JP2888376B2

JP2888376B2 - 複数トラヒック・クラス用の交換装置

Info

Publication number: JP2888376B2
Application number: JP7517739A
Authority: JP
Inventors: イリアディス、イリアル; ギューリン、ロック、エー．
Original assignee: インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Priority date: 1993-12-31
Filing date: 1993-12-31
Publication date: 1999-05-10
Anticipated expiration: 2014-05-10
Also published as: DE69328380T2; DE69328380D1; EP0737392A1; US5742606A; JPH09504672A; WO1995018499A1; EP0737392B1

Description

【発明の詳細な説明】本発明は、複数の入出力ポート間のデータ・トラヒッ
クを処理する交換機に関する。このデータ・トラヒック
は、少なくとも２つの異なるデータ・クラス、すなわ
ち、異なる特性、必要帯域、または異なる遅延感度を有
するデータを含む。

［発明の背景］並列マルチプロセッサ・コンピューティングから広域
の遠隔通信網に至る広い応用分野において、情報の高速
交換がますます重要な要因になりつつある。規模と目的
が明確に異なるにもかかわらず、これらの応用分野は必
要な高度の並列性から生ずる基本的な問題を共有してい
る。直面している最も基本的な問題は、調整と競合の問
題である。媒体がマイクロプロセッサ、データ記憶装
置、データ・バス、銅線または光フアイバのいずれであ
るかに関係なく、共通の媒体を共有する参加者の数が増
加するに伴い、それらの参加者間のアクセスの調整は複
雑な作業になる。この作業の解決策は、まさに共有媒体
へのアクセスを獲得しようとする瞬間に対話する参加者
の全体的独立の前提条件の下に考えなければならない。

調整の問題と深くからみあっているのは、競合の問題
である。すべての資源の完全な並列性は望まれておら
ず、不経済であるため、共有資源は必然的に関係プロセ
スのボトルネックとなる。１つの共有媒体に２者以上の
ユーザまたは参加者が同時にアクセスする場合、優先順
位に関する決定を行う必要がある。より高度の並列性ま
たは冗長性によって解決されない場合、従来の技術では
基本的に２つの機構を使用して競合の問題に対処してき
た。これらの機構は、統計的性質または優先順位設定の
使用のいずれかによって特徴づけられる。統計的手法
は、様々な仕組み（FIFO型バッファ、CSMA/CD型データ
通信プロトコルなど）で適用されて成功しているが、よ
り高度の決定論によるアクセス方式に向かう傾向が目立
っている。このような傾向の例として、将来の公衆広帯
域統合サービス・ディジタル網（BISDN）に向けての取
り組みがある。統合サービス網は、音声、ビデオ、およ
びデータの伝送に等しく対応するように設計されてい
る。遅延の影響を受けやすい場合もあればバースト性の
高い場合もあるこれらの様々なタイプの情報は、異なる
処理方法を必要とする。したがって競合問題の自然な解
決策は、さまざまなタイプの情報を優先度カテゴリまた
はそれに相当するものに分類することである。このよう
にして分類された情報の所望の処理方法をトリガする
「純粋な」情報（ペイロード）に、分類タグを付ける。
たとえば、ビデオおよびオーディオ・アプリケーション
を高優先順位を有するものとして分類し、ファイル転送
と電子メールを低優先順位のトラヒックとして分類する
こともできる。

前述の問題に戻る前に、高速データ交換が適用される
主要な分野であるという理由から遠隔通信の分野につい
て簡単に概説する。この分野における発達は、あらゆる
関連分野の最新のモデルとみなされる。

上記ですでに述べたように、BISDNのような新しい高
度遠隔通信サービスは、データ、音声、およびビデオの
伝送を含むマルチメディア・アプリケーションへの対応
を促している。これらのサービスは帯域の高度な柔軟性
を必要とし、これはパケット交換によって最もよく得ら
れることがわかっている。その理由は、パケット交換が
帯域を動的かつ瞬時に割り振ることができ、多重比によ
って資源を効率的に使用することができるためである。
特に、セルと呼ばれるデータの短い固定長パケットに基
づく非同期転送モード（ATM）が、将来の公衆BISDNの統
合交換伝送標準になると予想される。可変長パケットを
基礎にしたATMと高速パケット交換（FPS）の両方の構内
網が検討されている。所望のデータ転送レートは、100M
ビット／秒の限界を超えて最高1Gビット／秒まで上げ
る。現在、2.4Gビット／秒の最大転送レートが計画され
ている。このような転送レートは、SONET/SDHなどの光
通信標準の発達の影響を受けている。

超大規模集積（VLSI）マイクロチップ技術の進歩によ
って、このような将来の転送レートに対応可能な高速交
換の開発が可能になっている。主としてソフトウェア処
理に基づく従来のパケット交換とは異なり、これらの新
しい高度パケット交換はハードウェアを基礎としてい
る。これらのパケット交換の競合解決のためのトポロジ
とバッファ構成は、高度のモジュール性を用いる。ルー
ティング機能は一般に、セルフルーティングと呼ばれる
ハードウェア・レベルの分散方式で行われる。高度パケ
ット交換構造については、以下の資料から知られる。

米国特許第4679190号では、同期データ交換と非同期
データ交換の切換えを行うと同時に、最高の割当て可能
優先順位を持つデータ交換が交換網のどの段でも抑止さ
れないように保証することが可能な、多段相互接続網
（MIN）について述べられている。音声情報を搬送する
パケットには他のデータより高い優先順位が与えられ
る。交換構造のどの段階で競合が発生しても、より優先
順位の高いパケットを通過させることによってその競合
を解決する。優先順位の低いデータは抑止され、入力ア
ダプタ（ポート）のデータ・バッファに残される。バッ
ファ空間、すなわちメモリを備えることは、一般に入力
キューイングと呼ばれる。同じ優先順位を持つパケット
の衝突は、アービトレーション部によって所定の規則ま
たはラウンド・ロビン方式に従って処理される。

上記の従来の入力キューイングは、パフォーマンスの
観点から見て出力キューイングよりもスループットが劣
る。米国特許第5008878号で述べられている交換では、
このパフォーマンスの優位を利用する。基本交換機構成
は、入力ポートを介して交換構造に接続された入力アダ
プタから成る。交換構造の出力ポートは、出力アダプタ
にリンクされている。入力アダプタでは、パケット交換
インタフェースおよび回線交換インタフェースからの様
々なサービス（コンピュータ、電話、およびその他の送
信源からのトラヒック）が集められ、所望の出力ポー
ト、ペイロード長、およびペイロードの優先順位クラス
を指定するルーティング情報が入ったパケット・ヘッダ
を持つ一様なミニパケットに変換される。デパッケージ
ングは出力ポートで行われる。交換構造自体は、高速セ
ルフルーティング相互接続網である。各出力ポートに
は、１対のFIFOキューイング・バッファが割り当てられ
る。各対のうちの第１のバッファでは、所与のサイクル
・タイム内にディスパッチしなければならない高優先順
位トラヒック、すなわち回線交換トラヒックまたは必須
帯域トラヒックがキューイングされ、第２のバッファは
低優先順位または非予約帯域トラヒックを扱う。優先順
位方式は、高優先順位キューを先に処理することによっ
て実施される。このキューで待機しているパケットがな
い場合にのみ、第２のバッファを出力ポートに接続する
ことができる。

1990年３月発行のIBM Technical Disclosure Bulleti
n,vol.32,no.10Bの176〜177ページの「Packet Switchin
g Module」と題する論文と、欧州特許出願第0492025号
および第0429026号では、共通出力記憶域から単一の出
力ポートにバッファ空間を動的に割り振る方法が述べら
れており、特に、バースト性のデータ・トラヒックの場
合、出力ポート競合がさらに緩和される。しかし、複数
出力ポートを持つ出力FIFOキューは実現が困難であり、
VLSIチップ上に実装する場合に大きさが制限され、従来
の入力キューイング概念の単一ポートFIFOバッファと比
較して費用がかかる。この出力バッファは、出力ポート
競合を解決するように、すなわち同じ交換サイクル中に
複数の入力からセルを受け付けることができるように、
複数の入力を持つか、またはより高速で動作しなければ
ならない。

