Asynchronous transfer mode packet switch

• US 5,636,210 A
• Filed: 08/02/1995
• Issued: 06/03/1997
• Est. Priority Date: 08/02/1995
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Jagannath P. Agrawal
• Inventors: Agrawal, Jagannath P.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US08/510,594
• Time in Patent Office: 671 Days
• Field of Search: 370/60, 370/60.1, 370/61, 370/58.1, 370/58.2, 370/58.3, 370/53, 370/54, 370/94.1
• US Class Current: 370/390
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/1561 Distribute and route fabrics, e.g. Batcher-Banyan
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/455 Provisions for supporting expansion in ATM switches

Abstract

An asynchronous transfer mode packet switch for use in a Broadband Integrated Services Digital Network is disclosed. The asynchronous transfer mode packet switch is highly modular and allows expansion of the switch to handle applications having less than eight input and output devices to applications having up to 2¹⁴ input and output devices. The preferred asynchronous transfer mode packet switch is constructed as either a single-stage switch for routing data packets between up to 2⁶ input and output devices, a two-stage switch for routing packets between up to 2¹⁰ input and output devices, or a three-stage switch for routing packets between up to 2¹⁴ input and output devices.

Claims

1. An asynchronous transfer mode packet switch for routing packets between a plurality of communication devices, said packet switch comprising:

a plurality of input ports for receiving packets from a plurality of communication devices;

a plurality of output ports for delivering the received packets to a plurality of communication devices; and

routing means for routing the packets from said input ports to said output ports, said routing means including

a quantity of buffer groups equal to the quantity of said input ports for receiving and storing the packets from said input ports before delivery to said output ports, each of said buffer groups including a plurality of buffers for preventing packet blocking and packet loss within said routing means;

a buffer management module for allocating said buffers to the packets.

2. The packet switch as set forth in claim 1, said buffer management module including means for allocating said buffer groups and said buffers to said received data packets in sequential order for sharing said buffers among all of said output ports.

3. The packet switch as set forth in claim 1, including means for delivering a single broadcast packet to a plurality of output ports.

4. The packet switch as set forth in claim 3, said buffer management module including means for allocating a broadcast packet to a single memory buffer, means for determining the number of output ports the broadcast packet is destined for, means for counting the number of times the memory buffer storing the broadcast packet is read by the output ports, and means for releasing the memory buffer for another packet only after the memory buffer has been read by all the designated output ports.

5. The packet switch as set forth in claim 1 further including a plurality of read sequencers, each of said read sequencers being associated with a corresponding one of said output ports for receiving from said buffer management module a memory buffer address for indicating that a packet destined for its respective output port has been stored in that memory buffer.

6. The packet switch as set forth in claim 5, said read sequencers each including means for receiving a plurality of different memory buffer addresses from said buffer management module and for selecting the highest priority packet to be read next by its respective output port.

7. The packet switch as set forth in claim 6, said read sequencers each including means for sorting the plurality of different memory buffer addresses according to their priority for facilitating the selecting of the highest priority packet.

8. The packet switch as set forth in claim 1, said routing means further including a buffer switching module for routing packets from said buffers to said output ports.

9. The packet switch as set forth in claim 1, said routing means further including an input processing module for delaying packets received from said input ports for a predetermined amount of time before delivery to said buffer groups to allow said buffer management module time to allocate the packets among said buffer groups.

10. The packet switch as set forth in claim 9, said buffer management module including means for generating and delivering to said input processing module routing tags for routing the packets to the appropriate buffer groups.

11. The packet switch as set forth in claim 10, said input processing module including means for attaching said routing tags to the packets for routing the packets to the appropriate buffer groups.

12. An asynchronous transfer mode packet switch for routing packets from a plurality of input communication devices to a plurality of output communication devices, said packet switch comprising:

a plurality of input ports for receiving packets from a plurality of input communication devices;

