JPH0746267A - トークンリングネットワークの同期帯域幅割り当てシステム - Google Patents
トークンリングネットワークの同期帯域幅割り当てシステムInfo
- Publication number
- JPH0746267A JPH0746267A JP6137386A JP13738694A JPH0746267A JP H0746267 A JPH0746267 A JP H0746267A JP 6137386 A JP6137386 A JP 6137386A JP 13738694 A JP13738694 A JP 13738694A JP H0746267 A JPH0746267 A JP H0746267A
- Authority
- JP
- Japan
- Prior art keywords
- time
- message
- token
- node
- bandwidth allocation
- 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
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
- H04L12/42—Loop networks
- H04L12/427—Loop networks with decentralised control
- H04L12/433—Loop networks with decentralised control with asynchronous transmission, e.g. token ring, register insertion
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/64—Hybrid switching systems
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Small-Scale Networks (AREA)
- Synchronisation In Digital Transmission Systems (AREA)
Abstract
(57)【要約】
【目的】 ネットワークマネジャから適当な同期帯域幅
の確保の許可を得ようとするノードにより利用されるト
ークンリングネットワークについて、最小同期帯域幅割
り当てｈiを発生するために提供されるシステムであ
る。 【構成】 同期帯域幅割り当てを、ネットワークの最小
メッセージ発生期間Ｔ、最大メッセージ送信時間Ｃ、要
求メッセージ供給遅延限界ｄ及び目標トークン巡回時間
ＴＴＲＴに基づいて定めることにより可能になる。ｈi
は、ノードに許された最悪の場合の送信メッセージの時
間がメッセージ供給時間制約条件を満足させる必要があ
るノードの時間よりも小さくないことを保証することに
より計算される。 【効果】 このシステムは、従来の場合の条件であった
ｄ＝Ｔである場合に限らず、ｄのいかなる値にも適応す
る。このシステムは単純に実行できるとともに異なるメ
ッセージ供給時間制約条件をもつさらに多くのアプリケ
ーションに適用することができる。
の確保の許可を得ようとするノードにより利用されるト
ークンリングネットワークについて、最小同期帯域幅割
り当てｈiを発生するために提供されるシステムであ
る。 【構成】 同期帯域幅割り当てを、ネットワークの最小
メッセージ発生期間Ｔ、最大メッセージ送信時間Ｃ、要
求メッセージ供給遅延限界ｄ及び目標トークン巡回時間
ＴＴＲＴに基づいて定めることにより可能になる。ｈi
は、ノードに許された最悪の場合の送信メッセージの時
間がメッセージ供給時間制約条件を満足させる必要があ
るノードの時間よりも小さくないことを保証することに
より計算される。 【効果】 このシステムは、従来の場合の条件であった
ｄ＝Ｔである場合に限らず、ｄのいかなる値にも適応す
る。このシステムは単純に実行できるとともに異なるメ
ッセージ供給時間制約条件をもつさらに多くのアプリケ
ーションに適用することができる。
Description
【０００１】
【産業上の利用分野】この発明は、コンピュータネット
ワークにおいて、デジタルビデオあるいはオーディオの
送信及び分散制御あるいは監視のようなリアルタイムア
プリケーションを可能にするＦＤＤＩ（Fiber Distribu
ted data interface）トークンリングネットワークのた
めの同期帯域幅割り当てシステムに関するものである。
ワークにおいて、デジタルビデオあるいはオーディオの
送信及び分散制御あるいは監視のようなリアルタイムア
プリケーションを可能にするＦＤＤＩ（Fiber Distribu
ted data interface）トークンリングネットワークのた
めの同期帯域幅割り当てシステムに関するものである。
【０００２】
【従来の技術】物理的に離れている多くの位置にあり、
多数の異なるユーザーにより使用される小規模及び中規
模のパーソナルコンピュータが増加すると、それに伴っ
て大きなネットワークに個々のコンピュータ端末を接続
してそれぞれのネットワーク端末の間において容易に通
信を行う必要性や要求が生じてくる。ネットワークの端
末の数及びネットワークに接続されている端末の間の物
理的に分離された距離が増加するにつれて、ネットワー
クで相互に接続された多数のコンピュータを適応させる
ために比較的高速に通信することができるネットワーク
を提供することが重要になる。
多数の異なるユーザーにより使用される小規模及び中規
模のパーソナルコンピュータが増加すると、それに伴っ
て大きなネットワークに個々のコンピュータ端末を接続
してそれぞれのネットワーク端末の間において容易に通
信を行う必要性や要求が生じてくる。ネットワークの端
末の数及びネットワークに接続されている端末の間の物
理的に分離された距離が増加するにつれて、ネットワー
クで相互に接続された多数のコンピュータを適応させる
ために比較的高速に通信することができるネットワーク
を提供することが重要になる。
【０００３】このような大規模なネットワークのひとつ
がトークンリングネットワークである。トークンリング
において、多数のローカルサイトが閉ループ状の送信媒
体に直列に接続されている。一つの動作中の端末から他
の端末に対して、メッセージと呼ばれるデータの流れと
しての情報が連続して送信される。それぞれの端末は、
通常、それぞれのメッセージを再発生及び反復する。そ
して、リング上の他のデバイスと通信するために、リン
グへの１つ又はそれ以上のデバイスを接続する手段とし
て機能する。送信媒体にアクセスした端末は、リングに
対して情報を送信する。情報はひとつの端末から次の端
末へ巡回する。情報は目的の端末を指定して情報が通過
したときにコピーさせるアドレスとともに送信される。
メッセージは直列に相互接続された端末に沿って移動
し、最後に最初にメッセージを送信した端末に戻され
る。そして、その端末はリングから送信情報を除去す
る。
がトークンリングネットワークである。トークンリング
において、多数のローカルサイトが閉ループ状の送信媒
体に直列に接続されている。一つの動作中の端末から他
の端末に対して、メッセージと呼ばれるデータの流れと
しての情報が連続して送信される。それぞれの端末は、
通常、それぞれのメッセージを再発生及び反復する。そ
して、リング上の他のデバイスと通信するために、リン
グへの１つ又はそれ以上のデバイスを接続する手段とし
て機能する。送信媒体にアクセスした端末は、リングに
対して情報を送信する。情報はひとつの端末から次の端
末へ巡回する。情報は目的の端末を指定して情報が通過
したときにコピーさせるアドレスとともに送信される。
メッセージは直列に相互接続された端末に沿って移動
し、最後に最初にメッセージを送信した端末に戻され
る。そして、その端末はリングから送信情報を除去す
る。
【０００４】媒体を通過するトークンを発見してつかま
えると、端末は媒体に対してその情報を送信する権利を
得る。トークンはユニークなシンボルの列からなる制御
信号であり、送信されたデータが加えられて媒体を巡回
する。トークンをある端末が発見すると、その端末はリ
ングからトークンを取り出す。そして、その端末は１つ
又はそれ以上の情報のフレームを送信し、このデータ送
信が完了したときに、他の端末がリングにアクセスでき
るように新しいトークンを出力する。トークンを通過さ
せる前に１つの端末が媒体を占有する時間は、トークン
保持タイマにより制御される。
えると、端末は媒体に対してその情報を送信する権利を
得る。トークンはユニークなシンボルの列からなる制御
信号であり、送信されたデータが加えられて媒体を巡回
する。トークンをある端末が発見すると、その端末はリ
ングからトークンを取り出す。そして、その端末は１つ
又はそれ以上の情報のフレームを送信し、このデータ送
信が完了したときに、他の端末がリングにアクセスでき
るように新しいトークンを出力する。トークンを通過さ
せる前に１つの端末が媒体を占有する時間は、トークン
保持タイマにより制御される。
【０００５】トークンによるリングへのアクセスの調整
に加えて、要求されるサービスの相対的なクラスに対応
して、優先順位の複数のレベルが独立、かつ動的なリン
グ帯域幅の指定に役に立つように、リング帯域幅の複数
のレベルの優先順位をつけることが可能である。サービ
スのクラスには、同期、非同期、あるいは即時サービス
がある。全てのクラスのサービスに対して、有限なリン
グ帯域幅の割り当てはリングのユーザーの間の相互の同
意によりなされる。有限の帯域幅は、第１に、先に述べ
たクラス、すなわち上記に定義された同期及び非同期の
部分に分割される。非同期通信とは、サービスに対する
全ての要求が、動的に割り当てられたリング帯域幅及び
応答時間の集まりのために競争を行う、データ送信サー
ビスのクラスである。同期通信とは、通信を要求するそ
れぞれの端末に対して予め最大の帯域幅が割り当てられ
ており、かつ、特有の遅延時間を越えないように応答時
間が保証されている、データ送信サービスのクラスであ
る。即時データ送信は一般にリングの修復のような特別
なアプリケーションでのみ使用される。
に加えて、要求されるサービスの相対的なクラスに対応
して、優先順位の複数のレベルが独立、かつ動的なリン
グ帯域幅の指定に役に立つように、リング帯域幅の複数
のレベルの優先順位をつけることが可能である。サービ
スのクラスには、同期、非同期、あるいは即時サービス
がある。全てのクラスのサービスに対して、有限なリン
グ帯域幅の割り当てはリングのユーザーの間の相互の同
意によりなされる。有限の帯域幅は、第１に、先に述べ
たクラス、すなわち上記に定義された同期及び非同期の
部分に分割される。非同期通信とは、サービスに対する
全ての要求が、動的に割り当てられたリング帯域幅及び
応答時間の集まりのために競争を行う、データ送信サー
ビスのクラスである。同期通信とは、通信を要求するそ
れぞれの端末に対して予め最大の帯域幅が割り当てられ
ており、かつ、特有の遅延時間を越えないように応答時
間が保証されている、データ送信サービスのクラスであ
る。即時データ送信は一般にリングの修復のような特別
なアプリケーションでのみ使用される。
【０００６】多数のネットワークの端末が数マイルの距
離にわたって分散配置されているとき、データが送信さ
れる送信媒体が非常に重要になってくる。このように多
数のネットワークステーションが相互に接続されている
送信媒体の１つは、光ファイバ媒体である。光ファイバ
媒体において、光送信機からの光信号は、光ファイバ導
波路を通って伝搬し、光受信機に導かれる。上記で名づ
けたデータ送信のクラスは、ファイバ分配データインタ
フェース（ＦＤＤＩ）と呼ばれる標準化された光ファイ
バネットワークにおいて実現されている。ＦＤＤＩは、
一般に多数の層からなっている。すなわち、データイン
タフェースの物理的な要求を定義する物理層、データの
完全性を確保する共通のプロトコルばかりでなく媒体へ
の公平な決定論的なアクセスを定義するデータ層、及び
さまざまなＦＤＤＩ層においてプロセスの実行を管理す
る端末レベルでの必要な制御を定義する端末管理層であ
る。リアルタイム通信を行うためには、ＦＤＤＩにより
提供されるサービスをアプリケーションでいかに使用す
るのかが重要である。とりわけ、要求される遅延時間の
範囲でそれぞれのリアルタイムのメッセージを送信する
ことが保障されている端末において、必要とされる同期
帯域幅の割り当てを計算するシステムの提供が重要であ
る。
離にわたって分散配置されているとき、データが送信さ
れる送信媒体が非常に重要になってくる。このように多
数のネットワークステーションが相互に接続されている
送信媒体の１つは、光ファイバ媒体である。光ファイバ
媒体において、光送信機からの光信号は、光ファイバ導
波路を通って伝搬し、光受信機に導かれる。上記で名づ
けたデータ送信のクラスは、ファイバ分配データインタ
フェース（ＦＤＤＩ）と呼ばれる標準化された光ファイ
バネットワークにおいて実現されている。ＦＤＤＩは、
一般に多数の層からなっている。すなわち、データイン
タフェースの物理的な要求を定義する物理層、データの
完全性を確保する共通のプロトコルばかりでなく媒体へ
の公平な決定論的なアクセスを定義するデータ層、及び
さまざまなＦＤＤＩ層においてプロセスの実行を管理す
る端末レベルでの必要な制御を定義する端末管理層であ
る。リアルタイム通信を行うためには、ＦＤＤＩにより
提供されるサービスをアプリケーションでいかに使用す
るのかが重要である。とりわけ、要求される遅延時間の
範囲でそれぞれのリアルタイムのメッセージを送信する
ことが保障されている端末において、必要とされる同期
帯域幅の割り当てを計算するシステムの提供が重要であ
る。
【０００７】
【発明が解決しようとする課題】ＦＤＤＩトークンリン
グネットワークでは、同期メッセージに対して保障され
たスループット及びそれぞれのノードあるいはステーシ
ョンに対して一定限度の媒体アクセス遅延時間が用意さ
れている。しかしながら、このことのみでは、それぞれ
の及び全てのクリティカルメッセージを適宜に供給する
ことを要求する多くのリアルタイムアプリケーションを
効果的に扱うことができない。この理由は、ＦＤＤＩは
ノードへの媒体アクセス遅延時間の限度を保障している
がメッセージに対しては保障していないからである。メ
ッセージ伝搬遅延時間は、たとえメッセージが保障され
たスループットより大きくない率で発生されるとして
も、媒体アクセス遅延時間の限度を越えることもある。
グネットワークでは、同期メッセージに対して保障され
たスループット及びそれぞれのノードあるいはステーシ
ョンに対して一定限度の媒体アクセス遅延時間が用意さ
れている。しかしながら、このことのみでは、それぞれ
の及び全てのクリティカルメッセージを適宜に供給する
ことを要求する多くのリアルタイムアプリケーションを
効果的に扱うことができない。この理由は、ＦＤＤＩは
ノードへの媒体アクセス遅延時間の限度を保障している
がメッセージに対しては保障していないからである。メ
ッセージ伝搬遅延時間は、たとえメッセージが保障され
たスループットより大きくない率で発生されるとして
も、媒体アクセス遅延時間の限度を越えることもある。
【０００８】これ以上の背景技術の説明に代えて、トー
クンパッシングシステムについての有用な従来技術を記
載した文献のリストを以下に示す。
クンパッシングシステムについての有用な従来技術を記
載した文献のリストを以下に示す。
【０００９】G.Agrawal,B.Chen,W.Zhao,and S.Davari.
Guaranteeing synchronousmessage deadlines with the
timed token protocol. In Proceedings of IEEE, Jun
e 1992;B.Chen,G.Agrawal,and W.Zhao. Optimal synchr
onous capacity allo-cation for hard real-time comm
unications with the timed token protocol.In Procee
dings of Real-Time Systems Symposium. IEEE,Decembe
r 1992;FDDI Station Management(SMT)-draft propose
d. American NationalStandard,ANSI X3T9/92067,June
25,1992;Fiber Distributed Data Interface(FDDI)-Tok
en Ring Media AccessControl(MAC). American Nationa
l Standard,ANSI X3.139,1987;Domenico Ferrari and D
inesh C.Verma. A scheme for real-timechannel estab
lishment in wide-area networks. IEEE Journal on Se
lectedAreas in Communications, SAC-8(3):368-379,Ap
ril 1990;Dilip D.Kandlur,Kang G.Shin,and Domenico
Ferrari. Real-timecommunication in multi-hop netwo
rks. In Proceedings of 11th conferenceon Distribut
ed Computer Systems,pages 300-307, IEEE,May 1991;F
loyd E.Ross. An overview of FDDI, The fiber distri
buted datainterface. IEEE Journal on Selected Area
s in Communications,7(7):1043-1051,September 1989;
K.C.Sevcik ancd M.J.Johnson. Cycle time properties
of the FDDItoken ting protocol. Technical Report
CSRI-179,Computer Science ReserchInstitute,Univers
ity of Toronto,1986;K.G.Shin and Qin Zheng. FDDI-M
:a scheme to doubule FDDI's ability of supporting
synchronous traffic. Patent pending;Alfred C.Weav
er. Local area networks and busses an analysis.Tec
hnical report,Flight Data Systems, NASA-Johnson Sp
ace Center,1986;Qin Zheng. Real-time Fault-tolera
nt Communication in ComputerNetworks. PhD thesis,U
niversity of Michigan,1993;Qin Zheng and Kang G.Sh
in.Fault-tolerant real-time communication in distr
ibuted computing systems. In Proc. 22nd Annual Int
ernationalSymposium on Fault-tolerant Computing,pa
ge 86-93 9992;Qin Zheng and Kang G.Shin. Real-time
communication in local area ring networks. In Pro
ceedings of Conference on Local Computer Networks,
pages 416-425,September 1992;Qin Zheng and Kang G.
Shin. On the ability of establishing real-time cha
nnels in point-to-point packet-switched networks.
IEEE Transactions on Communication (in press),199
3;Qin Zheng,Kang G.Shin,and Abram-Profeta. Transmi
ssion of compressed digital motion video over comp
uter networks. In Digest of COMPCONSpring'93,pages
37-46,February 1993.
Guaranteeing synchronousmessage deadlines with the
timed token protocol. In Proceedings of IEEE, Jun
e 1992;B.Chen,G.Agrawal,and W.Zhao. Optimal synchr
onous capacity allo-cation for hard real-time comm
unications with the timed token protocol.In Procee
dings of Real-Time Systems Symposium. IEEE,Decembe
r 1992;FDDI Station Management(SMT)-draft propose
d. American NationalStandard,ANSI X3T9/92067,June
25,1992;Fiber Distributed Data Interface(FDDI)-Tok
en Ring Media AccessControl(MAC). American Nationa
l Standard,ANSI X3.139,1987;Domenico Ferrari and D
inesh C.Verma. A scheme for real-timechannel estab
lishment in wide-area networks. IEEE Journal on Se
lectedAreas in Communications, SAC-8(3):368-379,Ap
ril 1990;Dilip D.Kandlur,Kang G.Shin,and Domenico
Ferrari. Real-timecommunication in multi-hop netwo
rks. In Proceedings of 11th conferenceon Distribut
ed Computer Systems,pages 300-307, IEEE,May 1991;F
loyd E.Ross. An overview of FDDI, The fiber distri
buted datainterface. IEEE Journal on Selected Area
s in Communications,7(7):1043-1051,September 1989;
K.C.Sevcik ancd M.J.Johnson. Cycle time properties
of the FDDItoken ting protocol. Technical Report
CSRI-179,Computer Science ReserchInstitute,Univers
ity of Toronto,1986;K.G.Shin and Qin Zheng. FDDI-M
:a scheme to doubule FDDI's ability of supporting
synchronous traffic. Patent pending;Alfred C.Weav
er. Local area networks and busses an analysis.Tec
hnical report,Flight Data Systems, NASA-Johnson Sp
ace Center,1986;Qin Zheng. Real-time Fault-tolera
nt Communication in ComputerNetworks. PhD thesis,U
niversity of Michigan,1993;Qin Zheng and Kang G.Sh
in.Fault-tolerant real-time communication in distr
ibuted computing systems. In Proc. 22nd Annual Int
ernationalSymposium on Fault-tolerant Computing,pa
ge 86-93 9992;Qin Zheng and Kang G.Shin. Real-time
communication in local area ring networks. In Pro
ceedings of Conference on Local Computer Networks,
pages 416-425,September 1992;Qin Zheng and Kang G.
Shin. On the ability of establishing real-time cha
nnels in point-to-point packet-switched networks.
IEEE Transactions on Communication (in press),199
3;Qin Zheng,Kang G.Shin,and Abram-Profeta. Transmi
ssion of compressed digital motion video over comp
uter networks. In Digest of COMPCONSpring'93,pages
37-46,February 1993.
【００１０】
【課題を解決するための手段】請求項１に係るトークン
リングネットワークの同期帯域幅割り当てシステムは、
多数のノードとネットワークマネジャを有するトークン
リングネットワークにおいて、上記トークンリングネッ
トワークに接続されたノードのいずれもが最悪の場合で
メッセージ送信を許される時間Γ(t)が、１つのノード
が上記トークンリングネットワークのメッセージ伝搬時
間制約条件を満足させる必要がある時間よりも小さくな
いように、最小同期帯域幅割り当てｈiを発生するため
の、上記ネットワークマネジャに結合されるように適合
された手段を備えるものである。
リングネットワークの同期帯域幅割り当てシステムは、
多数のノードとネットワークマネジャを有するトークン
リングネットワークにおいて、上記トークンリングネッ
トワークに接続されたノードのいずれもが最悪の場合で
メッセージ送信を許される時間Γ(t)が、１つのノード
が上記トークンリングネットワークのメッセージ伝搬時
間制約条件を満足させる必要がある時間よりも小さくな
いように、最小同期帯域幅割り当てｈiを発生するため
の、上記ネットワークマネジャに結合されるように適合
された手段を備えるものである。
【００１１】請求項２に係るトークンリングネットワー
クの同期帯域幅割り当てシステムは、上記最小同期帯域
幅割り当てｈiを、所定の式で表される上記時間Γ(t)
が、所定の式を満足するように発生する構成としたもの
である。
クの同期帯域幅割り当てシステムは、上記最小同期帯域
幅割り当てｈiを、所定の式で表される上記時間Γ(t)
が、所定の式を満足するように発生する構成としたもの
である。
【００１２】請求項３に係るトークンリングネットワー
クの同期帯域幅割り当てシステムは、所定の手順により
ノードｉについて最小同期帯域幅割り当てｈiを求める
構成としたものである。
クの同期帯域幅割り当てシステムは、所定の手順により
ノードｉについて最小同期帯域幅割り当てｈiを求める
構成としたものである。
【００１３】
【作用】請求項１の発明においては、上記ネットワーク
マネジャに結合されるように適合された手段が、上記ト
ークンリングネットワークに接続されたノードのいずれ
もが最悪の場合でメッセージ送信を許される時間Γ(t)
が、１つのノードが上記トークンリングネットワークの
メッセージ伝搬時間制約条件を満足させる必要がある時
間よりも小さくないように最小同期帯域幅割り当てｈi
を発生する。
マネジャに結合されるように適合された手段が、上記ト
ークンリングネットワークに接続されたノードのいずれ
もが最悪の場合でメッセージ送信を許される時間Γ(t)
が、１つのノードが上記トークンリングネットワークの
メッセージ伝搬時間制約条件を満足させる必要がある時
間よりも小さくないように最小同期帯域幅割り当てｈi
を発生する。
【００１４】請求項２の発明においては、上記最小同期
帯域幅割り当てｈiを、所定の式で表される上記時間Γ
(t)が、所定の式を満足するように発生する。
帯域幅割り当てｈiを、所定の式で表される上記時間Γ
(t)が、所定の式を満足するように発生する。
【００１５】請求項３の発明においては、所定のの手順
により、ノードｉについて最小同期帯域幅割り当てｈi
を求める。
により、ノードｉについて最小同期帯域幅割り当てｈi
を求める。
【００１６】
【実施例】以下、この発明について図を用いて説明す
る。図１は、ＦＤＤＩトークンリングネットワークにお
けるリアルタイム通信を実現する同期帯域幅割り当てを
行うためのシステムを表すブロックダイアグラムであ
る。
る。図１は、ＦＤＤＩトークンリングネットワークにお
けるリアルタイム通信を実現する同期帯域幅割り当てを
行うためのシステムを表すブロックダイアグラムであ
る。
【００１７】図１に関して、トークンリングネットワー
ク１０には種々のノードが結合されている。一般的に、
ノードは、互いに通信を行うリングにより相互に接続さ
れているコンピュータに関するものである。ノード１２
はある通信チャネルの目的ノードを表しているが、ノー
ド１４はデータを出力する供給元ノードを表している。
ネットワークマネジャ１８はノード間の同期帯域幅割り
当ての管理を行う。
ク１０には種々のノードが結合されている。一般的に、
ノードは、互いに通信を行うリングにより相互に接続さ
れているコンピュータに関するものである。ノード１２
はある通信チャネルの目的ノードを表しているが、ノー
ド１４はデータを出力する供給元ノードを表している。
ネットワークマネジャ１８はノード間の同期帯域幅割り
当ての管理を行う。
【００１８】１つの同期チャネルを開設するには、供給
元ノードはネットワークマネージャ１８へ同期帯域幅の
ある部分を要求しなければならない。この矢印２０によ
り表される要求はノード１４からネットワークマネジャ
１８へ送信される。ネットワークマネジャ１８は、矢印
２２により表されるように、ノード１４に応答する。要
求は、ノード１４が必要とする同期帯域幅割り当てｈi
を含む。ｈiは、いったんトークンを得たときにノード
１４が同期メッセージを送信するために許可される時間
である。全てのノードが要求する帯域幅の割り当ての合
計が、目標トークン巡回時間（target token rotation
time、以下「ＴＴＲＴ」と記す）を越えない場合のみ、
ネットワークマネジャ１８は要求を許可する。
元ノードはネットワークマネージャ１８へ同期帯域幅の
ある部分を要求しなければならない。この矢印２０によ
り表される要求はノード１４からネットワークマネジャ
１８へ送信される。ネットワークマネジャ１８は、矢印
２２により表されるように、ノード１４に応答する。要
求は、ノード１４が必要とする同期帯域幅割り当てｈi
を含む。ｈiは、いったんトークンを得たときにノード
１４が同期メッセージを送信するために許可される時間
である。全てのノードが要求する帯域幅の割り当ての合
計が、目標トークン巡回時間（target token rotation
time、以下「ＴＴＲＴ」と記す）を越えない場合のみ、
ネットワークマネジャ１８は要求を許可する。
【００１９】従来は、システムが、ネットワーク資源の
無駄を必然的に生じさせてしまう以上の時間ｈiを発生
していたので、わずかな同期チャネルしか適応できなか
った。このシステムでは、ｈi発生器２４がノード１４
に結合されており、同期帯域幅割り当て時間を最適な短
さあるいは最小にする。
無駄を必然的に生じさせてしまう以上の時間ｈiを発生
していたので、わずかな同期チャネルしか適応できなか
った。このシステムでは、ｈi発生器２４がノード１４
に結合されており、同期帯域幅割り当て時間を最適な短
さあるいは最小にする。
【００２０】後に説明するように、ｈiの計算におい
て、ｈiが、最悪の場合においてノードがメッセージの
送信を許可された時間が、ノードがメッセージ伝搬時間
制約条件を厳格に満足する必要がある時間よりも小さく
ならないことを保証にすることにより、ｈiが最小にな
る。
て、ｈiが、最悪の場合においてノードがメッセージの
送信を許可された時間が、ノードがメッセージ伝搬時間
制約条件を厳格に満足する必要がある時間よりも小さく
ならないことを保証にすることにより、ｈiが最小にな
る。
【００２１】以下に示す最小のｈiを与えるアルゴリズ
ムは、リアルタイムチャネルを確立するために必要であ
る。一実施例においては、
ムは、リアルタイムチャネルを確立するために必要であ
る。一実施例においては、
【００２２】
【数４】
【００２３】さらなる説明として、ファイバ分配データ
インタフェース（ＦＤＤＩ）は光ファイバ媒体を使用す
る１００Ｍｂｐｓトークンリングネットワークのための
ＡＮＳＩの標準である。高い送信スピードによって、Ｆ
ＤＤＩは、現在の低速のイーサネット及びＩＥＥＥ８０
２．５トークンリングの帯域幅が飽和するという問題を
緩和する。さらに、このＦＤＤＩの同期送信容量は、デ
ジタルビデオ／オーディオ送信や分散制御／監視のよう
なリアルタイムアプリケーションの実現を可能にする。
インタフェース（ＦＤＤＩ）は光ファイバ媒体を使用す
る１００Ｍｂｐｓトークンリングネットワークのための
ＡＮＳＩの標準である。高い送信スピードによって、Ｆ
ＤＤＩは、現在の低速のイーサネット及びＩＥＥＥ８０
２．５トークンリングの帯域幅が飽和するという問題を
緩和する。さらに、このＦＤＤＩの同期送信容量は、デ
ジタルビデオ／オーディオ送信や分散制御／監視のよう
なリアルタイムアプリケーションの実現を可能にする。
【００２４】このＦＤＤＩの同期送信容量は２つの保証
の形態、すなわち、媒体アクセス遅延時間の制限及び同
期通信に対する最小のスループットという形でそれぞれ
のノードに提供される。特に、ＦＤＤＩネットワークの
目標トークン巡回時間がＴＴＲＴに設定され、ノードｉ
の同期帯域幅割り当てがｈiであれば、ノードｉが同期
メッセージを送信する機会の待時間は、２×ＴＴＲＴで
制限され、平均的して、同期メッセージを送信するため
に帯域幅ｈi／ＴＴＲＴ×１００Ｍｂｐｓをもつことが
保証される。これら２つの性質により、ＦＤＤＩは同期
通信を行うことができるが、これらだけではリアルタイ
ムアプリケーションには十分でない。
の形態、すなわち、媒体アクセス遅延時間の制限及び同
期通信に対する最小のスループットという形でそれぞれ
のノードに提供される。特に、ＦＤＤＩネットワークの
目標トークン巡回時間がＴＴＲＴに設定され、ノードｉ
の同期帯域幅割り当てがｈiであれば、ノードｉが同期
メッセージを送信する機会の待時間は、２×ＴＴＲＴで
制限され、平均的して、同期メッセージを送信するため
に帯域幅ｈi／ＴＴＲＴ×１００Ｍｂｐｓをもつことが
保証される。これら２つの性質により、ＦＤＤＩは同期
通信を行うことができるが、これらだけではリアルタイ
ムアプリケーションには十分でない。
【００２５】リアルタイムアプリケーションでは、通
常、予め定められたメッセージ発生率で、適宜、メッセ
ージのそれぞれが伝搬される必要がある。しかし、ＦＤ
ＤＩネットワークはスループット及び遅延時間の制限を
別々に保証している。あるノードが保証されたｈi／Ｔ
ＴＲＴ×１００Ｍｂｐｓのスループットレートで同期メ
ッセージを送信するとき、メッセージの全てが、遅延時
間の制限２×ＴＴＲＴを有するであろうとの保証はされ
ない。この問題をさらに理解するために、以下に示すビ
デオチャネルについて検討する。１）チャネルのソース
はＴ単位ごとの時間にビデオフレームを発生する。完全
な動画像ビデオに対して、Ｔ＝３３ｍｓである。２）送
信レート１００Ｍｂｐｓで最大サイズのビデオフレーム
を送信するために必要な時間は、Ｃ単位時間である。
３）目的端末で滑らかなリアルタイムビデオを提供する
ためには、それぞれのフレームは、その発生後ｄ単位時
間内に目的端末に供給される必要がある。我々は、この
例においてｄ＝Ｔと仮定する。
常、予め定められたメッセージ発生率で、適宜、メッセ
ージのそれぞれが伝搬される必要がある。しかし、ＦＤ
ＤＩネットワークはスループット及び遅延時間の制限を
別々に保証している。あるノードが保証されたｈi／Ｔ
ＴＲＴ×１００Ｍｂｐｓのスループットレートで同期メ
ッセージを送信するとき、メッセージの全てが、遅延時
間の制限２×ＴＴＲＴを有するであろうとの保証はされ
ない。この問題をさらに理解するために、以下に示すビ
デオチャネルについて検討する。１）チャネルのソース
はＴ単位ごとの時間にビデオフレームを発生する。完全
な動画像ビデオに対して、Ｔ＝３３ｍｓである。２）送
信レート１００Ｍｂｐｓで最大サイズのビデオフレーム
を送信するために必要な時間は、Ｃ単位時間である。
３）目的端末で滑らかなリアルタイムビデオを提供する
ためには、それぞれのフレームは、その発生後ｄ単位時
間内に目的端末に供給される必要がある。我々は、この
例においてｄ＝Ｔと仮定する。
【００２６】上記に示したパラメータにより、ビデオチ
ャネルについての最大通信トラヒックはＣ／Ｔ×１００
Ｍｂｐｓとなる。したがって、ｈi／ＴＴＲＴ＝Ｃ／Ｔ
であるようにＦＤＤＩが構成されれば、スループットの
要求は満足させられる。２×ＴＴＲＴ＝Ｔであれば、遅
延時間の供給もまた満足させられる。両者から、我々は
ｈi＝Ｃ／２を得る。ＦＤＤＩの媒体アクセス制御（Ｍ
ＡＣ）プロトコルから、ｈiは、いったんトークンを捕
まえてから送信する同期メッセージに対して許されてい
るノードｉの最大時間である。したがって、ｈi＝Ｃ／
２は、最大サイズのビデオフレームが送信を完了するた
めに２つのトークンの到来が必要であることを暗示して
いる。ＴＴＲＴはＴ／２にセットされているから、１つ
のトークンの巡回時間はＴと同程度の長さであり、最大
サイズフレームは、最悪の場合、遅延時間の制限Ｔ内に
送信されない。
ャネルについての最大通信トラヒックはＣ／Ｔ×１００
Ｍｂｐｓとなる。したがって、ｈi／ＴＴＲＴ＝Ｃ／Ｔ
であるようにＦＤＤＩが構成されれば、スループットの
要求は満足させられる。２×ＴＴＲＴ＝Ｔであれば、遅
延時間の供給もまた満足させられる。両者から、我々は
ｈi＝Ｃ／２を得る。ＦＤＤＩの媒体アクセス制御（Ｍ
ＡＣ）プロトコルから、ｈiは、いったんトークンを捕
まえてから送信する同期メッセージに対して許されてい
るノードｉの最大時間である。したがって、ｈi＝Ｃ／
２は、最大サイズのビデオフレームが送信を完了するた
めに２つのトークンの到来が必要であることを暗示して
いる。ＴＴＲＴはＴ／２にセットされているから、１つ
のトークンの巡回時間はＴと同程度の長さであり、最大
サイズフレームは、最悪の場合、遅延時間の制限Ｔ内に
送信されない。
【００２７】上記の問題を解決するため、媒体アクセス
遅延時間制限を少なくするように小さなＴＴＲＴを用い
るか、端末に割り当てられている同期帯域幅を増加する
ように大きいｈiを用いるかのいずれかを行うことがで
きる。最初の方法はいくつかの理由のため非常に望まし
いわけではない。第１に、ＴＴＲＴは、通常は、リング
初期化時間においてセットされる。アプリケーションが
作り出されているときにＴＴＲＴを変更すると不都合が
生じる。第２に、ＴＴＲＴが小さくなりすぎるとトーク
ンパッシングオーバーヘッドが生じること及びリング潜
在（latency）のために、リング全体の能力が低下す
る。第３に、ＴＴＲＴが減少すると、端末に割り当てら
れている同期帯域幅が増加する。この発明は第２の方
法、例えば同期帯域幅を増加させることに関するもので
ある。上記の問題は、同期帯域幅割り当て（synchronou
s bandwidth allocation、ＳＢＡ）システムを発展させ
ることにより解決される。同期帯域幅割り当てシステム
は、ネットワーク目標トークン巡回時間ＴＴＲＴ及びア
プリケーションのトラヒック仕様が与えられたとき、要
求遅延時間制限内で全てのメッセージが送信されること
が保証されるように、ノードの同期帯域幅割り当てｈi
を決定する。ＦＤＤＩの端末管理標準ＳＭＴ７．２は、
同期帯域幅割り当て（ＳＢＡ）手段を記述している。こ
れは１つのノードに割り当てられる同期帯域幅がどの程
度であるかを示唆するが、どれだけの同期帯域幅が特定
のアプリケーションに対して割り当てられる必要がある
のかについて開示していない。明らかに、同期トラヒッ
クを扱うＦＤＤＩの容量は、適当なＳＢＡシステムなし
には効果的に使用され得ない。
遅延時間制限を少なくするように小さなＴＴＲＴを用い
るか、端末に割り当てられている同期帯域幅を増加する
ように大きいｈiを用いるかのいずれかを行うことがで
きる。最初の方法はいくつかの理由のため非常に望まし
いわけではない。第１に、ＴＴＲＴは、通常は、リング
初期化時間においてセットされる。アプリケーションが
作り出されているときにＴＴＲＴを変更すると不都合が
生じる。第２に、ＴＴＲＴが小さくなりすぎるとトーク
ンパッシングオーバーヘッドが生じること及びリング潜
在（latency）のために、リング全体の能力が低下す
る。第３に、ＴＴＲＴが減少すると、端末に割り当てら
れている同期帯域幅が増加する。この発明は第２の方
法、例えば同期帯域幅を増加させることに関するもので
ある。上記の問題は、同期帯域幅割り当て（synchronou
s bandwidth allocation、ＳＢＡ）システムを発展させ
ることにより解決される。同期帯域幅割り当てシステム
は、ネットワーク目標トークン巡回時間ＴＴＲＴ及びア
プリケーションのトラヒック仕様が与えられたとき、要
求遅延時間制限内で全てのメッセージが送信されること
が保証されるように、ノードの同期帯域幅割り当てｈi
を決定する。ＦＤＤＩの端末管理標準ＳＭＴ７．２は、
同期帯域幅割り当て（ＳＢＡ）手段を記述している。こ
れは１つのノードに割り当てられる同期帯域幅がどの程
度であるかを示唆するが、どれだけの同期帯域幅が特定
のアプリケーションに対して割り当てられる必要がある
のかについて開示していない。明らかに、同期トラヒッ
クを扱うＦＤＤＩの容量は、適当なＳＢＡシステムなし
には効果的に使用され得ない。
【００２８】近年、ＳＢＡ構成についての研究の関心が
高まりつつあった。Agrawalその他は、リング帯域のわ
ずか３３％にすぎない合計のピーク信号率で同期チャネ
ルのいかなる組み合わせも扱うことができると証明され
た、標準化された均衡のとれたＳＢＡ構成を提案した。
しかし、この構成には以下に示す問題がある。第１に、
要求メッセージ遅延時間制限ｄがメッセージ発生周期Ｔ
に等しいアプリケーションに対してのみ使用することが
できる。このことは、扱うことのできるネットワークの
アプリケーションのタイプを制限することになる。第２
に、この構成はアプリケーションに割り当てられた同期
帯域幅は必要最小なものではないという意味で最適では
なく、したがってネットワークが扱うことのできる同期
トラヒックの量が減少する。第３に、グローバルＳＢＡ
構成では、１つのノードへの同期帯域幅の割り当て／割
り当て解除は、全ての他のノードに対して予め割り当て
られた同期帯域幅を変更することを要求する。グローバ
ルなＳＢＡ構成によると、同期帯域幅割り当ての実行が
複雑になる。
高まりつつあった。Agrawalその他は、リング帯域のわ
ずか３３％にすぎない合計のピーク信号率で同期チャネ
ルのいかなる組み合わせも扱うことができると証明され
た、標準化された均衡のとれたＳＢＡ構成を提案した。
しかし、この構成には以下に示す問題がある。第１に、
要求メッセージ遅延時間制限ｄがメッセージ発生周期Ｔ
に等しいアプリケーションに対してのみ使用することが
できる。このことは、扱うことのできるネットワークの
アプリケーションのタイプを制限することになる。第２
に、この構成はアプリケーションに割り当てられた同期
帯域幅は必要最小なものではないという意味で最適では
なく、したがってネットワークが扱うことのできる同期
トラヒックの量が減少する。第３に、グローバルＳＢＡ
構成では、１つのノードへの同期帯域幅の割り当て／割
り当て解除は、全ての他のノードに対して予め割り当て
られた同期帯域幅を変更することを要求する。グローバ
ルなＳＢＡ構成によると、同期帯域幅割り当ての実行が
複雑になる。
【００２９】Agrawalの構成の改良として、Chenその他
は、前述した文献において記載したように最適なＳＢＡ
構成を提案した。しかし、かれらの構成はなお同じｄ＝
Ｔの制限を受けるとともに、グローバルな構成である。
さらに、それは最適な帯域幅の計算のために繰り返しア
ルゴリズムを使用しており、理論上、収束させるために
無限のステップを必要とする。
は、前述した文献において記載したように最適なＳＢＡ
構成を提案した。しかし、かれらの構成はなお同じｄ＝
Ｔの制限を受けるとともに、グローバルな構成である。
さらに、それは最適な帯域幅の計算のために繰り返しア
ルゴリズムを使用しており、理論上、収束させるために
無限のステップを必要とする。
【００３０】この発明では、ＳＢＡシステムはｄ＝Ｔで
あること要求せず、ほとんどの場合において最適にな
る。最適帯域幅の計算は、ただ１つのステップでなし得
る。さらに、１つのノードに対する同期帯域幅の割り当
て／割り当て解除は、他のノードに対して同期帯域幅の
割り当ての変更を要求しない。したがって、同期帯域幅
割り当ての実行が容易になる。
あること要求せず、ほとんどの場合において最適にな
る。最適帯域幅の計算は、ただ１つのステップでなし得
る。さらに、１つのノードに対する同期帯域幅の割り当
て／割り当て解除は、他のノードに対して同期帯域幅の
割り当ての変更を要求しない。したがって、同期帯域幅
割り当ての実行が容易になる。
【００３１】以下の説明のために、ＦＤＤＩのＭＡＣプ
ロトコルのレビュー及び関係のある性質を示す。
ロトコルのレビュー及び関係のある性質を示す。
【００３２】プロトコル１（ＦＤＤＩのＭＡＣ） Ｐ１：０からＮ−１まで番号が付けられたＮ個のアクテ
ィブなノードがリングにあるとする。ＦＤＤＩリング初
期化処理の一部として、それぞれのノードは目標トーク
ン巡回時間（ＴＴＲＴ）を宣言する。それらのうちの最
小のものがリングのＴＴＲＴとして選択されている。同
期トラヒックを取り扱うそれぞれのノードは、同期メッ
セージを送信するためにＴＴＲＴの一部に割り当てられ
ている。同期帯域幅割り当てと呼ばれるｈiで、ノード
ｉが同期メッセージを送信するために割り当てられたＴ
ＴＲＴの一部を示すものとする。
ィブなノードがリングにあるとする。ＦＤＤＩリング初
期化処理の一部として、それぞれのノードは目標トーク
ン巡回時間（ＴＴＲＴ）を宣言する。それらのうちの最
小のものがリングのＴＴＲＴとして選択されている。同
期トラヒックを取り扱うそれぞれのノードは、同期メッ
セージを送信するためにＴＴＲＴの一部に割り当てられ
ている。同期帯域幅割り当てと呼ばれるｈiで、ノード
ｉが同期メッセージを送信するために割り当てられたＴ
ＴＲＴの一部を示すものとする。
【００３３】Ｐ２：それぞれのノードは２つの内部タイ
マを有する。すなわち、トークン巡回タイマ（ＴＲＴ）
とトークン保持タイマ（ＴＨＴ）である。ＴＲＴは常に
カウントアップし、ノードのＴＨＴは、ノードが同期メ
ッセージを送信しているときのみカウントアップする。
もし、トークンがノードに達する前にそのノードのＴＲ
ＴがＴＴＲＴになったときは、ＴＲＴは０にリセットさ
れ、トークンはノードの遅延カウントＬCを１だけ増加
することにより遅延の印がつけられる。異なるノードに
おけるタイマの初期化のために、リング初期化の後に最
初のトークンの巡回中においていかなるメッセージの送
信も許されず、ＬCは０にセットされる。
マを有する。すなわち、トークン巡回タイマ（ＴＲＴ）
とトークン保持タイマ（ＴＨＴ）である。ＴＲＴは常に
カウントアップし、ノードのＴＨＴは、ノードが同期メ
ッセージを送信しているときのみカウントアップする。
もし、トークンがノードに達する前にそのノードのＴＲ
ＴがＴＴＲＴになったときは、ＴＲＴは０にリセットさ
れ、トークンはノードの遅延カウントＬCを１だけ増加
することにより遅延の印がつけられる。異なるノードに
おけるタイマの初期化のために、リング初期化の後に最
初のトークンの巡回中においていかなるメッセージの送
信も許されず、ＬCは０にセットされる。
【００３４】Ｐ３：トークンをもつノードだけがメッセ
ージを送信する資格をもつ。メッセージ送信時間はノー
ドのタイマにより制御されるが、処理中のメッセージ送
信は、それが完了するまで中断されることはない。ノー
ドｉがトークンを受信するとき、このノードは以下に示
す処理を行う。
ージを送信する資格をもつ。メッセージ送信時間はノー
ドのタイマにより制御されるが、処理中のメッセージ送
信は、それが完了するまで中断されることはない。ノー
ドｉがトークンを受信するとき、このノードは以下に示
す処理を行う。
【００３５】Ｐ３．１：ＬC＞０ なら ＬC＝ＬC−１
及び ＴＨＴ＝ＴＴＲＴとする。それ以外なら ＴＨ
Ｔ＝ＴＲＴ 及びＴＲＴ＝０ とする。
及び ＴＨＴ＝ＴＴＲＴとする。それ以外なら ＴＨ
Ｔ＝ＴＲＴ 及びＴＲＴ＝０ とする。
【００３６】Ｐ３．２：ノードｉが同期メッセージをも
つとき、ノードｉは、この同期メッセージをｈiに達す
るまでの時間、あるいは全ての同期メッセージが送信さ
れるまでのいずれかの条件が満たされるまでの間に送信
する（標準においてはそうでないが、我々はネットワー
クの同期性能の向上及び解析の単純化のためにノードは
同期トラヒックを常に最初に送信すると仮定する。）
つとき、ノードｉは、この同期メッセージをｈiに達す
るまでの時間、あるいは全ての同期メッセージが送信さ
れるまでのいずれかの条件が満たされるまでの間に送信
する（標準においてはそうでないが、我々はネットワー
クの同期性能の向上及び解析の単純化のためにノードは
同期トラヒックを常に最初に送信すると仮定する。）
【００３７】Ｐ３．３：ノードｉが非同期メッセージを
もつとき、ノードｉは、ＴＨＴのカウントがＴＴＲＴに
達するまで、あるいは全ての非同期メッセージが送信さ
れるまでのいずれかの条件が満たされるまでに送信され
る。 Ｐ３．４：ノードｉはトークンを次のノード（ｉ＋１）
ｍｏｄＮにパスする。
もつとき、ノードｉは、ＴＨＴのカウントがＴＴＲＴに
達するまで、あるいは全ての非同期メッセージが送信さ
れるまでのいずれかの条件が満たされるまでに送信され
る。 Ｐ３．４：ノードｉはトークンを次のノード（ｉ＋１）
ｍｏｄＮにパスする。
【００３８】Ｔringでリングの待ち時間とトークン通過
オーバーヘッドとを加えた時間を表す。これは、いかな
るメッセージを送信することなくトークンをリングに沿
って一回巡回させるために必要な時間である。そして、
Ｔpで最大サイズの非同期メッセージを送信するために
必要な時間を表す。このとき、ＦＤＤＩのＭＡＣプロト
コルのパラメータは下記のプロトコル制約条件を満足し
なければならない。
オーバーヘッドとを加えた時間を表す。これは、いかな
るメッセージを送信することなくトークンをリングに沿
って一回巡回させるために必要な時間である。そして、
Ｔpで最大サイズの非同期メッセージを送信するために
必要な時間を表す。このとき、ＦＤＤＩのＭＡＣプロト
コルのパラメータは下記のプロトコル制約条件を満足し
なければならない。
【００３９】
【数５】
【００４０】上記の不等式の物理的な意味は、ネットワ
ークのノードについて割り当てられている同期帯域幅の
総和は実効的なリング帯域幅を越えないということであ
る。この制約条件に違反すると、リングが不安定にな
り、”要求(claiming)”と”動作(operational)”との
間で振動する。このプロトコル制約条件の下で、ＦＤＤ
Ｉに関する良く知られた事実として、最悪の場合のトー
クン巡回時間が２×ＴＴＲＴで制限されること、及び平
均トークン巡回時間がＴＴＲＴで制限されるということ
がある。さらに一般的な結果が、Agrawalその他により
下記に述べるように得られた。
ークのノードについて割り当てられている同期帯域幅の
総和は実効的なリング帯域幅を越えないということであ
る。この制約条件に違反すると、リングが不安定にな
り、”要求(claiming)”と”動作(operational)”との
間で振動する。このプロトコル制約条件の下で、ＦＤＤ
Ｉに関する良く知られた事実として、最悪の場合のトー
クン巡回時間が２×ＴＴＲＴで制限されること、及び平
均トークン巡回時間がＴＴＲＴで制限されるということ
がある。さらに一般的な結果が、Agrawalその他により
下記に述べるように得られた。
【００４１】補助定理１（最悪の場合のトークン巡回時
間） （１）式のプロトコル制約条件の下で、ノードｉへの全
てのｎ連続するトークンの訪問の間の経過時間は、ｎ×
ＴＴＲＴ−ｈiで制限される。ノードｉがいったんトー
クンを得ると、同期メッセージの送信は、ｈi単位の時
間になされる。以下に示す補助定理は、ノードｉが時間
ｔの間に同期メッセージを送信することが許可される、
時間の下限を与える。
間） （１）式のプロトコル制約条件の下で、ノードｉへの全
てのｎ連続するトークンの訪問の間の経過時間は、ｎ×
ＴＴＲＴ−ｈiで制限される。ノードｉがいったんトー
クンを得ると、同期メッセージの送信は、ｈi単位の時
間になされる。以下に示す補助定理は、ノードｉが時間
ｔの間に同期メッセージを送信することが許可される、
時間の下限を与える。
【００４２】補助定理２（同期送信時間） ＦＤＤＩの（１）式のプロトコル制約条件の下で、ノー
ドｉは、少なくとも、時間ｔの間に同期メッセージを送
信するための
ドｉは、少なくとも、時間ｔの間に同期メッセージを送
信するための
【００４３】
【数６】
【００４４】単位の時間をもつ。
【００４５】
【数７】
【００４６】となったとき、下限に達する。
【００４７】補助定理１及び２は、今日までＦＤＤＩの
最良の公表された同期特性である。このシステムは新し
いＳＢＡシステムを導き出すことのできる補助定理２の
改良に関するものである。
最良の公表された同期特性である。このシステムは新し
いＳＢＡシステムを導き出すことのできる補助定理２の
改良に関するものである。
【００４８】前に議論したように、リアルタイム通信の
重要な特徴は、それぞれのメッセージが予め定められた
遅延時間の制限内で目的端末に伝搬されなければならな
いことである。制限されたネットワーク送信帯域幅のた
め、この要求は、メッセージ発生特性についての何等か
の情報なしには満足させられなかった。
重要な特徴は、それぞれのメッセージが予め定められた
遅延時間の制限内で目的端末に伝搬されなければならな
いことである。制限されたネットワーク送信帯域幅のた
め、この要求は、メッセージ発生特性についての何等か
の情報なしには満足させられなかった。
【００４９】このシステムにおいて、ＴとＣの２つのパ
ラメータがメッセージ発生パターンを記述するために用
いられる。ここで、Ｔは最小メッセージ発生間時間、Ｃ
は最大メッセージ送信時間（すなわち、最大サイズのメ
ッセージを送信するために必要な時間）。繰り返し音声
／ビデオ送信及びリアルタイム制御／監視のような、多
くのリアルタイムのアプリケーションに対するパラメー
タの従来の知識を仮定するのが合理的である。トラヒッ
クパターンがほとんど予測できないアプリケーションに
対して、ＴとＣについての見積もられた値が用いられ
る。ある処理が予め定められたメッセージサイズを越え
ること、及び／又は予め定められた遅延時間制限の内に
メッセージが供給されないという危険が生じるメッセー
ジ発生率を越えることがあるかもしれない。しかし、こ
の特別な処理は他のアプリケーションの保証に影響を及
ぼすことはない。
ラメータがメッセージ発生パターンを記述するために用
いられる。ここで、Ｔは最小メッセージ発生間時間、Ｃ
は最大メッセージ送信時間（すなわち、最大サイズのメ
ッセージを送信するために必要な時間）。繰り返し音声
／ビデオ送信及びリアルタイム制御／監視のような、多
くのリアルタイムのアプリケーションに対するパラメー
タの従来の知識を仮定するのが合理的である。トラヒッ
クパターンがほとんど予測できないアプリケーションに
対して、ＴとＣについての見積もられた値が用いられ
る。ある処理が予め定められたメッセージサイズを越え
ること、及び／又は予め定められた遅延時間制限の内に
メッセージが供給されないという危険が生じるメッセー
ジ発生率を越えることがあるかもしれない。しかし、こ
の特別な処理は他のアプリケーションの保証に影響を及
ぼすことはない。
【００５０】要求されたメッセージ伝搬遅延時間制限ｄ
と供給元のノードｉのアドレスとともに、リアルタイム
通信に対するリアルタイムチャネルの概念が用いられ
る。リアルタイムチャネルは４つの組み変数でτ＝
（Ｔ，Ｃ，ｄ，ｉ）で表される。これは、それぞれの供
給元のノードｓで発生したメッセージが、メッセージ発
生間時間がＴ以上であり、かつ、メッセージ送信時間が
Ｃ以下である間は、ｄ以下の時間で、１又はそれ以上の
ノードに連続的に供給されることを保証する。
と供給元のノードｉのアドレスとともに、リアルタイム
通信に対するリアルタイムチャネルの概念が用いられ
る。リアルタイムチャネルは４つの組み変数でτ＝
（Ｔ，Ｃ，ｄ，ｉ）で表される。これは、それぞれの供
給元のノードｓで発生したメッセージが、メッセージ発
生間時間がＴ以上であり、かつ、メッセージ送信時間が
Ｃ以下である間は、ｄ以下の時間で、１又はそれ以上の
ノードに連続的に供給されることを保証する。
【００５１】リアルタイムチャネルはリアルタイム通信
を実現する便利な手段である。ユーザーは、自身のアプ
リケーションのために適当な帯域幅及び遅延時間制限を
もつチャネルを用意することができる。このことは、ユ
ーザーが帯域幅及び回路の品質についての選択すること
がほとんどできない従来の回路切換送信に対して、きわ
だった対照をなす。この発明はＦＤＤＩネットーワーク
におけるリアルタイムチャネルを実現することを扱うも
のである。
を実現する便利な手段である。ユーザーは、自身のアプ
リケーションのために適当な帯域幅及び遅延時間制限を
もつチャネルを用意することができる。このことは、ユ
ーザーが帯域幅及び回路の品質についての選択すること
がほとんどできない従来の回路切換送信に対して、きわ
だった対照をなす。この発明はＦＤＤＩネットーワーク
におけるリアルタイムチャネルを実現することを扱うも
のである。
【００５２】リアルタイムチャネルの組みは、それぞれ
のチャネルの要求されているメッセージの伝搬遅延時間
制限が、適切なＦＤＤＩのＭＡＣプロトコルのパラメー
タ設定により保証され得るならば、ＦＤＤＩネットワー
クにおいて確立され得ると言われている。プロコトル１
から、ユーザーが調整できるパラメータはＴＴＲＴとｈ
iである。ＴＴＲＴは通常ネットワークの初期化時間で
設定され、度々変更できない。ネットワークが保証でき
るということより、最小メッセージ遅延時間制限ｄmin
＝２×ＴＴＲＴが決まる。ｄminより小さい遅延時間制
限を伴ういかなるチャネル要求も拒絶される。与えられ
たＴＴＲＴにより、ノードｉに割り当てられた同期帯域
幅はｈiの値により決定される。このように、ＳＢＡ構
成はリアルタイムチャネルを適応させるようにｈiの値
を決定する。ＳＢＡ構成は、チャネルの要求された遅延
時間制限を保証するならば、リアルタイムチャネルの組
みに関して可能であると言われている。ＳＢＡ構成は、
可能なＳＢＡ構成が存在するときに、それが常に可能で
あるならば最適であると言われている。最適なＳＢＡ構
成の利点は、最適なＳＢＡにより拒絶されるリアルタイ
ムチャネルの組みは他のいかなるＳＢＡ構成でも確立さ
れ得ないから、ＦＤＤＩの同期送信能力の完全な利用で
ある。
のチャネルの要求されているメッセージの伝搬遅延時間
制限が、適切なＦＤＤＩのＭＡＣプロトコルのパラメー
タ設定により保証され得るならば、ＦＤＤＩネットワー
クにおいて確立され得ると言われている。プロコトル１
から、ユーザーが調整できるパラメータはＴＴＲＴとｈ
iである。ＴＴＲＴは通常ネットワークの初期化時間で
設定され、度々変更できない。ネットワークが保証でき
るということより、最小メッセージ遅延時間制限ｄmin
＝２×ＴＴＲＴが決まる。ｄminより小さい遅延時間制
限を伴ういかなるチャネル要求も拒絶される。与えられ
たＴＴＲＴにより、ノードｉに割り当てられた同期帯域
幅はｈiの値により決定される。このように、ＳＢＡ構
成はリアルタイムチャネルを適応させるようにｈiの値
を決定する。ＳＢＡ構成は、チャネルの要求された遅延
時間制限を保証するならば、リアルタイムチャネルの組
みに関して可能であると言われている。ＳＢＡ構成は、
可能なＳＢＡ構成が存在するときに、それが常に可能で
あるならば最適であると言われている。最適なＳＢＡ構
成の利点は、最適なＳＢＡにより拒絶されるリアルタイ
ムチャネルの組みは他のいかなるＳＢＡ構成でも確立さ
れ得ないから、ＦＤＤＩの同期送信能力の完全な利用で
ある。
【００５３】ＦＤＤＩネットワークについてのリアルタ
イムチャネルを確立するための条件をこれから導く。こ
れらの条件から、新しいＳＢＡシステムを開発すること
ができる。
イムチャネルを確立するための条件をこれから導く。こ
れらの条件から、新しいＳＢＡシステムを開発すること
ができる。
【００５４】Γ(t)で、最悪の場合の１つのノードが期
間ｔにおいて同期メッセージを送信することが許された
時間を表す。補助定理２からノードｉに対するΓ(t)の
下限値が得られる。我々は、以下に示すように、正確な
Γ(t)の値を計算することにより補助定理２を改良す
る。
間ｔにおいて同期メッセージを送信することが許された
時間を表す。補助定理２からノードｉに対するΓ(t)の
下限値が得られる。我々は、以下に示すように、正確な
Γ(t)の値を計算することにより補助定理２を改良す
る。
【００５５】補助定理３（最悪の場合の同期送信時間）
ＦＤＤＩのプロトコル制約条件（１）の下で、最悪の場
合のノードｉは
ＦＤＤＩのプロトコル制約条件（１）の下で、最悪の場
合のノードｉは
【００５６】
【数８】
【００５７】期間ｔにおいて同期メッセージを送信する
時間単位をもつ。ここで、δ(t)は次のように計算され
る。
時間単位をもつ。ここで、δ(t)は次のように計算され
る。
【００５８】
【数９】
【００５９】２つのリアルタイムチャネルが同じ送信元
のノードをもたず、ノードの同期送信時間がリアルタイ
ムチャネルメッセージのみに使用されるものとする。こ
のとき、補助定理２から、我々は、ＦＤＤＩネットワー
クについてリアルタイムチャネルの確立のために必要か
つ十分な下記の条件を得る。
のノードをもたず、ノードの同期送信時間がリアルタイ
ムチャネルメッセージのみに使用されるものとする。こ
のとき、補助定理２から、我々は、ＦＤＤＩネットワー
クについてリアルタイムチャネルの確立のために必要か
つ十分な下記の条件を得る。
【００６０】定理１（ＦＤＤＩについてのチャネル確立
条件） リアルタイムチャネルτ＝（Ｔ，Ｃ，ｄ，ｉ）は、プロ
トコル制約条件（１）の下、次の条件を満たすときには
及び満たすときのみＦＤＤＩネットワークについて確立
され得る。
条件） リアルタイムチャネルτ＝（Ｔ，Ｃ，ｄ，ｉ）は、プロ
トコル制約条件（１）の下、次の条件を満たすときには
及び満たすときのみＦＤＤＩネットワークについて確立
され得る。
【００６１】
【数１０】
【００６２】ここでΓ(t)は、ｉ＝ｓとして補助定理３
から計算される。そして、
から計算される。そして、
【００６３】
【数１１】
【００６４】である。
【００６５】不等式（２）は無限の長さの間隔でチェッ
クされなければならないから、定理１からリアルタイム
チャネルに必要とされる最小の同期帯域幅割り当て（す
なわちｈi）の計算は困難である。幸いにも、以下に示
す定理により、ほとんどの場合で要求される最小の同期
帯域幅割り当て（すなわち、２×ＴＴＲＴ≦ｄ≦Ｔ＋Ｔ
ＴＲＴ または ｄ≧Ｔ＋２×ＴＴＲＴ のとき）及び
他の場合に対するｈiの上限を容易に計算することがで
きる。
クされなければならないから、定理１からリアルタイム
チャネルに必要とされる最小の同期帯域幅割り当て（す
なわちｈi）の計算は困難である。幸いにも、以下に示
す定理により、ほとんどの場合で要求される最小の同期
帯域幅割り当て（すなわち、２×ＴＴＲＴ≦ｄ≦Ｔ＋Ｔ
ＴＲＴ または ｄ≧Ｔ＋２×ＴＴＲＴ のとき）及び
他の場合に対するｈiの上限を容易に計算することがで
きる。
【００６６】定理２（ｈｉの計算）リアルタイムチャネ
ル（Ｔ，Ｃ，ｄ，ｉ）を確立するために要求される最小
のｈiは次のように計算される。
ル（Ｔ，Ｃ，ｄ，ｉ）を確立するために要求される最小
のｈiは次のように計算される。
【００６７】
【数１２】
【００６８】定理２から、我々は次のようなチャネル確
立アルゴリズムを得ることができる。
立アルゴリズムを得ることができる。
【００６９】アルゴリズム１（ＦＤＤＩについてのチャ
ネル確立） ｎ−１個のリアルタイムチャネルτi＝（Ｔi，Ｃi，
ｄi，ｓi）、ｉ＝１，・・・，ｎ−１が、すでにＦＤＤ
Ｉリングについて確立されているとする。このとき新し
いチャネルτn＝（Ｔn，Ｃn，ｄn，ｉ）は次に示すステ
ップで確立される。
ネル確立） ｎ−１個のリアルタイムチャネルτi＝（Ｔi，Ｃi，
ｄi，ｓi）、ｉ＝１，・・・，ｎ−１が、すでにＦＤＤ
Ｉリングについて確立されているとする。このとき新し
いチャネルτn＝（Ｔn，Ｃn，ｄn，ｉ）は次に示すステ
ップで確立される。
【００７０】ステップ１：定理２からｈiを計算する。 ステップ２：プロトコル制約条件（１）が満足されてい
るとき、ｉの同期帯域幅割り当てをｈiに設定し、チャ
ネルτnを確立する。そうでないときは、チャネル確立
要求は拒絶される。
るとき、ｉの同期帯域幅割り当てをｈiに設定し、チャ
ネルτnを確立する。そうでないときは、チャネル確立
要求は拒絶される。
【００７１】上記のアルゴリズムに関して、Ｔ＋ＴＴＲ
Ｔ＜ｄ＜Ｔ＋２×ＴＴＲＴに対して、定理２により最小
のｈiの上限のみが得られる。この上限がいかにぴった
りしているかを知るために、ＦＤＤＩネットワークにつ
いてのリアルタイムチャネルの確立のための必要な条件
が、割り当てられた同期帯域幅（ｈi／ＴＴＲＴ×１０
０Ｍｂｐｓ）がチャネルについての運ばれるべき期待信
号帯域幅（Ｃ／Ｔ×１００Ｍｂｐｓ）よりも小さくては
ならないことを注意しておく。これは、ｈi≧（ＴＴＲ
Ｔ／Ｔ）Ｃが必要条件であり、（ＴＴＲＴ／Ｔ）Ｃは要
求されるｈi下限であることを意味する。このように、
定理２で与えられる上限と最小のｈiとの差は、次式に
より制限される。
Ｔ＜ｄ＜Ｔ＋２×ＴＴＲＴに対して、定理２により最小
のｈiの上限のみが得られる。この上限がいかにぴった
りしているかを知るために、ＦＤＤＩネットワークにつ
いてのリアルタイムチャネルの確立のための必要な条件
が、割り当てられた同期帯域幅（ｈi／ＴＴＲＴ×１０
０Ｍｂｐｓ）がチャネルについての運ばれるべき期待信
号帯域幅（Ｃ／Ｔ×１００Ｍｂｐｓ）よりも小さくては
ならないことを注意しておく。これは、ｈi≧（ＴＴＲ
Ｔ／Ｔ）Ｃが必要条件であり、（ＴＴＲＴ／Ｔ）Ｃは要
求されるｈi下限であることを意味する。このように、
定理２で与えられる上限と最小のｈiとの差は、次式に
より制限される。
【００７２】
【数１３】
【００７３】ここで、ｘ＝Ｔ／ＴＴＲＴである。
【００７４】このことから、定理２において得られる上
限は最小ｈiの２倍を決して越えないであろうことが分
かる。他に、ＴがＴＴＲＴの倍数であるか、ＴＴＲＴが
Ｔの倍数であるとき、定理２から得られる上限は実際は
最小ｈiであることが得られる。
限は最小ｈiの２倍を決して越えないであろうことが分
かる。他に、ＴがＴＴＲＴの倍数であるか、ＴＴＲＴが
Ｔの倍数であるとき、定理２から得られる上限は実際は
最小ｈiであることが得られる。
【００７５】第２に、アルゴリズム１は、最小ｈiが定
理２から得られるとき、最適なＳＢＡ構成である。これ
は、以下に示す４つの状況を含んでいる。
理２から得られるとき、最適なＳＢＡ構成である。これ
は、以下に示す４つの状況を含んでいる。
【００７６】 １．２×ＴＴＲＴ≦ｄ≦Ｔ＋ＴＴＲＴ ２．ｄ≧Ｔ＋２×ＴＴＲＴ ３．ＴがＴＴＲＴの倍数である。 ４．ＴＴＲＴがＴの倍数である。
【００７７】上記の状況はほとんどのリアルタイム通信
アプリケーションを含んでいることに注意する。例え
ば、分散制御／監視システムにおける通信は、通常、き
つい遅延時間要求（ｄ≦Ｔ＋ＴＴＲＴ）をもっている、
そして、ビデオ／オーディオ通信は、しばしば大きな遅
延時間（ｄ≧Ｔ＋２×ＴＴＲＴ）に耐えることができ
る。このようにほとんどのアプリケーションに対して、
アルゴリズム１による同期帯域幅割り当ては最適なもの
である。
アプリケーションを含んでいることに注意する。例え
ば、分散制御／監視システムにおける通信は、通常、き
つい遅延時間要求（ｄ≦Ｔ＋ＴＴＲＴ）をもっている、
そして、ビデオ／オーディオ通信は、しばしば大きな遅
延時間（ｄ≧Ｔ＋２×ＴＴＲＴ）に耐えることができ
る。このようにほとんどのアプリケーションに対して、
アルゴリズム１による同期帯域幅割り当ては最適なもの
である。
【００７８】一般性に関するこの発明の利点について言
うと、アルゴリズム１が任意のパラメータ、すなわちｄ
≦Ｔまたはｄ＞Ｔについてチャネルを確立できるのに対
し、従来のＳＢＡ構成はｄ＝Ｔのみでリアルタイムチャ
ネルを確立することができる。多くのアプリケーショ
ン、特に、リアルタイム制御／監視システムについての
要求遅延時間制限ｄは、通常、メッセージ発生期間Ｔよ
りも小さいから、実際においてこの拡張は非常に重要で
ある。また、ｄ＞Ｔによるリアルタイムチャネルは、マ
ルチメディアアプリケーションに対して有用である。こ
のように、ｄ＝Ｔと制限することにより、リアルタイム
通信を取り扱うネットワークの能力及び効果は大きく制
限される。
うと、アルゴリズム１が任意のパラメータ、すなわちｄ
≦Ｔまたはｄ＞Ｔについてチャネルを確立できるのに対
し、従来のＳＢＡ構成はｄ＝Ｔのみでリアルタイムチャ
ネルを確立することができる。多くのアプリケーショ
ン、特に、リアルタイム制御／監視システムについての
要求遅延時間制限ｄは、通常、メッセージ発生期間Ｔよ
りも小さいから、実際においてこの拡張は非常に重要で
ある。また、ｄ＞Ｔによるリアルタイムチャネルは、マ
ルチメディアアプリケーションに対して有用である。こ
のように、ｄ＝Ｔと制限することにより、リアルタイム
通信を取り扱うネットワークの能力及び効果は大きく制
限される。
【００７９】最適性に関して言うと、Agrawalその他の
ＳＢＡ構成は、制限的な仮定ｄ＝Ｔの下ですら、最適で
はない。このように、他の構成を用いて確立するなら、
リアルタイムチャネル確立要求は拒絶されるかもしれな
い。Chenその他のＳＢＡ構成はｄ＝Ｔの制限的な仮定の
下で最適であり、複雑な計算を要求する。対照的に、ア
ルゴリズム１は、従来のＳＢＡ構成の特別の場合である
ｄ＝Ｔを含む非常に広い範囲のｄに対して最適である。
ＳＢＡ構成は、制限的な仮定ｄ＝Ｔの下ですら、最適で
はない。このように、他の構成を用いて確立するなら、
リアルタイムチャネル確立要求は拒絶されるかもしれな
い。Chenその他のＳＢＡ構成はｄ＝Ｔの制限的な仮定の
下で最適であり、複雑な計算を要求する。対照的に、ア
ルゴリズム１は、従来のＳＢＡ構成の特別の場合である
ｄ＝Ｔを含む非常に広い範囲のｄに対して最適である。
【００８０】最後に単純性に関して言うと、従来のＳＢ
Ａ構成は、チャネルの追加／除去またはチャネルのパラ
メータの変更がネットワークの全てのノードの同期帯域
幅割り当ての調整を必要とする意味で大域の構成であ
る。このことから、ＳＢＡの実行が複雑になる。対照的
に、アルゴリズム１は局所的なパラメータ調整を必要と
するのみで、そのため従来の構成より実行がはるかに容
易になる。
Ａ構成は、チャネルの追加／除去またはチャネルのパラ
メータの変更がネットワークの全てのノードの同期帯域
幅割り当ての調整を必要とする意味で大域の構成であ
る。このことから、ＳＢＡの実行が複雑になる。対照的
に、アルゴリズム１は局所的なパラメータ調整を必要と
するのみで、そのため従来の構成より実行がはるかに容
易になる。
【００８１】アルゴリズム１の１つのアプリケーション
の例として、ＦＤＤＩネットワークにおける以下に示す
ようなビデオチャネルを確立するために必要な同期帯域
幅を計算する。ビデオフレーム発生周期Ｔ＝３３ｍｓ
（３０フレーム／秒）、最大フレームの送信時間は１ｍ
ｓ（１００Ｋｂ最大フレームサイズ）そして要求される
フレーム遅延時間制限はｄｍｓであるとする。このビデ
オチャネルの最大期待トラヒックは、ＢC＝Ｃ／Ｔ×１
００＝３Ｍｂｐｓである。ネットワーク目標トークン巡
回時間は代表値ＴＴＲＴ＝８ｍｓにセットされていると
する。
の例として、ＦＤＤＩネットワークにおける以下に示す
ようなビデオチャネルを確立するために必要な同期帯域
幅を計算する。ビデオフレーム発生周期Ｔ＝３３ｍｓ
（３０フレーム／秒）、最大フレームの送信時間は１ｍ
ｓ（１００Ｋｂ最大フレームサイズ）そして要求される
フレーム遅延時間制限はｄｍｓであるとする。このビデ
オチャネルの最大期待トラヒックは、ＢC＝Ｃ／Ｔ×１
００＝３Ｍｂｐｓである。ネットワーク目標トークン巡
回時間は代表値ＴＴＲＴ＝８ｍｓにセットされていると
する。
【００８２】ｄは２×ＴＴＲＴより小さくてはならない
から、上記のビデオチャネルをｄ＜１６ｍｓに対して確
立することはできない。１６≦ｄ≦Ｔ＋ＴＴＲＴ＝４１
ｍｓに対して、最小要求ｈiは定理２から計算される。
から、上記のビデオチャネルをｄ＜１６ｍｓに対して確
立することはできない。１６≦ｄ≦Ｔ＋ＴＴＲＴ＝４１
ｍｓに対して、最小要求ｈiは定理２から計算される。
【００８３】
【数１４】
【００８４】ｄ≧Ｔ＋２×ＴＴＲＴ＝４９ｍｓに対して ｈi＝（ＴＴＲＴ／Ｔ）Ｃ＝０．２４ｍｓ ４１ｍｓ＜ｄ＜４９ｍｓに対して、我々は定理２で与え
られた上限を用いる。
られた上限を用いる。
【００８５】ｈi＝Ｃ／ｐ0＝０．２５ｍｓ１つのチャネ
ルに割り当てられた同期帯域幅が Ｂi＝ｈi／ＴＴＲＴ
×１００Ｍｂｐｓであることを思い出して、ｄの関数と
してのＢiの値により以下の検討結果が得られる。
ルに割り当てられた同期帯域幅が Ｂi＝ｈi／ＴＴＲＴ
×１００Ｍｂｐｓであることを思い出して、ｄの関数と
してのＢiの値により以下の検討結果が得られる。
【００８６】第１に、要求される遅延時間制限ｄが小さ
くなればなるほど、同期帯域幅はチャネルにより多く要
求される。例えば、遅延時間制限ｄ＜２３ｍｓ内でそれ
ぞれのビデオフレームが供給されることを保証するため
に、チャネルについて期待信号帯域幅の４倍以上の１
２．５Ｍｂｐｓ同期帯域幅を、ビデオチャネルが確保す
る必要がある。一般的に、１つのチャネルには、遅延時
間制限ｄを保証するために必要な最大信号帯域幅（定理
２から）のおよそ
くなればなるほど、同期帯域幅はチャネルにより多く要
求される。例えば、遅延時間制限ｄ＜２３ｍｓ内でそれ
ぞれのビデオフレームが供給されることを保証するため
に、チャネルについて期待信号帯域幅の４倍以上の１
２．５Ｍｂｐｓ同期帯域幅を、ビデオチャネルが確保す
る必要がある。一般的に、１つのチャネルには、遅延時
間制限ｄを保証するために必要な最大信号帯域幅（定理
２から）のおよそ
【００８７】
【数１５】
【００８８】倍の同期帯域幅が必要である。このこと
は，ＦＤＤＩはきつい遅延時間要求によるリアルタイム
通信を取り扱う点で非常に効果的ではないことを示して
いる。小さな遅延時間制限を要求するリアルタイムトラ
ヒックを扱うことのＦＤＤＩの能力を顕著に改善するＦ
ＤＤＩのＭＡＣプロトコルの単純な修正はKang G.Shin
及びQin Zhengにより提案された。
は，ＦＤＤＩはきつい遅延時間要求によるリアルタイム
通信を取り扱う点で非常に効果的ではないことを示して
いる。小さな遅延時間制限を要求するリアルタイムトラ
ヒックを扱うことのＦＤＤＩの能力を顕著に改善するＦ
ＤＤＩのＭＡＣプロトコルの単純な修正はKang G.Shin
及びQin Zhengにより提案された。
【００８９】第２に、要求される同期帯域幅により、ｄ
≧Ｔ＋２×ＴＴＲＴ＝４９ｍｓに対する期待信号帯域幅
が減少する。この事実には２つの意味がある。（１）１
つのチャネルに期待信号帯域幅と等しい同期帯域幅が割
り当てられるとき、それぞれのメッセージがＴ＋２×Ｔ
ＴＲＴ（あるいはＴがＴＴＲＴの倍数であるなら Ｔ＋
ＴＴＲＴ）より長くない遅延時間で送信されることが保
証される。このことはメッセージ遅延時間限界は媒体ア
クセス遅延限界２×ＴＴＲＴに等しいという一般的な誤
解と対照的である。（２）メッセージ遅延時間がＴ＋２
×ＴＴＲＴよりも大きくなることを許容することによ
り、得られることは何もない。言い換えれば、フレーム
が５００ｍｓ程度遅延することが許容されているビデオ
チャネルは、上記の例のわずかに５０ｍｓのフレーム遅
延を要求するチャネルと同じ同期帯域幅を必要とするの
である。この発見はＦＤＤＩネットワークについて分配
マルチメディアシステムを設計するために非常に有用で
ある。
≧Ｔ＋２×ＴＴＲＴ＝４９ｍｓに対する期待信号帯域幅
が減少する。この事実には２つの意味がある。（１）１
つのチャネルに期待信号帯域幅と等しい同期帯域幅が割
り当てられるとき、それぞれのメッセージがＴ＋２×Ｔ
ＴＲＴ（あるいはＴがＴＴＲＴの倍数であるなら Ｔ＋
ＴＴＲＴ）より長くない遅延時間で送信されることが保
証される。このことはメッセージ遅延時間限界は媒体ア
クセス遅延限界２×ＴＴＲＴに等しいという一般的な誤
解と対照的である。（２）メッセージ遅延時間がＴ＋２
×ＴＴＲＴよりも大きくなることを許容することによ
り、得られることは何もない。言い換えれば、フレーム
が５００ｍｓ程度遅延することが許容されているビデオ
チャネルは、上記の例のわずかに５０ｍｓのフレーム遅
延を要求するチャネルと同じ同期帯域幅を必要とするの
である。この発見はＦＤＤＩネットワークについて分配
マルチメディアシステムを設計するために非常に有用で
ある。
【００９０】第３に、ＴがＴＴＲＴより数倍長いとき
は、定理２から計算されるｈiの上限と実際の最小ｈiの
差は無視できる。この差はＴの減少に伴い増加する。し
たがって、Ｔ＋ＴＴＲＴ＜ｄ＜Ｔ＋２×ＴＴＲＴかつＴ
がＴＴＲＴの倍数でないときは、同期帯域幅を過剰に確
保しないようにＴＴＲＴはできるだけ小さく設定すべき
である。
は、定理２から計算されるｈiの上限と実際の最小ｈiの
差は無視できる。この差はＴの減少に伴い増加する。し
たがって、Ｔ＋ＴＴＲＴ＜ｄ＜Ｔ＋２×ＴＴＲＴかつＴ
がＴＴＲＴの倍数でないときは、同期帯域幅を過剰に確
保しないようにＴＴＲＴはできるだけ小さく設定すべき
である。
【００９１】アルゴリズム１は、通常の供給元のノード
でのリアルタイムチャネルに対しても使用される。特
に、２つのチャネルτ1とτ2が同じ供給元のノードであ
るならば、τ1はｈi＝ｔ1である必要が、τ2はｈi＝ｔ2
である必要がある。このときｈi＝ｔ1＋ｔ2に設定すれ
ば、トークンの訪問でｔ1とｔ2をそれぞれ越えないよう
に、τ1とτ2のメッセージの送信時間を調整する送信元
のノードにある機構を提供する両方のチャネルの要求が
満足される。
でのリアルタイムチャネルに対しても使用される。特
に、２つのチャネルτ1とτ2が同じ供給元のノードであ
るならば、τ1はｈi＝ｔ1である必要が、τ2はｈi＝ｔ2
である必要がある。このときｈi＝ｔ1＋ｔ2に設定すれ
ば、トークンの訪問でｔ1とｔ2をそれぞれ越えないよう
に、τ1とτ2のメッセージの送信時間を調整する送信元
のノードにある機構を提供する両方のチャネルの要求が
満足される。
【００９２】上述したこの発明の望ましい実施例によ
り、この技術分野の技能を有する者は、この発明の思想
の範囲内で修正及び変更を行い得る。したがって、特許
請求の範囲の記載のみによりこの発明の範囲が定義され
るものである。
り、この技術分野の技能を有する者は、この発明の思想
の範囲内で修正及び変更を行い得る。したがって、特許
請求の範囲の記載のみによりこの発明の範囲が定義され
るものである。
【００９３】
【発明の効果】以上のように、請求項１の発明によれ
ば、トークンリングネットワークに接続されたノードの
いずれもが最悪の場合でメッセージ送信を許される時間
Γ(t)が、１つのノードが上記トークンリングネットワ
ークのメッセージ伝搬時間制約条件を満足させる必要が
ある時間よりも小さくないように最小同期帯域幅割り当
てｈiを発生するための、上記ネットワークマネジャに
結合されるように適合された手段を備えるので、最適な
同期帯域幅割り当てｈiを発生させることができる。
ば、トークンリングネットワークに接続されたノードの
いずれもが最悪の場合でメッセージ送信を許される時間
Γ(t)が、１つのノードが上記トークンリングネットワ
ークのメッセージ伝搬時間制約条件を満足させる必要が
ある時間よりも小さくないように最小同期帯域幅割り当
てｈiを発生するための、上記ネットワークマネジャに
結合されるように適合された手段を備えるので、最適な
同期帯域幅割り当てｈiを発生させることができる。
【００９４】また、請求項２の発明によれば、最小同期
帯域幅割り当てｈiを、所定の式で表される上記時間Γ
(t)が、所定の式を満足するように発生する構成とした
ので、最小メッセージ発生時間と要求メッセージ供給遅
延限界とが一致しないときでも、最適な同期帯域幅割り
当てｈiを発生させることができる。
帯域幅割り当てｈiを、所定の式で表される上記時間Γ
(t)が、所定の式を満足するように発生する構成とした
ので、最小メッセージ発生時間と要求メッセージ供給遅
延限界とが一致しないときでも、最適な同期帯域幅割り
当てｈiを発生させることができる。
【００９５】また、請求項３の発明によれば、所定の手
順によりノードｉについて最小同期帯域幅割り当てｈi
を求める構成としたので、繰り返し演算によらず、最適
な同期帯域幅割り当てｈiを発生させることができる。
順によりノードｉについて最小同期帯域幅割り当てｈi
を求める構成としたので、繰り返し演算によらず、最適
な同期帯域幅割り当てｈiを発生させることができる。
【図１】 この発明の一実施例によるトークンリングネ
ットワークの構成図である。
ットワークの構成図である。
１０ トークンリングネットワーク、１２、１４ ノー
ド、１８ ネットワークマネジャ、２４ ｈi発生器。
ド、１８ ネットワークマネジャ、２４ ｈi発生器。
Claims (3)
- 【請求項１】 多数のノードとネットワークマネジャを
有するトークンリングネットワークにおいて、 上記トークンリングネットワークに接続されたノードの
いずれもが最悪の場合でメッセージ送信を許される時間
Γ(t)が、１つのノードが上記トークンリングネットワ
ークのメッセージ伝搬時間制約条件を満足させる必要が
ある時間よりも小さくないように、最小同期帯域幅割り
当てｈiを発生するための、上記ネットワークマネジャ
に結合されるように適合された手段を備えることを特徴
とするトークンリングネットワークの同期帯域幅割り当
てシステム。 - 【請求項２】 トークンリングネットワークに接続され
たノードがメッセージを発生する間隔としての最小メッ
セージ発生時間をＴ、上記メッセージを送信するために
許される時間としての最大メッセージ送信時間をＣ、上
記メッセージを供給するまでに許される時間としての要
求メッセージ供給遅延限界をｄ、及びトークンが上記ト
ークンリングネットワークを巡回する時間である目標ト
ークン巡回時間をＴＴＲＴとしたとき、 上記最小同期帯域幅割り当てｈiを、 【数１】 で表される上記時間Γ(t)が、次式を満足するように 【数２】 発生することを特徴とする請求項１記載のトークンリン
グネットワークの同期帯域幅割り当てシステム。 - 【請求項３】 トークンリングネットワークに接続され
たノードがメッセージを発生する間隔としての最小メッ
セージ発生時間をＴ、上記メッセージを送信するために
許される時間としての最大メッセージ送信時間をＣ、上
記メッセージを供給するまでに許される時間としての要
求メッセージ供給遅延限界をｄ、及びトークンが上記ト
ークンリングネットワークを巡回する時間である目標ト
ークン巡回時間をＴＴＲＴとしたとき、 以下の手順により、ノードｉについて最小同期帯域幅割
り当てｈiを求めることを特徴とする請求項１記載のト
ークンリングネットワークの同期帯域幅割り当てシステ
ム。 【数３】
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/099918 | 1993-07-30 | ||
| US08/099,918 US5390182A (en) | 1993-07-30 | 1993-07-30 | System for synchronous bandwidth allocation in token ring networks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0746267A true JPH0746267A (ja) | 1995-02-14 |
| JP3329942B2 JP3329942B2 (ja) | 2002-09-30 |
Family
ID=22277241
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP13738694A Expired - Lifetime JP3329942B2 (ja) | 1993-07-30 | 1994-06-20 | トークンリングネットワークの同期帯域幅割り当てシステム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5390182A (ja) |
| JP (1) | JP3329942B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6590865B1 (en) | 1998-08-04 | 2003-07-08 | Matsushita Electric Industrial Co., Ltd. | Transmission system, bandwidth management apparatus, and bandwidth management method |
| KR100484305B1 (ko) * | 2002-11-26 | 2005-04-20 | 한국전자통신연구원 | 이중 링에서의 부하 분산과 공평성 제공을 고려한 자원할당 방법 |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5600797A (en) * | 1993-11-24 | 1997-02-04 | Intel Corporation | System for identifying new client and allocating bandwidth thereto by monitoring transmission of message received periodically from client computers informing of their current status |
| US5673393A (en) * | 1993-11-24 | 1997-09-30 | Intel Corporation | Managing bandwidth over a computer network having a management computer that allocates bandwidth to client computers upon request |
| US5604742A (en) * | 1995-05-31 | 1997-02-18 | International Business Machines Corporation | Communications system and method for efficient management of bandwidth in a FDDI station |
| EP1457895A3 (en) | 1995-10-26 | 2005-04-20 | Matsushita Electric Industrial Co., Ltd. | File System |
| US6058419A (en) * | 1996-10-30 | 2000-05-02 | Nec Corporation | Communication network control system and control method therefor |
| US5935218A (en) * | 1997-04-04 | 1999-08-10 | Siemens Information And Communication Networks, Inc. | Method and apparatus for bus network prioritization using the broadcast of delay time to lower priority users from high priority users in a token or loop network |
| US7415038B2 (en) * | 2001-03-29 | 2008-08-19 | International Business Machines Corporation | Method and system for network management providing access to application bandwidth usage calculations |
| US7130927B2 (en) * | 2001-07-05 | 2006-10-31 | International Business Machines Corporation | Method of bandwidth management between the stations of a local area network |
| US7248601B2 (en) * | 2001-08-09 | 2007-07-24 | International Business Machines Corporation | Method of allocating bandwidth on request to the stations of a local area network |
| FR2849730A1 (fr) * | 2003-01-02 | 2004-07-09 | Thomson Licensing Sa | Methode pour reserver de la bande passante dans un reseau de type ethernet |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE3785799T2 (de) * | 1986-06-27 | 1993-10-28 | Fujitsu Ltd | Paketdatenübertragungssystem mit Ringtypübertragungsleitung. |
| US4942574A (en) * | 1988-03-31 | 1990-07-17 | American Telephone And Telegraph Company, At&T Bell Laboratories | Concurrent resource request resolution mechanism |
| JP2522392B2 (ja) * | 1988-08-05 | 1996-08-07 | 三菱電機株式会社 | サイクリックデ―タ伝送方法 |
| JPH06103888B2 (ja) * | 1989-10-14 | 1994-12-14 | 三菱電機株式会社 | 通信レスポンス制御方法 |
| US5119374A (en) * | 1990-05-29 | 1992-06-02 | Advanced Micro Devices, Inc. | Method of and system for implementing multiple levels of asynchronous priority in FDDI networks |
| US5291491A (en) * | 1991-01-22 | 1994-03-01 | Digital Equipment Corporation | Avoidance of false re-initialization of a computer network |
| US5251209A (en) * | 1991-03-28 | 1993-10-05 | Sprint International Communications Corp. | Prioritizing attributes in integrated services networks |
| US5313466A (en) | 1992-09-22 | 1994-05-17 | The Texas A&M University System | Local synchronous bandwidth allocation in a token ring network |
-
1993
- 1993-07-30 US US08/099,918 patent/US5390182A/en not_active Expired - Lifetime
-
1994
- 1994-06-20 JP JP13738694A patent/JP3329942B2/ja not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6590865B1 (en) | 1998-08-04 | 2003-07-08 | Matsushita Electric Industrial Co., Ltd. | Transmission system, bandwidth management apparatus, and bandwidth management method |
| KR100484305B1 (ko) * | 2002-11-26 | 2005-04-20 | 한국전자통신연구원 | 이중 링에서의 부하 분산과 공평성 제공을 고려한 자원할당 방법 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5390182A (en) | 1995-02-14 |
| JP3329942B2 (ja) | 2002-09-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zheng et al. | Synchronous bandwidth allocation in FDDI networks | |
| EP0621704B1 (en) | System for network wide bandwidth allocation | |
| US7496112B1 (en) | Methods and apparatuses for allocating time slots to circuit switched channels | |
| US5754532A (en) | Use of multipoint connection services to establish call-tapping points in a switched network | |
| US5548579A (en) | System for effective allocation of network-wide bandwidth | |
| JP2000502856A (ja) | ネットワーク資源を管理する方法と装置 | |
| JPH07170271A (ja) | 統合ネットワークにおけるマルチメディア・ストリームの柔軟な参入許可制御方法 | |
| JP3329942B2 (ja) | トークンリングネットワークの同期帯域幅割り当てシステム | |
| JPH0646082A (ja) | 情報転送制御方式 | |
| Degermark et al. | Advance reservations for predictive service in the internet | |
| Hamdaoui et al. | Selection of timed token protocol parameters to guarantee message deadlines | |
| Wong et al. | Fairness in window flow controlled computer networks | |
| Ferrari et al. | Resource partitioning for real-time communication | |
| Bohm et al. | Resource reservation in DTM | |
| Baldi et al. | Adaptive real-time group multicast | |
| Rubin et al. | FECCA-A new access algorithm for an ATM ring network with destination removal | |
| JP2794740B2 (ja) | 網内リソース管理方法 | |
| Chen et al. | On the ability of the FDDI-M protocol to support real-time traffic | |
| KR20000025697A (ko) | 사설망 노드 인터페이스 라우팅 기능을 분산시키는 방버버 | |
| JP2844627B2 (ja) | 網内リソース割り当て方法 | |
| Tufail et al. | ABR congestion control schemes and the multicast problem | |
| Huang et al. | A novel congestion control mechanism for multicast real-time connections | |
| JP2000031972A (ja) | 分散型マルチメディアサービス提供システム | |
| Jia et al. | Guaranteeing maximum reliability and minimum delay QoS routing based on WF2Q | |
| Selvakennedy et al. | Dynamic scheduling scheme for handling traffic multiplicity in wavelength division multiplexed optical networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R370 | Written measure of declining of transfer procedure |
Free format text: JAPANESE INTERMEDIATE CODE: R370 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R154 | Certificate of patent or utility model (reissue) |
Free format text: JAPANESE INTERMEDIATE CODE: R154 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070719 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080719 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090719 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100719 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110719 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110719 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120719 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120719 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130719 Year of fee payment: 11 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |