CAM04-6: Single-Path Routing of Time-varying Traffic

TitleCAM04-6: Single-Path Routing of Time-varying Traffic
Publication TypeConference Papers
Year of Publication2006
AuthorsKashyap A, Bhattacharjee B, La R, Shayman M, Tabatabaee V
Conference NameGlobal Telecommunications Conference, 2006. GLOBECOM '06. IEEE
Date Published2006/12/27/1
Keywordsalgorithm;linear, algorithm;time-varying, algorithms;telecommunication, bound;IP, case, complexity;iterative, intra-domain, IP, methods;linear, multipath, network, network;ISP, networks;Internet;computational, optimal, performance, problem;heuristic, profile;worst, programming;optimal, programming;probability;randomised, rounding, routing;iterated, routing;probability;randomized, routing;telecommunication, single-path, topology;NP-hard, topology;telecommunication, traffic, traffic;
Abstract

We consider the problem of finding a single-path intra-domain routing for time-varying traffic. We characterize the traffic variations by a finite set of traffic profiles with given non-zero fractions of occurrence. Our goal is to optimize the average performance over all of these traffic profiles. We solve the optimal multi-path version of this problem using linear programming and develop heuristic single-path solutions using randomized rounding and iterated rounding. We analyze our single-path heuristic (finding the optimal single-path routing is NP-hard), and prove that the randomized rounding algorithm has a worst case performance bound of O(log(KN)/log(log(KN))) compared to the optimal multi-path routing with a high probability, where K is the number of traffic profiles, and N the number of nodes in the network. Further, our simulations show the iterated rounding heuristics perform close to the optimal multi-path routing on a wide range of measured ISP topologies, in both the average and the worst-case. Overall, these results are extremely positive since they show that in a wide-range of practical situations, it is not necessary to deploy multi-path routing; instead, an appropriately computed single-path routing is sufficient to provide good performance.

DOI10.1109/GLOCOM.2006.29