Architecture for high speed class of service enabled linecard

• US 6,687,247 B1
• Filed: 10/27/1999
• Issued: 02/03/2004
• Est. Priority Date: 10/27/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dan, Yie-Fong, Wilford, Bruce
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/428,870
• Time in Patent Office: 1,560 Days
• Field of Search: 370/392, 370/389, 370/393, 370/475, 370/397, 370/400, 370/471, 370/399, 370/349, 370/401, 370/402, 370/413, 370/412, 709/238, 709/265
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 45/502 Frame based
• CPC Class Codes: H04L 45/583 Stackable routers
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

A linecard architecture for high speed routing of data in a communications device. This architecture provides low latency routing based on packet priority: packet routing and processing occurs at line rate (wire speed) for most operations. A packet data stream is input to the inbound receiver, which uses a small packet FIFO to rapidly accumulate packet bytes. Once the header portion of the packet is received, the header alone is used to perform a high speed routing lookup and packet header modification. The queue manager then uses the class of service information in the packet header to enqueue the packet according to the required priority. Enqueued packets are buffered in a large memory space holding multiple packets prior to transmission across the device'"'"'s switch fabric to the outbound linecard. On arrival at the outbound linecard, the packet is enqueued in the outbound transmitter portion of the linecard architecture. Another large, multi-packet memory structure, as employed in the inbound queue manager, provides buffering prior to transmission onto the network.

Claims

1. An apparatus for routing packets in a communications network device comprising:

an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail;

a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information;

a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet;

an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer,

wherein said inbound receiver, said lookup circuit, and said first packet modifier circuit each operate substantially at said line rate in said linecard.

2. The apparatus of claim 1 further comprising:

an outbound receiver connected to and concurrently receiving at least one outbound packet into a third buffer;

a second packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and

an outbound queue manager connected to said second packet modifier circuit that buffers said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer

wherein said outbound receiver and said second packet modifier circuit each operate substantially at said line rate in said linecard.

3. The apparatus as recited in claim 1, wherein said first buffer comprises a FIFO.

4. The apparatus as recited in claim 1, wherein said data structure further comprises an M-way branching tree structure.

5. The apparatus as recited in claim 1, wherein said first packet modifier circuit further comprises an inbound rate limiter.

6. The apparatus as recited in claim 1, wherein said inbound queue manager further comprises a buffer usage manager.

7. The apparatus as recited in claim 1, wherein said inbound queue manager further comprises a circuit that dequeues said packet using a modified deficit round robin algorithm.

8. An apparatus for routing packets in a communications network device comprising:

an outbound receiver connected to and concurrently receiving at least one outbound packet into a first buffer;

a first packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and

an outbound queue manager connected to said first packet modifier circuit that buffers said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer

wherein said outbound receiver and said first packet modifier circuit each operate substantially at said line rate in said linecard.

9. The apparatus as recited in claim 8, wherein said first buffer comprises one or more FIFOs.

10. The apparatus as recited in claim 8, wherein said first packet modifier circuit further comprises an outbound rate pacer.

11. The apparatus as recited in claim 8, wherein said first packet modifier circuit further comprises a buffer usage manager.

12. The apparatus as recited in claim 8, wherein said first packet modifier circuit further comprises an outbound rate limiter.

13. The apparatus as recited in claim 8, wherein said outbound queue manager further comprises a circuit that dequeues said packet using a modified deficit round robin algorithm.

14. A method of routing packets in a communications network device, comprising the steps of:

a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail;

b) comparing said header to a data structure;

c) determining routing information;

d) modifying said header according to at least said routing information to form a modified packet;

e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

wherein said steps a) through d) are performed substantially at said line rate in said linecard.

15. The method of claim 14 further comprising the steps of:

f) concurrently receiving at least one outbound packet into a third buffer;

g) modifying said outbound packet according to information contained in said outbound packet; and

h) buffering said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer;

wherein said steps f) and g) are performed substantially at said line rate in said linecard.

16. The method of claim 14 wherein said data structure further comprises an M-way branching tree structure.

17. The method of claim 14 wherein the step of modifying said header further comprises inbound rate limiting.

18. The method of claim 14 wherein the step of buffering said modified packet further comprises managing buffer usage.

19. The method of claim 14 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.

20. A method of routing packets in a communications network device, comprising the steps of:

a) concurrently receiving at least one outbound packet into a first buffer;

b) modifying said outbound packet according to information contained in said outbound packet; and

c) buffering said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

wherein said steps a) and b) are performed substantially at said line rate in said linecard.

21. The method of claim 20 wherein the step of modifying said outbound packet further comprises outbound rate pacing.

22. The method of claim 20 wherein the step of modifying said outbound packet further comprises managing buffer usage.

23. The method of claim 20 wherein the step of modifying said outbound packet further comprises outbound rate limiting.

24. The method of claim 20 wherein the step of buffering said outbound packet further comprises dequeuing said packet using a modified deficit round robin algorithm.

25. A computer system for interfacing with a communications network, comprising computer instructions for:

a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail;

b) comparing said header to a data structure;

c) determining routing information;

d) modifying said header according to at least said routing information to form a modified packet;

e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

wherein said steps a) through d) are performed substantially at said line rate in said linecard.

26. The computer system of claim 25 wherein said data structure further comprises an M-way branching tree structure.

27. The computer system of claim 25 wherein the step of modifying said header further comprises inbound rate limiting.

28. The computer system of claim 25 wherein the step of buffering said modified packet further comprises managing buffer usage.

29. The computer system of claim 25 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.

30. A computer readable storage medium, comprising computer instructions for:

a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail;

b) comparing said header to a data structure;

c) determining routing information;

d) modifying said header according to at least said routing information to form a modified packet;

e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

wherein said steps a) through d) are performed substantially at said line rate in said linecard.

31. The computer readable storage medium of claim 30 wherein said data structure further comprises an M-way branching tree structure.

32. The computer readable storage medium of claim 30 wherein the step of modifying said header further comprises inbound rate limiting.

33. The computer readable storage medium of claim 30 wherein the step of buffering said modified packet further comprises managing buffer usage.

34. The computer readable storage medium of claim 30 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.

35. A computer readable carrier wave, comprising computer instructions for:

a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail;

b) comparing said header to a data structure;

c) determining routing information;

d) modifying said header according to at least said routing information to form a modified packet;

e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

wherein said steps a) through d) are performed substantially at said line rate in said linecard.

36. The computer readable carrier wave of claim 35 wherein said data structure further comprises an M-way branching tree structure.

37. The computer readable carrier wave of claim 35 wherein the step of modifying said header further comprises inbound rate limiting.

38. The computer readable carrier wave of claim 35 wherein the step of buffering said modified packet further comprises managing buffer usage.

39. The computer readable carrier wave of claim 35 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.

40. An apparatus for routing packets in a communications network device comprising:

an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail;

a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information;

a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet;

an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer,

an outbound receiver connected to and concurrently receiving at least one outbound packet into a third buffer;

a second packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and

an outbound queue manager connected to said second packet modifier circuit that buffers said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer,

wherein said inbound receiver, said lookup circuit, said first packet modifier circuit, said outbound receiver, and said second packet modifier circuit each operate substantially at said line rate in said linecard.

41. A method of routing packets in a communications network device, said method comprising:

a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail;

b) comparing said header to a data structure;

c) determining routing information;

d) modifying said header according to at least said routing information to form a modified packet;

e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer;

f) concurrently receiving at least one outbound packet into a third buffer;

g) modifying said outbound packet according to information contained in said outbound packet; and

h) buffering said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer;

wherein a) through d), f), and g) are performed substantially at said line rate in said linecard.