US5917820A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient packet forwarding arrangement for routing packets in an internetwork
Assignee: Cisco Technology Inc
•
Filing: 1996-06-10
•
Granted: 1999-06-29
•
Expires: 2016-06-10
Abstract
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.
Inventors
- 👤 Yakov Rekhter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 03:34
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/74; H04L45/745; H04L45/74591
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
170 words
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.
Claim 2
Dependent Claim
170 words
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.
Claim 3
Dependent Claim
24 words
The system of claim 1, wherein said predetermined groups of said one or more destination addresses are grouped in accordance with destination address prefixes.
Claim 4
Dependent Claim
35 words
The system of claim 2, wherein said local and remote tags are fixed-length tags having a minimal bit length to uniquely identify each of said one or more destination address prefixes stored in said TDB.
Claim 5
Dependent Claim
96 words
The system of claim 2, wherein the packet does not contain a valid tag, the system further comprising: a forwarding information database (FIDB) containing said destination address prefixes, said local and remote tags and said routing information; and a longest match algorithm configured to search said destination address prefixes of said FIDB, wherein said packet forwarder implements said longest match algorithm to search said destination address prefixes of said FIDB for a destination address carried in a network layer header of the packet and for forwarding the packet to the router identified by said routing information.
Claim 6
Dependent Claim
35 words
The system of claim 2, wherein the packet is a multicast packet, and further wherein said packet forwarder forwards the packet only when said previous hop node is a reverse path forwarding previous hop node.
Claim 7
Dependent Claim
36 words
The system of claim 5, wherein the received multicast packet contains a remote tag unique to the previous hop node, said packet forwarder executing said exact match algorithm on said TDB with said received remote tag.
Claim 8
Dependent Claim
55 words
The system of claim 5, wherein the received multicast packet does not have a valid tag and having a network layer header including network layer destination and source addresses, the packet forwarder executing said longest match algorithm on said FIDB with said source address to determine whether said previous hop router is an RPF neighbor.
Claim 9
Dependent Claim
23 words
The system of claim 1, wherein said local and remote tags are transferred in a data link layer header of the forwarded packet.
Claim 10
Dependent Claim
49 words
The system of claim 1, wherein said local and remote tags are arranged in a hierarchical tagging scheme having multiple levels of tagging corresponding to the hierarchical routing levels, wherein peer routers maintain tags associated with their routing level, reducing the number of tags that certain routers must maintain.
Claim 11
Dependent Claim
175 words
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.
Claim 12
Dependent Claim
175 words
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.
Claim 13
Dependent Claim
28 words
The method of claim 10, further comprising the step of: (e) prior to said step (b), providing said one or more local tags with the previous hop node.
Claim 14
Dependent Claim
43 words
The method of claim 11, further comprising the steps of: (d) prior to said step (c), receiving at least one of said one or more remote tags from said next hop node; and (e) updating said tag database with said received remote tags.
Claim 15
Dependent Claim
63 words
The method of claim 12, wherein the packet does not contain a valid tag, the system comprising a forwarding information database (FIDB) containing said destination address prefixes, said local and remote tags and routing information, the method further comprising the steps of: (f) searching said destination address prefixes of said FIDB with a longest match algorithm for said destination address of the packet.
Claim 16
Dependent Claim
67 words
The method of claim 10, wherein said packet is a unicast packet containing a local tag unique to the router, wherein said step (c) comprises the step of: (1) searching said next hop database for a local tag that exactly matches said local tag included in said packet; and (2) replacing said local tag in the packet with a remote tag associated with the matching local tag.
Claim 17
Dependent Claim
34 words
The method of claim 10, wherein the packet is a multicast packet, and further wherein said step (e) is performed only when the previous hop node is a reverse path forwarding previous hop node.
Claim 18
Dependent Claim
77 words
The method of claim 15, wherein said multicast packet contains a remote tag unique to the previous hop node, wherein said step (c) comprises the steps of: (1) searching said next hop database for a remote tag and MAC address that exactly matches said remote tag and an associated MAC address included in said packet; and (2) replacing said remote tag in the packet with said local tag associated with said matching remote tag in the TDB.
Claim 19
Dependent Claim
23 words
The method of claim 10, wherein said local and remote tags are transferred in a data link layer header of the forwarded packet.
Claim 20
Dependent Claim
49 words
The method of claim 10, wherein said local and remote tags are arranged in a hierarchical tagging scheme having multiple levels of tagging corresponding to the hierarchical routing levels, wherein peer routers maintain tags associated with their routing level, reducing the number of tags that certain routers must maintain.
Claim 21
Dependent Claim
171 words
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.
Claim 22
Dependent Claim
171 words
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.
References Cited (Backward Citations)
US5243342A
Cited
US5500860A
Cited
US5491692A
Cited
US5426637A
Cited
US5353283A
Cited
US5394402A
Cited
US5519704A
Cited
US5555256A
Cited
US5452294A
Cited
US5561669A
Cited
US5650993A
Cited
US5623492A
Cited
US5651002A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-06-28 | 2002-12-28 | 2003-06-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-06-28 | 2006-12-28 | 2007-06-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-06-28 | 2010-12-28 | 2011-06-29 | $7700.00 | Window Closed / Lapsed |