Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-06-23
2002-06-11
Vincent, David (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395210, C370S412000
Reexamination Certificate
active
06404768
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to storing cells of ATM packets for service from a server. More specifically, the present invention is related to storing cells of ATM packets in buffer administration groups until the cells are scheduled for service from a server.
BACKGROUND OF THE INVENTION
Earlier researchers have proposed dynamic threshold schemes limited to a set of destinations ports sharing the same memory and assuming equal sharing among ports. However, sharing of buffer among destinations may not be equal. For example, we may like to dedicate more buffer for a WAN uplink. Further, bandwidth in a given port may be partitioned into virtual pipes for commercial purposes. It may be desirable to dedicate different fraction of buffer to each virtual pipe e.g. proportional to the fraction of bandwidth. Similarly, a virtual pipe may have traffic from separate traffic classes with different buffer requirements. Further traffic from each class may have multiple VCs below it. Thus, there is a need for a more flexible buffer sharing scheme. This scheme should track the natural hierarchy of sharing, offer flexibility for weighted sharing among different destinations during congestion, and be based on dynamic thresholds to allow maximal utilization of shared memory by a single destination.
A scheme by Choudhury and Hahne [A. K. Choudhury and E. L. Hahne. Dynamic Queue Length Thresholds in a Shared Memory ATM Switch. In IEEE Infocom, pages 679-687, March 1996], incorporated by reference herein, allows maximal sharing of memory using dynamic thresholds. However, the scheme restricts memory to be shared equally among ports under congestion.
In the scheme by Choudhury and Hahne, when there is only one switch output port that is very active, it should have access to as much of the share memory buffer as possible. When there are many contending queues, however, it is desired to divide the memory fairly among them. All queues with sufficient traffic to warrant thresholding should obtain the same amount of space, called the control threshold. The control threshold value is determined by monitoring the total amount of unused buffer space.
Each output queue attempts to limit its length to some function of the unused buffer space; output queues with less demand than this can have all the space they wish. At time t, let T(t) be the control threshold and let Q
i
(t) be the length of queue i. Let Q(t) be the sum of all the queue lengths, i.e. the total occupancy of the shared memory. Then, if B is the total buffer space,
T
(
t
)=ƒ(
B−Q
(
t
))=ƒ(
B−&Sgr;
i
Q
i
(
t
)) (1)
An arriving cell for queue i will be blocked at time t if Q
i
(t)≧T(t). All cells going to this queue will be blocked until the queue length drops below the control threshold.
The simplest scheme proposed is to set the control threshold to a multiple a of the unused buffer space.
T
(
t
)=&agr;(
B−Q
(
t
))=&agr;(
B−&Sgr;
i
Q
i
(
t
)) (
2
)
Typically, &agr; is chosen to be a power of 2 (either positive or negative) to simplify implementation to a shifter.
The above Dynamic Threshold scheme adapts to changes in traffic conditions. Whenever the load changes, the system will go through a transient. For example, when an output port suddenly becomes congested, its queue will grow, the total buffer occupancy will go up, the control threshold will go down, and queues exceeding the threshold will have their arrivals blocked temporarily while they drain, freeing up more cell buffers for the newly active queue. If there are M queues, all very active, then their “steady state” queue lengths will be
Q
i
(
t
)
=
T
(
t
)
=
α
1
+
α
M
(
B
-
S
)
,
(
3
)
where S is the space occupied by queues below the control threshold. The amount of memory held in reserve by the algorithm is
(
B
-
S
)
1
+
α
M
.
If &agr;=2, for instance, a single queue with no competition is allowed to take ⅔ of the entire shared memory, and ⅓ is held back. If M then increases from 1 to 10, that long queue will drain, and the newly active queues will grow, until all ten stabilize at {fraction (2/21)} of the buffer, with {fraction (1/21)} unallocated.
The above scheme deliberately wastes a small amount of buffer space. This “wasted” buffer space actually serves two useful functions. The first advantage of maintaining some spare space at all times is that this provides a cushion during transient periods when an output queue first becomes active. This reduces cell loss during transients. Secondly, when an output queue has such a load increase and begins taking over some of the spare buffer space, this action leads to the buffer allocation mechanism to adjust threshold. If there were no built-in share buffering, then the cell arrival rates and/or loss rates of the individual output queues would have to be monitored to determine when load conditions had changed.
The present invention allows for sharing among ports in some pre-determined proportions, for an arbitrary number of hierarchies, packet traffic and packet level dropping mechanisms viz. EPD, PPD, RED.
SUMMARY OF THE INVENTION
The present invention pertains to an apparatus for serving ATM packets, each packet having cells. The apparatus comprises a server which provides service to a cell. The apparatus comprises a scheduler mechanism which determines which cell is to receive service from the server. The scheduler mechanism is connected to the server. The apparatus comprises a shared memory mechanism having a first region for storing cells of a first packet of a first connection and at least a second region for storing cells of a second packet of a second connection. Each region has a dynamic size determined by demands of the corresponding connection.
The present invention pertains to an apparatus for serving ATM packets, each packet having cells. The apparatus comprises a server which provides service to a cell. The apparatus comprises a scheduler mechanism which determines which cell is to receive service from the server. The scheduler is connected to the server. The apparatus comprises a shared memory mechanism which has a buffer management module having buffer administration groups for receiving cells of packets from connections. Each buffer administration group has a dynamic threshold which adapts to changes in traffic conditions. The threshold identifying the number of cells the buffer administration group can store.
The present invention pertains to a method for serving cells of ATM packets. The method comprises the steps of storing a cell of an ATM packet of a first connection in a first buffer administration group of a shared memory independent of any scheduling considerations. Then there is the step of servicing the cell from the first buffer administration group after a scheduler determines the server connected to the buffer administration group is able to provide service to the cell.
The present invention pertains to a method for serving cells of ATM packets. The method comprises the steps of storing a cell of an ATM packet of a first connection in a first buffer administration group of a shared memory. Then there is the step of changing a dynamic threshold defining the number of cells the first buffer administration group can store. Next there is the step of receiving another cell at the first buffer administration group.
REFERENCES:
patent: 5555265 (1996-09-01), Kakuma et al.
patent: 5610914 (1997-03-01), Yamada
patent: 5838681 (1998-11-01), Bonomi et al.
patent: 5862137 (1999-01-01), Manning et al.
patent: 5936958 (1999-08-01), Soumiya et al.
patent: 6188698 (2001-02-01), Galand et al.
Adams Jay P.
Basak Debashis
Marconi Communications Inc.
Schwartz Ansel M.
Vincent David
LandOfFree
Method and apparatus for serving ATM packets/cells 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 serving ATM packets/cells, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for serving ATM packets/cells will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2974893