Method and apparatus for coordinating routing parameters via a back-channel communication medium

• US 7,675,868 B2
• Filed: 01/23/2008
• Issued: 03/09/2010
• Est. Priority Date: 10/17/2000
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Villaverde, Jose-Miguel Pulido, Madan, Herbert S., Lloyd, Michael A., Finn, Sean P., Balonado, Omar C., McGuire, James G., Karam, Mansour J.
• Primary Examiner(s): Vu, Thong H
• Application Number:
  US12/011,120
• Publication Number:
  US 20080186877A1
• Time in Patent Office: 776 Days
• Field of Search: 370/351, 370/254, 709/242, 709/219, 709/224, 709/223, 709/250
• US Class Current: 370/254
• CPC Class Codes: H04L 41/508 based on type of value added network service under agreement
• CPC Class Codes: H04L 41/5096 wherein the managed service relates to distributed or central networked applications
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/0841 Round trip packet loss
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 : Identifying congestion
• CPC Class Codes: H04L 47/20 : Traffic policing
• CPC Class Codes: H04L 47/283 : in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

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.

Claims

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.

2. The method of claim 1, further comprising:

receiving a second plurality of routes for a second plurality of prefixes via the mesh.

3. The method of claim 2, further comprising:

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.

5. The method of claim 3, further comprising:

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.

13. The method of claim 10, further comprising:

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.

15. The method of claim 14, further comprising:

controlling, by a Decision Maker, the rate at which the second thread may access prefix updates.

16. The method of claim 14, further comprising:

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.

19. The method of claim 14, further comprising:

updating, by a router, to reflect a SPAL winner set.

20. The method of claim 19, further comprising:

reevaluating the SPAL winner set at the output of the priority queue.