JPH03188733A - ウィンドウサイズの決定方法とデータセルの輻輳制御方法 - Google Patents
ウィンドウサイズの決定方法とデータセルの輻輳制御方法Info
- Publication number
- JPH03188733A JPH03188733A JP2326116A JP32611690A JPH03188733A JP H03188733 A JPH03188733 A JP H03188733A JP 2326116 A JP2326116 A JP 2326116A JP 32611690 A JP32611690 A JP 32611690A JP H03188733 A JPH03188733 A JP H03188733A
- Authority
- JP
- Japan
- Prior art keywords
- virtual circuit
- window
- determining
- size
- rank
- 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
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/17—Interaction among intermediate nodes, e.g. hop by hop
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/16—Flow control; Congestion control in connection oriented networks, e.g. frame relay
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/27—Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
-
- 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/5629—Admission control
- H04L2012/5631—Resource management and allocation
-
- 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/5629—Admission control
- H04L2012/5631—Resource management and allocation
- H04L2012/5632—Bandwidth allocation
- H04L2012/5634—In-call negotiation
-
- 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/5629—Admission control
- H04L2012/5631—Resource management and allocation
- H04L2012/5632—Bandwidth allocation
- H04L2012/5635—Backpressure, e.g. for ABR
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5681—Buffer or queue management
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/33—Flow control; Congestion control using forward notification
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は、一般にはデータネットワークに関し、さらに
、詳しくはデータネットワーク内の情報の流れを改善す
るプロトコル、方法及び装置に関する。
、詳しくはデータネットワーク内の情報の流れを改善す
るプロトコル、方法及び装置に関する。
（従来技術）
ディジタルデータを転送するパケット交換ネットワーク
は、従来技術でよく知られている０＝船釣に、データは
ネットワークに接続されたホストから、一連のネットワ
ークリンクとスイッチを経て、受信ホストに伝送される
。送信ホストからのメツセージはパケットに分割され、
それがネットワークを介して伝送され、受信ホストで再
び組立てられる。仮想回線ネットワークが本発明の主題
であるが、ここで２つのホストの間の単一セツション間
に伝送されるデータパケットは、全て同一の物理ネット
ワークパスを辿る。
は、従来技術でよく知られている０＝船釣に、データは
ネットワークに接続されたホストから、一連のネットワ
ークリンクとスイッチを経て、受信ホストに伝送される
。送信ホストからのメツセージはパケットに分割され、
それがネットワークを介して伝送され、受信ホストで再
び組立てられる。仮想回線ネットワークが本発明の主題
であるが、ここで２つのホストの間の単一セツション間
に伝送されるデータパケットは、全て同一の物理ネット
ワークパスを辿る。
データトラフィックのランダム性から、データはネット
ワークのスイッチノードに、送出リンクの伝送速度より
大きい瞬間速度で到着する。また仮想回線からのデータ
は、伝送できるまでバッファ内に取り入れられる。従来
、各種キューイング統制法が知られている。初期のデー
タネットワークでは、キューイングにある種の先入れ先
出（ＦＩＦＯ）方式をとるのが通例であった。この先着
順サービスでは、異なる仮想回線から着信するデータパ
ケットは１つのバッファに入れられ、それらがバッファ
内に着信した順と、同じ順に出力リンク上に伝送される
る。もっと最近になり、一部のデータネットワークでは
、ラウントロピン方式のキューイング統制法が使われた
。このネットワークについては、エイ−ジー・フレーザ
（Ａ、Ｇ、Ｆｒａｓｅｒ）の「汎用データ転送システム
に向かう」と題する論文、ｒｌＥＥＥジャーナル オン
セレクティド エリア イン コミュニケーション（
ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ ５ｅｌｅｃｔｅｄ
Ａｒｅａｓ ｉｎ Ｃｏａｍｕｎｉｅａｔｉｏｎ ）
Ｊ １９８３年９月に述べられている。ラウントロピン
サービスは、着信する各仮想回線のデータを回線に対す
る別個のバッファ内に入れ、データを有するバッファか
ら代る代る少量のデータを、バッファが全て空になるま
で送る。米国特許第４，５８３，２１９号リトル（Ｒｉ
ｄｄｌｅ） 、は少量のデータからなるメツセージで、
遅延の小さい特定のラウントロピンの実施例を開示して
いる。
ワークのスイッチノードに、送出リンクの伝送速度より
大きい瞬間速度で到着する。また仮想回線からのデータ
は、伝送できるまでバッファ内に取り入れられる。従来
、各種キューイング統制法が知られている。初期のデー
タネットワークでは、キューイングにある種の先入れ先
出（ＦＩＦＯ）方式をとるのが通例であった。この先着
順サービスでは、異なる仮想回線から着信するデータパ
ケットは１つのバッファに入れられ、それらがバッファ
内に着信した順と、同じ順に出力リンク上に伝送される
る。もっと最近になり、一部のデータネットワークでは
、ラウントロピン方式のキューイング統制法が使われた
。このネットワークについては、エイ−ジー・フレーザ
（Ａ、Ｇ、Ｆｒａｓｅｒ）の「汎用データ転送システム
に向かう」と題する論文、ｒｌＥＥＥジャーナル オン
セレクティド エリア イン コミュニケーション（
ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ ５ｅｌｅｃｔｅｄ
Ａｒｅａｓ ｉｎ Ｃｏａｍｕｎｉｅａｔｉｏｎ ）
Ｊ １９８３年９月に述べられている。ラウントロピン
サービスは、着信する各仮想回線のデータを回線に対す
る別個のバッファ内に入れ、データを有するバッファか
ら代る代る少量のデータを、バッファが全て空になるま
で送る。米国特許第４，５８３，２１９号リトル（Ｒｉ
ｄｄｌｅ） 、は少量のデータからなるメツセージで、
遅延の小さい特定のラウントロピンの実施例を開示して
いる。
このラウントロピンサービスの範鴫に属する他の多くの
変更例がある。
変更例がある。
先着順キューイング統制法はラウントロピン統制法より
実施がやや容易である。しかし、トラフィックが高密度
状態の場合、先着順統制法は不公平となる。このことは
ニス・ピー・モーガン（Ｓ。
実施がやや容易である。しかし、トラフィックが高密度
状態の場合、先着順統制法は不公平となる。このことは
ニス・ピー・モーガン（Ｓ。
Ｐ、Ｍｏｒｇａｎ）の「バイト・ストリーム通信網にお
けるキューイング統制法とパッシブふくそう（輻１）」
と題する論文、「ザ プロシーデインゲス イブ Ｉ
ＥＥＥ ＩＮＦＯＣＯＭ（ｔｈｅＰｒｏｃｅｅｃｌ
ｌｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ ） Ｊ
１９８９年４月、に説明されている。限られた伝送資源
を多くのユーザが競う場合、先着順キューイングは長い
メツセージを提出するユーザに幅部するリンクのバンド
幅の全てをどうしても与えてしまい、短いメッセージを
送信しようとするユーザ全員に行き渡るには不十分な場
合でも、ラウントロピン方式は、使用可能バンド幅を平
等にユーザ全員に分けるので、少量のユーザが多量ユー
ザのために締め出されることはない。
けるキューイング統制法とパッシブふくそう（輻１）」
と題する論文、「ザ プロシーデインゲス イブ Ｉ
ＥＥＥ ＩＮＦＯＣＯＭ（ｔｈｅＰｒｏｃｅｅｃｌ
ｌｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ ） Ｊ
１９８９年４月、に説明されている。限られた伝送資源
を多くのユーザが競う場合、先着順キューイングは長い
メツセージを提出するユーザに幅部するリンクのバンド
幅の全てをどうしても与えてしまい、短いメッセージを
送信しようとするユーザ全員に行き渡るには不十分な場
合でも、ラウントロピン方式は、使用可能バンド幅を平
等にユーザ全員に分けるので、少量のユーザが多量ユー
ザのために締め出されることはない。
データ接続はどんな場合でも、送信機が受信機をオーバ
ーランさせることのないようにする必要がある。これは
エイ・ニス・タネンボーム（Ａ、Ｓ。
ーランさせることのないようにする必要がある。これは
エイ・ニス・タネンボーム（Ａ、Ｓ。
Ｔａｎｅｎｂａｕｍ ） 、コンピュータネットワーク
、第２版プレンティス・ホール、（１９８８）２２Ｂ−
２３９頁に記載のように、スライディング・ウィンド・
プロトコルにより通常行われる。送信機はフレームと呼
ばれる単位でデータを送る。各フレームはシーケンス番
号を有する。受信機はフレームを受信すると、そのシー
ケンス番号を送信機に戻す。送信機に一度に発行が許可
されるシーケンス番号は限られた数のみである。即ち、
データは所定量までは送信できるが、さらに新しいデー
タを送信するには、シーケンスの適切な肯定応答を受け
るまで待たなければならない。所定時間内に期待する肯
定応答が来ない場合、送信機は１つ以上のフレームを再
送信する。送信中の所定時間に、送信機に許されるビッ
トの最大数がウィンドサイズと呼ばれ、ここではＷで表
示される。発行シーケンスの最大数が、ウィンドサイズ
と呼ばれる場合もあるが、ここではそのようには使用し
ない。
、第２版プレンティス・ホール、（１９８８）２２Ｂ−
２３９頁に記載のように、スライディング・ウィンド・
プロトコルにより通常行われる。送信機はフレームと呼
ばれる単位でデータを送る。各フレームはシーケンス番
号を有する。受信機はフレームを受信すると、そのシー
ケンス番号を送信機に戻す。送信機に一度に発行が許可
されるシーケンス番号は限られた数のみである。即ち、
データは所定量までは送信できるが、さらに新しいデー
タを送信するには、シーケンスの適切な肯定応答を受け
るまで待たなければならない。所定時間内に期待する肯
定応答が来ない場合、送信機は１つ以上のフレームを再
送信する。送信中の所定時間に、送信機に許されるビッ
トの最大数がウィンドサイズと呼ばれ、ここではＷで表
示される。発行シーケンスの最大数が、ウィンドサイズ
と呼ばれる場合もあるが、ここではそのようには使用し
ない。
ここでは送信機と受信機を、次のような回線により接続
するとする。毎秒Ｓビットのスピード、ラウンド・トリ
ップ伝搬時間Ｔ。秒であって、Ｓ以上の速度でデータを
送受できるとする。Ｗをウィンドサイズとする。他の場
合にアイドル状態のパスに連続して伝送を保持するには
、Ｗは少なくともラウンド・トリップＷ。の大きさでな
ければならない。ここでＷｏはＷ ｏ ”” Ｓ Ｔ
ｏにより与えられる。Ｗｏは遅延バンド幅積と呼ばれる
場合がある。スピードが異なる多数のリンクを通る回線
の場合、Ｓは最も遅いリンクのスピードを表わす。
するとする。毎秒Ｓビットのスピード、ラウンド・トリ
ップ伝搬時間Ｔ。秒であって、Ｓ以上の速度でデータを
送受できるとする。Ｗをウィンドサイズとする。他の場
合にアイドル状態のパスに連続して伝送を保持するには
、Ｗは少なくともラウンド・トリップＷ。の大きさでな
ければならない。ここでＷｏはＷ ｏ ”” Ｓ Ｔ
ｏにより与えられる。Ｗｏは遅延バンド幅積と呼ばれる
場合がある。スピードが異なる多数のリンクを通る回線
の場合、Ｓは最も遅いリンクのスピードを表わす。
もし、ウィンドがラウンド・トリップ未満のウィンドの
場合、回線のとるネットワーク・バンド幅の平均部分は
Ｗ／ＷＯを超えることはできない。
場合、回線のとるネットワーク・バンド幅の平均部分は
Ｗ／ＷＯを超えることはできない。
原則的には、回線が所定のウィンドを有する場合、どん
な場合でもパケットを失わぬためには、全ウィンドを記
憶するに適したバッファスペースが各キューイング点で
可能でなければならない。
な場合でもパケットを失わぬためには、全ウィンドを記
憶するに適したバッファスペースが各キューイング点で
可能でなければならない。
というのは、順進行はどのリンクも初めは瞬間的には停
止となりうるからである。このことは以下に詳しく説明
する。負荷の軽いネットワークの場合、目立った遅延は
起こり憎く、回線間のバッファスペースを共有できるの
が一般的である。しかし、通信網がふくそうする場合に
は状況は変わる。
止となりうるからである。このことは以下に詳しく説明
する。負荷の軽いネットワークの場合、目立った遅延は
起こり憎く、回線間のバッファスペースを共有できるの
が一般的である。しかし、通信網がふくそうする場合に
は状況は変わる。
ふくそうとは、各回線が全てフロー制御されているにも
拘らず、高密度なトラフィックが通信網に流入した場合
をいう。無制御ふくそうは、バッファのオーバーフロー
、もしくは長い遅延によるデータロスとなり、センダは
ロスと解釈してしまう。
拘らず、高密度なトラフィックが通信網に流入した場合
をいう。無制御ふくそうは、バッファのオーバーフロー
、もしくは長い遅延によるデータロスとなり、センダは
ロスと解釈してしまう。
このロスが再伝送のトリガとなり、扱う負荷の増加と共
に通信網の処理能力が低下する不安定状態となる。デー
タを再伝送しなければならない場合は、いつも、元のデ
ータを伝送するのに使用された通信網容量の一部がロス
となるため、ふくそう不安定状態となる。極端な場合は
、ふくそう通信網はデッドロックとなり、再スタートし
なければならなくなる。
に通信網の処理能力が低下する不安定状態となる。デー
タを再伝送しなければならない場合は、いつも、元のデ
ータを伝送するのに使用された通信網容量の一部がロス
となるため、ふくそう不安定状態となる。極端な場合は
、ふくそう通信網はデッドロックとなり、再スタートし
なければならなくなる。
このふくそう制御方法は、タネンボームの前記豊中２８
７−２８８頁と３０９−３２０頁に概説されている。こ
のふくそう制御方法は、通信網ふくそうの始まりを感知
しようとする試みと共に、バッファスペースを統計的に
共用しようとするものが多い。ふくそうの始まりを検出
すると、通信網へのデータの入力と、フローダウンする
ようホストに要求する試みがなされる。これらの方法は
特に、ふくそう不安定となるものである。不良ホストは
データを提供し続け、バッファのオーバーフローを引き
起こす。オーバーフローを引き起こすパケットを提供す
るホストのみならず、他のホストが、次にパケットを失
う全てのユーザからの再伝送の要求となるが、通信網を
不安定状態にし、デッドロックとするのはこの影響から
である。代わって、上記のようにデータロスによるふく
そう不安定状態は、次の場合、仮想回線通信網では起き
ないということが長く認められてきた。即ち、メモリの
全ウィンドウを、各キューイングノードで各仮想回線に
配分する、及びセンダがタイムアウトすると、自動的に
再伝送としないで、まず照会メツセージを出して、正常
に受信された最後のフレームを求める場合である。もし
各回線に全バッファを配分することと、本質的に公平な
キューイング統制、即ちラウントロピンのある変形とを
組合わせると、通信網は安定となり、所定の負荷の下で
取り得るだけ公平となる。
７−２８８頁と３０９−３２０頁に概説されている。こ
のふくそう制御方法は、通信網ふくそうの始まりを感知
しようとする試みと共に、バッファスペースを統計的に
共用しようとするものが多い。ふくそうの始まりを検出
すると、通信網へのデータの入力と、フローダウンする
ようホストに要求する試みがなされる。これらの方法は
特に、ふくそう不安定となるものである。不良ホストは
データを提供し続け、バッファのオーバーフローを引き
起こす。オーバーフローを引き起こすパケットを提供す
るホストのみならず、他のホストが、次にパケットを失
う全てのユーザからの再伝送の要求となるが、通信網を
不安定状態にし、デッドロックとするのはこの影響から
である。代わって、上記のようにデータロスによるふく
そう不安定状態は、次の場合、仮想回線通信網では起き
ないということが長く認められてきた。即ち、メモリの
全ウィンドウを、各キューイングノードで各仮想回線に
配分する、及びセンダがタイムアウトすると、自動的に
再伝送としないで、まず照会メツセージを出して、正常
に受信された最後のフレームを求める場合である。もし
各回線に全バッファを配分することと、本質的に公平な
キューイング統制、即ちラウントロピンのある変形とを
組合わせると、通信網は安定となり、所定の負荷の下で
取り得るだけ公平となる。
データキット（ＤＡＴＡＫＩ７登録商品名）通信網は、
ＡＴ＆Ｔにより市場に出されている仮想回線通信網であ
る。これは比較的低い伝送速度で動作し、今述べたよう
に、各仮想回線に全ウィンドバッフ７リングを供与する
ものである。この通信網は米国特許Ｒｅ第３１．３１９
号に開示の方法と類似の方法を用いる。これは米国特許
箱３，７４９゜８４５号、エイ・ジー・フレーザー（Ａ
、Ｇ、 Ｆｒａｓｅｒ）、１９７３年７月３１日、０１
９８３年７月１９日再発行のもので、比較的低速Ｔ１チ
ャネル上、毎秒約１．５メガビツトで動作する。このデ
ータキッド通信網は、次の理由から通信網不安定状態と
はならない。それは各仮想回線に対する全ウィンドバッ
ファリングであり、１つのホストのデータロスは、他の
ユーザのデータロスを引き起こさないためである。専用
全ウィンバッファリングはこのような低速チャネルには
適している。しがしデータウィンドのサイズが毎秒１．
５メガビツト超過の高速で急増している。これは光フア
イバ伝送に使用のような場合である。Ｎをノードにおけ
る同時にアクティブな仮想回線の最大数とすると、各回
線にラウンドトリップウィンドを与えるのに必要な総バ
ッファスペースはＮ５Ｔｏとなる。地理的に限られた低
速通信網の各ノードに、この量のメモリを供給すること
は実施可能である。しがし、ハイスピードと通信網サイ
ズによっては、各仮想回線に対し、メモリの全ラウンド
トリップウィンドを専用実施することは、最終的には行
うことができない。例えば６０ＩＩｌｓの公称大陸横断
パケット・ラウンド・トリップ・伝搬時間を仮定すると
、毎秒１．５メガビツトの伝送速度に対し、各交換ノー
ドで各回線には、１１キロバイトのバッファメモリが必
要である。これは毎秒４５メガビツトの速度では３３８
キロバイトに増加する。
ＡＴ＆Ｔにより市場に出されている仮想回線通信網であ
る。これは比較的低い伝送速度で動作し、今述べたよう
に、各仮想回線に全ウィンドバッフ７リングを供与する
ものである。この通信網は米国特許Ｒｅ第３１．３１９
号に開示の方法と類似の方法を用いる。これは米国特許
箱３，７４９゜８４５号、エイ・ジー・フレーザー（Ａ
、Ｇ、 Ｆｒａｓｅｒ）、１９７３年７月３１日、０１
９８３年７月１９日再発行のもので、比較的低速Ｔ１チ
ャネル上、毎秒約１．５メガビツトで動作する。このデ
ータキッド通信網は、次の理由から通信網不安定状態と
はならない。それは各仮想回線に対する全ウィンドバッ
ファリングであり、１つのホストのデータロスは、他の
ユーザのデータロスを引き起こさないためである。専用
全ウィンバッファリングはこのような低速チャネルには
適している。しがしデータウィンドのサイズが毎秒１．
５メガビツト超過の高速で急増している。これは光フア
イバ伝送に使用のような場合である。Ｎをノードにおけ
る同時にアクティブな仮想回線の最大数とすると、各回
線にラウンドトリップウィンドを与えるのに必要な総バ
ッファスペースはＮ５Ｔｏとなる。地理的に限られた低
速通信網の各ノードに、この量のメモリを供給すること
は実施可能である。しがし、ハイスピードと通信網サイ
ズによっては、各仮想回線に対し、メモリの全ラウンド
トリップウィンドを専用実施することは、最終的には行
うことができない。例えば６０ＩＩｌｓの公称大陸横断
パケット・ラウンド・トリップ・伝搬時間を仮定すると
、毎秒１．５メガビツトの伝送速度に対し、各交換ノー
ドで各回線には、１１キロバイトのバッファメモリが必
要である。これは毎秒４５メガビツトの速度では３３８
キロバイトに増加する。
以上の従来知られた技術におけるふくそう不安定状態を
回避する課題と、同じく増加し始めたバッファメモリの
要求を回避する課題に対する解決の要望がある。そこで
、本発明の目的は、全ウィンドバッフ７リングの利点を
保持する一方で、必要とするメモリ総量を節減すること
である。
回避する課題と、同じく増加し始めたバッファメモリの
要求を回避する課題に対する解決の要望がある。そこで
、本発明の目的は、全ウィンドバッフ７リングの利点を
保持する一方で、必要とするメモリ総量を節減すること
である。
本発明の他の目的は、回線間のバッファメモリの共用と
回線に対するウィンドサイズを、ダイナミック調節する
ことにより、各回線に対し、必要とするバッファリング
量を節減することである。
回線に対するウィンドサイズを、ダイナミック調節する
ことにより、各回線に対し、必要とするバッファリング
量を節減することである。
米国特許箱４，７３６，３６９号、ブラシー（Ｂｒａｚ
ｉｌａｌ）ら、はトラフィックパターンの変化トハッフ
ァの可能性に応じ、ユーザセツションとの経路の間にウ
ィンドサイズを、ダイナミックに調節する問題について
、幾つかの特徴を述べている。ところが、この特許はフ
ロー制御とウィンド調節をリンクバイリンクに実施する
ことに基づく通信網を想定している。即ち、送信機と受
信機の間のバス上の隣接するノードの各ベア間の、個別
交渉の結果としてのものを想定している。高速通信網に
対しては、リンクバイリンクのフロー制御が次の理由か
らエンドツウェンド制御より適切さの点で劣ると一般に
考えられている。それはリンクバイリンク制御は通信網
ノード上に、さらに演算上の負荷を追加するためと考え
られている。
ｉｌａｌ）ら、はトラフィックパターンの変化トハッフ
ァの可能性に応じ、ユーザセツションとの経路の間にウ
ィンドサイズを、ダイナミックに調節する問題について
、幾つかの特徴を述べている。ところが、この特許はフ
ロー制御とウィンド調節をリンクバイリンクに実施する
ことに基づく通信網を想定している。即ち、送信機と受
信機の間のバス上の隣接するノードの各ベア間の、個別
交渉の結果としてのものを想定している。高速通信網に
対しては、リンクバイリンクのフロー制御が次の理由か
らエンドツウェンド制御より適切さの点で劣ると一般に
考えられている。それはリンクバイリンク制御は通信網
ノード上に、さらに演算上の負荷を追加するためと考え
られている。
このことから、本発明のさらに他の目的は、ダイナミッ
クに調節するウィンドにエンドツウェンドに基づいてフ
ロー制御を実施することである。
クに調節するウィンドにエンドツウェンドに基づいてフ
ロー制御を実施することである。
（発明の概要）
本発明は１つ以上のノードを有し、データセルが仮想回
線を経由して転送される通信網において、データセルの
ふくそうを制御する方法である。
線を経由して転送される通信網において、データセルの
ふくそうを制御する方法である。
本方法は次のステップを有する。即ち、通信網において
仮想回線が形成されると、各ノードにおいて仮想回線に
対し、デフォルトセルバッファを割当てるステップ、及
び 仮想回線の間中の次の実施ステップである。即ち、サイ
ズの異なるセルバッファが必要かどうかを仮想回線の挙
動から決定するステップ；もしサイズの異なるセルバッ
ファを必要とする場合、仮想回線のノードに異なるサイ
ズを示す第１の再サイジング信号を与えるステ・ツブ；
仮想回線の各ノードにおいて、 もしサイズがその異なるサイズより小さい場合、ノード
が与えることのできるバッファサイズを示すことにより
、第１の再サイジング信号に応答するステップ；及び 仮想回線の各ノードにおいて、 いずれかのノードにより指示される最小バッファサイズ
以下のサイズに仮想回線に対するセルバッファをセット
するステップである。
仮想回線が形成されると、各ノードにおいて仮想回線に
対し、デフォルトセルバッファを割当てるステップ、及
び 仮想回線の間中の次の実施ステップである。即ち、サイ
ズの異なるセルバッファが必要かどうかを仮想回線の挙
動から決定するステップ；もしサイズの異なるセルバッ
ファを必要とする場合、仮想回線のノードに異なるサイ
ズを示す第１の再サイジング信号を与えるステ・ツブ；
仮想回線の各ノードにおいて、 もしサイズがその異なるサイズより小さい場合、ノード
が与えることのできるバッファサイズを示すことにより
、第１の再サイジング信号に応答するステップ；及び 仮想回線の各ノードにおいて、 いずれかのノードにより指示される最小バッファサイズ
以下のサイズに仮想回線に対するセルバッファをセット
するステップである。
本発明は次の他の特徴を有する。即ち、セルバッファサ
イズを決める方法、 要求されるセルバッファサイズを決める方法、及び ノードが与えることのできるセルバッファサイズを決め
る方法と、 ノードが与えることのできるセルバッファサイズを決め
る方法は次の定数りを有する。これは次式より導かれる
。
イズを決める方法、 要求されるセルバッファサイズを決める方法、及び ノードが与えることのできるセルバッファサイズを決め
る方法と、 ノードが与えることのできるセルバッファサイズを決め
る方法は次の定数りを有する。これは次式より導かれる
。
再ネゴシェーション間隔−ｈτ
ここで、τは通信網における最長ラウンドトリップ時間
であり、再ネゴシェーション間隔は、時間の間隔であっ
て、この後、仮想回線のセルバッファの再サイジングが
自動的に再考される。
であり、再ネゴシェーション間隔は、時間の間隔であっ
て、この後、仮想回線のセルバッファの再サイジングが
自動的に再考される。
［実施例の説明コ
図１は、パケット交換通信網を説明するブロックダイア
グラムを示す図である。通信網は多数のパケットのソー
スと、行き先を多数のルータと交換ノードを介して、仮
想回線により相互接続すると想定する。パケットのソー
スと行き先は、ユーザサイト側にあるローカルエリア通
信網に付随する。例えば、ソース１０２は、ローカルエ
リア通信網１０６に接続され、これはルータ１１０に接
続される。ルータの有する機能の１つは、ソースにより
発行される可変長のデータパケットと、セル通信網１１
０により伝送され、交換される一定長データセルの間を
変換することで考えられるが、これか本発明を限定する
ものではない。本発明に関するルータの、他の機能は以
下に説明する。
グラムを示す図である。通信網は多数のパケットのソー
スと、行き先を多数のルータと交換ノードを介して、仮
想回線により相互接続すると想定する。パケットのソー
スと行き先は、ユーザサイト側にあるローカルエリア通
信網に付随する。例えば、ソース１０２は、ローカルエ
リア通信網１０６に接続され、これはルータ１１０に接
続される。ルータの有する機能の１つは、ソースにより
発行される可変長のデータパケットと、セル通信網１１
０により伝送され、交換される一定長データセルの間を
変換することで考えられるが、これか本発明を限定する
ものではない。本発明に関するルータの、他の機能は以
下に説明する。
ルータは、ローカル通信網１０６をアクセス線路１０８
を経てセル通信網１００へ接続する。特定の仮想回線に
属するデータセルは、一連の交換ノード１１４とデータ
リンク１１６を通り、ルータ１２０に接続するアクセス
線路１１８に伝送される。ルータ１２０は、特定の行き
先にアドレスされたデータパケットに、データセルを再
アッセンブルし、パケットをローカル通信網１２４に（
ケラトを伝送し、そこから行き先１２８に送られる。
を経てセル通信網１００へ接続する。特定の仮想回線に
属するデータセルは、一連の交換ノード１１４とデータ
リンク１１６を通り、ルータ１２０に接続するアクセス
線路１１８に伝送される。ルータ１２０は、特定の行き
先にアドレスされたデータパケットに、データセルを再
アッセンブルし、パケットをローカル通信網１２４に（
ケラトを伝送し、そこから行き先１２８に送られる。
本発明の開示のために、通信網１００はかなり高い伝送
速度で動作する点景外、通信網１００は、ＡＴ＆Ｔ社よ
り市場に出されているデータキ・ソト仮想回線通信網に
類似のものであると仮定する。
速度で動作する点景外、通信網１００は、ＡＴ＆Ｔ社よ
り市場に出されているデータキ・ソト仮想回線通信網に
類似のものであると仮定する。
即ち、接続が初めに開始されるときに、通信網１００は
選択した交換ノード１１４を経由するソースルータと、
行き先ルータ間の仮想回線パスを形成すると仮定する。
選択した交換ノード１１４を経由するソースルータと、
行き先ルータ間の仮想回線パスを形成すると仮定する。
接続が続いている間、パケットはソースから行き先に仮
想回線を通って送られる。しかし、このバスにおいて、
実際の伝送線路と伝送線路上のバンド幅は問題として、
今取り上げている接続に専用のものではなく、これはこ
のような多くの接続の中で時分割することができる。
想回線を通って送られる。しかし、このバスにおいて、
実際の伝送線路と伝送線路上のバンド幅は問題として、
今取り上げている接続に専用のものではなく、これはこ
のような多くの接続の中で時分割することができる。
図２は、本発明のノードにおけるセルバッファリング装
置の実施例を説明する図である。このセルバッファリン
グ装置は、多くの仮想回線を取り扱うことができる。バ
ッファスペースは、仮想回線当りに配分され、この仮想
回線の配分は、モニタ２００の制御でダイナミックに変
えることができる。このモニタは、通常のマイクロプロ
セッサシステムであって、以下に述べるふくそう制御機
構の実施に用いることができるものである。図中の受信
機２０２と送信機２０４は通常のものであって、送信機
は既知の方法を用いて仮想回線中ラウントロピンサービ
スを実施できる。
置の実施例を説明する図である。このセルバッファリン
グ装置は、多くの仮想回線を取り扱うことができる。バ
ッファスペースは、仮想回線当りに配分され、この仮想
回線の配分は、モニタ２００の制御でダイナミックに変
えることができる。このモニタは、通常のマイクロプロ
セッサシステムであって、以下に述べるふくそう制御機
構の実施に用いることができるものである。図中の受信
機２０２と送信機２０４は通常のものであって、送信機
は既知の方法を用いて仮想回線中ラウントロピンサービ
スを実施できる。
セルが到着すると、受信機２０２はセルがベツダにおけ
るビットで示されるように、ふくそうメツセージである
かどうかを決める。ふくそうメツセージは、モニタに対
する別のＦＩＦＯキュー２０６に記憶される。到着セル
がふくそうメツセージでない場合、受信機２０２はバス
ＷＶＣ上に仮想回線番号を、及びラインＷＲＥＱ上に書
き込み要求を形成する。受信機は、セルをその出力バス
２０８に送り、そこでコントローラ２１２の制御下のセ
ルキュー２１０でバッファに入れられる。
るビットで示されるように、ふくそうメツセージである
かどうかを決める。ふくそうメツセージは、モニタに対
する別のＦＩＦＯキュー２０６に記憶される。到着セル
がふくそうメツセージでない場合、受信機２０２はバス
ＷＶＣ上に仮想回線番号を、及びラインＷＲＥＱ上に書
き込み要求を形成する。受信機は、セルをその出力バス
２０８に送り、そこでコントローラ２１２の制御下のセ
ルキュー２１０でバッファに入れられる。
このセルキュー２１０はある適当なサイズのメモリアレ
ーであって、ここでは説明のために１つのセルの幅を持
ったワードで構成される。
ーであって、ここでは説明のために１つのセルの幅を持
ったワードで構成される。
受信機２０２と送信機２０４は独立回線である。
それぞれが他と独立してセルキュー２１０に入れたり、
そこからセルを取り出したりする。送信機２０４がセル
を送ろうとする場合、バスＲＶＣ上に仮想回線番号を、
そしてラインＲＲＥＱ上に読みだし要求を形成する。仮
想回線ＲＶＣに関するキュー２１０における配分バッフ
ァが空の場合、コントローラ２１２は、信号ＥＭＰＴＹ
をＴＲＵＥ値にセットすることにより、この状態を表わ
し、送信機は別の仮想回線を試行することができる。
そこからセルを取り出したりする。送信機２０４がセル
を送ろうとする場合、バスＲＶＣ上に仮想回線番号を、
そしてラインＲＲＥＱ上に読みだし要求を形成する。仮
想回線ＲＶＣに関するキュー２１０における配分バッフ
ァが空の場合、コントローラ２１２は、信号ＥＭＰＴＹ
をＴＲＵＥ値にセットすることにより、この状態を表わ
し、送信機は別の仮想回線を試行することができる。
さもなければ、ＲＶＣに関するバッファの次のセルが出
力バス上に送られ、送信機２０４により読み取られるこ
ととなる。コントローラ２１２は、バス上にＭＡ Ｄ
Ｄ Ｒ，ライン上にＭＷとＭＲの信号を介してセルキュ
ーを制御する。ＭＡＤＤＲはセルキュー２１０における
アドレスであって、それに対して次のセルが書き込まれ
たり、もしくは読み取られたりする。ＭＷＳＭＲはそれ
ぞれキュー書き込み、もしくは読取りの動作を表わす。
力バス上に送られ、送信機２０４により読み取られるこ
ととなる。コントローラ２１２は、バス上にＭＡ Ｄ
Ｄ Ｒ，ライン上にＭＷとＭＲの信号を介してセルキュ
ーを制御する。ＭＡＤＤＲはセルキュー２１０における
アドレスであって、それに対して次のセルが書き込まれ
たり、もしくは読み取られたりする。ＭＷＳＭＲはそれ
ぞれキュー書き込み、もしくは読取りの動作を表わす。
モニタ２００により生成されるふくそうメツセージは、
別の出力ＦＩＦＯ２１４に記憶される。これらのメツセ
ージは送信機により伝送線路２１６上出力され、多重化
される。
別の出力ＦＩＦＯ２１４に記憶される。これらのメツセ
ージは送信機により伝送線路２１６上出力され、多重化
される。
ふくそう制御方法を実施するために、モニタ２００はバ
スＡＤＤＲＳＲＳＷ及びＤＡＴＡでコントローラ２１２
に対するデータ構造にアクセスする内部構造を有する。
スＡＤＤＲＳＲＳＷ及びＤＡＴＡでコントローラ２１２
に対するデータ構造にアクセスする内部構造を有する。
これらのデータ構造は、各仮想回線に対する瞬間的バッ
ファ長とセルキューにおけるセルの全数を含む。以下に
述べるプロトコルにより、ふくそう制御を行うのに要す
る平均化動作はモニタ２００により行われる。
ファ長とセルキューにおけるセルの全数を含む。以下に
述べるプロトコルにより、ふくそう制御を行うのに要す
る平均化動作はモニタ２００により行われる。
図３は、図２のコントローラ２１２の詳細を示す説明図
である。コントローラの主要な働きは、次の通りである
。即ち、各仮想回線に対するバッファ配分を見失わぬよ
う接触を保つこと、各仮想回線に対する瞬間的バッファ
使用（バッファ長）を見失わぬよう接触を保つこと、次
のようにセルキューにおけるメモリの配分を管理するこ
と、即ち、ダイナミックに長さの変わる専用バッファに
おいて、各仮想回線に対し、データをバッファ内に入れ
ることができるように管理すること、及びセルキュ〜に
おけるデータの読取りと書き込みをそれが受信され、ま
たは送信することを制御することである。説明上、メモ
リは１つのセルの単位チー＋ニーにおいて区分けされる
。このセクションはコントローラの基礎エレメントをま
ず記述し、次に詳細にこれらのエレメントの動作を記述
する。
である。コントローラの主要な働きは、次の通りである
。即ち、各仮想回線に対するバッファ配分を見失わぬよ
う接触を保つこと、各仮想回線に対する瞬間的バッファ
使用（バッファ長）を見失わぬよう接触を保つこと、次
のようにセルキューにおけるメモリの配分を管理するこ
と、即ち、ダイナミックに長さの変わる専用バッファに
おいて、各仮想回線に対し、データをバッファ内に入れ
ることができるように管理すること、及びセルキュ〜に
おけるデータの読取りと書き込みをそれが受信され、ま
たは送信することを制御することである。説明上、メモ
リは１つのセルの単位チー＋ニーにおいて区分けされる
。このセクションはコントローラの基礎エレメントをま
ず記述し、次に詳細にこれらのエレメントの動作を記述
する。
アービタ３００は、次の要求の信号ＷＲＥＱとＲＲＥＱ
を受信する。即ち、それぞれ特定の仮想回線に関連する
バッファにセルの書き込ろを行う要求、または特定の仮
想回線に関連するバッファからセルを読取りを行う要求
である。アービタは次のことを保証する。即ち、書き込
み動作と、読取り動作が妨害されることなく行われるこ
と、及びマルチプレクサ（Ｗ−ＯＲ−Ｒ）への選択人力
が次のようにセットされること、即ち、読取り動作中入
力ＲＶＣがバスＶＣ上にあること、及び書き込み動作中
、入力ＷｖＣがバスＶＣ上にあることである。この説明
の残りとして、書き込み動作と読取り動作を別々に説明
する。
を受信する。即ち、それぞれ特定の仮想回線に関連する
バッファにセルの書き込ろを行う要求、または特定の仮
想回線に関連するバッファからセルを読取りを行う要求
である。アービタは次のことを保証する。即ち、書き込
み動作と、読取り動作が妨害されることなく行われるこ
と、及びマルチプレクサ（Ｗ−ＯＲ−Ｒ）への選択人力
が次のようにセットされること、即ち、読取り動作中入
力ＲＶＣがバスＶＣ上にあること、及び書き込み動作中
、入力ＷｖＣがバスＶＣ上にあることである。この説明
の残りとして、書き込み動作と読取り動作を別々に説明
する。
テーブルｃＯＵＮＴ ＴＡＢＬＥ３０４を設ケ、各仮
想回線に対しバッファ配分と、バッファ使用を記憶する
。このテーブルはマルチプレクサ３゜２からのバスＶＣ
上の（ｌｉ２想回線番号でアドレスされる。各仮想回線
はＣ０ＵＮＴ ＴＡＢＬＥに２つのエントリを有する
。１つのエントリはＬＩＭＩＴ［ＶＣ］で仮想回線ＶＣ
で現時点でバッファに入れられ得るデータのセルの最大
数を有する。
想回線に対しバッファ配分と、バッファ使用を記憶する
。このテーブルはマルチプレクサ３゜２からのバスＶＣ
上の（ｌｉ２想回線番号でアドレスされる。各仮想回線
はＣ０ＵＮＴ ＴＡＢＬＥに２つのエントリを有する
。１つのエントリはＬＩＭＩＴ［ＶＣ］で仮想回線ＶＣ
で現時点でバッファに入れられ得るデータのセルの最大
数を有する。
これが次の仮想回線に配分されるウィンドサイズを決め
る。第２のエントリはＣ０ＵＮＴ ［ＶＣ］であって、
仮想回線ＶＣによりセルキュー２１０において、現時点
で用いられるセルの数を有する。
る。第２のエントリはＣ０ＵＮＴ ［ＶＣ］であって、
仮想回線ＶＣによりセルキュー２１０において、現時点
で用いられるセルの数を有する。
Ｃ０ＵＮＴ ＴＡＢＬＥの内容はコントローラ２１２
の動作前、または動作中、いつでもモニタ２００により
読取りでき、もしくは書き込みができる。
の動作前、または動作中、いつでもモニタ２００により
読取りでき、もしくは書き込みができる。
テーブルＱＵＥＵＥ、ＰＯＩＴＥＲ３０６は各仮想回線
に関連するバッファの読取りポインタと書き込みポイン
タを有する。読取りポインタＲＰ［ＶＣ］は仮想回線Ｖ
Ｃに関連するバッファから読取る次のセルを含有する場
所を示す。一方、書き込みポインタＷＰ ［ＶＣ］は仮
想回線ＶＣに関連するバッファに書き込まれる次の場所
を示す。
に関連するバッファの読取りポインタと書き込みポイン
タを有する。読取りポインタＲＰ［ＶＣ］は仮想回線Ｖ
Ｃに関連するバッファから読取る次のセルを含有する場
所を示す。一方、書き込みポインタＷＰ ［ＶＣ］は仮
想回線ＶＣに関連するバッファに書き込まれる次の場所
を示す。
ダイナミックに変わる長さのバッファは、各仮想回線に
対するセルのリンクされたリストを保つことにより保持
される。このリンクされたリストはＬＩＳＴ ＭＡＮ
ＡＧＥＲ３０８により保持される。これはまたフリーバ
ッファスペースを形成する未使用セルのリンクされたリ
ストを保持する。
対するセルのリンクされたリストを保つことにより保持
される。このリンクされたリストはＬＩＳＴ ＭＡＮ
ＡＧＥＲ３０８により保持される。これはまたフリーバ
ッファスペースを形成する未使用セルのリンクされたリ
ストを保持する。
ＬＩＳＴ ＭＡＮＡＧＥＲの動作を以下に述べる。
ＧＬＯＢＡＬ Ｃ０ＵＮＴレジスト３１０は、全ての
仮想回線バッファにおけるセル総数を見失わぬよう接触
を保つ。もし各仮想回線がそのバッファ内で１つの（未
使用の）セルより開始される場合、ＧＬＯＢＡＬ Ｃ
０ＵＮＴレジスタの初期値は仮想回線の数に等しい。こ
のＧＬＯＢＡＬＣＯＵＮＴレジスタはモニタにより書き
込み、もしくは読取りが行われる。Ｔ ＩＭＩＮＧ＋Ｃ
０ＮＴＲ０Ｌ回線３１２は、コントローラを作動するの
に必要な全ての制御信号を供給する。
仮想回線バッファにおけるセル総数を見失わぬよう接触
を保つ。もし各仮想回線がそのバッファ内で１つの（未
使用の）セルより開始される場合、ＧＬＯＢＡＬ Ｃ
０ＵＮＴレジスタの初期値は仮想回線の数に等しい。こ
のＧＬＯＢＡＬＣＯＵＮＴレジスタはモニタにより書き
込み、もしくは読取りが行われる。Ｔ ＩＭＩＮＧ＋Ｃ
０ＮＴＲ０Ｌ回線３１２は、コントローラを作動するの
に必要な全ての制御信号を供給する。
読みだし要求動作、もしくは書き込み要求動作の開始に
先立って、コントローラはモニタにより初期化される。
先立って、コントローラはモニタにより初期化される。
各仮想回線に対し、ＷＰ ［ＶＣ］とＲＰ ［ＶＣ］は
特定セル番号により初期化され、Ｃ０ＵＮＴ ［ＶＣ］
は１の値に初期化される。これは１つの（未使用の）セ
ルを有する空のバッファが入力データの受入に対して存
在することを表わす。ＬＩＭＩＴ ［ＶＣ］の初期値は
、その仮想回線に対する初期バッファ配分であり、これ
はその初期ウィンドサイズに等しい。ＬＩＳＴ ＭＡ
ＮＡＧＥＲは次のように初期化される。即ち、フリーリ
ストは、セルキュー２１０における全てのセルを含むリ
ンクされたリストであるが、但しテーブルＱＵＥＵＥ
ＰＯＩＮＴＥＲにおいて初期化されたものを除く。
特定セル番号により初期化され、Ｃ０ＵＮＴ ［ＶＣ］
は１の値に初期化される。これは１つの（未使用の）セ
ルを有する空のバッファが入力データの受入に対して存
在することを表わす。ＬＩＭＩＴ ［ＶＣ］の初期値は
、その仮想回線に対する初期バッファ配分であり、これ
はその初期ウィンドサイズに等しい。ＬＩＳＴ ＭＡ
ＮＡＧＥＲは次のように初期化される。即ち、フリーリ
ストは、セルキュー２１０における全てのセルを含むリ
ンクされたリストであるが、但しテーブルＱＵＥＵＥ
ＰＯＩＮＴＥＲにおいて初期化されたものを除く。
セルが到若すると、受信機はＷＲＥＱに書き込み要求を
表明し、ＷＶＣに仮想回線番号の要求を表明する。バス
ＶＣを用いてＣ０ＵＮＴ ＴＡＢＬＥにアドレスし、
Ｃ０ＵＮＴ ［ＶＣ］ とＬＩＭＩＴ ［ＶＣ］ フィ
ールドにおける値とコンパレータ３１４に送出せしめる
。もし問題としている仮想回線がセルキューにおいて、
その配分スペースの全てを消費しなかった場合、即ち、
テーブルにおいて、Ｃ０ＵＮＴ ［ＶＣ］がＬＩＭＩＴ
［ＶＣ］未満である場合、コンパレータはラインＬ Ｉ
Ｍ ＩＴＲＥＡＣＨＥＤにＦＡＬＳＥ値を生成する。
表明し、ＷＶＣに仮想回線番号の要求を表明する。バス
ＶＣを用いてＣ０ＵＮＴ ＴＡＢＬＥにアドレスし、
Ｃ０ＵＮＴ ［ＶＣ］ とＬＩＭＩＴ ［ＶＣ］ フィ
ールドにおける値とコンパレータ３１４に送出せしめる
。もし問題としている仮想回線がセルキューにおいて、
その配分スペースの全てを消費しなかった場合、即ち、
テーブルにおいて、Ｃ０ＵＮＴ ［ＶＣ］がＬＩＭＩＴ
［ＶＣ］未満である場合、コンパレータはラインＬ Ｉ
Ｍ ＩＴＲＥＡＣＨＥＤにＦＡＬＳＥ値を生成する。
バスＶＣを用いてＷＰ ［ＶＣ］がバスＭＡＤＤＲにあ
るようにＱＵＥＵＥ ＰＯＩＮＴＥＲＳテーブルにア
ドレスする。Ｌ ＩＭＩＴＲＥＡＣＨＥＤがＦＡＬＳＥ
である場合、タイミングと制御回線は信号ＭＷを生成す
る。これはセルにセルキュー２１０に書き込みを行わせ
、そして、ＬＩＳＴ ＭＡＮＡＧＥＲを制御してＶＣ
に関連するバッファに新しいセルを配分せしめリンクさ
せる。さらに、ＶＣに対するバッファの使用と、全セル
カウント値が更新される。バッファの使用を更新するた
めに、Ｃ０ＵＮＴ ［ＶＣ］における現在の値はバスＣ
０ＵＮＴを経由して、アップ／ダウンカウンタに送られ
る。そしてＣ０ＵＮＴ ［ＶＣ］において記録されたセ
ルの現在数を１つだけ増加する。バスＮＣ０ＵＮＴに現
れるこの新しい値が、Ｃ０ＵＮＴ ＴＡＢＬＥの入力
としてテーブルに書き込まれる。全セルカウントは同じ
ようにレジスタＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０とア
ップ／ダウンカウンタ３１６を用いて増加される。
るようにＱＵＥＵＥ ＰＯＩＮＴＥＲＳテーブルにア
ドレスする。Ｌ ＩＭＩＴＲＥＡＣＨＥＤがＦＡＬＳＥ
である場合、タイミングと制御回線は信号ＭＷを生成す
る。これはセルにセルキュー２１０に書き込みを行わせ
、そして、ＬＩＳＴ ＭＡＮＡＧＥＲを制御してＶＣ
に関連するバッファに新しいセルを配分せしめリンクさ
せる。さらに、ＶＣに対するバッファの使用と、全セル
カウント値が更新される。バッファの使用を更新するた
めに、Ｃ０ＵＮＴ ［ＶＣ］における現在の値はバスＣ
０ＵＮＴを経由して、アップ／ダウンカウンタに送られ
る。そしてＣ０ＵＮＴ ［ＶＣ］において記録されたセ
ルの現在数を１つだけ増加する。バスＮＣ０ＵＮＴに現
れるこの新しい値が、Ｃ０ＵＮＴ ＴＡＢＬＥの入力
としてテーブルに書き込まれる。全セルカウントは同じ
ようにレジスタＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０とア
ップ／ダウンカウンタ３１６を用いて増加される。
もし、書き込み動作中、ＬＩＭＩＴＲＥＡＣＨＥＤがＴ
ＲＵＥの場合、即ち、問題としている仮想回線が、セル
キューにおけるその配分スペース全てを消費した場合、
Ｔ＋Ｃ回線３１２はセルキューにデータを書き込み、新
しいセルを配分し、モしてＣ０ＵＮＴ ［ＶＣ］もしく
はＧＬＯＢＡＬＣＯＵＮＴの値を増加するための信号を
生成しない。従って、その割当られたウィンドサイズを
超過するＶＣはいずれも対応するセルを失うが、他の仮
想回線に対するデータは影を受けない。
ＲＵＥの場合、即ち、問題としている仮想回線が、セル
キューにおけるその配分スペース全てを消費した場合、
Ｔ＋Ｃ回線３１２はセルキューにデータを書き込み、新
しいセルを配分し、モしてＣ０ＵＮＴ ［ＶＣ］もしく
はＧＬＯＢＡＬＣＯＵＮＴの値を増加するための信号を
生成しない。従って、その割当られたウィンドサイズを
超過するＶＣはいずれも対応するセルを失うが、他の仮
想回線に対するデータは影を受けない。
送信機が新しいセルを送るとする場合、それはラインＲ
ＲＥＱに読取り要求と、バスＲＶＣに仮想回線番号要求
を表明する。Ｃ０ＵＮＴ ＴＡＢＬＥをアクセスして
Ｃ０ＵＮＴ ［ＶＣ］の値をコンパレータ３１８に送出
する。この第２の人力値はゼロである。ＶＣに関連する
バッファがデータを含まれない場合、コンパレータ３１
８はＴＲＵＥ信号をＥＰＤＴＹに生成し、そして動作は
ＴＩＭＩ ＮＧ＋Ｃ０ＮＴＲ０Ｌ回線３１２により終了
される。ＥＭＰＴＹがＦＡＬＳＥの場合、アップ／ダウ
ンカウンタ３２０はＣ０ＵＮＴ ［ＶＣ］の値を減算し
、そして、その結果の値をＣ０ＵＮＴＴＡＢＬＥ３０４
に書き込む。この場合、ＱＵＥＵＥ ＰＯＩＮＴＥＲ
ＳからのＲＰ ［ＶＣ］の値は、バスＭＡＤＤＲにあっ
てＭＲ倍信号生成され、セルキュー２１０からのセルを
読み取る。ＲＰ ［ＶＣ］はまたＬＩＳＴ ＭＡＮＡ
ＧＥＲ３０８に人力され、その結果、セルは配分を取り
止めフリーの記憶ｖｔ置に戻される６ＶＣに対するバッ
ファにおける次のセルのアドレスは、バスＮＲＰにあっ
て、ＱＵＥＵＥ ＰＯＩＮＴＥＲ５３０６に書き込ま
れる。ＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０に記憶された
、バッファ内に入れられたセルの全カウント値は減算さ
れる。
ＲＥＱに読取り要求と、バスＲＶＣに仮想回線番号要求
を表明する。Ｃ０ＵＮＴ ＴＡＢＬＥをアクセスして
Ｃ０ＵＮＴ ［ＶＣ］の値をコンパレータ３１８に送出
する。この第２の人力値はゼロである。ＶＣに関連する
バッファがデータを含まれない場合、コンパレータ３１
８はＴＲＵＥ信号をＥＰＤＴＹに生成し、そして動作は
ＴＩＭＩ ＮＧ＋Ｃ０ＮＴＲ０Ｌ回線３１２により終了
される。ＥＭＰＴＹがＦＡＬＳＥの場合、アップ／ダウ
ンカウンタ３２０はＣ０ＵＮＴ ［ＶＣ］の値を減算し
、そして、その結果の値をＣ０ＵＮＴＴＡＢＬＥ３０４
に書き込む。この場合、ＱＵＥＵＥ ＰＯＩＮＴＥＲ
ＳからのＲＰ ［ＶＣ］の値は、バスＭＡＤＤＲにあっ
てＭＲ倍信号生成され、セルキュー２１０からのセルを
読み取る。ＲＰ ［ＶＣ］はまたＬＩＳＴ ＭＡＮＡ
ＧＥＲ３０８に人力され、その結果、セルは配分を取り
止めフリーの記憶ｖｔ置に戻される６ＶＣに対するバッ
ファにおける次のセルのアドレスは、バスＮＲＰにあっ
て、ＱＵＥＵＥ ＰＯＩＮＴＥＲ５３０６に書き込ま
れる。ＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０に記憶された
、バッファ内に入れられたセルの全カウント値は減算さ
れる。
ＬＩＳＴ ＭＡＮＡＧＥＲ３０８は、各仮想回線に対
するセルバッファを形成するメモリ場所のリンクされた
リストを保持する。また、これはフリーリストを形成す
るメモリ場所のリンクされたリストを保持する。ＬＩＳ
Ｔ ＭＡＮＡＧＥＲ３０８は、リンクメモリＬＮＫＭ
ＥＭ３２２を有し、これはセルキュー２１０における各
セルに対する情報の１つのワードを含む。ＬＮＫＭＥＭ
３２２におけるワードの幅は、セルキュー２１０におけ
るセルの数の底２に対する対数である。レジスタ、ＦＲ
ＥＥ３２４があるが、これはフリーリストにおける第１
のエントリーに対するポインタを含む。
するセルバッファを形成するメモリ場所のリンクされた
リストを保持する。また、これはフリーリストを形成す
るメモリ場所のリンクされたリストを保持する。ＬＩＳ
Ｔ ＭＡＮＡＧＥＲ３０８は、リンクメモリＬＮＫＭ
ＥＭ３２２を有し、これはセルキュー２１０における各
セルに対する情報の１つのワードを含む。ＬＮＫＭＥＭ
３２２におけるワードの幅は、セルキュー２１０におけ
るセルの数の底２に対する対数である。レジスタ、ＦＲ
ＥＥ３２４があるが、これはフリーリストにおける第１
のエントリーに対するポインタを含む。
次に仮想回線ＶＣに対するバッファを説明する。
読取りポインタＲＰ ＣＶＣ］は、仮想回線ＶＣに対す
る次のセルが送信機により用意されているセルバッファ
の場所を指す。ＲＰ ［ＶＣ］は、セルキュー２１０等
から準備されている、次のセルのポインタを含むＬＮＫ
ＭＥＭ３２２における場所を指す。このように進行して
、１つがＬＮＫＭＥＭ３２２における場所に到着すると
、それがＷＰ ［ＶＣ］により指された同じ場所をポイ
ントする。セルキュー２１０におけるこの場所が、次の
セルがＶＣに対し到着できる未使用の場所である。
る次のセルが送信機により用意されているセルバッファ
の場所を指す。ＲＰ ［ＶＣ］は、セルキュー２１０等
から準備されている、次のセルのポインタを含むＬＮＫ
ＭＥＭ３２２における場所を指す。このように進行して
、１つがＬＮＫＭＥＭ３２２における場所に到着すると
、それがＷＰ ［ＶＣ］により指された同じ場所をポイ
ントする。セルキュー２１０におけるこの場所が、次の
セルがＶＣに対し到着できる未使用の場所である。
セルキュー２１０におけるフリースペースは、フリーリ
ストによってＬ Ｎ Ｋ Ｍ Ｅ Ｍ ３２２において
、見失わぬようあとを追う。フリーリストの開始は、レ
ジスタＦＲＥＥ３２４において保持される。これはいず
れの仮想回線に対するバッファ上にないセルキュー２１
０における場所を指す。ＦＲＥＥはＬＮＫＭＥＭ３２２
において、次のフリーセルへのポインタを含む場所を指
し、以下同様である。
ストによってＬ Ｎ Ｋ Ｍ Ｅ Ｍ ３２２において
、見失わぬようあとを追う。フリーリストの開始は、レ
ジスタＦＲＥＥ３２４において保持される。これはいず
れの仮想回線に対するバッファ上にないセルキュー２１
０における場所を指す。ＦＲＥＥはＬＮＫＭＥＭ３２２
において、次のフリーセルへのポインタを含む場所を指
し、以下同様である。
仮想回線ＶＣに対し書き込み要求が惹起するとき、もし
ＶＣがそのバッファ配分を超えなかった場合、新しいセ
ルは配分され、ＶＣに関連するバッファにリンクされる
。ＷＰ ［ＶＣ］における値が、動作の初めにバスＷＰ
上にあるＬＩＳＴ ＭＡＮＡＧＥＲ３０８に入力され
る。書き込みポイントの新しい値ＮＷＰは、動作の終り
にＬＩＳＴＭＡＮＡＧＥＲ３０８により出力される。Ｎ
ＷＰはテーブルＱＵＥＵＥ ＰＯＩＮＴＥＲＳ３０６
に書き込まれる。これは次のように起こる。即ち、 １）レジスタＦＲＥＥ３２４における値、これは未使用
セルを表わすものである。これがＶＣに関連するリンク
されたリストに連鎖され、モしてＮＷＰとして出力され
る。
ＶＣがそのバッファ配分を超えなかった場合、新しいセ
ルは配分され、ＶＣに関連するバッファにリンクされる
。ＷＰ ［ＶＣ］における値が、動作の初めにバスＷＰ
上にあるＬＩＳＴ ＭＡＮＡＧＥＲ３０８に入力され
る。書き込みポイントの新しい値ＮＷＰは、動作の終り
にＬＩＳＴＭＡＮＡＧＥＲ３０８により出力される。Ｎ
ＷＰはテーブルＱＵＥＵＥ ＰＯＩＮＴＥＲＳ３０６
に書き込まれる。これは次のように起こる。即ち、 １）レジスタＦＲＥＥ３２４における値、これは未使用
セルを表わすものである。これがＶＣに関連するリンク
されたリストに連鎖され、モしてＮＷＰとして出力され
る。
ＮＷＰ−ＬＮＫＨＥＭ ［ＷＰコ −ＦＲＥＥ２）
フリーリストにおける次のフリー場所がＦＲＥＥ３２４
に書き込まれる。
フリーリストにおける次のフリー場所がＦＲＥＥ３２４
に書き込まれる。
ＦＲＥＥ−ＬＮＫＭＥＭ ［ＦＲＥＥ］仮想回線ＶＣに
対し、読取り要求が行われたとき、現在読取られている
セル、即ちＲＰ ［ＶＣ］は、バスＲＰ上のＬＩＳＴ
ＭＡＮＡＧＥＲ３０８に入力されてフリーリストに戻
され、ＶＣに関連するバッファにおける次のセルがＮＲ
Ｐとして戻される。ＮＲＰはテーブルＱＵＥＵＥ Ｐ
ＯＩＮｉＴＥＲ５３０６に書き込まれる。このことは次
のように起こる。即ち、 １）新しい読取りポインタが戻されるが、これはＶＣに
関連するバッファにおいて、次のセルを指示するもので
ある。
対し、読取り要求が行われたとき、現在読取られている
セル、即ちＲＰ ［ＶＣ］は、バスＲＰ上のＬＩＳＴ
ＭＡＮＡＧＥＲ３０８に入力されてフリーリストに戻
され、ＶＣに関連するバッファにおける次のセルがＮＲ
Ｐとして戻される。ＮＲＰはテーブルＱＵＥＵＥ Ｐ
ＯＩＮｉＴＥＲ５３０６に書き込まれる。このことは次
のように起こる。即ち、 １）新しい読取りポインタが戻されるが、これはＶＣに
関連するバッファにおいて、次のセルを指示するもので
ある。
ＮＩ？Ｐ−ＬＮＫＭＥＭ［ＲＰ］
２）このサイクルで読み取られたセルは、フリーリスト
にそれをリンクすることにより配分を取り戻す。
にそれをリンクすることにより配分を取り戻す。
ＬＮＫＭＥＭ［ＲＰコーＦｌ？ＥＥ
Ｐ）？ＥＥ−ＲＰ
第４図は、第１図の１１０のようなルータの実施例を説
明する図である。第１図のローカルエリア通信網１０６
から到着する可変長パケットは第４図の左上部に示すＬ
ＡＮ受信機４００により受信される。各パケットにある
大域アドレスは翻訳回線４０２により仮想回線番号に翻
訳される。パケットは考えている特定のパケット長より
小さいか、もしくは大きい固定長セルを用いて移動され
る。そこでさらにヘッダーまたはトレーラバイトがパケ
ットに付加される。それにより行き先ルータに到着する
セルのシーケンスからパケットの再アセンブリを容易に
行う。そして行き先ルータはソールルータに対してフロ
ー制御を行わせ、そして脱落セル、もしくは誤送セルを
検出させる。その結果、得られた情報はセルサイズの積
分倍数で、ある長さにパッドされねばならない。この機
能は、本発明に対し直接関係して適切なものではないが
、ここで実施例を説明し、これらの機能とルータにより
実施されるべきふくそう管理機能の関係を表わすものを
述べる。
明する図である。第１図のローカルエリア通信網１０６
から到着する可変長パケットは第４図の左上部に示すＬ
ＡＮ受信機４００により受信される。各パケットにある
大域アドレスは翻訳回線４０２により仮想回線番号に翻
訳される。パケットは考えている特定のパケット長より
小さいか、もしくは大きい固定長セルを用いて移動され
る。そこでさらにヘッダーまたはトレーラバイトがパケ
ットに付加される。それにより行き先ルータに到着する
セルのシーケンスからパケットの再アセンブリを容易に
行う。そして行き先ルータはソールルータに対してフロ
ー制御を行わせ、そして脱落セル、もしくは誤送セルを
検出させる。その結果、得られた情報はセルサイズの積
分倍数で、ある長さにパッドされねばならない。この機
能は、本発明に対し直接関係して適切なものではないが
、ここで実施例を説明し、これらの機能とルータにより
実施されるべきふくそう管理機能の関係を表わすものを
述べる。
ＬＡＮパケット、及び翻訳回線４０２により生成される
仮想回線番号はセグメンテーション回線４０４に送られ
る。そこで上記の機能のため、即ちそのバイトのプレー
スホールダとしてパケットにヘッダーないしトレーラバ
イトを付加し、第２のセグメンテーション回線４０８に
送られる。その結果得られた情報は、セルサイズの積分
倍数にパッドされ、セルキュー４０６に記憶される。こ
れは第２図で述べたセルキュー２１０と同じ構造を有す
るものである。特に、コントローラ４１０における内部
のデータ構造はモニタ４１２によりアクセスされる。こ
こで各仮想回線に対し、バッファ使用（バッファ長）が
モニタされ、仮想回線に対するバッファ配分がダイナミ
ックに調節される。セグメンテーション回線４０８は仮
想回線にウィンドウフロー制御を行う。ここで各仮想回
線に対するウィンドウサイズは、以下に述べるプロトコ
ルの制御下にダイナミックに変えることができる。ウィ
ンドウフロー制御を行うために、セグメンテーション回
線は、適切な付加データバイトを書き入れ、再アセンブ
リとフロー制御プロトコルを完成する。最低限、セグメ
ンテーション回線４０８は、仮想回線当たりのカウンタ
値を保持する。これはウィンドウフロー制御を実施する
ためにそれが送出発行に際し、応答のないデータ量を見
失わぬよう接触を保つ。そして遠隔受信機からデータが
フロー制御ウィンドウから無事に送られたことを示す応
答を受信する。再アセンブリとウィンドウフロー制御を
行う方法は、従来技術において周知であるが、本発明の
独自の特徴は、ウィンドウサイズとバッファサイズが、
ふくそう制御メツセージの影響によりダイナミックに変
化できることである。送信機４１５はセグメンテーショ
ン回線４０８、及び下記ようにローカル受信機、及び出
力ふくそうＦＩＦＯ４１９からセルを受取り、そして出
力セル伝送線路４１６に−それらを送る。
仮想回線番号はセグメンテーション回線４０４に送られ
る。そこで上記の機能のため、即ちそのバイトのプレー
スホールダとしてパケットにヘッダーないしトレーラバ
イトを付加し、第２のセグメンテーション回線４０８に
送られる。その結果得られた情報は、セルサイズの積分
倍数にパッドされ、セルキュー４０６に記憶される。こ
れは第２図で述べたセルキュー２１０と同じ構造を有す
るものである。特に、コントローラ４１０における内部
のデータ構造はモニタ４１２によりアクセスされる。こ
こで各仮想回線に対し、バッファ使用（バッファ長）が
モニタされ、仮想回線に対するバッファ配分がダイナミ
ックに調節される。セグメンテーション回線４０８は仮
想回線にウィンドウフロー制御を行う。ここで各仮想回
線に対するウィンドウサイズは、以下に述べるプロトコ
ルの制御下にダイナミックに変えることができる。ウィ
ンドウフロー制御を行うために、セグメンテーション回
線は、適切な付加データバイトを書き入れ、再アセンブ
リとフロー制御プロトコルを完成する。最低限、セグメ
ンテーション回線４０８は、仮想回線当たりのカウンタ
値を保持する。これはウィンドウフロー制御を実施する
ためにそれが送出発行に際し、応答のないデータ量を見
失わぬよう接触を保つ。そして遠隔受信機からデータが
フロー制御ウィンドウから無事に送られたことを示す応
答を受信する。再アセンブリとウィンドウフロー制御を
行う方法は、従来技術において周知であるが、本発明の
独自の特徴は、ウィンドウサイズとバッファサイズが、
ふくそう制御メツセージの影響によりダイナミックに変
化できることである。送信機４１５はセグメンテーショ
ン回線４０８、及び下記ようにローカル受信機、及び出
力ふくそうＦＩＦＯ４１９からセルを受取り、そして出
力セル伝送線路４１６に−それらを送る。
ルータ１１０はまた、通信網１００から第１図のアクセ
ス線路１１２を経由しセルを受信する。
ス線路１１２を経由しセルを受信する。
これらのセルは第４図の右下端に示す受信機４１４に到
着する。これらのセルがソース１０２から生成され、行
き先１２８に向かうパケットからのものである限り、そ
れらは遠隔ルータ１２０からのふくそうメツセージか、
もしくは肯定応答のいずれかである。他のソース、ロー
カル通信網１０６に付随する行き先と通信しようとする
ものであるが、ここからアクセス線路１１２に到着する
セルの扱いについては、以下のルータ１２０の説明まで
暫く据置く。
着する。これらのセルがソース１０２から生成され、行
き先１２８に向かうパケットからのものである限り、そ
れらは遠隔ルータ１２０からのふくそうメツセージか、
もしくは肯定応答のいずれかである。他のソース、ロー
カル通信網１０６に付随する行き先と通信しようとする
ものであるが、ここからアクセス線路１１２に到着する
セルの扱いについては、以下のルータ１２０の説明まで
暫く据置く。
考えている２Ｆｆ１類のうち１種類のセルが到着すると
、受信機４１４はヘッダにおけるビットにより表示され
、セルがふくそうメツセージであるかどうかを決める。
、受信機４１４はヘッダにおけるビットにより表示され
、セルがふくそうメツセージであるかどうかを決める。
ふくそうメツセージがモニタ４１２に対する別のＦＩＦ
Ｏキュー４１７に記憶され、後述するプロトコルの１つ
によって処理される。もしプロトコルがさらにふくそう
メツセージを生成すると、適切なセルがモニタ４１２か
らセグメンテーション回線４０８に送られ、そして出力
セル伝送線路４１６て多重化される。もし到着セルがふ
くそうメツセージでない場合、受信器４１うはセルを再
アセンブリ回線４１８に送り、これはセルが遠隔ルータ
からの肯定応答であるかどうか決める。もしそうである
場合、再アセンブリ回線４１８は肯定応答受信の表示を
セグメンテーション回線に送り、その結果発行データ量
のカウント値を改新することができる。
Ｏキュー４１７に記憶され、後述するプロトコルの１つ
によって処理される。もしプロトコルがさらにふくそう
メツセージを生成すると、適切なセルがモニタ４１２か
らセグメンテーション回線４０８に送られ、そして出力
セル伝送線路４１６て多重化される。もし到着セルがふ
くそうメツセージでない場合、受信器４１うはセルを再
アセンブリ回線４１８に送り、これはセルが遠隔ルータ
からの肯定応答であるかどうか決める。もしそうである
場合、再アセンブリ回線４１８は肯定応答受信の表示を
セグメンテーション回線に送り、その結果発行データ量
のカウント値を改新することができる。
第４図と同じ構造のルータはまた、第１図のエレメント
１２０を表わすことができる。この場合、このルータに
対応する受信機４１４は第１図の出力アクセス線路１１
８からセルを受取る。これらのセルがソース１０２によ
り生成され、行き先１２８に向けられるパケットによる
限り、それらはデータセルかまたは遠隔ルータ１１０か
らのふくそうメツセージのいずれかである。セルが到着
すると、受信機４１４はセルがヘッダーのビットにより
示されたふくそうメツセージであるかどうかを決める。
１２０を表わすことができる。この場合、このルータに
対応する受信機４１４は第１図の出力アクセス線路１１
８からセルを受取る。これらのセルがソース１０２によ
り生成され、行き先１２８に向けられるパケットによる
限り、それらはデータセルかまたは遠隔ルータ１１０か
らのふくそうメツセージのいずれかである。セルが到着
すると、受信機４１４はセルがヘッダーのビットにより
示されたふくそうメツセージであるかどうかを決める。
ふくそうメツセージはモニタ４１２１；対し、別のＦＩ
ＦＯキュー４１７に記憶され、下記のプロトコルの１つ
により処理される。もしプロトコルがさらにふくそうメ
ツセージを生成する場合、適切なセルはモニタ４１２よ
りセグメンテーション回線４０８に送られ、第４図の左
下部に示す出力セル伝送線路４１６で多重化される。も
し、到着セルがふくそうメツセージでない場合、受信機
４１４はセルを再アセンブリ回線４１８に送る。これは
セルキュー４２０における仮想回線光たりのバッファ内
に到着セルを格納する。もし再アセンブリ回線４１８が
、完全ローカルエリア通信網パケットが蓄積されたこと
を検出すると、再アセンブリ回線４１８は、ライン４２
２上ローカル送信機４１６に送出肯定応答コマンドを送
る。
ＦＯキュー４１７に記憶され、下記のプロトコルの１つ
により処理される。もしプロトコルがさらにふくそうメ
ツセージを生成する場合、適切なセルはモニタ４１２よ
りセグメンテーション回線４０８に送られ、第４図の左
下部に示す出力セル伝送線路４１６で多重化される。も
し、到着セルがふくそうメツセージでない場合、受信機
４１４はセルを再アセンブリ回線４１８に送る。これは
セルキュー４２０における仮想回線光たりのバッファ内
に到着セルを格納する。もし再アセンブリ回線４１８が
、完全ローカルエリア通信網パケットが蓄積されたこと
を検出すると、再アセンブリ回線４１８は、ライン４２
２上ローカル送信機４１６に送出肯定応答コマンドを送
る。
さらに、再アセンブリ回線４１８がバッファコントロー
ラ４２２にマルチプル読取り要求を発行し、それにより
パケットを形成するセルが再アセンブリ回線４２４に続
き送られる。再アセンブラ操作を容易にするために、再
アセンブリ回線４２４はパケットがルータ１１０により
、セルに変換されたときに付加されたヘッダーもしくは
トレーラバイトを検出できる。次にパケットは翻訳回線
４２６に送られ、そこでパケットがローカルエリア通信
網１２４に送られる前に、大域アドレスはローカルエリ
ア通信網の特定アドレス翻訳される。
ラ４２２にマルチプル読取り要求を発行し、それにより
パケットを形成するセルが再アセンブリ回線４２４に続
き送られる。再アセンブラ操作を容易にするために、再
アセンブリ回線４２４はパケットがルータ１１０により
、セルに変換されたときに付加されたヘッダーもしくは
トレーラバイトを検出できる。次にパケットは翻訳回線
４２６に送られ、そこでパケットがローカルエリア通信
網１２４に送られる前に、大域アドレスはローカルエリ
ア通信網の特定アドレス翻訳される。
ウィンドウサイズの選択
本発明に述べる装置とプロトコルの動作は、ウィンドウ
サイズの選択に依存するものではない、色々実際面を考
慮して使用するウィンドウサイズを決定する。ウィンド
ウサイズが２柾類のみの場合、次のように考慮すること
により、多数の仮想回線とウィンドウサイズの好ましい
関係を導くことができる。
サイズの選択に依存するものではない、色々実際面を考
慮して使用するウィンドウサイズを決定する。ウィンド
ウサイズが２柾類のみの場合、次のように考慮すること
により、多数の仮想回線とウィンドウサイズの好ましい
関係を導くことができる。
任意のノードにおいて、同時にアクティブであることの
できる仮想回線の最大数をＮ。とする。
できる仮想回線の最大数をＮ。とする。
さらにＮ。未満のある数Ｎ１の仮想回線にフルサイズウ
ィンドウＷ。を具備させることを決めるとし、一方、残
りのＮ０＝Ｎ１の仮想回線に軽度のトラフィックに適切
な、ある小さいサイズＢｏのバッファを付与する。もし
、同時にＮｌのユーザがいて、その各ユーザのチャネル
の同じ割合を取るとすると、各ユーザの取るチャネルの
割合は１／Ｎ である。ウィンドウサイズＢ。を有する
ユ−ザが取ることのできるチャネル要領の最大割合は、
Ｂｏ／Ｗｏである。］、 ／ Ｎ ｔを小さいバッファ
を有するユーザの持ちつるトランクの最大割合、即ちＢ
ｏ ／ｗｏに等しいと置くと、諸量間に次の関係を得る
。
ィンドウＷ。を具備させることを決めるとし、一方、残
りのＮ０＝Ｎ１の仮想回線に軽度のトラフィックに適切
な、ある小さいサイズＢｏのバッファを付与する。もし
、同時にＮｌのユーザがいて、その各ユーザのチャネル
の同じ割合を取るとすると、各ユーザの取るチャネルの
割合は１／Ｎ である。ウィンドウサイズＢ。を有する
ユ−ザが取ることのできるチャネル要領の最大割合は、
Ｂｏ／Ｗｏである。］、 ／ Ｎ ｔを小さいバッファ
を有するユーザの持ちつるトランクの最大割合、即ちＢ
ｏ ／ｗｏに等しいと置くと、諸量間に次の関係を得る
。
Ｗｏ／Ｂ０＝Ｎ。
全ての仮想回線に配分される全バッファスペースＢは次
式となる。
式となる。
Ｂ ＝ （Ｎｏ ＝Ｎ１）ＢＯ＋ Ｎ１Ｗｏ＝ ＮｏＢ
Ｏ−Ｗｏ＋ ＷＯ／Ｂ。
Ｏ−Ｗｏ＋ ＷＯ／Ｂ。
ＢｏについてＢを最小とすると次式を得る。
これらの指揮からＢＮ ＳＮ 及びＷ。間０ ゝ
１２ の好ましい関係が得られる。
１２ の好ましい関係が得られる。
２を超える種類のウィンドサイズがある場合、各種選択
で可能である。幾何数列、例えば２の累乗で増加するよ
うに、サイズを選択すると便利である。別の方法として
幾つかの例で好ましいものであるが、各種標準伝送する
スピードにおけるラウンドトリップウィンドウに対応す
る異なるサイズを用いる方法である。さらに別の事態で
は他の選択をすることも可能である。
で可能である。幾何数列、例えば２の累乗で増加するよ
うに、サイズを選択すると便利である。別の方法として
幾つかの例で好ましいものであるが、各種標準伝送する
スピードにおけるラウンドトリップウィンドウに対応す
る異なるサイズを用いる方法である。さらに別の事態で
は他の選択をすることも可能である。
バッファ配分プロトコル
以下に共用可能なバッファスペースが配分されたり、配
分が取り消されたりする場合のプロトコル、及び仮想回
線のノード、ルータ及びホストに警報が知らせたりする
場合のプロトコルについて説明する。必要に応じて第５
図ないし第１２図を参照する。
分が取り消されたりする場合のプロトコル、及び仮想回
線のノード、ルータ及びホストに警報が知らせたりする
場合のプロトコルについて説明する。必要に応じて第５
図ないし第１２図を参照する。
各ノードコントローラ２１２は、テーブルＣ０ＵＮＴ
ＴＡＢＬＥにおけるエントリルにＣ０ＵＮＴ ［ＶＣ
］を経由して、その仮想回線の各バッファ長を見失わぬ
よう接触を保つ。このテーブルは先に第３図に関連して
説明したものである。各ノードコントローラはまた、そ
のフリーリストのサイズを見失わなわぬように接触を保
つ。これは第２図のセルキュー２１０におけるセル（固
定）数と、第３図に関連して述べたレジスタＧＬＯＢＡ
Ｌ Ｃ０ＵＮＴ３１０の内容との差である。これら全
ての量は、第２図に示すノードモニタ２００により、い
つでも読取りが可能である。同様に、各ルータは第４図
に示すルータモニタ４１２に利用可能であるテーブルに
おいて、その仮想回線の各々の入力バッファ長を見失わ
ぬよう接触を保つ。
ＴＡＢＬＥにおけるエントリルにＣ０ＵＮＴ ［ＶＣ
］を経由して、その仮想回線の各バッファ長を見失わぬ
よう接触を保つ。このテーブルは先に第３図に関連して
説明したものである。各ノードコントローラはまた、そ
のフリーリストのサイズを見失わなわぬように接触を保
つ。これは第２図のセルキュー２１０におけるセル（固
定）数と、第３図に関連して述べたレジスタＧＬＯＢＡ
Ｌ Ｃ０ＵＮＴ３１０の内容との差である。これら全
ての量は、第２図に示すノードモニタ２００により、い
つでも読取りが可能である。同様に、各ルータは第４図
に示すルータモニタ４１２に利用可能であるテーブルに
おいて、その仮想回線の各々の入力バッファ長を見失わ
ぬよう接触を保つ。
開示目的のために、各ルータは第４図の左側に示すセル
キュー４０６を交換ノードに類似の方法で管理すると仮
定する。それによりＣ０ＵＮＴとＧＬＯＢＡＬ Ｃ０
ＵＮＴ３１０に類似の量がルータのモニタに利用可能と
なる。
キュー４０６を交換ノードに類似の方法で管理すると仮
定する。それによりＣ０ＵＮＴとＧＬＯＢＡＬ Ｃ０
ＵＮＴ３１０に類似の量がルータのモニタに利用可能と
なる。
ノードコントローラやルータにとり、これらがバッファ
長の平滑化された平均を保持することは必要ではないが
望ましい。時間変化量ｑについて好んでよく使用される
平滑化プロシージャは、次の容易に実施できる帰納的ア
ルゴリズムにより与えられる。
長の平滑化された平均を保持することは必要ではないが
望ましい。時間変化量ｑについて好んでよく使用される
平滑化プロシージャは、次の容易に実施できる帰納的ア
ルゴリズムにより与えられる。
ｒｎ＝（”）も十什、１
ここでｑ は時間ｎにおけるｑの値、γ０＝１は時間ｎ
−１における移動平均、γｎは時間ｎにおける移動平均
、及びｆは０ないし１の数であって平均区間の長さ制御
のために選択される。Δを秒の区間で観察が行われると
すると、近似的平均区間はＴＡｖ秒で在り次式により示
される。
−１における移動平均、γｎは時間ｎにおける移動平均
、及びｆは０ないし１の数であって平均区間の長さ制御
のために選択される。Δを秒の区間で観察が行われると
すると、近似的平均区間はＴＡｖ秒で在り次式により示
される。
ＴＡｖ＝（１−１／ｌｏｇｆ）Δ【
通信網ふくそう制御に対する適切な平均区間は、１０な
いし１００ラウンドトリツプタイムスである。
いし１００ラウンドトリツプタイムスである。
本発明の各種実施例では、４つまでの２進；が通信網ふ
くそうの標識として、各仮想回線に対して用いられる。
くそうの標識として、各仮想回線に対して用いられる。
これらの量を次のように定義する。
ＢＩＧ ＩＮＰＵＴ、ルータにおける反復プログラム
が周期的に実行され（第５図、ステップ５００）、この
パラメータを更新する。仮想回線に対し、次の場合は１
に等しくセットされる。即ち、ルータ１１０においてそ
の仮想回線に対し、セルキュー例えば４０６におけるバ
ッファが過去ではあるが、最近に時間のある分数以上の
間、占有されていた場合である。また次の場合は０に等
しくセットされる（ステップ５０４） 、即ち、そのバ
ッファが時間のその分数以上の間、占有されていなかっ
た場合である。ＢＩＧ ＩＮＰＵＴを求めるためには
、移動平均アルゴリズム（ステップ５０４）におけるｆ
ｆ１Ｑは、与えられた観察でバッファにデータが見出さ
れるか否かにより１もしくはＯをとる。量γ（ステップ
５９６）は、バッファが過去ＴＡＹ秒間に占有されてい
た時間の分数の推定値である。γに対する代表的なであ
るか決して排他的でないしきい値は０．５である。
が周期的に実行され（第５図、ステップ５００）、この
パラメータを更新する。仮想回線に対し、次の場合は１
に等しくセットされる。即ち、ルータ１１０においてそ
の仮想回線に対し、セルキュー例えば４０６におけるバ
ッファが過去ではあるが、最近に時間のある分数以上の
間、占有されていた場合である。また次の場合は０に等
しくセットされる（ステップ５０４） 、即ち、そのバ
ッファが時間のその分数以上の間、占有されていなかっ
た場合である。ＢＩＧ ＩＮＰＵＴを求めるためには
、移動平均アルゴリズム（ステップ５０４）におけるｆ
ｆ１Ｑは、与えられた観察でバッファにデータが見出さ
れるか否かにより１もしくはＯをとる。量γ（ステップ
５９６）は、バッファが過去ＴＡＹ秒間に占有されてい
た時間の分数の推定値である。γに対する代表的なであ
るか決して排他的でないしきい値は０．５である。
ＳＯＭＥ ＢＡＣＫＬＯＧ、 この量は任意の仮想
回線、任意のノード１１４もしくは出力ルータ１２０で
、次の場合に１に等しくセットされる。
回線、任意のノード１１４もしくは出力ルータ１２０で
、次の場合に１に等しくセットされる。
即ち、そのノードもしくはルータにおける仮想回線バッ
ファが過去であるが最近に、ある分数以上の時間の間、
占有されていた場合である。そうでない場合は０に等し
くセットされる。ＳＯＭＥＢＡＣＫＬＯＧを求めるため
には、移動平均アルゴリズムにおける量ｑは与えられた
観察に際し、データが仮想回線バッファに見出されるか
否かにより１もしくは０をとる。次に量γはバッファが
過去ＴＡｖ秒間、占有されていた時間の分数の推定値で
ある。ＳＯＭＥ ＢＡＣＫＬＯＧを計算するモニタプ
ログラムのフロー制御は第５図に非常に類似している。
ファが過去であるが最近に、ある分数以上の時間の間、
占有されていた場合である。そうでない場合は０に等し
くセットされる。ＳＯＭＥＢＡＣＫＬＯＧを求めるため
には、移動平均アルゴリズムにおける量ｑは与えられた
観察に際し、データが仮想回線バッファに見出されるか
否かにより１もしくは０をとる。次に量γはバッファが
過去ＴＡｖ秒間、占有されていた時間の分数の推定値で
ある。ＳＯＭＥ ＢＡＣＫＬＯＧを計算するモニタプ
ログラムのフロー制御は第５図に非常に類似している。
代表的ではあるが決して排他的でないしきい値は０．５
である。ＢＩＧ ＩＮＰＵＴ及びＳＯＭＥ ＢＡＣ
ＫＬＯＧに対するしきい値は同一である必要はない。
である。ＢＩＧ ＩＮＰＵＴ及びＳＯＭＥ ＢＡＣ
ＫＬＯＧに対するしきい値は同一である必要はない。
ＢＩＧ ＢＡＣＫＬＯＧ、この量は任意の仮想回線、
任意のノードもしくは出力ルータで次の場合に１に等し
くセットされる。即ち、仮想回線がそのノードもしくは
モニタにおいて大きいバッファ長を存する場合である。
任意のノードもしくは出力ルータで次の場合に１に等し
くセットされる。即ち、仮想回線がそのノードもしくは
モニタにおいて大きいバッファ長を存する場合である。
そうでない場合はＯに等しくセットされる。ボルトネッ
クノードにおけるバッファ長はゆっくり変化するので、
バッファ長の平滑化は恐らく不必要であろう。大きいバ
ッファ長に対する判定基準はウィンドウサイズの集合に
依存する。もしウィンドウサイズが２の因子で相関して
いるすると、代表的であるが排他的でない選択は、ＢＩ
Ｇ ＢＡＣＫＬＯＧを次の場合には１に等しくセット
することある。即ち、瞬間的バッファ長が現ウィンドウ
の７５９６を超える場合である。そうでない場合は、０
に等しくセットされる。ウィンドサイズが等間隔であっ
たとすると、代表的選択は、次の場合にＢＩＧ ＢＡ
ＣＫＬＯを１に等しくセットすることである。即ち、瞬
間的バッファ長がウィンドウ間の間隔の１５０％を超え
る場合である。そうでない場合は０に等しくセットされ
る。
クノードにおけるバッファ長はゆっくり変化するので、
バッファ長の平滑化は恐らく不必要であろう。大きいバ
ッファ長に対する判定基準はウィンドウサイズの集合に
依存する。もしウィンドウサイズが２の因子で相関して
いるすると、代表的であるが排他的でない選択は、ＢＩ
Ｇ ＢＡＣＫＬＯＧを次の場合には１に等しくセット
することある。即ち、瞬間的バッファ長が現ウィンドウ
の７５９６を超える場合である。そうでない場合は、０
に等しくセットされる。ウィンドサイズが等間隔であっ
たとすると、代表的選択は、次の場合にＢＩＧ ＢＡ
ＣＫＬＯを１に等しくセットすることである。即ち、瞬
間的バッファ長がウィンドウ間の間隔の１５０％を超え
る場合である。そうでない場合は０に等しくセットされ
る。
５ＰＡＣＥ ＣＲＵＮＣＨ，この量は任意のノードも
しくは出力ルータで次の場合に１に等しくセットされる
。即ち、そのノードはルータで占有セルの瞬間的な数、
即ちＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０が、第２図また
は第４図に示すセルキュー２１０または４０６における
セルの総数の何分の１かのＦより大きい場合である。そ
うでない場合は０に等しくセットされる。代表例として
はＦ−７／８が逗択される。但し、Ｆの値は臨界的なも
のではない。
しくは出力ルータで次の場合に１に等しくセットされる
。即ち、そのノードはルータで占有セルの瞬間的な数、
即ちＧＬＯＢＡＬ Ｃ０ＵＮＴ３１０が、第２図また
は第４図に示すセルキュー２１０または４０６における
セルの総数の何分の１かのＦより大きい場合である。そ
うでない場合は０に等しくセットされる。代表例として
はＦ−７／８が逗択される。但し、Ｆの値は臨界的なも
のではない。
各種ウィンドウ管理プロトコルは上述のふくそう標識の
うちの幾つか、もしくは仝部を用いて行われる。２つの
実施例を以下に述べるが、これらは本発明を限定するも
のではない。この２つの各実施例において、各仮想回線
は常に少なくとも最小サイズＢａの大きさのバッファ配
分を有する。
うちの幾つか、もしくは仝部を用いて行われる。２つの
実施例を以下に述べるが、これらは本発明を限定するも
のではない。この２つの各実施例において、各仮想回線
は常に少なくとも最小サイズＢａの大きさのバッファ配
分を有する。
またウィンドウのフルサイズＷｏの限界いっばいまでの
他の変数サイズを有することができる。第１の実施例で
は、データソース（ルータ）におけるバッファ長、及び
ノードにおけるフリーキュースペースを使用してウィン
ドウサイズの変化を管理する。第２の実施例では、仮想
回線のデータソースと全てのノードにおけるバッファ長
と、フリーキュースペースに関する状態の統合利用を行
う。
他の変数サイズを有することができる。第１の実施例で
は、データソース（ルータ）におけるバッファ長、及び
ノードにおけるフリーキュースペースを使用してウィン
ドウサイズの変化を管理する。第２の実施例では、仮想
回線のデータソースと全てのノードにおけるバッファ長
と、フリーキュースペースに関する状態の統合利用を行
う。
２つの各実施例において、仮想回線の両方向が正しく同
じノードを横断すること、及び各ノードが単一のモニタ
２００を有し、これがいずれかの方向に移動するふくそ
う制御セルにより送られるメツセージを読取り、応答す
ることができること、この両者を仮定する。もしこの行
きと戻りのバスが論理的にバラバラである場合、プロト
コルを明確に修正して使用することができる制御メッセ
ージの戻り走行で機能を行う代わりに、仮想回線の別の
移動を使用して、進行方向における制御メツセージの移
動により変化を、全て行うこともできる。
じノードを横断すること、及び各ノードが単一のモニタ
２００を有し、これがいずれかの方向に移動するふくそ
う制御セルにより送られるメツセージを読取り、応答す
ることができること、この両者を仮定する。もしこの行
きと戻りのバスが論理的にバラバラである場合、プロト
コルを明確に修正して使用することができる制御メッセ
ージの戻り走行で機能を行う代わりに、仮想回線の別の
移動を使用して、進行方向における制御メツセージの移
動により変化を、全て行うこともできる。
第１の実施例において、入力ルータ１１０のモニタて動
作するプログラムにおけるフロー制御を模式的に第６図
に示す。第６図において、ｊ２ＬＩＭＩＴは特定の仮想
回線に対し、存在するバッフアバ配分を示す。ｆｆ１Ｗ
ＩＮＤＯＷ Ｓ ＩＺＥは提案する新しいバッファ配
分を示す。入力ルータ１１０はその各仮想回線に対し、
１ＢＩＧ ＩＮＰＵＴをモニタする（第６図ステップ
６０２）。しばしば後述のように、任意の仮想回線に割
り当てられたウィンドウのサイズの変更を要求できる。
作するプログラムにおけるフロー制御を模式的に第６図
に示す。第６図において、ｊ２ＬＩＭＩＴは特定の仮想
回線に対し、存在するバッフアバ配分を示す。ｆｆ１Ｗ
ＩＮＤＯＷ Ｓ ＩＺＥは提案する新しいバッファ配
分を示す。入力ルータ１１０はその各仮想回線に対し、
１ＢＩＧ ＩＮＰＵＴをモニタする（第６図ステップ
６０２）。しばしば後述のように、任意の仮想回線に割
り当てられたウィンドウのサイズの変更を要求できる。
それは、仮想回線上制御メツセージを送信することによ
り要求する（ステップ６０８と６１４）。
り要求する（ステップ６０８と６１４）。
ここに説明の実施例では、ヘッダーのビットにより識別
される特定のふくそう制御セルによりメツセージは送ら
れる。それに代わって別法として、普通のデータセルの
ヘッダーにおいて、この様なフィールドが形成されてい
る場合であるが、ふくそうフィールドにおける特定のビ
ットにより、ふくそう制御メツセージを送ることもでき
る。この特定の制御セルを使う場合と、ヘッダーのフィ
ールドを使う場合とに論理的な差はない。
される特定のふくそう制御セルによりメツセージは送ら
れる。それに代わって別法として、普通のデータセルの
ヘッダーにおいて、この様なフィールドが形成されてい
る場合であるが、ふくそうフィールドにおける特定のビ
ットにより、ふくそう制御メツセージを送ることもでき
る。この特定の制御セルを使う場合と、ヘッダーのフィ
ールドを使う場合とに論理的な差はない。
ウィンドウのサイズを変えようとする入力ルータはユ０
、ＷＩＮＤＯＷ ５ＩＺＥを含むメツセージを送信す
る。この初めの０は０ＲＩＧＩＮと呼ぶ変数を表わす。
、ＷＩＮＤＯＷ ５ＩＺＥを含むメツセージを送信す
る。この初めの０は０ＲＩＧＩＮと呼ぶ変数を表わす。
入力ルータからの要求を送るメツセージは、値０ＲＩＣ
ＩＮ−０により識別される。出力ルータからの応答を送
るメツセージは、後述のように０ＲＩＧＩＮ−１を有す
る。ＷＩＮＤＯＷ ５ＩＺＥは要求されるウィンドウ
のサイズであって、全ての使用可能のラウンドサイズを
表わすのに必要なだけの数のビットにコード化される０
＝例として、可能サイズが２種類のみの場合、ＷＩＮＤ
ＯＷ ５ＩＺＥ可は、単に０もしくは１ビツトのみを
必要とする。
ＩＮ−０により識別される。出力ルータからの応答を送
るメツセージは、後述のように０ＲＩＧＩＮ−１を有す
る。ＷＩＮＤＯＷ ５ＩＺＥは要求されるウィンドウ
のサイズであって、全ての使用可能のラウンドサイズを
表わすのに必要なだけの数のビットにコード化される０
＝例として、可能サイズが２種類のみの場合、ＷＩＮＤ
ＯＷ ５ＩＺＥ可は、単に０もしくは１ビツトのみを
必要とする。
現在のウィンドウサイズ（ステップ６１２．６１４）よ
り大きな新しいウィンドウサイズを要求する入力ルータ
は、後述のように、ステップ６１６において確認を受信
するまで新しいウィンドウサイズの使用を始めない。こ
れに反して、ルータは、より小さなウィンドウを使い始
めるまで、その現在の配分より小さいウィンドウサイズ
を要求しない（ステップ６０６）。交換ノードは初めの
ウィンドウサイズ以上であるバッフアノ＼イブンを節減
できるため、より小さいウィンドウに対する要求の確認
は保証される。
り大きな新しいウィンドウサイズを要求する入力ルータ
は、後述のように、ステップ６１６において確認を受信
するまで新しいウィンドウサイズの使用を始めない。こ
れに反して、ルータは、より小さなウィンドウを使い始
めるまで、その現在の配分より小さいウィンドウサイズ
を要求しない（ステップ６０６）。交換ノードは初めの
ウィンドウサイズ以上であるバッフアノ＼イブンを節減
できるため、より小さいウィンドウに対する要求の確認
は保証される。
順方向バスに沿う交換ノードのノードコントローラ２１
２が０、ＷＩＮＤＯＥ ５ＩＺＥを含む制御メツセー
ジを受信する場合、次のようなにメツセージの処理が行
われる。もしノードコントローラが要求されるバッファ
配分をすることができる場合、それを行い、メツセージ
を次のノードへ変更なしに送る。もしフリーリストにお
いて、要求を満たすには不十分な配分スペースである場
合、ノードはできるだけ大きいバッファサイズを配分し
、最小で現在のバッファサイズとする。いずれの場合で
も、コントローラは次のノードに送る前に、メツセージ
に入れることができるＷＩＮＤＯＷ ５ＩＺＥの値を
書き込む。出力ルータはまた要求されるＷＩＮＤＯＷ
５ＩＺＥの値であってできるだけ近い値を満たし、０
ＲＩＧＩＮ−１とセットして応答メツセージを示し、戻
りバスの第１の交換ノードにＷＩＮＤＯＷ ５ＩＺＥ
の最終値を含む応答を送信する。戻りバスのノードコン
トローラは０ＲＩＧＩＮ−１とＷＩＮＤＯＷ Ｓ１’
ＺＥフイールドを読取り、そしてそれらの配分を調節す
る。この調節は、あるノードが配分処理を誤る前には、
初めの要求を満たすノードに対するせいぜい下方配分で
ある。入力ルータが１で、ＷＩＮＤＯＷ ５ＩＺＥを
含む制御メツセージを受信する場合、ＷＩＮＤＯＷ
５ＩＺＥの値と矛盾しないバッファ配分の集合が全体の
バスに存在することを知ることができる。
２が０、ＷＩＮＤＯＥ ５ＩＺＥを含む制御メツセー
ジを受信する場合、次のようなにメツセージの処理が行
われる。もしノードコントローラが要求されるバッファ
配分をすることができる場合、それを行い、メツセージ
を次のノードへ変更なしに送る。もしフリーリストにお
いて、要求を満たすには不十分な配分スペースである場
合、ノードはできるだけ大きいバッファサイズを配分し
、最小で現在のバッファサイズとする。いずれの場合で
も、コントローラは次のノードに送る前に、メツセージ
に入れることができるＷＩＮＤＯＷ ５ＩＺＥの値を
書き込む。出力ルータはまた要求されるＷＩＮＤＯＷ
５ＩＺＥの値であってできるだけ近い値を満たし、０
ＲＩＧＩＮ−１とセットして応答メツセージを示し、戻
りバスの第１の交換ノードにＷＩＮＤＯＷ ５ＩＺＥ
の最終値を含む応答を送信する。戻りバスのノードコン
トローラは０ＲＩＧＩＮ−１とＷＩＮＤＯＷ Ｓ１’
ＺＥフイールドを読取り、そしてそれらの配分を調節す
る。この調節は、あるノードが配分処理を誤る前には、
初めの要求を満たすノードに対するせいぜい下方配分で
ある。入力ルータが１で、ＷＩＮＤＯＷ ５ＩＺＥを
含む制御メツセージを受信する場合、ＷＩＮＤＯＷ
５ＩＺＥの値と矛盾しないバッファ配分の集合が全体の
バスに存在することを知ることができる。
新しくオープンした仮想回線は、各ノードにおけるバッ
ファ配分Ｂ とウィンドウサイズＢｏを有する。入力ル
ータはそれがＢＩＧ ＩＮＰＵＴ−１であることを認
めると、直ちにウィンドウサイズの増加を要求しなけれ
ばならない。ウィンドウの変更を要求し、応答を受信し
た後、入力ルータは再度ＢＩＧ ＝ＩＮＰＵＴを調べる
前に、ある時間Ｄ１例えば１０ないし１００ラウンドト
リツプタイム、待つことができる。次にＢＩＧ ＩＮ
ＰＵＴ−１の場合、さらに別のウィンドウサイズの増加
を求めることができる。減少が求められる場合、仮想回
線の発行データ量がより小さいウィンドウに当てはまる
まで、入力ルータは要求を出さず、その時から新しいウ
ィンドウの限度を観測する。実際の配分は、ＬＩＭＩＴ
の値がＷＩＮＤＯＷＳＩＺＥ（ステップ６０８．６１８
）の値に等しくなるまで変更されない。
ファ配分Ｂ とウィンドウサイズＢｏを有する。入力ル
ータはそれがＢＩＧ ＩＮＰＵＴ−１であることを認
めると、直ちにウィンドウサイズの増加を要求しなけれ
ばならない。ウィンドウの変更を要求し、応答を受信し
た後、入力ルータは再度ＢＩＧ ＝ＩＮＰＵＴを調べる
前に、ある時間Ｄ１例えば１０ないし１００ラウンドト
リツプタイム、待つことができる。次にＢＩＧ ＩＮ
ＰＵＴ−１の場合、さらに別のウィンドウサイズの増加
を求めることができる。減少が求められる場合、仮想回
線の発行データ量がより小さいウィンドウに当てはまる
まで、入力ルータは要求を出さず、その時から新しいウ
ィンドウの限度を観測する。実際の配分は、ＬＩＭＩＴ
の値がＷＩＮＤＯＷＳＩＺＥ（ステップ６０８．６１８
）の値に等しくなるまで変更されない。
交換ノード１１４のモニタで動作するプログラムにおけ
るフロー制御は、いずれかの方向からのふくそう制御セ
ルの到着に応答して行われるが、これを第７図に示す。
るフロー制御は、いずれかの方向からのふくそう制御セ
ルの到着に応答して行われるが、これを第７図に示す。
ステップ７００は要求されたウィンドウサイズにできる
だけ近付くようにＬＩ Ｍ Ｉ Ｔを変更する。ステッ
プ７０２は制御セルにＬＩＭＩＴの新しい値を書き込み
、仮想回線における次のノードにメツセージを送る。
だけ近付くようにＬＩ Ｍ Ｉ Ｔを変更する。ステッ
プ７０２は制御セルにＬＩＭＩＴの新しい値を書き込み
、仮想回線における次のノードにメツセージを送る。
先の実施例は入力ルータにおいてふくそう情報のみを用
いた。第２の実施例は必要に応じて、新しいウィンドウ
サイズをとるために全回線にわたるふくそう情報を統合
するプロトコルを用いる。
いた。第２の実施例は必要に応じて、新しいウィンドウ
サイズをとるために全回線にわたるふくそう情報を統合
するプロトコルを用いる。
これは２つのフェーズの信号プロシージャを用いる。即
ち、第１のフェーズは新しいウィンドウをセットアツプ
するものであり、第２のフェーズは色々のノードにおけ
る新しい・ウィンドウとバッファ配分に存在する矛盾を
解消するものである。入力ルータと出力ルータ及び交換
ノードにより行われる論理ステップを第８図ないし第１
２図に模式第２の実施例におけるプロトコルは先に定義
した０ＲＩＣＩＮｉＢＩＧ ＩＮＰＵＴ、ＳＯＭＥＢ
ＡＣＫＬＯＧＳＢＩＧ ＢＡＣＫＬＯＧ、及び５ＰＡ
ＳＥ ＣＲＵＮＣＨを用いる。プロトコルは信号の２
つのフェーズを用いるので、もう１つの２進量であるＰ
ＨＡＳＥを必要とし、これはフェーズ１に対しては値は
０、フェーズ２に対しては値は１をとる。フェーズ１に
おいて、入力ルータ１１０は次の量からなる６・ビット
フィールドを送る制御メツセージをセットする。即ち、
０ＲＩＧＩＮ−０、ＰＨＡＳＥ−０、ＢＩＧ ＩＮＰ
ＵＴ、５ＰＡＳＥ ＣＲＵＮＣＨ−０、ＳＯＭＥ
Ｂ Ａ ＣＫ Ｌ ＯＧ −０、ＢＩＧ ＢＡＣＫＬ
ＯＧ−０である。入力ルータに対するフロー制御を第８
図に示す。
ち、第１のフェーズは新しいウィンドウをセットアツプ
するものであり、第２のフェーズは色々のノードにおけ
る新しい・ウィンドウとバッファ配分に存在する矛盾を
解消するものである。入力ルータと出力ルータ及び交換
ノードにより行われる論理ステップを第８図ないし第１
２図に模式第２の実施例におけるプロトコルは先に定義
した０ＲＩＣＩＮｉＢＩＧ ＩＮＰＵＴ、ＳＯＭＥＢ
ＡＣＫＬＯＧＳＢＩＧ ＢＡＣＫＬＯＧ、及び５ＰＡ
ＳＥ ＣＲＵＮＣＨを用いる。プロトコルは信号の２
つのフェーズを用いるので、もう１つの２進量であるＰ
ＨＡＳＥを必要とし、これはフェーズ１に対しては値は
０、フェーズ２に対しては値は１をとる。フェーズ１に
おいて、入力ルータ１１０は次の量からなる６・ビット
フィールドを送る制御メツセージをセットする。即ち、
０ＲＩＧＩＮ−０、ＰＨＡＳＥ−０、ＢＩＧ ＩＮＰ
ＵＴ、５ＰＡＳＥ ＣＲＵＮＣＨ−０、ＳＯＭＥ
Ｂ Ａ ＣＫ Ｌ ＯＧ −０、ＢＩＧ ＢＡＣＫＬ
ＯＧ−０である。入力ルータに対するフロー制御を第８
図に示す。
ノードコントローラに対するフローの制御を第９図に示
す。ノードコントローラがフェーズ１の制御メツセージ
を受信すると、それは次の値を調べる。即ち、５ＰＡＳ
Ｅ ＣＲＵＮＣＨ（ステラ９００） 、ＳＯＭＥ
ＢＡＣＫＬＯＧ （ステップ９０４） 、及びＢＩＧ
ＢＡＣＫＬＯＣ； （ステップ９１０）である。そし
てもし与えられた量のそれ自信の値が０である場合、そ
のフィールドを変更なく送る。もしその量のそれ自信の
値が１である場合、次の交換ノードに（ステップ９１２
）制御メツセージを伝送する前に、対応するフィールド
に、第９図（ステップ９０２．９０６．９１０）に示す
ように１を書き込む。
す。ノードコントローラがフェーズ１の制御メツセージ
を受信すると、それは次の値を調べる。即ち、５ＰＡＳ
Ｅ ＣＲＵＮＣＨ（ステラ９００） 、ＳＯＭＥ
ＢＡＣＫＬＯＧ （ステップ９０４） 、及びＢＩＧ
ＢＡＣＫＬＯＣ； （ステップ９１０）である。そし
てもし与えられた量のそれ自信の値が０である場合、そ
のフィールドを変更なく送る。もしその量のそれ自信の
値が１である場合、次の交換ノードに（ステップ９１２
）制御メツセージを伝送する前に、対応するフィールド
に、第９図（ステップ９０２．９０６．９１０）に示す
ように１を書き込む。
受信ルータ１２０がフェーズ１制御メツセージを受信す
ると、それはまず、５ＰＡＳＥ ＣＲＵＮＣＨ，ＳＯ
ＭＥ ＢＡＣＫＬＯＧ、及びＢＩＧＢＡＣＫＬＯＧの
それ自信の値と到着メツセージにおける値を、丁度交換
ノードがしたように結合する。受信ルータは次に修正メ
ツセージの最後の４ビツトを調べ、第１０図に示す論理
フローを用いて、下記の４つの場合に従いＷＩＮＤＯＷ
ＳＩＺＥの提案値を計算する。
ると、それはまず、５ＰＡＳＥ ＣＲＵＮＣＨ，ＳＯ
ＭＥ ＢＡＣＫＬＯＧ、及びＢＩＧＢＡＣＫＬＯＧの
それ自信の値と到着メツセージにおける値を、丁度交換
ノードがしたように結合する。受信ルータは次に修正メ
ツセージの最後の４ビツトを調べ、第１０図に示す論理
フローを用いて、下記の４つの場合に従いＷＩＮＤＯＷ
ＳＩＺＥの提案値を計算する。
１）もしＢＩＧ ＩＮＰＵＴ−１及びＳ ＯＭＥＢＡ
ＣＫＬＯＧ−０（ステップ１０００）ならば、ウィンド
ウサイズを増加する。
ＣＫＬＯＧ−０（ステップ１０００）ならば、ウィンド
ウサイズを増加する。
仮想回線はラウントロピンスケジューラにより、どこに
もボルトネックされていない、仮想回線はもつと速くに
送りたがっている。不必要にそのウィンドウにより減速
されるでいる。
もボルトネックされていない、仮想回線はもつと速くに
送りたがっている。不必要にそのウィンドウにより減速
されるでいる。
２）もしＢＩＧ ＢＡＣＫＬＯＧ−１及び５ｐＡＳＥ
ＣＲＵＮＣＨ−１（ステップ１００２．１００４）
ならば、ウィンドサイズを減少する。
ＣＲＵＮＣＨ−１（ステップ１００２．１００４）
ならば、ウィンドサイズを減少する。
あるノードはラウントロピンスケジューラによリボトル
ネックされている。大きなバッファがそこに地区説され
そして、ウィンドウは不必要に大きい、そこであるノー
ド手はスペースを用いてこれを満たす。
ネックされている。大きなバッファがそこに地区説され
そして、ウィンドウは不必要に大きい、そこであるノー
ド手はスペースを用いてこれを満たす。
３）もしＢＩＧ ＩＮＰＵＴ−０、ＳＯＭＥＢＡＣＫ
ＬＯＧ−０，５ＰＡＳＥ ＣＲＵＮＣＨ−１（ステッ
プ１００６）ならば、ウィンドウサイズを減少する。
ＬＯＧ−０，５ＰＡＳＥ ＣＲＵＮＣＨ−１（ステッ
プ１００６）ならば、ウィンドウサイズを減少する。
仮想回線は出力された負荷は軽度であるので負荷送る大
きなウィンドウは不要である。そこでノードはスペース
を用いてこれを満たしている。
きなウィンドウは不要である。そこでノードはスペース
を用いてこれを満たしている。
４）他の全ての場合であって、現在のウィンドウサイズ
は適切である。
は適切である。
受信ルータは次に戻りパスにより初めの交換ノードにフ
ェーズ１制御メツセージを送信する（ステップ１０１２
）。応答メツセージはフィールド０ＲＩＧＩＮ−１、Ｐ
ＨＡＳＥ−０、ＷＩＮＤＯＷ ５ＩＺＥを含み、最後
のフィールドは推奨ウィンドウサイズの２進符号化を含
む。戻りパスの各ノードコントローラ２１２は制御メツ
セージをみて、第１１図に示す動作をとる。もし増加配
分が要求されると（ステップ１１００）、増加可能の場
合はノードはその配分を行う（ステップ１１０２）、も
し要求配分が不可能ならば、可能な化ぎりいかなる配分
でも行う。但し、最小な現在のバッファサイズである。
ェーズ１制御メツセージを送信する（ステップ１０１２
）。応答メツセージはフィールド０ＲＩＧＩＮ−１、Ｐ
ＨＡＳＥ−０、ＷＩＮＤＯＷ ５ＩＺＥを含み、最後
のフィールドは推奨ウィンドウサイズの２進符号化を含
む。戻りパスの各ノードコントローラ２１２は制御メツ
セージをみて、第１１図に示す動作をとる。もし増加配
分が要求されると（ステップ１１００）、増加可能の場
合はノードはその配分を行う（ステップ１１０２）、も
し要求配分が不可能ならば、可能な化ぎりいかなる配分
でも行う。但し、最小な現在のバッファサイズである。
そしてＷＩＮＤＯＷ ５ＩＺＥフイールドで行った配
分を書き込む（ステップ１１０４）。ノードは次に戻り
パスの次のノードに制御メツセージを伝送する（ステッ
プ１１０６）。もし要求が減少配分に対するものならば
、ノードは未だ減少を行っていないがＷＩＮＤＯＷＳＩ
ＺＥフィールドを変更なしに送る。 送信ルータがフェ
ーズ１応答メツセージを受信すると（ステップ８０４）
、ＷＩＮＤＯＷ ５ＩＺＥフイールドは仮想回線が有
しようとするウィンドウを示す。もし現在のウィンドウ
サイズを超えて増加が認められると、直ちに可能となる
る。もし減少があると、送信ルートは仮想回線で応答デ
ータの量を待ち、第８図に示すようにステップ８０６で
新しいウィンドウサイズになる。次にそれは、フィール
ド０ＲＩＧＩＮ−０、ＰＨＡＳＥ−１、ＷＩＮＤＯＷ
Ｓ ＩＺＥ （ステップ８１０）を有するフェーズ２
制御メツセージを送信する。このメツセージを受信する
ノードコントローラは、第１２図に示す動作をする。そ
れらは下方でそれらのバッファ配分を必要ならば、ＷＩ
ＮＤＯＷ ５ＩＺＥ （ステップ１２００）の値に調
節し、制御メツセージを変えずに送る（ステップ１２０
２）。
分を書き込む（ステップ１１０４）。ノードは次に戻り
パスの次のノードに制御メツセージを伝送する（ステッ
プ１１０６）。もし要求が減少配分に対するものならば
、ノードは未だ減少を行っていないがＷＩＮＤＯＷＳＩ
ＺＥフィールドを変更なしに送る。 送信ルータがフェ
ーズ１応答メツセージを受信すると（ステップ８０４）
、ＷＩＮＤＯＷ ５ＩＺＥフイールドは仮想回線が有
しようとするウィンドウを示す。もし現在のウィンドウ
サイズを超えて増加が認められると、直ちに可能となる
る。もし減少があると、送信ルートは仮想回線で応答デ
ータの量を待ち、第８図に示すようにステップ８０６で
新しいウィンドウサイズになる。次にそれは、フィール
ド０ＲＩＧＩＮ−０、ＰＨＡＳＥ−１、ＷＩＮＤＯＷ
Ｓ ＩＺＥ （ステップ８１０）を有するフェーズ２
制御メツセージを送信する。このメツセージを受信する
ノードコントローラは、第１２図に示す動作をする。そ
れらは下方でそれらのバッファ配分を必要ならば、ＷＩ
ＮＤＯＷ ５ＩＺＥ （ステップ１２００）の値に調
節し、制御メツセージを変えずに送る（ステップ１２０
２）。
受信ルータはフィールド０ＲＩＧＩＮ−１、ＰＨＡＳＥ
−１、ＷＩＮＤＯＷ ５ＩＺＥを有するフェーズ２応
答メツセージを戻す。交換ノードは単にこのメッセーシ
セを次の理由で送るのみである。
−１、ＷＩＮＤＯＷ ５ＩＺＥを有するフェーズ２応
答メツセージを戻す。交換ノードは単にこのメッセーシ
セを次の理由で送るのみである。
なぜなら、その唯一の目的は、送信ルータにバッファ配
分の矛盾のない集合が全仮想回線に存在することをと知
らせることである。
分の矛盾のない集合が全仮想回線に存在することをと知
らせることである。
フェーズ２を終了後、送信ルータは、フェーズ１の再開
の前、第８図ステップ８１６に示したように、暫く待つ
。フェーズ２終了以降ある時間Ｄ、例えば１０ないし１
００ラウンドトリツプタイムか経過するまで、例にどち
らが先にこようと、待つ。次に、もし現ウィンドウサイ
ズが最小ウィンドウサイズＢｏより大きい（ステップ８
１８）かもしくは、もしＢＩＧ ＩＮＰＵＴ−１（ス
テップ８００）ならば、フェーズ１は直ちに始まる。
の前、第８図ステップ８１６に示したように、暫く待つ
。フェーズ２終了以降ある時間Ｄ、例えば１０ないし１
００ラウンドトリツプタイムか経過するまで、例にどち
らが先にこようと、待つ。次に、もし現ウィンドウサイ
ズが最小ウィンドウサイズＢｏより大きい（ステップ８
１８）かもしくは、もしＢＩＧ ＩＮＰＵＴ−１（ス
テップ８００）ならば、フェーズ１は直ちに始まる。
そうでない場合、フェーズ１はＢＩＧ ＩＮＰＵＴ−
１とにると直ちに始まる。新しくオーブンされる仮想回
線は、その初めのウィンドウサイズとバッファ配分がＢ
ｏであるが、それがあるとすれば、ＢＩＧ ＩＮＰＵ
Ｔ−１となると直ちにフェーズ１を始めねばならない。
１とにると直ちに始まる。新しくオーブンされる仮想回
線は、その初めのウィンドウサイズとバッファ配分がＢ
ｏであるが、それがあるとすれば、ＢＩＧ ＩＮＰＵ
Ｔ−１となると直ちにフェーズ１を始めねばならない。
（ウィンドウ・サイジングの概要：第１図と第２図）
本発明の現出願後、さらに研究をすすめた結果、第１図
に示すセル通信網におけるウィンドウのサイシジング方
法を改善することができた。
に示すセル通信網におけるウィンドウのサイシジング方
法を改善することができた。
この方法は、原出願に開示の第１の実施例に特に適して
いる。以下にまず、これらの方法の概要を説明し、次に
仮想回線に対する理想的なウィンドウサイズを決める方
法、再サイジングがいつ必要かを決める方法、及び再サ
イジングの実施方法を詳しく説明する。
いる。以下にまず、これらの方法の概要を説明し、次に
仮想回線に対する理想的なウィンドウサイズを決める方
法、再サイジングがいつ必要かを決める方法、及び再サ
イジングの実施方法を詳しく説明する。
通信網１００において、各交換ノード１１４はメモリバ
ッファ２１０（第２図）を有する。バッファは、ある割
当て解除されたメモリスペースと共に、各仮想回線に対
し、回線当りのキューに論理的に割られる。回線当りの
キューはキューが属する仮想回線経由で送られるセルを
含む。
ッファ２１０（第２図）を有する。バッファは、ある割
当て解除されたメモリスペースと共に、各仮想回線に対
し、回線当りのキューに論理的に割られる。回線当りの
キューはキューが属する仮想回線経由で送られるセルを
含む。
キューはラウントロピンでサービスされる。各仮想回線
のキューに割当てられたバッファスペース量は、時に応
じて変動するが回線の現ウィンドウサイズより決して小
さくはならず、それ以上である。交換コントローラ２１
２は、各仮想回線に配分されたメモリ量のリストを保持
する。もし仮想回線のキューがオーバーフローする場合
、その仮想回線に属するセルのみか放棄される。しかし
回線当りのキューが本発明によりサイズが決められると
、オーバーフローはルータ１１０てのみ起こり、通信網
内では決して起こらない。
のキューに割当てられたバッファスペース量は、時に応
じて変動するが回線の現ウィンドウサイズより決して小
さくはならず、それ以上である。交換コントローラ２１
２は、各仮想回線に配分されたメモリ量のリストを保持
する。もし仮想回線のキューがオーバーフローする場合
、その仮想回線に属するセルのみか放棄される。しかし
回線当りのキューが本発明によりサイズが決められると
、オーバーフローはルータ１１０てのみ起こり、通信網
内では決して起こらない。
ルータ１１０とルータ１２０は、通信網メーカに属する
と考えられるが、これらは仮想回線通信網上エツジツウ
エツジ・セルウィンドウを強制する。各仮想回線はデフ
ォルトウィンドウがそれがセットアツプされると与えら
れる。デフォルトウィンドウは仮想回線経由で伝送され
る最大パケットと、少なくともある信号情報を保持する
のに最小限、十分な大きさである。仮想回線は少なくと
もデフォルトウィンドウサイズのウィンドウを、それが
存在する間は保持する。入力ルータ１１０は、全ラウン
ドトリップ・ウィンドウまでのウィンドウサイズの増加
、もしくはデフォルトウィンドウまでの減少の要求を発
行することができる。
と考えられるが、これらは仮想回線通信網上エツジツウ
エツジ・セルウィンドウを強制する。各仮想回線はデフ
ォルトウィンドウがそれがセットアツプされると与えら
れる。デフォルトウィンドウは仮想回線経由で伝送され
る最大パケットと、少なくともある信号情報を保持する
のに最小限、十分な大きさである。仮想回線は少なくと
もデフォルトウィンドウサイズのウィンドウを、それが
存在する間は保持する。入力ルータ１１０は、全ラウン
ドトリップ・ウィンドウまでのウィンドウサイズの増加
、もしくはデフォルトウィンドウまでの減少の要求を発
行することができる。
増加をワン・ラウンドトリップ時間の短い間隔で要求す
ることもできるが、減少はルータ１１０で再ネゴシェー
ション・タイマにより決められたより、長い間隔で要求
される。要求は仮想回線内を回り、ノードモニタ２００
は下記のようにそれを確認修正し、またバッファ配分の
適切な変更も行う。応答が入力ルータ１１０に戻ると、
ルータ１１０は仮想回線に対する新しいウィンドウに対
応するセルバッファ配分が、仮想回線の全ての交換ノー
ド１１４に存在することを知る。ルータ１１０はバッフ
ァ配分増加を確認後、より大きいウィンドウを使い始め
る。バッファ配分の減少要求をする前に、より小さいウ
ィンドウを強制し始める。
ることもできるが、減少はルータ１１０で再ネゴシェー
ション・タイマにより決められたより、長い間隔で要求
される。要求は仮想回線内を回り、ノードモニタ２００
は下記のようにそれを確認修正し、またバッファ配分の
適切な変更も行う。応答が入力ルータ１１０に戻ると、
ルータ１１０は仮想回線に対する新しいウィンドウに対
応するセルバッファ配分が、仮想回線の全ての交換ノー
ド１１４に存在することを知る。ルータ１１０はバッフ
ァ配分増加を確認後、より大きいウィンドウを使い始め
る。バッファ配分の減少要求をする前に、より小さいウ
ィンドウを強制し始める。
仮想回線の理想的ウィンドウサイズの決定以下に、仮想
回線の理想的なウィンドウサイズを求めるアルゴリズム
を展開する。このアルゴリズムの展開は回線を一度に１
つターンオンし、ターンオンした後、連続して伝送する
単純例から始め、次にこの単純例を変えて仮想回線によ
るデータの間欠的伝送を考える。
回線の理想的なウィンドウサイズを求めるアルゴリズム
を展開する。このアルゴリズムの展開は回線を一度に１
つターンオンし、ターンオンした後、連続して伝送する
単純例から始め、次にこの単純例を変えて仮想回線によ
るデータの間欠的伝送を考える。
いずれの通過リンクでもコンテンションに出会わない単
独ユーザ（仮想回線）は、全帯域幅通信網を使用するた
めにはウィンドウサイズＷ。を必要とする。他のアクテ
ィブユーザとリンクを共用するユーザは、Ｗｏと同じ大
きさのウィンドウを必要としない。このようなユーザに
全帯域幅を与える必要はないからである。原則として、
もしＮユーザがリンク経由で連続的に伝送する場合、各
ユーザはＷｏ／Ｎより大きいウィンドウを必要とせず、
必要条件の合計ウィンドウが丁度Ｗ。である。
独ユーザ（仮想回線）は、全帯域幅通信網を使用するた
めにはウィンドウサイズＷ。を必要とする。他のアクテ
ィブユーザとリンクを共用するユーザは、Ｗｏと同じ大
きさのウィンドウを必要としない。このようなユーザに
全帯域幅を与える必要はないからである。原則として、
もしＮユーザがリンク経由で連続的に伝送する場合、各
ユーザはＷｏ／Ｎより大きいウィンドウを必要とせず、
必要条件の合計ウィンドウが丁度Ｗ。である。
もう少し、実際的な例として、次の仮説の場合を考えて
みる。即ち、リンク経由で伝送する回線を一度に１つタ
ーンオンし、そして連続的に伝送する場合である。もし
ターンオンされたに番目の回線にウィンドウサイズＷ。
みる。即ち、リンク経由で伝送する回線を一度に１つタ
ーンオンし、そして連続的に伝送する場合である。もし
ターンオンされたに番目の回線にウィンドウサイズＷ。
／ｋを割当てると、ｋ回線が伝送しているとき、ラウン
トロピン・キューイング統制の場合、各個にトランク帯
域幅の一部１／ｋを与え、そしてスループットが不必要
にウィンドウ制約を受けるところはどこもない。
トロピン・キューイング統制の場合、各個にトランク帯
域幅の一部１／ｋを与え、そしてスループットが不必要
にウィンドウ制約を受けるところはどこもない。
もしに番目のユーザがＷｏ／にのウィンドウサイズをと
るとすると、Ｎユーザに対する合計バッファスペースＢ
は次式を満足し、 Ｂ／Ｗｋ＝Σ１／に＝ｌｏｇＮ。
るとすると、Ｎユーザに対する合計バッファスペースＢ
は次式を満足し、 Ｂ／Ｗｋ＝Σ１／に＝ｌｏｇＮ。
ｋ＝１
実際上は、その結果ＢはＷＯの何倍かになる。
−膜内に、データ通信網は多種類のユーザを有するが、
次の３つの広いカテゴリに類別することができる。即ち
、 （１）伝送がデフォルトウィンドウより短い中間ユーザ
、 （２）伝送がＷｏと比べて長く、ラウンドトリップ伝搬
時間Ｔｏに比べ、長い間隔に分けられている大量ユーザ
；及び （３）Ｔｏと同じ位の間隔で、Ｗｏと同じくらいの反復
伝送を特徴とするアクティビティの期間と、Ｔｏに比べ
長いイナクティビティ期間分けられている間欠ユーザで
ある。この間欠ユーザが効率をよくするのに一番難しく
、ウィンドウサイズの選択の際に考慮するのがこのクラ
スのユーザである。
次の３つの広いカテゴリに類別することができる。即ち
、 （１）伝送がデフォルトウィンドウより短い中間ユーザ
、 （２）伝送がＷｏと比べて長く、ラウンドトリップ伝搬
時間Ｔｏに比べ、長い間隔に分けられている大量ユーザ
；及び （３）Ｔｏと同じ位の間隔で、Ｗｏと同じくらいの反復
伝送を特徴とするアクティビティの期間と、Ｔｏに比べ
長いイナクティビティ期間分けられている間欠ユーザで
ある。この間欠ユーザが効率をよくするのに一番難しく
、ウィンドウサイズの選択の際に考慮するのがこのクラ
スのユーザである。
（１）式に導かれたモデルは、次の点で非現実的である
。即ち、新しいユーザが到着したとき、アクティブに伝
送しているユーザ数は、新しいと同等もしくはそれより
大きいウィンドウ配分を保有するユーザ数に等しいと仮
定している点である。
。即ち、新しいユーザが到着したとき、アクティブに伝
送しているユーザ数は、新しいと同等もしくはそれより
大きいウィンドウ配分を保有するユーザ数に等しいと仮
定している点である。
平均して、次の理由からアクティブに伝送しているユー
ザ数はやや少ない。それは−ザがウィンドウ配分を保有
する時間ある部分の間ユーザは伝送して行わないからで
ある。ここで、次のようにアイドル時間の間の影響をモ
デル化する。
ザ数はやや少ない。それは−ザがウィンドウ配分を保有
する時間ある部分の間ユーザは伝送して行わないからで
ある。ここで、次のようにアイドル時間の間の影響をモ
デル化する。
ウィンドウ配分を有するユーザ数は、ゆっくりと変動す
ると仮定し、２つのノード“アクティブ。
ると仮定し、２つのノード“アクティブ。
と“アイドル″を有するクローズド・キューイング通信
網をここで考える。伝送ユーザはアクティブノードでキ
ューに入れられていると考え、そして単独のプロセッサ
・シェアリング・オーバーと考える。アクティブノード
を通る各パスにおける間欠ユーザの平均サービス時間の
条件はτである。
網をここで考える。伝送ユーザはアクティブノードでキ
ューに入れられていると考え、そして単独のプロセッサ
・シェアリング・オーバーと考える。アクティブノード
を通る各パスにおける間欠ユーザの平均サービス時間の
条件はτである。
アクティビティの各バースト後、ユーザは平均時間ｈτ
の間、無限サーバノードとしてモデル化され、アイドル
状態を見に行く。実際の通信網においては、約ｈτより
長い間アイドル状態であったユーザは休止と判定され、
そのウィンドウはデフォルトウィンドウに縮減されてし
まう。しかし、このポピユレーションロスは本クローズ
ド通信網モデルには含まれていない。
の間、無限サーバノードとしてモデル化され、アイドル
状態を見に行く。実際の通信網においては、約ｈτより
長い間アイドル状態であったユーザは休止と判定され、
そのウィンドウはデフォルトウィンドウに縮減されてし
まう。しかし、このポピユレーションロスは本クローズ
ド通信網モデルには含まれていない。
ユニで次に記載の平均値分析を適用する。即ち、イー・
デイ・ラゾウスカ（Ｅ、Ｄ、Ｌａｚｏｖｓｋａ） 、ジ
ェイ・サホーヤン（Ｊｉｚａｈｏｒｊａｎ） 、シイ・
ニス・グラハム（Ｇ、Ｓ、Ｇｒａｈａｌｌ） 、及びケ
イ・シイ・シブシフ（Ｋ、Ｃ，５ｅｖｓｉｋ） 、クオ
ンティタティブ システム パーホーマンス（Ｑｕａｎ
ｔａｔｊｖｅ Ｓｙｓｔｃｍ Ｐｕｆｏｒｍａｎｓｅ）
：キューイング通信網を用いるコンピュータ シス
テム分析、プレンティス・ホール（１９８４） 、１１
２−１１６頁である。これによりにユーザを有する通信
網におけるアクティブユーザの平均数Ｊｋを求める。ユ
ーザがアクティブである平均時間は、平均サイクル時間
（Ｊｉ＋１）τ＋ｈτからの（Ｊｋ−１＋１）τである
。従って次式を得る。
デイ・ラゾウスカ（Ｅ、Ｄ、Ｌａｚｏｖｓｋａ） 、ジ
ェイ・サホーヤン（Ｊｉｚａｈｏｒｊａｎ） 、シイ・
ニス・グラハム（Ｇ、Ｓ、Ｇｒａｈａｌｌ） 、及びケ
イ・シイ・シブシフ（Ｋ、Ｃ，５ｅｖｓｉｋ） 、クオ
ンティタティブ システム パーホーマンス（Ｑｕａｎ
ｔａｔｊｖｅ Ｓｙｓｔｃｍ Ｐｕｆｏｒｍａｎｓｅ）
：キューイング通信網を用いるコンピュータ シス
テム分析、プレンティス・ホール（１９８４） 、１１
２−１１６頁である。これによりにユーザを有する通信
網におけるアクティブユーザの平均数Ｊｋを求める。ユ
ーザがアクティブである平均時間は、平均サイクル時間
（Ｊｉ＋１）τ＋ｈτからの（Ｊｋ−１＋１）τである
。従って次式を得る。
Ｊｌ−１＋Ｉ ＪＩ
Ｊｌ−１＋１＋ｂ ｋ
／（ｋ〜１）で置き換え、その結果得られた２次式を解
くことにより、重要なパラメータ範囲のＪｋ−１に対す
る非常に正確なりローズド形の式を得ることができる。
くことにより、重要なパラメータ範囲のＪｋ−１に対す
る非常に正確なりローズド形の式を得ることができる。
このクローズド通信網分析を用いて次のことができる。
ｋ−１の間欠ユーザが既にいて’ Ｗｋ−１以上のウィ
ンドウを有するとき、ｋ番目の到着ユーザがウィンドウ
配分Ｗｋ−１を受取ると仮定する。
ンドウを有するとき、ｋ番目の到着ユーザがウィンドウ
配分Ｗｋ−１を受取ると仮定する。
ｋ番目ユーザのウィンドウをＷｋ−１と表わす取決めと
すると、１番目のユーザのウィンドウはＷ。
すると、１番目のユーザのウィンドウはＷ。
と表わすことになり、これを全ラウンドトリップウィン
ドウとして用いる。ｋ番目のユーザのスループットが不
必要に制約されないためには、Ｗｋ−１は次式を満たす
必要がある。
ドウとして用いる。ｋ番目のユーザのスループットが不
必要に制約されないためには、Ｗｋ−１は次式を満たす
必要がある。
Ｗ ／Ｗ 〜１／ （Ｊｉ１＋１）。
ｋ−１０
Ｊｉ−０から出発して、ｈのいずれの値に対しても循環
式（２）からＪｋ−１の数値を求めるのは自明のことで
ある。しかし、（２）の右辺をＪ ｋ−１Ｊｋ−１にク
ローズド形の近似を用いると次式を得る。
式（２）からＪｋ−１の数値を求めるのは自明のことで
ある。しかし、（２）の右辺をＪ ｋ−１Ｊｋ−１にク
ローズド形の近似を用いると次式を得る。
Ｗｋ−＋ ／Ｗｏ ＝ １７（ｋ−ｈ）
但し、ｋ＞ｈ。
但し、ｋ＞ｈ。
もしｈ−ｏとすると、（４）式は当然次式を与える。
Ｗｋ、／Ｗ０＝１／に
これは（１）式のシフトされたバージョンである。
もしに番目のユーザは（４）式による配分が与えられる
と、Ｎのユーザに対する全バッファ配分は次式を満足す
る。
と、Ｎのユーザに対する全バッファ配分は次式を満足す
る。
もしｈ＞０とすると、
％−１／ＷＯ＝１−（ｋ−１）／ｈ
侃し、ｋ（ｈ。
侃し、ｋ（ｈ。
となり、その結果、初めのユーザに与えられるウィンド
ウサイズは、Ｗｏから線状に減少するものはほんの僅か
のユーザである。ｋ−１に近付くと、遷移がある。ｈ番
目のユーザは次式のウィンドウを得る。
ウサイズは、Ｗｏから線状に減少するものはほんの僅か
のユーザである。ｋ−１に近付くと、遷移がある。ｈ番
目のユーザは次式のウィンドウを得る。
Ｗｋ−ｔ ／Ｗｋ ＝ １１ｈ１ｎ 但し
、ｋ−ｈ、またウィンドウサイズ分布のティルは次式と
なり、合計は積分により近似することができ、次式を与
える。
、ｋ−ｈ、またウィンドウサイズ分布のティルは次式と
なり、合計は積分により近似することができ、次式を与
える。
小数のアルジエブラであるが次式を示す。
Ｂ／Ｗｏ＝］ｏｇＮ＋ｈ／２
イ！し、 Ｎ＞ｈ＞１
この式を用いてＢ／ＷｏＳＮ及びｈの間のトレードオフ
を計算できる。
を計算できる。
ｈの実際の値は何であろうか、恐らく間欠ユーザは次の
理由から約ワン・ラウンドトリップ・ウィンドウ以上の
メッセージ長を有すると考えられる。もし、もっと短い
メツセージであるとすると、先ず初めに最大ウィンドウ
が配分されることはなイカらである。仮想回線のウィン
ドウは約ワン・ラウンドトリップ時間でシャットダウン
されうるので原則としてｈは１に近い。しかし、通信網
が休止を決める前に間欠ユーザーに数秒の考慮時間を与
えてもよいと考えられる。大陸間ラウンドトリップは約
６０ｍ５である。伝送データのラウンドトリップ・ウィ
ンドウ当り３Ｓのアイドル時間はｈ−５０に対応する。
理由から約ワン・ラウンドトリップ・ウィンドウ以上の
メッセージ長を有すると考えられる。もし、もっと短い
メツセージであるとすると、先ず初めに最大ウィンドウ
が配分されることはなイカらである。仮想回線のウィン
ドウは約ワン・ラウンドトリップ時間でシャットダウン
されうるので原則としてｈは１に近い。しかし、通信網
が休止を決める前に間欠ユーザーに数秒の考慮時間を与
えてもよいと考えられる。大陸間ラウンドトリップは約
６０ｍ５である。伝送データのラウンドトリップ・ウィ
ンドウ当り３Ｓのアイドル時間はｈ−５０に対応する。
６Ｓのアイドル時間はｈ−１００に対応する。
一定のデフォルトウィンドウが所定の点景上、各回線に
割当てられるとすると、その点において、全バッファ使
用率カーブは直線となる。初めのＫのユーザは以上のよ
うに計算されたウィンドウが与えられると仮定すると、
残りＮ−にのユーザはサイズΔのウィンドウが与えられ
る。すると、Ｎのユーザに必要とする全バッファスペー
スは次式％式％） （５）式の右辺はＷｋ−１≧Δである限り、Ｋと共に増
加する。実際上にの最大値、例えばに２で、（８）式が
満足されるものであるが、を選択する。
割当てられるとすると、その点において、全バッファ使
用率カーブは直線となる。初めのＫのユーザは以上のよ
うに計算されたウィンドウが与えられると仮定すると、
残りＮ−にのユーザはサイズΔのウィンドウが与えられ
る。すると、Ｎのユーザに必要とする全バッファスペー
スは次式％式％） （５）式の右辺はＷｋ−１≧Δである限り、Ｋと共に増
加する。実際上にの最大値、例えばに２で、（８）式が
満足されるものであるが、を選択する。
Ｋ ＝ Ｋ ２とおいて計算された全バッファスペース
がメモリの最大量、例えばＢ よりも、各スイッチに与
えられたよりも、もっと大きいことが解ると、Ｋの最大
値、例えばに１で、それにはＢ＜Ｂ、となるものである
が、を選択する。もしに１＜Ｋ ならば、Ｋｌとに２の
間に間欠ユーザがいる場合ある条件下で、ユーザがそう
所望しても、トランクを十分活用できない。勿論Ｂ
＞ＮΔでない限り、Ｎのユーザにデフォルトウィンドウ
を与えることさえできない。
がメモリの最大量、例えばＢ よりも、各スイッチに与
えられたよりも、もっと大きいことが解ると、Ｋの最大
値、例えばに１で、それにはＢ＜Ｂ、となるものである
が、を選択する。もしに１＜Ｋ ならば、Ｋｌとに２の
間に間欠ユーザがいる場合ある条件下で、ユーザがそう
所望しても、トランクを十分活用できない。勿論Ｂ
＞ＮΔでない限り、Ｎのユーザにデフォルトウィンドウ
を与えることさえできない。
ディスクリート理想的ウィンドウサイズＭの異なるディ
スクリートウィンドウサイズがあると仮定する。同時に
存在することのできる仮想回線の最大数をＮであると仮
定する。区切り点の集合、例えば、０＝Ｎｏ＜Ｎｉ＜−
＜ＮＭ＝Ｎ。
スクリートウィンドウサイズがあると仮定する。同時に
存在することのできる仮想回線の最大数をＮであると仮
定する。区切り点の集合、例えば、０＝Ｎｏ＜Ｎｉ＜−
＜ＮＭ＝Ｎ。
を選択したい。またウィンドウサイズの集合、例えばＷ
＞Ｗ ・・・〉Ｗ 、を選択し、次のよう０
１ Ｍ−１ に回線にそれらを割当てたい。アクティブとなる回線に
は次のような最小ウィンドサイズＷｋが与えられる。即
ち、Ｎ１＜ｋ＜Ｎｉ＋１であって、ここでに−１はＷＩ
以上のウィンドウサイズを有する他の回線数である。
＞Ｗ ・・・〉Ｗ 、を選択し、次のよう０
１ Ｍ−１ に回線にそれらを割当てたい。アクティブとなる回線に
は次のような最小ウィンドサイズＷｋが与えられる。即
ち、Ｎ１＜ｋ＜Ｎｉ＋１であって、ここでに−１はＷＩ
以上のウィンドウサイズを有する他の回線数である。
ある特定のＮ１を選択する場合、（２）式を帰納的にＪ
Ｎｉについて解き、そして ｗ、７ｗｏ ＝ １／（ＪＮｉ＋１）。
Ｎｉについて解き、そして ｗ、７ｗｏ ＝ １／（ＪＮｉ＋１）。
からＷ＋を計算することにより（Ｎｉ ＋１）番目の回
線の帯域幅を限定しないＷｌの最小値を得ることができ
る。しかし、前述のクローズド形の近似を用いるとはる
るかに容易である。この近似によって、正規化ウィンド
ウＷｋ−Ｗｋ／Ｗは、次の２次式を満足する。
線の帯域幅を限定しないＷｌの最小値を得ることができ
る。しかし、前述のクローズド形の近似を用いるとはる
るかに容易である。この近似によって、正規化ウィンド
ウＷｋ−Ｗｋ／Ｗは、次の２次式を満足する。
ｈｗｊ’ ＋ （Ｎ；＋１−ｈ）ｗＨ−１＝ Ｏ。
そしてこの解は、
”’ ＝ Ｎ７＋１−ｈ＋［（Ｎ７＋１−ｈ）２＋４ｈ
ｌｌ１２任意の区切り点とウィンドウサイズの集合につ
いて、正規化全バッファ使用率ｂ −Ｂ ／Ｗｏは、こ
こで処理できる区切り点Ｍ−１について、もしくはその
代わりに処理できるウィンドウサイズＭ１について、ｂ
を最小にしたい。順次各Ｗｊについて（１）式の右辺を
微分し、モしてＮｉはＷｌ 、のみに依存すると、次式を得る。
ｌｌ１２任意の区切り点とウィンドウサイズの集合につ
いて、正規化全バッファ使用率ｂ −Ｂ ／Ｗｏは、こ
こで処理できる区切り点Ｍ−１について、もしくはその
代わりに処理できるウィンドウサイズＭ１について、ｂ
を最小にしたい。順次各Ｗｊについて（１）式の右辺を
微分し、モしてＮｉはＷｌ 、のみに依存すると、次式を得る。
（Ｗｋ−Ｉ Ｗｋ）（１？’Ｊｋ／ｄｗｋ＋Ｎｋ＋＋
＝Ｎｋ＝０但し、ｋ＝１、２，・・・１Ｍ−１ さらに（１１）式を微分することにより次式を得る。
＝Ｎｋ＝０但し、ｋ＝１、２，・・・１Ｍ−１ さらに（１１）式を微分することにより次式を得る。
ｈ−ｏの場合は特に簡単である。もしＭの異なるウィン
ドウサイズがあるとする場合、１とＮ＋１の間のＭ−１
の幾何平均として、Ｎ１＋１．Ｎｉ＋１ ・・・ の値
を選択するとＮの仮想回線により使用される全バッファ
スペースＢが最小化されることは容易に示される。従っ
て、 Ｎｉ ＋１− （Ｎ＋１） ｊ／Ｍｉ−０，１，・・・
１Ｍ。
ドウサイズがあるとする場合、１とＮ＋１の間のＭ−１
の幾何平均として、Ｎ１＋１．Ｎｉ＋１ ・・・ の値
を選択するとＮの仮想回線により使用される全バッファ
スペースＢが最小化されることは容易に示される。従っ
て、 Ｎｉ ＋１− （Ｎ＋１） ｊ／Ｍｉ−０，１，・・・
１Ｍ。
であり、バッファスペースの最小値は次式を満足Ｂ／Ｗ
Ｏ＝ Ｍ［（Ｎ＋ １）””−１１（１７）式において
、もしＮが大きいならば、及びもしウィンドウサイズの
数Ｍをユーザ数Ｎに等しく選ぶならば、（１７）式の右
辺は近似的に１０ｇＮとなることが示される。
Ｏ＝ Ｍ［（Ｎ＋ １）””−１１（１７）式において
、もしＮが大きいならば、及びもしウィンドウサイズの
数Ｍをユーザ数Ｎに等しく選ぶならば、（１７）式の右
辺は近似的に１０ｇＮとなることが示される。
もしｈがゼロでないならば、（１４）式は数値的に解く
ことができるＭ−１の式の系である。最も簡単な方法は
、Ｎ１の任意の出発値から順次Ｎ２、・・・” Ｍ−１
を計算し、その結果、全系を次式％式％ ここで、Ｎは仮想回線の最大数である。（１８）式を満
足するＮ１の値を根を求める方法、例えば２等分法によ
り所望するだけ正確に求めることができる。
ことができるＭ−１の式の系である。最も簡単な方法は
、Ｎ１の任意の出発値から順次Ｎ２、・・・” Ｍ−１
を計算し、その結果、全系を次式％式％ ここで、Ｎは仮想回線の最大数である。（１８）式を満
足するＮ１の値を根を求める方法、例えば２等分法によ
り所望するだけ正確に求めることができる。
セルバッファサイズの変更：第１３図
既に説明のように、仮想回線に対するセルバラする。
ファサイズの変更の要求はふくそう制御情報の形をとる
。この情報は仮想回線経由で送られる各セルのヘッダー
に組込まれるか、または別個のふくそう制御セルに含ま
れる。
。この情報は仮想回線経由で送られる各セルのヘッダー
に組込まれるか、または別個のふくそう制御セルに含ま
れる。
第１３図は好ましい実施例として、ふくそう制御情報１
３０１を示す図である。フィールドＲＲ１３０３は要求
・応答ビット、フィールド５ＮＩ３０５はシーケンスピ
ット、残りのビットはウィンドウサイズ・フィールド１
３０７を形成し、これはノード１１４におけるセルバッ
ファサイズを示す。
３０１を示す図である。フィールドＲＲ１３０３は要求
・応答ビット、フィールド５ＮＩ３０５はシーケンスピ
ット、残りのビットはウィンドウサイズ・フィールド１
３０７を形成し、これはノード１１４におけるセルバッ
ファサイズを示す。
好ましい実施例として、ふくそう制御情報１３０１はセ
ルヘッダーの一部であり、フィールドを次のように用い
る。即ち、仮想回線に対するノード１１４のセルバッフ
ァサイズの変更を要求するために、ルータ１１０は仮想
回線に属する各出力セルにふくそう制御情報１３０１を
セットする。
ルヘッダーの一部であり、フィールドを次のように用い
る。即ち、仮想回線に対するノード１１４のセルバッフ
ァサイズの変更を要求するために、ルータ１１０は仮想
回線に属する各出力セルにふくそう制御情報１３０１を
セットする。
その結果、ＲＲ１３０１は要求を示し、フィールドＳＮ
Ｉ ３０５はサイズ変更の最終要求のもの以外のシーケ
ンス番号を有し、及びフィールド１３０７は所望のウィ
ンドウサイズを有する。もし要求がウィンドウサイズの
縮減である場合、ルータ１１０はまず仮想回線へのセル
のフローを新しいウィンドウサイズとコンパチブルな速
度に減少し、次に縮減要求を行う。もし要求がウィンド
ウサイズの増加の場合、ルータ１１０はルータ１２０か
らウィンドウの増加できるサイズを示すふくそう制御情
報１３０１を受信するまでセルのフローを増加しない。
Ｉ ３０５はサイズ変更の最終要求のもの以外のシーケ
ンス番号を有し、及びフィールド１３０７は所望のウィ
ンドウサイズを有する。もし要求がウィンドウサイズの
縮減である場合、ルータ１１０はまず仮想回線へのセル
のフローを新しいウィンドウサイズとコンパチブルな速
度に減少し、次に縮減要求を行う。もし要求がウィンド
ウサイズの増加の場合、ルータ１１０はルータ１２０か
らウィンドウの増加できるサイズを示すふくそう制御情
報１３０１を受信するまでセルのフローを増加しない。
各ノード１１４に対するメモリは、ノードを通る各仮想
回線について仮想回線のウィンドウサイズを調節するの
に最後に使われたふくそう制御情報のコピーを含む。以
下これをノードに対する現ふくそう制御情報と呼ぶ。任
意の仮想回線に属するセルがノード１１４を通る際は、
いつもコントローラ２１２はセルのヘッダーに現ふくそ
う制御情報をコピーする。
回線について仮想回線のウィンドウサイズを調節するの
に最後に使われたふくそう制御情報のコピーを含む。以
下これをノードに対する現ふくそう制御情報と呼ぶ。任
意の仮想回線に属するセルがノード１１４を通る際は、
いつもコントローラ２１２はセルのヘッダーに現ふくそ
う制御情報をコピーする。
ノード１１４がセルを受取ると、ふくそう制御情報をセ
ルから取出しモニタ２００に送る。もしふくそう制御情
報１３０１が要求を示すＲＲフィールド１３０３と現ふ
くそう制御情報のそれと異なるＳＮフィールド１３０５
を有する場合、モニタ２００はウィンドウサイズ・フィ
ールド１３０７に指定のサイズのウィンドウを、どの位
与えることができるかを決める。そうして、現ふくそう
制御情報を入力要求のＲＲとＳＮの値に、そしてＷ３１
３０７の値を決めた値にセットする。その時からノード
４１４をでる仮想回線に対する全てのセルのヘッダーは
新しい現ふくそう制御情報のコピーを有することになる
。
ルから取出しモニタ２００に送る。もしふくそう制御情
報１３０１が要求を示すＲＲフィールド１３０３と現ふ
くそう制御情報のそれと異なるＳＮフィールド１３０５
を有する場合、モニタ２００はウィンドウサイズ・フィ
ールド１３０７に指定のサイズのウィンドウを、どの位
与えることができるかを決める。そうして、現ふくそう
制御情報を入力要求のＲＲとＳＮの値に、そしてＷ３１
３０７の値を決めた値にセットする。その時からノード
４１４をでる仮想回線に対する全てのセルのヘッダーは
新しい現ふくそう制御情報のコピーを有することになる
。
ウィンドウサイズの決定は次の通りである。もし仮想回
線に対する要求の指定サイズが現ウィンドウより小さい
場合、モニタ２００は単にこの要求を仮想回線に対する
現ふくそう制御情報にコピーする。もしこの指定サイズ
が現ウィンドウより大きく、ノード１１４がこの指定サ
イズのセルバッファを提供できる場合、モニタ２００は
再び単に、この要求を仮想回線に対する現ふくそう制御
情報にコピーする。もしこの指定サイズが大きいか、ノ
ード１１４がウィンドウサイズ・フィールド１３０７に
示されたサイズのウィンドウを提供できない場合、モニ
タ２００は提供できるウィンドウのサイズを決め、コン
トローラ２１２における現ふくそう制御情報にこの要求
をコピーするが、提供できるウィンドウサイズを示すよ
うウィンドウサイズ１３０７を変更する。ノード１１４
が提供できるウィンドウサイズを決める方法を以下にさ
らに詳しく説明する。
線に対する要求の指定サイズが現ウィンドウより小さい
場合、モニタ２００は単にこの要求を仮想回線に対する
現ふくそう制御情報にコピーする。もしこの指定サイズ
が現ウィンドウより大きく、ノード１１４がこの指定サ
イズのセルバッファを提供できる場合、モニタ２００は
再び単に、この要求を仮想回線に対する現ふくそう制御
情報にコピーする。もしこの指定サイズが大きいか、ノ
ード１１４がウィンドウサイズ・フィールド１３０７に
示されたサイズのウィンドウを提供できない場合、モニ
タ２００は提供できるウィンドウのサイズを決め、コン
トローラ２１２における現ふくそう制御情報にこの要求
をコピーするが、提供できるウィンドウサイズを示すよ
うウィンドウサイズ１３０７を変更する。ノード１１４
が提供できるウィンドウサイズを決める方法を以下にさ
らに詳しく説明する。
以上から明らかなように、ルータ１１０により要求に対
するふくそう制御情報１３０１を有するセルがルータ１
２０に達すると、ウィンドウサイズ１３０７はノード４
のいずれもが提供できる最小ウィンドウサイズを示す。
するふくそう制御情報１３０１を有するセルがルータ１
２０に達すると、ウィンドウサイズ１３０７はノード４
のいずれもが提供できる最小ウィンドウサイズを示す。
次にルータ１２０はルータ１２０においてバッファスペ
ースの使用できる可能性から、さらにライインドウサイ
ズの減少が必要かどうかを判別する。ウィンドウサイズ
を決めた後、ルータ１２０は仮想回線を経由して送るセ
ルのふくそう制御フィールド１３０１を次のようにセッ
トする。ＲＲ１３０７は応答を示すようにセットされる
。５Ｎ１３０５は同一のままで変わらない。ＷＳ１３０
７はノード１１４のいずれかにより指定の最小ウィンド
ウサイズのいずれかにセットされる。各ノード１１４が
応答メツセージを受取ると、ウィンドウサイズ・フィー
ルド１３０７の指定のように仮想回線に対するセルバッ
ファサイズをセットし、現ふくそう制御情報に応答メツ
セージをコピーし、そして行先ルータ１１０向げに仮想
回線のセルに新しい現制御情報をコピーし始める。ルー
タ１１０はヘッダーが応答メツセージを有する仮想回線
に対するセルを受取ると、ウィンドウサイズ・フィール
ド１３０７に指定のサイズのセルバッファが、全てのノ
ードにおいて仮想回線に対し利用可能であることを知り
、それにより仮想回線にセルのフローを増加する。ルー
タ１１０による次のウィンドウサイズの変更要求は、５
Ｎ１３０５を最後の要求のそれと異なる値にセットする
以外同じように行われる。
ースの使用できる可能性から、さらにライインドウサイ
ズの減少が必要かどうかを判別する。ウィンドウサイズ
を決めた後、ルータ１２０は仮想回線を経由して送るセ
ルのふくそう制御フィールド１３０１を次のようにセッ
トする。ＲＲ１３０７は応答を示すようにセットされる
。５Ｎ１３０５は同一のままで変わらない。ＷＳ１３０
７はノード１１４のいずれかにより指定の最小ウィンド
ウサイズのいずれかにセットされる。各ノード１１４が
応答メツセージを受取ると、ウィンドウサイズ・フィー
ルド１３０７の指定のように仮想回線に対するセルバッ
ファサイズをセットし、現ふくそう制御情報に応答メツ
セージをコピーし、そして行先ルータ１１０向げに仮想
回線のセルに新しい現制御情報をコピーし始める。ルー
タ１１０はヘッダーが応答メツセージを有する仮想回線
に対するセルを受取ると、ウィンドウサイズ・フィール
ド１３０７に指定のサイズのセルバッファが、全てのノ
ードにおいて仮想回線に対し利用可能であることを知り
、それにより仮想回線にセルのフローを増加する。ルー
タ１１０による次のウィンドウサイズの変更要求は、５
Ｎ１３０５を最後の要求のそれと異なる値にセットする
以外同じように行われる。
以上の説明から明らかなように、ルータ１１０はルータ
１２０からの応答を受取るまで待たなければ、再度ウィ
ンドウサイズの調整を要求することはでさない。
１２０からの応答を受取るまで待たなければ、再度ウィ
ンドウサイズの調整を要求することはでさない。
もしあまりに多くのウィンドウサイズがあって、利用で
きるヘッダースペースにコードできない場合、ふくそう
制御情報をヘッダーの単一ビットにより、それぞれマー
クされた特別のふくそう制御情報セルにおけるデータフ
ィールドとして送ることができる。
きるヘッダースペースにコードできない場合、ふくそう
制御情報をヘッダーの単一ビットにより、それぞれマー
クされた特別のふくそう制御情報セルにおけるデータフ
ィールドとして送ることができる。
セルバッファサイズの変更要求時の決定送信ルータ１１
０は、先の要求に対する応答を受取った後、いつでもウ
ィンドウサイズの増加を要求することができるが、好ま
しい実施例においては、ウィンドウサイズの減少要求は
再ネゴシェーション間隔だけ離して行われる。再ネゴシ
ェーション間隔はほぼｈτであるが、ここでτは通信網
における最長ラウンドトリップ時間であり、ｈは先に説
明したアイドル時間のパラメータである。
０は、先の要求に対する応答を受取った後、いつでもウ
ィンドウサイズの増加を要求することができるが、好ま
しい実施例においては、ウィンドウサイズの減少要求は
再ネゴシェーション間隔だけ離して行われる。再ネゴシ
ェーション間隔はほぼｈτであるが、ここでτは通信網
における最長ラウンドトリップ時間であり、ｈは先に説
明したアイドル時間のパラメータである。
前述のように、ｈの実際の値はｈτが少ない秒数になる
ような値である。
ような値である。
次のウィンドウ要求のサイズを決めるために、ルータ１
１０は所定の仮想回線がシステムにおいて有する総数を
見失わぬよう接触を保つ。即ち、これはルータ１１０が
有し、仮想口線を経由して伝送されるのを待つセル数と
、仮想回線に対するノード１１４におけるセル数の和で
ある。後者の数は送られたセル数とアクノレツジされた
セル数の差を見失わ′ぬよう接触を保つことにより推定
することができる。ルータ１１０はまた最後の再ネゴシ
ェーション間隔の間、仮想回線の累積スループットを接
触を保ち見失わぬようにする。ルータ１１０がウィンド
ウを要求する場合、要求されるサイズは次の点から決め
られる。即ち、仮想回線が形成されたとき仮想回線に対
し、セットされたデフォルトウィンドウサイズ、仮想回
線がシステムにおいて有するセルの総数、及びもし回線
が再ネゴシェーション間隔の間、平均スループットに対
応する速度でラウンドトリップ時間中動作をしたとする
場合のワン・ラウンドトリップ時間の間、回線を通った
とするセルの数から決められる。最後の値、ＴＮは次式
から導かれる。
１０は所定の仮想回線がシステムにおいて有する総数を
見失わぬよう接触を保つ。即ち、これはルータ１１０が
有し、仮想口線を経由して伝送されるのを待つセル数と
、仮想回線に対するノード１１４におけるセル数の和で
ある。後者の数は送られたセル数とアクノレツジされた
セル数の差を見失わ′ぬよう接触を保つことにより推定
することができる。ルータ１１０はまた最後の再ネゴシ
ェーション間隔の間、仮想回線の累積スループットを接
触を保ち見失わぬようにする。ルータ１１０がウィンド
ウを要求する場合、要求されるサイズは次の点から決め
られる。即ち、仮想回線が形成されたとき仮想回線に対
し、セットされたデフォルトウィンドウサイズ、仮想回
線がシステムにおいて有するセルの総数、及びもし回線
が再ネゴシェーション間隔の間、平均スループットに対
応する速度でラウンドトリップ時間中動作をしたとする
場合のワン・ラウンドトリップ時間の間、回線を通った
とするセルの数から決められる。最後の値、ＴＮは次式
から導かれる。
ユニでＣＴは、累積スループット、Ｔｏはラウンドトリ
ップ時間、及びＴ は再ネゴシエーシｅｎｅｇ ヨン間隔である。要求サイズは次の点から決められる。
ップ時間、及びＴ は再ネゴシエーシｅｎｅｇ ヨン間隔である。要求サイズは次の点から決められる。
即ち、デフォルト・ウィンドウサイズの最大、システム
におけるセル総数、及びＴＮで、全ラウンドトリップウ
ィンドウまでである。上記計算にＴＮが含まれるのは瞬
間的アイドル状態のために仮想回線のウィンドウを閉鎖
からルータ１１０を防ぐためである。
におけるセル総数、及びＴＮで、全ラウンドトリップウ
ィンドウまでである。上記計算にＴＮが含まれるのは瞬
間的アイドル状態のために仮想回線のウィンドウを閉鎖
からルータ１１０を防ぐためである。
もしルータ１１０がデータの全ラウンドトリップウィン
ドウを、それをサポートする各仮想回線の入力バケット
バッファに収容できない場合、ルータ１１０は仮想回線
に対し、現在のセルウィンドウと少なくとも同じ大きさ
人力バッファを送らねばならず、入力バッファオーバー
フローを見失わぬよう接触を保たねばならない。セルウ
ィンドウサイズの増加の最終要求以降、入力オーバーフ
ローを次のように処理できる。即ち、丁度ウィンドウサ
イズの次の増加要求がある時に、回線がシステムにおい
て全ラウンドトリップに値するデータを有するように処
理できる。
ドウを、それをサポートする各仮想回線の入力バケット
バッファに収容できない場合、ルータ１１０は仮想回線
に対し、現在のセルウィンドウと少なくとも同じ大きさ
人力バッファを送らねばならず、入力バッファオーバー
フローを見失わぬよう接触を保たねばならない。セルウ
ィンドウサイズの増加の最終要求以降、入力オーバーフ
ローを次のように処理できる。即ち、丁度ウィンドウサ
イズの次の増加要求がある時に、回線がシステムにおい
て全ラウンドトリップに値するデータを有するように処
理できる。
ノード１１４におけるセルバッファサイズの決定、第１
４図 ウィンドウＷｏからＷｋ−１の理想的なウィンドウサイ
ズの場合について、上記３式もしくは４式を用いて導い
たウィンドウサイズを回線番号１・・・ｋに対してプロ
ットした結果、得られた曲線１４０５を第１４図に示す
。各モニタ２００の有するテーブルには、各ポテンシャ
ル仮想回線１・・・ｋに対し曲線１４０５に−より求め
られる理想的ウィンドウサイズと、そのポテンシャル仮
想回線番号とが対応付けされる。さらにモニタ２００は
、ノードにおける各仮想回線に配分された現在のセルバ
ッファと、これらの各仮想回線に配分された現在のセル
バッファと、これらの各仮想回線ランクを見失わぬよう
接触を保つが、ここでこのランクは、この回線のセルバ
ッファ配分の順序数である。即ち、配分の最大を有する
回線をランク１、次の最大をランク２、等Ｒとする。も
しＷ がランクｋの回線の現在の配分を表わすとすると
、Ｗ はＷｋ−１以下でなければならない。
４図 ウィンドウＷｏからＷｋ−１の理想的なウィンドウサイ
ズの場合について、上記３式もしくは４式を用いて導い
たウィンドウサイズを回線番号１・・・ｋに対してプロ
ットした結果、得られた曲線１４０５を第１４図に示す
。各モニタ２００の有するテーブルには、各ポテンシャ
ル仮想回線１・・・ｋに対し曲線１４０５に−より求め
られる理想的ウィンドウサイズと、そのポテンシャル仮
想回線番号とが対応付けされる。さらにモニタ２００は
、ノードにおける各仮想回線に配分された現在のセルバ
ッファと、これらの各仮想回線に配分された現在のセル
バッファと、これらの各仮想回線ランクを見失わぬよう
接触を保つが、ここでこのランクは、この回線のセルバ
ッファ配分の順序数である。即ち、配分の最大を有する
回線をランク１、次の最大をランク２、等Ｒとする。も
しＷ がランクｋの回線の現在の配分を表わすとすると
、Ｗ はＷｋ−１以下でなければならない。
仮想回線のウィンドウサイズを要求サイズＷｒに増加す
るよう要求がなされた場合、テーブル、現在のウィンド
ウサイズ、仮想回線のランクを次のように用いて仮想回
線の新しいウィンドウサイズを決める。ふくそう制御情
報１３０１が到着し、任意の仮想回線に対し、セルバッ
ファの拡大を要求する場合、モニタ２００は、まずＷＳ
フィールド１３０７に指定のウィンドウサイズＷ が仮
に与えられたとしたとき、所定の仮想回線が他の仮想回
線に比べ、どのランクを持つことになるかを求める。こ
れは所定の仮想回線の仮説ランクである。所定の仮想回
線の現在のランクから始め、次にモニタ２００は以下の
ようになるまで次に高いランクの各仮想回線とランクを
交換する。即ち、所定の仮想回線が仮説ランクを達成す
るまでか、または交換が次に高い仮想回線に対して、現
在のセルバッファサイズと、不一致のランクを次の高い
仮想回線に与える必要があるまでランクを交換する。こ
の不一致は、テーブルを用いて次のように求める。次に
高い仮想回線に対する新しいランクとしてテーブルの数
１．・・・、にの１つを用いる。
るよう要求がなされた場合、テーブル、現在のウィンド
ウサイズ、仮想回線のランクを次のように用いて仮想回
線の新しいウィンドウサイズを決める。ふくそう制御情
報１３０１が到着し、任意の仮想回線に対し、セルバッ
ファの拡大を要求する場合、モニタ２００は、まずＷＳ
フィールド１３０７に指定のウィンドウサイズＷ が仮
に与えられたとしたとき、所定の仮想回線が他の仮想回
線に比べ、どのランクを持つことになるかを求める。こ
れは所定の仮想回線の仮説ランクである。所定の仮想回
線の現在のランクから始め、次にモニタ２００は以下の
ようになるまで次に高いランクの各仮想回線とランクを
交換する。即ち、所定の仮想回線が仮説ランクを達成す
るまでか、または交換が次に高い仮想回線に対して、現
在のセルバッファサイズと、不一致のランクを次の高い
仮想回線に与える必要があるまでランクを交換する。こ
の不一致は、テーブルを用いて次のように求める。次に
高い仮想回線に対する新しいランクとしてテーブルの数
１．・・・、にの１つを用いる。
そして、もしその数に対し指定されたセルバッファサイ
ズが、次に高い仮想回線に対する現在のセルバッファサ
イズより小さい場合、次に高い仮想回線が降格されるラ
ンクは不一致である。
ズが、次に高い仮想回線に対する現在のセルバッファサ
イズより小さい場合、次に高い仮想回線が降格されるラ
ンクは不一致である。
ランク交換シリーズの最終に所定の仮想回線の有するラ
ンクをｊとすると、回線はｌ１ｉｎ （Ｗ 。
ンクをｊとすると、回線はｌ１ｉｎ （Ｗ 。
Ｗｊ−１）に等しい配分を実際に受取り、最終ランクは
最終配分と一致する。もし配分減少を要求する場合、減
少は自動的に与えられ、回線のランクは一致が得られる
まで低いランクを有する回線と交換される０＝度モニタ
２００が、新しいバッファ配分を決めると、前述のよう
に現ふくそう制御情報をセットする。そして、次のノー
ド１１４は説明したように、このノード１１４を通った
仮想回線に対し、セルのヘッダーにおけるふくそう制御
情報に応答する。
最終配分と一致する。もし配分減少を要求する場合、減
少は自動的に与えられ、回線のランクは一致が得られる
まで低いランクを有する回線と交換される０＝度モニタ
２００が、新しいバッファ配分を決めると、前述のよう
に現ふくそう制御情報をセットする。そして、次のノー
ド１１４は説明したように、このノード１１４を通った
仮想回線に対し、セルのヘッダーにおけるふくそう制御
情報に応答する。
第１４図は増加例を示す。同図において、各垂直線１４
０７Ａ、・・・、Ｄは仮想回線を示す。この線の長さは
仮想回線に現ウィンドウサイズを表わす。パネル１４０
１において、回線Ａ、Ｂ、Ｃ。
０７Ａ、・・・、Ｄは仮想回線を示す。この線の長さは
仮想回線に現ウィンドウサイズを表わす。パネル１４０
１において、回線Ａ、Ｂ、Ｃ。
及びＤはランク順であり、各仮想回線１４０７に対する
セルバッファサイズは曲線１４０４に関する曲線の位置
と一致する。次にモニタ２００は、仮想回線りに対する
ふくそう制御情報１３０１を受取るが、これは点線ラベ
ルの１４０９により示されるように、仮想回線に対し、
全ラウンドトリップ・ウィンドウＷｏを要求するもので
ある。直線１４０９が曲線１４０５の上に伸びているこ
とに示されるように、このように要求されたウィンドウ
サイズは、ランク４を有する仮想回線に対して、曲線１
４０５が許容するものより大きい。従って、仮想回線り
はまず仮想回線Ｃと交換され、次に仮想回線Ｂと交換さ
れる。どちらの場合も、交換された仮想回線の降格によ
り、次のように線が曲線と交わることを起こさない。即
ち、降格された仮想回線のセルバッファサイズを示す線
が曲線１４０５と交わる。即ち、新しいランクは、降格
された仮想回線の現在のセルバッファサイズと一致する
。しかし、仮想回線Ａとの交換を試行する場合、仮想回
線Ａの降格の結果不一致となる。
セルバッファサイズは曲線１４０４に関する曲線の位置
と一致する。次にモニタ２００は、仮想回線りに対する
ふくそう制御情報１３０１を受取るが、これは点線ラベ
ルの１４０９により示されるように、仮想回線に対し、
全ラウンドトリップ・ウィンドウＷｏを要求するもので
ある。直線１４０９が曲線１４０５の上に伸びているこ
とに示されるように、このように要求されたウィンドウ
サイズは、ランク４を有する仮想回線に対して、曲線１
４０５が許容するものより大きい。従って、仮想回線り
はまず仮想回線Ｃと交換され、次に仮想回線Ｂと交換さ
れる。どちらの場合も、交換された仮想回線の降格によ
り、次のように線が曲線と交わることを起こさない。即
ち、降格された仮想回線のセルバッファサイズを示す線
が曲線１４０５と交わる。即ち、新しいランクは、降格
された仮想回線の現在のセルバッファサイズと一致する
。しかし、仮想回線Ａとの交換を試行する場合、仮想回
線Ａの降格の結果不一致となる。
従って、仮想回線りはランク２が与えられ、そのセルバ
ッファサイズは、曲線１４０５がそのランクに対し許容
する最大にセットされる。この結果は、パネル１４０３
に示される。回線りの新しいセルバッファサイズは、他
の回線と競争して帯域幅のかなりのシェアを与える。曲
線１４０５はノードにおいて、セルバッファの特に好都
合で有効な配分の結果を与えるが、今述べた方法を仮想
回線ｉ＋１に対するウィンドウが仮想回線ｉに対するそ
れより小さい、ｌ＜ｉ＜ｋの場合の他の曲線についても
用いることができる。
ッファサイズは、曲線１４０５がそのランクに対し許容
する最大にセットされる。この結果は、パネル１４０３
に示される。回線りの新しいセルバッファサイズは、他
の回線と競争して帯域幅のかなりのシェアを与える。曲
線１４０５はノードにおいて、セルバッファの特に好都
合で有効な配分の結果を与えるが、今述べた方法を仮想
回線ｉ＋１に対するウィンドウが仮想回線ｉに対するそ
れより小さい、ｌ＜ｉ＜ｋの場合の他の曲線についても
用いることができる。
（結論）
以上の詳細説明は、本技術分野の当業者がセルでデータ
を伝送する仮想回線通信網において、如何にふくそうを
制御するかを開示したものである。
を伝送する仮想回線通信網において、如何にふくそうを
制御するかを開示したものである。
特に、本詳細説明は通信網のノードにおいて、仮想回線
に対するセルバッファのウィンドウサイズの選択方法の
改善、仮想回線がセルバッファサイズの変更を必要とす
るその時の決定方法の改善、及び仮想回線に対し、セル
バッファサイズの変更要求に、ノードがどう対応すべき
かを決める方法の改善を開示したものである。
に対するセルバッファのウィンドウサイズの選択方法の
改善、仮想回線がセルバッファサイズの変更を必要とす
るその時の決定方法の改善、及び仮想回線に対し、セル
バッファサイズの変更要求に、ノードがどう対応すべき
かを決める方法の改善を開示したものである。
さらに本詳細説明は、本発明の実施に際し、現時点で本
発明の知る最良の方法を本願に開示したものである。し
かし、本説明から明らかなように、本発明の精神と原理
から逸脱することなく、本技術分野の当業者に明らかな
ように、他の方法で本発明を実施することも可能である
。例えば、セルバッファサイズの変更信号に他の方法を
適用し、ふくそう制御情報に異なる形を与え、また曲線
１４０５以外の曲線を用いることにより、ノードにおけ
るバッファサイズの選択を制御することができる。従っ
て、本詳細説明は全て説明のための例示であって、本発
明を限定するものではなく、本発明は添付フレイムにお
いて限定した以外は、その特定の実施態様に制約される
ものではない。
発明の知る最良の方法を本願に開示したものである。し
かし、本説明から明らかなように、本発明の精神と原理
から逸脱することなく、本技術分野の当業者に明らかな
ように、他の方法で本発明を実施することも可能である
。例えば、セルバッファサイズの変更信号に他の方法を
適用し、ふくそう制御情報に異なる形を与え、また曲線
１４０５以外の曲線を用いることにより、ノードにおけ
るバッファサイズの選択を制御することができる。従っ
て、本詳細説明は全て説明のための例示であって、本発
明を限定するものではなく、本発明は添付フレイムにお
いて限定した以外は、その特定の実施態様に制約される
ものではない。
第１図は、ユーザパケットホストソースを行き先に接続
する複数の交換ノードを有する代表的データ交換通信網
のアーキテクチャを示す図、第２図は、個別仮想回線に
対応する複数の多重化タイムスロットを有する受信チャ
ネルに対するノードにおけるデータ受信とキューイング
構成の詳細を示す図、 第３図は、受信チャネル上仮想回線のバッフ７スーベー
ス配分とデータキューイングを処理する第２図のコント
ローラの詳細を示す図、第４図は、ホストからの可変長
データパケット定長データセルの間を変換し、さらにル
ータにおけるバッファスペース配分と、データキューイ
ングを処理するルータの詳細を示す図、 第５図は、ルータもしくは交換ノードにおいて、仮想回
線に対するデータのバッファ長を決める方法を示す図、 第６図および第７図は、ダイナミックバッファ配分に対
する判断基準として入力データにおけるバッファ長を用
いる実施例の場合、ルータとノードにおいて仮想回線に
対し、ダイナミックに配分スルバッファスペースのルー
タとノードにおいて実施のプロトコルと方法ステップを
示すフローチャート図、 第８図ないし第１２図は、判断基準としてルータにおけ
るバッファ長と共にノードにおけるバッファ長を用いる
実施例の場合に仮想回線に固定もしくは可変サイズのブ
ロックでバッファスペースを配分するのにルータとノー
ドで実施のプロトコルと方法ステップを示すフローチャ
ート図である。 第１３図は、ふくそう制御フィールドを示す図、及び 第１４図は、要求に応答してセルバッファサイズを調節
する方法を示す図である。 １００・・・セル通信網 １０２・・・ソース １０６・・・ローカルエリア通信網 １１０・・・ルータ １１４・・・交換ノード １１６・・・データリンク １２０・・・ルータ １２４・・・ローカルエリア通信網 １２８・・・行き先 ２００・・・モータ ２０２・・・受信機 ２０４・・・送信機 ２０６・・・ＦＩＦＯ ２１０・・・セルキュー ２１２・・・コントローラ ２１４・・・ＦＩＦＯ ３００・・・アービタ ３０２・・・ＭＵＸ （マルチプレクサ）３０４・・・
テーブル ３０６・・・テーブル ３０８・・・レジスタ ３１０・・・レジスタ ＦｒＧ。 ３１４・・・コンパレータ ３１６・・・カウンタ ３１８・・・コンパレータ ３２４・・・レジスタ ４００・・・受信機 ４０２・・・回線 ４０４・・・回線 ４０６・・・セルキュー ４０８・・・回線 ４１０・・・コントローラ ４１２・・・モニタ ４１４・・・受信機 ４１５・・・送信機 ４１８・・・回線 ４２４・・・回線 ４２６・・・回線 出 願 人：アメリカン テレグラフ テレフォン カムバニ− アンド ＦＩＧ、 ２ ＦＩＧ、 ５ ＦＩＧ、 ７ ＦＩｏ、 ８ 送信ルータ ＦＩｏ、 ９
する複数の交換ノードを有する代表的データ交換通信網
のアーキテクチャを示す図、第２図は、個別仮想回線に
対応する複数の多重化タイムスロットを有する受信チャ
ネルに対するノードにおけるデータ受信とキューイング
構成の詳細を示す図、 第３図は、受信チャネル上仮想回線のバッフ７スーベー
ス配分とデータキューイングを処理する第２図のコント
ローラの詳細を示す図、第４図は、ホストからの可変長
データパケット定長データセルの間を変換し、さらにル
ータにおけるバッファスペース配分と、データキューイ
ングを処理するルータの詳細を示す図、 第５図は、ルータもしくは交換ノードにおいて、仮想回
線に対するデータのバッファ長を決める方法を示す図、 第６図および第７図は、ダイナミックバッファ配分に対
する判断基準として入力データにおけるバッファ長を用
いる実施例の場合、ルータとノードにおいて仮想回線に
対し、ダイナミックに配分スルバッファスペースのルー
タとノードにおいて実施のプロトコルと方法ステップを
示すフローチャート図、 第８図ないし第１２図は、判断基準としてルータにおけ
るバッファ長と共にノードにおけるバッファ長を用いる
実施例の場合に仮想回線に固定もしくは可変サイズのブ
ロックでバッファスペースを配分するのにルータとノー
ドで実施のプロトコルと方法ステップを示すフローチャ
ート図である。 第１３図は、ふくそう制御フィールドを示す図、及び 第１４図は、要求に応答してセルバッファサイズを調節
する方法を示す図である。 １００・・・セル通信網 １０２・・・ソース １０６・・・ローカルエリア通信網 １１０・・・ルータ １１４・・・交換ノード １１６・・・データリンク １２０・・・ルータ １２４・・・ローカルエリア通信網 １２８・・・行き先 ２００・・・モータ ２０２・・・受信機 ２０４・・・送信機 ２０６・・・ＦＩＦＯ ２１０・・・セルキュー ２１２・・・コントローラ ２１４・・・ＦＩＦＯ ３００・・・アービタ ３０２・・・ＭＵＸ （マルチプレクサ）３０４・・・
テーブル ３０６・・・テーブル ３０８・・・レジスタ ３１０・・・レジスタ ＦｒＧ。 ３１４・・・コンパレータ ３１６・・・カウンタ ３１８・・・コンパレータ ３２４・・・レジスタ ４００・・・受信機 ４０２・・・回線 ４０４・・・回線 ４０６・・・セルキュー ４０８・・・回線 ４１０・・・コントローラ ４１２・・・モニタ ４１４・・・受信機 ４１５・・・送信機 ４１８・・・回線 ４２４・・・回線 ４２６・・・回線 出 願 人：アメリカン テレグラフ テレフォン カムバニ− アンド ＦＩＧ、 ２ ＦＩＧ、 ５ ＦＩＧ、 ７ ＦＩｏ、 ８ 送信ルータ ＦＩｏ、 ９
Claims (32)
- （１）１つ以上のノードを有する仮想回線データ通信網
において、 ノードからの任意のリンクを用いてｋ番目の仮想回線に
対し、ノードにおけるウィンドウサイズＷ＿ｋ＿−＿１
を決める方法であって、 この方法は、 ｋ番目の仮想回線の追加に先立って、リンクを用いてア
クティブ仮想回線Ｊ＿ｋ＿−＿１平均数を決めるステッ
プと、 式 Ｗ＿ｋ＿−＿１／Ｗ＿０＝１／（Ｊ＿ｋ＿−＿１＋１）
（Ｗ＿０は最高速度ラウンドトリップウィンドウ）から
ｋ番目の仮想回線に対するウィンドウサイズＷ＿ｋ＿−
＿１を決めるステップ、 とからなることを特徴とするウィンドウサイズの決定方
法。 - （２）間欠に使用する仮想回線は、アクティブに使用す
る場合の平均サービス時間の条件τと、平均アイドル時
間ｈτを有し、 アクティブ仮想回線Ｊ＿ｋ＿−＿１平均数を決めるステ
ップを、Ｊ＿０−０から出発する漸化式 Ｊ＿ｋ＿−＿１＋１／Ｊ＿ｋ＿−＿１＋ｈ＝Ｊｋ／ｋを
用いて行うことを特徴とする請求項１記載の方法。 - （３）間欠に使用する仮想回線は、アクティブに使用す
る場合の平均サービス時間の条件τと、平均アイドル時
間ｈτを有し、 アクティブ仮想回線Ｊ＿ｋ＿−＿１平均数を決めるステ
ップを、Ｊ＿ｋ＿−＿１について、近似式 ｋ−ｈ＋［（ｋ−ｈ）＾２＋４ｈ］＾１＾／＾２−２／
２を用いて行うことを特徴とする請求項１記載の方法。 - （４）アクティブ仮想回線平均数を決めるステップを、
通信網の最長ラウンドトリップ時間をτ、及びｈτが少
ない秒数であるようなｈの値を用いて行うことを特徴と
する請求項３記載の方法。 - （５）１つ以上のノードを有する仮想回線データ通信網
において、 ノードからの任意のリンクを用いて、ｋ番目の仮想回線
に対し、ノードにおけるウィンドウサイズＷ＿ｋ＿−＿
１を決める方法であって、 この方法は、 一定のウィンドウサイズ数があることを決めるステップ
と、 通信網に同時に存在することのできる仮想回線数Ｎを、
０＝Ｎ＿０＜Ｎ＿１＜・・・＜Ｎ＿Ｍ＝Ｎとなるように
Ｍ＋１区切り点の集合に分けるステップと、Ｍのウィン
ドウサイズＷ＿０＞Ｗ＿１＞・・・＞Ｗ＿Ｍ＿−＿１を
Ｎ＿ｉがＷ＿ｉに対応するように、Ｎ＿０ないしＮ＿Ｍ
＿−＿１の区切り点と対応付けするステップと、ｋ番目
の仮想回線の追加に先立ってリンクを用いて、アクティ
ブ仮想回線Ｊ＿Ｎ＿ｉ平均数を決めるステップと、 式 Ｗ＿ｉ／Ｗ＿０＝１／Ｊ＿Ｎ＿＿ｉ＋１ （Ｎ＿ｉ＜ｋ≦Ｎ＿ｉ＿＋＿１であり、Ｗ＿０は最高速
度ラウンドトリップウィンドウ） から仮想回線Ｎ＿ｉに対応するウィンドウサイズＷを決
めるステップ、 とからなることを特徴とするウィンドウサイズの決定方
法。 - （６）間欠に使用する仮想回線は、アクティブに使用す
る場合の平均サービス時間の条件τと、平均アイドル時
間ｈτを有し、 アクティブ仮想回線Ｊ＿Ｎ＿ｉ平均数を決めるステップ
をＪ＿０＝０から出発し、各Ｊ＿Ｎ＿ｉに対してのみ結
果を保持する漸化式 Ｊ＿ｋ＿−＿１＋１／Ｊ＿ｋ＿−＿１＋１＋ｈ＝Ｊ＿ｋ
／ｋを用いて行うことを特徴とする請求項５記載の方法
。 - （７）間欠に使用する仮想回線は、アクティブに使用す
る場合の平均サービス時間の条件τと、平均アイドルｈ
τを有し、 アクティブ仮想回線Ｊ＿Ｎ＿ｉ平均数を決めるステップ
をＪ＿Ｎ＿ｉについて近似式 Ｎｉ＋１−ｈ＋［（Ｎ＿ｉ＋１−ｈ）＾２＋４ｈ］＾１
＾／＾２−２／２を用いて行うことを特徴とする請求項
５記載の方法。 - （８）アクティブ仮想回線平均数を決めるステップを、
通信網の最長ラウンドトリップ時間をτ、及びｈτが少
ない秒数であるようなｈの値を用いて行う、 ことを特徴とする請求項７記載の方法。 - （９）正規化した全バッファ使用率ｂを、ｋ＝１、２、
・・・、Ｍ−１についての式 （Ｗ＿ｋ＿−＿１−Ｗ＿ｋ）ｄＮ＿ｋ／ｄＷ＿ｋ＋Ｎ＿
ｋ＿＋＿１−Ｎ＿ｋ＝０、但し、 ｄＮ＿ｋ／ｄＷ＿ｋ＝２ｈｗ＿ｋ＋Ｎ＿ｋ＋１−ｈ／Ｗ
＿ｋの系を解くことにより最小とする、 ことを特徴とする請求項８記載の方法。 - （１０）データをセルに転送して、エッジに発する任意
の仮想回線に対し、通信網において要求されるウィンド
サイズを決める仮想回線データ通信網のエッジを用いる
方法であって、 この方法は、 所定の仮想回線がエッジで有するセルＴＣの総数を通信
網において見失わぬよう接触を保つステップと、 非常に新しい再ネゴシェーション間隔の間、所定の仮想
回線のセルの累積するスループットＣＴを見失わぬよう
接触を保つステップと、 多数のセルを収容できる十分に大きい通信網において、 ラウンドトリップ時間を最も新しい再ネゴシェーション
間隔の長さで割った商を、ＣＴ倍した積とＴＣの大きい
方である仮想回線に対するウィンドウを要求するステッ
プ、 とからなることを特徴とするエッジで用いる方法。 - （１１）エッジにおいて、所定の仮想回線に対するセル
バッファがオーバーフローするかどうかを見失わぬよう
に接触を保つステップと、もし再ネゴシェーション間隔
の間、セルバッファがオーバーフローする場合、ウィン
ドウ要求ステップにおいて、 全ラウンドトリップウィンドウを要求するステップをさ
らに有する、 ことを特徴とする請求項１０記載の方法。 - （１２）要求ウィンドウが現ウィンドウより大きいとき
、ウィンドウに対する未定のままの要求がない場合、何
時でもウィンドウを要求するステップを行い、及び要求
ウィンドウが現ウィンドウより小さいとき、現在の再ネ
ゴシェーション間隔の終了するまで、ウィンドウを要求
するステップを行わない、 ことを特徴とする請求項１０記載の方法。 - （１３）再ネゴシェーション間隔は、少ない秒数である
ことを特徴とする請求項１０ないし請求項１２のいずれ
かに記載の方法。 - （１４）仮想回線通信網のノードにおいて、使用するウ
ィンドウのサイズを決める方法であって、この方法は、 ノードにおける異なるサイズのウィンドウの要求に応答
して、ノードからの任意のリンクを用いにの仮想回線の
任意の１つに対し、ノードにおけるウィンドウのサイズ
を決める方法であり、この方法は、 各に仮想回線が、機能により名称が付与される最大ウィ
ンドウを決め、それにより仮想回線ｊに対する最大ウィ
ンドウが、仮想回線ｊ＋１に対する最大ウィンドウより
大きく、１＜ｊ＜ｋであることを決めるステップと、 ノードにおける各仮想回線に対するウィンドウと、ウィ
ンドウの現サイズについて、各仮想回線のランクを決め
るステップと、 もし仮にそのウィンドウが要求サイズであると仮定した
場合に、その所定の仮想回線が有するとされるポテンシ
ャルランクを決めるステップと、所定の仮想回線がポテ
ンシャルランクを達成するまで、もしくは所定の仮想回
線のランクのさらなる変更が、次のランキングの仮想回
線のランクを以下に示すようなランクに変更することを
必要とするまで、即ち、次にランクされた仮想回線の現
ウィンドウサイズが、その交換の結果、次にランクされ
た仮想回線が受取るランクの最大ウィンドウより大きい
ようなランクに変更することを必要とするまで、所定の
仮想回線のランクを次のランキングの仮想回線のそれと
必要とする方向に交換することにより、ポテンシャルラ
ンクにより必要とされる方向に、所定の仮想回線のラン
クを変更するステップと、 ウィンドウサイズを要求ウィンドサイズと、所定の仮想
回線により達成された最終ランクに対する最大ウィンド
ウの小さい方であるように、所定の仮想回線のウィンド
ウサイズを決めるステップ、からなることを特徴とする
ウィンドウサイズの決定方法。 - （１５）任意の仮想回線ｉは、名称が付与される最大ウ
ィンドウＷ＿ｉ＿−＿１を決めるステップは、ノードか
らのリンクを用いてアクティブ仮想回線Ｊ＿ｉ＿−＿１
平均数を決めるステップと、式 Ｗ＿ｉ＿−＿１／Ｗ＿０＝１／Ｊ＿ｉ＿−＿１−１を用
いて、最大ウィンドウＷ＿ｉ＿−＿１を決めるステップ
、 とからなることを特徴とする請求項１４記載の方法。 - （１６）間欠に使用する仮想回線は、アクティブに使用
する場合の平均サービス時間の条件τと、平均アイドル
時間ｈτを有し、及び アクティブ仮想回線Ｊ＿ｉ＿−＿１平均数を決めるステ
ップを、Ｊ＿０＝０から出発する漸化式 Ｊ＿ｉ＿−＿１＋１／Ｊ＿ｉ＿−＿１＋１＋ｈ＝Ｊ＿ｉ
／ｉを用いて行うことを特徴とする請求項１５記載の方
法。 - （１７）間欠に使用する仮想回線は、アクティブに使用
する場合の、平均サービス時間の条件τと平均アイドル
時間ｈτを有し、及び アクティブ仮想回線Ｊ＿ｉ＿−＿１平均数を決めるステ
ップをＪ＿ｉ＿−＿１について近似式 ｉ−ｈ＋［（ｉ−ｈ）＾２＋４ｈ］＾１＾／＾２−２／
２を用いて行うことを特徴とする請求項１５記載の方法
。 - （１８）最大ウィンドウサイズを決めるステップを、通
信網の最長ラウンドトリップ時間をτ、及びｈτが少な
い秒数であるようなｈの値を用いて行うことを特徴とす
る請求項１６ないし請求項１７のいずれかに記載の方法
。 - （１９）通信網のノードにおいて、データセルのふくそ
うを制御して仮想回線を経由して、データのセルを送る
方法であって、この方法は、仮想回線が形成されると、
各ノードにおける仮想回線に対し、デフォルトセルバッ
ファを割当てるステップと、 仮想回線の間、実施するステップからなり、この実施す
るステップは、 異なるサイズのセルバッファが必要であるかどうかを、
仮想回線の挙動から決めるステップと、もし、異なるサ
イズのセルバッファが必要な場合、仮想回線におけるノ
ードに異なるサイズを表わす第１の再サイジング信号を
与えるステップと、仮想回線の各ノードにおいて、もし
異なるサイズより小さい場合に、ノードが提供できるバ
ッファサイズを示すことにより、第１の再サイジング信
号に応答するステップと、 仮想回線の各ノードにおいて、 ノードのいずれかにより示された最小バッファ以下のバ
ッファサイズに、仮想回線に対するセルバッファをセッ
トするステップ、 からなることを特徴とするデータセルの輻輳制御方法。 - （２０）異なるサイズのセルバッファが必要であるかど
うかを決めるステップを、 仮想回線が通信網に入る通信網の第１のエッジにおいて
行い、及び 前記方法は、仮想回線が通信網を出る通信網の第２のエ
ッジにおいて、第１の再サイジング信号を受信するステ
ップと、ノードにおけるセルバッファにセットされるバ
ッファサイズを選択するステップ、 をさらに有することを特徴とする請求項１９記載の方法
。 - （２１）前記方法は、第２のエッジから選択したバッフ
ァサイズを含む、第２の再サイジング信号をノードに送
るステップをさらに有し、及び仮想回線に対し、セルバ
ッファをセットするステップを第２の再サイジング信号
に指定の選択したバッファサイズを用いて行うことを特
徴とする請求項２０記載の方法。 - （２２）第１の再サイジング信号を送るステップを順に
、各ノードに第１の再サイジング信号を逐次送ることに
より行うことを特徴とする請求項２１記載の方法。 - （２３）第２の再サイジング信号を送るステップを順に
、各ノードに第２の再サイジング信号を行うことを特徴
とする請求項２２記載の方法。 - （２４）異なるサイズのセルバッファが必要かどうかを
決めるステップは、 所定の仮想回線が、第１のエッジにおいて有するセルＴ
Ｃの総数を通信網において、見失わぬよう接触を保つス
テップと、 非常に新しい再ネゴシェーション間隔の間、所定の仮想
回線のセルの累積したスループットＣＴを見失わぬよう
接触を保つステップと、 多数のセルを収容できる十分に大きい通信網において、 ラウンドトリップ時間を最も新しい再ネゴシェーション
間隔の長さで割った商を、ＣＴ倍した積とＴＣの大きい
方である仮想回線に対するウィンドウを要求するステッ
プを行うことにより実施されることを特徴とする請求項
２０記載の方法。 - （２５）ルータにおいて、所定の仮想回線に対するセル
バッファがオーバーフローするかどうかを見失わぬよう
に接触を保つステップと、もし、再ネゴシェーション間
隔の間、セルバッファがオーバーフローする場合、ウィ
ンドウを要求するステップにおいて、 全ラウンドトリップウィンドウを要求するステップをさ
らに有することを特徴とする請求項２４記載の方法。 - （２６）要求ウィンドウが現ウィンドウより大きいとき
、ウィンドウに対する未定のままの要求がない場合、い
つでもウィンドウを要求するステップをルータが行い、 及び要求ウィンドウが現ウィンドウより小さいとき、現
在の再ネゴシェーション間隔の終了するまでのウィンド
ウを要求するステップを、ルータは行わないことを特徴
とする請求項２４記載の方法。 - （２７）再ネゴシェーション間隔が、少ない秒数である
ことを特徴とする請求項２６記載の方法。 - （２８）第１の再サイジング信号に応答するステップは
、他の仮想回線と比較して、各仮想回線のランクを各仮
想回線のウィンドウの現在のサイズから決めるステップ
と、 もし仮に、そのウィンドウが要求サイズであると仮定し
た場合に、その所定の仮想回線が有するとされるポテン
シャルランクを決めるステップと、所定の仮想回線がポ
テンシャルランクを達成するまで、もしくは所定の仮想
回線のランクのさらなる変更が、次のランキングの仮想
回線のランクを以下に示すようなランクに変更すること
を必要とするまで、即ち、次にランクされた仮想回線の
現ウイィンドウサイズがその交換の結果、次にランクさ
れた仮想回線が受取るランクの最大ウィンドウより大き
いような、ランクに変更することを必要とするまで、所
定の仮想回線のランクを次のランキングの仮想回線のそ
れと必要とする方向に交換することにより、ポテンシャ
ルランクにより必要とされる方向に所定の仮想回線のラ
ンクを変更するステップであって、ランクに対する最大
ウィンドウは機能により決められ、それによって仮想回
線ｊに対する最大ウィンドウは、仮想回線ｊ＋１に対す
る最大ウィンドウより大きく、１＜ｊ＜ｋであるような
前記所定の仮想回線のランクを変更するステップと、 ウィンドウサイズを要求ウィンドウサイズと所定の仮想
回線に達成された最終ランクに対する最大ウィンドウサ
イズの小さい方であるように、所定の仮想回線のウィン
ドウサイズを決めるステップからなることを特徴とする
請求項１９記載の方法。 - （２９）任意の仮想回線ｉは名称が付与される最大ウィ
ンドウＷｉ−１を決めるステップは、ノードからのリン
クを用いて、アクティブ仮想回線Ｊ＿ｉ＿−＿１平均数
を決めるステップと、式 Ｗ＿ｉ＿−＿１／Ｗ＿０＝１／Ｊ＿ｉ＿−＿１−１を用
いて、最大ウィンドウＷ＿ｉ＿−＿１を決めるステップ
とからなることを特徴とする請求項２８記載の方法。 - （３０）間欠に使用する仮想回線は、アクティブに使用
する場合の平均サービス時間の条件τと、平均アイドル
時間ｈτを有し、及び アクティブ仮想回線Ｊ＿ｉ＿−＿１平均数を決めるステ
ップを、Ｊ＿０＝０から出発する漸化式 Ｊ＿ｉ＿−＿１＋１／Ｊ＿ｉ＿−＿１＋１＋ｈ＝Ｊ＿ｉ
／ｉを用いて行うことを特徴とする請求項２９記載の方
法。 - （３１）間欠に使用する仮想回線は、アクティブに使用
する場合の平均サービス時間の条件τと、平均アイドル
時間ｈτを有し、及び アクティブ仮想回線Ｊ＿ｉ＿−１平均数を決めるステッ
プをＪ＿ｉ＿−＿１について近似式 ｉ−ｈ＋［（ｉ−ｈ）＾２＋４ｈ］＾１＾／＾２−２／
２を用いて行うことを特徴とする請求項２９記載の方法
。 - （３２）最大ウィンドウサイズを決めるステップを、通
信網の最長ラウンドトリップ時間をτ、及びｈτが少な
い秒数であるようなｈの値を用いて行うことを特徴とす
る請求項３０ないし請求項３１のいずれかに記載の方法
。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US443,975 | 1989-11-30 | ||
| US07/443,975 US5014265A (en) | 1989-11-30 | 1989-11-30 | Method and apparatus for congestion control in a data network |
| US07/607,831 US5163046A (en) | 1989-11-30 | 1990-11-08 | Dynamic window sizing in a data network |
| US607,831 | 1990-11-08 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH03188733A true JPH03188733A (ja) | 1991-08-16 |
| JP2693267B2 JP2693267B2 (ja) | 1997-12-24 |
Family
ID=27033727
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP32611690A Expired - Fee Related JP2693267B2 (ja) | 1989-11-30 | 1990-11-29 | ウィンドウサイズの決定方法とデータセルの輻輳制御方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5163046A (ja) |
| EP (2) | EP0687090A3 (ja) |
| JP (1) | JP2693267B2 (ja) |
| CA (1) | CA2030349C (ja) |
| DE (1) | DE69025713T2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0591124A (ja) * | 1990-04-13 | 1993-04-09 | Digital Equip Corp <Dec> | バーストトラヒツクを運ぶ高速回線網の輻輳回避方法と装置および通信回線網 |
Families Citing this family (112)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2615509B2 (ja) * | 1990-10-30 | 1997-05-28 | 富士通株式会社 | 通信装置 |
| US5339411A (en) * | 1990-12-21 | 1994-08-16 | Pitney Bowes Inc. | Method for managing allocation of memory space |
| JPH0783361B2 (ja) * | 1991-05-14 | 1995-09-06 | 松下電器産業株式会社 | リング状パケット通信網 |
| JP3278865B2 (ja) * | 1991-06-28 | 2002-04-30 | 日本電気株式会社 | トラヒック制御方法 |
| JPH0548638A (ja) * | 1991-08-15 | 1993-02-26 | Fujitsu Ltd | Ａｔｍ網におけるエンド・エンド間輻輳対処制御処理方式 |
| SE469252B (sv) * | 1991-10-04 | 1993-06-07 | Eritel Ab | Foerfarande foer kontroll och styrning av datafloedet i ett paketdatanaet omfattande ett antal linjer och ett antal noder daer linjerna via noder foerbinder ett antal terminaler |
| US5291481A (en) * | 1991-10-04 | 1994-03-01 | At&T Bell Laboratories | Congestion control for high speed packet networks |
| US5243596A (en) * | 1992-03-18 | 1993-09-07 | Fischer & Porter Company | Network architecture suitable for multicasting and resource locking |
| JPH06196563A (ja) * | 1992-09-29 | 1994-07-15 | Internatl Business Mach Corp <Ibm> | Ｖｌｓｉの配線設計に対するコンピュータ実施可能な過密領域配線方法 |
| US5528513A (en) * | 1993-11-04 | 1996-06-18 | Digital Equipment Corp. | Scheduling and admission control policy for a continuous media server |
| FI94815C (fi) * | 1993-11-30 | 1995-10-25 | Nokia Telecommunciations Oy | Menetelmä sekä järjestelmä kehysvälitysverkon ylikuormitustilanteiden hallitsemiseksi |
| FI94814C (fi) * | 1993-11-30 | 1995-10-25 | Nokia Telecommunications Oy | Menetelmä kehysvälitysverkon ylikuormitustilanteiden hallitsemiseksi sekä kehysvälitysverkon tilaajasolmu |
| US5497375A (en) * | 1994-01-05 | 1996-03-05 | Motorola, Inc. | Device and method for ATM end system cell flow regulation |
| US6473793B1 (en) * | 1994-06-08 | 2002-10-29 | Hughes Electronics Corporation | Method and apparatus for selectively allocating and enforcing bandwidth usage requirements on network users |
| JPH0823332A (ja) * | 1994-07-05 | 1996-01-23 | Mitsubishi Electric Corp | リング型ａｔｍノードのアクセス制御装置 |
| JP2891111B2 (ja) * | 1994-07-15 | 1999-05-17 | 日本電気株式会社 | Ａｔｍセル速度測定方法および装置 |
| US5546520A (en) * | 1994-09-30 | 1996-08-13 | International Business Machines Corporation | Method, system, and memory for reshaping the frame edges of a window around information displayed in the window |
| US5541912A (en) * | 1994-10-04 | 1996-07-30 | At&T Corp. | Dynamic queue length thresholds in a shared memory ATM switch |
| US5521916A (en) * | 1994-12-02 | 1996-05-28 | At&T Corp. | Implementation of selective pushout for space priorities in a shared memory asynchronous transfer mode switch |
| FI951278A0 (fi) * | 1995-03-17 | 1995-03-17 | Finland Telecom Oy | Foerfarande och arrangemang foer att behaerska en buffert i ett ATM-naet |
| US5537395A (en) * | 1995-04-13 | 1996-07-16 | Northern Telecom Limited | Method and apparatus for setting a channel congestion message in a wireless multiple access packet data system |
| FI98023C (fi) * | 1995-05-09 | 1997-03-25 | Nokia Telecommunications Oy | Liukuvaan ikkunaan perustuva datavuonohjaus, joka käyttää säädettävää ikkunakokoa |
| US5680400A (en) * | 1995-05-31 | 1997-10-21 | Unisys Corporation | System for high-speed transfer of a continuous data stream between hosts using multiple parallel communication links |
| US5787086A (en) * | 1995-07-19 | 1998-07-28 | Fujitsu Network Communications, Inc. | Method and apparatus for emulating a circuit connection in a cell based communications network |
| GB2304210B (en) * | 1995-08-11 | 2000-02-16 | Fujitsu Ltd | Data receiving devices |
| AU6970896A (en) * | 1995-09-14 | 1997-04-01 | Ascom Nexion Inc. | Transmitter controlled flow control for buffer allocation in wide area atm networks |
| US5917822A (en) * | 1995-11-15 | 1999-06-29 | Xerox Corporation | Method for providing integrated packet services over a shared-media network |
| AU1697697A (en) * | 1996-01-16 | 1997-08-11 | Fujitsu Limited | A reliable and flexible multicast mechanism for atm networks |
| US5724358A (en) * | 1996-02-23 | 1998-03-03 | Zeitnet, Inc. | High speed packet-switched digital switch and method |
| US5721849A (en) * | 1996-03-29 | 1998-02-24 | International Business Machines Corporation | Method, memory and apparatus for postponing transference of focus to a newly opened window |
| US5666498A (en) * | 1996-03-29 | 1997-09-09 | International Business Machines Corporation | Method, memory and apparatus for automatically resizing a window |
| US5699535A (en) * | 1996-03-29 | 1997-12-16 | International Business Machines Corporation | Method, memory and apparatus for automatically resizing a plurality of windows displayed on a computer display |
| US5872567A (en) * | 1996-03-29 | 1999-02-16 | International Business Machines Corporation | Method, memory and apparatus for automatically resizing a window in response to a loss or gain in focus |
| US5940077A (en) * | 1996-03-29 | 1999-08-17 | International Business Machines Corporation | Method, memory and apparatus for automatically resizing a window while continuing to display information therein |
| US5822300A (en) * | 1996-04-02 | 1998-10-13 | Compaq Computer Corporation | Congestion management scheme |
| US5748905A (en) * | 1996-08-30 | 1998-05-05 | Fujitsu Network Communications, Inc. | Frame classification using classification keys |
| GB9624179D0 (en) | 1996-11-20 | 1997-01-08 | Plessey Telecomm | Telecommunications access systems and equipment |
| US6359882B1 (en) | 1997-04-01 | 2002-03-19 | Yipes Communications, Inc. | Method and apparatus for transmitting data |
| US5943053A (en) * | 1997-04-01 | 1999-08-24 | Sun Microsystems, Inc. | Method and apparatus for expanding and contracting a window panel |
| US6076113A (en) * | 1997-04-11 | 2000-06-13 | Hewlett-Packard Company | Method and system for evaluating user-perceived network performance |
| US6105064A (en) * | 1997-05-30 | 2000-08-15 | Novell, Inc. | System for placing packets on network for transmission from sending endnode to receiving endnode at times which are determined by window size and metering interval |
| US6088356A (en) * | 1997-06-30 | 2000-07-11 | Sun Microsystems, Inc. | System and method for a multi-layer network element |
| US6246680B1 (en) | 1997-06-30 | 2001-06-12 | Sun Microsystems, Inc. | Highly integrated multi-layer switch element architecture |
| US6081522A (en) * | 1997-06-30 | 2000-06-27 | Sun Microsystems, Inc. | System and method for a multi-layer network element |
| US6094435A (en) * | 1997-06-30 | 2000-07-25 | Sun Microsystems, Inc. | System and method for a quality of service in a multi-layer network element |
| US6119196A (en) * | 1997-06-30 | 2000-09-12 | Sun Microsystems, Inc. | System having multiple arbitrating levels for arbitrating access to a shared memory by network ports operating at different data rates |
| US6016310A (en) * | 1997-06-30 | 2000-01-18 | Sun Microsystems, Inc. | Trunking support in a high performance network device |
| US6044087A (en) * | 1997-06-30 | 2000-03-28 | Sun Microsystems, Inc. | Interface for a highly integrated ethernet network element |
| US6115378A (en) * | 1997-06-30 | 2000-09-05 | Sun Microsystems, Inc. | Multi-layer distributed network element |
| US6081512A (en) * | 1997-06-30 | 2000-06-27 | Sun Microsystems, Inc. | Spanning tree support in a high performance network device |
| US6021132A (en) * | 1997-06-30 | 2000-02-01 | Sun Microsystems, Inc. | Shared memory management in a switched network element |
| US6049528A (en) * | 1997-06-30 | 2000-04-11 | Sun Microsystems, Inc. | Trunking ethernet-compatible networks |
| US6044418A (en) * | 1997-06-30 | 2000-03-28 | Sun Microsystems, Inc. | Method and apparatus for dynamically resizing queues utilizing programmable partition pointers |
| US6320846B1 (en) * | 1997-08-05 | 2001-11-20 | Hi/Fm, Inc. | Method and apparatus for controlling network bandwidth |
| US6321272B1 (en) * | 1997-09-10 | 2001-11-20 | Schneider Automation, Inc. | Apparatus for controlling internetwork communications |
| US6185210B1 (en) * | 1997-09-30 | 2001-02-06 | Bbn Corporation | Virtual circuit management for multi-point delivery in a network system |
| US6249530B1 (en) * | 1997-12-22 | 2001-06-19 | Sun Microsystems, Inc. | Network bandwidth control |
| US6370114B1 (en) * | 1997-12-31 | 2002-04-09 | Nortel Networks Limited | Apparatus and method for optimizing congestion control information in a multi-protocol network |
| US6085254A (en) * | 1998-04-10 | 2000-07-04 | Telefonaktiebolaget Lm Ericsson (Publ) | Dynamic size alteration of memory files |
| CA2331310A1 (en) * | 1998-05-08 | 1999-11-18 | Siemens Aktiengesellschaft | Method for controlling the message flow in a communication network |
| US6778545B1 (en) * | 1998-09-24 | 2004-08-17 | Cisco Technology, Inc. | DSP voice buffersize negotiation between DSPs for voice packet end devices |
| CA2249152C (en) * | 1998-09-30 | 2003-07-08 | Northern Telecom Limited | Apparatus for and method of managing bandwidth for a packet-based connection |
| HRP980536B1 (en) * | 1998-10-05 | 2006-04-30 | O�egovi� Julije | Arrangements for window - time - space flow control |
| US6304936B1 (en) | 1998-10-30 | 2001-10-16 | Hewlett-Packard Company | One-to-many bus bridge using independently and simultaneously selectable logical FIFOS |
| US6269413B1 (en) | 1998-10-30 | 2001-07-31 | Hewlett Packard Company | System with multiple dynamically-sized logical FIFOs sharing single memory and with read/write pointers independently selectable and simultaneously responsive to respective read/write FIFO selections |
| US6934255B1 (en) | 1999-02-02 | 2005-08-23 | Packeteer, Inc. | Internet over satellite apparatus |
| US6584083B1 (en) | 1999-02-02 | 2003-06-24 | Mentat Inc. | Internet over satellite method |
| US6654344B1 (en) | 1999-02-02 | 2003-11-25 | Mentat Inc. | Method and system for controlling data flow in an internet over satellite connection |
| JP3814678B2 (ja) * | 1999-02-02 | 2006-08-30 | パケッティー・インコーポレーテッド | サテライトを介するインターネット |
| US6460085B1 (en) | 1999-02-02 | 2002-10-01 | Mentat Inc. | Method and system for managing memory in an internet over satellite connection |
| US6529477B1 (en) | 1999-02-02 | 2003-03-04 | Mentat Inc. | Internet over satellite system |
| US6335933B1 (en) * | 1999-05-21 | 2002-01-01 | Broadcom Homenetworking, Inc. | Limited automatic repeat request protocol for frame-based communication channels |
| US6831912B1 (en) * | 2000-03-09 | 2004-12-14 | Raytheon Company | Effective protocol for high-rate, long-latency, asymmetric, and bit-error prone data links |
| US6665868B1 (en) * | 2000-03-21 | 2003-12-16 | International Business Machines Corporation | Optimizing host application presentation space recognition events through matching prioritization |
| US20020188950A1 (en) * | 2000-05-01 | 2002-12-12 | Hughes Electronics Corporation | Low speed data port for data transactions and information |
| US7360231B2 (en) * | 2000-05-01 | 2008-04-15 | The Directv Group, Inc. | System for obtaining data regarding customer use of interactive television |
| US6760782B1 (en) | 2000-08-04 | 2004-07-06 | Schneider Automation Inc. | Apparatus for controlling internetwork communications |
| US6889384B1 (en) * | 2000-11-08 | 2005-05-03 | The Directv Group, Inc. | Simplified interactive user interface for multi-video channel navigation |
| ATE326802T1 (de) * | 2000-11-28 | 2006-06-15 | Flash Networks Ltd | System und verfahren für eine übertragungsratensteuerung |
| US7154916B2 (en) * | 2001-07-26 | 2006-12-26 | The Directv Group, Inc. | Method for real-time insertion of auxiliary data packets into DSS bitstream in the presence of one or more service channels |
| US6996564B2 (en) * | 2001-08-13 | 2006-02-07 | The Directv Group, Inc. | Proactive internet searching tool |
| US7856660B2 (en) | 2001-08-21 | 2010-12-21 | Telecommunication Systems, Inc. | System for efficiently handling cryptographic messages containing nonce values |
| US7464180B1 (en) | 2001-10-16 | 2008-12-09 | Cisco Technology, Inc. | Prioritization and preemption of data frames over a switching fabric |
| US8145787B1 (en) * | 2001-10-16 | 2012-03-27 | Cisco Technology, Inc. | Adaptive bandwidth utilization over fabric links |
| US7054902B2 (en) * | 2001-10-23 | 2006-05-30 | Packeteer, Inc. | Multicast delivery systems and methods |
| KR100765121B1 (ko) * | 2001-11-24 | 2007-10-11 | 엘지전자 주식회사 | 송신버퍼의 프로토콜 데이터 유닛 폴링 방법 |
| US20030126196A1 (en) * | 2001-12-27 | 2003-07-03 | Todd Lagimonier | System for optimizing the invocation of computer-based services deployed in a distributed computing environment |
| JP4126928B2 (ja) * | 2002-02-28 | 2008-07-30 | 日本電気株式会社 | プロキシサーバ及びプロキシ制御プログラム |
| JP3947424B2 (ja) | 2002-05-02 | 2007-07-18 | 株式会社エヌ・ティ・ティ・ドコモ | パケット送信制御装置、移動ノード、制御ノード、パケット通信方法、及びパケット通信システム |
| US7302648B1 (en) * | 2002-07-10 | 2007-11-27 | Apple Inc. | Method and apparatus for resizing buffered windows |
| US7802008B2 (en) * | 2002-08-12 | 2010-09-21 | Matsushita Electric Industrial Co., Ltd. | Quality of service management in network gateways |
| US6876628B2 (en) * | 2002-08-28 | 2005-04-05 | Emware, Inc. | Optimization of subnetwork bandwidth based on desired subscription rates |
| US7343398B1 (en) | 2002-09-04 | 2008-03-11 | Packeteer, Inc. | Methods, apparatuses and systems for transparently intermediating network traffic over connection-based authentication protocols |
| CN1918867B (zh) * | 2003-11-05 | 2010-08-11 | 瞻博网络公司 | 用于传输控制协议初始化会话建立的透明优化 |
| US7564792B2 (en) * | 2003-11-05 | 2009-07-21 | Juniper Networks, Inc. | Transparent optimization for transmission control protocol flow control |
| US7058058B2 (en) | 2003-11-05 | 2006-06-06 | Juniper Networks, Inc. | Transparent optimization for transmission control protocol initial session establishment |
| DE602004016827D1 (de) * | 2004-05-19 | 2008-11-13 | Mitsubishi Electric Corp | Verfahren und Einrichtung zur Funkbetriebsmittelzuweisung |
| GR1005055B (el) * | 2004-08-27 | 2005-12-06 | Atmel Corporation | Μεθοδος και συστημα για ενα μηχανισμο διασφαλισης ποιοτητας υπηρεσιας για ασυρματα δικτυα. |
| US9325456B2 (en) * | 2005-03-22 | 2016-04-26 | Intel Corporation | Method and apparatus for delayed recovery for block acknowledgement bursting in a wireless network |
| US20060239194A1 (en) * | 2005-04-20 | 2006-10-26 | Chapell Christopher L | Monitoring a queue for a communication link |
| US8325600B2 (en) | 2005-12-30 | 2012-12-04 | Intel Corporation | Segmentation interleaving for data transmission requests |
| US9049175B2 (en) | 2010-12-02 | 2015-06-02 | Microsoft Technology Licensing, Llc | Client-adjustable window size for connectionless transfer protocols |
| US8521902B2 (en) | 2010-12-02 | 2013-08-27 | Microsoft Corporation | Shared buffer for connectionless transfer protocols |
| US8873385B2 (en) | 2010-12-07 | 2014-10-28 | Microsoft Corporation | Incast congestion control in a network |
| US9344374B2 (en) * | 2012-07-06 | 2016-05-17 | Adara Networks, Inc. | Network congestion control |
| US10122645B2 (en) | 2012-12-07 | 2018-11-06 | Cisco Technology, Inc. | Output queue latency behavior for input queue based device |
| US9628406B2 (en) * | 2013-03-13 | 2017-04-18 | Cisco Technology, Inc. | Intra switch transport protocol |
| US9860185B2 (en) | 2013-03-14 | 2018-01-02 | Cisco Technology, Inc. | Intra switch transport protocol |
| JP6244836B2 (ja) * | 2013-11-12 | 2017-12-13 | 富士通株式会社 | 通信装置及びパケット制御方法 |
| US9473882B2 (en) * | 2014-06-16 | 2016-10-18 | Motorola Solutions, Inc. | Enhanced location data throughput on a windowed data channel in a radio communication system |
| CN106302090B (zh) * | 2015-05-25 | 2019-10-22 | 阿里巴巴集团控股有限公司 | 一种消息处理方法、装置及系统 |
| SG10201912856TA (en) * | 2019-12-20 | 2021-07-29 | Panasonic Ip Corp America | Communication device and communication method for multi-link block acknowledgement |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6342543A (ja) * | 1986-08-08 | 1988-02-23 | Nippon Telegr & Teleph Corp <Ntt> | パケットフロー制御方法 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3749845A (en) | 1971-08-27 | 1973-07-31 | Bell Telephone Labor Inc | Digital data communication system |
| USRE31319E (en) | 1971-08-27 | 1983-07-19 | Bell Telephone Laboratories, Incorporated | Digital data communication system |
| US4841526A (en) * | 1984-05-25 | 1989-06-20 | Wilson Jon C | Data communications system |
| US4583219A (en) | 1984-07-16 | 1986-04-15 | At&T Bell Laboratories | Trunk for packet switching |
| US4736369A (en) | 1986-06-13 | 1988-04-05 | International Business Machines Corp. | Adaptive session-level pacing |
| US5014265A (en) * | 1989-11-30 | 1991-05-07 | At&T Bell Laboratories | Method and apparatus for congestion control in a data network |
-
1990
- 1990-11-08 US US07/607,831 patent/US5163046A/en not_active Expired - Lifetime
- 1990-11-20 CA CA002030349A patent/CA2030349C/en not_active Expired - Fee Related
- 1990-11-21 EP EP95112656A patent/EP0687090A3/en not_active Withdrawn
- 1990-11-21 EP EP90312680A patent/EP0430571B1/en not_active Expired - Lifetime
- 1990-11-21 DE DE69025713T patent/DE69025713T2/de not_active Expired - Fee Related
- 1990-11-29 JP JP32611690A patent/JP2693267B2/ja not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6342543A (ja) * | 1986-08-08 | 1988-02-23 | Nippon Telegr & Teleph Corp <Ntt> | パケットフロー制御方法 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0591124A (ja) * | 1990-04-13 | 1993-04-09 | Digital Equip Corp <Dec> | バーストトラヒツクを運ぶ高速回線網の輻輳回避方法と装置および通信回線網 |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2030349C (en) | 1997-04-22 |
| EP0430571B1 (en) | 1996-03-06 |
| EP0430571A3 (en) | 1993-03-17 |
| CA2030349A1 (en) | 1991-05-31 |
| EP0687090A2 (en) | 1995-12-13 |
| EP0687090A3 (en) | 2005-07-06 |
| JP2693267B2 (ja) | 1997-12-24 |
| DE69025713T2 (de) | 1996-10-10 |
| DE69025713D1 (de) | 1996-04-11 |
| EP0430571A2 (en) | 1991-06-05 |
| US5163046A (en) | 1992-11-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH03188733A (ja) | ウィンドウサイズの決定方法とデータセルの輻輳制御方法 | |
| US5014265A (en) | Method and apparatus for congestion control in a data network | |
| US6615271B1 (en) | Traffic control system having distributed rate calculation and link flow control | |
| US6456590B1 (en) | Static and dynamic flow control using virtual input queueing for shared memory ethernet switches | |
| US5379297A (en) | Concurrent multi-channel segmentation and reassembly processors for asynchronous transfer mode | |
| KR100234212B1 (ko) | 패킷 네트워크에서의 적응 속도기반 혼잡제어 | |
| US5457687A (en) | Method and apparatus for backward explicit congestion notification (BECN) in an ATM network | |
| US9419907B2 (en) | I/O driven rate adaptation | |
| US6088736A (en) | Joint flow control mechanism in a telecommunications network | |
| US5115430A (en) | Fair access of multi-priority traffic to distributed-queue dual-bus networks | |
| US6359863B1 (en) | Rate allocation system and method for ATM switched networks | |
| US7161907B2 (en) | System and method for dynamic rate flow control | |
| JPH0657014B2 (ja) | 適応選択形のパケット交換システムにおけるフロ−制御 | |
| JPH07273772A (ja) | Ａｔｍスイッチにおける帯域幅要求を処理する装置および方法 | |
| JPH0897832A (ja) | 固定長セル交換ネットワーク・ノード内の出力トラフィックをシェーピングするための方法および装置 | |
| JP2001519973A (ja) | 共用バッファへの優先度付きアクセス | |
| US5852601A (en) | Method and apparatus for reactive congestion control in an asynchronous transfer mode (ATM) network | |
| US6249819B1 (en) | Method for flow controlling ATM traffic | |
| EP1037500A2 (en) | Network element delay allocation for efficient use of network resources | |
| EP0604538B1 (en) | Method and apparatus for asynchronous transfer mode (atm) network | |
| Platt et al. | Traffic management in frame relay networks | |
| Indiresan et al. | Design tradeoffs in implementing real-time channels on bus-based multiprocessor hosts | |
| JP2001086127A (ja) | トラフィック特性別最適化転送システム及び方法 | |
| JPH04151931A (ja) | 帯域割り当て制御方式 | |
| WO1997004563A1 (en) | Joint flow control mechanism in a telecommunications network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |