Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-06-30
2002-04-23
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S232000, C370S235000, C370S395210
Reexamination Certificate
active
06377547
ABSTRACT:
BACKGROUND
This invention relates to ATM networks and, more particularly, to approaches for transmitting cells through ATM network nodes that, at times, are unable to accommodate incoming data.
ATM networks transmit cells from a source point in the network to a destination point in the network by passing the cells from node to node through connecting links. Each node comprises a number of input ports and output ports. Here we consider an ATM switch with output port buffering. Connections from different input ports can be routed to the same output port. Each output port will function as a multiplexer. An incoming cell is routed to a particular one of the output ports in accordance with a path that is established for a virtual circuit to which the cell belongs. Each cell has a header portion and a data portion. In addition to the virtual connection's ID, the header portion includes information about control information about the data that it is carrying. The data carried by the cells may have its own, higher level, structure, such as “packets” that are made up of a number of cells.
It is possible that the packets that need to be transmitted on a particular output port are too numerous to be accommodated by the bandwidth available at a link connected to that particular output port. To prevent the loss problem that, obviously, might occur, a buffer is provided. Still, it is possible for the buffer to overflow, causing a loss of cells. Obviously, if a cell loss must be suffered, it is better to lose cells in accordance with a thought-out algorithm, than to lose cells indiscriminately.
To date, most efforts pertaining to cell loss in an ATM node have been concentrated on methods for increasing ATM network efficiency by maximizing statistical gain while still guaranteeing the aggregated Quality of Service (QoS) of connections. Most of the work is based on the use of a single First-In-First-Out (FIFO) buffer for all connections. The problem with a simple FIFO buffer approach is that there is no way to distinguish one connection from another without adding some costly enhancements. It has been shown, however, that in a single FIFO queuing system where no accounting is taken of connections, if arriving cells are dropped in case of buffer overflow, for a given set of connections the burstier connections experience a higher Cell Loss Ratio (CLR) and may actually fail to maintain the desired QoS levels, even though the QoS of that aggregate traffic is still satisfied.
In contrast to single FIFO queuing architecture, “per-virtual connection” queuing provides a more flexible and effective architecture for enhancing traffic management at ATM nodes. With such an architecture, one can attempt to fairly distribute shared buffer resources across active connections so as to provide QoS assurance on individual connection basis.
All currently known schemes for buffer sharing require some pre-calculated thresholds that require prior knowledge of traffic characteristics and of the service discipline to be used but which are very difficult to determine and not practical to implement. In “Dynamic Queue Length Thresholds in a Shared Memory,” by A. Choudhury and E. Hahne,
Proc. INFOCOM'
96, pages 679-687, 1996, for example, a dynamic queue length thresholds scheme is proposed to selectively discard packets where the maximum permissible length of any individual queue at any instant is a function of the unused buffer capacity. Compared with static threshold schemes, this scheme automatically adapts the load variation among the output queues. However, the assurance of cell loss requirements for individual connections is not addressed in this scheme.
A Weighted Fair Blocking (WFB) mechanism for discrete-time multiplexing is proposed in “Weighted Fair Blocking Mechanism for Discrete-Time Multiplexing,” by A. Conway and C. Rosenberg,
Proc. INFOCOM'
96, pages 1045-1053, 1995. In WFB, packets arrive in batches and the algorithm rejects some of the packets in a batch arrival when there is insufficient space in the buffer, or buffers. Although it is claimed that WFB decouples buffer dimensioning from parameterization of the discard algorithm, the process of determining appropriate weights so as to satisfy different loss requirements remains as difficult as determining appropriate threshold values in any threshold based control policies. The fact that, when implementing the WFB mechanism, a linear programming approach is used in the computation of the packet selection probabilities, and prior knowledge of source traffic characteristics is required, attests to the current impracticality of the WFB approach.
The cell loss performance of individual connections does get addressed by D. Haymand et al in “Statistical Analysis and Simulation Study of Video Teleconference Traffic in ATM Networks,”
IEEE Trans. Circuits and Sys. For Video Technology
, 2(1):49-59, March 1992, where the ATM multiplexer keeps track of accumulated cell losses for all active connections. When a new cell arrives and the buffer is full, a cell is discarded from the connection that has the lowest current accumulated loss rate (among all connections that have cells currently in the buffer). This approach requires on-line measurements of both the numbers of losses and arrivals, and it requires maintaining running ratios, which is computationally intensive, and does not allow for QoS requirements. A generalized version of the above, given in “A Measurement-Based Loss Scheduling Scheme,” by T. Yang and J. Pan in
Proc. INFOCOM'
96, pages 1062-1071, 1996, deals with situations where traffic streams have different characteristics as well as different loss (QoS) requirements. When a cell arrives and the buffer is full, a cell is discarded only if it belongs to a connection with the smallest ratio between its loss ratio measurement and its loss performance requirement, a predetermined number. The limitations of the Yang et al scheme are that not only that is on-line measurement of cell loss ratio required, but it is not optimal if all connections are not equally demanding.
What is needed, then, is an effective and simple-to-implement technique that redistributes cell losses according to each connection's QoS.
SUMMARY
The disadvantages of prior art cell discarding techniques are overcome with a method that intelligently selects cells for discarding from a node with a full buffer. A cell from a chosen connection is chosen for discarding based on the individual traffic loads that comprise the overall traffic load of the node, on the traffic load of the chosen connection, and on the QoS that is desired for the various connections that are active in the node. In accordance with an illustrative embodiment, a fair ratio of loss is defined for each of the set of connections that are active in the node based on the aforementioned traffic and QoS considerations. When an incoming cell finds the buffer full, a connection is selected, based on the computed fair ratio of loss values. When the connection thus selected does not have a cell to be discarded, another connection is selected for discarding a cell. To maintain the desired “fairness”, a credit factor is maintained in association with each of the subqueues in the buffer, and when the initially selected subqueue is replaced with a substitute subqueue, the credit factor of the former is decremented, and the credit factor of the latter is incremented.
REFERENCES:
patent: 4475192 (1984-10-01), Fernow et al.
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5233606 (1993-08-01), Pashan et al.
patent: 5404354 (1995-04-01), Hayter et al.
patent: 5729530 (1998-03-01), Kawaguchi et al.
patent: 5764641 (1998-06-01), Lin
Fang et al., Simulation Study of TCP Performance in ATM Networks, IEEE, pp. 1217-1223, 1996.*
Li et al., On TCP performance in ATM networks with per-VC early packet discard mechanisms, Elsevier Science, pp. 1065-1076, 1996.*
Tung et al., Resource Allocation Algorithms for ATM Nodes Supporting Heterogeneous Traffic Sources Subject to Varying Quality of Service Requirements, IE
Levy Yonatan Aharon
Mang Xiaowen
AT&T Corp.
Chin Wellington
Duong Frank
LandOfFree
Quality of service-oriented cell disc discarding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quality of service-oriented cell disc discarding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quality of service-oriented cell disc discarding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896955