(57)【要約】  データ中継装置１０は、自装置よりデータ中継装置９０までに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを予め合計コスト記憶部８１で記憶する。データ中継装置９０との間に所定帯域のパスを確立した場合には、合計コストに基づいて経路を選択し、当該選択した経路にデータを振り分けて送信する。この経路の選択について、データ中継装置１０は、各々の経路の合計コスト差が所定値以内の経路同士となるようなグループを編成し、編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する。所定値の値がデータ中継装置９０に設定されたデフディレイ許容値と同値であれば、デフディレイアラームを発生させることなくデータ中継装置１０とデータ中継装置９０との間にパスを確立することが可能となる。
2009063550.tif 000002
【特許請求の範囲】
【請求項１】
自装置より所定の終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを記憶し、ネットワークにおいて自装置が始点ノードとなり、前記終点ノードへ所定帯域のパスを確立する場合には、前記合計コストを参照しつつ、前記所定帯域の確保に必要な数の経路を束ねて仮想的に一つのパスを確立するデータ中継装置であって、
各々の経路の合計コスト差が予め当該データ中継装置に設定された所定値以内の経路同士となるようなグループを編成するグループ編成手段と、
前記終点ノードへパスを確立する要求に対し、前記グループ編成手段によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する経路選択手段と、
を備えたことを特徴とするデータ中継装置。
【請求項２】
前記グループ編成手段は、当該データ中継装置に対して前記終点ノードへのパスの確立が要求される前の所定のタイミングでグループを編成し、
前記グループ編成手段によって編成されたグループと、当該グループに含まれる経路の数とを対応付けて記憶するグループ内経路数記憶手段をさらに備え、
前記経路選択手段は、前記終点ノードへパスを確立する要求に対し、前記グループ内経路数記憶手段を参照して当該パスの帯域に必要な経路数以上の経路を含むグループから経路を選択することを特徴とする請求項１に記載のデータ中継装置。
【請求項３】
前記終点ノードへ所定帯域のパスを確立する要求を受け付けた際に、当該パスの帯域の確保に必要とする経路数を算出する経路数算出手段と、
使用可能な全経路を合計コストの小さい順にソートし、ソートしたテーブル内で連続する前記経路数の経路群であって、当該経路群に含まれる最大コストと最小コストとの差が所定値以内となる経路群を、前記テーブルの合計コストの最小値側から探索する経路群探索手段と、
をさらに備え、
前記グループ編成手段は、前記経路群探索手段による探索の結果得られた経路群をグループとして編成することを特徴とする請求項１に記載のデータ中継装置。
【請求項４】
ネットワークにおいて始点ノードより終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを参照しつつ、所定帯域のパスの確立に必要な数の経路を選択し、当該選択した経路を束ねて仮想的に一つのパスを確立する場合の経路選択方法であって、
各々の経路の合計コスト差が所定値以内の経路同士となるようなグループを編成するグループ編成工程と、
前記終点ノードへパスを確立する要求に対し、前記グループ編成工程によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する経路選択工程と、
を含んだことを特徴とする経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ネットワークにおいて始点ノードより終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを参照しつつ、所定帯域のパスの確立に必要な数の経路を選択し、当該選択した経路を束ねて仮想的に一つのパスを確立するデータ中継装置および経路選択方法に関する。
【背景技術】
【０００２】
従来、ＩＰ（Internet  Protocol）ネットワークにおけるデータの転送に関する技術が考案されてきたが（例えば特許文献１）、ＭＰＬＳ（Multi-Protocol  Label  Switching）の登場により、所定の始点ノードから終点ノードまで高速にデータを転送可能なパスが提供されるようになった。【０００３】
さらに、近年、このＭＰＬＳを一般化したＧＭＰＬＳ（Generalized  Multi-Protocol  Label  Switching）が登場し、パスを提供することができる範囲がＩＰネットワークだけでなく、ＳＯＮＥＴ／ＳＤＨ（Synchronous  Optical  Network/Synchronous  Digital  Hierarchy）網まで拡大された。【０００４】
そして、当該ＳＯＮＥＴ／ＳＤＨ網に提供されるパスの帯域を制御する技術であるＶＣＡＴ（Virtual  Concatenation）が注目されている。ＶＣＡＴが注目される理由について説明すると、従来、ＳＯＮＥＴ／ＳＤＨ網に提供されるパスの帯域については、１５０Ｍｂｐｓ、６００Ｍｂｐｓ、２．４Ｇｂｐｓ、１０Ｇｂｐｓと、４倍ごとの値に縛られていた。これに対し、ＶＣＡＴでは、５０Ｍｂｐｓ、１００Ｍｂｐｓ、１５０Ｍｂｐｓと、５０Ｍｂｐｓの任意の倍数の値で、より細かくパスの帯域の設定を行うことができるようになった。以上が、ＶＣＡＴが注目される理由である。【０００５】
ここで、ＶＣＡＴに基づいてＳＯＮＥＴ／ＳＤＨ網にパスを確立する手法について具体的に説明する。【０００６】
まず、管理装置は、オペレータの指示によって、ＳＯＮＥＴ／ＳＤＨ網において始点ノードであるデータ中継装置に対し、所定の終点ノードまでに例えば２００Ｍｂｐｓの帯域のパスを確立するように要求する。【０００７】
データ中継装置は、上記した要求を管理装置から受け付けると、自装置より終点ノードまでに至るための経路（多くの場合、他のノードを経由した経路である）を探索し、その結果、複数通りの経路を求める。データ中継装置は、ＶＣＡＴに基づいて、求めた経路の一つ一つに対して５０Ｍｂｐｓの帯域を確保し、複数の経路を仮想的に束ねることでより細かなパスの帯域を設定する。つまり、データ中継装置は、２００Ｍｂｐｓの帯域のパスを確立する要求に対し、求めた複数通りの経路から４つの経路の選択を必要とする。【０００８】
そこで、データ中継装置は、コストと呼ばれる数値に基づいて、求めた複数通りの経路から４つの経路を選択する。コストとは、ＧＭＬＰＳで定義されている数値であり、リンク（ネットワーク内におけるノードとノードの区間）に対して所定の算出手法により決定される。【０００９】
データ中継装置は、経路を探索するとともに、当該経路に含まれるリンクのコストを算出し、さらに、これらのコストを合計した合計コストを経路ごとにそれぞれ算出する。そして、データ中継装置は、当該合計コストが低い順に経路を４つ選択し、当該選択した４つの経路を束ねることで帯域が２００Ｍｂｐｓである仮想的なパスを確立する。【００１０】
上記のように確立されたパスには、帯域が２００Ｍｂｐｓまでのデータが送信されるが、束ねられた４つの経路それぞれにおいて、データが始点ノードから送信されてから終点ノードに受信されるまでの時間が異なる。そのため、終点ノードには、データの伝送遅延差を吸収する機能が備えられている。また、終点ノードには、ＧＭＬＰＳで定義されたコストと同等な数値であるデフディレイ許容値が設定されており、経路間の合計コストの差については当該デフディレイ許容値以内であることが望まれる。【００１１】
【特許文献１】特開平９−１９１３２２
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上述したように、データ中継装置は、複数通りの経路から必要数分の経路を選択するが、その選択の判断基準となるものは、合計コストの絶対値の低さであり、合計コスト間の相対値の低さについては判断基準外となっている。【００１３】
このような判断基準で選択された経路間の合計コストの差は、時として大きな値となることがあった。【００１４】
そして、経路間の合計コストの差が終点ノードに設定されたデフディレイ許容値を越えてしまうと、ＳＯＮＥＴ／ＳＤＨ網においてデフディレイアラームが発生し、信号が復元できないという課題があった。【００１５】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、デフディレイアラームの発生をなくすことが可能なデータ中継装置および経路選択方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上述した課題を解決し、目的を達成するため、本発明は、自装置より所定の終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを記憶し、ネットワークにおいて自装置が始点ノードとなり、前記終点ノードへ所定帯域のパスを確立する場合には、前記合計コストを参照しつつ、前記所定帯域の確保に必要な数の経路を束ねて仮想的に一つのパスを確立するデータ中継装置であって、各々の経路の合計コスト差が予め当該データ中継装置に設定された所定値以内の経路同士となるようなグループを編成するグループ編成手段と、前記終点ノードへパスを確立する要求に対し、前記グループ編成手段によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する経路選択手段と、を備えたことを特徴とする。【００１７】
また、本発明は、上記の発明において、前記グループ編成手段は、当該データ中継装置に対して前記終点ノードへのパスの確立が要求される前の所定のタイミングでグループを編成し、前記グループ編成手段によって編成されたグループと、当該グループに含まれる経路の数とを対応付けて記憶するグループ内経路数記憶手段をさらに備え、前記経路選択手段は、前記終点ノードへパスを確立する要求に対し、前記グループ内経路数記憶手段を参照して当該パスの帯域に必要な経路数以上の経路を含むグループから経路を選択することを特徴とする。【００１８】
また、本発明は、上記の発明において、前記終点ノードへ所定帯域のパスを確立する要求を受け付けた際に、当該パスの帯域の確保に必要とする経路数を算出する経路数算出手段と、使用可能な全経路を合計コストの小さい順にソートし、ソートしたテーブル内で連続する前記経路数の経路群であって、当該経路群に含まれる最大コストと最小コストとの差が所定値以内となる経路群を、前記テーブルの合計コストの最小値側から探索する経路群探索手段と、をさらに備え、前記グループ編成手段は、前記経路群探索手段による探索の結果得られた経路群をグループとして編成することを特徴とする。【００１９】
また、本発明は、ネットワークにおいて始点ノードより終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを参照しつつ、所定帯域のパスの確立に必要な数の経路を選択し、当該選択した経路を束ねて仮想的に一つのパスを確立する場合の経路選択方法であって、各々の経路の合計コスト差が所定値以内の経路同士となるようなグループを編成するグループ編成工程と、前記終点ノードへパスを確立する要求に対し、前記グループ編成工程によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する経路選択工程と、を含んだことを特徴とする。
【発明の効果】
【００２０】
本発明によれば、各々の経路の合計コスト差が所定値以内の経路同士となるようなグループを編成し、終点ノードへパスを確立する要求に対し、同一グループ内から当該パスの帯域に応じた数の経路を選択するので、所定値を終点ノードのデフディレイ許容値に設定することで、デフディレイアラームの発生をなくすことが可能となる。【００２１】
また、本発明によれば、終点ノードへのパスの確立が要求される前の所定のタイミングでグループを編成し、当該編成したグループと、当該グループに含まれる経路の数とを対応付けて記憶する。そして、終点ノードへパスを確立する要求に対し、対応関係を参照して当該パスの帯域に必要な経路数以上の経路を含むグループから経路を選択する。こうすることによって、パスを確立する要求を受け付けるたびにグループを編成して経路を選択する手法と比較して、要求を受け付けてから経路を選択するまでにかかる時間を短くすることが可能となる。【００２２】
また、本発明によれば、所定帯域のパスを確立する要求を受け付けた際に、当該パスの帯域の確保に必要とする経路数を算出する。そして、使用可能な全経路を合計コストの小さい順にソートし、ソートしたテーブル内で連続する経路数の経路群であって、当該経路群に含まれる最大コストと最小コストとの差が所定値以内となる経路群を、テーブルの合計コストの最小値側から探索する。そして、探索の結果得られた経路群をグループとして編成する。こうすることによって、パスを確立する要求を受け付ける前に予めグループを編成する手法と比較して、経路が所属するグループを固定せずに、経路の組み合わせに柔軟性をもたせることが可能となるとともに、コストの変動に対して柔軟に対処することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】図１は、実施例１に係るデータ中継装置の構成を示すブロック図である。
【図２】図２は、ネットワークの具体例および当該ネットワーク内における所定の経路を示す図である。
【図３】図３は、合計コスト記憶部が記憶する情報の例を示す図である。
【図４】図４は、昇順合計コスト記憶部が記憶する情報の例を示す図である。
【図５】図５は、組分後合計コスト記憶部が記憶する情報の例を示す図である。
【図６】図６は、経路選択参照テーブル記憶部が記憶する情報の例を示す図である。
【図７】図７は、経路選択参照テーブル作成部による処理の流れを示すフローチャートである。
【図８】図８は、実施例２に係るデータ中継装置の構成を示すブロック図である。
【図９】図９は、グループ探索処理部による処理を説明するための図である。
【図１０】図１０は、経路指示部による処理の流れを示すフローチャートである。
【符号の説明】
【００２４】
１  ネットワーク
１０、９０、１２０  データ中継装置
２０、１００  データ受信処理部
３０、１１０  データ送信処理部
４０  要求取得部
５０、１３０  経路指示部
６０  経路選択参照テーブル作成部
６１、１３１ａ  ソート処理部
６２  組分処理部
６３  テーブル作成処理部
７０  経路選択参照テーブル記憶部
８０  記憶部
８１  合計コスト記憶部
８２  昇順合計コスト記憶部
８３  組分後合計コスト記憶部
１０１  伝送遅延差吸収部
１３１  グループ探索処理部
１３２  グループ編成処理部
【発明を実施するための最良の形態】
【００２５】
以下に添付図面を参照して、本発明に係るデータ中継装置の好適な実施例について詳細に説明する。
【実施例１】
【００２６】
まず、図１および図２を用いて本発明に係るデータ中継装置の概要を説明する。なお、図１は、実施例１に係るデータ中継装置の構成を示すブロック図であり、図２は、ネットワークの具体例および当該ネットワーク内における所定の経路を示す図である。【００２７】
データ中継装置１０は、自装置についてもネットワーク１におけるノードの一つとなり、ネットワーク１を構成する。そして、データ中継装置１０は、同じくネットワーク１におけるノードの一つであるデータ中継装置９０とネットワーク１を介して通信可能に接続される。【００２８】
具体的に例を挙げて説明すると、図２に示すように、「ａ」〜「ｈ」の記号を付した８つのノードで構成されるネットワークにおいて、データ中継装置１０およびデータ中継装置９０は、それぞれノード「ａ」およびノード「ｈ」の位置関係でネットワークに存在する。【００２９】
また、図１に戻って、データ中継装置１０は、自装置よりデータ中継装置９０までに至るための異なる複数通りの経路について、各経路内のノード間のコスト（コストについては後述する）の合計である合計コストを予め記憶する。【００３０】
具体的に例を挙げて説明すると、図２に示すように、ノード「ａ」としてのデータ中継装置１０は、自装置よりノード「ｈ」としてのデータ中継装置９０までに至るための各経路に経路ＩＤを付与し、経路情報として保持している。例えば、データ中継装置１０は、ノード「ｂ」そしてノード「ｆ」を経由する経路に対して経路ＩＤ「Ｐ１」として認識する。そして、データ中継装置１０は、後述する合計コスト記憶部８１において、経路ＩＤと、当該経路ＩＤが付与された経路の合計コストとを対応付けて予め記憶する。【００３１】
また、図１に戻って、データ中継装置１０は、自装置とデータ中継装置９０との間にＶＣＡＴに基づいた所定帯域のパスを確立した場合には、自装置よりデータ中継装置９０までに至るための異なる複数の経路にデータを振り分けて送信する。【００３２】
具体的に例を挙げて説明すると、図２に示すように、ノード「ａ」としてのデータ中継装置１０は、自装置とノード「ｈ」としてのデータ中継装置９０との間に１５０Ｍｂｐｓのパスを確立した場合には、例えば、経路ＩＤ「Ｐ１」が付与された経路と、経路ＩＤ「Ｐ２」が付与された経路と、経路ＩＤ「Ｐ３」が付与された経路との３つの経路にデータをそれぞれ５０Ｍｂｐｓずつ振り分けて送信する。【００３３】
また、図１に戻って、データ中継装置９０は、データ中継装置１０から異なる複数の経路で送信されたデータを受信し、経路間で発生した伝送遅延差を吸収しつつ、振り分けられたデータを多重化する。また、データ中継装置９０は、上述したコストと同等な数値でデフディレイ許容値を設定している。そして、データ中継装置９０は、データ中継装置１０より送信されたデータが流れる経路間の合計コストの差が当該デフディレイ許容値を越えると、ネットワーク１にデフディレイアラームを発生させる。なお、本実施例では、データ中継装置１０が当該デフディレイ許容値を予め保持しているものとして説明を行う。以上がデータ中継装置の概要である。【００３４】
次に、図１を用いてデータ中継装置の構成を説明する。同図に示すように、データ中継装置１０は、データ受信処理部２０と、データ送信処理部３０と、要求取得部４０と、経路指示部５０と、経路選択参照テーブル作成部６０と、経路選択参照テーブル記憶部７０と、記憶部８０とを備える。【００３５】
データ受信処理部２０は、当該データ中継装置１０に対して送信されたデータを受け付けて処理する。具体的には、データ受信処理部２０は、データ中継装置９０との間に確立されたパスを通すデータを受け付けた場合には、後述するデータ送信処理部３０へ出力する。また、データ受信処理部２０は、ネットワーク１を管理する管理装置から送信されたパスの確立に係る要求を受け付けた場合には、後述する要求取得部４０に出力する。【００３６】
データ送信処理部３０は、ＶＣＡＴに基づいてデータ中継装置９０へデータを送信する。具体的には、データ送信処理部３０は、パスを通してデータ中継装置９０に転送するデータをデータ受信処理部２０から受け取ると、後述する経路指示部５０によって現に指示されている経路へ当該受け取ったデータを振り分けて送信する。【００３７】
以上、データ中継装置１０の概要で説明した処理動作を行うデータ受信処理部２０およびデータ送信処理部３０について説明した。【００３８】
以下では、図２〜図６を用いつつ、データ中継装置１０において特に本発明に関連する構成要素を説明する。なお、図３は、合計コスト記憶部が記憶する情報の例を示す図であり、図４は、昇順合計コスト記憶部が記憶する情報の例を示す図であり、図５は、組分後合計コスト記憶部が記憶する情報の例を示す図であり、図６は、経路選択参照テーブル記憶部が記憶する情報の例を示す図である。【００３９】
記憶部８０は、経路選択参照テーブル作成部６０による各種処理に用いられるデータなどを記憶し、特に本発明に密接に関連するものとしては、合計コスト記憶部８１と、昇順合計コスト記憶部８２と、組分後合計コスト記憶部８３とを備える。【００４０】
合計コスト記憶部８１は、当該データ中継装置１０よりデータ中継装置９０までに至るための異なる複数通りの経路について、各経路に含まれるリンクに対するコストの合計である合計コストを記憶する。【００４１】
コストとは、ＧＭＬＰＳで定義されている数値であり、リンク（ネットワーク内におけるノードとノードの区間）に対して所定の算出手法により決定される。例えば、図２に示すネットワークにおいて、ノード「ａ」とノード「ｂ」の区間については、コスト「１」となる。また、経路ＩＤ「Ｐ１」の経路では、ノード「ａ」とノード「ｂ」の区間のコストが「１」、ノード「ｂ」とノード「ｆ」の区間のコストが「１１」、ノード「ｆ」とノード「ｈ」の区間のコストが「４」であるので、合計コストは、「１」と、「１１」と、「４」とを合計し、「１６」となる。なお、経路ＩＤ「Ｐ２」および経路ＩＤ「Ｐ３」の経路では、合計コストは、それぞれ「５」および「２０」となる。データ中継装置１０は、ネットワーク１へ接続された際に、当該ネットワーク１における全ノード間の接続に係る情報を収集してコストを算出する。そして、データ中継装置１０は、自装置よりデータ中継装置９０までに至るための異なる複数通りの経路について、各経路に含まれるリンクに対するコストの合計を算出し、合計コスト記憶部８１において経路ごとに記憶する。【００４２】
その結果、具体的には、図３に示すように、合計コスト記憶部８１は、経路ＩＤと、合計コストとを対応付けて記憶する。例えば、図３に示すように、合計コスト記憶部８１は、経路ＩＤ「Ｐ１」と、合計コスト「１６」とを対応付けて記憶する。【００４３】
昇順合計コスト記憶部８２は、合計コスト記憶部８１に格納されたデータが合計コストについて小さい順に並び換えられた結果を記憶する。具体的には、図４に示すように、昇順合計コスト記憶部８２は、経路ＩＤおよび合計コストの対応関係に対し、「０」から始まる連番であり、後述する組分処理部６２による情報処理に利用されるインデックスをさらに対応付けて記憶する。例えば、図４に示すように、昇順合計コスト記憶部８２は、インデックス「０」と、経路ＩＤ「Ｐ２」と、合計コスト「５」とを対応付けて記憶する。【００４４】
組分後合計コスト記憶部８３は、昇順合計コスト記憶部８２に格納されたデータがグルーピングされた結果を記憶する。具体的には、図５に示すように、組分後合計コスト記憶部８３は、インデックス、経路ＩＤおよび合計コストの対応関係に対し、当該経路ＩＤが付与された経路が所属するグループを一意に識別可能なグループＩＤをさらに対応付けて記憶する。例えば、図５に示すように、組分後合計コスト記憶部８３は、インデックス「０」と、経路ＩＤ「Ｐ２」と、合計コスト「５」と、グループＩＤ「Ａ」とを対応付けて記憶する。【００４５】
経路選択参照テーブル記憶部７０は、後述する経路選択参照テーブル作成部６０によって編成されたグループと、当該グループに含まれる経路の数とを対応付けて記憶する。【００４６】
具体的には、図６に示すように、経路選択参照テーブル記憶部７０は、グループＩＤと、当該グループＩＤで識別されるグループに含まれる経路の数である経路数と、グループに含まれる経路に付与された経路ＩＤとを対応付けて記憶する。例えば、図６に示すように、経路選択参照テーブル記憶部７０は、グループＩＤ「Ａ」と経路数「２」との対応関係に対し、経路ＩＤ「Ｐ２」および経路ＩＤ「Ｐ６」を対応付けて記憶する。【００４７】
経路選択参照テーブル作成部６０は、経路選択参照テーブル記憶部７０によって記憶される経路選択参照テーブルを作成する処理部であり、具体的には、ソート処理部６１と、組分処理部６２と、テーブル作成処理部６３とで構成される。【００４８】
ソート処理部６１は、合計コストの大小に基づいて経路ＩＤおよび合計コストの対応関係を並び換える。具体的には、ソート処理部６１は、合計コスト記憶部８１に格納された対応関係を読み出し、当該読み出した対応関係を合計コストの大小に基づいて並び換える。そして、ソート処理部６１は、並び換えた対応関係に対して「０」から始まる連番であるインデックスを付与し、昇順合計コスト記憶部８２に格納する。【００４９】
組分処理部６２は、各々の経路の合計コスト差が予め当該データ中継装置１０に設定された所定値以内の経路同士となるようなグループを編成する。なお、グループを編成するタイミングについては、当該データ中継装置１０に対してデータ中継装置９０へのパスの確立が要求される前の所定のタイミングである。具体的には、組分処理部６２は、昇順合計コスト記憶部８２に格納された情報を処理し、その処理結果を組分後合計コスト記憶部８３に格納する。なお、組分処理部６２による処理の詳細についてはフローチャートで後述する。【００５０】
テーブル作成処理部６３は、組分処理部６２によって編成されたグループと、当該グループに含まれる経路の数とを対応付けたテーブルを作成する。具体的には、テーブル作成処理部６３は、組分後合計コスト記憶部８３が記憶するテーブルに基づいて、同一のグループＩＤを含む対応関係の数をグループＩＤごとに算出する。そして、テーブル作成処理部６３は、グループＩＤに対して算出した値を経路数として、グループＩＤと、経路数と、グループＩＤで識別されるグループに含まれる経路の経路ＩＤとを対応付けたテーブルを作成し、経路選択参照テーブル記憶部７０に格納する。【００５１】
要求取得部４０は、パスを確立する要求から経路数を算出する。具体的には、要求取得部４０は、管理装置から送信されたパスの確立に係る要求をデータ受信処理部２０が受け付けると、当該要求に含まれる帯域情報を取得し、当該帯域情報より必要な経路数を算出し、経路指示部５０に出力する。例えば、要求取得部４０は、１５０Ｍｂｐｓのパスを確立する要求からは、経路数「３」を算出する。なお、要求に含まれる情報としては、帯域情報のほか、パスの終点となるノードの識別情報などが含まれるが、本実施例では、パスの終点をデータ中継装置９０のみに限定し、帯域情報以外の情報については省略して説明する。【００５２】
経路指示部５０は、データ中継装置９０へパスを確立する要求に対し、経路選択参照テーブル作成部６０によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する。具体的には、経路指示部５０は、要求取得部４０から出力された経路数を受け取ると、経路選択参照テーブル記憶部７０によって記憶されたテーブルに基づいて、当該受け取った経路数以上の経路数を含む対応関係を選択する。そして、経路指示部５０は、選択した対応関係から経路ＩＤを読み出し、経路ＩＤが示す経路にデータを振り分けて送信するようにデータ送信処理部３０に対して指示する。【００５３】
引き続き、図１を用いてデータ中継装置９０の構成を説明する。同図に示すように、データ中継装置９０は、特に本発明に密接に関連するものとしては、データ受信処理部１００と、データ送信処理部１１０とを備える。【００５４】
データ受信処理部１００は、データ中継装置１０から異なる複数の経路で送信されたデータを受信すると、伝送遅延差吸収部１０１によって経路間で発生した伝送遅延差を吸収しつつ、振り分けられたデータを多重化する。そして、データ受信処理部１００は、多重化されたデータをデータ送信処理部１１０に出力する。【００５５】
データ送信処理部１１０は、多重化されたデータをデータ受信処理部１００から受け取ると、所定の中継先へさらにデータを送信する。【００５６】
次に、データ中継装置１０における経路選択参照テーブル作成部６０の処理動作について図７のフローチャートを参照して説明する。同図に示した処理フローは、データ中継装置１０に対してデータ中継装置９０へのパスの確立が要求される前の所定のタイミング（例えばデータ中継装置１０がネットワーク１へ接続された際など）に実行される処理である。【００５７】
同図に示すように、経路選択参照テーブル作成部６０において、ソート処理部６１は、経路ＩＤおよび合計コストの対応関係を合計コストが昇順となるように並び換える（ステップＳ１１０）。そして、ソート処理部６１は、並び換えた対応関係に「０」から始まる連番のインデックスを付与し（ステップＳ１２０）、昇順合計コスト記憶部８２に格納する。【００５８】
組分処理部６２は、先頭インデックスに対応付けられた合計コストを基準コストとし（ステップＳ１３０）、先頭インデックスが付与された経路ＩＤが示す経路を所定のグループに所属させるとともに（ステップＳ１４０）、経路ＩＤに対して当該グループを識別するグループＩＤを対応付ける。【００５９】
次に、組分処理部６２は、インデックス「ｎ（ｎの初期値は１）」に対応付けられた合計コストと基準コストの差を算出する（ステップＳ１５０）。【００６０】
そして、組分処理部６２は、算出した差がデータ中継装置９０のデフディレイ許容値以内であるか否かを判定する（ステップＳ１６０）。なお、データ中継装置１０は、予め所定のタイミングでデータ中継装置９０のデフディレイ許容値を保持している。【００６１】
組分処理部６２は、判定の結果、算出した差がデータ中継装置９０のデフディレイ許容値以内である場合には（ステップＳ１６０肯定）、インデックス「ｎ」に対応付けられた経路ＩＤで識別される経路を、現に基準コストである合計コストに対応付けられた経路ＩＤで識別される経路が所属するグループと同じグループに所属させる（ステップＳ１７０）。【００６２】
一方、組分処理部６２は、判定の結果、上記したデフディレイ許容値を超える場合には（ステップＳ１６０否定）、インデックス「ｎ」に対応付けられた経路ＩＤで識別される経路を、現に基準コストである合計コストに対応付けられた経路ＩＤで識別される経路が所属するグループとは別の新たなグループに所属させ（ステップＳ２００）、インデックス「ｎ」に対応付けられた合計コストを基準コストとする（ステップＳ２１０）。【００６３】
組分処理部６２は、インデックス「ｎ」に対応付けられた経路ＩＤで識別される経路を、現に基準コストである合計コストに対応付けられた経路ＩＤで識別される経路が所属するグループと同じグループに所属させた後、もしくは、インデックス「ｎ」に対応付けられた合計コストを基準コストとした後（ステップＳ１７０またはステップＳ２１０）、ｎをインクリメントする（ステップＳ１８０）。そして、組分処理部６２は、ｎが後尾インデックスを超えたか否かを判定し（ステップＳ１９０）、超えていない場合には（ステップＳ１９０否定）、ステップＳ１５０〜ステップＳ２１０の処理をｎが後尾インデックスを超えるまで繰り返す。ｎが後尾インデックスを超えるまで組分処理部６２による処理が繰り返されると、図５に示すような対応関係が組分後合計コスト記憶部８３に格納される。【００６４】
そして、テーブル作成処理部６３は、ｎが後尾インデックスを超えた場合には（ステップＳ１９０肯定）、組分後合計コスト記憶部８３に格納された対応関係に基づいて、経路選択参照テーブルを作成して経路選択参照テーブル記憶部７０に格納し（ステップＳ２２０）、処理を終了する。【００６５】
なお、以上で説明した処理による結果なされた組分けは、異なる複数の経路に対する組分けの一例であって、これに限定されるものではない。図５では、経路ＩＤに対して重複なくグループＩＤが対応付けられているが、例えば、各々の経路の合計コスト差が所定値以内であるという条件を満たすならば、経路ＩＤ「Ｐ６」に対してグループＩＤ「Ａ」およびグループＩＤ「Ｂ」を対応付けるようにしてもよい。【００６６】
［実施例１の効果］
上記したように、実施例１によれば、各々の経路の合計コスト差が予めデータ中継装置１０に設定された所定値以内の経路同士となるようなグループを編成する。そして、終点ノードへパスを確立する要求に対し、編成したグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する。こうすることによって、所定値をデータ中継装置９０のデフディレイ許容値に設定し、デフディレイアラームの発生をなくすことが可能となる。【００６７】
また、実施例１によれば、終点ノードへのパスの確立が要求される前の所定のタイミングでグループを編成し、当該編成したグループと、当該グループに含まれる経路の数とを対応付けて記憶する。そして、終点ノードへパスを確立する要求に対し、対応関係を参照して当該パスの帯域に必要な経路数以上の経路を含むグループから経路を選択する。こうすることによって、パスを確立する要求を受け付けるたびにグループを編成して経路を選択する手法と比較して、要求を受け付けてから経路を選択するまでにかかる時間を短くすることが可能となる。
【実施例２】
【００６８】
実施例２では、要求を受け付けるたびにグループを編成し、当該編成したグループに基づいて経路を選択することとした。これは、経路が所属するグループを固定せず、経路の組み合わせに柔軟性をもたせるとともに、コストの変動に対して柔軟に対処するためである。【００６９】
図８を用いて、実施例２に係るデータ中継装置１２０の構成を説明する。図８は、実施例２に係るデータ中継装置の構成を示すブロック図である。同図に示すように、データ中継装置１２０は、実施例１と同様、データ受信処理部２０と、データ送信処理部３０と、要求取得部４０と、記憶部８０とを備え、記憶部８０内には、合計コスト記憶部８１および昇順合計コスト記憶部８２を備える。また、データ中継装置１２０は、実施例１と異なる点としては、経路指示部１３０をさらに備える。なお、実施例１と同じ処理動作を行う部や、同じ機能を有する部については説明を省略し、以下では、経路指示部１３０についてのみ説明を行う。【００７０】
経路指示部１３０は、グループ探索処理部１３１と、グループ編成処理部１３２とを備え、データ中継装置９０へパスを確立する要求に対し、グループ編成処理部１３２によって編成されたグループにおいて同一グループ内から当該パスの帯域に応じた数の経路を選択する。具体的には、経路指示部１３０は、要求取得部４０から出力された経路数を受け取ると、内部に備えた各処理部による処理を実行し、グループ編成処理部１３２によって編成されたグループ内の経路を選択する。そして、経路指示部１３０は、当該選択した経路にデータを振り分けて送信するようにデータ送信処理部３０に対して指示する。【００７１】
グループ探索処理部１３１は、使用可能な全経路を合計コストの小さい順にソートし、ソートしたテーブル内で連続するグループＩＤ経路数の経路群であって、当該経路群に含まれる最大コストと最小コストとの差が所定値以内となる経路群を、グループＩＤテーブルの合計コストの最小値側から探索する。【００７２】
具体的には、グループ探索処理部１３１は、その内部にソート処理部１３１ａを備え、当該ソート処理部１３１ａによって、合計コスト記憶部８１に格納された対応関係を合計コストの大小に基づいて並び換える。そして、並び換えた対応関係に対して「０」から始まる連番であるインデックスを付与し、昇順合計コスト記憶部８２に格納する。【００７３】
以下に、図９を用いて、要求取得部４０から受け取った経路数が３であった場合を例に、ソート後のグループ探索処理部１３１による処理を説明する。図９上段に示すように、グループ探索処理部１３１は、まず、インデックス「０」からインデックス「２」に対応する合計コストを選択する。【００７４】
そして、グループ探索処理部１３１は、選択した合計コストにおいて最小の合計コスト「５」と最大の合計コスト「１１」との差「６」を算出する。【００７５】
ここで、グループ探索処理部１３１は、算出した差「６」がデータ中継装置９０のデフディレイ許容値以内であれば、当該選択した合計コストに対応する経路ＩＤを後述するグループ編成処理部１３２に出力する。一方、グループ探索処理部１３１は、デフディレイ許容値を超える場合には、図９中段に示すように、選択範囲をずらして、インデックス「１」からインデックス「３」に対応する合計コストを選択する。【００７６】
そして、グループ探索処理部１３１は、選択した合計コストにおいて、同様に最小の合計コスト「９」と最大の合計コスト「１６」との差「７」を算出する。【００７７】
以上のように、グループ探索処理部１３１は、最小の合計コストと最大の合計コストとの差がデフディレイ許容値以内となる合計コストを探索する。【００７８】
なお、合計コストの選択時、すでにパスの確立に用いられた経路の合計コストについては選択外となる。例えば、図９上段では、インデックス「０」からインデックス「２」に対応する合計コストが選択されているが、インデックス「１」およびインデックス「２」に対応する合計コストを持つ経路がすでにパスの確立に用いられている場合には、グループ探索処理部１３１は、インデックス「０」、インデックス「３」、インデックス「４」に対応する合計コストを選択する。【００７９】
また、所定の合計コストが候補となるように選択範囲をずらしてもよい。例えば、経路ＩＤ「Ｐ１」に対応する合計コスト「１６」を候補として、まず、インデックス「１」からインデックス「３」が付与された合計コストを選択する。そして、同様に選択範囲をずらしていき、最後にインデックス「３」からインデックス「５」が付与された合計コストを選択する。以上のように条件を満たす合計コストを探索してもよい。【００８０】
そして、グループ探索処理部１３１は、探索の結果、条件を満たす合計コストが得られた場合には、当該合計コストに対応付けられた経路ＩＤをグループ編成処理部１３２に出力する。【００８１】
グループ編成処理部１３２は、グループ探索処理部１３１による探索の結果得られた経路群をグループとして編成する。具体的には、グループ編成処理部１３２は、グループ探索処理部１３１から経路ＩＤを受け取ると、当該受け取った経路ＩＤが示す経路をグループとして編成する。【００８２】
次に、データ中継装置１２０における経路指示部１３０の処理動作について図１０のフローチャートを参照して説明する。同図に示した処理フローは、データ中継装置１２０に対してデータ中継装置９０へのパスの確立が要求されるたびに繰り返し実行される処理である。【００８３】
同図に示すように、経路指示部１３０は、要求取得部４０から経路数を受け取ると（ステップＳ２３０肯定）、ソート処理部１３１ａによって、経路ＩＤおよび合計コストの対応関係を合計コストが昇順となるように並び換える（ステップＳ２４０）。そして、経路指示部１３０は、ソート処理部１３１ａによって、並び換えた対応関係に「０」から始まる連番のインデックスを付与し（ステップＳ２５０）、昇順合計コスト記憶部８２に格納する。【００８４】
そして、経路指示部１３０は、グループ探索処理部１３１によって、インデックス「ｎ（初期値は０）」に対応付けられた合計コストからインデックスの数字が低い順に経路数だけ合計コストを選択する（ステップＳ２６０）。【００８５】
そして、経路指示部１３０は、グループ探索処理部１３１によって、選択した合計コストにおいて最小の合計コストと最大の合計コストとの差を算出する（ステップＳ２７０）。【００８６】
そして、経路指示部１３０は、グループ探索処理部１３１によって、算出した差がデフディレイ許容値以内であるか否かを判定し（ステップＳ２８０）、デフディレイ許容値を超える場合には（ステップＳ２８０否定）、ｎをインクリメントした後（ステップＳ３１０）、ステップＳ２６０の処理へ戻り、引き続き同様の処理を実行する。【００８７】
一方、経路指示部１３０は、デフディレイ許容値以内である場合には（ステップＳ２８０肯定）、グループ探索処理部１３１によって現に選択されている合計コストを持つ経路同士を、グループ編成処理部１３２によってグループとして編成する（ステップＳ２９０）。そして、経路指示部１３０は、編成したグループ内の経路にデータを振り分けて送信するようにデータ送信処理部３０に対して指示し（ステップＳ３００）、処理を終了する。【００８８】
［実施例２の効果］
上記したように、実施例２によれば、データ中継装置９０へ所定帯域のパスを確立する要求を受け付けた際に、当該パスの帯域の確保に必要とする経路数を算出する。そして、使用可能な全経路を合計コストの小さい順にソートし、ソートしたテーブル内で連続する経路数の経路群であって、当該経路群に含まれる最大コストと最小コストとの差が所定値以内となる経路群を、テーブルの合計コストの最小値側から探索する。そして、探索の結果得られた経路群をグループとして編成する。こうすることによって、パスを確立する要求を受け付ける前に予めグループを編成する手法と比較して、経路が所属するグループを固定せずに、経路の組み合わせに柔軟性をもたせることが可能となり、コストの変動に対して柔軟に対処することが可能となる。【００８９】
以上、本発明に係るデータ中継装置の好適な実施例について説明してきたが、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、例えば、ソート処理部６１と、組分処理部６２とを統合するなど、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【産業上の利用可能性】
【００９０】
上述してきたように、本発明に係るデータ中継装置および経路選択方法は、ネットワークにおいて始点ノードより終点ノードまでに至るための異なる複数通りの経路について、各経路内のノード間のコストの合計である合計コストを参照しつつ、所定帯域のパスの確立に必要な数の経路を選択し、当該選択した経路を束ねて仮想的に一つのパスを確立する場合に有用であり、デフディレイアラームの発生をなくすことに適する。
【図１】
2009063550.tif 000003
【図２】
2009063550.tif 000004
【図３】
2009063550.tif 000005
【図４】
2009063550.tif 000006
【図５】
2009063550.tif 000007
【図６】
2009063550.tif 000008
【図７】
2009063550.tif 000009
【図８】
2009063550.tif 000010
【図９】
2009063550.tif 000011
【図１０】
2009063550.tif 000012
【国際調査報告】
2009063550.tif 000013
2009063550.tif 000014
2009063550.tif 000015
2009063550.tif 000016