Rate-controlled multi-class high-capacity packet switch

• US 6,876,629 B2
• Filed: 12/19/2003
• Issued: 04/05/2005
• Est. Priority Date: 02/04/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Uortel Networks Limited
• Inventors: Munter, Ernst A., Beshai, Maged E.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US10/741,375
• Publication Number:
  US 20040141494A1
• Time in Patent Office: 473 Days
• Field of Search: 370/232, 370/358, 370/235, 370/236, 370/395.4, 370/395.42, 370/395.43, 370/411, 370/413, 370/412, 370/374, 370/503, 370/392, 709/229
• US Class Current: 370/232
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/205 Quality of Service based
• 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

Abstract

A packet switch includes ingress modules, egress modules, and a switch core. Packets of variable sizes may be divided into segments of predetermined sizes to facilitate switching within the switch core. The segmentation process may require null-padding which increases the flow rate within the switch. The segments are transferred from ingress to egress under flow-rate control based on inflating specified flow rates. Null padding is removed at egress. Ingress modules sort segments or packets according to their destination egress modules and egress modules sort segments or packets according to their ingress-module origin. Thus, segments of the same packet, and packets of the same stream, are properly concatenated as they appear in a logical buffer at egress. To enable growth of the packet switch to accommodate a very large number of ingress and egress modules, the switch implements a method of fast matching to schedule packet transfer across the switch core.

Claims

1. A method of switching data units from a plurality of ingress modules to a plurality of egress modules through a switching fabric, the method comprising steps of:

sorting said data units at each ingress module into ingress queues each of said ingress queues corresponding to an egress module;

switching said data units to respective egress modules;

sorting data units at each egress module into egress queues each of said egress queues corresponding to an ingress module; and

reassembling data units at each egress queue of said each egress module into data packets without reordering said data units.

2. The method of claim 1, wherein said data units are segments of data packets, each of said data packets destined to one of said egress modules and containing an arbitrary integer number of data segments.

3. The method of claim 2, wherein said data segments of said each of said data packets are switched to said one of said egress modules during time slots of arbitrary temporal separation.

4. The method of claim 1, wherein at least one of said data units contains null data.

5. The method of claim 1, wherein said data units have equal sizes.

6. The method of claim 1, further including a step of associating a label with each data unit, the label comprising:

a first field providing an identifier of a sort order at ingress;

a second field indicating whether a data unit is the last in a data packet; and

a third field containing data segments.

7. The method of claim 6, wherein the third field is padded with null data when a respective segment is shorter than the length of the third field.

8. The method of claim 7, wherein when the second field indicates that the segment is a null-padded last segment in the data packet, a number of bits from the third field is used to indicate a length of the segment in the third field, said number being not less than the base-2 logarithm of the length in bytes of the third field.

9. The method of claim 8, wherein said null data is removed before said transmitting from said each egress module.

10. A packet switch comprising:

a plurality of ingress modules each operable to receive data packets and divide said packets into data segments;

a plurality of egress modules; and

a switch core operable to selectively switch said data segments to said egress modules;

wherein

at least one of said ingress modules sorts said segments into ingress queues each ingress queue corresponding to a destination egress module; and

at least one of said egress modules sorts data segments it receives through said switch core into egress queues each egress queue corresponding to an ingress-module origin.

11. The packet switch of claim 10, wherein each of said egress modules is further operable to assemble data segments into reconstructed data packets without reordering said data segments.

12. The packet switch of claim 11, wherein at least one of said data segments includes null data.

13. The packet switch of claim 12, wherein said at least one of said egress modules is operable to remove said null data from each of said at least one of said data segments prior to assembling said reconstructed data packets.

14. The packet switch of claim 10, wherein said at least one of said ingress modules is further operable to identify a last segment of each of said data packets.

15. A method of switching packets of variable size comprising the steps of:

dividing each packet at ingress into a number of segments each having a length upper bound;

null-padding each segment that is shorter than said upper bound;

prefixing each segment with a header;

transferring said data segments through a switch fabric; and

reconstructing each packet by removing the headers and any null padding;

wherein the segments are transferred from an ingress module to an egress module under rate regulation based on a specified transfer rate inflated by a factor determined according to null-data content.

16. The method of claim 15, wherein said factor is specific to each pair of ingress and egress modules.

17. The method of claim 16, wherein said factor is determined dynamically according to a ratio of size aggregation of received packets to size aggregation of segmented packets.

18. The method of claim 17, wherein said ratio at least equals (1+1/(2P)) where P is the mean number of segments per packet.

19. The method of claim 17, wherein said ratio is determined at predetermined time intervals.

20. The method of claim 15, wherein said header identifies an ingress module that received said each packet.

21. The method of claim 15, including a further step of sorting the segments at ingress according to designated egress modules.

22. The method of claim 15, including a further step of sorting the segments received at each egress module according to their labels.

23. The method of claim 15, wherein said specified transfer rate from each ingress module to each egress module is explicitly determined by an admission-control mechanism.

24. The method of claim 15, wherein said specified transfer rate from each ingress module to each egress module is determined adaptively according to ingress-buffer occupancy.

25. A method of fast matching of corresponding entries in at least two arrays each having the same number of entries, the method comprising steps of:

dividing the at least two arrays into sets of corresponding sub-arrays each set comprising a sub-array of each of said at least two arrays;

dividing said sets into groups of sets;

concurrently processing all sets to determine matching entries for each set;

concurrently accumulating said matching entries for each of said groups to determine a matching outcome for each of said groups; and

accumulating the matching outcome for all groups to determine all matching entries.

26. The method of claim 25, wherein said processing includes a step of determining the least value of corresponding entries within each set.

27. The method of claim 26, wherein said matching entries include null entries.

28. The method of claim 26, wherein the step of accumulating the matching outcome for all groups is terminated when the matching outcome reaches a predetermined limit.

29. An apparatus for fast matching comprising:

a plurality of sets of memory devices;

a plurality of matching circuits each associated with one of said sets of memory devices;

a plurality of transit data registers;

a plurality of group selectors each connecting at input to a group of said matching circuits and at output to one of said transit data registers; and

an output selector connecting at input to said transit data registers and at output to a result register;

wherein

each of said group selectors cyclically transfers outputs of respective matching circuits to the transit register to which it is connected; and

said output selector cyclically transfers data from said transit registers to said result register.

30. The apparatus of claim 29, wherein each of the matching circuits compares data read from corresponding addresses in the set of memory devices associated with said each of said matching circuits.