JP3446704B2 - シェーパ及びそれに用いるスケジューリング方法 - Google Patents
シェーパ及びそれに用いるスケジューリング方法Info
- Publication number
- JP3446704B2 JP3446704B2 JP2000009602A JP2000009602A JP3446704B2 JP 3446704 B2 JP3446704 B2 JP 3446704B2 JP 2000009602 A JP2000009602 A JP 2000009602A JP 2000009602 A JP2000009602 A JP 2000009602A JP 3446704 B2 JP3446704 B2 JP 3446704B2
- Authority
- JP
- Japan
- Prior art keywords
- packet
- time
- associative memory
- search
- shaper
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 41
- 230000005540 biological transmission Effects 0.000 claims description 53
- 238000004364 calculation method Methods 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 13
- 230000006870 function Effects 0.000 description 3
- 238000007796 conventional method Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/74—Address processing for routing
- H04L45/745—Address table lookup; Address filtering
- H04L45/7453—Address table lookup; Address filtering using hashing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/22—Traffic shaping
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/56—Queue scheduling implementing delay-aware scheduling
- H04L47/564—Attaching a deadline to packets, e.g. earliest due date first
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/56—Queue scheduling implementing delay-aware scheduling
- H04L47/568—Calendar queues or timing rings
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Multi Processors (AREA)
Description
【０００１】
【発明の属する技術分野】本発明はシェーパ及びそれに
用いるスケジューリング方法に関し、特にネットワーク
においてセルやパケットを制御するためのシェーパに用
いられるスケジューリング方法に関する。
用いるスケジューリング方法に関し、特にネットワーク
においてセルやパケットを制御するためのシェーパに用
いられるスケジューリング方法に関する。
【０００２】
【従来の技術】シェーパはＡＴＭ（Ａｓｙｎｃｈｒｏｎ
ｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ：非同期転送モー
ド）技術を利用したネットワークやＩＰ（Ｉｎｔｅｒｎ
ｅｔＰｒｏｔｏｃｏｌ）を利用したネットワークにおい
て、セルと呼ばれる固定長データやパケットと呼ばれる
可変長データ（以下、セルやパケットをパケットとす
る）を制御し、ネットワーク資源を有効に利用するため
に利用されている。
ｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ：非同期転送モー
ド）技術を利用したネットワークやＩＰ（Ｉｎｔｅｒｎ
ｅｔＰｒｏｔｏｃｏｌ）を利用したネットワークにおい
て、セルと呼ばれる固定長データやパケットと呼ばれる
可変長データ（以下、セルやパケットをパケットとす
る）を制御し、ネットワーク資源を有効に利用するため
に利用されている。
【０００３】例えば、ネットワークを利用するユーザは
トラヒックパラメータを用いて利用する資源を申告し、
ネットワークの提供者は申告したトラヒックを元にネッ
トワークを構成している。
トラヒックパラメータを用いて利用する資源を申告し、
ネットワークの提供者は申告したトラヒックを元にネッ
トワークを構成している。
【０００４】しかしながら、ユーザは必ずしも申告した
トラヒックパラメータ通りにパケットを送信せずに、申
告したトラヒックパラメータに違反することも考えられ
る。この場合、違反をしていない他のユーザのネットワ
ーク資源を使ってしまう可能性があるため、ネットワー
クの提供者はトラヒックを監視することが必要になる。
トラヒックを監視して違反を検出した場合、一般的には
パケットを廃棄するか、ネットワーク内にパケットを転
送する前にユーザの申告したトラヒックパラメータ通り
にパケットを転送し直す方法がある。
トラヒックパラメータ通りにパケットを送信せずに、申
告したトラヒックパラメータに違反することも考えられ
る。この場合、違反をしていない他のユーザのネットワ
ーク資源を使ってしまう可能性があるため、ネットワー
クの提供者はトラヒックを監視することが必要になる。
トラヒックを監視して違反を検出した場合、一般的には
パケットを廃棄するか、ネットワーク内にパケットを転
送する前にユーザの申告したトラヒックパラメータ通り
にパケットを転送し直す方法がある。
【０００５】また、ユーザがネットワークにパケットを
転送する場合には、ネットワーク提供者によってパケッ
トが廃棄されないように、また申告したトラヒックパラ
メータに違反しないように、シェーパを利用してトラヒ
ックパラメータに適合したトラヒックをネットワークに
送信している。
転送する場合には、ネットワーク提供者によってパケッ
トが廃棄されないように、また申告したトラヒックパラ
メータに違反しないように、シェーパを利用してトラヒ
ックパラメータに適合したトラヒックをネットワークに
送信している。
【０００６】ネットワークで転送される一連のパケット
は、トラヒックパラメータとして具体的な数値として表
すことができ、ＡＴＭではＬｅａｋｙ Ｂｕｃｋｅｔモ
デル、ＩＰではＴｏｋｅｎ Ｂｕｃｋｅｔモデルを用い
てトラヒックパラメータを表している。
は、トラヒックパラメータとして具体的な数値として表
すことができ、ＡＴＭではＬｅａｋｙ Ｂｕｃｋｅｔモ
デル、ＩＰではＴｏｋｅｎ Ｂｕｃｋｅｔモデルを用い
てトラヒックパラメータを表している。
【０００７】トラヒック違反はパケット到着間隔が申告
したトラヒックパラメータで計算できる間隔よりも短い
間隔で到着した場合で、シェーパはこの間隔をトラヒッ
クパラメータ違反にならない長い間隔で送信し直す処理
を行う。
したトラヒックパラメータで計算できる間隔よりも短い
間隔で到着した場合で、シェーパはこの間隔をトラヒッ
クパラメータ違反にならない長い間隔で送信し直す処理
を行う。
【０００８】シェーパの機能として、理想とする時刻に
パケットを出力するスケジューリング処理が必要にな
る。一つの方法として、パケットをキューイングし、ト
ラヒックパラメータによって理想とする時刻を計算し、
タイマを用いて理想とする時刻のカウントを行い、カウ
ンタが理想とする時刻を示した時にパケットを出力する
方法が考えられる。この方法は１フローの場合には有効
ではあるが、シェーパは複数のフローを扱うことが一般
的であり、タイマはフロー数だけ必要になり、現実的で
はない。
パケットを出力するスケジューリング処理が必要にな
る。一つの方法として、パケットをキューイングし、ト
ラヒックパラメータによって理想とする時刻を計算し、
タイマを用いて理想とする時刻のカウントを行い、カウ
ンタが理想とする時刻を示した時にパケットを出力する
方法が考えられる。この方法は１フローの場合には有効
ではあるが、シェーパは複数のフローを扱うことが一般
的であり、タイマはフロー数だけ必要になり、現実的で
はない。
【０００９】フロー毎に時刻を管理する方法として、配
列をベースにしたアルゴリズムが提案されている。配列
の１要素はタイマで管理される１時刻に対応し、あるフ
ロー番号のパケットを理想の時刻に送信するようにスケ
ジューリングするためには、理想の時刻に対応する配列
番号にフロー番号を書込む。
列をベースにしたアルゴリズムが提案されている。配列
の１要素はタイマで管理される１時刻に対応し、あるフ
ロー番号のパケットを理想の時刻に送信するようにスケ
ジューリングするためには、理想の時刻に対応する配列
番号にフロー番号を書込む。
【００１０】タイマは現在の時刻を示しており、タイマ
の時刻が進む毎に、現在時刻に対応する配列番号の内容
を取得して、この現在時刻に出力するパケットがないか
否かを検索する。この配列を利用した手法ではタイマを
１個だけ準備すればよく、フロー数が増加しても、配列
に必要なビット幅が増えるという利点がある。
の時刻が進む毎に、現在時刻に対応する配列番号の内容
を取得して、この現在時刻に出力するパケットがないか
否かを検索する。この配列を利用した手法ではタイマを
１個だけ準備すればよく、フロー数が増加しても、配列
に必要なビット幅が増えるという利点がある。
【００１１】しかしながら、配列をベースにした方法は
設定可能な時刻の範囲を広くすると、それに比例して配
列を大きくしなければならず、大容量のメモリ（ＲＡ
Ｍ：ランダムアクセスメモリ）を必要とするため、現実
的には設定可能な時刻の範囲を狭くしなくてはいけない
という制限が発生してしまうという問題がある。
設定可能な時刻の範囲を広くすると、それに比例して配
列を大きくしなければならず、大容量のメモリ（ＲＡ
Ｍ：ランダムアクセスメモリ）を必要とするため、現実
的には設定可能な時刻の範囲を狭くしなくてはいけない
という制限が発生してしまうという問題がある。
【００１２】これらの問題を解決するために、設定可能
な時刻の範囲に比例したメモリを必要とせず、またフロ
ー数を増加させてもタイマ機能を増加させないために、
ＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍ
ｅｍｏｒｙ：連想メモリ）を利用した方法が提案されて
いる。この方法については、特開平１０−２３０３７号
公報に開示されている。
な時刻の範囲に比例したメモリを必要とせず、またフロ
ー数を増加させてもタイマ機能を増加させないために、
ＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍ
ｅｍｏｒｙ：連想メモリ）を利用した方法が提案されて
いる。この方法については、特開平１０−２３０３７号
公報に開示されている。
【００１３】
【発明が解決しようとする課題】しかしながら、上記の
従来の提案手法においては、同一時刻に出力するパケッ
トが存在した場合の処理動作を想定しておらず、複数の
パケットを同一時刻に送出する設定をＣＡＭに登録した
場合には同一時刻に設定したパケットが１個しか出力さ
れない、あるいはＣＡＭが複数のアドレスを同時に返す
ことができないため、エラーを返してしまい、１個もパ
ケットを送信することができずに、バッファにパケット
が次々に溜まることとなり、バッファオーバフローが発
生し、パケット送出処理を期待通りに行うことができな
いという問題が発生する。
従来の提案手法においては、同一時刻に出力するパケッ
トが存在した場合の処理動作を想定しておらず、複数の
パケットを同一時刻に送出する設定をＣＡＭに登録した
場合には同一時刻に設定したパケットが１個しか出力さ
れない、あるいはＣＡＭが複数のアドレスを同時に返す
ことができないため、エラーを返してしまい、１個もパ
ケットを送信することができずに、バッファにパケット
が次々に溜まることとなり、バッファオーバフローが発
生し、パケット送出処理を期待通りに行うことができな
いという問題が発生する。
【００１４】また、上記の従来の提案手法では一定間隔
で各バッファからパケットを送出することを想定してい
るので、パケットが到着した時刻とトラヒックパラメー
タとによって送出時刻を決定する場合に利用することが
できない。
で各バッファからパケットを送出することを想定してい
るので、パケットが到着した時刻とトラヒックパラメー
タとによって送出時刻を決定する場合に利用することが
できない。
【００１５】そこで、本発明の目的は上記の問題点を解
消し、ＣＡＭを利用して同一時刻に複数のパケットを設
定する場合でも、同一時刻に設定された複数のパケット
があることを認識して複数のパケットを送出することが
できるシェーパ及びそれに用いるスケジューリング方法
を提供することにある。
消し、ＣＡＭを利用して同一時刻に複数のパケットを設
定する場合でも、同一時刻に設定された複数のパケット
があることを認識して複数のパケットを送出することが
できるシェーパ及びそれに用いるスケジューリング方法
を提供することにある。
【００１６】また、本発明の他の目的は、パケットが到
着した時刻とトラヒックパラメータとによって送出時刻
を決定する場合でも、送出する時刻を設定可能にするこ
とができるシェーパ及びそれに用いるスケジューリング
方法を提供することにある。
着した時刻とトラヒックパラメータとによって送出時刻
を決定する場合でも、送出する時刻を設定可能にするこ
とができるシェーパ及びそれに用いるスケジューリング
方法を提供することにある。
【００１７】
【課題を解決するための手段】本発明によるシェーパ
は、ネットワークにおいてセル及びパケットを制御する
ためのシェーパであって、前記セル及び前記パケットを
設定した理想時刻に送出する時に該当する前記セル及び
前記パケットを送信すべき時刻が経過したことを検出す
るための連想メモリと、現在時刻を計時するタイマと、
前記タイマからの現在時刻を基に前記連想メモリを検索
して前記現在時刻に送出するパケットの有無を検索する
現在時刻検索手段と、予め設定された伝送路のトラヒッ
クパラメータを用いて前記パケットの送出時刻を計算す
る計算手段とを備え、 前記理想時刻を前記連想メモリの
検索テーブルのフロー番号に対応するアドレスに設定す
るとともに、前記連想メモリの検索結果から得られるア
ドレスを、同一時刻に送出するパケットを示しかつリン
クされたデータ構造のポインタとして利用し、前記計算
手段で計算された送出時刻を前記連想メモリに設定時刻
として登録している。
は、ネットワークにおいてセル及びパケットを制御する
ためのシェーパであって、前記セル及び前記パケットを
設定した理想時刻に送出する時に該当する前記セル及び
前記パケットを送信すべき時刻が経過したことを検出す
るための連想メモリと、現在時刻を計時するタイマと、
前記タイマからの現在時刻を基に前記連想メモリを検索
して前記現在時刻に送出するパケットの有無を検索する
現在時刻検索手段と、予め設定された伝送路のトラヒッ
クパラメータを用いて前記パケットの送出時刻を計算す
る計算手段とを備え、 前記理想時刻を前記連想メモリの
検索テーブルのフロー番号に対応するアドレスに設定す
るとともに、前記連想メモリの検索結果から得られるア
ドレスを、同一時刻に送出するパケットを示しかつリン
クされたデータ構造のポインタとして利用し、前記計算
手段で計算された送出時刻を前記連想メモリに設定時刻
として登録している。
【００１８】
【００１９】本発明によるスケジューリング方法は、ネ
ットワークにおいてセル及びパケットを制御するための
シェーパに用いるスケジューリング方法であって、前記
セル及び前記パケットを設定した理想時刻に送出する時
に該当する前記セル及び前記パケットを送信すべき時刻
が経過したことを検出するための連想メモリを現在時刻
に基づいて検索して前記現在時刻に送出するパケットの
有無を検索するステップと、予め設定された伝送路のト
ラヒックパラメータを用いて前記パケットの送出時刻を
計算する第２のステップとを備え、 前記理想時刻を前記
連想メモリの検索テーブルのフロー番号に対応するアド
レスに設定するとともに、前記連想メモリの検索結果か
ら得られるアドレスを、同一時刻に送出するパケットを
示しかつリンクされたデータ構造のポインタとして利用
し、前記第２のステップで計算された送出時刻を前記連
想メモリに設定時刻として登録している。
ットワークにおいてセル及びパケットを制御するための
シェーパに用いるスケジューリング方法であって、前記
セル及び前記パケットを設定した理想時刻に送出する時
に該当する前記セル及び前記パケットを送信すべき時刻
が経過したことを検出するための連想メモリを現在時刻
に基づいて検索して前記現在時刻に送出するパケットの
有無を検索するステップと、予め設定された伝送路のト
ラヒックパラメータを用いて前記パケットの送出時刻を
計算する第２のステップとを備え、 前記理想時刻を前記
連想メモリの検索テーブルのフロー番号に対応するアド
レスに設定するとともに、前記連想メモリの検索結果か
ら得られるアドレスを、同一時刻に送出するパケットを
示しかつリンクされたデータ構造のポインタとして利用
し、前記第２のステップで計算された送出時刻を前記連
想メモリに設定時刻として登録している。
【００２０】
【００２１】すなわち、本発明のスケジューリング方法
は、ＡＴＭのセルあるいはＩＰパケット（以下、セル及
びＩＰパケットをパケットとする）等のパケットを設定
した理想時刻に送出する時に、該当パケットを送信すべ
き時刻が経過したことを検出する部分に連想メモリ（Ｃ
ＡＭ）を用いている。
は、ＡＴＭのセルあるいはＩＰパケット（以下、セル及
びＩＰパケットをパケットとする）等のパケットを設定
した理想時刻に送出する時に、該当パケットを送信すべ
き時刻が経過したことを検出する部分に連想メモリ（Ｃ
ＡＭ）を用いている。
【００２２】したがって、本発明のスケジューリング方
法は、理想時刻を連想メモリの検索テーブルのフロー番
号に対応するアドレスに設定することで、連想メモリに
登録するアドレスをパケットが属するフロー番号から決
定することが可能となり、データ登録されていない空き
テーブルエントリを検索する必要がなくなるという特徴
を持っている。
法は、理想時刻を連想メモリの検索テーブルのフロー番
号に対応するアドレスに設定することで、連想メモリに
登録するアドレスをパケットが属するフロー番号から決
定することが可能となり、データ登録されていない空き
テーブルエントリを検索する必要がなくなるという特徴
を持っている。
【００２３】連想メモリの検索結果から得られるアドレ
スを、同一時刻に送出するパケットを示しかつリンクさ
れたデータ構造のポインタとして利用することで、連想
メモリを利用した検索を行った場合、複数のパケットが
同一時刻に重なった場合でも複数のパケットを順番に送
出することが可能となる。
スを、同一時刻に送出するパケットを示しかつリンクさ
れたデータ構造のポインタとして利用することで、連想
メモリを利用した検索を行った場合、複数のパケットが
同一時刻に重なった場合でも複数のパケットを順番に送
出することが可能となる。
【００２４】本発明のスケジューリング方法は、ネット
ワーク内にパケットを転送する前にユーザの申告したト
ラヒックパラメータ通りにパケットを転送し直す方法を
用いる場合に利用する。
ワーク内にパケットを転送する前にユーザの申告したト
ラヒックパラメータ通りにパケットを転送し直す方法を
用いる場合に利用する。
【００２５】
【発明の実施の形態】次に、本発明の一実施例について
図面を参照して説明する。図１は本発明の一実施例によ
るシェーパの構成を示すブロック図である。図１におい
て、シェーパ１はバッファ管理部１０と、送出パケット
登録部１１と、同一時刻重複検索部１２と、検索データ
クリア部１３と、現在時刻検索部１４と、同一時刻送出
パケット群送信要求部１５と、スケジューリング要求部
１６と、タイマ（Ｔｉｍｅｒ）部１７と、ＣＡＭ（連想
メモリ）インタフェース部１８と、パケットバッファ部
２０と、トラヒックパラメータ部２１と、同一時刻送出
パケット管理テーブル部２２と、連想メモリ（ＣＡＭ）
２３とから構成されている。
図面を参照して説明する。図１は本発明の一実施例によ
るシェーパの構成を示すブロック図である。図１におい
て、シェーパ１はバッファ管理部１０と、送出パケット
登録部１１と、同一時刻重複検索部１２と、検索データ
クリア部１３と、現在時刻検索部１４と、同一時刻送出
パケット群送信要求部１５と、スケジューリング要求部
１６と、タイマ（Ｔｉｍｅｒ）部１７と、ＣＡＭ（連想
メモリ）インタフェース部１８と、パケットバッファ部
２０と、トラヒックパラメータ部２１と、同一時刻送出
パケット管理テーブル部２２と、連想メモリ（ＣＡＭ）
２３とから構成されている。
【００２６】バッファ管理部１０はパケットの入出力処
理とパケットをフロー毎にパケットバッファ部２０に記
録する処理とを行う。パケットバッファ部２０はパケッ
トデータを記録する。
理とパケットをフロー毎にパケットバッファ部２０に記
録する処理とを行う。パケットバッファ部２０はパケッ
トデータを記録する。
【００２７】スケジューリング要求部１６はトラヒック
パラメータによってパケットの理想送出時刻を計算し、
同一時刻重複検索部１２にスケジューリング要求を出
す。トラヒックパラメータ部２１はトラヒックパラメー
タを保持する。
パラメータによってパケットの理想送出時刻を計算し、
同一時刻重複検索部１２にスケジューリング要求を出
す。トラヒックパラメータ部２１はトラヒックパラメー
タを保持する。
【００２８】同一時刻重複検索部１２は既に同一時刻に
送出設定されているパケットが無いか否かを検索する。
送出パケット登録部１１は送出時刻を連想メモリ２３に
設定し、同一時刻に出力するパケットを管理するテーブ
ルを設定する。同一時刻送出パケット管理テーブル部２
２は同一時刻に送出設定されたパケットを管理する。
送出設定されているパケットが無いか否かを検索する。
送出パケット登録部１１は送出時刻を連想メモリ２３に
設定し、同一時刻に出力するパケットを管理するテーブ
ルを設定する。同一時刻送出パケット管理テーブル部２
２は同一時刻に送出設定されたパケットを管理する。
【００２９】タイマ部１７は時刻をカウントし、現在時
刻検索部１４とスケジューリング要求部１６とに現在時
刻の値を出力する。現在時刻検索部１４は現在時刻の送
出パケットを検索する。検索データクリア部１３は検索
データの削除処理を行う。
刻検索部１４とスケジューリング要求部１６とに現在時
刻の値を出力する。現在時刻検索部１４は現在時刻の送
出パケットを検索する。検索データクリア部１３は検索
データの削除処理を行う。
【００３０】同一時刻送出パケット群送信要求部１５は
現在時刻検索部１４によって検索一致したアドレスを指
定し、パケット送信の要求を行う。ＣＡＭインタフェー
ス部１８は連想メモリ２３へのデータ検索、データ書込
みのインタフェースである。
現在時刻検索部１４によって検索一致したアドレスを指
定し、パケット送信の要求を行う。ＣＡＭインタフェー
ス部１８は連想メモリ２３へのデータ検索、データ書込
みのインタフェースである。
【００３１】連想メモリ２３は記憶装置の一種で、自回
路に登録されているテーブルの中から検索データに一致
するテーブルを検索し、一致するテーブルを検出した場
合にテーブルが登録されているアドレスを結果として出
力する機能を持つ。
路に登録されているテーブルの中から検索データに一致
するテーブルを検索し、一致するテーブルを検出した場
合にテーブルが登録されているアドレスを結果として出
力する機能を持つ。
【００３２】図２は図１の連想メモリ２３内のテーブル
を示す図である。図２において、連想メモリ２３の検索
は有効／無効ビット・フィールドと、設定時刻・フィー
ルドとが一つの登録データとなるデータに対して行われ
る。
を示す図である。図２において、連想メモリ２３の検索
は有効／無効ビット・フィールドと、設定時刻・フィー
ルドとが一つの登録データとなるデータに対して行われ
る。
【００３３】有効／無効ビット・フィールドは対応する
アドレスのテーブルが連想メモリ２３の検索によって検
索一致させるか否かを指定するためのビットを格納する
領域である。テーブルに一致させない時には“０”を登
録しておき、検索データには常に“１”を利用する。設
定時刻・フィールドは送出する設定時刻を登録する領域
である。
アドレスのテーブルが連想メモリ２３の検索によって検
索一致させるか否かを指定するためのビットを格納する
領域である。テーブルに一致させない時には“０”を登
録しておき、検索データには常に“１”を利用する。設
定時刻・フィールドは送出する設定時刻を登録する領域
である。
【００３４】図３及び図４は図１の同一時刻送出パケッ
ト管理テーブル２２が保持するテーブルを示す図であ
る。図３及び図４において、同一時刻送出パケット管理
テーブル２２が保持するテーブルは同一時刻に送出する
パケットを管理するためのテーブルである。
ト管理テーブル２２が保持するテーブルを示す図であ
る。図３及び図４において、同一時刻送出パケット管理
テーブル２２が保持するテーブルは同一時刻に送出する
パケットを管理するためのテーブルである。
【００３５】同じフローに属するパケットは先に入力し
たパケットを先に出力するので、パケットバッファ部２
０で保持されたフローの先頭に位置するパケットを送出
することになる。よって、フロー番号を利用して同一時
刻に送出するパケットを管理することができる。
たパケットを先に出力するので、パケットバッファ部２
０で保持されたフローの先頭に位置するパケットを送出
することになる。よって、フロー番号を利用して同一時
刻に送出するパケットを管理することができる。
【００３６】上記のテーブルはリンク構造を利用し、先
頭（ＴＯＰ）及び最後尾（ＴＡＩＬ）の位置を保持する
テーブル（図３参照）と、リンクされて接続されるフロ
ー番号の位置（ＮＥＸＴ）を示すテーブル（図４参照）
とを用いる。
頭（ＴＯＰ）及び最後尾（ＴＡＩＬ）の位置を保持する
テーブル（図３参照）と、リンクされて接続されるフロ
ー番号の位置（ＮＥＸＴ）を示すテーブル（図４参照）
とを用いる。
【００３７】図５及び図６は同一フローに属するパケッ
トを管理するテーブルを示す図である。図５及び図６に
おいて、同一フローに属するパケットを管理するテーブ
ルはパケットバッファ部２０が保持している。同一フロ
ーに属するパケットは同一時刻送出パケット管理テーブ
ル２２と同様に、リンク構造を利用している。
トを管理するテーブルを示す図である。図５及び図６に
おいて、同一フローに属するパケットを管理するテーブ
ルはパケットバッファ部２０が保持している。同一フロ
ーに属するパケットは同一時刻送出パケット管理テーブ
ル２２と同様に、リンク構造を利用している。
【００３８】図７は同一時刻に送出するパケットが１パ
ケットしかない状態を示す図であり、図８は同一時刻に
送出するパケットが複数パケット存在する状態を示す図
であり、図９及び図１０は本発明の一実施例によるシェ
ーパのパケット入力時の動作を示すフローチャートであ
り、図１１及び図１２は本発明の一実施例によるシェー
パのパケット出力時の動作を示すフローチャートであ
る。これら図１〜図１２を参照して本発明の一実施例に
よるシェーパの動作について説明する。尚、図９〜図１
２に示す処理動作はシェーパ１の各部が図示せぬ制御メ
モリのプログラムを実行することで実現され、制御メモ
リとしてはＲＯＭ（リードオンリメモリ）やＩＣ（集積
回路）メモリ等が使用可能である。
ケットしかない状態を示す図であり、図８は同一時刻に
送出するパケットが複数パケット存在する状態を示す図
であり、図９及び図１０は本発明の一実施例によるシェ
ーパのパケット入力時の動作を示すフローチャートであ
り、図１１及び図１２は本発明の一実施例によるシェー
パのパケット出力時の動作を示すフローチャートであ
る。これら図１〜図１２を参照して本発明の一実施例に
よるシェーパの動作について説明する。尚、図９〜図１
２に示す処理動作はシェーパ１の各部が図示せぬ制御メ
モリのプログラムを実行することで実現され、制御メモ
リとしてはＲＯＭ（リードオンリメモリ）やＩＣ（集積
回路）メモリ等が使用可能である。
【００３９】パケットの入力処理の場合、バッファ管理
部１０はパケットが入力されると（図９ステップＳ
１）、入力されたパケットとパケットのフロー番号とを
受取り、フロー番号に対応するバッファにパケットを接
続する（図９ステップＳ２）。フロー番号に対応するバ
ッファにパケットが無い場合には、フロー番号の先頭の
パケットである。
部１０はパケットが入力されると（図９ステップＳ
１）、入力されたパケットとパケットのフロー番号とを
受取り、フロー番号に対応するバッファにパケットを接
続する（図９ステップＳ２）。フロー番号に対応するバ
ッファにパケットが無い場合には、フロー番号の先頭の
パケットである。
【００４０】先頭パケットの場合には連想メモリ２３よ
ってスケジューリング登録がされていないため（図９ス
テップＳ３）、スケジューリング要求部１６に対して連
想メモリ２３へのスケジューリング登録の要求を行う
（図９ステップＳ５）。フロー番号の先頭パケットでは
ない時（図９ステップＳ３）、バッファ管理部１０はパ
ケットを接続する処理のみを行い（図９ステップＳ
４）、パケットが入力した場合の処理を終了する。
ってスケジューリング登録がされていないため（図９ス
テップＳ３）、スケジューリング要求部１６に対して連
想メモリ２３へのスケジューリング登録の要求を行う
（図９ステップＳ５）。フロー番号の先頭パケットでは
ない時（図９ステップＳ３）、バッファ管理部１０はパ
ケットを接続する処理のみを行い（図９ステップＳ
４）、パケットが入力した場合の処理を終了する。
【００４１】スケジューリング要求部１６はバッファ管
理部１０からスケジューリング設定するフロー番号を受
取り、対応するフロー番号のトラヒックパラメータをト
ラヒックパラメータテーブル２１から取得し（図９ステ
ップＳ６）、パケットがトラヒックパラメータを違反し
ていないか否かを検出する処理を行う（図９ステップＳ
７）。
理部１０からスケジューリング設定するフロー番号を受
取り、対応するフロー番号のトラヒックパラメータをト
ラヒックパラメータテーブル２１から取得し（図９ステ
ップＳ６）、パケットがトラヒックパラメータを違反し
ていないか否かを検出する処理を行う（図９ステップＳ
７）。
【００４２】スケジューリング要求部１６はトラヒック
パラメータを違反していた場合（図９ステップＳ８）、
パケットに遅延を与え、タイマ部１７が出力する現在時
刻を基に当該パケットを送出する時刻を計算するととも
に、同一時刻重複検索部１２に検索要求を出す（図１０
ステップＳ９）。
パラメータを違反していた場合（図９ステップＳ８）、
パケットに遅延を与え、タイマ部１７が出力する現在時
刻を基に当該パケットを送出する時刻を計算するととも
に、同一時刻重複検索部１２に検索要求を出す（図１０
ステップＳ９）。
【００４３】トラヒックパラメータはトラヒックモデル
によって異なるが、ＡＴＭ技術を用いたネットワークで
はＬｅａｋｙ Ｂｕｃｋｅｔモデル、ＩＰを用いたネッ
トワークではＴｏｋｅｎ Ｂｕｃｋｅｔモデルが利用さ
れる。
によって異なるが、ＡＴＭ技術を用いたネットワークで
はＬｅａｋｙ Ｂｕｃｋｅｔモデル、ＩＰを用いたネッ
トワークではＴｏｋｅｎ Ｂｕｃｋｅｔモデルが利用さ
れる。
【００４４】同一時刻重複検索部１２はスケジューリン
グ要求部１６から要求を受取ると、まず連想メモリ２３
に既に同一時刻に送出するパケットが存在するか否か
を、連想メモリ２３を検索して調べる（図１０ステップ
Ｓ１０）。連想メモリ２３への検索要求の方法、検索デ
ータは現在時刻検索部１４と同様である。但し、検索デ
ータに使う時刻が現在時刻ではなく、スケジューリング
要求部１６から受取ったパケットの送出時刻である。
グ要求部１６から要求を受取ると、まず連想メモリ２３
に既に同一時刻に送出するパケットが存在するか否か
を、連想メモリ２３を検索して調べる（図１０ステップ
Ｓ１０）。連想メモリ２３への検索要求の方法、検索デ
ータは現在時刻検索部１４と同様である。但し、検索デ
ータに使う時刻が現在時刻ではなく、スケジューリング
要求部１６から受取ったパケットの送出時刻である。
【００４５】検索一致してアドレスが返された時には同
一時刻に送出するパケットが既に連想メモリ２３に登録
されていた時であり（図１０ステップＳ１１）、同一時
刻重複検索部１２は送出パケット登録部１１に対して返
されたアドレスを通知する（図１０ステップＳ１３）。
一時刻に送出するパケットが既に連想メモリ２３に登録
されていた時であり（図１０ステップＳ１１）、同一時
刻重複検索部１２は送出パケット登録部１１に対して返
されたアドレスを通知する（図１０ステップＳ１３）。
【００４６】一致したデータがなく、アドレスが返され
ない時には同一時刻に送出するパケットが連想メモリ２
３に登録されていない時であり（図１０ステップＳ１
１）、同一時刻重複検索部１２は送出パケット登録部１
１に対してスケジューリング要求部１６から要求された
パケットのフロー番号を通知する（図１０ステップＳ１
２）。
ない時には同一時刻に送出するパケットが連想メモリ２
３に登録されていない時であり（図１０ステップＳ１
１）、同一時刻重複検索部１２は送出パケット登録部１
１に対してスケジューリング要求部１６から要求された
パケットのフロー番号を通知する（図１０ステップＳ１
２）。
【００４７】具体的な例として、同一時刻に送出するパ
ケットが１パケットしかない状態を図７に示し、同一時
刻に送出するパケットが複数パケット存在する状態を図
８に示す。図８を参照すると、フロー番号２５４には時
刻Ｔ−１が登録されており、時刻Ｔ−１にパケットを送
出するための設定がされている。この場合、先頭は「２
５４」で、最後尾は「５」となっている。同一時刻のリ
スト構造を管理するテーブルを辿ると、フロー番号「２
５４」の次はフロー番号「１」、その次はフロー番号
「４」、最後にフロー番号「５」となっている。
ケットが１パケットしかない状態を図７に示し、同一時
刻に送出するパケットが複数パケット存在する状態を図
８に示す。図８を参照すると、フロー番号２５４には時
刻Ｔ−１が登録されており、時刻Ｔ−１にパケットを送
出するための設定がされている。この場合、先頭は「２
５４」で、最後尾は「５」となっている。同一時刻のリ
スト構造を管理するテーブルを辿ると、フロー番号「２
５４」の次はフロー番号「１」、その次はフロー番号
「４」、最後にフロー番号「５」となっている。
【００４８】送出パケット登録部１１は同一時刻重複検
索部１２から登録するパケットのフロー番号と設定する
送出時刻とが重複していることが通知されると（図１０
ステップＳ１４）、検索一致して得られたアドレスを受
取る（図１０ステップＳ１５）。また、送出パケット登
録部１１は連想メモリ２３への登録処理を行わず、同一
時刻送出パケット管理テーブル２２で管理される同一時
刻を示すリンク構造に登録するパケットのフロー番号を
接続する（図１０ステップＳ１６）。先頭と最後尾との
テーブルの位置は同一時刻重複検索部１２から受取った
アドレスを用いる。
索部１２から登録するパケットのフロー番号と設定する
送出時刻とが重複していることが通知されると（図１０
ステップＳ１４）、検索一致して得られたアドレスを受
取る（図１０ステップＳ１５）。また、送出パケット登
録部１１は連想メモリ２３への登録処理を行わず、同一
時刻送出パケット管理テーブル２２で管理される同一時
刻を示すリンク構造に登録するパケットのフロー番号を
接続する（図１０ステップＳ１６）。先頭と最後尾との
テーブルの位置は同一時刻重複検索部１２から受取った
アドレスを用いる。
【００４９】重複していなかったことが通知されると
（図１０ステップＳ１４）、送出パケット登録部１１は
フロー番号に対応する連想メモリ２３のアドレスに送出
時刻を設定し（図１０ステップＳ１７）、同一時刻送出
パケットテーブル２２にパケットを設定する（図１０ス
テップＳ１８）。この場合、リンク構造にはこの設定す
るパケットのみが存在することになる。つまり、先頭と
最後尾とが同じである。
（図１０ステップＳ１４）、送出パケット登録部１１は
フロー番号に対応する連想メモリ２３のアドレスに送出
時刻を設定し（図１０ステップＳ１７）、同一時刻送出
パケットテーブル２２にパケットを設定する（図１０ス
テップＳ１８）。この場合、リンク構造にはこの設定す
るパケットのみが存在することになる。つまり、先頭と
最後尾とが同じである。
【００５０】一方、パケットの出力処理の場合、現在時
刻検索部１４はタイマ部１７が出力する現在時刻を連想
メモリ２３の検索データとして用い、検索要求をＣＡＭ
インタフェース部１８に対して行う（図１１ステップＳ
２１）。検索データは有効／無効ビット・フィールドに
対応するビットを“１”にし、現在時刻を加えたデータ
である。
刻検索部１４はタイマ部１７が出力する現在時刻を連想
メモリ２３の検索データとして用い、検索要求をＣＡＭ
インタフェース部１８に対して行う（図１１ステップＳ
２１）。検索データは有効／無効ビット・フィールドに
対応するビットを“１”にし、現在時刻を加えたデータ
である。
【００５１】検索一致するデータが連想メモリ２３に登
録されている場合（図１１ステップＳ２２）、連想メモ
リ２３からデータが登録されているアドレスが結果とし
て現在時刻検索部１４に返される（図１１ステップＳ２
３）。
録されている場合（図１１ステップＳ２２）、連想メモ
リ２３からデータが登録されているアドレスが結果とし
て現在時刻検索部１４に返される（図１１ステップＳ２
３）。
【００５２】アドレスが返されると、現在時刻検索部１
４はパケットの送出要求を同一時刻送出パケット群送信
要求部１５に対して行い（図１１ステップＳ２４）、同
時に一致したデータを連想メモリ２３から削除するため
に検索データクリア部１３に登録データの削除要求を行
う（図１１ステップＳ２５）。
４はパケットの送出要求を同一時刻送出パケット群送信
要求部１５に対して行い（図１１ステップＳ２４）、同
時に一致したデータを連想メモリ２３から削除するため
に検索データクリア部１３に登録データの削除要求を行
う（図１１ステップＳ２５）。
【００５３】検索データクリア部１３は連想メモリ２３
に登録された時刻を示すデータを削除する処理を行う
（図１１ステップＳ２６）。具体的に、検索データクリ
ア部１３は連想メモリ２３のデータ（図２参照）の有効
／無効ビットを“０”に設定する。この場合、現在時刻
検索部１４は有効／無効ビットに対応する検索データの
ビットを“１”にして検索するため、現在時刻検索部１
４では検索一致しない。
に登録された時刻を示すデータを削除する処理を行う
（図１１ステップＳ２６）。具体的に、検索データクリ
ア部１３は連想メモリ２３のデータ（図２参照）の有効
／無効ビットを“０”に設定する。この場合、現在時刻
検索部１４は有効／無効ビットに対応する検索データの
ビットを“１”にして検索するため、現在時刻検索部１
４では検索一致しない。
【００５４】検索一致するデータが連想メモリ２３に登
録されていない場合には（図１１ステップＳ２２）、処
理を終了し、タイマ部１７が次の時刻を出力するまで待
つ。タイマ部１７が次の時刻を出力した時には再び検索
を行う。
録されていない場合には（図１１ステップＳ２２）、処
理を終了し、タイマ部１７が次の時刻を出力するまで待
つ。タイマ部１７が次の時刻を出力した時には再び検索
を行う。
【００５５】同一時刻送出パケット群送信要求部１５は
現在時刻検索部１４から受取ったアドレスをバッファ管
理部１０に通知するインタフェース処理を行い、バッフ
ァ管理部１０に送信要求を出す（図１１ステップＳ２
７）。
現在時刻検索部１４から受取ったアドレスをバッファ管
理部１０に通知するインタフェース処理を行い、バッフ
ァ管理部１０に送信要求を出す（図１１ステップＳ２
７）。
【００５６】バッファ管理部１０は同一時刻送出パケッ
ト群送信要求部１５からパケットの送信要求があると、
同一時刻送出パケット群送信要求部１５から連想メモリ
２３で検索一致したアドレスを受取る。受取ったアドレ
スは同一時刻送出パケット管理テーブル２２が保持する
先頭と最後尾とを保持するテーブル（図３参照）の位置
を示している。
ト群送信要求部１５からパケットの送信要求があると、
同一時刻送出パケット群送信要求部１５から連想メモリ
２３で検索一致したアドレスを受取る。受取ったアドレ
スは同一時刻送出パケット管理テーブル２２が保持する
先頭と最後尾とを保持するテーブル（図３参照）の位置
を示している。
【００５７】このアドレスが示す先頭と最後尾との値、
先頭の値が示すリンク構造の接続を管理するテーブル
（図４参照）の位置を辿り、最後尾の値が示す位置まで
が同一時刻に送出するフロー番号、つまりフロー番号に
対応するバッファの先頭パケットを示す。
先頭の値が示すリンク構造の接続を管理するテーブル
（図４参照）の位置を辿り、最後尾の値が示す位置まで
が同一時刻に送出するフロー番号、つまりフロー番号に
対応するバッファの先頭パケットを示す。
【００５８】バッファ管理部１０は先頭から最後尾を辿
り（図１１ステップＳ２８）、パケットバッファ部２０
からパケットを取出し、そのパケットを出力する（図１
１ステップＳ２９）。パケットを出力する時には、バッ
ファ管理部１０とパケットバッファ部２０とで管理され
る同一フロー番号に属するパケットをリンク構造から削
除する（図１１ステップＳ３０）。
り（図１１ステップＳ２８）、パケットバッファ部２０
からパケットを取出し、そのパケットを出力する（図１
１ステップＳ２９）。パケットを出力する時には、バッ
ファ管理部１０とパケットバッファ部２０とで管理され
る同一フロー番号に属するパケットをリンク構造から削
除する（図１１ステップＳ３０）。
【００５９】この時、同一フローに属するパケットがま
だ残っている場合には（図１１ステップＳ３１）、まだ
残っているパケットのスケジューリングを行うために、
スケジューリング要求部１６に連想メモリ２３へのスケ
ジューリング登録の要求を行う（図１１ステップＳ３
２）。
だ残っている場合には（図１１ステップＳ３１）、まだ
残っているパケットのスケジューリングを行うために、
スケジューリング要求部１６に連想メモリ２３へのスケ
ジューリング登録の要求を行う（図１１ステップＳ３
２）。
【００６０】このように、設定時刻をデータとして連想
メモリ２３に登録し、現在時刻検索部１４が現在時刻を
検索キーとして連想メモリ２３を検索することで、設定
時刻を登録したアドレスが得られるため、バッファ管理
部１０はそのアドレスを基にフロー番号を得ることがで
きるので、ハードウェアの大規模化を抑制しかつ大容量
のメモリを必要としない。
メモリ２３に登録し、現在時刻検索部１４が現在時刻を
検索キーとして連想メモリ２３を検索することで、設定
時刻を登録したアドレスが得られるため、バッファ管理
部１０はそのアドレスを基にフロー番号を得ることがで
きるので、ハードウェアの大規模化を抑制しかつ大容量
のメモリを必要としない。
【００６１】また、同一時刻送出パケット管理テーブル
２２においては同一時刻に出力するパケットをリンク構
造で管理し、送出時刻で連想メモリ２３を検索する際
に、同一時刻重複検索部１２において予め設定された時
刻の検索を行うため、同一時刻に送出するパケットが複
数あっても、同一時刻にパケットを送出することができ
る。
２２においては同一時刻に出力するパケットをリンク構
造で管理し、送出時刻で連想メモリ２３を検索する際
に、同一時刻重複検索部１２において予め設定された時
刻の検索を行うため、同一時刻に送出するパケットが複
数あっても、同一時刻にパケットを送出することができ
る。
【００６２】さらに、バッファ管理部１０にパケットが
到着した時に、バッファ管理部１０がスケジューリング
要求をスケジューリング要求部１６に出し、スケジュー
リング要求部１６がトラヒックパラメータを利用してパ
ケットの送出時刻を計算することで、一定間隔以外の時
刻を設定することができる。
到着した時に、バッファ管理部１０がスケジューリング
要求をスケジューリング要求部１６に出し、スケジュー
リング要求部１６がトラヒックパラメータを利用してパ
ケットの送出時刻を計算することで、一定間隔以外の時
刻を設定することができる。
【００６３】さらにまた、バッファ管理部１０がパケッ
トを出力した時に、出力したパケットの属するフロー番
号のパケットがバッファに保持されているか否かをバッ
ファ管理部１０で検出し、同じフロー番号に属するパケ
ットが保持されていた時にバッファ管理部１０がスケジ
ューリング要求部１６にスケジューリングの要求を出す
ため、パケットを一定間隔で送出することができるだけ
でなく、送出時刻をトラヒックパラメータから計算して
任意の時刻に設定（スケジューリング）することができ
る。
トを出力した時に、出力したパケットの属するフロー番
号のパケットがバッファに保持されているか否かをバッ
ファ管理部１０で検出し、同じフロー番号に属するパケ
ットが保持されていた時にバッファ管理部１０がスケジ
ューリング要求部１６にスケジューリングの要求を出す
ため、パケットを一定間隔で送出することができるだけ
でなく、送出時刻をトラヒックパラメータから計算して
任意の時刻に設定（スケジューリング）することができ
る。
【００６４】上記の本発明の一実施例では同一時刻送出
パケット管理テーブル２２とパケットバッファ部２０と
に対してリンク構造を持つデータフォーマットを用いて
いるが、同一時刻送出パケット管理テーブル２２におい
ては最大フロー数分のデータが格納できるＦＩＦＯ（Ｆ
ｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューデータ構
造をフロー数個用意して実現してもよい。
パケット管理テーブル２２とパケットバッファ部２０と
に対してリンク構造を持つデータフォーマットを用いて
いるが、同一時刻送出パケット管理テーブル２２におい
ては最大フロー数分のデータが格納できるＦＩＦＯ（Ｆ
ｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューデータ構
造をフロー数個用意して実現してもよい。
【００６５】また、パケットバッファ部２０において
も、各フロー番号に分けてバッファを管理することがで
き、各フローの先頭パケットを取出す機構、各フローの
最後尾にパケットを追加する機構を持つデータ構造を持
つアルゴリズムであれば何でもよい。
も、各フロー番号に分けてバッファを管理することがで
き、各フローの先頭パケットを取出す機構、各フローの
最後尾にパケットを追加する機構を持つデータ構造を持
つアルゴリズムであれば何でもよい。
【００６６】
【発明の効果】以上説明したように本発明のシェーパに
よれば、ネットワークにおいてセル及びパケットを制御
するためのシェーパにおいて、セル及びパケットを設定
した理想時刻に送出する時に該当するセル及びパケット
を送信すべき時刻が経過したことを検出するための連想
メモリと、現在時刻を計時するタイマとを設け、タイマ
からの現在時刻を基に連想メモリを検索して現在時刻に
送出するパケットの有無を検索することによって、連想
メモリを利用して同一時刻に複数のパケットを設定する
場合でも、同一時刻に設定された複数のパケットがある
ことを認識して複数のパケットを送出することができる
という効果がある。
よれば、ネットワークにおいてセル及びパケットを制御
するためのシェーパにおいて、セル及びパケットを設定
した理想時刻に送出する時に該当するセル及びパケット
を送信すべき時刻が経過したことを検出するための連想
メモリと、現在時刻を計時するタイマとを設け、タイマ
からの現在時刻を基に連想メモリを検索して現在時刻に
送出するパケットの有無を検索することによって、連想
メモリを利用して同一時刻に複数のパケットを設定する
場合でも、同一時刻に設定された複数のパケットがある
ことを認識して複数のパケットを送出することができる
という効果がある。
【００６７】また、本発明の他のシェーパによれば、上
記の構成のほかに、予め設定された伝送路のトラヒック
パラメータを用いてパケットの送出時刻を計算する手段
を設け、その計算された送出時刻を連想メモリに設定時
刻として登録することによって、パケットが到着した時
刻とトラヒックパラメータとによって送出時刻を決定す
る場合でも、送出する時刻を設定可能にすることができ
るという効果がある。
記の構成のほかに、予め設定された伝送路のトラヒック
パラメータを用いてパケットの送出時刻を計算する手段
を設け、その計算された送出時刻を連想メモリに設定時
刻として登録することによって、パケットが到着した時
刻とトラヒックパラメータとによって送出時刻を決定す
る場合でも、送出する時刻を設定可能にすることができ
るという効果がある。
【図１】本発明の一実施例によるシェーパの構成を示す
ブロック図である。
ブロック図である。
【図２】図１の連想メモリ内のテーブルを示す図であ
る。
る。
【図３】図１の同一時刻送出パケット管理テーブルが保
持するテーブルを示す図である。
持するテーブルを示す図である。
【図４】図１の同一時刻送出パケット管理テーブルが保
持するテーブルを示す図である。
持するテーブルを示す図である。
【図５】同一フローに属するパケットを管理するテーブ
ルを示す図である。
ルを示す図である。
【図６】同一フローに属するパケットを管理するテーブ
ルを示す図である。
ルを示す図である。
【図７】同一時刻に送出するパケットが１パケットしか
ない状態を示す図である。
ない状態を示す図である。
【図８】同一時刻に送出するパケットが複数パケット存
在する状態を示す図である。
在する状態を示す図である。
【図９】本発明の一実施例によるシェーパのパケット入
力時の動作を示すフローチャートである。
力時の動作を示すフローチャートである。
【図１０】本発明の一実施例によるシェーパのパケット
入力時の動作を示すフローチャートである。
入力時の動作を示すフローチャートである。
【図１１】本発明の一実施例によるシェーパのパケット
出力時の動作を示すフローチャートである。
出力時の動作を示すフローチャートである。
【図１２】本発明の一実施例によるシェーパのパケット
出力時の動作を示すフローチャートである。
出力時の動作を示すフローチャートである。
１ シェーパ
１０ バッファ管理部
１１ 送出パケット登録部
１２ 同一時刻重複検索部
１３ 検索データクリア部
１４ 現在時刻検索部
１５ 同一時刻送出パケット群送信要求部
１６ スケジューリング要求部
１７ タイマ部
１８ ＣＡＭインタフェース部
２０ パケットバッファ部
２１ トラヒックパラメータ部
２２ 同一時刻送出パケット管理テーブル部
２３ 連想メモリ（ＣＡＭ）
Claims (16)
- 【請求項１】 ネットワークにおいてセル及びパケット
を制御するためのシェーパであって、 前記セル及び前記パケットを設定した理想時刻に送出す
る時に該当する前記セル及び前記パケットを送信すべき
時刻が経過したことを検出するための連想メモリと、現
在時刻を計時するタイマと、前記タイマからの現在時刻
を基に前記連想メモリを検索して前記現在時刻に送出す
るパケットの有無を検索する現在時刻検索手段と、予め
設定された伝送路のトラヒックパラメータを用いて前記
パケットの送出時刻を計算する計算手段とを有し、 前記理想時刻を前記連想メモリの検索テーブルのフロー
番号に対応するアドレスに設定するとともに、前記連想
メモリの検索結果から得られるアドレスを、同一時刻に
送出するパケットを示しかつリンクされたデータ構造の
ポインタとして利用し、前記計算手段で計算された送出
時刻を前記連想メモリに設定時刻として登録 することを
特徴とするシェーパ。 - 【請求項２】 前記現在時刻検索手段は、前記タイマか
らの現在時刻を前記連想メモリの検索データフォーマッ
トに直し、その検索データフォーマットで前記連想メモ
リを検索することを特徴とする請求項１記載のシェー
パ。 - 【請求項３】 前記現在時刻検索手段は、前記現在時刻
に送出するパケットがあることを検出した時に当該パケ
ットの登録情報を前記連想メモリから削除するよう指示
しかつ当該パケットの出力を指示することを特徴とする
請求項１または請求項２記載のシェーパ。 - 【請求項４】 前記連想メモリへのスケジューリング時
刻設定の要求時にその設定時刻を基に前記連想メモリを
検索して当該設定時刻に送出するパケットの重複の有無
を検索する同一時刻重複検索手段を含むことを特徴とす
る請求項１から請求項３のいずれか記載のシェーパ。 - 【請求項５】 前記同一時刻重複検索手段は、前記設定
時刻を前記連想メモリの検索データフォーマットに直
し、その検索データフォーマットで前記連想メモリを検
索することを特徴とする請求項４記載のシェーパ。 - 【請求項６】 前記同一時刻重複検索手段で前記パケッ
トの重複が検出された時に前記設定時刻に送出するパケ
ットのフロー番号を同一時刻に送出されるパケットにリ
ンク接続して追加する送出パケット登録手段を含むこと
を特徴とする請求項４または請求項５記載のシェーパ。 - 【請求項７】 前記送出パケット登録手段は、前記同一
時刻重複検索手段で前記パケットの重複が検出されなか
った時に前記設定時刻に送出するパケットのフロー番号
を前記連想メモリのアドレスとして前記設定時刻を前記
連想メモリに登録することを特徴とする請求項６記載の
シェーパ。 - 【請求項８】 前記連想メモリに設定時刻が設定されて
いない時に前記連想メモリの検索で一致しないように前
記連想メモリの登録情報の一部に有効及び無効の一方を
示す有効／無効情報を付加し、前記現在時刻検索手段
は、前記連想メモリの検索時に前記有効／無効情報に基
づいて前記現在時刻に送出するパケットの有無を検索す
ることを特徴とする請求項１から請求項７のいずれか記
載のシェーパ。 - 【請求項９】 ネットワークにおいてセル及びパケット
を制御するためのシェーパに用いるスケジューリング方
法であって、 前記セル及び前記パケットを設定した理想時刻に送出す
る時に該当する前記セル及び前記パケットを送信すべき
時刻が経過したことを検出するための連想メモリを現在
時刻に基づいて検索して前記現在時刻に送出するパケッ
トの有無を検索する第１のステップと、予め設定された
伝送路のトラヒックパラメータを用いて前記パケットの
送出時刻を計算する第２のステップとを有し、 前記理想時刻を前記連想メモリの検索テーブルのフロー
番号に対応するアドレスに設定するとともに、前記連想
メモリの検索結果から得られるアドレスを、同一時刻に
送出するパケットを示しかつリンクされたデータ構造の
ポインタとして利用し、前記第２のステップで計算され
た送出時刻を前記連想メモリに設定時刻として登録 する
ことを特徴とするスケジューリング方法。 - 【請求項１０】 前記第１のステップは、前記タイマか
らの現在時刻を前記連想メモリの検索データフォーマッ
トに直し、その検索データフォーマットで前記連想メモ
リを検索することを特徴とする請求項９記載のスケジュ
ーリング方法。 - 【請求項１１】 前記第１のステップは、前記現在時刻
に送出するパケットがあることを検出した時に当該パケ
ットの登録情報を前記連想メモリから削除するよう指示
しかつ当該パケットの出力を指示することを特徴とする
請求項９または請求項１０記載のスケジューリング方
法。 - 【請求項１２】 前記連想メモリへのスケジューリング
時刻設定の要求時にその設定時刻を基に前記連想メモリ
を検索して当該設定時刻に送出するパケットの重複の有
無を検索する第３のステップを含むことを特徴とする請
求項９から請求項１１のいずれか記載のスケジューリン
グ方法。 - 【請求項１３】 前記第３のステップは、前記設定時刻
を前記連想メモリの検索データフォーマットに直し、そ
の検索データフォーマットで前記連想メモリを検索する
ことを特徴とする請求項１２記載のスケジューリング方
法。 - 【請求項１４】 前記第３のステップで前記パケットの
重複が検出された時に前記設定時刻に送出するパケット
のフロー番号を同一時刻に送出されるパケットにリンク
接続して追加するステップを含むことを特徴とする請求
項１２または請求項１３記載のスケジューリング方法。 - 【請求項１５】 前記第３のステップで前記パケットの
重複が検出されなかった時に前記設定時刻に送出するパ
ケットのフロー番号を前記連想メモリのアドレスとして
前記設定時刻を前記連想メモリに登録するステップを含
むことを特徴とする請求項１２から請求項１４のいずれ
か記載のスケジューリング方法。 - 【請求項１６】 前記連想メモリに設定時刻が設定され
ていない時に前記連想メモリの検索で一致しないように
前記連想メモリの登録情報の一部に有効及び無効の一方
を示す有効／無効情報を付加し、 前記第１のステップは、前記連想メモリの検索時に前記
有効／無効情報に基づいて前記現在時刻に送出するパケ
ットの有無を検索することを特徴とする請求項９から請
求項１５のいずれか記載のスケジューリング方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000009602A JP3446704B2 (ja) | 2000-01-19 | 2000-01-19 | シェーパ及びそれに用いるスケジューリング方法 |
| US09/764,283 US20010008530A1 (en) | 2000-01-19 | 2001-01-19 | Shaper and scheduling method for use in the same |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000009602A JP3446704B2 (ja) | 2000-01-19 | 2000-01-19 | シェーパ及びそれに用いるスケジューリング方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001203702A JP2001203702A (ja) | 2001-07-27 |
| JP3446704B2 true JP3446704B2 (ja) | 2003-09-16 |
Family
ID=18537731
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000009602A Expired - Fee Related JP3446704B2 (ja) | 2000-01-19 | 2000-01-19 | シェーパ及びそれに用いるスケジューリング方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US20010008530A1 (ja) |
| JP (1) | JP3446704B2 (ja) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4258996B2 (ja) * | 2001-06-05 | 2009-04-30 | 沖電気工業株式会社 | スケジューリング装置およびセル通信装置 |
| US20030128686A1 (en) * | 2001-12-06 | 2003-07-10 | Hur Nam Chun | Variable delay buffer |
| CN100358314C (zh) * | 2003-10-28 | 2007-12-26 | 华为技术有限公司 | 一种实现异步转移模式下虚通道流量控制的方法及装置 |
| US20060161647A1 (en) * | 2004-12-22 | 2006-07-20 | Waldemar Wojtkiewicz | Method and apparatus providing measurement of packet latency in a processor |
| US20090323529A1 (en) * | 2008-06-27 | 2009-12-31 | Ericsson Inc. | Apparatus with network traffic scheduler and method |
| US20100166007A1 (en) * | 2008-12-30 | 2010-07-01 | Jeremy Horner | Advanced Elastic Time Recovery Mechanism Using Wildcard Searches |
| US8705552B1 (en) | 2010-02-09 | 2014-04-22 | Marvell International Ltd. | Controlling latency variations in a packet node |
| JP5609584B2 (ja) | 2010-08-30 | 2014-10-22 | 富士通株式会社 | シェーピング装置及び方法 |
| US8903925B2 (en) * | 2012-05-14 | 2014-12-02 | Microsoft Corporation | Scheduled messages in a scalable messaging system |
| FR3016762B1 (fr) * | 2014-01-17 | 2017-08-25 | Cie Ind Et Financiere D'ingenierie Ingenico | Methode de transmission de donnees chiffrees, methode de reception, dispositifs et programmes d'ordinateur correspondants. |
| US11689440B2 (en) * | 2019-02-06 | 2023-06-27 | Marvell Israel (M.I.S.L) Ltd. | Method and apparatus for transmit time timestamping |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5862206A (en) * | 1996-09-12 | 1999-01-19 | Cabletron Systems, Inc. | Method and apparatus for performing raw cell status report frequency mitigation on transmit in a network node |
-
2000
- 2000-01-19 JP JP2000009602A patent/JP3446704B2/ja not_active Expired - Fee Related
-
2001
- 2001-01-19 US US09/764,283 patent/US20010008530A1/en not_active Abandoned
Also Published As
| Publication number | Publication date |
|---|---|
| JP2001203702A (ja) | 2001-07-27 |
| US20010008530A1 (en) | 2001-07-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR102337092B1 (ko) | 트래픽 측정 방법, 장치, 및 시스템 | |
| Apostolopoulos et al. | QoS routing mechanisms and OSPF extensions | |
| US7477644B2 (en) | Method and system of efficient packet reordering | |
| JP3446704B2 (ja) | シェーパ及びそれに用いるスケジューリング方法 | |
| US6480489B1 (en) | Method and apparatus for data re-assembly with a high performance network interface | |
| US7133363B2 (en) | Storage switch with bandwidth control function | |
| US6266322B1 (en) | Dimensioning bandwidth and connection admission control for elastic traffic in high-speed communication networks | |
| US20050276230A1 (en) | Communication statistic information collection apparatus | |
| CN101241492B (zh) | 具有容量动态控制功能的内存数据存储装置及其实现方法 | |
| JP2005010970A (ja) | 分散キャッシュ制御方法、ネットワークシステムおよび当該ネットワークに用いられる制御サーバないしルータ | |
| US20140133320A1 (en) | Inter-packet interval prediction learning algorithm | |
| CN107453948A (zh) | 一种网络测量数据的存储方法及系统 | |
| Pan et al. | Nb-cache: Non-blocking in-network caching for high-performance content routers | |
| CN104270466B (zh) | 数据上报方法及相关设备 | |
| CN100499516C (zh) | 分组交换设备流量监测查询方法及线卡采集器 | |
| CN101453361A (zh) | 一种网站请求队列管理方法 | |
| US6507563B1 (en) | Methods and apparatus for controlling congestion within diverse protocol stacks | |
| JP3837670B2 (ja) | データ中継装置、連想メモリデバイス、および連想メモリデバイス利用情報検索方法 | |
| CN100435514C (zh) | 以太网驱动级底层过滤方法和系统 | |
| CN102812675B (zh) | 分组转送处理装置、方法 | |
| CN109981460A (zh) | 一种面向服务的融合网络、计算、存储一体化方法及装置 | |
| JP4409401B2 (ja) | パケット転送装置及びストレージシステム | |
| JP6266445B2 (ja) | パケット中継装置及びパケット中継方法 | |
| CN106339385A (zh) | 抓取网页的系统、网页抓取节点分配方法、抓取网页的方法 | |
| Heyman et al. | A new method for analyzing feedback-based protocols with applications to engineering Web traffic over the Internet |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070704 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080704 Year of fee payment: 5 |
|
| LAPS | Cancellation because of no payment of annual fees |