JP4398263B2

JP4398263B2 - 経路設計方法

Info

Publication number: JP4398263B2
Application number: JP2004005930A
Authority: JP
Inventors: 晃永田; 啓二宮▲崎▼; 仁上野
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2004-01-13
Filing date: 2004-01-13
Publication date: 2010-01-13
Anticipated expiration: 2024-01-13
Also published as: CN100377529C; CN1642111A; JP2005203885A; US8185616B2; US20050154790A1

Description

本発明は、複数のノードを接続してなるネットワークにおいて、該ノードがトラフィックを中継する経路、及びトラフィックの割り当てを適切に設計し、該ネットワークの効率の良い利用を可能とする技術に関する。
例えば、本発明は、複数地点にまたがるユーザ拠点間でMulti Point-to-Multi Point通信を提供する仮想ＬＡＮサービス（例：広域イーサネット(登録商標)）の管理・運用に用いられる技術である。具体的には、仮想ＬＡＮ運用システムにおいて、ユーザ拠点〜中継ネットワーク間の接続回線（アクセスリンク）の契約帯域値を超えない程度に十分な速度を確保し且つ効率よく収容するよう、ユーザトラヒックを収容する経路および帯域を、ユーザごとに決定する技術に関する。

従来、複数のユーザ拠点間で、Multi Point-to-Multi Point通信を提供するサービスとして、中継ネットワークにイーサスイッチノードを配備し、イーサネットのＶＬＡＮ技術を用いてユーザトラヒックを収容する所謂広域イーサネットサービスやＴＬＳ（transparent LAN service）が広く知られている。以後、広域イーサネットを例にとって述べる。

多地点ＬＡＮを収容する広域イーサネットにおいて、サービス提供通信事業者は、ユーザの拠点すべてを結ぶ経路（ツリートポロジ）を決定し、これを論理ブロードキャストドメイン（ＶＬＡＮ）としてユーザに割り当てる。このときイーサスイッチノードには、出力ポートごとに転送可能なＶＬＡＮ、転送しないＶＬＡＮを設定する。これにより、ユーザトラヒックの到達範囲を決定でき、ユーザごとに異なるＶＬＡＮを割り当てることで、ユーザＡの拠点から送出されたトラヒックが、異なるユーザＢの拠点に到達させないことができる。すなわち、同一ネットワークに複数の異なるユーザトラヒックが収容可能である。

ここで、あるユーザに割り当てられた論理ブロードキャストドメインに含まれるノードまたはリンクの集合を経路、論理ブロードキャストドメインの範囲を決定することを経路設計と呼ぶことにする。この経路設計とは、具体的には、中継ネットワークの各ノードにおいて、どのポートで転送可能にし、どのポートで転送不可にするかを決定することや、これらのポートに割り当てる帯域を決定することである。

ユーザトラヒックへのＶＬＡＮの割り当ては、例えば、中継ネットワークの入り口のノードで、ユーザの送出したイーサネットフレーム個々に対して、ＩＥＥＥ８０２．１ｑ記載のＶＬＡＮタグを付与することで実現される。タグには、トラヒックを識別するための識別子（ＶＬＡＮＩＤ）が含まれる。

たとえば、ユーザＡに対するＶＬＡＮＩＤが１００番であると決定されたとすると（どのユーザに何番のＶＬＡＮＩＤを割り当てるかは、例えばオペレータが他のユーザと重複しない値を適当に決めるなどすることによって決定される）、ユーザＡのイーサネットフレームのＶＬＡＮタグ内にＶＬＡＮＩＤ１００を書き込む。中継ネットワーク内部（中継ネットワーク入り口ノード含む）では、このＶＬＡＮＩＤを見てトラヒック転送可能ポートが決定される。受信したフレームが、転送可能ポートのうち具体的にどのポートに転送されるかは、通常のイーサネット技術に順ずる。すなわち、各イーサネットフレームのもつ宛先ＭＡＣアドレスや、ノード(以下、イーサネット装置とも称する)の機能に依存する。

イーサネット装置がＭＡＣアドレス学習機能を持っていて、且つＭＡＣアドレス学習テーブルに宛先ＭＡＣアドレスおよび転送先ポートがエントリされていればそのポートに転送し、ＭＡＣアドレス学習テーブルにエントリされていない宛先ＭＡＣアドレスを持つイーサネットフレームであるか、あるいはＭＡＣアドレス学習機能を有しないイーサネット装置であれば、受信したポートを除く転送可能な全ポートに受信フレームをコピーして転送する（ブロードキャスト）。中継ネットワークを転送され、中継ネットワークの出口ノードに到達すると、出口ノードでは、ＶＬＡＮタグを削除し、そのＶＬＡＮＩＤに対応するポートへ出力することで、所望のユーザへのトラヒック転送を完了する。

広域イーサにおいて、現在はユーザが、接続したい拠点ごとにアクセスリンクの速度（帯域）を、サービス提供者と取り決めて（契約して）、サービスを享受するケースが主流である。アクセスリンクとは、拠点と中継ネットワークとを結ぶ回線のことを指す。この場合、ユーザトラヒックは拠点のアクセスリンクで契約値を上回らないようなトラヒック速度に絞られた後、中継ネットワークに流れ込む。中継ネットワーク内では、ユーザに割り当てられた論理ブロードキャストドメイン内を、イーサネット方式（ブロードキャスト、ＭＡＣアドレス学習、など）に従って転送される。

ユーザトラヒックは、アクセスリンクでそのトラヒック速度を絞られているため、中継ネットワークにおいて、オペレータ（サービス提供者）が（例えば手動で）決定した経路上を、特に帯域制御されることなく、あるいは、経路上の各リンクにおいてユーザトラヒックを収容するのに十分大きい帯域（例えば、全拠点が通信しても輻輳が起こらない程度に）を割り当てられて流されていることが考えられる。後者の場合、経路に沿って単純に大きな帯域、例えば、全拠点のアクセスリンク帯域の和９０Mbpsよりも大きい１００Mbpsを割り当てる（図１）など。

本願発明に関連する先行技術として、例えば、下記の特許文献１乃至４に開示される技術がある。
特開平９−８３５４６号公報特開平１１−３４１１５４号公報特開２００２−１４１９３２号公報

そのため、異なる帯域を契約する２拠点間が通信する場合、送信側から受信側のアクセスリンク契約帯域以上のトラヒックが送出され受信側のアクセスリンク手前でその超過分が廃棄されることが起こりうる。中継ネットワークからしてみれば、廃棄されるべき無駄なトラヒックを転送したことになり、帯域の無駄遣いである。

帯域無駄遣いは、他ユーザの品質低下の原因にもなりうる。また、ネットワークに収容するユーザ数を増やすには、ユーザが利用する帯域の総和（消費帯域と呼ぶことにする）はできるだけ小さいほうが望ましく、帯域無駄遣いは、これを妨げる。

これを回避するためには中継ネットワークの各リンクでユーザごとの利用可能帯域を設定し帯域制御すればよいが、収容拠点が多数あり、また、拠点からのトラヒック要求は、その拠点からの最大トラヒック速度がアクセスリンクの契約帯域として与えられているだけで、どの拠点宛にどれだけのトラヒック要求があるか、決定されていないことが想定され、その利用可能帯域を効果的に決定する方法が無い。

ここでは、経路が与えられることを前提とする。全拠点を結び、且つ閉路がない経路であればなんでもよい。たとえば、オペレータが管理画面等からマウスクリック等でリンク
を選択することで決定したものでよい。

本発明の目的は、ユーザトラヒックを、効率よく収容するための経路設計を容易に行うことができる技術を提供することである。

本発明は上記課題を解決するために、以下の手段を採用した。
（１）本発明の経路設計方法は、複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置にて、前記ユーザ拠点間の通信経路を設計する方法であって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、を含む。

これにより、ユーザトラヒックを、効率よく収容するための経路および割り当て帯域を決定し、且つその結果を自動でネットワーク装置に設定することが可能となり、経路設計時のオペレーションの手間・所要時間を抑えることが出来る。

（２）本発明の経路設計方法は、前記経路設計を行うステップにおいて、全ユーザ拠点を結ぶ経路上の各中継ノードについて任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とする付記１に記載の経路設計方法。

これにより、ユーザトラヒックに対し、中継ネットワーク内ノードで転送されるたびにそのノードから受信側拠点までの間の許容量を超えた分が廃棄されて絞られる。つまり、受信側のアクセスリンクの通信帯域を越えて廃棄されるトラヒックを早めに廃棄するよう各中継ノードの利用可能帯域を割り当てることが可能となり、トラヒック廃棄ポイントをできるだけトラヒック送出側に近づけられるため、中継ネットワーク上での無駄なトラヒック転送を抑えることが出来る経路を設計できる。

（３）本発明の経路設計方法は、前記経路設計を行うステップにおいて、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外して通信経路を求める。

これにより、ユーザ拠点間の通信の中継と関係のない処理を省くことができ、少ないケ計算規模で経路設計を行うことができる。

（４）前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求める。
これにより、（拠点収容ノード数）＜（中継ノード総数）の場合に、短い計算時間で上
記経路設計が可能となる。

（５）前記経路設計を行うステップにおいて、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外し、この除外後のツリー状の経路について各リンクに割り当てられた帯域の総和が最小となるように帯域を割り当てる。
これにより、消費帯域が最小となる経路および割り当て帯域を短時間で決定することが出来る。

（６）前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求め、該最短ホップ経路について通信帯域の割り当てを行う。
これにより、（拠点収容ノード数）＜（中継ノード数）の場合に、短い計算時間で最短ホップ経路を特定し、この特定の経路についてのみ帯域の割り当てを行えば良く、適切な経路及び帯域を短時間で決定できる。

（７）本発明の経路設計方法は、拠点収容ノードになりうる中継ノードを起点としたツリー状の経路の情報を予め求めて記憶しておき、経路設計を行う際に該ツリー状の経路の情報を読み出して利用する。
これにより、同じ最短路ツリー計算を何度も行う必要がなくなるため、個々のユーザに対する計算時間を抑えることができる。

（８）本発明の経路設計方法は、ポート数１で且つユーザ拠点収容ノードではない中継ノードおよびそれに接続するリンク全てを設計対象から除外したのちに経路設計を行う。
これにより、設計対象とするノードおよびリンクを減らすことが出来るため、最短路ツリー計算にかかる時間が減少し、設計時間の短縮に繋がる。

（９）本発明の経路設計方法は、前記ネットワークがサブドメインに分割されて管理されている場合に、前記アクセスリンクを介してユーザ拠点と接続する中継ノードを１つも含まないサブドメインに所属するノードおよびこれに接続されるリンク全てを設計対象から除外したのちに経路設計を行う。
これにより、設計対象とするノードおよびリンクを減らすことができるため、最短路ツリー計算にかかる時間が減少し、設計時間の短縮に繋がる。

（１０）本発明の経路設計方法は、ツリー状の経路を求めた際に、ある中継ノードから同じ中継数で起点ノードに到達できる別経路が求められた場合、その別経路の情報を、当該ノードに属する情報として保持しておく。
上記経路設計で求めた経路を変更する場合に、再計算することなく同じホップ数で迂回できる経路（代替経路）をすぐに提示できる。

（１１）本発明の経路設計方法は、前記経路設計の完了後、前記経路設計の結果及び前記別経路の情報を保持しておく。
前記経路設計の完了後、上記経路設計で求めた経路を変更する場合に、再計算することなく同じホップ数で迂回できる経路（代替経路）をすぐに提示できる。

また、本発明は、上記（１）〜（１１）の処理をネットワーク管理装置に実行させる経路設計プログラムであっても良い。更に、本発明は、上記プログラムを実行するデバイス（ネットワーク管理装置、コンピュータ）に読み取り可能に記録した記録媒体であっても良い。そして、それぞれのデバイスに、この記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。

このデバイスで読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等のデバイスから読み取ることができる記録媒体をいう。このような記録媒体の内デバイスから取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、CD-ROM、CD-R/W、DVD、DAT、8mmテープ、メモリカード等がある。
また、コンピュータに固定された記録媒体としてハードディスクやＲＯＭ（リードオンリーメモリ）等がある。

また、本発明は、複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワーク及び該中継ノードと接続するネットワーク管理装置とを備えるネットワークシステムにおいて、
前記ネットワーク管理装置が、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付ける入力部と、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するトポロジ取得部と、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う経路設計部と、
前記経路設計結果を出力する経路出力部と
を備え、
前記中継ノードが、
前記通信のトラヒックを受け付ける入力部と、
該トラヒックを前記ポートを介して次のノードに出力する出力部と、
前記ネットワーク管理装置から設定情報を受信する設定取得部と、
この設定情報に基づいて前記出力部のポートの設定を行う設定部と、
を備える。

本発明は、ユーザトラヒックを、効率よく収容するための経路設計を容易に行う技術を提供できる。

以下、図面を参照して本発明を実施するための最良の形態について説明する。以下の実施の形態の構成は例示であり、本発明は実施の形態の構成に限定されない。
〈実施形態１〉
図１は、本発明の実施形態１としてのネットワークシステムの全体構成を示す図である。

同図に示すように、本実施形態のネットワークシステムは、経路設計機能を持ったネットワーク管理装置１０と、ユーザトラヒックを中継する中継ノード(ネットワーク装置)Ｎと、これらを接続するネットワークを備えている。各中継ノードＮは、リンク３を介して接続され、中継ネットワークを構成している。設定用ネットワーク４は、例えばイーサネ
ットであってもよい。設定用ネットワーク４は、ネットワーク管理装置１０と全ての中継ノードとを個々に接続してもよいし、ネットワーク管理装置１０とある一つの中継ノードＮとのみ接続して、この中継ノードＮから他の中継ノードＮへは、ユーザトラヒック転送用の中継ネットワークを介して設定コマンド（設定情報）を送出してもよい。

中継ノードＮは、前記ユーザ拠点間の通信のトラヒック（ユーザトラヒック）の入力を受け付ける入力部２１や、該ユーザトラヒックを後述のポートを介して次のノード（中継ノード或はユーザ拠点）に出力する出力部２２、ネットワーク管理装置１０から設定情報を受信する設定取得部２３、この設定情報に基づいて該出力部のポートの設定を行う設定部２４を備えている。

この中継ノードＮは、ユーザ拠点１００間に流れるトラヒック全体をひとつのグループとして扱うものであり、出力部２２が有する複数のポートのうち、このグループごとに設定されたポートからこのグループのトラヒックを出力する。これにより、各中継ノードＮは、ネットワーク管理装置１０で設計された経路とおりにトラヒックを中継する。

このグループ毎の中継を実現するため中継ノードＮは、設定取得部２３がネットワーク管理装置１０から設定用ネットワーク４を介して設定情報を受信し、この設定情報に基づいて設定部２４が、トラヒックを転送可能なポートがどれで転送しないポートがどれかを該グループ毎に出力部２２に設定する。また、該設定部２４は、転送可能なポートについて、そのグループのトラヒックを転送する速度（出力レート）の上限を設定する。

広域イーサネットの場合、中継ノードＮとはイーサネット装置であり、ユーザトラヒックをグループ化して取り扱う技術はＩＥＥＥ８０２．１ｑで規定されるＶＬＡＮ技術を用いれば良い。このＶＬＡＮ技術をサポートした装置であれば、グループ（ＶＬＡＮ）ごとに転送可能なポート、転送不可能なポートを設定できる。また、ポートごとにグループ（ＶＬＡＮ）のトラヒック転送レートの上限を設定する処理は、公知の装置（例えば、富士通製のイーサネット装置ＦｌａｓｈＷａｖｅ５５５０）で行っている処理と同じである。この中継ノードＮでのＶＬＡＮごとのトラヒック転送レート制御のイメージを、図２に示す。中継ノードＮは、図２に示すように、各出力ポートにおいて所定のグループのトラヒック（フレーム）のみを選択的に出力する機能を持っている。

この中継ノードＮは、予め設定取得部２３が手動コマンドラインまたは設定用ネットワーク４を介してネットワーク管理装置１０からの制御コマンド（設定情報）を受け付け、このコマンドに基づいて設定部２４がＶＬＡＮＩＤ−キュー対応表、各ポートのキュー転送レート表のそれぞれに相当する事項を設定する。即ち出力部２２内のメモリに記憶されたＶＬＡＮＩＤ−キュー対応表及びキュー転送レートの該当項目を更新する。そして中継ノードＮの出力部２２は、このＶＬＡＮＩＤ−キュー対応表を参照して、受信したフレームをＶＬＡＮＩＤに応じたキューに振り分け、どのＶＬＡＮＩＤを持つフレームをどのポートへ転送するかを決定し、各ポートのキューコントローラが、所定のキューＮｏのキューをキュー転送レート表に基づくレート（帯域）で出力する。以降の説明では、ＶＬＡＮＩＤに対応する転送可能ポートと、そのＶＬＡＮＩＤに許可する出力レートのみを設定対象とし、設定しようとするＶＬＡＮＩＤが具体的に何番のキューに対応するか、キュー転送レート表の何番エントリに○○bpsと書き込むか等の具体的な事項は簡単のために省略
する。なお、この出力部２２による処理は、上記に限らず設定に基づいて各グループのトラヒックが所定のポートから所定の帯域で出力できる処理であれば、公知の如何なる処理であっても良い。

