Packet transmission scheduling with threshold based backpressure mechanism

[0002] 1. Field of the Invention

[0003] This invention relates to a scheme for scheduling the transmission of streams of information over channels or links of an information network.

[0004] 2. Discussion of the Known Art

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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_iwithin which to dequeue the appropriate amount of descriptors from its descriptor queue. After serving channel j, a time period of

[0009] M−1

[0010] ΣT_i

[0011] i=o

[0012] must lapse before information is again served into the buffer for the same channel j.

[0013] Let an interval V between each visit to a given channel to load new information into the channel's buffer, be defined as

[0014] M−1

[0015] V=ΣT_i

[0016] i=o

[0017] 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.

[0018] 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).

[0019] 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.

[0020] 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.

[0021] 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.

[0022] In the drawing:

[0023] FIG. 1 is schematic block diagram of a packet scheduling arrangement for an information network according to the invention;

[0024] FIG. 2 is an example of a format for a watermark event signal produced in the arrangement of FIG. 1;

[0025] FIG. 3 illustrates high and low priority information packets loaded in a transmission buffer of prior packet scheduling systems;

[0026] FIG. 4 illustrates high and low priority packets loaded in a transmission buffer of the present scheduling arrangement; and

[0027] FIGS. 5A and 5B are flow diagrams illustrating a general operation of the packet scheduling arrangement of FIG. 1.

[0028] FIG. 1 shows an information packet scheduling arrangement 10 according to the invention. In the scheduling arrangement 10, a “closed loop” approach is taken wherein an information packet is delivered to a channel buffer only in response to a request associated with the channel. Specifically, a packet scheduler 12 is configured to respond to watermark event signals which may originate, for example, from a programmable communication controller 14 (e.g., type TS-704 available from T.sqware) which has been configured and programmed to control operations of components of the arrangement 10 and the timing of such operations, as described below. In a typical application, the controller 14 itself may be coupled to a PCI bus (not shown) over which address, control and data signals are transmitted from and delivered to the controller 14. Further, in the arrangement 10, a maximum size (e.g., 3000 bytes) is imposed for system packets, and the capacities of the channel buffers are also limited to accommodate, for example, not more than two or three full-size packets.

[0029] A packet request controller 16 which may be part of the controller 14, operates to supply the event signals to an input of a watermark event FIFO 18 (WmFIFO). The packet scheduler 12 is configured to detect and to respond to the event signals (packet requests) in the order the signals are output from the watermark event FIFO 18.

[0030] As seen in FIG. 1, the communication controller 14 maintains M transmit buffers 20 (TB₀to TB_M−1) for the same number of logical channels. For example, each buffer 20 may have a capacity of two full-size system packets (3000 bytes), and preferably not more than three full-size packets. A watermark level is associated with each of the buffers 20, and each of the buffer watermark levels W₀to W_M−1is user programmable via the controller 14. The watermark levels are measured in bytes rather than in numbers of packets, and the levels may be adjusted dynamically to achieve sub-optimal performance, if desired.

[0031] A number of descriptor queues 22 (DQ₀to DQ_M−1) are coupled to the packet scheduler 12. Each of the queues 22 is arranged to receive incoming packet descriptors representing information packets to be transmitted over a corresponding channel. Also, in the illustrated embodiment, each of the queues 22 has multiple internal queues, e.g., DQ₀₀and DQ₀₁. Incoming descriptors representing higher priority (e.g., real time) information are enqueued in a first internal queue (e.g., DQ_i0) of each descriptor queue 22, where i=0 to M−1. Descriptors representing lower priority information (e.g., ordinary data) are enqueued in a second internal queue (DQ_i1) of each queue 22. Each of the queues 22 may also have three or more internal queues, or be in the form of a single queue, depending on the application at hand. Information packets corresponding to dequeued descriptors are loaded for transmission into corresponding buffers 20 by operation of a packet buffer manager 24, which cooperates with the packet scheduler 12.

[0032] As mentioned, the maximum packet size is restricted, e.g., to 1500 bytes. The size of each transmit buffer 20 is then chosen to be small relative to the maximum packet size, for example, to a size of only two full packets (or 3000 bytes). As explained below, by limiting the maximum packet size and the capacity of the transmit buffers 20 accordingly, transmission disturbances within a channel that would otherwise be noticed when a small-size packet of real time (high priority) information is buffered behind large-size packets of low priority information, are greatly reduced or avoided.

[0033] When a number of bytes (not packets) awaiting transmission in a given transmit buffer 20 runs below the buffer's set watermark value W_i, a watermark event signal for the corresponding channel is provided from the packet request controller 16 to the watermark FIFO 18. A flow control procedure, discussed later below, avoids generation of multiple watermark events at any one time for the same logical channel.

[0034] Occupancy levels of the transmit buffers 20 are monitored in a round-robin fashion by the packet request controller 16. When the number of bytes in a given transmit buffer 20 falls below the watermark value Wi programmed for the buffer, and a partial almost full (WmFULL) flag of the watermark FIFO 18 is de-asserted, a watermark event signal is directed into the WmFIFO 18 by operation of the packet request controller 16. As shown in FIG. 2, the event signal format may include, e.g., a 13-bit logical channel number (LCN), identifying the transmission channel whose buffer has signaled that the number of bytes remaining for transmission has fallen below the set watermark level. Upper bits of the event word in FIG. 2 may be reserved for other or future use.

[0035] The WmFULL signal associated with the FIFO 18, is programmed or set to be triggered at a threshold that will assure that sufficient space will remain in the FIFO 18 to accommodate all possible outstanding watermark event signals associated with the transmit buffers 20, without danger of overflow. The WmFULL signal is detected by the controller 14, and the controller has an associated watermark event signal queue 26 which is, e.g., four words deep. Since there may also be four outstanding event transfers, setting the WmFULL flag to a threshold of at least eight words or more should be sufficient. Further, if a maximum number of outstanding event requests that can be handled by the controller 14 is known (e.g., 512 outstanding requests for the type TS-704), a threshold of at least the same number of words may be chosen for activation of the WmFULL flag.

[0036] The scheduler 12 may maintain and monitor an event empty (WmEE) flag associated with the watermark FIFO 18. The scheduler is backpressured (i.e., idle) if WmEE is asserted. If WmEE is not asserted, events are emptied from the FIFO 18 one by one in the order they were entered, to the packet scheduler 12. As mentioned, the event signals output from the FIFO 18 are requests for packets whose descriptors are dequeued from the queues 22. Importantly, when an event signal identifying a given channel is received by the scheduler 12, and the descriptor queue associated with the channel has multiple internal queues, those descriptors contained in a high priority queue (e.g., queue DQ₀₀in FIG. 1) are dequeued ahead of descriptors contained in a low priority queue (e.g., DQ₀₁) for the given channel. Information packets corresponding to the dequeued descriptors are then fetched and placed in the transmit buffer 20 for the given channel. Even though the threshold value is set in bytes, the scheduler will transfer in terms of complete packets which can vary individually in size.

[0037] When comparing buffer occupancy with the watermark threshold value for a given transmit buffer 20, a coarser granularity of more than one byte for the threshold value may be used. For example, a granularity of 64 bytes may perform satisfactory, while easing the software implementation for the communication controller 14. As mentioned, the watermark threshold value is measured in bytes, rather than packets. This avoids an underrun of the transmit buffers 20 as might occur when a channel is allocated with a high bandwidth, and arriving packets are small in size. In such a case, the transmit buffer for the channel will be drained rapidly, and an insufficient number of requests for additional packets will be generated. Setting the threshold too low will result in an inefficient use of the transmit channel. If the threshold is set too high, the QoS will suffer. In the latter case, it is possible that many low priority packets are already queued, and then a new high priority packet arrives. The high priority packet will then be transmitted only after the lower priority packets, thus adversely affecting the QoS.

