Technique for reducing consumption of router resources after...

Details Technique for reducing consumption of router resources after... Technique for reducing consumption of router resources after...

1999-10-12

2004-03-09

Maung, Zarni (Department: 2154)

Electrical computers and digital processing systems: multicomput

Computer-to-computer protocol implementing

Computer-to-computer handshaking

C709S238000, C709S242000

Reexamination Certificate

active

06704795

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to computer networks and, more particularly, to the efficient deployment of router resources when rendering route selection decisions after restarts in a computer network.
BACKGROUND OF THE INVENTION
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, called a router, to extend the effective “size” of each network. Since management of a large system of interconnected computer networks can prove burdensome, small groups of computer networks may be maintained as autonomous systems or routing domains. The networks within a routing domain are typically coupled together by conventional “intradomain” routers. Yet it still may be desirable to increase the number of nodes capable of exchanging data; in this case, “interdomain” routers executing interdomain routing protocols are used to interconnect nodes of the various autonomous systems. An example of an interdomain routing protocol is the Border Gateway Protocol (BGP) which performs routing between autonomous systems by exchanging routing and reachability information among the interdomain routers of the systems. The interdomain routers configured to execute the BGP protocol, called BGP routers, maintain routing tables, transmit routing update messages and render routing selection decisions based on routing metrics.
Specifically, each BGP router maintains a routing table that lists feasible paths to a particular destination. Periodic refreshing of the routing table is generally not performed; however, BGP peer routers residing in the autonomous systems exchange routing information under certain circumstances. For example, when a BGP router initially connects to the network, the peer routers exchange the entire contents of their routing tables with that router. Thereafter when changes occur to those contents, the routers exchange only those portions of their routing tables that change in order to update their peers' tables. These update messages, which are sent in response to routing table changes, advertise routing changes with respect to a particular destination. The BGP routing protocol is well-known and described in detail in
Request for Comments
(
RFC
) 1771, by Y. Rekhter and T. Li (1995), and
Interconnections, Bridges and Routers,
by R. Pearlman, published by Addison Wesley Publishing Company, at pages 323-329 (1992), all disclosures of which are hereby incorporated by reference.
Broadly stated, a BGP router generates routing update messages for a neighboring peer router by “walking-through” the routing table and applying appropriate routing policies. A routing policy is information that enables a BGP router to rank routes according to filtering and preference (i.e., the “preferred” route). Routing updates provided by the update message allow BGP routers of the autonomous systems to construct a consistent view of the network topology. The update messages are sent using a reliable transport, such as the Transmission Control Protocol (TCP), to ensure reliable delivery. TCP is a transport protocol implemented by a transport layer of the Internet Protocol (IP) architecture; the term TCP/IP is commonly used to denote this architecture. The TCP/IP architecture is well known and described in
Computer Networks,
3
rd Edition,
by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
After the TCP transport connection is established, the neighboring BGP routers exchange various messages defined by the BGP protocol; in particular, the routers exchange conventional BGP OPEN and KEEPALIVE messages. The OPEN message sets forth parameters that allow the routers to identify themselves and to negotiate various exchange parameters, whereas the initial KEEPALIVE message transfer typically confirms acceptance of the OPEN message exchange. As used herein, the term restart denotes establishment of a reliable peer connection between the neighboring routers.
Upon a restart, the initial transfer among the BGP neighbors involves an exchange of their entire or “full” BGP routing tables. A full routing table exchange comprises the transfer of a complete set of preferred paths to each destination stored in each neighbor's BGP routing table. In addition to the routing table, each router contains a forwarding table that controls forwarding of packets to, e.g., a next hop. The routing table is used to construct the forwarding table and, as described herein, router resources are required to update those tables.
The initial transfer of the routing table is realized through the use of one or more BGP UPDATE messages. The conventional UPDATE message is generally used to advertise a current route of a neighboring router; as a result, each UPDATE message issued by a BGP neighboring router subsequent to the initial routing information exchange is an incremental update that comprises advertisement of only one or a subset of the preferred paths. The same UPDATE message format is used to exchange both the initial BGP routing table and any incremental changes to that table.
After confirming the OPEN message exchange during the restart, the KEEPALIVE message is periodically issued by a sending peer router to ensure that the receiving peer router “knows” that the sender is alive. Although a router may send KEEPALIVE messages in addition to UPDATE messages, a neighbor that has routes to advertise may send the UPDATE message in lieu of the KEEPALIVE message. Receipt of an UPDATE message by the receiving peer router is, however, an indication that the sending peer router is alive and, thus, obviates the need to send the periodic KEEPALIVE message. A hold time value (i.e., “hold-down timer”) contained in the OPEN message defines a maximum time period (e.g., number of seconds) that may elapse between receipt of successive KEEPALIVE and/or UPDATE messages by a neighbor.
Once a BGP router receives routing information via the UPDATE message, it performs a BGP route selection process to determine if the newly received route is preferred to the currently used route. That is, the router compares the newly received route to a destination (stored in the message) with the contents of its routing table by essentially “walking-through” the routing table to locate a route that has the same destination as the new route. Upon finding a match, the router applies the predetermined routing policy to determine which route is preferred by ranking the routes according to local criteria of the router. The local criteria are preferably based on predetermined preference and filtering parameters; for example, the preferred route may be determined based on the length of an autonomous system path. If the new route is preferred to the route stored in the routing table, the router completes the route selection process by updating its forwarding table with the new route and advertising that route to its neighbors, subject to the hold-down timer.
A problem with this conventional approach is that after a restart, the router may receive routing table updates to the same destination from the many different neighbors. For example, assume that router A has three neighbors N
1
-N
3
, each of which has a route to a destination D. From A's point of view, the preferred route is the route advertised (via the UPDATE message) by N
1
, the next preferred route is the route advertised by N
2
and the least preferred route is the route advertised by N
3
. However, the UPDATE messages received by A from N
1
-N
3
may arrive in various sequences. For example, a first scenario may comprise A initially receiving an UPDATE messa

Affiliated with

Also associated with

Rating

Technique for reducing consumption of router resources after... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique for reducing consumption of router resources after..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for reducing consumption of router resources after... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3256274