講演抄録/キーワード |
講演名 |
2014-03-07 09:50
リンクメトリック変更によるサーバへのアクセストラフィック制御 ○棟近高大・野口 烈・巳波弘佳(関西学院大) NS2013-228 |
抄録 |
(和) |
近年,ブロードバンドインターネット接続の普及に伴い,動画配信サービスなど,大容量データの配信が増加している.これは,コンテンツ配信サーバの負荷を増大させ,サービス品質を低下させる可能性もある.この問題に対処するため,ユーザからのアクセスを分散させるミラーリングという手法がある.このミラーリングの手法では,ネットワーク上のミラーサーバ配置場所,サーバの選択方法によって,サービスの信頼性・ネットワーク負荷・ミラーサーバ負荷・サービス遅延といった性能が大きく異なってくる.最短経路ルーティングを用いるネットワークにおいては,小さいメトリックを割り当てられたリンクに最短経路が集中する傾向がある.したがって,リンクを通過する経路数が容量以下になるようにし,かつサーバへの要求量の和が容量以下になるように,限定されたリンクのみのメトリックを更新してネットワークのサーバ負荷分散を図る必要がある.
本稿では,これをサーバ負荷分散辺コスト決定問題として定式化し,NP完全性を証明した.さらに,メトリックを変更できるリンクを1本に限定した場合における多項式時間アルゴリズムを設計した.また,すべてのリンクのメトリックを変更できるとした場合におけるヒューリスティックアルゴリズムも設計した.これらのアルゴリズムを現実の様々なネットワークへ適用し,アルゴリズムの有効性を評価した. |
(英) |
Recently, with the spread of broadband Internet access and video contents provide services, large contents in the Internet have increased loads of contents servers and networks. This is at risk of degrading the quality of service. To overcome this problem, some mirror servers providing the same contents are located on a network and a request is navigated to one of the mirror servers. When mirror servers are located in a network and the shortest path routing are used, it is necessary to determine the metrics of links appropriately, because many paths may pass a link with small metric and there is high possibility that it causes the congestion of the link and servers. It is important to determine the link metrics so as to limit the total amount of demand in a link and in a server. In this paper, we define this link metric decision problem to control server access traffic. First, we prove that it is NP-complete. Next, when we restricted this problem to determine the metric of only a link, we show that it can be solved in polynomial time. In addition, we present a heuristic algorithm for the problem when the metrics of all links can be changed. We evaluate these algorithms by using some actual network topologies, and the results showed that server load balance can be realized by the heuristic algorithm. |
キーワード |
(和) |
リンクメトリック / ミラーサーバ / トラフィック制御 / NP 完全性 / 多項式時間アルゴリズム / / / |
(英) |
Link Metric / Mirror Server / Traffic Control / NP-complete / Polynomial-time Algorithm / / / |
文献情報 |
信学技報, vol. 113, no. 472, NS2013-228, pp. 301-306, 2014年3月. |
資料番号 |
NS2013-228 |
発行日 |
2014-02-27 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2013-228 |