HBH配送システムに適したキャッシング方式の提案

摘要

近年，CDN（Contents Delivery Network）やP2P（Peer to Peer）ファイル共有システムといった，ファイル配送システムが普及してきており，ファイル配送における平均サービス時間の低減が課題となっている．この問題に対して，1リンクモデルにおいて，システム全体の平均サービス時間の低減を目的としたHBH最適配送方式が提案され，最適解に近い値を導出することに成功しているが，この配送アルゴリズムは，ネットワーク上の各ノードのキャッシュ容量が十分にあり，キャッシュ溢れが生じない理想的な環境を前提としており，制限がある場合，システムに導入されるキャッシング方式によりその特性が異なる．そこで本稿では，HBH最適配送方式に適したキャッシングの1方式として，キャッシュ溢れ時に，リクエスト数とファイルサイズに着目し再配送に要するサービス時間が最小であると予想されるファイルをキャッシュから追い出し再配送させる計画を立てる方式を提案し，計算機シミュレーションにより，有効性の検証を行った．その結果，提案方式によりFIFOやLFUといった既存のキャッシング方式に比べ，平均サービス時間が改善されることを確認した．%Reduction of average service latency for file delivery is one of the crucial problems of file distribution systems in widespread use, such as CDN (Contents Delivery Network), Web Proxy System, or P2P file sharing system (Peer-to-Peer file delivery system). As one of the solutions, in our previous works, we already developed Hop-by-Hop local optimal file delivery method, which performed nearly at the overall theoretical efficiency limit of the system under the limited case, where the system had adequate cache capacity and cache overflow never occurred. However, practical system has finite cache capacity, and cache algorithm which pushes unnecessary files out of cache when cache overflow occurs, should be introduced into the system. In this case, average service latency depends on interaction between file delivery method and cache algorithm, because the files which are pushed out of cache by cache algorithm should be resended when users require the files again, and the service latency of the resends are produced by file delivery method. Therefore, in this paper, we introduce a cache algorithm suitable for Hop-by-Hop local optimal file delivery method under the case where overflow occurs, and evaluate the performance of it. The results show that our algorithm performs effectively reduction of average service latency compared to FIFO (First-In First-Out) and LFU (Least Frequently Used).