JPH10164136A - パケット通信装置及び方法 - Google Patents

Abstract

(57)【要約】 【課題】 上位レイヤパケットを分割して成る固定長の
パケットをインターリーブに出力する際に上位レイヤパ
ケット長を考慮してサービスの公平性を保証する。 【解決手段】 送信待ちの下位レイヤパケットを蓄積す
るパケットキューと、各パケットキュー対応に蓄積され
ている下位レイヤパケットが属する上位レイヤパケット
のパケット長を記憶するパケット長記憶手段と、この上
位レイヤパケット長の情報を用いて下位レイヤパケット
を出力するためのパケットキューを選択し、同一の上位
レイヤパケットに所属する下位レイヤパケットを出力し
終えるまで選択しつづけるスケジューリング手段とを備
える。このスケジューリング手段は、同一の上位レイヤ
パケットに属するパケットが全部そろうまで待たずに該
パケットの出力を開始することも可能である。また、２
つの最終パケット間の到着パケット数をカウントするこ
とによりパケット長を測定することもできる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、上位レイヤパケッ
トを固定長パケットに分割して伝送するパケット通信装
置及び方法に関する。

【０００２】

【従来の技術】ATM (Asynchronous Transfer Mode)伝送
方式を用いたパケット網では、セルと呼ばれる53オクテ
ットの固定長のパケットが伝送される。ATM 方式におい
ては、セルのヘッダ部に書かれたVCI (Virtual Channel
Identifier)、VPI (Virtual Path Identifier) により
コネクションが識別される。

【０００３】一般に、ATM レイヤより上位レイヤのパケ
ットは、複数のATM セルに分割されて伝送される。ATM
レイヤと上位レイヤとの間に定義され、上位レイヤパケ
ットをATM セルに分解あるいはATM セルから上位レイヤ
パケットを組立てるレイヤをAAL (ATM Adaptation Laye
r)と呼び、サービスクラスに応じて異なるAAL 処理が用
意されている。

【０００４】AAL 処理のうち、セル単位の処理をSAR (S
egmentation and Reassembly) 、上位レイヤパケット単
位の処理をCS (Convergense Sublayer) と呼ぶ。CSの中
で各サービスクラス毎に定義される部分をCPCS (Common
Part Convergense Sublayer) 、サービス毎に依存して
定義される部分をSSCS(Service Specific Convergense
Sublayer) と呼ぶ。

【０００５】特に、高速処理に適したAAL 処理としてAA
L5と呼ばれる方式がある。これは、セルヘッダ中の継続
表示ビットと呼ばれる１ビットの情報を用いてAAL 処理
を行なう。具体的には送信側は上位レイヤパケットの最
終セルに対してのみ継続表示ビットをオフにし、受信側
では、継続表示ビットがオフとなるまでは受信セルが同
一の上位レイヤパケットに所属するとみなしてパケット
の組立てを行なう。これによりオーバーヘッドが少な
く、かつ、簡単なAAL 処理が可能となる。このような理
由から通常のデータ通信においては、AAL5が使用され
る。

【０００６】しかしながら、AAL5を使用した場合には以
下の問題がある。AAL5が上位レイヤパケットの境界を認
識するために使用可能な情報は継続表示ビットのみであ
るため、１つのVC (Virtual Connection) の中に異なる
上位レイヤパケットに所属するセルをインターリーブで
きない。これは、同一出力VCで異なる上位レイヤパケッ
トを識別するための識別子を各セルに付加することを行
わないAAL 処理の場合に生じる問題である。

【０００７】ここで、異なる上位レイヤパケットに属す
るセルをノンインターリーブに出力しなければならない
代表的な例として以下のようなものがある。１）現在、
ATM フォーラムでは、ポイント- ポイント通信または、
ポイント-マルチポイント通信の標準化を中心に行なっ
ているが、マルチポイント- ポイント、マルチポイント
- マルチポイント通信も検討している。複数のVCを１つ
のVCに多重する場合には、ATM スイッチにおいて異なる
入力VCからのセルをノンインターリーブに出力する機能
が必須となる。

【０００８】２）IPパケットをATM セルで運ぶ場合に、
ルータがATM スイッチ機能も有し、IPフローとATM VCを
１対１に対応させることにより、ルータにおいて、IPレ
イヤまで処理を上げることなく、ATM レベルでIPパケッ
トのスイッチングを行なう技術がある。IPフローがIPソ
ースネットワークアドレス、宛先ネットワークアドレス
のペアで定義される場合には、各ルータでネットワーク
数の2 乗のオーダの数のVCが必要となる。VC数を削減す
るためには、同一の宛先アドレスをもつフローを一つの
VCに多重すればよいが、このためには、異なるソースネ
ットワークアドレスに対応する入力VCからのセルをノン
インターリーブに出力する必要がある。

【０００９】現在、AAL5のセルをノンインターリーブに
出力する方法として、文献「W. Ren, K. Siu, and H. S
uzuki, "Performance Evaluation of Multipoint-Point
ABRand UBR", ATM Forum Technical Contribution, N
o.96-1402, 1996 」がある。

【００１０】これは、以下のようなものである。入力VC
毎にセルキューおよびパケット数カウンタを設け、AAL5
の継続表示ビットがオフであるセルをセルキューに入力
する毎に対応するVCのパケット数カウンタをインクリメ
ントし、AAL5の継続表示ビットがオフであるセルをセル
キューから出力する毎に対応するVCのパケット数カウン
タをデクリメントする。さらに、セル出力時にはパケッ
ト数カウンタが１以上のセルキューからラウンドロビン
に出力キューを選択し、いったん選択したセルキュー
は、継続表示ビットがオフであるセルを出力するまでは
継続して選択される。

【００１１】

【発明が解決しようとする課題】しかしながら、上記方
式では、大きく以下の２つの問題点がある。まず第一
に、上記方式では、上位レイヤのパケット長が考慮され
ないため、上位レイヤで何らかのフロー制御を行なわな
い場合には、上位レイヤパケット長が大きいセルが多い
セルキューほど、高いスループットを得ることになり、
サービスの公平性という点で問題が出てくる。

【００１２】また、上位レイヤのパケット長を考慮する
には少なくともセルキュー内の先頭の上位レイヤパケッ
トのパケット長を把握する必要があるが、AAL5パケット
のように、パケット長が書かれているフィールドがパケ
ットのヘッダ部ではなく、トレイラ部にある場合には、
セルキューの先頭からパケット長フィールドの位置が固
定ではないため、パケット長をすぐには把握することが
できない。さらに、異なる上位レイヤパケットが多重さ
れる場合には、パケット長フィールドの位置が上位レイ
ヤプロトコルにより変わるため、上位レイヤパケットの
フォーマットに依存せずにパケット長を把握できるのが
望ましい。

【００１３】第二に、上記方式では、パケット数カウン
タが１以上の場合、すなわち、セルキュー内の先頭の上
位レイヤパケットがすべてセルキューに蓄積された後で
なければスケジューリングが行なわれない（このような
スケジューリングをノンカットスルー・スケジューリン
グと呼ぶ）ため、パケット長が大きいパケットほど遅延
時間が大きくなってしまう。

【００１４】以上の問題点に鑑み、本発明は、ノンイン
ターリーブに下位レイヤパケット（例えばセル）を出力
しつつサービスの公平性を担保することが可能なスケジ
ューリング機能を備えたパケット通信装置及び方法を提
供することを目的とする。

【００１５】

【課題を解決するための手段】本発明（請求項１）は、
上位レイヤパケットを分割して成る固定長の下位レイヤ
パケットを出力するパケット通信装置において、出力待
ちの下位レイヤパケットを蓄積するための複数のパケッ
トキューと、各パケットキュー対応にパケットキューに
蓄積されている下位レイヤパケットが所属する上位レイ
ヤパケットのパケット長の情報を記憶するためのパケッ
ト長記憶手段と、このパケット長記憶手段に記憶される
上位レイヤパケット長の情報を用いて、下位レイヤパケ
ットの出力を許可するパケットキューを選択するパケッ
トスケジューリング手段とを具備することを特徴とす
る。

【００１６】上記で記憶される上位レイヤパケット長の
情報は、後述するように固定長パケット数をカウントす
ることにより得ても構わないし、パケット長フィールド
を含む固定長パケットからパケット長の情報を抽出する
ことにより得ても構わない。

【００１７】これにより、上位レイヤのパケット長を考
慮して下位レイヤパケットのスケジューリングを行うこ
とが可能になり、サービスの公平性が担保される。ここ
で、前記パケットスケジューリング手段は、選択したパ
ケットキューに蓄積された下位レイヤパケットが同一の
上位レイヤパケットに所属するものである限りこの下位
レイヤパケットを出力し終えるべく該パケットキューを
選択しつづけることが好ましい（請求項２）。

【００１８】これにより、上位レイヤのパケット長を考
慮して下位レイヤパケットのノンインターリーブな出力
をスケジューリングすることが可能になる。本発明（請
求項３）は、パケット長の情報がそのヘッダ部に記入さ
れていない可変長パケットを出力するパケット通信装置
において、出力待ちのパケットを蓄積するための複数の
パケットキューと、このパケットキューに蓄積されてい
るパケットのパケット長の情報もしくはこの情報が記憶
されている前記パケットキュー内の位置を検出するパケ
ット長検出手段と、各パケットキュー対応にこのパケッ
ト長検出手段により検出されたパケット長の情報もしく
はパケットキュー内位置を記憶するためのパケット長記
憶手段と、このパケット長記憶手段に記憶されたパケッ
ト長の情報もしくはパケットキュー内位置に基づいて得
られるパケット長の情報を用いて、パケットの出力を許
可するパケットキューを選択するパケットスケジューリ
ング手段とを具備することを特徴とする。

【００１９】上記のパケット長情報の検出は、後述する
ように該パケットを分割した下位レイヤパケットの数を
カウントすることにより実現しても構わないし、該パケ
ットのパケット長フィールドからパケット長の情報を抽
出することにより実現しても構わない。

【００２０】これにより、AAL5パケットのようなパケッ
ト長をすぐには把握することのできないパケットに対し
ても、パケット長を考慮したスケジューリングを行うこ
とが可能になり、サービスの公平性が担保される。

【００２１】本発明（請求項４）は、上位レイヤパケッ
トを分割して成り、該上位レイヤパケットの最終下位レ
イヤパケットか否かを識別するための最終パケット識別
情報を含む固定長の下位レイヤパケットを出力するパケ
ット通信装置において、上位レイヤパケットのパケット
長をある最終下位レイヤパケットを受信してから次の最
終下位レイヤパケットを受信するまでに受信した固定長
パケット数をカウントすることにより測定する上位レイ
ヤパケット長測定手段と、この上位レイヤパケット長測
定手段により測定された上位レイヤパケット長を用いて
下位レイヤパケットの出力を制御する制御手段とを具備
することを特徴とする。

【００２２】これにより、上位レイヤパケットのパケッ
トフォーマットに依存することなく、上位レイヤパケッ
ト長を把握して、下位レイヤパケットの出力制御（例え
ばスケジューリング）をすることが可能になる。

【００２３】本発明（請求項５）は、上位レイヤパケッ
トを分割して成る固定長の下位レイヤパケットを出力す
るパケット通信装置において、出力待ちの下位レイヤパ
ケットを蓄積するための複数のパケットキューと、ある
パケットキューに同一の上位レイヤパケットに所属する
下位レイヤパケットが全て蓄積されるのを待たずに該下
位レイヤパケットの出力が許可されるように該パケット
キューを選択可能とし、選択されたパケットキューに蓄
積された下位レイヤパケットが同一の上位レイヤパケッ
トに所属するものである限りこの下位レイヤパケットを
出力し終えるべく該パケットキューを選択しつづけるパ
ケットスケジューリング手段とを具備することを特徴と
する。

【００２４】これにより、ノンインターリーブなスケジ
ューリングを行ないつつ、上位レイヤパケットの先頭下
位レイヤパケットが到着すればただちにスケジューリン
グを行なう（このようなスケジューリングをカットスル
ー・スケジューリングと呼ぶ）ことが可能になり、パケ
ット長が大きいと遅延時間が大きくなってしまう問題を
解決できる。

【００２５】ここで、前記下位レイヤパケットを、上位
レイヤパケットの最終パケットか否かを識別するための
最終パケット識別情報を含むものとし、前記パケットス
ケジューリング手段は、現在選択中のパケットキューが
所定時間空である場合には、最終パケットであることを
示す最終パケット識別情報を記入した下位レイヤパケッ
トを新たに生成して出力することが好ましい（請求項
６）。

【００２６】これにより、ノンインターリーブ且つカッ
トスルー・スケジューリングを行った場合に、後続の下
位レイヤパケットが到着しないために空のパケットキュ
ーを選択しつづけてしまうという問題を解決できる。

【００２７】ここで、前記所定時間は、選択中のパケッ
トキューが空になってから全パケットキューのキュー長
の和が一定値を越えない間としても良い（請求項７）。
これにより、選択中のパケットキューが空である場合
に、選択中のパケットキューのサービスを中止するまで
の待ち時間を本パケット通信装置内の蓄積パケット数に
応じて変えることができる。

【００２８】また、この発明においても、各パケットキ
ュー対応にパケットキューに蓄積されている下位レイヤ
パケットが所属する上位レイヤパケットのパケット長の
情報を記憶するためのパケット長記憶手段を更に設け、
前記パケットスケジューリング手段が、このパケット長
記憶手段に記憶される上位レイヤパケット長の情報を用
いて、下位レイヤパケットの出力を許可するパケットキ
ューの選択を行う（請求項８）ことにより、上位レイヤ
のパケット長を考慮して下位レイヤパケットのノンイン
ターリーブ且つカットスルーなスケジューリングを行う
ことが可能になる。

【００２９】本発明（請求項９）は、ノンインターリー
ブなスケジューリングを行う請求項２または５の発明に
於けるパケットスケジューリング手段が、各パケットキ
ューに割り当てられた出力許可数が残っているパケット
キューを下位レイヤパケットの出力を許可するパケット
キューとして選択し、同一の上位レイヤパケットに所属
する下位レイヤパケットを出力し終えるまでは該パケッ
トキューの残っている出力許可数を超えても該パケット
キューを選択しつづけることを特徴とする。

【００３０】このとき、同一の上位レイヤパケットに所
属する下位レイヤパケットが全てパケットキューに蓄積
されるのを待たずに該下位レイヤパケットの出力を許可
するように該パケットキューを選択した場合に、残って
いる出力許可数を超えても選択しつづける動作を行うこ
ととし、同一の上位レイヤパケットに所属する下位レイ
ヤパケットが全てパケットキューに蓄積されているなら
ば、該パケットキューを下位レイヤパケットの出力を許
可するパケットキューとして選択するのは該同一の上位
レイヤパケットに所属する下位レイヤパケットの数が残
っている出力許可数以下の場合とすることもできる（請
求項１０）。

【００３１】そして、請求項９の発明に於けるパケット
スケジューリング手段は、各パケットキューに割り当て
られた出力許可数に基づいた出力の終了後、再度各パケ
ットキューに出力許可数を割り当てる際に、残っていた
出力許可数を超えて下位レイヤパケットを出力したパケ
ットキューについては超えた分に応じて差し引いた数を
割り当てるものであることが好ましい（請求項１１）。

【００３２】これにより、下位レイヤパケットをノンイ
ンターリーブに出力した結果、出力許可数を超えるよう
なスケジューリングが行なわれるが、次の出力許可数の
割り当て時に超えた分を調整することにより、サービス
の公平性を保証したスケジューリングが可能になる。ま
た、カットスルー・スケジューリングを行なう場合に、
サービスしようとするパケットのパケット長があらかじ
めわからない場合にも、公平性を保証したスケジューリ
ングが可能になる。

【００３３】さらに、前記パケットスケジューリング手
段が、各パケットキューに割り当てられた出力許可数に
基づいた出力の終了後、再度各パケットキューに出力許
可数を割り当てる際に、残っていた出力許可数を超えて
下位レイヤパケットを出力したパケットキューが空であ
り、且つ、該パケットキューの出力後に全パケットキュ
ーが空になった時が存在する場合には、前記差し引きを
行わない数を該パケットキューに割り当てるようにして
も良い（請求項１２）。このように、本パケット通信装
置が全体としてビジーでなくなった場合には、次の出力
許可数を初期状態に戻すことにより、さらなる公平性の
保証が可能である。

【００３４】上述したスケジューリングは、具体的に
は、例えば次のようにして実現できる。すなわち、各パ
ケットキュー対応に出力可能な下位レイヤパケットの量
を示すカウンタ値を保持するカウンタ手段を更に設け、
前記パケットスケジューリング手段は、（ａ）このカウ
ンタ手段に保持されたカウンタ値が正で且つ空でないパ
ケットキューを下位レイヤパケットの出力を許可するパ
ケットキューとして選択し、同一の上位レイヤパケット
に所属する下位レイヤパケットを出力し終えるまで該パ
ケットキューを選択しつづけ、（ｂ）対応するカウンタ
値を下位レイヤパケットを出力した分に応じてデクリメ
ントし、（ｃ）選択候補ではなくなったパケットキュー
のカウンタ値を、該カウンタ値を所定の値だけインクリ
メントした値及び該所定の値のうち小さい方の値に設定
し、全パケットキューが選択候補でなくなるまではカウ
ンタ値を増加させたパケットキューを選択候補とはしな
いようにし、（ｄ）出力後に全パケットキューが空にな
ったならば、新たな下位レイヤパケットが各パケットキ
ューに到着した直後までに、全カウンタ値をそれぞれの
パケットキューに対応する所定の値に設定した状態にな
っているように、カウンタ値を制御する（請求項１
３）。

【００３５】上記（ａ）は、出力しようとする同一の上
位レイヤパケットに所属する下位レイヤパケットの量が
保持されたカウンタ値より大きくてもその下位レイヤパ
ケットの出力を許可するようにそのパケットキューを選
択可能であることを意味する。上記（ｂ）は、出力しよ
うとするパケット量がカウンタ値より大きかった場合、
カウンタ値が負になることを意味する。出力した分をデ
クリメントする際、パケット長記憶手段がある場合はそ
のパケット長を利用しても良い。上記（ｃ）によれば、
カウンタ値が負の場合は空になっても所定の値より小さ
い値にしかならず、このことは、残っていた出力許可数
を超えて出力したパケットキューについては超えた分に
応じて差し引いた数を割り当てることを意味する。上記
（ｄ）は、全パケットキューが空になったなら、残って
いた出力許可数を超えて出力したパケットキューにも差
し引きを行わない数を割り当ててあげることを意味す
る。

【００３６】ここで、上記（ｄ）を、例えば次のように
実現しても良い。すなわち、全パケットキューが空にな
る毎に異なる値を記憶するビジー期間記憶手段と、パケ
ットキュー対応に最後に下位レイヤパケットを出力した
時の前記ビジー期間記憶手段の値を保持する出力時ビジ
ー期間記憶手段とを更に設け、前記パケットスケジュー
リング手段は、あるパケットキューに新たな下位レイヤ
パケットが入力された時に該パケットキューに対応する
出力時ビジー期間記憶手段の値が前記ビジー期間記憶手
段の値と異なるならば、この出力時ビジー期間記憶手段
の値を前記ビジー期間記憶手段の値に設定するとともに
対応するカウンタ値を所定の値に設定する（請求項１
４）。

【００３７】本発明（請求項１５）は、下位レイヤパケ
ットを複数の仮想コネクションから受信し、この受信し
た下位レイヤパケットを受信に用いられた仮想コネクシ
ョンに対応するパケットキューに入力する受信手段と、
ノンインターリーブなスケジューリングを行う請求項２
または５の発明に於けるスケジューリング手段により出
力の許可された下位レイヤパケットを一つの仮想コネク
ションに対して送信する送信手段とを更に具備したこと
を特徴とする。

【００３８】これにより、複数の仮想コネクションから
受信した下位レイヤパケットを、公平性の保証されたノ
ンインターリーブなスケジューリングを行いつつ、一つ
の仮想コネクションに多重して転送することが可能にな
る。以上に説明した装置に係る各発明は、例えば請求項
１６〜１９に示すように、方法の発明としても成立す
る。

【００３９】

【発明の実施の形態】以下、図面を参照しながら、本発
明の実施形態について説明する。なお、本発明のパケッ
ト通信装置は、パケット交換機、パケット多重化装置な
ど、固定長パケットの多重化を行なう装置において、パ
ケットのバッファリングが生じる部分のいずれにも適用
可能である。また、パケット交換機に適用する場合に
は、従来のパケット交換機の特定の入出力ポートに本実
施形態のパケット通信装置を接続する構成でもよい。

【００４０】図１に、本発明の第１の実施形態に係るパ
ケット通信装置の構成例を示す。本発明の第１の実施形
態のパケット通信装置は、ＡＡＬ５パケット（可変長／
上位レイヤパケット）を分割して成るＡＴＭのセル（固
定長／下位レイヤパケット）をノンインターリーブかつ
ノンカットスルーに出力するためのものであり、セル入
力部、セル出力部、出力待ちのセルを蓄積するためのＶ
Ｃ毎のパケットキュー（セルキュー）１１〜１３、スケ
ジューリング手段から構成される。また、スケジューリ
ング手段は、ＶＣ毎に現在到着中の上位レイヤパケット
のパケット長をカウントするためのパケット長カウンタ
２１〜２３と、パケット長カウンタがカウントを終了し
たパケット長を蓄積するためのパケット長キュー３１〜
３３から構成されるパケット長記憶手段とを有する。

【００４１】図１において、セルはすべてＡＡＬ５パケ
ットを分割したセルであり、白丸または黒丸で表され
る。ここで、白丸は継続表示ビットがオンのセル（非最
終セル）、黒丸は継続表示ビットがオフのセル（最終セ
ル）である。

【００４２】本パケット通信装置に到着したセルは、セ
ル入力部においてヘッダ処理が行なわれ、入力セルが所
属するＶＣに対応するセルキューに入力される。このと
き、対応するパケット長カウンタが１だけインクリメン
トされる。インクリメント後、もし、入力セルの継続表
示ビットがオフであれば、パケット長カウンタの値をパ
ケット長キューに入力するとともに、パケット長カウン
タを０にクリアする。

【００４３】図１において、セルキュー１（１１）へは
上位レイヤパケットの最終セルがまだ到着していないた
め、パケット長キュー１（３１）は空である。セルキュ
ー２（１２）へは、上位レイヤパケットの最終セルがす
でに２個到着しており、それぞれの最終セルの到着時点
のパケット長カウンタ２（２２）の値＝２がパケット長
キュー２（３２）に入力されている。さらにセルキュー
２のパケット長カウンタ（２２）は、現在は３番目の上
位レイヤパケットのパケット長をカウント中である。ま
た、セルキュー３（１３）は上位レイヤパケットの最終
セル到着後、パケット長カウンタ（２３）の値＝３がパ
ケット長キュー３（３３）に入れられ、パケット長カウ
ンタ３（２３）がクリアされた状態を表している。

【００４４】スケジューリング手段は、各ＶＣキュー内
のパケット長キューの先頭にあるパケット長の情報を基
に出力ＶＣキューを選択する。選択アルゴリズムとして
は、一般の可変長パケットのスケジューリングアルゴリ
ズムが使用可能である。

【００４５】ここでは、パケット長キューが空でないよ
うなセルキューを選択するものとする。例えば、図１に
おいて、セルキュー１（１１）は、セルキューにはセル
が溜っているものの、パケット長キュー１（３１）が空
であるため選択の対象とはならない。すなわち、ノンカ
ットスルーなスケジューリングとなる。

【００４６】スケジューリング手段は現在選択している
ＶＣのＶＣＩをセル出力部に通知する。出力セルキュー
が選択されない場合には、ＶＣＩとして負の値をセル出
力部に通知する。また、セル出力部からスケジューリン
グ手段へは、出力セルが最終セルかどうかが通知され、
最終セル以外であった場合には、現在選択中のＶＣを引
続き選択するようにする。すなわち、ノンインターリー
ブなスケジューリングとなる。

【００４７】セル出力部は、スケジューリング手段から
通知されたＶＣＩに対応するセルキューにセルがあれば
先頭セルを取り出して出力する。負の値を持つＶＣＩが
通知された場合には空セルが出力される。さらに、出力
セルが最終セルであるかどうかをスケジューリング手段
に通知する。最終セルが出力されると、対応するパケッ
ト長はパケット長キューから削除される。

【００４８】例えば、図１において、スケジューリング
手段が所定のアルゴリズムによりＶＣ２、ＶＣ３、 Ｖ
Ｃ２の順に出力ＶＣを選択した場合には、セルキュー２
から２個、セルキュー３から３個、セルキュー２から２
個、の順にセルが出力される。

【００４９】図２には、本発明の第２の実施形態に係る
パケット通信装置の構成例を示す。これは、ＡＴＭにお
けるＡＡＬ５（上位レイヤ）パケットのセル（下位レイ
ヤパケット）をノンインターリーブかつノンカットスル
ーに出力するためのものであり、かつ、上位レイヤパケ
ットのパケット長が上位レイヤパケットのヘッダまたは
トレイラ部分の定められた位置に書き込まれており、こ
の情報をパケット通信装置が読みとることができる場合
の構成例である。

【００５０】図２において、パケット通信装置は、セル
入力部、セル出力部、出力待ちのセルを蓄積するための
ＶＣ毎のパケットキュー（セルキュー）１１〜１３、ス
ケジューリング手段から構成される。また、スケジュー
リング手段は、入力セルのペイロードから上位レイヤパ
ケットのパケット長フィールドを読み出すパケット長抽
出手段と、パケット長抽出手段が読み出したパケット長
を蓄積するためのパケット長キュー３１〜３３から構成
されるパケット長記憶手段とを有する。

【００５１】図２において、セルはすべてＡＡＬ５パケ
ットを分割したセルであり、白丸または黒丸で表され
る。ここで、白丸は継続表示ビットがオンのセル（非最
終セル）、黒丸は継続表示ビットがオフのセル（最終セ
ル）である。

【００５２】本パケット通信装置に到着したセルは、セ
ル入力部においてヘッダ処理が行なわれ、入力セルが所
属するＶＣに対応するセルキューに入力される。もし、
入力セルの継続表示ビットがオフであれば、パケット長
抽出手段は、入力セルのペイロード部内の定められたフ
ィールドからパケット長を読出して対応するＶＣのパケ
ット長キューに入力する。

【００５３】図２において、セルキュー１（１１）には
上位レイヤパケットの最終セルがまだ到着していないた
め、パケット長キュー１（３１）は空である。セルキュ
ー２（１２）へは、上位レイヤパケットの最終セルがす
でに２個到着しており、それぞれの最終セルが所属する
上位レイヤパケットのパケット長＝２がパケット長キュ
ー２（３２）に入力されている。また、セルキュー３
（１３）には３セル分の上位レイヤパケットが１個到着
しており、したがって、パケット長＝３がパケット長キ
ュー３（３３）に入れられている。

【００５４】スケジューリング手段は、各セルキュー内
のパケット長キューの先頭にあるパケット長の情報を基
に出力セルキューを選択する。選択アルゴリズムとして
は、一般の可変長パケットのスケジューリングアルゴリ
ズムが使用可能である。

【００５５】ここでは、パケット長キューが空でないよ
うなセルキューを選択するものとする。例えば、図２に
おいて、セルキュー１（１１）にはセルが溜っているも
のの、パケット長キュー１（３１）が空であるため選択
の対象とはならない。すなわち、ノンカットスルー・ス
ケジューリングとなる。

【００５６】また、スケジューリング手段は、現在選択
しているＶＣのＶＣＩをセル出力部に通知する。出力Ｖ
Ｃが選択されない場合には、ＶＣＩとして負の値をセル
出力部に通知する。また、セル出力部からスケジューリ
ング手段へは、出力セルが最終セルかどうかが通知さ
れ、最終セル以外であった場合には、現在選択中のＶＣ
を引続き選択するようにする。

【００５７】セル出力部は、スケジューリング手段から
通知されたＶＣＩに対応するセルキューにセルがあれば
先頭セルを取り出して出力する。負の値を持つＶＣＩが
通知された場合には空セルが出力される。さらに、出力
セルが最終セルであるかどうかをスケジューリング手段
に通知する。

【００５８】例えば、図２において、スケジューリング
手段が所定のアルゴリズムによりＶＣ２、ＶＣ３、ＶＣ
２の順に出力ＶＣを選択した場合には、セルキュー２の
セルキューから２個、セルキュー３のセルキューから３
個、セルキュー２のセルキューから２個、の順にセルが
出力される。

【００５９】これにより、上位レイヤパケットのパケッ
ト長が最終セルのペイロード部に含まれる場合に、第１
の実施形態のようなカウンタを用いずにパケット長情報
を抽出することができる。

【００６０】ここで、上記第１／第２の実施形態におけ
るパケット長記憶手段は、以上に示したように下位レイ
ヤパケットの出力のノンインターリーブなスケジューリ
ングに用いることができる他、上位レイヤパケットを組
み立てた後でその上位レイヤパケットに対してスケジュ
ーリングするような場合においても用いることができ
る。すなわち、ＡＡＬ５パケットのように、可変長（上
位レイヤ）パケットで、かつ、パケット長の情報がパケ
ットのヘッダ部ではなく、トレイラ部分に書かれている
ような場合には、パケット長の情報をスケジューリング
手段が利用するために、上記パケット長記憶手段が必要
となる。

【００６１】この場合、パケット長記憶手段は、カウン
トするかトレイラ部にアクセスすることに得たパケット
長の値またはパケット長の値が格納されているメモリ内
アドレスを、パケット長キューに入れるかまたは各パケ
ットの先頭部に付加することににより実現される。

【００６２】次に、図３及び図４に、上記第１もしくは
第２の実施形態に係るパケット通信装置のスケジューリ
ング手段の動作例を示す。ここでは、ＡＡＬ５パケット
のセルに対し、ノンカットスルーなノンインターリーブ
・スケジューリングを行なう場合、すなわち、ＡＡＬ５
パケットの最終セルが到着したセルキューのみをノンイ
ンターリーブにサービスする場合について示す。

【００６３】ｑ［ｉ］、ｆ［ｉ］、ｌ［ｉ］（０＜＝ｉ
＜＝Ｎ、Ｎ：ＶＣＩの最大値）をそれぞれ、ＶＣキュー
ｉのセルキュー、パケット長キュー、パケット長カウン
タとする。ｓｅｒｖは、スケジューリング手段が現在選
択している出力ＶＣキューの番号を表す。ｓｅｒｖ＜０
のときはスケジューリング手段が出力ＶＣキューを選択
していないことを表す。

【００６４】スケジューリング手段は、初期化処理、セ
ル入力処理、セル出力処理の３種類の処理を行なう。初
期化処理（図３（ａ））は、システム起動時に１度実行
される。初期化処理では、まず、各ＶＣキューｉのセル
キューに対し、ｉｎｉｔ＿ｑｕｅｕｅ（ｑ［ｉ］）、ｉ
ｎｉｔ＿ｑｕｅｕｅ（ｆ［ｉ］）が実行される。ここ
で、ｉｎｉｔ＿ｑｕｅｕｅ（ｘ）は、キューｘを初期化
する処理を表す。次に、ｓｅｒｖ：＝−１、各ＶＣｉに
ついてｌ［ｉ］：＝０、とした後、セル選択アルゴリズ
ムに依存した処理ｓｃｈｅｄ＿ｉｎｉｔ＿ＮＣＴ（Ａ）
を実行する。ここで、ｓｃｈｅｄ＿ｉｎｉｔ＿ＮＣＴ
（Ａ）は、セル選択アルゴリズムＡに依存したノンカッ
トスルー用の初期化処理である（以上Ｓ１）。

【００６５】セル入力処理（図３（ｂ））では、以下の
ステップで到着セルが処理される。到着セルをＣとす
る。まず、ＣのＶＰＩ／ＶＣＩ値を得るために、ｉ：＝
ｖｃｉ（Ｃ）とする。ｖｃｉ（Ｃ）は、セルＣのヘッダ
部のＶＰＩ／ＶＣＩ値を返す関数である。次に、セルＣ
をセルキューｑ［ｉ］に入れるためにｅｎｑｕｅｕｅ
（ｑ［ｉ］，Ｃ）を実行する。さらに、パケット長カウ
ンタｌ［ｉ］を１だけインクリメントする（以上Ｓ
２）。

【００６６】次に、ｅｏｆ（Ｃ）＝０であれば（Ｓ３
Ｎｏ）、セル入力処理は終了する。ここで、ｅｏｆ
（Ｃ）は、セルＣのヘッダの継続表示ビットを見て、Ｃ
がＡＡＬ５パケットの最終セルであれば１を、そうでな
ければ０を返す関数である。一方、ｅｏｆ（Ｃ）＝１で
ある場合、もし、ｌｅｎ（ｆ［ｉ］）＝０であれば（Ｓ
４Ｙｅｓ）、到着が完了したＡＡＬ５パケットをスケジ
ューリングするためにｓｅｎｄ＿ｉｎ＿ＮＣＴ（Ａ，
ｉ）を実行する（Ｓ５）。ここで、ｌｅｎ（ｘ）は、キ
ューｘのキュー長（蓄積エントリ数）を返す関数であ
る。また、ｓｅｎｄ＿ｉｎ＿ＮＣＴ（Ａ、ｉ）は、ノン
カットスルーの場合のセル選択アルゴリズムＡに依存し
た、ＶＣキューｉに関する入力処理である。

【００６７】最後に、キュー長カウンタｌ［ｉ］の値を
ｆ［ｉ］に入れるためにｅｎｑｕｅｕｅ（ｆ［ｉ］，ｌ
［ｉ］）を実行し、ｌ［ｉ］：＝０とする（Ｓ６）。セ
ル出力処理（図４）では、以下のステップで出力セルが
処理される。まず、ｓｅｒｖ＜０なら（Ｓ１１ Ｙｅ
ｓ）、次の出力セルキューを選択するために、ｓｅｒ
ｖ：＝ｓｃｈｅｄ＿ｃｈｏｏｓｅ（Ａ）を実行する（Ｓ
１２）。ここで、ｓｃｈｅｄ＿ｃｈｏｏｓｅ（Ａ）は、
セル選択アルゴリズムＡに依存して出力するセルキュー
を返す関数である。

【００６８】次に、ｓｅｒｖ＞＝０なら（Ｓ１３ Ｙｅ
ｓ）、セルキューｑ［ｓｅｒｖ］からセルを取り出すた
めに、Ｃ：＝ｄｅｑｕｅｕｅ（ｑ［ｓｅｒｖ］）を実行
する。ｄｅｑｕｅｕｅ（ｘ）は、キューｘの先頭のエン
トリを取り出す関数である。次に、セルＣが最終セルか
どうかをチェックするためにＥＯＦ：＝ｅｏｆ（Ｃ）を
実行し、セルＣを出力するためにｔｒａｎｓｍｉｔ
（Ｃ）を実行する（以上Ｓ１４）。

【００６９】その後、出力したセルがＡＡＬ５パケット
の最終セルであれば、すなわち、ＥＯＦ＝１であれば
（Ｓ１５ Ｙｅｓ）、パケット長キューｆ［ｓｅｒｖ］
から、出力したＡＡＬ５パケットのパケット長を取り出
すために、Ｌ：＝ｄｅｑｕｅｕｅ（ｆ［ｓｅｒｖ］）を
実行し、セルキューｓｅｒｖの次のパケットをスケジュ
ーリングするために、ｓｅｎｄ＿ｏｕｔ＿ＮＣＴ（Ａ，
Ｌ，ｉ）を実行し、最後に、このセルキューの選択をと
りやめるためにｓｅｒｖ：＝−１とする。ここで、ｓｅ
ｎｄ＿ｏｕｔ＿ＮＣＴ（Ａ，Ｌ，ｉ）は、ノンカットス
ルーの場合のセル選択アルゴリズムＡに依存した、ＶＣ
キューｉに関する出力処理である。その際、出力パケッ
トのパケット長Ｌの情報がｓｅｎｄ＿ｏｕｔ＿ＮＣＴ
（Ａ，Ｌ，ｉ）内で使用される（以上Ｓ１６）。

【００７０】次に、図５及び図６に、図３及び図４に示
したノンカットスルー・スケジューリングにおいて、セ
ル選択アルゴリズムとして特願平８−２３９１５９に示
されるような重み付け公平キューイング（ＷＦＱ）アル
ゴリズムを採用した場合の、セル選択アルゴリズム依存
部分のフローチャートを示す。

【００７１】このセル選択アルゴリズムにおいては、２
個のスケジューリングキューＱ、Ｑ’を使用する。Ｑは
現在のラウンドで出力待ちのＶＣＩを入れるためのキュ
ー、Ｑ’は次のラウンドで出力待ちのＶＣＩを入れるた
めのキューである。ここで、ラウンドとは、各セルキュ
ーｉから最大ｗ［ｉ］個セルを送出できる期間のことで
ある。ｗ［ｉ］は、ＶＣｉに対して割当てられるサービ
スに関する重みであり、システムの最大パケット長以上
の値をとる。また、各ＶＣキューｉは、現在のラウンド
で出力可能なセル数を記憶するカウンタｃ［ｉ］を持
つ。

【００７２】ｓｃｈｅｄ＿ｉｎｉｔ＿ＮＣＴ（ＷＦＱ）
では、図５（ａ）に示すように、スケジューリングキュ
ーＱ、Ｑ’を初期化するためにｉｎｉｔ＿ｑｕｅｕｅ
（Ｑ）、ｉｎｉｔ＿ｑｕｅｕｅ（Ｑ’）を実行する。次
に、各ＶＣキューｉに対してカウンタｃ［ｉ］にｗ
［ｉ］を設定するために、ｃ［ｉ］：＝ｗ［ｉ］を実行
する（以上Ｓ２１）。

