(57)【要約】【課題】各ノードがポイントツーポイントで接続され、トークンパッシングによって伝送制御を行うネットワークにて、優先ノードが存在する場合に、効率のよいトークンの巡回路を決定する。【解決手段】接続情報２０６は、複数の従属ノード３００と主ノード２００との接続関係、どの従属ノード３００が優先ノードであるかを定義する情報である。巡回路生成部２０３は、優先ノードを介して主ノード２００に接続された従属ノード３００（以下、子ノードという）がある場合、その優先ノードの次に子ノードに対してトークンを巡回させてから、残りの従属ノード３００に対してトークンを巡回させる経路を巡回路として生成する。そして、巡回路生成部２０３は、生成した巡回路を定義する情報を巡回路情報２０２として出力する。【選択図】図３
2010233134.tif 000002
【特許請求の範囲】
【請求項１】
トークンを保持している時間内のみデータを送信することが許される複数の従属ノードと、少なくとも１つの従属ノードを直接接続し、当該少なくとも１つの従属ノード以外の従属ノードを他の従属ノードを介して接続し、前記複数の従属ノードの間でトークンを巡回させる主ノードとに対し、トークンを巡回させる経路である巡回路を生成する巡回路生成装置であって、
前記複数の従属ノードと前記主ノードとの接続関係を定義するとともに、他の従属ノードより優先してトークンの巡回先となる従属ノードを優先ノードとして定義する接続情報を記憶装置に予め保持する接続情報保持部と、
前記接続情報保持部により保持された接続情報を参照して、前記優先ノードを介して前記主ノードに接続された従属ノードがある場合、当該従属ノードを子ノードとし、前記優先ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として処理装置により生成し、生成した巡回路を定義する巡回路情報を出力する巡回路生成部とを備えることを特徴とする巡回路生成装置。
【請求項２】
前記巡回路生成部は、前記接続情報保持部により保持された接続情報で複数の優先ノードが定義されている場合、前記複数の優先ノードのうち、前記主ノードとの間に接続された従属ノードの数であるホップ数が最も多い優先ノードを最遠ノードとし、前記最遠ノードの前に前記最遠ノード以外の優先ノードに対してトークンを巡回させ、前記最遠ノードを介して前記主ノードに接続された従属ノードがある場合、当該従属ノードを前記子ノードとし、前記最遠ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として生成することを特徴とする請求項１に記載の巡回路生成装置。
【請求項３】
前記巡回路生成部は、前記最遠ノードと前記主ノードとの間に接続された従属ノードがある場合、当該従属ノードのうち、ホップ数が多い従属ノードから順番に対象ノードとし、当該対象ノードと当該対象ノードを介して前記主ノードに接続された従属ノードとに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として生成することを特徴とする請求項２に記載の巡回路生成装置。
【請求項４】
前記巡回路生成装置は、前記主ノードとなる通信装置であり、
前記巡回路生成部は、記憶装置に対し、前記巡回路情報を書き込むとともに、前記複数の従属ノードの各々に対し、前記巡回路情報で定義された巡回路を設定するための情報を送信することを特徴とする請求項１から３までのいずれかに記載の巡回路生成装置。
【請求項５】
トークンを保持している時間内のみデータを送信することが許される複数の従属ノードと、少なくとも１つの従属ノードを直接接続し、当該少なくとも１つの従属ノード以外の従属ノードを他の従属ノードを介して接続し、前記複数の従属ノードの間でトークンを巡回させる主ノードとに対し、トークンを巡回させる経路である巡回路を生成する巡回路生成方法であって、
記憶装置が、前記複数の従属ノードと前記主ノードとの接続関係を定義するとともに、他の従属ノードより優先してトークンの巡回先となる従属ノードを優先ノードとして定義する接続情報を予め保持し、
処理装置が、記憶装置に保持された接続情報を参照して、前記優先ノードを介して前記主ノードに接続された従属ノードがある場合、当該従属ノードを子ノードとし、前記優先ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として生成し、生成した巡回路を定義する巡回路情報を出力することを特徴とする巡回路生成方法。
【請求項６】
トークンを保持している時間内のみデータを送信することが許される複数の従属ノードと、少なくとも１つの従属ノードを直接接続し、当該少なくとも１つの従属ノード以外の従属ノードを他の従属ノードを介して接続し、前記複数の従属ノードの間でトークンを巡回させる主ノードとに対し、トークンを巡回させる経路である巡回路を生成する巡回路生成プログラムであって、
前記複数の従属ノードと前記主ノードとの接続関係を定義するとともに、他の従属ノードより優先してトークンの巡回先となる従属ノードを優先ノードとして定義する接続情報を記憶装置に予め保持する接続情報保持処理と、
前記接続情報保持処理により保持された接続情報を参照して、前記優先ノードを介して前記主ノードに接続された従属ノードがある場合、当該従属ノードを子ノードとし、前記優先ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として処理装置により生成し、生成した巡回路を定義する巡回路情報を出力する巡回路生成処理とをコンピュータに実行させることを特徴とする巡回路生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、巡回路生成装置及び巡回路生成方法及び巡回路生成プログラムに関するものである。本発明は、特に、トークンパッシングによって伝送制御を行う通信方式に利用可能な巡回路生成装置及び巡回路生成方法及び巡回路生成プログラムに関するものである。
【背景技術】
【０００２】
伝送制御方式の１つに、トークンパッシング方式がある。トークンパッシング方式では、ノード間でトークンの受け渡しを行い、トークンを保持しているノードがデータの送信権を得る。これにより、ネットワーク内の１つのノードのみが送信権を得ることになり、複数ノードが同時に送信することによる衝突を回避している。ノードの参入と離脱がある都度、受け渡しするノードの順序を決めた上で、トークンを巡回させる。ノードは、巡回しているトークンを保持した際、送信するデータを持っていれば、データを送信してトークンを解放する。送信すべきデータがなければ、そのままトークンを解放する。
【０００３】
従来技術では、バスに接続した複数のノードが、局番の大きな局から小さな局の順となるように構成した論理リングを用いて、トークン巡回を行っている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平６−３３４６６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
各ノードがポイントツーポイントで接続されるネットワークにおいても、前述したトークンパッシング方式を用いることができる。各ノードでは、トークンを受け取ると自ノード宛か判定し、自ノード宛であればトークンを保持し、自ノード宛でなければ、他ノード宛にブリッジ動作をする。
【０００６】
各ノードがポイントツーポイントで接続されるネットワークでは、トークンの巡回順序が適切でないと、ノード間をトークンが必要以上に往復することになり効率が悪い。例えば、１局〜４局の４台のノードから構成されるネットワークにおいて、４台のノードが１局、２局、３局、４局の順に直列に接続されているとする。このとき、トークンを１局→３局→２局→４局→１局の順で巡回させた場合、トークンが経由するノードは１局→２局→３局→２局→３局→４局→３局→２局→１局となる。一方、トークンを１局→２局→３局→４局→１局の順で巡回させた場合、トークンが経由するノードは１局→２局→３局→４局→３局→２局→１局となり、効率がよくなる。ノード数が増えるほど、適切でない順序でトークンを巡回させた場合の無駄が多くなる。
【０００７】
伝送路上では、上記のように適切な順序でトークンを巡回させることが理想であるが、アプリケーション上の必要等から、トークンの巡回路中でトークンを先に送付したいノード（以下では優先ノードと呼ぶ）が存在する場合がある。優先ノードがネットワークに存在する場合でも、できるだけ無駄なくトークンがノードを一巡するように、巡回路を決定することで、ネットワークの利用率が向上する。
【０００８】
しかしながら、従来技術では、各ノードがポイントツーポイントで接続されるネットワーク構成を踏まえていないため、適切でないトークン巡回順序となるという課題があった。また、トークンを先に送付したいノードが存在する場合に、先にトークンが巡回するような順序にトークン巡回順序を決定することができないという課題があった。
【０００９】
ある種のシステムは、マスタ用途のノードと、マスタ用途のノードと比した場合リソースに制限があるスレーブ用途のノードから構成される。このようなシステムでは、伝送制御レベルでも、スレーブ用途のノードで使用できるリソースに制限がある。
【００１０】
しかしながら、従来技術では、全てのノードが同じ機能を有しており、リソースの少ない（使用できるリソースが制限されているため、多くの機能を実装できない）スレーブをネットワークのノードにする場合に、そのまま適用できないという課題があった。
【００１１】
本発明では、例えば、各ノードがポイントツーポイントで接続され、トークンパッシングによって伝送制御を行うネットワークにて、優先ノードが存在する場合に、効率のよいトークンの巡回路を決定することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一の態様に係る巡回路生成装置は、
トークンを保持している時間内のみデータを送信することが許される複数の従属ノードと、少なくとも１つの従属ノードを直接接続し、当該少なくとも１つの従属ノード以外の従属ノードを他の従属ノードを介して接続し、前記複数の従属ノードの間でトークンを巡回させる主ノードとに対し、トークンを巡回させる経路である巡回路を生成する巡回路生成装置であって、
前記複数の従属ノードと前記主ノードとの接続関係を定義するとともに、他の従属ノードより優先してトークンの巡回先となる従属ノードを優先ノードとして定義する接続情報を記憶装置に予め保持する接続情報保持部と、
前記接続情報保持部により保持された接続情報を参照して、前記優先ノードを介して前記主ノードに接続された従属ノードがある場合、当該従属ノードを子ノードとし、前記優先ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を前記巡回路として処理装置により生成し、生成した巡回路を定義する巡回路情報を出力する巡回路生成部とを備えることを特徴とする。
【発明の効果】
【００１３】
本発明の一の態様によれば、巡回路生成装置が、優先ノードを介して主ノードに接続された従属ノードがある場合、当該従属ノードを子ノードとし、前記優先ノードの次に前記子ノードに対してトークンを巡回させてから、残りの従属ノードに対してトークンを巡回させる経路を巡回路として生成するため、各ノードがポイントツーポイントで接続され、トークンパッシングによって伝送制御を行うネットワークにて、優先ノードが存在する場合に、効率のよいトークンの巡回路を決定することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１に係る通信システムの構成例を示すブロック図である。
【図２】実施の形態１に係る通信システムの他の構成例を示すブロック図である。
【図３】実施の形態１に係る主ノードの構成を示すブロック図である。
【図４】実施の形態１に係る従属ノードの構成を示すブロック図である。
【図５】実施の形態１に係る主ノード及び従属ノードそれぞれのハードウェア構成の一例を示す図である。
【図６】実施の形態１に係る主ノードの接続情報保持部で保持される接続情報の一例を示すテーブルである。
【図７】実施の形態１に係る主ノードの巡回路生成部で出力される巡回路情報の一例を示すテーブルである。
【図８】実施の形態１に係る主ノードの参照構造生成部の動作を示すフローチャートである。
【図９】実施の形態１に係る主ノードの巡回路生成部の動作を示すフローチャートである。
【図１０】実施の形態１に係る主ノードのフレーム判定部の動作を示すフローチャートである。
【図１１】実施の形態１に係る従属ノードのフレーム判定部の動作を示すフローチャートである。
【図１２】実施の形態１に係る主ノードのトークン解析部及び従属ノードのトークン解析部の動作を示すフローチャートである。
【図１３】実施の形態２に係る通信システムの構成例を示すブロック図である。
【図１４】実施の形態２に係る主ノードの接続情報保持部で保持される接続情報の一例を示すテーブルである。
【図１５】実施の形態２に係る主ノードの巡回路生成部で出力される巡回路情報の一例を示すテーブルである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、図を用いて説明する。
【００１６】
実施の形態１．
図１は、本実施の形態に係る通信システム１００の構成例を示すブロック図である。
【００１７】
図１の例において、通信システム１００は、ライン型（直列接続型）のシステム構成をとっている。通信システム１００は、１つの主ノード２００（１局）と複数の従属ノード３００（２局〜４局）から構成され、ノード間は伝送路１０１によってピアツーピアで接続されている。
【００１８】
主ノード２００は、少なくとも１つの従属ノード３００を直接接続し、当該少なくとも１つの従属ノード３００以外の従属ノード３００を他の従属ノード３００（直接接続している従属ノード３００、あるいは、直接接続している従属ノード３００及びその先に接続されている１つ以上の従属ノード３００）を介して接続し、複数の従属ノード３００の間でトークンを巡回させる通信装置である。図１の例では、主ノード２００である１局は、従属ノード３００である２局〜４局のうち、２局を直接接続している。また、２局を介して３局を接続し、２局及び３局を介して４局を接続している。
【００１９】
各々の従属ノード３００は、トークンを保持している時間内のみデータを送信することが許される。
【００２０】
図２は、本実施の形態に係る通信システム１００の他の構成例を示すブロック図である。
【００２１】
図２の例において、通信システム１００は、ツリー型のシステム構成をとっている。通信システム１００は、図１の例と同じく１つの主ノード２００（１局）と複数の従属ノード３００（２局〜６局）から構成され、ノード間は伝送路１０１によってピアツーピアで接続されている。図１のライン型のシステム構成の場合と異なり、３つ以上のノードとピアツーピアで接続されるノード（２局及び３局）を含んでいる。
【００２２】
図２の例では、主ノード２００である１局は、従属ノード３００である２局〜６局のうち、２局を直接接続している。また、２局を介して３局及び５局を接続し、２局及び３局を介して４局及び６局を接続している。
【００２３】
図３は、主ノード２００の構成を示すブロック図である。
【００２４】
図３において、主ノード２００には、他のノードと接続するためのポート２０１ａ，ｂ、巡回路情報２０２を保持する巡回路生成部２０３、フレーム判定部２０４、トークン解析部２０５、接続情報２０６を保持する接続情報保持部２０７、参照構造生成部２０８、参照構造保持部２０９が含まれる。巡回路生成部２０３、接続情報保持部２０７、参照構造生成部２０８、参照構造保持部２０９は、巡回路生成装置４００を構成している。巡回路生成装置４００は、主ノード２００及び従属ノード３００に対し、トークンを巡回させる経路である巡回路を生成する（設定する）装置である。主ノード２００の各部の動作については後述する。
【００２５】
図示していないが、主ノード２００は、処理装置、記憶装置、入力装置、出力装置等のハードウェアを備える。ハードウェアは主ノード２００の各部によって利用される。例えば、処理装置は、主ノード２００の各部でデータや情報の演算、加工、読み取り、書き込み等を行うために利用される。記憶装置は、そのデータや情報（例えば、巡回路情報２０２、接続情報２０６）を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。
【００２６】
なお、図３では、主ノード２００が２つのポートを持つ場合を示しているが、主ノード２００は３つ以上のポートを持っていてもよい。また、主ノード２００が巡回路生成装置４００を備える場合を示しているが、従属ノード３００が巡回路生成装置４００を備えていてもよいし、通信システム１００が、主ノード２００及び従属ノード３００とは別の装置として巡回路生成装置４００を備えていてもよい。
【００２７】
図４は、従属ノード３００の構成を示すブロック図である。
【００２８】
図４において、従属ノード３００には、トークン解析部３０１、フレーム判定部３０２、ポート３０３ａ，ｂが含まれる。従属ノード３００の各部の動作については後述する。
【００２９】
図示していないが、従属ノード３００は、処理装置、記憶装置、入力装置、出力装置等のハードウェアを備える。ハードウェアは従属ノード３００の各部によって利用される。例えば、処理装置は、従属ノード３００の各部でデータや情報の演算、加工、読み取り、書き込み等を行うために利用される。記憶装置は、そのデータや情報を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。
【００３０】
なお、図４では、従属ノード３００が２つのポートを持つ場合を示しているが、従属ノード３００は３つ以上のポートを持っていてもよい。
【００３１】
図５は、主ノード２００及び従属ノード３００それぞれのハードウェア構成の一例を示す図である。
【００３２】
図５において、主ノード２００（あるいは従属ノード３００）は、コンピュータであり、ＬＣＤ９０１（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ９０６といったハードウェアデバイスを備えている。これらのハードウェアデバイスはケーブルや信号線で接続されている。ＬＣＤ９０１の代わりに、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）、あるいは、その他の表示装置が用いられてもよい。マウス９０３の代わりに、タッチパネル、タッチパッド、トラックボール、ペンタブレット、あるいは、その他のポインティングデバイスが用いられてもよい。
【００３３】
主ノード２００（あるいは従属ノード３００）は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）を備えている。ＣＰＵ９１１は、処理装置の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、ＬＣＤ９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ９０６、ＨＤＤ９２０（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）と接続され、これらのハードウェアデバイスを制御する。ＨＤＤ９２０の代わりに、フラッシュメモリ、光ディスク装置、メモリカードリーダライタ又はその他の記憶媒体が用いられてもよい。
【００３４】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、ＨＤＤ９２０は、不揮発性メモリの一例である。これらは、記憶装置の一例である。通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５は、入力装置の一例である。また、通信ボード９１５、ＬＣＤ９０１、プリンタ９０６は、出力装置の一例である。
【００３５】
通信ボード９１５は、伝送路１０１に接続されている。
【００３６】
ＨＤＤ９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」として説明する機能を実行するプログラムが含まれている。プログラムは、ＣＰＵ９１１により読み出され実行される。ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（識別子）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として含まれている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶される。ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理（動作）に用いられる。抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３７】
本実施の形態の説明において用いるブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示す。データや信号は、ＲＡＭ９１４等のメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、ＨＤＤ９２０の磁気ディスク、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）、あるいは、その他の記録媒体に記録される。また、データや信号は、バス９１２、信号線、ケーブル、あるいは、その他の伝送媒体により伝送される。
【００３８】
本実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。即ち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアのみ、あるいは、素子、デバイス、基板、配線といったハードウェアのみで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアとハードウェアとの組み合わせ、あるいは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、フレキシブルディスク、コンパクトディスク、磁気ディスク、光ディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」としてコンピュータを機能させるものである。あるいは、プログラムは、本実施の形態の説明で述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００３９】
図６は、主ノード２００の接続情報保持部２０７で保持される接続情報２０６の一例を示すテーブルである。
【００４０】
図６の例において、接続情報２０６は、ノードごとに、主ノード２００がある側を親側としたときの親ノードと子ノード、トークン巡回順を優先するノード（即ち、優先ノード）であるか、主ノード２００からのホップ数を示している。親ノードが未記入のノードは、主ノード２００であることを示している。接続情報２０６には、ポートの接続関係も記載されている。図６の例では、ポートをＰで示し、Ｐｎ＝Ｘ局：Ｐｍは、ポートＰｎがＸ局のポートＰｍと接続していることを表している。図６の例は、図１の例に示した接続関係を表現しており、１局が主ノード２００であり、２局〜４局が従属ノード３００である。また、３局が優先ノードである。接続情報保持部２０７が保持する接続情報２０６は、予め主ノード２００に設定していてもよいし、ネットワーク起動（通信システム１００の初期化処理）時に、接続情報保持部２０７が動的に従属ノード３００とのインタラクションによって情報収集をすることで生成してもよい。
【００４１】
上記のように、接続情報２０６は、複数の従属ノード３００と主ノード２００との接続関係を定義する情報である。また、接続情報２０６は、他の従属ノード３００より優先してトークンの巡回先となる従属ノード３００を優先ノードとして定義する情報である。接続情報２０６は、接続情報保持部２０７によって記憶装置（例えば、主ノード２００の記憶装置）に予め保持される。
【００４２】
図７は、主ノード２００の巡回路生成部２０３で出力される巡回路情報２０２の一例を示すテーブルである。
【００４３】
図７の例において、巡回路情報２０２には、トークンの巡回順にノードが記されている。図７の例は、図６の例に示した接続情報２０６に基づいて生成される巡回路を表現しており、主ノード２００である１局を起点として、優先ノードである３局、優先ノード以外の従属ノード３００である４局、２局を経て、主ノード２００である１局を終点とする巡回路を示している。即ち、トークンが１局→３局→４局→２局→１局の順で巡回し、データ送信が行われることを示している。巡回路生成部２０３は、参照構造生成部２０８に対し、後述する処理手順を実行させ、実行結果として参照構造保持部２０９により保持されるデータ（後述する参照構造）に基づいて、上記のような巡回路を生成する。
【００４４】
上記のように、巡回路情報２０２は、巡回路生成部２０３が接続情報保持部２０７により保持された接続情報２０６を参照して生成した巡回路を定義する情報である。巡回路情報２０２は、巡回路生成部２０３によって出力される。
【００４５】
後述するように、巡回路生成部２０３は、優先ノードを介して主ノード２００に接続された従属ノード３００（以下、子ノードという）がある場合、その優先ノードの次に子ノードに対してトークンを巡回させてから、残りの従属ノード３００に対してトークンを巡回させる経路を巡回路として処理装置により生成する。図６の例では、従属ノード３００である２局が、優先ノードである３局を介して主ノード２００である１局に接続されているため、子ノードに該当する。よって、巡回路生成部２０３は、優先ノードである３局、子ノードである２局、残りの従属ノード３００である４局の順にトークンを巡回させる経路を巡回路として生成する。この巡回路を定義したものが、図７に示した巡回路情報２０２である。
【００４６】
また、巡回路生成部２０３は、接続情報保持部２０７により保持された接続情報２０６で複数の優先ノードが定義されている場合、それらの優先ノードのうち、主ノード２００との間に接続された従属ノード３００の数（以下、ホップ数という）が最も多い優先ノード（以下、最遠ノードという）の前に（即ち、最遠ノードより先に）最遠ノード以外の優先ノードに対してトークンを巡回させ、最遠ノードの次に、最遠ノードを介して主ノード２００に接続された従属ノード３００（即ち、子ノード）に対してトークンを巡回させてから、残りの従属ノード３００に対してトークンを巡回させる経路を巡回路として生成する。
【００４７】
また、巡回路生成部２０３は、最遠ノードと主ノード２００との間に接続された従属ノード３００がある場合、当該従属ノード３００のうち、ホップ数が多い従属ノード３００から順番に（以下、それぞれを対象ノードという）、対象ノードと対象ノードを介して主ノード２００に接続された従属ノード３００とに対してトークンを巡回させてから、残りの従属ノード３００に対してトークンを巡回させる経路を巡回路として生成する。
【００４８】
図８は、主ノード２００の参照構造生成部２０８の動作を示すフローチャートである。
【００４９】
図８において、参照構造生成部２０８は、接続情報保持部２０７により記憶装置に保持された接続情報２０６を参照し、主ノード２００を選択する（Ｓ１０１）。図６の例では、１局を選択する。
【００５０】
なお、参照構造生成部２０８は、全てのノードについて予め、あるいは、個別のノードについてノードを初めて選択する際に、ノードが持つポートごとにポート状態データを処理装置により生成し、記憶装置に記憶するものとする。ポート状態データは、ポートにマークが付与されているか否かを示し、マークが付与されていれば、そのマークを示すデータである。マークには、＊マークとＵマークと（優先ノードホップ数，ノードホップ数）マークとの３種類がある。＊マークは、子ノードに接続されているポートに付与されるマークである。Ｕマークは、親ノードに接続されているポートに付与されるマークである。（優先ノードホップ数，ノードホップ数）マークは、＊マークが付与されたポートに後から付与されるマークであり、そのポートを持つノード及びそのポートに接続されているノードの中に優先ノードがあれば、主ノード２００からのホップ数が最大となる優先ノードのホップ数を優先ノードホップ数として示す。優先ノードがなければ、優先ノードホップ数はＮＵＬＬ（以下では「−」で示す）とする。また、そのポートを持つノード及びそのポートに接続されているノードのうち、主ノード２００からのホップ数が最大となるノードのホップ数をノードホップ数として示す。参照構造生成部２０８は、ポートにマークを付与する場合、そのポートのポート状態データを処理装置により更新するものとする。
【００５１】
参照構造生成部２０８は、マークが付いていないポート（マークなしポート）があるかどうかを判定する（Ｓ１０２）。ある場合には、マークなしポートを選択し、＊マークを付ける（Ｓ１０３）。図６の例では、１局のポートＰ１に＊マークを付ける。
【００５２】
参照構造生成部２０８は、ポート単位で参照構造を生成し、選択したノードが基点となるように参照構造に登録して、引き続き操作する対象とする（Ｓ１０４）。図６の例では、１局のポートＰ１の参照構造に「１局」を登録し、「１局」と設定する。
【００５３】
なお、参照構造とは、あるポートについて、そのポートを持つノードから、そのポートを利用して通信可能な経路を示すデータをいう。参照構造は、参照構造保持部２０９によって記憶装置に保持される。参照構造生成部２０８は、参照構造にノードを登録する処理を処理装置により行う。
【００５４】
参照構造生成部２０８は、Ｓ１０３で選択したポートと接続しているノードを選択する（Ｓ１０５）。図６の例では、２局を選択する。
【００５５】
参照構造生成部２０８は、Ｓ１０５で選択したノードにおいて、Ｓ１０３で選択したポートと接続しているポートにＵマークを付ける（Ｓ１０６）。図６の例では、２局のポートＰ１にＵマークを付ける。
【００５６】
参照構造生成部２０８は、Ｓ１０５で選択したノードにおいて、マークなしポートがあるかどうかを判定する（Ｓ１０２）。ある場合には、上記のように、Ｓ１０３からＳ１０６までの処理を行う。図６の例では、Ｓ１０２からＳ１０６までの処理を繰り返して、２局のポートＰ２、３局のポートＰ２に＊マークを付けるとともに、３局のポートＰ１、４局のポートＰ１にＵマークを付ける。また、２局のポートＰ２の参照構造に「２局」を登録し、「２局」と設定する。また、３局のポートＰ２の参照構造に「３局」を登録し、「３局」と設定する。なお、この時点で選択中のノードは４局である。
【００５７】
参照構造生成部２０８は、Ｓ１０２でマークなしポートがない場合には、Ｕマーク以外のマークが付いているポートがあるかどうかを判定する（Ｓ１０７）。ない場合には、選択中のノードを登録対象として記憶装置に記憶する。図６の例では、４局はＵマークが付いているポート（Ｕマーク付ポート）しか持っていないため、「４局」を登録対象として記憶する。
【００５８】
参照構造生成部２０８は、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせを記憶装置に記憶する（Ｓ１１１）。このとき、選択中のノードのどのポートにも（優先ノードホップ数，ノードホップ数）マークがない場合には、そのノードのホップ数をそれぞれ優先ノードホップ数とノードホップ数の組み合わせとして記憶する。選択中のノードが優先ノードでない場合には、優先ノードホップ数はＮＵＬＬとなる。例えば、選択中のノードが優先ノードであり、ホップ数が３であれば（３，３）、優先ノードでなく、ホップ数が２であれば（−，２）の組み合わせを記憶する。一方、選択中のノードのポートに（優先ノードホップ数，ノードホップ数）マークがある場合には、マークが付されている全てのポートの優先ノードホップ数と選択中のノードの優先ノードホップ数とのうち、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせを記憶する。優先ノードホップ数が同じものがあれば、ノードホップ数が最大となる組み合わせを記憶する。このとき、優先ノードホップ数がＮＵＬＬであれば、優先ノードホップ数が０であるとみなす。例えば、（２，２）というマークが付されたポートと（３，４）というマークが付されたポートがあり、選択中のノードが優先ノードでなく、ホップ数が１であれば（３，４）の組み合わせを記憶する。また、（２，２）というマークが付されたポートと（−，４）というマークが付されたポートがあり、選択中のノードが優先ノードでなく、ホップ数が１であれば（２，２）の組み合わせを記憶する。また、（−，２）というマークが付されたポートと（−，４）というマークが付されたポートがあり、選択中のノードが優先ノードでなく、ホップ数が１であれば（−，４）の組み合わせを記憶する。図６の例では、４局は（優先ノードホップ数，ノードホップ数）マークが付いているポートを持っておらず、４局のホップ数が３であるため、（−，３）の組み合わせを記憶する。
【００５９】
参照構造生成部２０８は、Ｓ１１１でホップ数の組み合わせを記憶した後、Ｕマーク付ポートを選び、選んだポートに接続しているノードを選択する（Ｓ１１２）。図６の例では、４局のポートＰ１に接続されている３局を選択する。
【００６０】
参照構造生成部２０８は、Ｓ１１２で選択したノードにおいて、Ｓ１１２で選んだＵマーク付ポートと接続しているポートに付いている＊マークを、Ｓ１１１で記憶した（優先ノードホップ数，ノードホップ数）マークに変更する（Ｓ１１３）。図６の例では、３局のポートＰ２の＊マークを（−，３）マークに変更する。
【００６１】
参照構造生成部２０８は、Ｓ１１３で（優先ノードホップ数，ノードホップ数）マークを付けたポートの参照構造を選択し、選択した参照構造に、Ｓ１０８で登録対象として記憶したノード、又は、後述するＳ１１０で登録対象として記憶した参照構造を登録する（Ｓ１１４）。なお、参照構造を登録する際に同じノードが連続する場合は、１つにまとめる（例えば、「２局→３局→３局」となる場合は、「２局→３局」とする）。図６の例では、３局のポートＰ２の参照構造に「４局」を登録し、「３局→４局」と設定することになる。
【００６２】
参照構造生成部２０８は、Ｓ１１４で選択した参照構造に、続けて、選択中のノードを登録する（Ｓ１１５）。図６の例では、３局のポートＰ２の参照構造に「３局」を登録し、「３局→４局→３局」と設定することになる。
【００６３】
参照構造生成部２０８は、選択中のノードが主ノード２００であるかを判定し（Ｓ１１６）、主ノード２００でなければ、Ｓ１０２から処理を繰り返す。図６の例では、３局は主ノード２００ではないため、Ｓ１０２、Ｓ１０７の処理を行う。
【００６４】
参照構造生成部２０８は、Ｓ１０７でＵマーク以外のマークが付いているポートがある場合には、ポートごとに設けている参照構造を、優先ノードホップ数が小さい順に並べる（Ｓ１０９）。優先ノードホップ数が同じ場合には、ノードホップ数が小さい順に並べる。このとき、優先ノードホップ数がＮＵＬＬのポートがあれば、先に優先ノードホップ数がＮＵＬＬでないポートの参照構造を並べ、それに続けて、優先ノードホップ数がＮＵＬＬのポートの参照構造を並べる。参照構造生成部２０８は、Ｓ１０９で並べた参照構造を、登録対象として記憶装置に記憶する（Ｓ１１０）。図６の例では、３局はＵマーク付ポートを１つ（ポートＰ２）しか持っていないため、単に３局のポートＰ２の参照構造「３局→４局→３局」を登録対象として記憶する。その後、Ｓ１１１で３局は優先ノードであり、ホップ数が２であるため、（２，２）の組み合わせを記憶する。そして、Ｓ１１２からＳ１１５までの処理を行って、２局のポートＰ２の＊マークを（２，２）マークに変更するとともに、２局のポートＰ２の参照構造に「３局→４局→３局」を登録し、「２局→３局→４局→３局」と設定する。続いて、Ｓ１１６で２局は主ノード２００ではないため、Ｓ１０２からＳ１１５の処理を行って、１局のポートＰ１の＊マークを（２，２）マークに変更するとともに、１局のポートＰ１の参照構造に「２局→３局→４局→３局」及び「２局」を登録し、「１局→２局→３局→４局→３局→２局」と設定する。
【００６５】
参照構造生成部２０８は、Ｓ１１６で選択中のノードが主ノード２００であれば、マークなしポートがあるかどうかを判定し（Ｓ１１７）、ある場合には、Ｓ１０２から処理を繰り返す。参照構造生成部２０８は、Ｓ１１７でマークなしポートがない場合には、全てのポートについて、参照構造を作成したことになる。図６の例では、１局は主ノード２００であり、マークなしポートがないため、１局のポートＰ１の参照構造である「１局→２局→３局→４局→３局→２局」を作成したことになる。
【００６６】
参照構造生成部２０８は、ここまでに作成した参照構造を最終形態にするために、次の手順をとる。
【００６７】
まず、参照構造生成部２０８は、優先ノードホップ数が小さい順に主ノード２００の全てのポートの参照構造をつなぐ（Ｓ１１８）。優先ノードホップ数が同じ場合には、ノードホップ数が小さい順につなぐ。このとき、主ノード２００のポートのうち、優先ノードを持たないポートの参照構造は無視する。なお、参照構造をつなぐ際に同じノードが連続する場合は、１つにまとめる（例えば、「２局→３局→３局」となる場合は、「２局→３局」とする）。図６の例では、１局はポートを１つ（ポートＰ１）しか持っていないため、最終形態の参照構造は「１局→２局→３局→４局→３局→２局」のままとなる（例えば、１局の別のポートの参照構造があれば、１局のポートＰ１の参照構造とつなぐ必要がある）。
【００６８】
次に、参照構造生成部２０８は、主ノード２００のポートに付けられている（優先ノードホップ数，ノードホップ数）マークを比較し、最大の優先ノードホップ数を持つポートを除き、残りのポートのうち優先ノードホップ数が記述されているポートの参照構造を、Ｓ１１８で作成した最終形態に続くようにつなぐ（Ｓ１１９）。なお、参照構造をつなぐ際に同じノードが連続する場合は、前述したように、１つにまとめる。図６の例では、１局はポートを１つ（ポートＰ１）しか持っておらず、１局のポートＰ１が最大の優先ノードホップ数を持つポートとなるため、最終形態の参照構造は「１局→２局→３局→４局→３局→２局」のままとなる（例えば、１局の別のポートの参照構造があれば、このポートとポートＰ１とのうち、最大の優先ノードホップ数を持つポートの参照構造以外の参照構造を、Ｓ１１８でつないだ参照構造につなぐ必要がある）。
【００６９】
最後に、参照構造生成部２０８は、主ノード２００の全てのポートが優先ノードを持つ場合を除き、優先ノードを持たないポートの参照構造を、Ｓ１１９で作成した最終形態に続くようにつなぎ（Ｓ１２０）、終了する。なお、参照構造をつなぐ際に同じノードが連続する場合は、前述したように、１つにまとめる。図６の例では、１局はポートを１つ（ポートＰ１）しか持っておらず、優先ノードを持たないポートが存在しないため、最終形態の参照構造は「１局→２局→３局→４局→３局→２局」のままとなる。
【００７０】
前述したように、以上の手順でＳ１２０までに参照構造生成部２０８が作成した参照構造は、主ノード２００の参照構造保持部２０９により記憶装置に保持される。
【００７１】
図９は、主ノード２００の巡回路生成部２０３の動作を示すフローチャートである。
【００７２】
図９において、巡回路生成部２０３は、参照構造保持部２０９から、最終形態の参照構造の基点から順番にノードを選択する（Ｓ２０１）。巡回路生成部２０３は、Ｓ２０１で選択したノードが巡回路情報２０２に記載されているか判定し（Ｓ２０２）、記載されている場合には参照構造から次のノードを得る（Ｓ２０１）。Ｓ２０２で記載されていない場合には、巡回路生成部２０３は、巡回路情報２０２と接続情報保持部２０７により保持されている接続情報２０６とを基に、巡回路情報２０２に記載されていない優先ノードが残っているかどうかを判定する（Ｓ２０３）。Ｓ２０３で残っていない場合には、巡回路生成部２０３は、Ｓ２０１で選択したノードを巡回路の末尾に登録する（Ｓ２０４）。続いて、巡回路生成部２０３は、全ノードが巡回路に登録されたかどうかを判定して（Ｓ２０５）、登録された場合には巡回路情報を各ノードに設定して終了する。Ｓ２０５で全ノードが巡回路に登録されていない場合には、Ｓ２０１から手順を繰り返す。Ｓ２０３の判定で巡回路情報２０２に記載されていない優先ノードがある場合には、巡回路生成部２０３は、Ｓ２０１で選択したノードが巡回路情報２０２に記載されていない優先ノードであるかどうかを判定し（Ｓ２０６）、記載されていない優先ノードである場合には、巡回路生成部２０３は、ノードを巡回路の末尾に登録し（Ｓ２０４）、全ノードが巡回路に登録されたかどうかを判定する（Ｓ２０５）。Ｓ２０６で巡回路情報２０２に記載されている優先ノードではないと判定した場合には、Ｓ２０１から手順を繰り返す。
【００７３】
図６の例では、参照構造保持部２０９によって記憶装置に保持されている最終形態の参照構造は、「１局→２局→３局→４局→３局→２局」である。そのため、巡回路生成部２０３は、まず、優先ノードである３局を巡回路の末尾に登録する。続けて、３局の次にある４局を巡回路の末尾に登録する。４局の次は３局であるが、登録済なので、その次にある２局を巡回路の末尾に登録する。このようにして、トークンを１局→３局→４局→２局→１局の順に巡回させる巡回路が生成され、図７に示した巡回路情報２０２が巡回路生成部２０３によって記憶装置に書き込まれる。
【００７４】
巡回路の作成完了後に各ノードに行う設定手順は次のようになる。
【００７５】
巡回路生成部２０３は、トークン解析部２０５に対し、トークン巡回に関わるノードの情報を設定する。このとき設定するノードの情報はトークンの巡回に利用可能な情報であればよく、例えば、次にトークンを巡回させる先のノード、自ノードへのトークンの送信元となるノード、自ノードの前後のノードのいずれを示す情報でもよい。ただし、全てのノードで同じ規則に基づいていることが望ましい。巡回路生成部２０３は、主ノード２００が持つポート２０１ａ，ｂを介して従属ノード３００と通信を行うことで、従属ノード３００に対し、トークン巡回に関わるノードの情報を設定する。従属ノード３００は、従属ノード３００が持つポート３０３ａ（又はポート３０３ｂ）及びフレーム判定部３０２を介して、トークン解析部３０１に対し、トークン巡回に関わるノードの情報を設定する。
【００７６】
上記のように、本実施の形態では、巡回路生成装置４００が主ノード２００に実装されている（即ち、主ノード２００となる通信装置である）ため、巡回路生成部２０３は、主ノード２００の記憶装置に対し、巡回路情報２０２を書き込む。また、巡回路生成部２０３は、各々の従属ノード３００に対し、巡回路情報２０２で定義された巡回路を設定するための情報を送信する。
【００７７】
図１０は、主ノード２００のフレーム判定部２０４の動作を示すフローチャートである。
【００７８】
図１０において、フレーム判定部２０４は、ポートからフレームを受信すると（Ｓ３０１）、受信したフレームの種別を判定し（Ｓ３０２）、データであれば通信アプリケーションに渡す（Ｓ３０３）。フレーム判定部２０４は、Ｓ３０２の判定で制御フレームの場合には、制御フレームの種類を判定し（Ｓ３０４）、トークンであればトークン解析部２０５に渡す（Ｓ３０５）。フレーム判定部２０４は、Ｓ３０４の判定で、接続情報２０６であれば、接続情報保持部２０７に渡す（Ｓ３０６）。
【００７９】
図１１は、従属ノード３００のフレーム判定部３０２の動作を示すフローチャートである。
【００８０】
図１１において、フレーム判定部３０２は、ポートからフレームを受信すると（Ｓ４０１）、受信したフレームの種別を判定し（Ｓ４０２）、データであれば通信アプリケーションに渡す（Ｓ４０３）。フレーム判定部３０２は、Ｓ４０２の判定でトークンの場合には、トークン解析部３０１に渡す（Ｓ４０４）。
【００８１】
図１２は、主ノード２００のトークン解析部２０５及び従属ノード３００のトークン解析部３０１の動作を示すフローチャートである。
【００８２】
図１２において、主ノード２００のトークン解析部２０５（あるいは従属ノード３００のトークン解析部３０１）は、主ノード２００のフレーム判定部２０４（あるいは従属ノード３００のフレーム判定部３０２）からトークンを受け取ると（Ｓ５０１）、トークン解析部２０５（あるいはトークン解析部３０１）に設定されたトークン巡回設定を基に次ノード宛のトークンを準備する（Ｓ５０２）。トークン解析部２０５（あるいはトークン解析部３０１）は、トークンと、トークンの宛先を含む送信指示をポートに渡し（Ｓ５０３）、再度トークンを受け取る（Ｓ５０１）まで待つ。
【００８３】
以下では、ネットワーク（即ち、通信システム１００）にノードが追加された場合の主ノード２００の動作を、図８を部分的に用いて説明する。
【００８４】
ネットワークにノードが追加された場合には、例えば、主ノード２００のポートを経由して接続情報保持部２０７で保持する接続情報２０６が変更となる。主ノード２００の参照構造生成部２０８は、追加となったノードを接続したノード及びそのポートを判別する。参照構造生成部２０８は、判定した結果、追加ノードを接続したノードを選択する。追加ノードを接続したポートはマークが付いていないので、参照構造生成部２０８は、Ｓ１０２からの手順に従い、マークが付いていないポートとして選択し、＊マークを付ける。参照構造生成部２０８は、ポート単位で参照構造を生成し、選択したノードが基点となるように参照構造に登録して、引き続き操作する対象とする（Ｓ１０３）。以降の手順は図８に従うが、Ｓ１１６の判定が異なる。参照構造生成部２０８は、Ｓ１１６では主ノード２００であるかを判定したが、ノード追加時は、追加ノードを接続したノードであるかを判定する。参照構造生成部２０８は、追加ノードを接続したノードである場合には、参照構造の生成を停止する。参照構造生成部２０８は、新たに生成した参照構造を基に、既に参照構造保持部２０９に保持している参照構造を次のように変更する。
【００８５】
まず、参照構造生成部２０８は、追加ノードを接続したノードを参照構造から検索する。参照構造生成部２０８は、検索したノード（追加ノードを接続したノード）の手前に、新たに生成した参照構造を挿入する。このとき、参照構造を挿入する際に同じノードが連続する場合は、１つにまとめる。例えば、既存の参照構造として、「１局→２局→３局→２局」があったときに、３局に４局が接続された場合、新たに生成される参照構造は「３局→４局→３局」となる。参照構造生成部２０８は、新たに生成した参照構造を既存の参照構造に挿入すると、追加ノードを接続したノードである３局の前に新たに生成した参照構造を挿入するので、「１局→２局→３局→４局→３局→２局」となる。
【００８６】
以下では、ネットワークからノードが削除された場合の主ノード２００の動作を説明する。
【００８７】
ネットワークからノードが削除された場合には、主ノード２００のポートを経由して接続情報保持部２０７で保持する接続情報２０６が変更となる。主ノード２００の参照構造生成部２０８は、削除となったノードが接続されていたノード及びそのポートを判別する。参照構造生成部２０８は、既に参照構造保持部２０９に保持している参照構造を次のように変更する。
【００８８】
まず、参照構造生成部２０８は、削除されたノードが接続していたノードを参照構造から検索する。参照構造生成部２０８は、削除されたノードが接続していたポートに対応した参照構造を消去する。参照構造生成部２０８は、最終形態となっている参照構造では、削除されたノードが接続していたノードから削除されたノードへつながっている個所を検索し、削除されたノードからそれ以降に現れる削除されたノードが接続していたノードまでを削除する。例えば、既存の参照構造として、「１局→２局→３局→２局」があった場合、３局が削除されたとすると、削除されたノードが接続していたノードから削除されたノードへつながっている個所は、「３局→２局」の部分であり、これを削除すると参照構造は「１局→２局」となる。
【００８９】
以上説明したように、本実施の形態に係る通信方式には、以下のような特徴がある。
・１台の主ノード２００が、トークン巡回順序を決定し、主ノード２００以外のノードに巡回順序設定を送付する。各ノードは設定された順序でトークンを巡回させ、トークン受信時に送信権を得る。
【００９０】
また、主ノード２００は、参照構造生成部２０８と巡回路生成部２０３を持つ。参照構造を作成した後、参照構造に基づいてトークン巡回路を決定する。各ノードに決定した巡回路を設定するための情報を送付する。
【００９１】
上記参照構造は、ノードの接続関係、有効になっているポート数、トークンを先に送付するノードである優先ノードの一覧、優先ノードと主ノード２００間のホップ数及びノードと主ノード２００間のホップ数を基に決定する。
【００９２】
実施の形態２．
実施の形態１の説明において、巡回路生成装置４００が図１の通信システム１００の主ノード２００に実装されており、接続情報２０６が図６のようなものであった場合、巡回路生成装置４００は図７の巡回路情報２０２のように定義される巡回路を生成することを示した。以下では、実施の形態２として、別の例を示す。
【００９３】
図１３は、本実施の形態に係る通信システム１００の構成例を示すブロック図である。
【００９４】
図１３の例において、通信システム１００は、１つの主ノード２００（２局）と８つの従属ノード３００（１局、３局〜９局）から構成され、ノード間は伝送路１０１によって接続されている。
【００９５】
図１３の例では、主ノード２００である２局は、従属ノード３００である１局、３局〜９局のうち、１局、３局、６局を直接接続している。また、３局を介して４局及び７局を接続し、３局及び４局を介して５局及び８局を接続し、６局を介して９局を接続している。
【００９６】
図１４は、主ノード２００の接続情報保持部２０７で保持される接続情報２０６の一例を示すテーブルである。
【００９７】
図１４の例は、図１３の例に示した接続関係を表現しており、２局が主ノード２００であり、１局、３局〜９局が従属ノード３００である。また、３局、８局、９局が優先ノードである。
【００９８】
以下、図８を用いて、図１４の例における主ノード２００の参照構造生成部２０８の動作について説明する。
【００９９】
参照構造生成部２０８は、接続情報保持部２０７により記憶装置に保持された接続情報２０６を参照し、主ノード２００である２局を選択する（Ｓ１０１）。２局にはマークなしポート（ポートＰ１〜Ｐ３）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ１を選択し、＊マークを付ける（Ｓ１０３）。なお、参照構造生成部２０８は、ポートＰ２あるいはＰ３を選択してもよい。Ｓ１０３の後、参照構造生成部２０８は、２局のポートＰ１の参照構造を生成し、「２局」を登録して「２局」と設定する（Ｓ１０４）。参照構造生成部２０８は、２局のポートＰ１と接続しているノードである１局を選択する（Ｓ１０５）。参照構造生成部２０８は、１局において２局のポートＰ１と接続しているポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１００】
Ｓ１０５で選択した１局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク付ポート（ポートＰ１）しかないため（Ｓ１０７でＮＯ）、参照構造生成部２０８は、「１局」を登録対象として記憶装置に記憶する（Ｓ１０８）。１局には（優先ノードホップ数，ノードホップ数）マークが付いているポートがないため、参照構造生成部２０８は、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（−，１）の組み合わせを記憶装置に記憶する（Ｓ１１１）。ここで、優先ノードホップ数が「−」となるのは、１局が優先ノードではないからである。ノードホップ数が「１」となるのは、１局のホップ数が１だからである。Ｓ１１１の後、参照構造生成部２０８は、Ｕマーク付ポートである１局のポートＰ１を選び、１局のポートＰ１に接続しているノードである２局を選択する（Ｓ１１２）。参照構造生成部２０８は、Ｓ１１２で選択した２局において、Ｓ１１２で選んだＵマーク付ポートと接続しているポートＰ１に付いている＊マークを、Ｓ１１１で記憶した（−，１）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、２局のポートＰ１の参照構造「２局」に、Ｓ１０８で登録対象として記憶した「１局」を登録し（Ｓ１１４）、さらに、Ｓ１１２で選択した「２局」を登録して「２局→１局→２局」と設定する（Ｓ１１５）。
【０１０１】
Ｓ１１２で選択した２局は主ノード２００であるが（Ｓ１１６でＹＥＳ）、２局にはマークなしポート（ポートＰ２及びＰ３）があるため（Ｓ１１７及びＳ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ２を選択し、＊マークを付ける（Ｓ１０３）。なお、参照構造生成部２０８は、ポートＰ３を選択してもよい。Ｓ１０３の後、参照構造生成部２０８は、２局のポートＰ２の参照構造を「２局」と設定し（Ｓ１０４）、３局を選択し（Ｓ１０５）、３局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１０２】
Ｓ１０５で選択した３局にはマークなしポート（ポートＰ２及びＰ３）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ２を選択し、＊マークを付ける（Ｓ１０３）。なお、参照構造生成部２０８は、ポートＰ３を選択してもよい。Ｓ１０３の後、参照構造生成部２０８は、３局のポートＰ２の参照構造を「３局」と設定し（Ｓ１０４）、４局を選択し（Ｓ１０５）、４局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１０３】
Ｓ１０５で選択した４局にはマークなしポート（ポートＰ２及びＰ３）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ２を選択し、＊マークを付ける（Ｓ１０３）。なお、参照構造生成部２０８は、ポートＰ３を選択してもよい。Ｓ１０３の後、参照構造生成部２０８は、４局のポートＰ２の参照構造を「４局」と設定し（Ｓ１０４）、５局を選択し（Ｓ１０５）、５局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１０４】
Ｓ１０５で選択した５局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク付ポート（ポートＰ１）しかないため（Ｓ１０７でＮＯ）、参照構造生成部２０８は、「５局」を登録対象として記憶装置に記憶し（Ｓ１０８）、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（−，３）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、５局のポートＰ１を選び、４局を選択し（Ｓ１１２）、４局のポートＰ２に付いている＊マークを（−，３）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、４局のポートＰ２の参照構造「４局」に「５局」を登録し（Ｓ１１４）、さらに、「４局」を登録して「４局→５局→４局」と設定する（Ｓ１１５）。
【０１０５】
Ｓ１１２で選択した４局は主ノード２００ではなく（Ｓ１１６でＮＯ）、４局にはマークなしポート（ポートＰ３）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ３を選択し、＊マークを付ける（Ｓ１０３）。参照構造生成部２０８は、４局のポートＰ３の参照構造を「４局」と設定し（Ｓ１０４）、８局を選択し（Ｓ１０５）、８局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１０６】
Ｓ１０５で選択した８局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク付ポート（ポートＰ１）しかないため（Ｓ１０７でＮＯ）、参照構造生成部２０８は、「８局」を登録対象として記憶装置に記憶する（Ｓ１０８）。８局には（優先ノードホップ数，ノードホップ数）マークが付いているポートがないため、参照構造生成部２０８は、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（３，３）の組み合わせを記憶装置に記憶する（Ｓ１１１）。ここで、優先ノードホップ数もノードホップ数も「３」となるのは、８局が優先ノードであり、ホップ数が３だからである。Ｓ１１１の後、参照構造生成部２０８は、８局のポートＰ１を選び、４局を選択し（Ｓ１１２）、４局のポートＰ３に付いている＊マークを（３，３）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、４局のポートＰ３の参照構造「４局」に「８局」を登録し（Ｓ１１４）、さらに、「４局」を登録して「４局→８局→４局」と設定する（Ｓ１１５）。
【０１０７】
Ｓ１１２で選択した４局は主ノード２００ではなく（Ｓ１１６でＮＯ）、４局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク以外のマークが付いているポート（ポートＰ２及びＰ３）があるため（Ｓ１０７でＹＥＳ）、参照構造生成部２０８は、ポートごとに設けている参照構造を、優先ノードホップ数が小さい順に並べ（Ｓ１０９）、登録対象として記憶装置に記憶する（Ｓ１１０）。ここでは、優先ノードホップ数がある（「３」である）４局のポートＰ３の参照構造「４局→８局→４局」が１番目、優先ノードホップ数がない（「−」である）４局のポートＰ２の参照構造「４局→５局→４局」が２番目に記憶される。Ｓ１１０の後、参照構造生成部２０８は、４局のポートＰ２に付いている（−，３）マークと４局のポートＰ３に付いている（３，３）マークと４局の優先ノードホップ数（ＮＵＬＬである）とのうち、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（３，３）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、４局のポートＰ１を選び、３局を選択し（Ｓ１１２）、３局のポートＰ２に付いている＊マークを（３，３）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、３局のポートＰ２の参照構造「３局」に「４局→８局→４局」と「４局→５局→４局」を順番に登録し（Ｓ１１４）、さらに、「３局」を登録して「３局→４局→８局→４局→５局→４局→３局」と設定する（Ｓ１１５）。
【０１０８】
Ｓ１１２で選択した３局は主ノード２００ではなく（Ｓ１１６でＮＯ）、３局にはマークなしポート（ポートＰ３）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ３を選択し、＊マークを付ける（Ｓ１０３）。参照構造生成部２０８は、３局のポートＰ３の参照構造を「３局」と設定し（Ｓ１０４）、７局を選択し（Ｓ１０５）、７局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１０９】
Ｓ１０５で選択した７局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク付ポート（ポートＰ１）しかないため（Ｓ１０７でＮＯ）、参照構造生成部２０８は、「７局」を登録対象として記憶装置に記憶し（Ｓ１０８）、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（−，２）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、７局のポートＰ１を選び、３局を選択し（Ｓ１１２）、３局のポートＰ３に付いている＊マークを（−，２）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、３局のポートＰ３の参照構造「３局」に「７局」を登録し（Ｓ１１４）、さらに、「３局」を登録して「３局→７局→３局」と設定する（Ｓ１１５）。
【０１１０】
Ｓ１１２で選択した３局は主ノード２００ではなく（Ｓ１１６でＮＯ）、３局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク以外のマークが付いているポート（ポートＰ２及びＰ３）があるため（Ｓ１０７でＹＥＳ）、参照構造生成部２０８は、ポートごとに設けている参照構造を、優先ノードホップ数が小さい順に並べ（Ｓ１０９）、登録対象として記憶装置に記憶する（Ｓ１１０）。ここでは、優先ノードホップ数がある（「３」である）３局のポートＰ２の参照構造「３局→４局→８局→４局→５局→４局→３局」が１番目、優先ノードホップ数がない（「−」である）３局のポートＰ３の参照構造「３局→７局→３局」が２番目に記憶される。Ｓ１１０の後、参照構造生成部２０８は、３局のポートＰ２に付いている（３，３）マークと３局のポートＰ３に付いている（−，２）マークと３局の優先ノードホップ数（１である）とのうち、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（３，３）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、３局のポートＰ１を選び、２局を選択し（Ｓ１１２）、２局のポートＰ２に付いている＊マークを（３，３）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、２局のポートＰ２の参照構造「２局」に「３局→４局→８局→４局→５局→４局→３局」と「３局→７局→３局」を順番に登録し（Ｓ１１４）、さらに、「２局」を登録して「２局→３局→４局→８局→４局→５局→４局→３局→７局→３局→２局」と設定する（Ｓ１１５）。
【０１１１】
Ｓ１１２で選択した２局は主ノード２００であるが（Ｓ１１６でＹＥＳ）、２局にはマークなしポート（ポートＰ３）があるため（Ｓ１１７及びＳ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ３を選択し、＊マークを付ける（Ｓ１０３）。参照構造生成部２０８は、２局のポートＰ３の参照構造を「２局」と設定し（Ｓ１０４）、６局を選択し（Ｓ１０５）、６局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１１２】
Ｓ１０５で選択した６局にはマークなしポート（ポートＰ２）があるため（Ｓ１０２でＹＥＳ）、参照構造生成部２０８は、ポートＰ２を選択し、＊マークを付ける（Ｓ１０３）。参照構造生成部２０８は、６局のポートＰ２の参照構造を「６局」と設定し（Ｓ１０４）、９局を選択し（Ｓ１０５）、９局のポートＰ１にＵマークを付ける（Ｓ１０６）。
【０１１３】
Ｓ１０５で選択した９局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク付ポート（ポートＰ１）しかないため（Ｓ１０７でＮＯ）、参照構造生成部２０８は、「９局」を登録対象として記憶装置に記憶し（Ｓ１０８）、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（２，２）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、９局のポートＰ１を選び、６局を選択し（Ｓ１１２）、６局のポートＰ２に付いている＊マークを（２，２）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、６局のポートＰ２の参照構造「６局」に「９局」を登録し（Ｓ１１４）、さらに、「６局」を登録して「６局→９局→６局」と設定する（Ｓ１１５）。
【０１１４】
Ｓ１１２で選択した６局は主ノード２００ではなく（Ｓ１１６でＮＯ）、６局にはマークなしポートがなく（Ｓ１０２でＮＯ）、Ｕマーク以外のマークが付いているポート（ポートＰ２）が１つだけあるため（Ｓ１０７でＹＥＳ）、参照構造生成部２０８は、単に６局のポートＰ２の参照構造「６局→９局→６局」を登録対象として記憶装置に記憶する（Ｓ１０９及びＳ１１０）。参照構造生成部２０８は、６局のポートＰ２に付いている（２，２）マークと６局の優先ノードホップ数（ＮＵＬＬである）とのうち、優先ノードホップ数が最大となる優先ノードホップ数とノードホップ数の組み合わせとして、（２，２）の組み合わせを記憶装置に記憶する（Ｓ１１１）。参照構造生成部２０８は、６局のポートＰ１を選び、２局を選択し（Ｓ１１２）、２局のポートＰ３に付いている＊マークを（２，２）マークに変更する（Ｓ１１３）。参照構造生成部２０８は、２局のポートＰ３の参照構造「２局」に「６局→９局→６局」を登録し（Ｓ１１４）、さらに、「２局」を登録して「２局→６局→９局→６局→２局」と設定する（Ｓ１１５）。
【０１１５】
Ｓ１１２で選択した２局は主ノード２００であり（Ｓ１１６でＹＥＳ）、２局にはマークなしポートがないため（Ｓ１１７でＮＯ）、この時点で、２局の全てのポートについて、参照構造を作成したことになる。
【０１１６】
参照構造生成部２０８は、優先ノードホップ数が小さい順に、２局のポートのうち、優先ノードを持たないポート（ポートＰ１）以外のポート（ポートＰ２及びＰ３）の参照構造をつなぎ、最終形態の参照構造「２局→６局→９局→６局→２局→３局→４局→８局→４局→５局→４局→３局→７局→３局→２局」を生成する（Ｓ１１８）。
【０１１７】
参照構造生成部２０８は、２局のポートのうち、優先ノードを持たないポート（ポートＰ１）及び最大の優先ノードホップ数を持つポート（ポートＰ３）以外のポート（ポートＰ２）の参照構造を、Ｓ１１８で生成した最終形態の参照構造につなぎ、最終形態の参照構造を「２局→６局→９局→６局→２局→３局→４局→８局→４局→５局→４局→３局→７局→３局→２局→６局→９局→６局→２局」と設定する（Ｓ１１９）。なお、この例で最終形態の参照構造につながれるのは１つのポート（ポートＰ２）の参照構造のみであるが、複数のポートの参照構造がつながれる場合、順番は任意である。
【０１１８】
参照構造生成部２０８は、２局のポートのうち、優先ノードを持たないポート（ポートＰ１）の参照構造を、Ｓ１１９で生成した最終形態の参照構造につなぎ、最終形態の参照構造を「２局→６局→９局→６局→２局→３局→４局→８局→４局→５局→４局→３局→７局→３局→２局→６局→９局→６局→２局→１局→２局」と設定し（Ｓ１２０）、終了する。
【０１１９】
図１５は、主ノード２００の巡回路生成部２０３で出力される巡回路情報２０２の一例を示すテーブルである。
【０１２０】
図１５の例において、巡回路情報２０２には、トークンの巡回順にノードが記されている。図１５の例は、図１４の例に示した接続情報２０６に基づいて生成される巡回路を表現しており、主ノード２００である２局を起点として、優先ノードである９局、３局、８局、優先ノード以外の従属ノード３００である４局、５局、７局、６局、１局を経て、主ノード２００である２局を終点とする巡回路を示している。即ち、トークンが２局→９局→３局→８局→４局→５局→７局→６局→１局→２局の順で巡回し、データ送信が行われることを示している。
【０１２１】
以下、巡回路生成部２０３が上記の巡回路を生成する手順について説明する。
【０１２２】
まず、巡回路生成部２０３は、参照構造生成部２０８に対し、前述した処理手順を実行させる。前述したように、実行結果として参照構造「２局→６局→９局→６局→２局→３局→４局→８局→４局→５局→４局→３局→７局→３局→２局→６局→９局→６局→２局→１局→２局」が得られる。巡回路生成部２０３は、この参照構造の先頭から優先ノードを順番に選択する（９局、３局、８局が順番に選択される）。続いて、巡回路生成部２０３は、最後に選択した優先ノードの次から未選択のノードを順番に選択する（４局、５局、７局、６局、１局が順番に選択される）。最後に、巡回路生成部２０３は、選択したノードを順番に並べて、上記の巡回路を生成する。
【符号の説明】
【０１２３】
１００  通信システム、１０１  伝送路、２００  主ノード、２０１ａ，ｂ  ポート、２０２  巡回路情報、２０３  巡回路生成部、２０４  フレーム判定部、２０５  トークン解析部、２０６  接続情報、２０７  接続情報保持部、２０８  参照構造生成部、２０９  参照構造保持部、３００  従属ノード、３０１  トークン解析部、３０２  フレーム判定部、３０３ａ，ｂ  ポート、９０１  ＬＣＤ、９０２  キーボード、９０３  マウス、９０４  ＦＤＤ、９０５  ＣＤＤ、９０６  プリンタ、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信ボード、９２０  ＨＤＤ、９２１  オペレーティングシステム、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群。
【図１】
2010233134.tif 000003
【図２】
2010233134.tif 000004
【図３】
2010233134.tif 000005
【図４】
2010233134.tif 000006
【図５】
2010233134.tif 000007
【図６】
2010233134.tif 000008
【図７】
2010233134.tif 000009
【図８】
2010233134.tif 000010
【図９】
2010233134.tif 000011
【図１０】
2010233134.tif 000012
【図１１】
2010233134.tif 000013
【図１２】
2010233134.tif 000014
【図１３】
2010233134.tif 000015
【図１４】
2010233134.tif 000016
【図１５】
2010233134.tif 000017