JPH0779252A - パケット出力制御方式 - Google Patents

Abstract

(57)【要約】 【目的】 パケット交換機におけるパケット出力制御方
式に関し、入出力ハイウェイの交差点に設けられたバッ
ファメモリにおけるパケットの廃棄率を低下させること
を目的とする。 【構成】 複数の入力ハイウェイ１に入力されるパケッ
トを出力ハイウェイ２との交差点に設けたバッファメモ
リ３に蓄積したのち出力ハイウェイ２に出力させるパケ
ット交換機に、蓄積パケット量が閾値を超えたバッファ
メモリが発生したときに情報を送出する蓄積量監視手段
５を備えるとともに、各バッファメモリに蓄積されたパ
ケットを出力部４を介して出力ハイウェイに出力させる
制御を行う読出制御部10内に、バッファメモリを一定順
序で選択してパケットを出力させる順次読出制御手段11
と、閾値を超えるパケットを蓄積したバッファメモリが
発生したときにそのバッファメモリ３に蓄積されたパケ
ットを優先的に出力させる最大蓄積バッファ優先読出制
御手段12を備えるように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、パケット交換機におけ
るパケット出力制御方式、特に入力ハイウェイと出力ハ
イウェイの交差点にバッファメモリを設けるクロスポイ
ント・バッファ形式のパケット交換機におけるパケット
出力制御方式に関する。

【０００２】複数の入力ハイウェイから複数の出力ハイ
ウェイへとパケットを交換するパケット交換機では、複
数の入力ハイウェイから入力されて同一方路に向かうパ
ケットをその方路に対応する同一の出力ハイウェイに接
続する場合に、複数の入力ハイウェイからのパケットが
衝突するのを防ぐため、緩衝用メモリ（以下、バッファ
メモリと記す）が設けられている。バッファメモリの形
式はバッファメモリの配置位置によって幾つかに分けら
れるが、形式によって総メモリ量や、パケット転送速度
の変換の要否に差がある。また、バッファメモリの読出
制御方法にも各種の方法があるが、特に、特定の入力ハ
イウェイから同一出力ハイウェイに対してパケットが集
中した場合のパケットの廃棄率や、パケットの到着から
出力までに要する時間（以下、出力遅延時間と記す）及
びその変動は読出制御方法によって大きく異なる。

【０００３】このため、パケットの転送速度の変換が不
要で、パケットの廃棄率が低く、出力遅延時間とその変
動が小さいパケット出力制御方式が求められている。

【０００４】

【従来の技術】図12はＡＴＭスイッチの構成説明図、図
13は出力バッファ形式の構成説明図、図14はクロスポイ
ント・バッファ形式の構成説明図、図15〜図17は従来技
術の構成図、図18〜図20は従来技術のバッファメモリ蓄
積状態説明図である。

【０００５】図12はパケット交換機の一種であるＡＴＭ
交換機のスイッチ構成を図示したものである。音声、デ
ータ、動画像など各種の形態の通信サービスを統合化し
た次世代の通信ネットワークとして広帯域ＩＳＤＮの実
用化が進められている。ＡＴＭ（Asynchronous Transfe
r Mode: 非同期転送モード) はその中核をなす技術であ
り、動画像などの連続情報やデータなどのバースト情報
の発生状態や各種の情報の通信速度に依存することな
く、すべての情報を固定長（４８バイト長）のブロック
に分割し、５バイトのヘッダーを付して構成したセルと
呼ばれるパケット（５３バイト）を単位として高速転送
する技術である。

【０００６】ＡＴＭ交換機では情報をパケット（以下、
セルを含めてパケットと記す）単位で交換するため、図
12に示すように複数（Ｎ）本の入力ハイウェイ１から入
力されるパケットをアドレスフィルタ（ＡＦ）32により
転送先を選別し、同一方路に向かうパケットのみをその
方路に該当する１本の出力ハイウェイ２（出力ハイウェ
イ＃ｉで示す）に出力する。その際、Ｎ本の入力ハイウ
ェイ１から同一出力ハイウェイ２に接続されるパケット
の衝突を回避するため、入力されるパケットを一旦バッ
ファメモリ３に蓄積したのち、順次出力ハイウェイに出
力するようにしている。図12の書込制御部30は各入力ハ
イウェイ１に入力されるパケットのバッファメモリ３へ
の書き込みを制御し、読出制御部30はバッファメモリ３
に蓄積されたパケットを出力ハイウェイ２に出力させる
際の読み出しを制御する部分である。図示のように入力
ハイウェイ１と出力ハイウェイ２のパケットの転送速度
は同一（Ｖｂ／ｓ）であるのが普通である。

【０００７】図12のバッファメモリ３の配置方法には幾
つかの形式があるが、図13と図14に代表的なバッファメ
モリ形式の構成を示す。図13は出力バッファメモリ形
（以下、出力バッファ形式と記す）と呼ばれるもので、
同図の(1) に示すように入力ハイウェイ１と出力ハイウ
ェイ２がそれぞれＮ本である場合にバッファメモリ（Ｂ
Ｍ）３は出力ハイウェイ２に対応して配置される。

【０００８】図13の(2) は動作原理を説明するために出
力ハイウェイ２を１本（出力ハイウェイ＃ｉ）のみ取り
出して図示したものである。Ｎ本の入力ハイウェイ１か
ら入力されるパケットは集線部33において時分割多重さ
れ、出力ハイウェイ２に出力されるが、入出力ハイウェ
イのパケットの転送速度をＶｂ／ｓとした場合、この形
式では時分割多重する際に速度をＮ倍のＮＶｂ／ｓにし
てバッファメモリ３に書き込んだのち、速度Ｖｂ／ｓで
読み出して出力ハイウェイ２に出力する必要がある。こ
の形式はバッファメモリ３が出力ハイウェイ２ごとに集
約されるため、総メモリ量は少なくなるが、集線部33の
内部速度やバッファメモリの書き込み速度を高速にする
必要があるため、使用回路素子などが高価なものとな
り、制御も難しくなる。

【０００９】図14はクロスポイント・バッファメモリ形
（以下、クロスポイント・バッファ形式と記す）と呼ば
れるもので、入力ハイウェイと出力ハイウェイの交差点
にバッファメモリを配置する形式である。図14の(1) は
全体構成の中におけるバッファメモリ３の位置を図示
し、同図の(2) は１本の出力ハイウェイ（出力ハイウェ
イ＃ｉ）２のみを取り出して図示しているが、図の(2)
では、循環するトークンを捕捉したバッファメモリ３か
らパケットが読み出されて出力ハイウェイ２に出力され
る動作原理を示している（トークンについては周知の技
術であるため詳細説明は省略する）。

【００１０】クロスポイント・バッファ形式はバッファ
メモリ３が分散されるため、バッファメモリの溢れによ
るパケット廃棄率を出力バッファ形式と同一値に保とう
とするとメモリの総量が大きくなるが、バッファメモリ
３の書き込み及び読み出し速度は入出力ハイウェイと同
一速度のＶｂ／ｓでよいため、制御は容易となる。

【００１１】以上のように、出力バッファ形式とクロス
ポイント・バッファ形式には一長一短があるが、メモリ
の総量は増加しても低廉化が進んでいる低速の汎用メモ
リ素子が使用できるクロスポイント・バッファ形式が採
用される場合が多くなっている。以下、クロスポイント
・バッファ形式を前提として説明する。

【００１２】図15〜図17はクロスポイント・バッファ形
式のパケット交換機におけるバッファメモリ関連部分を
バッファメモリの読出制御方法別に記載したものであ
る。各図はいずれも４本の入力ハイウェイ１から入力さ
れるパケットを１本の出力ハイウェイ２に出力する例を
示しているが、入力ハイウェイ１にはアドレスフィルタ
ー（図12参照) を経たパケット、即ち、同一方路向けの
パケットのみが入力され、出力ハイウェイ２はその方路
に該当するハイウェイを示している。なお、各図とも書
込制御部は図示省略されている。

【００１３】図15〜図17において、４本の入力ハイウェ
イ（＃１〜＃４）１に対応して設けられたＢＭ−Ａ〜Ｂ
Ｍ−Ｄの４つのバッファメモリ３（以下、個々のバッフ
ァメモリを指す場合にはＢＭ−Ａ、ＢＭ−Ｂのように記
す）は先入れ先出し（First-in First-out、以下、ＦＩ
ＦＯと記す）方式のメモリであり、バッファメモリごと
に最初に入力されたパケットを先頭に入力順に蓄積され
る。先頭番地に蓄積されたパケットは読出制御部の制御
によって読み出され、出力部４を介して出力ハイウェイ
２に出力されるが、先頭のパケットが読み出されると後
のパケットが順次先頭の番地に向けて歩進するようにな
っている。

【００１４】パケットは出力部４内を循環するトークン
を捕捉したバッファメモリ３から読み出される。トーク
ンはＢＭ−Ａ、ＢＭ−Ｂ、ＢＭ−Ｃ、ＢＭ−Ｄの順に循
環するものとするが、各バッファメモリ３がトークンを
捕捉できるか否か、言い換えれば読み出されるか読み飛
ばされるかは読出制御部の制御によって決まる。図15〜
図17の読出制御部はそれぞれ読出制御方法が異なってい
るが、以下、各図ごとに説明する。

【００１５】図15はバッファメモリの読出制御方法にス
キップポーリング式（または、バッファ順次読出式）を
用いた従来技術の構成図である。読出制御部40のスキッ
プポーリング制御部41は出力部４のトークンにＢＭ−
Ａ、ＢＭ−Ｂ、ＢＭ−Ｃ、ＢＭ−Ｄの順に読み出させる
が、先頭番地にパケットが蓄積されていないバッファメ
モリ３はスキップ（読み飛ばし）させる。

【００１６】図18は図15の構成におけるバッファメモリ
３の蓄積状態とパケットの入出力状況を説明する図であ
る。同図は後述の図７の(2) に示すパケット入力時期
（Ｓ１〜Ｓ10で示す）に各バッファメモリＢＭ−Ａ〜Ｂ
Ｍ−Ｄにパケットが入力された場合の各バッファメモリ
のパケット蓄積状態を時間の経過に合わせて記載してい
る。図において、Ａ１はバッファメモリＢＭ−Ａに１番
目に入力されたパケット、Ａ２はその次にＢＭ−Ａに入
力されたパケットを示しているが、他のパケットも同様
である。また、各バッファメモリＢＭ−Ａ〜ＢＭ−Ｄの
高さは蓄積されているパケットの数を表し、１番下のパ
ケットが先頭の位置にある。

【００１７】図18の最下段にはトークンの読出周期を示
しているが、説明の便からパケットがバッファメモリ３
に蓄積される時期（以下、入力時期と記す）はトークン
の読出周期に同期し、読み出しは最も早くてもパケット
の入力時期から１周期後であるとする。また、同時に入
力したパケットの読出順序は循環しているトークンが早
く到着した方のバッファメモリ３に記憶されているパケ
ットが先に読み出されるものとする。

【００１８】図15のスキップ・ポーリング制御部41によ
る読出制御では、図18に示すようにパケット到着順序Ｓ
１にＢＭ−Ａに入力されたパケットＡ１はトークンの次
の読出周期で読み出され、パケット到着順序Ｓ２にＢＭ
−ＢとＢＭ−Ｃに同時に入力されたパケットＢ１とパケ
ットＣ１はトークンの位置からパケットＢ１が先に読み
出され、次いでパケットＣ１が読み出される。

【００１９】以下同様に読み出され、図18の出力ＨＷに
示す順序でパケットは出力ハイウェイ２に出力される。
図の例では入力ハイウェイ＃３よりパケットが連続して
入力され、対応するＢＭ−Ｃに蓄積されてゆくが、トー
クンはＢＭ−Ａ、ＢＭ−Ｂ、ＢＭ−Ｃ、ＢＭ−Ｄの順に
循環するため、同一バッファメモリ３から連続してパケ
ットを読み出すことがない。このため、ＢＭ−Ｃに蓄積
されるパケットは入力パケットが少ない他の入力ハイウ
ェイから入力されるパケットより先または同時に入力さ
れても出力が後になることが多い。図の例ではＣ４、Ｃ
５、Ｃ６、Ｃ７の各パケットは他のバッファメモリ３に
蓄積されたパケットより早いか、同時に入力されたにも
関わらず、出力は最後になっている。

【００２０】このことは、パケットが連続して入力され
るバッファメモリ３に出力待ちのパケットが次第に累積
されることを意味している。説明の便のため、各バッフ
ァメモリ３の蓄積容量を３個とすれば、図のパケットＣ
５、Ｃ６、Ｃ７はＢＭ−Ｃに蓄積できずに廃棄される可
能性が高い。

【００２１】以上のように、スキップポーリング式の読
出制御方法は制御は極めて単純であるが、バーストトラ
ヒックのように同一方路に対してパケットが連続して入
力されるような場合、出力遅延時間が大となり、これに
伴ってバッファメモリにパケットが累積されるため、パ
ケット廃棄率も高くなるという欠点がある。

【００２２】次に図16について説明する。図16はスキッ
プポーリング式の欠点を除くために考案された最大蓄積
バッファ優先読出式の読出制御方法を用いた従来技術の
構成図である。最大蓄積バッファ優先読出式は蓄積パケ
ットの数（キューの数）が最大のバッファメモリから読
み出すようにポーリングを行うもので、以下、ＬＮＱ
（Largest Number of cells in the Queue、注）ポーリ
ング式と記す。（注. 電子情報通信学会、信学技法ＳＳ
Ｅ92-88 、宗宮他「ＡＴＭ集線装置におけるバーストト
ラヒック特性の一検討」平成4.11. 26参照）。

【００２３】図16の構成では、蓄積量監視部53が各バッ
ファメモリＢＭ−Ａ〜ＢＭ−Ｄのパケット蓄積量を監視
し、監視結果を読出制御部50のＬＮＱポーリング制御部
51に通知する。ＬＮＱポーリング制御部51は各バッファ
メモリＢＭ−Ａ〜ＢＭ−Ｄのパケット蓄積量を比較し、
蓄積量が最も多いバッファメモリ３の識別情報を出力部
４のトークンに送り、そのバッファメモリ３に蓄積され
たパケットを読み出させる。蓄積量が最大のバッファメ
モリ３が複数、例えば２個存在する場合はトークンの循
環順序に従って２個のバッファメモリ３を交互に読み出
す。

【００２４】図19は図16の構成におけるバッファメモリ
３の蓄積状態とパケットの入出力状況を説明する図であ
る。パケットの入力順序は図18と同一条件であり、図示
の方法も図18と同一である。

【００２５】図16の方法では蓄積量が最大となったバッ
ファメモリ３が発生するとそのバッファメモリ３に蓄積
されているパケットを優先的に読み出させる。図19の例
ではＢＭ−ＣとＢＭ−Ａ（一時的）が最大蓄積量となっ
ている時間が長いが、優先的に読み出された結果、例え
ばＣ４、Ｃ５、Ｃ６などのパケットは図18のスキップポ
ーリング式におけるよりもかなり早く読み出される。ま
た、これに伴ってＢＭ−Ｃに累積されるパケット量が減
少し、蓄積量が多くなっている時間が短くなるため、パ
ケット廃棄率もスキップポーリング式より低くなる。図
19の場合、各バッファメモリ３の蓄積容量を仮に３個と
すれば、パケットＣ６は廃棄されるが、Ｃ６が廃棄され
ればＣ７は蓄積可能となる可能性が高いので、廃棄され
るパケットの数は図18より少なくなる。

【００２６】しかし、ＬＮＱポーリング式は蓄積量が多
いバッファメモリ３を優先的に読み出す反面、蓄積量が
少ないバッファメモリ３の読み出しが後回しとなる。図
19に示すように、蓄積量が少ないＢＭ−Ｂに蓄積された
パケットＢ２は早い時期に入力されたにも関わらず、後
から入力されたパケットＣ３〜Ｃ６及びＡ３よりも出力
時期が後になっている。即ち、ＬＮＱポーリング式は、
同一方路へのトラヒックが少ない入力ハイウェイ１から
入力されるパケットの出力遅延時間が大きくなり、ま
た、他のバッファメモリ３の蓄積状態によって出力遅延
時間が左右されるため、出力遅延時間の変動も大きくな
るという欠点がある。

【００２７】次に図17について説明する。図17はスキッ
プポーリング式やＬＮＱポーリング式のようにトラヒッ
クが多い方路または少ない方路のパケット出力遅延の増
加や出力時間の変動の増加を防ぐ読出制御方法を用いた
従来技術の構成図である。図17の構成では、入力ハイウ
ェイ１に到着順序記憶部62を接続し、全入力ハイウェイ
１に入力されるパケットの到着順序を記憶する。到着順
序記憶部62に記憶される情報は到着したパケットを識別
する情報（以下、パケット情報と記す）で、例えば、ア
ドレス情報などが用いられる。図７の(2) は到着順序記
憶部62内のメモリ（図示省略）にパケット情報が記憶さ
れた状態を図示したものである。

【００２８】到着順序記憶部62は記憶したパケットの識
別情報を到着順にＦＩＦＯ方式で読出制御部60に通知す
るが、図７の(2) の例では最初にパケット到着順序Ｓ１
のパケットＡ１の情報が送出され、次にパケット到着順
序Ｓ２のパケットＢ１とＣ１の情報が送出される。以
下、同様にパケットの到着順序が通知されるが、読出制
御部60のＦＩＦＯポーリング制御部61は到着順序記憶部
62より入力された順に出力部４のトークンに読み出しを
指示する。

【００２９】図20は図17の構成におけるバッファメモリ
３の蓄積状態とパケットの入出力状況を説明する図であ
るが、パケットの入力条件及び図示の方法は図18と同一
である。図20に示すように、入力されたパケットはトー
クンの位置によって多少前後することはあってもほぼ到
着順に出力されている。従って、この方法では特定のパ
ケットだけが極端に長い時間、バッファメモリ３内に蓄
積されることはないが、蓄積量が増加しても優先して出
力することはしないため、バーストトラヒックが入力さ
れた場合のパケット廃棄率は図16のＬＮＱポーリング式
よりも大きくなる。図19と図20のＢＭ−Ｃのパケット蓄
積状態を比較した場合、蓄積されたパケットの最大数は
同数であるが、図20の方が最大数のパケットを蓄積して
いる時間が長いことから両者のパケット廃棄率に差があ
ることは明かである。

【００３０】

【発明が解決しようとする課題】以上のように、従来技
術のパケット出力制御方式においては、スキップポーリ
ング式の読出制御方法は同一方路宛のパケットが連続し
て入力されるバッファメモリに蓄積されたパケットの出
力遅延時間が大きくなり、かつ、パケットの廃棄率も高
くなると言う欠点があった。また、ＬＮＱポーリング式
の読出制御方法は同一方路へのトラヒックが少ない入力
ハイウェイから入力されるパケットの出力遅延時間と出
力遅延時間の変動が大きいという欠点がある。更に、Ｆ
ＩＦＯポーリング式の読出制御方法は入力されたパケッ
トが入力順に出力されるという長所はあるが、パケット
の廃棄率が必ずしも低くないという問題がある。

【００３１】このため、入力されるパケットの出力遅延
時間やその変動が極端に大きくなることがなく、低いパ
ケットの廃棄率が得られるパケット出力制御方式が求め
られている。

【００３２】本発明は、入出力ハイウェイの交差点に設
けられたバッファメモリにおけるパケットの廃棄率を低
下させることを目的とする。

【００３３】

【課題を解決するための手段】図１は本発明の原理説明
図、図２及び図３は本発明の他の原理説明図である。図
中、１は同一方路宛のパケットが入力される複数の入力
ハイウェイ、２は入力されるパケットの宛先方路に対応
する出力ハイウェイ、３は複数の入力ハイウェイ１と出
力ハイウェイ２の交差点に入力ハイウェイ対応に設けら
れた先入れ先出し（ＦＩＦＯ）方式のバッファメモリ、
４はバッファメモリ３に記憶されたパケットを出力ハイ
ウェイ４に出力する出力部、10及び20はバッファメモリ
３に一時蓄積されたパケットを順次読み出し、出力部４
を介して出力ハイウェイ２に出力させる制御を行う読出
制御部である。

【００３４】５は各バッファメモリ３に蓄積されたパケ
ットの量を監視し、予め定めた閾値を超える量のパケッ
トを蓄積したバッファメモリ３が発生したとき、そのバ
ッファメモリ３のパケット蓄積量が閾値を超えたことを
示す情報をパケット蓄積量が閾値以下となるまで送出す
る蓄積量監視手段、６は入力ハイウェイ１より入力され
るパケットの識別情報をそのパケットが蓄積されるバッ
ファメモリ３と到着順が識別できるように記憶したの
ち、その識別情報を到着順に順次送出する到着順序記憶
手段である。

【００３５】11及び12は読出制御部10内に設けられ、11
はバッファメモリ３を一定順序で選択し、選択したバッ
ファメモリ３の先頭に蓄積されているパケットを出力ハ
イウェイ２に出力するよう出力部４を制御するバッファ
順次読出制御手段、12は蓄積量監視手段５よりパケット
蓄積量が閾値を超えたバッファメモリ３が発生したこと
を示す情報が送出されている間、バッファ順次読出制御
手段11による読出制御に優先してパケット蓄積量が閾値
を超えたバッファメモリ３よりパケットを読み出して出
力ハイウェイ２に出力するよう出力部４を制御する最大
蓄積バッファ優先読出制御手段である。

【００３６】21〜23は読出制御部20内に設けられ、21は
到着順序記憶手段６より順次送出されるパケットの識別
情報を受信する都度、そのパケットが蓄積されているバ
ッファメモリ３からパケットを読み出して出力ハイウェ
イ２に出力するよう出力部４を制御する到着順読出制御
手段、22は蓄積量監視手段５よりパケット蓄積量が閾値
を超えたバッファメモリ３が発生したことを示す情報が
送出されている間、到着順読出制御手段21による読出制
御に優先してパケット蓄積量が閾値を超えたバッファメ
モリ３よりパケットを読み出して出力ハイウェイ２に出
力するよう出力部４を制御する最大蓄積バッファ優先読
出制御手段、23は最大蓄積バッファ優先読出制御手段22
が優先的に出力させたバッファメモリ３内の該当パケッ
トの識別情報を最大蓄積バッファ優先読出制御手段22よ
り受信して到着順序記憶手段６に記憶されているパケッ
トの識別情報の中からそのパケットの識別情報を消去さ
せる制御を行う優先読出パケット情報消去手段である。

【００３７】24は優先読出パケット情報消去手段23に代
えて読出制御部20内に設けられるもので、バッファメモ
リ３対応に設けた計数手段を内蔵し、最大蓄積バッファ
優先読出制御手段24の制御によりバッファメモリ３より
パケットが読み出されたときにそのバッファメモリ３に
対応する計数手段が示す数値に１を加算し、到着順読出
制御手段21より減算の指示を受信した場合に指示された
バッファメモリ３に対応する計数手段が示す数値より１
を減ずる優先読出パケット数記憶手段である。

【００３８】25は読出制御部20内に優先読出パケット数
記憶手段24が設けられる場合に到着順読出制御手段21内
に設けられ、到着順読出制御手段21が出力部４に対して
バッファメモリ３に蓄積されたパケットを読み出す制御
を行う際に、優先読出パケット数記憶手段26内の該当バ
ッファメモリ３に対応する計数手段が示す数値を確認
し、その数値が１以上である場合にパケットの読出制御
を省略して優先読出パケット数記憶手段26内の該当バッ
ファメモリ３に対応する計数手段に対してその計数部の
表示する数値より１を減ずるよう指示する読出省略処理
手段である。

【００３９】

【作用】図１において、複数の入力ハイウェイ１より入
力される同一方路宛のパケットは入力ハイウェイ１に対
応して設けられたバッファメモリ３に一時蓄積される。
バッファ順次読出制御手段11はバッファメモリ３を一定
順序で順次選択し、選択したバッファメモリ３の先頭に
蓄積されているパケットを出力ハイウェイ２に出力する
よう出力部４を制御する。この制御により出力部４は各
バッファメモリ３の先頭パケットを出力ハイウェイ２に
出力させる。バッファメモリ３はＦＩＦＯメモリである
ため、先頭のパケットが読み出されると以後に入力され
たパケットが先頭の位置に向かって一つづつ歩進する。
先頭のパケットにパケットが記憶されていないバッファ
メモリ３はパケットが蓄積されていないことを示してい
るため、バッファ順次読出制御手段11はそのバッファメ
モリ３を読み飛ばす（スキップする）。

【００４０】一方、蓄積量監視手段５は各バッファメモ
リ３に蓄積されているパケットの量を監視しているが、
パケットの蓄積量が予め設定した閾値を超えたバッファ
メモリ３が発生すると閾値超過のバッファメモリ３の発
生を知らせる情報を蓄積量が閾値以下になるまで読出制
御部10に送出し続ける。

【００４１】この情報を受信すると、読出制御部10の最
大蓄積バッファ優先読出制御手段12はその情報がなくな
るまでバッファ順次読出制御手段11による読出制御に優
先してパケット蓄積量が閾値を超えたバッファメモリ３
よりパケットを読み出して出力ハイウェイ２に出力する
よう出力部４を制御する。バッファメモリ３に多量のパ
ケットが入力され、そのバッファメモリ３の蓄積容量を
超えると以後のパケットは廃棄されるが、図１において
は上記のように、パケットの蓄積量が閾値を超えた時点
でそのバッファメモリ３から優先してパケットを読み出
すのでパケットが廃棄される可能性は低くなる。

【００４２】次に図２の作用を説明する。図１と同様
に、複数の入力ハイウェイ１より入力される同一方路宛
のパケットは入力ハイウェイ１に対応して設けられたバ
ッファメモリ３に一時蓄積されるが、図２の場合は、到
着順序記憶手段６が入力ハイウェイ１より入力されるパ
ケットの識別情報を到着順とそのパケットが蓄積される
バッファメモリ３が識別できるように記憶したうえ、到
着順情報として順次読出制御部20に出力する。

【００４３】読出制御部20の到着順読出制御手段21はこ
の到着順情報を受信する都度、該当バッファメモリ３か
らパケットを読み出して出力ハイウェイ２に出力するよ
う出力部４を制御する。従って、図２の構成ではパケッ
トは到着順に出力される。

【００４４】一方、蓄積量監視手段５は図１と同様、各
バッファメモリ３に蓄積されているパケットの量を監視
しているが、パケットの蓄積量が閾値を超えるバッファ
メモリ３が発生するとこれを知らせる情報を読出制御部
10に送出する。この情報を受信すると、読出制御部10の
最大蓄積バッファ優先読出制御手段22はその情報がなく
なるまで到着順読出制御手段21による読出指示に優先し
てそのバッファメモリ３よりパケットを読み出して出力
ハイウェイ２に出力するよう出力部４に指示する。この
ため、特定の入力ハイウェイに同一方路宛のパケットが
集中して入力されてもパケットの廃棄率は大きくならな
い。

【００４５】ところで図２における最大蓄積バッファ優
先読出制御手段22による読み出しでは到着順序記憶手段
６に記憶されているパケット到着順序を無視して後から
到着したパケットを先に出力する事態が発生する。その
ため、到着順序記憶手段６に記憶されているパケット識
別情報の中から優先して出力が行われたパケットの識別
情報を削除することが必要になる。

【００４６】そのため、最大蓄積バッファ優先読出制御
手段22は閾値を超えるパケットを蓄積したバッファメモ
リ３よりパケットを優先的に読み出させると、そのパケ
ットの識別情報を優先読出パケット情報消去手段23に通
知する。優先読出パケット情報消去手段23はこの通知を
受けると、到着順序記憶手段６に記憶されているパケッ
トの識別情報の中からそのパケットの識別情報を消去す
る。

【００４７】次に図３の作用について説明する。図３に
おいても図２と同様、通常は読出制御部20の到着順読出
制御手段21が到着順序記憶手段６からの情報に従って該
当バッファメモリ３からパケットを読み出して出力ハイ
ウェイ２に出力させるので、図３でもパケットは到着順
に出力される。また、パケット蓄積量が閾値を超えたバ
ッファメモリ３が発生したときに最大蓄積バッファ優先
読出制御手段22がそのバッファメモリ３から蓄積された
パケットを優先的に読み出させる作用も図２と同じであ
る。

【００４８】図３においても最大蓄積バッファ優先読出
制御手段22による読み出しが行われると到着順序記憶手
段６に記憶されているパケット到着順序を無視して後か
ら到着したパケットを先に出力する事態が発生するが、
図３では到着順序記憶手段６に記憶されている到着順の
パケット識別情報を消去せずにパケットの出力が混乱し
ないように処理する。

【００４９】そのため、図３の優先読出パケット数記憶
手段24にはバッファメモリ３対応に計数手段（図示省
略）が設けられている。この計数手段は初期値として０
を示しているが、最大蓄積バッファ優先読出制御手段22
の制御により閾値超過のバッファメモリ３からパケット
が読み出される都度、読み出しが行われたバッファメモ
リ３に対応する計数手段が示す数値に１を加算する。従
って、計数手段の数値は優先して読み出したパケットの
数を示すこととなる。

【００５０】そのバッファメモリ３のパケット蓄積量が
閾値以下になるとバッファメモリ３の読み出しは再び到
着順読出制御手段21によって行われるようになる。到着
順読出制御手段21は最初のときと同様に到着順序記憶手
段６より出力されるパケット識別情報に従ってパケット
の読み出しを制御する。このとき到着順序記憶手段６よ
り出力されるパケット識別情報の中には最大蓄積バッフ
ァ優先読出制御手段22の制御により優先して出力された
パケットの識別情報も含まれているが、到着順読出制御
手段21が出力部４に読み出しを指示するのに先立って読
出省略処理手段25が優先読出パケット数記憶手段24にア
クセスし、そのパケットが蓄積されているバッファメモ
リ３に対応する計数手段の数値を確認する。

【００５１】その数値が１以上を示している場合はその
バッファメモリ３から優先して読み出したパケットが１
個以上存在することになるので、読出省略処理手段25は
到着順読出制御手段21にそのバッファメモリ３からの読
み出しを省略させる。このため、到着順読出制御手段21
は次のパケットの読み出しに移るが、その際、読出省略
処理手段25は優先読出パケット数記憶手段24の該当バッ
ファメモリ３に対応する計数手段の数値より１を減ず
る。従って、計数手段が示す数値はそれ以降、そのバッ
ファメモリ３から読み出しを省略すべき回数（パケット
の数）を示すことになる。

【００５２】以上を繰り返すことにより該当バッファメ
モリ３に対応する計数手段の数値は順次減少するが、計
数手段の数値が０になった場合は、優先して出力された
パケットがなくなったことを示すため、以後、到着順読
出制御手段21は到着順序記憶手段６より出力されるパケ
ット識別情報に従って、到着順にパケットを読み出す制
御を行う。

【００５３】図３の方法は優先読み出しを行ったバッフ
ァメモリ３から更に読み出しを行ったり、すでに読み出
したパケットを重複してパケットを読み出すことなどが
ないようにする点で図２と同じ作用をもつが、図２の優
先読出パケット情報消去手段23に比して処理が簡単にな
る。

【００５４】

【実施例】図４〜図６は本発明の実施例の構成図で、図
４は図１の原理説明図、図５は図２の原理説明図、図６
は図３の原理説明図にそれぞれ基づく実施例の構成図で
ある。また、図７は本発明の実施例の到着順序記憶部に
おけるパケット情報記憶状態の説明図、図８及び図９は
図４の構成における実施例のバッファメモリ蓄積状態説
明図、図10及び図11は図５及び図６の構成における実施
例のバッファメモリ蓄積状態説明図である。

【００５５】全図を通じ、同一符号は同一対象物を示
し、11はスキップポーリング制御部で図１のバッファ順
次読出制御手段11の実現形態、12はＬＮＱポーリング制
御部で図１の最大蓄積バッファ優先読出制御手段12の実
現形態、21はＦＩＦＯポーリング制御部で図２及び図３
の到着順読出制御手段21の実現形態、22はＬＮＱポーリ
ング制御部で図２及び図３の最大蓄積バッファ優先読出
制御手段の実現形態である。24A 〜24D はＦＩＦＯポー
リング制御部21内に設けられるカウンタ（以下、ＣＮＴ
−Ａ〜ＣＮＴ−Ｄと記す）で、作用の説明において計数
手段として説明したものに該当する。また、25は読出省
略処理部（ＮＲＣ）で、図３の読出省略処理手段25の実
現形態である。

