大規模ネットワークシミュレーション向けのルーティングテーブルの容量削減  [in Japanese] Reducing the Size of Routing Tables for Large-scale Network Simulation  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

ネットワーク規模の増大やネットワーク構造の複雑化にともない,大規模ネットワークにおけるシミュレーションが必要とされている.しかし,計算機で使用できる資源は限られているため,シミュレータに適用可能なネットワークの大きさ,シミュレーションシナリオの規模は制限される.シミュレーションにおいて,計算機資源(特にメモリ容量)を消費する要因の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.

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 TV is the number of nodes. An algorithmic routing recently proposed by Heung et al. only requires O (N) space for representing 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.

Journal

  • IPSJ journal

    IPSJ journal 45(4), 1134-1143, 2004-04-15

    Information Processing Society of Japan (IPSJ)

References:  10

Codes

  • NII Article ID (NAID)
    110002712161
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    6919406
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-741
  • Data Source
    CJP  NDL  NII-ELS  IPSJ 
Page Top