Method and apparatus for a flexible access rate common-memory packet switch

• US 6,118,792 A
• Filed: 11/21/1997
• Issued: 09/12/2000
• Est. Priority Date: 11/21/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Beshai, Maged E.
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/976,423
• Time in Patent Office: 1,026 Days
• Field of Search: 370/230, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/448, 370/357, 370/358, 370/359, 370/360, 370/369, 370/370, 370/235, 370/422 , 370/252
• US Class Current: 370/468
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics

Abstract

A method of controlling asymmetrical port access in a common-memory (CM) multi-port data packet switch and a high-capacity flexible access rate CM data packet switch are described. The method involves providing a common-memory-access control table which defines a unique contiguous band of CM access time slots allocated to each port of the packet switch. Each access time slot is identified by a time slot identifier. Time slot identifiers are generated at a regular interval. The time slot identifiers are generated so that CM access time for each port is substantially equally spaced to minimize delay jitter. The packet switch may have an equal number of input and output ports, or more output ports than input ports. In the high-capacity CM packet switch, several CM switch modules are interlinked by middle buffers in a folded configuration to provide a packet switch having Terabit output capacity. The advantage is a packet switch architecture which supports flexible access rates to eliminate idle switch capacity, the CM access time slots being substantially equally spaced apart to reduce packet transfer delay jitter.

Claims

1. A method of controlling port access to the common-memory of a common-memory multi-port data packet switch, comprising:

defining a control cycle consisting of a fixed number of discrete common-memory access time slots;

allocating a proportional number of the access time slots to each port based on a predetermined access capacity requirement for the port; and

distributing access time slots for each port in the control cycle in such a way as to reduce packet transfer delay and jitter.

2. A method of controlling asymmetrical port access in a common-memory multi-port data packet switch, comprising:

a) at least during each execution of an initialization process for the data packet switch, inspecting a common-memory-access control table to determine a lower bound and an upper bound of a unique contiguous band of common-memory access time slots allocated to each port and passing the lower bound and the upper bound to a controller for each port;

b) continuously maintaining a cyclic count having a maximum value equal to the number of access time slots allocated in the control table; and

c) applying a scatter transform to the count each time it is incremented to obtain a scattered transform result, whereby each port controller is enabled to access the common-memory when the transform result is greater than or equal to the lower bound and less than the upper bound passed to the port controller.

3. A method of controlling asymmetrical port access in a common-memory multi-port data packet switch as claimed in claim 2 wherein the access time slot allocations in the common-memory-access control table are computed by a common-memory-access control algorithm.

4. A method of controlling asymmetrical port access in a common-memory multi-port data packet switch as claimed in claim 3 wherein the common-memory-access control algorithm periodically computes the access time slot allocations for a control table based on short term predicted network traffic load.

5. A method of controlling asymmetrical port access in a common-memory multi-port data packet switch as claimed in claim 4 wherein the common-memory-access control algorithm computes a new control table every Nth control cycle, wherein N is an integer greater than, or equal to, 1.

6. A method of controlling asymmetrical port access in a common-memory multi-port data packet switch as claimed in claim 2 wherein the scatter transform comprises a reverse conversion of a binary representation of the count, the least significant bit of the binary representation becoming the most significant bit of the result.

7. A flexible access rate common-memory packet switch, comprising:

a plurality of input ports and output ports;

a common-memory for switching packets between the input ports and the output ports;

means for storing an allocation of common-memory access time slots for each port, the allocation being based on a predetermined access capacity requirement for the port; and

means for distributing the access time slots for each port in a control cycle of all access time slots allocated in such a way that each port accesses the common-memory in a cyclic sequence of substantially equally spaced access time slot intervals.

8. A flexible access rate common-memory packet switch, comprising:

a common-memory switch module having an ingress side and an egress side;

a plurality of input ports connected to the ingress side of the common-memory switch module;

a plurality of output ports connected to the egress side of the common-memory switch module;

a smoothing buffer associated with each of the input and output ports;

a common-memory-access control table for defining a unique contiguous band of discrete access time slot allocations for access to the common-memory by each of the input and output ports;

means for sequentially generating time slot identifiers so that access to the common-memory switch module is enabled for each port in a substantially evenly spaced relationship; and

means for enabling a specific port to access the common-memory switch module when a time slot identifier indicates a time slot within the contiguous band allocated to that port.

9. A flexible access rate common-memory packet switch as claimed in claim 8 wherein the smoothing buffer is a short buffer having a capacity of less than 5 packets.

10. A flexible access rate common-memory packet switch as claimed in claim 8 wherein the means for sequentially generating a time slot identifier comprises:

a counter for continuously maintaining a count, the counter being of a finite word length having a range corresponding to the total number of access time slots allocated in the common-memory-access control table; and

a scatter transform for converting the count to the time slot identifier.

11. A flexible access rate common-memory packet switch as claimed in claim 10 wherein the scatter transform for converting the count to the time slot identifier comprises means for reversing a binary representation of the count so that the least significant bit becomes the most significant bit of the time slot identifier.

12. A flexible access rate common-memory packet switch as claimed in claim 8 wherein the common-memory packet switch further comprises a common-memory-access control table algorithm for generating the access time slot allocations in the common-memory-access control table.

13. A flexible access rate common-memory packet switch as claimed in claim 12 wherein the common-memory-access control table algorithm periodically generates common-memory-access control table access-time-slot allocations based on a predictive algorithm of traffic load at the respective input and output ports of the packet switch and the smoothing buffers at the input ports are replaced by long buffers which can accommodate a plurality of packets.

14. A flexible access rate common-memory packet switch as claimed in claim 8 wherein the common-memory packet switch is a multicast switch.

15. A flexible access rate common-memory packet switch as claimed in claim 14 wherein the multicast switch has more output ports than input ports.

16. A flexible access rate common-memory packet switch as claimed in claim 8 wherein the common-memory packet switch is a unicast switch but the ports are respectively allocated contiguous bands of time slots proportioned to accommodate a committed access capacity for each port.