(57)【要約】パケットの優先制御が可能であり、かつ、受信パケットを格納するバッファの使用効率が高められ、部品コストが低減されたネットワークスイッチ装置を提供する。受信パケット（１０）は、バッファ制御回路（３）の制御の下で、その宛先のネットワークに対応するバッファに格納される。また、優先度判定回路（２）は、受信パケット（１０）の優先度クラスを判定する。バッファ制御回路（３）は、各バッファ（１−１）〜（ｎ）において、複数の優先度クラスのパケットを登録可能な送信キュー（４−１）〜（ｎ）を形成する。そして、受信パケット（１０）をバッファに書き込む際に、優先度判定回路（２）の判定に基づいて、対応する送信キュー内に登録された同じ優先度クラスのパケットのうち、最後に登録されたパケットの次に受信パケット（１０）が送信予約されるように制御する。
2004066570.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワーク間でパケットの転送を行うネットワークスイッチ装置において、
転送先の前記ネットワークごとに設けられた複数のバッファと、
受信パケットが入力されると、前記受信パケットの優先度クラスを判定する優先度判定回路と、
前記各バッファにおいて、複数の前記優先度クラスの前記パケットを登録可能な送信キューを形成し、宛先に対応する前記バッファに対して前記受信パケットを書き込むとともに、前記優先度判定回路の判定結果に基づいて、対応する前記送信キュー内に登録された同じ前記優先度クラスの前記パケットのうち、最後に登録された前記パケットの次に送信予約されるように前記受信パケットを登録するバッファ制御回路と、
を有することを特徴とするネットワークスイッチ装置。
【請求項２】
前記各バッファの使用量があらかじめ決められたしきい値に達しているか否かを判定する使用量検知回路をさらに有し、
前記バッファ制御回路は、前記受信パケットを前記送信キューに登録する際に、前記使用量検知回路によって、対応する前記バッファの使用量が前記しきい値に達していると判定された場合に、前記送信キュー内に登録されている前記パケットのうち、前記優先度クラスが最も低く、かつ最後に登録された前記パケットを廃棄することを特徴とする請求の範囲第１項記載のネットワークスイッチ装置。
【請求項３】
前記バッファ制御回路は、前記受信パケットを前記送信キューに登録する際に、対応する前記バッファの使用量が前記しきい値を超えると判定された場合に、前記受信パケットが、登録先の前記送信キュー内に登録された前記パケットの前記優先度クラスのうち、最も低い前記優先度クラスまたはそれより下位クラスに属しているときは、前記受信パケット自身を廃棄することを特徴とする請求の範囲第２項記載のネットワークスイッチ装置。
【請求項４】
前記バッファ制御回路は、前記受信パケットを前記送信キューに登録する際に、前記受信パケットと同じ前記優先度クラスの前記パケットが前記送信キュー内に登録されていない場合、前記受信パケットより上位の前記パケットが前記送信キューにすでに登録されているときは、最も近い上位の前記優先度クラスの前記パケットのうち、最後に登録された前記パケットの次に前記受信パケットを登録し、前記受信パケットより上位の前記パケットが前記送信キューに登録されていないときは、前記送信キューの先頭に前記受信パケットを登録することを特徴とする請求の範囲第１項記載のネットワークスイッチ装置。
【請求項５】
前記バッファ制御回路は、前記各送信キューに登録した前記パケット間の連結を、前記各パケットの前記各バッファにおける書き込み位置に基づく連結リスト構造として管理することを特徴とする請求の範囲第１項記載のネットワークスイッチ装置。
【請求項６】
前記各バッファにおける前記パケットの書き込み位置を指し示すポインタをそれぞれ保持するポインタスタックをさらに具備し、
前記バッファ制御回路は、前記バッファへの前記パケットの書き込み時に、対応する前記ポインタスタックから前記ポインタをＰＯＰして取得し、取得した前記ポインタを用いて前記各バッファに形成された前記送信キュー内の前記パケット間の連結を管理することを特徴とする請求の範囲第５項記載のネットワークスイッチ装置。
【請求項７】
前記バッファ制御回路は、前記各送信キュー内における直前の書き込み位置、および後続の前記パケットの書き込み位置をそれぞれ示す前記ポインタを、前記パケットとともに付属データとして前記バッファに書き込むことを特徴とする請求の範囲第６項記載のネットワークスイッチ装置。
【請求項８】
前記バッファ制御回路は、前記各送信キュー内において同じ前記優先度クラスに属する前記パケットのうち、最後に登録された前記パケットを指し示す前記ポインタを保持する末尾ポインタ保持部を前記優先度クラスごとに具備し、
新たな前記受信パケットを登録する際に、前記受信パケットの前記優先度クラスに対応する前記末尾ポインタ保持部に保持された前記ポインタに指し示される前記パケットの前記付属データのうち、後続の前記パケットを指し示す前記ポインタを、前記受信パケットを指し示す前記ポインタに書き換え、さらに、前記受信パケットの前記付属データに、直前の前記パケットを指し示す前記ポインタとして、前記受信パケットの前記優先度クラスに対応する前記末尾ポインタ保持部に保持された前記ポインタを書き込んだ後、前記受信パケットの前記優先度クラスに対応する前記末尾ポインタ保持部が保持する前記ポインタを、前記受信パケットを指し示す前記ポインタに書き換えることを特徴とする請求の範囲第７項記載のネットワークスイッチ装置。
【請求項９】
前記バッファ制御回路は、前記各送信キュー内において同じ前記優先度クラスに属する前記パケットのうち、最初に登録された前記パケットを指し示す前記ポインタを保持する先頭ポインタ保持部を前記優先度クラスごとに具備し、
前記各バッファから前記パケットを読み出す際に、前記ポインタが保持されているもののうち最も上位の前記優先度クラスに対応する前記先頭ポインタ保持部を参照して、保持されている前記ポインタの指し示す前記パケットを読み出すとともに、読み出した前記パケットの前記付属データに書き込まれた前記ポインタのうち、後続の前記パケットを指し示す前記ポインタによって、参照した前記先頭ポインタ保持部を更新することを特徴とする請求の範囲第９項記載のネットワークスイッチ装置。
【請求項１０】
前記バッファ制御回路は、前記各送信キュー内に登録された前記各パケットを指し示す前記ポインタを送信予定順に保持するポインタ保持部を、前記優先度クラスごとに具備し、
新たな前記受信パケットを登録する際に、前記受信パケットの前記優先度クラスに対応する前記ポインタ保持部の最後尾に、前記受信パケットを指し示す前記ポインタを書き込むことを特徴とする請求の範囲第６項記載のネットワークスイッチ装置。
【請求項１１】
前記バッファ制御回路は、前記送信キューからの前記パケットの送信完了後には、送信された前記パケットに割り当てられていた前記ポインタを前記ポインタスタックにＰＵＳＨして返却することを特徴とする請求の範囲第６項記載のネットワークスイッチ装置。
【請求項１２】
複数のネットワーク間でパケットの転送を行うネットワークスイッチ装置において、
転送先の前記ネットワークごとに設けられた複数のバッファと、
受信パケットが入力されると、前記受信パケットの優先度クラスを判定する優先度判定回路と、
前記各バッファにおいて、１つ以上の隣接する前記優先度クラスの前記パケットを登録可能な複数の送信キューを形成し、宛先に対応する前記バッファに対して前記受信パケットを書き込むとともに、前記優先度判定回路の判定結果に基づいて、対応する前記送信キュー内に登録された同じ前記優先度クラスの前記パケットのうち、最後に登録された前記パケットの次に送信予約されるように前記受信パケットを登録するバッファ制御回路と、
を有することを特徴とするネットワークスイッチ装置。
【請求項１３】
受信パケットを転送先のネットワークに対応するバッファに一旦蓄積しながら複数のネットワーク間で転送するネットワークスイッチ方法において、
受信パケットが入力されると、前記受信パケットの優先度クラスを判定し、
前記各バッファにおいて、複数の前記優先度クラスの前記パケットを登録可能な送信キューを形成し、宛先に対応する前記バッファに対して前記受信パケットを書き込むとともに、前記優先度クラスの判定結果に基づいて、対応する前記送信キュー内に登録された同じ前記優先度クラスの前記パケットのうち、最後に登録された前記パケットの次に送信予約されるように前記受信パケットを登録する、
ことを特徴とするネットワークスイッチ方法。
【発明の詳細な説明】
【技術分野】  本発明は、複数のネットワーク間でパケットの転送を行うネットワークスイッチ装置およびネットワークスイッチ方法に関し、特に、パケットの優先度に応じた転送制御を行うことが可能な、ストア＆フォワード方式のネットワークスイッチ装置およびネットワークスイッチ方法に関する。
【背景技術】  インターネット等のように多数のネットワークが互いに接続されている場合、それらの接続にはネットワークスイッチ装置が用いられることが多い。中でも、受信したパケットを内部のバッファに一旦蓄積した後、目的の送信ポートに転送するスイッチ方式はストア＆フォワード方式と言われ、このようなスイッチ方式を採用したネットワークスイッチ装置が広く使用されている。
ストア＆フォワード型のネットワークスイッチ装置では、送信予定のパケットは、宛先ポートごとにポインタで連結した連結リスト構造のキューとして制御されることが一般的である。連結リスト構造を用いてバッファメモリ内に形成されたキューを制御する従来のパケットスイッチとしては、例えば以下のようなものがあった。
このパケットスイッチは、各入力回線から受信した可変長パケットを、固定長のデータブロック単位で共通バッファメモリに書き込む。この書き込み時に、バッファ制御部が入力回線別の入力キューを形成し、可変長パケットの最終データブロックが入力キューに登録された時、この入力キューのリンクド・アドレスリストを転送先出力回線と対応した出力キューにリンクする。
各入力キューは、共通バッファメモリへの書き込みの際に、次の固定長データブロックの書込みアドレスを次アドレスメモリに記憶することにより形成される。また、各出力キューは、次に読み出すべきデータブロックを示す次読出しアドレスと、最後のデータブロックを示す最終読出しアドレスとを記憶するアドレステーブルからなり、バッファ制御部の入力キュー制御部が、各可変長パケットの先頭データブロックの書き込みアドレスと、最終データブロックの書き込みアドレスとを、それぞれ転送先出力回線と対応するアドレステーブルの次読出しアドレスおよび最終読出しアドレスに移すことによって、出力キューへの入力キューリンクを完了する。さらに、先行する可変長パケットの最終読出しアドレスがすでに登録された状態である場合には、次アドレスメモリから後続可変長パケットの先頭データブロックの書込みアドレスを抽出して、このアドレスを最終読出しアドレスにリンクさせる。このような制御により、バッファメモリの使用効率を高めるとともに、スイッチング動作を高速化している。例えば、特開２００２−１５２２４７号公報（段落番号〔００２５〕〜〔００４０〕、第３図）参照。
ところで、ネットワークを介して通信される情報には、データ品質を一定以上に確保すべき情報と、データ品質の劣化を許容できる情報とがある。そこで、例えば、これらの情報の優先度を多段階にクラス分けした優先度クラスを定義し、通信される各パケットの属性（送信元アドレス等）に応じて優先度クラスを与えることが考えられる。この場合、ネットワークスイッチ装置において、優先度クラスの高いパケットを優先的に転送することにより、優先度の高いパケットのデータ転送の確実性を向上させることができる。
ストア＆フォワード方式のネットワークスイッチ装置では、通常、受信パケットの宛先を判定した後、宛先別（出力ポートごと）に形成されたパケットのキューに受信パケットを連結し、これらのキューからパケットを読み出して送出する。ここで、受信パケットにそれぞれ異なる優先度が付与されており、それらの受信パケットに対して優先制御を行う場合は、出力ポートごとに優先度クラス数分のキューを作成し、優先度クラス別に振り分けられた受信パケットを、該当する優先度クラスのキューに連結する。そして、優先度クラスの高いキューから先にパケットを送出することにより、優先制御を実現する。
優先度の高い情報としては、例えば音声データや動画像データが代表的である。このようなリアルタイム性が重要視される情報の通信をサポートするためには、これらの情報のネットワークスイッチ装置における中継遅延時間をできるだけ短縮する必要がある。しかし、優先制御が行われるネットワークスイッチ装置でも、例えば同じ出力ポートの同じ優先度クラス宛のトラフィックが集中する等の事態が発生すると、優先度の高いパケットであっても廃棄されてしまうことがあり得る。
優先度の高いパケットの中継遅延時間を短縮可能にした従来のパケットスイッチとして、以下のようなものがあった。このパケットスイッチは、入力回線から受信した可変長パケットを各入力回線インタフェースで固定長のセルに変換し、スイッチ部においてセル単位でスイッチングし、このスイッチ部からの出力セルを各出力回線インタフェースで元の可変長パケットに変換して出力回線に送出するように構成されている。そして、各入力回線インタフェースが、受信した可変長パケットから変換された固定長のセルを出力回線ごとに優先度別にキューイングし、各キューの蓄積セルを優先度に応じて選択的に出力するための制御手段を備えたことを特徴としている。
このパケットスイッチにおいて、特定の出力ポートに向かう複数のパケットが複数の入力回線から時間的に重なって入力され、スイッチ部内で上記の特定出力ポートに向かうセルの蓄積量が所定のしきい値を超えた場合には、各入力回線インタフェースに対して輻輳状態通知が与えられる。そして、上記の特定出力ポートに向かうセルを送出中の入力回線インタフェースが、この輻輳状態通知に応答して、セル優先度の低いものから選択的にセル送出を抑制する。これによって、輻輳状態が深刻化することが回避され、優先度の高いパケットが大幅に遅延することなく出力回線側に転送される。例えば、特開２０００−１５１６３３号公報（段落番号〔００１２〕〜〔００１８〕、第１図）参照。
ところで、ストア＆フォワード方式のネットワークスイッチ装置において、宛先別に形成されたパケットのキューは、通常、それぞれ物理的または論理的に分離された有限な大きさのバッファに格納されている。また、優先制御が行われるネットワークスイッチでは、さらに、優先度クラスごとにキューが形成されることが多い。このようなネットワークスイッチ装置において、ある出力ポートに対して特定の優先度クラス宛のトラフィックが集中した場合、同じ出力ポートの別の優先度クラスのキューでは空き容量があるにもかかわらず、トラフィックが集中したキューでは輻輳が発生してしまうことがある。このような事態を避けるためには、例えば、各優先度クラスのキューに対して十分なバッファ容量を確保する必要がある。しかし、この場合にはメモリの使用効率が低下するとともに、メモリ容量が増大して部品コストが高くなることが問題であった。
上記の特開２０００−１５１６３３号公報で開示されたパケットスイッチでは、スイッチ部内のバッファメモリと、出力回線インタフェース内の出力バッファメモリにおいて、それぞれ優先度クラスごとにキューを形成することができる。このとき、各バッファメモリにおいて、優先度クラス別の各キューが他のキューと空きエリアを共用する共通バッファ構造を採用することにより、メモリ容量を有効に利用できる。しかし、このためには、スイッチ部および出力回線インタフェースの双方において、出力回線別および優先度クラス別の連結リストを管理してバッファ制御を行う必要があり、処理が複雑になって高コストとなることが問題となる。また、このパケットスイッチは、受信パケットを固定長のセルに変換して取り扱うことが前提とされており、受信パケットをそのままの状態で取り扱う装置に対しては適用できない。
【発明の開示】
本発明は、このような課題に鑑みてなされたものであり、パケットの優先制御が可能であり、かつ、受信パケットを格納するバッファの使用効率が高められ、部品コストが低減されたネットワークスイッチ装置を提供することを目的とする。
本発明では上記課題を解決するために、図１に示すようなネットワークスイッチ装置が提供される。このネットワークスイッチ装置は、複数のネットワーク間でパケットの転送を行うものであり、転送先の前記ネットワークごとに設けられた複数のバッファ１−１〜ｎ（ただし、ｎは１以上の整数）と、受信パケット１０が入力されると、前記受信パケット１０の優先度クラスを判定する優先度判定回路２と、前記各バッファ１−１〜ｎにおいて、複数の前記優先度クラスの前記パケットを登録可能な送信キュー４〜１〜ｎを形成し、宛先に対応する前記バッファに対して前記受信パケット１０を書き込むとともに、前記優先度判定回路２の判定結果に基づいて、対応する前記送信キュー内に登録された同じ前記優先度クラスの前記パケットのうち、最後に登録された前記パケットの次に送信予約されるように前記受信パケット１０を登録するバッファ制御回路３とを有することを特徴とする。
このようなネットワークスイッチ装置では、バッファ制御回路３の制御の下で、受信パケット１０がその宛先のネットワークに対応するバッファに格納される。また、優先度判定回路２は、受信パケット１０の優先度クラスを判定する。バッファ制御回路３は、各バッファ１−１〜ｎにおいて、複数の優先度クラスのパケットを登録可能な送信キュー４−１〜ｎを形成する。そして、受信パケット１０をバッファに書き込む際に、優先度判定回路２の判定に基づいて、対応する送信キュー内に登録された同じ優先度クラスのパケットのうち、最後に登録されたパケットの次に受信パケット１０が送信予約されるように制御する。
これにより、宛先のネットワークに対応するバッファ１−１〜ｎには、それぞれ１つの送信キュー４−１〜ｎが形成され、各送信キュー４−１〜ｎでは、優先度クラスが高く、かつ先に受信されたパケットほど先に送信されるようにパケットが登録される。このとき、優先度クラスごとに割り当てられるバッファ容量が特定されないため、受信パケット１０はその優先度クラスに関係なくバッファ１−１〜ｎの空き領域に格納される。また、例えば、バッファ制御回路３によって、各送信キュー４−１〜ｎに登録したパケット間の連結を、各パケットの各バッファ１−１〜ｎにおける書き込み位置に基づく連結リスト構造として管理することも可能である。
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】  図１は、本発明の原理を説明するための原理図である。
図２は、本発明の第１の実施の形態に係るネットワークスイッチ装置の接続例を示す図である。
図３は、本発明の第１の実施の形態に係るネットワークスイッチ装置の内部構成を示すブロック図である。
図４は、本発明の第１の実施の形態に係るネットワークスイッチ装置において、送信バッファ内に格納されたデータの構造を模式的に示す図である。
図５は、本発明の第１の実施の形態に係るネットワークスイッチ装置において、バッファ制御回路に設けられるレジスタ群と、送信キューとの関係を示す図である。
図６は、本発明の第１の実施の形態に係るネットワークスイッチ装置において、パケットを送信バッファに書き込む場合のバッファ制御回路における処理の流れを示すフローチャートである。
図７は、本発明の第１の実施の形態に係るネットワークスイッチ装置において、パケットを送信バッファから読み出す場合のバッファ制御回路における処理の流れを示すフローチャートである。
図８は、本発明の第２の実施の形態に係るネットワークスイッチ装置において、バッファ制御回路に設けられるポインタメモリと、送信キューとの関係を示す図である。
図９は、本発明の第２の実施の形態に係るネットワークスイッチ装置において、パケットを送信バッファに書き込む場合のバッファ制御回路における処理の流れを示すフローチャートである。
図１０は、本発明の第２の実施の形態に係るネットワークスイッチ装置において、パケットを送信バッファから読み出す場合のバッファ制御回路における処理の流れを示すフローチャートである。
図１１は、本発明の第３の実施の形態に係るネットワーク装置において、各送信バッファに形成される送信キューの例を示す図である。
【発明を実施するための最良の形態】  以下、本発明の実施の形態を図面を参照して説明する。
図１は、本発明の原理を説明するための原理図である。
本発明のネットワークスイッチ装置は、複数のネットワークに接続して、これらのネットワーク間でパケットを転送する装置である。このネットワークスイッチ装置は、図１に示すように、転送先のネットワークごとにそれぞれ設けられたバッファ１−１〜ｎ（ただし、ｎは１以上の整数）と、優先度判定回路２と、バッファ制御回路３とを有している。
各バッファ１−１〜ｎは、ネットワークを通じて受信したパケット（以下、受信パケットと呼称する）１０を、その宛先に応じて格納するための記憶装置であり、例えば半導体メモリ等によって構成される。なお、各バッファ１−１〜ｎの領域は、必ずしも物理的に分離された領域である必要はなく、１つの共有バッファ上に各領域が論理的に分離されて形成されてもよい。
優先度判定回路２は、受信パケット１０に付与された優先度クラスを判定して、判定結果をバッファ制御回路３に通知する。
バッファ制御回路３は、バッファ１−１〜ｎにおける受信パケット１０の書き込みおよび読み出しの動作を制御する。バッファ制御回路３は、宛先のネットワークごとに設けられたバッファ１−１〜ｎにおいて、それぞれ１つの送信キュー４−１〜ｎを形成して、受信パケット１０をその宛先に対応するバッファに格納させるとともに、対応する送信キューに登録する。
ここで、各送信キュー４−１〜ｎには、複数の優先度クラスのパケットを登録することが可能とされる。バッファ制御回路３は、優先度判定回路２による判定結果に基づいて、送信キューに対する登録位置を決定する。具体的には、宛先に対応する送信キュー内にすでに登録されている、受信パケット１０と同じ優先度クラスのパケットのうち、最後に登録されたパケットの次に送信予約されるように、受信パケット１０を送信キューに登録する。
以下、このネットワークスイッチ装置におけるスイッチング動作を、順を追って説明する。この説明では、バッファ１−１に対応するネットワークに転送すべきパケットが受信された場合を想定する。
接続されたネットワークからパケットが受信されると（ステップＳ１）、優先度判定回路２により、この受信パケット１０に付与された優先度クラスが判定される（ステップＳ２）。この判定は、例えば受信パケット１０のヘッダ情報を参照して行われ、判定結果がバッファ制御回路３に通知される。
バッファ制御回路３は、例えば図示しないヘッダ解析部等から受信パケット１０の宛先の通知を受けて、その宛先に対応するバッファ１−１に対して受信パケット１０を書き込むように、動作を制御する（ステップＳ３）。バッファ１−１内には、バッファ制御回路３の制御の下で送信キュー４−１が形成され、送信キュー４−１内には、パケットが送信予定順に登録される。
ここで、バッファ制御回路３は、受信パケット１０と同じ優先度クラスのパケットが送信キュー４−１にすでに登録されている場合には、これらのパケットのうち、その送信キュー４−１内で最後に登録されたパケットの次に送信予約されるように、受信パケット１０を登録する。
図１では、例として、高優先度と低優先度の２段階の優先度クラスが設定されているものとしている。そして、バッファ１−１内の送信キュー４−１には、双方の優先度クラスのパケットがすでに登録された状態となっている。ここで、受信パケット１０が高優先度クラスと判定された場合には、受信パケット１０は、送信キュー４−１内において、高優先度クラスのパケットの末尾に挿入される（ステップＳ３−１）。また、受信パケット１０が低優先度クラスと判定された場合には、受信パケット１０は、低優先度クラスのパケットの末尾に登録される（ステップＳ３−２）。
なお、ステップＳ３−１において、受信パケット１０の登録時にバッファ１−１の空き領域がない場合には、送信キュー４−１に登録されていたパケットのうち、優先度が最も低い低優先度クラスで、かつ最後に登録されたパケットが廃棄され、受信パケット１０の挿入が行われる。また、ステップＳ３−２において、同様にバッファ１−１の空き領域がない場合には、受信パケット１０自身が廃棄される。
このようなバッファ１−１に対する書き込み制御により、１つの送信キュー４−１でありながら、高優先度クラスのパケットは、それより下位の優先度クラスのパケットよりも常に先に送信予約される。そして、送信キュー４−１からは、バッファ制御回路３による制御の下で、先頭のパケットから順に読み出され、対応するネットワークに送信される（ステップＳ４）。
以上の動作において、バッファ制御回路３によるバッファ１−１への書き込み制御により、送信キュー４−１内では、優先度クラスが高く、かつ先に受信されたパケットほど先に送信されるようにパケットが登録される。このとき、優先度クラスごとに割り当てられるバッファ容量が特定されず、バッファ１−１に空き領域がある場合は優先度クラスに関係なく受信パケット１０が格納される。従って、この送信キュー４−１に対してパケットが集中する等により輻輳が発生した場合に、優先度クラスが高いパケットほどより確実に送信が行われるとともに、バッファ１−１内の使用効率が高められる。この結果、バッファ１−１の容量を抑制することができ、部品コストが低減される。
なお、上記のようなバッファ制御回路３によるバッファ１−１〜ｎの書き込み・読み出し制御を効率的に行うためには、バッファ１−１〜ｎ内に格納した各パケットを、各バッファ１−１〜ｎにおける書き込み位置に基づく連結リスト構造として管理すればよい。例えば、各バッファ１−１〜ｎ内の書き込み位置を指し示すポインタを保持するポインタスタックを設け、バッファ制御回路３は、受信パケット１０の書き込み時にこのポインタスタックからポインタをＰＯＰして取得する。そして、送信キュー４−１〜ｎ内に登録された各パケット間の連結を、各パケットを指し示すポインタを用いた連結リストを用いて管理する。
次に、本発明の実施の形態について、具体的に説明する。
〔第１の実施の形態〕
図２は、本発明の第１の実施の形態に係るネットワークスイッチ装置の接続例を示す図である。
図２に示すように、ネットワークスイッチ装置１００には、複数の通信ポートが設けられており、各通信ポートにネットワーク２１〜２４が接続されている。各ネットワーク２１〜２４には、例えば端末装置２１ａ、２２ａ、２３ａおよび２４ａが接続されている。
ネットワークスイッチ装置１００は、接続されたネットワーク２１〜２４の間におけるパケットの転送を行う。例えば、端末装置２１ａから端末装置２２ａ宛てに送信されたパケットは、ネットワーク２１を通じてネットワークスイッチ装置１００に入力され、このネットワークスイッチ装置１００の処理によってネットワーク２２に転送される。これにより、転送されたパケットが、ネットワーク２２を通じて端末装置２２ａにおいて受信される。
図３は、ネットワークスイッチ装置１００の内部構成を示すブロック図である。
図３に示すように、ネットワークスイッチ装置１００は、受信インタフェース１１１〜１１４、受信バッファ１２１〜１２４、送信インタフェース１３１〜１３４、送信バッファ１４１〜１４４、データ転送回路１５０、ヘッダ解析回路１６０、ポインタスタック１７０、使用量監視回路１８０、およびバッファ制御回路１９０を具備する。
受信インタフェース１１１〜１１４は、外部のネットワークからのデータを受信する通信インタフェースであり、それぞれネットワーク２１〜２４に接続されている。受信インタフェース１１１〜１１４は、各ネットワーク２１〜２４を通じて受信したパケットを、受信バッファ１２１〜１２４に対して供給する。
受信バッファ１２１〜１２４は、それぞれ受信インタフェース１１１〜１１４から供給されたパケットを一時的に格納するためのバッファメモリである。受信バッファ１２１〜１２４は、格納したパケットのヘッダ情報をヘッダ解析回路１６０に出力するとともに、データ転送回路１５０に対してパケットの出力要求を行い、データ転送回路１５０からの応答に応じて、格納したパケットをデータ転送回路１５０に出力する。
一方、送信インタフェース１３１〜１３４は、外部のネットワークに対してデータを送信する通信インタフェースであり、それぞれネットワーク２１〜２４に接続されている。送信インタフェース１３１〜１３４は、それぞれ送信バッファ１４１〜１４４から供給されたパケットを、ネットワーク２１〜２４に対して送信する。
送信バッファ１４１〜１４４は、データ転送回路１５０から供給されたパケットを一時的に格納するためのバッファメモリである。送信バッファ１４１〜１４４は、供給されたパケットを、データ転送回路１５０によって指定されたアドレスに書き込む。そして、対応する送信インタフェース１３１〜１３４からの送信要求に応じて、書き込まれたパケットを、バッファ制御回路１９０によるアドレス指定に基づいて読み出し、それぞれ送信インタフェース１３１〜１３４に対して出力する。
各送信バッファ１４１〜１４４は、パケットの書き込みおよび読み出しの各動作が行われるたびに、これらの動作が行われたことを使用量監視回路１８０に対して通知する。これにより、使用量監視回路１８０において、各送信バッファ１４１〜１４４の使用量を監視することが可能となる。
また、送信バッファ１４１〜１４４内には、バッファ制御回路１９０による制御の下で、それぞれ１つずつの送信キューが形成される。そして、書き込まれたパケットのそれぞれに対して付属セル領域が設けられ、付属セル領域には、そのパケットが登録された送信キューにおける先行パケットおよび後続パケットの書き込み位置を指し示すポインタが、バッファ制御回路１９０によって書き込まれる。これにより、各送信キュー内に登録されたパケット間の連結が管理される。
データ転送回路１５０は、各受信バッファ１２１〜１２４からパケットを受け取り、宛先に対応する送信バッファに対して転送する。データ転送回路１５０は、各受信バッファ１２１〜１２４から出力要求を受けると、そのパケットの宛先を示す情報をヘッダ解析回路１６０から取得する。また、使用量監視回路１８０からの情報に基づき、宛先に対応する送信バッファに対する書き込みが可能か否かを判断し、可能な場合には、ポインタスタック１７０からポインタを取得して、そのポインタに基づく書き込みアドレスを指定し、パケットを転送する。
ヘッダ解析回路１６０は、受信バッファ１２１〜１２４に格納されたパケットのヘッダ情報を取得し、そのパケットの宛先として指定された送信ポートを、データ転送回路１５０およびバッファ制御回路１９０に対して通知する。また、取得したヘッダ情報からそのパケットの優先度クラスを判定して、バッファ制御回路１９０に対して通知する。ヘッダ解析回路１６０は、例えば、宛先の送信ポートと優先度クラスとの対応テーブルを具備して、この対応テーブルを参照して、ヘッダ情報に示された宛先から優先度クラスを判断する。
ポインタスタック１７０は、送信バッファ１４１〜１４４におけるパケットの書き込みアドレスを指し示すポインタが格納されている。ポインタスタック１７０は、データ転送回路１５０からの要求に応じて、ポインタをＰＯＰし、データ転送回路１５０およびバッファ制御回路１９０に出力する。また、出力したポインタに指し示される送信バッファ１４１〜１４４内の領域が、パケットの読み出しや廃棄により開放された場合は、そのポインタがバッファ制御回路１９０から供給され、ポインタスタック１７０にＰＵＳＨされて返却される。従って、ポインタスタック１７０内に存在するポインタは、必ず送信バッファ１４１〜１４４内の空き領域を指し示していることになる。
使用量監視回路１８０は、各送信バッファ１４１〜１４４において空き領域があるか否かを示す情報を、データ転送回路１５０およびバッファ制御回路１９０に対して通知する。使用量監視回路１８０は、各送信バッファ１４１〜１４４から、パケットの書き込みおよび読み出しの各動作が行われたことの通知を受ける。また、バッファ制御回路１９０から、送信バッファ１４１〜１４４内に格納されたパケットが廃棄され、バッファ内の領域が開放されたことの通知を受ける。そして、これらの通知に基づいて各送信バッファ１４１〜１４４内のバッファ使用量をカウントし、カウント値があらかじめ設定された値に達すると、その送信バッファに空き領域がなくなったと判断する。
この使用量監視回路１８０は、データ転送回路１５０およびバッファ制御回路１９０に対して、各送信バッファ１４１〜１４４に空き領域があるか否かを示す情報を、例えば定期的に、あるいは各通知先からの要求に応じて更新する。
バッファ制御回路１９０は、送信バッファ１４１〜１４４におけるパケットの書き込みおよび読み出しの動作を制御する。また、バッファ制御回路１９０は、送信バッファ１４１〜１４４内においてそれぞれ１つずつの送信キューを形成し、書き込まれたパケットを、送信キューに対して優先度クラスに応じて登録する。各送信キューに割り当てられるバッファ容量は有限とされる。また、各送信キューは、登録されたパケットとその前後のパケットとを連結させた双方向連結リスト構造を用いて管理される。
このために、バッファ制御回路１９０は、各送信バッファ１４１〜１４４内にパケットが書き込まれる際に、このパケットの書き込みアドレスを指し示すポインタを、ポインタスタック１７０から取得する。そして、送信バッファ１４１〜１４４内に、各パケットのそれぞれに対応する付属セル領域を設け、送信キュー内においてこのパケットに先行するパケットと後続のパケットとをそれぞれ指し示すポインタを、付属セル領域に書き込む。
また、各送信キューに対しては、高い優先度クラスに属するパケットが常に上位に送信予約される。また、同じ優先度クラスに属するパケットについては、受信した順に送信予約される。このような優先度クラスに応じた登録管理を行うために、バッファ制御回路１９０は、後述するように、登録されたパケットのうち、各優先度クラスごとにその先頭パケットと末尾パケットとをそれぞれ指し示すポインタを保持するためのレジスタ群を具備する。そして、パケットの書き込みや読み出しを行うたびに、このレジスタ群の保持するポインタを更新する。
なお、本実施の形態では、送信バッファ１４１〜１４４は１つの共有メモリ内に設けられ、各バッファの領域が論理的に分離されて使用されるものとする。従って、ポインタスタック１７０は、共有メモリ内の全領域における書き込みアドレスに対応するポインタを一元的に保持しており、これによって共有メモリを効率的に使用することが可能となっている。ただし、各送信ポート用のバッファ領域の容量（すなわち送信バッファ１４１〜１４４としてそれぞれ使用される容量）は一定となるように決められており、これらの各容量が使用量監視回路１８０によって監視されるようになっている。
このようなネットワークスイッチ装置１００により、優先度クラスに応じてパケットの転送順や廃棄の可否を判断することが可能なスイッチング処理が行われる。例えば、ネットワーク２１からネットワーク２２に転送すべきパケットを受信した場合には、受信インタフェース１１１において受信されたパケットは、受信バッファ１２１に一旦格納される。このパケットのヘッダ情報はヘッダ解析回路１６０に通知され、ヘッダ解析回路１６０は、パケットの宛先から優先度クラスを判断し、バッファ制御回路１９０に宛先とともに通知する。
データ転送回路１５０は、受信バッファ１２１からパケットを受け取ると、ヘッダ解析回路１６０から通知された宛先に対応する送信バッファ１４２に対する転送処理を開始する。データ転送回路１５０は、使用量監視回路１８０からの情報に基づいて、送信バッファ１４２に対する書き込みが可能と判断すると、ポインタスタック１７０からポインタをＰＯＰして取得し、取得したポインタの指し示すアドレスにパケットを転送する。
また、バッファ制御回路１９０は、通知された宛先に対応する送信バッファ１４２内の送信キューにおいて、通知された優先度クラスのパケットの登録が可能か否かを判断する。使用量監視回路１８０からの使用量通知に基づき、送信キューにおいて格納可能な領域に余裕がある場合は、すべてのパケットが登録可能であるが、空き領域がない場合には、ヘッダ解析回路１６０から通知された優先度クラスに応じて、登録の可否を判断する。
登録しようとしているパケットより下位の優先度クラスのパケットが、送信バッファ１４２内の送信キューにすでに登録されている場合、バッファ制御回路１９０は、新たなパケットを登録可能と判断する。この場合、送信キューの最後尾に登録されたパケットを廃棄する処理を行うとともに、パケットを廃棄したことを使用量監視回路１８０に通知する。これにより、使用量監視回路１８０は、データ転送回路１５０に対して、送信バッファ１４２に空き領域が発生したことを通知するので、データ転送回路１５０は、送信バッファ１４２に対してパケットを転送する。
一方、登録しようとしているパケットと同等以下の優先度クラスのパケットが、送信バッファ１４２内の送信キューに登録されていない場合、バッファ制御回路１９０は、新たなパケットの登録が不可能と判断する。この場合、送信バッファ１４２内の領域が開放されないので、使用量監視回路１８０は、データ転送回路１５０に対して、パケットの書き込みが不可能である旨を通知し続ける。これにより、データ転送回路１５０は、パケットの転送が不可能であると判断して、受信バッファ１２１から受け取ったパケットを廃棄する。
送信バッファ１４２に書き込まれたパケットは、バッファ制御回路１９０の制御の下で、送信キューへの登録が連結リスト構造として管理される。そして、送信キューの登録順に従って読み出され、送信インタフェース１３２からネットワーク２２に送出される。
ここで、図４は、送信バッファ内に格納されたデータの構造を模式的に示す図である。
図４では、送信バッファ１４１〜１４４におけるパケットを、各バッファ内に形成される送信キューに登録された順に示している。なお、図４では、送信キュー内で連結された各パケットが連続して配置されているが、送信バッファ１４１〜１４４上の実際の物理的な書き込み位置は、この通りにはなるとは限らない。
上述したように、送信バッファ１４１〜１４４内では、各パケットが格納されるパケット格納領域１４０ａとともに、付属セル領域１４０ｂがパケットごとに設けられる。図４に示すように、付属セル領域１４０ｂには、送信キュー内の直前のパケットを指し示すポインタ（以下、直前ポインタと呼称する）と、後続のパケットを指し示すポインタ（以下、後続ポインタと呼称する）とが格納される。
付属セル領域１４０ｂの各ポインタは、バッファ制御回路１９０によって書き込まれる。直前ポインタは、受信パケットが送信バッファ１４１〜１４４に転送された際に書き込まれ、後続ポインタは、送信キュー内で後続のパケットが登録された際に書き込まれる。このような各ポインタを利用することにより、送信キュー内のパケットを前後の双方向に連結された双方向連結リスト構造として管理することが可能となる。
例えば、パケットを読み出したときには、そのパケットの付属セル領域１４０ｂの後続ポインタを参照することにより、次に送信すべきパケットの書き込み位置を知ることができる。また、送信バッファの空き領域がなくなり、優先度クラスの判定により送信キュー内のパケットを廃棄することになった場合は、送信キュー内の最後尾のパケットが廃棄される。このとき、廃棄するパケットの付属セル領域１４０ｂの直前ポインタを参照することにより、廃棄後に最後尾となるパケットの書き込み位置を知ることができる。
次に、付属セル領域１４０ｂに格納された各ポインタを利用したバッファ制御回路１９０の制御について詳しく説明する。なお、以下の説明では、例として、優先度が高い順に“高優先度”“中優先度”“低優先度”の３段階の優先度クラスを取り扱うことが可能であるとする。
図５は、バッファ制御回路１９０に設けられるレジスタ群と、送信キューとの関係を示す図である。
上述したように、各送信バッファ１４１〜１４４では、バッファ制御回路１９０の制御の下で、１つずつの送信キューが形成される。そして、各送信キューでは、優先度クラスが高いパケットほど先に送信予約されるように、登録が行われる。また、同じ優先度クラスのパケットでは、受信した順に登録される。従って、送信キューには、図５に示すように、高優先度クラスのパケットＰｈ（１）〜Ｐｈ（ｓ）が連結された後に、中優先度クラスのパケットＰｍ（１）〜Ｐｍ（ｔ）が連結され、さらに低優先度クラスのパケットＰｌ（１）〜Ｐｌ（ｕ）が連結される（ただし、ｓ，ｔ，ｕはそれぞれ１以上の整数である）。
このような構造の送信キューが形成されることにより、各送信バッファ１４１〜１４４では、優先度クラスごとに割り当てられるバッファ容量が特定されないため、受信したパケットはその優先度クラスに関係なくバッファの空き領域に格納される。従って、特定の送信ポートに輻輳が発生した場合に、対応する送信バッファに空き領域が発生することがなくなり、メモリの使用効率が高められる。
ところで、上記の構造の送信キューを管理するために、バッファ制御回路１９０は、各優先度クラスのパケットのうち先頭のものと末尾のものの書き込み位置を認識するためのレジスタ群を具備する。図５のように３段階の優先度クラスの取り扱いが可能な場合は、高優先度クラスに対しては、この優先度クラスのパケットのうち、先頭のパケットを指し示すポインタ、および末尾のパケットを指し示すポインタをそれぞれ保持する高優先先頭ポインタレジスタ１９１ａおよび高優先末尾ポインタレジスタ１９２ａが設けられる。同様に、中優先度クラスに対しては、中優先先頭ポインタレジスタ１９１ｂおよび中優先末尾ポインタレジスタ１９２ｂ、低優先度クラスに対しては、低優先先頭ポインタレジスタ１９１ｃおよび低優先末尾ポインタレジスタ１９２ｃが、それぞれ設けられる。
各優先度クラスの末尾ポインタレジスタは、該当する優先度を持つ新たなパケットが登録される際に更新され、先頭ポインタレジスタは、先頭のパケットが送信バッファから読み出される際に更新される。
なお、送信キュー内では、同じ優先度クラスのパケット間は、付属セル領域１４０ｂに書き込まれたポインタにより双方向が連結される。しかし、異なる優先度クラスのパケット間はこのような連結が行われない。従って、同じ優先度クラスのうち先頭のパケットの付属セル領域１４０ｂには、直前ポインタは書き込まれず、直前のパケットがないことを示す情報が書き込まれる。また、最後尾のパケットの付属セル領域１４０ｂには、後続ポインタは書き込まれず、後続のパケットがないことを示す情報が書き込まれる。また、異なる優先度クラス間のパケットの連結は、上記のレジスタ群に格納されたポインタにより管理される。
次に、これらのレジスタ群およびパケットの付属セル領域１４０ｂに格納されたポインタを用いたバッファ制御回路１９０の処理を、フローチャートを用いて説明する。なお、以下の図６および図７に示すフローチャートの説明では、例として、ネットワーク２１からネットワーク２２に対して転送すべきパケットを受信した場合を想定する。また、図６および図７の説明では、必要に応じて、ネットワークスイッチ装置１００内の他の要素における処理についての説明も加える。
図６は、パケットを送信バッファに書き込む場合のバッファ制御回路１９０における処理の流れを示すフローチャートである。以下、図６に示す処理をステップ番号に沿って説明する。
まず、受信インタフェース１１１において受信されたパケットが、受信バッファ１２１に一旦格納される。そして、格納されたパケットがデータ転送回路１５０に引き渡されるとともに、このパケットのヘッダ情報が、ヘッダ解析回路１６０に通知される。ヘッダ解析回路１６０は、パケットの宛先から優先度クラスを判断し、バッファ制御回路１９０に宛先とともに通知する。また、宛先はデータ転送回路１５０に対しても通知される。
［ステップＳ６０１］バッファ制御回路１９０は、ヘッダ解析回路１６０より、新たに受信されたパケットの宛先と優先度クラスの通知を受ける。
［ステップＳ６０２］使用量監視回路１８０からの情報を参照して、宛先に対応する送信バッファ１４２に空き領域があるか否かを判断する。空き領域がある場合は、ステップＳ６０３に進み、ない場合はステップＳ６０９に進む。
ここで、受信バッファ１２１からパケットを受け取ったデータ転送回路１５０は、ヘッダ解析回路１６０からの通知に基づいて、このパケットの宛先を判断する。そして、同様に、使用量監視回路１８０からの情報を参照して、宛先に対応する送信バッファ１４２に空き領域があるか否かを判断し、この判断に応じてパケットを転送するか否かを決定する。
［ステップＳ６０３］送信バッファ１４２に空き領域がある場合は、ポインタスタック１７０からＰＯＰされたポインタが、データ転送回路１５０およびバッファ制御回路１９０に供給される。データ転送回路１５０は、送信バッファ１４２にパケットを転送し、取得したポインタの指し示すアドレスに書き込む。
［ステップＳ６０４］バッファ制御回路１９０は、送信バッファ１４２に対応する各優先度クラスの先頭ポインタレジスタのうち、受信パケットの優先度クラスの先頭ポインタレジスタを参照し、このレジスタにポインタが格納されているか否かを判断する。格納されていない場合は、送信キューに同じ優先度クラスのパケットが登録されていないと判断して、ステップＳ６０５に進む。また、格納されている場合は、送信キューに同じ優先度クラスのパケットがすでに登録されていると判断して、ステップＳ６０６に進む。
［ステップＳ６０５］受信パケットの優先度クラスに対応する先頭ポインタレジスタおよび末尾ポインタレジスタに、ポインタスタック１７０から取得したポインタ、すなわち受信パケットの格納位置を指し示すポインタを格納する。例えば、受信パケットが中優先度クラスである場合は、取得したポインタを中優先先頭ポインタレジスタ１９１ｂおよび中優先末尾ポインタレジスタ１９２ｂに格納する。また、このとき、受信パケットの付属セル領域１４０ｂには、直前および後続のパケットがないことを示す情報を書き込む。これにより、受信パケットが送信キューに登録され、パケットの書き込み処理が終了する。
［ステップＳ６０６］受信パケットと同じ優先度クラスのパケットが送信キューにすでに登録されている場合は、まず、該当する優先度クラスの末尾ポインタレジスタを参照する。例えば、受信パケットが中優先度クラスの場合は、中優先末尾ポインタレジスタ１９２ｂを参照する。そして、このレジスタに格納されているポインタが指し示すパケットの付属セル領域１４０ｂに対し、後続ポインタを、受信パケットを指し示すポインタで更新する。
［ステップＳ６０７］次に、受信パケットの付属セル領域１４０ｂに対して、直前ポインタとして末尾ポインタレジスタに格納されているポインタを格納する。このとき、付属セル領域１４０ｂには、後続のパケットがないことを示す情報も書き込む。
［ステップＳ６０８］さらに、末尾ポインタレジスタを、受信パケットを指し示すポインタで更新する。これにより、受信パケットが、送信キュー上の同じ優先度クラスのパケットのうち、最後に登録されていたパケットの次の位置に登録され、パケットの書き込み処理が終了する。
［ステップＳ６０９］一方、宛先に対応する送信バッファ１４２の空き容量がない場合には、まず、受信パケットの優先度クラスより下位クラスに対応する先頭ポインタレジスタを参照して、いずれかのレジスタにポインタが格納されているか否かを判断する。格納されている場合は、より下位クラスのパケットが送信キューにすでに登録されていると判断され、ステップＳ６１０に進む。
また、格納されていない場合は、何も処理が行われないままパケットの書き込み処理が終了される。この場合、受信パケットは、送信キュー中に登録されているパケットの中で最下位あるいはそれよりさらに下位の優先度クラスに属していることになり、廃棄すべきパケットと判断される。使用量監視回路１８０は、送信バッファ１４２の空き領域がないことをデータ転送回路１５０に通知し続ける。これにより、データ転送回路１５０は、このパケットの転送を行わないまま、受信バッファ１２１〜１２４のいずれかから次のパケットを受け取って、転送処理を開始するので、前のパケットは廃棄される。
［ステップＳ６１０］受信パケットより下位クラスのパケットが送信キューにすでに登録されている場合には、まず、ポインタが格納されている末尾ポインタレジスタのうち、最下位クラスのレジスタに格納されているポインタを、ポインタスタック１７０にＰＵＳＨして返却する。例えば、図５のような送信キューが形成されていた場合には、低優先末尾ポインタレジスタ１９２ｃに格納されているポインタを返却する。これにより、送信バッファ１４２の領域が、１パケット分だけ開放される。
［ステップＳ６１１］ステップＳ６１０で返却したポインタで指し示されるパケットの付属セル領域１４０ｂから直前ポインタを抽出し、この直前ポインタで、末尾ポインタレジスタを更新する。また、このとき、抽出した直前ポインタに指し示されるパケットの付属セル領域１４０ｂに対して、後続ポインタを消去して、後続のパケットがないことを示す情報を書き込む。これにより、送信キューの最後尾のパケットの登録が抹消される。
なお、付属セル領域に直前のパケットがないことを示す情報が書き込まれていた場合には、対応する優先度クラスの末尾ポインタレジスタおよび先頭ポインタレジスタの双方のポインタを消去する。
［ステップＳ６１２］送信バッファ１４２の領域が開放されたことを、使用量監視回路１８０に通知し、ステップＳ６０３に進む。これにより、使用量監視回路１８０は、送信バッファ１４２に空き領域が発生したと判断して、このことをデータ転送回路１５０に通知する。データ転送回路１５０は、この通知を受けるとともに、ステップＳ６０３に対応する処理によりポインタスタック１７０からポインタを取得し、パケットを送信バッファ１４２に転送して、取得したポインタに指し示されるアドレスに書き込む。
以上の処理により、受信パケットは、送信キューにすでに登録されていた同じ優先度クラスのパケットのうち、最後に登録されたパケットの次に送信予約される（ステップＳ６０６〜Ｓ６０８に対応）。
また、受信パケットと同じ優先度クラスのパケットが送信キュー内に登録されていない場合には、送信キュー内でこの優先度クラスに該当する位置に受信パケットが登録される（ステップＳ６０５に対応）。具体的には、受信パケットより上位クラスのパケットが送信キューにすでに登録されていた場合には、登録されている中で最も近い上位クラスのパケットのうち、最後に登録されたパケットの次に受信パケットが登録される。例えば、送信キューには高優先度クラスと低優先度クラスのパケットのみが登録されている送信キューに、中優先度クラスの受信パケットを登録する場合には、それより上位である高優先度クラスの最終パケットの次に、受信パケットが挿入される。また、受信パケットより上位クラスのパケットが送信キューに登録されていない場合には、受信パケットが送信キューの先頭に登録される。
さらに、各送信バッファ１４１〜１４４の容量は有限であるため、例えばネットワーク２２宛てにパケットが集中して送信バッファ１４２が埋め尽くされた場合には、パケットを廃棄する必要が生じる。このとき、送信キューに登録されているもののうち、最も優先度クラスが低く、かつ最後に登録されたパケットを廃棄する（ステップＳ６１０〜Ｓ６１２に対応）。また、受信パケットが属する優先度クラスより下位クラスのパケットが送信キューに登録されていない場合は、受信パケット自身が廃棄される。
従って、送信キューでは、優先度クラスの高いパケットほど先に送信されるように、パケットが登録される。また、優先度クラスごとに割り当てられるバッファ容量が特定されないため、送信バッファに空き領域がある場合には、優先度クラスに関係なく受信パケットが空き領域に格納される。逆に、空き領域がない場合には、優先度クラスが最も低いパケットが常に廃棄され、高い優先度クラスのパケットが確実に送信予約される。
このため、特定の送信キューにおいて輻輳が発生した場合でも、優先度クラスが高いパケットほどより確実に送信が行われるとともに、送信バッファに空き領域が発生することがなくなる。従って、送信バッファ１４１〜１４４の使用効率が高められ、結果的に各バッファの容量を小さくすることができるので、部品コストが低減される。
また、送信キューに登録したパケット間の連結を、パケットの書き込み位置を指し示すポインタを用いた双方向連結リスト構造として管理することにより、送信キューへのパケットの登録処理だけでなく、一旦登録された低優先度クラスのパケットを廃棄する際の処理も効率的に実行することが可能となる。
次に、図７は、パケットを送信バッファから読み出す場合のバッファ制御回路１９０における処理の流れを示すフローチャートである。以下、図７に示す処理をステップ番号に沿って説明する。
［ステップＳ７０１］バッファ制御回路１９０は、ポインタが格納されている先頭ポインタレジスタのうち、最上位クラスのレジスタを参照する。そして、このレジスタに格納されているポインタが指し示すパケットを読み出し、対応する送信インタフェース１３２に転送する。これにより、読み出されたパケットがネットワーク２２に送出される。
［ステップＳ７０２］ステップＳ７０１で参照した先頭ポインタレジスタのポインタを、ポインタスタック１７０にＰＵＳＨして返却する。
［ステップＳ７０３］送信バッファ１４２の領域が開放されたことを、使用量監視回路１８０に通知する。
［ステップＳ７０４］返却したポインタが指し示すパケットの付属セル領域１４０ｂの後続ポインタで、対応する優先度クラスの先頭ポインタレジスタを更新する。ここで、参照した付属セル領域１４０ｂに、後続のパケットがないことを示す情報が書き込まれていた場合は、この情報を、対応する優先度クラスの先頭ポインタレジスタに書き込む。これにより、次回の読み出しでは、下位クラスのパケットが読み出される。
以上の処理により、パケットは送信キューから順次読み出され、宛先の端末が接続されたネットワークに送出される。バッファ制御回路１９０に設けられたレジスタ群に保持されたポインタと、付属セル領域１４０ｂに格納されたポインタとを用いることにより、送信キューに送信予約された順に、パケットを効率よく読み出すことができる。また、読み出したパケットを指し示していたポインタをポインタスタック１７０に返却することにより、次の受信パケットを格納可能な空き領域が開放され、送信バッファを効率的に利用することができる。
〔第２の実施の形態〕
次に、本発明の第２の実施の形態例について説明する。第２の実施の形態では、ネットワークスイッチ装置全体の構成は、図３と同様である。ただし、第１の実施の形態と異なる点は、送信バッファ１４１〜１４４内に格納するデータがパケットの内容のみで、付属データ領域が形成されないこと、および、バッファ制御回路１９０に、各送信キューに登録されたすべてのパケットのポインタを管理するポインタメモリが優先度クラスごとに設けられ、これらのポインタメモリを用いて送信キューに対するパケットの登録、廃棄、読み出しの処理が行われることである。
図８は、バッファ制御回路１９０に設けられるポインタメモリと、送信キューとの関係を示す図である。
本実施の形態でも、上記の第１の実施の形態の場合と同様に、各送信バッファ１４１〜１４４には１つずつの送信キューが形成される。そして、各送信キューでは、優先度クラスが高いパケットほど先に送信予約されるように、登録が行われる。また、同じ優先度クラスのパケットでは、受信した順に登録される。従って、送信キューには、図８に示すように、高優先度クラスのパケットＰｈ（１）〜Ｐｈ（ｓ）が連結された後に、中優先度クラスのパケットＰｍ（１）〜Ｐｍ（ｔ）が連結され、さらに低優先度クラスのパケットＰｌ（１）〜Ｐｌ（ｕ）が連結される（ただし、ｓ，ｔ，ｕはそれぞれ１以上の整数である）。
また、本実施の形態では、上記の構造の送信キューを管理するために、バッファ制御回路１９０は、送信キュー内に登録されたすべてのパケットを指し示すポインタを保持するポインタメモリを、優先度クラスごとに具備する。図５のように３段階の優先度クラスの取り扱いが可能な場合は、高優先度、中優先度、低優先度の各クラスに対して、高優先ポインタメモリ１９３ａ、中優先ポインタメモリ１９３ｂ、低優先ポインタメモリ１９３ｃがそれぞれ設けられる。
各ポインタメモリには、バッファ制御回路１９０がポインタスタック１７０から取得したポインタが格納される。このとき、各ポインタメモリは、ポインタを取得した順にＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）方式で保持することができるとともに、最後尾のポインタを順次削除することが可能となっている。
以下、これらのポインタメモリに格納されたポインタを用いたバッファ制御回路１９０の処理を、フローチャートを用いて説明する。なお、以下の図９および図１０に示すフローチャートの説明では、例として、ネットワーク２１からネットワーク２２に対して転送すべきパケットを受信した場合を想定する。また、図９および図１０の説明では、必要に応じて、ネットワークスイッチ装置１００内の他の要素における処理についての説明も加える。
図９は、パケットを送信バッファに書き込む場合のバッファ制御回路１９０における処理の流れを示すフローチャートである。
第１の実施の形態の場合と同様に、受信インタフェース１１１において受信されたパケットは、受信バッファ１２１に一旦格納される。そして、格納されたパケットがデータ転送回路１５０に引き渡されるとともに、このパケットのヘッダ情報が、ヘッダ解析回路１６０に通知される。ヘッダ解析回路１６０は、パケットの宛先から優先度クラスを判断し、バッファ制御回路１９０に宛先とともに通知する。また、宛先はデータ転送回路１５０に対しても通知される。
［ステップＳ９０１］バッファ制御回路１９０は、ヘッダ解析回路１６０より、新たに受信されたパケットの宛先と優先度クラスの通知を受ける。
［ステップＳ９０２］使用量監視回路１８０からの情報を参照して、宛先に対応する送信バッファ１４２に空き領域があるか否かを判断する。空き領域がある場合は、ステップＳ９０３に進み、ない場合はステップＳ９０５に進む。
ここで、受信バッファ１２１からパケットを受け取ったデータ転送回路１５０は、ヘッダ解析回路１６０からの通知に基づいて、このパケットの宛先を判断する。そして、同様に、使用量監視回路１８０からの情報を参照して、宛先に対応する送信バッファ１４２に空き領域があるか否かを判断し、この判断に応じてパケットを転送するか否かを決定する。
［ステップＳ９０３］送信バッファ１４２に空き領域がある場合は、ポインタスタック１７０からＰＯＰされたポインタが、データ転送回路１５０およびバッファ制御回路１９０に供給される。データ転送回路１５０は、送信バッファ１４２にパケットを転送し、取得したポインタの指し示すアドレスに書き込む。
［ステップＳ９０４］バッファ制御回路１９０は、送信バッファ１４２に対応する各優先度クラスのポインタメモリのうち、受信パケットの優先度クラスに対応するポインタメモリの最後尾に、ステップＳ９０３で取得したポインタを格納する。これにより、受信パケットが送信キューに登録される。
［ステップＳ９０５］  また、宛先に対応する送信バッファ１４２の空き容量がない場合には、まず、受信パケットの優先度クラスより下位クラスに対応するポインタメモリを参照して、いずれかのポインタメモリにポインタが格納されているか否かを判断する。格納されている場合は、より下位クラスのパケットが送信キューにすでに登録されていると判断され、ステップＳ９０６に進む。
また、格納されていない場合は、何も処理が行われないままパケットの書き込み処理が終了される。この場合、受信パケットは、送信キュー中に登録されているパケットの中で最下位あるいはそれよりさらに下位の優先度クラスに属していることになり、廃棄すべきパケットと判断される。使用量監視回路１８０は、送信バッファ１４２の空き領域がないことをデータ転送回路１５０に通知し続け、この通知に基づいて、データ転送回路１５０は、受信バッファ１２２から受け取ったパケットを廃棄する。
［ステップＳ９０６］受信パケットより下位クラスのパケットが送信キューにすでに登録されている場合には、ポインタが登録されているポインタメモリのうち、最下位クラスに対応するポインタメモリを参照し、このポインタメモリの最後尾のポインタをポインタスタック１７０に返却するとともに、ポインタメモリから消去する。これにより、送信バッファ１４２の領域が、１パケット分だけ開放される。
［ステップＳ９０７］送信バッファ１４２の領域が開放されたことを、使用量監視回路１８０に通知し、ステップＳ９０３に進む。これにより、使用量監視回路１８０は、送信バッファ１４２に空き領域が発生したと判断して、このことをデータ転送回路１５０に通知する。データ転送回路１５０は、この通知を受けるとともに、ステップＳ９０３に対応する処理によりポインタスタック１７０からポインタを取得し、パケットを送信バッファ１４２に転送して、取得したポインタに指し示されるアドレスに書き込む。
以上の処理により、上記の第１の実施の形態と同様な送信キューが形成される。すなわち、受信パケットは、ステップＳ９０３およびＳ９０４の処理により、送信キューにすでに登録されていた同じ優先度クラスのパケットのうち、最後に登録されたパケットの次に送信予約される。また、受信パケットと同じ優先度クラスのパケットが送信キュー内に登録されていない場合には、送信キュー内でこの優先度クラスに該当する位置に受信パケットが登録される。
また、例えばネットワーク２２宛てにパケットが集中して送信バッファ１４２が埋め尽くされた場合には、ステップＳ９０６〜Ｓ９０７の処理により、送信キューに登録されているもののうち、最も優先度クラスが低く、かつ最後に登録されたパケットが廃棄される。また、受信パケットが属する優先度クラスより下位クラスのパケットが送信キューに登録されていない場合は、受信パケット自身が廃棄される。
図１０は、パケットを送信バッファから読み出す場合のバッファ制御回路１９０における処理の流れを示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
［ステップＳ１００１］バッファ制御回路１９０は、ポインタが格納されているポインタメモリのうち、最上位クラスのポインタメモリを参照して、格納されているポインタを取り出す。このとき、取り出したポインタはポインタメモリから消去される。
［ステップＳ１００２］取り出したポインタが指し示すパケットを読み出し、対応する送信インタフェース１３２に転送する。これにより、読み出されたパケットがネットワーク２２に送出される。
［ステップＳ１００３］取り出したポインタを、ポインタスタック１７０にＰＵＳＨして返却する。
［ステップＳ１００４］送信バッファ１４２の領域が開放されたことを、使用量監視回路１８０に通知する。
以上の処理により、パケットは送信キューから順次読み出され、宛先の端末が接続されたネットワークに送出される。バッファ制御回路１９０に設けられたポインタメモリに保持されたポインタを用いることにより、送信キューに送信予約された順に、パケットを効率よく読み出すことができる。また、読み出したパケットを指し示していたポインタをポインタスタック１７０に返却することにより、次の受信パケットを格納可能な空き領域が開放され、送信バッファを効率的に利用することができる。
このように、第２の実施の形態では、第１の実施の形態と比較して、ポインタを管理する処理が大幅に単純化される。しかし、第２の実施の形態の場合、各ポインタメモリは、ＦＩＦＯ方式によるデータの格納とともに、最後尾のデータを順次消去する機能を持つ必要があるため、書き込み・読み出しの制御が複雑となり、高価な制御回路が必要となる。従って、第２の実施の形態では、部品コストが高くなるとともに、設置面積も大きくなる。
なお、以上の第１および第２の実施の形態例では、送信ポートごとの送信バッファ１４１〜１４４の領域を共有メモリ内に設け、この共有メモリへの書き込み位置を１つのポインタスタック１７０で一元的に管理する構成とした。しかし、各送信バッファ１４１〜１４４の領域が物理的に分離された構成としてもよい。この場合は、送信バッファ１４１〜１４４ごとにポインタスタック１７０を設けて、書き込みおよび読み出しのアドレス管理を行えばよい。また、この場合には、使用量監視回路１８０は、各ポインタスタックに未使用のポインタが残っているか否かにより、各送信バッファ１４１〜１４４に空き領域があるか否かを判断することも可能である。
〔第３の実施の形態〕
次に、本発明の第３の実施の形態例について説明する。第３の実施の形態では、ネットワークスイッチ装置全体の構成は、図３と同様である。ただし、第１および第２の実施の形態と異なる点は、各送信バッファ１４１〜１４４内に複数の送信キューが形成されることである。
図１１は、各送信バッファに形成される送信キューの例を示す図である。なお、以下の説明では、優先度の高い方からＡ〜Ｈの８段階の優先度クラスを取り扱うことが可能であるとする。
図１１に示すように、各送信バッファ１４１〜１４４内では、それぞれ３つずつの送信キューが形成される。また、各送信キュー内には、１つ以上の隣接する優先度クラスのパケットが登録される。図１１の例では、第１の送信キューには優先度クラス“Ａ”“Ｂ”“Ｃ”のパケットを、第２の送信キューには優先度クラス“Ｄ”“Ｅ”のパケットを、第３の送信キューには優先度クラス“Ｆ”“Ｇ”“Ｈ”のパケットをそれぞれ登録可能となっている。そして、各送信キューは最大容量があらかじめ決められている。
なお、図１１の例では、送信バッファ１４１においては、第１の送信キューＱ１１には優先度“Ａ”“Ｂ”“Ｃ”のパケットが、第２の送信キューＱ１２には優先度“Ｄ”“Ｅ”パケットが、第３の送信キューＱ１３には優先度“Ｆ”“Ｇ”“Ｈ”のパケットがそれぞれすでに登録された状態を示している。また、送信バッファ１４４においては、第１の送信キューＱ４１には優先度“Ａ”“Ｃ”のパケットのみが、第２の送信キューＱ４２には優先度“Ｄ”“Ｅ”パケットが、第３の送信キューＱ４３には優先度“Ｆ”のパケットのみがそれぞれすでに登録された状態を示している。
このような送信キューへの登録を管理するために、使用量監視回路１８０は、各送信バッファ１４１〜１４４におけるバッファ使用量を、送信キューごとにカウントする。また、送信キュー内のパケット間の連結の管理は、上記の第１および第２の実施の形態のいずれも利用可能である。そして、バッファ制御回路１９０は、パケットの読み出し時に、割り当てられた優先度クラスの高い送信キューから順に、パケットが登録されているか否かを判断して、登録されている送信キューからパケットを順次読み出す。
なお、このようなネットワークスイッチ装置では、１つの送信キューに登録可能な１つ以上の優先度クラスの単位で、登録可能なパケット数が制限されることから、輻輳の発生時に、下位クラスの送信キューには空き領域があるにもかかわらず、上位クラスのパケットが廃棄されてしまう可能性があり得る。このような事態を回避するためには、上位クラスのパケットが登録される送信キューほど、割り当てるバッファ容量を大きくすることが望ましい。
以上説明したように、本発明のネットワークスイッチ装置では、宛先のネットワークに対応するバッファにそれぞれ１つの送信キューが形成され、各送信キューでは、優先度クラスが高く、かつ先に受信されたパケットほど先に送信されるようにパケットが登録される。このとき、優先度クラスごとに割り当てられるバッファ容量が特定されないため、受信パケットはその優先度クラスに関係なくバッファの空き領域に格納される。従って、特定の送信キューにおいて輻輳が発生した場合に、優先度クラスが高いパケットほどより確実に送信が行われるとともに、バッファ内の使用効率が高められ、バッファの容量を抑制して部品コストを低減することができる。
また、例えば、バッファ制御回路によって、各送信キューに登録したパケット間の連結を、各パケットの各バッファにおける書き込み位置に基づく連結リスト構造として管理することにより、各送信キューへの登録時や送信キューからの出力時のアドレス管理が効率化される。
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応するすべての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【図１】
2004066570.tif 000003
【図２】
2004066570.tif 000004
【図３】
2004066570.tif 000005
【図４】
2004066570.tif 000006
【図５】
2004066570.tif 000007
【図６】
2004066570.tif 000008
【図７】
2004066570.tif 000009
【図８】
2004066570.tif 000010
【図９】
2004066570.tif 000011
【図１０】
2004066570.tif 000012
【図１１】
2004066570.tif 000013
【国際調査報告】
2004066570.tif 000014
2004066570.tif 000015
2004066570.tif 000016
2004066570.tif 000017