JPH0637799A - トランクグループ入力／出力モードを備えた交換機 - Google Patents

トランクグループ入力／出力モードを備えた交換機

Info

Publication number
JPH0637799A
JPH0637799A JP10818093A JP10818093A JPH0637799A JP H0637799 A JPH0637799 A JP H0637799A JP 10818093 A JP10818093 A JP 10818093A JP 10818093 A JP10818093 A JP 10818093A JP H0637799 A JPH0637799 A JP H0637799A
Authority
JP
Japan
Prior art keywords
network
output
cell
input
cells
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
JP10818093A
Other languages
English (en)
Other versions
JP3447321B2 (ja
Inventor
Joseph B Lyles
ビー ライルズ ジョセフ
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 JPH0637799A publication Critical patent/JPH0637799A/ja
Application granted granted Critical
Publication of JP3447321B2 publication Critical patent/JP3447321B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime 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
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/10—Routing in connection-oriented networks, e.g. X.25 or ATM
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • 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/104—Asynchronous transfer mode [ATM] switching fabrics
    • H04L49/105—ATM switching elements
    • H04L49/107—ATM switching elements using shared medium
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/15—Interconnection of switching modules
    • H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
    • H04L49/1561—Distribute and route fabrics, e.g. Batcher-Banyan
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/15—Interconnection of switching modules
    • H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
    • H04L49/1576—Crossbar or matrix
    • 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/25—Routing or path finding in a switch fabric
    • H04L49/256—Routing or path finding in ATM switching fabrics
    • H04L49/258—Grouping
    • 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/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/565—Sequence integrity
    • 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)
  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Small-Scale Networks (AREA)
  • Interface Circuits In Exchanges (AREA)

Abstract

(57)【要約】 【目的】より高速の入力および（または）出力にサービ
スするために、多数の経路指定ネットワークを有する非
ブロッキング自己経路指定式交換網をトランクグループ
化入力モードおよび（または）出力モードで動作させる
ことである。 【構成】非トランクグループ化入力からパケットによっ
て指定されたバーチャル回線上のトランクグループ化出
力および非トランクグループ化出力へパケツトを交換す
る非ブロッキング自己経路指定式交換網を有する交換機
において、交換網は分類ネットワークと、その次に配置
され、複数の入力を同一出力へ同時にアクセスさせる複
数の経路指定ネットワークを有し、各バーチャル回線上
のパケットの順序を予約する手段を備えている。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、高速広帯域通信ネット
ワーク、より詳細には、高性能ローカルエリアネットワ
ーク（ＬＡＮ）に関するものである。
【０００２】
【従来の技術】研究プロジェクトやシステムプロダクト
は、ほどなく既設のＬＡＮの容量を越える帯域幅、応答
性および（または）リアルタイムの諸要求をもつであろ
う。たとえば、私文書から技術文献に及ぶ文書について
紙から電子書式への移行が進行中であり、そのために進
歩した電子走査装置や印刷装置が開発された。これらの
装置は、装置の速度や解像度が増しているほか、装置の
カラーやグレースケール容量が拡大されているため、そ
の帯域幅の要求は拡大し続けるであろう。改良型ＬＡＮ
に対する要求のもう１つの例は、壁サイズ表示装置をベ
ースとする会議支援装置とライブビデオリンクを使用す
るゼロックスメデアスペース（Xerox Media Space)な
ど、出現しつつあるいくつかの共同制作技術によって考
えられている高品質ビデオイメージに集中している。さ
らに、高性能コンピュータは、計算資源、高性能ファイ
ルサーバー、視覚化ワークステーション、等として使用
できるようになりつつあるが、現在使用されているＬＡ
Ｎは、これらの高性能コンピュータを支援するのに必要
な容量を備えていない。
【０００３】需要の多い潜在的な科学計算や視覚化アプ
リケーションは、ギガビット／秒（Gbps ) のデータ伝
送速度を必要とするが、大多数の知覚アプリケーション
には10 〜 100メガビット／秒（ Mbps ）の帯域幅で十
分である。しかし、リアルタイムビデオなど、一部の知
覚アプリケーションは、ネットワークに長い連続負荷を
にかけるし、また二点間（unicast ）リンクのほかに、
１対多（multicasting）伝送を要求するであろう。従っ
て、ごく普通のユーザー共同体を同時にサポートするた
めに、ＬＡＮがほどなく 10 〜 40 Gbpsの総合帯域幅を
必要とするであろうという仮定は妥当である。異なるユ
ーザー共同体は一般に異なるニーズを有しており、また
あらゆるユーザー共同体の要求は一般に時間と共に膨ら
むので、ユーザー共同体の要求を優雅にかつ経済的に満
たすためにスケール（scale)する高性能ＬＡＮが要望さ
れている。
【０００４】
【発明が解決しようとする課題】既知のＦＤＤＩ（Fibe
r Distributed Data Interface) ネットワークは、本発
明が考えているＬＡＮのピーク帯域幅要求も、総合帯域
幅要求も満足させることができない。また、クロスバー
交換機または高速同報通信バスをベースとする技術な
ど、最近開発された他の多くの技術は、提案されたＬＡ
Ｎのマルチキャスト（muticast) 、同報通信(broadcas
t) 、および（または）余裕度(affordability) の諸要
求を満たすことができないように思われる。
【０００５】
【課題を解決するための手段】非トランクグループ化入
力からパケットによって指定されたバーチャル回線上の
トランクグループ化出力および非トランクグループ化出
力へパケットを交換する非ブロッキング自己経路指定式
交換網を有する交換機において、前記交換網は複数の入
力を同一出力へ同時にアクセスさせるために、分類ネッ
トワークと前記分類ネットワークの次に配置された複数
の経路指定ネットワークを有している。本発明に従っ
て、交換機は前記各バーチャル回線上のパケットの順序
を予約する手段を備えている。
【０００６】
【実施例】Ｉ．定義 以下の用語は、ここで使用する場合には以下の意味を有
する。
【０００７】「チャンネルレート（channel rate) 」と
は、特定のストリーム、チャンネル、等、たとえば単一
テレビジョン伝送、ファイル転送、データベーストラン
ザクションのビットレートである。
【０００８】「リンクレート（link rate)」とは、ネッ
トワークのデバイス（ホスト、ルータ、交換機）が個別
リンク（一対の電線、同軸ケーブル、光ファイバー）上
で維持することができる、または維持しなければならな
いビットレートである。このレートは、チャンネルレー
トの上限である。また、このレートはインタフェースの
ハードウェアのコストや、ネットワークプロトコルのハ
ードウェアやソフトウェアのコストに大きな影響を及ぼ
す。
【０００９】「総合レート(aggregate rate)」とは、同
時に伝送することができる最大数のリンクについてリン
クレートの合計として表される最大総合ネットワーク容
量である。バスまたはリングとして具体化されたネット
ワーク、すなわち単一周波数無線同報通信を使用するネ
ットワークの場合、リンクレートは総合レートと同じで
ある。逆に、通常の電話交換システムは、どんなリンク
のレートよりもはるかに高い総合レートが得られる。
【００１０】II. 基本的アーキテクチャ 本発明のＡＴＭ ＬＡＮは、ＡＴ＆Ｔ/Bellcore によっ
て開発された形式の VLSI ベース”Batcher/banyan”ネ
ットワークを使用して具体化することができる。理解さ
れるように、このＬＡＮは、 115 Mbps のリンクレート
で動作するユニキャストおよびマルチキャストバーチャ
ル回線をサポートし、リンクレートを600 Mbpsまで増や
す用意がなされている。ここに開示する具体化において
は、各交換機は３２ポートをサポートするであろう。し
かし、Batcher/banyanネットワークは、２５６ポートよ
り大きな交換機や、（一部には、ここに開示した進歩の
ために、）１ギカビット／秒以上のリンクレートに対し
スケールするであろうと思われる。また、より大きなユ
ーザー共同体をサポートするために、これらの交換機を
相互に接続し、より大きな階層型ネットワークを作るこ
とができる。
【００１１】ＡＴＭ交換の魅力の１つは、標準規格にな
るのもかなり近いことである。この形式のネットワーク
の基本的概念は、すべての通信が「セル」と呼ばれる小
さい固定サイズデータパケットの送信と交換によって行
われることである。バーチャル回線技法を使用すること
によって各パケットのオーバーヘッドが減るので、各セ
ルのヘッダーはソースと宛先間のすべての交換機によっ
てあらかじめ設定された経路を識別する。そのため、セ
ルおよびその望ましい経路指定を識別するために必要な
情報は、通常のＸＮＳまたはＴＣＰ／ＩＰデータグラム
の場合のヘッダー情報よりもかなり少ない。ＡＴＭ標準
規格作成活動やその技術的内容に興味のある人は、ＣＣ
ＩＴＴ (International Telegraph and Telphone Consu
ltativeCommittee)の Study Groups XI および XVIII
およびＡＮＳＩ (American National Standards Insti
tute) sub-committee Ｔ１Ｓ１により公表された上記
主題の論文を参照されたい。
【００１２】明らかになりつつあるＡＴＭ標準規格に従
って、セルは小さい固定サイズ（５３バイト）パケット
である。そのヘッダーに宛先バーチャル回線インデック
ス（Virtual Circuit Index ；ＶＣＩと略す）として知
られる宛先アドレッシング情報が入っている。そのほか
に、バーチャルパスインデックス（Virtual Path Inde
x；ＶＰＩと略す）があるが、バーチャルパス上の交換
は本質的にバーチャル回線上の交換に等しいので、バー
チャルパスインデックスについての詳細は省略する。セ
ルが交換網に入る前に、ソースホストは、セルをそのソ
ースから宛先へ転送する「バーチャル回線（Virtual Ci
rcuit ）」として知られる固定ルートを決定する。この
バーチャル回線の切り換えられた各リンク（各交換機間
リンクおよび各交換機宛先間リンク）は、交換機特定バ
ーチャル回線識別子（ＶＣＩ′）によって独自に識別さ
れる。従って、１つのバーチャル回線は多数の名前を有
する。セルはバーチャル回線に沿ったどの点でも再順序
付けができないので、セルはそれらが送出された順序で
到着するはずである。
【００１３】上記のことを心に留めて第１図を見ると、
階層型ＬＡＮ２１は、１つまたはそれ以上のソース３
１，３２から１つまたはそれ以上の宛先３３へセルたと
えばＡＴＭセル２７を転送する複数の自己経路指定非ブ
ロッキング式交換機２２〜２５で構成されていることが
わかる。たとえば、ＬＡＮの場合には、ソース３１，３
２はワークステーションであってもよいし、宛先３３は
ファイルサーバであってもよい。図示のように、ＬＡＮ
２１は２段階の階層を有するが、階層は、Metroporitan
Area Networks（ＭＡＮｓ）や Wide Area Networks
（ＷＡＮｓ）を含む、かなり長い経路を通してパケット
の移送および交換を行うように拡張できることは明らか
であろう。
【００１４】次に、図２について説明する。交換機２２
〜２５はそれぞれのバッチャー／バンヤン（batcher/ba
nyan) ネットワーク４１によって適当に構成されてい
る。図示のように、交換機２２の場合は、単一ｎポート
バッチャー分類ネットワーク４２が、ある数ｋ（一般
に、２または３）のバイヤン経路指定ネットワーク４
３，４４へセルを提供する。バンヤン経路指定ネットワ
ーク４３，４４は、同一セル交換サイクルの間にどのセ
ルも紛失させずに、ｋ個のセルを同一出力ポート番号へ
経路指定できるように接続されている。この並行処理に
適応させるため、バンヤン経路指定ネットワーク４３，
４４から１サイクル当たり最大ｋ個のセルを受け入れる
ように作られた比較的大きな（数千個のセル）ＦＩＦＯ
バッファ４５が各出力ポートに設けられている。ＦＩＦ
Ｏバッファ４５は、実時間トラヒックと「最善努力」ト
ラヒックの両方を取り扱うために、２個のＦＩＦＯバッ
ファ（図示せず）、すなわちレート制限付きすなわち予
約トラヒックのための数百個のセルから成る小さいＦＩ
ＦＯバッファと、未予約トラヒックのための相当大きな
ＦＩＦＯバッファとで構成されていることが好ましい。
小さいＦＩＦＯバッファのサイズは、レート制限付きス
トリームの周期のほぼ２倍に制限される。問題のレート
について、これは予約トラヒックのためのＦＩＦＯバッ
ファを少なくとも 200〜300 セルのサイズにすべきこと
を意味する。厳格なレート限界によって制限されない
「バースト」トラヒックの場合は、バーチャル回線はよ
り大きなＦＩＦＯバッファ（最善努力トラヒック）に待
機させられる。決められた出力ポートに対しアクセスし
ている各入力ポートについて、少なくとも１個のフルデ
ータグラム分のバッファリングがあれば、伝送制御プロ
トコル（ＴＣＰ）は有効に実行することが判る。従っ
て、Ｎ個の全ポートが１出力へ同時にＴＣＰパケットを
送るであろうＮポート交換機の場合は、より大きな出力
ＦＩＦＯバッファ内に約４×４Ｋバイト分のバッファリ
ングが必要である。知られているように、これらのサイ
ズのＦＩＦＯバッファはＳＲＡＭから簡単に作られる。
【００１５】理解されるように、仮に単一交換サイクル
の間にｋ個以上のセルを同一出力ポート番号へ送られる
ようなことがあれば、交換機は単に過剰のセルを落とす
というよりは、予想されるように実行するのに失敗する
であろう。従って、この状況は避けなければならない。
そのため、一般に認められている慣例に従って、そのよ
うな対立するセル間の競合を公平に裁くと同時に、どの
サイクルにおいても多くてもｋ個のセルを交換機へ与え
る予約リング４６が設けられている。以下詳しく説明す
るように、この予約リング４６は、短縮アレイ（systol
ic array) を作るためすべてのポートを通して配線され
た一組の回路（各ポートにつき１個の回路）で構成され
ている。
【００１６】交換網４１および予約リング４６の入力側
に接続されているのは、ｎ×ｎコピーネットワーク４８
である。コピーネットワーク４８は在庫または特注のク
ロスバー交換機の構成部品を使用して作ることができ
る。すべてのセルは、スイッチヘッダー内のマルチキャ
ストビットの状態によって、二地点間セルまたはマルチ
キャストセルとして特別に標識が付けられる。理解され
るように、ＡＴＭセルを交換網４１を通して経路指定
し、ＦＩＦＯバッファ４５において適当な出力待ち行列
に入れるために、ＡＴＭセルにスイッチヘッダーが事前
に付けられている。入ってきたマルチキャストセルは、
コピーネットワークを迂回し、交換網４１に通される
が、そのとき交換網４１でインタセプトされ、出力回線
へ送られずに、コピーネットワーク４８へ戻される。
【００１７】詳しく述べると、マルチキャストセルのヘ
ッダー内の宛先バーチャル回線インデックス（ＶＣＩ）
は、個々の宛先でなく、グループを識別する。従って、
交換ネットワーク４１を通るマルチキャストセルの最初
のパスにより、セルはコピーネットワーク４８の入力へ
送られる。コピーネットワーク４８はセルのコピーをＣ
個（または、たぶんもう少し多い）作成することができ
る。ここで、Ｃはセルがアドレスされたグループのサイ
ズである。交換機２２〜２５のような階層形態の交換機
を取り扱う必要がある場合には、ある程度の複雑になる
が、この複雑さによってハードウェアが複雑になること
はない。セルのコピーがコピーネットワーク４８から出
ていくとき（しかし、交換ネットワーク４１に入る前
に）、事前にプログラムされたパーポートマッピング
（per-port mapping) ハードウェア（図示せず）が各コ
ピーを異なるグループ番号へアドレスする。これを実行
するために、コピーネットワーク４８の各出力ポートに
ある別個のテーブルが、一般にグループ番号によってイ
ンデックスされる。前記テーブルにはグループ番号に対
する出力ポート番号が入っているので、コピーネットワ
ーク４８の決められたどの入力ポートも、類似サイズの
多数のグループを扱うことができる。明らかに、上述の
コピーネットワーク４８は、多数のマルチキャストグル
ープをサポートできるが、グループメンバー数の変動が
比較的にまれであるアプリケーションに最も適してい
る。
【００１８】また、入ってくるセルと、コピーネットワ
ーク４８によって与えられるセルをバッファリングする
ために、交換網４１の各入力ポートにＦＩＦＯセルバッ
ファ５１，５２が設けられている。これらのバッファ５
１，５２は、それらのセルを競合せずに交換網４１を通
して経路指定することができるまで、入力ポートに届い
たセルを保持する（所望ならば、複数の優先権クラスを
サポートするために、これらのバッファ５１，５２の一
方または両方をサブバッファに分割することができ
る）。
【００１９】交換網４１を通るセルの経路指定は、交換
機に対する入力ポートにあるＶＣＩトランスレータ５３
によって制御される。これらのトランスレータ５３は、
ホストプロセッサ（図示せず）によつて維持、更新され
るＶＣＩ参照用テーブル５４を使用して、入力ポートア
ドレスと、入力ポートに対する待ち行列の先頭にいるセ
ルのヘッダーに含まれている宛先バーチャル回線インデ
ックス（ＶＣＩ）の樹木値関数（tree valued functio
n) を計算する。すなわち、[ VCI ′, outputPORT, mut
icastFlag] ← Routing Function [i, VCI]。理解され
るように、主として各種の経路指定テーブルやマッピン
グテーブルをＶＣＩ参照用テーブル５４にロードして交
換機２２を制御するために、通常のマイクロプロセッサ
または同種の装置（図示せず）に対するインタフェース
が必要である。
【００２０】III. 交換機の構成要素の詳細な説明 Ａ．バーチャル回線トランスレータ アドレス・マッピングを実行するために交換網４１の入
力ポートに設けられたトランスレータ５３は、目標宛先
への経路上の交換網４１から出力ポートを選択すること
（入力待ち行列の先頭にいるＡＴＭセルのヘッダー内の
宛先ＶＣＩ／ＶＰＩアドレスに基づいて）； 入力ＶＣ
Ｉ／ＶＰＩアドレスを出力リンクに適した値に書き直す
こと（ＶＣＩ／ＶＰＩはエンドツウエンド有意性（end-
to-end significance)を持たないことを想起された
い）；および後で詳しく説明するように、マルチキャス
ト伝送に必要なマッピングを管理すること、を含むいく
つかの機能を有する。これらのトランスレータ５３は、
さらに、たとえば請求書作成やロード監視のために、バ
ーチャル回線ごとに交換されるＡＴＭセルの数のカウン
トを保持することができる。図３は、典型的なＡＴＭセ
ルの書式を示し、図４はＡＴＭセルの典型的なスイッチ
ヘッダーの書式を示す。セルヘッダー内の広域フローコ
ントロール（ＧＦＣ）フィールドは通常はＮＵＬＬ値が
入ることに留意されたい。
【００２１】Ｂ．バッチャー／バンヤン（Batcher/Bany
an) ネットワーク 交換網は、どの交換サイクルにおいてもその入力の任意
順列（arbitrary permutaton) または部分順列（partia
l permutation)を生成することができる場合には、「非
ブロッキング」であると呼ばれる。言い換えると、非ブ
ロッキング式交換機は、考えられるすべての１対１入力
／出力マッピングを生成することができる。
【００２２】交換網は、一般に単一交換機のカスケード
ネットワークすなわちステージで構成される。このよう
な交換網を通る経路は、決められた入力から決められた
出力へ交換機のステージを通る通路である。交換網は、
交換網内の各ステージごとに、そのステージに入ってく
るセルに含まれる情報すなわち局部的に入手可能な情報
だけで経路指定を決定することができる場合には、「自
己経路指定」と分類される。
【００２３】バッチャー／バンヤンネットワークは、非
ブロッキング自己経路指定式交換網の知られた例であ
る。知られているように、バッチャーネットワークは、
一般に深さ log2 Ｎ（これはＮlog2Ｎ個の分類要素が必
要であることを意味する）のネットワークでＮ個のデー
タストリームを分類する並行分類ネットワークである。
図５に示すように、各分類要素６２は、２つの入力（Ａ
およびＢ）を受け取り、最小値と最大値を計算すること
によって入力を分類する。従って、もし入力が始めに最
上位ビットを有する２ビット直列データストリームの形
をしていれば、分類要素は、図６に示した非常に簡単な
有限状態マシン（finite state machine)６４として機
能する。４つの入力、８つの入力、それ以上の入力につ
いては、通例、これらの分類要素６２を再帰的に組み合
わせて分類ネットワーク６５すなわちソーターが作られ
る（図７参照）。
【００２４】図８に示すように、標準バンヤン経路指定
ネットワーク７１は深さ log2 Ｎの複数ステージのネッ
トワークである。ここで、Ｎはネットワークへの入力数
である。バンヤン経路指定ネットワーク７１は、バッチ
ャー分類ネットワーク６５と同様に、２つの入力と２つ
の出力を有する基本交換要素７２を再帰的に組み合わせ
て構成される。従って、バンヤンネットワーク７１に
は、Ｏ（Ｎlog2Ｎ）個の基本交換要素７２がある。デー
タシーケンスがバンヤンネットワーク７１を通って流れ
るとき、バンヤンネットワーク７１の各ステージにある
基本要素７２は、出力アドレスの１ビットを調べ、その
ビットの値に従って、そのデータシーケンス内のそのビ
ットおよび後続のすべてのビットを一方または他方の出
力へ経路指定する。慣例に従って、アドレスビットは各
ステージごとに変わるので、第１ステージは最上位アド
レスビットの値に基づいて経路指定を行い、第２ステー
ジは第２の上位アドレスビットの値に基づいて経路指定
を行い、Ｎ番目のステージは最下位アドレスビットの値
に基づいて経路指定を行う。Ｎ個のアドレスビットが処
理された後、シーケンスの残りの部分は交換機の出力へ
設定された経路をたどる。これは、あるシーケンスの終
端と次のシーケンスの始端を外部因子によって決定する
必要があることを意味する。従って、この例の場合、各
シーケンスは固定サイズＡＴＭセル＋その固定サイズス
イッチヘッダーであることを想起されたい。
【００２５】バンヤンネットワーク７１のどのステージ
においても、２つの入力が同一出力を選択する可能性が
ある。もしそれが起きれば、バンヤンネットワーク７１
は、「ブロックする」ので、不確定な結果が生じる。言
い換えると、バンヤンネットワーク７１はその入力の任
意順列を計算することができない。しかし、バンヤンネ
ットワーク７１は「非ブロッキング」であるから、順列
のクラスが存在する。これらのクラスの１つは、入力が
出力アドレスによって順序付けられるクラスである。こ
のため、非ブロッキング自己経路指定である交換網４１
を得るために、図２に示すように、バッチャー分類ネッ
トワーク４２はバンヤン経路指定ネットワーク４３，４
４の前にある。
【００２６】図２に示すように、複数のバンヤン経路指
定ネットワーク４３，４４（一般に、２または３個）を
使用して、出力競合（output contention)を減らすこと
が好ましい。たとえば、図示した実施例の場合は、ｋ＝
２のスピードアップ率を得るために、バッチャー分類ネ
ットワーク４２の後方に２個のバンヤン経路指定ネット
ワーク４３，４４が存在する。各バンヤン経路指定ネッ
トワーク４３，４４は入力の１／ｋのみを使用するの
で、他の入力はふさがれる。バッチャー分類ネットワー
ク４２のｋ番目の出力がバンヤン経路指定ネットワーク
４３または４４のｋ番目の入力に接続されるように、バ
ッチャー分類ネットワーク４２の出力はバンヤン経路指
定ネットワーク４３，４４の入力に接続されている（こ
れは、図示のように、バンヤン経路指定ネットワーク４
３，４４がバッチャー分類ネットワーク４２の奇数およ
び偶数番号の出力をそれぞれ経路指定することを意味す
る）。従って、同一出力ポートへアドレスされたｋ個ま
での個別セルがバッチャー分類ネットワーク４２の連続
するｋ個の出力に現れることができる。それらの個別セ
ルは、そのあとｋ個の別個のバンヤン経路指定ネットワ
ーク４３，４４を通して交換網４１の目標出力ポートへ
経路指定することがきる。
【００２７】Ｃ．予約リング 予約リング４６（図２参照）は、単一出力へ宛てられた
セルの数がｋ以上のとき交換網４１の出力ポートに対す
る「公正」なアクセスを実施する仲裁者（アービタ）で
ある。「公正」については多くの異なる定義がなされて
いるが、交換網４１の競合中の入力ポートに対し総当た
り（ラウンドロビン）サービスを提供する仲裁者が好ま
れる。
【００２８】詳しく説明すると、予約リング４６は、Ar
turo Cisneros, "Large Packet Switch and contention
Resolution Device," Proc.XII International Switch
ingSymposium,Stockholm,Sweden, May/June,1990. V3,
pp.77-83 の公表論文の教示に従って、それぞれが隣接
マシンとだけ通信する有限状態マシン７６ａ，７６
ｂ，．．．７６ｉ，７６（ｉ＋１）の線型短縮アレイ７
５（図９）として具体化される。線型短縮アレイたとえ
ばアレイ７５を使用することの特にすぐれた利点は、す
べての通信がローカルであり、電気的負荷がアレイのサ
イズと共に増さないことである。このことがシステムの
線形スケーリングを可能にする。
【００２９】上記論文の予約リング機構を修正すること
により、複数の経路指定ネットワーク４３，４４（すな
わち、ｋ≧２のネットワーク）を有する交換網たとえば
交換網４１に対する公正な総当たり競合解決策が得られ
ることが判った。作動中、有限状態マシン７６ａ〜７６
ｎは、交換網４１の入力ポートに対応付けられた一組の
空間固定評価要素（spatially fixed evaluation eleme
nts)として機能し、これらの有限状態マシンすなわち評
価子７６ａ〜７６ｎを環状に通過するように状態情報の
ベクトルがシフトされる。これを実行するために、各評
価子７６ａ〜７６ｎは、内部アドレスレジスタＲＡi 、
外部シフト済アドレスレジスタＳＡi 、競合フラグビッ
トのための内部単一ビットレジスタＦＣi 、競合要求フ
ラグのための第２の内部単一ビットレジスタＲＣi 、ペ
ンディング競合要求フラグのための第３の内部単一ビッ
トレジスタＦi 、シフト済競合フラグのための外部レジ
スタＳＣi 、走査ベクトルのための単一ビットレジスタ
Ｔi 、および内部（ｋ−１）ビット log2 ｋ mod k カ
ウンタCntri を備えている。さらに、各評価子７６ａ〜
７６ｎをアクティブ（InSession ＝０) 状態と非アクテ
ィブ（InSession ＝１) 状態の間で切り換えるための手
段が設けられている。
【００３０】システムリセット時間に、すべての評価子
７６ａ〜７６ｎがリセットされ、その結果それらのアド
レスレジスタＲＡi ，ＳＡi がクリヤされ、それらのカ
ウンタCntri と、フラグビットおよび状態ＲＣi ，ＳＣ
i ，ＦＣi ，Ｆi ，Ｔi および InSessioni が“０”す
なわち「偽」へセットされる。各仲裁サイクルの始め
に、評価子７６ａ〜７６ｎが交換網４１の入力ポートに
対する入力待ち行列の先頭にいるアクティブセルを走査
し、これらのセルがアドレスされる出力ポートのアドレ
スを、内部アドレスレジスタＲＡi と外部アドレスレジ
スタＳＡi にロードする。もし入力ポートが非アクティ
ブであれば（すなわち、もしその入力待ち行列が空であ
れば）、評価子は非アクティブ状態（InSession ＝０、
Ｔi ＝０）へ切り換えられる。この初期化手順が終わっ
た後、一連の少なくとも（ｎ−１）のシフトおよび比較
ステップが開始され、それによりアドレス値ＳＡi と競
合フラグビットＳＣがリング内でシフトされる（すなわ
ち、ポートｉの評価子におけるそれらの変数の値がポー
トｉ＋１における評価子へシフトし、最後のポートの評
価子における変数の値が０番目のポートの評価子へシフ
トする）。Ｔi はシフトダウンするが、ポート０のＴ入
力は“１”のままである。
【００３１】各シフトの後、アドレスレジスタＲＡi ，
ＳＡi の内容が各評価子によって比較される。もしアク
ティブ評価子においてそれらが同一であると判れば、そ
の評価子は、その要求された競合フラグＲＣi とシフト
された競合フラグＳＣi とが同じ値にセットされている
かどうかを判断することによって、その同一性が正当な
仲裁セッションに由来するものかどうかを判断する。
【００３２】もし評価子が正当な仲裁セッションの参加
者であれば、評価子は競合ベクトルＴi の現在状態を検
査する。もしＴi が依然として偽（“０”）であれば、
ｉ番目の評価子は、交換網４１のｉ番目の入力ポートに
あるアクティブセルと、その上の一定の入力ポートにあ
るアクティブセルとが同一出力ポートに対するアクセス
を争っていると判断する。どの交換サイクルにおいて
も、交換網４１の同一出力ポートに対しｋ個までのセル
（しかし、ｋ個のセルに過ぎない）を交換することがで
きるので、ｉ番目の評価子は、交換網４１内のそれより
上のどこかのポートと競合していることを発見すると、
カウンタCntri を単に増分する。しかし、もしカウンタ
Cntri がオーバーフローする前にｉ番目の評価子が真
（“１”）の競合ベクトル値Ｔi を受け取れば、ｉ番目
の評価子は、カウンタCntri 内の現在カウント＋同意信
号を入力バッファへ戻すことによって、交換網４１のｉ
番目の入力ポートに対する入力待ち行列の先頭にいるセ
ルを解放し、要求された出力ポートへ切り換える。他
方、もし真（“１”）の競合ベクトル値Ｔi を受け取る
前にカウンタCntri がオーバーフローすれば、ｉ番目の
評価子において競合フラグビットＦＣi とペンディング
競合フラグＦi が真（“１”）状態へセットされ、要求
されたときすべての競合者に対し交換網４１の要求され
た出力ポートに対するアクセスを総当たりトップダウン
順に許可するため、１つまたはそれ以上の追加交換サイ
クルの間競合セッションが延長される。
【００３３】Ｄ．代替仲裁処理 図１０に、ｋ個のバンヤン経路指定ネットワーク４３，
４４（図２）の出力ポートに対する「公正な」アクセス
を与えるもう１つの短縮アレイ手法（ｋ≧２）を示す。
この実施において、各評価子７８ａ〜７８ｎは以下のよ
うに機能する。 Initialize for arbitration: counter:＝０； Grant:＝０； Arbitration step: lostLastTime-Out：＝lostLastTime-In; resVec-Out：＝resVec-In; lostThisTime-Out：＝lostThisTime-In; IF couter ＝ portRequested THEN ｛ IF lostLastTime-In＝０ OR ISetLostLastTime THEN ｛ IF resVec-In＝０ THEN ｛ Grant:＝１； ISetLostLastTime：＝０ resVec-Out：＝１； lostThisTime-Out：＝０； ｝ELSE｛ lostThisTime-Out ：＝１； ISetLostLastTime ：＝NOT lostThisTime-In; ｝; ｝; ｝;
【００３４】予約リング４６のこの具体化において、第
１評価子７８ａ（図示せず）は、“０”に拘束された r
esVec 入力と、予約リングの最後の要素の lostThisTim
e 出力に拘束された lostLastTime 入力を有することに
注目されたい。 resVec 入力を通してシフトされるビッ
トのストリームはベクトルを表しており、その要素は対
応する出力ポートの予約である。もし決められた出力ポ
ートに対し１以上の要求者が存在すれば、アクセスする
のに失敗した第１要求者がその対応付けられた“ ISetL
ostLastTime ”ビットを設定するので、リングの動作は
総当たり戦（ラウンドロビンフェア）である。仲裁サイ
クルが終了したとき、設定された“ ISetLostLastTime
”ビットをもつ多くの予約リング要素が存在すること
があるが、それらの各ビットは異なる出力ポートを指示
する。
【００３５】理解されるように、図１０のこの予約リン
グ機構は、１交換サイクルの間に複数の入力ポートに同
一出力ポートにアクセスすることを許すケースを扱える
ように拡張することができる。これは、予約ベクトル r
esVec をｋビット幅にすることによって達成される。こ
こで、ｋは、１交換サイクル中に単一出力ポートへ送る
ことができる入力ポートの数である。
【００３６】図１０に示した形式のより大きな予約リン
グを２つ（またはそれ以上）のセクションに分割するこ
とが望ましいことがある。２つのリングの予約ベクトル
もやはりｋビット幅である。しかし、第１セクションに
ついてはｋビットの一部が“１”に初期化され、他方の
第２セクションについては対応するビットが“０”に初
期化される。残りのビットはトップが“０”に、そして
ボトムが“１”に初期化される。ロードは入力にわたっ
て均一に分散していると仮定すると、交換機は、近似的
に、あたかも唯一の予約リングが存在しているかのよう
に機能するが、２つのリングはある単一リングのクロッ
ク周波数の１／２で実行することができる。
【００３７】もしトラヒックが分割された２つの半リン
グにわたって一様に分布していなければ、予約ベクトル
に対するビットの初期設定を変更することにより、どれ
か決められた出力ポートに対する帯域幅を２つの半リン
グの間でやりとりすることができる。予約リングの各半
分のトラヒックを計算する方法は、以下の２つがある
が、それらに限定されない。 １） 予約リングの各半分の最も下すなわち最後の評価
子の出力で、“１”に設定された“lostThisTime”ビッ
トの数をカウントする。 ２） 予約リング要素を通してシフトされるデータスト
リームにカウンタのベクトルを加えて、各紛失（losin
g) 評価子に目標の出力ポートに対応付けられたカウン
タを増分させる。次に最後の評価子から出るときこれら
のカウンタの合計を求め、もしこの合計が所定のしきい
値以上であれば、分割された予約リングの間で帯域幅を
移す。
【００３８】Ｅ．コピーネットワーク 図２のＮ×Ｎコピーネットワーク４８は、１交換サイク
ルごとにｊ個までのＡＴＭ入力セルＩj （ｊ≦Ｎ）を受
け取り、各セルの正確なコピーをＣj 個作成する。各Ｃ
j 個のコピーはコピーグループと呼ばれる。理解される
ように、セルの複写は、「マルチキャスト操作」として
知られる操作における重要なステップである。
【００３９】コピーネットワーク４８に対する手法の根
底には、交換網４１の使用に関する実行可能な３つの仮
定がある。第１は、各ｊごとに、Ｃj が非常にゆっくり
変わることである。第２は、すべてのコピーグループサ
イズの合計が≦Ｎであることである。第３は、Ｃj がｊ
のみの関数であることである。まとめると、これらの条
件は、各コピーグループによって作成されるコピーの数
が非常にゆっくり変わることを意味し、それはコピーグ
ループのメンバー数がセルの内容の関数でないことを意
味する。従って、静的ルーチング戦略によってどんなコ
ピーグループについてもｊの特定値を選択することがで
きるので、コピーネットワーク４８の１個の入力とＣj
個の出力が各コピーグループに専用される。
【００４０】標準クロスバー交換機の場合には、Ｎ個の
各入力はＮ個の各出力へ扇形に広がっている。これは、
１個の入力と複数個の出力の部分集合とを接続している
クロスポイントを「ＯＮ」にすれば、その入力がこれら
すべての出力へコピーされることを意味する。概念的
に、コピーネットワーク４８は、コピーグループに対す
る入力として使用されるｊ個の入力、使用されない（ｎ
−ｊ）個の入力、および使用されるΣＣj 個の出力を有
するＮ×Ｎクロスバーより成っている。しかし、実際問
題として、通常は、全クロスバーは必要ない。このこと
は、大きなクロスバーはチップが高価であるばかりでな
く、難しいシステム実装問題を引き起こすので、幸運で
ある。
【００４１】より簡単で、しかも要求を満たすコピーネ
ットワーク４８を構築する２つの手法である。その１つ
は、コピーネットワーク４８を２層のＮ／ｍクロスバー
（図示せず）として構築するものである。ここで、ｍは
１チップに実装されるクロスバーのサイズである。
【００４２】幸運なことに、図２に示すように、コピー
ネットワーク４８の最も普通の使用が小コピーグループ
であるアプリケーションには、代案を用いることができ
る。すなわち、コピーグループとして必要な数Ｃj のセ
ルコピーを作成するためにマルチノードスパントリー
（multi-node spanning tree) が必要なときは、交換網
４１自身を使用して、コピーネットワーク４８の複数の
「バーチャル回線層」を相互接続することが可能であ
る。コピーネットワーク４８のこの好ましい実施例は、
２種類の基板（交換網４１と、それぞれがｐ個の回線ご
とに完全な論理を有するＮ／ｐ個の同一回線カード）を
使用して具体化することができるので、自然なシステム
実装を用いることと両立する。図２に示すように、回線
カードの論理は、（そのｐ個の回線ごとに）入力リンク
８４と出力リンク８５、ＶＣＩトランスレータ５３、予
約リング評価子（図９および図１０参照）、すべての入
力および出力バッファリング、およびｐ×ｐクロスバー
８６を有する。このようなコピーネットワーク４８を使
用するときは、ｐ個より大きなグループ（ここでは、ｐ
＝８）へのマルチキャスト伝送（multicast)または同報
通信 (broadcas) は、前記グループへマルチキャスト伝
送することによって処理されるので、セルは交換網４１
を通って３つの旅をする。
【００４３】Ｆ．入力および出力バッファリング−待ち
行列戦略− 交換網４１は、共用待ち行列でなく、分散形待ち行列
（各入力回線および出力回線ごとの１つまたはそれ以上
の専用待ち行列）を使用する。知られているように、共
用待ち行列は、すべての回線にわたってバッファ空間を
動的再配置するのに役に立つ、すなわちバッファメモリ
をより効率的に使用するのに役に立つ手法である。しか
し、この場合はバッファの利用を最適にするよりも設計
の単純さのほうが重要であるので、交換機に公正なサー
ビス訓練を課すと同時に、入力回線と出力回線を互いに
分離するための手段が設けられている。従って、もし数
個の入力がトラヒックを運ぶ出力の能力をかなり越える
レートで伝送すれば、セルは入力回線のためのバッファ
またはその特定出力のためのバッファのどちらかにおい
て交換機によって失われるであろう。
【００４４】ＬＡＮ２１（図１）は、簡単なフロー制御
機構を適切に使用して、保証トラフィックロードを制限
する。詳しく述べると、ＬＡＮのサービスを受けるソー
ス３１，３２などのワークステーション、その他のコン
ピュータのネットワークインタフェースのハードウェア
／ソフトウェア（図示せず）に依存して、保証トラヒッ
クのレートを制限する。慣例に従って、事前に資源予約
を行った保証トラヒックストリームを指示するために、
ＶＣＩ参照用テーブル内の resTraf ビット(スイッチ
ヘッダーへコピーされる）が使用される。従って、交換
機２２〜２５のそれぞれの入力ポートごとに、少なくと
も２つの入力待ち行列（保証トラヒック用と非保証トラ
ヒック用）が存在する。もし非保証トラヒック用待ち行
列が一杯であれば、非保証セルは待ち行列に入れない。
【００４５】IV. システム操作 Ａ．ユニキャスト（unicast) ユニキャスト（単数宛）伝送は、所定のバーチャル回線
アドレス（ＶＣＩ）によって定義されるように、複数の
ソースから指定された単一宛先へのセルの通常の経路指
定である。任意の決められた交換機たとえば図２の交換
機２２において、交換網４１の１つの入力ポートのため
の入力リンク８４にセルが到着すると、ユニキャスト操
作が始まる。入力リンク８４内の論理（図示せず）はセ
ルヘッダーのＶＣＩフィールドを検査し、非零値が入っ
ていること（すなわち、セルが空でないこと）を確かめ
る。もしセルがこの試験をパスすれば、決められた入力
ポートに対する入力バッファ５１の状態を検査し、セル
を受け入れることができるか否かを決定する。この受入
れ／拒絶決定を行う場合は、セルのヘッダー内のセル紛
失優先権（cell loss priority; 略してＣＬＰ )ビット
の状態を考慮に入れることが好ましい。たとえば、
（１）バッファ５１が一杯でなく、ＣＬＰビットがリセ
ットされた場合、あるいは（２）バッファ５１が全体の
半分ほどふさがっている場合だけ、セルは入力バッファ
５１へシフトされる。
【００４６】交換網４１の各入力ポートにあるバーチャ
ル回線トランスレータ５３は、入力バッファ５１とクロ
スバーバッファ５２の両方からセルを取り出す。優先権
はクロスバーバッファ５２に与えられる。理解されるよ
うに、トランスレータ５３は、出力競合のために予約リ
ング４６にブロックされたセルが存在しない場合だけア
クティブである。上記のブロッキング状態が存在しない
場合は、各交換サイクルの始めに、２個の入力ＦＩＦＯ
バッファ５１，５２が検査され、クロスバーバッファ５
２（第１の選択）または入力バッファ５１（第２の選
択）の一方からセルが取り出される。これらのＦＩＦＯ
バッファ５１，５２が共に空であれば、ＮＵＬＬセルす
なわち全部がゼロの空セルが生成される。
【００４７】バーチャル回線トランスレータ５３では、
選択されたセルのヘッダーの始めの４バイトが「４バイ
ト＋１０ビット」遅延バッファ（図示せず）へシフトさ
れ、セルの残り（たとえば、標準ＡＴＭセルのケースで
は、４９バイトの情報）がＶＣＩ変換ＦＩＦＯバッファ
（図示せず）へシフトされる。このヘッダーに含まれて
いるＶＣＩ値は、そのあとＶＣＩ変換テーブル５４にイ
ンデックスすることによって、スイッチヘッダー（swit
ch header: 図４参照）を生成する情報を得るために使
用される。このスイッチヘッダーは前記遅延バッファの
始めの１０ビットに書き込まれる。ＶＣＩ変換テーブル
５３は、さらに、新しいＶＰＩ／ＶＣＩ値をセルに提供
する。この新しいＶＰＩ／ＶＣＩ値を使用して、古いＶ
ＰＩ／ＶＣＩ値に上書きされ、そのあとＡＴＭセルのヘ
ッダーのチェックサムすなわち“ＨＥＣ”フィールド
（図３参照）が更新される。
【００４８】スイッチヘッダーは、セルが空かどうかを
指示するアクティブフラグ（１ビット）、出力ポートア
ドレス（２個の並列３２ポートバンヤンによって提供さ
れる６４ポート用の６ビット）、およびストッパービッ
ト（デュアルバンヤン交換網４１用の１ビット、その出
所と機能は後で詳しく説明する）を含むように適当に書
式化されている。さらに、スイッチヘッダーは、一般
に、出力ポートがセルをコピーネットワーク４８へ送る
べきかどうかを指示するマルチキャストフラグ（１ビッ
ト）、コピーネットワーク上の予約トラフィックと未予
約トラフィックとを区別する予約トラヒック（ＲＴ）ビ
ット（１ビット）、オーバーロードの場合にそのセルが
脱落するのにふさわしい候補か否かを指示するセル紛失
優先権（ＣＬＰ）フラグ（１ビット）（このビットは、
ＡＴＭヘッダー内のＣＬＰビットのコピーである）、お
よびスイッチヘッダーの長さが２バイトになるようにス
イッチへッダーに詰めるための予約ビット（５ビット）
を含んでいる。
【００４９】実際には、バッチャー／バンヤン交換網４
１（図２）は、既知の技法に従って、その入力ポートと
出力ポートの間に１バイト幅（８ビット幅）のデータ経
路を与えるように構成することが好ましい。スイッチヘ
ッダーの始めのバイト（すなわち、アクティブビット、
出力ポートアドレス、およびストッパービット）は上記
のデータ経路上でビット並列モードで伝送されるが、ス
イッチヘッダーの残りのバイトとＡＴＭセルの全５３バ
イトは、交換網４１の並列データ経路構造を活用するた
めに、バイト並列モードで伝送することが好ましい。
【００５０】バーチャル回線トランスレータ５３によっ
て処理されたセルは、予約リング４６の仲裁制御を受け
る。その仲裁機能を実行するために、予約リング４６は
交換網４１への入力待ち行列の先頭にいるセルのヘッダ
ーのみを検査し、これらのセルの間に競合状態が存在す
るかどうかを判断し、もし存在すれば、それらの競合を
解決する。実際には、ＶＣＩ変換バッファ（図示せず）
は制限付き深さ（bounded depth)のものである。
【００５１】交換網４１（図２）の決められた入力ポー
トのための評価子（図９および図１０参照）が仲裁ラウ
ンドに勝った時はすぐに、その入力ポートに待機中のセ
ルが交換ファブリック４１を通して送られる。図示のよ
うに、交換機の基本構造は、２個のバンヤンネットワー
ク４３，４４（ｋ＝２）より成り、各ネットワーク４
３，４４は最終的に選択された出力ポートのための出力
バッファ４５に接続している。もしセルがアクティブで
なければ（すなわち、もしセルに事前に付けられたスイ
ッチヘッダーのアクティブビットが０であれば）、セル
は出力バッファ４５によって待ち行列に入れられないて
あろう。他方、もしセルがアクティブであって、そのス
イッチヘッダー内の resTrafビットが“ＯＮ”であれ
ば、セルは保証トラフィックのために予約された出力バ
ッファ４５のセクションで待ち行列に入れられるであろ
う。あるいは、もしセルがアクティブであって、その r
esTrafビットが“ＯＦＦ”であれば、セルは非保証（未
予約）トラフィックのために予約された出力バッファ４
５のセクションに置かれる。
【００５２】任意の決められた出力バッファ４５の保証
待ち行列内のセルは、常に非保証待ち行列内のセルのど
れかの前で待ち行列から出される。セルがユニキャスト
されているとき、スイッチヘッダー内のマルチキャスト
ビットは“ＯＦＦ”（“０”）にされるので、ユニキャ
ストセルが待ち行列から出されるとき、対応付けられた
出力バッファ４５へ送られるように、セルに標識が付け
られる。
【００５３】想起されるように、スイッチヘッダーの最
初のバイトは全８ビットにわたって（すなわち、全部の
並列データ経路にわたって）複製され、他方の第２のバ
イトはバイト並列モードで伝送されるので、スイッチヘ
ッダーはセル長に９バイトを付加する。さらに、出力リ
ンクでは、５３バイト長セルにフレーミング情報の２バ
イトが付加されるので（図示してない通常手段によっ
て）、出力バッファ４５におけるバイトレートは、それ
が接続されている出力リンク８５のバイトレートより少
なくとも（５３＋９）／（５３＋２）倍大きい。この不
釣合いを調整するために、一般に、各出力バッファ４５
をその対応する出力リンク８５に対し速度整合する短い
ＦＩＦＯバッファ（図示せず）が設けられる。
【００５４】Ｂ．マルチキャスト（multicast) 前に指摘したように、マルチキャスト（多数宛）グルー
プは、複数のネットワークの宛先をアドレッシングする
バーチャル回線である。従って、交換機の各ステージ
は、グループ内のすべての宛先へ入力セルのコピーを送
るためアクセスしなければならない交換機の出力ポート
を知っていなければならない。単一交換機たとえば交換
機２２（図１）の見地から、マルチキャストグループ
は、既知の一組の宛先ＶＣＩへ経路指定すべきセルを指
定するＶＣＩ／ＶＰＩペアである。本発明の交換機の特
徴の１つは、マルチキャストセルの経路指定を２段階で
実行することである。すなわち、最初に正しい入力コピ
ーネットワーク４８を通してマルチキャストセルを経路
指定することによって正しい数のコピーを作成し、次に
これらのマルチキャストセルのコピーを交換網４１を通
して意図した宛先へ個別に再経路指定する。
【００５５】マルチキャスト操作は、ユニキャスト操作
と同じステップで始まる。ＶＣＩ変換プロセスのとき、
インデックス付きエントリＶＣＩ変換テーブル５４（図
２）は、入力セルのヘッダー内のＶＣＩがユニキャスト
アドレスを示すかマルチキャストグループアドレスを示
すかを指定するので、最初の違いが生じる。従って、マ
ルチキャストＶＣＩを有するセルについて、スイッチヘ
ッダー内のマルチキャストビットが設定される。次に上
記セルは交換網４１を通って、交換網４１が名前付きマ
ルチキャストＶＣＩを見て結び付けた出力バッファ４５
の待ち行列へ行く。その待ち行列から出るとき、マルチ
キャストビットの状態は、対応付けられた出力リンク８
５へでなく、決められた出力バッファ４５に接続された
コピーネットワーク４８の入力を経由してコピーネット
ワーク４８へセルを戻すように、ハードウェアに命令す
る。次にコピーネットワーク４８は、セルの一定の数の
同一コピー、たとえばｊ個のコピーを作成する。次にこ
れらのコピーは決められたコピーグループに専用のコピ
ーネットワーク４８のｊ個の出力へ個別に経路指定され
る。次にｊ個の各出力は受け取ったコピーを、交換網４
１の入力ポートのためのクロスバーすなわちコピーネッ
トＦＩＦＯバッファ５２へ送り込む。各コピーのヘッダ
ー内のアクティブビットは空セルとアクティブセルを区
別するので、ＦＩＦＯバッファ５２はアクティブセルを
待ち行列に入れ、空セルを廃棄することができる。
【００５６】決められたコピーグループに対応付けられ
た一組のコピーネットＦＩＦＯバッファ５２において待
ち行列に入れられた後、前に述べたように、セルはバー
チャル回線トランスレータ５３によって正規の順序で取
り出される。各バーチャル回線トランスレータ５３はそ
れぞれ別個のＶＣＩ変換テーブル５４を有しているの
で、セルのｊ個のコピーはｊ個の異なるＶＣＩ変換を受
け取る。従って、ｊ個の各セルについて、後続の処理ス
テップは、ユニキャストセルすなわち交換網４１を通る
マルチキャストセルの最初のパスと同じである。
【００５７】理解されるように、交換機のどれかの交換
網４１を通るマルチキャストセルの経路指定は、バーチ
ャル回線トランスレータ５３中で起きるＶＣＩの再書込
みによって決まる。たとえば、ｊをマルチキャストグル
ープのサイズとし、 vci、 vci′i 、および vci″i を
マルチキャスト操作のとき連続するマルチキャストセル
がとるＶＣＩ値であるとする（０＜ｉ＜ｊ）。セルが最
初に交換機２２（図２）に入るとき、そのＶＣＩ値は v
ciである。従って、セルがバーチャル回線トランスレー
タ５３の１つを最初に通る際に、前記値 vci に基づい
て、セルに対するスイッチヘッダーが生成され、それに
よりセルヘッダーのＶＣＩ値が vci′へ書き直される。
その結果、コピーネットワーク４８を出るときには、セ
ルの正確なコピー（それぞれが vci′のＶＣＩ値を有す
る）がｊ個ある。そのあと、各コピーは、対応するトラ
ンスレータ５３においてｊ個の異なるＶＣＩ変換テーブ
ル５４（それぞれに、 vci′番目のエントリ用の異なる
変換が入っている）を使用して変換される。従って、コ
ピーネットワーク４８から出てくるｊ個のセルのｉ番目
のコピーは、独自のスイッチヘッダーと vci″i の独自
のＶＣＩ値を受け取る。
【００５８】幾つかの実例においては、交換機の複雑さ
を減らすために、コピーネットワーク４８を単一基板ま
たはカード（図示せず）に実装することが望ましいこと
がある。たとえ回線カードのサイズより大きなコピーグ
ループが許されても、交換機自身を用いてコピーネット
ワーク４８の連続するレイヤを相互に接続することがで
きるので、これは実行可能なオプションである。操作
上、これは、複数レベルのマルチキャストグループを許
すことによって行われる。言い換えると、トランスレー
タ５３の所で、コピーネットワーク４８から出てくるｊ
個のコピーのＶＣＩを後続のマルチキャストグループの
ためのＶＣＩに変換することができ、そしてこれらのコ
ピーのためのスイッチヘッダーのマルチキャストフラグ
ビットを設定することにより、交換機にコピーを再経路
指定させ、コピーネットワーク４８を通して戻すことが
できる。もしこのオプションを使用すれば、上例からの
ｉ番目のセルは、そのセルのスイッチヘッダーのマルチ
キャストビットが零に設定されたか否かに従って、ユニ
キャストセルとして残りの交換機によって処理される
か、またはマルチキャストセルとして再び処理されるで
あろう。もしコピーネットワーク４８から出てくるコピ
ーが異なるマルチキャストセルであれば、交換網４１を
別に通過するとき、そのセルのヘッダーの vci″、 vc
i′′′、および vci′′′′のＶＣＩ値が生成される
であろう。
【００５９】手短に言うと、コピーネットワーク４８の
注目すべき多くの特徴の１つは、いろいろなサイズのコ
ピーグループに適合するようにコピーネットワーク４８
を簡単にプログラムできることである。このプログラミ
ングはＶＣＩ変換テーブル５４に組み込まれているの
で、コピーグループのメンバー数に対する変更は、１つ
またはそれ以上の変換テーブル５４を再構成する必要が
あるので、最小限にすべきである。
【００６０】Ｃ．パケットの完全性の保存−ストッパー
ＩＤ− 既知のバッチャー／バンヤンチップは１ビット幅のデー
タ通路を有し、一般に約 155 MHz のクロック速度で実
行する。従って、指定されたＡＴＭのレートの最低は約
155Ｍビット／秒であるので、上記チップはＡＴＭネッ
トワークに指定されたレートの下限とぴったり一致す
る。しかし、複数のバッチャー／バンヤンネットワーク
を相互に並列に実行させることができるので、交換機の
ビット処理能力を損なわずに、攻撃的でないクロック速
度を使用することができる。たとえば、８ビット直列バ
ッチャー／バンヤンネットワークを約 20 MHz のクロッ
ク速度で並列に実行させることによって、約 155Ｍビッ
ト／秒の処理能力を得ることができる。
【００６１】想起されるように、バッチャー分類ネット
ワーク４２の次にｋ個のバンヤン経路指定ネットワーク
４３，４４が続くように交換網４１（図２）を構成する
ことにより、付加スピードアップ係数ｋを得ることがで
きる。その場合には、ｋ個までのセルを交換網４１の同
一出力ポートへ同時に経路指定することができる。
【００６２】並列バンヤンネットワーク７１ａ，７１ｂ
によって得られるスピードアップ係数と、複数のビット
直列バッチャー／バンヤンネットワークを相互に並列に
実行させることによって可能になった並行処理とをうま
く組み合わせるために、同一出力ポートへアドレスされ
たセルの内容が混り合わないように注意する必要があ
る。前に指摘したように、複数のバッチャー／バンヤン
ネットワークを相互に並列に実行させるために、複数ビ
ットデータ経路の各ビットごとに出力ポートアドレスを
伝送しなければならない。バッチャー分類ネットワーク
４２は、入力がアドレスされた出力ポートのアドレスに
基づいて、入力を通常のやり方で分類する。しかし、も
し複数のセルが同一アドレスを有していれば、この分類
は、アドレスのすぐ後に続く１ビットまたは数ビットに
基づいて行われる。従って、もしアドレスビットの後に
本質的にランダムなデータが続けば、同一出力ポートへ
アドレスされたセルの内容が混じり合う危険がある。
【００６３】この問題を解決するために、セルが交換網
４１を通して経路指定される前に、各入力セルごとに、
ｋ個までの独自の値をとることができる「ストッパーＩ
Ｄ」がスイッチヘッダー内の出力ポートアドレスに付加
される。このＩＤはデータ経路の全ビットについて出力
ポートアドレスの付加物として伝送されるので、データ
経路の全ビットは確実に出力ポートアドレスを分類す
る。
【００６４】理解されるように、１交換サイクルごと
に、任意の決められた出力ポートアドレスへ経路指定す
ることができるセルは多くてもｋ個であるので、ストッ
パーＩＤはｋ個の独自の値をとる整数が適当である。実
際には、ストッパーＩＤを０〜ｋ−１にすると、ｋ個の
セルの任意集合の全ビットについて決定論的分類順序が
確保されるので最も都合がよい。ストッパーＩＤは予約
リング４６によって計算される。前に述べた予約リング
４６の第１の実施例の場合には、ストッパーＩＤは、許
可の時点にmod k カウンタによって戻される値が適当で
ある。予約リング４６の第２の実施例の場合には、スト
ッパーＩＤは“firstZero[resVec-In] ”によって戻さ
れる値が適当である。
【００６５】Ｄ．トランクグループ化 広帯域ＩＳＤＮ通信について現在最も関心が集まってい
ると思われるデータ転送速度は、光キャリア（Optical
Carrier 、略してＯＣ）階層によって決まる。非同期転
送モード（Asynchronous Transfer Mode 、略してＡＴ
Ｍ）について規定された最小データ転送速度は約 155 M
b/sec ( ＯＣ−３）である。もっと高いデータ転送速
度、たとえば約 622 Mb/sec ( ＯＣ−１２）も規定され
ている。これらの高速リンクは、交換機間のトランクと
して、あるいは高容量サーバたとえば共用ファイルサー
バ（図示せず）へ接続するのに適している。しかし、高
速で実行する交換網を構成することは技術的または経済
的に、またはその両方の理由で難しいことは立証するこ
とができる。
【００６６】電気通信分野において周知の方法は、交換
機上の複数の入力／出力ポートを用いて１個の高速回線
をサービスすることである。「トランクグループ化」と
呼ばれるこの方法の主な技術的欠点は、任意の決められ
たバーチャル回線内でセルの順序を維持しなければなら
ないことである。
【００６７】このことを心に留めて、次に図１１につい
て説明する。交換機１００は２つの入力回線と２つの出
力回線を有する。一方の入力回線１０１と一方の出力回
線１０２は、前に述べたように、本質的に交換機と同じ
速度で実行する。他方の入力回線１０３と他方の出力回
線１０４は、交換機の４倍の速度で実行させるためにト
ランクグループ化されている。便宜上、これらの回線を
それぞれＯＣ−３，ＯＣ−１２と呼ぶことにするが、異
なる回線レートおよび交換機速度を使用してもよいこと
はもちろんである。
【００６８】最初にトランクグループ化出力回線１０４
について説明すると、ＯＣ−１２出力回線を駆動するた
めに４本のＯＣ−３入力回線をトランクグループ化しな
ければならないことは明らかであろう。前に述べたよう
に、交換網１０６がｋ個のバンヤンネットワークを有す
る場合には、どの単一セル時間の間に４ｋ個までのセル
をトランクグループ化出力回線１０４のための出力バッ
ファ１０７にロードすることができる（しかし、ＯＣ−
１２出力回線で伝送する場合は、単一セル時間の間に出
力バッファ１０７から最大４個のセルを取り出せるだけ
である）。
【００６９】想起されるように、予約リング機構の第１
の実施例（図９参照）は、入力待ち行列（ＲＡi ’ｓ）
の先頭にいるセルが要求した出力ポートと、巡回する予
約ベクトル（ＳＡi ’ｓ）とを比較する一連の（少なく
ともｎ−１）シフト／比較ステップを実行することによ
って、交換網の同一出力ポートへのアクセスを争ってい
るセル間の競合を解決する。しかし、トランクグループ
化出力回線の場合には、要求されたアドレス（ＲＡ）と
マスクされた巡回予約因子（ＳＡ）のより低位の log2
Ａビットを用いて、この比較が行われる。ここで、Ａは
トランクグループ化出力回線を駆動するため集められた
入力ポートの数である。たとえば、ＯＣ−１２出力回線
を駆動するため４本のＯＣ−３入力回線を集める場合に
は、ＲＡ値とＳＡ値のより低位の２ビットはマスクされ
る。
【００７０】与えられた入力セルがトランクグループ化
出力回線行きであるか否かについては、スイッチヘッダ
ー内の出力ポートアドレスのＮ／Ａ個のより高位のビッ
トを使用してＮ／Ａエントリのテーブル（各エントリは
要求された出力がトランクグループであるか否かを示す
論理式である）にインデックスすることによって判断す
るのが適当である。言い換えると、上例の場合、これ
は、出力ポートアドレスのより高位の４ビットを使用し
て、１６エントリのテーブルにインデックスすることに
よってトランクグループ化／非トランクグループ化の判
断が行われることを意味する。
【００７１】要求された出力ポートがトランクグループ
であることが判った場合には、スイッチヘッダー内のポ
ートアドレスのより低位の log2 Ａビットを、（ log2
Ａ＋log2 k mod Ａ＋ｋ）カウンタからのより高位の lo
g2 Ａビットで上書きし、それにより入力回線の中から
トランクグループ化出力を識別することによって、その
出力ポートについて実アドレスを計算することができ
る。これは、図９に示した予約リングの評価子７６ａ〜
７６ｎ内のカウンタの長さを２ビット延長することを意
味し、この結果、より高位の２ビットを使用して、トラ
ンクグループ化されＯＣ−１２出力ポート行きのセルの
ためのスイッチヘッダーイメージのより低位の２ビット
を上書きすることができる。
【００７２】セルの順序は任意の決められたバーチャル
回線内では維持しなければならないが、異なるバーチャ
ル回線間では維持する必要がない。複数の非トランクグ
ループ化入力（たとえば、複数のＯＣ−３入力）によっ
てセルをトランクグループ化出力（たとえば、ＯＣ−１
２出力）へ送ろうとしている場合には、各入力は、任意
の決められたセル時間の間に１セルをトランクグループ
化出力へ送ることができるだけである。従って、前に述
べたストッパーＩＤは別個のセル時間にトランクグルー
プ化出力に到着することができるＡ＊ｋ個までのセルの
グループ内で順序を有効に維持するので、ｋ個のセルス
トリームはどれも、セルの順序が乱れないであろう。
【００７３】非トランクグループ化出力（たとえば、Ｏ
Ｃ−３出力）またはトランクグループ化出力（たとえ
ば、ＯＣ−１２出力）のどちらにもセルを送ることがで
きるトランクグループ化入力（たとえば、図１１のＯＣ
−１２入力１０３）が存在する場合には、セルの順序を
維持することはかなり複雑な問題である。たとえ単一セ
ル時間の間に任意の決められたバーチャル回線から複数
のセルがトランクグループ化出力へ到着することがある
場合でも、セルの順序はバーチャル回線内で維持されな
ければならない。しかし、予約リング４６（前述の log
2 Ａ＋ log2 ｋの長さのカウンタを含むように改造され
ている）によって、トランクグループ化出力に対する実
ポートアドレスのより低位の log2 Ａビット（たとえ
ば、上例と同様に、より低位の２ビット）と、そのアド
レスに付加される log2 ｋビットのより長いストッパー
ＩＤとが計算され、従って、それらがトランクグループ
化トラヒックのための２次分類キーを提供するので、こ
の問題に対する解決策は用意されている。従って、同一
バーチャル回線によって２個以上のセルが交換網１０６
の同一出力ポートへ送られた時はいつも、この２次分類
キーに従ってセルが分類される。
【００７４】もしセルが厳密に昇順で交換網１０６の入
力にマップされれば（予約リング４６は競合している入
力が総当たりトップダウン順に目標出力ポートへアクセ
スすることを許可することを想起されたい）、この２次
分類キーは順序問題に対する完全な解決策であろう。し
かし、もし同じ〔出力ポート，ＶＣＩ〕の組合せに宛て
られた１個またはそれ以上の未送セルが予約リング４６
のための待ち行列に依然として存在していれば、仲裁処
理は競合している最下位番号の入力ポートから最上位番
号の入力ポートへ環状に巡回するので、上記の厳密な順
序は維持されない。
【００７５】この順序問題に対して考えられる１つの解
決策は、前記 Cisneros の論文のアルゴリズム１に記載
されている仲裁セッションの概念を適用することであ
る。同じ〔出力ポート，ＶＣＩ〕の組合せに宛てられた
セルのため仲裁セッションが始まった後に入力待ち行列
の先頭に到着したセルは、予約リング４６において待ち
行列に入るため、仲裁セッションが終了するまで待機し
なければならない。同じ〔出力ポート，ＶＣＩ〕の組合
せに宛てられたより高位番号の入力にセルが依然として
存在するときは、もしそのセルがまだ仲裁セッションに
参加していなければ（すなわち、より高位番号の入力ポ
ートのための評価子において、ＦＣi ＝０）、交換網１
０６の決められた入力に対する待ち行列の先頭にいるセ
ルが予約リング４６によって待ち行列に入れられるのを
阻止することにより、上記概念の適用を有効に達成する
ことができる。この手法に固有の待ち行列の先頭の阻止
は、交換網１０６の処理能力を少し低下させる傾向があ
る。しかし、阻止されたセルを小さいＦＩＦＯバッファ
（図示せず）に振り向けることによって、上記の阻止を
最小にすることができる。この小さいＦＩＦＯバッファ
は、セルがもはや阻止されなくなって初めて、セルを待
ち行列の先頭へ戻す。
【００７６】セルの順序問題に対するもう１つの解決策
は、前記 Cisneros の論文のアルゴリズム２に記載され
ている優先権関数（Priority Function)を使用すること
である。この手法を使用するために、交換網１０６の各
入力ポートに対し log2 Ａ（たとえば、上例の場合は２
ビット長）優先権フィールドが割り当てられているの
で、それらの各フィールドを、特定の優先権フィールド
が割り当てられた入力ポートに対する入力待ち行列の先
頭にいるセルの〔出力ポート，ＶＣＩ〕宛先に一致す
る、予約リング４６におけるセルの番号に等しい値に初
期化することができる。その後、予約リング４６を通る
各完全サイクルの後、その特定の〔出力ポート，ＶＣ
Ｉ〕宛先へ各セルが送られるたびに、各入力ポートのた
めの優先権フィールドを１だけ減分することができる。
これにより、仲裁処理を交換網への入力に関して総当た
りさせるのでなく、入力回線に関して厳密に総当たりさ
せるので、順序問題に対する上記の解決策とは異なる
「公正なアクセス」の概念が得られるが、これは容認で
きるものである。
【００７７】以上の説明を熟読されれば、本発明は、よ
り高速の入力および（または）出力をサービスするため
に、複数の経路指定ネットワークを有する非ブロッキン
グ自己経路指定式交換網をトランクグループ化入力モー
ドおよび（または）トランクグループ化出力モードで動
作させることが可能であることを理解されるであろう。
【図面の簡単な説明】
【図１】本発明に従って構成された階層型ＡＴＭ ＬＡ
Ｎを示す略図である。
【図２】本発明に従って構成されたＡＴＭ交換機を示す
略図である。
【図３】ＡＴＭセルの通常の書式を示す図である。
【図４】ＡＴＭセルのための典型的なスイッチヘッダー
を示す図である。
【図５】バッチャー分類要素を示す略図である。
【図６】バッチャー分類要素の作用を示す有限状態マシ
ンの図である。
【図７】図５に示した形式の分類要素の再帰的組合せよ
り成るバッチャー分類ネットワークを示す略図である。
【図８】バンヤン経路指定ネットワークを示す略図であ
る。
【図９】予約リング機構を示す略図である。
【図１０】別の予約リング機構を示す略図である。
【図１１】トランクグループ化された入力および出力を
有する交換機を示す略図である。
【符号の説明】
２１ 階層型ＬＡＮ ２２〜２５ 自己経路指定非ブロッキング式交換機 ２７ ＡＴＭセル ３１，３２ ソース ３３ 宛先 ４１ バッチャー／バンヤンネットワーク（交換網） ４２ バッチャー分類ネットワーク ４３，４４ バンヤン経路指定ネットワーク ４５ ＦＩＦＯバッファ ４６ 予約リング ４８ ｎ×ｎコピーネットワーク ５１，５２ ＦＩＦＯセルバッファ ５３ ＶＣＩトランスレータ ５４ ＶＣＩ参照用テーブル（ＶＣＩ変換テーブル） ６２ 分類要素 ６４ 有限状態マシン ７１ 標準バンヤン経路指定ネットワーク ７２ 基本交換要素 ７５ 線形短縮アレイ ７６ 有限状態マシン ８４ 入力リンク ８５ 出力リンク ８６ ｐ×ｐクロスバー １００ 交換機 １０１ 入力回線 １０２ 出力回線 １０３ 別の入力回線 １０４ 別の出力回線 １０６ 交換網
フロントページの続き (51)Int.Cl.5 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０４Ｑ 3/42 １０５ Ｃ 9076−5Ｋ 8529−5Ｋ Ｈ０４Ｌ 11/20 １０２ Ｚ 8529−5Ｋ １０２ Ｄ

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】 非トランクグループ化入力からパケット
    によって指定されたバーチャル回線上のトランクグルー
    プ化出力および非トランクグループ化出力へパケットを
    交換する非ブロッキング自己経路指定式交換網を有する
    交換機であって、 前記交換網は、複数の入力を同一出力へ同時にアクセス
    させるために、分類ネットワークと、前記分類ネットワ
    ークの次に配置された複数の経路指定ネットワークを有
    し、前記各バーチャル回線上のパケットの順序を予約す
    る手段を備えていることを特徴とする交換機。
JP10818093A 1992-05-20 1993-05-10 トランクグループ入力／出力モードを備えた交換機 Expired - Lifetime JP3447321B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/887162 1992-05-20
US07/887,162 US5325356A (en) 1992-05-20 1992-05-20 Method for aggregating ports on an ATM switch for the purpose of trunk grouping

Publications (2)

Publication Number Publication Date
JPH0637799A true JPH0637799A (ja) 1994-02-10
JP3447321B2 JP3447321B2 (ja) 2003-09-16

Family

ID=25390569

Family Applications (1)

Application Number Title Priority Date Filing Date
JP10818093A Expired - Lifetime JP3447321B2 (ja) 1992-05-20 1993-05-10 トランクグループ入力／出力モードを備えた交換機

Country Status (4)

Country Link
US (1) US5325356A (ja)
EP (1) EP0571152B1 (ja)
JP (1) JP3447321B2 (ja)
DE (1) DE69332426T2 (ja)

Families Citing this family (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5544168A (en) * 1991-08-02 1996-08-06 Gpt Limited ATM switching arrangement
US5796966A (en) * 1993-03-01 1998-08-18 Digital Equipment Corporation Method and apparatus for dynamically controlling data routes through a network
JP2518515B2 (ja) * 1993-05-27 1996-07-24 日本電気株式会社 高速コネクション設定パケット交換機
CA2143495A1 (en) * 1994-03-21 1995-09-22 Rasoul M. Oskouy Method and apparatus for reordering incoming interleaved asynchronous transfer mode cells
US6151301A (en) * 1995-05-11 2000-11-21 Pmc-Sierra, Inc. ATM architecture and switching element
US5583861A (en) * 1994-04-28 1996-12-10 Integrated Telecom Technology ATM switching element and method having independently accessible cell memories
US5878215A (en) * 1994-05-23 1999-03-02 Mastercard International Incorporated System and method for processing multiple electronic transaction requests
US5517495A (en) * 1994-12-06 1996-05-14 At&T Corp. Fair prioritized scheduling in an input-buffered switch
US5627836A (en) * 1995-01-31 1997-05-06 Bell Atlantic Network Services, Inc. VPI/VCI administration
US5590123A (en) * 1995-05-23 1996-12-31 Xerox Corporation Device and method for use of a reservation ring to compute crossbar set-up parameters in an ATM switch
US5812775A (en) * 1995-07-12 1998-09-22 3Com Corporation Method and apparatus for internetworking buffer management
US5748633A (en) * 1995-07-12 1998-05-05 3Com Corporation Method and apparatus for the concurrent reception and transmission of packets in a communications internetworking device
US5651002A (en) * 1995-07-12 1997-07-22 3Com Corporation Internetworking device with enhanced packet header translation and memory
US5796944A (en) * 1995-07-12 1998-08-18 3Com Corporation Apparatus and method for processing data frames in an internetworking device
US5825774A (en) * 1995-07-12 1998-10-20 3Com Corporation Packet characterization using code vectors
EP0850519A1 (en) * 1995-09-08 1998-07-01 Next Level Communications Fttc interface circuitry as a physical layer entity
DE19540160C2 (de) * 1995-10-27 2000-05-31 Andreas Kirstaedter Verfahren zur Koordinierung über serielle Leitungen von eingangsgepufferten ATM Vermittlungseinrichtungen zur Vermeidung von Ausgangsblockierungen
AU1697697A (en) 1996-01-16 1997-08-11 Fujitsu Limited A reliable and flexible multicast mechanism for atm networks
US5838681A (en) * 1996-01-24 1998-11-17 Bonomi; Flavio Dynamic allocation of port bandwidth in high speed packet-switched digital switching systems
US5867653A (en) * 1996-04-18 1999-02-02 International Business Machines Corporation Method and apparatus for multi-cast based video conferencing
US5862329A (en) * 1996-04-18 1999-01-19 International Business Machines Corporation Method system and article of manufacture for multi-casting audio visual material
US5917819A (en) * 1996-04-26 1999-06-29 Cascade Communications Corp. Remapping of ATM cells for multicast transmission
US6442172B1 (en) 1996-07-11 2002-08-27 Alcatel Internetworking, Inc. Input buffering and queue status-based output control for a digital traffic switch
US5768257A (en) 1996-07-11 1998-06-16 Xylan Corporation Input buffering/output control for a digital traffic switch
US5949789A (en) * 1996-11-21 1999-09-07 Xerox Corporation Arbitration ring for accessing a limited bandwidth switching network
US5930256A (en) * 1997-03-28 1999-07-27 Xerox Corporation Self-arbitrating crossbar switch
US6288739B1 (en) 1997-09-05 2001-09-11 Intelect Systems Corporation Distributed video communications system
KR20000055431A (ko) * 1999-02-05 2000-09-05 서평원 에이티엠 스위칭 시스템에서 멀티캐스팅 망
US7016301B1 (en) * 1999-09-01 2006-03-21 Cisco Technology, Inc. Fair multiplexing scheme for multiple input port router
JP3570366B2 (ja) * 2000-09-13 2004-09-29 日本電気株式会社 アービタ回路及びそれに用いる出力セルのアービトレーション方法
US6999418B2 (en) * 2001-12-21 2006-02-14 Fujitsu Limited System and method for reduced frame flooding
CN105847191B (zh) * 2016-03-23 2019-03-01 华为技术有限公司 一种基于重排序算法的交换设备

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4839324A (en) * 1988-08-26 1989-06-13 E. I. Du Pont De Nemours And Company Composition for polymerization with improved activator system
US4893304A (en) * 1988-09-02 1990-01-09 Bell Communications Research, Inc. Broadband packet switch with combined queuing
DE3942977A1 (de) * 1989-12-23 1991-06-27 Standard Elektrik Lorenz Ag Verfahren zum wiederherstellen der richtigen zellfolge, insbesondere in einer atm-vermittlungsstelle, sowie ausgangseinheit hierfuer
US5132965A (en) * 1990-05-03 1992-07-21 Pacific Bell Nonblocking parallel banyan network
CA2048198C (en) * 1990-08-09 1996-06-04 Kai Y. Eng Growable switch
JPH04229747A (ja) * 1990-08-17 1992-08-19 Hitachi Ltd パケット交換方法、およびパケット交換システム

Also Published As

Publication number Publication date
EP0571152B1 (en) 2002-10-23
DE69332426T2 (de) 2003-03-06
DE69332426D1 (de) 2002-11-28
EP0571152A3 (en) 1997-10-22
EP0571152A2 (en) 1993-11-24
JP3447321B2 (ja) 2003-09-16
US5325356A (en) 1994-06-28

Similar Documents

Publication Publication Date Title
US5305311A (en) Copy network providing multicast capabilities in a broadband ISDN fast packet switch suitable for use in a local area network
JP3447321B2 (ja) トランクグループ入力／出力モードを備えた交換機
EP0571166B1 (en) Switching network with reservation ring
US5327420A (en) Method for building multi-bit parallel Batcher/banyan networks
US6667984B1 (en) Methods and apparatus for arbitrating output port contention in a switch having virtual output queuing
US5923656A (en) Scalable broad band input-queued ATM switch including weight driven cell scheduler
US6449283B1 (en) Methods and apparatus for providing a fast ring reservation arbitration
US5689508A (en) Reservation ring mechanism for providing fair queued access in a fast packet switch networks
US5511070A (en) Reservation ring mechanism for controlling contention in a broadband ISDN fast packet switch suitable for use in a local area network
US6487213B1 (en) Methods and apparatus for fairly arbitrating contention for an output port
JP3577188B2 (ja) 多段式ネットワークにおけるマルチキャスト・セルのバッファリング
US6160811A (en) Data packet router
US5940389A (en) Enhanced partially self-routing algorithm for controller Benes networks
Duan et al. A high-performance OC-12/OC-48 queue design prototype for input-buffered ATM switches
Sarkies The bypass queue in fast packet switching
WO1993006675A1 (en) Nonblocking multicast fast packet/circuit switching networks
Yun A terabit multiservice switch
Fahmy A survey of ATM switching techniques
Mir A survey of data multicast techniques, architectures, and algorithms
Rathgeb et al. ATM switches—basic architectures and their performance
Kim Multichannel ATM switch with preserved packet sequence
Wong et al. Pipeline banyan-a parallel fast packet switch architecture
JPH0637798A (ja) パケット交換機の予約リング機構
Keyvani VHDL implementation of a high-speed symmetric crossbar switch
Newman Fast packet switching for broadband ISDN

Legal Events

Date Code Title Description
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20030526

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

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

Free format text: PAYMENT UNTIL: 20070704

Year of fee payment: 4

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

Free format text: PAYMENT UNTIL: 20080704

Year of fee payment: 5

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

Free format text: PAYMENT UNTIL: 20080704

Year of fee payment: 5

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

Free format text: PAYMENT UNTIL: 20090704

Year of fee payment: 6

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

Free format text: PAYMENT UNTIL: 20090704

Year of fee payment: 6

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

Free format text: PAYMENT UNTIL: 20100704

Year of fee payment: 7

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

Free format text: PAYMENT UNTIL: 20110704

Year of fee payment: 8

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

Free format text: PAYMENT UNTIL: 20110704

Year of fee payment: 8

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

Free format text: PAYMENT UNTIL: 20120704

Year of fee payment: 9

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

Free format text: PAYMENT UNTIL: 20130704

Year of fee payment: 10

EXPY Cancellation because of completion of term