JP3336614B2 - 木構造通信路の設計方法、及び、通信路の木構造解 - Google Patents
木構造通信路の設計方法、及び、通信路の木構造解Info
- Publication number
- JP3336614B2 JP3336614B2 JP29213199A JP29213199A JP3336614B2 JP 3336614 B2 JP3336614 B2 JP 3336614B2 JP 29213199 A JP29213199 A JP 29213199A JP 29213199 A JP29213199 A JP 29213199A JP 3336614 B2 JP3336614 B2 JP 3336614B2
- Authority
- JP
- Japan
- Prior art keywords
- tree
- path
- route
- node
- score
- 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.)
- Expired - Fee Related
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/48—Routing tree calculation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/18—Loop-free operations
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/48—Routing tree calculation
- H04L45/484—Routing tree calculation using multiple routing trees
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q3/00—Selecting arrangements
- H04Q3/0016—Arrangements providing connection between exchanges
- H04Q3/0062—Provisions for network management
- H04Q3/0083—Network planning or design; Modelling of planned or existing networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Small-Scale Networks (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Telephonic Communication Services (AREA)
Description
【０００１】
【発明の属する技術分野】本発明は、木構造通信路の設
計方法、及び、通信路の木構造解に関し、特に、入口ノ
ード数が多く、作成される木の数がなるべく少なくて発
見的手法により解を高速に求めることができる木構造通
信路の設計方法、及び、通信路の木構造解に関する。
計方法、及び、通信路の木構造解に関し、特に、入口ノ
ード数が多く、作成される木の数がなるべく少なくて発
見的手法により解を高速に求めることができる木構造通
信路の設計方法、及び、通信路の木構造解に関する。
【０００２】
【従来の技術】与えられた通信用ネットワークから、木
（ツリー）が作成される。ネットワークは、多数のノー
ドから形成されている。多数のノードを接続する枝の集
合として木が作成される。ある出口ノードに対して複数
の入り口ノードが接続される複数の経路を与え木の数を
最小にする問題は、混合整数計画法で解かれ得る。混合
整数計画法は、必ず最適解を与えることができる。
（ツリー）が作成される。ネットワークは、多数のノー
ドから形成されている。多数のノードを接続する枝の集
合として木が作成される。ある出口ノードに対して複数
の入り口ノードが接続される複数の経路を与え木の数を
最小にする問題は、混合整数計画法で解かれ得る。混合
整数計画法は、必ず最適解を与えることができる。
【０００３】問題の規模が大きくなって与えられる経路
あるいは木の数が多くなれば、混合整数計画法により最
適解を得るために要する時間が、非常に長くなることを
回避することができない。必ずしも最適解が得られなく
木の数が最小にならなくても、できる限り木の数が少な
くなって高速に解く解法の提供が望まれる。
あるいは木の数が多くなれば、混合整数計画法により最
適解を得るために要する時間が、非常に長くなることを
回避することができない。必ずしも最適解が得られなく
木の数が最小にならなくても、できる限り木の数が少な
くなって高速に解く解法の提供が望まれる。
【０００４】
【発明が解決しようとする課題】本発明の課題は、必ず
しも最適解が得られなくて木の数が最小にならなくて
も、できる限り木の数が少なくなって高速に解くことが
できる木構造通信路の設計方法、及び、通信路の木構造
解を提供することにある。本発明の他の課題は、必ずし
も最適解が得られなくて木の数が最小にならなくても、
できる限り木の数が少なくなって高速に解くことがで
き、新たに経路が追加されても木を簡単に更新すること
ができる木構造通信路の設計方法、及び、通信路の木構
造解を提供することにある。
しも最適解が得られなくて木の数が最小にならなくて
も、できる限り木の数が少なくなって高速に解くことが
できる木構造通信路の設計方法、及び、通信路の木構造
解を提供することにある。本発明の他の課題は、必ずし
も最適解が得られなくて木の数が最小にならなくても、
できる限り木の数が少なくなって高速に解くことがで
き、新たに経路が追加されても木を簡単に更新すること
ができる木構造通信路の設計方法、及び、通信路の木構
造解を提供することにある。
【０００５】
【課題を解決するための手段】その課題を解決するため
の手段が、下記のように表現される。その表現中に現れ
る技術的事項には、括弧（）つきで、番号、記号等が添
記されている。その番号、記号等は、本発明の実施の複
数・形態又は複数の実施例のうちの少なくとも１つの実
施の形態又は複数の実施例を構成する技術的事項、特
に、その実施の形態又は実施例に対応する図面に表現さ
れている技術的事項に付せられている参照番号、参照記
号等に一致している。このような参照番号、参照記号
は、請求項記載の技術的事項と実施の形態又は実施例の
技術的事項との対応・橋渡しを明確にしている。このよ
うな対応・橋渡しは、請求項記載の技術的事項が実施の
形態又は実施例の技術的事項に限定されて解釈されるこ
とを意味しない。
の手段が、下記のように表現される。その表現中に現れ
る技術的事項には、括弧（）つきで、番号、記号等が添
記されている。その番号、記号等は、本発明の実施の複
数・形態又は複数の実施例のうちの少なくとも１つの実
施の形態又は複数の実施例を構成する技術的事項、特
に、その実施の形態又は実施例に対応する図面に表現さ
れている技術的事項に付せられている参照番号、参照記
号等に一致している。このような参照番号、参照記号
は、請求項記載の技術的事項と実施の形態又は実施例の
技術的事項との対応・橋渡しを明確にしている。このよ
うな対応・橋渡しは、請求項記載の技術的事項が実施の
形態又は実施例の技術的事項に限定されて解釈されるこ
とを意味しない。
【０００６】本発明による木構造通信路の設計方法は、
複数の入口ノード（Ｅ１〜Ｅｉ）と、単数の出口ノード
（Ｅｓ：ｓは１〜ｉ）と、入口ノード（Ｅ１〜Ｅｉ）と
出口ノード（Ｅｓ）との間に介設されて接続される複数
の接続ノード（Ｃ１〜Ｃｊ）、及び、入口ノード（Ｅ１
〜Ｅｉ）と出口ノード（Ｅｓ）と接続ノード（Ｃ１〜Ｃ
ｊ）とが接続される複数の経路が与えられていて、下記
複数のステップ：複数の経路のうちから順次に選択され
る経路に関して順次に得点を付与すること、複数の経路
から得点が小さい順番で順序づけられた経路を選択する
こと、順序づけられた経路のうちの最も得点が低い経路
ｎとその他の経路ｐ（ｐは１〜ｑ、但しｎは除かれる）
とから木を作成すること、木の作成が不可能である経路
のうち最も得点が低い経路ｍとその他の未だ木として作
成されていない経路とから他の木を作成することとを含
み、得点を付与することは、下記判定基準：（１）選択
された経路と他の経路について、これらに共通して現れ
るノードが存在しないこと、（２）選択された経路と他
の経路について、これらに共通して現れる共通ノードが
存在する場合、共通ノードが接続する他のノードも共通
していることの（１）又は（２）のいずれかに該当すれ
ばその該当の度に加点することである。
複数の入口ノード（Ｅ１〜Ｅｉ）と、単数の出口ノード
（Ｅｓ：ｓは１〜ｉ）と、入口ノード（Ｅ１〜Ｅｉ）と
出口ノード（Ｅｓ）との間に介設されて接続される複数
の接続ノード（Ｃ１〜Ｃｊ）、及び、入口ノード（Ｅ１
〜Ｅｉ）と出口ノード（Ｅｓ）と接続ノード（Ｃ１〜Ｃ
ｊ）とが接続される複数の経路が与えられていて、下記
複数のステップ：複数の経路のうちから順次に選択され
る経路に関して順次に得点を付与すること、複数の経路
から得点が小さい順番で順序づけられた経路を選択する
こと、順序づけられた経路のうちの最も得点が低い経路
ｎとその他の経路ｐ（ｐは１〜ｑ、但しｎは除かれる）
とから木を作成すること、木の作成が不可能である経路
のうち最も得点が低い経路ｍとその他の未だ木として作
成されていない経路とから他の木を作成することとを含
み、得点を付与することは、下記判定基準：（１）選択
された経路と他の経路について、これらに共通して現れ
るノードが存在しないこと、（２）選択された経路と他
の経路について、これらに共通して現れる共通ノードが
存在する場合、共通ノードが接続する他のノードも共通
していることの（１）又は（２）のいずれかに該当すれ
ばその該当の度に加点することである。
【０００７】このような得点づけによって、確実に、全
ての経路を収容する木を作成することができ、このよう
に作成される木が最適でなく、その数が最小数ではなく
ても、発見法的にその木の作成が高速に実行され得る。
一旦作成された木構造に新たに経路が作成される場合に
も、木を再び作成することができる利点がある。経路を
木に代えた場合にも、本発明はそのまま適用され得る。
この意味で、経路は木であることを意味し、従って、経
路は経路又は木である。加点は、単純に統一的に＋１点
でよい。
ての経路を収容する木を作成することができ、このよう
に作成される木が最適でなく、その数が最小数ではなく
ても、発見法的にその木の作成が高速に実行され得る。
一旦作成された木構造に新たに経路が作成される場合に
も、木を再び作成することができる利点がある。経路を
木に代えた場合にも、本発明はそのまま適用され得る。
この意味で、経路は木であることを意味し、従って、経
路は経路又は木である。加点は、単純に統一的に＋１点
でよい。
【０００８】本発明による通信路の木構造解は、既述の
木構造通信路の設計方法により設計される木構造解であ
る。その木構造解はコンピュータに読み取り可能に記録
媒体に記録され得る。
木構造通信路の設計方法により設計される木構造解であ
る。その木構造解はコンピュータに読み取り可能に記録
媒体に記録され得る。
【０００９】
【発明の実施の形態】図に一致対応して、本発明による
木構造通信路の設計方法の実施の形態は、図１に示され
るように、入力される経路について後述される採点を実
行する経路採点手段１と、その採点の結果に基づいて経
路を並べ替える経路並べ替え手段２と、並べ替えられた
経路から順に木を生成する木作成手段３とを備えてい
る。
木構造通信路の設計方法の実施の形態は、図１に示され
るように、入力される経路について後述される採点を実
行する経路採点手段１と、その採点の結果に基づいて経
路を並べ替える経路並べ替え手段２と、並べ替えられた
経路から順に木を生成する木作成手段３とを備えてい
る。
【００１０】経路採点手段１は経路並べ替え手段２に接
続し、経路並べ替え手段２は木作成手段３に接続してい
る。木作成手段は、与えられた経路から木の数ができる
だけ少なく高速に木構造解を出力することができる解法
を記述するプログラムにより動作し、そのプログラムを
記録する記録媒体を備えている。その記録媒体に記録さ
れているプログラムは、任意のコンピュータに読み取ら
れ得る。
続し、経路並べ替え手段２は木作成手段３に接続してい
る。木作成手段は、与えられた経路から木の数ができる
だけ少なく高速に木構造解を出力することができる解法
を記述するプログラムにより動作し、そのプログラムを
記録する記録媒体を備えている。その記録媒体に記録さ
れているプログラムは、任意のコンピュータに読み取ら
れ得る。
【００１１】図２は、本発明の解法が適用されて木構造
解が求められる問題である通信用ネットワークを例示し
ている。ノード又は結節端点は、Ｅ１、Ｅ２、・・・Ｅ
１０と、Ｃ１、Ｃ２、・・・、Ｃ５とで表示されてい
る。このようなネットワークの経路の部分集合として、
下記６つの経路が抽出される。その６つの経路は、同一
の出口ノードＥ１が採択されている。
解が求められる問題である通信用ネットワークを例示し
ている。ノード又は結節端点は、Ｅ１、Ｅ２、・・・Ｅ
１０と、Ｃ１、Ｃ２、・・・、Ｃ５とで表示されてい
る。このようなネットワークの経路の部分集合として、
下記６つの経路が抽出される。その６つの経路は、同一
の出口ノードＥ１が採択されている。
【００１２】経路１：Ｅ３−Ｃ２−Ｅ１ 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１ 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１ 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１ 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１ 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１
【００１３】図３は、木構造解法部分である採点方法を
示している。ステップＳ１で、６つの内の任意の１つの
経路ｎが選択される。経路ｎの得点は、ステップＳ２で
初期化されて、０とされる。次に、経路ｎ以外の経路ｍ
が選択される（ステップＳ３）。経路ｎと経路ｍとから
木が生成し得るかどうかが判定される。経路の両端点は
Ｅで表示され、その両端点で挟まれている点はＣで表示
される。以下、ノードと端点は、用語上、区別されずに
用いられる。
示している。ステップＳ１で、６つの内の任意の１つの
経路ｎが選択される。経路ｎの得点は、ステップＳ２で
初期化されて、０とされる。次に、経路ｎ以外の経路ｍ
が選択される（ステップＳ３）。経路ｎと経路ｍとから
木が生成し得るかどうかが判定される。経路の両端点は
Ｅで表示され、その両端点で挟まれている点はＣで表示
される。以下、ノードと端点は、用語上、区別されずに
用いられる。
【００１４】木生成の可能・不可能は、下記判定規則が
適用される。 （１）経路Ａ又は木Ａと経路Ｂ又は木Ｂについて、これ
らに共通して現れるノードが存在しなければ、木の生成
が可能である。 （２）経路Ａ又は木Ａと経路Ｂ又は木Ｂについて、これ
らに共通して現れるノードが存在する場合、その共通ノ
ードが接続する他のノードも両経路又は木で共通してい
るならば、木の作成が可能であり、そうでない場合は、
木の生成は不可能である。
適用される。 （１）経路Ａ又は木Ａと経路Ｂ又は木Ｂについて、これ
らに共通して現れるノードが存在しなければ、木の生成
が可能である。 （２）経路Ａ又は木Ａと経路Ｂ又は木Ｂについて、これ
らに共通して現れるノードが存在する場合、その共通ノ
ードが接続する他のノードも両経路又は木で共通してい
るならば、木の作成が可能であり、そうでない場合は、
木の生成は不可能である。
【００１５】図４は、このような木の生成の可能・不可
能を判定する判定方法を示している。経路／木ｎと経路
／木ｍに共通するノードが存在するかどうかがステップ
Ｓ１１で判定され、共通ノードが存在しなければ、それ
らから木が生成することが可能であると判定される（ス
テップＳ１２）。それらに共通ノードが存在すれば、ス
テップＳ１３で、その共通のノードから接続するノード
が経路／木ｎと経路／木ｍとで同じである（共通する）
かどうかが判定される。そのような接続する共通ノード
が存在するならば、ステップＳ１２に移行して、木の生
成が可能であると判定される。そのような接続する共通
ノードが存在しないならば、木の作成は不可能であると
判定される（ステップＳ１４）。
能を判定する判定方法を示している。経路／木ｎと経路
／木ｍに共通するノードが存在するかどうかがステップ
Ｓ１１で判定され、共通ノードが存在しなければ、それ
らから木が生成することが可能であると判定される（ス
テップＳ１２）。それらに共通ノードが存在すれば、ス
テップＳ１３で、その共通のノードから接続するノード
が経路／木ｎと経路／木ｍとで同じである（共通する）
かどうかが判定される。そのような接続する共通ノード
が存在するならば、ステップＳ１２に移行して、木の生
成が可能であると判定される。そのような接続する共通
ノードが存在しないならば、木の作成は不可能であると
判定される（ステップＳ１４）。
【００１６】このような規則に基づく木の生成の可能・
不可能の判定基準に従って、ステップＳ４で、経路ｎと
経路ｍとから木が生成可能でるか生成不能であるかが判
定される。木の生成が可能であれば、経路ｎにはその得
点として１が追加される（ステップＳ５）。得点＝０＋
１＝１。木の生成が可能であれば経路ｎにはその得点と
して１が加算され、木の生成が不可能であれば得点１の
加算がなく、ステップＳ６に進む。
不可能の判定基準に従って、ステップＳ４で、経路ｎと
経路ｍとから木が生成可能でるか生成不能であるかが判
定される。木の生成が可能であれば、経路ｎにはその得
点として１が追加される（ステップＳ５）。得点＝０＋
１＝１。木の生成が可能であれば経路ｎにはその得点と
して１が加算され、木の生成が不可能であれば得点１の
加算がなく、ステップＳ６に進む。
【００１７】ステップＳ６では、全ての経路の選択が完
了していないので、ステップＳ３に戻る。ステップＳ６
で、先に選択された経路ｍ（例示：ｍ＝２）と異なり、
経路ｎ（例示：ｎ＝１）以外の他の残りの経路から、別
な経路ｓ（例示：ｓ＝２）が選択される。経路ｓについ
て、ステップＳ４〜Ｓ５が繰り返されて、既述の加算条
件に従って得点計算が行われる。経路ｎとこれ以外の全
ての経路とによる木の生成の可能・不可能が判定され、
既述の計算が実行され、経路ｎに関する他の経路の得点
が決定されると（ステップＳ７）、ステップＳ１に戻
り、経路ｎ以外の経路ｋが選択され、既述のステップが
繰り返されて、経路ｋに関して経路ｋ以外の経路の得点
の計算が実行される。
了していないので、ステップＳ３に戻る。ステップＳ６
で、先に選択された経路ｍ（例示：ｍ＝２）と異なり、
経路ｎ（例示：ｎ＝１）以外の他の残りの経路から、別
な経路ｓ（例示：ｓ＝２）が選択される。経路ｓについ
て、ステップＳ４〜Ｓ５が繰り返されて、既述の加算条
件に従って得点計算が行われる。経路ｎとこれ以外の全
ての経路とによる木の生成の可能・不可能が判定され、
既述の計算が実行され、経路ｎに関する他の経路の得点
が決定されると（ステップＳ７）、ステップＳ１に戻
り、経路ｎ以外の経路ｋが選択され、既述のステップが
繰り返されて、経路ｋに関して経路ｋ以外の経路の得点
の計算が実行される。
【００１８】例示すれば、経路２と経路３では、ノード
Ｃ３が共通して現れ、且つ、経路２ではノードＣ３は経
路Ｃ４に接続し、経路３ではノードＣ２に接続し、共通
ノードＣ３が接続する共通ノードは存在しないので、経
路２と経路３とからは木を作成することができない。経
路１と経路３では、ノードＣ２が共通して現れ、両者と
もノードＣ２は共通のノード（端点Ｅ１）に接続するの
で、木の作成が可能である。
Ｃ３が共通して現れ、且つ、経路２ではノードＣ３は経
路Ｃ４に接続し、経路３ではノードＣ２に接続し、共通
ノードＣ３が接続する共通ノードは存在しないので、経
路２と経路３とからは木を作成することができない。経
路１と経路３では、ノードＣ２が共通して現れ、両者と
もノードＣ２は共通のノード（端点Ｅ１）に接続するの
で、木の作成が可能である。
【００１９】このような得点づけが完了して、得点表が
下記のように作成される。 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２点 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２点 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点
下記のように作成される。 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２点 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２点 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点
【００２０】経路並べ替え手段２は、経路をそれらの得
点がより低い順に並べる。 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２点 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２点 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点
点がより低い順に並べる。 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２点 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２点 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点
【００２１】木作成手段３は、経路並べ替え手段２で並
べ替えられた経路の並び順に基づいて、木を作成する。
図５は、その木作成方法を示している。全ての経路１〜
６は”設計未完”とされる（ステップＳ２１）。”設計
未完”の経路のうちで、もっとも得点が低い経路ｎ（例
示：ｎ＝２）が選択される（ステップＳ２２）。経路ｎ
は、これだけから形成される木ｎとみなされる。経路／
木ｎは、”設計完了”とされる（ステップＳ２３）。
べ替えられた経路の並び順に基づいて、木を作成する。
図５は、その木作成方法を示している。全ての経路１〜
６は”設計未完”とされる（ステップＳ２１）。”設計
未完”の経路のうちで、もっとも得点が低い経路ｎ（例
示：ｎ＝２）が選択される（ステップＳ２２）。経路ｎ
は、これだけから形成される木ｎとみなされる。経路／
木ｎは、”設計完了”とされる（ステップＳ２３）。
【００２２】”設計未完”であり次に得点が低い経路ｍ
（例示：ｍ＝５）が選択される（ステップＳ２４）。木
ｎと経路ｍとから木が生成することができるかどうかが
既述の同じ判定方法により判定される（ステップＳ２
５）。木ｎと経路ｍとから木が生成することができるな
らば、木ｎに経路ｍが加えられて新たに生成される。こ
のように新たに生成される木は、新たに木ｎとされる。
（例示：ｍ＝５）が選択される（ステップＳ２４）。木
ｎと経路ｍとから木が生成することができるかどうかが
既述の同じ判定方法により判定される（ステップＳ２
５）。木ｎと経路ｍとから木が生成することができるな
らば、木ｎに経路ｍが加えられて新たに生成される。こ
のように新たに生成される木は、新たに木ｎとされる。
【００２３】この場合、木ｍは、”設計完了”とされる
（ステップＳ２６）。ステップＳ２７の判断に基づい
て、経路ｎ以外の”設計未完”の全ての経路に関して、
ステップＳ２４〜Ｓ２６が繰り返されて実行される。全
ての経路についてステップＳ２４〜Ｓ２６が繰り返さ
れ、全ての経路が”設計完了”になっているかどうかが
判定される（ステップＳ２８）。”設計未完”の経路が
残っていれば、ステップＳ２２〜Ｓ２７が繰り返されて
実行される。
（ステップＳ２６）。ステップＳ２７の判断に基づい
て、経路ｎ以外の”設計未完”の全ての経路に関して、
ステップＳ２４〜Ｓ２６が繰り返されて実行される。全
ての経路についてステップＳ２４〜Ｓ２６が繰り返さ
れ、全ての経路が”設計完了”になっているかどうかが
判定される（ステップＳ２８）。”設計未完”の経路が
残っていれば、ステップＳ２２〜Ｓ２７が繰り返されて
実行される。
【００２４】１回目の試行ステップＳ２１〜Ｓ２７で、
下記結果が得られる。 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２
点：”設計完了” 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２
点：”設計未完” 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点：”設計
未完” 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点：”設計
完了” 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点：”設計未完” 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点：”設計
完了” この１回の試行により、木２は、経路２と経路４と経路
６とからなる木である。
下記結果が得られる。 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２
点：”設計完了” 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２
点：”設計未完” 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点：”設計
未完” 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点：”設計
完了” 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点：”設計未完” 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点：”設計
完了” この１回の試行により、木２は、経路２と経路４と経路
６とからなる木である。
【００２５】２回目の試行で下記結果が得られる。 経路２：Ｅ３−Ｃ３−Ｃ４−Ｃ１−Ｅ１：得点＝２
点：”設計完了” 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２
点：”設計完了” 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点：”設計
完了” 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点：”設計
完了” 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点：”設計完了” 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点：”設計
完了” このような２回の試行により、木２は、経路２と経路４
と経路６とからなる木であり、木５は、経路５と経路３
と経路１とからなる木である。
点：”設計完了” 経路５：Ｅ７−Ｃ４−Ｃ３−Ｃ２−Ｅ１：得点＝２
点：”設計完了” 経路３：Ｅ５−Ｃ３−Ｃ２−Ｅ１：得点＝３点：”設計
完了” 経路４：Ｅ５−Ｃ４−Ｃ１−Ｅ１：得点＝３点：”設計
完了” 経路１：Ｅ３−Ｃ２−Ｅ１：得点＝４点：”設計完了” 経路６：Ｅ７−Ｃ５−Ｃ１−Ｅ１：得点＝４点：”設計
完了” このような２回の試行により、木２は、経路２と経路４
と経路６とからなる木であり、木５は、経路５と経路３
と経路１とからなる木である。
【００２６】入力として経路が与えられる場合だけでは
なく、経路と木が混在して入力される場合でも、図３と
図５に表されている経路を木と読み替えて、新たな木の
生成方法を実行することができる。一旦木を作成した後
に、更に経路を追加して新しい木を更に生成することが
できる。
なく、経路と木が混在して入力される場合でも、図３と
図５に表されている経路を木と読み替えて、新たな木の
生成方法を実行することができる。一旦木を作成した後
に、更に経路を追加して新しい木を更に生成することが
できる。
【００２７】
【発明の効果】本発明による木構造通信路の設計方法、
及び、通信路の木構造解は、木の作成を高速に実行する
ことができる。更に、一旦作成した木に更に経路を追加
して、新しい木を更に生成することができる。
及び、通信路の木構造解は、木の作成を高速に実行する
ことができる。更に、一旦作成した木に更に経路を追加
して、新しい木を更に生成することができる。
【図１】図１は、本発明による木構造通信路の設計方法
の実施の形態を示すフローチャートである。
の実施の形態を示すフローチャートである。
【図２】図２は、木構造図である。
【図３】図３は、本発明による木構造通信路の設計方法
の部分である経路得点計算方法を示すフローチャートで
ある。
の部分である経路得点計算方法を示すフローチャートで
ある。
【図４】図４は、本発明による木構造通信路の設計方法
の部分である木の生成可能・不可能判定方法を示すフロ
ーチャートである。
の部分である木の生成可能・不可能判定方法を示すフロ
ーチャートである。
【図５】図５は、本発明による木構造通信路の設計方法
の部分である木の生成方法を示すフローチャートであ
る。
の部分である木の生成方法を示すフローチャートであ
る。
Ｅ１〜Ｅｉ…入口ノード Ｅｓ（ｓは１〜ｉ）…出口ノード Ｃ１〜Ｃｊ…接続ノード
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平９−284274（ＪＰ，Ａ) 特開 平６−112938（ＪＰ，Ａ) 特開 平６−62029（ＪＰ，Ａ) 特開 平３−230232（ＪＰ，Ａ) 特開2001−24684（ＪＰ，Ａ) 特開2001−36574（ＪＰ，Ａ) 特開2000−261476（ＪＰ，Ａ) 特開 平８−242226（ＪＰ，Ａ) 特開 平６−152593（ＪＰ，Ａ) (58)調査した分野(Int.Cl.7，ＤＢ名) H04L 12/28 H04L 12/44 - 12/46 H04L 12/00 - 12/26 H04L 12/50 - 12/66
Claims (3)
- 【請求項１】経路採点部分と、経路並べ替え部分と、並
べ替えられた経路から順に木を生成する木作成部分とを
具えるコンピュータを用いて木構造通信路を設計する木
構造通信路の設計方法であり、 複数の入口ノードと、単数の出口ノードと、前記入口ノ
ードと前記出口ノードとの間に介設されて接続される複
数の接続ノード、及び、前記入口ノードと前記出口ノー
ドと前記接続ノードとが接続される複数の経路が前記経
路採点部分に入力され、下記複数のステップ：前記経路採点部分が複数の前記経路 のうちから順次に選
択される経路に関して順次に得点を付与するステップ
と、前記経路並べ替え部分が 複数の前記経路から前記得点が
小さい順番で順序づけられた経路を選択するステップ
と、前記木作成部分が 前記順序づけられた前記経路のうちの
最も得点が低い経路とその他の経路とから木を作成する
ステップと、前記木作成部分が 前記木の作成が不可能である前記経路
のうち最も得点が低い経路とその他の未だ木として作成
されていない経路とから他の木を作成するステップとを
含み、 前記得点を付与するステップは、下記判定基準： （１）選択された経路と他の経路について、これらに共
通して現れるノードが存在しないこと、 （２）選択された経路と他の経路について、これらに共
通して現れる共通ノードが存在する場合、前記共通ノー
ドが接続する他のノードも共通していることの（１）又
は（２）のいずれかに該当すればその該当の度に加点す
ることである木構造通信路の設計方法。 - 【請求項２】請求項１において、 前記加点は＋１点である木構造通信路の設計方法。
- 【請求項３】請求項２において、 前記経路は、経路、又は、木である木構造通信路の設計
方法。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP29213199A JP3336614B2 (ja) | 1999-10-14 | 1999-10-14 | 木構造通信路の設計方法、及び、通信路の木構造解 |
| EP20000121871 EP1093311A3 (en) | 1999-10-14 | 2000-10-06 | Method for designing tree-structured communication routes and tree-structure solution of communication routes |
| US09/689,902 US6965944B1 (en) | 1999-10-14 | 2000-10-13 | Method for designing tree-structured communication routes and tree-structure solution of communication routes |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP29213199A JP3336614B2 (ja) | 1999-10-14 | 1999-10-14 | 木構造通信路の設計方法、及び、通信路の木構造解 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001111589A JP2001111589A (ja) | 2001-04-20 |
| JP3336614B2 true JP3336614B2 (ja) | 2002-10-21 |
Family
ID=17777947
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP29213199A Expired - Fee Related JP3336614B2 (ja) | 1999-10-14 | 1999-10-14 | 木構造通信路の設計方法、及び、通信路の木構造解 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6965944B1 (ja) |
| EP (1) | EP1093311A3 (ja) |
| JP (1) | JP3336614B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2883438B1 (fr) * | 2005-03-21 | 2007-05-18 | Canon Kk | Procede de construction d'une table de routage et procede de diffusion, produit programme d'ordinateur, moyens de stockage, dispositif de commutation et noeud correspondants |
| DE102009014978A1 (de) * | 2008-10-10 | 2010-04-29 | Eads Deutschland Gmbh | Rechenzeiteffiziente Routenbestimmung entlang mehrerer vorgegebener Wegpunkte mit dazwischenliegenden gegebenen Verbindungsstrecken |
| US9620022B2 (en) | 2014-06-10 | 2017-04-11 | Sikorsky Aircraft Corporation | Aircraft motion planning method |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000261476A (ja) | 1999-03-05 | 2000-09-22 | Telecommunication Advancement Organization Of Japan | ツリー構造ネットワークにおける経路図自動作成手法 |
Family Cites Families (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4466060A (en) * | 1982-02-11 | 1984-08-14 | At&T Bell Telephone Laboratories, Incorporated | Message routing in a computer network |
| US4873517A (en) * | 1988-06-23 | 1989-10-10 | International Business Machines Corporation | Method for selecting least weight end node to end node route in a data communications network |
| US4967345A (en) * | 1988-06-23 | 1990-10-30 | International Business Machines Corporation | Method of selecting least weight routes in a communications network |
| DE69025846T2 (de) * | 1989-10-13 | 1996-09-26 | Ibm | Verfahren zur Verwendung gespeicherter partieller Bäume zur Berechnung eines Weges in einem Datenkommunikationsnetz |
| JPH03230232A (ja) | 1990-02-06 | 1991-10-14 | Nec Corp | 木構造格納装置 |
| US5561790A (en) * | 1992-03-24 | 1996-10-01 | International Business Machines Corporation | Shortest path determination processes for use in modeling systems and communications networks |
| CA2094410C (en) | 1992-06-18 | 1998-05-05 | Joshua Seth Auerbach | Distributed management communications network |
| CA2094409C (en) | 1992-06-18 | 1998-07-14 | Joshua Seth Auerbach | Multicast communication tree creation and control method and apparatus |
| US5289460A (en) | 1992-07-31 | 1994-02-22 | International Business Machines Corp. | Maintenance of message distribution trees in a communications network |
| EP0684716B1 (en) * | 1994-05-25 | 2002-02-27 | International Business Machines Corporation | A data communication network and method for operating said network |
| JP3427954B2 (ja) | 1995-03-06 | 2003-07-22 | 日本電信電話株式会社 | Ｍｐパスサーチ回路 |
| JP2946193B2 (ja) | 1996-04-11 | 1999-09-06 | 株式会社超高速ネットワーク・コンピュータ技術研究所 | マルチキャスト接続経路選択方法 |
| AU5003397A (en) * | 1996-10-25 | 1998-05-15 | Cascade Communications Corporation | Multipoint-to-point packet transfer over virtual circuit |
| GB9625019D0 (en) * | 1996-11-29 | 1997-01-15 | Northern Telecom Ltd | Network restoration routing optimisation |
| US6415312B1 (en) * | 1999-01-29 | 2002-07-02 | International Business Machines Corporation | Reliable multicast for small groups |
| US6496485B1 (en) | 1999-06-14 | 2002-12-17 | Hewlett-Packard Company | Method of loop breaking tree indentification in a system bus hierarcy |
| IL130895A (en) * | 1999-07-12 | 2003-10-31 | Ectel Ltd | Method and system for controlling quality of service over a telecommunication network |
| JP3351394B2 (ja) | 1999-07-15 | 2002-11-25 | 日本電気株式会社 | 木構造を持つ通信路の設計回路及び木構造を持つ通信路の設計方法並びにコンピュータ可読記録媒体 |
| US6584071B1 (en) * | 1999-08-03 | 2003-06-24 | Lucent Technologies Inc. | Routing with service level guarantees between ingress-egress points in a packet network |
-
1999
- 1999-10-14 JP JP29213199A patent/JP3336614B2/ja not_active Expired - Fee Related
-
2000
- 2000-10-06 EP EP20000121871 patent/EP1093311A3/en not_active Withdrawn
- 2000-10-13 US US09/689,902 patent/US6965944B1/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000261476A (ja) | 1999-03-05 | 2000-09-22 | Telecommunication Advancement Organization Of Japan | ツリー構造ネットワークにおける経路図自動作成手法 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP1093311A3 (en) | 2003-09-10 |
| JP2001111589A (ja) | 2001-04-20 |
| US6965944B1 (en) | 2005-11-15 |
| EP1093311A2 (en) | 2001-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6564211B1 (en) | Fast flexible search engine for longest prefix match | |
| DE69531337T2 (de) | Weglenkung von Transaktionsnachrichten in einem digitalen Kommunikationsnetz | |
| JP3485262B2 (ja) | データ・パケットを分類する方法および手段 | |
| US7664040B2 (en) | Method of accelerating the shortest path problem | |
| KR0153392B1 (ko) | Lsi용 상호접속 배선 설계 방법 | |
| US7379424B1 (en) | Systems and methods for routing packets in multiprocessor computer systems | |
| US20020083159A1 (en) | Designing interconnect fabrics | |
| JP2505064B2 (ja) | 経路選択方法 | |
| EP1235461A3 (en) | A method of admission control and routing of virtual circuits | |
| JPH077427B2 (ja) | ノードの相互接続方法 | |
| JPH031275A (ja) | データ分類及び認識方法 | |
| US6766502B1 (en) | Method and apparatus for routing using deferred merging | |
| US20030208495A1 (en) | User selectable editing protocol for fast flexible search engine | |
| US20050163122A1 (en) | System and methods for packet filtering | |
| US20030172180A1 (en) | Efficient system and method of node and link insertion for deadlock-free routing on arbitrary topologies | |
| US6516319B1 (en) | Parallelized processing device for processing search keys based upon tree structure | |
| JP2001111589A (ja) | 木構造通信路の設計方法、及び、通信路の木構造解 | |
| Bateman et al. | Decidability and undecidability of theories with a predicate for the primes | |
| CN118690864A (zh) | 基于模式树的量子线路模式匹配方法 | |
| KR20010024944A (ko) | 전자 소자 및 장치의 설계 및 제조 방법 | |
| KR970060353A (ko) | 포토마스크에 대한 위상쉬프터 배치방법 및 기억매체 | |
| JP3199914B2 (ja) | フレーム中継制御方法、及びその装置 | |
| JPS63158935A (ja) | ネットワ−クの経路選択方法 | |
| JP2978648B2 (ja) | ネットワークシステムの最適方路決定方法 | |
| Hoffmann | Towards optimizing global MinCut partitioning |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20020708 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070809 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080809 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080809 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090809 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090809 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100809 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110809 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110809 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120809 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130809 Year of fee payment: 11 |
|
| LAPS | Cancellation because of no payment of annual fees |