講演抄録/キーワード |
講演名 |
2013-03-08 15:50
容量を考慮したキャッシュ配置に基づくクエリ誘導方式 ○堂 佳介・巳波弘佳(関西学院大) NS2012-241 |
抄録 |
(和) |
近年,大容量コンテンツ配信の増加に伴い,サーバ負荷増大によるサービス品質の低下が懸念されている.その解決手法の一つとして,キャッシュ機能を持つルータを用いることでサーバ負荷を軽減する方法が注目されている.しかし,すべてまたは一部のルータに多量のコンテンツがキャッシュされてしまうと,ルータ負荷が増大し,キャッシュヒット率の低下やルーティング機能に支障が生じてしまう.そのため,サーバとルータ両方の負荷を抑えるために,各ルータにコンテンツが集中しないようなコンテンツコピーをキャッシュするルータの組み合わせを決定することが重要となる.本稿では,これを容量考慮キャッシュ配置問題として定式化し,NP完全問題であることを証明した.さらに,この問題に対するヒューリスティックアルゴリズムを提案し,これを用いたキャッシュ配置制御法に関して数値実験により性能を評価する. |
(英) |
Recently, it is a big concern that the quality of service is degraded by large load of servers and flooding of large amounts of traffic in a network. To solve this problem, a router with storage for caching is attracting attention. Some control methods using such routers have been proposed so far. Breadcrumbs is famous one of the methods that leads a content request query to a cached copy by using routing history information stored in routers. It is important that a control method decreases the loads of servers and routers without increasing delay for retrieving a content or its cached copy. In this paper, we propose a control method to decrease the loads of servers and routers by determining appropriate locations of copies. First, we define the location problem and prove that it is NP-complete. Moreover, we propose some heuristic algorithms to solve this problem and evaluate the algorithm by numerical experiments. The results showed that these algorithms perform well. |
キーワード |
(和) |
Breadcrumbs / キャッシュ配置 / kセンター問題 / NP完全性 / 最適化問題 / / / |
(英) |
Breadcrumbs / cache location / k-center problem / NP-complete / optimization problem / / / |
文献情報 |
信学技報, vol. 112, no. 463, NS2012-241, pp. 445-450, 2013年3月. |
資料番号 |
NS2012-241 |
発行日 |
2013-02-28 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2012-241 |