| 講演名 | 2000/6/19 COMP2000-21 κ-連結グラフに対する小さなルーティングテーブルを持つ最適な耐故障性ルーティング 和田 幸一, 陳 慰, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 通信網や計算機網において情報伝達の信頼性をいかに高めるかは重要な問題である.本稿では計算機網は計算機を点, 通信回線を辺とした無向グラフを考える.2点間の通信はグラフ上の路を用いて行ない, 路線と呼ばれるその通信路を決定することをルーティングと呼ぶ.ルーティングの耐故障性に対する評価尺度の一つとして, 点集合が計算機網を表したグラフの故障していない点からなり, 2点間の路線が定義されていて故障を含まないとき, その2点間に有向辺を持つ有向グラフとして定義される生存路線グラフ(surviving route graph)の直径が提案されている.また, ルーティングを定義する時は定義される路線数と点に対して定義される路線数の最大値(路線次数と呼ぶ)をできるだけ小さくすることが望ましい.本稿では, n≥2κ^2なるn点κ連結グラフに対して路線数Ο(κ^2n), 路線次数Ο(κ√n)であり任意のκ-1以下の故障に対して生存路線グラフの直径が3となるルーティングが構成できることを示す.また, 任意のn点連結グラフに対して路線数Ο(n√n), 路線次数Ο(√n)であり任意の1個の故障に対して生存路線グラフの直径が2となるルーティングが構成できることを示す. |
| 抄録(英) | We study the problem of designing fault-tolerant routings with small routing tables for a κ-connected network of n processors in the surviving route graph model. The surviving route graph for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G, ρ)/F).we want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node(called route degree)as least as possible. In this paper, we show that we can construct a routing λ for every n-node κ-connected graph such that n≥2κ^2, in which the route degree is Ο(κ√n), the total number of routes is Ο(κ^2n) and D(R(G, λ)/F)≤3 for any fault set F(|F|<κ). We also show that we can construct a routing ρ_1 for every n-node biconnected graphs, in which the total number of routes is Ο(n)and D(R(G, ρ_1)/{f})≤2 for any fault f, and using ρ_1 a routing ρ_2 for every n-node biconnected graphs, in which the route degree is Ο(√n), the total number of routes is Ο(n√n)and D(R(G, ρ_2)/{f})≤2 for any fault f. |
| キーワード(和) | 耐故障性 / 固定ルーティング / ルーティングテーブル / グラフの直径 / 分散計算 |
| キーワード(英) | Fault tolerance / fixed routing / routing table / diameter / distributed computing |
| 資料番号 | COMP2000-21 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | COMP2000-21 κ-連結グラフに対する小さなルーティングテーブルを持つ最適な耐故障性ルーティング |
| サブタイトル（和） | |
| タイトル（英） | COMP2000-21 Optimal Fault-Tolerant Routings for κ-connected Graphs with Small Routing Tables |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 耐故障性 / Fault tolerance |
| キーワード(2)（和/英） | 固定ルーティング / fixed routing |
| キーワード(3)（和/英） | ルーティングテーブル / routing table |
| キーワード(4)（和/英） | グラフの直径 / diameter |
| キーワード(5)（和/英） | 分散計算 / distributed computing |
| 第 1 著者 氏名（和/英） | 和田 幸一 / Koichi Wada |
| 第 1 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 2 著者 氏名（和/英） | 陳 慰 / Wei Chen |
| 第 2 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-21 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |