JPH0779352B2

JPH0779352B2 - パケット選択装置

Info

Publication number: JPH0779352B2
Application number: JP33683789A
Authority: JP
Inventors: エル．リンシェン
Original assignee: アメリカンテレフォンアンドテレグラフカムパニー
Priority date: 1988-12-29
Filing date: 1989-12-27
Publication date: 1995-08-23
Anticipated expiration: 2010-08-23
Also published as: EP0376597A2; JPH02237337A; DE68921864T2; DE68921864D1; EP0376597B1; EP0376597A3; US4937817A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、パケット通信網のための入力装置に関し、更
に詳細には、パケットの伝送先の受信可能性または不可
能性に基づいてパケットを伝送先に送るために入力パケ
ットを選択する装置に関する。

〔従来の技術〕

色々な形式のデジタル通信の交換網として、パケット交
換装置が望ましいことが実証されてきた。このような交
換網の入力に、データ部分とパケットの伝送先に対する
数値指定部分とをそれぞれ含むパケットを入力すると、
その交換網は、各パケットを識別した伝送先に送る。

パケット網によって伝達されるトラヒック（総伝送デー
タ）は、突発的に増える傾向がある。配分のために送ら
れてくるパケットが多い期間もあれば、また、殆どパケ
ットが到来しない期間もある。突発的なトラヒックを交
換するパケット網は、経済的な理由から、トラヒックを
最大速度ではなく平均速度で伝達するように管理され
る。このような通信網では、トラヒック速度の平均化に
役立つように、実際の交換網の前、内部、またはその出
力でパケットのバッファ処理も行われる。

通信網の入力でパケットのバッファ処理を行うことは、
ソート後展開する通信網（バッチャ−バンニャンの通信
網とも称する）のような簡単な通信網構造を使用するこ
とができるので、好都合である。周知の入力バッファ装
置では、複数の並列バッファから、先入れ先出し規則ま
たはパケットの優先度に基づいてパケットが選択され
る。このため、パケットが「無弁別」伝送される結果と
なり、パケットの伝送先がパケット到着時に受信可能で
あると言う確証もないままパケットが通信網に送られる
ことになる。このような無弁別伝送を行うと、伝送先が
ビジーなために使用できないパケットも伝送されるの
で、通信網の資源が無駄になり、通信網のスループット
（総体効率）が低下する結果となる。

いくつかの研究によれば、パケットの無弁別伝送を行う
通信網のスループットは、せいぜい59％程度に過ぎない
（例えば、1986年のヒューストンでのIEEE世界通信会議
（IEEE Global Communication Conference）と報告誌
（p.659）に掲載のエム・ジェイ・キャロル（M.J.Karo
l）他による論文「空間分割パケット・スイッチに関す
る入力対出力の行列待ち（Input versus Output Queuin
g on a Space Division Packet Switch）」）。ブロッ
ク化したパケットを再伝送する装置を具備することによ
り、この低いスループットによる影響を緩和する試みが
行われてきた。このような影響緩和の試みにより若干の
改善は得られたが、結果的に、パケットの遅れが増加
し、網構造がさらに複雑になった。

伝送先の有効度に基づいて配分するためにパケットを選
択する一極集中型の装置が作られた。このような装置で
は、到来するすべてのパケットまたは到来するすべての
パケットの伝送先の情報が単一のユニットに集積され、
集積された全パケットの伝送先の情報およびパケットの
伝送先の有効性に基づいてパケットが選択される。この
ような一極集中型の装置は、パケット配分速度が制限さ
れ、考慮するべきパケットの総数および選択するべき数
が同じであれば、市販の高性能配分システムのパケット
速度に比べて低速である。

従って、伝送先の有効性に基づくパケットの選択という
スループット上の利点を与えると共に、市販の高性能パ
ケット・システムと併用し得る高いパケット速度で動作
するパケット選択装置に対する必要性が、当技術分野に
存在する。

〔発明の概要〕

本発明の原理に従えば、上記の課題は解決し、技術的進
歩が達成される。本発明においては、各々が複数のパケ
ットをソートする複数の入力ユニット、および各々が伝
送先処理状態指示子に関係付けられた複数の伝送先のア
ドレス（目的アドレス）を各入力ユニットに与える装置
を備えたパケット選択装置によって、パケット選択動作
の一部として、パケット伝送先の有効性が分散的にで吟
味される。与えられた目的アドレスが記憶されているパ
ケットの何れかの伝送先の情報と一致し、かつその与え
られた目的アドレスに関係付けられた伝送先処理状態指
示子が伝送先の有効性を示している場合、各入力ユニッ
トの選択器は、それが記憶している複数のパケットのう
ちの１つを選択する。複数の入力ユニットによるパケッ
トの選択を全体的なパケット選択動作の一部として各ユ
ニットが同時に行うことによって、市販の高性能パケッ
ト・システムと併用可能な高速動作を与えている。

本発明の一特徴に従がえば、各伝送先に対してパケット
を１つだけ選択する性能が改善される。本発明において
は、アドレスを与える装置によって、各入力ユニット
に、複数のアドレスの中から異なるアドレス１つずつ
と、各々に関する処理状態指示子とが同時に与えられ
る。また、単一パケットの選択性が強化されるのは、選
択装置が一致しているアドレスに関係付けられた処理状
態指示子を無効性を示すように変更することによってそ
のアドレスを無効にし、更にその無効にした選択装置に
接続された入力ユニットが無効性を示している処理状態
指示子に関係付けられたパケット伝送先に対してパケッ
トを選択することが禁止されている場合である。また、
一実施例においては、入力ユニットがパケットを選択す
ると、以後その入力ユニットはそれ以上のパケットの選
択が禁止される。

実施例では、目的アドレスを与える機能を各入力ユニッ
トに分散することにより、さらなる速度上の利点を実現
している。各入力ユニットは、一連の目的アドレスを与
えるために規則的な間隔（選択期間と称する）で増加さ
れるカウンタを備えている。各カウンタが各選択期間の
間に他のカウンタとは異なった目的アドレスを与えるこ
とを保証するために、異なった開始値が各カウンタ内に
設定される。この初期値は、その入力ユニットにおいて
各入力ユニットに予め割り当てられた特有の識別子から
求められる。発生した乱数を全入力ユニットに送り、そ
の乱数を所定の識別子に加算すれば、都合よく各カウン
タの初期値が得られる。

複数の目的アドレスを与えるためにカウンタを用いる
と、発生される選択期間信号の数を選ぶことによって、
各入力ユニットに与えられる目的アドレスの数を選択で
きるようになる。説明の一実施例においては、伝送先の
数と等しい数の選択期間信号を発生することによって、
伝送先のすべてのアドレスが与えられる。

パケットの伝送先の有効性または無効性が定義される処
理状態指示子は、選択期間に同期して入力手段から入力
手段へと移される。説明の実施例では、全入力手段のカ
ウンタに記憶されている全パケット目的アドレスに１つ
の数列が含まれており、処理状態指示子を送るために、
入力ユニットは、この数列と逆の順序で接続される。こ
のように接続される結果、入力手段は、そのカウンタ内
部に特有の目的アドレスを有し、１つ前の選択期間の間
にそのアドレスを持っていた入力手段から、その特有の
アドレスに対応する処理状態指示子を受け取る。これに
よって目的アドレスと処理状態指示子との対応が維持さ
れる。

１つの入力ユニットから次の入力ユニットに送られる処
理状態指示子の値は、送信側の入力ユニットによって管
理される。入力ユニットが、ある選択期間の間にパケッ
トを選択しない場合、次の入力ユニットに送られる処理
状態指示子は、その前の選択期間の間に送信側の入力ユ
ニットが受信した処理状態指示子と同じである。それに
対して、入力ユニットが、ある選択期間にパケットを選
択した場合、次の選択期間の間に次の入力手段に送られ
る処理状態指示子は、目的アドレスの無効性を示す。

パケット選択の一部として、カウンタから与えられる目
的アドレスと記憶されている複数のパケットの伝送先情
報とが比較される。この比較を迅速に行うために、各入
力ユニットが複数の比較器を備え、これらの各比較器に
よって、記憶されているパケットの１つの伝送先情報が
カウンタから与えられた目的アドレスと比較される。こ
のように平行して比較することにより、パケットの選択
だけでなく、伝送先の処理状態指示子の更新にも使用さ
れる比較結果が与えられる。

パケットを受信するパケット伝送先の個々の有効性を示
す状態指示子が、本発明の実施例の入力ユニットに与え
られる。各入力ユニットの許可を与える装置は、この状
態指示子によって制御することができるので、各入力手
段から一度に１つの伝送先にのみ送るためのパケットを
選択することが可能となる。

〔実施例〕

第１図は、16個の入力ポート102および16個の出力ポー
ト103を有するパケット交換網101を含む、本発明の実施
例のブロック図である。交換網101は、ホワング他によ
る米国特許第４、516、238号において説明された形式の
ものであり、交換網の各出力ポートに向けられたパケッ
トを１つずつしか含まないような入力パケットの集合に
用いられるノンブロッキング（非阻止）型である。各入
力ポート102は、トランク制御装置105によって入力パケ
ット通信路104に接続され、トランク制御装置105は、そ
れに接続された通信路104から到来するパケットを受信
してバッファ108に記憶し、接続されている入力102に送
るパケットをバッファ108から選択する。

第１図のトランク制御装置105は、パケット期間の開始
時に交換網101にパケットを一斉に送るように、すべて
同期して動作する。パケット期間は、クロック回路106
からの信号によって定義される繰り返し期間であり、接
続のパケット期間が始まる前に１つのパケットを完全に
送れるだけの長さがある。

各トランク制御装置105は、入力パケットを格納するバ
ッファ108、交換網101に送るためにバッファに格納され
ているパケットを選択する選択器109、および選択され
たパケットを伝送するまで保持する出力レジスタ110を
備えている。パケットの選択においてトランク制御装置
が協調し合うことにより、一パケット期間の期間中に交
換網101に送られるパケットが同一の網出力ポート103に
重複して向けられることがないようにしている。このよ
うな事前選択処理によって、交換網101におけるパケッ
ト阻止を無くし、交換網のスループットを改善する。

各パケット期間の期間中、各トランク制御装置105の選
択器109は、各出力ポート103のアドレスが与えられると
ともに、そのアドレスで表される出力ポートの次のパケ
ット期間における有効性または無効性に関する処理状態
指示子も与えられる。特定のアドレスの提示は、一度に
付きただ１つの選択器に対して行われるのであり、また
選択器がある特定の伝送先の出力に向けられたパケット
を選択した場合には、その選択器は、そのアドレスがそ
の出力ポートを無効として他のトランク制御装置105に
示すようにする。次のパケット期間が始まる前に、各ト
ランク制御装置は、それ自体が選択したパケットがある
場合、それを次のパケット期間に交換網101に送るため
に、そのパケットを出力レジスタ110に移す。

パケット選択動作の一部として、選択器109は、出力ポ
ート103を表す与えられた目的アドレスをバッファ108内
の所定数のパケットの伝送先情報と比較して、それらの
パケットの中に、その目的アドレスによって表された出
力ポートに送るべきパケットが存在するかどうかを判定
する。比較する所定数のパケットの選択は、レジスタに
よって行われる。その所定数を大きくすれば、スループ
ットは最も大きくなるが、結果として、選択器109は複
雑となり、遅くなる可能性がある。所定数が小さけれ
ば、選択器109は簡単になるが、スループットの改善度
が小さくなることがある。

第１表は、128x128スイッチについて、所定数に対する
最大スループットを模擬的に求めた結果である。59％の
スループットは、送信パケットの59％が阻止されなかっ
たということである。現在の例では、選択器109におい
て、与えられた目的アドレスは、バッファ内の４個のパ
ケットの伝送先情報と比較される、つまり、所定数は４
に等しい。

各パケット期間は、パケット伝送先の数に等しい多くの
選択期間（第３図）に分割されている。本実施例では出
力ポートが16個あるので、パケット期間は、16の選択期
間に分割されている。各選択期間の間に、選択器109
は、１つの出力ポート103の目的アドレス、および次の
パケット期間中のその出力ポートの有効性もしくは無効
性を定義する導線120上の処理状態信号を受け取る。パ
ケット期間の終わりには、各選択器は、すべての出力ポ
ート103に向けられたパケットに対する検査を終了して
いる。

各トランク制御装置105は、そのトランク制御装置に一
連の目的アドレスを与えるために使用する２進カウンタ
115を備えている。カウンタ115は、出力ポート103全部
のアドレスを表すのに充分な４つのビット位置で構成さ
れている。各パケット期間の初めに、各カウンタ115に
は、それを含むトランク制御装置105に特有な２進値が
ロードされる。この特有な値は、各トランク制御装置に
予め割り当てて識別子レジスタ116に格納している特有
のトランク制御装置識別子から取ったものである。第１
図のトランク制御装置105に割り当てられた識別子は、
一番上のトランク制御装置が「0000」、中間の14個のト
ランク制御装置が順に「0001」から「1110」まで、そし
て一番下のトランク制御装置が「1111」である。

各パケット期間の最初に、加算器118において、乱数発
生器117からの乱数を各トランク制御装置の識別子に
（モジュロ16として）加算し、この結果を導線119を介
してカウンタ115に送る。乱数をトランク制御装置の識
別子に加えることにより、カウンタ115には「0000」か
ら「1111」までの値が順に記憶されるが、カウンタ115
内部の実際の値は、その乱数によって決まることにな
る。このように、各パケット期間の最初に各選択器109
に与えられる目的アドレスを無作為に変えることによ
り、パケット選択の公平さが、改善される。カウンタ11
5に記憶されている値は、出力ポート103の目的アドレス
を表し、選択器109に入力として与えられる。

また、各選択器109は、カウンタ115内のアドレスで表さ
れる出力ポートが次のパケット期間中に有効か無効かを
明示する、導線120上の処理状態信号も受け取る。選択
器109への処理状態信号は、隣の高い方のトランク制御
装置識別子を有するトランク制御装置の選択器によって
生成される。一番下のトランク制御装置（識別子＝「11
11」）の選択器109への処理状態信号は、一番上のトラ
ンク制御装置（識別子＝「0000」）の選択器によって生
成されることに注意を要する。処理状態信号は、通信路
120を介して選択器から選択器へとディジー・チェーン
式に送られる。本実施例における各パケット期間は、第
３図に示すように０から15までの番号を付した16の選択
期間に分割されている。第１の選択期間の間に、すべて
の選択器109が、それぞれに接続されたカウンタ115から
は特有の目的アドレスを、そして通信路120からは伝送
先が有効である（まだ選択された伝送先はない）ことを
明示する処理状態信号を受け取る。カウンタ115内の目
的アドレスは、バッファ108からの最大４個の目的アド
レス情報と比較される。選択器109は、一致するものが
無ければ何もしないが、一致するものがある場合には、
その一致するパケットをバッファ108から出力レジスタ1
10に移し、その選択器の内部に禁止信号を発生し、さら
に選択された伝送先の無効性を明示する処理状態信号を
生成する。禁止信号は、選択器のうちで一致したパケッ
トを検出したものが生成し、その生成中の選択器がそれ
以上パケットを選択するのを次のパケット期間まで禁止
するために使用される。

クロック回路106は、導線121を介して各カウンタ115に
送られるカウンタ・インクリメント信号を発生すること
によって第２の選択期間を開始させる。カウンタ115
は、そのインクリメント信号に対し、そのカウンタ値に
（モジュロ16として）１を加えることによって応答し、
各選択器に次に高い指定を行う。またこのとき、各選択
器も、順序的に次の選択器に新たな処理状態信号を送
る。この新たな処理状態信号は、その生成中の選択器が
前の（第１の）選択期間中にパケットを選択しなかった
場合は、有効性を示し、その生成中の選択器が前の選択
期間中にパケットを選択した場合は、無効性を示す。

第２およびそれ以降の選択期間において、無効性を明示
する処理状態信号を受信している選択器109では、仮に
それによって格納されているパケットのうちの１つの伝
送先情報がそのカウンタ値に一致しても、パケットは選
択されない。有効性を明示する処理状態信号を受信して
いる選択器は、（一致が存在すれば）上記のようにして
パケットを選択する。

