Method and system for correlating practical constraints in a network Number:7,394,760 from the United States Patent and Trademark Office (PTO) owispatent A system and method for identifying optimal mapping of logical links to the physical topology of a network is provided. Upon obtaining one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint and obtaining a maximum time delay allowed between the each pair of network nodes, the mapping options are correlated with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.<H constraints, correlating, Method, and, syst, 7394760.html, Patent, pto, 7394760

Title: Method and system for correlating practical constraints in a network

Abstract: A system and method for identifying optimal mapping of logical links to the physical topology of a network is provided. Upon obtaining one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint and obtaining a maximum time delay allowed between the each pair of network nodes, the mapping options are correlated with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.

Patent Number: 7,394,760 Issued on 07/01/2008 to Nucci, et al.

Inventors: Nucci; Antonio (Burlingame, CA), Taft; Nina A. (San Francisco, CA), Diot; Christophe (Cambridge, GB), Giroire; Frederic (Paris, FR)
Assignee: Sprint Communications Company L.P. (Overland Park, KS)

Appl. No.: 10/615,649

Filed: July 9, 2003

Current U.S. Class: 370/225 ; 370/238

Current International Class: H04L 12/28 (20060101)

Field of Search: 370/225,238

References Cited [Referenced By]

U.S. Patent Documents


5164938	November 1992	Jurkevich et al.
5500808	March 1996	Wang
5590356	December 1996	Gilbert
5600638	February 1997	Bertin et al.
5764740	June 1998	Holender
5805578	September 1998	Stirpe et al.
5933607	August 1999	Tate et al.
6069894	May 2000	Holender et al.
6577601	June 2003	Wolpert
6956824	October 2005	Mark et al.
2002/0097671	July 2002	Doverspike et al.

Foreign Patent Documents


950966	Sep., 1989	EP

Other References

Modiano et al, "Survicable routing of logical topologies in WDM networks", IEEE INFOCOM 2001, pp. 348-357. cited by examiner .
Nucci et al, "Design of Fault-Tolerant Logical Topologies in Wavelength-Routed Optical IP Networks", GLOBECOM 2001, pp. 1-6. cited by examiner .
T. Erlebach, K. Jansen, C. Kakalamanis, M. Mihail and P. Perslano "Optimal wavelength routing on directed fiber trees", Theoretical Computer Science, vol. 221, n.1-2, pp. 119-137, 1999. cited by other .
D. S. Hochbaum editor "Approximation Algorithms for NP-Hard Problems", PWS Publishing Company, 1997. cited by other .
Eric J. Harder, Sang-Kyu Lee and Hyeong-Ah Choi "On Wavelength Assignment in WDM Optical Networks", Proceedings of the 4th International Conference on Massively Parallel Processing Using Optical Interconnections (MPPOI'97), 1997. cited by other .
A. Nucci, N. Taft, P. Tmran, H. Zang and C. Diot "Increasing the Link Utilization in IP over WDM Networks" Opticom 2002. Jun. 2002. cited by other .
G. Iannaccone, C. Chuah, R. Mortier, S. Bhattacharyya and C. Diot "Analysis of Link Failures in a Large IP Backbone" in Proc. 2nd ACM Sigcomm Internet Measurement Workshop (IMW), Nov. 2002. cited by other .
K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi and C. Diot "Analysis of Measured Single-Hop Delay from an Operational Backbone Network" in Proc.IEEE Infocom, New York, Jun. 2002. cited by other .
J. Armitage, O. Crochat, J. Y. Le Boudec "Design of a Survivable WDM Photonic Network", in Proc. INFOCOM '97, pp. 244-252, Apr. 1997. cited by other .
O. Crochat, J.Y.Le Boudec "Design Protection for WDM Optical Networks", IEEE Journal on Selected Areas in Communication, vol. 16, n.7, pp. 1158-1165, Sep. 1998. cited by other .
O.Crochat, J.Y.Le Boudec, O.Gerstel "Protection Interoperability for WDM Optical Networks", IEEE Transaction on Networking, vol. 8, n.3, pp. 384-395, Jun. 2000. cited by other .
E. Modiano, A. Narula-Tam "Survivable routing of logical topologies in WDM networks", in Proc. INFOCOM '01 vo1.l, pp. 348-357, Anchorage, Alaska, Apr. 2001. cited by other .
F. Glover, E. Taillard and D. De Werra "A User's Guide to Tabu Search", Annals of Operations Research, vol. 41, pp. 3-28, 1993. cited by other .
V. Kumar "Approximating arc circular colouring and bandwidth allocation in all-optical ring networks", First international Workshop on Approximation ALgorihms for Combinatorial Optimization Problems (APPROX'98), 1998. cited by other .
A. Nucci, B. Sanso, T. G. Crainic, E. Leonardi, M. Marsan "Design of Fault-Tolerant Logical Topologies in Wavelength-Routed Optical IP Networks", IEEE Globecom Proceedings, Nov. 2001. cited by other .
B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Perennes and U. Vaccar "Graph problems arising from wavelength-routing in all-optical networks", 2nd IEEE Workshop on Optics and Computer Science, part of IPP'97, Genova, Switzerland, Apr. 1997. IEEE Press. cited by other .
V. Auletta, 1. Caragiannis and P. Persiano "Randomized path coloring on binary trees", 3rd International Workshop on Approximation ALgorihms for Combinatorial Optimization Problems (APPROX'OO), vo1. I913, pp. 60-71, Springer-Verlag, 2000. cited by other.

Primary Examiner: Yao; Kwang B.
Assistant Examiner: Lai; Andrew

Claims

We claim:

1. A method for identifying optimal mapping of logical links to the physical topology of a network, the method comprising: obtaining one or more mapping options for mapping multiple logical links between a first pair of network nodes and a second pair of network nodes, the first and second pair of network nodes sharing at least one node, onto physical paths that are at least relatively disjoint to enhance robustness of the network in an event of a resource failure; obtaining a maximum time delay allowed between each pair of network nodes; and correlating the mapping options with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.

2. The method of claim 1, further comprising: obtaining a relative time delay allowed between two or more physical paths.

3. The method of claim 2, further comprising: correlating the mapping options with the maximum time delay and the relative time delay to identify optimal mapping of logical links to the physical topology of a network.

4. The method of claim 3, further comprising: obtaining the availability of wavelengths in a network.

5. The method of claim 4, further comprising: correlating the mapping options with the maximum time delay, the relative time delay and the wavelength availability to identify optimal mapping of logical links to the physical topology of a network.

6. The method of claim 5, further comprising: obtaining a priority order of the network node pairs.

7. The method of claim 6, further comprising: correlating the mapping options with the maximum time delay, the relative time delay, the wavelength availability and the priority order of the network node pairs to identify optimal mapping of logical links to the physical topology of a network.

8. The method of claim 7, wherein the correlation is performed using an integer linear program.

9. The method of claim 7, wherein the correlation is performed using a Tabu search methodology.

10. The method of claim 7, wherein the correlation is performed to identify the optimal mapping for a large Internet network backbone.

11. The method of claim 7, wherein the correlation is utilized to identify where new fibers or wavelengths need to be added to the network topology.

12. One or more computer storage media having computer-executable instructions for performing the method recited in claim 1.

13. One or more computer storage media having computer-executable instructions for performing the method recited in claim 7.

14. A computer system for identifying optimal mapping of logical links onto the physical topology of a network, the system comprising: a practical constraint module comprising a mapping option sub-module for obtaining one or more mapping options for multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint and a maximum time delay sub-module for obtaining a maximum time delay allowed between the each pair of network nodes; and a correlation module coupled with the practical constraint module for correlating the mapping options with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.

15. The computer system of claim 14, wherein the practical constraint module further comprises a relative time delay sub-module for obtaining the relative time delay allowed between two or more physical paths.

16. The computer system of claim 15, wherein the correlation module coupled with the practical constraint module correlates the mapping options with the maximum time delay and the relative time delay.

17. The computer system of claim 16, wherein the practical constraint module further comprises a wavelength sub-module for obtaining the wavelength availability in a network.

18. The computer system of claim 17, wherein the correlation module coupled with the practical constraint module correlates the mapping options with the maximum time delay, the relative time delay allowed and wavelength availability.

19. The computer system of claim 18, wherein the correlation module utilizes an integer linear program to perform the correlation.

20. The computer system of claim 18, wherein the correlation module utilizes a Tabu search methodology to perform the correlation.

21. The computer system of claim 18, wherein the correlation is performed to identify the optimal mapping for a large Internet network backbone.

22. A system for identifying optimal mapping of logical links to the physical topology of a network, the system comprising: means for obtaining one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint; means for obtaining a maximum time delay allowed between the each pair of network nodes; and means for correlating the mapping options with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.

23. The system of claim 22, further comprising: means for obtaining a relative time delay allowed between two or more physical paths.

24. The system of claim 23, further comprising: means for correlating the mapping options with the maximum time delay and the relative time delay to identify optimal mapping of logical links to the physical topology of a network.

25. The system of claim 24, further comprising: means for obtaining the availability of wavelengths in the network.

26. The system of claim 25, further comprising: means for correlating the mapping options with the maximum time delay, the relative time delay and the wavelength availability to identify optimal mapping of logical links to the physical topology of a network.

27. The system of claim 26, further comprising: means for obtaining a priority order of the network node pairs.

28. The system of claim 27, further comprising: means for correlating the mapping options with the maximum time delay, the relative time delay, the wavelength availability and the priority order of the network node pairs to identify optimal mapping of logical links to the physical topology of a network.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

Not Applicable.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

Not Applicable.

TECHNICAL FIELD

More particularly, the invention relates to a computerized system and method for identifying optimal mapping in a network. The system and method of the present invention increases the robustness of network backbones while taking into account practical considerations.

BACKGROUND OF THE INVENTION

Most Internet Protocol (IP) backbone networks are designed on top of a Dense Wavelength Division Multiplexing (DWDM) infrastructure. An IP network is a set of logical links that are statically mapped on the physical links of the fiber network. In a DWDM network, each logical link is assigned one wavelength if wavelength continuity is required, or a sequence of wavelengths if wavelength conversion equipment is present. Further, Internet Service Providers (ISPs) are systematically forced to use the shortest distance path between two Points of Presence (PoPs) in order to meet their promised Service Level Agreements (SLAs). In this environment, several logical links (each using a different wavelength) may traverse the same fiber (or the same conduit), making the IP network vulnerable to a physical link failure, such as a fiber cut, that can bring down a significant fraction of the IP routes.

In the past, a Synchronous Optical network (SONET) was used to offer protection and fast restoration of service. However, due to the cost of optical equipment, most ISPs do not use SONET protection anymore. Instead, they rely on the IP layer to restore the connectivity in case of failure. When equipment fails in the topical network, IP routers detect the failure and update their routing tables with alternate logical links. This approach only succeeds if the remaining set of logical links still forms a connected topology.

Mapping logical links to the physical topology to assure connectivity during failures has already been studied. Prior approaches include an Integer Linear Problem (ILP) formulation that solves the problem for moderate size networks by applying a Branch & Cut algorithm. However, this approach assumes there is only a single logical link between network node pairs and does not take into account any delay constraints.

Topology mapping with wavelength constraints has also been studied. Without wavelength converters, the problem is known as the wavelengths assignment problem (WAP). This problem is similar to the path-coloring problem in standard graphs, which is equivalent to the general vertex-coloring problem. Numerous heuristics have been proposed for different types of topologies. However, these approaches do not balance the tradeoff between running time and quality of the solution.

Accordingly, there remains a need for a system and method for identifying optimal mapping of logical links to the physical topology of a network that incorporates practical considerations, such as delay constraints, wavelength availability and multiple logical links between network node pairs.

BRIEF SUMMARY OF THE INVENTION

In one aspect of the present invention, a method for identifying optimal mapping of logical links to the physical topology of a network is provided. The method obtains one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint. The method also obtains a maximum time delay allowed between the each pair of network nodes. The method correlates the mapping options with the maximum time delay. Optionally, the method also obtains a relative time delay allowed between two or more physical paths, the wavelength availability in the network and/or a priority order of the network node pairs. If so, the method correlates mapping options with the maximum time delay, the relative time delay, the wavelength availability and/or the network node priority pairs.

In yet another aspect of the present invention, a computer system for identifying optimal mapping of logical links onto the physical topology of a network is provided. The system includes a practical constraint module and a correlation module. The practical constraint module includes a mapping option sub-module for obtaining one or more mapping options for multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint and a maximum time delay sub-module for obtaining a maximum time delay allowed between the each pair of network nodes. The correlation module is coupled with the practical constraint module and correlates the mapping options with the maximum time delay.

Still a further aspect of the present invention is a system for identifying optimal mapping of logical links to the physical topology of a network. The system includes means for obtaining one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint. The system also includes means for obtaining a maximum time delay allowed between the each pair of network nodes and means for correlating the mapping options with the maximum time delay to identify optimal mapping of logical links to the physical topology of a network.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING

FIG. 1 is diagram of two mapping options between two neighboring network nodes;

FIG. 2 is a block diagram of a computing system including a practical constraint module and a correlation module in accordance with an embodiment of the present invention;

FIG. 3 is a block diagram of a computing system, including a practical constraint module and a correlation module in accordance with an embodiment of the present invention;

FIG. 4 is a flowchart representative of a computer program for identifying optimal mapping in an IP network in accordance with an embodiment of the present invention.

FIG. 5 is a flowchart representative of a computer program for identifying optimal mapping in an IP network in accordance with an embodiment of the present invention;

FIG. 6A is diagram of mapping logical links between two network nodes in accordance with an embodiment of the present invention;

FIG. 6B is diagram of mapping logical links between two network nodes in accordance with an embodiment of the present invention;

FIG. 7 is a diagram of an exemplary physical topology for a large IP network;

FIG. 8 is a diagram of exemplary logical topology for a large IP network;

FIG. 9A is graphical representation of a performance metric in accordance with an embodiment of the present invention;

FIG. 9B is graphical representation of a performance metric in accordance with an embodiment of the present invention;

FIG. 9C is graphical representation of a performance metric in accordance with an embodiment of the present invention;

FIG. 9D is graphical representation of a performance metric in accordance with an embodiment of the present invention; and

FIG. 10 is exemplary graphical representation of the amount of logical links that use a given fiber segment.

DETAILED DESCRIPTION OF THE INVENTION

With reference to FIG. 1, a network is made up of a set of network nodes (100) interconnected by logical links (104). Network nodes, may be, but are not limited to points of presence (PoPS). Each network node (101) is a mini-network composed of a small number of core routers (102), a large number of conventional access routers and intra-network node logical links (106). The core routers (102) in each network node (101) are fully meshed. In a large IP network, each access router is attached to a minimum of two core routers (102). Customers connect to conventional access routers. The connection between adjacent network nodes is done by parallel logical links terminating at different core routers in each network node in such a way that a single router failure cannot bring down a customer nor the entire connectivity between a pair of neighboring network nodes. The inter-network node links are connected by high capacity links (currently, 2.5 Gbps and 10 Gbps). Inter-network node links (and intra-network node logical links) are mapped onto the physical fiber topology.

In order to maximize fault-resilience of the network, parallel logical links may be mapped onto the fiber network in such a way that either a fiber (or conduit) or an optical equipment failure does not cause all the parallel logical links between a pair of network nodes to go down simultaneously. Neighboring (or adjacent) network nodes are network nodes that are directly connected by one or more logical links. There are typically several logical links between neighboring network nodes. The number of parallel logical links is different for each network node pair. The number of logical links may vary depending on the network design options adopted (currently between two and twelve). Each logical link is mapped to a physical fiber path (or physical link). Parallel logical links are mapped onto physical links that are at least relatively disjoint. This design approach improves the robustness of the backbone in the event of resource failure (e.g. router, optical device, fiber).

In addition, load balancing in large networks may be used on the parallel logical links in order to minimize the load of each link and improve the performance of the network. Load balancing splits the traffic on equal cost routes (per flow or per packet). To support load balancing, the delays on parallel logical links need to be similar enough, so that there is no impact on an application if its traffic is rerouted on an alternate logical link after a failure.

In addition to maximizing fault resistance, other practical constraints and requirements faced by carriers today may be incorporated into a mapping solution. One of the practical constraints is maintaining the ISP's Service Level Agreements (SLA's) for any network node pair in the network. Maximum network node-to-network node delay is an important SLA parameter and its value is defined by each ISP. In the continental US, the currently maximum delay is typically between about 50 ms and 80 ms. However, the maximum delay may any specified value. The delay between any network node pair should be below the value defined in the SLA. In addition to the maximum delay, relative delay on the alternative inter-network node paths, may also be taken into consideration. Many applications cannot tolerate a major change in delay in the event of a failure. For example, a Voice-over Internet Protocol (VoIP) application would suffer dramatically if rerouted on a link that caused the end-to-end delay to currently increase by about 50 ms.

Another practical constraint is wavelength limitations. IP networks often have an almost complete absence of wavelength converters in the DWDM layers and from the diversity of fiber quality (fibers currently can support between 8 and 80 wavelengths). Therefore, a shortage of wavelengths in these IP networks is not unusual. If there is a shortage of wavelength in an IP network, the order that the network node pairs are mapped may be critical. As such, network node pairs may be prioritized. For example, logical links connecting network nodes that carry the largest amount of traffic would assure higher fault resilience than logical links carrying small amounts of traffic. On a large IP network, the priority network node pairs are often transcontinental links that connect two major cities such as New York and San Francisco.

Given a particular topology of the physical network, it is not always possible to simultaneously find completely disjoint physical links, and to maintain the delay below the SLA for all logical links between a given network node pair. For example, there may not necessarily exist two short delay paths that are also completely disjoint. In order to find completely disjoint paths, sometimes a long circuitous route for the second path that substantially increases the delay is used.

The present invention is directed to a system and method for identifying the optimal mapping solution in a network. FIG. 2 depicts an exemplary computer system 200 for identifying the optimal mapping solution in a network. The system 200 includes a practical constraint module 201 coupled with a correlation module 210. The practical constraint module 201 includes a mapping options sub-module 202 that obtains one or more mapping options for mapping multiple logical links between one or more pairs of network nodes onto physical paths that are at least relatively disjoint. The practical constraint module, 201, also includes a maximum time delay sub-module 204 for obtaining a maximum time delay allowed between the each pair of network nodes. The practical constraint module 201 may also optionally include a relative time delay sub-module 206 and/or a wavelength sub-module 208. The relative time delay sub-module 206 obtains a relative time delay allowed between two or more physical paths. The wavelength sub-module 208 obtains the availability of wavelengths in the network. The correlation module 210 correlates the mapping options with the maximum delay and optionally correlates the mapping options with the maximum delay, the relative time delay allowed and/or the wavelength availability.

Those skilled in the art will appreciate that the present invention contemplates the presence of additional modules and/or sub-modules of the computer system 200, and the modules and/or sub-modules may be combined with one another and/or separated into new modules and/or sub-modules.

The present invention is directed to a system and method for identifying the optimal mapping solution in a network. FIG. 3 depicts an exemplary computer system 300 for identifying the optimal mapping solution in a network. The system 300 includes a practical constraint module 302 coupled with a correlation module 308. The practical constraint module 302 includes a mapping options sub-module 304 that obtains one or more mapping options for mapping multiple logical links between two or more pairs of network nodes onto physical paths that are at least relatively disjoint. The practical constraint module, 302, includes a priority sub-module 306 for obtaining a priority order of the network node pairs. The correlation module 308 correlates the mapping options with the network node priority.

Those skilled in the art will appreciate that the present invention contemplates the presence of additional modules and/or sub-modules of the computer system 300, and the modules and/or sub-modules may be combined with one another and/or separated into new modules and/or sub-modules.

The invention may be described in the general context of computer-executable instructions, such as program modules. Generally, program modules include routines, programs, objects, components, segments, schemas, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

Computers typically include a variety of computer-readable media. Computer-readable media includes any media that can be accessed by a computer and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer-readable media may comprise computer storage media and communications media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD), holographic or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer.

Communications media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communications media includes wired media such as a wired network or direct wired connection, and wireless media such as acoustic, RF, infrared, spread spectrum and other wireless media. Communications media are commonly used to upload and download information in a network environment, such as the Internet. Combinations of any of the above should also be included within the scope of computer-readable media.

The computer may operate in a networked environment using logical connections to one or more remote computers such as a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above. The logical connections may include connections to a local area network (LAN), a wide area network (WAN) and/or other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

Computer storage mechanisms and associated media provide storage of computer-readable instructions, data structures, program modules and other data for the computer. A user may enter commands and information into the computer through input devices such as a keyboard and pointing device, commonly referred to as a mouse, trackball or touch pad. Other input devices may include a microphone, touchscreen, camera, joystick, game pad, scanner, or the like. In addition to a monitor or other type of display device, computers may also include other peripheral output devices such as speakers and printers, which may be connected through an output peripheral interface.

Although many other internal components of computers have not been discussed herein, those of ordinary skill in the art will appreciate that such components and their interconnection are well-known. Accordingly, additional details concerning the internal construction of computers need not be disclosed in connection with the present invention.

Referring next to FIG. 4, a flow diagram 400 is provided which illustrates an embodiment for identifying optimal mapping in a network in accordance with the present invention. Mapping options are obtained at block 402. The mapping options comprise mapping multiple logical links between one or more pairs of network nodes onto physical paths of the IP topology that are as diverse as possible. In other words, a mapping option is a set of physical paths to which parallel logical links between a pair of network nodes may be mapped. The maximum time delay is obtained at block 404. The maximum time delay is the maximum delay allowed between two network nodes and is often set by an SLA requirement. The mapping options are correlated with the maximum time delay at block 406. The correlation of the mapping options with the maximum time delay allowed may be used to identify the optimal mapping of parallel logical links to physical paths of an IP network.

Referring to FIG. 5, a flow diagram 500 is provided which illustrates an embodiment for identifying optimal mapping of parallel logical links to physical paths in a network in accordance with the present invention. Mapping options are obtained at block 502. The order of network node priority is obtained at block 504. The network node priority pairs are network nodes that will have their logical links mapped first. The network node pairs with the highest priority are often those that have a special status in the network, e.g., they carry more traffic or they connect major geographical locations. In block 506, the mapping options are correlated with the network node priority. The correlation of the mapping options with network node priority may be used to identify the optimal mapping of parallel logical links to physical paths of an IP network.

Network Protection and Disjointness. In order to maximize fault-resilience, parallel logical links may be mapped onto the fiber network in such a way that either a fiber conduit or an optical equipment failure does not cause all the parallel logical links between a pair of network nodes to go down simultaneously. Thus, parallel logical links are mapped onto physically disjoint fibers whenever possible.

Finding completely disjoint fiber paths for logical links is often difficult. The logical topology demands large numbers of disjoint options, however the physical topology may limit the number of options for alternate disjoint paths. There are often a limited set of conduits containing fibers in the ground and because these fibers have been layed out according to terrain constraints (mountains, bridges, etc.) and conveniences such as train tracks or pipelines. Finding maximally disjoint paths is difficult and is often challenging in the case of a current US network backbone because the multiplicity of parallel links between network nodes is not merely two, but can be as large as 12 (although is more commonly between 4 to 7). When completely disjoint paths cannot be found, the method of the present invention searches for maximally disjoint paths.

The system and method of the present invention minimizes the number of logical links that are disrupted over all possible physical failures. In other words, the system and method of the present invention minimizes the jointness of the parallel logical links between each pair of adjacent network nodes. Minimizing the jointness is equivalent to maximizing the disjointness. The following is a description of a local jointness (LJ) metric that is assigned to a pair of network nodes.

For local jointness, consider two neighboring network node s and t. The parallel links between s and t use a set of fiber segments {(i,j)} that start at node i and terminate at node j. Each fiber segment is to be assigned one jointness value for each pair of adjacent network nodes using that segment. (Thus each fiber gets a set of values, one for each network node pair traversing it.) For a given network node pair, the fiber segment is assigned a jointness value equal to the number of parallel logical links sharing this fiber segment minus one.

Therefore, the jointness of a fiber segment used by a single link between s and t is zero. The local jointness of a network node pair (s,t) is defined as the sum of the jointness of each fiber segment {(i,j)} used by any of its parallel logical links. A local jointness of zero for network node pair (s,t) means that all the parallel logical links between s and t use fully disjoint physical paths.

With reference to FIG. 6A and FIG. 6B, three exemplary logical links between two network nodes are mapped onto the physical network represented in the figure. The plain lines indicate fibers separated by optical cross connects. The dashed lines represent the candidate physical paths for the three logical links. In FIG. 6A, the three parallel links share a single fiber segment and thus the jointness of network node pair (A, B) is two. In FIG. 6B, there are two fibers that each have a jointness of one (since two paths share each link), and thus the jointness of the network node pair (A, B) is also two.

The lower the jointness metric, the less fiber sharing there is. As the jointness is reduced it decreases the likelihood that a single fiber failure will affect a large number of the parallel logical links of the same network node pair. Thus, minimizing the jointness metric can improve robustness.

In the illustrated example, two different scenarios can give rise to the same jointness value for a network node pair. Therefore the jointness metric does not always distinguish the two scenarios in FIG. 6A and FIG. 6B in terms of robustness. Since different mapping scenarios can lead to the same jointness value, the jointness metric in this example does not uniquely differentiate all possible mapping scenarios. In this example, the mapping of FIG. 6B would be considered more robust than the mapping of FIG. 6A. In FIG. 6A, a single fiber failure will bring down all the logical links between network nodes A and B, whereas in FIG. 6B the two network nodes will remain connected under any single fiber failure scenario. Priority information, discussed later, may be used to add further robustness differentiation to the jointness metric.

To determine the global jointness of the network, the local jointness over all neighboring network node pairs in the backbone is added. The global jointness then can be used to compare various mappings. The impact of the delay SLAs on fiber sharing may also be evaluated using this jointness metric.

Delay constraints. A Service Level Agreement (SLA) is a contract, for example, between an ISP and its customer. This contract specifies a maximum end-to-end delay (maximum delay constraint) between any arbitrary pair or network nodes (not just neighboring network nodes) that should be satisfied at any moment in time, both under normal operation and during failures. The delay mostly comes from propagation delay. The delay between a pair of network nodes is the worse case total transmission time, among all possible routes, between these two network nodes. All the possible routes between two network nodes are considered as any one of them may be used as the alternate route in event of a failure.

The physical layout of fibers in today's networks tends to yield the following situation: two network nodes that are geographically close often have one route between them that is short (in terms of distance and hence propagation time), while all other routes are much longer (typically on the order of 5 to 10 times longer). If there are many parallel links to be mapped for a given network node pair, it makes it difficult to minimize jointness without increasing the length of alternate fiber paths. As mentioned earlier, it is not acceptable for SLAs to be broken when routes change. Furthermore, ISPs cannot allow delay sensitive applications to experience a degradation in delay that would be critical to the application. Thus, another delay constraint, the relative delay constraint, limits the allowable difference in delay between two paths is introduced.

In order to control the relative delay constraint, for each pair of neighboring network nodes, one of its paths is chosen to be the default path. The delay of each of the parallel logical links, for a given network node pair is to be no more than u % longer than the default path delay. Conceptually the default path is a reference path used to control the delay differences between alternate paths. Because the default path is an artifact of the method, it may or may not be used itself. Later, three different strategies for computing the default path will be discussed.

Wavelength limitation. In DWDM networks each fiber often has a fixed number of wavelengths. While performing the mapping, the system may determine whether a sufficient number of wavelengths exist for this mapping. In the case of no wavelength conversion, the same wavelength should be available on all the fiber segments involved in the physical paths. The limitation on the number of available wavelengths significantly complicates the problem. A solution that is optimal from a jointness standpoint might not be feasible from the wavelength allocation standpoint. In other words, assigning one wavelength to a logical link of network node pair (A, B) can reduce the possibilities of fiber path choice for network node pair (C, D), and increase the jointness for all other network node pairs. Therefore, in one embodiment of the invention, the system takes wavelength limitation into consideration in the computation of jointness.

Approach. In one embodiment of the present invention, an Integer Linear Program (ILP) model, that includes some or all of the constraints discussed above, is provided. In another embodiment, a heuristic algorithm is provided (using the Tabu Search meta heuristic methodology) to solve the mapping problem for large networks whose size makes the ILP model difficult to use. The solutions found by the heuristic algorithm may be compared with the one found by the ILP model. An objective of both the ILP model and the heuristic algorithm is to minimize the global jointness while simultaneously meeting the maximum and relative delay requirements for SLAs. However, it is difficult to find the optimal mapping for the constraints introduce because the problem is complex and the search space is large. Thus, two types of priorities may be applied to help manage the distribution of resources across network nodes, further improve robustness and limit the search space.

Sometimes the mapping of one network node pair can compromise the mapping of another. In particular, if there is a shortage of wavelengths, then the order in which network node pairs are mapped can be critical. Those network node pairs mapped first may use up some wavelengths that are then no longer available to other network node pairs. This can limit the choices of alternate paths for the latter network node pairs. A set of network node pairs are considered as priority network node pairs and map their logical links first. In this embodiment, those priority network node pairs are granted the minimum local jointness possible, even if it means that the non-priority network node pairs end up with a larger local jointness than they would receive if no priorities existed at all. Priority network node pairs correspond to the inter-network node logical links that are most important to protect because they have a special status in the network (e.g. they carry more traffic, or they connect major geographical locations). For example, in a large IP backbone, transcontinental east-west links are usually considered to be high priority network node pairs.

In one embodiment, among all the parallel links that must be mapped for a given network node pair, preferably at least two of them are completely disjoint (if possible) and these are priority logical links. Thus, in this embodiment, instead of mapping all parallel logical links for each network node pair simultaneously, if these are two logical links that can be mapped to completely disjoint paths, these are mapped first and the remaining parallel links are mapped afterwards. For the remaining parallel paths, the system searches for physical paths that minimize the local jointness for that network node pair (given the mapping of the first two paths). If there are not two completely disjoint paths, then all the links are mapped together, again trying to minimize the local jointness. With the second priority notion, the chances of each network node pair having at least two completely disjoint fiber paths is increased. This makes the network node pair more robust because no single fiber failure that can completely disconnect the network node pair. Referring again to FIG. 6A and FIG. 6B, the two priority logical links would have a jointness of zero in the mapping of FIG. 6B and a jointness of one in FIG. 6A. With this notion of priority the solution in FIG. 6B is better than the solution of FIG. 6A because the mapping FIG. 6B includes two completely disjoint paths whereas the mapping of FIG. 6A does not. Priority links thus may help to differentiate the robustness of two mappings of equal local jointness.

To integrate these priorities to minimize global jointness, the following mapping sequence may be used. The goal of the sequence is to minimize the global jointness while respecting the following sequence of steps: Step 1. Map the priority logical links for the priority network node pairs. Step 2. Map the remaining logical links of the priority network node pairs. Step 3. Map the priority logical links for the remaining non-priority network node pairs. Step 4. Map the remaining links (non-priority links of non-priority network node pairs).

In addition to jointness minimization, the system may also take into account delay constraints. First, the delay between any network node pair in the network is often bound by the maximum delay value found in the SLA (known as the maximum delay constraint). Second, the delay difference between all parallel links for any given neighboring network node pair should be within u % of the default path (known as the relative delay constraint).

The relative delay requirement appears as a constraint in the optimization formulation and in the following algorithm. Instead of adding the maximum delay constraint as an input to the objective function, the maximum delay is computed after the mapping has been performed, e.g. as an output of the solutions. The trade-off between jointness and maximum delay can be analyzed by varying the value of u in the set of constraints.

In one embodiment, the system and method of the present invention looks to three strategies in selecting the default path. 1) The Shortest Path (SP): is the default path and is the shortest physical path between a given neighboring network node pair. "Shortest" refers to the path with the shortest propagation delay. 2) Second Shortest Path (SSP): is the default path and is the second shortest path that exists between a given pair of neighboring network nodes. 3) Smallest Disjoint Path (SDP): For each pair of neighboring network nodes there are two completely disjoint paths if the constraints on relative delay and wavelength availability are temporarily removed. This is true because the min cut of the network is two. Given these two disjoint paths, the longer of the two is selected to be the default path.

These strategies can impact the network, especially the trade-off between delay and jointness. The consideration of the different strategies allows a wider diversity of path selection that helps meet a larger number of requirements simultaneously.

EXAMPLE 1

In the following example, a network node by a single router is represented. This "mega-router" has all of the inter-network node links for the whole network node attached to it. The same technique could be applied to intra-network node links as well.

In this example, a physical topology is composed of Optical Cross Connects (OXCs) interconnected by optical fibers is given. Each fiber is characterized by a limited number of wavelengths and its capacity. An IP topology made up of IP routers interconnected by IP layer logical links is also given. The purpose of this example is to find 1) maximally disjoint physical paths for the parallel logical links of all pairs of neighboring network nodes, such that they satisfy the relative delay constraint and 2) an assignment of wavelengths for each logical links. The search for disjoint paths and the wavelength assignment can be conducted in parallel because the wavelength assignment has a direct impact of the feasibility of physical paths.

The maximum delay over all network node pairs is an output of the solution (and the algorithm in the case of the heuristic). As explained in the previous section, the maximum delay can be controlled by tuning the parameter u. Therefore, the maximum delay is computed in a post computation step, after a mapping solution has been found.

In one embodiment of the present invention, an Integer Linear Program (ILP) model, is provided. In another embodiment, heuristic algorithm is provided (using the Tabu Search meta heuristic methodology) to solve the mapping problem for large networks whose size makes the ILP model difficult to use. The solutions found by the heuristic algorithm may be compared with the one found by the ILP model.

ILP Model. The mapping problem is formulated as an Integer Linear Program (ILP) whose objective is to minimize the Global Jointness of the network. First, all the default path lengths between each pair of neighboring network nodes are computed as discussed above.

1) Notation: Let .epsilon.={(i,j)} denote the set of fibers and S={(s, t)} denote the set of neighboring network node pairs. Let n.sup.st denote the number of inter-network nodes links between the two network nodes s and t. Let S.sub.priority.OR right.S represent the subset of the priority network node pairs.

Let w.sub.ij represent the number of wavelengths for fiber (i,j), and w.sub.max the number of wavelengths available on the fiber with the most wavelengths. It is used as bound for the channel index in the constraints. Let .sup.(x)a.sub.ij.epsilon.{0, 1} for all (i,j).epsilon..epsilon. and x.epsilon.{1, 2, . . . , w.sub.max} such that (w)a.sub.ij=1 if the wavelength x belongs to fiber (i, j).

The notation pertaining to delays is as follows: Let I.sub.ij.gtoreq.0 be the length of the physical link (i,j) for all (i,j).epsilon..epsilon.. The values are in the millisecond range. Let d.sup.st for all (s,t).epsilon.S be the delay between the network nodes s and t using the default path. The maximum delay difference among all parallel links between each pair of neighboring network nodes is specified via the parameter u.

2) Decision Variables: To compute the routing

.pi..function. ##EQU00001## is defined for all

.di-elect cons..di-elect cons..di-elect cons..times..times..times..times..pi..function. ##EQU00002## if the m.sup.th link of the network node pair (s, t) traverses the fiber (i, j).

Decision variables maybe used to handle wavelengths. Let .sup.(x).lamda..sup.st(m), defined for all (s,t).epsilon.S, m.epsilon.(1 . . . n.sup.st) and x.epsilon.n.sub.max.sup.st, where .sup.(x).lamda..sup.st(m)=1 if the m.sup.th logical link of (s, t) uses the wavelength x. Let

.times..lamda..function..di-elect cons..times..times..times..times..lamda..function. ##EQU00003## if the m.sup.th logical link of (s, t) traverses either the fiber (i, j) or (j, i) uses wavelength x.

The decision variables for handling the SLA are as follows. Let .LAMBDA..sup.st(m) be the total length of m.sup.th be the total length of m.sup.th logical link of (s, t) for all (s, t).epsilon.S and m.epsilon.{1, 2, . . . , n.sup.st} The length of logical link is defined by

.LAMBDA..function..di-elect cons..times..pi..function. ##EQU00004## Let

.LAMBDA. ##EQU00005## be a length longer than the longest logical link of (s, t).

The jointness is computed in the model with two variables q and q.sup.1 where q represents the jointness for all logical links and q.sup.1 denotes the jointness for the two priority logical links. These two variables allow the local jointness for only two priority logical links (for all neighboring pairs) and for all logical links in the network to be analyzed separately. Let

.gtoreq..times..pi..function..pi..function. ##EQU00006## for all (i, j).epsilon. and (s, t).epsilon.S. It is the number of paths of (s, t) minus one that use the fiber (i, j). Let

'.times..times..gtoreq..times..pi..function..pi..function. ##EQU00007## for all (i, j).epsilon..epsilon. and (s, t).epsilon.S. If the two paths use the fiber (i, j),

'.times..times. ##EQU00008## is equal to one, otherwise it is null.

3) Constraints: The flow continuity constraints for the physical paths of the inter-network nodes links of the pair of network nodes (s, t) are:

.di-elect cons..di-elect cons..times..pi..function..di-elect cons..di-elect cons..times..pi..function..times..times..times..times..times..times..A-in- verted..di-elect cons..A-inverted..di-elect cons..times..times..times..times..times. ##EQU00009## Equation (1) defines the physical path associated with each logical link.

Wavelength assignment. A ((s, t), m).epsilon.S.times.{1 . . . n.sup.st},

.ltoreq..ltoreq..times..lamda..function. ##EQU00010## Equation (2) does the wavelength with assignments for all the paths.

The following equation ensures that the physical paths use only fibers where wavelengths are available.

.A-inverted..ltoreq..ltoreq..A-inverted..di-elect cons..times..times..times..times..times..times..pi..function..ltoreq..lam- da..function. ##EQU00011##

If the m.sup.th path of the pair (s, t) uses the wavelength x, since (1-.sup.(x).lamda..sup.st(m))=0, the constraint becomes

.pi..function..ltoreq..pi..function. ##EQU00012## has to be null if the fiber (i, j) does not support this wavelength.

B is a big arbitrary number and its use is explained in more detail later. Equation (4) ensures that one wavelength can only be used once per fiber.

.di-elect cons..times..times..lamda..function..lamda..function..ltoreq..ti- mes..times..A-inverted..di-elect cons.<.A-inverted..ltoreq..ltoreq. ##EQU00013##

For each fiber (i, j) and each wavelength x, only one

.lamda..function..times..times..times..times..lamda..function. ##EQU00014## can be used, for all the logical links of all the paths.

.times..times..times..times..lamda..function..times..A-inverted..di-elect cons..times..times..times..times.<.A-inverted..di-elect cons..times..times..times..times..times..times..lamda..function..gtoreq..- lamda..function..pi..function..pi..function..lamda..function..ltoreq..lamd- a..function..lamda..function..ltoreq..pi..function..pi..function. ##EQU00015##

