JPH0846590A

JPH0846590A - データ伝送システム

Info

Publication number: JPH0846590A
Application number: JP7107939A
Authority: JP
Inventors: Jiingu Kuin; ジィングクィン
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1994-04-07
Filing date: 1995-04-07
Publication date: 1996-02-16
Also published as: US5392280A

Abstract

(57)【要約】【目的】動的な帯域の分割とロスのない伝送を提供す
る高品質な帯域伝送を可能とするデータ伝送システムを
得る。【構成】この発明のデータ伝送システムにおいては、
同期タイムスロットを用いてデータを伝送する同期デー
タ伝送手段と、非同期タイムスロットを用いてデータを
伝送する非同期データ伝送手段が、データを伝送する。
非同期タイムスロットは、同期タイムスロットの未使用
時間分拡張される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、ディジタル通信ネッ
トワークに関するものである。特に、複数のユーザに対
して伝送能力を保証し、新しいデータ伝送スケジューリ
ングとフィードバックフローコントロールシステムを提
供することによって、ネットワーク利用の拡大を図るも
のである。

【０００２】

【従来の技術】ディジタル通信ネットワークは、２つの
タイプに分類される。同期ネットワークと非同期ネット
ワークである。同期ネットワークにおいて、通信能力は
以下のようにユーザに割り当てられる。即ち、時間を一
定の大きさのフレームに分割し、個々のユーザに割り当
てる方法である。非同期ネットワークにおいて、情報は
パケット又はセルと呼ばれる独立したデータ単位で構成
されている。それぞれのデータ単位は、時間フレームに
制御されることなく、独立してネットワーク上を伝送さ
れる。

【０００３】同期通信ネットワークの長所は、与えられ
た通信能力が、個々のユーザに割り当てられると言う点
である。即ち、例えば、伝送帯域幅やディレイ制約等、
ネットワークで提供されるある種の質的なサービスが保
証されているという点である。ところが、同期ネットワ
ークは、様々なビット伝送速度に対応した伝送を行うに
は適していない。なぜならば、通信のリソースを複数の
ユーザで共有することができないからである。今日のデ
ィジタル電話ネットワークは、リアルタイムの音声会話
をかなりよくサポートしている非同期通信ネットワーク
の一例ではあるが、大量のデータをバースト伝送するよ
うなコンピュータを用いたデータ伝送には適していると
はいえない。

【０００４】一方、非同期伝送ネットワークは、伝送リ
ンクに様々なビット伝送速度を多重化することによっ
て、ネットワークの効率化を達成している。しかし、同
時にユーザに対する質の低下を招いてもいる。現在のコ
ンピュータネットワークにおいては、非同期ネットワー
クがどのようにコンピュータによるデータ通信をサポー
トするかを試行しているにすぎず、非同期通信ネットワ
ークは、オーディオビデオデータ等リアルタイムのマル
チメディアデータの伝送には、十分利用できるものとは
いえない。

【０００５】非同期伝送モード（ＡＴＭ：Ａｓｙｎｃｈ
ｒｏｎｏｕｓＴｒａｎｓｆｅｒＭｏｄｅ）は、同期ネ
ットワークと非同期ネットワークの両者の長所を、同時
に実現するために開発された技術である。特に、ＡＴＭ
ネットワークにおいては、ユーザの情報は５３バイト固
定長のセルで構成されている。このセルは、タイムフレ
ームの拘束を受けずに、既に確立されているパスに沿っ
て非同期に伝送される。伝送帯域幅がダイナミックに全
てのユーザによって分割されるので、ネットワークの効
率化が図れる。しかしながらＡＴＭネットワークは、非
同期伝送が元々持っていたサービスの質の低下という欠
点も持っている。ＡＴＭネットワーク上で、ネットワー
クの高度の利用を保ちながら、サービスの質を保証し、
大量のデータ量の伝送を制御することは困難である。こ
の問題を解消するために、多くのトラヒック制御が試み
られているが、同期伝送と非同期伝送の長所を同時に得
られるＡＴＭはまだ実現されていない。

【０００６】特に、トラヒック制御の問題を解決するた
めには、２つのアプローチがなされている。予防制御と
反応制御である。予防制御とは、ネットワークが輻輳レ
ベルに達するのを防ぐことである。一般にトラヒックの
流れを制御させるためには、ネットワークの入口でデー
タの入力を制御したり、帯域幅を割り当てることが行わ
れている。ＡＴＭスイッチにおいては、入力制御手段が
コネクションのセットアップ時において、新しいコネク
ションを受け付けるかどうか決定する。帯域実施部は、
個々のコネクションが以下のことを保証するようにモニ
タする。即ち、コネクションのセットアップ時に定義さ
れた帯域に実トラヒックフローが従うことを保証する。
スイッチにおいて、適切なセル伝送スケジュール方式を
用いることで、予防制御はユーザにある種の質的なサー
ビスをしばしば提供できる。質的なサービスとは、例え
ば、伝送帯域保証からディレイ制約にわたるサービスで
ある。予防制御における大きな問題の１つは、可変ビッ
ト伝送速度の場合に、即ち、ビット伝送速度が幅広く変
化するトラヒックの場合に、ネットワークの効率化を図
ることが難しいという点である。ユーザは、通常ネット
ワークの負荷の状況がより多くのメッセージを送ること
ができるときでも、一旦割り当てられた以上のメッセー
ジを送ることを許可されない。このためにＡＴＭネット
ワークは、同期伝送ネットワークのように動作する。ま
た、トラヒック管理及びスケジューリング方式は実現す
るのが高価である。

【０００７】一方、反応制御は、フィードバック機構を
備え、ネットワークの負荷状況に応じて、トラヒックを
設定するものである。ネットワークは、最も効果的であ
るようにトラヒックを受け入れる。また、個々のコネク
ションが運ぶことができるトラヒック量には、予め制限
は設定されない。それ故、コンピュータネットワークに
おいて発生するようなバーストデータ伝送に適した反応
制御を行うことによって、動的な帯域分割とネットワー
クの効率良い利用を実現することができる。ところが、
反応制御を用いてもサービスの質を保証することは困難
である。それは、個々のコネクションが用いることがで
きる帯域幅がネットワークの実際の負荷状況に左右され
るからである。非同期伝送のように、サービスの質が低
い伝送方式においては、反応制御は、確実な帯域幅を要
求するリアルタイムのアプリケーションをサポートする
ことはできない。リアルタイムのアプリケーションと
は、例えば、オーディオビデオデータのような対話型の
マルチメディアデータの伝送である。

【０００８】

【発明が解決しようとする課題】前述した観点から、同
期伝送と非同期伝送を統合するアプローチを提供する必
要がある。同期伝送と非同期伝送の統合とは、動的な帯
域の分割とロスのない伝送の両方を同時に提供する高品
質な帯域伝送を可能とするネットワークである。

【０００９】高品質な帯域伝送の目的は、ユーザに帯域
を保証してコネクションを提供することである。帯域を
保証することは、今日の回線交換の通信ネットワークの
ような非同期通信ネットワークにおいて提供されるよう
なサービスを、ネットワークで実現することである。

【００１０】ロスのない動的な帯域分割伝送は、利用者
にリソースが利用可能な限り予め保証された範囲以上に
帯域を利用することを許可する。特に、ある利用者に割
り当てられていない帯域、或は、割り当てられてはいる
が、使用されていない帯域を他のユーザに解放する。ま
た、この動的な帯域分割によってバッファのオーバフロ
ーが起こらないことを保証する。この目的を達成するこ
とは、ネットワークが伝送帯域を有効に利用することを
可能にする。そしてまた、今日の非同期通信ネットワー
クにおいて、可変ビット伝送速度の伝送をサポートする
上で非常に重要である。

【００１１】保証された帯域伝送と動的な帯域分割の統
合は、適正な課金方式が用いられた場合には、ネットワ
ーク利用者と、ネットワーク提供者の双方に利益をもた
らす。例えば、１つの方法として、コネクションに課金
する際に帯域幅に応じた課金と実際に伝送されたセルの
数に応じた課金を合計して料金を算出する方法がある。
この課金方法によれば、テレビ会議システムの利用者
は、会議の内容が重要でない時には、ビデオ（映像）の
スイッチを切るということによって、ネットワーク料金
を節約することができる。ビデオ（映像）のスイッチを
切っても、接続は保たれているので、利用者は音声だけ
で会議の様子をモニタすることができ、重要な局面では
再びビデオ伝送を再開することができる。一方、ネット
ワーク提供者は、ネットワークの利用者が増えることに
よって利益を得ることができる。

【００１２】

【課題を解決するための手段】この発明のデータ交換ネ
ットワークのデータ伝送システムは、以下の要素を備え
たことを特徴とする。（ａ）同期タイムスロットと非同期タイムスロットを有
するタイムフレームを用い、上記タイムフレーム内の一
定の同期タイムスロットを上記複数のユーザに割り当て
る割当手段、（ｂ）あらかじめ決定された同期タイムス
ロットを用いて、上記ユーザに関連するデータを伝送す
る同期データ伝送手段、（ｃ）上記タイムフレーム内の
非割当時間の範囲まで拡張された上記非同期タイムスロ
ットを用いてデータを伝送する非同期データ伝送手段。

【００１３】上記非割当時間は、同期タイムスロット内
の未使用時間に関連づけられていることを特徴とする。

【００１４】上記非同期タイムスロットは、上記非同期
タイムスロットの前に位置する同期タイムスロットの未
使用時間の範囲まで拡張されることを特徴とする。

【００１５】上記データ交換ネットワークは、上流スイ
ッチと、上記上流スイッチから出力される出力リンクを
入力リンクとして入力する下流スイッチを備え、上記上
流スイッチと上記下流スイッチはバッファを有するとと
もに、上記上流スイッチに対応する上記下流スイッチの
バッファが一定量に達したとき、上記上流スイッチに上
記非同期伝送を中断させる非同期伝送中断手段を備えた
ことを特徴とする。

【００１６】上記上流スイッチは、対応するバッファに
結合された入力リンクであって、所定のキューに対応す
るデータを上記バッファにロードする複数の入力リンク
を有し、上記同期データ伝送手段と非同期データ伝送手
段は、上記同期伝送と非同期伝送に供給するためにラウ
ンドロビン方式で上記キューに順番でアクセスする伝送
スケジュール手段を備え、上記伝送スケジュール手段
は、空きキューと対応する同期タイムスロットの未使用
時間の合計を検出し、データ伝送の為に後続の非同期タ
イムスロットを上記未使用時間により拡張する手段とを
備えたことを特徴とする。

【００１７】上記スケジュール手段は、上記非同期伝送
中断手段に結合されていることを特徴とする。

【００１８】上記下流スイッチは、上記バッファのバッ
ファ占有状態を示すコードを生成するコード生成手段を
備え、上記非同期伝送中断手段は、上記下流スイッチか
ら上記上流スイッチへのリンクを備えたことを特徴とす
る。

【００１９】コネクション型セル交換ネットワークにお
けるデータ伝送システムおいて、あらかじめ決定された
タイムフレーム内で、同期タイムスロットと非同期タイ
ムスロットを交互に発生させるデータ伝送フォーマット
を用いることを特徴とする。

【００２０】上記同期タイムスロットは固定長であり、
上記非同期タイムスロットは可変長であって、上記非同
期タイムスロットの長さは、上記非同期タイムスロット
の前に位置する同期タイムスロットの使用済み時間量に
対応して決定されることを特徴とする。

【００２１】同期タイムスロットの長さは、上記同期タ
イムスロットに対応するコネクションの帯域要請により
決定されることを特徴とする。

【００２２】

【作用】この発明の、データ伝送システムにおいては、
割当手段が、タイムフレーム内の一定の同期タイムスロ
ットを複数のユーザに割り当てる。また、同期データ伝
送手段が、あらかじめ決定された同期タイムスロットを
用いて、上記ユーザに関連するデータを伝送する。非同
期データ伝送手段は、上記タイムフレーム内の非割当時
間の範囲まで拡張された上記非同期タイムスロットを用
いてデータを伝送する。

【００２３】また、非同期データ伝送手段が用いる非同
期タイムスロットは、上記タイムフレーム内の非割当時
間の範囲まで拡張されているが、上記非割当時間は、同
期タイムスロット内の未使用時間に関連づけられてい
る。

【００２４】また、上記非同期タイムスロットは、上記
非同期タイムスロットの前に位置する同期タイムスロッ
トの未使用時間の範囲まで拡張される。

【００２５】上記データ交換ネットワークは、上流スイ
ッチと、上記上流スイッチから出力される出力リンクを
入力リンクとして入力する下流スイッチを備え、上記上
流スイッチと上記下流スイッチはバッファを有するとと
もに、非同期伝送中断手段を備えている。非同期伝送中
断手段は、上記上流スイッチに対応する上記下流スイッ
チのバッファが一定量に達した時、上記上流スイッチに
上記非同期伝送を中断させる。

【００２６】上記上流スイッチは、対応するバッファに
結合され、所定のキューに対応するデータを上記バッフ
ァにロードする複数の入力リンクを有している。上記同
期データ伝送手段と非同期データ伝送手段に備えられた
伝送スケジュール手段は、上記同期伝送と非同期伝送に
供給するためにラウンドロビン方式で上記キューに順番
でアクセスする。上記スケジュール手段は、空きキュー
と対応する同期タイムスロットの未使用時間の合計を検
出しデータ伝送の為に後続の非同期タイムスロットを上
記未使用時間により拡張する手段とを備えている。

【００２７】上記スケジュール手段は、上記非同期伝送
中断手段に結合されており、上記非同期伝送中断手段と
対応して、機能する。

【００２８】上記下流スイッチが備えているコード生成
手段は、上記バッファのバッファ占有状態を示すコード
を生成する。上記非同期伝送中断手段は、上記下流スイ
ッチから上記上流スイッチへのリンクを備えており、下
流スイッチにおいて生成されたコードを上流スイッチに
伝えることができる。

【００２９】この発明のコネクション型セル交換ネット
ワークにおけるデータ伝送システムにおいては、あらか
じめ決定されたタイムフレーム内で、同期タイムスロッ
トと非同期タイムスロットを交互に発生させるデータ伝
送フォーマットが用いられる。

【００３０】上記同期タイムスロットは固定長であり、
上記非同期タイムスロットは可変長であって、上記非同
期タイムスロットの長さは、上記非同期タイムスロット
の前に位置する同期タイムスロットの使用済み時間量に
対応して決定される。

【００３１】また、この発明においては、同期タイムス
ロットの長さは、上記同期タイムスロットに対応するコ
ネクションの帯域要請により決定される。

【００３２】

【実施例】

実施例１．図１は、この発明のデータ伝送システムのブ
ロック図である。図において、１０は上流スイッチ、１
２は上流スイッチの下流に設けられた下流スイッチであ
る。１４は上流スイッチ１０に入力される複数の入力リ
ンク、１６は上流スイッチ１０から出力される複数の出
力リンクであり、１つの出力リンクは、下流スイッチ１
２の入力リンク１８となっている。下流スイッチ１２は
複数の出力リンク２０を有し、入力リンク１８から入力
されたデータは、これらの出力リンクの１つを選択して
出力される。２２は下流スイッチ１２に備えられたバッ
ファであり、入力データを記憶し、そのデータを１つ又
は複数の出力リンクに送り出す。

【００３３】２４は上流スイッチ１０に備えられたバッ
ファである。各リンクに割り付けられたコネクションを
経由してデータが入力され、バッファ２４は、これら複
数のデータを入力して、従来のスイッチング方式により
セル待ち行列（以下、キューともいう）２６，２８，３
０に記憶する。図に示すように、入力リンク１４は、上
流スイッチ１０において、タイムドラウンドロビンスケ
ジューリング方式により、出力リンク１６に関連づけら
れる。タイムドラウンドロビンスケジューリング方式に
よれば、セル伝送スケジューラ３２のスケジュールによ
り、セル待ち行列２６，２８，３０に記憶されたデータ
は、順番にアクセスされ出力される。バッファ２４は、
コネクション毎に１つのキューを用いて構成される。コ
ネクションとは、２つのエンドユーザを接続する１つの
パスである。ここで、コネクション１，２，３に対し
て、キュー２６，２８，３０がそれぞれ対応して設けら
れているものとする。図に示すように、各キューには、
コネクションに関連づけられたＧＴＴ（Ｇｕａｒａｎｔ
ｅｅｄＴｒａｎｓｍｉｓｓｉｏｎＴｉｍｅ）が同期
伝送を行う時間（以下、同期転送時間という）として用
意される。ＧＴＴ１は、コネクション１用の同期伝送時
間である。図に示すように、コネクション１のデータ３
４を伝送するのに、ＧＴＴ１の内、一部分しか使用され
ない。即ち、コネクション１には、未使用の同期伝送時
間がある。また、図に示すように、コネクション２のデ
ータ３８は、このコネクション２に割り当てられたＧＴ
Ｔ２（図のデータ３６に相当）をオーバした部分であ
り、このデータ３８を伝送するためには、ＧＴＴ２以外
にさらに時間が必要である。コネクション１に未使用時
間があるので、コネクション２の追加のデータ３８は、
コネクション１の未使用時間を用いて下流スイッチ１２
に非同期に伝送される。

【００３４】フレームシーケンス４０を用いて、この伝
送を説明する。まず、ＧＴＴ１用に生成された同期タイ
ムスロットを用いて、コネクション１からデータ３４が
送られる。続いて、ＧＴＴ１の未使用時間を用いて、コ
ネクション２のデータ３８が非同期に送られる。最後
に、コネクション２のＧＴＴ２用の同期タイムスロット
を用いて、データ３６が送られる。このように、ＧＴＴ
１の未使用時間を用いて、非同期モードで追加のデータ
３８を伝送することができる。

【００３５】このように、同期伝送時間ＧＴＴの未使用
時間を検出し、可変長の非同期タイムスロットでデータ
を伝送することによって、伝送帯域を有効に利用するこ
とができる。さらに、もし、下流スイッチに充分なバッ
ファスペースがあるならば、データの損失が確実に発生
しなくなるというメリットも得られる。ところが、実際
には、いつも充分なバッファスペースがあるとは限らな
い。そこで、上流スイッチ１０と下流スイッチ１２の間
に両方向のリンクを設ける。ここでは、下流スイッチ１
２から上流スイッチ１０にフィードバックパス５０が備
えられる。下流スイッチ１２のバッファ占有ステータス
は、Ｆビットを用いて、非同期伝送コントローラ５２に
伝えられる。非同期伝送コントローラ５２は、下流スイ
ッチ１２に充分なバッファスペースがないときには、上
流スイッチ１０の下流スイッチ１２へのデータ伝送を中
断させる。タイムドラウンドロビンのスケジューリング
は、トランスミッタ５６へのコネクションに基づいて、
セル伝送スケジューラ３２の管理下で行われる。空きキ
ュー検出手段５８は、伝送中にキューが空であることを
検出し、同期伝送モードを非同期伝送モードに切り換え
ることを許可する。同期時間モニタ６０は、空きキュー
の検出によって、同期伝送時間に未使用時間があること
を判断する。この同期時間モニタ６０の出力により、ト
ランスミッタ５６は制御される。

【００３６】前述した例は、同期伝送時間に未使用時間
がある場合のみ非同期伝送を行うようにしているが、予
め同期伝送と非同期伝送の両方を行う時間を確保し、同
期伝送時間に未使用時間がある場合に、その未使用時間
を非同期伝送用に用いるようにしてもよい。図２と図３
にその例を示す。

【００３７】図２は、タイムフレームの構成を示すブロ
ック図である。図において、６２はタイムフレームであ
る。６４，６６，６８はタイムフレーム６２に含まれる
同期タイムスロットであり、コネクションに対応するＧ
ＴＴに応じて長さが変化する複数のタイムスロットであ
る。また、７０，７２，７４は可変長の非同期タイムス
ロットである。図２に示す例は、非同期タイムスロット
７０，７２，７４が同期タイムスロット６４，６６，６
８の後に存在する場合を示している。

【００３８】図３は、非同期タイムスロットを拡張した
タイムフレームの構成を示すブロック図である。同期タ
イムスロット６４に、コネクション１のデータのない部
分がある時、その部分を非同期タイムスロット７０の拡
張部に割り当てることができる。図において、矢印７６
で示す部分が、非同期タイムスロット７０の拡張部であ
る。

【００３９】図４は、図１に示すセル伝送スケジューラ
３２で使用されるアルゴリズムの流れ図である。ここで
は、図２及び図３に示したタイムフレームを用いる場合
について説明する。８０において、初期値として、ｉに
１を設定する。次に、８２において、コネクションｉに
対応するキューｉのセルをコネクションのＧＴＴを用い
て、同期伝送する。８４では、タイマを用いて、コネク
ションｉの同期伝送時間が終了したかどうか判断する。
同期伝送時間が残っている時、８６において、キューｉ
に他のセルがあるかどうか判断する。キューｉが空の
時、８８において非同期伝送が行われる。また、８４の
判断において、同期伝送時間が終了した時も非同期伝送
は行われる。非同期時間の終了は、９０において、タイ
マで判断される。そして、９２において、ｉの値を増加
させ、次のコネクションの同期伝送に移る。

【００４０】図５と図６を用いて、データの輻輳につい
て説明する。図において、１０，１２はスイッチであ
り、９４，９６，９８はリンクである。また、図６にお
いて、１００はバッファである。図５は、データが正常
に伝送される場合を示している。図６は、データの輻輳
が発生する場合を示している。図５は、スイッチ１０か
ら次のスイッチ１２へのセルの伝送を示すブロック図で
ある。スイッチ１０に入力されるコネクション１（Ｃ
１）とコネクション２（Ｃ２）は、リンク帯域をそれぞ
れ１／２使用している。図中、Ｂ／２は、ＢＡＮＤ（帯
域）の１／２を意味している。コネクション１とコネク
ション２は、スイッチ１０において、時分割多重され、
リンク９４に出力され、リンク９４からスイッチ１２に
入力される。スイッチ１２で、コネクション１のデータ
は、出力リンク９６に出力されるが、コネクション２の
データは、出力リンク９８にスイッチされる。また、リ
ンク帯域の１／２を占有するコネクション３（Ｃ３）の
データが、コネクション１のデータと一緒に出力リンク
９６に出力される。コネクション１が１／２帯域、コネ
クション３が１／２帯域なので、ちょうど１帯域とな
る。

【００４１】一方、データの輻輳が発生する場合につい
て、図６を用いて説明する。図６において、コネクショ
ン２は、１／４帯域しか使わないので、コネクション１
は、スイッチ１０からリンク９４への出力においては、
リンク帯域を１／４増加させ、３／４まで使用できる。
スイッチ１２で、出力リンク９６のデータ量は、コネク
ション１が３／４帯域、コネクション３が１／２帯域な
ので、３／４＋１／２＝５／４となり、出力リンク９６の帯域幅Ｂを越えてしまうこと
になる。ここで、帯域幅Ｂを越えたコネクション１のデ
ータを蓄積するために、バッファ１００が用いられる。
また、図に点線１０２で示すＦビット伝送により、スイ
ッチ１０にバッファ１００のデータ蓄積状態使用が通知
される。

【００４２】図７は、図４の流れ図において、８８に示
した非同期伝送処理の詳細図である。１１０に示す矢印
で、下流スイッチからＦビットが入力されると、１１２
において、Ｆ＝ＥＮＡＢＬＥかどうか判断する。その判
断結果に従って、セル伝送、アイドルセル伝送のいずれ
かが行われる。アイドルセル伝送は、下流スイッチへの
データ伝送の停止に相当する。Ｆ＝ＥＮＡＢＬＥでない
時、１１４において、アイドルセルが伝送される。アイ
ドルセルは、下流スイッチにより無視されるセルのこと
であり、アイドルセルは下流スイッチで廃棄される。Ｆ
＝ＥＮＡＢＬＥの時、１１６において、伝送すべきデー
タがあるかチェックする。即ち、すべてのキューが空か
どうか判断する。伝送すべきデータがない時は、アイド
ルセルが伝送される。また、伝送すべきデータがある時
は、１１８において、セルが伝送される。

【００４３】通信ネットワークにおいて、帯域伝送は従
来、同期転送モード（ＳＴＭ：Ｓｙｎｃｈｒｏｎｏｕｓ
ＴｒａｎｓｆｅｒＭｏｄｅ）で行われていた。ＳＴ
Ｍにおいては、時間は、複数の固定長のフレームに分割
され、各フレームはさらに小さいタイムスロットに分割
される。帯域伝送は、各フレームのいくつかのタイムス
ロットを、個々のコネクションに固定的に割り当てるこ
とにより実現される。ＳＴＭは従来の通信ネットワーク
においては、成果を納めているが、今後の統合ネットワ
ークには適していない。それは、帯域割当が固定的で、
帯域が充分に活用できないからである。特に、ＳＴＭに
おいては、１つのコネクションに異なる帯域幅を割り当
てるようにタイムスロットを管理するのが困難である。
また、ＳＴＭにおいては、複数のコネクションが動的
に、伝送帯域を共有するようにタイムスロットを管理す
るのが困難である。

【００４４】ＡＴＭは、コネクションにタイムスロット
を動的に割り当てるセルベースの伝送方式を用いてい
る。個々のセルは、独立した単位なので、いつでも伝送
可能である。このようにして、複数の利用者が、伝送帯
域を効果的に共有でき、ネットワークの効率化をはかる
ことができる。ところが、動的な帯域の共有を行うと、
コネクションへの帯域の確保が保証されないという問題
がある。

【００４５】この問題を解決するために、ＡＴＭネット
ワークにおいて用いられるのが、Ｓｔｏｐ−ａｎｄ−Ｇ
ｏセル伝送方式である。ＳＴＭ方式と同様に、Ｓｔｏｐ
−ａｎｄ−Ｇｏセル伝送方式においても、時間はフレー
ムに分割される。Ｓｔｏｐ−ａｎｄ−Ｇｏセル伝送方式
では、複数のコネクションに各フレーム中の決まったタ
イムスロットを固定的に割り当てることはせず、タイム
フレーム毎に各コネクションのセルの数を制限するため
にストップキューとゴーキューを使用する。このように
して、帯域が柔軟に管理される。即ち、１つのコネクシ
ョンに対して異なる帯域幅を持たせることができる。と
ころが、フレーム内のセルの数を制限することは、動的
な帯域共有をしたという要求に反することになる。

【００４６】動的な帯域共有を実現するために、この発
明においては、ＡＴＭネットワーク内で帯域を提供する
ために、タイムドラウンドロビン方式のスケジューリン
グアルゴリズムを用いている。タイムドラウンドロビン
スケジューリング方式は、Ｓｔｏｐ−ａｎｄ−Ｇｏ方式
と同様の帯域割付機能を実現する。さらに、このタイム
ドラウンドロビンスケジューリング方式は、フィードバ
ックフロー制御方式を実現できるという長所がある。こ
のフィードバックフロー制御方式は、同期伝送、非同期
伝送のコンセプトを取り入れることにより、容易に実現
できるものである。また、このフィードバックフロー制
御方式により、動的な帯域共有とロスのない伝送を実現
することができる。特に、この発明においては、時間が
ラウンドロビン周期（ＲＲＰ：Ｒｏｕｎｄ−Ｒｏｂｉｎ
−Ｐｅｒｉｏｄ）と呼ばれる固定サイズのフレームに分
割される。１つのラウンドロビン周期ＲＲＰの中で、各
コネクションは、それぞれ一定量のＧＴＴを与えられ
る。このＧＴＴの中では、複数のセルが、フィードバッ
クフロー制御方式の制御を受けずに伝送される。各コネ
クションが周期的に一定の伝送時間を割り当てられるこ
とから、これを同期伝送と呼ぶ。このようにして、保証
された帯域割り当てと動的な帯域共有を実現できる。

【００４７】説明の便宜の為に、時間は、１つのＡＴＭ
セルの伝送時間を単位として示すものとする。また、Ｒ
ＲＰとＧＴＴはすべて整数とする。また、『コネクショ
ン』という用語は、バーチャルサーキット（Ｖｅｒｔｉ
ａｌｃｉｒｃｕｉｔｓ：ＶＣ）、バーチャルパス（ｖ
ｉｒｔｕａｌｐａｔｈ：ＶＰ）の代わりに用いられて
おり、一般にＡＴＭについて述べる時にコネクションが
１つ又は複数のＶＣ／ＶＰを示す表現として用いられる
のと同様である。この発明のタイムドラウンドロビンセ
ル伝送アルゴリズムを、図８から図１０を用いて、以下
に示す。アルゴリズム１．（タイムドラウンドロビン伝送）１．各リンクには、ラウンドロビン周期ＲＲＰが割り当
てられ、ラウンドロビンタイマが設けられる。ラウンド
ロビン周期ＲＲＰは、ラウンドロビン伝送の一単位時間
である。ラウンドロビンタイマは、各コネクションがセ
ルの伝送に使用できる時間（ラウンドロビンタイムＲＲ
Ｔ）をカウントする。２．コネクションの帯域取得要請に応じて、各コネクシ
ョンは、コネクションが設定されるリンクのＧＴＴを割
り当てられる。リンク上の１コネクションに割り当てら
れる帯域は、ＧＴＴ／ＲＲＰ×リンク帯域で算出される。３．伝送リンク上にｎ個のコネクションＣＮ１，・・
・，ＣＮｎがあり、それぞれ対応するＧＴＴ１，・・
・，ＧＴＴｎがあるものとする。Ｔｉ＝ＧＴＴ１＋，・・・，＋ＧＴＴｉの式で、コネクション１からコネクションｎまでのＧＴ
Ｔの累計時間Ｔｉが求められる。即ち、Ｔｉは、ｉ＝１の時、ＧＴＴ１ｉ＝２の時、ＧＴＴ１＋ＧＴＴ２ｉ＝３の時、ＧＴＴ１＋ＧＴＴ２＋ＧＴＴ３ｉ＝ｎの時、ＧＴＴ１＋ＧＴＴ２＋ＧＴＴ３＋，・・
・，＋ＧＴＴｎとなる。また、 δ＝ＲＲＰ−Ｔｎの式で、タイムフレームの非割り当て伝送時間δが求め
られる。Ｔｎは、ｉ＝ｎの時のＴｉである。この時、以
下に示すタイムドラウンドロビン方式で、セルの伝送が
スケジュールされる。

【００４８】ステップ１．初期値の設定ｉ：＝１、ラウンドロビンタイムＲＲＴ：
＝０ステップ２．コネクションＣＮｉからＧＴＴｉを用いて
セル伝送する。具体的には、コネクションＣＮｉの複数
セルをラウンドロビンタイムＲＲＴがＴｉ（Ｔｉ＝ＧＴ
Ｔ１＋，・・・，＋ＧＴＴｉ）になるまで、又は、コネ
クションＣＮｉの全セルが伝送完了するまで、同期セル
として伝送する。ステップ３．後述する、非同期伝送アルゴリズムで以下
の条件式を満たすまで、セルを伝送する。ＲＲＴ＞＝Ｔｉ＋［ｉδ／ｎ］セルは、非同期セルとして伝送される。ステップ４．ｉ＜ｎの時、ｉ：＝ｉ＋１とし、ステップ
２に分岐する。そうでない時、ステップ１に分岐する。
図８に、上記タイムドラウンドロビン方式に対応する流
れ図を示す。

【００４９】図９は、ラウンドロビン方式によるセル伝
送のキュー構造を示す図である。また、図１０は、各コ
ネクションが同期セルを伝送するため、全ＧＴＴを使用
する時の同期伝送と非同期伝送の交替のパターンを示す
ブロック図である。コネクションが、自分に割り当てら
れたＧＴＴのすべてを使いきらない時は、残りの時間
は、図１０において、小さな矢印で示すように、非同期
伝送に使用される。小さな矢印で示す部分が、非同期伝
送に使用される、拡張された部分である。

【００５０】コネクションｉは、自分のセルを伝送する
時間として、ラウンドロビン周期ＲＲＰの内、ＧＴＴｉ
を保証されるので、Ｂをリンクの帯域幅とすると、リン
ク上において、以下の平均帯域Ｂｉを使用可能であるこ
とが保証される。Ｂｉ＝（ＧＴＴｉ／ＲＲＰ）×Ｂもし、ラウンドロビン周期ＲＲＰに、スイッチ（ノー
ド）に到着するセルの数が、コネクションｉのＧＴＴｉ
により伝送されるセルの数より小さければ、１単位時間
が１セルの伝送時間に等しいことを考えると、コネクシ
ョンｉは、伝送の順番が回ってくる度に、ノードにキュ
ーイングされているセルのすべてを伝送できることにな
る。これにより、ラウンドロビン周期ＲＲＰ内のコネク
ションの平均セル到着率がコネクション割り当て帯域を
越えないという条件において、以下のような、アルゴリ
ズム１の２つの特性が導かれる。１つは、ノードｉにお
いて、セルのキューイングディレイは、最悪の場合、ラ
ウンドロビン周期ＲＲＰ内に限られるということであ
る。２つ目は、コネクションｉで必要とされる最大バッ
ファのサイズは、ＧＴＴｉにより伝送されるセルの数に
限られるということである。

【００５１】この実施例におけるＡＴＭネットワーク
は、この２つの特性のおかげで、今日の回線交換ネット
ワークによりサポートされた支援サービスを可能にして
いる。なぜならば、アプリケーションが自分に割り当て
られた通信帯域を越えない限り、限られたディレイとロ
スのない伝送が、保証されるからである。

【００５２】ラウンドロビン周期ＲＲＰは、アルゴリズ
ム１のパフォーマンスに影響する重要なパラメータであ
る。一方では、バッファの必要性を低くし、セルのディ
レイを小さくするためにＲＲＰを小さく設定することが
望ましい。また、一方では、ＲＲＰは帯域幅割り当ての
最小単位を決定する。リンクの帯域幅をＢとすると、コ
ネクションに割り当て可能な最小帯域は、Ｂ／ＲＲＰで
ある。例えば、１５０Ｍｂ／ｓのリンクに６４Ｋｂ／ｓ
のコネクションをセットアップすると、ＲＲＰは１５
０，０００／６４＝２，３４４となり、リンク上の最大
セルディレイは、約６．３ｍｓとなる。

【００５３】上記の基本タイムドラウンドロビンアルゴ
リズムは容易に拡張可能である。例えば、高帯域のコネ
クションをいくつかの低帯域のコネクションに分割する
ことで、最悪の場合のディレイをより小さくすることが
できる。また、低帯域の複数のコネクションを多重化し
て１つの高帯域コネクションとすることによって、より
細かい帯域割り当てを達成することができる。図９にお
いては、ＧＴＴの非割り当て伝送時間δをフレーム内に
回帰配置しているが、他の方法でも良い。例えば、容易
に実現したいという目的によって、或いは、レイテンシ
ーが低い通信に適合させたいという目的によって他の方
法で、非割り当て伝送時間δを分配配置しても良い。

【００５４】アルゴリズム１に説明したように、ＧＴＴ
／ＲＲＰ×リンク帯域が、リンク上でコネクションに保
証される帯域である。ラウンドロビン周期ＲＲＰを用い
て帯域幅Ｂのリンク上で帯域幅Ｂｃのコネクションを確
立するために、コネクションに必要なＧＴＴは、ＧＴＴ＝［Ｂｃ・ＲＲＰ／Ｂ］であり、ここで［ｘ］は、ｘと等しいか又はｘ以上の、
最小の整数値と等しい限界値とする。コネクションの設
定は、リンク上を通過するすべてのコネクションのＧＴ
Ｔの合計がＲＲＰを越えない時、リンク上で受け付けら
れる。コネクションの追加削除は、ＧＴＴの累計時間Ｔ
ｉと非割り当て伝送時間δの値の変更を必要とするの
で、ラウンドロビン周期ＲＲＰの最後に行われる。

【００５５】上記のコネクション設定手順には、１つの
問題点がある、それは、ＧＴＴ＝［Ｂｃ・ＲＲＰ／Ｂ］
というＧＴＴを計算する時の限界値の算出オペレーショ
ンによっては、１つのコネクションに対して僅かに異な
る帯域幅が割り当てられるかもしれないことである。Ｒ
ＲＰが異なれば、上記ＧＴＴも異なって算出される可能
性がある。従って、リンク毎にＲＲＰに異なれば、その
コネクションに対するＧＴＴもリンク毎に異なってしま
う。こうして、上流のリンクであるコネクションに割り
当てられた帯域が、下流のリンクでそのコネクションに
割り当てられた帯域よりも、大きいとセルの損失が起こ
る危険性がある。しかし、コネクションは、通常リンク
上に発生元から目的地（宛先）まで、シーケンシャルに
確立されるので、上流のリンクでコネクションに割り当
てられた帯域をそのまま、次の下流のリンクで必要なＧ
ＴＴを計算するのに用いることで、この問題は回避でき
る。このように、ロスのない同期伝送が保証される。

