RRGS-round-robin greedy scheduling for input/output terabit switches
US6618379B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 8, 1998 |
| Grant date | Sep 9, 2003 |
| Priority date | — |
| Expiry date | Dec 8, 2018 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L49/3018
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A novel protocol for scheduling of packets in high-speed cell based switches is provided. The switch is assumed to use a logical cross-bar fabric with input buffers. The scheduler may be used in optical as well as electronic switches with terabit capacity. The proposed round-robin greedy scheduling (RRGS) achieves optimal scheduling at terabit throughput, using a pipeline technique. The pipeline approach avoids the need for internal speedup of the switching fabric to achieve high utilization. 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 a set of inputs and repeating the steps if the pair (i,j…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.