(57)【特許請求の範囲】
【請求項１】
複数のデマンドノードと少なくとも一つの目的地ノードとを含む、同期性光学ネットワーク（ＳＯＮＥＴ）のための階層的アーキテクチャの設計方法であって、前記複数のデマンドノードにて通信トラフィックが発生し、前記少なくとも一つの目的地ノードにて前記通信トラフィックが集結されスイッチへ転送される設計方法において、
ａ．前記複数のデマンドノードを、デマンドノードグループに分割するとともに、選択されたデマンドノードがハブおよびスポークによるツリートポロジーに属するスポークノードとなるよう事前に選択するステップと、
ｂ．バックボーンリングとの接続のためのリングハブとなるよう、各前記グループから少なくとも一つのノードを選択するステップと、
ｃ．少なくとも前記リングハブと前記少なくとも一つの目的地ノードとを含む、バックボーンリングトポロジーを設計するステップと、
ｄ．各前記デマンドノードグループに対してアクセスリングトポロジーを設計し、前記バックボーンリングトポロジーと前記アクセスリングトポロジーとをもって初期ネットワークトポロジーを構成するステップと、
ｅ．前記初期ネットワークトポロジーに関連するコストを算定するステップと、
ｆ．少なくとも一つの代替リングハブを選択し、新たな一式のリングハブを用意するステップと、
ｇ．ステップ（ｃ）〜ステップ（ｅ）を前記新たな一式のリングハブに適用して実施し、その結果ネットワークコスト推計が減少するかどうかを断定するステップと、
ｈ．最小限のコストが係わるネットワークトポロジーが生成されるまで、ステップ（ｆ）〜ステップ（ｇ）を繰り返すステップと、
を有することを特徴とする設計方法。
【請求項２】
請求項１に記載の方法であって、
選択されたデマンドノードが、ハブおよびスポークによるツリートポロジーに属するスポークノードとなるよう事前に選択される方法において更に、
ｉ．前記選択されたデマンドノードを、第一の複数のグループに分割するステップと、
ｊ．各前記第一の複数のグループの地理的メジアンを表す位置を検出し、各グループにおいて前記位置に、前記バックボーントポロジーまたはアクセスリングトポロジーのどちらかに含まれる前記ノードの中から選ばれるルートノードを関連させるステップであって、各前記ルートノードは各グループにおいて前記地理的メジアン位置に最も距離的に近いノードであるステップと、
ｋ．各ルートノードが、自身が属するリングとそのリングに関係するノードグループを表すツリーとを連結するよう、各前記第一の複数のグループに対してツリートポロジーを設計するステップと、
ｌ．前記選択されたデマンドノードを、前記第一の複数のグループとは異なった第二の複数のグループに分割し、ステップ（ｊ）〜ステップ（ｋ）を前記第二の複数のグループに適用して実施するステップと、
ｍ．最短長を有するツリートポロジーが生成されるまで、ステップ（ｉ）を繰り返すステップと、
を有することを特徴とする方法。
【請求項３】
請求項２に記載の方法において更に、ビンパッキング発見的方法に従って、各ハブおよびスポークトポロジー、アクセスリングトポロジー、並びにバックボーンリングトポロジーに対してＳＯＮＥＴ伝送リングを設計するステップを有する方法。
【請求項４】
請求項３に記載の方法において、前記ビンパッキング発見的手法は、最初適合減少型発見的方法であり、前記ビンパッキング発見方法は、前記要求が複数のリングにより均一に分配されるように、前記要求を前記複数のリングに割り付けようとすることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、ステップ（ｂ）は、各前記グループにおいてリングハブとするよう一対の隣接するノードを選択し、前記階層的アーキテクチャがパスインラインアーキテクチャになるよう構成するステップを含むことを特徴とする方法。
【請求項６】
請求項３に記載の方法において、前記アクセスリングトポロジーは、バックボーンリングトポロジーよりも低いスピードのＳＯＮＥＴリングをサポートすることを特徴とする方法。
【請求項７】
請求項１に記載の方法において、前記複数のデマンドノードはステップ（ａ）において、ｐ−メジアン発見的方法に従って分割されることを特徴とする方法。
【請求項８】
請求項１に記載の方法において、前記別個のデマンドノードグループは各々、所定の最大数よりも少ない数のノードを含むことを特徴とする方法。
【請求項９】
請求項５に記載の方法において、該選択された隣接するデマンドノードは互いに、所定の最小限の距離によって離れていることを特徴とする方法。
【請求項１０】
請求項１に記載の方法において、前記最小限のコストが係わるネットワークトポロジーが生成された後、前記アクセスリングトポロジーおよび前記バックボーンリングトポロジーを再設計し、先在するリンクを組み込むステップを実施することを含む方法。
【請求項１１】
請求項１０に記載の方法において、前記再設計のステップは、スタイナーの巡回セールスマン問題による発見的方法に従って実施されることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ローカルアクセスに適した同期性光学ネットワーク（ＳＯＮＥＴ）リングの設計方法に関する。
【０００２】
【従来の技術】
電気通信業におけるローカルアクセス市場では、規制緩和の到来を迎え、ますます競争が激化している。ローカルアクセスサービスは、従来の普通電話サービス（Plain Old Telephone Service;ＰＯＴＳ）および各種データサービスに加え、ケーブルテレビ、無線、パーソナル通信サービス（ＰＣＳ）、並びにインターネットにアクセスする高帯域デジタル接続などの新しい電気通信サービスに、加入者接続が可能な状態にすることが必要である。このようなサービスを供給するために設計されるネットワークに最も要求される二つの特性は、信頼性と、市場に合わせて経済的に発展できることである。
【０００３】
電気通信伝送ネットワークは一般的に、一連のデマンドノード、一連の目的地ノード、およびそれらのノードを連結する一連のリンク並びに中間ノードによって構成されている。デマンドノードにてデマンドが発生し、目的地ノードにてデマンドは終了する。特にローカルアクセスネットワークに関して言えば、デマンドノードは大規模事業施設およびローカルサービングオフィス（ＬＳＯ）から成る。ＬＳＯは、多くの個人および小規模事業の顧客からのデマンドトラフィックの集結点を表す。ローカルネットワークの目的地ノードは、終端交差接続装置並びにローカルおよび長距離スイッチが位置するネットワークノードである。大多数のデマンドの目的地になる特定のネットワークノードは、サービスノードと称される。
【０００４】
同期性光学ネットワーク（ＳＯＮＥＴ）として知られる伝送技術は、ローカルアクセスネットワークに要求される特徴を有する。即ちＳＯＮＥＴは、現代の電気通信ネットワークに対して、経済的で、フレキシブルで、且つ信頼性の高い転送機構を提供するものである。特にＳＯＮＥＴは、ファイバ切断などのネットワーク上の故障の後にサービスの迅速な復旧を可能にする、自己回復リング（ＳＨＲ）ネットワークの設計を容易にする。電気通信業界では、ローカルネットワークを含む数々のネットワーク内に、ＳＯＮＥＴリングネットワークを早急に配備している。ローカルアクセスネットワークに適したＳＯＮＥＴアーキテクチャには、パスインライン（Path-in-Line；ＰＩＬ）として知られたものがある。ＰＩＬアーキテクチャは、互いに連結された複数のリングを階層的に配置したものを用いる。
【０００５】
ＳＯＮＥＴアーキテクチャの設計方法論は、ネットワークトポロジーの設計と、ＳＯＮＥＴリング自身の設計とに分けられる。ネットワークトポロジーとは、ネットワーク内のリンクの空間的配置に関することである。例えばリングトポロジーにおいては、数個のリンクが環状に接続され、トポロジー上のリングを形成する。ＳＯＮＥＴリングとは、ネットワークリングトポロジーを横断（トランジスタバース：traverse）する物理的な通信経路に関することである。更に詳しく言えば、ＳＯＮＥＴリングは、トポロジー上のリングの各リンクを通過する一対のファイバから成る。サポートできるノードの容量および数量に限界があるため、一つのトポロジー上のリングにおける全てのノードの処理にあたるには、数個のＳＯＮＥＴリングが必要な場合もある。このような場合の、同じトポロジー上のリングを通過する複数のＳＯＮＥＴリングは、積層されている、と説明される。
【０００６】
ネットワーク設計方法の主な課題は、最小限のコストで、特定のトポロジー上の制約に即したネットワークを構成することである。ＳＯＮＥＴネットワークのコストは、光ファイバによるリンクの形成に係わる伝送費に、ノードにおけるＳＯＮＥＴ装置費を足したものを含む。伝送費は、総距離費とファイバ費の、二大要素から成る。総距離費は、実際のネットワークリンクの長さによって変動し、これらリンクの設置費を表す。設置費は、ネットワーク設置のための用地（ＲＯＷ）にかかる費用と、設置工事（Ｅ＆Ｉ）費を含む。ファイバ費は、総距離および必要なファイバの数量の両方によって変動し、その両要素は、需要によって変動するものである。装置費は、ＳＯＮＥＴアーキテクチャと需要に、主に関連した数値である。ネットワーク設計時の課題が上述のとおりであるとして、ネットワーク設計が取り組む問題点はより詳細には以下のように言い換えられる：一連のデマンドノード、目的地ノード、中間ノード、ＳＯＮＥＴアーキテクチャ、コスト構造、並びに一連のトポロジー上の制約が存在する状況での設計方法は、どのようなリンクが構成されるべきか、および、ノード間に最も経済的な接続を形成するにはいかほどの装置を配備すればよいかを決定しなければならない。制約とは一般的に、トポロジーアーキテクチャのサイズおよび加入者数の限界を決定するものである。ローカルアクセスに適したＰＩＬ  ＳＯＮＥＴアーキテクチャに課せられる制約は、二つのハブを有する階層的リングトポロジーであって、目的地ノードが全てバックボーンリングに位置するトポロジーであることを含む。これによりトラフィックが、多数のデマンドノードから比較的少数の目的地ノードへと向けて流れる。
【０００７】
デマンドノードの大多数は、トポロジー上のリング上に位置する。しかしいくつかのデマンドノードは、「ルート（根）」ノードと称されるノードに、ハブおよびスポークトポロジーによって連結されている。ハブおよびスポークトポロジーは樹木（ツリー）の構造に似て、輪を形成することなく、一連のデマンドノードをスポークと称されるリンクによって相互に接続する。ハブおよびスポークネットワークが「ルート」している（連結している）トポロジー上のリングに関係する、積層型ＳＯＮＥＴリングは、そのハブおよびスポークネットワーク上のデマンドノードの処理にもあたる。
【０００８】
ＳＯＮＥＴネットワークの従来の設計方法論は、コアネットワークに、双方向ライン交換型ＳＯＮＥＴリングを使用するものが中心であった。このようなネットワークは、重要なポイントツーポイントのデマンドが存在する場合に適しており、長距離のコアネットワーク、並びにローカル交換キャリアのスイッチツースイッチトラフィックを処理するネットワークを含む。例えば、ベルコア（BellCore）社製のＳＯＮＥＴツールキットは、このような設計のアルゴリズムを含む（Cosares, S. et al.,"SONET Toolkit: A Decision Support System for Design of Robust and Cost-Effective Fiber-Optic Networks", Interfaces, 25 (1995) pp.20-40に加え、Wasem, O.J.,"An Algorithm for Designing Rings for Survivable Fiber Networks", IEEE Transactions on Reliability, 40 (1991) pp.428-432、 Wasem, O.J, et al."Survivable SONET Networks - Design Methodology", IEEE Journal on Selected Areas in Communications, 12 (1994) pp.205-212、および Wu, T. et al."A Multi-period Design Model for Survivable Network Architecture Selection for SONET Interoffice Networks" IEEE Transactions on Reliability, 40 (1991) pp.417-427 参照のこと）。このようなネットワークのリング設計のための、更なる方法およびシステムが、ＵＳウエスト（US West）社により開発されている（１９９６年５月７日発行のＬ．Ａ．コックスらの米国特許第５，５１５，３６７号"Method and System for Planning and Installing Communications Networks（通信システムの立案および設置のための方法およびシステム）"参照のこと。）Laguna, M.,"Clustering for the Design of SONET Rings in Interoffice Telecommunications", Management Science, 40 (1994) pp.1533-1541では、非階層的リングネットワークにおいて、重要なポイントツーポイントのデマンドを用いてクラスターに分割をすることが提案されている。Altinkemer, K.,"Topological Design of Ring Networks" Computers and Operations Research, 21 (1994) pp.421-431は、バックボーンリングがすでに決定されており、一つのアクセスリングにつき一つのハブのみ必要な場合における、アクセスリングの設計方法を開示している。同様に、Shi,J.and Fonseka, J.P.,"Hierarchical Self-Healing Rings", IEEE/ACM Transactions on Networking, 3 (1995) pp.690-697では、一つのアクセスリングにつき一つのハブが設けられ、各リングには均一数のノードが設けられる階層的なネットワークの設計に関する問題点が扱われている。
【０００９】
【発明が解決しようとする課題】
しかし従来の方法論では、前に列挙したトポロジー上の制約が課せられた、ローカルアクセスに適したＳＯＮＥＴアーキテクチャの設計に関する問題点は扱わない。より詳細に言えば、従来の方法論は、以下に列挙する状況に対応していない：デマンドは、多数のデマンドノードから少数の目的地ノードへ向けて流れる；ネットワークトポロジーは、ハブおよびスポークのツリー、二つのハブを有するアクセスリング、およびバックボーンリングを有し、それらは階層的に連結されている；伝送費が装置費よりも大きな割合を占める；並びに、ネットワークは数百のデマンドノードを有することがある。
【００１０】
【課題を解決するための手段】
本発明は、複数のデマンドノードと少なくとも一つの目的地ノードとを含む、同期性光学ネットワーク（ＳＯＮＥＴ）のための階層的アーキテクチャの設計方法を提供する。この設計方法において、デマンドノードにて通信トラフィックが発生し、目的地ノードにて通信トラフィックが集結されスイッチへ転送される。この設計方法は：（ａ）複数のデマンドノードを、別個のデマンドノードグループに分割するステップと、（ｂ）バックボーンリングとの接続のためのリングハブとなるよう、各グループから少なくとも一つのノードを選択するステップと、（ｃ）少なくともそのリングハブと目的地ノードを含む、バックボーンリングのトポロジーを設計するステップと、（ｄ）各デマンドノードグループに対してアクセスリングのトポロジーを設計し、バックボーンリングのトポロジーとアクセスリングのトポロジーとをもって初期ネットワークトポロジーを構成するステップと、（ｅ）初期ネットワークトポロジーに関連するコストを算定するステップと、（ｆ）少なくとも一つの代替リングハブを選択し、新たな一式のリングハブを用意するステップと、（ｇ）ステップ（ｃ）〜ステップ（ｅ）を新たな一式のリングハブに適用して実施し、その結果ネットワークコスト推計が減少するかどうかを断定するステップと、（ｈ）最小限のコストが係わるネットワークトポロジーが生成されるまで、ステップ（ｆ）〜ステップ（ｇ）を繰り返すステップと、を含む。本発明の他の態様は、ハブおよびスポークトポロジーの設計およびＳＯＮＥＴ伝送に係わる設計に関するものである。
【００１１】
本発明の設計方法は、現存するネットワーク施設のごくわずかな部分しか使用せず、ネットワークの大部分を新たなリンクによって建設する場合、いわゆる「グリーンフィールド」状況において、特に有効である。更に本発明による方法は、数百のデマンドノードを有するネットワークの設計を効率的に成すものである。
【００１２】
【発明の実施の形態】
本発明は、ローカルアクセスネットワークでの使用に適したＳＯＮＥＴアーキテクチャ設計方法に関する。以下に、本発明の例としてＰＩＬ  ＳＯＮＥＴアーキテクチャの設計に関して説明を行うが、当業者であれば、本発明はT-H.Wu, "Fiber Network Service Survivability", Section 8.2.2., Artech House, Boston (1992)に記載されている等の他のアーキテクチャの設計にも適用可能であることが理解できると考える。
【００１３】
図１に示すように、ローカルアクセスネットワーク用のＰＩＬアーキテクチャは、リング１０１、１０３等のアクセスリングとバックボーンリング１０５との２組のトポロジー上のリングと、ハブおよびスポークツリー１１０とを含む。トポロジー上のアクセスリング、またはハブおよびスポークツリーは、ＯＣ−３リング等の低速ＳＯＮＥＴリングをもち、トポロジー上のバックボーンリングはＯＣ−４８リング等の高速ＳＯＮＥＴリングをもつ。アクセスリングは主に、デマンドノードからデマンドを収集するのに用いられる。バックボーンリングはネットワーク目的地ノードおよび中間ノード、ならびにいくつかの大規模なデマンドノードを含む。図１に示すタイプのリングネットワークは、階層リングネットワークと呼ばれることが多い。
【００１４】
ＰＩＬアーキテクチャでは、各アクセスリングはリングハブと呼ばれる２つの中間ノードでバックボーンリングに接続される。例えば図１では、アクセスリング１０１はリングハブ１０７および１０９でバックボーンリング１０５に接続される。所与のアクセスリングとバックボーンリングとの間の接続損失を回避するために、アクセスリングの２つのリングハブ間を最低限の距離だけ離すようにすることで、ハブの同時故障の頻度が低減される。１つのリングハブは、１つ以上のアクセスリング用として機能できる。各リングハブのコストは、あるノードをリングハブとして構成することに関連した固定コストと、該ハブを用いるアクセスリング上でサポートされるデマンドの総量によって異なる可変コストとを含む。ＰＩＬアーキテクチャ以外のＳＯＮＥＴアーキテクチャでは、アクセスリングをバックボーンリングに接続するのに必要なリングハブは１つだけであることに注意されたい。
【００１５】
このように、ローカルアクセスに適したＰＩＬ  ＳＯＮＥＴアーキテクチャに課せられる制約には、すべての目的地ノードがバックボーンリングにあるため多数のデマンドノードから比較的少数の目的地ノードへとトラフィックが流れる二重ハブ方式の階層リングトポロジーが含まれる。環境によっては、技術的およびサービス品質（ＱＯＳ）要件のためにＳＯＮＥＴ  ＰＩＬアーキテクチャに他の制約が課せられる場合がある。このような付加的制約には次のようなものがある。
【００１６】
−音声回路をもつＳＯＮＥＴパス上のＱＯＳ要件に起因する各アクセスリングおよびバックボーンリングの最大長の規格。
【００１７】
−選択した既存のファイバーセグメントをリンクの経路指定に使用すること。トポロジー上のリングの２リンク間は同じファイバーセグメントでは経路指定できない。これら既存セグメントの単位コストは新たにリンクを確立するコストよりも大幅に安い。
【００１８】
−複数ノードの故障によるサービス損失を抑えるための各アクセスリングの最大許容ノード数の規格。
【００１９】
−非常に小規模なアクセスリングの創設を回避するための最小ノード数の規格。
【００２０】
−一定のデマンドノードをハブおよびスポークトポロジーを用いてリングノードに接続する規格。
【００２１】
本発明に従えば、上記の課題を３つのサブステップに分解して連続的に解決することによってＰＩＬ  ＳＯＮＥＴネットワークが設計される。サブステップは、リングトポロジーの設計、ハブおよびスポークトポロジーの設計、およびＳＯＮＥＴトランスポートシステムの設計である。以下にこれら３つの副課題の設計について説明する。
【００２２】
リングトポロジー設計
リングトポロジーの設計は、図２に示すフロー図に従って進められる。まず、デマンドノードを個別のクラスター（集団）に分割する（ステップ２００）。各クラスターは１つのアクセスリングを示す。クラスター化に使用可能なアルゴリズムは、M.B.Tietz and P.Bart, "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph", Operations Research 16, (1968) p.955-961に記載のあるｐメジアン発見的方法に基づく。このアルゴリズムは、各アクセスリングの最大許容数のノードに対する制約の実行にも適用できる。一組のクラスターの形成後、クラスター間で各ノードを切り替えて、アクセスリングあたりの最小数のノードに制約を実行することができる。各クラスター内では一対のリングハブが指定される（ステップ２０２）。リングハブは、ノードとクラスターの地理的メジアンとの接近度に基づいて選択される。
【００２３】
前のステップで一組のリングハブが指定されると、巡回セールスマン問題（ＴＳＰ）発見的方法等の公知の技術に従ってバックボーンリングトポロジーが設計される（ステップ２０４）。バックボーンリングは、リングハブとバックボーン上に存在するべく指定されうる他のノードとを含む。次に、ステップ２００で各クラスターに指定されたノード（リングハブを含む）に基づき、ＴＳＰ発見的方法を用いて各クラスターごとにアクセスリングトポロジーが設計される（ステップ２０６）。リングハブ対が隣接するようにＰＩＬアーキテクチャが設計されていれば、リングハブ対は１つの「スーパーノード」として扱われる。１つ以上のアクセスリングが最大長制約に違反する場合、選択したノードを他のクラスターに移動させてリングが再配列される。ここまでに述べたステップに従ってリングトポロジーが設計されると、そのコストが評価され、コストが以前の設計よりも改善されていることがわかれば、その結果が記憶される（ステップ２０８）。
【００２４】
その後、リングハブは、バックボーンの長さを短縮する他のノードと交換される（ステップ２１０）。このようなノードが見つかれば、最初のステップ２０４へ戻って新たなリングハブの組に基づいてバックボーンリングが設計され、その後、ステップ２０６で対応するアクセスリングが設計される。これらのステップ２００〜２１０を複数回反復することによって解決策が決まれば、既存のファイバーセグメントを考慮してスタイナーのＴＳＰ発見的方法に従ってトポロジー上のリングが設計しなおされる。スタイナーのＴＳＰ発見的方法では、最終的な設計には前に選択されたデマンドノード、リングハブ、およびネットワークノードを残し、一方でその他のノード（既存のファイバーセグメントに接続されたノード）が有利であればそれらのノードを組み入れることが要求される。
【００２５】
最後に、できあがったバックボーンの長さが所定の最大長を上回っていれば、アクセスリングおよび任意のバックボーンデマンドノードが２つ以上の組にクラスター化され、ステップ２０４および２１２に従って各ノード組ごとに異なるトポロジー上のバックボーンリングが設計される。
【００２６】
ハブおよびスポーク設計
ハブおよびスポークトポロジーは、リングトポロジーの設計に続いて行われる。ハブおよびスポークツリーに存在するべく事前に選択されたデマンドノードはスポークノードと呼ばれる。各ツリーのルート（根）はアクセスリングまたはバックボーンリングのいずれかにあるノードの中から選ばれたノードでもよい。明白なことだが、スポークノード数およびルートノードとなりうるノード数が多ければ、莫大な数のツリーネットワークが設計可能となる。このような多数の設計の中から最適な設計を決定するには、次の手順を用いることができる。これは図３に示す。
【００２７】
まず、事前に選択したスポークノードをｐ個のグループに分割する（ステップ３００）。クラスター化の規準には、上記のM.B. Teiz et al. に記載された発見的方法に基づくｐメジアンクラスター化技術等の各種のクラスター化技術を用いることができる。各クラスターはクラスターの地理的メジアンを表す位置を含む。次に、その地理的メジアンにもっとも近接したバックボーンリングノードまたはアクセスリングノードの位置が求められ、ルートノードとなる（ステップ３０２）。こうして選択されたルートノードは予めルートとなりうると規定されたノードからのみ選択されるものであり、それぞれのクラスターに加えられる（ステップ３０４）。同じリングノードが２つ以上のクラスターに一番近いルートノードとして機能する場合は、クラスター同士が組み合わされる。各クラスターのトポロジーは、Prim, R. C., "Shortest Connection Networks and Some Generalizations", Bell System Technical Journal, 36 (1957)pp. 1389-1401 に記載された等の標準の最小スパニング木（ＭＳＴ）アルゴリズムに従って設計される（ステップ３０６）。ツリートポロジーが設計されると、スポークノードは再びｐ個のグループに分けられるが、ここではｐ値は初期値とは異なっている。最終的な設計は、最短のツリー長を生成するｐ値に対応したものとなる（ステップ３１０）。評価されるべきツリーの数（クラスター分割グループ数ｐ）は、総スポークノード数ｓによって異なる。ｓ値が小さければ（５０未満等）、１からｓの間のすべてのｐ値が評価される。ｓ値が大きければ、ｓ／２５からｓまでのｐ値が１０ごとに評価される。より好適なｐ値を求めるには、求められた最適値の近傍でｐ値をより精密に検索すればよい。ハブおよびスポークトポロジーが選択されると、エンドノードを各ツリーからそれに隣接するツリーへ移動させて、ツリー全体長の一層の短縮がはかられる。
【００２８】
「ＳＯＮＥＴトランスポート設計」
ＳＯＮＥＴトランスポート設計は、トポロジー上の各アクセスリングおよびバックボーンリング中に積層型ＳＯＮＥＴを構築するものである。ＳＯＮＥＴトランスポート設計のために、ハブおよびスポークトポロジー上のデマンドノードはハブおよびスポークツリーが根をおろすトポロジー上のリングの一部とみなされる。使用する特定の設計方法は、構築中のＳＯＮＥＴアーキテクチャによって異なる。例えば、ＰＩＬアーキテクチャ等の階層リングアーキテクチャは、低速一方向パス交換型ＯＣ−３リングを使用してアクセスリングならびにハブおよびスポークツリー上のデマンドノードにサービスする。その後、ＯＣ−３リングはバックボーン上でサービスを行う高速ＯＣ−４８リングの上にくる。バックボーンＯＣ−４８リングもまた、この一方向パス交換モードで作動される。各ＯＣ−３リングは保有可能な総デマンド数およびリングがサービスするノード数に制限がある。本発明の一実施形態では、ビンパッキング（bin-packing）発見的アルゴリズムを用いて、デマンドノードを各アクセスリング上の異なるＯＣ−３リングに割り当てる。ビンパッキング発見的方法は、Johnson et al., "Worst-case Performance Bounds for Simple One-dimensional packing Algorithms", SIAM Journal of Computing, 3 (1974) pp.299-325に記載された最初適合減少型発見的アルゴリズムを変形して得られる。変形したビンパッキング発見的方法は、最初適合減少型（first-fit decreasing）発見的方法で求めたのと同数のリングを用いるが、デマンドをリングに割り当てる際にデマンドがリング間でより均等に分配されるようにする。この発見的方法は必要最低数のＳＯＮＥＴリングをほぼ与えることができるので、リングハブ装置にかかるコストを最小限に抑えられる。またバックボーントポロジーに存在するＯＣ−４８リングも、ビンパッキングアルゴリズムに従って設計できる。ＯＣ−４８リングの設計には、ＯＣ−３アクセスリングからのデマンドおよびバックボーン上に直接配置された任意のデマンドノードからのデマンドが入力トラフィックとして使用される。ＯＣ−４８リングの必要数を最小化することにより、サービスノードで必要な装置量の低減も可能となる。
【図面の簡単な説明】
【図１】  パス・イン・ラインＳＯＮＥＴネットワークの一例を示す簡易図である。
【図２】  本発明に従うリングトポロジーの設計方法を示すフロー図である。
【図３】  本発明に従うハブおよびスポークトポロジーの設計方法を示すフロー図である。
【符号の説明】
１０１  アクセスリング、１０５  バックボーンリング、１０７，１０９  リングハブ、１１０  ハブおよびスポーク。
【図１】
0004092016.tif 000002
【図２】
0004092016.tif 000003
【図３】
0004092016.tif 000004