Method and system for switching packets

• US 7,525,995 B2
• Filed: 04/06/2005
• Issued: 04/28/2009
• Est. Priority Date: 11/22/2000
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Dune Networks, Inc. (Broadcom, Inc.)
• Inventors: Iny, Ofer
• Primary Examiner(s): Backer; Firmin
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US11/099,582
• Publication Number:
  US 20050174940A1
• Time in Patent Office: 1,483 Days
• Field of Search: 370/386, 370/389, 370/392, 370/394, 370/465, 370/473, 370/474, 370/388
• US Class Current: 370/474
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing

Abstract

A system for switching variable size packets in a network is disclosed. The system comprises at least one ingress controller which receives a plurality of packets and which segments each of the packets into fixed sized fragments. The at least one ingress controller has a time-clock. The time clocks of all ingress controllers are synchronized to within a tolerance. Each fragment is tagged with at least a unique source of ID, time-stamp, and a fragment-number to form a cell. Each cell belongs to one packet having the same time-stamp value. The ingress controller sends each of the cells through a link such that a cell'"'"'s destination is reachable through that link. The system includes a fabric element which receives cells from a plurality of inputs links. The cells are ordered. The fabric element sends ordered cells through a plurality of outputs and through which the destination of the cells is reachable. The cell order is defined such that a cell ahead of another either has a lagging time stamp, or if the timestamp is the same the cell ahead of another has a source-id which has a predetermined priority, or if both the timestamp and the source-id are the same the cell ahead of another has a lagging fragment-number. The system finally includes at least one egress controller which receives the ordered cells from the plurality of input links, and sends the ordered cells through an output where such order results in complete packets. A packet switching device in accordance with the present invention solves the cell ordering and packet reassembly issues using a unified distributed method in a multi-stage interconnect network.

Claims

1. A method of switching, via a plurality of links of an interconnect network, a plurality of packets, which are received by a plurality of ingress controllers, to a plurality of output ports of a plurality of egress controllers, the method comprising:

segmenting said plurality of packets into a plurality of packet fragments;

generating a plurality of cells, each including one of said packet fragments, a global time stamp, an ingress identification, a destination identification, and a fragment number; and

sending said plurality of cells to said plurality of output ports via said links based on a prioritization scheme which is based on said global time stamp, said ingress identification, and said fragment number,

wherein sending said plurality of cells based on said prioritization scheme comprises;

prioritizing a first cell over a second cell having a lagging time stamp compared to a time stamp of said first cell;

prioritizing said first cell over a third cell having the same time stamp as said first cell and an ingress identification of lower priority compared to an ingress identification of said first cell; and

prioritizing said first cell over a fourth cell having the same time stamp and ingress identification as said first cell and having a lagging fragment number compared to a fragment number of said first cell.

2. The method of claim 1 comprising transferring an empty cell from an ingress controller to a link if said ingress controller has no cell including a packet fragment to transfer to said link, said empty cell including at least a global time stamp corresponding to a global time at which said empty cell is transferred to said link, and an ingress identification corresponding to an identification of said ingress controller.

3. The method of claim 1 comprising transferring an empty cell from a fabric element of said network to a link if said fabric element has no cell including a packet fragment to transfer to said link, said empty cell including at least a global time stamp, an ingress identification and a fragment number of a cell previously received by said fabric element.

4. The method of claim 1 comprising transferring a cell from a fabric element of said network only after receiving cells from all input links of said fabric element.

5. The method of claim 4 comprising storing cells received from one or more of said input links according to a first-in-first out scheme.

6. The method of claim 1 comprising transferring a cell to an output port of an egress controller only after receiving cells from all input links of said egress controller.

7. The method of claim 6 comprising storing cells received from one or more of said input links according to a first-in-first out scheme.

8. The method of claim 1 comprising synchronizing, within a predetermined tolerance, the generation of time stamps by said plurality of ingress controllers.

9. The method of claim 1, wherein all cells corresponding to a certain packet have a time stamp corresponding to a global time at which a first cell of said certain packet is transferred to said network.

10. The method of claim 1, wherein at least one cell of said cells includes a flag indicating whether said cell is an empty cell.

11. The method of claim 1, wherein segmenting said plurality of packets comprises segmenting said plurality of packets into a plurality of fixed size fragments.

12. The method of claim 1, comprising maintaining reachability data to determine one or more possible links for reaching a destination port.

13. A system for switching a plurality of packets to a plurality of destinations via links of a network, the system comprising:

a plurality of ingress controllers to receive said plurality of packets, to segment said plurality of packets into a plurality of packet fragments, and to generate a plurality of cells each including one of said packet fragments, a global time stamp, an ingress identification, a destination identification, and a fragment number;

a plurality of egress controllers including a plurality of output ports; and

an interconnect network including a plurality of fabric elements to transfer said cells from said ingress controllers to said egress controllers via a plurality of links,

wherein said cells are sent to said plurality of output ports via said links based on a prioritization scheme which is based on said global time stamp, said ingress identification, and said fragment number, and

wherein at least one of said egress controllers and said plurality of fabric elements is able to;

prioritize a first cell over a second cell having a lagging time stamp compared to a time stamp of said first cell;

prioritize said first cell over a third cell having the same time stamp as said first cell and an ingress identification of lower priority compared to an ingress identification of said first cell; and

prioritize said first cell over a fourth cell having the same time stamp and ingress identification as said first cell and having a lagging fragment number compared to a fragment number of said first cell.

14. The system of claim 13, wherein at least one fabric element is able to transfer an empty cell to a link if said fabric element has no cell including a packet fragment to transfer to said link, said empty cell including at least a global time stamp, an ingress identification and a fragment number of a cell previously received by said fabric element.

15. The system of claim 13, wherein at least one fabric element is able to transfer a cell only after receiving cells from all input links of said fabric element.

16. The system of claim 15, wherein said fabric element comprises a first-in-first-out storage scheme to store cells received from one or more of said input links.

17. The system of claim 13, wherein at least one egress controller is able to transfer a cell to an output port of said egress controller only after receiving cells from all input links of said egress controller.

18. The system of claim 17, wherein said egress controller comprises a first-in-first-out storage scheme to store cells received from one or more of said input links.

19. The system of claim 13, wherein at least one ingress controller is able to transfer an empty cell to a link if said ingress controller has no cell including a packet fragment to transfer to said link, said empty cell including at least a global time stamp corresponding to a global time at which said empty cell is transferred to said link, and an ingress identification corresponding to an identification of said ingress controller.

20. The system of claim 13 comprising a global clock scheme to synchronize, within a predetermined tolerance, the generation of time stamps by said plurality of ingress controllers.

21. The system of claim 13, wherein at least one ingress controller is able to generate all cells corresponding to a certain packet having a time stamp corresponding to a global time at which a first cell of said certain packet is transferred to said network.

22. The system of claim 13, wherein at least one ingress controller is able to generate at least one cell including a flag indicating whether said cell is an empty cell.

23. The system of claim 13, wherein said plurality of ingress controllers are able to segment said plurality of packets into a plurality of fixed size fragments.

24. The system of claim 13 comprising at least one reachability table to maintain reachability data to determine one or more possible links for reaching a destination port.