Scaleable route redistribution mechanism

Details Scaleable route redistribution mechanism Scaleable route redistribution mechanism

1999-06-29

2003-11-04

Etienne, Ario (Department: 2157)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Routing data updating

C709S238000, C707S793000, C707S793000

Reexamination Certificate

active

06643706

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to network routers, and, more particularly, to a method and apparatus for redistributing routing changes between routing protocols and other processes running on a router.
2. Description of the Related Art
As the amount of information carried by today's networks continues to increase, ways of improving the scaleability and efficiency of network elements becomes increasingly important. Such efficiency and scaleability is of particular importance in network elements through which large amounts of network traffic must pass. One such network element is the router, a device that directs network traffic between hosts. Routers build routing tables that contain their collected information on the paths to destinations that the router knows how to reach. Routers both announce and receive route information to and from other routers. This information goes into the router's routing table. Routers develop a hop-by-hop mechanism by keeping track of the “next hop” information that enables a data packet to find its destination through the network. A router that does not have a direct physical connection to the destination of the information being routed resorts to the local routing table and forwards the information to another router that is closer to the desired destination. This process repeats itself until the information works its way through the network to the desired destination.
A router can employ several different protocols in supporting the routing of information through the network. These routing protocols can generally be divided into interior gateway protocols (IGPs), such as the router information protocol (RIP), the interior gateway routing protocol (IGRP), the enhanced interior gateway routing protocol (EIGRP), the open shortest path first (OSPF) protocol, and the intermediate system-to-intermediate system (ISIS) protocol, within their boundaries, and interconnect via an exterior gateway protocol (EGP) such as the border gateway protocol (BGP), among other such protocols.
FIG. 1
illustrates an exemplary software architecture
100
of the prior art. Included in software architecture
100
is a router operating system
110
that supports the operation of the router (not shown) on which software architecture
100
is implemented. Software modules running on router operating system
110
include routing protocols
120
(
1
)-(N) and a routing table module
130
. Routing table module
130
includes a routing table
140
, as shown in FIG.
1
. Routing protocols
120
(
1
)-(N) include IGPs, such as RIP, IGRP, EIGRP, OSPF and ISIS, and EGPs such as BGP. In the router software architecture shown in
FIG. 1
(software architecture
100
), router operating system
110
is of a single-threaded design. As such, control passes from module to module and only one thread of execution is executed at any one time.
In such existing implementations, there exists a mechanism for the synchronous, data-driven notification of changes in the routes stored in routing table
140
. This notification is passed to processes that are enabled in router operating system
110
, and that may include processes such as one or more of routing protocols
120
(
1
)-(N), maintenance processes, monitoring processes and other processes registered for notification in the event of certain changes in routing table
140
. Because such processes are most commonly routing protocols (e.g., routing protocols
120
(
1
)-(N)), such registered processes will be referred to herein under the umbrella term “routing protocols” without loss of generality. The process of notification in response to a change in routing table
140
is referred to herein as route redistribution.
In router operating system
110
, the notification mechanism is referred to as synchronous because the notification for a change in one or more routes (a change in routing table
140
) is processed by one routing protocol before the same change notification can be delivered to another routing protocol or before another change notification for another route can be delivered. The synchronicity of this function is imposed by the single-threaded execution employed in router operating system
110
. Notification in such a system may be implemented, for example, as a function callback. This means that a calling process must wait for the subroutine call to routing table module
130
to complete before the calling process can proceed. Each process requiring notification of the change to routing table
140
must be notified by routing table module
130
prior to routing table module
130
returning from the subroutine call to the calling process.
The notification mechanism is referred to herein as being data-driven to indicate a change notification is delivered to registered processes immediately upon any routing change, such as the addition, modification or deletion of a route in routing table
140
. This presents the possibility of a situation in which the process updating the routing table (e.g., routing table module
130
) exhibits a marked slowdown in processing due to the need to generate a large number of notifications.
The synchronous, data-driven nature of the notification mechanism also raises the problem that a routing protocol must always be prepared to accept the process change notifications. This mechanism imposes a restriction on the design and implementation of routing protocols. A more flexible approach would allow a routing protocol to accept process change notifications at its discretion, rather than at the discretion of the software module that is charged with maintaining the routing table (e.g., routing table module). A solution to this dilemma is the use of buffers. However, buffering suffers from the deficiencies noted subsequently, which are tied to the need for memory allocation and the finite resources available therefor.
In router operating system
110
, change notifications are referred to herein as being selectable because a routing protocol can specify restrictions on change notifications, thereby restricting notifications of changes to those routes belonging to a specific set of one or more other routing protocols. For example, an EGP (e.g., BGP) might need to be informed of routing changes effected by an IGP (e.g., ISIS). BGP would include ISIS in the set of protocols for which BGP is to receive routing table change notifications. As the number of routing protocols is increased, the overhead of adding, modifying and deleting a route increases, particularly if a large number of the routing protocols are to receive notification of changes by a similarly large number of routing protocols. This increase in overhead is caused by the coupling between the act of making changes to routing table
140
and the need to synchronously distribute notification of that change to other of the routing protocols. As will be apparent to one of skill in the art, it is possible to restrict notifications based any number of criteria, of which restricting notifications using routing protocols is but one example.
One way to address the problems caused by this coupling is to separate the actions of updating routing table
140
and notifying routing protocols of the change. One means of effecting such a separation is through the use of buffers to hold the notifications. However, the use of buffers is not without problems. As will be appreciated by one of skill in the art, the use of buffers not only would be expected to consume memory, but in contemporary routers could be expected to consume relatively large amounts of memory (given that such routers might be expected to support over 50,000 routes in normal operation).
Another foreseeable drawback of buffers is the possibility of multiple buffering. In such a scenario, a perfect history is kept for each of the routing protocols receiving notifications of route changes in routing table
140
. Because each routing protocol keeps a copy of the change history of routing table
140
, large amounts of memory are consumed by the buffe

Affiliated with

Also associated with

Rating

Scaleable route redistribution mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scaleable route redistribution mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaleable route redistribution mechanism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3178035