[0038] As noted earlier, a flow control is necessary to avoid generating multiple watermark event signals corresponding to the same channel. The following mechanism ensures that a new watermark event is generated only when the previous request has been fulfilled. In other words, there is at most one outstanding watermark event per channel at any time. One control bit may be assigned to each channel to manage the event flow, and the control bits all set to “0” initially. The control bit for each channel is set to “1” when a watermark event is generated. It is then reset to “0” each time a packet is fetched and stored in the corresponding buffer 20. The following is an example of a flow control procedure with pseudo codes, and assuming 256 channels per controller 14. FIGS. 5A and 5B are flow diagrams showing operations of the controller 14 and the scheduler 12.

[0039] while(TRUE) {

[0040] For i=0 to 255

[0041] {

[0042] if (control[i]=‘0’) then

[0043] if (WmFULL=‘0’) then

[0044] if (number_of_bytes[i]<watermark_leve[i]) then generate a watermark event with channel# i;

[0045] control[i]=‘1’;

[0046] i=i+1;

[0047] end if;

[0048] end if;

[0049] else

[0050] i=i+1;

[0051] end if;

[0052] };

[0053] }

[0054] With the above flow control procedure, there can be at most one outstanding request per logical channel. Thus, the size of the watermark FIFO 18 may be small since the FIFO will not contain more than M requests, where M is the number of logical channels supported by the arrangement 10. Accordingly, the controller 14 need not monitor the WmFULL flag of the watermark FIFO 18 since the latter will never overflow.

[0055] The backpressure mechanism embodied in the arrangement 10 uses a combination a small and fixed-size transmit buffer 20 for each logical channel, and an adjustable watermark threshold value for each channel buffer. The size of the transmit buffers is chosen not too small as to cause underrun or to overflow easily, and not too large as to minimize the frequency or rate at which a given channel is served with new information packets. As explained further below, quality of service (QoS) is also provided for those channels that support more than one class of service if each transmit buffer 20 is small and of a fixed-size.

[0056] To understand the significance of using a small and fixed-size transmit buffer to provide (QoS) among different classes of traffic within a logical channel, assume, for example, that a given channel i supports two classes of service, viz., high priority and low priority traffic. That is, N=2 wherein N is the number of internal queues in the descriptor queue for the channel. See FIG. 1. Assume also that the maximum packet size is fixed, and that high priority packets always preempt low priority packets in the descriptor queues. Thus, when a request associated with channel i is received by the scheduler 12, the scheduler will operate always to look at the high priority queue first if that queue is not empty.

[0057] FIG. 3 shows a scenario where the size of a transmit buffer can accommodate six or more full-size packets, and FIG. 4 illustrates a case where the size of a transmit buffer 20 can hold only two full-size packets. FIG. 3 shows that due to the large size of the transmit buffer, a late arrived information packet PKT_H is placed behind five low priority packets PKT_L. Thus, the high priority packet PKT_H suffers a queuing delay equal to the transmission time of five PKT_Ls ahead of the high priority packet. By using a small size transmit buffer, as in FIG. 4, high priority packet PKT_H needs to wait only for the transmission time of one low priority PKT_L, since the packet scheduler 12 cannot deliver more than two information packets to buffer TB_iat one time. A service guarantee for the high priority packets is therefore possible if the size of the transmit buffers 20 is kept sufficiently small.

[0058] Restricting the maximum packet size to, e.g., 1500 bytes also helps the delay performance of small-size real time packets (i.e., high priority traffic) which may follow right after a large size data packet (low priority) within the same channel transmit buffer. In a worst case example, in a channel allocated with a bandwidth of 64 Kbps, if a small real time packet is buffered behind a 1500 byte data packet, the former will have a wait time of not more than 187.5 msec in the buffer before transmission.

[0059] While the foregoing description represents a preferred embodiment of the invention, it will be obvious go those skilled in the art that various changes and modifications may be made, without departing from the spirit and scope of the invention pointed out by the following claims.