(57)【要約】【課題】クライアントからのデータへのアクセス時間を短縮し、通信機器の消費電力を削減する。【解決手段】クライアントがサーバにアクセスするデータを中継するための中継機器であって、前記データに関連付けされた識別子を格納するｍ（≧３）本のキューと、前記データを格納するためのストレージと、前記クライアントからアクセスされたデータの識別子を前記キューに格納し、前記データのうち所定のデータを前記ストレージに格納する処理装置とを備え、前記処理装置は、（ｍ−１）回アクセスされたデータの識別子を（ｍ−１）本目のキューの先頭に格納し、ｍ回アクセスされたデータの識別子をｍ本目のキューの先頭に格納し、および、ｍ回アクセスされたデータを前記ストレージに格納し、前記（ｍ−１）本目のキューの容量は、（ｍ−２）本目のキューの容量より小さい。【選択図】図５
2016010041.tif 000002
【特許請求の範囲】
【請求項１】
クライアントがサーバにアクセスするデータを中継するための中継機器であって、
前記データに関連付けされた識別子を格納するｍ（≧３）本のキューと、
前記データを格納するためのストレージと、
前記クライアントからアクセスされたデータの識別子を前記キューに格納し、前記データのうち所定のデータを前記ストレージに格納する処理装置とを備え、
前記処理装置は、
（ｍ−１）回アクセスされたデータの識別子を（ｍ−１）本目のキューの先頭に格納し、
ｍ回アクセスされたデータの識別子をｍ本目のキューの先頭に格納し、および、ｍ回アクセスされたデータを前記ストレージに格納し、
前記（ｍ−１）本目のキューの容量は、（ｍ−２）本目のキューの容量より小さいことを特徴とする中継機器。
【請求項２】
クライアントがサーバにアクセスするデータを中継する機器による中継方法であって、
前記機器は、前記データに関連付けされた識別子を格納するｍ（≧３）本のキューと、
前記データを格納するためのストレージと、
前記クライアントからアクセスされたデータの識別子を前記キューに格納し、前記データのうち所定のデータを前記ストレージに格納する処理装置とを備え、
（ｍ−１）回アクセスされたデータの識別子を（ｍ−１）本目のキューの先頭に格納するステップと、
ｍ回アクセスされたデータの識別子をｍ本目のキューの先頭に格納し、および、ｍ回アクセスされたデータを前記ストレージに格納するステップとを備え、
前記（ｍ−１）本目のキューの容量は、（ｍ−２）本目のキューの容量より小さいことを特徴とする中継方法。
【請求項３】
請求項２に記載の中継方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、中継機器、中継方法、およびプログラムに関し、より詳細には、クライアントから要求されたデータを中継する中継機器、中継方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、情報化社会の進展に伴い、オフィスやサーバ室等に設置される通信機器の数が急増し、通信機器全体で消費される電力が増大している。本明細書では、通信機器とは、サーバ、ＰＣ、ルータなどをいう。そこで、サーバとクライアントＰＣとの間で、データを伝送する際に掛かる時間を短縮することによって、各通信機器を使用する時間を減少させ、各通信機器の電源で消費される電力量を削減する方法が考えられる。
【０００３】
例えば、クライアントＰＣから要求されたデータがサーバの記憶装置に存在した場合、クライアントＰＣは、サーバからルータを介して要求されたデータを取得する。ここで、ルータに記憶装置を設け、設けた記憶装置に要求されたデータが格納されていると、クライアントＰＣは、サーバから取得する時間よりも短い時間で要求されたデータを取得することが可能となる。
【０００４】
ルータの記憶装置には、クライアントＰＣからのアクセス頻度の高いデータを優先的に格納するのが望ましい。クライアントＰＣからのアクセス頻度の高いデータは、またアクセスされる可能性があり、アクセス頻度の高いデータをルータの記憶装置に格納しておくことは、クライアントＰＣ１ａからのアクセス時間を短縮することに繋がる。
【０００５】
そこで、例えば、ＬＲＵ（Least Recently Used）、ＬＲＵ−ｋ、２Ｑ、およびＡＲＣ（Adaptive Replacement Cache）のようなアルゴリズムを用いて、クライアントＰＣからのアクセス頻度が高いデータをルータの記憶装置に格納していく方法が知られている。
【０００６】
図１にＬＲＵを説明するための図を示す。ルータには、データが格納されるキュー１１が備えられている。キュー１１には、ａ、ｂ、ｃ、ｄ、ｅの順番で各データが格納されている。
【０００７】
例えば、クライアントＰＣからサーバに対してデータｆを要求し、要求がルータに到達した際、ルータは、要求されたデータｆがルータのキュー１１に存在するかどうかを確認する。図１（ａ）に示すように、要求されたデータｆはルータのキュー１１に存在しないため、要求をそのままサーバへ送信し、サーバの記憶装置に格納されているデータｆをルータに送信する。次に、ルータがデータｆを受信した場合、図１（ｂ）に示すように、ルータのキュー１１の先頭にデータｆが格納され、キュー１１の末尾にあるデータｅが削除される。そして、ルータは、データｆをクライアントＰＣに送信する。
【０００８】
次に、例えば、クライアントＰＣからサーバに対してデータｃを要求し、要求がルータに到達した際、ルータは、要求されたデータｃがルータのキュー１１に存在するかどうかを確認する。図１（ｂ）に示すように、要求されたデータｃはルータのキュー１１に存在するため、図１（ｃ）に示すように、ルータのキュー１１の先頭にデータｃを移動する。そして、ルータは、データｃをクライアントＰＣに送信する。
【０００９】
ＬＲＵでは、新しいデータがキュー１１に格納され、且つ、古いデータが削除される一方、再度アクセスされたデータは、キュー１１の先頭に移動し、削除され難くなる。クライアントＰＣが再度アクセスしたデータにもう一度アクセスする場合、アクセス時間を短縮することが可能となる。
【００１０】
しかし、ＬＲＵでは、新しいデータがキュー１１に短時間で複数個格納された場合、アクセス回数の多いデータがキュー１１の末尾に押し出され、削除される可能性がある。
【００１１】
そこで、ＬＲＵを改善したＬＲＵ-ｋでは、ルータのキュー１１に格納されるデータのアクセス回数をカウントし、アクセス回数が多いデータを優先的にキュー１１に格納する（例えば、非特許文献１を参照）。しかし、ＬＲＵ-ｋでは、全データのアクセス回数を管理する必要があり、クライアントＰＣがデータにアクセスする時間以外にかかる処理時間が長くなる可能性がある。
【００１２】
そこで、異なる長さの２本のキューを用いて、クライアントＰＣからのアクセス時間をＬＲＵよりも短縮するように構築されたアルゴリズムである２Ｑ（例えば、非特許文献２を参照）が知られている。
【００１３】
図２に２Ｑを説明するための図を示す。ルータには、データが格納されるキュー１２およびキュー１３が備えられている。１本目のキュー１２には、ａ、ｂ、ｃ、ｄ、ｅの各データが格納され、２本目のキュー１３には、ｆ、ｇ、ｈ、ｉの各データが格納されている。キュー１２には、１回アクセスされたデータが格納され、キュー１３には、２回以上アクセスされたデータが格納される。
【００１４】
例えば、クライアントＰＣからサーバに対してデータｊを要求し、要求がルータに到達した際、ルータは、要求されたデータｊがルータの２本のキュー１２、１３に存在するかどうかを確認する。図２（ａ）に示すように、要求されたデータｊはルータの２本のキュー１２、１３に存在しないため、要求をそのままサーバへ送信し、サーバの記憶装置に格納されているデータｊをルータに送信する。次に、ルータがデータｊを受信した場合、図２（ｂ）に示すように、ルータの１本目のキュー１２の先頭にデータｊが格納され、キュー１２の末尾にあるデータｅが削除される。そして、ルータは、データｊをクライアントＰＣに送信する。
【００１５】
次に、例えば、クライアントＰＣからサーバに対してデータｃを要求し、要求がルータに到達した際、ルータは、要求されたデータｃがルータの２本のキュー１２、１３に存在するかどうかを確認する。図２（ｂ）に示すように、要求されたデータｃはルータの１本目のキュー１２に存在するため、図２（ｃ）に示すように、ルータの２本目のキュー１３の先頭にデータｃを移動し、２本目のキュー１３の末尾にあるデータｉが削除される。そして、ルータは、データｃをクライアントＰＣに送信する。
【００１６】
２Ｑでは、再度アクセスのあったデータが、２本目のキュー１３に格納され、ＬＲＵより削除され難くなる可能性が高くなる。したがって、クライアントＰＣが再度アクセスのあったデータにもう一度アクセスする場合、アクセス時間をＬＲＵの場合より短縮する可能性を増加させることができる。
【００１７】
しかし、２Ｑでは、２本目のキュー１３に格納されるためには最低２回のアクセスが必要で、２回以上のアクセスがないと、ＬＲＵと変わらないアクセス時間となる場合があった。また、アクセスの少ないデータが、１本目のキュー１２に毎回格納されるので、ルータの記憶装置の容量を無駄に使用している可能性もあった。
【００１８】
そこで、データを格納する２本のデータキューと、データを識別するためのメタデータだけを格納する２本のメタデータキューとの計４本のキューを用いてアクセス時間を短縮し、且つ、記憶装置の容量を抑えるように構築されたアルゴリズム、ＡＲＣ（例えば、非特許文献３を参照）が知られている。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】E. J. O'neil, , P. E. O'neil, and G. Weikum, "The LRU-K page replacement algorithm for database disk buffering", ACM SIGMOD Record, Vol.22, No.2,1993
【非特許文献２】T. Johnson and D. Shasha, "2Q: A Low Overhead High Performance Bu er Management Replacement Algorithm", Proceedings in 20th VLDB, 1994
【非特許文献３】N. Megiddo, and D. S. Modha, "ARC: a self-tuning, low overhead replacement cache", Proceedings of the 2nd USENIX conference on File and storage technologies, 2003
【発明の概要】
【発明が解決しようとする課題】
【００２０】
図３にＡＲＣを説明するための図を示す。ルータには、データが格納される１本目のデータキュー１４、２本目のデータキュー１５が備えられ、データのメタデータが格納される１本目のメタデータキュー１６、２本目のメタデータキュー１７が備えられている。メタデータキューについては後で詳述するが、ＡＲＣでは、メタデータキューで削除されるメタデータの数によって、データキューの長さを調整する。
【００２１】
１本目のデータキュー１４には、ａ、ｂ、ｃの各データが格納され、２本目のデータキュー１５には、ｄ、ｅ、ｆの各データが格納されている。また、１本目のメタデータキュー１６には、ｇ、ｈ、ｉの各データのメタデータが格納され、２本目のメタデータキュー１７には、ｊ、ｋ、ｌの各データのメタデータが格納されている。１本目のデータキュー１４には、１回アクセスされたデータが格納され、２本目のデータキュー１５には、２回以上アクセスされたデータが格納される。１本目のメタデータキュー１６には、１本目のデータキュー１４からあふれたデータのメタデータが格納され、２本目のメタデータキュー１７には、２本目のデータキュー１５からあふれたデータのメタデータが格納される。
【００２２】
例えば、クライアントＰＣからサーバに対してデータｍを要求し、要求がルータに到達した際、ルータは、要求されたデータｍがルータのデータキュー１４、１５、メタデータキュー１６、１７に存在するかどうかを確認する。図３（ａ）に示すように、要求されたデータｍはルータの４本のキューのどれにも存在しないため、要求をそのままサーバへ送信し、サーバの記憶装置に格納されているデータｍをルータに送信する。次に、ルータがデータｍを受信した場合、図３（ｂ）に示すように、ルータの１本目のデータキュー１４の先頭にデータｍが格納され、１本目のデータキュー１４の末尾にあるデータｃが、メタデータのみとなって１本目のメタデータキュー１６の先頭に移動する。そして、ルータは、データｍをクライアントＰＣに送信する。
【００２３】
次に、例えば、クライアントＰＣからサーバに対してデータａを要求し、要求がルータに到達した際、ルータは、要求されたデータａがルータのデータキュー１４、１５、メタデータキュー１６、１７に存在するかどうかを確認する。要求されたデータａは、１本目のデータキュー１４に存在するため、図３（ｃ）に示すように、ルータの２本目のデータキュー１５の先頭にデータａを移動し、２本目のデータキュー１５の末尾にあるデータｆが、メタデータのみとなって２本目のメタデータキュー１７の先頭に移動する。そして、ルータは、データａをクライアントＰＣに送信する。
【００２４】
１本目のデータキュー１４に格納されるデータが多い場合、１本目のデータキュー１４で削除されるデータの数が増加し、１本目のメタデータキュー１６に格納されるデータの識別子も増加して、１本目のメタデータキュー１６でデータが削除される回数が多くなる。２本目のデータキュー１４についても、格納されるデータが多い場合、２本目のデータキュー１５で削除されるデータの数が増加し、２本目のメタデータキュー１７に格納されるデータの識別子も増加して、２本目のメタデータキュー１７でデータが削除される回数が多くなる。そこで、ＡＲＣでは、１本目のメタデータキュー１６でデータが削除される回数が一定の数を超えれば、１本目のデータキュー１４の長さを増やし、２本目のメタデータキュー１７でデータが削除される回数が一定の数を超えれば、２本目のデータキュー１５の長さを増やして、アクセスされるデータの格納数を増加させている。
【００２５】
ＡＲＣでは、再度アクセスのあったデータは、２本目のデータキュー１５に格納される。そして、２本目のデータキュー１５が満杯で、再度アクセスのあったデータが２本目のデータキュー１５の末尾からあふれた場合、あふれたデータに係るメタデータが２本目のメタデータキュー１７に格納される。削除されるメタデータの数によってデータキューの長さを変更し、クライアントがアクセスしたいデータの数を増加させ、アクセス時間の短縮を図っている。
【００２６】
しかしながら、ＡＲＣでは、偶然短時間に同じ不要なデータに２回アクセスがあった場合、データが２本目のデータキュー１５に格納され、以後長時間アクセスされないまま留まり続け、無駄にルータの記憶装置の容量を使用してしまう可能性があった。無駄にルータの記憶装置の容量を使用すると、本当にアクセスしたかったデータがルータの記憶装置に格納されない結果、クライアントからのデータへのアクセス時間が長くなってしまうという場合があった。クライアントからのデータへのアクセス時間が長くなってしまうと、通信機器の使用時間を増加させ、通信機器の消費電力を上昇させるという問題があった。
【００２７】
本発明は、このような問題に鑑みてなされたもので、その目的とするところは、クライアントからのデータへのアクセス時間を短縮し、通信機器の消費電力を削減するための、データ中継装置、データ中継方法、およびプログラムを提供することにある。
【課題を解決するための手段】
【００２８】
本発明は、このような目的を達成するために、請求項１に記載の発明は、クライアントがサーバにアクセスするデータを中継するための中継機器であって、前記データに関連付けされた識別子を格納するｍ（≧３）本のキューと、前記データを格納するためのストレージと、前記クライアントからアクセスされたデータの識別子を前記キューに格納し、前記データのうち所定のデータを前記ストレージに格納する処理装置とを備え、前記処理装置は、（ｍ−１）回アクセスされたデータの識別子を（ｍ−１）本目のキューの先頭に格納し、ｍ回アクセスされたデータの識別子をｍ本目のキューの先頭に格納し、および、ｍ回アクセスされたデータを前記ストレージに格納し、前記（ｍ−１）本目のキューの容量は、（ｍ−２）本目のキューの容量より小さいことを特徴とする。
【発明の効果】
【００２９】
以上説明したように、本発明によれば、クライアントからのデータへのアクセス時間を短縮し、通信機器の消費電力を削減することが可能となる。
【図面の簡単な説明】
【００３０】
【図１】ＬＲＵを説明するための図である。
【図２】２Ｑを説明するための図である。
【図３】ＡＲＣを説明するための図である。
【図４】本発明の一実施形態にかかるルータの構成を示すブロック図である。
【図５】本発明の一実施形態にかかるルータで用いられるアルゴリズムの一例を説明するための図である。
【図６】本発明の一実施形態にかかるデータ中継方法を示すフローチャートである。
【発明を実施するための形態】
【００３１】
以下、図面を参照しながら本発明の実施形態について詳細に説明する。
【００３２】
＜構成＞  
図４に本発明の一実施形態にかかるルータの構成のブロック図を示す。本発明の一実施形態にかかるルータ４は、記憶装置４２を備え、クライアントＰＣからサーバに要求されたデータの識別子およびデータを記憶装置４２に格納する処理装置４１をさらに備える。
【００３３】
記憶装置４２は、クライアントＰＣからサーバに要求されたデータの識別子を格納するＩＤキュー４２１と、クライアントＰＣからサーバに要求されたデータを格納するストレージ４２２とを備える。ＩＤキュー４２１の長さは、設定により変更可能である。
【００３４】
処理装置４１は、データを送受信する通信部４１１と、受信したデータの識別子をＩＤキュー４２１に格納し、受信したデータをストレージ４２２に格納する管理部４１２と、ＩＤキュー４２１にクライアントＰＣから要求されたデータが存在するかどうか確認したり、キューが満杯かどうかを確認したりする判定部４１３とを備える。データの識別子は、当該データがアクセスされる毎に別のＩＤキューへ移動する。後述するＩＤキューに移動した場合、クライアントから再度当該データにアクセスがあると、識別子に紐づいたデータがストレージ４２２に格納される。
【００３５】
本発明の一実施形態では、クライアントＰＣからのアクセス数が所定数を超えたデータについてストレージ４２２に格納する。クライアントＰＣからのアクセス数が所定数未満のデータについては、データの識別子だけをＩＤキュー４２１に格納する。
【００３６】
図５に、本発明の一実施形態にかかるルータで用いられるアルゴリズムの一例を説明するための図を示す。ＩＤキュー４２１には、データの識別子が格納される１本目のＩＤキュー５＿１、２本目のＩＤキュー５＿２、．．．、（ｍ−２）本目のＩＤキュー５＿（ｍ−２）、（ｍ−１）本目のＩＤキュー５＿（ｍ−１）、ｍ本目のＩＤキュー５＿ｍが備えられている。ＩＤキュー５＿１には、ａ、ｂ、ｃ、ｄ、ｅの各データの識別子が格納され、ＩＤキュー５＿２には、ｆ、ｇ、ｈ、ｉの各データの識別子が格納されている。また、ＩＤキュー５＿（ｍ−２）には、ｊ、ｋ、ｌの各データの識別子が格納され、ＩＤキュー５＿（ｍ−１）には、ｍ、ｎの各データの識別子が格納されている。そして、ＩＤキュー５＿ｍには、ｏ、ｐ、ｑ、ｒの各データの識別子が格納されている。
【００３７】
１本目のＩＤキュー５＿１には、１回アクセスされたデータの識別子が格納され、２本目のＩＤキュー５＿２には、２回アクセスされたデータの識別子が格納される。（ｍ−２）本目のＩＤキュー５＿（ｍ−２）には、（ｍ−２）回アクセスされたデータの識別子が格納され、（ｍ−１）本目のＩＤキュー５＿（ｍ−１）には、（ｍ−１）回アクセスされたデータの識別子が格納される。また、ｍ本目のＩＤキュー５＿ｍには、ｍ回アクセスされたデータの識別子が格納される。ルータ４のストレージ４２２には、ｍ本目のＩＤキュー５＿ｍに格納されているデータの識別子に紐付いたデータが格納される。
【００３８】
例えば、クライアントＰＣからサーバに対してデータｓを要求し、要求がルータ４に到達した場合を考える。判定部４１３は、要求されたデータｓの識別子がルータ４の全てのＩＤキューのうちどれかに存在するかどうかを確認する。図５に示すように、要求されたデータｓの識別子はルータ４のＩＤキューの全てに存在しないため、通信部４１１は、要求をそのままサーバへ送信し、サーバの記憶装置に格納されたデータｓをルータ４に送信する。次に、通信部４１１がデータｓを受信した場合、管理部４１２は、ルータ４の１本目のＩＤキュー５＿１の先頭にデータｓの識別子を格納し、管理部４１２は、ＩＤキュー５＿１の末尾にあるデータｅの識別子を削除する。そして、通信部４１１は、データｓをクライアントＰＣに送信する。
【００３９】
また、例えば、クライアントＰＣからサーバに対してデータｃを要求し、要求がルータ４に到達した場合を考える。判定部４１３は、要求されたデータｃの識別子がルータ４のＩＤキューの全てに存在するかどうかを確認する。要求されたデータｃの識別子は、図５に示すように、１本目のＩＤキュー５＿１に存在するため、管理部４１２は、ルータ４の２本目のＩＤキュー５＿２の先頭にデータｃを移動し、２本目のＩＤキュー５＿２の末尾にあるデータｉを削除する。一方、通信部４１１は、クライアントＰＣからの要求をサーバへ送信し、サーバの記憶装置に格納されたデータｃをルータ４に送信する。次に、通信部４１１がデータｃを受信した場合、データｃをクライアントＰＣに送信する。
【００４０】
さらに、例えば、クライアントＰＣからサーバに対してデータｍを要求し、要求がルータ４に到達した場合を考える。判定部４１３は、要求されたデータｍの識別子がルータ４の全てのＩＤキューのうちどれかに存在するかどうかを確認する。一方、通信部４１１は、クライアントＰＣからの要求をサーバへ送信し、サーバの記憶装置に格納されたデータｍをルータ４に送信して、データｍをサーバから取得する。要求されたデータｍの識別子は、図５に示すように、（ｍ−１）本目のＩＤキュー５＿（ｍ−１）に存在するため、管理部４１２は、ルータ４のｍ本目のＩＤキュー５＿ｍの先頭にデータｍの識別子を移動し、且つ、データｍをルータ４のストレージ４２２に格納する。そして、管理部４１２は、ｍ本目のＩＤキュー５＿ｍの末尾にあるデータｒの識別子を削除し、且つ、ルータ４のストレージ４２２に格納されていたデータｒを削除する。そして、通信部４１１は、データｍをクライアントＰＣに送信する。
【００４１】
また、例えば、クライアントＰＣからサーバに対してデータｐを要求し、要求がルータ４に到達した場合を考える。判定部４１３は、要求されたデータｐの識別子がルータ４の全てのＩＤキューのうちどれかに存在するかどうかを確認する。要求されたデータｐの識別子は、図５に示すように、ｍ本目のＩＤキュー５＿ｍに存在するため、管理部４１２は、ルータ４のｍ本目のＩＤキュー５＿ｍの先頭にデータｐの識別子を移動する。そして、通信部４１１は、ストレージ４２２に格納されたデータｐをクライアントＰＣに送信する。
【００４２】
本発明の一実施形態にかかる、１本目のＩＤキュー５＿１から（ｍ−１）本目のＩＤキュー５＿（ｍ−１）については、ｍの数が大きいほどキューの長さが短く（容量が少なく）なっている。また、本発明の一実施形態にかかる、ｍ本目のＩＤキュー５＿ｍは、（ｍ−１）本目のＩＤキュー５＿（ｍ−１）の長さと比較して長くなっている。
【００４３】
１本目から（ｍ−１）本目までのＩＤキューについて、ｍの数が大きいほどキューの長さが短くした理由は、アクセス頻度が高く、且つ、アクセス間隔が短いデータだけをストレージ４２２に格納させたいためである。
【００４４】
ｍ本目のＩＤキュー５＿ｍが（ｍ−１）本目のＩＤキュー５＿（ｍ−１）より長くした理由は、アクセス頻度の高いデータがストレージ４２２にできるだけ多く格納され、クライアントＰＣからのアクセス時間を短縮しようとするためである。
【００４５】
本発明の一実施形態によって、ｍ回アクセスされたデータの識別子は、ｍ本目のＩＤキュー５＿ｍに格納され、且つ、ルータ４のストレージ４２２に格納される。一方、（ｍ−１）回以下でアクセスされたデータの識別子は、（ｍ−１）以下の本目のＩＤキューに格納される。よって、偶然短時間に不要なデータを２回アクセスしても、データがルータに格納されることが減少する。また、アクセス頻度の高いデータだけをルータの記憶装置に格納することによって、アクセス頻度の高いデータに対するアクセス時間を短縮することが可能となる。
【００４６】
＜フロー＞  
図６に本発明の一実施形態にかかるデータ中継方法のフローチャートを示す。判定部４１３は、或るデータＸの識別子Ｙが全てのＩＤキューのうちどれかに存在するかどうか判定する（ステップ６０１）。
【００４７】
識別子Ｙが全てのＩＤキューに存在しなかった場合、判定部４１３は、ＩＤキュー５＿１が満杯かどうかを判定する（ステップ６０２）。ＩＤキュー５＿１が満杯であった場合、管理部４１２は、ＩＤキュー５＿１の末尾の識別子を削除し（ステップ６０３）、識別子ＹをＩＤキュー５＿１の先頭に格納する（ステップ６０４）。ＩＤキュー５＿１が満杯でなかった場合、管理部４１２は、識別子ＹをＩＤキュー５＿１の先頭に格納する（ステップ６０４）。
【００４８】
識別子ＹがＩＤキュー５＿ｉ（ｉ＝１〜（ｍ−２））に存在した場合、判定部４１３は、ＩＤキュー５＿（ｉ＋１）が満杯かどうかを判定する（ステップ６０５）。ＩＤキュー５＿（ｉ＋１）が満杯であった場合、管理部４１２は、ＩＤキュー５＿（ｉ＋１）の末尾の識別子を削除し（ステップ６０６）、ＩＤキュー５＿ｉ中の識別子ＹをＩＤキュー５＿（ｉ＋１）の先頭に移動する（ステップ６０７）。ＩＤキュー５＿（ｉ＋１）が満杯でなかった場合、管理部４１２は、ＩＤキュー５＿ｉ中の識別子ＹをＩＤキュー５＿（ｉ＋１）の先頭に移動する（ステップ６０７）。
【００４９】
識別子ＹがＩＤキュー５＿（ｍ−１）（ｍ≧３）に存在した場合、判定部４１３は、ＩＤキュー５＿ｍが満杯かどうかを判定する（ステップ６０８）。ＩＤキュー５＿ｍが満杯であった場合、管理部４１２は、ＩＤキュー５＿ｍの末尾の識別子を削除し（ステップ６０９）、削除した識別子に紐付けられたデータをストレージ４２２から削除し（ステップ６１０）、ＩＤキュー５＿（ｍ−１）中の識別子ＹをＩＤキュー５＿ｍの先頭に移動する（ステップ６１１）。ＩＤキュー５＿ｍが満杯でなかった場合、管理部４１２は、ＩＤキュー５＿（ｍ−１）中の識別子ＹをＩＤキュー５＿ｍの先頭に移動する（ステップ６１１）。管理部４１２は、識別子Ｙに紐付けられたデータＸをストレージ４２２に格納する（ステップ６１２）。
【００５０】
識別子ＹがＩＤキュー５＿ｍに存在した場合、管理部４１３は、ＩＤキュー５＿ｍ中の識別子ＹをＩＤキュー５＿ｍの先頭に移動する（ステップ６１３）。
【００５１】
本発明の一実施形態にかかる中継方法は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通じて提供することも可能である。
【００５２】
本実施形態によれば、クライアントからのデータへのアクセス時間を短縮し、通信機器の消費電力を削減することが可能となる。
【符号の説明】
【００５３】
４  ルータ
５＿１、５＿２、５＿（ｍ−２）、５＿（ｍ−１）、５＿ｍ、１１、１２、１３、１４、１５、１６、１７、４２１  キュー
４１  処理装置
４２  記憶装置
４１１  通信部
４１２  管理部
４１３  判定部
４２２  ストレージ
【図１】
2016010041.tif 000003
【図２】
2016010041.tif 000004
【図３】
2016010041.tif 000005
【図４】
2016010041.tif 000006
【図５】
2016010041.tif 000007
【図６】
2016010041.tif 000008