Method for compressing route data in a router
AssigneeCisco Technology, Inc.
InventorsWilliam L. Lynch, Srihari Ramachandra Sangli
Life of this patent
Estimating the term…
Abstract
A method for a router having a routing table and a forwarding table. In an embodiment, the method includes creating an entry for use in the forwarding table, the entry corresponding to multiple entries of the routing table. The entry may correspond to a set of entries of the routing table which specify overlapping IP addresses and a same next hop router, in one example. In another example, the entry may be an aggregate entry corresponding to a set of entries of the routing table which specify the same next hop router.
Claims14
In a router, a method for representing in a forwarding table two or more entries of a routing table, the method comprising:
- comparing a destination address of a packet to entries in the forwarding table to determine a next router to which the packet is to be forwarded, said entries in the forwarding table organized as nodes of a trie;
- determining if the two or more entries of the routing table can be represented in the forwarding table using a reduced number of entries, said two or more entries of the routing table organized as nodes of the trie;
- and
- if so, representing in the forwarding table the two or more entries of the routing table using the reduced number of entries.
In a router having a routing table and a forwarding table, a method comprising:
- determining a next router to which a packet is to be forwarded, the determination based, in part, upon the forwarding table organized as a trie;
- and
- creating an entry for use in the forwarding table, said entry corresponding to multiple entries of the routing table, said multiple entries organized as part of the trie.
A router including a routing table and a forwarding table, comprising:
- a module configured to determine destination entries in a routing table, said destination entries organized as nodes of a trie;
- and
- a module for creating an entry for use in the forwarding table, said entry corresponding to multiple entries of the routing table, and organized as a node of the trie.
A router including a routing table and a forwarding table, comprising:
- a module for determining if the two or more entries of the routing table can be represented in the forwarding table using a reduced number of entries, said two or more entries organized as nodes of a trie;
- and
- a module for representing in the forwarding table the two or more entries of the routing table using the reduced number of entries said reduced number of entries organized as nodes of a trie.
A computer readable medium to represent two or more entries of a routing table of a router using a reduced number of entries in a forwarding table, the computer readable medium containing instructions which, when executed by a processor, cause the processor to perform operations comprising:
- comparing a destination address of a packet to entries in the forwarding table to determine a next router to which the packet is to be forwarded, said entries in the forwarding table organized as nodes of a trie;
- determining if the two or more entries of the routing table can be represented in the forwarding table using a reduced number of entries, said two or more entries of the routing table organized as nodes of the trie;
- and
- representing in the forwarding table the two or more entries of the routing table using the reduced number of entries.
Dependencies are inferred from the claim text.