Granted Patent B1

US 7,903,666 · App. 12/101,026 · Granted Mar 8, 2011

Assignee: Extreme Networks, Inc.

Abstract

Claims (42)

1. A method, comprising:

maintaining route entries of a route table as nodes in a routing tree;

compressing child nodes in the routing tree that have a common gateway with their respective parent nodes, wherein the compressing includes

determining the nodes that have a equal-cost multi-path (ECMP), and

compressing a child node for which a number of equal-cost multi-paths (ECMPs) matches with the number of ECMPs of a respective parent node and a set of gateways of the child node matches with the set of gateways of the respective parent node; and

installing the route entries associated with uncompressed nodes into a forwarding table of a routing device that employs longest prefix match (LPM) lookup to forward data packets.

2. The method of claim 1 , wherein each route entry comprises an Internet Protocol (IP) prefix and a gateway.

3. The method of claim 1 , wherein the forwarding table is stored in one of a content-addressable memory (CAM), ternary content-addressable memory (TCAM), random access memory (RAM), dynamic RAM (DRAM), static RAM (SRAM) or a flash memory on the routing device.

4. The method of claim 1 , wherein the route table is stored in a route manager database.

5. The method of claim 1 , wherein the route table is implemented in a control plane and the forwarding table is implemented in a data plane.

6. The method of claim 1 , wherein the routing tree is one or more of a radix tree, a Patricia tree, or a trie.

7. A method for compressing route entries in a route table where the route entries are maintained as nodes in a routing tree, the method comprising:

for each current node

compressing the current node if the current node has a parent node with a same gateway;

determining whether the current node has any child nodes; for each child node

compressing the child node if the child node is uncompressed and the child node and the current node have the same gateway, wherein the compressing includes

determining the nodes that have a equal-cost multi-path (ECMP), and

compressing a child node for which a number of equal-cost multi-paths (ECMPs) matches with the number of ECMPs of a respective parent node and a set of gateways of the child node matches with the set of gateways of the respective parent node;

uncompressing the child node if the child node is compressed and the child node and the current node have different gateways; and

installing the route entries associated with uncompressed nodes into a forwarding table of a routing device.

8. The method of claim 7 , wherein the routing tree is one or more of a radix tree, a Patricia tree, or a trie.

9. The method of claim 7 , wherein each route entry comprises an Internet Protocol (IP) prefix and a gateway.

10. A non-transitory computer-readable medium having content stored thereon to provide instructions to result in an electronic device performing operations including:

maintaining route entries of a route table as nodes in a routing tree;

compressing child nodes that have a common gateway with their respective parent nodes, wherein the compressing includes

determining if the nodes have a equal-cost multi-path (ECMP), and

compressing a child node with ECMP for which a number of equal-cost multi-paths (ECMPs) matches with the number of ECMPs of a respective parent node and a set of gateways of the child node matches with the set of gateways of the respective parent node; and

installing the route entries associated with uncompressed nodes into a forwarding table of a routing device that employs longest prefix match (LPM) lookup to forward data packets.

11. The non-transitory computer-readable medium of claim 10 , wherein each route entry comprises an Internet Protocol (IP) prefix and a gateway.

12. The non-transitory computer-readable medium of claim 10 , wherein the route table is stored in a route manager database.

13. The non-transitory computer-readable medium of claim 10 , wherein the route table is implemented in a control plane and the forwarding table is implemented in a data plane.

14. The non-transitory computer-readable medium of claim 10 , wherein the routing tree is one or more of a radix tree, a Patricia tree, or a trie.

15. A system comprising:

a ternary content-addressable memory (TCAM) to store a forwarding table associated with a routing device;

means for maintaining route entries of a route table as nodes in a routing tree;

means for compressing child nodes that have a common gateway with their respective parent nodes, wherein the means for compressing includes

means for determining if the nodes have a equal-cost multi-path (ECMP), and

means for compressing a child node with ECMP for which a number of equal-cost multi-paths (ECMPs) matches with the number of ECMPs of a respective parent node and a set of gateways of the child node matches with the set of gateways of the respective parent node; and

means for installing the route entries associated with uncompressed nodes into a forwarding table of a routing device that employs longest prefix match (LPM) lookup to forward data packets.

16. The system of claim 15 , wherein each route entry comprises an Internet Protocol (IP) prefix and a gateway.

17. The system of claim 15 , further comprising a route manager database to store the route table.

18. The system of claim 15 , wherein the routing tree is one or more of a radix tree, a Patricia tree, or a trie.

Assignments (10)

Continuity (1)