【００５６】図４〜図６の構成図においては入力ハイウ
ェイ１として＃１〜＃４の４本の入力ハイウェイのみを
記載し、バッファメモリ３も４本の入力ハイウェイ１に
対応してＢＭ−Ａ〜ＢＭ−Ｄの４個のみを記載してい
る。以下、バッファメモリ３を個別に説明する場合はＢ
Ｍ−Ａ〜ＢＭ−Ｄを用いる。

【００５７】次に、各図について説明するが、入力ハイ
ウェイ１、バッファメモリ３、出力部４（トークンを含
む）及び出力ハイウェイ２の構成と基本的な動作は従来
技術において説明した内容と同一であるので簡単な説明
にとどめる。また、図４〜図６の構成の基本的な動作は
作用の説明に記載した内容と変わらないので重複を避
け、パケットの入出力と蓄積状況を中心に具体的なモデ
ルにより説明する。

【００５８】先ず、図４の構成について図７、図８及び
図９を併用して説明する。図４の４本の入力ハイウェイ
＃１〜＃４に入力されるパケットはそれぞれ対応するバ
ッファメモリＢＭ−Ａ〜ＢＭ−Ｄに入力順に蓄積され
る。蓄積量監視部５は各バッファメモリＢＭ−Ａ〜ＢＭ
−Ｄに蓄積されているパケットの数が予め設定した閾値
を超えていないか監視しているが、説明の便のため、こ
の閾値を「２」とする。前記したようにバッファメモリ
３はＦＩＦＯメモリであるので、先頭のパケットが出力
されると以後のパケットは順次先頭に向けて歩進する
が、上記の前提では２個のパケットが蓄積されている状
態で３個目のパケットが入力されるとそのバッファメモ
リ３の蓄積量が閾値を超えたとして読出制御部10に通知
がなされる。

【００５９】最初に、すべてのバッファメモリ３が閾値
を超えていない状態の動作について説明するが、パケッ
トの入力順序として図７の(1) を用いる。図７は後述の
到着順序記憶部６の記憶状態を説明する図であるが、入
力順序のモデルとしても使用することとする。図７の
(1) は入力時期Ｓ１の時点でＢＭ−ＡにパケットＡ１、
Ｓ２の時点でＢＭ−ＢにパケットＢ１、以下同様に入力
されることを図示しているが、Ｓ１、Ｓ２等の入力時期
は説明の便から従来技術と同様、出力部４のトークンの
読出周期に同期しているものとする。これらのパケッ
ト、例えばパケットＡ１〜Ａ４はＢＭ−Ａ内においては
先頭番地（図示省略）から順に詰めて記憶され、出力さ
れると消滅する。なお、図７中におけるトークン方向の
矢印はパケットの出力順序に関係するバッファメモリ３
の選択順序を示すものである。図８は図７の(1) の入力
モデルに従ってパケットが入力された場合のバッファメ
モリＢＭ−Ａ〜ＢＭ−Ｄの蓄積状態とパケットの入出力
状況を示し、同図の出力ＨＷには出力ハイウェイ２にパ
ケットが出力される順序が示されている。図４の構成で
は閾値を超えるパケットを蓄積したバッファメモリ３が
ない場合、スキップポーリング制御部11の制御によって
出力が行われるが、図８に示すように、この入力モデル
ではＢＭ−Ａ、ＢＭ−Ｂ及びＢＭ−Ｄの３つのバッファ
メモリはいずれも２個目のパケットが入力される前に１
個目のパケットが出力され、ＢＭ−Ｃも同時に２個のパ
ケットが蓄積されることがあっても閾値（３個）を超え
るパケットが蓄積されることはない。

【００６０】出力部４のトークンはＢＭ−Ａ、ＢＭ−
Ｂ、ＢＭ−Ｃ、ＢＭ−Ｄと循環したのち再びＢＭ−Ａに
戻るため、図８のパケットＣ２のようにパケットＢ２よ
りも先に入力されたにも関わらず後から出力されたり、
パケットＣ４のようにパケットＡ４やパケットＢ３より
も先に入力されたにも関わらず、それらのパケットより
後から出力されるようなケースも生ずるが、この入力モ
デルのようにトラヒックが少ない場合にはスキップポー
リング制御でも入力されてから極端に長い間、出力され
ずにいるパケットが生ずることは少ない。

【００６１】次に閾値を超えるパケットを蓄積したバッ
ファメモリ３が発生した場合について説明するが、この
場合には図７の(2) を入力モデルとして用いる。なお、
この入力モデルは従来技術の説明に使用したものと同一
である。

【００６２】図９は図７の(2) に示す入力時期にパケッ
トが入力された場合のバッファメモリＢＭ−Ａ〜ＢＭ−
Ｄの蓄積状態とパケットの入出力状況を示している。図
９の例ではパケットＡ２が出力ＨＷに出力されたあと、
スキップポーリング制御によりパケットＢ２が出力され
る筈であったが、その読出周期が到来したときにパケッ
トＣ４が３個目のパケットとしてＢＭ−Ｃに蓄積される
ため、図４の蓄積量監視部５より読出制御部10にＢＭ−
Ｃのパケット蓄積量が閾値を超えたことが通知される。
ここでは説明の便のため、この通知を受けると読出制御
部10は直ちにＬＮＱポーリング制御部12による制御に移
行するものとする。

【００６３】ＬＮＱポーリング制御部12による制御では
閾値を超えたバッファメモリ（この場合はＢＭ−Ｃ）か
ら優先的にパケットの読み出しを行うので、先ずＢＭ−
Ｃの先頭に蓄積されているパケットＣ２を読み出す。パ
ケットＣ２が読み出されるとＢＭ−Ｃのパケット蓄積量
は閾値以下の２個になるが、次の読出周期のときに３個
目のパケットＣ５が蓄積されるため、続けてＢＭ−Ｃよ
りのパケット読み出しが行われる。以下、同様にしてパ
ケットＣ５までＢＭ−Ｃのみからパケットの読み出しが
行われる。

【００６４】パケットＣ５が出力されるとＢＭ−Ｃのパ
ケット蓄積量は閾値以下となるので読出制御部10の制御
はスキップポーリング制御部11に戻る。このとき、トー
クンはパケットＣ５の読み出し終了直後であるためＢＭ
−Ｄの読み出しから始め、パケットＤ２が読み出され
る。以下、パケットＡ３、Ｂ２の順で読み出される。

【００６５】ここで図９をスキップポーリング制御のみ
により読み出しを行った従来技術の図18と比較する。図
９と図18は入力モデルが全く同一であるが、各パケット
の出力時期を比較すると、図18ではＢＭ−Ｃに連続して
入力されたパケットＣ４〜Ｃ７が最後に出力されている
のに対し、図９では蓄積量が閾値を超えたときにＢＭ−
Ｃから優先的に読み出されるため、パケットＣ４〜Ｃ７
の全部が最後まで出力されずに残っていると言うような
現象は生じない。

【００６６】このように、図９では同一のバッファメモ
リＢＭ−Ｃにパケットが連続して入力されてもパケット
がそのまま累積されないため、パケットがバッファメモ
リ３から溢れる可能性が減り、パケットの廃棄率が低下
する。これは図９と図18の比較よっても確認できる。即
ち、図18では４個以上（最大５個）のパケットが蓄積さ
れた状態が発生しているのに対して、図９ではＢＭ−Ｃ
に４個以上のパケットが蓄積される状態は発生していな
い。ＢＭ−Ｃの蓄積容量を仮に３個とすれば図18ではパ
ケットＣ５、Ｃ６、Ｃ７が廃棄される可能性が高いが、
図９ではパケットの廃棄が生じない。即ち、図９のパケ
ット廃棄率が図18に比して低いことは明瞭である。

【００６７】次に図９をＬＮＱポーリング制御のみによ
り読み出しを行った従来技術の図19と比較して見る。図
９と図18も入力モデルは全く同一であるが、ここでも図
９の方がパケットの廃棄率が低くなることは明かであ
る。

【００６８】また、図４の構成ではパケットの蓄積量が
閾値を超えるバッファメモリ３が発生するとそのバッフ
ァメモリの読み出しを優先したため、例えば図９のパケ
ットＢ２のように入力からかなり後に出力されるパケッ
トが生ずる。この点において図９と図19に大きな差はな
いように見えるが、これは説明の便から閾値を低く設定
したことに起因している。閾値を高く設定すれば出力時
期が大きく遅れるパケットは特定のバッファメモリ３に
集中トラヒックが加わったような場合にしか発生しな
い。これに対して、図19ではたとえトラヒックが低くて
もＢＭ−Ｂよりも多いパケットを蓄積しているバッファ
メモリ３が存在すればＢＭ−Ｂに蓄積されたパケットの
出力時期が大きく遅れる可能性が高い。

【００６９】以上から、図４の構成は廃棄率及びパケッ
トの遅延時間のいずれにおいもＬＮＱポーリング制御の
みにより読み出しを行う従来技術に対しても優れている
ことは明かである。

【００７０】次に図５の構成について図７、図10及び図
11を併用して説明する。図５の構成では閾値を超えるパ
ケットを蓄積したバッファメモリ３がない場合、ＦＩＦ
Ｏポーリング制御部21の制御によって出力が行われ、閾
値を超えるパケットを蓄積したバッファメモリ３が発生
するとＬＮＱポーリング制御部22の制御に切替えられ
る。

【００７１】最初に図７の(1) の入力モデルによりパケ
ットが入力され、すべてのバッファメモリ３の蓄積パケ
ットが閾値を超えない場合について説明する。図10はそ
の場合のバッファメモリＢＭ−Ａ〜ＢＭ−Ｄの蓄積状態
とパケットの入出力状況を説明する図である。

【００７２】図５では到着順序記憶部６が入力ハイウェ
イ１に入力されるパケットの到着順序をメモリ（図示省
略）に記憶している。図７はこれまで入力モデルの説明
に利用してきたが、本来は到着順序記憶部６のメモリに
パケットの到着順序が記憶された状態を説明する図であ
る。到着順序記憶部６にはパケットの到着順序がバッフ
ァメモリ別に記憶されるが、この場合、図７のＳ１〜Ｓ
１２はＢＭ−Ａ〜ＢＭ−Ｄ対応に設けられた到着順序記
憶部６内のメモリ領域の相対番地に相当し、Ｓ１が各メ
モリ領域の先頭番地を示していると見ることができる。
また、Ａ１〜Ｄ４は従来技術の説明においても述べたよ
うに、バッファメモリ３に蓄積されるパケット本体では
なく、アドレス情報などのパケット情報である。

【００７３】到着順序記憶部６のメモリもＦＩＦＯ式の
メモリであり、例えば先頭番地のＳ１に記憶されたパケ
ット情報Ａ１が読出制御部20に対して出力されるとＳ２
に記憶されたパケット情報Ｂ１が先頭番地に進み、以下
のパケット情報も順次１番地づつ歩進する。ただし、こ
のメモリに記憶されるパケット情報はバッファメモリ３
に蓄積されるパケットとは異なり、到着順序記憶部６内
においてバッファメモリ単位に先頭番地に詰めて記憶さ
れることはない。

【００７４】以上のように、到着順序記憶部６は図７の
(1) のように記憶されてゆくパケット情報を先頭番地Ｓ
１から順次読出制御部20内のＦＩＦＯポーリング制御部
21に送出するが、ＦＩＦＯポーリング制御部21はパケッ
ト情報の受信順に該当バッファメモリ３からそのパケッ
ト情報に指定されたパケットを読み出すよう出力部４を
制御する。その結果、図10の出力ＨＷに示す順序でパケ
ットが出力される。

【００７５】図10では全バッファメモリＢＭ−Ａ〜ＢＭ
−Ｄが閾値以上のパケットを蓄積することがないので図
９における出力順序と大きな差はないが、図10の場合、
同時に入力されたパケットの出力順序がトークンの位置
により前後することはあっても、図９と異なって後から
入力されたパケットが先に出力されることはない。

【００７６】次にパケット蓄積量が閾値を超えるバッフ
ァメモリ３が発生した場合、即ち、図７の(2) のように
パケットが入力された場合のバッファメモリ３の蓄積情
報とパケットの入出力状況を図11により説明する。この
場合、ＦＩＦＯポーリング制御部21は出力ＨＷにパケッ
トＡ２を出力したのち、パケットＢ２を出力しようとす
るが、パケットＣ５が入力されたことによりＢＭ−Ｃの
パケット蓄積量が閾値を超えるため、この時点から読出
制御部20はＬＮＱポーリング制御部22による制御に移
る。以後、パケットＣ５を出力するまでパケットの読み
出しはＢＭ−Ｃのみ行われ、パケットＣ５の出力を終わ
るとＦＩＦＯポーリング制御部21による制御に戻る。

【００７７】ここで、到着順序記憶部６のメモリの記憶
状態を説明する。この場合における到着順序記憶部６の
メモリの記憶状態は図７の(2) に示される。到着順序記
憶部６のメモリはＦＩＦＯメモリであるため、パケット
Ａ２を出力した状態では図７の(2) のＳ４に記憶された
パケット情報が先頭番地にきているが、ここでＦＩＦＯ
ポーリング制御部21がパケットＢ２を読み出す前に、Ｌ
ＮＱポーリング制御部22によってＳ５番地のパケットＣ
３、Ｓ７番地のパケットＣ４、Ｓ８番地のパケットＣ５
が読み出される。

【００７８】パケットＣ３、Ｃ４、Ｃ５を読み出す都
度、到着順序記憶部６のメモリを歩進させるとまだ出力
されていないパケットＢ２、Ｄ２、Ａ３、Ａ４の情報が
失われるため、ＦＩＦＯポーリング制御部21からＬＮＱ
ポーリング制御部22に制御が移った時点で到着順序記憶
部６のメモリの歩進（ＦＩＦＯ動作）を停止させる。従
って、この場合はＳ４番地が先頭番地となった状態で停
止する。

【００７９】ＬＮＱポーリング制御部22は制御を開始す
ると前記のように出力部４を制御してＢＭ−Ｃの読み出
しを行うが、そのとき読み出したパケットの識別情報
（到着順序記憶部６より受信して記憶しているパケット
情報）を優先読出パケット情報消去処理部23に送出す
る。優先読出パケット情報消去処理部23はこのパケット
情報を到着順序記憶部６に送り、到着順序記憶部６のメ
モリからそのパケット識別情報を消去させる。

【００８０】従って、ＢＭ−Ｃのパケット蓄積量が閾値
以下となったとき、即ち、パケットＣ５を出力し終わっ
た時点では到着順序記憶部６のメモリは図７の(2) のＳ
４のパケット情報がが先頭番地にあり、かつ、Ｃ３、Ｃ
４、Ｃ５のパケット情報が消去された状態となってい
る。ＢＭ−Ｃのパケット蓄積量が閾値以下となり、ＦＩ
ＦＯポーリング制御部21に制御が戻ると、ＦＩＦＯポー
リング制御部21は図７(2) のＳ４に記憶されているパケ
ットからバッファメモリの読み出しを再開するが、パケ
ットＡ２の読み出しが終了したことは記憶されているの
でパケットＢ２の読み出しから再開する。

【００８１】Ｓ４に記憶されたパケット情報によりパケ
ットＢ２の読み出しが終了すると到着順序記憶部６のメ
モリに記憶されたパケット情報は１番地づつ歩進する
が、パケットＣ３の識別情報が消去されているためＳ５
には何も記憶されていない。このため、メモリは更に歩
進し、Ｓ６が先頭番地となる。ＦＩＦＯポーリング制御
部21はＳ６に記憶されているパケットを読み出すように
制御するので、図11の出力ＨＷに示すようにパケットＢ
２に続いてパケットＤ２が出力される。

【００８２】ここで、図11をＦＩＦＯポーリング制御の
みにより読み出しを行った従来技術の図20と比較する。
図11と図20は入力モデルが全く同一であるが、各パケッ
トの出力順序を見ると、図18にはＦＩＦＯポーリングの
特徴である入力順の出力が保たれている状況が現れてい
るのに対して、図11は閾値を超えたＢＭ−Ｃの読み出し
を優先させるため、他のバッファメモリ３に蓄積されて
いる一部のパケット、例えばパケットＢ２などは出力が
遅延している。

