Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-08
2003-09-09
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S458000
Reexamination Certificate
active
06618379
ABSTRACT:
I. DESCRIPTION OF THE INVENTION
IA. Field of the Invention
This invention relates to terrabit switches for use in applications like electronic and optical media. Specifically, this invention relates to a round robin greedy scheduling algorithm. This invention is embodied in methods for scheduling and a terrabit switching system that implements the round robin greedy scheduling algorithm.
IB. Background of the Invention
With the growing demand for bandwidth there is an increasing need for terabit switching. see M. Beshai, and E. Miinter, “Multi-tera-bit/s switch based on burst transfer and independent shared buffers,”
ICC'
95, pp. 1724-1730, N. McKeown et al., “The tiny tera: a packet switch core,”
IEEE Micro,
vol. 171, January-February 1997, pp. 26-33, and W. D. Zhong, Y. Shimazu, M. Tsukuda, and K. Yukimatsu, “A modular Tbit/s TDM-WDM photonic ATM switch using optical buffers,”
IEICE Transactions on Communications,
vol. E77-B, no. 2, February 1994, pp. 190-196. Optical switching core (which can be viewed as a logical cross bar switch) with electronic control is an attractive candidate for high capacity switches. At a line rate of 10 Gb/s, a 64 byte cell/packet has to be processed within 40 ns.
An important issue faced by practitioners in the field is how to make fast scheduling decisions that will use the optical core efficiently. Switch design in such a case may involve input buffering, output buffering or both. In a switch with output buffering, the output buffers require access speed greater than the total switch throughput. Alternatively, a knockout architecture is employed in order to decrease the required output buffer speed, where a limited number of cells are accepted by the output buffer and the rest are dropped. An optical knockout switch has been proposed in, Zhong, Y. Shimazu, M. Tsukuda, and K. Yukimatsu, “A modular Tbit/s TDM-WDM photonic ATM switch using optical buffers,”
IEICE Transactions on Communications,
vol. E77-B, no. 2, February 1994, pp. 190-196. The complexity of optical knockout switching is high since each output requires several optical reverse Banyan networks and optical buffers.
Switches with input buffering use buffers more efficiently, and need memory bandwidth of only twice the line rate. In a simple scheme with input buffering, all inputs make requests to transmit packets that are at the head of their queues. If two or more inputs make requests for the same output, one of them is chosen randomly. It was shown in, see M. J. Karol, M. G. Hluchyj, and S. P. Morgan, “Input vs. output queuing on a space-division packet switch,”
IEEE Transactions on Communications,
vol. COM-35, no. 12, December 1987, pp. 1347-1356 that input buffering algorithm leads to a throughput of 0.587 under uniform traffic condition. The efficiency further decreases in the case of non-uniform traffic. In several other scheduling schemes, packets other than the HOL (head of line) packets contend for output ports. See R. Fan, M. Akiyama, and Y. Tanaka, “An input buffer-type ATM switching using schedule comparison,”
Electronics and Communications in Japan:
Part I, vol. 74, no. 11, 1991, pp.17-25; S. Motoyama, D. W. Petr, and V. S. Frost, “Input-queued switch based on a scheduling algorithm,”
Electronics Letters,
vol. 31, no. 14, July 1995, pp. 1127-1128; and H. Obara, “Optimum architecture for input queuing ATM switches,”
Electronics Letters,
vol. 27, no. 7, March 1991, pp. 555-557. During each time slot, an input issues requests to several outputs. With just 4 requests per time slot, an efficiency approaching 1 is achieved. However, in such a scheme at high speeds multiple request/acknowledgements for scheduling cannot be processed within one time slot (where a slot represents a packet transmission time). Also, for the non-uniform traffic with hot-spots, the performance may degrade since inputs independently decide which outputs they are going to request.
The switch performance can be improved if the switch controller knows the states of all input-output queues. Such information enables the switch controller to increase the number of simultaneous transmissions in each time slot. In the SLIP protocol, the outputs independently issue grants to the inputs, which leads to some inefficiency. see N. McKeown, P. Varaiya, J. Walrand, Scheduling cells in an input-queued switch,”
Electronic Letters,
vol. 29, no. 25, December 1993, pp. 2174-2175. Better coordination between inputs is achieved by the algorithms discussed in, see D. Guo, Y. Yemini, Z. Zhang, “Scalable high-speed protocols for WDM optical star networks,”
IEEE INFOCOM'
94. However, these algorithms have a disadvantage that they require many time slots to make scheduling decisions.
II. SUMMARY OF THE INVENTION
It is an objective of the present invention to solve the above-mentioned problems in the conventional technologies. Specifically it is an objective of the present invention to provide a method for making scheduling decisions in a terabit switch that will efficiently use the optical core. It is a further objective of the present invention to provide a pipeline architecture that performs a round-robin greedy scheduling while providing good performance and fulfilling stringent timing requirements without internal speedups.
In order to meet the above objectives there is provided a method for determining a time slot in a N×N crossbar switch for a round robin greedy scheduling protocol, comprising N logical queues corresponding to N output ports, the input for the protocol being a state of all the input-output queues, output of the protocol being a schedule, the method comprising: choosing input corresponding to i=(constant−k−1) mod N, stopping if there are no more inputs, otherwise choosing the next input in a round robin fashion determined by i=(i+1)mod N; choosing an output j such that a pair (i,j) to a set C={(i,j)| there is at least one packet from I to j}, if the pair (i,j) exists removing i from the set of inputs and j from a set of outputs; and adding the pair (i,j) to the schedule and repeating the steps; removing i from a set of inputs and repeating the steps if the pair (i,j) does not exist; Another aspect of this invention is a method of scheduling wherein in each time slot N distinct schedules are in progress simultaneously for N distant future time slots, the method comprising; making a specific future time slot available to input for scheduling in a round-robin fashion; selecting an output for a kth time slot in future, by an input i; starting a schedule for the kth time slot in future; determining a next input (I+1) mod N and sending to the next input remaining outputs that are free to receive packets during the kth time slot.
Preferably if an input i is the last input to complete a schedule for the kth time slot, it selects an output (if feasible) and sends a modified output set to a next input; and if the input I completes a schedule for the kth time slot it does not send the output set to the next input.
Still preferably an input that does not receive a modified set of outputs from a previous input starts a new schedule.
Another aspect of the present invention is a method of pipelined round robin greedy scheduling for odd number of inputs wherein an i th time slot is completed using a process comprising: Initializing k(0,1)=k(1,1)= . . . k(N−1,1)=0, const=N+1, wherein, k(i,I)>0 is the time slot for which input i reserves an output in Ith time slot, i
I
=(const−N−1) mod N denotes an input that starts a new schedule in Ith time slot, and k(i,I)=0 implies that the action of input i in time slot I is suppressed; setting O
I+N={O,
1, . . . ,N−1}, k(I
I
,I)=I+N, k(i,I)=k((i−1)mod N,I−1) for 0≦i≦N−1 and i≠i
i
, choosing one output j at input i, 0
≦
i
≦
N−1, in a round-robin fashion from the set O
k
(i,1) for which it has a packet to send, provided that k(i,I)≠0 and
Fan Ruixue
Ramamurthy Gopalakrishnan
Smiljanić Aleksandra
NEC Corporation
Sughrue & Mion, PLLC
Yao Kwang Bin
LandOfFree
RRGS-round-robin greedy scheduling for input/output terabit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with RRGS-round-robin greedy scheduling for input/output terabit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and RRGS-round-robin greedy scheduling for input/output terabit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056794