説明

スロット割当方法、管理装置及びエッジルータ

【課題】エリア毎にスロットが管理されるネットワークにおいて複数エリアを通過するパケットの遅延時間を短縮する。
【解決手段】本管理装置は、(A)スロットがエリア毎に管理されるネットワークにおける隣接エリア及び自エリアを通過する特定パケットについてのスロット割当要求を受信した場合、隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと、隣接エリアにおいて特定パケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に自エリアにおいて特定パケットの送信に対して割り当て可能なスロットを探索することで、自エリアにおいて特定パケットの送信に対して割り当てる割当スロットを決定するスロット決定部と、(B)決定された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ特定パケットの通信経路上のノードに送信する送信部とを有する。

【発明の詳細な説明】
【技術分野】
【0001】
本技術は、有線ネットワークにおいて時分割でデータ転送を行う分野の技術に関する。
【背景技術】
【0002】
時分割でデータ転送を行う技術として、例えばTDM(Time Division Multiplexing)などの技術が知られている。TDMでは、1フレームを複数のタイムスロット(以下、単にスロットと呼ぶ)に区切り、スロット毎に別々のデータ転送を行う。TDMの場合、各ノードは、自身に割り当てられたスロット以外の期間では送信権がないため、自身に割り当てられたスロットの開始時刻になるまで送信待ち状態となる。そのため、ノードがパケットを中継する際には遅延が生じてしまう。
【0003】
なお、中継時の遅延を短縮するような技術は存在しているが、ネットワークが複数エリアに分割され、エリア毎にスロットが管理されるような場合については考慮されていない。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2006−74606号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
従って、本技術の目的は、一側面において、エリア毎にスロットが管理されるネットワークにおいて複数エリアを通過するパケットの遅延時間を短縮するための技術を提供することである。
【課題を解決するための手段】
【0006】
第1の態様に係る管理装置は、(A)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと、隣接エリアにおいて特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に自エリアにおいて特定のパケットの送信に対して割り当て可能なスロットを探索することにより、自エリアにおいて特定のパケットの送信に対して割り当てる割当スロットを決定するスロット決定部と、(B)決定された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ特定のパケットの通信経路上のノードに送信する送信部とを有する。
【0007】
第2の態様に係るエッジルータは、(A)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算する差分計算部と、(B)送信元側のエリア内のノードから送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信する受信部と、(C)受信したパケットを宛先側のエリア内のノードへ送出するための、宛先側のエリアにおけるスロットが割り当てられていない場合、第1のスロットの番号及びスロット差分値、又は第1のスロットの番号とスロット差分値とから特定される優先スロット番号を含むスロット割当要求を、宛先側のエリアにおけるスロットを管理する管理装置に送信する割当要求処理部と、(D)管理装置から割り当てられる第2のスロットを用いてパケットを宛先側のエリア内のノードへ送出するスケジューラとを有する。
【0008】
第3の態様に係る管理装置は、(A)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける自エリア及び第1の隣接エリアを通過する第1のパケットについてのスロット割当要求を受信した場合、自エリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、第1の候補スロットの番号を含む第1の候補リストを生成し、第1の隣接エリアにおける管理装置に通知する候補リスト生成部と、(B)第2の隣接エリア及び自エリアを通過する第2のパケットの送信に対して第2の隣接エリアで割り当て可能なスロットである第2の候補スロットを含む第2の候補リストを受信した場合、当該第2の候補リストに含まれる第2の候補スロット毎に、第2の隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に自エリアにおいて第2のパケットの送信に対して割り当て可能なスロットを探索することにより自エリアにおける第3の候補スロットを特定し、当該優先スロットの番号と第3の候補スロットの番号との差分を遅延時間として計算する候補スロット抽出部と、(C)自エリアが第2のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、遅延時間が最も小さい第3の候補スロットを割当スロットとして選択するスロット選択処理部と、(D)スロット選択処理部により選択された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ第2のパケットの通信経路上のノードに送信すると共に、割当スロットとして選択された第3の候補スロットに対応する第2の候補スロットを特定するためのデータを第2の隣接エリアにおける管理装置に通知する送信部とを有する。
【発明の効果】
【0009】
エリア毎にスロットが管理されるネットワークにおいて複数エリアを通過するパケットの遅延時間を短縮できる。
【図面の簡単な説明】
【0010】
【図1】図1は、ネットワーク構成の一例を示す図である。
【図2】図2は、本技術の実施の形態の前提となる時分割データ転送方式を説明するための図である。
【図3】図3は、時分割データ転送方式において、1フレームを3分割した場合の例を示す図である。
【図4】図4は、複数のエリアで構成されるネットワーク構成の一例を示す図である。
【図5】図5は、エリア間のフレーム開始タイミングの関係の一例を示す図である。
【図6】図6は、パケットが複数エリアを通過する際の処理を説明するための図である。
【図7】図7は、エリアA乃至Cを通過する際の遅延を説明するための図である。
【図8】図8は、本技術の実施の形態の全体の流れを説明するための図である。
【図9】図9は、図8に示した処理でスロットを割り当てた場合に発生する遅延を説明するための図である。
【図10】図10は、エッジルータの機能ブロック図である。
【図11】図11は、エッジノードテーブル格納部に格納されるエッジノードテーブルの一例を示す図である。
【図12】図12は、キュー管理テーブル格納部に格納されるキュー管理テーブルの一例を示す図である。
【図13】図13は、スロット差分値格納部に格納されるデータの一例を示す図である。
【図14】図14は、スケジュールDBに格納されるデータの一例を示す図である。
【図15】図15は、中継ルータの機能ブロック図である。
【図16】図16は、スロットテーブル格納部に格納されるスロットテーブルの一例を示す図である。
【図17】図17は、第1の実施の形態における管理サーバの機能ブロック図である。
【図18】図18は、スロット管理テーブル格納部に格納されるスロット管理テーブルの一例を示す図である。
【図19】図19は、通信経路を説明するための図である。
【図20】図20は、リンク情報格納部に格納されるデータの一例を示す図である。
【図21】図21は、上り方向のリンクと下り方向のリンクとを別々に表した場合の図である。
【図22】図22は、ネットワーク構成の一例を示す図である。
【図23】図23は、第1の実施の形態における処理の処理フローを示す図である。
【図24】図24は、スロット差分計算処理の処理フローを示す図である。
【図25】図25は、スロット割当処理1の処理フローを示す図である。
【図26】図26は、第1の実施の形態における処理の処理フローを示す図である。
【図27】図27は、スロット割当処理2の処理フローを示す図である。
【図28】図28は、スロット差分計算処理2の処理フローを示す図である。
【図29】図29は、スロット差分計算処理2を模式的に示した図である。
【図30】図30は、第2の実施の形態における管理サーバの機能ブロック図である。
【図31】図31は、割当候補リスト格納部に格納されるデータの一例を示す図である。
【図32】図32は、第2の実施の形態の全体の流れを説明するための図である。
【図33】図33は、第2の実施の形態の全体の流れを説明するための図である。
【図34】図34は、第2の実施の形態における処理の処理フローを示す図である。
【図35】図35は、割当候補リスト生成処理の処理フローを示す図である。
【図36】図36は、第2の実施の形態における処理の処理フローを示す図である。
【図37】図37は、割当候補計算処理の処理フローを示す図である。
【図38】図38は、第2の実施の形態における処理の処理フローを示す図である。
【図39】図39は、第2の実施の形態における処理の処理フローを示す図である。
【図40】図40は、第2の実施の形態における処理の処理フローを示す図である。
【図41】図41は、第2の実施の形態における処理の処理フローを示す図である。
【図42】図42は、コンピュータの機能ブロック図である。
【図43】図43は、コンピュータの機能ブロック図である。
【図44】図44は、第1の態様に係る管理装置の機能ブロック図である。
【図45】図45は、第2の態様に係るエッジルータの機能ブロック図である。
【図46】図46は、第3の態様に係る管理装置の機能ブロック図である。
【図47】図47は、第4の態様に係るスロット割当方法の処理フローを示す図である。
【図48】図48は、第5の態様に係る中継処理方法の処理フローを示す図である。
【図49】図49は、第6の態様に係るスロット割当方法の処理フローを示す図である。
【発明を実施するための形態】
【0011】
まず、図1乃至図3を用いて、本技術の実施の形態の前提となる時分割データ転送方式を簡単に説明する。例えば、図1に示すようなネットワークを想定して説明する。図1において、ルータ231がルータ201、ルータ202及びルータ232と接続され、ルータ232はルータ203及びルータ204に接続されている。また、ルータ201はユーザ端末271と接続され、ルータ202はユーザ端末272と接続され、ルータ203はサーバ273と接続され、ルータ204はサーバ274と接続されている。さらに、ルータ201乃至204並びにルータ231及び232は、管理サーバ251と制御線(図1では点線)によって接続されている。ここでは、ユーザ端末271及び272並びにサーバ273及び274などの外部ネットワークに接続されるルータ201乃至204をエッジルータ又はエッジノードと呼ぶ。また、エッジノード間で送信されるパケットを中継するルータ231及び232を中継ルータ又は中継ノードと呼ぶ。図1において、矩形はエッジノードを表しており、丸は中継ノードを表している(以下、同じ)。なお、これは簡単なネットワークの一例であるから、ネットワーク構成はこれに限定されるものではない。
【0012】
なお、管理サーバ251は、スロットの同期を取るのに必要なデータ(例えば1フレームの間隔、1フレーム内のスロット数など)をエッジノード201乃至204に送信するようになっており、エッジノード201乃至204は、管理サーバ251からのデータに従って各スロットの同期を取るようになっている。
【0013】
図2に示すように、例えばユーザ端末271からのパケット(宛先はサーバ274であるものとする)がエッジノード201に到着すると(図2:ステップ(1))、エッジノード201は、パケットをキューに一旦格納し、スロット割当要求を管理サーバ251に送信する(ステップ(2))。このスロット割当要求には、送信元エッジノード及び宛先エッジノードの識別情報などが含まれる。図2の例では、エッジノード201に到着したパケットの宛先がサーバ274であるため、エッジノード201が送信元エッジノードとなり、エッジノード204が宛先エッジノードとなる。なお、以下では、送信元エッジノードを送信元ノードと呼び、宛先エッジノードを宛先ノードと呼ぶ場合もある。
【0014】
そして、管理サーバ251は、エッジノード201から、送信元ノード及び宛先ノードの情報を含むスロット割当要求を受信すると、送信元ノードから宛先ノードへのパケット送信に対して割り当て可能なスロットを探索し、割り当て可能なスロットの中から当該パケット送信に対して割り当てるスロット(以下、割当スロットと呼ぶ)を決定する。この際、管理サーバ251は、他のパケットと衝突しないようなスロットを割当スロットとして決定する。そして、管理サーバ251は、割当スロットの番号と、割当スロットにおいて使用すべき入出力IF(インタフェース)の情報とを含むスロット割当指示を送信元ノードから宛先ノードまでの経路上のノードに送信する(ステップ(3))。図2の例では、管理サーバ251は、エッジノード201と中継ノード231と中継ノード232とエッジノード204とにスロット割当指示を送信する。
【0015】
そして、エッジノード201は、管理サーバ251からのスロット割当指示を受信した後、割り当てられたスロットを用いて、パケットを送出する(ステップ(4))。この際、エッジノード201は、スロットの開始を表す制御パケットを送信してから、キューに格納されているパケットを送出し、スロットの終了を表す制御パケットを最後に送信する。
【0016】
中継ノード231及び232は、管理サーバ251からのスロット割当指示に従って、従来のルーティング処理を行うことなく、パケットを次のノードへ転送する。図2の例では、中継ノード231は、エッジノード201からのパケットを中継ノード232へ転送し、中継ノード232は、中継ノード231からのパケットをエッジノード204へ転送する。
【0017】
例えば図3に、1フレームを3つのスロットに区切った場合の例を示す。図3の例では、スロット1(図3では、t0〜t1、t3〜t4、・・・)において、エッジノード201とエッジノード202との間のパケット通信と、エッジノード203とエッジノード204との間のパケット通信とが行われるようになっている。また、スロット2(図3では、t1〜t2、t4〜t5、・・・)において、エッジノード201とエッジノード203との間のパケット通信が行われるようになっている。さらに、スロット3(図3では、t2〜t3、t5〜t6、・・・)において、エッジノード201とエッジノード204との間のパケット通信が行われるようになっている。なお、図3では、説明を簡単にするために、3つのスロットに区切った場合を一例として示しており、スロットの数はこれに限定されない。
【0018】
このような時分割データ転送方式によれば、中継ノードにおいて、パケットバッファリング及びルーティングテーブル検索処理を行わなくて済むようになる。従って、パケットバッファリング及びルーティング処理で消費していた電力を削減でき、中継ノードの省電力化が可能となる。
【0019】
なお、上では、1台の管理サーバが全てのノードを管理することを前提として説明したが、1台の管理サーバで管理できるノードの数には限りがある。そこで、例えば大規模なネットワークの場合には、図4に示すように、複数のグループ(図4では3つ)に分けて管理するような手法が考えられる。
【0020】
図4では、グループAのエリア(エリアAと呼ぶ)には、エッジノード101と、エッジノード102と、エッジノード107と、エッジノード108と、中継ノード131と、中継ノード132とが属している。そして、中継ノード131はエッジノード101、エッジノード102、エッジノード108及び中継ノード132と接続され、中継ノード132はエッジノード107と接続されている。また、エリアAに属する各ノードは、エリアAを管理する管理サーバ151と制御線(図4では点線)によって接続されている。また、グループBのエリア(エリアBと呼ぶ)には、エッジノード103と、エッジノード104と、エッジノード108と、エッジノード109と、中継ノード133と、中継ノード134とが属している。すなわち、エッジノード108はエリアA及びBの両エリアに属している。そして、中継ノード133はエッジノード103、エッジノード108及び中継ノード134と接続され、中継ノード134はエッジノード104及びエッジノード109と接続されている。また、エリアBに属する各ノードは、エリアBを管理する管理サーバ152と制御線(図4では点線)によって接続されている。さらに、グループCのエリア(エリアC)には、エッジノード105と、エッジノード106と、エッジノード107と、エッジノード109と、中継ノード135と、中継ノード136とが属している。すなわち、エッジノード107はエリアA及びCの両エリアに属しており、エッジノード109はエリアB及びCの両エリアに属している。そして、中継ノード135はエッジノード107及び中継ノード136と接続され、中継ノード136はエッジノード109、エッジノード105及びエッジノード106と接続されている。
【0021】
なお、図4では、エリア毎にそのエリアに属するエッジノードがスロットの同期を取るようになっているものとする。また、1フレームの長さは全エリアで共通しているものとする。但し、例えば図5に示すように、フレーム開始タイミングは、エリア間で同じ場合もあれば、異なる場合もある。図5は、エリアAとエリアBとのフレーム開始タイミングが同じであり、エリアBとエリアCとのフレーム開始タイミングが異なっている例を示している。なお、図5では、100個のスロットで1フレームが構成されているものとする。
【0022】
そして、例えばエリアAに属するエッジノードは、同じくエリアAに属する他のエッジノードへパケットを送信する際には、エリアAの管理サーバ151にスロット割当要求を送信し、管理サーバ151から割り当てられるスロットを用いてパケット送信を行う。また、エリアBに属するエッジノードは、同じくエリアBに属する他のエッジノードへパケットを送信する際には、エリアBの管理サーバ152にスロット割当要求を送信し、管理サーバ152から割り当てられるスロットを用いてパケット送信を行う。さらに、エリアCに属するエッジノードは、同じくエリアCに属する他のエッジノードへパケットを送信する際には、エリアCの管理サーバ153にスロット割当要求を送信し、管理サーバ153から割り当てられるスロットを用いてパケット送信を行う。
【0023】
例えばエリアA、エリアB、エリアCの順に3つのエリアを通過するパケットがあった場合、図6に示すような流れでパケットが送信される。まず、エッジノード101にパケットが到着すると(図6:ステップ(11))、エッジノード101は、エリアAの管理サーバ151にスロット割当要求を送信する(ステップ(12))。管理サーバ151は、エッジノード101からのスロット割当要求に応じて、エリアAにおける割当スロットを決定し、スロット割当指示を経路上のノードに送信する(ステップ(13))。ここでは、スロット2が割り当てられたものとする。そして、エッジノード101は、管理サーバ151から割り当てられたスロット2を用いて、エッジノード108へパケットを送信する。
【0024】
そして、エッジノード108にパケットが到着すると(ステップ(14))、エッジノード108は、エリアBの管理サーバ152にスロット割当要求を送信する(ステップ(15))。管理サーバ152は、エッジノード108からのスロット割当要求に応じて、エリアBにおける割当スロットを決定し、スロット割当指示を経路上のノードに送信する(ステップ(16))。ここでは、スロット1が割り当てられたものとする。そして、エッジノード108は、管理サーバ152から割り当てられたスロット1を用いて、エッジノード109へパケットを送信する。
【0025】
そして、エッジノード109にパケットが到着すると(ステップ(17))、エッジノード109は、エリアCの管理サーバ153にスロット割当要求を送信する(ステップ(18))。管理サーバ153は、エッジノード109からのスロット割当要求に応じて、エリアCにおける割当スロットを決定し、スロット割当指示を経路上のノードに送信する(ステップ(19))。ここでは、スロット1が割り当てられたものとする。そして、エッジノード109は、管理サーバ153から割り当てられたスロット1を用いて、エッジノード105へパケットを送信する。
【0026】
しかしながら、図5に示したように、エリアAとエリアBとのフレーム開始タイミングが同じであったとすると、エッジノード108は、エリアAのスロット2によって送信されてくるパケットをエリアBへ転送するためには、エリアBのスロット1の開始時間になるまで待たなければならず、図7に示すように99スロット分の遅延が生ずることとなる。また、図5に示したように、エリアBとエリアCとのフレーム開始タイミングが異なっていたとすると、エッジノード109は、エリアBのスロット1によって送信されてくるパケットをエリアCへ転送するためには、エリアCのスロット1の開始時刻になるまで待たなければならず、図7に示すように99スロット分の遅延が生ずることとなる。従って、例えばスロット長が1msであった場合には、エリアA乃至Cを通過する際に毎回198ms程度の遅延が生ずることになってしまう。
【0027】
そこで、本技術の実施の形態では、エリア間のスロットのずれと前のエリアで使用されているスロットの番号とを考慮して、遅延が少なくなるようなスロットを割り当てるようにする。例えば図8に示すように、エリア間の境界に設置されるエッジノード108及び109が、事前にエリア間のスロットのずれを表すスロット差分値Sij(iは入力側エリア、jは出力側エリアを表す)を計算しておく(図8:ステップ(20))。より具体的には、エッジノード108は、スロット差分値SAB及びSBAを計算し、エッジノード109は、スロット差分値SBC及びSCBを計算する。ここでは、SABは0であり、SBCは1であるものとする。なお、スロット差分値の計算処理については後で詳細に説明する。
【0028】
そして、エッジノード101にパケットが到着すると(ステップ(21))、エッジノード101は、エリアAの管理サーバ151にスロット割当要求を送信する(ステップ(22))。管理サーバ151は、エッジノード101からのスロット割当要求に応じて、エリアAにおける割当スロットを決定し、スロット割当指示を経路上のノードに送信する(ステップ(23))。ここでは、スロット2が割り当てられたものとする。そして、エッジノード101は、管理サーバ151から割り当てられたスロット2を用いて、エッジノード108へパケットを送信する。
【0029】
そして、エッジノード108にパケットが到着すると(ステップ(24))、エッジノード108は、エリアAで使用されているスロットの番号(=2)とスロット差分値SAB(=0)とを用いて優先スロット番号(2+0=2)を計算する。そして、エリアBの管理サーバ152に、優先スロット番号(=2)を含むスロット割当要求を送信する(ステップ(25))。そして、管理サーバ152は、エッジノード108からのスロット割当要求に応じて、優先スロットであるスロット2から順に割り当て可能なスロットを探索し、エリアBにおける割当スロットを決定する(ステップ(26))。ここでは、スロット3が割り当て可能なスロットとして最初に検出され、割当スロットとして決定されたものとする。そして、管理サーバ152は、スロット割当指示を経路上のノードに送信する(ステップ(27))。その後、エッジノード108は、管理サーバ152から割り当てられたスロット3を用いて、エッジノード109へパケットを送信する。
【0030】
そして、エッジノード109にパケットが到着すると(ステップ(28))、エッジノード109は、エリアBで使用されているスロットの番号(=3)とスロット差分値SBC(=1)とを用いて優先スロット番号(3+1=4)を計算する。そして、エリアBの管理サーバ153に、優先スロット番号(=4)を含むスロット割当要求を送信する(ステップ(29))。そして、管理サーバ153は、エッジノード109からのスロット割当要求に応じて、優先スロットであるスロット4から順に割り当て可能なスロットを探索し、エリアCにおける割当スロットを決定する(ステップ(30))。ここでは、スロット4が割り当て可能なスロットとして最初に検出され、割当スロットとして決定されたものとする。そして、管理サーバ153は、スロット割当指示を経路上のノードに送信する(ステップ(31))。その後、エッジノード109は、管理サーバ153から割り当てられたスロット4を用いて、エッジノード105へパケットを送信する。
【0031】
これにより、図9に示すように、エリアAのスロット2によって送信されてくるパケットをエリアBへ転送する際には、1スロット分の遅延(1ms)で済むようになる。また、エリアBのスロット3によって送信されてくるパケットをエリアCへ転送する際には遅延時間は発生しない。従って、エリアA乃至Cを通過する際に生ずる遅延は1ms程度となり、少ない遅延で済むようになる。
【0032】
[実施の形態1]
図10に、本技術の第1の実施の形態におけるエッジルータの機能ブロック図を示す。エッジルータは、パケット受信部1001と、宛先エッジノード毎のキュー1003(図10では1003a乃至1003c)を有するパケット分類部1002と、エッジノードテーブル格納部1004と、キュー管理テーブル格納部1005と、制御部1006と、差分計算部1007と、スロット差分値格納部1008と、割当要求処理部1009と、スケジュールDB1010と、スケジューラ1011とを有する。
【0033】
パケット受信部1001は、外部ネットワーク又は他のエッジノードからのパケットを受信し、パケット分類部1002に出力する。パケット分類部1002は、エッジノードテーブル格納部1004及びキュー管理テーブル格納部1005に格納されているデータを用いて、パケット受信部1001が受信したパケットを該当するキュー1003に格納したり、スロットの割り当てが必要な場合には割当要求処理部1009に処理を行うよう指示したりする。なお、受信したパケットが他のノードから送信されてきたものである場合には、パケット分類部1002は、パケット送信に使用されているスロット番号を取得し、割当要求処理部1009に出力する。制御部1006は、管理サーバからスロット同期のためのデータを受信し、受信データを用いてスロットの同期を取るための処理を実施し、スロットの切り替わるタイミングをスケジューラ1011に通知する。また、制御部1006は、スロット同期のためのデータを複数の管理サーバから受信した場合には、自エッジノードがエリア間の境界に置かれているノード(以下、境界ノードと呼ぶ)であると判断し、境界ノードである旨の通知を差分計算部1007及び割当要求処理部1009に出力する。差分計算部1007は、制御部1006から境界ノードである旨の通知を受信すると、エリア間のスロットのずれを表すスロット差分値を計算し、スロット差分値格納部1008に格納する。割当要求処理部1009は、パケット分類部1002からの指示に応じてスロット割当要求を管理サーバに送信したり、管理サーバからのスロット割当指示を受信した場合にはスロット割当指示に含まれるデータをスケジュールDB1010に格納したりする。なお、割当要求処理部1009は、制御部1006から境界ノードである旨の通知を受信している場合には、スロット差分値格納部1008に格納されているデータとパケット分類部1002からのスロット番号(すなわち、前のエリアで使用されているスロット番号)とを用いて優先スロット番号を計算し、優先スロット番号を含むスロット割当要求を管理サーバに送信する。スケジューラ1011は、制御部1006からの通知に応じて、スケジュールDB1010に格納されているデータに従って、パケット分類部1002内のキュー1003に格納されているパケットを送出する。
【0034】
エッジノードテーブル格納部1004には、例えば図11に示すようなエッジノードテーブルが予め格納されている。図11の例では、エッジノードテーブルには、宛先アドレスの列と、宛先エッジノードの列とが含まれる。例えば、宛先アドレスが192.168.1.10であれば、宛先エッジノードはノードBであることが分かる。
【0035】
また、キュー管理テーブル格納部1005には、例えば図12に示すようなキュー管理テーブルが格納される。図12の例では、キュー管理テーブルには、キューIDの列と、宛先エッジノードの列とが含まれる。例えば宛先エッジノードがノードBであるパケットの格納先は、ID「q001」のキューであることが分かる。
【0036】
さらに、スロット差分値格納部1008には、例えば図13に示すようなデータが格納される。図13の例では、スロット差分値格納部1008には、入力側エリアと、出力側エリアと、スロット差分値とが格納されるようになっている。例えば、入力側エリアがエリアA、出力側エリアがエリアBの場合、スロット差分値SABは2となっている。
【0037】
また、スケジュールDB1010には、例えば図14に示すようなデータが格納される。図14の例では、スケジュールDB1010には、スロット番号と、出力IFと、キューIDの列とが格納されるようになっている。例えば、ID「q001」のキューに格納されているパケットについては、スロット1を用いて、eth0のIFに出力するようスケジューリングされていることを示している。
【0038】
次に、図15に、第1の実施の形態における中継ルータの機能ブロック図を示す。中継ルータは、スロットテーブル管理部1301と、スロットテーブル格納部1302と、スイッチ部1303とを有する。
【0039】
スロットテーブル管理部1301は、管理サーバからのスロット割当指示を受信し、スロット割当指示に含まれるスロット番号及び入出力IFの情報をスロットテーブル格納部1302に格納する。スイッチ部1303は、スロットテーブル格納部1302に格納されているデータに従ってIFの切り替えを行う。
【0040】
スロットテーブル格納部1302には、例えば図16に示すようなスロットテーブルが格納される。図16の例では、スロットテーブルには、入力の列と、出力の列とが含まれる。入力の列には、パケットが入力されるIFの識別情報とスロット番号とが格納されるようになっている。また、出力の列には、パケットの出力先となるIFの識別情報が格納されるようになっている。例えば、スロット1では、eth0のIFから入力されるパケットをeth1のIFへ出力することを示している。
【0041】
次に、図17に、第1の実施の形態における管理サーバの機能ブロック図を示す。管理サーバは、受信部1501と、スロット割当処理部1502と、スロット管理テーブル格納部1503と、リンク情報格納部1504と、送信部1505と、エリア管理DB1506とを有する。
【0042】
受信部1501は、エッジノードからのスロット割当要求を受信し、スロット割当処理部1502に出力する。スロット割当処理部1502は、スロット管理テーブル格納部1503及びリンク情報格納部1504に格納されているデータを用いて、後で説明するスロット割当処理を実施し、スロット割当指示を送信するよう送信部1505に指示する。送信部1505は、スロット割当処理部1502からの指示に応じてスロット割当指示を送信する。また、エリア管理DB1506には、スロット同期のためのデータなどが格納されており、送信部1505は、スロット同期のためのデータをエリア管理DB1506から読み出し、エリアに属するエッジノードへ送信する。
【0043】
スロット管理テーブル格納部1503には、例えば図18に示すようなスロット管理テーブルが格納される。図18の例では、スロット管理テーブルには、送信元エッジノードの列と、宛先エッジノードの列と、スロット番号の列と、経路の列とが含まれる。例えば図19に示すようなノードA乃至Hを含むエリアであった場合に、図18の一番上のレコードは、ノードAからノードCへのパケット送信に対してスロット1が割り当てられており、ノードAからノードCまでの経路は「ノードA−>ノードE−>ノードG−>ノードC」であることを示している。なお、図19において、ノードEはノードA、ノードF、ノードG及びノードHと接続され、ノードFはノードB、ノードG及びノードHと接続され、ノードGはノードC及びノードHと接続され、ノードHはノードDと接続されている。
【0044】
また、リンク情報格納部1504には、例えば図20に示すようなデータが格納される。図20の例では、上り方向のリンクの使用状態(0:未使用、1:使用済み)と下り方向のリンクの使用状態とを別々に管理するようになっている。例えば図19では、上り方向のリンクと下り方向のリンクとをまとめて1本の線で表しているが、これらを別々に図示すると図21のようになる。すなわち、図21における矢印の本数(20本)分のレコードが、リンク情報格納部1504に格納される。図20の例では、リンク情報格納部1504には、リンクの両端ノードのうち始点側ノードの番号(src)の列と、終点側ノードの番号(dst)の列と、スロット1の列と、スロット2の列と、・・・と、スロットnの列とが含まれる。例えば、「ノードA−>ノードE」のリンクがスロット1で使用されることになった場合には、「ノードA−>ノードE」のレコード(すなわち、srcの列が「A」且つdstの列が「E」のレコード)のスロット1の列に「1」(使用済み)が設定される。
【0045】
また、エリア管理DB1506には、エリアに属するエッジノード及び中継ノードの情報や、スロット同期のためのデータ(例えばフレーム長、1フレーム内のスロット数など)、エリアに属する各ノードの入出力IFの情報などが格納されている。
【0046】
次に、図22乃至図29を用いて、エッジルータ、中継ルータ及び管理サーバの処理について説明する。なお、ここでは、図22に示すようにパケットがエリアA及びBを通過する場面を想定して説明する。図22では、管理サーバAがエリアAを担当し、管理サーバBがエリアBを担当するようになっている。また、エリアAにおける通信経路は、「エッジノードA−>中継ノードA−>エッジノードB」であり、エリアBにおける通信経路は、「エッジノードB−>中継ノードB−>エッジノードC」であるものとする。また、前提として、管理サーバAは、自身のエリア管理DB1506に格納されているスロット同期のためのデータを既にエッジノードA及びBに送信しており、管理サーバBも、自身のエリア管理DB1506に格納されているスロット同期のためのデータを既にエッジノードB及びCに送信しているものとする。
【0047】
まず、エッジノードBの制御部1006が、管理サーバA及びBの各々からスロット同期のためのデータを受信する。そして、制御部1006は、複数の管理サーバからデータを受信したことで、自ノードが境界ノードであると判断し、境界ノードである旨の通知を差分計算部1007及び割当要求処理部1009に出力する。そして、エッジノードBの差分計算部1007は、制御部1006からの通知を受信すると、スロット差分計算処理を実施する(図23:ステップS1)。このスロット差分計算処理については図24を用いて説明する。
【0048】
まず、差分計算部1007は、入力側エリアの時刻tにおけるスロット番号aを取得する(図24:ステップS51)。また、差分計算部1007は、出力側エリアの時刻t+dtにおけるスロット番号bを取得する(ステップS53)。なお、dtは、エッジノードにおける遅延時間を表し、dt=0としてもよい。そして、差分計算部1007は、スロット番号aとスロット番号bとを用いてスロット差分値Sijを算出し、スロット差分値格納部1008に格納する(ステップS55)。具体的には、Sij=mod(b−a,最大スロット番号)によって算出する。なお、管理サーバから通知されるスロット同期のためのデータには1フレーム内のスロット数が含まれており、このスロット数から最大スロット番号が特定される。例えば1フレーム内のスロット数が100であれば、最大スロット番号も100となる。例えば入力側エリアをエリアAとし、出力側エリアをエリアBとした際に、エリアAの時刻tにおけるスロット番号aが2であり、エリアBの時刻tにおけるスロット番号bが3であり、最大スロット番号が100であった場合、スロット差分値SABは、mod(3−2,100)=1となる。また、差分計算部1007は、エリアBを入力側エリア、エリアAを出力側エリアとしてステップS51乃至S55の処理を実施し、SBAも算出する。すなわち、エリアAとエリアBとの境界にいる場合には、エリアAからエリアBの方向と、エリアBからエリアAの方向との両方向についてステップS51乃至S55の処理を実施し、SABとSBAとを算出する。その後、処理を終了し、元の処理に戻る。
【0049】
図23の説明に戻って、エッジノードAのパケット受信部1001は、外部ネットワークからのパケットを受信すると、受信パケットをパケット分類部1002に出力する。そして、パケット分類部1002は、受信パケットをキュー1003に格納する(ステップS3)。具体的には、エッジノードAのパケット分類部1002が、パケットの宛先アドレスを用いてエッジノードテーブル格納部1004を検索し、宛先エッジノードを特定する。そして、宛先エッジノードを用いてキュー管理テーブル格納部1005を検索し、宛先エッジノードに対応するキューIDを特定し、特定したキューIDを持つキュー1003にパケットを格納する。その後、パケット分類部1002が、スロットの割り当てが必要であると判断し、割当要求処理部1009に処理を行うよう指示する。そして、エッジノードAの割当要求処理部1009は、パケット分類部1002からの指示に応じて、スロット割当要求を管理サーバAに送信する(ステップS5)。なお、このスロット割当要求には、送信元エッジノード及び宛先エッジノードの識別情報などが含まれる。
【0050】
そして、管理サーバAの受信部1501は、エッジノードAからのスロット割当要求を受信すると(ステップS7)、受信したスロット割当要求をスロット割当処理部1502に出力する。そして、管理サーバAのスロット割当処理部1502は、受信したスロット割当要求と、スロット管理テーブル格納部1503とリンク情報格納部1504とエリア管理DB1506とに格納されているデータとを用いてスロット割当処理1を実施する(ステップS9)。このスロット割当処理1については図25を用いて説明する。
【0051】
まず、スロット割当処理部1502は、リンク情報格納部1504に格納されているデータを用いて、スロット割当要求に含まれる送信元エッジノードから宛先エッジノードまでの通信経路を未使用リンクによって形成可能なスロットを抽出する(図25:ステップS61)。そして、スロット割当処理部1502は、抽出したスロット毎に、未使用リンクによる最短経路を特定し、最短経路におけるホップ数を算出する(ステップS63)。例えばダイクストラ法などによって送信元エッジノードから宛先エッジノードまでの最短経路を特定する。そして、スロット割当処理部1502は、最短経路におけるホップ数が許容ホップ数以下となるスロットの中から自エリア(ここでは、エリアA)における割当スロットを選択する(ステップS65)。例えば、全てのリンクを未使用とした場合の最短経路におけるホップ数を最小ホップ数とし、最小ホップ数+αを許容ホップ数として用いる。また、条件を満たすスロットが複数存在する場合には、例えば最短経路におけるホップ数が最も小さいスロットを割当スロットとして選択する。そして、スロット割当処理部1502は、リンク情報格納部1504において、割当スロットの未使用リンクによる最短経路に含まれるリンクを使用済みに設定する(ステップS67)。また、スロット割当処理部1502は、送信元エッジノードと宛先エッジノードと割当スロットの番号と最短経路情報とを含むレコードをスロット管理テーブル格納部1503に登録する(ステップS68)。また、スロット割当処理部1502は、エリア管理DB1506に格納されているデータと最短経路情報とを用いて、最短経路上の各ノードが使用するべき入出力IFを特定する(ステップS69)。その後、処理を終了し、元の処理に戻る。
【0052】
図23の説明に戻って、管理サーバAのスロット割当処理部1502は、最短経路上の各ノードに対してスロット割当指示を送信するよう送信部1505に指示する。この際、スロット割当処理1の処理結果である割当スロットの番号、最短経路情報及び入出力IFの情報を送信部1505に渡す。そして、送信部1505は、スロット割当処理部1502からの指示に応じて、割当スロット番号と入出力IF情報とを含むスロット割当指示を最短経路上の各ノードに送信する(ステップS11)。ここでは、管理サーバAの送信部1505は、エッジノードA、中継ノードA及びエッジノードBにスロット割当指示を送信する。
【0053】
そして、エッジノードA、中継ノードA及びエッジノードBは、管理サーバAからのスロット割当指示を受信する(ステップS13乃至S17)。なお、エッジノードAは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスケジュールDB1010に格納する。また、中継ノードAは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスロットテーブル格納部1302に格納する。
【0054】
その後、エッジノードAのスケジューラ1011は、エッジノードAからエッジノードBへのパケット送信に対して割り当てられているスロットの開始時刻になると、スケジュールDB1010のデータから特定されるキュー1003に格納されているパケットを、スケジュールDB1010のデータから特定される出力IFへ送出する(ステップS19)。この際、スケジューラ1011は、スロットの開始を表す第1制御パケットを送信してから、キュー1003内のパケットを送出する。さらに、そのスロットの最後に、スロットの終了を表す第2制御パケットを送信する。例えばスロット1が割り当てられていた場合、スロット1の開始時刻になったら、スロット番号「1」を含む第1制御パケットを送信し、その後、スロット1が終了するまでの間、キュー1003に格納されているパケットを出力IFへ送出する。そして、スロット1の最後に、スロット番号「1」を含む第2制御パケットを送信する。
【0055】
そして、中継ノードAのスイッチ部1303は、スロットテーブル格納部1302に格納されているデータに従って、エッジノードAからエッジノードBへのパケットを中継する(ステップS21)。具体的には、第1制御パケットを受信した場合、スイッチ部1303は、第1制御パケットに含まれるスロット番号を用いてスロットテーブル格納部1302を検索し、スロット番号に対応する入力IF及び出力IFを特定する。そして、第2制御パケットを受信するまでの間、特定した入力IFからのパケットを、特定した出力IFへ転送する。すなわち、中継ノードAは、従来のルーティング処理を行うことなく、エッジノードAからエッジノードBへのパケットを中継する。
【0056】
そして、エッジノードBのパケット受信部1001は、中継ノードAを介してエッジノードAからのパケットを受信すると、受信パケットをパケット分類部1002に出力する。そして、パケット分類部1002は、受信パケットをキュー1003に格納する(ステップS23)。本ステップの処理は、基本的にはステップS3の処理と同じであるため、ここでは詳細な説明は省略する。その後、端子Aを介してステップS25(図26)に移行する。
【0057】
図26の説明に移行して、端子Aの後、エッジノードBのパケット分類部1002が、スロットの割り当てが必要であると判断し、割当要求処理部1009に処理を行うよう指示する。ここで、エッジノードBは境界ノードであるため、エッジノードBの割当要求処理部1009は、パケット分類部1002からの指示を受信すると、前のエリア(ここでは、エリアA)で使用されているスロットの番号とスロット差分値格納部1008に格納されているスロット差分値Sij(ここでは、SAB)とを用いて優先スロット番号を計算する(ステップS25)。具体的には、前のエリアで使用されているスロットの番号をsとし、優先スロット番号=s+Sijによって算出する。なお、割当要求処理部1009は、制御部1006から境界ノードである旨の通知を受信することで、自エッジノードが境界ノードであることを把握する。その後、エッジノードBの割当要求処理部1009は、送信元エッジノードと宛先エッジノードと優先スロット番号とを含むスロット割当要求を管理サーバBに送信する(ステップS27)。
【0058】
そして、管理サーバBの受信部1501は、エッジノードBからのスロット割当要求を受信すると(ステップS29)、受信したスロット割当要求をスロット割当処理部1502に出力する。そして、管理サーバBのスロット割当処理部1502は、受信したスロット割当要求と、スロット管理テーブル格納部1503とリンク情報格納部1504とエリア管理DB1506とに格納されているデータとを用いてスロット割当処理2を実施する(ステップS31)。このスロット割当処理2については図27を用いて説明する。
【0059】
まず、スロット割当処理部1502は、スロット割当要求に含まれる優先スロット番号を、処理対象のスロット番号を表す変数xに設定する(図27:ステップS71)。そして、スロット割当処理部1502は、リンク情報格納部1504に格納されているデータを用いて、送信元エッジノードから宛先エッジノードまでの経路のうち、スロットxの未使用リンクによる最短経路を計算する(ステップS73)。例えばダイクストラ法などによって、送信元エッジノードから宛先エッジノードまでの最短経路を計算する。そして、スロット割当処理部1502は、送信元エッジノードから宛先エッジノードまでのパケット送信に対してスロットxを割り当てることができるか否か判断する(ステップS75)。例えば、最短経路におけるホップ数が許容ホップ数以下であれば、割り当て可能と判断し、最短経路におけるホップ数が許容ホップ数を超えている場合や、未使用リンクによって送信元エッジノードから宛先エッジノードまでの経路を確保できないような場合には、割り当て不可と判断する。
【0060】
そして、スロットxを割り当てることが可能であると判断した場合(ステップS75:Yesルート)、スロット割当処理部1502は、スロットxを自エリア(ここでは、エリアB)における割当スロットとして決定する(ステップS77)。そして、スロット割当処理部1502は、リンク情報格納部1504において、スロットxの未使用リンクによる最短経路に含まれるリンクを使用済みに設定する(ステップS79)。また、スロット割当処理部1502は、送信元エッジノードと宛先エッジノードと割当スロットの番号と最短経路情報とを含むレコードをスロット管理テーブル格納部1503に登録する(ステップS81)。また、スロット割当処理部1502は、エリア管理DB1506に格納されているデータと最短経路情報とを用いて、最短経路上の各ノードが使用するべき入出力IFを特定する(ステップS83)。その後、処理を終了し、元の処理に戻る。
【0061】
一方、スロットxを割り当てることはできないと判断した場合(ステップS75:Noルート)、スロット割当処理部1502は、変数xの値を1インクリメントし(ステップS85)、変数xの値が最大スロット番号を超えたかどうか判断する(ステップS87)。変数xの値が最大スロット番号を超えている場合には(ステップS87:Yesルート)、スロット割当処理部1502は、変数xに1を設定する(ステップS89)。一方、変数xの値が最大スロット番号を超えていなければ(ステップS87:Noルート)、ステップS91の処理に移行する。
【0062】
その後、スロット割当処理部1502は、変数xの値が優先スロット番号と等しいかどうか判断する(ステップS91)。変数xの値が優先スロット番号と等しくない場合(ステップS91:Noルート)、ステップS73の処理に戻り、上で述べた処理を繰り返す。なお、変数xの値が優先スロット番号と等しくないということは、割り当て可能かどうか判定していないスロットがあるということを意味する。
【0063】
一方、変数xの値が優先スロット番号と等しい場合(ステップS91:Yesルート)、ステップS93の処理に移行する。なお、変数xの値が優先スロット番号と等しいと判断されるのは、優先スロット番号から順に全てのスロットについて判定したが、割り当て可能なスロットが見つからなかった場合である。この場合、スロット割当処理部1502は、割り当て失敗を表す応答をスロット割当要求の要求元へ送信する(ステップS93)。その後、処理を終了する。
【0064】
以上のように、優先スロットから順に割り当て可能なスロットを探索することによって、遅延が少なくなるようなスロットを割り当てることができる。なお、上では、優先スロットから順に割り当て可能なスロットを探索し、最初に検出されたものを割当スロットとして決定するようになっていたが、最初に検出されたものを毎回割り当てるのではなく、優先スロットから少し離れたスロットを割り当てるようにしてもよい。これにより、優先スロットの後方にある程度の隙間を設けつつ、優先スロットに近いスロットを割り当てることができる。なお、隙間の部分については、別のパケット送信に割り当てることができるようになる。どの程度の間隔を設けるかは、ランダムに決定するようにしてもよいし、運用状況に応じて管理者が設定するようにしてもよい。
【0065】
図26の説明に戻って、管理サーバBのスロット割当処理部1502は、最短経路上の各ノードに対してスロット割当指示を送信するよう送信部1505に指示する。この際、スロット割当処理2の処理結果である割当スロットの番号、最短経路情報及び入出力IFの情報を送信部1505に渡す。そして、送信部1505は、スロット割当処理部1502からの指示に応じて、割当スロット番号と入出力IF情報とを含むスロット割当指示を最短経路上の各ノードに送信する(ステップS33)。ここでは、管理サーバBの送信部1505は、エッジノードB、中継ノードB及びエッジノードCにスロット割当指示を送信する。
【0066】
そして、エッジノードB、中継ノードB及びエッジノードCは、管理サーバBからのスロット割当指示を受信する(ステップS35乃至S39)。なお、エッジノードBは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスケジュールDB1010に格納する。また、中継ノードBは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスロットテーブル格納部1302に格納する。
【0067】
その後、エッジノードBのスケジューラ1011は、エッジノードBからエッジノードCへのパケット送信に対して割り当てられているスロットの開始時刻になると、スケジュールDB1010のデータから特定されるキュー1003に格納されているパケットを、スケジュールDB1010のデータから特定される出力IFへ送出する(ステップS41)。なお、上でも述べたように、スケジューラ1011は、第1制御パケットを送信してから、キュー1003内のパケットを送出し、スロットの最後に第2制御パケットを送信する。
【0068】
そして、中継ノードBのスイッチ部1303は、スロットテーブル格納部1302に格納されているデータに従って、エッジノードBからエッジノードCへのパケットを中継する(ステップS43)。本ステップの処理は、基本的にはステップS21の処理と同じであるため、ここでは詳細な説明は省略する。
【0069】
そして、エッジノードCのパケット受信部1001は、中継ノードBを介してエッジノードBからのパケットを受信する(ステップS45)。そして、エッジノードCは、宛先となるユーザ端末等や外部ネットワークにパケットを転送する。
【0070】
以上のような処理を実施することによって、管理サーバBにおいて、遅延が少なくなるようなスロットを割り当てることができ、エリアA及びBを通過する際に生ずる遅延時間を短くすることができる。なお、エリア間のスロット番号のずれを考慮した上でスロットを割り当てるので、エリア間でフレーム開始タイミングがずれているような場合でも、遅延が少なくなるようなスロットを割り当てることができる。
【0071】
また、上では、エリア間の境界にいるエッジノードが優先スロット番号を計算し、優先スロット番号を管理サーバへ渡すようになっていたが、前のエリアで使用されているスロットの番号とスロット差分値とを管理サーバへ渡すようにして、管理サーバで優先スロット番号を計算するようにしてもよい。
【0072】
また、図24に示したスロット差分計算処理の代わりに、図28に示すような処理(スロット差分計算処理2と呼ぶ)をステップS1(図23)において実施するようにしてもよい。以下、図28を用いて、スロット差分計算処理2について説明する。
【0073】
まず、差分計算部1007が、各々のエリア内を流れる第1制御パケットを監視する(図28:ステップS101)。なお、上でも述べたように、パケットが送信される際には、スロットの先頭に第1制御パケットが送信されるようになっている。そして、差分計算部1007は、エリア毎に、あるスロット番号を含む第1制御パケットを受信した時点における内部時計の時刻と当該スロット番号とを記録する(ステップS103)。例えば、図29に示すように、エリアAの中継ノードに接続されるIF1から流れてくるパケットを監視し、スロット番号「1」を含む第1制御パケットを検出すると、当該第1制御パケットを受信した時点における内部時計の時刻t1を取得し、時刻t1とスロット番号「1」とを記録する。さらに、エリアBの中継ノードに接続されるIF2から流れてくるパケットを監視し、スロット番号「1」を含む第1制御パケットを検出すると、当該第1制御パケットを受信した時点における内部時計の時刻t2を取得し、時刻t2とスロット番号「1」とを記録する。
【0074】
そして、差分計算部1007は、ステップS103において記録した時刻及びスロット番号とを用いて、エリア間の時差を算出し、スロット長とエリア間の時差とからスロット差分値Sijを算出してスロット差分値格納部1008に格納する(ステップS105)。なお、スロット長は、スロット同期のためのデータに含まれるフレーム長と1フレーム内のスロット数とから算出することができる。そして、処理を終了し、元の処理に戻る。このようにしても、スロット差分値Sijを算出することができる。
【0075】
[実施の形態2]
次に、図30乃至図41を用いて、第2の実施の形態について説明する。第2の実施の形態では、管理サーバが自エリアにおいて割り当て可能なスロットの中から割当候補スロットを抽出し、割当候補スロットの番号を含む割当候補リストを次のエリアにおける管理サーバへ通知する。そして、末端エリアにおける管理サーバが、各エリアで列挙された割当候補スロットに従って、全体の遅延時間が最も少なくなるような割り当てを決定する。
【0076】
第2の実施の形態における管理サーバの機能ブロック図を図30に示す。なお、エッジルータ及び中継ルータの機能ブロック図は、基本的には第1の実施の形態と同じである。第2の実施の形態における管理サーバは、受信部1501と、スロット割当処理部1510と、スロット管理テーブル格納部1503と、リンク情報格納部1504と、送信部1505と、エリア管理DB1506と、割当候補リスト格納部1507とを有する。なお、受信部1501と、スロット管理テーブル格納部1503と、リンク情報格納部1504と、送信部1505と、エリア管理DB1506とは、第1の実施の形態と同じものである。
【0077】
また、スロット割当処理部1510は、候補リスト生成部1511と、候補スロット抽出部1512と、スロット選択処理部1513とを含む。候補リスト生成部1511は、スロット管理テーブル格納部1503及びリンク情報格納部1504に格納されているデータを用いて割当候補リストを生成するなどの処理を実施し、生成した割当候補リストを割当候補リスト格納部1507に格納する。候補スロット抽出部1512は、前のエリアの管理サーバからの割当候補リストとスロット管理テーブル格納部1503及びリンク情報格納部1504に格納されているデータとを用いて自エリアの割当候補スロットを抽出したり、遅延累計を計算したりして、処理結果を割当候補リスト格納部1507に格納する。スロット選択処理部1513は、割当候補リスト格納部1507に格納されているデータを用いて割当スロットを選択するなどの処理を実施する。
【0078】
割当候補リスト格納部1507には、例えば図31に示すようなデータが格納される。図31の例では、割当候補リスト格納部1507には、順位の列と、自エリアの割当候補スロット番号の列と、遅延累計の列とが含まれる。例えば自エリアにおいてスロット番号が7のスロットを割り当てたとすると、自エリアを通過するまでの間に、5スロット分の遅延が生ずることを表している。
【0079】
まず、図32及び図33を用いて、本実施の形態の全体の流れについて説明しておく。ここでは、パケットがエリアA乃至Cの3つのエリアを通過する場面を想定して説明する。まず、エリア間の境界に設置されるエッジノードB及びC(図32ではノードB及びC)が、エリア間のスロットのずれを表すスロット差分値Sijを計算し、スロット差分値格納部1008に格納する(図32:ステップ(40))。ここでは、SABは0であり、SBCは2であるものとする。
【0080】
そして、エッジノードA(図32ではノードA)にパケットが到着すると(ステップ(41))、エッジノードAは、エリアAの管理サーバAにスロット割当要求を送信する(ステップ(42))。管理サーバAは、エッジノードAからのスロット割当要求に応じて、エリアAにおける割当候補スロットを所定数分抽出し(ステップ(43))、割当候補スロットの番号を含む割当候補リストAをエッジノードBへ送信する(ステップ(44))。また、管理サーバAは、割当候補リストAを割当候補リスト格納部1507に格納しておく。ここでは、スロット10とスロット20とスロット50とが割当候補スロットとして抽出されたものとする。なお、エリアAは、先頭エリアであるため、遅延累計は0となっている。
【0081】
そして、エッジノードBは、管理サーバAからの割当候補リストAを受信すると、割当候補リストAにおける割当候補スロット毎に、当該割当候補スロットの番号とスロット差分値格納部1008に格納されているスロット差分値ABとを用いて優先スロット番号を計算し、優先スロット番号によって割当候補リストAを更新する(ステップ(45))。但し、スロット差分値ABが0であるため、ここでは、割当候補リストAは元のままである。そして、エッジノードBは、割当候補リストAを管理サーバBに送信する(ステップ(46))。
【0082】
そして、管理サーバBは、エッジノードBから割当候補リストAを受信すると、割当候補リストAにおける割当候補スロット毎に、当該割当候補スロットの番号(すなわち、優先スロット番号)から順に、エリアBにおける割当候補スロットを抽出し、エリアBにおける割当候補スロットと優先スロット番号との差分を用いて遅延累計を計算する(ステップ(47))。ここでは、第1位のスロット10に対し、エリアBにおける割当候補スロットとしてスロット15が抽出され、第2位のスロット20に対し、エリアBにおける割当候補スロットとしてスロット22が抽出され、第3位のスロット50に対し、エリアBにおける割当候補スロットとしてスロット53が抽出されたものとする。従って、第1位の候補に対する遅延累計は5(=15−10)となり、第2位の候補に対する遅延累計は2(=22−20)となり、第3位の候補に対する遅延累計は3(=53−50)となる。そして、管理サーバBは、自エリアが末端エリアではないため、エリアBにおける割当候補スロットと遅延累計とを含む割当候補リストBをエッジノードCへ送信する(ステップ(48))。また、管理サーバBは、割当候補リストBを割当候補リスト格納部1507に格納しておく。
【0083】
そして、エッジノードCは、管理サーバBからの割当候補リストBを受信すると、割当候補リストBにおける割当候補スロット毎に、当該割当候補スロットの番号とスロット差分値格納部1008に格納されているスロット差分値BCとを用いて優先スロット番号を計算し、優先スロット番号によって割当候補リストBを更新する(ステップ(49))。ここで、スロット差分値BCは2であるため、第1位のスロット15は、スロット17(=15+2)に更新され、第2位のスロット22は、スロット24(=22+2)に更新され、第3位のスロット53は、スロット55(=53+2)に更新される。そして、エッジノードCは、更新後の割当候補リストBを管理サーバCに送信する(ステップ(50))。
【0084】
そして、管理サーバCは、エッジノードCから割当候補リストBを受信すると、割当候補リストBにおける割当候補スロット毎に、当該割当候補スロットの番号(すなわち、優先スロット番号)から順に、エリアCにおける割当候補スロットを抽出し、エリアCにおける割当候補スロットと優先スロット番号との差分を用いて遅延累計を計算する(ステップ(51))。ここでは、第1位のスロット17に対し、エリアCにおける割当候補スロットとしてスロット21が抽出され、第2位のスロット24に対し、エリアCにおける割当候補スロットとしてスロット32が抽出され、第3位のスロット55に対し、エリアCにおける割当候補スロットとしてスロット57が抽出されたものとする。従って、第1位の候補に対する遅延累計は9(=5+21−17)となり、第2位の候補に対する遅延累計は10(=2+32−24)となり、第3位の候補に対する遅延累計は5(=3+57−55)となる。そして、管理サーバCは、自エリアが末端エリアであるため、遅延累計が最も少ない第3位のスロットであるスロット57を自エリアにおける割当スロットとして選択する(ステップ(52))。
【0085】
図33の説明に移行して、管理サーバCは、スロット57を割り当てるため、割当スロット番号として57を含むスロット割当指示をエリアC内のノードへ送信する(ステップ(53))。そして、管理サーバCは、自エリアにおいて割り当てたスロット57に対応する、エリアBにおける割当候補スロットを特定するためのデータとして、選択候補番号(3)をエッジノードCを介して管理サーバBに送信する(ステップ(54))。
【0086】
そして、管理サーバBは、管理サーバCからの選択候補番号を受信すると、割当候補リスト格納部1507に格納されている割当候補リストBの中から第3位のスロットであるスロット53を、自エリアにおける割当スロットとして選択する(ステップ(55))。そして、管理サーバBは、スロット53を割り当てるため、割当スロット番号として53を含むスロット割当指示をエリアB内のノードへ送信する(ステップ(56))。そして、管理サーバBは、選択候補番号をエッジノードBを介して管理サーバAに送信する(ステップ(57))。
【0087】
そして、管理サーバAは、管理サーバBからの選択候補番号を受信すると、割当候補リスト格納部1507に格納されている割当候補リストAの中から第3位のスロットであるスロット50を、自エリアにおける割当スロットとして選択する(ステップ(58))。そして、管理サーバAは、スロット50を割り当てるため、割当スロット番号として50を含むスロット割当指示をエリアA内のノードへ送信する(ステップ(59))。
【0088】
ここまでの処理で、エリアA乃至Cにおいてパケット送信に用いるスロットが割り当てられたことになる。その後、エリアAではスロット50を用いてパケット送信が行われ、エリアBではスロット53を用いてパケット送信が行われ、エリアCではスロット57を用いてパケット送信が行われる。
【0089】
次に、図34乃至図41を用いて、エッジルータ、中継ルータ及び管理サーバの処理について説明する。なお、前提として、管理サーバAは、自身のエリア管理DB1506に格納されているスロット同期のためのデータを既にエッジノードA及びBに送信しており、管理サーバBも、自身のエリア管理DB1506に格納されているスロット同期のためのデータを既にエッジノードB及びCに送信しているものとする。
【0090】
まず、エッジノードBの制御部1006が、管理サーバA及びBの各々からスロット同期のためのデータを受信する。そして、制御部1006は、複数の管理サーバからデータを受信したことで、自ノードが境界ノードであると判断し、境界ノードである旨の通知を差分計算部1007及び割当要求処理部1009に出力する。そして、エッジノードBの差分計算部1007は、制御部1006からの通知を受信すると、スロット差分計算処理を実施する(図34:ステップS111)。スロット差分計算処理については、上で説明した処理(図24又は図28)と同じであるため、ここでは詳細な説明は省略する。
【0091】
その後、エッジノードAのパケット受信部1001は、外部ネットワークからのパケットを受信すると、受信パケットをパケット分類部1002に出力する。そして、パケット分類部1002は、受信パケットをキュー1003に格納する(ステップS113)。本ステップの処理は、基本的にはステップS3の処理と同じであるため、ここでは詳細な説明は省略する。そして、パケット分類部1002が、スロットの割り当てが必要であると判断し、割当要求処理部1009に処理を行うよう指示する。そして、エッジノードAの割当要求処理部1009は、パケット分類部1002からの指示に応じて、スロット割当要求を管理サーバAに送信する(ステップS115)。なお、このスロット割当要求には、送信元エッジノード及び宛先エッジノードの識別情報などが含まれる。
【0092】
そして、管理サーバAの受信部1501は、エッジノードAからのスロット割当要求を受信すると(ステップS117)、受信したスロット割当要求をスロット割当処理部1510に出力する。そして、スロット割当処理部1510の候補リスト生成部1511は、受信したスロット割当要求と、スロット管理テーブル格納部1503とリンク情報格納部1504とに格納されているデータとを用いて割当候補リスト生成処理を実施する(ステップS119)。この割当候補リスト生成処理については図35を用いて説明する。
【0093】
まず、候補リスト生成部1511は、リンク情報格納部1504に格納されているデータを用いて、スロット割当要求に含まれる送信元エッジノードから宛先エッジノードまでの通信経路を未使用リンクによって形成可能なスロットを抽出する(図35:ステップS201)。そして、候補リスト生成部1511は、抽出したスロット毎に、所定の評価式を用いて評価値を算出する(ステップS203)。例えば、最短経路におけるホップ数が少ないほど評価値が高くなるような評価式などを用いる。なお、本処理は、本実施の形態の主要部ではないため、これ以上述べない。
【0094】
そして、候補リスト生成部1511は、抽出したスロットを評価値に従ってソートした場合の上位N位までのスロットを割当候補スロットとして選択する(ステップS205)。なお、Nの値は予め定められているものとする。そして、候補リスト生成部1511は、割当候補スロットの番号を含む割当候補リストAを生成し、割当候補リスト格納部1507に格納する(ステップS207)。その後、処理を終了し、元の処理に戻る。
【0095】
図34の説明に戻って、候補リスト生成部1511は、割当候補リスト生成処理の処理結果である割当候補リストAを、エッジノードBを介して管理サーバBへ送信するよう送信部1505に指示する。そして、送信部1505は、候補リスト生成部1511からの指示に応じて、割当候補リストAをエッジノードBに送信する(ステップS121)。この後、管理サーバAは、管理サーバBからの応答待ちとなる。なお、管理サーバAの処理は、端子Bを介して図39へ移行する。
【0096】
そして、エッジノードBの割当要求処理部1009は、管理サーバAからの割当候補リストAを受信する(ステップS123)。その後、処理は端子Cを介して図36へ移行する。
【0097】
図36の説明に移行して、端子Cの後、エッジノードBの割当要求処理部1009は、割当候補リストAに含まれる割当候補スロットの番号とスロット差分値格納部1008に格納されているスロット差分値Sij(ここでは、SAB)とを用いて優先スロット番号を計算し、優先スロット番号で割当候補リストAを更新する(図36:ステップS125)。具体的には、割当候補リストAにおける割当候補スロット毎に、当該割当候補スロットの番号をsとし、優先スロット番号=s+Sijによって算出する。そして、割当候補リストAにおける各割当候補スロットの番号を、対応する優先スロット番号によって書き換えることにより割当候補リストAを更新する。その後、エッジノードBの割当要求処理部1009は、更新後の割当候補リストAを管理サーバBに送信する(ステップS127)。
【0098】
そして、管理サーバBの受信部1501は、エッジノードBから割当候補リストAを受信すると(ステップS129)、割当候補リストAをスロット割当処理部1510に出力する。そして、スロット割当処理部1510の候補スロット抽出部1512は、割当候補リストAを受信すると、割当候補リストAと、スロット管理テーブル格納部1503とリンク情報格納部1504とに格納されているデータとを用いて割当候補計算処理を実施する(ステップS131)。この割当候補計算処理については図37を用いて説明する。
【0099】
まず、候補スロット抽出部1512は、カウンタmに1を設定する(図37:ステップS211)。そして、候補スロット抽出部1512は、第m位の候補に対応する優先スロット番号を取得する(ステップS213)。なお、上で説明したステップS125において、割当候補リストAにおける割当候補スロットの番号は、優先スロット番号で更新されているので、ここでは、割当候補リストAにおける第m位の割当候補スロットの番号を優先スロット番号として取得する。そして、候補スロット抽出部1512は、取得した優先スロット番号を、処理対象のスロット番号を表す変数xに設定する(ステップS215)。
【0100】
そして、候補スロット抽出部1512は、リンク情報格納部1504に格納されているデータを用いて、送信元エッジノードから宛先エッジノードまでの経路のうち、スロットxの未使用リンクによる最短経路を計算する(ステップS217)。例えばダイクストラ法などによって、送信元エッジノードから宛先エッジノードまでの最短経路を計算する。そして、候補スロット抽出部1512は、送信元エッジノードから宛先エッジノードまでのパケット送信に対してスロットxを割り当てることができるか否か判断する(ステップS219)。例えば、最短経路におけるホップ数が許容ホップ数以下であれば、割り当て可能と判断し、最短経路におけるホップ数が許容ホップ数を超えている場合や、未使用リンクによって送信元エッジノードから宛先エッジノードまでの経路を確保できないような場合には、割り当て不可と判断する。
【0101】
そして、スロットxを割り当てることが可能であると判断した場合(ステップS219:Yesルート)、候補スロット抽出部1512は、スロットxを自エリア(ここでは、エリアB)における、第m位の割当候補スロットとして決定する(ステップS221)。候補スロット抽出部1512は、変数xの値を、自エリアの割当候補スロット番号として、割当候補リスト格納部1507における第m位のレコードに設定する。そして、候補スロット抽出部1512は、ステップS213において取得した優先スロット番号と変数xの値との差分を計算し、当該差分を、割当候補リストAに含まれる第m位の遅延累計に加算した値を新たな遅延累計として算出する(ステップS223)。候補スロット抽出部1512は、算出した遅延累計を、割当候補リスト格納部1507における第m位のレコードに設定する。その後、ステップS233の処理に移行する。
【0102】
一方、スロットxを割り当てることはできないと判断した場合(ステップS219:Noルート)、候補スロット抽出部1512は、変数xの値を1インクリメントし(ステップS225)、変数xの値が最大スロット番号を超えたかどうか判断する(ステップS227)。変数xの値が最大スロット番号を超えている場合には(ステップS227:Yesルート)、候補スロット抽出部1512は、変数xに1を設定する(ステップS229)。一方、変数xの値が最大スロット番号を超えていなければ(ステップS227:Noルート)、ステップS231の処理に移行する。
【0103】
その後、候補スロット抽出部1512は、変数xの値がステップS213において取得した優先スロット番号と等しいかどうか判断する(ステップS231)。変数xの値が優先スロット番号と等しくない場合(ステップS231:Noルート)、ステップS217の処理に戻り、上で述べた処理を繰り返す。なお、変数xの値が優先スロット番号と等しくないということは、割り当て可能かどうか判定していないスロットがあるということを意味する。
【0104】
一方、変数xの値が優先スロット番号と等しい場合(ステップS231:Yesルート)、ステップS233の処理に移行する。なお、変数xの値が優先スロット番号と等しいと判断されるのは、優先スロット番号から順に全てのスロットについて判定したが、割り当て可能なスロットが見つからなかった場合である。従って、候補スロット抽出部1512は、割当候補リスト格納部1507における第m位のレコードに、割り当て可能なスロットがない旨を表すデータを設定しておく。
【0105】
そして、候補スロット抽出部1512は、第N位まで処理が完了したか(すなわち、m=Nであるか)判断する(ステップS233)。第N位まで処理が完了していなければ(ステップS233:Noルート)、候補スロット抽出部1512は、カウンタmを1インクリメントする(ステップS235)。その後、ステップS213の処理に戻り、上で述べた処理を繰り返す。一方、第N位まで処理が完了した場合(ステップS233:Yesルート)、処理を終了し、元の処理に戻る。
【0106】
以上のような処理を実施することによって、前のエリアの割当候補スロットに対する、自エリアの割当候補スロットを抽出することができる。また、優先スロットから順に割当候補スロットを探索することで、遅延の少ない割当候補スロットを抽出することができる。
【0107】
図36の説明に戻って、管理サーバBの候補スロット抽出部1512は、宛先エッジノード(ここでは、エッジノードC)が境界ノードであるか否かの問い合わせを宛先エッジノードに送信する(ステップS133)。
【0108】
そして、エッジノードCの制御部1006は、管理サーバBからの問い合わせを受信し(ステップS135)、問い合わせに対する応答を送信する(ステップS137)。なお、制御部1006は、スロット同期のためのデータを複数の管理サーバから受信している場合には、自ノードは境界ノードであると判断し、境界ノードである旨の応答を送信する。一方、1つの管理サーバのみから受信している場合には、自ノードは境界ノードではないと判断し、境界ノードではない旨の応答を送信する。
【0109】
そして、管理サーバBの候補スロット抽出部1512は、エッジノードCから、問い合わせに対する応答を受信する(ステップS139)。その後、処理は端子Dを介して図38に移行する。
【0110】
図38の説明に移行して、端子Dの後、管理サーバBの候補スロット抽出部1512は、エッジノードCからの応答が、境界ノードである旨の応答であったか判断する(図38:ステップS141)。エッジノードCからの応答が、境界ノードである旨の応答であった場合には(ステップS141:Yesルート)、端子Eを介して図41に移行する。なお、エッジノードCが境界ノードであるということは、エリアBは末端エリアではないため、管理サーバBは、自エリアの割当候補スロットの番号と遅延累計とを含む割当候補リストBを、次のエリアの管理サーバに送信することになる。
【0111】
一方、エッジノードCからの応答が、境界ノードではない旨の応答であった場合(ステップS141:Noルート)、候補スロット抽出部1512が、スロット選択処理部1513に処理を行うよう指示する。なお、エッジノードCが境界ノードではないということは、エリアBが末端エリアとなるため、管理サーバBが、遅延累計が最も少ない割当候補スロットを割当スロットとして選択することになる。
【0112】
管理サーバBのスロット選択処理部1513は、候補スロット抽出部1512からの指示に応じて、割当候補リスト格納部1507において遅延累計が最も少ない割当候補スロットをエリアBの割当スロットとして選択する(ステップS143)。なお、スロット選択処理部1513は、リンク情報格納部1504において、選択した割当スロットの未使用リンクによる最短経路に含まれるリンクを使用済みに設定する。また、送信元エッジノードと宛先エッジノードと割当スロットの番号と最短経路情報とを含むレコードをスロット管理テーブル格納部1503に登録する。さらに、エリア管理DB1506に格納されているデータと最短経路情報とを用いて、最短経路上の各ノードが使用するべき入出力IFを特定する。
【0113】
そして、管理サーバBのスロット選択処理部1513は、スロット割当指示を送信するよう送信部1505に指示する。この際、割当スロットの番号、最短経路情報及び入出力IFの情報を送信部1505に渡す。そして、送信部1505は、スロット選択処理部1513からの指示に応じて、割当スロット番号と入出力IF情報とを含むスロット割当指示を最短経路上の各ノードに送信する(ステップS145)。ここでは、管理サーバBの送信部1505は、エッジノードB、中継ノードB及びエッジノードCにスロット割当指示を送信する。
【0114】
そして、エッジノードB、中継ノードB及びエッジノードCは、管理サーバBからのスロット割当指示を受信する(ステップS147乃至S151)。なお、エッジノードBは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスケジュールDB1010に格納する。また、中継ノードBは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスロットテーブル格納部1302に格納する。
【0115】
その後、管理サーバBのスロット選択処理部1513は、いずれの割当候補スロットを選択したかを特定するための選択候補番号をエッジノードBを介して管理サーバAに送信する(ステップS153)。そして、エッジノードBは、管理サーバBから選択候補番号を受信する(ステップS155)。その後、処理は端子Fを介して図39に移行する。
【0116】
図39の説明に移行して、端子Fの後、エッジノードBは、選択候補番号を管理サーバAに送信する(図39:ステップS157)。そして、端子Bの後、管理サーバAのスロット選択処理部1513は、エッジノードBから選択候補番号を受信すると(ステップS159)、選択候補番号に従って、割当候補リストAの中からエリアAの割当スロットを選択する(ステップS161)。なお、スロット選択処理部1513は、リンク情報格納部1504において、選択した割当スロットの未使用リンクによる最短経路に含まれるリンクを使用済みに設定する。また、送信元エッジノードと宛先エッジノードと割当スロットの番号と最短経路情報とを含むレコードをスロット管理テーブル格納部1503に登録する。さらに、エリア管理DB1506に格納されているデータと最短経路情報とを用いて、最短経路上の各ノードが使用するべき入出力IFを特定する。
【0117】
そして、管理サーバAのスロット選択処理部1513は、スロット割当指示を送信するよう送信部1505に指示する。この際、割当スロットの番号、最短経路情報及び入出力IFの情報を送信部1505に渡す。そして、送信部1505は、スロット選択処理部1513からの指示に応じて、割当スロット番号と入出力IF情報とを含むスロット割当指示を最短経路上の各ノードに送信する(ステップS163)。ここでは、管理サーバAの送信部1505は、エッジノードA、中継ノードA及びエッジノードBにスロット割当指示を送信する。
【0118】
そして、エッジノードA、中継ノードA及びエッジノードBは、管理サーバAからのスロット割当指示を受信する(ステップS165乃至S167)。なお、エッジノードAは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスケジュールDB1010に格納する。また、中継ノードAは、受信したスロット割当指示に含まれる割当スロットの番号及び入出力IF情報をスロットテーブル格納部1302に格納する。
【0119】
なお、ここまでの処理で、エリアA及びBにおいてパケット送信に用いるスロットが割り当てられたことになる。その後、エッジノードAのスケジューラ1011は、エッジノードAからエッジノードBへのパケット送信に対して割り当てられているスロットの開始時刻になると、スケジュールDB1010のデータから特定されるキュー1003に格納されているパケットを、スケジュールDB1010のデータから特定される出力IFへ送出する(ステップS169)。そして、中継ノードAのスイッチ部1303は、スロットテーブル格納部1302に格納されているデータに従って、エッジノードAからエッジノードBへのパケットを中継する(ステップS171)。そして、エッジノードBのパケット受信部1001は、中継ノードAを介してエッジノードAからのパケットを受信すると、受信パケットをパケット分類部1002に出力する。そして、パケット分類部1002は、受信パケットをキュー1003に格納する(ステップS173)。その後、端子Gを介して図40に移行する。
【0120】
図40の説明に移行して、端子Gの後、エッジノードBのスケジューラ1011は、エッジノードBからエッジノードCへのパケット送信に対して割り当てられているスロットの開始時刻になると、スケジュールDB1010のデータから特定されるキュー1003に格納されているパケットを、スケジュールDB1010のデータから特定される出力IFへ送出する(図40:ステップS175)。そして、中継ノードBのスイッチ部1303は、スロットテーブル格納部1302に格納されているデータに従って、エッジノードBからエッジノードCへのパケットを中継する(ステップS177)。そして、エッジノードCのパケット受信部1001は、中継ノードBを介してエッジノードBからのパケットを受信する(ステップS179)。
【0121】
また、ステップS141(図38)の後、端子Eを介して図41に移行してきた場合の処理について説明する。なお、端子Eを介して図41に移行してくるのは、エリアBが末端エリアではないと判断された場合である。図41において、端子Eの後、管理サーバBの候補スロット抽出部1512は、割当候補リスト格納部1507に格納されている割当候補スロットの番号と遅延累計とを含む割当候補リストBをエッジノードCに送信する(図41:ステップS181)。この後、管理サーバBは、管理サーバCからの応答待ちとなる。
【0122】
そして、エッジノードCの割当要求処理部1009は、管理サーバBからの割当候補リストBを受信する(ステップS183)。そして、エッジノードCの割当要求処理部1009は、割当候補リストBに含まれる割当候補スロットの番号とスロット差分値格納部1008に格納されているスロット差分値Sij(ここでは、SBC)とを用いて優先スロット番号を計算し、優先スロット番号で割当候補リストBを更新する(ステップS185)。なお、本ステップの処理は、スロット差分値SBCを用いる点以外は、基本的にはステップS125と同じであるため、ここでは詳細な説明は省略する。その後、エッジノードCの割当要求処理部1009は、更新後の割当候補リストBを管理サーバCに送信する(ステップS187)。
【0123】
そして、管理サーバCの受信部1501は、エッジノードCから割当候補リストBを受信する(ステップS189)。この後、管理サーバCによって、上で説明したステップS131以降の処理が実施される。
【0124】
以上のような処理を実施することによって、各エリアで列挙された割当候補スロットに従って、全体の遅延時間が最も少なくなるようなスロットを割り当てることができるようになる。
【0125】
なお、上では、エリア間の境界にいるエッジノードが優先スロット番号を計算し、優先スロット番号によって更新した割当候補リストを管理サーバへ送信するようになっていたが、管理サーバで優先スロット番号を計算するようにしてもよい。この場合、割当候補スロットとスロット差分値とを管理サーバへ渡すようにして、ステップS213において、優先スロット番号を計算するようにすればよい。
【0126】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明したエッジルータ、中継ルータ及び管理サーバの機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。データ格納部の構成も同様に一例にすぎない。また、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしてもよい。
【0127】
なお、上で述べた管理サーバは、コンピュータ装置であって、図42に示すように、メモリ2501とCPU2503とハードディスク・ドライブ(HDD)2505と表示装置2509に接続される表示制御部2507とリムーバブル・ディスク2511用のドライブ装置2513と入力装置2515とネットワークに接続するための通信制御部2517とがバス2519で接続されている。オペレーティング・システム(OS:Operating System)及び本実施例における処理を実施するためのアプリケーション・プログラムは、HDD2505に格納されており、CPU2503により実行される際にはHDD2505からメモリ2501に読み出される。必要に応じてCPU2503は、表示制御部2507、通信制御部2517、ドライブ装置2513を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ2501に格納され、必要があればHDD2505に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク2511に格納されて頒布され、ドライブ装置2513からHDD2505にインストールされる。インターネットなどのネットワーク及び通信制御部2517を経由して、HDD2505にインストールされる場合もある。このようなコンピュータ装置は、上で述べたCPU2503、メモリ2501などのハードウエアとOS及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【0128】
また、上で述べたエッジルータ及び中継ルータは、図43に示すように、メモリ2601とCPU2603とハードディスク・ドライブ(HDD)2605と表示装置2609に接続される表示制御部2607とリムーバブル・ディスク2611用のドライブ装置2613と入力装置2615とネットワークに接続するための通信部2617(図43では、2617a乃至2617c)とがバス2619で接続されている。なお、場合によっては、表示制御部2607、表示装置2609、ドライブ装置2613、入力装置2615は含まれない場合もある。オペレーティング・システム(OS:Operating System)及び本実施例における処理を実施するためのアプリケーション・プログラムは、HDD2605に格納されており、CPU2603により実行される際にはHDD2605からメモリ2601に読み出される。必要に応じてCPU2603は、表示制御部2607、通信部2617、ドライブ装置2613を制御して、必要な動作を行わせる。なお、通信部2617のいずれかを介して入力されたデータは、他の通信部2617を介して出力される。CPU2603は、通信部2617を制御して、適切に出力先を切り替える。また、処理途中のデータについては、メモリ2601に格納され、必要があればHDD2605に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク2611に格納されて頒布され、ドライブ装置2613からHDD2605にインストールされる。インターネットなどのネットワーク及び通信部2617を経由して、HDD2605にインストールされる場合もある。このようなコンピュータ装置は、上で述べたCPU2603、メモリ2601などのハードウエアとOS及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【0129】
本実施の形態の第1の態様に係る管理装置(図44)は、(a)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと、隣接エリアにおいて特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に自エリアにおいて特定のパケットの送信に対して割り当て可能なスロットを探索することにより、自エリアにおいて特定のパケットの送信に対して割り当てる割当スロットを決定するスロット決定部(図44:3501)と、(b)決定された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ特定のパケットの送信の経路上のノードに送信する送信部(図44:3503)とを有する。
【0130】
このようにすれば、エリア間のスロットのずれと隣接エリアで使用されているスロットとを考慮した形で、自エリアで使用するスロットを決定することができる。すなわち、遅延が少なくなるようなスロットを決定し、割り当てることができるようになる。
【0131】
また、上で述べたスロット決定部が、未使用リンクによって形成される最短経路におけるホップ数が所定の許容ホップ数以下となるスロットを割り当て可能なスロットとして探索するようにしてもよい。このようにすれば、例えば遠回りするような経路を割り当てることがなくなる。
【0132】
さらに、上で述べたスロット決定部が、最初に検出された割り当て可能なスロットを上記割当スロットとして決定するようにしてもよい。このようにすれば、遅延が最も少なくなるようなスロットを割り当てることができる。
【0133】
また、上で述べたスロット決定部が、優先スロットから任意の時間以上離れている割り当て可能なスロットのうち、優先スロットに最も近いスロットを上記割当スロットとして決定するようにしてもよい。このようにすれば、ある程度の間隔を空けつつ、優先スロットの近傍のスロットを割り当てることができるようになる。このように間隔を空けることで、空けた部分のスロットについては、別のパケット送信に割り当てることができる。
【0134】
本実施の形態の第2の態様に係るエッジルータ(図45)は、(a)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算する差分計算部(図45:3601)と、(b)送信元側のエリア内のノードから送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信する受信部(図45:3603)と、(c)受信したパケットを宛先側のエリア内のノードへ送出するための、宛先側のエリアにおけるスロットが割り当てられていない場合、第1のスロットの番号及びスロット差分値、又は第1のスロットの番号とスロット差分値とから特定される優先スロット番号を含むスロット割当要求を、宛先側のエリアにおけるスロットを管理する管理装置に送信する割当要求処理部(図45:3605)と、(d)管理装置から割り当てられる第2のスロットを用いてパケットを宛先側のエリア内のノードへ送出するスケジューラ(図45:3607)とを有する。
【0135】
このように、スロット差分値と送信元側のエリアで使用されているスロットとを含むスロット割当要求を管理装置に送信することで、管理装置において、遅延が少なくなるようなスロットを割り当てることが可能になる。
【0136】
また、上で述べた差分計算部が、送信元側のエリアにおいて特定の時刻におけるスロットの番号を第1の番号として取得すると共に、宛先側のエリアにおいて特定の時刻におけるスロットの番号を第2の番号として取得し、第1の番号と第2の番号との差分をスロット差分値として計算するようにしてもよい。このようにすれば、スロット差分値を計算することができる。
【0137】
さらに、上で述べた差分計算部が、送信元側のエリアにおいて特定のスロット番号を含む制御パケットを受信した時点の時刻を第1の時刻として取得すると共に、宛先側のエリアにおいて特定のスロット番号を含む制御パケットを受信した時点の時刻を第2の時刻として取得し、第1の時刻と第2の時刻との時間差からスロット差分値を計算するようにしてもよい。このようにすれば、ネットワーク上を流れている制御パケットからスロット差分値を計算することができる。
【0138】
本実施の形態の第3の態様に係る管理装置(図46)は、(a)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける自エリア及び第1の隣接エリアを通過する第1のパケットについてのスロット割当要求を受信した場合、自エリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、第1の候補スロットの番号を含む第1の候補リストを生成し、第1の隣接エリアにおける管理装置に通知する候補リスト生成部(図46:3701)と、(b)第2の隣接エリア及び自エリアを通過する第2のパケットの送信に対して第2の隣接エリアで割り当て可能なスロットである第2の候補スロットを含む第2の候補リストを受信した場合、当該第2の候補リストに含まれる第2の候補スロット毎に、第2の隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に自エリアにおいて第2のパケットの送信に対して割り当て可能なスロットを探索することにより自エリアにおける第3の候補スロットを特定し、当該優先スロットの番号と第3の候補スロットの番号との差分を遅延時間として計算する候補スロット抽出部(図46:3703)と、(c)自エリアが第2のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、遅延時間が最も小さい第3の候補スロットを割当スロットとして選択するスロット選択処理部(図46:3705)と、(d)スロット選択処理部により選択された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ第2のパケットの通信経路上のノードに送信すると共に、割当スロットとして選択された第3の候補スロットに対応する第2の候補スロットを特定するためのデータを第2の隣接エリアにおける管理装置に通知する送信部(図46:3707)とを有する。
【0139】
本実施の形態の第4の態様に係るスロット割当方法は、パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、(a)隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、隣接エリアと自エリアとのエリア間のスロットのずれを表すデータと、隣接エリアにおいて特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に自エリアにおいて特定のパケットの送信に対して割り当て可能なスロットを探索することにより、自エリアにおいて特定のパケットの送信に対して割り当てる割当スロットを決定するステップ(図47:S3001)と、(b)決定された割当スロットの番号を含むスロット割当指示を自エリアに属し且つ特定のパケットの通信経路上のノードに送信するステップ(図47:S3003)とを含む。
【0140】
本実施の形態の第5の態様に係る中継処理方法は、(a)パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算するステップ(図48:S3101)と、(b)送信元側のエリア内のノードから送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信するステップ(図48:S3103)と、(c)受信したパケットを宛先側のエリア内のノードへ送出するための、宛先側のエリアにおけるスロットが割り当てられていない場合、第1のスロットの番号及びスロット差分値、又は第1のスロットの番号とスロット差分値とから特定される優先スロット番号を含むスロット割当要求を、宛先側のエリアにおけるスロットを管理する管理装置に送信するステップ(図48:S3105)と、(d)管理装置から割り当てられる第2のスロットを用いてパケットを宛先側のエリア内のノードへ送出するステップ(図48:S3107)とを含む。
【0141】
本実施の形態の第6の態様に係るスロット割当方法は、パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、(a)第1のエリア及び第2のエリアを通過する特定のパケットについてのスロット割当要求を受信した場合、第1のエリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、第1の候補スロットの番号を含む第1の候補リストを生成し、第2のエリアにおける管理装置に通知するステップ(図49:S3201)と、(b)第1のエリアにおける管理装置からの第1の候補リストを受信した場合、当該第1の候補リストに含まれる第1の候補スロット毎に、第1のエリアと第2のエリアとのエリア間のスロットのずれを表すデータと当該第1の候補スロットの番号とから特定される優先スロットから順に第2のエリアにおいて特定のパケットの送信に対して割り当て可能なスロットを探索することにより第2のエリアにおける第2の候補スロットを特定し、当該優先スロットの番号と第2の候補スロットの番号との差分を遅延時間として計算するステップ(図49:S3203)と、(c)第2のエリアが特定のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には(図49のS3205:Yes)、遅延時間が最も小さい第2の候補スロットを第2のエリアの割当スロットとして選択するステップ(図49:S3207)と、(d)第2のエリアの割当スロットの番号を含むスロット割当指示を第2のエリアに属し且つ特定のパケットの通信経路上のノードに送信すると共に、第2のエリアの割当スロットとして選択された第2の候補スロットに対応する第1の候補スロットを特定するためのデータを第1のエリアにおける管理装置に通知するステップ(図49:S3209)とを含む。
【0142】
このようにすれば、第1のエリア及び第2のエリアを通過する際の全体の遅延時間が少なくなるようなスロットを割り当てることができるようになる。
【0143】
第6の態様において、第2のエリアにおける管理装置から第1の候補スロットを特定するためのデータを受信した場合には、当該第1の候補スロットを特定するためのデータを用いて、第1の候補リストの中から第1のエリアの割当スロットを選択するステップと、第1のエリアの割当スロットの番号を含むスロット割当指示を第1のエリアに属し且つ特定のパケットの通信経路上のノードに送信するステップとをさらに含むようにしてもよい。
【0144】
第6の態様において、第2のエリアが末端エリアでなければ、第2の候補スロットの番号と遅延時間とを含む第2の候補リストを生成し、第2のエリアの次のエリアである第3のエリアにおける管理装置に通知するステップと、第2のエリアにおける管理装置からの第2の候補リストを受信した場合、当該第2の候補リストに含まれる第2の候補スロット毎に、第2のエリアと第3のエリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に第3のエリアにおいて割り当て可能なスロットを探索することにより第3のエリアにおける第3の候補スロットを特定し、当該優先スロットの番号と第3の候補スロットの番号との差分を、第2候補リストに含まれる遅延時間に加算するステップと、第3のエリアが末端エリアである場合には、遅延時間が最も小さい第3の候補スロットを第3のエリアの割当スロットとして選択するステップと、第3のエリアの割当スロットの番号を含むスロット割当指示を第3のエリアに属し且つ特定のパケットの通信経路上のノードに送信すると共に、第3のエリアの割当スロットとして選択された第3の候補スロットに対応する第2の候補スロットを特定するためのデータを第2のエリアにおける管理装置に通知するステップと、第3のエリアにおける管理装置から第2の候補スロットを特定するためのデータを受信した場合には、当該第2の候補スロットを特定するためのデータを用いて、第2の候補リストの中から第2のエリアの割当スロットを選択するステップと、第2のエリアの割当スロットの番号を含むスロット割当指示を第2のエリアに属し且つ特定のパケットの通信経路上のノードに送信すると共に、第2のエリアの割当スロットとして選択された第2の候補スロットに対応する第1の候補スロットを特定するためのデータを第1のエリアにおける管理装置に通知するステップと、第2のエリアにおける管理装置から第1の候補スロットを特定するためのデータを受信した場合には、当該第1の候補スロットを特定するためのデータを用いて、第1の候補リストの中から第1のエリアの割当スロットを選択するステップと、第1のエリアの割当スロットの番号を含むスロット割当指示を第1のエリアに属し且つ特定のパケットの通信経路上のノードに送信するステップとをさらに含むようにしてもよい。このようにすれば、3つのエリアを通過するようなパケットについても、全体の遅延時間が少なくなるようなスロットを各エリアで割り当てることができるようになる。
【0145】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、CD−ROM、光磁気ディスク、半導体メモリ(例えばROM)、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、RAM等の記憶装置に一時保管される。
【0146】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【0147】
(付記1)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと、前記隣接エリアにおいて前記特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより、前記自エリアにおいて前記特定のパケットの送信に対して割り当てる割当スロットを決定するスロット決定部と、
決定された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記特定のパケットの通信経路上のノードに送信する送信部と、
を有する管理装置。
【0148】
(付記2)
前記スロット決定部が、
未使用リンクによって形成される最短経路におけるホップ数が所定の許容ホップ数以下となるスロットを前記割り当て可能なスロットとして探索する
付記1記載の管理装置。
【0149】
(付記3)
前記スロット決定部が、
最初に検出された前記割り当て可能なスロットを前記割当スロットとして決定する
付記1又は2記載の管理装置。
【0150】
(付記4)
前記スロット決定部が、
前記優先スロットから任意の時間以上離れている前記割り当て可能なスロットのうち、前記優先スロットに最も近いスロットを前記割当スロットとして決定する
付記1又は2記載の管理装置。
【0151】
(付記5)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算する差分計算部と、
前記送信元側のエリア内のノードから前記送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信する受信部と、
受信した前記パケットを前記宛先側のエリア内のノードへ送出するための、前記宛先側のエリアにおけるスロットが割り当てられていない場合、前記第1のスロットの番号及び前記スロット差分値、又は前記第1のスロットの番号と前記スロット差分値とから特定される優先スロット番号を含むスロット割当要求を、前記宛先側のエリアにおけるスロットを管理する管理装置に送信する割当要求処理部と、
前記管理装置から割り当てられる第2のスロットを用いて前記パケットを前記宛先側のエリア内のノードへ送出するスケジューラと、
を有するエッジルータ。
【0152】
(付記6)
前記差分計算部が、
前記送信元側のエリアにおいて特定の時刻におけるスロットの番号を第1の番号として取得すると共に、前記宛先側のエリアにおいて前記特定の時刻におけるスロットの番号を第2の番号として取得し、前記第1の番号と前記第2の番号との差分を前記スロット差分値として計算する
付記5記載のエッジルータ。
【0153】
(付記7)
前記差分計算部が、
前記送信元側のエリアにおいて特定のスロット番号を含む制御パケットを受信した時点の時刻を第1の時刻として取得すると共に、前記宛先側のエリアにおいて前記特定のスロット番号を含む制御パケットを受信した時点の時刻を第2の時刻として取得し、前記第1の時刻と前記第2の時刻との時間差から前記スロット差分値を計算する
付記5記載のエッジルータ。
【0154】
(付記8)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける自エリア及び第1の隣接エリアを通過する第1のパケットについてのスロット割当要求を受信した場合、前記自エリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、前記第1の候補スロットの番号を含む第1の候補リストを生成し、前記第1の隣接エリアにおける管理装置に通知する候補リスト生成部と、
第2の隣接エリア及び前記自エリアを通過する第2のパケットの送信に対して前記第2の隣接エリアで割り当て可能なスロットである第2の候補スロットを含む第2の候補リストを受信した場合、当該第2の候補リストに含まれる前記第2の候補スロット毎に、前記第2の隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記第2のパケットの送信に対して割り当て可能なスロットを探索することにより前記自エリアにおける第3の候補スロットを特定し、当該優先スロットの番号と前記第3の候補スロットの番号との差分を遅延時間として計算する候補スロット抽出部と、
前記自エリアが前記第2のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、前記遅延時間が最も小さい前記第3の候補スロットを割当スロットとして選択するスロット選択処理部と、
前記スロット選択処理部により選択された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記第2のパケットの通信経路上のノードに送信すると共に、前記割当スロットとして選択された前記第3の候補スロットに対応する前記第2の候補スロットを特定するためのデータを前記第2の隣接エリアにおける管理装置に通知する送信部と、
を有する管理装置。
【0155】
(付記9)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、
隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと、前記隣接エリアにおいて前記特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより、前記自エリアにおいて前記特定のパケットの送信に対して割り当てる割当スロットを決定するステップと、
決定された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記特定のパケットの通信経路上のノードに送信するステップと、
を含む、スロット割当方法。
【0156】
(付記10)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算するステップと、
前記送信元側のエリア内のノードから前記送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信するステップと、
受信した前記パケットを前記宛先側のエリア内のノードへ送出するための、前記宛先側のエリアにおけるスロットが割り当てられていない場合、前記第1のスロットの番号及び前記スロット差分値、又は前記第1のスロットの番号と前記スロット差分値とから特定される優先スロット番号を含むスロット割当要求を、前記宛先側のエリアにおけるスロットを管理する管理装置に送信するステップと、
前記管理装置から割り当てられる第2のスロットを用いて前記パケットを前記宛先側のエリア内のノードへ送出するステップと、
を含み、エッジルータにより実行される中継処理方法。
【0157】
(付記11)
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、
第1のエリア及び第2のエリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記第1のエリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、前記第1の候補スロットの番号を含む第1の候補リストを生成し、前記第2のエリアにおける管理装置に通知するステップと、
前記第1のエリアにおける管理装置からの前記第1の候補リストを受信した場合、当該第1の候補リストに含まれる前記第1の候補スロット毎に、前記第1のエリアと前記第2のエリアとのエリア間のスロットのずれを表すデータと当該第1の候補スロットの番号とから特定される優先スロットから順に前記第2のエリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより前記第2のエリアにおける第2の候補スロットを特定し、当該優先スロットの番号と前記第2の候補スロットの番号との差分を遅延時間として計算するステップと、
前記第2のエリアが前記特定のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、前記遅延時間が最も小さい前記第2の候補スロットを前記第2のエリアの割当スロットとして選択するステップと、
前記第2のエリアの割当スロットの番号を含むスロット割当指示を前記第2のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信すると共に、前記第2のエリアの割当スロットとして選択された前記第2の候補スロットに対応する前記第1の候補スロットを特定するためのデータを前記第1のエリアにおける管理装置に通知するステップと、
を含む、スロット割当方法。
【0158】
(付記12)
前記第2のエリアにおける管理装置から前記第1の候補スロットを特定するためのデータを受信した場合には、当該第1の候補スロットを特定するためのデータを用いて、前記第1の候補リストの中から前記第1のエリアの割当スロットを選択するステップと、
前記第1のエリアの割当スロットの番号を含むスロット割当指示を前記第1のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信するステップと、
をさらに含む、付記11記載のスロット割当方法。
【0159】
(付記13)
前記第2のエリアが前記末端エリアでなければ、前記第2の候補スロットの番号と前記遅延時間とを含む第2の候補リストを生成し、前記第2のエリアの次のエリアである第3のエリアにおける管理装置に通知するステップと、
前記第2のエリアにおける管理装置からの前記第2の候補リストを受信した場合、当該第2の候補リストに含まれる前記第2の候補スロット毎に、前記第2のエリアと前記第3のエリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に前記第3のエリアにおいて割り当て可能なスロットを探索することにより前記第3のエリアにおける第3の候補スロットを特定し、当該優先スロットの番号と前記第3の候補スロットの番号との差分を、前記第2候補リストに含まれる前記遅延時間に加算するステップと、
前記第3のエリアが前記末端エリアである場合には、前記遅延時間が最も小さい前記第3の候補スロットを前記第3のエリアの割当スロットとして選択するステップと、
前記第3のエリアの割当スロットの番号を含むスロット割当指示を前記第3のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信すると共に、前記第3のエリアの割当スロットとして選択された前記第3の候補スロットに対応する前記第2の候補スロットを特定するためのデータを前記第2のエリアにおける管理装置に通知するステップと、
前記第3のエリアにおける管理装置から前記第2の候補スロットを特定するためのデータを受信した場合には、当該第2の候補スロットを特定するためのデータを用いて、前記第2の候補リストの中から前記第2のエリアの割当スロットを選択するステップと、
前記第2のエリアの割当スロットの番号を含むスロット割当指示を前記第2のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信すると共に、前記第2のエリアの割当スロットとして選択された前記第2の候補スロットに対応する前記第1の候補スロットを特定するためのデータを前記第1のエリアにおける管理装置に通知するステップと、
前記第2のエリアにおける管理装置から前記第1の候補スロットを特定するためのデータを受信した場合には、当該第1の候補スロットを特定するためのデータを用いて、前記第1の候補リストの中から前記第1のエリアの割当スロットを選択するステップと、
前記第1のエリアの割当スロットの番号を含むスロット割当指示を前記第1のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信するステップと、
をさらに含む、付記11記載のスロット割当方法。
【符号の説明】
【0160】
101,102,103,104,105,106,107,108 エッジルータ
131,132,133,134,135,136 中継ルータ
151,152,153 管理サーバ
1001 パケット受信部 1002 パケット分類部
1003 キュー 1004 エッジノードテーブル格納部
1005 キュー管理テーブル格納部 1006 制御部
1007 差分計算部 1008 スロット差分値格納部
1009 割当要求処理部 1010 スケジュールDB
1011 スケジューラ
1301 スロットテーブル管理部 1302 スロットテーブル格納部
1303 スイッチ部
1501 受信部 1502 スロット割当処理部
1503 スロット管理テーブル格納部 1504 リンク情報格納部
1505 送信部 1506 エリア管理DB
1507 割当候補リスト格納部 1510 スロット割当処理部
1511 候補リスト生成部 1512 候補スロット抽出部
1513 スロット選択処理部

