JPH11103296A - 競合制御回路 - Google Patents

Abstract

(57)【要約】 【課題】 ＡＴＭ伝送路上に多重されたセル流のバース
ト性を除去するために、セルをメモリに書き込み、読み
出す方式のシェーピング装置において、セル出力の競合
制御回路の規模を小さくすることを目的とする。 【解決手段】 セル書き込み時は、書き込みアドレス制
御部２０は空きアドレスメモリ４０からセルメモリ１０
の空きアドレスを入力し、セルメモリ１０に出力する。
また、理想送出時刻が入力されると、その値をアドレス
とし、セル存在有無メモリ６０、先頭アドレスメモリ７
０、最終アドレスメモリ８０にアクセスする。セル読み
出し時は、読み出しアドレス制御部３０はセルメモリ１
０への読み出しアドレスを出力し、現在時刻が入力され
ると、その値をアドレスとし、セル存在有無メモリ６
０、先頭アドレスメモリ７０、最終アドレスメモリ８０
にアクセスする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ＡＴＭ（非同期転
送モード）網において、多数の宛先のセルが多重された
回線上で、同一宛先のセルのバースト性を除去するため
のシェーピング装置に用いられ、異なる宛先のセルの理
想的な送出時刻が一致して出力の競合が生じた場合に、
その競合制御を行う競合制御回路に関するものである。

【０００２】

【従来の技術】ＡＴＭ網のセル流においては、一般に多
重化装置やスイッチ等を通過する際に、セル間隔が入力
時と出力時で異なるというセル遅延揺らぎ（ＣＤＶ：Ｃ
ｅｌｌＤｅｌａｙ Ｖａｒｉａｔｉｏｎ）が生じる。Ｃ
ＤＶはその他の種々の要因によっても生じるが、ＣＤＶ
によりセル間隔が縮まると、局所的に帯域（セル間隔の
逆数）が増加することになり、交換機等での収容率がオ
ーバーしてセルが廃棄される等の問題が生じる。そこ
で、ＣＤＶにより縮まったセル間隔を広げるシェーピン
グ装置が用いられている。

【０００３】シェーピング装置によってセル間隔を広げ
ることは一般にセル間隔の縮まったセルを遅延させるこ
とにより実現される。セル間隔は帯域に対応するので、
宛先が異なり、帯域も異なるセルに対しては、そのセル
間隔は異なり、遅延させる量も異なる。例えば宛先Ａの
セルの帯域が１０Ｍｂ／ｓで、宛先Ｂのセルの帯域が２
０Ｍｂ／ｓの場合は、宛先Ａのセルのセル間隔は宛先Ｂ
のセルのセル間隔の２倍となる。

【０００４】また、セルを遅延させるシェーピングの方
式には種々の方式があるが、本発明に係る競合制御回路
は、入力セルを一度、メモリに書き込み、出力すべき時
刻にメモリから読み出すシェーピング方式を採用したも
のである。ただし、既に述べたように、宛先の異なるセ
ルは遅延させる量が異なるため、出力すべき時刻が同一
時刻となる恐れがあるという問題がある。

【０００５】この場合、同一時刻には一つのセルしか出
力できないため、同一時刻の他のセルは止むを得ず本来
出力すべき時刻とは異なる時刻で出力する必要が生じ
る。以後の説明では、本来出力すべき時刻を理想送出時
刻と呼ぶ。このように、理想送出時刻に出力できないと
きに、どのように出力するかを決める制御を競合制御と
呼ぶ。また、この競合制御を実現する回路が本発明で採
り挙げる競合制御回路である。

【０００６】従来の競合制御の一方法として、理想送出
時刻以降で、出力すべきセルがない最も近い時刻を出力
時刻とする方法がある。図１９がその競合制御の動作を
示す説明図である。図１９において、理想送出時刻「ｔ
０＋１」のセルＡが到着する前に、出力時刻が「ｔ
０」，「ｔ０＋１」，「ｔ０＋３」の他のセルが既に存
在しているとする。このとき上記セルＡが到着したとす
ると、既に「ｔ０＋１」の時刻に出力すべき他のセルが
あるため、止むを得ずこの時刻以降で上記セルＡを出力
できる時刻（即ち、空いている時刻）を検索する。

【０００７】この例では「ｔ０＋２」の時刻に出力すべ
きセルがなくて空きになっているので、上記セルＡの出
力時刻としてこの「ｔ０＋２」を割り当てる。次に、理
想送出時刻「ｔ０」のセルＢが到着したとすると、既に
「ｔ０」の時刻に出力すべき他のセルがあるため、止む
を得ずこの時刻以降で上記セルＢを出力できる時刻を検
索する。この例では「ｔ０＋４」の時刻に出力すべきセ
ルがなくて空きになっているので、セルＢの出力時刻と
してこの「ｔ０＋４」を割り当てる。

【０００８】この図１９に示す従来の競合制御方法を用
いたものとして、例えば特開平８−１２５６６８号公報
に示された従来のシェーピング回路がある。図２０はこ
の公報に示された従来のシェーピング回路の構成図であ
る。図２０において、３００は送出時刻及びこの送出時
刻に対応するアドレスを有するセルバッファ、３１０は
入力セルのＶＰＩ／ＶＣＩ（ＶＰＩ：Ｖｉｒｔｕａｌ
Ｐａｔｈ Ｉｄｅｎｔｉｆｉｅｒ、ＶＣＩ：Ｖｉｒｔｕ
ａｌ Ｃｈａｎｎｅｌ Ｉｄｅｎｔｉｆｉｅｒ）を識別
するヘッダ識別部、３２０はパラメータテーブル３５０
からのパラメータに基づいて理想送出時刻を計算する送
出時刻計算部である。

【０００９】また、３３０は送出時刻計算部３２０から
の理想送出時刻に基づいて検索テーブル３６０を検索し
て空ぎ時刻を求める空き時刻検索部、３４０はセルバッ
ファ３００の書き込みアドレスおよび読み出しアドレス
を制御するバッファ制御部、３５０はパラメータテーブ
ル、３６０は検索テーブル、３７０は現在時刻に対応す
るバッファ読み出しアドレスを出力するセル出力リスト
である。

【００１０】次に、図２０に示すシェーピング回路の動
作について説明する。ヘッダ識別部３１０は入力セルの
ヘッダに含まれるＶＰＩ／ＶＣＩを識別して出力する。
このＶＰＩ／ＶＣＩは送出時刻計算部３２０に入力され
る。送出時刻演算部３２０は、上記ＶＰＩ／ＶＣＩを入
力すると、パラメータテーブル３５０に記憶してあるパ
ラメータを使ってこのＶＰＩ／ＶＣＩに対応するセルの
送出すべき時刻（理想送出時刻）を計算し、空き時刻検
索部３３０に通知する。

【００１１】空き時刻検索部３３０は、上記理想送出時
刻を入力すると、検索テーブル３６０を参照して、上記
送出時刻計算部３２０から通知された理想送出時刻また
はそれ以降の時間で送出が可能な空き時刻を検索し、検
出された空き時刻をバッファ制御部３４０に通知する。
バッファ制御部３４０は空き時刻検索部３３０から出力
された空き時刻を入力し、セルバッファ３００の書き込
みアドレスとして出力する。また、検索テーブル３６０
の当該空き時刻は使用中時刻に変更される。

【００１２】また、セル出力リスト３７０から現在時刻
に対応するデータを読み出し、セルバッファ３００の読
み出しアドレスとして出力する。読み出されたセルの送
信が完了すると、検索テーブル３６０の当該セルに対応
した領域を空き時刻に変更する。

【００１３】このように、空き時刻検索部３３０と検索
テーブル３６０により、理想送出時刻から実際に送出す
る時刻を求めることにより競合制御を行っている。図２
０に示すセルバッファ３００は送出時刻とアドレスが対
応する構成となっており、セルバッファ３００を用いて
書き込みと読み出しの制御を行っているため、セルバッ
ファ３００とバッファ制御部３４０とセル出力リスト３
７０も含めた回路３８０を競合制御回路とみなすことが
できる。本発明はこの競合制御回路３８０に関する発明
であり、送出時刻計算部３２０の回路構成は任意のもの
で構わない。

【００１４】しかし、図１９のように空き時刻を検索す
る方法では検索位置以降に既にセルが多数存在する場
合、本来の送出時刻より実際の送出時刻がかなり遅くな
る場合がある。また、図１９のように、競合制御により
理想送出時刻が早い（時刻「ｔ０」）セルＢが、理想送
出時刻が遅い（時刻「ｔ０＋１」）セルＡよりも遅く出
力される場合が生じるというセルの送出順序の問題があ
る。このセル送出順序の問題は各時刻毎に保存できるセ
ルが１セルの場合であるために生じるものである。

【００１５】そのため、この問題を解決する方法とし
て、各時刻毎に保存できる数を多くし、同一時刻では早
く到着したものから順に出力するという競合制御方法も
考えられている。この方法による競合制御を以後、ＦＩ
ＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）型競合
制御と呼ぶ。

【００１６】図２１は従来のＦＩＦＯ型競合制御の動作
を示す説明図である。図２１に示すように、ＦＩＦＯ型
競合制御では、理想送出時刻毎にＦＩＦＯメモリを持
ち、理想送出時刻が同一のセル同志でキューを形成す
る。そしてＦＩＦＯメモリから順次セルを読み出して出
力する。ＦＩＦＯ型競合制御では、理想送出時刻とのず
れが、図１９の競合制御方法よりも小さくなり、また理
想送出時刻の早い順に必ず出力される。

【００１７】図２２は図２１に示す従来のＦＩＦＯ型競
合制御を実現するための構成図である。図２２におい
て、４００は理想送出時刻毎に設けられたＦＩＦＯメモ
リ、４１０は理想送出時刻をデコードして対応するＦＩ
ＦＯメモリに書き込み信号を出力するデコーダ、４２０
は各ＦＩＦＯメモリ４００の空き状態と現在時刻から、
読み出すＦＩＦＯメモリを決定する読み出し制御部であ
る。

【００１８】次に、図２１の動作を図２２を用いて説明
する。図２１において、「ｔ０−１」、「ｔ０」、「ｔ
０＋１」、「ｔ０＋２」、「ｔ０＋３」、「ｔ０＋４」
の６個の理想送出時刻毎のＦＩＦＯメモリがあり、「ｔ
０」、「ｔ０＋１」、「ｔ０＋３」のＦＩＦＯメモリに
はすでに他のセルが１つずつ格納されているとする。例
えば、「ｔ０」のＦＩＦＯメモリにはセルａが、「ｔ０
＋１」のＦＩＦＯメモリにはセルｂが、「ｔ０＋３」の
ＦＩＦＯメモリにはセルｃが格納されているとする。

【００１９】このとき、理想送出時刻「ｔ０＋１」のセ
ルＡが到着すると、当該セルＡは、理想送出時刻に相当
するＦＩＦＯメモリ４００に、デコーダ４１０の書き込
み信号を用いて、書き込まれる。即ち、セルＡの理想送
出時刻「ｔ０＋１」はデコーダ４１０でデコードされ、
「ｔ０＋１」のＦＩＦＯメモリ４００が選択される。従
ってセルＡは「ｔ０＋１」のＦＩＦＯメモリ４００に格
納される。しかし、この「ｔ０＋１」のＦＩＦＯメモリ
４００にはすでにセルｂが格納されているので、セルＡ
はこのセルｂの後に格納されることになる。

【００２０】次に、理想送出時刻「ｔ０」のセルＢが到
着すると、セルＢの理想送出時刻「ｔ０」はデコーダ４
１０でデコードされ、「ｔ０」のＦＩＦＯメモリ４００
が選択される。従ってセルＢは「ｔ０」のＦＩＦＯメモ
リ４００に格納される。しかし、この「ｔ０」のＦＩＦ
Ｏメモリ４００にはすでにセルａが格納されているの
で、セルＢはこのセルａの後に格納されることになる。

【００２１】次に、図２２のシェーピング回路におい
て、読み出し制御部４２０は、各ＦＩＦＯメモリからの
空き信号と、現在時刻の情報から、読み出すべきＦＩＦ
Ｏメモリ４００を１つ選択し、読み出し信号を選択され
たＦＩＦＯメモリ４００に出力する。これにより、ＦＩ
ＦＯメモリ４００から以下の順序でセルが出力される。
まず「ｔ０」のＦＩＦＯメモリ４００に格納されている
セルがすべて出力され、次に、「ｔ０＋１」のＦＩＦＯ
メモリ４００に格納されているセルがすべて出力され、
次に、「ｔ０＋２」のＦＩＦＯメモリ４００に格納され
ているセルがすべて出力され、次に、「ｔ０＋３」のＦ
ＩＦＯメモリ４００に格納されているセルがすべて出力
され、次に、「ｔ０＋４」のＦＩＦＯメモリ４００に格
納されているセルがすべて出力される。

【００２２】この結果、図２１に示すように、シェーピ
ング回路出力として、まず時刻「ｔ０」にセルａが出力
され、時刻「ｔ０＋１」にセルＢが出力され、時刻「ｔ
０＋２」にセルｂが出力され、時刻「ｔ０＋３」にセル
Ａが出力され、時刻「ｔ０＋４」にセルｃが出力され
る。

【００２３】

【発明が解決しようとする課題】従来のＦＩＦＯ型競合
制御回路は上記のように、ＦＩＦＯメモリ４００を理想
送出時刻毎に設けることにより実現していた。しかも回
線に収容されるパスすべてが同一理想送出時刻となる可
能性があるため、ＦＩＦＯメモリの容量は、どの時刻に
おいても収容パス数分保存する必要があった。従って、
遅延させる量が大きくて、理想送出時刻の取りうる値が
多いときは、ＦＩＦＯメモリの個数が多くなり、また、
収容パス数が多い場合は、それぞれのＦＩＦＯメモリの
容量が大きくなり、回路規模が巨大になってしまうとい
う問題点があった。

【００２４】本発明は、このような問題点を解決するた
めに行われたもので、遅延量と収容パス数に依存せず、
従来よりも回路規模の小さい競合制御回路を提供するこ
とを目的とする。

【００２５】

【課題を解決するための手段】この発明に係る競合制御
回路は、到着したＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ
Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）セル（以下単にセルと呼
ぶ）をメモリに書き込み、出力時刻にメモリから読み出
すシェーピング装置に含まれる競合制御回路において、
上記セルを保存するセルメモリと、該セルメモリの空き
アドレスを管理する空きアドレスメモリと、上記セルメ
モリの書き込みアドレスを制御する書き込みアドレス制
御部と、上記セルメモリの読み出しアドレスを制御する
読み出しアドレス制御部と、上記セルメモリの上記セル
の読み出し順序を管理するアドレスチェーンメモリと、
理想送出時刻毎に上記セルが存在するかどうかの情報を
持つセル存在有無メモリと、理想送出時刻毎に最初に出
力すべきセルが保存されているセルメモリのアドレスを
記録する先頭アドレスメモリと、理想送出時刻毎に最後
に出力すべきセルが保存されているセルメモリのアドレ
スを記録する最終アドレスメモリと、を備えたものであ
る。

【００２６】また、この発明に係る競合制御回路は、到
着したセルをメモリに書き込み、出力時刻にメモリから
読み出すシェーピング装置に含まれる競合制御回路にお
いて、上記セルを保存するセルメモリと、上記セルメモ
リの空きアドレスを管理する空きアドレスメモリと、該
セルメモリの書き込みアドレスを制御する書き込みアド
レス制御部と、上記セルメモリの読み出しアドレスを制
御する読み出しアドレス制御部と、上記セルメモリの上
記セルの読み出し順序を管理するアドレスチェーンメモ
リと、理想送出時刻毎に上記セルが存在するかどうかの
情報を持つセル存在有無メモリと、理想送出時刻毎に最
初に出力すべきセルが保存されているセルメモリのアド
レスを記録する先頭アドレスメモリと、理想送出時刻毎
に最後に出力すべきセルが保存されているセルメモリの
アドレスを記録する最終アドレスメモリと、入力セルの
ヘッダに含まれる識別子を取り出すヘッダ識別部と、識
別子毎の遅延優先クラスを記録した遅延優先情報メモリ
とを備え、前記遅延優先クラスは２クラスであり、入力
セルの遅延優先情報に応じて書き込みアドレスを制御す
る手段を備えたものである。

【００２７】また、この発明に係る競合制御回路は、到
着したセルをメモリに書き込み、出力時刻にメモリから
読み出すシェーピング装置に含まれる競合制御回路にお
いて、上記セルを保存するセルメモリと、このセルメモ
リの空きアドレスを管理する空きアドレスメモリと、上
記セルメモリの書き込みアドレスを制御する書き込みア
ドレス制御部と、上記セルメモリの読み出しアドレスを
制御する読み出しアドレス制御部と、上記セルメモリの
セルの読み出し順序を管理するアドレスチェーンメモリ
と、理想送出時刻毎にセルが存在するかどうかの情報を
持つセル存在有無メモリと、理想送出時刻毎に最初に出
力すべきセルが保存されているセルメモリのアドレスを
記録する先頭アドレスメモリと、理想送出時刻毎に最後
に出力すべきセルが保存されているセルメモリのアドレ
スを記録する最終アドレスメモリと、入力セルのヘッダ
に含まれる識別子を取り出すヘッダ識別部と、識別子毎
の遅延優先クラスを記録した遅延優先情報メモリとを備
え、前記遅延優先クラスは２クラスであり、セル存在有
無メモリと先頭アドレスメモリと最終アドレスメモリ
は、遅延優先クラス毎にデータを保持しており、入力セ
ルの遅延優先クラスに応じて書き込みアドレスを制御す
る手段を備えたものである。

【００２８】また、この発明に係る競合制御回路は、到
着したセルをメモリに書き込み、出力時刻にメモリから
読み出すシェーピング装置に含まれる競合制御回路にお
いて、セルを保存するセルメモリと、上記セルメモリの
空きアドレスを管理する空きアドレスメモリと、このセ
ルメモリの書き込みアドレスを制御する書き込みアドレ
ス制御部と、上記セルメモリの読み出しアドレスを制御
する読み出しアドレス制御部と、上記セルメモリの上記
セルの読み出し順序を管理するアドレスチェーンメモリ
と、理想送出時刻毎に上記セルが存在するかどうかの情
報を持つセル存在有無メモリと、理想送出時刻毎に最初
に出力すべきセルが保存されているセルメモリのアドレ
スを記録する先頭アドレスメモリと、理想送出時刻毎に
最後に出力すべきセルが保存されているセルメモリのア
ドレスを記録する最終アドレスメモリと、入力セルのヘ
ッダに含まれる識別子を取り出すヘッダ識別部と、識別
子毎の遅延優先クラスを記録した遅延優先情報メモリと
を備え、前記遅延優先クラスは３クラス以上であり、セ
ル存在有無メモリと先頭アドレスメモリと最終アドレス
メモリは、遅延優先クラス毎にデータを保持しており、
入力セルの遅延優先クラスに応じて書き込みアドレスを
制御する手段を備えたものである。

【００２９】

【発明の実施の形態】

実施の形態１．図１はこの発明に係る競合制御回路の一
実施の形態を示す構成図である。図１において、１０は
セルを保存するセルメモリ、２０はセルメモリ１０の書
き込みアドレスを制御する書き込みアドレス制御部、３
０はセルメモリ１０の読み出しアドレスを制御する読み
出しアドレス制御部、４０はセルメモリ１０の空きアド
レスを管理する空きアドレスメモリ、５０はセルメモリ
１０のアドレスチェーンを管理するアドレスチェーンメ
モリ、６０は理想送出時刻毎に出力すべきセルが存在す
るかどうかの情報を保存するセル存在有無メモリ、７０
は理想送出時刻毎のセルメモリ１０の先頭アドレスを管
理する先頭アドレスメモリ、８０は理想送出時刻毎のセ
ルメモリ１０の最終アドレスを管理する最終アドレスメ
モリである。

【００３０】図１ではセルメモリ１０、アドレスチェー
ンメモリ５０、セル存在有無メモリ６０、先頭アドレス
メモリ７０、最終アドレスメモリ８０は書き込みアドレ
スと読み出しアドレスを持つ２ポートＲＡＭを想定して
いるが、時分割にアクセスすることによりシングルポー
トＲＡＭを用いることも可能である。

【００３１】また空きアドレスメモリ４０はＦＩＦＯメ
モリを想定しているが、シングルポートＲＡＭを用いて
ライトアドレスとリードアドレスを制御することにより
実現することも可能である。

【００３２】またセル存在有無メモリ６０、先頭アドレ
スメモリ７０、最終アドレスメモリ８０は必要アドレス
数が同一であるため、データ幅を大きくし、１つのメモ
リで実現することも可能である。またセル存在有無メモ
リ６０のデータ幅は１ビットであるため、セレクタとレ
ジスタを組み合わせて実現することも可能である。

【００３３】まず、本実施の形態におけるＦＩＦＯ型競
合制御の実現方法の原理について説明する。本実施の形
態ではＦＩＦＯ型競合制御を図２２に示すような理想送
出時刻毎に設けられたＦＩＦＯメモリ４００を用いない
で実現する。そのために、理想送出時刻に関係せずセル
を保存する１つの共通メモリ（セルメモリ１０）とその
空きアドレスを管理する空きアドレスメモリ４０、およ
び図２２のＦＩＦＯに相当する情報（同一理想送出時刻
におけるセルの到着順序）を保持する４個のアドレス制
御メモリ（アドレスチェーンメモリ５０、セル存在有無
メモリ６０、先頭アドレスメモリ７０、最終アドレスメ
モリ８０）により構成する。

【００３４】図２は図２２の従来のＦＩＦＯに相当する
情報の保持方法を示した説明図である。セル存在有無メ
モリ６０、先頭アドレスメモリ７０、最終アドレスメモ
リ８０は理想送出時刻毎にデータを保持する。アドレス
チェーンメモリ５０は、セルメモリ１０のアドレス毎に
データを保持している。

【００３５】セル存在有無メモリ６０は、理想送出時刻
毎に出力すべきデータが存在しているかどうかの情報１
ビットを保持している。先頭アドレスメモリ７０は、理
想送出時刻毎に、最初に出力すべきデータが存在してい
るセルメモリ１０のアドレスを保持している。最終アド
レスメモリ８０は、理想送出時刻毎に、最後に出力すべ
きデータが存在しているセルメモリ１０のアドレスを保
持している。アドレスチェーンメモリ５０は同一理想送
出時刻のセルが保存されているセルメモリ１０のアドレ
スを出力順序を含めて保持するものであり、具体的には
セルメモリ１０に保存されているセルをアドレスとし、
次に出力するセルのアドレスをデータとして保持してい
る。

【００３６】次に、図２の動作を説明する。図２におい
て、理想送出時刻が「ｔ」のセルが到着した場合、書き
込みアドレス制御部２０はこの理想送出時刻「ｔ」をア
ドレスとしてセル存在有無メモリ６０のデータを読み出
す。この場合、読み出したデータは「１」であるため、
書き込みアドレス制御部２０は送出すべきセルが既にセ
ルメモリ１０に存在していることを認識する。

【００３７】そこで、書き込みアドレス制御部２０は先
頭アドレスメモリ７０のアドレス「ｔ」のデータを読み
出す。すると、データ「１０」が得られるため、書き込
みアドレス制御部２０は最初のセルがセルメモリ１０の
アドレス１０に保存されていると認識する。また書き込
みアドレス制御部２０は最終アドレスメモリ８０のアド
レス「ｔ」のデータを読み出す。するとデータ「１８」
が得られるため、書き込みアドレス制御部２０は最後の
セルがセルメモリ１０のアドレス「１８」に保存されて
いることを認識する。

【００３８】次に、書き込みアドレス制御部２０はアド
レスチェーンメモリ５０のアドレス「１０」（先頭メモ
リアドレス７０のデータ）を読み出す。するとデータ
「２５」が得られるため、書き込みアドレス制御部２０
は２番目のセルがセルメモリ１０のアドレス「２５」に
保存されていることを認識する。

【００３９】同様に書き込みアドレス制御部２０はアド
レスチェーンメモリ５０のアドレス「２５」を読み出
す。するとデータ「１８」が得られるため、書き込みア
ドレス制御部２０は３番目のセルがセルメモリ１０のア
ドレス「１８」に保存されていることを認識する。しか
も、この「１８」という値は、最終アドレスメモリ８０
の値「１８」と一致しているため、書き込みアドレス制
御部２０はこのセルが、理想送出時刻「ｔ」の最後のセ
ルであることを認識する。

【００４０】以上より、アドレス制御部２０は理想送出
時刻「ｔ」にはセルメモリアドレス１０、２５、１８の
３つのセルが存在していることを認識する。

【００４１】図３は図２の場合のアドレスチェーンメモ
リ５０、セル存在有無メモリ６０、先頭アドレスメモリ
７０および最終アドレスメモリ８０のアドレスとデータ
の関係を示した構成図である。図３に示すようにアドレ
スチェーンメモリ５０は、セルメモリ１０と同一のアド
レス数が必要であり、セル存在有無メモリ６０、先頭ア
ドレスメモリ７０、最終アドレスメモリ８０は、理想送
出時刻と同一の数だけアドレスが必要である。

【００４２】しかし、本メモリ構成はシェーピング装置
で遅延させる量および入力されるパス数には依存せず、
図２０に示した従来のＦＩＦＯ型競合制御回路と違っ
て、理想送出時刻毎にＦＩＦＯメモリを持つ必要がな
く、またパス数分の容量のＦＩＦＯメモリを持つ必要も
ないので、メモリ容量が大幅に削減されるという効果を
奏する。

【００４３】次に、セル書き込み時の処理について詳細
に説明する。セル書き込み時は、書き込みアドレス制御
部２０、空きアドレスメモリ４０、アドレスチェーンメ
モリ５０、セル存在有無メモリ６０、先頭アドレスメモ
リ７０、最終アドレスメモリ８０により処理を行う。図
４は競合制御回路の書き込み制御に関する部分について
の動作を示す説明図である。

【００４４】図４において、書き込みアドレス制御部２
０は空きアドレスメモリ４０からセルメモリ１０の空き
アドレスを入力し、その空きアドレスを書き込みアドレ
スとしてセルメモリ１０に出力する。また理想送出時刻
が入力されると、その値をアドレスとし、セル存在有無
メモリ６０、先頭アドレスメモリ７０、最終アドレスメ
モリ８０にアクセスする。また最終アドレスメモリ８０
からリードした値をアドレスとしてアドレスチェーンメ
モリ５０にアクセスする。

【００４５】図５はこの実施の形態のセル書き込み時の
処理を示す説明図である。図５は図２の状態で理想送出
時刻「ｔ」のセルが到着した場合を想定している。この
とき、書き込みアドレス制御部２０は空きアドレスメモ
リ４０から空きアドレス「３１」を読み出すことによ
り、到着セルをセルメモリ１０の当該アドレス「３１」
にライトする（図示せず）。一方、書き込みアドレス制
御部２０はセル存在有無メモリ６０のアドレス「ｔ」を
読み出し、データが「１」であることから、既に理想送
出時刻「ｔ」には、送出すべきセルが存在していること
を認識する。

【００４６】そこで書き込みアドレス制御部２０は最終
アドレスメモリ８０のアドレス「ｔ」を読み出し、デー
タが「１８」であることから、アドレスチェーンメモリ
５０の当該アドレス「１８」にデータ「３１」をライト
する。また、最終アドレスメモリ８０のアドレス「ｔ」
のデータを「１８」から「３１」に変更する。

【００４７】また、図６は、この実施の形態のセル書き
込み時の処理を示す別の説明図であり、図２の状態で理
想送出時刻「ｔ＋１」のセルが到着した場合を想定して
いる。次に、図６の動作を説明する。理想送出時刻「ｔ
＋１」のセルが到着すると、書き込みアドレス制御部２
０は図５のときと同様に空きアドレスメモリ４０から空
きアドレス「３１」を読み出すことにより、到着セルを
セルメモリ１０の当該アドレス「３１」にライトする。

【００４８】一方、書き込みアドレス制御部２０はセル
存在有無メモリ６０のアドレス「ｔ＋１」を読み出し、
データが「０」であることから、到着セルは、その理想
送出時刻における最初のセルであると認識する。そこ
で、書き込みアドレス制御部２０はセル存在有無メモリ
６０のアドレス「ｔ＋１」に「１」をライトするととも
に、この場合、セルメモリ１０のアドレス「ｔ＋１」に
は１つのデータしかないので、先頭アドレスメモリ７０
と最終アドレスメモリ８０のアドレス「ｔ＋１」に、空
きアドレスメモリ４０から読み出した「３１」をライト
する。

【００４９】次に、セル読み出し時の処理について詳細
に説明する。セル読み出し時は、図１に示す読み出しア
ドレス制御部３０、空きアドレスメモリ４０、アドレス
チェーンメモリ５０、セル存在有無メモリ６０、先頭ア
ドレスメモリ７０、最終アドレスメモリ８０により処理
を行う。図７はこの実施の形態の読み出しアドレス制御
部３０と空きアドレスメモリ４０、アドレスチェーンメ
モリ５０、セル存在有無メモリ６０、先頭アドレスメモ
リ７０、最終アドレスメモリ８０との詳細な接続関係を
示す構成図である。

【００５０】図７において、読み出しアドレス制御部３
０は内部に継続読み出しか否かの識別に使われる継続読
み出しフラグレジスタ９０と、継続の場合の次回のアド
レスを保存している継続次回アドレスレジスタ１００と
継続の場合の最終アドレスを保存している継続最終アド
レスレジスタ１１０を持つ。読み出しアドレス制御部３
０はセルメモリ１０への読み出しアドレスを出力し、か
つ空きアドレスメモリ４０へも読み出しアドレスを空き
アドレスとして出力して、空きアドレスメモリ４０に書
き込む。

【００５１】また現在時刻が入力されると、その値をア
ドレスとし、セル存在有無メモリ６０、先頭アドレスメ
モリ７０、最終アドレスメモリ８０にアクセスする。ま
た先頭アドレスメモリ７０からリードした値あるいは継
続次回アドレスレジスタ１００の値あるいは継続最終ア
ドレスレジスタ１１０の値をアドレスとしてアドレスチ
ェーンメモリ５０にアクセスする。

【００５２】図８はこの実施の形態のセル読み出し時の
処理を示す説明図である。次に、図８の動作を説明す
る。図８において、現在時刻が「ｔ」となると、読み出
しアドレス制御部３０はまず継続読み出しフラグレジス
タ９０の値をリードする。すると、データ「０」を得る
ので、読み出しアドレス制御部３０は継続でないと認識
する。そこで、読み出しアドレス制御部３０はセル存在
有無メモリ６０のアドレス「ｔ」をリードする。する
と、データ「１」が得られるので、読み出しアドレス制
御部３０は現在時刻「ｔ」と一致する理想送出時刻
「ｔ」に送出すべきセルが存在していることを認識す
る。

【００５３】そこで、読み出しアドレス制御部３０は先
頭アドレスメモリ７０のアドレス「ｔ」からデータ「１
０」をリードする。次に、読み出しアドレス制御部３０
はこのデータ「１０」をアドレスとして、セルメモリ１
０からセルを読み出して出力する。次に、セルメモリ１
０のアドレス「１０」はセルの読み出しが完了して空き
になったので、読み出しアドレス制御部３０は空きアド
レスメモリ４０に読み出したアドレスの「１０」をライ
ト（追加）する。

【００５４】一方、最終アドレスメモリ８０のアドレス
「ｔ」にアクセスし、データ「３１」をリードする。こ
の値は、先頭アドレスメモリ７０からリードした「１
０」と異なるため、読み出しアドレス制御部３０は、理
想送出時刻「ｔ」に送出すべきセルが２セル以上あると
判断する。この場合、現在時刻が「ｔ＋１」になったと
きにも、理想送出時刻「ｔ」のセルを継続して送出する
必要がある。

【００５５】このように、過去の理想送出時刻のセルを
読み出す状態のことを、本明細書では「継続読み出し状
態」と定義する。時刻「ｔ」において、読み出しアドレ
ス制御部３０は次の時刻以降が継続読み出し状態である
ことを認識すると、継続読み出しフラグレジスタ９０に
「１」をライトする。また、読み出しアドレス制御部３
０は、アドレスチェーンメモリ５０のアドレス「１０」
（先頭アドレスメモリ７０の値）からデータ「２５」を
リードする。

【００５６】次に、読み出しアドレス制御部３０は、継
続次回アドレスレジスタ１００に当該データ「２５」を
ライトし、継続最終アドレスレジスタ１１０に「３１」
（最終アドレスメモリ８０の値）をライトする。そし
て、時刻「ｔ」のセルメモリ１０からのセルの読み出し
は完了したので、セル存在有無メモリ６０のアドレス
「ｔ」に「０」をライトする。

【００５７】図９は図８の時刻が１つ進んだ状態でのセ
ル読み出し時の処理を示す説明図であり、現在時刻が
「ｔ＋１」のときについて示したものである。次に、図
９の動作を説明する。現在時刻が「ｔ＋１」になると、
読み出しアドレス制御部３０はまず、継続読み出しフラ
グレジスタ９０の値をリードし、その値が「１」である
ので、時刻「ｔ＋１」において継続読み出し状態である
と認識する。

【００５８】そこで、読み出しアドレス制御部３０は継
続次回アドレスレジスタ１００のデータ「２５」をリー
ドし、このデータ「２５」をアドレスとしてセルメモリ
１０からセルを読み出して出力する。次に、セルメモリ
１０のアドレス「２５」はセルの読み出しが完了して空
きになったので、読み出しアドレス制御部３０は空きア
ドレスメモリ４０に読み出したアドレスの「２５」をラ
イト（追加）する。

【００５９】次に、読み出しアドレス制御部３０は継続
最終アドレスレジスタ１１０からデータ「３１」をリー
ドする。このデータ「３１」は、継続次回アドレスレジ
スタ１００のデータ「２５」と異なるため、読み出しア
ドレス制御部３０は次の時刻「ｔ＋２」になっても、継
続読み出し状態のままであると判断する。そこで、読み
出しアドレス制御部３０はこのデータ「２５」をアドレ
スとしてアドレスチェーンメモリ５０からデータ「１
８」をリードし、この値「１８」を継続次回アドレスレ
ジスタ１００にライトする。

【００６０】一方、読み出しアドレス制御部３０はセル
存在有無メモリ６０の現在時刻アドレス「ｔ＋１」のデ
ータをリードする。すると、データ「０」が得られるの
で、読み出しアドレス制御部３０は理想送出時刻「ｔ＋
１」のセルが存在しないことを認識し、時刻「ｔ＋１」
のときにおける処理を終了する。

【００６１】図１０は図９の時刻がさらに１つ進んだ状
態でのセル読み出し時の処理を示す説明図であり、現在
時刻が「ｔ＋２」のときについて示したものである。読
み出しアドレス制御部３０は、まず継続読み出しフラグ
レジスタ９０の値をリードする。すると、データ「１」
が得られるので、読み出しアドレス制御部３０は時刻
「ｔ＋２」においても継続読み出し状態であることを認
識する。

【００６２】そこで、読み出しアドレス制御部３０は継
続次回アドレスレジスタ１００のデータ「１８」をリー
ドし、このデータ「１８」をアドレスとしてセルメモリ
１０からセルを読み出して出力する。次に、セルメモリ
１０のアドレス「１８」はセルの読み出しが完了して空
きになったので、読み出しアドレス制御部３０は空きア
ドレスメモリ４０に読み出したアドレスの「１８」をラ
イト（追加）する。

【００６３】次に、読み出しアドレス制御部３０は継続
最終アドレスレジスタ１１０からデータ「３１」をリー
ドする。このデータ「３１」は継続次回アドレスレジス
タ１００のデータ「１８」と異なるため、読み出しアド
レス制御部３０は次の時刻「ｔ＋３」になっても、継続
読み出し状態のままであると判断する。そこで、読み出
しアドレス制御部３０はこのデータ「１８」をアドレス
として、アドレスチェーンメモリ５０からデータ「３
１」をリードし、その値「３１」を継続次回アドレスレ
ジスタ１００にライトする。

【００６４】一方、読み出しアドレス制御部３０はセル
存在有無メモリ６０の現在時刻アドレス「ｔ＋２」のデ
ータをリードする。すると、データ「１」が得られるの
で、読み出しアドレス制御部３０は理想送出時刻「ｔ＋
２」のセルが存在することを認識する。そのため、将
来、理想送出時刻が「ｔ」のセルをすべて読み出し終わ
った後、理想送出時刻「ｔ＋２」のセルを引き続き読み
出す必要がある。この情報は次のようにアドレスチェー
ンを接続することで保持される。

【００６５】読み出しアドレス制御部３０は先頭アドレ
スメモリ７０のアドレス「ｔ＋２」からデータ「１３」
をリードする。次に、読み出しアドレス制御部３０は継
続最終アドレスレジスタ１１０の値である「３１」をア
ドレスとして、アドレスチェーンメモリ５０にデータ
「１３」をライトする。また、読み出しアドレス制御部
３０は最終アドレスメモリ８０のアドレス「ｔ＋２」か
らデータ「１５」をリードする。

【００６６】次に、読み出しアドレス制御部３０は継続
最終アドレスレジスタ１１０に上記データ「１５」をラ
イトする。これにより、理想送出時刻「ｔ」と「ｔ＋
２」のセルのアドレスチェーンが接続されることにな
る。そして、最後にセル存在有無メモリのアドレス「ｔ
＋２」にデータ「０」をライトする。

【００６７】以上述べた制御を行うことでＦＩＦＯ型競
合制御を実現することができる。本実施の形態を用いれ
ば、収容パス数分の深さを持つＦＩＦＯメモリを理想送
出時刻分持つ必要がなく、１つのセルメモリと５個の制
御用メモリを用いるだけで良く、回路規模を大幅に削減
することができる。

【００６８】実施の形態２．図１１はこの発明に係る競
合制御回路の別の実施の形態を示す構成図である。図１
１において、図１と同符号は同一または相当部分を示
す。１２０は入力セルのヘッダに含まれるＶＰＩ／ＶＣ
Ｉを取り出すヘッダ識別部、１３０はＶＰＩ／ＶＣＩ毎
の遅延優先度を記録した遅延優先情報メモリである。本
実施の形態では遅延クラスは２クラスを想定しており、
遅延優先情報メモリ１３０はＶＰＩ／ＶＣＩ毎に遅延優
先情報１ビットを保存している。そして、入力セルのＶ
ＰＩ／ＶＣＩに応じて、遅延優先情報を書き込みアドレ
ス制御部２０に出力する。本明細書では、遅延優先情報
が「１」のとき遅延に対して厳しいパス、「０」のとき
遅延に対して厳しくないパスを意味することとする。

【００６９】また、図１１において、ヘッダ識別部１２
０と遅延優先情報メモリ１３０が追加された以外は図１
と同一であり、書き込みアドレス制御部２０、読み出し
アドレス制御部３０と空きアドレスメモリ４０、アドレ
スチェーンメモリ５０、セル存在有無メモリ６０、先頭
アドレスメモリ７０、最終アドレスメモリ８０との接続
関係は図４、図７と同一である。

【００７０】次に、この実施の形態の動作を説明する。
セル読み出し時の処理動作は実施の形態１と同一であ
る。異なる点は、セル書き込み時の処理動作である。入
力セルの遅延優先情報が「０」、すなわち遅延に対して
厳しくないパスの場合は理想送出時刻毎に設けられたア
ドレスチェーンの最後尾に追加し、遅延優先情報が
「１」、すなわち遅延に対して厳しいパスの場合は理想
送出時刻毎のアドレスチェーンの先頭に追加する。この
点が、実施の形態１と異なるところである。

【００７１】図１２はこの実施の形態におけるセル書き
込み時の動作を示す説明図である。図１２は図２の状態
で理想送出時刻「ｔ」のセルが到着した場合の動作を示
す。このとき、書き込みアドレス制御部２０は空きアド
レスメモリ４０から空きアドレス「３１」を読み出すこ
とにより、到着セルをセルメモリ１０の当該空きアドレ
ス「３１」にライトする。一方、書き込みアドレス制御
部２０はセル存在有無メモリ６０のアドレス「ｔ」を読
み出す。すると、データ「１」が得られるので、書き込
みアドレス制御部２０は既に理想送出時刻「ｔ」には、
送出すべき他のセルが存在していると認識する。

【００７２】ここで、書き込みアドレス制御部２０は遅
延優先情報が１（即ち遅延に対して厳しいパス）のとき
は先頭アドレスメモリ７０のアドレス「ｔ」を読み出
す。すると、データ「１０」が得られるので、書き込み
アドレス制御部２０はアドレスチェーンメモリ５０のア
ドレス「３１」に当該データ「１０」をライトする。ま
た、先頭アドレスメモリ７０のアドレス「ｔ」に、上記
データ「３１」をライトする。これにより、理想送出時
刻「ｔ」のセル４個の中で、現在到着したセルが最初に
出力されることになる。

【００７３】従って、理想送出時刻「ｔ」とのずれを小
さく出力することができる。

【００７４】一方、遅延優先情報が０（即ち遅延に対し
て厳しくないパス）のときは、実施の形態１と同じく、
書き込みアドレス制御部２０は最終アドレスメモリ８０
のアドレス「ｔ」を読み出す。すると、データ「１８」
が得られるので、書き込みアドレス制御部２０はアドレ
スチェーンメモリ５０の当該アドレス「１８」にデータ
「３１」をライトする。また、最終アドレスメモリ８０
のアドレス「ｔ」に、上記データ「３１」をライトす
る。これにより、理想送出時刻「ｔ」のセル４個の中
で、現在到着したセルが最後に出力されることになる。

【００７５】以上のように、セル書き込み時に、そのセ
ルの遅延優先情報に基き、アドレスチェーンを接続する
ことにより、実施の形態１と比べて遅延に対して厳しい
パスについて、理想送出時刻とのずれを小さく出力する
ことができるという効果がある。

【００７６】実施の形態３．また、図１３はこの発明に
係る競合制御回路の別の実施の形態を示す構成図であ
る。図１３の構成は実施の形態２における図１２の構成
とほぼ同じであるが、セル存在有無メモリ６０、先頭ア
ドレスメモリ７０、最終アドレスメモリ８０の構成が実
施の形態１、２と異なる。図１４は図１３に示すセル存
在有無メモリ６０、先頭アドレスメモリ７０、最終アド
レスメモリ８０の構成を示す構成図であり、同時に内容
を示している。

【００７７】また、各メモリに保存するデータの内容は
実施の形態１、２とほぼ同一であるが、データを遅延優
先クラス毎に持つ点が異なる。従って、セル存在有無メ
モリ６０、先頭アドレスメモリ７０、最終アドレスメモ
リ８０のメモリ容量は、図３のメモリ構成と比べればわ
かるように、実施の形態１および２の時の２倍となる。
ただし、セルメモリ１０、空きアドレスメモリ４０、ア
ドレスチェーンメモリ５０のメモリ容量は実施の形態
１、２と同一で良い。

【００７８】なお、図１４では、セル存在有無メモリ６
０、先頭アドレスメモリ７０、最終アドレスメモリ８０
のデータ幅を図３の場合の２倍に増やして実現している
が、遅延優先クラス毎の別々のメモリにしてもよいし、
データ幅は図３の場合と同じで、アドレス数を２倍にし
遅延優先クラスに応じてアドレスを変えることにより実
現しても良い。

【００７９】図１５は実施の形態３におけるセル書き込
み時の処理を示す説明図である。図１５は図２の状態で
理想送出時刻「ｔ」のセルが到着した場合である。図１
５においては図２と異なり遅延優先クラスを意識した制
御となっているため、理想送出時刻「ｔ」と「ｔ＋２」
に対応するセルのうち、セルメモリ１０に保存されてい
るアドレス「１８」と「１５」のセルは遅延に対して厳
しいパス、アドレス「１０」と「２５」と「１３」のセ
ルは遅延に対して厳しくないパスと想定している。

【００８０】なお、図１５のアドレスチェーンメモリ５
０において、各時刻毎に遅延優先クラス１に対応するデ
ータを左に、遅延優先クラス０に対応するデータを右に
示しているが、実際にはアドレスチェーンメモリ５０は
理想送出時刻毎、あるいは遅延優先クラス毎に分かれて
いるわけではなく、実施の形態１および２と同じく、セ
ルメモリ１０のアドレス毎にデータを持つ構成になって
いる。

【００８１】次に、この実施の形態の動作を説明する。
理想送出時刻「ｔ」のセルが到着すると、書き込みアド
レス制御部２０は空きアドレスメモリ４０から空きアド
レス「３１」を読み出し、到着セルをセルメモリ１０の
当該空きアドレス「３１」にライトする。

【００８２】一方、書き込みアドレス制御部２０はセル
存在有無メモリ６０のアドレス「ｔ」の、到着セルに対
応する上記遅延クラスのデータを読み出し、そのデータ
の値に応じて、先頭アドレスメモリ７０、最終アドレス
メモリ８０、アドレスチェーンメモリ５０の、到着セル
に対応する遅延クラスのデータ領域にアクセスする。ア
クセス方法は実施の形態１と同様である。

【００８３】例えば、遅延優先クラスが「１」のセルが
到着した場合、書き込みアドレス制御部２０はセル存在
有無メモリ６０のアドレス「ｔ」の遅延優先クラスが１
のデータを読み出す。すると、データ「１」が得られる
ので、最終アドレスメモリ８０のアドレス「ｔ」の遅延
優先クラスが１のデータを読み出す。すると、データ
「１８」が得られるので、書き込みアドレス制御部２０
はアドレスチェーンメモリ５０の当該アドレス「１８」
に、空きアドレスメモリから読み出したデータ「３１」
をライトする。そして書き込みアドレス制御部２０は最
終アドレスメモリ８０のアドレス「ｔ」の遅延優先クラ
スが１の領域に、データ「３１」をライトする。

【００８４】遅延優先情報が「０」のときも同様であ
る。

【００８５】次にセル読み出し時の動作について説明す
る。図１６、図１７、図１８にそれぞれ時刻「ｔ」、
「ｔ＋１」、「ｔ＋２」におけるセル読み出し時の空き
アドレスメモリ４０、アドレスチェーンメモリ５０、セ
ル存在有無メモリ６０、先頭アドレスメモリ７０、最終
アドレスメモリ８０、継続読み出しフラグレジスタ９
０、継続次回アドレスレジスタ１００、継続最終アドレ
スレジスタ１１０のデータ内容を示す。

【００８６】図１６は実施の形態３におけるセル読み出
し時の処理を示す説明図である。なお時刻「ｔ−１」で
はセルメモリ１０から読み出すセルがない場合を想定し
ている。また理想送出時刻「ｔ」と「ｔ＋２」に対応す
るセルのうち、セルメモリ１０に保存されているアドレ
ス「１８」と「３１」と「１５」のセルは遅延に対して
厳しいパス、アドレス「１０」と「２５」と「１３」の
セルは遅延に対して厳しくないパスと想定している。

【００８７】次に、現在時刻「ｔ」における動作を図１
６を用いて説明する。現在時刻が「ｔ」になると、読み
出しアドレス制御部３０は、まず継続読み出しフラグレ
ジスタ９０からデータを読み出す。すると、データ
「０」が得られるので、読み出しアドレス制御部３０は
継続読み出し中でないことを認識する。次に、読み出し
アドレス制御部３０はセル存在有無メモリ６０のアドレ
ス「ｔ」を読み出す。すると、遅延優先クラス「１」，
「０」のデータがともに「１」が得られるので、読み出
しアドレス制御部３０は遅延優先クラス「１」，「０」
ともにセルが存在していると認識する。

【００８８】この場合、少なくとも２個のセルが存在し
ていることとなるため、読み出しアドレス制御部３０は
継続読み出しフラグレジスタ９０に「１」をライトす
る。次に、読み出しアドレス制御部３０は先頭アドレス
メモリ７０のアドレス「ｔ」の遅延優先クラス「１」の
データ「１８」をリードする。そして、セルメモリ１０
から当該アドレス「１８」のセルを読み出し、伝送路上
に出力する。次に、セルメモリ１０のアドレス「１８」
はセルの読み出しが完了して空きになったので、読み出
しアドレス制御部３０は空きアドレスメモリ４０に読み
出したアドレスの「１８」をライト（追加）する。

【００８９】次に、読み出しアドレス制御部３０は最終
アドレスメモリ８０のアドレス「ｔ」の遅延優先クラス
「１」のデータ「３１」をリードし、先頭アドレスメモ
リ７０のアドレス「ｔ」の遅延優先クラス「０」のデー
タ「１０」をリードする。そして、読み出しアドレス制
御部３０はアドレスチェーンメモリ５０の上記アドレス
「３１」に当該データ「１０」をライトする。

【００９０】また、読み出しアドレス制御部３０はアド
レスチェーンメモリ５０のアドレス「１８」のデータ
「３１」をリードし、継続次回アドレスレジスタ１００
に当該データ「３１」をライトする。次に、読み出しア
ドレス制御部３０は最終アドレスメモリ８０のアドレス
「ｔ」の遅延優先クラス「０」のデータ「２５」をリー
ドし、継続最終アドレスレジスタ１１０に当該データ
「２５」をライトする。以上が時刻「ｔ」における動作
である。

【００９１】図１７は図１６の時刻が１つ進んだ状態で
のセル読み出し時の処理を示す説明図である。次に、現
在時刻「ｔ＋１」のときの動作を図１７を用いて説明す
る。現在時刻が「ｔ＋１」になると、読み出しアドレス
制御部３０はまず継続読み出しフラグレジスタ９０から
データを読み出す。すると、データ「１」が得られるの
で、読み出しアドレス制御部３０は継続読み出し中であ
ることを認識する。

【００９２】そこで、読み出しアドレス制御部３０は継
続次回アドレスレジスタ１００のデータ「３１」をリー
ドする。次に、読み出しアドレス制御部３０はこのデー
タ「３１」をアドレスとして、セルメモリ１０からセル
を読み出し、伝送路上に出力する。次に、セルメモリ１
０のアドレス「３１」はセルの読み出しが完了して空き
になったので、読み出しアドレス制御部３０は空きアド
レスメモリ４０に読み出したアドレスの「３１」をライ
ト（追加）する。

【００９３】次に、読み出しアドレス制御部３０はセル
存在有無メモリ６０のアドレス「ｔ＋１」を読み出し、
遅延優先クラス「１」，「０」のデータがともに「０」
であることにより、読み出しアドレス制御部３０はセル
メモリ１０には理想送出時刻「ｔ＋１」のセルが存在し
ないことを認識する。

【００９４】そこで、読み出しアドレス制御部３０は継
続最終アドレスレジスタ１１０のデータ「２５」をリー
ドし、このデータ「２５」が、継続次回アドレスレジス
タ１００のデータ「３１」と異なるため、継続読み出し
レジスタ９０の値は「１」のままに設定する。次に、読
み出しアドレス制御部３０はアドレスチェーンメモリ５
０のアドレス「３１」のデータ「１０」をリードし、継
続次回アドレスレジスタ１００にデータ「１０」をライ
トする。以上が時刻「ｔ＋１」における動作である。

【００９５】また、図１８は図１７の時刻がさらに１つ
進んだ状態でのセル読み出し時の処理を示す説明図であ
る。次に、現在時刻「ｔ＋２」のときの動作を図１８を
用いて説明する。現在時刻が「ｔ＋２」になると、読み
出しアドレス制御部３０はまず継続読み出しフラグレジ
スタ９０からデータを読み出す。すると、データ「１」
が得られるので、読み出しアドレス制御部３０は継続読
み出し中であることを認識する。

【００９６】そこで、読み出しアドレス制御部３０は継
続次回アドレスレジスタ１００のデータ「１０」をリー
ドする。次に、読み出しアドレス制御部３０はこのデー
タ「１０」をアドレスとしてセルメモリ１０からセルを
読み出し、伝送路上に出力する。次に、セルメモリ１０
のアドレス「１０」はセルの読み出しが完了して空きに
なったので、読み出しアドレス制御部３０は空きアドレ
スメモリ４０に読み出したアドレスの「１０」をライト
（追加）する。

【００９７】次に、読み出しアドレス制御部３０はアド
レスチェーンメモリ５０のアドレス「１０」のデータ
「２５」をリードし、継続次回アドレスレジスタ１００
に当該データ「２５」をライトする。

【００９８】次に、読み出しアドレス制御部３０はセル
存在有無メモリ６０のアドレス「ｔ＋２」を読み出す。
すると、遅延優先クラス「１」，「０」のデータがとも
に「１」が得られるので、読み出しアドレス制御部３０
は遅延優先クラス「１」，「０」ともに理想送出時刻
「ｔ＋２」のセルが存在していることを認識する。そこ
で、以下のようにアドレスチェーンを接続し直す。

【００９９】読み出しアドレス制御部３０は継続最終ア
ドレスレジスタ１１０のデータ「２５」をリードし、さ
らに先頭アドレスメモリ７０のアドレス「ｔ＋２」の遅
延優先クラス「１」のデータ「１５」をリードする。そ
して、読み出しアドレス制御部３０はアドレスチェーン
メモリ５０の上記アドレス「２５」に当該データ「１
５」をライトする。さらに、読み出しアドレス制御部３
０は最終アドレスメモリ８０のアドレス「ｔ＋２」の遅
延優先クラス「０」のデータ「１３」をリードし、継続
最終アドレスレジスタ１１０に当該データ「１３」をラ
イトする。

【０１００】次に、読み出しアドレス制御部３０は最終
アドレスメモリ８０のアドレス「ｔ＋２」の遅延優先ク
ラス「１」のデータ「１５」をリードし、また、先頭ア
ドレスメモリ７０のアドレス「ｔ＋２」の遅延優先クラ
ス「０」のデータ「１３」をリードする。そして、アド
レスチェーンメモリ５０のアドレス「１５」にデータ
「１３」をライトする。以上が時刻「ｔ＋２」における
動作である。

【０１０１】以上のような動作を行うことにより、実施
の形態２とは異なり、各理想送出時刻について、遅延優
先クラスが低いものは、優先クラスが高いものよりも必
ず後に出力することができる。

【０１０２】また、アドレス管理用のメモリ容量は実施
の形態１、２と比べると多くなるが、メモリ容量の大き
いセルメモリ１０の容量は実施の形態１、２と変わら
ず、個別にＦＩＦＯメモリを設けるよりは回路規模を小
さく実現できる。

【０１０３】また、本例は遅延クラスが２クラスの場合
について示したが、遅延クラスが複数になっても、セル
存在有無メモリ６０、先頭アドレスメモリ７０、最終ア
ドレスメモリ８０のデータ領域を遅延クラス数分設け、
２クラスの場合と同様の処理を行うことにより、遅延優
先クラスが低いものは、優先クラスが高いものよりも必
ず後に出力することができる。

【０１０４】

【発明の効果】この発明によれば、セルを保存するセル
メモリと、セルメモリの空きアドレスを管理する空きア
ドレスメモリと、セルメモリの書き込みアドレスを制御
する書き込みアドレス制御部と、セルメモリの読み出し
アドレスを制御する読み出しアドレス制御部と、セルメ
モリのセルの読み出し順序を管理するアドレスチェーン
メモリと、理想送出時刻毎にセルが存在するかどうかの
情報を持つセル存在有無メモリと、理想送出時刻毎に最
初に出力すべきセルが保存されているセルメモリのアド
レスを記録する先頭アドレスメモリと、理想送出時刻毎
に最後に出力すべきセルが保存されているセルメモリの
アドレスを記録する最終アドレスメモリと、を備えたの
で、収容パス数分の深さを持つＦＩＦＯメモリを理想送
出時刻分持つ必要がなく、１つのセルメモリと５個の制
御用メモリを用いるだけで良く、回路規模を大幅に削減
することができるという効果を奏する。

【０１０５】また、この発明によれば、セルメモリの空
きアドレスを管理する空きアドレスメモリと、セルメモ
リの書き込みアドレスを制御する書き込みアドレス制御
部と、セルメモリの読み出しアドレスを制御する読み出
しアドレス制御部と、セルメモリのセルの読み出し順序
を管理するアドレスチェーンメモリと、理想送出時刻毎
にセルが存在するかどうかの情報を持つセル存在有無メ
モリと、理想送出時刻毎に最初に出力すべきセルが保存
されているセルメモリのアドレスを記録する先頭アドレ
スメモリと、理想送出時刻毎に最後に出力すべきセルが
保存されているセルメモリのアドレスを記録する最終ア
ドレスメモリと、入力セルのヘッダに含まれる識別子を
取り出すヘッダ識別部と、識別子毎の遅延優こクラスを
記録した遅延優先情報メモリとを備え、前記遅延優先ク
ラスは２クラスであり、セル存在有無メモリと先頭アド
レスメモリと最終アドレスメモリは、遅延優先クラス毎
にデータを保持しており、入力セルの遅延優先クラスに
応じて書き込みアドレスを制御する手段を備えたので、
セル書き込み時に、そのセルの遅延優先情報に基き、ア
ドレスチェーンを接続することにより、実施の形態１と
比べて遅延に対して厳しいパスについて、理想送出時刻
とのずれを小さく出力することができるという効果を奏
する。

【０１０６】また、この発明によれば、セルを保存する
セルメモリと、セルメモリの空きアドレスを管理する空
きアドレスメモリと、セルメモリの書き込みアドレスを
制御する書き込みアドレス制御部と、セルメモリの読み
出しアドレスを制御する読み出しアドレス制御部と、セ
ルメモリのセルの読み出し順序を管理するアドレスチェ
ーンメモリと、理想送出時刻毎にセルが存在するかどう
かの情報を持つセル存在有無メモリと、理想送出時刻毎
に最初に出力すべきセルが保存されているセルメモリの
アドレスを記録する先頭アドレスメモリと、理想送出時
刻毎に最後に出力すべきセルが保存されているセルメモ
リのアドレスを記録する最終アドレスメモリと、入力セ
ルのヘッダに含まれる識別子を取り出すヘッダ識別部
と、識別子毎の遅延優先クラスを記録した遅延優先情報
メモリとを備え、前記遅延優先クラスは２クラスであ
り、セル存在有無メモリと先頭アドレスメモリと最終ア
ドレスメモリは、遅延優先クラス毎にデータを保持して
おり、入力セルの遅延優先クラスに応じて書き込みアド
レスを制御する手段を備えたので、各理想送出時刻につ
いて、遅延優先クラスが低いものは、優先クラスが高い
ものよりも必ず後に出力するようにできるという効果を
奏する。

【０１０７】また、この発明によれば、セルを保存する
セルメモリと、セルメモリの空きアドレスを管理する空
きアドレスメモリと、セルメモリの書き込みアドレスを
制御する書き込みアドレス制御部と、セルメモリの読み
出しアドレスを制御する読み出しアドレス制御部と、セ
ルメモリのセルの読み出し順序を管理するアドレスチェ
ーンメモリと、理想送出時刻毎にセルが存在するかどう
かの情報を持つセル存在有無メモリと、理想送出時刻毎
に最初に出力すべきセルが保存されているセルメモリの
アドレスを記録する先頭アドレスメモリと、理想送出時
刻毎に最後に出力すべきセルが保存されているセルメモ
リのアドレスを記録する最終アドレスメモリと、入力セ
ルのヘッダに含まれる識別子を取り出すヘッダ識別部
と、識別子毎の遅延優先クラスを記録した遅延優先情報
メモリとを備え、前記遅延優先クラスは３クラス以上で
あり、セル存在有無メモリと先頭アドレスメモリと最終
アドレスメモリは、遅延優先クラス毎にデータを保持し
ており、入力セルの遅延優先クラスに応じて書き込みア
ドレスを制御する手段を備えたので、遅延クラスが複数
になっても、セル存在有無メモリ６０、先頭アドレスメ
モリ７０、最終アドレスメモリ８０のデータ領域を遅延
クラス数分設け、２クラスの場合と同様の処理を行うこ
とにより、遅延優先クラスが低いものは、優先クラスが
高いものよりも必ず後に出力するようにできるという効
果を奏する。

【図面の簡単な説明】

【図１】 この発明に係る競合制御回路の１実施の形態
を示す構成図である。

【図２】 図２２の従来のＦＩＦＯに相当する情報の保
持方法を示した説明図である。

【図３】 図２の場合のアドレスチェーンメモリ５０、
セル存在有無メモリ６０、先頭アドレスメモリ７０、最
終アドレスメモリ８０のアドレスとデータの関係を示し
た構成図である。

【図４】 競合制御回路の書き込み制御に関する部分に
ついての動作を示す説明図である。

【図５】 この発明の実施の形態１のセル書き込み時の
処理を示す説明図である。

【図６】 この発明の実施の形態１のセル書き込み時の
処理を示す別の説明図である。

【図７】 この発明の実施の形態１の読み出しアドレス
制御部３０と空きアドレスメモリ４０、アドレスチェー
ンメモリ５０、セル存在有無メモリ６０、先頭アドレス
メモリ７０、最終アドレスメモリ８０との詳細な接続関
係を示す構成図である。

【図８】 この発明の実施の形態１のセル読み出し時の
処理を示す説明図である。

【図９】 図８の時刻が１つ進んだ状態でのセル読み出
し時の処理を示す説明図である。

【図１０】 図９の時刻がさらに１つ進んだ状態でのセ
ル読み出し時の処理を示す説明図である。

【図１１】 この発明に係る競合制御回路の別の実施の
形態を示す構成図である。

【図１２】 この発明の実施の形態２におけるセル書き
込み時の動作を示す説明図である。

【図１３】 この発明に係る競合制御回路の別の実施
の形態を示す構成図である。

【図１４】 図１３に示すセル存在有無メモリ６０、先
頭アドレスメモリ７０、最終アドレスメモリ８０の構成
を示す構成図である。

【図１５】 この発明の実施の形態３におけるセル書き
込み時の処理を示す説明図である。

【図１６】 この発明の実施の形態３におけるセル読み
出し時の処理を示す説明図である。

【図１７】 図１６の時刻が１つ進んだ状態でのセル読
み出し時の処理を示す説明図である。

【図１８】 図１７の時刻がさらに１つ進んだ状態での
セル読み出し時の処理を示す説明図である。

【図１９】 従来の競合制御の動作を示す説明図であ
る。

【図２０】 従来の競合制御回路が含まれるシェーピン
グ装置の構成図である。

【図２１】 従来のＦＩＦＯ型競合制御の動作を示す説
明図である。

【図２２】 図２１に示す従来のＦＩＦＯ型競合制御を
実現するための構成図である。

【符号の説明】

１０ セルメモリ ２０ 書き込みアドレス制御部 ３０ 読み出しアドレス制御部 ４０ 空きアドレスメモリ ５０ アドレスチェーンメモリ ６０ セル存在有無メモリ ７０ 先頭アドレスメモリ ８０ 最終アドレスメモリ ９０ 継続読み出しフラグレジスタ １００ 継続次回アドレスレジスタ １１０ 継続最終アドレスレジスタ １２０ ヘッダ識別部 １３０ 遅延優先メモリ ３００ セルバッファ ３１０ ヘッダ識別部 ３２０ 送出時刻計算部 ３３０ 空き時刻検索部 ３４０ バッファ制御部 ３５０ パラメータテーブル ３６０ 検索テーブル ３７０ セル出力リスト ３８０ 競合制御回路 ４００ ＦＩＦＯメモリ ４１０ デコータ ４２０ 読出制御部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 秋田 稔 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内

Claims (4)

【特許請求の範囲】
1. 【請求項１】 到着したＡＴＭ（Ａｓｙｎｃｈｒｏｎｏ
   ｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）セル（以下単にセ
   ルと呼ぶ）をメモリに書き込み、出力時刻にメモリから
   読み出すシェーピング装置に含まれる競合制御回路にお
   いて、 上記セルを保存するセルメモリと、 該セルメモリの空きアドレスを管理する空きアドレスメ
   モリと、 上記セルメモリの書き込みアドレスを制御する書き込み
   アドレス制御部と、 上記セルメモリの読み出しアドレスを制御する読み出し
   アドレス制御部と、 上記セルメモリの上記セルの読み出し順序を管理するア
   ドレスチェーンメモリと、 理想送出時刻毎に上記セルが存在するかどうかの情報を
   持つセル存在有無メモリと、 理想送出時刻毎に最初に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する先頭アドレスメモリ
   と、 理想送出時刻毎に最後に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する最終アドレスメモリ
   と、 を備えたことを特徴とする競合制御回路。
2. 【請求項２】 到着したセルをメモリに書き込み、出力
   時刻にメモリから読み出すシェーピング装置に含まれる
   競合制御回路において、 上記セルを保存するセルメモリと、 上記セルメモリの空きアドレスを管理する空きアドレス
   メモリと、 該セルメモリの書き込みアドレスを制御する書き込みア
   ドレス制御部と、 上記セルメモリの読み出しアドレスを制御する読み出し
   アドレス制御部と、 上記セルメモリの上記セルの読み出し順序を管理するア
   ドレスチェーンメモリと、 理想送出時刻毎に上記セルが存在するかどうかの情報を
   持つセル存在有無メモリと、 理想送出時刻毎に最初に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する先頭アドレスメモリ
   と、 理想送出時刻毎に最後に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する最終アドレスメモリ
   と、 入力セルのヘッダに含まれる識別子を取り出すヘッダ識
   別部と、 識別子毎の遅延優先クラスを記録した遅延優先情報メモ
   リとを備え、 前記遅延優先クラスは２クラスであり、 入力セルの遅延優先情報に応じて書き込みアドレスを制
   御する手段を備えたことを特徴とする競合制御回路。
3. 【請求項３】 到着したセルをメモリに書き込み、出力
   時刻にメモリから読み出すシェーピング装置に含まれる
   競合制御回路において、 上記セルを保存するセルメモリと、 このセルメモリの空きアドレスを管理する空きアドレス
   メモリと、 上記セルメモリの書き込みアドレスを制御する書き込み
   アドレス制御部と、 上記セルメモリの読み出しアドレスを制御する読み出し
   アドレス制御部と、 上記セルメモリのセルの読み出し順序を管理するアドレ
   スチェーンメモリと、 理想送出時刻毎にセルが存在するかどうかの情報を持つ
   セル存在有無メモリと、理想送出時刻毎に最初に出力す
   べきセルが保存されているセルメモリのアドレスを記録
   する先頭アドレスメモリと、 理想送出時刻毎に最後に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する最終アドレスメモリ
   と、 入力セルのヘッダに含まれる識別子を取り出すヘッダ識
   別部と、 識別子毎の遅延優先クラスを記録した遅延優先情報メモ
   リとを備え、 前記遅延優先クラスは２クラスであり、セル存在有無メ
   モリと先頭アドレスメモリと最終アドレスメモリは、遅
   延優先クラス毎にデータを保持しており、入力セルの遅
   延優先クラスに応じて書き込みアドレスを制御する手段
   を備えたことを特徴とする競合制御回路。
4. 【請求項４】 到着したセルをメモリに書き込み、出力
   時刻にメモリから読み出すシェーピング装置に含まれる
   競合制御回路において、 セルを保存するセルメモリと、 上記セルメモリの空きアドレスを管理する空きアドレス
   メモリと、 このセルメモリの書き込みアドレスを制御する書き込み
   アドレス制御部と、 上記セルメモリの読み出しアドレスを制御する読み出し
   アドレス制御部と、 上記セルメモリの上記セルの読み出し順序を管理するア
   ドレスチェーンメモリと、 理想送出時刻毎に上記セルが存在するかどうかの情報を
   持つセル存在有無メモリと、 理想送出時刻毎に最初に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する先頭アドレスメモリ
   と、 理想送出時刻毎に最後に出力すべきセルが保存されてい
   るセルメモリのアドレスを記録する最終アドレスメモリ
   と、 入力セルのヘッダに含まれる識別子を取り出すヘッダ識
   別部と、 識別子毎の遅延優先クラスを記録した遅延優先情報メモ
   リとを備え、 前記遅延優先クラスは３クラス以上であり、セル存在有
   無メモリと先頭アドレスメモリと最終アドレスメモリ
   は、遅延優先クラス毎にデータを保持しており、入力セ
   ルの遅延優先クラスに応じて書き込みアドレスを制御す
   る手段を備えたことを特徴とする競合制御回路。