【００７３】ｓｃｈｅｄ＿ｉｎ＿ＮＣＴ（ＷＦＱ，ｉ）
では、図６（ａ）に示すように、スケジューリングキュ
ーＱに入力ＶＣＩ＝ｉを入れるためにｅｎｑｕｅｕｅ
（Ｑ、ｉ）を実行する（Ｓ３１）。

【００７４】ｓｅｎｄ＿ｃｈｏｏｓｅ（ＷＦＱ）は、図
５（ｂ）に示すように、選択ＶＣＩを初期化するために
ｉ：＝−１とする（Ｓ２２）。次に、スケジューリング
キューＱのキュー長を調べる。ｌｅｎ（Ｑ）＝０であれ
ば（Ｓ２３ Ｙｅｓ）、ＱとＱ’を入れ換えるために、
ｓｗａｐ（Ｑ、 Ｑ’）を実行する（Ｓ２４）。その
後、もう一度スケジューリングキューＱのキュー長を調
べる。ｌｅｎ（Ｑ）＞０なら（Ｓ２５ Ｙｅｓ）、Ｑか
ら出力ＶＣＩを取り出すためにｉ：＝ｄｅｑｕｅｕｅ
（Ｑ）を実行する（Ｓ２６）。最後にｒｅｔｕｒｎ
（ｉ）で出力ＶＣＩ値ｉを返す（Ｓ２７）。

【００７５】ｓｃｈｅｄ＿ｏｕｔ＿ＮＣＴ（ＷＦＱ，
Ｌ，ｓｅｒｖ）では、図６（ｂ）に示すように、まず、
カウンタ値ｃ［ｓｅｒｖ］をパケット長Ｌだけデクリメ
ントするために、ｃ［ｓｅｒｖ］：＝ｃ［ｓｅｒｖ］−
Ｌを実行し、ｆ［ｓｅｒｖ］の先頭の値を参照するため
に、Ｌ’：＝ｈｅａｄ（ｆ［ｓｅｒｖ］）とする（Ｓ３
２）。ただし、ｈｅａｄ（ｘ）は、キューｘの先頭のエ
ントリを取り出すことなく参照する関数である。

【００７６】次に、パケット長キューｆ［ｓｅｒｖ］が
空でなく、かつ、カウンタ値が正であれば（Ｓ３３ Ｙ
ｅｓ）、ｓｅｒｖをスケジューリングＱに入れる（Ｓ３
４）。そうでなく（Ｓ３３ Ｎｏ）、もし、パケット長
キューｆ［ｓｅｒｖ］が空でなければ（Ｓ３５ Ｙｅ
ｓ）、ｃ［ｓｅｒｖ］＜＝０であるため、次のラウンド
でサービスさせるためにｓｅｒｖをスケジューリング
Ｑ’に入れ、ｃ［ｓｅｒｖ］をｗ［ｓｅｒｖ］だけイン
クリメントさせる（Ｓ３６）。もし、パケット長キュー
ｆ［ｓｅｒｖ］が空であれば（Ｓ３５ Ｎｏ）、ｃ［ｓ
ｅｒｖ］をｗ［ｓｅｒｖ］にリセットする（Ｓ３７）。

【００７７】以下には、ＡＡＬ５パケットを分割したセ
ルに対し、カットスルーなノンインターリーブ・スケジ
ューリングを行なう場合、すなわち、ＡＡＬ５パケット
の最終セルが未到着なセルキューもノンインターリーブ
にサービスされる場合について説明する。なお、カット
スルー・スケジューリングを行う場合のパケット通信装
置の構成は、図１もしくは図２に示したものと同様にな
り、スケジューリング手段の動作を以下のようにする。

【００７８】図７〜９に本ケースのスケジューリング手
段の一つの動作例を示す。本例では、出力中のＶＣの最
終セルがあらかじめ定められた時間（ＭＡＸＷＡＩＴセ
ル時間）内に届かない場合には、継続表示ビットをオフ
にしたダミーセルがパケット通信装置内で生成、出力さ
れ、以降、継続表示ビットをオフにしたセルが到着する
までこのＶＣの到着セルは廃棄されるものとする。

【００７９】ここで、ＭＡＸＷＡＩＴの値は、ＶＣごと
に異なる値に設定してもよい。その場合には、ＶＣのト
ラヒックパラメータや送出レートに基づいてＭＡＸＷＡ
ＩＴの値を決めてもよい。

【００８０】ｑ［ｉ］、ｆ［ｉ］、ｌ［ｉ］（０＜＝ｉ
＜＝Ｎ）をそれぞれ、ＶＣキューｉのセルキュー、ＶＣ
キューｉのパケット長キュー、パケット長カウンタとす
る。ｓｅｒｖは、スケジューリング手段が現在選択して
いるか出力ＶＣキューの番号を表す。ｓｅｒｖ＜０のと
きはスケジューリング手段が出力ＶＣキューを選択して
いないことを表す。

【００８１】また、ｗａｉｔは現在出力中のＶＣのセル
キューが空になってから経過した時間をカウントするカ
ウンタ、Ｔはシステムの系内セル数をカウントするカウ
ンタである。なお、Ｔは使用されない場合もある。ま
た、ｅｒｒｏｒ［ｉ］は、ＶＣキューｉのセルキューが
選択されており、かつセルキューが空になってからＭＡ
ＸＷＡＩＴ時間経過したかどうかを記憶するフラグであ
る。

【００８２】スケジューリング手段は、初期化処理、セ
ル入力処理、セル出力処理の３種類の処理を行なう。初
期化処理（図７）は、システム起動時に１度実行され
る。初期化処理では、まず、各ＶＣキューｉのセルキュ
ーに対し、ｉｎｉｔ＿ｑｕｅｕｅ（ｑ［ｉ］）、ｉｎｉ
ｔ＿ｑｕｅｕｅ（ｆ［ｉ］）が実行される。ここで、ｉ
ｎｉｔ＿ｑｕｅｕｅ（ｘ）は、キューｘを初期化する処
理を表す。次に、ｓｅｒｖ：＝０、ｗａｉｔ：＝０、
Ｔ：＝０、各ＶＣｉについてｌ［ｉ］：＝０、ｅｒｒｏ
ｒ［ｉ］：＝０とした後、セル選択アルゴリズムに依存
した処理ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ（Ａ）を実行す
る。ここで、ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ（Ａ）は、セ
ル選択アルゴリズムＡに依存したカットスルー用の初期
化処理である（以上Ｓ４１）。

【００８３】セル入力処理（図８）では、以下のステッ
プで到着セルが処理される。到着セルをＣとする。ま
ず、ＣのＶＰＩ／ＶＣＩ値を得るために、ｉ：＝ｖｃｉ
（Ｃ）とする（Ｓ５１）。ｖｃｉ（Ｃ）は、セルＣのヘ
ッダ部のＶＰＩ／ＶＣＩ値を返す関数である。

【００８４】次に、現在出力中のＶＣのセルキューが空
になってからＭＡＸＷＡＩＴ時間経過していれば、すな
わち、ｅｒｒｏｒ［ｉ］＝１なら（Ｓ５２ Ｙｅｓ）、
セルＣはセルキューｑ［ｉ］には入れられず、さらにセ
ルＣがＡＡＬ５パケットの最終セル、すなわちｅｏｆ
（Ｃ）＝１なら（Ｓ５４ Ｙｅｓ）、ｅｒｒｏｒ
［ｉ］：＝０としｃ［ｓｅｒｖ］をｗ［ｓｅｒｖ］にリ
セットする（Ｓ５５）。

【００８５】一方、ｅｒｒｏｒ［ｉ］＝０であれば（Ｓ
５２ Ｎｏ）、以下の処理を行なう。まず、セルＣをセ
ルキューｑ［ｉ］に入れるためにｅｎｑｕｅｕｅ（ｑ
［ｉ］，Ｃ）を実行し、ｌ［ｉ］およびＴを１だけイン
クリメントした後、到着したセルをスケジューリングす
るために、ｓｅｎｄ＿ｉｎ＿ＣＴ（Ａ，ｉ）を実行する
（Ｓ５３）。ここで、ｓｅｎｄ＿ｉｎ＿ＣＴ（Ａ、
ｉ）は、カットスルーの場合のセル選択アルゴリズムＡ
に依存した、ＶＣキューｉに関する入力処理である。次
に、ｅｏｆ（Ｃ）＝０であれば、セル入力処理は終了す
る。ここで、ｅｏｆ（Ｃ）は、セルＣのヘッダの継続表
示ビットを見て、ＣがＡＡＬ５パケットの最終セルであ
れば１を、そうでなければ０を返す関数である。一方、
ｅｏｆ（Ｃ）＝１である場合（Ｓ５６ Ｙｅｓ）、キュ
ー長カウンタｌ［ｉ］の値をｆ［ｉ］に入れるためにｅ
ｎｑｕｅｕｅ（ｆ［ｉ］，ｌ［ｉ］）を実行し、ｌ
［ｉ］：＝０とする（Ｓ５７）。

【００８６】セル出力処理（図９）では、以下のステッ
プで出力セルが処理される。まず、ｓｅｒｖ＜０なら
（Ｓ６１ Ｙｅｓ）、次の出力セルキューを選択するた
めにｓｅｒｖ：＝ｓｃｈｅｄ＿ｃｈｏｏｓｅ（Ａ）を実
行する（Ｓ６２）。ここで、ｓｃｈｅｄ＿ｃｈｏｏｓｅ
（Ａ）は、セル選択アルゴリズムＡに依存して出力する
セルキューを返す関数である。

【００８７】次に、ｓｅｒｖ＜０なら（Ｓ６３ Ｎｏ）
セル出力処理は終了する。ｓｅｒｖ＞＝０なら（Ｓ６３
Ｙｅｓ）、まず、セルキューｑ［ｓｅｒｖ］にセルが
あるかどうか、すなわち、ｌｅｎ（ｑ［ｓｅｒｖ］）＞
０かどうかをチェックする。

【００８８】このとき、ｌｅｎ（ｑ［ｓｅｒｖ］）＞０
（Ｓ６４ Ｙｅｓ）であれば、以下の処理を行なう。ま
ず、ｗａｉｔ：＝０とし、セルキューｑ［ｓｅｒｖ］か
らセルを取り出すために、Ｃ：＝ｄｅｑｕｅｕｅ（ｑ
［ｓｅｒｖ］）を実行する。ｄｅｑｕｅｕｅ（ｘ）は、
キューｘの先頭のエントリを取り出す関数である。次
に、セルＣが最終セルかどうかをチェックするためにＥ
ＯＦ：＝ｅｏｆ（Ｃ）を実行し、ｔｒａｎｓｍｉｔ
（Ｃ）を実行してセルＣを出力し、Ｔを１だけデクリメ
ントする（以上Ｓ６５）。

【００８９】その後、出力したセルがＡＡＬ５パケット
の最終セルであれば、すなわち、ＥＯＦ＝１であれば
（Ｓ６６ Ｙｅｓ）、パケット長キューｆ［ｓｅｒｖ］
から、出力したＡＡＬ５パケットのパケット長を取り出
すために、Ｌ：＝ｄｅｑｕｅｕｅ（ｆ［ｓｅｒｖ］）を
実行し、パケットキューｓｅｒｖの次のパケットをスケ
ジューリングするために、ｓｅｎｄ＿ｏｕｔ＿ＣＴ
（Ａ，Ｌ，ｓｅｒｖ）を実行し、最後に、このパケット
キューの選択をとりやめるためにｓｅｒｖ：＝−１とす
る（Ｓ６９）。ここで、ｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ、
Ｌ、ｉ）は、カットスルーの場合のセル選択アルゴリズ
ムＡに依存した、ＶＣキューｉに関するセル選択アルゴ
リズム依存出力処理である。その際、出力パケットのパ
ケット長Ｌの情報がｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ，Ｌ，
ｉ）内で使用される。

【００９０】一方、ＥＯＦ＝０であれば（Ｓ６６ Ｎ
ｏ）、パケットキューｑ［ｓｅｒｖ］が空、すなわち、
ｌｅｎ（ｑ［ｓｅｒｖ］）＝０かどうかをチェックす
る。ｌｅｎ（ｑ［ｓｅｒｖ］）＝０であれば（Ｓ６７
Ｙｅｓ）、ＡＡＬ５パケットの最終セルが未到着のまま
キューが空になったことを意味する。このとき、ｗａｉ
ｔ：＝ＭＡＸＷＡＩＴとする（Ｓ６８）。

【００９１】一方、ｌｅｎ（ｑ［ｓｅｒｖ］）＝０であ
ったならば（Ｓ６４ Ｎｏ）、ｗａｉｔタイマーをデク
リメントするために、ｗａｉｔ：＝ｗａｉｔ−１とする
（Ｓ７０）。ｗａｉｔ＝０であれば（Ｓ７１ Ｙｅ
ｓ）、ダミー最終セルを送出し、ｅｒｒｏｒ［ｉ］：＝
１とする（Ｓ７２）。

【００９２】図１０〜１１には、ＡＡＬ５パケットを分
割したセルに対し、カットスルーなノンインターリーブ
・スケジューリングを行なう場合（パケット通信装置の
構成は、図１もしくは図２に示したものと同様）のスケ
ジューリング手段の別の動作例を示す。本例では、セル
出力中のＶＣの最終セルが到着していない状態でシステ
ムの系内セル数がＴＭＡＸを越えた場合には、継続表示
ビットをオフにしたダミーセルがパケット通信装置内で
生成、出力され、以降、継続表示ビットをオフにしたセ
ルが到着するまでこのＶＣの到着セルは廃棄されるもの
とする。

【００９３】ｑ［ｉ］、ｆ［ｉ］、ｌ［ｉ］（１＜＝ｉ
＜＝Ｎ）をそれぞれ、ＶＣキューｉのパケットキュー、
パケット長キュー、パケット長カウンタとする。ｓｅｒ
ｖは、スケジューリング手段が現在選択しているか出力
ＶＣキューの番号を表す。ｓｅｒｖ＜０のときはスケジ
ューリング手段が出力ＶＣキューを選択していないこと
を表す。

【００９４】また、Ｔはシステムの系内セル数をカウン
トするカウンタである。また、ｅｒｒｏｒ［ｉ］は、各
ＶＣごとに、現在出力中のＶＣのセルキューが空になっ
てからＴ＞ＴＭＡＸになったかどうかを記憶するフラグ
である。

【００９５】スケジューリング部は、初期化処理、セル
入力処理、セル出力処理の３種類の処理を行なう。初期
化処理（図１０）は、システム起動時に１度実行され
る。初期化処理では、まず、各ＶＣキューｉのセルキュ
ーに対し、ｉｎｉｔ＿ｑｕｅｕｅ（ｑ［ｉ］）、ｉｎｉ
ｔ＿ｑｕｅｕｅ（ｆ［ｉ］）が実行される。ここで、ｉ
ｎｉｔ＿ｑｕｅｕｅ（ｘ）は、キューｘを初期化する処
理を表す。次に、ｓｅｒｖ：＝０、Ｔ：＝０、各ＶＣｉ
についてｌ［ｉ］：＝０、ｅｒｒｏｒ［ｉ］：＝０とし
た後、セル選択アルゴリズムに依存した処理ｓｃｈｅｄ
＿ｉｎｉｔ＿ＣＴ（Ａ）を実行する。ここで、ｓｃｈｅ
ｄ＿ｉｎｉｔ＿ＣＴ（Ａ）は、セル選択アルゴリズムＡ
に依存したカットスルー用の初期化処理である（以上Ｓ
８１）。

【００９６】セル入力処理は、図８のセル入力処理と同
じ動作である。セル出力処理（図１１）では、以下のス
テップで出力セルが処理される。まず、ｓｅｒｖ＜０な
ら（Ｓ９１ Ｙｅｓ）、次の出力セルキューを選択する
ためにｓｅｒｖ：＝ｓｃｈｅｄ＿ｃｈｏｏｓｅ（Ａ）を
実行する（Ｓ９２）。ここで、ｓｃｈｅｄ＿ｃｈｏｏｓ
ｅ（Ａ）は、セル選択アルゴリズムＡに依存して出力す
るセルキューを返す関数である。

【００９７】次に、ｓｅｒｖ＜０なら（Ｓ９３ Ｎｏ）
セル出力処理は終了する。ｓｅｒｖ＞＝０なら（Ｓ９３
Ｙｅｓ）、まず、セルキューｑ［ｓｅｒｖ］にセルが
あるかどうか、すなわち、ｌｅｎ（ｑ［ｓｅｒｖ］）＞
０かどうかをチェックする。

【００９８】このとき、ｌｅｎ（ｑ［ｓｅｒｖ］）＞０
であれば（Ｓ９４ Ｙｅｓ）、以下の処理を行なう。ま
ず、セルキューｑ［ｓｅｒｖ］からセルを取り出すため
に、Ｃ：＝ｄｅｑｕｅｕｅ（ｑ［ｓｅｒｖ］）を実行す
る。ｄｅｑｕｅｕｅ（ｘ）は、キューｘの先頭のエント
リを取り出す関数である。次に、セルＣが最終セルかど
うかをチェックするためにＥＯＦ：＝ｅｏｆ（Ｃ）を実
行し、ｔｒａｎｓｍｉｔ（Ｃ）を実行してセルＣを出力
し、Ｔを１だけデクリメントする（以上Ｓ９５）。

【００９９】その後、出力したセルがＡＡＬ５パケット
の最終セルであれば、すなわち、ＥＯＦ＝１であれば
（Ｓ９６ Ｙｅｓ）、パケット長キューｆ［ｓｅｒｖ］
から、出力したＡＡＬ５パケットのパケット長を取り出
すために、Ｌ：＝ｄｅｑｕｅｕｅ（ｆ［ｓｅｒｖ］）を
実行し、セルキューｓｅｒｖの次のパケットをスケジュ
ーリングするために、ｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ，
Ｌ，ｉ）を実行し、最後に、このセルキューの選択をと
りやめるためにｓｅｒｖ：＝−１とする（Ｓ９７）。こ
こで、ｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ，Ｌ，ｉ）は、カッ
トスルーの場合のセル選択アルゴリズムＡに依存した、
ＶＣキューｉに関するセル選択アルゴリズム依存出力処
理である。その際、出力パケットのパケット長Ｌの情報
がｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ，Ｌ，ｉ）内で使用され
る。

【０１００】一方、ｌｅｎ（ｑ［ｓｅｒｖ］）＝０であ
った場合（Ｓ９４ Ｎｏ）、Ｔ＞ＴＭＡＸであれば（Ｓ
９８ Ｙｅｓ）、ダミー最終セルを送出し、ｅｒｒｏｒ
［ｉ］：＝１とする（Ｓ９９）。

【０１０１】次に、図１２及び図１３に、図７〜９もし
くは図１０〜１１に示したようなカットスルー・スケジ
ューリングにおいて、セル選択アルゴリズムとして特願
平８−２３９１５９に示されるような重み付け公平キュ
ーイング（ＷＦＱ）アルゴリズムを採用した場合の、セ
ル選択アルゴリズム依存部分のフローチャートを示す。

【０１０２】このセル選択アルゴリズムにおいては、２
個のスケジューリングキューＱ、Ｑ’を使用する。Ｑは
現在のラウンドで出力待ちのＶＣＩを入れるためのキュ
ー、Ｑ’は次のラウンドで出力待ちのＶＣＩを入れるた
めのキューである。ここで、ラウンドとは、各セルキュ
ーｉから最大ｗ［ｉ］個セルを送出できる期間のことで
ある。ｗ［ｉ］は、ＶＣｉに対して割当てられるサービ
スに関する重みであり、システムの最大パケット長以上
の値をとる。

【０１０３】また、各ＶＣキューｉは、現在のラウンド
で出力可能なセル数を記憶するカウンタｃ［ｉ］、およ
び、最後に出力されたＶＣキューｉのセルが所属するビ
ジー期間を記憶するカウンタｂ［ｉ］を持つ。さらに、
スケジューリング手段全体で、最後に出力されたセルが
所属するビジー期間を記憶するカウンタＢ、および現在
バッファリングされているセル数をカウントするカウン
タＴを持つ。

【０１０４】ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ（ＷＦＱ）で
は、図１２（ａ）に示すように、スケジューリングキュ
ーＱ、Ｑ’を初期化するためにｉｎｉｔ＿ｑｕｅｕｅ
（Ｑ）、ｉｎｉｔ＿ｑｕｅｕｅ（Ｑ’）を実行する。次
に、各ＶＣキューｉに対してｃ［ｉ］：＝ｗ［ｉ］、ｂ
［ｉ］：＝０を実行する。さらにＢ：＝０とする（以上
Ｓ１０１）。

【０１０５】ｓｃｈｅｄ＿ｉｎ＿ＣＴ（ＷＦＱ，ｉ）で
は、図１２（ｂ）に示すように、セル到着直前までセル
キューｑ［ｉ］が空であった場合、すなわち、ｌｅｎ
（ｑ［ｉ］）＝１の場合（Ｓ１２２ Ｙｅｓ）にのみ以
下の処理を行なう。

【０１０６】まず、スケジューリングキューＱに入力Ｖ
ＣＩ＝ｉを入れるためにｅｎｑｕｅｕｅ（Ｑ、ｉ）を実
行する（Ｓ１２３）。次に、ＶＣｉのビジー期間カウン
タｂ［ｉ］の値とＢの値を比較する。ｂ［ｉ］＝Ｂでな
ければ（Ｓ１２４ Ｎｏ）、ＶＣｉが最後に出力されて
からシステムが少なくとも１回はアイドル状態になった
ことを表している。このとき、ｂ［ｉ］：＝Ｂとし、カ
ウンタをリセットするためにｃ［ｉ］：＝ｗ［ｉ］とす
る（Ｓ１２５）。

【０１０７】ｓｃｈｅｄ＿ｃｈｏｏｓｅ（ＷＦＱ）の動
作は、図５（ｂ）で示されたものと同じである。ｓｃｈ
ｅｄ＿ｏｕｔ＿ＣＴ（ＷＦＱ，Ｌ，ｓｅｒｖ）では、図
１３に示すように、まず、カウンタ値ｃ［ｓｅｒｖ］を
パケット長Ｌだけデクリメントするために、ｃ［ｓｅｒ
ｖ］：＝ｃ［ｓｅｒｖ］−Ｌを実行する（Ｓ１１１）。
次に、Ｔ＝０であれば（Ｓ１１２ Ｙｅｓ）、ビジー期
間カウンタＢの値を１だけインクリメントする（Ｓ１１
３）。

【０１０８】次に、パケットキューｑ［ｓｅｒｖ］が空
でなく、かつｃ［ｓｅｒｖ］＞０であれば（Ｓ１１４
Ｙｅｓ）、このラウンド内にさらに選択可能にするた
め、スケジューリングキューＱにｓｅｒｖを入れる（Ｓ
１１５）。

【０１０９】そうでない場合（Ｓ１１４ Ｎｏ）、以下
のように動作する。もしパケットキューｑ［ｓｅｒｖ］
が空でなければ（Ｓ１１６ Ｙｅｓ）、次のラウンドで
選択可能にするため、スケジューリングキューＱ’にｓ
ｅｒｖを入れる（Ｓ１１７）。そして、ｃ［ｓｅｒｖ］
の値を、ｃ［ｓｅｒｖ］をｗ［ｓｅｒｖ］だけインクリ
メントした値とｗ［ｓｅｒｖ］との最小値に設定する
（Ｓ１１８）。

【０１１０】上記例では、選択しているパケットキュー
に上位レイヤパケットの最終セルが到着している場合で
も、すなわち、上位レイヤパケット長が既知の場合で
も、カウンタｃ［ｓｅｒｖ］は負になるが、上位レイヤ
パケット長が既知の場合にあらかじめパケット出力によ
ってカウンタ値が負になることが確実なパケットキュー
は選択しないようにすることも可能である。

【０１１１】図１４には、本発明の第３の実施形態とし
て、カットスルー、かつノンインターリーブなスケジュ
ーリングを行ない、パケット長記憶手段および、パケッ
ト長カウンタまたはパケット長抽出手段を使用しないよ
うな場合のパケット通信装置の構成例を示す。

【０１１２】本発明の第３の実施形態に係るパケット通
信装置は、ＡＡＬ５パケットのセルをノンインターリー
ブかつカットスルーに出力するためのものであり、セル
入力部、セル出力部、出力待ちのセルを蓄積するための
ＶＣ毎のパケットキュー、スケジューリング手段から構
成される。また、スケジューリング手段は、パケット長
カウンタ、パケット長抽出手段、パケット長記憶手段は
有しない。

【０１１３】図１４において、セルはすべてＡＡＬ５パ
ケットを分割したセルであり、白丸または黒丸で表され
る。ここで、白丸は継続表示ビットがオンのセル（非最
終セル）、黒丸は継続表示ビットがオフのセル（最終セ
ル）である。

【０１１４】本パケット通信装置に到着したセルは、セ
ル入力部においてヘッダ処理が行なわれ、入力セルが所
属するＶＣに対応するセルキューに入力される。スケジ
ューリング手段は、まだ出力パケットキューを選択して
いない場合には、空でないパケットキューの中から出力
パケットキューを選択する。すなわち、カットスルーな
スケジューリングとなる。選択アルゴリズムとしては、
一般の可変長パケットのスケジューリングアルゴリズム
が使用可能である。スケジューリング手段は現在選択し
ているＶＣのＶＣＩをセル出力部に通知する。出力パケ
ットキューが選択されない場合には、ＶＣＩとして負の
値をセル出力部に通知する。

【０１１５】また、セル出力部からスケジューリング手
段へは、出力セルが最終セルかどうかが通知され、最終
セル以外であった場合には、現在選択中のＶＣを引続き
選択するようにする。すなわち、ノンインターリーブな
スケジューリングとなる。

【０１１６】さらに、出力パケットキューを選択してい
る場合に、出力パケットキューが所定時間空であった場
合には、継続表示ビットをオフにしたダミーセルを新た
に生成して出力するともに、新たに出力パケットキュー
の選択を行なう。図１４では、所定時間が固定時間ＷＡ
ＩＴＭＡＸである例を示している。

【０１１７】次に、図１５〜１９に、上記第３の実施形
態に係るパケット通信装置のスケジューリング手段の動
作例を示す。図１５、１６、１７は上記所定時間がＷＡ
ＩＴＭＡＸである場合について、図１８、１９は上記所
定時間が各パケットキューの系内セル数の和がしきい値
ＴＭＡＸを越えるまでの場合を示している。

【０１１８】スケジューリング部は、初期化処理、セル
入力処理、セル出力処理の３種類の処理を行なう。図１
５に、所定時間がＷＡＩＴＭＡＸである場合の、初期化
処理を示す。初期化処理は、システム起動時に１度実行
される。初期化処理では、まず、各ＶＣキューｉのセル
キューに対し、ｉｎｉｔ＿ｑｕｅｕｅ（ｑ［ｉ］）が実
行される。ここで、ｉｎｉｔ＿ｑｕｅｕｅ（ｘ）は、キ
ューｘを初期化する処理を表す。次に、ｓｅｒｖ：＝−
１、ｗａｉｔ：＝０、各ＶＣについてｅｒｒｏｒ
［ｉ］：＝０、とした後、セル選択アルゴリズムに依存
した処理ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ（Ａ）を実行す
る。ここで、ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ（Ａ）は、セ
ル選択アルゴリズムＡに依存したカットスルー用の初期
化処理である（以上Ｓ１２１）。

【０１１９】図１６に、所定時間がＷＡＩＴＭＡＸであ
る場合の、セル入力処理を示す。セル入力処理では、以
下の手順で到着セルが処理される。到着セルをＣとす
る。まず、ＣのＶＰＩ／ＶＣＩ値を得るために、ｉ：＝
ｖｃｉ（Ｃ）とする（Ｓ１３１）。ｖｃｉ（Ｃ）は、セ
ルＣのヘッダ部のＶＰＩ／ＶＣＩ値を返す関数である。

【０１２０】次に、現在出力中のＶＣのセルキューが空
になってからＭＡＸＷＡＩＴ時間経過していれば、すな
わち、ｅｒｒｏｒ［ｉ］＝１なら（Ｓ１３２ Ｙｅ
ｓ）、セルＣはセルキューｑ［ｉ］には入れられず、さ
らにセルＣがＡＡＬ５パケットの最終セル、すなわちｅ
ｏｆ（Ｃ）＝１なら（Ｓ１３３ Ｙｅｓ）、ｅｒｒｏｒ
［ｉ］：＝０としｃ［ｓｅｒｖ］をｗ［ｓｅｒｖ］にリ
セットする（Ｓ１３４）。

【０１２１】一方、ｅｒｒｏｒ［ｉ］＝０であれば（Ｓ
１３２ Ｎｏ）、以下の処理を行なう。まず、セルＣを
セルキューｑ［ｉ］に入れるためにｅｎｑｕｅｕｅ（ｑ
［ｉ］、 Ｃ）を実行し、Ｔを１だけインクリメントし
た後、到着したセルをスケジューリングするために、ｓ
ｅｎｄ＿ｉｎ＿ＣＴ（Ａ，ｉ）を実行する（Ｓ１３
５）。ここで、ｓｅｎｄ＿ｉｎ＿ＣＴ（Ａ，ｉ）は、カ
ットスルーの場合のセル選択アルゴリズムＡに依存し
た、ＶＣキューｉに関する入力処理である。

【０１２２】図１７に、所定時間がＷＡＩＴＭＡＸであ
る場合の、セル出力処理を示す。セル出力処理では、以
下の手順で出力セルが処理される。まず、ｓｅｒｖ＜０
なら（Ｓ１４１ Ｙｅｓ）、次の出力セルキューを選択
するためにｓｅｒｖ：＝ｓｃｈｅｄ＿ｃｈｏｏｓｅ
（Ａ）を実行する（Ｓ１４２）。ここで、ｓｃｈｅｄ＿
ｃｈｏｏｓｅ（Ａ）は、セル選択アルゴリズムＡに依存
して出力するセルキューを返す関数である。

【０１２３】次に、ｓｅｒｖ＜０なら（Ｓ１４３ Ｎ
ｏ）セル出力処理は終了する。ｓｅｒｖ＞＝０なら（Ｓ
１４３ Ｙｅｓ）、まず、セルキューｑ［ｓｅｒｖ］に
セルがあるかどうか、すなわち、ｌｅｎ（ｑ［ｓｅｒ
ｖ］）＞０かどうかをチェックする。

【０１２４】このとき、ｌｅｎ（ｑ［ｓｅｒｖ］）＞０
（Ｓ１４４ Ｙｅｓ）であれば、以下の処理を行なう。
まず、ｗａｉｔ：＝０とし、セルキューｑ［ｓｅｒｖ］
からセルを取り出すために、Ｃ：＝ｄｅｑｕｅｕｅ（ｑ
［ｓｅｒｖ］）を実行する。ｄｅｑｕｅｕｅ（ｘ）は、
キューｘの先頭のエントリを取り出す関数である。次
に、セルＣが最終セルかどうかをチェックするためにＥ
ＯＦ：＝ｅｏｆ（Ｃ）を実行し、ｔｒａｎｓｍｉｔ
（Ｃ）を実行してセルＣを出力し、Ｔを１だけデクリメ
ントした後、パケットキューｓｅｒｖの次のパケットを
スケジューリングするためにｓｃｈｅｄ＿ｏｕｔ＿ＣＴ
（Ａ，ｓｅｒｖ）を実行する（以上Ｓ１４５）。ここ
で、ｓｃｈｅｄ＿ｏｕｔ＿ＣＴ（Ａ、ｉ）は、カットス
ルーの場合のセル選択アルゴリズムＡに依存した、ＶＣ
キューｉに関するセル選択アルゴリズム依存出力処理で
ある。

【０１２５】次に、出力したセルがＡＡＬ５パケットの
最終セルであれば、すなわち、ＥＯＦ＝１であれば（Ｓ
１４６ Ｙｅｓ）、このセルキューの選択をとりやめる
ためにｓｅｒｖ：＝−１とする（Ｓ１４９）。一方、Ｅ
ＯＦ＝０であれば（Ｓ１４６Ｎｏ）、セルキューｑ［ｓ
ｅｒｖ］が空、すなわち、ｌｅｎ（ｑ［ｓｅｒｖ］）＝
０かどうかをチェックする。ｌｅｎ（ｑ［ｓｅｒｖ］）
＝０であれば（Ｓ１４７ Ｙｅｓ）、ＡＡＬ５パケット
の最終セルが未到着のままキューが空になったことを意
味する。このとき、ｗａｉｔ：＝ＭＡＸＷＡＩＴとする
（Ｓ１４８）。

【０１２６】一方、ｌｅｎ（ｑ［ｓｅｒｖ］）＝０であ
ったならば（Ｓ１４４ Ｎｏ）、ｗａｉｔタイマーをデ
クリメントするために、ｗａｉｔ：＝ｗａｉｔ−１とす
る（Ｓ１５０）。ｗａｉｔ＝０であれば（Ｓ１５１ Ｙ
ｅｓ）、ダミー最終セルを送出し、ｅｒｒｏｒ［ｉ］：
＝１とする（Ｓ１５２）。

【０１２７】図１８には、所定時間を系内セル数の和が
ＴＭＡＸを越えるまでとする場合の、初期化処理を示
す。初期化処理は、システム起動時に１度実行される。
初期化処理では、まず、各ＶＣキューｉのセルキューに
対し、ｉｎｉｔ＿ｑｕｅｕｅ（ｑ［ｉ］）が実行され
る。ここで、ｉｎｉｔ＿ｑｕｅｕｅ（ｘ）は、キューｘ
を初期化する処理を表す。次に、ｓｅｒｖ：＝−１、各
ＶＣについてｅｒｒｏｒ［ｉ］：＝０、とした後、セル
選択アルゴリズムに依存した処理ｓｃｈｅｄ＿ｉｎｉｔ
＿ＣＴ（Ａ）を実行する。ここで、ｓｃｈｅｄ＿ｉｎｉ
ｔ＿ＣＴ（Ａ）は、セル選択アルゴリズムＡに依存した
カットスルー用の初期化処理である（以上Ｓ１６１）。

【０１２８】所定時間を系内セル数の和がＴＭＡＸを越
えるまでとする場合の、セル入力処理は、図１６と同じ
である。図１９に、所定時間を系内セル数の和がＴＭＡ
Ｘを越えるまでとする場合の、セル出力処理を示す。セ
ル出力処理では、以下の手順で出力セルが処理される。
まず、ｓｅｒｖ＜０なら（Ｓ１７１ Ｙｅｓ）、次の出
力セルキューを選択するためにｓｅｒｖ：＝ｓｃｈｅｄ
＿ｃｈｏｏｓｅ（Ａ）を実行する（Ｓ１７２）。ここ
で、ｓｃｈｅｄ＿ｃｈｏｏｓｅ（Ａ）は、セル選択アル
ゴリズムＡに依存して出力するセルキューを返す関数で
ある。

【０１２９】次に、ｓｅｒｖ＜０なら（Ｓ１７３ Ｎ
ｏ）セル出力処理は終了する。ｓｅｒｖ＞＝０なら（Ｓ
１７３ Ｙｅｓ）、まず、セルキューｑ［ｓｅｒｖ］に
セルがあるかどうか、すなわち、ｌｅｎ（ｑ［ｓｅｒ
ｖ］）＞０かどうかをチェックする。

【０１３０】このとき、ｌｅｎ（ｑ［ｓｅｒｖ］）＞０
（Ｓ１７４ Ｙｅｓ）であれば、以下の処理を行なう。
まず、ｗａｉｔ：＝０とし、セルキューｑ［ｓｅｒｖ］
からセルを取り出すために、Ｃ：＝ｄｅｑｕｅｕｅ（ｑ
［ｓｅｒｖ］）を実行する。ｄｅｑｕｅｕｅ（ｘ）は、
キューｘの先頭のエントリを取り出す関数である。次
に、セルＣが最終セルかどうかをチェックするためにＥ
ＯＦ：＝ｅｏｆ（Ｃ）を実行し、ｔｒａｎｓｍｉｔ
（Ｃ）を実行してセルＣを出力し、Ｔを１だけデクリメ
ントした後、パケットキューｓｅｒｖの次のパケットを
スケジューリングするためにｓｅｎｄ＿ｏｕｔ＿ＣＴ
（Ａ，ｓｅｒｖ）を実行する（以上Ｓ１７５）。ここ
で、ｓｅｎｄ＿ｏｕｔ＿ＣＴ（Ａ，ｉ）は、カットスル
ーの場合のセル選択アルゴリズムＡに依存した、ＶＣキ
ューｉに関するセル選択アルゴリズム依存出力処理であ
る。

【０１３１】次に、出力したセルがＡＡＬ５パケットの
最終セルであれば、すなわち、ＥＯＦ＝１であれば（Ｓ
１７６ Ｙｅｓ）、このセルキューの選択をとりやめる
ためにｓｅｒｖ：＝−１とする（Ｓ１７７）。

【０１３２】一方、ｌｅｎ（ｑ［ｓｅｒｖ］）＝０であ
ったならば（Ｓ１７４ Ｎｏ）、もしパケットキュー内
の系内セル数の和がしきい値を越えていれば、すなわ
ち、Ｔ＞ＴＭＡＸであれば（Ｓ１７８ Ｙｅｓ）、ダミ
ー最終セルを送出し、ｅｒｒｏｒ［ｉ］：＝１とする
（Ｓ１７９）。

