JPS63500764A - 優先ランダム分割及び競合検出を備えたパケット交換ロ−カル回路綱 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 優先ランダム分割及び競合検出を備えたパケット交換ローカル回！？８網 〔技術分野〕 この発明はローカル通信分野に関し、特に多重アクセス放送チャネル形式のパケ ット交換通信回路網に関する。

〔従来の技術〕

パケット交換通信回路網は、同軸ケーブル、ファイバー・オプティック・り゛− プル又はラジオ・チャネルのような共有する通信チャネルを介して通信端末装置 間でデータを転送するために広く用いられている。このような通信回線網はコン ピュータ間でディジタル・データを伝送するため、また事務所環境におけるワー ドプロセッサ、プリンタ、ドキュメント・スキャナー及びテレファックス装置の ようなオフィス装置を結合するために用いられている。

このような通信回線網を横築する際の妥協点には、効率、伝送遅延、経済性及び 信頼性がある。一般に、通信チャネルそれ自体は資源を充分に備えてはいないの で、通信回Ｇ！網は通信チャネルを最大効率で利用するように動作しなければな らない。システムは、信頼性を達成するために、システムの一部の故障が通信回 線網の全体をシャット・ダウンさせてしまわないように設計されていなければな らない。

これらの要求の多くを満足させるために見出されたデータ通信回線網の１形式に は、ＣＳＭ＾／ＣＤ（Ｃａｒｒｉｅｒ　５ｅｎｓｅ　ＭｕｌｔｉｐｌｅＡｃｃｅ ｓｓ　ｗｉｔｈ　Ｃｏｎｆｌｉｃｔ　Ｄｅｔｅｃｔｉｏｎ）がある、　ＣＳＭ＾ ／ＣＤのうちで商業的に成功した例には、ゼロックス社（Ｘｅｒｏｘ　Ｃｏｒｐ ｏｒａｔｉｏｎ）により開発されたＥＴＨＥＲＮＥＴがある（メトカルフェ他に 対し、１９７７年１２月１３日に発行された米国特許第４，０６３，２２０号を 参照されたい）。

ＣＳＭ＾／ＣＤ回線網では、通信チャネルは複数の端末装置により共有される。

この形式の回報通信多重アクセス回線網では、通信チャネルに対するアクセスを 制御するために中実装置を設けていない。端末装置は共有チャネルを介して他の 端末装置にデータ・パケットを送信し、送信に関する判断は各端末装置が通信チ ャネルのトラフィックを独立して観測することにより行なわれる。各データ・パ ケットは目的のレシーバのアドレスを含み、回線網の全ての端末装置により受信 される。中央制御装置を設けていないので、一つの故障がシステム全体を不能に する可能性は少なく、これによってシステムの信頼性を最大にしている。ＣＳＭ ＾／ＣＤシステムでは、通信チャネルを介してパケットの送信についてレディー となっている端末装置が、先ず通信チャネルを調べて（搬送波を検知し）、他の 通信チャネルが送信しているか否かを判断する。レディーの端末装置は、通信チ ャネルがビジーのときは、チャネルが空きとなるまで待機する。端末装置は、通 信チャネルが空きのときに（搬送波が検知されないときに）、パケットの送信を 開始する。　ＣＳＭ＾／ＣＤシステムでは、２以上の端末装置が同時に送信する ことがある。この結果、衝突が発生する。各端末装置はこのような衝突を原因と する競合を検出する（競合検出）機能を有する。競合が検出されたときは、全て の端末装置が送信を停止し、競合を解決するルーチンを実行する。　ＥＴＨＥＲ ＮＥＴシステムの場合に、このルーチンは、各送信をしようとする前に端末装置 にランダムな期間の遅延をさせるものである。

ＥＴＩＩＥＲＮＥＴのようなデータ通信システムは、急激に増加するに伴い、全 て同一の長さを有する従来のデータ・パケットばがっでなく、長さが種々異なる パケットを送信する要求も発生した。

統合されたこの形式の通信に対する要求の一例として、共通のデータ通信回線ｗ ４ｐ介して通常のデータ・メツセージと共に高品質のイメージ情報を送信する要 求がある。このような要求の特定例には、病院内、病院間又は診療所間のローカ ル・ネットワークを介して思考のデータ及びＸ線のイメージを送信することと、 電子印刷環境におけるテキスト及び高品質の写真イメージを送信することが含ま れている。他の例には、限定的な音声パケッＩ・の遅延を許容する通信回線網を 介して音声情報及び通常データを通信するものがある。このような総合通信回線 網ではチャネル・トラフィックが比較的短いパケットと２比較的長い（例えば、 １桁以上長い）パケットからなる。データ・パケットは、音声パケットより通常 １０〜１００倍長く、同様にイメージ・パケットはデータ・パケットより通常１ ０〜１００倍長い、イメージ全体は１データ・パケットより通常３〜４桁長いが 、１イメージは１００以上に分割可能なので、イメージ・パケットはデータ・パ ケットより１〜２桁長いに過ぎない。

単純な設計では、送信すべきパケットの長さをそれぞれ処理可能な独立チャネル を備える。しかし、このような多重チャネル・システムは非常に費用が掛かる。

従って、単独チャネルが混合したパケット長を効率よく処理できることが好まし い。

この解決方法での問題は、ローカル環境において公知のＣＳＮ＾／ＣＤシステム が通信チャネルを高速にアクセスし、効率的に利用するものであっても、このＣ ＳＭ＾／ＣＤシステムに安定性がないことである。即ち、システム能力を瞬時的 に超える短い時間で重いトラフィックとなったときは、システムが回復不能の飽 和状態にロック・アップしてしまう、この状態では、総合チャネル能力が競合を 解決するための処理に費やされてしまい、首尾よく送信を行なうことができない ０例えば、イメージ・パケットは極端に重いトラフィックとして振る舞うので、 統合されたデータ／イメージ回線網に不安定性の問題が発生する。

ランダム分割処理又はツリー法と呼ばれる技術に関連するパケット交換データ通 信システムが提案された。ランダム分割処理又はツリー法は、重トラフィックの バーストが存在するときに安定であると数学的に証明された。ジョン■、カベタ ナキス（Ｊｏｈｎ　Ｉ　、　Ｃａｐｅｔａｎａｋｉｓ）による［パケット同報通 信チャネルノツリー・フルボリズム」、ＩＥＥＥ　ＴＲＡＮＳＡＣＴｆＯＮ　Ｏ Ｎ　ＩＮＦＯＭＡＴＩＯＮＴＨＥＯＲＹ　ＶＯＬ、ＩＴ−２５，Ｎｏ、５．１９ ７９年９月を参照されたい。

基本的なランダム分割又はツリー法はスロット・チャネル用に設計されたもので あった。各スロットの長さはデータ・パケットの長さに等しい、チャネルのユー ザは、それぞれ活性のチャネル・フィードバックと呼ばれる過去のチャネル送信 の総合的な結果について独立した観察により、その送信又は再送信を決定するこ とが必要である。固有のフィードバックには３値ある。

即ち、ユーザは、過去の送信が空き、成功、又は競合であったことを判別するこ とができる。ユーザはスロットの境界で判断を行なう、このようにして、通信シ ステムは２つのモード、即ち通常モードと競合モードとの間を交番する。競合が 発生すると、全ての送信器は競合解決モードになり、新たに到達したものは全て 次の通常モードへの遷移まで待機され、衝突に関連した全てのパケットは同じよ うな確率により２つのサブセットのうちの一つを独立して選択する。各サブセッ トは、根を持つ２進数のツリーの根元からの分岐に対応するものと見ることがで きる。Ｓ突に続くスロットでは、これらの第１のサブセットを送信する。他の衝 突が発生すると、このサブセットは更に２つのサブセットに分割され、元の分岐 から成長する分岐に更に対応させている。これらのサブセットのうちの第１のも のは次のスロットによって送信され、この送信が成功したときは、又は空きであ ったときは、サプセッ１〜のうちの第２のらのを次のスロットにより送信する０ 通常、サブセットの送信が衝突になったときは、このサブセットは分割され、ツ リーの新しい２つの分岐は古い分岐から成長する。サブセットの送イ３が空き又 は首尾よくであったときは（即ち、スロットが空であるときは、又はｌパケット を含むときは）１次のスロットを用いて次のサブセットを送信する。全てのサブ セットが尽きたときは、再び通常モードに入る。

理論的には、ランダム分割又はツリー法は絶対的に安定であることが示された。

これは、０．３４７バゲツト／スロツトの最大スループット速度を達成すること ができる。しかし、これがローカル・エリア・ネットワークに適用されたときは 、この速度は低過ぎるものと思われる。更に、通信回線網にランダム分割又はツ リー法をどのように分散して実行できるのがは示されていない。

従って、この発明の目的は、改良されたチャネル・スループットによってランダ ム分割又はツリー法を実行する安定した分散制御通信システムを提供することに ある。

〔発明の開示〕

要約すると、この発明の目的は搬送波検知及び競合検出手段を有する多重アクセ ス通信チャネル及び通信端末装置を提供することにより達成される。集中化され ず、分散されたチャネル制御は統合したトラフィック用に競合解決及び優先度送 信ｉｎを用いることにより達成される。搬送波検知及び競合検出は２０−カル環 境にあるチャネルへの高速アクセスと可能にする。

ランダム分割処理は分散制御により絶対的に安定な処理を提供するものであり、 優先度送信は短いデータ・パケットに長いデータ・パケットより凡い送信遅延号 補償する。

更に具体的には、この発明の目的は１つの通信チャネル及び複数の通信端末装置 を有する回線網を形成することにより達成される。各端末装置は情報パケットご 送受信し、かつチャネルを監視して搬送波の存在又はパケット間の衝突するトラ ンシーバと、分散方法によりパケ・ノドの送信又は再送信を編成する通信制御装 置と、情報バケッＩ−含発生し、かつ蓄積するワーク・ステーションとを備えて いる。２形式のチャオ・ル・トラフィック、即ち短パケット及び長パケットがあ る０通信制御装置はトランシーバから搬送波検知信号及び競合検出信号を受取り 、チャネルが空きか、連続する短パケツト送信によりビジーであるか、又はパケ ット間の衝突によりビジーであるかを判断する。

パケットの送信はセツション及びサイクルに編成される。１セツシヨンは前のセ ツション中に到達した全ての短パケットを送信するために必要な時間、又は前の セツション中に到達したパケットがないときに前のセツション中に到達した長パ ケットのうちの一つを送信するために必要な期間と定義される。１セツンが送信 されたときは長セツションと呼ばれ、前のセツションの終了後に直ちに送信され たパケットがなかったときは、空きセツションと呼ばれる。

サイクルは、前のサイクル中に到達した全ての長バッツＩ−を首尾よく送信する ために必要な期間として定義される。前のサイクル中に長パケットを送信する準 備ができていないときは、現在サイクルが空きセツションで終る。従って、サイ クルは、空きセツション、空きセツションが続く多数の短セツション、１つの長 セツション、又は複数の長短のセツションである。

セツション中に到達する短セツションは、ランダム分割処理を用いることにより 、次のセツション中に首尾よく全て送信され、送信競合を解決する。同様に、あ るサイクル中に到達する長セツションは、ランダム分割処理を用いることにより 次のサイクルで首尾よく全て送信される。各サイクルにおいて、長セツションは 前のセツションで短バケツ？−が到達しなかったときにのみ開始される。長セツ ションでは、１つの長パケットのみが送信され、他は次の長セッションオで保持 される。このようにして、短パケットの送信に長パケットの送信より高い優先度 を与えることにより、長パケットの送信による短パケットの送信遅延を最小化さ せる。

システムは前の競合パケットから新たに到達したパケットを切り離すので（即ち 、切り離した競合する長短のパケットをそれぞれ短セツション及びサイクルで完 全に解決するので）、システムは安定である。チャネル容量に対する要求が増加 するに従って、遅延は長くなるが、チャネル利用の効率はＣＳＭ＾／ＣＤシステ ムの場合のようには低下しない。最後に、搬送波検知及び競合検出処理が競合解 決のために高速フィードバック情報を供給するので、チャネル・スルーブツトは 従来の技術のランダム分割又はツリー法のものより相当に大きい。

〔図面の簡単な説明〕

第１図はこの発明による通信システムのブロック図、第２図は第１図に示す通信 制御装置の機能的な構成を示すブロック図、 第３図はこの発明による通信システムの総合的な動作の一例を示すタイミング図 、 第４図〜第８図はこの発明による通信制御装置の動作を示すフローチャート、 第９ａ図〜第９ｄ図はこの発明による通信制御装置により用いられるフィードバ ック信号に有用なタイミング図、第１０図はこの発明の好ましい実施例の動作を 説明する際に有用な制御パラメータの値のテーブル、 第１１図はこの発明による通信制御装置の動作の例を示すプロ。

り図である。

〔実施例〕

本発明によるバクット交換による優先度ランダム分割・競合検出（ＰＲＳ／ＣＤ ）通信システムの概要構成を第１図に示す、　ＰＲＳ／ＣＤ通信システムは同軸 ケーブル１０を有する単独チャネルの通信媒体を備えている。複数の通信チャネ ル１２は同軸Ｔコネクタ１４を備えている受動タップを介して通信媒体に接続さ れている。

各通信チャネル１２は同軸ケーブル１０上の情報を送受信し、搬送波検知信号Ｃ ３及び競合検出信号ＣＤを発生するトランシーバ１８（このようなトランシーバ は従来の技術で知られているので、更に詳細に説明はしない。）と、通信チャネ ル１２に対する端末装置のアクセスを制御する通信制御装置２０と、端末装置間 で送信されるメツセージを発生し、他の端末装置から受信するメツセージを蓄積 し、かつ表示するワーク・ステーション２２とを備えている。

ＰＲＳ／ＣＤ通信システムの総合的な構成は、通信制御装置２０に大きな相違が あるが、現在使用されているＥＴＨＥＲＮＥＴのような標準ＣＳＭ＾／ＣＤ通信 システムに類似している。

ワーク・ステーション２２には、例えば、英数字データ入力を発生するキーボー ドと、英数字データを表示するモニタ・ディスプレイ装置、又は高解像度イメー ジ情報を発生するスキャナーを有する高解像度イメージ端末装置と、高解像度イ メージを表示するモニタとが備えられている。データは発信源及び宛先のレシー バ・アドレスを含む短いデータ・パケットにより送信される。イメージ情報はデ ータ・パケットの１０〜１００倍の長いイメージ・パケットにより送信される。

第２図を参照すると、通信制御装置２０は搬送波検知信号Ｃ８及び競合検出信号 ＣＤｔトランシーバから受信する。

フィードバック信号発生器２８が搬送波検知信号ＣＳ及び競合検出信号ＣＤを受 取り、以下で説明するフィードバック信号Ｆを発生する。ランダム分割処理制御 手段３０はフィードバック信号Ｆを用い、以下で説明するように、送信バッファ ２４及び受信バッファ２６からのデータ・パケットを制御している。送信バッフ ァ２４及び受信バッファ２６はデータ・バス３２を介してワーク・ステーション ２２に接続され、インタフェース３３を介してトランシーバ１８に接続されてい る。

フィードバック信号発生器２８及びランダム分割処理制御手段３０はハードウェ ア、ソフトウェア又はファームウェアにより実現することができるや例えば、通 信制御装置２０は送受信すべきデータ・パケット及びイメージ・パケットを蓄積 するバッファ・メモリに接続され、プログラムされているマイクロプロセッサを 備えてもよい。

通信制御装置２０を詳細に説明する前に、当該システムの動作を総括的に、即ち 当該システムの全通信制御装置２０間の正味の協力結果に基づいて説明しよう、 パケット送信は複数のサイクル及び複数のセツションに編成される。１セツシヨ ンは、最終セツション中に到着する全てのデータ・パケットを送信するのに必要 とする期間、又は最終セツション中にデータ・パケットが一つも到達しなかった ときに、最終サイクルで到達したイメ−ジ・パケットのうちの一つを送信するの に必要とする期間である。データ・パケット又はイメージ・パケットは、首尾よ く送信するまで、送信バッファ２４に保持される。

以下の説明では、１セツシヨンは、データ・パケットの送信に割り付けられてい るときは、「データ・セツション」と呼ばれるが、１つのイメージ・パケットの 送信に割り付けられているときは、「イメージ・セツション」と呼ばれる。１セ ツシヨンは、それが連続的な２つの空きスロットからなるときは、空きセツショ ンと呼ばれる。

１ザイクルは、前のサイクル中に到達した全てのイメージ・パケットを送信する ために必要な期間である。もし、前のサイクルでイメージ・パケットが到達しな かったときは、現在サイクルは空きセツション、で終了する。１サイクルは：（ ａ）１つの空きセツション；（ｂ）空きセツションに続く多数のデータ・セツシ ョン；（ｃ）１イメージ・セツション；又は（ｄ）イメージ・セツション及びデ ータ・セツションの複合から構成される。

あるセツションで到達したデータ・パケットは、ランダム分割処理を用いる次の セツションで首尾よく全て送信される。同様に、１サイクルで到達したイメージ ・パケットは次のサイクルで首尾よく全て送信される。イメージ・セツションは 、各サイクルにおいて前のセツションでデータ・パケットが到達しなかったとき にのみ開始される。データ・パケット送信の遅延を許容し得る値ｔで減少させる ために、各イメージ・セツションでは１イメージ・パケットのみの送信が許可さ れる。残りは次のセツションまで保持される。

この発明によるＰＲＳ／ＣＤ通信システムのパケット送信の例を第３図に示す。

この例では、それぞれイメージ到達及びデータ到達の時間線上のドツトにより示 されるように、サイクル１の先頭で、２イメージ・パケットＩ、及び■２．４つ のデータ・バケツ）’　Ｄ　＋　、　Ｄ　２　、　Ｄ　）及びり、が到達してい る。データＤ、、Ｄ２．Ｄコ及びり、は、優先度が高いので、イメージ■１及び ■２の前に送信が許可される。ランダム分割処理によるこれらのパケット間の競 合の最終解決により、セツション１が構成される。このセツション中に、他のデ ータ・パケットＤ５が到達する。従って、前のセツションで到達したデータ・パ ケットはイメージ・パケットより高い優先度を有するので、セツション２はその 送信に割り付けられる。

セツション２では、データ・パケットは到達しない、従って、セツション２の終 了後に直ちに送信されるデータ・バケツ１〜は存在しない、この結果、空きスロ ットとなる。　ＰＲＳ／ＣＤ通信システムにおいてスロットの長さは、システム における２つの端末装置間の最大信号伝搬遅延長であり、従来の技術ランダム分 割処理法のスロット長よりずっと短い。

この点で、システムにおいて活性な全ての通信端末装置は、セツション２で到達 したデータがないことを知る。イメージ・パケット１１及び工、はセツション３ で送信が許可される。これらの送信順序はランダム分割処理により判断され、そ の結果、イメージ・パケットのうちの一つ、例えば■２を首尾よく送信する。イ メージ・パケット■２の送信成功によりセツション３が完結する。

イメージ・パケット■、は第１サイクルの次のイメージ・セツションのために保 持される。セツション３では、データ・パケットＤ６〜Ｄ、。が到達する。従っ て、新しいセツション４はデータ・パケットの送信に割り付けられる。新しいイ メージ到達Ｉ。

は次のサイクルまで保持される。セツション４では到達したデータ・パケットが ないので、セツション５はイメージ・パケットＩＩの送信に割り付けられる。前 のサイクルで到達した全てのイメージ・パケットはセツション５の終了までに全 て送信され、サイクル１を終結する。

サイクル１で到達したイメージ・パケットエ３はサイクル２で送信される。しか し、サイクル１のセツション５で到達したデータ・パケットＤＩ＋及びＤＩ２は 、サイクル２の第２のセツションでイメージ・パケット■、を送信する前に、サ イクル２の第１セツシヨンで送信される。セツション２中に到達したデータ・パ ケットＤＩ３〜Ｉ）＋ｉは、サイクル３のセツション１で送信される。

サイクル２ではデータが到達しないので、サイクル３はデータ・セツション（デ ータ・パケットＤＩ３〜ＤＩ６の送信）と、空きセツションとからなる。それぞ れサイクル３及びサイクル４で到達したイメージ・パケット又はデータ・パケッ トはないので、サイクル４及びサイクル５は空きセツションである。ｆ＆後に、 サイクル６は１つのイメージ・セツションであり、サイクル５で到達したイメー ジ・パゲッ）−Ｉ　、を送信する。データ・パケット及びイメージ・パケットの 送信はこのようにして継続する。

通信制御装置２０の動作を総合的な見地ではなく、局部的に詳細に説明しよう、 この発明を実行する好ましい実施例では、通信制御装置２０はプログラムされた マイクロプロセッサと、送受信するイメージ・パケット及びデータ・パケットを 保持する関連のバッファ・メモリとを備える形式により実現される。マイクロプ ロセッサのプログラムには以下で定義している一組のレジスタＦ、Ｇ、Ｉ　、Ｂ 、Ｕ、Ｒ及びＳが含まれる。

Ｆはチャネル・フィードバック信号である。

Ｆ＝０：判断実行時点でチャネルが空きのとき、即ち最終送信の終了より後の、 又は前の判断実行時点より後のｒユニットのときである。ただし、ｒは回線網の 最大端末装置間の信号伝搬時間であるフィードバック信号Ｆのｒ期間は空きセツ ションと呼ぶ。

Ｆ−１：チャネルが判断実行時点でビジーのときであり、送信は成功したデータ ・パケットである。

Ｆ−２：判断実行時点でビジーのときであり、送信は成功したイメージ・パケッ トである。

Ｆ−３＝チヤネルが判断実行時点でビジーのときであり、送信は競合断片である 。トランスミツターは、送出パケットが他のバケツ１へと衝突したのを検出する と、その送信を直ちに停止する。衝突断片とは衝突したパケットの不完全な送信 をいう。

Ｇは、グローバル・ポインタであり、その値が与えられた時間が全ての端末装置 で同一となっている。Ｇの値は当該システムの全ての端末装置が利用可能なフィ ードバック信号の情報により更新される。

■は、各端末装置に接続されている個別的なインジケータである、データ・パケ ットはＩ＝２から開始され、イメージ・パケットは当該システムの優先度履歴に 従ってＩ＝１スは０から開始される。

Ｂは、衝突が検出されたときに各送信端末装置で局部的に独立して発生するラン ダムの２進数であり、■に加算されて端末装置を送信グループ又は非送信グルー プにランダムに割り付ける。

Ｕは、サイクル制御処理に用いられる総合的な２進ポインタである。

Ｒは、サイクル制御処理に用いられる固有のインジケータであり、現在サイクル で送信されるべきイメージ・パケットを有するときに表示される。

Ｓは、サイクル制御処理に用いられる総合的なインジケータであり、進行中のセ ツションでデータ・パケットの送信が首尾よく行われたか否かを表示する。

ここで、第４図を参照して、通信制御装置２０の総合的な制御処理制御を説明し よう、「新しいユーザ」と呼ばれる端末装置が最初にシステムに加わると、セツ ション確認ルーチンを実行してランダム分割処理に追従することができるセツシ ョン境界のうちの一つを位置付けする。セツション境界が確認されると、端末装 置は次のセツションに参加し、反復的にランダム分割処理を実行する。ただし、 ランダム分割処理に入る前に、端末装置は固有のインジケータＩの値を初期化す る。バッファに送信すべきデータ・パケットが待機しているときは、■を２にセ ットする。そうでないときは、ＩはＵ又はＲの値に従って１又は０にセットする 。

第５図はセツションの確認処理を示す、先ずカウンタＫを０にセットし、受信処 理を実行する。受信処理は以下に説明するようにフィードバック信号Ｆを発生す る。セツション確認処理は、イメージ・パケットを受信するまで（Ｆ＝２）か、 又は連続する４つの空きスロットを検出するまで（４回連続してＦ＝Ｏ）、チャ ネルを「聞＜」、イメージ・パケットを検出したときは（Ｆ＝２）、セツション 確認処理を抜は出してイメージ・セツション直後のセツションの境界のマークを 付ける。もし、４つの空きスロットが連続して検出されたときは、セツション確 認処理は、当該空きセツションにあるとほぼ確認をする。しかし、空きセツショ ンは連続する２つの空きスロットからなるので、端末装置は、検出した最終空き スロットが空きセツションのうちの第１の空きスロットか、又は第２の空きスロ ットかを知ることができない。

４つの空きスロッｌ−後に、高い確率でシステムは空きセツションにあったと判 断された。少ないといえども、これらの４つの空きスロットは、前のセツション において競合解決の一部であるという可能性があるので、この判断は確実である という判断ではなかった。数４はこの可能性を充分に小さくするように選択され たものである。

