JP4484317B2 - Shaping device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a shaping device that shapes a transmission band of a packet.
[0002]
[Prior art]
In the packet-type communication method used on the Internet, packets from a large number of users can share the same line, so the cost per band can be kept low. In the Internet, there has been a demand for realizing communication quality (QoS: Quality of Service) such as a low delay time and a low discard rate, which has been realized in the conventional telephone network and corporate network.
[0003]
The minimum bandwidth guarantee service, which is one of the services that realize QoS, guarantees the minimum bandwidth contracted for each user (contractor), and packets exceeding this minimum bandwidth are transferred as long as network resources permit. .
[0004]
For example, the minimum bandwidth guarantee service is provided in the Internet 200 of FIG. 2, and the minimum bandwidth received by five terminals (terminal E235, terminal F236, terminal G237, terminal H238, terminal I239) directly connected to the edge router B204 is Consider a case where the user E, the user F, the user G, the user H, and the user I are contracted. The traffic transmitted from the terminal A231, terminal B232, terminal C233, and terminal D234 directly connected to the edge router A201 is transmitted to the terminal E235, terminal F236, terminal G237, and terminal H238 by the edge router A201, backbone router A202, backbone router B203, and edge router 204B. To terminal I239. When the line from the backbone router B203 to the edge router B204 is a bottleneck, the backbone router B203 possesses a shaper for the line and transfers it with a minimum bandwidth guaranteed for each user.
[0005]
As a scheduling method for a shaper that guarantees the minimum bandwidth, for example, a scheduling method called WFQ (Weighted Fair Queueing) is known. As the WFQ algorithm, an algorithm called SCFQ (Self Clocked Fair Queueing) is described in S.Golestani, A Self-Clocked Fair Queueing Scheme for Broadband Applications, In proc. Of INFOCOM94, pp.636-646, 1994. (Prior art 1). In Prior Art 1, the shaper has a plurality of queues i (= 1 to N), each queue i has a weight Wi and a variable Fi that are proportional to the bandwidth used, and updates the variable Fi when a packet arrives at the shaper. . At the time of packet output, the packet of queue i having the smallest Fi is serviced from among the variables Fi of the first packet of queue i in which packets are accumulated. Update the variable Fi
Fi = L / Wi + max (Fi, V (ta))
Done according to Here, L is the packet length of the arrival packet, ta is the arrival time of the packet, and V (t) is a function that returns the value of the packet variable Fi of the queue i at time t. In this method, a minimum bandwidth of Wi / (sum of Wi) × line bandwidth is guaranteed from queue i.
[0006]
[Problems to be solved by the invention]
The first problem with the prior art 1 shaper is that it cannot be shaped at high speed as the number of users increases. The shaper of the prior art 1 queues the traffic of each user (= contractor) in a queue for each user. Since the time for determining a queue for transmitting a packet increases as the number of users increases, shaping cannot be performed at high speed.
[0007]
The second problem is that the user cannot efficiently use the minimum bandwidth. This problem will be described with reference to the Internet 200 in FIG. Traffic from the terminal A231, terminal B232, terminal C233, and terminal D234 to the terminal E235 of the user E is input to the backbone router B203 as shown in FIG. Further, the shaper of the backbone router B203 guarantees the minimum bandwidth of the user E and performs shaping. When the total traffic of all users in the backbone router B203 changes as shown in FIG. 10, the traffic output by the shaper changes as shown in FIG. Since the total traffic of all users is below the line bandwidth at time ta, traffic to user E is output as soon as it is accumulated in the queue for each user. Further, since the bandwidth of user E is below the minimum bandwidth at time tb, all the traffic of user E is output. At time tc, the total traffic of all users exceeds the line bandwidth, and the bandwidth of user E exceeds the minimum bandwidth. Therefore, the packet of user E is accumulated in the queue for each user. Increases and the packet is discarded. Since the shaper does not consider the importance of the packet, the user may discard the important packet that the user wants to reach the receiving terminal and transfer other packets. The shaper of the prior art 1 discards packets important for the user and transmits other packets, and the user may not be able to use the minimum bandwidth efficiently. In the present invention, important packets that the user wants to reach the receiving terminal are called important packets, and other packets are called non-important packets.
[0008]
As described above, the prior art shaper cannot guarantee the minimum bandwidth of many users and perform shaping at high speed.
[0009]
A first object of the present invention is to provide a shaping apparatus that guarantees the minimum bandwidth of many users and performs shaping at high speed.
[0010]
In addition, since the shaper of the conventional technology protects important packets and cannot efficiently use the minimum bandwidth, the user cannot efficiently use the minimum bandwidth.
[0011]
A second object of the present invention is to provide a shaping device that protects important packets and efficiently uses the minimum bandwidth.
[0012]
[Means for Solving the Problems]
In order to achieve the first object, a shaping apparatus according to the present invention is based on a packet storage FIFO for storing packets, a priority determination means for determining a queuing priority of the packet, and the queuing priority. A discard control unit that determines whether to store or discard packets in the packet storage FIFO, and packets of a plurality of users are stored in the same packet storage FIFO. Since the shaping apparatus of the present invention outputs a packet from one packet storage FIFO 520, it is not necessary to select a buffer for outputting a packet from a plurality of buffers, and shaping can be performed at high speed.
[0013]
In order to achieve the second object described above, the shaping device of the present invention includes priority determination means that uses, as a priority packet, a packet for a minimum bandwidth guaranteed to each user for a plurality of user packets. When the priority determination means receives a user packet exceeding the minimum bandwidth, the important packet predetermined by the user is preferentially determined as a priority packet. Since the shaping apparatus of the present invention protects and transfers important packets, the minimum bandwidth can be used efficiently.
[0014]
Other problems to be solved by the present invention and the means for solving the problems will be clarified in the “Embodiments” section of the present invention and the drawings.
[0015]
DETAILED DESCRIPTION OF THE INVENTION
First, the general operation of the router having the shaping function of the present invention will be described with reference to FIGS. FIG. 1 shows a router 100 to which the present invention is applied. The router 100 includes N input lines 110-i (i = 1 to N) through which packets are input, a packet reception circuit 120-i that performs packet reception processing, a routing processing unit 130, and packet relay processing that switches packets Means 140, shaper unit 500-j (j = 1 to N) for each output line, packet transmission circuit 150-j for performing transmission processing, and N output lines 160-j for outputting packets .
[0016]
FIG. 3 shows an example of a packet format on the Internet 200. A packet in the Internet 200 includes a header part 310 and a data part 320. The header section 310 includes a source IP address (Source IP Address: hereinafter referred to as “SIP”) 311 that is a source address (address of the transmission terminal) and a destination IP address (Destination IP) that is a destination address (address of the reception terminal). Address: hereinafter referred to as “DIP”) 312, a source port (Source Port: hereinafter referred to as “SPORT”) 313 representing the source protocol (= higher application) and a destination port (Destination Port: representing the destination protocol) (Hereinafter referred to as “DPORT”). Further, the data unit 320 includes user data 321. In addition to the above information, information such as a service identifier (TOS: Type of Service) is also stored in the header section 310, but the processing described later can be executed in the same manner as the information.
[0017]
FIG. 4 shows a packet format inside the router 100 to which the present invention is applied. The packet format in the router 100 includes an internal header portion 330 in addition to the packet format in the Internet 200. The internal header section 330 is composed of a packet length 331 representing the byte length of the packet, an input line number 332 that is an identifier of the line to which the packet is input, and an output line number 333 that is an identifier of the line to which the packet is output.
[0018]
The network configuration assumed by the present invention is shown in FIG. The Internet 200 in FIG. 2 provides a minimum bandwidth guarantee service, and the minimum bandwidth received by five terminals (terminal E235, terminal F236, terminal G237, terminal H238, terminal I239) directly connected to the edge router B204 is the user. Contracted with E, User F, User G, User H, and User I. Terminal A231, terminal B232, terminal C233, and terminal D234 transmit packets, and terminal E235, terminal F236, terminal G237, terminal H238, and terminal I239 receive them. Although the bandwidth of the line from the backbone router B203 to the edge router B204 is larger than the sum of the minimum bandwidth contracted with each user, it is a bottleneck. The router 100 to which the present invention is applied is used as the backbone router B203, and the shaping unit 500-j of the output line 160-j leading to the edge router B204 performs shaping so as to guarantee the minimum bandwidth to each user.
[0019]
When a packet is input from the input line 110-i of the router 100 to which the present invention is applied, the packet receiving circuit 120-i adds an internal header portion 330, counts the byte length of the packet, and packet length 331 (unit is Byte) Write to. Further, the line number i of the input line 110-i to which the packet is input is written in the input line number 332, and the packet is transmitted to the routing processing unit 130. At this point, the output line number 333 is a meaningless value. When receiving the packet, the routing processing unit 130 determines the output line 160-j that outputs the packet from the DIP 312 and writes the line number j of the output line 160-j to the output line number 333 and transmits it to the packet relay processing unit 140. The packet relay processing unit 140 switches the packet according to the output line number 333 and transmits the packet to the shaper unit 500-j for each output line. The shaper unit 500-j guarantees the minimum bandwidth for each user and transmits the packet to the packet transmission circuit 150-j. When receiving the packet, the packet transmission circuit 150-j deletes the internal header part 330 and transmits the packet to the output line 160-j.
[0020]
Next, the detailed operation of the shaper unit 500 of the present invention will be described. FIG. 5 shows a block diagram of the shaper unit 500 of the present invention. The shaper unit 500 includes a packet accumulation FIFO 520 that accumulates packets, a packet output control unit 530 that outputs packets in the order of accumulation in the packet accumulation FIFO 520, and a discard control unit 510 that controls packet input and discard to the packet accumulation FIFO 520 And a bandwidth monitoring unit 600 that determines the queuing priority when the packet is stored in the packet storage FIFO 520. In the present invention, a packet whose bandwidth monitoring unit 600 determines the queuing priority as “priority” is referred to as a priority packet, and a packet that is determined as “non-priority” is referred to as a non-priority packet. The priority packet is preferentially stored in the packet storage FIFO 520 when congestion occurs and a large number of packets are stored in the packet storage FIFO 520.
[0021]
The discard control unit 510 stores the temporary storage buffer 511 that temporarily stores packets, the FIFO counter 513 that counts the number of packets stored in the packet storage FIFO 520, and the threshold of the packet storage FIFO 520 for priority packets of the FIFO counter 513 Priority packet threshold accumulation means 514, non-priority packet threshold accumulation means 515 for storing the threshold of the packet accumulation FIFO 520 for non-priority packets, and a discard determination circuit 512. The threshold accumulated in the priority packet threshold accumulation means 514 is larger than the threshold accumulated in the non-priority packet threshold accumulation means 515.
[0022]
When a packet is input from the packet relay processing unit 140, the header part 310, the data part 320, and the internal header part 330 are all stored in the temporary storage buffer 511, and the header part 310 and the internal header part 330 are stored in the bandwidth monitoring part 600. The bandwidth monitoring unit 600 determines the queuing priority based on the accumulated information. The bandwidth of the packet input for each user is monitored, and “priority” is determined for a packet within the minimum bandwidth, and “non-priority” is determined for an excess packet. Further, the queuing priority 12 composed of this determination information is transmitted to the discard determination circuit 512. Details of the operation of the bandwidth monitoring unit 600 will be described later.
[0023]
The discard determination circuit 512 of the discard controller 510 uses the queuing priority 12, the value of the FIFO counter 513, the threshold in the priority packet threshold storage unit 514, and the threshold in the non-priority packet threshold storage unit 515 to temporarily store the buffer 511. It is determined whether or not to discard the packet. When queuing priority 12 is "priority"
When the threshold value in the priority packet threshold value accumulation unit 514> the value of the FIFO counter 513, it is determined as “accumulation” and the temporary accumulation buffer 511 is instructed to transmit the packet to the packet accumulation FIFO 520. When the temporary storage buffer 511 receives this signal, it transmits the packet to the packet storage FIFO 520, and the packet storage FIFO 520 stores this packet.
[0024]
When the threshold in the priority packet threshold storage means 514 is equal to the value of the FIFO counter 513, it is determined as “discard” and the temporary storage buffer 511 is not instructed to transmit the packet. The temporary storage buffer 511 overwrites the information of the packet that has arrived next to the information of the packet determined to be “discard”. On the other hand, if the queuing priority 12 is "Non-priority"
When the threshold in the non-priority packet threshold accumulation means 515> the value of the FIFO counter 513, it is determined as “accumulation”
When the threshold in the non-priority packet threshold storage means 515 ≦ the value of the FIFO counter 513, it is determined as “discard”. The discard determination circuit 512 transmits the determination result (“accumulation” or “discard”) as the discard determination result 13 to the FIFO counter 513. The FIFO counter 513 adds 1 to the accumulated information when the discard determination result 13 is “accumulation”, and does not add when it is “discard”.
[0025]
The packet output control unit 530 transmits the packet transmission activation signal 14 so that the packets are transmitted in the line bandwidth in the order of accumulation in the packet accumulation FIFO 520, and the packet accumulation FIFO 520 that has received this signal transmits the packet to the packet transmission circuit 150. . When receiving the packet transmission activation signal 14, the FIFO counter 513 subtracts 1 from the accumulated information. In the present invention, the packet output control unit 530 transmits the packet transmission activation signal 14 so as to transmit the packet in the line bandwidth, but the bandwidth is equal to or less than the line bandwidth set by the network operator (for example, half of the line bandwidth). You may send it.
[0026]
Since the shaper unit 500-j of the present invention outputs a packet from one packet storage FIFO 520, it is not necessary to select a buffer for outputting a packet from a plurality of buffers, and shaping can be performed at high speed.
[0027]
When traffic destined for user E (terminal E235) is input to the shaper unit 500-j as shown in FIG. 9, and the total traffic of all users is input to the shaper unit 500-j as shown in FIG. The traffic for user E output from 160-j is as shown in FIG. At time ta, the total traffic of all users is below the line bandwidth, so user E's packet is stored in packet storage FIFO 520 and output. Since the total traffic of all users exceeds the line bandwidth at times tb and tc, packets are accumulated in the packet accumulation FIFO 520 exceeding the value in the threshold accumulation means 515 for non-priority packets. At this time, the non-priority packet is not accumulated, and only the priority packet is accumulated in the packet accumulation FIFO 520. Packets are output from the packet storage FIFO 520 in the line bandwidth, and the priority packets for each user are input below the minimum bandwidth. Since the sum of the minimum bandwidths of each user is equal to or less than the line bandwidth, the priority packets are not discarded but are accumulated in the packet accumulation FIFO 520 and output from the output line 160-j. At time tb, the band of user E is equal to or lower than the minimum band, and therefore the packet of user E is finally output from the output line 160-j. At time tc, a packet below the lowest bandwidth of user E is determined as a priority packet and output from the output line 160-j, but a packet above the minimum bandwidth is determined as a non-priority packet and discarded.
[0028]
Next, the detailed operation of the bandwidth monitoring unit 600 will be described. At time tc, the bandwidth monitoring unit 600 selectively determines important packets as priority packets. With this function, the shaper unit 500 can protect important packets. As an algorithm for bandwidth monitoring, an algorithm obtained by extending continuousLeaky Bucket Algorithm (hereinafter referred to as leaky bucket algorithm), which is a monitoring algorithm for cells that are fixed-length packets, for bandwidth monitoring of variable-length packets is used. The leaky bucket algorithm is described, for example, in Chapter 4.4.2 of The ATM Forum Specification version 4.1. The leaky bucket algorithm is a leaky bucket model with a certain depth, with water leaking in the monitoring band while the bucket is filled with water, and one cell of water is poured into the bucket when the cell arrives. In order to allow the arrival fluctuation of the cell, the bucket has a depth. When the bucket does not overflow, the input cell is determined to be compliant, and when it overflows, it is determined to be violated. In the present invention, the bandwidth of variable-length packets can be monitored by changing the amount of water poured upon arrival of the packets.
[0029]
FIG. 6 shows a block diagram of the bandwidth monitoring unit 600. The bandwidth monitoring unit 600 includes a bandwidth monitoring table control unit 650, a bucket accumulation amount determination unit 610, a monitoring result determination unit 620, a bandwidth monitoring table 630, and a flow detection unit 640. The flow detection unit 640 determines a flow identifier based on information in the header for each input packet in order to perform bandwidth monitoring. The bandwidth monitoring unit 600 performs bandwidth monitoring using bandwidth monitoring control information corresponding to the flow identifier. In the present invention, it is determined whether a packet identification condition created by combining information in the header or the like is a flow condition, a series of traffic that matches the flow condition, and whether an input packet matches the flow condition. This flow identification is called flow detection.
[0030]
FIG. 7 shows the format of the bandwidth monitoring table 630. The bandwidth monitoring table 630 includes M pieces of bandwidth monitoring control information 700-k (k = 1 to M). The bandwidth monitoring unit 600 performs bandwidth monitoring for one user based on the bandwidth monitoring control information 700-k. The bandwidth monitoring control information 700-k includes the bucket depth THR-A701-k (Byte) (Threshold-A) for important packets and the bucket depth THR-B702-k (Byte) (Threshold) for non-important packets. -B), POLR703-k (Byte / sec) (Policing Rate) representing the rate of water leakage from the bucket and indicating the monitoring rate, and the same bandwidth monitoring control information 700-k (k = 1 to M) It consists of the time TS704-k (sec) (Time Stamp) when the packet water was accumulated in the bucket last time and the CNT705-k (Byte) (Count), which is the amount of water accumulated in the bucket at time TS704-k. The Note that THR-A701-k and THR-B702-k representing the bucket depth have a relationship of THR-A701-k ≧ THR-B702-k.
[0031]
FIG. 8 shows a flowchart of the bandwidth monitoring unit 600. The processing of the bandwidth monitoring unit 600 is a bandwidth monitoring start processing 800, a bucket accumulation amount determination processing 810, and a monitoring result determination processing 820. The latter two processes are mainly executed by the bucket accumulation amount determination unit 610 and the monitoring result determination unit 620, respectively.
[0032]
When the bandwidth monitoring unit 600 receives the packet header information 11 including the header unit 310 and the internal header unit 330, the packet length storage unit 622 of the monitoring result determination unit 620 indicates the packet length 331, and the flow detection unit 640 indicates the input line number. 332, output line number 333, SIP 311, DIP 312, SPORT 313, and DPORT 314 are stored (step 801). In step 802, the flow detection unit 640 performs flow detection based on the accumulated information. Here, the flow identifier of the packet in the temporary storage buffer 511 and whether it is an important or non-important packet are determined. Further, the flow identifier information 15 composed of the flow identifier is sent to the bandwidth monitoring table control circuit 651 of the bandwidth monitoring table control unit 650, and the packet importance level information 17 indicating the importance level of the packet is sent to the packet importance level of the monitoring result determination unit 620. It transmits to the storage means 624.
[0033]
The flow identifier information 15 and the user have a one-to-one correspondence. In the Internet 200 of FIG. 2, for example, the flow detection unit 640 determines a flow identifier by identifying a user by the IP address (DIP312) of the terminal E235, terminal F236, terminal G237, terminal H238, and terminal I239, and determines the TCP port number. The application is identified from (SPORT313, DPORT314), and the importance of the packet is determined.
[0034]
Upon receiving the flow identifier information 15, the bandwidth monitoring table control circuit 651 creates an address of the bandwidth monitoring table 630, reads the bandwidth monitoring control information 700-k, and monitors the THR-A701-k and THR-B702-k as the monitoring results. The POLR 703-k, TS704-k, and CNT705-k are stored in the POLR storage unit 613, the TS storage unit 614, and the CNT storage unit 615 of the bucket storage amount determination unit 610, respectively, in the THR storage unit 623 of the determination unit 620 (step 803). ).
[0035]
In the bucket accumulation amount determination processing 810, the bucket accumulation amount determination unit 610 determines the amount of bucket water immediately before packet input (bucket accumulation amount). First, the bucket accumulation amount determination circuit 611 calculates the difference between the value of the timer 612 that counts the current time (unit: sec) and TS704-k (sec) in the TS accumulation means 614, and water is accumulated in the bucket last time. The elapsed time (sec) that has elapsed since then is calculated (step 811). Next, multiply the elapsed time (sec) by POLR703-k (Byte / sec) in the POLR accumulation means 613 to calculate the amount of water leaked since the previous accumulation of water in the bucket (bucket decrease) (step) 812). Further, the bucket accumulation amount immediately before the packet is input is determined by subtracting the bucket decrease amount from the CNT 705-k in the CNT accumulation means 615 (step 813). Whether the bucket accumulation amount is positive or negative is determined (step 814). If the determination result is negative, the bucket accumulation amount is corrected to "0" (bucket is empty) (step 815).
[0036]
In the monitoring result determination process 820, the monitoring result determination circuit 621 of the monitoring result determination unit 620 determines whether or not water corresponding to the packet in the temporary storage buffer 511 enters the bucket and determines the priority of the packet. First, the monitoring result determination circuit 621 adds the packet length (Byte) to the bucket accumulation amount (Byte) determined in the bucket accumulation amount determination processing 810 (Step 821). Next, the packet importance storage unit 624 stores the packet importance information 17 transmitted by the flow detection unit 640. Based on this accumulated information, the bandwidth monitoring process branches (step 822). When the stored information is “important”, the monitoring result determination circuit 621 performs a size comparison between the packet depth THR-A701-k stored in the THR storage unit 623 and the added value ( Step 823). Bucket accumulation amount + packet length> THR-A701-k, that is, when the bucket overflows, the packet accumulated in the temporary accumulation buffer 511 is judged as a violation packet, and the bandwidth monitoring result information 18 indicating “violation” is The queuing priority 12 indicating “non-priority” is transmitted to the discard determination circuit 512 to the bandwidth monitoring table control circuit 651 of the bandwidth monitoring table control unit 650 (step 826). On the other hand, when the bucket accumulation amount + packet length ≦ THR-A701-k, the input packet is determined to be a compliant packet, and the bandwidth monitoring result information 18 indicating “compliance” is indicated to the bandwidth monitoring table control circuit 651 to indicate “priority”. The queuing priority 12 is transmitted to the discard determination circuit 512 of the discard control unit 510, and the value of “bucket accumulation amount + packet length” is transmitted to the bandwidth monitoring table control circuit 651 as the bucket accumulation amount information 16 (step 825). When the reference result of step 822 is “non-important”, the bucket accumulation amount + packet length value is stored in the THR storage means 623 and the added value of the bucket depth THR-B702-k for the non-important packet A comparison is made (step 824). Step 825 is executed when bucket accumulation amount + packet length ≦ THR-B702-k, and step 826 is executed when bucket accumulation amount + packet length> THR-B702-k.
[0037]
When the bandwidth monitoring table control circuit 651 receives the bandwidth monitoring result information 18 indicating “Compliance”, the bucket accumulation amount information 16 and the value of the timer 612 are respectively set as the bucket accumulation amount immediately after the bandwidth monitoring and the arrival time of the packet. Write to CNT705-k and TS704-k of the monitoring table 630 (step 827). When the bandwidth monitoring table control circuit 651 receives the bandwidth monitoring result information 18 indicating “Violation”, the bandwidth monitoring table control circuit 651 does not perform Step 827. When the above processing ends, bandwidth monitoring ends (step 828).
[0038]
Steps 822 and 824 are processes unique to the present invention. The bandwidth monitoring unit 600 has two bucket depths THR-A701-k and THR-B702-k, and executes step 822 and step 824 to selectively determine important packets as priority packets. Consider the case where the breakdown of the important packets and the unimportant packets of the traffic destined for user E is shown in FIG. In this case, the determination result of the bandwidth monitoring unit 600 is as shown in FIG. The mesh portion is a priority packet, and the white portion is a non-priority packet. At time tb, since packets are input at the minimum bandwidth or less, water is not accumulated in the bucket, and all packets are determined to be “priority”. On the other hand, at time ta and tc, since the packet is input beyond the minimum bandwidth, water is accumulated up to the bucket depth THR-B702-k for non-important packets. At this time, the non-important packet is not stored and determined as “non-priority”, and only the important packet is stored in the bucket and determined as “priority”.
[0039]
The traffic output from the output line 160-j is shown in FIG. At time ta, the total traffic of all users is below the line bandwidth (see FIG. 10), so the packet destined for user E is output as soon as it is stored in the packet storage FIFO 520. At time tc, since the total traffic of all users exceeds the line bandwidth, packets are accumulated in the packet accumulation FIFO 520 exceeding the threshold in the non-priority packet threshold accumulation means 515. At this time, the non-priority packet is not accumulated in the packet accumulation FIFO 520, but only the priority packet is accumulated. Packets are output from the packet storage FIFO 520 in the line bandwidth, and priority packets are input below the line bandwidth. Therefore, priority packets are not discarded but are stored in the packet storage FIFO 520 and finally output from the output line 160-j. . For this reason, all important packets of the user E are output from the output line 160-j. At time tb, since all packets destined for user E are determined as priority packets, all packets are output from the output line 160-j.
[0040]
As described above, the bandwidth monitoring unit 600 of the shaper unit 500 selectively determines important packets as priority packets, and the discard control unit 510 preferentially stores the priority packets in the packet storage FIFO 520. 500 can forward important packets while protecting them.
[0041]
So far, the operation of the router 100 has been described. In the case of an ATM exchange or a frame relay exchange, the header section 310 is composed of connection identifiers such as VPI / VCI and DLCI, and discard priority information such as CLP and DE. Correspondingly, the routing processing unit 130 determines the output line 160-j that outputs a packet from the connection identifier instead of the DIP 312, and the flow detection unit 640 is connected to the SIP 311, DIP 312, SPORT 313, and DPORT 314. Flow detection is performed using identifiers and discard priority information.
[0042]
【The invention's effect】
The router 100 including the shaper unit 500 of the present invention can perform shaping at high speed while guaranteeing the minimum bandwidth of many users. By using this router 100, the network operator can provide a minimum bandwidth guarantee service to many users in a high-speed network.
[0043]
Furthermore, the router 100 including the shaper unit 500 of the present invention can protect important packets and perform shaping that efficiently uses the minimum bandwidth. By using the router 100, the network operator can provide a “service that can effectively use the minimum bandwidth” in which packets important to the user are protected and transmitted.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a router 100 to which the present invention is applied.
FIG. 2 is a configuration diagram of a network.
FIG. 3 is a diagram showing a format of a packet in the Internet 200.
FIG. 4 is a diagram showing a packet format in the router 100 to which the present invention is applied.
FIG. 5 is a block diagram showing a configuration of a shaper unit 500 according to the present invention.
FIG. 6 is a block diagram showing a configuration of a bandwidth monitoring unit 600 of the present invention.
7 is a view showing a format of a bandwidth monitoring table 630. FIG.
FIG. 8 is a flowchart of a bandwidth monitoring unit 600 to which the present invention is applied.
FIG. 9 is a diagram illustrating a time change of traffic destined for a terminal E235 in traffic input to the shaper unit 500;
FIG. 10 is a diagram illustrating a temporal change in the total traffic of all users input to the shaper unit 500;
FIG. 11 is a diagram showing a time change of traffic destined for a terminal E235 in traffic output from the output line 160-j.
FIG. 12 is a diagram showing a change over time in the breakdown of important packets and non-important packets destined for terminal E235 in traffic input to shaper section 500;
FIG. 13 is a diagram illustrating a change in traffic over time that the bandwidth monitoring unit 600 determines as “priority” or “non-priority”;
FIG. 14 is a diagram showing a time change of traffic destined for terminal E235 in traffic output from output line 160-j.
[Explanation of symbols]
11 ... Packet header information
12 ... queuing priority
13 ... Disposal judgment result
14 ... Packet transmission start signal
15: Flow identifier information
16 ... Bucket accumulation information
17: Packet importance information
18: Band monitoring result information.

Claims (10)

In a shaping device that guarantees the minimum bandwidth and transmits packets,
One buffer to store packets;
Output control means for outputting packets in the order of accumulation in the buffer;
Priority determination means for determining queuing priority when storing in the buffer;
A discard control unit that determines whether to accumulate or discard a packet in the buffer based on the queuing priority ; and the priority determination unit detects a series of packet flows from information or the like in a packet header, and the flow Flow detection means for determining a flow identifier that is an identifier of
A bandwidth monitoring table entries composed of the bandwidth monitoring control information to one or more holders is control information for monitoring the band,
Bandwidth monitoring table control means for reading an entry corresponding to the flow identifier from a bandwidth monitoring table;
Wherein and a determining monitoring result determining means for queuing priority based on the packet length of the bandwidth monitoring control information and the timer value and the packet header indicating the current time in the entry of the bandwidth check table control means read The flow detection means determines whether the importance of the packet in the flow is important or non-important in addition to the flow identifier
The monitoring result determining means determines a queuing priority based on the importance in addition to the bandwidth monitoring control information, a timer value indicating the current time, and a packet length in a packet header,
Further, the bandwidth monitoring control information includes monitoring bandwidth information, and the monitoring result determination means monitors whether the packet violates the monitoring bandwidth regardless of the importance , and the importance is important. If the bandwidth used by the packet is not exceeding the monitoring bandwidth, and the packet is a non-critical packet, the low-importance packet does not violate the monitoring bandwidth, A shaping device that determines that the queuing priority of an unimportant packet is a priority . Threshold priority storage means for priority packets that stores the maximum value (threshold value) of the buffer that is referred to when the discard control means determines whether to store or discard packets with a priority priority of queuing priority; Threshold storage means for non-priority packets that stores the maximum value (threshold) of the buffer referred to when determining whether to store or discard packets with a degree of “non-priority”;
The shaping apparatus according to claim 1, further comprising a counter that counts the number of packets accumulated in the buffer. The shaping device according to claim 1,
The priority determination means has one entry composed of bucket depth information, bandwidth information, arrival time information of the previous packet, and accumulated amount information of the bucket when the previous packet arrives, which is control information for monitoring the bandwidth. Or a multiple bandwidth monitoring table,
Bucket accumulation amount determination means for calculating the accumulation amount of the bucket immediately before the bandwidth monitoring from the read bandwidth information, the arrival time information of the previous packet, the accumulation amount information of the bucket at the arrival of the previous packet, and the timer value indicating the current time;
A shaping apparatus comprising monitoring result determination means for determining a queuing priority based on an accumulation amount of a bucket immediately before bandwidth monitoring, a packet length in a packet header, and bucket depth information. A shaping device according to claim 3,
The bandwidth monitoring table has a plurality of bucket depths as the bucket depth information, and the monitoring result determination means is the bucket storage amount immediately before the bandwidth monitoring, the packet length in the packet header, and the bucket depth information. And a queuing priority based on the importance. A packet storage FIFO to store packets;
Priority determining means for determining the queuing priority of the packet;
A discard control unit that determines packet storage / discard to the packet storage FIFO based on the queuing priority;
The priority determination means sets a packet for a minimum bandwidth guaranteed to each user for a plurality of user packets as a priority packet, and receives a packet of a user exceeding the minimum bandwidth. The priority packet determined by the user is preferentially determined as a priority packet, and the priority determination means determines whether the packet violates the minimum bandwidth regardless of the importance of the packet. monitoring, severity does not exceed the minimum bandwidth is bandwidth packet uses of the importance, and if the importance degree of the packet is non-critical, the importance is unimportant If the packet does not violate the minimum bandwidth, the shaping device is characterized in that the queuing priority of the packet whose importance is unimportant is determined as priority .   6. The shaping apparatus according to claim 5, wherein the packets of the plurality of users are stored in the same packet storage FIFO. In a shaping device that guarantees the minimum bandwidth and transmits packets,
One packet storage FIFO to store packets;
Output control means for outputting packets in the order of accumulation in the packet accumulation FIFO;
Priority determination means for determining queuing priority when storing in the packet storage FIFO;
A discard control unit that determines whether to store or discard packets in the packet storage FIFO based on the queuing priority , and the priority determination unit detects a series of packet flows from information in a packet header. Flow detection means for determining a flow identifier which is an identifier of the flow;
A bandwidth monitoring table having one or more entries composed of bandwidth monitoring control information which is control information for monitoring the bandwidth;
Bandwidth monitoring table control means for reading an entry corresponding to the flow identifier from a bandwidth monitoring table;
And a monitoring result determining means for determining a queuing priority based on the packet length of the bandwidth check table control means read the timer value and the packet header indicating the bandwidth monitoring control information and the current time in the entry,
The flow detection means determines the importance of the packet in the flow in addition to the flow identifier, and the monitoring result determination means sets the bandwidth monitoring control information, the timer value indicating the current time, and the packet length in the packet header. In addition, a queuing priority is determined based on the importance,
Further, the bandwidth monitoring control information includes the information on the minimum bandwidth, and the monitoring result determination means monitors whether the packet violates the minimum bandwidth regardless of the importance , and the importance If the bandwidth used by the packets whose importance is important does not exceed the minimum bandwidth, and the packets whose importance is not important do not violate the minimum bandwidth, the importance is not important. shaping apparatus characterized by determining a priority queuing priority of a packet.   Priority packet threshold storage means for storing a maximum value (threshold value) of the packet storage FIFO to be referred to when the discard control unit determines whether to store or discard a packet with a priority of “priority”. Non-priority packet threshold storage means for storing the maximum value (threshold value) of the packet storage FIFO to be referred to when determining whether to store or discard a packet having a non-priority ingress priority, and the packet storage FIFO 8. The shaping device according to claim 7, further comprising a counter that counts the number of packets accumulated in the. The shaping device according to claim 7,
Bandwidth monitoring of one or more carrying the composed entry from the arrival time information and the previous packet arrival bucket storage amount information when the bucket depth information and band information and the previous packet is control information for monitoring the bandwidth Table,
A bucket water level decision means for calculating the accumulated amount of bucket bandwidth monitoring to just the value of the timer indicating the accumulated amount information and the current time bucket upon arrival of the arrival time information of the read bandwidth information and the previous packet and the previous packet ,
Shaping apparatus characterized by comprising a monitoring result determining means for determining a queuing priority based on the packet length and a bucket depth information in bucket accumulation amount and the packet header just before the bandwidth monitoring. The shaping device according to claim 9, wherein
The bandwidth monitoring table has a plurality of bucket depths as the bucket depth information, and the monitoring result determination means is the bucket storage amount immediately before the bandwidth monitoring, the packet length in the packet header, and the bucket depth information. And a queuing priority is determined based on the importance.

Images