【００８３】しかし、バッファメモリ３の蓄積量を比較
すると、特に入力パケットの多いＢＭ−Ｃにおいて図11
と図20の間に大きな差がある。即ち、図11では閾値を超
える３個目のパケットＣ５が入力されたのちもパケット
の蓄積量が３個以下であるのに対して図20ではパケット
の蓄積量が４個以上となる時間が比較的長く続く。バッ
ファメモリ３の蓄積容量を例えばパケット３個とする
と、図20ではパケットＣ６とＣ７は廃棄される可能性が
高いのに対して、図11ではパケットの廃棄は生じない。
即ち、パケットの廃棄率は明かに図11の方が低い。

【００８４】次に図11をＬＮＱポーリング制御のみによ
り読み出しを行った従来技術の図19と比較する。これま
での各方式の比較結果を加味して両図を比較すれば、こ
こでも図11の方がパケットの廃棄率が低いことは明かで
ある。また、図11では閾値を超えたパケットが蓄積され
たバッファメモリＢＭ−Ｃのパケットを優先して出力し
ている間を除いてパケットの出力順序はほぼ入力順序に
従っている。従って、パケットの送出遅延及び遅延変動
の点においても図11の方が優れていることは明かであ
る。

【００８５】次に図６の構成について説明するが、図６
の読出制御方法は図５と全く同一でり、バッファメモリ
３の蓄積状態とパケットの入出力状況も図11がそのまま
適用されるのでパケットの読出制御については説明を省
略し、優先読出パケット数記憶部24と読出省略処理部
（ＮＲＣ）25を主体に説明する。

【００８６】図５において説明したように、通常状態で
ＦＩＦＯポーリング制御を行い、閾値を超えるパケット
を蓄積したバッファメモリ３が発生したときにそのバッ
ファメモリ３の読み出しを優先させる読出制御方法で
は、優先して出力したパケット情報を到着順序記憶部６
から消去するか、優先読み出しを行ったバッファメモリ
３のパケット蓄積量が閾値以下となったのちにおいても
そのバッファメモリが優先的に読み出されることがない
ように処理する必要がある。図６は後者の処理を行うも
のである。

【００８７】図６のＦＩＦＯポーリング制御部21が出力
ＨＷにパケットＡ２を出力したときにＢＭ−Ｃにパケッ
トＣ５が入力されると、ＢＭ−Ｃのパケット蓄積量が閾
値を超えるため、この時点から読出制御部20はＬＮＱポ
ーリング制御部22による制御に移り、ＬＮＱポーリング
制御部22は先ずパケットＣ３を読み出す。このとき、Ｌ
ＮＱポーリング制御部22は優先読出パケット数記憶部24
に対して優先読み出しの実行を知らせる情報を送出す
る。この状態でＢＭ−ＣよりパケットＣ３が読み出され
るとＢＭ−Ｃより読み出しが行われたことを検出できる
信号（以下、読出信号と記す）、例えばバッファメモリ
３のリードイネーブル信号（周知の技術であるため、詳
細説明は省略する）が優先読出パケット数記憶部24内の
カウンタＣＮＴ−Ｃに出力される。カウンタ24A 〜24D
は初期値は“０”となっているが、ＬＮＱポーリング制
御部22より優先読み出しの実行を知らせる情報が送出さ
れている状態でバッファメモリ３より読出信号が送出さ
れると読み出しが行われたバッファメモリ３に対応する
カウンタ（この場合はＣＮＴ−Ｃ）をインクリメントす
る。優先読み出しはパケットＣ５を出力するまで行われ
るので、パケットＣ４及びＣ５が読み出されるときにも
ＣＮＴ−Ｃはインクリメントされ、優先読み出しを終了
した時点でＣＮＴ−Ｃの記憶している数値は「３」とな
る。

【００８８】この状態で制御がＦＩＦＯポーリング制御
部21に戻ると、ＦＩＦＯポーリング制御部21は到着順序
記憶部６より到着順のパケット情報を得てＦＩＦＯポー
リング制御によるパケットの読出制御を再開する。この
とき、到着順序記憶部６のメモリは前記したように図７
の(2) のＳ４が先頭番地になっている状態であるが、図
６の構成ではパケットＣ３〜Ｃ５の識別情報は消去され
ないためそのまま残っている。

【００８９】ＦＩＦＯポーリング制御部21は読出制御を
再開すると図５におけると同様に先ずパケットＢ２を読
み出す動作に入るが、その際、ＦＩＦＯポーリング制御
部21内の読出省略処理部25がパケットＢ２が蓄積されて
いるバッファメモリＢＭ−Ｂに対応するカウンタＣＮＴ
−Ｂの数値を確認する。ＣＮＴ−Ｂは対応するバッファ
メモリＢＭ−Ｂが優先読み出しをされることがなかった
ため、数値は初期値の“０”を表示している。読出省略
処理部25はこれをＦＩＦＯポーリング制御部21の本体に
知らせる。カウンタの数値が１以上の数を示していない
場合、ＦＩＦＯポーリング制御部21はそのまま読み出し
を行うように制御するのでパケットＢ２がＢＭ−Ｂより
読み出される。

【００９０】これによって到着順序記憶部６のメモリは
歩進し、図７の(2) に示すＳ５が先頭番地になる。ＦＩ
ＦＯポーリング制御部21はＳ５に記憶されているパケッ
トＣ３の識別情報を得て読み出し動作に入り、パケット
Ｂ２の場合と同様に読出省略処理部25はパケットＣ３が
蓄積されているバッファメモリＢＭ−Ｃに対応するカウ
ンタＣＮＴ−Ｃの数値を確認する。このときＣＮＴ−Ｃ
は前記のように「３」を表示しているが、カウンタの数
値が１以上の数を示していると、読出省略処理部25はそ
のカウンタの数値をデクリメントするとともに、ＦＩＦ
Ｏポーリング制御部21にそのときのパケット（この場合
はパケットＣ３）の読み出しを省略させるようにする。
従って、到着順序記憶部６のメモリにパケット情報が残
っていてもパケットＣ２が再び出力されたり、閾値以下
となっているバッファメモリＢＭ−Ｃから他のパケット
が優先的に読み出されたりすることはない。なお、この
時点でカウンタＣＮＴ−Ｃの数値は「２」となる。

【００９１】以後、同様にしてＦＩＦＯポーリング制御
部21はパケットＤ２、Ａ３、Ａ４を読み出すが、その間
においてパケットＣ４、Ｃ５の読み出し制御は省略す
る。パケットＣ５の読み出しを省略した時点でカウンタ
ＣＮＴ−Ｃの数値は「０」となるので、以後のバッファ
メモリＢＭ−Ｃからの読み出しは正常に行われる。優先
読み出しを行ったバッファメモリ３よりの読み出しがパ
ケット蓄積量が閾値以下となったのちに混乱することを
防止する方法として図６の方法はハード回路主体で構成
できるため、ソフトウェアによる動作が主体となる図５
の方法よりも処理が簡単となると言う特徴がある。

【００９２】以上、図４〜図11により本発明の実施例を
説明したが、図４〜図11はあくまで本発明の実施例の一
部を示したものに過ぎず、本発明が図示した内容のみに
限定されないことは言うまでもない。例えば、図４〜図
11においては出力部４内にトークンを循環させるとして
説明したが、出力部４がバッファメモリ３を選択する方
法はトークンを使用する方法以外にも各種の方法があ
り、いずれの方法によっても本発明の効果が変わらない
ことは明かである。また、優先読出パケット数記憶部2
4、特にその内部に設けられるカウンタＣＮＴ−Ｃ〜Ｃ
ＮＴ−Ｃは図６においては読出制御部20内に設けられて
いるが、これらが読出制御部20の外に設けられていても
本発明の効果は変わらない。

【００９３】更に、図８〜図10においては特定の入力モ
デルによりパケットの入出力状況を説明したが、その特
徴は定性的なものであるため、入力モデルが変わっても
それぞれの特徴が失われたり、各構成間或いは従来技術
との間で優劣関係が変わることがないことは明かであ
る。

【００９４】

【発明の効果】以上説明したように、入力ハイウェイと
出力ハイウェイの交差点にバッファメモリを設けて入力
されるパケットを一時蓄積させたのち出力ハイウェイに
出力させるパケット交換機においては、特定の入力ハイ
ウェイから同一方路宛にバースト状のパケットが入力さ
れるとその入力ハイウェイに対応するバッファメモリに
パケットが集中して蓄積されるため、パケットの廃棄率
が高くなる可能性があるが、本発明によればパケット量
が予め定めた閾値以上に達するとそのバッファメモリに
蓄積されたパケットを優先的に出力させるため、パケッ
トの廃棄率を低下させることができ、また、蓄積量が多
いバッファメモリや蓄積量が少ないバッファメモリに蓄
積されたパケットの出力遅延時間及び出力遅延時間の変
動が極端に大きくなる現象が避けられる。このため、本
発明はパケット交換機の性能向上とサービス品質の向上
に大きく貢献する。

【図面の簡単な説明】

【図１】 本発明の原理説明図（１）

【図２】 本発明の原理説明図（２）

【図３】 本発明の原理説明図（３）

【図４】 本発明の実施例構成図（１）

【図５】 本発明の実施例構成図（２）

【図６】 本発明の実施例構成図（３）

【図７】 本発明の実施例到着順序記憶部記憶状態説明
図

【図８】 図４の構成における実施例バッファメモリ蓄
積状態説明図（１）

【図９】 図４の構成における実施例バッファメモリ蓄
積状態説明図（２）

【図10】 図５・図６の構成における実施例バッファメ
モリ蓄積状態説明図（１）

【図11】 図５・図６の構成における実施例バッファメ
モリ蓄積状態説明図（２）

【図12】 ＡＴＭスイッチの構成説明図

【図13】 出力バッファ形式構成図

【図14】 クロスポイントバッファ形式構成図

【図15】 従来技術の構成図（１）

【図16】 従来技術の構成図（２）

【図17】 従来技術の構成図（３）

【図18】 従来技術のバッファメモリ蓄積状態説明図
（１）

【図19】 従来技術のバッファメモリ蓄積状態説明図
（２）

【図20】 従来技術のバッファメモリ蓄積状態説明図
（３）

【符号の説明】

１ 入力ハイウェイ ２ 出力ハイウェイ ３ バッファメモリ ４ 出力部 ５ 蓄積量監視手段 ６ 到着順序記憶手段 10、20 読出制御部 11 バッファ順次読出制御手段 12、22 最大蓄積バッファ優先読出制御手段 21 到着順読出制御手段 23 優先読出パケット情報消去手段 24 優先読出パケット数記憶手段 25 読出省略処理手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者 朝永 博 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 鴨井 條益 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内

Claims (3)

【特許請求の範囲】
1. 【請求項１】 同一方路宛のパケットが入力される複数
   の入力ハイウェイ(1) と該方路に対応する出力ハイウェ
   イ(2) の交差点に前記複数の入力ハイウェイ(1) 対応に
   設けた先入れ先出し方式のバッファメモリ(3) に入力さ
   れるパケットを一時蓄積させたのち、読出制御部(10)の
   制御により前記バッファメモリ(3) より読み出し、出力
   部(4) を介して前記出力ハイウェイ(2) に出力させるパ
   ケット交換機のパケット出力制御方式であって、 前記各バッファメモリ(3) に蓄積されたパケットの量を
   監視し、予め定めた閾値を超える量のパケットを蓄積し
   たバッファメモリ(3) が発生したとき、該バッファメモ
   リ(3) のパケット蓄積量が閾値を超えたことを示す情報
   をパケット蓄積量が閾値以下となるまで送出する蓄積量
   監視手段(5) を備え、かつ、 前記読出制御部(10)内に、前記バッファメモリ(3) を一
   定順序で選択し、選択したバッファメモリ(3) の先頭に
   蓄積されているパケットを前記出力ハイウェイ(2) に出
   力するよう前記出力部(4) を制御するバッファ順次読出
   制御手段(11)と、 前記蓄積量監視手段(5) よりパケット蓄積量が閾値を超
   えたバッファメモリ(3) が発生したことを示す情報が送
   出されている間、前記バッファ順次読出制御手段(11)に
   よる読出制御に優先してパケット蓄積量が閾値を超えた
   バッファメモリ(3) よりパケットを読み出して前記出力
   ハイウェイ(2) に出力するよう前記出力部(4) を制御す
   る最大蓄積バッファ優先読出制御手段(12)を備えたこと
   を特徴とするパケット出力制御方式。
2. 【請求項２】 同一方路宛のパケットが入力される複数
   の入力ハイウェイ(1) と該方路に対応する出力ハイウェ
   イ(2) の交差点に前記複数の入力ハイウェイ(1) 対応に
   設けた先入れ先出し方式のバッファメモリ(3) に入力さ
   れるパケットを一時蓄積させたのち、読出制御部(20)の
   制御により前記バッファメモリ(3) より読み出し、出力
   部(4) を介して前記出力ハイウェイ(2) に出力させるパ
   ケット交換機のパケット出力制御方式であって、 前記各バッファメモリ(3) に蓄積されたパケットの量を
   監視し、予め定めた閾値を超える量のパケットを蓄積し
   たバッファメモリ(3) が発生したとき、該バッファメモ
   リ(3) のパケット蓄積量が閾値を超えたことを示す情報
   をパケット蓄積量が閾値以下となるまで送出する蓄積量
   監視手段(5) と、 前記入力ハイウェイ(1) より入力されるパケットの識別
   情報を該パケットが蓄積されるバッファメモリ(3) と到
   着順が識別できるように記憶したのち、該識別情報を到
   着順に順次送出する到着順序記憶手段(6) を備え、か
   つ、 前記読出制御部(20)内に、前記到着順序記憶手段(6) よ
   り順次送出されるパケットの識別情報を受信する都度、
   該パケットが蓄積されているバッファメモリ(3) からパ
   ケットを読み出して前記出力ハイウェイ(2) に出力する
   よう前記出力部(4) を制御する到着順読出制御手段(21)
   と、 前記蓄積量監視手段(5) よりパケット蓄積量が閾値を超
   えたバッファメモリ(3) が発生したことを示す情報が送
   出されている間、前記到着順読出制御手段(21)による読
   出制御に優先してパケット蓄積量が閾値を超えたバッフ
   ァメモリ(3) よりパケットを読み出して前記出力ハイウ
   ェイ(2) に出力するよう前記出力部(4)を制御する最大
   蓄積バッファ優先読出制御手段(22)と、 前記最大蓄積バッファ優先読出制御手段(22)が優先的に
   出力させたパケットの識別情報を最大蓄積バッファ優先
   読出制御手段(22)より受信して前記到着順序記憶手段
   (6) に記憶されているパケットの識別情報の中から該パ
   ケットの識別情報を消去させる制御を行う優先読出パケ
   ット情報消去手段(23)を備えたことを特徴とするパケッ
   ト出力制御方式。
3. 【請求項３】 前記優先読出パケット情報消去手段(23)
   に代えて、前記バッファメモリ(3) 対応に設けた計数手
   段を内蔵し、前記最大蓄積バッファ優先読出制御手段(2
   4)の制御により前記バッファメモリ(3) よりパケットが
   読み出されたときに該バッファメモリ(3) に対応する前
   記計数手段が示す数値に１を加算し、前記到着順読出制
   御手段(21)より減算の指示を受信した場合に指示された
   バッファメモリ(3) に対応する前記計数手段が示す数値
   より１を減ずる優先読出パケット数記憶手段(24)を備
   え、かつ、 前記到着順読出制御手段(21)内に、該到着順読出制御手
   段(21)が前記出力部(4) に対して前記バッファメモリ
   (3) に蓄積されたパケットを読み出す制御を行う際に、
   前記優先読出パケット数記憶手段(26)内の該当バッファ
   メモリ(3) に対応する前記計数手段が示す数値を確認
   し、該数値が１以上である場合にパケットの読出制御を
   省略して前記優先読出パケット数記憶手段(26)内の該当
   バッファメモリ(3) に対応する前記計数手段に対して該
   計数手段が示す数値より１を減ずるよう指示する読出省
   略処理手段(25)を備えたことを特徴とする請求項２記載
   のパケット出力制御方式。