Equations (5), (6) and (7) ensure that

.lamda..function..times..times..times..times..times..times..lamda..functio- n..times..times. ##EQU00016## and 0 otherwise.

The constraint on the relative path lengths as follows.

.A-inverted..di-elect cons..times..times..times..times..times..times..LAMBDA..LAMBDA..function.- .gtoreq..LAMBDA..ltoreq. ##EQU00017##

Equation (8) forces

.LAMBDA. ##EQU00018## to be longer than the physical paths of the pair of network nodes (s, t). The minimization process will search for solutions less than this largest value. Equation (9) requires this largest value to be within u % of the delay of the default path length for each (s, t).

4) Avoiding loops: The flow continuity constraints (1) are insufficient to guarantee that the physical paths avoid loops. To solve this problem, new constraints are proposed. The principle is to make sure that a path uses only fibers that are part of a subset of the physical topology called a covering tree.

5) Objective function: The objective function is to minimize:

.di-elect cons..times..di-elect cons..times.'.times..times..di-elect cons..times..di-elect cons..times..di-elect cons..times..di-elect cons..times.'.times..times..di-elect cons..times..di-elect cons..times. ##EQU00019##

The four components of the objective function correspond to the four steps outlined in the mapping sequence discussed above. B is a large number that needs to be much larger than the sum of all the jointness parameters. In this objective, the jointness of the links included in step 1 of our mapping sequence is multiplied by B.sup.3, step 2 is multiplied by B.sup.2 and so on. By multiplying the first term by B.sup.3, the first term of the objective function is minimized first. Thus, step 1 (step 2) has the highest importance (second highest importance) within this objective function, respectively. Whenever there is a tie (i.e., two solutions produce the same jointness for term one), then the following term is used to break the tie. The rest of the objective function is structured the same way.

EXAMPLE 2

The heuristic of this example uses the application of the Tabu Search (TS) methodology. See F. Glover, E. Taillard and D. DeWerra "A User's Guide to Tabu Search," Annals of Operations Research, Vol. 41, pp. 3-28, 1993. TS is based on a guided partial exploration of the space of admissible solutions. In this example, the exploration starts from an initial solution that is generally obtained with a greedy algorithm. Each solution visited is evaluated using the same objective function, equation (1), as in the ILP example. When a stop criterion is satisfied, the algorithm returns the best-visited solution.

For each admissible solution, a set of neighboring solutions is defined. A neighboring solution is defined as a solution that can be obtained from the current solution by applying a transformation (also called a move) to one aspect of the solution. The set of all admissible moves uniquely defines the neighborhood of each solution.

At each iteration of the TS algorithm, all solutions in the neighborhood of the current one are evaluated, and the best is selected as the new current solution. In order to efficiently explore the solution space, the definition of neighborhood may change during the solution space exploration; in this way it is possible to achieve an intensification or a diversification of the search in different solution regions.

A special rule, the Tabu list, is introduced in order to prevent the algorithm to deterministically cycle among already visited solutions. The Tabu list stores the last accepted moves; while a move is stored in the Tabu list, it cannot be used to generate a new move. The choice of the Tabu list size is important in the optimization procedure: too small could cause the cyclic repetition of the same solutions, while too large would severely limit the number of applicable moves, thus preventing a good exploration of the solution space.

During the search of an optimal solution, the Tabu search is allowed to investigate solutions outside the space of admissible solutions. Non-admissible solutions are solutions that require more wavelengths on some fibers than provided by the wavelength-division multiplexing (WDM) topology. All solutions, even non-admissible ones, always satisfy the SLA requirements. For some scenarios (when a fiber has only a few wavelengths) even finding a single admissible solution can be hard because of the wavelength assignment problem. To avoid getting stuck, the heuristic is allowed to temporarily go outside the space of admissible solutions. A strategic oscillation is operated between the space of admissible solutions and the space of non-admissible solutions. When inside the space of admissible solutions, current solution is improved; when outside this space, a special kind of move as described below is applied to come back instead.

The following are the seven components of the TS heuristic designed to solve the mapping problem.

Precomputation step. Before running the TS heuristic, the default length path is computed for each pair of neighboring network nodes according to the three strategies described above. For each pair of neighboring network nodes, the set of physical paths are built to satisfy the relative delay constraint. This set is then sorted according to the length of each physical link, from shortest to longest. The IP routes are built for all arbitrary network node pairs according to the ISIS routing protocol.

Initial solution. The choice of the initial solution is important since it can significantly reduce the convergence time. For each logical link, the shortest physical path between neighboring network nodes was chosen to be the initial mapping. Typically, this solution is outside the space of admissible solutions, but it is optimal in terms of delay.

Moves and Neighborhood generation. Since during the exploration admissible and non-admissible solutions were visited two different kinds of moves are defined. When the search is focused on the space of admissible solutions, the selected move will find a solution without considering the wavelength constraint. When the search takes place outside the space of admissible solutions the move will try to m