故障耐性の高い路線割当をもつ通信網の構成問題

概要

論文の詳細を見る
通信網や計算機網における情報伝達の信頼性をいかに経済的に効率よく高めるかは重要な問題である．通常，通信網（計算機網）は局（計算機）を点，通信回線を辺としたグラフで表され，任意の二点間の通信はグラフの通路を用いて行われる．通信網の二点間の通信経路を決定することを路線割当（routing）と呼ぶが，路線割当が前もって計算されている通信網の信頼性の尺度として，通信網を表すグラフとその路線割当，および故障点と故障辺によって定義されるSR-グラフ（surviving route graph）と呼ばれるグラフの直径を評価しようという提案がなされている．SR-グラフは，通信網を表したグラフの故障していない点から成り，二点間の通信経路が故障していないとき，その二点間に有向辺を持つ有向グラフとして定義される．SR-グラフの直径が小さいとき故障耐性が高いということにする．本論文では，SR-グラフの辺数の下界を与え，任意の正整数n，k（n＞k）に対して，その下界に一致する辺数をもつn個の点のグラフを構成し，そのグラフに対して（準）最短路線割当を定義し，任意のk－1個の故障に対するSR-グラフの直径が最悪の場合でも4以下となることを示す．ここで，路線割当が（準）最短であるとは，路線が定義されている任意の2点に対する路線の長さが元のグラフにおけるその2点間の最短通路の長さに等しい（高々1だけ大きい）ことをいう．また，（準）最短路線割当に制限しなければ任意のn，k（n2k）に対してn個の点を持ちk－1個の故障に対してSR-グラフの直径が3以下となる路線割当を定義できる辺数最小のグラフを構成できることを示す．
Institute of Electronics, Information and Communication Engineersの論文
1987-11-20

著者

羅予頻
清華大学

故障耐性の高い路線割当をもつ通信網の構成問題

スポンサーリンク

概要

著者

関連論文

スポンサーリンク