a plurality of output ports for delivering the received packets to a plurality of communication devices;

a switch assembly for routing the packets from said input ports to said output ports, said switch assembly including

a plurality of input group modules, each of said input group modules being coupled with a plurality of said input ports for receiving packets therefrom, said input group modules including a number of transfer paths for routing said packets, and

a plurality of output group modules coupled with said input group modules for receiving packets routed over said transfer paths and for routing the packets to said output ports,

each of said input group modules including means for separating the packets into unicast packets destined for a single output port, multicast packets destined for a plurality of output ports less than a pre-determined number, and broadcast packets destined for a plurality of output ports greater than a pre-determined number.

13. The packet switch as set forth in claim 12, said input group modules including means for copying each of said multicast packets to create a plurality of unicast packets for delivery to a plurality of single output ports.

14. The packet switch as set forth in claim 13, said input group modules including means for broadcasting each of said broadcast packets to all of said output ports.

15. The packet switch as set forth in claim 12, each of said input group modules including a sorter for sorting said unicast packets into groups of packets destined for each of said output group modules and for sorting said groups according to their priorities.

16. The packet switch as set forth in claim 15, each of said input group modules further including a trap network coupled with said sorter for selecting the highest priority packets for routing over said transfer paths.

17. The packet switch as set forth in claim 16, each of said input group modules further including a concentrator coupled with said trap network for concentrating the highest priority packets for routing over said transfer paths and for recirculating the lower priority packets to said sorter.

18. The packet switch as set forth in claim 17, each of said input group modules further including a plurality of routers for routing the concentrated highest priority packets to said output group modules over said transfer paths.

19. The packet switch as set forth in claim 12, each of said output group modules including

a plurality of buffer groups for receiving and storing packets from said input group modules before delivery to said output ports;

and

a buffer management module for allocating the packets among said buffer groups,

said output group modules including a number of buffer groups equal to the number of input ports for facilitating quick transfer of packets from said input module to said buffer groups, each of said buffer groups including a plurality of buffers for preventing packet blocking and packet loss within said output group module.

20. The packet switch as set forth in claim 19, said buffer management module including means for allocating received packets to said buffer groups in sequential order for sharing said memory buffers among all of said output ports.

21. The packet switch as set forth in claim 19, including means for delivering a single broadcast packet to a plurality of output ports.

22. The packet switch as set forth in claim 21, said buffer management module including means for allocating a broadcast packet to a single memory buffer, means for determining the number of output ports the broadcast packet is destined for, means for counting the number of times the memory buffer storing the broadcast packet is read by the output ports, and means for releasing the memory buffer for another packet only after the memory buffer has been read by all the designated output ports.

23. The packet switch as set forth in claim 19 further including a plurality of read sequencers, each of said read sequencers being associated with a corresponding one of said output ports for receiving from said buffer management module a memory buffer address for indicating that a packet destined for its respective output port has been stored in that memory buffer.

24. The packet switch as set forth in claim 23, said read sequences each including means for receiving a plurality of different memory buffer addresses from said buffer management module and for selecting the highest priority packet to be read next by its respective output port.

25. The packet switch as set forth in claim 24, said read sequencers each including means for sorting the plurality of different memory buffer addresses according to their priority for facilitating the selecting of the highest priority packet.

26. The packet switch as set forth in claim 19, said output group module further including a buffer switching module for routing packets from said memory buffers to said output ports.

27. The packet switch as set forth in claim 19, said output group module further including an input processing module for delaying packets received from said input ports for a predetermined amount of time before delivery to said buffer groups to allow said buffer management module time to allocate the packets among said buffer groups.

28. The packet switch as set forth in claim 27, said buffer management module including means for generating and delivering to said input processing module routing tags for routing the packets to the appropriate buffer groups.

29. The packet switch as set forth in claim said input processing module including means for attaching said routing tags to the packets for routing the packets to the appropriate buffer groups.