International OR
Optimizing Internet Networks
France Telecom:
Changing the rules to accommodate demanding new traffic streams
By Eric Gourdin
In the last few years, the use of Internet has literally exploded in Europe as it has in the United States, imposing itself as the media for all next-generation's communications. Paradoxically, the founding principles that made the "old" Internet a success — low-cost connectivity between non-commercial communities wishing to exchange digital information — are now widely criticized for not providing guaranteed quality and performance.
The Internet's rather simple decentralized routing mechanisms with automatic reconfiguration in case of topology adjustments or failures proved to be very efficient for the applications of the last decades. It was designed to "do its best" to accommodate all the requirements placed upon the system. It was not designed to guaranty a particular level of performance, certainly not end-to-end quality of service.
Today, with the development of multimedia technologies, the Internet is expected to support real-time voice and video applications. To meet the challenge, the Internet community is spending an enormous amount of energy to change the rules in order to accommodate these new, demanding traffic streams.
France Telecom is the leading actor of the Internet business in France and is rapidly extending its activities in the rest of the world. As the R&D entity of France Telecom, we are actively involved in the evolution of Internet technologies and to foresee their implications in the deployment of France Telecom's private Internet network. Operations research expertise is crucial in this domain.
One field we have recently started to investigate that impacts many network optimization processes is "traffic engineering." TE represents the ability to optimize the use of network resources only by means of efficient routing decisions. For this purpose, one must first precisely define the mechanisms that, once implemented in the network, will allow the routing equipment (called routers) to choose their routing paths for any given destination. Secondly, and this is mainly where the OR expertise is required, once the routing mechanism is chosen, one (in fact, the network administrator) must efficiently tune all parameters in order to ensure the best possible network performances.
Concerning the first topic, the Internet community has recently proposed new routing protocols (MPLS for Multi-Protocol Label Switching) that allow much more flexibility than the "classical" ones. In the "classical" Internet routing protocol (OSPF, IS-IS, etc.), routing decision are based on standard shortest-path rules. More precisely, the network administrator has to assign a value (or administrative weight) to each link of its domain (or rely on the default value of 1). The routers, aware of all the domain topology and associated values, build their routing tables by computing a shortest path for any reachable destination of the domain. The mechanism has restrictions that will be discussed later.
With MPLS, it is possible to define any kind of path (according to the weights or not) by marking the encountered nodes with labels. Moreover, it is also possible, during the definition of the LSP (Label Switched Path), to take into account some minimum bandwidth requirements, and afterwards to reserve this bandwidth for a given traffic stream or set of streams. This new protocol already seems to impose itself as a future standard.
Having defined the main features of MPLS, the Internet community is now working on the second of the topics mentioned above, namely the rules and necessary guidelines for its efficient implementation, which appears to be much more difficult than initially expected. The choice of a routing mechanism and the effective rules for its implementation will heavily impact the network performances and many related decisions on a variety of time scales. Some OR problems will henceforth also naturally appear at several time scales. Of course, on the short-term or even "real-time" time scale, everything should be configured for an efficient network behavior. However, some exceptional events might occur for which some additional automatic mechanisms could be implemented in the routers (for instance, the pre-definition of a backup route in case of failure).
On the medium-term horizon and even during the initial configuration of the network, parameters should be set up or updated to accommodate some drastic changes in the traffic pattern. The parameters need to be re-optimized periodically to fit more closely with changing traffic patterns, but how often do you do this (every hour? day)? Finally, on the long-term horizon, the whole planning of the network should take into account the type of routing mechanisms that will be implemented in the routers. In fact, at such a horizon, the planner should even try to figure out the possible evolutions in the routing mechanisms, at least those one that might have an impact on the whole network planning process.
During the last few years in our France Telecom R&D team, we have focused our attention on some of the topics related with TE and network optimization problems. Since we could find little research or results on the subject, we first investigated the impact and the limitations of shortest-path routing compared to any kind of single- or multiple-path routing. We did this for two reasons: First, many Internet domains are still working with "classical" routing protocols (based on shortest-path routes). Thus, it seems worthwhile to figure out how much one can gain from the use of MPLS. There are obvious technical advantages such as the bandwidth reservation feature, but from a purely performance point of view, it is not a priority obvious how much better MPLS would work. Second, the effective implementations of MPLS solutions are far from being standardized or widely tested, and many of them still rely, for the dynamic definition of LSP on the shortest-path rules of the underlying "classical" routing protocol. Consequently, one of the first questions we tried to answer is the following: How much flexibility is necessary in the choice of routes to realize some optimal behavior of a network?
Assuming a network administrator believes he has addressed this question and has hence decided to use a certain routing protocol, the question of the tuning of the parameters then quite naturally arises. Indeed, even if a routing protocol specifies the rules allowing the selection of one route over another, there generally remain some parameters to set in order to implement the protocol in practice. For instance, the "classical" routing protocols are essentially based on the weights. In MPLS, one must decide how the LSP is created, between which nodes, etc. For this purpose, it is also necessary to define some desirable objective, hopefully one that is representative of some network performance criterion. For instance, in a network planning process, we can imagine that the OR team has defined some "optimal" routing pattern. If the specification of the routing protocol has not been considered in this optimization process, it is at least necessary to take it into account at that point and determine whether the routing pattern is compliant with the routing protocol. If for some operating reasons the network administrator wishes to impose some specific routes, he would also have to determine how to configure the routing parameters in order to achieve his routing pattern. Hence, a crucial question to address, once a routing pattern has been established one way or another, is: Is it possible to realize a given choice of routes (routing pattern) with a given routing protocol? If so, how do you do it?
To provide some answers to the first question, we have considered several network optimization problems (network design, network loading, maximum throughput, etc.) to which we have added some restrictions in terms of routing capabilities. More precisely, we have compared three routing strategies.
In the first routing strategy, each flow can be split into as many routes as needed (multicommodity flow). In the second strategy, each commodity must follow a single route. This rule also applies in the third strategy with the additional requirement that each single route must be defined as a unique shortest path. The uniqueness requirement can seem (and is) a little restrictive. This choice is motivated by the fact that multiple shortest paths would also imply some additional rules to efficiently manage the load balancing between the several equal cost path. It not clear to us if such a load-balancing capability is easy to manage from an operational point of view. The uniqueness requirement removes an additional difficult dimension to the problem and thus seems more "attractive."
The first strategy is obviously the least constrained one and will hence always lead to the best results. Similarly, the second strategy will lead to better results than the third one. However, how much better these strategies are is not so obvious to guess. From a purely theoretical point of view, it is well known that only a few routes are necessary for each demand to reach the optimality of a multi-commodity flow problem. In the example in Figure 1, we have optimally routed the three demands of three, nine and four units in the capacitated network described on the left of the figure in order to maximize the minimum over all links of the remaining capacity. As expected, the single-path solution (in the middle) is much weaker than the multiple-paths solution (on the right).
Figure 1: Single path versus multiple paths.
To address the second main question — the compliance of a given set of routes with a given routing protocol — we have again, first focused on shortest-path routing protocols. The question then reduces to: Given a network topology and a routing pattern, is it possible to find weights on each link such that each route of the routing pattern is a shortest path, and even preferably, a unique shortest path? This problem can be relatively easily answered by solving a linear problem (possibly with integer weight variables and with a constraints-generation technique to avoid the enumeration of all possible paths). For instance, in the case of the single-path routing pattern of Figure 1, the solution with integer weights, minimizing the maximum weight is depicted in Figure 2.
Figure 2: Set of weights for unique shortest
Consider a slightly different example in Figure 3. The minimal remaining capacity in the case of optimal single -path routing is 0. Besides, if you observe the routing pattern, it appears that the blue and the purple paths define two distinct sub-paths between nodes A and B. Since these two sub-paths cannot both be unique shortest paths between A and B, this configuration is obviously incompatible with unique shortest-path routing (in other words, there does not exist a set a weights such that each given path is a unique shortest path). It follows from this example that a routing pattern must satisfy certain conditions in order to be compatible. For instance, we say that a routing pattern is sub-optimal if any two paths having two nodes in common share the same sub-path between these nodes. This condition is obviously not satisfied by the example of Figure 3. Since this sub-optimality condition is necessary to ensure the compatibility, the routing pattern is not compatible. It is even not too difficult to check on a network of this size that there does not exist a compatible single-path routing solution feasible for this example.
Figure 3: Incompatible single path routing pattern.
It is natural to ask whether the sub-optimality condition is also sufficient to guaranty the compatibility of a routing pattern, and, indeed, the answer is not so obvious (we did not find any reference on this subject in the literature either). Figure 4 shows an example of a sub-optimal routing pattern that is not compatible, .i.e., there does not exist a set of weights such that each one of the paths is the unique shortest path.
Figure 4: Sub-optimal, but not compatible with single shortest path routing.
All these considerations might seem rather theoretical and far from the operational considerations. These are, however, exactly the questions that arise every day in the field of network operation and for which accurate answers are needed. For instance, the tool we developed to address the problem of shortest-path weights computations allowed us to solve some practical problems on the national France Telecom Internet network where routing patterns were designed according to several operational constraints (an illustrative output of our tool is provided in Figure 5).
Figure 5: Set of shortest-path weights for given routing pattern.
We still need to get more insight on some of the basic crucial questions we have barely just sketched. At the same time, since the competition date does not leave us much time, we must also answer many other questions related to the routing mechanisms, especially the ones involving MPLS. We have to come up with solutions allowing efficient management of the Internet traffic, taking into account many other technical aspects that were not even mentioned here (reliability, robustness, domain partitioning, etc.) There is, without any doubt, enough material at hand for still many years of intensive operations research in telecommunication networks.
References
- Ben-Ameur, Walid, Eric Gourdin, Bernard Liau and Nicholas Michel, "Optimizing administrative weights for efficient single-path routing," Proceedings of Networks 2000.
- Ben-Ameur, W. and B. Liau, "Calcul des métriques de routage pour Internet," to appear in Annals of Telecommunications.
- Ben-Ameur, W., E. Gourdin and B. Liau, "Internet Routing and Topology Problems," Proceedings of DRCN2000.
- Ben-Ameur, W. and E. Gourdin, "Internet Routing and Related Topology Issues," submitted to SIAM J. Discrete Mathematics.
Eric Gourdin is an OR analyst at France Telecom. Walid Ben Ameur, Jérome Geffard, Bernard Liau and Nicolas Michel contributed to this article.
OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.