リングネットワークにおけるページ移動について

• 松林, 昭

書誌事項

タイトル別名

• Page Migration on Ring Networks

抄録

金沢大学理工研究域電子情報学系

ページ移動問題とは,ネットワーク上でページと呼ばれるデータへのアクセス要求を発行するノード系列に対して,ページを動的に移動することにより要求に対するサービスコストと移動コストの総和を最小化する問題である.この間題に対しては,木,一様ネットワーク,およびそれらのCartesian積を除いて,4未満の競合比を持つ決定的オンラインアルゴリズムは知られていない.本稿では,ページサイズが1に限定されている条件の下で,リングネットワークに対する決定的な2+√<2>(⋍3.4142)-競合オンラインアルゴリズムを示す.このアルゴリズムはリングの木とトーラスにも拡張できる.さらにページ移動問題の競合比の下界として,一般のネットワークに対して3.1639,リングネットワークに対して3.1213を与える. The page migration problem is to compute dynamic allocation of a page on a network for a given sequence of nodes issuing requests for the page. The goal is to minimize the total communication costs of services for requests and of migrations of the page. We did not know any deterministic online algorithm with competitive ratio less than 4 for networks other than trees, uniform networks, and Cartesian products of those networks so far. In this paper we give a 2+√<2>(⋍ 3.4142)-competitive deterministic algorithm on rings (with edge weights) for the setting that the page size is 1. We can also derive algorithms for trees of rings and tori with the same competitive ratio and with the same setting. Moreover, we show an improved lower bound of 3.1639 for general networks and a lower bound of 3.1213 for rings. Our lower bound for rings is the first result which gives an explicit lower bound greater than 3 for rings, together with an explicit proof.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2006 (122), 35-42, 2006-11-21

  情報処理学会

詳細情報

• CRID: 1050282810916418048
• NII論文ID: 110005717684
• NII書誌ID: AN1009593X
• ISSN: 09196072
• NDL書誌ID: 8571453
• Web Site: http://hdl.handle.net/2297/14258
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I8571453
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles