Method and system for switching variable sized packets

• US 7,095,744 B2
• Filed: 05/30/2001
• Issued: 08/22/2006
• Est. Priority Date: 11/22/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Dune Networks, Inc. (Broadcom, Inc.)
• Inventors: Iny, Ofer
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US09/867,506
• Publication Number:
  US 20020061030A1
• Time in Patent Office: 1,910 Days
• Field of Search: 370/394, 370/395.6, 370/395.63, 370/395.64, 370/395.65, 370/466, 370/473, 370/474
• US Class Current: 370/395.6
• 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 system for switching variable size packets in a network comprising:

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 having a time-clock, all ingress controller'"'"'s time-clocks are synchronized to within a tolerance, each fragment is tagged with at least a unique source of ID, a time-stamp, and a fragment-number to form a cell, each cell belonging 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;

a fabric element which receives cells from a plurality of inputs links, where such cells are ordered, and sends ordered cells through a plurality of outputs, and through which the destination of the cells is reachable, where 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; and

at least one egress controller which receives ordered cells from the plurality of input links, and sends ordered cells through an output, where such order results in complete packets.

2. The system of claim 1 where the fabric element selects a cell for transmission if all incoming links FIFOs have at least one cell.

3. The system of claim 1 where the egress controller selects a cell for output if all incoming links FIFOs have at least one cell.

4. The system of claim 1 where the ingress controller sends an empty cell through output link if no data fragment is available, where such empty cells contain at least the current local timestamp, and source-id.

5. The system of claim 2 where the ingress controller sends an empty cell through output link if no data fragment is available, where such empty cells contain at least the current local timestamp, and source-id.

6. The system of claim 4, where when empty cells are received by a fabric element they are stored in the fabric element'"'"'s corresponding link input FIFO if that FIFO has less cells than a threshold.

7. The system of claim 5, where when empty cells are received by a fabric element they are stored in the fabric element'"'"'s corresponding link input FIFO if that FIFO has less cells than a threshold.

8. The system of claim 1 where the fabric element sends an empty cell through output link if no data fragment is available, where such empty cells contain at least the timestamp, source-id, and fragment-number of the last cell that was processed by the fabric element.

9. The system of claim 3 where the fabric element sends an empty cell through output link if no data fragment is available, where such empty cells contain at least the timestamp, source-id, and fragment-number of the last cell that was processed by the fabric element.

10. The system of claim 6, where when an empty cell is received by the egress controller it is stored in the fabric element'"'"'s corresponding link input FIFO if that FIFO has less cells then a threshold.

11. The system of claim 7, where when an empty cell is received by the egress controller it is stored in the fabric element'"'"'s corresponding link input FIFO if that FIFO has less cells then a threshold.

12. The system of claim 1, where the fabric element selects a cell for transmission if all active incoming links FIFOs have at least one cell, where active links are links through which a cell with at least a timestamp, source-id was received in a past period.

13. The system of claim 1, where the egress controller selects a cell for output if all active incoming links FIFOs have at least one cell, where active links are links through which a cell with at least a timestamp, source-id was received in a past period.

14. The system of claim 1, where ingress controller sends cells through a link such that cell'"'"'s destination is reachable through that link and such that all possible links are load balanced.

15. The system of claim 1, where fabric element sends cells through links through which a cell'"'"'s destination is reachable, and where all possible output links for such cell are load balanced.

16. The system of claim 14, where the ingress controller maintains a reachability table used to determine which links are possible for a destination.

17. The system of claim 15, where the fabric element maintains a reachability table used to determine which links are possible for a destination.