Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1998-11-06
2002-05-07
Etienne, Ario (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
C709S220000, C370S392000
Reexamination Certificate
active
06385649
ABSTRACT:
TECHNICAL FIELD
This invention relates to network routers and more particularly, to methods for compressing routing tables used by the routers to route network messages.
BACKGROUND
Routers are specialized computing devices that route digital messages over a network. Routers receive messages from one location (e.g., source computer or another router) and forward them to the next destination (e.g., destination computer or another router) over the most efficient available path.
Routers use routing tables to direct message traffic over a network. Routing tables have multiple entries (e.g., thousands to tens of thousands), with each entry being an address of a destination device. For instance, in the Internet context, each entry consists of the 32-bit IP (Internet Protocol) address such as “192.56.7.48”. The IP address may also include a prefix length, such as 8, 16, or 24. The prefix lengths specify how many bits a router should consider for a next route. For instance, if the IP address “192.56.7.48” is assigned a prefix length of “16”, the router need only consider the first two bytes to determine a next route and may effectively read the IP address as “192.56.0.0”.
Associated with each entry in the routing table is a “next hop” value that indexes into a second table. The second or “next hop” table has fewer entries (e.g., 10-100 entries) to identify IP addresses of a next router or destination port in the network. For instance, the IP address “192.56.7.48/16” may have an associated next hop value of “17”, meaning that the IP address for the next router is at location 17 in the next hop table.
The router uses the routing table and next hop table to route messages most efficiently through the network. When a packet arrives at a router, the router first finds the address in the routing table that provides the closest match to the destination address. The general rule is that the IP address with the longest-matching prefix in comparison to the destination address is selected. The router then locates the next hop associated with the selected IP address and routes the packet to the next router referenced by the IP address in the next hop table indexed by the next hop. There are many different high-speed algorithms to quickly look up addresses in the routing and next hop tables.
Due to the explosive growth of content being made available on the World Wide Web, the Internet is rapidly growing to fill every corner of the world. The demands of the Internet backbone routers are commensurately increasing. Nodes are being added to the network at an extremely fast rate. It is estimated that the number of routes in the Internet backbone has been growing by 10,000 routes per year. More sophisticated and faster routers are being developed, with larger routing tables, to accommodate the increasing number of routes. To improve the speed and reliability of routers, it is desirable to reduce the size of the routing table in ways that do not harm the functionality or efficiency of the router.
Toward this end, this invention is directed to techniques for reducing the size of the routing table.
SUMMARY
This invention concerns routers and methods for compressing router tables employed in routers. The methods produce smaller, yet functionally equivalent tables.
In one implementation, a method for compressing a routing table involves constructing a binary tree representation of the routing table. The binary tree has multiple nodes, wherein parent nodes at one level branch to zero, one, or two child nodes at a next lower level. The compression method makes three passes through the tree. In a first pass, the compression method propagates routing information down to the leaf nodes of the tree (i.e., nodes that do not branch to lower children nodes). 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 the more 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=&phgr;
A∩B, if A∩B≠&phgr;
where “A*B” is the 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 the root node, and subsequently each 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 three-pass process restructures the tree, the compression method converts the free back to a new routing table.
REFERENCES:
patent: 5095480 (1992-03-01), Fenner
patent: 5490258 (1996-02-01), Fenner
patent: 5546390 (1996-08-01), Stone
patent: 5751971 (1998-05-01), Dobbins et al.
patent: 5826262 (1998-10-01), Bui et al.
patent: 5933849 (1999-08-01), Srbjic et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6192051 (2001-02-01), Lipman et al.
patent: 2 284 730 (1995-06-01), None
Draves Richard P.
King Christopher Kevin
Venkatachary Srinivasan
Dinh Khanh Quang
Etienne Ario
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Routers and methods for optimal routing table compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routers and methods for optimal routing table compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routers and methods for optimal routing table compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2900803