従って、２つの確認誤りがあり得る。その第１は、可能性は低いが、４つの空き スロットはデータ・パケットか、又はイメージ・パケットかの競合解決セツショ ンの一部である。その第２は、空きセツションは２つの空きスロットからなるの で、新しいユーザがマークした境界は１スロツト離れている可能性がある。

セツション境界を予測した後は、「新しいユーザ」はレディーのときにそのパケ ットを送信することができる。パケットの送信が成功したときは、回線網の全て のユーザは新しい境界に自動的に調整される。送信したパケットがイメージ・パ ケットのときは、通常の場合のように、全てのユーザがランダム分割処理（以下 で説明する）から抜は出し、新しい境界に合わせる。送信したパケットがデータ ・パケットのときは、Ｋ≧４、かつＳ＝１であるので、全てのユーザはランダム 分割処理から抜けだし、新しい境界に合わせる。

新しいユーザがパケットを送信する前に、他のユーザがいくつかのパケットを送 信しているときは、新しいユーザはチャネルのフィードバックに基づいてセツシ ョン境界２訂正する。新しいユーザの訂正は通常のセツション、及び以下に説明 するランダム分割処理に含まれているサイクル確認に基づいている。

「新しいユーザ」がそのパケットを送信している間に衝突を検出したときは、「 新しいユーザ」が確認処理の誤りを起こした可能性がある０次に、競合解決及び 境界訂正の処理は全ての端末装置により実行される。

競合解決がデータ・パケット又はイメージ・パケットのみを原因としているとき は、衝突はランダム分割処理により解決され、「新しいユーザ」を含む全ての端 末装置は競合解決の終結で境界に合わせる。このようにして、この場合は境界確 認で犯したかも知れない誤りを訂正する。

「新しいユーザ」が送信したデータ・パケットが多数のイメージ・パケットと衝 突したときは、新しいユーザがセツション確認誤りをしたことを意味する。実際 にはイメージ・セツションにあるので、「新しいユーザ」は境界誤りを訂正する 必要がある。

以下に説明する競合は、ランダム分割処理により解決され、データ・パケットは イメージ・パケットを送信する前に、首尾よく送信される。Ｇ＝１、Ｓ＝１及び に≧４のときは、１セツション当り１イメージ・パケットの送信を補償するため に、ランダム分割処理から抜は出すことが許可される端末装置はない、「新しい ユーザ」はイメージ・セツションの境界を検出し、その誤りを訂正する。「新し いユーザ」により送信されたデータ・パケットは、次のデータ・パケットまで首 尾よく送信されるか、又は保持される。

「新しいユーザ」により送信されたイメージ・パケットが多数のデータ・パケッ トと衝突するときは、回線網が実際にはデータ・セツションにあることを意味す る。イメージ・パケットはランダム分割処理によりこのデータ・パケットで首尾 よく送信される。この場合に、全ての端末装置はイメージ送信により強制された 新しい境界に合わせる。

要するに、［新しいユーザＪは第５図に示すセツション確認処理を終結した後は 、何時でもそのパケットを送信することができる。全ての確認誤りはランダム分 割処理の修復機構により自動的に訂正される。セツション確認処理によりいくら かのオバーヘッドが導入されるが、総合的なパフォーマンスに対する影響は最小 となっている。

端末装置が新しいセツション境界を検出することにより、又は強制することによ り、初期化された後に、通信制御装置２０は第６図に示すランダム分割処理を実 行する。ランダム分割処理は他の端末装置と協力してセツション及びサイクルを 発生する条件ループである。第６図の最上部に示すように、条件ループに入る前 に、制御パラメータＧ、Ｕ、Ｒ及びＳをセットする。個別的なインジケータ■は グローバル・ポインタＧと比較され、端末装置が送信可能か、又は受信可能かを 判断する。端末装置はＧ＝１のときにのみ送信することが許可される。Ｇ　＝　 １のときは、送信処理が呼び出され、同時にランダムな２進数Ｂを発生する。送 信後に、フィードバック信号Ｆを調べてデータ・パケット若しくはイメージ・パ ケットを首尾よく送信したか、又は衝突が発生したかを判断する。衝突が発生し たときは（Ｆ−３）、個別的なインジケータＩをランダムな２進数（０又は１） により増加し、グローバル・ポインタＧを１により増加する。

２以上の端末装置が同一かつ任意の２進数Ｂを発生ずると、新しい衝突となる６ ランダム分割処理による連続的な各バスにおいて、衝突に含まれる各端末装置そ のものは１つの送信グループ又は非送信グループに任意に割り付けられる。ラン ダム分割処理による次のパスにおいて、送信グループの端末装置は再び送信を試 行する。最終的にランダム分割処理により、１端末装置のみが送信グループに残 る。次に、この端末装置はそのパケットを首尾よく送信することができる。首尾 よく送信した役、全ての端末装置のＧを１だけ減少させ、ランダム分割処理を反 復する。１以上の端末装置がＧ＝１のときは、新しい衝突となり、ランダム分割 処理は以上に説明したように、再び競合の解決をする。

このようにして、ランダム分割処理が継続し、前のセツション中に受信した全て のデータ・パケットを送信するまで発生した競合を解決する。以上で説明したよ うに、全てのデータ・パケットはＩ＝２により初期化され、またイメージ・パケ ットはＩ＝１又はＯにより初期化され、従って送信するデータ・パケットを有す る全ての端末装置は、イメージ・パケットを送信する前にデータ・パケットを首 尾よく送信する。しかし、全てのデータ・パケットを送信したときは、Ｇを１に 減少させて、イメージ・パケットを送信することができる。イメージ・パケット 間で衝突が発生すると、各送信端末装置はランダムな２進数Ｂを発生し、その個 別的なインジケータ■を１又は０だけ増加させ、かつＧを増加させる。Ｇ＝１を 有する端末装置が送信をし、１端末装置のみがＧ＝１になるまで処理を反復する 。次に、この端末装置はそのイメージ・パケットを首尾よく送信する。しかし、 イメージ・パケットの送信の成功が検出されると（Ｆ＝２）、Ｒは０にセットさ れ、ランダム分割処理は第４図の総合制御処理に戻る。これによってセツション を終結させることになり、他のイメージ・パケットの送信を許可する前に、最近 に到達したデータ・バケツｌ〜の送信を許可する。

