Combined and data compressed fifo based arbitration for a non-blocking switch

• US 20050099945A1
• Filed: 04/28/2003
• Published: 05/12/2005
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Holm, Ingemar, Schumacher, Norbert, Kohler, Helmut, Abel, Francois, Goldrian, Gottfried Andreas
• Granted Patent: US 7,379,470 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method and system for switching data packets through a multiple (m) input, multiple (n) output switching device providing a switching method having a fast one-cycle throughput. A respective switching device behaves like an output queued switch from a set of distributed output queues reading the incoming input control information from the plurality of input ports (IP) and compresses the information in a form which allows an easy association with a respective output port (OP) to which an individual input port is temporarily mapped.

Claims

1. A data packet switching method in which a buffer is used for buffering input control information about incoming packets at a plurality of m input ports to be switched to a plurality of n output ports of a respective switching device, the method being enabled for concurrent read operation from at least a subtotal of output ports, the method comprising the steps of:

a.) compressing said input control information from an indicator bit vector, an indicator bit representing either information data present or data absent on a respective one of said data input ports,

b.) storing respective subsets of said compressed control information according to an output port indication evaluated from packet header information into a respective buffer storage provided per output port,

c.) evaluating the compressed control information from the total of buffer storages for switching the respective data packet to the desired switching device output port.

2. The method according to claim 1, in which the compressing step comprises the steps of:

building an input port subgroup index for addressing respective subgroups of the total of input ports, each subgroup covering a predetermined plurality of input ports, and

providing subgroup indication means for each subgroup for tracking at which input ports of a subgroup data is concurrently present.

3. The method according to claim 2 in which said subgroup indication means is a bit sequence in which each bit indicates either data present or data not present for a respective input port forming part of a respective subgroup.

4. The method according claim 3 in which each bit of said bit sequence encodes or is derived from a respective input port number within a subgroup.

5. The method according to claim 2 in which each subgroup covers a number of 8 input ports.

6. The method according to claim 1, in which a plurality of buffer storages is provided for a respective plurality of priority lanes.

7. The method according to claim 1 in which said buffer storages are FIFO-operated.

8. The method according to claim 1, further comprising the step of bypassing a buffer storage when it does not hold data.

9. A chip circuit for use in a data packet switching method in which a buffer is used for buffering input control information about incoming packets at a plurality of m input ports to be switched to a plurality of n output ports of a respective switching device, the method being enabled for concurrent read operation from at least a subtotal of output ports, the method comprising the steps of:

a.) compressing said input control information from an indicator bit vector, an indicator bit representing either information data present or data absent on a respective one of said data input ports,

b.) storing respective subsets of said compressed control information according to an output port indication evaluated from packet header information into a respective buffer storage provided per output port,

c.) evaluating the compressed control information from the total of buffer storages for switching the respective data packet to the desired switching device output port.

10. The chip circuit performing the method according to claim 9, in which the compressing step comprises the steps of:

building an input port subgroup index for addressing respective subgroups of the total of input ports, each subgroup covering a predetermined plurality of input ports, and

providing subgroup indication means for each subgroup for tracking at which input ports of a subgroup data is concurrently present.

11. The chip circuit performing the method according to claim 10 in which said subgroup indication means is a bit sequence in which each bit indicates either data present or data not present for a respective input port forming part of a respective subgroup.

12. The chip circuit performing the method according claim 11 in which each bit of said bit sequence encodes or is derived from a respective input port number within a subgroup.

13. The chip circuit performing the method according to claim 12 in which each subgroup covers a number of 8 input ports.

14. The chip circuit performing the method according to claim 9, in which a plurality of buffer storages is provided for a respective plurality of priority lanes.

15. The chip circuit performing the method according to claim 9 in which said buffer storages are FIFO-operated.

16. The chip circuit performing the method according to claim 9, further comprising the step of bypassing a buffer storage when it does not hold data.

17. A chip circuit for use in a data packet switching method in which a buffer is used for buffering input control information about incoming packets at a plurality of m input ports to be switched to a plurality of n output ports of a respective switching device, the method being enabled for concurrent read operation from at least a subtotal of output ports, the chip circuit comprising:

a.) a compressing circuit compressing said input control information from an indicator bit vector, an indicator bit representing either information data present or data absent on a respective one of said data input ports,

b.) storing circuit storing respective subsets of said compressed control information according to an output port indication evaluated from packet header information into a respective buffer storage provided per output port,

c.) evaluating circuit evaluating the compressed control information from the total of buffer storages for switching the respective data packet to the desired switching device output port.

18. The chip circuit according to claim 17, in which the compressing circuit comprises:

an input port subgroup index circuit building an imput port subgroup index addressing respective subgroups of the total of input ports, each subgroup covering a predetermined plurality of input ports, and

a subgroup indication indicating each subgroup for tracking at which input ports of a subgroup data is concurrently present.

19. The chip circuit according to claim 17 in which said subgroup indication is a bit sequence in which each bit indicates either data present or data not present for a respective input port forming part of a respective subgroup.

20. The chip circuit according claim 19 in which each bit of said bit sequence encodes or is derived from a respective input port number within a subgroup.

21. The chip circuit according to claim 20 in which each subgroup covers a number of 8 input ports.

22. The chip circuit according to claim 21, in which a plurality of buffer storages is provided for a respective plurality of priority lanes.

23. The chip circuit according to claim 17 in which said buffer storages are FIFO-operated.

24. The chip circuit according to claim 17, further comprising a bypass bypassing a buffer storage when it does not hold data.

25. The chip circuit according to claim 17 in which said buffer storage is an SRAM memory device.

26. The chip circuit according to claim 17 further comprising a buffer storage per output port.

27. The chip circuit according to claim 17 further comprising a buffer storage per lane.