Packet routing and switching device

• US 7,382,787 B1
• Filed: 06/20/2002
• Issued: 06/03/2008
• Est. Priority Date: 07/30/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mehrotra, Sharad, Lynch, William L., Jayaram, Nikhil, Li, Anthony J., Barnes, Peter M.
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): HARTMANN II, KENNETH R
• Application Number:
  US10/177,496
• Time in Patent Office: 2,175 Days
• Field of Search: 370/392, 370/389, 370/349, 370/395.31
• US Class Current: 370/401
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method for routing and switching data packets from one or more incoming links to one or more outgoing links of a router. The method comprises receiving a data packet from the incoming link, assigning at least one outgoing link to the data packet based on the destination address of the data packet, and after the assigning operation, storing the data packet in a switching memory based on the assigned outgoing link. The data packet extracted from the switching memory, and transmitted along the assigned outgoing link. The router may include a network processing unit having one or more systolic array pipelines for performing the assigning operation.

Claims

1. A method for storing a packet in a memory of a router, comprising:

parsing a packet header to extract an Internet Protocol (IP) address and Quality of Service (QoS) data, the IP address and QoS data used, in part, to create a packet context;

assigning an Interface Ordinal Descriptor (IOD) number to the packet, the IOD specifying a port upon which the packet was received;

passing the IP address of the packet through a systolic array pipeline to perform a forwarding table lookup using a trie search of tries stored in a forwarding table;

based on at least a portion of the IP address of the packet obtained from the forwarding table lookup, assigning the packet to at least one outgoing link of the router; and

storing the packet in the memory based on the assigning operation.

2. The method of claim 1, wherein the assigning operation includes assigning a destination queue to the packet, the destination queue being mapped to the assigned outgoing link.

3. The method of claim 2, wherein the storing operation writes the packet in the destination queue.

4. The method of claim 1, wherein the storing operation includes dividing the packet into at least two cells.

5. The method of claim 4, wherein the at least two cells are less than or equal to 34 bytes.

6. The method of claim 4, wherein the storing operation writes the at least two cells in the destination queue.

7. The method of claim 4, wherein the storing operation writes the at least two cells in the destination queue contiguously in round robin order.

8. The method of claim 1, wherein the assigning operation further comprises:

providing a forwarding table memory having a plurality of nodes arranged in a trie, wherein each node contains a portion of various IP addresses, an indicator indicating if the IP address of the node is supported by the router and a queue of the router associated with the node;

comparing a portion of the IP address of the packet to one or more of the various destination addresses in the trie to locate the longest match there between;

determining the node which contains longest match and examining the indicator therein;

if the indicator, in the node which contains the longest match, indicates that the router supports the IP address of the node which contains the longest match, then associating the packet with the queue of the router associated with the node which contains the longest match.

9. The method of claim 8, wherein the comparing operation compares the most significant bits of the destination address of the packet to the most significant bits of the various destination addresses in the trie.

10. In a router for routing and switching data packets from one or more incoming links to one or more outgoing links, each data packet including a packet header specifying a Internet Protocol (IP) address and Quality of Service (QoS) data for the data packet, a method for routing and switching a data packet comprising:

receiving the data packet from the incoming link, and assigning an Interface Ordinal Descriptor (IOD) number to the data packet, the IOD specifying a port upon which the data packet was received;

passing the IP address of the packet through a systolic array pipeline to perform a forwarding table lookup using a trie search of tries stored in a forwarding table;

assigning at least one outgoing link to the data packet based on the IP address of the data packet, the IP address being obtained from the forwarding table lookup;

after the assigning operation, storing the data packet in a switching memory based on the assigned outgoing link for the data packet;

extracting the data packet from the switching memory; and

transmitting the data packet to the assigned outgoing link.

11. The method of claim 10, wherein the operation of assigning an outgoing link to the data packet includes assigning a destination queue to the data packet, the destination queue being mapped to the assigned outgoing link.

12. The method of claim 11, wherein the operation of storing the data packet in a switching memory includes the operation of storing the data packet in the assigned destination queue.

13. The method of claim 10, wherein the operation of storing the data packet in a switching memory includes dividing the data packet into at least two cells.

14. The method of claim 13, wherein the at least two cells are less than or equal to 34 bytes.

15. The method of claim 13, wherein the operation of storing the data packet in the switching memory includes the operation of storing the at least two cells in the destination queue.

16. The method of claim 13, wherein the operation of storing the data packet in the switching memory includes the operation of storing the at least two cells contiguously in round robin order in the destination queue.

17. In a router having one or more incoming links and one or more outgoing links, a method of routing and switching data packets where each data packet has a packet header specifying a destination internet protocol (IP) address for the packet, the method comprising:

providing a systolic array pipeline in communications with a forwarding table;

receiving a data packet from an incoming link;

looking-up the destination IP address of the data packet in the forwarding table using the systolic array pipeline, the looking-up performed using a trie search of tries stored in the forwarding table;

assigning an outgoing link to the data packet;

storing the data packet in a memory based on the assigning operation;

extracting the data packet from the memory as cells in a contiguous order stored in an assigned destination queue; and

transmitting the packet to the assigned outgoing link.

18. The method of claim 17, wherein the operation of storing a data packet in a memory occurs after the looking-up operation.

19. The method of claim 17, wherein the looking-up operation assigns a destination queue to the packet, the destination queue being mapped to the outgoing link for the packet.

20. The method of claim 19, wherein the operation of storing the data packet in a memory includes the operation of storing the data packet in the assigned destination queue.

21. The method of claim 19, wherein the operation of storing the data packet in a memory includes the operation of dividing the data packet into at least two cells.

22. The method of claim 21, wherein the at least two cells is less than or equal to 34 bytes.

23. The method of claim 21, wherein the operation of storing the data packet in a memory includes storing the at least two cells in the destination queue.

24. The method of claim 21, further comprising reassembling the data packet using, in part, the cells stored in the contiguous order.

25. In a router for routing and switching a data packet from an incoming link in a packet switched network to an outgoing link in the packet switched network, the data packet including a packet header having a Internet Protocol (IP) address for the packet, a method of routing and switching the data packet comprising:

receiving the data packet from the incoming link;

parsing a packet header to extract an Internet Protocol (IP) address and Quality of Service (QoS) data, the IP address and QoS data used, in part, to create a packet context;

assigning an Interface Ordinal Descriptor (IOD) number to the packet, the IOD specifying a port upon which the packet was received;

determining the outgoing link for the data packet using a systolic array pipeline to perform a forwarding table lookup using a trie search of tries stored in a forwarding table;

writing a portion of the data packet to a memory as cells in a contiguous order; and

transmitting the data packet to the outgoing link.

26. The method of claim 25, wherein determining the outgoing link for the packet further includes:

parsing the packet to extract the IP address;

performing a forwarding table lookup of the IP address to assign a base destination queue to the data packet using a trie search of tries stored in a forwarding table; and

queuing to assign a destination queue to the data packet.

27. The method of claim 26, wherein determining the outgoing link for the data packet includes assigning a destination queue to the data packet, the destination queue being mapped to the outgoing link for the data packet.

28. The method of claim 27, wherein writing the data packet further includes:

dividing the data packet into at least two cells; and

storing the at least two cells in the destination queue for the data packet.

29. The method of claim 28, further comprising reassembling the data packet using, in part, the cells stored in the contiguous order.