【００５６】アルゴリズム１は、もしも、ステップ３に
おいて非同期伝送が許可されなければ、まったくＳＴＭ
やＳｔｏｐ−ａｎｄ−Ｇｏセル伝送方式と同様に動作す
る。各コネクションは、一定量の帯域を割り当てられ、
未使用の帯域や、未割り当ての帯域は、無駄になる。そ
こで、残っている帯域を「効果的に」、かつ、「安全
に」使用するために、非同期伝送アルゴリズムが考えら
れた。ここで、「効果的に」とは、可能な限り多くの非
同期セルが伝送されることを意味している。また、「安
全に」とは、多くのセルを送りすぎて、下流ノードでオ
ーバフローを起こしセルの損失を起こすことがないよう
に、多すぎるセルを伝送しないことを意味している。

【００５７】図１１，図１２は、動的な帯域共有が正し
く制御されない場合に、バッファオーバフローを引き起
こすことを説明する図である。図１１において、コネク
ションＣ１，Ｃ２，Ｃ３は、それぞれリンク伝送帯域の
１／２を割り当てられているとする。各コネクション
が、それぞれ自分に割り当てられた帯域だけを使用して
いる時は、輻輳は、起こらない。ところが、ある時、コ
ネクションＣ２が割り当てられた帯域の１／２（即ち、
リンク伝送帯域の１／４）しか使用せず、余った半分を
動的にコネクションＣ１が使用したとする。この時、図
１２に示すように、下流のノードにおいて、輻輳が起こ
りセルの喪失が発生する。セルの損失を完全に回避する
ため、動的な帯域共有は、即ち、アルゴリズム１による
非同期伝送は、下流ノードに充分なバッファスペースが
ある時だけ許可されるべきである。

【００５８】この発明においては、リンクバイリンク
（リンク対リンク）のフィードバックフロー制御方式
が、ノードの非同期転送をイネイブルしたりディセイブ
ルしたりするために使われている。図１３に示すよう
に、下流のノードＢからカレントなノードＡに流れる各
セルにＦビットが用いられ、ノードＡからノードＢへの
非同期転送を制御するために使用される。説明を簡単に
するために、ここでは、両方向の伝送帯域は、同一とす
る。Ｆビットには、ＥＮＡＢＬＥＤ／ＤＩＳＡＢＬＥＤ
のいづれかが記されている。Ｆ＝ＥＮＡＢＬＥＤのセル
をノードＢから受け取っている時だけ、ノードＡはノー
ドＢへ非同期セルの伝送が許可される。このフィードバ
ックフロー制御方式では、ノードＡの非同期伝送をディ
セイブルするにより、バッファオーバフローが起こらな
いことを確実にする。また、ノードＢでバッファオーバ
フローが起こりそうもない時に、ノードＡの非同期伝送
をイネイブルする事によりバッファのアンダーフローが
起こらないことを確実にする。これらのために、ノード
Ｂにおいて、適当なＦビット設定アルゴリズムを使用す
る。

【００５９】簡単に言うと、フィードバック情報だけを
持つアイドルセルを、空いているリンクを用いてノード
ＢからノードＡへ伝送するセル挿入方式が用いられる。
それゆえ、ノードＡは、ノードＢから連続して、Ｆ＝Ｅ
ＮＡＢＬＥＤ／Ｆ＝ＤＩＳＡＢＬＥＤのセルのどちらか
を受け取る。図１４に示すように、ノードＡからのセル
を記憶するためにノードＢにＭセル分のバッファスペー
スが割り当てられているとする。同期伝送は、フィード
バック制御方式では制御されないので、最悪の場合、同
期セルを記憶するために、ＲＲＰで伝送されるセル分
（以下、ＲＲＰ同期セル数（計算式上、単にＲＲＰと記
す）を、ＲＲＰの同期伝送モードで伝送される同期セル
の数とする）のバッファが必要となる。その結果、非同
期セルの割当は、Ｍ−ＲＲＰ同期セル数となる。Ｒをノ
ードＢからノードＡへのラウンドトリップディレイとす
る。そうすると、ノードＢがＦビットをＤＩＳＡＢＬＥ
Ｄとし始めた後、Ｒに達するまで、ノードＡから非同期
セルを受け取ることになる。以下、Ｒ非同期セル数（計
算式上、単にＲと記す）を、ノードＢがＦビットをＤＩ
ＳＡＢＬＥＤとし始めた後、ノードＢがノードＡから受
け取る非同期セルの数とする。Ｆビット設定アルゴリズ
ムは、非同期セルの数がＭ−ＲＲＰ−Ｒに達した時、Ｆ
＝ＤＩＳＡＢＬＥＤに設定し、非同期セルの数が、Ｍ−
ＲＲＰ−Ｒを下回った時、Ｆ＝ＥＮＡＢＬＥＤに設定す
る。これを、アルゴリズム２として以下に示す。

【００６０】アルゴリズム２．（Ｆビット設定アルゴリ
ズム）１．ノードＡから到着し、ノードＢに一時的に蓄積され
る非同期セルの数をカウンタＣでカウントする。２．Ｃ＞＝Ｍ−ＲＲＰ−Ｒの時、Ｆ：＝ＤＩＳＡＢＬＥ
Ｄを設定する。それ以外の時、Ｆ：＝ＥＮＡＢＬＥＤを
設定する。上記アルゴリズム２の流れ図を、図１５に示
す。

【００６１】この単純なアプローチには、２つの問題点
がある。１つ目は、非同期セルのカウントの問題であ
る。ＡＴＭネットワークにおいて、１つのコネクション
に属する複数のセルは、ＦＩＦＯで伝送される。このＦ
ＩＦＯの規則に従うと、ノードＡから到着する非同期セ
ルは、ノードＢにおいて、非同期セルとして伝送される
のではなく、同期伝送時間ＧＴＴで伝送されるかもしれ
ない。即ち、同期伝送セルと非同期セルのいずれの形式
にもなるため、非同期セルの数のみをカウンタＣにより
カウントしても、バッファオーバフローは予防できな
い。これは、以下のように問題を複雑にする。つまり、
同期セルに割り当てられる同期伝送時間を縮め、ラウン
ドロビン周期ＲＲＰよりも長い時間ノードＢに同期セル
を留まらせることになる。その結果、同期セルを蓄積す
るために、ＲＲＰ同期セル数よりも多くのバッファスペ
ースが必要とされる。従って、非同期セルをカウントす
るだけでは、バッファオーバフローは予防できない。２
つ目は、バッファアンダーフローの問題である。アルゴ
リズム２では、バッファアンダーフローを予防できな
い。アルゴリズム２では、ノードＢがセルを出力し、Ｒ
非同期セル数に達するまでバッファに空きバッファがで
きるのをを持つことになるが、Ｒ非同期セル数が大きな
値であると、ノードＡから非同期伝送は許可されない場
合がある。これは、大きなノード間伝送ディレイを持つ
ネットワークに巨大なバッファの必要性と帯域の浪費を
引き起こす。最悪の場合、Ｒ＞Ｍ−ＲＲＰの時、非同期
伝送は、完全に停止される。

【００６２】第１の問題を解決するために、各コネクシ
ョン毎にＦＩＦＯの規則に基づく伝送を行う代わりに、
ＧＴＴでは同期セルを最初に伝送し、非同期伝送モード
では非同期セルを最初に伝送するスケジューリングアル
ゴリズムをノードＢが用いる。こうすれば、カウンタＣ
は、ノードＡから到着して、ノードＢに記憶されている
非同期セルの数を示すことになる。その理由は、このス
ケジューリングポリシーを用いれば、ＧＴＴでは同期セ
ルを最初に伝送するので、どの同期セルもラウンドロビ
ン周期ＲＲＰよりも長いディレイにはならないからであ
る。それゆえ、ＲＲＰ同期セル分のバッファスペース
は、ノードＡからのすべての同期セルに充分適応する。
その結果、ノードＢの非同期セルの数（カウンタＣの
値）が、Ｍ−ＲＲＰ−Ｒを越えないよう確認するだけ
で、バッファオーバフローを防止することができる。

【００６３】ところが、上記のスケジューリングアルゴ
リズムは、実際には、ＡＴＭには使用できない。なぜな
ら、ＡＴＭは、コネクション毎のセルの伝送順序を維持
する必要があるからである。言い替えれば、ＦＩＦＯス
ケジューリングは、同一のコネクションに属するセルに
使用されるべきであるということである。この問題は、
セルのタイプ（同期又は非同期のタイプ）を”交換”
（ｓｗａｐｐｉｎｇ）する事で解決する。特に、ノード
Ｂがコネクションｉの非同期セルをＧＴＴｉで既に伝送
済みであり、コネクションｉの残りの同期セルがまだノ
ードＢにある時、同期セルが伝送済みで、非同期セルが
バッファ内に残っているかのように、これらの２つのセ
ルのタイプが”交換”される。以下に、この方法の詳細
なアルゴリズムを示す。

【００６４】アルゴリズム３．（カウンタＣの管理）１．非同期セルの数を記録するために、カウンタＣを使
用する。加えて、コネクションｉの同期セルを記憶する
ために、カウンタＳｉが使用される（ｉ＝１，・・・，
ｎ）。２．カウンタＣは、ノードＡから非同期セルが到着する
と、１加算する。カウンタＳｉは、コネクションｉの同
期セルがノードＡから到着すると、１加算する。３．ノードＢがコネクションｉのセルをＧＴＴｉで伝送
する時、（ａ）セルが、同期セルならば、カウンタＳｉ
から１減算し、（ｂ）セルが、非同期セルならば、カウ
ンタＳｉ＞０の時、カウンタＳｉから１減算し、それ以
外は、カウンタＣから１減算する。４．ノードＢがコネクションｉのセルを、非同期伝送ア
ルゴリズムで伝送する時、（ａ）セルが非同期セルなら
ば、カウンタＣから１減算し、（ｂ）セルが、同期セル
ならば、カウンタＣ＞０の時、カウンタＣから１減算
し、それ以外は、カウンタＳｉから１減算する。上記ア
ルゴリズム３の流れ図を、図１６から図１８に示す。

【００６５】第２のバッファアンダーフローの問題を解
決するためには、カウンタＣ＞＝Ｍ−ＲＲＰ−Ｒの時、
Ｆ＝ＤＩＳＡＢＬＥＤを常には設定しないアルゴリズム
が必要である。アルゴリズム２において、カウンタＣが
増加してＭ−ＲＲＰ−Ｒに達した時、Ｆ＝ＤＩＳＡＢＬ
ＥＤを設定するのは、以下の理由である。ラウンドトリ
ップディレイが存在することを考慮したので、ノードＢ
は、Ｆ＝ＤＩＳＡＢＬＥＤになった後でも、ノードＡか
らの非同期セルをＲ非同期セル数まで受信できる。とこ
ろが、ノードＢは、Ｆ＝ＤＩＳＡＢＬＥＤが設定された
後、ノードＡからの非同期セルを１つも受信しない場合
がある。そこで、ラウンドトリップディレイ経過時に、
カウンタＣの値がＭ−ＲＲＰよりも大きくなければ、ノ
ードＢは、ＦビットをＥＮＡＢＬＥＤに設定したセル
を、Ｍ−ＲＲＰ−Ｃセル数のセルだけノードＡに送出す
る事ができる。Ｍ−ＲＲＰ−Ｃセル数のセルは、この数
までの非同期セルの伝送ををノードＡに許可するもので
ある。以下に、Ｆビット設定アルゴリズムについて述べ
る。

【００６６】アルゴリズム４．（Ｆビット設定アルゴリ
ズム２）１．カウンタＣは、アルゴリズム３と同様に用いられ
る。２．ｔはカレントな時間を示すものとする。ｔｄｅとｔ
ｅｄは、それぞれＦがその値をＤＩＳＡＢＬＥＤからＥ
ＮＡＢＬＥＤへ、またＥＮＡＢＬＥＤからＤＩＳＡＢＬ
ＥＤへ変化させる時刻を示している。Ｃｄｅは、時間ｔ
ｄｅにおけるＣの値を指している。Ｆビットは、以下の
ように設定される。

【００６７】ステップ１．Ｃ＜Ｍ−ＲＲＰ−Ｒの時、
Ｆ：＝ＥＮＡＢＬＥＤを設定する。それ以外の時、ステ
ップ２に分岐する。ステップ２．ｔ−１の時点でＣ＜Ｍ−ＲＲＰ−Ｒの時、
そして、ｔの時点でＣ＝Ｍ−ＲＲＰ−Ｒになる時、ｔｅ
ｄ：＝ｔＦｉ＝ＤＩＳＡＢＬＥＤを設定する。それ以
外の時、ステップ３に分岐する。ステップ３．ｔ＜ｔｅｄ＋ラウンドトリップディレイＲ
の時、Ｆ：＝ＤＩＳＡＢＬＥＤを設定する。それ以外の
時、ステップ４に分岐する。ステップ４．Ｃ＝Ｍ−ＲＲＰの時、Ｆ：＝ＤＩＳＡＢＬ
ＥＤを設定する。それ以外の時、ステップ５に分岐す
る。ステップ５．ｔ−１の時点で、Ｆ＝ＤＩＳＡＢＬＥＤの
時、ｔｄｅ：＝ｔ，Ｆ：＝ＥＮＡＢＬＥＤ，Ｃｄｅ：＝
Ｃ（ただし、Ｃ≦Ｍ−ＲＲＰ）を設定する。それ以外の
時ステップ６に分岐する。ステップ６．ｔ＜ｔｄｅ＋（Ｍ−ＲＲＰ−Ｃｄｅセル数
の伝送時間）の時、Ｆ：＝ＥＮＡＢＬＥＤを設定する。
それ以外の時、Ｆ：＝ＤＩＳＡＢＬＥＤ，ｔｅｄ：＝ｔ
を設定する。

【００６８】上記アルゴリズムの流れ図を、図１９に示
す。また、上記のアルゴリズムに対応する図を、図２０
に示す。図において、Ｘ軸は時間、Ｙ軸はカウンタＣで
ある。ＣがＭ−ＲＲＰ−Ｒを下回る時、ノードＡに非同
期セルの伝送を許可しても常に安全である。それゆえ、
ステップ１において、ノードＢからノードＡに送られる
セルは、Ｆ＝ＥＮＡＢＬＥＤを示している。ステップ２
では、ＣがＭ−ＲＲＰ−Ｒを越える時を検出し、ノード
Ａの非同期伝送をストップさせるため、ｔｅｄとＦ＝Ｄ
ＩＳＡＢＬＥＤを設定する。ところが、ラウンドトリッ
プディレイＲの為に、ノードＢはまだノードＡからの非
同期セルを受信し続ける。そこで、ステップ３では、Ｆ
＝ＤＩＳＡＢＬＥＤの設定のままである。最悪の場合、
Ｒを越えて、余分な非同期セルがノードＢに到着し、ｔ
ｅｄ＋Ｒの時点でＣにＭ−ＲＲＰを越えさせてしまう。
この状況では、ステップ４でまだ、Ｆ＝ＤＩＳＡＢＬＥ
Ｄのままである。ステップ５において、ＦビットがＥＮ
ＡＢＬＥＤに設定される時（ＣがＭ−ＲＲＰを下回る
時）を検出し、ｔｄｅ，Ｃｄｅを設定する。すると、ス
テップ６において、Ｍ−Ｒ−ＣｅｄまでのセルがＦ＝Ｅ
ＮＡＢＬＥＤにセットされる。その後、Ｃ＞＝Ｍ−ＲＲ
Ｐ−Ｒの時、ＦがＤＩＳＡＢＬＥＤに設定され、ｔｅｄ
がカレントな時間に設定される。これは、もし、ＣがＭ
−ＲＲＰ−Ｒを超え続けるならば、ステップ３におい
て、ラウンドトリップディレイＲの間、ＦビットをＤＩ
ＳＡＢＬＥＤに設定する。

【００６９】アルゴリズム４にはまだ、無駄の点があ
る。なぜならば、ステップ３に示すように、ｔｅｄ設定
（つまり、ＦビットがＥＮＡＢＬＥＤからＤＩＳＡＢＬ
ＥＤに変更された時）の後、ラウンドトリップディレイ
Ｒに達するまで、ＤＩＳＡＢＬＥＤになったままとなっ
ている。その理由は、非同期セルがノードＡから連続し
て到着すると考えているからである。非同期セルが連続
してくるとは限らないので、ＤＩＳＡＢＬＥＤになった
ままとなっているのは無駄である。例えば、ステップ６
において、ＦビットがＤＩＳＡＢＬＥＤに設定された
後、ある状況下では、Ｍ−ＲＲＰ−Ｃｄｅに達するまで
の非同期セルだけが到着する。従って、ステップ６にお
いて、ｔｅｄを設定してからラウンドトリップディレイ
Ｒに達するまで、ＤＩＳＡＢＬＥＤを保つ必要はない。
それ故、実現のためのコストをかければ、アルゴリズム
４よりも更に効果的なＦビット設定アルゴリズムを開発
できることが可能である。

【００７０】非同期伝送アルゴリズムの他の方法とし
て、ノードＡがノードＢからＦ＝ＥＮＡＢＬＥＤのセル
を受信している間に使用される伝送スケジューリングポ
リシーがある。言い替えると、ノードＡがノードＢに非
同期伝送を許可する時、ノードＡは、どのセルを伝送す
るべきだろうか。この質問に対する答は、非同期伝送に
期待するパフォーマンスに依存する。もしも、複数のコ
ネクションを公正に扱いたいならば、ピュアラウンドロ
ビンスケジューリング方式を使用すれば良い。また、コ
ネクションの重要度を区別するならば、優先度付けされ
たスケジューリングや、タイムドラウンドロビンスケジ
ューリングを使用すれば良い。

【００７１】この発明のフィードバックフロー制御シス
テムを他の方法と比較してみよう。元来、一般に、不変
のビット伝送速度を用いたデータ伝送においては、必要
ではなかったので、通信の分野では、フィードバックフ
ロー制御の考え方は、なかなか受け入れられなかった。
ところが、ＡＴＭが紹介され、可変ビット伝送速度をサ
ポートする必要がでてくると、数多くのフィードバック
フロー制御方式が提案された。なぜならば、フィードバ
ックフロー制御機構なしでは、充分なネットワークの活
用を達成することができなかったからである。この機構
を実現する多くの方法が提案され、これらの方法に共通
するのは、リンク毎、かつ、コネクション毎のクレジッ
トベースのフィードバックフロー制御方法である。これ
らの方法と比較すると、この発明は、次の２点で、大幅
に簡易化されている。

【００７２】１つは、コネクション毎ではなく、リンク
毎のフィードバック制御が用いられている点である。従
来の方式として、あるコネクションがリンク上のそのコ
ネクション以外のすべてのコネクションのデータ伝送を
停止させてしまうという問題を回避するために、コネク
ション毎のフィードバック制御方式が使用されていた。
コネクション毎の制御を行うには、各コネクションは、
自分自身のクレジットカウントを持たなければならな
い。クレジットカウントは、下流のノードから個別に伝
送される情報を用いて更新される。また、バッファスペ
ースは、静的に各コネクションに割り当てられる。この
結果、クレジット管理機構が複雑となり、動的な帯域分
割を達成するために大容量のバッファが必要とされる。

【００７３】この発明のタイムドラウンドロビンセル伝
送方式では、各コネクションは、一定量の最低帯域を保
証され、コネクションがブロックされることが全くな
い。このように、この発明のタイムドラウンドロビンセ
ル伝送方式では、リンク上のすべてのコネクションを、
単一のコネクションとして扱うリンク毎のフィードバッ
ク制御方式を用いることができる。これにより、有意に
フィードバック機構が簡易化され、必要とされるバッフ
ァ容量が減少する。

【００７４】２つ目に簡易化された点は、空きバッファ
数をクレジットカウントの値として知らせるクレジット
ベースのフィードバック制御方式でなく、空きバッファ
の有無を知らせる状態ベースのフィードバック制御方式
であるという点である。下流ノードのバッファのカレン
トな占有状態を示すために、クレジットカウントの値で
なくフィードバックセルの１ビットだけを用いる。これ
により、下流ノードから上流ノードに流れる通常セル
（ｒｅｇｕｌａｒｃｅｌｌ）にフィードバック情報をエ
ンコードする事が可能になる。また、ノードが特別なフ
ィードバック用セルを生成する負担をなくせる。また、
通常セルにフィードバック情報を運ばせることにより、
セル挿入方式を用いた連続フィードバック制御の実現が
可能となる。

【００７５】この２つの簡易化により、この発明のシス
テムにおいては、同等な帯域分割性能を維持しながら、
従来のフィードバック制御方式よりもより小さいバッフ
ァスペースをより容易に実現している。

【００７６】ここで、この発明のＡＴＭ交換機における
トラヒック制御方式の実現について述べる。その目的
は、この発明のシステムが、既存のＡＴＭ交換機に特別
に何も加えないで実現されているのを示すことである。
図２１は、シェアードバッファメモリを使用するＡＴＭ
交換機である。図において、２００はシェアードバッフ
ァメモリ、２０２はコントロールユニット、２０４は多
重化装置（ＭＵＸ）、２０６は多重分離装置（ＤＭＵ
Ｘ）である。入力されるセルは多重化され、シェアード
バッファメモリ２００に記憶される。その後、関連する
出力リンクに多重分離され、次のノードに伝送される。
コントロールユニット２０２は、多重化装置（ＭＵＸ）
２０４が入力セルを記憶できるように、メモリ２００の
空きアドレスを供給する。また、コントロールユニット
２０２は、メモリ２００に記憶されたセルのアドレスを
セル伝送のために、ＤＭＵＸに供給する。

【００７７】ラウンドロビンセル伝送方法を実現するた
めには、各コネクション毎にＦＩＦＯセルキューを維持
する必要がある。１つの方法として、図２２に示すよう
な、リンクドリストキュー構造を使用する方法がある。
図において、２１０はタグ、２１２はシェアードバッフ
ァメモリ２００に記憶されたセルである。タグ２１０
は、キューに記憶されている次のセルのタグの位置を示
すポインタである。各コネクションのキューの最初のセ
ル（先頭セル）と最後のセル（末尾セル）のアドレス
は、コントロールユニット２０２の中のコネクションル
ックアップテーブル２２６に記憶される。

【００７８】図２３にコントロールユニットの構造図を
示す。コントロールユニットはセルキューを管理し、伝
送されるセルのスケジュールを行う。セルのスケジュー
ルは、以下のように行われる。

【００７９】まず最初に、アイドルアドレスプール２２
０に、メモリ２００の空きアドレスが記憶される。空き
アドレスには、入力したセルが記憶される。図２３のパ
ス１に示すように、アイドルアドレスプール２２０か
ら、各入力セル毎に１つのアドレスが割り当てられる。
セルが伝送されると、そのセルのシェアードバッファメ
モリ２００中のアドレスがパス２を介して、アイドルア
ドレスプール２２０に返される。

【００８０】次に、読み出しアドレスレジスタ２２２
が、図２３に示すパス３を介して、出力リンク毎に、次
に伝送されるべきセルのメモリ中のアドレスを提供す
る。読み出しアドレスレジスタ２２２は、パス４を介し
てコントロールサーキット２２４により、使用している
セル伝送スケジューリングアルゴリズムに従って、更新
される。

【００８１】続いて、図２４に示すコネクションルック
アップテーブル２２６を用いて、各コネクションの情報
が記憶される。この情報には、この発明のトラヒック制
御方法を実現するために有用である。例えば、セルキュ
ーの最初のセルのアドレスと最後のセルのアドレス、割
り当てられたＧＴＴｉ、同期セルのカウントＳｉ、所望
のラウンドロビンの順序を実現するためのネクストコネ
クションポインタと、ラストコネクションポインタ等が
記憶される。コネクションルックアップテーブル２２６
は、独立したコンポーネントとして構成しても良い。ま
た、ＡＴＭ交換機に既存のｖｉｒｔｕａｌ−ｃｉｒｃｕ
ｉｔルーティングテーブルと結合させて構成しても良
い。

【００８２】セルキューの管理は、以下のように行われ
る。セルが入力リンクに到着すると、セルが記憶される
空きアドレスが、アイドルアドレスプール２２０から読
み出される。この空きアドレスとコネクション識別番号
を含む入力セルのヘッダーが、パス５とパス６を介し
て、コントロールサーキット２２４に送られる。コネク
ションルックアップテーブル２２６のＦＣＡ（ファース
トセルアドレス）がセットされていない時、即ち、キュ
ーが空の時、ＦＣＡとＬＣＡ（ラストセルアドレス）の
両方が、パス７を介して空きアドレスの値を用いてセッ
トされる。そうでなければ、ＬＣＡだけが、空きアドレ
スの値を用いてセットされ、ラストセルアドレスの元の
値は、パス７とパス５を介してＭＵＸ２０４に送られ
る。これにより、元のラストセルアドレスに記憶されて
いるセルのタグが空きアドレスの値で更新される。

【００８３】セルが伝送されると、ＦＣＡは、キューの
中の次のセルのアドレスに更新されなければならない。
これは、パス８とパス７を介して、伝送されたセルのタ
グをＦＣＡに書くことにより行われる。コネクションル
ックアップテーブル２２６を見る回数を減らすために、
この操作は、コネクション交換時にのみ行われる必要が
ある。コネクション交換時とは、トランスミッタがある
コネクションのセルの伝送をやめて、次のコネクション
に切り換えるときである。

【００８４】ＦＩＦＯセルキューが、各コネクションに
割り当てられると、コントロールサーキット２２４にタ
イムドラウンドロビンセル伝送アルゴリズムをインプリ
メントすることは簡単である。時間は、１セル伝送時間
を単位として計測される出力リンク毎に、ラウンドロビ
ンタイマとして動作するカウンタが用いられる。セル０
がこれから伝送されるセルとし、セル１が次に伝送され
るセルだとする。アルゴリズム１に定められた規則によ
り、コントロールサーキット２２４は、セル１のアドレ
スを読み出しアドレスレジスタ２２２に供給するため
に、以下に述べる３つのアクションの１つを行う。セル
１のアドレスは、以下のｐ１から導かれる。１．セル１とセル０が同一のコネクションに属する時、
ｐ１：＝セル０のタグを設定する。２．セル１がセル０のコネクションとは異なるコネクシ
ョンｉに属する時、ｐ１：＝「コネクションルックアッ
プテーブルＣＬＴに記憶されたコネクションｉのファー
ストセルアドレスＦＣＡ」を設定する。３．次に伝送されるべきセルがない時、ｐ１にシェアー
ドバッファメモリ２００に記憶されたフィードバック情
報のみを運ぶアイドルセルのアドレスを設定する。即
ち、セルの挿入を行う。

【００８５】この発明のフィードバックフロー制御方式
も同様に、容易に実現できる。ＡＴＭセルヘダーの１ビ
ットが、Ｆビットとして用いられ、もう１ビットが同期
セルを非同期セルと区別するために用いられる。ＡＴＭ
セルヘダーの３ビットのＧｅｎｅｒｉｃＦｌｏｗＣ
ｏｎｔｒｏｌ（ＧＦＣ）ビットの使用方法については、
定義されていないことから、３ビットの内、２ビットが
利用可能と考えられる。これらの２ビットの値は、コン
トロールサーキット２２４により、アルゴリズム１とア
ルゴリズム４に従って決定され、図２３に示すパス４と
パス３を介して、ＤＭＵＸ２０６に転送される。そし
て、伝送時にセルに挿入される。

【００８６】以上のように、リンクドリストキュー構造
を用いて、この発明のトラヒック制御方式が容易に既存
のＡＴＭ交換機の構造で実現できる。しかし、１つのセ
ルが複数のキューに登場するシェアードバッファスイッ
チにおけるマルチキャスト伝送をサポートすることがで
きないという問題がある。この問題は、拡張リンクドリ
ストデータ構造を用いることで解決される。図２５にお
いて、複数のキューに属するセルは、それぞれキューの
次のセルをポイントする複数のタグを使用している。そ
れぞれのタグをキューに関連づけることにより、拡張リ
ンクドリストデータ構造でマルチキャストセルを取り扱
うことが可能になる。関連付けは、明示的にタグ中にキ
ューＩＤを書き込んでも良いし、又は、暗示的に示す方
法でも良い。暗示的とは、例えば、ｉ番目のタグは、ｉ
番目のキューに対応するという方法である。また、キュ
ーｉでセルの伝送完了後、タグｉをクリアーするように
しておき、すべてのタグがクリアーされたかどうかチェ
ックする事で、容易に、バッファからマルチキャストセ
ルを消す時期を決定できる。

【００８７】シェアードバッファメモリ２００におい
て、拡張リンクドリストキュー構造を実現する方法は２
つある。以下にその方法を示す。

【００８８】１つは、タグフィールドを拡大する方法で
ある。各セルのタグフィールドは、ポインタの最大数を
格納するまで大きくすることができる。ポインタの最大
数とは、スイッチのポートの数である。例えば、６４Ｋ
セルを記憶可能なシェアードバッファメモリを備えた１
６×１６のスイッチは、１セルのタグフィールドに、２バイト×１６ポート＝３２バイトの長さが必要となる。

【００８９】２つ目の方法は、間接アドレス付け方法で
ある。すべてのセルが、マルチキャストセルというわけ
ではないので、１セルのタグフィールドを保持するだけ
の大きさにすることによって、バッファのオーバヘッド
を減少させることが可能である。上記の例では、タグフ
ィールドは２バイトになる。ユニキャストセルでは、タ
グは、図２２に示すように、直接、キューの次のセルを
ポイントする。マルチキャストセルでは、タグは、図２
６に示すように、実ポインタが記憶される場所への間接
ポインタとして使用される。この方法によれば、平均バ
ッファオーバヘッドを減らすことができるが、より高速
なシェアードバッファメモリを必要とする。なぜなら
ば、１つのマルチキャストセルを伝送するのに２度のバ
ッファアクセスを行うからである。

【００９０】最後に、拡張リンクドリスト構造は、フォ
ールトトレラントにも有効であることを述べておく。な
ぜならば、複数のタグをキューの次のセルへの冗長ポイ
ンタとしても利用できるからである。

【００９１】

【発明の効果】この発明によれば、タイムフレーム内の
非割当時間を、データ伝送に利用できる。

【００９２】また、この発明によれば、同期タイムスロ
ット内の未使用時間を、有効に利用できる。

【００９３】また、この発明によれば、非同期タイムス
ロットの前に位置する同期タイムスロットの未使用時間
の範囲まで拡張されるので、動的にタイムスロットの管
理ができる。

【００９４】また、この発明によれば、下流スイッチの
バッファの使用量に応じて、非同期伝送を中断させるの
で、データのロスを防ぐことができる。

【００９５】また、この発明によれば、ネットワークの
効率よい利用が可能になる。

【００９６】また、この発明によれば、ネットワークの
負荷状況に応じて、トラヒックの設定が可能になる。

【００９７】また、この発明によれば、下流スイッチの
状況を、上流スイッチにフィードバックできる。これに
より、ネットワークが輻輳レベルに達するのを防ぐこと
ができる。

【００９８】この発明によれば、ネットワークを動的に
管理できる。

【００９９】また、この発明によれば、負荷状況に対応
した、ネットワークの有効利用ができる。

【０１００】また、この発明によれば、帯域幅をダイナ
ミックに管理できる。

【図面の簡単な説明】

【図１】この発明のデータ伝送システムのブロック図
である。

【図２】この発明のタイムフレームの構成を示すブロ
ック図である。

【図３】この発明の非同期タイムスロットを拡張した
タイムフレームの構成を示すブロック図である。

【図４】この発明のセル伝送スケジューラのアルゴリ
ズムの流れ図である。

【図５】この発明の実施例のデータ輻輳を説明する図
である。

【図６】この発明の実施例のデータ輻輳を説明する図
である。

【図７】この発明の非同期伝送処理の詳細図である。

【図８】この発明のタイムドラウンドロビン方式に対
応する流れ図である。

【図９】この発明のラウンドロビン方式によるセル伝
送のキュー構造を示す図である。

【図１０】この発明の同期伝送と非同期伝送の交替の
パターンを示すブロック図である。

【図１１】この発明の実施例のバッファオーバフロー
を説明する図である。

【図１２】この発明の実施例のバッファオーバフロー
を説明する図である。

【図１３】この発明のノード間のＦビットを含むセル
伝送を示す図である。

【図１４】この発明のノードＢのバッファ割り当てを
示す図である。

【図１５】この発明のセル伝送スケジューラのアルゴ
リズムの流れ図である。

【図１６】この発明のセル伝送スケジューラのアルゴ
リズムの流れ図である。

【図１７】この発明のセル伝送スケジューラのアルゴ
リズムの流れ図である。

【図１８】この発明のセル伝送スケジューラのアルゴ
リズムの流れ図である。

【図１９】この発明のセル伝送スケジューラのアルゴ
リズムの流れ図である。

【図２０】この発明の実施例の時間とカウンタＣの値
の変化を示す図である。

【図２１】この発明のシェアードバッファメモリを使
用するＡＴＭ交換機のブロック図である。

【図２２】この発明のリンクドリストキュー構造図で
ある。

【図２３】この発明のコントロールユニットの構造図
である。

【図２４】この発明のコネクションルックアップテー
ブルを示す図である。

【図２５】この発明のマルチキャストセルの処理を示
す図である。

【図２６】この発明の間接アドレス付け方法を用いた
拡張リンクドリストキュー構造を説明する図である。

【符号の説明】

１０上流スイッチ、１２下流スイッチ、１４入力
リンク、１６出力リンク、２２，２４バッファ、２
６，２８，３０セル待ち行列（キュー）、３２セル
伝送スケジューラ、５２非同期伝送コントローラ、５
６トランスミッタ、５８空きキュー検出手段、６０
同期時間モニタ。

Claims

【特許請求の範囲】

【請求項１】以下の要素を備えたデータ交換ネットワ
ークのデータ伝送システム（ａ）同期タイムスロットと非同期タイムスロットを有
するタイムフレームを用い、上記タイムフレーム内の一
定の同期タイムスロットを上記複数のユーザに割り当て
る割当手段、（ｂ）あらかじめ決定された同期タイムス
ロットを用いて、上記ユーザに関連するデータを伝送す
る同期データ伝送手段、（ｃ）上記タイムフレーム内の
非割当時間の範囲まで拡張された上記非同期タイムスロ
ットを用いてデータを伝送する非同期データ伝送手段。
【請求項２】上記非割当時間は、同期タイムスロット
内の未使用時間に関連づけられていることを特徴とする
請求項１記載のデータ伝送システム。
【請求項３】上記非同期タイムスロットは、上記非同
期タイムスロットの前に位置する同期タイムスロットの
未使用時間の範囲まで拡張されることを特徴とする請求
項１記載のデータ伝送システム。
【請求項４】上記データ交換ネットワークは、上流ス
イッチと、上記上流スイッチから出力される出力リンク
を入力リンクとして入力する下流スイッチを備え、上記
上流スイッチと上記下流スイッチはバッファを有すると
ともに、上記上流スイッチに対応する上記下流スイッチのバッフ
ァが一定量に達したとき、上記上流スイッチに上記非同
期伝送を中断させる非同期伝送中断手段を備えたことを
特徴とする請求項１記載のデータ伝送システム。
【請求項５】上記上流スイッチは、対応するバッファ
に結合された入力リンクであって、所定のキューに対応
するデータを上記バッファにロードする複数の入力リン
クを有し、上記同期データ伝送手段と非同期データ伝送
手段は、上記同期伝送と非同期伝送に供給するためにラ
ウンドロビン方式で上記キューに順番でアクセスする伝
送スケジュール手段を備え、上記伝送スケジュール手段
は、空きキューと対応する同期タイムスロットの未使用
時間の合計を検出し、データ伝送の為に後続の非同期タ
イムスロットを上記未使用時間により拡張する手段とを
備えたことを特徴とする請求項４記載のデータ伝送シス
テム。
【請求項６】上記スケジュール手段は、上記非同期伝
送中断手段に結合されていることを特徴とする請求項５
記載のデータ伝送システム。
【請求項７】上記下流スイッチは、上記バッファのバ
ッファ占有状態を示すコードを生成するコード生成手段
を備え、上記非同期伝送中断手段は、上記下流スイッチ
から上記上流スイッチへのリンクを備えたことを特徴と
する請求項６記載のデータ伝送システム。
【請求項８】コネクション型セル交換ネットワークに
おけるデータ伝送システムおいて、あらかじめ決定されたタイムフレーム内で、同期タイム
スロットと非同期タイムスロットを交互に発生させるデ
ータ伝送フォーマットを用いるデータ伝送システム。
【請求項９】上記同期タイムスロットは固定長であ
り、上記非同期タイムスロットは可変長であって、上記
非同期タイムスロットの長さは、上記非同期タイムスロ
ットの前に位置する同期タイムスロットの使用済み時間
量に対応して決定されることを特徴とする請求項８記載
のデータ伝送システム。
【請求項１０】同期タイムスロットの長さは、上記同
期タイムスロットに対応するコネクションの帯域要請に
より決定されることを特徴とする請求項９のデータ伝送
システム。