【発明の詳細な説明】
通信装置内でフレームを廃棄する方法及び装置関連特許出願
本願は、１９９５年７月１９日に出願された米国仮特許出願第６０／００１，
４９８号に関連する。発明の技術分野
本発明は概して通信に関し、更に特定的には通信装置内でフレームを廃棄する
方法及び装置に関する。発明の背景
通信のために非同期転送モード（ＡＴＭ）セルを使用する通信網はしばしば様
々な通信プロトコルを使用する装置とインタフェースで接続される。多くの既存
の通信網はＡＴＭ以外の通信プロトコルを使用するため、ＡＴＭ通信網はしばし
ば既存の通信網にインタフェースで接続される。通信網の例は、電話網、ＩＳＤ
Ｎ網、フレームリレー網、イーサネット網及び／又はトークンリング網を含む。
ＡＴＭ通信網にインタフェースで接続される幾つかの既存の通信網は、通信のた
めに情報のフレームを使用する。フレームがＡＴＭ通信網を通じて搬送されると
き、フレームは典型的にはそのフレームの終わりがＡＴＭセルのヘッダ内の情報
によって示されている一連のＡＴＭセルへ分割される。
ＡＴＭ通信網の輻輳を緩和するため、網内の交換ノードにおいて、その交換ノ
ード又は通信網全般内の輻輳によりＡＴＭセルを廃棄することが時には望ましい
。しかしながら、ＡＴＭ通信網を通過するフレームの一部であるセルを廃棄する
ことにより、帯域幅が非効率的に使用されうる。より多くのＡＴＭセルからなる
フレームの一部
である単一のＡＴＭセルが廃棄されれば、ＡＴＭセルのフレーム全体は通信網を
通じて再び送信されねばならない。フレームのセルが廃棄された後にこのフレー
ム中の他のＡＴＭセルが網を通過することを許されれば、ＡＴＭ通信網を通して
非廃棄セルを伝送するために使用される帯域幅は本質的に無駄にされる。幾つか
のフレームは他のフレームよりも重要であり得るため、輻輳した交換ノード又は
網内でフレームを廃棄することはまた問題となりうる。発明の概要
本発明は、通信用の一連のセルを使用した通信網内でフレームを廃棄する方法
及び装置からなる。本発明は、異なる優先度を有するフレームが異なる輻輳レベ
ルで廃棄され得るよう、フレームに対して異なる優先度を割り当てることを可能
にする。本発明の１つの面は、通信装置内でフレームを廃棄する方法である。夫
々のセルがデータ部と、セル損優先度標識とを有するヘッダ部とからなる、複数
のフレームを表わす複数のセルが受信される。セルのうちの少なくとも幾つかは
バッファ内に記憶される。エンドオブフレームマーカを含む第１のセルが受信さ
れるとき、バッファ内のセル数が第１の閾値を超過するか否かが決定される。第
１の閾値が超過されていれば、その一連のセル内のセルに対するセル損優先度標
識が第１の状態にセットされている場合、第１のセルと第２のセルとの間に受信
された一連のセルは廃棄される。第２のセルはエンドオブフレームマーカを含む
セルからなる。
本発明は幾つかの重要な技術的な利点を有する。本発明は、輻輳が生じたとき
に、ただフレームの一部分を廃棄するよりもむしろ、一連のセルからなるフレー
ム全体が廃棄されるため、ＡＴＭ通信網内の帯域幅のより効率的な使用を可能に
する。更に、たとえフレームの伝送の間に網が輻輳したとしても、オーバラン条
件が検出されるか、又はバッファプール限界が超過されない限り、そのフレーム
内のセルは廃棄されないままである。本発明は、フレームのセルが、ＡＴＭセル
のヘッダ情報を使用して多数の優先度レベルでマーク付けされることを可能にす
る。本発明のこの特徴は、フレームがその優先度に依存して、様々な輻輳レベル
で廃棄されることを可能にする。より低い優先度のフレームはより低い輻輳レベ
ルで廃棄される。従って、本発明は高い優先度のフレームのスループットを増加
しうる。
優先度の付けられたフレーム廃棄では、フレームは、フレームベースド通信網
のコミットされた情報レート以下の帯域幅を使用するときに高い優先度としてマ
ーク付けされ、フレーム規準通信網のコミットされた情報レート以上の帯域幅を
使用するときに低い優先度としてマーク付けされる。本発明を使用するＡＴＭ通
信網は、まずコミットされた情報レート以上で送信されたフレームを廃棄し、フ
レーム規準通信網のユーザの間でより公正な分配を提供する。また、優先度の付
けられたフレーム廃棄は、末端の局がフロー制御されていない通信網内の入力フ
ィルタとして使用されうる。図面の簡単な説明
本発明のより完全な理解のため、並びに、他の特徴及び利点のため、添付の図
面と共に以下の説明が参照される。図面において、
図１は本発明によって構成される通信装置のブロック図を示す図であり、
図２は本発明によるフレームを廃棄する段階を説明するフローチャートを示す
図である。発明の詳細な説明
本発明及びその利点の望ましい実施例は、同様の対応する部分に対して同様の
番号が使用される、図１及び図２を参照して最もよく理解される。
図１は本発明によって構成される通信装置１０を示す。本実施例では、通信装
置１０はＡＴＭ通信網内の交換ノードからなる。通信装置１０は、通信網内で情
報のフレームを通過させるための一連のセルを使用する通信網内のいかなる種類
の通信装置であっても良い。
通信装置１０は交換機本体１４に結合される一連の入力プロセッサ１２からな
る。各入力プロセッサ１２は入力データの１つ以上のソースに接続される。入力
プロセッサ１２は、入力データを処理し、必要に応じてセルを廃棄し、非廃棄セ
ルを交換機本体１４へ通過させる。入力プロセッサ１２はまた様々な種類のデー
タを一連のＡＴＭセルへ変換する。
入力プロセッサ１２は、プロセッサ１６と、キューポインタ１８とバッファメ
モリ２０とを更に有する。入力プロセッサ１２は、特定用途向け集積回路（ＡＳ
ＩＣ）からなるが、以下に説明される機能を実行するために動作可能なあらゆる
種類の電子回路でありうる。
プロセッサ１６は通信装置１０内のセルの廃棄を制御する。プロセッサ１６に
よって廃棄されず、入力プロセッサ１２によって受信されたセルはバッファメモ
リ２０内のキューに記憶される。この例では、各バーチャルコネクションはバッ
ファメモリ２０内の夫々のキューに関連づけられる。キューポインタメモリ１８
内に記憶されたポインタは、バッファメモリ２０内の各キューの前及び後を追う
よう使用される。バーチャルコネクションに関連する各キューはまたバッファと
も称される。入力プロセッサ１６は特定バーチャルコネクションに関連し、バッ
ファメモリ２０に記憶されるキューの最大の大きさを決定する。更に、プロセッ
サ１６はバーチャルコネクションに関連するバッファを他のバーチャルコネクシ
ョンと関連するバッファのプールに割り当てうる。このように、プロセッサ１６
は、個々のバッファに含まれうるセル数を制限するほかに、バッファプール内に
含まれうるセルの最大数に対して制限を設けうる。
プロセッサ１６はまたバーチャルコネクションに関連する特定
バッファ内のセル数を反映するカウンタを維持する。１つのバーチャルコネクシ
ョンに対して多数のバッファが関連づけられていれば、プロセッサ１６は多数の
バッファの夫々に対してカウンタを維持しうる。プロセッサ１６は輻輳をモニタ
し、輻輳がある閾値を超過すればフレームを廃棄するためにバッファカウンタを
使用する。
本実施例では、プロセッサ１６は２つのフレーム優先度のレベルと、これらの
優先度のレベルに対応する２つの輻輳閾値を維持する。プロセッサ１６は、本発
明の範囲を逸脱することなく、より大きい又はより小さい数の優先度のレベルを
維持しうる。本例では、より低い優先度のフレームはより低い輻輳の閾値に遭遇
した後に廃棄され、一方より高い優先度のフレームはより高いレベルの輻輳に遭
遇した後に廃棄される。
本実施例は、フレームの優先度を決定するために、フレームを形成するＡＴＭ
セルのヘッダ内のセル損優先度ビットを使用する。セル損優先度ビットがゼロ値
を有するとき、フレームは高い優先度のフレームであると考えられる。セル損優
先度ビットが１にセットされるとき、フレームは低い優先度のフレームであると
考えられる。本実施例は、フレームが廃棄されるべきか否かを決定するために、
フレームの第１のセルのセル損優先度ビットを使用する。通常、フレーム内の各
セルのセル損優先度ビットは同じ値を有する。本発明の範囲を逸脱することなく
、優先度を示すために他のヘッダ情報が使用されうる。
帯域幅を効率的に使用するため、プロセッサ１６はフレーム境界において輻輳
を検査する。セルがエンドオブフレーム標識を有する場合、プロセッサ１６は、
低輻輳閾値又は高輻輳閾値のどちらが超過されたのかを決定するために検査する
。低輻輳閾値が超過されている場合、状態変数は続くフレームの低い優先度を有
する（セル損優先度ビットが１である）全てのフレームが廃棄されることを示す
ようセットされる。高輻輳閾値が超過されている場合、状態変数は
全ての続くフレームが廃棄されるべきであることを示すようセットされる。いず
れの場合も、エンドオブフレームセルは廃棄されない。フレーム境界においてい
ずれの輻輳閾値も超過されなければ、状態変数は、連続するフレームが廃棄され
ないよう非廃棄状態にセットされる。
本実施例では、エンドオブフレームセルではないユーザデータセルのみが廃棄
される。それらのシステムオペレーションの重要性により、ＯＡＭといった他の
セルは、以下に説明されるようにプール空間が超過され、オーバラン条件が存在
しない限り廃棄されない。プロセッサ１６はセルがユーザデータ又は、セルのペ
イロードタイプ標識を使用した他のデータを含むか否かを決定する。ペイロード
タイプ標識はＡＴＭセルのヘッダ内に現れる。
フレームの終わりにおける検査が高輻輳閾値が超過されていることを示せば、
エンドオブフレームセルを除き、続くフレーム内の全てのセルが廃棄され、プロ
セッサ１６は廃棄されたフレームの終わりにおいて再び輻輳の状態を決定する。
フレームの終わりにおいて低輻輳閾値が超過され、次のフレームの第１のセルの
セル損優先度ビットが１にセットされることが決定されれば、そのフレーム内の
全てのセルは廃棄され、プロセッサ１６は廃棄されたフレームの終わりにおいて
輻輳のレベルを再び検査する。
プロセッサ１６はまた、輻輳があまりにも重大になり、バッファオーバランが
生ずるか、バッファプール内のセル数がそのバッファプールに関連するプール限
界に達するとき、フレームの部分を廃棄しうる。
プロセッサ１６は、廃棄されたフレーム内のセルを、バッファメモリ２０内に
配置される前に廃棄させる。本発明のこの面は、キューの再配置が不必要である
ため、キューポインタメモリ１８内に記憶されるキューポインタの操作を容易に
することを可能にする。
本発明のより詳細な動作は、図２を参照して最もよく理解されよ
う。図２は図１の入力プロセッサ１２がフレームを廃棄する方法を説明するフロ
ーチャートを示す。図２に示される方法は、フレームを廃棄するかどうかを決定
するために２つの状態変数を使用する。第１の状態変数、即ちフレーム廃棄状態
は、輻輳のレベルが、全てのフレームが廃棄されるか、さもなければクリアされ
るべきである点に達したときにセットされる。第２の状態変数、即ちＣＬＰ１フ
レーム廃棄状態は、輻輳のレベルが１のセル損優先度を有する（低い優先度）フ
レームを廃棄するために十分高いときにセットされる。そうでなければこの変数
はクリアされる。
方法はステップ２２において初期化から開始する。初めに、ステップ２２で状
態変数がクリアされる。ステップ２４において、セルが受信される。次に、ステ
ップ２６においてセルがユーザデータ、又はエンドオブフレームセルであるか、
セル損優先度が１であるか、ＣＬＰ１フレーム廃棄状態がセットされているかが
決定される。セルは、そのペイロードタイプ標識が０又は２であるとき、ユーザ
データであると考えられる。セルは、そのペイロードタイプ標識が１又は３であ
るとき、エンドオブフレームセルであると考えられる。ペイロードタイプ標識は
ＡＴＭセルのヘッダ内に現れる。ステップ２６において全ての条件が満たされれ
ば、１のセル損優先度を有し、輻輳のレベルはその種類のフレームを廃棄するた
めに十分高く、フレームはユーザデータを含むため、現在のフレームは廃棄され
る。このように、フレーム廃棄状態変数はステップ２８においてセットされる。
ステップ２８の後、又はステップ２６において全ての条件が満たされなければ、
手順はステップ３０へ続く。ステップ２６は、フレーム境界においてエンドオブ
フレームセルを処理するときにのみ変更されるＣＬＰ１フレーム廃棄状態変数の
状態に依存することに注意すること。
ステップ３０では、セルがエンドオブフレームマーカを有するか否かが決定さ
れる。エンドオブフレームマーカを有さなければ、処
理はステップ４４へ続く。エンドオブフレームマーカを有するとき、フレーム境
界に達しており、網内の輻輳が検査されねばならない。従って、処理は、バッフ
ァが高輻輳閾値に達したか否かを決定するステップ３２へ続く。高輻輳閾値に達
していれば、ステップ４２において廃棄フレーム状態変数がセットされ、手順は
ステップ４４へ続く。高輻輳閾値に達していなければ、廃棄フレーム状態変数は
、この変数が前のフレームのためにセットされていた場合のためにステッブ３４
においてクリアされる。次にステップ３６において、バッファが低輻輳閾値に達
しているかどうかが決定される。低輻輳閾値に達していなければ、ＣＬＰ１フレ
ーム廃棄状態変数は、この変数が前のフレームのためにセットされていた場合の
ためにステップ３８においてクリアされる。低輻輳閾値に達していれば、ＣＬＰ
１フレーム廃棄状態変数はステップ４０においてセットされる。
次に、ステップ４４において、プール限界が超過されているか、又はバッファ
オーバラン条件が生じているかどうかが決定される。本実施例では、幾つかのバ
ーチャルコネクションがバッファプールを共用しうる。このバッファプールの限
界が超過されれば、セルを置く場所が無いため、現在のセルはステップ４６にお
いて直ちに廃棄される。同様に、バッファオーバランが生じていれば、たとえそ
のような廃棄がフレームの途中で生じても、セルはまたステップ４６で廃棄され
るべきである。ステップ４６の後、処理はセルがユーザデータ又はエンドオブフ
レームセルであるかを決定するステップ４８へ続く。セルがユーザデータ又はエ
ンドオブフレームセルでなければ、次のセルを受信するために手順はステップ２
４へ戻る。セルがユーザデータ又はエンドオブフレームセルであれば、ステップ
５０においてフレーム廃棄状態がセットされる。ステップ５０においてフレーム
廃棄状態をセットすることにより、ステップ４６においてそこからセルが廃棄さ
れた残りのフレームもまた廃棄される。フレームの１つのセルは既に廃棄されて
いるため、帯域幅を無駄に
することを防ぐため、残りもまた廃棄されるべきである。上述のようにエンドオ
ブフレームセルは、エンドオブフレームセルが受信されたときにバッファオーバ
ラン条件又はプール限界オーバラン条件がもはや存在しなくとも、やはり送信さ
れる。
ステップ４４に戻り、いずれの条件も満たされなければ過程はステップ５２へ
続く。ステップ５２では、フレーム廃棄状態変数がセットされているか、また現
在のセルがユーザデータを含むかどうかが決定される。フレーム廃棄状態変数が
セットされておらず、現在のセルがユーザデータを含まなければ、手順は次のセ
ルを処理するためにステップ２４へ戻る。フレーム廃棄状態変数がセットされて
おり、現在のセルがユーザデータを含んでいれば、現在のセルはステップ５４に
おいて廃棄され、手順はステップ２４へループして戻る。
図２の処理はこのようにして、各エンドオブフレームセルが受信されるたびに
フレーム境界における輻輳を検査する。輻輳のレベルが続くフレームのための適
当な所定の閾値を超過すれば、エンドオブフレームセルを除く続くフレームのセ
ルは廃棄される。この処理は従って、網の帯域幅をより効率的に使用し、フレー
ムの優先度の付けられた廃棄を可能にする。
本発明は詳述されたが、請求項によって定義される本発明の精神及び範囲を逸
脱することなく、様々な変化、代替、変更が行われうることが理解されるべきで
ある。DETAILED DESCRIPTION OF THE INVENTION Methods and apparatus related patent applications present frame is disposed in a communication system, July 1995 filed on 19 U.S. Provisional Patent Application No. 60/001, relating to No. 498. TECHNICAL FIELD OF THE INVENTION The present invention relates generally to communications, and more particularly to a method and apparatus for discarding frames in a communication device. BACKGROUND OF THE INVENTION Communication networks that use Asynchronous Transfer Mode (ATM) cells for communication are often interfaced with devices that use various communication protocols. ATM communication networks are often interfaced to existing communication networks because many existing communication networks use communication protocols other than ATM. Examples of communication networks include a telephone network, an ISDN network, a frame relay network, an Ethernet network and / or a token ring network. Some existing networks that interface to ATM networks use frames of information for communication. When a frame is transported over an ATM network, the frame is typically divided into a series of ATM cells, the end of the frame being indicated by information in the ATM cell header. In order to alleviate congestion in an ATM communication network, it is sometimes desirable at a switching node in the network to discard ATM cells due to congestion in the switching node or the communication network in general. However, by discarding cells that are part of a frame passing through the ATM network, bandwidth can be used inefficiently. If a single ATM cell, which is part of a frame of more ATM cells, is discarded, the entire frame of ATM cells must be transmitted again over the network. If other ATM cells in this frame are allowed to pass through the network after the cells of the frame have been discarded, the bandwidth used to transmit non-discarded cells over the ATM network is essentially wasted. Is done. Discarding frames in congested switching nodes or networks can also be problematic, as some frames may be more important than others. SUMMARY OF THE INVENTION The present invention comprises a method and apparatus for discarding frames in a communication network using a series of cells for communication. The invention makes it possible to assign different priorities to frames, so that frames with different priorities can be discarded at different congestion levels. One aspect of the present invention is a method for discarding a frame in a communication device. A plurality of cells representing a plurality of frames are received, each cell comprising a data portion and a header portion having a cell loss priority indicator. At least some of the cells are stored in a buffer. When the first cell including the end of frame marker is received, it is determined whether the number of cells in the buffer exceeds a first threshold. If the first threshold is exceeded, the cell loss priority indicator for a cell in the series of cells is set to the first state and the reception between the first cell and the second cell is performed. The series of cells that have been set is discarded. The second cell comprises a cell containing an end-of-frame marker. The present invention has several important technical advantages. The present invention allows for more efficient use of bandwidth in an ATM network because, when congestion occurs, an entire frame of a series of cells is discarded, rather than just a portion of the frame. To Furthermore, even if the network is congested during the transmission of a frame, the cells in that frame will not be discarded unless an overrun condition is detected or the buffer pool limit is exceeded. The present invention allows cells of a frame to be marked at multiple priority levels using the ATM cell header information. This feature of the invention allows a frame to be dropped at various congestion levels, depending on its priority. Lower priority frames are discarded at lower congestion levels. Thus, the present invention can increase the throughput of high priority frames. In prioritized frame discarding, frames are marked as high priority when using bandwidth below the committed information rate of the frame-based network and the committed information rate of the frame-based network is When using the above bandwidth, it is marked as low priority. An ATM network employing the present invention first discards frames transmitted above the committed information rate, providing a fairer distribution among users of the frame-based network. Also, prioritized frame discarding can be used as an input filter in a communication network where the terminal station is not flow controlled. BRIEF DESCRIPTION OF THE DRAWINGS For a more complete understanding of the present invention, as well as other features and advantages, reference is made to the following description taken in conjunction with the accompanying drawings. In the drawings, FIG. 1 is a block diagram of a communication device constructed according to the present invention, and FIG. 2 is a flowchart illustrating a step of discarding a frame according to the present invention. DETAILED DESCRIPTION OF THE INVENTION Preferred embodiments of the present invention and its advantages are best understood with reference to FIGS. 1 and 2, wherein like numerals are used for like corresponding parts. FIG. 1 shows a communication device 10 configured according to the present invention. In this embodiment, the communication device 10 comprises a switching node in an ATM communication network. Communication device 10 may be any type of communication device in a communication network that uses a series of cells to pass frames of information through the communication network. The communication device 10 comprises a series of input processors 12 coupled to a switch body 14. Each input processor 12 is connected to one or more sources of input data. The input processor 12 processes the input data, discards cells as needed, and passes non-discarded cells to the switch body 14. Input processor 12 also converts various types of data into a series of ATM cells. The input processor 12 further includes a processor 16, a queue pointer 18, and a buffer memory 20. Input processor 12 comprises an application specific integrated circuit (ASIC), but can be any type of electronic circuit operable to perform the functions described below. The processor 16 controls the disposal of cells in the communication device 10. Cells not received by processor 16 and received by input processor 12 are stored in a queue in buffer memory 20. In this example, each virtual connection is associated with a respective queue in buffer memory 20. The pointers stored in the queue pointer memory 18 are used to track before and after each queue in the buffer memory 20. Each queue associated with a virtual connection is also called a buffer. The input processor 16 determines the maximum size of the queue associated with a particular virtual connection and stored in the buffer memory 20. Further, processor 16 may allocate buffers associated with virtual connections to a pool of buffers associated with other virtual connections. Thus, the processor 16 may place a limit on the maximum number of cells that can be included in a buffer pool, in addition to limiting the number of cells that can be included in an individual buffer. Processor 16 also maintains a counter that reflects the number of cells in a particular buffer associated with the virtual connection. If multiple buffers are associated with one virtual connection, processor 16 may maintain a counter for each of the multiple buffers. Processor 16 monitors congestion and uses a buffer counter to discard frames if congestion exceeds a certain threshold. In the present embodiment, processor 16 maintains two frame priority levels and two congestion thresholds corresponding to these priority levels. Processor 16 may maintain a greater or lesser number of priority levels without departing from the scope of the present invention. In this example, lower priority frames are discarded after encountering a lower congestion threshold, while higher priority frames are discarded after encountering a higher level of congestion. This embodiment uses the cell loss priority bit in the header of the ATM cells forming the frame to determine the priority of the frame. When the cell loss priority bit has a value of zero, the frame is considered to be a high priority frame. When the cell loss priority bit is set to 1, the frame is considered to be a low priority frame. This embodiment uses the cell loss priority bit of the first cell of the frame to determine whether the frame should be discarded. Usually, the cell loss priority bit of each cell in the frame has the same value. Other header information may be used to indicate priority without departing from the scope of the present invention. To use bandwidth efficiently, processor 16 checks for congestion at frame boundaries. If the cell has an end-of-frame indicator, processor 16 checks to determine whether the low congestion threshold or the high congestion threshold has been exceeded. If the low congestion threshold has been exceeded, a state variable is set to indicate that all frames with a lower priority (cell loss priority bit is 1) for the following frames are discarded. If the high congestion threshold has been exceeded, a state variable is set to indicate that all subsequent frames should be discarded. In either case, the end of frame cell is not discarded. If no congestion threshold is exceeded at a frame boundary, the state variable is set to a non-discarded state so that successive frames are not discarded. In this embodiment, only user data cells that are not end-of-frame cells are discarded. Due to the importance of their system operation, other cells, such as OAM, are not discarded unless pool space is exceeded and an overrun condition exists, as described below. Processor 16 determines whether the cell contains user data or other data using the cell's payload type indicator. The payload type indicator appears in the header of the ATM cell. If the check at the end of the frame indicates that the high congestion threshold has been exceeded, all cells in the subsequent frame are discarded, except for end-of-frame cells, and the processor 16 returns to the congested state at the end of the discarded frame. To determine. If at the end of the frame the low congestion threshold is exceeded and it is determined that the cell loss priority bit of the first cell of the next frame is set to 1, all cells in that frame are discarded and the processor 16 again checks the level of congestion at the end of the discarded frame. Processor 16 may also discard portions of the frame when congestion becomes too serious and a buffer overrun occurs or the number of cells in the buffer pool reaches the pool limit associated with that buffer pool. The processor 16 causes the cells in the discarded frame to be discarded before being placed in the buffer memory 20. This aspect of the invention makes it easier to manipulate the cue pointers stored in the cue pointer memory 18 because cue relocation is not required. The more detailed operation of the present invention will be best understood with reference to FIG. FIG. 2 is a flowchart illustrating a method of discarding a frame by the input processor 12 of FIG. The method shown in FIG. 2 uses two state variables to determine whether to discard the frame. The first state variable, the frame discard state, is set when the level of congestion reaches a point at which all frames should be discarded or otherwise cleared. The second state variable, the CLP1 frame discard state, is set when the level of congestion is high enough to discard frames with a cell loss priority of 1 (low priority). Otherwise this variable is cleared. The method starts at step 22 with initialization. First, at step 22, the state variables are cleared. In step 24, a cell is received. Next, in step 26, it is determined whether the cell is user data or an end-of-frame cell, the cell loss priority is 1, and the CLP1 frame discard state is set. A cell is considered to be user data when its payload type indicator is 0 or 2. A cell is considered to be an end-of-frame cell when its payload type indicator is 1 or 3. The payload type indicator appears in the header of the ATM cell. If all conditions are satisfied in step 26, the current frame is discarded because it has a cell loss priority of one, the level of congestion is high enough to discard that type of frame, and the frame contains user data. Is done. Thus, the frame discard state variable is set at step 28. After step 28, or if all conditions are not met in step 26, the procedure continues to step 30. Note that step 26 depends on the state of the CLP1 frame discard state variable, which changes only when processing end-of-frame cells at frame boundaries. In step 30, it is determined whether the cell has an end of frame marker. If not, the process continues to step 44. When having an end-of-frame marker, the frame boundary has been reached and congestion in the network must be checked. Accordingly, processing continues to step 32, which determines whether the buffer has reached the high congestion threshold. If the high congestion threshold has been reached, the discard frame state variable is set in step 42 and the procedure continues to step 44. If the high congestion threshold has not been reached, the discarded frame state variable is cleared at step 34 in case this variable had been set for the previous frame. Next, in step 36, it is determined whether the buffer has reached the low congestion threshold. If the low congestion threshold has not been reached, the CLP1 frame discard status variable is cleared in step 38 in case this variable was set for the previous frame. If the low congestion threshold has been reached, the CLP 1 frame discard status variable is set in step 40. Next, at step 44, it is determined whether a pool limit has been exceeded or a buffer overrun condition has occurred. In this embodiment, several virtual connections can share a buffer pool. If this buffer pool limit is exceeded, the current cell is immediately discarded at step 46 since there is no place to put the cell. Similarly, if a buffer overrun has occurred, the cell should also be discarded at step 46, even if such discarding occurs in the middle of the frame. After step 46, processing continues to step 48 where it is determined whether the cell is user data or an end of frame cell. If the cell is not a user data or end of frame cell, the procedure returns to step 24 to receive the next cell. If the cell is a user data or end of frame cell, a frame discard state is set in step 50. By setting the frame discard state in step 50, the remaining frames from which cells were discarded in step 46 are also discarded. Since one cell of the frame has already been discarded, the rest should also be discarded to prevent wasting bandwidth. As described above, the end-of-frame cell is still transmitted even if there is no longer a buffer overrun condition or a pool limit overrun condition when the end-of-frame cell is received. Returning to step 44, if none of the conditions are met, the process continues to step 52. In step 52, it is determined whether the frame discard status variable is set and whether the current cell contains user data. If the frame discard status variable is not set and the current cell does not contain user data, the procedure returns to step 24 to process the next cell. If the frame discard state variable is set and the current cell contains user data, the current cell is discarded at step 54 and the procedure loops back to step 24. The process of FIG. 2 thus checks for congestion at frame boundaries each time an end-of-frame cell is received. If the level of congestion exceeds an appropriate predetermined threshold for the subsequent frame, cells in subsequent frames except for end-of-frame cells are discarded. This process thus makes more efficient use of the network bandwidth and allows for prioritized discarding of frames. Although the present invention has been described in detail, it should be understood that various changes, substitutions, and alterations can be made without departing from the spirit and scope of the invention as defined by the claims.
【手続補正書】特許法第１８４条の８第１項
【提出日】１９９７年２月１９日
【補正内容】
請求の範囲
１． データ部とセル損優先度標識を含むヘッダ部とからなるセルであって、複
数のフレームを表わす複数のセルを受信する段階と、
バッファ内に少なくとも幾つかのセルを記憶する段階と、
第１のフレームに対応するエンドオブフレームマーカを有する第１のセルが受
信されたとき、バッファ内のセル数が第１の閾値を超過するか否かを決定する段
階と、
第１の閾値が超過され、また一連のセル内のセルのためのセル損優先度標識が
第１の状態にセットされれば、第１のセルと、該第１のフレームに関して続くフ
レームに対応するエンドオブフレームマーカを有する第２のセルとの間に受信さ
れた一連のセルを廃棄する段階とからなる、通信装置内でフレームを廃棄する方
法。
２． 廃棄された一連のセルは、第２のセルを除き第１のフレームの後に受信さ
れた続くフレーム内の各セルを含む、請求項１記載の方法。
３． 第１のセルが受信されたときに、バッファ内のセル数が第２の閾値を超過
するか否かを決定する段階と、
第２の閾値が超過されていれば、第１のセルと第２のセルとの間に受信された
一連のセルを廃棄する段階とを更に有する請求項１記載の方法。
４． バッファ内のセル数がオーバラン閾値を超過すればセルを廃棄する段階を
更に有する請求項３記載の方法。
５． バッファはバッファプールのメンバであり、
バッファプール内のセル数がバッファプール限界を超過すればセ
ルを廃棄する段階を更に有する請求項４記載の方法。
６． バッファプール限界を超過するセルに関連するフレームに対応する全ての
セルを廃棄する段階を更に有する、請求項５記載の方法。
７． バッファ内のセル数がオーバラン閾値を超過すればセルを廃棄する段階を
更に有する請求項１記載の方法。
８． バッファはバッファプールのメンバであり、
バッファプール内のセル数がバッファプール限界を超過すればセルを廃棄する
段階を更に有する請求項１記載の方法。
９． セルは非同期転送モードセルからなる請求項１記載の方法。
１０． 交換機本体と、
該交換機本体に結合され、データ部とセル損優先度標識を含むヘッダ部とから
なるセルであって複数のフレームを表わす複数のセルを受信するよう動作可能な
入力プロセッサとからなり、
該入力プロセッサは少なくとも幾つかのセルを記憶するよう動作可能なバッフ
ァを有し、該入力プロセッサは第１のフレームに対応するエンドオブファイルマ
ーカを含む第１のセルが受信されたとき、バッファ内のセル数が第１の閾値を超
過すれば第１の廃棄信号を発生するよう動作可能であり、該入力プロセッサは第
１の廃棄信号の発生に応答して、第１のセルと第２のセルとの間の一連のセルの
中のセルのためのセル損優先度標識が第１の状態にセットされていれば、第１の
セルと第２のセルとの間に受信された一連のセルを廃棄するよう動作可能であり
、第２のセルは第１のフレームに関して続くフレームに対応するエンドオブフレ
ームマーカを有する、通信装
置。
１１． 入力プロセッサは特定用途向け集積回路からなる請求項１０記載の通信
装置。
１２． セルは非同期転送モードセルからなる請求項１０記載の通信装置。
１３． 廃棄された一連のセルは、第２のセルを除き第１のフレームの後に受信
された続くフレーム内の各セルを含む、請求項１０記載の通信装置。
１４． 入力プロセッサは、第１のセルが受信されたときにバッファ内のセル数
が第２の閾値を超過していれば第２の廃棄信号を発生するよう動作可能であり、
入力プロセッサは第２の廃棄信号の発生に応じて第１のセルと第２のセルとの間
に受信された一連のセルを廃棄するよう動作可能である請求項１０記載の通信装
置。
１５． 入力プロセッサは、
バッファ内のセル数がオーバラン閾値を超過していればセルを廃棄するよう動
作可能である請求項１４記載の通信装置。
１６． バッファはバッファプールのメンバであり、入力プロセッサは、
バッファプール内のセル数がバッファプール限界を超過すればセルを廃棄する
よう動作可能である請求項１５記載の通信装置。
１７． 入力プロセッサは、バッファプール限界を超過するセルに関連するフレ
ームに対応する全てのセルを廃棄するよう動作可能で
ある、請求項１６記載の通信装置。
１８． 入力プロセッサは、
バッファ内のセル数がオーバラン閾値を超過すればセルを廃棄するよう動作可
能である請求項１０記載の通信装置。
１９． バッファはバッファプールのメンバであり、入力プロセッサはバッファ
プール内のセル数がバッファプール限界を超過すればセルを廃棄するよう動作可
能である請求項１０記載の通信装置。[Procedure of Amendment] Article 184-8, Paragraph 1 of the Patent Act
[Submission date] February 19, 1997
[Correction contents]
The scope of the claims
1. A cell consisting of a data part and a header part including a cell loss priority indicator,
Receiving a plurality of cells representing a number of frames;
Storing at least some cells in a buffer;
A first cell having an end of frame marker corresponding to the first frame is received.
Determining, when received, whether the number of cells in the buffer exceeds a first threshold
Floor and
A first threshold is exceeded and a cell loss priority indicator for cells in the series is
If set to the first state, the first cell and subsequent frames for the first frame.
Received between the second cell having an end-of-frame marker corresponding to the frame.
Discarding a series of cells in a communication device.
Law.
2. The discarded series of cells is received after the first frame except for the second cell.
2. The method of claim 1 including each cell in a subsequent subsequent frame.
3. When the first cell is received, the number of cells in the buffer exceeds a second threshold
Deciding whether or not to do so;
If the second threshold has been exceeded, a received between the first cell and the second cell
Discarding the series of cells.
4. If the number of cells in the buffer exceeds the overrun threshold, drop the cell.
4. The method of claim 3, further comprising:
5. The buffer is a member of the buffer pool,
If the number of cells in the buffer pool exceeds the buffer pool limit,
5. The method of claim 4, further comprising the step of discarding the file.
6. All frames corresponding to cells that exceed the buffer pool limit
The method of claim 5, further comprising the step of discarding the cell.
7. If the number of cells in the buffer exceeds the overrun threshold, drop the cell.
The method of claim 1, further comprising:
8. The buffer is a member of the buffer pool,
Discard cells if the number of cells in the buffer pool exceeds the buffer pool limit
The method of claim 1, further comprising a step.
9. The method of claim 1, wherein the cells comprise asynchronous transfer mode cells.
10. Exchange body,
The data part and the header part including the cell loss priority indicator, which are connected to the switch body,
Operable to receive a plurality of cells representing a plurality of frames.
Consisting of an input processor,
The input processor has a buffer operable to store at least some cells.
And the input processor has an end-of-file manager corresponding to the first frame.
The number of cells in the buffer exceeds a first threshold when the first cell containing the
Otherwise, the input processor is operable to generate a first discard signal, and the input processor
One of the series of cells between the first cell and the second cell in response to the occurrence of the first discard signal.
If the cell loss priority indicator for the middle cell is set to the first state, the first
Operable to discard a series of cells received between a cell and a second cell.
, The second cell is the end of frame corresponding to the subsequent frame with respect to the first frame.
Communication device having a frame marker
Place.
11. The communication of claim 10, wherein the input processor comprises an application specific integrated circuit.
apparatus.
12. The communication device according to claim 10, wherein the cell comprises an asynchronous transfer mode cell.
13. A series of discarded cells are received after the first frame except for the second cell.
11. The communication device according to claim 10, comprising each cell in a succeeding frame.
14． The input processor determines the number of cells in the buffer when the first cell is received.
Is operable to generate a second discard signal if exceeds a second threshold,
The input processor is responsive to the occurrence of the second discard signal between the first cell and the second cell.
11. The communication device of claim 10 operable to discard a series of cells received by said communication device.
Place.
15. The input processor is
Operate to discard cells if the number of cells in the buffer exceeds the overrun threshold.
The communication device according to claim 14 operable.
16. The buffer is a member of the buffer pool, and the input processor
Discard cells if the number of cells in the buffer pool exceeds the buffer pool limit
The communication device of claim 15 operable to:
17． The input processor is responsible for the frame associated with cells that exceed the buffer pool limit.
Operable to discard all cells corresponding to the
17. The communication device of claim 16, wherein:
18. The input processor is
Operable to discard cells if the number of cells in the buffer exceeds the overrun threshold
The communication device according to claim 10, wherein the communication device is capable of functioning.
19. The buffer is a member of the buffer pool and the input processor
Operates to discard cells if the number of cells in the pool exceeds the buffer pool limit
The communication device according to claim 10, wherein the communication device is capable of functioning.
─────────────────────────────────────────────────────
フロントページの続き
(81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，
ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ
Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ
，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，
ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ
Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ
，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ
，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ，
ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，Ｈ
Ｕ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ
，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，
ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，Ｒ
Ｏ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ
，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ
(72)発明者 ハウザー，スティーヴン エイ
アメリカ合衆国，マサチューセッツ州
01803，バーリントン，ファームズ・ドラ
イヴ 106番
(72)発明者 マニング，トマス エイ
アメリカ合衆国，マサチューセッツ州
01532，ノースボロ，サマー・ストリート
26番
(72)発明者 ペック，デイヴィッド エヌ
アメリカ合衆国，マサチューセッツ州
01752，マールバラ，アンダーソン・ロー
ド 181番────────────────────────────────────────────────── ───
Continuation of front page
(81) Designated countries EP (AT, BE, CH, DE,
DK, ES, FI, FR, GB, GR, IE, IT, L
U, MC, NL, PT, SE), OA (BF, BJ, CF)
, CG, CI, CM, GA, GN, ML, MR, NE,
SN, TD, TG), AP (KE, LS, MW, SD, S
Z, UG), UA (AM, AZ, BY, KG, KZ, MD
, RU, TJ, TM), AL, AM, AT, AU, AZ
, BB, BG, BR, BY, CA, CH, CN, CU,
CZ, DE, DK, EE, ES, FI, GB, GE, H
U, IL, IS, JP, KE, KG, KP, KR, KZ
, LK, LR, LS, LT, LU, LV, MD, MG,
MK, MN, MW, MX, NO, NZ, PL, PT, R
O, RU, SD, SE, SG, SI, SK, TJ, TM
, TR, TT, UA, UG, UZ, VN
(72) Inventor Hauser, Stephen A
Massachusetts, United States
01803, Burlington, Farms Dora
Eve 106
(72) Inventors Manning, Thomas A
Massachusetts, United States
01532, Northborough, Summer Street
26th
(72) Inventors Peck, David N
Massachusetts, United States
01752, Marlborough, Anderson Low
De 181