Method and apparatus for maintaining packet order integrity in parallel switching engine

• US 6,721,309 B1
• Filed: 05/18/1999
• Issued: 04/13/2004
• Est. Priority Date: 05/18/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Reader, Scot A., Stone, Geoffrey C.
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/314,261
• Time in Patent Office: 1,792 Days
• Field of Search: 370/412, 370/413, 370/428, 370/394, 370/397, 370/399, 370/362, 370/364
• US Class Current: 370/362
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 49/102 using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/153 ATM switching fabrics having parallel switch planes
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A method and apparatus for maintaining packet order integrity in a switching engine wherein inbound packets are forwarded to different ones of parallel processing elements for switching. Order preservation for packets relating to the same conversation is guaranteed by checking for each inbound packet whether a previous packet from the same source is pending at a processing element and, if the check reveals that such a packet is pending, forwarding the inbound packet to the same processing element as the previous packet.

Claims

1. A method for preserving packet order integrity in a switching engine wherein packets are forwarded to different ones of a plurality of processing elements within a processor array for switching, comprising checking for each inbound packet whether another packet from the same source is pending at an individual processing element before forwarding the inbound packet to the individual processing element.

2. A method for preserving packet order integrity in a switching engine wherein packets are forwarded to different ones of a plurality of parallel processing elements for switching, comprising:

checking for an inbound packet whether another packet from the same source is pending at any processing element; and

if another packet from the same source is pending at any processing element, forwarding the inbound packet to the processing element at which the other packet from the same source is pending.

3. The method according to claim 2, further comprising:

if no other packet from the same source is pending at any processing element, forwarding the inbound packet to a processing element selected in accordance with a predetermined algorithm.

4. The method according to claim 2, further comprising:

if no other packet from the same source is pending at any processing element, forwarding the inbound packet to a processing element selected in accordance with a predetermined load balancing algorithm.

5. The method according to claim 2, further comprising:

if no other packet from the same source is pending at any processing element, forwarding the inbound packet to a processing element having the lowest backlog of packets.

6. A method for preserving packet order integrity in a switching engine wherein packets are forwarded to different ones of a plurality of processing elements within a processor array for switching, comprising checking for each inbound packet whether a source of the packet is committed to a processing element within the processor array before forwarding the inbound packet to the processor array.

7. A method for preserving packet order integrity in a switching engine wherein packets are forwarded to different ones of a plurality of processing elements within a processor array for switching, comprising:

determining if a source of an inbound packet is committed to any processing element; and

if the source of the inbound packet is committed to any processing element, forwarding the inbound packet to the processing element to which the source is committed.

8. The method according to claim 7, further comprising:

if the source of the inbound packet is not committed to any processing element, forwarding the inbound packet to a processing element selected in accordance with a predetermined algorithm.

9. The method according to claim 7, further comprising:

if the source of the inbound packet is not committed to any processing clement, forwarding the inbound packet to a processing clement selected in accordance with a predetermined load balancing algorithm.

10. The method according to claim 7, further comprising:

if the source of the inbound packet is not committed to any processing element, forwarding the inbound packet to a processing element having the lowest backlog of packets.

11. In a switching engine wherein packets from different sources are forwarded to different ones of a plurality of parallel processing elements for switching, a method for preserving packet order integrity, comprising:

committing a source to processing element; and

forwarding inbound packets from the source to the processing clement and no other processing element until the commitment is released

12. The method according to claim 11, wherein the commitment is released when all the inbound packets from the source have been switched from the processing element.

13. A switching engine to switch packets from a plurality of sources comprising:

a processor array to switch the packets and provide them as output, the processor array including a plurality of parallel processing elements; and

a plurality of input controllers to receive the packets from the plurality of sources and to provide the received packets to the processor array,

wherein the input controller, after receiving a packet, determines whether another packet from the same source is pending within the processor array before forwarding the packet to the processor array,

wherein the processor array provides packets from each of the plurality of sources as output in the order they are received as to preserve packet order integrity of the packets from the same source.

14. The switching engine of claim 13 wherein each input controller, after receiving a packet, determines whether another packet from the same source is pending at any of the parallel processing elements, and wherein the input controller, if another packet from the same source is pending at one of the parallel processing elements, forwards the packet to that processing element.

15. The switching engine of claim 14 wherein the input controller, if no other packet from the same source is pending at any of the parallel processing elements, forwards the packet to one of the parallel processing elements selected in accordance with a predetermined algorithm.

16. The switching engine of claim 14 wherein the input controller, if no other packet from the same source is pending at any of the parallel processing elements, forwards the packet to one of the parallel processing elements selected in accordance with a predetermined load balancing algorithm.

17. The switching engine of claim 14 wherein the input controller, if no other packet from the same source is pending at any of the parallel processing elements, forwards the packet to the processing element having the lowest backlog of packets.

18. The switching engine of claim 13 wherein each input controller, after receiving a packet, determines whether the source providing the packet is committed to any of the parallel processing elements before providing the packet to the processor array.

19. The switching engine of claim 18 wherein each input controller, if the source providing the packet is committed to one of the parallel processing elements, provides the packet to that processing element.

20. The switching engine of claim 18 wherein each input controller, if the source providing the packet is not committed to any of the parallel processing elements, provides the packet to a processing element selected in accordance with a predetermined algorithm.

21. The switching engine of claim 18 wherein each input controller, if the source providing the packet is not committed to any of the parallel processing elements, provides the packet to a processing element selected in accordance with a predetermined load balancing algorithm.

22. The switching engine of claim 18 wherein each input controller, if the source providing the packet is not committed to any of the parallel processing elements, provides the packet to a processing element having the lowest backlog of packets.

23. The switching engine of claim 13 wherein the packets from different sources are forwarded to different ones of the plurality of parallel processing elements, and wherein at least one source is committed to a processing element and the packets from the committed source are provided to the processing element and no other processing element until the commitment is released.

24. The switching engine of claim 23 wherein the commitment is released when all the packets from the committed source have been switched from the processing element.