Methods, systems, and computer program products for multi-path shortest-path-first computations and distance-based interface selection for VoIP traffic

• US 20070053300A1
• Filed: 10/10/2006
• Published: 03/08/2007
• Est. Priority Date: 10/01/2003
• Status: Active Grant

• Current Assignee: Genband US LLC (Ribbon Communications, Inc.)
• Original Assignee: Santera Systems LLC
• Inventors: Li, San-qi, Shei, Yen, Zhu, Rupert, Lu, David, Qian, Edward
• Granted Patent: US 7,570,594 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

Methods, systems, and computer program products for multipath Shortest-Path-First (SPF) computations and distance-based interface selection for VoIP traffic are disclosed. According to one method, a multi-path router instance associated with a plurality of network interfaces in a source IP device is provided. A cost is assigned to each of a plurality of internal segments between the multi-path router instance and the network interfaces associated with the multi-path router instance. An aggregate cost is calculated for each of a plurality of traffic paths originating at the multi-path router instance in the source IP device and extending through each of the network interfaces associated with the multi-path router instance to a destination IP device in the network. A list of IP paths is generated, and the paths in the list are ranked based on the calculated cost. Traffic is sent from the source IP device over at least one of the paths in the list. The path costs and rankings are updated in response to segment cost changes.

Claims

1. A method for obtaining a ranked list of paths to a destination IP device across a data network based on path costs, the method comprising:

(a) providing a multi-path router instance associated with a plurality of network interfaces in a source IP device;

(b) assigning a cost to each of a plurality of internal segments between the multi-path router instance and the network interfaces associated with the multi-path router instance;

(c) calculating an aggregate cost for each of a plurality of traffic paths originating at the multi-path router instance in the source IP device and extending through each of the network interfaces associated with the multi-path router instance to a destination IP device in the network;

(d) generating a list of IP paths and ranking the paths in the list based on the calculated costs;

(e) sending traffic from the source IP device over at least one of the paths in the list; and

(f) updating the path costs and rankings in response to segment cost changes.

2. The method of claim 1 wherein providing a multi-path router instance includes providing a multi-path shortest path first (SPF) router instance configured to participate in an SPF protocol.

3. The method of claim 1 wherein assigning a cost to each of a plurality of internal segments includes assigning the costs so that the aggregate costs of the traffic paths are substantially equal.

4. The method of claim 1 wherein assigning a cost to each of a plurality of internal segments includes assigning the costs to direct outgoing packets to or away from at least one of the traffic paths.

5. The method of claim 1 wherein calculating the aggregate path cost for each of a plurality of paths includes using external network path cost information stored in an Open Shortest Path First (OSPF) link state database.

6. The method of claim 1 wherein calculating the aggregate path cost for each of a plurality of paths includes using external network path cost information stored in a Traffic Engineering OSPF (TE-OSPF) link state database.

7. The method of claim 1 wherein sending traffic over at least one of the paths includes sending traffic over a lowest cost path and selecting a path with next lowest cost from the plurality of paths in the event that a failure is reported on the lowest cost path.

8. The method of claim 1 wherein sending traffic over at least one of the paths includes redistributing the traffic among available lowest cost paths using load balancing methods in the event that a failure is reported on one of a plurality of lowest cost paths.

9. The method of claim 1 comprising generating a plurality of ranked path lists using a plurality of multi-path router instances in the source IP device.

10. The method of claim 1 wherein calculating an aggregate cost for each of a plurality of network traffic paths includes assigning a shortest path first (SPF) node identifier to each of the network interfaces.

11. The method of claim 1 comprising advertising the costs of the internal segments to at least one external network device.

12. The method of claim 1 wherein the source IP device comprises at least one of a media gateway and a VoIP processing device.

13. A system for obtaining a ranked list of paths from an IP device to a destination IP device across a data network based on path costs, the system comprising:

a source IP device including;

(a) a plurality of network interfaces for sending media packets to and receiving media packets from a network;

(b) a multi-path router instance associated with the plurality of network interfaces;

(c) a plurality of internal segments between the multi-path router instance and the network interfaces, each of the network interfaces being assigned a cost; and

(d) wherein the multi-path router instance is adapted to calculate a an aggregate path cost for traffic paths to a destination IP device from the multi-path router instance, through the internal segment, through each of the network interfaces, to create a list of traffic paths to the destination IP device, to rank the paths in the list based on the costs, and to forward traffic to the destination IP device using at least one of the paths.

