COMP2000-21 κ-連結グラフに対する小さなルーティングテーブルを持つ最適な耐故障性ルーティング

概要

論文の詳細を見る
通信網や計算機網において情報伝達の信頼性をいかに高めるかは重要な問題である.本稿では計算機網は計算機を点, 通信回線を辺とした無向グラフを考える.2点間の通信はグラフ上の路を用いて行ない, 路線と呼ばれるその通信路を決定することをルーティングと呼ぶ.ルーティングの耐故障性に対する評価尺度の一つとして, 点集合が計算機網を表したグラフの故障していない点からなり, 2点間の路線が定義されていて故障を含まないとき, その2点間に有向辺を持つ有向グラフとして定義される生存路線グラフ(surviving route graph)の直径が提案されている.また, ルーティングを定義する時は定義される路線数と点に対して定義される路線数の最大値(路線次数と呼ぶ)をできるだけ小さくすることが望ましい.本稿では, n≥2κ^2なるn点κ連結グラフに対して路線数Ο(κ^2n), 路線次数Ο(κ√n)であり任意のκ-1以下の故障に対して生存路線グラフの直径が3となるルーティングが構成できることを示す.また, 任意のn点連結グラフに対して路線数Ο(n√n), 路線次数Ο(√n)であり任意の1個の故障に対して生存路線グラフの直径が2となるルーティングが構成できることを示す.
社団法人電子情報通信学会の論文
2000-06-19