Wavelength routing in optical networks of diameter two

We consider optical networks with routing by wavelength division multiplexing. We show that wavelength switching is unnecessary in routings where communication paths use at most two edges. We then exhibit routings in some explicit pseudo-random graphs, showing that they achieve optimal performance subject to constraints on the number of edges and the maximal degree. We also observe the relative inefficiency of planar networks.     

Sensible decisions based on QoS

Network Quality of Service (QoS) criteria of interest include conventional metrics such as throughput, delay, loss, and jitter, as well as new QoS criteria based on power utilization, reliability and security. Variable and adaptive routing have again become of interest in networking because of the increasing importance of mobile ad-hoc networks. In this paper we develop a probability model of adaptive routing algorithms which use the expected QoS to select paths in the network. Our objective is not to analyze QoS, but rather to design randomized routing policies which can improve QoS. We define QoS metrics as non-negative random variables associated with network paths which satisfy a sub-additivity condition along each path. We define the QoS of a path, under some routing policy, as the expected value of a non-decreasing measurable function of the QoS metric. We discuss sensitive and insensitive QoS metrics, the latter being dependent on the routing policy which is used. We describe routing policies simply as probabilistic choices among all possible paths from some source to some given destination. Incremental routing policies are defined as those which can be derived from independent decisions taken at certain points (or nodes) along paths. Sensible routing policies are then introduced: they take decisions based simply on the QoS of each available path. Sensible policies, which make decisions based on the QoS of the paths, are introduced. We prove that the routing probability of a sensible policy can always be uniquely obtained. A hierarchy of m-sensible probabilistic routing policies is then introduced. A 0-sensible policy is simply a random choice of routes with equal probability, while a 1-sensible policy selects a path with a probability which is inversely proportional to the (expected) QoS of the path. We prove that an m + 1-sensible policy provides better QoS on the average than an m-sensible policy, if the QoS metric is insensitive. We also show that under certain conditions, the same result also holds for sensitive QoS metrics.Accepted: May 2003, This work was supported by the U.S. Army and Navy under contracts N611339-00-K-0002, N61339-02-C0050, N61339-02-C0080, N61339-02-C0117, and by NSF grants EIA0086251, EIA0203446, ECS0216381.     

Jittering performance of random deflection routing in packet networks

This paper reports a study of random deflection routing protocol and its impact on delay-jitter over packet networks. In case of congestion, routers with a random deflection routing protocol can forward incoming packets to links laying off shortest paths; namely, packets can be “deflected” away from their original paths. However, random deflection routing may send packets to several different paths, thereby introducing packet re-ordering. This could affect the quality of receptions, it could also impair the overall performance in transporting data traffic. Nevertheless, the present study reveals that deflection routing could actually reduce delay-jitter when the traffic loading on the network is not heavy.     

Increasing Internet Capacity Using Local Search

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing

We generalize Dijkstra's algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

Spare routing problem with p minimal paths for time-based stochastic flow networks

A time-based stochastic flow network (TBSFN), in which each arc has several possible capacities/states and a lead time, is addressed to discuss the system reliability of spare routing for a computer network. The minimum transmission time to send a given amount of data through a single minimal path is uncertain. Although the transmission time will be shortened even if the data are sent through p (p > 1) disjoint minimal paths simultaneously, it is still variable in a TBSFN. This paper is concerned with evaluating the probability that a specified amount of data can be sent through p minimal paths simultaneously within a time threshold. Such a probability is named the system reliability, which can be treated as a performance index for measuring the transmission ability. We present an efficient methodology to assess the system reliability. Furthermore, a spare routing for boosting the system reliability is established in advance to indicate the main and spare p minimal paths. Subsequently, the system reliability of the spare routing can be computed easily, which shows the contribution of the spare design. From the viewpoint of decision support, we may conduct the sensitive analysis to find out the most important arc which will increase/decrease the system reliability most significantly.     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

Multiobjective design of survivable IP networks

Modern communication networks often use Internet Protocol routing and the intra-domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.     

Routing complexity of faulty networks

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for the d‐dimensional mesh. We use tools from percolation theory to show that in the d‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph G_n,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On finding dissimilar Pareto-optimal paths

The aim of the present paper is to provide a methodology for finding a set of alternative paths between an origin and a destination site on which routing one or a set of dangerous goods. Finding a set of paths allows one to equally distribute the total risk among the population exposed. The concept of equity of risk is here related to the concept of determining spatially dissimilar paths. We divide our approach into two phases. In the first phase we find a set of Pareto-Optimal paths between an origin and a destination, by implementing a multicriteria shortest path algorithm. In the second one, for each path previously found, and by using a geographical information system, we construct a Buffer Zone approximating the impact area of a material being released after an accident. Based on these Buffer Zones, a dissimilarity index between every pair of paths can be derived in order to find the most spatially different routes. We then compare our method with an iterative penalty method and discuss computational results based both on a real application and on test problems.     

Coloring all directed paths in a symmetric tree,with an application to optical networks*

Let T be a symmetric directed tree, i.e., an undirected tree with each edge viewed as two opposite arcs. We prove that the minimum number of colors needed to color the set of all directed paths in T, so that two paths of the same color never use the same directed arc of T, is equal to the maximum number of different paths that contain the same arc of T. The proof implies a polynomial time algorithm for actually coloring the paths with the minimum number of colors. When only a subset of the directed paths is to be colored, the problem is known to be NP‐complete; we describe certain instances of the problem which can be efficiently solved. These results are applied to WDM (wavelength‐division multiplexing) routing in all‐optical networks. In particular, we solve the all‐to‐all gossiping problem in optical networks. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 183–196, 2001     

A New Multiobjective Dynamic Routing Method for Multiservice Networks: Modelling and Performance

There are potential advantages in formulating the routing problems in modern multiservice networks as multiple objective problems. This paper presents a novel hierarchical bi-level multiobjective dynamic routing model for multiservice networks. It is based on a bi-objective shortest path algorithm, with dynamically adapted soft-constraints, to compute alternative paths for each node pair and on a heuristic to synchronously select alternative routing plans for the network in a dynamic alternative routing context. It is a routing method which periodically changes alternative paths as a function of periodic updates of certain QoS related parameters obtained from real-time measurements. The performance of the proposed routing method is compared with two reference dynamic routing methods namely RTNR and DAR by means of a discrete-event simulator.A previous short version of this work was presented at INOC’03 (International Network Optimisation Conference). Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

Dynamic programming algorithms for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints (e.g. capacities or time windows) are solved via column generation and branch-and-price, it is common that the pricing problem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the nodes. The pricing problem is usually solved via dynamic programming in two possible ways: requiring elementary paths or allowing paths with cycles. We experimentally compare these two strategies and we evaluate the effectiveness of some algorithmic ideas to improve their performance.     

Topology design for on-demand dual-path routing in wireless networks

One way to achieve reliability with low-latency is through multi-path routing and transport protocols that build redundant delivery channels (or data paths) to reduce end-to-end packet losses and retransmissions. However, the applicability and effectiveness of such protocols are limited by the topological constraints of the underlying communication infrastructure. Multiple data delivery paths can only be constructed over networks that are capable of supporting multiple paths. In mission-critical wireless networks, the underlying network topology is directly affected by the terrain, location and environmental interferences, however the settings of the wireless radios at each node can be properly configured to compensate for these effects for multi-path support. In this work we investigate optimization models for topology designs that enable end-to-end dual-path support on a distributed wireless sensor network. We consider the case of a fixed sensor network with isotropic antennas, where the control variable for topology management is the transmission power on network nodes. For optimization modeling, the network metrics of relevance are coverage, robustness and power utilization. The optimization models proposed in this work eliminate some of the typical assumptions made in the pertinent network design literature that are too strong in this application context.     

Linear broadcast routing

In this paper we examine the problem of performing broadcasts in networks where the messages are constrained to follow linear paths. Many high speed networks, where routing is done in specialized hardware, have this characteristic. We show that the general problem is NP-complete but find a polynomial time approximation algorithm which is guaranteed to provide a solution which is within twice the optimal. We also suggest some generalizations of this work and propose several open problems.     

An Incremental Procedure for Improving Path Assignment in a Telecommunications Network

A fundamental problem in the design and management of a telecommunications network is that of determining an optimal routing pattern for a given set of origin-destination demand pairs. In addition, reliability considerations may require provisioning a set of backup paths to protect the working traffic against network failures. In the literature, the problem of finding an optimal routing for a network with fixed link capacities and a list of point-to-point demands (origin-destination pairs), each with a set of candidate routing paths has been referred to as the path-assignment problem. There are three versions of this problem that correspond to the type of network protection required (no protection, dedicated protection, and shared protection). The solution to those models can be used to determine an initial design for a new network. Over time, however, changes in the demand pattern and/or upgrades to the network equipment may create a situation in which the working and/or backup paths are sub-optimal.For network managers who are reluctant to make wholesale changes to an established and reliable routing assignment, a complete modification to obtain an optimal assignment that uses fewer network resources is viewed as highly risky. This investigation presents a new procedure to take a given feasible, but sub-optimal design and improve it by making a series of incremental improvements each of which only changes a small number of path assignments. Network managers view this strategy as much less risky since only a few customers are affected by any one change. Test cases that require no protection, dedicated protection, and shared protection were examined in an empirical analysis. For all cases, near-optimal solutions were achieved irrespective of the quality of the given sub-optimal starting solutions.     

Finding Optimal Routings in Hamming Graphs

A routing R in a graph consists of a simple path p_uvfromu to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p_uvare shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé’s condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.