JPH1168838A - 経路選択方法 - Google Patents
経路選択方法Info
- Publication number
- JPH1168838A JPH1168838A JP23045097A JP23045097A JPH1168838A JP H1168838 A JPH1168838 A JP H1168838A JP 23045097 A JP23045097 A JP 23045097A JP 23045097 A JP23045097 A JP 23045097A JP H1168838 A JPH1168838 A JP H1168838A
- Authority
- JP
- Japan
- Prior art keywords
- cost
- route
- qos
- range
- conditions
- 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
Classifications
-
- 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
- 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
- H04L45/10—Routing in connection-oriented networks, e.g. X.25 or ATM
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
- H04L2012/562—Routing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5638—Services, e.g. multimedia, GOS, QOS
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Feedback Control In General (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【課題】 コストに関して予め誤差範囲を指定すると、
複数のＱｏＳ条件を低コストで全て満足し、かつコスト
が誤差範囲内にある経路を最適経路として選択する経路
選択方法を提供する。 【解決手段】 ステップＳ１では、満足すべき複数のＱ
ｏＳ条件が設定される。ステップＳ２では、近似誤差ε
が入力される。ステップＳ３では、最適経路を検索する
コストの範囲を暫定的に設定する。ステップＳ４では、
最適解コスト近似手続が実行される。ステップＳ５で
は、前記コスト範囲が十分に狭まったか否かが判定さ
れ、狭められたコスト範囲が依然として広過ぎれば、前
記ステップＳ４へ戻って最適解コスト近似手続を繰り返
す。また、既にコスト範囲が十分に狭まっていれば、ス
テップＳ６の最適解求解手続が実行される。
複数のＱｏＳ条件を低コストで全て満足し、かつコスト
が誤差範囲内にある経路を最適経路として選択する経路
選択方法を提供する。 【解決手段】 ステップＳ１では、満足すべき複数のＱ
ｏＳ条件が設定される。ステップＳ２では、近似誤差ε
が入力される。ステップＳ３では、最適経路を検索する
コストの範囲を暫定的に設定する。ステップＳ４では、
最適解コスト近似手続が実行される。ステップＳ５で
は、前記コスト範囲が十分に狭まったか否かが判定さ
れ、狭められたコスト範囲が依然として広過ぎれば、前
記ステップＳ４へ戻って最適解コスト近似手続を繰り返
す。また、既にコスト範囲が十分に狭まっていれば、ス
テップＳ６の最適解求解手続が実行される。
Description
【０００１】
【発明の属する技術分野】本発明は、始点と終点とを結
ぶ複数の経路の中から、所望のＱｏＳ条件を満足する経
路を選択する経路選択方法に係り、特に、コストに関し
て予め誤差範囲を指定すると、複数のＱｏＳ条件を低コ
ストで全て満足し、かつコストが誤差範囲内にある経路
を最適経路として選択する経路選択方法に関する。
ぶ複数の経路の中から、所望のＱｏＳ条件を満足する経
路を選択する経路選択方法に係り、特に、コストに関し
て予め誤差範囲を指定すると、複数のＱｏＳ条件を低コ
ストで全て満足し、かつコストが誤差範囲内にある経路
を最適経路として選択する経路選択方法に関する。
【０００２】
【従来の技術】ネットワークの高度利用を図るために
は、通信経路の帯域幅、伝送遅延および誤り率といった
複数のＱｏＳ（Quality of Service）に関して所望条件
を低コストで同時に満足する経路選択技術が必要不可欠
である。また、近年普及しつつあるＡＴＭ（Asynchrono
us Transfer Mode）においても、セル許容遅延、セル転
送最大遅延、あるいはセル損失率等の複数のＱｏＳが定
義されており、これら複数のＱｏＳに関して所望条件を
満足し得る通信経路選択技術の重要性が増している。こ
こで、ＱｏＳは、その性質によって以下の３種類に大別
することができる。 加法性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の和となる性質であり、例えば伝送遅延やセル転送最大
遅延が当てはまる。 乗法性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の積の関数となる性質であり、例えば誤り率やセル損失
率が当てはまる。 凹性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の最小値となる性質であり、例えば帯域幅が当てはま
る。
は、通信経路の帯域幅、伝送遅延および誤り率といった
複数のＱｏＳ（Quality of Service）に関して所望条件
を低コストで同時に満足する経路選択技術が必要不可欠
である。また、近年普及しつつあるＡＴＭ（Asynchrono
us Transfer Mode）においても、セル許容遅延、セル転
送最大遅延、あるいはセル損失率等の複数のＱｏＳが定
義されており、これら複数のＱｏＳに関して所望条件を
満足し得る通信経路選択技術の重要性が増している。こ
こで、ＱｏＳは、その性質によって以下の３種類に大別
することができる。 加法性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の和となる性質であり、例えば伝送遅延やセル転送最大
遅延が当てはまる。 乗法性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の積の関数となる性質であり、例えば誤り率やセル損失
率が当てはまる。 凹性 経路のＱｏＳ値が、経路を構成する各リンクのＱｏＳ値
の最小値となる性質であり、例えば帯域幅が当てはま
る。
【０００３】ここで、複数のＱｏＳを考慮して低コスト
の経路を選択する従来技術として、「ｒｕｌｅ−ｂａｓ
ｅｄ経路選択方式」を図８のフローチャートを参照して
説明する。ここでは、図９に示したように、ノード数が
１０（Ａ〜Ｊ）のネットワーク上で、ノードＡ（始点）
からノードＪ（終点）まで所望のＱｏＳ条件を全て満足
する最低コストの経路を選択する場合を考える。なお、
各ノード間のリンクコスト、帯域幅、伝送遅延および誤
り率は、図１０に示した通りであるものとし、満足すべ
きＱｏＳ条件は以下の３条件であるものとする。 ＱｏＳ条件１…帯域幅が３以上であること ＱｏＳ条件２…伝送遅延が１６以下であること ＱｏＳ条件３…誤り率がＯ．Ｏ５以下であること ステップＳ１では、凹性のＱｏＳである帯域幅につい
て、その所望条件を満足しないリンクが経路選択の対象
から除外される。本実施形態では、ＤＪ間の帯域幅が
“２”であって前記ＱｏＳ条件１を満足しないので、当
該経路ＤＪが経路選択の対象から除外される。ステップ
Ｓ２では、満足すべき他のＱｏＳ条件に優先順位を付け
ると共に、後に詳述する最大試行回数Ｎを決定する。本
実施形態では、ＱｏＳ条件２（伝送遅延）がＱｏＳ条件
３（誤り率）に優先するものとし、最大試行回数Ｎを２
回に設定したものとして説明する。
の経路を選択する従来技術として、「ｒｕｌｅ−ｂａｓ
ｅｄ経路選択方式」を図８のフローチャートを参照して
説明する。ここでは、図９に示したように、ノード数が
１０（Ａ〜Ｊ）のネットワーク上で、ノードＡ（始点）
からノードＪ（終点）まで所望のＱｏＳ条件を全て満足
する最低コストの経路を選択する場合を考える。なお、
各ノード間のリンクコスト、帯域幅、伝送遅延および誤
り率は、図１０に示した通りであるものとし、満足すべ
きＱｏＳ条件は以下の３条件であるものとする。 ＱｏＳ条件１…帯域幅が３以上であること ＱｏＳ条件２…伝送遅延が１６以下であること ＱｏＳ条件３…誤り率がＯ．Ｏ５以下であること ステップＳ１では、凹性のＱｏＳである帯域幅につい
て、その所望条件を満足しないリンクが経路選択の対象
から除外される。本実施形態では、ＤＪ間の帯域幅が
“２”であって前記ＱｏＳ条件１を満足しないので、当
該経路ＤＪが経路選択の対象から除外される。ステップ
Ｓ２では、満足すべき他のＱｏＳ条件に優先順位を付け
ると共に、後に詳述する最大試行回数Ｎを決定する。本
実施形態では、ＱｏＳ条件２（伝送遅延）がＱｏＳ条件
３（誤り率）に優先するものとし、最大試行回数Ｎを２
回に設定したものとして説明する。
【０００４】ステップＳ３では、コスト関数またはいず
れかのＱｏＳ条件が選択されるが、最初は常にコスト関
数が選択される。ステップＳ４では、前記ステップＳ３
で選択された条件、すなわち最初はコスト関数が最小と
なる経路Ｐ0 が、他のＱｏＳ条件を無視して選択され
る。図１０に示した例では、始点Ａ→Ｇ→Ｈ→Ｉ→終点
Ｊの経路Ｐ0 が選択される。ステップＳ５では、経路Ｐ
0 が全てのＱｏＳ条件を満足しているか否かが判定され
る。上記した経路Ｐ0 では、伝送遅延が“２８”となっ
て前記ＱｏＳ条件２を満足しないのでステップＳ８へ進
む。
れかのＱｏＳ条件が選択されるが、最初は常にコスト関
数が選択される。ステップＳ４では、前記ステップＳ３
で選択された条件、すなわち最初はコスト関数が最小と
なる経路Ｐ0 が、他のＱｏＳ条件を無視して選択され
る。図１０に示した例では、始点Ａ→Ｇ→Ｈ→Ｉ→終点
Ｊの経路Ｐ0 が選択される。ステップＳ５では、経路Ｐ
0 が全てのＱｏＳ条件を満足しているか否かが判定され
る。上記した経路Ｐ0 では、伝送遅延が“２８”となっ
て前記ＱｏＳ条件２を満足しないのでステップＳ８へ進
む。
【０００５】ステップＳ８では、試行回数ｎが最大試行
回数Ｎを越えたか否かが判定され、ここでは未だ越えて
いないのでステップＳ７へ進み、試行回数ｎを“１”だ
けインクリメンしてステップＳ３へ戻る。ステップＳ３
では、今度は優先順位の高いＱｏＳ条件２（伝送遅延）
が選択され、ステップＳ４では伝送遅延が最小となる経
路Ｐ1 が、他のＱｏＳ条件を無視して選択される。
回数Ｎを越えたか否かが判定され、ここでは未だ越えて
いないのでステップＳ７へ進み、試行回数ｎを“１”だ
けインクリメンしてステップＳ３へ戻る。ステップＳ３
では、今度は優先順位の高いＱｏＳ条件２（伝送遅延）
が選択され、ステップＳ４では伝送遅延が最小となる経
路Ｐ1 が、他のＱｏＳ条件を無視して選択される。
【０００６】本実施形態では、始点Ａ→Ｅ→Ｈ→Ｉ→終
点Ｊの経路Ｐ1 が選択される。ステップＳ５では、経路
Ｐ1 が他の全てのＱｏＳ条件を同時に満足しているか否
かが判定される。本実施形態では、上記した経路Ｐ1 で
の誤り率はＯ．Ｏ５以下となって前記ＱｏＳ条件３を満
足するので、全てのＱｏＳ条件が満足されたものとして
ステップＳ６へ進む。ステップＳ６では、当該経路Ｐ1
を最適経路として出力する。
点Ｊの経路Ｐ1 が選択される。ステップＳ５では、経路
Ｐ1 が他の全てのＱｏＳ条件を同時に満足しているか否
かが判定される。本実施形態では、上記した経路Ｐ1 で
の誤り率はＯ．Ｏ５以下となって前記ＱｏＳ条件３を満
足するので、全てのＱｏＳ条件が満足されたものとして
ステップＳ６へ進む。ステップＳ６では、当該経路Ｐ1
を最適経路として出力する。
【０００７】なお、前記ステップＳ５の判定が繰り返し
否定となり、ステップＳ８において試行回数ｎが最大試
行回数Ｎを越えてしまうと、ステップＳ９では、条件に
合致する経路がない旨の情報を出力する。
否定となり、ステップＳ８において試行回数ｎが最大試
行回数Ｎを越えてしまうと、ステップＳ９では、条件に
合致する経路がない旨の情報を出力する。
【０００８】
【発明が解決しようとする課題】上記した従来技術で
は、次のような問題点があった。 (1) 近似精度が経験則に依存する。
は、次のような問題点があった。 (1) 近似精度が経験則に依存する。
【０００９】前記ステップＳ２では、利用者の経験則に
基づいて各ＱｏＳ条件に優先順序を設定し、この優先順
序に従って各ＱｏＳ条件を満足する経路の有無が順次判
定される。このため、各ＱｏＳ条件の種類や性質に関す
る知識がなければ、最適な、または近似精度の高い経路
を選択することができない。
基づいて各ＱｏＳ条件に優先順序を設定し、この優先順
序に従って各ＱｏＳ条件を満足する経路の有無が順次判
定される。このため、各ＱｏＳ条件の種類や性質に関す
る知識がなければ、最適な、または近似精度の高い経路
を選択することができない。
【００１０】例えば、前記ステップＳ２において、上記
とは逆にＱｏＳ条件３（誤り率）がＱｏＳ条件２（伝送
遅延）に優先するように指定すると、ステップＳ３で
は、始点Ａ→Ｂ→Ｃ→Ｆ→終点Ｊが誤り率最小経路Ｐ2
として選択される。この経路Ｐ2 の伝送遅延は“１４”
となり、全てのＱｏＳ条件を満足する。そして、経路Ｐ
2 のリンクコストの和は“２６”であり、前記経路Ｐ１
のコスト“３２”よりも小さくなる。
とは逆にＱｏＳ条件３（誤り率）がＱｏＳ条件２（伝送
遅延）に優先するように指定すると、ステップＳ３で
は、始点Ａ→Ｂ→Ｃ→Ｆ→終点Ｊが誤り率最小経路Ｐ2
として選択される。この経路Ｐ2 の伝送遅延は“１４”
となり、全てのＱｏＳ条件を満足する。そして、経路Ｐ
2 のリンクコストの和は“２６”であり、前記経路Ｐ１
のコスト“３２”よりも小さくなる。
【００１１】このように，ＱｏＳの優先順序の設定いか
んによって選択経路が異なるため、近似精度が経験則に
依存することになる。ＱｏＳ条件の個数ｒが増大すれ
ば、ＱｏＳに関する優先順序の割り当て方はｒ！＝ｒ×
（ｒ−１）×・・・２×１となるため、近似精度は更に経
験則に依存することになる。 (2) 近似精度が固定である。
んによって選択経路が異なるため、近似精度が経験則に
依存することになる。ＱｏＳ条件の個数ｒが増大すれ
ば、ＱｏＳに関する優先順序の割り当て方はｒ！＝ｒ×
（ｒ−１）×・・・２×１となるため、近似精度は更に経
験則に依存することになる。 (2) 近似精度が固定である。
【００１２】近似比率がノードやリンクの個数、または
コスト、帯域輻、伝送遅廷および誤り率等のネットワー
ク構成によって固定的に決まってしまう。このため、ネ
ットワーク提供者やネットワーク利用者の望むＱｏＳ条
件を満足するネットワーク資源を柔軟に割り当てられな
い事態が生じる。
コスト、帯域輻、伝送遅廷および誤り率等のネットワー
ク構成によって固定的に決まってしまう。このため、ネ
ットワーク提供者やネットワーク利用者の望むＱｏＳ条
件を満足するネットワーク資源を柔軟に割り当てられな
い事態が生じる。
【００１３】例えば、上記した従来方式では、コストに
関わらず伝送遅延が最小となる経路＝Ａ→Ｅ→Ｈ→Ｉ→
Ｊが選択されるが、この経路のリンクコストの和は“３
２”であるのに対して最適解のリンクコストの和は１４
であり、近似比は３２／１４で約２．３となる。したが
って、任意のネットワークにおける近似比の最大値、す
なわち近似比率は少なくとも２．３になる。
関わらず伝送遅延が最小となる経路＝Ａ→Ｅ→Ｈ→Ｉ→
Ｊが選択されるが、この経路のリンクコストの和は“３
２”であるのに対して最適解のリンクコストの和は１４
であり、近似比は３２／１４で約２．３となる。したが
って、任意のネットワークにおける近似比の最大値、す
なわち近似比率は少なくとも２．３になる。
【００１４】このように、上記した従来技術では、近似
比率がリンクコスト等のネットワーク構成によって固定
的に決まってしまうため、例えば近似比率を２．３より
も小さくして、より近似精度の高い経路を任意のネット
ワークにおいて求めようとしても、このような要求には
応えられないという問題があった。
比率がリンクコスト等のネットワーク構成によって固定
的に決まってしまうため、例えば近似比率を２．３より
も小さくして、より近似精度の高い経路を任意のネット
ワークにおいて求めようとしても、このような要求には
応えられないという問題があった。
【００１５】本発明の目的は、上記した従来技術の問題
点を解決し、利用者の経験則に依存せず、任意の近似誤
差εを実行時に指定すれば、ネットワーク構成とは無関
係に所望の近似比率（１＋ε）を満足する最適経路を選
択し得る経路選択方法を提供することにある。
点を解決し、利用者の経験則に依存せず、任意の近似誤
差εを実行時に指定すれば、ネットワーク構成とは無関
係に所望の近似比率（１＋ε）を満足する最適経路を選
択し得る経路選択方法を提供することにある。
【００１６】
【課題を解決するための手段】上記した目的を達成する
ために、本発明では、始点と終点とを結ぶ複数の経路の
中から、複数のＱｏＳ条件を低コストで満足する経路を
選択する経路選択方法において、複数のＱｏＳ条件をそ
れぞれ設定し、未知の最適経路のコストに対して許容し
得る誤差範囲を入力し、少なくとも最適経路のコストを
含むコスト範囲を暫定的に設定し、前記コスト範囲が、
前記誤差範囲の関数である基準範囲まで減縮されている
か否かを判定し、減縮されていないと判定されると、現
在のコスト範囲内で最低コストから順に、当該コストで
始点から各ノードへ至るまでの複数のＱｏＳを、既にＱ
ｏＳが求められたノードの各ＱｏＳに基づいて求め、前
記複数のＱｏＳ条件を全て満足して始点から終点へ至る
経路が、前記誤差範囲の関数として与えられる基準コス
トまでに見つかるか否かに基づいて前記コスト範囲を減
縮し、減縮されたコスト範囲を対象に最適経路を検索す
るようにした。
ために、本発明では、始点と終点とを結ぶ複数の経路の
中から、複数のＱｏＳ条件を低コストで満足する経路を
選択する経路選択方法において、複数のＱｏＳ条件をそ
れぞれ設定し、未知の最適経路のコストに対して許容し
得る誤差範囲を入力し、少なくとも最適経路のコストを
含むコスト範囲を暫定的に設定し、前記コスト範囲が、
前記誤差範囲の関数である基準範囲まで減縮されている
か否かを判定し、減縮されていないと判定されると、現
在のコスト範囲内で最低コストから順に、当該コストで
始点から各ノードへ至るまでの複数のＱｏＳを、既にＱ
ｏＳが求められたノードの各ＱｏＳに基づいて求め、前
記複数のＱｏＳ条件を全て満足して始点から終点へ至る
経路が、前記誤差範囲の関数として与えられる基準コス
トまでに見つかるか否かに基づいて前記コスト範囲を減
縮し、減縮されたコスト範囲を対象に最適経路を検索す
るようにした。
【００１７】上記した経路選択方法によれば、ＱｏＳ条
件に関するオペレータの知識や経験に左右されることな
く、予め指定した誤差範囲内に収まる実質的に最適な経
路を選択できるようになる。
件に関するオペレータの知識や経験に左右されることな
く、予め指定した誤差範囲内に収まる実質的に最適な経
路を選択できるようになる。
【００１８】
【発明の実施の形態】以下、図面を参照して本発明を詳
細に説明する。ここでは、初めに本発明の基本概念につ
いて簡単に説明し、その後で具体的事例を参照して詳細
に説明するものとする。
細に説明する。ここでは、初めに本発明の基本概念につ
いて簡単に説明し、その後で具体的事例を参照して詳細
に説明するものとする。
【００１９】図１は、本発明の一実施形態である経路選
択方法の概略動作を示したフローチャートである。ここ
では、前記図１０に示したように、複数の中継ノードを
経由して始点Ａと終点Ｊとを結ぶ複数の経路の中から、
複数のＱｏＳ条件を低コストで同時に満足する最適経路
を選択する場合を例にして説明する。
択方法の概略動作を示したフローチャートである。ここ
では、前記図１０に示したように、複数の中継ノードを
経由して始点Ａと終点Ｊとを結ぶ複数の経路の中から、
複数のＱｏＳ条件を低コストで同時に満足する最適経路
を選択する場合を例にして説明する。
【００２０】ステップＳ１では、満足すべき複数のＱｏ
Ｓ条件として、例えば帯域幅、伝送遅延および誤り率等
のＱｏＳに関する所望条件が設定される。ステップＳ２
では、複数のＱｏＳ条件を全て満足する経路の中で、コ
ストが最小となる未知の最適経路のコスト（最適コス
ト）に対して、許容し得る近似誤差εが入力される。す
なわち、最適コストの１．５倍（すなわち、近似比率が
１．５）までのコスト負担が必要な経路を許容するので
あれば、近似誤差εとして０．５が入力される。
Ｓ条件として、例えば帯域幅、伝送遅延および誤り率等
のＱｏＳに関する所望条件が設定される。ステップＳ２
では、複数のＱｏＳ条件を全て満足する経路の中で、コ
ストが最小となる未知の最適経路のコスト（最適コス
ト）に対して、許容し得る近似誤差εが入力される。す
なわち、最適コストの１．５倍（すなわち、近似比率が
１．５）までのコスト負担が必要な経路を許容するので
あれば、近似誤差εとして０．５が入力される。
【００２１】ステップＳ３では、前記最適コストを含む
上限値ＣUBおよび下限値ＣLBを適宜に設定することで、
最適経路を検索するコストの範囲（以下、単にコスト範
囲と表現する）を暫定的に設定する。すなわち、最適コ
ストが、例えば３０±２０の範囲にあると予測される場
合、検索コスト範囲の上限値ＣUBとして１０（３０−２
０）、下限値ＣLBとして５０（３０＋２０）が設定さ
れ、コスト範囲が１０〜５０の範囲に絞り込まれる。
上限値ＣUBおよび下限値ＣLBを適宜に設定することで、
最適経路を検索するコストの範囲（以下、単にコスト範
囲と表現する）を暫定的に設定する。すなわち、最適コ
ストが、例えば３０±２０の範囲にあると予測される場
合、検索コスト範囲の上限値ＣUBとして１０（３０−２
０）、下限値ＣLBとして５０（３０＋２０）が設定さ
れ、コスト範囲が１０〜５０の範囲に絞り込まれる。
【００２２】ステップＳ４では、後に詳述する最適解コ
スト近似手続が実行される。最適解コスト近似手続と
は、後にステップＳ６において実行される最適解求解手
続で検索するコスト範囲を予め狭めるための前処理であ
り、最適解求解手続で費やされる検索時間を短縮する目
的で実行される。
スト近似手続が実行される。最適解コスト近似手続と
は、後にステップＳ６において実行される最適解求解手
続で検索するコスト範囲を予め狭めるための前処理であ
り、最適解求解手続で費やされる検索時間を短縮する目
的で実行される。
【００２３】図２は、前記最適解コスト近似手続と最適
解求解手続の関係を模式的に表現した図である。例え
ば、始点Ａから終点Ｊへ至るまでのリンクコストの和と
してコスト１から１００までを取り得る場合、最適解求
解手続のみで最適コストを求めようとすると、初めに始
点Ａと終点Ｊとをコスト１で結ぶ経路の有無を判定し、
無ければ今度はコスト２で結ぶ経路の有無を判定し、…
といったように、全てのコスト範囲（１〜１００）を検
索しなければならない。このため、最適解求解手続では
最適経路および最適コストを求めることができる反面、
それまでに長時間を要するという問題があった。
解求解手続の関係を模式的に表現した図である。例え
ば、始点Ａから終点Ｊへ至るまでのリンクコストの和と
してコスト１から１００までを取り得る場合、最適解求
解手続のみで最適コストを求めようとすると、初めに始
点Ａと終点Ｊとをコスト１で結ぶ経路の有無を判定し、
無ければ今度はコスト２で結ぶ経路の有無を判定し、…
といったように、全てのコスト範囲（１〜１００）を検
索しなければならない。このため、最適解求解手続では
最適経路および最適コストを求めることができる反面、
それまでに長時間を要するという問題があった。
【００２４】このような問題を解消するために、本発明
では前記図１のステップＳ３において、検索対象のコス
ト範囲に関する上限値ＣUBおよび下限値ＣLBを設定して
予めコスト範囲を狭めておく。そして、依然としてコス
ト範囲が広いようであれば、コスト範囲を更に狭めるた
めに、最適解求解手続に先立って最適解コスト近似手続
を繰り返し実行してコスト範囲を狭め、最適解求解手続
が狭いコスト範囲に対してのみ実行されるようにしてい
る。
では前記図１のステップＳ３において、検索対象のコス
ト範囲に関する上限値ＣUBおよび下限値ＣLBを設定して
予めコスト範囲を狭めておく。そして、依然としてコス
ト範囲が広いようであれば、コスト範囲を更に狭めるた
めに、最適解求解手続に先立って最適解コスト近似手続
を繰り返し実行してコスト範囲を狭め、最適解求解手続
が狭いコスト範囲に対してのみ実行されるようにしてい
る。
【００２５】さらに具体的にいえば、ステップＳ４の最
適解コスト近似手続では、任意コストＶの経路が複数の
ＱｏＳ条件を全て満足するか否かを判定する（ステップ
Ｓ４ａ）。当該経路が全てのＱｏＳ条件を満足すれば、
最適コストは任意コストＶ以下であることが判明する。
これとは逆に、満足されないＱｏＳ条件が一つでもあれ
ば、最適コストは任意コストＶ以上であることが判明す
る。したがって、前記判定結果に基づいてコスト範囲を
狭めることができる（ステップＳ４ｂ）。
適解コスト近似手続では、任意コストＶの経路が複数の
ＱｏＳ条件を全て満足するか否かを判定する（ステップ
Ｓ４ａ）。当該経路が全てのＱｏＳ条件を満足すれば、
最適コストは任意コストＶ以下であることが判明する。
これとは逆に、満足されないＱｏＳ条件が一つでもあれ
ば、最適コストは任意コストＶ以上であることが判明す
る。したがって、前記判定結果に基づいてコスト範囲を
狭めることができる（ステップＳ４ｂ）。
【００２６】ステップＳ５では、前記コスト範囲が十分
に狭まったか否かが判定され、狭められたコスト範囲が
依然として広過ぎれば、前記ステップＳ４へ戻って最適
解コスト近似手続を繰り返す。また、既にコスト範囲が
十分に狭まっていれば、ステップＳ６の最適解求解手続
が実行される。
に狭まったか否かが判定され、狭められたコスト範囲が
依然として広過ぎれば、前記ステップＳ４へ戻って最適
解コスト近似手続を繰り返す。また、既にコスト範囲が
十分に狭まっていれば、ステップＳ６の最適解求解手続
が実行される。
【００２７】ステップＳ６では、狭められたコスト範囲
内でリンクコストが低い経路から順に、各経路に関する
複数のＱｏＳ値を求め（ステップＳ６ａ）、全てのＱｏ
Ｓ条件が最初に満足される経路を実質的な最適経路とみ
なす（ステップＳ６ｂ）。
内でリンクコストが低い経路から順に、各経路に関する
複数のＱｏＳ値を求め（ステップＳ６ａ）、全てのＱｏ
Ｓ条件が最初に満足される経路を実質的な最適経路とみ
なす（ステップＳ６ｂ）。
【００２８】図３は、前記最適解求解手続の内容を説明
するための図であり、図１１は、その動作を示したフロ
ーチャートである。
するための図であり、図１１は、その動作を示したフロ
ーチャートである。
【００２９】ステップＳ５１では、最小コスト（＝１）
から順に、始点Ａから各ノードに至るまでの各ＱｏＳ値
をコストごとに求めるために、コスト変数ｃが初期値
“１”に設定される。ステップＳ５２では、各コストご
とに、始点Ａ（１番目）からｉ番目のノードに至るまで
の全てのＱｏＳを求めるために、ノード変数ｉが初期値
“２”に設定される。
から順に、始点Ａから各ノードに至るまでの各ＱｏＳ値
をコストごとに求めるために、コスト変数ｃが初期値
“１”に設定される。ステップＳ５２では、各コストご
とに、始点Ａ（１番目）からｉ番目のノードに至るまで
の全てのＱｏＳを求めるために、ノード変数ｉが初期値
“２”に設定される。
【００３０】ステップＳ５３では、コストがコスト変数
ｃ（ここでは、“１”）と一致する経路について、始点
Ａからｉ番目のノード（ここでは、２番目のノードＢ）
に至るまでの全てのＱｏＳを求める。
ｃ（ここでは、“１”）と一致する経路について、始点
Ａからｉ番目のノード（ここでは、２番目のノードＢ）
に至るまでの全てのＱｏＳを求める。
【００３１】ステップＳ５４では、ノード変数ｉがｎか
否か、すなわちコスト変数がｃ（＝１）である経路につ
いて終点Ｊまで処理が進んだか否かが判定され、初めは
ｎ以下なのでステップＳ５６へ進む。ステップＳ５６で
は、ノード変数ｉを１だけインクリメントしてステップ
Ｓ５３へ戻る。
否か、すなわちコスト変数がｃ（＝１）である経路につ
いて終点Ｊまで処理が進んだか否かが判定され、初めは
ｎ以下なのでステップＳ５６へ進む。ステップＳ５６で
は、ノード変数ｉを１だけインクリメントしてステップ
Ｓ５３へ戻る。
【００３２】以下同様に、コスト変数ｃが“１”の場合
について、ノード変数ｉがｎに達するまで、ノード変数
ｉがインクリメントされるごとにステップＳ５３、Ｓ５
４、Ｓ５６の処理が繰り返される。ところが、本実施形
態では始点Ａと各ノードＢ，Ｅ，Ｇとの間のコストが、
図１０に示したように、それぞれ２、２６、２であり、
既にコスト変数ｃ（＝１）を越えているので、図３に示
したように、コスト変数ｃ（＝１）に関する各ＱｏＳ欄
（１，Ｂ）〜（１，Ｊ）にはＱｏＳ値が登録されない。
について、ノード変数ｉがｎに達するまで、ノード変数
ｉがインクリメントされるごとにステップＳ５３、Ｓ５
４、Ｓ５６の処理が繰り返される。ところが、本実施形
態では始点Ａと各ノードＢ，Ｅ，Ｇとの間のコストが、
図１０に示したように、それぞれ２、２６、２であり、
既にコスト変数ｃ（＝１）を越えているので、図３に示
したように、コスト変数ｃ（＝１）に関する各ＱｏＳ欄
（１，Ｂ）〜（１，Ｊ）にはＱｏＳ値が登録されない。
【００３３】その後、ステップＳ５４においてノード変
数ｉがｎと一致したと判定されると、ステップＳ５５へ
進む。ステップＳ５５では、始点Ａから終点Ｊに至るま
での経路が全てのＱｏＳ条件を満足しているか否かが判
定される。本実施形態では、コスト変数ｃが“１”の経
路は存在せず、各ＱｏＳ欄にはＱｏＳ値が登録されてい
ない。したがって、当該ステップＳ５５の判定は否定と
なってステップＳ５８へ進む。ステップＳ５８では、コ
スト変数ｃが１だけインクリメントされ、その後ステッ
プＳ５２へ戻る。
数ｉがｎと一致したと判定されると、ステップＳ５５へ
進む。ステップＳ５５では、始点Ａから終点Ｊに至るま
での経路が全てのＱｏＳ条件を満足しているか否かが判
定される。本実施形態では、コスト変数ｃが“１”の経
路は存在せず、各ＱｏＳ欄にはＱｏＳ値が登録されてい
ない。したがって、当該ステップＳ５５の判定は否定と
なってステップＳ５８へ進む。ステップＳ５８では、コ
スト変数ｃが１だけインクリメントされ、その後ステッ
プＳ５２へ戻る。
【００３４】次いで、コスト変数ｃが“２”の経路につ
いて、ノード変数ｉがｎに達するまでステップＳ５２〜
Ｓ５６の処理が前記と同様にして繰り返される。本実施
形態では、ノードＢ，ノードＧまでの経路のコスト変数
ｃが“２”なので、図３に示したように、ＱｏＳ欄
（２、Ｂ）には、帯域幅、伝送遅延、誤り率に関するＱ
ｏＳとして、（３，２，０．００５）が格納される。
いて、ノード変数ｉがｎに達するまでステップＳ５２〜
Ｓ５６の処理が前記と同様にして繰り返される。本実施
形態では、ノードＢ，ノードＧまでの経路のコスト変数
ｃが“２”なので、図３に示したように、ＱｏＳ欄
（２、Ｂ）には、帯域幅、伝送遅延、誤り率に関するＱ
ｏＳとして、（３，２，０．００５）が格納される。
【００３５】しかしながら、本実施形態ではノードＡか
らノードＢへ至る経路のコストが既に“２”であり、コ
スト“２”ではノードＢから次のノードへ進めないの
で、ＱｏＳ欄（２、Ｃ）〜（２、Ｊ）にはＱｏＳ値が登
録されない。同様に、コスト“３”でもノードＢから次
のノードへ進めないので、ＱｏＳ欄（３、Ｂ）には前記
と同様にＱｏＳ値（３，２，０．００５）が登録される
が、ＱｏＳ欄（３、Ｃ）〜（３、Ｊ）にはＱｏＳ値が登
録される。
らノードＢへ至る経路のコストが既に“２”であり、コ
スト“２”ではノードＢから次のノードへ進めないの
で、ＱｏＳ欄（２、Ｃ）〜（２、Ｊ）にはＱｏＳ値が登
録されない。同様に、コスト“３”でもノードＢから次
のノードへ進めないので、ＱｏＳ欄（３、Ｂ）には前記
と同様にＱｏＳ値（３，２，０．００５）が登録される
が、ＱｏＳ欄（３、Ｃ）〜（３、Ｊ）にはＱｏＳ値が登
録される。
【００３６】コスト“４”では、ノードＢからノードＣ
まで進めるので、ＱｏＳ欄（４、Ｂ）には前記と同様に
ＱｏＳ値（３，２，０．００５）が登録され、ＱｏＳ欄
（４、Ｃ）にはＱｏＳ値（３，４，０．００９７５）が
登録される。
まで進めるので、ＱｏＳ欄（４、Ｂ）には前記と同様に
ＱｏＳ値（３，２，０．００５）が登録され、ＱｏＳ欄
（４、Ｃ）にはＱｏＳ値（３，４，０．００９７５）が
登録される。
【００３７】以下同様に、コスト変数ごとに各ノードへ
至るまでのＱｏＳ値が求められ、ノードＪへ至る経路が
あると、その時の各ＱｏＳ値が基準値と比較される。そ
の結果、たとえ一つのＱｏＳ値でも基準条件を満足して
いなければ、当該処理はステップＳ５５からステップＳ
５８へ戻り、コスト変数をインクリメントして上記処理
を更に繰り返す。そして、いずれかのコスト変数におい
て、ノードＪへ至る経路の各ＱｏＳ値が全て基準条件を
満足すると、当該処理はステップＳ５５からステップＳ
５７へ進み、当該経路を最適解と判定する。
至るまでのＱｏＳ値が求められ、ノードＪへ至る経路が
あると、その時の各ＱｏＳ値が基準値と比較される。そ
の結果、たとえ一つのＱｏＳ値でも基準条件を満足して
いなければ、当該処理はステップＳ５５からステップＳ
５８へ戻り、コスト変数をインクリメントして上記処理
を更に繰り返す。そして、いずれかのコスト変数におい
て、ノードＪへ至る経路の各ＱｏＳ値が全て基準条件を
満足すると、当該処理はステップＳ５５からステップＳ
５７へ進み、当該経路を最適解と判定する。
【００３８】なお、図１２に模式的に示したように、始
点Ａと終点Ｊとの間のノードＸ（経由点）へ至る経路と
して、ノードＶを経由する経路１と、ノードＷを経由す
る経路２とが存在する場合、全てのＱｏＳについて一方
の経路が他方の経路より優れていれば、終点Ｊに至る経
路のＱｏＳは、当該一方の経路を経由して終点Ｊに至る
経路のＱｏＳとして求めることになる。
点Ａと終点Ｊとの間のノードＸ（経由点）へ至る経路と
して、ノードＶを経由する経路１と、ノードＷを経由す
る経路２とが存在する場合、全てのＱｏＳについて一方
の経路が他方の経路より優れていれば、終点Ｊに至る経
路のＱｏＳは、当該一方の経路を経由して終点Ｊに至る
経路のＱｏＳとして求めることになる。
【００３９】しかしながら、例えば帯域幅および伝送遅
延に関しては経路１の方が優れているが、誤り率に関し
ては経路２の方が優れているといったように、ＱｏＳに
関して両者の優劣が一義に定まらない場合は、いずれの
経路に基づいて終点Ｊに至る経路のＱｏＳを求めるかが
問題となる。
延に関しては経路１の方が優れているが、誤り率に関し
ては経路２の方が優れているといったように、ＱｏＳに
関して両者の優劣が一義に定まらない場合は、いずれの
経路に基づいて終点Ｊに至る経路のＱｏＳを求めるかが
問題となる。
【００４０】本実施形態では、このような問題点を解決
するために、経由するノードに同一コストで至る経路が
複数存在し、当該ノードに至るまでの各経路におけるＱ
ｏＳの優劣が一義に定まらない場合、前記複数の経路の
うち、最初は任意の一の経路を経由して終点へ至る経路
が全てのＱｏＳ条件を満足するか否かを判定し、複数の
ＱｏＳ条件の一つでも満足していないと、今度は他の一
の経路を経由して終点へ至る経路が全てのＱｏＳ条件を
満足するか否かを判定し、全てのＱｏＳ条件を満足すれ
ば当該経路を最適経路と判定する。
するために、経由するノードに同一コストで至る経路が
複数存在し、当該ノードに至るまでの各経路におけるＱ
ｏＳの優劣が一義に定まらない場合、前記複数の経路の
うち、最初は任意の一の経路を経由して終点へ至る経路
が全てのＱｏＳ条件を満足するか否かを判定し、複数の
ＱｏＳ条件の一つでも満足していないと、今度は他の一
の経路を経由して終点へ至る経路が全てのＱｏＳ条件を
満足するか否かを判定し、全てのＱｏＳ条件を満足すれ
ば当該経路を最適経路と判定する。
【００４１】この結果、終点に至る過程において同一コ
ストでＱｏＳの優劣が一義に定まらない複数の経路が存
在し、その中に終点においてＱｏＳ条件の全ては満足で
きない経路が含まれている場合でも、終点において全て
のＱｏＳ条件を満足できる経路が一つでも含まれていれ
ば、当該経路を選択できるようになる。
ストでＱｏＳの優劣が一義に定まらない複数の経路が存
在し、その中に終点においてＱｏＳ条件の全ては満足で
きない経路が含まれている場合でも、終点において全て
のＱｏＳ条件を満足できる経路が一つでも含まれていれ
ば、当該経路を選択できるようになる。
【００４２】次いで、図４、５のフローチャートを参照
して、本発明の一実施形態である経路選択方法の動作
を、前記図９、１０に関して説明したネットワークを例
にして詳細に説明する。図４は、本発明を適用した経路
選択方法の主要動作を示したフローチャートである。
して、本発明の一実施形態である経路選択方法の動作
を、前記図９、１０に関して説明したネットワークを例
にして詳細に説明する。図４は、本発明を適用した経路
選択方法の主要動作を示したフローチャートである。
【００４３】ステップＳ１１では、満足すべき複数のＱ
ｏＳ条件、および全てのＱｏＳ条件を満足する経路の中
でコストが最小となる未知の最適経路のコストＯＰＴに
対して許容し得る近似誤差εが設定される。この近似誤
差εは、求められた経路のコストがＯＰＴ（１＋ε）以
下となったときに当該経路を実質的な最適経路と認める
ことができる値に予め設定される。
ｏＳ条件、および全てのＱｏＳ条件を満足する経路の中
でコストが最小となる未知の最適経路のコストＯＰＴに
対して許容し得る近似誤差εが設定される。この近似誤
差εは、求められた経路のコストがＯＰＴ（１＋ε）以
下となったときに当該経路を実質的な最適経路と認める
ことができる値に予め設定される。
【００４４】本実施形態では、近似誤差εとして“０．
５”が設定されると共に、複数のＱｏＳ条件として、帯
域幅、伝送遅延および誤り率のＱｏＳに関する条件（基
準値）が設定される。本実施形態では、帯域幅は３以
上、伝送遅延は１６以下、誤り率は０．０５以下に設定
されたものとする。
５”が設定されると共に、複数のＱｏＳ条件として、帯
域幅、伝送遅延および誤り率のＱｏＳに関する条件（基
準値）が設定される。本実施形態では、帯域幅は３以
上、伝送遅延は１６以下、誤り率は０．０５以下に設定
されたものとする。
【００４５】ステップＳ１２では、ＱｏＳの中で凹性を
示す帯域幅について、ＱｏＳ条件［≧３］を満足しない
ＤＪ間のリンク（帯域幅＝２）が経路選択の対象から外
される。ステップＳ１３では、コスト範囲の下限値ＣLB
として、“１”が暫定的に設定される。
示す帯域幅について、ＱｏＳ条件［≧３］を満足しない
ＤＪ間のリンク（帯域幅＝２）が経路選択の対象から外
される。ステップＳ１３では、コスト範囲の下限値ＣLB
として、“１”が暫定的に設定される。
【００４６】ステップＳ１４では、コスト範囲の上限値
ＣUBとして、最大のコストからｎ（ノード数）−１番目
に大きいコストまでの和が設定される。本実施形態では
ノード数が１０（Ａ〜Ｊ）なので、最大コスト２６（Ａ
Ｅ間）から９番目のコストまでの和として７８（２６
［ＡＥ間］＋２０［ＣＤ間］＋２０［ＦＪ間］＋２［Ａ
Ｂ間］＋２［ＡＧ間］＋２［ＢＣ間］＋２［ＣＦ間］＋
２［ＥＦ間］＝７８）が上限値ＣUBとして設定される。
ＣUBとして、最大のコストからｎ（ノード数）−１番目
に大きいコストまでの和が設定される。本実施形態では
ノード数が１０（Ａ〜Ｊ）なので、最大コスト２６（Ａ
Ｅ間）から９番目のコストまでの和として７８（２６
［ＡＥ間］＋２０［ＣＤ間］＋２０［ＦＪ間］＋２［Ａ
Ｂ間］＋２［ＡＧ間］＋２［ＢＣ間］＋２［ＣＦ間］＋
２［ＥＦ間］＝７８）が上限値ＣUBとして設定される。
【００４７】ステップＳ１５では、下限値ＣLBと上限値
ＣUBとに基づいて、検索対象のコスト範囲が十分に減縮
されているか否かが判定され、下限値ＣLBおよび上限値
ＣUBが次式(1) を満足すれば、検索対象のコスト範囲が
十分に減縮されているものと判定されてステップＳ５１
へ進む。 ＣUB≦（１＋ε）・ＣLB (1) ここでは、下限値ＣLBが“１”、上限値ＣUBが“７
８”、近似誤差εが０．５であって上式(1) は成立しな
いので、検索対象のコスト範囲を更に狭めるためにステ
ップＳ１６へ進む。ステップＳ１６では、次式(2) を満
足する変数Ｖが、最適コストの暫定的な予測値として求
められる。
ＣUBとに基づいて、検索対象のコスト範囲が十分に減縮
されているか否かが判定され、下限値ＣLBおよび上限値
ＣUBが次式(1) を満足すれば、検索対象のコスト範囲が
十分に減縮されているものと判定されてステップＳ５１
へ進む。 ＣUB≦（１＋ε）・ＣLB (1) ここでは、下限値ＣLBが“１”、上限値ＣUBが“７
８”、近似誤差εが０．５であって上式(1) は成立しな
いので、検索対象のコスト範囲を更に狭めるためにステ
ップＳ１６へ進む。ステップＳ１６では、次式(2) を満
足する変数Ｖが、最適コストの暫定的な予測値として求
められる。
【００４８】本実施形態では、次式(2) を満足する予測
値Ｖを求めるために、次式で表されれる数列ａi に対し
て、ａk ＞ＣUB／ＣLBを満足する最小のk を求める。
値Ｖを求めるために、次式で表されれる数列ａi に対し
て、ａk ＞ＣUB／ＣLBを満足する最小のk を求める。
【００４９】
【数１】 次いで、Ｖ´＝ａk-2 なるＶ´を求め、Ｖ＝Ｖ´・ＣLB
なる予測値Ｖを求める。本実施形態では、予測値Ｖとし
て“４”が求められる。 （ＣLB3/4 ・ＣUB1/4 ）＜Ｖ≦（ＣLB1/2 ・ＣUB1/2 ） (2) ステップＳ１７では、予測値Ｖ＝４，近似比率ε＝０．
５として、検索対象のコスト範囲を狭めるための最適解
コスト近似手続が実行される。
なる予測値Ｖを求める。本実施形態では、予測値Ｖとし
て“４”が求められる。 （ＣLB3/4 ・ＣUB1/4 ）＜Ｖ≦（ＣLB1/2 ・ＣUB1/2 ） (2) ステップＳ１７では、予測値Ｖ＝４，近似比率ε＝０．
５として、検索対象のコスト範囲を狭めるための最適解
コスト近似手続が実行される。
【００５０】図５は、最適解コスト近似手続の動作を示
したフローチャートである。ステップＳ３１では、リン
クコストが予測値Ｖ以上のリンクとして、ＡＥ間，ＣＤ
間およびＦＪ間の各リンクが経路選択の対象から除外さ
れる。ステップＳ３２では、各ノードＸＹ間のリンクコ
ストＣxyが、次式(3) に基づいて近似値Ｃ１xyに置換さ
れる。これにより、差の小さいリンクコスト同士を同一
のコストにグループ化することができ、各リンクコスト
が取り得る値の種類を少なくできる。 Ｃ１xy＝［（ｎ−１）・Ｃxy／（Ｖ・ε）］ (3) 但し、［…］は、…の小数点切り捨てを意味する。ここ
では、ノード数ｎが“１０、予測値Ｖが“４”、近似誤
差εが“０．５”なので、例えばコスト“２”はコスト
“９”に置換され、コスト“３”はコスト“１３”に置
換される。
したフローチャートである。ステップＳ３１では、リン
クコストが予測値Ｖ以上のリンクとして、ＡＥ間，ＣＤ
間およびＦＪ間の各リンクが経路選択の対象から除外さ
れる。ステップＳ３２では、各ノードＸＹ間のリンクコ
ストＣxyが、次式(3) に基づいて近似値Ｃ１xyに置換さ
れる。これにより、差の小さいリンクコスト同士を同一
のコストにグループ化することができ、各リンクコスト
が取り得る値の種類を少なくできる。 Ｃ１xy＝［（ｎ−１）・Ｃxy／（Ｖ・ε）］ (3) 但し、［…］は、…の小数点切り捨てを意味する。ここ
では、ノード数ｎが“１０、予測値Ｖが“４”、近似誤
差εが“０．５”なので、例えばコスト“２”はコスト
“９”に置換され、コスト“３”はコスト“１３”に置
換される。
【００５１】ステップＳ３３では、最小コスト（＝０）
から順に、始点Ａから各ノードに至るまでの各ＱｏＳ値
をコストごとに求めるために、コスト変数ｃに初期値
“０”が設定される。ステップＳ３４では、次式(4) が
成立するか否かが判定され、成立すれば、図４のステッ
プＳ１８へ進み、検索対象のコスト範囲の下限値ＣLB
が、これまでの“１”から前記予測値Ｖ（＝４）に更新
され、検索対象のコスト範囲が狭められる。成立しなけ
ればステップＳ３５へ進む。 ｃ≧（ｎ−１）／ε (4) 本実施形態では、式(4) の右辺が“１８”となるのでス
テップＳ３５へ進む。ステップＳ３５では、各コストご
とに、始点Ａ（１番目）からｉ番目のノードに至るまで
の全てのＱｏＳを求めるために、ノード変数ｉに初期値
“２”が設定される。
から順に、始点Ａから各ノードに至るまでの各ＱｏＳ値
をコストごとに求めるために、コスト変数ｃに初期値
“０”が設定される。ステップＳ３４では、次式(4) が
成立するか否かが判定され、成立すれば、図４のステッ
プＳ１８へ進み、検索対象のコスト範囲の下限値ＣLB
が、これまでの“１”から前記予測値Ｖ（＝４）に更新
され、検索対象のコスト範囲が狭められる。成立しなけ
ればステップＳ３５へ進む。 ｃ≧（ｎ−１）／ε (4) 本実施形態では、式(4) の右辺が“１８”となるのでス
テップＳ３５へ進む。ステップＳ３５では、各コストご
とに、始点Ａ（１番目）からｉ番目のノードに至るまで
の全てのＱｏＳを求めるために、ノード変数ｉに初期値
“２”が設定される。
【００５２】続くステップＳ３６〜Ｓ３８では、ノード
Ａを始点として、リンクコストの和がｃである各ノード
までの経路に関して、そのＱｏＳが求められる。すなわ
ち、ステップＳ３６では、リンクコストの和がｃ（＝
０）である、始点Ａから各ノードｉへ至る経路のＱｏＳ
がそれぞれ求められる。ステップＳ３７では、ノード変
数ｉがノード数ｎと比較され、ノード変数ｉがノード数
ｎと一致しなければ、ステップＳ３８においてノード変
数ｉを“１”だけインクリメントしてステップＳ３６へ
戻る。
Ａを始点として、リンクコストの和がｃである各ノード
までの経路に関して、そのＱｏＳが求められる。すなわ
ち、ステップＳ３６では、リンクコストの和がｃ（＝
０）である、始点Ａから各ノードｉへ至る経路のＱｏＳ
がそれぞれ求められる。ステップＳ３７では、ノード変
数ｉがノード数ｎと比較され、ノード変数ｉがノード数
ｎと一致しなければ、ステップＳ３８においてノード変
数ｉを“１”だけインクリメントしてステップＳ３６へ
戻る。
【００５３】その後、ステップＳ３７においてノード変
数ｉがノード数ｎに一致する、換言すれば、ノードＡを
始点として、リンクコストの和がｃである終点ノードＪ
までの経路に関してＱｏＳが求められるとステップＳ３
９へ進む。ステップＳ３９では、求められたＱｏＳが全
てのＱｏＳ条件を満足しているか否かが判定され、ここ
では、リンクコストの和が“０”で全てのＱｏＳ条件を
満足するような、始点Ａから終点Ｊへ至る経路は存在し
ないので、ステップＳ４０においてコスト変数ｃを
“１”だけインクリメントした後にステップＳ３４へ戻
る本実施形態では、前記ステップＳ３４〜Ｓ４０の処理
が１７回繰り返されてコスト変数ｃが“１８”になる
と、ステップＳ３９よりも先にステップＳ３４の判定が
真となって図４のステップＳ１８へ進む。
数ｉがノード数ｎに一致する、換言すれば、ノードＡを
始点として、リンクコストの和がｃである終点ノードＪ
までの経路に関してＱｏＳが求められるとステップＳ３
９へ進む。ステップＳ３９では、求められたＱｏＳが全
てのＱｏＳ条件を満足しているか否かが判定され、ここ
では、リンクコストの和が“０”で全てのＱｏＳ条件を
満足するような、始点Ａから終点Ｊへ至る経路は存在し
ないので、ステップＳ４０においてコスト変数ｃを
“１”だけインクリメントした後にステップＳ３４へ戻
る本実施形態では、前記ステップＳ３４〜Ｓ４０の処理
が１７回繰り返されてコスト変数ｃが“１８”になる
と、ステップＳ３９よりも先にステップＳ３４の判定が
真となって図４のステップＳ１８へ進む。
【００５４】再び図４へ戻り、ステップＳ１８では、下
限値ＣLBに予測値Ｖ（＝４）が設定され、その後、ステ
ップＳ１５へ戻る。ステップＳ１５では、前記と同様に
して上限値ＣUBと下限値ＣLBのと間が十分に狭まったか
否かが判定される。本実施形態では、上限値ＣUBが“７
８”、下限値ＣLBが“４”であり、前記式(1) が成立し
ないので、コスト範囲が依然として広過ぎると判定され
てステップＳ１６へ進む。ステップＳ１６では、前記と
同様に式(2) に基づいて予測値Ｖが演算され、今度は
“１６”を得る。
限値ＣLBに予測値Ｖ（＝４）が設定され、その後、ステ
ップＳ１５へ戻る。ステップＳ１５では、前記と同様に
して上限値ＣUBと下限値ＣLBのと間が十分に狭まったか
否かが判定される。本実施形態では、上限値ＣUBが“７
８”、下限値ＣLBが“４”であり、前記式(1) が成立し
ないので、コスト範囲が依然として広過ぎると判定され
てステップＳ１６へ進む。ステップＳ１６では、前記と
同様に式(2) に基づいて予測値Ｖが演算され、今度は
“１６”を得る。
【００５５】ステップＳ１７では、今度は予測値Ｖ＝１
６、近似誤差＝０．５として前記と同様に最適解コスト
近似手続き（図５）が実行され、今回は、ステップＳ３
４よりも前にステップＳ３９の判定が真となって図４の
ステップＳ１９へ進む。再び図４へ戻り、ステップＳ１
９では、次式(5) に従って上限値ＣUBが“２４”に更新
される。 上限値ＣUB＝（１＋ε）Ｖ (5) 続くステップＳ１５では、前記と同様にして上限値ＣUB
と下限値ＣLBとの間が十分に狭まったか否かが判定され
る。本実施形態では、上限値ＣUBが“２４”、下限値Ｃ
LBが“４”であり、前記式(1) は依然として偽であるた
め、再びステップＳ１６以降の処理が繰り返され、上限
値ＣUBが“１２・２1/2 ”、下限値ＣLBが“８・
２1/2 ”となったときに上式(1) が真となるため、検索
対象のコスト範囲が十分に狭まったと判定されてステッ
プＳ５１へ進む。ステップＳ５１では、上限値ＣUB＝１
２・２1/2 ＝１６．９７が最適解のリンクコストの和と
認定される。
６、近似誤差＝０．５として前記と同様に最適解コスト
近似手続き（図５）が実行され、今回は、ステップＳ３
４よりも前にステップＳ３９の判定が真となって図４の
ステップＳ１９へ進む。再び図４へ戻り、ステップＳ１
９では、次式(5) に従って上限値ＣUBが“２４”に更新
される。 上限値ＣUB＝（１＋ε）Ｖ (5) 続くステップＳ１５では、前記と同様にして上限値ＣUB
と下限値ＣLBとの間が十分に狭まったか否かが判定され
る。本実施形態では、上限値ＣUBが“２４”、下限値Ｃ
LBが“４”であり、前記式(1) は依然として偽であるた
め、再びステップＳ１６以降の処理が繰り返され、上限
値ＣUBが“１２・２1/2 ”、下限値ＣLBが“８・
２1/2 ”となったときに上式(1) が真となるため、検索
対象のコスト範囲が十分に狭まったと判定されてステッ
プＳ５１へ進む。ステップＳ５１では、上限値ＣUB＝１
２・２1/2 ＝１６．９７が最適解のリンクコストの和と
認定される。
【００５６】なお、前記図５のステップＳ３２における
数値置換およびステップＳ３４における大小判定結果に
基づいてコスト範囲を狭める手法に関しては、１９９２
年２月発行の『マスマティクス オブ オペレーション
ズ リサーチ』のＶｏｌ１７，Ｎo.１ (MATHEMATICS OF
OPERATIONS RESEARCH Vol17, No.1, February 1992)
』において、「APPROXIMATION SCHEMES FOR THE RESTR
ICTED SHORTEST PATH PROBLEM」と題して詳細に論じら
れており、ここではこの論文の内容を援用する。
数値置換およびステップＳ３４における大小判定結果に
基づいてコスト範囲を狭める手法に関しては、１９９２
年２月発行の『マスマティクス オブ オペレーション
ズ リサーチ』のＶｏｌ１７，Ｎo.１ (MATHEMATICS OF
OPERATIONS RESEARCH Vol17, No.1, February 1992)
』において、「APPROXIMATION SCHEMES FOR THE RESTR
ICTED SHORTEST PATH PROBLEM」と題して詳細に論じら
れており、ここではこの論文の内容を援用する。
【００５７】図６は、本発明の第２実施形態である経路
選択方法の主要動作を示したフローチャートであり、前
記と同一の符号を付したステップでは同一または同等の
処理が実行されるので、その説明は省略する。
選択方法の主要動作を示したフローチャートであり、前
記と同一の符号を付したステップでは同一または同等の
処理が実行されるので、その説明は省略する。
【００５８】本実施形態では、ステップＳ１５の判定が
真となってコスト範囲が十分に狭くなると、ステップＳ
６１では、リンクコストの和が下限値ＣLBを下回る経
路、および上限値ＣUBを上回る経路が検索対象から除か
れる。ステップＳ６２では、残りの経路の全てを対象に
して最適経路が求められる。
真となってコスト範囲が十分に狭くなると、ステップＳ
６１では、リンクコストの和が下限値ＣLBを下回る経
路、および上限値ＣUBを上回る経路が検索対象から除か
れる。ステップＳ６２では、残りの経路の全てを対象に
して最適経路が求められる。
【００５９】図７は、本発明の第３実施形態である経路
選択方法の主要動作を示したフローチャートであり、前
記と同一の符号を付したステップでは同一または同等の
処理が実行されるので、その説明は省略する。
選択方法の主要動作を示したフローチャートであり、前
記と同一の符号を付したステップでは同一または同等の
処理が実行されるので、その説明は省略する。
【００６０】本実施形態では、ステップＳ１５の判定が
真となってコスト範囲が十分に狭くなると、ステップＳ
７１では、前記図３、１１に関して説明した最適解求解
手続が、前記狭められたコスト範囲を対象に実行され
る。すなわち、下限値ＣLBを出発点として全ての経路を
対象にして最適経路が求められる。
真となってコスト範囲が十分に狭くなると、ステップＳ
７１では、前記図３、１１に関して説明した最適解求解
手続が、前記狭められたコスト範囲を対象に実行され
る。すなわち、下限値ＣLBを出発点として全ての経路を
対象にして最適経路が求められる。
【００６１】
【発明の効果】本発明によれば、以下のような効果が達
成される。 (1) 予めコスト範囲を絞り込み、狭められた範囲に対し
てのみ、各コストごとに始点から終点へ到る経路の有無
が判定されるので、最適解を導き出すまでに要する時間
が短縮される。 (2) 予め指定した近似誤差を満足する最適解を導き出せ
るようになる。 (3) 始点から各ノードへ同一コストで至る経路が複数存
在する場合、一の経路を経由して終点に至ったときに満
足できないＱｏＳ条件があると、他の一の経路を経由し
た場合を求め、当該他の一の経路を経由したときに全て
のＱｏＳ条件が満足されれば当該経路を最適解とするの
で、終点に至ることのできる経路が一つでもあれば、当
該経路を選択できるようになる。
成される。 (1) 予めコスト範囲を絞り込み、狭められた範囲に対し
てのみ、各コストごとに始点から終点へ到る経路の有無
が判定されるので、最適解を導き出すまでに要する時間
が短縮される。 (2) 予め指定した近似誤差を満足する最適解を導き出せ
るようになる。 (3) 始点から各ノードへ同一コストで至る経路が複数存
在する場合、一の経路を経由して終点に至ったときに満
足できないＱｏＳ条件があると、他の一の経路を経由し
た場合を求め、当該他の一の経路を経由したときに全て
のＱｏＳ条件が満足されれば当該経路を最適解とするの
で、終点に至ることのできる経路が一つでもあれば、当
該経路を選択できるようになる。
【図１】 本発明の経路選択方法の概略フローチャート
である。
である。
【図２】 本発明の基本概念を模式的に表現した図であ
る。
る。
【図３】 最適解求解手続を説明するための図である。
【図４】 本発明の第１実施形態のフローチャートであ
る。
る。
【図５】 最適解コスト近似手続のフローチャートであ
る。
る。
【図６】 本発明の第２実施形態のフローチャートであ
る。
る。
【図７】 本発明の第３実施形態のフローチャートであ
る。
る。
【図８】 従来技術のフローチャートである。
【図９】 ネットワークの構成例を示した図である。
【図１０】 各リンクの特性を一覧表示した図である。
【図１１】 最適解求解手続のフローチャートである。
【図１２】 経路選択における問題点を説明するための
図である。
図である。
Ａ〜Ｊ…ノード
───────────────────────────────────────────────────── フロントページの続き (72)発明者 小花 貞夫 東京都新宿区西新宿２丁目３番２号 国際 電信電話株式会社内
Claims (6)
- 【請求項１】 少なくとも一つのノードを経由して始点
と終点とを結ぶ複数の経路の中から、複数のＱｏＳ条件
を低コストで満足する経路を選択する経路選択方法にお
いて、 複数のＱｏＳに関して満足すべき条件をそれぞれ設定
し、 全てのＱｏＳ条件を満足する経路の中でコストが最小と
なる未知の最適経路のコストに対して許容し得る誤差範
囲を入力し、 少なくとも前記最適経路のコストを含むコスト範囲を暫
定的に設定し、 前記コスト範囲が、前記誤差範囲の関数である基準範囲
まで減縮されているか否かを判定し、 減縮されていないと判定されると、現在のコスト範囲内
で最低コストから順に、当該コストで始点から各ノード
へ至るまでの複数のＱｏＳを、既にＱｏＳが求められた
ノードの各ＱｏＳに基づいて求め、 前記複数のＱｏＳ条件を全て満足して始点から終点へ至
る経路が、前記誤差範囲の関数として与えられる基準コ
ストまでに見つかるか否かに基づいて前記コスト範囲を
減縮し、 前記基準範囲まで減縮されたコスト範囲から最適経路を
検索することを特徴とする経路選択方法。 - 【請求項２】 前記基準範囲まで減縮されたコスト範囲
から最適経路を検索する際、前記コスト範囲に含まれる
経路を実質的な最適経路と判定することを特徴とする請
求項１に記載の経路選択方法。 - 【請求項３】 前記基準範囲まで減縮されたコスト範囲
から最適経路を検索する際、前記コスト範囲内で最低コ
ストから順に、当該コストで始点から各ノードへ至るま
での複数のＱｏＳを、既にＱｏＳが求められたノードの
各ＱｏＳに基づいて求め、 前記複数のＱｏＳ条件を全て満足して始点から終点へ至
る最初の経路を実質的な最適経路と判定することを特徴
とする請求項１に記載の経路選択方法。 - 【請求項４】 前記基準範囲まで減縮されたコスト範囲
から最適経路を検索する際、始点から終点へ至るコスト
が前記コスト範囲外となる経路を予め検索対象から外
し、残りの経路のみを対象に最適経路を検索することを
特徴とする請求項１に記載の経路選択方法。 - 【請求項５】 経由するノードに同一コストで至る経路
が複数存在し、当該経由するノードに至るまでの各経路
におけるＱｏＳの優劣が一義に定まらない場合、前記複
数の経路のうち、一の経路を経由して終点へ至る経路が
複数のＱｏＳ条件の一つでも満足していないと、他の一
の経路を経由して終点へ至る経路が全てのＱｏＳ条件を
満足するか否かを順次判定し、いずれかの経路が全ての
ＱｏＳ条件を満足すれば、当該経路を選択することを特
徴とする請求項４に記載の経路選択方法。 - 【請求項６】 前記複数のＱｏＳは、経路のＱｏＳ値
が、各リンクのＱｏＳ値の和として与えられる加法性の
ＱｏＳ、各リンクのＱｏＳ値の積として与えられる乗法
性のＱｏＳおよび各リンクのＱｏＳ値の最小値として与
えられる凹性のＱｏＳの少なくとも一つを含むことを特
徴とする請求項１ないし５のいずれかに記載の経路選択
方法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23045097A JP3662097B2 (ja) | 1997-08-12 | 1997-08-12 | 経路選択方法 |
| US09/128,520 US6259673B1 (en) | 1997-08-12 | 1998-08-03 | Route selection method |
| DE69828664T DE69828664T2 (de) | 1997-08-12 | 1998-08-11 | Verfahren zur Lenkweg-Auswahl |
| EP98115083A EP0897253B1 (en) | 1997-08-12 | 1998-08-11 | Route selection method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23045097A JP3662097B2 (ja) | 1997-08-12 | 1997-08-12 | 経路選択方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1168838A true JPH1168838A (ja) | 1999-03-09 |
| JP3662097B2 JP3662097B2 (ja) | 2005-06-22 |
Family
ID=16908076
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23045097A Expired - Fee Related JP3662097B2 (ja) | 1997-08-12 | 1997-08-12 | 経路選択方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6259673B1 (ja) |
| EP (1) | EP0897253B1 (ja) |
| JP (1) | JP3662097B2 (ja) |
| DE (1) | DE69828664T2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007325032A (ja) * | 2006-06-01 | 2007-12-13 | Nippon Telegr & Teleph Corp <Ntt> | 要求解釈方法、および、要求解釈装置 |
| JP2011176445A (ja) * | 2010-02-23 | 2011-09-08 | Fujitsu Ltd | 経路決定装置，経路決定方法及び経路決定プログラム |
| JP2015180014A (ja) * | 2014-03-19 | 2015-10-08 | 富士通株式会社 | 経路選択方法、ノード装置、及び、プログラム |
Families Citing this family (28)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3665460B2 (ja) * | 1997-12-05 | 2005-06-29 | 富士通株式会社 | 分散自律協調型の応答時間チューニングによる経路選択システム、方法、及び記録媒体 |
| WO2000038402A1 (en) * | 1998-12-23 | 2000-06-29 | Enikia Llc | Power line communication system for local area networks |
| US7352692B1 (en) | 1999-01-15 | 2008-04-01 | Cisco Technology, Inc. | Resource reservation scheme for path restoration in an optical network |
| US6631134B1 (en) * | 1999-01-15 | 2003-10-07 | Cisco Technology, Inc. | Method for allocating bandwidth in an optical network |
| US7764596B2 (en) | 2001-05-16 | 2010-07-27 | Cisco Technology, Inc. | Method for restoring a virtual path in an optical network using dynamic unicast |
| US6856627B2 (en) | 1999-01-15 | 2005-02-15 | Cisco Technology, Inc. | Method for routing information over a network |
| US6912221B1 (en) * | 1999-01-15 | 2005-06-28 | Cisco Technology, Inc. | Method of providing network services |
| US7428212B2 (en) * | 1999-01-15 | 2008-09-23 | Cisco Technology, Inc. | Best effort technique for virtual path restoration |
| US6990068B1 (en) | 1999-01-15 | 2006-01-24 | Cisco Technology, Inc. | Virtual path restoration scheme using fast dynamic mesh restoration in an optical network |
| US6801496B1 (en) | 1999-01-15 | 2004-10-05 | Cisco Technology, Inc. | Network addressing scheme for reducing protocol overhead in an optical network |
| US6813272B1 (en) * | 1999-06-23 | 2004-11-02 | Korea Telecommunication Authority | QoS-based routing method |
| US6826182B1 (en) * | 1999-12-10 | 2004-11-30 | Nortel Networks Limited | And-or multi-cast message routing method for high performance fault-tolerant message replication |
| US6766373B1 (en) * | 2000-05-31 | 2004-07-20 | International Business Machines Corporation | Dynamic, seamless switching of a network session from one connection route to another |
| US20020021466A1 (en) * | 2000-06-29 | 2002-02-21 | Peter Abrams | Shortest path first restoration routing in a fiberoptic network |
| JP3987302B2 (ja) * | 2001-04-26 | 2007-10-10 | 富士通株式会社 | 経路探索方法、タイミング解析方法、波形解析方法、電子回路シミュレーション装置、及びプログラム |
| US7477594B2 (en) * | 2001-05-16 | 2009-01-13 | Cisco Technology, Inc. | Method for restoring a virtual path in an optical network using 1:N protection |
| JP3823837B2 (ja) * | 2002-01-31 | 2006-09-20 | 日本電気株式会社 | 光通信ネットワーク及びそれに用いる光通信ネットワーク設計方法 |
| US7020087B2 (en) * | 2003-01-13 | 2006-03-28 | Motorola, Inc. | Segmented and distributed path optimization in a communication network |
| EP1458148A1 (en) * | 2003-03-10 | 2004-09-15 | Sony International (Europe) GmbH | Quality of Service (QoS) -aware handover procedure for Ad-Hoc networks |
| US7706282B2 (en) * | 2003-06-25 | 2010-04-27 | Leping Huang | Bluetooth personal area network routing protocol optimization using connectivity metric |
| US7965626B2 (en) * | 2004-08-03 | 2011-06-21 | Hewlett-Packard Development Company, L.P. | System and method for transferring data on a data network using multiple paths |
| JP2006060579A (ja) * | 2004-08-20 | 2006-03-02 | Fujitsu Ltd | アプリケーション特性に応じて複数の経路を同時に利用する通信装置 |
| JP4421978B2 (ja) * | 2004-09-03 | 2010-02-24 | 富士通株式会社 | 遅延保証パス設定システム |
| US7489635B2 (en) * | 2004-09-24 | 2009-02-10 | Lockheed Martin Corporation | Routing cost based network congestion control for quality of service |
| US7701857B2 (en) * | 2006-06-07 | 2010-04-20 | Genband Inc. | Method, system, and computer-readable medium for resource-based route selection |
| US8014291B2 (en) | 2006-11-28 | 2011-09-06 | Cisco Technology, Inc. | Relaxed constrained shortest path first (R-CSPF) |
| US8982887B2 (en) * | 2007-05-18 | 2015-03-17 | International Business Machines Corporation | System, method and program for making routing decisions |
| EP2608465A1 (en) * | 2011-12-15 | 2013-06-26 | Alcatel Lucent | Path computation entity and method for computing a path |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5072379A (en) * | 1989-05-26 | 1991-12-10 | The United States Of America As Represented By The Adminstrator Of The National Aeronautics And Space Administration | Network of dedicated processors for finding lowest-cost map path |
| US5508999A (en) * | 1990-05-08 | 1996-04-16 | U S West Advanced Technologies, Inc. | Method and system for designing least cost local access networks |
| JP3033203B2 (ja) * | 1991-01-25 | 2000-04-17 | 株式会社日立製作所 | 配線経路探索装置及び配線経路探索方法 |
| US5317566A (en) * | 1993-08-18 | 1994-05-31 | Ascom Timeplex Trading Ag | Least cost route selection in distributed digital communication networks |
| US5832069A (en) * | 1995-11-17 | 1998-11-03 | Sprint Communications Co L.P. | Object oriented system for modeling telecommunications circuits to estimate the access cost for leasing selected circuits |
| JP2723097B2 (ja) * | 1995-12-04 | 1998-03-09 | 日本電気株式会社 | Ｑｏｓルーティング装置 |
| JP3173983B2 (ja) * | 1995-12-28 | 2001-06-04 | 松下電器産業株式会社 | 経路選出方法およびシステム |
| KR100194608B1 (ko) * | 1996-11-20 | 1999-06-15 | 이계철 | Atm 통신망에서의 멀티캐스트 경로 할당방법 |
| US6104701A (en) * | 1996-12-13 | 2000-08-15 | International Business Machines Corporation | Method and system for performing a least cost routing function for data communications between end users in a multi-network environment |
-
1997
- 1997-08-12 JP JP23045097A patent/JP3662097B2/ja not_active Expired - Fee Related
-
1998
- 1998-08-03 US US09/128,520 patent/US6259673B1/en not_active Expired - Fee Related
- 1998-08-11 DE DE69828664T patent/DE69828664T2/de not_active Expired - Fee Related
- 1998-08-11 EP EP98115083A patent/EP0897253B1/en not_active Expired - Lifetime
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007325032A (ja) * | 2006-06-01 | 2007-12-13 | Nippon Telegr & Teleph Corp <Ntt> | 要求解釈方法、および、要求解釈装置 |
| JP4681507B2 (ja) * | 2006-06-01 | 2011-05-11 | 日本電信電話株式会社 | 要求解釈方法、および、要求解釈装置 |
| JP2011176445A (ja) * | 2010-02-23 | 2011-09-08 | Fujitsu Ltd | 経路決定装置，経路決定方法及び経路決定プログラム |
| JP2015180014A (ja) * | 2014-03-19 | 2015-10-08 | 富士通株式会社 | 経路選択方法、ノード装置、及び、プログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0897253A2 (en) | 1999-02-17 |
| EP0897253A3 (en) | 2002-12-18 |
| EP0897253B1 (en) | 2005-01-19 |
| US6259673B1 (en) | 2001-07-10 |
| DE69828664D1 (de) | 2005-02-24 |
| JP3662097B2 (ja) | 2005-06-22 |
| DE69828664T2 (de) | 2006-01-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH1168838A (ja) | 経路選択方法 | |
| US6377551B1 (en) | QoS based route determination method for communications networks | |
| US7072304B2 (en) | Network path selection based on bandwidth | |
| US5600638A (en) | Method and system for improving the processing time of the path selection in a high speed packet switching network | |
| US5502816A (en) | Method of routing a request for a virtual circuit based on information from concurrent requests | |
| EP0568477A2 (en) | Method and apparatus for optinum path selection in packet transmission networks | |
| CN110891093A (zh) | 一种时延敏感网络中边缘计算节点选择方法及系统 | |
| KR20000035663A (ko) | 패킷기반의 통신네트워크 설계 방법 및 장치와 제조품 | |
| KR20000035662A (ko) | 패킷기반의 통신네트워크 설계 방법 및 장치와 제조품 | |
| JPH1070571A (ja) | 最適パス決定方法 | |
| EP0897232B1 (en) | Traffic management in packet communication networks having service priorities and employing effective bandwidths | |
| Shvedov et al. | Determining shortest paths between two arbitrary nodes in a composite transport network using segment routing | |
| US9674081B1 (en) | Efficient mapping of table pipelines for software-defined networking (SDN) data plane | |
| EP4187814A1 (en) | Data processing method and device | |
| KR101754618B1 (ko) | 소프트웨어 정의 네트워크 기반의 가상 네트워크 동적 생성 방법 및 그 장치 | |
| CN105721316B (zh) | 一种下发流表的方法及装置 | |
| CN114024907A (zh) | 一种多口字环形结构下的流量调度方法和系统 | |
| US6377544B1 (en) | System and method for increasing the speed of distributed single and multi-commodity flow using second order methods | |
| US11750955B2 (en) | Routing method for dynamic WDM optical networks with wavelength continuity constraints | |
| EP4152726B1 (en) | Method for optimizing a routing in a communications network | |
| US11368769B2 (en) | Method for dimensioning a WDM optical network with wavelength continuity constraint | |
| JP4436307B2 (ja) | ＬＳＰ（ＬａｂｅｌＳｗｉｔｃｈｅｄＰａｔｈ）経路計算方法及び装置及びプログラム | |
| US20120063362A1 (en) | Method and apparatus for computing paths to destinations in networks having link constraints | |
| Józsa et al. | Reroute sequence planning for label switched paths in multiprotocol label switching networks | |
| CN117978719B (zh) | 一种保障服务质量的最小费用差异路由方法及装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20041006 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20041013 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20041213 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050112 |
|
| 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: 20050316 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050322 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |