JPH04504489A - コネクション指向型ネットワークにおけるコネクションレス・パケットの分散型ルータ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 コネクション指向型ネットワークにおけるコネクションレス・パケットの分散型 ルータ発明の分野 本発明は、複数の階層レベルと、いずれの階層レベルでもネットワークに対して 分散可能な複数のルータを有するパケットルータ（ｐａｃｋｅｔ　ｒｏｕｔｅｒ 　）の分野に係り、特に詳細には、コネクション指向型ネットワーク（ｃｏｎｎ ｅｃｔｉｏｎ　ｏｒｉｅｎｔｅｄ　ｎｅｔｗｏｒｋ　）におけるデータグラム（ ｄａｔａｇｒａａｓ　）　−パケットのルータに関する。

発明の背景 ローカルエリアネットワーク（Ｌｏｃａｌ　ＡｒｅａＮｅ　ｔｗｏ　ｒｋｓ）（ ＬＡＮｓ）によるコンピュータ通信は、一般には、通信設備間にコネクション（ ｃｏｎｎｅｃｔｉｏｎ）をあらかじめ確立することなくデータグラムにより行わ れる。プロトコルの単純さ、コネクションの確立の手続が必要がなく、コネクシ ョンを確立することにより生じる時間遅延をなくし、通信の速度が速くなるので 、これは有利なことである。広い地域でも、距離によりもたらされる限界なしに 、このようなコネクションレス・データグラム通信のような可能性をもつことは 好ましいことである。

経済的理由により広域通信（ｗｉｄｅ　ａｒｅａ　ｃｏａ＋ｍｕｎｉｃａｔｌ。

ｎ）は、分は合った、すなわち共有の搬送様式で提供されるのが最も有利である 。従って、広域データグラム通信に対して望まれることは、現実には公衆ネット ワークの発展と連携していなければならず、また、それを達成する手段は公衆ネ ットワークの一部とされなければならないことである。

広域データグラム通信への研究では、公衆ネットワークの分野において既に２つ の開発が存在している。これらの二つの開発は、電気学会プロジェクト８０２． 　６（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｌｅｃｔｒｉｃａｌａｎｄ　Ｅｌｅｃｔｒ ｏｎｉｃ　ＥｎｇｉｎｅｅｒｓＰｒｏｊｅｃｔ　８０２．６）により標準化され ツツあるメトロポリタン　エリア　ネットワーク（Ｍｅｔｒ。

ｐｏｌ　ｉ　ｔａｎ　Ａｒｅａ　Ｎｅｔｗｏｒｋｓ）（ＭＡＮｓ）と、インター ナショナル　コンスラチブ　コミッテー　オンテレグラフィ　アンド　テレフォ ニ　（Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ５ｕｌａｔｉｖｅ　Ｃｏｍｍ１ｔｔ ｅｅ　ｏｎ　Ｔｅｌｅｇｒａｐｈｙ　ａｎｄ　Ｔｅ１ｅｐｈｏｎｙ）（ＣＣＩＴ Ｔ）スタブ−グループ　ＸＶＩ　Ｉ　Ｉ　（Ｓｔｕｄｙ　Ｇｒｏｕｐ　ＸＶＩＩ Ｉ）により標準化されつつある広帯域サービス総合デジタル網（ＢｒｏａｄΔｂ ａｎｄ　Ｉｎｔｅｇｒａｔｅｄ　５ｅｒｖｉｃｅ　Ｄｉｇｉｔａｌ　Ｎｅｔｗｏ ｒｋ）（Ｂ　ｌ５ＤＮ）である。これらの二つの開発に関する最近刊行された文 献のなかに、アール、エム、ニューマン、ゼット、エル、バドリキス、ジュー。

エル、バレット（Ｒ，Ｍ、Ｎｅｗｍａｎ、Ｚ、Ｌ、Ｂｕｄｒｉｋｉｓ　＆　Ｊ、 Ｌ、Ｈｕｌｌｅｔｔ）による“キューピーニスエックス　マン”　（“Ｔｈｅ　 ＱＰＳＸ　ＭＡＮ”）、ＩＥＥＥ通信誌（ＩＥＥＥ　Ｃｏｍｍｕｎｉｃａｔｉｏ ｎｓ　Ｍａｇａｚｉｎｅ）、Ｖｏｌ、２６．Ｎｏ、４゜ｐｐ２０−２８．４月、 １９８８と、チー、エム、チェン、とデー、ジ、メッサーシュミット（Ｔ、　Ｍ 、Ｃｈｅｎ　ａｎｄ　Ｄ、Ｇ、　Ｍｅｓｓｅｒｓｃｈｍｉｄｔ）による“集中音 声／データ交換“　（“Ｉｎｔｅｇｒａｔｅｄ　Ｖｏｉｃｅ／Ｄａｔａ　Ｓｗｉ ｔｃｈｉｎｇ）、ＩＥＥＥ通信誌（ＩＥＥＥ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　 Ｍａｇａｚｉｎｅ）、Ｖｏｌ、２６．Ｎｏ、６．ｐｐ１６−２６．６月、１９８ ８がある。

ＭＡＮは、典型的には１都市の区域における、データグラム通信を含む総合デジ タル通信を提供するであろう。

もデータグラム通信を提供できるなら、結果的にはＭＡＮを包括することになる 。しかし、現在考えられている通信を中央サーバーにより与えられた特定人への 限定サービスとしただけのコネクション指向型通信を含むにすぎない、 発明の概要 二二に開示された発明は、ＭＡＮとＢ　ｌ５ＤＮに適用可能なデータグラム用ル ータに係るが、本発明の範囲セグメントを有するデータグラムをルーチングする ためのネットワークを提供する。このネットワークは、少なくとも１個のセグメ ント・スイッチング手段と、このスイッチング手段と複数の端末との間に接続さ れ、データグラムを第１ルータから第２ルータヘスイツチングシステムを経由し 、送りかつ、このデータグラムを第２ルータから第２端末へ送るように、第１端 末から発信されたデータグラム内のデータを処理するように構成された複数個の ルータとを備えている。

また、本発明は、少なくとも１個のセグメント・スイッチング手段と、このスイ ッチング手段と複数の端末との間に接続された複数個のルータとを有するネット ワーク内でデータグラムをルーチングする方法を提供する。

この方法は、データグラムを第１ルータから第２ルータヘスツチング手段を経由 し、送りかつ、このデータグラムを第２ルータから第２端末へ送るように、第１ 端末から発信されたデータグラム内のデータを処理しすることを含んでいる。

公知のシステムにおいて、中央データグラム・サーバーは一般にはこの用途に意 図されたものであるが、十分に機能しておらず、本発明によれば分散型ルーチン グ方式が提供される。本発明の方式においてはデータグラムのルータのルーチン ブタスフを、多様性がない場合（即ち、ソースから行き先に至る可能な路がただ 一つしか無い時）はデータグラムをその適切な別のルータに向かわせ、多様性が ある場合は１個の適切な別のルータに向かわせることとすることができる。両ル ータ間に確立された回路が永久的に存在するのであれば、データグラムをコネク ション指向型ネットワークで一つのルータから別のルータべ、回路を確立するこ となく送ることができるとも考えられている。これらの原理は、コネクション指 向型ネットワークが実在の物理回線を有している場合であってもコネクション指 向型ネットワークが仮想回線を有している場合であっても同様に適用することが できる。

更に、ルータは複数の領域（ｄｏｓ＋ａｉｎｓ　）にグループ化することができ 、これらの領域は階層的に相互に接続されることができる。更に、ルータが理論 上は領域の工・ソジ（ｅｄｇｅｓ　）になければならず、従って、２つのはつき りした方向を有するエツジデバイスでなければならないことが有利であると認識 されている。領域ｊから領域ｉへ向けられたルータはＲｊｉと呼ぶことができる 。そのルータは両頭域ｊ、ｉのエツジデバイスである。そのルータは領域ｊから の入力ソケットと、領域ｉへの出力ソケットとを有している。ルータＲ１ｊに関 してはこれと逆である。

ユニバーサル・コネクションレス・データグラム転送にとって、ある領域に入っ ているルータは、その領域を出るルータに永久的に接続されなければならない。

例外は、ルータＲｊｊ、の出力がルータＲ１ｊの入力に接続されていないことで ある。ユニバーサルコネクションを可能にするのにさらに必要なことは、最も高 い階層レベルにある領域を除く全ての領域において、より高い階層レベルにある 領域へ直接あるいは間接に与えられる出力を有するルータが少なくとも１個存在 することである。更に必要なことは、最も高い階層レベルに領域がただ１個存在 することと、この最も高い階層レベルの領域から各領域に到達可能であることで ある。

領域は高速パケットスイッチ又は複数個の入力ポートと出力ポートとを有し、す べてのポートが互いに接続されている非同期転送モードスイッチ（ＡＴＭｓｗｉ ｔｃｈ）を備えそいる。高速パケットスイッチの一例はエイ、ファングとニス、 ナウア（Ａ、Ｈｕａｎｇ＆　Ｓ、Ｋｎａｕｅｒ）による“スターライト、広域帯 デジタルスイッチ−（Ｓｔａｒｌｉｔｅ、　Ａ　Ｗｉｄｅｂａｎｄ　Ｄｉｇｉｔ ａｌ　５ｗ１ｔｃｈ’）。

１９８４、世界電気通信ＩＥＥＥ会議予稿集（Ｐ　ｒ　ｏ　ｃｅｅｄｉｎｇｓ　 ｏｆ　ＩＥＥＥ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｇｌｏｂａｌ　Ｔｅｌｅｃｏｍ ｍｕｎｉｃａｔ　ｉ　ｏｎｓ）　、ｐｐ５．　３．　１−５．　３．　５．に記 載されている。

前述の構造と特性とにより、ルーチングを世界中の最終行き先のアドレスに基づ いてあらゆる場所で行うことができる。また、電話の番号付けに行われている習 慣に近似するように、アドレスそれ自身が３あるいは４個のサブフィールド（ｓ ｕｂｆ　１ｅｌｄ）に分割され、例えば１５桁数のようにアドレス自体が階層的 サブフィールドにサブ分割されていれば、ルーチングのプロセスは、迅速に行わ れることができる。いずれのルータにおけるタスクは、データグラムが適切な次 のルータに到着するように、データグラムが送られるべき回路を指示するルート ラベルに最終行き先のアドレスをトランスレートすることであるとも考えられて いる。

このトランスレートは、候補ラベル（ｃａｎｄｉｄａｔｅｌａｂｅｌ　）と、候 補ラベルに関連する特定の論理変数の値のルックアップにより行われ、最少は、 最終行き先アドレスの各サブフィールドに関連したひとつのラベル候補である。

実際に適応されるラベルを論理変数の値にもとずく簡単な演鐸法により決定する ことができる。適応可能のラベルを決定するこの手続は新しいアルゴリズムに匹 敵する。このアルゴリズムに沿って行われるトランスレーションは高速でおこう ことができ、データグラムが１００Ｍｂｉｔ／ｓ又はそれ以上で送信される際に も、ルーチングが迅速に行われることができる。

本発明は、パケットのすべてのビットが連続して送信される場合であって、可変 長パケットとしてデータグラムが送信されるときのにも、又データグラムが部分 に分割される場合のいずれにしても適用できる。

ＩＥＥＥ８０３．６とＢ　ｌ５ＤＮは固定長のセグメントに分割する。以下に記 載する本発明の詳細な説明は前者の場合のものである。

コネクション指向型ネットワークで差し込みのように転送されるセグメントから データグラムをリアセンブリすることは、メモリの大きさあるいは速度の必要性 においてルートの選択と同様の問題を提起する。本発明によれば、大きいスペー スから小さいスペースへラベルを変換することも問題である。本発明は、少なく とも１セグメントを有するデータグラムをルーチングするネツトワークのルータ を提供する。

このルータは、 データグラムを受信し、このデータグラムから行き先アドレスを読取る第１手段 と、 この第１手段に応答して、前記行き先アドレスにもとずいて出力接続データ（Ｖ ＣＩ　０ＵＴ）を決定する第２手段と、 前記出力接続データ（ＶＣＩ　０ＵＴ）を前記データグラムに含める第３手段と を備え、 前記データグラムは前記ルータから出力されたのち、前記出力コネクションデー タ（ＶＣＩ　０ＵＴ）にもとずいて前記ネットワークにルーチングされるもので ある。

図面の簡単な説明 本発明は、単に例として示す本発明の作動と実施と共に、添付の図面を参照して さらに詳細に説明される。

第１図は本発明のルーチング方式を実施した階層ネットワークの構成図； 第２図はＩＥＥＥ　８０２．６標準セグメントの書式％式％ −の書式図； 第４図はＣＣＩＴＴ　Ｅ、１６４サ一ビス番号の書式第５Ａ図はルータ回路の概 略構成図； 第５Ｂ図は本発明のラベル変換の原理を実施したアドレス／ＶＣＩ変換装置の構 成図；　第６図は再組み立てメツセージの識別子決定回路の構成図；第７図は、 第６図の装置の一部分であるタグサーバの構成図； 第８図は、第５図の装置に必要な優先度エンコーデングに使われる論理回路； 第９図は、第５図の装置のマルチプレクサ−の概略構成図； 第１０図は、第７図の制御装置により実行されるプログラムの流れ図である。

好適な実施例の説明 従来技術においては、データグラムのルーチングでは１又はそれ以上のセントラ ルサーバー（ｃｅ口ｔｒａｌｉｓｅｄ　５ｅｒｖｅｒ）が必要なのは当然とされ ているようである。セントラルサーバーはコンピュータであり、加入者はこれら のコンピュータに対してあらかじめ回線を用意する。加入者はそのコンピュータ へ意図する行き先の指示を含むデータグラムを送り、これに対してコンピュータ はそのデータグラムを指示された行き先へ、再びあらかじめ用意された回線を使 って送る。データグラムを送るのに使われる回線は永久に確立されたものなので 、回線の確立による遅延は無く、この点で従来技術の方式は高速である。しかし 、すべてのデータグラムが１個のプロセッサを介して通信路で送られなければな らないために、従来方式が真実に高速作動あるいは実時間作動を行う機会がまっ たく奪はれることになる。更に、従来技術方式は、相互結合を可能にするのに、 限定された加入者数に制限される。

この問題は、サービス機能を分散し、また、本発明の方式が地球上の通信設備の 実質的部分をおおう程までに際限なく発展でき、全てに対してコネクションレス 又はゲータグラムコネクションを行うことができるように構成することによる本 発明にしたがって回避される。本発明のシステムは、この目的の為に確立される コネクション指向型交換ネットワークあるいは、他の通信トラッフィクを搬送す るためのコネクション指向型交換ネットワークと重複する。

第１図を参照すると、コネクション・ルーチングシステムの全体は複数の領域（ ｄｏｍａｉｎ）に分けられている、第１図において、レベルゼロにおける領域は 円として示され、８１〜ら８５で示されている。各レベルゼロ領域は先に述べた ＱＰＳＸ　ＭＡＮからなってもよい。レベル１．２．３の領域は正方形で示され 、レベル１領域は１０１、１０２で示され、レベル２領域は１０３で示され、レ ベル３領域は１０４で示されいる。この装置は３つのＩ型ルータ１１１．１１３ ．１２９を有し、これらのルータはレベルゼロ領域から入力を受け、レベル１領 域へ出力する。■型ルータ１１２．１１４．１３０はレベル１領域から入力を受 け、レベルゼロ領域は出力する。■型ルータ１１９．１２０．１２１．１２２． １２６．１２８はレベル１領域とより高いレベル領域において入力、出力を行う 。

第１図のシステムに固有のことは、レベルゼロ領域はルーチングを必要としない という仮定である。顧客即ち端末装置がレベルゼロ領域専用に取り付けられてい る。

端末装置は小円で示されていて、例えばレベルゼロ領域８１に取り付けられた端 末装置９１．９２である。これらの領域をルーチングする必要は無い。これは、 これらの領域はただ１個の端末装置を有しているか、コネクションレスデータグ ラム転送を支持する、ＩＥＥＥ８０２．６　ＭＡＮとして標準化されたザブネッ トワークのようなコネクションレスサブネットワークだからであるからである。

後者を選択すると、方式全体で必要なルータの数が減り、両者のうちで最も有利 である。

レベル１領域１０１はルータ１１３の出力ソケットをレベル１領域１０１の、ル ータ１１４を除くすべての■型ルータと■型ルータ１１２．１１６．１１８．１ １９．１２１の入力ソケットに接続する固定された回線とともに示されている。

同様に、ルータ１１４への入力は、Ｉ型ルータと■型ルータのすべての出力に接 続されて示されている。単純化するためにルータ１１３．１１４を抜き出してあ り、同様の線がレベル１領域１０１の各ルータと他のすべてのルータを接続して いる。これは、領域１０２．１０３．１０４のルータに対しても同様であるが、 第１図では図を明瞭にするために示されていない。

ある領域のエツジの周りには、Ｎ個の入ってくるルータとＮ個の出ていくルータ とがあり、２個の領域が互いに反対方向の１対のルータにより接続されていると 仮定すると、各出力ソケットから発生する単方向回線即ちシンプレツク回線（ｓ ｉｍｐｌｅｘ　ｃｉｒｃｕｉｔ　）の数は（Ｎ−１）であり、この数は各入力ソ ケットで終わる固定単信回線の数でもある。その領域における固定単方向回線の 合計数は２Ｎ（Ｎ−１）である。

更に、第１図の領域１０１のルータ１１３を参照して、領域８２で発生し領域８ ２を越えて行くように意図されたデータグラムの例を考えてみる。このデータグ ラムは、ルター１１３により、領域１０１に入力ソケットを有するもう一つのル ータヘルーチングされなければならない。

このルーチングは、データグラムのヘッダーにある最終行き先アドレスにもとづ いて行われる。

本発明の原理を実施するこのタスクと、このタスクの実行は、データグラムのフ ォーマットと、データグラムの発信がＩＥＥＥ　８０２．６　ドラフト　スタン ダード（ＩＥＥＥ　８０２．６　Ｄｒａｆｔ　５ｔａｎｄａｒｄ　（Ｄｒａｆｔ 　Ｄ９．　８月、１９８９）に沿っている場合について説明される。データグラ ムは固定長のセグメントを連続させて送られる。１セグメントのフォーマットは 第１図に示されている。

第２図を参照すると、行は８ビット即ちオクテツト（ｏｃｔｅｔｓ）のグループ を示し、左から右へ、上から下への転送順序である。最初の７オクテツト０１− ０７はセグメントヘッダーで、残りの４６オクテツトのうち４４オクテツトは転 送用にデータをペイロードされ、２オクテツトはセグメントトレーラである。

データグラムは８０００オクテツトまでのいずれの長さでもよく、４４オクテツ トの長さのセグメントで転送される。ＩＥＥＥ　８０２．６スタンダードは、コ ネクションレスデータ通信の他に二つのサービス分野、即ち同時コネクション指 向型と非同時コネクション指向型のコネクションレスデータグラムを提供してい る。これらの三つの分野のセグメントはセグメントへラダーオクテツト０１から ０５までを共有する。あるセグメントがコネクションレスデータグラムの一部分 であるかどうかはＶＣＩ（仮想回線識別子（Ｖｉｒｔｕａｌ　Ｃ１ｒｃｕｉｔ　 Ｉｄｅｎｔｉｆｉｅｒ））フィールド７１の最後の４ビツトの特定の値即ち行０ ４の最初の４ビツトにより示される。これらの４ビツトがすべてＯの時はセグメ ントはコネクションレスである。以下の記載において”ＶＣ１″と“ラベノじは 同じ意味に使われる。

そのセグメントがコネクションレスとすると、そのセグメントがメツセージの始 まり（ＢＯＭ）を携行しているか、メツセージの継続（ＣＯＭ）を携行している か。

メツセージの終わり（ＥＯＭ）を携行しているか、あるいは独立のセグメントメ ツセージ（ＳＳＭ）を携行しているかという情報は２ビットＳ型フィールド即ち 第２図のサブフィールドにより示される。

１個のメツセージのすべてのセグメントは同じメツセージ識別子、（Ｍ　ＩＤ） フィールド７６を携行しなければならない。

１データグラムはオクテツト０８のＳＳＭか８０Ｍセグメントで始まり、ＩＳＯ （Ｉｎｔｅｒｎａｔ　１ｏｎａｌ　５ｔａｎｄａｒｄｓ　Ｏｒｇａｎｉｓａｔｉ ｏｎ）レベル２ヘツダーで始まり、このＩＳＯレベル２ヘッダーにＩＳＯレベル ３ヘッダーが続く。本発明の原理によればルーチングは最終行き先アドレスにも とすいている。

このアドレスはいずれの場合にもレベル３ヘツダーにある。ＩＥＥＥ　８０２． ６スタンダードにより、ＣＣＩＴＴ　Ｅ、１６４最終行き先アドレスはレベル２ ヘツダーにあるることもでき、ルーチングはこのヘッダーにもとづいて行うこと ができる。以下の記載においては後者が適応すると仮定する。ある状況において レベル２ヘツダーが最終行き先アドレスを携行していない場合は、レベル３ヘツ ダーにある行き先にもとすいて、ここに記載されていることがほとんど変更なし に行われる。

第３図はＩＥＥＥ　８０２．６スタンダードに沿ったレベル２ヘツダーのフォー マットを示している。即時に係わりのある行き先アドレス（ＤＡ）フィールド１ ４２のみを有する７個のフィールドがある。このフォーマツする４ビツトの第１ サブフイールドと、６０ビツトのアドレスサブフィールドからなる。アドレスが ＣＣＩＴＴ　Ｅ、１６４に沿ったものである時は、すべての６０ビツトの位置は そのアドレスの１５個の２進化１０進数により占められる。このフォーマットは 第４図に示されている。

本発明のコネクションレスルーチンブタスフとこのタスクを実行するための原理 は、ルータのブロック線図である第５Ａ図を参照することにより理解できる。ル ータは第２図のフォーマットを有するシリアルのセグメントを連続時間で入力ラ イン５２０で受け、それらのセグメントを適切な態様で変更して、それらのセグ メントを出力ライン５３８にシリアルに送り出す。入力と出力とは使用中は連続 し、一定のネットワークの伝送速度である。

たとえば、伝送速度が４４．２１０Ｍｂ　ｉ　ｔ／ｓの場合、この伝送速度は公 衆ネットワークデジタルトランスポートにおける標準ネット速度の一つで、北米 のＤＱＤＢネットワークに使われる計画になっているが、セグメントの、入力出 力速度は１０４．２６９セグメント／秒である。第５Ａ図のアーキテクチャ−と 本発明の構成要素を有するルータは１０４．２６９セグメント／秒以上、例えば 、最近ＤＱＤＢネットワークにも考えられている１４０Ｍｂｉｔ／ｓと１５５Ｍ ｂｉｔ／ｓが可能である。

各ビットあるいはビットグループ、例えば８ビツトグループあるいはオクッテト において入力出力はシリアルとすることができ、このことは本発明の原理を変え るものではない。

ルータは特定可能の標準構成要素からなる。即ち、ラッチ５０３．５０４、デ・ マルチプレクサ−５０６，５０７，５０８、マルチプレクサ−５０９，５１０， ５１２，５１３と、遅延回路５４１．５４２．５４３．５４４からなる。ルータ は本発明の２個のシステムを内蔵している。即ちアドレス−ＶＣＩ　（ａｄｄｒ ｅｓｓ　ｔｏ　ＶＣＴ）　ｈランスレータ５０１と、バケットアセンブラ／・ラ ベルサーバー５０２である。すべての構成要素とこのシステムにおける作動のタ イミングはタイミングコントローラ５０５により制御されており、タイミングコ ントローラ５０５自体はビットあるいはビットグループと、入力におけるセグメ ントのスタートと同期している。

ラッチ５０３は、セグメント型を示す第２図のフォーマットのフィールド７５で あるＳ　型（Ｓ　ＴＹＰＥ）を捕捉する。ラッチ５０３の内容はデマルチプレク サ−５０６、システム５０１．５０２、マルチプレクサ−５１３へ指示を与える 。セグメントが単一のセグメントメツセージ（ＳＳＭ）又はメツセージの始まり （ＢＯＭ）である場合、デ・マルチプレクサ−５０６はセグメントをライン５２ １に出す。セグメントがメツセージの継続（ＣＯＭ）又はメツセージの終わり（ ＥＯＭ）の場合、セグメントはライン５２２に出される。遅延回路５４１は、出 力をいずれにスイッチすべきかについてラッチの内容を考慮しつつ、セグメント の第１ビツト到着に間に合うように、決定が成されるまでセグメントを十分遅ら せるルータを離れるセグメントは、入ってきた時と同じビットフィールドを持っ ていなければならないが、第２図のフィールド７１．７６であるＶＣＩとＭ　Ｉ Ｄは例外である。他の例外は、再計算し変更される２個のサイクリックな冗長フ ィールド（ｃｙｃｌｉｃ　ｒｅｄｕｎｄａｎｃｙ　ｆ’１ｅｌｄ　）である。こ れらはルータ内で行われるのではなく、ルータに続いた別のユニットにおいて行 われる。しかし、その機能は、本発明を変更することなくルータ・システムに組 み込むこともできる。

ルータを離れるセグメントは、直ぐ次の行き先へ行くのに適切なＶＣＩとＭ　Ｉ Ｄを有していなければならない。ＶＣＩは、ＡＴＭスイッチ、例えば第１図の１ ０１あるいは１０３、が所定の入力ソケットから意図された出力ソケットへセグ メントを転送するのに使うラベルである。Ｍ　ＤＩは、あるメツセージの分割さ れたセグメントを論理的に繋ぐラベルであり、所定のソース及び行き先に対する 異なるメツセージのセグメントが並列であってもインタリーブされていてもそれ らの異なるメツセージには異なっていなければならない。

適切なＶＣＩは、最終行き先アドレスあるいは加入者番号、第１図の９１あるい は９７から決定され、最終行き先アドレスあるいは加入者番号はメツセージのヘ ッドエンド、即ちＳＳＭとＢＯＭのフィールド７７の最初に付けられる。最終行 き先は入ってくるＳＳＭとＢＯＭからラッチ５０４によりラッチされ、アドレス ／ＭＣＩトランスレータ（ａｄｄｒｅｓｓ　ｔｏ　ＶＣＴ　ＴＲＡＮＳＬＡＴＯ Ｒ）　５０１　へライン５２７により送られ、アドレス／ＭＣＩトランスレータ ５０１は適切なＶＣＩを決定し、この適切なりＣ１をライン５２８に出す。ＳＳ ＭあるいはＢＯＭはデマルチプレクサ−５０８においてデマルチブレックスされ 、デマルチプレクサ−５０８は、ＳＳＭあるいはＢＯＭが入ってきた際に持って いるＶＣＩとＭ　ＩＤをライン５２５に出し、残りのフィールドをライン５２６ に出す。

ＢＯＭの場合、ライ：／３２４（７）ＶＣＩ　ＩＮとＭ　Ｉリアセンブラー／ラ ベルサーバー５０２へ読み込まれ、メツセージリアセンブラー／ラベルサーバー ５０２はそのメツセージの続＜ＣＯＭとＥＯＭを認識し、ＣＯＭとドは遅延回路 ５４３を経由してマルチプレクサ−５１２に送られ、マルチプレクサ−５１２は 残りのツイールドラセージリアセンブラー／ラベルサーバー５０２により出され る。

ＳＳＭの場合、Ｍ　ＩＤはあらゆる場合において空フィールド（ｎｕｌｌ　ｆｉ ｅｌｄ）であり、最初のセグメントと続くいずれのセグメントとともリンクする ことはない。従ッテ、ＶＣＩ　ｌＮ５Ｍ　ＩＤ　ＩＮとＭＣＩ　ＯＵＴをメツセ ージ・リアセングラ／ラベルサーバー５０２に記憶させる必要がなく、メツセー ジ・リアセンブラー／ラベルサーバー５０２はＳＳＭにとって適切な（空（ｎｕ ｌり）Ｍ　ＩＤ　ＯＵＴを出す。従って、ＳＳＭ　ＯＵＴはＢＯＭ　ＯＵＴと同 じマルチプレクシングにより形成され、同じくライン５３６に現れる。

ＣＯＭとＥＯＭは同様にしてデ・マルチプレクサ−５０７によりデマルチプレク スされ、デ・マルチプレクサ−５０７は入ってくるＶＣＩとＭ　ＩＤをライン５ ２４に出し、残りのフィールドをライン５２３に出す、ＶＣＩ　ＩＮとＭ　ＩＤ 　ＩＮはメツセージ・リアセンブラー／ラベルサーバー５０２に入力され、メツ セージ・リアセンブラー／ラベルサーバー５０２はそメツセージのクスされ、マ ルチプレクサ−５１０の出力はセグメントの残りのフィールドであるマルチプレ クサ−５１１内のＣＯＭ　ＲＩＮあるいはＥＯＭ　ＲＩＮでマルチブレクスされ 、マルチプレクサ−５１１は得られたセグメ５に出す。最後に、マルチプレクサ −５１３はライン５切な方を選択する。

デマルチプレクシングとマルチブレクシングは進行段階に沿って第５Ａ図に示さ れている。これは説明のためにだけである。現実の実行においては、デマルチプ レクサ−５０６，５０７，５０８のすべてのデマルチプレクシングは１個のデマ ルチプレクサ−内でもっと効率よく行われ、マルチプレクサ−５０９〜５１３の すべてのマルチブレクシングは１個のマルチプレクサ−内で行われる。また、説 明のためにのみＢＯＭ　ＲＩＮとＳＳＭ　ＲＩＮはＣＯＭ　ＲＩＮとＥＯＭ　Ｒ ＩＮとは別に示されている。現実の実行においては、それらは区別されず共通の ラインに出される。従って、２個の遅延回路５４２．５４３は１個の遅延回路で ある。

遅延回路５４２．５４３．５４４の遅延は出力されたセグメントの異なる要素を 適切に時間的に一致させるのに重要である。遅延回路５４２．５４３が共通でな い場合には１、遅延回路５４２．５４３の遅延は互いに等しくなければならず、 ＶＣＩ　ＯＵＴとＭ　ＩＤ　ＯＵＴを発生させる場合、アドレス／ｖＣＩトラン スレータ５０１とパケット・リアセンブラ・ラベルサーバー５０２の遅延の大き い方と等しくなければならない。

パケット・リアセンブラ・ラベルサーバー５０２に、より大きい遅延が発生した 場合には、遅延回路５４４がトリミング遅延回路としてライン５２８に挿入され てＶＣＩ　ＯＵＴがアドレス／ｖＣＩトランスレータ５０１から出されるのを遅 延させて、メツセージ・リアセンブラ・ラベルサーバー５０２からの遅延に等し くマルチブレクスする。アドレス／ＶＣＩトランスレータ５０１に、より大きい 遅延が発生した場合には、トリミング遅延回路はメツセージ・リアセンブラ会ラ ベルサーバー５０２からのＶＣＩ　ＯＵＴとＭ　ＩＤ　ＯＵＴに適用される。

セグメントは次々と時間間隔なしにルータに入ってくるかもしれず、連続するセ グメントはまったく任意にＢＯＭ、ＳＳＭ、ＣＯＭ、ＥＯＭの４個の型のいずれ の型であるかもしれないので、第５Ａ図のアーキテクチャ−を有するアドレス／ ＶＣ！）ランスレータ５０１とメツセージ・リアセンブラ・ラベルサーバー５０ ２により行われるタスクは１セグメント期間でやり遂げられなければならない。

これは因みに次のことを意味する。即ち、遅延回路５４２．５４３の遅延は最大 の１セグメント期間に限定される、さらに重要なことには、アドレス／ＶＣ！） ランスレータ５０１とメツセージφリアセンブラ・ラベルサーバー５０２はその 限定された時間にそれぞれのタスクを行うことを意味する。

アドレス／ｖＣＩトランスレータの仕事は、トランスレートが簡単なメモリ・ル ックアップによりできる場合に得られる短い時間内になし遂げられる。各送る可 能性のある行き先アドレスに対して適切なＶＣＩをメモリに入れておく。しかし 、現在のところ、アドレススペースの大きさからしてこれは実施できない。行き 先アドレスは６０ビツトであるのに対して、送る可能性のある行き先アドレスの 数は２６０あるいは１０１８であるからである。

アドレス／ＶＣＩ　トランスレートをメモリルックアップで実施可能とする方法 は開発され、同時分割メモリルックアップと呼ばれている。アドレス全体をサブ フィールドに分割し、各サブフィールドを、実施可能の大きさの対応するメモリ にアクセスできように小さいものとする方法である。

第５Ａ図のシステム５０１のブロック線図を示す第５Ｂ図を参照する。ライン５ ２２の行き先アドレスＤＡＤＤＲはライン２１１．２１４１．、、．２１６の（ ｎ＋１）フィールド、フィールド　０、フィールド　１、フィールド　ｎにデマ ルチプレックスされる。これらのフィールドはランダムアクセスメモリ２２Ｌ　 ２２２、。

、、、２２５，２２６へのアドレスとして呈示される。

各メモリから候補ｖ　ｃ　Ｉ　（ｃａｎｄｉｄａｔｅ　ＶＣＴ）が読み出されさ れる。また、各メモリから読み出されるのは論理変数、即ちライン２４３にＩＯ 、ライン２４４に工１１１６１、ライン２４６にＩｎが読み出される。候補ＶＣ Ｉはマルチプレックサ−ＭＵＸ２７０への入力であり、論理装置２５０への論理 変数である。論理装置ライン２６０への総合的に選択し、このＶＣＩがマルチプ レックサ−出力ライン５２８のＶＣＩ　ＯＵＴとなる。

メモリに格納され、メモリから取り出されるＶＣＩと論理変数はアドレスの特定 の分割と、作られた階層領域間の特定の相互接続とに依存する。メモリへの書き 込みのタスクはネットワーク管理装置により行われる。以下に続く説明において 、ＶＣＩの選択は、アドレスの分割（ＰＡＲＴＩＯＮｒＮＧ）が厳密に階層的で あり、更に、その分割が、領域への階層分割に厳密に対応する場合のものである 。次に、論理変数は少なくともあるレベルへのルーチングが指示されているかど うかを指示する１個のバイナリピット２進数字に過ぎず、論理変数の選択は、論 理装置あるいは優先度エンコーダ（ｐｒｉｏｒｉｔｙ　ｅｎｄｏｄｅｒ）　２５ ０による優先度エンコーデング（ｐｒｉｏｒｉｔｙ　ｅｎｅｏｄｊｎｇ）により 実行される。

優先度エンコーデングのタスクは知られており、優先度エンコーダの機能の次の 数学的説明から理解することができる。

Ｉｋ、　ｋ−０，１，、、、ｎを優先度エンコーダへの２進化値入力とし、ＸＩ 、ｊ−０，、、、ｍを優先度エンコーダからの２進化値出力とする。総合的に、 出力は２進化１０進正整数ｙとしてえられ、２進化１０進正整数ｙは ｙの可能な最も大きい値は少なくともｎに等しい。

ｍ　＞　ｌｏｇ２　（ｎ＋１）　（２）の場合に等しくなる。

エンコーダの出力は、 Ｊ＝ｚ　＋１．−−　ｒ　ｎに対して Ｉｚ−１及びＩｊ−０（３） の場合に限り値ｙ＝ｚとなる。

ｎ−７故にｍ−３の場合の優先度エンコーダの真理値表を表１に小す。

ＴＡＢＬＥ　Ｚ 工ＮＰ（ＪＴＳ　０ｔＪＴＰｔＪＴ５　０ｔＪＴＰｔＪＴＡＬＵＥ 工Ｏ”１　”２　Ｉ３　工４　”５　工６　Ｉ７　Ｉ２　”ｌ　”ＯＹｌｏｏｏ ｏｏｏｏｏｏｏｏ ｘｌＯＯＯＯＯＯＯＯｌｌ ＸＸ１００ＯＯＯＯ１０２ ｘｘｘ　１　０００００　１　１３ ｘ　Ｘ　ｘ　ｘ　ｚ　ＯＯＯＩ　Ｏ’　０　４ＸＸＸＸＸ１００１０１５ ＸＸＸＸＸＸＩＯ１１０６ ＸＸＸＸＸＸＸｌｌｌ１７ 優先度エンコーダの実現したものが第８図に示されている。論理変数Ｉｔ〜■７ はライン２９１を介してライン２８５に出される。論理変数の否定（ｎｅｇａｔ 　ｔｏｎ）あるいは逆数（ｉｎｖｅｒｓｅ）は、例えばネゲータ（ｎｅｇａｔｏ ｒ）あるいはインバーター２９２によるＩ２の否定は、図示の異なる組み合わせ でＯＲゲート３００〜３０４に出される。

ＯＲゲートの出力は、ＩＩの一定の組み合わせあるいは否定Ｉ、の一定の組み合 わせと共にＡＮＤゲート３０５゜３０６．３０７に出力され、ＡＮＤゲート３０ ５，３０６．３０７は出力としてＸ。＋ＸｌとＩ２を発生してライン３０８．３ ０９と３１０にそれぞれ出力する。Ｉ。

は優先度エンコーダへの入力ではない。というのは、Ｉ。−１に対応する出力ｘ Ｏ−ＩＯ１ｘ、−〇、ｘ２■０は、！、−Ｉ、がすべでゼロの時デフォルトとし て優先度エンコーダにより発生されるからである。

ラベルの選択は第５Ｂ図のマルチプレクサ−２７０により行われる。第９図は、 ４６ビツトラベルから１個を選択する簡単な場合のマルチプレクサ−を実現した ものを示す。この場合、わずか２つのＸ要素、Ｘｏとｘｌがあるだけである。こ れらはデコーダ４１０に与えられる。

Ｘｏとｘｌの値によって、１個の特定の出力ライン４２１．４２２．４２３．４ ２４が選ばれる。デコーダ４１０の真理値表が表ＩＩに示されている。これらの ラインはトリステートバッフｙ　（Ｔｒｉ−ｓｔａｔｅ　ｂｕｆｆｅｒ）　４４ ０．４４１．４４２．４４３のイネーブル人力に接続される。

トリステートバッファへの人力はそれぞれＶＣＩ　ｔｌ。

ファが選ばれたかにより、そのラベルかそのトリステートバッファの出力に現わ れ、出力バス５２８に出される。

ＴＡＢＬＥ　ＸＸ ＶＡＬｔＪＥ　！ＮＰＵ？　（ｂｉｔｓ）Ｙｘｌ　）Ｃ□　（ｈ　ｂｉｔｓ） ０　０　０　ＬＡＢＥｒ、０ １　０　１　ＬＡＢＥＬＩ ２１　０　ＬＡＢＥＬ２ ３１１ＬＡＢｌ：Ｌ３ 第５Ａ図のメツセージアセンブラ・ラベルサーバー５０２のタスクは１セグメン ト期間より短い期間にやはりなし遂げられなければならず、このようにするには 、やはりメモリルックアップが必要である。メモリルックアップのアドレススペ ースは、３４ビツトのＶＣＩとＭ　ＩＤを一緒にしたものであり、要求されるア ドレスロケーションの数は２Ｘ１０”である。従って、またこれは実用的でない 。

これを可能にするための２段階メモリルックアップが開発されており、その実施 例を第６図を参照して説明すチプレックスされ、それぞれＶＣＩ　ＴＡＧサーバ ー３３１８はバ’：；１．３２２１．：　ｋ　ｌ：’　”／トのＶＣＩ　ＴＡＧ を発生し、バス３２４に１ビツトのＭ　ＩＤ　ＴＡＧを発生させる。これらの２ 個のバスは合わされて（ｋ＋１）ピッこれらの４個のサーバーの必要とされるメ モリサイズは入力ビットの数に指数的に関係し、出力ビットの数に直線的に関係 する。これらの４個のメモリに格納されるビットの合計数は Ｎ＋　−に２”　＋１２″　＋　ｎ２（ｋ＋１１１個のメモリルックアップが使 われるとすると、そのメモリに格納されるビット数は Ｎ２　＝　（ｍ＋ｎ）２（−＋１’　（５）であろう。

（ｋ＋１）が（ｍ　＋　ｎ　）より評価しつる程に小さい数である場合にいはＮ １はＮ２よりも非常に小さい。例えば、ｍが２０に等しく、ｎが１４に等しく、 ｋと１の両者が８に等しいとすると、Ｎ１は約１１．０００．０００であり、一 方、Ｎ２は５ｘ１０”即ち５００．０００．０００．０００をこえる。

第６図のブロック線図の４個のＶＣＩ　ＴＡＧサーバ３１７．３１８．３２５． ３２６はすべて同じ回路であるが、メモリの数値サイズ（ｎｕａ＋ｅｒｉｃａｌ 　５ｉｚｅ）とラインにおいてのみ異なり、このことは第７図で理解できる。

３９６は第６図のＶＣＩ　ＴＡＧ３２２．Ｍ　ＩＤ　ＩＮ　ＴＡＧ３２３．ＶＣ Ｉ　０ＵＴ３２７．Ｍ　ＩＤ０ＵＴ３２８のそれぞれを表す。

第７図を参照する。キー３５０はカウントＲＡＭ３４０へのアドレス選択として バス３５６に与えられ、ラベルＲＡＭ３６５へのアドレス選択としてバス３５５ に与えられる。これにより所定メモリ位置に格納されたデータを読みだしと書き 込むことが可能になる。カウントＲＡＭ３４０からのカウント値３４７はカウン ター３４６内に読み込まれ、ラベルＲＡＭ３６５からのラベル値３８９はタグラ ッチ３９５内に読み込まれる。カウントＲＡＭとラベルＲＡＭへの書き込みと、 カウンター３４６、ラッチ３９５とタグ　Ｆ　Ｉ　Ｆ　Ｏ（ＴＡＧ−ＦＩＦＯ） 　３８０の作動はコントローラ３８５に制御されている。

コントローラ３８５はセグメント型指示即ちバス３９７を受け取る。また、コン トローラ３８５は、ラベルＲＡＭ３６５から読み出されたタグ値をバス３９０で 受取り、カウンター３４６により発生された最新のカウント値をバス３４８で受 け取る。また、コントローラ３８５は、外部で発生されたラベルの入力をバス３ ９９で受ケ取ることもできる。

適切な場合には、コントローラ３８５は次の指令を出す。即ち、 （ｉ）　カウンターＲＡＭ３４０へ書き込み指令をヘライン３４１に、 （ｉ　ｉ）　カウンター３４６へ、ロード指令をライン３４２に、増加指令をラ イン３４３で、減少指令をライン３４４に、消去指令をライン３４５に、（ｉ　 ｉ　ｉ）　タグ　ＦＩＦＯへ、読みだし指令をライン３７０に、書き込み指令を ライン３９１に、タグアウトをバス３７２に、 （ｉｖ）　ラベルＲＡＭ３６５へ、書き込み指令をライン３６０に、すべてゼロ のデータ語をバス３６６に、そして、 （Ｖ）　タグラッチへ、消去指令をライン２７１に、ロード指令をライン３９４ に出す。

適切な場合には、また、コントローラ３８５はバス３８６にエラーコードを、ラ イン３８７に新しい出力指示を出す。

コントローラは、種々の具体的な実施例を有するマイクロプログラムプロセッサ ーでよい。プロセッサーはＥＳＰ４４８か複数個のＥＳＰを並列のカスケード接 続したものからなる。プロセッサーの機能は、次の疑似コード（パスカル言語と Ｃ言語に幾分か似ている）により表されるプログラムを実行することにより果た されることができる。プログラムリストを以下に示す。

