Method of transmitting information through data switching apparatus and apparatus therefor

• US 7,088,710 B1
• Filed: 11/10/1999
• Issued: 08/08/2006
• Est. Priority Date: 12/22/1998
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Inventors: Johnson, Ian David, Howarth, Paul, Collins, Michael Patrick Robert
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): SCHEIBEL, ROBERT C
• Application Number:
  US09/869,091
• Time in Patent Office: 2,463 Days
• Field of Search: 370/414, 370/357
• US Class Current: 370/357
• CPC Class Codes: H04L 12/64 Hybrid switching systems
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/153 ATM switching fabrics having parallel switch planes
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/506 Backpressure
• CPC Class Codes: H04L 49/606 Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A data switch for handling packets of information; the switch includes input traffic managers, ingress routers, a memoryless cyclic switch fabric, egress routers and output traffic managers all acting under the control of a switch controller. Each ingress router includes a set of virtual output buffers one for each output traffic manager and each message priority. Each data packet or cell as it arrives is examined to identify the output traffic manager address and its message priority. The switch controller uses a first arbitration and selection process to schedule the passage of the next cell across the switch fabric which the ingress router uses a second arbitration and selection process to select the appropriate virtual output queue for use in the switch fabric transfer.

Claims

1. A method of transmitting information through a data switching apparatus connected to a plurality of input line end devices and output line end devices, said input line end devices transmitting protocol information packets to a data switch for transmission to specific output line end devices,

the data switching apparatus comprising a plurality of input traffic manager units a plurality of output traffic manager units and a data switch, the data switch comprising a plurality of input routers, a plurality of output routers, and a memory-less cyclic switch fabric, and a switch controller, said switch fabric being controlled by said switch controller, said input traffic manager units being connected to one or more of said input line end devices, and said output traffic manager units being connected to one or more of said output line end devices,

each input traffic manager unit being arranged to convert protocol information packets it receives from the respective input line end devices into fixed length cells having a header, said header indicating the output traffic manager unit connected to the output line end device to which the cell should be sent,

each input router being arranged to receive cells from a respective group of said input traffic manager units, and to maintain virtual output queues for each output traffic manager unit;

each output router being arranged to transmit cells to a respective group of said output traffic manager units

the method comprising the steps of;

(a) on the arrival of a cell from an input traffic manager unit, examining the cell header at the input router, placing it in a virtual output queue for the output traffic manager unit indicated by the cell header, generating a transfer request including the address of the output traffic manager unit indicated by the header of that cell, and passing said transfer request to the switch controller,

wherein the or each of the cell headers includes message priority information, the or each of the transfer requests includes a priority code; and

the switch fabric is controlled by the switch controller to connect ones of said input routers to ones of said output routers;

(b) scheduling the passage of the or each of the cells across the switch fabric at the switch controller at each switch style, by using a first arbitration process to select which of said input routers to connect to which of said output routers, and controlling the switch fabric to connect the selected input routers to the corresponding selected output routers;

(c) upon it being determined that a given input router is to be connected to a given output router, performing a second arbitration process at that given input router to select a single virtual output queue, from among the virtual output queues for the output traffic manager units to which the given output router sends cells, and transmitting the cell at the head of the selected virtual output queue across the switch fabric to the given output router; and

transmitting the cell by the given output router to the output traffic manager indicated by the cell header.

2. The method according to claim 1, wherein each input router maintains a virtual output queue for each output traffic manager unit and priority level, and upon receipt of a cell the input router places the cell in the virtual output queue for the priority and output traffic manager unit indicated by the cell header.

3. The method according to claim 1, wherein each output router maintains an output queue for each of the output traffic manager units to which it transmits cells.

4. The method according to claim 1, wherein each input router maintains an input buffer for each of the input traffic manager units from which it receives signals.

5. The method according to claim 1, wherein said second arbitration process performed by the given input router is weighted round-robin arbitration process based upon:

the length of said output virtual queues of the given input router;

an aggregate queue packet urgency; and

a backpressure from said output traffic manager.

6. The method according to claim 1, wherein the first arbitration process selects which input routers and output routers to connect, to maximize the number of said transfer requests which can be satisfied.

7. A data switching apparatus for connection to a plurality of input line end devices and output line end devices to transmit protocol information packets received from said input line end devices to specific output line end devices,

the data switching apparatus comprising a plurality of input traffic manager units, a plurality of output traffic manager units and a data switch, the data switch comprising a plurality of input routers, a plurality of output routers, an memory-less cyclic switch fabric, and a switch controller, said switch fabric being controlled by said switch controller, each of said input traffic manager units being for connection to one of more of said input line end devices, and each of said output traffic manager units being for connection to one or more of said output line end devices,

each of the input traffic manager units being arranged to convert protocol information packets it receives from the respective input line end devices into fixed length cells having a cell header including message priority information, said cell header indicating the output traffic manager unit connected to the output line end device to which the cell should be sent,

each of the input routers being arranged to receive cells from a respective group of said input traffic manager units, to maintain a set of virtual output queues for each output traffic manager unit, and, on the arrival of a cell from an input traffic manager unit, to examine the associated cell header, to place it in a virtual output queue for the output traffic manager unit indicated by the associated cell header, to generate a transfer request including the address of the output traffic manager unit indicated by the header of that cell, and to pass said transfer request to the switch controller,

each output router being connected to a respective group of said output traffic manager units;

wherein each output router is arranged, upon receipt of a cell having a header which indicates one of that group of output traffic manager units, to transmit the received cell to that indicated output traffic manager unit;

said input routers are arranged to include a priority code in said transfer requests;

the switch fabric is arranged, under the control of the switch controller, to connect ones of said input routers to ones of said output routers;

the switch controller is arranged to schedule the passage of cells across the switch fabric at each switch cycle, by using a first arbitration process to select which of said input routers to connect to which of said output routers, and control the switch fabric to connect the selected input routers to the corresponding selected output routers; and

each input router is arranged, upon it being determined that that input router is to be connected to a given output router, to perform a second arbitration process to select a single virtual output queue from among the virtual output queues for the output traffic manager units to which the given output router is connected, and to transmit the cell at the head of the selected virtual output queue across the switch fabric to the given output router.

8. The data switching apparatus according to claim 7, wherein each input router, is arranged to maintain a virtual output queue for each output traffic manager unit and priority level, and the input router is arranged to place a received cell in the virtual output queue for the priority and output traffic manager unit indicated by the cell header.

9. The data switching apparatus according to claim 7, wherein each output router is arranged to maintain an output queue for each of the group of output traffic manager units to which it can send cell.

10. The data switching apparatus according to claim 7, wherein each input router is arranged to maintain an input buffer for each of the input traffic manager units from which it receives signals.

11. The data switching apparatus according to claim 7, wherein said second arbitration process is a weighted round-robin arbitration process based upon:

the length of said output virtual queues of the given input router;

an aggregate queue packet urgency; and

a backpressure from said output traffic manager units.

12. The data switching apparatus according to claim 7, wherein the first arbitration process selects which input routers and output routers to connect, to maximize the number of said transfer requests which can be satisfied.