Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-04-18
2001-07-24
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C709S227000
Reexamination Certificate
active
06266323
ABSTRACT:
BACKGROUND
The present invention relates to transmission of variable bit rate data via a shared medium, and more particularly to techniques for determining whether a shared medium can accept data from a variable bit rate data source without exceeding tolerable packet loss rates and delay limits.
In many systems, sampled data is generated at regular intervals (i.e., the “sampling period”) in the form of variable size packets. Variable bit rate compressed speech sources are one source for such data. It is typical for a number of sources of variable size packets to use time multiplexing techniques to share a transmission medium. As an example, asynchronous transfer mode (ATM) is a standard protocol that is commonly used for transmitting asynchronous telecommunication data within a telecommunication system for one or more applications that provide variable size packets. The ATM protocol, however, is based on the transmission of data in fixed size data packets known as ATM cells. The protocol for each ATM cell is the same, wherein, each ATM cell contains a forty-eight octet payload and a five octet header. In general, ATM is well known in the art.
The telecommunication data associated with each application is initially in a data transfer format that is application specific. If ATM is to be used for transporting the data, the application specific data format must be adapted so that it is compatible with the ATM protocol. This is accomplished by an ATM adaptation layer (AAL)
101
, as illustrated in FIG.
1
. Referring now to
FIG. 1
, the application layer
102
represents telecommunication data arriving from a specific telecommunication data application. The task of the AAL
101
, as mentioned, is to reformat the data so that the data is compatible with the ATM protocol. Once reformatted, the ATM layer
103
can transport the data to a desired receiving unit.
A commonly employed AAL is AAL
2
, which is sometimes referred to as AALm. AAL
2
, is typically used to transform low bit rate, asynchronous data, such as cellular voice data into a format that may be supplied to the ATM layer
103
. More particularly, AAL
2
segments low bit rate data streams into small data packets, which are often called minicells or microcells. The small data packets from a particular low bit rate, asynchronous data source are then multiplexed together with small packets from other similar data sources to form ATM cells. By segmenting the data into smaller, variable size data packets and by multiplexing the small packets from multiple data sources, data transportation delays are reduced and bandwidth utilization is improved. In addition, transportation delays can be further reduced and bandwidth utilization further improved by allowing the small data packets to overlap between adjacent ATM cells, as illustrated in FIG.
2
.
In known systems, when variable bit rate data is transmitted via a shared medium (e.g., through a leased line of constant bit rate), the utilization (efficiency) of the shared medium is low because the compressed rate is normally below the allocated space in the shared medium. This will typically be the case if, for example, a Virtual Private network is used to carry telephone connections between different sites of a company, or if a cellular operator uses leased lines to carry compressed voice packets. The low utilization is generally a consequence of the fact that the design of conventional systems accommodates worst-case situations by assuming that each data packet will have its maximum size, thereby ignoring the fact that an individual data packet will often be smaller than its maximum possible size.
Conventional systems can increase efficiency by reducing the allocated capacity while applying buffering at the entrance of the shared medium. Buffering is necessary because the reduction of the allocated capacity on the shared medium eliminates any guarantee that the arriving data packets can be transmitted immediately. If the total arrival rate is temporarily higher than the total allocated capacity, data packets must be discarded or buffered. This will result in excessive transmission delay and/or information loss which can seriously impact the quality of service where the data is, for example, compressed speech data.
Consequently, there is a need for techniques of utilizing and designing transmission mediums that are to be shared by variable bit rate data sources.
SUMMARY
In accordance with one aspect of the present invention, a new connection that will supply new variable bit rate data packets to be transmitted may be established in a shared system for transmitting variable bit rate data packets. The new variable bit rate data packets may be, for example, new variable rate speech packets. This is performed by determining whether establishment of a new connection will cause the shared system to exceed a predefined sample loss rate by using information about a data packet repetition rate that is common to all connections and information about a distribution of packet sizes for each existing connection and for the new connection. Then, the new connection is established if it is determined that the predefined sample loss rate will not be exceeded. Otherwise, the new connection is rejected if it is determined that the predefined sample loss rate will be exceeded.
In one embodiment, establishing or rejecting a new connection is performed by determining, for the new connection, a value of a moment generating function defined as:
ψ
X
(
Θ
)
=
∑
i
=
1
S
P
i
ⅇ
Θ
R
i
where S is the number of possible data packet sizes for the new connection, (R
i
, P
i
) pairs are possible new connection data packet sizes, R
i
, with corresponding assigned probabilities, P
i
, and &thgr; is an arbitrary positive real number. Then, a determination is made regarding whether any value of &thgr; exists that satisfies the Chernoff bound as expressed in the following inequality:
-
Θ
L
buf
+
∑
j
log
ψ
X
j
(
Θ
)
≤
log
P
e
where j indexes through all established connections and the new connection, L
buf
is a length of a buffer for storing data packets supplied to the shared system for transmitting variable bit rate data packets, and P
e
is a predefined packet loss rate that can be tolerated in the shared system for transmitting variable bit rate data packets. If a value of &thgr; exists that satisfies the Chernoff bound, then the new connection is established. Otherwise, if no value of &thgr; exists that satisfies the Chernoff bound, then the new connection is rejected.
In another aspect of the invention, the step of determining whether any value of &thgr; exists that satisfies the Chernoff bound comprises the step of retrieving values of the moment generating function for all established connections from data storage means.
In yet another aspect of the invention, L
buf
is determined in accordance with the following equation:
L
buf
=D
limit
·r
where D
limit
is a predefined delay limit and r is a predefined rate of packet transmission in the shared system for transmitting variable bit rate data packets.
In still another aspect of the invention, the buffer is a first-in-first-out (FIFO) queue, and the technique further comprises the step of inserting each arriving data packet at the end of the FIFO queue.
In another embodiment of the invention, a new connection that will supply new variable bit rate data packets to be transmitted in a shared system for transmitting variable bit rate data packets may be established, wherein every data source in the shared system provides variable bit rate data packets having identical size distributions. The new variable bit rate data packets may be, for example, new variable rate speech packets. This is accomplished by determining &thgr;value of a that minimizes the left side of the inequality:
−&THgr;L
buf
+n·log&psgr;
x
(&THgr;)≦logP
e
where L
buf
is a length of a buffer for storing data packets supplied to the shared s
Valko Andras
Westberg Lars
Burns Doane Swecker & Mathis L.L.P.
Chin Wellington
Nguyen Steven
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Resource estimation for variable bit rate data sources does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resource estimation for variable bit rate data sources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource estimation for variable bit rate data sources will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549404