JPH11187054A - ローカルアクセスに適したｓｏｎｅｔリングネットワークの設計方法 - Google Patents
ローカルアクセスに適したｓｏｎｅｔリングネットワークの設計方法Info
- Publication number
- JPH11187054A JPH11187054A JP10209437A JP20943798A JPH11187054A JP H11187054 A JPH11187054 A JP H11187054A JP 10209437 A JP10209437 A JP 10209437A JP 20943798 A JP20943798 A JP 20943798A JP H11187054 A JPH11187054 A JP H11187054A
- Authority
- JP
- Japan
- Prior art keywords
- ring
- topology
- nodes
- node
- demand
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- RGNPBRKPHBKNKX-UHFFFAOYSA-N hexaflumuron Chemical group C1=C(Cl)C(OC(F)(F)C(F)F)=C(Cl)C=C1NC(=O)NC(=O)C1=C(F)C=CC=C1F RGNPBRKPHBKNKX-UHFFFAOYSA-N 0.000 title claims abstract 4
- 238000000034 method Methods 0.000 title claims description 43
- 238000013461 design Methods 0.000 claims abstract description 42
- 230000003287 optical effect Effects 0.000 claims abstract description 5
- 230000001360 synchronised effect Effects 0.000 claims abstract description 5
- 238000004891 communication Methods 0.000 claims description 10
- 230000006854 communication Effects 0.000 claims description 10
- 230000005540 biological transmission Effects 0.000 claims description 7
- 238000012856 packing Methods 0.000 claims description 7
- 230000003247 decreasing effect Effects 0.000 abstract 1
- 239000000835 fiber Substances 0.000 description 11
- 238000009434 installation Methods 0.000 description 3
- 238000011160 research Methods 0.000 description 2
- 230000003044 adaptive effect Effects 0.000 description 1
- 230000002457 bidirectional effect Effects 0.000 description 1
- 239000000969 carrier Substances 0.000 description 1
- 230000003831 deregulation Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000009977 dual effect Effects 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 239000013307 optical fiber Substances 0.000 description 1
- 238000005192 partition Methods 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 230000007723 transport mechanism Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
- H04L12/46—Interconnection of networks
- H04L12/4637—Interconnected ring systems
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J3/00—Time-division multiplex systems
- H04J3/02—Details
- H04J3/08—Intermediate station arrangements, e.g. for branching, for tapping-off
- H04J3/085—Intermediate station arrangements, e.g. for branching, for tapping-off for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q11/00—Selecting arrangements for multiplex systems
- H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
- H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
- H04Q11/0478—Provisions for broadband connections
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J2203/00—Aspects of optical multiplex systems other than those covered by H04J14/05 and H04J14/07
- H04J2203/0001—Provisions for broadband connections in integrated services digital network using frames of the Optical Transport Network [OTN] or using synchronous transfer mode [STM], e.g. SONET, SDH
- H04J2203/0028—Local loop
- H04J2203/0039—Topology
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J2203/00—Aspects of optical multiplex systems other than those covered by H04J14/05 and H04J14/07
- H04J2203/0001—Provisions for broadband connections in integrated services digital network using frames of the Optical Transport Network [OTN] or using synchronous transfer mode [STM], e.g. SONET, SDH
- H04J2203/0028—Local loop
- H04J2203/0039—Topology
- H04J2203/0042—Ring
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J2203/00—Aspects of optical multiplex systems other than those covered by H04J14/05 and H04J14/07
- H04J2203/0001—Provisions for broadband connections in integrated services digital network using frames of the Optical Transport Network [OTN] or using synchronous transfer mode [STM], e.g. SONET, SDH
- H04J2203/0051—Network Node Interface, e.g. tandem connections, transit switching
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Small-Scale Networks (AREA)
- Time-Division Multiplex Systems (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Optical Communication System (AREA)
Abstract
(57)【要約】
【課題】 同期性光学ネットワーク（ＳＯＮＥＴ）のた
めの階層的アーキテクチャを設計する。 【解決手段】 複数のデマンドノードを、グループに分
割し（２００）、各グループからバックボーンリングと
の接続のためのリングハブとなるノードを選択し（２０
２）、そのリングハブと目的地ノードを含むバックボー
ンリングのトポロジーを設計し（２０４）、各デマンド
ノードグループに対してアクセスリングのトポロジーを
設計し（２０６）、両トポロジー構成される初期ネット
ワークトポロジーのコストを算定する（２０８）。他の
代替リングハブを選択し、新たな一式のリングハブを用
意し、上記ステップをリングハブに実施し、その結果ネ
ットワークコスト推計が減少するかどうかを判定し、最
小限のコストが係わるネットワークトポロジーが生成さ
れるまでステップ繰り返す。
めの階層的アーキテクチャを設計する。 【解決手段】 複数のデマンドノードを、グループに分
割し（２００）、各グループからバックボーンリングと
の接続のためのリングハブとなるノードを選択し（２０
２）、そのリングハブと目的地ノードを含むバックボー
ンリングのトポロジーを設計し（２０４）、各デマンド
ノードグループに対してアクセスリングのトポロジーを
設計し（２０６）、両トポロジー構成される初期ネット
ワークトポロジーのコストを算定する（２０８）。他の
代替リングハブを選択し、新たな一式のリングハブを用
意し、上記ステップをリングハブに実施し、その結果ネ
ットワークコスト推計が減少するかどうかを判定し、最
小限のコストが係わるネットワークトポロジーが生成さ
れるまでステップ繰り返す。
Description
【０００１】
【発明の属する技術分野】本発明は、ローカルアクセス
に適した同期性光学ネットワーク（ＳＯＮＥＴ）リング
の設計方法に関する。
に適した同期性光学ネットワーク（ＳＯＮＥＴ）リング
の設計方法に関する。
【０００２】
【従来の技術】電気通信業におけるローカルアクセス市
場では、規制緩和の到来を迎え、ますます競争が激化し
ている。ローカルアクセスサービスは、従来の普通電話
サービス（Plain Old Telephone Service;ＰＯＴＳ）お
よび各種データサービスに加え、ケーブルテレビ、無
線、パーソナル通信サービス（ＰＣＳ）、並びにインタ
ーネットにアクセスする高帯域デジタル接続などの新し
い電気通信サービスに、加入者接続が可能な状態にする
ことが必要である。このようなサービスを供給するため
に設計されるネットワークに最も要求される二つの特性
は、信頼性と、市場に合わせて経済的に発展できること
である。
場では、規制緩和の到来を迎え、ますます競争が激化し
ている。ローカルアクセスサービスは、従来の普通電話
サービス（Plain Old Telephone Service;ＰＯＴＳ）お
よび各種データサービスに加え、ケーブルテレビ、無
線、パーソナル通信サービス（ＰＣＳ）、並びにインタ
ーネットにアクセスする高帯域デジタル接続などの新し
い電気通信サービスに、加入者接続が可能な状態にする
ことが必要である。このようなサービスを供給するため
に設計されるネットワークに最も要求される二つの特性
は、信頼性と、市場に合わせて経済的に発展できること
である。
【０００３】電気通信伝送ネットワークは一般的に、一
連のデマンドノード、一連の目的地ノード、およびそれ
らのノードを連結する一連のリンク並びに中間ノードに
よって構成されている。デマンドノードにてデマンドが
発生し、目的地ノードにてデマンドは終了する。特にロ
ーカルアクセスネットワークに関して言えば、デマンド
ノードは大規模事業施設およびローカルサービングオフ
ィス（ＬＳＯ）から成る。ＬＳＯは、多くの個人および
小規模事業の顧客からのデマンドトラフィックの集結点
を表す。ローカルネットワークの目的地ノードは、終端
交差接続装置並びにローカルおよび長距離スイッチが位
置するネットワークノードである。大多数のデマンドの
目的地になる特定のネットワークノードは、サービスノ
ードと称される。
連のデマンドノード、一連の目的地ノード、およびそれ
らのノードを連結する一連のリンク並びに中間ノードに
よって構成されている。デマンドノードにてデマンドが
発生し、目的地ノードにてデマンドは終了する。特にロ
ーカルアクセスネットワークに関して言えば、デマンド
ノードは大規模事業施設およびローカルサービングオフ
ィス（ＬＳＯ）から成る。ＬＳＯは、多くの個人および
小規模事業の顧客からのデマンドトラフィックの集結点
を表す。ローカルネットワークの目的地ノードは、終端
交差接続装置並びにローカルおよび長距離スイッチが位
置するネットワークノードである。大多数のデマンドの
目的地になる特定のネットワークノードは、サービスノ
ードと称される。
【０００４】同期性光学ネットワーク（ＳＯＮＥＴ）と
して知られる伝送技術は、ローカルアクセスネットワー
クに要求される特徴を有する。即ちＳＯＮＥＴは、現代
の電気通信ネットワークに対して、経済的で、フレキシ
ブルで、且つ信頼性の高い転送機構を提供するものであ
る。特にＳＯＮＥＴは、ファイバ切断などのネットワー
ク上の故障の後にサービスの迅速な復旧を可能にする、
自己回復リング（ＳＨＲ）ネットワークの設計を容易に
する。電気通信業界では、ローカルネットワークを含む
数々のネットワーク内に、ＳＯＮＥＴリングネットワー
クを早急に配備している。ローカルアクセスネットワー
クに適したＳＯＮＥＴアーキテクチャには、パスインラ
イン（Path-in-Line；ＰＩＬ）として知られたものがあ
る。ＰＩＬアーキテクチャは、互いに連結された複数の
リングを階層的に配置したものを用いる。
して知られる伝送技術は、ローカルアクセスネットワー
クに要求される特徴を有する。即ちＳＯＮＥＴは、現代
の電気通信ネットワークに対して、経済的で、フレキシ
ブルで、且つ信頼性の高い転送機構を提供するものであ
る。特にＳＯＮＥＴは、ファイバ切断などのネットワー
ク上の故障の後にサービスの迅速な復旧を可能にする、
自己回復リング（ＳＨＲ）ネットワークの設計を容易に
する。電気通信業界では、ローカルネットワークを含む
数々のネットワーク内に、ＳＯＮＥＴリングネットワー
クを早急に配備している。ローカルアクセスネットワー
クに適したＳＯＮＥＴアーキテクチャには、パスインラ
イン（Path-in-Line；ＰＩＬ）として知られたものがあ
る。ＰＩＬアーキテクチャは、互いに連結された複数の
リングを階層的に配置したものを用いる。
【０００５】ＳＯＮＥＴアーキテクチャの設計方法論
は、ネットワークトポロジーの設計と、ＳＯＮＥＴリン
グ自身の設計とに分けられる。ネットワークトポロジー
とは、ネットワーク内のリンクの空間的配置に関するこ
とである。例えばリングトポロジーにおいては、数個の
リンクが環状に接続され、トポロジー上のリングを形成
する。ＳＯＮＥＴリングとは、ネットワークリングトポ
ロジーを横断（トランジスタバース：traverse）する物
理的な通信経路に関することである。更に詳しく言え
ば、ＳＯＮＥＴリングは、トポロジー上のリングの各リ
ンクを通過する一対のファイバから成る。サポートでき
るノードの容量および数量に限界があるため、一つのト
ポロジー上のリングにおける全てのノードの処理にあた
るには、数個のＳＯＮＥＴリングが必要な場合もある。
このような場合の、同じトポロジー上のリングを通過す
る複数のＳＯＮＥＴリングは、積層されている、と説明
される。
は、ネットワークトポロジーの設計と、ＳＯＮＥＴリン
グ自身の設計とに分けられる。ネットワークトポロジー
とは、ネットワーク内のリンクの空間的配置に関するこ
とである。例えばリングトポロジーにおいては、数個の
リンクが環状に接続され、トポロジー上のリングを形成
する。ＳＯＮＥＴリングとは、ネットワークリングトポ
ロジーを横断（トランジスタバース：traverse）する物
理的な通信経路に関することである。更に詳しく言え
ば、ＳＯＮＥＴリングは、トポロジー上のリングの各リ
ンクを通過する一対のファイバから成る。サポートでき
るノードの容量および数量に限界があるため、一つのト
ポロジー上のリングにおける全てのノードの処理にあた
るには、数個のＳＯＮＥＴリングが必要な場合もある。
このような場合の、同じトポロジー上のリングを通過す
る複数のＳＯＮＥＴリングは、積層されている、と説明
される。
【０００６】ネットワーク設計方法の主な課題は、最小
限のコストで、特定のトポロジー上の制約に即したネッ
トワークを構成することである。ＳＯＮＥＴネットワー
クのコストは、光ファイバによるリンクの形成に係わる
伝送費に、ノードにおけるＳＯＮＥＴ装置費を足したも
のを含む。伝送費は、総距離費とファイバ費の、二大要
素から成る。総距離費は、実際のネットワークリンクの
長さによって変動し、これらリンクの設置費を表す。設
置費は、ネットワーク設置のための用地（ＲＯＷ）にか
かる費用と、設置工事（Ｅ＆Ｉ）費を含む。ファイバ費
は、総距離および必要なファイバの数量の両方によって
変動し、その両要素は、需要によって変動するものであ
る。装置費は、ＳＯＮＥＴアーキテクチャと需要に、主
に関連した数値である。ネットワーク設計時の課題が上
述のとおりであるとして、ネットワーク設計が取り組む
問題点はより詳細には以下のように言い換えられる：一
連のデマンドノード、目的地ノード、中間ノード、ＳＯ
ＮＥＴアーキテクチャ、コスト構造、並びに一連のトポ
ロジー上の制約が存在する状況での設計方法は、どのよ
うなリンクが構成されるべきか、および、ノード間に最
も経済的な接続を形成するにはいかほどの装置を配備す
ればよいかを決定しなければならない。制約とは一般的
に、トポロジーアーキテクチャのサイズおよび加入者数
の限界を決定するものである。ローカルアクセスに適し
たＰＩＬ ＳＯＮＥＴアーキテクチャに課せられる制約
は、二つのハブを有する階層的リングトポロジーであっ
て、目的地ノードが全てバックボーンリングに位置する
トポロジーであることを含む。これによりトラフィック
が、多数のデマンドノードから比較的少数の目的地ノー
ドへと向けて流れる。
限のコストで、特定のトポロジー上の制約に即したネッ
トワークを構成することである。ＳＯＮＥＴネットワー
クのコストは、光ファイバによるリンクの形成に係わる
伝送費に、ノードにおけるＳＯＮＥＴ装置費を足したも
のを含む。伝送費は、総距離費とファイバ費の、二大要
素から成る。総距離費は、実際のネットワークリンクの
長さによって変動し、これらリンクの設置費を表す。設
置費は、ネットワーク設置のための用地（ＲＯＷ）にか
かる費用と、設置工事（Ｅ＆Ｉ）費を含む。ファイバ費
は、総距離および必要なファイバの数量の両方によって
変動し、その両要素は、需要によって変動するものであ
る。装置費は、ＳＯＮＥＴアーキテクチャと需要に、主
に関連した数値である。ネットワーク設計時の課題が上
述のとおりであるとして、ネットワーク設計が取り組む
問題点はより詳細には以下のように言い換えられる：一
連のデマンドノード、目的地ノード、中間ノード、ＳＯ
ＮＥＴアーキテクチャ、コスト構造、並びに一連のトポ
ロジー上の制約が存在する状況での設計方法は、どのよ
うなリンクが構成されるべきか、および、ノード間に最
も経済的な接続を形成するにはいかほどの装置を配備す
ればよいかを決定しなければならない。制約とは一般的
に、トポロジーアーキテクチャのサイズおよび加入者数
の限界を決定するものである。ローカルアクセスに適し
たＰＩＬ ＳＯＮＥＴアーキテクチャに課せられる制約
は、二つのハブを有する階層的リングトポロジーであっ
て、目的地ノードが全てバックボーンリングに位置する
トポロジーであることを含む。これによりトラフィック
が、多数のデマンドノードから比較的少数の目的地ノー
ドへと向けて流れる。
【０００７】デマンドノードの大多数は、トポロジー上
のリング上に位置する。しかしいくつかのデマンドノー
ドは、「ルート（根）」ノードと称されるノードに、ハ
ブおよびスポークトポロジーによって連結されている。
ハブおよびスポークトポロジーは樹木（ツリー）の構造
に似て、輪を形成することなく、一連のデマンドノード
をスポークと称されるリンクによって相互に接続する。
ハブおよびスポークネットワークが「ルート」している
（連結している）トポロジー上のリングに関係する、積
層型ＳＯＮＥＴリングは、そのハブおよびスポークネッ
トワーク上のデマンドノードの処理にもあたる。
のリング上に位置する。しかしいくつかのデマンドノー
ドは、「ルート（根）」ノードと称されるノードに、ハ
ブおよびスポークトポロジーによって連結されている。
ハブおよびスポークトポロジーは樹木（ツリー）の構造
に似て、輪を形成することなく、一連のデマンドノード
をスポークと称されるリンクによって相互に接続する。
ハブおよびスポークネットワークが「ルート」している
（連結している）トポロジー上のリングに関係する、積
層型ＳＯＮＥＴリングは、そのハブおよびスポークネッ
トワーク上のデマンドノードの処理にもあたる。
【０００８】ＳＯＮＥＴネットワークの従来の設計方法
論は、コアネットワークに、双方向ライン交換型ＳＯＮ
ＥＴリングを使用するものが中心であった。このような
ネットワークは、重要なポイントツーポイントのデマン
ドが存在する場合に適しており、長距離のコアネットワ
ーク、並びにローカル交換キャリアのスイッチツースイ
ッチトラフィックを処理するネットワークを含む。例え
ば、ベルコア（BellCore）社製のＳＯＮＥＴツールキッ
トは、このような設計のアルゴリズムを含む（Cosares,
S. et al.,"SONET Toolkit: A Decision Support Syst
em for Designof Robust and Cost-Effective Fiber-Op
tic 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 Methodo
logy", IEEE Journal on Selected Areas in Communica
tions, 12 (1994) pp.205-212、および Wu, T. et al."
A Multi-period Design Model for Survivable Network
Architecture Selection for SONET Interoffice Netw
orks" IEEE Transac tions on Reliability, 40 (1991)
pp.417-427 参照のこと）。このようなネットワークの
リング設計のための、更なる方法およびシステムが、Ｕ
Ｓウエスト（US West）社により開発されている（１９
９６年５月７日発行のＬ．Ａ．コックスらの米国特許第
５，５１５，３６７号"Method and System for Plannin
g andInstalling Communications Networks（通信シス
テムの立案および設置のための方法およびシステム）"
参照のこと。）Laguna, M.,"Clustering for the Desig
nof SONET Rings in Interoffice Telecommunication
s", Management Science,40 (1994) pp.1533-1541で
は、非階層的リングネットワークにおいて、重要なポイ
ントツーポイントのデマンドを用いてクラスターに分割
をすることが提案されている。Altinkemer, K.,"Topolo
gical Design of Ring Networks" Computers a nd Opera
tions Research, 21 (1994) pp.421-431は、バックボー
ンリングがすでに決定されており、一つのアクセスリン
グにつき一つのハブのみ必要な場合における、アクセス
リングの設計方法を開示している。同様に、Shi,J.and
Fonseka,J.P.,"Hierarchical Self-Healing Rings", IE
EE/ACM Transactions on Networ king, 3 (1995) pp.690
-697では、一つのアクセスリングにつき一つのハブが設
けられ、各リングには均一数のノードが設けられる階層
的なネットワークの設計に関する問題点が扱われてい
る。
論は、コアネットワークに、双方向ライン交換型ＳＯＮ
ＥＴリングを使用するものが中心であった。このような
ネットワークは、重要なポイントツーポイントのデマン
ドが存在する場合に適しており、長距離のコアネットワ
ーク、並びにローカル交換キャリアのスイッチツースイ
ッチトラフィックを処理するネットワークを含む。例え
ば、ベルコア（BellCore）社製のＳＯＮＥＴツールキッ
トは、このような設計のアルゴリズムを含む（Cosares,
S. et al.,"SONET Toolkit: A Decision Support Syst
em for Designof Robust and Cost-Effective Fiber-Op
tic 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 Methodo
logy", IEEE Journal on Selected Areas in Communica
tions, 12 (1994) pp.205-212、および Wu, T. et al."
A Multi-period Design Model for Survivable Network
Architecture Selection for SONET Interoffice Netw
orks" IEEE Transac tions on Reliability, 40 (1991)
pp.417-427 参照のこと）。このようなネットワークの
リング設計のための、更なる方法およびシステムが、Ｕ
Ｓウエスト（US West）社により開発されている（１９
９６年５月７日発行のＬ．Ａ．コックスらの米国特許第
５，５１５，３６７号"Method and System for Plannin
g andInstalling Communications Networks（通信シス
テムの立案および設置のための方法およびシステム）"
参照のこと。）Laguna, M.,"Clustering for the Desig
nof SONET Rings in Interoffice Telecommunication
s", Management Science,40 (1994) pp.1533-1541で
は、非階層的リングネットワークにおいて、重要なポイ
ントツーポイントのデマンドを用いてクラスターに分割
をすることが提案されている。Altinkemer, K.,"Topolo
gical Design of Ring Networks" Computers a nd Opera
tions Research, 21 (1994) pp.421-431は、バックボー
ンリングがすでに決定されており、一つのアクセスリン
グにつき一つのハブのみ必要な場合における、アクセス
リングの設計方法を開示している。同様に、Shi,J.and
Fonseka,J.P.,"Hierarchical Self-Healing Rings", IE
EE/ACM Transactions on Networ king, 3 (1995) pp.690
-697では、一つのアクセスリングにつき一つのハブが設
けられ、各リングには均一数のノードが設けられる階層
的なネットワークの設計に関する問題点が扱われてい
る。
【０００９】
【発明が解決しようとする課題】しかし従来の方法論で
は、前に列挙したトポロジー上の制約が課せられた、ロ
ーカルアクセスに適したＳＯＮＥＴアーキテクチャの設
計に関する問題点は扱わない。より詳細に言えば、従来
の方法論は、以下に列挙する状況に対応していない：デ
マンドは、多数のデマンドノードから少数の目的地ノー
ドへ向けて流れる；ネットワークトポロジーは、ハブお
よびスポークのツリー、二つのハブを有するアクセスリ
ング、およびバックボーンリングを有し、それらは階層
的に連結されている；伝送費が装置費よりも大きな割合
を占める；並びに、ネットワークは数百のデマンドノー
ドを有することがある。
は、前に列挙したトポロジー上の制約が課せられた、ロ
ーカルアクセスに適したＳＯＮＥＴアーキテクチャの設
計に関する問題点は扱わない。より詳細に言えば、従来
の方法論は、以下に列挙する状況に対応していない：デ
マンドは、多数のデマンドノードから少数の目的地ノー
ドへ向けて流れる；ネットワークトポロジーは、ハブお
よびスポークのツリー、二つのハブを有するアクセスリ
ング、およびバックボーンリングを有し、それらは階層
的に連結されている；伝送費が装置費よりも大きな割合
を占める；並びに、ネットワークは数百のデマンドノー
ドを有することがある。
【００１０】
【課題を解決するための手段】本発明は、複数のデマン
ドノードと少なくとも一つの目的地ノードとを含む、同
期性光学ネットワーク（ＳＯＮＥＴ）のための階層的ア
ーキテクチャの設計方法を提供する。この設計方法にお
いて、デマンドノードにて通信トラフィックが発生し、
目的地ノードにて通信トラフィックが集結されスイッチ
へ転送される。この設計方法は：（ａ）複数のデマンド
ノードを、別個のデマンドノードグループに分割するス
テップと、（ｂ）バックボーンリングとの接続のための
リングハブとなるよう、各グループから少なくとも一つ
のノードを選択するステップと、（ｃ）少なくともその
リングハブと目的地ノードを含む、バックボーンリング
のトポロジーを設計するステップと、（ｄ）各デマンド
ノードグループに対してアクセスリングのトポロジーを
設計し、バックボーンリングのトポロジーとアクセスリ
ングのトポロジーとをもって初期ネットワークトポロジ
ーを構成するステップと、（ｅ）初期ネットワークトポ
ロジーに関連するコストを算定するステップと、（ｆ）
少なくとも一つの代替リングハブを選択し、新たな一式
のリングハブを用意するステップと、（ｇ）ステップ
（ｃ）〜ステップ（ｅ）を新たな一式のリングハブに適
用して実施し、その結果ネットワークコスト推計が減少
するかどうかを断定するステップと、（ｈ）最小限のコ
ストが係わるネットワークトポロジーが生成されるま
で、ステップ（ｆ）〜ステップ（ｇ）を繰り返すステッ
プと、を含む。本発明の他の態様は、ハブおよびスポー
クトポロジーの設計およびＳＯＮＥＴ伝送に係わる設計
に関するものである。
ドノードと少なくとも一つの目的地ノードとを含む、同
期性光学ネットワーク（ＳＯＮＥＴ）のための階層的ア
ーキテクチャの設計方法を提供する。この設計方法にお
いて、デマンドノードにて通信トラフィックが発生し、
目的地ノードにて通信トラフィックが集結されスイッチ
へ転送される。この設計方法は：（ａ）複数のデマンド
ノードを、別個のデマンドノードグループに分割するス
テップと、（ｂ）バックボーンリングとの接続のための
リングハブとなるよう、各グループから少なくとも一つ
のノードを選択するステップと、（ｃ）少なくともその
リングハブと目的地ノードを含む、バックボーンリング
のトポロジーを設計するステップと、（ｄ）各デマンド
ノードグループに対してアクセスリングのトポロジーを
設計し、バックボーンリングのトポロジーとアクセスリ
ングのトポロジーとをもって初期ネットワークトポロジ
ーを構成するステップと、（ｅ）初期ネットワークトポ
ロジーに関連するコストを算定するステップと、（ｆ）
少なくとも一つの代替リングハブを選択し、新たな一式
のリングハブを用意するステップと、（ｇ）ステップ
（ｃ）〜ステップ（ｅ）を新たな一式のリングハブに適
用して実施し、その結果ネットワークコスト推計が減少
するかどうかを断定するステップと、（ｈ）最小限のコ
ストが係わるネットワークトポロジーが生成されるま
で、ステップ（ｆ）〜ステップ（ｇ）を繰り返すステッ
プと、を含む。本発明の他の態様は、ハブおよびスポー
クトポロジーの設計およびＳＯＮＥＴ伝送に係わる設計
に関するものである。
【００１１】本発明の設計方法は、現存するネットワー
ク施設のごくわずかな部分しか使用せず、ネットワーク
の大部分を新たなリンクによって建設する場合、いわゆ
る「グリーンフィールド」状況において、特に有効であ
る。更に本発明による方法は、数百のデマンドノードを
有するネットワークの設計を効率的に成すものである。
ク施設のごくわずかな部分しか使用せず、ネットワーク
の大部分を新たなリンクによって建設する場合、いわゆ
る「グリーンフィールド」状況において、特に有効であ
る。更に本発明による方法は、数百のデマンドノードを
有するネットワークの設計を効率的に成すものである。
【００１２】
【発明の実施の形態】本発明は、ローカルアクセスネッ
トワークでの使用に適したＳＯＮＥＴアーキテクチャ設
計方法に関する。以下に、本発明の例としてＰＩＬ Ｓ
ＯＮＥＴアーキテクチャの設計に関して説明を行うが、
当業者であれば、本発明はT-H.Wu, "Fiber Network Ser
vice Survivability", Section 8.2.2., Artech House,
Boston (1992)に記載されている等の他のアーキテクチ
ャの設計にも適用可能であることが理解できると考え
る。
トワークでの使用に適したＳＯＮＥＴアーキテクチャ設
計方法に関する。以下に、本発明の例としてＰＩＬ Ｓ
ＯＮＥＴアーキテクチャの設計に関して説明を行うが、
当業者であれば、本発明はT-H.Wu, "Fiber Network Ser
vice 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 Wei
ghted Graph", Operations Research 16, (1968) p.955
-961に記載のあるｐメジアン発見的方法に基づく。この
アルゴリズムは、各アクセスリングの最大許容数のノー
ドに対する制約の実行にも適用できる。一組のクラスタ
ーの形成後、クラスター間で各ノードを切り替えて、ア
クセスリングあたりの最小数のノードに制約を実行する
ことができる。各クラスター内では一対のリングハブが
指定される（ステップ２０２）。リングハブは、ノード
とクラスターの地理的メジアンとの接近度に基づいて選
択される。
設計は、図２に示すフロー図に従って進められる。ま
ず、デマンドノードを個別のクラスター（集団）に分割
する（ステップ２００）。各クラスターは１つのアクセ
スリングを示す。クラスター化に使用可能なアルゴリズ
ムは、M.B.Tietz and P.Bart, "Heuristic Methods for
Estimating the Generalized Vertex Median of a Wei
ghted Graph", Operations Research 16, (1968) p.955
-961に記載のあるｐメジアン発見的方法に基づく。この
アルゴリズムは、各アクセスリングの最大許容数のノー
ドに対する制約の実行にも適用できる。一組のクラスタ
ーの形成後、クラスター間で各ノードを切り替えて、ア
クセスリングあたりの最小数のノードに制約を実行する
ことができる。各クラスター内では一対のリングハブが
指定される（ステップ２０２）。リングハブは、ノード
とクラスターの地理的メジアンとの接近度に基づいて選
択される。
【００２３】前のステップで一組のリングハブが指定さ
れると、巡回セールスマン問題（ＴＳＰ）発見的方法等
の公知の技術に従ってバックボーンリングトポロジーが
設計される（ステップ２０４）。バックボーンリング
は、リングハブとバックボーン上に存在するべく指定さ
れうる他のノードとを含む。次に、ステップ２００で各
クラスターに指定されたノード（リングハブを含む）に
基づき、ＴＳＰ発見的方法を用いて各クラスターごとに
アクセスリングトポロジーが設計される（ステップ２０
６）。リングハブ対が隣接するようにＰＩＬアーキテク
チャが設計されていれば、リングハブ対は１つの「スー
パーノード」として扱われる。１つ以上のアクセスリン
グが最大長制約に違反する場合、選択したノードを他の
クラスターに移動させてリングが再配列される。ここま
でに述べたステップに従ってリングトポロジーが設計さ
れると、そのコストが評価され、コストが以前の設計よ
りも改善されていることがわかれば、その結果が記憶さ
れる（ステップ２０８）。
れると、巡回セールスマン問題（ＴＳＰ）発見的方法等
の公知の技術に従ってバックボーンリングトポロジーが
設計される（ステップ２０４）。バックボーンリング
は、リングハブとバックボーン上に存在するべく指定さ
れうる他のノードとを含む。次に、ステップ２００で各
クラスターに指定されたノード（リングハブを含む）に
基づき、ＴＳＰ発見的方法を用いて各クラスターごとに
アクセスリングトポロジーが設計される（ステップ２０
６）。リングハブ対が隣接するようにＰＩＬアーキテク
チャが設計されていれば、リングハブ対は１つの「スー
パーノード」として扱われる。１つ以上のアクセスリン
グが最大長制約に違反する場合、選択したノードを他の
クラスターに移動させてリングが再配列される。ここま
でに述べたステップに従ってリングトポロジーが設計さ
れると、そのコストが評価され、コストが以前の設計よ
りも改善されていることがわかれば、その結果が記憶さ
れる（ステップ２０８）。
【００２４】その後、リングハブは、バックボーンの長
さを短縮する他のノードと交換される（ステップ２１
０）。このようなノードが見つかれば、最初のステップ
２０４へ戻って新たなリングハブの組に基づいてバック
ボーンリングが設計され、その後、ステップ２０６で対
応するアクセスリングが設計される。これらのステップ
２００〜２１０を複数回反復することによって解決策が
決まれば、既存のファイバーセグメントを考慮してスタ
イナーのＴＳＰ発見的方法に従ってトポロジー上のリン
グが設計しなおされる。スタイナーのＴＳＰ発見的方法
では、最終的な設計には前に選択されたデマンドノー
ド、リングハブ、およびネットワークノードを残し、一
方でその他のノード（既存のファイバーセグメントに接
続されたノード）が有利であればそれらのノードを組み
入れることが要求される。
さを短縮する他のノードと交換される（ステップ２１
０）。このようなノードが見つかれば、最初のステップ
２０４へ戻って新たなリングハブの組に基づいてバック
ボーンリングが設計され、その後、ステップ２０６で対
応するアクセスリングが設計される。これらのステップ
２００〜２１０を複数回反復することによって解決策が
決まれば、既存のファイバーセグメントを考慮してスタ
イナーのＴＳＰ発見的方法に従ってトポロジー上のリン
グが設計しなおされる。スタイナーのＴＳＰ発見的方法
では、最終的な設計には前に選択されたデマンドノー
ド、リングハブ、およびネットワークノードを残し、一
方でその他のノード（既存のファイバーセグメントに接
続されたノード）が有利であればそれらのノードを組み
入れることが要求される。
【００２５】最後に、できあがったバックボーンの長さ
が所定の最大長を上回っていれば、アクセスリングおよ
び任意のバックボーンデマンドノードが２つ以上の組に
クラスター化され、ステップ２０４および２１２に従っ
て各ノード組ごとに異なるトポロジー上のバックボーン
リングが設計される。
が所定の最大長を上回っていれば、アクセスリングおよ
び任意のバックボーンデマンドノードが２つ以上の組に
クラスター化され、ステップ２０４および２１２に従っ
て各ノード組ごとに異なるトポロジー上のバックボーン
リングが設計される。
【００２６】ハブおよびスポーク設計ハブおよびスポー
クトポロジーは、リングトポロジーの設計に続いて行わ
れる。ハブおよびスポークツリーに存在するべく事前に
選択されたデマンドノードはスポークノードと呼ばれ
る。各ツリーのルート（根）はアクセスリングまたはバ
ックボーンリングのいずれかにあるノードの中から選ば
れたノードでもよい。明白なことだが、スポークノード
数およびルートノードとなりうるノード数が多ければ、
莫大な数のツリーネットワークが設計可能となる。この
ような多数の設計の中から最適な設計を決定するには、
次の手順を用いることができる。これは図３に示す。
クトポロジーは、リングトポロジーの設計に続いて行わ
れる。ハブおよびスポークツリーに存在するべく事前に
選択されたデマンドノードはスポークノードと呼ばれ
る。各ツリーのルート（根）はアクセスリングまたはバ
ックボーンリングのいずれかにあるノードの中から選ば
れたノードでもよい。明白なことだが、スポークノード
数およびルートノードとなりうるノード数が多ければ、
莫大な数のツリーネットワークが設計可能となる。この
ような多数の設計の中から最適な設計を決定するには、
次の手順を用いることができる。これは図３に示す。
【００２７】まず、事前に選択したスポークノードをｐ
個のグループに分割する（ステップ３００）。クラスタ
ー化の規準には、上記のM.B. Teiz et al. に記載され
た発見的方法に基づくｐメジアンクラスター化技術等の
各種のクラスター化技術を用いることができる。各クラ
スターはクラスターの地理的メジアンを表す位置を含
む。次に、その地理的メジアンにもっとも近接したバッ
クボーンリングノードまたはアクセスリングノードの位
置が求められ、ルートノードとなる（ステップ３０
２）。こうして選択されたルートノードは予めルートと
なりうると規定されたノードからのみ選択されるもので
あり、それぞれのクラスターに加えられる（ステップ３
０４）。同じリングノードが２つ以上のクラスターに一
番近いルートノードとして機能する場合は、クラスター
同士が組み合わされる。各クラスターのトポロジーは、
Prim, R. C., "Shortest Connection Networks and Som
e Generalizations", Bell System Technical Journal,
36 (1957)pp. 1389-1401 に記載された等の標準の最小
スパニング木（ＭＳＴ）アルゴリズムに従って設計され
る（ステップ３０６）。ツリートポロジーが設計される
と、スポークノードは再びｐ個のグループに分けられる
が、ここではｐ値は初期値とは異なっている。最終的な
設計は、最短のツリー長を生成するｐ値に対応したもの
となる（ステップ３１０）。評価されるべきツリーの数
（クラスター分割グループ数ｐ）は、総スポークノード
数ｓによって異なる。ｓ値が小さければ（５０未満
等）、１からｓの間のすべてのｐ値が評価される。ｓ値
が大きければ、ｓ／２５からｓまでのｐ値が１０ごとに
評価される。より好適なｐ値を求めるには、求められた
最適値の近傍でｐ値をより精密に検索すればよい。ハブ
およびスポークトポロジーが選択されると、エンドノー
ドを各ツリーからそれに隣接するツリーへ移動させて、
ツリー全体長の一層の短縮がはかられる。
個のグループに分割する（ステップ３００）。クラスタ
ー化の規準には、上記のM.B. Teiz et al. に記載され
た発見的方法に基づくｐメジアンクラスター化技術等の
各種のクラスター化技術を用いることができる。各クラ
スターはクラスターの地理的メジアンを表す位置を含
む。次に、その地理的メジアンにもっとも近接したバッ
クボーンリングノードまたはアクセスリングノードの位
置が求められ、ルートノードとなる（ステップ３０
２）。こうして選択されたルートノードは予めルートと
なりうると規定されたノードからのみ選択されるもので
あり、それぞれのクラスターに加えられる（ステップ３
０４）。同じリングノードが２つ以上のクラスターに一
番近いルートノードとして機能する場合は、クラスター
同士が組み合わされる。各クラスターのトポロジーは、
Prim, R. C., "Shortest Connection Networks and Som
e Generalizations", Bell System Technical Journal,
36 (1957)pp. 1389-1401 に記載された等の標準の最小
スパニング木（ＭＳＴ）アルゴリズムに従って設計され
る（ステップ３０６）。ツリートポロジーが設計される
と、スポークノードは再びｐ個のグループに分けられる
が、ここではｐ値は初期値とは異なっている。最終的な
設計は、最短のツリー長を生成するｐ値に対応したもの
となる（ステップ３１０）。評価されるべきツリーの数
（クラスター分割グループ数ｐ）は、総スポークノード
数ｓによって異なる。ｓ値が小さければ（５０未満
等）、１からｓの間のすべてのｐ値が評価される。ｓ値
が大きければ、ｓ／２５からｓまでのｐ値が１０ごとに
評価される。より好適なｐ値を求めるには、求められた
最適値の近傍でｐ値をより精密に検索すればよい。ハブ
およびスポークトポロジーが選択されると、エンドノー
ドを各ツリーからそれに隣接するツリーへ移動させて、
ツリー全体長の一層の短縮がはかられる。
【００２８】「ＳＯＮＥＴトランスポート設計」ＳＯＮ
ＥＴトランスポート設計は、トポロジー上の各アクセス
リングおよびバックボーンリング中に積層型ＳＯＮＥＴ
を構築するものである。ＳＯＮＥＴトランスポート設計
のために、ハブおよびスポークトポロジー上のデマンド
ノードはハブおよびスポークツリーが根をおろすトポロ
ジー上のリングの一部とみなされる。使用する特定の設
計方法は、構築中のＳＯＮＥＴアーキテクチャによって
異なる。例えば、ＰＩＬアーキテクチャ等の階層リング
アーキテクチャは、低速一方向パス交換型ＯＣ−３リン
グを使用してアクセスリングならびにハブおよびスポー
クツリー上のデマンドノードにサービスする。その後、
ＯＣ−３リングはバックボーン上でサービスを行う高速
ＯＣ−４８リングの上にくる。バックボーンＯＣ−４８
リングもまた、この一方向パス交換モードで作動され
る。各ＯＣ−３リングは保有可能な総デマンド数および
リングがサービスするノード数に制限がある。本発明の
一実施形態では、ビンパッキング（bin-packing）発見
的アルゴリズムを用いて、デマンドノードを各アクセス
リング上の異なるＯＣ−３リングに割り当てる。ビンパ
ッキング発見的方法は、Johnson et al., "Worst-case
Performance Bounds for Simple One-dimensional pack
ing Algorithms", SIAM Journal of Computing, 3 (197
4) pp.299-325に記載された最初適合減少型発見的アル
ゴリズムを変形して得られる。変形したビンパッキング
発見的方法は、最初適合減少型（first-fit decreasin
g）発見的方法で求めたのと同数のリングを用いるが、
デマンドをリングに割り当てる際にデマンドがリング間
でより均等に分配されるようにする。この発見的方法は
必要最低数のＳＯＮＥＴリングをほぼ与えることができ
るので、リングハブ装置にかかるコストを最小限に抑え
られる。またバックボーントポロジーに存在するＯＣ−
４８リングも、ビンパッキングアルゴリズムに従って設
計できる。ＯＣ−４８リングの設計には、ＯＣ−３アク
セスリングからのデマンドおよびバックボーン上に直接
配置された任意のデマンドノードからのデマンドが入力
トラフィックとして使用される。ＯＣ−４８リングの必
要数を最小化することにより、サービスノードで必要な
装置量の低減も可能となる。
ＥＴトランスポート設計は、トポロジー上の各アクセス
リングおよびバックボーンリング中に積層型ＳＯＮＥＴ
を構築するものである。ＳＯＮＥＴトランスポート設計
のために、ハブおよびスポークトポロジー上のデマンド
ノードはハブおよびスポークツリーが根をおろすトポロ
ジー上のリングの一部とみなされる。使用する特定の設
計方法は、構築中のＳＯＮＥＴアーキテクチャによって
異なる。例えば、ＰＩＬアーキテクチャ等の階層リング
アーキテクチャは、低速一方向パス交換型ＯＣ−３リン
グを使用してアクセスリングならびにハブおよびスポー
クツリー上のデマンドノードにサービスする。その後、
ＯＣ−３リングはバックボーン上でサービスを行う高速
ＯＣ−４８リングの上にくる。バックボーンＯＣ−４８
リングもまた、この一方向パス交換モードで作動され
る。各ＯＣ−３リングは保有可能な総デマンド数および
リングがサービスするノード数に制限がある。本発明の
一実施形態では、ビンパッキング（bin-packing）発見
的アルゴリズムを用いて、デマンドノードを各アクセス
リング上の異なるＯＣ−３リングに割り当てる。ビンパ
ッキング発見的方法は、Johnson et al., "Worst-case
Performance Bounds for Simple One-dimensional pack
ing Algorithms", SIAM Journal of Computing, 3 (197
4) pp.299-325に記載された最初適合減少型発見的アル
ゴリズムを変形して得られる。変形したビンパッキング
発見的方法は、最初適合減少型（first-fit decreasin
g）発見的方法で求めたのと同数のリングを用いるが、
デマンドをリングに割り当てる際にデマンドがリング間
でより均等に分配されるようにする。この発見的方法は
必要最低数のＳＯＮＥＴリングをほぼ与えることができ
るので、リングハブ装置にかかるコストを最小限に抑え
られる。またバックボーントポロジーに存在するＯＣ−
４８リングも、ビンパッキングアルゴリズムに従って設
計できる。ＯＣ−４８リングの設計には、ＯＣ−３アク
セスリングからのデマンドおよびバックボーン上に直接
配置された任意のデマンドノードからのデマンドが入力
トラフィックとして使用される。ＯＣ−４８リングの必
要数を最小化することにより、サービスノードで必要な
装置量の低減も可能となる。
【図１】 パス・イン・ラインＳＯＮＥＴネットワーク
の一例を示す簡易図である。
の一例を示す簡易図である。
【図２】 本発明に従うリングトポロジーの設計方法を
示すフロー図である。
示すフロー図である。
【図３】 本発明に従うハブおよびスポークトポロジー
の設計方法を示すフロー図である。
の設計方法を示すフロー図である。
１０１ アクセスリング、１０５ バックボーンリン
グ、１０７，１０９ リングハブ、１１０ ハブおよび
スポーク。
グ、１０７，１０９ リングハブ、１１０ ハブおよび
スポーク。
フロントページの続き (72)発明者 モーハン ガワンド アメリカ合衆国 ニュージャージー州 イ ースト ウィンザー ダッチ ネック ロ ード 461 (72)発明者 ジョン ジー ケリンスウィッツ アメリカ合衆国 ニュージャージー州 ウ ェイサイド シャーリー アン ドライブ 17 (72)発明者 ハナン ルス アメリカ合衆国 ニュージャージー州 マ ルボロ トルーマン ドライブ 14 (72)発明者 モーシュ ビー ローゼンウェイン アメリカ合衆国 ニュージャージー州 ロ ング ブランチ レノックス アベニュー 237 (72)発明者 ロマナス ロイ アメリカ合衆国 ニュージャージー州 ブ リッジウォーター リンバーガー ドライ ブ ４
Claims (11)
- 【請求項１】 複数のデマンドノードと少なくとも一つ
の目的地ノードとを含む、同期性光学ネットワーク（Ｓ
ＯＮＥＴ）のための階層的アーキテクチャの設計方法で
あって、前記複数のデマンドノードにて通信トラフィッ
クが発生し、前記少なくとも一つの目的地ノードにて前
記通信トラフィックが集結されスイッチへ転送される設
計方法において、 ａ．前記複数のデマンドノードを、別個のデマンドノー
ドグループに分割するステップと、 ｂ．バックボーンリングとの接続のためのリングハブと
なるよう、各前記グループから少なくとも一つのノード
を選択するステップと、 ｃ．少なくとも前記リングハブと前記少なくとも一つの
目的地ノードとを含む、バックボーンリングトポロジー
を設計するステップと、 ｄ．各前記デマンドノードグループに対してアクセスリ
ングトポロジーを設計し、前記バックボーンリングトポ
ロジーと前記アクセスリングトポロジーとをもって初期
ネットワークトポロジーを構成するステップと、 ｅ．前記初期ネットワークトポロジーに関連するコスト
を算定するステップと、 ｆ．少なくとも一つの代替リングハブを選択し、新たな
一式のリングハブを用意するステップと、 ｇ．ステップ（ｃ）〜ステップ（ｅ）を前記新たな一式
のリングハブに適用して実施し、その結果ネットワーク
コスト推計が減少するかどうかを断定するステップと、 ｈ．最小限のコストが係わるネットワークトポロジーが
生成されるまで、ステップ（ｆ）〜ステップ（ｇ）を繰
り返すステップと、 を有することを特徴とする設計方法。 - 【請求項２】 請求項１に記載の方法であって、選択さ
れたデマンドノードが、ハブおよびスポークによるツリ
ートポロジーに属するスポークノードとなるよう事前に
選択される方法において更に、 ｉ．前記選択されたデマンドノードを、第一の複数のグ
ループに分割するステップと、 ｊ．各前記第一の複数のグループの地理的メジアンを表
す位置を検出し、各グループにおいて前記位置に、前記
バックボーントポロジーまたはアクセスリングトポロジ
ーのどちらかに含まれる前記ノードの中から選ばれるル
ートノードを関連させるステップであって、各前記ルー
トノードは各グループにおいて前記地理的メジアン位置
に最も距離的に近いノードであるステップと、 ｋ．各ルートノードが、自身が属するリングとそのリン
グに関係するノードグループを表すツリーとを連結する
よう、各前記第一の複数のグループに対してツリートポ
ロジーを設計するステップと、 ｌ．前記選択されたデマンドノードを、前記第一の複数
のグループとは異なった第二の複数のグループに分割
し、ステップ（ｊ）〜ステップ（ｋ）を前記第二の複数
のグループに適用して実施するステップと、 ｍ．最短長を有するツリートポロジーが生成されるま
で、ステップ（ｌ）を繰り返すステップと、 を有することを特徴とする方法。 - 【請求項３】 請求項２に記載の方法において更に、ビ
ンパッキング発見的方法に従って、各ハブおよびスポー
クトポロジー、アクセスリングトポロジー、並びにバッ
クボーンリングトポロジーに対してＳＯＮＥＴ伝送リン
グを設計するステップを有する方法。 - 【請求項４】 請求項３に記載の方法において、前記ビ
ンパッキング発見的手法は、最初適合減少型発見的方法
であることを特徴とする方法。 - 【請求項５】 請求項１に記載の方法において、ステッ
プ（ｂ）は、各前記グループにおいてリングハブとする
よう一対の隣接するノードを選択し、前記階層的アーキ
テクチャがパスインラインアーキテクチャになるよう構
成するステップを含むことを特徴とする方法。 - 【請求項６】 請求項３に記載の方法において、前記ア
クセスリングトポロジーは、バックボーンリングトポロ
ジーよりも低いスピードのＳＯＮＥＴリングをサポート
することを特徴とする方法。 - 【請求項７】 請求項１に記載の方法において、前記複
数のデマンドノードはステップ（ａ）において、ｐ−メ
ジアン発見的方法に従って分割されることを特徴とする
方法。 - 【請求項８】 請求項１に記載の方法において、前記別
個のデマンドノードグループは各々、所定の最大数より
も少ない数のノードを含むことを特徴とする方法。 - 【請求項９】 請求項５に記載の方法において、該選択
された隣接するデマンドノードは互いに、所定の最小限
の距離によって離れていることを特徴とする方法。 - 【請求項１０】 請求項１に記載の方法において、前記
最小限のコストが係わるネットワークトポロジーが生成
された後、前記アクセスリングトポロジーおよび前記バ
ックボーンリングトポロジーを再設計し、先在するリン
クを組み込むステップを実施することを含む方法。 - 【請求項１１】 請求項１０に記載の方法において、前
記再設計のステップは、スタイナーの巡回セールスマン
問題による発見的方法に従って実施されることを特徴と
する方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/899,103 US6061335A (en) | 1997-07-24 | 1997-07-24 | Method for designing SONET ring networks suitable for local access |
| US08/899,103 | 1997-07-24 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JPH11187054A true JPH11187054A (ja) | 1999-07-09 |
| JPH11187054A5 JPH11187054A5 (ja) | 2005-10-27 |
| JP4092016B2 JP4092016B2 (ja) | 2008-05-28 |
Family
ID=25410484
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20943798A Expired - Fee Related JP4092016B2 (ja) | 1997-07-24 | 1998-07-24 | ローカルアクセスに適したｓｏｎｅｔリングネットワークの設計方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6061335A (ja) |
| EP (1) | EP0893894A3 (ja) |
| JP (1) | JP4092016B2 (ja) |
| CA (1) | CA2243777A1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2023073950A1 (ja) * | 2021-10-29 | 2023-05-04 | 日本電信電話株式会社 | ループ配線を設計するための装置、方法及びプログラム |
Families Citing this family (34)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6728205B1 (en) * | 1997-02-19 | 2004-04-27 | Massachusetts Institute Of Technology | Method and apparatus for automatic protection switching |
| US6396852B1 (en) * | 1997-11-18 | 2002-05-28 | Jane Marie Simmons | Ring bundling in the design of rings for telecommunications networks |
| US6463033B1 (en) * | 1998-05-04 | 2002-10-08 | Lucent Technologies Inc. | Dual hubbed tree architecture for a communication network |
| FR2779844B1 (fr) * | 1998-06-12 | 2001-07-27 | Ela Medical Sa | Structure d'interconnexion entre organes adressables d'un microcalculateur, notamment pour dispositif medical implantable actif tel que stimulateur ou defibrillateur cardiaque |
| US7009934B1 (en) * | 1999-03-01 | 2006-03-07 | Ciena Corporation | Method and apparatus for rerouting an optical network upon fault |
| US6819662B1 (en) * | 1999-04-29 | 2004-11-16 | Telecommunications Research Laboratories | Method for protecting a telecommunications network |
| US6355886B1 (en) * | 1999-05-21 | 2002-03-12 | Tycom (Us) Inc. | Undersea trunk-and-branch logical ring networks |
| US6667981B1 (en) * | 1999-06-30 | 2003-12-23 | Worldcom, Inc. | Method of partitioning traffic and placing add/drop multiplexers in a stacked ring network |
| EP1132844A3 (en) * | 2000-03-02 | 2002-06-05 | Telseon IP Services Inc. | E-commerce system facilitating service networks including broadband communication service networks |
| US6963575B1 (en) | 2000-06-07 | 2005-11-08 | Yipes Enterprise Services, Inc. | Enhanced data switching/routing for multi-regional IP over fiber network |
| US20020036988A1 (en) * | 2000-07-31 | 2002-03-28 | Network Design Tools, Inc. | Method for designing rings in telecommunications network |
| KR100659719B1 (ko) * | 2000-12-30 | 2006-12-21 | 에스케이 텔레콤주식회사 | 컴퓨팅 장치에서 최소 비용의 통신망 구축을 위한 링 기반통신망 설계 방법 |
| US7133410B2 (en) * | 2001-02-12 | 2006-11-07 | Tellabs Operations, Inc. | Method and system for designing ring-based telecommunications networks |
| US20030009598A1 (en) * | 2001-04-12 | 2003-01-09 | Gunluk Oktay Necip | Method for designing demand-sensitive rings |
| EP1253746A3 (de) * | 2001-04-24 | 2005-12-07 | Siemens Aktiengesellschaft | Multicast-Übertragungsverfahren und Multicast-Übertragungssystem |
| JP4777552B2 (ja) * | 2001-08-02 | 2011-09-21 | 富士通株式会社 | ネットワークにおけるノード装置およびネットワークシステム |
| US7346709B2 (en) * | 2002-08-28 | 2008-03-18 | Tellabs Operations, Inc. | Methods for assigning rings in a network |
| US8463947B2 (en) * | 2002-08-28 | 2013-06-11 | Tellabs Operations, Inc. | Method of finding rings for optimal routing of digital information |
| US20050095008A1 (en) * | 2003-11-04 | 2005-05-05 | International Business Machines Corporation | Configurator tool for optical networking devices |
| US7577245B2 (en) * | 2004-07-29 | 2009-08-18 | At&T Intellectual Property I, L.P. | Method of detecting misrouted inter-office transport facility routes in a telecommunications system |
| US7580837B2 (en) | 2004-08-12 | 2009-08-25 | At&T Intellectual Property I, L.P. | System and method for targeted tuning module of a speech recognition system |
| US20060117020A1 (en) * | 2004-12-01 | 2006-06-01 | John Toebes | Arrangement for selecting a server to provide distributed services from among multiple servers based on a location of a client device |
| US7864942B2 (en) | 2004-12-06 | 2011-01-04 | At&T Intellectual Property I, L.P. | System and method for routing calls |
| US7242751B2 (en) | 2004-12-06 | 2007-07-10 | Sbc Knowledge Ventures, L.P. | System and method for speech recognition-enabled automatic call routing |
| US7751551B2 (en) | 2005-01-10 | 2010-07-06 | At&T Intellectual Property I, L.P. | System and method for speech-enabled call routing |
| US7468955B2 (en) * | 2005-04-11 | 2008-12-23 | At&T Intellectual Property I, L.P. | System and method of defining a modified UPSR SONET network including sub-tending rings |
| US7657020B2 (en) | 2005-06-03 | 2010-02-02 | At&T Intellectual Property I, Lp | Call routing system and method of using the same |
| US7472189B2 (en) * | 2005-07-21 | 2008-12-30 | Sbc Knowledge Ventures, L.P. | Method of collecting data from network elements |
| US20070050485A1 (en) * | 2005-08-30 | 2007-03-01 | Sbc Knowledge Ventures, L.P. | System and method for designing multi-ring communication networks |
| CN100365999C (zh) * | 2005-12-01 | 2008-01-30 | 中讯邮电咨询设计院 | 应用于光传输通信网络对业务进行分组的设计方法 |
| US8040820B2 (en) * | 2007-03-06 | 2011-10-18 | Cisco Technology, Inc. | Modelling service flows in dynamic access domains |
| EP1995916A1 (de) * | 2007-05-24 | 2008-11-26 | Siemens Schweiz AG | Einrichtung zur Steuerung und/oder Überwachung und Datenabfrage von entlang eines Verkehrsnetzwerkes angeordneten dezentralen Funktionseinheiten |
| CN111178421B (zh) * | 2019-12-25 | 2023-10-20 | 贝壳技术有限公司 | 检测用户状态的方法、装置、介质以及电子设备 |
| CN112954609B (zh) * | 2021-02-09 | 2023-09-05 | 北京交通大学 | 一种基于骨干环的分布式地理位置服务方法 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5564021A (en) * | 1994-05-31 | 1996-10-08 | Us West Technologies, Inc. | Method for assigning inter-nodal traffic loads to channels in sonet rings |
| US5515367A (en) * | 1990-05-08 | 1996-05-07 | U S West Advanced Technologies, Inc. | Method and system for planning and installing communication networks |
| US5546542A (en) * | 1993-11-29 | 1996-08-13 | Bell Communications Research, Inc. | Method for efficiently determining the direction for routing a set of anticipated demands between selected nodes on a ring communication network |
| US5923646A (en) * | 1996-08-30 | 1999-07-13 | Nynex Science & Technology | Method for designing or routing a self-healing ring in a communications network and a self-healing ring routed in accordance with the method |
-
1997
- 1997-07-24 US US08/899,103 patent/US6061335A/en not_active Expired - Fee Related
-
1998
- 1998-07-20 EP EP98305771A patent/EP0893894A3/en not_active Withdrawn
- 1998-07-21 CA CA002243777A patent/CA2243777A1/en not_active Abandoned
- 1998-07-24 JP JP20943798A patent/JP4092016B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2023073950A1 (ja) * | 2021-10-29 | 2023-05-04 | 日本電信電話株式会社 | ループ配線を設計するための装置、方法及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2243777A1 (en) | 1999-01-24 |
| EP0893894A3 (en) | 1999-10-20 |
| US6061335A (en) | 2000-05-09 |
| EP0893894A2 (en) | 1999-01-27 |
| JP4092016B2 (ja) | 2008-05-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4092016B2 (ja) | ローカルアクセスに適したｓｏｎｅｔリングネットワークの設計方法 | |
| US5515367A (en) | Method and system for planning and installing communication networks | |
| Bouillet et al. | Lightpath re-optimization in mesh optical networks | |
| KR100973695B1 (ko) | 노드 장치 및 스패닝 트리를 이용한 최단 경로 결정 방법 | |
| US7313328B2 (en) | Node used in photonic network, and photonic network | |
| CN112532518B (zh) | 一种段路由策略的路径选择方法及装置 | |
| US8660010B2 (en) | System and method for second order multi-layer traffic grooming for optical network optimization | |
| JP4837765B2 (ja) | 多階層資源転送網経路計算に必要な資源管理及び再帰的経路計算方法及び装置 | |
| WO2007088341A1 (en) | Method and device for connecting separate spanning tree networks | |
| EP1993223B1 (en) | Method and device of group broadcast protection in wdm optical network | |
| CN101026482A (zh) | Wdm光网络中基于共享风险链路组的网络保护方法 | |
| Wasem et al. | Survivable SONET networks/spl mdash/design methodology | |
| Zhang et al. | Dynamic traffic grooming algorithms for reconfigurable SONET over WDM networks | |
| CN115277430B (zh) | 一种链路故障概率量化方法及sdn控制器部署方法 | |
| US7668184B2 (en) | Method and system for designing ring-based telecommunications networks | |
| US20110150470A1 (en) | Procedure, apparatus, system, and computer program for network planning | |
| EP1422888A2 (en) | Constraint based routing with irregular metrics | |
| Fortz et al. | A tabu search algorithm for self-healing ring network design | |
| Hwang et al. | Multiple shared backup cycles for survivable optical mesh networks | |
| US20030023706A1 (en) | Apparatus and method for optimizing telecommunications network design using weighted span classification and rerouting rings that fail to pass a cost therehold | |
| Kos et al. | Topological planning of communication networks | |
| JP2003333090A (ja) | マルチレイヤ光ネットワークおよび当該ネットワークにおけるトラヒックエンジニアリング方法 | |
| US20030035379A1 (en) | Apparatus and method for optimizing telecommunication network design using weighted span classification | |
| Hashiguchi et al. | Techniques for agile network re-optimization following traffic fluctuations | |
| US7894469B2 (en) | Generic SONET/SDH time slot selection algorithm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050722 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050722 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20050722 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20070918 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070925 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071219 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20080205 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080303 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110307 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110307 Year of fee payment: 3 |
|
| LAPS | Cancellation because of no payment of annual fees |