I.イリアディス（Iliadis）およびW.デンツェル（Den
zel）による「Performance of Packet Switches with I
nput and Output Queueing」、IEEE International Con
ference on Communication、1990年４月16〜19日、316.
3.1〜７ページ、I.イリアディスによる「Head of Line
Arbitration of Packet Switches with Combined Input
and Output Queueing」、Intern.Journal of Digital
and Analog Comm.Syst.,Vol.4（1991）、181〜190ペー
ジ、またはH.F.バドラン（Badran）およびH.T.ムフタ
（Mouftah）による「Head of LIne Arbitration in ATM
Switches with Input−Output Buffering and Backpre
ssure Control」、Proc.of GLOBECOM'91、1991年12月２
〜５日アリゾナ州フェニックス、11.4.1〜５ページの例
のように、他のいくつかの情報源から、多少効率が高い
がより高価な出力メモリを、それよりかなり安価だが効
率の低い入力側の大量のメモリと組み合わせることによ
って、高いパフォーマンス／コスト比の実現を目指す入
力キューイングと出力キューイングの組合せが提案され
ている。バッファのサイズは主として所望のデータ・パ
ケット損失率によっ決まる。入出力キューイングの組合
せの概念は、各段にその段独自の（入力）キューを備え
たバッファ付き多段構造に拡大することができる。

出力バッファのオーバーフローは、出力バッファが十
分なスペースを提供することができない期間中は着信パ
ケットの伝送を抑止するバックプレッシャ機構によって
処理する。これは、パケットを入力線の終端で待機させ
るバックプレッシャ信号によって実施される。

２つ以上のクラスのトラヒックが発生すると、交換機
設計にいくつかの問題が生じる。各入力キュー内または
バッファ内でパケットが必ずパケットのクラスに従って
それぞれ配列されるようにする機構が必要である。同じ
ことが出力バッファにもあてはまる。各ポートのバッフ
ァ管理機構が少なくとも原則としては着信パケットまた
は格納パケットの状況に関する全情報を持っているた
め、この各キュー内の優先順位ソートは容易に実現され
る。ソート・アルゴリズムについては、たとえば米国特
許第4942569号で述べられている。

しかし、優先トラヒックが、通常は独立し、さらに互
いに遮蔽されているとみなされて設計されている複数ま
たはすべての入力に分散している場合は、各入力間の調
整の実施は厄介でコストがかかり、パフォーマンスが低
下する。コスト上の理由からそれ以上の検討は進められ
ないが理想的な解決策は、交換機（２プレーン交換機）
内のトラヒックのクラスごとに別々の出力キューを設け
ることであろう。

したがって、本発明の目的は、特に100Mビット／秒を
超えるデータ転送レートの、様々なクラスまたは優先順
位の情報トラヒックのための交換方法および装置を提供
することである。具体的には、本発明は、単入力線の間
の調整を行わない、前記トラヒックのための交換方法お
よび装置を提供することである。超高速の交換機を考慮
して、本発明はさらに最小限のハードウェア構成要素に
よる実施を目的とする。

［発明の概要］上記の目的は、入力キューを備えた入力ポートと出力
キューを備えた出力ポートとを有し、前記出力キューの
オーバーフロー状態を検出する制御手段と、オーバーフ
ロー状態の場合に所定の期間Ｔの間、少なくとも１つの
クラスのトラヒックの伝送を抑止する中断手段とを含
む、通信交換機によって達せられる。

本発明の基本思想は、同じ出力ポートに送られるより
高い優先順位を有するデータを優先させて優先順位のよ
り低いデータの伝送を中断することである。この中断
は、出力バッファまたはメモリからのバックプレッシャ
によって、すなわち着信パケットが拒否されると、トリ
ガされ、所定の期間Ｔのあいだ継続する。Ｔの最適値
は、主に入出力バッファ・サイズ、全トラヒック内の様
々なトラヒック・クラスの割合などのシステムパラメー
タによって異なる。Ｔの上限は、出力バッファが確実に
空にされる時間によって決められる。時間Ｔの後で周期
的に信号を出す装置を、たとえば最大でＴの値に対応す
る数のスイッチ・サイクルをすべて記録するインクリメ
ンタによって、またはそのような数に初期設定され、ゼ
ロに達すると信号を出すデクリメンタによって、容易に
実現することができる。

通信網における高速交換機内で使用することができる
ように、本発明の機構の複雑さは最小限に抑えられる。
本発明の機構は、既存の交換機の設計を大幅に変更する
ことなく実現することができる。また、１つの出力ポー
ト専用の出力バッファがいっぱいになった後のパケット
の損失を防止する、既存のパックプレッシャ方式を利用
するので有利である。さらに、交換機アーキテクチャ内
にトラヒックの１つのクラスだけを専門に処理する特別
な段階を設けず、異なる入力線間でデータを交換する必
要がない。

本発明の好ましい実施例では、中断手段は通常のバッ
クプレッシャ機構に接続される。この通常のバックプレ
ッシャ機構は、未占有メモリ空間がないために出力キュ
ーでパケットを受け取ることができない場合に起動され
る。その場合、送信されたパケットを受信することがで
きないことを示す信号が送信入力側に返される。入力側
がただちに、すなわち次のスイッチ・サイクルで同じパ
ケットの送信を再試行することができる周知のバックプ
レッシャ機構とは異なり、この中断手段は、優先順位の
低いパケットについてこの再試行を期間Ｔの間、遅延さ
せる。したがって、期間Ｔは、入力線ごとに独立して、
低優先順位のパケットを送信する試行の失敗によってト
リガされる。

本発明の別の態様では、バックプレッシャ信号は低優
先順位パケットの送信の試行に失敗した入力ポートに装
着された中断手段をトリガするだけではなく、それと同
時に中断手段にすべての入力線からの低優先順位トラヒ
ックの送信を抑止させる。

この好ましい実施例は、出力バッファの一部を高優先
順位パケットのみの専用とする必要なしに、高優先順位
トラヒックを優先させる。しかし、バッファの一部を高
優先順位パケット専用に予約することができるバッファ
・サイズの場合は、出力バッファがその予約部分までい
っぱいになった場合に起動される低優先順位トラヒック
用のバックプレッシャ機構を適用することができる。そ
の場合、この低優先順位バックプレッシャ機構からの信
号は、通常のバックプレッシャの場合について前述した
ように扱うことができる。

この新規機構は、２種類以上のクラスのトラヒックに
容易に拡大することができる。多数のトラヒック・クラ
スを含む好ましい実施例では、クラス（添え字ｉで示
す）ごとに異なる期間Ｔ（ｉ）を決定する。値Ｔ（ｉ）
は、クラスの優先順位が下がるに従って大きくなる。本
発明の別の態様では、異なるトラフィック・クラスにつ
いて異なるオーバーフロー条件を設定する。したがっ
て、最高の優先順位クラスだけが出力ポートのバッファ
・メモリ全体にアクセスすることができる。それに対し
て、優先順位がより低いクラスのデータ・パケットは、
バッファ・メモリの一部しか占有することができない。
この部分空間のサイズは、トラヒック・クラスに応じて
制限することができる。そのクラスのパケットが、より
高いクラスのために事実上予約されているバッファ空間
を占有しようと試行する（そして失敗する）と、そのト
ラヒック・クラスについてオーバーフロー状態が通知さ
れる。

本発明の他の実施例では、各出力ポートの出力バッフ
ァまたはキューは、すべての出力ポートによって共有さ
れる共通記憶域の一部である。各出力（論理キュー）の
共有は、前述の出力キューとの類比によって説明するこ
とができる。単一の論理キューのサイズの他に、すべて
の論理キューによって占有される共通記憶域のサイズを
監視して、さらに他のオーバーフロー条件を設けること
ができる。

以下では、その詳細が当業者に周知であって、たとえ
ば上記で引用した特許で説明されている、いくつかのタ
イプの既存のATM交換機に関して本発明の実施例を示
す。本発明または説明する実施例あるいはその組合せ
を、他の周知および将来の交換機設計に合わせて改変す
ることは、当業者にとって簡単な作業であることが明ら
かになろう。

［図面の簡単な説明］以下に、本発明について以下の図面を参照しながら詳
細に説明する。

