yasu's blog

On the Computational Complexity and Effectiveness of ``N-hub Shortest-Path Routing''

Reuven Cohen and Gabi Nakibly. On the computational complexity and effectiveness of n-hub shortest-path routing. In INFOCOM, 2004.

既存の shortest path ルーティングで、中継ノードを N 個指定させ loose source ルーティングさせる方法を N-hub shortest path ルーティングと定義。 各フローの経路を曲げて遠回りさせてやることで、ネットワークの利用効率を向上させる。 ネットワークの最大負荷の最小化。

計算量の議論が豊富。N-hub shortest path ルーティングを、既存の (unsplittable) Multicommodity Flow Routing 問題に関連付け、計算量の下界などを示す。

SAT を reduction して 1-hub 問題を生成できることから、NP-complete と証明した。 1-hub が NP-complete なので、Integer 1-hub, Integer N-hub も NP-complete。 N-hub は Integer N-hub の generalization なので、それも NP-complete。 (最後だけちょっと疑問。1-hub -> Integer 1-hub -> Integer N-hub -> N-hub と連鎖 させてるが、単に文章の書き方問題なのか。。。 そもそも、generalization だと問題のクラスは同じになるんだっけ？ 同じ問題を包含する、だとわかる気がするが。。。Computers and Intractability 読んで 勉強する必要アリ。)

NP-complete として知られる Edge-Disjoint Paths 問題に対する PTAS が存在しない ことから、2-e 以内に厳密に収まる approximation も存在しないと証明した。

トラフィックフローの開放を考えると、どのようなアルゴリズムも、最適より良くも悪くも Θ (|E|) の比率となる。開放を考えないと、O(log|V|)に挑戦できる。以下のアルゴリズムは それに挑戦する。

[20][21]で提案された algorithm を、online approximation algorithm として N-hub に応用。Algorithm-1 は最適からの利用率の比率を考慮して計算、 Algorithm-2 はネットワーク内の最大負荷を最小化、Algorithm-3 は Algorithm-2 を拡張して、ネットワーク内の最大負荷が最小となる場合でも、パス間の 最大負荷の最小化を目的とする。 そして計算量の最適からの比率を議論。

シミュレーションでこれを評価。BRITE で WAXMAN モデルのネットワークを生成。 フローは始点終点をランダムに、Zipf (ジップの法則、べき乗関数の親戚）に従う ように作った。最適 OPT は LP で計算。|V|=50 で |E|/|V| は 2 や 5、 |V|=10, |E|= 20、|V|=50, |E|= 250 などでシミュレーション。 1-hub で 最適とほぼ変わらない性能が出せた、N-hub の N の数では大した差異が 見られなかった、グラフが小さくなっても性能向上した比率が変わらなかった、 Shortest path ルーティングよりかなり良い性能が示せた、などが成果。

MCF の参考文献：

[18] S. G. Kollopoulus and C. Stein, ``Improved approximation algorithms for the unsplittable flow problems,'' in Proceedings of FOCS, 1997, pp. 426・35. [19] N. G. Y. Dinitz and M. Goemans, ``On the single-source unsplittable flow problem,'' Combinatorica, vol. 19, pp. 17・1, 1999. [20] J. A. et al, ``Online load balancing with applications to machine scheduling and virtual circuit routing,'' Journal of the ACM, vol. 44, no. 3, pp. 486・04, 1997.

VCR の参考文献：

[21] J. T. Havill and W. Mao, ``Greedy online algorithms for routing permanent virtual circuits,'' Networks, vol. 34, pp. 136・53, 1999. [22] W. Mao and R. Simha, ``Routing and scheduling file transfers in packetswitched networks,'' Journal of Computing and Information, vol. 1, pp. 559・74, 1994.

計算量：

[23] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Co., 1979.