Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-10-14
2003-11-11
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S395400
Reexamination Certificate
active
06646986
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of transfer rate control of multi-class packetized data. In particular, it is directed to methods of and apparatus for controlling and scheduling a large number of classes of data streams of variable sized packets sharing a high speed channel.
BACKGROUND OF INVENTION
This work is funded in part by the U.S. Government under Technology Investment Agreement, TIA F30602-98-2-0194.
Transfer rate control of data streams in a data network is needed for service quality control. It is also needed for realizing dynamic virtual networks where a high capacity, wide coverage network is divided into a number of virtual networks generally of different coverage and capacity. A data stream (or a class of data stream) is defined by (1) spatial attributes such as the source and sink nodes of a stream, (2) the grade-of-service attributes, such as blocking a connection request or delay of acceptance, and (3) quality-of-service attributes, such as packet delay or loss.
The use of rate control in data networks was accentuated with the emergence of ATM technology. In ATM, the cell size is constant. The fixed size of cells somewhat simplifies the control of data transfer rates. Several methods have been proposed for ATM rate control. For example, in U.S. Pat. Nos. 5,905,730 May 18, 1999 Yang et al and 5,926,459 July 20, 1999 Lyles et al.
U.S. Pat. No. 5,905,730 described a high speed packet scheduler which provides a high degree of fairness in scheduling packets associated with different sessions. An arriving packet is assigned a virtual start time and then a virtual finish time is calculated using its transfer time, length and other parameter. The packet with the smallest virtual finish time is then scheduled to transfer. U.S. Pat. No. 5,926,459, on the other hand, describes a traffic shaper in a packet switched communications system. The shaper includes a queueing mechanism and a scheduling mechanism. The scheduling mechanism comprises separate queues for packets with different priorities and a queue control mechanism for monitoring emission from the queues and for selectively de-scheduling packets on the queues.
PCT patent application WO98/46037 published on Oct. 15, 1998 has the present inventor as a co-inventor and described in detail the service rate regulator for ATM streams. It describes among other things the serial time domain rate control in which the controller tracks the required sampling instances of the data streams by using a time-space map. The concept of null class in the ATM environment is also described therein, in that a null class is created to use unassigned channel capacity.
More recently, the Internet, which transfers pacektized data of differing sizes, has gained widespread popularity. The Internet uses the Internet Protocol (IP) which relates to variable-size data. Presently, the Internet does not provide quality-of-service (QOS) control, and any enhancement of the IP that aims at providing QOS control is likely to require some form of transfer rate control of variable-size packets.
In a ATM, the transfer rate control is based on controlling the rate of transfer of cells of fixed sizes. In IP, such control must be based on controlling the bit rate not the packet rate, since the packets are generally of different sizes. Achieving precise rate control of variable-size packets is more intricate than realizing precise rate control of fixed size packets. It is more difficult to track data transfer rates of multiple data streams of variable packet sizes.
The packet scheduling problem may be summarized as follows:
Transfer rate regulation is a post admission problem. A number of data streams, each stream containing a number of connections, share a common channel. Each data stream has a specified data transfer rate such that the sum of the specified data transfer rates of all the data streams does not exceed the capacity of the shared channel. The rate allocations of a connection in a data stream may be based on user specifications or on traffic measurements at network ingress. A node is required to determine the best timing (schedule) of transmission of the packets of each data stream it receives from traffic sources so that the spacing of the packets of each stream conforms to the specified sampling interval of the stream. The sampling interval for transfer is inversely proportional to the specified transfer rate of the stream. This requirement must be satisfied for all the data streams that share the same channel. Furthermore, the packet sizes are generally unequal.
The present invention therefore aims at providing a method of and apparatus for controlling transfer rates or scheduling the service time of a large number of data streams of variable-sized packets sharing a high speed channel. The invention uses an expanded calendar for scheduling the service times of multiple data streams. The expanded calendar consists of an expanded time-space map, where a time slot in the map is associated with a stream identifier. A designated data stream is indicated by its stream identifier. The calendar (timespace map) is expanded by a predetermined expansion factor. The calendar expansion is a technique in which the number of time slots in the calendar is increased to exceed the maximum number of events recorded in the calendar at any time. This implies faster scanning of the calendar. The purpose of the expansion is to reduce a calendar's spatial congestion which may occur when the time slots become so occupied that scheduling subsequent events require extensive search and results in scheduling delay jitter.
SUMMARY OF INVENTION
Briefly stated, in accordance with one aspect, the invention is directed to a data structure for transfer rate control of K data streams into a shared channel, wherein the data streams contain variable-sized packets and K is a positive integer greater than unity. The data structure comprises an array of K pointers pointing to K packet buffers, each of which packet buffers is to hold the packets of respective data streams, and a calendar having a J-times expanded time-space map organized in L calendar slots holding either a data stream identifier or a vacant entry, J and L being positive integers greater than 1. The structure further includes a search array having one-to-one correspondence to the calendar slots for searching the calendar for eligible data streams for transfer and a control data table having K records, each record for each data stream having following fields; a scaling factor F, a nominal sampling interval &Dgr; expressed in the number of calendar slots, a credit C in arbitrary units, a normalized length B of the packet of the data stream at the head of its packet buffer, and a next service time slot T of the calendar.
In accordance with another aspect, the invention is directed to an apparatus for transfer rate control of K data streams into a shared channel wherein the data streams contain variable sized packets and are stored in K packet buffers, K being a positive integer. The device comprises 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 and a control data memory C holding specification of the data streams. The device further includes a search control circuit for locating a vacant slot indicator in memory B 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
In accordance with yet a further aspect, the invention is directed to 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 wherein each data stream has packets of
Kizou Hassan
Nortel Networks Limited
Waxman Andrew M.
LandOfFree
Scheduling of variable sized packet data under transfer rate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling of variable sized packet data under transfer rate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling of variable sized packet data under transfer rate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3155810