(57)【特許請求の範囲】
【請求項１】
複数の入力装置からのデータ転送要求を並列に検査し、転送許可を与える並列型の調停装置において、
各入力装置とその入力装置がデータ転送を許可された出力装置の組を表す行列であるただ１つの出力割付状況記録部と、
前記各入力装置から当該出力装置へのデータ転送要求の有無を一定の時間周期ごとにサンプリングする要求サンプリング部と、
前記要求サンプリング部のサンプリング結果を順次記録する転送要求時系列記録部と、
転送要求に対して定義される複数の優先度について当該出力装置への転送要求中に含まれる優先度を記録する優先度記録部と、
当該出力装置へのデータ転送をあるデータ転送要求に対して許可している途中か否かを示すビットを格納する出力割付済ビット格納手段と、
当該出力装置に対するデータ転送を許可しているデータ転送要求を識別する番号を記録する割付要求番号格納手段と、
（１）前記優先度記録部を参照して当該出力装置に対する最も優先度の高いデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ１を生成し、（２）全ての前記割付要求番号の値を読み出すことにより、当該出力装置以外の他の出力装置に対するデータ転送が既に許可されたデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ２を生成し、（３）前記リストＬ１およびＬ２の情報と、前記転送要求時系列記録部に記録された当該出力装置に対するデータ転送要求のサンプリング結果を用いて、当該出力装置を含む複数の出力装置へのデータ転送を要求しているマルチキャストのデータ転送要求のうち当該出力装置以外の一部の出力装置へのデータ転送が既に許可されているデータ転送要求があれば、その中から最も時間的に古くかつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定し、そのようなデータ転送要求がなければ最も優先度が高い転送要求の中で最も時間的に古く、かつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定し、（４）前記（１）〜（３）を実行する間に前記（１）で生成されたリストＬ１中のデータ転送要求の優先度よりも更に優先度の高いデータ転送要求が当該出力装置に対して新たに到着しているか否かを前記優先度記録部を参照して判断する処理を前記（１）の処理よりも短い時間で実行し、このようなデータ転送要求が新たに到着していれば前記（１）の処理へ戻って処理を再開し、到着していなければ前記（３）において特定されたデータ転送要求を当該出力装置へのデータ転送を許可するデータ転送要求と最終的に確定し、前記出力割付済ビットがクリアされ当該出力装置に対する１つ前のデータ転送が完了したことを確認した後に、前記出力割付済ビットをセットし、前記割付要求番号格納手段に新たに当該出力装置へのデータ転送を許可したデータ転送要求を識別する番号を格納し、前記出力割付状況記録部の更新を行う出力割付処理部とが、
複数ある各出力装置ごとに対応して備えられていることを特徴とする調停装置。
【請求項２】
複数の入力装置と、複数の出力装置と、前記複数の入力装置と前記複数の出力装置間を結合し、入力装置からのフレームを当該出力装置へと送信する経路を提供する結合装置と、請求項１に記載の調停装置とを備えた通信装置。
【請求項３】
複数の入力装置からのデータ転送要求を並列に検査し、転送許可を与える調停方法であって、
前記各入力装置とその入力装置がデータ転送を許可された出力装置の組を表す行列を生成するステップと、
前記各入力装置から出力装置へのデータ転送要求の有無を一定の時間周期で各出力装置ごとにサンプリングするステップと、
前記サンプリング結果を各出力装置ごとに順次記録するステップと、
転送要求に対して定義される複数の優先度について、転送要求中に含まれる優先度を各出力装置ごとに記録するステップと、
対応する出力装置へのデータ転送をあるデータ転送要求に対して許可している途中か否かを示す出力割付済ビットを格納するステップと、
対応する出力装置に対するデータ転送を許可しているデータ転送要求を識別する番号を格納するステップと、
（１）記録されている前記優先度を参照して当該出力装置に対する最も優先度の高いデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ１を生成するステップと、
（２）当該出力装置に対するデータ転送を許可しているデータ転送要求を識別する番号を記録するための割付要求番号の全ての値を読み出すことにより、当該出力装置以外の他の出力装置に対するデータ転送が既に許可されたデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ２を生成するステップと、
（３）前記リストＬ１およびＬ２の情報と、順次記録された当該出力装置に対するデータ転送要求のサンプリング結果を用いて、当該出力装置を含む複数の出力装置へのデータ転送を要求しているマルチキャストのデータ転送要求のうち当該出力装置以外の一部の出力装置へのデータ転送が既に許可されているデータ転送要求があれば、その中から最も時間的に古くかつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定し、そのようなデータ転送要求がなければ最も優先度が高い転送要求の中で最も時間的に古く、かつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定するステップと、
（４）前記ステップ（１）〜（３）を実行する間に前記ステップ（１）で生成されたリストＬ１中のデータ転送要求の優先度よりも更に優先度の高いデータ転送要求が当該出力装置に対して新たに到着しているか否かを記録されている前記優先度を参照して判断する処理を前記ステップ（１）の処理よりも短い時間で実行し、このようなデータ転送要求が新たに到着していれば前記ステップ（１）の処理へ戻って処理を再開し、到着していなければ前記ステップ（３）において特定されたデータ転送要求を当該出力装置へのデータ転送を許可するデータ転送要求と最終的に確定し、前記出力割付済ビットがクリアされ当該出力装置に対する１つ前のデータ転送が完了したことを確認した後に、前記出力割付済ビットをセットし、前記割付要求番号に新たに当該出力装置へのデータ転送を許可したデータ転送要求を識別する番号を格納し、各入力装置とその入力装置がデータ転送を許可された出力装置の組を表す行列の更新を行うステップとを備えた調停方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２以上の入力装置から同一の出力装置に対するデータの転送要求が発行されることによって生じる結合装置の出力部に対する内部競合を回避するための調停装置とこの調停装置を用いた通信装置に関する。
【０００２】
【従来の技術】
従来より、複数の入力装置及び複数の出力装置を、一つの入力装置からのデータを適切な出力装置に送る機能を有する結合装置によって結合してなる通信装置がある。このような通信装置では、２以上の入力装置から同一の出力装置に対するデータの転送要求が発行されることによって生じる結合装置の出力部に対する内部競合を回避するため、結合装置の出力部等の装置内部資源の使用状況を管理し、その使用状況に応じて各入力装置からのデータの転送要求を調停する装置（以下、調停装置と呼ぶ。）が用いられる。
【０００３】
調停装置の配置の仕方は、単一の調停装置が各入力装置からの転送要求を検査し転送許可を与える集中調停型と、出力装置毎に調停装置を配置し、各調停装置は担当の出力装置への転送要求に対する転送許可判断のみを行なう並列調停型との２つに大別される。
【０００４】
図２４は集中調停型の調停装置を用いた通信装置の一例を示すもので、複数の入力装置１０1〜１０Nと、結合装置２０と、複数の出力装置３０1〜３０Nと、調停装置１４０とからなる。このような調停装置１４０においては、各入力装置１０1〜１０Nからのデータ転送要求を一つずつ逐次的に検査し、出力装置３０1〜３０Nのうちの宛先の出力装置が空いている転送要求に対し転送許可を与えていく制御方式や、すべての外部通信回線が同期したタイムスロットを用いて通信を行ない、調停装置１４０はタイムスロットの開始に相当する一定の時間間隔毎に全入力装置１０1〜１０Nからのデータ転送要求を一斉に検査する方式がある。
【０００５】
また、図２５は並列調停型の調停装置を用いた通信装置の一例を示すもので、複数の入力装置１０1〜１０Nと、複数の出力装置３０1〜３０Nと、複数のデータコピーバッファ１６０1〜１６０Nと、複数の調停装置１５０1〜１５０Nとからなる。
【０００６】
集中調停型は、構成が簡単なため実装が容易であるという利点を有する。しかし、各入力装置１０1〜１０Nからのデータ転送要求を一つずつ逐次的に検査する方式は、単位時間あたりのデータ転送要求処理能力が低いことは明らかである。また、外部通信回線がタイムスロットを用いない非同期型の回線の場合は、各入力装置１０1〜１０Nからデータ転送要求が発生したりデータ転送が終了したりするタイミングが全て異なるため、全入力装置１０1〜１０Nからのデータ転送要求を一斉に検査する方式では効率が悪い。この傾向は転送されるデータが可変長データの場合特に顕著である。したがって、タイムスロットを用いない一般的な通信方式のもとではデータ転送要求処理能力を向上させるために並列調停型の調停装置を用いるのが通常である。従って、以下、本発明では、この並列調停型について議論する。
【０００７】
図２５の例において、複数の異なる入力装置１０1〜１０Nから異なるタイミングで発行された同一の出力装置へのデータ転送要求について、これらの間の時間的な前後関係を出力装置を割り当てる調停のスケジューリングに反映させること、すなわち、早く到着した転送要求に対しては早く出力装置を割り当てるようにすることは、転送要求間の公平性の観点から重要である。このような機能を実現するためには、図２５の出力装置に対応した調停装置側に、例えば、各入力装置１０1〜１０Nからのデータのコピーを到着した順に時系列を保持して格納しておく機能が必要である。しかし、更に、入力装置１０1〜１０Nからのデータ転送要求に対し数段階の優先度が定義されていて、調停装置１５０1〜１５０Nにおいては、優先度の高い転送要求を優先度の低い転送要求よりも優先的に出力装置を割り当てながら、かつ、同一優先度の転送要求間では転送要求到着の時系列を反映した割り当てを行なう、という制御を行ないたい場合、定義された優先度毎に時系列確保用の機能を保持するという単純な方法では回路規模の大幅な増大を招いてしまう。このような回路規模の増大を抑えながら上記の制御を実現する方法は自明ではない。
【０００８】
並列調停型の調停装置におけるもう一つの問題として、マルチキャスト転送制御の問題がある。マルチキャスト転送とは、ある入力装置から同じデータを複数の宛先の出力装置に転送することである。図２５の例のように、入力装置側に転送データを宛先毎にコピーして個別に転送する機能を有する通信装置の場合は、全宛先のうち調停処理によって獲得できた出力装置から順次転送データをコピーして送信する操作を全宛先に対する送信が完了するまで行なえばよい。したがって、各宛先毎の調停装置は互いに完全に独立して調整操作を行なえばよい。
【０００９】
これに対し、入力装置の簡素化を目的に入力装置側に上記のような転送データのコピー機能を持たせず、中間の結合装置上にデータコピー機能を持たせる通信装置の構成方法も考えられる。図２６に示すように、入力装置１０1〜１０Nはデータコピーの機能を有しないため結合装置１２０に対して一度だけデータ転送を行ない、その転送されたデータが結合装置１２０上でコピーされ全宛先に一括に転送される。このようなマルチキャスト転送の方式をワンショット（Ｏｎｅ  ｓｈｏｔ）型マルチキャスト転送と呼ぶ。
【００１０】
この場合明らかに、入力装置１０1〜１０Nは、マルチキャスト転送の全ての宛先について調停装置からのデータ転送許可を受信して初めてデータ転送を開始することができる。したがって、複数の異なる入力装置からのマルチキャスト転送要求間でデッドロックが生じないこと、すなわち、互いに他の転送要求がすでに獲得した出力装置の解放を待ち合うことによってどちらのデータ転送も永久に開始できなくなるという現象が生じないことを保証しなければならない。図２７は２つのマルチキャスト転送間でこのようなデッドロックが生じてしまった場合の例である。入力装置１０1、１０Nはそれぞれ、出力装置３０2と３０N-1に対するマルチキャスト転送を要求しているが、入力装置１０1は出力装置３０2のみを、入力装置１０Nは出力装置３０N-1のみを獲得し、それぞれの転送要求は残りの出力装置の解放を互いに待ち合う状態となっている。このような状態が生じてしまうと、それぞれのデータ転送要求は永久にデータ転送を開始できなくなってしまう。入力装置側に転送データのコピー機能を持たない並列調停型の調停装置において、このようなデッドロックが生じないことを保証する方法は自明ではない。
【００１１】
【発明が解決しようとする課題】
上述した従来の調停装置では、下記のような問題点があった。
（１）各入力装置からの転送要求に対して優先度付けを行ないその優先度に基づいて転送要求の調停を行なう機能を実現する際、定義する優先度数の増加に伴い回路規模が増大する。
（２）入力装置上にはデータのコピー機能を持たせず、結合装置上でデータコピーを行なうワンショット型マルチキャスト転送をサポートする際に、異なる入力装置からの複数のマルチキャスト転送要求が互いにデッドロックの状態に陥る可能性がある。
【００１２】
本発明は、前述のような、外部通信回線がタイムスロットを用いない非同期型の回線で、各入力装置からのデータ転送要求が発生したりデータ転送が終了したりするタイミングが全て異なるような通信方式をとっており、調停装置においては、各出力装置毎に調停装置を配置し、各出力装置に対応する調停装置は担当の当該出力装置へのデータ転送要求に対するデータ転送のスケジューリングをそれぞれ非同期に行なう並列型調停装置において、
（１）入力装置上にはデータのコピー機能を持たせず、結合装置上でデータコピーを行なうワンショット型マルチキャスト転送をサポートする際に、異なる入力装置からの複数のマルチキャスト転送要求が互いにデッドロックの状態に陥ることなくフレーム転送が確実に処理されることを保証する、
（２）各入力装置からの転送要求に対して優先度付けを行ないその優先度に基づいて転送要求の調停を行なう機能を実現する際、定義する優先度数の増加に対する回路規模の増大を抑えることができる、
（３）複数の異なる入力装置から異なるタイミングで発行された同一優先度の同一の出力装置へのデータ転送要求について、これらの間の時間的な前後関係を出力装置を割り当てる調停のスケジューリングに反映させる、すなわち、早く到着した転送要求に対しては早く出力を割り当てるようにする、
という（１）〜（３）を全て満足する調停装置および方法を実現することを目的とする。
【００１３】
【課題を解決するための手段】
上記目的を達成するために、本発明の調停装置は、複数の入力装置からのデータ転送要求を並列に検査し、転送許可を与える並列型の調停装置において、
各入力装置とその入力装置がデータ転送を許可された出力装置の組を表す行列であるただ１つの出力割付状況記録部と、
前記各入力装置から当該出力装置へのデータ転送要求の有無を一定の時間周期ごとにサンプリングする要求サンプリング部と、
前記要求サンプリング部のサンプリング結果を順次記録する転送要求時系列記録部と、
転送要求に対して定義される複数の優先度について当該出力装置への転送要求中に含まれる優先度を記録する優先度記録部と、
当該出力装置へのデータ転送をあるデータ転送要求に対して許可している途中か否かを示すビットを格納する出力割付済ビット格納手段と、
当該出力装置に対するデータ転送を許可しているデータ転送要求を識別する番号を記録する割付要求番号格納手段と、
（１）前記優先度記録部を参照して当該出力装置に対する最も優先度の高いデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ１を生成し、（２）全ての前記割付要求番号の値を読み出すことにより、当該出力装置以外の他の出力装置に対するデータ転送が既に許可されたデータ転送要求の発行元の入力装置の番号の組みを格納したリストＬ２を生成し、（３）前記リストＬ１およびＬ２の情報と、前記転送要求時系列記録部に記録された当該出力装置に対するデータ転送要求のサンプリング結果を用いて、当該出力装置を含む複数の出力装置へのデータ転送を要求しているマルチキャストのデータ転送要求のうち当該出力装置以外の一部の出力装置へのデータ転送が既に許可されているデータ転送要求があれば、その中から最も時間的に古くかつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定し、そのようなデータ転送要求がなければ最も優先度が高い転送要求の中で最も時間的に古く、かつ番号が最も小さい入力装置を発行元に持つデータ転送要求を特定し、（４）前記（１）〜（３）を実行する間に前記（１）で生成されたリストＬ１中のデータ転送要求の優先度よりも更に優先度の高いデータ転送要求が当該出力装置に対して新たに到着しているか否かを前記優先度記録部を参照して判断する処理を前記（１）の処理よりも短い時間で実行し、このようなデータ転送要求が新たに到着していれば前記（１）の処理へ戻って処理を再開し、到着していなければ前記（３）において特定されたデータ転送要求を当該出力装置へのデータ転送を許可するデータ転送要求と最終的に確定し、前記出力割付済ビットがクリアされ当該出力装置に対する１つ前のデータ転送が完了したことを確認した後に、前記出力割付済ビットをセットし、前記割付要求番号格納手段に新たに当該出力装置へのデータ転送を許可したデータ転送要求を識別する番号を格納し、前記出力割付状況記録部の更新を行う出力割付処理部とが、
複数ある各出力装置ごとに対応して備えられていることを特徴とする。
【００１４】
本発明によれば、各出力割付処理部が、各要求サンプリング部によってサンプリングされた順番で転送要求受信部からの転送要求に対して出力装置の割付を行っているので、マルチキャスト転送要求が互いにデッドロックの状態に陥ることはない。また、各出力装置毎に優先度を記録するための優先度記録部が備えられているため、定義する優先度数が増加した場合でも優先度記録部のビット数と結線のみを増やせばよいので、優先度数の増加に対する回路規模の増大を従来と比較して抑えることができる。さらに、要求サンプリング部によりサンプリングされたデータ転送要求は転送要求時系列記録部により順次記録されるため、同一優先度の転送要求は発生した順序に従って処理されることを保証することができる。
【００１５】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１６】
図１は本発明による通信装置の一実施形態の構成を示すもので、複数の入力装置１０1〜１０Nと、結合装置２０と、複数の出力装置３０1〜３０Nと、調停装置４０とからなる。図１は集中調停型調停装置の例を示す図２４と同一であるが、図３の説明で口述するように、調停装置の内部構造としては並列型調停装置となっている。
【００１７】
各入力装置１０1〜１０Nおよび出力装置３０1〜３０Nに接続された外部通信回線はタイムスロットを用いない非同期型の回線で、この回線上では長さが可変のデータが非同期に送受信される。以下では、この可変長のデータ転送単位をフレームと呼ぶ。
【００１８】
入力装置１０1〜１０Nは、外部通信回線から１つのフレームが到着すると、転送要求信号をアサート（有効化）しフレーム転送要求が発生したことを転送要求信号を出力して調停装置４０に通知するとともに、フレームの送信先となる要求出力装置一覧信号を調停装置４０に通知する。
【００１９】
結合装置２０は、当該入力／出力装置間を結合し、当該入力装置からのフレームを当該出力装置へと送信する経路を提供する。本実施形態では、１段のクロスバスイッチにより構成されているものとし、フレーム送信先の出力装置の競合がない限り入力装置からのフレーム転送が行えるものとする。また、本結合装置２０上の入／出力装置間を結ぶ途中の経路においては、一切のデータ転送の待ちは発生せず（ノンブロッキング）、出力装置を獲得した入力装置から送信されたフレームデータは直ちに宛先の出力装置へ到着するものとする。
【００２０】
調停装置４０は、各入力装置１０1〜１０Nからのフレーム転送要求について、複数の異なる入力装置からの同一の出力装置へのフレーム転送の衝突を回避しながらフレーム転送要求に対する出力装置の割り付けを行ない、結合装置２０の当該入力／出力装置間の接続を確立し、入力装置に対してフレーム転送許可を発行する機能を持つ。
【００２１】
入力装置１０1〜１０Nは、調停装置４０からの転送許可信号がアサートされると、宛先の出力装置に対するフレーム転送を開始する。フレーム転送中は転送要求信号をアサートし続ける。また、調停装置４０からの転送許可信号もアサートされ続ける。フレーム転送が終了すると、転送要求信号をネゲート（無効化）し、フレーム転送が終了した旨を調停装置４０に通知する。
【００２２】
調停装置４０は、転送許可信号をアサートしている入力装置１０1〜１０Nからの転送要求信号のネゲートを検出すると、フレーム転送が終了したと判断し、フレーム転送の宛先であった出力装置の解放処理、および、当該入力／出力装置間の結合装置２０の接続解除処理を行なう。そして、これらを行った後、当該入力装置に対する転送許可信号をネゲートする。
【００２３】
図２は、本実施形態における入力装置１０1の構成である。入力装置１０1は、外部通信回線ａから到着したフレームデータを宛先出力装置への転送許可が発行されるまでの間格納しておく領域として、単一のＦＩＦＯ（first in first out）キューを有する。フレームは外部通信回線ａから到着した順にＦＩＦＯキューに格納され、キューの先頭フレームから順に１つずつ調停装置４０に対する転送要求が発行され、出力装置３０1〜３０Nへの転送が行なわれる。したがって、フレーム転送要求間で宛先出力装置への転送処理の追い越しが行われることはなく、フレームは外部通信回線ａから到着した順に出力装置へと転送される。
【００２４】
また、この入力装置１０1はフレームデータをコピーする機能は有しない。したがって、複数の出力装置へ転送されるマルチキャスト転送の場合、調停装置４０はそのフレームの全ての宛先出力装置を当該転送要求へ割り当てた時点で初めて転送許可信号を発行する。転送許可信号が発行されたマルチキャストフレームは当該入力装置のＦＩＦＯキューから読み出された後、結合装置２０上でデータのコピーが行われ、全ての宛先出力装置への転送が行われる。
【００２５】
以下、入力装置１０1〜１０Nの動作の詳細を説明する。まず、外部通信回線ａからデータが送られてくると、回線入力部１１内のフレーム抽出部１２においてフレームの抽出を行ない、入力フレームのデータｂを入力バッファ部１５に書き込む。また、宛先情報抽出／フレーム長計測部１３で抽出した宛先情報、および、優先度信号と、宛先情報抽出／フレーム長計測部１３で計測したフレーム長情報を経路制御部１４に送る（図中のＣ）。
【００２６】
経路制御部１４は宛先情報を用いて出力装置３０1〜３０Nのうちから転送先となる出力装置を決定し、転送要求信号をアサートしてフレーム転送要求の発生を調停装置４０に通知するとともに、要求出力装置一覧信号と優先度信号を通知する。そして、調停装置４０から転送許可信号がアサートされるのを待つ。調停装置４０から転送許可を受け取ると、経路制御部１４はフレーム長情報ｄを転送制御部１６に送る。
【００２７】
転送制御部１６は、フレーム長ｄを受け取ると、入力バッファ部１５へ読み出し信号ｅを送り、入力バッファ部１５中のフレームデータｆを読み出す。読み出されたフレームデータは、結合装置２０を経由して出力装置３０1〜３０Nへと転送される（ｈ）。また、転送制御部１６は、フレーム長情報ｄをもとにフレームを転送するのに必要な時間をカウンタ回路により計測し、その間、上記入力バッファ部１５の読み出しを継続する。さらに、転送制御部１６は、カウンタ回路により転送の終了を検出すると、入力バッファ部１５の読み出しを終了し、転送終了信号ｇを経路制御部１４に送る。経路制御部１４は、転送終了信号ｇを受けて、調停装置４０に対する転送要求信号をネゲートする。
【００２８】
以上が入力装置１０1〜１０Nの動作である。なお、出力装置３０1〜３０Nは、結合装置２０から送られたフレームデータｈを単純に外部通信回線ｉへ出力するだけであるため、その構成については省略する。
【００２９】
次に、本実施形態における調停装置４０の構成を図３を参照して説明する。図３は図１における調停装置４０の内部構成を示すもので、転送要求受信部４１1〜４１Nと、要求サンプリング部４２1〜４２Nと、転送要求時系列記録部４３1〜４３Nと、優先度記録部４４1〜４４Nと、出力割付処理部４５1〜４５Nと、出力割付状況記録部４６と、割付要求番号と、出力割付済ビットと、マルチプレクサ（ＭＵＸ）４７1、４７2と、結合装置制御部４８と、結合装置解放要求発行部４９とから構成されている。
【００３０】
転送要求受信部４１1〜４１N、結合装置解放要求発行部４９1〜４９Nはそれぞれ各入力装置１０1〜１０Nに対応して存在し、また、要求サンプリング部４２1〜４２N、転送要求時系列記録部４３1〜４３N、優先度記録部４４1〜４４N、出力割付処理部４５1〜４５N、割付要求番号、出力割付済ビット、はそれぞれ各出力装置３０1〜３０Nに対応して存在する。各出力割付処理部４５1〜４５Nは、対応する当該出力装置への複数のフレーム転送要求間の調停処理をそれぞれ独立して非同期に並列実行する。したがって本実施形態における調停装置４０は並列型調停装置の一種である。なお、各入力装置に対応する転送要求受信部、結合装置解放要求発行部も全て独立して非同期に並列動作する。
【００３１】
ここで、本実施形態における調停装置４０は、図３中太線の、要求サンプリング部４２1〜４２N、転送要求時系列記録部４３1〜４３N、優先度記録部４４1〜４４N、出力割付状況記録部４５1〜４５N、割付要求番号、出力割付済ビットを備えた点、および、出力割付処理部４５1〜４５Nにおいて出力装置３０1〜３０Nの割付けを行なう際に後述する方法を用いる点を除いて、図２４に示した従来の調停装置１４０と同様である。
【００３２】
要求サンプリング部４２1〜４２Nは、各入力装置１０1〜１０Nから対応する当該出力装置へのデータ転送要求の有無を一定の時間周期でサンプリングする。転送要求時系列記録部４３1〜４３Nは、要求サンプリング部４２1〜４２Nのサンプリング結果を順次記録する。優先度記録部４４1〜４４Nは、転送要求に対して定義される複数の優先度について当該出力装置への転送要求中に含まれる優先度を記録する。出力割付処理部４５1〜４５Nは、転送要求時系列記録部４３1〜４３Nおよび優先度記録部４４1〜４４Nを参照して当該出力装置に対する複数のデータ転送要求の中から最も優先度が高く、時間的に古いデータ転送要求を特定して当該出力装置に対するデータ転送を許可する。
【００３３】
以下、ある外部通信回線から入力装置へ到着した１つのフレームについてのフレーム転送要求が本実施形態における調停装置４０において処理され、当該入力装置に対してフレーム転送許可が発行され結合装置２０へのフレーム転送が開始されるまでの流れを説明する。ここで、入力装置１０i、出力装置３０i等の表記については、ｉ番目の入力装置または出力装置、またはそれに対応する前述の各処理部を意味するものとし、１≦ｉ≦Ｎである。ここでは、ｉ番目の外部通信回線に、ｊ番目の出力装置、および、ｋ番目の出力装置宛のマルチキャストフレームが到着したものとして説明する。（１≦ｉ、ｊ、ｋ≦Ｎ）また、本実施形態における通信装置では、フレーム転送要求に対して優先度が１からＳまで定義されており、その数値が小さい転送要求ほど優先的に扱われるものとする。すなわち、優先度１が最高、優先度Ｓが最低の優先度であるとする。
【００３４】
まず、調停装置４０内部の動作を説明する前に、入力装置１０1〜１０N、および、調停装置４０間のインタフェース、すなわち、フレーム転送要求の開始から転送終了までの間に送受される信号と処理手順の概要について説明する。各入力装置１０1〜１０Nと調停装置４０は、図１および図３に示すように４種類の信号線で結線されている。転送要求信号、要求出力装置一覧信号、および、優先度信号が入力装置１０1〜１０Nから調停装置４０への出力方向の信号であり、転送許可信号が調停装置４０から入力装置１０1〜１０Nへの出力方向の信号である。
【００３５】
図４の（ａ）および（ｃ）は、これらの結線を介して送受される信号のタイミングチャートである。ｉ番目の外部通信回線から１つのフレームを受信した入力装置１０iは、調停装置４０内の対応する転送要求受信部４１iに対し、転送要求信号をアサートし、フレーム転送要求が発生したことを調停装置４０に通知する。図４（ａ）では、負論理の転送要求信号の値を‘１’から‘０’へ反転することで転送要求の発生を通知し、当該転送要求の宛先となる出力装置の一覧を示す要求出力装置一覧信号ビットマップ情報として複数サイクルに渡って調停装置４０へ転送している様子を示している。調停装置４０へ転送される要求出力装置一覧信号は、図４（ｂ）に示すようなフォーマットのビットマップ情報で、当該転送要求の宛先に対応する出力装置のフィールドのビット値が‘１’に設定される。図４（ｂ）の例は、当該フレーム転送の宛先が出力装置３０jと出力装置３０kのマルチキャスト転送であることを示している。要求出力装置一覧信号は、このビットマップ情報の転送効率とハードウェアの実装を考慮したビット幅を有し、前記ビットマップ情報はこのビット幅と出力装置の数Ｎに応じて決定されるサイクル数を要して調停装置に転送されるものとする。また、入力装置１０iは、このとき同時に当該フレーム転送要求の優先度を優先度信号により通知する。図４（ａ）の例では、当該フレーム転送要求の優先度が‘１’（最高優先度）であることを示している。この優先度信号は、システム内で定義されたフレーム転送の優先度数を表現するのに十分なビット幅を有するものとする。
【００３６】
これらを受信した調停装置４０は、当該入力装置１０iからのフレーム転送要求に対して、宛先となる出力装置３０j、および出力装置３０kの割り当て処理を開始する。出力装置３０j、３０kの割り当てが完了し、さらに、結合装置２０の当該入力／出力装置間の接続の確立が完了すると、入力装置１０iに対して転送許可信号をアサートする。この様子を図４（ｃ）に示す。転送許可信号は負論理で、調停装置４０はこの信号値を‘１’から‘０’に反転することで、当該入力装置１０iに対しフレームの転送許可を発行している。
【００３７】
入力装置１０iは、調停装置４０からの転送許可が発行されると、フレームデータの結合装置２０への実際の転送を開始する。フレーム転送中は転送要求信号をアサートし続け、調停装置４０からの転送許可信号もアサートされ続ける。入力装置１０iは、フレームデータの転送が終了すると、転送要求信号をネゲートする。図４（ｃ）では、転送要求信号の値を‘０’から‘１’に反転することで、フレーム転送の終了を通知している。
【００３８】
調停装置４０は、転送許可信号をアサートしている入力装置１０iからの転送要求信号のネゲートを検出すると、フレーム転送が終了したと判断し、その入力装置１０iに対する転送許可信号をネゲートする。図４（ｃ）では、転送許可信号の値を‘０’から初期値の‘１’へ戻している。
【００３９】
以上が、入力装置１０i、および、調停装置４０間でフレーム転送要求の開始から転送終了までの間に送受される信号と動作の概要である。次に、調停装置４０内部の動作を以下に詳述する。
【００４０】
転送要求受信部４１の処理の概要を図５に示す。転送要求受信部４１iは、対応する入力装置１０iからの転送要求信号のアサート、および、要求出力装置一覧信号、および、優先度信号の通知を検出すると、当該転送要求の宛先となる出力装置の一覧を図５中の宛先リストに格納する。そして、要求サンプリング部４２1〜４２Nのうちの宛先となる出力装置３０j、３０kに対応する要求サンプリング部４２j、４２kに対して出力先獲得要求を発行する。本実施形態では、この出力先獲得要求は、システムクロックに同期して、１システムクロック周期の間ビット‘１’のパルスを出力先獲得要求信号線上に出力するものとする。宛先となる出力装置が複数あるマルチキャスト転送の場合には、宛先となる全ての出力装置に対応する出力先獲得要求のパルスを同時に出力する。また、転送要求受信部４１iは、上記の出力先獲得要求パルスの発行と同時に、受信したフレーム転送要求の優先度に相当する優先度通知信号をアサートする。図５の例では、宛先である出力装置３０jおよび出力装置３０kに対応する要求サンプリング部４２j、４２kに対して出力先獲得要求信号パルスを発行し、優先度を１に指定している。
【００４１】
次に、要求サンプリング部４２1〜４２Nの動作を説明する。図６はその動作の概要を示す。要求サンプリング部４２1〜４２Nは、出力装置３０1〜３０Nのうちの自身に対応する出力装置に対する、全ての転送要求受信部４１1〜４１Nからの出力先獲得要求パルスの有無、すなわち、全ての転送要求受信部４１1〜４１Nからの出力先獲得要求信号の値をラッチし、ラッチした値の列を転送要求時系列記録部４３1〜４３Nのうちの対応する転送要求時系列記録部の最後尾ポインタ（後述）がさすワードに書き込む、という動作を繰り返す。そして、要求サンプリング部４２1〜４２Nは、転送要求受信部４１1〜４１Nのうちの、出力先獲得要求パルスを発行している転送要求受信部からの信号値のラッチ時には‘１’の値を、出力先獲得要求パルスを発行していない転送要求受信部からの信号値のラッチ時には‘０’の値をラッチする。図６（ａ）の例は、時刻ｔ１に転送要求受信部４１iが出力装置３０j、および、３０kに対する出力先獲得要求パルスを発行し、それらの出力装置に対応する要求サンプリング部４２j、４２kがそれらのパルスをラッチしている様子を示している。このようにラッチされた値の列は、それぞれに対応する転送要求時系列記録部の最後尾ポインタ（後述）がさすワードに書き込まれる。
【００４２】
要求サンプリング部４２1〜４２Nがこのラッチ動作を繰り返す周期をサンプリング周期と呼ぶ。本実施形態では、このサンプリング周期は、当該出力装置に対する、全ての転送要求受信部４１1〜４１Nからの出力先獲得要求パルスの有無の状態が変化しうる最小の時間間隔度、すなわち、前述のシステムクロックの１周期分の長さであるとする。これはすなわち、各転送要求時系列記録部４３1〜４３Nからの出力先獲得要求の時間的な前後関係を厳密に記録するためである。
【００４３】
図６（ｂ）は、図６（ａ）に示した時刻ｔ１より１つ後のサンプリング周期後の時刻ｔ２、すなわち、時刻ｔ１より１クロック後の時刻ｔ２における様子を示しており、転送要求受信部４１1が出力装置３０jに対する、転送要求受信部４１Nが出力装置３０kに対するユニキャスト転送の出力先獲得要求パルスを発行している。これらのパルスはそれぞれ各要求サンプリング部でラッチされた後、図６（ａ）のワード位置より１ワード分だけ後方に進めた位置にある転送要求時系列要求部の最後尾ポインタがさすワードに書き込まれる。
【００４４】
次に、転送要求時系列記録部４３1〜４３Nの動作を説明する。転送要求時系列記録部４３1〜４３Nは図７に示すように、要求サンプリング部４２1〜４２Nの１回のサンプリング結果を記録するための、入力装置の数のビットレジスタからなるワードを、入力装置の個数だけ並べた構造を有する。
【００４５】
本実施形態における通信装置は入力装置の数がＮ個であるので、転送要求時系列記録部４３1〜４３NはＮ個のビットレジスタからなるワードをＮワード有する。また、転送要求時系列記録部４３1〜４３Nは、要求サンプリング部４２1〜４２Nからのサンプリング結果を次に書き込むべきワードを指す最後尾ポインタを有する。転送要求時系列記録部４３1〜４３Nは、要求サンプリング部４２1〜４２Nのサンプリング周期、すなわち、本実施形態ではシステムクロックの１周期毎に、このポインタが示すワードに要求サンプリング部４２1〜４２Nからのサンプリング結果を書き込み最後尾ポインタを一つ後ろにずらす、という動作を繰り返す。このようにして、転送要求時系列記録部４３1〜４３Nは、各入力装置１０1〜１０Nに対応する転送要求受信部４１1〜４１Nから当該出力装置３０1〜３０Nに対して発行された出力先獲得要求を、それらの時間的前後関係を保持した形で記録していく。
【００４６】
また、転送要求時系列記録部４３1〜４３Nは、上記の他に、以下の（１）、（２）の機能を備える。
（１）要求サンプリング部４２1〜４２Nのあるサンプリング周期におけるサンプリング結果がすべて‘０’、すなわち、当該出力装置に対する出力先獲得要求がどの転送要求受信部４１1〜４１Nからも発生していない場合は、転送要求時系列記録部４３1〜４３Nへのサンプリング結果の書き込みは行なわない。
（２）転送要求時系列記録部４３1〜４３Nの任意のワードの任意のビットレジスタは同じ当該出力装置に対応する出力割付処理部４５1〜４５Nからその値の読み出し、および、そのビットの‘０’クリアが可能である。後述する出力割付処理部４５1〜４５Nの操作によってあるワード中のビットが全て消去された場合は、図８に示すように後続のワードを全て前に詰め直し、最後尾ポインタの位置を１ワード分前にずらす。
【００４７】
この（１）、（２）の操作と、図４に示したように各入力装置は１つのフレーム転送が終了してはじめて次のフレーム転送要求を発行できることにより、各転送要求時系列記録部４３1〜４３Nには入力装置の総数を越える数のサンプリング結果が蓄積することがないことが保証できる。したがって、転送要求時系列記録部４３1〜４３Nには入出力装置の数だけのワード数があればよい。
【００４８】
なお、後述する各出力割付処理部４５1〜４５Nはそれぞれ独立して非同期に並列動作すること、および、上記（１）、（２）とから、各転送要求時系列記録部４３1〜４３Nの最後尾ポインタがさすワード位置は全て同じであるとは限らない。図６（ａ）および（ｂ）においても、転送要求時系列記録部４３j、４３kの各最後尾ポインタがそれぞれ異なるワード位置をさしている状況を例として示している。
【００４９】
以上の手順で転送要求時系列記録部４３1〜４３Nに記録されていく入力装置からの出力先獲得要求に対して、出力割付処理部４５1〜４５Nは、これらの記録された内容を参照しながら、対応する出力装置を割り付ける（データ転送を許可する）出力先獲得要求を決定する。図９は、この出力割付処理部４５の動作をフローチャート化したものである。以下、出力割付処理部４５1〜４５Nの処理を説明する。
【００５０】
出力割付処理部４５1〜４５Nの処理は、図９に示すように大きく（１）〜（５）のステージに分かれる。ステージ（１）では、本実施形態における通信装置で定義されたフレーム転送の優先度のうち、その優先度の出力先獲得要求が対応する転送要求時系列記録部４３中に格納されているものの最高の優先度を検索する。ステージ（２）では、自身以外の、他の出力装置３０1〜３０Nに対応する出力割付処理部４５1〜４５Nにおいて、すでに出力先獲得要求への出力装置の割り付けが完了しているものについて、出力装置を割り付けられた出力先獲得要求の発行元の転送要求受信部４１の番号を記録する。ステージ（３）では、対応する転送要求時系列記録部４３の内容を先頭ワードから順にスキャンし、自身が対応する出力装置を割り付ける出力先獲得要求の候補を検索する。ステージ（４）では、ステージ（１）で検索した優先度より更に高優先度の出力先獲得要求がステージ（１）からステージ（３）を実行する間に新たに対応する転送要求時系列記録部４３に到着しているか否かを検査する。そのような出力先獲得要求が到着している場合には、ステージ（１）の処理に戻る。ステージ（５）では、対応する出力装置を割り付ける出力先獲得要求を最終決定し、その出力先獲得要求に対して出力装置を割り付ける。要求する出力装置を全て割り付けられた入力装置は、対応するフレームの結合装置２０へのフレーム転送を行ない、これが終了すると割り付けられた出力装置は解放される。出力装置が解放されると、出力割付処理部４５はステージ（１）へ戻り、次の割り付け処理を開始する。
【００５１】
なお、後述のように、ステージ（４）の実行に要するシステムクロックのサイクル数は、ステージ（１）のそれよりも短くなくてはならない。
【００５２】
出力割付処理部４５1〜４５Nは、以上のステージ（１）からステージ（５）の処理を繰り返すことにより、出力先獲得要求に対して対応する出力装置を次々に割り付けていく。以下、これらの処理の詳細を説明する。
【００５３】
まずステージ（１）における処理の詳細を説明する。図１０は、優先度記録部４４1〜４４Nの構成を示す図で、ビットレジスタＰ［１］、Ｐ［２］、．．．、Ｐ［Ｓ］は、それぞれ、本実施形態における通信装置で定義された１からＳまでのフレーム転送の優先度に対応している。なお、以下では、入力装置からの優先度ｉのフレーム転送要求に対応する、転送要求受信部からの出力先獲得要求のことを、優先度ｉの出力先獲得要求と呼ぶ。各Ｐ［ｉ］の値は、当該出力装置に対する、全ての転送要求受信部からの優先度ｉの優先度通知信号の値の論理和である。すなわち、Ｐ［ｉ］＝１は当該転送要求時系列記録部中に優先度ｉの出力先獲得要求が存在していること、Ｐ［ｉ］＝０は存在していないことを表す。ステージ（１）において、出力割付処理部４５1〜４５Nは、先ず優先度記録部４４1〜４４Nのビットレジスタの並びＰ＝（Ｐ［１］、Ｐ［２］、．．．、Ｐ［Ｓ］）を参照し、Ｐ［ｋ］＝１なる最小のｋであるＫｍｉｎ（１≦Ｋｍｉｎ≦Ｓ）を見つける。そして、優先度Ｋｍｉｎの全ての優先度通知信号の値をリストＬ１に格納する。すなわちリストＬ１は、優先度Ｋｍｉｎの全ての出力先獲得要求の集合を表す。図１１にこの操作の例を示す。
【００５４】
この例では、転送要求受信部４１iからの優先度１の優先度通知信号がアサートされており、また、転送要求受信部４１2、４１N-1、４１Nからの優先度Ｓの優先度通知信号がアサートされている。したがって、Ｋｍｉｎの値は１となり、リストＬ１には優先度がＫｍｉｎ＝１の全ての優先度通知信号の値が格納される。例では、優先度１の優先度通知信号をアサートしているのは転送要求受信部４１iだけであり、したがって、リストＬ１のｉ番目のビットのみが１で、他のビットは全て０となっている。
【００５５】
次にステージ（２）において、自身以外の全ての出力割付処理部４５における割付要求番号の内容をリストＬ２に格納する。すなわち、リストＬ２は、すでに要求出力装置（の一部）が割り付けられているフレーム転送要求の発行元である入力装置の番号のリストである。図１２にこの操作の例を示す。出力装置割付処理部４５は、自身が対応する出力装置を割り付けたフレーム転送要求の発行元の入力装置の番号を自身が対応する割付要求番号に書き込む機能、および、それ以外の全ての割付要求番号に書かれている値を読み出す機能を有する。なお、割付要求番号の値が０であるときは、その割付要求番号に対応する出力装置はそのフレーム転送要求にも割付られていないことを意味する。図１２の例では、出力装置３０1が入力装置１０5からのフレーム転送要求に対して、すなわち、転送要求受信部４１5からの出力先獲得要求に対して既に割り付けられており、また、出力装置３０Nが入力装置１０1からのフレーム転送要求に対して、すなわち、転送要求受信部４１1からの出力先獲得要求に対して割り付けられている。したがって、リストＬ２は、図に示すようにビット［１］、および、ビット［５］が‘１’で、他のビットが全て‘０’の値からなるリストとなる。
【００５６】
ステージ（３）では、このようにして内容を決定したリストＬ１、Ｌ２を使用しながら、対応する転送要求時系列記録部４３の各ワードを先頭から順にスキャンし、対応する出力装置を割り付ける転送要求の候補を検索する。まずは、リストＬ２の内容と転送要求時系列記録部４３の各ワードとのビット毎の論理積（ＡＮＤ）をとる演算（結果をリストＲとする）を行なう。この演算を転送要求時系列記録部４３の先頭ワードから開始し、リストＲがオール‘０’であればワード位置を一つずつ進めながら同様の演算を繰り返す。あるワードＩにおいてリストＲが初めてオール‘０’でなくなったとき、ステージ（３）の処理は終了する。最後尾ワードまで検索してもリストＲがオール‘０’でないようなワードが存在しなければ、次にリストＬ１の内容と転送要求時系列記録部４３の各ワードとの同様の演算を先頭ワードから順にワード位置を進めながら行なう。ここでは必ずリストＲがオール‘０’でないものが見つかるので、最初にそのようなワードＩが見つかった時点でステージ（３）の処理は終了する。
【００５７】
このステージ（３）の処理で抽出するワードの意味は以下の通りである。リストＬ２との論理積演算中にワードを抽出した場合、そのワードの中には、本演算を行った出力割付処理部４５に対応する出力装置に加えてそれ以外の出力装置に対しても出力先獲得要求を発行しているマルチキャスト転送要求ですでに本出力割付処理部４５に対応する出力装置以外の出力装置の一部を割り付けられている出力先獲得要求のうち、最も古く発行された出力先獲得要求を含んでいる。また、リストＬ１との論理積演算中にワードを抽出した場合、そのワード中には、ステージ（１）の処理を実行した時点における、本出力割付処理部４５に対応する出力装置への転送要求のうち最高優先度の優先度Ｋｍｉｎを持つ転送要求に対応する出力先獲得要求のうち、最も早く発行されたものが含まれている。これらは当該出力装置を割り付けるべき出力先獲得要求の候補である。
【００５８】
図１３は、図１１、図１２の操作で決定したリストＬ１、Ｌ２の内容と転送要求時系列記録部４３の各ワードとの間でビット毎の論理積演算を行なう例である。転送要求時系列記録部４３には、図１１に示した転送要求受信部４１2、４１i、４１N-1、４１Nからの出力先獲得要求パルスの履歴が書き込まれている。転送要求受信部４１iと転送要求受信部４１N-1からの出力先獲得要求パルスは同じ時刻に発行され、転送要求受信部４１2、および、４１Nからの出力先獲得要求パルスはそれぞれこれらとは異なる時刻に発行されたことを示している。ステージ（３）の処理の前半では、リストＬ２と転送要求時系列記録部４３内の各ワードとの間でビット毎の論理積演算が行なわれる。本例では転送要求時系列記録部４３の最後尾ワードまで全てこの演算結果はオール‘０’のままであるとする。したがって、ステージ（３）の処理の後半でリストＬ１を用いて同様の演算が行なわれ、その結果、図中のワードＩにおけるビット［ｉ］（転送要求受信部４１iからの出力先獲得要求）とリストＬ１のビット［ｉ］が共に‘１’であるため、リストＲがオール‘０’でなくなり処理が終了する。
【００５９】
ステージ（４）の処理では、ステージ（３）の処理で検索した前述の候補の中から出力装置を割り付ける出力先獲得要求を決定する前に、ステージ（１）から（３）の処理を実行する間にステージ（１）の処理において検索した最高優先度Ｋｍｉｎよりも更に高い優先度の転送要求が当該出力装置に対して新たに発行されているか否かを確認する。ステージ（１）の処理と同様の方法でＰ［Ｋ’ｍｉｎ］＝１なる最小のＫ’ｍｉｎ（１≦Ｋ’ｍｉｎ≦Ｎ）を見つけ、Ｋ’ｍｉｎ＜Ｋｍｉｎであればステージ（１）の処理に戻って再度操作を行なう。Ｋ’ｍｉｎ＝Ｋｍｉｎであれば、ステージ（５）の処理に移る。なお、ステージ（４）の処理が必要な理由については後述する。
【００６０】
ステージ（５）では、ステージ（３）の結果抽出したワードＩに含まれる複数の出力先獲得要求の中から、当該出力装置を割り付ける出力先獲得要求を最終決定する。ワードＩがステージ（３）の処理の前半、すなわち、リストＬ２の論理積演算中に抽出されたものである場合は、リストＬ２とのビット毎の論理積演算において‘１’となるワードＩ中の出力先獲得要求のうち、最も小さい入力装置番号からの出力先獲得要求を、当該出力装置を割り付ける出力先獲得要求とする。最も小さい入力装置番号からの出力先獲得要求を選ぶ理由は後述する。リストＬ２とのビット毎の論理積演算において‘１’となる出力先獲得要求がワードＩ中に１つしか存在しない場合は、その出力先獲得要求を当該出力装置を割り付ける出力先獲得要求とする。ワードＩがステージ（３）の処理の後半、すなわち、リストＬ１の論理積演算中に抽出されたものである場合は、リストＬ１を用いて同様の方法で当該出力装置を割り付ける出力先獲得要求を決定する。図１４は、図１３の動作で抽出したワードＩについて、リストＬ１とのビット毎の論理積演算において‘１’となるワードＩ中の出力先獲得要求の中から最も小さい入力装置番号に対応する出力先獲得要求を検索する様子を示しており、最も小さい入力装置番号に対応する出力先獲得要求が入力装置１０iに対応する出力先獲得要求であることを識別する様子を示している。
【００６１】
以上の操作で選択した入力装置１０iに対応する出力先獲得要求は、優先度がＫｍｉｎ＝１のフレーム転送要求に対応する出力先獲得要求のうちもっとも早く発行されたものの中で、対応するフレーム転送要求発行元の入力装置番号が最も小さいものに相当する。
【００６２】
出力装置を割り付ける出力先獲得要求が決定すると、実際に出力装置を割り付ける操作を行なう。この操作の概要を図１５に示す。出力割付処理部は、出力装置を割り付ける出力先獲得要求を決定すると、次に、当該出力装置に対応する出力割付済ビットが‘０’であることを確認する。このビットは、出力装置がある転送要求に対して割り付けられている時に‘１’、そうでない時には‘０’の値をとる。出力割付処理部が出力装置を新たな出力先獲得要求に対して割り付ける際に、出力割付処理部４５によって‘１’にセットされ、フレーム転送が終了したとき、フレーム転送許可を受けた当該入力装置に対応する結合装置解放要求発行部４９（後述）によって‘０’クリアされる。したがって、上記ビット検査は、この出力装置に対する一つ前のフレーム転送が終了し結合装置２０の解放が完了していることの確認を意味する。上記出力割付済ビットが‘１’である場合は、出力割付処理部４５はこのビットが‘０’クリアされるまで待つ。
【００６３】
出力割付処理部４５は、上記出力割付済ビットが‘０’クリアされたことを確認すると、このビットを‘１’にセットするとともに、当該出力装置を入力装置１０iからのフレーム転送要求に対応する出力先獲得要求に対して割り付けたことを示すために割付要求番号フィールドの値を‘ｉ’にセットする。また、同時に、出力割付状況記録部４６の当該要素を‘１’にセットする。出力割付状況記録部４６はＮ×Ｎ個の要素からなる行列で、要素Ａ［ｉ，ｊ］＝１は、現在出力装置３０jが入力装置１０iからのフレーム転送要求に対応する出力先獲得要求に対して割り付けられていること、Ａ［ｉ，ｊ］＝０は現在出力装置３０jがどの出力先獲得要求にも割り付けられていないことを示す。本実施形態の説明では、入力装置１０iが出力装置３０j、および出力装置３０kに対してフレーム転送要求を発行しているので、出力割付処理部４５jがＡ［ｉ，ｊ］を、出力割付処理部４５kがＡ［ｉ，ｋ］をステージ（５）の処理においてそれぞれ‘１’にセットする。
【００６４】
出力割付状況記録部４６の更新後、出力割付処理部４５は、転送要求時系列記録部４３のワード中の出力装置を割り付けた出力先獲得要求に対応するビットを‘０’クリアする。このときもし、このワード中の全てのビットが‘０’になれば、後続のワード以降を前に詰めなおす操作を行なう。
【００６５】
転送要求受信部４１は、出力先獲得要求の発行後、出力割付状況記録部４６を監視し、当該フレームの出力先となる全ての出力装置が自身の出力先獲得要求に対して割り付けられるのを待つ。本実施形態では、転送要求受信部４１iは、出力割付状況記録部４６のＡ［ｉ，ｊ］、および、Ａ［ｉ，ｋ］がともに‘１’となるのを待つ。そして、これらがともに‘１’になったことを検出すると、結合装置制御部４８に対し結合装置の入出力装置間の接続要求を発行する。本実施形態では、転送要求受信部４１iは、入力装置１０iと、出力装置３０jおよび出力装置３０kとの間の接続を要求する。
【００６６】
図１５中の結合装置接続要求は、接続を要求する入出力装置の番号の対ｉとｊおよびｋを含むものとする。
【００６７】
結合装置制御部４８は、複数の転送要求受信部４１1〜４１Nからの接続要求を１つずつ処理する。転送要求受信部４１iからの接続要求を選択し、結合装置の入力装置１０iと出力装置３０jおよび３０kとの接続操作が完了すると、転送要求受信部１０iに対しその旨を通知する。
【００６８】
この段階で、入出力装置間の接続経路が確立され、フレーム転送が行なえる状態となっている。入出力装置間の接続操作の完了を通知された転送要求受信部４１iは、当該入力装置１０iに対してフレーム転送要求許可信号をアサートしフレーム転送許可を発行する。これを受けた当該入力装置１０iは出力装置３０jおよび出力装置３０kへのフレーム転送を開始する。
【００６９】
以上が、ある入力装置からのフレーム転送要求到着してからフレーム転送が開始されるまでの処理である。
【００７０】
次に、フレーム転送が終了した時の処理の概要を図１６に示す。入力装置１０iは、当該フレームの転送が終了すると、転送要求信号をネゲートし、調停装置４０に対してフレーム転送の終了を通知する。入力装置１０iからの転送要求信号は結合装置解放要求発行部４０iにも供給されており、これによってフレーム転送の終了を検出した結合装置解放要求発行部４９iは、当該入力装置１０iと当該フレーム転送の宛先である出力装置３０jおよび出力装置３０k間の結合装置２０の接続解放要求を結合装置制御部４８に対して発行する。
【００７１】
図１６中の結合装置解放要求は、解放を要求する入出力装置の番号の対ｉとｊおよびｋを含むものとする。ここで、結合装置解放要求発行部４９iは、転送要求受信部４１iの宛先リスト（図５参照）を参照可能であり、これにより当該フレーム転送の宛先が出力装置３０jおよび３０kであったことを知る。
【００７２】
結合装置制御部４８は、結合装置解放要求発行部４９iからこの接続解放要求を受け取ると、結合装置２０の入出力装置間の接続解放操作を行なう。この操作が終了すると、結合装置解放要求発行部４９iに対しその旨を通知する。
【００７３】
入出力装置間の接続解放操作の完了を通知された結合装置解放要求発行部４９iは、図１６に示すように、出力割付状況記録部４６の要素Ａ［ｉ，ｊ］とＡ［ｉ，ｋ］、および、出力装置３０jと出力装置３０kの出力割付済ビット、および、割付要求番号フィールドをすべて‘０’クリアする。
【００７４】
以上が、外部通信回線から本通信装置に到着したフレームが、調停装置４０における出力装置の競合調停を経た後、当該出力装置に転送され、フレーム転送が終了するまでの処理の流れである。
【００７５】
以下では、上に述べた本実施形態における調停装置４０の動作によって実現される出力装置割り付け方法の特徴、および、本調停装置４０の動作の妥当性について説明する。
【００７６】
本調停装置４０における転送要求時系列記録部４３は、各入力装置に対応する転送要求受信部から当該出力装置３０に対して発行された出力先獲得要求を、システムクロックの周期を粒度としてそれらが発行された時系列順に記録する機能を有する。すなわち、同一のシステムクロックのタイミングで発行された出力先獲得要求は全て、各転送要求時系列記録部４３において同一ワードの中に記録され、そうでないものは発行された順に前方のワードから順に異なるワードに記録されていく。
【００７７】
このように記録された出力先獲得要求に対し、出力割付処理部４５は、優先度の高い出力先獲得要求から順に転送要求時系列記録部４３の前方のワードから検索し、該当する優先度の出力先獲得要求を含むワードが見つかった時点で、そのワード中の、最も番号の小さい入力装置からの出力先獲得要求に対して当該出力装置を割り付ける（リストＬ２の役割については後述する）、という動作を繰り返す。
【００７８】
これらの特徴を有する本調停装置４０により、以下のａ〜ｄが実現される。
ａ．同じ出力装置に対して発行された複数の転送要求受信部４１からの出力先獲得要求に対して、優先度の高い出力先獲得要求の順に当該出力装置が割り付けられる。
ｂ．同じ出力装置に対して発行された複数の転送要求受信部４１からの出力先獲得要求のうち同一優先度の出力先獲得要求については、早く発行された順に当該出力装置が割り付けられる。
ｃ．同じ出力装置に対して発行された複数の転送要求受信部４１からの出力先獲得要求のうち同時に発行された同一優先度の出力先獲得要求については、入力装置番号の若い順に当該出力装置が割り付けられる。
【００７９】
また、各入力装置に対応する転送要求受信部４１と結合装置解放要求発行部４９、および、各出力装置に対応する要求サンプリング部４２と転送要求時系列記録部４３と優先度記録部４４と出力割付処理部４５は全て、その動作の進行において同じ処理部の間で相互依存性がなく、それぞれが並列に動作可能である。したがって、本調停装置４０は、各入力装置毎に異なるタイミングでフレーム転送要求が発生／終了する可変長フレームスイッチングシステムを効率良く実現するのに適している。
【００８０】
次に、本調停装置４０の動作の妥当性について説明する。まず、ある入力装置に到着したフレームを１箇所の出力装置に転送するユニキャスト転送だけを考えた場合、本調停装置４０が問題なく動作するのは明らかである。フレームを複数の出力装置に転送するマルチキャスト転送については、本実施形態ではワンショット型マルチキャスト転送を前提としているが、従来の並列調停型の調停装置において、異なる入力装置からの複数のマルチキャスト転送が互いにデッドロックの状態に陥ることなくフレーム転送が確実に処理されることを保証する方法は自明ではない。以下では、本実施形態の調停装置４０がこの点を保証できていることを説明する。
【００８１】
まず、簡単のため、フレーム転送要求に対して優先度が定義されていない場合を考える。この場合、出力割付処理部４５は図９に示す処理を全て行なう必要はなく、転送要求時系列記録部４３の前方のワードから順番に、ワード内の、対応する入力装置番号の小さい転送要求受信部４１からの出力先獲得要求に対して出力装置を割り付けていく、という一部の基本動作だけを繰り返し行なえばよい。
【００８２】
これらの条件のもとで、まず、図１７に示すように同一時刻に発行された、出力装置の競合を含む複数のマルチキャスト出力先獲得要求を考える。同一時刻に発行されたこれらの出力先獲得要求は、図１７（ａ）に示すように、競合する全ての出力装置に対応する転送要求時系列記録部４３において、同一のワード中に記録される。そして、これらの出力先獲得要求の優先度は等しいため、競合する各出力装置に対応する出力割付処理部４５において各出力先獲得要求に対して出力装置を割り付ける順番は全て同じ（具体的には、転送要求発行元の入力装置の番号の小さい順）となる。図１７の例では、図１７（ｂ）に示すように、出力割付処理部４５j、４５kにおいてともに、転送要求受信部４１aからの出力先獲得要求に出力装置を割り付けた後、転送要求受信部４１bからの出力先獲得要求に出力装置が割り付けられる。したがって、これら同時刻に発行されたマルチキャストの出力先獲得要求が互いにデッドロックの状態に陥ることはない。
【００８３】
つまり、出力割付処理部４５1〜４５Nは、要求サンプリング部４２1〜４２Nによってサンプリングされた順番で転送要求受信部４１1〜４１Nからの出力先獲得要求に対して出力装置の割付を行っているため、マルチキャスト転送要求が互いにデッドロックの状態に陥ることはない。
【００８４】
次に、異なる時刻に発行された出力装置の競合を含む複数のマルチキャストの出力先獲得要求を考える。図１８（ａ）に示すように、これらの出力先獲得要求については、競合する全ての出力装置に対応する転送要求時系列記録部４３において、異なるワード内に、出力先獲得要求が発行された時刻順に格納される。そして、これらの出力先獲得要求の優先度が等しいため、競合する各出力装置に対応する出力割付処理部４５において各出力先獲得要求に対して出力装置を割り付ける順番は全て同じ（具体的には、出力先獲得要求が発行された時刻順）となる。図１８の例では、図１８（ｂ）に示すように、出力割付処理部４５j、４５kにおいてともに、転送要求受信部４１aからの出力先獲得要求に出力装置を割り付けた後、転送要求受信部４１bからの出力先獲得要求に出力装置が割り付けられる。したがって、これらの出力先獲得要求が互いにデッドロックの状態に陥ることはない。
【００８５】
以上のことから、フレーム転送要求に対して優先度を定義しない場合には、本実施形態の要求サンプリング部４２1〜４２Nと転送要求時系列記録部４３1〜４３Nとの組合せによる出力先獲得要求の記録方法と、出力割付処理部４５1〜４５Nの一部の基本的な動作だけで、異なる入力装置からの複数のマルチキャスト転送が互いにデッドロックの状態に陥ることなくフレーム転送要求が確実に処理されることが保証されることが分かる。
【００８６】
次に、フレーム転送要求に対して優先度を導入した場合を考える。出力割付処理部４５1〜４５Nについては、図９に示す処理を行なうものとする。
【００８７】
フレーム転送要求に対して優先度を導入した場合、各出力割付処理部４５1〜４５Nは、転送要求時系列記録部４３の先頭に近いワード中の出力先獲得要求から順番に出力装置を割り付けていくわけではなく、後方のワード中の出力先獲得要求でも優先度が高いものがある場合は先に割り付けを行なう。ここで、本実施形態における各出力割付処理部４５1〜４５Nは全て互いに非同期に動作するため、出力割付処理部４５1〜４５Nの動作に単純に優先度の判定を追加するだけでは以下に述べるような問題が生じる。
【００８８】
図１９では、時刻ｔ１に転送要求受信部４１aからフレーム転送先が出力装置３０j、および出力装置３０kのマルチキャストの出力先獲得要求が優先度ｐ２で発行され、時刻ｔ１より後の時刻ｔ２において転送要求受信部４１bからフレーム転送先が同じく出力装置３０j、および３０kのマルチキャストの出力先獲得要求が優先度ｐ１で発行された様子を表している。ここで、優先度ｐ１はｐ２より高い優先度であるとする。
【００８９】
出力装置３０jに対応する出力割付処理部４５jは、ｔ１とｔ２の間の時刻に、次に出力装置を割り付ける出力先獲得要求の決定動作を開始し、時刻ｔ２より前に、最も優先度の高い要求の検索（図９におけるリストＬ１の決定）を完了したとする。この間、転送要求受信部４１bからの出力先獲得要求はまだ発行されていないので、出力割付処理部４５jは転送要求受信部４１aからの出力先獲得要求に対して当該出力装置３０jを割り付ける。この様子を図２０に示す。一方、出力装置３０kに対応する出力割付処理部４５Yは、時刻ｔ２より後に次に出力装置を割り付ける出力先獲得要求の決定動作を開始したとすると、転送要求受信部４１bからの出力先獲得要求の優先度ｐ１は転送要求受信部４１aからの転送要求の優先度ｐ２より高いので、出力割付処理部４５kは転送要求受信部４１bからの出力先獲得要求に対して当該出力装置３０kを割り付ける。この結果、図２０に示すように、転送要求受信部４１aは転送要求受信部４１bが獲得した出力装置３０kの解放を待ち、転送要求受信部４１bは転送要求受信部４１aが獲得した出力装置３０jの解放を待つことになり、互いにデッドロックの状態に陥ってしまう。
【００９０】
図９に示した出力割付処理部４５のステージ（２）、（４）は、上記のような状態の発生を回避するための処理である。図２０の例において、出力割付処理部４５kが次に出力装置を割り付ける出力先獲得要求の決定動作を開始するまでに出力割付処理部４５jが既に割り付け動作を完了していた場合、出力割付処理部４５kはステージ（２）において、転送要求受信部４１aからの出力先獲得要求がマルチキャストの出力先獲得要求で、かつ、フレーム転送先のうち、自身が管理する出力装置３０k以外の出力装置３０jをすでに獲得していることを検出する。これにより、デッドロックを回避するために、転送要求受信部４１bからの高優先度の出力先獲得要求ではなく、転送要求受信部４１aからの出力先獲得要求に出力装置３０kを割り付ける必要があることを認識できる。この様子を図２１に示す。
【００９１】
また、図２０の例において、出力割付処理部４５jと出力割付処理部４５kの動作が図２２に示すような時間的関係にあった場合、すなわち、
（ａ）出力割付処理部４５jのステージ（１）実行時において、優先度ｐ１の転送要求ｒ１はまだ発行されていない。
（ｂ）出力割付処理部４５kのステージ（１）実行時において、優先度ｐ１の転送要求ｒ１はすでに発行されている。
（ｃ）出力割付処理部４５kのステージ（２）実行時において、出力割付処理部４５jのステージ（５）、すなわち、出力装置の割り付け処理はまだ完了していない。
の全てが成り立つ場合を考える。この場合、（ａ）により、出力割付処理部４５jはステージ（１）で優先度Ｐ２をＫｍｉｎとして選択し、ステージ（３）でその優先度の出力先獲得要求を検索する。また、出力割付処理部４５kのステージ（２）実行時においてはまだ出力割付処理部４５jは出力装置の割り付けを完了していないため、出力割付処理部４５kは、ステージ（１）で優先度Ｐ１をＫｍｉｎとして選択し、ステージ（３）でその優先度の出力先獲得要求を検索する。
【００９２】
ステージ（４）は、このような状態のときにこのままデッドロックに陥ることを防ぐための処理である。このステージでは、ステージ（１）で選択した優先度Ｋｍｉｎよりも高い優先度の出力先獲得要求がステージ（１）から（３）を実行する間に新たに発行されていないかどうか確認する。ステージ（１）と同様の方法でＫｍｉｎの値を再度定め、先にステージ（１）で定めた値よりも小さい値であれば、ステージ（１）に戻り、そうでなければステージ（５）に移る。
【００９３】
図２２の例では、出力割付処理部４５jはステージ（４）の結果、優先度ｐ１を選択し直して割り付け処理を再開する。その結果、出力割付処理部４５j、４５kのいずれにおいても、転送要求受信部４１bからの出力先獲得要求に対して出力装置が割り付けられることになり、デッドロックの状態を回避することができる。
【００９４】
ただし、ステージ（４）の実行に要するシステムクロックのサイクル数は、ステージ（１）のそれよりも短くなるような実装でなければならない。図２３に、ステージ（４）の実行サイクル数がステージ（１）のそれよりも長い場合に生じる不具合の例を示す。このような場合、以下の（ａ）〜（ｃ）全てを満足するような場合が起こり得る。
（ａ）出力割付処理部４５jのステージ（４）の実行後に、優先度ｐ１の出力先獲得要求ｒ１が発行されている。
（ｂ）優先度ｐ１の転送要求ｒ１の発行後に、出力割付処理部４５kがステージ（１）の処理を開始している。
（ｃ）出力割付処理部４５kのステージ（２）実行時において、出力割付処理部４５jのステージ（５）、すなわち、出力装置の割り付け処理はまだ完了していない。
【００９５】
これらが全て満たされた場合、出力割付処理部４５j、４５kはそれぞれ優先度ｐ２、ｐ１の出力先獲得要求に対して当該出力装置を割り付けてしまい、デッドロックの状態となってしまう。このため、ステージ（４）の実行サイクル数をステージ（１）のそれよりも短くする必要がある。
【００９６】
以上のように、ステージ（２）、（４）により、各出力割付処理部４５の非同期の動作に起因するデッドロックの発生を防止することができ、フレーム転送要求に対して優先度を導入した場合でもデッドロックフリーのフレーム転送要求処理を行なうことができる。
【００９７】
【発明の効果】
以上説明したように、本発明によれば、下記のような効果を得ることができる。
（１）各出力割付処理部が、各要求サンプリング部によってサンプリングされた順番で転送要求受信部からの出力先獲得要求に対して出力装置の割付を行っているので、異なる入力装置からの複数のマルチキャストの出力先獲得要求が互いにデッドロックの状態に陥ることがない。
（２）各出力装置毎に優先度を記録するための優先度記録部が備えられているため、システム内で定義される優先度の数が増加した場合、優先度記録部のビット数と結線が優先度分だけ増加し、出力割付処理部の優先度選択に関する論理が増加するのみで対応することができる。したがって、優先度数の増加に対する回路規模の増大の度合は従来と比較して小さいと言える。
（３）要求サンプリング部によりサンプリングされた出力先獲得要求は転送要求時系列記録部により順次記録されるため、同一優先度の出力先獲得要求間においては、異なる時刻に発生した出力先獲得要求は発生した順序どおりに出力装置が割り付けられる。
【図面の簡単な説明】
【図１】本発明による一実施形態の通信装置の構成を示すブロック図である。
【図２】図１の通信装置における入力装置の構成を示す図である。
【図３】図１の通信装置における調停装置の内部構成図である。
【図４】図１の通信装置における入力装置と調停装置４０間で送受される信号とそのタイミングを示す図である。
【図５】図３の調停装置における転送要求受信部４１の構成と動作を示す図である。
【図６】図３の調停装置における要求サンプリング部４２の動作を示す図である。
【図７】図３の調停装置における転送要求時系列記録部４３の構成を示す図である。
【図８】転送要求時系列記録部４３のワード消去／詰め直し操作の概要を示す図である。
【図９】図３の調停装置における出力割付処理部４５の動作を示すフローチャートである。
【図１０】図３の調停装置における優先度記録部の構成を示す図である。
【図１１】図３の優先度記録部を用いて、出力割付処理部４５が図９中のステージ（１）の処理を実行する様子を説明した図である。
【図１２】図３の調停装置における割付要求番号部の構成、および、出力割付処理部４５が図９中のステージ（２）の処理を実行する様子を説明した図である。
【図１３】出力割付処理部４５が図９中のステージ（３）の処理を実行する様子を説明した図である。
【図１４】出力割付処理部４５が図９中のステージ（５）の処理を実行する様子を説明した図である。
【図１５】出力割付処理部４５がステージ（５）の処理を終了してから、転送要求受信部４１が入力装置に対して転送許可信号をアサートするまでの処理の流れを説明した図である。
【図１６】入力装置がフレーム転送を終了してから、結合装置２０の入出力装置間の結合を解放し、出力装置の割り付けを解放するまでの処理の流れを説明した図である。
【図１７】転送要求に優先度がない場合について、同一時刻に発行された宛先競合を含む複数のマルチキャスト転送要求間で、デッドロックが生じないことを説明する図である。
【図１８】転送要求に優先度がない場合について、異なる時刻に発行された宛先競合を含む複数のマルチキャスト転送要求間で、デッドロックが生じないことを説明する図である。
【図１９】宛先競合を含む優先度の異なる複数のマルチキャスト転送要求の一例を示す図である。
【図２０】図１９の例において、出力割付処理部４５のステージ（４）がないと仮定した場合に、宛先競合を含む優先度の異なる複数のマルチキャスト転送要求の間でデッドロックが生じることがあることを説明する図である。
【図２１】出力割付処理部４５のステージ（２）によって宛先競合を含む優先度の異なる複数のマルチキャスト転送要求間でのデッドロックが回避できることを示す図である。
【図２２】出力割付処理部４５のステージ（４）によって宛先競合を含む優先度の異なる複数のマルチキャスト転送要求間でのデッドロックが回避できることを示す図である。
【図２３】出力割付処理部４５のステージ（４）の実行サイクル数がステージ（１）の実行サイクル数よりも長くなければならないことを説明する図である。
【図２４】従来の集中調停型の通信装置の一例を示す図である。
【図２５】従来の並列調停型の通信装置の一例を示す図である。
【図２６】ワンショット型マルチキャスト転送を説明する図である。
【図２７】宛先の競合を含む複数のワンショット型マルチキャスト転送要求の間でデッドロックが生じる様子を示す図である。
【符号の説明】
１０1〜１０N    入力装置
１１    回線入力部
１２    フレーム抽出部
１３    宛先情報抽出／フレーム長計測部
１４    経路制御部
１５    入力バッファ部
１６    転送制御部
２０    結合装置
３０1〜３０N    入力装置
４０    調停装置
４１1〜４１N    転送要求受信部
４２1〜４２N    要求サンプリング部
４３1〜４３N    転送要求時系列記録部
４４1〜４４N    優先度記録部
４５1〜４５N    出力割付処理部
４６    出力割付状況記録部
４７1、４７2    マルチプレクサ（ＭＵＸ）
４８    結合装置制御部
４９1〜４９N    結合装置解放要求発行部
１２０    結合装置
１４０    調停装置
１５０1〜１５０N    調停装置
１６０1〜１６０N    データコピーバッファ
【図１】
0003655599.tif 000002
【図２】
0003655599.tif 000003
【図３】
0003655599.tif 000004
【図４】
0003655599.tif 000005
【図５】
0003655599.tif 000006
【図６】
0003655599.tif 000007
【図７】
0003655599.tif 000008
【図８】
0003655599.tif 000009
【図９】
0003655599.tif 000010
【図１０】
0003655599.tif 000011
【図１１】
0003655599.tif 000012
【図１２】
0003655599.tif 000013
【図１３】
0003655599.tif 000014
【図１４】
0003655599.tif 000015
【図１５】
0003655599.tif 000016
【図１６】
0003655599.tif 000017
【図１７】
0003655599.tif 000018
【図１８】
0003655599.tif 000019
【図１９】
0003655599.tif 000020
【図２０】
0003655599.tif 000021
【図２１】
0003655599.tif 000022
【図２２】
0003655599.tif 000023
【図２３】
0003655599.tif 000024
【図２４】
0003655599.tif 000025
【図２５】
0003655599.tif 000026
【図２６】
0003655599.tif 000027
【図２７】
0003655599.tif 000028