Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-05-28
2004-08-31
Pham, Chi (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S392000, C370S412000, C370S429000
Reexamination Certificate
active
06785236
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a scheme for scheduling the transmission of streams of information over channels or links of an information network.
2. Discussion of the Known Art
Prior to transmission over links or logical channels of an information network, information streams corresponding, e.g., to voice, video, or data are typically stored in transmit buffers. It is not uncommon to transmit real time information such as voice and motion video together with non-time sensitive information (e.g., numerical data), serially over one logical channel or link between two nodes of a network.
For each network channel, descriptors representing information packets to be transmitted over the channel are received in a descriptor queue associated with the channel. There may be multiple internal queues within the descriptor queue for the channel, wherein the internal queues represent different classes of service carried by the same channel. When packet descriptors arrive, they are enqueued in their corresponding queues according to the desired transmission channel and class of service.
A transmit buffer is provided for each logical channel in the egress (i.e., transmission) direction. The buffers associated with the channels are served in a round robin fashion by operation of a scheduler, which acts to fetch and to forward a certain number of information packets to the buffers for transmission over the corresponding channels. That is, the buffers contain the actual information (e.g., IP packets) that will be transmitted over the channels of a system or network. To ensure a fair share of network resources over the channels, fair queuing and scheduling algorithms are typically used to allocate available bandwidth among all the logical channels. See, e.g., D. Stiliadis, et al., Efficient Fair Queuing Algorithms for Packet-Switched Networks, IEEE/ACM Trans. Networking, Vol. 6, No. 2 (April 1998); M. Shredhar, et al., Efficient Fair Queuing Using Deficit Round Robin, IEEE/ACM Trans. Networking (June 1996); S. Golestani, A Self-Clocked Fair Queuing Scheme for Broadband Applications, Proc. IEEE/INFOCOM 94; and A. Demers, et al., Analysis and Simulation of a Fair Queuing Algorithm, Proc. of ACM SIGCOMM (1989). All relevant portions of the cited publications are incorporated by reference.
The number of packet descriptors dequeued at one time for a given channel by the scheduler, is related to the bandwidth of the channel. Assume there are M logical channels in a given network, and that each channel requires a service time of T
i
within which to dequeue the appropriate amount of descriptors from its descriptor queue. After serving channel j, a time period of
M−1
&Sgr;T
i
i=o
must lapse before information is again served into the buffer for the same channel j.
Let an interval V between each visit to a given channel to load new information into the channel's buffer, be defined as
M−1
V=&Sgr;T
i
i=o
To achieve satisfactory quality of service (QoS) features for real-time traffic (e.g., voice communications), the time interval V should be relatively small (e.g., about 6 msec). This is important for real-time information packets which must be transported always within acceptable delay periods. See N. F. Maxemchuk, et al., A Cooperative Packet Recovery Protocol for Multicast Video, IEEE International Conference on Network Protocols (October 1997); and N. F. Maxemchuk, et al., Measurement and Interpretation of Voice Traffic on the Internet, ICC '97, all relevant portions of which are incorporated by reference. Thus, the interval V may become too long and unacceptable if most of the packets to be transmitted are large, and QoS will suffer.
At high speeds, the implementation of packet service disciplines is costly. The known schemes have the following problems. First, they are open-loop in the sense that they establish an acceptable time period V, and visit each channel at least once every time period V. At each visit to a channel, a number of descriptors related to the bandwidth of the channel are dequeued from the corresponding descriptor queue. This procedure requires the system hardware to be fast enough to finish all necessary tasks for each channel in a time period of V/M. Hardware complexity is a function of the number of active channels, and implementation becomes more challenging as the number of logical channels increases. There are schemes that try to provide efficient and scalable architecture in a cost-effective manner. See, e.g., H. J. Chao, et al, “Design of Packet Fair Queuing Schedulers Using a Ram-Based Searching Engine, IEEE JSAC, v. 17, no. 6 (June 1999); S. Rathnavelu, “Adaptive Time Slot; a Scheduling Scheme for ATM End-Points”, IEEE Globe Comm 1996. See also U.S. Pat. No. 5,751,709 (May 12, 1998) and Pat. No. 5,712,851 (Jan. 27, 1998). A key difficulty with packet fair queuing (PFQ) algorithms is that they require buffering on a per-channel basis and non-trivial service arbitration among all channels. See D. C. Stephens, et al, “Implementing Scheduling Algorithms in High-speed Networks, IEEE JSAC v. 17, no. 6 (June 1999).
In general, two kinds of buffering schemes are known. In a fixed size buffering scheme, the use of buffers whose size is too small easily creates an underrun condition which results in channel starvation, and will cause overflow if packet sizes are large relative to the buffer's capacity. On the other hand, using large size buffers is costly if one wants only to accommodate a worst case condition, and large delays are introduced when implementing certain algorithms. In a variable size buffering scheme, dynamic storage allocation requires complicated management, and places further burdens on hardware design.
SUMMARY OF THE INVENTION
According to the invention, a method of transmitting streams of information over channels in an information network, includes associating a number of queues with corresponding channels of the network, enqueuing incoming descriptors representing information to be transmitted over a given channel in a queue associated with the channel, and dequeuing the descriptors from the queues by operation of a scheduler. A number of small and fixed size transmit buffers are associated with corresponding channels. A watermark threshold value corresponding to a minimum occupancy is defined for each of the transmit buffers. After the occupancy of a given transmit buffer falls below the threshold value for the buffer, a corresponding watermark event signal identifying the channel associated with the buffer is provided to the scheduler. Information represented by descriptors dequeued by the scheduler is delivered to the corresponding buffers, according to the order of the event signals provided to the scheduler.
For a better understanding of the invention, reference is made to the following description taken in conjunction with the accompanying drawing and the appended claims.
REFERENCES:
patent: 5872769 (1999-02-01), Caldara et al.
patent: 5982776 (1999-11-01), Manning et al.
patent: 6167029 (2000-12-01), Ramakrishnan
patent: 6405258 (2002-06-01), Erimli et al.
patent: 6611522 (2003-08-01), Zheng et al.
patent: 6614756 (2003-09-01), Morgenstern et al.
Tsquare, TS704—672 Channel HDLC Controller Data Book (Mar. 1999).
D.C. Stephens, et al, Implementing Scheduling Algorithms in High-Speed Networks, IEEE JASC (Jun. 1999) at 1145-58.
S. Rathnavelu, Adaptive Time Slot: A Scheduling Scheme for ATM End Points, IEEE GlobeCom (1996) at 2118-22.
H.J. Chao, et al, Design of Packet-Fair Queuing Schedulers Using a RAM-Based Searching Engine, IEEE JSAC (Jun. 1999) at 1105-26.
N.F. Maxemchuk, et al, Measurement & Interpretation of Voice Traffic on the Internet ICC'97.
N.F. Maxemchuk, et al, A Cooperative Packet Recovery Protocol for Multicast Video, IEEE Int. Conf. on Network Protocols (Oct. 1997) at 259-61.
A. Demers, et al, Analysis & Simulation of a Fair Queueing Algorithm, Proc. of ACM SIGCOMM (1989) at 1-12.
S.J. Golestani, A Self-Clocked Fair Queueing Scheme for B
Lo W. Steven
Rathnavelu Sunder R.
Lucent Technologies - Inc.
Ly Anh-Vu H
Pham Chi
LandOfFree
Packet transmission scheduling with threshold based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet transmission scheduling with threshold based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet transmission scheduling with threshold based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310361