Router uses a single hierarchy independent routing table that includes a flag to look-up a series of next hop routers for routing packets

• US 6,658,481 B1
• Filed: 04/06/2000
• Issued: 12/02/2003
• Est. Priority Date: 04/06/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Vaidhyanathan, Natarajan, Basso, Claude, Gallo, Anthony Matteo
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US09/544,312
• Time in Patent Office: 1,335 Days
• Field of Search: 709/238, 709/239, 709/242, 709/243, 709/244, 370/238, 370/392, 370/235, 370/254, 370/255, 370/351
• US Class Current: 709/243
• 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/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

In a network processor-based device, there is provided a single routing table for network routers and an efficient routing algorithm implemented by the routing device. The routing table includes packet forwarding information including a subnet address associated with a destination address location, an ISO layer three (3) network protocol address, e.g., IP address, of a router interface that can route packets to the subnet address, and an identifier indicating whether that router is an exit BGP router that may or may not be directly attached to the packet forwarding router. A table look-up mechanism is provided to determine next hop information and determine associated BGP status of the next hop. At such time it is determined that a router is not a BGP router (i.e., is directly attached to the forwarding router), the packet will be transmitted to that router.

Claims

1. A method for routing packets in a network comprising one or more router devices, said method comprising the steps of:

(a) determining a destination address for a packet to be forwarded;

(b) performing a look-up in a single packet forwarding table in a router device to ascertain packet forwarding information associated with the destination address, said packet forwarding information including a layer three network protocol address of a router interface servicing said subnet address, and an associated flag indicating whether said interface is a BGP exit router interface that may or may not be directly attached to said routing device;

(c) forwarding said packet to said indicated layer three protocol address when said flag value is not set and, if said flag value is set, the steps of;

(d) utilizing said indicated exit next hop layer three network protocol address as an index into said forwarding table to perform a look-up in said single packet forwarding table to find a next hop router and associated flag value, and forwarding said packet to said indicated next hop when said flag value is not set, and otherwise repeating step (d) until said associated flag is not set, wherein at such time said packet is routed to said next hop router.

2. The method according to claim 1, wherein step (a) further includes the step of parsing said packet header for determining said destination address.

3. The method according to claim 1, wherein step (a) further includes the optional step of determining whether said destination address is a valid address.

4. The method according to claim 1, wherein said layer three network protocol includes one of IP, IPx, or CLNP.

5. A network processor device for transmitting data packets in a network, each data packet including a packet header with a destination address location for said packet, said network processor device comprising:

a single packet forwarding table for determining packet forwarding information relating to a destination subnet address of a packet to be forwarded, said packet forwarding information including a layer three network protocol address of a router interface servicing the destination subnet address, and an identifier indicating whether said interface is an exit BGP router interface;

mechanism for performing table look-up operation to identify said next hop router associated with said packet, said mechanism initiating transmission of said packet to a next hop router at said layer three network protocol address if said identifier indicates said next hop router is not an exit router and, if said next hop router indicated in said table is an exit router interface, said mechanism further utilizing said indicated layer three network protocol address of a router interface as an index to perform a subsequent table look-up in said single packet forwarding table to find associated next hop routers, and forwarding said packet to said indicated next hop router upon first determination that said indicated router is not an exit router.

6. The network processor device according to claim 5, wherein said network processor device includes a router.