Efficient packet forwarding arrangement for routing packets in an internetwork

• US 5,917,820 A
• Filed: 06/10/1996
• Issued: 06/29/1999
• Est. Priority Date: 06/10/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Rekhter, Yakov
• Primary Examiner(s): Jung, Min
• Application Number:
  US08/662,418
• Time in Patent Office: 1,114 Days
• Field of Search: 370/255, 370/400, 370/401, 370/402, 370/403, 370/404, 370/405, 370/408, 370/392, 370/474
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

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.

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.

2. The system of claim 1, wherein said predetermined groups of said one or more destination addresses are grouped in accordance with destination address prefixes.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. The system of claim 1, wherein said local and remote tags are transferred in a data link layer header of the forwarded packet.

9. 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.

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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. The method of claim 10, wherein said local and remote tags are transferred in a data link layer header of the forwarded packet.

18. 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.

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.