SEPARATION OF DATA AND CONTROL IN A SWITCHING DEVICE

• US 20090109975A1
• Filed: 12/31/2008
• Published: 04/30/2009
• Est. Priority Date: 12/16/1996
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: KOMPELLA, Kireeti, FERGUSON, Dennis C., OSKOUY, Rasoul Mirzazadeh, VEERAGANDHAM, Sreeram, JU, Hann-Hwan, SINDHU, Pradeep S., LIENCRES, Bjorn O., LIM, Raymond Marcelino Manese, AGARWAL, Nalini
• Granted Patent: US 8,189,605 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• 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/72 Routing based on the source address
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/1538 Cell slicing
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9042 : Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 : Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

A method and apparatus for switching a data packet between a source and destination in a network. The data packet includes a header portion and a data portion. The header portion includes routing information for the data packet. The method includes defining a data path in the router comprising a path through the router along which the data portion of the data packet travels and defining a control path comprising a path through the router along which routing information from the header portion travels. The method includes separating the data path and control path in the router such that the routing information can be separated from the data portion allowing for the separate processing of each in the router. The data portion can be stored in a global memory while routing decisions are made on the routing information in the control path.

Claims

1. A method of looking up a key associated with a packet to determine a route through a routing device comprising:

upon receipt of the key, forward traversing one or more nodes which make up a trie stored in a memory by evaluating at each node traversed one or more bits in the key as indicated by a bits-to-test indicator associated with each node, a value of the bits in the key determining a path traversed along the trie;

locating an end node in the trie, the end node having a route;

comparing the route to the key;

if they match, outputting destination information associated with the end node to guide the transfer of the packet through the routing device; and

if they do not match, traversing the trie backwards to locate a best match for the key.

2. The method of claim 1 wherein the step of forward traversing includes storing on a stack, for each node having one or more attached routes, the bits-to-test indicator and pointers to the attached mutes.

3. The method of claim 2 wherein the step of traversing the trie backwards includes:

comparing the key with the route to determine a first dissimilar bit location;

popping entries off the stack to determine when the bits-to-test indicator associated with a first node in the backward traversal is loss than or equal to the first dissimilar bit location; and

outputting destination information associated with the first node to guide the transfer of the packet through the routing device.

4. The method of claim 3 wherein the first node includes a route, the method further including calculating statistical information for each packet and storing in memory the statistical information with the route associated with each of the end node and the first node.

5. The method of claim 4 further including, transferring the statistical information along with the destination information to an output port in the routing device for transfer to a destination.

6. The method of claim 1 further including the step of prior to a forward traversal of the trie, searching a root table for a match of a predetermined number of bits in the key, the root table indexed by the predetermined number of bits where each entry includes a pointer to a start node in the trie to begin the forward traversal.

7. The method of claim 1 wherein the forward traversal of the trie includes loading node information for each node traversed in the trie until the end node is reached, the node information including a bits-to-test indicator, a plurality of child pointers and one or more attached routes.

8. The method of claim 1 where the nodes in the tree include 2ⁿ child pointers, where N is an integer greater than 1, each pointer including a bits-to-test indicator and an address in the memory where the child node is stored, the bits-to-test indicator indicating one or more bits to be tested in the key associated with a child node to which the child pointers indicate, and where the forward traversal includes testing one or more bits indicated by the bits-to-test indicator and retrieving an appropriate child pointer associated with the child node that indicates a next node in the trie to be traversed after the child node, whereby accesses to the memory are minimized in the forward traversal of the trie by loading a single pointer at each node until the end node is reached.

9. A method of routing a packet through a switch comprising:

upon receipt of the packet, extracting a key from the packet;

forward traversing a trie by evaluating at each node one or more bits in the key as indicated by a bits-to-test indicator associated with each node, values of the bits in the key located at a position indicated by the bits-to-test indicator determining a path traversed along the trie at each node;

locating an end node in the tree, the end node having a route;

comparing the route to the key;

if they match, retrieving destination information associated with the end node;

if they do not match, traversing the trie backwards to locate a best match for the key having a route and destination information associated therewith, and

routing the packet through the switch according to the destination information.

10. A method of inserting a route in a route table where the route table is stored as a trie in a memory of a routing device, the route table defining a path by which a packet is transferred through the routing device, the method comprising:

traversing the trie to determine an insertion point;

determining if the insertion point has an associated parent node and sibling node in the trie;

if so, creating a multi-node from the parent, sibling and the route including setting one or more child pointers in the multi-node to indicate a node directly beneath the insertion point;

storing the multi-node in the memory; and

updating the child pointer in a node directly above the parent node to indicate a starting address in the memory for the multi-node.

11-34. -34. (canceled)