Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-09-15
2004-07-06
El-Hady, Nabil (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S239000, C709S240000, C709S242000, C709S243000
Reexamination Certificate
active
06760777
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for providing computational scalability and fault-tolerance to path-vector routing protocols in a router. The invention also relates to distribution of a Border Gateway Protocol in a highly scalable, multiple processor router.
BACKGROUND OF THE RELATED ART
In the context of internetworking, routing is the coordinated transfer of information from a source to a destination via a router. Routers with the capability to forward data packets between subnetworks are referred to as intermediate systems (ISs). Intermediate systems may be classified as inter-domain ISs, i.e., those which can communicate within routing domains, and inter-domain ISs which can communicate both within and between routing domains. A routing domain, or autonomous system, can be considered to be a part of an inter-network that is regulated under common administrative authority.
A key component of routing is determination of optimal routing paths for data packets. Thereafter a second component, which may be referred to as “switching”, comprises transporting packets through the internetwork. Determination of optimal routing paths relies on one or more routing protocols to provide and update a routing database, or route table, for each router in a network. Depending on the particular routing protocol(s) used, various metrics are involved in building the routing database. Such metrics are well known in the art.
Dynamic routing protocols may be interior or exterior with respect, to a given autonomous system (AS). Conventionally, interior routing protocols are used for routing within a routing domain or AS (intra-AS). Exterior routing protocols exchange routing information between routing domains (inter-AS). Border Gateway protocol (BGP) is a path-vector routing protocol that is widely used in internetwork routing (see, for example, RFC 1771,
A Border Gateway Protocol
4 (
BGP
-4), Y. Rekhter and T Li, 1995). BGP performs both intra-domain and inter-domain routing in networks. A primary function of BGP is to exchange routing information with other BGP systems (peers). BGP's main functions include receiving routes from BGP peers, maintaining the routes in a routing table, applying routing policy specific to the router/AS, transmitting routing updates to other BGP systems, and computing optimal routing paths based on routing metrics. Other BGP functions like maintaining routing sessions (TCP/IP), route aggregation, route flap dampening, etc, are well known in the art.
Prior art routers typically run BGP on a single processor. The computation requirements of main BGP functions increase linearly with the number of peers. BGP doesn't computationally scale well on a single CPU with an increasing number of peers. In prior art systems, accommodation of increasing numbers of peer routers relies on reconfiguring the network by the meshing of multiple separate routers. This approach has a number of drawbacks, including the requirement for considerable increases in network management. A truly scalable BGP should be able to distribute the computational load of the protocol on multiple CPUs.
Another disadvantage of running BGP on a single CPU is that it has a single point of failure. Any local failure results in peer routing sessions dying. Whenever routing sessions fail peers withdraw routes through the local router. When the routes through the local router get withdrawn from all peers, the local router essentially becomes “invisible” to the rest of the network. It no longer gets traffic directed to it for forwarding purposes. BGP running on a single CPU system is not fault-tolerant. In a fault tolerant implementation of BGP, the routing information on the local router and peer router is not lost due to a single point of failure on the local router. A single point of failure on the local router will not result in the router becoming “invisible” to the rest of the network.
As demand for Internet usage continues to expand, there is a need for highly scalable routers having the capacity to handle greatly increased data flow. Scalable routers such as those of the instant invention, are characterized as having a large number of interfaces and a large number of peers. In order to accommodate such large numbers of peers, it is necessary to provide a plurality of processors and to distribute the computational load associated with the large number of protocol peers over the plurality of processors. Running multiple instances of BGP on a multi-processor router not only allows for scalability of the router, but also provides fault-tolerance. Configuring a single router also eases network management.
In order to implement a router running a plurality of instances of BGP, the inventors of the instant application have developed a novel version of BGP, which is referred to herein as router-distributed BGP (rdBGP). Furthermore, in prior art systems and methods, BGP fault tolerance in a given router was not available, due to the fact that a single instance of BGP was running on that router. In contrast, a multi-processor, scalable router of the invention which runs a plurality of BGP instances concurrently, provides for fault tolerance of that router, as will be described herein below.
Scalable routers can also be logically partitioned into logical router entities also know as virtual routers that run independently, sharing the same physical router's resources. We shall use the terms router and virtual router interchangeably herein.
SUMMARY OF THE INVENTION
In a preferred embodiment of the present invention, in an internetwork, a method for operating a distributed path-vector routing protocol within a multi-processor router, comprising the steps of (a) running an instance of a router-distributed Border Gateway Protocol (rdBGP) on each of a plurality of processors of the multi-processor router; (b) establishing routing sessions between individual instances of rdBGP running on separate processors of the multi-processor router, and between individual ones of the instances of rdBGP and external protocol peers; (c) exchanging routing information between instances of rdBGP and the external protocol peers, wherein the instances of rdBGP learn, from the external protocol peers, routes for a plurality of destinations; (d) calculating independently, by each instance of rdBGP, a set of routes, including a best route, for each of the plurality of destinations learned from the locally handled external protocol peers; and (e) sharing route information determined with the other instances of rdBGP running on separate processors in the multi-processor router, and updating route information according to information received from the other instances of rdBGP.
In some preferred embodiments of the invention there is a further step (f) for sharing route information with the external protocol peers. Also in some preferred embodiments a routing session is established between every instance of rdBGP and every other instance of rdBGP. In still further preferred embodiments two instances of rdBGP maintain a routing session with each external protocol peer, providing fault-tolerance thereby.
In some embodiments each of the plurality of instances of rdBGP are in full-mesh communication with each other via a reliable communication mechanism. In some embodiments instances of rdBGP are dynamically assigned to the plurality of external protocol peers based on a metric selected from the group consisting of CPU usage and memory usage.
In another aspect of the present invention a multi-processor router is provided, comprising a plurality of instances of a router-distributed Border Gateway Protocol (rdBGP) executing on each of a plurality of processors, an internal fabric through which the plurality of processors may communicate, and ports through which the rdBGP instances may communicate with external routers. The router is characterized in that each instance of rdBGP establishes a routing session with an external router, learns routes from the external router, and determines a set of ro
Agarwal Puneet
Basturk Erol
Menezes Vivek
Boys Donald R.
Central Coast Patent Agency Inc.
El-Hady Nabil
Pluris, Inc.
LandOfFree
Method and apparatus for distributing and providing fault... 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 distributing and providing fault..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distributing and providing fault... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218307