Competitive Analysis of Minimal Oblivious Routing Algorithms on Hypercubes

スポンサーリンク

概要

• 論文の詳細を見る

• We study the performance of oblivious routing algorithms that follow minimal (shortest) paths, referred to as minimal oblivious routing algorithms in this paper, using competitive analysis on a d-dimensional, N = 2^d-node hyoercube. We assume that packets are injected into the hypercube arbitrarity and continuously, without any (e.g., probabilistic) assumption on the arrival pattern of the packets. Minimal algorithms reduce the total load in the network in the first place and they preserve locality. First we show that the well known determnistic oblivious routiong algorithm, namely, the greedy routing algorithm, has competitive ratio Ω(N^<1/2>. Then we show a problem lower bound of Ω(N^<log2(5/4)/log^5 N). We also give a natural randomized minimal oblivious routing algorithm whose competitive ratio is close to the problem lower bound we provide.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Lei Chin-laung

  The Authors Are With The Department Of Electrical Engineering National Taiwan University

• YEH Tzuoo-Hawn

  The authors are with the Department of Electrical Engineering National Taiwan University,

関連論文

• A Naming, Storage, and Retrieval Model for Software Assets
• A False-Sharing Free Distributed Shared Memory Management Scheme
• Competitive Analysis of Minimal Oblivious Routing Algorithms on Hypercubes

スポンサーリンク