JP3045547B2 - データパケット交換ネットワークにおける局のアクセス速度制御システム及び方法 - Google Patents
データパケット交換ネットワークにおける局のアクセス速度制御システム及び方法Info
- Publication number
- JP3045547B2 JP3045547B2 JP41800090A JP41800090A JP3045547B2 JP 3045547 B2 JP3045547 B2 JP 3045547B2 JP 41800090 A JP41800090 A JP 41800090A JP 41800090 A JP41800090 A JP 41800090A JP 3045547 B2 JP3045547 B2 JP 3045547B2
- Authority
- JP
- Japan
- Prior art keywords
- station
- packets
- flow
- access speed
- parameter
- 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 - Lifetime
Links
- 238000000034 method Methods 0.000 title claims description 13
- 230000005540 biological transmission Effects 0.000 claims description 17
- 238000013459 approach Methods 0.000 claims description 4
- 238000004891 communication Methods 0.000 claims description 4
- 238000004364 calculation method Methods 0.000 claims description 3
- 230000007423 decrease Effects 0.000 claims description 3
- 238000012545 processing Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 5
- 101100172132 Mus musculus Eif3a gene Proteins 0.000 description 3
- 239000011159 matrix material Substances 0.000 description 3
- 230000009977 dual effect Effects 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000001747 exhibiting effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000012552 review Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L12/5602—Bandwidth control in ATM Networks, e.g. leaky bucket
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/11—Identifying congestion
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/13—Flow control; Congestion control in a LAN segment, e.g. ring or bus
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/26—Flow control; Congestion control using explicit feedback to the source, e.g. choke packets
- H04L47/263—Rate modification at the source after receiving feedback
-
- 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
- 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/5629—Admission control
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Small-Scale Networks (AREA)
- Mobile Radio Communication Systems (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、経路指定計画に従って
或る局から他の局へとデータパケットを転送することの
できる無線通信チャネルによって相互接続される多数の
送／受信局を具えているデータパケット交換ネットワー
クにおける局のアクセス速度を制御するシステム及び方
法に関するものである。
或る局から他の局へとデータパケットを転送することの
できる無線通信チャネルによって相互接続される多数の
送／受信局を具えているデータパケット交換ネットワー
クにおける局のアクセス速度を制御するシステム及び方
法に関するものである。
【０００２】
【従来の技術】チャネルアクセス制御プロトコルの目的
は、いくつかの制御変数を最適に調整することによって
無線チャネルの処理能力を最大にすることにある。純粋
且つスロット化したアロハ（ＡＬＯＨＡ）ネットワーク
では、制御変数が、各局がデータパケットを伝送する速
度を決定し、又ＣＳＭＡネットワークでは、制御変数
が、各局がチャネルを読み取る速度を決定する。なお、
局のアクセス速度は、局が（ＡＬＯＨＡネットワーク
で）データパケットを伝送したり、又は（ＣＳＭＡネッ
トワークで）チャネルを読み取る速度にはあまり当ては
まらない。単一のホップ・トポロジには概念的に１つの
単一チャネルがあり、チャネルの処理能力と制御変数と
の間には相対的に良く知られている関係がある。これら
の関係は制御変数を調整するのに明白な目標とする。マ
ルチホップ・トポロジには概念上局数と同数の独立チャ
ネルがあり、全体的な処理能力には正確な関係は存在し
ない。
は、いくつかの制御変数を最適に調整することによって
無線チャネルの処理能力を最大にすることにある。純粋
且つスロット化したアロハ（ＡＬＯＨＡ）ネットワーク
では、制御変数が、各局がデータパケットを伝送する速
度を決定し、又ＣＳＭＡネットワークでは、制御変数
が、各局がチャネルを読み取る速度を決定する。なお、
局のアクセス速度は、局が（ＡＬＯＨＡネットワーク
で）データパケットを伝送したり、又は（ＣＳＭＡネッ
トワークで）チャネルを読み取る速度にはあまり当ては
まらない。単一のホップ・トポロジには概念的に１つの
単一チャネルがあり、チャネルの処理能力と制御変数と
の間には相対的に良く知られている関係がある。これら
の関係は制御変数を調整するのに明白な目標とする。マ
ルチホップ・トポロジには概念上局数と同数の独立チャ
ネルがあり、全体的な処理能力には正確な関係は存在し
ない。
【０００３】
【発明が解決しようとする課題】本発明の目的は、パケ
ット交換ネットワークにおける最小出力比を有している
局の出力比が、この最小出力比を有している局が直接及
ぶ範囲の局の負荷を最適に調整することにより、又前記
局の負荷をその負荷に係わる局に最適に振りわけること
によって高められるようにパケット交換ネットワークに
おける局のアクセス速度を制御する方法を提供すること
にある。
ット交換ネットワークにおける最小出力比を有している
局の出力比が、この最小出力比を有している局が直接及
ぶ範囲の局の負荷を最適に調整することにより、又前記
局の負荷をその負荷に係わる局に最適に振りわけること
によって高められるようにパケット交換ネットワークに
おける局のアクセス速度を制御する方法を提供すること
にある。
【０００４】
【課題を解決するための手段】本発明は、経路指定計画
に従って或る局から他の局へとデータパケットを転送す
ることのできる無線通信チャネルによって相互接続され
る多数の送／受信局を具えているデータパケット交換ネ
ットワークにおける局のアクセス速度を制御するシステ
ムであって、各局が： −データパケットを受信し、且つ伝送する手段と； −単位時間当りに首尾良く伝送されたパケット数である
当該局の出力フローを示す第１パラメータを計算する第
１計算手段と； −当該局が中継し得る隣接局の出力フローに基づく分量
でこれら隣接局の出力フローが減少すると増える当該局
の入力フロー増加傾向を示す第２パラメータを計算する
第２計算手段と； −当該局の負荷を示す第３パラメータを計算する第３計
算手段と； −前記第１，第２及び第３パラメータを当該局の及ぶ受
信範囲の全隣接局に伝送する伝送手段と； −当該局のアクセス速度を変更するアクセス速度変更手
段と； −比較手段；とを具え、ネットワークの作動中に各局で
は前記第１パラメータを前記第１計算手段により計算し
て、この第１パラメータを前記伝送手段により各局が及
ぶ受信範囲における全ての隣接局に規則的な時間間隔で
伝送し、その後各局では前記第２及び第３パラメータを
前記第２及び第３計算手段により計算し、各局の伝送手
段がその隣接局に前記第２及び第３パラメータを伝送
し、これら隣接局における前記比較手段は、前記第２及
び第３パラメータの受信後に、それらの隣接局のどの局
が最も大きな入力フローの増加傾向を有しているかを決
定し、且つ第３パラメータに基づいて前記アクセス速度
変更手段が前記隣接局のアクセス速度を更新して、最も
大きな入力フローの増加傾向を有している局の負荷を公
称チャネル負荷に近付け得るように前記システムを機能
させることを特徴とするデータパケット交換ネットワー
クにおける局のアクセス速度制御システムにある。
に従って或る局から他の局へとデータパケットを転送す
ることのできる無線通信チャネルによって相互接続され
る多数の送／受信局を具えているデータパケット交換ネ
ットワークにおける局のアクセス速度を制御するシステ
ムであって、各局が： −データパケットを受信し、且つ伝送する手段と； −単位時間当りに首尾良く伝送されたパケット数である
当該局の出力フローを示す第１パラメータを計算する第
１計算手段と； −当該局が中継し得る隣接局の出力フローに基づく分量
でこれら隣接局の出力フローが減少すると増える当該局
の入力フロー増加傾向を示す第２パラメータを計算する
第２計算手段と； −当該局の負荷を示す第３パラメータを計算する第３計
算手段と； −前記第１，第２及び第３パラメータを当該局の及ぶ受
信範囲の全隣接局に伝送する伝送手段と； −当該局のアクセス速度を変更するアクセス速度変更手
段と； −比較手段；とを具え、ネットワークの作動中に各局で
は前記第１パラメータを前記第１計算手段により計算し
て、この第１パラメータを前記伝送手段により各局が及
ぶ受信範囲における全ての隣接局に規則的な時間間隔で
伝送し、その後各局では前記第２及び第３パラメータを
前記第２及び第３計算手段により計算し、各局の伝送手
段がその隣接局に前記第２及び第３パラメータを伝送
し、これら隣接局における前記比較手段は、前記第２及
び第３パラメータの受信後に、それらの隣接局のどの局
が最も大きな入力フローの増加傾向を有しているかを決
定し、且つ第３パラメータに基づいて前記アクセス速度
変更手段が前記隣接局のアクセス速度を更新して、最も
大きな入力フローの増加傾向を有している局の負荷を公
称チャネル負荷に近付け得るように前記システムを機能
させることを特徴とするデータパケット交換ネットワー
クにおける局のアクセス速度制御システムにある。
【０００５】本発明の好適例では、前記第１パラメータ
は、正しく送られたパケットのフローと、送らなければ
ならないパケットのフローとの比である出力比とする。
この出力比は第１計算手段により次のような比として計
算するのが好適である。即ち、予定した期間中首尾良く
送られて承認されたパケット数と、このパケット数と前
記期間の終了時にまだ待ち状態にあるパケット数との和
との比として計算するのが好適である。
は、正しく送られたパケットのフローと、送らなければ
ならないパケットのフローとの比である出力比とする。
この出力比は第１計算手段により次のような比として計
算するのが好適である。即ち、予定した期間中首尾良く
送られて承認されたパケット数と、このパケット数と前
記期間の終了時にまだ待ち状態にあるパケット数との和
との比として計算するのが好適である。
【０００６】以下図面を参照して本発明を説明する。
【０００７】マルチホップネットワーク用のチャネルア
クセス制御プロトコルについて論じる前に、先ず単一ホ
ップネットワークにおける斯種のプロトコルの機能につ
いて再考する。
クセス制御プロトコルについて論じる前に、先ず単一ホ
ップネットワークにおける斯種のプロトコルの機能につ
いて再考する。
【０００８】単一ホップネットワークにおけるチャネル
負荷Ｇは種々の局のアクセス速度g (K) の和によって決
定される。チャネルの処理能力を最大とするためにチャ
ネル負荷Ｇを制御する必要がある。チャネル負荷が大き
過ぎると衝突回数が多くなり過ぎ、又チャネル負荷が小
さ過ぎるとアイドル期間が長くなり過ぎる。従ってチャ
ネル負荷として最適なチャネル負荷 Gnom がある。この
最適チャネル負荷は、局のアクセス速度g(K)を調整した
り、又はこれらのアクセス速度g(K)を直接制御する幾つ
かの変数を調整したりすることによって維持する必要が
ある。このことがアクセス制御プロトコルの目的であ
る。
負荷Ｇは種々の局のアクセス速度g (K) の和によって決
定される。チャネルの処理能力を最大とするためにチャ
ネル負荷Ｇを制御する必要がある。チャネル負荷が大き
過ぎると衝突回数が多くなり過ぎ、又チャネル負荷が小
さ過ぎるとアイドル期間が長くなり過ぎる。従ってチャ
ネル負荷として最適なチャネル負荷 Gnom がある。この
最適チャネル負荷は、局のアクセス速度g(K)を調整した
り、又はこれらのアクセス速度g(K)を直接制御する幾つ
かの変数を調整したりすることによって維持する必要が
ある。このことがアクセス制御プロトコルの目的であ
る。
【０００９】斯様なプロトコルの第１カテゴリは次のよ
うに実行し得る。各局Ｋはチャネルを聴取することによ
って、そのチャネルの状態についての情報を収集し、そ
れに応じて局固有のアクセス速度g(K)を調整する。例え
ば最適チャネル負荷には最適な割合の衝突パケットが対
応する。現行の衝突パケットの割合を測定すると共に、
それを最適な割合と比較することによって、各局はその
局固有のアクセス速度を変更して、その速度を最適値に
調整することができる。ＣＳＭＡネットワークでは、同
じ戦略をアイドル期間に対する最適平均長さに基づいて
実行させることができる。このタイプの戦略とは、各局
がチャネルの状態を聴取することに過ぎない。
うに実行し得る。各局Ｋはチャネルを聴取することによ
って、そのチャネルの状態についての情報を収集し、そ
れに応じて局固有のアクセス速度g(K)を調整する。例え
ば最適チャネル負荷には最適な割合の衝突パケットが対
応する。現行の衝突パケットの割合を測定すると共に、
それを最適な割合と比較することによって、各局はその
局固有のアクセス速度を変更して、その速度を最適値に
調整することができる。ＣＳＭＡネットワークでは、同
じ戦略をアイドル期間に対する最適平均長さに基づいて
実行させることができる。このタイプの戦略とは、各局
がチャネルの状態を聴取することに過ぎない。
【００１０】プロトコルの他のカテゴリは局間の情報交
換に基づくものであり、従ってこのようなプロトコルは
これらの情報交換のための予約チャネル容量を必要とす
る。例えば、各局はその状態（伝送休止状態又は待ち状
態）を伝送して、パケットを伝送する局の数ｍを知るこ
とができる。この場合、各局はその局固有のアクセス速
度を Gnom ／m に調整することができる。それぞれの局
は、それらが情報を伝送するのにどれだけのチャネル容
量を必要とするかを（入札することにより）知らせるこ
ともでき、次いでこれらのニーズに従って総チャネル容
量を共有することができる。第１カテゴリに比べ、この
ような情報交換はチャネル負荷の調整を改善するだけで
なく、要求に応じてチャネル容量を共有させることもで
きる。しかし、このような利点は多少不十分であり、そ
の実行に用いられるチャネル容量を正当化することには
ならない。それでも斯様な情報交換が極めて有効となり
得る場合（マルチホップ・ホトポロジ）がある。
換に基づくものであり、従ってこのようなプロトコルは
これらの情報交換のための予約チャネル容量を必要とす
る。例えば、各局はその状態（伝送休止状態又は待ち状
態）を伝送して、パケットを伝送する局の数ｍを知るこ
とができる。この場合、各局はその局固有のアクセス速
度を Gnom ／m に調整することができる。それぞれの局
は、それらが情報を伝送するのにどれだけのチャネル容
量を必要とするかを（入札することにより）知らせるこ
ともでき、次いでこれらのニーズに従って総チャネル容
量を共有することができる。第１カテゴリに比べ、この
ような情報交換はチャネル負荷の調整を改善するだけで
なく、要求に応じてチャネル容量を共有させることもで
きる。しかし、このような利点は多少不十分であり、そ
の実行に用いられるチャネル容量を正当化することには
ならない。それでも斯様な情報交換が極めて有効となり
得る場合（マルチホップ・ホトポロジ）がある。
【００１１】マルチホップ・ホトポロジでは、全ての局
ではないにしても、お互いの受信範囲内にあたかも幾つ
かの異なるチャネルがあるような場合がある。多数の局
Ｉ，Ｇ，Ｋ及びＬを示している図１の状態を考えるに、
この図で図面上接続されている２つの局はお互いの受信
範囲内にある。この状態では局ＩとＬがパケットを同時
に伝送することができる。これら２つのパケットは、こ
れらパケットの伝送中局Ｊ及びＫがパケットを伝送して
いなければ局Ｊ及びＫによって正確に受信される。これ
によりチャネルが幾つかあることがわかる。単一ホップ
・トポロジにおけるチャネルアクセス制御の目的はチャ
ネルの処理能力を最大とすることであった。マルチホッ
プ・トポロジでは、その目的はかなりあいまいなものと
なる。例えば、局Ｊがパケットを伝送すると、このパケ
ットは局Ｉによって正確に受信されるが、このパケット
は局Ｋでは（局Ｌによって送られたパケットと）衝突す
ることになる。「このパケット伝送が有害となるか、否
かとして考慮する必要があるか？」と云うことは、答え
なければならない一種の質問事項である。アクセス速度
を制御する基準とする種々の目標機能につき下記に説明
する。
ではないにしても、お互いの受信範囲内にあたかも幾つ
かの異なるチャネルがあるような場合がある。多数の局
Ｉ，Ｇ，Ｋ及びＬを示している図１の状態を考えるに、
この図で図面上接続されている２つの局はお互いの受信
範囲内にある。この状態では局ＩとＬがパケットを同時
に伝送することができる。これら２つのパケットは、こ
れらパケットの伝送中局Ｊ及びＫがパケットを伝送して
いなければ局Ｊ及びＫによって正確に受信される。これ
によりチャネルが幾つかあることがわかる。単一ホップ
・トポロジにおけるチャネルアクセス制御の目的はチャ
ネルの処理能力を最大とすることであった。マルチホッ
プ・トポロジでは、その目的はかなりあいまいなものと
なる。例えば、局Ｊがパケットを伝送すると、このパケ
ットは局Ｉによって正確に受信されるが、このパケット
は局Ｋでは（局Ｌによって送られたパケットと）衝突す
ることになる。「このパケット伝送が有害となるか、否
かとして考慮する必要があるか？」と云うことは、答え
なければならない一種の質問事項である。アクセス速度
を制御する基準とする種々の目標機能につき下記に説明
する。
【００１２】ソース宛先トラヒックマトリックスＭが与
えられたものとすれば、この全トラヒックマトリックス
を経路指定するのに要する時間を最小とするため、或い
は同等に、単位時間当りに経路指定し得るトラヒックマ
トリックスの割合を例えばａ％のように最大とするため
に個々のアクセス速度を指定させるようにすることがで
きる。従って、この目標は単位時間当りに正確に伝送し
得るトラヒック量ａ×Ｍを最大とすることにある。この
最大化にとっては全てのアクセス速度を大域的に最適と
する必要がある。この最適化は、「フィリップス リサ
ーチ ラボラトリ，ブラッセルス，レポートＲ514, 198
7 」に P.J.Courtois, G.Scheys 及び P.Semalにより発
表された“A distributed Controller for a Non-Persi
stent CSMAChannel"に記載されているように、計算上極
めて扱いにくく、しかも実際上殆ど実現できない。さら
に、分数形システムではアクセス速度を局部的にしか最
適化できない。これがため、順最適目標を規定する必要
がある。
えられたものとすれば、この全トラヒックマトリックス
を経路指定するのに要する時間を最小とするため、或い
は同等に、単位時間当りに経路指定し得るトラヒックマ
トリックスの割合を例えばａ％のように最大とするため
に個々のアクセス速度を指定させるようにすることがで
きる。従って、この目標は単位時間当りに正確に伝送し
得るトラヒック量ａ×Ｍを最大とすることにある。この
最大化にとっては全てのアクセス速度を大域的に最適と
する必要がある。この最適化は、「フィリップス リサ
ーチ ラボラトリ，ブラッセルス，レポートＲ514, 198
7 」に P.J.Courtois, G.Scheys 及び P.Semalにより発
表された“A distributed Controller for a Non-Persi
stent CSMAChannel"に記載されているように、計算上極
めて扱いにくく、しかも実際上殆ど実現できない。さら
に、分数形システムではアクセス速度を局部的にしか最
適化できない。これがため、順最適目標を規定する必要
がある。
【００１３】２種類の処理能力を区別する必要があり、
これらの処理能力とは局Ｋが単位時間当りに正確に受信
するパケット数Ｆ（→Ｋ）で、以後局Ｋの入力フローと
称するものであり、他の１つは局Ｋが単位時間当りに首
尾良く伝送するパケット数Ｆ（Ｋ→）で、以後局Ｋの出
力フローと称するものである。局Ｋは斯るフローに対す
る承認（肯定応答）を遅かれ早かれ受け取るものとす
る。
これらの処理能力とは局Ｋが単位時間当りに正確に受信
するパケット数Ｆ（→Ｋ）で、以後局Ｋの入力フローと
称するものであり、他の１つは局Ｋが単位時間当りに首
尾良く伝送するパケット数Ｆ（Ｋ→）で、以後局Ｋの出
力フローと称するものである。局Ｋは斯るフローに対す
る承認（肯定応答）を遅かれ早かれ受け取るものとす
る。
【００１４】第１の目標機能は最小入力フローの最大化
にある。即ち、
にある。即ち、
【００１５】この目標を適えるために、各局は（その局
の近接局及びその局も含めて）どの局が最小の入力フロ
ーを出しているかを決め、しかもその局の入力フローを
高めるために、その局固有のアクセス速度を変更する必
要がある。この目標をかなえさせるためには、上記(1)
における最小の入力フローを計算し得るようにするため
に、各局はその現行の入力フローＦ( →Ｋ) を他の局に
伝達する必要がある。最小値が例えば局Ｉであったら、
この局の近隣の局は局Ｉの入力フローを増やすためにそ
れらの局のアクセス速度を変更すべきである。これがた
め、或る局は隣接局に入力フローを増やすことができる
旨を知らせることもできる。例えば、各局Ｋはその局自
体でわかるように現行のチャネル負荷 Gcur (K) を測定
でき、しかもその最大入力フローＦ( →Ｋ) を達成する
チャネル負荷 Gnom (K) を決定し得るようにする必要が
ある。これらの２つの値を知らせれば、局Ｉの隣接局は
入力フローＦ( →Ｉ) を増やすためにそれら隣接局のア
クセス速度を更新することができる。従って、各局が知
らせるべき情報は、次の３つか、 〔Ｆ( →Ｋ) ， G nom (K), G cur (K) 〕
(2) 又はもっと密な形態で、 〔Ｆ( →(K))，G r (K) ＝ G cur (K)／ G nom
(K)〕 (3) から成るものである。この処置の目的は局Ｋが正確に受
信するパケット数を増やすことに過ぎない。これらのパ
ケットの行き先を局Ｋに定めたり、局Ｋにこれらのパケ
ットを中継させなければならないことは何等保証されな
い。
の近接局及びその局も含めて）どの局が最小の入力フロ
ーを出しているかを決め、しかもその局の入力フローを
高めるために、その局固有のアクセス速度を変更する必
要がある。この目標をかなえさせるためには、上記(1)
における最小の入力フローを計算し得るようにするため
に、各局はその現行の入力フローＦ( →Ｋ) を他の局に
伝達する必要がある。最小値が例えば局Ｉであったら、
この局の近隣の局は局Ｉの入力フローを増やすためにそ
れらの局のアクセス速度を変更すべきである。これがた
め、或る局は隣接局に入力フローを増やすことができる
旨を知らせることもできる。例えば、各局Ｋはその局自
体でわかるように現行のチャネル負荷 Gcur (K) を測定
でき、しかもその最大入力フローＦ( →Ｋ) を達成する
チャネル負荷 Gnom (K) を決定し得るようにする必要が
ある。これらの２つの値を知らせれば、局Ｉの隣接局は
入力フローＦ( →Ｉ) を増やすためにそれら隣接局のア
クセス速度を更新することができる。従って、各局が知
らせるべき情報は、次の３つか、 〔Ｆ( →Ｋ) ， G nom (K), G cur (K) 〕
(2) 又はもっと密な形態で、 〔Ｆ( →(K))，G r (K) ＝ G cur (K)／ G nom
(K)〕 (3) から成るものである。この処置の目的は局Ｋが正確に受
信するパケット数を増やすことに過ぎない。これらのパ
ケットの行き先を局Ｋに定めたり、局Ｋにこれらのパケ
ットを中継させなければならないことは何等保証されな
い。
【００１６】前記目標１に関する主たる批判は、入力フ
ローが最小の局が必ずしもその入力フローを増やす必要
があるとは限らず、この局の入力フローは少なくても十
分なことがあると云う点にある。これとは逆に、入力フ
ローが最大の局は、そのまま入力フローを或る程度増や
しておくことを必要とすることもある。このようは批判
を満足させるためには局の個々の要求を考慮する必要が
ある。局Ｋが受信しなければならない（単位時間当り）
のパケット数Ｔ（→Ｋ）とする場合、次のような目標機
能を規定することができる。即ち、
ローが最小の局が必ずしもその入力フローを増やす必要
があるとは限らず、この局の入力フローは少なくても十
分なことがあると云う点にある。これとは逆に、入力フ
ローが最大の局は、そのまま入力フローを或る程度増や
しておくことを必要とすることもある。このようは批判
を満足させるためには局の個々の要求を考慮する必要が
ある。局Ｋが受信しなければならない（単位時間当り）
のパケット数Ｔ（→Ｋ）とする場合、次のような目標機
能を規定することができる。即ち、
【００１７】このような目標では、或る局がその局固有
のアクセス速度g(K)を更新して、局が受信する入力フロ
ーと、その局が受信すべきである入力フローとの比が最
小である隣接局の入力フローを増やすようにする。受信
すべき入力フローＴ（→Ｋ）は生憎局Ｋの隣接局に分配
されるため、この入力フローは隣接局のどこにも利用で
きなくなる。さらに、大抵の場合、経路指定はパケット
を中継する必要のある局までは特別に規定しない。この
ような問題を克服するために次のような目標機能が試さ
れる。
のアクセス速度g(K)を更新して、局が受信する入力フロ
ーと、その局が受信すべきである入力フローとの比が最
小である隣接局の入力フローを増やすようにする。受信
すべき入力フローＴ（→Ｋ）は生憎局Ｋの隣接局に分配
されるため、この入力フローは隣接局のどこにも利用で
きなくなる。さらに、大抵の場合、経路指定はパケット
を中継する必要のある局までは特別に規定しない。この
ような問題を克服するために次のような目標機能が試さ
れる。
【００１８】
【００１９】正しく受信されるフローと、受信しなけれ
ばならないフローとの比を考える代りに、この場合には
正しく送られて、承認される出力フローＦ（Ｋ→）と、
送らなければならない出力フローＴ（Ｋ→）との比を考
慮する。この比は局Ｋの出力待ち行列の長さを測定する
ことによって決定することができる。或る期間中に局Ｋ
がｎ（Ｋ）個のパケットを首尾良く伝送し（これらが承
認され）、且つこの期間の終りにまだg(K)個のパケット
が待ち状態にるものとすれば、この期間に対しては次式
が成立する。
ばならないフローとの比を考える代りに、この場合には
正しく送られて、承認される出力フローＦ（Ｋ→）と、
送らなければならない出力フローＴ（Ｋ→）との比を考
慮する。この比は局Ｋの出力待ち行列の長さを測定する
ことによって決定することができる。或る期間中に局Ｋ
がｎ（Ｋ）個のパケットを首尾良く伝送し（これらが承
認され）、且つこの期間の終りにまだg(K)個のパケット
が待ち状態にるものとすれば、この期間に対しては次式
が成立する。
【００２０】
【数３】
【００２１】出力比と称する量0(K)はどの局でも決める
ことができ、それを近隣の局に知らせて、例えば局Ｉま
で届く局所的最小値を各局によって別々に容易に計算す
ることができる。この場合の目標は最小出力比を高める
ことにある。式(5) から明らかなように、経路指定は最
適化変数とは見なされないから、出力比0(I)を高めるに
は出力フローF(I →) を増やすだけでよい。しかし、局
Ｉで待たされたパケットを中継し得る局が前もってわか
らないから、局の出力フローF(I →) を増やすのは困難
である。大まかなやり方では、局Ｉに増大アクセス速度
g(I)を割当てるために、局Ｉの近隣の局のアクセス速度
を低下させるようにする。この簡単な方法でも極めてま
れなケースで有効なこともあるが、これを制約なしで適
用する場合には極めて弊害がある。
ことができ、それを近隣の局に知らせて、例えば局Ｉま
で届く局所的最小値を各局によって別々に容易に計算す
ることができる。この場合の目標は最小出力比を高める
ことにある。式(5) から明らかなように、経路指定は最
適化変数とは見なされないから、出力比0(I)を高めるに
は出力フローF(I →) を増やすだけでよい。しかし、局
Ｉで待たされたパケットを中継し得る局が前もってわか
らないから、局の出力フローF(I →) を増やすのは困難
である。大まかなやり方では、局Ｉに増大アクセス速度
g(I)を割当てるために、局Ｉの近隣の局のアクセス速度
を低下させるようにする。この簡単な方法でも極めてま
れなケースで有効なこともあるが、これを制約なしで適
用する場合には極めて弊害がある。
【００２２】このことは明らかにアクセス制御をマルチ
ホップ・トポロジに対処させなければならない問題に二
重の特性があることを啓発している。一方では、局、例
えばＫはその隣接局に局Ｋの入力フローF(→K)どれだけ
増やすかについて知らせることができるが、局Ｋはこの
入力フローの増加が必要であるか、どうか判断すること
ができない(T( →K)はわからない）。他方では、局Ｉは
その隣接局に局Ｉが十分な伝送をできない（その局の出
力比が小さ過ぎる）旨を知らせるようにすることができ
るが、たとえそれが首尾よくいったとしても、隣接局は
フローの増加に如何に反応したらよいかわからず、その
隣接局は局Ｉの出力フローを高めるのにどのような反応
すべきなのかわからない。
ホップ・トポロジに対処させなければならない問題に二
重の特性があることを啓発している。一方では、局、例
えばＫはその隣接局に局Ｋの入力フローF(→K)どれだけ
増やすかについて知らせることができるが、局Ｋはこの
入力フローの増加が必要であるか、どうか判断すること
ができない(T( →K)はわからない）。他方では、局Ｉは
その隣接局に局Ｉが十分な伝送をできない（その局の出
力比が小さ過ぎる）旨を知らせるようにすることができ
るが、たとえそれが首尾よくいったとしても、隣接局は
フローの増加に如何に反応したらよいかわからず、その
隣接局は局Ｉの出力フローを高めるのにどのような反応
すべきなのかわからない。
【００２３】図２の例がこの状況を示している。この図
は局所的に最小の出力比0(I)を呈する局Ｉのアクセス速
度を高める大まかなやり方では、ネットワークの他の部
分のパーホーマンスを損なうことになることも示してい
る。
は局所的に最小の出力比0(I)を呈する局Ｉのアクセス速
度を高める大まかなやり方では、ネットワークの他の部
分のパーホーマンスを損なうことになることも示してい
る。
【００２４】局Ｔがセット（集合）Ｍから主として到来
するトラヒックによってオーバーロードされるものとす
る。この結果、局Ｉはそのすぐ隣りの局Ａ、特に集合Ｌ
を経て容易に伝送する局Ｅ及びＦの出力比よりも遙かに
小さい出力比を有する。局Ｉのアクセス速度g(I)を高め
て、この局Ｉの出力フローを高める試みは、最小出力比
を有する局を包含する集合Ｍのみを損なうことになる。
このことからして、アクセス速度を高めるには最深の注
意を払わなければならない。この例は明らかにアクセス
制御が直面しなければならない２元的な問題を啓発して
いる。局Ｉ及び集合Ｍにおける多分幾つかの局は、それ
らの出力フローが小さ過ぎる旨はわかるが、それを改善
する方法がわからず、又局Ｋはその入力フローを大きく
し得ることはわかるが、入力フローの増加が必要かどう
かはわからない。このような状況は情報交換によってし
か解決することができない。最小出力比を最大とするこ
とを目的とし、且つ２つの連続情報交換を必要とする本
発明による分散形プロトコルにつき以下説明する。
するトラヒックによってオーバーロードされるものとす
る。この結果、局Ｉはそのすぐ隣りの局Ａ、特に集合Ｌ
を経て容易に伝送する局Ｅ及びＦの出力比よりも遙かに
小さい出力比を有する。局Ｉのアクセス速度g(I)を高め
て、この局Ｉの出力フローを高める試みは、最小出力比
を有する局を包含する集合Ｍのみを損なうことになる。
このことからして、アクセス速度を高めるには最深の注
意を払わなければならない。この例は明らかにアクセス
制御が直面しなければならない２元的な問題を啓発して
いる。局Ｉ及び集合Ｍにおける多分幾つかの局は、それ
らの出力フローが小さ過ぎる旨はわかるが、それを改善
する方法がわからず、又局Ｋはその入力フローを大きく
し得ることはわかるが、入力フローの増加が必要かどう
かはわからない。このような状況は情報交換によってし
か解決することができない。最小出力比を最大とするこ
とを目的とし、且つ２つの連続情報交換を必要とする本
発明による分散形プロトコルにつき以下説明する。
【００２５】図２に示した例を再び参照するに、本発明
によるプロトコルは次のようなステップを含むものとす
ることができる。即ち、
によるプロトコルは次のようなステップを含むものとす
ることができる。即ち、
【００２６】1.局Ｉはその局の出力比を（放送）知らせ
る； 2.(a) 局Ｔは比較により局Ｉの出力比が最小である旨及
びそれが局Ｉのパケットの潜在的受信局である旨を（そ
のルーテングテーブルでのチェックにより）悟る； (b) この場合に、局Ｔはその入力フローを増やす必要が
ある旨を隣接局に知らせ、且つどれだけ増やすことがで
きるかを（ Gcur (T) 及び Gnom (T) を知らせることに
よって) 告げる。 3.この場合、局Ｔの隣接局は Gcur (T) を Gnom (T) に
近付けるためにそれらのアクセス速度を変更する。
る； 2.(a) 局Ｔは比較により局Ｉの出力比が最小である旨及
びそれが局Ｉのパケットの潜在的受信局である旨を（そ
のルーテングテーブルでのチェックにより）悟る； (b) この場合に、局Ｔはその入力フローを増やす必要が
ある旨を隣接局に知らせ、且つどれだけ増やすことがで
きるかを（ Gcur (T) 及び Gnom (T) を知らせることに
よって) 告げる。 3.この場合、局Ｔの隣接局は Gcur (T) を Gnom (T) に
近付けるためにそれらのアクセス速度を変更する。
【００２７】プロトコルは２つの連続情報交換を必要と
する。先ず出力比を変換する。これにより各局Ｋはその
入力フローの増加傾向（ＩＦＩＴ）を計算することがで
きる。
する。先ず出力比を変換する。これにより各局Ｋはその
入力フローの増加傾向（ＩＦＩＴ）を計算することがで
きる。
【００２８】 ここにＲ（Ｌ）は局Ｌによって放射されたパケットを中
継し得る局の集合を示す。従って最小値は局Ｋの隣接局
（距離を聴取して）であり、しかも局Ｋが中継し得る局
Ｌに引継がれる。この変数ＩＦＩＴ（Ｋ）は局Ｋの入力
フローF(→K)をどれだけ改善すべきかの目安となり、入
力フロー増加傾向の他の目安については後に説明する。
ネットワーク全体における入力フローの増加傾向IFIT
(K) は大域最小出力比を有する局の中継局である局Ｋに
対して最大となる。ＩＦＩＴの決定は上記プロトコルに
おけるステップ(2a)に対応する。
継し得る局の集合を示す。従って最小値は局Ｋの隣接局
（距離を聴取して）であり、しかも局Ｋが中継し得る局
Ｌに引継がれる。この変数ＩＦＩＴ（Ｋ）は局Ｋの入力
フローF(→K)をどれだけ改善すべきかの目安となり、入
力フロー増加傾向の他の目安については後に説明する。
ネットワーク全体における入力フローの増加傾向IFIT
(K) は大域最小出力比を有する局の中継局である局Ｋに
対して最大となる。ＩＦＩＴの決定は上記プロトコルに
おけるステップ(2a)に対応する。
【００２９】第２情報交換はＩＦＩＴに関連する。この
交換により各局Ｋはその隣接局N(K)における最大ＩＦＩ
Ｔを呈する局を求めることができる。 ここに、TK はこの局を示す。N(K)における TK は入力
フローを増やす局である。この場合、局Ｋはそのアクセ
ス速度をそれ相当に変更しなければならない。従って、
このプロトコルの目的はＩを中継し得る局 TK の入力フ
ローを増やすことによって最も小さい出力比0(I)を増や
すことにある。従ってアクセス速度g(K)を図３Ａに示し
た下記の規則により更新させる。
交換により各局Ｋはその隣接局N(K)における最大ＩＦＩ
Ｔを呈する局を求めることができる。 ここに、TK はこの局を示す。N(K)における TK は入力
フローを増やす局である。この場合、局Ｋはそのアクセ
ス速度をそれ相当に変更しなければならない。従って、
このプロトコルの目的はＩを中継し得る局 TK の入力フ
ローを増やすことによって最も小さい出力比0(I)を増や
すことにある。従ってアクセス速度g(K)を図３Ａに示し
た下記の規則により更新させる。
【００３０】図３Ａにおけるg min 及びg max は許容さ
れる最小及び最大アクセス速度をそれぞれ示し、ε，δ
1 ,δ2 , δ3 及びδ4 はプロトコルパラメータであ
る。これらのプロトコルパラメータに対する理想的な形
態を図３Ｂに示してある。局T K と負荷が高過ぎると、
その隣接局は全てそれらのアクセス速度を下げる。局T
K の負荷が軽過ぎると、局Ｋは、それが最小出力比を有
している場合で、しかも局T K が局Ｋを中継し得る場合
にだけアクセス速度を高めることができる。局T K のト
ラヒック負荷が既に最適に調整されている場合には、出
力比が最も小さい局に対するアクセス速度を少し高め
て、他の局アクセス速度を僅かだけ下げる更新だけが有
効となる。
れる最小及び最大アクセス速度をそれぞれ示し、ε，δ
1 ,δ2 , δ3 及びδ4 はプロトコルパラメータであ
る。これらのプロトコルパラメータに対する理想的な形
態を図３Ｂに示してある。局T K と負荷が高過ぎると、
その隣接局は全てそれらのアクセス速度を下げる。局T
K の負荷が軽過ぎると、局Ｋは、それが最小出力比を有
している場合で、しかも局T K が局Ｋを中継し得る場合
にだけアクセス速度を高めることができる。局T K のト
ラヒック負荷が既に最適に調整されている場合には、出
力比が最も小さい局に対するアクセス速度を少し高め
て、他の局アクセス速度を僅かだけ下げる更新だけが有
効となる。
【００３１】アクセス速度の更新は局T K が特定のもの
ではない場合にはかなり複雑なものとなる。この場合に
は、局T K の入力フローを大域的に増加させるために、
アクセス速度を更新させる必要がある。宛先に最も近い
局T K に何等かの優先権を与えて、ネットワークに残さ
なければならないトラヒックに高い優先度を与えること
ができる。
ではない場合にはかなり複雑なものとなる。この場合に
は、局T K の入力フローを大域的に増加させるために、
アクセス速度を更新させる必要がある。宛先に最も近い
局T K に何等かの優先権を与えて、ネットワークに残さ
なければならないトラヒックに高い優先度を与えること
ができる。
【００３２】出力比をより一層一般的に定義するには次
のような限定条件を考慮する。
のような限定条件を考慮する。
【数４】 従って、伝送済み、及び全く伝送しないn(K) ＝0 ＝q
(K)）局の出力比は最大となる。
(K)）局の出力比は最大となる。
【００３３】さらに、入力フロー増加傾向ＩＦＩＴは上
述した所では最も小さい出力比の逆関数として定義し
た。実際上、このようにすると、どの局も最小出力フロ
ーを伝送しなければならないことになる。このことはプ
ロ コルの不公平な特性と見なすことができる。ＩＦＩ
Ｔの他の目安は平均出力比の逆関数、即ち
述した所では最も小さい出力比の逆関数として定義し
た。実際上、このようにすると、どの局も最小出力フロ
ーを伝送しなければならないことになる。このことはプ
ロ コルの不公平な特性と見なすことができる。ＩＦＩ
Ｔの他の目安は平均出力比の逆関数、即ち
【００３４】
【数５】 か、或いは大域化した出力比の逆関数、即ち、
【数６】 とすることができる。これらの目安では、各局のパーホ
ーマンスをその隣接局のパーホーマンスと混合させる。
これにより、或る局が伝送パケットを僅かしか有してお
らず、出力フローがゼロの場合でも公平にすることがで
きる。
ーマンスをその隣接局のパーホーマンスと混合させる。
これにより、或る局が伝送パケットを僅かしか有してお
らず、出力フローがゼロの場合でも公平にすることがで
きる。
【００３６】ＩＦＩＴが最大の局が局Ｋそのものである
場合には、アクセス速度ｇ(K) を特定の方向で更新させ
るべきである。この更新にはこの場合、局Ｋの固有のア
クセス速度ｇ(K) が、この局Ｋによって正しく受信され
るパケット数に支障をきたす旨を考慮する必要がある。
例えば、局Ｋがパケットを伝送している時に、その局が
パケットを受信できなければ、アクセス速度ｇ(K) を減
らして、局Ｋの入力フローを増やす必要がある。
場合には、アクセス速度ｇ(K) を特定の方向で更新させ
るべきである。この更新にはこの場合、局Ｋの固有のア
クセス速度ｇ(K) が、この局Ｋによって正しく受信され
るパケット数に支障をきたす旨を考慮する必要がある。
例えば、局Ｋがパケットを伝送している時に、その局が
パケットを受信できなければ、アクセス速度ｇ(K) を減
らして、局Ｋの入力フローを増やす必要がある。
【００３７】ここで述べたプロトコルはいずれも情報交
換を必要とする。これがため、プロトコルを実行させる
ためには各局の出力及び入力フローを参照とすべきであ
る。この要件の結論はプロトコルの公平な特性が極めて
重要と思われることにある。
換を必要とする。これがため、プロトコルを実行させる
ためには各局の出力及び入力フローを参照とすべきであ
る。この要件の結論はプロトコルの公平な特性が極めて
重要と思われることにある。
【００３８】
【実施例】上述した方法を実行するネットワークにて機
能さすべく設計した局における種々の回路のハードウェ
ヤ構成を図４にブロックにて示してある。図４は受信段
11、伝送段12、トラヒックコントローラ13及び追加のコ
ントローラ14を具えている局10を示す。作動中受信段11
は種々のチャネルからのデータパケットを受信する機能
をし、これらのデータパケットはトラヒックコントロー
ラ13に転送される。このトラヒックコントローラ13は各
受信したデータパケットの宛先をモニタし、且つ局10が
受信データパケットを中継しなければならない場合に
は、その受信データパケットを伝送段12へと転送する
か、或いは局10が上記受信データパケットの宛先であっ
た場合には、その受信データパケットを出力端子15に転
送するか、又はさもなければ受信データパケットを廃棄
する。受信段11、伝送段12及びトラヒックコントローラ
13の機能については当業者にとって周知であると思われ
るので、これらの回路の機能についての説明は省略す
る。
能さすべく設計した局における種々の回路のハードウェ
ヤ構成を図４にブロックにて示してある。図４は受信段
11、伝送段12、トラヒックコントローラ13及び追加のコ
ントローラ14を具えている局10を示す。作動中受信段11
は種々のチャネルからのデータパケットを受信する機能
をし、これらのデータパケットはトラヒックコントロー
ラ13に転送される。このトラヒックコントローラ13は各
受信したデータパケットの宛先をモニタし、且つ局10が
受信データパケットを中継しなければならない場合に
は、その受信データパケットを伝送段12へと転送する
か、或いは局10が上記受信データパケットの宛先であっ
た場合には、その受信データパケットを出力端子15に転
送するか、又はさもなければ受信データパケットを廃棄
する。受信段11、伝送段12及びトラヒックコントローラ
13の機能については当業者にとって周知であると思われ
るので、これらの回路の機能についての説明は省略す
る。
【００３９】上述したように局10は追加のコントローラ
14を装備しており、これは第１計算器16、第２計算器1
7、第３計算器18、比較段19及びアクセス速度変更手段2
0の如き多数のサブ回路を具えている。
14を装備しており、これは第１計算器16、第２計算器1
7、第３計算器18、比較段19及びアクセス速度変更手段2
0の如き多数のサブ回路を具えている。
【００４０】作動中第１計算器16は、データパケットが
伝送段12によって首尾良く伝送される度毎にトラヒック
コントローラ13から情報を受信する。計算器16はトラヒ
ットコントローラ13から受信した情報に基いて上述した
第１パラメータを計算し、このパラメータは伝送段12に
よって単位時間当りに首尾良く伝送されるパケット数を
示し、これは換言するに局10の出力フローを示す第１パ
ラメータである。この計算した第１パラメータを計算器
16から伝送段12に供給して、隣接局へと伝送する。
伝送段12によって首尾良く伝送される度毎にトラヒック
コントローラ13から情報を受信する。計算器16はトラヒ
ットコントローラ13から受信した情報に基いて上述した
第１パラメータを計算し、このパラメータは伝送段12に
よって単位時間当りに首尾良く伝送されるパケット数を
示し、これは換言するに局10の出力フローを示す第１パ
ラメータである。この計算した第１パラメータを計算器
16から伝送段12に供給して、隣接局へと伝送する。
【００４１】局10の受信段11は隣接局からの第１パラメ
ータも受信し、これらの第１パラメータは受信段11から
第２計算器17へと転送され、ここでは上記第１パラメー
タを用いて局10の入力フローの増加傾向を示す前述した
第２パラメータを計算する。
ータも受信し、これらの第１パラメータは受信段11から
第２計算器17へと転送され、ここでは上記第１パラメー
タを用いて局10の入力フローの増加傾向を示す前述した
第２パラメータを計算する。
【００４２】第３計算器18はトラヒックコントローラ13
から情報を受信し、それに基いて局10の負荷を示す第３
パラメータを計算する。
から情報を受信し、それに基いて局10の負荷を示す第３
パラメータを計算する。
【００４３】第２計算器17によって計算した第２パラメ
ータ及び第３計算器18によって計算した第３パラメータ
の双方を伝送段12に転送してから、これらを局10の及ぶ
範囲の全ての隣接局に伝送する。
ータ及び第３計算器18によって計算した第３パラメータ
の双方を伝送段12に転送してから、これらを局10の及ぶ
範囲の全ての隣接局に伝送する。
【００４４】受信段11にて受信される隣接局からの第２
及び第３パラメータは比較段19に転送され、ここで全て
の隣接局から受信されたパラメータを互いに比較し、且
つ局10の直ぐ隣りのどの局が最も大きな入力フローの増
加傾向を有しているのかを決定する。この判定を反映す
る信号を比較段19からアクセス速度変更手段20に転送す
る。このアクセス速度変更手段20は斯様な信号の受信に
応答して適当な制御信号をトラヒックコントローラ13に
与え、局10のアクセス速度が上述したような方法で更新
させる。
及び第３パラメータは比較段19に転送され、ここで全て
の隣接局から受信されたパラメータを互いに比較し、且
つ局10の直ぐ隣りのどの局が最も大きな入力フローの増
加傾向を有しているのかを決定する。この判定を反映す
る信号を比較段19からアクセス速度変更手段20に転送す
る。このアクセス速度変更手段20は斯様な信号の受信に
応答して適当な制御信号をトラヒックコントローラ13に
与え、局10のアクセス速度が上述したような方法で更新
させる。
【００４５】図４の追加のコントローラ14は多数の別個
のサブ回路16, 17, 18, 19及び20を具えているが、より
精巧な例として追加のコントローラ14は適当にプログラ
ム化したプロセッサ又はコンピュータで構成し、これに
て種々の計算及び比較操作を行ない、且つ適切な信号を
伝送段12に与えたり、トラヒックコントローラ13に制御
信号を与えたりすることもできることは明らかである。
のサブ回路16, 17, 18, 19及び20を具えているが、より
精巧な例として追加のコントローラ14は適当にプログラ
ム化したプロセッサ又はコンピュータで構成し、これに
て種々の計算及び比較操作を行ない、且つ適切な信号を
伝送段12に与えたり、トラヒックコントローラ13に制御
信号を与えたりすることもできることは明らかである。
【図１】単純化したマルチポップパケット無線ネットワ
ークを示す線図である。
ークを示す線図である。
【図２】マルチポップ無線ネットワークを極めて図式的
に示した線図である。
に示した線図である。
【図３】（Ａ）は、本発明による方法に用いる汎用のア
クセス速度更新規則の大要を示す説明図である。（Ｂ）
は、プロトコルパラメータがとり得る形態を示す説明図
である。
クセス速度更新規則の大要を示す説明図である。（Ｂ）
は、プロトコルパラメータがとり得る形態を示す説明図
である。
【図４】ネットワーク局の１つを構成するハードウェヤ
のブロック図である。
のブロック図である。
10 局 11 受信段 12 伝送段 13 トラヒックコントローラ 16 第１計算器 17 第２計算器 18 第３計算器 19 比較段 20 アクセス速度変更手段
───────────────────────────────────────────────────── フロントページの続き (73)特許権者 590000248 Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １, 5621 ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔ ｈｅ Ｎｅｔｈｅｒｌａｎｄｓ (72)発明者 ギ フランソワ ジュール シェイ ベルギー国 ブリュッセル アブニュ ベスラール２ (72)発明者 ピェール ニコラス ウィリ セマル ベルギー国 ブリュッセル アブニュ ベスラール２
Claims (11)
- 【請求項１】 経路指定計画に従って或る局から他の局
へとデータパケットを転送することのできる無線通信チ
ャネルによって相互接続される多数の送／受信局を具え
ているデータパケット交換ネットワークにおける局のア
クセス速度を制御するシステムであって、各局が： −データパケットを受信し、且つ伝送する手段と； −単位時間当りに首尾良く伝送されたパケット数である
当該局の出力フローを示す第１パラメータを計算する第
１計算手段と； −当該局が中継し得る隣接局の出力フローに基づく分量
でこれら隣接局の出力フローが減少すると増える当該局
の入力フロー増加傾向を示す第２パラメータを計算する
第２計算手段と； −当該局の負荷を示す第３パラメータを計算する第３計
算手段と； −前記第１，第２及び第３パラメータを当該局の及ぶ受
信範囲の全隣接局に伝送する伝送手段と； −当該局のアクセス速度を変更するアクセス速度変更手
段と； −比較手段； とを具え、ネットワークの作動中に各局では前記第１パ
ラメータを前記第１計算手段により計算して、この第１
パラメータを前記伝送手段により各局が及ぶ受信範囲に
おける全ての隣接局に規則的な時間間隔で伝送し、その
後各局では前記第２及び第３パラメータを前記第２及び
第３計算手段により計算し、各局の伝送手段がその隣接
局に前記第２及び第３パラメータを伝送し、これら隣接
局における前記比較手段は、前記第２及び第３パラメー
タの受信後に、それらの隣接局のどの局が最も大きな入
力フローの増加傾向を有しているかを決定し、且つ第３
パラメータに基づいて前記アクセス速度変更手段が前記
隣接局のアクセス速度を更新して、最も大きな入力フロ
ーの増加傾向を有している局の負荷を公称チャネル負荷
に近付け得るように前記システムを機能させることを特
徴とするデータパケット交換ネットワークにおける局の
アクセス速度制御システム。 - 【請求項２】 前記第１パラメータは、正しく送られた
パケットのフローと、送らなければならないパケットの
フローとの比である出力比とすることを特徴とする請求
項１のシステム。 - 【請求項３】 作業中に前記第１計算手段が前記出力比
を、データパケット伝送手段により首尾良く送られ、且
つ所定の期間中に承認されたパケット数と、このパケッ
ト数と前記期間の終了時にデータパケット伝送手段でま
だ待機しているパケット数との和との比として計算する
ことを特徴とする請求項２のシステム。 - 【請求項４】 作動中に前記第２計算手段が次のアルゴ
リズム、即ち に従って入力フロー増加傾向を計算し、ここにＩＦＩＴ
(K) は局Ｋの入力フロー増加傾向、R(L)は局Ｌが送った
パケットを中継し得る局の集合、0(L)は局Ｌの出力比と
したことを特徴とする請求項１〜３のいずれか一項のシ
ステム。 - 【請求項５】 各局のアクセス速度g(K)を下記の規則に
従ってアクセス速度変更手段により更新させ、 【数１】 ここに、G min 及びG max は許容される最小及び最大ア
クセス速度をそれぞれ示し、∈，δ1,δ2,δ3 及びδ4
はプロトコルパラメータとしたことを特徴とする請求項
１〜４のいずれか一項のシステム。 - 【請求項６】 前記第１，第２及び第３計算手段を１つ
のプログラム化したコンピュータに併合させたことを特
徴とする請求項１〜６のいずれか一項のシステム。 - 【請求項７】 経路指定計画に従って成る局から他の局
へとデータパケットを転送することのできる無線通信チ
ャネルによって相互接続される数の送／受信局を具えて
いるデータパケット交換ネットワークにおける局のアク
セス速度を制御する方法において、前記ネットワークの
作動中に各局が単位時間当りに首尾良く伝送されたパケ
ット数である当該局の出力フローを示す第１パラメータ
を計算し、且つこのパラメータを前記局の及ぶ受信範囲
における全隣接局に所定の時間間隔で伝送し、その後各
局は、それが中継し得る隣接局の出力フローに基づく分
量で、これら隣接局の出力フローが減少すると増える当
該局の入力フロー増加傾向を示す第２パラメータと、当
該局の負荷を示す第３パラメータを計算し、その後各局
はその隣接局に前記第２及び第３パラメータを伝送し、
これらの隣接局では前記第２及び第３パラメータの受信
後にこれらの隣接局のどの局が最も大きな入力フロー増
加傾向を有しているかを決定し、且つ第３パラメータに
基づいてそれらの隣接局のアクセス速度を更新して、最
も大きな入力フローの増加傾向を有している局の負荷を
公称チャネル負荷に近付けるようにすることを特徴とす
るデータパケット交換ネットワークにおける局のアクセ
ス速度制御方法。 - 【請求項８】 前記第１パラメータは、正しく送られた
パケットのフローと、送らなければならないパケットの
フローとの比である出力比とすることを特徴とする請求
項７の方法。 - 【請求項９】 前記出力比を、首尾良く送られ、且つ所
定の期間中に承認されたパケット数と、このパケット数
と前記期間の終了時にまだ待機しているパケット数との
和との比として計算することを特徴とする請求項８の方
法。 - 【請求項１０】 前記入力フロー増加傾向が、 として規定され、ここにＩＦＩＴ(K) は局Ｋの入力フロ
ー増加傾向、Ｒ(L) は局Ｌによって送られたパケットを
中継し得る局の集合、0(L)は局Ｌの出力比とすることを
特徴とする請求項７〜９のいずれか一項の方法。 - 【請求項１１】 各局のアクセス速度g(K)を下記の規則
に従って更新させ、 【数２】 ここにG min 及び G maxは許容される最小及び最大アク
セス速度をそれぞれ示し、∈，δ1,δ2,δ3 及びδ4 は
プロトコルパラメータとすることを特徴とする請求項７
〜10のいずれか一項の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| NL89203188.1 | 1989-12-14 | ||
| EP89203188A EP0432315B1 (en) | 1989-12-14 | 1989-12-14 | System and method for controlling the access rates of packet switching network stations |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04135336A JPH04135336A (ja) | 1992-05-08 |
| JP3045547B2 true JP3045547B2 (ja) | 2000-05-29 |
Family
ID=8202526
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP41800090A Expired - Lifetime JP3045547B2 (ja) | 1989-12-14 | 1990-12-14 | データパケット交換ネットワークにおける局のアクセス速度制御システム及び方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5146454A (ja) |
| EP (1) | EP0432315B1 (ja) |
| JP (1) | JP3045547B2 (ja) |
| CA (1) | CA2031971C (ja) |
| DE (1) | DE68922905T2 (ja) |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| SE469252B (sv) * | 1991-10-04 | 1993-06-07 | Eritel Ab | Foerfarande foer kontroll och styrning av datafloedet i ett paketdatanaet omfattande ett antal linjer och ett antal noder daer linjerna via noder foerbinder ett antal terminaler |
| US5276677A (en) * | 1992-06-26 | 1994-01-04 | Nec Usa, Inc. | Predictive congestion control of high-speed wide area networks |
| JPH06303282A (ja) * | 1993-04-13 | 1994-10-28 | Hitachi Ltd | 情報伝送系における情報処理方式 |
| MY123040A (en) * | 1994-12-19 | 2006-05-31 | Salbu Res And Dev Proprietary Ltd | Multi-hop packet radio networks |
| GB9509921D0 (en) * | 1995-05-17 | 1995-07-12 | Roke Manor Research | Improvements in or relating to mobile radio systems |
| US6097700A (en) * | 1995-09-18 | 2000-08-01 | Telefonaktiebolaget L M Ericsson (Publ) | Packet switched radio channel congestion control |
| US5742588A (en) * | 1995-09-18 | 1998-04-21 | Telefonaktiebolaget Lm Ericsson | Packet switched traffic management in a cellular telecommunications system |
| FI102868B (fi) * | 1996-02-26 | 1999-02-26 | Nokia Mobile Phones Ltd | Päätelaite tietoliikennepalvelun käyttämiseksi |
| SE509542C2 (sv) * | 1997-06-27 | 1999-02-08 | Ericsson Telefon Ab L M | Paketförmedling i ett cellulärt radiokommunikationssystem |
| US20030158942A1 (en) * | 2002-02-15 | 2003-08-21 | Exanet, Inc. | Real-time reconfiguration of computer networks based on system measurements |
| US7433366B1 (en) * | 2003-05-16 | 2008-10-07 | Cisco Technology, Inc. | Offered load fairness in a stack |
| US9642093B2 (en) * | 2012-09-24 | 2017-05-02 | Nec Corporation | Method and system for operating stations in a cooperative station network |
| US9525638B2 (en) | 2013-10-15 | 2016-12-20 | Internap Corporation | Routing system for internet traffic |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4534024A (en) * | 1982-12-02 | 1985-08-06 | At&T Bell Laboratories | System and method for controlling a multiple access data communications system including both data packets and voice packets being communicated over a cable television system |
| DE3276041D1 (en) * | 1982-12-28 | 1987-05-14 | Ibm | Method of dynamic assignment of speeds in a multiplex transmission system |
| US4611322A (en) * | 1984-08-03 | 1986-09-09 | At&T Bell Laboratories | Traffic load control arrangement and method for a packet switching system |
| IT1199859B (it) * | 1985-03-06 | 1989-01-05 | Cselt Centro Studi Lab Telecom | Rete locale integrata ad alta velo-cita'riconfigurabile |
| US4734908A (en) * | 1986-10-31 | 1988-03-29 | American Telephone And Telegraph Company, At&T Bell Laboratories | High speed trunk interface with concurrent protocol handlers |
| EP0276349B1 (en) * | 1987-01-28 | 1992-03-25 | International Business Machines Corporation | Apparatus for switching information between channels for synchronous information traffic and asynchronous data packets |
-
1989
- 1989-12-14 EP EP89203188A patent/EP0432315B1/en not_active Expired - Lifetime
- 1989-12-14 DE DE68922905T patent/DE68922905T2/de not_active Expired - Fee Related
-
1990
- 1990-11-30 US US07/621,108 patent/US5146454A/en not_active Expired - Lifetime
- 1990-12-11 CA CA002031971A patent/CA2031971C/en not_active Expired - Fee Related
- 1990-12-14 JP JP41800090A patent/JP3045547B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| CA2031971A1 (en) | 1991-06-15 |
| CA2031971C (en) | 2001-12-18 |
| DE68922905T2 (de) | 1995-12-21 |
| EP0432315B1 (en) | 1995-05-31 |
| DE68922905D1 (de) | 1995-07-06 |
| EP0432315A1 (en) | 1991-06-19 |
| US5146454A (en) | 1992-09-08 |
| JPH04135336A (ja) | 1992-05-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7197016B2 (en) | Time division protocol for an ad-hoc, peer-to-peer radio network having coordinating channel access to shared parallel data channels with separate reservation channel | |
| JP3045547B2 (ja) | データパケット交換ネットワークにおける局のアクセス速度制御システム及び方法 | |
| KR100823467B1 (ko) | 애드 혹 네트워크들에서 공평성 및 서비스 차별성을 제공하기 위한 시스템 및 방법 | |
| JP4723035B2 (ja) | 無線アドホック・ネットワーク用分散オーバレイ多チャンネル・メディア・アクセス制御（ｍａｃ） | |
| EP1912391B1 (en) | Method and system for efficient network formation and maintenance of node routing databases in a mobile ad-hoc network | |
| US7633865B2 (en) | Network operations control in packet data networks | |
| KR101018141B1 (ko) | 무선 네트워크에서 토폴로지 제어를 수행하기 위한 시스템및 방법 | |
| US20080151834A1 (en) | Method and apparatus for maintaining traffic flow in a mesh network | |
| US8155006B2 (en) | Method, device, and communication system for adjusting data rates in a network | |
| US9402244B2 (en) | Multiple simultaneous link transmissions for a multi-frequency multi-rate multi-transceiver communications device | |
| JP2962509B1 (ja) | 移動体通信システム、基地局装置、移動局装置および送信電力制御方法 | |
| JP2005323150A (ja) | 無線情報通信方法、無線通信端末及び無線通信親局 | |
| US20080151833A1 (en) | Method and apparatus for distributed bandwidth assignment in mesh backhaul networks | |
| JP2005236362A (ja) | 通信中継装置 | |
| CN114258112B (zh) | 一种ap选举方法、装置及计算机可读存储介质 | |
| JP2006157640A (ja) | 無線通信システム | |
| JP2006345339A (ja) | リングネットワークを構成するノード装置およびデータフレーム制御方法 | |
| CN117425193A (zh) | 一种基于tdma定向分布式资源动态调度方法 | |
| Jose et al. | Network routing system, method, and computer program product |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090317 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100317 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100317 Year of fee payment: 10 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100317 Year of fee payment: 10 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100317 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110317 Year of fee payment: 11 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110317 Year of fee payment: 11 |