Source: http://www.google.com/patents/US7675868?dq=7,446,777
Timestamp: 2017-12-17 03:03:57
Document Index: 541528298

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US7675868 - Method and apparatus for coordinating routing parameters via a back-channel ... - Google Patents
Systems and methods are described for enabling routers to coordinate via a back-channel communication medium. The information exchanged over the back-channel is used to increase the number of paths considered for the routers during route optimization. The Decision Makers may assert routes and prefixes...http://www.google.com/patents/US7675868?utm_source=gb-gplus-sharePatent US7675868 - Method and apparatus for coordinating routing parameters via a back-channel communication medium
Publication number US7675868 B2
Application number US 12/011,120
Also published as CA2424680A1, CA2424680C, CA2637743A1, CA2637743C, EP1350363A2, EP1350363B1, US7349994, US20020075813, US20080186877, WO2002033895A2, WO2002033895A3, WO2002033896A2, WO2002033896A3, WO2002033915A1
Publication number 011120, 12011120, US 7675868 B2, US 7675868B2, US-B2-7675868, US7675868 B2, US7675868B2
Inventors Omar C. Balonado, Sean P. Finn, Mansour J. Karam, Michael A. Lloyd, Herbert S. Madan, James G. McGuire, Jose-Miguel Pulido Villaverde
Patent Citations (264), Non-Patent Citations (26), Referenced by (12), Classifications (42), Legal Events (9)
Method and apparatus for coordinating routing parameters via a back-channel communication medium
US 7675868 B2
Systems and methods are described for enabling routers to coordinate via a back-channel communication medium. The information exchanged over the back-channel is used to increase the number of paths considered for the routers during route optimization. The Decision Makers may assert routes and prefixes to the routers under their control. This may be done via a Border Gateway Protocol (BGP) feed. The Decision Makers, in turn, communicate separately with one another, in order to coordinate routing policy amongst themselves. This coordination may be performed over a back-channel, which may take the form of physical or logical connections between the Decision Makers.
1. A method of exchanging routing performance information amongst a plurality of decision makers, each decision maker controlling a distinct subset of a plurality of routers, wherein the plurality of decision makers are in communication via a mesh dedicated to exchanging routing performance information, the method comprising:
asserting a first plurality of preferred routes for a first plurality of prefixes to the subset of routers; and
concurrent with the asserting the first plurality of preferred routes, sending a first plurality of performance scores generated from performance measurements for the first plurality of routes to the plurality of decision makers via the mesh; and
routing the first plurality of prefixes through a SPAL.
receiving a second plurality of routes for a second plurality of prefixes via the mesh.
receiving a second plurality of performance scores for the second plurality of routes.
4. The method of claim 3, wherein the first and second pluralities of performance scores are included in one or more Local Preferences fields in a BGP feed.
applying penalties to each of the first and second pluralities of performance scores.
6. The method of claim 1, wherein the asserting the first plurality of preferred routes is performed via a BGP feed to the subset of routers.
7. The method of claim 1, wherein the plurality of performance scores are sent via a BGP feed to the mesh.
8. The method of claim 1, wherein the mesh is at least partially comprised of physical links between the plurality of decision makers.
9. The method of claim 1, wherein the mesh is at least partially comprised of logical links between the plurality of decision makers.
10. A method for deciding between best routes and default routes, comprising:
converting, by an RIU, measurements into scores, the measurements comprising information on performance of a plurality of routes traversing a router;
sending, by a Decision Maker, a plurality of updates to the router; and
routing, by the router, a prefix through a best available SPAL once a steady state has been achieved.
11. The method of claim 10, wherein the sending updates occurs over a tunable period of time.
12. The method of claim 10, wherein the scores are calculated from separate models for voice, video, and HTTP data.
queuing, by the router, the plurality of updates in a priority queue.
14. A method for selecting a SPAL, comprising:
polling, by a first thread, a database for changes in one or more of: per-SPAL performance, load, and coverage;
inserting, by the first thread, a prefix update in a priority queue;
accessing, by a second thread, the prefix update; and
sending, by the second thread, the prefix update to an RIU via a communication back-channel.
controlling, by a Decision Maker, the rate at which the second thread may access prefix updates.
converting, by the second thread, the prefix update to an UPDATE.
17. The method of claim 14, wherein the polling further comprises:
searching, by the first thread, for group level changes.
18. The method of claim 17, wherein the polling further comprises:
unpacking, by the first thread, the group into a plurality of prefixes.
updating, by a router, to reflect a SPAL winner set.
reevaluating the SPAL winner set at the output of the priority queue.
This patent application is a continuation of the U.S. application Ser. No. 09/960,623, filed Sep. 20, 2001, and titled “Method and Apparatus for Coordinating Routing Parameters Via a Back-Channel Communication Medium,” now U.S. Pat. No. 7,349,994, which claims the benefit of U.S. Provisional Application No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, and is a continuation-in-part of U.S. application Ser. No. 09/903,441, filed Jul. 10, 2001, now U.S. Pat. No. 7,080,161 U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, now U.S. Pat. No. 7,406,539 and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001, now U.S. Pat. No. 7,363,367 which are all hereby incorporated by reference in their entireties.
The invention includes systems and methods for enabling networking devices to coordinate via a back-channel communication medium. The information exchanged over the back-channel is used to increase the number of paths considered for the routers during route optimization.
FIG. 1-FIG. 4 illustrate different configurations of routing intelligence units and edge routers, according to some embodiments of the invention.
In some embodiments of the invention, one or more routing intelligence units are stationed at the premises of a multi-homed organization, each of which controls one or more edge routers. These devices inject BGP updates to the Edge Routers they control, based on performance data from measurements obtained locally, or from a Routing Intelligence Exchange—Routing Intelligence Exchanges are further described in U.S. Provisional Applications No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, and U.S. applications Ser. No. 09/903,441, filed Jul. 10, 2001, U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001, which are hereby incorporated by reference in their entirety. Different configurations of these routing intelligence units and edge routers are illustrated in FIGS. 1 through 4. In some embodiments illustrated in FIG. 1, one edge router 102 with multiple ISPs 104 and 106 is controlled by a single device 100. FIG. 2 illustrates embodiments in which the routing intelligence unit 200 controls multiple edge routers 202 and 204, each of which in turn links to multiple ISPs 206, 208, 210, and 212; FIG. 2 also illustrates embodiments in which routers 203 205 controlled by the routing intelligence unit 200 are not coupled to SPALs. In FIG. 3, a single routing intelligence unit 300 controls multiple edge routers 302 and 304, each of which is linked to exactly one ISP 306 and 308. In additional embodiments illustrated in FIG. 4, different routing intelligence units 400 and 402, each connected to a set of local edge routers 404, 406, 408, and 410, may coordinate their decisions. In some embodiments of the invention, the routing intelligence units comprise processes running within one or more processors housed in the edge routers. Other configurations of routing intelligence units and edge routers will be apparent to those skilled in the art.
One goal is to reach a steady state whereby prefixes are, most of the time, routed through the best available Service Provider Access Link (i.e., SPAL), that is, through the SPAL that is the best in terms of end-to-end user performance for users belonging to the address space corresponding to that prefix. To achieve this goal, the Decision Maker will send a significant amount of updates to the router (over a tunable period of time) until steady state is reached. This desirable steady state results from a mix of customer-tunable criteria, which may include but are not limited to end-to-end user measurements, load on the links, and/or cost of the links.
Current measurements of end-to-end user performance on the Internet show that fluctuations in performance are frequent. Indeed, the reasons for deterioration of performance of a prefix may include, but are not limited to the following:
The network conditions can vary along the path used by the packets that correspond to that prefix on their way to their destination.
Alternatively, the access link through which the prefix is routed can go down.
The Service Provider to which the prefix is routed can lose coverage for that prefix.
In such occurrences. the routing intelligence unit should detect the deterioration/failure, and quickly take action to alleviate its effect on the end-user.
In order to avoid swamping routers with BGP updates. in some embodiments of the invention, the maximum rate of update permitted by the routing intelligence unit is offered as, for example, a control, such as a knob that is set by the customer. The faster the rate of updates, the faster the system can react in the event of specific performance deteriorations or link failures.
A diagram showing the high-level architecture of Routing Intelligence Unit, and focused on its BGP settings is shown in FIG. 5 a. In the embodiments illustrated in FIG. 5 a, three BGP peering types may exist between a given Routing Intelligence Unit 500 and the external world: one to control the local edge router or routers 502 that this particular Routing Intelligence Unit 500 is optimizing, one to a Routing Infrastructure Exchange (RIX) 504, and one to every other Routing Intelligence Unit device with which it coordinates 506, as further described in U.S. Provisional Applications No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, U.S. applications Ser. No. 09/903,441, filed Jul. 10, 2001, U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001, which are hereby incorporated by reference in their entirety. In the diagram shown in FIG. 5 a, the three external peering types are shown as the arrows at far left (to the Edge Routers 502 and to RIX 504) and far right 506. In order for BGP updates to be propagated to the appropriate devices, some devices are configured to be route reflectors, and others as route reflector clients. In embodiments illustrated in FIG. 5 a, the Edge Routers 502 are both route reflectors, and the peer BGP stacks are clients, as indicated by the labels “r” and “c”. Similarly, in the peering between the BGP Process 506 and the BGP Stack, the BGP Process 506 is a route reflector, and the BGP Stack is a client. Note that the separation between the BGP Process 506 and BGP Stack is not required in all embodiments. However, when they are separate, the use of route reflection allows the BGP Process 506 to behave as a normal BGP implementation (as described in The Big Book of Border Gateway Protocol RFCs referenced in the Background Of The Invention). Other configurations of the devices that may be used for propagation of BGP updates will be apparent to those skilled in the art.
Embodiments of the invention also include procedures for a Decision Maker 508 to decide whether to use a prefix which arrives via coordination with the other decision makers 510 512. Some implementations avoid use of such remote routes unless they are distinctly attractive. Thus, in such embodiments, given a choice between comparable local and remote routes (wherein ‘comparable’ may mean within a winner-set width), the local route is always used. Other implementations may include:
a static penalty applied to all remote announcements
a static penalty per remote Decision Maker
a static penalty per remote SPAL
dynamic penalties per remote Decision Maker
In the following, we describe each thread separately. In the description, we will refer to tables in the database, and to fields within these tables. The contents of this database are also explicated in U.S. Provisional Applications No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, and U.S. applications Ser. No. 09/903,441, filed Jul. 10, 2001, U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001, which are hereby incorporated by reference in their entirety.
This first thread 600 polls the database for changes in terms of per-SPAL performance, load, or coverage, and decides on which prefix updates to insert in a Priority Queue that holds prefix update requests.
In some embodiments of the invention, such changes are checked for in 2 passes. The first pass looks for group level changes, wherein a group comprises an arbitrary collection of prefixes. Groups are also described in U.S. Provisional Applications No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, and U.S. applications Ser. No. 09/903,441, filed Jul. 10, 2001, U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001, which are hereby incorporated by reference in their entirety. In case a significant change in performance for a group is noticed, the group is unpacked into its individual prefixes; the corresponding prefixes are checked and considered for insertion in the priority queue. The second pass captures prefixes for which there are no group-level performance changes.
1) In case a significant change in its performance score is witnessed on at least one of its local SPALs.
2) In case a significant change in its performance score is witnessed on a foreign SPAL (that is, a SPAL that is controlled by a different Routing Intelligence Unit box in a coordinated system).
3) In case any of the local SPALs becomes invalid.
4) In case an update pertaining to this prefix was received from the router.
5) A peering with either a local or a remote router goes down, for instance, during the router's maintenance windows.
6) At the user's request.
In some embodiments of the invention, in the first pass, an asynchronous thread goes through all groups in the GROUP_SPAL table, checking whether the NEW_DATA bit is set.
This bit is set by the measurement listener in case a new measurement from a/32 resulted in an update of delay, jitter, and loss in the database. Delay, jitter, and loss, also denoted as d, v, and p, are used to compute an application-specific score, denoted by m. The scalar m. is used to rate application-specific performance; MOS stands for “Mean Opinion Score”, and represents the synthetic application-specific performance. In embodiments of the invention, MOS may be multiplied by a degradation factor that is function of link utilization, resulting in m. (That is, the larger the utilization of a given SPAL, the larger the degradation factor, and the lower the resulting m)
//First pass: only consider groups for which there is a change in
the group pref data
compute m (spal, d, v, p, spal-penalty), store in
d=alpha*d+(1−alpha)*dnew
v=beta*v+(1−beta)*vnew
p=gamma*p+(1−gamma)*pnew,
where dnew, vnew, pnew represent the new delay, jitter, and loss measurements. Algorithms for calculating MOS for HTTP (1.0 and 1.1) and for voice and video are also presented in U.S. Provisional Applications No. 60/241,450, filed Oct. 17, 2000 and U.S. Provisional Application No. 60/275,206, filed Mar. 12, 2001, and U.S. applications Ser. No. 09/903,441, filed Jul. 10, 2001, U.S. application Ser. No. 09/923,924, filed Aug. 6, 2001, and U.S. application Ser. No. 09/903,423, filed Jul. 10, 2001. Values used for the models employed by these algorithms in embodiments of the invention are presented in an XML format below. Note that since MOS is computed per group, a selection from the sets of the following parameters may be made to allow different optimization goals for each group.
<module> <engine slot= ”1”><application model= ”http1.0” [alpha=”0.9”
beta=”0.9” gamma= ”0.9” theta=”1.18” phi=”0.13” omega=”0.15”
psi=”0.25”] />
</engine> </module>
<module> <engine slot=”1”><application model=”http1.1” [alpha= ”0.9”
beta=”0.9” gamma= ”0.9” theta= ”1.3” phi=”0.31” omega=”0.41”
psi=”1 .0”] />
<module> <engine slot=”1” <application model=”voice”
[alpha=”0.9” beta=”0. 9” gamma=”0.9” theta =”1 .5” phi=”6.0”
omega=”23.0” psi=”0.0”]
/> </engine>
<module> <engine slot=”1”> <application model=”video” [alpha=”0.9”
beta=”0.9” gamma=”0.9” theta=”1 .0” phi=”4.0” omega=”69.0”
psi=”0.0”] />
In some embodiments of the invention, in the second pass, an asynchronous thread goes through all prefixes in the PREFIX table. In some such embodiments, for each prefix, Checks 2, 3, and 4 are made: NEW_INCOMING_BID in the PREFIX table indicates that a new bid was received from the coordination back channel; NEW_INVALID in the PREFIX_SPAL table indicates, for a particular (Prefix P, SPAL x) pair a loss of coverage for Prefix P over SPAL x. NEW_NATURAL_DATA indicates the receipt by Routing Intelligence Unit of an update message from a router, notifying it of a change in its natural BGP winner. In fact, the Decision Maker only asserts a performance route in case it is not the same as the natural BGP route; hence, it can potentially receive updates concerning the natural BGP winners of given prefixes from routers to which it has asserted no performance route for those prefixes. (The advantage of such an implementation is that when no performance route is sent to a router, the routing intelligence unit will get routing updates from that router. In contrast, if performances route were asserted regardless of whether they agree with the natural BGP choice, the Routing Intelligence Unit would never receive an update from the router pertaining to changes in the natural BGP winner for the different prefixes. If Routing Intelligence Unit were to assert performance routes regarding a given prefix P to all routers irrespectively of the current BGP winner for that prefix, it will never receive an update from the router pertaining to changes in the natural BGP winner for Prefix P. Indeed, the performance route would always be the winner, so the router would assume there is nothing to talk about.)
get new_bid, new_natural, and accepting_data from prefix_group
schedule_prefix (prefix) }
Prevent any use of a prefix unknown to BGP. This is achieved using the ACCEPTING_DATA check included in some embodiments of the invention.
Permit all such use, in a context where new routes cannot propagate
Permit such use, but mark any new prefix with the well-known community value no-advertise to prevent propagation
Permit such use, but configure the routers to prevent any further propagation (in some embodiments, by filtering such prefixes)
Deciding to Insert a Prefix Update Request in the Priority Queue: the Schedule_Prefix Function
First of all, a winner set of SPALs is re-computed for P; this set includes SPALs for which the performance is close to maximal.
After the winner set W is computed for P, the decision maker determines whether the current route for P is included in W.
In case of a coordinated Routing Intelligence Unit system, in some embodiments of the invention, the back channel is sent updates pertaining to Prefix P even if the local prefix update request is dropped. For example, the performance on local links could have changed dramatically since the last time a bid was sent to the back channel for this prefix; in the event of such an occurrence, an updated bid is sent to the back channel (through the BGP peering set up for this purpose).
In case the current route is not part of the newly computed winner set, it is clear that Prefix P is not routed optimally. Before going ahead and inserting an update request for Prefix P in the queue, the Routing Intelligence Unit performs a check of the flapping history for Prefix P. In case this check shows that Prefix P has an excessive tendency to flap, no prefix update request is inserted in the queue.
In some embodiments of the invention, before the prefix is inserted in the queue, a SPAL is chosen at random from the winner set. In case the winner set includes a remote SPAL controlled by a coordinated Routing Intelligence Unit as well as a local SPAL, the local SPAL is always preferred. Also, in some embodiments of the invention, the randomness may be tweaked according to factors pertaining to any one or more of the following: link bandwidth, link cost, and traffic load for a given prefix. Finally, the state in the database is updated, and the element is inserted in the Priority Queue. The rank of the prefix update in the priority queue is determined by computing the potential percent improvement obtained from moving the prefix from its current route to the pending winner route.
At the outset, a winner set of SPALs is re-computed for P; this set includes SPALs for which the performance is close to maximal. In some embodiments of the invention, invalid SPALs are excluded from the winner set computation. Bids from remote SPALs under the control of coordinated Routing Intelligence Units may, in embodiments, be included in the winner set computation. Since the bids corresponding to such remote routes are filtered through BGP, they are in units which are compatible with iBGP's LocalPref, which in some implementations is limited to 0-255. Therefore one possible implementation is to multiply m by 255. The converted quantity is referred to as MSLP. For consistency, the m values computed for local SPALs are also converted to local_pref units. The new winner is then determined to be the set of all SPALs for which MSLP is larger than MSLPmax-winner-set-threshold, where MSLPmax represents the maximum MSLP for that prefix across all available SPALs, and winner-set-threshold represents a customer-tunable threshold specified in LocalPref units. The related pseudo-code is shown below.
mark spal as invalid, not to be used in winner_set computation
valid spals and other— bid
// First, detect non-communicated withdrawal of a prefix
if (current_winner not in winner_set) && (pending_winner in winner_set)
current_route_per_router = SPAL(prefix, router, type = natural, state =
if (current_route_per router exists) && (current_route_per_router !=
if (current_route in winner_set) || (special_route==current_winner)
get bid_low_threshold and bid_high_threshold from prefix_group
if ((MSLP(prefix, current_spal) < bid_low_threshold) ||
(MSLP(prefix, current_spal) bid_high_threshold))
compute bid_low_threshold and bid_high_threshold from
MSLP (prefix)
if (new invalid)
In some embodiments of the invention, before the prefix is inserted in the queue, a SPAL is chosen at random from the winner set. This way, traffic is spread across more than one SPAL, hence achieving some level of load balancing. In order to achieve some set of desirable policies, randomness can be tweaked in order to favor some SPALs and disregard others. For example, in some embodiments, in case the winner set includes a remote SPAL controlled by a coordinated Routing Intelligence Unit as well as a local SPAL, the local SPAL is always preferred. In other words, a remote SPAL is only the winner in case it is the only available SPAL in the winner set. Also, depending on the weight of a prefix and the observed load on different links, one can tweak the probabilities in such a way that the prefix is routed through a SPAL that fits it best. (This feature corresponds to the “Saturation Avoidance Factor”—SAF, described later in this document) After a winner is selected, PENDING_WINNER in PREFIX_SPAL is updated to reflect the new potential winner. Finally, the element is inserted in the Priority Queue. In some embodiments, the rank of the prefix update in the priority queue is determined by computing the percent improvement; that is, the percent improvement obtained from moving the prefix from its current route to the pending winner route. That is, percent-improvement=[score(pending_winner)−Score(current_route)]/Score(current_route). The special-spal-flag is part of the data structure for the update, as it will be used in the determination of which messages to send to the local routers.
In this thread 602, elements are taken out of the queue in a rate-controlled manner. In some embodiments of the invention, this rate is specified by the customer. The update rate is often referred to as the token rate. Tokens are given at regular intervals, according to the update rate. Each time a token appears, the head of the queue is taken out of the queue, and considered for potential update. In case the database shows that more recent passes in Thread 1 have canceled the update request, it is dropped without losing the corresponding token; the next update request is then taken out from the head of the queue; this procedure is performed until either the queue empties, or a valid request is obtained. In some embodiments of the invention, when an update request that corresponds to Prefix P is determined to be current (thus, valid), one or more of the following tasks are performed:
The flapping state is updated for Prefix P.
The database is updated to reflect the new actual winner; more specifically, the pending winner, chosen before inserting the prefix update request at the end of the first thread now becomes the current winner.
In this thread 602, elements are just taken out from the queue in a rate-controlled manner, according to an update rate that may be set by the customer. The update rate is often referred to as the token rate: indeed, tokens are given at regular intervals, according to the update rate. Each time a token appears, the head of the queue is taken out, and considered for potential update.
In case FORGIVING_MODE (also in the PREFIX table) is set to 0, and INTERCHANGE_RATE exceeds flap_high, FORGIVING_MODE is set to 1.
In case FORGIVING_MODE is set to 1, but INTERCHANGE_RATE drops below flap_low, FORGIVING_MODE is set to 0 again, and the prefix update request survives this check.
In case FORGIVING_MODE is set to 1 and INTERCHANGE_RATE is larger than flap_low, or FORGIVING_MODE is set to 0, and INTERCHANGE_RATE is below flap_high, FORGIVING_MODE does not change.
form UPDATE to send to local SBGP
E. Technical Considerations
Configuring Routing Intelligence Unit as a Perfect Listener is desirable, as it allows the support of private peerings. For example, unless Routing Intelligence Unit is configured as a Perfect listener, when Routing Intelligence Unit hears about a prefix, it can't assume that coverage exists for that prefix across all SPALs. Considering the scenario described above, a prefix that the Routing Intelligence Unit learns about could be covered by any of the three SPALs the router is connected to. For example, assume that only SPAL 1 has coverage for a given prefix P; in case the Routing Intelligence Unit asserts a performance route for that prefix across SPAL 2, there is no guarantee that the traffic pertaining to that prefix will be transited by the Service Provider to which SPAL 2 is connected (which we denote Provider 2). In case Provider 2 actually has a private peering with Provider X that obeys to some pre-specified contract, Provider X could well monitor the traffic from Provider 2, and filter all packets that do not conform to that contract. In case this contract namely specifies that Provider X will only provide transit to customers residing on Provider X's network, then the traffic pertaining to Prefix P will be dropped. If Routing Intelligence Unit were a Perfect Listener, it would only assert performance routes for prefixes across SPALs that are determined to have coverage for these prefixes. This behavior may be referred to as “extremely polite”.
In some embodiments, the Routing Intelligence Unit is capable of avoiding the “Rocking the boat” problem, which stems from unwanted propagation of prefixes which did not already exist in BGP. The Routing intelligence Unit can operate in “impolite” mode, where any prefixes may be used, or in “polite” mode, where only those prefixes which were previously present in BGP can be used. An ANNOUNCED bit resides in the ROUTER_PREFIX_SPAL table, and is set by the Peer Manager in case the Routing Intelligence Unit hears about a prefix from any of the Routers. This bit allows use of “polite” mode by the following procedure: in case the ANNOUNCED bit is set to 0 for all (router, SPAL) combinations in the ROUTER_PREFIX_SPAL table, then ACCEPTING_DATA is set to 0 in the PREFIX table.
In some embodiments of the invention, a specific (Prefix P, SPAL x) pair is invalidated in case there are reasons to believe that SPAL x no longer provides coverage to Prefix P. One possible implementation is described as follows. Measurements corresponding to a (Prefix, SPAL) pair are assumed to arrive to the Decision Maker at something close to a predictable rate. A background thread that is independent from Threads 1 and 2 computes this update rate, and stores a time of last update, the LAST_UPDATE_TIME. Another background thread verifies that LAST_ICR_TIME is reasonable given UPDATE_RATE. For example, assuming that measurements come in following a Poisson distribution, it is easy to verify whether LAST_ICR_TIME exceeds a fixed percentile of the inter-arrival interval. As LAST_UPDATE_TIME increases, the Decision Maker becomes more and more worried about the validity of the path. In the current design, there are two thresholds: at the first threshold, the NEW_INVALID and INVALID flags are set in the PREFIX_SPAL table. As described in Thread 1 above, setting the NEW_INVALID flag for a (Prefix P, SPAL x) pair will prevent any new update requests for Prefix P to be routed through SPAL x. At this stage, no other action is taken. At the second threshold, the Decision Maker becomes “very concerned” about routing Prefix P through SPAL x; hence, an urgent check is made to see whether Prefix P is currently routed through SPAL x, in which case an urgent UPDATE is created (that is, an UPDATE that bypasses the entire queue system) in order to route Prefix through a different SPAL.
Some embodiments of the invention support a Saturation Avoidance Factor, which measures the effect of a prefix on other prefixes. In some embodiments of the invention, the “Saturation Avoidance Factor” (SAF) pertaining to a given prefix may be taken into account when prefixes are sorted in the Priority Queue. This SAF measures the effect of a prefix on other prefixes. That is, if, upon scheduling a prefix on a given link, its effect on the other prefixes already scheduled on that link is high (i.e., this effectively means that the aggregate load for this prefix is large), its SAF should be low. The lower the SAF of a prefix, the lower its place in the Priority Queue. This way, the algorithm will always favor low load prefixes rather than high load prefixes. Note that in some embodiments, the SAF is not directly proportional to load. For example, a prefix that has a load equal to 0.75 C has a different SAF whether it is considered to be scheduled on an empty link or on a link which utilization has already reached 75%. In the later case, the SAF should be as low as possible, since scheduling the prefix on the link would result in a link overflow.
1. The default mode: the user specifies one token rate (and, optionally, a bucket size), shared equally among the prefixes updates destined to the different links.
2. The enhanced performance mode: the user specifies a minimum token rate (and, optionally, a bucket size). Depending on factors such as the total bandwidth utilization and the bandwidth of individual links, the prefix scheduler takes the initiative to function at a higher speed when possible, allowing better performance when it is not dangerous to do so.
3. The custom mode: in this case, the user can specify minimum and maximum token rates (and, optionally, bucket sizes), as well as conditions on when to move from a token rate to another. Using this custom mode, customers can tailor the prefix scheduler to their exact need.
Even though the priority queue is sized in such a way that the delay spent in the queue is minimized, there is still an order of magnitude between the time scale of the BGP world, at which level decisions are taken, and the physical world, in which edge stats and interface stats are measured. That is, even though the queuing delay is comparable to other delays involved in the process of changing a route, prefix performance across a given link or the utilization of a given link can change much more quickly. For example, a 2 second queuing delay could be appropriate in the BGP world, while 2 seconds can be enough for congestion to occur across a given link, or for the link utilization to go from 25% to 75% . . . . For this reason, in some embodiments of the invention, the winner set is re-evaluated at the output of the priority queue.
US5514938 Oct 24, 1994 May 7, 1996 U.S. Philips Corporation D.C. ciruit for starting high pressure discharge lamp
US5590126 Sep 27, 1995 Dec 31, 1996 Lucent Technologies Inc. Method for call establishment and rerouting in mobile computing networks
US5652841 Jun 7, 1995 Jul 29, 1997 Nemirovsky; Paul Method and apparatus for aggregating terminals into clusters to assist in the construction of a distributed data communication network
US5659196 Apr 19, 1996 Aug 19, 1997 Mitsubishi Denki Kabushiki Kaisha Integrated circuit device for acceleration detection
US6064946 Mar 11, 1996 May 16, 2000 Koninklijke Ptt Nederland N.V. Signal quality determining device and method
US6119235 Dec 24, 1997 Sep 12, 2000 Ukiah Software, Inc. Method and apparatus for quality of service management
US6226226 Oct 2, 1997 May 1, 2001 Itt Manufacturing Enterprises, Inc. Method for vehicle data dependent range measurement from a vehicle
US6317118 Nov 9, 1998 Nov 13, 2001 Seiko Epson Corporation Remote coordinate input device and remote coordinate input method
US6341309 Dec 24, 1997 Jan 22, 2002 Novell, Inc. Firewall system for quality of service management
US6363332 Dec 22, 1998 Mar 26, 2002 Caterpillar Inc. Method and apparatus for predicting a fault condition using non-linear curve fitting techniques
US6393486 Oct 28, 1999 May 21, 2002 Cisco Technology, Inc. System and method using level three protocol information for network centric problem analysis and topology construction of actual or planned routed network
US6434606 May 28, 1999 Aug 13, 2002 3Com Corporation System for real time communication buffer management
US6438592 Feb 25, 1998 Aug 20, 2002 Michael G. Killian Systems for monitoring and improving performance on the world wide web
US6446028 Nov 25, 1998 Sep 3, 2002 Keynote Systems, Inc. Method and apparatus for measuring the performance of a network based application program
US6452950 Jan 14, 1999 Sep 17, 2002 Telefonaktiebolaget Lm Ericsson (Publ) Adaptive jitter buffering
US6453356 Apr 15, 1998 Sep 17, 2002 Adc Telecommunications, Inc. Data exchange system and method
US6549954 * Aug 23, 1999 Apr 15, 2003 Advanced Micro Devices, Inc. Object oriented on-chip messaging
US6560204 Mar 2, 1999 May 6, 2003 Telcordia Technologies, Inc. Method of estimating call level traffic intensity based on channel link measurements
US6584093 * Jan 5, 1999 Jun 24, 2003 Cisco Technology, Inc. Method and apparatus for automatic inter-domain routing of calls
US6594307 Dec 13, 1996 Jul 15, 2003 Koninklijke Kpn N.V. Device and method for signal quality determination
US6631419 Sep 22, 1999 Oct 7, 2003 Juniper Networks, Inc. Method and apparatus for high-speed longest prefix and masked prefix table search
US6633640 Feb 1, 2000 Oct 14, 2003 Avaya Technology Corp. Methods and apparatus for analysis of load-balanced multi-site call processing systems
US6658000 Sep 18, 2000 Dec 2, 2003 Aerocast.Com, Inc. Selective routing
US6661797 Feb 28, 2000 Dec 9, 2003 Lucent Technologies Inc. Quality of service based path selection for connection-oriented networks
US6687229 Nov 6, 1998 Feb 3, 2004 Lucent Technologies Inc Quality of service based path selection for connection-oriented networks
US6704795 Oct 12, 1999 Mar 9, 2004 Cisco Technology, Inc. Technique for reducing consumption of router resources after BGP restart
US6707824 May 19, 1999 Mar 16, 2004 Nortel Networks Limited Method and apparatus for flexible egress traffic queuing
US6714549 Dec 23, 1998 Mar 30, 2004 Worldcom, Inc. High resiliency network infrastructure
US6714896 Mar 11, 1999 Mar 30, 2004 British Telecommunications Public Limited Company Method and apparatus for signal degradation measurement
US6728484 Sep 7, 1999 Apr 27, 2004 Nokia Corporation Method and apparatus for providing channel provisioning in optical WDM networks
US6728777 Jun 2, 2000 Apr 27, 2004 Nortel Networks Limited Method for engineering paths for multicast traffic
US6728779 May 31, 2000 Apr 27, 2004 Lucent Technologies Inc. Method and apparatus for exchanging routing information in a packet-based data network
US6735177 Nov 16, 1999 May 11, 2004 Nec Corporation Multicast communication device and method
US6748426 Jun 15, 2000 Jun 8, 2004 Murex Securities, Ltd. System and method for linking information in a global computer network
US6751661 Jun 22, 2000 Jun 15, 2004 Applied Systems Intelligence, Inc. Method and system for providing intelligent network management
US6751664 Jul 5, 2000 Jun 15, 2004 At&T Corp. Method for monitoring and meeting customer bandwidth demand in operational IP data networks
US6757255 Jul 27, 1999 Jun 29, 2004 Fujitsu Limited Apparatus for and method of measuring communication performance
US6795399 Nov 24, 1998 Sep 21, 2004 Lucent Technologies Inc. Link capacity computation methods and apparatus for designing IP networks with performance guarantees
US6801502 May 8, 2000 Oct 5, 2004 At&T Corp. Method and apparatus for load-sensitive routing of long-lived packet flows
US6810417 Feb 19, 2002 Oct 26, 2004 Kin Man Lee Content delivery network system and method for network configuring
US6819662 Apr 28, 2000 Nov 16, 2004 Telecommunications Research Laboratories Method for protecting a telecommunications network
US6820133 Mar 24, 2000 Nov 16, 2004 Netli, Inc. System and method for high-performance delivery of web content using high-performance communications protocol between the first and second specialized intermediate nodes to optimize a measure of communications performance between the source and the destination
US6829221 Dec 27, 1999 Dec 7, 2004 Nortel Networks Limited Border gateway protocol manager and method of managing the selection of communication links
US6839745 Oct 10, 2000 Jan 4, 2005 Verizon Corporate Services Group Inc. System and method for generating reports in a telecommunication system
US6897684 Mar 4, 2003 May 24, 2005 Elpida Memory, Inc. Input buffer circuit and semiconductor memory device
US6909700 Nov 24, 1998 Jun 21, 2005 Lucent Technologies Inc. Network topology optimization methods and apparatus for designing IP networks with performance guarantees
US6912203 Jul 31, 2000 Jun 28, 2005 Cisco Technology, Inc. Method and apparatus for estimating delay and jitter between many network routers using measurements between a preferred set of routers
US6912222 Feb 24, 2000 Jun 28, 2005 Internap Network Services Corporation Private network access point router for interconnecting among internet route providers
US6920134 Dec 19, 2000 Jul 19, 2005 Telefonaktiebolaget Lm Ericsson (Publ) Method for transporting physical objects, transportation system and transportation means
US6956858 Jun 29, 2001 Oct 18, 2005 Mayan Networks Corporation Network routing table and packet routing method
US6963575 Feb 27, 2001 Nov 8, 2005 Yipes Enterprise Services, Inc. Enhanced data switching/routing for multi-regional IP over fiber network
US6981055 Aug 22, 2000 Dec 27, 2005 Internap Network Services Corporation Method and system for optimizing routing through multiple available internet route providers
US6993584 Jul 12, 2001 Jan 31, 2006 Hughes Network Systems Method and system for improving network performance by utilizing path selection, path activation, and profiles
US6999432 Jun 28, 2001 Feb 14, 2006 Microsoft Corporation Channel and quality of service adaptation for multimedia over wireless networks
US7002917 Jan 4, 2000 Feb 21, 2006 Cisco Technology, Inc. Method for path selection in a network
US7020086 Jun 29, 2001 Mar 28, 2006 Telefonaktiebolaget Lm Ericsson (Publ) Lagrange quality of service routing
US7024475 Apr 24, 2000 Apr 4, 2006 Nortel Networks Limited Performance modeling of a communications system
US7027448 Jun 7, 2001 Apr 11, 2006 At&T Corp. System and method for deriving traffic demands for a packet-switched network
US7043541 Sep 21, 2000 May 9, 2006 Cisco Technology, Inc. Method and system for providing operations, administration, and maintenance capabilities in packet over optics networks
US7043562 Jun 9, 2003 May 9, 2006 Avivi Systems, Inc. Irregular network
US7046653 * Jan 22, 2002 May 16, 2006 Jan Nigrin Diversity communication system and method of operation thereof
US7065584 Apr 28, 2000 Jun 20, 2006 Lucent Technologies Inc. Method and apparatus for network mapping using end-to-end delay measurements
US7110393 Feb 28, 2001 Sep 19, 2006 3Com Corporation System and method for providing user mobility handling in a network telephony system
US7111073 May 30, 2000 Sep 19, 2006 Cisco Technology, Inc. Apparatus for estimating delay and jitter between network routers
US7222268 * Sep 18, 2001 May 22, 2007 Enterasys Networks, Inc. System resource availability manager
US7472192 May 15, 2001 Dec 30, 2008 Arbinet-Thexchange Ltd. Communication system and method for connecting to multiple ISP's
US20010026537 Feb 23, 2001 Oct 4, 2001 Michael Massey Satellite internet backbone network system using virtual onboard switching
US20010037311 Feb 16, 2001 Nov 1, 2001 Mccoy James Efficient internet service cost recovery system and method
US20030016770 May 1, 2001 Jan 23, 2003 Francois Trans Channel equalization system and method
US20030039212 Oct 17, 2001 Feb 27, 2003 Lloyd Michael A. Method and apparatus for the assessment and optimization of network traffic
US20030112788 Dec 18, 2001 Jun 19, 2003 Erhart Wesley R. System and method for controlling media gateways that interconnect disparate networks
US20030161321 Oct 17, 2001 Aug 28, 2003 Karam Mansour J. Method and apparatus for characterizing the quality of a network path
US20030163555 Feb 28, 2001 Aug 28, 2003 Abdella Battou Multi-tiered control architecture for adaptive optical networks, and methods and apparatus therefor
US20040030776 Aug 12, 2002 Feb 12, 2004 Tippingpoint Technologies Inc., Multi-level packet screening with dynamically selected filtering criteria
US20040062267 Jun 5, 2003 Apr 1, 2004 Minami John Shigeto Gigabit Ethernet adapter supporting the iSCSI and IPSEC protocols
US20040218546 Mar 17, 2004 Nov 4, 2004 Clark Alan Douglas Per-call quality of service monitor for multimedia communications system
US20050083912 Mar 1, 2004 Apr 21, 2005 At&T Corp. Method and apparatus for functional architecture of voice-over-IP SIP network border element
US20050132060 Dec 5, 2004 Jun 16, 2005 Richard Mo Systems and methods for preventing spam and denial of service attacks in messaging, packet multimedia, and other networks
US20050201302 Mar 18, 2005 Sep 15, 2005 Wiltel Communications Group, Inc. Internet route deaggregation and route selection preferencing
US20050243726 Jul 6, 2005 Nov 3, 2005 Tactical Networks A.S. System and method for real-time buying and selling of internet protocol (IP) transit
US20060026682 Jul 29, 2005 Feb 2, 2006 Zakas Phillip H System and method of characterizing and managing electronic traffic
US20060036763 Oct 18, 2005 Feb 16, 2006 Johnson Kirk L Methods and apparatus for routing requests in a network
US20060291446 * Nov 9, 2005 Dec 28, 2006 Donald Caldwell Systems, methods, and devices for managing routing
US20070064715 Nov 20, 2006 Mar 22, 2007 Avaya, Inc. Method and apparatus for the assessment and optimization of network traffic
US20070115840 Oct 17, 2001 May 24, 2007 Feick Wayne A Method and apparatus for communicating data within measurement traffic
US20070271066 Mar 16, 2007 Nov 22, 2007 Nikitin Alexei V Method, computer program, and system for automated real-time signal analysis for detection, quantification, and prediction of signal changes
US20080089241 Nov 30, 2007 Apr 17, 2008 Lloyd Michael A Method and apparatus for the assessment and optimization of network traffic
US20080101793 Dec 17, 2007 May 1, 2008 Calix Networks, Inc. Network address association recovery
US20090006647 Jun 11, 2008 Jan 1, 2009 Balonado Omar C Method and apparatus for performance and cost optimization in an internetwork
US20090031025 Sep 26, 2008 Jan 29, 2009 Lloyd Michael A Load optimization
EP0504537A1 Mar 22, 1991 Sep 23, 1992 International Business Machines Corporation Method and apparatus for the testing and evaluation of geographically distributed telecommunication networks
EP0528075A1 Aug 19, 1991 Feb 24, 1993 ALCATEL BELL Naamloze Vennootschap Performance measurement device for a telecommunication path and method used therein
EP0598969B1 Nov 27, 1992 Feb 10, 1999 International Business Machines Corporation Inter-domain multicast routing
EP0788267A3 Dec 11, 1996 Oct 30, 2002 Sun Microsystems, Inc. User-extensible interactive network packet language
EP0942560A2 Feb 8, 1999 Sep 15, 1999 Siemens Information and Communication Networks Inc. Apparatus and method for speech transport with adaptive packet size
EP0977456A2 Jun 23, 1999 Feb 2, 2000 Nec Corporation Multiplexing system and control method therefor
EP0999674B1 Sep 14, 1999 Apr 28, 2004 Lucent Technologies Inc. Method for providing quality of service for delay sensitive traffic over IP networks
FR2806862B1 Title not available
1 "A Longest Prefix Match Search Engine for Multi-Gigabit IP Processsing", Masayoshi Kobayoshi et al., C&C Media Research Laboratories, NEC Corporation, pp. 1360-1364, Jun. 2000, IEEE.
3 Bates et al., "Multiprotocol Extensions for BGP-4", The Internet Society, Jun. 2000, pp. 1-10.
4 Berson et al, "An Architecture for Advance Reservations in the Internet," USC Information Sciences Institute, Jul. 16,1998, pp. 1-21.
5 C. Alaettinoglu et al. "Routing Policy Specification Language (RPSL)," http://quimby.gnus.org/internet-drafts-ietf-rps-rpsl-v2-00.txt, pp. 1-56, Mar. 1995.
6 D. New, "RFC 3620, The TUNNEL Profile," Oct. 2003, The Internet Society.
7 Draves et al, "Constructing Optimal IP Routing Tables," 1999 IEEE, 1-10.
8 Francis et al., "An Architecture for a Global Internet Host Distance Estimation Service," Oct. 2001, pp. 1-17.
9 Francis, Paul, et al, "An Architecture for a Global Internet Host Distance Estimation Service," 1999, pp. 210-217, IEEE.
10 Govindan et al., "An Analysis of Internet Inter-Domain Topology and Route Stability," USC Information Sciences Institute, 1997 IEEE.
11 Ingham et al., "Supporting Highly Manageable Web Services", Computer Networks and ISDN Systems 29 (1997), pp. 1405-1416.
12 Krishnamurthy et al., "On Network-Aware Clustering of Web Clients," Aug. 2000, 14 pages.
13 Kumar et al., "The MASC/BGMP Architecture for Inter-domain Multicast Routing," Sep. 1998, 12 pages.
14 Massoulie et al., "Arguments in favour of admission control for TCP flows", Jan. 1999, pp. 1-16.
15 Nick Feamster et al., "Controlling the Impact of BGP Policy Changes on IP Traffic", Nov. 6, 2001, pp. 1-18.
16 Nikolaos Skarmeas ct al., "Intelligent Routine Based on Active Patterns as the Basis for the Integration of Distributed Information Systems", Department of Computing Imperial College London, Feb. 1997, pp. 1-12.
17 Nikolaos Skarrneas et al., "Content Based Routing as the Basis for Intra-Agent Communication", Jan. 1998, Department of Computing Imperial College London.
18 Paxson, "Toward a Framework for Defining Internet Performance Metrics," http://www.isoc.org/inet96/proceedingsld3/d3 3,htm, pp. 1-20.
19 Sami Iren et al., "The Transport Layer: Tutorial and Survey", ACM Computing Surveys, vol. 31, No. 4, Dec. 1999, pp. 360-405.
20 Savage, et al., "Practical Network Support for IP Traceback", SIGCOMM, 2000, available at http://www-cse.ucsd.edu/~savage/papers/Sigcomm00.pdf, pp. 1-12.
21 Savage, et al., "Practical Network Support for IP Traceback", SIGCOMM, 2000, available at http://www-cse.ucsd.edu/˜savage/papers/Sigcomm00.pdf, pp. 1-12.
22 Traina, "BGP-4 Protocol Analysis", Cisco Systems, Networking Group, Request for comments 1774, Mar. 1995, available at http://www.faqs.org/ftp/rfc/pdf/rfc1774.txt.pdf, pp. 1-10.
23 Yasushi Saito et al., "Manageability, Availability and Performance in Porcupine: A Highly Scalable, Cluster-Based Mail Service", 17th ACM Symposium on Operating ystcrn rinciples, pp. 1-15, Dec. 1999.
24 Yositsugu, Ohmae et al, "Dividing Method for Topological Design of Corporate Communication Networks," Aug. 1, 1992, pp. 54-62, Communications, Wiley Hoboken ,NJ, US.
25 Yu, "Scalable Routing Design Principles," The Internet Society, Jul. 2000, pp. 1-26.
26 Z. Wang et al., "Resource Allocation for Elastic Traffic: Architecture and Mechanisms," Conference Proceedings Article, Apr. 1 2000, XP010376681, pp. 159-169.
US8488490 * Oct 14, 2009 Jul 16, 2013 At&T Intellectual Property I, L.P. Methods and apparatus to determine a capacity for a network layer topology
US8942138 * Jul 1, 2013 Jan 27, 2015 At&T Intellectual Property I, L.P. Methods and apparatus to determine a capacity for a network layer topology
US8976710 * Jun 22, 2012 Mar 10, 2015 Infosys Limited Methods for discovering and analyzing network topologies and devices thereof
US9503375 * Jun 30, 2011 Nov 22, 2016 F5 Networks, Inc. Methods for managing traffic in a multi-service environment and devices thereof
US20110085469 * Oct 14, 2009 Apr 14, 2011 John Klincewicz Methods and apparatus to determine a capacity for a network layer topology
US20130163471 * Jun 22, 2012 Jun 27, 2013 Infosys Limited Methods for discovering and analyzing network topologies and devices thereof
US20130287391 * Jul 1, 2013 Oct 31, 2013 At&T Intellectual Property I, L.P. Methods and apparatus to determine a capacity for a network layer topology
U.S. Classification 370/254, 709/250
International Classification H04L12/28, H04L12/26, H04L12/56, H04L12/24
Cooperative Classification H04L45/123, H04L43/0811, H04L43/0858, H04L43/0864, H04L43/0882, H04L43/087, H04L43/16, H04L45/00, H04L43/00, H04L45/04, H04L47/283, H04L43/026, H04L45/22, H04L43/0841, H04L43/0835, H04L41/5096, H04L41/508, H04L47/10, H04L47/20, H04L47/11, H04L45/50, H04L43/0817, H04L45/124
European Classification H04L47/20, H04L45/50, H04L45/123, H04L47/11, H04L41/14A, H04L45/22, H04L47/10, H04L45/00, H04L45/04, H04L47/28A, H04L43/00, H04L45/124, H04L12/26M
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BALDONADO, OMAR C.;FINN, SEAN P.;KARAM, MANSOUR J.;AND OTHERS;REEL/FRAME:020512/0233;SIGNING DATES FROM 20011109 TO 20011112
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BALDONADO, OMAR C.;FINN, SEAN P.;KARAM, MANSOUR J.;AND OTHERS;SIGNING DATES FROM 20011109 TO 20011112;REEL/FRAME:020512/0233