各カウンタ115が、第３の選択期間の始めに再びインク
リメントされ、新たな処理状態信号が、選択器の間を次
々と順番に送られる。新たな処理状態信号が伝送先の有
効性を示すのは、（その信号を発生している選択器を含
めて）前の何れの選択器も、その信号を受信中の選択器
109のカウンタ115によって表される伝送先を選択したこ
とがない場合である。同様に、新たな処理状態信号が伝
送先の無効性を示すのは、（その信号を発生している選
択器を含めて）前の何れかの選択器が、その信号を受信
中の選択器109のカウンタ115によって表される伝送先を
選択したことがある場合である。

選択期間は、前記のようにして第16期間の終わりまで続
き、そこで、目的アドレスとそれに関係付けられた処理
状態信号がすべて各選択器109に示されたことになる。
このとき、トランク制御装置105の出力レジスタ110は、
パケット期間の間に選択されたパケットをすべて含んで
いる。第16選択期間の終了時に、すべての選択器が再び
パケットを選択できるように、すべての処理状態信号を
有効性を示すように再設定し、選択器109の内部への禁
止信号を解除することによって、新たな選択段階が開始
される。選択期間の前記の過程は、次のパケット期間の
間に繰り返し、前のパケット期間の間に選択されたパケ
ットは、交換網101に送られる。

第３図に示したパケット期間は、パケット期間全体を占
める０から15までの16個の等しい選択期間に分割されて
いる。第４図に、16番目の選択期間がパケット期間の最
後の１つ前で終わるような、パケット期間の別な分割方
法を示す。これによって、パケットを選択した後に、パ
ケットを出力レジスタ110に移し、各選択器内部で禁止
信号と処理状態信号とをリセットする時間を残してい
る。

第２図は、トランク制御装置105の構造を表し、選択器1
09の内部を示す。第２図において、処理状態信号通信路
120の入力部分は、120−１と記し、この通信路の出力部
分は120−２と記してある。

選択器109には、４つのレジスタ126、およびバッファ10
8から記憶されているパケットの情報を読み出し、各レ
ジスタ126にそれを置く制御器125が含まれる。各レジス
タ126には、バッファ108内のパケットの目的アドレスを
格納するアドレス部（ADDR）、およびアドレス部に格納
された目的アドレスを有するパケットを格納するバッフ
ァ108における位置を定義するポインタ（PTR）が含まれ
る。各レジスタ126のアドレス部は、４つの比較器128の
うちの対応する比較器へ１つの入力として加えられる。
また、各比較器は、伝送路129を介してカウンタ115の現
在の数値も受け取る。カウンタ115の値が対応するレジ
スタ126に格納されているアドレスと一致した場合、各
カウンタ128は、４つのフリップフロップ130のうち対応
するものを「１」の状態に設定する。フリップフロップ
130の出力は、ORゲートに接続され、レジスタ126のアド
レス部の何れかがカウンタ115の値と一致した場合、そ
のORゲート132の出力が「１」となるようにしてある。

ORゲート132の出力は、導線113を介してANDゲート134へ
入力として与えられ、このゲートのもう一方の入力は禁
止フリップフロップ135に接続される。禁止フリップフ
ロップ135は、各パケット期間の始めにANDゲート134に
「１」を与えるようにセットされ、その後、リセットさ
れると、禁止信号「０」を発生して、１つのパケット期
間の間にパケットを２つ選択することを禁止する。AND
ゲート134の出力は、フリップフロップ135が「１」にセ
ットされている間はORゲート132の出力と同じであり、
フリップフロップ135が「０」にリセットされている時
は「０」である。ANDゲート134の出力は、ANDゲート136
およびORゲートの入力に与えられる。

ORゲート137により、すぐ後の選択期間中に次の選択器
に与えられる伝送先処理状態信号が制御される。ORゲー
ト137は、ANDゲート134の出力および導線120−１を介し
て先行の選択器から来る処理状態信号を入力として受信
する。ORゲート137の伝送先処理状態信号出力が「１」
となるのは、先行の選択器が、現在カウンタ115に表さ
れている目的アドレスを選択した場合か、またはレジス
タ126のアドレスの１つが、カウンタ115の値と一致する
場合の何れかである。ORゲート137の出力は、フリップ
フロップ138のデータ入力に与えられる。各選択期間の
始めに、フリップフロップ138は、クロック回路106から
の導線上140の信号によって反転して、そのデータ入力
の処理状態信号を処理状態信号出力路120−２を介して
次の選択器109に送って格納するようにする。フリップ
フロップ138は、各パケット期間の始めに「０」にクリ
アされ、遊休状態を示す。

また、先行の選択器109からの導線120−１上の処理状態
信号は、インバータ139を介してANDゲート136の入力に
も与えられる。クロック回路106からのストローブ信号
は、各選択期間の終了時に、ANDゲート136の残りの入力
143に与えられる。このストローブ信号に従って、先行
の選択器109からの導線120−１上の処理状態信号が有効
性を示し、かつANDゲート134の出力が「１」でパケット
伝送先の一致を示している場合に限り、ANDゲート136の
出力は「１」である。この入力の組み合わせが起こるの
は、カウンタ115によって表される伝送先が、有効で、
かつレジスタ126に格納されているアドレスの１つに一
致する場合である。ANDゲート136からの出力は、「１」
の場合パケットが選択されたことを示すが、導線142を
介してフリップフロップ135のリセット入力および制御
器125に与えられる。導線142の信号が「１」の場合、フ
リップフロップ135は、ゼロ状態にリセットされ、選択
器109がそれ以上パケットを選択することを禁止する。
各パケット期間の最初には、フリップフロップ135は、
クロック106からの導線141上の信号によって、すべて状
態「１」にセットされる。

また、ANDゲート136の出力は、導線142を介して制御器1
25に送られ、一致し有効なパケットが発見されたことを
知らせる。制御器125は、導線142上の「１」に応じて、
比較器128による以降の比較を禁止し、通信路144によっ
てフリップフロップ130の各々に問い合わせる、フリッ
プフロップ130が「１」の状態にあることは、レジスタ1
26のうちの関係付けられた１つにあるアドレスが、カウ
ンタ115の値と一致することを意味する。状態「１」に
あるフリップフロップ130を検出すると、制御器125は、
通信路145を介して関係付けられたレジスタ126のポイン
タ部を読み、そのポインタを用いてパケットをバッファ
108から出力レジスタ110へ移す。制御器110は、パケッ
トを出力レジスタ110に移すと、新たなアドレスおよび
別なパケットを表すパケット・ポインタを、一致した直
後のレジスタ126に格納する。

制御器125は、同じ選択器内109のレジスタが同一の伝送
先を表すことがないように、パケットポインタをレジス
タ126に格納するので好都合である。このため、パケッ
ト効率が向上する。そのようにする代わりに、制御器12
5は、バッファ108がパケットを受信した順番にパケット
ポインタをレジスタ126に配列することも可能である。
このようにすると伝送先が同じパケットはレジスタ126
で同時に表現されるので、制御器125には、２つ以上の
一致パケットが検出された場合、一致パケットを１つ選
択する能力が備わる。

前記の実施例の交換網は、トランク制御装置およびパケ
ット伝送先出力ポートを同数備えていた。また、本発明
により、入力および出力が同数の場合、パケット効率も
向上する。例えば、入力の数が８で、出力の数が16であ
る場合、選択器109は、パケットの選択に関しては前記
のように動作する。しかし、カウンタ115の値と処理状
態信号との関係を維持するためには、８選択期間と同等
な遅延ユニット（第５図）を処理状態信号路120に挿入
する必要がある。本発明の実施例では、一番上のトラン
ク制御装置105と一番下のトランク制御装置105との間の
導線120に直列に、第５図の遅延ユニットを接続した。
遅延ユニットは、各選択器109におけるフリップフロッ
プ138と同様に制御された８個のフリップフロップから
構成されている。

前記の説明は、パケット交換網を介してパケット伝送に
関する。本発明の原理は、伝送先である利用装置または
利用資源に対する目的アドレスを含む任意のデータ・メ
ッセージの配分に等しく適用することができる。さら
に、「伝送先処理状態信号（指示子）」なる用語を用い
て、パケットの伝送先の有効性または無効性を識別する
信号を示した。このような伝送先処理状態信号は、利用
装置の有効性を記述する任意のビジー／アイドル形式の
状態指示子で差し支えない。

【図面の簡単な説明】

第１図は、本発明を具体化するシステムのブロック図、第２図は、第１図のトランク制御装置の図、第３図および第４図は、本発明の実施例で使用された時
間間隔の調整を示す図、第５図は、一実施例において使用された遅延ユニットの
ブロック図である。

Claims

【特許請求の範囲】

【請求項１】一連の複数の伝送先アドレスを有する複数
のパケット伝送先へ伝送するためにパケットを選択する
装置において、乱数発生器（117）と、それぞれ一連の順序づけられた番号を有する識別手段
（116）を有し、前記複数のパケット伝送先のうちの１
つを識別する伝送先情報を含む複数のパケットを格納す
る複数の入力手段（105）と、前記乱数発生器に接続された前記入力手段のそれぞれに
おいて各入力手段に複数の伝送先アドレスを供給する手
段であって、発生した乱数を前記識別手段からの前記番
号と組み合わせて第１の固有の伝送先アドレスを発生す
る組合せ手段（118）と、前記伝送先アドレスを繰り返
しインクリメントして前記入力手段のそれぞれにすべて
の伝送先アドレスを順次与えるインクリメント手段（11
5）とを有し、各伝送先アドレスによって識別され、先
行する入力手段によって与えられる各伝送先の利用可能
性状態を示す伝送先処理状態指示子を有する伝送先アド
レス供給手段と、前記入力手段のそれぞれにおいて、前記の供給された伝
送先アドレスのうちの１つが前記入力手段に格納された
前記パケットのうちの１つの前記伝送先情報と一致し、
かつその一致した伝送先アドレスに対応する伝送先処理
状態指示子によって前記一致伝送先アドレスで表される
伝送先が有効であることが示されている場合、前記の格
納されたパケットのうちの１つを選択する選択手段（10
9）と、前記入力手段のそれぞれにおいて、前記選択手段によっ
て選択されたパケットを前記入力手段から送信する手段
（110）とからなることを特徴とするパケット選択装
置。
【請求項２】前記選択手段が、与えられた伝送先アドレ
スに関係づけられた前記伝送先処理状態指示子が無効性
を示す場合に前記格納されたパケットのうちの１つを選
択することを禁止する手段を有することを特徴とする請
求項１の装置。
【請求項３】前記伝送先アドレス供給手段が、複数の選
択期間信号を発生する発生手段からなり、前記インクリメント手段が、前記選択期間信号のそれぞ
れに応じて、前記組合せ手段のそれぞれにある伝送先ア
ドレスに同一の数値を加算する手段からなることを特徴
とする請求項１の装置。
【請求項４】前記発生手段が、前記パケット伝送先の数
と同数の複数の前記選択期間信号を発生する手段からな
ることを特徴とする請求項３の装置。
【請求項５】各入力手段が他の入力手段のうちの１つか
らの前記伝送先処理状態指示子を受信するように接続さ
れるように、前記入力手段どうしを閉ループ（120）に
接続する接続手段を有し、さらに前記入力手段のそれぞ
れが、接続された他の入力手段に前記伝送先処理状態指
示子を送信する送信手段（138）からなることを特徴と
する請求項３の装置。
【請求項６】前記送信手段のそれぞれが、前記接続手段
からの伝送先処理状態指示子を受信する手段と、前記選
択期間信号に応じて、前記の受信した前記伝送先処理状
態指示子を前記接続手段に送信する手段とを有すること
を特徴とする請求項５の装置。
【請求項７】前記送信手段のそれぞれが、伝送先の有効
性を示す前記伝送先状態指示子のうちの１つを前記接続
手段から受信する手段と、前記選択手段および前記選択期間信号の１つに応じて、
前記伝送先のうちの１つが無効であることを識別する前
記伝送先処理状態指示子を前記接続手段に送る手段とを
有することを特徴とする請求項６の装置。