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

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.

Description

RELATED APPLICATIONS
• This application is a continuation-in-part of U.S. patent application Ser. No. 10/943,513 filed Sep. 17, 2004 (pending), which is a continuation-in-part of U.S. patent application Ser. No. 10/676,233, filed Oct. 1, 2003 (pending), and which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/526,126 filed Dec. 1, 2003 and U.S. Provisional Patent Application Ser. No. 60/551,814 filed Mar. 10, 2004.
• This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/748,749 filed Dec. 9, 2005.
• This application is related to U.S. patent application Ser. No. 10/943,275 filed Sep. 17, 2004 (now U.S. Pat. No. 6,956,820).
• The disclosure of each of the above-referenced documents is incorporated herein by reference in its entirety.
TECHNICAL FIELD
• The subject matter described herein relates to providing voice over IP (VoIP) traffic engineering and path resilience. More particularly, the subject matter described herein relates to methods, systems, and computer program products for multi-path shortest-path-first (SPF) computations and distance-based interface selection for VoIP traffic.
BACKGROUND
• IP routing protocols use SPF methods to compute and select the shortest path to a network destination. IP routing protocols that use SPF methods have conventionally implemented path cost calculations assuming that each network device is a single node. In these networks, all potential paths between the source and destination IP devices are identified through network topology information provided by network devices through link state advertisement (LSA) or similar status messages. Costs are assigned to each network segment by a network administrator to reflect relative geographic distance, equipment cost, or other network attributes as deemed appropriate by the administrator. Conventionally, assigned cost values are constrained to be zero or positive, and cost metrics have relative meaning only.
• One SPF algorithm conventionally calculates an aggregate sum of the network segment costs for each of a set of predefined paths from a source IP device to a destination IP device, and the path with the lowest cost is selected by the source IP device for data transfers. Multiple paths having the same aggregate cost may be utilized by the source IP device in a load-sharing configuration where the total data traffic is distributed across all paths. The path lists generated by conventional SPF calculations do not permit an IP device to autonomously identify alternate paths to a destination IP device for the purposes of either distributing data traffic for load-balancing or for redirecting traffic under a segment or IP device failure in the data network. If an IP device experiences traffic load demands beyond the capacity of the preferred path identified by the SPF calculation, the excess traffic is discarded. Likewise, if a network node or segment in the lowest cost path fails, the IP device cannot autonomously redirect its data traffic. Until new path definitions are provided by other network nodes through link state advertisement messages, data traffic flows are interrupted and requests for establishment of new VoIP call connections are rejected due to blockage.
• One published protocol commonly used in public data networks, called Open Shortest Path First (OSPF), utilizes the basic SPF algorithm and methods. OSPF is defined to support general purpose unidirectional data traffic, such as file or webpage retrieval from a remote server. However, the OSPF definitions do not include methods to pre-assign alternate paths, nor do they include methods for data traffic recovery under node or segment failures along the preferred path. Similarly, the OSPF definitions do not include methods to constrain data traffic assignment among a group of equal low-cost paths in a load-balancing application.
• OSPF has been extended to support modified segment cost definitions to support real-time traffic. This modified algorithm, called Traffic Engineering OSPF (TE-OSPF), continues to utilize the fundamental SPF calculation method. Applications that require interactive or low-latency data transfers between two IP devices, such as VoIP or interactive video services, typically have predefined levels of service quality to meet. These service quality levels are conventionally defined in terms of data throughput rates, maximum path delay, and percent availability, and these levels are commonly defined such that the service cannot tolerate data flow interruptions. However, the TE-OSPF definitions, like the OSPF definitions, do not support definitions of pre-assigned alternate paths for rapid network failure recovery or provide mechanisms to constrain load balancing among multiple lowest-cost paths. Systems supporting low-latency or interactive data traffic are consequently limited in their ability to implement the functions often required to support the defined service quality levels.
• Accordingly, in light of these difficulties associated with obtaining a ranked list of paths to a destination IP device across a data network based on path costs, there exists a need for improved methods, systems, and computer program products for multi-path SPF computations and distance-based interface selection for VoIP traffic.
SUMMARY
• 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.
• As used herein, the term “IP device” refers to any system that has at least one interface to a data network, supports conventional data network routing protocols, and accepts data traffic in conventional formats. An IP device may be a conventional router or it may be a conventional endpoint, such as a media gateway or a server. The term “source IP device” refers to an IP device serving as the origin of data traffic to be carried across the data network. The term “destination IP device” refers to an IP device serving as the destination or termination point in the data network for the data traffic. The term “node” refers to any system in the data network that is capable of routing data traffic and supporting SPF cost assignments and calculations. The term “segment” refers to a physical connection between adjacent network nodes. The terms “data path” or “path” refers to a defined set of segments and nodes that jointly provide a connection across a data network between an IP device sourcing data traffic and an IP device sinking or terminating data traffic.
• The subject matter described herein for multi-path SPF computations and distance-based interface selection for VoIP traffic may be implemented using a computer program product comprising computer executable instructions embodied in a computer-readable medium. Exemplary computer-readable media suitable for implementing the subject matter described herein include chip memory devices, disk memory devices, programmable logic devices, application specific integrated circuits, and downloadable electrical signals. In addition, a computer-readable medium that implements the subject matter described herein may be distributed across multiple physical devices and/or computing platforms.
BRIEF DESCRIPTION OF THE DRAWINGS
• Preferred embodiments of the subject matter described herein will now be explained with reference to the accompanying drawings of which:
• FIG. 1 is a flow chart of an exemplary process for obtaining a ranked list of paths from a source IP device to a destination IP device across a data network using a SPF calculation according to an embodiment of the subject matter described herein;
• FIG. 2 is a block diagram of an exemplary data network containing an IP device with one multi-path router instance, a conventional IP device, and multiple data network segments and nodes between the two devices according to an embodiment of the subject matter described herein;
• FIG. 3 is a block diagram of an exemplary data network containing an IP device with two multi-path router instances, two conventional IP devices, and multiple data network segments and nodes between the two devices according to an embodiment of the subject matter described herein;
• FIG. 4 is a block diagram of an exemplary data network containing two IP devices, each with one multi-path router instance, and multiple data network segments and nodes between the two devices according to an embodiment of the subject matter described herein; and
• FIG. 5 is a block diagram of an exemplary media gateway containing a control module, VoIP host resources, a switch fabric, two internal multi-path router instances with associated cost tables, and multiple network interfaces according to an embodiment of the subject matter described herein.
DETAILED DESCRIPTION
• In view of the problems described above with respect to obtaining a ranked list of paths from a source IP device to a destination IP device across a data network using SPF calculations, the subject matter described herein provides a method to obtain a ranked list of paths to a destination IP device across a data network based on path costs.
• FIG. 1 illustrates anexemplary process100 for obtaining a ranked list of paths from a source IP device to a destination IP device across a data network. This process may be implemented by at least one multi-path router instance in an IP device having a plurality of network interfaces. The multi-path router instance may utilize a published routing protocol based on SPF algorithms, such as OSPF or TE-OSPF. The multi-path router instance may execute the SPF algorithm multiple times to obtain multiple paths to a destination through the network interfaces.
• InFIG. 1, atblock102 the multi-path router instance in an IP device may assign a SPF node identifier to each of a plurality of network interfaces under its control. This node identifier may be of any format meaningful to the host IP device and the multi-path router instance.
• Atblock104, the multi-path router instance may assign a cost to the segment between each network interface and the IP device resource hosting the multi-path router instance. This cost may be defined by the multi-path router instance, or it may be assigned by the host system. For example, if a diagnostic task running on the IP device determines that a network interface requires maintenance, the IP device may present a request to the multi-path router instance to change the cost for the segment between the multi-path router instance and the network interface. This permits the multi-path router instance to gracefully shift data traffic from the network interface before the diagnostic task disables the interface for maintenance operations. Once the system diagnostic has completed its work on the network interface, the IP device may then provide a request to the multi-path router instance to return the segment cost to its original value in order to re-enable data traffic on that interface.
• Once the interior segment costs have been assigned, the multi-path router instance in the IP device may advertise these costs to adjacent SPF network nodes. For example, an IP device with multiple network interfaces to an adjacent network router may advertise the interior segment costs in order to assist the router with data path selection for traffic terminating at the IP device. These costs may be transmitted to the adjacent network node(s) using conventional link state advertisement (LSA) messages.
• Atblock106, the SPF may calculate the total path cost for each network path originating at the multi-path router instance. The assigned and available network paths may be maintained in a link state database (LSDB) created and maintained by the multi-path router instance based on network topology information received from neighboring IP devices. The network path calculations may start at the network interface, using the cost assigned to the interior segment atblock106 as the first cost in the summation.
• Atblock108, the multi-path router instance may create and maintain a list of all available network paths to IP destinations to which the host IP device has traffic flow assignments. This list may be ranked in order of calculated path cost, with the most preferred path to a destination IP device being the path with lowest aggregate cost. This list may be maintained by the multi-path router instance separate from the LSDB in order to ensure that the multi-path router instance has the opportunity to filter incoming LSA messages from adjacent network nodes for applicable network topology definition changes before recalculating and potentially changing the ranks of the network path definitions.
• The multi-path router instance may also analyze the ranked path list before enabling data traffic on the preferred path. For example, the multi-path router instance may define the preferred path(s) as being the path(s) having the lowest aggregate cost. The multi-path router instance may also cross-check the definition of the preferred path(s) against the contents of the LSDB to ensure that the defined preferred path(s) are available for use. In the even that the methods atblock108 identify multiple paths with the same preferred cost, the multi-path router instance may further constrain assignment of data traffic along those paths in order to achieve a level of performance desired by an application.
• Atdecision point110, the multi-path router instance may query the host IP device to determine if changes to the interior segment cost assignments are required. The host IP device may need to modify these assignments for a variety of reasons, including system maintenance operations or network interface reconfiguration requirements. If a change to segment costs is required, the multi-path router instance may implement the change and then transition to block104 in order to recalculate all network path costs and generate new path rank lists. If no change is required, the process may proceed todecision point112.
• Atdecision point112, the multi-path router instance may receive at least one LSA message from adjacent nodes to analyze for any network topology or network segment cost changes. Each LSA message may have a format defined for conventional SPF protocols including OSPF or TE-OSPF. If the multi-path router instance determines that a network topology change has occurred that impacts its LSDB, the multi-path router instance may update its LSDB and the process may transition to block106 in order to recalculate all network path costs. If the LSA message does not provide updated network topology information, the process may transition todecision point110 to monitor for any interior segment changes required by the host IP device.
• Exemplary IP Device with Single Multi-Path Router Instance
• In one implementation, an IP device, such as a media gateway, may include a single multi-path router instance that executes a path cost calculation algorithm, multiple times to calculate path costs to a destination through a plurality of network interface in the IP device.FIG. 2 illustrates anexemplary data network200 with anIP device202 having plural network interface and a single multi-path router instance according to an embodiment of the subject matter described herein, aconventional IP device204,multiple network routers206,208, and210, and a plurality ofnetwork segments212,214,216,218,220, and222.IP device1202,IP device2204, as well asrouters RT1206,RT2208, andRT3210 may all configured with instances of a SPF algorithm such as OSPF or TE-OSPF. For example,data network200 may be present in a campus or customer premise gateway application to provide access to the public Internet.
• InFIG. 2,IP device1202 may further include amulti-path router instance224,multiple network interfaces226,228, and230, multipleinterior segments232,234, and236, and a path cost table238.IP device2204 may be a conventional IP device serving as an end node indata network200.
• IP device1202 andIP device2204 may define application data traffic flows using conventional data communication protocol methods including IP source and destination addresses, TCP or UDP addresses, and Real-Time Transport Protocol (RTP) addresses used for VoIP traffic.IP device1202,IP device2204,RT1206,RT2208, andRT3210 may each maintain network topology information in a LSDB and may update their respective LSDBs upon receipt of LSAs as defined according to conventional implementations of the SPF protocol.
• IP device1202 may assign SPF node identities to networkinterface A226,network interface B228, andnetwork interface C230.IP device1302 or the operator ofIP device1202 may assign SPF costs tointerior segments232,234, and236. These costs may be defined by system management resources withinIP device1 through interaction withmulti-path router instance224, and may be keyed to constrain data traffic flows through specific network interfaces withinIP device1202. Once assigned, these costs may also be advertised to adjacentnetwork devices RT1206,RT2208, andRT3210 using conventional LSA messages. The network path definitions and associated path costs to each destination IP device may also be stored bymulti-path router instance224 in the path cost table238.
• In an exemplary application, a network administrator may assign the following costs todata network segments212,214,216,218,220, and222, as indicated inFIG. 2, using methods associated with conventional SPF protocols:
• • Cost(212)=5; Cost(214)=10; Cost(216)=8;
  • Cost(218)=12; Cost(220)=3; Cost(222)=18
    Multi-path router instance224 may then derive three parallel network path definitions and cost models costs to destination IP device2204 as follows:$\mathrm{Path}A\text{:}\mathrm{network}\mathrm{interface}A226\colon\colon \mathrm{RT}1206\colon\colon \mathrm{IP}\mathrm{device}2204$$\mathrm{Path}B\text{:}\mathrm{network}\mathrm{interface}B228\colon\colon \mathrm{RT}2208\colon\colon \mathrm{IP}\mathrm{device}2204$$\mathrm{Path}C\text{:}\mathrm{network}\mathrm{interface}C230\colon\colon \mathrm{RT}3210\colon\colon \mathrm{IP}\mathrm{device}2204$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}A\right)=\mathrm{Cost}\left(232\right)+\mathrm{Cost}\left(212\right)+\mathrm{Cost}\left(218\right)\\ =\mathrm{Cost}\left(232\right)+5+12\\ =\underset{\_}{\mathrm{Cost}\left(232\right)+17}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}B\right)=\mathrm{Cost}\left(234\right)+\mathrm{Cost}\left(214\right)+\mathrm{Cost}\left(220\right)\\ =\mathrm{Cost}\left(234\right)+10+3\\ =\underset{\_}{\mathrm{Cost}\left(234\right)+13}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}C\right)=\mathrm{Cost}\left(236\right)+\mathrm{Cost}\left(216\right)+\mathrm{Cost}\left(222\right)\\ =\mathrm{Cost}\left(236\right)+8+18\\ =\underset{\_}{\mathrm{Cost}\left(236\right)+26}\end{array}$
• In a second exemplary application with the above exemplary network segment costs,multi-path router instance224 may set costs forinterior segments232,234, and236 so that all three network paths betweenmulti-path router instance224 andIP device2204 have equal cost. This configuration may permitIP device1202 to distribute the aggregate data traffic destined forIP device2204 among the three paths in a load sharing configuration. In order to achieve this configuration,multi-path router instance224 may assign the following values to the interior segment cost parameters:
• • Cost(232)=9; Cost (Path A)=26
  • Cost(234)=13; Cost (Path B)=26
  • Cost(236)=0; Cost (Path C)=26
• In a third exemplary application of with the above exemplary network segment costs,multi-path router instance224 may be required by other resources withinIP device1202 to establish a prioritized rank of network interface or path utilization without changing assigned costs for externaldata network segments212,214,216,218,220, and222. For example, an autonomous system management function withinIP device1202 (not shown) may determine thatnetwork interface C230 has become overloaded and can no longer carry the same level of traffic as before.Multi-path router instance224 may assign the following cost parameters in order to favor use ofnetwork interface A226 first, followed bynetwork interface B228, and then reservenetwork interface C230 for sparing or overflow traffic only:
• • Cost (232)=20; Cost (Path A)=37
  • Cost (234)=35; Cost (Path B)=48
  • Cost (236)=100; Cost (Path C)=126
• Exemplary IP Device with Plural Multi-Path Router Instances
• In the example illustrated inFIG. 2,IP device202 includes a singlemulti-path router instance224. In an alternate implementation, an IP device, such as a media gateway, may include plural multi-path router instances, at least one of which executes a path cost calculation algorithm multiple times to calculate path costs to a destination through a plurality of network interface in the IP device.FIG. 3 illustrates anexemplary data network300 with anIP device302 having plural multi-path router instances according to an embodiment of the subject matter described herein, twoconventional IP devices304 and306, a plurality ofnetwork devices308,310,312, and314, and a plurality ofnetwork segments316,318,320,322,324,326,328,330,332, and334.IP device1302,IP device2304,IP device3306, as well asrouters RT1308,RT2310,RT3312, andRT4314 may be configured with instances of a SPF algorithm such as OSPF or TE-OSPF. For example,data network300 may be a VoIP network to provide IP telephony service to VoIP subscribers.
• InFIG. 3,IP device1 may include twomulti-path router instances336 and338, fivenetwork interfaces340,342,344,346, and348, fiveinterior segments350,352,354,356, and358, and path cost tables360 and362.IP device2304 andIP device306 may be conventional IP devices serving as end nodes indata network300.
• IP device1302,IP device2304, andIP device306 may define application data traffic flows using conventional data communication protocol methods including IP source and destination addresses, TCP or UDP addresses, and RTP addresses for VoIP traffic.IP device1302,IP device2304,IP device3306,RT1308,RT2310,RT3312, andRT4314 may each maintain network topology information in a LSDB and may update their respective LSDBs upon receipt of LSAs as defined according to conventional implementations of the SPF protocol.
• IP device1302 may assign SPF node identities to networkinterface A340,network interface B342,network interface C344,network interface D346,network interface E348.IP device1302 or the operator ofIP device1302 may assign SPF costs tointerior segments350,352,354,356, and358. These costs may be defined by system management resources withinIP device1302 through interaction with multi-pathrouter instances SPF1336 andSPF2338, and may be keyed to constrain data traffic flows through specific network interfaces withinIP device1302. Once assigned, these costs may be advertised to adjacentnetwork devices RT1308,RT2310,RT3312, andRT4314 using conventional LSA messages.Multi-path router instance1336 may maintain a LSDB and path calculations fornetwork interface A340,network interface B342, andnetwork interface C344, and may store its network path definitions and associated path costs to each destination IP device in the path cost table360.Multi-path router instance2338 may maintain a LSDB and path calculations fornetwork interface D346 andnetwork interface E348, and may store its network path definitions associated path costs to each destination IP device in the path table362.IP device1302 may collect the LSDB and path calculation information frommulti-path router instance1336 andmulti-path router instance2338 and create a combined LSDB and path table for the overall device.
• In an exemplary application, a network administrator may assign the following costs todata network segments316,318,320,322,324,326,328,330,332, and334, as indicated inFIG. 3, using methods associated with conventional SPF protocols:
• • Cost(316)=50; Cost(318)=64; Cost(320)=39;
  • Cost(322)=70; Cost(324)=83; Cost(326)=23;
  • Cost(328)=58; Cost(330)=28; Cost(332)=35;
  • Cost(334)=18;
    Multi-path router instance1336 may derive three parallel network path definitions and costs to destination IP device2304 as follows:$\mathrm{Path}A\text{:}\mathrm{network}\mathrm{interface}A340\colon\colon \mathrm{RT}1308\colon\colon \mathrm{IP}\mathrm{device}2304$$\mathrm{Path}B\text{:}\mathrm{network}\mathrm{interface}B342\colon\colon \mathrm{RT}2310\colon\colon \mathrm{IP}\mathrm{device}2304$$\mathrm{Path}C\text{:}\mathrm{network}\mathrm{interface}C344\colon\colon \mathrm{RT}3312\colon\colon \mathrm{IP}\mathrm{device}2304$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}A\right)=\mathrm{Cost}\left(350\right)+\mathrm{Cost}\left(316\right)+\mathrm{Cost}\left(326\right)\\ =\mathrm{Cost}\left(350\right)+50+23\\ =\underset{\_}{\mathrm{Cost}\left(350\right)+73}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}B\right)=\mathrm{Cost}\left(352\right)+\mathrm{Cost}\left(318\right)+\mathrm{Cost}\left(328\right)\\ =\mathrm{Cost}\left(352\right)+64+58\\ =\underset{\_}{\mathrm{Cost}\left(352\right)+122}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}C\right)=\mathrm{Cost}\left(354\right)+\mathrm{Cost}\left(320\right)+\mathrm{Cost}\left(330\right)\\ =\mathrm{Cost}\left(354\right)+39+28\\ =\underset{\_}{\mathrm{Cost}\left(354\right)+67}\end{array}$
• Multi-path router instance1336 may also derive a single, non-redundant network path definition and cost model todestination IP device3306 using conventional SPF protocols as follows:$\mathrm{Path}D\text{:}\mathrm{network}\mathrm{interface}C344\colon\colon \mathrm{RT}3312\colon\colon \mathrm{IP}\mathrm{device}3306$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}D\right)=\mathrm{Cost}\left(354\right)+\mathrm{Cost}\left(320\right)+\mathrm{Cost}\left(332\right)\\ =\mathrm{Cost}\left(354\right)+39+35\\ =\underset{\_}{\mathrm{Cost}\left(354\right)+74}\end{array}$
• Multi-path router instance2338 may derive two parallel network path definitions and cost models todestination IP device3306 as follows:$\mathrm{Path}E\text{:}\mathrm{network}\mathrm{interface}D346\colon\colon \mathrm{RT}3312\colon\colon \mathrm{IP}\mathrm{device}3306$$\mathrm{Path}F\text{:}\mathrm{network}\mathrm{interface}E348\colon\colon \mathrm{RT}4314\colon\colon \mathrm{IP}\mathrm{device}3306$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}E\right)=\mathrm{Cost}\left(356\right)+\mathrm{Cost}\left(322\right)+\mathrm{Cost}\left(332\right)\\ =\mathrm{Cost}\left(356\right)+70+35\\ =\underset{\_}{\mathrm{Cost}\left(356\right)+105}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}F\right)=\mathrm{Cost}\left(358\right)+\mathrm{Cost}\left(324\right)+\mathrm{Cost}\left(334\right)\\ =\mathrm{Cost}\left(358\right)+83+18\\ =\underset{\_}{\mathrm{Cost}\left(358\right)+101}\end{array}$
• Multi-path router instance2338 may also derive a single, non-redundant network path definition and cost model todestination IP device2304 using conventional SPF protocols as follows:$\mathrm{Path}G\text{:}\mathrm{network}\mathrm{interface}D346\colon\colon \mathrm{RT}3312\colon\colon \mathrm{IP}\mathrm{device}2304$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}G\right)=\mathrm{Cost}\left(356\right)+\mathrm{Cost}\left(322\right)+\mathrm{Cost}\left(330\right)\\ =\mathrm{Cost}\left(356\right)+70+28\\ =\underset{\_}{\mathrm{Cost}\left(356\right)+98}\end{array}$
• In a second exemplary application ofIP device1302 indata network300 with the above network segment costs,SPF1instance336 may set costs forinterior segments350,352, and354 such that Paths A, B, and C have the same aggregate cost. This may be desired by application resources inIP device1302 in order to provide load balancing across multiple network paths for data traffic between IP applications associated withSPF1336 andIP device2304. In order to achieve this goal, the assigned costs may be as follows:
• • Cost(350)=49; Cost(Path A)=122
  • Cost(352)=0; Cost(Path B)=122
  • Cost(354)=55; Cost(Path C)=122 and Cost(Path D)=129
• In a third exemplary application ofIP device1302 indata network300 with the above exemplary network segment costs,multi-path router instance2338 may independently set cost values forinterior segments356 and358 such that Paths D and E have the same cost, in order to provide load balancing of data traffic between IP applications associated withSPF2 andIP device3306. In order to achieve this goal, the assigned costs may be as follows:
• • Cost(356)=30; Cost(Path E)=135 and Cost(Path G)=128
  • Cost(358)=34; Cost(Path F)=135
• In another exemplary application ofIP device1302 indata network300 with the above network segment costs,multi-path router instance1336 may be required by other resources withinIP device1302 to established a prioritized rank of network interface or path utilization without changing assigned costs for external data network segments. For example, an autonomous system management function withinIP device1.302 may determine thatnetwork interface A340 requires a new software load and can only carry traffic on an emergency basis until the update is complete.Multi-path router instance1336 may assign the following cost parameters in order to favor use ofnetwork interface B342 first, followed bynetwork interface C344, and then reservenetwork interface A340 for sparing or overflow traffic only:
• • Cost(350)=500; Cost(Path A)=573
  • Cost(352)=10; Cost(Path B)=132
  • Cost(354)=70; Cost(Path C)=137 and Cost(Path D)=144
• In yet another exemplary application ofIP device1302 indata network300 with the above network segment costs,multi-path router instance2338 may be required by other resources withinIP device1302 to established a prioritized rank of network interface or path utilization without changing assigned costs for external data network segments. For example, an autonomous system management function withinIP device1302 may determine thatnetwork interface E348 requires diagnostic testing and should have data traffic temporarily diverted tonetwork interface D346 until the tests are complete.Multi-path router instance2338 may assign the following cost parameters in order to favor use ofnetwork interface E346 first and then reservenetwork interface F348 for sparing or overflow traffic only:
• • Cost(356)=20; Cost(Path E)=125 and Cost(Path G)=118
  • Cost(358)=1000; Cost(Path F)=1101
Exemplary Data Network with Plural IP Devices with Multi-Path Calculation Capabilities
• An IP device with a multi-path router instance according to an embodiment of the subject matter described herein may communicate with other like devices to maintain ranked VoIP path lists to the devices.FIG. 4 illustrates anexemplary data network400 withIP devices402 and404, a plurality ofnetwork devices406,408, and410, and a plurality ofnetwork segments412,414,416,418,420, and422.IP device1402 andIP device2404 may serve simultaneously as source and destination IP devices, and each may contain resources to provide functions according to the subject matter described herein.IP device1402,IP device2404, as well asrouters RT1406,RT2408, andRT3410 may all be configured with instances of a SPF algorithm such as OSPF or TE-OSPF. For example,data network400 may represent two multi-service provisioning platforms supporting a mix of voice, video, and data traffic at a network access point.
• InFIG. 4,IP device1402 may includemulti-path router instance424, threenetwork interfaces426,428, and430, threeinterior segments432,434, and436, and a path cost table438. Similarly,IP device2404 may include multi-pathSPF router instance440, threenetwork interfaces442,444, and446, threeinterior segments448,450, and452, and a path cost table454.
• In an exemplary application, a network administrator may assign the following costs todata network segments412,414,416,418,420, and422, as indicated inFIG. 4, using methods associated with conventional SPF protocols:
• • Cost(412)=35; Cost(414)=30; Cost(416)=45
  • Cost(418)=40; Cost(420)=45; Cost(422)=35
• Multi-path router instance424 and multi-path router instance438 may define three interconnecting network paths and associated cost models, as follows:$\mathrm{Path}A\text{:}\mathrm{Network}\mathrm{interface}1A426\colon\colon \mathrm{RT}1406\colon\colon \mathrm{network}\mathrm{interface}2A$$440$$\mathrm{Path}B\text{:}\mathrm{Network}\mathrm{interface}1B428\colon\colon \mathrm{RT}2408\colon\colon \mathrm{network}\mathrm{interface}2B$$442$$\mathrm{Path}C\text{:}\mathrm{Network}\mathrm{interface}1C430\colon\colon \mathrm{RT}3410\colon\colon \mathrm{network}\mathrm{interface}2C$$444$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}A\right)=\mathrm{Cost}\left(432\right)+\mathrm{Cost}\left(412\right)+\mathrm{Cost}\left(418\right)+\mathrm{Cost}\left(446\right)\\ =\mathrm{Cost}\left(432\right)+35+40+\mathrm{Cost}\left(446\right)\\ =\underset{\_}{\mathrm{Cost}\left(432\right)+\mathrm{Cost}\left(446\right)+75}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}B\right)=\mathrm{Cost}\left(434\right)+\mathrm{Cost}\left(414\right)+\mathrm{Cost}\left(420\right)+\mathrm{Cost}\left(448\right)\\ =\mathrm{Cost}\left(434\right)+30+45+\mathrm{Cost}\left(448\right)\\ =\underset{\_}{\mathrm{Cost}\left(434\right)+\mathrm{Cost}\left(448\right)+75}\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}C\right)=\mathrm{Cost}\left(436\right)+\mathrm{Cost}\left(416\right)+\mathrm{Cost}\left(422\right)+\mathrm{Cost}\left(450\right)\\ =\mathrm{Cost}\left(436\right)+45+35+\mathrm{Cost}\left(450\right)\\ =\underset{\_}{\mathrm{Cost}\left(436\right)+\mathrm{Cost}\left(450\right)+80}\end{array}$
• In a second exemplary application, the multi-path router instances inIP device1402 may autonomously assign costs tointerior segments350,352,354,356, and358 while maintaining the external network costs identified above. For example,multi-path router instance424 may autonomously assign costs toIP device1402interior segments432,434, and436, as follows:
• • Cost(432)=15; Cost(434)=10; Cost(436)=15
• Additionally,multi-path router instance438 may autonomously assign costs toIP device2404interior segments446,448, and450, as follows:
• • Cost(446)=20; Cost(448)=20; Cost(450)=20
• These multi-path router instances may then define the end-to-end cost for each of the three network paths as follows:$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}A\right)=\mathrm{Cost}\left(432\right)+\mathrm{Cost}\left(412\right)+\mathrm{Cost}\left(418\right)+\mathrm{Cost}\left(446\right)\\ =15+35+40+20=110\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}B\right)=\mathrm{Cost}\left(434\right)+\mathrm{Cost}\left(414\right)+\mathrm{Cost}\left(420\right)+\mathrm{Cost}\left(448\right)\\ =10+30+45+20=115\end{array}$$\begin{array}{c}\mathrm{Cost}\left(\mathrm{Path}C\right)=\mathrm{Cost}\left(436\right)+\mathrm{Cost}\left(416\right)+\mathrm{Cost}\left(422\right)+\mathrm{Cost}\left(450\right)\\ =15+45+35+20=115\end{array}$
• Path A represents the preferred path betweenIP device1multi-path router instance424 andIP device2multi-path router instance438, with paths B and C as alternates in a load-sharing configuration.
• In a third exemplary application,IP device2404 may have a requirement to stop sending traffic throughnetwork interface2B444 so that equipment atIP device2404 may be replaced or reconfigured.Multi-path router instance440 may reassigninterior segment450 cost to be 10,000 in order to gracefully shift traffic away fromnetwork interface444. This change of cost assignment may raise the aggregate cost for Path B to 10,085 if the external network does not make any contemporaneous changes to costs assigned tonetwork segments414 or420. Since the interior segment costs may be advertised using SPF LSA messages,IP device1 may update its internal path cost calculations and ranked path list with the change atIP device2, shifting all data traffic away from Path B before the conventional LSA messages associated with SPF network protocols would provide an indication thatnetwork interface2B444 has been disabled byIP device2404.
Exemplary Media Gateway
• In one exemplary implementation, an IP device with a multi-path router instance may comprise a media gateway or other like device for processing media packets, such as VoIP packets.FIG. 5 illustrates an exemplary media gateway having a multi-path router instance according to an embodiment of the subject matter described herein. InFIG. 5,media gateway500 includes acontrol module502, acentral switch fabric504, four VoIP hostsH1504,H2506,H3508, andH4510, two SPFrouter instances SPF1514 andSPF2516 with associated path cost tables518 and520, and four network interfaces A522,B524,C526, andD528.
• InFIG. 5,control module502 may provide overall control and supervision of all resources inmedia gateway500, and may compriseresource manager530,internal cost matrix532, a globalVoIP path list534, and a global network topology and cost data table536.Resource manager530 may allocate new VoIP sessions to incoming packets and update the global network topology and cost data table536 based on network path information provided by multi-path SPFrouter instances SPF1514 andSPF2516.Resource manager530 may assign VoIP sessions to VoIP network paths stored in the globalVoIP path list534 and to VoIP hostsH1506,H2508,H3510, andH4512 based on available processing capacity in the VoIP hosts.Internal cost matrix532 may include internal costs associated with VoIP sessions originating at VoIP hostsH1506,H2508,H3510, andH4512 and passing through multi-pathrouter instances SPF1514 andSPF2516 to the external data network through network interfaces A522,B524,C526, andD528.
• Switch fabric504 may provide connectivity amongcontrol module502, VoIP hostsH1506,H2508,H3510, andH4512, multi-path SPFrouter instances SPF1514 andSPF2516, and other resources inmedia gateway500. In one implementation,switch fabric504 may be an Ethernet switch fabric. In an alternate implementation,switch fabric504 may be an ATM switch fabric. Although not illustrated inFIG. 5,media gateway500 may include a plurality of TDM interfaces for interfacing with a TDM network and a TDM switching matrix for connecting the TDM interfaces to VoIP hosts506,508,510, and512.
• VoIP hostsH1506,H2508,H3510, andH4512 may contain resources for processing VoIP and TDM voice streams. For example, each VoIP host may include codecs, voice over ATM, voice over IP, and TDM components, and digital signal processing resources for processing VoIP streams. Each host may also include resources to implement RTP protocol functions, including datagram creation and control messaging. Each host may also have a unique IP address assigned bymedia gateway500.
• Multi-path SPFrouter instances SPF1514 andSPF2516 and cost tables518 and520 may be utilized inmedia gateway500 to implement all routing protocol interactions with adjacent SPF nodes in the external data network. Multi-pathrouter instances SPF1514 andSPF2516 may implement a published protocol utilizing SPF algorithms and methods, such as OSPF and TE-OSPF or may implement a propriety SPF protocol. Multi-path SPFrouter instances SPF1514 andSPF2516 may each be associated with multiple network interfaces and implement network path definitions and cost calculations according to the subject matter described herein.
• Network interfaces A522,B524,C526, andD528 may provide standard external interface functions tomedia gateway500, including physical termination of network segments to adjacent network nodes. For example, network interfaces522,524,526, and528 may be IP network interfaces that interface with an external IP network.
• In operation, multi-pathSPF router instances514 and516 may each implement an SPF algorithm multiple times usingnetwork interfaces522,524,526, and528 as SPF nodes to calculate costs for a plurality of paths throughnetwork interface522,524,526, and528 to a destination. Multi-pathSPF router instances514 and516 may create and maintain a ranked list of IP paths to the destinations based on the calculated costs. Multi-pathSPF router instances514 and516 may forward traffic over at least one of the paths, such as a lowest cost path. If the lowest-cost path fails, multi-pathSPF router instances514 and516 may select a new lost cost path and begin using that path for outgoing media packets.
• It will be understood that various details of the subject matter described herein may be changed without departing from the scope of the subject matter described herein. Furthermore, the foregoing description is for the purpose of illustration only, and not for the purpose of limitation, as the subject matter described herein is defined by the claims as set forth hereinafter.

Claims (36)

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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 1 comprising advertising the costs of the internal segments to at least one external network device.

12. The method ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 25 comprising advertising the costs of the internal segments to at least one external network device.

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

Images