Switching systems and methods of operation of switching systems

• US 20020034183A1
• Filed: 11/13/2001
• Published: 03/21/2002
• Est. Priority Date: 05/01/1998
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Prabhakar, Balaji, McKeown, Nick
• Application Number:
  US09/991,302
• Publication Number:
  US 20020034183A1
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Architectures based on a non-blocking fabric, such as a crosspoint switch, are attractive for use in high-speed LAN switches, ATM switches and IP routers. These fabrics, coupled with memory bandwidth limitations, dictate that queues be placed at the input of the switch. But it is well known that input-queueing can lead to low throughput, and does not allow the control of latency through the switch. This is in contrast to output-queueing, which maximizes throughput, and permits the accurate control of packet latency through scheduling.

A switch is disclosed with virtual output queueing at the input and queueing at the output With a speedup of just four, and the use of a “most urgent packet first” method of operation, the switch can behave identically to an output-queued switch, regardless of the nature of the arriving traffic. The switch therefore performs as if it were output-queued, yet uses memory that runs more slowly.

Claims

1. A method of operation of a switching system, the switching system comprising:

a plurality of output stages each operable to supply packets of data to a respective output line;

a plurality of input stages each operable to receive packets of data on a respective input line, each received packet being destined for at least a respective one of the output stages; and

a transfer stage operable to transfer packets of data from any of the input stages to those of the output stages for which those packets are destined; and

the method of operation of the switching system comprising the steps of;

for each output stage, noting the temporal order in which the packets destined for that output stage are received by the input stages; and

controlling the transfer stage so that, for each output stage, the packets destined for that output stage are transferred from the input stages to that output stage in the noted order.

2. A method as claimed in claim 1, wherein:

the system operates according to time slots such that;

no more than one packet is received by each input stage during each time slot; and

no more than one packet is supplied by each output stage during each time slot; and

each time slot is divided into a plurality of phases such that;

no more than one packet is transferred from each input stage by the transfer stage during each phase; and

no more than one packet is transferred to each output stage by the transfer stage during each phase.

3. A method as claimed in claim 2, wherein each such time slot is divided into between two and four such phases.

4. A method as claimed in claim 2, wherein each such time slot is divided into four such phases.

5. A method as claimed in claim 2, wherein the controlling step includes the step, during each phase and for each output stage, of:

selecting that one of the input stages, if any, having that one of the packets which are destined for that output stage which is earliest in the noted temporal order; and

transferring that one packet from the selected input stage to that output stage unless there is input contention due to the selected input stage also having been selected for another of the output stages.

6. A method as claimed in claim 5, wherein the controlling step includes the step, if there is such input contention, of selecting that one of the output stages whose destined packet is earliest in the noted temporal order, unless there is none which is earliest.

7. A method as claimed in claim 6, wherein the controlling step includes the step, in the case of input contention, of repeating the controlling step for the or each output stage which is not selected in respect of the next earliest packet in the noted temporal order.

8. A method as claimed in claim 6, wherein the output stages have a predetermined ranking, and wherein the controlling step includes the step, if none of the packets is earliest as aforesaid, of selecting between the output stages in accordance with the predetermined ranking.

9. A method as claimed in claim 8, wherein the controlling step includes the step, in the case of input contention, of repeating the controlling step for the or each output stage which is not selected in respect of the next earliest packet in the noted temporal order.

10. A method as claimed in claim 1, wherein each input stage comprises a plurality of input buffers, one for each output stage, the method further including the step of placing each received packet in that one of the input buffers for the input line on which that packet is received and for the output stage for which that packet is destined.

11. A method as claimed in claim 1, wherein each output stage comprises a respective output buffer for the packets, and the packets are output from the respective output buffer to the respective output line in dependence upon the noted temporal order of the packets in the respective output buffer.

13. A system as claimed in claim 12, wherein each output stage comprises a respective output buffer for the packets, and the packets are supplied from that buffer to the respective output line in dependence upon the detected temporal order of the packets in the respective output buffer.

14. A system as claimed in claim 12, wherein each input stage comprises an input buffer for each output stage.

15. A system as claimed in claim 14, wherein the input buffers are first-in-first-out buffers.

12. A switching system comprising:

a plurality of output stages each operable to supply packets of data to a respective output line;

a plurality of input stages each operable to receive packets of data on a respective input line, each received packet being destined for at least a respective one of the output stages;

a transfer stage operable to transfer packets of data from any of the input stages to those of the output stages for which those packets are destined;

means for detecting, for each output stage, the temporal order in which the packets destined for that output stage are received by the input stages; and

means for controlling the transfer stage so that, for each output stage, the packets destined for that output stage are transferred from the input stages to that output stage in the detected temporal order.