Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
2000-05-31
2004-04-27
Alam, Hosain (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C709S238000, C709S241000, C370S469000, C379S221020, C714S004110
Reexamination Certificate
active
06728779
ABSTRACT:
TECHNICAL FIELD
This invention relates to packet-based data networks. More particularly, this invention relates to the exchange of routing information between routers in such a network.
BACKGROUND OF THE INVENTION
In packet-based data networks such as the Internet, routers “talk” to each other to exchange routing information. Specifically, a router will announce the path it will use to get to a particular destination to each of its peer routers. Each router will thus know the path that its peer routers will take in sending a packet to a particular destination. Routing protocols, running on the routers, are used to exchange such information between routers. A routing protocol can be an Interior Gateway Protocol (IGP) or an Exterior Gateway Protocol (EGP). An IGP is used for routing within an administrative domain such as within a corporate backbone network or within a network that is owned by one company and has a unified administrative control over how routing is done. Generally such routing is metric-based in that the goal in routing between two points within an administrative domain is to find the route with the lowest cost, where cost may, for example, be distance or some other parameter than can be assigned to a link between routers. Examples of common routing protocols used within an IGP are the Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) protocol, and the Intermediate System to Intermediate System (IS—IS) protocol. The advantageous property of such IGPs is that they are guaranteed to always achieve a stable routing within the network that is consistent with the network's configuration. The difference between the different routing protocols lies in the nature of the messages passed between routers. Since an IGP is used within a network that is owned or controlled by a single organization, no hostility exists between the owners of the routers within the network that might otherwise affect the willingness of a particular router in another network to accept traffic from a router owned by another.
An EGP is used to exchange routing information between autonomous administrative domains. Thus, border, or edge, routers that might link, for example, an autonomous AT&T network with an autonomous Sprint network, need to communicate via an EGP rather than an IGP. Unlike a single autonomous system in which routing can be metric based, routing between autonomous systems needs to be policy based. Each autonomous system may in fact want to protect itself from being used by others who are not paying for its use. Thus, one autonomous system may restrict routing through it from a competitor's system since it doesn't want such competitor's customers to use its resources, even though such routing would be the “shortest” path. EGPs, unlike metric-based IGPs, are thus policy based because autonomous systems will not always be able to agree as to the best path to a specified destination. As a result, an EGP is much more complicated to administer since it involves expressing a policy of how an administrative domain wants to interact with the rest of the world.
The Border Gateway Protocol (BGP) is currently the only interdomain routing protocol employed on the Internet (see, e.g., Y. Rekhter and T. Li, “A border gateway protocol”, RFC 1771 [BGP version 4], 1995; J. W. Stewart, BGP4
, Inter
-
Domain Routing in the Internet
, Addison-Wesley, 1998; and B. Halabi,
Internet Routing Architectures
, Cisco Press, 1997). The BGP allows each autonomous system to independently formulate its own routing policies, and it allows these policies to override distance metrics in favor of policy concerns. However, routing policies of autonomous systems can conflict with each other. Inconsistencies in routing policies can result in several problems such as the inability to find a stable routing plan. Thus, as a change at one router occurs, information is exchanged with its peers that causes a second router to change its routing and exchange information with its peer routers, etc., etc., eventually causing the first router to change its routing again, then the second and so forth. Such a protocol is said to diverge and cause persistent route oscillations. Thus, with the BGP, edge routers between autonomous systems could continue to only exchange information without ever agreeing upon a stable routing plan. Such a situation could in fact have a catastrophic effect in the global Internet resulting in improperly routed traffic, and possibly even causing “gridlock” on the Internet with the amount of routing information being transferred from router to router. The latter could slow the network down to a crawl and, in a worst case situation, cause a “meltdown” of the Internet. Further, an autonomous system on the network has no ability to determine the cause of the routing problems since it only has local information available to it. Even further, even if it did, no one autonomous system has the ability to correct oscillations caused by inconsistency of routing policies between autonomous systems.
SUMMARY OF THE INVENTION
The problems associated with the prior art are solved by the routing protocol of the present invention. This new routing protocol, referred to herein as the Simple Path Vector Protocol (SPVP), extends the BGP by adding a new attribute to the routing messages sent by an edge router to its peers in different autonomous sytems. This additional attribute is a path history which is dynamically computed at each edge router as the routing path to a particular destination is changed. This path history attribute is thus sent by a router to its peers together with the sending router's path to that destination. Protocol oscillations caused by policy conflicts produce paths whose histories contain cycles. By observing the dynamic path history that is computed at an edge router as a received routing message from a peer router that contains a history attribute is processed, a cycle can be identified in the newly computed history and associated with a policy conflict at that receiving edge router's associated autonomous system. In further accord with the present invention, the protocol automatically suppresses as a permitted path to that destination those paths whose histories contain cycles.
REFERENCES:
patent: 3988587 (1976-10-01), Shreve et al.
patent: 4656658 (1987-04-01), King
patent: 4825206 (1989-04-01), Brice, Jr. et al.
patent: 4972457 (1990-11-01), O'Sullivan
patent: 5398277 (1995-03-01), Martin, Jr. et al.
patent: 5864605 (1999-01-01), Keshav
patent: 5898826 (1999-04-01), Pierce et al.
patent: 6055492 (2000-04-01), Alexander, III et al.
patent: 6115393 (2000-09-01), Engel et al.
patent: 6453064 (2002-09-01), Aikawa et al.
patent: 6535518 (2003-03-01), Hu et al.
patent: 0817424 (1998-01-01), None
Y. Rekhter and T. Li, “A Border Gateway Protocol,” RFC 1771 ( BGP version 4), 1995.
J. W. Stewart, “Inter-Domain Routing in the Internet, ” BGP4, Addison-Wesley, 1998.
B. Halabi, “Internet Routing Architectures,” Cisco Press, 1997.
T. G. Griffin and G. T. Wilfong, “An Analysis of BGP Convergent Properties,”SIGCOM '99, 1999.
M. G. Gouda, “Elements of Network Protocol Design,” John Wiley & Sons, Inc., 1998.
Griffin, T.G. et al.,IEEE INFOCOM 2000, “A Safe Path Vector Protocol”, pp. 490-499, Mar. 26-30, 2000.
Griffin, T.G. et al.,IEEE, “Policy Disputes In Path-Vector Protocols”, pp. 21-30, 1999.
Griffin Timothy G.
Wilfong Gordon Thomas
Alam Hosain
Gurey Stephen M.
Lucent Technologies - Inc.
Wang Liang-che
LandOfFree
Method and apparatus for exchanging routing information in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for exchanging routing information in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for exchanging routing information in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3233995