JP4879382B2 - パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 - Google Patents
パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 Download PDFInfo
- Publication number
- JP4879382B2 JP4879382B2 JP2000124667A JP2000124667A JP4879382B2 JP 4879382 B2 JP4879382 B2 JP 4879382B2 JP 2000124667 A JP2000124667 A JP 2000124667A JP 2000124667 A JP2000124667 A JP 2000124667A JP 4879382 B2 JP4879382 B2 JP 4879382B2
- Authority
- JP
- Japan
- Prior art keywords
- packet
- length
- value
- variable
- class
- 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
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
-
- 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
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/15—Flow control; Congestion control in relation to multipoint traffic
-
- 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/20—Traffic policing
-
- 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/24—Traffic characterised by specific attributes, e.g. priority or QoS
- H04L47/2425—Traffic characterised by specific attributes, e.g. priority or QoS for supporting services specification, e.g. SLA
- H04L47/2433—Allocation of priorities to traffic types
-
- 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/24—Traffic characterised by specific attributes, e.g. priority or QoS
- H04L47/2441—Traffic characterised by specific attributes, e.g. priority or QoS relying on flow classification, e.g. using integrated services [IntServ]
-
- 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/29—Flow control; Congestion control using a combination of thresholds
-
- 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/30—Flow control; Congestion control in combination with information about buffer occupancy at either end or at transit nodes
-
- 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/32—Flow control; Congestion control by discarding or delaying data units, e.g. packets or frames
-
- 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/43—Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
-
- 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/60—Queue scheduling implementing hierarchical 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/62—Queue scheduling characterised by scheduling criteria
- H04L47/625—Queue scheduling characterised by scheduling criteria for service slots or service orders
- H04L47/627—Queue scheduling characterised by scheduling criteria for service slots or service orders policing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/20—Support for services
- H04L49/205—Quality of Service based
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/25—Routing or path finding in a switch fabric
- H04L49/253—Routing or path finding in a switch fabric using establishment or release of connections between ports
- H04L49/254—Centralised controller, i.e. arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3045—Virtual queuing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3072—Packet splitting
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/60—Software-defined switches
- H04L49/608—ATM switches adapted to switch variable length packets, e.g. IP packets
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5647—Cell loss
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5651—Priority, marking, classes
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5652—Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5679—Arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5681—Buffer or queue management
- H04L2012/5682—Threshold; Watermark
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/10—Packet switching elements characterised by the switching fabric construction
- H04L49/101—Packet switching elements characterised by the switching fabric construction using crossbar or matrix
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/20—Support for services
- H04L49/201—Multicast operation; Broadcast operation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3009—Header conversion, routing tables or routing tags
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3063—Pipelined operation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/50—Overload detection or protection within a single switching element
- H04L49/501—Overload detection
- H04L49/503—Policing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Quality & Reliability (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、ＩＰ（Internet Protocol ）パケットのような可変長パケット（またはフレーム）のルーチングを行なうパケットスイッチ、特に、可変長パケットに対するＱｏＳ（Quality of Service）制御、廃棄制御、マルチキャスト制御といった複雑な制御を実現する大容量パケットスイッチ、それに用いることの可能なスケジューリング装置、廃棄制御回路、マルチキャスト制御回路およびＱｏＳ制御装置に関する。
【０００２】
【従来の技術】
近年、インターネットの急速な普及により、通信トラヒック需要が急増しており、Ｔｂｐｓ（テラビット／秒）クラス以上の高速・大容量のルータやスイッチの実現が望まれている。
従来、ＩＰパケットのような可変長パケットを処理するルータ装置において、パケットフォワーディング処理をハードウェア化することにより、高速化を図るアプローチが行われているが、ＱｏＳ制御、廃棄制御、マルチキャスト制御といった複雑な処理については、ソフトウェア処理、またはハードウェアで行う場合にも低速での処理に限られていた。またＡＴＭ（Asynchronous Transfer Mode）交換機においては、基本的に固定長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御が行われていた。
【０００３】
前者のルータ装置のようにソフトウェアベースの方式では、複雑な処理を実装することができるが、回線速度の高速化にともない、回線速度と同等の速度でソフトウェアの処理を実現することは困難となってきており、より高速・大容量の処理は困難となっていた。
後者のＡＴＭ交換機では、固定長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御を行うため、ＩＰパケットのような可変長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御する機能を持たない。またＧＦＲ（Guaranteed Frame Rate ）というＡＴＭにおいてＡＡＬ５の可変長パケット識別を利用して、可変長パケットレベルのＱｏＳ保証、廃棄制御を行うという試みも行われているが、この方式でも、パケットのスイッチング、転送単位はセルと呼ばれる固定長パケット単位であり、ネットワークを構成する全ノードをＡＴＭ交換機で実現する必要があり、ＩＰパケット単位でスイッチング、転送処理を行うパケットスイッチとして適用することはできない。
【０００４】
次に、ＱｏＳ制御に関しては、主に、使用帯域が予め規定されないベストエフォートクラスの可変長パケット間での公平な帯域分配方法として、ＷＦＱ（Weighted Fair Queueing）が知られている（A.K.Parekh, R.G.Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case", IEEE/ACM trans. On Networking, Vol 1, No.3, pp.344-357, Jun. 1993; A.K.Parekh, R.G.Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Multiple-Node Case", IEEE/ACM trans. On Networking, Vol 2, No.2, pp.137-150, Jun. 1993）。
【０００５】
ＷＦＱは、キューイングされているコネクションに設定されているウェイトに比例して余剰帯域を分配するＧＰＳ（Generalized Processor sharing ）を基本にしている。ＧＰＳでは、アクティブな（キューを使用している）任意のコネクション（ｉ）（ｊ）について常に式（１）が成立するように読出しデータ量を分配する帯域割り当て方式である。
【０００６】
Ｓ（ｉ，τ，ｔ）／Ｓ（ｊ，τ，ｔ）≧Φ（ｉ）／Φ（ｊ） …（１）
ここで、Φ（Ｎ）はコネクションＮに対するウェイト、Ｓ（Ｎ，τ，ｔ）はコネクションＮに対して時間〔τ，ｔ〕の間にサービスされるデータ量である。また式（１）で等号が成り立つのはコネクション（ｉ）と（ｊ）のデータがともにキューイングされているときである。例えば、各コネクション＃０，＃１，＃２，＃３にそれぞれ、ウェイトを０．１：０．２：０．４：０．３の割合で与えておき、もし仮にコネクション＃３のみノンアクティブ（パケットがキューイングされていない）で、それ以外のコネクションがアクティブであるとき、コネクション＃３を除くコネクション＃０〜＃２のコネクションで、各々読出し帯域が０．１：０．２：０．４になるように帯域を分配する。
【０００７】
ＧＰＳは基本的に無限小のビット単位での帯域分配を意味するが、現実には分配単位が可変長パケット（フレーム）毎であるため、ＷＦＱではＧＰＳをフレームレベルの公平な帯域分配に拡張している。
ＷＦＱでは、フレーム到着時にフローｉのｋ番目のパケットが時刻ｔ（ｉ，ｋ）に到着し、そのフレーム長をＬ（ｉ，ｋ）としたときの終了予定時刻Ｆ（ｉ，ｋ）を式（２）で計算し、Ｆの小さい順から読み出す。
【０００８】
Ｆ（ｉ，ｋ）＝ｍａｘ｛Ｆ（ｉ，ｋ−１），ｔ（ｉ，ｋ）｝＋Ｌ（ｉ，ｋ）／ｒ（ｉ，ｋ） …（２）
但し、ｒ（ｉ）＝Φ（ｉ）／ΣΦ×Ｒ、ここでΣΦはキューイングされているコネクションのウェイトの合計であり、Ｒは出力リンクのレートである。
ここで、ｒ（ｉ，ｋ）はパケットがキューから読み出される度に変化するため、全コネクションについてＦ（ｉ，ｋ）の再計算が必要となり、また、キューイングされている全パケットについて、終了予定時刻Ｆ（ｉ，ｋ）を保持しなければならないため、ハード規模が大きくなるという問題があった。そのため実時間の代わりにVirtual Time（キューイングされているコネクション数に応じて刻みの変化する時間カウンタ）を式（３）のように定義し、Ｆ（ｉ，ｋ）を式（４）のように再定義し、Virtual TimeをΣΦとＲが変化するたびに再計算し、Ｆ（ｉ，ｋ）については、パケット到着時に１回計算するのみで実現する方式が提案されている。
【０００９】
Ｖｔ＝Ｖ（τ）＋（Ｒ／ΣΦ）（ｔ−τ） …（３）
Ｆ（ｉ，ｋ）＝ｍａｘ｛Ｆ（ｉ，ｋ−１），Ｖｔ（ｉ，ｋ）｝＋Ｌ（ｉ，ｋ）／Φ（ｉ） …（４）
しかしながら、Virtual timeを用いると、演算量の削減が図れるが、実時間で処理する必要のある、転送レートが規定された帯域保証クラスのパケットとの間の優先度制御が困難となるという問題が生じていた。
【００１０】
廃棄制御に関しては、アダプティブな廃棄方式としてＲＥＤ（Random Early Detection）が知られている（Internet Society RFC2309）。これは、輻輳状態が同期してしまうことを防ぐため、輻輳状態になったらバッファが溢れる前に輻輳状態に応じた確率でランダムに廃棄を行う方式である。これにより、ＴＣＰ(Transmission Control Protocol）のような輻輳制御機能を持つプロトコルでは早めに送信レートを落とすことが出来、かつ全端末の動作が同期しないので安定したスループットが出るという特長を持つ。
【００１１】
しかしながら、ＲＥＤは、廃棄をランダムに行う必要があるためアルゴリズムが複雑でソフトウェアにより実装されており、高速化には向いていなかった。また、基本的に廃棄はフレーム（可変長パケット）到着時に行うため、その時点でバッファに溜まっているデータが全て掃けた後でないと廃棄が端末に通知されないという問題があった。
【００１２】
マルチキャスト制御に関しては、バッファアドレス管理方式として、従来では固定長パケットに対するパケットｂｙパケットの動作のみが実現されており、複数の固定長パケットの連続からなる可変長パケットを意識した制御は実現されていない。
【００１３】
【発明が解決しようとする課題】
したがって本発明の目的は、可変長パケットに対して、高速かつ少ないハードウェア規模でＱｏＳ制御、廃棄制御、マルチキャスト制御といった複雑な制御を実現する大容量パケットスイッチ、それに用いることの可能なスケジューリング装置、廃棄制御回路、マルチキャスト制御回路およびＱｏＳ制御装置を提供することにある。
【００１４】
【課題を解決するための手段】
本発明によれば、複数の入力回線からの可変長パケットを固定長パケットに分割するパケット分割部と、複数の入力回線のそれぞれに対して設けられ、その各々が、複数の出力回線の各々について、指定可能なＱｏＳ（Quality of Service）クラス数よりも少数の相異なる優先度が与えられたキューを有し、対応する入力回線からの固定長パケットを、出力回線およびＱｏＳクラスに従って該キューのいずれかに格納する複数の入力バッファ部と、入力バッファ部のキューに格納された固定長パケットを、キューに与えられた優先度に従って単位時間内では出力回線が同じである２以上の固定長パケットが読み出されないように読み出すスケジューラと、スケジューラが読み出した固定長パケットの各々を複数の出力回線のうちの指定された１つにルーチングするスイッチと、複数の出力回線のそれぞれに対して設けられ、スイッチから出力される固定長パケットからの可変長パケットの組み立ておよびＱｏＳクラスに基づく優先制御を行なうための複数の出力バッファ部とを具備するパケットスイッチが提供される。
【００１５】
本発明によれば、指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、可変長パケットがキューの先頭に達したとき第１の値を対応するトークンに加算する手段と、単位時間が経過するごとにアクティブなＱｏＳクラスのトークンから第２の値を減算する手段と、出力回線へのパケット装置が可能なとき、アクティブなＱｏＳクラスの中で、対応するトークンが最小もしくは０であるものの可変長パケットの読み出しを開始する手段とを具備するスケジューリング装置もまた提供される。
【００１６】
本発明によれば、指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、帯域保証クラスの可変長パケットおよび指定帯域内で入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第１のカウンタと、ベストエフォートクラスの可変長パケットおよび指定帯域を超えて入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第２のカウンタと、第１のカウンタについて０でないカウント値を有するＱｏＳクラスおよび第２のカウンタについて０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含むスケジューリング装置もまた提供される。
【００１７】
本発明によれば、バッファ内に格納されているパケットの量のその閾値との差分にバッファの先頭に存在する可変長パケットのパケット長を乗じてその結果を出力する演算回路と、カウンタと、演算回路の演算結果をカウンタに加算する加算回路と、カウンタの値が所定値を超えているときバッファの先頭に存在する可変長パケットを一度に廃棄し、前記パケット長に所定値を乗じた値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路もまた提供される。
【００１８】
本発明によれば、バッファ内に格納されているパケットの量のその閾値との差分を出力する演算回路と、カウンタと、演算回路の演算結果をカウンタに加算する加算回路と、カウンタの値が所定値を超えているときバッファの先頭に存在する固定長パケットを廃棄し、所定値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路もまた提供される。
【００１９】
本発明によれば、バッファに格納されている、マルチキャスト制御すべき可変長パケットのアドレスを格納するマルチキャストキューと、複数の出力回線のそれぞれに対して設けられた複数の出力バッファキューと、バッファに格納されている可変長パケットのアドレスを管理するアドレス管理テーブルと、マルチキャスト制御すべき可変長パケットのアドレスがマルチキャストキューに格納されたとき、該可変長パケットのアドレスを含むレコードをその出力先の数だけアドレス管理テーブルに格納し、その出力先に対応する出力バッファキューに、該レコードのアドレスをそれぞれ格納する制御手段とを具備するマルチキャスト制御回路もまた提供される。
【００２０】
本発明によれば、ＱｏＳクラスを有する可変長パケットをスイッチングするパケットスイッチにおいて、複数のＱｏＳクラスを簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記可変長パケットの読み出し制御を行う手段を備えたことを特徴とするパケットスイッチもまた提供される。
本発明によれば、ＱｏＳクラスを有するＩＰパケットを固定長パケットへ変換し、固定長パケット単位でスイッチングするパケットスイッチにおいて、ＩＰパケットの優先度クラスを、ＩＰパケットに割り当てられるＱｏＳクラスの数より少ない数の簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記固定長パケットの読み出し制御を行う手段を備えたことを特徴とするパケットスイッチもまた提供される。
【００２１】
本発明によれば、ＱｏＳクラスを有するＩＰパケットを固定長パケットへ変換し、固定長パケット単位でスイッチングするパケットスイッチにおいて、ＩＰパケットの優先度クラスを、ＩＰパケットに割り当てられるＱｏＳクラスの数より少ない数の簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記固定長パケットをスイッチへ読み出し制御を行う手段と、スイッチング後の前記固定長パケットを、ＩＰパケットに割り当てられるＱｏＳクラスに基づいて読み出し制御する手段を備えたことを特徴とするパケットスイッチもまた提供される。
【００２２】
本発明によれば、高優先グループに属する１つ以上のＱｏＳクラスの中からパケットを読み出すべき１つのＱｏＳクラスを選択する第１の選択部と、低優先グループに属する１つ以上のＱｏＳクラスの中からパケットを読み出すべき１つのＱｏＳクラスを選択する第２の選択部と、高優先グループと低優先グループのいずれか一方を選択し、それによって第１または第２の選択部が選択したＱｏＳクラスのパケットを選択する第３の選択部とを具備するＱｏＳ制御装置もまた提供される。
【００２３】
【発明の実施の形態】
図１に本発明の一実施形態に係るパケットスイッチを概念的に示す。入力回線から入力された可変長パケットは、パケット分割部１０において固定長パケットに分割され入力バッファ部１２にバッファリングされる。入力バッファ部１２は、Ｎ本の入力回線数分あり、各入力バッファは論理的にＭ本の出力回線毎、およびＱｏＳ毎（帯域保証クラス１１、ベストエフォートクラス１７）に分かれている。各入力回線より入力バッファ部１２へ入力されたパケットは各々対応する出力回線毎、ＱｏＳ毎にバッファリングされる。この際、ＱｏＳクラスを予め契約や呼受け付け制御により入力トラヒック量の予想可能な帯域保証クラスと、契約や呼受け付け制御がなく入力トラヒック量の予想ができないベストエフォートクラスの２クラスのいずれかに縮退して割り当てる。
【００２４】
入力バッファ部１２にバッファリングされた各パケットは、回線間スケジューラ１４により、スイッチ部１６への送出タイミングが調整される。この際、回線間スケジューラ１４では、はじめに出力回線毎にバッファリングされたパケットのうち帯域保証クラスのパケットについて、複数の入力回線で同一の出力回線を選択しないように出力回線を選択する、競合制御を行う（図１：１３）。次にベストエフォートクラスのパケットについて、このとき選択されなかった出力回線について、同様に複数の入力回線で同一の出力回線を選択しないように競合制御を行う（図１：１５）。以上のような回線間スケジューリング動作を単位時間内、例えば、１つの出力回線で固定長パケット１個に相当するデータを送出するに要する時間内で実施する。これにより、各入力回線間の論理出力バッファ毎、ＱｏＳクラス毎の競合制御のもとで各入力バッファから出力されるパケットが選択され、スイッチ部１６へ転送される。転送されたパケットはスイッチ部１６でパケットに付与されたあて先情報を元に各出力バッファ部１８へスイッチングされる。
【００２５】
出力バッファ部１８に入力した各パケットは、実際のＱｏＳクラス毎（通常３クラス以上）にバッファリングされる。出力バッファ部１８では、各出力回線内の各ＱｏＳクラス毎のＱｏＳ制御（設定レートや優先順位に応じた読み出し順序制御）を行い、各出力回線にパケットを出力する。
ここでは、入力バッファ部１２でのＱｏＳクラス数を帯域保証クラスとベストエフォートクラスの２クラスに縮退させている。これにより、多数のキュー間（入力回線数×出力回線数×ＱｏＳクラス数（３以上））での競合制御を入力回線数×出力回線数×２に削減できる。
【００２６】
一般にＱｏＳ制御としては、単純な優先制御だけでなく、読み出しレートなどの複雑な読み出し順序の制御が必要であるが、ＱｏＳクラスを帯域保証クラスとベストエフォートクラスに縮退させ、帯域保証クラスをスケジューリングしてからベストエフォートクラスをスケジューリングすることによりスケジューリング処理を簡単化している。
【００２７】
さらに、スイッチの内部動作速度を入力バッファの到着速度より高め、スイッチング後の出力バッファ１８において、実際のＱｏＳクラス毎のＱｏＳ制御を行うことにより、パケットスイッチトータルとしてのＱｏＳ制御ポイントを出力バッファ部のＱｏＳ制御に集約できる。この際、出力バッファ部では、各出力回線毎のＱｏＳクラス制御のみ行えば良いことから、スイッチ全体のＱｏＳ制御が必要な入力バッファ部で行う場合に比べ、必要なハードウェアの量は少ない。
【００２８】
図１のパケットスイッチで採用されている、出力回線毎の論理キューを持つ入力バッファ型スイッチでは、ほぼ１００％のスループットが実現されるので、予めトラヒック量が予想できるクラスに対しては、入力バッファ側におけるパケットの廃棄率や遅延時間を出力バッファ側におけるＱｏＳ制御によって生じるパケット廃棄率や遅延時間に比べて非常に小さくできる。スイッチ内部の動作速度を高めることにより、これらはさらに小さくすることができる。したがって、入力側で複数のＱｏＳクラスを２クラスにマッピングしても実質的に問題ない。
【００２９】
図２および図３にそれぞれ本発明における可変長パケットフォーマットの一例、および可変長パケットを複数の固定長パケットに分離するときの固定長パケットのフォーマットの一例を示す。また、表１および表２にはそれぞれ、図２および図３における各フィールドの説明を示す。ここでは、可変長パケットとしてＩＰｖ４フォーマット（Internet Society RFC791 ）を用いている。但し、宛先アドレスのような、それによって各パケットのフローまたはコネクションを識別できる情報要素、およびＱｏＳクラス値が含まれているパケットであれば、どのようなフォーマットでも良い。ここでＱｏＳクラス値は、パケット中に記述されたＱｏＳクラス値ではなく、フローやコネクションに対して予め設定されたテーブルからＱｏＳクラスを変換して求めても良い。固定長パケットも同様に装置内部ローカルなパケットであるため、必要な情報要素が含まれていれば、フォーマットはどのようなフォーマットでも良い。
表１
Ｖｅｒｓ バージョン番号
ＩＨＬ ヘッダ長
Ｔｙｐｅ ｏｆ Ｓｅｒｖｉｃｅ 優先度
Ｔｏｔａｌ Ｌｅｎｇｔｈ ＩＰｖ４ペイロード長
Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ フラグメントＩＤ
Ｆｌａｇｓ フラグ
Ｆｌａｇｍｅｎｔ Ｏｆｆｓｅｔ フラグメントオフセット
Ｔｉｍｅ ｔｏ Ｌｉｖｅ ホップ期限
Ｐｒｏｔｏｃｏｌ プロトコル
Ｈｅａｄｅｒ Ｃｈｅｃｋｓｕｍ ヘッダチェックサム
Ｓｏｕｒｃｅ Ａｄｄｒｅｓｓ 送信元アドレス
Ｄｅｓｔｉｎａｔｉｏｎ Ａｄｄｒｅｓｓ あて先アドレス
Ｐａｙｌｏａｄ ペイロード
表２
ＥＮ 空きセル識別子（０：空きセル、１：有効セル）
Ｃ マルチキャスト識別子
ＱＣＰ Ouality of Service：品質クラス識別子
ＣＩＤ コネクション識別子
ＰＫＬ ペイロード長
Ｆ タギングフラグ（０：高優先クラス、１：低優先クラス）
ＦＲＩ フレームタイプ（００：中間、０１：先頭、１０：最終、１１：先頭＆最終）
図４に図１のスイッチ部１６の入力側におけるスケジューリングを実現する具体的な構成を示す。図４の入力バッファ部のスケジューラ構成において、入力されたフレームは、ポリシング制御部２０において、予め設定されたレート以上のものについてはタギングされる。タギング情報はフレーム毎に付与され、別線、または図２の可変長パケットフォーマットに内部ヘッダを追加してそこにビットを付与することにより後段に転送される。パケット分割部１０では入力された可変長パケットを一定長のセグメントに分割する。ヘッダ付与部２２では、ヘッダ変換テーブル２４の情報をもとに各セグメントに各種ヘッダ情報を付与して図３の固定長パケットを組み上げる。
【００３０】
ここで、ＱｏＳクラスに関しては、予めコネクション毎、またはフロー毎に設定されたＱｏＳクラス（例えば４クラス）のテーブルを参照しＱＣＰビットに０〜３の値を付与するとともに、これらのＱｏＳクラスをさらに帯域保証クラスとベストエフォートクラスの２クラスにマッピングする。この２クラスにマッピングされたＱｏＳクラスを縮退ＱｏＳクラスと呼ぶことにする。入力バッファ部１２、およびスケジューラ部２５ではこの縮退ＱｏＳクラスと出力回線番号情報に基づき、それぞれパケットのキューイング、パケット読み出しのスケジューリングを行う。
【００３１】
ここで、スケジューラ部２５では、後段のマトリックススイッチ部へ入力される全パケットについて、効率良くしかも同一の出力回線を持つパケットが同時に転送されないようにスケジューリングを行う。さらにこの競合制御時に縮退ＱｏＳクラスに応じて、初めに帯域保証クラスについてスケジューリングを行い、次に帯域保証クラスのスケジューリングで選択されなかった入力回線と出力回線についてベストエフォートクラスについてスケジューリングを行う。スケジューリング処理の具体的な例については後に詳しく説明する。
【００３２】
図５は、スケジューラの正順、逆順を考慮したパイプラインの８回線について帯域保証クラス、ベストエフォートクラスをスケジューリングした場合のパイプラインのシーケンスである。
図５に示した例では、パイプラインのシーケンス順序を入れ替えることにより、１周期に正順、逆順を考慮したパイプラインと同じパターンが同数現れるようになっており、入力回線間の公平性を保証している。さらに同一時間に同一入力回線に対する処理の競合を避けることになり、同じ処理をしなければならないハード処理量を削減している。
【００３３】
尚、スケジューリングアルゴリズムについては、帯域保証クラスの方がベストエフォートクラスより優先度が高くなれば、他のアルゴリズムを用いても良い。
以上のようなスケジューリング処理により決定されたパケットは入力バッファ部からよみだされ、マトリックススイッチにおいて、出回線情報にもとづいてスイッチングされる。このとき、マトリックススイッチのスイッチング速度を各回線のデータレートの総和より大きく（内部速度アップという）することにより、入力バッファ部の廃棄遅延特性の向上を図り、入力バッファ部における競合によりスイッチトータルとしての品質が劣化するのを抑制してもよい。
【００３４】
スイッチングされた固定長パケットは一旦出力バッファ部にキューイングされる（図１：１８）。この際、後に説明するように、可変長パケットへ戻してからＱｏＳ制御を行なうか、または先に固定長パケットのままでＱｏＳ制御を行ってから可変長パケット組立てを行っても良い。
以上のような一連の処理により、入力バッファ側では、縮退した２クラスのみ簡易なＱｏＳ制御を行いながら、出力バッファ側で３クラス以上のＱｏＳ制御を行うことにより、スイッチトータルとして、３クラス以上のＱｏＳ制御を可能としている。
【００３５】
上記は、入力可変長パケットを一旦固定長パケットに分割して行っているが、スケジューラ部において、可変長パケットの連続性を崩さない選択を行うことにより、実質的に可変長パケットのままでスイッチング処理を行なうようにしても良い。
図６は、入力バッファ部１２において、1 ＱｏＳクラス内に帯域保証が必要な最低保証レート分と帯域保証が不要だがトラヒック量が予測できないベストエフォート分を合わせ持つ、最低帯域保証クラスを収容する手法の一例を示す。最低帯域保証クラスを収容する際、最低帯域保証クラスのパケットもベストエフォートクラスのキュー１７にバッファリングする。但し、キューの前段のポリシング制御部２６において、最低帯域保証クラスに対して、最低保証レートを超えて入力されるパケットに対してはタギングを行っておき、タギングなしのパケットの廃棄閾値θ3 に対して、タギングありのパケットとベストエフォートクラスのパケットに対する、使用可能なキューのしきい値θ2 を低く設定する。
【００３６】
これにより最低帯域保証クラスを含む場合についても２クラスにマッピングすることが可能になる。この際、最低帯域保証クラスの最低保証レート内で入力されるパケットの廃棄閾値θ3 を帯域保証クラスのパケットの廃棄閾値θ1 と等しく設定して、帯域保証クラスと同等の品質保証を可能としても良い。また最低帯域保証クラスの最低保証レートを超えて入力されるパケットについては、同じベストエフォートクラスにマッピングされる。
【００３７】
図７にフローチャートを示す。入力バッファ部において、到着パケットが最低帯域保証クラスのときに、ベストエフォートクラスとしてキューイングしておき、その際図７のようにタギング情報に基づいた廃棄制御を行うことにより、扱うクラス数を増やさずに帯域保証クラスの品質保持を可能としている。
図８および９に出力バッファ部１８の構成の２つの例を示す。出力バッファ部１８には複数の入力回線からのパケットが混在した状態で到着する。この混在した状態をパケットインタリーブまたは単にインタリーブという。従って、出力バッファ部１８でこのインタリーブされた複数の固定長パケットを組立て、元の可変長パケットに戻してから、出力回線よりパケットを送出する必要がある。さらにＱｏＳ保証するためには、予め設定されたレートや優先度に応じた順序でパケットが送出されなければならない。
【００３８】
図８の例では、出力バッファ部にインタリーブして到着した固定長パケットを可変長パケット組立てバッファ２８に一旦バッファリングし、元の可変長パケットに戻す。この際インタリーブして到着したパケットは、複数の入力回線のものからのものが混在しており、さらに同一入力回線内でも入力回線側でＱｏＳクラス制御をした場合には、複数のクラスからのパケットが混在する。前述の例ではこのＱｏＳクラス数は２クラスとなる。従って、入力回線数（Ｎ）×入力回線側のＱｏＳクラス数（ｅｘ．２）個のキューを用意し、インタリーブして到着した固定長パケットを一旦バッファリングし、元の可変長パケットを組立てる。
【００３９】
可変長パケットが組立て終わったら、ＱｏＳクラス（ｅｘ．４クラス）に応じて、可変長ベースＱｏＳ制御部３０に転送し、可変長ベースＱｏＳ制御部３０において、パケット長を考慮したＱｏＳ制御を行うことにより、予め設定されたレートや優先度に応じた順序でパケットを出力回線より転送する。
図９の例では、出力バッファ部にインタリーブして到着した固定長パケットのままで、固定長ベースＱｏＳ制御部３２においてバッファリングし、予め設定されたレートや優先度に応じた順序でパケットを後段の可変長パケット組立て部に転送する。この場合のＱｏＳ制御はパケット長が固定であるので容易である。
【００４０】
後段の可変長パケット組立てバッファ３４には入力回線毎および、出側でのＱｏＳクラス毎にパケットがインタリーブされた状態で到着するので、入力回線数（Ｎ）×出側のＱｏＳクラス数（ｅｘ．４）個のキューを用意し、インタリーブして到着した固定長パケットを一旦バッファリングし、元の可変長パケットを組立て、パケットが組みあがった順番に出力回線より可変長パケットを転送する。
【００４１】
図１０は図８をより詳しくした図である。可変長パケット組立てバッファ２８に到着するパケットは、異なる入力回線、異なる縮退ＱｏＳクラスのものがインタリーブして到着するので、可変長パケット組立てバッファ２８では、入力回線毎、縮退ＱｏＳクラス毎にキューイングする。可変長パケット管理部３６では、各パケットに付与された可変長パケットの先頭、末尾の情報より１可変長パケット分のパケットを監視し、１可変長パケット分が組みあがったら、可変長パケット送信通知をだし、１可変長パケット分連続的に後段へ転送する。この際、実際のパケット内の情報を転送するのではなく、バッファに書きこまれたアドレス、およびアドレスチェーン情報のみをコピーしてもよい。さらに後段のＱｏＳ制御部３０では、ＱｏＳクラス数分のバッファを用意しておき、到着パケットをＱｏＳクラス（ｅｘ．４クラス）毎にキューイングする。ＱｏＳスケジューリング部３８では、キューへ書きこまれた、パケットのＱｏＳクラスやフレーム長を監視し、パケット長や予め設定されたレートやウェイト、優先度に応じて読み出し順序の競合制御を行い、読み出し可能となったＱｏＳクラスに対して出力回線への送出を指示する。
【００４２】
図１１は出力回線がさらに複数の低速回線へＤＭＵＸ（分離）される場合を示す。可変長パケット組立てバッファ２８の処理は同じであるが、ＱｏＳ制御部３０において、ＱｏＳクラス毎のキューを論理出方路（ＤＭＵＸ）分保持しており、ＱｏＳスケジューリング部３８において、各ＤＭＵＸ中の各ＱｏＳクラスキューからの読み出しがＤＭＵＸの帯域を超えないように制御する。ここで、各ＤＭＵＸへのタイムスロットを割り当て、タイムスロットに対応するＤＭＵＸキュー内の各ＱｏＳクラスについてＱｏＳスケジューリングを行う。
【００４３】
図１２では図９の構成において、図１１と同様に複数の低速回線へＤＭＵＸ（分離）されるとともに、ＱｏＳ制御部と可変長パケット組立てバッファの論理的な配備位置が逆になっている。このため、ＱｏＳ制御部３２では、ＱｏＳクラス毎、ＤＭＵＸ毎にキューイングし、固定長パケットのまま各ＤＭＵＸ中の各ＱｏＳクラスキューからの読み出しがＤＭＵＸの帯域を超えないように行なわれてＱｏＳスケジューリングを行う。また可変長パケット組立て部３４には、入力回線毎、ＱｏＳクラス毎、ＤＭＵＸ毎にキューイングしておき、１可変長パケット分組みあがった時点で出力回線へ１可変長パケット分連続的に出力する。
【００４４】
出力バッファ部１８での処理を考慮すると、スイッチ部１６の各出力回線から出力される固定長パケットの並びが、複数の入力回線からのパケットが混在した状態であるとしても、同じ可変長パケットから生じた固定長パケットができるだけ連続するように入力側でスケジューリングすることが望ましい。図１３は、この点を考慮した回線間スケジューラ１４の構成を示す。スケジューラ部の可変長パケット管理部４０は、各論理出方路毎の可変長パケット送出状態を管理するものであり、可変長パケットを構成する最初の固定長パケットを送出したときフラグをセットし、最終パケットを送出したときクリアすることにより、可変長パケット送出状態を識別する。また、未確定管理部４２は、他の入力回線によって読み出しが確定している回線を管理するもの、要求管理部４４は、入力バッファ部からの読み出し要求数を管理するもの、スケジューリング処理部４６は、要求情報、未確定情報、可変長パケット送出状態をもとに送出論理出方路を決定するものである。
【００４５】
スケジューリング処理部４６は、各論理出力回線毎に、現在可変長パケットを構成する固定長パケットを送出中であるかを判定し、スケジューリングの際に送出中の論理出力回線を優先的に選択する。これにより、１つの可変長パケットを構成する固定長パケットがまとめて読み出されやすくなるため、出力側の可変長パケットバッファでの待ち合わせ時間を低減することが可能となり、出力側の可変長パケット組み立てバッファ量を削減することができる。
【００４６】
以下にスケジューリング動作の具体的な例を図１４および図１５を参照して説明する。ここでは、簡略化のため３×３スイッチを例にとり動作を説明する。各入力回線は、論理的に出力方路毎に分割された論理キュー（以下、ＶＯＱ：Virtual Output Queueと記す）４７を有している。また、可変長パケット送出状態を示す可変長パケット状態レジスタ４８を各ＶＯＱ毎に備える。各ＶＯＱはさらに複数のＱｏＳクラスごとに分割されているがここでは図示が省略されている。
【００４７】
上記可変長パケット状態レジスタ４８は、可変長パケット送出中のＶＯＱを識別するためのレジスタであり、バッファからパケットを読み出したとき、そのパケットのパケット種別を識別し、可変長パケットエンドパケットで無いとき、“１”にセットされ、可変長パケットエンドパケットのときにリセットされる。スケジューラでは、本レジスタが“１”に設定されている状態を可変長パケット送出状態として扱う。読み出したパケットが可変長パケットエンドパケットであるか否かは、パケットヘッダのパケット識別ビットを参照することにより判定可能である。
【００４８】
スケジューリング処理部４６は、上記可変長パケット状態レジスタ４８を参照して、各入力回線について以下の２つのＳＴＥＰに沿って読み出しＶＯＱを決定する。
ＳＴＥＰ１：可変長パケット送出中のＶＯＱのみをスケジューリング対象としてスケジューリング処理を実施。
【００４９】
ＳＴＥＰ２：ＳＴＥＰ１において読み出しＶＯＱが確定しなかった場合に限り、可変長パケット未送出状態のＶＯＱを対象としてスケジューリングを実施。
まず、初期状態として図１４（左側）に示すようなパケットが蓄積されており、スケジューリング順序として、入力回線＃０から順に入力回線＃１→＃２の順でスケジューリングが実行されるとする。スケジューリングの開始入力回線（図中●印）は、スケジューリング周期毎に所定の規則に従って更新される。
(1) Ｔ＝０におけるスケジューリング動作
入力回線＃０では全てのＶＯＱが可変長パケット未送出状態であるため、上記ＳＴＥＰ１ではどのＶＯＱも確定されない。従って、ＳＴＥＰ２として可変長パケット未送出回線（この例では全てのＶＯＱ）の中からラウンドロビン方式により読み出しＶＯＱを決定する。ここでは、ＶＯＱ＃０が選択されたとする。（図中、読み出しＶＯＱを★印で示す）入力回線＃１でも同様の手順でスケジューリングが実行されるが、既に入力回線＃０によってＶＯＱ＃０が選択されているため、Ｔ＝０ではどのＶＯＱも選択することが出来ない。入力回線＃２では、ＶＯＱ＃１が選択されたとする。
(2) Ｔ＝０における可変長パケット状態レジスタ更新
スケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別に応じて可変長パケット状態レジスタを更新する。
【００５０】
Ｔ＝０では、入力回線＃０−ＶＯＱ＃０と、入力回線＃２−ＶＯＱ＃１からパケットが読み出される。これら読み出しパケットはいずれも、可変長パケットエンドパケットでないため、可変長パケット状態レジスタを“１”に設定する。（図１４の右側参照）これにより、次回のスケジューリング周期では、入力回線＃０−ＶＯＱ＃０と、入力回線＃２−ＶＯＱ＃１は、可変長パケット送出中ＶＯＱとして扱われ、優先的にスケジューリングされるようになる。
【００５１】
次に図１５を参照してＴ＝１におけるスケジューリング動作を示す。Ｔ＝１では、開始入力回線が更新され、入力回線＃１→＃２→＃０の順でスケジューリングが実行される。
(3) Ｔ＝１におけるスケジューリング処理
入力回線＃１では、全ての可変長パケット状態レジスタ４８が“０”であるため、可変長パケット未送出ＶＯＱの中から選択を行いＶＯＱ＃０を読み出しＶＯＱとする。
【００５２】
入力回線＃２では、可変長パケット送出中のＶＯＱがあるため、そのＶＯＱを優先的に選択する。この例では、可変長パケット送出ＶＯＱはＶＯＱ＃１しかないため、ＶＯＱ＃１を読み出しＶＯＱとする。複数のＶＯＱが存在する場合は、ラウンドロビン方式で選択する。
次に入力回線＃０でも、可変長パケット送出中のＶＯＱがあるため、同様に優先的に可変長パケット送出中のＶＯＱの中から読み出しＶＯＱを決定しようとするが、既にＶＯＱ＃０は入力回線＃１によって選択されているため、選択することが出来ない。従って、可変長パケット未送出回線の中から読み出しＶＯＱを決定する。この例では、ＶＯＱ＃１とＶＯＱ＃２が可変長パケット未送出であり、ラウンドロビンによりＶＯＱ＃１を選択する。このように、可変長パケット送出中のＶＯＱがある場合でも、他の入力回線によって選択されている場合で、可変長パケット送出中のＶＯＱが選択できない場合には、可変長パケット未送出ＶＯＱを選択する。
(4) Ｔ＝１における可変長パケット状態レジスタ更新
スケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別に応じて可変長パケット状態レジスタを更新する。
【００５３】
Ｔ＝１では、入力回線＃０−ＶＯＱ＃１、入力回線＃１−ＶＯＱ＃０および入力回線＃２−ＶＯＱ＃１からパケットが読み出される。
入力回線＃０−ＶＯＱ＃１、入力回線＃１−ＶＯＱ＃０から読み出されたパケットは共に可変長パケットエンドパケットで無いため可変長パケット送出レジスタを“１”に設定する。これにより、これらのＶＯＱは次のスケジューリング周期では、可変長パケット送出中ＶＯＱとして扱われ、優先的にスケジューリングされる。
【００５４】
一方、入力回線＃２−ＶＯＱ＃１から読み出されたパケットは、可変長パケットエンドパケットであるため、可変長パケット状態レジスタを“０”にクリアする。従って、本ＶＯＱは次のスケジューリング周期では、可変長パケット未送出ＶＯＱとして扱われる。
このように、可能な限り可変長パケット送出中のＶＯＱを優先的にスケジューリングすることにより、１つの入力回線から送出されるパケットは、ＶＯＱ毎に連続して読み出されやすくなるため、出力側の可変長パケット待ち合わせ時間を短くすることが可能となる。
【００５５】
図１６にこのスケジューリング処理のフローを示す。本フローは、１つの入力回線におけるスケジューリング処理フローである。
ステップ１００１〜１００４はスケジューリングプロセスである。まず、ステップ１００１において、優先的に可変長パケット送出中のＶＯＱについてスケジューリングを行う。ここで、未確定とは、他の入力回線によって選択されていないＶＯＱを意味し、要求ありとは、バッファにパケットが蓄積されていることを意味し、可変長パケット送出中とは、可変長パケット状態レジスタに“１”が設定されていることを意味する。次にステップ１００２において、上記ステップ１００１の処理によって、読み出しＶＯＱが確定したかを判定し、確定した場合には、可変長パケット状態レジスタの更新プロセスへ、未確定の場合には、可変長パケット未送出ＶＯＱのスケジューリングプロセスに移る。
【００５６】
ステップ１００３は、ステップ１００１において、ＶＯＱが確定されなかった場合にのみ実行され、可変長パケット未送出（可変長パケット状態レジスタ＝０）のＶＯＱについてスケジューリングを行う。ステップ１００４は、上記ステップ１００３において、読み出しＶＯＱが確定したかを判定するプロセスであり、未確定の場合にはスケジューリング処理を終了し、確定時は可変長パケット状態レジスタ更新プロセスに移る。
【００５７】
ステップ１００５〜１００７は、可変長パケット状態レジスタの更新プロセスである。ステップ１００１／１００３のスケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別を判定し、可変長パケットエンドパケットで無いときには、可変長パケット状態レジスタを“１”に設定し、可変長パケットエンドパケットのときに同レジスタをクリアする。
【００５８】
図８，１０，１１の可変長ベースＱｏＳ制御部３０ではパケット長を考慮したＱｏＳ制御が必要になる。図１７は、このパケット長を考慮したＱｏＳ制御を実現する手法の一例を概念的に示す。図８の可変長ベースＱｏＳ制御部３０において、各ＱｏＳクラス毎にバッファリングされた先頭のパケットのパケット長に対応するカウンタ値（ここではトークンと呼ぶことにする）を設定する。この際トークン値は、例えば、各ＱｏＳクラスに対するウェイト値（Φi ）として式（５）のような正規化した値を使用すれば、パケット長をそのまま使用できる。
【００５９】
Φi ＝Ｒ×τ×Φis／ΣΦis …（５）
ここでＲは全体の目標リンクレート、τは内部処理の単位時間（ｅｘ．固定長パケット時間）、Φisは各ＱｏＳクラスに割り当てられたウェイト値、ΣΦisはアクティブなＱｏＳクラスに対するΦisの総和である。また添え字のｉは、ＱｏＳクラスに付された番号に対応している。なお、式（５）中のＲ×τ／ΣΦisの値は一定であるので、（５）式から計算されるΦi の代わりに各ＱｏＳクラスのウェイト値Φisを使うことができる。
【００６０】
図１７に示すように、各ＱｏＳクラスの先頭パケットに対応するトークン値（Ｔi ）を単位時間（τ）毎、Φi ／ΣΦi ずつ減算していき、回線にパケットが読出し可能なとき、各トークン値の中で最小値（ベストエフォートクラスのパケットのとき）または０（レートが規定される帯域保証クラスのパケットのとき）のトークン値を持つＱｏＳクラスのパケットを読み出す。
【００６１】
この手法では、ＷＦＱのようにウェイト値に応じて各ＱｏＳクラスの帯域をアクティブなＱｏＳクラスで比例分配することが可能である。またＷＦＱようにキューイングされている全パケットについて、終了予定時刻Ｆ（ｉ，ｋ）を保持しなくて良いため、ハード規模が削減できる。さらに、実時間でスケジューリングするための、読出しレートを規定する帯域保証型のＱｏＳスケジューリングとの間の優先度制御が可能である。また、ΣΦi をアクティブなキューの数によらず一定とすることにより、そのまま、読出しレートを規定する帯域保証型のＱｏＳスケジューラとして使用できるため、回路を共通化してハード規模の削減や設計工数の削減が図れる。また、トークンを加算する処理とトークンから減算値を減算する処理と各ＱｏＳクラスのトークンを比較し、最も小さいまたは０のトークンを持つＱｏＳクラスのキューを選択して読み出す処理は、パイプライン化することも可能であり、高速なＱｏＳ制御を行うことも可能である。
【００６２】
図１８に実際のハードウェア構成の例、図１９にフローチャートを示す。図示した例は、可変長ベースＱｏＳ制御部において、可変長パケット組立てバッファ部とＱｏＳ制御部でパケットバッファは共通でバッファへの書きこみアドレスのみを転送する場合の構成に対応している。出力回線部に入力された固定長パケットは、パケットバッファ５０へ書きこまれるとともに、アドレス管理ＦＩＦＯ５２において、入力回線毎、縮退ＱｏＳ毎にアドレスのＦＩＦＯチェーンを構成する。可変長パケット組立て部５４では、各キューへの１可変長パケット分の到着を管理し、１可変長パケット分到着した可変長パケットについて、対応するパケットバッファのアドレスをコピーし、ＱｏＳクラス毎、ＤＭＵＸ毎のアドレスＦＩＦＯを構成する。さらに、ヘッダ情報をパケット識別部５６に転送する。パケット識別部５６ではパケットヘッダからＱｏＳクラス、ＤＭＵＸ番号やパケット長といったＱｏＳスケジューリングに必要な情報を抽出し、後で詳述する図１９の処理フローに従い、読み出しＱｏＳクラスの選択を行い、ＤＭＵＸ読み出し部５８より対応するパケットをパケットバッファから出力パケットハイウェイへ読み出す。このときＤＭＵＸ読み出し部５８では、各ＤＭＵＸ毎の固定的なタイムスロットを管理しておき、各タイムスロットのタイミングにおいてスケジューリングすべきＤＭＵＸの番号を通知し、対応するＤＭＵＸについて図１９の処理フローを実行する。
【００６３】
図１９の処理フローでは、３つのプロセスが連携して動作する。パケット到着処理プロセスでは、可変長パケットが到着したとき、または前述のアドレス管理ＦＩＦＯ５２において、可変長パケットがＦＩＦＯの先頭に来たとき、対応する可変長パケットのＱｏＳクラスごとにトークン値の加算（ステップ１１００）、および、ウェイト値総和ΣΦi への加算を行う（ステップ１１０２）。またパケット読み出しプロセスでは、前可変長パケットの読み出しが終了し、次の可変長パケットを選択する前、もしくは初期状態において、可変長パケットの選択が行われていないとき、各ＱｏＳ毎のトークン値（ｉ）を比較し、最小トークン値を持つＱｏＳクラスを選択し（ステップ１１０４）、当該ＱｏＳクラスのパケットの読み出しを開始する（ステップ１１０６）。このとき、同一ＱｏＳクラスにキューイングされている他のパケットが無く、キューが空になるときは、ΣΦi からの減算処理を行う（ステップ１１０８）。一方、減算値処理プロセスでは、単位時間毎に、全ＱｏＳクラスの減算値を計算し（ステップ１１１０）、全ＱｏＳクラスのトークン値から減算値の減算を行う（ステップ１１１２）。
【００６４】
図２０は、パケット長を考慮したＱｏＳ制御の第２の例を概念的に示す図である。トークン値（Ｔi ）をトークン値×ΣΦi に置き換え、さらに単位時間毎の減算値としてΦi を使用する。
この手法では、一般に処理時間がかかるΦi ／ΣΦi の除算処理をなくすことができる。但し、ＱｏＳクラスキューの状態を反映するΣΦi の更新が、前述の手法では１単位時間毎に可能であるのに対して、パケットの先頭を読出してトークン値を積みあげるときのみになるため、多少公平性に関して特性的な劣化が生じる。
【００６５】
図２１にフローチャートを示す。パケット到着処理プロセスにおけるトークン値の加算値にパケット長の代わりにパケット長×ΣΦi を用い、また減算値処理プロセスにおいて、減算値をΦi ／ΣΦi の代わりにΦi としている。
図２２は、パケット長を考慮したＱｏＳ制御の第３の例を示す。この手法では、トークン値をトークン値×ΣΦi に置き換える代わりに、ΣΦi の加算をパケット長に相当する回数だけ繰返すことに置き換えている。
【００６６】
トークン回数を管理するカウンタが必要となるため多少複雑になるが、乗算処理をなくすことができるためハード量の削減が図れる。またパケット長に相当する回数分のΣΦi の加算の際に、逐次最新のΣΦi を使用することにより、ＱｏＳクラスキューの状態を反映する頻度が多くなり、公平性に関して特性的な向上が図れる。
【００６７】
図２３にフローチャートを示す。パケット到着処理プロセスにおけるトークン値の加算値にパケット長の代わりにΣΦi を用い、累積パケット長カウンタによって、加算したΣΦi の回数を管理する。また減算値処理プロセスにおいて、累積パケット長カウンタが０になるまで、トークン値のフレームへの加算処理を繰返し、減算値をΦi ／ΣΦi の代わりにΦi としている。
【００６８】
図２４は、最低帯域が保証されさらに余剰帯域の使用が許される最低帯域保証クラスの可変長パケットについてのパケット長を考慮した制御が可能なＱｏＳ制御の一例を概念的に示す。入力された最低帯域保証クラスの可変長パケットについては通常はスイッチ部１４の前段に設けられるポリシング制御部２０において、最低保証帯域を超えて到着したパケットにタギングを行うことにより、帯域保証のパケットとベストエフォート分のパケットが識別される。スイッチ部１４の後段のＱｏＳ制御部５８では到着した可変長パケットを構成する固定長パケットの数をＱｏＳクラス（ｅｘ１６クラス）別にカウンタする。すべてのＱｏＳクラスのそれぞれについて帯域保証クラス用のカウンタとベストエフォートクラス用のカウンタを用意し、最低帯域保証クラスについてはそれらの双方を使用し、ベストエフォートクラスについてはベストエフォートクラスのカウンタのみを使用し、帯域保証クラスについては帯域保証クラスのカウンタのみを使用するようにすることが好ましい。この様にすることにより、システムの柔軟性が向上する。
【００６９】
ここでＱｏＳ制御部５８では、カウンタ値が正の値のものについて、前述した重み付けによる読出し制御を行う。トークン演算のアルゴリズムは前述の３通りのいずれでも良い。但し、この際、可変長パケットのパケット長の代わりに固定長パケットのパケット長を用い、また帯域保証クラスについては設定レートに従う読出しを行う。また帯域保証クラスとベストエフォートクラスからの要求の競合時は単純に帯域保証クラスを高くするかラウンドロビンや予め設定された優先度に応じて読み出す。このようなスケジューリング処理は固定長パケット毎に行い、選択されたＱｏＳクラスのカウンタ値を１減算するとともに、可変長バッファ部６０へ選択されたＱｏＳクラスを通知する。
【００７０】
可変長バッファ部６０では、通知数をＱｏＳクラス毎に計数し、累積数が各キューの先頭のパケット長に達したら、１可変長パケットの読み出しを行なう。
上記の制御により、１ＱｏＳクラス内に帯域保証分とベストエフォート分が含まれる最低帯域保証クラスに対して可変長パケットに対するＱｏＳ制御が可能となる。図６，７を参照して説明した制御のように同一キューにマッピングしてキューしきい値で制御する方法だとベストエフォート分のパケットが使用できるキュー領域は帯域保証クラスが利用できるキュー領域より小さくなるという制限が生じるが、このような問題が解消される。また、単純に１ＱｏＳクラスのキューを帯域保証分とベストエフォート分とで２つに分けると生じるパケットの順序逆転も起きない。
【００７１】
さらに、帯域保証クラスのスケジューリングとベストエフォートクラスのスケジューリングを別々に行うことができるので単純に帯域保証クラスの優先度を高くするような優先制御だけでなく、ラウンドロビンにしたり予め優先度を設定しておくなどより複雑な優先制御が可能となる。
図２５に具体的な構成を示す。ここでは、固定長パケット単位にパケットバッファへのキューイングを管理しているが、連続する固定長パケットを可変長パケットと置き換え、可変長パケットの先頭と末尾を管理し、１可変長パケット分連続的に読み出すことにより、可変長パケットにおいても全く同様に当てはまる。
【００７２】
ＱｏＳスケジューラ６２において、到着した可変長パケットを構成する固定長パケットの数がカウントされる。この際、最低帯域保証クラスについては、当該フレームがタギングされているか否かによって、適合パケット数カウンタにカウントするか、不適合パケット数カウンタにカウントするかに分かれる。前述のように帯域保証クラスおよびベストエフォートクラスについては一方のカウンタのみが使用される。ＱｏＳスケジューラ６２では各カウンタ値が０で無いものについて、予め設定されたレートやウェイト、優先度に応じて、１つのＱｏＳクラスを選択する。選択されたＱｏＳクラスは可変長パケット管理部６４に通知される。可変長パケット管理部６４では、通知された選択ＱｏＳクラス数を管理しており、累積数をパケット長に換算して、各ＱｏＳクラス毎のキューの先頭パケットのパケット長より大きくなった場合には、当該可変長パケットを出力ハイウェイから出力する。
【００７３】
このとき、固定長パケットサイズやフォーマットは、どのようなものでもよく、可変長パケットの先頭と末尾を管理できれば、ここでの固定長パケットにヘッダを付与する必要はない。
図２６は、最低保証帯域クラスの可変長パケットの制御が可能なＱｏＳ制御の他の例の原理を説明する図である。図２６は或るＱｏＳクラスに対するトークン値の動作を示している。ここで、入力された可変長パケットはＱｏＳクラスごとにキューイングされている。Φigは帯域保証クラス用に設定された読出しレート値である。またΦibはベストエフォートクラス用に設定されたウェイト値である。ベストエフォート分を含まない帯域保証クラスのΦibはゼロに、帯域保証分を含まないベストエフォートクラスのΦigはゼロに設定される。最低帯域保証クラスについては、ΦigとΦibにゼロでない値が設定される。
【００７４】
ここでは、１単位時間内にトークン減算処理を帯域保証クラスサイクル用とベストエフォートクラスサイクル用の２回行う。このとき、いずれのＱｏＳクラスにおいても帯域保証クラスのパケットの読み出しが無いときは、ベストエフォートクラスサイクル用のトークン減算処理も行うが、帯域保証クラスの可変長パケットの読み出しがあるときまたは帯域保証クラスの可変長パケットの読み出しが続いているときは、ベストエフォートクラスサイクル用のトークン減算処理を行わない。最低帯域保証クラスのパケットには予め前段のポリシング制御部において、最低保証帯域を超えたフレームにタギングをしておく。帯域保証クラスサイクル用のスケジューリングを行い読み出すべきフームの有無を判定する際、タギングのない最低保証帯域以下のパケットについてのみ読み出すべきパケットが有りとして処理し、タギングがある場合は読み出すべきパケットが無しとして処理する。
【００７５】
もしくは、帯域保証クラスの読み出しパケットの有り無しに関わらず、常にベストエフォートクラスサイクル用のトークン減算処理を行い、ΣΦibの代わりにΣΦiall（アクティブなコネクションについてのΦigとΦibの総和）を使用することもできる。
このようにすれば、可変長パケットの状態のままで、スケジューリングができ、帯域保証クラスのスケジューリングを行ってからベストエフォートクラスのスケジューリングを行うという簡単な制御で最低帯域保証クラスの収容が可能となる。但し、一般にΣΦigとΣΦibは異なる値であるため、前記の３通りのトークン演算アルゴリズムのうち、トークンとしてどちらのクラスにも共通であるパケット長を用いる第１番目の演算アルゴリズムのみが適用できる。
【００７６】
図２７に処理のフローチャートを示す。可変長パケット到着処理プロセスにおいて、帯域保証クラスとベストエフォートクラスで、ΣΦi を各々ΣΦigとΣΦibとして別々に管理する（ステップ１２００）。また同様に減算値更新プロセスにおいても減算値Φi ／ΣΦi の代わりにΦig／ΣΦigとΦib／ΣΦibを別々に管理し（ステップ１２０２）、トークンの減算処理を帯域保証クラスからパケットが読み出されているときと、そうでないときに分けて行う（ステップ１２０４）。また可変長パケット読み出しプロセスにおいて、先に帯域保証クラスのパケットまたはタギングのない最低帯域保証クラスのパケットがキューイングされているキューの中からの可変長パケットの選択を行い（ステップ１２０６）、次にベストエフォートクラスのパケットまたはタギングされている最低帯域保証クラスのパケットがキューイングされているキューの中からの可変長パケットの選択を行う（ステップ１２０８）。またΣΦの減算についても同様に帯域保証クラスとベストエフォートクラスで別々に行う（ステップ１２１０）。なお、図２７に示した例では、帯域保証クラスについては、Φibがゼロに設定され、ベストエフォートクラスについては、Φigがゼロに設定されるものとする。その代わりとして、減算値更新プロセスにおいて、帯域保証クラスについては、Φibの減算を行なわず、ベストエフォートクラスについては、Φigの減算を行なわないようにしても良い。
【００７７】
図２８は、最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御のさらに他の例の原理を説明する図である。図２８は図２６と同様に前述の第１番目の演算アルゴリズムを適用した場合の、或るＱｏＳクラスに対するトークン値の動作を示している。この例では、最低帯域保証クラスのパケットは、帯域保証クラス用とベストエフォートクラス用の２つのスケジューラにより並列に処理する。但し、トークン値はＱｏＳクラス毎のキューの先頭パケットのパケット長に対応する同一のトークン値を使用する。このとき、ベストエフォートクラス用のスケジューラでは、ΣΦibの代わりにΣΦiallを使用する。
【００７８】
最低帯域保証クラスについては、帯域保証クラス用とベストエフォートクラス用の２つのスケジューラによるスケジューリングが行なわれる。それらの読出し処理により、いずれか先に読出しが行われたときは、読出しが行われなかった方の読み出された可変長パケットに対して行われた累積トークン減算値を繰り越し分として、次の可変長パケットのトークン値を計算する際に減算する。
【００７９】
この手法では、帯域保証クラス用とベストエフォートクラス用で別々にトークンの減算処理が必要となるため、ハード規模が増加する。但し、帯域保証クラス用とベストエフォートクラス用を並列に処理できるので、高速なスケジューリングが可能となる。また、ΣΦigとΣΦiallが一致する必要がないので、前述した３つの演算アルゴリズムのいずれもが適用可能である。
【００８０】
図２９にフローチャートを示す。この例では、フレーム到着処理プロセスにおいて、１つのＱｏＳクラスｉについてトークン値を帯域保証クラスとベストエフォートクラスでトークン値（ｉｇ）、トークン値（ｉｂ）として別々に管理する（ステップ１３００）。さらに、減算値更新プロセスにおいて、トークン値（ｉｇ）とトークン値（ｉｂ）からそれぞれΦ(ig)／ΣΦ(ig)とΦ(ib)／ΣΦ(isll)を減算するときに、減算量をそれぞれ繰越分（ｉｇ）と繰越分（ｉｂ）として記憶しておく（ステップ１３０２）。読み出しパケットの選択の際には、可変長パケット読出プロセスにおいて、まず、可変長パケットが存在するすべてのＱｏＳクラスの中からトークン値（ｉｇ）がゼロになっているクラスを選択する（ステップ１３０４）。このとき、帯域保証分を持たないベストエフォートクラスについては、Φigをゼロに設定すれば、ステップ１３０２におけるトークン値（ｉｇ）の減算が実質的に行なわれないので、ここで選択されることはない。次に、可変長パケットが存在するすべてのＱｏＳクラスの中からトークン値（ｉｂ）が最小であるものを選択する（ステップ１３０６）。このとき同様に、ベストエフォート分を持たない帯域保証クラスについては、Φibをゼロに設定すれば、ステップ１３０２におけるトークン値（ｉｂ）の減算が実質的に行なわれないので、ここで選択されることはない。帯域保証分とベストエフォート分を併せ持つ最低帯域保証クラスについては、両者のいずれかとして選択され、選択されなかった方の繰越分を次のパケットの選択に反映させるため、選択されなかった方のトークン値に−（繰越分）を設定する（ステップ１３０８）。
【００８１】
次に、本発明の一実施形態に係るパケット廃棄の手法を説明する。なお、以下の記述において、「可変長パケット」は「フレーム」と、「固定長パケット」は単に「パケット」と称される。本発明において、廃棄はランダムでなく周期的に行い、その周期をキュー長の状態に応じて変えることにより、確率的な廃棄を実現する。また、廃棄を読み出し時に行うことにより、キューの先頭から廃棄することが出来るため、廃棄を早く端末に通知することが出来る。廃棄判定はキューの先頭パケット読み出し時に行う。図３０および式（６）に示すように、キュー長に応じた廃棄確率を決定し、式（７）で決定される周期で廃棄を行う。これにより、長いフレームはそれだけ高い確率で廃棄することが出来る。廃棄時は、１フレーム分のパケットを１パケット時間に廃棄することにより、スループットの低下を防ぐことが出来る。
【００８２】
廃棄確率＝（平均キュー長−ＴＨmin ）／（ＴＨv −ＴＨmin ） …（６）
廃棄周期＝１／（廃棄確率×パケット長） …（７）
具体的な回路構成を図３１に、動作フローを図３２に、動作の一例を図３３に示す。バッファ内のキュー長を管理するキュー長カウンタ６６、設定されたしきい値を保持するしきい値レジスタ６８、設定された読み出し間隔パラメータを保持する読み出し間隔レジスタ７０、読み出し間隔制御に用いるＬＢカウンタ７２、バッファの先頭のフレームのフレーム長を管理するフレーム長カウンタ７４、ＬＢカウンタ動作を制御するカウンタ制御７６、その他演算器より構成される。
【００８３】
フレームの先頭のパケットを読み出す時、平均キュー長としきい値を比較する。平均キュー長がしきい値を越えていない場合はそのまま読み出しを行う。しきい値を越えた場合、しきい値と平均キュー長との差分にフレーム長を掛け合わせた値を、ＬＢカウンタ７２に加算する。そして加算結果が０を越えていた場合、該当フレームに属するパケットを全て廃棄し（具体的な方法は後述）、ＬＢカウンタ値から、読み出し間隔レジスタ７０の値にフレーム長を掛け合わせた値を減算する。加算結果が０を越えていない場合は、そのまま読み出しを行う。ＬＢカウンタに加算する値が大きいほど、カウンタ値が０を越える確率が高くなる。よって本動作により、輻輳度合いとフレーム長に応じた確率でフレームを廃棄することが出来る。
【００８４】
ここで、平均キュー長はその時点での値を用いることも、移動平均を取った値を用いることも可能である。一時的な輻輳ではなく、長期的な輻輳時のみ廃棄制御をかけるため、移動平均を取った値を用いることが有効であるが、バッファを大きく取ることができれば、しきい値を大きく設定し実キュー長がしきい値越えとなった時点で長期輻輳と判断することも可能である。また、読み出し時に廃棄することで、バッファの先頭のフレームに対し廃棄することが出来る。
【００８５】
図３４および図３５に１フレームに属するすべてのパケットの廃棄を１パケット時間内に行なう手法の一例を示す。図の左上に概念的に表されるアドレス管理ＦＩＦＯは、実際には各キューのスタート／エンドポインタ９２とアドレス管理テーブル９４により構成される。アドレス管理テーブル９４には、次のアドレスを示す次アドレス、フレーム最終パケットのアドレスを示すＥＮＤアドレス、キューに次のフレームが存在することを示す次先頭アドレスイネーブル、次のフレームの先頭アドレスを示す次先頭アドレス、フレームの先頭を示すフレーム先頭フラグ、フレーム長のフィールドを有するレコードが格納される。
【００８６】
図３４において、廃棄するフレームを空きアドレスキューにつなぎ替えるため、空きアドレスキューのエンドポインタによって示される最終アドレス（アドレス９）のレコードの次アドレスの値をつなぎ替えるフレームの先頭アドレス（アドレス５）に書き替える（ステップＡ）。そして空きアドレスキューのエンドポインタをつなぎ替えるフレームのＥＮＤアドレス値（アドレス１）に書き替える（ステップＢ）。次に廃棄が行われたキューから廃棄フレームを取り除くため、キューのスタートポインタを次先頭アドレス（アドレス１３）に書き替える（ステップＣ）。以上のようにアドレスリンクを書き替えることにより図３５に示すようになり、１パケット時間内に１フレーム分の廃棄を行うことが出来る。
【００８７】
パケット廃棄方式の他の例として、基本的な考えは前述と同じであるが、廃棄判定は各パケット読み出し毎に行い、廃棄確率は、平均キュー長がしきい値を越えた量のみに比例させ、それに見合った周期で廃棄を行う。パケット毎に廃棄判定を行うため、結果的に長いフレームはそれだけ高い確率で廃棄することが出来る。１パケット廃棄したら同一フレームに属する以降のパケットの読み出し毎に廃棄する。廃棄に廃棄パケット数分の時間掛かるため特性的に前述の手法に劣るが、逆にパケットｂｙパケットの動作のため回路構成が簡単になるため、より高速動作が必要なバッファ制御に適する。
【００８８】
以上の廃棄方式はキュー毎に制御される。また、複数のしきい値を持たせることにより廃棄に対するプライオリティを持たせることが出来る。
このパケット廃棄方式の具体的な構成の例を、図３６に示す。キュー長を管理するキュー長カウンタ７８、設定されたしきい値を保持するしきい値レジスタ８０、設定された読み出し間隔パラメータを保持する読み出し間隔レジスタ８２、読み出し間隔制御に用いるＬＢカウンタ８４、フレーム廃棄中であることを示す廃棄フラグ８６、ＬＢカウンタを制御するカウンタ制御部８８、その他演算器より構成される。各パケットの読み出し時、平均キュー長としきい値を比較する。平均キュー長がしきい値を越えていない場合はそのまま読み出しを行う。しきい値を越えた場合、しきい値とキュー長との差分を、ＬＢカウンタに加算する。そして加算結果が０を越えていた場合、該当パケットを廃棄、廃棄ＬＢカウンタ値から読み出し間隔レジスタ値を減算し、廃棄フラグを立てる。加算結果が０を越えていない場合は、そのまま読み出しを行う。パケット廃棄を行った場合、同一フレームの以降のパケット読み出し時に廃棄を行い、ＬＢカウンタ値に対し、ＬＢしきい値とキュー長との差分値の加算と、カウンタ値から読み出し間隔レジスタ値を減算する。同一フレームの最終になったら、フラグをクリアする。（先頭フレーム到着時、廃棄フラグをクリアしてから廃棄判定をしても良い。）最終パケットは廃棄しないことで、廃棄フレームと次のフレームとを識別させることが出来る。パケット毎に廃棄判定を行うため、廃棄確率はフレームが長いほど高くなる。よって本動作により、輻輳度合いとフレーム長に応じた確率でフレームを廃棄することが出来る。以上の動作フローを図３７に、ＬＢカウンタ動作例を図３８に示す。ここで、平均キュー長はその時点での値を用いることも、移動平均を取った値を用いることも可能である。一時的な輻輳ではなく、長期的な輻輳時のみ廃棄制御をかけるため、移動平均を取った値を用いることが有効であるが、バッファが大きく取れれば、しきい値を大きく設定し実キュー長がしきい値越えとなった時点で長期輻輳と判断することも可能である。また、読み出し時に廃棄することで、バッファの先頭のフレームに対し廃棄することが出来る。パケットの廃棄に１フレーム時間かかるため、前述の方式より特性的には劣化するが、回路構成が簡単になるため、より高速な動作が必要なところに適する。
【００８９】
ＬＢカウンタ制御については、正負を逆転したり、廃棄判定を０でなくしきい値を用いて行っても良い。
可変長パケットであるフレームをスイッチングするパケットスイッチにおいては、１つのフレームを複数の低速回線へマルチキャストする場合に次の様な解決すべき問題がある。図３９に示すように、スイッチ部１６からフレーム組立バッファ２８に１フレーム分のパケットが溜まった後にＤＭＵＸ９０にパケットが移し替えられるが、その移し替えを１パケットづつ行うと、マルチキャストを行う場合、図４０に示すように複数の低速回線に同時に複製するためにはマルチキャスト数分のアドレス更新を１パケット時間内に行う必要があり高速動作には適さない。また図４１に示すように、マルチキャスト用として別のキュー９１を設ける場合、フレーム連続性を保証するためにマルチキャストを行なわないパケットとマルチキャストの複製先が競合しないように制御する必要がある。更に、フレーム長に比例してマルチキャストに時間がかかる問題もある。
【００９０】
そこで、図４２に示すように、フレーム組立てバッファ２８からＤＭＵＸ９０への移動を１パケットずつでなく１フレーム分のパケットをまとめて移動するようにすれば、フレーム組立てバッファ２８での読み出し競合の問題は解消される。１フレーム分のパケットの移動は、以下に説明するように、パケットのデータを実際に移動するのでなく、パケットバッファ内の格納アドレスを移動するようにすれば、１パケット時間内で可能になる。
【００９１】
フレーム単位でのパケットの移動の具体例を図４３，４４を参照して説明する。図の左上に概念的に示されるアドレス管理ＦＩＦＯは、実際には、各キューのスタート／エンドポインタ９２とアドレス管理テーブル９４により構成される。アドレス管理テーブル９４には、次のアドレスを示す次アドレス、フレーム最終パケットのアドレスを示すＥＮＤアドレス、キューに次のフレームが存在することを示す次先頭アドレスイネーブル、次のフレームの先頭アドレスを示す次先頭アドレス、フレームの先頭を示すフレーム先頭フラグ、及びフレーム長のフィールドを有するレコードが格納される。
【００９２】
ここで、図４３において、１フレーム分のパケットがフレーム組立バッファに溜まった場合、まずフレームを出力バッファキューにつなぐために、出力バッファのエンドポインタが示す最終アドレス（アドレス２）のレコードの次アドレスの値を、フレームの先頭アドレス（アドレス５）に書き替える（ステップＡ）。そして出力バッファのエンドポインタを、つなぎ替えるフレームのＥＮＤアドレス値（アドレス１）に書き替える（ステップＢ）。次にフレーム組立キューを更新するために、フレーム組立キューのスタートポインタを次先頭アドレス（アドレス１３）に書き替える（ステップＣ）。以上により、図４４に示すようになり、１パケット時間内にフレーム組立バッファから出力バッファに移動することが出来る。
【００９３】
図４５に本発明におけるマルチキャストの処理を概念的に示す。マルチキャストすべきフレームはまずＤＭＵＸ９０を経てマルチキャストキュー９６に移動される。勿論、この移動もアドレスの書き替えのみによって行なわれる。マルチキャストキュー９６からＤＭＵＸ９０の各出力回線に複製する際、複製フレーム毎に１つのマルチキャストアドレス９８を付与する。そしてアドレスリンクにはマルチキャストアドレス９８をつなぎ変える。これにより、１フレーム分を１パケット時間で仮想的に複製できるため、ユニキャストパケットとの間でフレーム連続性が保証され競合制御が不要になる。同時に複製に掛かる時間が複製数×パケット時間のみで可能となる。
【００９４】
マルチキャスト処理の具体例を図４６〜図５３に示す。図４３，４４の構成に加え、出力バッファは更に複数の出力回線に対するキューを含むので、複数の出力回線へのキューとマルチキャストキュー９６のスタート／エンドアドレスポインタとコネクション管理テーブル１００を用意する。また、アドレス管理テーブル９４には、マルチキャスト識別ビット、マルチキャストコネクションを識別するＣＩＤ、マルチキャストキューからの再配置完了を示す振分完了フラグ、フレームのマルチキャスト出力数を管理するマルチキャスト数カウンタ、及びマルチキャストアドレスに対応するフレームのアドレスを示すフレームアドレスのフィールドが追加される。コネクション管理テーブルには、マルチキャストされるコネクションのＣＩＤが実際の出力回線の番号とともに格納される。図示されている例は、ＣＩＤの２と１がこの順で登録され、それらに対応する出力回線はそれぞれ１と４であることを示す。
【００９５】
マルチキャストフレームのフレーム組立が完了すると、出力バッファではなくマルチキャストキューに移動する（図４６）。出力回線別のキューに同一のアドレスを使用できないため、複製時に新たな空きアドレス（アドレス３，１１）を確保し、そのアドレスをフレームの代理として該当する出力バッファキュー（キュー１，４）につなぎ変える。同時にアドレス管理テーブルのマルチキャストアドレス（アドレス３，１１）に対し、フレームアドレスのフィールドに実際のフレームのスタートアドレス（アドレス５）を、そのアドレスのＥＮＤアドレスのフィールドにフレームのエンドアドレス（アドレス１）を保持する。また、フレームがコピーされる毎にそのアドレスのマルチキャストカウンタをインクリメントし、同一フレームの最終コピー時（コネクション管理テーブルのＥＮＤフラグで識別）に再配置完了フラグを立てる（図４７〜図４９）。
【００９６】
ＤＭＵＸからの読み出し時は、マルチキャストアドレス（アドレス３，１１）のフレームアドレス（アドレス５）からＥＮＤアドレス（アドレス１）までのパケットを読み出す。１フレーム分のパケット読み出し完了後、マルチキャストアドレスを空きアドレスキューに返却し、マルチキャストカウンタをデクリメントする。その結果が０で且つ再配置完了フラグが立っていれば、リンクとポインタの書き換えにより１フレーム分のアドレスを空きアドレスに返却する（図５０〜図５３）。ここで、第一回目のコピーではマルチキャストアドレスを用いずリンクとエンドポインタの書き換えにより再配置することで、制御が複雑になるものの使用アドレスを削減することも出来る。
【００９７】
図５４には、スイッチ１６の入力側および出力側のいずれにも適用可能なＱｏＳ制御の他の例を概念的に示す。
選択部２００は、所定の規則に従って高優先グループに属するＱｏＳクラスの中から１つを選択する。選択部２０２は、所定の規則に従って低優先グループに属するＱｏＳクラスの中から１つを選択する。選択部２０４は選択部２００が選択したＱｏＳクラスおよび選択部２０２が選択したＱｏＳのいずれか一方を選択する。
【００９８】
このＱｏＳ制御は、単純な優先度選択回路のみで実現でき、予め各ＱｏＳクラスにレートや読み出し比を設定して競合制御を行う場合に比べて、ハード規模の削減が可能となる。
このＱｏＳ制御はパケット廃棄などによる品質劣化が少ない入力側に適用可能であるが、品質劣化ポイントでなければ出力側にも適用可能である。
【００９９】
図５５は図５４のＱｏＳ制御を図１のスイッチ１６の入力側の入力バッファ部１２および回線間スケジューラ１４に適用した例を示す。図５５において、入力回線の各々について、入力バッファ部１２はＭ個のＶｏＱ毎にＱｏＳクラス毎のキューを保持している。スケジューリング部１４は全ＶｏＱ×ＱｏＳ個のキューについて、１単位時間には同じＶｏＱを選択しないように競合制御する。このとき、各スケジューリング部１４は、未確定管理部２０６において、確定していないＶｏＱ情報を交換することにより競合制御を実施する。
【０１００】
入力バッファ部１２のＶｏＱ毎のＱｏＳキューに固定長パケットが到着した際、スケジューリング部１４に対して、対応するＶｏＱ番号と当該パケットのＱｏＳクラスが属する優先グループを通知し、スケジューリング部１４の各要求数カウンタ２０８，２１０で要求数を管理する。この際、例えば、帯域保証クラスのパケットは高優先グループとして通知し、ベストエフォートクラスのパケットは低優先グループとして通知する。
【０１０１】
次に１つのスケジューリング部１４内の高優先グループの選択部２１２において、要求カウンタ数が０でないものの中から１つのＶｏＱを選択し、隣接するスケジューリング部１４へは未確定管理部２０６を経由して、確定していないＶｏＱを通知する。未確定ＶｏＱを受信したスケジューリング部１４は未確定ＶｏＱの中から同様の手順で１つのＶｏＱを選択し、順次この操作を繰り返し、全入力回線について高優先グループに対するスケジューリングが完了する。
【０１０２】
次に、高優先グループに対してＶｏＱが選択されなかった入力回線について、選択されなかったＶｏＱを対象として、各スケジューラ部１４の低優先グループ選択部２１４で高優先グループのときと同じ手順でＶｏＱが順次選択される。
以上の処理により全入力回線について、高優先グループまたは低優先グループに対応するユニークなＶｏＱ値が選択される。以上の機能が図５４の選択部２０４に対応する。
【０１０３】
次にスケジューラ部１４は決定したＶｏＱ値、および優先グループを入力バッファ部１２に通知し、入力バッファ部１２では図５６の処理を行い、高優先グループまたは低優先グループの中から１つのＱｏＳキューを選択する。またこのとき、１可変長パケットの連続性を維持するように選択を管理することにより、同一ＱｏＳクラス内のフレームの連続性が保証される。
【０１０４】
図５７は、図５４のＱｏＳ制御を図８のＱｏＳ制御部３０におけるＱｏＳ制御に適用した例を示す。入力バッファ部１２における制御との違いは、高優先グループか低優先グループかの選択を競合制御によって行うのではなく、高優先グループに対応するパケットの有無で判定している。すなわち、図５７のステップ２０００，２００２、および２００４の処理が図５４の選択部２０４，２００、および２０２にそれぞれ相当する。
【０１０５】
図５８は図５４のＱｏＳ制御において、各ＱｏＳクラスを高優先グループおよび低優先グループのいずれかへ割り当てる手法の一例を示す。
図５８に示した例では、帯域保証クラスのキューを高優先グループにマッピングし、ベストエフォートクラスのキューを低優先グループにマッピングする。最低レートまでは帯域保証し、最低レート以上は帯域の余剰がある場合のみ読み出し可能とする最低帯域保証クラスに関しては、高優先グループと低優先グループの両方にマッピングし、帯域保証分の読み出しを高優先グループとして、余剰帯域分の読み出しを低優先グループとして読み出すことにより最低帯域保証クラスのＱｏＳ制御を実現する。
【０１０６】
これにより、単純な優先度選択のみで最低帯域保証クラスの帯域保証分をベストエフォートクラスより優先度を高くし、帯域保証クラスと同等の優先度に設定し、最低帯域保証クラスの余剰帯域分を帯域保証クラスより優先度を低くし、ベストエフォートクラスと同等の優先度に設定できるため、帯域保証クラスやベストエフォートクラスに影響を与えずに最低帯域保証クラスを収容することが可能となる。
【０１０７】
図５９に図５８の手法をスイッチ１６の入力側のＱｏＳ制御に適用した場合の、入力バッファ部１２およびスケジューリング部１４の具体的な回路構成を示す。最低帯域保証クラスを高優先グループ、または低優先グループにマッピングするために、前段のポリシング制御部２２０において、到着するパケットのトラヒックを監視し、予め規定された最低保証レート以下のパケットに対してはタギングを行わず、最低保証レートより上のパケットについてはタギングを行う。
【０１０８】
そしてタギングなしのパケットが到着した際は高優先グループとしてスケジューリング部１４へ通知し、タギングありのパケットが到着した際はスケジューリング部１４へ低優先パケットとして通知する。この際、どちらのパケットも同一のＱｏＳキュー２２２に保持する。図示されていないが、帯域保証クラスおよびベストエフォートクラスのパケットの到着はポリシング制御部２０の処理を経ることなく、それぞれ高優先グループおよび低優先グループとして通知される。
【０１０９】
各スケジューリング部１４において、ＶｏＱ、および優先グループが決定され、入力バッファ部１２に通知されると、当該ＶｏＱに対する通知された優先グループ内のＱｏＳクラス選択部２２４または２２６において、１つのＱｏＳクラスを選択し、対応するＱｏＳキュー２２２から１パケットを読み出す。この際、最低帯域保証クラスについては、高優先グループの中から選択されたとしても低優先グループの中から選択されたとしても、タギングの有無にかかわらず対応するキューの先頭からパケットが読み出される。
【０１１０】
高優先グループ内および低優先グループ内での１つのＱｏＳクラスの選択は、例えば図６０に示すように単純なラウンドロビン方式を適用することができる。ラウンドロビン方式の場合、小さなハードウェアの規模で帯域を各ＱｏＳクラスで公平に配分することができる。しかしながら、ＱｏＳクラス間で到着トラヒック量に偏りがあると、トラヒック量の増加に比例して遅延時間が増加して遅延時間に不公平を生じるという問題がある。
【０１１１】
グループ内での選択をパケットの到着順に行なえば、遅延時間の不公平は解消される。これを実現するためには、例えば、図６１に示すように、ＱｏＳクラス選択部２２４，２２６のキューに格納されるデータに、到着順を示すタイムスタンプを付し、この順で選択すれば良い。図６１において、巡回カウンタ２４０，２４２は各優先グループ内のＱｏＳクラスのパケットの情報を登録する度に１だけインクリメントされ、入力バッファ量に対応するパケット数までカウントしたら０に戻るカウンタであり、このカウンタの値がパケットの情報に付加される。またカウンタ値検索部２４４，２４６もパケットを選択する毎に１づつインクリメントされる内部カウンタを有し、この値に一致する巡回カウンタ値を有する情報を検索する。
【０１１２】
別の方法として、図６２に示すように、それぞれのグループ内において、パケットが到着したＱｏＳクラスの番号をＦＩＦＯ２３０およびＦＩＦＯ２３２に格納する。選択の際に、ＦＩＦＯから読み出された番号に対応するパケットを選択するようにすれば、到着順に選択することができる。
図６３は遅延時間が比較的公平なさらに他のグループ内選択方法を示す。まず、カウンタ２３４により、到着したパケットの数がＱｏＳクラスごとにカウントされる。パケットが選択されるとカウント値がデクリメントされる。一定の観測周期が経過するごとに、選択されずに残ったパケット数がＱｏＳクラスごとにカウンタ２３６に加算される。すなわち、カウンタ２３６では前周期とそれ以前の周期で到着し未だ選択されていないパケットの数がカウントされる。セレクタ２３８による選択の際に、カウンタ２３６の値がすべてゼロであるときは、カウンタ２３４の中でゼロでない値を持つＱｏＳクラスの中からラウンドロビン方式で１つのＱｏＳクラスが選択される。カウンタ２３６の中にゼロでない値を持つＱｏＳクラスがあればそちらを優先してラウンドロビン方式で１つのＱｏＳクラスが選択される。図６３に示した例では、現周期に到着した未選択のパケットをカウントするカウンタ２３４と、前周期およびそれ以前の周期で到着した未選択のパケットをカウントするカウンタ２３６の２組のカウンタが使用されているが、前周期のパケット数と前々周期およびそれ以前の周期のパケット数を別々にカウントするといったように、履歴をさらに細分化してカウントすれば、一層公平性が向上する。
【０１１３】
この手法は到着パケット数をカウントするだけなので、到着パケットごとにタイムスタンプまたはＱｏＳクラスの番号を記憶する手法と比べてハードウェアの量が少なくて済む。
図６４はグループ内選択のさらに他の手法を示す。図６４において、キュー長カウンタ２４０，２４２は各ＱｏＳクラスごとに未選択の固定長パケットのパケット数をカウントする。比較器２４４，２４６はキュー長カウンタ２４０，２４２の中でカウント値が最大のものを選択する。
【０１１４】
キュー長が長いことと到着トラヒック比が高いことは必ずしも一致しないが、ほぼ同様の傾向をもつため、ラウンドロビン方式の場合に比べより公平な遅延特性となることが期待できる。またキュー長はキュー長による廃棄制御等に利用するためのものと共用可能であるため、比較的ハード規模を小さく実現できる。
【０１１５】
【発明の効果】
以上説明したように本発明によれば、高速かつ少ないハードウェア規模で、可変長パケットのＱｏＳ制御、廃棄制御およびマルチキャスト制御を実現する大容量パケットスイッチが提供される。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る大容量パケットスイッチを概念的に示す図である。
【図２】可変長パケットの一例としてのＩＰｖ４のフレーム形式を示す図である。
【図３】固定長パケットの形式の一例を示す図である。
【図４】スイッチ部１６の入力例におけるスケジューリングを実現する具体的な構成を示す図である。
【図５】パイプライン処理によるスケジューリングの一例を示す図である。
【図６】入力側における最低帯域保証クラスのパケットのスケジューリングの一例を示す図である。
【図７】図６のスケジューリング処理のフローチャートである。
【図８】出力バッファ部１８の構成の第１の例を示す図である。
【図９】出力バッファ部１８の構成の第２の例を示す図である。
【図１０】図８の例の詳細な構成を示す図である。
【図１１】図８および図１０の構成において、出力回線がさらに複数の低速回線へ分離される場合を示す図である。
【図１２】図９の構成において、出力回線がさらに複数の低速回線へ分離される場合を示す図である。
【図１３】出力側の処理を考慮した入力側のスケジューラの構成を示す図である。
【図１４】図１３のスケジューラの動作の一例を示す図である。
【図１５】図１３のスケジューラの動作の一例を示す図である。
【図１６】図１３のスケジューラの動作のフローチャートである。
【図１７】本発明における可変長パケットのＱｏＳ制御の第１の例を概念的に示す図である。
【図１８】図１７のＱｏＳ制御を実現する回路構成の一例を示す図である。
【図１９】図１７のＱｏＳ制御の動作のフローチャートである。
【図２０】可変長パケットのＱｏＳ制御の第２の例を概念的に示す図である。
【図２１】図２０のＱｏＳ制御の動作のフローチャートである。
【図２２】可変長パケットのＱｏＳ制御の第３の例を概念的に示す図である。
【図２３】図２２のＱｏＳ制御の動作のフローチャートである。
【図２４】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第１の例を示す図である。
【図２５】図２４のＱｏＳ制御を実現する具体的な構成を示す図である。
【図２６】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第２の例を示す図である。
【図２７】図２６のＱｏＳ制御の動作のフローチャートである。
【図２８】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第３の例を示す図である。
【図２９】図２６のＱｏＳ制御の動作のフローチャートである。
【図３０】本発明のパケット廃棄制御における平均キュー長と廃棄確率の関係を示す図である。
【図３１】本発明のパケット廃棄制御の第１の例の構成を示すブロック図である。
【図３２】図３１の廃棄制御の処理のフローチャートである。
【図３３】図３１の廃棄制御におけるＬＢカウンタの動作の一例を示すグラフである。
【図３４】本発明の廃棄制御の動作の一例を示す図である。
【図３５】本発明の廃棄制御の動作の一例を示す図である。
【図３６】本発明のパケット廃棄制御の第２の例の構成を示すブロック図である。
【図３７】図３６の廃棄制御の処理のフローチャートである。
【図３８】図３６の廃棄制御におけるＬＢカウンタの動作の一例を示す図である。
【図３９】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４０】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４１】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４２】本発明における、フレーム組立てバッファからＤＭＵＸのフレーム単位での移動を概念的に示す図である。
【図４３】フレーム単位での移動の具体例を示す図である。
【図４４】フレーム単位での移動の具体例を示す図である。
【図４５】本発明の一実施例に係るマルチキャスト制御を概念的に示す図である。
【図４６】マルチキャスト制御の具体例を示す図である。
【図４７】マルチキャスト制御の具体例を示す図である。
【図４８】マルチキャスト制御の具体例を示す図である。
【図４９】マルチキャスト制御の具体例を示す図である。
【図５０】マルチキャスト制御の具体例を示す図である。
【図５１】マルチキャスト制御の具体例を示す図である。
【図５２】マルチキャスト制御の具体例を示す図である。
【図５３】マルチキャスト制御の具体例を示す図である。
【図５４】本発明の他のＱｏＳ制御を概念的に示す図である。
【図５５】図５４のＱｏＳ制御をスイッチの入力側に適用した例を示す図である。
【図５６】図５５の回路の動作のフローチャートである。
【図５７】図５４のＱｏＳ制御をスイッチの出力側に適用した例を示す図である。
【図５８】図５４のＱｏＳ制御において各ＱｏＳクラスのアービングの例を示す図である。
【図５９】最低帯域保証クラスに対するＱｏＳ制御を実現する構成の例を示す図である。
【図６０】優先グループ内のＱｏＳクラスの選択をラウンドロビン方式で行なう場合を示す図である。
【図６１】優先グループ内のＱｏＳクラスの選択をタイムスタンプにより行なう場合を示す図である。
【図６２】優先グループ内のＱｏＳクラスの選択を到着順序管理ＦＩＦＯにより行なう場合を示す図である。
【図６３】優先グループ内のＱｏＳクラスの選択を観測周期内パケット数の履歴により行なう場合を示す図である。
【図６４】優先グループ内のＱｏＳクラスの選択をキュー長により行なう場合を示す図である。
【符号の説明】
１０…パケット分割部
１２…入力バッファ部
１４…回線間スケジューラ
１６…スイッチ部
１８…出力バッファ部
【発明の属する技術分野】
本発明は、ＩＰ（Internet Protocol ）パケットのような可変長パケット（またはフレーム）のルーチングを行なうパケットスイッチ、特に、可変長パケットに対するＱｏＳ（Quality of Service）制御、廃棄制御、マルチキャスト制御といった複雑な制御を実現する大容量パケットスイッチ、それに用いることの可能なスケジューリング装置、廃棄制御回路、マルチキャスト制御回路およびＱｏＳ制御装置に関する。
【０００２】
【従来の技術】
近年、インターネットの急速な普及により、通信トラヒック需要が急増しており、Ｔｂｐｓ（テラビット／秒）クラス以上の高速・大容量のルータやスイッチの実現が望まれている。
従来、ＩＰパケットのような可変長パケットを処理するルータ装置において、パケットフォワーディング処理をハードウェア化することにより、高速化を図るアプローチが行われているが、ＱｏＳ制御、廃棄制御、マルチキャスト制御といった複雑な処理については、ソフトウェア処理、またはハードウェアで行う場合にも低速での処理に限られていた。またＡＴＭ（Asynchronous Transfer Mode）交換機においては、基本的に固定長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御が行われていた。
【０００３】
前者のルータ装置のようにソフトウェアベースの方式では、複雑な処理を実装することができるが、回線速度の高速化にともない、回線速度と同等の速度でソフトウェアの処理を実現することは困難となってきており、より高速・大容量の処理は困難となっていた。
後者のＡＴＭ交換機では、固定長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御を行うため、ＩＰパケットのような可変長パケット毎にＱｏＳ制御、廃棄制御、マルチキャスト制御する機能を持たない。またＧＦＲ（Guaranteed Frame Rate ）というＡＴＭにおいてＡＡＬ５の可変長パケット識別を利用して、可変長パケットレベルのＱｏＳ保証、廃棄制御を行うという試みも行われているが、この方式でも、パケットのスイッチング、転送単位はセルと呼ばれる固定長パケット単位であり、ネットワークを構成する全ノードをＡＴＭ交換機で実現する必要があり、ＩＰパケット単位でスイッチング、転送処理を行うパケットスイッチとして適用することはできない。
【０００４】
次に、ＱｏＳ制御に関しては、主に、使用帯域が予め規定されないベストエフォートクラスの可変長パケット間での公平な帯域分配方法として、ＷＦＱ（Weighted Fair Queueing）が知られている（A.K.Parekh, R.G.Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case", IEEE/ACM trans. On Networking, Vol 1, No.3, pp.344-357, Jun. 1993; A.K.Parekh, R.G.Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Multiple-Node Case", IEEE/ACM trans. On Networking, Vol 2, No.2, pp.137-150, Jun. 1993）。
【０００５】
ＷＦＱは、キューイングされているコネクションに設定されているウェイトに比例して余剰帯域を分配するＧＰＳ（Generalized Processor sharing ）を基本にしている。ＧＰＳでは、アクティブな（キューを使用している）任意のコネクション（ｉ）（ｊ）について常に式（１）が成立するように読出しデータ量を分配する帯域割り当て方式である。
【０００６】
Ｓ（ｉ，τ，ｔ）／Ｓ（ｊ，τ，ｔ）≧Φ（ｉ）／Φ（ｊ） …（１）
ここで、Φ（Ｎ）はコネクションＮに対するウェイト、Ｓ（Ｎ，τ，ｔ）はコネクションＮに対して時間〔τ，ｔ〕の間にサービスされるデータ量である。また式（１）で等号が成り立つのはコネクション（ｉ）と（ｊ）のデータがともにキューイングされているときである。例えば、各コネクション＃０，＃１，＃２，＃３にそれぞれ、ウェイトを０．１：０．２：０．４：０．３の割合で与えておき、もし仮にコネクション＃３のみノンアクティブ（パケットがキューイングされていない）で、それ以外のコネクションがアクティブであるとき、コネクション＃３を除くコネクション＃０〜＃２のコネクションで、各々読出し帯域が０．１：０．２：０．４になるように帯域を分配する。
【０００７】
ＧＰＳは基本的に無限小のビット単位での帯域分配を意味するが、現実には分配単位が可変長パケット（フレーム）毎であるため、ＷＦＱではＧＰＳをフレームレベルの公平な帯域分配に拡張している。
ＷＦＱでは、フレーム到着時にフローｉのｋ番目のパケットが時刻ｔ（ｉ，ｋ）に到着し、そのフレーム長をＬ（ｉ，ｋ）としたときの終了予定時刻Ｆ（ｉ，ｋ）を式（２）で計算し、Ｆの小さい順から読み出す。
【０００８】
Ｆ（ｉ，ｋ）＝ｍａｘ｛Ｆ（ｉ，ｋ−１），ｔ（ｉ，ｋ）｝＋Ｌ（ｉ，ｋ）／ｒ（ｉ，ｋ） …（２）
但し、ｒ（ｉ）＝Φ（ｉ）／ΣΦ×Ｒ、ここでΣΦはキューイングされているコネクションのウェイトの合計であり、Ｒは出力リンクのレートである。
ここで、ｒ（ｉ，ｋ）はパケットがキューから読み出される度に変化するため、全コネクションについてＦ（ｉ，ｋ）の再計算が必要となり、また、キューイングされている全パケットについて、終了予定時刻Ｆ（ｉ，ｋ）を保持しなければならないため、ハード規模が大きくなるという問題があった。そのため実時間の代わりにVirtual Time（キューイングされているコネクション数に応じて刻みの変化する時間カウンタ）を式（３）のように定義し、Ｆ（ｉ，ｋ）を式（４）のように再定義し、Virtual TimeをΣΦとＲが変化するたびに再計算し、Ｆ（ｉ，ｋ）については、パケット到着時に１回計算するのみで実現する方式が提案されている。
【０００９】
Ｖｔ＝Ｖ（τ）＋（Ｒ／ΣΦ）（ｔ−τ） …（３）
Ｆ（ｉ，ｋ）＝ｍａｘ｛Ｆ（ｉ，ｋ−１），Ｖｔ（ｉ，ｋ）｝＋Ｌ（ｉ，ｋ）／Φ（ｉ） …（４）
しかしながら、Virtual timeを用いると、演算量の削減が図れるが、実時間で処理する必要のある、転送レートが規定された帯域保証クラスのパケットとの間の優先度制御が困難となるという問題が生じていた。
【００１０】
廃棄制御に関しては、アダプティブな廃棄方式としてＲＥＤ（Random Early Detection）が知られている（Internet Society RFC2309）。これは、輻輳状態が同期してしまうことを防ぐため、輻輳状態になったらバッファが溢れる前に輻輳状態に応じた確率でランダムに廃棄を行う方式である。これにより、ＴＣＰ(Transmission Control Protocol）のような輻輳制御機能を持つプロトコルでは早めに送信レートを落とすことが出来、かつ全端末の動作が同期しないので安定したスループットが出るという特長を持つ。
【００１１】
しかしながら、ＲＥＤは、廃棄をランダムに行う必要があるためアルゴリズムが複雑でソフトウェアにより実装されており、高速化には向いていなかった。また、基本的に廃棄はフレーム（可変長パケット）到着時に行うため、その時点でバッファに溜まっているデータが全て掃けた後でないと廃棄が端末に通知されないという問題があった。
【００１２】
マルチキャスト制御に関しては、バッファアドレス管理方式として、従来では固定長パケットに対するパケットｂｙパケットの動作のみが実現されており、複数の固定長パケットの連続からなる可変長パケットを意識した制御は実現されていない。
【００１３】
【発明が解決しようとする課題】
したがって本発明の目的は、可変長パケットに対して、高速かつ少ないハードウェア規模でＱｏＳ制御、廃棄制御、マルチキャスト制御といった複雑な制御を実現する大容量パケットスイッチ、それに用いることの可能なスケジューリング装置、廃棄制御回路、マルチキャスト制御回路およびＱｏＳ制御装置を提供することにある。
【００１４】
【課題を解決するための手段】
本発明によれば、複数の入力回線からの可変長パケットを固定長パケットに分割するパケット分割部と、複数の入力回線のそれぞれに対して設けられ、その各々が、複数の出力回線の各々について、指定可能なＱｏＳ（Quality of Service）クラス数よりも少数の相異なる優先度が与えられたキューを有し、対応する入力回線からの固定長パケットを、出力回線およびＱｏＳクラスに従って該キューのいずれかに格納する複数の入力バッファ部と、入力バッファ部のキューに格納された固定長パケットを、キューに与えられた優先度に従って単位時間内では出力回線が同じである２以上の固定長パケットが読み出されないように読み出すスケジューラと、スケジューラが読み出した固定長パケットの各々を複数の出力回線のうちの指定された１つにルーチングするスイッチと、複数の出力回線のそれぞれに対して設けられ、スイッチから出力される固定長パケットからの可変長パケットの組み立ておよびＱｏＳクラスに基づく優先制御を行なうための複数の出力バッファ部とを具備するパケットスイッチが提供される。
【００１５】
本発明によれば、指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、可変長パケットがキューの先頭に達したとき第１の値を対応するトークンに加算する手段と、単位時間が経過するごとにアクティブなＱｏＳクラスのトークンから第２の値を減算する手段と、出力回線へのパケット装置が可能なとき、アクティブなＱｏＳクラスの中で、対応するトークンが最小もしくは０であるものの可変長パケットの読み出しを開始する手段とを具備するスケジューリング装置もまた提供される。
【００１６】
本発明によれば、指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、帯域保証クラスの可変長パケットおよび指定帯域内で入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第１のカウンタと、ベストエフォートクラスの可変長パケットおよび指定帯域を超えて入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第２のカウンタと、第１のカウンタについて０でないカウント値を有するＱｏＳクラスおよび第２のカウンタについて０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含むスケジューリング装置もまた提供される。
【００１７】
本発明によれば、バッファ内に格納されているパケットの量のその閾値との差分にバッファの先頭に存在する可変長パケットのパケット長を乗じてその結果を出力する演算回路と、カウンタと、演算回路の演算結果をカウンタに加算する加算回路と、カウンタの値が所定値を超えているときバッファの先頭に存在する可変長パケットを一度に廃棄し、前記パケット長に所定値を乗じた値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路もまた提供される。
【００１８】
本発明によれば、バッファ内に格納されているパケットの量のその閾値との差分を出力する演算回路と、カウンタと、演算回路の演算結果をカウンタに加算する加算回路と、カウンタの値が所定値を超えているときバッファの先頭に存在する固定長パケットを廃棄し、所定値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路もまた提供される。
【００１９】
本発明によれば、バッファに格納されている、マルチキャスト制御すべき可変長パケットのアドレスを格納するマルチキャストキューと、複数の出力回線のそれぞれに対して設けられた複数の出力バッファキューと、バッファに格納されている可変長パケットのアドレスを管理するアドレス管理テーブルと、マルチキャスト制御すべき可変長パケットのアドレスがマルチキャストキューに格納されたとき、該可変長パケットのアドレスを含むレコードをその出力先の数だけアドレス管理テーブルに格納し、その出力先に対応する出力バッファキューに、該レコードのアドレスをそれぞれ格納する制御手段とを具備するマルチキャスト制御回路もまた提供される。
【００２０】
本発明によれば、ＱｏＳクラスを有する可変長パケットをスイッチングするパケットスイッチにおいて、複数のＱｏＳクラスを簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記可変長パケットの読み出し制御を行う手段を備えたことを特徴とするパケットスイッチもまた提供される。
本発明によれば、ＱｏＳクラスを有するＩＰパケットを固定長パケットへ変換し、固定長パケット単位でスイッチングするパケットスイッチにおいて、ＩＰパケットの優先度クラスを、ＩＰパケットに割り当てられるＱｏＳクラスの数より少ない数の簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記固定長パケットの読み出し制御を行う手段を備えたことを特徴とするパケットスイッチもまた提供される。
【００２１】
本発明によれば、ＱｏＳクラスを有するＩＰパケットを固定長パケットへ変換し、固定長パケット単位でスイッチングするパケットスイッチにおいて、ＩＰパケットの優先度クラスを、ＩＰパケットに割り当てられるＱｏＳクラスの数より少ない数の簡易な優先度クラスにマッピングする手段と、簡易な優先度クラスに基づいて、前記固定長パケットをスイッチへ読み出し制御を行う手段と、スイッチング後の前記固定長パケットを、ＩＰパケットに割り当てられるＱｏＳクラスに基づいて読み出し制御する手段を備えたことを特徴とするパケットスイッチもまた提供される。
【００２２】
本発明によれば、高優先グループに属する１つ以上のＱｏＳクラスの中からパケットを読み出すべき１つのＱｏＳクラスを選択する第１の選択部と、低優先グループに属する１つ以上のＱｏＳクラスの中からパケットを読み出すべき１つのＱｏＳクラスを選択する第２の選択部と、高優先グループと低優先グループのいずれか一方を選択し、それによって第１または第２の選択部が選択したＱｏＳクラスのパケットを選択する第３の選択部とを具備するＱｏＳ制御装置もまた提供される。
【００２３】
【発明の実施の形態】
図１に本発明の一実施形態に係るパケットスイッチを概念的に示す。入力回線から入力された可変長パケットは、パケット分割部１０において固定長パケットに分割され入力バッファ部１２にバッファリングされる。入力バッファ部１２は、Ｎ本の入力回線数分あり、各入力バッファは論理的にＭ本の出力回線毎、およびＱｏＳ毎（帯域保証クラス１１、ベストエフォートクラス１７）に分かれている。各入力回線より入力バッファ部１２へ入力されたパケットは各々対応する出力回線毎、ＱｏＳ毎にバッファリングされる。この際、ＱｏＳクラスを予め契約や呼受け付け制御により入力トラヒック量の予想可能な帯域保証クラスと、契約や呼受け付け制御がなく入力トラヒック量の予想ができないベストエフォートクラスの２クラスのいずれかに縮退して割り当てる。
【００２４】
入力バッファ部１２にバッファリングされた各パケットは、回線間スケジューラ１４により、スイッチ部１６への送出タイミングが調整される。この際、回線間スケジューラ１４では、はじめに出力回線毎にバッファリングされたパケットのうち帯域保証クラスのパケットについて、複数の入力回線で同一の出力回線を選択しないように出力回線を選択する、競合制御を行う（図１：１３）。次にベストエフォートクラスのパケットについて、このとき選択されなかった出力回線について、同様に複数の入力回線で同一の出力回線を選択しないように競合制御を行う（図１：１５）。以上のような回線間スケジューリング動作を単位時間内、例えば、１つの出力回線で固定長パケット１個に相当するデータを送出するに要する時間内で実施する。これにより、各入力回線間の論理出力バッファ毎、ＱｏＳクラス毎の競合制御のもとで各入力バッファから出力されるパケットが選択され、スイッチ部１６へ転送される。転送されたパケットはスイッチ部１６でパケットに付与されたあて先情報を元に各出力バッファ部１８へスイッチングされる。
【００２５】
出力バッファ部１８に入力した各パケットは、実際のＱｏＳクラス毎（通常３クラス以上）にバッファリングされる。出力バッファ部１８では、各出力回線内の各ＱｏＳクラス毎のＱｏＳ制御（設定レートや優先順位に応じた読み出し順序制御）を行い、各出力回線にパケットを出力する。
ここでは、入力バッファ部１２でのＱｏＳクラス数を帯域保証クラスとベストエフォートクラスの２クラスに縮退させている。これにより、多数のキュー間（入力回線数×出力回線数×ＱｏＳクラス数（３以上））での競合制御を入力回線数×出力回線数×２に削減できる。
【００２６】
一般にＱｏＳ制御としては、単純な優先制御だけでなく、読み出しレートなどの複雑な読み出し順序の制御が必要であるが、ＱｏＳクラスを帯域保証クラスとベストエフォートクラスに縮退させ、帯域保証クラスをスケジューリングしてからベストエフォートクラスをスケジューリングすることによりスケジューリング処理を簡単化している。
【００２７】
さらに、スイッチの内部動作速度を入力バッファの到着速度より高め、スイッチング後の出力バッファ１８において、実際のＱｏＳクラス毎のＱｏＳ制御を行うことにより、パケットスイッチトータルとしてのＱｏＳ制御ポイントを出力バッファ部のＱｏＳ制御に集約できる。この際、出力バッファ部では、各出力回線毎のＱｏＳクラス制御のみ行えば良いことから、スイッチ全体のＱｏＳ制御が必要な入力バッファ部で行う場合に比べ、必要なハードウェアの量は少ない。
【００２８】
図１のパケットスイッチで採用されている、出力回線毎の論理キューを持つ入力バッファ型スイッチでは、ほぼ１００％のスループットが実現されるので、予めトラヒック量が予想できるクラスに対しては、入力バッファ側におけるパケットの廃棄率や遅延時間を出力バッファ側におけるＱｏＳ制御によって生じるパケット廃棄率や遅延時間に比べて非常に小さくできる。スイッチ内部の動作速度を高めることにより、これらはさらに小さくすることができる。したがって、入力側で複数のＱｏＳクラスを２クラスにマッピングしても実質的に問題ない。
【００２９】
図２および図３にそれぞれ本発明における可変長パケットフォーマットの一例、および可変長パケットを複数の固定長パケットに分離するときの固定長パケットのフォーマットの一例を示す。また、表１および表２にはそれぞれ、図２および図３における各フィールドの説明を示す。ここでは、可変長パケットとしてＩＰｖ４フォーマット（Internet Society RFC791 ）を用いている。但し、宛先アドレスのような、それによって各パケットのフローまたはコネクションを識別できる情報要素、およびＱｏＳクラス値が含まれているパケットであれば、どのようなフォーマットでも良い。ここでＱｏＳクラス値は、パケット中に記述されたＱｏＳクラス値ではなく、フローやコネクションに対して予め設定されたテーブルからＱｏＳクラスを変換して求めても良い。固定長パケットも同様に装置内部ローカルなパケットであるため、必要な情報要素が含まれていれば、フォーマットはどのようなフォーマットでも良い。
表１
Ｖｅｒｓ バージョン番号
ＩＨＬ ヘッダ長
Ｔｙｐｅ ｏｆ Ｓｅｒｖｉｃｅ 優先度
Ｔｏｔａｌ Ｌｅｎｇｔｈ ＩＰｖ４ペイロード長
Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ フラグメントＩＤ
Ｆｌａｇｓ フラグ
Ｆｌａｇｍｅｎｔ Ｏｆｆｓｅｔ フラグメントオフセット
Ｔｉｍｅ ｔｏ Ｌｉｖｅ ホップ期限
Ｐｒｏｔｏｃｏｌ プロトコル
Ｈｅａｄｅｒ Ｃｈｅｃｋｓｕｍ ヘッダチェックサム
Ｓｏｕｒｃｅ Ａｄｄｒｅｓｓ 送信元アドレス
Ｄｅｓｔｉｎａｔｉｏｎ Ａｄｄｒｅｓｓ あて先アドレス
Ｐａｙｌｏａｄ ペイロード
表２
ＥＮ 空きセル識別子（０：空きセル、１：有効セル）
Ｃ マルチキャスト識別子
ＱＣＰ Ouality of Service：品質クラス識別子
ＣＩＤ コネクション識別子
ＰＫＬ ペイロード長
Ｆ タギングフラグ（０：高優先クラス、１：低優先クラス）
ＦＲＩ フレームタイプ（００：中間、０１：先頭、１０：最終、１１：先頭＆最終）
図４に図１のスイッチ部１６の入力側におけるスケジューリングを実現する具体的な構成を示す。図４の入力バッファ部のスケジューラ構成において、入力されたフレームは、ポリシング制御部２０において、予め設定されたレート以上のものについてはタギングされる。タギング情報はフレーム毎に付与され、別線、または図２の可変長パケットフォーマットに内部ヘッダを追加してそこにビットを付与することにより後段に転送される。パケット分割部１０では入力された可変長パケットを一定長のセグメントに分割する。ヘッダ付与部２２では、ヘッダ変換テーブル２４の情報をもとに各セグメントに各種ヘッダ情報を付与して図３の固定長パケットを組み上げる。
【００３０】
ここで、ＱｏＳクラスに関しては、予めコネクション毎、またはフロー毎に設定されたＱｏＳクラス（例えば４クラス）のテーブルを参照しＱＣＰビットに０〜３の値を付与するとともに、これらのＱｏＳクラスをさらに帯域保証クラスとベストエフォートクラスの２クラスにマッピングする。この２クラスにマッピングされたＱｏＳクラスを縮退ＱｏＳクラスと呼ぶことにする。入力バッファ部１２、およびスケジューラ部２５ではこの縮退ＱｏＳクラスと出力回線番号情報に基づき、それぞれパケットのキューイング、パケット読み出しのスケジューリングを行う。
【００３１】
ここで、スケジューラ部２５では、後段のマトリックススイッチ部へ入力される全パケットについて、効率良くしかも同一の出力回線を持つパケットが同時に転送されないようにスケジューリングを行う。さらにこの競合制御時に縮退ＱｏＳクラスに応じて、初めに帯域保証クラスについてスケジューリングを行い、次に帯域保証クラスのスケジューリングで選択されなかった入力回線と出力回線についてベストエフォートクラスについてスケジューリングを行う。スケジューリング処理の具体的な例については後に詳しく説明する。
【００３２】
図５は、スケジューラの正順、逆順を考慮したパイプラインの８回線について帯域保証クラス、ベストエフォートクラスをスケジューリングした場合のパイプラインのシーケンスである。
図５に示した例では、パイプラインのシーケンス順序を入れ替えることにより、１周期に正順、逆順を考慮したパイプラインと同じパターンが同数現れるようになっており、入力回線間の公平性を保証している。さらに同一時間に同一入力回線に対する処理の競合を避けることになり、同じ処理をしなければならないハード処理量を削減している。
【００３３】
尚、スケジューリングアルゴリズムについては、帯域保証クラスの方がベストエフォートクラスより優先度が高くなれば、他のアルゴリズムを用いても良い。
以上のようなスケジューリング処理により決定されたパケットは入力バッファ部からよみだされ、マトリックススイッチにおいて、出回線情報にもとづいてスイッチングされる。このとき、マトリックススイッチのスイッチング速度を各回線のデータレートの総和より大きく（内部速度アップという）することにより、入力バッファ部の廃棄遅延特性の向上を図り、入力バッファ部における競合によりスイッチトータルとしての品質が劣化するのを抑制してもよい。
【００３４】
スイッチングされた固定長パケットは一旦出力バッファ部にキューイングされる（図１：１８）。この際、後に説明するように、可変長パケットへ戻してからＱｏＳ制御を行なうか、または先に固定長パケットのままでＱｏＳ制御を行ってから可変長パケット組立てを行っても良い。
以上のような一連の処理により、入力バッファ側では、縮退した２クラスのみ簡易なＱｏＳ制御を行いながら、出力バッファ側で３クラス以上のＱｏＳ制御を行うことにより、スイッチトータルとして、３クラス以上のＱｏＳ制御を可能としている。
【００３５】
上記は、入力可変長パケットを一旦固定長パケットに分割して行っているが、スケジューラ部において、可変長パケットの連続性を崩さない選択を行うことにより、実質的に可変長パケットのままでスイッチング処理を行なうようにしても良い。
図６は、入力バッファ部１２において、1 ＱｏＳクラス内に帯域保証が必要な最低保証レート分と帯域保証が不要だがトラヒック量が予測できないベストエフォート分を合わせ持つ、最低帯域保証クラスを収容する手法の一例を示す。最低帯域保証クラスを収容する際、最低帯域保証クラスのパケットもベストエフォートクラスのキュー１７にバッファリングする。但し、キューの前段のポリシング制御部２６において、最低帯域保証クラスに対して、最低保証レートを超えて入力されるパケットに対してはタギングを行っておき、タギングなしのパケットの廃棄閾値θ3 に対して、タギングありのパケットとベストエフォートクラスのパケットに対する、使用可能なキューのしきい値θ2 を低く設定する。
【００３６】
これにより最低帯域保証クラスを含む場合についても２クラスにマッピングすることが可能になる。この際、最低帯域保証クラスの最低保証レート内で入力されるパケットの廃棄閾値θ3 を帯域保証クラスのパケットの廃棄閾値θ1 と等しく設定して、帯域保証クラスと同等の品質保証を可能としても良い。また最低帯域保証クラスの最低保証レートを超えて入力されるパケットについては、同じベストエフォートクラスにマッピングされる。
【００３７】
図７にフローチャートを示す。入力バッファ部において、到着パケットが最低帯域保証クラスのときに、ベストエフォートクラスとしてキューイングしておき、その際図７のようにタギング情報に基づいた廃棄制御を行うことにより、扱うクラス数を増やさずに帯域保証クラスの品質保持を可能としている。
図８および９に出力バッファ部１８の構成の２つの例を示す。出力バッファ部１８には複数の入力回線からのパケットが混在した状態で到着する。この混在した状態をパケットインタリーブまたは単にインタリーブという。従って、出力バッファ部１８でこのインタリーブされた複数の固定長パケットを組立て、元の可変長パケットに戻してから、出力回線よりパケットを送出する必要がある。さらにＱｏＳ保証するためには、予め設定されたレートや優先度に応じた順序でパケットが送出されなければならない。
【００３８】
図８の例では、出力バッファ部にインタリーブして到着した固定長パケットを可変長パケット組立てバッファ２８に一旦バッファリングし、元の可変長パケットに戻す。この際インタリーブして到着したパケットは、複数の入力回線のものからのものが混在しており、さらに同一入力回線内でも入力回線側でＱｏＳクラス制御をした場合には、複数のクラスからのパケットが混在する。前述の例ではこのＱｏＳクラス数は２クラスとなる。従って、入力回線数（Ｎ）×入力回線側のＱｏＳクラス数（ｅｘ．２）個のキューを用意し、インタリーブして到着した固定長パケットを一旦バッファリングし、元の可変長パケットを組立てる。
【００３９】
可変長パケットが組立て終わったら、ＱｏＳクラス（ｅｘ．４クラス）に応じて、可変長ベースＱｏＳ制御部３０に転送し、可変長ベースＱｏＳ制御部３０において、パケット長を考慮したＱｏＳ制御を行うことにより、予め設定されたレートや優先度に応じた順序でパケットを出力回線より転送する。
図９の例では、出力バッファ部にインタリーブして到着した固定長パケットのままで、固定長ベースＱｏＳ制御部３２においてバッファリングし、予め設定されたレートや優先度に応じた順序でパケットを後段の可変長パケット組立て部に転送する。この場合のＱｏＳ制御はパケット長が固定であるので容易である。
【００４０】
後段の可変長パケット組立てバッファ３４には入力回線毎および、出側でのＱｏＳクラス毎にパケットがインタリーブされた状態で到着するので、入力回線数（Ｎ）×出側のＱｏＳクラス数（ｅｘ．４）個のキューを用意し、インタリーブして到着した固定長パケットを一旦バッファリングし、元の可変長パケットを組立て、パケットが組みあがった順番に出力回線より可変長パケットを転送する。
【００４１】
図１０は図８をより詳しくした図である。可変長パケット組立てバッファ２８に到着するパケットは、異なる入力回線、異なる縮退ＱｏＳクラスのものがインタリーブして到着するので、可変長パケット組立てバッファ２８では、入力回線毎、縮退ＱｏＳクラス毎にキューイングする。可変長パケット管理部３６では、各パケットに付与された可変長パケットの先頭、末尾の情報より１可変長パケット分のパケットを監視し、１可変長パケット分が組みあがったら、可変長パケット送信通知をだし、１可変長パケット分連続的に後段へ転送する。この際、実際のパケット内の情報を転送するのではなく、バッファに書きこまれたアドレス、およびアドレスチェーン情報のみをコピーしてもよい。さらに後段のＱｏＳ制御部３０では、ＱｏＳクラス数分のバッファを用意しておき、到着パケットをＱｏＳクラス（ｅｘ．４クラス）毎にキューイングする。ＱｏＳスケジューリング部３８では、キューへ書きこまれた、パケットのＱｏＳクラスやフレーム長を監視し、パケット長や予め設定されたレートやウェイト、優先度に応じて読み出し順序の競合制御を行い、読み出し可能となったＱｏＳクラスに対して出力回線への送出を指示する。
【００４２】
図１１は出力回線がさらに複数の低速回線へＤＭＵＸ（分離）される場合を示す。可変長パケット組立てバッファ２８の処理は同じであるが、ＱｏＳ制御部３０において、ＱｏＳクラス毎のキューを論理出方路（ＤＭＵＸ）分保持しており、ＱｏＳスケジューリング部３８において、各ＤＭＵＸ中の各ＱｏＳクラスキューからの読み出しがＤＭＵＸの帯域を超えないように制御する。ここで、各ＤＭＵＸへのタイムスロットを割り当て、タイムスロットに対応するＤＭＵＸキュー内の各ＱｏＳクラスについてＱｏＳスケジューリングを行う。
【００４３】
図１２では図９の構成において、図１１と同様に複数の低速回線へＤＭＵＸ（分離）されるとともに、ＱｏＳ制御部と可変長パケット組立てバッファの論理的な配備位置が逆になっている。このため、ＱｏＳ制御部３２では、ＱｏＳクラス毎、ＤＭＵＸ毎にキューイングし、固定長パケットのまま各ＤＭＵＸ中の各ＱｏＳクラスキューからの読み出しがＤＭＵＸの帯域を超えないように行なわれてＱｏＳスケジューリングを行う。また可変長パケット組立て部３４には、入力回線毎、ＱｏＳクラス毎、ＤＭＵＸ毎にキューイングしておき、１可変長パケット分組みあがった時点で出力回線へ１可変長パケット分連続的に出力する。
【００４４】
出力バッファ部１８での処理を考慮すると、スイッチ部１６の各出力回線から出力される固定長パケットの並びが、複数の入力回線からのパケットが混在した状態であるとしても、同じ可変長パケットから生じた固定長パケットができるだけ連続するように入力側でスケジューリングすることが望ましい。図１３は、この点を考慮した回線間スケジューラ１４の構成を示す。スケジューラ部の可変長パケット管理部４０は、各論理出方路毎の可変長パケット送出状態を管理するものであり、可変長パケットを構成する最初の固定長パケットを送出したときフラグをセットし、最終パケットを送出したときクリアすることにより、可変長パケット送出状態を識別する。また、未確定管理部４２は、他の入力回線によって読み出しが確定している回線を管理するもの、要求管理部４４は、入力バッファ部からの読み出し要求数を管理するもの、スケジューリング処理部４６は、要求情報、未確定情報、可変長パケット送出状態をもとに送出論理出方路を決定するものである。
【００４５】
スケジューリング処理部４６は、各論理出力回線毎に、現在可変長パケットを構成する固定長パケットを送出中であるかを判定し、スケジューリングの際に送出中の論理出力回線を優先的に選択する。これにより、１つの可変長パケットを構成する固定長パケットがまとめて読み出されやすくなるため、出力側の可変長パケットバッファでの待ち合わせ時間を低減することが可能となり、出力側の可変長パケット組み立てバッファ量を削減することができる。
【００４６】
以下にスケジューリング動作の具体的な例を図１４および図１５を参照して説明する。ここでは、簡略化のため３×３スイッチを例にとり動作を説明する。各入力回線は、論理的に出力方路毎に分割された論理キュー（以下、ＶＯＱ：Virtual Output Queueと記す）４７を有している。また、可変長パケット送出状態を示す可変長パケット状態レジスタ４８を各ＶＯＱ毎に備える。各ＶＯＱはさらに複数のＱｏＳクラスごとに分割されているがここでは図示が省略されている。
【００４７】
上記可変長パケット状態レジスタ４８は、可変長パケット送出中のＶＯＱを識別するためのレジスタであり、バッファからパケットを読み出したとき、そのパケットのパケット種別を識別し、可変長パケットエンドパケットで無いとき、“１”にセットされ、可変長パケットエンドパケットのときにリセットされる。スケジューラでは、本レジスタが“１”に設定されている状態を可変長パケット送出状態として扱う。読み出したパケットが可変長パケットエンドパケットであるか否かは、パケットヘッダのパケット識別ビットを参照することにより判定可能である。
【００４８】
スケジューリング処理部４６は、上記可変長パケット状態レジスタ４８を参照して、各入力回線について以下の２つのＳＴＥＰに沿って読み出しＶＯＱを決定する。
ＳＴＥＰ１：可変長パケット送出中のＶＯＱのみをスケジューリング対象としてスケジューリング処理を実施。
【００４９】
ＳＴＥＰ２：ＳＴＥＰ１において読み出しＶＯＱが確定しなかった場合に限り、可変長パケット未送出状態のＶＯＱを対象としてスケジューリングを実施。
まず、初期状態として図１４（左側）に示すようなパケットが蓄積されており、スケジューリング順序として、入力回線＃０から順に入力回線＃１→＃２の順でスケジューリングが実行されるとする。スケジューリングの開始入力回線（図中●印）は、スケジューリング周期毎に所定の規則に従って更新される。
(1) Ｔ＝０におけるスケジューリング動作
入力回線＃０では全てのＶＯＱが可変長パケット未送出状態であるため、上記ＳＴＥＰ１ではどのＶＯＱも確定されない。従って、ＳＴＥＰ２として可変長パケット未送出回線（この例では全てのＶＯＱ）の中からラウンドロビン方式により読み出しＶＯＱを決定する。ここでは、ＶＯＱ＃０が選択されたとする。（図中、読み出しＶＯＱを★印で示す）入力回線＃１でも同様の手順でスケジューリングが実行されるが、既に入力回線＃０によってＶＯＱ＃０が選択されているため、Ｔ＝０ではどのＶＯＱも選択することが出来ない。入力回線＃２では、ＶＯＱ＃１が選択されたとする。
(2) Ｔ＝０における可変長パケット状態レジスタ更新
スケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別に応じて可変長パケット状態レジスタを更新する。
【００５０】
Ｔ＝０では、入力回線＃０−ＶＯＱ＃０と、入力回線＃２−ＶＯＱ＃１からパケットが読み出される。これら読み出しパケットはいずれも、可変長パケットエンドパケットでないため、可変長パケット状態レジスタを“１”に設定する。（図１４の右側参照）これにより、次回のスケジューリング周期では、入力回線＃０−ＶＯＱ＃０と、入力回線＃２−ＶＯＱ＃１は、可変長パケット送出中ＶＯＱとして扱われ、優先的にスケジューリングされるようになる。
【００５１】
次に図１５を参照してＴ＝１におけるスケジューリング動作を示す。Ｔ＝１では、開始入力回線が更新され、入力回線＃１→＃２→＃０の順でスケジューリングが実行される。
(3) Ｔ＝１におけるスケジューリング処理
入力回線＃１では、全ての可変長パケット状態レジスタ４８が“０”であるため、可変長パケット未送出ＶＯＱの中から選択を行いＶＯＱ＃０を読み出しＶＯＱとする。
【００５２】
入力回線＃２では、可変長パケット送出中のＶＯＱがあるため、そのＶＯＱを優先的に選択する。この例では、可変長パケット送出ＶＯＱはＶＯＱ＃１しかないため、ＶＯＱ＃１を読み出しＶＯＱとする。複数のＶＯＱが存在する場合は、ラウンドロビン方式で選択する。
次に入力回線＃０でも、可変長パケット送出中のＶＯＱがあるため、同様に優先的に可変長パケット送出中のＶＯＱの中から読み出しＶＯＱを決定しようとするが、既にＶＯＱ＃０は入力回線＃１によって選択されているため、選択することが出来ない。従って、可変長パケット未送出回線の中から読み出しＶＯＱを決定する。この例では、ＶＯＱ＃１とＶＯＱ＃２が可変長パケット未送出であり、ラウンドロビンによりＶＯＱ＃１を選択する。このように、可変長パケット送出中のＶＯＱがある場合でも、他の入力回線によって選択されている場合で、可変長パケット送出中のＶＯＱが選択できない場合には、可変長パケット未送出ＶＯＱを選択する。
(4) Ｔ＝１における可変長パケット状態レジスタ更新
スケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別に応じて可変長パケット状態レジスタを更新する。
【００５３】
Ｔ＝１では、入力回線＃０−ＶＯＱ＃１、入力回線＃１−ＶＯＱ＃０および入力回線＃２−ＶＯＱ＃１からパケットが読み出される。
入力回線＃０−ＶＯＱ＃１、入力回線＃１−ＶＯＱ＃０から読み出されたパケットは共に可変長パケットエンドパケットで無いため可変長パケット送出レジスタを“１”に設定する。これにより、これらのＶＯＱは次のスケジューリング周期では、可変長パケット送出中ＶＯＱとして扱われ、優先的にスケジューリングされる。
【００５４】
一方、入力回線＃２−ＶＯＱ＃１から読み出されたパケットは、可変長パケットエンドパケットであるため、可変長パケット状態レジスタを“０”にクリアする。従って、本ＶＯＱは次のスケジューリング周期では、可変長パケット未送出ＶＯＱとして扱われる。
このように、可能な限り可変長パケット送出中のＶＯＱを優先的にスケジューリングすることにより、１つの入力回線から送出されるパケットは、ＶＯＱ毎に連続して読み出されやすくなるため、出力側の可変長パケット待ち合わせ時間を短くすることが可能となる。
【００５５】
図１６にこのスケジューリング処理のフローを示す。本フローは、１つの入力回線におけるスケジューリング処理フローである。
ステップ１００１〜１００４はスケジューリングプロセスである。まず、ステップ１００１において、優先的に可変長パケット送出中のＶＯＱについてスケジューリングを行う。ここで、未確定とは、他の入力回線によって選択されていないＶＯＱを意味し、要求ありとは、バッファにパケットが蓄積されていることを意味し、可変長パケット送出中とは、可変長パケット状態レジスタに“１”が設定されていることを意味する。次にステップ１００２において、上記ステップ１００１の処理によって、読み出しＶＯＱが確定したかを判定し、確定した場合には、可変長パケット状態レジスタの更新プロセスへ、未確定の場合には、可変長パケット未送出ＶＯＱのスケジューリングプロセスに移る。
【００５６】
ステップ１００３は、ステップ１００１において、ＶＯＱが確定されなかった場合にのみ実行され、可変長パケット未送出（可変長パケット状態レジスタ＝０）のＶＯＱについてスケジューリングを行う。ステップ１００４は、上記ステップ１００３において、読み出しＶＯＱが確定したかを判定するプロセスであり、未確定の場合にはスケジューリング処理を終了し、確定時は可変長パケット状態レジスタ更新プロセスに移る。
【００５７】
ステップ１００５〜１００７は、可変長パケット状態レジスタの更新プロセスである。ステップ１００１／１００３のスケジューリング処理によって決定されたＶＯＱからパケットを読み出し、読み出したパケット種別を判定し、可変長パケットエンドパケットで無いときには、可変長パケット状態レジスタを“１”に設定し、可変長パケットエンドパケットのときに同レジスタをクリアする。
【００５８】
図８，１０，１１の可変長ベースＱｏＳ制御部３０ではパケット長を考慮したＱｏＳ制御が必要になる。図１７は、このパケット長を考慮したＱｏＳ制御を実現する手法の一例を概念的に示す。図８の可変長ベースＱｏＳ制御部３０において、各ＱｏＳクラス毎にバッファリングされた先頭のパケットのパケット長に対応するカウンタ値（ここではトークンと呼ぶことにする）を設定する。この際トークン値は、例えば、各ＱｏＳクラスに対するウェイト値（Φi ）として式（５）のような正規化した値を使用すれば、パケット長をそのまま使用できる。
【００５９】
Φi ＝Ｒ×τ×Φis／ΣΦis …（５）
ここでＲは全体の目標リンクレート、τは内部処理の単位時間（ｅｘ．固定長パケット時間）、Φisは各ＱｏＳクラスに割り当てられたウェイト値、ΣΦisはアクティブなＱｏＳクラスに対するΦisの総和である。また添え字のｉは、ＱｏＳクラスに付された番号に対応している。なお、式（５）中のＲ×τ／ΣΦisの値は一定であるので、（５）式から計算されるΦi の代わりに各ＱｏＳクラスのウェイト値Φisを使うことができる。
【００６０】
図１７に示すように、各ＱｏＳクラスの先頭パケットに対応するトークン値（Ｔi ）を単位時間（τ）毎、Φi ／ΣΦi ずつ減算していき、回線にパケットが読出し可能なとき、各トークン値の中で最小値（ベストエフォートクラスのパケットのとき）または０（レートが規定される帯域保証クラスのパケットのとき）のトークン値を持つＱｏＳクラスのパケットを読み出す。
【００６１】
この手法では、ＷＦＱのようにウェイト値に応じて各ＱｏＳクラスの帯域をアクティブなＱｏＳクラスで比例分配することが可能である。またＷＦＱようにキューイングされている全パケットについて、終了予定時刻Ｆ（ｉ，ｋ）を保持しなくて良いため、ハード規模が削減できる。さらに、実時間でスケジューリングするための、読出しレートを規定する帯域保証型のＱｏＳスケジューリングとの間の優先度制御が可能である。また、ΣΦi をアクティブなキューの数によらず一定とすることにより、そのまま、読出しレートを規定する帯域保証型のＱｏＳスケジューラとして使用できるため、回路を共通化してハード規模の削減や設計工数の削減が図れる。また、トークンを加算する処理とトークンから減算値を減算する処理と各ＱｏＳクラスのトークンを比較し、最も小さいまたは０のトークンを持つＱｏＳクラスのキューを選択して読み出す処理は、パイプライン化することも可能であり、高速なＱｏＳ制御を行うことも可能である。
【００６２】
図１８に実際のハードウェア構成の例、図１９にフローチャートを示す。図示した例は、可変長ベースＱｏＳ制御部において、可変長パケット組立てバッファ部とＱｏＳ制御部でパケットバッファは共通でバッファへの書きこみアドレスのみを転送する場合の構成に対応している。出力回線部に入力された固定長パケットは、パケットバッファ５０へ書きこまれるとともに、アドレス管理ＦＩＦＯ５２において、入力回線毎、縮退ＱｏＳ毎にアドレスのＦＩＦＯチェーンを構成する。可変長パケット組立て部５４では、各キューへの１可変長パケット分の到着を管理し、１可変長パケット分到着した可変長パケットについて、対応するパケットバッファのアドレスをコピーし、ＱｏＳクラス毎、ＤＭＵＸ毎のアドレスＦＩＦＯを構成する。さらに、ヘッダ情報をパケット識別部５６に転送する。パケット識別部５６ではパケットヘッダからＱｏＳクラス、ＤＭＵＸ番号やパケット長といったＱｏＳスケジューリングに必要な情報を抽出し、後で詳述する図１９の処理フローに従い、読み出しＱｏＳクラスの選択を行い、ＤＭＵＸ読み出し部５８より対応するパケットをパケットバッファから出力パケットハイウェイへ読み出す。このときＤＭＵＸ読み出し部５８では、各ＤＭＵＸ毎の固定的なタイムスロットを管理しておき、各タイムスロットのタイミングにおいてスケジューリングすべきＤＭＵＸの番号を通知し、対応するＤＭＵＸについて図１９の処理フローを実行する。
【００６３】
図１９の処理フローでは、３つのプロセスが連携して動作する。パケット到着処理プロセスでは、可変長パケットが到着したとき、または前述のアドレス管理ＦＩＦＯ５２において、可変長パケットがＦＩＦＯの先頭に来たとき、対応する可変長パケットのＱｏＳクラスごとにトークン値の加算（ステップ１１００）、および、ウェイト値総和ΣΦi への加算を行う（ステップ１１０２）。またパケット読み出しプロセスでは、前可変長パケットの読み出しが終了し、次の可変長パケットを選択する前、もしくは初期状態において、可変長パケットの選択が行われていないとき、各ＱｏＳ毎のトークン値（ｉ）を比較し、最小トークン値を持つＱｏＳクラスを選択し（ステップ１１０４）、当該ＱｏＳクラスのパケットの読み出しを開始する（ステップ１１０６）。このとき、同一ＱｏＳクラスにキューイングされている他のパケットが無く、キューが空になるときは、ΣΦi からの減算処理を行う（ステップ１１０８）。一方、減算値処理プロセスでは、単位時間毎に、全ＱｏＳクラスの減算値を計算し（ステップ１１１０）、全ＱｏＳクラスのトークン値から減算値の減算を行う（ステップ１１１２）。
【００６４】
図２０は、パケット長を考慮したＱｏＳ制御の第２の例を概念的に示す図である。トークン値（Ｔi ）をトークン値×ΣΦi に置き換え、さらに単位時間毎の減算値としてΦi を使用する。
この手法では、一般に処理時間がかかるΦi ／ΣΦi の除算処理をなくすことができる。但し、ＱｏＳクラスキューの状態を反映するΣΦi の更新が、前述の手法では１単位時間毎に可能であるのに対して、パケットの先頭を読出してトークン値を積みあげるときのみになるため、多少公平性に関して特性的な劣化が生じる。
【００６５】
図２１にフローチャートを示す。パケット到着処理プロセスにおけるトークン値の加算値にパケット長の代わりにパケット長×ΣΦi を用い、また減算値処理プロセスにおいて、減算値をΦi ／ΣΦi の代わりにΦi としている。
図２２は、パケット長を考慮したＱｏＳ制御の第３の例を示す。この手法では、トークン値をトークン値×ΣΦi に置き換える代わりに、ΣΦi の加算をパケット長に相当する回数だけ繰返すことに置き換えている。
【００６６】
トークン回数を管理するカウンタが必要となるため多少複雑になるが、乗算処理をなくすことができるためハード量の削減が図れる。またパケット長に相当する回数分のΣΦi の加算の際に、逐次最新のΣΦi を使用することにより、ＱｏＳクラスキューの状態を反映する頻度が多くなり、公平性に関して特性的な向上が図れる。
【００６７】
図２３にフローチャートを示す。パケット到着処理プロセスにおけるトークン値の加算値にパケット長の代わりにΣΦi を用い、累積パケット長カウンタによって、加算したΣΦi の回数を管理する。また減算値処理プロセスにおいて、累積パケット長カウンタが０になるまで、トークン値のフレームへの加算処理を繰返し、減算値をΦi ／ΣΦi の代わりにΦi としている。
【００６８】
図２４は、最低帯域が保証されさらに余剰帯域の使用が許される最低帯域保証クラスの可変長パケットについてのパケット長を考慮した制御が可能なＱｏＳ制御の一例を概念的に示す。入力された最低帯域保証クラスの可変長パケットについては通常はスイッチ部１４の前段に設けられるポリシング制御部２０において、最低保証帯域を超えて到着したパケットにタギングを行うことにより、帯域保証のパケットとベストエフォート分のパケットが識別される。スイッチ部１４の後段のＱｏＳ制御部５８では到着した可変長パケットを構成する固定長パケットの数をＱｏＳクラス（ｅｘ１６クラス）別にカウンタする。すべてのＱｏＳクラスのそれぞれについて帯域保証クラス用のカウンタとベストエフォートクラス用のカウンタを用意し、最低帯域保証クラスについてはそれらの双方を使用し、ベストエフォートクラスについてはベストエフォートクラスのカウンタのみを使用し、帯域保証クラスについては帯域保証クラスのカウンタのみを使用するようにすることが好ましい。この様にすることにより、システムの柔軟性が向上する。
【００６９】
ここでＱｏＳ制御部５８では、カウンタ値が正の値のものについて、前述した重み付けによる読出し制御を行う。トークン演算のアルゴリズムは前述の３通りのいずれでも良い。但し、この際、可変長パケットのパケット長の代わりに固定長パケットのパケット長を用い、また帯域保証クラスについては設定レートに従う読出しを行う。また帯域保証クラスとベストエフォートクラスからの要求の競合時は単純に帯域保証クラスを高くするかラウンドロビンや予め設定された優先度に応じて読み出す。このようなスケジューリング処理は固定長パケット毎に行い、選択されたＱｏＳクラスのカウンタ値を１減算するとともに、可変長バッファ部６０へ選択されたＱｏＳクラスを通知する。
【００７０】
可変長バッファ部６０では、通知数をＱｏＳクラス毎に計数し、累積数が各キューの先頭のパケット長に達したら、１可変長パケットの読み出しを行なう。
上記の制御により、１ＱｏＳクラス内に帯域保証分とベストエフォート分が含まれる最低帯域保証クラスに対して可変長パケットに対するＱｏＳ制御が可能となる。図６，７を参照して説明した制御のように同一キューにマッピングしてキューしきい値で制御する方法だとベストエフォート分のパケットが使用できるキュー領域は帯域保証クラスが利用できるキュー領域より小さくなるという制限が生じるが、このような問題が解消される。また、単純に１ＱｏＳクラスのキューを帯域保証分とベストエフォート分とで２つに分けると生じるパケットの順序逆転も起きない。
【００７１】
さらに、帯域保証クラスのスケジューリングとベストエフォートクラスのスケジューリングを別々に行うことができるので単純に帯域保証クラスの優先度を高くするような優先制御だけでなく、ラウンドロビンにしたり予め優先度を設定しておくなどより複雑な優先制御が可能となる。
図２５に具体的な構成を示す。ここでは、固定長パケット単位にパケットバッファへのキューイングを管理しているが、連続する固定長パケットを可変長パケットと置き換え、可変長パケットの先頭と末尾を管理し、１可変長パケット分連続的に読み出すことにより、可変長パケットにおいても全く同様に当てはまる。
【００７２】
ＱｏＳスケジューラ６２において、到着した可変長パケットを構成する固定長パケットの数がカウントされる。この際、最低帯域保証クラスについては、当該フレームがタギングされているか否かによって、適合パケット数カウンタにカウントするか、不適合パケット数カウンタにカウントするかに分かれる。前述のように帯域保証クラスおよびベストエフォートクラスについては一方のカウンタのみが使用される。ＱｏＳスケジューラ６２では各カウンタ値が０で無いものについて、予め設定されたレートやウェイト、優先度に応じて、１つのＱｏＳクラスを選択する。選択されたＱｏＳクラスは可変長パケット管理部６４に通知される。可変長パケット管理部６４では、通知された選択ＱｏＳクラス数を管理しており、累積数をパケット長に換算して、各ＱｏＳクラス毎のキューの先頭パケットのパケット長より大きくなった場合には、当該可変長パケットを出力ハイウェイから出力する。
【００７３】
このとき、固定長パケットサイズやフォーマットは、どのようなものでもよく、可変長パケットの先頭と末尾を管理できれば、ここでの固定長パケットにヘッダを付与する必要はない。
図２６は、最低保証帯域クラスの可変長パケットの制御が可能なＱｏＳ制御の他の例の原理を説明する図である。図２６は或るＱｏＳクラスに対するトークン値の動作を示している。ここで、入力された可変長パケットはＱｏＳクラスごとにキューイングされている。Φigは帯域保証クラス用に設定された読出しレート値である。またΦibはベストエフォートクラス用に設定されたウェイト値である。ベストエフォート分を含まない帯域保証クラスのΦibはゼロに、帯域保証分を含まないベストエフォートクラスのΦigはゼロに設定される。最低帯域保証クラスについては、ΦigとΦibにゼロでない値が設定される。
【００７４】
ここでは、１単位時間内にトークン減算処理を帯域保証クラスサイクル用とベストエフォートクラスサイクル用の２回行う。このとき、いずれのＱｏＳクラスにおいても帯域保証クラスのパケットの読み出しが無いときは、ベストエフォートクラスサイクル用のトークン減算処理も行うが、帯域保証クラスの可変長パケットの読み出しがあるときまたは帯域保証クラスの可変長パケットの読み出しが続いているときは、ベストエフォートクラスサイクル用のトークン減算処理を行わない。最低帯域保証クラスのパケットには予め前段のポリシング制御部において、最低保証帯域を超えたフレームにタギングをしておく。帯域保証クラスサイクル用のスケジューリングを行い読み出すべきフームの有無を判定する際、タギングのない最低保証帯域以下のパケットについてのみ読み出すべきパケットが有りとして処理し、タギングがある場合は読み出すべきパケットが無しとして処理する。
【００７５】
もしくは、帯域保証クラスの読み出しパケットの有り無しに関わらず、常にベストエフォートクラスサイクル用のトークン減算処理を行い、ΣΦibの代わりにΣΦiall（アクティブなコネクションについてのΦigとΦibの総和）を使用することもできる。
このようにすれば、可変長パケットの状態のままで、スケジューリングができ、帯域保証クラスのスケジューリングを行ってからベストエフォートクラスのスケジューリングを行うという簡単な制御で最低帯域保証クラスの収容が可能となる。但し、一般にΣΦigとΣΦibは異なる値であるため、前記の３通りのトークン演算アルゴリズムのうち、トークンとしてどちらのクラスにも共通であるパケット長を用いる第１番目の演算アルゴリズムのみが適用できる。
【００７６】
図２７に処理のフローチャートを示す。可変長パケット到着処理プロセスにおいて、帯域保証クラスとベストエフォートクラスで、ΣΦi を各々ΣΦigとΣΦibとして別々に管理する（ステップ１２００）。また同様に減算値更新プロセスにおいても減算値Φi ／ΣΦi の代わりにΦig／ΣΦigとΦib／ΣΦibを別々に管理し（ステップ１２０２）、トークンの減算処理を帯域保証クラスからパケットが読み出されているときと、そうでないときに分けて行う（ステップ１２０４）。また可変長パケット読み出しプロセスにおいて、先に帯域保証クラスのパケットまたはタギングのない最低帯域保証クラスのパケットがキューイングされているキューの中からの可変長パケットの選択を行い（ステップ１２０６）、次にベストエフォートクラスのパケットまたはタギングされている最低帯域保証クラスのパケットがキューイングされているキューの中からの可変長パケットの選択を行う（ステップ１２０８）。またΣΦの減算についても同様に帯域保証クラスとベストエフォートクラスで別々に行う（ステップ１２１０）。なお、図２７に示した例では、帯域保証クラスについては、Φibがゼロに設定され、ベストエフォートクラスについては、Φigがゼロに設定されるものとする。その代わりとして、減算値更新プロセスにおいて、帯域保証クラスについては、Φibの減算を行なわず、ベストエフォートクラスについては、Φigの減算を行なわないようにしても良い。
【００７７】
図２８は、最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御のさらに他の例の原理を説明する図である。図２８は図２６と同様に前述の第１番目の演算アルゴリズムを適用した場合の、或るＱｏＳクラスに対するトークン値の動作を示している。この例では、最低帯域保証クラスのパケットは、帯域保証クラス用とベストエフォートクラス用の２つのスケジューラにより並列に処理する。但し、トークン値はＱｏＳクラス毎のキューの先頭パケットのパケット長に対応する同一のトークン値を使用する。このとき、ベストエフォートクラス用のスケジューラでは、ΣΦibの代わりにΣΦiallを使用する。
【００７８】
最低帯域保証クラスについては、帯域保証クラス用とベストエフォートクラス用の２つのスケジューラによるスケジューリングが行なわれる。それらの読出し処理により、いずれか先に読出しが行われたときは、読出しが行われなかった方の読み出された可変長パケットに対して行われた累積トークン減算値を繰り越し分として、次の可変長パケットのトークン値を計算する際に減算する。
【００７９】
この手法では、帯域保証クラス用とベストエフォートクラス用で別々にトークンの減算処理が必要となるため、ハード規模が増加する。但し、帯域保証クラス用とベストエフォートクラス用を並列に処理できるので、高速なスケジューリングが可能となる。また、ΣΦigとΣΦiallが一致する必要がないので、前述した３つの演算アルゴリズムのいずれもが適用可能である。
【００８０】
図２９にフローチャートを示す。この例では、フレーム到着処理プロセスにおいて、１つのＱｏＳクラスｉについてトークン値を帯域保証クラスとベストエフォートクラスでトークン値（ｉｇ）、トークン値（ｉｂ）として別々に管理する（ステップ１３００）。さらに、減算値更新プロセスにおいて、トークン値（ｉｇ）とトークン値（ｉｂ）からそれぞれΦ(ig)／ΣΦ(ig)とΦ(ib)／ΣΦ(isll)を減算するときに、減算量をそれぞれ繰越分（ｉｇ）と繰越分（ｉｂ）として記憶しておく（ステップ１３０２）。読み出しパケットの選択の際には、可変長パケット読出プロセスにおいて、まず、可変長パケットが存在するすべてのＱｏＳクラスの中からトークン値（ｉｇ）がゼロになっているクラスを選択する（ステップ１３０４）。このとき、帯域保証分を持たないベストエフォートクラスについては、Φigをゼロに設定すれば、ステップ１３０２におけるトークン値（ｉｇ）の減算が実質的に行なわれないので、ここで選択されることはない。次に、可変長パケットが存在するすべてのＱｏＳクラスの中からトークン値（ｉｂ）が最小であるものを選択する（ステップ１３０６）。このとき同様に、ベストエフォート分を持たない帯域保証クラスについては、Φibをゼロに設定すれば、ステップ１３０２におけるトークン値（ｉｂ）の減算が実質的に行なわれないので、ここで選択されることはない。帯域保証分とベストエフォート分を併せ持つ最低帯域保証クラスについては、両者のいずれかとして選択され、選択されなかった方の繰越分を次のパケットの選択に反映させるため、選択されなかった方のトークン値に−（繰越分）を設定する（ステップ１３０８）。
【００８１】
次に、本発明の一実施形態に係るパケット廃棄の手法を説明する。なお、以下の記述において、「可変長パケット」は「フレーム」と、「固定長パケット」は単に「パケット」と称される。本発明において、廃棄はランダムでなく周期的に行い、その周期をキュー長の状態に応じて変えることにより、確率的な廃棄を実現する。また、廃棄を読み出し時に行うことにより、キューの先頭から廃棄することが出来るため、廃棄を早く端末に通知することが出来る。廃棄判定はキューの先頭パケット読み出し時に行う。図３０および式（６）に示すように、キュー長に応じた廃棄確率を決定し、式（７）で決定される周期で廃棄を行う。これにより、長いフレームはそれだけ高い確率で廃棄することが出来る。廃棄時は、１フレーム分のパケットを１パケット時間に廃棄することにより、スループットの低下を防ぐことが出来る。
【００８２】
廃棄確率＝（平均キュー長−ＴＨmin ）／（ＴＨv −ＴＨmin ） …（６）
廃棄周期＝１／（廃棄確率×パケット長） …（７）
具体的な回路構成を図３１に、動作フローを図３２に、動作の一例を図３３に示す。バッファ内のキュー長を管理するキュー長カウンタ６６、設定されたしきい値を保持するしきい値レジスタ６８、設定された読み出し間隔パラメータを保持する読み出し間隔レジスタ７０、読み出し間隔制御に用いるＬＢカウンタ７２、バッファの先頭のフレームのフレーム長を管理するフレーム長カウンタ７４、ＬＢカウンタ動作を制御するカウンタ制御７６、その他演算器より構成される。
【００８３】
フレームの先頭のパケットを読み出す時、平均キュー長としきい値を比較する。平均キュー長がしきい値を越えていない場合はそのまま読み出しを行う。しきい値を越えた場合、しきい値と平均キュー長との差分にフレーム長を掛け合わせた値を、ＬＢカウンタ７２に加算する。そして加算結果が０を越えていた場合、該当フレームに属するパケットを全て廃棄し（具体的な方法は後述）、ＬＢカウンタ値から、読み出し間隔レジスタ７０の値にフレーム長を掛け合わせた値を減算する。加算結果が０を越えていない場合は、そのまま読み出しを行う。ＬＢカウンタに加算する値が大きいほど、カウンタ値が０を越える確率が高くなる。よって本動作により、輻輳度合いとフレーム長に応じた確率でフレームを廃棄することが出来る。
【００８４】
ここで、平均キュー長はその時点での値を用いることも、移動平均を取った値を用いることも可能である。一時的な輻輳ではなく、長期的な輻輳時のみ廃棄制御をかけるため、移動平均を取った値を用いることが有効であるが、バッファを大きく取ることができれば、しきい値を大きく設定し実キュー長がしきい値越えとなった時点で長期輻輳と判断することも可能である。また、読み出し時に廃棄することで、バッファの先頭のフレームに対し廃棄することが出来る。
【００８５】
図３４および図３５に１フレームに属するすべてのパケットの廃棄を１パケット時間内に行なう手法の一例を示す。図の左上に概念的に表されるアドレス管理ＦＩＦＯは、実際には各キューのスタート／エンドポインタ９２とアドレス管理テーブル９４により構成される。アドレス管理テーブル９４には、次のアドレスを示す次アドレス、フレーム最終パケットのアドレスを示すＥＮＤアドレス、キューに次のフレームが存在することを示す次先頭アドレスイネーブル、次のフレームの先頭アドレスを示す次先頭アドレス、フレームの先頭を示すフレーム先頭フラグ、フレーム長のフィールドを有するレコードが格納される。
【００８６】
図３４において、廃棄するフレームを空きアドレスキューにつなぎ替えるため、空きアドレスキューのエンドポインタによって示される最終アドレス（アドレス９）のレコードの次アドレスの値をつなぎ替えるフレームの先頭アドレス（アドレス５）に書き替える（ステップＡ）。そして空きアドレスキューのエンドポインタをつなぎ替えるフレームのＥＮＤアドレス値（アドレス１）に書き替える（ステップＢ）。次に廃棄が行われたキューから廃棄フレームを取り除くため、キューのスタートポインタを次先頭アドレス（アドレス１３）に書き替える（ステップＣ）。以上のようにアドレスリンクを書き替えることにより図３５に示すようになり、１パケット時間内に１フレーム分の廃棄を行うことが出来る。
【００８７】
パケット廃棄方式の他の例として、基本的な考えは前述と同じであるが、廃棄判定は各パケット読み出し毎に行い、廃棄確率は、平均キュー長がしきい値を越えた量のみに比例させ、それに見合った周期で廃棄を行う。パケット毎に廃棄判定を行うため、結果的に長いフレームはそれだけ高い確率で廃棄することが出来る。１パケット廃棄したら同一フレームに属する以降のパケットの読み出し毎に廃棄する。廃棄に廃棄パケット数分の時間掛かるため特性的に前述の手法に劣るが、逆にパケットｂｙパケットの動作のため回路構成が簡単になるため、より高速動作が必要なバッファ制御に適する。
【００８８】
以上の廃棄方式はキュー毎に制御される。また、複数のしきい値を持たせることにより廃棄に対するプライオリティを持たせることが出来る。
このパケット廃棄方式の具体的な構成の例を、図３６に示す。キュー長を管理するキュー長カウンタ７８、設定されたしきい値を保持するしきい値レジスタ８０、設定された読み出し間隔パラメータを保持する読み出し間隔レジスタ８２、読み出し間隔制御に用いるＬＢカウンタ８４、フレーム廃棄中であることを示す廃棄フラグ８６、ＬＢカウンタを制御するカウンタ制御部８８、その他演算器より構成される。各パケットの読み出し時、平均キュー長としきい値を比較する。平均キュー長がしきい値を越えていない場合はそのまま読み出しを行う。しきい値を越えた場合、しきい値とキュー長との差分を、ＬＢカウンタに加算する。そして加算結果が０を越えていた場合、該当パケットを廃棄、廃棄ＬＢカウンタ値から読み出し間隔レジスタ値を減算し、廃棄フラグを立てる。加算結果が０を越えていない場合は、そのまま読み出しを行う。パケット廃棄を行った場合、同一フレームの以降のパケット読み出し時に廃棄を行い、ＬＢカウンタ値に対し、ＬＢしきい値とキュー長との差分値の加算と、カウンタ値から読み出し間隔レジスタ値を減算する。同一フレームの最終になったら、フラグをクリアする。（先頭フレーム到着時、廃棄フラグをクリアしてから廃棄判定をしても良い。）最終パケットは廃棄しないことで、廃棄フレームと次のフレームとを識別させることが出来る。パケット毎に廃棄判定を行うため、廃棄確率はフレームが長いほど高くなる。よって本動作により、輻輳度合いとフレーム長に応じた確率でフレームを廃棄することが出来る。以上の動作フローを図３７に、ＬＢカウンタ動作例を図３８に示す。ここで、平均キュー長はその時点での値を用いることも、移動平均を取った値を用いることも可能である。一時的な輻輳ではなく、長期的な輻輳時のみ廃棄制御をかけるため、移動平均を取った値を用いることが有効であるが、バッファが大きく取れれば、しきい値を大きく設定し実キュー長がしきい値越えとなった時点で長期輻輳と判断することも可能である。また、読み出し時に廃棄することで、バッファの先頭のフレームに対し廃棄することが出来る。パケットの廃棄に１フレーム時間かかるため、前述の方式より特性的には劣化するが、回路構成が簡単になるため、より高速な動作が必要なところに適する。
【００８９】
ＬＢカウンタ制御については、正負を逆転したり、廃棄判定を０でなくしきい値を用いて行っても良い。
可変長パケットであるフレームをスイッチングするパケットスイッチにおいては、１つのフレームを複数の低速回線へマルチキャストする場合に次の様な解決すべき問題がある。図３９に示すように、スイッチ部１６からフレーム組立バッファ２８に１フレーム分のパケットが溜まった後にＤＭＵＸ９０にパケットが移し替えられるが、その移し替えを１パケットづつ行うと、マルチキャストを行う場合、図４０に示すように複数の低速回線に同時に複製するためにはマルチキャスト数分のアドレス更新を１パケット時間内に行う必要があり高速動作には適さない。また図４１に示すように、マルチキャスト用として別のキュー９１を設ける場合、フレーム連続性を保証するためにマルチキャストを行なわないパケットとマルチキャストの複製先が競合しないように制御する必要がある。更に、フレーム長に比例してマルチキャストに時間がかかる問題もある。
【００９０】
そこで、図４２に示すように、フレーム組立てバッファ２８からＤＭＵＸ９０への移動を１パケットずつでなく１フレーム分のパケットをまとめて移動するようにすれば、フレーム組立てバッファ２８での読み出し競合の問題は解消される。１フレーム分のパケットの移動は、以下に説明するように、パケットのデータを実際に移動するのでなく、パケットバッファ内の格納アドレスを移動するようにすれば、１パケット時間内で可能になる。
【００９１】
フレーム単位でのパケットの移動の具体例を図４３，４４を参照して説明する。図の左上に概念的に示されるアドレス管理ＦＩＦＯは、実際には、各キューのスタート／エンドポインタ９２とアドレス管理テーブル９４により構成される。アドレス管理テーブル９４には、次のアドレスを示す次アドレス、フレーム最終パケットのアドレスを示すＥＮＤアドレス、キューに次のフレームが存在することを示す次先頭アドレスイネーブル、次のフレームの先頭アドレスを示す次先頭アドレス、フレームの先頭を示すフレーム先頭フラグ、及びフレーム長のフィールドを有するレコードが格納される。
【００９２】
ここで、図４３において、１フレーム分のパケットがフレーム組立バッファに溜まった場合、まずフレームを出力バッファキューにつなぐために、出力バッファのエンドポインタが示す最終アドレス（アドレス２）のレコードの次アドレスの値を、フレームの先頭アドレス（アドレス５）に書き替える（ステップＡ）。そして出力バッファのエンドポインタを、つなぎ替えるフレームのＥＮＤアドレス値（アドレス１）に書き替える（ステップＢ）。次にフレーム組立キューを更新するために、フレーム組立キューのスタートポインタを次先頭アドレス（アドレス１３）に書き替える（ステップＣ）。以上により、図４４に示すようになり、１パケット時間内にフレーム組立バッファから出力バッファに移動することが出来る。
【００９３】
図４５に本発明におけるマルチキャストの処理を概念的に示す。マルチキャストすべきフレームはまずＤＭＵＸ９０を経てマルチキャストキュー９６に移動される。勿論、この移動もアドレスの書き替えのみによって行なわれる。マルチキャストキュー９６からＤＭＵＸ９０の各出力回線に複製する際、複製フレーム毎に１つのマルチキャストアドレス９８を付与する。そしてアドレスリンクにはマルチキャストアドレス９８をつなぎ変える。これにより、１フレーム分を１パケット時間で仮想的に複製できるため、ユニキャストパケットとの間でフレーム連続性が保証され競合制御が不要になる。同時に複製に掛かる時間が複製数×パケット時間のみで可能となる。
【００９４】
マルチキャスト処理の具体例を図４６〜図５３に示す。図４３，４４の構成に加え、出力バッファは更に複数の出力回線に対するキューを含むので、複数の出力回線へのキューとマルチキャストキュー９６のスタート／エンドアドレスポインタとコネクション管理テーブル１００を用意する。また、アドレス管理テーブル９４には、マルチキャスト識別ビット、マルチキャストコネクションを識別するＣＩＤ、マルチキャストキューからの再配置完了を示す振分完了フラグ、フレームのマルチキャスト出力数を管理するマルチキャスト数カウンタ、及びマルチキャストアドレスに対応するフレームのアドレスを示すフレームアドレスのフィールドが追加される。コネクション管理テーブルには、マルチキャストされるコネクションのＣＩＤが実際の出力回線の番号とともに格納される。図示されている例は、ＣＩＤの２と１がこの順で登録され、それらに対応する出力回線はそれぞれ１と４であることを示す。
【００９５】
マルチキャストフレームのフレーム組立が完了すると、出力バッファではなくマルチキャストキューに移動する（図４６）。出力回線別のキューに同一のアドレスを使用できないため、複製時に新たな空きアドレス（アドレス３，１１）を確保し、そのアドレスをフレームの代理として該当する出力バッファキュー（キュー１，４）につなぎ変える。同時にアドレス管理テーブルのマルチキャストアドレス（アドレス３，１１）に対し、フレームアドレスのフィールドに実際のフレームのスタートアドレス（アドレス５）を、そのアドレスのＥＮＤアドレスのフィールドにフレームのエンドアドレス（アドレス１）を保持する。また、フレームがコピーされる毎にそのアドレスのマルチキャストカウンタをインクリメントし、同一フレームの最終コピー時（コネクション管理テーブルのＥＮＤフラグで識別）に再配置完了フラグを立てる（図４７〜図４９）。
【００９６】
ＤＭＵＸからの読み出し時は、マルチキャストアドレス（アドレス３，１１）のフレームアドレス（アドレス５）からＥＮＤアドレス（アドレス１）までのパケットを読み出す。１フレーム分のパケット読み出し完了後、マルチキャストアドレスを空きアドレスキューに返却し、マルチキャストカウンタをデクリメントする。その結果が０で且つ再配置完了フラグが立っていれば、リンクとポインタの書き換えにより１フレーム分のアドレスを空きアドレスに返却する（図５０〜図５３）。ここで、第一回目のコピーではマルチキャストアドレスを用いずリンクとエンドポインタの書き換えにより再配置することで、制御が複雑になるものの使用アドレスを削減することも出来る。
【００９７】
図５４には、スイッチ１６の入力側および出力側のいずれにも適用可能なＱｏＳ制御の他の例を概念的に示す。
選択部２００は、所定の規則に従って高優先グループに属するＱｏＳクラスの中から１つを選択する。選択部２０２は、所定の規則に従って低優先グループに属するＱｏＳクラスの中から１つを選択する。選択部２０４は選択部２００が選択したＱｏＳクラスおよび選択部２０２が選択したＱｏＳのいずれか一方を選択する。
【００９８】
このＱｏＳ制御は、単純な優先度選択回路のみで実現でき、予め各ＱｏＳクラスにレートや読み出し比を設定して競合制御を行う場合に比べて、ハード規模の削減が可能となる。
このＱｏＳ制御はパケット廃棄などによる品質劣化が少ない入力側に適用可能であるが、品質劣化ポイントでなければ出力側にも適用可能である。
【００９９】
図５５は図５４のＱｏＳ制御を図１のスイッチ１６の入力側の入力バッファ部１２および回線間スケジューラ１４に適用した例を示す。図５５において、入力回線の各々について、入力バッファ部１２はＭ個のＶｏＱ毎にＱｏＳクラス毎のキューを保持している。スケジューリング部１４は全ＶｏＱ×ＱｏＳ個のキューについて、１単位時間には同じＶｏＱを選択しないように競合制御する。このとき、各スケジューリング部１４は、未確定管理部２０６において、確定していないＶｏＱ情報を交換することにより競合制御を実施する。
【０１００】
入力バッファ部１２のＶｏＱ毎のＱｏＳキューに固定長パケットが到着した際、スケジューリング部１４に対して、対応するＶｏＱ番号と当該パケットのＱｏＳクラスが属する優先グループを通知し、スケジューリング部１４の各要求数カウンタ２０８，２１０で要求数を管理する。この際、例えば、帯域保証クラスのパケットは高優先グループとして通知し、ベストエフォートクラスのパケットは低優先グループとして通知する。
【０１０１】
次に１つのスケジューリング部１４内の高優先グループの選択部２１２において、要求カウンタ数が０でないものの中から１つのＶｏＱを選択し、隣接するスケジューリング部１４へは未確定管理部２０６を経由して、確定していないＶｏＱを通知する。未確定ＶｏＱを受信したスケジューリング部１４は未確定ＶｏＱの中から同様の手順で１つのＶｏＱを選択し、順次この操作を繰り返し、全入力回線について高優先グループに対するスケジューリングが完了する。
【０１０２】
次に、高優先グループに対してＶｏＱが選択されなかった入力回線について、選択されなかったＶｏＱを対象として、各スケジューラ部１４の低優先グループ選択部２１４で高優先グループのときと同じ手順でＶｏＱが順次選択される。
以上の処理により全入力回線について、高優先グループまたは低優先グループに対応するユニークなＶｏＱ値が選択される。以上の機能が図５４の選択部２０４に対応する。
【０１０３】
次にスケジューラ部１４は決定したＶｏＱ値、および優先グループを入力バッファ部１２に通知し、入力バッファ部１２では図５６の処理を行い、高優先グループまたは低優先グループの中から１つのＱｏＳキューを選択する。またこのとき、１可変長パケットの連続性を維持するように選択を管理することにより、同一ＱｏＳクラス内のフレームの連続性が保証される。
【０１０４】
図５７は、図５４のＱｏＳ制御を図８のＱｏＳ制御部３０におけるＱｏＳ制御に適用した例を示す。入力バッファ部１２における制御との違いは、高優先グループか低優先グループかの選択を競合制御によって行うのではなく、高優先グループに対応するパケットの有無で判定している。すなわち、図５７のステップ２０００，２００２、および２００４の処理が図５４の選択部２０４，２００、および２０２にそれぞれ相当する。
【０１０５】
図５８は図５４のＱｏＳ制御において、各ＱｏＳクラスを高優先グループおよび低優先グループのいずれかへ割り当てる手法の一例を示す。
図５８に示した例では、帯域保証クラスのキューを高優先グループにマッピングし、ベストエフォートクラスのキューを低優先グループにマッピングする。最低レートまでは帯域保証し、最低レート以上は帯域の余剰がある場合のみ読み出し可能とする最低帯域保証クラスに関しては、高優先グループと低優先グループの両方にマッピングし、帯域保証分の読み出しを高優先グループとして、余剰帯域分の読み出しを低優先グループとして読み出すことにより最低帯域保証クラスのＱｏＳ制御を実現する。
【０１０６】
これにより、単純な優先度選択のみで最低帯域保証クラスの帯域保証分をベストエフォートクラスより優先度を高くし、帯域保証クラスと同等の優先度に設定し、最低帯域保証クラスの余剰帯域分を帯域保証クラスより優先度を低くし、ベストエフォートクラスと同等の優先度に設定できるため、帯域保証クラスやベストエフォートクラスに影響を与えずに最低帯域保証クラスを収容することが可能となる。
【０１０７】
図５９に図５８の手法をスイッチ１６の入力側のＱｏＳ制御に適用した場合の、入力バッファ部１２およびスケジューリング部１４の具体的な回路構成を示す。最低帯域保証クラスを高優先グループ、または低優先グループにマッピングするために、前段のポリシング制御部２２０において、到着するパケットのトラヒックを監視し、予め規定された最低保証レート以下のパケットに対してはタギングを行わず、最低保証レートより上のパケットについてはタギングを行う。
【０１０８】
そしてタギングなしのパケットが到着した際は高優先グループとしてスケジューリング部１４へ通知し、タギングありのパケットが到着した際はスケジューリング部１４へ低優先パケットとして通知する。この際、どちらのパケットも同一のＱｏＳキュー２２２に保持する。図示されていないが、帯域保証クラスおよびベストエフォートクラスのパケットの到着はポリシング制御部２０の処理を経ることなく、それぞれ高優先グループおよび低優先グループとして通知される。
【０１０９】
各スケジューリング部１４において、ＶｏＱ、および優先グループが決定され、入力バッファ部１２に通知されると、当該ＶｏＱに対する通知された優先グループ内のＱｏＳクラス選択部２２４または２２６において、１つのＱｏＳクラスを選択し、対応するＱｏＳキュー２２２から１パケットを読み出す。この際、最低帯域保証クラスについては、高優先グループの中から選択されたとしても低優先グループの中から選択されたとしても、タギングの有無にかかわらず対応するキューの先頭からパケットが読み出される。
【０１１０】
高優先グループ内および低優先グループ内での１つのＱｏＳクラスの選択は、例えば図６０に示すように単純なラウンドロビン方式を適用することができる。ラウンドロビン方式の場合、小さなハードウェアの規模で帯域を各ＱｏＳクラスで公平に配分することができる。しかしながら、ＱｏＳクラス間で到着トラヒック量に偏りがあると、トラヒック量の増加に比例して遅延時間が増加して遅延時間に不公平を生じるという問題がある。
【０１１１】
グループ内での選択をパケットの到着順に行なえば、遅延時間の不公平は解消される。これを実現するためには、例えば、図６１に示すように、ＱｏＳクラス選択部２２４，２２６のキューに格納されるデータに、到着順を示すタイムスタンプを付し、この順で選択すれば良い。図６１において、巡回カウンタ２４０，２４２は各優先グループ内のＱｏＳクラスのパケットの情報を登録する度に１だけインクリメントされ、入力バッファ量に対応するパケット数までカウントしたら０に戻るカウンタであり、このカウンタの値がパケットの情報に付加される。またカウンタ値検索部２４４，２４６もパケットを選択する毎に１づつインクリメントされる内部カウンタを有し、この値に一致する巡回カウンタ値を有する情報を検索する。
【０１１２】
別の方法として、図６２に示すように、それぞれのグループ内において、パケットが到着したＱｏＳクラスの番号をＦＩＦＯ２３０およびＦＩＦＯ２３２に格納する。選択の際に、ＦＩＦＯから読み出された番号に対応するパケットを選択するようにすれば、到着順に選択することができる。
図６３は遅延時間が比較的公平なさらに他のグループ内選択方法を示す。まず、カウンタ２３４により、到着したパケットの数がＱｏＳクラスごとにカウントされる。パケットが選択されるとカウント値がデクリメントされる。一定の観測周期が経過するごとに、選択されずに残ったパケット数がＱｏＳクラスごとにカウンタ２３６に加算される。すなわち、カウンタ２３６では前周期とそれ以前の周期で到着し未だ選択されていないパケットの数がカウントされる。セレクタ２３８による選択の際に、カウンタ２３６の値がすべてゼロであるときは、カウンタ２３４の中でゼロでない値を持つＱｏＳクラスの中からラウンドロビン方式で１つのＱｏＳクラスが選択される。カウンタ２３６の中にゼロでない値を持つＱｏＳクラスがあればそちらを優先してラウンドロビン方式で１つのＱｏＳクラスが選択される。図６３に示した例では、現周期に到着した未選択のパケットをカウントするカウンタ２３４と、前周期およびそれ以前の周期で到着した未選択のパケットをカウントするカウンタ２３６の２組のカウンタが使用されているが、前周期のパケット数と前々周期およびそれ以前の周期のパケット数を別々にカウントするといったように、履歴をさらに細分化してカウントすれば、一層公平性が向上する。
【０１１３】
この手法は到着パケット数をカウントするだけなので、到着パケットごとにタイムスタンプまたはＱｏＳクラスの番号を記憶する手法と比べてハードウェアの量が少なくて済む。
図６４はグループ内選択のさらに他の手法を示す。図６４において、キュー長カウンタ２４０，２４２は各ＱｏＳクラスごとに未選択の固定長パケットのパケット数をカウントする。比較器２４４，２４６はキュー長カウンタ２４０，２４２の中でカウント値が最大のものを選択する。
【０１１４】
キュー長が長いことと到着トラヒック比が高いことは必ずしも一致しないが、ほぼ同様の傾向をもつため、ラウンドロビン方式の場合に比べより公平な遅延特性となることが期待できる。またキュー長はキュー長による廃棄制御等に利用するためのものと共用可能であるため、比較的ハード規模を小さく実現できる。
【０１１５】
【発明の効果】
以上説明したように本発明によれば、高速かつ少ないハードウェア規模で、可変長パケットのＱｏＳ制御、廃棄制御およびマルチキャスト制御を実現する大容量パケットスイッチが提供される。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る大容量パケットスイッチを概念的に示す図である。
【図２】可変長パケットの一例としてのＩＰｖ４のフレーム形式を示す図である。
【図３】固定長パケットの形式の一例を示す図である。
【図４】スイッチ部１６の入力例におけるスケジューリングを実現する具体的な構成を示す図である。
【図５】パイプライン処理によるスケジューリングの一例を示す図である。
【図６】入力側における最低帯域保証クラスのパケットのスケジューリングの一例を示す図である。
【図７】図６のスケジューリング処理のフローチャートである。
【図８】出力バッファ部１８の構成の第１の例を示す図である。
【図９】出力バッファ部１８の構成の第２の例を示す図である。
【図１０】図８の例の詳細な構成を示す図である。
【図１１】図８および図１０の構成において、出力回線がさらに複数の低速回線へ分離される場合を示す図である。
【図１２】図９の構成において、出力回線がさらに複数の低速回線へ分離される場合を示す図である。
【図１３】出力側の処理を考慮した入力側のスケジューラの構成を示す図である。
【図１４】図１３のスケジューラの動作の一例を示す図である。
【図１５】図１３のスケジューラの動作の一例を示す図である。
【図１６】図１３のスケジューラの動作のフローチャートである。
【図１７】本発明における可変長パケットのＱｏＳ制御の第１の例を概念的に示す図である。
【図１８】図１７のＱｏＳ制御を実現する回路構成の一例を示す図である。
【図１９】図１７のＱｏＳ制御の動作のフローチャートである。
【図２０】可変長パケットのＱｏＳ制御の第２の例を概念的に示す図である。
【図２１】図２０のＱｏＳ制御の動作のフローチャートである。
【図２２】可変長パケットのＱｏＳ制御の第３の例を概念的に示す図である。
【図２３】図２２のＱｏＳ制御の動作のフローチャートである。
【図２４】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第１の例を示す図である。
【図２５】図２４のＱｏＳ制御を実現する具体的な構成を示す図である。
【図２６】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第２の例を示す図である。
【図２７】図２６のＱｏＳ制御の動作のフローチャートである。
【図２８】最低帯域保証クラスの可変長パケットの制御が可能なＱｏＳ制御の第３の例を示す図である。
【図２９】図２６のＱｏＳ制御の動作のフローチャートである。
【図３０】本発明のパケット廃棄制御における平均キュー長と廃棄確率の関係を示す図である。
【図３１】本発明のパケット廃棄制御の第１の例の構成を示すブロック図である。
【図３２】図３１の廃棄制御の処理のフローチャートである。
【図３３】図３１の廃棄制御におけるＬＢカウンタの動作の一例を示すグラフである。
【図３４】本発明の廃棄制御の動作の一例を示す図である。
【図３５】本発明の廃棄制御の動作の一例を示す図である。
【図３６】本発明のパケット廃棄制御の第２の例の構成を示すブロック図である。
【図３７】図３６の廃棄制御の処理のフローチャートである。
【図３８】図３６の廃棄制御におけるＬＢカウンタの動作の一例を示す図である。
【図３９】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４０】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４１】可変長パケットのマルチキャスト制御において解決すべき課題を説明する図である。
【図４２】本発明における、フレーム組立てバッファからＤＭＵＸのフレーム単位での移動を概念的に示す図である。
【図４３】フレーム単位での移動の具体例を示す図である。
【図４４】フレーム単位での移動の具体例を示す図である。
【図４５】本発明の一実施例に係るマルチキャスト制御を概念的に示す図である。
【図４６】マルチキャスト制御の具体例を示す図である。
【図４７】マルチキャスト制御の具体例を示す図である。
【図４８】マルチキャスト制御の具体例を示す図である。
【図４９】マルチキャスト制御の具体例を示す図である。
【図５０】マルチキャスト制御の具体例を示す図である。
【図５１】マルチキャスト制御の具体例を示す図である。
【図５２】マルチキャスト制御の具体例を示す図である。
【図５３】マルチキャスト制御の具体例を示す図である。
【図５４】本発明の他のＱｏＳ制御を概念的に示す図である。
【図５５】図５４のＱｏＳ制御をスイッチの入力側に適用した例を示す図である。
【図５６】図５５の回路の動作のフローチャートである。
【図５７】図５４のＱｏＳ制御をスイッチの出力側に適用した例を示す図である。
【図５８】図５４のＱｏＳ制御において各ＱｏＳクラスのアービングの例を示す図である。
【図５９】最低帯域保証クラスに対するＱｏＳ制御を実現する構成の例を示す図である。
【図６０】優先グループ内のＱｏＳクラスの選択をラウンドロビン方式で行なう場合を示す図である。
【図６１】優先グループ内のＱｏＳクラスの選択をタイムスタンプにより行なう場合を示す図である。
【図６２】優先グループ内のＱｏＳクラスの選択を到着順序管理ＦＩＦＯにより行なう場合を示す図である。
【図６３】優先グループ内のＱｏＳクラスの選択を観測周期内パケット数の履歴により行なう場合を示す図である。
【図６４】優先グループ内のＱｏＳクラスの選択をキュー長により行なう場合を示す図である。
【符号の説明】
１０…パケット分割部
１２…入力バッファ部
１４…回線間スケジューラ
１６…スイッチ部
１８…出力バッファ部
Claims (23)
- 複数の入力回線からの可変長パケットを固定長パケットに分割するパケット分割部と、
複数の入力回線のそれぞれに対して設けられ、その各々が、複数の出力回線の各々について、指定可能なＱｏＳ（Quality of Service）クラス数よりも少数の相異なる優先度が与えられたキューを有し、対応する入力回線からの固定長パケットを、出力回線およびＱｏＳクラスに従って該キューのいずれかに登録する複数の入力バッファ部と、
入力バッファ部のキューに登録された固定長パケットを、キューに与えられた前記優先度に従って単位時間内では出力回線が同じである２以上の固定長パケットが読み出されないように読み出すスケジューラと、
スケジューラが読み出した固定長パケットの各々を複数の出力回線のうちの指定された１つにルーチングするスイッチと、
複数の出力回線のそれぞれに対して設けられ、スイッチから出力される固定長パケットからの可変長パケットの組み立ておよびＱｏＳクラスに基づく優先制御を行なうための複数の出力バッファ部とを具備し、
前記スケジューラは前記複数の入力回線の各々に対応させた複数のスケジューラ部からなり、単位時間内で、前記複数の入力バッファ部内のすべてのキューを、キューに与えられた優先度の順、入力回線の所定の順番、および出力回線の所定の順番で調べて、各出力回線へ出力する固定長パケットを該複数のスケジューラ部から１つずつ選択するものであって該複数のスケジューラ部の間で行うパイプライン制御は、１周期に該スケジューラ部の正順および逆順を考慮したパイプライン制御であって、かつ複数のパイプラインのシーケンス順序を入れ替えることによりそのパイプラインと同じパターンが同数現れるように行い、
同一の優先度、同一の入力回線のキューの中から固定長パケットを送出する出力回線を選択するにあたり、可変長パケットを構成する複数の固定長パケットの一部が送出済である出力回線に対応するキュー内の固定長パケットを他に優先して選択することを特徴とするパケットスイッチ。 - 前記入力バッファ部の各々は、各出力回線について第１の優先度のキューおよび第２の優先度のキューを有し、
帯域保証クラスのパケットは第１の優先度のキューに登録され、
ベストエフォートクラスのパケットは第２の優先度のキューに登録され、
最低帯域保証クラスのパケットは第２の優先度のキューに登録され、
第２の優先度のキューは、最低保証帯域を超えて入力された最低帯域保証クラスのパケットとベストエフォートクラスのパケットとを廃棄するための第１の廃棄レベルと、第１の廃棄レベルより高く設定され最低保証帯域内で入力された最低帯域保証クラスのパケットを廃棄するための第２の廃棄レベルとを有する請求項１記載のパケットスイッチ。 - 前記出力バッファ部の各々は、
入力回線の各々について、前記入力バッファ部における各出力回線に対するキューの数と同数のキューを有し、スイッチから出力される固定長パケットを入力回線に応じていずれかのキューに格納することによって固定長パケットから可変長パケットを組み立てる可変長パケット組立てバッファと、
指定可能なＱｏＳクラス数と同数のキューを有し、可変長パケット組立てバッファで組み立てられた可変長パケットをＱｏＳクラスに応じて対応するキューに登録し、パケット長およびＱｏＳクラスに応じて可変長パケットを順次読み出して対応する出力回線へ出力するＱｏＳ制御部とを含む請求項１記載のパケットスイッチ。 - 前記出力バッファ部の各々は、
指定可能なＱｏＳクラス数と同数のキューを有し、スイッチから出力される固定長パケットをＱｏＳクラスに従っていずれかのキューに登録する固定長ベースＱｏＳ制御部と、
入力回線の各々について、指定可能なＱｏＳクラス数と同数のキューを有し、固定長ベースＱｏＳ制御部から出力される固定長パケットを入力回線およびＱｏＳクラスに従って対応するキューに登録して可変長パケットを組み立て、対応する出力回線へ送出する可変長パケット組立てバッファとを含む請求項１記載のパケットスイッチ。 - 前記ＱｏＳ制御部は、
可変長パケットがキューの先頭に達したとき該キューの先頭に達した該可変長パケットのパケット長である第１の値を対応するトークンに加算する手段と、
単位時間が経過するごとにアクティブなＱｏＳクラスのトークンから第２の値を減算する手段と、
出力回線へのパケット送出が可能なとき、アクティブなＱｏＳクラスの中で、対応するトークンが最小もしくは０であるものの可変長パケットの読み出しを開始する手段とを含む請求項３記載のパケットスイッチ。 - 前記第２の値は、アクティブなＱｏＳクラスのウェイトの総和に対する、個々のアクティブなＱｏＳクラスのウェイトの比に対応する値である請求項５記載のパケットスイッチ。
- 前記第１の値は、キューの先頭に達した可変長パケットのパケット長とアクティブなＱｏＳクラスのウェイトの総和との積に対応する値であり、前記第２の値は、個々のアクティブなＱｏＳクラスのウェイトに対応する値である請求項５記載のパケットスイッチ。
- 前記第１の値加算手段は、アクティブなＱｏＳクラスのウェイトの総和を単位時間が経過するごとにトークンに加算し、これをパケット長に対応する回数だけ繰り返すことによって第１の値の加算を達成する請求項７記載のパケットスイッチ。
- 前記ＱｏＳ制御部は、
可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントするカウンタと、
０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、
優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含む請求項３記載のパケットスイッチ。 - 前記ＱｏＳ制御部は、
帯域保証クラスの可変長パケットおよび最低保証帯域内で入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第１のカウンタと、
ベストエフォートクラスの可変長パケットおよび最低保証帯域を超えて入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第２のカウンタと、
第１のカウンタについて０でないカウント値を有するＱｏＳクラスおよび第２のカウンタについて０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、
優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含む請求項３記載のパケットスイッチ。 - 前記第２の値は、帯域保証分の第２の値とベストエフォート分の第２の値とを含み、
前記第２の値減算手段は、帯域保証クラスからのパケットの読出しがあるときトークンから帯域保証分の第２の値のみを減算し、帯域保証クラスからの読出しがないときトークンから帯域保証分の第２の値とベストエフォート分の第２の値を減算する請求項５記載のパケットスイッチ。 - 前記トークンは、帯域保証分のトークンとベストエフォート分のトークンを含み、前記第２の値は、帯域保証分の第２の値とベストエフォート分の第２の値を含み、
前記第２の値減算手段は、帯域保証分のトークンとベストエフォート分のトークンとから帯域保証分の第２の値とベストエフォート分の第２の値をそれぞれ減算し、
帯域保証分のトークンおよびベストエフォート分のトークンのいずれか一方に基づき読み出すパケットが選ばれたとき、選ばれたパケットについて他方のトークンに対して行なわれた減算量が次のパケットのトークンに繰り越される請求項５記載のパケットスイッチ。 - 請求項１に記載のパケットスイッチの前記出力バッファ部におけるスケジューリング装置であって、
指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、
可変長パケットがキューの先頭に達したとき該キューの先頭に達した該可変長パケットのパケット長である第１の値を対応するトークンに加算する手段と、
単位時間が経過するごとにアクティブなＱｏＳクラスのトークンから第２の値を減算する手段と、
出力回線へのパケット送出が可能なとき、アクティブなＱｏＳクラスの中で、対応するトークンが最小もしくは０であるものの可変長パケットの読み出しを開始する手段とを具備するスケジューリング装置。 - 前記第２の値は、アクティブなＱｏＳクラスのウェイトの総和に対する、個々のアクティブなＱｏＳクラスのウェイトの比に対応する値である請求項１３記載のスケジューリング装置。
- 前記第１の値は、キューの先頭に達した可変長パケットのパケット長とアクティブなＱｏＳクラスのウェイトの総和との積に対応する値であり、前記第２の値は、個々のアクティブなＱｏＳクラスのウェイトに対応する値である請求項１３記載のスケジューリング装置。
- 前記第１の値加算手段は、アクティブなＱｏＳクラスのウェイトの総和を単位時間が経過するごとにトークンに加算し、これをパケット長に対応する回数だけ繰り返すことによって前記第１の値の加算を達成する請求項１５記載のスケジューリング装置。
- 請求項１に記載のパケットスイッチの前記出力バッファ部におけるスケジューリング装置であって、
指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、
可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントするカウンタと、
０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、
優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含むスケジューリング装置。 - 請求項１に記載のパケットスイッチの前記出力バッファ部におけるスケジューリング装置であって、
指定可能なＱｏＳクラス数と同数のキューであって、可変長パケットをＱｏＳクラスに応じてそれぞれに登録し得るものと、
帯域保証クラスの可変長パケットおよび最低保証帯域内で入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第１のカウンタと、
ベストエフォートクラスの可変長パケットおよび最低保証帯域を超えて入力された最低帯域保証クラスの可変長パケットの固定長パケット数をＱｏＳクラスごとにカウントする第２のカウンタと、
第１のカウンタについて０でないカウント値を有するＱｏＳクラスおよび第２のカウンタについて０でないカウント値を有するＱｏＳクラスを対象としてパケット長一定として優先して出力すべきパケットのＱｏＳクラスを決定して通知する優先制御部と、
優先制御部からの通知をＱｏＳクラスごとにカウントし、カウント値が対応するキューの先頭の可変長パケットのパケット長に相当する値に達したＱｏＳクラスについて、可変長パケットを読み出して出力回線へ送出する可変長パケット管理部とを含むスケジューリング装置。 - 前記第２の値は、帯域保証分の第２の値とベストエフォート分の第２の値とを含み、
前記第２の値減算手段は、帯域保証クラスからのパケットの読出しがあるときトークンから帯域保証分の第２の値のみを減算し、帯域保証クラスからの読出しがないときトークンから帯域保証分の第２の値とベストエフォート分の第２の値を減算する請求項１３記載のスケジューリング装置。 - 前記トークンは、帯域保証分のトークンとベストエフォート分のトークンを含み、前記第２の値は、帯域保証分の第２の値とベストエフォート分の第２の値を含み、
前記第２の値減算手段は、帯域保証分のトークンとベストエフォート分のトークンとから帯域保証分の第２の値とベストエフォート分の第２の値をそれぞれ減算し、
帯域保証分のトークンおよびベストエフォート分のトークンのいずれか一方に基づき読み出すパケットが選ばれたとき、選ばれたパケットについて他方のトークンに対して行なわれた減算量が次のパケットのトークンに繰り越される請求項１３記載のスケジューリング装置。 - 前記入力バッファ部および出力バッファ部の少なくとも一方のバッファ内に格納されているパケットの量のその閾値との差分にバッファの先頭に存在する可変長パケットのパケット長を乗じてその結果を出力する演算回路と、
カウンタと、
演算回路の演算結果をカウンタに加算する加算回路と、
カウンタの値が所定値を超えているときバッファの先頭に存在する可変長パケットを一度に廃棄し、前記パケット長に所定値を乗じた値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路をさらに有する請求項１記載のパケットスイッチ。 - 前記入力バッファ部および出力バッファ部の少なくとも一方のバッファ内に格納されているパケットの量のその閾値との差分を出力する演算回路と、
カウンタと、
演算回路の演算結果をカウンタに加算する加算回路と、
カウンタの値が所定値を超えているときバッファの先頭に存在する固定長パケットを廃棄し、所定値をカウンタから減算する制御回路とを具備する可変長パケットの廃棄制御回路をさらに有する請求項１記載のパケットスイッチ。 - 前記複数の出力回線毎の出力バッファ部のバッファにおいて、
バッファに格納されている、マルチキャスト制御すべき可変長パケットのアドレスを登録するマルチキャストキューと、
複数の出力回線のそれぞれに対して設けられた複数の出力バッファキューと、
バッファに格納されている可変長パケットのアドレスを管理するアドレス管理テーブルと、
マルチキャスト制御すべき可変長パケットのアドレスがマルチキャストキューに登録されたとき、該可変長パケットのアドレスを含むレコードをその出力先の数だけアドレス管理テーブルに格納し、その出力先に対応する出力バッファキューに、該レコードのアドレスをそれぞれ登録する制御手段とを具備するマルチキャスト制御回路を有する請求項１記載のパケットスイッチ。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000124667A JP4879382B2 (ja) | 2000-03-22 | 2000-04-25 | パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 |
| US09/813,226 US7016366B2 (en) | 2000-03-22 | 2001-03-20 | Packet switch that converts variable length packets to fixed length packets and uses fewer QOS categories in the input queues that in the outout queues |
| EP20060000474 EP1646192B1 (en) | 2000-03-22 | 2001-03-22 | Packet switch, scheduling device, drop control circuit, multicast control circuit and QOS control device |
| EP01106433A EP1137227A3 (en) | 2000-03-22 | 2001-03-22 | Packet switch, scheduling device, drop control circuit, multicast control circuit and Qos control device |
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000080383 | 2000-03-22 | ||
| JP2000080383 | 2000-03-22 | ||
| JP2000-80383 | 2000-03-22 | ||
| JP2000124667A JP4879382B2 (ja) | 2000-03-22 | 2000-04-25 | パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001339427A JP2001339427A (ja) | 2001-12-07 |
| JP4879382B2 true JP4879382B2 (ja) | 2012-02-22 |
Family
ID=26588072
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000124667A Expired - Fee Related JP4879382B2 (ja) | 2000-03-22 | 2000-04-25 | パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US7016366B2 (ja) |
| EP (2) | EP1137227A3 (ja) |
| JP (1) | JP4879382B2 (ja) |
Families Citing this family (111)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3475900B2 (ja) | 2000-03-29 | 2003-12-10 | 日本電気株式会社 | 調停方式及びそれを用いたアービタ回路 |
| US6845100B1 (en) * | 2000-08-28 | 2005-01-18 | Nokia Mobile Phones Ltd. | Basic QoS mechanisms for wireless transmission of IP traffic |
| JP3443093B2 (ja) * | 2000-12-27 | 2003-09-02 | 株式会社東芝 | ディジタル記録再生装置 |
| DE60008265T2 (de) * | 2000-12-28 | 2004-07-22 | Alcatel | Methode zur Bandbreitenzuteilung für Netzwerkendgeräte in einem Kommunikationsnetzwerk mit einen Medienzugriffssteuerungsgerät zur Ausführung dieser Methode |
| US7042883B2 (en) * | 2001-01-03 | 2006-05-09 | Juniper Networks, Inc. | Pipeline scheduler with fairness and minimum bandwidth guarantee |
| US7486686B2 (en) * | 2001-02-26 | 2009-02-03 | Vitesse Semiconductor Corporation | Method and apparatus for scheduling data on a medium |
| WO2002079758A1 (en) * | 2001-03-29 | 2002-10-10 | Circadiant Systems, Inc. | Error function analysis of optical components with uncertainty ranges |
| US7627870B1 (en) * | 2001-04-28 | 2009-12-01 | Cisco Technology, Inc. | Method and apparatus for a data structure comprising a hierarchy of queues or linked list data structures |
| JP3705353B2 (ja) * | 2001-05-22 | 2005-10-12 | 日本電気株式会社 | パケットスケジューリング装置及び方法 |
| KR20040003052A (ko) * | 2001-06-05 | 2004-01-07 | 노오텔 네트웍스 리미티드 | 상대적 스루풋 산포도에 기초하여 이동 단말기로의 데이타패킷 송신을 스케쥴링하는 다중 임계 스케쥴러 |
| US7724760B2 (en) * | 2001-07-05 | 2010-05-25 | Broadcom Corporation | Method and apparatus for bandwidth guarantee and overload protection in a network switch |
| JP3622843B2 (ja) * | 2001-07-11 | 2005-02-23 | 日本電気株式会社 | 可変長パケットスイッチ方法及びシステム |
| US20030014532A1 (en) * | 2001-07-16 | 2003-01-16 | Shean-Guang Chang | Method and apparatus for multicast support |
| US7158480B1 (en) * | 2001-07-30 | 2007-01-02 | Nortel Networks Limited | Feedback output queuing system, apparatus, and method |
| US8271672B1 (en) | 2001-08-31 | 2012-09-18 | Juniper Networks, Inc. | Guaranteed bandwidth memory apparatus and method |
| US7089257B2 (en) * | 2001-09-27 | 2006-08-08 | Qualcomm, Inc. | Method and system for providing a unified data exchange and storage format |
| GB2381406A (en) * | 2001-10-24 | 2003-04-30 | Ipwireless Inc | Packet data queuing and processing |
| JP2003134160A (ja) * | 2001-10-25 | 2003-05-09 | Matsushita Electric Ind Co Ltd | 帯域保証システム、中継装置、及び、ネットワーク管理サーバ |
| US7698454B1 (en) * | 2001-11-26 | 2010-04-13 | Juniper Networks, Inc. | Interfacing with streams of differing speeds |
| US7023856B1 (en) * | 2001-12-11 | 2006-04-04 | Riverstone Networks, Inc. | Method and system for providing differentiated service on a per virtual circuit basis within a packet-based switch/router |
| US7212528B2 (en) | 2001-12-21 | 2007-05-01 | Alcatel Canada Inc. | System and method for reassembling packets in a network element |
| CA2440236C (en) * | 2001-12-28 | 2008-02-12 | Nokia Corporation | Packet scheduling method and apparatus |
| CA2369432A1 (en) | 2002-01-24 | 2003-07-24 | Alcatel Canada Inc. | System and method for reassembling packets in a network element |
| EP1331770A1 (en) * | 2002-01-24 | 2003-07-30 | Alcatel Canada Inc. | System and method for reassembling packets in a network element |
| US7085849B1 (en) * | 2002-03-08 | 2006-08-01 | Juniper Networks, Inc. | Scheduler systems and methods for transmit system interfaces |
| US7680043B2 (en) * | 2002-03-20 | 2010-03-16 | International Business Machines Corporation | Network processor having fast flow queue disable process |
| GB0207507D0 (en) * | 2002-03-28 | 2002-05-08 | Marconi Corp Plc | An apparatus for providing communications network resource |
| US7151777B2 (en) * | 2002-04-04 | 2006-12-19 | Fujitsu Limited | Crosspoint switch having multicast functionality |
| TWI244349B (en) * | 2002-05-01 | 2005-11-21 | Interdigital Tech Corp | Point to multi-point services using high speed shared channels in wireless communication systems |
| CN103596270B (zh) * | 2002-05-01 | 2017-04-19 | 美商内数位科技公司 | 无线通信中使用的用户设备以及网络装置 |
| JP3857183B2 (ja) * | 2002-05-24 | 2006-12-13 | 株式会社日立コミュニケーションテクノロジー | アドレス変換機能を備えたパケット転送装置 |
| CN1656754A (zh) * | 2002-05-30 | 2005-08-17 | 松下电器产业株式会社 | 分组传送电路和分组传送方法 |
| US7292580B2 (en) * | 2002-06-10 | 2007-11-06 | Lsi Corporation | Method and system for guaranteeing quality of service in a multi-plane cell switch |
| CA2393373A1 (en) | 2002-07-15 | 2004-01-15 | Anthony Gerkis | Apparatus, system and method for the transmission of data with different qos attributes. |
| US7633971B1 (en) * | 2002-09-13 | 2009-12-15 | Ceterus Networks, Inc. | Method and system for transport of packet-based datastreams over frame-based transport systems employing physically diverse transmission channels |
| FI112421B (fi) * | 2002-10-29 | 2003-11-28 | Tellabs Oy | Menetelmä ja laitteisto siirtoyhteyskapasiteetin vuorottamiseksi pakettikytkentäisten tietoliikennevoiden kesken |
| EP1416681A1 (en) * | 2002-10-29 | 2004-05-06 | Alcatel | Method for traffic engineering and ingress router adapted to perform such a method |
| US8520520B2 (en) * | 2002-11-06 | 2013-08-27 | Avaya, Inc. | System and method for per flow guaranteed throughput, multiple TCP flow bandwidth provisioning, and elimination of packet drops for transmission control protocol (TCP) and TCP-friendly protocols |
| US20040090964A1 (en) * | 2002-11-07 | 2004-05-13 | Coke Reed | Means and apparatus for a scaleable congestion free switching system with intelligent control II |
| US7599287B2 (en) * | 2002-11-15 | 2009-10-06 | Cisco Technology, Inc. | Tokens in token buckets maintained among primary and secondary storages |
| US7304942B1 (en) * | 2002-11-15 | 2007-12-04 | Cisco Technology, Inc. | Methods and apparatus for maintaining statistic counters and updating a secondary counter storage via a queue for reducing or eliminating overflow of the counters |
| US7307949B1 (en) * | 2002-11-19 | 2007-12-11 | Juniper Networks, Inc. | Hierarchical policers for enforcing differentiated traffic behavior |
| JP3643827B2 (ja) * | 2002-12-17 | 2005-04-27 | 株式会社半導体理工学研究センター | ルータ装置とその出力ポート回路及びその制御方法 |
| KR100564743B1 (ko) * | 2002-12-18 | 2006-03-27 | 한국전자통신연구원 | 다기능 스위치 패브릭 장치 및 그 제어 방법 |
| US20060129525A1 (en) * | 2002-12-19 | 2006-06-15 | Edwin Rijpkema | Combined best effort and contention free guaranteed throughput data scheduling |
| JPWO2004066570A1 (ja) * | 2003-01-17 | 2006-05-18 | 富士通株式会社 | ネットワークスイッチ装置およびネットワークスイッチ方法 |
| US20040156381A1 (en) * | 2003-02-10 | 2004-08-12 | Fischer Michael Andrew | Partial queuing using an interface with bounded latency |
| DE10308954A1 (de) * | 2003-02-28 | 2004-09-09 | Siemens Ag | Übertragung von Daten in einem schaltbaren Datennetz |
| CN1300714C (zh) * | 2003-03-10 | 2007-02-14 | 华为技术有限公司 | 对数据通信中交换芯片外挂存储器优化管理的方法 |
| FI115100B (fi) | 2003-10-14 | 2005-02-28 | Tellabs Oy | Menetelmä ja laitteisto ruuhkanhallinnan sekä siirtoyhteyskapasiteetin vuorottamisen ohjaamiseksi pakettikytkentäisessä tietoliikenteessä |
| EP1683310A1 (en) * | 2003-10-31 | 2006-07-26 | Koninklijke Philips Electronics N.V. | Integrated circuit and method for avoiding starvation of data |
| WO2005048614A1 (fr) * | 2003-11-14 | 2005-05-26 | Zte Corporation | Procede de programmation de paquets pour systeme de communication sans fil |
| JP2005204002A (ja) * | 2004-01-15 | 2005-07-28 | Fujitsu Ltd | パケット中継装置 |
| US7304944B2 (en) * | 2004-05-03 | 2007-12-04 | Lucent Technologies Inc. | Unified scheduling and queueing architecture for a multiservice switch |
| JP4632245B2 (ja) * | 2005-02-23 | 2011-02-16 | 株式会社エヌ・ティ・ティ・ドコモ | 送信局、移動通信システムおよび送信電力制御方法 |
| JP3961000B2 (ja) * | 2005-05-26 | 2007-08-15 | 株式会社日立コミュニケーションテクノロジー | パケット転送装置及びネットワークシステム |
| WO2007002034A2 (en) * | 2005-06-20 | 2007-01-04 | Comcast Cable Holdings, Llc | Method and system of managing and allocating communication related resources |
| JP4524656B2 (ja) * | 2005-08-04 | 2010-08-18 | ソニー株式会社 | 情報処理装置および方法、並びにプログラム |
| US9521584B2 (en) * | 2005-10-17 | 2016-12-13 | Qualcomm Incorporated | Method and apparatus for managing data flow through a mesh network |
| US8730982B2 (en) * | 2005-11-10 | 2014-05-20 | Broadcom Corporation | Scheduling of data transmission with minimum and maximum shaping of flows in a network device |
| JP4648833B2 (ja) * | 2005-12-28 | 2011-03-09 | 富士通株式会社 | 帯域管理装置 |
| US20070165647A1 (en) * | 2006-01-19 | 2007-07-19 | Tellabs Operations, Inc. | Apparatus, method, and computer program for data packet scheduling |
| US8018845B2 (en) * | 2006-01-25 | 2011-09-13 | Cisco Technology, Inc | Sampling rate-limited traffic |
| WO2007099644A1 (ja) * | 2006-03-03 | 2007-09-07 | Hitachi, Ltd. | クロスバスイッチ |
| JP4659657B2 (ja) * | 2006-03-28 | 2011-03-30 | 富士通株式会社 | フレーム多重装置 |
| US8255599B2 (en) * | 2006-03-28 | 2012-08-28 | Integrated Device Technology Inc. | Packets transfer device having data absorbing buffers with elastic buffer capacities |
| DE102006015239B3 (de) * | 2006-03-30 | 2007-08-23 | Siemens Ag | Netzzugangssteuerung mit zusätzlicher Verkehrsklasse in einem Kommunikationsnetz |
| US20080123649A1 (en) * | 2006-07-20 | 2008-05-29 | Via Technologies, Inc. | Systems and methods for broadcast storm control |
| US8077611B2 (en) * | 2006-07-27 | 2011-12-13 | Cisco Technology, Inc. | Multilevel coupled policer |
| US7899079B2 (en) * | 2006-08-24 | 2011-03-01 | Futurewei Technologies, Inc. | System for managing reserved bits in a variable-length message and optimizing message decoding utilizing the same |
| JP4701152B2 (ja) * | 2006-10-20 | 2011-06-15 | 富士通株式会社 | データ中継装置、データ中継方法およびデータ中継プログラム |
| US7697435B1 (en) * | 2007-02-02 | 2010-04-13 | Sprint Communications Company L.P. | Dynamic backhaul delay determination |
| JP4899961B2 (ja) * | 2007-03-19 | 2012-03-21 | 富士通株式会社 | 通信装置および出力制御方法 |
| US7710953B2 (en) * | 2007-03-30 | 2010-05-04 | Alcatel-Lucent Usa Inc. | Method and apparatus for operating fast switches using slow schedulers |
| US9209982B2 (en) * | 2007-05-18 | 2015-12-08 | Cisco Technology, Inc. | Charging for network services based on delivered quality of service |
| US8284792B2 (en) * | 2007-06-01 | 2012-10-09 | Apple Inc. | Buffer minimization in interface controller |
| KR101075724B1 (ko) * | 2007-07-06 | 2011-10-21 | 삼성전자주식회사 | 통신 시스템에서 패킷 전송 속도 제한 장치 및 방법 |
| US20100195492A1 (en) * | 2007-07-23 | 2010-08-05 | Janos Harmatos | Controlling Traffic in a Packet Switched Communications Network |
| US7889739B2 (en) * | 2007-10-22 | 2011-02-15 | Verizon Patent And Licensing Inc. | Label and exp field based MPLS network device |
| US8045563B2 (en) * | 2007-12-27 | 2011-10-25 | Cellco Partnership | Dynamically adjusted credit based round robin scheduler |
| US9013999B1 (en) * | 2008-01-02 | 2015-04-21 | Marvell International Ltd. | Method and apparatus for egress jitter pacer |
| US20090232160A1 (en) * | 2008-03-17 | 2009-09-17 | Nokia Corporation | Bandwidth Requests of Scheduling Services |
| JP5428203B2 (ja) * | 2008-05-30 | 2014-02-26 | 富士通株式会社 | データ出力装置および通信装置ならびにスイッチ装置 |
| US8468426B2 (en) * | 2008-07-02 | 2013-06-18 | Apple Inc. | Multimedia-aware quality-of-service and error correction provisioning |
| JP2008295070A (ja) * | 2008-07-03 | 2008-12-04 | Ntt Docomo Inc | 適応無線パラメータ制御方法、ＱｏＳ制御装置、基地局及び無線通信システム |
| US7800519B2 (en) * | 2008-09-30 | 2010-09-21 | Apple Inc. | Method and apparatus for compressing and decompressing data |
| GB2464310B (en) | 2008-10-10 | 2012-10-17 | Micron Technology Inc | Switching device |
| IL201774A0 (en) * | 2009-10-27 | 2010-06-16 | Eci Telecom Ltd | Technique of throughput control for packer switches |
| US20110194426A1 (en) * | 2010-02-09 | 2011-08-11 | Chien Fang | Hierarchical queuing and scheduling |
| US8773992B2 (en) | 2010-10-11 | 2014-07-08 | At&T Intellectual Property I, L.P. | Methods and apparatus for hierarchical routing in communication networks |
| GB201101709D0 (en) | 2011-02-01 | 2011-03-16 | Transpacket As | A method and a node arrangement for optimizing traffic processing in integrated hybrid networks |
| CN102118314A (zh) * | 2011-02-28 | 2011-07-06 | 华为技术有限公司 | 流量管理的方法和管理装置 |
| JP5682391B2 (ja) * | 2011-03-22 | 2015-03-11 | 富士通株式会社 | データ転送装置、並列計算機システムおよびデータ転送装置の制御方法 |
| US9258248B2 (en) * | 2011-04-01 | 2016-02-09 | Alcatel Lucent | Energy-efficient network device with coordinated scheduling and processor rate control |
| JP5416168B2 (ja) * | 2011-05-19 | 2014-02-12 | 富士通テレコムネットワークス株式会社 | 通信装置 |
| GB201111106D0 (en) * | 2011-06-30 | 2011-08-10 | Xelerated Ab | Method, network device, computer program and computer program product for communication queue state |
| US8908711B2 (en) * | 2011-11-01 | 2014-12-09 | Hewlett-Packard Development Company, L.P. | Target issue intervals |
| US8879571B2 (en) * | 2011-11-01 | 2014-11-04 | Hewlett-Packard Development Company, L.P. | Delays based on packet sizes |
| CN102377682B (zh) * | 2011-12-12 | 2014-07-23 | 西安电子科技大学 | 基于定长单元存储变长分组的队列管理方法及设备 |
| WO2014017069A1 (ja) * | 2012-07-24 | 2014-01-30 | パナソニック株式会社 | バスシステムおよび中継器 |
| US8867559B2 (en) * | 2012-09-27 | 2014-10-21 | Intel Corporation | Managing starvation and congestion in a two-dimensional network having flow control |
| JP6127857B2 (ja) * | 2013-09-17 | 2017-05-17 | 富士通株式会社 | トラフィック制御装置 |
| JP2016208241A (ja) * | 2015-04-21 | 2016-12-08 | 富士通株式会社 | 伝送装置及びパケット制御方法 |
| KR102492234B1 (ko) * | 2016-02-16 | 2023-01-27 | 주식회사 쏠리드 | 분산 안테나 시스템, 이의 프레임 처리 방법, 및 이의 혼잡 회피 방법 |
| US10587526B2 (en) * | 2016-05-30 | 2020-03-10 | Walmart Apollo, Llc | Federated scheme for coordinating throttled network data transfer in a multi-host scenario |
| US10826715B2 (en) * | 2016-12-02 | 2020-11-03 | Datalogic Ip Tech S.R.L. | Simple device replacement in a Profinet IO conformance class A (CCA) network through ubiquitous computing paradigm and combining a token ring approach with a ubicomp paradigm to prevent real-time performance drop |
| JP2018132189A (ja) * | 2017-02-14 | 2018-08-23 | イートン インテリジェント パワー リミテッド | 流体制御システムのための制御システムネットワークアーキテクチャ |
| US11051319B2 (en) * | 2018-09-04 | 2021-06-29 | Qualcomm Incorporated | Techniques for low latency communications in wireless local area networks |
| US11599644B2 (en) | 2019-05-17 | 2023-03-07 | Walmart Apollo, Llc | Blocking insecure code with locking |
| JP7652582B2 (ja) | 2021-02-17 | 2025-03-27 | 日本放送協会 | ネットワークスイッチおよびプログラム |
| US20230344774A1 (en) * | 2022-04-21 | 2023-10-26 | Verizon Patent And Licensing Inc. | User plane congestion control service |
Family Cites Families (23)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1995003657A1 (fr) | 1993-07-21 | 1995-02-02 | Fujitsu Limited | Central mta |
| JP3601078B2 (ja) * | 1993-08-05 | 2004-12-15 | 富士通株式会社 | ルータ、フレームリレー交換機、及びフレームリレー優先通信方式 |
| JP3354689B2 (ja) | 1994-02-28 | 2002-12-09 | 富士通株式会社 | Ａｔｍ交換機、交換機及びそのスイッチングパス設定方法 |
| EP0706297A1 (en) * | 1994-10-07 | 1996-04-10 | International Business Machines Corporation | Method for operating traffic congestion control in a data communication network and system for implementing said method |
| CA2150967C (en) * | 1994-12-22 | 2001-04-03 | Jon C. R. Bennett | Method and a scheduler for controlling when a server provides service with rate control to an entity |
| JP2856104B2 (ja) * | 1995-04-18 | 1999-02-10 | 日本電気株式会社 | Ａｔｍスイッチ |
| US5809024A (en) * | 1995-07-12 | 1998-09-15 | Bay Networks, Inc. | Memory architecture for a local area network module in an ATM switch |
| JPH09116551A (ja) * | 1995-10-18 | 1997-05-02 | Toshiba Corp | データパケット転送方法及びデータパケット転送装置 |
| JPH09321768A (ja) * | 1996-05-28 | 1997-12-12 | Matsushita Electric Ind Co Ltd | Ａｔｍ交換機 |
| JP3537991B2 (ja) | 1996-05-29 | 2004-06-14 | 日本電信電話株式会社 | Ａｔｍセル伝送装置 |
| JPH1075251A (ja) * | 1996-08-29 | 1998-03-17 | Mitsubishi Electric Corp | Ａｔｍ交換装置 |
| JP3435293B2 (ja) * | 1996-09-10 | 2003-08-11 | 株式会社東芝 | パケットスケジューリング装置及びパケット転送方法 |
| JPH10126419A (ja) * | 1996-10-23 | 1998-05-15 | Nec Corp | Ａｔｍ交換機システム |
| JPH1141241A (ja) | 1997-07-18 | 1999-02-12 | Hitachi Ltd | Ａｔｍスイッチ及びそのセル出力優先制御方法 |
| JP3382517B2 (ja) | 1997-08-04 | 2003-03-04 | 日本電信電話株式会社 | 優先制御回路 |
| US6072772A (en) * | 1998-01-12 | 2000-06-06 | Cabletron Systems, Inc. | Method for providing bandwidth and delay guarantees in a crossbar switch with speedup |
| JP3011172B2 (ja) * | 1998-01-28 | 2000-02-21 | 日本電気株式会社 | Ａｔｍ交換機及びそのスイッチ制御方法並びにその制御プログラムを記録した記録媒体 |
| US6044061A (en) * | 1998-03-10 | 2000-03-28 | Cabletron Systems, Inc. | Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch |
| US6160812A (en) * | 1998-05-04 | 2000-12-12 | Cabletron Systems, Inc. | Method and apparatus for supplying requests to a scheduler in an input buffered multiport switch |
| US6052368A (en) * | 1998-05-22 | 2000-04-18 | Cabletron Systems, Inc. | Method and apparatus for forwarding variable-length packets between channel-specific packet processors and a crossbar of a multiport switch |
| JP3506612B2 (ja) * | 1998-08-31 | 2004-03-15 | 富士通株式会社 | スケジューリング制御装置 |
| JP3704438B2 (ja) * | 1998-12-09 | 2005-10-12 | 株式会社日立製作所 | 可変長パケット通信装置 |
| JP3732989B2 (ja) * | 2000-01-12 | 2006-01-11 | 富士通株式会社 | パケットスイッチ装置及びスケジューリング制御方法 |
-
2000
- 2000-04-25 JP JP2000124667A patent/JP4879382B2/ja not_active Expired - Fee Related
-
2001
- 2001-03-20 US US09/813,226 patent/US7016366B2/en not_active Expired - Fee Related
- 2001-03-22 EP EP01106433A patent/EP1137227A3/en not_active Withdrawn
- 2001-03-22 EP EP20060000474 patent/EP1646192B1/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US20010033581A1 (en) | 2001-10-25 |
| EP1646192A2 (en) | 2006-04-12 |
| EP1646192A3 (en) | 2007-10-31 |
| EP1646192B1 (en) | 2015-05-20 |
| JP2001339427A (ja) | 2001-12-07 |
| EP1137227A2 (en) | 2001-09-26 |
| US7016366B2 (en) | 2006-03-21 |
| EP1137227A3 (en) | 2004-10-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4879382B2 (ja) | パケットスイッチ、スケジューリング装置、廃棄制御回路、マルチキャスト制御回路、およびＱｏＳ制御装置 | |
| JP3732989B2 (ja) | パケットスイッチ装置及びスケジューリング制御方法 | |
| US8189597B2 (en) | Pipeline scheduler with fairness and minimum bandwidth guarantee | |
| JP4070610B2 (ja) | データ・ストリーム・プロセッサにおけるデータ・ストリームの操作 | |
| US5278828A (en) | Method and system for managing queued cells | |
| US7457297B2 (en) | Methods and apparatus for differentiated services over a packet-based network | |
| AU736406B2 (en) | Method for providing bandwidth and delay guarantees in a crossbar switch with speedup | |
| US7177317B2 (en) | Flexible scheduler in an asynchronous transfer mode (ATM) switch | |
| KR100933917B1 (ko) | 네트워크 스위치에서의 대역폭 보장 및 과부하 보호 방법및 장치 | |
| JP3435293B2 (ja) | パケットスケジューリング装置及びパケット転送方法 | |
| US7649882B2 (en) | Multicast scheduling and replication in switches | |
| EP0872988A2 (en) | A method for supporting per-connection queuing for feedback-controlled traffic | |
| US7113510B2 (en) | Hardware self-sorting scheduling queue | |
| US7580355B2 (en) | Method of performing weighted round-robin queue scheduling using a dynamic link list and structure for implementing same | |
| JP4163044B2 (ja) | 帯域制御方法およびその帯域制御装置 | |
| US6246687B1 (en) | Network switching system supporting guaranteed data rates | |
| CA2462793C (en) | Distributed transmission of traffic streams in communication networks | |
| Hu et al. | Feedback-based scheduling for load-balanced two-stage switches | |
| JP4072315B2 (ja) | パケットスイッチ | |
| HUP0203928A2 (en) | Method and system for controlling transmission of packets in computer networks | |
| Benet et al. | Providing in-network support to coflow scheduling | |
| KR100369562B1 (ko) | 고속 통합 서비스망에서 ｗｆｑ의 에뮬레이션을 통한 공정패킷 스케쥴링 방법 및 그 공정 패킷 스케쥴러 | |
| US20070133561A1 (en) | Apparatus and method for performing packet scheduling using adaptation round robin | |
| Prasanth et al. | Performance analysis of buffered crossbar switch scheduling algorithms | |
| JP2000165447A (ja) | 電気通信網においてデータパケットをスケジューリングする方法およびシステム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20070312 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20090202 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20090616 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090817 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090908 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20091202 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20091216 |
|
| A912 | Re-examination (zenchi) completed and case transferred to appeal board |
Free format text: JAPANESE INTERMEDIATE CODE: A912 Effective date: 20100108 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20110927 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20111130 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20141209 Year of fee payment: 3 |
|
| LAPS | Cancellation because of no payment of annual fees |