Technique for selective routing updates

Details Technique for selective routing updates Technique for selective routing updates

1999-06-30

2003-05-20

Cangialosi, Salvatore (Department: 2661)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S395310

Reexamination Certificate

active

06567380

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to computer networks and, more particularly, to routing updates associated with routing protocols used 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 pre-defined 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, smaller 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 routing domains. 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 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 decisions based on routing metrics.
Each BGP router maintains a routing table (related to BGP) that lists all feasible paths to a particular network. BGP peer routers residing in the autonomous systems exchange routing information under certain circumstances. Incremental updates to the routing table are generally performed. For example, when a BGP router initially connects to the network, the peer routers may exchange the entire contents of their routing tables. 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, represent incremental updates that advertise only an optimal path to a particular network or that withdraw its reachability to the network. 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. Perlman, 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 an adjacency or neighbor peer router by “walking-through” the routing table, identifying changes 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 “optimal route”). Routing updates provided by the update message allows BGP routers of the autonomous systems to construct a consistent view of the network topology. The update messages are typically 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).
Generation of a routing update message by a router in accordance with a conventional update process may involve the following steps: (1) identifying a route in the routing table that has changed; (2) applying a per-neighbor route filtering policy, if appropriate; and (3) formating an update message, if appropriate. There is typically one or more paths associated with each route entry of the routing table; update message generation is concerned with the best path from among these paths. An entry version number is typically maintained for each route entry and used for incremental update operations. A routing table version number is also maintained and used to indicate a “level” of the routing table. The table version number is incremented each time there is a change to the routing table. Moreover each time there is a change to an entry in the routing table, such as when the entry is added or deleted or when there is a best path change, the table version number is incremented and the entry version number is set to that incremented value.
In addition, a neighbor version number may be maintained in a neighbor data structure for each neighbor to indicate whether the neighbor is up-to-date with all route changes in the routing table. For example, the neighbor version number may be compared with the entry version numbers and a route may be eligible for further consideration of routing updates to the neighbor if its entry version number is greater than the neighbor version number. The neighbor version number is set to the table version number after all entries in the route table have been evaluated (and advertised if necessary) for the neighbor.
In certain situations, however, routing updates are not necessary for a neighbor having a neighbor version number that is less than an entry version number.
FIG. 1
is a schematic block diagram of a conventional computer network
100
comprising a plurality of autonomous systems AS
1-3
configured to exchange routing information with (i.e., maintain) a plurality of “external” neighboring peer routers residing in the autonomous systems. Specifically, AS
1-2
maintains external peers B
2
-B
3
and B
2
′-B
3
′, while AS
2-3
maintains external peers B
4
-B
5
.
Assume that AS
1
advertises different multi-exit discriminator (MED) values MED
1
, MED
2
to AS
2
over B
2
-B
3
and B
2
′-B
3
′, respectively, for a particular route X. A MED value is an optional non-transitive attribute of an update message. The MED value is used by an updating BGP “sender” in, e.g., AS
1
, to discriminate among multiple exit points to a BGP “receiver” in a neighboring autonomous system, such as AS
2
. Further assume a path (i.e., the greater MED value) is initially advertised as a best path for route X by AS
1
to AS
2
, and AS
2
advertises that path to AS
3
. A preferred path (i.e., the lesser MED value) is subsequently advertised as the best path for X by AS
1
to AS
2
. AS
2
transitions the best path to this preferred path and increments the entry version number for route X. As a result, an update message for route X may be sent to AS
3
. This update message is considered a duplicate by AS
3
because (from its point of view) there is no change for route X. Since the generation and transmission of routing update messages by the sender as well as the processing of these messages by the receiver consume resources, it would be advantageous to provide a technique that avoids generation of such unnecessary routing updates.
SUMMARY OF THE INVENTION
The invention comprises a technique that allows selective generation of routing update messages by a router for its neighboring peer routers of a computer network. Broadly stated, when an entry version number of a route is incremented, the reason (i.e., “what has changed”) for the change in the best path of the route is identified and recorded. That is, each time there is a new version of a route, attributes of the best path for the new version and the previous version of the route are compared and the changes are recorded. According to the selective routing update technique, recordation of the reason is effected using change flags. These flags, along with the characte

Affiliated with

Also associated with

Rating

Technique for selective routing updates 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 selective routing updates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for selective routing updates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3038822