JPH0856230A - スイッチングシステム - Google Patents

スイッチングシステム

Info

Publication number
JPH0856230A
JPH0856230A JP10390895A JP10390895A JPH0856230A JP H0856230 A JPH0856230 A JP H0856230A JP 10390895 A JP10390895 A JP 10390895A JP 10390895 A JP10390895 A JP 10390895A JP H0856230 A JPH0856230 A JP H0856230A
Authority
JP
Japan
Prior art keywords
tag
cell
output
value
bit
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.)
Pending
Application number
JP10390895A
Other languages
English (en)
Inventor
Raua Fuu
ラウア フー
Shien Chia
シェン チア
Gooshiyu Abuhijitsuto
ゴーシュ アブヒジット
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Publication of JPH0856230A publication Critical patent/JPH0856230A/ja
Pending legal-status Critical Current

Links

Classifications

    • 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
    • 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
    • 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
    • H04L49/309—Header conversion, routing tables or routing tags
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/40—Constructional details, e.g. power supply, mechanical construction or backplane
    • H04L49/405—Physical details, e.g. power supply, mechanical construction or backplane of ATM switches
    • 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)
  • Use Of Switch Circuits For Exchanges And Methods Of Control Of Multiplex Exchanges (AREA)

Abstract

(57)【要約】 【目的】 ダイナミック・スケジューリング・アルゴリ
ズムをサポートできるタグベースのスイッチングシステ
ムを得る。 【構成】 入力したセルに宛先ビットと優先度を示すタ
グを付加し、タグの値により出力順を決定する。タグの
値の比較は、木構造で配置された比較器により並列に行
うので、処理速度の速いスイッチングシステムが実現で
きる。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】この発明は、セルやパケットがノ
ード間でネットワークを転送されるディジタル通信ネッ
トワークに関するものである。さらに、この発明は、ネ
ットワーク中でセルが、あるノードから次のノードへ転
送される順序をスケジューリングするための改良された
方式を備えたディジタル通信ネットワークに関する。
【０００２】
【従来の技術】一般に、ディジタル通信ネットワークで
は、メッセージや情報の流れがパケットやセルと呼ばれ
る連続した小単位に細分化され、このセルやパケット
が、ノードからノードへ伝送される。また、各ノードに
おいて、スイッチがセルやパケットを伝送する順序と伝
送する次のノードとを選択する。その結果、ディジタル
情報はその最終宛先へ適時に到着する。これらのネット
ワークスイッチは、様々な特性のネットワーク通信をサ
ポートできるのが望ましい。例えば、適時な到着をリア
ルタイムに厳しく保証することを要求する通信、音声や
ビデオ用の連続的なメディア通信、早急な返答を要求す
る通信が含まれる。
【０００３】重要なディジタル通信ネットワークの１つ
として、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎ
ｓｆｅｒ Ｍｏｄｅ：非同期伝送モード）ネットワーク
がある。ＡＴＭネットワークは、ネットワーク中のある
ポイント（ノード）から、あるほかのポイント（ノー
ド）へデータを伝送するのに用いられる。ここで、デー
タや情報は、連続した固定サイズの小さなセルに細分化
されて、ネットワークのノード間で伝送される。ここで
述べているノードは、ネットワークの複数のノード間で
パケットやセルを高速にスイッチングしたり、ルーティ
ングしたりするＡＴＭスイッチを含む。ＡＴＭネットワ
ークの一般的な原理は、Ｊ・ブライアン・リールズとダ
ニエル・Ｃ・スウィンハートによる、「発生するギガビ
ット環境とローカルＡＴＭの役割」（ＩＥＥＥコミュニ
ケーションマガジン、３０巻、４類、１９９２年４月、
５２−５８頁）、及びＣ・ラムによる、「ＡＴＭ方式へ
の高速化」（ユニックス レビュー、１０巻、１０類、
１９９２年１０月、２９−３６頁）に述べられている。
【０００４】ＡＴＭネットワークの重要な課題の１つ
は、各スイッチによって伝送されるセルを、スケジュー
リングすることである。セルは通常、各スイッチの待ち
行列内に、バッファリングされる。セルの渋滞（輻輳）
がないものとすると、これらのセルは、スイッチで入力
リンクから受信され、直ちに出力リンクをとおして別の
宛先へ送信される。しかし、セルが複数の入力リンクを
通して到着し、同じ出力リンクへ同時に送信されなけれ
ばならない場合、セルが望ましい順序で伝送されるに
は、セルの待ち行列（キュー）をつくることが必要であ
る。
【０００５】どのセルがどの時間にどの順序で伝送され
るかのスケジューリングを調整するためには、ＦＩＦＯ
（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ：先入れ先出
し）方式による順序付けを使うのが普通である。ＦＩＦ
Ｏ方式においては、スイッチに、先に到着するセルが、
次に到着するセルに優先して伝送される。リアルタイム
アプリケーションをサポートするネットワークの場合、
セルに優先度がつけられ、セルの優先度によって、セル
は別々の待ち行列に記憶される。その後、セルは、その
別個の待ち行列の優先度に従って、指示された順序で伝
送される。これらの単純な方式は、限られた数と種類の
リアルタイムアプリケーションのみをサポートしうる。
なぜならば、ＦＩＦＯ方式と優先度スケジューリング機
能は、データ損失のない適時な伝送に対して、限られた
保証のみを提供できるからである。例えば、ＡＴＭロー
カル・エリア・ネットワーク、あるいは、ＡＴＭワイド
・エリア・ネットワークの初期世代のスイッチは、単
に、入力ネットワークリンクから出力ネットワークリン
クへセルを転送するというスケジューリングをしたりデ
ィスパッチしたりという、大変簡易なスケジューリング
アルゴリズムを備えている。通信は、ＡＴＭ法則による
ＦＩＦＯ順序付けで処理されるが、少数の、通常２種類
の優先順位が、リアルタイム通信要求を持つアプリケー
ションをサポートするために、かなり限定された方法で
提供されている。静的に割り当てられた優先度は、近年
の進んだ変化に富む多種多様なアプリケーションを持つ
中位サイズのローカル・エリア・ネットワークに対して
さえも、ほとんど十分でない。さらに、アプリケーショ
ンが音声やビデオなど連続的なメディアを伝送する必要
がある場合、もしくは、アプリケーションが実時間で期
待した返答を必要とする場合、ネットワークサービスの
質や適時性に関して予測や保証をすることは実質的に不
可能である。
【０００６】過去２０年にわたって、実時間やマルチメ
ディア・コンピューティング及び通信に関して十分な研
究がなされてきた。また、多くのスケジューリングアル
ゴリズムが細部にわたり発明され、研究されてきた。例
えば、Ｊ・ジャンゴク・バーとＴ・スーダによる「ＡＴ
Ｍネットワークにおける通信量制御スキームとプロトコ
ルの分析」（ＩＥＥＥ会報７９巻、第２版、１９９１年
２月、１７０−１８９頁）は、ＡＴＭスイッチにおいて
一般的なスケジューリング機能によって、実現されなけ
ればならない多数の通信コントロールスキームを説明し
ている。さらに、Ｈ・ジャングらは、「転送速度に基づ
くサービス原則の比較」（Ｈ・ジャングとＳ・ケシャ
ブ、ＡＣＭ ＳＩＧＣＯＭＭ会報、’９１、チューリッ
ヒ、１９９１年９月）、「レート制御静的優先度待ち」
（Ｈ・ジャングとＤ・フェラーリ、国際コンピュータサ
イエンス学会技術報告＃ＴＲ−９２−００３、カリフォ
ルニア、バークレー）の論文で、転送速度に基づくサー
ビス原則と転送速度により制御された静的優先度キュー
イングを説明している。スケジューリングアルゴリズム
のさらなる例は、以下の論文、論説に記載されている。
Ｗ・Ａ・ホーン、「簡易なスケジューリングアルゴリズ
ム」（ナーバル リサーチ ロジスティッククオータリ
ー、２１巻、１９７４年、１７７−１８５頁）、Ｊ．
Ｒ．ジャクソン「最大遅延量を最小にするプロダクショ
ンラインのスケジューリング」（マネージメント サイ
エンス リサーチ プロジェクト、調査報告４３，ＵＣ
ＬＡ、１９５５年１月）、Ｃ・Ｒ・カルマネク，Ｈ・カ
ナキア，Ｓ・ケシャブ、「高速ネットワークのためのレ
ート制御サーバー］（ＩＥＥＥグローバル テレコミュ
ニケーション コンファレンス、カリフォルニア、サン
ディエゴ、１９９０年１２月、３００．３．１−３０
０．３．９頁）、Ａ・クマー，Ｊ・パレク「統合サービ
スネットワークにおけるフロー制御への汎用プロセッサ
ーのシェアリングアプローチ」（ｐｈＤ論文、ＭＩＴ、
１９９２年２月）、Ｈ・Ｔ・カング，Ａ・チャップマ
ン、「ＡＴＭネットワークに対するＦＣＶＣ（Ｆｌｏｗ
−Ｃｏｎｔｒｏｌｌｅｄ Ｖｉｒｔｕａｌ Ｃｈａｎｎ
ｅｌｓ：フロー制御バーチャルチャネル）提案」（ネッ
トワークプロトコルに関する１９９３年国際会議会報、
カリフォルニア、サンフランシスコ、１９９３年、１０
月１９−２２日）、Ｃ・Ｌ・リュウとＪ・Ｗ・レイラン
ド、「ハードの実時間環境におけるマルチプログラミン
グのためのスケジューリングアルゴリズム」（ＡＣＭジ
ャーナル、２０巻、第１版、１９７３年）、Ｌ・ジャン
グ、「バーチャルクロック：パケットスイッチネットワ
ークのための新しい通信量コントロールアルゴリズム」
（ＡＣＭ ＳＩＧＣＯＭＭ会報、ペンシルバニア、フィ
ラデルフィア、１９９０年９月、１９−２９頁）、Ｌ・
ジャング、「バーチャルクロック：パケットスイッチネ
ットワークのための新しい通信量コントロールアルゴリ
ズム」（コンピューターシステムにおけるＡＣＭトラン
ザクション、９巻、第２版、１９９１年５月、１０１−
１２４頁）、Ｑ・ジェング，Ｋ・シン、「２地点間パケ
ットスイッチネットワークにおける実時間チャネルの確
立能力について」（コミュニケーションにおけるＩＥＥ
Ｅトランザクション、１９９４年３月）。
【０００７】これらのアルゴリズムの多くは、ＡＴＭネ
ットワークにおける実行には、不適当とされてきたこと
に注意しなければならない。なぜならば、こうしたアル
ゴリズムは、一般的な環境には、専門的すぎるからであ
る。また、キューのサーチに時間がかかりすぎるからで
ある。
【０００８】しかし、ＡＴＭスケジューリングのための
ＶＬＳＩシーケンサーチップが、Ｈ・ジョナサン・カオ
とネクデット・アズンによる論文、「ＡＴＭ通信シェイ
パーと行列管理のためのＶＬＳＩシーケンサーチップ」
（ＩＥＥＥソリッドステイトサーキットジャーナル、２
７巻、第１１版、１９９２年１１月）において述べられ
ている。このシステムにおいて、セルは出力ポートにス
イッチングされる。各ポートは、それ自体の待ち行列と
シーケンサーチップを含んでいる。各ポートにおいて、
セルは、シーケンサーチップによって優先順位に分類さ
れる。このシステムは、改良された優先度スケジューリ
ングを実現しているが、スイッチの各出力ポートに対し
て別々の分類回路を要求する。その結果、コストが増加
し、スイッチのデザインの柔軟性が減少する。また、性
能低下の可能性もある。
【０００９】共用バッファスケジューリング方式を用い
たＡＴＭスイッチに関する重要な提案が、Ｈ・近藤ほ
か，Ｋ・大島ほかによる以下の２つの論文で述べられて
いる。Ｈ・近藤，Ｈ・山中，Ｍ・石脇，Ｙ・松田，Ｍ・
中谷、「ＡＴＭスイッチＬＳＩのための効率的なセルフ
タイムの行列アーキテクチャー」（カスタム インテグ
レーテド サーキット コンファレンス、サンディエ
ゴ、１９９４年５月）、Ｋ・大島，Ｈ・山中，Ｈ・斉
藤，Ｈ・山田，Ｓ・小浜，Ｈ・近藤，Ｙ・松田、「ＳＴ
Ｓタイプの共用バッファリングとそのＬＳＩ実現に基づ
く新しいＡＴＭスイッチアーキテクチャー」（国際スイ
ッチングシンポジウム’９２会報、日本、横浜、１９９
２年１０月、３５９−３６３頁）。このＡＴＭスイッチ
デザインの重要な要素は、共通の待ち合わせ機能と、統
計的な多重化を発展させるため共用バッファと、より迅
速な性能とより低いコストである。このスイッチは、出
力バッファリングを用いるほかのＡＴＭスイッチとは、
すべての入力ポートからの入力セルが直接共通のバッフ
ァメモリに蓄積されるという点で、区別される。出力
は、ＦＩＦＯ方式や単純な優先度方式に基いて選択され
る。このようなスイッチは、単純な優先度で満足するよ
うな、長距離テレコミュニケーションに対しては十分に
機能するが、このスイッチには、ファクトリーオートメ
ーションや、パワープラントコントロール、フルモーシ
ョンビデオなどリアルタイムアプリケーションをサポー
トする待ち行列制御の機能はない。
【００１０】
【発明が解決しようとする課題】この発明は、以上のよ
うな課題を解決するためになされたもので、スタティッ
クなスケジューリングアルゴリズムだけでなく、ダイナ
ミックなスケジューリングアルゴリズムに則った待ち行
列制御が可能なスイッチングシステムを得ることを目的
としている。
【００１１】
【課題を解決するための手段】この発明に係るスイッチ
ングシステムは、複数の入力リンクと複数の出力リンク
を持ち、各入力リンクによりネットワーク内の１以上の
宛先を示す宛先情報を含むヘッダフィールドとデータと
を格納したセルを受信するスイッチと、上記ヘッダフィ
ールドの宛先情報を、各ビットが各出力リンクに対応し
ておりそのビットが有意状態である時そのセルが最終宛
先に到着するようにそのビットに対応する出力リンクに
対してそのセルを出力することを示している宛先ビット
のベクトルに変換する変換手段と、各セルに対して、上
記宛先ビットのベクトルを付加するベクトル付加手段
と、上記ベクトルを付加されたセルを１つ以上の出力リ
ンクに接続する接続手段とを備え、上記接続手段は、上
記ベクトルを付加されたセルを到着順に格納するキュー
イング手段と、キューイング手段に格納されたセルの中
から到着順とは異なる順に各出力リンクに対して各出力
リンクに対応する宛先ビットが有意状態のセルを選択す
る選択手段とを備え、上記選択手段は、セルの出力をス
ケジュールするスケジュール手段を有し、上記スケジュ
ール手段は、選択順を決定するアルゴリズムを記憶する
手段と、スイッチの動作に先だってそのアルゴリズムを
設定する手段と、スイッチの動作中にそのアルゴリズム
を再設定する手段と、上記各出力リンクに対してセル送
信時間内に上記アルゴリズムを実行する手段を有してお
り、上記スイッチは、更に、上記出力リンクに選択した
セルを出力する出力手段を備えたことを特徴とする。
【００１２】上記出力手段は、上記ベクトルが除去され
たセルを出力することを特徴とする。
【００１３】上記アルゴリズムは、ダイナミック・プラ
イオリティ・スケジューリング・アルゴリズムと、スタ
ティック・プライオリティ・スケジューリング・アルゴ
リズムと、ラウンド・ロビン・アルゴリズムと、これら
の組み合わせのいずれかから選択されることを特徴とす
る。
【００１４】上記スケジュール手段は、各出力リンクに
セルを出力する順番を決定するために設定されたスケジ
ューリングアルゴリズムに基づいて、キューイング手段
の中に格納されたセルの出力順序を示す値をタグ値とし
て計算し、このタグ値を有するタグをセルに付加するタ
グ付加手段を有し、上記選択手段は、タグ値と宛先ビッ
トの値に基づいて、キューイング手段の中に格納された
セルをサーチするサーチ手段とを備え、選択手段は、各
出力リンクに対応する宛先ビットの値が有意状態である
セルの中で最も小さいタグ値を持つセルをサーチして選
択し、もし、最も小さいタグ値を持つセルが２以上存在
する場合に、先に到着したセルを選択することを特徴と
する。
【００１５】上記キューイング手段は、先頭から末尾に
至る複数のレジスタからなるＦＩＦＯ回路を備え、各レ
ジスタは、出力を待っているセルを示すものであり、各
レジスタは、上記宛先ビットのベクトルとタグ値のバイ
ナリーコードを保持し、各レジスタは、先頭から末尾の
方向でセルの到着順を示していることを特徴とする。
【００１６】上記サーチ手段は、上記レジスタの数と同
じ数の複数の比較回路を備え、各比較回路は、各レジス
タに対応して設けられ、各比較回路は、対応したレジス
タのタグ値と末尾側にある次のレジスタに対応した比較
回路からの出力値を比較するようにリニアに配置され、
各比較回路は、対応するレジスタのタグ値が末尾側にあ
る次に比較回路から出力されたタグ値より小さい場合で
あって、かつ、選択した出力リンクに対する宛先ビット
が有意状態である場合に、出力ビットをオンにすること
により、上記比較回路は、選択した出力リンクに対して
最小のタグ値を伝搬させ、待ち行列の中からセルを選択
することを特徴とする。
【００１７】上記サーチ手段は、上記レジスタの数の半
分に当たる複数の比較回路と追加の比較回路を備え、上
記比較回路を階層的に配置し、ルートと枝と葉を持つツ
リーを構成し、葉と枝のサブセットによりサブツリーを
構成し、葉に配置された各比較回路は、２つの隣り合う
レジスタのタグ値を比較して小さいタグ値を有するレジ
スタを識別し、上記追加の比較回路は、２つのサブツリ
ーからのタグ値を比較し、選択した出力リンクに対し
て、最小のタグ値を持つレジスタが存在しているサブツ
リーを識別し、上記ツリーは、選択した出力リンクに対
して、最小のタグ値を伝搬することを特徴とする。
【００１８】また、この発明に係るスイッチングシステ
ムは、複数の出力リンクと出力リンクを示すアドレスを
含んだセルを受信する複数の入力リンクと、上記アドレ
スを宛先ビットに変換する変換手段と、上記入力リンク
のセルを少なくとも１つの出力リンクに接続する接続手
段とを備え、上記接続手段は、入力リンクから出力リン
クへセルの出力をスケジュールするスケジュール手段を
備え、スケジュール手段は、各出力リンクにセルを出力
する順番を決定するために、予め設定されたスケジュー
リングアルゴリズムに基づいて、どのセルを出力すべき
かを示す値を生成し、生成した値をタグ値として有する
タグをセルに付加するタグ手段と、共通キューと、上記
共通キューに、各セルに対して宛先ビットとタグ値を挿
入する手段と、上記宛先ビットとタグ値に基づいて、上
記共通キューから、対応している宛先の中から最小のタ
グ値を持つセルをサーチするサーチ手段と、宛先に対応
した出力リンクに対して最小のタグ値を持つセルを出力
する出力手段とを備えたことを特徴とする。
【００１９】上記サーチ手段は、最小のタグ値をシリア
ルに評価していくリニアサーチ手段を有していることを
特徴とする。
【００２０】上記サーチ手段は、木構造を用いて同時に
複数対のセルを評価していくロガリズミックサーチ手段
を有していることを特徴とする。
【００２１】上記サーチ手段は、リニアサーチ手段とロ
ガリズミックサーチ手段を結合したサーチ手段を有して
いることを特徴とする。
【００２２】上記タグ手段は、先頭から末尾までのキュ
ーを形成するように配置された一連のタグレジスタと、
複数の比較器と、上記タグレジスタと比較器を接続する
接続手段と、上記セルを対応するタグレジスタにより識
別できるように記憶する記憶手段と、記憶されたセルの
タグ値をタグレジスタに設定する設定手段とを備え、上
記比較器は、タグレジスタのタグ値と１つ前の比較器か
らの出力値を比較して小さい方の値を決定するととも
に、小さい方の値と宛先ビットを出力する出力手段と、
小さい方の値と宛先ビットに基づいて、記憶されたセル
を識別する識別手段とを備えたことを特徴とする。
【００２３】上記比較器は、一連のビットから構成され
た出力を持ち、この一連のビットの中に、宛先ビットが
有意状態であり、同じ宛先ビットが有意状態であるキュ
ー中の他のセルのタグ値よりも小さいタグ値を持つこと
を示す特定ビットを有しており、各比較器は、各タグ値
とキューの末尾方向にあるタグの最小値とを比較するこ
とにより、宛先別に各セルのプライオリティを設定する
ことを特徴とする。
【００２４】上記比較器は、２つのタグ値を比較する手
段と、小さい方の値を出力する手段とを有し、１つのタ
グ値に対して１つの追加の入力ビットを備え、上記比較
器の出力は、比較対象となるタグ値を示す追加の入力ビ
ットにより条件付けられていることを特徴とする。
【００２５】上記追加の入力ビットは、宛先ビットが有
意状態になっているセルのタグ値を特定するものである
ことを特徴とする。
【００２６】上記スイッチングシステムは、更に、最小
のタグ値を持つセルが２以上存在する場合に、キューの
先頭に近いセルを選択する手段を備えたことを特徴とす
る。
【００２７】上記タグ手段は、枝を経由してルートに連
結された葉を持った階層的木構造を有し、各枝は、一対
のタグレジスタと隣り合うタグレジスタの間に設けられ
たタグレジスタ用比較器と、２つのタグレジスタ用比較
器からの出力を入力する追加の比較器を有しており、上
記追加の比較器は、宛先ビットが有意状態になってお
り、小さい方のタグ値を持つタグレジスタに対応するセ
ルを識別する手段を有していることを特徴とする。
【００２８】上記タグレジスタ用比較器は、小さい方の
タグ値と２つの比較ビットを出力し、２つの比較ビット
の内、一方の比較ビットは一方のセルが小さい方のタグ
値を持っていることを示し、２つの比較ビットの内、他
方の比較ビットは他方のセルが小さい方のタグ値を持っ
ていることを示すものであり、上記選択手段は、小さい
方のタグ値を持っているセルを識別するために、宛先ビ
ットと比較ビットを入力する複数のＡＮＤゲートを有
し、複数のＡＮＤゲートは、ルートにおいてただ１つの
ＡＮＤゲートが有意な出力を有するように構成されてお
り、このＡＮＤゲートの有意な出力により出力リンクに
出力されるセルを示すことを特徴とする。
【００２９】上記ＡＮＤゲートは、そのＡＮＤゲートに
対応したセルが適切な宛先ビットを有しているかを判定
するために用いられるものであり、上記タグレジスタ用
比較器は、異なるＡＮＤゲートへ接続された出力ビット
を有し、このタグレジスタ用比較器からの出力ビット
は、対応するセルの宛先ビットとＡＮＤを取られ、その
結果の出力が有意状態である場合は、対応するセルが宛
先ビットが有意状態であり、最小のタグ値を持つセルで
あることを示すことを特徴とする。
【００３０】上記スイッチングシステムは、更に、２以
上のセルが最小のタグ値を有する場合、先着のセルを識
別する手段を有することを特徴とする。
【００３１】上記タグレジスタ用比較器は、先頭と末尾
を持つキューを定義し、上記追加の比較器は、２入力か
ら小さい値を出力するとともに、キューの先頭方向にあ
る２入力の値がキューの末尾方向にある２入力の値以下
である場合に、有意状態を出力することを特徴とする。
【００３２】上記スイッチングシステムは、更に、上記
木構造のルート方向への上位層レベルにおいて、下位層
レベルのどの枝が小さい方のタグ値を有しているか決定
することにより小さい方のタグ値を有する枝を識別する
識別手段を有し、上記識別手段は、各タグに対応してそ
のタグの宛先ビットとそのタグが最小のタグ値を有する
ことを示すビットとのＡＮＤを取るためのＡＮＤゲート
を有していることを特徴とする。
【００３３】
【作用】この発明のスイッチングシステムは、スケジュ
ール手段がセルの出力をスケジュールする。スケジュー
ル手段は、所定のアルゴリズムに基づいて、セルを順番
に選択する。このように、スケジュール手段を備えるこ
とにより、セルの優先処理が行える柔軟なシステムを提
供する。また、上記スケジュール手段は、いろいろな種
類なアルゴリズムを採用することができる。そのアルゴ
リズムによって、優先度の高いセルをタイムリーに交換
することができるとともに、優先度の低いセルを後から
交換することができる。
【００３４】出力手段は、セルを出力する場合には、ス
イッチの内部で用いた宛先ビットのベクトルを除去して
出力する。
【００３５】上記アルゴリズムとしては、ダイナミック
なスケジューリングアルゴリズムやスタティックなスケ
ジューリングアルゴリズムを用いることができるととも
に、ラウンド・ロビン・アルゴリズムも用いることがで
きる。或いは、これらのアルゴリズムの組み合わせでも
よい。
【００３６】スケジュール手段は、優先順位を示すタグ
値を計算し、このタグ値を有するタグをセルに付加す
る。サーチ手段は、このタグ値と宛先ビットを用いて出
力すべきセルをサーチする。結果として、選択手段は、
ある出力リンクに対する宛先ビットが有意状態（オン）
になっており、かつ、それらの中で最も小さいタグ値を
持つセルを選択する。最も小さいタグ値を持つセルが２
以上存在する場合には、先に到着したセルを選択する。
【００３７】キューイング手段は、複数のレジスタによ
りＦＩＦＯを構成している。この複数のレジスタからな
るＦＩＦＯにより到着順を示すとともに、宛先ビットの
ベクトルとタグを保持するようにしている。
【００３８】サーチ手段は、複数の比較回路をリニアに
配置し、各レジスタに記憶されたタグ値を順に比較する
ことにより、最小のタグ値を持つセルを検出する。
【００３９】或いは、サーチ手段は、２個のレジスタに
対して１つの比較回路を備え、２個のレジスタのタグ値
の比較結果を更に追加の比較回路で比較することによ
り、ツリー形式を用いて、最小のタグ値を持つセルを選
択する。このように、ツリー構造を用いた比較処理を行
うことにより、キューに記憶されたエントリーの数の対
数に比例する時間で最小のタグ値を持つセルを選択で
き、前述したリニアにサーチする場合に比べて高速処理
を行える。
【００４０】この発明のスイッチングシステムは、スケ
ジュール手段が、セルの出力順番を予め設定されたスケ
ジューリングアルゴリズムに基づいて決定する。スケジ
ュール手段は、出力リンクに共通に設けられたキューを
備え、そのキューに対して各セルの宛先ビットと優先度
を示すタグを記憶させる。サーチ手段が、この宛先ビッ
トとタグを参照することにより、出力リンクに出力する
セルの順番を決定する。タグに記載されるタグ値は、ダ
イナミック、或いは、スタティックなアルゴリズムのい
ずれのアルゴリズムに基づくもので計算されたもので構
わない。従って、このスイッチングシステムは、ユーザ
の要求に応じて柔軟なスケジューリング方式を採用する
ことができる。
【００４１】上記サーチ手段は、リニアサーチ手段によ
り、最小のタグ値を順番に捜していく。
【００４２】或いは、サーチ手段は、ロガリズミックサ
ーチ手段を有し、木構造を用いて最小のタグ値を高速に
検索する。
【００４３】或いは、サーチ手段は、リニアサーチ手段
とロガリズミックサーチ手段を結合したサーチ手段によ
り、最小のタグ値を検索する。
【００４４】上記タグ手段は、タグレジスタと比較器を
備え、タグレジスタにタグ値を設定し、比較器がこのタ
グ値を順番に比較していくことにより、最小のタグ値を
検出する。
【００４５】上記比較器は、特定の出力リンクに対する
宛先ビットが有意状態（オン）であり、最小のタグ値を
持つことを示す特定ビットを出力し、各比較器は、キュ
ーの末尾方向にある比較器からの出力と各比較器に対応
したタグ値とを比較することにより、優先度を決定す
る。
【００４６】比較器は、２つのタグ値を比較して小さい
方の値を出力する。また、比較器は、追加の入力ビット
を備え、追加の入力ビットにより入力したタグを比較対
象とするかどうかを決定する。
【００４７】上記追加の入力ビットは、宛先ビットが有
意状態（オン）になっているセルを示すことにより、対
応するタグ値が比較対象になるかどうかを特定するもの
である。
【００４８】もし、最小のタグ値を持つセルが２以上存
在する場合には、先に到着したセルを選択する。
【００４９】前述したタグ手段の別な構成として、タグ
を階層的構造を持った比較器により比較するようにして
も構わない。一対のタグレジスタに対して、比較器を１
個設け、この比較器からの出力を更に追加の比較器で比
較することにより、最小のタグ値を持つタグレジスタを
検出する。このようにして、検索を高速に行う。
【００５０】比較器は、比較した２つのタグ値の内、い
ずれのほうが小さい値を持っているかを示す比較ビット
を出力し、選択手段は、複数のＡＮＤゲートを有し、Ａ
ＮＤゲートが比較ビットを入力するとともに、宛先ビッ
トを入力することにより最終的に優先度の高いセルを１
つだけ特定する。
【００５１】ＡＮＤゲートは、宛先ビットが有意状態
（オン）になっているかどうかを判定するとともに、比
較器からの比較ビットとのＡＮＤを取ることにより、最
終的に宛先ビットが有意状態（オン）であり、最終のタ
グ値を持つセルを選択する。
【００５２】もし、２以上のセルが最終のタグ値を有す
る場合には、先に到着したセルを選択して出力する。
【００５３】タグ手段が前述したように、階層的木構造
を用いて最小のタグ値を検索する場合には、タグレジス
タ用比較器により先頭から末尾方向が存在するキューを
定義し、追加の比較器により先頭方向にあるタグ値が末
尾方向にあるタグ値よりも小さい場合に、その先頭方向
にあるタグ値を持ったセルを選択する。
【００５４】本発明のスイッチングシステムは、更に、
識別手段により階層的木構造を持つ場合に、どの枝が小
さい方のタグを有しているかを識別し、その識別手段
は、ＡＮＤゲートに基づいて、タグの宛先ビットとその
タグ値が最小のタグ値であることを示すビットとのＡＮ
Ｄを取ることにより、最終的に優先度の高いセルを選択
する。このようなＡＮＤゲートを備えることにより、階
層的木構造を取った場合に、葉からルートに対して宛先
ビットを伝搬するため、各タグ毎に必要とされていたＡ
ＮＤゲートを省略することができる。結果として、ＡＮ
Ｄゲートの数を減少させることができ、回路構成を簡略
することができる。
【００５５】
【実施例】
実施例１．各種のスケジューリングアルゴリズムを適合
させるために、この発明に係るディジタル通信ネットワ
ークスイッチは、改良されたスケジューリングシステム
を備えている。その改良されたスケジューリングアルゴ
リズムによれば、各セルは、スイッチに到着する都度、
タグ付けされ、その後、共通キューに記憶される。タグ
は、バイナリーの数値から成る。タグの数値は、トラヒ
ックのクラスに対応するスケジューリングアルゴリズム
や、セルが伝送されるバーチャルチャネル（ｖｉｒｔｕ
ａｌ ｃｈａｎｎｅｌ）の属性や、セル自身の特性を考
慮して計算される。続いて、キューが宛先とタグにより
出力リンク又は出力ポート毎に並列に検索される。複数
のセルの宛先が同一である時、即ち、出力リンク又は出
力ポートが同一である時は、その中で最小のタグ値を持
つセルが選択される。これにより、スイッチは、常に、
宛先毎に、スケジューリングアルゴリズムに従って、最
初のセルを選択する。
【００５６】より一般的に言えば、この発明のスイッチ
ングシステムは、アルゴリズムを記憶する手段を備えて
いる。記憶されたアルゴリズムに従って、セルがスケジ
ュールされる順番が決定される。また、アルゴリズム
は、スイッチの動作に先立って、また、スイッチの動作
中に変更可能であるので、ネットワークの幅広いトラヒ
ック要求に対応することが可能となる。
【００５７】この発明のスイッチは、スタティックアル
ゴリズムとダイナミックアルゴリズムの両方をサポート
可能である。これらのアルゴリズムには、以下のものを
含む。ルー，ジャングによるレートモノトニックアルゴ
リズム、ジャングによる単純優先度アルゴリズム、クマ
ーによるウェイテッドフェアキューイングアルゴリズ
ム、ジャクソン，ルー，ホーン，ジェングによる最早デ
ッドラインファーストアルゴリズム、ジャングによるバ
ーチャルクロックアルゴリズム、カルマネクによるラウ
ンド・ロビン及び階層的ラウンド・ロビン。以上のアル
ゴリズムは、本明細書で既に述べたものである。また、
カングのフローコントロールドバーチャルチャネルアル
ゴリズムのような複雑な制御アルゴリズムもサポート可
能である。
【００５８】この発明は、以下の３点により成り立って
いる。第１に、タグ値がいずれかの演算可能なファンク
ションに従って計算される点、第２に、タグ値がセルが
伝送される順番を示している点、第３に、上に挙げたす
べてのアルゴリズムに共通する特徴として、セルの順番
が数値のタグで表現されると言う点である。検索を成立
させる唯一の決定要因は、タグの持つ数値であり、タグ
の持つ意味は問われない。さらに、各セルのタグ値は、
伝送中に計算されるので、スタティック・スケジューリ
ング・アルゴリズムだけでなく、ダイナミック・スケジ
ューリング・アルゴリズムもサポートできる。また、タ
グ毎に、十分な数のビットが用意されているので、スイ
ッチバッファ中の全セルの順番を並び替えて、各ビット
の値を書き変えることも可能である。
【００５９】この発明のポイントは、タグベースの検索
を行う点にある。各セル（ＡＴＭセル）は、ネットワー
クスイッチに到着すると、バイナリーの数値を持つタグ
を付加される。典型的な実施例においては、８ビット、
１６ビット、あるいはそれ以上の複数のビットを持つタ
グが用いられる。８ビットの場合には、２５６（２の８
乗）通りのタグ値が設定できる。１６ビットの場合に
は、６５５３６（２の１６乗）通り、ｎビットの場合に
は、２のｎ乗のタグ値が設定できる。各セルのタグは、
そのセルが伝送されるバーチャルチャネル、そのバーチ
ャルチャネルのトラヒックのクラスのスケジューリング
アルゴリズム、そのセル自身の特性等に関連する情報を
持っている。そして、セル、タグ及び宛先情報が、伝送
待ちのセルキューの末尾に入力される。この実施例にお
いては、キューは、ＶＬＳＩ回路で構成されている。
【００６０】やがて、スイッチが、特定の宛先にセルを
伝送しようとする時、キューに記憶されているすべての
セルを対象に出力リンク毎、或いは、出力ポート毎に並
列に検索が行われ、その宛先に一致する最小のタグ値を
持つセルが選択される。選択されたセルは、キューから
消去され、伝送される。キューの中に同一のタグ値を持
つ複数のセルが存在する場合には、もっとも早くキュー
に到着したセルが選択される。キュー検索部は、最小の
タグだけでなくセルが伝送される出力ポートも識別す
る。
【００６１】このアーキテクチャーにより、スタティッ
ク・スケジューリング・アルゴリズム，ダイナミック・
スケジューリング・アルゴリズムを問わず、前述した全
てのアルゴリズムを含む幅広いクラスのスケジューリン
グアルゴリズムを実現することが可能となる。また、タ
グ値に範囲設定をすれば、１つのスイッチで同時に種々
のトラヒックのクラスに対応する種々のスケージューリ
ングアルゴリズムを実現できる。具体的には、タグ値を
計算する際に、優先度の高いクラスのタグを数値の小さ
い範囲に割り当て、優先度の低いクラスのタグを数値の
大きい範囲に割り当てる。そのような割り当てを行え
ば、数値を頼りに検索するシステムでは、優先度の高い
クラスのセルが１つでもあれば、必ずそのセルが選択さ
れる。なぜならば、優先度の高いクラスのセルのタグ
は、優先度の低いクラスのセルのタグよりも、より小さ
い値を持つからである。
【００６２】図１を用いて説明する。ＡＴＭスイッチ１
０は、複数の入力リンク１４を備えている。複数の入力
リンク１４は、複数の入力処理部１６に接続されてい
る。複数の入力処理部１６からの出力は、それぞれキュ
ー検索部１８とメモリ（セルバッファメモリ）２０に入
力される。キュー検索部１８は、制御部２２により制御
される。制御部２２は、また、入力処理部１６及び出力
処理部２４も制御する。入力処理部１６及び出力処理部
２４は、それぞれマイクロプロセッサとメモリを備えて
いる。また、入力処理部１６と出力処理部２４は、制御
部２２によりアルゴリズムを設定、或いは、再設定する
手段を備えており、スイッチに到着するセルやスイッチ
から送り出されるセルのネットワークへの要求に従っ
て、適切なアルゴリズムが用いられるように制御され
る。
【００６３】キュー検索部１８の出力は、それぞれ出力
処理部２４に入力される。それに伴い、セルバッファメ
モリ２０の出力も出力処理部２４に入力される。２６に
示すように、入力処理部１６の出力は、宛先情報とタグ
とバッファアドレスを含んでいる。これらは、キュー検
索部１８に接続されている。また、２８に示すように、
セルヘッダーとセル本体は、セルバッファメモリ２０に
記憶される。
【００６４】次に、動作について説明する。セルは、入
力リンク１４を介して入力処理部１６に到着する。入力
処理部１６は、到着したセルをセル毎に処理する。通
常、どのＡＴＭスイッチでも行われている内部処理に加
えて、入力処理部１６はセル毎にタグ値を計算する。タ
グ値の計算は、そのセルのバーチャルチャネルに対応す
るスケジューリングアルゴリズムに従って行われる。タ
グ値は、また、バーチャルチャネルの状態やセルの到着
時刻にも左右される。バーチャルチャネルとは、他の全
てのデータストリームと区別される特定のデータストリ
ームのエンドトゥーエンドのコネクションを指す。ＡＴ
Ｍネットワークにおいて、それは、セルヘッダー中のビ
ットにより識別される。入力処理部１６は、また、バー
チャルチャネルの状態情報やスイッチによりメンテナン
スされる他の情報も計算し、更新する。
【００６５】上記計算後、タグと宛先情報とセルのバッ
ファアドレスとが出力され、キュー検索部１８のキュー
に記憶される。また、セルヘッダーとセルデータは、セ
ルバッファメモリ２０に出力される。その時点で、セル
のアドレス、宛先及びタグはキューイングされ、セルヘ
ッダーとセルデータは、セルバッファメモリに記憶され
る。こうして、入力処理部は、次のセルを受け付け、処
理することが可能な状態になる。以上のことから、入力
処理は、関連する入力リンク１４の１セルサイクルに割
り当てられた時間内に完了しなければならない。１セル
サイクルとは、入力リンクの帯域幅で１つのＡＴＭセル
を受信するのに必要な時間のことである。
【００６６】キュー検索部１８は、キューを順に検索
し、個々の出力処理部２４について対応する宛先ビット
を持つセルを選択する。出力処理部２４は、セルが伝送
されるのに必要な計算があればその計算を行う。その
後、ネットワークの他のノードやセルの最終宛先に向け
て出力リンク３０にセルを伝送する。キュー検索部１８
によって行われる検索は、全ての出力処理部に関連する
スイッチ内の入力リンク１４及び出力リンク３０の内、
最も遅いリンクの１セルサイクルに割り当てられた時間
内に完了しなければならない。
【００６７】この発明のキュー検索システムの説明に先
だって、図２を用いて既に知られている検索システムに
ついて説明する。これは、図１に示すキュー検索部１８
に相当する。図２に示す検索システムは、縦列接続する
ことにより上位ステージ又は／及び下位ステージを備え
ることができ、拡張することも可能である。キュー検索
部１８は、ＶＬＳＩを用いたＦＩＦＯ回路３１（ｓｅｌ
ｆ−ｔｉｍｅｄ ＦＩＦＯ）からなっている。キューエ
ントリーは、ＦＩＦＯ回路３１の末尾から挿入される。
ＦＩＦＯに未使用のエントリーがあれば、自動的にキュ
ーの先頭方向に前詰めにシフトされる。各キューエント
リー３９は、レジスタに記憶され、宛先フィールド４１
とアドレスフィールド３５と優先度ビット３７を持って
いる。宛先フィールド４１は、独立した一連のバイナリ
ービットを持っており、各ビットは１か０かいずれかの
値を持つ。この実施例では、１の値を有意状態（オン）
としている。この値は、データがどの出力リンクに伝送
されるかによって決定される。宛先フィールドを構成し
ている各ビットを、宛先ビットを呼ぶ。スイッチの出力
リンク３０と同数の宛先ビットがあり、各宛先ビット
は、特定の出力リンクへのコネクションを示している。
キューエントリーの宛先フィールドの対応するビットが
１の時に、キューエントリーと出力リンクを結ぶコネク
ションが成立する。例えば、宛先フィールドの第３ビッ
トがの１の時には、対応するデータは、第３の出力リン
クに伝送されることを示している。
【００６８】上で述べたように、宛先フィールドの各ビ
ットは、それぞれ出力リンクに対応しているので、キュ
ー全体を縦の列に着目して先頭から末尾まで眺めてみる
と、キューに記憶している全てのセルと１つの出力リン
クとの対応関係が分かる。即ち、各カラム（列）のビッ
トが１か０かを調べると、セルが特定の出力リンクに伝
送されるかどうかを確認することができる。マルチキャ
ストセルの場合、即ち、１つのセルが複数の出力リンク
に関連付けられている場合には、そのセルの宛先フィー
ルドには、１の値を持ったビットが複数存在する。図２
において、例えば、宛先フィールドの右端のカラムを見
てみると、１の値を持ったセルが２つあることが分か
る。この従来の検索システムにおいては、どのスケジュ
ーリングアルゴリズムを用いても、同一の出力リンクに
向かう２つのセルがある場合に、その伝送の順番を決定
できるようにするために、優先度ビット３７を設けてい
る。
【００６９】以上のように、キューエントリー３９の宛
先フィールド４１の中に１の値を持つビットがあれば、
そのキューエントリーのアドレスフィールド３５に示さ
れたアドレスに対応して、セルバッファメモリ２０に記
憶されているセルは、必ずそのビットに対応する出力リ
ンクに伝送される。このことは、宛先ビットによってセ
ルが１つの出力リンクに伝送されるか、或いは、複数の
出力リンクに伝送されるかを識別できるということを示
している。図２において、４３に示すキューエントリー
のように、宛先フィールド４１の全てのビットが０であ
る場合には、このエントリーは未使用であるとみなされ
る。また、図２には、検索回路５０とバス読み出し回路
４５が示されている。
【００７０】次に、動作について説明する。制御部２２
からキュー検索部１８に対して、「ある１つの出力リン
ク３０に伝送するセルを検索せよ」という命令が出され
ると、宛先フィールド４１の中でその出力リンクに対応
するビットが特定される。次に、検索回路５０が特定さ
れたビット位置に１がたっていて、かつ、キューの先頭
に最も近いキューエントリー３９を選択する。次に、制
御部２２は、選択されたキューエントリーのセルのアド
レスフィールド３５をバス読み出し回路４５に入力す
る。バス読み出し回路４５において、選択されたセルの
アドレスフィールド３５は、キュー検索部１８の出力４
９となる。続いて、選択されたキューエントリーの対応
する宛先ビットは、リセットされ、値は０となる。最後
に、出力処理部２４は、アドレスを出力４９により受け
取る。そのアドレスは、セルバッファメモリ２０から指
定された出力リンク３０へ伝送するセルを選択するため
に用いられる。
【００７１】図３は、説明を簡単にするために、図２に
示すキューエントリー３９が４つある場合を示してい
る。また、図２において、宛先フィールド４１で示して
いたものの内、宛先ビットを４２として示している。ま
た、遅延優先度フィルタ４８は、優先度ビット３７を入
力する。キュー検索部１８は、出力リンク３０に対応す
るセルを選択するコマンドを受けると、宛先ビットの中
からその出力リンクに対応するカラム４６を選択する。
このカラムは、遅延優先度フィルタ４８に入力される。
遅延優先度フィルタ４８には、既にキューの各エントリ
ーに対応する２つの優先度を示す優先度ビットが入力さ
れている。出力リンクが選択された時、宛先ビットの内
でその出力リンクに対応するカラムの全てのセルに対応
するビットが、遅延優先度フィルタ４８に入力される。
遅延優先度フィルタ４８は、優先度ビットと宛先ビット
を結合し、結合結果として０か１の値を持つ各セルに対
応するビットを出力する。この時、出力された値が０で
あれば、そのセルは選択されないことを示している。ま
た、ビットの値が１である時には、そのセルが選択され
る資格があるということを示している。このように、遅
延優先度フィルタ４８は、２種類の優先度を用いて単純
な優先度付けの機能を果たしている。この従来技術にお
いて、遅延優先度フィルタは、同じ宛先を持つ複数のセ
ルの中から、いくつかの任意のセルを選択するために用
いられている。より明確に言えば、遅延優先度フィルタ
は、高い優先度と低い優先度をつけることによって、高
い優先度のセルが低い優先度のセルよりも、先に伝送さ
れることを可能にしている。
【００７２】遅延優先度フィルタ４８から出力された一
連のビットは、比較回路５０ａに入力される。比較回路
５０ａは、各エントリーのビットをその両隣のビットと
比較する。これは、図３に示されている論理和ゲート５
２及び排他的論理和ゲート５４により行われる。その結
果、出力ビットの内、１つのビットだけが１の値を持つ
ことになる。それは、その１の値を持つビットに対応す
るエントリーが選ばれて伝送されることを示している。
選択されたエントリーは、宛先ビットが１であるエント
リーの内、最もキューの先頭に近いエントリーである。
【００７３】図３に示すアクセラレータ６０は、検索を
スピードアップするために用いられる。その結果、１セ
ルサイクル内で全ての出力リンクの検索を順に行うこと
が可能となる。アクセラレータ６０は、通常一般的に用
いられている先読み回路であり、縦列接続される場合の
下位ステージからの入力６２と上位ステージへの出力６
４を備えている。下位ステージからの入力６２が０の時
は、下位ステージにおいて、指定された出力リンクに対
してエントリーが未選択であることを示している。下位
のステージからの入力６２が１の時は、下位のステージ
において、指定された出力リンクに対してエントリーが
選択されたことを示している。従って、下位ステージか
らの入力が１の時は、比較回路からの出力ビット５６
は、全て０になるように設計されている。上位ステージ
への出力６４は、下位ステージ又は自ステージにおい
て、エントリーが未選択の場合、０が出力される。下位
ステージ又は自ステージにおいて、エントリーが既に選
択された場合は、１が出力される。
【００７４】図４は、図３における従来の遅延優先度フ
ィルタ４８を、この発明のリニアサーチ回路７０で置き
換えたものである。この実施例においては、各キューエ
ントリー３９は、タグレジスタ７２により拡張されてい
る。タグレジスタ７２は、数値に対応する値を持ってお
り、その数値の大きさは、優先度を設定するために用い
られる。この発明においては、最も小さいタグ値を持つ
セルが最も高い優先度を与えられる。前述したように、
タグの持つ値によって優先度が設定される。この実施例
のリニアサーチ回路７０は、様々な選択機能を提供する
ことを目的として備えられている。これは、前述した図
３に示す遅延優先度フィルタ４８が単純化機能を目的と
していた点と大きく異なっている。多様な選択機能を提
供することにより、複数のスケジューリングアルゴリズ
ムの幅広い要求に柔軟に答えることができる。図４にお
いても、説明を簡単にするために、数百のキューエント
リーの中から、４つのエントリーを取り分けている。４
つのエントリーに対して、それぞれタグレジスタ７２と
比較器７４が対応している。各タグレジスタ７２は、図
１に示す入力処理部１６で計算された、セルエントリー
に対応するタグの値を示すバイナリーの数値を持ってい
る。この数値が比較器７４において、キューの中の直前
のタグの比較器の出力と比較される。比較結果により、
２つの数値の内、どちらが小さいかが決定される。この
順序付け処理の結果は、キューの中を順に次の比較器に
引き継がれる。
【００７５】また、この順序付け処理の結果は、一連の
ビットとして出力ライン７６に出力される。これらの一
連のビットの内、いずれかのビットに１がたっていれ
ば、それは第１に、対応するキューエントリーの宛先ビ
ットが１であることを示している。第２に、対応するキ
ューエントリーのタグ値がキューの中で選択された宛先
ビットが１である全てのキューエントリー中で、そのキ
ューエントリーのタグ値が最も小さいということも示し
ている。それ故、以下のことが分かる。１つは、リニア
サーチ回路７０及び比較回路５０ａ及びアクセラレータ
６０からなるリニアサーチ回路の出力ビット５６は、選
択された宛先ビットが１にセットされている全てのキュ
ーエントリーの中から、１つだけを選択するというこ
と、もう１つは、選択されたキューエントリーは、最小
のタグ値を持つということである。また、更に、もしも
２つ以上のキューエントリーが同一の最小のタグ値を持
ち、同一の宛先ビットを持っている場合に、キューの先
頭に最も近いエントリーが選択されるということにな
る。
【００７６】その結果、リニアサーチ回路７０により、
スケジューリングアルゴリズムが適当であろう思って採
用した方式に従って計算されたタグ値に基づいて、選択
プロセスを独自に構築する機会が提供される。即ち、リ
ニアサーチ回路７０は、タグ値が小さな値を持つセルを
先に出力するように設計されていているのであるから、
スケジューリングアルゴリズムが、先に出力したいセル
のタグ値を小さな値にするということさえ守れば、どの
ような方式でタグ値を決定してもよいことになる。この
ようにして、スケジューリングアルゴリズムの独自構築
が可能になる。
【００７７】特に、この発明においては、タグベースの
検索を実現するために、従来の遅延優先度フィルタ４８
を使用していない。遅延優先度フィルタ４８の代わり
に、キューの各エントリーに対応するタグレジスタを持
つ。また、各タグレジスタをキューの末尾に向かって他
のタグと比較し、最小値を持つタグを選択する比較器７
４を持つ。図５は、図４に示したリニアサーチ回路７０
の詳細を示す図である。図５に示すように、以下の例に
おいて、ｋを各タグレジスタのビット数とする。また、
Ｎをキューエントリーの総数とする。キューエントリー
ｉに対応するタグをタグｉとし、キューエントリーｉに
対応する比較器を比較器ｉとする。タグｉのタグ値をタ
グ値Ｔi とする。キューエントリーｉに対応する宛先ビ
ットを宛先ビットＤi とする。比較器ｉ＋１と比較器ｉ
の間を通っている一組のワイヤの出力値を出力値Ｍi+1
とする。比較器ｉの出力を、出力値Ｍi ，１ビットＣi
とする。この１ビットＣi は、宛先ビットＤi がセット
されているかどうかとともに、もし、セットされている
時は、更に、タグ値Ｔi が出力値Ｍi+1 以下であるかど
うかを示す。
【００７８】キュー最後尾エントリーからの出力値ＭN
は、宛先ビットＤN に１がたっている場合には、タグ値
ＴN の値にセットされる。また、宛先ビットＤN が０の
時は、２k −１（全ビット＝１）という値になる。比較
器ｉの一組のワイヤからの出力値Ｍi は、キューエント
リーｉからキューの最終（キューエントリーＮ）までの
エントリーの内、最小のタグ値を示す。また、ビットＣ
i は、宛先ビットＤiがセットされ、かつ、そのタグ値
Ｔi がキューエントリーｉからＮまでのキュー内にある
タグ値の中で最小値の場合、１に設定される。出力され
たビットＣi は、図２及び図３に示す従来例の回路の遅
延優先度フィルタの出力を置き換える。検索回路５０
は、単に、ビットＣi が１にセットされている最初のエ
ントリーを選択する。即ち、最小のタグ値を持つエント
リーを検索する。
【００７９】以下に、比較器の動作について、詳細に説
明する。タグレジスタの各ビットを比較する比較論理回
路を図６に示す。図６は、図５に示す比較器ｉのｊ番目
の比較論理回路を示している。図６のＴi ［ｊ］とラベ
ル付けされたボックス１３０は、ｉ番目のキューエント
リーのタグレジスタのｊ桁目（ｋ−１≧ｊ≧０）のビッ
トを示している。Ｍi+1 ［ｊ］とラベル付けされたワイ
ヤ１３２は、出力値Ｍi+1 のｊ番目のビットであり、キ
ュー最後尾方向にあるｉ＋１番目のキューエントリーの
比較器ｉ＋１からくるものである。また、Ｍi ［ｊ］と
ラベル付けされたワイヤ１３２は、出力値Ｍi のｊ番目
のビットであり、このエントリーからキューの先頭に向
かって出力されるものである。Ｃi［ｊ＋１］とラベル
付けされたワイヤ１３６と、Ｅi ［ｊ＋１］とラベル付
けされたワイヤ１３８は、ｉ番目のエントリーの比較器
ｉの（ｊ＋１）番目の比較論理回路からくるキャリービ
ットである。また、Ｃi ［ｊ］とラベル付けされたワイ
ヤ１４０とＥi ［ｊ］とラベル付けされたワイヤは、ｉ
番目のエントリーの比較器ｉのｊ番目の比較論理回路か
ら次の下位ビットの比較論理回路へ、即ち、（ｊ−１）
番目の比較論理回路へ出力されるキャリービットであ
る。
【００８０】２つのキャリービットとワイヤからの出力
値の意味は、以下のように定義される。 ここで、Ｎ＝キューのエントリー総数、Ｎ≧ｉ≧１，ｋ
−１≧ｊ≧０である。また、Ｔi ［（ｋ−１）・・・
ｊ］は、ｋビットで示されたタグ値Ｔi の上位ｋ−ｊビ
ットの値を意味する。
【００８１】式（１）により、Ｃi ［ｊ］＝１の時は、
宛先ビットＤi が１であり、かつ、エントリーｉのタグ
値Ｔi の上位ｋ−１ビットからｊビットまでの値がエン
トリーｉ＋１からエントリーＮまでの最小のタグ値Ｍ
i+1 の上位ｋ−１ビットからｊビットまでの値以下であ
ることを示している。Ｃi ［ｊ］＝０の時は、そのエン
トリーｉは、検索すべきエントリーでないことを示す。
Ｃi ［０］は、Ｃi として比較回路に出力される。ま
た、式（２）により、Ｅi ［ｊ］＝１の時は、Ｃ
i［ｊ］＝１の時で、かつ、タグ値Ｔi と出力値Ｍi+1
の上位ｋ−１ビットからｊビットまでの値が等しいこと
を示している。従って、Ｅi ［ｊ］＝１の時は、必ずＣ
i ［ｊ］＝１である。式（３）は、Ｍi ［（ｋ−１）・
・・ｊ］がエントリーｉからエントリーＮまでの最小の
タグ値の上位ｋ−１ビットからｊビットまでであること
を示している。
【００８２】図６に示す比較論理回路の機能は、図７に
示す論理値表で定義される。図７において、５行目のＣ
i ［ｊ＋１］とＥi ［ｊ＋１］の値は、ありえない組み
合わせである。図７を用いて、比較器が最小値を導き出
すことを以下に証明する。まず、最初に、以下のよう
に、初期設定をする。
【００８３】式（１）及び（２）は、全てのｉ及びｊ＝
ｋについて成り立つ。同様に、式（３）もｉ＝Ｎ及び全
てのｊ＝０，・・・，ｋ−１について成り立つ。次に、
帰納法で話を進めよう。０≦ｊ＜ｋ，１≦ｉ＜Ｎの時の
ビットＴi ［ｊ］を考えてみる。上記全ての値及び図６
のｉ，ｊ以外の値について、仮定を満足したとする。す
ると、この仮定により、 となる。また、図７に示す比較器のロジックテーブルの
１行目〜４行目の場合には、Ｃi ［ｊ＋１］＝０である
から、Ｄi ＝０であるか、または、 Ｔi ［（ｋ−１）・・・（ｊ＋１）］ ＞Ｍi+1 ［（ｋ−１）・・・（ｊ＋１）］ であり、１行目〜４行目の５列目に示すように、 Ｍi ［ｊ］＝Ｍi+1 ［ｊ］ となる。その結果、 Ｔi ［（ｋ−１）・・・ｊ］ ＞Ｍi+1 ［（ｋ−１）・・・ｊ］ 以上のように、式（１），（２）及び（３）は、成立す
る。５行目は、ありえないＣi ［ｊ＋１］とＥi ［ｊ＋
１］の組み合わせを示している。６行目〜９行目の場合
には、Ｃi ［ｊ＋１］＝１であり、Ｅi ［ｊ＋１］＝０
なので、Ｔi ［（ｋ−１）・・・（ｊ＋１）］が最小値
となり、 Ｔi ［（ｋ−１）・・・（ｊ＋１） ＜Ｍi+1 ［（ｋ−１）・・・（ｊ＋１）］ （７） 及び、６行目〜９行目の５列目に示すように、 Ｍi ［ｊ］＝Ｔi ［ｊ］ となる。その結果、以下の式が成立する。 Ｔi ［（ｋ−１）・・・ｊ］ ＜Ｍi+1 ［（ｋ−１）・・・ｊ］ また、６行目〜９行目の６列目と７列目に示すように、
Ｃi ［ｊ］とＥi ［ｊ］の値も対応してそれぞれ１及び
０にセットされる。更に、式（７）と帰納法の仮定によ
り、以下の式が成立する。 Ｍi ［（ｋ−１）・・・（ｊ＋１）］ ＝Ｔi ［（ｋ−１）・・・（ｊ＋１）］ その結果、ｍ＝ｉ，・・・，Ｎ，Ｄm ＝１に対して、以
下の式が真となる。 １０行目〜１３行目の場合には、Ｃi ［ｊ＋１］＝１、
かつ、Ｅi ［ｊ＋１］＝１なので、Ｔi ［（ｋ−１）・
・・（ｊ＋１）］は、今までの最小値Ｍi+1 ［（ｋ−
１）・・・（ｊ＋１）］と同じ値を示している。従っ
て、 Ｔi ［（ｋ−１）・・・（ｊ＋１）］ ＝Ｍi+1 ［（ｋ−１）・・・（ｊ＋１）］ となる。それ故、１０行目と１３行目に示すように、Ｔ
i ［ｊ］＝Ｍi+1 ［ｊ］の時、 Ｔi ［（ｋ−１）・・・ｊ］ ＝Ｍi+1 ［（ｋ−１）・・・ｊ］ となり、１１行目に示すように、Ｔi ［ｊ］＜Ｍi+1
［ｊ］の時、 Ｔi ［（ｋ−１）・・・ｊ］ ＜Ｍi+1 ［（ｋ−１）・・・ｊ］ となり、１２行目に示すように、Ｔi ［ｊ］＞Ｍi+1
［ｊ］の時、 Ｔi ［（ｋ−１）・・・ｊ］ ＝Ｍi+1 ［（ｋ−１）・・・ｊ］ となる。これにより、式（１），（２）及び（３）が導
かれる。以上のように、式（１），（２）及び（３）
は、キューに記憶されている全てのセルのタグに適合す
る。
【００８４】その結果、エントリーｉのタグ値Ｔi が最
小の時、 となる。以上のように、キューに対して高速なリニアサ
ーチが行われ、最小値を持つタグが選択される。
【００８５】この比較回路には、例えば、ワイヤ１３６
と１３８のように、２本のキャリーラインが必要であ
る。もし、キャリーラインが１本しかない場合には、図
７に示した７行目と８行目、１１行目と１２行目のよう
に、Ｔi ［ｊ］とＭi+1 ［ｊ］が異なる場合と、６行目
と９行目、１０行目と１３行目のように、Ｔi ［ｊ］と
Ｍi+1 ［ｊ］が同じ場合との差異を検出することができ
ない。
【００８６】この実施例のように、各キューエントリー
の間に使用されるの単純比較器をＶＬＳＩで構成しリニ
アサーチを行うには、１ビットにつき、およそ２５個の
トランジスタが必要である。そのため、タグが１６ビッ
トで構成されている場合には、約４００個のトランジス
タが必要となる。Ｍ1 ［０］の値を出力するためには、
宛先ビットからの情報が必要である。この情報は、Ｎ個
全てのキューエントリーのｋビットのタグの各ビットを
逐次、走査比較することによって得られる。この走査比
較は、配列の左上から右下に向けて順次実行される。１
つのキューエントリーに対する比較結果が出るまで待つ
ことなく、次のキューエントリーの第１ビット目の走査
比較を先に開始しても構わない。このように、各比較器
の走査比較を可能な限り早めに実行することにより、回
路内の最長パスの長さは、Ｎ＋ｋビットとなる。
【００８７】キュー検索部を０．８ｍのＣＭＯＳで構成
した場合、単純比較器は、およそ１６ビットのタグ比較
を５．５ナノセカンドで行う。このことから、キューに
１６個（Ｎ＝１６）のエントリーがあり、そのｊ番目の
ビットを走査比較するには、ほぼ同じ時間がかかること
が想定できる。例えば、１６ビット（ｋ＝１６）のタグ
を有する１２８エントリー（Ｎ＝１２８）を持つキュー
から最小値を持つエントリーを選択するには、以下の式
から概略４９．５ナノセカンドかかることが計算でき
る。 Ｎビットの走査比較時間＋ｋビットの走査比較時間＝
（１２８／１６）×５．５＋５．５＝４９．５
【００８８】上記４９．５ナノセカンドは非常に速い
が、この値は、キューエントリー数の増加により大きく
なってしまう。例えば、キューエントリーが２５６個で
あれば、１２８個の場合のほぼ倍の時間がかかる。
【００８９】以上のような、キューをリニアサーチする
方法には、時間がかかるという課題が残っている。この
課題を解決するために、図８に示すような二分木の形式
を用いてもよい。この改良例においては、一組（２つ）
のキューエントリーのタグの間に１つの比較器を備えて
いる。この比較器からの出力は、次の上位レベルの比較
器の片側に入力される。あるレベルの２台の比較器に対
応して、必ずその上位レベルに１台の比較器が配置され
ている。そのため、キューエントリーされているデータ
数Ｎ＝２n の時、比較器の数はリニアサーチの場合と同
じく、２n −１となる。図８においては、比較木（比較
に用いる木構造）は、３レベルの深さとなっている。
【００９０】図８は、この実施例のキューエントリーが
８個ある場合の比較器の配置を示す図である。モジュー
ル８０は、二分木形式で２つの比較器から構成されるモ
ジュールである。１つのキューエントリーからのタグレ
ジスタ８２と、隣接するキューエントリーからのタグレ
ジスタ８４が比較器８６に接続される。比較器８６にお
いて、入力された２つのタグの値が比較され、より小さ
い方のタグが選択される。選択されたタグに対応するキ
ューエントリーの宛先ビットが１にセットされる。もし
も、入力された２つのタグの値が同一である場合には、
比較器８６はキューの先頭により近い方のタグを選択す
る。このような構成を取れば、キューに記憶されている
全てのエントリーから最小の値を持つタグを選択するの
に必要な時間は、キュー内に記憶されているエントリー
の数のロガリズムに比例する。例えば、キューのエント
リーが１２８個であった場合には、最小値を持つタグを
選択するのに要する時間は、図４に示すリニアサーチ回
路を用いた場合に要する時間の１／２以下となる。 例１．エントリーの数＝８の時、ｌｏｇ2 ８＝３ 例２．エントリーの数＝１２８の時、ｌｏｇ2 １２８＝
７
【００９１】比較器８６の出力及び隣接する比較器８８
の出力は、上位レベルの比較器９０に入力される。比較
器９０の出力は、同様に、比較器９２に入力される。以
上のように、図８においては、比較器の配置が木構造を
なしている。
【００９２】各比較器からは、２つの出力ビットＣがＣ
´（図中、バーＣで示す）出力される。例えば、比較器
８６から出力された出力ビット９４は、論理積ゲート９
８に入力され、もう１つの出力ビット９６は、もう１つ
の論理積ゲート１００に入力され、最小値を持つタグの
選択に使用される。比較器からの出力ビットは、論理積
ゲート９８と１００で、それぞれ選択されたキューエン
トリーの対応する宛先ビットとＡＮＤ演算される。その
結果、論理積ゲートからの出力ビットが１である場合に
は、以下の３点を示している。第１に、対応するキュー
エントリーの宛先ビットに１の値が入っているというこ
と。第２に、その比較器に入力された複数のタグからな
るサブツリーの中で、最小のタグ値であるということ。
第３に、同一の最小タグ値を持つエントリーが２つ以上
あった場合に、そのエントリーがそれらの中で最も早く
キューイングされていること、即ち、キューの先頭に近
いことを示している。このように、比較器と対応する論
理積ゲートを木構造で配置したことにより、該当する宛
先ビットに１がたっており、かつ、キューの中で最小の
タグ値を持つ最もキューの先頭に近いキューエントリー
を選択することができる。
【００９３】比較器の動作についてより詳しく説明す
る。木構造の葉にあたる比較器は、ｋビットからなる２
つのタグレジスタの値を入力し、一組のｋビットからな
る出力を生成する。出力されたｋビットには、２つの入
力の内、より小さい方の値が示されている。また、木構
造の葉にあたる比較器の２つの出力ビットＣとＣ´の
内、出力ビットＣに着目してみると、比較器への２つの
入力の内、キューの先頭側からの入力値が、キューの最
後尾側からの入力値よりもより小さい時、或いは、同一
の値である時のみ、１がたつことになる。出力ビットＣ
が１の時は、出力ビットＣ´は０となる。出力ビットＣ
が０の時、出力ビットＣ´は１となる。
【００９４】各タグのタグ値は、宛先ビットの値を逆転
させた値でＯＲ演算される。これは、処理対象となって
いないタグレジスタが小さい値を持っている場合に、現
在処理中の宛先に関するタグレジスタの比較結果に、悪
影響を及ぼすことを防ぐことを目的としている。宛先ビ
ットが０の場合は、逆転させた値が１となり、この１と
タグレジスタの各ビットのＯＲ演算すると、全ビットが
１となり、最大のタグ値を示すことになる。このように
して、宛先ビットがのエントリーのタグ値を無視するこ
とができる。木構造のそれぞれのレベルにおいて、比較
器からの出力ｋビットは、図面では比較器の右側に示さ
れている。次の上位レベルの比較器の一方に入力され
る。比較器から出力されたＣ及びＣ´は、直前の下位レ
ベルで選択された出力ビットとＡＮＤ演算される。ここ
でＣ´は、Ｃの値を逆転させた値を示す。その結果、検
索の結果を示す出力ビットが最上位レベルにおいて出力
される。最終的に１にセットされた出力ビットは、１つ
だけになる。即ち、最小値のタグを持つキューエントリ
ーに対応するビットであり、かつ、キューの先頭に最も
近いキューエントリーに対応するビットである。宛先ビ
ットが１つも一致しない場合には、出力ビットが１つも
セットされない。
【００９５】Ｎをキューエントリー総数とすると、この
二分木からなる比較器の最長パスは、ｋ＊ｌｏｇ2 Ｎと
なる。前述したリニアサーチ回路と同様の考え方を用い
れば、１６ビットのタグを有する１２８個のキューエン
トリーから結果を選択するまでにかかる合計時間は、
５．５×ｌｏｇ2 １２８＝５．５×７＝３８．５ナノセ
カンドとなる。この時間は、キューのデータ数が２倍に
なっても、僅か５．５ナノセカンド延長されるだけであ
る。例えば、２５６個のキューエントリーから結果を選
択するまでにかかる合計時間は、５．５×ｌｏｇ2 ２５
６＝５．５×８＝４４．０ナノセカンドとなる。
【００９６】図８に示した回路においては、Ｎ＊ｌｏｇ
2 Ｎ個の論理積ゲートが、最小値のタグを持った出力を
選択するのに必要であった。この数は、各比較器からの
出力Ｃ及びＣ´を次の下位層レベルにフィードバックす
ることで、２＊Ｎ個まで減少させることが可能である。
図９は、２つの層からなる変形例を示す図である。図９
において、使用されている符号で図８と同一符号のもの
は相当部分である。今まで示してきた図の中では選択出
力が右向きであったのに対して、この図においては左向
きとなっている。この回路においては、図８に示した回
路よりもより多くの時間が必要となる。なぜならば、Ｃ
及びＣ´が選択出力に加えられなければならないからで
ある。この余分にかかる時間は、ｌｏｇ2 Ｎ個の論理積
回路の時間である。そして、論理積ゲート９８の出力
は、論理積ゲート１０２に接続され、論理積ゲート１０
０の出力は、論理積ゲート１０４にそれぞれ接続され
る。これらの論理積ゲートには、図に示すように、宛先
ビット１０６及び１０８もまた入力される。
【００９７】上で述べた二分木検索方法は、スピードが
速く、また、リニアサーチ方式と同じ数の比較器を使用
するものである。次に、より処理速度が速い変形例につ
いて述べる。図１０は、前述した２つの方式を組み合わ
せた構成図である。図において、キューは、Ｌ個のエン
トリーからなる複数のグループに分割されている。それ
ぞれのグループには、図４に示した形式のリニアサーチ
回路１２０が備えられている。これらのグループは、並
列に検索される。その結果、グループ毎にグループの中
で最小値のタグを持つエントリーを選択する。各グルー
プからの出力１２４は、追加のリニアサーチ回路１２６
に接続され、そこで全体の最小値のタグを持つグループ
が選択される。リニアサーチ回路１２６からの出力は、
ビットの集まりからなる。そのビットの集まりの中の１
ビットだけが、１の値を持っている。即ち、そのビット
は、全体の中で最小のタグを持つグループに対応してい
る。これらのビットの集まりは、次に論理積ゲート１２
８の配列に接続される。この論理積ゲート１２８は、リ
ニアサーチ回路１２０に対応している。リニアサーチ回
路１２０の各出力ビットは、リニアサーチ回路１２６の
出力ビットとＡＮＤ演算される。その結果、最終的に最
小値のタグを持ち、かつ、処理対象の宛先ビットに１が
たっているキューエントリーが選択される。
【００９８】以下に、より詳細に説明する。この結合方
式においては、Ｌ個のエントリーからなるグループが並
列して比較され、並列してリニアサーチ方式で比較され
る。そして、その結果が上位層のレベルで更に比較され
る。従って、各グループ毎にそのグループ内の最小値の
タグを持つｋビットの値を生成する。更に、Ｌ本の出力
ラインを生成する。木構造の中の末端でないグループの
出力ラインは、折り返され、次の下位層レベルのグルー
プの出力ラインとＡＮＤ演算される。それ故、葉に当た
るグループの出力ラインは、そのタグがそのグループ内
でも最小であり、更に全ての上位層レベルのグループ中
で最小である場合のみ１がセットされる。
【００９９】各グループの最長パスの長さは、ｋ＋Ｌで
ある。キューエントリー総数をＮとすると、グループ数
は、Ｎ／Ｌとなり、ｌｏｇL Ｎ個の階層数が存在する。
この場合、回路全体が最終結果を算出するまでの時間
は、｛１階層が結果を算出する時間＋出力時間｝×階層
数となり、（ｋ＋Ｌ＋１）＊ｌｏｇL Ｎに比例する。例
えば、１６ビット（ｋ＝１６）の比較器が５．５ナノセ
カンド必要とする場合、１６個のエントリー（Ｌ＝１
６）を持つ１つのグループは、およそｋビットの走査比
較時間＝５．５＋５．５＝２＊５．５＝１１ナノセカン
ドを検索に要することになる。１６2 個＝２５６個（Ｎ
＝２５６，Ｌ＝１６，１６グループ）のエントリーのキ
ューは、ｌｏｇL Ｎ＝ｌｏｇ16２５６＝２となり、この
数字（１１ナノセカンド）の倍だけの時間を必要とす
る。これは、約２２ナノセカンドである。また、木構造
の中で用いられる比較器の総数は、２n である。Ｌの値
に関わらず、比較器の総数は、およそ２n となる。
【０１００】より早い処理スピードを達成するために、
必要であれば、木構造をパイプライン化することも可能
である。だが、その場合には、回路もより複雑化すると
いう欠点も発生する。階層化された比較器の各階層レべ
ルは、パイプラインにおけるステージに相当する。第１
サイクルで第１の出力リンクに対応する一組の宛先ビッ
トが選択され、第１階層レベルの全ての比較器から第１
階層レベルの結果が形成される。形成された結果は、次
の第２階層レベルに出力される。そして、その次の第２
サイクルにおいて、第２の出力リンクに対応した新たな
一組の宛先ビットが第１階層レベルの比較器で選択され
る。一方、第２階層レベルの比較器では、第２サイクル
において、第１階層レベルの比較器からの出力、即ち、
直前のパイプラインステージからの出力が比較される。
ｌｏｇL Ｎ個のサイクルが経過した後、第１の出力リン
クに対応する選択出力ビットが結果として得られる。そ
れ以降のサイクルにおいては、１サイクル毎に各出力リ
ンクに対応する結果がその都度得られる。このようにし
て、１ＡＴＭセル時間よりも、はるかに短い時間で各宛
先の選択出力が得られる。
【０１０１】スケジューリングアルゴリズムをインプリ
メントするという観点から見ると、このキューイングシ
ステムにより提供されるタグベースの検索方法は、大変
柔軟性に富むものである。そして、スタティックなスケ
ジュール方法やダイナミックなスケジュール方法いずれ
にも幅広く対応して実現可能なものである。以下に具体
的に述べる。
【０１０２】単純優先度アルゴリズム及びレートモノト
ニックスケジューリングアルゴリズムにおいては、タグ
値はバーチャルチャネルにより静的に割り当てられる。
即ち、チャネルが設定されると、その優先度も決定され
る。そして、そのチャネルに到着するセルは全て同一の
タグ値を割り当てられる。より小さいタグは、優先度の
より高い優先度に対応しているので、スケジュールの際
に優遇される。タグベースの検索は、２k レベルの優先
度、或いは、レートリゾリューションをサポートする。
【０１０３】ほとんどのＡＴＭスイッチは、いくつかの
種類の優先度スケジューリングをサポートしている。だ
が、サポートされる優先度レベルの数は、非常に小さ
い。具体的には、およそ２レベルか４レベル位である。
今日では、同一のネットワーク環境において、多種多様
なタスクを柔軟にスケジューリングするために、かなり
多くの優先度レベルをサポートすることが必要であるこ
とが明らかになっている。特に、レートモノトニックア
ルゴリズムは、反復性のリアルタイムタスクをそのタス
クの反復の度数によって分類する。より高い度数を持つ
タスクは、より高い優先度を割り当てられる。多数の種
類のタスクをサポートするために充分なリゾリューショ
ンを持つことが望まれていた。
【０１０４】バーチャルクロックアルゴリズム及びウェ
イテッドフェアキューイングスケジューリングは、単純
なダイナミック・スケジューリング・アルゴリズムであ
る。セルがＡＴＭスイッチに到着すると、到着時間とバ
ーチャルチャネルの状態に基づいて、タグが計算され
る。同一のバーチャルチャネルの各セルは、異なるタグ
を付加される。セルがネットワークからどのようなサー
ビスを受けるかも、タグを計算する場合に用いられるア
ルゴリズム要素の１つである。
【０１０５】最早デッドラインファーストスケジューリ
ングアルゴリズムは、全てのスケジューリングアルゴリ
ズムの中で、最も一般的なものである。一連のリアルタ
イムタスクがいかなる方法によりスケジュールされよう
とも、それらのタスクは、最早デッドラインファースト
アルゴリズムにより、スケジュールされることが可能で
あるということが証明されている。バーチャルクロック
アルゴリズムやウェイテッドフェアキューイングアルゴ
リズムのように、最早デッドラインファーストアルゴリ
ズムもダイナミック・スケジューリング・アルゴリズム
である。このアルゴリズムによれば、タグ値は、各セル
の到着時間及びバーチャルチャネルの状態に基づいて計
算される。その結果、タグは、デッドライン値を持つ。
【０１０６】最後に、ラウンド・ロビン・アルゴリズム
は、ハードウェアで実現するよりも、ソフトウェアで実
現する方がより実現しやすいと考えられている典型的な
アルゴリズムである。このアルゴリズムを、この発明の
タグベースの検索で実現することが可能である。それ
は、そのアルゴリズムを他のダイナミック・スケジュー
リング・アルゴリズムと同様に取り扱うことにより可能
となる。そうすることによって、全てのバーチャルチャ
ネルに対して、１つのグローバルカウンタＲが保持され
る。グローバルカウンタＲの値は、処理されたラウンド
を記憶する。また、各バーチャルチャネルｖ毎に、その
バーチャルチャネルの最新の受信セルのラウンド番号を
示す値ｒv が保持される。新しいセルを受信すると、タ
グは以下のように設定される。 ｔａｇcell＝ｎｅｗ＿ｒv ＝ｍａｘ｛Ｒ，ｏｌｄ−ｒv ｝＋１
【０１０７】次に、セルは、このタグを付加されてキュ
ーに挿入される。セルをディスパッチ（発送）する時間
になると、最小値のタグが選択される。ラウンド・ロビ
ン・チャネルの選択されたセルのタグがグローバルカウ
ンタＲの値よりもより大きい場合、グローバルカウンタ
Ｒの値は、タグの値で書き換えられ更新される。
【０１０８】全てのダイナミック・スケジューリング・
アルゴリズムにおいて、タグは任意の実時間時計により
増加する要素であり、時としてタグ値の計算結果がｋ−
１ビットを超えることがある。その場合、キューの全て
のエントリーのタグ値は、ｋが充分な桁数を持っていれ
ば、タグレジスタの最上位ビット（ｋ番目）が１とな
る。それ以上のオーバフローを防ぐためには、単にこれ
らのビットの全てをリセットしてゼロにし、処理を続け
ればよい。これは、ロジカルクロック又はバーチャルク
ロックの時間を２k-1 ユニット毎に、２k-1 の値だけ進
めることに等しい。より詳しく述べると、キューに残っ
ている全てのエントリーのタグ値が２k-1を超え、新し
いタグの値もまた２k-1 よりも大きい時、全てのキュー
エントリーのタグレジスタの最上位ビットをリセットす
ることは、キューエントリーの順番を替えずに、キュー
にその時点で存在するタグ値及び以降キューに入ってく
るタグ値を２k-1 減少させる効果がある。
【０１０９】実際のネットワークにおいては、トラヒッ
クが何らかのパラメータにより保証された配信を要求し
た場合には、リアルタイムスケジューリングアルゴリズ
ムを使い、保証された配信を要求しないトラヒックにつ
いては、他の公平、かつ、最適と思われるスケジューリ
ングアルゴリズムを使うことが必要である。これは、タ
グの最上位ビットを使うことで、サポート可能である。
例えば、あるスイッチのバーチャルチャネルがＣ個のク
ラスに分割されているとする。また、各クラスは隣のク
ラスの優先度よりも、より高い優先度であるとする。こ
の時、クラスはタグの上位ｌｏｇ2 Ｃビットにエンコー
ドされる。最も優先度の高いクラスは、最小の値を持
つ。その結果、この発明のタグベース検索システムは、
常に最も高い優先度のクラスから、最小値のタグを持つ
キューエントリーを選択する。
【０１１０】以上のように、この発明のディジタル通信
ネットワーク用スイッチは、汎用のキューイングシステ
ムを利用する。このシステムは、該当するエントリーで
最小のタグを持つエントリーをキューから検索するとい
う考えに基づいている。このようなシステムでは、リア
ルタイムの保証を要求するアプリケーションや、オーデ
ィオデータ、ビデオデータのような連続性のあるメディ
アや、迅速な応答を要求するアプリケーションをサポー
トする幅広いクラスのスケジューリングアルゴリズムを
実現することが可能である。更に、１つのスイッチで同
時に多数のスケジューリングアルゴリズムを実現でき
る。それにより、様々な基準に従って、様々なクラスの
トラヒックをサポートできる。この発明は、プログラム
により実現してもよい。つまり、各入出力ポートに処理
速度の速いプログラム可能なマイクロプロセッサをそれ
ぞれ備え、このマイクロプロセッサ上で実行されるソフ
トウェアで、ＡＴＭセルに割り当てられたタグの計算方
法を実現してもよい。このシステムは、ＡＴＭネットワ
ークで種々のリサーチ及びプロトタイプ環境を柔軟に実
現する新しいレベルを築き上げる。また、システムをイ
ンプリメントする開発者をネットワークサービスに関す
る負荷から解放し、システムをインプリメントする開発
者をアプリケーションの仕様実現に集中させることがで
きるというメリットも得られる。
【０１１１】以上のように、この実施例においては、Ｆ
ＩＦＯアルゴリズム及びシンプルな優先度付け方式を含
む幅広いクラスのセル・スケジューリング・アルゴリズ
ムを実現するために、タグベースの検索を行うＡＴＭネ
ットワークについて説明した。このスイッチングシステ
ムにおいては、各セルはネットワークスイッチに到着す
ると、バイナリーの数値を持つタグを付加される。各セ
ルのタグは、そのセルが伝送されるバーチャルチャネ
ル、そのバーチャルチャネルのトラヒックのクラスのス
ケジューリングアルゴリズム、そのセル自身の特性等に
関連する情報を持っている。そして、セル、タグ及び宛
先情報が、伝送待ちのセルキューの末尾に入力される。
この実施例においては、キューは、ＶＬＳＩ回路で構成
されている。
【０１１２】スイッチが、特定の宛先にセルを伝送しよ
うとする時、キューに記憶されているすべてのセルを対
象に並列に検索が行われ、その宛先に一致する最小のタ
グ値を持つセルが選択される。選択されたセルは、キュ
ーから消去される。伝送され、キューの中に同一のタグ
を持つ複数のセルが存在する場合には、もっとも早くキ
ューに到着したセルが選択される。キュー検索部は、最
小のタグだけでなくセルが伝送される出力ポートも識別
する。以上のように、スイッチキューに記憶された各セ
ルには、バイナリーの数値を持つタグが付加される。そ
れにより、キューは、ある特定の宛先を持つセルの中
で、最小値のタグを持つセルを速やかに検索することが
可能になる。この構成を取れば、様々な特徴を持つネッ
トワークのトラヒックをサポートするほとんど全ての公
表されているスケジューリングアルゴリズムを実現でき
る。また、シビアなリアルタイムの要求にも応えられ、
連続性のあるメディアの伝送も可能で、迅速なレスポン
スも実現できる。更に、この構成を取れば、独自のスケ
ジューリング方式とアルゴリズムを持つ複数のトラヒッ
クのクラスを、１つのネットワーク内でサポートでき
る。
【０１１３】
【発明の効果】以上のように、この発明によれば、柔軟
性に富んだスケジューリングを行うことができる。ま
た、いろいろな種類のスケジューリングアルゴリズムを
採用することができる。
【０１１４】また、この発明によれば、宛先ビットのベ
クトルは、除去された形でセルが出力されるので、スイ
ッチングシステム内部で用いた宛先ビットのベクトルが
外部に出力されることはなく、スイッチングシステムの
インタフェースは、従来のスイッチングシステムと同様
であり、従来のシステムと互換性のあるシステムを提供
することができる。
【０１１５】また、この発明によれば、各種スケジュー
リングアルゴリズムを採用することができ、ユーザの要
求に応じた、或いは、各システムの要求に応じたスケジ
ューリングを行うことができる。
【０１１６】また、この発明によれば、タグという情報
を用いることにより優先度を持った処理を行うことがで
きる。
【０１１７】また、この発明によれば、レジスタの内部
に宛先ビットとタグを保持しているので、レジスタを参
照することにより、スケジューリングを行うことができ
る。
【０１１８】また、この発明によれば、サーチ手段がリ
ニアにタグをサーチしていくので、単純な方法により出
力すべきセルを検出することができる。
【０１１９】また、この発明によれば、サーチ手段が階
層的木構造を用いてタグをサーチするので、高速にセル
を検出することができる。
【０１２０】また、この発明によれば、スケジュール手
段がタグ手段と共通のキューとサーチ手段を備えること
により、優先度付けを行ったスイッチング処理を行うこ
とができる。
【０１２１】また、この発明によれば、リニアサーチ手
段を備えているので、タグを順番に比べることにより、
優先度の高いセルを検出することができる。
【０１２２】また、この発明によれば、ロガリズミック
サーチ手段を備えているので、優先度の高いセルを高速
に検索することができる。
【０１２３】また、この発明によれば、リニアサーチと
ロガリズミックサーチを任意に結合することができるの
で、柔軟な検索を行える。
【０１２４】また、この発明によれば、タグレジスタと
比較器を備えているので、タグの値を比較器により順番
に比較することにより、優先度の高いセルを出力するこ
とができる。
【０１２５】また、この発明によれば、比較器の出力の
中に最小のタグ値を示す特定ビットを設けているので、
この特定ビットを利用することにより、最小値を持つタ
グを検出することができる。
【０１２６】また、この発明によれば、比較器は、各タ
グに対して追加の入力ビットを備えているので、この追
加の入力ビットにより、比較対象となるタグであるかど
うかを判定することができる。
【０１２７】また、この発明によれば、追加の入力ビッ
トを備えているので、この追加の入力ビットに宛先ビッ
トの情報を与えることにより、対応するタグが比較対象
となるタグであるかどうかを判定することができる。
【０１２８】また、この発明によれば、最小のタグ値を
持つセルが２以上存在する場合でも、先着したセルを先
に出力する。従って、同一の優先度を持つセルが存在す
る場合には、セルの逆転現象は生じない。
【０１２９】また、この発明によれば、階層的木構造を
用いてサーチするので、高速サーチを行うことができ
る。
【０１３０】また、この発明によれば、比較器からの比
較ビットと宛先ビットをＡＮＤゲートによりチェックし
ているので、最終的にただ１つのＡＮＤゲートが有意な
出力を有するように構成できる。このように、比較ビッ
トとＡＮＤゲートの採用により、簡単な回路により、優
先度を持ったスケジューリングを行える。
【０１３１】また、この発明によれば、ＡＮＤゲートに
より宛先ビットの検査と最小のタグ値があるかどうかの
検査が行われるので、最終的に宛先ビットがオンであ
り、最小のタグ値を持つセルを検出することができる。
【０１３２】また、この発明によれば、２以上のセルが
最小のタグ値を有する場合に、先着のセルを選択するの
で、同じ優先度を持つセルの逆転が生じない。
【０１３３】また、この発明によれば、階層的木構造を
持ったサーチを行う場合に、キューの末尾よりもキュー
の先頭方向にあるものを優先して出力するので、先入
れ、先出し方式を保ちながら、優先度を持ったスケジュ
ーリングを行うことができる。
【０１３４】また、この発明によれば、ＡＮＤゲートの
数を減少させた回路を用いてスケジューリング処理を行
うことができる。
【図面の簡単な説明】
【図１】 この発明のＡＴＭスイッチの論理的構造を示
すブロック図である。
【図２】 従来例のキュー検索システムを示すブロック
図である。
【図３】 図２に示す従来例の遅延優先度フィルタを備
えた宛先ビットと検索回路の詳細図である。
【図４】 この発明の実施例の計算されたタグ値を選択
するリニアサーチ手段に４個のキューエントリーを描い
た概要図である。
【図５】 この発明のリニアサーチ手段の詳細図であ
る。
【図６】 この発明のリニアサーチ手段の一要素のブロ
ック図である。
【図７】 この発明の実施例の比較器の論理値の定義図
である。
【図８】 この発明の実施例のロガリズミックサーチ手
段に８個のキューエントリーを描いた概要図である。
【図９】 この発明の実施例のロガリズミックサーチ手
段の概要図である。
【図１０】 この発明の実施例のリニアサーチ手段とロ
ガリズミックサーチ手段を結合させたブロック図であ
る。
【符号の説明】
１０ ＡＴＭスイッチ、１４ 入力リンク、１６ 入力
処理部、１８ キュー検索部、２０ セルバッファメモ
リ、２２ 制御部、２４ 出力処理部、３５アドレスフ
ィールド、３７ 優先度ビット、４１ 宛先フィール
ド、４２ 宛先ビット、５０ａ 比較回路、５６ 出力
ビット、７２，８２，８４ タグレジスタ、７４，８
６，８８，９０，９２ 比較器。
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０４Ｑ 3/52 １０１ Ｚ 9566−5Ｇ 9466−5Ｋ Ｈ０４Ｌ 11/20 １０２ Ｚ

Claims (22)

    【特許請求の範囲】
  1. 【請求項１】 複数の入力リンクと複数の出力リンクを
    持ち、各入力リンクによりネットワーク内の１以上の宛
    先を示す宛先情報を含むヘッダフィールドとデータとを
    格納したセルを受信するスイッチと、 上記ヘッダフィールドの宛先情報を、各ビットが各出力
    リンクに対応しておりそのビットが有意状態である時そ
    のセルが最終宛先に到着するようにそのビットに対応す
    る出力リンクに対してそのセルを出力することを示して
    いる宛先ビットのベクトルに変換する変換手段と、 各セルに対して、上記宛先ビットのベクトルを付加する
    ベクトル付加手段と、 上記ベクトルを付加されたセルを１つ以上の出力リンク
    に接続する接続手段とを備え、 上記接続手段は、上記ベクトルを付加されたセルを到着
    順に格納するキューイング手段と、キューイング手段に
    格納されたセルの中から到着順とは異なる順に各出力リ
    ンクに対して各出力リンクに対応する宛先ビットが有意
    状態のセルを選択する選択手段とを備え、 上記選択手段は、セルの出力をスケジュールするスケジ
    ュール手段を有し、上記スケジュール手段は、選択順を
    決定するアルゴリズムを記憶する手段と、 スイッチの動作に先だってそのアルゴリズムを設定する
    手段と、 スイッチの動作中にそのアルゴリズムを再設定する手段
    と、 上記各出力リンクに対してセル送信時間内に上記アルゴ
    リズムを実行する手段を有しており、 上記スイッチは、更に、上記出力リンクに選択したセル
    を出力する出力手段を備えたことを特徴とするディジタ
    ル通信ネットワーク用のスイッチングシステム。
  2. 【請求項２】 上記出力手段は、上記ベクトルが除去さ
    れたセルを出力することを特徴とする請求項１記載のス
    イッチングシステム。
  3. 【請求項３】 上記アルゴリズムは、ダイナミック・プ
    ライオリティ・スケジューリング・アルゴリズムと、ス
    タティック・プライオリティ・スケジューリング・アル
    ゴリズムと、ラウンド・ロビン・アルゴリズムと、これ
    らの組み合わせのいずれかから選択されることを特徴と
    する請求項１記載のスイッチングシステム。
  4. 【請求項４】 上記スケジュール手段は、各出力リンク
    にセルを出力する順番を決定するために設定されたスケ
    ジューリングアルゴリズムに基づいて、キューイング手
    段の中に格納されたセルの出力順序を示す値をタグ値と
    して計算し、このタグ値を有するタグをセルに付加する
    タグ付加手段を有し、上記選択手段は、タグ値と宛先ビ
    ットの値に基づいて、キューイング手段の中に格納され
    たセルをサーチするサーチ手段とを備え、選択手段は、
    各出力リンクに対応する宛先ビットの値が有意状態であ
    るセルの中で最も小さいタグ値を持つセルをサーチして
    選択し、もし、最も小さいタグ値を持つセルが２以上存
    在する場合に、先に到着したセルを選択することを特徴
    とする請求項１記載のスイッチングシステム。
  5. 【請求項５】 上記キューイング手段は、先頭から末尾
    に至る複数のレジスタからなるＦＩＦＯ回路を備え、各
    レジスタは、出力を待っているセルを示すものであり、
    各レジスタは、上記宛先ビットのベクトルとタグ値のバ
    イナリーコードを保持し、各レジスタは、先頭から末尾
    の方向でセルの到着順を示していることを特徴とする請
    求項４記載のスイッチングシステム。
  6. 【請求項６】 上記サーチ手段は、上記レジスタの数と
    同じ数の複数の比較回路を備え、各比較回路は、各レジ
    スタに対応して設けられ、各比較回路は、対応したレジ
    スタのタグ値と末尾側にある次のレジスタに対応した比
    較回路からの出力値を比較するようにリニアに配置さ
    れ、各比較回路は、対応するレジスタのタグ値が末尾側
    にある次に比較回路から出力されたタグ値より小さい場
    合であって、かつ、選択した出力リンクに対する宛先ビ
    ットが有意状態である場合に、出力ビットをオンにする
    ことにより、上記比較回路は、選択した出力リンクに対
    して最小のタグ値を伝搬させ、待ち行列の中からセルを
    選択することを特徴とする請求項５記載のスイッチング
    システム。
  7. 【請求項７】 上記サーチ手段は、上記レジスタの数の
    半分に当たる複数の比較回路と追加の比較回路を備え、
    上記比較回路を階層的に配置し、ルートと枝と葉を持つ
    ツリーを構成し、葉と枝のサブセットによりサブツリー
    を構成し、葉に配置された各比較回路は、２つの隣り合
    うレジスタのタグ値を比較して小さいタグ値を有するレ
    ジスタを識別し、上記追加の比較回路は、２つのサブツ
    リーからのタグ値を比較し、選択した出力リンクに対し
    て、最小のタグ値を持つレジスタが存在しているサブツ
    リーを識別し、上記ツリーは、選択した出力リンクに対
    して、最小のタグ値を伝搬することを特徴とする請求項
    ５記載のスイッチングシステム。
  8. 【請求項８】 複数の出力リンクと出力リンクを示すア
    ドレスを含んだセルを受信する複数の入力リンクと、 上記アドレスを宛先ビットに変換する変換手段と、 上記入力リンクのセルを少なくとも１つの出力リンクに
    接続する接続手段とを備え、 上記接続手段は、入力リンクから出力リンクへセルの出
    力をスケジュールするスケジュール手段を備え、 スケジュール手段は、 各出力リンクにセルを出力する順番を決定するために、
    予め設定されたスケジューリングアルゴリズムに基づい
    て、どのセルを出力すべきかを示す値を生成し、生成し
    た値をタグ値として有するタグをセルに付加するタグ手
    段と、 共通キューと、 上記共通キューに、各セルに対して宛先ビットとタグ値
    を挿入する手段と、 上記宛先ビットとタグ値に基づいて、上記共通キューか
    ら、対応している宛先の中から最小のタグ値を持つセル
    をサーチするサーチ手段と、 宛先に対応した出力リンクに対して最小のタグ値を持つ
    セルを出力する出力手段とを備えたことを特徴とするデ
    ィジタル通信ネットワーク用のスイッチングシステム。
  9. 【請求項９】 上記サーチ手段は、最小のタグ値をシリ
    アルに評価していくリニアサーチ手段を有していること
    を特徴とする請求項８記載のスイッチングシステム。
  10. 【請求項１０】 上記サーチ手段は、木構造を用いて同
    時に複数対のセルを評価していくロガリズミックサーチ
    手段を有していることを特徴とする請求項８記載のスイ
    ッチングシステム。
  11. 【請求項１１】 上記サーチ手段は、リニアサーチ手段
    とロガリズミックサーチ手段を結合したサーチ手段を有
    していることを特徴とする請求項８記載のスイッチング
    システム。
  12. 【請求項１２】 上記タグ手段は、 先頭から末尾までのキューを形成するように配置された
    一連のタグレジスタと、 複数の比較器と、 上記タグレジスタと比較器を接続する接続手段と、 上記セルを対応するタグレジスタにより識別できるよう
    に記憶する記憶手段と、 記憶されたセルのタグ値をタグレジスタに設定する設定
    手段とを備え、 上記比較器は、タグレジスタのタグ値と１つ前の比較器
    からの出力値を比較して小さい方の値を決定するととも
    に、 小さい方の値と宛先ビットを出力する出力手段と、 小さい方の値と宛先ビットに基づいて、記憶されたセル
    を識別する識別手段とを備えたことを特徴とする請求項
    ８記載のスイッチングシステム。
  13. 【請求項１３】 上記比較器は、一連のビットから構成
    された出力を持ち、この一連のビットの中に、宛先ビッ
    トが有意状態であり、同じ宛先ビットが有意状態である
    キュー中の他のセルのタグ値よりも小さいタグ値を持つ
    ことを示す特定ビットを有しており、 各比較器は、各タグ値とキューの末尾方向にあるタグの
    最小値とを比較することにより、宛先別に各セルのプラ
    イオリティを設定することを特徴とする請求項１２記載
    のスイッチングシステム。
  14. 【請求項１４】 上記比較器は、２つのタグ値を比較す
    る手段と、小さい方の値を出力する手段とを有し、１つ
    のタグ値に対して１つの追加の入力ビットを備え、上記
    比較器の出力は、比較対象となるタグ値を示す追加の入
    力ビットにより条件付けられていることを特徴とする請
    求項１２記載のスイッチングシステム。
  15. 【請求項１５】 上記追加の入力ビットは、宛先ビット
    が有意状態になっているセルのタグ値を特定するもので
    あることを特徴とする請求項１４記載のスイッチングシ
    ステム。
  16. 【請求項１６】 上記スイッチングシステムは、更に、
    最小のタグ値を持つセルが２以上存在する場合に、キュ
    ーの先頭に近いセルを選択する手段を備えたことを特徴
    とする請求項１２記載のスイッチングシステム。
  17. 【請求項１７】 上記タグ手段は、枝を経由してルート
    に連結された葉を持った階層的木構造を有し、各枝は、
    一対のタグレジスタと隣り合うタグレジスタの間に設け
    られたタグレジスタ用比較器と、２つのタグレジスタ用
    比較器からの出力を入力する追加の比較器を有してお
    り、上記追加の比較器は、宛先ビットが有意状態になっ
    ており、小さい方のタグ値を持つタグレジスタに対応す
    るセルを識別する手段を有していることを特徴とする請
    求項８記載のスイッチングシステム。
  18. 【請求項１８】 上記タグレジスタ用比較器は、小さい
    方のタグ値と２つの比較ビットを出力し、２つの比較ビ
    ットの内、一方の比較ビットは一方のセルが小さい方の
    タグ値を持っていることを示し、２つの比較ビットの
    内、他方の比較ビットは他方のセルが小さい方のタグ値
    を持っていることを示すものであり、上記選択手段は、
    小さい方のタグ値を持っているセルを識別するために、
    宛先ビットと比較ビットを入力する複数のＡＮＤゲート
    を有し、複数のＡＮＤゲートは、ルートにおいてただ１
    つのＡＮＤゲートが有意な出力を有するように構成され
    ており、このＡＮＤゲートの有意な出力により出力リン
    クに出力されるセルを示すことを特徴とする請求項１７
    記載のスイッチングシステム。
  19. 【請求項１９】 上記ＡＮＤゲートは、そのＡＮＤゲー
    トに対応したセルが適切な宛先ビットを有しているかを
    判定するために用いられるものであり、上記タグレジス
    タ用比較器は、異なるＡＮＤゲートへ接続された出力ビ
    ットを有し、このタグレジスタ用比較器からの出力ビッ
    トは、対応するセルの宛先ビットとＡＮＤを取られ、そ
    の結果の出力が有意状態である場合は、対応するセルが
    宛先ビットが有意状態であり、最小のタグ値を持つセル
    であることを示すことを特徴とする請求項１８記載のス
    イッチングシステム。
  20. 【請求項２０】 上記スイッチングシステムは、更に、
    ２以上のセルが最小のタグ値を有する場合、先着のセル
    を識別する手段を有することを特徴とする請求項１９記
    載のスイッチングシステム。
  21. 【請求項２１】 上記タグレジスタ用比較器は、先頭と
    末尾を持つキューを定義し、上記追加の比較器は、２入
    力から小さい値を出力するとともに、キューの先頭方向
    にある２入力の値がキューの末尾方向にある２入力の値
    以下である場合に、有意状態を出力することを特徴とす
    る請求項１７記載のスイッチングシステム。
  22. 【請求項２２】 上記スイッチングシステムは、更に、
    上記木構造のルート方向への上位層レベルにおいて、下
    位層レベルのどの枝が小さい方のタグ値を有しているか
    決定することにより小さい方のタグ値を有する枝を識別
    する識別手段を有し、上記識別手段は、各タグに対応し
    てそのタグの宛先ビットとそのタグが最小のタグ値を有
    することを示すビットとのＡＮＤを取るためのＡＮＤゲ
    ートを有していることを特徴とする請求項１７記載のス
    イッチングシステム。
