遺伝的アルゴリズムによる負荷分散機構を有する適応型ルーティング  [in Japanese] An Adaptive Routing Algorithm with Load Balancing by a Genetic Algorithm  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本論文では,遺伝的アルゴリズムにより代替経路のリストを生成するとともに,それらの間で通信パケットを確率的に分配することで負荷の分散をはかる適応型ルーティングアルゴリズムを提案する.RIPやSPFなど従来用いられてきたルーティングアルゴリズムではルーティングテーブルやリンク状態をネットワーク全体にブロードキャストするため,ネットワークが大規模化した場合に多くの通信コストを要し,ネットワーク全体の性能を低下させる.また,複数の良い代替経路がある場合でも1つの最短経路を集中して使用してしまう.本論文で提案するルーティングアルゴリズムは,実際に多数のパケットが使用している経路に関してのみ代替経路の生成およびその通信遅延時間の評価を行うため,ルーティングの情報交換に必要な通信コストを大きく削減することが可能となる.また,本アルゴリズムでは代替経路間でパケットを確率的に分配することで負荷の分散をはかる.離散事象シミュレーションに基づくネットワークシミュレータを構築し,比較実験を行った.その結果,従来手法に比べ少ない通信コストにより効果的なルーティングがなされていることが示された.This paper presents an adaptive routing algorthm which has load balancing mechanism among alternative paths by a genetic algorithm.Conventional routing algorithms such as RIP and SPF broadcast information on routing tables or link status in a network,which yields much communication overhead and degrades total performance when the network becomes large.Conventional routing algorithms only generate the shortest path to send a packet,even if some good alternative paths are available.Our routing algorithm generates alternative paths and observes communication latency only for paths frequently used.This mechanism greatly reduces communication cost for information exchanging of the routing.Moreover this algorithm realizes load balancing on the alternative paths by destributing packets among them.We perform simulation experiments using a discrete event simulator of network communication.The result of the experiments shows that our algorithm achieves effective routing with less communication overhead.

This paper presents an adaptive routing algorithm which has a load balancing mechanism among alternative paths by a genetic algorithm. Conventional routing algorithms such as RIP and SPF broadcast information on routing tables or link status in a network, which yields much communication overhead and degrades total performance when the network becomes large. Conventional routing algorithms only generate the shortest path to send a packet, even if some good alternative paths are available. Our routing algorithm generates alternative paths and observes communication latency only for paths frequently used. This mechanism greatly reduces communication cost for information exchangind of the routing. Moreover this algorithm realizes load balancing on the alternative paths by distributing packets among them. We perform simulation experiments using a discrete event simulator of network communication. The result of the experiments shows that our algorithm achieves effective routing with less communication overhead.

Journal

  • Transactions of Information Processing Society of Japan

    Transactions of Information Processing Society of Japan 39(2), 219-227, 1998-02-15

    Information Processing Society of Japan (IPSJ)

References:  10

Cited by:  12

Codes

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