Multiplex communications – Channel assignment techniques – Using time slots
Reexamination Certificate
1999-02-04
2002-03-05
Olms, Douglas (Department: 2661)
Multiplex communications
Channel assignment techniques
Using time slots
C370S235000, C370S252000, C370S447000, C370S461000, C370S462000, C370S516000
Reexamination Certificate
active
06353618
ABSTRACT:
FIELD OF INVENTION
The invention generally relates to the art of telecommunications traffic management and more specifically to a method and apparatus for controlling traffic flows in a packet-switched network, especially an ATM network, in order to provide constant bit rate service performance.
BACKGROUND OF INVENTION
The concept of a “traffic contract” is well known to those skilled in the art of telecommunications network engineering. Basically, a user or end-station device agrees to transmit packets according to certain pre-defined or negotiated traffic parameters, and in return the network will provide a certain service performance. If, however, the traffic flow from the end-station to the network does not conform to the traffic parameters as specified by a pre-determined conformance algorithm, the network does not have to provide the requested service performance.
The negotiated characteristics of an ATM connection are specified in ATM traffic management protocols, for instance the ATM Forum Traffic Management Specification, Version 4.0, doc. no. af-tm-0056.000, April 1996, which is incorporated herein by reference. These negotiated characteristics include:
(a) the desired service category and QoS parameters, such as the cell loss ratio and delay;
(b) the traffic descriptor, comprising, for instance, the PCR and CDVT, discussed in greater detail below; and
(c) the conformance definition used to unambiguously specify the conforming cells of the connection.
One service category defined by the ATM traffic management protocol is the constant bit rate (CBR) service which provides a connection a static amount of bandwidth that is continuously available during the lifetime of the connection. The requested bandwidth is characterized by the Peak Cell Rate (PCR) value. Another service category is the unspecified bit rate (UBR) service category which also includes a PCR value that the network may try, but does not guarantee, to meet. The PCR is explicitly stated for each ATM connection request. For instance, a switched virtual connection (SVC) call setup message includes an information element (IE) specifying the PCR value.
The CDVT or Cell Delay Variation Time, is a measure of the maximum allowed burstiness of a CBR connection. When packets or cells from two or more connections are multiplexed in a node, cells from a given connection may be delayed while cells of another connection are inserted at the output of the multiplexer. Similarly, some cells may be delayed while physical layer overhead cells are inserted. Consequently, with reference to the peak emission interval, T, which is the inverse of the contracted PCR, some randomness may affect the inter-arrival time between consecutive cells of a connection as monitored at the user-to-network interface (UNI). The upper bound on the degree of permissible clumping or burstiness is the CDVT parameter. Presently, this parameter is not explicitly negotiated when a connection request is received by the network, but rather is implicitly negotiated at subscription time.
The ATM conformance definition employs the Generic Cell Rate Algorithm (GCRA) which is used to define, in an operational manner, the relationship between the PCR and CDVT. The GCRA is defined with two parameters, the Increment, I, and the Limit, L. For CBR service, I=T=1/PCR, and L=CDVT. The GCRA determines for each cell arrival whether or not the cell conforms to the traffic contract of the connection. The GCRA is illustrated in
FIG. 1
(original source: page 63 of ATM Forum Traffic Management Specification, Version 4.0, doc. no. af-tm-0056.000, April 1996). The GCRA is equivalent to a leaky bucket controller (LBC) algorithm. Specifically, a stream is GCRA(I, L) conformant if it conforms to an LBC with bucket size
σ
=
1
+
L
I
and token rate
ρ
=
1
I
.
It should be noted that an LBC controller with parameters (&sgr;,&rgr;) ensures that the largest number of conformant cells between any two instances of time t
1
and t
2
is no more than &sgr;+&rgr;*(t
2
−t
1
).
An end-station device can be modelled as sourcing a plurality of traffic connections. For example, a wide-area-network may comprise two local-area-networks which are connected through a public ATM network. Each local-area-network comprises a number of workstations which are linked through a concentrator device that multiplexes the traffic streams from the various workstations for transmission over the ATM network. Since a key element of the traffic contract from the perspective of the user or end-station, e.g., the concentrator, is the sequence of cells sent to the network, the end-station will typically employ a scheduler or virtual shaping device which processes the multiplexed source cell stream such that the resultant output toward the network conforms to the traffic parameters specified in the traffic contract.
At the other side of the user-to-network interface, the network typically includes a connection admission control (CAC) function in order to determine whether a connection request should be admitted or denied. As discussed above, a connection request typically defines the source traffic parameters and the requested service performance or quality of service (QoS) class. For a switched connection such as an SVC the connection request occurs at call origination time, and for a permanent connection such as a PVC the connection request occurs when the permanent connection is provisioned. The CAC will only accept the connection request provided that the QoS for existing connections would still be met if the new request is accepted. CAC is typically carried out on a node-by-node basis for switched connections and through a centralized bandwidth management system for permanent connections. For accepted connection requests, CAC determines the configuration of the traffic conformance algorithm, routing, and resource allocation, including trunk bandwidth, buffer space, and internal node resources. It will be appreciated that in order to achieve high switching rates, the CAC must be simple and operate very rapidly.
Once the connection is accepted, the network must typically monitor the connection at the end-station access in order to protect network resources from behaviour which can affect the QoS of other already established connections. This is accomplished by detecting violations of negotiated parameters and taking appropriate actions. In ATM standards, this function is commonly termed Usage Parameter Control (UPC). The UPC typically employs the GCRA for monitoring the connection. However, there are some instances where UPC cannot be applied at the periphery of a network for various reasons.
Network node elements also have the problem of having to shape traffic flows. This is because a network element has to schedule incoming packets or cells from a variety of connections or queues into an outgoing link which interconnects a counterpart network element. The scheduler, arbiter or virtual shaping device of a network element must employ an effective service discipline in order to meet different levels of QoS and bandwidth requirements. For example, the receiving network element may accept only a certain degree of packet clumping or burstiness, i.e., packet or cell delay tolerance, otherwise buffers on the receiving network element would overflow. The network scheduler, arbiter or virtual shaping device should also ideally operate very rapidly in order to achieve high switching rates.
SUMMARY OF INVENTION
Generally speaking, the invention provides a method and related apparatus for scheduling packets in a non-work conserving manner at a queueing point in order to minimize, or at least quantify, the maximum burstiness or jitter of a packet stream.
According to one aspect of the invention, a data communication method is provided for use in a packet-switched network. The method comprises:
(a) receiving packets from a traffic source, such as a connection, and queuing the packets in a memory;
(b) defining a repeating scheduling frame having a duration FD and a total of FL slo
Davis Tom
Hung Anthony
Pezeshki-Esfahani Hossain
Alcatel Canada Inc.
Hom Shick
Macchione Alfred A.
Olms Douglas
LandOfFree
Method and apparatus for controlling traffic flows in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for controlling traffic flows in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling traffic flows in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2849582