ネットワーク管理装置１０は、ＣＰＵやメインメモリからなる演算処理部１１、入力部１２、記憶部（ハードディスク）１３、通信制御部（ＣＣＵ）１４等からなる一般的なコ
ンピュータである。

該記憶部１３は、ネットワークの管理や運用、経路設計を行うプログラム及びオペレーティングシステム等のソフトウェアを記憶している。また、記憶部１３には、トポロジ情報データベースが構築されており、このデータベースに、自動で収集した或はオペレータが手動で入力した中継ネットワークのトポロジ情報を記憶されている。

入力部１２は、ユーザ収容網設計のために、オペレータからユーザ拠点情報を受け付ける。これは例えば、何かしらの書式に従ったファイルで行ってもよいし、ＧＵＩからの操作で行ってもよいし、テキスト入力やコマンド入力で行ってもよい。
通信制御部１４は、設定用ネットワーク４を介して各中継ノードＮと接続し、設定情報の送信やトポロジ情報の取得のための通信を制御する。

演算処理部１１は、記憶部１３に記憶したプログラムに従って入力部１２やＣＣＵ１４からの情報を処理することにより、経路設計部や、ネットワーク設定部（経路出力部に相当）、トポロジ取得部としても機能している。

トポロジ取得部は、記憶部１３のトポロジ情報データベースから中継ネットワークのトポロジ情報を取得している。このトポロジ情報データベースのトポロジ情報は、一般に良く知られたネットワーク管理システムと同様に、自動で収集して保持しておいても良いし、設計のたびにオペレータが手動で入力してもよい。このトポロジ情報には、中継ネットワークの、中継ノードＮの情報（ＩＤなど）や、ノードのもつポートの情報（ポート番号、ポートに繋がる対向の中継ノードＮのＩＤ、ポートに繋がるリンク３の情報（帯域、割り当て済み帯域）など）が含まれる。

経路設計部は、トポロジ情報データベースを参照して前記入力部で受け付けたユーザ拠点間を結ぶツリー状経路を設計する。
ネットワーク設定部は、経路設計部による設計結果に基づいて設定情報を中継ノードに送信して各中継ノードに中継経路及びその帯域を設定させる。

図３は実施形態１のネットワークシステムにおける経路設計の説明図である。同図において四角で示したＮ１〜Ｎ６のオブジェクトが中継ノードＮ、それを繋ぐ実線がリンク３、port○○が装置のもつポート番号、点線が設定用ネットワーク４、三角１０１〜１０５がユーザ拠点（具体的には各拠点のエッジルータ等）２である。この場合、中継ネットワークとは、中継ノードＮ１〜Ｎ６とこれらの間及び中継ノードＮ１〜Ｎ６とユーザ拠点１００とを結ぶリンク（アクセスリンク）３からなるネットワークを指す。

図４はこのときネットワーク管理装置１０が保持するトポロジ情報の例である。リンク帯域は単位をMbpsとして記述してある。（なお、簡単のため、トポロジ情報の一部を抜粋して示す。中継ネットワーク〜拠点の情報、たとえばアクセスリンクのポート番号などは表記しない。）

図５は各ユーザ拠点１００のユーザ情報の例を示す図である。拠点収容ノードとは、拠点２がアクセスリンクを介して接続される対向の中継ノードＮである。
そして図６はネットワーク管理装置１０による経路設計の手順を示すフローチャートである。

（ステップ１）
まず、オペレータがネットワーク管理装置１０のキーボードを操作して各ユーザ拠点１００から中継ノードＮとを接続するリンクであるアクセスリンクの帯域の情報及びこのア
クセスリンクを介してユーザ拠点と接続する中継ノードを示す情報等のユーザ情報を入力すると、ネットワーク管理装置１０はこのユーザ情報を受け付け、記憶部１３に記憶させる。

（ステップ２）
次にネットワーク管理装置１０は、トポロジ取得部により前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を記憶部１３のトポロジ情報データベースから取得する。

（ステップ３）
また、ネットワーク管理装置１０は、経路設計部により、前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う。

（ステップ４）
そして、ネットワーク管理装置１０は、前記経路設計結果に基づき各中継ノードＮについて通信を中継するポート及び中継しないポートを示す情報及び該通信を中継するポートの通信帯域の上限を示す情報を含む設定情報をそれぞれの中継ノードＮに出力（送信）する。この設定情報を受信した各中継装置は、該設定情報に基づいてＶＬＡＮＩＤ−キュー対応表及び各ポートのキュー転送レート表を更新し、上記経路で当該ユーザトラヒックを中継するように設定する。なお、本実施形態では、ネットワーク管理装置１０のネットワーク設定部（経路出力部）が、設定情報を出力することにより、各中継ノードに経路を設定するように構成したが、これに限らず、この設定情報或は経路設計結果を単にディスプレイ上に表示（出力）或は印刷出力する構成とし、各中継ノードの設定は、オペレータがこの出力を見ながら手動で設定するものでも良い。

各ユーザに対するＶＬＡＮＩＤの割り付けは、例えばオペレータが決定したものを用いてもよいし、収容網設計機能で重複しないよう適切に割り付けても良い。いずれにせよ、ネットワーク管理装置１０が割り当てるべきユーザとＶＬＡＮＩＤと各中継ノードのポートとの対応が認識できるものとする。

例えば、図５で記述した情報を持つユーザ情報に割り付けるＶＬＡＮＩＤがＡであり、図５を元に経路設計を行った結果が図７のようであったとする。図７の意味するところは、ノード１についてポート１がＶＬＡＮＩＤＡのフレームを転送可能で、その出力レー
ト（通信帯域）が最大２０Ｍｂｐｓであるということである。この場合、ノード１は、ユーザ拠点１００からＶＬＡＮＩＤＡのタグを持ったイーサフレームが、２０Ｍｂｐｓを
超える速度（例えば２５Ｍｂｐｓ）で到着した場合、超過分である５Ｍｂｐｓは出力ポート１の出力キューで廃棄する。また、ノード１のポート２についての記載は無いが、これは、ＶＬＡＮＩＤＡのフレームのポート２への転送を不可とすることを意味する。

ネットワーク管理装置１０のネットワーク設定部は、この経路設計結果を各中継ノードＮに送信して設定を行わせる。この設定は、例えば、設定用ネットワーク４を介して設定対象の中継ノードＮへｔｅｌｎｅｔでリモートログインし、設定用コマンド（設定情報）を入力することで行う。具体的にどういうコマンドを用いるかは、中継ノードＮの仕様に依存するが、図７の意味するところが設定されれば如何なるものでもよい。このように設定された結果、ネットワークにはこのユーザのトラヒック（ＶＬＡＮＩＤ１のフレーム）に対し図８のような設定が為されることになる。図８において太線で示した部分がブロードキャストドメインである。また、図８に示すように本実施形態のネットワーク管理装置１０では、任意のユーザ拠点１００から他のユーザ拠点１００までがツリー状の経路とな
るように設計する。

以上のように本実施形態によれば、ユーザトラヒックを、効率よく収容するための経路および割り当て帯域を決定し、且つその結果を自動でネットワーク装置に設定することが可能となり、オペレーションの手間・所要時間を抑えることが出来る。

〈実施形態２〉
本実施形態は、前述の実施形態１と比較して経路設計部による通信帯域の割り当て方法が異なっており、その他の構成は同じである。このため前述の実施形態１と同一の構成については再度の説明を省略する。

本実施形態の経路設計部は、前述と同様に全ユーザ拠点を結ぶ経路を求め、この経路上の各中継ノードについて、任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とするように通信帯域を割り当てる。

ここで割当帯域とは、その両端の出力ポートに割り当てられる出力レートのことを指す。リンク割当帯域を決め、これに倣い、その両端ポートの出力レートを決める。
リンク帯域の割り当ては、以下の方法に従えば実現できる。

このとき経路設計部は、各中継ノードＮに対し、処理フラグを定義する。例えば各中継ノードＮと対応する処理フラグをメモリに記憶し、経路設計を開始する際に初期して該フラグの値を０、即ち未処理の状態とし、割当帯域を決定した中継ノードＮと対応するフラグの値を１、即ち処理済の状態とする。この処理フラグに基づき、以下の３つのステップを行う。なお、このアルゴリズムは、経路が与えられた後に行うものであるので、トラヒックを中継しないポート（リンク）については無視している。

（ステップ１１）
処理フラグ０の中継ノードＮであって、帯域が未設定のリンクが少ない中継ノードＮ（未設定のリンクが１本のノード）を一つ選択する。

（ステップ１２）
この選択した中継ノードＮについて、接続しているリンクの帯域（即ち、該リンクを介してトラヒックを中継するポートの帯域、以下単にリンクの帯域とも称する）を、そのノードに接続されている他のリンクに割り当てられている帯域の総和（＝α）以下とする。具体的には、以下の（ア）〜（ウ）に従う。

（ア）帯域が未設定のリンクはαを設定する。
（イ）帯域が既に設定されているリンクで、それがαよりも大きい場合はαを設定する。この場合、その中継リンクより向こう側は再計算の必要が生じるため、対向ノードの処理フラグを０にする。
（ウ）帯域が既に設定されているリンクで、それがα以下である場合にはそのままにしておく。
全てのリンクに処理を終えたら、その中継ノードＮの処理フラグを１にする。

（ステップ１３）
処理フラグ０の中継ノードＮがなくなるまでステップ１１からステップ１２を繰り返す。

以下に、その具体例を示す。図９（Ａ）において、三角１０１〜１０３はユーザ拠点であり、四角Ｎ１〜Ｎ３が、中継ネットワーク内でこのユーザトラヒック（ＶＬＡＮ）が転送される経路として割り当てられた中継ノードＮであるとする。このとき拠点１０１は５０Ｍを、拠点１０２は２０Ｍ、拠点１０３は２０Ｍをアクセスリンク帯域として契約したとする。ここでは、リンク１−３、リンク２−３を介してトラヒックを中継するポートが帯域割り当ての対象である。なお、上記アルゴリズムで登場する処理フラグの状態は、中継ノードに×印をつけることで表現する。×印がある中継ノードＮは処理フラグ１、×印が無いノードは処理フラグ０である。

まず、処理フラグ０で帯域未設定の中継リンク数が最小の中継ノードを選択する（ステップ１１）。ここでは中継ノードＮ１とＮ２が候補となる。このうちまず中継ノードＮ１を選択し（例えば複数の候補がある場合には、ＩＤの小さい順に一つを選択する）、リンク１−３に他のリンクの総和である５０Ｍを設定し、中継ノードＮ１の処理フラグを１とする（ステップ１２）。そしてまだ処理フラグ０のノードがあるのでステップ１１に戻る（ステップ１３）。

次に中継ノードＮ２が選ばれ（ステップ１１）、リンク２−３に他リンクの帯域の総和である２０Ｍを設定し、ノードＮ２の処理フラグを１とする（ステップ１２）。ここまでの様子を図９（Ｂ）に示す。

そして処理フラグ０の中継ノードＮがあるので、ステップ１１に戻り（ステップ１３）、中継ノードＮ３が選ばれる（ステップ１１）。条件ウによりリンク２−３はそのままでよいが、リンク１−３は他のリンク帯域の総和以上（５０Ｍ＞２０Ｍ＋２０Ｍ）であるため、条件イによりリンク１−３に２０Ｍ＋２０Ｍ＝４０Ｍを設定し、対向ノードである中継ノードＮ１の処理フラグを０にすると共に中継ノードＮ３の処理フラグを１にする（ステップ１２）。ここまでの様子を図９（Ｃ）に示す。

処理フラグ０の中継ノードＮがあるので、ステップ１１に戻り（ステップ１３）、中継ノードＮ１が選ばれる（ステップ１１）。条件ウにより、このノードはこのままでよく、処理フラグを１にする。

処理フラグ０のノードが無くなったので、処理を終了する（ステップ１３）。結果、図９（Ｄ）のようになる。
このように本実施形態によれば、中継ネットワークの各ノードからトラヒックを送出する際に、その送出リンクの対向ノードより向こう側の許容トラヒック量を超える分を廃棄するような帯域割り当てが可能となり、中継ネットワークでの無駄なトラヒック転送を回避できる（ユーザが実質的に流せるだけのトラヒック分しか割り当てない）。

例：図１０のリンク１−２（ノードＮ１〜Ｎ２間のリンク）では、ノード１で４０Ｍ＋３０Ｍ＝７０Ｍが中継可能、ノードＮ２で１０Ｍ＋１０Ｍ＝２０Ｍが中継可能であるため、小さい方の２０Ｍを割り当て帯域とする。

従来、中継ネットワーク内の帯域は、一般的に余裕を持って割り当てていたので、ユーザ拠点１０１からユーザ拠点１０４へ４０Ｍｂｐｓトラヒックが送られた場合、中継ノードＮ６で３０Ｍｂｐｓのトラヒックを廃棄し、１０Ｍｂｐｓだけユーザ拠点１０４へ到達することになる。従って、中継ネットワークは、３０Ｍｂｐｓの無駄なトラヒックを中継したことになり、ネットワークの利用効率を低下させる要因となっていた。

これに対し本実施形態のように経路設計した中継ネットワークでは、各リンクの帯域がユーザ情報（アクセスリンクの帯域）に基づいて設定されているので、ユーザ拠点１０１
からユーザ拠点１０４へ４０Ｍｂｐｓトラヒックが送られた場合、中継ノードＮ１で２０Ｍｂｐｓのトラヒックを廃棄し、中継ノードＮ６で１０Ｍｂｐｓのトラヒックを廃棄し、１０Ｍｂｐｓがユーザ拠点１０４へ到達するので、無駄なトラヒックが早い段階（上流側の中継ノードＮ）で廃棄されるので、ネットワークを効率良く利用できる。

〈実施形態３〉
本実施形態は、前述の実施形態１と比較して経路設計部による通信経路の決定方法が異なっており、その他の構成は同じである。このため前述の実施形態２と同一の構成については再度の説明を省略する。

前述の実施形態２の帯域割り当て方法を用いた場合、消費帯域最小となる経路は、必ず、中継ネットワーク内のノードのうちいずれか一つを起点（根）とした最短路ツリー上に存在する。
そこで、以下の方法を用いることで、上記帯域割り当てを行った場合に少ない計算規模で消費帯域が最小となる経路を決定可能である。

即ちネットワーク管理装置１０の経路設定部は、各中継ノードを起点とする最短路ツリーを求め、該ツリーからトラヒックの中継に無関係なリンクおよびノードを取り除いた経路を得て、得られた経路（最短路ツリー）のそれぞれに対し、帯域設計を試行し、その結果消費帯域が最小であるものを選択する。

具体的には、以下の方法により実現される。
本例では、図１３に示すネットワークに対し、図１１に示すユーザ情報を有するユーザのトラヒックを収容する経路の設計を行うものとする。このとき、経路設計部は、図１４に示すトポロジ情報をもとに、中継ネットワークのノードＮ１〜Ｎ６を起点（根）ノードＮｒとした最短路ツリーを、合計６つ計算する。最短路ツリーは、例えば、各リンクのコストを１として根ノードＮｒからのコストを最小にするツリーを求める計算アルゴリズムを用いれば求めることができ、例えばダイクストラアルゴリズムが有名である。例えば各リンクのコストを１とすれば、根ノードＮｒからの最短ホップ経路を求めることになる。ここで、ノードＸを起点とした最短路ツリーをツリーＸと呼ぶことにする。図１７はダイクストラアルゴリズムの処理結果の例としてツリー１について示したものである。親ノードとは、その中継ノードＮから根ノードＮｒまで最小コスト経路（この場合最短ホップ経路になる）で到達しようとしたときの一つ根ノード側のノードである。ノード１について親ノードが「--」となっているが、これは自身が根ノードＮｒであることを示す。実際には、例えば0など、根ノードＮｒを表す数値を格納することになる。これらを絵で表した
ものが図１２である。斜線を入れたノードは、各ツリーの起点ノードＮｒである。つぎに、経路設計部は、ユーザトラヒック収容に無関係なノードを除外するため、以下の処理を行う。

（ステップ２１）
まず、当該ユーザのユーザ情報に基づいてユーザトラヒックを中継しない中継ノードＮを特定する条件（例えば当該ユーザのユーザ拠点と接続する拠点収容ノードでなく且つポート数が一つのノードであること）を定義する。

（ステップ２２）
次に、図１１の拠点収容ノード情報を参照し、各ツリーから前記条件に該当する中継ノード、即ちユーザトラヒックの中継に無関係なノードがあるか否かを判定する。この条件に該当する中継ノードが無ければ、無関係なノードが無いので処理を終了する。また、条件に該当する中継ノードがあれば、次のステップ２２に移行する。

（ステップ２２）
上記条件に該当した中継ノードＮ及びこの中継ノードと接続したリンクを設計対象のトポロジ情報から除外する。

（ステップ２３）
そしてステップ２１に戻り、前記条件に該当する中継ノードＮが無くなるまで、繰り返す。

この処理の結果、図１５に示すように、無関係な中継ノードＮ及びリンクを除外したツリー状経路が得られる。この経路についてそれぞれ帯域割り当てを試行する。その結果を図１６に示した。各ツリーの消費帯域を比較すると、ツリー１が７０Ｍｂｐｓ、ツリー２が７０Ｍｂｐｓ、ツリー３が８０Ｍｂｐｓ、ツリー４が８０Ｍｂｐｓ、ツリー５が１００Ｍｂｐｓ、ツリー６が１５０Ｍｂｐｓとなり、この場合ツリー１か２が消費帯域最小ツリーとして選ばれる。

このように、本実施形態によれば、中継に無関係な中継ノードを除外して帯域の割り当てを求めるので、ネットワークに含まれるノードを総当りして求めるよりも計算規模が抑えられ、（最短路ツリー計算）×（中継ノード数）程度の計算規模で容易に消費帯域最小となる経路を決定することが出来る。

〈実施形態４〉
本実施形態は、前述の実施形態３と比較して経路設計部による通信経路の決定方法が異なっており、その他の構成は同じである。このため前述の実施形態３と同一の構成については再度の説明を省略する。

実施形態３でも記述したように、消費帯域最小となる経路は、必ず、中継ネットワーク内のノードのうちいずれか一つを起点（根）とした最短路ツリー上に存在する。そこで、所望の経路を含む最短路ツリーの根ノードを、効率よく発見することが本実施形態の特徴である。

具体的には、以下の方法により実施する。
ネットワーク管理装置１０の経路設計部は、各中継ノードＮについて以下の評価式で評価し、この表価値が最小となる中継ノードＮを選択する。
ノードaのトータル評価値
＝Σ_{i∈｛全ての拠点収容ノード｝}｛ツリーiにおけるノードaの評価値｝

ツリーiにおけるノードa評価値
＝（拠点収容ノードi〜ノードa間の最短ホップ数）×（拠点収容ノードiに繋が
るアクセスリンク契約帯域）

本例では、図１３に示すネットワークに対し、図１１に示すユーザ情報を有するユーザのトラヒックを収容する経路の設計を行うものとする。このとき、経路設計部は、図１４に示すトポロジ情報をもとに、中継ネットワークに含まれる中継ノードＮを起点（根）ノードＮｒとした最短路ツリーを計算する。なお、本実施形態では、計算規模の抑制のため、拠点収容ノードを根ノードＮｒとした最短路ツリーを求める。即ち、中継ノードＮ１，Ｎ３，Ｎ４，Ｎ６が根ノードの対象となり、ツリー１，３，４，６を求める。最短路ツリーを求める手法は前述と同様でよい。

そして、各ツリーにおけるノードaの評価値を求める。これはダイクストラアルゴリズ
ムの処理結果を用いれば容易に求められる。この様子を示したものが図１８である。図１
８のツリー１において、ノードＮ２に「４０×１」と付されているが、これがツリー１における中継ノードＮ２の評価値であり、（中継ノードＮ１に繋がるアクセスリンクの契約帯域＝４０Ｍｂｐｓ）×（ノードＮ１からのホップ数＝１）を表している。評価値計算に用いる契約帯域の単位は、ｋｂｐｓでもＭｂｐｓでも、適宜変更して構わないが、同じユーザに対する設計中は全てのツリーで同じ単位で取り扱う。この場合はＭｂｐｓで取り扱っている。

各ノードＮ１，Ｎ３，Ｎ４，Ｎ６において、全ツリー１，３，４，６の評価値が求まったら、各ノードＮ１，Ｎ３，Ｎ４，Ｎ６のトータル評価値を求める。これは、それぞれのノードで全ツリーでの評価値の和をとることで求められる。中継ノードＮ２であれば、ツリー１における評価値４０と、ツリー３における評価値３０と、ツリー４における評価値６０と、ツリー６における評価値１０の和である１２０が、求めるトータル評価値となる。全ノードＮ１，Ｎ３，Ｎ４，Ｎ６のトータル評価値が求まったら、これが最小であるノードをひとつ選ぶ。この場合、経路設計部は、中継ノードＮ１の７０が最小であるので中継ノードＮ１を選択する。選択された中継ノードＮ１が、当該ユーザのトラヒックを収容する経路としての最短路ツリーの根ノードＮｒとなる。

そして経路設計部は、選択したノードを根ノードＮｒとして各拠点収容ノードとを最短ホップ経路で接続する経路（最短ホップ経路）を決定する。選ばれたノードと各拠点収容ノードとを最短ホップ経路は、改めて算出してもよいし、たとえば各ツリー算出時のダイクストラ計算結果をこの時点まで保持しておき、これを流用して求めても良い。後者の場合、たとえばノード１〜６間の経路は、ツリー６からノード１を探索し、その親ノードＮ２、さらにそのノードＮ２の親ノードＮ６を順に調べることで得られる。これらの動作を示したものが図１９である。図１９の設計結果は、例えば図３３のように示される。

この方法は、計算規模が（最短路ツリー計算）×（拠点数）となる。すなわち、設計対象が（拠点数）＜（中継ノード数）となる環境においては、実施形態３の方法よりもさらに大きな効果を発揮する。

例えば、拠点数１０のユーザに対し、ノード数１００００で経路設計を行った場合、全ての中継ノードについて最短路ツリーを求めて経路設計を行った場合５時間程度係るのに対し、本実施形態の方法で経路設計を行う場合、１分程度の計算時間となる。

〈実施形態５〉
前述の実施形態３で示したように、ユーザ拠点間の通信を中継しない中継ノードを除外した経路について、前述の実施形態２に示したように、各中継ノードの任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とするように通信帯域を割り当てても良い。

これにより、トラヒックの中継に無関係な中継ノードを除外して帯域の割り当てを行えるので、更に容易な処理で経路設計を行うことができる。

〈実施形態６〉
前述の実施形態４で示したように、評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求め、該最短ホップ経路について、前述の実施形態２に示したように、各中継ノードの任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とするように通信帯域を割り当てても良い。

これにより、最短ホップ経路についてのみ帯域の割り当てを行えば良く、容易な処理で
経路設計を行うことができる。

〈実施形態７〉
本実施形態は、前述の実施形態４と比較して、あらかじめ拠点収容ノードとなりうるノードを起点としたツリー状の最短経路を求めておく点が異なっており、その他の構成は同じである。このため前述の実施形態４と同一の構成については再度の説明を省略する。

前述の実施形態４では、拠点収容ノードを起点とした最短路ツリーを求めることを基本とした設計方法である。設計時に参照するものは設計対象ユーザ情報、トポロジ情報である。本実施形態は、この最短路ツリーを予め求めておき、経路設計時間を短縮することを目的とする。

そこで本実施形態では、経路設計部が、拠点収容ノードとなりうる中継ノードＮ全てについて、この中継ノードを起点（根）とした最短路ツリーをあらかじめ求めて、その結果を記憶部１３に記憶（保持）しておく。

拠点収容ノードになりうる中継ノードＮとは、具体的には、接続関係的に中継ネットワークの端に位置するノードである。（中継ネットワークのノードは、一般に、内部でトラヒック転送を行うためだけに配備されるものと、トラヒック転送だけでなくユーザ拠点が接続されることを目的として配備されるものとに分けて捉えることが出来る場合が多く、本手法では後者を拠点収容ノードになりうるノードと捉えている。）

トポロジ情報を取得した場合、ユーザ情報が与えられる前に、あらかじめ、拠点収容ノードとなりうる中継ノードＮを抽出し、これらを起点とする最短路ツリーを作成してこの情報を保持しておけばよい。ここで拠点収容ノードとなりうる中継ノードＮを抽出するためには、例えば、取得したトポロジ情報に、オペレータが拠点収容ノードとなりうるノードを手動で入力することや、既に他のユーザの拠点を収容しているノードを識別して自動で入力するなどにより、これを指定し、ユーザ情報を受け付けたときに拠点収容ノードとなりうるノードか否かの要素を追加したトポロジ情報を持つようにすればよい。例えば図１３に示すネットワークについて、前述のトポロジ情報（図１４）に、拠点収容ノードとなりうるノードか否かの要素（拠点収容ノード候補）を加え、図２０に示すようにトポロジ情報データベースに記憶する。図２０において拠点収容ノード候補の項が１のノードが拠点収容ノードとなりうるノード、０のノードがそうではないノードである。

このトポロジ情報が与えられると、経路設計部は、拠点収容ノードとなりうる中継ノードＮを抽出し、図２１に示すようなツリーテーブルを作成し、記憶部１３に記憶させる。

そして、ユーザ情報を受け付けて経路設計を行う際、経路設計部は、最短路ツリー計算を行うのではなく、このツリーテーブルから該当するツリーを検索して得るようにする。
この方法により、一度ツリーテーブルを作成しておけば、ユーザ網収容設計ごとに毎回最短路ツリー計算を行う手間が短縮できるため、ユーザ個々の設計時間を抑えることが可能になる。

〈実施形態８〉
本実施形態は、前述の実施形態３又は４と比較して、あらかじめ経路設計に無関係な中継ノード及びリンクを設計対象のトポロジ情報から除外する点が異なっており、その他の構成は同じである。このため前述の実施形態３又は４と同一の構成については再度の説明を省略する。

本実施形態では、ユーザ情報が与えられたのち、トポロジ情報から経路設計に無関係な
ノードおよびリンクをあらかじめ設計対象から除くことで、経路計算の手間を省き、設計時間を抑えることを目的とする。

この経路設計に無関係なノードおよびリンクとは、ユーザ拠点間の通信を中継しないノード及びリンクであり、具体的には、「ユーザ拠点収容ノードではない、且つ、ポート数が１である中継ノード及びこのノードと接続したリンク」を指す。本形態ではこれを削除条件と呼ぶことにする。削除条件を満たす中継ノードＮが検出されれば、その中継ノードＮおよびそのノードＮと繋がるリンク３全てを設計対象から削除する。リンク３を削除する場合は、対向ノードの該ポートデータも削除する。ただし、このノードＮ及びリンク３の情報をトポロジ情報データベースからから完全に削除してしまうと、後々の設計に支障をきたすので、経路設計部が経路設計時に読み出したトポロジ情報からこのノードＮ及びリンク３の情報を除外して用いる。削除は、この読み出した情報からの削除とする。

図２２のようなネットワーク（ＮＷ）について、図２３に示すトポロジ情報を取得し、図５に示すユーザ情報が与えられた場合、経路設計部は、トポロジ情報をメモリ上に読み出した後、これら情報をもとに、上記削除条件を満たす中継ノードをトポロジ情報から検索する。この場合、中継ノードＮ７がこれに該当する。経路設計部は、読み出したトポロジ情報から中継ノードＮ７およびリンク５−７を削除する。削除後、トポロジが若干変わることになるので、経路設計部は、再び削除条件を満たすノードの有無をチェックする。この場合、削除後のトポロジ情報において、中継ノードＮ５が新たに削除対象として検出されるため、ノードＮ５とリンク５−２を削除する。これら処理によって、削除対象トポロジ情報は図２４に示すものになる。

上記処理を施した後、経路設計を行うことで、例えばダイクストラ計算の際にかかる手間が大きく短縮されるため、ユーザ個々にかかる設計時間が大幅に削減できる。

〈実施形態９〉
本実施形態は、前述の実施形態８と比較して、サブドメイン毎に経路設計に無関係な中継ノード及びリンクを設計対象のトポロジ情報から除外する点が異なっており、その他の構成は同じである。このため前述の実施形態８と同一の構成については再度の説明を省略する。

管理の簡単化のため、中継ネットワークは、階層化されて扱われていることがある。図２５がその例である。ここでは、点線が囲まれたノードが一つのサブドメインとして扱われる。中継ノードＮ１，Ｎ４がサブドメイン１、中継ノードＮ２がサブドメイン２、中継ノードＮ３，Ｎ６がサブドメイン３、中継ノードＮ５、Ｎ７，Ｎ８がサブドメイン４である。例えばトポロジ情報にサブドメイン属性を追加することでこれを取り扱う。図２６がその例である。本実施形態では、ユーザ拠点に無関係なノードおよびリンクを、前述の実施形態８と同様の削除条件で削除する際、サブドメインごとに設計対象から削除しようというものである。

サブドメインごと削除するためには、例えば図２７に示すような、拠点収容ノードを含むドメインであるか否かをあらわす要素をもったサブドメイン情報があればよい。ここでは、拠点収容候補として１が入ったドメインは拠点収容ノード候補（拠点収容ノードとなりうるノード）を含むドメイン、０はそうでないドメインである。このサブドメイン情報は、あらかじめトポロジ情報データベースにオペレータが入力しておき、例えば、図２６のようなトポロジ情報を与えた後、このトポロジ情報に含まれる所属サブドメインＩＤと拠点収容候補とを対応付けたテーブルを作成すればよい。

図２６および図２７の情報がそろったのち、ユーザ収容網設計開始の際に、ノードおよ
びリンクの削除処理を開始する。ここで、図５のようなユーザ情報が与えられたとする。経路設計部は、図２７で拠点収容候補となっている（１が入力されている）サブドメインについて、削除条件（拠点収容ノードを含まないこと）に該当するか、即ち、図５のユーザ拠点収容ノードをひとつも含まないサブドメインが無いか検索を行う。検索対象となるサブドメインは１，３，４であるが、この場合、サブドメイン４に属するノードＮ５，Ｎ７，Ｎ８は、いずれもユーザ情報の拠点収容ノードに含まれないため、サブドメイン４が検出される。検出されたサブドメイン４に属するノードおよびリンクは、設計対象から削除する。具体的には、中継ノードＮ５，Ｎ７，Ｎ８と、リンク５−７、５−８、７−８、２−５を削除する。

削除後、トポロジ情報は図２８のようになる。処理後のトポロジ情報を用いてユーザ収容網設計を行えば、経路設計に要する手間が短縮でき、所要時間の大幅に削減できる。

〈実施形態１０〉
本実施形態は、前述の実施形態１から９と比較して、別経路の情報を保持しておく点が異なっており、その他の構成は同じである。このため前述の実施形態１から９と同一の構成については再度の説明を省略する。

上記経路設計では、最短経路ツリー計算を行うことが基本となっている。最短経路ツリーアルゴリズムとして各リンクコストを１としたダイクストラアルゴリズムを用いている。ダイクストラアルゴリズムでは、根ノードＮｒからのコストが最小のツリーを一意に決定する。たとえば、図１３のようなネットワークで図１４のようなトポロジ情報が与えられた場合、ツリー１を計算すると図２９（Ａ）のような結果が得られる。しかし、実際には、図２９（Ｂ）のようなツリーも存在し、いずれも、各ノードから根ノードまでのコストは同じである。この場合、ダイクストラアルゴリズムが中継ノードＮ６について処理する際、根ノードまで至るコストが２の親ノードとして中継ノードＮ２と中継ノードＮ５が候補に挙がる。どちらを選択するかは、任意に設定できるが、たとえば、同じコスト値の親ノード候補が複数得られた場合はノードIDの値の小さいほうを採用する、などのルールを予め設定しておき、この場合はノードＮ２を親ノードとして採用する。

このように同じコスト値を持つ親ノードが２つ得られた場合は、親ノードとして採用するのは１つだけであるが、もう一方の候補も、代替親ノードとしてそのノードIDを保持するようにする。３つ以上得られた場合は、採用された一つを除いた残りの親ノード候補の中から一つ適当に選択する。たとえばノードIDが最小のものを選択する。

図２９（Ｃ）は、ダイクストラアルゴリズムの処理結果に、代替親ノードの情報を追加した場合のツリー１の処理結果である。代替親ノードがもし得られていれば、代替親ノード情報にそのノードIDを保持する。この場合、中継ノードＮ６に対し親ノードはＮ２であり、同じコスト２で根ノードＮｒに到達できる親ノード候補として中継ノードＮ５も存在するため、これを代替親ノードとして保持する。中継ノードＮ１−Ｎ５については、代替親ノード候補が存在しないため、代替親ノード情報として、存在しないことを表す値、たとえば０を保持する。

ダイクストラアルゴリズム処理を行う際に、上記のような代替親ノード情報も得るようにすることで、設計結果として得られた経路でユーザトラヒックを収容しようとした場合に、該経路上の残帯域の不足などの理由により特定の中継ノードＮで収容が不可能となり、経路の変更が必要となった場合に、該中継ノードＮを含むツリーの代替親ノード情報を参照し、そのリンクを迂回する代替親ノードをもつものが存在するかどうかを検索し、もし存在すれば、親ノードをこの代替親ノードに代え、同じ消費帯域となる別の経路に変更させる。これにより、初めから設計をやり直す必要が無く、迅速に経路設計を行うことが
可能になる。

