Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-01-24
2003-03-18
Rao, Seema S. (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S412000
Reexamination Certificate
active
06535484
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of cell switching network communications and, more specifically, to the efficient management of shared buffer resources within such a network.
BACKGROUND
The desire to integrate data, voice, image and video over high speed digital trunks has led to the development of a packet switching technique called cell relay or asynchronous transfer mode (ATM). ATM traffic is switched and multiplexed in fixed length cells and an ATM network typically provides a number of interconnected nodes which are capable of receiving data from other network nodes and forwarding that data through to other network nodes to its ultimate destination. Nodes are interconnected by transmission paths, each of which supports one or more virtual paths. Each virtual path contains one or more virtual channels. Switching can be performed at the transmission path, virtual path or virtual channel level.
Network nodes generally employ buffering schemes to prevent contention for switch resources (e.g., ports). In the past, this has included relatively unsophisticated solutions, such as a first-in-first-out (FIFO) queue at each port. This solution quickly leads to cells being dropped indiscriminately when the volume of network traffic is large. Other schemes involve “per connection” buffering where each logical connection (i.e., virtual path, virtual channel) is allocated its own cell memory. When the number of supported connections is large, however, the sum of the maximum buffer requirements for individual connections may drastically exceed the physical available memory.
If one large buffer resource is to be shared among a number of connections then, some form of buffer management must be employed. In the past, one solution has been to divide the buffer into a number of queues of fixed length and “hard allocate” capacity for each connection. The problem with this solution is that the fixed length queues offer no flexibility depending upon network traffic conditions. In addition, because of size and cost constraints, each queue would have to remain relatively small as a single switch may support thousands of logical connections. Those network connections with significant amounts of traffic would likely soon fill up their allotted queue and cell dropping would soon result. Another solution has been to oversubscribe the single memory resource and allow each connection to buffer up to a fixed maximum, but where the sum of all the connection maxima exceeds the memory capacity. This alternative relies on the fact that all connections are unlikely to require their maximum buffer space at the same time. Although this condition is true most of the time, it is inevitable that contention for buffer space will result at some point. Once contention does result, cells are dropped indiscriminately, i.e., without regard for whether a connection is already using a significant amount of buffer space or not. A third solution has been to reserve a minimum buffer allocation for each connection with the unallocated space available on a first-come-first-served basis. This allows each connection a guaranteed minimum buffer space. The problem with this solution is that where the number of logical connections runs into the thousands, a very large (i.e., expensive) common buffer is required for any reasonable minimum.
None of the buffer management schemes of the prior art have satisfactorily addressed the problem of per connection buffer management for large numbers of connections. Hence, it would be desirable to have a mechanism for effectively managing the oversubscription of a shared buffer resource.
SUMMARY AND OBJECTS OF THE INVENTION
It is therefore an object of the present invention to provide an improved method for managing the oversubscription of a common communications resource shared by a large number of traffic flows, such as ATM connections.
It is a further object of the present invention to provide an efficient method of buffer management at the connection level of a cell switching data communication network so as to minimize the occurrence of resource overflow conditions.
This and other objects of the invention are achieved by an effective method for managing oversubscription by dynamically changing the maximum buffer space allowed for a particular traffic flow or connection in response to the global utilization of a single buffer resource. A buffer utilization threshold for each of a number of various traffic flows is established. As new cells arrive, the global usage of the buffer resource is monitored. As the buffer fills, the individual thresholds for the various traffic flows are dynamically scaled based upon the global usage of the buffer. This method allows guaranteed buffer space for sensitive traffic flows despite the oversubscription. Aggressive buffer allocations are scaled back when necessary, thereby leaving space for traffic flows which are using only a small portion of their allocated buffer space. The present invention in effect maintains isolation between well behaved traffic flows, insuring that only flows which are using a disproportionate amount of memory are blocked from storing further cells or packets in the memory when the global resource usage approaches capacity.
In one embodiment, the thresholds are coded in mantissa and exponent form so that the scaling is accomplished by adjusting the exponent This approach allows a minimum of memory to be used to store the flow thresholds and simplifies the mechanism for scaling the thresholds.
Other objects, features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 4430712 (1984-02-01), Coulson et al.
patent: 4849968 (1989-07-01), Turner
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5157654 (1992-10-01), Cisneros
patent: 5274768 (1993-12-01), Traw et al.
patent: 5303078 (1994-04-01), Brackett et al.
patent: 5311509 (1994-05-01), Heddes et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5359592 (1994-10-01), Corbalis et al.
patent: 5379297 (1995-01-01), Glover et al.
patent: 5412655 (1995-05-01), Yamada et al.
patent: 5434848 (1995-07-01), Chimento, Jr. et al.
patent: 5499238 (1996-03-01), Shon
patent: 5517643 (1996-05-01), Davy
patent: 5530698 (1996-06-01), Kozaki et al.
patent: 5539899 (1996-07-01), Huynh et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5541919 (1996-07-01), Young et al.
patent: 5542068 (1996-07-01), Peters
patent: 5546389 (1996-08-01), Wippenbeck et al.
patent: 5548587 (1996-08-01), Bailey et al.
patent: 5550823 (1996-08-01), Irie et al.
patent: 5555264 (1996-09-01), Sallberg et al.
patent: 5557604 (1996-09-01), Usumi et al.
patent: 5557607 (1996-09-01), Holden
patent: 5568477 (1996-10-01), Galand et al.
patent: 5570362 (1996-10-01), Nishimura
patent: 5584015 (1996-12-01), Villette et al.
patent: 5600820 (1997-02-01), Johnston
patent: 5617416 (1997-04-01), Damien
patent: 5625625 (1997-04-01), Oskouy et al.
patent: 5633861 (1997-05-01), Hanson et al.
patent: 5680582 (1997-10-01), Slayden
patent: 5701495 (1997-12-01), Arndt et al.
patent: 5704047 (1997-12-01), Schneeberger
patent: 5742606 (1998-04-01), Iliadis et al.
patent: 5742765 (1998-04-01), Wong et al.
patent: 5765032 (1998-06-01), Valizadeh
patent: 5768275 (1998-06-01), Lincoln et al.
patent: 5793747 (1998-08-01), Kline
patent: 5796735 (1998-08-01), Miller et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5838677 (1998-11-01), Kozaki et al.
patent: 5844901 (1998-12-01), Holden et al.
patent: 5850395 (1998-12-01), Hauser et al.
patent: 5854911 (1998-12-01), Watkins
patent: 5875352 (1999-02-01), Gentry et al.
patent: 5898688 (1999-04-01), Norton et al.
patent: 5901147 (1999-05-01), Joffe
patent: 5970064 (1999-10-01), Clark et al.
patent: 5974466 (1999-10-01), Mizutani et al.
patent: 5978856 (1999-11-01), Jones
patent: 5982783 (1999-11-01), Frey et al.
patent: 5999518 (1999-12-01), Nattkemper et al.
patent: 5999533 (1999-12-01), Peres et al.
patent: 6011775 (2000-01-01), Bono
Hughes David A.
Klausmeier Daniel E.
Blakely , Sokoloff, Taylor & Zafman LLP
Cisco Technology Inc.
Rao Seema S.
LandOfFree
Method and apparatus for per traffic flow buffer management 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 per traffic flow buffer management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for per traffic flow buffer management will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3071105