14. The system of claim 13 the multi-path router instance comprises a multi-path shortest path first (SPF) router instance configured to participate in a shortest path first protocol.

15. The system of claim 13 wherein each of the plurality of internal segments is assigned a cost such that the aggregate costs of the traffic paths are substantially equal.

16. The system of claim 13 wherein each of the plurality of internal segments is assigned a cost to direct outgoing packets to or away from at least one of the traffic paths.

17. The system of claim 13 wherein the multi-path router instance is adapted to use external network path cost information stored in an Open Shortest Path First (OSPF) link state database in calculating the aggregate path cost for each of the paths.

18. The system of claim 13 wherein the multi-path router instance is adapted to use external network path cost information stored in a Traffic Engineering Open Shortest Path First (TE-SPF) link state database in calculating the aggregate path cost for each of the paths.

19. The system of claim 13 wherein, in sending traffic over at least one of the paths, the multi-path router instance is adapted to send the traffic over a lowest cost path and to select a path with next lowest cost from the plurality of paths in the event that a failure is reported on the lowest cost path.

20. The system of claim 13 wherein, in sending traffic over at least one of the paths, the multi-path router instance is adapted to redistribute the traffic among available lowest cost paths using load balancing methods in the event that a failure is reported on one of a plurality of lowest cost paths.

21. The system of claim 13 comprising generating a plurality of ranked path lists using a plurality of multi-path router instances in the source IP device.

22. The system of claim 13 wherein, in calculating an aggregate cost for each of a plurality of network traffic paths, the multi-path router instance is adapted to assign a shortest path first (SPF) node identifier to each of the network interfaces.

23. The system of claim 13 wherein the multi-path router instance is adapted to advertise the costs of the internal segments to at least one external network device.

24. The system of claim 13 wherein the source IP device comprises at least one of a media gateway and a VoIP processing device.

25. A computer program product comprising computer-executable instructions embodied in a computer-readable medium for performing steps comprising:

(a) providing a multi-path router instance associated with a plurality of network interfaces in a source IP device;

(b) assigning a cost to each of a plurality of internal segments between the multi-path router instance and the network interfaces associated with the multi-path router instance;

(c) calculating an aggregate cost for each of a plurality of traffic paths originating at the multi-path router instance in the source IP device and extending through each of the network interfaces associated with the multi-path router instance to a destination IP device in the network;

(d) generating a list of IP paths and ranking the paths in the list based on the calculated costs;

(e) sending traffic from the source IP device over at least one of the paths in the list; and

(f) updating the path costs and rankings in response to segment cost changes.

26. The computer program product of claim 25 wherein providing a multi-path router instance includes providing a multi-path shortest path first (SPF) router instance configured to participate in a shortest path first protocol.

27. The computer program product of claim 25 wherein assigning a cost to each of a plurality of internal segments includes assigning the costs so that the aggregate costs of the traffic paths are substantially equal.

28. The computer program product of claim 25 wherein assigning a cost to each of a plurality of internal segments includes assigning the costs to direct outgoing packets to or away from at least one of the traffic paths.

29. The computer program product of claim 25 wherein calculating the aggregate path cost for each of a plurality of paths includes using external network path cost information stored in an Open Shortest Path First (OSPF) link state database.

30. The computer program product of claim 25 wherein calculating the aggregate path cost for each of a plurality of paths includes using external network path cost information stored in a Traffic Engineering OSPF (TE-OSPF) link state database.

31. The computer program product of claim 25 wherein sending traffic over at least one of the paths includes sending traffic over a lowest cost path and selecting a path with next lowest cost from the plurality of paths in the event that a failure is reported on the lowest cost path.

32. The computer program product of claim 25 wherein sending traffic over at least one of the paths includes redistributing the traffic among available lowest cost paths using load balancing methods in the event that a failure is reported on one of a plurality of lowest cost paths.

33. The computer program product of claim 25 comprising generating a plurality of ranked path lists using a plurality of multi-path router instances in the source IP device.

34. The computer program product of claim 25 wherein calculating an aggregate cost for each of a plurality of network traffic paths includes assigning a shortest path first (SPF) node identifier to each of the network interfaces.

35. The computer program product of claim 25 comprising advertising the costs of the internal segments to at least one external network device.

36. The computer program product of claim 25 wherein the source IP device comprises at least one of a media gateway and a VoIP processing device.