Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-11-18
2002-09-17
Ngo, Ricky (Department: 2731)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S468000
Reexamination Certificate
active
06452933
ABSTRACT:
FIELD OF THE INVENTION
The instant invention relates generally to packet-based communication systems and particularly to fair-queuing systems implemented in routers and switches in a packet-based communication system.
BACKGROUND OF THE INVENTION
Much research has been devoted to development of queuing systems for packet-based communication networks that emulates as closely as possible, an ideal “fluid flow” model, i.e., where data packets communicated from multiple sources are considered to be infinitely divisible and multiple sources may transmit their data simultaneously, e.g., on a single physical communication link. Infinite divisibility is not feasible in practice. In packet networks, typically once a packet is transmitted over the link, the whole packet must be sent, i.e., it cannot be interrupted to transfer another packet in between. As there exists a desire to provide Quality of Service “QoS” guarantees in a packet network, there is required the implementation of traffic scheduling methods in the data packet switches or routers. The function of a scheduling method is to select, for each outgoing link of a switch, the packet to be transmitted in the next cycle from the available packets belonging to the communication sessions sharing the output link. This selection must be performed such that the QoS guaranteed for the individual traffic sessions, e.g., upper bounds on maximum delay, are satisfied. Implementation of the method may be hardware or software, but because of speed considerations, scheduling is usually implemented in hardware in ATM switches and high-speed routers.
Many different scheduling methods have been proposed to approximate the theoretical scheduling discipline known as Generalized Processor Sharing (GPS) system, which is a discipline defined with respect to the “fluid” model. Such a GPS would allow for tight control of the bandwidth allocated to each session communicating on a link. However, as packets transmitted by a session cannot be divided further, the data from multiple sources must be interleaved only at packet boundaries. Thus, the GPS discipline cannot be implemented in practice in a packet-switched network.
Servicing of separate queues by simple FIFO, Round Robin, and fair queuing techniques, and the like, are well-known. However, “Weighted” fair-queuing (“WFQ”) schemes have been developed that closely approximate the fluid system. Particularly, A. Demers, S. Keshav, S. Shenker, in the reference “Analysis and Simulation of a Fair Queuing Algorithm”
Internetworking: Research and Experience,
pp, 3-26, vol. 1, 1990 describe a fair queuing scheme that emulates GPS by essentially simulating a fluid flow GPS system for reference and basing packet scheduling decisions on the order of departures in the GPS system. In weighted fair queuing, each traffic session i sharing the output link controlled by the scheduling method is assigned a value &phgr;
i
corresponding to the reserved bandwidth of the session. The values &phgr;
i
are computed such that the reserved bandwidth of session i on the link is given by:
φ
i
∑
j
=
1
v
φ
j
where the denominator computes the sum of the &phgr;
i
values for all &ugr; sessions sharing the link.
Particularly, as shown in
FIG. 1
, a WFQ system
100
is provided with a plurality of per-connection queues
20
a,
. . . ,
20
i,
with each queue storing packets in a different portion of a shared memory
25
for temporarily storing packets of information, e.g., input traffic from a source device such as a data terminal. It is understood that there can be provided different types of queues for accommodating different types of traffic, e.g., audio, video, data, etc. Additionally provided is a shaper
30
a,
. . . ,
30
i
that forward packets from the queues to the Weighted Fair Queueing Server with a rate exactly equal to the allocated. The Weighted Fair Queueing scheduler assumes that a weight is associated with each queue
20
a,
. . . ,
20
i,
respectively, so that the service offered by the scheduler to each one of these queues while they have packets waiting is always in proportion to the weights. For example, let us assume that the capacity (bandwidth) of the link C=10 packets/sec. Let us also assume that the scheduler is serving three queues; Q
1
being accorded a weight WQ
1
=20%, queque Q
2
being accorded a weight WQ
2
=30%, and queue Q
3
being accorded a weight WQ
3
=50%. Then, if all queues have packets waiting, then Q
1
and Q
2
will receive a guaranteed bandwidth of 2 and 3 packets/second respectively, and Q
3
will receive a guaranteed bandwidth of 5 packets/second. However, if, for example, Q
3
does not have any packets waiting, then the excess bandwidth is equal to 5 packets/second. In a WFQ system, this excess bandwidth is redistributed in proportion to the associated weights of the queues that have packets waiting. In the above example, when queue Q
3
does not have packets waiting, the excess bandwidth will be distributed proportionally to queues Q
1
and Q
2
so that they now receive instaneous bandwidth of 4 and 6 packets per second respectively. Each packet leaving its respective shaper
30
is forwarded directly to a Rate Proportional Server
40
(“RPS”), which may be any weighted fair queuing variation, that forwards the packets to output link
50
.
In such a WFQ scheme, beneficial properties exist such as end-to-end delay guarantees, e.g., each packet is guaranteed a certain rate for each packet flow in the stream, and, the provision of isolation between streams, e.g., a misbehaving source will not effect the flow of other streams. Additionally, an added benefit is that when there is underutilization of capacity, e.g., when flow is particularly bursty and there may be idle time, the WFQ system facilitates the redistribution of the unused bandwidth so as to preserve work-conservation property. Presently, the redistribution property of unused bandwidth capacity among the queues is done in a manner inherited from the fluid-flow model, e.g., in accordance with the weight associated with the particular queue. Thus, when the packet queues are idle, “excess” bandwidth is redistributed to backlogged connections in proportion to their weights which are based on long-term requirements.
The drawback of GPS that all fair queuing systems inherit in their close emulation of GPS is that GPS severely restricts state-dependent bandwidth sharing. The only state-dependency in GPS is in the number of backlogged connections. There is no further latitude and sharing is determined by the guaranteed rates which are set based on long term needs of the connections. This restriction on bandwidth sharing is more stringent than that necessary to preserve a key of property of fair queuing, the ability to guarantee worst case delay bounds for leaky bucket controlled traffic sources. Consequently, there is no need for fair queuing systems to emulate the possibly suboptimal excess bandwidth sharing of GPS.
It would thus be highly desirable to provide in a weighted fair queuing system emulating GPS, a method of achieving redistribution of unused bandwidth in a state-dependent manner, i.e., that reflects instantaneous needs of the remaining backlogged traffic flows.
SUMMARY OF THE INVENTION
The instant invention is a modified approach to weighted fair queuing implementing an adaptive redistribution scheme. In such a scheme, each per connection flow is guaranteed its specified share of the link bandwidth with any excess bandwidth being adaptively redistributed. The scheme enables preservation of fair queuing's ability to provide worst case end to end delay bounds and the schemes work like fair queuing when there is no excess bandwidth. The excess bandwidth may be distributed according to a different criteria. Examples of state dependent criteria are: 1) Longest delay first (LDF) that serves the flow with current longest delay; 2) Least time to overflow (LTO) that serves the flow with minimum difference between maximum allowed delay and current delay; 3) Least time to overfl
Duffield Nicholas G.
Lakshman Tirunell V.
Stiliadis Dimitrios
Hodulik M. J.
Ngo Ricky
LandOfFree
Fair queuing system with adaptive bandwidth redistribution does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair queuing system with adaptive bandwidth redistribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair queuing system with adaptive bandwidth redistribution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2873356