JP10390895A 1994-04-28 1995-04-27 スイッチングシステム Pending JPH0856230A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/234,385 US5455825A (en) 1994-04-28 1994-04-28 Tag-based scheduling system for digital communication switch
US08/234385 1994-04-28

Publications (1)

Publication Number Publication Date
JPH0856230A true JPH0856230A (ja) 1996-02-27

Family

ID=22881169

Family Applications (1)

Application Number Title Priority Date Filing Date
JP10390895A Pending JPH0856230A (ja) 1994-04-28 1995-04-27 スイッチングシステム

Country Status (2)

Country Link
US (1) US5455825A (ja)
JP (1) JPH0856230A (ja)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004242334A (ja) * 2003-02-07 2004-08-26 Fujitsu Ltd 高速交換環境でマルチキャストするシステム、方法及び論理
US6810038B1 (en) 1999-04-02 2004-10-26 Nec Corporation Switch, scheduler thereof, and switch scheduling method
US6882655B1 (en) 1999-05-13 2005-04-19 Nec Corporation Switch and input port thereof
US7336648B1 (en) 2000-01-11 2008-02-26 Fujitsu Limited Label switching system
JP2010035245A (ja) * 2003-02-07 2010-02-12 Fujitsu Ltd 高速交換環境でマルチキャスティングするシステム、方法及び論理
JP2017525079A (ja) * 2014-06-13 2017-08-31 ブル・エス・アー・エス リスト内でのアイテム一致の検索

Families Citing this family (76)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0690596B1 (en) * 1994-06-28 2002-05-15 Hewlett-Packard Company, A Delaware Corporation Method and apparatus for scheduling the transmission of cells of guaranteed-bandwidth virtual channels
DE69434329T2 (de) * 1994-08-31 2006-03-09 Hewlett-Packard Development Co., L.P., Houston Verfahren und Vorrichtung zur Regulierung von Zellentransmissionen über virtuelle Kanäle
US5638538A (en) * 1995-01-13 1997-06-10 Digital Equipment Corporation Turbotable: apparatus for directing address and commands between multiple consumers on a node coupled to a pipelined system bus
US5570360A (en) * 1995-03-20 1996-10-29 Stratacom, Inc. Method and apparatus for implementing communication service contract using cell arrival information
JP3133234B2 (ja) * 1995-07-13 2001-02-05 株式会社東芝 Ａｔｍスイッチのアドレス生成回路
JP3103298B2 (ja) * 1995-07-17 2000-10-30 株式会社東芝 Ａｔｍスイッチのアドレス生成回路
WO1997004542A2 (en) * 1995-07-19 1997-02-06 Fujitsu Network Communications, Inc Multipoint-to-point arbitration in a network switch
US5909427A (en) 1995-07-19 1999-06-01 Fujitsu Network Communications, Inc. Redundant switch system and method of operation
US5898671A (en) 1995-09-14 1999-04-27 Fujitsu Network Communications, Inc. Transmitter controlled flow control for buffer allocation in wide area ATM networks
JP2737726B2 (ja) * 1995-11-20 1998-04-08 日本電気株式会社 バッファ制御装置
US5802448A (en) * 1995-12-14 1998-09-01 Time Warner Entertainment Co., L.P. Method and apparatus for processing requests for interactive applications based on system resources
US5822676A (en) * 1995-12-14 1998-10-13 Time Warner Entertainment Co. L.P. Digital serialization of program events
US5805154A (en) * 1995-12-14 1998-09-08 Time Warner Entertainment Co. L.P. Integrated broadcast application with broadcast portion having option display for access to on demand portion
US5995134A (en) * 1995-12-14 1999-11-30 Time Warner Cable Method and apparatus for enticing a passive television viewer by automatically playing promotional presentations of selectable options in response to the viewer's inactivity
US5818840A (en) * 1995-12-14 1998-10-06 Time Warner Entertainment Co. L.P. Asymmetric ATM switch
US5819036A (en) * 1995-12-14 1998-10-06 Time Warner Cable Method for message addressing in a full service network
US5671217A (en) * 1995-12-14 1997-09-23 Time Warner Entertainment Co. L.P. Scalable communications network employing shared logical nodes
US6340987B1 (en) 1995-12-14 2002-01-22 Time Warner Entertainment Company L.P. Method and apparatus for masking latency in an interactive television network
US5822530A (en) * 1995-12-14 1998-10-13 Time Warner Entertainment Co. L.P. Method and apparatus for processing requests for video on demand versions of interactive applications
US6044396A (en) * 1995-12-14 2000-03-28 Time Warner Cable, A Division Of Time Warner Entertainment Company, L.P. Method and apparatus for utilizing the available bit rate in a constrained variable bit rate channel
US5771435A (en) * 1995-12-14 1998-06-23 Time Warner Entertainment Co. L.P. Method and apparatus for processing requests for video presentations of interactive applications in which VOD functionality is provided during NVOD presentations
US5774458A (en) * 1995-12-14 1998-06-30 Time Warner Cable Multiplex amplifiers for two-way communications in a full-service network
US5797010A (en) * 1995-12-22 1998-08-18 Time Warner Cable Multiple run-time execution environment support in a set-top processor
GB2308959A (en) * 1995-12-29 1997-07-09 Ericsson Telefon Ab L M Data switching apparatus with fair queuing
JP2000517488A (ja) 1996-01-16 2000-12-26 フジツウ ネットワーク コミュニケーションズ，インコーポレイテッド Ａｔｍ網用の信頼性と柔軟性のあるマルチキャスト機構
DE19617816B4 (de) * 1996-05-03 2004-09-09 Siemens Ag Verfahren zum optimierten Übertragen von ATM-Zellen über Verbindungsabschnitte
US5732087A (en) * 1996-05-10 1998-03-24 Mitsubishi Electric Information Technology Center America, Inc. ATM local area network switch with dual queues
DE19634492B4 (de) * 1996-08-26 2004-10-14 Siemens Ag Verfahren zum optimierten Übertragen von ATM-Zellen über Verbindungsabschnitte
US5748905A (en) 1996-08-30 1998-05-05 Fujitsu Network Communications, Inc. Frame classification using classification keys
US5894481A (en) * 1996-09-11 1999-04-13 Mcdata Corporation Fiber channel switch employing distributed queuing
US6188690B1 (en) * 1996-12-12 2001-02-13 Pmc-Sierra, Inc. Method and apparatus for high speed, scalable communication system
US6098109A (en) * 1996-12-30 2000-08-01 Compaq Computer Corporation Programmable arbitration system for determining priority of the ports of a network switch
US6487212B1 (en) * 1997-02-14 2002-11-26 Advanced Micro Devices, Inc. Queuing structure and method for prioritization of frames in a network switch
EP0972379A4 (en) * 1997-04-04 2000-07-05 Ascend Communications Inc EXTREMELY FAST PACKET PROGRAMMING METHOD AND DEVICE
US5996013A (en) * 1997-04-30 1999-11-30 International Business Machines Corporation Method and apparatus for resource allocation with guarantees
US6088359A (en) * 1997-07-11 2000-07-11 Telefonaktiebolaget Lm Ericsson ABR server
US5963553A (en) * 1997-07-11 1999-10-05 Telefonaktiebolaget Lm Ericsson Handling ATM multicast cells
US6034958A (en) * 1997-07-11 2000-03-07 Telefonaktiebolaget Lm Ericsson VP/VC lookup function
US6154459A (en) * 1997-07-11 2000-11-28 Telefonaktiebolaget Lm Ericsson Data shaper for ATM traffic
US6185209B1 (en) 1997-07-11 2001-02-06 Telefonaktiebolaget Lm Ericsson VC merging for ATM switch
US6208661B1 (en) 1998-01-07 2001-03-27 International Business Machines Corporation Variable resolution scheduler for virtual channel communication devices
JP3077677B2 (ja) * 1998-07-14 2000-08-14 日本電気株式会社 品質保証ノード装置
WO2000010281A2 (en) * 1998-08-17 2000-02-24 Vitesse Semiconductor Corporation Network traffic manager
US6735190B1 (en) 1998-10-21 2004-05-11 Lucent Technologies Inc. Packet transport method device utilizing header removal fields
US6408001B1 (en) 1998-10-21 2002-06-18 Lucent Technologies Inc. Method for determining label assignments for a router
US6728210B1 (en) 1998-12-21 2004-04-27 Nec America, Inc. Multi-logical access for a serial data link
US6625160B1 (en) * 1999-07-02 2003-09-23 Cisco Technology, Inc. Minimum bandwidth guarantee for cross-point buffer switch
DE19941851C2 (de) * 1999-09-02 2003-04-10 Infineon Technologies Ag Zellkonfliktauflösungseinheit für eine Einrichtung zur Vermittlung einer Mehrzahl von paket-orientierten Signalen
US6891834B1 (en) * 1999-09-09 2005-05-10 Avici Systems Apparatus and method for packet scheduling
US6717951B2 (en) * 1999-12-29 2004-04-06 Intel Corporation Method and apparatus for determining priority of network packets
US6931424B1 (en) * 2000-03-21 2005-08-16 Alantro Communications, Inc. Storage efficient minimization logic
US6775271B1 (en) * 2000-05-17 2004-08-10 Intel Corporation Switching system and method for communicating information at a customer premises
US7266123B1 (en) * 2000-05-17 2007-09-04 Intel Corporation System and method for prioritizing and communicating subscriber voice and data information
US7140022B2 (en) * 2000-06-02 2006-11-21 Honeywell International Inc. Method and apparatus for slack stealing with dynamic threads
US6968392B1 (en) * 2000-06-29 2005-11-22 Cisco Technology, Inc. Method and apparatus providing improved statistics collection for high bandwidth interfaces supporting multiple connections
KR100382144B1 (ko) * 2000-07-31 2003-05-01 주식회사 케이티 입출력버퍼형 스위치의 셀 시지연 보상방법
US6836475B2 (en) * 2000-12-01 2004-12-28 Nokia Corporation Method and apparatus for traffic shaping for IP router queues/egress
US20020110094A1 (en) * 2001-02-13 2002-08-15 Reddy Naveen S. Spot beam hopping packet scheduler system
WO2002065709A1 (en) * 2001-02-14 2002-08-22 Kawasaki Microelectronics, Inc. Network switching device
US7382727B2 (en) * 2001-02-21 2008-06-03 Cisco Technology, Inc. System and method for asymmetrical bandwidth management
US7072300B1 (en) * 2001-03-23 2006-07-04 Advanced Micro Devices, Inc. Action tag generation within a network based on priority or differential services information
US6901052B2 (en) 2001-05-04 2005-05-31 Slt Logic Llc System and method for policing multiple data flows and multi-protocol data flows
US7042848B2 (en) * 2001-05-04 2006-05-09 Slt Logic Llc System and method for hierarchical policing of flows and subflows of a data stream
US6904057B2 (en) * 2001-05-04 2005-06-07 Slt Logic Llc Method and apparatus for providing multi-protocol, multi-stage, real-time frame classification
US7151744B2 (en) * 2001-09-21 2006-12-19 Slt Logic Llc Multi-service queuing method and apparatus that provides exhaustive arbitration, load balancing, and support for rapid port failover
US7099275B2 (en) * 2001-09-21 2006-08-29 Slt Logic Llc Programmable multi-service queue scheduler
US7301906B2 (en) 2001-12-17 2007-11-27 Lsi Corporation Methods and structures for improved buffer management and dynamic adaption of flow control status in high-speed communication networks
US20040160971A1 (en) * 2002-11-27 2004-08-19 Edward Krause Apparatus and method for dynamic channel mapping and optimized scheduling of data packets
JP2005198204A (ja) * 2004-01-09 2005-07-21 Pioneer Electronic Corp 情報配信表示システムおよび情報配信表示方法
US20060245358A1 (en) * 2005-04-29 2006-11-02 Beverly Harlan T Acceleration of data packet transmission
US8170041B1 (en) * 2005-09-14 2012-05-01 Sandia Corporation Message passing with parallel queue traversal
EP1953959A1 (en) * 2007-02-01 2008-08-06 British Telecommunications Public Limited Company Data communication
US8165033B1 (en) 2007-08-30 2012-04-24 Altera Corporation Method and apparatus for performing generalized processor sharing scheduling
DE102011009518B4 (de) * 2011-01-26 2013-09-12 Ruprecht-Karls-Universität Heidelberg Schaltungsanordnung für Verbindungsschnittstelle
CN109426650B (zh) * 2017-08-28 2023-07-18 华为技术有限公司 处理器和处理标签的方法
US10776185B2 (en) 2018-12-10 2020-09-15 International Business Machines Corporation Messaging software management for network devices supporting hardware tag matching

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH03201641A (ja) * 1989-12-27 1991-09-03 Toshiba Corp 通信パケットの優先制御方式

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6810038B1 (en) 1999-04-02 2004-10-26 Nec Corporation Switch, scheduler thereof, and switch scheduling method
US6882655B1 (en) 1999-05-13 2005-04-19 Nec Corporation Switch and input port thereof
US7336648B1 (en) 2000-01-11 2008-02-26 Fujitsu Limited Label switching system
JP2004242334A (ja) * 2003-02-07 2004-08-26 Fujitsu Ltd 高速交換環境でマルチキャストするシステム、方法及び論理
JP2010035245A (ja) * 2003-02-07 2010-02-12 Fujitsu Ltd 高速交換環境でマルチキャスティングするシステム、方法及び論理
JP2017525079A (ja) * 2014-06-13 2017-08-31 ブル・エス・アー・エス リスト内でのアイテム一致の検索

Also Published As

Publication number Publication date
US5455825A (en) 1995-10-03

Similar Documents

Publication Publication Date Title
US5455825A (en) Tag-based scheduling system for digital communication switch
Tamir et al. Dynamically-allocated multi-queue buffers for VLSI communication switches
Katevenis et al. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip
US4630258A (en) Packet switched multiport memory NXM switch node and processing method
Dally Virtual-channel flow control
US6529478B1 (en) Pass/drop apparatus and method for network switching node
Moon et al. Scalable hardware priority queue architectures for high-speed packet switches
US4623996A (en) Packet switched multiple queue NXM switch node and processing method
US5218676A (en) Dynamic routing system for a multinode communications network
EP1226501B1 (en) Network switch and components and method of operation
US5859835A (en) Traffic scheduling system and method for packet-switched networks
US20030137940A1 (en) Pass/drop apparatus and method for network switching node
US7457296B2 (en) Method and apparatus for sorting packets in packet schedulers using a connected trie data structure
Bolding et al. The case for chaotic adaptive routing
US5164939A (en) Packet switching device
KR19990087752A (ko) 효율적인 출력 요구 패킷 스위치와 방법
US6757284B1 (en) Method and apparatus for pipeline sorting of ordered streams of data items
EP1488600B1 (en) Scheduling using quantum and deficit values
US6714554B1 (en) Method and system for sorting packets in a network
US6836475B2 (en) Method and apparatus for traffic shaping for IP router queues/egress
Park et al. NN based ATM cell scheduling with queue length-based priority scheme
US7269158B2 (en) Method of operating a crossbar switch
US6490640B1 (en) Packet data switching apparatus
Modiano et al. A simple analysis of average queueing delay in tree networks
US7006513B1 (en) Method and system for pipelining packet selection