Complete packet discarding

Details Complete packet discarding Complete packet discarding

1998-06-30

2002-03-26

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S231000, C370S235000, C709S235000

Reexamination Certificate

active

06363069

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 which 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 which 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 number 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 is the 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 discards complete packets. When a cell that arrives at a node finds the node's buffer full, a connection is selected for discarding of cells. The selected connection is one which includes at least one cell that corresponds to the beginning of a packet. In another embodiment, the connection is chosen by first making an initial selection, determining whether that selection can stand, and if not, by making an alternate selection. When an alternate selection is made, a credit factor associated with the initial selection is decremented, while the credit factor of the alternate selection is incremented. The initial selection can be carried out by considering the overall traffic load at the node, the individual traffic loads that comprise the overall traffic load of the node, and the QoS that is desired for the various connections that are active in the node.


REFERENCES:
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 5233606 (1993-08-01), Pashan et al.
patent: 5282203 (1994-01-01), Oouchi
patent: 5650993 (1997-07-01), Lakshman et al.
patent: 5729530 (1998-03-01), Kawaguchi et al.
patent: 5764641 (1998-06-01), Lin
patent: 6092115 (2000-07-01), Choudhury et al.
patent: 6246687 (2001-06-01), Siu
Kara et al. (“Toward a Framework for Performance Evaluation of TCP Behaviour over ATM Networks”, ICCC'97, pp. 1-12.*
Lakshman et al. (“The Drop from Front Strategy in TCP and in TCP over ATM”, IEEE, pp. 1242-1250, 1996).*
Hassan et al. (“Impact of Cell Loss on the Efficiency of TCP/IP over ATM”, GLOBECOM'94, pp. 1-11, Feb. 9, 1994).*
Statistical Analysis and Simulation Study of Video Teleconference Traffic in ATM Networks, Daniel Hayman, et al, IEEE Transactions on Circuits and Systems for Video Technology

Affiliated with

Also associated with

Rating

Complete packet 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 Complete packet discarding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complete packet discarding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2824675