ネットワーク管理装置１０が図１３のネットワークに対し図３１のトポロジ情報を持ち、図１１のようなユーザ情報を受け付けたとする。ここで、経路設計部は、例えば実施形態４に記載の方法で経路設計を行うものとする。ただし、各ツリーにおける評価値を得る際、上記のようにダイクストラアルゴリズムの計算過程で、代替親ノード情報も得るものとする。その結果が図３０である。このとき前述と同様に、中継ノードＮ１がトータル評価値最小のノードとして選択され、図１９に示すような帯域割り当てがなされたとする。ここで、図３１に示されるように、リンク２−６は帯域（ここで示される帯域は、物理帯域でも残帯域でもよい）が５Ｍｂｐｓしか無く、リンク２−６で１０Ｍｂｐｓの割り当てを要求するこのユーザトラヒックを収容できないと判断する。この判断は、経路設計部が行っても良いし、オペレータが行って入力しても良い。

このトラヒックを収容できないと判断した場合、経路設計部は、リンク２−６を迂回し、且つ同じ消費帯域となる別の経路が存在しないか、図３０のツリー情報を用いてチェックを行う。この場合、得られている経路は中継ノードＮ１を根ノードＮｒとしたツリーの一部となっているので、ツリー１のテーブルを参照し、リンク２−６の下流に位置する中継ノードＮ６について代替親ノード情報の有無を調べる。この結果、経路設計部は、中継ノードＮ６について、同じコストで中継ノードＮ１に到達できる代替親ノード情報としてエントリされている中継ノードＮ５を選択し、中継ノードＮ５を経由して中継ノードＮ１に至る経路を求める。従って中継ノードＮ５の親ノード情報とあわせて、中継ノードＮ６〜中継ノードＮ１の経路としてリンク５−６、リンク１−５を選択し、現在の経路情報からリンク２−６を削除し、新しい経路リンク５−６、ノードＮ５、リンク１−５、およびそのポートについての情報に代えることにより、新しい経路として図３２のような経路、即ち同じ消費帯域となる別の経路を得ることができる。図３２の設計結果は、たとえば図３４のように示される。

〈実施形態１１〉
本実施形態は、前述の実施形態１０と比較して、経路設計完了後も、その設計に関する情報を保持しておく点が異なっており、その他の構成は同じである。このため前述の実施形態１０と同一の構成については再度の説明を省略する。

本実施形態では、経路設計部が、経路設計を完了した際、そのユーザの設計に関する情報としてツリー情報を記憶部１３に記憶（保持）しておくことで、設計済みユーザの経路を、後から迅速に変更することを可能にする。保持しておくツリー情報とは、前述の実施形態１０と同様、代替親ノード情報を含むものである。

ネットワーク管理装置１０は、図１３のようなネットワークに対し、図３５のようなトポロジ情報を保持しているとする。本形態では、図３７（Ａ）のようなユーザ１のユーザ情報を受け付け、経路設計部が、前述の実施形態４と同様に設計を行い、図３８（Ａ）のような設計結果を得たとする。なお、ユーザ１に割り当てるＶＬＡＮＩＤがＡであるとする。このとき、実施形態１０と同様にダイクストラアルゴリズム計算の際に代替親ノード情報も得るようにし、図３８（Ｂ）に示すようなツリー情報を得る。ここでは、ツリー１に関する情報のみ記載している。

経路設計部は、図３８（Ａ）の設計結果と図３８（Ｂ）のツリー情報をユーザ１の設計関連情報として保持する。たとえば、ユーザ情報管理用のデータベースを記憶部１３に構築してここに保持していても良いし、メモリ上で記憶していても良い。

ユーザ１を収容したことでトポロジ情報が図３６のように変更されたとする。図３６は
、図３５のトポロジ情報に比べ、ユーザ１に割り当てられた帯域の分が減算されている。
さらに図３７（Ｂ）のようなユーザ２のユーザ情報が受け付けられた場合とする。経路設計部は、ユーザ１のときと同様に、図３８（Ｃ），図３８（Ｄ）のような情報を得る。なお、ユーザ２に割り当てられるＶＬＡＮＩＤがＢであるとする。このとき、図３６から、ユーザ２に割り当てられるはずの帯域が、リンク２−６において不足していることがわかる。

ここで、ユーザ２がこの経路でなければならない場合、或いはこのように競合した際に最新の経路を優先する等のルールを設定している場合、経路設計部はユーザ１の経路の変更を行う。まず経路設計部は、収容済みユーザのなかから、リンク２−６を利用するユーザを検索し、そのユーザがいた場合、該ユーザにそのリンク２−６を迂回できる経路で且つ同じ消費帯域となる経路が存在しないかのチェックを行う。

この場合、図３８（Ａ）の情報より、ユーザ１がリンク２−６を利用する収容済みユーザとして検出される。そして図３８（Ｂ）のツリー情報から、前述の実施形態１０と同様に、リンク１−５、中継ノードＮ５、リンク５−６の迂回経路があることを得て、ユーザ１の経路を図３９のように変更する。このように同じ消費帯域で別の経路が存在するユーザ１を、いま得た新しい経路に収容替えすることで、トポロジ情報は図４０のようになり、図３６のときには不足していたリンク２−６の帯域も、ユーザ２を収容するに十分足るものとなり、ユーザ２が無事収容できるようになる。

〈その他の実施形態〉
本発明は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。

例えば、以下に付記した構成であっても上述の実施形態と同様の効果が得られる。また、これらの構成要素は可能な限り組み合わせることができる。

（付記１）複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置にて、前記ユーザ拠点間の通信経路を設計する経路設計方法であって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を含む経路設計方法。

（付記２）前記経路設計を行うステップにおいて、全ユーザ拠点を結ぶ経路上の各中継ノードについて任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とする付記１に記載の経路設計方法。

（付記３）前記経路設計を行うステップにおいて、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外して通信経路を求める付記１に記載の経路設計方法。

（付記４）前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求める付記１に記載の経路設計方法。

（付記５）前記経路設計を行うステップにおいて、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外し、この除外後のツリー状の経路について各リンクに割り当てられた帯域の総和が最小となるように帯域を割り当てる付記２に記載の経路設計方法。

（付記６）前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求め、該最短ホップ経路について通信帯域の割り当てを行う付記２に記載の経路設計方法。

（付記７）拠点収容ノードになりうる中継ノードを起点としたツリー状の経路の情報を予め求めて記憶しておき、経路設計を行う際に該ツリー状の経路の情報を読み出して利用する付記４に記載の経路設計方法。

（付記８）ポート数１で且つユーザ拠点収容ノードではない中継ノードおよびそれに接続するリンク全てを設計対象から除外したのちに経路設計を行う付記３又は４に記載の経路設計方法。

（付記９）前記ネットワークがサブドメインに分割されて管理されている場合に、前記アクセスリンクを介してユーザ拠点と接続する中継ノードを１つも含まないサブドメインに所属するノードおよびこれに接続されるリンク全てを設計対象から除外したのちに経路設計を行う付記３又は４に記載の経路設計方法。

（付記１０）ツリー状の経路を求めた際に、ある中継ノードから同じ中継数で起点ノードに到達できる別経路が求められた場合、その別経路の情報を、当該ノードに属する情報として保持しておく付記１から９の何れか１項に記載の経路設計方法。

（付記１１）前記経路設計の完了後、前記経路設計の結果及び前記別経路の情報を保持しておく付記１０に記載の経路設計方法。

（付記１２）前記経路設計の結果に基づき、各中継ノードについて前記ユーザ拠点間の通信を中継するポートを特定する情報及び該通信の帯域を示す情報を含む設定情報をそれぞれの中継ノードに送信し、該中継ノードに経路を設定させるステップを更に含む付記１から１１の何れかに記載の経路設計方法。

（付記１３）複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置にて運用され、前記ユーザ拠点間の通信経路を設計するプログラムであって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を前記ネットワーク管理装置に行わせる経路設計プログラム。

（付記１４）複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置であって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付ける入力部と、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するトポロジ取得部と、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う経路設計部と、
前記経路設計結果を出力する経路出力部と、
を含むネットワーク管理装置。

（付記１５）前記経路設計部が、全ユーザ拠点を結ぶ経路上の各中継ノードについて任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とする付記１４に記載のネットワーク管理装置。

（付記１６）前記経路設計部が、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外して通信経路を求める付記１４に記載のネットワーク管理装置。

（付記１７）前記経路設計部が、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求める付記１４に記載のネットワーク管理装置。

（付記１８）前記経路設計部が、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外し、この除外後のツリー状の経路について各リンクに割り当てられた帯域の総和が最小となるように帯域を割り当てる付記１５に記載のネットワーク管理装置。

（付記１９）前記経路設計部が、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値
を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最短ホップ数で接続した最短ホップ経路を求め、該最短ホップ経路について通信帯域の割り当てを行う付記１５に記載のネットワーク管理装置。

（付記２０）前記経路設計部が、拠点収容ノードになりうる中継ノードを起点としたツリー状の経路の情報を予め求めて記憶しておき、経路設計を行う際に該ツリー状の経路の情報を読み出して利用する付記１７に記載のネットワーク管理装置。

（付記２１）前記経路設計部が、ポート数１で且つユーザ拠点収容ノードではない中継ノードおよびそれに接続するリンク全てを設計対象から除外したのちに経路設計を行う付記１６又は１７に記載のネットワーク管理装置。

（付記２２）前記ネットワークがサブドメインに分割されて管理されている場合に、前記経路設計部が、前記アクセスリンクを介してユーザ拠点と接続する中継ノードを１つも含まないサブドメインに所属するノードおよびこれに接続されるリンク全てを設計対象から除外したのちに経路設計を行う付記１６又は１７に記載のネットワーク管理装置。

（付記２３）前記経路設計部が、ツリー状の経路を求めた際に、ある中継ノードから同じ中継数で起点ノードに到達できる別経路が求められた場合、その別経路の情報を、当該ノードに属する情報として保持しておく付記１４から２２の何れか１項に記載のネットワーク管理装置。

（付記２４）前記経路設計部が、前記経路設計の完了後、前記経路設計の結果及び前記別経路の情報を保持しておく付記２３に記載のネットワーク管理装置。

（付記２５）前記経路設計の結果に基づき、各中継ノードについて前記ユーザ拠点間の通信を中継するポートを特定する情報及び該通信の帯域を示す情報を含む設定情報をそれぞれの中継ノードに送信し、該中継ノードに経路を設定させるネットワーク設定部を備える付記１４から２４の何れか１項に記載のネットワーク管理装置。

（付記２６）複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワーク及び該中継ノードと接続するネットワーク管理装置とを備えるネットワークシステムであって、
前記ネットワーク管理装置が、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付ける入力部と、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するトポロジ取得部と、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う経路設計部と、
前記経路設計結果を出力する経路出力部と
を備え、
前記中継ノードが、
前記通信のトラヒックを受け付ける入力部と、
該トラヒックを前記ポートを介して次のノードに出力する出力部と、
前記ネットワーク管理装置から設定情報を受信する設定取得部と、
この設定情報に基づいて前記出力部のポートの設定を行う設定部と、
を備えたネットワークシステム。

（付記２７）複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワーク及び該中継ノードと接続するネットワーク管理装置とを備えるネットワークシステムにて運用される方法であって、
前記ネットワーク管理装置が、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を行い、
前記中継ノードが、
前記ネットワーク管理装置から設定情報を受信するステップと、
この設定情報に基づいて前記出力部のポートの設定を行うステップと、
を行うネットワーク管理方法。

本発明に係る実施形態１のネットワークシステムの全体構成を示す図トラヒック転送レート制御の説明図実施形態１のネットワークシステムにおける経路設計の説明図ネットワーク管理装置が保持するトポロジ情報の例を示す図収容しようとするユーザ情報の例を示す図経路設計方法のフローチャート図５に対する設計結果を示す図図５に対する設計結果を示す図帯域割り当てを行う際のアルゴリズムの説明図帯域割り当ての例を示す図ユーザ情報の例を示す図最短路ツリーの例を示す図ネットワーク構成の例を示す図図１３のトポロジ情報を示す図ノード除外後のツリーの例を示す図帯域の割り当て結果を示す図ダイクストラアルゴリズムの例を示す図ツリー上での評価値の例を示す図トータル評価値の例を示す図拠点収容ノード候補を加えたトポロジ情報の例を示す図ツリーテーブルの例を示す図ネットワーク構成の例を示す図トポロジ情報の例を示す図ノード除外後のトポロジ情報の例を示す図階層化されたネットワーク構成の例を示す図サブドメイン属性を含むトポロジ情報の例を示す図サブドメイン情報テーブルの例を示す図ノード除外後のトポロジ情報の例を示す図等コスト別経路の例を示す図ツリー上での評価値を得た際に作成されたダイクストラアルゴリズムの処理結果を示す図図１３のトポロジ情報の例を示す図実施形態１０における別経路の説明図図１９の設計結果を示す図図３２の設計結果を示す図図１３のトポロジ情報の例を示す図ユーザ１のトラヒック収容後のトポロジ情報を示す図ユーザ情報の例を示す図迂回前の設計結果を示す図迂回後の設計結果を示す図ユーザ１収容替え後のトポロジ情報を示す図

符号の説明

１０ネットワーク管理装置
１１演算処理部
１２入力部
１３記憶部
１４通信制御部
Ｎ中継ノード
２１入力部
２２出力部
２３設定取得部
２４設定部

Claims

複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置にて、前記ユーザ拠点間の通信経路を設計する経路設計方法であって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を含み、
前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最小ホップ数で接続した最小ホップ経路を求める経路設計方法。
前記経路設計を行うステップにおいて、全ユーザ拠点を結ぶ経路上の各中継ノードについて任意のポートに割り当てる通信帯域の上限を他ポートに割り当てる通信帯域の上限の和以下とする請求項１に記載の経路設計方法。
前記経路設計を行うステップにおいて、各中継ノードを起点とするツリー状の経路を求めると共に、前記通信を中継しない中継ノードを示す条件を定義し、該ツリー状の経路をなす中継ノードから該条件に該当する中継ノードを除外して通信経路を求める請求項１に記載の経路設計方法。
拠点収容ノードになりうる中継ノードを起点としたツリー状の経路の情報を予め求めて記憶しておき、経路設計を行う際に該ツリー状の経路の情報を読み出して利用する請求項３に記載の経路設計方法。
ポート数１で且つユーザ拠点収容ノードではない中継ノードおよびそれに接続するリンク全てを設計対象から除外したのちに経路設計を行う請求項１又は３に記載の経路設計方法。
複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置にて運用され、前記ユーザ拠点間の通信経路を設計するプログラムであって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を前記ネットワーク管理装置に行わせ、
前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最小ホップ数で接続した最小ホップ経路を求める経路設計プログラム。
複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワークの該中継ノードと接続するネットワーク管理装置であって、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付ける入力部と、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するトポロジ取得部と、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う経路設計部と、
前記経路設計結果を出力する出力部と、
を含み、
前記経路設計部が、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最小ホップ数で接続した最小ホップ経路を求めるネットワーク管理装置。
複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワーク及び該中継ノードと接続するネットワーク管理装置とを備えるネットワークシステムであって、
前記ネットワーク管理装置が、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付ける入力部と、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するトポロジ取得部と、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行う経路設計部と、
前記経路設計結果を出力する経路出力部と
を備え、
前記経路設計部が、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最小ホップ数で接続した最小ホップ経路を求め、
前記中継ノードが、
前記通信のトラヒックを受け付ける入力部と、
該トラヒックを前記ポートを介して次のノードに出力する出力部と、
前記ネットワーク管理装置から設定情報を受信する設定取得部と、
この設定情報に基づいて前記出力部のポートの設定を行う設定部と、
を備えたネットワークシステム。
複数のユーザ拠点間を複数の中継ノードとリンクとで接続するネットワーク及び該中継ノードと接続するネットワーク管理装置とを備えるネットワークシステムにて運用される方法であって、
前記ネットワーク管理装置が、
各ユーザ拠点と中継ノードとを接続するリンクであるアクセスリンクの帯域の情報及びこのアクセスリンクを介してユーザ拠点と接続する中継ノードを示す情報を含むユーザ情報の入力を受け付けるステップと、
前記ユーザ拠点間の通信を中継するネットワークのトポロジ情報を取得するステップと、
前記ユーザ情報及びトポロジ情報に基づいて通信を中継するポート及び中継しないポートを求めると共に、該通信を中継するポートの通信帯域の上限を求め、前記ユーザ拠点間をツリー状の経路で接続するように経路設計を行うステップと、
前記経路設計結果を出力するステップと、
を行い、
前記経路設計を行うステップにおいて、前記アクセスリンクを介してユーザ拠点と接続する中継ノードである拠点収容ノードを起点とするツリー状の経路を求め、このツリー状の経路をなす全中継ノードについて、各ユーザ拠点と中継ノードとを結ぶアクセスリンクで利用可能な帯域と、各ユーザ拠点から到達するのに必要な中継ノード数から得られる評価値を求め、この評価値に基づいて選択された中継ノードと、各拠点との間を最小ホップ数で接続した最小ホップ経路を求め、
前記中継ノードが、
前記ネットワーク管理装置から設定情報を受信するステップと、
この設定情報に基づいて前記出力部のポートの設定を行うステップと、
を行うネットワーク管理方法。