Method for scheduling transmissions in a buffered switch

Details Method for scheduling transmissions in a buffered switch Method for scheduling transmissions in a buffered switch

1998-08-10

2002-03-19

Hsu, Alpus H. (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S397000, C370S413000

Reexamination Certificate

active

06359861

ABSTRACT:

BACKGROUND OF THE INVENTION
Switches and routers have traditionally employed output-queuing. When packets or cells arrive at an input port, they are immediately transferred by a high-speed switching fabric to the correct output port and stored in output queues. Various queue management policies which have been considered, such as virtual clock algorithms, deficit round robin, weighted fair queuing or generalized processor sharing, and many variations, have attempted to control precisely the time of departure of packets belonging to different virtual circuits (VCs) or flows or sessions, thus providing various quality-of-service (QoS) features such as delay, bandwidth and fairness guarantees.
However, for these pure output-queuing schemes to work, the speed of the switching fabric and output buffer memory must be N times faster than the input line speed where N is the number of input lines, or the sum of the line speeds if they are not equal. This is because all input lines could have incoming data arriving at the same time, all needing to be transferred to the same output port. As line speeds increase to the Gb/s range and as routers have more input ports, the required fabric speed becomes infeasible unless very expensive technologies are used.
To overcome this problem, switches with input-queuing have been used in which incoming data are first stored in queues at the input ports. The decision of which packets to transfer across the fabric is made by a scheduling algorithm. A relatively slower fabric transfers some of the packets or cells to the output ports, where they might be transmitted immediately, or queued again for further resource management. The present invention only considers the problem from the viewpoint of designing a fabric fast enough to manage input queues, regardless of whether there are also output queues.
The ratio of the fabric speed to the input speed is called the “speedup.” An output-queued switch essentially has a speedup of N (whereupon input queues become unnecessary), whereas an input-queued switch typically has a much lower speedup, as low as the minimum value of one, i.e., no speedup. The main advantage of input queuing with low speedup is that the slower fabric speed makes such a switch more feasible and scalable, in terms of current technology and cost. The main disadvantage is that packets are temporarily delayed in the input queues, especially by other packets in the same queues destined for different outputs. In contrast, with output-queuing a packet is never affected by other packets destined for different outputs. This additional input-side queuing delay must be understood or quantified in order for an input-queued switch to provide comparable QoS guarantees as an output-queued switch.
One problem with input-queued switches is that if the next cell to be transmitted—that is, the cell at the head of the queue—is blocked because its destination port is busy, or perhaps because it has a low priority, all other cells queued up behind it are also blocked. This is known as head-of-line blocking. This problem is commonly resolved by allowing per-output queuing, in which each input has not one but M queues corresponding to M outputs. Thus the unavailability of one output does not affect the scheduling of cells bound for other outputs.
Graph theory concepts have been used to develop algorithms in attempts to efficiently select input/output pairs for transmission across the switch fabric. Inputs are treated as one set of nodes, outputs as the second set of nodes, and the paths between input/output pairs having data to transmit, are treated as the edges of the graph. A subset of edges such that each node is associated with only one edge is called a matching.
L. Tassiulas, A. Ephremides, “Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multihop radio networks,”
IEEE Trans. \Automatic Control
, vol.37, no.12, December 1992, pp.1936-1948, presented a scheduling algorithm using queue lengths as edge weights and choosing a matching with the maximum total weight at each timeslot. The expected queue lengths are bounded, i.e., they do not exceed some bound, assuming of course that no input or output port is overbooked. That is, this is true even if the traffic pattern is non-uniform, and even if any or all ports are loaded arbitrarily close to 100%. Hence, this “maximum weighted matching” algorithm, using queue lengths as weights, achieves 100% throughput. For an overview of the maximum weighted matching problem, see e.g., Ahuja, et al,
Network flows: theory, algorithms, and applications
. Published: Englewood Cliffs, N.J., Prentice Hall, 1993.
No speedup is required for this result. However, a main drawback preventing the practical application of this theoretical result is that maximum weighted matching algorithms are complex and slow, and are therefore not suitable for implementation in high-speed switches. Most algorithms have O(N
3
) or comparable complexity, and large overhead.
To overcome this problem, faster algorithms have recently been proved to achieve the same result of bounding expected queue lengths, and though not necessarily prior art, are presented here for a description of the present state of the art. For example, Mekkittikul and McKeown, “A Practical Scheduling Algorithm to Achieve 100% Throughput in Input-Queued Switches,”
IEEE INFOCOM
98, San Francisco, April 1998, uses maximum weighted matchings. However the weights are “port occupancies” defined by w(e
ij
)=sum of queue lengths of all VCs at input port i and all VCs destined to output port j. By using these edge weights, a faster, on the order of N
2.5
(O(N
2.5
)), complexity algorithm can be used to find maximum weighted matchings.
L. Tassiulas, “Linear complexity algorithms for maximum throughput in radio networks and input queued switches,”
IEEE INFOCOM
98, San Francisco, April 1998 goes one step further and shows that, with the original queue lengths as edge weights, expected queue lengths are bounded by a large class of randomized algorithms. Moreover, some of these algorithms have O(N
2
) complexity or “linear complexity”, i.e., linear in the number of edges.
Mekkittikul and McKeown, “A Starvation-free Algorithm for Achieving 100% Throughput in an Input-Queued Switch,” ICCCN 1996 also uses a maximum weighted matching algorithm on edge weights which are waiting times of the oldest cell in each queue. As a result, the expected waiting times, or cell delays, are bounded. This implies queue lengths are bounded, and hence is a stronger result.
All of these results are based on Lyapunov stability analysis, and consequently, all of the theoretically established bounds are very loose. While the algorithm of Tassiulas and Ephremides, and McKeown, Anantharam and Walrand, “Achieving 100% Throughput in an Input-Queued Switch.” Proc.
IEEE INFOCOM
, San Francisco, March 1996, exhibits relatively small bounds in simulations, the sample randomized algorithm given in L. Tassiulas, “Linear complexity algorithms for maximum throughput in radio networks and input queued switches,”
IEEE INFOCOM
98, San Francisco, April 1998, which is the only “linear-complexity” algorithm above, still exhibits very large bounds in simulations. To the best of our knowledge, no linear-complexity algorithm has been shown to have small bounds in simulations and also provide some kind of theoretical guarantee.
Several new works have appeared recently dealing with QoS guarantees with speedup. The earliest of these, Prabhakar and McKeown, “On the speedup required for combined input and output queued switching,” Computer Science Lab Technical Report, Stanford University, 1997, provides an algorithm that, with a speedup of four or more, allows an input-queued switch to exactly emulate an output-queued switch with FIFO queues. In other words, given any cell arrival pattern, the output patterns in the two switches are identical. Stoica, Zhang, “Exact Emulation of an Output Queuing Switch by a Combined Input Output Queuing Switch,” IWQoS 1998, and Chuang

Affiliated with

Also associated with

Rating

Method for scheduling transmissions in a buffered switch does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for scheduling transmissions in a buffered switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for scheduling transmissions in a buffered switch will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2832191