第1A図は、新規機構とともに（専用の）入力キューお
よび出力キューを有する交換機の基本構造を示す図であ
る。

第1B図は、新規機構とともに入力キューおよび共有出
力バッファを有する交換機の基本構造を示す図である。

第1C図は、トラヒックの３種類のクラスと２種類のオ
ーバーフロー状態を有する本発明の実施例を示す図であ
る。

第2A図は、２つの通信クラスの場合の新規委の機構の
機能原理を示す図である。

第2B図は、３つのトラヒック・クラスの場合の新規機
構の機能原理を示す図である。

［本発明の実施態様］第１図に示す基本nxn交換機構造体は、それぞれが着
信データ・パケットを格納する入力バッファ1a〜1nを有
するｎ個の入力ポートまたはアダプタを含む。バッファ
・メモリ内の単一の記憶単位をセル２と呼ぶ。この定義
は、ATMトラヒックにおけるデータ・パケットの名称に
関して選定されたものである。交換機構造自体は、要求
された出力ポートに着信トラヒックを転送するリーティ
ング部を含む。パケット交換システムでは、ルーティン
グ部は通常、着信データ・パケットのヘッダ部に入って
いる情報によって駆動される非閉塞網である（セルフル
ーティング）。ルーティング部３の典型的な設計は周知
であり、本発明に関しては特に関係がない。

ｎ個の出力バッファ4a〜4nのうちの１つが、ｎ個の出
力線のそれぞれの専用になっている。各出力バッファ
は、ｎ個の入力1a〜1nからデータを受け取ることがで
き、格納されているパケットを、接続されている出力ポ
ートに配送することができる。

本発明は、交換機のこの周知の部品に、出力バッファ
4a〜4nの実際の内容をバッファの容量に関連する参照値
と比較する制御装置5a〜5nを付加する。説明する例で
は、バッファの全容量を使用し、いっぱいになった出力
バッファ４にパケットが入ろうとすると制御装置５が起
動される。各制御装置は、タイミング装置6a〜6nに接続
され、入力キュー1a〜1nのいずれからのパケット伝送で
も所与の期間Ｔの間、中断することができる。

通常の動作中には、１つの入力チャネルを介した着信
データは、着信データが必要な形式を有していない場
合、適切なサイズのパケットに分割される。パケットは
入力キュー1a〜1nに入れられる。入力キューのラインの
上限に達すると、パケットはルーティング部３を介して
それらのパケットの宛先の出力ポートに転送される。出
力ポートでは、パケットが出力キュー4a〜4nの最初の未
占有セルに格納され、後で出力線に送信される。

通常、出力バッファ4a〜4nはどのような着信トラヒッ
クでも迅速に吸収し、したがっていくつかの入力ポート
からの競合をある程度まで遮断することなく許容する。
しかし、この許容範囲が尽きてオーバーフロー状態が発
生した場合は、新規機構が起動される。すなわち、低優
先順位パケットの転送の試行の失敗を検出し、当該の出
力キューに割り当てられた制御装置５が、発信側の入力
のタイミング装置６に信号を送る。タイミング装置内の
レジスタが、スイッチ・サイクル数単位の所定の数Ｔ、
すなわち１つのパケットが交換機構造を通って送られる
時間を表す整数に設定される。この時間は、すべてのス
イッチ要素のための自然時間尺度を形成する。この整数
はスイッチ・サイクル毎に１ずつ減少する。タイミング
装置は、Ｔスイッチ・サイクルの間、低優先順位パケッ
トの送信の試行を中断する。この期間の後、試行は再び
許可される。待機パケットの送信がもう一度失敗した場
合は、この機構が再び開始される。

第1B図の交換機では、新規機構がすべての出力ポート
のための共有出力バッファまたはメモリ８と組み合わさ
れる。制御装置10が、共有メモリ内の占有セル合計数と
出力ポートｊ（ｊ＝1,・・・,n）のうちの１つの出力ポ
ート用に定められている共有メモリ内の占有セル合計数
をそれぞれ示す２つの値ｎ（ｔ）およびｑ（j,t）を監
視することによって、バッファ８を監視する。２つの出
力キュー8a、8nによって占有されたメモリが図示されて
いる。入力ポートからの送信を中断するタイミング装置
6a〜6nは、オーバーフロー状態を示す２つの条件のいず
れかによってトリガされる。この２つの条件は、ｎ
（ｔ）＞Lsとｑ（j,t）＞Lqである。説明する例の場
合、16x16の交換機、すなわち16個の入力ポートと16個
の出力ポートを有する交換機のために、限界LsおよびLq
はそれぞれ80および32に設定されている（１≦ｊ≦1
6）。合計出力バッファ・サイズは96セルに制限され、
１つの出力ポートは最大48セルを占有することができ
る。前記の条件が満たされ、しかも入力ポートが低優先
順位パケットの送信を試行した場合、制御装置10はバッ
クプレッシャ信号を出し、その信号によって送信側入力
ポートに接続されているタイミング装置がトリガされ
る。

この例の１つの変更態様では、制御装置はすべてのタ
イミング装置に対して同時に信号を出し、したがってす
べての入力ポート1a〜1nからの低優先順位パケットの送
信の試行を期間Ｔの間、阻止する。

次に第1C図を参照すると、３種類のトラヒック・クラ
スが示されている。最初の２つのクラスは、最初の例
（第1A図）のものと類似した手段を使用して処理され
る。第３のクラスには、追加の制御手段9a〜9nと追加の
タイミング手段7a〜7nが割り当てられている。この第３
のトラヒック・クラスの場合、出力バッファ4a〜4nが、
第1C図の囲まれたセルで示されている限界まで占有され
るとオーバーフロー状態が検出される。追加のタイミン
グ装置7a〜7nは第２のクラスのトラヒックを遮断するタ
イマ6a〜6nとは異なる時間に設定されている。

第1A図〜第1C図で図示されている新規機構は、各入力
ポート内に複数の（論理）キューを有する交換機構造に
合わせて調整することもできる。これらの（論理）キュ
ーはそれぞれが１つのトラヒック・クラス用に予約され
ている。したがって、パケットはそのような入力ポート
からそれぞれの優先順位に従って送信される。

典型的な解決策を第2A図および第2B図に示す。これら
の図には、２種類（第2A図）および３種類（第2B図）の
トラヒック・クラスの場合の、受信側出力ポートのバッ
ファにおけるオーバーフロー状態に依存する入力ポート
からの低クラス・トラヒック動作が示されている。

オーバーフロー状態、すなわち信号21の「YES」レベ
ルになると、期間Ｔ中に出力メモリで未占有セルが使用
可能になった場合でも、すなわちオーバーフロー状態が
その期間中に終わるか否かに関係なく、低クラス・トラ
ヒックが期間Ｔの間、遮断される（信号22の「NO」状態
によって示される）。期間Ｔの後、低クラス優先順位ト
ラヒックのパケットの送信がもう一度試行される。パケ
ットが依然として、あるいは再び、出力キューまたはバ
ッファでオーバーフロー状態になる場合、その試行はさ
らにＴ期間の間、延期される。この処置は、送信パケッ
トが受信バッファで「NO」オーバーフロー状態になるま
で繰り返される。

この状況は、２種類の期間Ｔ（１）とＴ（２）が存在
する点を除けば３クラス・トラヒックでも変わらない。
前と同様に、この新規機構はクラス０トラヒックを中断
させないが、信号24および25の指示に従ってクラス１お
よびクラス２トラヒックをそれぞれＴ（１）またはＴ
（２）の間、延期する。第2A図と同じ表記を使用して、
出力バッファのオーバーフロー状態（信号23）を示す。
両方の期間Ｔ（１）、Ｔ（２）は、同じオーバーフロー
信号23によってトリガされる。パケット伝送の推測統計
学的な性質により、短い期間Ｔ（１）の方が、クラス１
トラヒックがクラス２トラヒックと比較して送信される
確率が高くなる。言い換えると、交換機は平均して、低
クラス・トラヒックに対して、より短い期間のあいだ開
いているということを意味する。

