JPH0637805A - パケットセルスケジューリング装置 - Google Patents
パケットセルスケジューリング装置Info
- Publication number
- JPH0637805A JPH0637805A JP12485193A JP12485193A JPH0637805A JP H0637805 A JPH0637805 A JP H0637805A JP 12485193 A JP12485193 A JP 12485193A JP 12485193 A JP12485193 A JP 12485193A JP H0637805 A JPH0637805 A JP H0637805A
- Authority
- JP
- Japan
- Prior art keywords
- transmission time
- input
- output
- cell
- memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/50—Overload detection or protection within a single switching element
- H04L49/505—Corrective measures
- H04L49/508—Head of Line Blocking Avoidance
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/25—Routing or path finding in a switch fabric
- H04L49/253—Routing or path finding in a switch fabric using establishment or release of connections between ports
- H04L49/254—Centralised controller, i.e. arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3018—Input queuing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q11/00—Selecting arrangements for multiplex systems
- H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
- H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
- H04Q11/0478—Provisions for broadband connections
-
- B—PERFORMING OPERATIONS; TRANSPORTING
- B06—GENERATING OR TRANSMITTING MECHANICAL VIBRATIONS IN GENERAL
- B06B—METHODS OR APPARATUS FOR GENERATING OR TRANSMITTING MECHANICAL VIBRATIONS OF INFRASONIC, SONIC, OR ULTRASONIC FREQUENCY, e.g. FOR PERFORMING MECHANICAL WORK IN GENERAL
- B06B2201/00—Indexing scheme associated with B06B1/0207 for details covered by B06B1/0207 but not provided for in any of its subgroups
- B06B2201/50—Application to a particular transducer type
- B06B2201/55—Piezoelectric transducer
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5679—Arbitration or scheduling
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
- Exchange Systems With Centralized Control (AREA)
Abstract
(57)【要約】
【目的】 入力待ち行列パケット交換機のスループット
を改善する。 【構成】 出力ポートスケジューラを使用する入力待ち
行列パケット交換機に対して、出力スケジューラが使用
不可能な入力ポートからのセル伝送時間を再利用（再割
当）することを可能にすることによって顕著なスループ
ット改善が達成される。出力スケジューラがセル伝送時
間を入力ポートに割り当て、その入力ポートが例えばス
ケジューリング衝突のため割り当てられた伝送時間を使
用することができない場合、入力ポートは後続の要求期
間中に同一の出力ポートに対し新たな要求を行い、使用
不能伝送時間割当を出力スケジューラに返す。出力スケ
ジューラは、その出力ポートに対する後の要求に割り当
てるために、その返された伝送時間を別の待ち行列に格
納する。
を改善する。 【構成】 出力ポートスケジューラを使用する入力待ち
行列パケット交換機に対して、出力スケジューラが使用
不可能な入力ポートからのセル伝送時間を再利用（再割
当）することを可能にすることによって顕著なスループ
ット改善が達成される。出力スケジューラがセル伝送時
間を入力ポートに割り当て、その入力ポートが例えばス
ケジューリング衝突のため割り当てられた伝送時間を使
用することができない場合、入力ポートは後続の要求期
間中に同一の出力ポートに対し新たな要求を行い、使用
不能伝送時間割当を出力スケジューラに返す。出力スケ
ジューラは、その出力ポートに対する後の要求に割り当
てるために、その返された伝送時間を別の待ち行列に格
納する。
Description
【０００１】
【産業上の利用分野】本発明はパケット交換に関し、特
に、入力待ち行列パケット交換機のスループットを改良
するコントローラおよびスケジューラに関する。
に、入力待ち行列パケット交換機のスループットを改良
するコントローラおよびスケジューラに関する。
【０００２】
【従来の技術】パケット交換機の同一の出力ポートに対
して同時に到着するパケットセル間の競合（コンテンシ
ョン）は、一度にただ１つのパケットセルをとることに
よって解決される。その結果、残りのパケットセルのた
めに何らかの一時記憶装置が必要である。交換機の入力
側に備えられる一時記憶装置が入力待ち行列であり、交
換機の出力側のパケットセルの記憶装置が出力待ち行列
である。交換機の各入出力ラインに関して、入力待ち行
列が許容する負荷は最大５８％までであるが、出力待ち
行列は、先入れ先出し（ＦＩＦＯ）記憶装置を利用すれ
ば１００％までの負荷を許容する。
して同時に到着するパケットセル間の競合（コンテンシ
ョン）は、一度にただ１つのパケットセルをとることに
よって解決される。その結果、残りのパケットセルのた
めに何らかの一時記憶装置が必要である。交換機の入力
側に備えられる一時記憶装置が入力待ち行列であり、交
換機の出力側のパケットセルの記憶装置が出力待ち行列
である。交換機の各入出力ラインに関して、入力待ち行
列が許容する負荷は最大５８％までであるが、出力待ち
行列は、先入れ先出し（ＦＩＦＯ）記憶装置を利用すれ
ば１００％までの負荷を許容する。
【０００３】
【発明が解決しようとする課題】入力待ち行列パケット
交換機におけるこのような低い性能の理由は、ヘッドオ
ブラインブロッキングとして知られる問題に関係する。
この問題を克服するため、入力待ち行列における記憶装
置を非ＦＩＦＯまたはランダムアクセスとすることが提
案されている。さらに、同一の出力ポートに対する異な
る入力待ち行列からのパケットセルのスケジューリング
は２段階で実行され、その結果、パケットセルの非衝突
伝送が可能となる。（例えば、オバラ他、Int'l. J. of
Digital and Analog Cabled Systems、第２巻第４号２
６１〜７ページ（１９８９年）参照。）このタイプのス
ケジューリングは出力スケジューリングと呼ばれる。こ
れによって、ランダムパケットセルトラヒックモデルの
場合５８％から６５％に交換機スループットが改善され
る。
交換機におけるこのような低い性能の理由は、ヘッドオ
ブラインブロッキングとして知られる問題に関係する。
この問題を克服するため、入力待ち行列における記憶装
置を非ＦＩＦＯまたはランダムアクセスとすることが提
案されている。さらに、同一の出力ポートに対する異な
る入力待ち行列からのパケットセルのスケジューリング
は２段階で実行され、その結果、パケットセルの非衝突
伝送が可能となる。（例えば、オバラ他、Int'l. J. of
Digital and Analog Cabled Systems、第２巻第４号２
６１〜７ページ（１９８９年）参照。）このタイプのス
ケジューリングは出力スケジューリングと呼ばれる。こ
れによって、ランダムパケットセルトラヒックモデルの
場合５８％から６５％に交換機スループットが改善され
る。
【０００４】
【課題を解決するための手段】出力ポートスケジューラ
を使用する入力待ち行列パケット交換機に対して、出力
スケジューラが使用不可能な入力ポートからのセル伝送
時間を再利用（再割当）することを可能にすることによ
って顕著なスループット改善が達成される。出力スケジ
ューラがセル伝送時間を入力ポートに割り当て、その入
力ポートが例えばスケジューリング衝突のため割り当て
られた伝送時間を使用することができない場合、入力ポ
ートは後続の要求期間中に同一の出力ポートに対し新た
な要求を行い、使用不能伝送時間割当を出力スケジュー
ラに返す。出力スケジューラは、その出力ポートに対す
る後の要求に割り当てるために、その返された伝送時間
を別の待ち行列に格納する。本発明の結果、スループッ
ト性能は、ランダムセルトラヒックモデルの場合５８％
から９２％に改善される。
を使用する入力待ち行列パケット交換機に対して、出力
スケジューラが使用不可能な入力ポートからのセル伝送
時間を再利用（再割当）することを可能にすることによ
って顕著なスループット改善が達成される。出力スケジ
ューラがセル伝送時間を入力ポートに割り当て、その入
力ポートが例えばスケジューリング衝突のため割り当て
られた伝送時間を使用することができない場合、入力ポ
ートは後続の要求期間中に同一の出力ポートに対し新た
な要求を行い、使用不能伝送時間割当を出力スケジュー
ラに返す。出力スケジューラは、その出力ポートに対す
る後の要求に割り当てるために、その返された伝送時間
を別の待ち行列に格納する。本発明の結果、スループッ
ト性能は、ランダムセルトラヒックモデルの場合５８％
から９２％に改善される。
【０００５】さらに、入力ポートグループ化を使用する
ことによって、スループット改善が実現される。これ
は、特定伝送時間中のパケットセル伝送が同一のグルー
プの入力待ち行列から選択されるように、複数の入力待
ち行列がグループ化（結合）されることを必要とする。
入力グループ化の結果、ランダムパケットセルトラヒッ
クモデルの場合９５％にスループットが改善される。
ことによって、スループット改善が実現される。これ
は、特定伝送時間中のパケットセル伝送が同一のグルー
プの入力待ち行列から選択されるように、複数の入力待
ち行列がグループ化（結合）されることを必要とする。
入力グループ化の結果、ランダムパケットセルトラヒッ
クモデルの場合９５％にスループットが改善される。
【０００６】
【実施例】統合サービス網およびマルチプロセッサ相互
接続のための高性能パケット交換への動きにおいて、交
換機組織を通して多くの同時入出力パスを提供し、内部
交換パスが決定論的にではなく統計的に時間多重化され
ることを可能にするパケット交換アーキテクチャに注目
が集まっている。このようなアーキテクチャは、交換機
の各入力および出力ポートで数百Ｍｂｐｓの領域の高速
伝送の可能性を提供し、それによって、数百Ｇｂｐｓの
オーダーの全交換容量を生成する。高速交換動作は、パ
ケットをルーティングするために交換機組織によって使
用されるソースおよび宛先アドレスのようなパス情報を
含むパケットヘッダを処理するためのほぼハードウェア
ベースのパケット処理を必要とする。
接続のための高性能パケット交換への動きにおいて、交
換機組織を通して多くの同時入出力パスを提供し、内部
交換パスが決定論的にではなく統計的に時間多重化され
ることを可能にするパケット交換アーキテクチャに注目
が集まっている。このようなアーキテクチャは、交換機
の各入力および出力ポートで数百Ｍｂｐｓの領域の高速
伝送の可能性を提供し、それによって、数百Ｇｂｐｓの
オーダーの全交換容量を生成する。高速交換動作は、パ
ケットをルーティングするために交換機組織によって使
用されるソースおよび宛先アドレスのようなパス情報を
含むパケットヘッダを処理するためのほぼハードウェア
ベースのパケット処理を必要とする。
【０００７】交換速度が増大すると、パケット輻輳がさ
らに問題となり、重要となる。パケット到着はスケジュ
ーリングされない。複数のパケットが、同一の出力ポー
ト宛に異なる入力ポートに同時に到着することがある。
これらのパケットのうちの１つのみが、特定のタイムス
ロットに交換機を通過することができる。すべての他の
競合するパケットは、その特定出力ポートに後で送信す
るために待ち行列に格納されなければならない。出力ス
ケジューリングおよび非ＦＩＦＯ待ち行列へのパケット
格納は、入力待ち行列パケット交換機のこの種の輻輳問
題を効果的に処理する際に従来使用されている２つの技
術である。
らに問題となり、重要となる。パケット到着はスケジュ
ーリングされない。複数のパケットが、同一の出力ポー
ト宛に異なる入力ポートに同時に到着することがある。
これらのパケットのうちの１つのみが、特定のタイムス
ロットに交換機を通過することができる。すべての他の
競合するパケットは、その特定出力ポートに後で送信す
るために待ち行列に格納されなければならない。出力ス
ケジューリングおよび非ＦＩＦＯ待ち行列へのパケット
格納は、入力待ち行列パケット交換機のこの種の輻輳問
題を効果的に処理する際に従来使用されている２つの技
術である。
【０００８】図１に、入力待ち行列パケット交換機のブ
ロック図を示す。このアーキテクチャはＮ個の入力ポー
ト１−１〜１−Ｎ、複数のセルメモリ２−１〜２−Ｎな
らびに対応する複数の待ち行列コントロール３−１〜３
−Ｎ、コンテンションコントロール７、およびＮ個の交
換機入力ポート４−１〜４−ＮならびにＮ個の交換機出
力ポート６−１〜６−Ｎを有するＮ×Ｎ交換機５を有す
る。Ｎは１より大きい正整数である。
ロック図を示す。このアーキテクチャはＮ個の入力ポー
ト１−１〜１−Ｎ、複数のセルメモリ２−１〜２−Ｎな
らびに対応する複数の待ち行列コントロール３−１〜３
−Ｎ、コンテンションコントロール７、およびＮ個の交
換機入力ポート４−１〜４−ＮならびにＮ個の交換機出
力ポート６−１〜６−Ｎを有するＮ×Ｎ交換機５を有す
る。Ｎは１より大きい正整数である。
【０００９】図には、表示および理解の明確さを促進す
るために、第１および第Ｎ入出力ポートの要素のみを示
してある。ここでは、「パケット」、「セル」、および
「パケットセル」という用語は、所定フォーマットの情
報のブロック（例えば非同期転送モード（ＡＴＭ））を
指すために使用され、相互交換可能である。ＡＴＭフォ
ーマットでは、セルとは、標準によってヘッダ（５バイ
ト）およびペイロード（４８バイト）に分割された合計
５３バイトを有すると定義された固定長パケットを指
す。同じく、「タイムスロット」および「伝送時間」と
いう用語はここでは単一のパケットにわたる時間間隔を
一般的に意味するように使用され、相互交換可能であ
る。
るために、第１および第Ｎ入出力ポートの要素のみを示
してある。ここでは、「パケット」、「セル」、および
「パケットセル」という用語は、所定フォーマットの情
報のブロック（例えば非同期転送モード（ＡＴＭ））を
指すために使用され、相互交換可能である。ＡＴＭフォ
ーマットでは、セルとは、標準によってヘッダ（５バイ
ト）およびペイロード（４８バイト）に分割された合計
５３バイトを有すると定義された固定長パケットを指
す。同じく、「タイムスロット」および「伝送時間」と
いう用語はここでは単一のパケットにわたる時間間隔を
一般的に意味するように使用され、相互交換可能であ
る。
【００１０】Ｎ×Ｎ交換機５を実現するために多くのタ
イプの交換機が考えられる。通常、交換機入力ポートと
交換機出力ポートの間の相互接続能力を実現するため
に、空間分割交換機が使用される。空間分割交換機とと
もに時分割多重化を使用することにより、タイムスロッ
ト空間分割交換機が実現される。対称（例えばＮ×Ｎ）
および非対称（例えばＮ×Ｍ）の両方の交換機アーキテ
クチャが考えられる。
イプの交換機が考えられる。通常、交換機入力ポートと
交換機出力ポートの間の相互接続能力を実現するため
に、空間分割交換機が使用される。空間分割交換機とと
もに時分割多重化を使用することにより、タイムスロッ
ト空間分割交換機が実現される。対称（例えばＮ×Ｎ）
および非対称（例えばＮ×Ｍ）の両方の交換機アーキテ
クチャが考えられる。
【００１１】また、ブロック化および非ブロック化アー
キテクチャが考えられるが、後者は前者より非常に高い
スループット効果を有する。最後に、自己ルーティング
交換機が交換機５として使用されることが考えられる。
さまざまな自己ルーティング交換機が従来周知であり、
大容量相互接続能力を達成する際に使用される。ここで
説明する実験からの特定の例では、交換機５はＮ×Ｎ、
非ブロック化、自己ルーティング、タイムスロット、空
間分割交換機を有する。
キテクチャが考えられるが、後者は前者より非常に高い
スループット効果を有する。最後に、自己ルーティング
交換機が交換機５として使用されることが考えられる。
さまざまな自己ルーティング交換機が従来周知であり、
大容量相互接続能力を達成する際に使用される。ここで
説明する実験からの特定の例では、交換機５はＮ×Ｎ、
非ブロック化、自己ルーティング、タイムスロット、空
間分割交換機を有する。
【００１２】セルメモリ２−１は、入力ポート１−１と
交換機入力ポート４−１の間に配置される。セルメモリ
２−１は、入力ポート１−１で受信されるパケットを格
納するための十分な容量を有するランダムアクセスメモ
リとして実現される。パケットは、待ち行列コントロー
ル３−１の制御下でセルメモリ２−１に格納される。図
１に示すように、待ち行列コントロール３−１は、受信
したパケットまたはパケットヘッダなどのその重要部分
に対応する。また、パケットは、待ち行列コントロール
３−１の制御下で適当な伝送時間にセルメモリ２−１か
ら取り出される。セルメモリ２−１に格納されたパケッ
トの伝送時間は、リード８−１による要求および調停手
順に従って待ち行列コントロール３−１とコンテンショ
ンコントロール７の間で交渉される。
交換機入力ポート４−１の間に配置される。セルメモリ
２−１は、入力ポート１−１で受信されるパケットを格
納するための十分な容量を有するランダムアクセスメモ
リとして実現される。パケットは、待ち行列コントロー
ル３−１の制御下でセルメモリ２−１に格納される。図
１に示すように、待ち行列コントロール３−１は、受信
したパケットまたはパケットヘッダなどのその重要部分
に対応する。また、パケットは、待ち行列コントロール
３−１の制御下で適当な伝送時間にセルメモリ２−１か
ら取り出される。セルメモリ２−１に格納されたパケッ
トの伝送時間は、リード８−１による要求および調停手
順に従って待ち行列コントロール３−１とコンテンショ
ンコントロール７の間で交渉される。
【００１３】コンテンションコントロールは、パケット
セルの伝送時間をスケジューリングするために、全交換
機組織に対する集中要素において実行される。適当な伝
送時間に、自己ルーティング空間交換機５は交換機入力
ポート４からセルを受信し、セルに含まれる物理ルーテ
ィング情報に基づいて自己ルーティングコントロールを
使用してそのセルを適当な交換機出力ポートにルーティ
ングする。
セルの伝送時間をスケジューリングするために、全交換
機組織に対する集中要素において実行される。適当な伝
送時間に、自己ルーティング空間交換機５は交換機入力
ポート４からセルを受信し、セルに含まれる物理ルーテ
ィング情報に基づいて自己ルーティングコントロールを
使用してそのセルを適当な交換機出力ポートにルーティ
ングする。
【００１４】コンテンションコントロール７は、２個の
入力セルが同じ伝送時間に同一の交換機出力ポートに割
り当てられないように、２段階スケジューリング方式に
よって出力スケジューリングを実行する。２段階とは、
要求段階および調停段階である。上掲のオバラ他による
論文には、２段階スケジューリングの詳細な説明があ
る。要求段階で、各待ち行列コントロール３は、伝送時
間の割当を必要とする特定の交換機出力ポートを宛先と
するセルに関してコンテンションコントロール７に通知
する。
入力セルが同じ伝送時間に同一の交換機出力ポートに割
り当てられないように、２段階スケジューリング方式に
よって出力スケジューリングを実行する。２段階とは、
要求段階および調停段階である。上掲のオバラ他による
論文には、２段階スケジューリングの詳細な説明があ
る。要求段階で、各待ち行列コントロール３は、伝送時
間の割当を必要とする特定の交換機出力ポートを宛先と
するセルに関してコンテンションコントロール７に通知
する。
【００１５】調停段階で、コンテンションコントロール
７は、割当可能な次の利用可能伝送タイムスロットを決
定するために、特定交換機出力ポートに対する内部スケ
ジューリングテーブルをチェックする。次に、利用可能
な伝送時間が要求中の待ち行列コントロールを通じてセ
ルに割り当てられる。待ち行列コントロールでは、割り
当てられた時間が他のセルによって予約されているか否
かをチェックする必要がある。その伝送時間が既に他の
セルによって予約されている場合、その待ち行列コント
ロールによるセルは、スケジューリングの次の周期で伝
送時間を要求するために復帰する。
７は、割当可能な次の利用可能伝送タイムスロットを決
定するために、特定交換機出力ポートに対する内部スケ
ジューリングテーブルをチェックする。次に、利用可能
な伝送時間が要求中の待ち行列コントロールを通じてセ
ルに割り当てられる。待ち行列コントロールでは、割り
当てられた時間が他のセルによって予約されているか否
かをチェックする必要がある。その伝送時間が既に他の
セルによって予約されている場合、その待ち行列コント
ロールによるセルは、スケジューリングの次の周期で伝
送時間を要求するために復帰する。
【００１６】図２に、セルメモリおよび待ち行列コント
ロールの詳細なブロック図を示す。セルメモリ２は、ポ
ート１のパケットセル入力を格納するのに十分な容量を
有するランダムアクセスメモリとして示されている。セ
ルメモリ２の出力は、交換入力ポート４を通じて与えら
れる。待ち行列コントロール３は、ＶＰＩテーブル３
１、メモリ３２、アドレス制御メモリ３３、および入力
コントローラ３４を有する。
ロールの詳細なブロック図を示す。セルメモリ２は、ポ
ート１のパケットセル入力を格納するのに十分な容量を
有するランダムアクセスメモリとして示されている。セ
ルメモリ２の出力は、交換入力ポート４を通じて与えら
れる。待ち行列コントロール３は、ＶＰＩテーブル３
１、メモリ３２、アドレス制御メモリ３３、および入力
コントローラ３４を有する。
【００１７】ＶＰＩテーブル３１は、セルアドレス変換
を実行し、各セルの物理ルーティング情報を与える。Ｖ
ＰＩテーブル３１は、ＡＴＭ標準に従って使用される仮
想パス識別子のリストを格納している。仮想パス識別子
はＡＴＭセルのヘッダ部分に位置し、リード３７を通じ
てＶＰＩテーブル３１に送られる。ＶＰＩテーブル３１
は、受信した仮想パス識別子に応答して、セル宛先をリ
ード３８に出力する。セル宛先は、入力コントローラ３
４に、特定のセルがいずれの交換機出力ポートへルーテ
ィングされるかを伝える。
を実行し、各セルの物理ルーティング情報を与える。Ｖ
ＰＩテーブル３１は、ＡＴＭ標準に従って使用される仮
想パス識別子のリストを格納している。仮想パス識別子
はＡＴＭセルのヘッダ部分に位置し、リード３７を通じ
てＶＰＩテーブル３１に送られる。ＶＰＩテーブル３１
は、受信した仮想パス識別子に応答して、セル宛先をリ
ード３８に出力する。セル宛先は、入力コントローラ３
４に、特定のセルがいずれの交換機出力ポートへルーテ
ィングされるかを伝える。
【００１８】メモリ３２は、セルメモリ２内のすべての
空きメモリ位置のリストを保持するランダムアクセスメ
モリである。伝送時間が入力コントローラ３４によって
受信されると、セルがセルメモリ２内で格納される位置
とともにアドレス制御メモリ３３に格納するために、リ
ード３９に出力される。アドレス制御メモリは、コンテ
ンションコントロール内の出力ポートスケジューラから
のセル伝送時間割当のリストを保持する。
空きメモリ位置のリストを保持するランダムアクセスメ
モリである。伝送時間が入力コントローラ３４によって
受信されると、セルがセルメモリ２内で格納される位置
とともにアドレス制御メモリ３３に格納するために、リ
ード３９に出力される。アドレス制御メモリは、コンテ
ンションコントロール内の出力ポートスケジューラから
のセル伝送時間割当のリストを保持する。
【００１９】メモリ３３は、適当な読み出しアドレスが
リード３６によってセルメモリ２に供給され、それによ
ってセルメモリ２の内容が割り当てられた伝送時間に読
み出されてリード４に出力されるように、シーケンシャ
ル（順次）に読み出される。実施例では、アドレス制御
メモリ３３内の位置は、スケジューリングされた（割り
当てられた）伝送時間を指す。さまざまなメモリに対す
る読み出し／書き込みおよびクリア制御信号は図では省
略されているが、これは当業者には明らかである。
リード３６によってセルメモリ２に供給され、それによ
ってセルメモリ２の内容が割り当てられた伝送時間に読
み出されてリード４に出力されるように、シーケンシャ
ル（順次）に読み出される。実施例では、アドレス制御
メモリ３３内の位置は、スケジューリングされた（割り
当てられた）伝送時間を指す。さまざまなメモリに対す
る読み出し／書き込みおよびクリア制御信号は図では省
略されているが、これは当業者には明らかである。
【００２０】コンテンションコントロールの詳細を図３
に示す。コンテンションコントロール７はＮ個の独立の
出力スケジューラ７０−１〜７０−Ｎを有する。各交換
機出力ポートに対応して１個の出力スケジューラがあ
る。各出力スケジューラは、リード８−１〜８−Ｎを通
じて待ち行列コントロールからの入力を受信し、待ち行
列コントロールと交渉する。すなわち、各待ち行列コン
トロールが、各出力スケジューラと通信する。
に示す。コンテンションコントロール７はＮ個の独立の
出力スケジューラ７０−１〜７０−Ｎを有する。各交換
機出力ポートに対応して１個の出力スケジューラがあ
る。各出力スケジューラは、リード８−１〜８−Ｎを通
じて待ち行列コントロールからの入力を受信し、待ち行
列コントロールと交渉する。すなわち、各待ち行列コン
トロールが、各出力スケジューラと通信する。
【００２１】もちろん、交換機出力ポートへの到着セル
をスケジューリングするために単一の出力スケジューラ
を使用する個とも可能である。しかし、Ｎ個すべての出
力ポートに対して単一の出力スケジューラを使用するこ
とは複雑となる。注意すべきことは、独立の出力スケジ
ューラを使用することは、達成可能なスループットを約
６５％に制限することである。このスループット条件
は、交換機出力ポートが、出力スケジューラによって特
定伝送時間を割り当てられたセルが実際にその伝送時間
を使用することを仮定することによって生じる。以前の
伝送時間予約のために、入力がその交換機にそのセルを
伝送することができず、その代わりに、異なる交換機出
力ポートを宛先とするセルを伝送する場合、割り当てら
れた伝送時間はむだになる。
をスケジューリングするために単一の出力スケジューラ
を使用する個とも可能である。しかし、Ｎ個すべての出
力ポートに対して単一の出力スケジューラを使用するこ
とは複雑となる。注意すべきことは、独立の出力スケジ
ューラを使用することは、達成可能なスループットを約
６５％に制限することである。このスループット条件
は、交換機出力ポートが、出力スケジューラによって特
定伝送時間を割り当てられたセルが実際にその伝送時間
を使用することを仮定することによって生じる。以前の
伝送時間予約のために、入力がその交換機にそのセルを
伝送することができず、その代わりに、異なる交換機出
力ポートを宛先とするセルを伝送する場合、割り当てら
れた伝送時間はむだになる。
【００２２】出力ポートスケジューラを有する入力待ち
行列パケット交換機の達成可能なスループットを大きく
増大させるため、本発明によれば、出力スケジューラ
は、以前の割当（予約）のために使用不能となった伝送
時間の再利用（再割当）を可能にするように構成され
る。入力待ち行列出力スケジューリングパケット交換機
の改良されたアーキテクチャを図４および５に示す。図
４は、アドレス制御メモリのさらに詳細な図であり、図
５は出力スケジューラの例のさらに詳細な図である。
行列パケット交換機の達成可能なスループットを大きく
増大させるため、本発明によれば、出力スケジューラ
は、以前の割当（予約）のために使用不能となった伝送
時間の再利用（再割当）を可能にするように構成され
る。入力待ち行列出力スケジューリングパケット交換機
の改良されたアーキテクチャを図４および５に示す。図
４は、アドレス制御メモリのさらに詳細な図であり、図
５は出力スケジューラの例のさらに詳細な図である。
【００２３】図示のように本発明に従って改良される
（後述）と、出力スケジューラおよび待ち行列コントロ
ールは次のように動作する。出力スケジューラは、特定
の入力の待ち行列コントロールに伝送時間を割り当て
る。待ち行列コントロールは、関連するセルが、以前の
予約のためにその伝送時間には伝送できないことを認識
する。次のスケジューリング周期に、待ち行列コントロ
ールは同一のセル（同一の出力ポート）に対して新たな
要求を発し、応答に、その出力スケジューラから新たに
割り当てられた伝送時間を受信する。
（後述）と、出力スケジューラおよび待ち行列コントロ
ールは次のように動作する。出力スケジューラは、特定
の入力の待ち行列コントロールに伝送時間を割り当て
る。待ち行列コントロールは、関連するセルが、以前の
予約のためにその伝送時間には伝送できないことを認識
する。次のスケジューリング周期に、待ち行列コントロ
ールは同一のセル（同一の出力ポート）に対して新たな
要求を発し、応答に、その出力スケジューラから新たに
割り当てられた伝送時間を受信する。
【００２４】新たな時間が受信されると、待ち行列コン
トロールは適当な出力スケジューラへ、以前に割り当て
られた伝送時間を返す。この時間は、その出力に対する
「再利用伝送タイムスロット」と呼ばれる。次に、出力
スケジューラは、簡単なラッチまたはＦＩＦＯメモリの
ような記憶装置にその再利用タイムスロットを格納す
る。再利用タイムスロットは、後続の要求への割当に使
用される。
トロールは適当な出力スケジューラへ、以前に割り当て
られた伝送時間を返す。この時間は、その出力に対する
「再利用伝送タイムスロット」と呼ばれる。次に、出力
スケジューラは、簡単なラッチまたはＦＩＦＯメモリの
ような記憶装置にその再利用タイムスロットを格納す
る。再利用タイムスロットは、後続の要求への割当に使
用される。
【００２５】すなわち、出力スケジューラが再利用タイ
ムスロットを取得し、その後タイムスロットの割当の要
求を受信した場合、その出力スケジューラは、この最後
の要求がなされたセルにこの再利用タイムスロットを割
り当てる。再利用タイムスロットは、そのタイムスロッ
トがセルに割り当てられることなく通過した場合には、
出力スケジューラのメモリから消去される。
ムスロットを取得し、その後タイムスロットの割当の要
求を受信した場合、その出力スケジューラは、この最後
の要求がなされたセルにこの再利用タイムスロットを割
り当てる。再利用タイムスロットは、そのタイムスロッ
トがセルに割り当てられることなく通過した場合には、
出力スケジューラのメモリから消去される。
【００２６】再利用タイムスロットを処理するための本
発明の原理による出力スケジューラの改良は、図５で、
独立の出力スケジューラ７０−１の実施例に示されてい
る。出力スケジューラ７０−１は、各待ち行列コントロ
ールの入力コントローラ３４−１〜３４−Ｎと交渉す
る。出力スケジューラは、コントローラ７０２、次利用
可能タイムスロット発生器７０３、および再利用タイム
スロットメモリ７０４を有する。次利用可能タイムスロ
ット発生器７０３はリード７０５によってコントローラ
７０２に接続され、再利用タイムスロットメモリ７０４
はリード７０６によってコントローラ７０２に接続され
る。
発明の原理による出力スケジューラの改良は、図５で、
独立の出力スケジューラ７０−１の実施例に示されてい
る。出力スケジューラ７０−１は、各待ち行列コントロ
ールの入力コントローラ３４−１〜３４−Ｎと交渉す
る。出力スケジューラは、コントローラ７０２、次利用
可能タイムスロット発生器７０３、および再利用タイム
スロットメモリ７０４を有する。次利用可能タイムスロ
ット発生器７０３はリード７０５によってコントローラ
７０２に接続され、再利用タイムスロットメモリ７０４
はリード７０６によってコントローラ７０２に接続され
る。
【００２７】入力コントローラ３４のうちのいずれかが
到着セルに対する伝送時間割当を要求した場合、コント
ローラ７０２はその要求を受信し、再利用タイムスロッ
トが存在するかどうか、再利用タイムスロットメモリ７
０４をチェックする。メモリ７０４が空である場合、コ
ントローラ７０２は次利用可能タイムスロット発生器７
０３を起動する。起動されると、次利用可能タイムスロ
ット発生器７０３は次利用可能タイムスロットを生成す
る。
到着セルに対する伝送時間割当を要求した場合、コント
ローラ７０２はその要求を受信し、再利用タイムスロッ
トが存在するかどうか、再利用タイムスロットメモリ７
０４をチェックする。メモリ７０４が空である場合、コ
ントローラ７０２は次利用可能タイムスロット発生器７
０３を起動する。起動されると、次利用可能タイムスロ
ット発生器７０３は次利用可能タイムスロットを生成す
る。
【００２８】実施例では、次利用可能タイムスロット発
生器７０３は簡単な計数器および加算器によって実現さ
れる。この場合、計数器はセル伝送に利用可能な次のタ
イムスロット番号を保持し、全要求数を計数し、この全
要求数を次のタイムスロット番号に加算する。再利用タ
イムスロットメモリ７０４がタイムスロットを格納して
いる場合、コントローラ７０２は、新たなタイムスロッ
トが次利用可能タイムスロット発生器７０３によって生
成される前に、その要求に、メモリ７０４からのタイム
スロットを割り当てる。
生器７０３は簡単な計数器および加算器によって実現さ
れる。この場合、計数器はセル伝送に利用可能な次のタ
イムスロット番号を保持し、全要求数を計数し、この全
要求数を次のタイムスロット番号に加算する。再利用タ
イムスロットメモリ７０４がタイムスロットを格納して
いる場合、コントローラ７０２は、新たなタイムスロッ
トが次利用可能タイムスロット発生器７０３によって生
成される前に、その要求に、メモリ７０４からのタイム
スロットを割り当てる。
【００２９】伝送時間が特定の入力に割り当てられた
後、出力スケジューラは、コントローラ７０２によっ
て、その特定入力からの再利用タイムスロットをメモリ
７０４に格納する。再利用タイムスロットがタイムスロ
ット割当の前に格納された場合、そのスケジューラへの
入力によって返された同一の伝送時間が、同一の入力に
直ちに再割当される。本発明は、この問題点を回避し、
再利用タイムスロットがそのタイムスロットを返した入
力以外の入力に割り当てられる確率を最大化する。
後、出力スケジューラは、コントローラ７０２によっ
て、その特定入力からの再利用タイムスロットをメモリ
７０４に格納する。再利用タイムスロットがタイムスロ
ット割当の前に格納された場合、そのスケジューラへの
入力によって返された同一の伝送時間が、同一の入力に
直ちに再割当される。本発明は、この問題点を回避し、
再利用タイムスロットがそのタイムスロットを返した入
力以外の入力に割り当てられる確率を最大化する。
【００３０】すなわち、これは、すべての割り当てられ
たタイムスロットが使用される確率を最大化する。この
割当方式を使用することによって、入力が、２つの連続
するスケジューリング試行において同一の伝送時間割当
を受信することは不可能となる。また、再利用タイムス
ロットは最終的に満期となり新たな伝送時間が割り当て
られるため、デッドロック状態は回避される。再利用タ
イムスロットは常に、発生器７０３の次利用可能タイム
スロットより時間的に早いことが重要である。
たタイムスロットが使用される確率を最大化する。この
割当方式を使用することによって、入力が、２つの連続
するスケジューリング試行において同一の伝送時間割当
を受信することは不可能となる。また、再利用タイムス
ロットは最終的に満期となり新たな伝送時間が割り当て
られるため、デッドロック状態は回避される。再利用タ
イムスロットは常に、発生器７０３の次利用可能タイム
スロットより時間的に早いことが重要である。
【００３１】再利用タイムスロットメモリ７０４は、ラ
ッチのような単一位置メモリ、または、ＦＩＦＯメモリ
もしくはランダムアクセスメモリのような複数位置メモ
リとして実現可能である。複数位置メモリによって、複
数の再利用タイムスロットが格納可能となる。ＦＩＦＯ
メモリ実現によって、複数の再利用タイムスロットが、
受信順に格納されることが可能となる。
ッチのような単一位置メモリ、または、ＦＩＦＯメモリ
もしくはランダムアクセスメモリのような複数位置メモ
リとして実現可能である。複数位置メモリによって、複
数の再利用タイムスロットが格納可能となる。ＦＩＦＯ
メモリ実現によって、複数の再利用タイムスロットが、
受信順に格納されることが可能となる。
【００３２】単一位置メモリでは、ただ１つの再利用タ
イムスロットのみが格納される。このタイムスロット
は、最先の再利用タイムスロット、最後の再利用タイム
スロット、または最先と最後のタイムスロットの間の任
意の１つのタイムスロットである。実験的には、出力ス
ケジューラが単一の再利用タイムスロットを格納する空
間のみを有する場合であっても、優れた性能およびスル
ープットが達成可能であることがわかっている。
イムスロットのみが格納される。このタイムスロット
は、最先の再利用タイムスロット、最後の再利用タイム
スロット、または最先と最後のタイムスロットの間の任
意の１つのタイムスロットである。実験的には、出力ス
ケジューラが単一の再利用タイムスロットを格納する空
間のみを有する場合であっても、優れた性能およびスル
ープットが達成可能であることがわかっている。
【００３３】コントローラ７０２は、Ｎ個の待ち行列コ
ントロールから要求を受け取る。スケジューラのコント
ローラは、１からＮの順で待ち行列コントロールをポー
リングする。または、この順列の始点は、毎回１または
それ以上増加されるなどとなる。要求に応答して順列を
バレルシフトすることが、スケジューリング過程にある
程度の公平さを導入するために考慮される。
ントロールから要求を受け取る。スケジューラのコント
ローラは、１からＮの順で待ち行列コントロールをポー
リングする。または、この順列の始点は、毎回１または
それ以上増加されるなどとなる。要求に応答して順列を
バレルシフトすることが、スケジューリング過程にある
程度の公平さを導入するために考慮される。
【００３４】各入力に対するセル列を保持し、タイムス
ロットの再利用を容易にするため、アドレス制御メモリ
３３が図４のように改良され、待ち行列コントロール３
の動作が下記のように改良される。アドレス制御メモリ
３３は、出力制御メモリ３３１およびセル到着順メモリ
３３２を有する。メモリ３３１および３３２はリード３
３３によって接続される。出力制御メモリ３３１は、入
力コントローラ３４から伝送時間割当を受信する。
ロットの再利用を容易にするため、アドレス制御メモリ
３３が図４のように改良され、待ち行列コントロール３
の動作が下記のように改良される。アドレス制御メモリ
３３は、出力制御メモリ３３１およびセル到着順メモリ
３３２を有する。メモリ３３１および３３２はリード３
３３によって接続される。出力制御メモリ３３１は、入
力コントローラ３４から伝送時間割当を受信する。
【００３５】出力制御メモリ３３１は、ランダムに書き
込まれ、シーケンシャルに読み出される。特定のメモリ
位置の内容は、特定の交換機出力ポートを指す。これ
は、もし存在すれば、その入力がセルを伝送するようス
ケジューリングされているポートである。出力制御メモ
リ３３１内の位置は、連続する伝送タイムスロットに対
応する。セル到着順メモリ３３２は、Ｎ個の同一のパー
ティションを有するＦＩＦＯメモリとして、または、Ｎ
個のＦＩＦＯメモリとして実現可能である。数Ｎは交換
機５の交換機出力ポートの数を指す。
込まれ、シーケンシャルに読み出される。特定のメモリ
位置の内容は、特定の交換機出力ポートを指す。これ
は、もし存在すれば、その入力がセルを伝送するようス
ケジューリングされているポートである。出力制御メモ
リ３３１内の位置は、連続する伝送タイムスロットに対
応する。セル到着順メモリ３３２は、Ｎ個の同一のパー
ティションを有するＦＩＦＯメモリとして、または、Ｎ
個のＦＩＦＯメモリとして実現可能である。数Ｎは交換
機５の交換機出力ポートの数を指す。
【００３６】各ＦＩＦＯメモリまたはパーティション
は、特定の交換機出力ポートを指す。従って、セル到着
順メモリ３３２内で、交換機出力ポートｊ（ｊ＝１，
２，．．．，Ｎ）に関するＦＩＦＯメモリとしてＦＩＦ
Ｏjという表記を使用することができる。ＦＩＦＯjは、
出力ｊを宛先とするセルを含むセルメモリアドレスの先
入れ先出しリストを含む。ＦＩＦＯjに格納された情報
は、リード３５によってメモリ３２から取得される。
は、特定の交換機出力ポートを指す。従って、セル到着
順メモリ３３２内で、交換機出力ポートｊ（ｊ＝１，
２，．．．，Ｎ）に関するＦＩＦＯメモリとしてＦＩＦ
Ｏjという表記を使用することができる。ＦＩＦＯjは、
出力ｊを宛先とするセルを含むセルメモリアドレスの先
入れ先出しリストを含む。ＦＩＦＯjに格納された情報
は、リード３５によってメモリ３２から取得される。
【００３７】動作時には、出力制御メモリ３３１はシー
ケンシャルに読み出される。特定の伝送時間に、出力制
御メモリ３３１は、関連する入力から交換機出力ポート
ｊへの伝送を示す内容のメモリ位置を読み出す。この情
報はセル到着順メモリ３３２に転送され、ＦＩＦＯjの
次に利用可能な内容が読み出される。ＦＩＦＯjの内容
はセルメモリアドレスの先入れ先出しリストであるた
め、メモリ３３２のＦＩＦＯj内の次利用可能セルメモ
リアドレスが読み出され、リード３６を通じてセルメモ
リ２へ出力される。続いて、これによって、適当なセル
が、セルメモリ２から取得され、交換機５に送られる。
ケンシャルに読み出される。特定の伝送時間に、出力制
御メモリ３３１は、関連する入力から交換機出力ポート
ｊへの伝送を示す内容のメモリ位置を読み出す。この情
報はセル到着順メモリ３３２に転送され、ＦＩＦＯjの
次に利用可能な内容が読み出される。ＦＩＦＯjの内容
はセルメモリアドレスの先入れ先出しリストであるた
め、メモリ３３２のＦＩＦＯj内の次利用可能セルメモ
リアドレスが読み出され、リード３６を通じてセルメモ
リ２へ出力される。続いて、これによって、適当なセル
が、セルメモリ２から取得され、交換機５に送られる。
【００３８】上記のように、入力コントローラ３４は、
そのセルの伝送時間割当について出力スケジューラと交
渉する。さらに、入力コントローラ３４は、その出力ス
ケジューラによって割り当てられたばかりの同一の伝送
時間に対する以前の予約があるか否かを判定する。すな
わち、コントローラ３４は、エントリがあるか否かを知
るために、メモリ３３１内の適当な位置をチェックする
（読み出す）。
そのセルの伝送時間割当について出力スケジューラと交
渉する。さらに、入力コントローラ３４は、その出力ス
ケジューラによって割り当てられたばかりの同一の伝送
時間に対する以前の予約があるか否かを判定する。すな
わち、コントローラ３４は、エントリがあるか否かを知
るために、メモリ３３１内の適当な位置をチェックする
（読み出す）。
【００３９】メモリ３３１内のその位置が空である場
合、コントローラは割当を受け入れ、アドレス制御メモ
リ内のセルに対して割り当てられた伝送時間の格納を実
行する。メモリ３３１内のその位置が空でない場合、コ
ントローラ３４はそのセルに対する伝送時間割当を拒絶
する。次のスケジューリング試行（スケジューリング周
期）中に、コントローラ３４は、そのセルに対して再び
伝送時間割当要求を発し、出力スケジューラから新たに
割り当てられた伝送時間を受信すると、使用不能（以前
に割り当てられた）伝送時間を再利用のためにスケジュ
ーラに返す。このようにして、入力コントローラ３４
は、使用することができる割当を受信するまで出力ｊへ
の伝送タイムスロット割当の要求を継続する。使用不能
なタイムスロットはすべて入力コントローラによって返
される。他の入力が出力ｊへの伝送にそのタイムスロッ
トを利用することが可能となる。
合、コントローラは割当を受け入れ、アドレス制御メモ
リ内のセルに対して割り当てられた伝送時間の格納を実
行する。メモリ３３１内のその位置が空でない場合、コ
ントローラ３４はそのセルに対する伝送時間割当を拒絶
する。次のスケジューリング試行（スケジューリング周
期）中に、コントローラ３４は、そのセルに対して再び
伝送時間割当要求を発し、出力スケジューラから新たに
割り当てられた伝送時間を受信すると、使用不能（以前
に割り当てられた）伝送時間を再利用のためにスケジュ
ーラに返す。このようにして、入力コントローラ３４
は、使用することができる割当を受信するまで出力ｊへ
の伝送タイムスロット割当の要求を継続する。使用不能
なタイムスロットはすべて入力コントローラによって返
される。他の入力が出力ｊへの伝送にそのタイムスロッ
トを利用することが可能となる。
【００４０】実験的には、本発明の原理によって実現さ
れる入力待ち行列出力スケジューリング交換機は、ラン
ダムセル到着モデルの場合９２％という顕著に改善され
たスループットを有する。各出力スケジューラにおける
１タイムスロットのみの再利用がこの結果を達成するた
めに使用された。タイムスロット再利用と入力グループ
化の組み合わせによって、さらにスループットは９５％
まで改善されることが可能である。
れる入力待ち行列出力スケジューリング交換機は、ラン
ダムセル到着モデルの場合９２％という顕著に改善され
たスループットを有する。各出力スケジューラにおける
１タイムスロットのみの再利用がこの結果を達成するた
めに使用された。タイムスロット再利用と入力グループ
化の組み合わせによって、さらにスループットは９５％
まで改善されることが可能である。
【００４１】入力グループ化を示す実施例を図６に示
す。この実施例では、ｋ個の入力ポートがグループ化さ
れる。入力モジュール９−１から９−（Ｎ／ｋ）のｋ個
の入力に到着するセルはセルメモリ２´に格納され、セ
ルメモリは、単一の待ち行列コントロール３´によって
制御される。待ち行列コントロール３´は、ｋ個以内の
セルが、セルメモリからグループ内の他の交換機入力ポ
ートに出力されるように動作する。
す。この実施例では、ｋ個の入力ポートがグループ化さ
れる。入力モジュール９−１から９−（Ｎ／ｋ）のｋ個
の入力に到着するセルはセルメモリ２´に格納され、セ
ルメモリは、単一の待ち行列コントロール３´によって
制御される。待ち行列コントロール３´は、ｋ個以内の
セルが、セルメモリからグループ内の他の交換機入力ポ
ートに出力されるように動作する。
【００４２】従って、待ち行列コントロール３´内のア
ドレス制御メモリは任意の与えられた伝送タイムスロッ
トにｋ個以内の割当を格納する位置を有する。グループ
のいずれの入力ポート１でセルが受信されるかにかかわ
らず、セルは、セルメモリおよび待ち行列コントロール
によって制御され、同一伝送タイムスロットで伝送され
る他のセルとは異なる出力ポートを宛先とする他の交換
機入力ポート４に出力される。図６の実施例はさらに、
コンテンションコントロール７´内の各入力スケジュー
ラが、入力グループ化のために、Ｎ／ｋ個の待ち行列コ
ントロールのみからの入力を受信するように改良されて
いる。
ドレス制御メモリは任意の与えられた伝送タイムスロッ
トにｋ個以内の割当を格納する位置を有する。グループ
のいずれの入力ポート１でセルが受信されるかにかかわ
らず、セルは、セルメモリおよび待ち行列コントロール
によって制御され、同一伝送タイムスロットで伝送され
る他のセルとは異なる出力ポートを宛先とする他の交換
機入力ポート４に出力される。図６の実施例はさらに、
コンテンションコントロール７´内の各入力スケジュー
ラが、入力グループ化のために、Ｎ／ｋ個の待ち行列コ
ントロールのみからの入力を受信するように改良されて
いる。
【００４３】明示していないが、セルが入力ポート１で
受信されるよりも高速で交換機５へ送信されるように、
セルメモリは書き込みよりも読み出しのほうが高速とす
ることが可能である。これは「スピードアップ」と呼ば
れ、タイムスロット再利用と組み合わせて同様のスルー
プット改善が期待される、入力グループ化の別の形態で
ある。
受信されるよりも高速で交換機５へ送信されるように、
セルメモリは書き込みよりも読み出しのほうが高速とす
ることが可能である。これは「スピードアップ」と呼ば
れ、タイムスロット再利用と組み合わせて同様のスルー
プット改善が期待される、入力グループ化の別の形態で
ある。
【００４４】
【発明の効果】以上述べたごとく、本発明によれば、ス
ループット性能は、伝送時間の再利用によって、ランダ
ムセルトラヒックモデルの場合５８％から９２％に改善
される。さらに、入力グループ化を組み合わせれば、ス
ループットは９５％に改善される。
ループット性能は、伝送時間の再利用によって、ランダ
ムセルトラヒックモデルの場合５８％から９２％に改善
される。さらに、入力グループ化を組み合わせれば、ス
ループットは９５％に改善される。
【図１】入力待ち行列パケット交換機のブロック図であ
る。
る。
【図２】図１の単一の入力ポートの待ち行列制御要素の
詳細なブロック図である。
詳細なブロック図である。
【図３】図１のコンテンションコントロールの詳細なブ
ロック図である。
ロック図である。
【図４】図２のアドレス制御メモリの詳細な図である。
【図５】本発明に原理によって実現される交換機の特定
出力ポートの出力スケジューラの図である。
出力ポートの出力スケジューラの図である。
【図６】入力グループ化を使用した代替実施例のブロッ
ク図である。
ク図である。
１ 入力ポート ２ セルメモリ ３ 待ち行列コントロール ３１ ＶＰＩテーブル ３２ メモリ ３３ アドレス制御メモリ ３３１ 出力制御メモリ ３３２ セル到着順メモリ ３４ 入力コントローラ ４ 交換機入力ポート ５ Ｎ×Ｎ交換機 ６ 交換機出力ポート ７ コンテンションコントロール ７０ 出力スケジューラ ７０２ コントローラ ７０３ 次利用可能タイムスロット発生器 ７０４ 再利用タイムスロットメモリ ９ 入力モジュール
───────────────────────────────────────────────────── フロントページの続き (72)発明者 カイ イン エング アメリカ合衆国 07716 ニュージャージ ー アトランティック ハイランズ、ペイ プ ドライヴ 54 (72)発明者 マーク ジョン カロル アメリカ合衆国 07704 ニュージャージ ー フェアヘイヴン、ポプラー アヴェニ ュー 26
Claims (9)
- 【請求項１】 複数の入力ポートおよび出力ポートを有
する交換機への入力に到着するパケットセルをスケジュ
ーリングする装置において、 各入力ポートに対応して、対応する入力ポートに到着す
るパケットセルを格納する手段と、 各入力ポートに対応して、特定のパケットセルが、対応
する入力ポートから交換機の特定の出力ポートへアクセ
スを許可される、その特定パケットセルに対する伝送時
間をコンテンション制御手段から要求し、コンテンショ
ン制御手段によって割り当てられた伝送時間を受け取
り、以前に割り当てられた伝送時間を返すことによっ
て、前記格納手段内のパケットセルの記憶装置を制御す
る手段と、 交換機の出力ポートへの各アクセス要求に伝送時間を割
り当て、前記記憶装置制御手段によって返された少なく
とも１つの以前に割り当てられた伝送時間を格納するコ
ンテンション制御手段とからなることを特徴とするパケ
ットセルスケジューリング装置。 - 【請求項２】 コンテンション制御手段が複数のスケジ
ューリング手段を有し、各スケジューリング手段は、特
定の出力ポートに対応して、その特定出力ポートに対す
る各要求を異なる伝送時間へとスケジューリングするこ
とを特徴とする請求項１の装置。 - 【請求項３】 スケジューリング手段がさらに、 以前に割り当てられた伝送時間を格納する手段と、 次利用可能伝送時間を発生する手段と、 要求に応答して、前記伝送時間格納手段および前記伝送
時間発生手段のうちの１つから伝送時間を選択的に割り
当てる手段とを有することを特徴とする請求項２の装
置。 - 【請求項４】 記憶装置制御手段が、 パケットセルを最初のもとの到着順序で保持する手段
と、 そのパケットセルに割り当てられた伝送時間を出力ポー
トに伝送するために格納する手段とを有することを特徴
とする請求項２の装置。 - 【請求項５】 以前に割り当てられた伝送時間を格納す
る手段が、以前に割り当てられた伝送時間を複数格納す
る手段を有することを特徴とする請求項３の装置。 - 【請求項６】 スケジューリング手段がさらに、伝送時
間格納手段から、以前に割り当てられた伝送時間を消去
する手段を有することを特徴とする請求項３の装置。 - 【請求項７】 記憶装置制御手段がさらに、割り当てら
れた伝送時間に格納手段から格納されたパケットセルを
取得する手段を有することを特徴とする請求項１の装
置。 - 【請求項８】 記憶装置制御手段が、 現在割り当てられている伝送時間が、伝送時間格納手段
内で他の伝送のために予約されているか否か判定する手
段と、 この判定手段に応答して、その伝送時間が既に予約され
ている場合に現在割り当てられている伝送時間をコンテ
ンション制御手段に返却する手段とを有することを特徴
とする請求項４の装置。 - 【請求項９】 記憶装置制御手段がさらに、以前に割り
当てられた伝送時間を後の要求期間中に返却するために
前記返却手段を遅延させる手段を有することを特徴とす
る請求項８の装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US878801 | 1992-05-05 | ||
| US07/878,801 US5255265A (en) | 1992-05-05 | 1992-05-05 | Controller for input-queued packet switch |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0637805A true JPH0637805A (ja) | 1994-02-10 |
| JP2981082B2 JP2981082B2 (ja) | 1999-11-22 |
Family
ID=25372874
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP12485193A Expired - Fee Related JP2981082B2 (ja) | 1992-05-05 | 1993-04-30 | パケットセルスケジューリング装置 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US5255265A (ja) |
| EP (1) | EP0569172B1 (ja) |
| JP (1) | JP2981082B2 (ja) |
| CA (1) | CA2093849C (ja) |
| DE (1) | DE69330395T2 (ja) |
| ES (1) | ES2160586T3 (ja) |
Families Citing this family (37)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| SE515148C2 (sv) * | 1993-06-23 | 2001-06-18 | Ericsson Telefon Ab L M | Styrning av cellväljare |
| US5542115A (en) | 1994-06-24 | 1996-07-30 | Pioneer Tech Development Limited | Paging method and apparatus |
| US5949781A (en) * | 1994-08-31 | 1999-09-07 | Brooktree Corporation | Controller for ATM segmentation and reassembly |
| US5517495A (en) * | 1994-12-06 | 1996-05-14 | At&T Corp. | Fair prioritized scheduling in an input-buffered switch |
| US5631908A (en) * | 1995-03-28 | 1997-05-20 | Digital Equipment Corporation | Method and apparatus for generating and implementing smooth schedules for forwarding data flows across cell-based switches |
| KR100262682B1 (ko) * | 1995-04-15 | 2000-08-01 | 최병석 | 멀티캐스트 atm교환기 및 그멀티캐스트 경합조정방법 |
| US5838684A (en) * | 1996-02-22 | 1998-11-17 | Fujitsu, Ltd. | Low latency, high clock frequency plesioasynchronous packet-based crossbar switching chip system and method |
| US5991296A (en) * | 1996-02-22 | 1999-11-23 | Fujitsu, Ltd. | Crossbar switch and method with reduced voltage swing and no internal blocking data path |
| US5923644A (en) * | 1996-10-03 | 1999-07-13 | The Board Of Trustees Of The Leland Stanford Junior University | Apparatus and method for processing multicast cells in an input-queued multicast switch |
| JP2871650B2 (ja) | 1997-04-17 | 1999-03-17 | 日本電気株式会社 | データ伝送システム |
| US5978858A (en) * | 1997-09-30 | 1999-11-02 | Compaq Computer Corporation | Packet protocol and distributed burst engine |
| JP3125739B2 (ja) * | 1998-02-17 | 2001-01-22 | 日本電気株式会社 | バススイッチ |
| US6044061A (en) * | 1998-03-10 | 2000-03-28 | Cabletron Systems, Inc. | Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch |
| US6160812A (en) * | 1998-05-04 | 2000-12-12 | Cabletron Systems, Inc. | Method and apparatus for supplying requests to a scheduler in an input buffered multiport switch |
| US6185221B1 (en) | 1998-11-09 | 2001-02-06 | Cabletron Systems, Inc. | Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch |
| US6539026B1 (en) | 1999-03-15 | 2003-03-25 | Cisco Technology, Inc. | Apparatus and method for delay management in a data communications network |
| US6952401B1 (en) * | 1999-03-17 | 2005-10-04 | Broadcom Corporation | Method for load balancing in a network switch |
| US6895015B1 (en) * | 1999-05-05 | 2005-05-17 | Advanced Micro Devices, Inc. | Dynamic time slot allocation in internal rules checker scheduler |
| US7058063B1 (en) * | 1999-06-18 | 2006-06-06 | Nec Corporation | Pipelined packet scheduler for high speed optical switches |
| US6731638B1 (en) * | 1999-10-14 | 2004-05-04 | Synchrodyne Networks, Inc. | Switch scheduling with common time reference |
| DE10105935B4 (de) * | 2000-02-09 | 2009-06-18 | Nec Corp. | Multimode-Scheduler, Vorrichtung mit einem Multimode-Scheduler und Multimode-Abwicklungsverfahren |
| US7023841B2 (en) * | 2000-12-15 | 2006-04-04 | Agere Systems Inc. | Three-stage switch fabric with buffered crossbar devices |
| US7158528B2 (en) * | 2000-12-15 | 2007-01-02 | Agere Systems Inc. | Scheduler for a packet routing and switching system |
| US7161906B2 (en) * | 2000-12-15 | 2007-01-09 | Agere Systems Inc. | Three-stage switch fabric with input device features |
| JP4072315B2 (ja) * | 2000-12-26 | 2008-04-09 | 富士通株式会社 | パケットスイッチ |
| US7433683B2 (en) * | 2000-12-28 | 2008-10-07 | Northstar Acquisitions, Llc | System for fast macrodiversity switching in mobile wireless networks |
| US7065046B2 (en) * | 2001-04-06 | 2006-06-20 | Lucent Technologies Inc. | Scalable weight-based terabit switch scheduling method |
| US20020191588A1 (en) * | 2001-06-13 | 2002-12-19 | Drexel University | Integrated circuit and packet switching system |
| US20030035371A1 (en) * | 2001-07-31 | 2003-02-20 | Coke Reed | Means and apparatus for a scaleable congestion free switching system with intelligent control |
| FR2830162B1 (fr) * | 2001-09-27 | 2003-12-05 | Streamcore | Dispositif de gestion partagee |
| JP3747839B2 (ja) * | 2001-11-21 | 2006-02-22 | 日本電気株式会社 | 符号変換システム及びその変換方法並びに変換プログラム |
| KR100483546B1 (ko) * | 2002-08-22 | 2005-04-15 | 엘지전자 주식회사 | 에이티엠 입력 셀 복제에 의한 멀티캐스트 스위칭 장치 및방법 |
| GB2397966B (en) * | 2003-02-01 | 2005-04-20 | 3Com Corp | High-speed switch architecture |
| GB2401279B (en) * | 2003-04-29 | 2005-06-01 | 3Com Corp | Switch module architecture |
| CN101002443A (zh) * | 2004-08-12 | 2007-07-18 | 皇家飞利浦电子股份有限公司 | 用于在集成电路中将数据分配给至少一个分组的方法 |
| US8054487B2 (en) | 2004-12-16 | 2011-11-08 | International Business Machines Corporation | Mechanism to create a reservation against a future scheduling object instantiation |
| US7346050B2 (en) * | 2005-01-31 | 2008-03-18 | International Business Machines Corporation | Method, system, and storage medium for delay optimization for scheduling in bufferless crossbar switches |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0287745A (ja) * | 1988-09-26 | 1990-03-28 | Nippon Telegr & Teleph Corp <Ntt> | セル競合制御回路 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| IT1196791B (it) * | 1986-11-18 | 1988-11-25 | Cselt Centro Studi Lab Telecom | Elemento di commutazione per reti di interconnessione multistadio autoinstradanti a commutazione di pacchetto |
| DE3738177A1 (de) * | 1987-11-10 | 1989-05-18 | Siemens Ag | Vermittlungsknoten fuer die vermittlung von in datenpaketen uebertragenen datensignalen |
| US4979165A (en) * | 1989-06-23 | 1990-12-18 | At&T Bell Laboratories | Multiple queue bandwidth reservation packet system |
| JP2803262B2 (ja) * | 1989-12-15 | 1998-09-24 | 日本電気株式会社 | パケット・スイッチ |
| US5157654A (en) * | 1990-12-18 | 1992-10-20 | Bell Communications Research, Inc. | Technique for resolving output port contention in a high speed packet switch |
-
1992
- 1992-05-05 US US07/878,801 patent/US5255265A/en not_active Expired - Lifetime
-
1993
- 1993-04-13 CA CA002093849A patent/CA2093849C/en not_active Expired - Fee Related
- 1993-04-26 EP EP93303225A patent/EP0569172B1/en not_active Expired - Lifetime
- 1993-04-26 DE DE69330395T patent/DE69330395T2/de not_active Expired - Fee Related
- 1993-04-26 ES ES93303225T patent/ES2160586T3/es not_active Expired - Lifetime
- 1993-04-30 JP JP12485193A patent/JP2981082B2/ja not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0287745A (ja) * | 1988-09-26 | 1990-03-28 | Nippon Telegr & Teleph Corp <Ntt> | セル競合制御回路 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2981082B2 (ja) | 1999-11-22 |
| DE69330395T2 (de) | 2002-05-16 |
| CA2093849C (en) | 1999-06-22 |
| ES2160586T3 (es) | 2001-11-16 |
| US5255265A (en) | 1993-10-19 |
| EP0569172A3 (en) | 1995-01-25 |
| CA2093849A1 (en) | 1993-11-06 |
| EP0569172A2 (en) | 1993-11-10 |
| DE69330395D1 (de) | 2001-08-09 |
| EP0569172B1 (en) | 2001-07-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2981082B2 (ja) | パケットセルスケジューリング装置 | |
| US5991295A (en) | Digital switch | |
| US7817543B2 (en) | Regulating data-burst transfer | |
| US6876629B2 (en) | Rate-controlled multi-class high-capacity packet switch | |
| Karol et al. | Improving the performance of input-queued ATM packet switches | |
| US7023841B2 (en) | Three-stage switch fabric with buffered crossbar devices | |
| US8031598B2 (en) | Flow-rate-regulated burst switches | |
| US7292580B2 (en) | Method and system for guaranteeing quality of service in a multi-plane cell switch | |
| US5982771A (en) | Controlling bandwidth allocation using a pace counter | |
| US7161906B2 (en) | Three-stage switch fabric with input device features | |
| JP2837651B2 (ja) | 通信システム | |
| EP0471344A1 (en) | Traffic shaping method and circuit | |
| JPH10164096A (ja) | マルチキャスト・パケット・アクセス調停方法 | |
| WO2007004159A2 (en) | Method and apparatus for bandwidth efficient and bounded latency packet buffering | |
| US7088729B2 (en) | Distributed scheduler for packet switches and passive optical networks | |
| JPH08307432A (ja) | 通信方法 | |
| JPH0879271A (ja) | セル交換装置及びセル交換システム | |
| JPH11122257A (ja) | 共通バッファ型スイッチ | |
| JPH11510010A (ja) | 割付け型及び動的帯域幅管理 | |
| JPH07183897A (ja) | 空間分割交換マトリクスの入力へ接続するための入力待ち行列システム | |
| Ranganathan et al. | A VLSI ATM switch architecture for VBR traffic | |
| JP3880890B2 (ja) | セルスイッチ及びセル交換方法 | |
| KR100220640B1 (ko) | Atm-pbx의 입력 버퍼형 atm스위치 | |
| JPH0730933A (ja) | 通話路スイッチ | |
| WO1997004570A1 (en) | Controlling bandwidth allocation using a pace counter |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080917 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |