System and method for compressing internet protocol routing tables

1. A networking device operably couplable to a first router and an autonomous system, the networking, device comprising:

a gateway operable to:

receive a first routing table from the first router;

exchange routing information with the autonomous system; and

send a first compressed routing table to the first router; and

a memory management system comprising a processor operable to:

in response to exchanging routing information, update the first routing table to create a first updated routing table; and

incrementally coalesce the first updated routing table into the first compressed routing table, wherein, in incrementally coalescing the first updated routing table, the memory management system is further operable to:

create an update node associated with a prefix received from the updated routing table;

normalize a child node associated with the update node;

determine a set of prevalent next-hops for the child node;

normalize an ancestor node associated with the update node; and

select a particular next-hop from the set of prevalent next-hops for the ancestor node, the update node, and the child node.

2. The networking device of claim 1 , wherein the first compressed routing table causes the first router to forward data in a manner that is identical to the first routing table.

3. The networking device of claim 1 , further operably couplable to a second router, wherein:

the gateway is further operable to:

receive a second routing table from the second router; and

send a second compressed routing table to the second router; and

the memory management system is further operable to:

in response to exchanging routing information, update the second routing table to create a second updated routing table; and

coalesce the second updated routing table into the second compressed routing table.

4. The networking device of claim 3 , wherein in exchanging information, the gateway is further operable to send the first routing table to the autonomous system.

5. The networking device of claim 4 , wherein the gateway uses a border gateway protocol to:

receive the first and second routing tables;

exchange routing information with the autonomous system; and

send the first and second compressed routing tables.

6. The networking device of claim 1 , wherein in coalescing the first updated routing table, the memory management system is further operable to:

compute a set of common route information from the first updated routing table;

compute a first set of unique route information from the first updated routing table; and

combine the set of common route information with the first set of unique route information together to form the first compressed routing table.

7. The networking device of claim 1 , wherein:

the processor is operable to perform computation on a plurality of processing threads; and

in coalescing the first updated routing table, the memory management system is further operable to:

place a plurality of nodes of the first updated routing table into a queue, wherein the plurality of nodes each relate to a portion of the first updated routing table that is to be updated;

select a first of the plurality of nodes from the head of the queue; and

coalesce a first tree associated with the first of the plurality of nodes into a first compressed tree by computing on a first of the plurality of processing threads.

8. The networking device of claim 7 , wherein in coalescing the first updated routing table, the memory management system is further operable to:

select a second of the plurality of nodes from the head of the queue; and

coalesce a second tree associated with the second of the plurality of nodes into a second compressed tree by computing on a second of the plurality of processing threads.

9. The networking device of claim 1 , wherein incrementally coalescing the first updated routing table is in response to an update received by the networking device.

10. The networking device of claim 1 , wherein the memory management system is further operable to coalesce the first updated routing table into a second compressed routing table, wherein the second compressed routing table:

is smaller than the first compressed routing table; and

causes the first router to forward data in a manner that is different from the first routing table.

11. A method comprising:

receiving a routing table from a router;

receiving routing information from an autonomous system;

updating the routing table with the routing information from the autonomous system;

compressing the updated routing table to eliminate redundant route information by:

creating an update node associated with a prefix received from the updated routing table;

normalizing a child node associated with the update node;

determining a set of prevalent next-hops for the child node;

normalizing an ancestor node associated with the update node; and

selecting a particular next-hop from the set of prevalent next-hops for the ancestor node, the update node, and the child node; and

sending the compressed routing table to the router.

12. The method of claim 11 , wherein compressing the updated routing table further comprises:

computing a set of common route information from the routing table;

computing a first set of unique route information from the routing table; and

combining the set of common route information with the set of unique route information together to form the compressed routing table.

13. The method of claim 11 , wherein compressing the routing table further comprises:

placing a plurality of nodes of the routing table into a queue, wherein the plurality of nodes each relate to a portion of the routing table that is to be updated;

selecting a first of the plurality of nodes from the head of the queue; and

coalescing a first tree associated with the first of the plurality of nodes into a first compressed tree by computing on a first of the plurality of processing threads in a multi-thread processor.

14. The method of claim 11 , wherein compressing the routing table further comprises incrementally making the compressed routing table.