ｒｅｐｅａｔ　（ＣＯＮＴＲＯＬ　ＬＯＯＰ）ｒｅｐ＠ａｔ　（ｄｏ　ｎｏｔｈ ｉｎｇ）　ｕｎｔｉｌ　ｎ＠ｗ−１ｎｐｕｔ；　（ＳＹＮＣＨＲＯＮ工ＺＡτ工 ＯＮ　ＯＮ）’　ｃｌｅａｒ　（ｎｅｗ−１ｎｐｕｔ）；　（ＬＩＮＥ　３９８ ）ｌｏａｄ　（ｃｏｕｎｔｅｒ）； ｃａｓｅ　ｓａｇｍｅｎｔ−ｔｙｐｅ　ｏｆＢＯＭ：　ｂｅｇｉｎ ｉｆ（（ｃｏｕｎｔａｒｍｏ）　ａｎｄ　（ｔａｇ＠０））ｒｅａｄ（ｔａｇ− ｆｉ、ｆｏ、ｄａｔａ）；ｗｒｉｔ＠（ｌａｂｅｌ−ｒａｍ、　ｄａｔａ　）　 ；ｉｎｃｒｅｍａｎｔ（ｃｏｕｎｔａｒ）；Ｗｒｉ　ｔ＠　（ＣＯｕｎｔａｒ− ｒａｍ　、　Ｃｏｕｎｔｅｒ　）　；１ｏａｄ　（ｔａｇ−１ａｔｃｈ　） ａｎｄ ＠ｌｓｅ　１ｆ（（ｃｏｕｎｔ＠ｒ００）　ａｎｄ　（ｔａｇ＜＞０））１、ｎ ｃｒａｍａｎｔ（ｃｏｕｎｔａｒ）；ｗｒｉぞ＊　（ｃｏｕｎｔａｒ−ｒａｍ、 ｃｏｕｎｔａｒ　）ｒｌｏａｄ　（ｔａｇ−１ａｔｃｈ　）　：ａｎｄ ｅｌｓ＠ｂｅｇｉｎ ＠ｒｒｏｒ　ｃｏｄ＠：ｍｌ； ｃｌｅａｒ（ｔａｇ−１ａｔｃｈ　）　；仰ｄ； ｅｎｄ； ＣＯＭ：　ｂｅｇｉｎ ｉｆ（（ｃｏｕｎｔ＠ｒ００）　ａｎｄ　（ｔａｇｃ＞０））ｔｈｅｎ　ｂｅｇ ｉｎ ａｒｒｏｒ　ｃｏｄｅ：ｓｏ； １ｏａｄ（ｔａｇ−１ａｔｃｈ）； ａｎｄ ａｌｓｅ　ｂａｇｉｎ ｅｒｒｏｒ　ｃロｄｅニー２； ｃｌｅａｒ（ｔａｇ−１ａｔｃｈ）；　’ａｎｄ； ａｎｄ； ＥＯＭ：　ｂｅｇｉｎ ｌｆ（（ｃｏｕｎｔｅｒｃ＞Ｏ）　ａｎｄ　（ｔａｇ＜）Ｏ））ｔｈａｎ　ｂ＠ ｇ組 １ｏａｄ（ｔａｇ−１ａｔｃｈ　）； ｄａｃｒ＠ｍａｎｔ（ｃｏｕｎｔｅｒ）；ｗｒｉ　ｔ＠（ｃｏｕｎｔａｒ−ｒａ ｍ　、　ｃｏｕｎｔ＠ｒ　）　；１ｆ（ｃｏｕｎｔａｒ−０） ｔｈｅｎ　ｂｅｇｉｎ ｗｒｉｔｅ（ｔａｇ−ｆｉｆｏ、　ｔａｇ　）　；ｗｒｉｔｅ（ｌａｂａｉ−ｒ ａｍ、Ｏ）；ａｒｒｏｒ　ｃｏｄｅ：ｓｏ； 観ｄ； ａｎｄ ｃｌｅａｒ（ｔａｇ−１ａｔｃｈ　）；ａｎｄ＝ ａｎｄ；　（ＥＮＤ　−ＯＦ　ＣＡＳＥ）ｐｕｌｓｅ（ｎｅｗ−ｏｕｔｐｕｔ） ；ｕｎｔｉｌ　ｆｏｒｅｖｅｒ； プログラムの流れ図は第１０Ａ〜１０Ｄ図に示されている。

タグサーバー（ｔａｇ　５ｅｒｖｅｒ）の作動と、タグサーバーのコントローラ ３８５の作動はＶＣＩタグサーバー、即ち第６図のサーバー３１７の場合につい て第７図を参照するとより詳しく説明されるであろう。この場合、バス３５５と ３５６に現われるキー３５０は現在のセグメントのヘッダーに携行されて入って きたＶＣＩである。セグメントがＣＯＭ（メツセージの続き）である場合には、 ラベルＲＡＭ３６５から読み出されるラベルは非零（ｎ。

ｎ−ｚｅｒｏ）であり、そのセグメントのために前もって格納されている。カウ ントＲＡＭ３４０のカウント読みだしも非零である。コントローラは読み出され たラベルとカウントが非零かどうかを調べる。どちらか、あるいは両者が零の場 合は、エラー状態を意味し、コントローラはエラーコードをバス３，８６に発生 させてそのエラー状態セグメントがＢＯＭ（メツセージの始まり）である場合は 、そのセグメントのＶＣＩ　ＴＡＧはある場合もあるしない場合もある。ある場 合には、読み出されるカウントとラベルは非零である。この場合、コントローラ はＶＣＩ　ＴＡＧをタグラッチ３９５内に前のようにラッチする。また、コント ローラはインクリメントコマンドをライン３４３に出し、このインクリメントコ マンドは、カウンター３４６のカウントを１だけインクリメントする。これに続 いて、コントローラは書き込み指令をライン３４１に出して最新のカウントを ブチ３９５内にラッチされる。カウントもインクリメントされて１になり、カウ ント　ＲＡＭ３４０内に前のように書き込まれる。

ＲＯＭか到着し、タグを与える必要がある時にＴＡＧ　ＦＩＦＯ３８０が万一に 空の場合、タグは与えられない。これはエラーであり、そのメツセージが失われ る結果となる。ＴＡＧスペースの数値サイズは、タグが無くなる可能性が無視で きる確率となるように選択されることができる。

最後に、セグメントがＥＯＭ（メツセージの終わり）の際には、ラベル−ＲＡＭ ３６５を読む場合の条件と作動はＣＯＭの場合と同じである。しかし、タグが自 由となりプールに戻される可能性がある。コントローラはデクリメントコマンド をカウンター３４６ヘライン３４４に出す。これにより、カウントは１だけデク リメントされ、最新のカウントがカウント　ＲＡＭ３４０に書き込まれる。得ら れたカウントが零の場合、タグは自由となる。タグはタグ　ラッチ３９５内にラ ッチされ、また、ライン３９１の書き込み指令により ＴＡＧ　ＦＩＦＯ３８０にも書き込まれる。これに続いて、すべて零のタグがコ ントローラによりバス３６６に出され、ライン３６０の書き込み指令によりバー ３２６は他の２個のサーバーとは次の点で異なる。

た数により限定されるのであってスペースのサイズにより限定されるのではない 点である。ラベルは、外部の送り手からバス３９９のラベルを経由し、バス３７ ２を経キーは特定のデータグラムのためのものであり、カウントは、ＲＯＭに続 く特定のキーのためのものであり、ＥＯＭに続いて零に戻る。この様に、カウン ト　ＲＡＭ３４０の機能はニル（ｎｉｌ）であり、この場合には無くてもよい。

ＶＣＩ　ＯＵＴサーバーはＭ　ＩＤ　ＯＵＴサーバーと次の点においてのみ異な る。即ち、 ＢＯＭが入った際に第５図のシステムにより決定される。

ＥＯＭが到着した際に、ＶＣＩのアドレス位置は再びバス３６６を経由して零に される。

型Ｉ、ＩＩ、　Ｈの３つの型のルータが説明されてきたが、包括的な実施例が可 能であることが認められるであろう。

コントローラ内の実行可能のプログラムを適切に変更するすることにより包括的 なルータをある型から別の型に変更可能である。

第１図の全体的な装置の要素を変更しても同じ機能を達成されることも認められ るであろう。コネクシジンレス零レベル領域は、端末装置をルータ−に直接に接 続する、即ち、各別個の端末装置に対して１対のルータを接続することにより無 くすことができることは既に述べたが、このようにするには、実質的により多く のルータ−を必要とする点で好ましくない。零レベル領域は集信装置として働き 、１ルータ−が多数の端末装置にサービスできるようにすると共に、領域内通信 のためのコネクションレス交換サービスを提供する。

すべてのコネクションレスメセージが１個のルータ−に送られる場合、集信機能 は別個の端末装置からの単純化かされたルーチング機能を有するコネクション指 向領域により果たされることもできる。その際、ルータ−は中央コネクションレ スサーバーに近似する。

コネクション指向型コンセントレータ自身は、コネクションレス領域内通信をな んら提供しないため、コネクションレス領域内通信を提供するようにルータの機 能性はそれなりに拡大されなければ成らない。

ネットワーク基準の特定の文脈と、その文脈の範囲内の本発明の具体的な実施例 がここに示され、記載されているが、これは単に説明のためにだけである。当業 者であれば。ここに具体的に示されていない、あるいは記載されていないが、前 述の原理を実施し前述の原理の精神と範囲から逸脱することのない他のシステム を工夫することができるであろう。例えば、上述のシステムは、データグラムの セグメント転送に係わるものであるが、幾つかの要素を使わなければ、セグメン トしない転送にも、適用できるものである。また、例えば、ランダムアクセスメ モリ、マルチプレククサー、優先度エンコーダ。

ＦＩＦＯメモリ等が以上記載されているが、これらはより基本的な、あるいは同 様の機能を果たす特別に構成された要素に置き換えられることができる。

第ら記 特表千４−５０４４８９　（１７） 国際調査報告 Ｕむ０ＦＡＩ豐こＸ

Claims (1)

1. 【特許請求の範囲】 １．少なくとも１個のセグメントを有するデータグラムをルーチングするネット ワークにおいて、ネットワークは、少なくとも１個のセグメントスイッチングシ ステム（１０１，．．．，１０４）と、このセグメントスイッチングシステム（ １０１，．．．，１０４）と複数個の端末（９１，．．．，９８）との間に接続 された複数個のルーター（１１１，．．．，１３０）であって、第１端末（９１ ）から発信されたデータグラムのデータを処理して、このデータグラムを第１ル ーター（１１１）から第２ルーター（１１８）へ前記セグメントスイッチングシ ステム（１０１，．．．，１０４）を経由して通し、このデータグラムを前記第 ２ルーター（１１８）から第２端末（９６）へ通す複数個のルーター（１１１． ．．，１３０）とを備えたネットワーク。 ２．各階層セグメント転送レベルに対応するように複数個のセグメントスイッチ ングシステム（１０１，．．．，１０４）は前記ルーターにより接続され、第１ レベルのセグメントスイッチングシステム（１０１，１０２）は前記端末と、第 ２レベルのセグメントスイッチングシステム（１０３）に接続され、前記第２レ ベルのセグメントスイッチングシステム（１０３）は前記第１レベル、の少なく とも２個のセグメントスイッチングシステム（１０１，１０２）に接続されてい る請求項１記載のネットワーク。 ３．前記第１レベルの１個のセグメントスイッチングシステム１０１は前記第１ レベルのもう１個のセグメントスイッチングシステムに接続されている請求項２ 記載のネットワーク。 ４．前記セグメントスイッチングシステム（１０１，１０３）は、より高いセグ メント転送レベルのセグメントスイッチングシステム（１０３，１０４）に、最 も高いセグメント転送レベルのセグメントスイッチングシステム（１０４）を除 いてすべてが接続されている請求項３記載のネットワーク。 ５．データグラムは、その最終行き先のアドレスにもとずいて前記ネットワーク を通して転送される前記請求項いずれかに記載のネットワーク。 ６．前記端末は、前記ルーター（１１１，．．．，１３０）により前記セグメン トスイッチングシステム（１０１，．．．，１０４）に接続された少なくとも１ 個のエーリアネットワーク手段（８１，．．．，８５）により接続されて少なく とも１グループとされている前記請求項いずれかに記載のネットワーク。 ７．前記ルーター（１１１，．．．，１３０）は、前記データグラムを受けとり 、前記データグラムから前記最終行き先のアドレスをアクセスする第１手段（５ ０３，５０４，５０５，５０６，５０７，５４１）と、 前記第１手段に応答して、前記最終行き先のアドレスにもとずいて出力コネクシ ョンデータ（ＶＣＩ ＯＵＴ）を決定する第２手段（５０１）と、前記出力コネ クションデータ（ＶＣＩ ＯＵＴ）を前記データグラムに含める第３手段（５０ ２，５０５，５０８，５０９，５１１，５１２，５１３，５４０，５４２，５４ ４，５４３）とを備え、 前記データグラムは、前記ルータから出力されたのち前記出力コネクションデー タ（ＶＣＩ ＯＵＴ）にもとずいて前記ネットワークにルートされる請求項５記 載のネットワーク。 ８．前記第２手段（５０１）は、 出力コネクションデータ（ＶＣＩ ＯＵＴ）と選択データが格納されたメモリ回 路（２２１，．．．，２２６）と、 前記最終行き先のアドレスをフィールドに分け、これらのフィールドを前記メモ リ回路（２２１，．．．，２２６）のそれぞれに与えて複数個の対応するコネク ションデータと選択データにアクセスする第４手段（２０１）と、 前記選択データにもとずいて前記複数個の対応するコネクションデータから出力 コネクションデータ（ＶＣＩ−〇ＵＴ）を選択する第５手段とを備える請求項７ 記載のネットワーク。９．前記階層セグメント転送レベルに対応する優先度にも とずいて前記選択データが選択されるように前記選択データが優先度コードに対 応する請求項８記載のネットワーク。 １０．前記第３手段（５０２，５０５，５０８，５０９，５１１，５１２，５１ ３，５４０，５４２，５４４，５４３）は、前記第１手段（５０３，５０４，５ ０５，５０６，５０７，５４１）により前記少なくとも１個のセグメントからア クセスされた入力コネクションデータ（ＶＣＩ−ＩＮ）と入力メッセージデータ （ＭＩＤ−ＩＮ）にもとずいて前記データグラムの前記少なくとも１個のセグメ ントに対する出力メッセージデータ（ＭＩＤ−ＯＵＴ）を決定するメッセージ手 段（５０２）を備え、 前記第３手段（５０２、５０５、５０８、５０９、５１１、５１２、５１３、５ ４０、５４２、５４４、５４３）は前記少なくとも１個のセグメント内の前記出 力メッセージデータ（ＭＩＤ−ＯＵＴ）を有し、前記少なくとも１個のセグメン トが前記データグラムに属することを、前記出力メッセージデータ（ＭＩＤ−Ｏ ＵＴ）が前記ルーターからの出力の際に、指示する請求項７、８および９のいず れかに記載のネットワーク。 １１．データグラムの第１セグメントが前記ルーターにより処理されたのち前記 データグラムの続くセグメントに対する前記出力コネクションデータ（ＶＣＩ ＯＵＴ）を更に決定し、前記出力コネクションデータ（ＶＣＩ ＯＵＴ）は前 記入力コネクションデータ（ＶＣＩ−ＩＮ）と前記入力メッセージデータ（Ｍ− ＩＤ−ＩＮ）にもとずいて決定され、前記第３手段は（５０２，５０５，５０８ ，５０９，５１１，５１２，５１３，５４０，５４２，５４４，５４３）は前記 続くセグメント内の前記出力コネクションデータ（ＶＣＩ ＯＵＴ）を有する請 求項１０記載のネットワーク。 １２．前記メッセージ手段（５０２）は少なくとも２個のタグサービング手段（ ３１７，３１８）を備え、これらのタグサービング手段はそれぞれ前記入力コネ クションデータ（ＶＣＩ−ＩＮ）と前記入力メッセージデータ（Ｍ−ＩＤ−ＩＮ ）によりアクセスされて、それぞれコネクションタグとメッセージタグを出力し 、前記出力コネクションデータ（ＶＣＩ ＯＵＴ）は前記タグにもとずいて決定 される請求項１１記載のネットワーク。 １３．前記コネクションタグと前記メッセージタグに応答して、前記出力コネク ションデータ（ＶＣＩ ＯＵＴ）と前記出力メッセージデータ（Ｍ−ＩＤ−ＯＵ Ｔ）とを出力するタグサービング手段を更に備え、前記３個のタグサービング手 段（３１７，３１８，３２５，３２６）は、 可用タグを格納する可用タグ記憶手段（３８０）と、データグラムに対する現在 のタグを格納するメモリー（３６５）と、前記現在のタグがもはや必要でなくな る時を決定して、前記現在のタグを前記タグ記憶手段に返す手段（３４０，３４ ６，３８５）とを備える請求項１２記載のネットワーク。 １４．前記ルータは実時間で前記データグラムを処理する、前記請求項のいずれ かに記載のネットワーク。 １５．少なくとも１個のセグメントを有するデータグラムをルーチングするネッ トワークのルータにおいて、前記ルータは、 データグラムを受けとり、このデータグラムから最終行き先のアドレスをアクセ スする第１手段（５０３，５０４，５０５，５０６，５０７，５４１）と、前記 第１手段に応答して、前記最終行き先のアドレスにもとずいて出力コネクション データ（ＶＣＩ ＯＵＴ）を決定する第２手段（５０１）と、前記出力コネクシ ョンデータ（ＶＣＩ ＯＵＴ）を前記データグラムに含める第３手段（５０２， ５０５，５０８，５０９，５１１，５１２，５１３，５４０，５４２，５４４， ５４３）とを備え、 前記データグラムは、前記ルータから出力されたのち前記出力コネクションデー タ（ＶＣＩ ＯＵＴ）にもとずいて前記ネットワークにルートされるルータ。 １６．前記第２手段（５０１）は、 出力コネクションデータ（ＶＣＩ　ＯＵＴ）と選択データが格納されたメモリ回 路（２２１，．．．，２２６）と， 前記最終行き先のアドレスをフィールドに分け、これらのフィールドを前記メモ リ回路（２２１，．，．．２２６）のそれぞれに与えて複数個の対応するコネク ションデータと選択データにアクセスする第４手段（２０１）と、 前記選択データにもとずいて前記複数個の対応するコネクションデータから出力 コネクションデータ（ＶＣＩ　ＯＵＴ）を選択する第５手段とを備える請求項第 １５記載のルータ。 １７．前記階層セグメント転送レベルに対応する優先度にもとずいて前記選択デ ータが選択されるように前記選択データが優先度コードに対応する請求項１６記 載のネットワーク。 １８．前記第３手段（５０２，５０５，５０８，５０９，５１１，５１２，５１ ３，５４０，５４２，５４４，５４３）は、前記第１手段（５０３，５０４，５ ０５，５０６，５０７，５４１）により前記少なくとも１個のセグメントからア クセスされた入力コネクションデータ（ＶＣＩ　ＩＮ）と入力メッセージデータ （Ｍ　ＩＤ　ＩＮ）にもとずいて前記データグラムの前記少なくとも１個のセグ メントに対する出力メッセージデータ（Ｍ　ＩＤ　ＯＵＴ）を決定するメッセー ジ手段（５０２）を備え、 前記第３手段（５０２、５０５、５０８、５０９、５１１、５１２、５１３、５ ４０、５４２、５４４、５４３）は、前記少なくとも１個のセグメントが前記ル ーターからの出力の際に前記データグラムに属することを指示する前記出力メッ セージデータ （Ｍ　ＩＤ　ＯＵＴ）を有する請求項１５、１６、および１７のいずれかに記載 のルータ。 １９．データグラムの第１セグメントが前記ルーターにより処理されたのち前記 データグラムの続くセグメントに対する前記出力コネクションデータ（ＶＣＩ　 ＯＵＴ）を更に決定し、前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）は前記 入力コネクションデータ（ＶＣＩ　ＩＮ）と前記入力メッセージデータ（ＭＩＤ 　ＩＮ）にもとずいて決定され、前記第３手段は（５０２，５０５，５０８，５ ０９，５１１，５１２，５１３，５４０，５４２，５４４，５４３）は前記続く セグメント内の前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）を有する請求項 １８記載のルーター。 ２０．前記メッセージ手段（５０２）は少なくとも２個のタグサービング手段（ ３１７，３１８）を備え、これらのタグサービング手段はそれぞれ前記入力コネ クションデータ（ＶＣＩ　ＩＮ）と前記入力メッセージデータ（Ｍ　ＩＤ　ＩＮ ）によりアクセスされて、それぞれコネクションタグとメッセージタグを出力し 、前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）は前記タグにもとずいて決定 される請求項第１９記載のネットワーク。 ２１．前記コネクションタグと前記メッセージタグに応答して、前記出力コネク ションデータ（ＶＣＩ　ＯＵＴ）と前記出力メッセージデータ（Ｍ　ＩＤ　ＯＵ Ｔ）とを出力するタグサービング手段を更に備え、前記３個のタグサービング手 段（３１７，３１８，３２５，３２６）は、 可用タグを格納する可用タグ記憶手段（３８０）と、データグラムに対する現在 のタグを格納するメモリー（３６５）と、前記現在のタグがもはや必要でなくな る時を決定して、前記現在のタグを前記タグ記憶手段に返す手段（３４０，３４ ６，３８５）とを備える請求項２０記載のネットワーク。 ２２．前記ルータは実時間で前記データグラムを処理する、前記特許請求項１５ 乃至２１のいずれかに記載のネットワーク。 ２３．少なくとも１個のセグメントスイッチングシステム（１０１，．．．，１ ０４）と、このセグメントスイッチングシステム（１０１，．．．，１０４）と 複数個の端末（９１，．．．，９８）との間にコネクションされた複数個のルー ター（１１１，．．．，１３０）とを有するネットワーク内でデータグラムをル ーチングする方法において、第１端末（９１）から発信されたデータグラムのデ ータを処理して前記データグラムを第１ルータ（１１１）から第２ルータ（１１ ８）へ前記セグメントスイッチングシステム（１０１，．．．，１０４）を経由 して通し、前記データグラムを前記第２ルータ（１１８）から第２端末へ通すこ とからなるデータグラムをルーチングする方法。 ２４．データグラムの最終行き先のアドレスにもとずいて前記データグラムを前 記ネットワークを通して転送することからなる請求項２３記載のデータグラムル ーチング方法。 ２５．前記データグラムから前記最終行き先のアドレスをアクセスすることと、 前記最終行き先のアドレスにもとずいて出力コネクションデータ（ＶＣＩ　ＯＵ Ｔ）を決定することと、前記データグラムに前記出力コネクションデータ（ＶＣ Ｉ　ＯＵＴ）を含めることと、前記データグラムが前記ルータから出力されたあ とに前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）にもとずいて前記ネットワ ーク内で前記データグラムをルチングすることから更になる請求項２４記載のデ ータグラムをルーチングする方法。 ２６．前記最終行き先のアドレスをフィールド毎に分けることと、これらのフィ ールドを、コネクションデータと選択データとを格納しているそれぞれのメモリ 回路に与えて複数個の対応するコネクションデータと選択データをアクセスする ことと、前記選択データにもとずいて前記複数個のコネクションデータから出力 コネクションデータを選択することから更になる請求項２５記載のデータグラム をルーチングする方法。 ２７．前記コネクションデータが階層セグメント転送レベルに対応する優先度に もとずいて選択されるように前記選択データは優先度コードに対応し、階層セグ メント転送レベルは、前記ルータ（１１１，．．．，１３０）により接続された それぞれのセグメントスイッチングシステム （１０１，．．．，１０４）を備える請求項２５及び２６のいずれかに記載のデ ータグラムをルーチングする方法。 ２８．前記少なくとも１個のセグメントから入力コネクションデータ（ＶＣＩ　 ＩＮ）と入力メッセージデータ（Ｍ　ＩＤ　ＩＮ）にアクセスすることと、前記 入力コネクションデータ（ＶＣＩ　ＩＮ）と前記入力メッセージデータ（Ｍ　Ｉ Ｄ　ＩＮ）にもとずいて出力メッセージデータ（Ｍ　ＩＤ　ＯＵＴ）を決定する ことと、前記出力メッセージデータ（Ｍ　ＩＤ　ＯＵＴ）を前記少なくとも１個 のセグメントに含ませることから更になり、前記少なくとも１個のセグメントが 前記データグラムに属することを、前記出力メッセージデータ（Ｍ　ＩＤ　ＯＵ Ｔ）が前記ルーターからの出力の際に指示する請求項２５、２６及び２７のいず れかに記載のデータグラムをルーチングする方法。 ２９．データグラムの第１セグメントの処理のあと、前記入力コネクションデー タ（ＶＣＩ　１Ｎ）と前記入力メッセージデータ（Ｍ　ＩＤ　ＩＮ）にもとずい て前記データグラムの続くセグメントに対する前記出力コネクションデータ（Ｖ ＣＩ　ＯＵＴ）を決定することと、前記出力コネクションデータを前記焼くセグ メントに含ませることから更になる請求項２８記載のデータグラムをルーチング する方法。 ３０．前記入力コネクションデータ（ＶＣＩ　ＩＮ）と前記入力メッセージデー タ（Ｍ　ＩＤ　ＩＮ）にそれぞれもとずいてタグサービング手段（３１７，３１ ８）からコネクションタグとメッセージタグとをアクセスすることと、前記コネ クションタグと前記メッセージタグとにもとずいて前記出力メッセージ（Ｍ　Ｉ Ｄ　ＯＵＴ）と前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）とを決定するこ とから更になる請求項２９記載のデータグラムをルーチングする方法。 ３１．前記コネクションタグと前記メッセージタグとにもとずいて更に備えられ たタグザービング手段（３２５，３２６）から前記前記出力メッセージ（Ｍ　Ｉ Ｄ　ＯＵＴ）と前記出力コネクションデータ（ＶＣＩ　ＯＵＴ）とを得ることか ら更になり、前記タグサービング手段（３１７、３１８、３２５、３２６）にお いて、可用タグはタグ記憶手段に格納され、データグラムに対する現在のタグは メモリに記憶され、前記データグラムが前記ルータを通過した際に前記現在のタ グは前記タグ記憶手段に戻される請求項３０記載のデータグラムをルーチングす る方法。 ３２．データグラムをルーチングする方法の工程は実時間で行われる請求項２３ 乃至３２のいずれかに記載のデータグラム をルーチングする方法。