【０１３３】次に、図１５〜１７もしくは図１８〜１９
に示したようなカットスルー・スケジューリングにおい
て、セル選択アルゴリズムとしてＷＦＱアルゴリズムを
採用した場合の、セル選択アルゴリズム依存部分の説明
を、図２０を用いて行なう。

【０１３４】このセル選択アルゴリズムにおいては、２
個のスケジューリングキューＱ、Ｑ’を使用する。Ｑは
現在のラウンドで出力待ちのＶＣＩを入れるためのキュ
ー、Ｑ’は次のラウンドで出力待ちのＶＣＩを入れるた
めのキューである。ここで、ラウンドとは、各セルキュ
ーｉから最大ｗ［ｉ］個セルを送出できる期間のことで
ある。ｗ［ｉ］は、ＶＣｉに対して割当てられるサービ
スに関する重みであり、システムの最大パケット長以上
の値をとる。

【０１３５】また、各ＶＣキューｉは、現在のラウンド
で出力可能なセル数を記憶するカウンタｃ［ｉ］、およ
び、最後に出力されたＶＣキューｉのセルが所属するビ
ジー期間を記憶するカウンタｂ［ｉ］を持つ。さらに、
スケジューリング手段全体で、最後に出力されたセルが
所属するビジー期間を記憶するカウンタＢ、および現在
バッファリングされているセル数をカウントするカウン
タＴを持つ。

【０１３６】図２０では、ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ
（ＷＦＱ）について述べる。なお、ｓｃｈｅｄ＿ｉｎｉ
ｔ＿ＣＴ（ＷＦＱ）、ｓｃｈｅｄ＿ｉｎ＿ＣＴ（ＷＦ
Ｑ、ｉ）の動作は図１２と同じであり、ｓｃｈｅｄ＿ｃ
ｈｏｏｓｅ（ＷＦＱ）の動作は図５（ｂ）と同じであ
る。

【０１３７】ｓｃｈｅｄ＿ｏｕｔ＿ＣＴ（ＷＦＱ，ｓｅ
ｒｖ）では、まず、カウンタ値ｃ［ｓｅｒｖ］を１だけ
デクリメントする（Ｓ１８１）。次に、Ｔ＝０であれば
（Ｓ１８２ Ｙｅｓ）、ビジー期間カウンタＢの値を１
だけインクリメントする（Ｓ１８３）。

【０１３８】次に、パケットキューｑ［ｓｅｒｖ］が空
でなく、かつｃ［ｓｅｒｖ］＞０であれば（Ｓ１８５
Ｙｅｓ）、このラウンド内にさらに選択可能にするた
め、スケジューリングキューＱにｓｅｒｖを入れる（Ｓ
１８６）。そうでない場合（Ｓ１８５ Ｎｏ）、以下の
ように動作する。もしパケットキューｑ［ｓｅｒｖ］が
空でなければ（Ｓ１８７ Ｙｅｓ）、次のラウンドで選
択可能にするため、スケジューリングキューＱ’にｓｅ
ｒｖを入れる（Ｓ１８８）。そして、ｃ［ｓｅｒｖ］の
値を、ｃ［ｓｅｒｖ］をｗ［ｓｅｒｖ］だけインクリメ
ントした値とｗ［ｓｅｒｖ］との最小値に設定する（Ｓ
１８９）。

【０１３９】次には、図１５〜１７もしくは図１８〜１
９に示したようなカットスルー・スケジューリングにお
いて、セル選択アルゴリズムとしてＦＩＦＯを採用した
場合の、セル選択アルゴリズム依存部分の説明を、図２
１、２２を用いて行なう。

【０１４０】このセル選択アルゴリズムにおいては、１
個のスケジューリングキューＱを使用する。Ｑは出力待
ちのＶＣＩを入れるためのキューである。また、各ＶＣ
ごとに、最後に出力されたＶＣキューｉのセルが所属す
るビジー期間を記憶するカウンタｂ［ｉ］を持つ。さら
に、スケジューリング手段全体で、最後に出力されたセ
ルが所属するビジー期間を記憶するカウンタＢ、および
現在バッファリングされているセル数をカウントするカ
ウンタＴを持つ。

【０１４１】図２１では、ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ
（ＦＩＦＯ）、ｓｃｈｅｄ＿ｃｈｏｏｓｅ＿ＣＴ（ＦＩ
ＦＯ）の説明を行なう。ｓｃｈｅｄ＿ｉｎｉｔ＿ＣＴ
（ＦＩＦＯ）では、スケジューリングキューＱを初期化
するためにｉｎｉｔ＿ｑｕｅｕｅ（Ｑ）を実行する。次
に、各ＶＣキューｉに対してｂ［ｉ］：＝０を実行す
る。さらにＢ：＝０、Ｔ：＝０とする（以上Ｓ１９
１）。

【０１４２】ｓｃｈｅｄ＿ｃｈｏｏｓｅ（ＦＩＦＯ）で
は、まず、選択ＶＣＩをクリアし（Ｓ１９２）、スケジ
ューリングキューＱが空でなければ（Ｓ１９３ Ｙｅ
ｓ）、スケジューリングキューＱの先頭のエントリを取
り出すためにｉ：＝ｄｅｑｕｅｕｅ（Ｑ）を実行し（Ｓ
１９４）、取り出したｉを選択した出力ＶＣＩ値として
ｒｅｔｕｒｎ（ｉ）で返す（Ｓ１９５）。

【０１４３】図２２では、ｓｃｈｅｄ＿ｉｎ＿ＣＴ（Ｆ
ＩＦＯ，ｉ）、ｓｃｈｅｄ＿ｏｕｔ＿ＣＴ（ＦＩＦＯ、
ｓｅｒｖ）の説明を行なう。ｓｃｈｅｄ＿ｉｎ＿ＣＴ
（ＦＩＦＯ，ｉ）では、まず、パケットキューｑ［ｉ］
が空であれば（Ｓ２０１ Ｎｏ）、スケジューリングキ
ューＱにｉが入れられる（Ｓ２０４）。そうでなければ
（Ｓ２０１ Ｙｅｓ）、ｑ［ｉ］の最後のセルを参照す
るためにＣ’：＝ｔａｉｌ（ｑ［ｉ］）とする（Ｓ２０
２）。ここで、ｔａｉｌ（ｘ）は、キューｘの最後のエ
ントリを参照するための関数である。Ｃ’が最終セルで
あれば、すなわちｅｏｆ（Ｃ’）＝１であれば（Ｓ２０
３ Ｙｅｓ）、到着セルはＡＡＬ５パケットの先頭セル
であるため、スケジューリングキューＱにｉが入れられ
る（Ｓ２０４）。

【０１４４】ｓｃｈｅｄ＿ｏｕｔ＿ＣＴ（ＦＩＦＯ，ｓ
ｅｒｖ）では、Ｔ＝０なら（Ｓ２０５ Ｙｅｓ）、ビジ
ー期間カウンタＢの値を１だけインクリメントする（Ｓ
２０６）。

【０１４５】これまでは、カットスルー、かつ、ノンイ
ンターリーブなスケジューリングを行なう場合に、カウ
ンタ値を重みの値にリセットするために必要なあるパケ
ットキューから最後にセルを出力後に全パケットキュー
が空になったかどうかのチェックを、そのパケットキュ
ーにセルが到着したときに行なう例を示したが、全パケ
ットキューが空になった時点で全パケットキューのカウ
ンタ値をいっせいに重みの値にリセットしてもよい。

【０１４６】なお、これまで使用されたＶＣごとのキュ
ー（ｑ［ｉ］、ｆ［ｉ］）、カウンタ（ｃ［ｉ］、ｌ
［ｉ］）、変数（ｅｒｒｏｒ［ｉ］、ｗ［ｉ］）は、シ
ステム起動時だけでなく、各ＶＣの設定時にも同様に初
期化される。

【０１４７】以上に述べたいずれの実施形態において
も、ノンインターリーブにスケジューリングがなされた
ＶＣを１本のＶＣにまとめて出力してもよい。また、本
発明に係るパケット通信装置は、ノンインターリーブが
必要であるＶＣと必要でないＶＣが混在する場合でも使
用可能である。この場合、ノンインターリーブが必要な
ＶＣと必要でないＶＣとの間では従来のスケジューリン
グアルゴリズムを用いてインターリーブに出力する。

【０１４８】最後に、本発明の第４の実施形態として、
従来のＡＴＭ交換機の入力／出力ポートに本発明のパケ
ット通信装置を接続させる例を図２３に示す。本例のパ
ケット通信装置は２入力２出力であり、そのうち２本の
入力がＡＴＭ交換機の２本の出力に、１本の出力がＡＴ
Ｍ交換機の１本の入力に、１本の出力が外部出力に接続
されている。外部入力からＡＴＭ交換機に入力されたセ
ルはノンインターリーブな出力が必要であれば、ＡＴＭ
交換機から本発明のパケット通信装置へ入力され、ノン
インターリーブに出力される。ノンインターリーブに出
力すべき入力ＶＣ群は、出力時には同一のＶＣとして出
力され、また、さらに交換処理が必要であればＡＴＭ交
換機に再入力される。また、本例のパケット通信装置の
出力ポート速度が入力ポートの速度よりも遅い場合に
は、本例のパケット通信装置は１入力でもよい。

【０１４９】

【発明の効果】以上詳述したように、本発明によれば、
上位レイヤのパケット長を考慮して下位レイヤパケット
のスケジューリングを行うことが可能になり、サービス
の公平性に優れたノンインターリーブなパケットの出力
が可能になる。

【０１５０】また、上位レイヤパケットのパケット長を
測定し、さらに測定結果をキューイングすることによ
り、上位レイヤのパケット長の情報が上位レイヤパケッ
トのヘッダ部分に書かれていなくても、また、パケット
長が均一でないパケットをスケジューリングする場合に
おいても、サービスの公平性を保証できる。

【０１５１】また、カットスルー・スケジューリングを
行なえば、同一の上位レイヤパケットに属する下位レイ
ヤパケットが全部揃わなくてもパケット出力を開始させ
ることができ、パケットのキューイング遅延を減少させ
ることができる。

【図面の簡単な説明】

【図１】 本発明の第１の実施形態に係るパケット通信
装置の構成例を示す図。

【図２】 本発明の第２の実施形態に係るパケット通信
装置の構成例を示す図。

【図３】 第１／第２の実施形態におけるスケジューリ
ング手段（ノンカットスルーの場合）の動作例を示すフ
ローチャート。

【図４】 第１／第２の実施形態におけるスケジューリ
ング手段（ノンカットスルーの場合）の動作例を示すフ
ローチャート。

【図５】 図３及び図４のスケジューリングにおいてセ
ル選択アルゴリズムとしてＷＦＱを用いる場合の詳細動
作例を示すフローチャート。

【図６】 図３及び図４のスケジューリングにおいてセ
ル選択アルゴリズムとしてＷＦＱを用いる場合の詳細動
作例を示すフローチャート。

【図７】 第１／第２の実施形態におけるスケジューリ
ング手段（カットスルーの場合）の一つの動作例を示す
フローチャート。

【図８】 第１／第２の実施形態におけるスケジューリ
ング手段（カットスルーの場合）の一つの動作例を示す
フローチャート。

【図９】 第１／第２の実施形態におけるスケジューリ
ング手段（カットスルーの場合）の一つの動作例を示す
フローチャート。

【図１０】 第１／第２の実施形態におけるスケジュー
リング手段（カットスルーの場合）の別の動作例を示す
フローチャート。

【図１１】 第１／第２の実施形態におけるスケジュー
リング手段（カットスルーの場合）の別の動作例を示す
フローチャート。

【図１２】 図７〜９もしくは図１０〜１１のスケジュ
ーリングにおいてセル選択アルゴリズムとしてＷＦＱを
用いる場合の詳細動作例を示すフローチャート。

【図１３】 図７〜９もしくは図１０〜１１のスケジュ
ーリングにおいてセル選択アルゴリズムとしてＷＦＱを
用いる場合の詳細動作例を示すフローチャート。

【図１４】 本発明の第３の実施形態に係るパケット通
信装置の構成例を示す図。

【図１５】 第３の実施形態におけるスケジューリング
手段（カットスルーの場合）の一つの動作例を示すフロ
ーチャート。

【図１６】 第３の実施形態におけるスケジューリング
手段（カットスルーの場合）の一つの動作例を示すフロ
ーチャート。

【図１７】 第３の実施形態におけるスケジューリング
手段（カットスルーの場合）の一つの動作例を示すフロ
ーチャート。

【図１８】 第３の実施形態におけるスケジューリング
手段（カットスルーの場合）の別の動作例を示すフロー
チャート。

【図１９】 第３の実施形態におけるスケジューリング
手段（カットスルーの場合）の別の動作例を示すフロー
チャート。

