System and method for router packet control and ordering

• US 6,876,657 B1
• Filed: 12/14/2000
• Issued: 04/05/2005
• Est. Priority Date: 12/14/2000
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Chiaro Networks, Ltd.
• Inventors: Brewer, Tony M., Palmer, Gregory S., Kleiner, Jim, Dugan, Michael K., Vogel, Paul F.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Juntima, Nittaya
• Application Number:
  US09/737,646
• Time in Patent Office: 1,573 Days
• Field of Search: 370/394, 370/401, 370/412, 370/413, 370/414, 370/428
• US Class Current: 370/394
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/352 Gigabit ethernet switching [GBPS]
• CPC Class Codes: H04L 49/357 Fibre channel switches

Abstract

Hardware interconnected around multiple packet forwarding engines prepends sequence numbers to packets going into multiple forwarding engines through parallel paths, After processing by the multiple forwarding engines, packets are reordered using queues and a packet ordering mechanism, such that the sequence numbers are put back into their original prepended order. Exception packets flowing through the forwarding engines do not follow a conventional fast path, but are processed off-line and emerge from the forwarding engines out of order relative to fast path packets. These exception packets are marked, such that after they exit the forwarding engines, they are ordered among themselves independent of conventional fast path packets. Viewed externally, all exception packets are ordered across all multiple forwarding engines independent of the fast path packets.

Claims

1. A system for router packet control and ordering comprising:

a packet forwarding engine containing a plurality of fast data paths each interconnected with an input port and an output port;

a processing block interconnected with said input ports of said packet forwarding engine through a plurality of rate matching queues;

an ingress application specific integrated circuit (ASIC) containing a packet ordering block, said packet ordering block interconnected with said output ports of said packet forwarding engine through a plurality of reorder queues within said ingress ASIC; and

a packet data random access memory (RAM) interconnected with said ingress ASIC, wherein said packet forwarding engine contains an exception processor, such that said fast data path bypasses said exception processor and such that said fast data path is interconnected with said exception processor through an exception data path.

2. The system of claim 1 wherein said input ports of said packet forwarding engine include a wide bandwidth port and a narrow bandwidth port.

3. The system of claim 2 wherein said wide bandwidth port has a capacity of approximately 3.2 gigabits per second (Gb/s).

4. The system of claim 2 wherein said narrow bandwidth port has a capacity of approximately 1.6 Gb/s.

5. The system of claim 1 wherein said reorder queues include an exception reorder queue.

6. The system of claim 1 wherein said packet ordering block contains a now-serving counter.

7. The system of claim 1 wherein said processing block is interconnected with an input data link having a bandwidth capacity of approximately 10 Gb/s.

8. The system of claim 1 wherein said processing block is interconnected with multiple input data links, such that each said data link has a bandwidth capacity of at least 1.0 Gb/s.

9. The system of claim 8 wherein each said data link has a bandwidth capacity of approximately 2.5 Gb/s.

10. A system for router packet control and ordering comprising:

a packet forwarding engine containing a plurality of fast data paths each interconnected with an input port and an output port;

a processing block interconnected with said input ports of said packet forwarding engine through a plurality of rate matching queues;

an ingress application specific integrated circuit (ASIC) containing a packet ordering blocks said packet ordering block interconnected with said output torts of said packet forwarding engine through a plurality of reorder queues within said ingress ASIC; and

a packet data random access memory (RAM) interconnected with said ingress ASIC, said system comprising a plurality of said packet forwarding engines, such that each said packet forwarding engine contains a plurality of fast data paths each interconnected with an input port and an output port, each said input port interconnected with said processing block through a plurality of rate matching queues; and

each said output port interconnected with said packet ordering block through a plurality of reorder queues within said ingress ASIC.

11. The system of claim 10 wherein said processing block is interconnected with an input data link having a bandwidth capacity of approximately 10 Gb/s.

12. The system of claim 10 wherein said processing block is interconnected with multiple input data links, such that each said data link has a bandwidth capacity of at least 1.0 Gb/s.

13. The system of claim 12 wherein each said data link has a bandwidth capacity of approximately 2.5 Gb/s.

14. The system of claim 10 wherein said processing block is partitioned into a plurality of independent processing sub-blocks.

15. The system of claim 10 wherein said packet ordering block is partitioned into a plurality of independent packet ordering sub-blocks.

16. A method of control and ordering of information packets in a network router comprising:

receiving through an input data link said packets;

sequence numbering said packets;

distributing said packets among a plurality of rate matching queues, such that each said rate matching queue feeds one of substantially parallel data links having differing information rates;

flowing said packets through said plurality of substantially parallel data links at differing information rates; and

reordering said packets after said flowing;

said packets comprising fast path packets and exception packets different from said fast path packets, wherein said exception packets are processed within a portion of said plurality of substantially parallel data links that is bypassed by said fast path packets, wherein said exception packets are reordered separately and independently from said fast path packets; and

wherein said reordering of fast path packets comprises;

receiving said fast path packets from said substantially parallel data links;

separating said packet headers from said packet payloads;

loading said packet headers into a plurality of fast path reorder queues; and

removing said packet headers from said fast path reorder queues in order of said sequence numbering.

17. The method of claim 16 wherein said removing comprises:

a. incrementing a now-serving number by one unit;

b. if a packet header having a sequence number matching said now-serving number is in said plurality of fast path reorder queues, then removing said packet header and iterating steps a and b;

otherwise

c. after a subsequent packet header arrives in each of said fast path reorder queues, if a packet header having a sequence number matching said now-serving number is in said plurality of fast path reorder queues, then removing said packet header and iterating steps a, b and c;

otherwise

d. iterating steps a, b, and c until a packet header is found having a sequence number matching said now-serving number.

18. The method of claim 17 wherein, if any of said plurality of fast path reorder queues does not receive a subsequent packet header during a programmable elapsed period of time, then inserting a keep-alive packet into a fast path reorder queue.

19. The method of claim 18 wherein said programmable elapsed period of time is on the order of 10 microseconds.

20. The method of claim 16 further comprising storing said separated packet payloads in a memory device.

21. The method of claim 16 wherein said substantially parallel data links are limited to a maximum packet flow rate of approximately 2.1 million packets per second.

22. The method of claim 16 wherein a portion of said substantially parallel data links are narrow bandwidth data links.

23. The method of claim 22 wherein a portion of said substantially parallel data links are wide bandwidth data links, such that a maximum bandwidth limit of said wide bandwidth data links is greater than a maximum bandwidth limit of said narrow data links.

24. The method of claim 23 wherein the maximum bandwidth of said narrow bandwidth data links is approximately 1.6 gigabits per second (Gb/s).

25. The method of claim 23 wherein the maximum bandwidth of said wide bandwith data links is approximately 3.2 Gb/s.

26. The method of claim 23 wherein said packets are distributed among said rate matching queues according to packet size, such that large packets greater than a threshold size are placed in large packet queues feeding wide bandwidth data links and such that small packets not greater than said threshold size are placed in small packet queues feeding narrow bandwidth data links.

27. The method of claim 26 wherein said small packet is placed in a particular small packet queue having the greatest unoccupied space.

28. The method of claim 26 wherein said large packet is placed in a particular large packet queue having the greatest unoccupied space.

29. The method of claim 26 wherein said packets are distributed roughly equally among said rate matching queues using a round robin algorithm.

30. The method of claim 26 wherein said threshold size is approximately 200 bytes.

31. The method of claim 26 further comprising inserting a keep-alive packet into any narrow bandwidth data link that is idle for a predetermined period of time.

32. The method of claim 31 wherein said predetermined period of time is programmable.

33. The method of claim 31 wherein said predetermined period of time is on the order of 10 microseconds.

34. The method of claim 16 wherein said packets are received through said input data link at a rate of approximately 10 Gb/s.

35. The method of claim 16 further comprising processing said packets within each of said plurality of substantially parallel data links, such that said processing is limited to a maximum data rate of approximately 2.5 Gb/s.

36. The method of claim 16 wherein said sequence numbering is applied within a header prepended to each of said packets.

37. The method of claim 16 wherein said exception packets are distinguished form said fast path packets by setting a bit within a header prepended to each said packet.

38. A method of control and ordering of information packets in a network router comprising:

receiving through an input data link said packets;

sequence numbering said packets;

distributing said packets among a plurality of rate matching queues, such that each said rate matching queue feeds one of substantially parallel data links having differing information rates;

flowing said packets through said plurality of substantially parallel data links at differing information rates; and

reordering said packets after said flowing;

said packets comprising fast path packets and exception packets different from said fast path packets, wherein said exception packets are processed within a portion of said plurality of substantially parallel data links that is bypassed by said fast path packets, wherein said exception packets are reordered separately and independently from said fast path packets; and

wherein said separate and independent reordering of exception packets comprises;

receiving said exception packets from said substantially parallel data links;

separating said exception packet headers from said exception packet payloads;

loading said exception packet headers into a plurality of exception reorder queues; and

removing said exception packet headers from said exception reorder queues in order of said sequence numbering.

39. The method of claim 38 further comprising storing said separated exception packet payloads in a memory device.

40. The method of claim 38 wherein said removing comprises:

a. if an exception packet header exists in each of said plurality of exception reorder queues, then removing the exception packet header having the lowest sequence number;

otherwise

b. after a time-out mechanism occurs, then removing the exception packet header having the lowest sequence number among all exception packets in any of said exception reorder queues.

41. The method of claim 40 wherein said time-out mechanism is programmable.

42. The method of claim 38 wherein nonordering packets are created within said portion of said plurality of substantially parallel data links wherein said exception packets are processed, said nonordering packets being identified by a bit set within a header of said nonordering packets, such that a said identified nonordering packet is loaded into one of said reorder queues and upon reaching the head of said reorder queue is removed from said reorder queue without regard to any sequence numbering.