Scheduling of variable sized packet data under transfer rate control
AssigneeNortel Networks Limited
InventorMaged E. Beshai
Life of this patent
Estimating the term…
Abstract
The invention relates to scheduling packets from numerous traffic classes that share a common high speed channel. A method and an apparatus for regulating several thousand traffic classes sharing a very high speed common channel of a capacity of the order of 80 Gb/s are described. The packets are generally of variable size, and each channel is assigned a transfer rate less than or equal to the capacity of shared channel, with the sum of transfer rates of all classes not exceeding the capacity of the shared channel. The rare allocation for each class is determined either by operator specification or, preferably, by automated means based on traffic monitoring. In the latter case, the transfer rate allocated to a class may be dynamically updated.
Claims22
An apparatus for transfer rate control of K data streams into a shared channel, the data streams containing variable sized packets and being stored in K packet buffers and K being a positive integer, the apparatus comprising:
- a pointer memory storing K pointers to the K packet buffers;
- a memory A containing an expanded time-space map for storing identifiers of data streams eligible for transfer in an array of calendar slots;
- a memory B having one-to-one correspondence with the memory A for locating a vacant calendar slot;
- a control data memory C holding specification of the data streams;
- a search-control circuit for locating a vacant slot indicator in memory B;
- a ready queue memory D for storing the identifiers of the data streams ready for transfer;
- and
- a transfer control circuit for determining transfer eligibility of each data stream based on the specification contained in the control data memory C and enabling the transfer of the packet of one of K packet buffers to the ready queue memory D.
A method of scheduling transfer of a plurality of data streams from a plurality of packet buffers to a shared channel by accessing calendar slots of a calendar, each data stream having packets of variable sizes and the calendar having an expanded time-space map forming the calendar slots for tracking service time of each data stream for eligibility for transfer, comprising steps of;
- at each access of a calendar slot when a stream identifier is read,
- (a) accumulating for each data stream a pre-calculated transfer credit;
- (b) ascertaining a packet size of each data stream;
- (c) declaring a data stream eligible for transfer if an accumulated transfer credit exceeds a predefined fraction of the packet size;
- and
- (d) retaining a transfer credit remainder in excess of the packet size.
A method scheduling the transfer of data streams having packets of variable sizes from a plurality of K packet buffers to a shared channel using an expanded calendar wherein a waiting packet from a packet buffer is transferred immediately to a ready queue at the calendar service time slot at which the data stream identity is read, and a future service time slot at which the data stream is eligible for subsequent packet transfer is determine by a calendar hop defined by the lesser of the packet size and a hop threshold, wherein if the product of a normalized packet size and a respective nominal calendar hop exceeds the hop threshold, the following steps are executed:
- (a) incur a penalty for the respective traffic stream equal to said product;
- (b) execute an intermediate hop determined by the lesser of the magnitude of the penalty and the hop threshold;
- (c) accrue a hop credit in each intermediate hop proportional to the number of the calendar slots in the hop;
- (d) reduce the penalty by the hop credit;
- (e) repeat steps (b), (c), and (d) until the penalty is offset, and
- (f) retain a credit fraction resulting from step (d).
The method of scheduling transfer of a plurality of rate-regulated and unregulated data streams from a plurality of packet buffers to a shared channel by accessing calendar slots of a calendar, each data stream having packets of variable sizes and the calendar having an expanded time-space map forming the calendar slots for tracking service time of each data stream for eligibility for transfer, comprising steps of:
- at each access of a calendar slot,
- assigning K classes to K rate-regulated data streams;
- assigning a null class to the unregulated data streams, and
- allocating a transfer rate equal to the difference between the channel capacity R and the sum of the allocated transfer rates of the K classes.
Dependencies are inferred from the claim text.