【図２０】 図１５〜１７もしくは図１８〜１９のスケ
ジューリングにおいてセル選択アルゴリズムとしてＷＦ
Ｑを用いる場合の詳細動作例を示すフローチャート。

【図２１】 図１５〜１７もしくは図１８〜１９のスケ
ジューリングにおいてセル選択アルゴリズムとしてＦＩ
ＦＯを用いる場合の詳細動作例を示すフローチャート。

【図２２】 図１５〜１７もしくは図１８〜１９のスケ
ジューリングにおいてセル選択アルゴリズムとしてＦＩ
ＦＯを用いる場合の詳細動作例を示すフローチャート。

【図２３】 ＡＴＭ交換機に本発明を適用する場合の構
成例を示す図。

【符号の説明】

１１、１２、１３…セルキュー １２、２２、２３…パケット長カウンタ ３１、３２、３３…パケット長キュー

Claims (19)

【特許請求の範囲】
1. 【請求項１】上位レイヤパケットを分割して成る固定長
   の下位レイヤパケットを出力するパケット通信装置にお
   いて、 出力待ちの下位レイヤパケットを蓄積するための複数の
   パケットキューと、 各パケットキュー対応にパケットキューに蓄積されてい
   る下位レイヤパケットが所属する上位レイヤパケットの
   パケット長の情報を記憶するためのパケット長記憶手段
   と、 このパケット長記憶手段に記憶される上位レイヤパケッ
   ト長の情報を用いて、下位レイヤパケットの出力を許可
   するパケットキューを選択するパケットスケジューリン
   グ手段とを具備することを特徴とするパケット通信装
   置。
2. 【請求項２】前記パケットスケジューリング手段は、選
   択したパケットキューに蓄積された下位レイヤパケット
   が同一の上位レイヤパケットに所属するものである限り
   この下位レイヤパケットを出力し終えるべく該パケット
   キューを選択しつづけることを特徴とする請求項１記載
   のパケット通信装置。
3. 【請求項３】パケット長の情報がそのヘッダ部に記入さ
   れていない可変長パケットを出力するパケット通信装置
   において、 出力待ちのパケットを蓄積するための複数のパケットキ
   ューと、 このパケットキューに蓄積されているパケットのパケッ
   ト長の情報もしくはこの情報が記憶されている前記パケ
   ットキュー内の位置を検出するパケット長検出手段と、 各パケットキュー対応にこのパケット長検出手段により
   検出されたパケット長の情報もしくはパケットキュー内
   位置を記憶するためのパケット長記憶手段と、 このパケット長記憶手段に記憶されたパケット長の情報
   もしくはパケットキュー内位置に基づいて得られるパケ
   ット長の情報を用いて、パケットの出力を許可するパケ
   ットキューを選択するパケットスケジューリング手段と
   を具備することを特徴とするパケット通信装置。
4. 【請求項４】上位レイヤパケットを分割して成り、該上
   位レイヤパケットの最終下位レイヤパケットか否かを識
   別するための最終パケット識別情報を含む固定長の下位
   レイヤパケットを出力するパケット通信装置において、 上位レイヤパケットのパケット長をある最終下位レイヤ
   パケットを受信してから次の最終下位レイヤパケットを
   受信するまでに受信した固定長パケット数をカウントす
   ることにより測定する上位レイヤパケット長測定手段
   と、 この上位レイヤパケット長測定手段により測定された上
   位レイヤパケット長を用いて下位レイヤパケットの出力
   を制御する制御手段とを具備することを特徴とするパケ
   ット通信装置。
5. 【請求項５】上位レイヤパケットを分割して成る固定長
   の下位レイヤパケットを出力するパケット通信装置にお
   いて、 出力待ちの下位レイヤパケットを蓄積するための複数の
   パケットキューと、 あるパケットキューに同一の上位レイヤパケットに所属
   する下位レイヤパケットが全て蓄積されるのを待たずに
   該下位レイヤパケットの出力が許可されるように該パケ
   ットキューを選択可能とし、選択されたパケットキュー
   に蓄積された下位レイヤパケットが同一の上位レイヤパ
   ケットに所属するものである限りこの下位レイヤパケッ
   トを出力し終えるべく該パケットキューを選択しつづけ
   るパケットスケジューリング手段とを具備することを特
   徴とするパケット通信装置。
6. 【請求項６】前記下位レイヤパケットは、上位レイヤパ
   ケットの最終パケットか否かを識別するための最終パケ
   ット識別情報を含むものであり、 前記パケットスケジューリング手段は、現在選択中のパ
   ケットキューが所定時間空である場合には、最終パケッ
   トであることを示す最終パケット識別情報を記入した下
   位レイヤパケットを新たに生成して出力することを特徴
   とする請求項５記載のパケット通信装置。
7. 【請求項７】前記所定時間は、選択中のパケットキュー
   が空になってから全パケットキューのキュー長の和が一
   定値を越えない間とすることを特徴とする請求項６記載
   のパケット通信装置。
8. 【請求項８】各パケットキュー対応にパケットキューに
   蓄積されている下位レイヤパケットが所属する上位レイ
   ヤパケットのパケット長の情報を記憶するためのパケッ
   ト長記憶手段を更に具備し、 前記パケットスケジューリング手段は、このパケット長
   記憶手段に記憶される上位レイヤパケット長の情報を用
   いて、下位レイヤパケットの出力を許可するパケットキ
   ューの選択を行うものであることを特徴とする請求項５
   記載のパケット通信装置。
9. 【請求項９】前記パケットスケジューリング手段は、各
   パケットキューに割り当てられた出力許可数が残ってい
   るパケットキューを下位レイヤパケットの出力を許可す
   るパケットキューとして選択し、同一の上位レイヤパケ
   ットに所属する下位レイヤパケットを出力し終えるまで
   は該パケットキューの残っている出力許可数を超えても
   該パケットキューを選択しつづけることを特徴とする請
   求項２または５記載のパケット通信装置。
10. 【請求項１０】前記パケットスケジューリング手段は、
    同一の上位レイヤパケットに所属する下位レイヤパケッ
    トが全てパケットキューに蓄積されるのを待たずに該下
    位レイヤパケットの出力を許可するように該パケットキ
    ューを選択した場合に、残っている出力許可数を超えて
    も選択しつづける動作を行うものであり、同一の上位レ
    イヤパケットに所属する下位レイヤパケットが全てパケ
    ットキューに蓄積されているならば、該パケットキュー
    を下位レイヤパケットの出力を許可するパケットキュー
    として選択するのは該同一の上位レイヤパケットに所属
    する下位レイヤパケットの数が残っている出力許可数以
    下の場合とすることを特徴とする請求項９記載のパケッ
    ト通信装置。
11. 【請求項１１】前記パケットスケジューリング手段は、
    各パケットキューに割り当てられた出力許可数に基づい
    た出力の終了後、再度各パケットキューに出力許可数を
    割り当てる際に、残っていた出力許可数を超えて下位レ
    イヤパケットを出力したパケットキューについては超え
    た分に応じて差し引いた数を割り当てるものであること
    を特徴とする請求項９記載のパケット通信装置。
12. 【請求項１２】前記パケットスケジューリング手段は、
    各パケットキューに割り当てられた出力許可数に基づい
    た出力の終了後、再度各パケットキューに出力許可数を
    割り当てる際に、残っていた出力許可数を超えて下位レ
    イヤパケットを出力したパケットキューが空であり、且
    つ、該パケットキューの出力後に全パケットキューが空
    になった時が存在する場合には、前記差し引きを行わな
    い数を該パケットキューに割り当てるものであることを
    特徴とする請求項１１記載のパケット通信装置。
13. 【請求項１３】各パケットキュー対応に出力可能な下位
    レイヤパケットの量を示すカウンタ値を保持するカウン
    タ手段を更に具備し、 前記パケットスケジューリング手段は、（ａ）このカウ
    ンタ手段に保持されたカウンタ値が正で且つ空でないパ
    ケットキューを下位レイヤパケットの出力を許可するパ
    ケットキューとして選択し、同一の上位レイヤパケット
    に所属する下位レイヤパケットを出力し終えるまで該パ
    ケットキューを選択しつづけ、（ｂ）対応するカウンタ
    値を下位レイヤパケットを出力した分に応じてデクリメ
    ントし、（ｃ）選択候補ではなくなったパケットキュー
    のカウンタ値を、該カウンタ値を所定の値だけインクリ
    メントした値及び該所定の値のうち小さい方の値に設定
    し、全パケットキューが選択候補でなくなるまではカウ
    ンタ値を増加させたパケットキューを選択候補とはしな
    いようにし、（ｄ）出力後に全パケットキューが空にな
    ったならば、新たな下位レイヤパケットが各パケットキ
    ューに到着した直後までに、全カウンタ値をそれぞれの
    パケットキューに対応する所定の値に設定した状態にな
    っているように、カウンタ値を制御することを特徴とす
    る請求項２、５もしくは８記載のパケット通信装置。
14. 【請求項１４】全パケットキューが空になる毎に異なる
    値を記憶するビジー期間記憶手段と、 パケットキュー対応に最後に下位レイヤパケットを出力
    した時の前記ビジー期間記憶手段の値を保持する出力時
    ビジー期間記憶手段とを更に具備し、 前記パケットスケジューリング手段は、あるパケットキ
    ューに新たな下位レイヤパケットが入力された時に該パ
    ケットキューに対応する出力時ビジー期間記憶手段の値
    が前記ビジー期間記憶手段の値と異なるならば、この出
    力時ビジー期間記憶手段の値を前記ビジー期間記憶手段
    の値に設定するとともに対応するカウンタ値を所定の値
    に設定することにより前記（ｄ）の動作を行うを特徴と
    する請求項１３記載のパケット通信装置。
15. 【請求項１５】下位レイヤパケットを複数の仮想コネク
    ションから受信し、この受信した下位レイヤパケットを
    受信に用いられた仮想コネクションに対応するパケット
    キューに入力する受信手段と、 前記スケジューリング手段により出力の許可された下位
    レイヤパケットを一つの仮想コネクションに対して送信
    する送信手段とを更に具備したことを特徴とする請求項
    ２または５記載のパケット通信装置。
16. 【請求項１６】上位レイヤパケットを分割して成る固定
    長の下位レイヤパケットを出力するパケット通信方法に
    おいて、 出力待ちの下位レイヤパケットを少なくとも１つのパケ
    ットキューに蓄積し、 各パケットキュー対応にパケットキューに蓄積されてい
    る下位レイヤパケットが所属する上位レイヤパケットの
    パケット長の情報を記憶し、 この記憶された上位レイヤパケット長の情報を用いて、
    下位レイヤパケットの出力を許可するパケットキューを
    選択することを特徴とするパケット通信方法。
17. 【請求項１７】パケット長の情報がそのヘッダ部に記入
    されていない可変長パケットを出力するパケット通信方
    法において、 出力待ちのパケットを少なくとも１つのパケットキュー
    に蓄積し、 このパケットキューに蓄積されているパケットのパケッ
    ト長の情報もしくはこの情報が記憶されている前記パケ
    ットキュー内の位置を検出し、 各パケットキュー対応にこの検出されたパケット長の情
    報もしくはパケットキュー内位置を記憶し、 この記憶されたパケット長の情報もしくはパケットキュ
    ー内位置に基づいて得られるパケット長の情報を用い
    て、パケットの出力を許可するパケットキューを選択す
    ることを具備することを特徴とするパケット通信方法。
18. 【請求項１８】上位レイヤパケットを分割して成り、該
    上位レイヤパケットの最終下位レイヤパケットか否かを
    識別するための最終パケット識別情報を含む固定長の下
    位レイヤパケットを出力するパケット通信方法におい
    て、 上位レイヤパケットのパケット長をある最終下位レイヤ
    パケットを受信してから次の最終下位レイヤパケットを
    受信するまでに受信した固定長パケット数をカウントす
    ることにより測定し、 この測定された上位レイヤパケット長を用いて下位レイ
    ヤパケットの出力を制御することを特徴とする有するパ
    ケット通信方法。
19. 【請求項１９】上位レイヤパケットを分割して成る固定
    長の下位レイヤパケットを出力するパケット通信方法に
    おいて、 出力待ちの下位レイヤパケットを少なくとも１つのパケ
    ットキューに蓄積し、 あるパケットキューに同一の上位レイヤパケットに所属
    する下位レイヤパケットが全て蓄積されるのを待たずに
    該下位レイヤパケットの出力が許可されるように該パケ
    ットキューを選択可能とするとともに、選択されたパケ
    ットキューに蓄積された下位レイヤパケットが同一の上
    位レイヤパケットに所属するものである限りこの下位レ
    イヤパケットを出力し終えるべく該パケットキューを選
    択しつづけることを特徴とするパケット通信方法。