Rate-controlled multi-class high-capacity packet switch

• US 6,721,271 B1
• Filed: 02/04/1999
• Issued: 04/13/2004
• Est. Priority Date: 02/04/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Munter, Ernst A., Beshai, Maged E.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/244,824
• Time in Patent Office: 1,895 Days
• Field of Search: 370/232, 370/235-236, 370/395.4, 370/395.42, 370/395.43, 370/411, 370/413, 370/412, 370/374, 370/395.41, 370/503, 370/509, 370/514, 370/358, 370/392, 370/389, 370/399, 370/401, 370/409, 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 high-capacity switch for transferring variable-sized packets under rate control is described. The packets are divided in the switch into segments of predetermined equal size. The packets are reconstructed before egress from the switch. The switch serves traffic of different classes of service, but the class of service distinction is relevant only at the ingress or egress modules. The switch control is preferably centralized to facilitate effective sharing of the inner capacity of the switch. The control is based on modulating the ingress/egress rate according to traffic load, the central control being unaware of the class of service disposition of the traffic it controls. The advantage is a high capacity switch adapted to transfer variable-sized packets with guaranteed rate control.

Claims

1. A method of switching data packet traffic belonging to multiple classes of service through a switching node in a data network, comprising steps of:

sorting the data packet traffic at each ingress module into traffic streams according to egress module from which the respective data packets must egress from the switching node and class of service;

determining an aggregate committed transfer rate to each traffic stream;

computing an aggregate committed transfer rate for each of the traffic streams destined to a same egress module;

determining traffic loads by counting the number of packet segments in each of the traffic streams;

communicating the aggregate committed transfer rate and the traffic loads to a capacity transfer allocation mechanism; and

distributing at the transfer allocation mechanism any switching core capacity that exceeds the aggregate committed transfer rate among ingress/egress pairs based on excess traffic loads.

2. The method as claimed in claim 1 wherein the number of classes of service may be specified for each ingress module.

3. The method as claimed in claim 1 wherein the traffic streams comprise cells of fixed size.

4. The method as claimed in claim 1 wherein the traffic streams comprise fixed-size segments of variable-sized packets.

5. A switching node for switching data packets, comprising:

a plurality of ingress modules each including a segmentation mechanism for deconstructing the packets into segments of a predetermined length at ingress and storing the segments in buffers in accordance with a traffic class of service property;

at least two egress modules;

a switch core for selectively connecting, in a manner transparent to traffic class of service, the ingress modules to the at least two egress modules to enable packets to be transferred therebetween;

a selector for selecting which of the buffered segments stored in a given one of the ingress modules to transfer to the switch core according to the traffic class of service property; and

a packet assembly mechanism for reconstructing each packet at egress so that each packet is transferred from the switch in a format in which it was received at the ingress module.

6. The packet switch as claimed in claim 5 wherein the switch core comprises a space-switched core.

7. The packet switch as claimed in claim 5 wherein the switch core comprises a bank of memories interposed between two rotators.

8. A switching node for switching data packets, comprising:

N ingress modules and M egress modules, N and M being integers greater than one;

a switching core interposed between the ingress modules and the egress modules;

an ingress/egress transfer allocation mechanism which periodically receives data related to data packet traffic transferred from each of the respective N ingress modules; and

an ingress/egress scheduling mechanism which uses data generated by the ingress/egress transfer allocation mechanism to generate a transfer schedule for each of the respective N ingress modules;

wherein the transfer schedules are periodically communicated to the respective ingress modules.

9. A switching node as claimed in claim 8 wherein the transfer schedule is generated from an ingress/egress transfer allocation matrix and a transfer schedule time frame used for generating the transfer schedule is of arbitrary length.

10. A switching node as claimed in claim 8 wherein the transfer allocation mechanism operates to allocate a capacity of the switching core so that the ingress and egress modules dynamically share an available capacity of the switching core.

11. A switching node as claimed in claim 8 wherein the switching node has a rotator-based switch architecture and the transfer allocation mechanism sends transfer rate allocations directly to each of the N ingress modules, and the respective ingress modules perform distributed spatial matching to achieve local scheduling for the transfer of packet segments to the switching core.

12. The switching node as claimed in claim 8 wherein the ingress/egress transfer allocation mechanism distributes, among the ingress/egress pairs having traffic waiting to be transferred across the switching core, unused capacity in the switching node.

13. A method of distributing unused core capacity in a packet switch having N ingress modules and N egress modules, comprising the steps of:

storing the unused ingress capacity in N elements of an array X;

storing the unused egress capacity in N elements of an array Y;

determining a total unused capacity by summing the N elements of a one of the array X or array Y; and

computing a transfer allocation of the total unused capacity for each ingress/egress pair by multiplying the respective unused ingress capacities by the respective unused egress capacities to obtain N² products, and dividing each of the N² products by the total unused capacity.

14. The method as claimed in claim 13 wherein prior to computing a transfer allocation, either of the multiplicand arrays, X or Y, is modified by dividing each of its elements by the total unused capacity and the transfer allocation for an ingress/egress pair is computed by multiplying the respective elements in array X by the elements in array Y.

15. A method as claimed in claim 14 wherein each element in the modified multiplicand array is left-shifted by an integer B bits before the division and the result of pair-wise multiplication of elements of the modified array and the other array is right-shifted B bits, the integer B being an integer greater than 8.

16. The method as claimed in claim 15 wherein multiplication processes are carried out in parallel.

17. A method of capacity sharing in a packet switch having a plurality of ingress modules and a plurality of egress modules interconnected by a switch core, the method comprising the steps of:

(a) sending from each ingress module a committed-capacity matrix to a transfer allocation mechanism, each element in the matrix containing the committed capacity of each ingress module with respect to each of the egress modules;

(b) sending from each ingress module to the transfer allocation mechanism an array storing a number of traffic units waiting to be transferred from the ingress module to each of the egress modules;

(c) creating at the transfer allocation mechanism a base matrix, each entry in the base matrix being a lesser of corresponding entries in the matrix containing the committed capacity and the matrix containing the traffic units;

(d) subtracting entries in the base matrix from corresponding entries in the traffic matrix to create a standby traffic matrix;

(e) computing an unused capacity for each ingress module and each egress module;

(f) simultaneously processing the N entries in a diagonal set of the standby traffic matrix;

(g) for each ingress/egress pair belonging to a diagonal set, determining an additional ingress/egress transfer allocation on the basis of the least one of an unused capacity of an ingress module of the ingress/egress pair, an unused capacity of an egress module of the ingress/egress pair, and a corresponding ingress/egress entry in the standby traffic matrix;

(h) if the additional ingress/egress transfer allocation is greater than zero, subtracting its value from the unused capacity entry at ingress, the unused capacity entry at egress, and the ingress/egress entry in the excess traffic matrix;

(i) repeating steps (f) to (h) until all diagonals are processed;

(j) repeating steps (a) to (i) each transfer allocation period; and

(k) selecting a different order of diagonal processing each transfer allocation period.

18. In a node for switching packet segments comprising N ingress modules, N egress modules, N core memories, each core memory being logically partitioned into N sections, each section corresponding to a one of the egress modules, and each section capable of string m data parcels, a transfer allocation mechanism which determines the number of parcels eligible for transfer from each ingress module to each egress during a scheduling cycle, a parcel scheduler comprising:

a bank of N egress-state memories, each egress-state memory being logically divided into N sections, each section being adapted to store a number representative of a number of parcels that can be accommodated in a corresponding section in the core memory;

a bank of N transfer allocation memories, each transfer allocation memory having N entries, each entry corresponding to an ingress/egress module pair and adapted to store any number representative of an eligible parcel transfer allocation for the ingress/egress pair;

an N×

N rotator to cyclically pair the transfer allocation memories and the egress-state memories;

a bank of N matching circuits, each circuit determining a lesser of a value stored in a transfer allocation memory and a value stored in a corresponding entry in the egress-state memory;

a bank of N result memories, each result memory corresponding to an ingress module and adapted to store a sequence of egress module numbers, each egress module number representing a parcel eligible for transfer to the egress module;

means for subtracting one from the entries of the egress-state memories and the transfer allocation memories for each egress module number in the result memories; and

means for transferring the contents of each result memory to its corresponding ingress module.

19. The scheduling apparatus as claimed in claim 18 wherein pairing of the core-image and transfer allocation memories is performed in accordance with different patterns in consecutive scheduling cycles.

20. The method as claimed in claim 18 wherein the process of comparing the transfer allocation memories and the egress-state memories, comprises the steps of:

matching simultaneously corresponding elements in the transfer allocation memories and the egress-state memories to select up to m packet parcels for transfer; and

selecting on a round-robin basis a total of up to m packet parcels from the parcels selected for transfer to a corresponding egress module during an egress interval.

21. In a node for switching packet segments comprising N ingress modules, N egress modules, a space switch interconnecting the N ingress modules and the N egress modules, a transfer allocation mechanism which determines the number of parcels eligible for transfer from each ingress module to each egress during a scheduling cycle, a parcel scheduler comprising:

a bank of N egress-state memories, each egress-state memory being logically divided into an array of N 1-bit entries, each entry being representative of the availability of an egress module to accept a parcel;

a bank of N transfer allocation memories, each transfer allocation memory having N entries, each entry corresponding to an ingress/egress module pair and adapted to store any number representative of an eligible parcel transfer allocation for the ingress/egress pair;

an N×

N rotator to cyclically pair the transfer allocation memories and the egress-state memories;

a bank of N matching circuits, each circuit determining a lesser of a value stored in a transfer allocation memory and a value stored in a corresponding entry in the egress-state memory;

a bank of N result memories, each result memory corresponding to an ingress module and adapted to store a sequence of egress module numbers, each egress module number representing a parcel eligible for transfer to the egress module;

means for subtracting one from the entries of the egress-state memories and the transfer allocation memories for each egress module number in the result memories; and

means for transferring the contents of each result memory to its corresponding ingress module.

22. A method of aggregating segments of digital data in an ingress module of a data packet switch into parcels, each parcel containing at least one and at most a predetermined integer number of the segments, each segment including a unique identifier associated with the ingress module, comprising the steps of:

sorting the segments into logical buffers in a payload memory of the ingress module using an identifier associated with an egress module from which the respective segments must egress from the switch, and a delay tolerance identifier to determine a sort order for the segments;

increasing by 1 a count of a number of waiting segments in each respective buffer each time a new segment is added to a one of the buffers, the count being maintained in a waiting segment count array;

declaring the new segment a critical segment if a respective count of the number of segments in a logical buffer is equal to the predetermined maximum number of segments in a parcel;

initializing a respective entry in a timer array if the new segment is a critical segment;

logically transferring segments from the payload memory to a ready queue associated with each egress module when a waiting segment count is greater than the predetermined number, or a respective entry in the waiting segment count array is greater than zero and a corresponding entry in the timer array exceeds a predetermined time limit associated with the logical buffer and increasing a ready-queue counter and decreasing a respective entry in the waiting segment count array accordingly;

transferring segments from the ready queue in parcels to a next stage of the data packet switch each parcel being padded with null data if the number of waiting segments in the ready-queue is greater than zero but less than the predetermined number and decreasing the ready-queue counter by the number of segments in the parcel after each parcel is transferred out of the ready queue.

23. The segment aggregation method as claimed in claim 22 wherein every entry in the waiting segment count array and every entry in the timer array is examined within a time interval sufficient to transfer a parcel from the ready-queue.

24. The segment aggregation method as claimed in claim 22 wherein the number of delay tolerance identifiers may vary frorn one ingress module to another ingress module.