@conference {12264,
	title = {CAM04-6: Single-Path Routing of Time-varying Traffic},
	booktitle = {Global Telecommunications Conference, 2006. GLOBECOM {\textquoteright}06. IEEE},
	year = {2006},
	month = {2006/12/27/1},
	pages = {1 - 6},
	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.},
	keywords = {algorithm;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;},
	doi = {10.1109/GLOCOM.2006.29},
	author = {Kashyap,A. and Bhattacharjee, Bobby and La,R. and Shayman,M. and Tabatabaee,V.}
}
