大規模ネットワークシミュレーション向けのルーティングテーブルの容量削減

機関リポジトリ 情報処理学会 HANDLE オープンアクセス

書誌事項

タイトル別名
  • Reducing the Size of Routing Tables for Large-scale Network Simulation
  • ネットワーク品質・制御

この論文をさがす

抄録

ネットワーク規模の増大やネットワーク構造の複雑化にともない，大規模ネットワークにおけるシミュレーションが必要とされている．しかし，計算機で使用できる資源は限られているため，シミュレータに適用可能なネットワークの大きさ，シミュレーションシナリオの規模は制限される．シミュレーションにおいて，計算機資源（特にメモリ容量）を消費する要因の1 つは，各ノードにおいて，到着したパケットを宛先ノードごとにどの隣接ノードに転送すべきかを示す，ルーティングテーブルであることが知られている．N をネットワークに含まれるノードの数とすると，表形式のルーティングテーブルでは，その容量は全体としてO(N 2 )となる．一方，任意の2 ノード間の経路がすべて，全ノードを含むある1 つの木（被覆木）に含まれる特殊な場合にのみ，ルーティングテーブルのデータ構造を被覆木そのものとすることで，ルーティングテーブルの容量をO(N)とする被覆木ルーティング法も提案されているが，任意のルーティングを表現できない制約がある．本論文では，被覆木ルーティング法をもとに，なるべく多くの経路を含む被覆木によるルーティングテーブルと，表形式のルーティングテーブルを組み合わせたルーティングテーブルを構築し，任意のルーティングを表現でき，かつそのルーティングテーブルの容量を削減する方法を提案する．提案手法の評価を行った結果，階層化トポロジにおいて，単純なルーティングテーブルと比較し，容量を90%削減できた．

In simulating large-scale networks, due to the limitation of available resources on computers, the size of the networks and the scale of simulation scenarios are often restricted. Especially, routing tables, which indicate the directions to forward packets, are considered to consume memory space. A general routing table requires O(N 2 ) space where N is the number of nodes. An algorithmic routing recently proposed by Heung et al. only requires O(N) space for rep-resenting routing tables, however this can be applied in the case that all the routes between two nodes are contained in a fixed spanning tree (i.e. very limited routing is allowed). In this paper, we propose a new method to reduce a capacity of routing tables which is applicable to any routing table. In our method, a (near-optimal) algorithmic routing based table is used to represent a part of the given routing table. Our experimental results have shown that our method could reduce about 90% of the routing table size compared with a general routing table in hierarchical networks.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