Rate-controlled multi-class high-capacity packet switch

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.

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.

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 N2 products, and dividing each of the N2 products by the total unused capacity.

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.

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.

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.

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.