(57)【要約】【課題】要求メッセージの無駄な誘導およびループを防止すること。【解決手段】本発明のルータは、要求メッセージを受信した時に、要求メッセージをＢＣ情報に従って転送する場合、転送方式情報を要求メッセージに付加する。また、要求メッセージを受信した時に、要求メッセージに転送方式情報が付加されており、かつ、該当するＢＣ情報を記録していない場合、要求メッセージの転送元のルータへ要求メッセージを転送する。また、要求メッセージを受信した時に、該当するＢＣ情報を記録しており、かつ、ＢＣ情報に下流ノードとして記録されたルータと、要求メッセージの転送元のルータと、が一致している場合、ＢＣ情報に上流ノードとして記録されたルータへ要求メッセージを転送し、ＢＣ情報を削除する。【選択図】図７
2015185994.tif 000002
【特許請求の範囲】
【請求項１】
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータであって
前記要求メッセージおよび前記応答メッセージを送受信する送受信部と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶部と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理部と、を有し、
前記応答メッセージを受信した時に、前記キャッシュ記憶部は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信部は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理部は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信部は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信部は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する、ルータ。
【請求項２】
請求項１に記載のルータであって、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとしてルータが記録されていない場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する、ルータ。
【請求項３】
請求項１または２に記載のルータであって、  前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージを前記サーバ宛に転送する、ルータ。
【請求項４】
端末と、
サーバと、
前記端末から前記サーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータと、を有し、
前記複数のルータの各々は、
前記要求メッセージおよび前記応答メッセージを送受信する送受信部と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶部と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理部と、を有し、
前記応答メッセージを受信した時に、前記キャッシュ記憶部は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信部は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理部は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信部は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信部は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、  前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する、コンテンツ配信システム。
【請求項５】
請求項４に記載のコンテンツ配信システムであって、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとしてルータが記録されていない場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する、コンテンツ配信システム。
【請求項６】
請求項４または５に記載のコンテンツ配信システムであって、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージを前記サーバ宛に転送する、コンテンツ配信システム。
【請求項７】
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータによるメッセージ転送方法であって
前記応答メッセージを受信した時に、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、該応答メッセージを前記端末宛に転送し、該コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、該要求メッセージの転送元のルータへ該要求メッセージを転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、該ＢＣ情報を削除する、メッセージ転送方法。
【請求項８】
請求項７に記載のメッセージ転送方法であって、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとしてルータが記録されていない場合、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、該ＢＣ情報を削除する、メッセージ転送方法。
【請求項９】
請求項７または８に記載のメッセージ転送方法であって、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、該要求メッセージを前記サーバ宛に転送する、メッセージ転送方法。
【請求項１０】
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータとして、コンピュータを機能させるためのプログラムであって、
前記コンピュータを、
前記要求メッセージおよび前記応答メッセージを送受信する送受信手段と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶手段と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理手段と、として機能させ、
前記応答メッセージを受信した時に、前記キャッシュ記憶手段は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信手段は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理手段は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信手段は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信手段は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信手段は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信手段は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理手段は、該ＢＣ情報を削除する、プログラム。 
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内のルータにコンテンツデータのキャッシュを保存し、コンテンツを要求するメッセージをキャッシュ方向へと誘導するコンテンツ配信システムにおいて、不完全な誘導経路を削除するための技術に関する。
【背景技術】
【０００２】
近年、ネットワークを介したコンテンツデータ（ビデオデータや書籍データなど）の流通が進んでいる。現状、ユーザは、サーバに保存されたコンテンツデータをダウンロードする場合、そのサーバのIP（Internet Protocol）アドレスをDNS（Domain Name System）などを用いて取得して、そのサーバへコンテンツを要求するメッセージを送信することで、所望のコンテンツデータを取得している。しかし、コンテンツ数やユーザ数の増大により、サーバへの負荷や取得時間が増大するという問題が懸念される。特定の少数のコンテンツデータ（Video On Demandや企業のWebページのデータなど）については、既存のCDN（Content Delivery Network）技術によって世界各地のサーバにコンテンツデータのキャッシュ（コピー）を保存する記憶装置がおかれ、サーバの負荷分散や応答時間の短縮が図られている。しかし、CDNにそぐわない一過性のコンテンツデータ（例えば、センサー測定データなど）やCDNを使うほどコストをかけられないコンテンツデータ（例えば、商店街の割引クーポンデータなど）については、上記問題は解決されない。
将来、ネットワークを介してやりとりされるあらゆるコンテンツデータについて、サーの負荷削減と取得時間の短縮を図ることを目的とする技術として、Breadcrumbs（以下、BC）と呼ばれる技術が非特許文献１に開示されている。BC方式では、ネットワーク内のルータにコンテンツデータのキャッシュを保存し、コンテンツID（Identifier）を用いてキャッシュへの誘導を行う。
【０００３】
以下、BC方式について、図１を用いて詳細に説明する。
図１に示すコンテンツ配信システムには、コンテンツサーバ101、ルータ201〜203、およびユーザ端末301，302が設けられている。
【０００４】
（1）ユーザ端末301によるコンテンツデータAの取得動作
まず、ユーザ端末301が、あるコンテンツデータAをダウンロードしようとしたとする。ユーザ端末301は、DNSなどの既存方式を用いて、コンテンツデータAを保存するサーバのIPアドレスを取得する。ここでは、サーバ101のIPアドレスを取得したとする。ユーザ端末301は、サーバ101宛にコンテンツ要求メッセージ（以下、要求メッセージと称す）を送信する。要求メッセージには、要求するコンテンツデータAのコンテンツIDおよびサーバ101のIPアドレスが含まれている。ユーザ端末301が送信した要求メッセージは、まずルータ202が受信する。ルータ202は、ユーザ端末301から受信した要求メッセージをルータ201へと転送する。ルータ201は、ルータ202と同様に、サーバ101へと要求メッセージを転送する。要求メッセージを受信したサーバ101は、コンテンツデータAを含むコンテンツ応答メッセージ（以下、応答メッセージと称す）を生成し、生成した応答メッセージをユーザ端末301宛に送信する。サーバ101が送信した応答メッセージは、まずルータ201が受信する。ここで、ルータ201は、応答メッセージの内容を解析し、コンテンツデータAのキャッシュを自身の記憶装置に保存して、ルータ202へと応答メッセージを転送する。その後、ルータ201は、自身のBreadcrumbテーブル（以下、BCテーブル）に以下のようなBC情報201-1を記録する。
[BC情報201-1]
・コンテンツID = A
・上流ノード = null
・下流ノード = 202
・データ通過時刻 = 2010/11/26 10:00:00
・リクエスト通過時刻 = null
【０００５】
BC情報は、応答メッセージ（コンテンツデータ）が流れた方向を示す情報であり、上記のように、コンテンツID、上流ノード、下流ノード、データ通過時刻、およびリクエスト通過時刻の情報が含まれている。コンテンツIDは、コンテンツデータを識別する識別子（ID）を表す。上流ノードは、そのコンテンツデータを含む応答メッセージのうち直近に受信した応答メッセージの転送元のルータを表す。下流ノードは、そのコンテンツデータを含む応答メッセージのうち直近に転送した応答メッセージの転送先のルータを表す。データ通過時刻は、そのコンテンツデータを含む応答メッセージのうち直近に転送した応答メッセージの転送時刻を表す。リクエスト通過時刻は、そのコンテンツデータを要求する要求メッセージのうち直近に受信した要求メッセージの受信時刻を表す。
【０００６】
もし、ルータ201においてコンテンツデータAのキャッシュを保存するための十分な記憶領域が無い場合、ルータ201は、最も過去にアクセスされたコンテンツデータのキャッシュから削除して記憶領域を解放し、新しいコンテンツデータAのキャッシュを保存する。コンテンツデータのキャッシュが削除されても、BC情報に記録された下流ノード方向にまだキャッシュを保存しているルータが存在する可能性があるため、BC情報はそのまま保持する。BC情報は、データ通過時刻が一定時間（Tf）更新されなかった場合、もしくはリクエスト通過時刻が一定時間（Tq）更新されなかった場合に削除される。基本的には、ルータにおいて、キャッシュを保存するための記憶領域の容量は、流通されるコンテンツデータの全容量と比較して非常に小さい。そのため、あまりダウンロードされないコンテンツデータのキャッシュは比較的早く削除される。これに対して、BC情報は、タイマーに従って削除され、タイマーも新しいダウンロードやリクエスト（要求メッセージ）の到着により延長されるため、キャッシュに比べて長くルータに残る。
【０００７】
応答メッセージをルータ201から受信したルータ202は、ルータ201と同様に、コンテンツデータAのキャッシュを自身の記憶装置に保存して、ユーザ端末301へと応答メッセージを転送する。その後、ルータ202は、自身のBCテーブルに以下のようなBC情報202-1を記録する。
[BC情報202-1]
・コンテンツID = A
・上流ノード  = 201
・下流ノード = null
・データ通過時刻 = 2010/11/26 10:00:10
・リクエスト通過時刻 = null
【０００８】
（2）ユーザ端末302によるコンテンツデータAの取得動作
その後、記憶領域の不足等の理由によりルータ201の記憶装置からコンテンツデータAのキャッシュが削除されたとする。
この状態で、ユーザ端末302が同じコンテンツデータAをダウンロードしようとしたとする。ユーザ端末302は、ユーザ端末301と同様に、DNSなどを用いて、コンテンツデータAを保存するサーバ101のIPアドレスを取得して、サーバ101宛に要求メッセージを送信する。ユーザ端末302が送信した要求メッセージは、ルータ203が受信し、ルータ201へと転送される。ここで、ルータ201は、要求メッセージに含まれるコンテンツデータAのキャッシュが自身の記憶装置に保存されているかを確認する。ここでは保存されていないため、ルータ201は、自身のBCテーブルに、コンテンツデータAに該当するBC情報（コンテンツデータAと同じコンテンツIDのBC情報。以下、同じ）が記録されているかを判断する。ここでは該当するBC情報（BC情報201-1）が記録されているため、ルータ201は、要求メッセージをサーバ101方向でなく、BC情報201-1に記録された下流ノード方向へと転送する。すなわち、ルータ201は、要求メッセージをルータ202へと転送する。その後、ルータ201は、自身のBCテーブルのコンテンツデータAに該当するBC情報（BC情報201-1）のリクエスト通過時刻を、以下のように、要求メッセージを受信した時刻へと書き換える。これにより、BC情報201-1は、BC情報201-2に更新される。
[BC情報201-2]
・コンテンツID = A
・上流ノード  = null
・下流ノード = 202
・データ通過時刻 = 2010/11/26 10:00:00
・リクエスト通過時刻 = 2010/11/26 10:04:59
【０００９】
要求メッセージをルータ201から受信したルータ202は、自身の記憶装置にコンテンツデータAのキャッシュが保存されているかどうかを判断する。
以降の動作は、ルータ202において、コンテンツデータAのキャッシュが保存されているか否かで異なり、保存されている場合は以下の（2-1）の動作が行われ、保存されていない場合は以下の（2-2）の動作が行われる。
【００１０】
（2-1）ルータ202にコンテンツデータAのキャッシュが保存されている場合
ルータ201からルータ202へとユーザ端末302の要求メッセージが転送された時に、ルータ202にコンテンツデータAのキャッシュが保存されていたとする。この場合、ルータ202は、コンテンツデータAを含む応答メッセージを生成し、生成した応答メッセージをユーザ端末302宛にルータ201を経由して送信する。その後、ルータ202は、自身のBCテーブルのコンテンツデータAに該当するBC情報（BC情報202-1）の下流ノード、データ通過時刻、リクエスト通過時刻を、以下のように書き換える。これにより、BC情報202-1は、BC情報202-2に更新される。
[BC情報202-2]
・コンテンツID = A
・上流ノード = 201
・下流ノード = 201
・データ通過時刻 = 2010/11/26 10:05:01
・リクエスト通過時刻 = 2010/11/26 10:05:00
【００１１】
応答メッセージをルータ202から受信したルータ201は、応答メッセージに含まれるコンテンツデータAのキャッシュを自身の記録装置へと再度保存し、ルータ203に応答メッセージを転送する。その後、ルータ201は、自身のBCテーブルのコンテンツデータAに該当するBC情報（BC情報201-2）の上流ノード、下流ノード、データ通過時刻を、以下のように書き換える。これにより、BC情報201-2は、BC情報201-3に更新される。
[BC情報201-3]
・コンテンツID = A
・上流ノード = 202
・下流ノード = 203
・データ通過時刻 = 2010/11/26 10:05:10
・リクエスト通過時刻 = 2010/11/26 10:04:59
【００１２】
ルータ203も、ルータ201と同様に、応答メッセージに含まれるコンテンツデータAのキャッシュを保存し、ユーザ端末302に応答メッセージを転送する。その後、ルータ203は、自身のBCテーブルに以下のBC情報203-1を記録する。
[BC情報203-1]
・コンテンツID = A
・上流ノード = 201
・下流ノード = null
・データ通過時刻 = 2010/11/26 10:05:20
・リクエスト通過時刻 = null
【００１３】
（2-2）ルータ202にコンテンツデータAのキャッシュが保存されていない場合
ルータ201からルータ202へとユーザ端末302の要求メッセージが転送された時に、ルータ202でも既にコンテンツデータAのキャッシュが保存されていなかったとする。この場合、ルータ202は、ルータ201と同様に、自身のBCテーブルに、コンテンツデータAに該当するBC情報が記録されているかを判断する。ここでは該当するBC情報（BC情報202-1）が記録されている。しかし、BC情報202-1に記録された下流ノードはnull（ユーザ端末）であるため、これ以上はBC情報に沿った転送ができない。そのため、ルータ202は、BC情報に上流ノードとして記録されたルータ201へと要求メッセージを転送し、BCテーブルからコンテンツデータAに該当するBC情報202-1を削除する。要求メッセージをルータ202から受信したルータ201は、自身のBCテーブルに記録された、コンテンツデータAに該当するBC情報201-2を参照する。ここでは、要求メッセージの転送元と、BC情報201-2に記録された下流ノードと、が共にルータ202である。そのため、ルータ201は、BC情報201-2は既に無効になったと判断し、要求メッセージをBC情報201-2に記録された上流ノードもしくはサーバ101への最短経路の次ホップへと転送する。ここでは、BC情報201-2に記録された上流ノードはnull（サーバ）であるため、ルータ201は、要求メッセージを、サーバ101への最短経路に沿って、サーバ101へ転送する。その後、ルータ201は、BCテーブルからコンテンツデータAに該当するBC情報201-2を削除する。これにより、BC情報に沿った誘導経路上にコンテンツデータが既に存在しない場合、そのBC情報を削除しながら要求メッセージをサーバ101へと届けることができる。この動作を誘導経路の無効化と呼ぶ。
【００１４】
上述のように、非特許文献１に開示されたBC方式では、ネットワーク内のルータにコンテンツデータのキャッシュを保存し、要求メッセージを応答メッセージが流れた方向（すなわち、コンテンツデータのキャッシュ方向）へと誘導する。このようにして、ネットワーク内に保存されたコンテンツデータを取得させることで、サーバの負荷削減とコンテンツデータの取得時間の短縮を図ることができる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】E. Rosensweig, J. Kurose, “Breadcrumbs: efficient, best-effort content location in cache networks",  Proc. 2009 IEEE Infocom Mini-Conference
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかし、非特許文献１に開示されたBC方式では、誘導経路の無効化により、途中で誘導が切れる不完全な誘導経路が発生し、最悪の場合、要求メッセージがループする可能性がある。
【００１７】
以下、不完全な誘導経路が発生し、ループが発生する場合のシーケンスについて、図２〜図６を用いて説明する。図２〜図６に示すコンテンツ配信システムには、サーバ111、ルータ211〜217、およびユーザ端末311〜313が設けられている。
【００１８】
まず、図２において、ユーザ端末312が、点線に沿って要求メッセージの送信と応答メッセージの受信とを行い、サーバ111からコンテンツデータBを取得する。その際に、ルータ211，213，214，216には、実線矢印のように、応答メッセージの流れた方向を示すBC情報が生成される。また、ルータ211，213，214，216には、コンテンツデータBのキャッシュが保持される。
その後、図３において、ユーザ端末311が、同じコンテンツデータBを要求し、要求メッセージをサーバ111宛に送信する。ここで、ルータ214のコンテンツデータBのキャッシュは既に削除されているとする。ユーザ端末311が送信した要求メッセージは、ルータ214においてBC情報にヒットし、ルータ216へと転送される。ルータ216は、コンテンツデータBのキャッシュを保存しているため、応答メッセージを生成してユーザ端末311へと送信する。それにより、ルータ214，216のBC情報は、図３の実線矢印のように更新される。ルータ215には、コンテンツデータBのキャッシュが保存されると共にBC情報が記録される。
その後、図４において、ユーザ端末313が、同じコンテンツデータBを要求する。要求メッセージはルータ214に到達する。ここで、ルータ214，215，216のコンテンツデータBのキャッシュは既に削除されているものとする。その場合、ルータ214は、要求メッセージをBCに沿ってルータ215へと転送する。
次に、図５において、ルータ215も、コンテンツデータBのキャッシュを保存しておらず、BC情報に記録された下流ノードはnull（ユーザ端末）である。そのため、ルータ215は、これ以上、要求メッセージを転送せず、BC情報に上流ノードとして記録されたルータ214へと要求メッセージを送り返す。それと同時にルータ215は、BC情報を既に無効と判断して削除する。ルータ215から要求メッセージを送り返されたルータ214は、自身の保存するBC情報を無効と判断して削除し、BC情報に上流ノードとして記録されていたルータ216へと要求メッセージを転送する。要求メッセージを受信したルータ216は、自身のBC情報を削除する。ルータ213のBC情報に下流ノードとして記録されたルータ214はBC情報を持たなくなるため、ルータ211→ルータ213の不完全な誘導経路が生成される。
次に、図６において、ルータ216は、これ以上、上流ノードへと要求メッセージを転送できないため、要求メッセージをサーバ111への最短経路の次ホップであるルータ214へと転送する。ルータ214は、コンテンツデータBのキャッシュも保存しておらず、BC情報も記録していないため、要求メッセージをサーバ111への最短経路に沿ってルータ212へと転送する。ルータ212は、ルータ214と同様に、要求メッセージをルータ211へと転送する。ここで、ルータ211，213のコンテンツデータBのキャッシュは既に削除されているとする。ただし、ルータ211にはBC情報が残っているため、ルータ211は、BC情報に下流ノードとして記録されたルータ213へと要求メッセージを転送する。ルータ213にもBC情報が残っているため、ルータ213は、BC情報に下流ノードとして記録されたルータ214へと要求メッセージを転送する。ルータ214にはBC情報が無いため、ルータ214は、サーバ111への最短経路の次ホップであるルータ212へと要求メッセージを転送する。この動作が繰り返され、要求メッセージはループする。ループが発生しない場合においても、不完全な誘導経路によって、削除されたキャッシュへの無駄な誘導が繰り返されるため、ユーザ端末313のコンテンツデータの取得を遅延させる原因となる。
【００１９】
本発明は、上述した課題を解決し、ネットワーク内で要求メッセージをキャッシュ方向へと誘導する方式において、不完全な誘導経路を検出して無効化し、無駄な誘導およびループを防止することができる技術を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明のルータは、
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータであって
前記要求メッセージおよび前記応答メッセージを送受信する送受信部と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶部と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理部と、を有し、
前記応答メッセージを受信した時に、前記キャッシュ記憶部は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信部は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理部は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信部は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信部は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、  前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する。
【００２１】
本発明のコンテンツ配信システムは、
端末と、
サーバと、
前記端末から前記サーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータと、を有し、
前記複数のルータの各々は、
前記要求メッセージおよび前記応答メッセージを送受信する送受信部と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶部と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理部と、を有し、
前記応答メッセージを受信した時に、前記キャッシュ記憶部は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信部は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理部は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信部は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信部は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信部は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、  前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信部は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理部は、該ＢＣ情報を削除する。
【００２２】
本発明のメッセージ転送方法は、
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータによるメッセージ転送方法であって
前記応答メッセージを受信した時に、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、該応答メッセージを前記端末宛に転送し、該コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、該要求メッセージの転送元のルータへ該要求メッセージを転送し、  前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、該ＢＣ情報を削除する。
【００２３】
本発明のプログラムは、
端末からサーバへ送信される、コンテンツデータを要求する要求メッセージを転送すると共に、前記サーバから前記端末へ送信される、コンテンツデータを含む応答メッセージを転送する複数のルータのうちの１つのルータとして、コンピュータを機能させるためのプログラムであって、
前記コンピュータを、
前記要求メッセージおよび前記応答メッセージを送受信する送受信手段と、
コンテンツデータのキャッシュを記憶するキャッシュ記憶手段と、
コンテンツデータの識別子と、該コンテンツデータを含む前記応答メッセージのうち直近に受信した前記応答メッセージの転送元のルータを表す上流ノードと、該コンテンツデータを含む前記応答メッセージのうち直近に転送した前記応答メッセージの転送先のルータを表す下流ノードと、を含むＢＣ情報を記録するＢＣ情報管理手段と、として機能させ、
前記応答メッセージを受信した時に、前記キャッシュ記憶手段は、該応答メッセージに含まれるコンテンツデータのキャッシュを保存し、前記送受信手段は、該応答メッセージを前記端末宛に転送し、前記ＢＣ情報管理手段は、該コンテンツデータに該当するＢＣ情報を記録または更新し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存している場合、前記送受信手段は、該コンテンツデータを含む前記応答メッセージを生成して、該応答メッセージを前記端末宛に転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致していない場合、前記送受信手段は、該ＢＣ情報に下流ノードとして記録されたルータへ、該要求メッセージを転送すると共に、該要求メッセージをＢＣ情報に従って転送することを示す転送方式情報を該要求メッセージに付加し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該要求メッセージに前記転送方式情報が付加されており、かつ、該コンテンツデータに該当するＢＣ情報を記録していない場合、前記送受信手段は、該要求メッセージの転送元のルータへ該要求メッセージを転送し、
前記要求メッセージを受信した時に、該要求メッセージにて要求されたコンテンツデータのキャッシュを保存しておらず、かつ、該コンテンツデータに該当するＢＣ情報を記録しており、かつ、該ＢＣ情報に下流ノードとして記録されたルータと、該要求メッセージの転送元のルータと、が一致している場合、前記送受信手段は、該ＢＣ情報に上流ノードとして記録されたルータへ該要求メッセージを転送し、前記ＢＣ情報管理手段は、該ＢＣ情報を削除する。
【発明の効果】
【００２４】
本発明によれば、不完全な誘導経路を検出して、その不完全な誘導経路を示すＢＣ情報を削除し、要求メッセージの無駄な誘導およびループを防止することができるという効果が得られる。
【図面の簡単な説明】
【００２５】
【図１】本発明のコンテンツ配信システムの構成例を示す図である。
【図２】本発明のコンテンツ配信システムの課題となるループ発生シーケンス（その１）を説明する図である。
【図３】本発明のコンテンツ配信システムの課題となるループ発生シーケンス（その２）を説明する図である。
【図４】本発明のコンテンツ配信システムの課題となるループ発生シーケンス（その３）を説明する図である。
【図５】本発明のコンテンツ配信システムの課題となるループ発生シーケンス（その４）を説明する図である。
【図６】本発明のコンテンツ配信システムの課題となるループ発生シーケンス（その５）を説明する図である。
【図７】本発明の一実施形態のルータの機能構成を示すブロック図である。
【図８】本発明の一実施形態のルータを含むコンテンツ配信システムの動作シーケンスを説明する図である。
【発明を実施するための形態】
【００２６】
以下に、本発明を実施するための形態について図面を参照して説明する。
以下では、図２〜図６に示すコンテンツ配信システムの構成を前提とし、そのシステム内に設けられたルータ211〜217に本発明を適用した場合を例に挙げて説明する。
図７に示すように、ルータ211〜217は、メッセージ送受信処理部401と、メッセージ転送決定処理部402と、コンテンツキャッシュ記憶部403と、BC情報管理部404と、転送経路管理部405と、不完全誘導経路検出処理部406と、BCテーブル407と、転送経路テーブル408と、を備えている。なお、メッセージ送受信処理部401と、メッセージ転送決定処理部402と、不完全誘導経路検出処理部406と、で送受信部409を構成している。
【００２７】
メッセージ送受信処理部401は、隣接ルータ、サーバ、またはユーザ端末との間で、要求メッセージおよび応答メッセージの送受信を行う。
コンテンツキャッシュ記憶部403は、コンテンツデータのキャッシュを保存する。また、コンテンツキャッシュ記憶部403は、コンテンツデータのキャッシュを保存した時間を管理する。コンテンツキャッシュ記憶部403は、新しいコンテンツデータのキャッシュを保存するための十分な記憶領域が無い場合、最も過去にアクセスされたコンテンツデータのキャッシュから削除して記憶領域を解放し、新しいコンテンツデータのキャッシュを保存する。
BC情報管理部404は、BCテーブル407を保持しており、BCテーブル407にBC情報を記録する。また、BC情報管理部404は、BC情報のデータ通過時刻およびリクエスト通過時刻を管理する。BC情報管理部404は、あるBC情報について、データ通過時刻が一定時間（Tf）更新されなかった場合、もしくは、リクエスト通過時刻が一定時間（Tq）更新されなかった場合、そのBC情報を削除する。
不完全誘導経路検出処理部406は、BC情報による誘導経路が不完全なものであることを検出する。
転送経路管理部405は、例えばOSPF（Open Shortest Path First）などの経路制御プロトコル（不図示）から経路情報を取得し、転送経路テーブル408に記録する。
メッセージ転送決定処理部402は、要求メッセージおよび応答メッセージの転送先を決定し、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。なお、転送方式は、後述のように、BC情報に従ってメッセージを転送したことを示す「BC情報による転送」であるか否かを表すものである。
以下、上記の各構成要素の動作について、応答メッセージを受信した場合と、要求メッセージを受信した場合と、に分けて説明する。
【００２８】
（A）応答メッセージを受信した場合
まず、応答メッセージを受信した場合について説明する。
メッセージ送受信処理部401は、受信した応答メッセージの応答メッセージ情報（コンテンツID、転送元、受信時刻、ユーザ端末情報、サーバ情報、転送方式など）をメッセージ転送決定処理部402およびBC情報管理部404に通知する。また、メッセージ送受信処理部401は、応答メッセージに含まれるコンテンツデータをコンテンツキャッシュ記憶部403に通知する。
コンテンツキャッシュ記憶部403は、メッセージ送受信処理部401から通知されたコンテンツデータを保存する。
メッセージ転送決定処理部402は、メッセージ送受信処理部401から通知された応答メッセージ情報に基づき、転送経路管理部405から、ユーザ端末方向への転送先を取得し、ユーザ端末への最短経路の次ホップのルータを応答メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、応答メッセージ情報の転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」でないことを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ応答メッセージを転送する。また、メッセージ送受信処理部401は、転送した応答メッセージの応答メッセージ情報（コンテンツID、転送先、転送時刻、ユーザ端末情報、サーバ情報、転送方式など）をBC情報管理部404に通知する。
BC情報管理部404は、メッセージ送受信処理部401から、応答メッセージの受信時および転送時に通知された応答メッセージ情報に基づき、BCテーブル407において該当するBC情報の記録や更新を行う。
【００２９】
（B）要求メッセージを受信した場合
続いて、要求メッセージを受信した場合について説明する。
メッセージ送受信処理部401は、受信した要求メッセージの要求メッセージ情報（コンテンツID、転送元、受信時刻、ユーザ端末情報、サーバ情報、転送方式など）をメッセージ転送決定処理部402およびBC情報管理部404に通知する。また、メッセージ送受信処理部401は、要求メッセージにて要求されたコンテンツデータのキャッシュがコンテンツキャッシュ記憶部403に保存されているか判断する。
BC情報管理部404は、メッセージ送受信処理部401から通知された要求メッセージ情報に基づき、要求メッセージにて要求されたコンテンツデータに該当するBC情報がBCテーブル407に記録されているか判断する。
以下、各構成要素の以降の動作も場合分けして説明する。
【００３０】
（B-1）コンテンツデータのキャッシュが保存されている場合
メッセージ送受信処理部401は、コンテンツキャッシュ記憶部403からコンテンツデータを取得し、そのコンテンツデータを含む応答メッセージを生成する。また、メッセージ送受信処理部401は、応答メッセージを生成したことをメッセージ転送決定処理部402に通知する。
メッセージ転送決定処理部402は、メッセージ送受信処理部401から応答メッセージを生成したことが通知されると、転送経路管理部405から、ユーザ端末方向への転送先を取得し、その転送先を応答メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」でないことを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ応答メッセージを転送する。また、メッセージ送受信処理部401は、転送した応答メッセージの応答メッセージ情報（コンテンツID、転送先、転送時刻、ユーザ端末情報、サーバ情報、転送方式など）をBC情報管理部404に通知する。
BC情報管理部404は、メッセージ送受信処理部401から、要求メッセージの受信時に通知された要求メッセージ情報や応答メッセージの転送時に通知された応答メッセージ情報に基づき、BCテーブル407において該当するBC情報の更新を行う。
【００３１】
（B-2）コンテンツデータのキャッシュが保存されてないが、BC情報が記録されている場合
メッセージ転送決定処理部402は、メッセージ送受信処理部401から通知された要求メッセージ情報に基づき、要求メッセージの転送方式を判断する。転送方式が「BC情報による転送」である場合、メッセージ転送決定処理部402は、不完全誘導経路検出処理部406に要求メッセージ情報を通知する。ここでは、コンテンツデータに該当するBC情報が記録されているため、後述のように、不完全誘導経路検出処理部406により不完全な誘導経路は検出されない。そのため、メッセージ転送決定処理部402は、BCテーブル407から該当するBC情報を取得する。また、メッセージ転送決定処理部402は、要求メッセージの転送方式が「BC情報による転送」でない場合、不完全誘導経路検出処理部406に要求メッセージ情報を通知することなく、BCテーブル407から該当するBC情報を取得する。
【００３２】
ここで、該当するBC情報に下流ノードとして記録されたルータと、要求メッセージの転送元のルータと、が一致しない場合、メッセージ転送決定処理部402は、該当するBC情報に下流ノードとして記録されたルータを要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」であることを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ要求メッセージを転送する。このとき、要求メッセージには、転送方式が「BC情報による転送」であることを示す転送方式情報を付加する。また、メッセージ送受信処理部401は、転送した要求メッセージの要求メッセージ情報（コンテンツID、転送先、転送時刻、ユーザ端末情報、サーバ情報、転送方式など）をBC情報管理部404に通知する。
BC情報管理部404は、メッセージ送受信処理部401から、要求メッセージの受信時および転送時に通知された要求メッセージ情報に基づき、BCテーブル407へのBC情報の更新を行う。
【００３３】
一方、該当するBC情報に下流ノードとしてルータが記録されていない場合（下流ノードとしてnull（ユーザ端末）が記録されている場合）、メッセージ送受信処理部401は、該当するBC情報に上流ノードとして記録されたルータを要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」であることを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ要求メッセージを転送する。
BC情報管理部404は、BCテーブル407から該当するBC情報を削除する。
【００３４】
一方、該当するBC情報に下流ノードとして記録されたルータと、要求メッセージの転送元のルータと、が一致する場合、メッセージ送受信処理部401は、該当するBC情報に上流ノードとして記録されたルータを要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」であることを示している。もしくは、メッセージ送受信処理部401は、転送経路管理部405からサーバ111方向への転送先を取得し、サーバ111への最短経路の次ホップのルータを要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」でないことを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ要求メッセージを転送する。このとき、転送先が、該当するBC情報に上流ノードとして記録されたルータである場合、要求メッセージには、転送方式が「BC情報による転送」であることを示す転送方式情報を付加する。
BC情報管理部404は、BCテーブル407から該当するBC情報を削除する。
【００３５】
（B-3）コンテンツデータのキャッシュが保存されておらず、BC情報も記録されていない場合
メッセージ転送決定処理部402は、メッセージ送受信処理部401から通知された要求メッセージ情報に基づき、要求メッセージの転送方式を判断する。転送方式が「BC情報による転送」である場合、メッセージ転送決定処理部402は、不完全誘導経路検出処理部406に要求メッセージ情報を通知する。
不完全誘導経路検出処理部406は、メッセージ転送決定処理部402から通知された要求メッセージ情報に基づき、要求メッセージにて要求されたコンテンツデータに該当するBC情報がBCテーブル407に記録されているか判断する。ここでは、該当するBC情報が記録されていないため、不完全誘導経路検出処理部406は、該当するBC情報による誘導経路が不完全なものであることを検出し、その旨をメッセージ転送決定処理部402に通知する。
メッセージ転送決定処理部402は、不完全誘導経路検出処理部406が不完全な誘導経路を検出すると、要求メッセージの転送元を要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」でないことを示している。
【００３６】
一方、メッセージ転送決定処理部402は、要求メッセージの転送方式が「BC情報による転送」でない場合、不完全誘導経路検出処理部406に要求メッセージ情報を通知することなく、BCテーブル407から該当するBC情報を取得する。しかし、ここでは、該当するBC情報は記録されていない。そのため、メッセージ送受信処理部401は、転送経路管理部405からサーバ111方向への転送先を取得し、サーバ111への最短経路の次ホップのルータを要求メッセージの転送先に決定する。そして、メッセージ転送決定処理部402は、決定した転送先、転送方式をメッセージ送受信処理部401に通知する。ここでの転送方式は、「BC情報による転送」でないことを示している。
メッセージ送受信処理部401は、メッセージ転送決定処理部402から通知された転送先へ要求メッセージを転送する。
【００３７】
以下、本実施形態のコンテンツ配信システムの具体的な動作シーケンスについて、図８を用いて説明する。
なお、図８は、図６において、ルータ211が、ユーザ端末312が送信した要求メッセージをルータ212から受信した時点の状況を示している。
【００３８】
この時点では、ルータ211において、ユーザ端末312が送信した要求メッセージにて要求されたコンテンツデータBのキャッシュは保存されていないが、コンテンツデータBに該当するBC情報は記録されている。
そのため、ルータ211は、該当するBC情報に下流ノードとして記録されたルータ213へ要求メッセージを転送する。このとき、要求メッセージには、転送方式が「BC情報による転送」であることを示す転送方式情報を付加する。  ルータ211から要求メッセージを受信したルータ213は、要求メッセージの転送方式を判断する。ここでは、転送方式は「BC情報による転送」であるため、ルータ213は、自ルータ213に該当するBC情報が記録されているかどうかを判断する。この時点では、該当するBC情報が記録されているため、ルータ213は、該当するBC情報に下流ノードとして記録されたルータ214へ要求メッセージを転送する。このとき、要求メッセージには、転送方式が「BC情報による転送」であることを示す転送方式情報を付加する。
ルータ213から要求メッセージを受信したルータ214は、要求メッセージの転送方式を判断する。ここでは、転送方式は「BC情報による転送」であるため、ルータ214は、自ルータ214に該当するBC情報が記録されているかどうかを判断する。この時点では、該当するBC情報が記録されていない。そのため、ルータ214は、該当するBC情報による誘導経路が不完全なものであることを検出し、要求メッセージを転送元であるルータ213に送り返す。
ルータ214から要求メッセージを送り返されたルータ213は、上述した背景技術の（2-2）に記載した無効化処理により、該当するBC情報を削除する。また、ルータ213は、該当するBC情報に上流ノードとして記録されていたルータ211へ要求メッセージを転送する。ルータ211も、ルータ213と同様に、該当するBC情報を削除し、サーバ方向であるサーバ111へ要求メッセージを転送する。
【００３９】
これにより、ルータ211およびルータ213に残っていた、不完全な誘導経路を示すBC情報が削除され、以降の要求メッセージがループまたは無駄に誘導されることを防止できる。
【００４０】
上述したように本実施形態においては、ルータ211〜217の各々は、要求メッセージを受信した時に、該当するBC情報に下流ノードとして記録されたルータへ要求メッセージを転送する場合、転送方式が「BC情報による転送」であることを示す転送方式情報を付加する。
また、ルータ211〜217の各々は、要求メッセージを受信した時に、その要求メッセージのキャッシュを保存しておらず、かつ、その要求メッセージに、転送方式が「BC情報による転送」であることを示す転送方式情報が付加されており、かつ、該当するBC情報を記録していない場合、要求メッセージの転送元のルータへ、要求メッセージを転送する。
ここで、図６の関連技術の場合、ルータ213から要求メッセージを受信したルータ214は、該当するBC情報を記録していない。そのため、ルータ214は、その要求メッセージを、サーバ111への最短経路の次ホップであるルータ212へと転送していた。これにより、要求メッセージはループし、削除されたキャッシュへの無駄な誘導が繰り返されていた。  これに対して図８の本実施形態の場合、ルータ213から要求メッセージを受信したルータ214は、該当するBC情報を記録していない。しかし、その要求メッセージに、転送方式が「BC情報による転送」であることを示す転送方式情報が付加されている。そのため、ルータ214は、該当するBC情報による誘導経路が不完全なものであることを検出し、その要求メッセージを、転送元のルータ213に送り返す。そのため、ルータ213は、該当するBC情報を削除して要求メッセージをルータ211に転送し、ルータ211も、ルータ213と同様に、該当するBC情報を削除する。これにより、ルータ211およびルータ213に残っていた、不完全な誘導経路を示すBC情報が削除され、以降の要求メッセージがループまたは無駄に誘導されることを防止できるという効果が得られる。
【００４１】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。以下、本実施形態の変形例を示す。
例えば、上記実施形態においては、図２〜図６に示すコンテンツ配信システムに本発明を適用した場合を例に挙げて説明した。しかし、本発明はこれに限定されず、複数のルータを備える他のコンテンツ配信システムにも適用することが可能である。
また、本発明のルータにて行われる方法は、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【００４２】
111    サーバ
211〜217    ルータ
311〜313    ユーザ端末
401    メッセージ送受信処理部
402    メッセージ転送決定処理部
403    コンテンツキャッシュ記憶部
404    BC情報管理部
405    転送経路管理部
406    不完全誘導経路検出処理部
407    BCテーブル
408    転送経路テーブル
409    送受信部
【図７】
2015185994.tif 000003
【図１】
2015185994.tif 000004
【図２】
2015185994.tif 000005
【図３】
2015185994.tif 000006
【図４】
2015185994.tif 000007
【図５】
2015185994.tif 000008
【図６】
2015185994.tif 000009
【図８】
2015185994.tif 000010