Routers and methods for optimal routing table compression

• US 6,385,649 B1
• Filed: 11/06/1998
• Issued: 05/07/2002
• Est. Priority Date: 11/06/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Venkatachary, Srinivasan, King, Christopher Kevin, Draves, Richard P.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): DINH, KHANH Q
• Application Number:
  US09/188,014
• Time in Patent Office: 1,278 Days
• Field of Search: 370/392, 370/60, 709/200, 709/214, 709/224, 709/238, 709/220, 709/202, 709/247, 711/718
• US Class Current: 709/224
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for compressing a routing table involves constructing a binary tree representation of the routing table. The compression method makes three passes through the tree. In a first pass, the compression method propagates routing information down to the tree leaves. During this pass, the program assigns every leaf node in the tree an associated next hop or an inherited next hop from a higher level ancestral node. In a second pass, the compression method migrates prevalent next hops up the tree. This bottom up pass involves forming a set of next hops at a parent node by supernetting the sets of next hops A and B for a pair of child nodes corresponding to the parent node, according to the following operation:

A*B=A∪B, if A∩B=φ

A∩B, if A∩B≠φ

where A*B is a set of next hops formed at the parent node. In the third pass, the compression method eliminates redundant branches in the tree. This top down pass begins at a parent node and selects a next hop from a parent node. The method then examines a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node. If it is, the method eliminates the next hops for the child node. After the tree is restructured by the three-pass process, the compression method converts it back to a new routing table.

Claims

1. A method for compressing a routing table comprising the following steps:

constructing a binary tree representation of the routing table, the binary tree having nodes representing various routes in the routing table;

assigning next hops to the nodes;

migrating prevalent next hops up the tree according to the following operation;

3. A method as recited in claim 1, wherein the eliminating step comprises the following steps:

selecting a next hop from a closest non-empty ancestor node; and

examining a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node and if so, eliminating the next hops for the child node.

4. A routing table stored in a computer-readable medium and constructed as a result of the method as recited in claim 1.

2. A method for compressing a routing table comprising the following steps:

constructing a binary tree representation of the routing table, the binary tree having nodes representing various routes in the routing node;

assigning next hops to the nodes;

migrating prevalent next hops up the tree, the migrating comprising applying path compression to a series of single branches that begin at a first node and end at a last node, where X represents a set of next hops at the last node and Y represents a set of next hops at the first node, and migrating next hops up the tree according to the following operation;

if XIY =φ

, assign Y at first node and X at last node

if XIY =φ

, assign XIY at first node and XIY at last node

eliminating redundant branches in the tree to produce an output tree; and

converting the output tree to a new routing table.

5. A method for compressing a binary tree representation of a routing table, the binary tree having multiple nodes at multiple levels that represent various routes in the routing table wherein a parent node at one level can branch to zero, one, or two child nodes at a next lower level, some of the nodes having associated next hops, the method comprising the following steps:

normalizing the tree by creating new child nodes for parent nodes having only one child node and assigning next hops from the parent nodes to the new child nodes;

migrating prevalent next hops up the tree by supernetting, at parent nodes, sets of the next hops A and B for corresponding pairs of child nodes according to the following operation;

6. A method as recited in claim 5, wherein the normalizing, migrating, and subnetting steps are performed in three passes through the tree.

7. A method as recited in claim 5, wherein the normalizing and migrating steps are performed in a single pass through the tree.

8. A method as recited in claim 5, wherein in all event that A*B=A∩

B for an individual parent node, further comprising the step of deleting the next hops at the pair of child nodes associated with the individual parent node.

9. A method as recited in claim 5, wherein the subnetting step comprises the following steps:

selecting a next hop from a closest non-empty ancestor node; and

examining a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node and if so, eliminating the next hops for the child node.

10. A method as recited in claim 9, wherein the selecting step comprises the step of selecting a next hop that attempts to avoid changing the tree structure.

11. A method for compressing a binary tree representation of a routing table, the binary tree having multiple nodes at multiple levels that represent various routes in the routing table, wherein a parent node at one level can branch to zero or two child nodes at a next lower level, the method comprising the following steps:

migrating prevalent next hops up the tree according to the following operation;

12. A method as recited in claim 11, wherein in an event that A*B=A∩

B for an individual parent node, further comprising the step of deleting the next hops at the pair of child nodes associated with the individual parent node in advance of the eliminating step.

13. A method as recited in claim 11, wherein the eliminating step comprises the following steps:

selecting a next hop from a closest non-empty ancestor node; and

examining a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node and if so, eliminating the next hops for the child node.

14. A method as recited in claim 13, wherein the selecting step comprises the step of selecting a next hop that attempts to avoid changing the tree structure.

15. A method as recited in claim 14, further comprising the step of eliminating any redundant routes having common IP addresses.

16. A method for processing a routing table comprising the following steps:

propagating sets of popular next hops from more-specific routes to more-general routes, where more-specific routes are defined by IP addresses with more prefix bits in comparison to IP addresses for more-general routes, by migrating the popular next hops according to the following operation;

17. A method for compressing a routing table comprising the following steps:

supernetting sets of popular next hops by migrating the popular next hops according to the following operation;

18. A router comprising:

a memory to store a routing table;

a processor coupled to the memory to route messages according to routes listed in the routing table; and

a table compressor to compress the routing table stored in the memory, the table compressor constructing a binary tree representation of the routing table and assigning next hops to nodes in the tree, the table compressor migrating prevalent next hops up the tree according to the following operation;

19. A router comprising;

a memory to store a routing table;

a processor coupled to the memory to route messages according to routes listed in the routing table;

a table compressor to compress the routing table stored in the memory, the table compressor constructing a binary representation of the routing table and assigning next hops to nodes in the tree, he table compressor migrating prevalent next hops up the tree and eliminating redundant branches in the tree, the table compressor converting the tree back to a compressed routing table; and

wherein the table compressor applies a path compression technique to a series of single branches that begin at a first node and end at a last node, where X represents a set of next hops at the last node and Y represents a set of next hops at the first node, the table compressor migrating next hops up the tree according to the following operation;

if XIY=φ

, assign Y at first node and X at last node

if XIY=φ

, assign XIY at first node and XIY at last node.

20. A router as recited in claim 19, wherein the table compressor eliminates branches by selecting a next hop from a closest non-empty ancestor node and examining a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node and if so, eliminating the next hops for the child node.

21. A router comprising:

a memory to store a routing table;

a processor coupled to the memory to route messages according to routes listed in the routing table; and

a table compressor to compress the table stored in the memory, the table compressor propagating sets of popular next hops from more-specific routes to more-general routes, where more-specific routes are defined by IP addresses with more prefix bits in comparison to IP addresses for more-general routes;

the table compressor migrating the popular next hops according to the following operation;

22. A computer-readable medium comprising computer-executable instructions for performing the following steps:

normalizing the tree by creating new child nodes for parent nodes having only one child node and assigning next hops from the parent nodes to the new child nodes;

migrating prevalent next hops up the tree by supernetting, at parent nodes, sets of the next hops A and B for corresponding pairs of child nodes according to the following operation;

23. A computer-readable medium comprising computer-executable instructions for performing the following steps:

migrating prevalent next hops up the tree according to the following operation;

24. A computer-readable medium comprising computer-executable instructions for performing the following steps:

propagating sets of popular next hops from more-specific routes to more-general routes, where more-specific routes are defined by IP addresses with more prefix bits in comparison to IP addresses for more-general routes;

migrating the popular next hops according to the following operation;