Packet routing and switching device

• US 9,094,237 B2
• Filed: 08/31/2012
• Issued: 07/28/2015
• Est. Priority Date: 07/30/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Barnes, Peter M., Jayaram, Nikhil, Li, Anthony J., Lynch, William L., Mehrotra, Sharad
• Primary Examiner(s): Murphy, Rhonda
• Application Number:
  US13/601,797
• Publication Number:
  US 20120320921A1
• Time in Patent Office: 1,061 Days
• Field of Search: None
• US Class Current: 1/1
• 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 network device routes data packets by storing the packets in a switching memory as a function of a destination address of the packet. The switching memory comprises switching memory queues that are mapped to ports of the device. A header of a received packet is examined to determine the network destination address to which it is to be routed, and a destination queue is assigned to the packet based on the destination address. Thereafter, the packet is divided into cells, and the cells are written to contiguous locations in the destination queue.

Claims

1. A network device comprising:

a switching memory comprising a plurality of switching memory queues associated with a plurality of ports of the network device, each switching memory queue being mapped to a corresponding one of the plurality of ports;

one or more processors to

examine a header of a received packet to determine a destination address that identifies one or more network destinations to which the packet is to be routed via the network device,

form a packet context from at least a portion of the header of the received packet, wherein the packet context includes at least the destination address of the received packet,

determining whether a destination queue selected from the plurality of switching memory queues can be assigned to the packet based at least on a portion of the packet context,

if a destination queue can be assigned to the packet based at least on the portion of the packet context then assigning the destination queue to the packet,

if a destination queue cannot be assigned to the packet based at least on the portion of the packet context then stroking the packet context associated with the packet, determining the destination queue from the stroked packet context, and assigning the destination queue determined from the stroked packet context to the packet;

a striper to divide the packet into multiple cells after the destination queue has been assigned to the packet; and

a memory control unit to write the multiple cells of the packet to contiguous locations in the destination queue, so that the multiple cells for the packet are stored contiguously in the switching memory as a function of the destination address of the packet.

2. The network device of claim 1, further comprising a line card unit to:

receive the multiple cells of the packet from the destination queue; and

reassemble the packet from the multiple cells.

3. The network device of claim 1, wherein the multiple cells are each less than or equal to 34 bytes.

4. The network device of claim 1, wherein the memory control unit is configured to write the multiple cells to the destination queue in round robin order.

5. The network device of claim 1, wherein the one or more processors further comprise a forwarding table memory which has a plurality of nodes arranged in a trie, each node containing:

a portion of various destination addresses;

an indicator to indicate whether the destination address of the node is supported by the network device; and

an identification of a particular one of the plurality of switching memory queues of the network device associated with the node.

6. The network device of claim 5, wherein the one or more processors are configured to:

compare a portion of the destination address of the packet to one or more of the various destination addresses in the trie to locate the longest match;

identify the node which contains the longest match;

examine the indicator in the identified node; and

responsive to determining that the indicator node indicates that the network device supports the destination address of the node which contains the longest match, processor associates the packet with the queue of the network device associated with the node which contains the longest match.

7. The network device of claim 6, wherein the one or more processors are configured to compare most significant bits of the destination address of the packet to most significant bits of the various destination addresses in the trie.

8. The network of device of claim 1, further comprising:

a route processor to process routing protocol messages regarding the network; and

a queue to temporarily store routing protocol messages which are destined for the route processor.

9. A method comprising:

at a network device, receiving a data packet from an incoming link of the network device, the data packet including a packet header containing a destination address for the packet;

at one or more processors on the network device, looking-up an outgoing link of the network device associated with the destination address by,

forming a packet context from at least a portion of the packet header of the received packet, wherein the packet context includes at least the destination address of the received packet,

determining whether a destination queue selected from the plurality of switching memory queues can be assigned to the packet based at least on a portion of the packet context,

if a destination queue can be assigned to the packet based at least on the portion of the packet context then assigning the destination queue to the packet, wherein the destination queue is mapped to the assigned outgoing link,

if a destination queue cannot be assigned to the packet based at least on the portion of the packet context then stroking the packet context associated with the packet, determining the destination queue from the stroked packet context, and assigning the destination queue determined from the stroked packet context to the packet, wherein the destination queue is mapped to the assigned outgoing link;

thereafter, at a switching engine on the network device,

dividing the data packet into multiple cells, and

storing the multiple cells of the data packet contiguously in a switching memory as a function of the assigned outgoing link;

at a line card unit on the network device, receiving the multiple cells of the packet from the switching memory and reassembling the packet from the multiple cells; and

transmitting the reassembled data packet from the network device to the assigned outgoing link.

10. The method of claim 9, wherein the one or more processors comprise a network processing unit having systolic array pipeline connected with a forwarding table, the looking-up of the outgoing link comprising looking-up the destination address in the forwarding table.

11. The method of claim 10, wherein the looking-up of the destination address in the forwarding table includes assigning a destination queue to the packet based on the assigned outgoing link, the destination queue forming part of a plurality of queues in the switching memory, each switching memory queue being mapped to one of a plurality of outgoing links.

12. The method of claim 10, wherein the storing of the multiple cells in the memory includes storing the multiple cells in one of a plurality of queues in the switching memory, each switching memory queue being mapped to one of a plurality of outgoing links.

13. The method of claim 9, wherein the switching engine comprises a striper to divide the packet into the multiple cells, the switching engine further comprising at least one memory control unit connected with the switching memory.

14. The method of claim 13, further comprising storing a delta count of cells stored in each destination queue.

15. The method of claim 14, further comprising the transmitting the delta count to the line card unit.

16. The method of claim 15, further comprising, at the line card unit, storing an indicator of the number cells in each destination queue and tracking a respective memory control unit associated with a beginning of each destination queue.

17. A method comprising, at a first processing unit on a network device:

receiving one or more data packets having routing information,

forming a packet context from at least a portion of the header of the received packet, wherein the packet context includes at least the destination address of the received packet,

determining whether a destination queue selected from the plurality of switching memory queues can be assigned to the packet based at least on a portion of the packet context, the assigned destination queue being mapped to a destination port of the network device,

if a destination queue can be assigned to the packet based at least on the portion of the packet context then assigning the destination queue to the packet,

if a destination queue cannot be assigned to the packet based at least on the portion of the packet context then stroking the packet context associated with the packet, determining the destination queue from the stroked packet context, and assigning the destination queue determined from the stroked packet context to the packet;

storing in a first table an indication of the receipt of the one or more data packets;

dividing each of the one or more data packets into multiple cells;

managing the storage of cells in the switching memory, the switching memory having a plurality of memory control units to manage a plurality of switching memory queues implemented in the switching memory, the cells being stored contiguously in the switching memory as a function of the assigned destination queue for the associated packet; and

intermittently transmitting to a second processing unit on the network device the indication of the receipt of the one or more data packets stored in the first table.

18. The method of claim 17, wherein the indication of the receipt of the one more data packets stored in the first table includes an aggregate number of received data packets organized by the assigned destination queue.

19. The method of claim 17, further comprising clearing the indication from the first table after the indication is transmitted to the second processing unit.