High bandwidth packet switch

• US 5,291,482 A
• Filed: 07/24/1992
• Issued: 03/01/1994
• Est. Priority Date: 07/24/1992
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Newman, Thomas E., Wendland, Kenneth E., McHarg, Christopher G., Schaff, Kenneth N.
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US07/919,461
• Time in Patent Office: 585 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/94.2, 370/58.1, 370/58.2, 370/58.3, 370/61
• US Class Current: 370/413
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing

Abstract

A fast packet switch comprising one buffer directly connected between a plurality of input ports and a plurality of output ports to effect rapid throughput of data packets. A pointer to a location in the buffer is allocated by a buffer manager upon receipt of notification of an incoming packet at the receiving input port and the input port delivers the packet as it is received to the location designated by the pointer. After the data packet is received, the input port delivers the pointer and a destination address for the packet to a router, which selects one of the plurality of output ports based on the destination address. The router queues the pointer in a queue for the selected output port. The output port then retrieves the data packet from the buffer using the pointer to determine the location, and transmits the data packet. After the transmission is complete, the output port returns the pointer to the buffer manager. This packet switch may be pipelined to receive, route, and transmit simultaneously on adjacent data packets.

Claims

1. A fast packet switch for routing data packets from a source to a destination, said data packets having a destination address, said switch comprising:

a plurality of input ports, a plurality of output ports, a buffer connected to said input ports and said output ports, a buffer manager connected to said input ports and said output ports, and a router connected to said input ports and said output ports;

said buffer manager selecting a location in said buffer in response to notification of receipt of a data packet at one of said input ports and producing data representing said buffer location, said input ports each having means responsive to receipt of said data representing said buffer location for delivering said incoming packet to said buffer location;

said router having means responsive to receipt of said data representing said buffer location and said destination address from said input ports for delivering said data representing said buffer location to a selected one of said plurality of output ports responsive to said destination address;

each of said output ports having means responsive to receipt of said data representing said buffer location for retrieving said data packet from said buffer location, transmitting said data packet and returning said data representing said buffer location to said buffer manager.

2. A fast packet switch according to claim 1 wherein said input ports receive data packets from a plurality of channels.

3. A fast packet switch according to claim 2 wherein each of said channels comprises one or more time slots, said input ports having means responsive to the arrival of each of said time slots to direct data received during that time slot to said buffer location selected by said buffer manager for said time slot.

4. A fast packet switch according to claim 3 wherein each of said input ports comprises a protocol state machine and an address state machine, said protocol state machine sequentially receiving data during each time slot and delivering said data to a location in said buffer based on an address calculated at said address state machine, wherein data for each data packet is stored sequentially in the order received in said buffer.

5. A fast packet switch according to claim 4 wherein each of said input ports further comprises a channel state buffer for storing information for said protocol state machine and said address state machine for each channel.

6. A fast packet switch according to claim 1 wherein said router comprises means for mapping said destination address to one of said output ports.

7. A fast packet switch according to claim 1 wherein said router comprises an output port FIFO for queuing said data representing said buffer location for said selected output port.

8. A fast packet switch according to claim 1 wherein said router comprises a look-up table for mapping said destination address to one of said output ports and an output port FIFO for queuing said data representing said buffer location for said selected output port.

9. A fast packet switch according to claim 1 wherein said output ports transmit data packets over a selected one of a plurality of channels.

10. A fast packet switch according to claim 9 wherein each of said channels comprises one or more time slots, said output port being responsive to the arrival of each of said time slots to transmit said data packet from said buffer during each time slot over said selected channel.

11. A fast packet switch according to claim 10 wherein each of said output ports comprises a protocol state machine and an address state machine, said protocol state machine obtaining data from said buffer location based on an address calculated by said address state machine and sequentially transmitting said data on each time slot.

12. A fast packet switch according to claim 11 wherein each of said output ports further comprises a channel state buffer for storing information for said protocol state machine and said address state machine for each channel.

13. A fast packet switch according to claim 1 wherein said buffer manager comprises a FIFO queue for storing said data representing said buffer locations.

14. A fast packet switch according to claim 13 wherein said buffer manager is responsive to said input ports for removing one of said data representing said buffer locations from said FIFO queue and delivering said data representing said buffer locations to said input ports and is further responsive to said output port delivering said data representing said buffer locations for returning said data representing said buffer locations to said FIFO queue.

15. A method for use in a packet switch for routing data packets from a source to a destination, said data packets each having a destination address and an end of packet signal, said packet switch comprising an input port, a plurality of output ports, a buffer connected to said input port and said output port, a buffer manager for allocating and deallocating pointers to locations in said buffer, and a router means for selecting one of said plurality of output ports, said method comprising:

responsive to receipt of a data packet from said source, said input port requesting a pointer from said buffer manager;

responsive to said pointer request, said buffer manager allocating a pointer corresponding to a specific buffer location;

responsive to receipt of said pointer, said input port delivering said data packet to said buffer, starting at said location, as said data packet is received from said source;

responsive to receipt of said end of packet signal, said input port delivering said pointer and said destination address to said router means;

responsive to receipt of said pointer and said destination address, said router selecting one of said plurality of output ports, and delivering said pointer to said selected output port;

responsive to receipt of said pointer, said selected output port retrieving said data packet from said buffer and transmitting said data packet to said destination; and

responsive to transmitting said end of packet signal, said selected output port returning said pointer to said buffer manager.

16. A method according to claim 15 wherein said step of delivering said data packet to said buffer comprises receiving said data packets on a plurality of channels delivered during a plurality of time slots by receiving a portion of said data packet during each time slot and delivering said portion of said data packet to its location in said buffer based on said pointer allocated for that data packet.

17. A method according to claim 15 wherein said step of selecting one of said plurality of output ports comprises looking up said destination address to derive said selected output port and queuing said pointer for said output port.

18. A method according to claim 15 wherein said step of retrieving said data packets from said buffer and transmitting said data packets comprises transmitting said data packets on a plurality of channels during a plurality of time slots, said selected output port retrieving data for said data packets from said buffer using said pointer and delivering said data packets on a predetermined channel.

19. A method according to claim 15 wherein said step of allocating a pointer comprises selecting said pointer from a queue of pointers on a first in, first out basis.

20. A method according to claim 15 wherein said steps are performed in a pipelined fashion.

21. A fast packet switch for routing data packets from a source to a destination, said data packets having a destination address, said switch comprising:

buffer means having a plurality of locations for storing data;

pointer control means for controlling storage of said data packets in said buffer means;

input means for receiving data packets from said source and delivering said data packets to said buffer means under control of said pointer control means;

a plurality of output means for sending said data packet to said destinations, said output means determining the destinations of said data packets in response to said pointer control means; and

routing means for selecting one of said plurality of said output means responsive to said pointer control means and said destination address.

22. A fast packet switch according to claim 21 wherein said input means receive data packets from a plurality of channels, wherein each of said channels comprises one or more time slots, said input means being responsive to the arrival of each of said time slots to direct data received during each time slot to its proper location in said buffer means.

23. A fast packet switch according to claim 22 wherein each of said input means comprises a protocol state machine and an address state machine for sequentially receiving data on each time slot at said protocol state machine and delivering said data to a location in said buffer means based on an address calculated at said address state machine based on data received from said pointer control means.

24. A fast packet switch according to claim 21 wherein said router means comprises means for mapping said destination address to one of said output ports.

25. A fast packet switch according to claim 21 wherein said router means comprises an output port FIFO for queuing data received from said pointer control means and said destination address for delivery to said selected output means.

26. A fast packet switch according to claim 21 wherein said router means comprises a look-up table for mapping said destination address to one of said output means and an output means FIFO for queuing data received from said pointer control means and said destination address for delivery to said selected output means.

27. A fast packet switch according to claim 21 wherein said output means transmit data packets over a selected one of a plurality of channels, said channel being selected according to said destination address, wherein each of said channels comprises one or more time slots, said output means being responsive to the arrival of each of said time slots to transmit said data packet from said buffer during each time slot over said selected channel.

28. A fast packet switch according to claim 21 wherein said buffer controller comprises a FIFO queue for storing pointer to said buffer locations;

said buffer controller being responsive to said input means for removing one of said pointer from said FIFO queue and delivering said pointer to said input means and is further responsive to said output means delivering said pointer for returning said pointer to said FIFO queue.