JP5604919B2 - Packet transfer apparatus and packet transfer method - Google Patents
Packet transfer apparatus and packet transfer method Download PDFInfo
- Publication number
- JP5604919B2 JP5604919B2 JP2010063206A JP2010063206A JP5604919B2 JP 5604919 B2 JP5604919 B2 JP 5604919B2 JP 2010063206 A JP2010063206 A JP 2010063206A JP 2010063206 A JP2010063206 A JP 2010063206A JP 5604919 B2 JP5604919 B2 JP 5604919B2
- Authority
- JP
- Japan
- Prior art keywords
- packet
- flow
- output
- token
- priority
- 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
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
- Communication Control (AREA)
Description
本発明は、パケット転送装置およびパケット転送方法に関する。 The present invention relates to a packet transfer apparatus and a packet transfer method.
従来、パケット通信の技術分野においては、パケットが伝送される複数のフローの合流地点にパケット転送装置を設けることが知られている。パケット転送装置は、複数のフローを流れるパケットの出力順序を制御しながら出力回路に転送することにより、出力回路のトラフィックを制御する。 Conventionally, in the technical field of packet communication, it is known to provide a packet transfer device at a confluence of a plurality of flows where packets are transmitted. The packet transfer device controls the traffic of the output circuit by transferring it to the output circuit while controlling the output order of the packets flowing through the plurality of flows.
また、パケット転送装置のパケット転送技術としてトークンバケット方式が知られている。トークンバケット方式は、複数のフローを流れるパケットをパケットバッファにいったん格納し、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を用いてパケットを出力する。 Further, a token bucket method is known as a packet transfer technique for a packet transfer apparatus. In the token bucket method, packets flowing through a plurality of flows are temporarily stored in a packet buffer, and a packet is stored using a token value that is information used to determine whether or not to permit output of the packet stored in the packet buffer. Output.
図８は、トークンバケット方式を説明するための図である。図８において横軸は時間を示し、縦軸は記憶部に記憶されているトークン値を示す。トークンバケット方式では、複数のフローに対応してトークン値が記憶される記憶部を有する。トークンバケット方式では、記憶部に記憶されたトークン値に、あらかじめ設定された周期（以下、「トークン追加周期」という。）で所定のトークン値（以下、「追加トークン値」という。）を加算する（図８の（ａ）参照）。また、トークンバケット方式では、記憶部に記憶されているトークン値が正または出力パケット長以上である場合にパケットの出力許可を行う。また、トークンバケット方式では、パケットバッファからパケットが出力されたら、パケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する（図８の（ｂ）参照）。なお図８の例は、トークン値が正の場合にパケットの出力許可を行う例である。また、トークンバケット方式では、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値（以下、「Max Token」という。）を超過したら、超過した分のトークン値を廃棄する（図８の（ｃ）参照）。 FIG. 8 is a diagram for explaining the token bucket method. In FIG. 8, the horizontal axis indicates time, and the vertical axis indicates token values stored in the storage unit. The token bucket method has a storage unit that stores token values corresponding to a plurality of flows. In the token bucket method, a predetermined token value (hereinafter referred to as “additional token value”) is added to a token value stored in the storage unit at a preset period (hereinafter referred to as “token addition period”). (See FIG. 8A). In the token bucket method, packet output is permitted when the token value stored in the storage unit is positive or longer than the output packet length. In the token bucket method, when a packet is output from the packet buffer, the token value corresponding to the output packet length is subtracted from the token value stored in the storage unit corresponding to the flow from which the packet is output ((( b)). Note that the example of FIG. 8 is an example of permitting packet output when the token value is positive. Also, in the token bucket method, if each token value stored in the storage unit corresponding to a plurality of flows exceeds a preset upper limit value (hereinafter referred to as “Max Token”), the excess tokens The value is discarded (see (c) of FIG. 8).
トークンバケット方式によって導かれるシェーピングレート（Shaping Rate：以下、「Sh_R」という。） は、トークン追加周期と、追加トークン値とによって以下のように表される。
Sh_R [bps(bits per second)]＝追加トークン値[byte]×8／トークン追加周期[s(second)]
なお、Sh_Rとは、フローごとのパケットの出力帯域である。例えば、追加トークン値が40,000[byte]、トークン追加周期が32[us]（=32×10^−6 [s]）の場合、Sh_Rは10G[bps]（=40,000 [byte]×8／32×10^−6[s]）となる。
The shaping rate (Shaping Rate: hereinafter referred to as “Sh_R”) derived by the token bucket method is expressed as follows by the token addition period and the additional token value.
Sh_R [bps (bits per second)] = additional token value [byte] x 8 / token addition period [s (second)]
Note that Sh_R is an output bandwidth of a packet for each flow. For example, if the additional token value is 40,000 [byte] and the token addition period is 32 [us] (= 32 × 10 ^ −6 [s]), Sh_R is 10G [bps] (= 40,000 [byte] × 8/32 × 10 ^ −6 [s]).
また、パケット転送装置では、トークンバケット方式とラウンドロビン（Round Robin：以下、「RR」という。）方式との組み合わせにより、複数のフローからのパケットの出力順序を制御することが知られている。RR方式とは、複数のフローを順番に選択しながら、選択されたフローのパケットバッファに格納されたパケットを順次出力する方式である。 Further, it is known that a packet transfer apparatus controls the output order of packets from a plurality of flows by a combination of a token bucket method and a round robin (hereinafter referred to as “RR”) method. The RR method is a method of sequentially outputting packets stored in a packet buffer of a selected flow while sequentially selecting a plurality of flows.
図９は、トークンバケット方式とRR方式との組み合わせを用いたパケット出力を説明するための図である。フロー♯１〜フロー♯ｎを流れるパケット♯１〜パケット♯ｎは、パケットバッファ♯１〜パケットバッファ♯ｎにそれぞれ格納される。なおｎは２以上の自然数である。ここで、フロー♯１〜フロー♯ｎのうち、記憶部に記憶されたトークン値が正であり、かつパケットバッファにパケットが格納されているフローが順次選択され、選択されたフローのパケットバッファに格納されたパケットが出力回路へ出力される。なお、フロー♯１〜フロー♯ｎそれぞれのSh_Rの総和ΣSh_Rは、出力回線のワイヤレート以下である。
FIG. 9 is a diagram for explaining packet output using a combination of the token bucket scheme and the RR scheme.
なお、複数のフローのパケットの出力帯域を管理する方法としては、ＷＲＲ(Weighted Round Robin)という技術も知られている。ＷＲＲは、トークンの代わりに重み（Weight）をフローごとに与える。また、ＷＲＲでは、あるフローが読み出し権利を得たら重みに応じた量を読み出した後、次のフローに読み出し権利を渡す制御を行う。例えばパケットの出力帯域=10G[bps]であり、重み=1のフローが1本のみである場合、そのフローは10G[bps]の性能が得られる。また、パケットの出力帯域=10G[bps]であり、重み=1のフローがもう1本存在すれば、各フローはそれぞれ5G[bps]の性能が得られる。ここで、一方のフローにパケットが入力されない場合、他方のフローが10G[bps]の出力帯域を占有することになるが、出力されたパケットを受信する装置が5G[bps]の受信能力しか無ければパケットは廃棄される。そこでもしパケットの出力帯域の上限設定が必要な場合、各フローにシェーパの設定を行う。 A technique called WRR (Weighted Round Robin) is also known as a method for managing output bands of packets of a plurality of flows. WRR gives weight for each flow instead of tokens. In WRR, when a certain flow obtains the right to read, an amount corresponding to the weight is read, and then the right to read is transferred to the next flow. For example, when the output bandwidth of a packet is 10 G [bps] and there is only one flow with a weight = 1, the flow can obtain a performance of 10 G [bps]. If the output bandwidth of the packet is 10 G [bps] and there is another flow with weight = 1, each flow can obtain a performance of 5 G [bps]. Here, if no packet is input to one flow, the other flow will occupy the output bandwidth of 10G [bps], but the device that receives the output packet has only 5G [bps] reception capability. The packet is discarded. Therefore, if it is necessary to set the upper limit of the output bandwidth of the packet, the shaper is set for each flow.
ところで、従来技術では、トークン値の廃棄の発生を抑制する目的で、パケットバッファにパケットが格納されているフローのMax Tokenを、パケットバッファにパケットが格納されていないフローのMax Tokenより大きく設定することが知られている。例えば従来技術は、パケットバッファにパケットが格納されていないフローのMax Token＝追加トークン値×1とし、パケットバッファにパケットが格納されているフローのMax Token=追加トークン値×nとする。ここでnは、トークン値が廃棄されない程度に大きく設定する値である。 By the way, in the prior art, in order to suppress the occurrence of token value discarding, the Max Token of the flow in which the packet is stored in the packet buffer is set larger than the Max Token of the flow in which the packet is not stored in the packet buffer. It is known. For example, in the prior art, Max Token of a flow in which no packet is stored in the packet buffer = addition token value × 1, and Max Token of a flow in which a packet is stored in the packet buffer = addition token value × n. Here, n is a value that is set so large that the token value is not discarded.
しかしながら、従来技術は、フローの数にかかわらずMax Tokenの増大を抑制することについては考慮されていない。 However, the conventional technology does not consider the suppression of the increase in Max Token regardless of the number of flows.
すなわち、従来技術によれば、フロー数の増大にしたがって記憶部に記憶されているトークン値の最大値が大きくなる場合がある。以下この点について説明する。図１０，図１１は、従来技術のパケット転送装置のトークン値の遷移モデルを示す図である。図１０のトークン値の遷移モデルは、３フローを収容したパケット転送装置の一例である。また、図１１のトークン値の遷移モデルは、全体の帯域は図１０の場合と変えずに２フロー増加したパケット転送装置の一例である。図１０と図１１において、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図１０と図１１において、複数のトークン追加周期を時間軸に沿って周期（Ａ）〜周期（Ｆ）という。 That is, according to the conventional technique, the maximum value of the token value stored in the storage unit may increase as the number of flows increases. This point will be described below. 10 and 11 are diagrams showing a token value transition model of a conventional packet transfer apparatus. The token value transition model in FIG. 10 is an example of a packet transfer apparatus accommodating three flows. The token value transition model in FIG. 11 is an example of a packet transfer apparatus in which the entire bandwidth is increased by two flows without changing from the case of FIG. 10 and 11, a period during which no packet is stored in the packet buffer of each flow is denoted by α, and a period during which the packet is stored in the packet buffer is denoted by β. 10 and 11, the plurality of token addition periods are referred to as period (A) to period (F) along the time axis.
図１０の周期（Ａ）ではフロー♯１とフロー♯２のパケットバッファにパケットが格納されていないので、フロー♯５のパケットバッファからパケットが出力される（図１０の（ａ）参照）。続いて周期（Ｂ）に入ると各フローの記憶部にトークン値が加算される（図１０の（ｂ）参照）。なおフロー♯１およびフロー♯２のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期（Ｂ）ではフロー♯１、フロー♯２およびフロー♯５のパケットバッファにパケットが格納されているから、フロー♯１、フロー♯２、フロー♯５の順にパケットが出力される（図１０の（ｃ）参照）。また、周期（Ｂ）においてパケットを出力した後、フロー♯１とフロー♯２のトークン値は負になるのに対して、フロー♯５のトークン値は正であるから、フロー♯５からパケットが出力される（図１０の（ｄ）参照）。続いて周期（Ｃ）に入ると各フローの記憶部にトークン値が加算される（図１０の（ｅ）参照）。周期（Ｃ）ではフロー♯１およびフロー♯２のトークン値が「０」つまり正ではないから、フロー♯１およびフロー♯２からはパケットが出力されず、フロー♯５からパケットが出力される（図１０の（ｆ）参照）。図１０の周期（Ｄ）以降の処理は図１０の周期（Ｂ）および周期（Ｃ）と同様であるから、説明を省略する。
In the period (A) of FIG. 10, since packets are not stored in the packet buffers of
次に、図１１の周期（Ａ）は図１０の場合と同様であるから説明を省略する。これに対して、図１１の周期（Ｂ）では、フロー♯３とフロー♯４が追加されてフロー数が多くなっているから、フロー♯１〜フロー♯４の順にパケットが出力され（図１１の（ａ）参照）、フロー♯５からはパケットが出力されない。この状態で周期（Ｃ）に入ると各フローの記憶部にトークン値が加算される（図１１の（ｂ）参照）。その結果、図１０のフロー♯５と図１１のフロー♯５を比較すると、フロー数が多い図１０のフロー♯５の記憶部に記憶されるトークン値の最大値が、図１０の場合と比べて大きくなる。なお、図１１の周期（Ｃ）の以後の処理は図１０の周期（Ｂ）および周期（Ｃ）と同様であるから、説明を省略する。
Next, the cycle (A) in FIG. 11 is the same as that in FIG. On the other hand, in the cycle (B) of FIG. 11, the flow # 3 and the flow # 4 are added and the number of flows is increased, so packets are output in the order of the
このように、RR方式を用いてパケットを出力するフローを順次選択する場合、フローの数が多くなるにしたがって、あるフローのパケットを出力する処理の待ち時間が長くなる。待ち時間の間はトークン追加周期がくるたびに記憶部にトークン値が加算される。一方、待ち時間の間はパケットが出力されないから、記憶部に記憶されているトークン値の減算は行われない。したがって、フローの数が多くなると、記憶部に記憶されるトークン値の最大値は大きくなる。トークン値の最大値が大きくなると、トークン値がMax Tokenを超えてトークン値の廃棄が発生するおそれが増大する。パケットバッファにパケットが格納されているフローに対してトークン値の廃棄が頻繁に発生すると、パケットの出力帯域の劣化につながるので好ましくない。一方、トークン値の廃棄を抑制するためにMax Tokenを大きく設定することも考えられるが、これは回路規模の増大を招くので好ましくない。 Thus, when sequentially selecting flows that output packets using the RR method, the waiting time for processing to output packets of a certain flow increases as the number of flows increases. During the waiting time, the token value is added to the storage unit every time a token addition period comes. On the other hand, since no packet is output during the waiting time, the token value stored in the storage unit is not subtracted. Therefore, as the number of flows increases, the maximum token value stored in the storage unit increases. When the maximum value of the token value becomes large, the possibility that the token value exceeds Max Token and the token value is discarded increases. If the token value is frequently discarded for the flow in which the packet is stored in the packet buffer, it is not preferable because the output band of the packet is deteriorated. On the other hand, it is conceivable to set Max Token large in order to suppress the discarding of the token value, but this is not preferable because it increases the circuit scale.
開示の技術は、上記に鑑みてなされたものであって、フローの数にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができるパケット転送装置およびパケット転送方法を提供することを目的とする。 The disclosed technique has been made in view of the above, and can suppress an increase in Max Token regardless of the number of flows, and can suppress occurrence of token value discard and a packet transfer method. The purpose is to provide.
本願の開示するパケット転送装置は、一つの態様において、パケットを伝送する複数のフローを流れるパケットをそれぞれ複数のフローに対応して格納するパケットバッファを有する。また、パケット転送装置は、パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を複数のフローに対応して記憶する記憶部を有する。また、パケット転送装置は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するトークン演算部を有する。トークン演算部は、パケットバッファからパケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。また、トークン演算部は、複数のフローに対応して記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する。また、パケット転送装置は、複数のフローごとにパケットバッファにパケットが格納されているか否かを検出するパケット監視部を有する。また、パケット転送装置は、パケット監視部で検出されたパケットの格納の有無およびトークン演算部によるトークン値の廃棄の有無に応じて、複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部を有する。また、パケット転送装置は、優先制御信号生成部で設定された複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部を有する。 In one aspect, a packet transfer device disclosed in the present application includes a packet buffer that stores packets flowing through a plurality of flows that transmit packets, corresponding to the plurality of flows, respectively. The packet transfer apparatus also includes a storage unit that stores token values, which are information used to determine whether or not to permit output of the packet stored in the packet buffer, corresponding to a plurality of flows. In addition, the packet transfer apparatus includes a token calculation unit that adds a predetermined token value to each of the token values stored in the storage unit corresponding to a plurality of flows at a preset period. The token calculation unit subtracts the token value corresponding to the output packet length from the token value stored in the storage unit corresponding to the flow in which the packet is output from the packet buffer. The token calculation unit discards the excess token value when each of the token values stored in the storage unit corresponding to a plurality of flows exceeds a preset upper limit value. The packet transfer apparatus also includes a packet monitoring unit that detects whether or not a packet is stored in the packet buffer for each of a plurality of flows. In addition, the packet transfer apparatus sets the priority of the packet output of a plurality of flows as high priority or low priority depending on whether the packet detected by the packet monitoring unit is stored and whether the token value is discarded by the token calculation unit. A priority control signal generation unit that is set every time. In addition, the packet transfer apparatus includes an output flow selection unit that sequentially selects a flow for outputting packets in accordance with the packet output priority of the plurality of flows set by the priority control signal generation unit.
本願の開示するパケット転送装置の一つの態様によれば、フローの数の多少にかかわらずMax Tokenの増大を抑制し、かつトークン値の廃棄の発生を抑制することができる。 According to one aspect of the packet transfer apparatus disclosed in the present application, it is possible to suppress an increase in Max Token regardless of the number of flows, and to suppress occurrence of token value discarding.
以下に、本願の開示するパケット転送装置およびパケット転送方法の実施例を図面に基づいて詳細に説明する。なお、この実施例により開示技術が限定されるものではない。 Embodiments of a packet transfer apparatus and a packet transfer method disclosed in the present application will be described below in detail with reference to the drawings. The disclosed technology is not limited by this embodiment.
図１は、実施例にかかるパケット転送装置の全体構成を示す図である。本実施例のパケット転送装置１００は、パケットバッファ１２０と、記憶部１４０と、トークン演算部１６０と、パケット監視部１８０と、優先制御信号生成部２００と、出力フロー選択部２２０とを有する。
FIG. 1 is a diagram illustrating the overall configuration of the packet transfer apparatus according to the embodiment. The
パケットバッファ１２０は、パケットバッファ１２０−１〜パケットバッファ１２０−ｎを有する。パケットバッファ１２０−１〜パケットバッファ１２０−ｎはそれぞれ、パケットを伝送するフロー♯１〜フロー♯ｎに対応して設けられる。パケットバッファ１２０−１〜パケットバッファ１２０−ｎには、フロー♯１〜フロー♯ｎを流れるパケットがそれぞれ格納される。
The
記憶部１４０は、記憶部１４０−１〜記憶部１４０−ｎを有する。記憶部１４０−１〜記憶部１４０−ｎはそれぞれ、フロー♯１〜フロー♯ｎに対応して設けられる。記憶部１４０−１〜記憶部１４０−ｎには、それぞれトークン値が記憶される。トークン値は、パケットバッファ１２０−１〜パケットバッファ１２０−ｎに格納されたパケットの出力を許可するか否かを判別するのに用いる情報である。
The
トークン演算部１６０は、トークンバケット方式にしたがって、記憶部１４０−１〜記憶部１４０−ｎに記憶されているトークン値に、トークン追加周期で追加トークン値を加算する。また、トークン演算部１６０は、記憶部１４０−１〜記憶部１４０−ｎのうちパケットバッファからパケットが出力されたフローに対応する記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する。さらに、トークン演算部１６０は、記憶部１４０−１〜記憶部１４０−ｎごとに、記憶されたトークン値が正か負かを判別する。記憶部１４０−１〜記憶部１４０−ｎごとのトークン値の正負の情報は、トークン情報として、優先制御信号生成部２００と出力フロー選択部２２０に出力される。また、トークン演算部１６０は、フロー♯１〜フロー♯ｎに対応して記憶部１４０−１〜記憶部１４０−ｎに記憶されたトークン値があらかじめ設定されたMax Tokenを超過したら超過した分のトークン値を廃棄する。記憶部１４０−１〜記憶部１４０−ｎごとのトークン値の廃棄の有無の情報は、トークン廃棄情報として、優先制御信号生成部２００に出力される。
The
パケット監視部１８０は、フロー♯１〜フロー♯ｎからパケットが入力されたら、パケットバッファ１２０−１〜パケットバッファ１２０−ｎのうち、パケットが入力されたフローに対応するパケットバッファにパケットを格納する。また、パケット監視部１８０は、パケットが格納されたパケットバッファの総パケット数の加算を行う。また、パケット監視部１８０は、パケットバッファ１２０−１〜パケットバッファ１２０−ｎからパケットが出力されたら、パケットが出力されたパケットバッファの総パケット数の減算を行う。さらに、パケット監視部１８０は、パケットバッファ１２０−１〜パケットバッファ１２０−ｎそれぞれの総パケット数を監視することにより、パケットバッファにパケットが格納されているか否かを検出する。パケットバッファ１２０−１〜パケットバッファ１２０−ｎごとのパケットが格納されているか否かの情報は、パケット有無情報として、優先制御信号生成部２００と出力フロー選択部２２０に出力される。
When a packet is input from
優先制御信号生成部２００には、トークン演算部１６０から出力されたトークン廃棄情報およびトークン情報と、パケット監視部１８０から出力されたパケット有無情報と、出力フロー選択部２２０から出力されたスキップ情報とが入力される。優先制御信号生成部２００は、入力された各情報に基づいて、フロー♯１〜フロー♯ｎのパケット出力の優先度を高優先度または低優先度に設定する。フロー♯１〜フロー♯ｎごとのパケット出力の優先度は、優先情報として出力フロー選択部２２０に出力される。優先制御信号生成部２００の詳細は後述する。
The priority control
出力フロー選択部２２０は、優先制御信号生成部２００から出力されたフロー♯１〜フロー♯ｎごとのパケット出力の優先情報に応じて、パケットを出力するフローを順次選択する。より具体的には、出力フロー選択部２２０は、フロー♯１〜フロー♯ｎを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。出力フロー選択部２２０は、パケットバッファにパケットが格納されていないフローまたは記憶部のトークン値が負のフローをスキップしながらパケットを出力するフローを順次選択する。フロー♯１〜フロー♯ｎごとのスキップの発生の有無の情報は、スキップ情報として、優先制御信号生成部２００に出力される。また、フロー♯１〜フロー♯ｎのうち、どのフローからパケットが出力されたかという情報は、出力フロー情報として、パケットバッファ１２０、トークン演算部１６０、およびパケット監視部１８０に出力される。
The output
次に、優先制御信号生成部２００の詳細を説明する。図２は、優先制御信号生成部２００の詳細構成を示す図である。優先制御信号生成部２００は、選択回路２０２−１〜選択回路２０２−ｎと、ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎと、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎとを有する。選択回路２０２−１〜選択回路２０２−ｎはそれぞれ、フロー♯１〜フロー♯ｎに対応して設けられる。ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎはそれぞれ、フロー♯１〜フロー♯ｎに対応して設けられる。ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎはそれぞれ、フロー♯１〜フロー♯ｎに対応して設けられる。
Next, details of the priority control
ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのトークン廃棄情報のうち、対応するフローのトークン廃棄情報が入力される。トークン廃棄情報は、トークン値の廃棄が発生した場合には「１」、トークン値の廃棄が発生しなかった場合には「０」という論理値でａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎに入力される。
Of the token discard information of
また、ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。つまり、パケット有無情報は、フローのパケットが存在した場合には「１」、フローのパケットが存在しない場合には「０」という論理値でａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎに入力される。
Also, the packet presence / absence information of the corresponding flow among the packet presence / absence information of the
また、ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎはそれぞれ、入力されたトークン廃棄情報とパケット有無情報に応じた論理値を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。具体的には、ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎはそれぞれ、入力されたトークン廃棄情報とパケット有無情報がともに「１」の場合には「１」を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。また、ａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎはそれぞれ、入力されたトークン廃棄情報とパケット有無情報の少なくとも一方が「０」の場合には「０」を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。 The AND circuits 204a-1 to 204a-n output logical values corresponding to the input token discard information and packet presence / absence information to the corresponding selection circuits 202-1 to 202-n, respectively. Specifically, each of the AND circuits 204a-1 to 204a-n sets “1” when the input token discard information and the packet presence / absence information are both “1”, and the corresponding selection circuit 202-1. To the selection circuit 202-n. Each of the AND circuits 204a-1 to 204a-n sets “0” when at least one of the input token discard information and packet presence / absence information is “0”, and selects the corresponding selection circuit 202-1. The data is output to the selection circuit 202-n.
一方、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのトークン情報のうち、対応するフローのトークン情報が入力される。トークン情報は、記憶部のトークン値が正の場合は「１」、記憶部のトークン値が負の場合は「０」という論理値でａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎに入力される。
On the other hand, the token information of the corresponding flow among the token information of
また、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのスキップ情報のうち、対応するフローのスキップ情報が入力される。スキップ情報は、フローのパケット出力処理がスキップされた場合には「１」、フローのパケット出力処理がスキップされなかった場合には「０」という論理値でａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎに入力される。さらに、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのパケット有無情報のうち、対応するフローのパケット有無情報が論理反転されて入力される。つまり、フローのパケットが存在しない場合には「１」、フローのパケットが存在する場合には「０」という論理値でａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎに入力される。
The skip information of the corresponding flow among the skip information of the
ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報に応じた論理値を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。具体的には、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報がともに「１」の場合には「１」を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。また、ａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎはそれぞれ、入力されたトークン情報とスキップ情報とパケット有無情報のいずれかが「０」の場合には「０」を、対応する選択回路２０２−１〜選択回路２０２−ｎに出力する。
The AND
選択回路２０２−１〜選択回路２０２−ｎはそれぞれ、対応するａｎｄ回路２０４ａ−１〜ａｎｄ回路２０４ａ−ｎおよびａｎｄ回路２０４ｂ−１〜ａｎｄ回路２０４ｂ−ｎから入力された論理値に応じた論理値を優先情報として出力する。例えば選択回路２０２−１は、ａｎｄ回路２０４ａ−１から出力された論理値が「１」で、ａｎｄ回路２０４ｂ−１から出力された論理値が「０」の場合は、フロー♯１の優先度を高優先度に設定する論理値「１」を優先情報として出力する。一方、選択回路２０２−１は、ａｎｄ回路２０４ａ−１から出力された論理値が「０」で、ａｎｄ回路２０４ｂ−１から出力された論理値が「１」の場合は、フロー♯１の優先度を低優先度に設定する論理値「０」を優先情報として出力する。選択回路２０２−２〜選択回路２０２−ｎについても同様である。
The selection circuits 202-1 to 202-n are respectively logical values corresponding to the logical values input from the corresponding AND circuits 204a-1 to 204a-n and AND
次に、出力フロー選択部２２０の詳細を説明する。図３は、出力フロー選択部２２０の詳細構成を示す図である。出力フロー選択部２２０は、ストリクトプライオリティ（Strict Priority：以下「SP」という。）回路２２２と、RR回路２２４ａと、RR回路２２４ｂを有する。また、出力フロー選択部２２０は、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎと、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎとを有する。また、出力フロー選択部２２０は、出力フロー保持回路２２８と、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎを有する。
Next, details of the output
出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎの優先情報のうち、対応するフローの優先情報が入力される。優先情報は、フローの優先度が高優先度の場合には「１」、フローの優先度が低優先度の場合には「０」の論理値で出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎに入力される。
The priority information of the corresponding flow among the priority information of the
また、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。パケット有無情報は、パケットバッファにパケットが格納されている場合には「１」、パケットバッファにパケットが格納されていない場合には「０」の論理値で出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎに入力される。
In addition, the token information of the corresponding flow among the token information of the
出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎはそれぞれ、入力された優先情報とトークン情報とパケット有無情報に応じた論理値を、RR回路２２４ａに出力する。具体的には、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の全ての論理値が「１」の場合には論理値「１」を出力する。また、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎはそれぞれ、入力された優先情報とトークン情報とパケット有無情報の少なくとも１つの論理値が「０」の場合には論理値「０」を出力する。
The output and
一方、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのトークン情報のうち、対応するフローのトークン情報が入力される。また、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎにはそれぞれ、フロー♯１〜フロー♯ｎのパケット有無情報のうち、対応するフローのパケット有無情報が入力される。
On the other hand, the token information of the corresponding flow among the token information of the
出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎはそれぞれ、入力されたトークン情報とパケット有無情報に応じた論理値を、RR回路２２４ｂに出力する。具体的には、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎはそれぞれ、入力されたトークン情報とパケット有無情報の論理値がともに「１」の場合には論理値「１」を出力する。また、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎはそれぞれ、入力されたトークン情報とパケット有無情報の少なくとも一方の論理値が「０」の場合には論理値「０」を出力する。
Each of the output and
RR回路２２４ａは、フロー♯１〜フロー♯ｎのうち、出力用ａｎｄ回路２２６ａ−１〜出力用ａｎｄ回路２２６ａ−ｎからの出力論理値が「１」である出力用ａｎｄ回路に対応するフローを順次選択してSP回路２２２に出力する。RR回路２２４ｂは、フロー♯１〜フロー♯ｎのうち、出力用ａｎｄ回路２２６ｂ−１〜出力用ａｎｄ回路２２６ｂ−ｎからの出力論理値が「１」である出力用ａｎｄ回路に対応するフローを順次選択してSP回路２２２に出力する。
The RR circuit 224a has a flow corresponding to the output and circuit whose output logical value is “1” from the output and
SP回路２２２は、RR回路２２４ａからの出力がある場合、RR回路２２４ａからの出力を出力フロー情報として出力する。つまり、SP回路２２２は、高優先度に設定されたフローがあるときには、高優先度のフローからのパケット出力を優先する。一方、SP回路２２２は、RR回路２２４ａからの出力がない場合、RR回路２２４ｂからの出力を出力フロー情報として出力する。このように、出力フロー選択部２２０は、フロー♯１〜フロー♯ｎを高優先度のクラスと低優先度のクラスに分け、高優先度のクラスのフローから優先的にパケットを出力し、高優先度のフローがなくなったら、低優先度のフローからパケットを出力する。
When there is an output from the RR circuit 224a, the SP circuit 222 outputs the output from the RR circuit 224a as output flow information. That is, the SP circuit 222 gives priority to the packet output from the high priority flow when there is a flow set to the high priority. On the other hand, when there is no output from the RR circuit 224a, the SP circuit 222 outputs the output from the RR circuit 224b as output flow information. In this way, the output
SP回路２２２から出力された出力フロー情報は、出力フロー選択部２２０の外部へ出力されるとともに、出力フロー保持回路２２８と、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎのそれぞれに入力される。出力フロー保持回路２２８は、SP回路２２２から出力された出力フロー情報を保持するとともに、前回出力フロー情報をスキップ判定回路２３０−１〜スキップ判定回路２３０−ｎのそれぞれに入力する。スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎはそれぞれ、出力フロー情報と前回出力フロー情報に基づいて、フロー♯１〜フロー♯ｎのパケット出力の処理がスキップされたか否かを判定する。前回出力フロー情報とは、最新のパケット出力の１つ前にパケットバッファからパケットが出力されたフローの情報である。
The output flow information output from the SP circuit 222 is output to the outside of the output
図４は、スキップ判定回路の動作を説明するための図である。図４において、自フローとは、フロー♯１〜フロー♯ｎのそれぞれのフローを指す。スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、フロー♯１〜フロー♯ｎのそれぞれに対して以下のフローチャートの処理を行う。また、図４の例では、フロー♯１〜フロー♯ｎにはそれぞれ、昇順のフローID（Identification）が付されているものとする。
FIG. 4 is a diagram for explaining the operation of the skip determination circuit. In FIG. 4, the own flow refers to each of
まず、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、フロー♯１〜フロー♯ｎのうち、パケットバッファからパケットが出力された最新のフローのID（以下、「出力フローID」という。）＝自フローIDであるか確認する（ステップＳ１）。ステップＳ１でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、自フローにスキップ有りの判定がなされていたら、そのスキップ判定を解除する（ステップＳ２）。
First, the skip determination circuit 230-1 to the skip determination circuit 230-n are referred to as the latest flow ID (hereinafter referred to as “output flow ID”) in which packets are output from the packet buffer among the
一方、ステップＳ１でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、出力フローID＞自フローIDであるか確認する（ステップＳ３）。ステップＳ３でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、フロー♯１〜フロー♯ｎのうち、前回出力フローID＜自フローIDであるか確認する（ステップＳ４）。前回出力フローIDとは、出力フローIDの１つ前にパケットバッファからパケットが出力されたフローのIDである。ステップＳ４でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、自フローがスキップされたと判定する（ステップＳ５）。
On the other hand, in the case of No in step S1, the skip determination circuit 230-1 to skip determination circuit 230-n confirm whether output flow ID> own flow ID is satisfied (step S3). If Yes in step S3, the skip determination circuit 230-1 to skip determination circuit 230-n checks whether the previous output flow ID <the own flow ID among the
一方、Ｓ４でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、前回出力フローID＞出力フローIDであるか確認する（ステップＳ６）。ステップＳ６でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、自フローがスキップされたと判定する（ステップＳ７）。一方、ステップＳ６でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、自フローはスキップ判定が解除されているかまたはスキップされたと判定されているかの現在の状態（以下、「現在スキップ判定状態」という。）を保持する（ステップＳ８）。 On the other hand, in the case of No in S4, the skip determination circuit 230-1 to skip determination circuit 230-n confirms whether the previous output flow ID> the output flow ID (step S6). If Yes in step S6, the skip determination circuit 230-1 to skip determination circuit 230-n determine that the own flow has been skipped (step S7). On the other hand, in the case of No in step S6, the skip determination circuit 230-1 to skip determination circuit 230-n determines whether the current flow is determined to have the skip determination canceled or skipped (hereinafter, “ (Referred to as “skip determination state”) (step S8).
ステップＳ３でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、前回出力フローID≧自フローIDであるか確認する（ステップＳ９）。ステップＳ９でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、現在スキップ判定状態を保持する（ステップＳ１０）。 In the case of No in step S3, the skip determination circuit 230-1 to skip determination circuit 230-n confirms whether the previous output flow ID ≧ the own flow ID (step S9). If Yes in step S9, the skip determination circuit 230-1 to skip determination circuit 230-n hold the current skip determination state (step S10).
一方、ステップＳ９でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、前回出力フローID＜出力フローIDであるか確認する（ステップＳ１１）。ステップＳ１１でYesの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、現在スキップ判定状態を保持する（ステップＳ１２）。一方、ステップＳ１１でNoの場合、スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎは、自フローがスキップされたと判定する（ステップＳ１３）。 On the other hand, in the case of No in step S9, the skip determination circuit 230-1 to skip determination circuit 230-n confirms whether or not the previous output flow ID <output flow ID (step S11). If Yes in step S11, the skip determination circuit 230-1 to skip determination circuit 230-n hold the current skip determination state (step S12). On the other hand, in the case of No in step S11, the skip determination circuit 230-1 to skip determination circuit 230-n determines that the own flow is skipped (step S13).
スキップ判定回路２３０−１〜スキップ判定回路２３０−ｎから出力されたフロー♯１〜フロー♯ｎの現在スキップ判定状態は、スキップ情報として優先制御信号生成部２００に入力される。図５は、優先制御信号生成部２００の動作を説明するための図である。優先制御信号生成部２００は、以下のフローチャートの処理をフロー♯１〜フロー♯ｎのそれぞれに対して行う。
The current skip determination state of the
まず、優先制御信号生成部２００は、フロー♯１〜フロー♯ｎのスキップ情報に基づいて、フロー♯１〜フロー♯ｎのスキップの発生が有か否かを判定する（ステップＳ２０）。ステップＳ２０でYesと判定した場合、優先制御信号生成部２００は、フロー♯１〜フロー♯ｎのトークン情報に基づいて、フロー♯１〜フロー♯ｎのトークン値の正か否かを判定する（ステップＳ２１）。ステップＳ２１でYesと判定した場合、優先制御信号生成部２００は、フロー♯１〜フロー♯ｎのパケット有無情報に基づいて、フロー♯１〜フロー♯ｎのパケットが有るか無いかを判定する（ステップＳ２６）。一方、ステップＳ２１でNoと判定した場合、優先制御信号生成部２００は、フローの優先度を現在の優先度に保持する（ステップＳ２３）。ステップＳ２６でYesと判定した場合、優先制御信号生成部２００は、このフローの優先度を低優先度に設定する（ステップＳ２２）。
First, the priority control
ステップＳ２０でNoと判定した場合、または、ステップＳ２６でNoと判定した場合、優先制御信号生成部２００は、フロー♯１〜フロー♯ｎのトークン廃棄情報に基づいて、フロー♯１〜フロー♯ｎのトークン値の廃棄が有か否かを判定する（ステップＳ２４）。ステップＳ２４でYesと判定した場合、優先制御信号生成部２００は、このフローの優先度を高優先度に設定する（ステップＳ２５）。一方、ステップＳ２４でNoと判定した場合、優先制御信号生成部２００は、フローの優先度を現在の優先度に保持する（ステップＳ２３）。なおフロー♯１〜フロー♯ｎの優先度の初期状態は低優先度に設定される。
When it is determined No in step S20, or when it is determined No in step S26, the priority control
なお、本実施例では、優先制御信号生成部２００は、フロー♯１〜フロー♯ｎのスキップ情報、トークン情報、パケット有無情報、およびトークン廃棄情報に基づいて、フロー♯１〜フロー♯ｎの優先度を設定しているが、これには限られない。すなわち、優先制御信号生成部２００は、パケット監視部１８０で検出されたパケット有無情報およびトークン演算部１６０によるトークン廃棄情報に応じて、フロー♯１〜フロー♯ｎのパケット出力の優先度を高優先度または低優先度に設定することができる。より具体的には、優先制御信号生成部２００は、パケット監視部１８０で検出されたパケットの格納が有りであり、かつトークン演算部１６０によるトークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定することができる。また、優先制御信号生成部２００は、少なくともパケット監視部１８０で検出されたパケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定することができる。
In this embodiment, the priority
次に、図６，図７Ａ，図７Ｂを用いて、実施例にかかるパケット転送装置１００のトークン値の遷移について説明する。図６，図７Ａ，図７Ｂは、実施例にかかるパケット転送装置１００のトークン値の遷移モデルを示す図である。図６，図７Ａ，図７Ｂはそれぞれ、フロー♯１〜フロー♯５のトークン値の遷移モデルを示している。図６，図７Ａ，図７Ｂのフロー♯１〜フロー♯５において、横軸は時間を示し、縦軸は記憶部♯１〜記憶部♯５に記憶されているトークン値を示す。図６，図７Ａ，図７Ｂにおいて、各フローのパケットバッファにパケットが格納されていない期間をαで示し、パケットバッファにパケットが格納されている期間をβで示す。また、図６と図７Ａにおいて、複数のトークン追加周期を時間軸に沿って周期（Ａ）〜周期（Ｆ）という。また、図７Ｂは図７Ａのトークン値の遷移モデルの続きを示すものであるから、図７Ｂの複数のトークン追加周期を時間軸に沿って周期（Ｆ）〜周期（Ｋ）という。
Next, the token value transition of the
図６の周期（Ａ）では、パケットバッファ１２０−１〜パケットバッファ１２０−４にパケットが格納されていないから、フロー♯１〜フロー♯４の優先度はそれぞれ低優先度に設定されているとする。一方、フロー♯５の優先度は高優先度に設定されているとする。図６の周期（Ａ）ではパケットバッファ１２０−１〜パケットバッファ１２０−４にパケットが格納されていないので、フロー♯５のパケットバッファ♯５からパケットが出力される（図６の（ａ）参照）。
In the period (A) of FIG. 6, since packets are not stored in the packet buffer 120-1 to packet buffer 120-4, the priority of the
続いて周期（Ｂ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されているトークン値に追加トークン値が加算される（図６の（ｂ）参照）。なおフロー♯１〜フロー♯４のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期（Ｂ）では、フロー♯５だけが高優先度に設定されているから、フロー♯５のパケットバッファ１２０−５から優先的にパケットが出力される（図６の（ｃ）参照）。また、周期（Ｂ）においてパケットを出力した後、フロー♯５のトークン値は負になるから、フロー♯１のパケットバッファ１２０−１からパケットが出力される（図６の（ｄ）参照）。
Subsequently, when the period (B) is entered, the additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see FIG. 6B). Since the token values of
続いて周期（Ｃ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図６の（ｅ）参照）。なおフロー♯１〜フロー♯４のトークン値はパケット有り時のMax Tokenに変更される。周期（Ｃ）ではパケットバッファ１２０−１〜パケットバッファ１２０−５にパケットが格納されているが、フロー♯５だけが高優先度に設定されているから、フロー♯５のパケットバッファ１２０−５から優先的にパケットが出力される（図６の（ｆ）参照）。また、周期（Ｃ）においてパケットを出力した後、フロー♯５のトークン値は負になるから、パケットバッファ１２０−２およびパケットバッファ１２０−３からパケットが出力される（図６の（ｇ）参照）。図６の周期（Ｄ）以降の処理は図６の周期（Ｂ）および周期（Ｃ）と同様であるから説明を省略する。
Subsequently, when the period (C) is entered, an additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (e) of FIG. 6). The token values of
図６で示した本実施例のモデルと図１１で示した従来技術のパケット転送装置のモデルとを比較すると、フロー＃５の優先度を高優先度に設定しているから、フロー＃５のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。 When the model of the present embodiment shown in FIG. 6 is compared with the model of the prior art packet transfer apparatus shown in FIG. 11, the priority of the flow # 5 is set to a high priority. The maximum token value is smaller than that of the prior art. That is, in the high-priority flow, packets are output preferentially, and the token value is subtracted every time a packet is output, so the maximum token value can be suppressed. Therefore, even if Max Token is set relatively small, the token value is hardly discarded. As a result, it is possible to suppress occurrence of token value discarding while suppressing Max Token.
次に、図７Ａ，図７Ｂでは、フロー♯１〜フロー♯５の優先度がそれぞれ低優先度に設定されているとする。まず、図７Ａの周期（Ａ）ではフロー♯１〜フロー♯５がいずれも低優先度に設定されているから、フロー♯１〜フロー♯４の順に、パケットバッファ１２０−１〜パケットバッファ１２０−４からパケットが出力される（図５Ａの（ａ）参照）。
Next, in FIGS. 7A and 7B, it is assumed that the priority of the
続いて周期（Ｂ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ａの（ｂ）参照）。なおフロー♯５のトークン値はMax Tokenに達しているから、加算されるトークン値は全て廃棄される。周期（Ｂ）ではフロー♯１〜フロー♯４のトークン値が負であるから、パケットバッファ１２０−１〜パケットバッファ１２０−４からはパケットは出力されず、パケットバッファ１２０−５からパケットが出力される（図７Ａの（ｃ）参照）。
Subsequently, when the period (B) is entered, an additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (b) of FIG. 7A). Since the token value of flow # 5 has reached Max Token, all token values to be added are discarded. In the period (B), since the token values of the
続いて周期（Ｃ）に入ると記憶部１４０−１〜記憶部１４０−５にトークン値が加算される（図７Ａの（ｄ）参照）。周期（Ｃ）においても、フロー♯１〜フロー♯４のトークン値が負であるから、パケットバッファ１２０−１〜パケットバッファ１２０−４からはパケットは出力されず、パケットバッファ１２０−５からパケットが出力される（図７Ａの（ｅ）参照）。
Subsequently, when the period (C) is entered, token values are added to the storage units 140-1 to 140-5 (see (d) of FIG. 7A). Also in the period (C), since the token values of the
続いて周期（Ｄ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ａの（ｆ）参照）。周期（Ｄ）では、フロー♯１〜フロー♯４のトークン値が０つまり正ではないから、パケットバッファ１２０−１〜パケットバッファ１２０−４からはパケットは出力されず、パケットバッファ１２０−５からパケットが出力される（図７Ａの（ｇ）参照）。
Subsequently, when the period (D) is entered, an additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (f) in FIG. 7A). In the period (D), since the token values of the
続いて周期（Ｅ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ａの（ｈ）参照）。周期（Ｅ）では、フロー♯１〜フロー♯４の順に、パケットバッファ１２０−１〜パケットバッファ１２０−４からパケットが出力される（図７Ａの（ｉ）参照）。
Subsequently, when the period (E) is entered, the additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (h) in FIG. 7A). In period (E), packets are output from packet buffer 120-1 to packet buffer 120-4 in the order of
続いて周期（Ｆ）に入ると記憶部１４０−１〜記憶部１４０−５にトークン値が加算される（図７Ａの（ｊ）参照）。ここで、フロー♯５では、記憶部１４０−５に記憶されたトークン値がMax Tokenを超過するから、超過した分のトークン値は廃棄される（図７Ａの（ｋ）参照）。すると、フロー♯５は、パケットバッファ１２０−５にパケットが格納されており、かつトークン値の廃棄が発生するので、パケットの出力の優先度が高優先度に設定される（図７Ａの（ｍ）参照）。周期（Ｆ）では、フロー♯１〜フロー♯４のトークン値が負であるから、パケットバッファ１２０−１〜パケットバッファ１２０−４からはパケットは出力されず、パケットバッファ１２０−５からパケットが出力される（図７Ｂの（ｎ）参照）。図７Ｂの周期（Ｇ）は図５Ｂの周期（Ｆ）と同様であるから、説明を省略する。また、図７Ｂの周期（Ｈ）は図７Ａの周期（Ｄ）と同様であるから、説明を省略する。
Subsequently, when the period (F) is entered, token values are added to the storage units 140-1 to 140-5 (see (j) in FIG. 7A). Here, in the flow # 5, since the token value stored in the storage unit 140-5 exceeds the Max Token, the excess token value is discarded (see (k) in FIG. 7A). Then, in flow # 5, since the packet is stored in the packet buffer 120-5 and the token value is discarded, the priority of the packet output is set to the high priority ((m in FIG. 7A). )reference). In the period (F), since the token values of the
続いて周期（Ｉ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ｂの（ｏ）参照）。周期（Ｉ）ではパケットバッファ１２０−１〜パケットバッファ１２０−５にパケットが格納されているが、フロー♯５だけが高優先度に設定されているから、フロー♯５のパケットバッファ１２０−５から優先的にパケットが出力される（図７Ｂの（ｐ）参照）。また、周期（Ｉ）においてパケットを出力した後、フロー♯５のトークン値は０つまり正ではなくなるから、パケットバッファ１２０−１、パケットバッファ１２０−２からパケットが出力される（図７Ｂの（ｑ）参照）。 Subsequently, when the period (I) is entered, an additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (o) in FIG. 7B). In the period (I), the packets are stored in the packet buffer 120-1 to the packet buffer 120-5, but only the flow # 5 is set to the high priority. Therefore, from the packet buffer 120-5 of the flow # 5, The packet is output preferentially (see (p) in FIG. 7B). Further, after outputting the packet in the cycle (I), the token value of the flow # 5 is 0, that is, not positive, so that the packet is output from the packet buffer 120-1 and the packet buffer 120-2 ((q in FIG. 7B). )reference).
続いて周期（Ｊ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ｂの（ｒ）参照）。周期（Ｊ）ではフロー♯５だけが高優先度に設定されているから、フロー♯５のパケットバッファ１２０−５から優先的にパケットが出力される（図７Ｂの（ｓ）参照）。また、周期（Ｊ）においてパケットを出力した後、フロー♯５のトークン値は負になるから、パケットバッファ１２０−３からパケットが出力される（図７Ｂの（ｔ）参照）。 Subsequently, when the period (J) is entered, the additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (r) in FIG. 7B). Since only the flow # 5 is set to the high priority in the cycle (J), the packet is preferentially output from the packet buffer 120-5 of the flow # 5 (see (s) in FIG. 7B). Further, after outputting the packet in the period (J), the token value of the flow # 5 becomes negative, so the packet is output from the packet buffer 120-3 (see (t) in FIG. 7B).
続いて周期（Ｋ）に入ると記憶部１４０−１〜記憶部１４０−５に記憶されたトークン値に追加トークン値が加算される（図７Ｂの（ｕ）参照）。周期（Ｋ）ではフロー♯５だけが高優先度に設定されているから、フロー♯５のパケットバッファ１２０−５から優先的にパケットが出力される（図７Ｂの（ｖ）参照）。また、周期（Ｋ）においてパケットを出力した後、フロー♯５のトークン値は負になるから、パケットバッファ１２０−４からパケットが出力される（図７Ｂの（ｗ）参照）。 Subsequently, when the period (K) is entered, the additional token value is added to the token values stored in the storage units 140-1 to 140-5 (see (u) in FIG. 7B). Since only the flow # 5 is set to the high priority in the cycle (K), the packet is preferentially output from the packet buffer 120-5 of the flow # 5 (see (v) in FIG. 7B). Further, since the token value of the flow # 5 becomes negative after outputting the packet in the period (K), the packet is output from the packet buffer 120-4 (see (w) in FIG. 7B).
以上のように、仮に、フロー♯５の優先度が低優先度の状態からトークン値が遷移したとしても、パケットバッファ１２０−５にパケットが格納されており、かつフロー♯５のトークン値がMax Tokenに達した時点でフロー♯５の優先度は高優先度に設定される。したがって、図７Ａ，図７Ｂで示したパケット転送装置のモデルと図１１で示した従来技術のパケット転送装置のモデルとを比較すると、フロー＃５のトークン値の最大値が従来技術に比べて小さくなる。つまり、高優先度のフローは優先的にパケットが出力され、パケットが出力されるたびにトークン値が減算されるので、トークン値の最大値を抑制することができる。したがって、Max Tokenを比較的小さく設定したとしてもトークン値の廃棄は発生し難い。その結果、Max Tokenを抑制しつつ、トークン値の廃棄の発生を抑制することができる。 As described above, even if the token value transitions from the low priority state of the flow # 5, the packet is stored in the packet buffer 120-5, and the token value of the flow # 5 is Max. When the token is reached, the priority of the flow # 5 is set to a high priority. Therefore, when the model of the packet transfer apparatus shown in FIGS. 7A and 7B is compared with the model of the conventional packet transfer apparatus shown in FIG. 11, the maximum token value of the flow # 5 is smaller than that of the conventional technique. Become. That is, in the high-priority flow, packets are output preferentially, and the token value is subtracted every time a packet is output, so the maximum token value can be suppressed. Therefore, even if Max Token is set relatively small, the token value is hardly discarded. As a result, it is possible to suppress occurrence of token value discarding while suppressing Max Token.
また、本実施例によれば、パケットバッファ１２０−１〜パケットバッファ１２０−ｎにパケットが蓄積された後、所定の時間が経過するとパケットを廃棄するHead Dropのような制御を行う場合であっても、パケットの廃棄の発生を抑制することができる。つまり、従来技術では、パケットバッファ１２０−１〜パケットバッファ１２０−ｎにパケットが蓄積されているにもかかわらず、他のフローの処理待ちのためにパケットが廃棄されるおそれがある。この点、本実施例は、パケットバッファ１２０−１〜パケットバッファ１２０−ｎにパケットが格納されていれば、トークン値の廃棄が発生した時点で高優先度になり、優先してパケットが出力されるので、所定時間経過後のパケットの廃棄が生じ難い。 In addition, according to the present embodiment, after a packet is accumulated in the packet buffer 120-1 to the packet buffer 120-n, when a predetermined time elapses, control such as Head Drop is performed in which the packet is discarded. Also, the occurrence of packet discard can be suppressed. In other words, according to the conventional technique, there is a possibility that the packet is discarded due to waiting for processing of another flow even though the packet is stored in the packet buffer 120-1 to the packet buffer 120-n. In this regard, in this embodiment, if packets are stored in the packet buffers 120-1 to 120-n, the priority is high when the token value is discarded, and the packets are output with priority. Therefore, it is difficult for a packet to be discarded after a predetermined time has elapsed.
ところで、トークン値の廃棄が発生しないようにMax Tokenを設定するためには、Max Token[byte]=フロー数[本]×最大パケット長[byte]/出力回線ワイヤレート[bps]×フローのSh_R[bps]とする。 By the way, in order to set Max Token so that the token value is not discarded, Max Token [byte] = number of flows [number] × maximum packet length [byte] / output line wire rate [bps] × Sh_R of flow [bps].
例えばあるパケット転送装置Xが、収容フロー数1024、最大パケット長10K[byte]、Sh_R設定粒度500K[bps]、Sh_Rのレンジ500K[bps]〜10G[bps]、トークン追加周期32u[s]という仕様となっているとする。このパケット転送装置Xにおいて、Sh_Rが500K[bps]の場合、トークン追加周期ごとに2[byte](=500K[bps]/8×32u[s])のトークン値が加算される。また、このパケット転送装置Xにおいて、Sh_Rが10Gbpsの場合、トークン追加周期ごとに40000byte(=10G[bps]/8×32u[s])のトークン値が加算される。 For example, a packet transfer apparatus X has a capacity of 1024 flows, a maximum packet length of 10K [byte], a Sh_R setting granularity of 500K [bps], a Sh_R range of 500K [bps] to 10G [bps], and a token addition period of 32u [s]. Suppose that it is a specification. In this packet transfer apparatus X, when Sh_R is 500 K [bps], a token value of 2 [bytes] (= 500 K [bps] / 8 × 32 u [s]) is added for each token addition period. Further, in this packet transfer apparatus X, when Sh_R is 10 Gbps, a token value of 40000 bytes (= 10 G [bps] / 8 × 32 u [s]) is added for each token addition period.
また、Sh_Rが1[Mbps]のフローが1000本あり、Sh_Rが9G[bps] のフローが1本あり、トータルのSh_Rが10G[bps]である場合を例に挙げると、Sh_Rが1M[bps]のフローのMax Tokenは、1K[byte](= 1000[本]×10K[byte]/(10×10^9)[bps]×(1×10^6)[bps])となる。また、Sh_Rが9G[bps]のフローのMax Tokenは、9M[byte](=1000[本]×10K[byte]/(10×10^9)[bps]×(9×10^9)[bps])となる。 For example, if there are 1000 flows with Sh_R 1 [Mbps], 1 flow with Sh_R 9G [bps], and total Sh_R 10G [bps], Sh_R 1M [bps] The Max Token of the flow of] is 1K [byte] (= 1000 [pieces] × 10K [byte] / (10 × 10 ^ 9) [bps] × (1 × 10 ^ 6) [bps]). The Max Token for a flow with Sh_R of 9G [bps] is 9M [byte] (= 1000 [lines] x 10K [byte] / (10 x 10 ^ 9) [bps] x (9 x 10 ^ 9) [ bps]).
これに対して、本実施例のパケット転送装置においては、46K[byte]（=１回の追加トークン分(36K[byte])＋最大パケット長(10K[byte])）のMax Tokenで、パケットの出力帯域の劣化を抑制することができる。ここで、低優先度のフローは従来技術に比べてトークン値が貯まりやすくなるが、Sh_Rが低ければ、トークン追加周期ごとのトークン値の追加は小さい。したがって、低優先度のフローであっても、従来技術のような例えば9M[byte]ものトークン値には達し難い。 On the other hand, in the packet transfer apparatus of the present embodiment, a packet with a Max Token of 46K [byte] (= additional token for one time (36K [byte]) + maximum packet length (10K [byte])) is used. It is possible to suppress the degradation of the output band. Here, in the low-priority flow, token values are more easily stored than in the prior art, but if Sh_R is low, addition of token values for each token addition period is small. Therefore, even with a low-priority flow, it is difficult to reach a token value of, for example, 9M [byte] as in the prior art.
また、Sh_Rが1M[bps]のフローの最大待ち合わせ時間は、80[ms]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたりには4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、待ち合わせ時間の間に追加するトークン値は10K[byte](=1M[bps]/8×80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。 The maximum waiting time for a flow with Sh_R of 1 M [bps] is 80 [ms]. In other words, since 1 G [bps] is allocated in a 32u [s] cycle to a low priority (1 M [bps]) flow, 4K [byte] is allocated per unit time. Therefore, 80 [ms] is required to secure 10K [byte] packet output for 1000 flows. Here, the token value to be added during the waiting time is 10K [byte] (= 1M [bps] / 8 × 80m [s]), so if you set a Max Token value greater than the token value to be added, Degradation of the output band can be suppressed.
以下、本実施例のパケット転送装置についてフローの本数およびフローのSh_Rを変えたいくつかのケースを説明する。 Hereinafter, several cases in which the number of flows and the flow Sh_R are changed in the packet transfer apparatus of this embodiment will be described.
（ケース１）
Sh_Rが1M[bps]のフローが500本、Sh_Rが5M[bps]のフローが500本、Sh_Rが7G[bps]のフローが1本である場合を例に挙げる。Sh_Rが7G[bps]のフローのMax Tokenが38K[byte]であった場合、Sh_Rが7G[bps]のフローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、26.7m[s] となる。つまり、低優先(1M[bps] と5M[bps])のフローには、32u[s]周期で3G[bps]分が割り当てられるので、単位時間あたり12K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、26.7[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は16.7K[byte](=5M[bps] /8 x 26.7m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
(Case 1)
As an example, there are 500 flows with Sh_R 1M [bps], 500 flows with Sh_R 5M [bps], and one flow with Sh_R 7G [bps]. If the Max Token of the flow with Sh_R 7G [bps] is 38K [byte], the flow with Sh_R 7G [bps] has high priority when the packet is stored and the token value is discarded become. At this time, the maximum waiting time for the flow with Sh_R of 1M [bps] and the flow with Sh_R of 5M [bps] is 26.7 m [s]. That is, since 3 G [bps] is allocated in a 32u [s] cycle to a flow with low priority (1 M [bps] and 5 M [bps]), 12 K [byte] per unit time is allocated. Therefore, 26.7 [ms] is required to secure 10K [byte] packet output for 1000 flows. Here, the token value to be added during the waiting time is 16.7K [byte] (= 5M [bps] / 8 x 26.7m [s]), so set the Max Token value greater than the token value to be added. Thus, it is possible to suppress the deterioration of the packet output bandwidth.
（ケース２）
Sh_Rが1M[bps]フローが999本、Sh_Rが5M[bps]フローが1本、Sh_Rが9G[bps]フローが1本である場合を例に挙げる。Sh_Rが9G[bps]フローのMax Tokenが46K[byte]であった場合、Sh_Rが9G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが5M[bps]のフローの最大待ち合わせ時間は、80m[s]となる。つまり、低優先(1M[bps])のフローには、32u[s]周期で1G[bps]分が割り当てられるので、単位時間あたり4K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、80[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン値は50K[byte](=5M[bps] / 8 x 80m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
(Case 2)
An example is given in which Sh_R has 1M [bps] flow, 999, Sh_R has 1 flow of 5M [bps], and Sh_R has 1 flow of 9G [bps]. If the Max Token of Sh_R is 9G [bps] is 46K [byte], the Sh_R of 9G [bps] flow has high priority when the packet is stored and the token value is discarded . At this time, the maximum waiting time for a flow with Sh_R of 1 M [bps] and a flow with Sh_R of 5 M [bps] is 80 m [s]. That is, since 1 G [bps] is allocated in a 32u [s] cycle to a low priority (1 M [bps]) flow, 4K [byte] per unit time is allocated. Therefore, 80 [ms] is required to secure 10K [byte] packet output for 1000 flows. Here, the token value to be added during the waiting time is 50K [byte] (= 5M [bps] / 8 x 80m [s]), so if you set a Max Token value greater than the token value to be added, the packet It is possible to suppress the degradation of the output band.
（ケース３）
Sh_Rが1M[bps]フローが1000本、Sh_Rが1G[bps]フローが1本、Sh_Rが8G[bps]フローが1本である場合を例に挙げる。Sh_Rが8G[bps]フローのMax Tokenが42K[byte]であった場合、Sh_Rが8G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。このとき、Sh_Rが1M[bps]のフローとSh_Rが1G[bps]のフローの最大待ち合わせ時間は、40m[s]となる。つまり、低優先(1M[bps]と1G[bps])のフローには、32u[s]周期で2G[bps]分が割り当てられるので、単位時間あたり8K[byte]が割り当てられる。したがって、10K[byte]のパケット出力を1000フロー分確保するためには、40[ms]必要になる。ここで、その待ち合わせ時間の間に追加するトークン量は5M[byte](=1G[bps]/8×40m[s])となるので、追加するトークン値以上のMax Token値を設定すればパケットの出力帯域の劣化を抑制することができる。
(Case 3)
As an example, Sh_R has 1000 1M [bps] flows, Sh_R has 1 1G [bps] flow, and Sh_R has 1 8G [bps] flow. If the Max Token of Sh_R is 8G [bps] is 42K [byte], then the Sh_R 8G [bps] flow has high priority when the packet is stored and the token value is discarded. . At this time, the maximum waiting time for a flow with Sh_R of 1 M [bps] and a flow with Sh_R of 1 G [bps] is 40 m [s]. That is, since a flow of low priority (1M [bps] and 1G [bps]) is assigned 2G [bps] in a cycle of 32u [s], 8K [byte] per unit time is assigned. Therefore, 40 [ms] is required to secure 10K [byte] packet output for 1000 flows. Here, the amount of tokens to be added during the waiting time is 5M [byte] (= 1G [bps] / 8 x 40m [s]), so if you set a Max Token value greater than the token value to be added, the packet It is possible to suppress the degradation of the output band.
また、Sh_Rが1G[bps]フローのMax Tokenも42K[byte]であった場合、Sh_Rが1G[bps]フローは、パケットが格納されており、かつトークン値の廃棄が発生した時点で高優先になる。そのときはSh_Rが8G[bps]フローのMax TokenはSh_Rが1G[bps]フローにより10K[byte]パケット出力時間を奪われてもトークン値の廃棄の発生を回避しなければならないため、さらに最大パケット長分を加えた52K[byte]のMax Tokenが必要となる。しかし、それでも従来技術においてパケットの出力帯域の劣化を抑制ために必要なMax Tokenと比較すると1/100以下のMax Tokenでパケットの出力帯域の劣化を抑制することができる。 If Max Token of Sh_R is 1G [bps] is also 42K [bytes], 1G [bps] flow of Sh_R is high priority when the packet is stored and the token value is discarded become. At that time, Max Token with Sh_R of 8G [bps] flow must avoid the token value discard even if Sh_R is deprived of 10K [byte] packet output time by 1G [bps] flow. A 52K [byte] Max Token plus the packet length is required. However, it is still possible to suppress the degradation of the output bandwidth of the packet with a Max Token of 1/100 or less as compared with the Max Token necessary for suppressing the degradation of the output bandwidth of the packet in the prior art.
以上、本実施例のパケット転送装置１００によれば、バケットバッファ１２０−１〜パケットバッファ１２０−ｎにパケットが格納されているフロー♯１〜フロー♯ｎでトークン値の廃棄が発生したら、そのフローのパケット出力の優先度は高優先度になる。パケット出力の優先度が高優先度になると、そのフローのパケットバッファからは優先的にパケットが出力される。パケットバッファからパケットが出力されると、パケットが出力されたフローに対応して記憶部に記憶されたトークン値から出力パケット長に応じたトークン値が減算される。したがって、本実施例のパケット転送装置１００によれば、フローの数が増大したとしても、記憶部に記憶されるトークン値の最大値を抑制することができるので、Max Tokenを抑制し、かつトークン値の廃棄の発生を抑制することができる。
As described above, according to the
上記の実施例に関し、さらに以下の付記を開示する。 The following additional notes are disclosed with respect to the above embodiments.
（付記１）パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファと、
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算するとともに、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、さらに前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備えたことを特徴とするパケット転送装置。
(Supplementary Note 1) A packet buffer that stores packets flowing through a plurality of flows that transmit packets, corresponding to the plurality of flows, and
A storage unit that stores a token value corresponding to the plurality of flows, which is information used to determine whether or not to permit output of the packet stored in the packet buffer;
A predetermined token value is added at a preset period to each of the token values stored in the storage unit corresponding to the plurality of flows, and the flow corresponding to the flow in which a packet is output from the packet buffer The token value corresponding to the output packet length is subtracted from the token value stored in the storage unit, and each of the token values stored in the storage unit corresponding to the plurality of flows exceeds a preset upper limit value. Then, a token calculation unit that discards the excess token value,
A packet monitoring unit for detecting whether or not a packet is stored in the packet buffer for each of the plurality of flows;
Depending on whether the packet detected by the packet monitoring unit is stored and whether the token value is discarded by the token calculation unit, the packet output priority of the plurality of flows is set to high priority or low priority. A priority control signal generator to be set;
A packet transfer apparatus comprising: an output flow selection unit that sequentially selects a flow for outputting a packet in accordance with a packet output priority of the plurality of flows set by the priority control signal generation unit.
（付記２）前記優先制御信号生成部は、前記パケット監視部で検出された前記パケットの格納が有りであり、かつ前記トークン演算部による前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記１に記載のパケット転送装置。
(Supplementary Note 2) The priority control signal generation unit is configured to store a packet of a flow in which the packet detected by the packet monitoring unit is stored and the token calculation unit discards the token value. Set the output priority to high priority,
The packet transfer apparatus according to
（付記３）前記トークン演算部は、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別し、
前記出力フロー選択部は、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択部でスキップされず、かつ前記トークン演算部でトークン値の廃棄が無しであるフローの優先度を保持する
付記１に記載のパケット転送装置。
(Supplementary Note 3) The token calculation unit determines whether each of the token values stored in the storage unit corresponding to the plurality of flows is positive or negative,
The output flow selection unit sequentially selects a flow that outputs a packet while skipping a flow in which no packet is stored in the packet buffer or a flow in which a token value stored in the storage unit is negative,
The priority control signal generation unit sets the packet output priority of a flow that is skipped by the output flow selection unit and the token value is determined to be positive by the token calculation unit to a low priority,
Holds the packet output priority of a flow that is skipped by the output flow selector and the token value is determined to be negative by the token calculator,
Set the priority of the flow that is not skipped by the output flow selection unit and the token value is discarded by the token calculation unit to a high priority,
The packet transfer device according to
（付記４）パケットを伝送する複数のフローを流れるパケットをそれぞれ前記複数のフローに対応して格納するパケットバッファにパケットが格納されているか否かを前記複数のフローごとに検出する監視ステップと、
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備えたことを特徴とするパケット転送方法。
(Supplementary Note 4) A monitoring step of detecting, for each of the plurality of flows, whether or not the packet is stored in a packet buffer that stores a packet flowing in a plurality of flows corresponding to the plurality of flows.
Each token value that is stored in the storage unit corresponding to the plurality of flows and that is used to determine whether or not to permit output of the packet stored in the packet buffer is set in advance. An addition step of adding a predetermined token value at a predetermined cycle;
A subtraction step of subtracting a token value corresponding to an output packet length from a token value stored in the storage unit corresponding to a flow in which a packet is output from the packet buffer;
A discarding step of discarding the excess token value when each of the token values stored in the storage unit corresponding to the plurality of flows exceeds a preset upper limit value;
Priority for setting the packet output priority of the plurality of flows to a high priority or a low priority according to whether or not the packet detected in the monitoring step is stored and whether or not the token value is discarded in the discarding step Configuration steps;
A packet transfer method comprising: an output flow selection step of sequentially selecting a flow for outputting a packet in accordance with a packet output priority of the plurality of flows set in the priority setting step.
（付記５）前記優先度設定ステップは、前記監視ステップで検出された前記パケットの格納が有りであり、かつ前記廃棄ステップによる前記トークン値の廃棄の発生が有りであるフローのパケットの出力の優先度を高優先度に設定し、
少なくとも前記監視ステップで検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
付記４に記載のパケット転送方法。
(Supplementary Note 5) In the priority setting step, priority is given to output of packets in a flow in which the packet detected in the monitoring step is stored and the token value is discarded in the discarding step. Set the degree to high priority,
The packet transfer method according to claim 4, wherein the priority of output of a packet of a flow in which at least the packet detected in the monitoring step is not stored is set to a low priority.
（付記６）前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別する判別ステップを有し、
前記出力フロー選択ステップは、前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながらパケットを出力するフローを順次選択し、
前記優先度設定ステップは、前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が正と判別されたフローのパケット出力の優先度を低優先度に設定し、
前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が負と判別されたフローのパケット出力の優先度を保持し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、
前記出力フロー選択ステップでスキップされず、かつ前記判別ステップでトークン値の廃棄が無しであるフローの優先度を保持する
付記４に記載のパケット転送方法。
(Supplementary Note 6) A determination step of determining whether each of the token values stored in the storage unit corresponding to the plurality of flows is positive or negative,
The output flow selection step sequentially selects a flow that outputs a packet while skipping a flow in which no packet is stored in the packet buffer or a flow in which a token value stored in the storage unit is negative,
The priority setting step sets the packet output priority of the flow skipped in the output flow selection step and the token value determined to be positive in the determination step to a low priority,
The priority of the packet output of the flow skipped in the output flow selection step and the token value determined to be negative in the determination step is retained.
Set the priority of the flow that is not skipped in the output flow selection step and the token value is discarded in the determination step to a high priority,
The packet transfer method according to appendix 4, wherein the priority of a flow that is not skipped in the output flow selection step and in which the token value is not discarded in the determination step is retained.
１００ パケット転送装置
１２０ パケットバッファ
１４０ 記憶部
１６０ トークン演算部
１８０ パケット監視部
２００ 優先制御信号生成部
２２０ 出力フロー選択部
100
Claims (3)
前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値を前記複数のフローに対応して記憶する記憶部と、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれにあらかじめ設定された周期で所定のトークン値を加算し、前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算し、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄し、前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別するトークン演算部と、
前記複数のフローごとに前記パケットバッファにパケットが格納されているか否かを検出するパケット監視部と、
前記パケット監視部で検出された前記パケットの格納の有無および前記トークン演算部による前記トークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先制御信号生成部と、
前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながら、前記優先制御信号生成部で設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択部と
を備え、
前記優先制御信号生成部は、前記出力フロー選択部でスキップされて、前記トークン演算部でトークン値が正と判別され、かつ前記パケットバッファにパケットが格納されていないフローのパケット出力の優先度を低優先度に設定し、前記出力フロー選択部でスキップされて、かつ前記トークン演算部でトークン値が負と判別されたフローのパケット出力の優先度を保持し、前記出力フロー選択部でスキップされず、かつ前記トークン演算部によるトークン値の廃棄が有りであるフロー、または、前記出力フロー選択部でスキップされて、前記トークン演算部でトークン値が正と判別され、前記パケットバッファにパケットが格納され、かつ前記トークン演算部によるトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、前記出力フロー選択部でスキップされず、かつ前記トークン演算部によるトークン値の廃棄が無しであるフローの優先度を保持し、
前記出力フロー選択部は、前記優先制御信号生成部により低優先度に設定されたフローよりも前記優先制御信号生成部により高優先度に設定されたフローを優先して選択する
ことを特徴とするパケット転送装置。 A packet buffer for storing a packet flowing through a plurality of flows transmitting packets corresponding to each of the plurality of flows;
A storage unit that stores a token value corresponding to the plurality of flows, which is information used to determine whether or not to permit output of the packet stored in the packet buffer;
A predetermined token value is added to each of the token values stored in the storage unit corresponding to the plurality of flows at a preset period, and the storage is performed corresponding to the flow in which a packet is output from the packet buffer. The token value corresponding to the output packet length is subtracted from the token value stored in the unit, and exceeded when each of the token values stored in the storage unit corresponding to the plurality of flows exceeds a preset upper limit value. A token calculation unit that discards the token value corresponding to the plurality of flows and determines whether each of the token values stored in the storage unit corresponding to the plurality of flows is positive or negative;
A packet monitoring unit for detecting whether or not a packet is stored in the packet buffer for each of the plurality of flows;
Depending on whether the packet detected by the packet monitoring unit is stored and whether the token value is discarded by the token calculation unit, the packet output priority of the plurality of flows is set to high priority or low priority. A priority control signal generator to be set;
Priority of packet output of the plurality of flows set by the priority control signal generation unit while skipping a flow in which no packet is stored in the packet buffer or a flow having a negative token value stored in the storage unit An output flow selection unit that sequentially selects a flow for outputting packets according to the degree,
The priority control signal generating unit is skipped in the output flow selection section, before Symbol token value in the token calculating unit is judged as positive, and the priority of the packet output of the flow packet in the packet buffer is not stored Is set to the low priority, the packet output priority of the flow that is skipped by the output flow selection unit and the token value is determined to be negative by the token calculation unit, and is skipped by the output flow selection unit The token value is discarded by the token calculation unit , or skipped by the output flow selection unit, the token value is determined to be positive by the token calculation unit, and the packet is stored in the packet buffer. stored, and sets the priority of the flow that waste is there a token value by the token calculation unit in the high priority, the Not skipped by the force flow selection section, and holds the flow priority is no disposal token value by the token computing section,
The output flow selection unit selects a flow set to a high priority by the priority control signal generation unit in preference to a flow set to a low priority by the priority control signal generation unit. Packet transfer device.
少なくとも前記パケット監視部で検出された前記パケットの格納が無しであるフローのパケットの出力の優先度を低優先度に設定する
請求項１に記載のパケット転送装置。 The priority control signal generation unit is a priority of the output of the packet of the flow in which the packet detected by the packet monitoring unit is stored and the token calculation unit discards the token value Set to high priority,
The packet transfer apparatus according to claim 1, wherein at least a packet output priority of a flow in which the packet detected by the packet monitoring unit is not stored is set to a low priority.
前記複数のフローに対応して記憶部に記憶されており、前記パケットバッファに格納されたパケットの出力を許可するか否かを判別するのに用いる情報であるトークン値のそれぞれに、あらかじめ設定された周期で所定のトークン値を加算する加算ステップと、
前記パケットバッファからパケットが出力されたフローに対応して前記記憶部に記憶されたトークン値から出力パケット長に応じたトークン値を減算する減算ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれがあらかじめ設定された上限値を超過したら超過した分のトークン値を廃棄する廃棄ステップと、
前記複数のフローに対応して前記記憶部に記憶されたトークン値のそれぞれが正か負かを判別する判別ステップと、
前記監視ステップで検出されたパケットの格納の有無および前記廃棄ステップによるトークン値の廃棄の有無に応じて、前記複数のフローのパケット出力の優先度を高優先度または低優先度に設定する優先度設定ステップと、
前記パケットバッファにパケットが格納されていないフローまたは前記記憶部に記憶されたトークン値が負であるフローをスキップしながら、前記優先度設定ステップで設定された前記複数のフローのパケット出力の優先度に応じて、パケットを出力するフローを順次選択する出力フロー選択ステップと
を備え、
前記優先度設定ステップは、前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が正と判別され、かつ前記パケットバッファにパケットが格納されていないフローのパケット出力の優先度を低優先度に設定し、前記出力フロー選択ステップでスキップされて、かつ前記判別ステップでトークン値が負と判別されたフローのパケット出力の優先度を保持し、前記出力フロー選択ステップでスキップされず、かつ前記廃棄ステップによるトークン値の廃棄が有りであるフロー、または、前記出力フロー選択ステップでスキップされて、前記判別ステップでトークン値が正と判別され、前記パケットバッファにパケットが格納され、かつ前記廃棄ステップによるトークン値の廃棄が有りであるフローの優先度を高優先度に設定し、前記出力フロー選択ステップでスキップされず、かつ前記廃棄ステップによるトークン値の廃棄が無しであるフローの優先度を保持し、
前記出力フロー選択ステップは、前記優先度設定ステップにより低優先度に設定されたフローよりも前記優先度設定ステップにより高優先度に設定されたフローを優先して選択する
ことを特徴とするパケット転送方法。 A monitoring step for detecting, for each of the plurality of flows, whether or not a packet is stored in a packet buffer that stores packets corresponding to the plurality of flows, each of which flows through a plurality of flows that transmit packets;
Each token value that is stored in the storage unit corresponding to the plurality of flows and that is used to determine whether or not to permit output of the packet stored in the packet buffer is set in advance. An addition step of adding a predetermined token value at a predetermined cycle;
A subtraction step of subtracting a token value corresponding to an output packet length from a token value stored in the storage unit corresponding to a flow in which a packet is output from the packet buffer;
A discarding step of discarding the excess token value when each of the token values stored in the storage unit corresponding to the plurality of flows exceeds a preset upper limit value;
A determination step of determining whether each of the token values stored in the storage unit corresponding to the plurality of flows is positive or negative;
Priority for setting the packet output priority of the plurality of flows to a high priority or a low priority according to whether or not the packet detected in the monitoring step is stored and whether or not the token value is discarded in the discarding step Configuration steps;
Priority of packet output of the plurality of flows set in the priority setting step while skipping a flow in which no packet is stored in the packet buffer or a flow having a negative token value stored in the storage unit And an output flow selection step for sequentially selecting a flow for outputting packets according to
The priority setting step is skipped in the output flow selection step, the token value is determined to be positive in the determination step , and the packet output priority of the flow in which no packet is stored in the packet buffer is reduced. The priority is set and the packet output priority of the flow that is skipped in the output flow selection step and the token value is determined to be negative in the determination step is retained, and is not skipped in the output flow selection step. And the token value discarded by the discard step , or skipped by the output flow selection step, the token value is determined positive by the determination step, the packet is stored in the packet buffer, and the the flow priority of the waste token value by discarding step is there high Yu Set time, holds the priority of not skipped in the output flow selection step, and it is no disposal token value by the disposal step flow,
The output flow selection step selects a flow set with a high priority by the priority setting step with priority over a flow set with a low priority by the priority setting step. Method.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2010063206A JP5604919B2 (en) | 2010-03-18 | 2010-03-18 | Packet transfer apparatus and packet transfer method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2010063206A JP5604919B2 (en) | 2010-03-18 | 2010-03-18 | Packet transfer apparatus and packet transfer method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2011199521A JP2011199521A (en) | 2011-10-06 |
| JP5604919B2 true JP5604919B2 (en) | 2014-10-15 |
Family
ID=44877181
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2010063206A Expired - Fee Related JP5604919B2 (en) | 2010-03-18 | 2010-03-18 | Packet transfer apparatus and packet transfer method |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP5604919B2 (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013239910A (en) * | 2012-05-15 | 2013-11-28 | Mitsubishi Electric Corp | Communication device |
| JP2015073210A (en) * | 2013-10-03 | 2015-04-16 | 株式会社日立製作所 | Transfer device |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004180302A (en) * | 2002-11-27 | 2004-06-24 | Alcatel Canada Inc | System and method for scheduling a data traffic flow for a communication device |
| JP4648833B2 (en) * | 2005-12-28 | 2011-03-09 | 富士通株式会社 | Bandwidth management device |
| JP4717768B2 (en) * | 2006-09-20 | 2011-07-06 | 富士通テレコムネットワークス株式会社 | Token bucket method and router using the same |
| JP2009147874A (en) * | 2007-12-18 | 2009-07-02 | Kddi Corp | Traffic control device, traffic control method, and traffic control program |
| JP2009200947A (en) * | 2008-02-22 | 2009-09-03 | Fujitsu Ltd | Packet transmitter, packet transmission method, and packet transmission program |
| US8824287B2 (en) * | 2008-04-24 | 2014-09-02 | Marvell International Ltd. | Method and apparatus for managing traffic in a network |
-
2010
- 2010-03-18 JP JP2010063206A patent/JP5604919B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2011199521A (en) | 2011-10-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP5157577B2 (en) | Packet buffer management device for determining arrival packet discard and its discard determination method | |
| US8000247B2 (en) | Bandwidth management apparatus | |
| JP2526013B2 (en) | Packet switching communication method | |
| JP4547339B2 (en) | Packet relay device having transmission control function | |
| US20110176554A1 (en) | Packet relay apparatus and method of relaying packet | |
| JP4659654B2 (en) | Shaper circuit | |
| JP4396657B2 (en) | Communication apparatus, transmission control method, and transmission control program | |
| CN112492646B (en) | Congestion control method and device based on congestion cause identification | |
| JP5598260B2 (en) | Packet transmission apparatus, packet transmission method and packet transmission program | |
| JP4704500B2 (en) | Packet processing device | |
| US20080192633A1 (en) | Apparatus and method for controlling data flow in communication system | |
| JP5604919B2 (en) | Packet transfer apparatus and packet transfer method | |
| US7933283B1 (en) | Shared memory management | |
| CN111131061B (en) | Data transmission method and network equipment | |
| JP2007208555A (en) | Transmission apparatus and line speed changing method | |
| JP4577220B2 (en) | Traffic control apparatus, method, and program using token bucket | |
| GB2360666A (en) | Flow control | |
| US7457238B2 (en) | Transmission system with congestion state-based flow control | |
| CN104022965B (en) | The method and apparatus that a kind of message goes out team's scheduling | |
| JP2008060658A (en) | Buffer controller and control method | |
| JP4086676B2 (en) | Data transfer device | |
| JP5759941B2 (en) | Communication apparatus and priority control method | |
| JP3508697B2 (en) | Packet switching device and packet switching method | |
| JPH1117702A (en) | Packet data memory device | |
| JP2006128859A (en) | Frame transfer device and frame transfer system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20130108 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20131018 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20131105 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20131227 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20140430 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20140620 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20140729 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20140811 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 5604919 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |