Efficient packet forwarding arrangement for routing packets in an internetwork
First Claim
1. A packet forwarding system for efficiently forwarding a data packet through a router, the data packet received from a previous hop node and forwarded to a next hop node of an internetwork, the system comprising:
- a tag database containing, for predetermined groups of one or more destination addresses, one or more unique local tags and one or more remote tags, each remote tag being unique to another node, separate from the router, one said remote tag being unique to said next hop node;
a tag exchange protocol means for exchanging said local tags with said other nodes independently of receipt of requests therefor from said other nodes and for updating said tag database with said one or more remote tags received from said neighboring nodes; and
a tag forwarder for implementing an exact match algorithm to search said tag database for a local tag that matches a tag provided in the packet, and for forwarding the packet to the node identified by routing information associated with said matching local tag.
2 Assignments
0 Petitions
Accused Products
Abstract
An improved packet forwarding arrangement for making quick and efficient next hop determinations through the creation and exchange of router-unique tags used as an index into a novel database of route information. The improved packet forwarding system operates independently of connectionless network layer protocols currently exiting in the router, utilizing an independent tag exchange protocol to advertise the locally-unique tags to neighboring routers, and a packet data link header to carry the tags. Central to the packet forwarding system is a fast look-up tag database (TDB) containing a locally-unique tag and one or more remote tags local to neighboring routers, all of which are associated with predetermined groups of destination addresses such as destination address prefixes. The table look-up data structure of the TDB as well as the small, fixed-length tags of the present invention enable the packet forwarding system to quickly and efficiently index through the TDB to obtain the necessary information to make next hop determinations, thereby significantly reducing the overhead associated with packet forwarding. An existing forwarding information database (FIDB) modified to include the same tags is also provided for communicating with nodes not supporting the present invention.
-
Citations
19 Claims
-
1. A packet forwarding system for efficiently forwarding a data packet through a router, the data packet received from a previous hop node and forwarded to a next hop node of an internetwork, the system comprising:
-
a tag database containing, for predetermined groups of one or more destination addresses, one or more unique local tags and one or more remote tags, each remote tag being unique to another node, separate from the router, one said remote tag being unique to said next hop node; a tag exchange protocol means for exchanging said local tags with said other nodes independently of receipt of requests therefor from said other nodes and for updating said tag database with said one or more remote tags received from said neighboring nodes; and a tag forwarder for implementing an exact match algorithm to search said tag database for a local tag that matches a tag provided in the packet, and for forwarding the packet to the node identified by routing information associated with said matching local tag. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. In an internetwork having two or more local networks interconnected by one or more routers, a method for forwarding packets in a router from a previous hop node to a next hop node, comprising the steps of:
-
(a) creating a tag database containing, for predetermined groups of one or more destination addresses, one or more router-unique local tags and one or more remote tags, each remote tag being unique to another node, separate from the router, one said remote tag being unique to said next hop node; (b) providing said one or more local tars to the previous hop node independently of receipt of requests therefor from the previous hop node; (c) receiving a data packet generated by the previous hop node, the data packet including a data link layer header having one of said one or more local tags and a network layer header having source and destination addresses; (d) searching said tag database for a tag for replacing said tag in the packet; and (e) forwarding the packet to the next hop node. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. For operating a router to forward data packets, a method comprising the steps of:
-
A) providing the router with a forwarding table that includes a plurality of forwarding-table entries, each of which is identified by a respective local tag and specifies a next hop node and at least one remote tag; B) providing one or more of said local tags to a previous hop node independently of receipt of requests therefor from the previous hop node; and C) in response to the router'"'"'s receipt from the previous hop node an input data packet including a network-layer payload and a network-layer header to which is prepended a header containing an input one of said local tags; i) generating an output packet containing the network-layer payload and a network-layer header to which is prepended a field containing a remote tag specified by the forwarding-table entry that the input local tag identifies; and ii) forwarding the output packet to the next hop node specified by the forwarding-table entry that the input local tag identifies.
-
Specification