JPH10164096A - マルチキャスト・パケット・アクセス調停方法 - Google Patents

マルチキャスト・パケット・アクセス調停方法

Info

Publication number
JPH10164096A
JPH10164096A JP31949797A JP31949797A JPH10164096A JP H10164096 A JPH10164096 A JP H10164096A JP 31949797 A JP31949797 A JP 31949797A JP 31949797 A JP31949797 A JP 31949797A JP H10164096 A JPH10164096 A JP H10164096A
Authority
JP
Japan
Prior art keywords
arbitration
destination
output
unit
cycle
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
Application number
JP31949797A
Other languages
English (en)
Other versions
JP4381490B2 (ja
Inventor
M Davis Helen
エム．デイビス ヘレン
T Preece Brian
ティー．プリース ブライアン
G Bell Alan
ジー．ベル アラン
B Reils Joseph
ビー．ライルズ ジョセフ
H Greene Daniel
エイチ．グリーン ダニエル
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.)
Xerox Corp
Original Assignee
Xerox 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 Xerox Corp filed Critical Xerox Corp
Publication of JPH10164096A publication Critical patent/JPH10164096A/ja
Application granted granted Critical
Publication of JP4381490B2 publication Critical patent/JP4381490B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

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/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/102—Packet switching elements characterised by the switching fabric construction using shared medium, e.g. bus or ring
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/20—Support for services
    • H04L49/201—Multicast operation; Broadcast operation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/20—Support for services
    • H04L49/201—Multicast operation; Broadcast operation
    • H04L49/203—ATM switching fabrics with multicast or broadcast capabilities
    • 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
    • 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
    • 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
    • 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/5681—Buffer or queue management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/103—Packet switching elements characterised by the switching fabric construction using a shared central buffer; using a shared memory
    • 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

(57)【要約】 【課題】 交換機に、予約リングを備えた交換ネットワ
ークの宛先出力チャネルへのマルチキャスト・パケット
・アクセスを調停する。 【解決手段】 １組の宛先出力チャネルを示す調停要求
を発してマルチキャストセルに関する調停セッションを
開始するステップと、調停サイクル中、当該１組の宛先
出力チャネルの各宛先出力チャネルへのアクセスを調停
するステップと、調停サイクル完了後、予約が割り当て
られた宛先出力チャネルを前記１組の宛先出力チャネル
の中から除去するステップと、この調停ステップと除去
ステップを連続する調停サイクルにわたって繰り返すス
テップとを含む。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、一般には通信ネッ
トワークに関し、特にATM (非同期転送モード)において
動作する予約リングを備えた交換ネットワークに対する
マルチキャスト・パケット・アクセスを調停する方法に
関する。
【０００２】
【従来の技術】ATM ネットワークが一般的となりオフィ
スネットワークとして使用されるようになるにつれ、小
型スケーラブル（規模の変更可能な）交換への要望が大
きくなってきた。オフィス環境では、こうした小型スケ
ーラブル交換機を「 ATM拡張コード (ATM extension co
rds)」として使用することにより一つの物理的接続でオ
フィス機器をより大型の中央側の交換機へ接続すること
が可能になる。こうした使用では、中央交換機が要求す
るスループットレベルに必ずしも小型スケーラブル交換
機がサポートする必要はない。このため、小型スケーラ
ブル交換機のアーキテクチャは制限された交換帯域幅内
で効率よく動作するように構成するのが望ましい。帯域
制限交換ネットワーク(limited bandwidth switching n
etworks)で動作する小型スケーラブル交換機には複数の
出力ポートがセットとして設けられており、交換ネット
ワークは、交換周期毎に限られた数のセルを出力ポート
に転送できる。一般に、交換帯域幅の制限された交換機
は、入力ポートが論理動作どおり動作できる総合最大リ
ンク速度 (aggregate maximum link rate)よりも低いス
ループットで動作する。
【０００３】制限された帯域幅で動作する交換機は、一
回の交換周期中に全ての入力及び出力ポートを可能性の
ある全ての一対一入出力ポート間マッピングを発生でき
ないため、「閉塞状態(blocking)」になる可能性があ
る。この閉塞状態を起こす交換機では、セルが失われな
いようにするため入力をバッファー処理する必要があ
る。出力バッファー処理が行われている場合でも、入力
バッファー処理を行うほうが望ましい。例えば、一交換
周期内に特定の出力バッファー向けの最大数のセルを出
力バッファーで待機させることができない時は、入力を
バッファー処理する必要がある。米国特許第 5,305,311
号に述べられているように、入力バッファー処理と出力
バッファー処理の組合せは、損失のない交換を行うのに
必要な出力バッファーの帯域幅を制限する効果的な方法
である。
【０００４】
【発明が解決しようとする課題】しかしながら、入力を
待機させて一交換周期毎に出力ポートへ１個のセルを出
力させる交換機では、待機行列の先頭のブロッキングが
生じる問題があることが知られている。一般に、待機行
列の先頭のブロッキングはスループットの著しい低下を
引き起こす。米国特許第 5,305,311号には、交換周期毎
に各出力ポートの速度をｋ（例えば、ｋ＝２）倍にして
待機行列の先頭のブロッキングを最小化する方法が開示
されている。出力ポート毎にその速度をｋ倍に増加させ
ることにより、ｋ＝１（単に入力を待機させた時）では
スループットは約５８％であったものを、ｋ＝２では約
８９％、さらにｋ＝４以上では略１００％にまで増加で
きる。
【０００５】
【課題を解決するための手段】本発明によれば、交換機
に、予約リングを備えた交換ネットワークの宛先出力チ
ャネルへのマルチキャスト・パケット・アクセスを調停
する方法を備える。当該交換ネットワークは、交換サイ
クル中に、Ｉ個の入力チャネルの内の選択されたものか
らＪ個の出力チャネルの内の選択されたものへの単一パ
ス・マルチキャスト・パケットを転送する。当該予約リ
ングは、交換サイクル中に同一の出力チャネルについて
競合する入力チャネル間のコンフリクトを解消する。本
方法は、１組の宛先出力チャネルを示す調停要求を発し
てマルチキャストセルに関する調停セッションを開始す
るステップと、調停サイクル中、当該１組の宛先出力チ
ャネルの各宛先出力チャネルへのアクセスを調停するス
テップと、調停サイクル完了後、予約が割り当てられた
宛先出力チャネルを前記１組の宛先出力チャネルの中か
ら除去するステップと、この調停ステップと除去ステッ
プを連続する調停サイクルにわたって繰り返すステップ
とを含む。この繰り返しステップは、１組の宛先出力チ
ャネル中の各宛先出力チャネルに予約が割り当てられた
時に調停セッションを終了させる。
【０００６】
【発明の実施の形態】以下、本発明の実施の形態を図面
を用いて詳細に説明する。
【０００７】図１は ATM(非同期転送モード)交換機５の
概略図を示したものである。交換機５は複数のクラスタ
モジュール８を有しており、このクラスタモジュール８
は、ネットワークチャネル１２、１３によりクラスタ間
交換ネットワーク１０に接続されている。各クラスタモ
ジュール８には１以上の入出力 (I/O)ポート１６が設け
られている。交換機５のアーキテクチャはモジュール型
でかつ階層構造である。モジュール形式をとっているた
め、交換機５の規模を変更するのは容易である。一方、
階層構造を有しているため、交換帯域幅をポート間で共
有させたり、同一クラスタモジュール８のI/O ポート１
６へのトラフィックが交換ネットワーク１０上であちこ
ち転送(traverse)されるのを防止できるため交換機５の
平均スループットは増加する。クラスタ間交換ネットワ
ーク１０に対するクラスタモジュール８のアクセスは、
調停すなわち予約リング１４を使って行われる。予約リ
ング１４は分散型アービタ(distributed arbiter) で、
ライン１７で結合された有限状態マシンあるいは調停ユ
ニットの線形シストリックアレイ(systolic array)とし
て構成される。予約リング１４の各調停ユニット１５は
直近のユニットに接続されている。予約リング１４のよ
うな線形シストリックアレイの利点としては、通信が全
て局所的に行われ、アレイが大きくなっても電気的負荷
が増えることがない。このため、交換機５の規模を線型
的に変更できる。
【０００８】交換機５はホストプロセッサ２０を備えて
おり、このプロセッサ２０がホストコントロールバス２
２を介して通信を行う。各クラスタモジュール８は、ク
ラスタ制御器２４、記憶ユニット２８、ポートインター
フェースユニット２７と、少なくとも１個の交換ネット
ワークインターフェースユニット１９を含む。クラスタ
制御器２４はクラスタモジュール８の制御／プライマリ
ーデータパスを提供する。記憶ユニット２８はクラスタ
制御器２４の外部に設けられており、セルをバッファー
処理のために格納したり、セルのマッピング情報を記憶
する。さらに、記憶ユニット２８内のデータ構造には、
入力待ち行列、複数の出力待ち行列、ＶＰＩ／ＶＣＩマ
ップ、および空きセル(free cell) のリストなどが含ま
れる。各クラスタモジュール８のポートインターフェー
スユニット２７は、複数のポートインターフェース２６
を含んでいる。このポートインターフェース２６はいず
れもネットワークを介してセルを送受信するためのもの
である。
【０００９】各クラスタモジュール８はクラスタ内の通
信だけでなく、クラスタ間の通信もサポートしている。
クラスタ間通信には、クラスタ間交換ネットワーク１０
を用いて異なるクラスタモジュール８に接続されたポー
ト間の交換処理が含まれる。クラスタ間交換ネットワー
ク１０へのアクセスは、各クラスタモジュール８の交換
ネットワークインターフェースユニット１９を介して行
われる。交換ネットワークインターフェースユニット１
９は、前記調停ユニット１５と交換ネットワークインタ
ーフェース１８を含んでいる。各交換ネットワークイン
ターフェース１８は、接続２１を介してクラスタ制御器
２４に接続されている。クラスタ間交換ネットワーク１
０とこのネットワーク１０の出力チャネル１３の双方に
対するアクセスまたは予約(reservation) が調停ユニッ
ト１５によって行われるまでは、交換ネットワークイン
ターフェース１８がパケットデータを保持している。
【００１０】動作中は、交換サイクル中にクラスタ間交
換ネットワーク１０を介していずれか１個の出力チャネ
ル１３へ最大Ｋ個（大文字）（ここで、K ≧１）のセル
が出力されるよう予約リング１４はスケジュールする。
ここで、Ｋ（大文字）はクラスタモジュール８毎の加速
係数(speed up factor) であって、（ｐ＊ｋ）に相当す
る。ここで、ｐはクラスタモジュール８の１個当たりの
I/O ポート１６の数を示しており、またｋ（小文字）は
交換機内でクラスタ処理を行わない交換機における I/O
ポート１６の１個当たりの加速係数である。１個のクラ
スタモジュール８の中の出力ポート１６では、出力チャ
ネル１３の１個当たりの加速係数Ｋ（大文字）を共有し
ている。
【００１１】図２は予約リング１４を示している。この
予約リング１４は、交換ネットワーク帯域幅や出力チャ
ネル１３と出力ポート１６へのアクセスといったネット
ワークの共有資源の分散調停(distributed arbitratio
n) を行うものである。予約リング１４は、複数の調停
ユニット１５から構成されている。この調停ユニット１
５は、調停サイクルにおいて、ネットワーク資源に対す
るコンテンション（競合）を解消する。例えば、予約リ
ング１４は、クラスタ間交換ネットワーク１０の出力チ
ャネル１３についてのコンテンション（Ｋコンテンショ
ンと称す）と、制限された交換ネットワークの帯域幅に
ついてのコンテンション（Ｂコンテンションと称す）を
解決する。調停サイクルの開始点では、（複数の）出力
チャネル１３へのアクセスに関する調停要求が調停ユニ
ット１５へ出力される。コントローラー５８のような中
央クロック機構を利用して、これらの調停要求はライン
１７を介して予約リング１４内部をあちこち転送され
る。集積回路のピン数を減少することが必要とされる実
施例では、ライン１７の数を減少させ、予約リング１４
の中で調停要求信号を時分割（またはパイプライン処
理）する。
【００１２】調停サイクル中に、調停ユニット１５は、
出力ポート１６、出力チャネル１３、交換ネットワーク
１０の帯域幅などのネットワーク資源へのアクセスを調
停する。調停ユニット１５へ出力された調停要求が調停
サイクル中に予約リング１４の内部をシフトされている
時に各調停ユニットでは到来する調停要求とそのユニッ
トに常駐している調停要求（resident arbitration req
uest）とを比較する（すなわち、そのユニット自身の調
停要求が予約リング内を一巡するようにシフトされ
る）。調停サイクルの間に、各調停ユニット１５は調停
の各段階でこのような比較を行う。もしネットワーク資
源に対してコンフリクトが発生していることが判明した
場合は、調停ユニット１５ではどちらの調停要求（すな
わち、シフトされた要求または常駐要求）がネットワー
ク資源について高い優先順位を有するかを判断する。多
数のネットワーク要求が存在しているため、ネットワー
ク資源へのアクセスの調停では調停サイクルが終了する
までに調停処理を何回も行う場合がある。調停サイクル
が終了するまでに調停処理が１回で済むか、あるいは２
回以上必要であるかは、調停中のネットワーク資源間の
関係で決まる（すなわち、あるネットワーク資源の調停
が相互に依存しているか、あるいは別の資源の調停とは
無関係であるかによる）。
【００１３】ネットワーク資源の各資源に対する調停処
理が残りのその他のネットワーク資源とは無関係に実行
されるときは、常に１回の調停処理中に複数のネットワ
ーク資源への調停が並行して行ってもよい。例えば、ク
ラスタモジュール８の各出力ポート１６が受信できる最
大セル数（つまり、ｋ＿alloc ）の総計が、クラスタモ
ジュール８が受信できるセル数（Ｋ）にすぎない（すな
わち、ｋ＿alloc の合計がＫと等しい）場合は、出力ポ
ート１６と出力チャネル１３へのアクセスの調停は個別
に実行される。この場合、１回の調停処理（すなわち、
予約リング１４を一順する間に）調停を並行して実行で
きる。上記の例では、調停ユニット１５が調停を要求し
ている（複数の）出力ポート１６と（複数の）出力チャ
ネル１３の両方の調停に成功した時に、交換ネットワー
クへのアクセスが許可される。
【００１４】しかしながら、クラスタモジュール８の各
出力ポート１６が受信できるセル数の総計がクラスタモ
ジュール８が受信できるセル数以上の（すなわち、ｋ＿
allocsの合計がＫよりも大きい）時は、複数のネットワ
ーク資源に対する複数の調停要求は個別には実行されな
い。これらのネットワーク資源に関する相互依存調停処
理を実行することにより、更に多くのネットワーク資源
が利用されることになる。例えば、調停ユニット１５が
出力チャネル１３へのアクセスだけを調停し、出力ポー
ト１６へのアクセスを得た場合はネットワーク資源の利
用が向上する。同様に、交換ネットワーク帯域幅が制限
されている場合は、調停ユニット１５が交換ネットワー
ク帯域幅への調停だけを調停し、出力ポート１６と出力
チャネル１３の両方へのアクセスを得たならばネットワ
ーク資源の利用がさらに向上する。
【００１５】ネットワーク資源に対して相互依存調停を
実行する場合は、予約リング１４を複数回巡回するよう
に調停要求をシフトすることにより最大交換スループッ
トを得ることができる。調停要求が予約リング１４を１
回巡回する間、調停ユニット１５は調停要求がネットワ
ーク資源に対して高い優先順位を有しているか否かを判
定する。調停処理に失敗した調停処理ユニット１５はそ
の後、自ユニットを調停処理から除く（すなわち、調停
処理で調停に失敗した調停ユニット１５はその後の調停
処理では要求を出力しない）。
【００１６】ネットワーク資源への相互依存調停の例を
説明する。出力ポート１６と出力チャネル１３へのアク
セスは並行して行うことができ（すなわち、クラスタモ
ジュール８の各ポート１６に関するk ＿allocsの合計が
Ｋにすぎない）、また交換機５の交換ネットワーク１０
の帯域幅が制限されていると仮定する。出力チャネル１
３へのアクセスの調停は、１以上の調停サイクルで行わ
れる。各調停サイクルは２回の調停処理から成る。第１
回目の調停処理で出力チャネル１３へのコンテンション
が解消され、第２回目の調停処理でクラスタ間交換ネッ
トワーク帯域幅コンテンションが解消される。さらに、
１以上の交換サイクルで各調停サイクルが実行できる。
バスフレームの期間に１以上のバススロットを調停する
ことにより、予約リング１４での調停に利用できる時間
が増加する。
【００１７】米国特許第5,519,698 号（Lyles et. a
l.,）の教示によれば、予約リング１４は有限状態マシ
ンまたは調停ユニット１５の線形シストリック(systoli
c)アレイから構成されている。この調停ユニットはそれ
ぞれ直近の調停ユニットとのみに通信する。処理として
は、交換サイクルで１個の出力チャネル１３へ最大でＫ
個のセルが出力され、また交換サイクルの間に最大でＢ
個のセルが交換ネットワークへ入力されるように予約リ
ング１４でクラスタ間交換ネットワーク１０へのアクセ
スを要求するセルのためにスケジューリングを行う。各
調停ユニット１５のＫの値は、出力チャネル１３の全体
に対して一定に設定することもできるし、あるいは、出
力チャネル１３毎に変えて設定することもできる。同様
に、何らかの一対一対のマッピングを転送する交換機の
能力(the ability of the switch toroute any one-to-
one mappings) を制限する複数の交換資源が存在する
場合は、各資源のＫ値は共通の値または異なる値をとる
場合がある。クラスタモジュール８はいずれも有限状態
マシンまたは調停ユニット１５を含む、このモジュール
は記憶ユニット２８内の入力待ち行列先頭のセルが、ク
ラスタ間交換ネットワーク１０の次の交換サイクル中に
送信すべきかどうかを判断する。すなわち、予約リング
１４の各調停ユニット１５は、送信準備ができているク
ラスタモジュール８に関連する最も優先順位の高いセル
を調べ、より優先順位の高いセルを入力待ち行列の先頭
に有するクラスタモジュール８が他に幾つあるかを判断
する有限状態マシンである。
【００１８】各調停ユニット１５の状態情報は内部レジ
スタ７３に記憶される。各調停ユニット１５へ転送され
る情報はインターフェースシフトレジスタ７４に格納さ
れる。予約リング１４にｍ個の調停ユニット１５が設け
られていると仮定すると、予約リング１４内を１回循環
する各調停ユニット１５の状態情報は、調停処理中にｍ
回シフトされる。一つの調停サイクルは１回以上の調停
処理から成る。本願明細書では、１回の調停処理でｍ回
シフトされる場合の各シフトを「調停ステージ(arbitra
tion stage) 」と称する。インターフェースシフトレジ
スタ７４に記憶されている状態情報は、各調停ユニット
１５の内部に記憶されている「R(すなわち、常駐）-Des
tination Vector 」を有しており、また特定のセルの所
望の宛先出力ポート１６を示す情報も有している。一つ
の実施の形態においては、常駐宛先ベクトル内の可能性
のある出力ポート１６をビットアレーを用いて示す。１
個のセルを１以上の出力ポート１６へ多重出力(multica
st) する場合は、その宛先ベクトル内の１以上のビット
を設定する。他の実施の形態においては、予め設定した
ビット列(sequences of bits) を用いて出力チャネル１
３の特定のグループを定義することができる。この場
合、各宛先ベクトルは、１以上の出力ポート16を示すよ
う予め設定されたビット列から構成されている。調停サ
イクルの開始時点では、予約リング１４上の各調停ユニ
ット１５の前記「R-destination vector」がその「S(す
なわち、シフト)-Destination Vector」へ複写される。
これら「S-Destination Vector」は、調停処理中に調停
リング１４の内部でシフトされる。
【００１９】インターフェースシフトレジスタ７４と内
部レジスタ７３にはそれぞれ「有効(valid) 」ビットを
含んでいる。この「有効」ビットは、所定の調停サイク
ル中の調停要求が有効であるかどうかを示すものであ
る。また、各インターフェースレジスタ７４には調停す
るセルの優先順位を示す情報が格納されている。セルの
優先権は、固有(intrinsic) のものであると同時に外的
(extrinsic) なものでもある。固有優先順位とはセルに
関連する優先順位（例えば、セルが多重出力セルである
かどうか、または予約済みトラフィックであるかそうで
ないか）である。外的優先順位とは、調停リング１４で
生成された順位（例えば、トークンまたは「Ｔ」ビッ
ト）である。このセルの優先順位情報の一部は内部レジ
スタ７３に複写される。これらの優先順位ビットを用い
てある調停ユニット１５が別の調停ユニット１５に対し
て調停処理を行う権利を獲得したか否かを判断する。要
するに、「トークン」または「Ｔ」ビットはタイ・ブレ
ーキング・ビット(tie-breaking bit)であって、別の調
停ユニット１５がより高い優先順位を持っているかどう
かを示すものである。「MCast 」ビットは、セルが多重
出力(multicast) されるのか単一出力(unicast) される
かを示している。また、「Rsv 」ビットは、セルが予約
済みトラフィックであるかそうでないかを示している。
さらに、「in＿session 」ビットは前回の調停サイクル
でセルがブロック(blocked) されたかどうかを示す。
【００２０】図３は、調停ユニット１５の制御状態７６
を詳細に示したものである。動作中においては、調停ユ
ニット１５が調停の時に各内部レジスタ７３に格納され
ている制御状態７６にアクセスする。調停サイクルで各
調停ユニット１５が実行するステップは図４〜７に示さ
れており、以下にこれを説明する。一般に、制御ユニッ
ト１５は制御状態７６を使用して「調停セッション(arb
itrary session) 」中に状態情報を記録する。この調停
セッションには幾つかの調停サイクルが含まれる場合が
ある。調停セッションの長さは、セルが１以上の所望の
出力チャネル１３へアクセスを行うのに成功したかどう
かで決まる。以下の説明からも分かるように、所定の調
停セッション中に同じ出力先へ割り当てられたセルは、
前記所定セッションに参加した全てのセルがそれらの共
通の宛先へ転送されるまでは、後から到着するセルに対
して閉鎖グループ(closed set)を形成する。他の実施の
形態においては、この要件は緩和されており、前記閉鎖
グループのセルでなくとも前記所定セッションに参加で
きる。この場合、前回の調停セッションに干渉しなけれ
ば、その後の新規の調停セッションの調停要求も参加す
る。このようにセッション要件が緩和された調停リング
の詳細が米国特許第5,305,311 号に開示されている。
【００２１】図４は調停セッション中に調停ユニット１
５が実行する一般的なステップを図示したフローチャー
トである。クラスタモジュール８は、調停要求をその調
停ユニット１５へ送信して調停セッションを開始または
調停セッションに参加する。調停要求はデータパケット
またはセルの送信先を特定し、データパケットの優先順
位を示す。例えば、多重送信セルの場合は１以上の出力
チャネル１３へアクセスする必要が生じる場合もあるた
め、調停要求を満足させるために調停セッションが１以
上の調停「サイクル」を要する場合もある。調停サイク
ルの終わりに、次の交換サイクルに備えてクラスタ間交
換ネットワーク１０の特定の入力チャネル１２から特定
の出力チャネル１３へセルを転送するよう定める。すで
に説明したように、各調停「サイクル」は２回の調停処
理から構成されている。各調停処理では、クラスタモジ
ュール（または入力チャネル１２）からの調停要求は予
約リング１４を巡回して伝搬する。第１回目の調停処理
では、入力チャネル１２間での出力チャネル１３につい
てのコンテンションを調停する。第２回目の調停処理で
は、入力チャネル１２間での交換ファブリック(switchi
ng fabric)の帯域幅「Ｂ」についてのコンテンションを
調停する。すでに説明したように、各調停処理では、調
停要求は予約リング１４の中を各調停ユニット１５へシ
フトされる。この各シフトを調停処理の「ステージ」と
定義する。
【００２２】調停サイクルでは、予約リング１４を構成
している調停ユニット１５がクラスタ間交換ネットワー
ク１０へのアクセスを調停する。「調停セッション」は
宛先と対応付けられており、次の調停サイクルまで調停
セッションが延長されるような場合は調停セッションは
アクティブのままになっている。関連する宛先のチャネ
ル１３へのアクセスの調停を調停ユニット１５が失敗し
た時は調停セッションが延長される。調停セッションを
延長される場合には、新たな調停要求はセッションに参
加できない。また、このセッションで処理されている調
停要求は、同セッションに関連する宛先に対して後から
出された調停要求よりも優先する。このように、調停セ
ッションがアクティブの時は、調停ユニット１５は前回
ブロックされた要求または新たな要求を再送信できる。
しかしながら、現在有効なセッションに対応する宛先に
関しては何れの調停ユニット１５も関連する宛先につい
ての新たな調停セッションを開始できない。何故なら、
新しい要求が調停に勝つ以前に該セッションの一部の要
求が満足されているためである。調停セッションを用い
てセルが無期限にブロックされるのを防ぐ方法はすでに
周知であり、その詳細は米国特許第5,519,698 号に開示
されている。
【００２３】予約リング１４に設けられている調停ユニ
ット１５の状態変数は立上げの時にステップ１０１でリ
セットされる。すなわち、内部レジスタ７３とインター
フェースシフトレジスタ７４の内の全ての変数がクリア
される。例えば、制御状態７６に格納されている「my＿
in＿session 」変数は「FALSE 」にリセットされる。次
に、ステップ１０２では要求ライン７８を経て調停要求
が調停ユニット１５へ入力される。ＴＲＵＥに設定され
た「有効」ビット付き調停要求は、調停ユニット１５に
は転送のためネットワークへ出力するセルがあることを
示している。ステップ１０４では、調停ユニット１５の
制御状態７６に格納されている状態情報が新しい調停
「サイクル」の開始時点でリセットされる。制御状態７
６に格納されている状態情報の詳細を図３に示す。
【００２４】調停セッションで１以上の出力チャネル１
３へのアクセスを調停するには、調停サイクルの各処理
に調停ユニット１５が参加する必要がある。第１回目の
調停処理において、交換ネットワーク１０の１以上の出
力チャネル１３とクラスタモジュール８の１以上の出力
ポート１６へのアクセスをステップ１０６において調停
ユニット１５が調停する。引き続く交換サイクルでは、
交換ネットワーク１０の各出力チャネル１３へ入力でき
るセルの最大数はＫ個に制限される。同時に、各出力ポ
ート１６に入力できるセルの最大数も「k ＿alloc 」個
に制限される。出力チャネル１３の１チャネル当たりの
入力数を「Ｋ」個に制限し、出力ポート１６へのセル入
力数を「k＿alloc」に制限する方法は後で詳細に説明す
る。調停ユニット１５の調停要求はステップ１０８で隣
接する調停ユニットにシフトされ、第１回目の調停処理
の各ステージ完了するまでステップ１０６の処理が繰り
返される。第２回目の調停処理では、クラスタ間交換ネ
ットワーク１０の帯域幅をステップ１１０で各調停ユニ
ット１５が調停する。交換ネットワーク１０で利用でき
る全帯域幅を「Ｂ」に制限する。ここで、「Ｂ」はポー
ト１６の総リンク速度未満である。第２回目の調停処理
の各ステージが完了するまで、ステップ１１２では予約
リング１４上の各調停ユニット１５に対してステップ１
１０の処理を繰り返し実行する。
【００２５】ステップ１１４では、処理が要求されてい
る出力チャネル１３に対しての交換帯域幅の調停が成功
したかどうかを各調停ユニット１５が判断する。交換ネ
ットワーク１０の次の交換サイクルでセルの交換を行う
ことが予約できる場合、調停は成功である。ステップ１
１６で調停セッションが成功裏に終わったと判断された
場合はステップ１０２が繰り返される。そうでない場合
は、ステップ１１７を実行する。ステップ１１７では調
停要求の全てまたは一部が再発行される。要求されてい
る出力チャネル１３の一部へのアクセスを、交換ネット
ワーク１０の次の交換サイクルで行うことが許可される
と調停要求の一部が再発行される。全てまたは一部が許
可された調停要求は、許可ライン７９または８３を経て
クラスタチャネル制御ユニット２４または交換ネットワ
ークインターフェース１８に出力される。
【００２６】図５は図４のフローチャートのステップ１
０６と１０８の詳細を示すフローチャートであって、調
停ステージにおける交換ネットワーク１０の１以上の出
力チャネル１３の調停の様子を示したものである。最初
に、ステップ１２０において、各調停ユニット１５はそ
の「S-Destination Vector」を予約リング１４へ転送す
る。上述のように、この「S-Destination Vector」の各
ビットは調停サイクルでどの調停出力チャネルについて
調停が行われているかを定義している。また、ステップ
１２０では、「カウンタ」変数をゼロにリセットして調
停サイクルの第１処理が開始された（すなわち、予約リ
ング１４の第１ステージが開始された）ことを通知す
る。次のステップ１２２では、予約リング１４からの要
求が隣接する調停ユニット１５からインターフェースシ
フトレジスタ７４（図２）によって受信される。
【００２７】ステップ１２４では、予約リング１４から
入力された調停要求から取り出したタイ・ブレーカー・
「トークン」(tie-breaker "token") を調べ、２台の調
停ユニットの間に繋がり(tie) がある時は調停要求に優
先権を付与できる。各調停ユニット１５は、予約リング
１４内を転送されて繋がりを終了させる「トークン」ま
たは「Ｔ」ビットを「current＿ring＿tail」変数と「n
xt＿ring＿tail」変数を用いて更新する。これらの変数
は、調停処理の各ステージでの優先順位を定義すること
により調停ユニット間でタイ・ブレーキングが公平に行
われことを保証する。概念的には、要求されている調停
ユニットの順番でリスト状に予約リング１４を分解する
ものと考える。リストの上位にある調停ユニットには、
リストの下位にある調停ユニットよりも高い優先順位が
付与される。公正さを高めるため、リストの開始（star
ting）調停ユニットは定まっているのではなく(not sta
tic)、予約リング１４の中を循環しているのである。こ
のため、固定でなく(not static)循環されている優先順
位で繋がりを解消することでポート全体での公正さが向
上する。例えば、各調停ユニット１５では、予約リング
１４に調停要求を出力する前にまずその「トークン」変
数を高い優先順位[HIGHER (priority)] に設定する。電
源立上げの時こうして指定された調停ユニットをリスト
の最後尾に割り当てる。リストの最後尾に指定された調
停ユニットは、「トークン」変数を予約リング１４へ出
力する前に低い優先順位[LOWER (priority)]に設定す
る。低い優先順位[LOWER (priority)]トークンを受信し
た調停ユニットは、現在の調停要求よりも低い優先権を
シフトされた調停要求に与える。しかしながら、調停ユ
ニットに優先順位の高い[HIGHER (priority)] トークン
が入力された時は、常駐調停要求よりも高い優先順位が
シフトされた調停要求に割り当てられる。すなわち、調
停処理の開始時点で優先順位の低いトークン変数が最初
に入力されるリスト中の次位の調停ユニットは、次の調
停処理ではリストの次の最後尾となる。
【００２８】各調停ユニットは、宛先「Ｋ＿counter 」
ベクトルをステップ１２６で更新する。このため、各調
停ユニット１５では、交換ネットワーク１０の要求出力
チャネル１３についてコンテンションが発生しているか
どうかを判断しなくてはならない。交換ネットワーク１
０の交換サイクルで１つの出力チャネル１３に転送され
るセルの数は「dest＿K ＿max 」個に制限されている。
調停ステージでは、各調停ユニット１５は「resident
(R)-destination vector」と「shifted(S)-destination
vector 」を比較して交換ネットワーク１０内の１つの
出力チャネル１３に対してコンテンションが発生してい
るかどうかを判断する。類似した出力チャネル１３に対
して２つの調停ユニットの間でコンテンションが発生し
ている場合は、どちらのユニットの優先順位が高いかを
判断して優先順位を決める。
【００２９】すなわち、ステップ１２６では、調停ステ
ージの時に同一出力チャネル１３に対して２台の調停ユ
ニットがコンテンション状態にある時は、優先順位の低
い調停ユニットがその宛先K ＿counter ベクトルに含ま
れている出力チャネルに相当する宛先K ＿counter を増
加させる。タイ・ブレーカー・「トークン(T bit) 」、
「有効」ビット、「rsv(すなわち、resvered)」トラフ
ィックビット、「mcast（すなわち、multicast)」ビッ
トからなる要素を組み合わせて使用して調停要求の優先
順位を決める。この「有効」ビットは、調停要求が現在
の調停処理で有効であるかどうかを表している。有効ビ
ットがTRUEに設定されたセルには高い優先順位が付与さ
れる。「rsv 」トラフィックビットは、セルが予約済み
トラフィックかそうでないかを表している。予約済みト
ラフィックには高い優先順位が付与される。「mscat 」
ビットは、セルが多重出力されるか単一出力されるかを
表している。次の交換サイクルで多重出力要求の一部を
再送信するよりもセルの出力チャネル１３を全て満足さ
せるほうがより効率的であるため、多重出力に高い優先
順位を付与する。
【００３０】ステップ１２７では、調停ステージにおい
て、出力ポート１６について他の調停ユニットとの競合
（コンテンション）に失敗した場合は、特定のポートに
ついての宛先「k ＿alloc ＿ct」カウンタを増加させ
る。各調停ユニット１５の「k＿alloc ＿ct」ベクトル
は、交換機５のポート毎に設けられた「k ＿alloc ＿c
t」カウンタを含んでいる。出力チャネルのコンテンシ
ョンを解消するため用いた優先順位を用いて出力ポート
１６についての２台の調停ユニット間のコンテンション
も解消される。本発明の実施の形態では、交換機５の出
力ポートに転送されるセルの数は、「dest＿k ＿alloc
＿max 」ベクトルに含まれている特定の値に限定されて
いる。従って、「dest＿k ＿alloc ＿max 」個以上のセ
ルが１つの出力ポートで競合する時は、「dest＿k ＿al
loc ＿max 」個のセルのみが交換ネットワークについて
の予約が認められる。各出力ポート１６に対して「k ＿
alloccounter 」が定義されておらず、また各出力チャ
ネル１３に対して「K ＿count」だけが定義されている
ような実施の形態の場合は、各調停ユニット１５はステ
ップ１２６の処理を行い、ステップ１２７の処理は省略
する。
【００３１】調停ユニット１５についての「session ＿
active」変数をステップ１２８で更新する。この「 ses
sion＿active」変数は調停ユニットの制御状態７６に格
納されていたものであり、交換ネットワーク１０の出力
ポート１３について前回の調停セッションがまだアクテ
ィブであるかどうかを表している。調停セッションは単
一の宛先である出力チャネル１３に関するものであり、
該セッションに参加しているセルのそれぞれが単一の宛
先である出力チャネル１３に転送されてしまうとそのセ
ッションは終了する。もし出力チャネル１３に対してセ
ッションがまだアクティブである場合は、「in＿sessio
n 」ビットがＦＡＬＳＥに設定されている出力チャネル
１３について、新規の調停要求が次回の調停セッション
まで延期されている。つまり、いずれかの宛先出力チャ
ネル１３への調停セッションが一旦開始されると、その
チャネルに対する別の要求が現在の調停セッションに付
加されることはない。このように、調停セッションが完
了すると、行列の先頭にあって次の調停セッションに参
加する資格のある全ての待ち要求は、次の調停セッショ
ンに参加できる。１以上の調停サイクルのセッションで
宛先出力チャネル１３について調停を行うことにより、
入力チャネルが無期限にブロックされる危険がなくな
る。
【００３２】ステップ１３０では、各調停ユニット１５
の制御状態７６に格納されている「カウンタ」変数を調
べて、各調停ユニットについての調停要求が予約リング
１４を一巡して各調停ユニットへシフトされたかどうか
を判断する。各調停要求が予約リング１４を一巡してシ
フトされると、ステップ１３６の処理が実行される。そ
うでない場合は、ステップ１３２の処理が実行される。
ステップ１３２では、「カウンタ」変数を増加させる。
ステップ１３４では、調停ユニットに最後に入力された
要求を予約リング１４上へシフトして出力し、ステップ
１２２の処理を繰り返す。
【００３３】各調停ユニット１５の調停要求内容が予約
リング１４を一巡してシフトされると、ステップ１３６
の処理が実行される。ステップ１３６では、「R-destin
ation vector」に定義されている要求される各宛先出力
チャネル１３についての「destination K ＿counter ve
ctor」に含まれているK ＿counterが「dest＿K ＿max」
を超えているかどうかを予約リング１４の各調停ユニッ
ト１５が判断する。この判断は、各調停ユニットの状態
制御ロジックに格納されている「destinationK＿counte
r vector」を用いて行う。 他の調停ユニットに対して
ある調停ユニット１５をステップ１２６において遅延さ
せた回数が「dest＿K＿max」１５を超えず、また他の調
停ユニット１５に対してある調停ユニット１５をステッ
プ１２７において遅延させた回数が「dest＿k ＿alloc
＿max」を超えない場合は、「ok＿to＿send-destinaion
vector」に対応する出力ポート１６を記録する。すな
わち、特定の宛先出力チャネル１３に対して「destinat
ion K ＿counter vector」の「K＿counter」が超えられ
ることがなく、また特定の宛先ポート１６についての
「k ＿alloc ＿ct vector 」の「k ＿alloc ＿ct」が超
えられるようなことがない場合にのみ、ビットを「ok＿
to＿send-destination vector 」に設定する。第１回目
の調停処理後では、「ok＿to＿send-destination vecto
r 」に設定されている各ビットは次の交換サイクルにど
の宛先出力チャネル１３がデータパケットを受信するか
を表している。「ok＿to＿send-destination vector 」
に設定されているこれらのビットは、交換サイクル中の
送信セル数の制約、すなわち各宛先出力チャネル１３に
最大で「dest＿K ＿max 」個のセルしか送信してはなら
ず、また、宛先出力ポート１６に最大で「k ＿alloc ＿
max 」個のセルしか送信してはならないという制約を満
足させるためのものである。しかしながら調停サイクル
のこの時点では、交換ネットワーク１０の帯域幅制限
「Ｂ」を超えているかどうかは「ok＿to＿send-destina
tion vector 」からは分からない。
【００３４】各クラスタモジュール８について１チャネ
ル当たりの加速係数Ｋ（the speedup of K per channe
l）と１ポート当たりの加速係数ｋ(the speedup of k p
er port) を動的に設定する実施の形態では、予約リン
グ１４の各調停ユニット１５は各「dest＿K＿max」また
は「dest＿k＿alloc＿max max vector」について定義さ
れている値が分からなくてはならない。つまり、ステッ
プ１２６、１２７、１３６の処理を実行する上で、各調
停ユニット１５は予約リング１４上の調停ユニット１５
の１チャネル当たりの加速係数Ｋと１ポート当たりの加
速係数ｋを知る必要がある。上述のように、予約リング
１４の各調停ユニットの１チャネル当たりの加速係数Ｋ
と１ポート当たりの加速係数ｋはいずれもシステムの初
期化の時点で動的に設定できる。
【００３５】図６は図４のフローチャートのステップ１
１０と１１２の詳細を示すフローチャートであって、調
停ステージにおける交換ネットワーク１０の制限帯域幅
「Ｂ」についての調停ユニット１５による調停の様子を
示したものである。ステップ１３８では、各調停ユニッ
ト１５のカウンタをゼロにリセットして第２回目の調停
処理が開始されたことを示す。ステップ１３８では、
「non-zero ok ＿to＿send destination vector 」を有
した調停ユニット１５がそのバス帯域幅要求を予約リン
グ１４上へシフトして出力する。ステップ１３８で、各
調停ユニット１５からその直近の調停ユニット１５へ調
停要求を転送する。ステップ１４０では、直近の調停ユ
ニット１５からの調停要求がインターフェースシフトレ
ジスタ７４（図２参照）へ入力される。ステップ１４２
では、上記ステップ１２４の場合と同様にタイ・ブレー
カー・トークン（the tie-breaker token ）を更新す
る。
【００３６】ステップ１４４では、クラスタ間交換ネッ
トワーク１０の帯域幅に対して各調停ユニット１５が競
合する。上述のように、クラスタ間交換ネットワーク１
０は帯域幅制限交換ネットワークである。従って、交換
サイクルでは、交換ネットワーク１０の入力チャネル１
２と出力チャネル１３との間に一対一の対応はない。こ
うした帯域幅の制限は、各調停ユニット１５の制御状態
７６に記録されている「B ＿max 」変数を用いて表わさ
れる。また、制御状態７６は、１以上の「B ＿count 」
変数と共に「B ＿count vector」を記録する。すなわ
ち、ステップ１４４では、シフトされた調停要求の優先
順位が常駐調停要求よりも高い場合には、交換機５の
（複数の）交換ネットワーク に対応したB ＿count vec
tor」の「B＿count 」変数の値が増加される。優先順位
の決定は、前記ステップ１２６での優先順位の決定と同
様に行われる。
【００３７】ステップ１４６では、「カウンタ」を評価
することにより、現在の調停サイクルで行ったバス帯域
幅「Ｂ」についての調停要求が予約リングを一巡して予
約リング１４上の各調停ユニット１５にシフトされたか
どうかを判断する。各インターフェースシフトレジスタ
７４が、リングを一巡するシフトに成功した場合は、ス
テップ１５２の処理を実行する。そうでない場合は、ス
テップ１４８の処理を実行する。ステップ１４８では、
「カウンタ」の値を増加させ、予約リング１４上でさら
に調停要求のシフトを行うことを通知する。次に、ステ
ップ１３４では、調停ユニット１５に最も新しく入力さ
れた調停要求を予約リング１４へシフトする。ステップ
１５２の処理が実行されたことは、バス帯域幅に関する
第２番目の調停処理が完了したことを示す。
【００３８】図７は、図４に示すフローチャートのステ
ップ１１４，１１６，１１７の詳細を示すフローチャー
トであり、現在の調停サイクルでどの調停ユニット１５
が優先順位を獲得したかを判断する。ステップ１５２で
は、まず最初に、次の交換サイクルの時に交換ネットワ
ーク１０の要求された宛先である少なくとも１個の出力
チャネル１３のうち少なくとも１つのチャネルへセルを
転送できるかどうかについて第１の判断を下す。各調停
ユニットは、ステップ１３６において「ok＿to＿send d
esignation vector 」の中の少なくとも１つのビットが
出力ポート１６に対して設定されたかどうかを確認する
ことで前記第１の判断を行う。さらに、「ok＿to＿send
designation vector 」に設定されているビットに対応
した宛先出力に関連する「B ＿count vector」の「B ＿
count 」がB ＿max 未満であるかどうかについて各調停
ユニット１５は第２の判断を下す。もし調停ユニット１
５のセルが次の交換サイクルの時に送信されるようスケ
ジュールがなされない場合は、ステップ１５８の処理を
実行する。そうでない場合は、ステップ１５４の処理を
実行する。
【００３９】ステップ１５４では、第１回目と第２回目
のいずれの調停処理においても交換ネットワーク１０に
ついてのアクセスの調停が成功した時は「送信」フラグ
をTRUEに設定する。調停サイクルの終わりに調停ユニッ
ト１５がそのクラスタ制御器２４へ「送信」フラグを送
信する。TRUEに設定された送信フラグを受信すると、次
の交換サイクルの時にクラスタ制御器２４は４交換ネッ
トワーク１０へセルを送信する準備をする。
【００４０】ステップ１５６では、調停に成功したセル
(successful contender)が共有する交換ネットワーク帯
域幅をB ＿count vectorを用いてスケジュールする。調
停に成功したセルが共有の交換ネットワーク帯域幅にア
クセスする時互いに干渉しなければ、資源は適切に配分
される。しかしながら、セルが出力ポートへのアクセス
の調停に成功したという表示によって、次の交換サイク
ルにおいて該出力ポートへそのセルが交換ネットワーク
を経て転送されるようバススロットがスケジュールされ
るのではない。
【００４１】バスを使用した(bus-based) 交換ネットワ
ークでは、競合に勝った調停ユニット１５のそれぞれの
「B ＿counter 」を用いてバス帯域幅の時間スロットを
割り当てる（上述のように、調停ステージの時に調停ユ
ニット１５が別の調停ユニットに対して遅延される都度
「B ＿counter 」を調停サイクルで増加させる）。競合
に勝った調停ユニットの「B ＿counter 」の値を調停ユ
ニット１５から出力された時間「スロットベクトル」に
記憶させる。すなわち、各カウンタの値は各調停ユニッ
トに固有のものであるため、バスの「B ＿counter 」値
を用いて所定セルの時間スロットを特定する。ベクトル
内の各B＿count値は各「Bn」について固有であるため、
「B ＿counter vector」の値が１以上のカウンタの値を
含んでいる時にも上記の原理が当てはまることになる。
他の実施の形態では、時分割(time-multiplexed)ではな
く空間多重化（space multiplexed ）フレームによる並
列ネットワークまたはファブリック形（fabric-based)
ネットワークで「B ＿counter 」を用いている。例え
ば、この実施の形態では、全ての「時間」スロットを使
用して独自の転送ネットワーク(unique routing networ
k)を表すことができる。従って、調停サイクルの最後
に、「B ＿counter 」を用いて複数の入力ポートに指示
を与えて独自の転送ネットワークへセルを出力すること
が可能である。
【００４２】ステップ１５８では、各調停ユニット１５
は、入力チャネル１２がブロックされて（複数の）出力
チャネル１３向けのセルデータを送信できないかどうか
判断する。もし何れの宛先入力チャネル１２(destinati
on input channel 12)がブロックされていない場合は、
ステップ１０２の処理を行う。一方、ブロックされてい
る場合は、ステップ１６０と１６２の処理を実行する。
【００４３】ステップ１６０では、調停ユニット１５の
「n ＿session 」フラグをTRUEに設定して現在の調停サ
イクルでは今行っている調停セッションが完了しない旨
をクラスタモジュール２４へ通知する。調停ユニット１
５は、現在の調停サイクルでは予約が認められなかった
（複数の）宛先出力ポートについての調停要求を次の１
以上の調停サイクルにおいて再送信しなければならな
い。調停要求を再送信する際に、セルデータの固有優先
権を更新して前回不成功に終わった（複数の）調停サイ
クルを反映させてもよい。また、「in＿session 」フラ
グをTRUEに設定して現在の調停セッションを次の調停サ
イクルまで継続することを通知する。ステップ１６２で
は、次の調停サイクルの時に再発行しなくてはならない
出力ポート要求を用いて宛先ベクトルを更新する。再発
行調停要求とは、現在の調停サイクルで調停に成功しな
かった要求のことである。これらの要求には、マルチキ
ャストセルの宛先出力チャネル１３のサブセットが含ま
れている。
【００４４】マッケオン（Mackeown）らは、「入力待ち
行列形交換機におけるマルチキャストセルのスケジュー
リング（Scheduling Multicast Cells In An Input-Que
uedSwitch」、ＩＥＥＥ ＩｎｆｏＣｏｍ、１９９６年
３月発行（ＩＳＳＮ ０７４３−１６６Ｘ）において、
入力待ち行列式マルチキャストＡＴＭ交換機におけるセ
ルのスケジューリングに関するワーク保存方式（work-c
onserving policy）を開示している。このワーク保存方
式は、数回の交換サイクル（即ち、セル期間）にわたっ
て、マルチキャストセルを、その特定の宛て先ポートに
コピーすることを可能にする。
【００４５】図１の交換機５は、ワンパスにおけるクラ
スタ間交換ネットワーク１０を介してのマルチキャスト
またはブロードキャスト・オペレーションを効率的に管
理する。ユニキャスト・トラフィックと異なり、クラス
タモジュール８はセルをマルチキャスト・トラフィック
として認識すると、そのマルチキャストセルは、メモリ
２８内の入力待ち行列に送られ、その後交換ネットワー
ク上を介して転送される。交換待ち潜伏性と交換ネット
ワークの負荷を軽減させる他の実施の形態では、クラス
タモジュール内のポートに宛て先指定されたマルチキャ
スト・トラフィックは入力待ち行列に送られるのではな
く、クラスタモジュール内の出力待ち行列に送られるこ
とにより交換ネットワーク上への転送が回避される。
【００４６】前述のように、図４は各調停ユニット１５
が行う全体的なステップを示すフローチャートである。
先に定義したように、調停「サイクル」は出力チャネル
に関する調停のための第１回目の調停処理（ステップ１
０６及び１０８）及び交換ネットワーク帯域幅に関する
調停のための第２回目の調停処理（ステップ１１０及び
１１２）から成る。調停ユニット１５は、出力チャネル
のコンテンションまたは交換帯域のコンテンションのい
ずれかが原因となって、マルチキャストセルの各宛先チ
ャネル１３に関しての調停を調停サイクル中に成功でき
ない。マルチキャストセルの出力宛先に予約が割り当て
られた場合、送信ＯＫ宛先ベクトル（ok＿to＿send-des
tinaion vector）が該出力宛先に設定され、マルチキャ
ストセルは次の交換サイクル中に交換ネットワーク上へ
出力される。しかし、マルチキャストセルの出力宛先に
予約が割り当てられない場合、マルチキャストセルは該
出力宛先のための次の調停サイクル中に再発行される。
調停セッションは、セッションの一部である全ての要求
に予約が割り当てられた時に完了する。二以上の調停サ
イクルにわたる調停セッションは、通常、連続する調停
サイクルにわたっている。ただし、調停セッションは、
マルチキャストセルを複数の連続しない交換サイクルに
わたって転送する結果に終わる場合もある。
【００４７】予約が割り当てられた各出力ポートは、各
調停ユニット１５のステート・ロジック内に格納される
送信ＯＫ宛先ベクトルに記録される。送信ＯＫ宛先ベク
トルの各ビットは、交換機５の宛先ポートと対応する。
調停サイクルの終了時に、送信ＯＫ宛先ベクトルは、グ
ラント・ライン８３上に出力され交換ネットワークイン
タフェース１８に到る。集積回路内のピン数を削減する
他の実施の形態においては、送信ＯＫ宛先ベクトルのビ
ットは出力ポート識別子に置き換えられる。
【００４８】図８乃至図１０は、マルチキャスト調停を
実行する予約リング１４の概略図である。図８乃至図１
０に示す予約リング１４は、３個の調停ユニット１５を
含む。各調停ユニットの内部レジスタはその全体が参照
番号７３で示され、インタフェース・シフト・レジスタ
はその全体が参照番号７４で示される。各調停ユニット
は、常駐宛先ベクトル８４、常駐優先値８５、シフト宛
先ベクトル８６及びシフト優先値８７を備える。常駐宛
先ベクトル８４とシフト宛先ベクトル８６は各自３個の
ビットＰ１，Ｐ２及びＰ３を有する。３個のビットＰ
１，Ｐ２及びＰ３は、交換ネットワーク１０の３個の出
力チャネル１３に対応する。各クラスタモジュール１５
の一部は比較器８８と８９によって構成されている。比
較器８８は二つの値が一致するか否かを判定し、比較器
８９は一方の値が他方より大きいか否かを判定する。ま
た、各クラスタモジュールは宛先Ｋカウンター・ベクト
ル８２のアレイを有し、このベクトルは常駐宛先ベクト
ル８４内に画定される出力チャネル１３を示す各ビット
毎に一個のＫカウンター（k＿counter）を記録する。上
記に定義したように、各出力チャネル１３は一以上の宛
先出力ポート１６と関連付けられている。
【００４９】図８乃至図１０に示す予約リング１４の各
調停処理は、三つの調停ステージから成る。第１調停ス
テージでは、各調停ユニットは自身の常駐宛先ベクトル
８４を自身のシフト宛先ベクトル８６に複写する。また
第１調停ステージでは、各調停ユニットは自身のＫカウ
ンター・ベクトル (k＿counter vector)８２の各Ｋカウ
ンターの値をゼロリセットする。第２及び第３調停ステ
ージを開始する前に、予約リングはインタフェース・シ
フト・レジスタ・ベクトル７４を調停リング・ライン１
７上にシフトする。第２及び第３調停ステージの間中、
各調停ユニット１５は常駐宛先ベクトル８４の各ビット
Ｐ１，Ｐ２及びＰ３がシフト宛先ベクトル８６の各ビッ
トＰ１，Ｐ２及びＰ３とそれぞれ一致するか否かを判定
する。３個のビットＰ１，Ｐ２及びＰ３のそれぞれに対
する比較器８８のいずれかが、常駐宛先ベクトルとシフ
ト宛先ベクトルが同一の出力チャネル１３を要求してい
ることを示している場合、比較器８９は常駐宛先ベクト
ルとシフト宛先ベクトルのいずれが優先権をもっている
かを判断する。常駐優先値８５及びシフト優先値８７は
優先権論理因子（booleans）、即ち上述し且つ図３に示
した「valid 」、「T」、「Rsv」、「MCast」及び「in
＿session」を含む。シフト優先権が常駐優先権より勝
るときは、該宛先ビットに対応するＫカウンターは加算
される。
【００５０】Ｋカウンター・ベクトル８２のいずれかの
Ｋカウンターの値が最大値（例えば図３に示す dest ＿
K ＿max ）に達した場合、調停中のセルは次の調停サイ
クル中に１組の関連する宛先ビットによって再調停され
る。各調停ステージは各調停ユニットにつき唯一の優先
権を設定しているので、交換ネットワーク１０における
正確な入出力マッピングを定義するためにそのＫカウン
ターの値を用いることができる。一以上のＫカウンター
が一個の調停ユニット１５に関するdest＿K ＿max より
小さいかもしれないので、複数の出力チャネル１３は単
一の入力チャネル１２からデータパケットを受け取るこ
とができる。交換ファブリック（fabric）をクロスバー
ファブリックとした他の実施の形態では、複数のクロス
バー出力チャネルは、単一の入力チャネルからセルを受
け取ることができる。これは、マルチキャストセルのた
めのコピーメカニズムとして働く。交換ネットワークを
バスとした他の実施の形態では、マルチキャストセルの
コピーは複数の出力チャネルがバスから同時に読込むこ
とによって行われる。
【００５１】またその他の実施の形態では、マルチキャ
ストセルによるブロッキングが長びくのを回避するた
め、マルチキャスト・パケットの全ての出力宛先がステ
ップ１１６（図２）で発行される前に、調停要求は終了
される。この実施の形態では、調停ユニット１５は、不
成功に終わった調停要求をクラスター制御器２４に送り
返す。この時、ステップ１０２において、クラスター制
御器は返送された調停要求を再発行するか新たな調停要
求を発行するかを決定する。
【図面の簡単な説明】
【図１】本発明を適用したモジュール式階層ＡＴＭ（非
同期転送モード）交換機の概略図である。
【図２】図１のモジュール式階層交換機内で動作する予
約リングの概略図である。
【図３】調停ユニットの制御状態を示す概略図である。
【図４】調停セッション中に各調停ユニットが実行する
全般的ステップを示したフローチャートである。
【図５】図４の出力チャネルと出力ポートの調停に関す
るステップ１０６と１０８の詳細を示すフローチャート
である。
【図６】図４の交換ファブリック帯域幅の調停に関する
ステップ１１０と１１２の詳細を示すフローチャートで
ある。
【図７】図４の現在の調停サイクルをどの調停ユニット
に割り当てるかを判断する処理に関するステップ１１
４、１１６、１１７の詳細を示すフローチャートであ
る。
【図８】マルチキャスト調停を実行する予約リング１４
を示す概略図である。
【図９】マルチキャスト調停を実行する予約リング１４
を示す概略図である。
【図１０】マルチキャスト調停を実行する予約リング１
４を示す概略図である。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ブライアン ティー．プリース アメリカ合衆国 94301 カリフォルニア 州 パロ アルト カウパー ストリート 151 (72)発明者 アラン ジー．ベル アメリカ合衆国 94301 カリフォルニア 州 パロ アルト エマーソン ストリー ト 2125 (72)発明者 ジョセフ ビー．ライルズ アメリカ合衆国 94043 カリフォルニア 州 マウンテン ビュー ローラ レーン 2403 (72)発明者 ダニエル エイチ．グリーン アメリカ合衆国 94087 カリフォルニア 州 サニーベイル マネ ドライブ 1055 ナンバー６

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】 交換ネットワーク及び予約リングを備え
    た交換機であって、交換ネットワークが，交換サイクル
    中、Ｉ個の入力チャネルの内の選択されたものからＪ個
    の出力チャネルの内の選択されたものへ単一パス・マル
    チキャスト・パケットを転送し、交換サイクル中、予約
    リングが同一の出力チャネルについての入力チャネル間
    の競合を解消するようにした交換機において、該予約リ
    ングを備えた交換ネットワークの宛先出力チャネルに対
    するマルチキャスト・パケット・アクセスを調停する方
    法であって、 １組の宛先出力チャネルを示す調停要求を発して、マル
    チキャストセルに関する調停セッションを開始するステ
    ップと、 調停サイクル中、当該１組の宛先出力チャネルの各宛先
    出力チャネルへのアクセスを調停するステップと、 調停サイクル完了後、予約を割り当てられた宛先出力チ
    ャネルを当該一セット宛先出力チャネルから除去するス
    テップと、 上記の調停ステップと除去ステップを連続する調停サイ
    クルにわたって繰り返し、１組の宛先出力チャネルの各
    宛先出力チャネル全てに予約が割り当てられたときに調
    停セッションを終了させる繰り返しステップとを含むマ
    ルチキャスト・パケット・アクセス調停方法。
JP31949797A 1996-11-21 1997-11-20 マルチキャスト・パケット・アクセス調停方法 Expired - Fee Related JP4381490B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US754726 1996-11-21
US08/754,726 US5835491A (en) 1996-11-21 1996-11-21 Method for supporting multicast capabilities in switching networks with a reservation ring

Publications (2)

Publication Number Publication Date
JPH10164096A true JPH10164096A (ja) 1998-06-19
JP4381490B2 JP4381490B2 (ja) 2009-12-09

Family

ID=25036050

Family Applications (1)

Application Number Title Priority Date Filing Date
JP31949797A Expired - Fee Related JP4381490B2 (ja) 1996-11-21 1997-11-20 マルチキャスト・パケット・アクセス調停方法

Country Status (2)

Country Link
US (1) US5835491A (ja)
JP (1) JP4381490B2 (ja)

Families Citing this family (51)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2308959A (en) * 1995-12-29 1997-07-09 Ericsson Telefon Ab L M Data switching apparatus with fair queuing
US6446125B1 (en) 1997-03-28 2002-09-03 Honeywell International Inc. Ripple scheduling for end-to-end global resource management
US6115756A (en) 1997-06-27 2000-09-05 Sun Microsystems, Inc. Electro-optically connected multiprocessor and multiring configuration for dynamically allocating time
US6246680B1 (en) * 1997-06-30 2001-06-12 Sun Microsystems, Inc. Highly integrated multi-layer switch element architecture
US6115378A (en) * 1997-06-30 2000-09-05 Sun Microsystems, Inc. Multi-layer distributed network element
US6044418A (en) 1997-06-30 2000-03-28 Sun Microsystems, Inc. Method and apparatus for dynamically resizing queues utilizing programmable partition pointers
US6119196A (en) 1997-06-30 2000-09-12 Sun Microsystems, Inc. System having multiple arbitrating levels for arbitrating access to a shared memory by network ports operating at different data rates
US6049528A (en) 1997-06-30 2000-04-11 Sun Microsystems, Inc. Trunking ethernet-compatible networks
US6016310A (en) 1997-06-30 2000-01-18 Sun Microsystems, Inc. Trunking support in a high performance network device
US6021132A (en) * 1997-06-30 2000-02-01 Sun Microsystems, Inc. Shared memory management in a switched network element
US6094435A (en) 1997-06-30 2000-07-25 Sun Microsystems, Inc. System and method for a quality of service in a multi-layer network element
US6072805A (en) * 1997-06-30 2000-06-06 Sun Microsystems, Inc. Observing arbiter
US6081512A (en) 1997-06-30 2000-06-27 Sun Microsystems, Inc. Spanning tree support in a high performance network device
US6044087A (en) 1997-06-30 2000-03-28 Sun Microsystems, Inc. Interface for a highly integrated ethernet network element
US6088356A (en) 1997-06-30 2000-07-11 Sun Microsystems, Inc. System and method for a multi-layer network element
US6081522A (en) 1997-06-30 2000-06-27 Sun Microsystems, Inc. System and method for a multi-layer network element
US6477169B1 (en) * 1999-05-14 2002-11-05 Nortel Networks Limited Multicast and unicast scheduling for a network device
US6628646B1 (en) 1999-05-14 2003-09-30 Nortel Networks Limited Programmable multicast scheduling for a network device
US6519225B1 (en) 1999-05-14 2003-02-11 Nortel Networks Limited Backpressure mechanism for a network device
US6661788B2 (en) 1999-05-14 2003-12-09 Nortel Networks Limited Multicast scheduling for a network device
US6765918B1 (en) * 1999-06-16 2004-07-20 Teledata Networks, Ltd. Client/server based architecture for a telecommunications network
CA2293920A1 (en) * 1999-12-31 2001-06-30 Nortel Networks Corporation Global distributed switch
US7165257B2 (en) 2000-02-08 2007-01-16 Mips Technologies, Inc. Context selection and activation mechanism for activating one of a group of inactive contexts in a processor core for servicing interrupts
US7082552B2 (en) 2000-02-08 2006-07-25 Mips Tech Inc Functional validation of a packet management unit
US7155516B2 (en) * 2000-02-08 2006-12-26 Mips Technologies, Inc. Method and apparatus for overflowing data packets to a software-controlled memory when they do not fit into a hardware-controlled memory
US7502876B1 (en) 2000-06-23 2009-03-10 Mips Technologies, Inc. Background memory manager that determines if data structures fits in memory with memory state transactions map
US7649901B2 (en) 2000-02-08 2010-01-19 Mips Technologies, Inc. Method and apparatus for optimizing selection of available contexts for packet processing in multi-stream packet processing
US7058064B2 (en) * 2000-02-08 2006-06-06 Mips Technologies, Inc. Queueing system for processors in packet routing operations
US7032226B1 (en) 2000-06-30 2006-04-18 Mips Technologies, Inc. Methods and apparatus for managing a buffer of events in the background
US7020161B1 (en) 2000-03-31 2006-03-28 Sun Microsystems, Inc. Prescheduling arbitrated resources
US6882649B1 (en) 2000-03-31 2005-04-19 Sun Microsystems, Inc. Least choice first arbiter
US7006501B1 (en) * 2000-03-31 2006-02-28 Sun Microsystems, Inc. Distributed least choice first arbiter
US6804731B1 (en) 2000-08-11 2004-10-12 Paion Company, Limited System, method and article of manufacture for storing an incoming datagram in switch matrix in a switch fabric chipset system
US6724759B1 (en) 2000-08-11 2004-04-20 Paion Company, Limited System, method and article of manufacture for transferring a packet from a port controller to a switch fabric in a switch fabric chipset system
EP1228609A1 (en) * 2000-08-11 2002-08-07 Paion Company, Limited Novel switch fabric chipset system and method
US6731631B1 (en) 2000-08-11 2004-05-04 Paion Company, Limited System, method and article of manufacture for updating a switching table in a switch fabric chipset system
US6993024B1 (en) * 2000-11-16 2006-01-31 Chiaro Networks, Ltd. System and method for router multicast control
EP1294143A3 (de) * 2001-09-03 2008-04-02 Nokia Siemens Networks Gmbh & Co. Kg Gekennzeichneter Prioritätwarteschlangescheduler
US7054330B1 (en) * 2001-09-07 2006-05-30 Chou Norman C Mask-based round robin arbitration
GB2381407B (en) * 2001-10-24 2004-06-30 Zarlink Semiconductor Ltd Dynamic buffering in packet systems
US7239646B1 (en) 2002-01-17 2007-07-03 Juniper Networks, Inc. Hierarchical round robin arbiter
US7352741B2 (en) * 2002-02-21 2008-04-01 Sun Microsystems, Inc. Method and apparatus for speculative arbitration
US7151777B2 (en) * 2002-04-04 2006-12-19 Fujitsu Limited Crosspoint switch having multicast functionality
US7433953B1 (en) * 2003-04-24 2008-10-07 Cisco Technology, Inc. Methods and apparatus for reducing arbitration delay in channelized systems by use of additional scheduling hierarchy
US20050117575A1 (en) * 2003-10-30 2005-06-02 Venkat Konda Nonblocking and deterministic unicast packet scheduling
JP2007510378A (ja) * 2003-10-30 2007-04-19 チーク テクノロジーズ，インク． ノンブロッキングで決定論的マルチレートユニキャストパケットスケジューリング
JP2007510379A (ja) * 2003-10-30 2007-04-19 チーク テクノロジーズ，インク． ノンブロッキングで決定論的マルチキャストパケットスケジューリング
JP4354379B2 (ja) * 2004-10-04 2009-10-28 株式会社日立製作所 帯域制御装置
US8300658B2 (en) * 2007-03-21 2012-10-30 Motorola Mobility Llc Apparatuses and methods for multi-antenna channel quality data acquisition in a broadcast/multicast service network using a multicast symbol
US7817653B2 (en) * 2007-04-19 2010-10-19 Hewlett-Packard Development Company, L.P. Priority selection circuit
US8085801B2 (en) * 2009-08-08 2011-12-27 Hewlett-Packard Development Company, L.P. Resource arbitration

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4531238A (en) * 1981-12-03 1985-07-23 Xerox Corporation Statistical contention control for star configured communication networks
US5130984A (en) * 1990-12-18 1992-07-14 Bell Communications Research, Inc. Large fault tolerant packet switch particularly suited for asynchronous transfer mode (ATM) communication
US5327420A (en) * 1992-05-20 1994-07-05 Xerox Corporation Method for building multi-bit parallel Batcher/banyan networks
US5305311A (en) * 1992-05-20 1994-04-19 Xerox Corporation Copy network providing multicast capabilities in a broadband ISDN fast packet switch suitable for use in a local area network
JPH0637797A (ja) * 1992-05-20 1994-02-10 Xerox Corp パケット交換網の予約リング機構
JP2655464B2 (ja) * 1992-12-25 1997-09-17 日本電気株式会社 パケット交換方式
FR2710167B1 (fr) * 1993-09-13 1995-11-24 Ouest Standard Telematique Sa Dispositf de commutation d'unités de protocole à haut débit, et procédé de commutation correspondant.
US5517495A (en) * 1994-12-06 1996-05-14 At&T Corp. Fair prioritized scheduling in an input-buffered switch

Also Published As

Publication number Publication date
US5835491A (en) 1998-11-10
JP4381490B2 (ja) 2009-12-09

Similar Documents

Publication Publication Date Title
JP4381490B2 (ja) マルチキャスト・パケット・アクセス調停方法
JP3936044B2 (ja) アクセス調停方法
US5912889A (en) ATM switch with output port clustering for dynamically allocating bandwidth between ports
US6044061A (en) Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch
US6160812A (en) Method and apparatus for supplying requests to a scheduler in an input buffered multiport switch
US6477169B1 (en) Multicast and unicast scheduling for a network device
EP0569172B1 (en) Improved controller for input-queued packet switch
JP4796149B2 (ja) 相互接続の待ち時間を低減するための方法及びシステム
US6963576B1 (en) Scheduling and arbitration scheme for network processing device
US8005092B2 (en) Two-dimensional pipelined scheduling technique
US6426957B1 (en) Asynchronous transfer mode based service consolidation switch
US6185221B1 (en) Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch
US20030174701A1 (en) Multicast scheduling for a network device
JPH09512152A (ja) 遠距離通信のスイッチングのための調停方法
US20040160970A1 (en) Methods and apparatus for event-driven routing
JP2000506701A (ja) 効率的な出力―要求パケット交換機および方法
JPH0338137A (ja) 高速デイジタル・パケット交換システム
US20030231588A1 (en) Method and apparatus for multicast and unicast scheduling
US5883895A (en) Arbitration ring with automatic sizing for a partially populated switching network
US7773616B2 (en) System and method for communicating on a richly connected multi-processor computer system using a pool of buffers for dynamic association with a virtual channel
US6643294B1 (en) Distributed control merged buffer ATM switch
US7103056B2 (en) Scheduling the dispatch of cells in multistage switches using a hierarchical arbitration scheme for matching non-empty virtual output queues of a module with outgoing links of the module
US7486687B2 (en) Method and allocation device for allocating pending requests for data packet transmission at a number of inputs to a number of outputs of a packet switching device in successive time slots
US7773617B2 (en) System and method for arbitration for virtual channels to prevent livelock in a richly-connected multi-processor computer system
JP4568364B2 (ja) 相互接続ファブリックにおいてユニキャスト・トラフィック及びマルチキャスト・トラフィックをスケジューリングする方法、装置、及びコンピュータ・プログラム（相互接続ファブリックにおいてユニキャスト・トラフィック及びマルチキャスト・トラフィックをスケジューリングする方法及び装置）

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20041108

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060523

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060814

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20061024

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20070213

A911 Transfer to examiner for re-examination before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20070227

A912 Re-examination (zenchi) completed and case transferred to appeal board

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20070406

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20090916

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121002

Year of fee payment: 3

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20131002

Year of fee payment: 4

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

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees