JPH05207068A - パケット網設計方式 - Google Patents
パケット網設計方式Info
- Publication number
- JPH05207068A JPH05207068A JP1154392A JP1154392A JPH05207068A JP H05207068 A JPH05207068 A JP H05207068A JP 1154392 A JP1154392 A JP 1154392A JP 1154392 A JP1154392 A JP 1154392A JP H05207068 A JPH05207068 A JP H05207068A
- Authority
- JP
- Japan
- Prior art keywords
- unit
- routing
- node
- virtual
- function
- 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.)
- Pending
Links
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【目的】 パケット網の設計において、設備コストを減
少させる。 【構成】 論理網設計部１０１において、仮想回線ルー
ティング設計を行い、仮想パス容量を求め、物理網設計
部１０２において、仮想パスルーティング設計を行い、
物理リンク容量を求め、摂動部１０３において仮想回線
ルーティングと仮想パスルーティングの最適化を行い、
経済的な設計を行う。
少させる。 【構成】 論理網設計部１０１において、仮想回線ルー
ティング設計を行い、仮想パス容量を求め、物理網設計
部１０２において、仮想パスルーティング設計を行い、
物理リンク容量を求め、摂動部１０３において仮想回線
ルーティングと仮想パスルーティングの最適化を行い、
経済的な設計を行う。
Description
【０００１】
【産業上の利用分野】本発明はパケット網を経済的に構
築するためのパケット網の設計方式に関するものであ
る。
築するためのパケット網の設計方式に関するものであ
る。
【０００２】
【従来の技術】従来、通信網の設計では、例えば同一出
願人による特願平０１−２１６５０２号明細書に記載の
ネットワーク設計方式によれば、図１２に示すように、
サービスごとに交換ルーティングの設計を行い回線容量
を算出する論理網設計部１、サービス間の回線容量を合
計するインタフェース部２、インタフェース部２で得ら
れた回線容量をもとにクロスコネクトルーティングの設
計を行い物理リンク容量を算出する物理網設計部３から
なる方式をとっている。
願人による特願平０１−２１６５０２号明細書に記載の
ネットワーク設計方式によれば、図１２に示すように、
サービスごとに交換ルーティングの設計を行い回線容量
を算出する論理網設計部１、サービス間の回線容量を合
計するインタフェース部２、インタフェース部２で得ら
れた回線容量をもとにクロスコネクトルーティングの設
計を行い物理リンク容量を算出する物理網設計部３から
なる方式をとっている。
【０００３】
【発明が解決しようとする課題】上述した従来のネット
ワーク設計方式では、マルチサービスを単一の交換方式
で扱うことのできるパケット交換網であるＡＴＭ網の設
計は扱っていない。パケット網における、呼ごとにパケ
ット交換機により端末間を結んで設定される仮想回線の
ルーティングとクロスコネクトによりパケット交換機間
あるいは端末間を結ぶ、仮想回線の束からなる仮想パス
のルーティングは、上述の従来のネットワーク設計方式
では、それぞれ交換ルーティングとクロスコネクトルー
ティングに対応して考えられる。しかし従来方式では交
換ルーティングを含む論理網と、クロスコネクトルーテ
ィングを含む物理網の設計が独立に行われているため
に、マルチサービスを交換するパケット網においてサー
ビスの性質によって交換ルーティングとクロスコネクト
ルーティングの適用領域が異なるという性質を生かした
設計ができないという問題がある。
ワーク設計方式では、マルチサービスを単一の交換方式
で扱うことのできるパケット交換網であるＡＴＭ網の設
計は扱っていない。パケット網における、呼ごとにパケ
ット交換機により端末間を結んで設定される仮想回線の
ルーティングとクロスコネクトによりパケット交換機間
あるいは端末間を結ぶ、仮想回線の束からなる仮想パス
のルーティングは、上述の従来のネットワーク設計方式
では、それぞれ交換ルーティングとクロスコネクトルー
ティングに対応して考えられる。しかし従来方式では交
換ルーティングを含む論理網と、クロスコネクトルーテ
ィングを含む物理網の設計が独立に行われているため
に、マルチサービスを交換するパケット網においてサー
ビスの性質によって交換ルーティングとクロスコネクト
ルーティングの適用領域が異なるという性質を生かした
設計ができないという問題がある。
【０００４】本発明の目的は、このような問題を解決し
たパケット網設計方式を提供することにある。
たパケット網設計方式を提供することにある。
【０００５】
【課題を解決するための手段】第１の発明は、クロスコ
ネクト装置を伝送リンクを用いて接続しクロスコネクト
網を構成し、その上に論理的にパケット交換網を実現す
るマルチサービス通信ネットワークにおいて、呼ごとに
パケット交換機により端末間を結んで設定される仮想回
線の設計パラメータとして仮想回線ルーティング、また
クロスコネクトによりパケット交換機間あるいは端末間
を結ぶ、仮想回線の束からなる仮想パスの設計パラメー
タとして仮想パスルーティングを考慮し、セル品質、呼
品質の制約の下で目的関数の最適化を計るパケット網設
計方式において、前記仮想回線のルーティング設計を行
い、前記仮想パス容量を算出する論理網設計部と、前記
仮想パス容量から前記仮想パスルーティング設計を行
い、物理リンク容量を算出する物理網設計部と、前記仮
想回線ルーティングと、仮想パスルーティングの間の最
適化を行う摂動部からなることを特徴とする。
ネクト装置を伝送リンクを用いて接続しクロスコネクト
網を構成し、その上に論理的にパケット交換網を実現す
るマルチサービス通信ネットワークにおいて、呼ごとに
パケット交換機により端末間を結んで設定される仮想回
線の設計パラメータとして仮想回線ルーティング、また
クロスコネクトによりパケット交換機間あるいは端末間
を結ぶ、仮想回線の束からなる仮想パスの設計パラメー
タとして仮想パスルーティングを考慮し、セル品質、呼
品質の制約の下で目的関数の最適化を計るパケット網設
計方式において、前記仮想回線のルーティング設計を行
い、前記仮想パス容量を算出する論理網設計部と、前記
仮想パス容量から前記仮想パスルーティング設計を行
い、物理リンク容量を算出する物理網設計部と、前記仮
想回線ルーティングと、仮想パスルーティングの間の最
適化を行う摂動部からなることを特徴とする。
【０００６】第２の発明によれば、前記摂動部は、交換
ノードの重みを計算する交換ノードの重み計算部と、前
記交換ノードの重み計算部で求めた重みを用いて最も重
みの重い交換ノードを捜す変更交換ノード選択部と、処
理の終了あるいは継続を判定する全ノード選択判定部
と、前記変更交換ノード選択部で選択されたノードの交
換機能をクロスコネクト機能に変更するノード機能変更
部と、変更前後の目的関数値を比較する目的関数改善効
果判定部と、前記ノード機能変更部で変更されたノード
の機能を元に戻すノード機能再変更部とからなり、前記
仮想回線ルーティングおよび仮想パスルーティングを決
めることを特徴とする。
ノードの重みを計算する交換ノードの重み計算部と、前
記交換ノードの重み計算部で求めた重みを用いて最も重
みの重い交換ノードを捜す変更交換ノード選択部と、処
理の終了あるいは継続を判定する全ノード選択判定部
と、前記変更交換ノード選択部で選択されたノードの交
換機能をクロスコネクト機能に変更するノード機能変更
部と、変更前後の目的関数値を比較する目的関数改善効
果判定部と、前記ノード機能変更部で変更されたノード
の機能を元に戻すノード機能再変更部とからなり、前記
仮想回線ルーティングおよび仮想パスルーティングを決
めることを特徴とする。
【０００７】第３の発明によれば、前記摂動部は、クロ
スコネクトノードの接続リンクの重みを計算するクロス
コネクトノードの重み計算部と、前記クロスコネクトノ
ードの重み計算部で求めた重みを用いて最も接続リンク
の重みの重いクロスコネクトノードを捜す変更クロスコ
ネクトノード選択部と、処理の終了あるいは継続を判定
する全ノード選択判定部と、前記変更クロスコネクトノ
ード選択部で選択されたノードのクロスコネクト機能を
交換機能に変更するノード機能変更部と、変更前後の目
的関数値を比較する目的関数改善効果判定部と、前記ノ
ード機能変更部で変更されたノード機能を元に戻すノー
ド機能再変更部とからなり、前記仮想回線ルーティング
および仮想パスルーティングを決めることを特徴とす
る。
スコネクトノードの接続リンクの重みを計算するクロス
コネクトノードの重み計算部と、前記クロスコネクトノ
ードの重み計算部で求めた重みを用いて最も接続リンク
の重みの重いクロスコネクトノードを捜す変更クロスコ
ネクトノード選択部と、処理の終了あるいは継続を判定
する全ノード選択判定部と、前記変更クロスコネクトノ
ード選択部で選択されたノードのクロスコネクト機能を
交換機能に変更するノード機能変更部と、変更前後の目
的関数値を比較する目的関数改善効果判定部と、前記ノ
ード機能変更部で変更されたノード機能を元に戻すノー
ド機能再変更部とからなり、前記仮想回線ルーティング
および仮想パスルーティングを決めることを特徴とす
る。
【０００８】第４の発明によれば、前記摂動部は、仮想
回線の重みを計算する仮想回線の重み計算部と、前記仮
想回線の重み計算部で求めた重みを用いて最も重みの重
い仮想回線を捜す変更仮想回線選択部と、処理の終了あ
るいは継続を判定する全仮想回線選択判定部と、前記変
更仮想回線選択部で選択された仮想回線の仮想回線ルー
ティングを仮想パスルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
回線の重みを計算する仮想回線の重み計算部と、前記仮
想回線の重み計算部で求めた重みを用いて最も重みの重
い仮想回線を捜す変更仮想回線選択部と、処理の終了あ
るいは継続を判定する全仮想回線選択判定部と、前記変
更仮想回線選択部で選択された仮想回線の仮想回線ルー
ティングを仮想パスルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
【０００９】第５の発明によれば、前記摂動部は、仮想
パスの重みを計算する仮想パスの重み計算部と、前記仮
想パスの重み計算部で求めた重みを用いて最も重みの重
い仮想パスを捜す変更仮想パス選択部と、処理の終了あ
るいは継続を判定する全仮想パス選択判定部と、前記変
更仮想パス選択部で選択された仮想パスの仮想パスルー
ティングを仮想回線ルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
パスの重みを計算する仮想パスの重み計算部と、前記仮
想パスの重み計算部で求めた重みを用いて最も重みの重
い仮想パスを捜す変更仮想パス選択部と、処理の終了あ
るいは継続を判定する全仮想パス選択判定部と、前記変
更仮想パス選択部で選択された仮想パスの仮想パスルー
ティングを仮想回線ルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
【００１０】第６の発明によれば、前記摂動部は、交換
ノードの重みを計算する交換ノードの重み計算部と、前
記交換ノードの重み計算部で求めた重みを用いて最も重
みの重い交換ノードを捜す変更交換ノード選択部と、処
理の終了あるいは継続を判定する選択ノードの重み判定
部と、前記変更交換ノード選択部で選択されたノードの
交換機能をクロスコネクト機能に変更するノード機能変
更部と、変更前後の目的関数値を比較する目的関数改善
効果判定部と、前記ノード機能変更部で変更されたノー
ドの機能を元に戻すノード機能再変更部とからなり、前
記仮想回線ルーティングおよび仮想パスルーティングを
決めることを特徴とする。
ノードの重みを計算する交換ノードの重み計算部と、前
記交換ノードの重み計算部で求めた重みを用いて最も重
みの重い交換ノードを捜す変更交換ノード選択部と、処
理の終了あるいは継続を判定する選択ノードの重み判定
部と、前記変更交換ノード選択部で選択されたノードの
交換機能をクロスコネクト機能に変更するノード機能変
更部と、変更前後の目的関数値を比較する目的関数改善
効果判定部と、前記ノード機能変更部で変更されたノー
ドの機能を元に戻すノード機能再変更部とからなり、前
記仮想回線ルーティングおよび仮想パスルーティングを
決めることを特徴とする。
【００１１】第７の発明によれば、前記摂動部は、クロ
スコネクトノードの接続リンクの重みを計算するクロス
コネクトノードの重み計算部と、前記クロスコネクトノ
ードの重み計算部で求めた重みを用いて最も接続リンク
の重みの重いクロスコネクトノードを捜す変更クロスコ
ネクトノード選択部と、処理の終了あるいは継続を判定
する選択ノードの重み判定部と、前記変更クロスコネク
トノード選択部で選択されたノードのクロスコネクト機
能を交換機能に変更するノード機能変更部と、変更前後
の目的関数値を比較する目的関数改善効果判定部と、前
記ノード機能変更部で変更されたノード機能を元に戻す
ノード機能再変更部とからなり、前記仮想回線ルーティ
ングおよび仮想パスルーティングを決めることを特徴と
する。
スコネクトノードの接続リンクの重みを計算するクロス
コネクトノードの重み計算部と、前記クロスコネクトノ
ードの重み計算部で求めた重みを用いて最も接続リンク
の重みの重いクロスコネクトノードを捜す変更クロスコ
ネクトノード選択部と、処理の終了あるいは継続を判定
する選択ノードの重み判定部と、前記変更クロスコネク
トノード選択部で選択されたノードのクロスコネクト機
能を交換機能に変更するノード機能変更部と、変更前後
の目的関数値を比較する目的関数改善効果判定部と、前
記ノード機能変更部で変更されたノード機能を元に戻す
ノード機能再変更部とからなり、前記仮想回線ルーティ
ングおよび仮想パスルーティングを決めることを特徴と
する。
【００１２】第８の発明によれば、前記摂動部は、仮想
回線の重みを計算する仮想回線の重み計算部と、前記仮
想回線の重み計算部で求めた重みを用いて最も重みの重
い仮想回線を捜す変更仮想回線選択部と、処理の終了あ
るいは継続を判定する選択仮想回線の重み判定部と、前
記変更仮想回線選択部で選択された仮想回線の仮想ルー
ティングを仮想パスルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
回線の重みを計算する仮想回線の重み計算部と、前記仮
想回線の重み計算部で求めた重みを用いて最も重みの重
い仮想回線を捜す変更仮想回線選択部と、処理の終了あ
るいは継続を判定する選択仮想回線の重み判定部と、前
記変更仮想回線選択部で選択された仮想回線の仮想ルー
ティングを仮想パスルーティングに変更するルーティン
グ機能変更部と、変更前後の目的関数値を比較する目的
関数改善効果判定部と、前記ルーティング機能変更部で
変更されたルーティング機能を元に戻すルーティング機
能再変更部とからなり、前記仮想回線ルーティングおよ
び仮想パスルーティングを決めることを特徴とする。
【００１３】第９の発明によれば、前記摂動部は、仮想
パスの重みを計算する仮想パスの重み計算部と、前記仮
想パスの重み計算部で求めた重みを用いて最も重みの重
い仮想パスを捜す変更仮想パス選択部と、処理の終了あ
るいは継続を判定する選択仮想パスの重み判定部と、前
記変更仮想パス選択部で選択された仮想パスの仮想パス
ルーティングを仮想回線ルーティングに変更するルーテ
ィング機能変更部と、変更前後の目的関数値を比較する
目的関数改善効果判定部と、前記ルーティング機能変更
部で変更されたルーティング機能を元に戻すルーティン
グ機能再変更部とからなり、前記仮想回線ルーティング
および仮想パスルーティングを決めることを特徴とす
る。
パスの重みを計算する仮想パスの重み計算部と、前記仮
想パスの重み計算部で求めた重みを用いて最も重みの重
い仮想パスを捜す変更仮想パス選択部と、処理の終了あ
るいは継続を判定する選択仮想パスの重み判定部と、前
記変更仮想パス選択部で選択された仮想パスの仮想パス
ルーティングを仮想回線ルーティングに変更するルーテ
ィング機能変更部と、変更前後の目的関数値を比較する
目的関数改善効果判定部と、前記ルーティング機能変更
部で変更されたルーティング機能を元に戻すルーティン
グ機能再変更部とからなり、前記仮想回線ルーティング
および仮想パスルーティングを決めることを特徴とす
る。
【００１４】
【実施例】次に図面を参照して本発明の実施例について
説明する。図１は第１の発明のパケット網設計方式の一
実施例を示したものである。
説明する。図１は第１の発明のパケット網設計方式の一
実施例を示したものである。
【００１５】本実施例のパケット網ではＡＴＭ網を考慮
し、トラヒックに対して、直通あるいはパケット交換機
により中継される仮想回線ルートを設定し、仮想回線の
束に対して、直通あるいはクロスコネクト装置により中
断される仮想パスを設定して接続を実現する。パケット
交換機による中継ではセルレベルおよび呼レベルの統計
多重効果が得られ、中継されるトラヒック量が大きいほ
ど単位トラヒック当たり必要となるリンク容量が小さく
なる。また、クロスコネクト装置による中継では統計多
重効果が得られないが、呼処理が不要であるためにノー
ドコストを削減できる。
し、トラヒックに対して、直通あるいはパケット交換機
により中継される仮想回線ルートを設定し、仮想回線の
束に対して、直通あるいはクロスコネクト装置により中
断される仮想パスを設定して接続を実現する。パケット
交換機による中継ではセルレベルおよび呼レベルの統計
多重効果が得られ、中継されるトラヒック量が大きいほ
ど単位トラヒック当たり必要となるリンク容量が小さく
なる。また、クロスコネクト装置による中継では統計多
重効果が得られないが、呼処理が不要であるためにノー
ドコストを削減できる。
【００１６】本実施例のパケット網設計では、各種通信
サービスのトラヒック需要量、トラヒック特性の申告
値、例えば最大帯域幅および平均帯域幅、ノード位置情
報およびコスト情報を入力とし、セル廃棄率および呼損
率規定値を制約条件として、交換装置コスト、クロスコ
ネクト装置コスト、リンクコストからなる設備コストで
定義される目的関数を最小化する仮想回線ルーティン
グ、仮想パス容量、仮想パスルーティング、物理リンク
容量の設計を行う。
サービスのトラヒック需要量、トラヒック特性の申告
値、例えば最大帯域幅および平均帯域幅、ノード位置情
報およびコスト情報を入力とし、セル廃棄率および呼損
率規定値を制約条件として、交換装置コスト、クロスコ
ネクト装置コスト、リンクコストからなる設備コストで
定義される目的関数を最小化する仮想回線ルーティン
グ、仮想パス容量、仮想パスルーティング、物理リンク
容量の設計を行う。
【００１７】このパケット網設計方式は大きく論理網設
計部１０１、物理網設計部１０２、摂動部１０２の３つ
の機能からなる。入力されたトラヒック需要にもとづい
て論理網設計部で仮想回線ルーティングを設計し、仮想
パス容量を求める。この仮想パス容量を入力として仮想
パス用ルーティングを設計し、物理リンク容量を求める
物理網設計を行う。仮想回線ルーティングおよび仮想パ
スルーティングの最適化を摂動部で行う。
計部１０１、物理網設計部１０２、摂動部１０２の３つ
の機能からなる。入力されたトラヒック需要にもとづい
て論理網設計部で仮想回線ルーティングを設計し、仮想
パス容量を求める。この仮想パス容量を入力として仮想
パス用ルーティングを設計し、物理リンク容量を求める
物理網設計を行う。仮想回線ルーティングおよび仮想パ
スルーティングの最適化を摂動部で行う。
【００１８】図１の論理網設計部１０１は両端のノード
間の距離の小さい順に仮想回線を選択し、仮想パス長と
仮想パス容量で定義した各仮想パスの重みを用いて選択
された仮想回線の経路を最短経路法で求める。求めた経
路上の仮想パスに選択された仮想回線上のトラヒック需
要を加え、仮想パス上に加わるトラヒック量を更新し、
必要な仮想パス容量を算出する処理を繰り返し、仮想回
線ルーティングを設計し、仮想パス容量を算出する。
間の距離の小さい順に仮想回線を選択し、仮想パス長と
仮想パス容量で定義した各仮想パスの重みを用いて選択
された仮想回線の経路を最短経路法で求める。求めた経
路上の仮想パスに選択された仮想回線上のトラヒック需
要を加え、仮想パス上に加わるトラヒック量を更新し、
必要な仮想パス容量を算出する処理を繰り返し、仮想回
線ルーティングを設計し、仮想パス容量を算出する。
【００１９】図１の物理網設計部１０２は両端のノード
間の距離の小さい順に仮想パスを選択し、物理リンク長
と物理リンク容量で定義した各物理リンクの重みを用い
て選択された仮想パスの経路を最短経路法で求める。求
めた経路上の物理リンクに選択された仮想パス容量を加
え、物理リンク上に加わる仮想パス容量を更新し、必要
な物理リンク容量を算出する処理を繰り返し、仮想パス
ルーティングを設計し、物理リンク容量を算出する。
間の距離の小さい順に仮想パスを選択し、物理リンク長
と物理リンク容量で定義した各物理リンクの重みを用い
て選択された仮想パスの経路を最短経路法で求める。求
めた経路上の物理リンクに選択された仮想パス容量を加
え、物理リンク上に加わる仮想パス容量を更新し、必要
な物理リンク容量を算出する処理を繰り返し、仮想パス
ルーティングを設計し、物理リンク容量を算出する。
【００２０】図２は、第２の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は交換ノードの重み計算部２０２、変更交換ノー
ド選択部２０３、全ノード選択判定部２０４、ノード機
能変更部２０５、目的関数改善効果判定部２０６、ノー
ド機能再変更部２０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は交換ノードの重み計算部２０２、変更交換ノー
ド選択部２０３、全ノード選択判定部２０４、ノード機
能変更部２０５、目的関数改善効果判定部２０６、ノー
ド機能再変更部２０７からなる。
【００２１】交換ノードの重み計算部２０２では、物理
網設計部１０２で設計した仮想回線ルーティング、仮想
パスルーティングのもとで交換ノードごとに交換される
トラヒック当たりの交換ノードコストの重みを計算す
る。
網設計部１０２で設計した仮想回線ルーティング、仮想
パスルーティングのもとで交換ノードごとに交換される
トラヒック当たりの交換ノードコストの重みを計算す
る。
【００２２】変更交換ノード選択部２０３では、交換ノ
ードの重み計算部２０２で求めた交換ノードの重みにつ
いて最大値を求め、その最大値を与える交換ノードをＳ
とする。
ードの重み計算部２０２で求めた交換ノードの重みにつ
いて最大値を求め、その最大値を与える交換ノードをＳ
とする。
【００２３】全ノード選択判定部２０４では、すでにす
べてのノードが選択されたとき処理を終了し、それ以外
の場合は処理を継続する。
べてのノードが選択されたとき処理を終了し、それ以外
の場合は処理を継続する。
【００２４】ノード機能変更部２０５では、図１０に示
すように、変更交換ノード選択部２０３で選択された交
換ノードＳで中継される仮想回線、例えば交換ノードｉ
−ｊ間を結ぶ仮想回線の束２４１について、交換ノード
ｉ−ｊの間の経路上でＳに隣接する交換ノードをＲ、Ｔ
（２１２、２１４）とし、Ｒ−Ｔ間を結ぶ仮想パスを新
たに設定する。ただし、交換ノードＲ、Ｔは交換ノード
ｉ、ｊ（２１１、２１５）と等しい場合もある。交換ノ
ードＳ（２１３）の機能をクロスコネクトに置き換え、
新たに設定された仮想パスをノードＳでクロスコネクト
する変更を行う。なお図１０において、２２１，２２
２，２２３，２２４，２２５は仮想パス、２３１はクロ
スコネクトノードである。
すように、変更交換ノード選択部２０３で選択された交
換ノードＳで中継される仮想回線、例えば交換ノードｉ
−ｊ間を結ぶ仮想回線の束２４１について、交換ノード
ｉ−ｊの間の経路上でＳに隣接する交換ノードをＲ、Ｔ
（２１２、２１４）とし、Ｒ−Ｔ間を結ぶ仮想パスを新
たに設定する。ただし、交換ノードＲ、Ｔは交換ノード
ｉ、ｊ（２１１、２１５）と等しい場合もある。交換ノ
ードＳ（２１３）の機能をクロスコネクトに置き換え、
新たに設定された仮想パスをノードＳでクロスコネクト
する変更を行う。なお図１０において、２２１，２２
２，２２３，２２４，２２５は仮想パス、２３１はクロ
スコネクトノードである。
【００２５】目的関数改善効果判定部２０６ではノード
機能変更部２０５で変更した設計パラメータと、変更前
の設計パラメータの与える目的関数の値の比較を行い、
変更後が小さいとき変更交換ノード選択部２０３へ戻
り、そうでないときはノード機能再変更部２０７の処理
へ進む。
機能変更部２０５で変更した設計パラメータと、変更前
の設計パラメータの与える目的関数の値の比較を行い、
変更後が小さいとき変更交換ノード選択部２０３へ戻
り、そうでないときはノード機能再変更部２０７の処理
へ進む。
【００２６】ノード機能再変更部２０７では、ノード機
能変更部２０５で変更した設計パラメータを元に戻し、
変更交換ノード選択部２０３で選択した交換ノードの重
みを０として全ノード選択判定部２０４の処理へ進む。
能変更部２０５で変更した設計パラメータを元に戻し、
変更交換ノード選択部２０３で選択した交換ノードの重
みを０として全ノード選択判定部２０４の処理へ進む。
【００２７】図３は、第３の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部はクロスコネクトノードの重み計算部３０２、変
更クロスコネクトノード選択部３０３、全ノード選択判
定部３０４、ノード機能変更部３０５、目的関数改善効
果判定部３０６、ノード機能再変更部３０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部はクロスコネクトノードの重み計算部３０２、変
更クロスコネクトノード選択部３０３、全ノード選択判
定部３０４、ノード機能変更部３０５、目的関数改善効
果判定部３０６、ノード機能再変更部３０７からなる。
【００２８】クロスコネクトノードの重み計算部３０２
では、論理網設計部１０１および物理網設計部１０２で
設定した仮想回線ルーティング、仮想パスルーティング
のもとでクロスコネクトノードごとにクロスコネクトさ
れるトラヒック当たりのリンクコストをリンクの重みと
して計算する。
では、論理網設計部１０１および物理網設計部１０２で
設定した仮想回線ルーティング、仮想パスルーティング
のもとでクロスコネクトノードごとにクロスコネクトさ
れるトラヒック当たりのリンクコストをリンクの重みと
して計算する。
【００２９】変更クロスコネクトノード選択部３０３で
は、クロスコネクトノードの重み計算部３０２で求めた
リンクの重みについて最大値を求め、その最大値を与え
るクロスコネクトノードをＣとする。
は、クロスコネクトノードの重み計算部３０２で求めた
リンクの重みについて最大値を求め、その最大値を与え
るクロスコネクトノードをＣとする。
【００３０】全ノード選択判定部３０４では、すでにす
べてのノードが選択されたとき処理を終了し、それ以外
の場合は処理を継続する。
べてのノードが選択されたとき処理を終了し、それ以外
の場合は処理を継続する。
【００３１】ノード機能変更部３０５では、図１１に示
すように、変更クロスコネクトノード選択部３０３で選
択されたクロスコネクトノードＣ（２３２）で中継され
る仮想パス２２６、例えばｘ−ｙを削除し、ｘ−Ｃ、Ｃ
−ｙを結ぶ仮想パスを新たに設定する。クロスコネクト
ノードＣ（２３２）の機能を交換に置き換え、新たに設
定された仮想パスｘ−Ｃ、Ｃ−ｙをノードＣ（２１７）
で交換する変更を行う。なお図１１において、２１６，
２１８は交換ノード、２２７，２２８は仮想パスであ
る。
すように、変更クロスコネクトノード選択部３０３で選
択されたクロスコネクトノードＣ（２３２）で中継され
る仮想パス２２６、例えばｘ−ｙを削除し、ｘ−Ｃ、Ｃ
−ｙを結ぶ仮想パスを新たに設定する。クロスコネクト
ノードＣ（２３２）の機能を交換に置き換え、新たに設
定された仮想パスｘ−Ｃ、Ｃ−ｙをノードＣ（２１７）
で交換する変更を行う。なお図１１において、２１６，
２１８は交換ノード、２２７，２２８は仮想パスであ
る。
【００３２】目的関数改善効果判定部３０６では、ノー
ド機能変更部３０５で変更した設計パラメータと、変更
前の設計パラメータの与える目的関数の値の比較を行
い、変更後が小さいとき変更クロスコネクトノード選択
部３０３へ戻り、そうでないときはノード機能再変更部
３０７の処理へ進む。
ド機能変更部３０５で変更した設計パラメータと、変更
前の設計パラメータの与える目的関数の値の比較を行
い、変更後が小さいとき変更クロスコネクトノード選択
部３０３へ戻り、そうでないときはノード機能再変更部
３０７の処理へ進む。
【００３３】ノード機能再変更部３０７ではノード機能
変更部３０５で変更した設計パラメータを元に戻し、変
更クロスコネクトノード選択部３０３で選択したクロス
コネクトノードの重みを０として全ノード選択判定部３
０４の処理へ進む。
変更部３０５で変更した設計パラメータを元に戻し、変
更クロスコネクトノード選択部３０３で選択したクロス
コネクトノードの重みを０として全ノード選択判定部３
０４の処理へ進む。
【００３４】図４は、第４の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想回線の重み計算部４０２、変更仮想回線選
択部４０３、全仮想回線選択判定部４０４、ルーティン
グ機能変更部４０５、目的関数改善効果判定部４０６、
ルーティング機能再変更部４０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想回線の重み計算部４０２、変更仮想回線選
択部４０３、全仮想回線選択判定部４０４、ルーティン
グ機能変更部４０５、目的関数改善効果判定部４０６、
ルーティング機能再変更部４０７からなる。
【００３５】仮想回線の重み計算部４０２では、論理網
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで同一
ノード間に設定される仮想回線の束ごとにトラヒック当
たりの仮想回線の通るリンクコストと交換ノードコスト
とクロスコネクトノードコストで定義される仮想回線の
重みを計算する。
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで同一
ノード間に設定される仮想回線の束ごとにトラヒック当
たりの仮想回線の通るリンクコストと交換ノードコスト
とクロスコネクトノードコストで定義される仮想回線の
重みを計算する。
【００３６】変更仮想回線選択部４０３では、仮想回線
の重み計算部４０２で求めた仮想回線の重みについて最
大値を求め、その最大値を与える同一ノード間に設定さ
れた仮想回線の束をＶとする。
の重み計算部４０２で求めた仮想回線の重みについて最
大値を求め、その最大値を与える同一ノード間に設定さ
れた仮想回線の束をＶとする。
【００３７】全仮想回線選択判定部４０４では、すでに
すべての仮想回線が選択されたとき処理を終了し、それ
以外の場合は処理を継続する。
すべての仮想回線が選択されたとき処理を終了し、それ
以外の場合は処理を継続する。
【００３８】ルーティング機能変更部４０５では、変更
仮想回線選択部４０３で選択された同一ノード間に設定
された仮想回線の束Ｖを仮想パスに変更して、その仮想
パスのルーティングを以下のように求める。はじめに各
交換ノードの重みをこれら交換ノードで交換されるトラ
ヒックごとのコストとして、各クロスコネクトノードの
重みをこれらクロスコネクトノードでクロスコネクトさ
れるトラヒックごとのコストとして、また各リンクの重
みをこれらリンクを通るトラヒックごとのコストとして
計算する。この重みを用いて最短経路法で仮想パスのル
ーティングを設定する。
仮想回線選択部４０３で選択された同一ノード間に設定
された仮想回線の束Ｖを仮想パスに変更して、その仮想
パスのルーティングを以下のように求める。はじめに各
交換ノードの重みをこれら交換ノードで交換されるトラ
ヒックごとのコストとして、各クロスコネクトノードの
重みをこれらクロスコネクトノードでクロスコネクトさ
れるトラヒックごとのコストとして、また各リンクの重
みをこれらリンクを通るトラヒックごとのコストとして
計算する。この重みを用いて最短経路法で仮想パスのル
ーティングを設定する。
【００３９】目的関数改善効果判定部４０６では、ルー
ティング機能変更部４０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
回線選択部４０３へ戻り、それ以外の場合はルーティン
グ機能再変更部４０７の処理へ進む。
ティング機能変更部４０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
回線選択部４０３へ戻り、それ以外の場合はルーティン
グ機能再変更部４０７の処理へ進む。
【００４０】ルーティング機能再変更部４０７では、ル
ーティング機能変更部４０５で変更した設計パラメータ
を元に戻し、変更仮想回線選択部４０３で選択した仮想
回線の重みを０として全仮想回線選択判定部４０４の処
理へ進む。
ーティング機能変更部４０５で変更した設計パラメータ
を元に戻し、変更仮想回線選択部４０３で選択した仮想
回線の重みを０として全仮想回線選択判定部４０４の処
理へ進む。
【００４１】図５は、第５の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想パスの重み計算部５０２、変更仮想パス選
択部５０３、全仮想パス選択判定部５０４、ルーティン
グ機能変更部５０５、目的関数改善効果判定部５０６、
ルーティング機能再変更部５０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想パスの重み計算部５０２、変更仮想パス選
択部５０３、全仮想パス選択判定部５０４、ルーティン
グ機能変更部５０５、目的関数改善効果判定部５０６、
ルーティング機能再変更部５０７からなる。
【００４２】仮想パスの重み計算部５０２では、論理網
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで仮想
パスごとにトラヒック当たりの仮想パスの通るリンクコ
ストと交換ノードコストとクロスコネクトノードコスト
で定義される仮想パスの重みを計算する。
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで仮想
パスごとにトラヒック当たりの仮想パスの通るリンクコ
ストと交換ノードコストとクロスコネクトノードコスト
で定義される仮想パスの重みを計算する。
【００４３】変更仮想パス選択部５０３では、仮想パス
の重み計算部５０２で求めた仮想パスの重みについて最
大値を求め、その最大値を求める仮想パスをＰとする。
の重み計算部５０２で求めた仮想パスの重みについて最
大値を求め、その最大値を求める仮想パスをＰとする。
【００４４】全仮想パス選択判定部５０４では、すでに
すべての仮想パスが選択されたとき処理を終了し、それ
以外の場合は処理を継続する。
すべての仮想パスが選択されたとき処理を終了し、それ
以外の場合は処理を継続する。
【００４５】ルーティング機能変更部５０５では、仮想
パスの重み計算部５０２で選択された仮想パスＰを仮想
回線に変更して、その仮想回線のルーティングを以下の
ように求める。はじめに各交換ノードの重みをこれら交
換ノードで交換されるトラヒックごとのコストとして、
各クロスコネクトノードの重みをこれらクロスコネクト
ノードでクロスコネクトされるトラヒックごとのコスト
として、また各リンクの重みをこれらリンクを通るトラ
ヒックごとのコストとして計算する。この重みを用いて
最短経路法で仮想回線のルーティングを設定する。
パスの重み計算部５０２で選択された仮想パスＰを仮想
回線に変更して、その仮想回線のルーティングを以下の
ように求める。はじめに各交換ノードの重みをこれら交
換ノードで交換されるトラヒックごとのコストとして、
各クロスコネクトノードの重みをこれらクロスコネクト
ノードでクロスコネクトされるトラヒックごとのコスト
として、また各リンクの重みをこれらリンクを通るトラ
ヒックごとのコストとして計算する。この重みを用いて
最短経路法で仮想回線のルーティングを設定する。
【００４６】目的関数改善効果判定部５０６では、ルー
ティング機能変更部５０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
パス選択部５０３へ戻り、それ以外の場合はルーティン
グ機能再変更部５０７の処理へ進む。
ティング機能変更部５０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
パス選択部５０３へ戻り、それ以外の場合はルーティン
グ機能再変更部５０７の処理へ進む。
【００４７】ルーティング機能再変更部５０７では、ル
ーティング機能変更部５０５で変更した設計パラメータ
を元に戻し、変更仮想パス選択部５０３で選択した仮想
パスの重みを０として全仮想パス選択判定部５０４の処
理へ進む。
ーティング機能変更部５０５で変更した設計パラメータ
を元に戻し、変更仮想パス選択部５０３で選択した仮想
パスの重みを０として全仮想パス選択判定部５０４の処
理へ進む。
【００４８】図６は、第６の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は交換ノードの重み計算部６０２、変更交換ノー
ド選択部６０３、選択ノードの重み判定部６０４、ノー
ド機能変更部６０５、目的関数改善効果判定部６０６、
ノード機能再変更部６０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は交換ノードの重み計算部６０２、変更交換ノー
ド選択部６０３、選択ノードの重み判定部６０４、ノー
ド機能変更部６０５、目的関数改善効果判定部６０６、
ノード機能再変更部６０７からなる。
【００４９】交換ノードの重み計算部６０２では、物理
網設計部１０２で設定した仮想回線ルーティング、仮想
パスルーティングのもとで交換ノードごとに交換される
トラヒック当たりの交換ノードコストの重みを計算す
る。
網設計部１０２で設定した仮想回線ルーティング、仮想
パスルーティングのもとで交換ノードごとに交換される
トラヒック当たりの交換ノードコストの重みを計算す
る。
【００５０】変更交換ノード選択部６０３では、交換ノ
ードの重み計算部６０２で求めた交換ノードの重みにつ
いて最大値を求め、その最大値を与える交換ノードをＳ
とする。
ードの重み計算部６０２で求めた交換ノードの重みにつ
いて最大値を求め、その最大値を与える交換ノードをＳ
とする。
【００５１】選択ノードの重み判定部６０４では、変更
交換ノード選択部６０３で求めた交換ノードの重みの最
大値が予め定めた定数Ａより大きいとき処理を終了し、
それ以外の場合は処理を継続する。
交換ノード選択部６０３で求めた交換ノードの重みの最
大値が予め定めた定数Ａより大きいとき処理を終了し、
それ以外の場合は処理を継続する。
【００５２】ノード機能変更部６０５では、図１０に示
すように、変更交換ノード選択部６０３で選択された交
換ノードＳで中継される仮想回線、例えば交換ノードｉ
−ｊ間を結ぶ仮想回線の束２４１について、交換ノード
ｉ−ｊの間の経路上でＳに隣接する交換ノードをＲ、Ｔ
（２１２、２１４）とし、Ｒ−Ｔ間を結ぶ仮想パスを新
たに設定する。ただし、交換ノードＲ、Ｔは交換ノード
ｉ，ｊ（２１１、２１５）と等しい場合もある。交換ノ
ードＳ（２１３）の機能をクロスコネクトに置き換え、
新たに設定された仮想パスをノードＳでクロスコネクト
する変更を行う。
すように、変更交換ノード選択部６０３で選択された交
換ノードＳで中継される仮想回線、例えば交換ノードｉ
−ｊ間を結ぶ仮想回線の束２４１について、交換ノード
ｉ−ｊの間の経路上でＳに隣接する交換ノードをＲ、Ｔ
（２１２、２１４）とし、Ｒ−Ｔ間を結ぶ仮想パスを新
たに設定する。ただし、交換ノードＲ、Ｔは交換ノード
ｉ，ｊ（２１１、２１５）と等しい場合もある。交換ノ
ードＳ（２１３）の機能をクロスコネクトに置き換え、
新たに設定された仮想パスをノードＳでクロスコネクト
する変更を行う。
【００５３】目的関数改善効果判定部６０６ではノード
機能変更部６０５で変更した設計パラメータと、変更前
の設計パラメータの与える目的関数の値の比較を行い、
変更後が小さいとき変更交換ノード選択部６０３へ戻
り、そうでないときはノード機能再変更部６０７の処理
へ進む。
機能変更部６０５で変更した設計パラメータと、変更前
の設計パラメータの与える目的関数の値の比較を行い、
変更後が小さいとき変更交換ノード選択部６０３へ戻
り、そうでないときはノード機能再変更部６０７の処理
へ進む。
【００５４】ノード機能再変更部６０７では、ノード機
能変更部６０５で変更した設計パラメータを元に戻し、
変更交換ノード選択部６０３で選択した交換ノードの重
みを０として選択ノードの重み判定部６０４の処理へ進
む。
能変更部６０５で変更した設計パラメータを元に戻し、
変更交換ノード選択部６０３で選択した交換ノードの重
みを０として選択ノードの重み判定部６０４の処理へ進
む。
【００５５】図７は、第７の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部はクロスコネクトノードの重み計算部７０２、変
更クロスコネクトノード選択部７０３、選択ノードの重
み判定部７０４、ノード機能変更部７０５、目的関数改
善効果判定部７０６、ノード機能再変更部７０７からな
る。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部はクロスコネクトノードの重み計算部７０２、変
更クロスコネクトノード選択部７０３、選択ノードの重
み判定部７０４、ノード機能変更部７０５、目的関数改
善効果判定部７０６、ノード機能再変更部７０７からな
る。
【００５６】クロスコネクトノードの重み計算部７０２
では論理網設計部１０１および物理網設計部１０２で設
定した仮想回線ルーティング、仮想パスルーティングの
もとでクロスコネクトノードごとにクロスコネクトされ
るトラヒック当たりのリンクコストをリンクの重みとし
て計算する。
では論理網設計部１０１および物理網設計部１０２で設
定した仮想回線ルーティング、仮想パスルーティングの
もとでクロスコネクトノードごとにクロスコネクトされ
るトラヒック当たりのリンクコストをリンクの重みとし
て計算する。
【００５７】変更クロスコネクトノード選択部７０３で
は、クロスコネクトノードの重み計算部７０２で求めた
リンクの重みについて最大値を求め、その最大値を与え
るクロスコネクトノードをＣとする。
は、クロスコネクトノードの重み計算部７０２で求めた
リンクの重みについて最大値を求め、その最大値を与え
るクロスコネクトノードをＣとする。
【００５８】選択ノードの重み判定部７０４では、変更
クロスコネクトノード選択部７０３で求めたリンクの重
みの最大値が予め定めた定数Ｂより大きいとき処理を終
了し、それ以外の場合は処理を継続する。
クロスコネクトノード選択部７０３で求めたリンクの重
みの最大値が予め定めた定数Ｂより大きいとき処理を終
了し、それ以外の場合は処理を継続する。
【００５９】ノード機能変更部７０５では、図１１に示
すように、変更クロスコネクトノード選択部７０３で選
択されたクロスコネクトノードＣ（２３２）で中継され
る仮想パス２２６、例えばｘ−ｙを削除し、ｘ−Ｃ、Ｃ
−ｙを結ぶ仮想パスを新たに設定する。クロスコネクト
ノードＣの機能を交換に置き換え、前記新たに設定され
た仮想パスｘ−Ｃ、Ｃ−ｙをノードＣ（２１７）で交換
する変更を行う。
すように、変更クロスコネクトノード選択部７０３で選
択されたクロスコネクトノードＣ（２３２）で中継され
る仮想パス２２６、例えばｘ−ｙを削除し、ｘ−Ｃ、Ｃ
−ｙを結ぶ仮想パスを新たに設定する。クロスコネクト
ノードＣの機能を交換に置き換え、前記新たに設定され
た仮想パスｘ−Ｃ、Ｃ−ｙをノードＣ（２１７）で交換
する変更を行う。
【００６０】目的関数改善交換判定部７０６では、ノー
ド機能変更部７０５で変更した設計パラメータと、変更
前の設計パラメータの与える目的関数の値の比較を行
い、変更後が小さいとき変更クロスコネクトノード選択
部７０３へ戻り、そうでないときはノード機能再変更部
７０７の処理へ進む。
ド機能変更部７０５で変更した設計パラメータと、変更
前の設計パラメータの与える目的関数の値の比較を行
い、変更後が小さいとき変更クロスコネクトノード選択
部７０３へ戻り、そうでないときはノード機能再変更部
７０７の処理へ進む。
【００６１】ノード機能再変更部７０７では、ノード機
能変更部７０５で変更した設計パラメータを元に戻し、
変更クロスコネクトノード選択部７０３で選択したクロ
スコネクトノードの重みを０として選択ノードの重み判
定部７０４の処理へ進む。
能変更部７０５で変更した設計パラメータを元に戻し、
変更クロスコネクトノード選択部７０３で選択したクロ
スコネクトノードの重みを０として選択ノードの重み判
定部７０４の処理へ進む。
【００６２】図８は、第８の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想回線の重み計算部８０２、変更仮想回線選
択部８０３、選択仮想回線の重み判定部８０４、ルーテ
ィング機能変更部８０５、目的関数改善効果判定部８０
６、ルーティング機能再変更部８０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想回線の重み計算部８０２、変更仮想回線選
択部８０３、選択仮想回線の重み判定部８０４、ルーテ
ィング機能変更部８０５、目的関数改善効果判定部８０
６、ルーティング機能再変更部８０７からなる。
【００６３】仮想回線の重み計算部８０２では、論理網
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで同一
ノード間に設定される仮想回線の束ごとにトラヒック当
たりの仮想回線の通るリンクコストと交換ノードコスト
とクロスコネクトノードコストで定義される仮想回線の
重みを計算する。
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで同一
ノード間に設定される仮想回線の束ごとにトラヒック当
たりの仮想回線の通るリンクコストと交換ノードコスト
とクロスコネクトノードコストで定義される仮想回線の
重みを計算する。
【００６４】変更仮想回線選択部８０３では、仮想回線
の重み計算部８０２で求めた仮想回線の重みについて最
大値を求め、その最大値を与える同一ノード間に設定さ
れた仮想回線の束をＶとする。
の重み計算部８０２で求めた仮想回線の重みについて最
大値を求め、その最大値を与える同一ノード間に設定さ
れた仮想回線の束をＶとする。
【００６５】選択仮想回線の重み判定部８０４では、変
更仮想回線選択部８０３で求めた仮想回線の重みの最大
値が予め定めた定数Ｄより大きいとき処理を終了し、そ
れ以外の場合は処理を継続する。
更仮想回線選択部８０３で求めた仮想回線の重みの最大
値が予め定めた定数Ｄより大きいとき処理を終了し、そ
れ以外の場合は処理を継続する。
【００６６】ルーティング機能変更部８０５では、変更
仮想回線選択部８０３で選択された同一ノード間に設定
された仮想回線の束Ｖを仮想パスに変更して、その仮想
パスのルーティングを以下のように求める。はじめに各
交換ノードの重みをこれら交換ノードで交換されるトラ
ヒックごとのコストとして、各クロスコネクトノードの
重みをこれらクロスコネクトノードでクロスコネクトさ
れるトラヒックごとのコストとして、また各リンクの重
みをこれらリンクを通るトラヒックごとのコストとして
計算する。この重みを用いて最短経路法で仮想パスのル
ーティングを設定する。
仮想回線選択部８０３で選択された同一ノード間に設定
された仮想回線の束Ｖを仮想パスに変更して、その仮想
パスのルーティングを以下のように求める。はじめに各
交換ノードの重みをこれら交換ノードで交換されるトラ
ヒックごとのコストとして、各クロスコネクトノードの
重みをこれらクロスコネクトノードでクロスコネクトさ
れるトラヒックごとのコストとして、また各リンクの重
みをこれらリンクを通るトラヒックごとのコストとして
計算する。この重みを用いて最短経路法で仮想パスのル
ーティングを設定する。
【００６７】目的関数改善効果判定部８０６では、ルー
ティング機能変更部８０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
回線選択部８０３へ戻り、それ以外の場合はルーティン
グ機能再変更部８０７の処理へ進む。
ティング機能変更部８０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
回線選択部８０３へ戻り、それ以外の場合はルーティン
グ機能再変更部８０７の処理へ進む。
【００６８】ルーティング機能再変更部８０７では、ル
ーティング機能変更部８０５で変更した設計パラメータ
を元に戻し、変更仮想回線選択部８０３で選択した仮想
回線の重みを０として選択仮想回線の重み判定部８０４
の処理へ進む。
ーティング機能変更部８０５で変更した設計パラメータ
を元に戻し、変更仮想回線選択部８０３で選択した仮想
回線の重みを０として選択仮想回線の重み判定部８０４
の処理へ進む。
【００６９】図９は、第９の発明に関する図１における
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想パスの重み計算部９０２、変更仮想パス選
択部９０３、選択仮想パスの重み判定部９０４、ルーテ
ィング機能変更部９０５、目的関数改善効果判定部９０
６、ルーティング機能再変更部９０７からなる。
摂動部１０３の一例の詳細アルゴリズム構成図である。
摂動部は仮想パスの重み計算部９０２、変更仮想パス選
択部９０３、選択仮想パスの重み判定部９０４、ルーテ
ィング機能変更部９０５、目的関数改善効果判定部９０
６、ルーティング機能再変更部９０７からなる。
【００７０】仮想パスの重み計算部９０２では、論理網
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで仮想
パスごとにトラヒック当たりの仮想パスの通るリンクコ
ストと交換ノードコストとクロスコネクトノードコスト
で定義される仮想パスの重みを計算する。
設計部１０１および物理網設計部１０２で設定した仮想
回線ルーティング、仮想パスルーティングのもとで仮想
パスごとにトラヒック当たりの仮想パスの通るリンクコ
ストと交換ノードコストとクロスコネクトノードコスト
で定義される仮想パスの重みを計算する。
【００７１】変更仮想パス選択部９０３では仮想パスの
重み計算部９０２で求めた仮想パスの重みについて最大
値を求め、その最大値を与える仮想パスをＰとする。
選択仮想パスの重み判定部９０４では、仮想パスの重み
計算部９０２で求めた仮想パスの重みの最大値が予め定
めた定数Ｅより大きいとき処理を終了し、それ以外の場
合は処理を継続する。
重み計算部９０２で求めた仮想パスの重みについて最大
値を求め、その最大値を与える仮想パスをＰとする。
選択仮想パスの重み判定部９０４では、仮想パスの重み
計算部９０２で求めた仮想パスの重みの最大値が予め定
めた定数Ｅより大きいとき処理を終了し、それ以外の場
合は処理を継続する。
【００７２】ルーティング機能変更部９０５では仮想パ
スの重み計算部９０２で選択された仮想パスＰを仮想回
線に変更して、その仮想回線のルーティングを以下のよ
うに求める。はじめに各交換ノードの重みをこれら交換
ノードで交換されるトラヒックごとのコストとして、各
クロスコネクトノードの重みをこれらクロスコネクトノ
ードでクロスコネクトされるトラヒックごとのコストと
して、また各リンクの重みをこれらリンクを通るトラヒ
ックごとのコストとして計算する。この重みを用いて最
短経路法で、仮想回線のルーティングを設定する。
スの重み計算部９０２で選択された仮想パスＰを仮想回
線に変更して、その仮想回線のルーティングを以下のよ
うに求める。はじめに各交換ノードの重みをこれら交換
ノードで交換されるトラヒックごとのコストとして、各
クロスコネクトノードの重みをこれらクロスコネクトノ
ードでクロスコネクトされるトラヒックごとのコストと
して、また各リンクの重みをこれらリンクを通るトラヒ
ックごとのコストとして計算する。この重みを用いて最
短経路法で、仮想回線のルーティングを設定する。
【００７３】目的関数改善効果判定部９０６では、ルー
ティング機能変更部９０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
パス選択部９０３へ戻り、それ以外の場合はルーティン
グ機能再変更部９０７の処理へ進む。
ティング機能変更部９０５で変更した設計パラメータ
と、変更前の設計パラメータのうち目的関数の値の最小
となるものを選択し、変更後が最小となるとき変更仮想
パス選択部９０３へ戻り、それ以外の場合はルーティン
グ機能再変更部９０７の処理へ進む。
【００７４】ルーティング機能再変更部９０７では、ル
ーティング機能変更部９０５で変更した設計パラメータ
を元に戻し、変更仮想パス選択部９０３で選択した仮想
パスの重みを０として選択仮想パスの重み判定部９０４
の処理へ進む。
ーティング機能変更部９０５で変更した設計パラメータ
を元に戻し、変更仮想パス選択部９０３で選択した仮想
パスの重みを０として選択仮想パスの重み判定部９０４
の処理へ進む。
【００７５】
【発明の効果】パケット網の設計において、仮想回線ル
ーティングと仮想パスルーティングの間の最適化を行う
方式により、従来の仮想回線網（論理網）、仮想パス網
（物理網）独立の設計に比べて、伝送リンクの使用効率
を向上させ、交換ノードの処理を低減させることによ
り、より経済的な網を構築できる利点がある。また第
６，第７，第８，第９の発明のパケット網設計方式を用
いると処理時間を短縮できる利点がある。
ーティングと仮想パスルーティングの間の最適化を行う
方式により、従来の仮想回線網（論理網）、仮想パス網
（物理網）独立の設計に比べて、伝送リンクの使用効率
を向上させ、交換ノードの処理を低減させることによ
り、より経済的な網を構築できる利点がある。また第
６，第７，第８，第９の発明のパケット網設計方式を用
いると処理時間を短縮できる利点がある。
【図１】第１の発明のパケット網設計方式の構成図であ
る。
る。
【図２】第２の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図３】第３の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図４】第４の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図５】第５の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図６】第６の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図７】第７の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図８】第８の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図９】第９の発明のパケット網設計方式の一実施例の
アルゴリズム構成図である。
アルゴリズム構成図である。
【図１０】第２および第６の発明のパケット網設計方式
を説明するための図である。
を説明するための図である。
【図１１】第３および第７の発明のパケット網設計方式
を説明するための図である。
を説明するための図である。
【図１２】従来のネットワーク設計方式の構成図であ
る。
る。
１０１ 論理網設計部 １０２ 物理網設計部 １０３ 摂動部 ２１１〜２１８ 交換ノード ２２１〜２２８ 仮想パス ２３１，２３２ クロスコネクトノード ２４１ 仮想回線の束
Claims (9)
- 【請求項１】クロスコネクト装置を伝送リンクを用いて
接続しクロスコネクト網を構成し、その上に論理的にパ
ケット交換網を実現するマルチサービス通信ネットワー
クにおいて、呼ごとにパケット交換機により端末間を結
んで設定される仮想回線の設計パラメータとして仮想回
線ルーティング、またクロスコネクトによりパケット交
換機間あるいは端末間を結ぶ、仮想回線の束からなる仮
想パスの設計パラメータとして仮想パスルーティングを
考慮し、セル品質、呼品質の制約の下で目的関数の最適
化を計るパケット網設計方式において、 前記仮想回線のルーティング設計を行い、前記仮想パス
容量を算出する論理網設計部と、 前記仮想パス容量から前記仮想パスルーティング設計を
行い、物理リンク容量を算出する物理網設計部と、 前記仮想回線ルーティングと、仮想パスルーティングの
間の最適化を行う摂動部からなることを特徴とするパケ
ット網設計方式。 - 【請求項２】前記摂動部は、 交換ノードの重みを計算する交換ノードの重み計算部
と、 前記交換ノードの重み計算部で求めた重みを用いて最も
重みの重い交換ノードを捜す変更交換ノード選択部と、 処理の終了あるいは継続を判定する全ノード選択判定部
と、 前記変更交換ノード選択部で選択されたノードの交換機
能をクロスコネクト機能に変更するノード機能変更部
と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ノード機能変更部で変更されたノードの機能を元に
戻すノード機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項３】前記摂動部は、 クロスコネクトノードの接続リンクの重みを計算するク
ロスコネクトノードの重み計算部と、 前記クロスコネクトノードの重み計算部で求めた重みを
用いて最も接続リンクの重みの重いクロスコネクトノー
ドを捜す変更クロスコネクトノード選択部と、 処理の終了あるいは継続を判定する全ノード選択判定部
と、 前記変更クロスコネクトノード選択部で選択されたノー
ドのクロスコネクト機能を交換機能に変更するノード機
能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ノード機能変更部で変更されたノード機能を元に戻
すノード機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項４】前記摂動部は、 仮想回線の重みを計算する仮想回線の重み計算部と、 前記仮想回線の重み計算部で求めた重みを用いて最も重
みの重い仮想回線を捜す変更仮想回線選択部と、 処理の終了あるいは継続を判定する全仮想回線選択判定
部と、 前記変更仮想回線選択部で選択された仮想回線の仮想回
線ルーティングを仮想パスルーティングに変更するルー
ティング機能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ルーティング機能変更部で変更されたルーティング
機能を元に戻すルーティング機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項５】前記摂動部は、 仮想パスの重みを計算する仮想パスの重み計算部と、 前記仮想パスの重み計算部で求めた重みを用いて最も重
みの重い仮想パスを捜す変更仮想パス選択部と、 処理の終了あるいは継続を判定する全仮想パス選択判定
部と、 前記変更仮想パス選択部で選択された仮想パスの仮想パ
スルーティングを仮想回線ルーティングに変更するルー
ティング機能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ルーティング機能変更部で変更されたルーティング
機能を元に戻すルーティング機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項６】前記摂動部は、 交換ノードの重みを計算する交換ノードの重み計算部
と、 前記交換ノードの重み計算部で求めた重みを用いて最も
重みの重い交換ノードを捜す変更交換ノード選択部と、 処理の終了あるいは継続を判定する選択ノードの重み判
定部と、 前記変更交換ノード選択部で選択されたノードの交換機
能をクロスコネクト機能に変更するノード機能変更部
と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ノード機能変更部で変更されたノードの機能を元に
戻すノード機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項７】前記摂動部は、クロスコネクトノードの接
続リンクの重みを計算するクロスコネクトノードの重み
計算部と、 前記クロスコネクトノードの重み計算部で求めた重みを
用いて最も接続リンクの重みの重いクロスコネクトノー
ドを捜す変更クロスコネクトノード選択部と、 処理の終了あるいは継続を判定する選択ノードの重み判
定部と、 前記変更クロスコネクトノード選択部で選択されたノー
ドのクロスコネクト機能を交換機能に変更するノード機
能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ノード機能変更部で変更されたノード機能を元に戻
すノード機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項８】前記摂動部は、 仮想回線の重みを計算する仮想回線の重み計算部と、 前記仮想回線の重み計算部で求めた重みを用いて最も重
みの重い仮想回線を捜す変更仮想回線選択部と、 処理の終了あるいは継続を判定する選択仮想回線の重み
判定部と、 前記変更仮想回線選択部で選択された仮想回線の仮想ル
ーティングを仮想パスルーティングに変更するルーティ
ング機能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ルーティング機能変更部で変更されたルーティング
機能を元に戻すルーティング機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。 - 【請求項９】前記摂動部は、 仮想パスの重みを計算する仮想パスの重み計算部と、 前記仮想パスの重み計算部で求めた重みを用いて最も重
みの重い仮想パスを捜す変更仮想パス選択部と、 処理の終了あるいは継続を判定する選択仮想パスの重み
判定部と、 前記変更仮想パス選択部で選択された仮想パスの仮想パ
スルーティングを仮想回線ルーティングに変更するルー
ティング機能変更部と、 変更前後の目的関数値を比較する目的関数改善効果判定
部と、 前記ルーティング機能変更部で変更されたルーティング
機能を元に戻すルーティング機能再変更部とからなり、 前記仮想回線ルーティングおよび仮想パスルーティング
を決めることを特徴とする請求項１記載のパケット網設
計方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1154392A JPH05207068A (ja) | 1992-01-27 | 1992-01-27 | パケット網設計方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1154392A JPH05207068A (ja) | 1992-01-27 | 1992-01-27 | パケット網設計方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05207068A true JPH05207068A (ja) | 1993-08-13 |
Family
ID=11780882
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1154392A Pending JPH05207068A (ja) | 1992-01-27 | 1992-01-27 | パケット網設計方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH05207068A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| AU692884B2 (en) * | 1994-06-13 | 1998-06-18 | Telefonaktiebolaget Lm Ericsson (Publ) | Enhancement of network operation and performance |
| JP2015050511A (ja) * | 2013-08-30 | 2015-03-16 | 日本電信電話株式会社 | 物理資源割当装置 |
-
1992
- 1992-01-27 JP JP1154392A patent/JPH05207068A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| AU692884B2 (en) * | 1994-06-13 | 1998-06-18 | Telefonaktiebolaget Lm Ericsson (Publ) | Enhancement of network operation and performance |
| JP2015050511A (ja) * | 2013-08-30 | 2015-03-16 | 日本電信電話株式会社 | 物理資源割当装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6697333B1 (en) | Bandwidth load consideration in network route selection | |
| US5404451A (en) | System for identifying candidate link, determining underutilized link, evaluating addition of candidate link and removing of underutilized link to reduce network cost | |
| EP0766430B1 (en) | Routing method in a communications network | |
| CA2191945C (en) | Source routing for connection-oriented network with repeated call attempts for satisfying user-specified qos parameters | |
| US5253161A (en) | Method for routing data in a near-optimal manner in a distributed data communications network | |
| JP4368981B2 (ja) | Ａｔｍネットワーク中のロード平衡したｕｂｒルーティング | |
| JP2002199005A (ja) | 相互接続構造を設計する方法 | |
| ZA200206884B (en) | Method and system for controlling data traffic in a network. | |
| EP0781021A3 (en) | Network congestion measurement method and apparatus therefor | |
| USRE40398E1 (en) | ATM telecommunications systems and method for routing narrow band traffic | |
| WO1998030041A1 (en) | System and method for network optimization using code blocking | |
| Mariusz et al. | Point-to-point blocking probability in switching networks with reservation | |
| US6744734B1 (en) | Method for generating the optimal PNNI complex node representations for restrictive costs | |
| US8547849B2 (en) | ATM telecommunications systems and method for routing narrow band traffic | |
| JPH05207068A (ja) | パケット網設計方式 | |
| JP2004505527A (ja) | 通信システム | |
| KR100273774B1 (ko) | 초고속 전용통신망 최적 설계를 위한 망 설계 방법 | |
| JP2763073B2 (ja) | 自己ルーティング通話路制御方式 | |
| JP2001257687A (ja) | Ａｔｍ交換機におけるｐｎｎｉ経路計算システム | |
| Ke et al. | On cost-based routing in connection-oriented broadband networks | |
| Medhi et al. | Dimensioning and computational results for wide-area broadband networks with two-level dynamic routing | |
| JP3036575B2 (ja) | 通信網設定方法および通信装置 | |
| Lee et al. | Pre-computation based selective probing (PCSP) scheme for distributed QoS routing | |
| JP2611659B2 (ja) | 伝送容量とトラヒックフローの算出方法 | |
| Girard et al. | An optimization method for broadband ISDN networks |