【特許請求の範囲】
【請求項1】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと、前記隣接エリアにおいて前記特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより、前記自エリアにおいて前記特定のパケットの送信に対して割り当てる割当スロットを決定するスロット決定部と、
決定された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記特定のパケットの通信経路上のノードに送信する送信部と、
を有する管理装置。
【請求項2】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算する差分計算部と、
前記送信元側のエリア内のノードから前記送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信する受信部と、
受信した前記パケットを前記宛先側のエリア内のノードへ送出するための、前記宛先側のエリアにおけるスロットが割り当てられていない場合、前記第1のスロットの番号及び前記スロット差分値、又は前記第1のスロットの番号と前記スロット差分値とから特定される優先スロット番号を含むスロット割当要求を、前記宛先側のエリアにおけるスロットを管理する管理装置に送信する割当要求処理部と、
前記管理装置から割り当てられる第2のスロットを用いて前記パケットを前記宛先側のエリア内のノードへ送出するスケジューラと、
を有するエッジルータ。
【請求項3】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおける自エリア及び第1の隣接エリアを通過する第1のパケットについてのスロット割当要求を受信した場合、前記自エリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、前記第1の候補スロットの番号を含む第1の候補リストを生成し、前記第1の隣接エリアにおける管理装置に通知する候補リスト生成部と、
第2の隣接エリア及び前記自エリアを通過する第2のパケットの送信に対して前記第2の隣接エリアで割り当て可能なスロットである第2の候補スロットを含む第2の候補リストを受信した場合、当該第2の候補リストに含まれる前記第2の候補スロット毎に、前記第2の隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと当該第2の候補スロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記第2のパケットの送信に対して割り当て可能なスロットを探索することにより前記自エリアにおける第3の候補スロットを特定し、当該優先スロットの番号と前記第3の候補スロットの番号との差分を遅延時間として計算する候補スロット抽出部と、
前記自エリアが前記第2のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、前記遅延時間が最も小さい前記第3の候補スロットを割当スロットとして選択するスロット選択処理部と、
前記スロット選択処理部により選択された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記第2のパケットの通信経路上のノードに送信すると共に、前記割当スロットとして選択された前記第3の候補スロットに対応する前記第2の候補スロットを特定するためのデータを前記第2の隣接エリアにおける管理装置に通知する送信部と、
を有する管理装置。
【請求項4】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、
隣接エリア及び自エリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記隣接エリアと前記自エリアとのエリア間のスロットのずれを表すデータと、前記隣接エリアにおいて前記特定のパケットの送信に対して割り当てられているスロットの番号とから特定される優先スロットから順に前記自エリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより、前記自エリアにおいて前記特定のパケットの送信に対して割り当てる割当スロットを決定するステップと、
決定された前記割当スロットの番号を含むスロット割当指示を前記自エリアに属し且つ前記特定のパケットの通信経路上のノードに送信するステップと、
を含む、スロット割当方法。
【請求項5】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいて送信元側のエリアと宛先側のエリアとのエリア間のスロットのずれを表すスロット差分値を計算するステップと、
前記送信元側のエリア内のノードから前記送信元側のエリアにおける第1のスロットを用いて送信されるパケットを受信するステップと、
受信した前記パケットを前記宛先側のエリア内のノードへ送出するための、前記宛先側のエリアにおけるスロットが割り当てられていない場合、前記第1のスロットの番号及び前記スロット差分値、又は前記第1のスロットの番号と前記スロット差分値とから特定される優先スロット番号を含むスロット割当要求を、前記宛先側のエリアにおけるスロットを管理する管理装置に送信するステップと、
前記管理装置から割り当てられる第2のスロットを用いて前記パケットを前記宛先側のエリア内のノードへ送出するステップと、
を含み、エッジルータにより実行される中継処理方法。
【請求項6】
パケット送信に用いられる期間であるスロットがエリア毎に管理されるネットワークにおいてスロットを管理する管理装置によって実行されるスロット割当方法であって、
第1のエリア及び第2のエリアを通過する特定のパケットについてのスロット割当要求を受信した場合、前記第1のエリアにおいて割り当て可能なスロットの中から第1の候補スロットを所定数分抽出し、前記第1の候補スロットの番号を含む第1の候補リストを生成し、前記第2のエリアにおける管理装置に通知するステップと、
前記第1のエリアにおける管理装置からの前記第1の候補リストを受信した場合、当該第1の候補リストに含まれる前記第1の候補スロット毎に、前記第1のエリアと前記第2のエリアとのエリア間のスロットのずれを表すデータと当該第1の候補スロットの番号とから特定される優先スロットから順に前記第2のエリアにおいて前記特定のパケットの送信に対して割り当て可能なスロットを探索することにより前記第2のエリアにおける第2の候補スロットを特定し、当該優先スロットの番号と前記第2の候補スロットの番号との差分を遅延時間として計算するステップと、
前記第2のエリアが前記特定のパケットを外部ネットワークへ出力するエッジノードを含む末端エリアである場合には、前記遅延時間が最も小さい前記第2の候補スロットを前記第2のエリアの割当スロットとして選択するステップと、
前記第2のエリアの割当スロットの番号を含むスロット割当指示を前記第2のエリアに属し且つ前記特定のパケットの通信経路上のノードに送信すると共に、前記第2のエリアの割当スロットとして選択された前記第2の候補スロットに対応する前記第1の候補スロットを特定するためのデータを前記第1のエリアにおける管理装置に通知するステップと、
を含む、スロット割当方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate

【図44】
image rotate

【図45】
image rotate

【図46】
image rotate

【図47】
image rotate

【図48】
image rotate

【図49】
image rotate


【公開番号】特開2012−9992(P2012−9992A)
【公開日】平成24年1月12日(2012.1.12)
【国際特許分類】
【出願番号】特願2010−142420(P2010−142420)
【出願日】平成22年6月23日(2010.6.23)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】