Router uses a single hierarchy independent routing table...

Details Router uses a single hierarchy independent routing table... Router uses a single hierarchy independent routing table...

2000-04-06

2003-12-02

Luu, Le Hien (Department: 2141)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Decentralized controlling

C709S238000, C709S242000, C370S351000

Reexamination Certificate

active

06658481

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to network processor-based devices, and more specifically to a single hierarchy independent routing table and packet routing methodology.
2. Discussion of the Prior Art
Currently, network processor-based devices that perform packet routing functions maintain multiple packet routing tables. For instance, as illustrated in
FIG. 1
, internet routers providing normal IP forwarding and External Border Gateway Protocol Next Hop Features are typically provided with router look-up tables including: 1) an External Border Gateway Protocol table
10
for controlling flow into and out of autonomous networks; and, 2) a packet forwarding table (Next Hop Feature table)
20
for listing subnet addresses
22
and subsequent “next hop” addresses
25
for all routers connected in the autonomous network. More particularly, the BGP tables
10
are maintained on all routers and include subnet addresses
12
for other routers on external networks. The BGP router function particularly, is what is seen by outside networks and is the router that connects an autonomous network to independent external networks.
FIG. 2
identifies an example network
50
comprising an autonomous network
30
and external networks
40
a,b
interconnected via routers R and network links. In operation, System A (
32
) in the autonomous network
30
is to forward a packet to a System
1
(
34
) in external network
40
a
at an ISO layer three network protocol destination address, e.g., IP address 9.1.1.1. In the forwarding path, router R
5
would perform a first lookup in its BGP Lookup table
10
(
FIG. 1
) to determine whether the path to System
1
(
34
) destination 9.1.1.1 goes through an exit router and, if so, determines the IP address of the egress interface for that exit router. In the example network of
FIG. 1
, this BGP egress interface is at address 6.9.1.1. Afterwards, the router performs a second lookup in the next hop table
20
with the IP address of the egress interface to determine the real next hop. In the example network of
FIG. 1
, this next hop address is determined as 8.2.1.1 (
25
). Thus, this forwarding packet operation requires two tables and two lookups. Once its status is ascertained, the packet is then transmitted to the router/end station indicated by the next hop lookup and the process is repeated until the packet is received by System
1
(
34
). If, for example, System
1
(at address 9.1.1.1) is moved so that it is connected to router RB instead of RC (for example, at 9.2.2.1), all router forwarding tables would then be updated to indicate RB as the next hop for System
1
.
Thus, in current router operation, both tables
10
,
20
are utilized when sending and receiving IP packets. BGP tables
10
are updated using the BGP protocol which enables routers to know the BGP structure of networks. Packet forwarding tables
20
are updated using the OSPF protocol, for example, which enables routers to understand the internal network architecture, i.e., within the autonomous network. OSPF calculates the shortest path from an IP Source Address (SA) to IP Destination Address (DA). For example, when a subnet is moved/deleted within a network, OSPF will update the new shortest path to that changed/deleted subnet if required (i.e., if associated next hop changes). This requires forwarding tables in all routers to be updated which entails deleting table entries and inserting new fields. The process of deleting and inserting new entries is not efficient. In addition, OSPF cannot account for local network structures when assembling routing table (i.e., OSPF is not aware of BGP routers).
It would be highly desirable to combine router forwarding and BGP tables into one table for more efficient processing and to have one router table that is hierarchy independent.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a hierarchy independent routing table that comprises a combination of packet forwarding (Next hop) and BGP Lookup tables into one table for more efficient processing.
It is a further object of the invention to provide a hierarchy independent routing forwarding table implemented in network processor-based routing devices for reducing routing algorithm complexity.
According to the invention, there is provided an apparatus and method for routing packets in a network comprising one or more router devices, the method comprising the steps of: determining from a packet arrived at a router device a destination address for the packet; performing a look-up in a single packet forwarding table in the device to ascertain packet forwarding information comprising a subnet address associated with the destination address, an IP address of a router interface servicing the subnet address, and an associated flag indicating whether the router is a BGP exit router; forwarding the packet to the indicated IP address when the flag value is not set and, if said flag value is set, the steps of utilizing the indicated IP address as index to perform subsequent look-ups in the single packet forwarding table to find IP address of a next hop router and associated flag value, and forwarding the packet to the indicated next hop router upon first determination that the associated flag value is not set.
Advantageously, the single packet routing table and routing method of the invention promotes hierarchy independence so that packets may be routed between autonomous and external networks.


REFERENCES:
patent: 6112248 (2000-08-01), Maciel et al.
patent: 6137781 (2000-10-01), Goto et al.
patent: 6310858 (2001-10-01), Kano et al.
patent: 6553002 (2003-04-01), Bremer et al.
patent: 6553031 (2003-04-01), Nakamura et al.
patent: 6567380 (2003-05-01), Chen

Affiliated with

Also associated with

Rating

Router uses a single hierarchy independent routing table... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Router uses a single hierarchy independent routing table..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Router uses a single hierarchy independent routing table... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3184022