Competitive Analysis of Minimal Oblivious Routing Algorithms on Hypercubes
Tzuoo-Hawn Yeh · 2001
Abstract We study the performance of oblivious routing algo-rithms that follow minimal (shortest) paths, referred to as minimal oblivious routing algorithms in this pa-per, using competitive analysis on a d-dimensional, N = 2d-node hypercube. We assume that packetsare injected into the hypercube arbitrarily and continuously, without any (e.g., probabilistic) assump-tion on the arrival pattern of the packets. Minimal algorithms reduce the total load in the network in thefirst place and they preserve locality. First we show that the well known deterministic oblivious routingalgorithm, namely, the greedy routing algorithm, has competitive ratio \\Omega (N 1/2). Then we show a problemlower bound of \\Omega ( N log2(5/4) / log5 N). We also give anatural randomized minimal oblivious routing algorithm whose competitive ratio is close to the problemlower bound we provide.