Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1999-03-16
2002-05-21
Chin, Wellington (Department: 2664)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S390000, C370S401000, C370S432000, C709S223000, C709S242000
Reexamination Certificate
active
06392997
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 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 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.
Specifically, each BGP router maintains a routing table that lists all feasible paths to a particular network. 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. 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 only an optimal path to a particular network. The optimal path is advertised as a single routing metric consisting of an arbitrary unit number that specifies a degree of preference for a particular link. The BGP routing protocol is well-known and described in detail in
Re-quest 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 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).
When more than one neighbor share similar routing policies and these neighbors share a common subnetwork, “identical” update messages may be sent by a BGP router to these neighboring peers of the autonomous systems. In this context, a common sub-network (subnet) is defined as a shared medium, such as a LAN, that allows the updating router to access its neighboring peer routers through a single network interface. When the neighbors share a common subnet, a grouped-based routing arrangement may be further employed that optimizes generation of the identical routing update messages. That is, the BGP router may generate an update message for one neighbor and then replicate that message for all other neighbors in accordance with a conventional replication process.
Specifically, the router generates the actual data contained in the update message and stores that data in a memory location of the router. The router then generates a header for each neighbor receiving the update; the header includes a pointer referencing the address of the message data location in memory. The router then processes each header to construct a message for each neighbor and transmits the messages such that each neighbor receives an identical copy of the actual message data. In a large network, the technique of grouping neighboring peer routers according to common subnets substantially reduces memory and processor utilization, thereby increasing the rate of (i.e., speeding-up) routing updates.
However, an inconsistent routing situation arises if the grouped-based routing arrangement is employed with a set of neighboring peer routers that do not share a common subnet. In other words, if multiple external BGP neighbors span multiple networks, the neighbors cannot be grouped by a common subnet because a next-hop attribute of the routing update message is different for each of these neighbors. The update routing message is thus not “identical” for each neighbor even if these neighbors share identical routing policies, and use of the conventional grouping arrangement results in incorrect (or misformatted) update messages being sent to the BGP peer receivers.
Accordingly, the routing update message must be generated separately for each neighboring peer router that does not share the common subnet. Separate generation of update messages causes substantial processor and memory resource consumption at the updating router which, in turn, limits router update performance. The present invention is directed to solving this problem and, in particular, to providing a technique for efficiently generating update messages for neighboring peer routers that do not share a common subnet.
SUMMARY OF THE INVENTION
The invention comprises an improved group-based routing update technique that allows limited per neighbor customization of routing update messages generated by an interdomain router for its neighboring peer routers within autonomous systems of a computer network. The inventive technique may be employed when the neighboring peer routers share identical routing policies, but the routing update messages differ only in certain attributes with known locations and lengths. Broadly stated, appropriate values of the location and length attributes for each neighboring router are calculated and stored during a novel replication stage of the inventive technique. Before each message is transmitted, the proper location and length attributes of the message are updated with the stored values for the respective neighbor.
In accordance with the inventive technique, the interdomain router generates a routing update message comprising a message data portion and further generates a plurality of headers, each associated with a neighboring peer router. Each header contains a plurality of pointers, one of which references the beginning of the message data portion stored in a memory of the interdomain router (the message pointer) and another of which references a location (the referenced field) within the message data portion that requires customization for each neighbor (the field pointer). The header further contains an actual value to be loaded i
Barbas Charles J.
Chin Wellington
Cisco Technology Inc.
Johnston A. SIdney
Phan M.
LandOfFree
Technique for group-based routing update with limited per... 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 group-based routing update with limited per..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for group-based routing update with limited per... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2872921