High speed variable length best match look-up in a switching device

A method of routing a packet through a switch comprising:

• upon receipt of the packet, extracting a key from the packet;
• forward traversing a tree by evaluating at each node a bit in the key as indicated by a bit-to-test indicator associated with each node, a value of the bit in the key located at a position indicated by the bit-to-test indicator determining a path traversed along the tree 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 tree 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.

A method of inserting a route in a route table where the route table is stored as a tree 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 tree to determine an insertion point;
• creating a new node;
• determining if the insertion point for the new node is between existing nodes in the tree;
• if so, setting a child pointer in the new node to indicate a node directly beneath the insertion point;
• storing the new node in the memory;
• and
• updating the child pointer in a node directly above the insertion point to indicate a starting address in the memory for the new node.

A router for routing packets in a packet switched network comprising:

• one or more input ports for receiving packets;
• a packet memory;
• an input switch coupled to each input port and the memory, the input switch including a transfer engine for transferring packets from an input port to the packet memory and a key extraction engine for extracting a key from each packet;
• a controller coupled to the input switch, the controller including a key look-up engine and a route memory, the route memory for storing a route table where the route table includes a tree, the key look-up engine traversing the tree to determine a best match to the key, and upon determining the best match for the key, generating notification information;
• one or more output ports;
• an output switch coupled to the controller, the packet memory and the output port for transferring packets from packet memory to an appropriate output port based on the notification information received from the controller.

A route look-up engine for locating a best match for a key in a route table, the route table including a tree stored in a memory associated with a routing device, the tree including one or more entries defining a path through a routing device for transferring a packet in a packet switched network from a source to a destination, the route look-up engine comprising:

• a stack for storing stack entries including a bit-to-test indicator and a pointer to the destination;
• and
• a look-up engine including a buffer, a bit comparison engine and a key comparison engine, the buffer for storing node information that is retrieved from the memory, the node information including a bit-to-test indicator,
• wherein responsive to receiving the key associated with a packet, the look-up engine forward traverses the tree, the bit comparison engine evaluating at each node traversed a bit in the key as indicated by a bit-to-test indicator associated with each node, a value of the bit in the key determining the path traversed along the tree, the look-up engine storing stack entries on the stack for each node traversed having an attached route, the look-up engine locating an end node having a route, the key comparison engine performing a singular key comparison for each packet routed through the routing device by comparing the key with the route, if they match, the look-up engine 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, the look-up engine traverses the tree backwards popping entries off the stack to locate a best match for the key and destination information associated therewith.

A computer program, tangibly stored on a computer-readable medium, comprising instructions for causing a computer to:

• upon receipt of a key, forward traverse a tree stored in a memory by evaluating at each node traversed a bit in the key as indicated by a bit-to-test indicator associated with each node, a value of the bit in the key determining a path traversed along the tree;
• locate an end node in the tree, the end node having a route;
• compare the route to the key;
• if they match, output destination information associated with the end node to guide a transfer of a packet through a routing device;
• and
• if they do not match, traverse the tree backwards to locate a best match for the key and destination information associated therewith.