パフォーマンス試験では、Ｔの適切な選定値を使用す
るとこの機構は低優先順位トラヒックのスループットに
はほとんど影響を与えないと同時に、より高いクラスの
トラヒックについて所望のサービス品質（QOS）を保証
することがわかる。これは恐らく、出力キューが少なく
とも部分的に満たされた状態でのみ使用される緊急装置
としてのこの提案機構の性質を反映した驚くべき結果で
あろう。入力ポートでそれぞれサイズＶおよびＱを有す
る２つの異なるキューに分かれている２クラス・トラヒ
ックの場合について、この新規機構のパフォーマンスを
示す。しかし、いくつかの低優先順位パケットから成る
フレームの送信中に、高優先順位パケットが着信した場
合、その高優先順位パケットはそのフレームの送信が完
了するまで待たなければならない。予約帯域および非予
約帯域のトラヒック密度をそれぞれρ_L（RS）およびρ_L
（NR）で表す。両方の値を最大トラヒック密度で正規化
する。値ρ_L（RS）＝0.8とρ_L（NR）＝0.08および1.00
を仮定して、低密度の非予約トラヒックと過剰（不正動
作）非予約トラヒックの場合をシミュレートする。交換
機の速度は入力線の速度より52％速い。両方のクラスの
パケットの許容損失確率を10^-6に設定する。以下の表
に、様々なＴの値（スイッチ・サイクル数で測定）の場
合の両方の論理入力キューＶおよびＱの必要サイズ（10
パケットと仮定したデータ・フレームの平均長と等しい
単位で測定）を示す。値Ｔ＝０は、制御をまったく適用
しない場合、すなわち本発明の機構を備えない交換機に
対応する。

入力ポートに制御を加えないと、低密度非予約トラヒ
ックの場合、予約帯域（RS）トラヒックの必要入力キュ
ー長Ｖは52ユニットである。本新規機構を１から10まで
の範囲の期間Ｔで適用すると必要キューサイズは47ユニ
ットまで下がる。しかし、本新規機構の完全な利点は、
高密度非予約トラヒックの場合に明確になる。その場
合、必要サイズは115からほぼ半分の65に下がる。表１
の結果は、１から10までの範囲の期間Ｔを選定すべきで
あることを示している。

Claims

(57)【特許請求の範囲】

【請求項１】データの着信パケットを格納する入力キュ
ー（1a〜1n）を備える入力ポートと、前記データの送出
パケットを格納する出力キュー（4a〜4n、８）を備える
出力ポートと、前記出力キュー（4a〜4n、８）のうちの
少なくとも１つにおける前記データ・パケットのオーバ
ーフロー状態を検出する制御手段（5a〜5n、9a〜9n、1
0）と、前記検出されたオーバーフロー状態の場合に前
記入力キュー（1a〜1n）の少なくとも１つが前記データ
・パケットを前記オーバーフロー状態が検出された前記
出力キュー（4a〜4n、８）に送信するのを阻止するバッ
クプレッシャ手段とを含む、複数のｎ個の異なるクラス
のデータ・トラヒックのための交換機であって、前記交
換機は、所定の期間（Ｔ）の間、入力キュー（1a〜1n）
がデータ・トラヒックの前記クラスのうちの少なくとも
１つのクラスを前記オーバーフロー状態が検出された前
記出力キュー（4a〜4n、８）に送信する試行を中断する
タイミング手段（6a〜6n、7a〜7n）をさらに含み、前記
タイミング手段（6a〜6n、7a〜7n）は前記検出されたオ
ーバーフロー状態の場合に前記制御手段（5a〜5n、9a〜
9n、10）によって出されるトリガ信号によってトリガさ
れることを特徴とする交換機。
【請求項２】データ・トラヒックの前記ｎ個のクラスの
伝送がｎ個の所定の期間Ｔ（ｉ），（ｉ＝1,・・・,
n）、の間、前記タイミング手段（6a〜6n、7a〜7n）に
よって中断され、前記期間Ｔ（ｉ）のそれぞれがデータ
・トラヒックの前記クラスのうちの１つに割り当てられ
ていることを特徴とする、請求項１に記載の交換機。
【請求項３】前記オーバーフロー状態のそれぞれが、異
なるしきい値を有し、データ・トラヒックの前記異なる
クラスのうちの少なくとも１つに割り当てられており、
前記制御手段（5a〜5n、9a〜9n）が複数の前記オーバー
フロー状態を検出するように設計されていることを特徴
とする、請求項２に記載の交換機。
【請求項４】タイミング手段（6a〜6n、7a〜7n）が入力
ポート（1a〜1n）のそれぞれに割り当てられていること
を特徴とする、請求項１に記載の交換機。
【請求項５】タイミング手段（6a〜6n、7a〜7n）が、デ
ィクリメンタまたはインクリメンタおよび前記期間
（Ｔ）に対応するスイッチ・サイクル数の後でディクリ
メンタまたはインクリメンタをリセットする手段とを含
むことを特徴とする、請求項１に記載の交換機。
【請求項６】すべての前記出力キュー（8a〜8n）が格納
される共通記憶バッファ（８）を特徴とし、前記制御手
段（10）が前記データ・パケットによって占有されてい
る前記記憶バッファ（８）の部分の実サイズ（ｎ
（ｔ））と、前記出力キュー（8a〜8n）のうちの１つに
宛てて送られる前記データ・パケットによって占有され
ている前記記憶バッファ（８）の部分のサイズ（ｑ（j,
t）），（ｊ＝1,・・・,n）、とを検出するように設計
されていることを特徴とする、請求項１に記載の交換
機。
【請求項７】前記入力ポート（1a〜1n）のそれぞれが、
データ・トラヒックのクラスに応じて前記着信データ・
パケットを事前ソートする別々の入力キュー（1a〜1n）
を有することを特徴とする、請求項１に記載の交換機。
【請求項８】データの着信パケットを格納する入力キュ
ー（1a〜1n）を備える入力ポートと、データの送出パケ
ットを格納する出力キュー（4a〜4n、８）を備える出力
ポートとを有する交換機を介してデータ・トラヒックの
複数のｎ個のクラスを伝送する方法であって、 −前記出力キュー（4a〜4n、８）のうちの少なくとも１
つの出力キュー内の前記データ・パケットのオーバーフ
ロー状態を検出するステップと、 −前記検出されたオーバーフロー状態の場合、前記入力
キュー（1a〜1n）のうちの少なくとも１つの出力キュー
において、前記オーバーフロー状態が検出された前記出
力キュー（4a〜4n、８）への前記データ・パケットの送
信を阻止するステップと、 −前記オーバーフロー状態の場合、所定の期間（Ｔ）の
間、前記オーバーフロー状態が検出された前記出力キュ
ー（4a〜4n、８）へのデータ・トラヒックの前記クラス
のうちの少なくとも１つのクラスの送信の試行を中断す
るステップとを含む方法。
【請求項９】データ・トラヒックの前記ｎ個のクラスの
それぞれに所定の期間Ｔ（ｉ），（ｉ＝1,・・・,n）が
割り当てられることを特徴とする、請求項８に記載の交
換方法。
【請求項１０】トラヒックの前記異なるクラスのうちの
少なくとも１つのクラスに、異なるしきい値を有する複
数の前記オーバーフロー状態が割り当てられることを特
徴とする、請求項９に記載の交換方法。
【請求項１１】入力ポート（1a〜1n）のそれぞれについ
て所定期間（Ｔ）が個別にトリガされることを特徴とす
る、請求項８に記載の交換方法。
【請求項１２】前記受信側出力キュー（4a〜4n、８）に
おいて前記オーバーフロー状態が検出されている間、デ
ータ・パケットの送信を試行することによって、前記入
力ポート（1a〜1n）のそれぞれについて期間（Ｔ）が個
別にトリガされることを特徴とする、請求項11に記載の
交換方法。
【請求項１３】前記入力ポート（1a〜1n）のすべてにつ
いて期間（Ｔ）が同時にトリガされることを特徴とす
る、請求項８に記載の交換方法。
【請求項１４】受信側出力キュー（4a〜4n、８）におい
てオーバーフロー状態が検出されている間、前記入力ポ
ート（1a〜1n）のうちの１つがデータ・パケットの送信
を試行することによって、前記期間（Ｔ）が前記入力ポ
ート（1a〜1n）のすべてについて同時にトリガされるこ
とを特徴とする、請求項13に記載の交換方法。