送信するデータ・パケットがないときは、空きスロットとなり、Ｇを１に減少し 、イメージ・パケットを送信する。しかし、各イメージ・パケットの送信の後は 、データ・パケットの条件に無関係に、自動的にＧの値を減少するのではなく、 ランダム分割処理を励起し、制御がランダム分割処理に戻されたときはＧを２に リセットする。

他方、個別的なインジケータＩが端末装置におけるＧに等しくないときはく第６ 図を参照）、ランダム分割処理は受信処理に分岐する。受信処理はチャネルを監 視し、フィードバック信号Ｆを発生する。衝突が発生したときは（Ｆ＝３＞、Ｇ の値を１だけ増加し、ランダム分割処理のループを反復する。チャネルがアイド ル（Ｆ＝０）のときは、又はデータ・パケットを首尾よく送信したときは（Ｆ　 ＝　１　）、Ｇを１により減少させ、ランダム分割処理と再び反復する。イメー ジ・パケット乞送信したときはＣＦ＝２）、ランダム分割処理は総合制御処理く 第４図を参照）に戻り、新しいセツションを開始する。受信処理におけるＫの値 についての増加及び検査は、以上で説明したように、セツション確認処理と協同 することにより、新しい端末装置が回線網に参加したときに新しい境界を定める 。

一般に、全ての端末装置はパケット送信のセツション及びサイクルの境界を監視 する。回線網で活性であった端末装置は、チャネル・フィードバック信号Ｆによ り及びレジスタＧ、Ｉ、Ｓ。

Ｒ及びＵの値によりセツション及びサイクルの境界を継続して追跡する。全ての 端末装置が実行したセツション及びサイクル確認は次のようである。イメージの 送信終了は１イメージ・セツションの境界を表示する。１サイクルの終了は、衝 突断片なしの１イメージ・セツションの終了か、又は２つの空きスロットからな る空きセツションかによって表わされる。データ・セツションの境界は、Ｇ−１ 、かつＳ＝１のときにマークが付けられる。

回線網に参加したばかりの「新しいユーザ」についてのセッシ。

ン確認及びザイクル境界は、セツション確認処理を参照して以上述べたように処 理される。

ここで、第７図を参照して送信処理を説明しよう。送信処理がランダム分割処理 により呼び出されると、送信処理は複数ビットのパケットをトランシーバに送信 し始め、パケットの終りを調べる。次に、衝突が検出されたか否かについて調べ る。

衝突が検出されなかったときは、完全なパケットを送信する。

パケット送信の終りで、フィードバック信号Ｆを発生し、パケットがイメージ・ パケットか、又はデータ・パケットであったかを示す。

衝突が検出されたときは、送信処理はフィードバック信号Ｆ＝３を発生すること により衝突を表示し、他の端末装置が確実に衝突を検出゛して送信を停止するよ うに長さａ′°の妨害信号を送信する。次、に、送信処理は、チャネルから搬送 波が検出されなくなるまで待機し、更にハードウェアが回復できるように時間長 Ｗだけ待機し、他のループを実行するランダム分割処理を知らせる「判断オン」 フラグをセットする。

次に、第８図を参照して受信処理を説明しよう。受信処理はクロックＣＬを開始 し、チャネルの搬送波について監視する０時間計の期間について搬送波を検出し なかったときは、フィードバック信号Ｆ＝０を発生し、制御をランダム分割処理 に戻す。

搬送波を検出したときは、クロックＣＬをリセットし、受信するパケットをバッ ファに蓄積する。送信の終りで、受信したバケツトの長さを調べてこれがデータ ・パケット（ＣＬ＝　１　＞か、イメージ・パケット（ＣＬ＞　１　＞か、又は 衝突断片（ＣＬ≦２ｒ＋ａ）かを判断し、これに従ってフィードバック信号Ｆを 発生する０以上の説明では、説明を簡単にするためにデータ・パケットの長さを １に正規化している。パケットがデータ・パケット又はイメージ・パケットであ るときは、受信処理はアドレスを調べ、その端末装置が目的の受信者であるかに ついて調べる。イエスのときは、受信処理はメツセージをアンバックし、これを ワーク・ステーションに転送する。その端末装置が目的の受信者でないときは、 受信処理はバッファをクリアし、ハードウェアが回復できるように時間Ｗでの遅 延を行ない、「判断オン」フラグをセットし、制御をランダム分割処理に戻す。

第９ａ図〜第９ｄ図は受信処理でフィードバック信号を発生させるために用いる 期間を示すタイミング図である。第９ａ図は送信後における長さｒの２つの空き スロットと、空きスロットの終了における判断実行点を示す、第９ｂ図は２ｒ＋ ａより短い、又はこれに等しい長さを有する衝突断片を示す、第９ｃ図はデータ ・パケットの長さく１に正規化された）を示す。第９ｄ図はよう。この例では、 前のサイクルの最終セツション中に３データ・パケットが到達し、かつ前のサイ クル中に通信制御装置２０の５端末装置に２つのイメージ・パケットが到達して いる。データ・パケット及びそれらの送信端末装置をＤ　＋　、　Ｄ　２及びり 、により表わし、またイメージ・パケット及びこれらの端末装置をＩ１及び工、 により表わす。ランダム分割処理の開始で、５端末装置における制御パラメータ を第１１図の第１例に示す。各端末装置のランダム分割処理による第１バスにお いて、■の値はＧと比較され、端末装置が送信しているか、又は受信しているか を判断する。ＩはＩ、又はＩ２に等しくないので、これらは送信が許可されず、 単にこれらのレジスタＦ、Ｇ、Ｓ及びＵを更新する。Ｄ　＋　、　Ｄ　２及びＤ ３に対してはＩ＝Ｇであるから、これら３端末装置は同時に送信をし、衝突をす る結果となる。衝突が検出されると、送信端末装置は送信を停止し、フィードバ ック信号Ｆ＝３を発生し、ランダム分割処理に戻る。同時に、受信端末装置は搬 送波が存在しないのを検出し、送信の長さから送信は衝突断片であったことを知 る。次に、受信端末装置はフィードバック信号Ｆ＝３を発生し、それぞれのラン ダム分割処理に戻る。

ランダム分割処理に戻ると、Ｄ、、Ｄ２及びり、の送信端末装置はランダムな２ 進数Ｂを発生し、これらは個別的なインジケータエをＢにより増加させる。全て の端末装置はＧを１だけ増加させる。Ｄ、、Ｄ２及びり、の送信端末装置が発生 したランダムな２進数Ｂをそれぞれ０．１及びＯとすると、制御パラメータは第 １０図の第２列に示すものとなる。

ランダム分割処理により次のバスにおいて、Ｄ２の送信端末装置のみがＩ＝Ｇと なるので、Ｄ２の送信端末装置はデータ・パケットを首尾よく送信する。データ ・パケットの送信に首尾よくした結果として、全ての端末装置はフィードバック 信号Ｆ−１を発生む、ポインタＳ＝１をセットし、Ｇを１により減少させる。そ の結果、制御パラメータは第１０図の第３列に示すものとなる。

ランダム分割処理を介する次のバスにおいて、データ・パケットＤ１及びＤ３は 同時に送信され、衝突を発生させる。データ・パケットＤ１及びＤ３がランダム な２進数１を発生すると仮定すると、その結果の制御パラメータの状態は第１０ 図の第４列に示すものとなる。

再びデータ・パケットＤ、及びり、が送信をすると、衝突が発生する。しかし、 今度は両端末装置がランダムな２進数Ｏを発生する。その結果は第１０図の第５ 列に示すものとなる。

ランダム分割処理を介する以下のバスでは、Ｇ＝４がいずれの端末装置の１値よ り大きいので、どの端末装置も送信することができず、従って空きスロットが発 生する。空きスロットの終りで、制御パラメータは第１０図の第６列に示すもの となる。

データ・パケットＤ、及びり、の端末装置が再び送信し、衝突する。しかし、今 度はデータ・バックＩ−Ｄ　、の端末装置がランダムな２進数Ｏを発生し、デー タ・パケットＤ、の端末装置は第１０図の第７列に示すように、ランダムな２進 数１を発生する。

その結果、データ・パケットＤつを首尾よく送信し、制御パラメータの状態は第 １０図の第８列に示すものとなる。

次に、データ・パケットＤ１は首尾よく送信され、その結果は第１０図の第９列 に示すものとなる。Ｉ＝２に等しいイメージ・パケットは存在しないので、ラン ダム分割処理による次のバスは空きスロットを発生し、第１０図の第１０列に示 す結果となる。

最後のデータ・パケットの送信からＳ＝１、またＧ＝１なので、ランダム分割処 理は総合制御処理により戻される。ランダム分割処理に戻ると、Ｇは２にセット され、Ｕ、Ｒ及びＳは０にセットされる。これは、前のセツション中に到達し、 なかも知れないデータ・パケットをイメージ・バック１への前で確実に送信させ る。制御パラメータは第１０図の第１１列に示すものとなる。送信するデータ・ バック１〜がなく、またイメージ・パケットの送信が許可されないので、スロッ トは空きとなる。その後の制御パラメータは第１０図の第１２列に示すものとな る。今度は、Ｓが０にリセットされるのて、ランダム分割処理は内部でループし 続ける９次のバスでは、イメージ・パケットＩ、及びＩ２を送信し、衝突が発生 する。Ｆ＝３、かつＧが１に減少したので、Ｒ及びＵは１にセットされる。イメ ージ・パケットＩ、の端末装置がランダムな２進数Ｏを発生し、イメージ・パケ ットＩ２の端末装置はランダムな２進数０を発生ずると仮定すると、制御パラメ ータは第１０図の第１３列に示すものとなる。

今度は、イメージ・パケットＩ２の端末装置はイメージ・パケットＩ２を首尾よ く送信する。フィードバック信号Ｆは２であるので５イメージ・バック１−Ｉ２ の端末装置に対するＲを０にリセットさせ、制御を総合制御処理に戻す。イメー ジ・パケットＩ、の端末装置の制御パラメータは第１０図の第１４列に示すもの どなる。ランダム分割処理に戻った際にＧが２にリセットされ、イメージ・パケ ット■１のＩが１であるので、イメージ・パケットＩ２の送信中に到達するデー タ・パケットがないと仮定すると、空きスロワｌ〜どなる。フィードバック信号 ＦはＦ＝０となる、Ｇは１により減少され、制御パラメータは第１０図の第１５ 列に示すものとなる。

最後に、イメージ・パケットＩ、が送信され、フィードバック信号ＦはＦ＝２と なり、ＲはＯにセットされ、サイクルが終了する。制御パラメータは第１０図の 第１６列に示すものとなる。

通信制御装置２０はこのようにしてサイクルし続け、イメージ・パケットを送信 する前に前のセツション及び現在セツションに到達する全てのデータ・パケット 企送信し、イメージ・セツション当り１イメージ・パケットのみを送信し、次の サイクルに行く前に前のサイクルで到達した全てのイメージ・パケットを送信す る。

第１１図は以上で説明した一連のステップにより発生したランダムな２進数のツ リーを示す。このツリーはそのルート・ノートで２つのサブツリーに分岐され、 その一つがデータ・パケット、他がイメージ・パケットである。なにも付けてな いツリーの分岐（０）は空きスロットを表わす。他の分岐は送信が発生する個所 を示す。この例ではどのセツション中にも到達したデータ・パケットが存在せず 、データ・セツションの後で連続的な２つのイメージ・セツションを実行してい る。進行中のセツションでデータ・パケットが到達した場合は、イメージ・パケ ットが保持され、次のイメージ・パケットを送信する前に、新しいデータ・ツリ ーを発生する。

説明の便宜上、データ・パケット及びイメージ・パケットなる話を用いたが、こ の発明をデータ及びイメージの送信に限定するものではなく、情報パケットの長 さが１桁以上の長さで異なり、混合した長さのイメージ・パケットを送信する際 に利用される。

〔発明の効果〕

この発明は通信チャネルを共有する一つのグループの通信端末装置間で情報を送 信するローカル・エリア・ネットワークのような通信システムにとり有用である 。この発明によるＰＲＳ／ＣＤバクット交換通信システムは、増加する重トラフ ィックの存在で安定であるという効果がある。即ち、チャネル使用の効率はトラ フィックが増加しても低下しない。更に、このシステムは、このシステムの特徴 の衝突検出により得られる急速なフィードバック情報によって、従来の技術のラ ンダム分割処理以上にチャネル利用を増加させるという効果がある。ＰＲＳ／Ｃ Ｄ通信システムは更に情報形式の優先度によって、高い優先度の情報パケットの 送信が低い優先度の情報のパケットにより短い送信遅延となる効果がある。

ＩＧ　Ｉ ＩＧ　２ 出口 口い　【 １口 Ｘ口 ＦＩＧ、　９ａ ＦＩＧ、　９ｂ ＦＩＧ、　９ｃ 琳１釉ＩＴ＋ぐラメ−７ ＦＩＧ、　１０ ＩＧ１１ 国際調査報告 １゜ｎ”ｎａｌｎｅａｌ　＆、、１ｂ。。、。ＰＣＴ／ＩＪＳ　８６１０ｉ７０ ６　−２−ＡＮＮＥＸ　Ｔｏ　ＴＨＥ　ＩＮＴＥＲＮＡＴＩＯＮＡＬ　５ＥＡ３ ＣＨＲＥ？ＯＲＴ　ＯＮ

Claims (9)

【特許請求の範囲】
1. １．パケット交換ローカル通信装置において、ａ．通信媒体と、 ｂ．前記通信媒体に接続され、短パケット及び長パケットを含む情報を通信し、 かつ長パケットが短パケットより１桁以上長くなっている複数の通信端末装置と を備え、前記通信端末装置は （ｉ）前記通信媒体上で信号を送受信すると共に、前記通信媒体上の搬送波の存 在を検出し、その存在に応答して搬送波検出信号を発生する手段、及び前記通信 媒体上の情報パケット間の衝突を検出し、この検出に応答して競合検出信号を発 生する手段を含むトランシーバ手段と、（ｉｉ）他の通信端末装置に送出すべき 長短の情報パケットを発生すると共に、他の通信端末装置から送出された長短の 情報パケットを受信するワーク・ステーションと、（ｉｉｉ）前記トランシーバ 手段と前記ワーク・ステーションとの間に接続され、前記搬送波検知信号及び前 記競合検出信号に応答して、異なる端末装置から情報パケットの送信間の競合を ランダム分割処理により解決するように情報パケットの送信を制御し、長パケッ トより短パケットの送信に優先度を与える通信制御手段とを備えることを特徴と するパケット交換ローカル通信装置。
2. ２．請求の範囲第１項記載のパケット交換ローカル通信装置において、前記複数 の通信端末装置における前記通信制御手段は、パケットの送信を１以上のセッシ ョンからなるサイクルに編成させるように動作すると共に、セッションは前のセ ッション中に到達した全ての短パケットの送信に必要な時間、又は短パケットが 前のセッション中に到達していないときに前のサイクル中に到達した１つの長パ ケットの送信に必要な時間であるとし、かつサイクルは前のサイクル中に到達し た全ての長パケットの送信に必要とする時間であるとし、もし長パケットが前の サイクルで到達していないときは、空きセッションにより終了させ、セッション は前のセッションの終了でパケットが到達していないときは空きセッションであ るとすることを特徴とするパケット交換ローカル通信装置。
3. ３．請求の範囲第２項記載のパケット交換ローカル通信装置において、前記通信 制御手段は （ａ）前記搬送波検知信号及び前記競合検出信号に応答して搬送波、送信したデ ータ・パケット、送信したイメージ・パケット又は衝突のいずれかがないことを 表示するためのフィードバック信号を発生するフィードバック信号発生手段と（ ｂ）衝突フィードバック信号に応答して送信グループ又は非送信グループにパケ ットをランダムに割り付け、次に可能な機会のときに前記パケットを送信するか 否かについて判断するランダム分割処理制御手段と を備えていることを特徴とするパケット交換ローカル通信装置。
4. ４．請求の範囲第３項記載のパケット交換ローカル通信装置において、前記通信 制御手段はフィードバック信号に応答してセッションの境界を検出するセッショ ン確認手段を更に備えていることを特徴とするパケット交換ローカル通信装置。
5. ５．請求の範囲第３項記載のパケット交換ローカル通信装置において、前記通信 制御手段は衝突の検出に応答して、確実に当該システムにおける全ての端末装置 が衝突を首尾よく検出するように予め定めた長さの妨害信号を送出する手段を更 に備えていることを特徴とするパケット交換ローカル通信装置。
6. ６．請求の範囲第３項記載のパケット交換ローカル通信装置において、前記ラン ダム分割処理制御手段はグローバル・ポインタを蓄積する第１レジスタ手段（Ｇ ）と、送信すべきパケットに関連する個別的なインジケータを蓄積する第２レジ スタ手段（Ｉ）と、それぞれの衝突後にバイナリ・ディジット（Ｂ）をランダム に発生する手段とを備え、前記ランダム分割制御手段はバイナリ・ディジットを 第１レジスタ（Ｉ）の内容に加算し、衝突を検出する度にグローバル・ポインタ （Ｇ）を増加させ、かつパケットを首尾よく送信する度にグローバル・ポインタ （Ｇ）を減少させる手段を備え、前記ランダム分割処理制御手段は第１レジスタ 手段（Ｇ）と、第２レジスタ手段（Ｉ）との内容を比較してＧ＝Ｉのときは、前 記パケットの送信を行う手段を更に備えていることを特徴とするパケット交換ロ ーカル通信装置。
7. ７．請求の範囲第６項記載のパケット交換ローカル通信装置において、前記ラン ダム分割処理制御手段は短パケット又は長パケットとして送信すべきパケットの 形式を識別し、かつ長パケットを首尾よくそれぞれ送信した後に短パケットの送 信の優先度を与える手段を備えていることを特徴とするパケット交換ローカル通 信装置。
8. ８．請求の範囲第７項記載のパケット交換ローカル通信装置において、前記パケ ットの形式を識別する手段は、送信すべきイメージ・パケットが残っているか否 かを表示するグローバルポインタを蓄積する第３レジスタ（Ｕ）と、特定の端末 装置が送信するイメージ・パケットを有することを表示する個別的なパラメータ を蓄積する第４レジスタ（Ｒ）とを備えていることを特徴とするパケット交換ロ ーカル通信装置。
9. ９．請求の範囲第１項記載のパケット交換ローカル通信装置において、前記短パ ケットはディジタル・データを表わし、前記長パケットはイメージ情報を表わす ことを特徴とするパケット交換ローカル通信装置。