[go: up one dir, main page]

WO2010089886A1 - パケットバッファ装置及びパケット廃棄方法 - Google Patents

パケットバッファ装置及びパケット廃棄方法 Download PDF

Info

Publication number
WO2010089886A1
WO2010089886A1 PCT/JP2009/052110 JP2009052110W WO2010089886A1 WO 2010089886 A1 WO2010089886 A1 WO 2010089886A1 JP 2009052110 W JP2009052110 W JP 2009052110W WO 2010089886 A1 WO2010089886 A1 WO 2010089886A1
Authority
WO
WIPO (PCT)
Prior art keywords
packet
queue
unit
time
measurement
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.)
Ceased
Application number
PCT/JP2009/052110
Other languages
English (en)
French (fr)
Inventor
朝永　博
西村　和人
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2010549323A priority Critical patent/JP5146548B2/ja
Priority to PCT/JP2009/052110 priority patent/WO2010089886A1/ja
Publication of WO2010089886A1 publication Critical patent/WO2010089886A1/ja
Priority to US13/195,109 priority patent/US8937962B2/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2416—Real-time traffic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/28—Flow control; Congestion control in relation to timing considerations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/30—Flow control; Congestion control in combination with information about buffer occupancy at either end or at transit nodes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/32—Flow control; Congestion control by discarding or delaying data units, e.g. packets or frames
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L65/00—Network arrangements, protocols or services for supporting real-time applications in data packet communication
    • H04L65/80—Responding to QoS

Definitions

  • the present invention relates to a packet discarding method in a packet buffer device that temporarily holds an arriving packet.
  • next-generation networks As a general rule, the quality of services provided by next-generation networks is guaranteed by providing sufficient data transmission bandwidth in the network.
  • a service provided by a WEB server, an IP telephone service, and a video transfer service are provided on a normal Internet, and therefore a sufficient data transmission bandwidth is not always provided.
  • tail drop (Tail Drop) and random initial detection (RED: Random Early Detection) have been proposed as data discard methods when the packet buffer is congested. Further, an edge node device that performs RED by changing the packet discard rate according to the packet stay time has been proposed. Furthermore, a data inflow amount control device for calculating a scheduled time at which a packet transmitted from a base station to a mobile station stays in a buffer of the base station is disclosed. Furthermore, a data transmission method is disclosed in which the mandatory arrival time at the data receiving destination registered in the transfer data is read, and when it is determined that the arrival has not occurred before the mandatory arrival time, the data packet is discarded.
  • an object of the disclosed apparatus and method is to reduce delay variation of an output packet when congestion occurs in a packet buffer apparatus that temporarily holds an incoming packet.
  • the queue that temporarily holds the arrived packet, the residence time predicting means that predicts the time that the arrived packet stays in the queue, and the residence time predicting means are determined.
  • a packet buffer device comprising packet discarding means for discarding a packet that arrives when the predicted time exceeds a predetermined first reference value.
  • FIG. 10 is a diagram (part 3) for explaining delay fluctuations that occur in packet discard control based on a residence time
  • FIG. 9 is a diagram (part 4) for explaining delay fluctuations that occur in packet discard control based on a residence time; It is FIG. (5) explaining the delay fluctuation
  • FIG. 6 is a configuration diagram illustrating a second configuration example of the input packet buffer illustrated in FIG. 5. It is a method for explaining a third example of the disclosed packet discarding method.
  • FIG. 6 is a configuration diagram illustrating a third configuration example of the input packet buffer illustrated in FIG. 5. It is a method explaining the 4th example of the packet discard method of an indication.
  • FIG. 6 is a configuration diagram illustrating a fourth configuration example of the input packet buffer illustrated in FIG. 5. It is a method explaining the 5th example of the packet discard method of an indication.
  • FIG. 6 is a configuration diagram illustrating a second configuration example of the input packet buffer illustrated in FIG. 5. It is a method for explaining a third example of the disclosed packet discarding method.
  • FIG. 6 is a configuration diagram illustrating a third configuration example of the input packet buffer illustrated in FIG. 5. It is a method explaining the 4th example of the packet discard method of an indication.
  • FIG. 6 is a configuration diagram illustrating a fourth configuration example of the input packet buffer illustrated in FIG.
  • FIG. 6 is a configuration diagram illustrating a fifth configuration example of the input packet buffer illustrated in FIG. 5. It is a method for explaining a sixth example of the disclosed packet discarding method.
  • FIG. 6 is a configuration diagram illustrating a sixth configuration example of the input packet buffer illustrated in FIG. 5. It is a method explaining the 7th example of the packet discard method of an indication.
  • FIG. 6 is a configuration diagram illustrating a seventh configuration example of the input packet buffer illustrated in FIG. 5. It is a method explaining the 8th example of the packet discard method of an indication.
  • tail drop and RED are known as data discard methods when the packet buffer device is congested.
  • the packet buffer device determines whether the amount of data stored in its internal queue exceeds a specified value. When the amount of data in the queue exceeds a specified value, the packet buffer device discards a packet that arrives thereafter without storing it in the queue.
  • the amount of data stored in the queue may be referred to as “queue length” in the following description. The technical relationship between the queue and the input and / or output packet buffer will be described later.
  • RED is a congestion control method that uses a function of lowering the packet transmission rate when packet discarding occurs in the TCP control of the transmission source device.
  • the packet buffer device discards packets at a certain discard rate as soon as congestion is likely to occur. By doing so, before the congestion increases, the transmission source device is notified of the occurrence of the congestion and the congestion is eliminated.
  • the packet buffer device randomly discards flows at a certain discard rate, thereby simultaneously reducing the rates of all the flows accommodated in this queue, and avoids a phenomenon in which the packet transfer throughput deteriorates.
  • the above tail drop and RED are both packet discard control based on the queue length.
  • a priority is generally given to a queue during QoS control.
  • the output rate of the queue with the lower priority changes in real time depending on the amount of traffic input to the queue with the higher priority.
  • FIG. 1 is a graph illustrating the relationship between output rate fluctuations and delay fluctuations.
  • the solid line shown in FIG. 1 shows the fluctuation of the output rate, and the broken line shows the delay time.
  • the dwell time in the queue that is, the delay increases, and it can be seen that fluctuations in the output rate cause delay fluctuations.
  • the discard control based on the queue length such as the tail drop and the RED has a problem that a delay fluctuation is caused by an output rate fluctuation generated at the time of congestion.
  • FIG. 2 is a diagram for explaining a first example of packet discard control based on the residence time.
  • Reference numeral 1 denotes a packet buffer device
  • reference signs P1 and P2 denote input packets input to the packet buffer device 1.
  • Reference numerals 3-1 to 3-N indicate N queues that temporarily hold input packets
  • reference numeral 2 indicates a packet determination unit
  • reference numeral 4 indicates a packet distribution unit
  • reference numeral 5 indicates Indicates the scheduler.
  • the packet buffer device can be applied to layer 2 and layer 3 packet transfer devices.
  • the packet discriminating unit 2 discriminates whether or not the input packets P1 and P2 comply with the rules regarding the input bandwidth determined for the transmission source user, and classifies the packets into packets that comply with the rules and packets that do not comply with the rules. .
  • the packet discriminating unit 2 marks a packet P1 indicated by a white rectangle that conforms to the rule, and a packet P2 indicated by a hatched rectangle marks a packet that does not comply with the rule. Indicates.
  • the packet distribution unit 4 distributes the input packet to any one of the queues 3-1 to 3-N according to the destination of the input packet, the user, the application, and the like.
  • the scheduler 5 reads out the packets from the queues 3-1 to 3-N and outputs them according to a predetermined priority and output bandwidth.
  • the packet discard control shown in FIG. 2 the residence time in which the packet is currently staying in the queue is measured. When the measured residence time exceeds the reference value, the packet P2 that does not comply with the regulations regarding the input bandwidth is discarded.
  • such discard control may be referred to as “tail drop based on residence time” (Time Based Tail Drop).
  • a discard rate that changes according to the measured residence time is determined, and the packet P2 that does not comply with the regulations regarding the input bandwidth is discarded at the determined discard rate.
  • such discard control may be referred to as “weighted random initial detection based on residence time” (Time Based WRED).
  • WRED is an abbreviation of Weighted Random Early Detection.
  • FIG. 3 is a diagram for explaining a second example of packet discard control based on the residence time.
  • the same components as those shown in FIG. 2 are denoted by the same reference numerals.
  • the packet discard control shown in FIG. 3 the retention time in which the packet is currently staying in the queue is measured, and the packet staying in the queue exceeding the reference value is discarded from the head of the queue.
  • such discard control may be referred to as “head drop based on residence time” (Time Based Head Drop).
  • the packet buffer device 1 performs discard control based on the residence time. At this time, the packet buffer device 1 uses the residence time of the first packet in the queue as the residence time. For this reason, the packet has already accumulated too much in the queue when the retention time of the leading packet exceeds the reference value and the discarding process is started. For this reason, when the disposal process is started, the residence time increases until the queue becomes empty, and when the queue becomes empty, the residence time rapidly decreases again. The reason for this will be described with reference to FIGS. 4A to 4E.
  • 4A to 4E are diagrams for explaining delay fluctuations that occur in packet discard control based on residence time.
  • the queue length of the queue 3-1 tends to increase, but the residence time of the first packet in the queue is still the reference value THTD at which packet discarding starts. Not reached.
  • the packet buffer device 1 starts tail drop or WRED because the residence time of the first packet in the queue 3-1 exceeds the reference value THTD.
  • THTD the reference value
  • the residence time of the packets that have reached the head of the queue continues to increase.
  • the state of FIG. 4D is reached and the queue 3-1 becomes empty, the residence time returns to “0”, and the storage of the packet in the queue is resumed. For this reason, the delay time decreases rapidly.
  • the tail drop based on the residence time and the WRED based on the residence time also have a problem that delay variation occurs at the time of congestion.
  • FIG. 5 is a diagram illustrating the overall configuration of the disclosed switch.
  • the switch 10 is a device that outputs a packet input from any of a plurality of input ports to any of a plurality of output ports.
  • the switch 10 may be a layer 2 switch or a layer 3 switch, for example.
  • Reference numerals 11-1 to 11-L denote input packet buffers
  • reference numeral 12 denotes a packet switching unit 12
  • reference numerals 13-1 to 13-M denote output packet buffers.
  • the L input packet buffers 11-1 to 11-L temporarily hold a packet input from the input port, and after scheduling, input the packet to the packet switching unit 12.
  • the packet switching unit 12 determines an output port to output a packet according to the address information indicated in the input packet, and outputs the packet to an output packet buffer connected to the determined output port.
  • the M output packet buffers 13-1 to 13-M temporarily hold the packet output from the packet switching unit 12, and output it from the output port after scheduling.
  • the packet switching unit 12 may include a packet buffer therein.
  • the packet buffer of the packet switching unit 12 is used to temporarily hold a packet, for example, on any path on the path output from the input port to the input / output port of the packet switching unit 12.
  • either or both of the input packet buffers 11-1 to 11-L and the output packet buffers 13-1 to 13-M may be omitted, and the packet buffers are aggregated in the packet switching unit 12. May be.
  • FIG. 6 is a configuration diagram illustrating a first configuration example of the input packet buffer 11-1 shown in FIG.
  • Other input packet buffers 11-2 to 11-L, output packet buffers 13-1 to 13-M, and packet buffers provided in the packet switching unit may have the same configuration.
  • Reference numeral 21 indicates a queue
  • reference numeral 22 indicates a queue length measurement unit
  • reference numeral 23 indicates a rate measurement unit
  • reference numeral 24 indicates a dwell time prediction unit
  • reference numeral 25 indicates a moving average calculation unit.
  • Reference numeral 26 indicates a packet discarding unit
  • reference numeral P indicates a packet.
  • the input packet buffer 11-1 includes a queue 21, a queue length measurement unit 22, a rate measurement unit 23, a residence time prediction unit 24, a moving average calculation unit 25, and a packet discard unit 26.
  • the queue 21 is a queue for temporarily holding packets input to the input packet buffer 11-1, and holds input packets in a first-in first-out manner.
  • the queue length measurement unit 22 measures the amount of data held in the queue 21, that is, the queue length LQ.
  • the queue length measurement unit 22 may output the weighted moving average value as a measurement result instead of the cue length measurement value itself that is sequentially measured. By using the weighted moving average value, when a sudden change in queue length occurs, the influence can be eliminated and stable control can be performed.
  • the rate measuring unit 23 measures the output rate RO of the packet output from the queue 21.
  • the moving average calculation unit 25 calculates the weighted moving average value TF of the predicted value of the residence time determined by the residence time prediction unit 24.
  • the weighted moving average value of the predicted value of the residence time is referred to as “average predicted value TF”.
  • the packet discard unit 26 performs a discard process before storing the arrival packet in the queue 21 based on the average predicted value TF.
  • Other methods for obtaining the average predicted value TF include a simple average method, a simple exponential average method, and a least square method. It is also possible to apply these methods to the moving average calculation unit 25.
  • FIG. 7 is a method for explaining a first example of the disclosed packet discarding method.
  • the rate measuring unit 23 measures the output rate RO of the packet output from the queue 21. An example of output rate RO measurement processing by the rate measuring unit 23 will be described later.
  • the queue length measurement unit 22 measures the queue length LQ of the queue 21.
  • the moving average calculation unit 25 calculates the average predicted value TF of the residence time determined by the residence time prediction unit 24.
  • the packet discarding unit 26 determines whether or not the average predicted value TF calculated by the moving average calculating unit 25 exceeds a predetermined allowable staying time THT.
  • the input packet buffer 11-1 returns the processing to operation SB.
  • the packet discard unit 26 moves the process to operation SF.
  • operation SF the packet discard unit 26 discards the arrived packet without holding it in the queue 21. That is, the packet discard unit 26 performs tail drop processing based on the predicted value of the packet residence time in the queue 21.
  • the packet discard unit 26 explicitly notifies the packet source device that the congestion has occurred in the switch 10 to the packet transmission source device.
  • the packet discard unit 26 explicitly notifies the transmission source device of the occurrence of congestion according to, for example, a TCP / IP congestion information notification function (Explicit Congestion Notification).
  • the input packet buffer 11-1 returns the processing to operation SB.
  • each of the operations SB to SG may be a step.
  • the staying time of the packet staying in the queue 21 is approximately the permissible staying time THT, so that the delay variation generated in the input packet buffer 11-1 is reduced.
  • TCP control retransmission timeout is measured and packet retransmission is controlled.
  • the delay variation in the input packet buffer provided in the transmission path is reduced, so that stable retransmission control is possible, which contributes to the improvement of the packet throughput.
  • FIG. 8 is a method for explaining a second example of the disclosed packet discarding method.
  • the packet discard unit 26 determines the discard rate of the input packet as follows according to the average predicted value TF.
  • the discard rate is the ratio of the number of packets discarded by the packet discard unit 26 to the total number of input packets per predetermined time.
  • the parameter MinTh is set as a threshold value (predicted value at the start of discarding) of the residence time at which the input packet starts to be discarded.
  • the parameter MaxP is set to the maximum value (maximum discard rate) of the discard rate of the input packet.
  • the parameter MaxTh is set as the residence time (maximum discard predicted value) when the discard rate reaches the maximum discard rate MaxP.
  • the packet discard unit 26 sets the discard rate of packets that can be normally transferred to 0. That is, when TF ⁇ MinTh, the input packet is not discarded.
  • the packet discard unit 26 sets the discard rate to MaxP.
  • the packet discard unit 26 discards the arrived packet at the discard rate determined by SH. That is, the packet discard unit 26 performs WRED based on the predicted value of the packet residence time in the queue 21.
  • the packet discard unit 26 determines whether or not congestion has occurred by determining whether or not the average predicted value TF is greater than MinTh.
  • the input packet buffer 11-1 returns the processing to operation SB.
  • each of the operations SB to SJ may be a step.
  • packet discarding starts when the average predicted value TF exceeds the discard start predicted value MinTh, and the flow of packets from the transmission source device that detected packet discarding The rate is reduced.
  • the average predicted value TF is expected to be excessively large, packets are not accumulated in the queue 21, so that the packet residence time is controlled so as to approach the set values determined in accordance with the above parameters.
  • delay variation occurring in the input packet buffer 11-1 is reduced.
  • FIG. 9 is a configuration diagram illustrating a first configuration example of the rate measuring unit 23 illustrated in FIG.
  • the input packet buffer 11-1 has N queues 21-1 to 21-N for temporarily holding input packets.
  • the queues 21-1 to 21-N are queues for temporarily holding packets input to the input packet buffer 11-1, and classify input packets classified by destination, user, application, etc. Hold each in a first-in first-out manner.
  • Reference numeral 30 represents a rate measurement control unit
  • reference numeral 31 represents a transmission cumulative amount measurement unit
  • reference numeral 32 represents a measured value storage unit
  • reference numeral 33 represents a transmission amount calculation unit
  • reference numeral 34 represents a rate.
  • a calculation part is shown.
  • the rate measurement unit 23 includes a rate measurement control unit 30, a transmission cumulative amount measurement unit 31, a measurement value storage unit 32, a transmission amount calculation unit 33, and a rate calculation unit 34.
  • the rate measurement control unit 30 sequentially selects each of the N queues 21-1 to 21-N periodically as a target queue for measuring the output rate of the packet at a constant measurement period T0.
  • the rate measurement control unit 30 notifies the selected queue to the transmission cumulative amount measurement unit 31 and the measurement value storage unit 32.
  • the transmission cumulative amount measuring unit 31 counts the amount of data transmitted from each of the queues 21-1 to 21-N and obtains the cumulative amount.
  • the cumulative amount of data transmitted from the measurement target queue is output to the measurement value storage unit 32 and the transmission amount calculation unit 33.
  • the measurement value storage unit 32 stores the cumulative amount of transmission data output from the transmission cumulative amount measurement unit 31 for each of the queues 21-1 to 21-N.
  • the accumulated amount of the transmission data amount stored at the previous measurement is output to the transmission amount calculation unit 33.
  • the transmission amount calculation unit 33 receives the cumulative amount of the transmission data amount measured this time from the transmission cumulative amount measurement unit 31 and receives the cumulative amount of the transmission data amount measured last time from the measurement value storage unit 32.
  • the transmission amount calculation unit 33 outputs the calculated transmission data amount to the rate calculation unit 34.
  • the rate calculation unit 34 may output a weighted moving average value of the output rate RO instead of the sequentially calculated output rate RO.
  • a weighted moving average value By using the weighted moving average value, when a sudden rate change occurs, the influence can be eliminated and stable control can be performed. Note that, as another method for obtaining an average value other than the weighted moving average value, a simple average method, a simple exponential average method, a least square method, or the like may be applied.
  • FIG. 10 illustrates a first example of the disclosed rate measurement method.
  • the output rate measured in the operation SB shown in FIG. 7 and FIG. 8 can be measured by the rate measuring method described below with reference to FIG.
  • the rate measurement control unit 30 sequentially selects each of the N queues 21-1 to 21-N periodically as a target queue for measuring the output rate of the packet at a constant measurement period T0. For each selected queue, the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, the transmission amount calculation unit 33, and the rate calculation unit 34 calculate the output rate of the packet, so that the loops SBA to SBF are repeatedly executed.
  • the transmission cumulative amount measuring unit 31 counts the amount of data transmitted from each of the queues 21-1 to 21-N and obtains the cumulative amount.
  • the transmission cumulative amount measuring unit 31 outputs the cumulative amount of data transmitted from the selected measurement target queue to the measured value storage unit 32 and the transmission amount calculating unit 33.
  • the measurement value storage unit 32 stores the cumulative amount of the transmission data amount output from the transmission cumulative amount measurement unit 31 for each of the queues 21-1 to 21-N.
  • the measurement value storage unit 32 outputs the cumulative amount of transmission data stored at the time of the previous measurement for the measurement target queue to the transmission amount calculation unit 33.
  • the transmission amount calculation unit 33 calculates the transmission data amount transmitted from the target queue between the previous measurement time and the current measurement time.
  • the rate calculation unit 34 calculates the output rate RO of the packet output from the measurement target queue from the transmission data amount input from the transmission amount calculation unit 33. Thereafter, rate measurement control unit 30 selects the next queue and returns the process to operation SBB.
  • each of the operations SBA to SBF may be a step.
  • the calculation of the measurement interval can be omitted by measuring the output rate of each queue periodically at regular intervals. Therefore, the processing content can be simplified, and real-time measurement processing for a large number of queues can be performed in a short time.
  • FIG. 11 is a configuration diagram illustrating a second configuration example of the rate measuring unit 23 illustrated in FIG. Also in this embodiment, the input packet buffer 11-1 has N queues 21-1 to 21-N for temporarily holding input packets.
  • Reference numeral 40 indicates a read timing detection unit
  • reference numeral 41 indicates a time measurement unit
  • reference numeral 42 indicates a time storage unit
  • reference numeral 43 indicates a measurement interval calculation unit.
  • the rate measurement unit 23 includes a rate measurement control unit 30, a transmission cumulative amount measurement unit 31, a measurement value storage unit 32, a transmission amount calculation unit 33, a rate calculation unit 34, a read timing detection unit 40, and a time measurement.
  • Unit 41, time storage unit 42, and measurement interval calculation unit 43 is a time measurement control unit 30, a transmission cumulative amount measurement unit 31, a measurement value storage unit 32, a transmission amount calculation unit 33, a rate calculation unit 34, a read timing detection unit 40, and a time measurement.
  • the read timing detection unit 40 notifies the rate measurement control unit 30 of the queue from which the data has been read.
  • the rate measurement control unit 30 notifies the notified queue to the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, and the time storage unit 42 as a queue for which the output rate of the packet is to be measured.
  • the time measuring unit 41 measures the current time.
  • the time storage unit 42 stores the current time as the measurement time of the measurement target queue and the stored previous measurement time as a measurement interval calculation unit. Output to 43.
  • the measurement interval calculation unit 43 calculates the measurement interval T1 at which the measurement is performed for the measurement target queue from the difference between the previous measurement time output from the time storage unit 42 and the current time.
  • the measurement interval calculation unit 43 outputs the calculated measurement interval T1 to the rate calculation unit 34.
  • the rate calculation unit 34 may output a weighted moving average value of the output rate RO instead of the sequentially calculated output rate RO. Note that, as another method for obtaining an average value other than the weighted moving average value, a simple average method, a simple exponential average method, a least square method, or the like may be applied.
  • FIG. 12 illustrates a second example of the disclosed rate measurement method.
  • the output rate measured in the operation SB shown in FIGS. 7 and 8 can be measured by a rate measuring method described below with reference to FIG.
  • the read timing detector 40 detects whether or not data has been read from any one of the queues 21-1 to 21-N.
  • the rate measuring unit 23 returns the processing to operation SCA.
  • the transmission accumulated amount measuring unit 31 When data reading is detected (operation SCA: Y), in operation SCB, the transmission accumulated amount measuring unit 31 counts the amount of data read from the queue where the reading is detected and is accumulated. Find the amount. The transmission cumulative amount measurement unit 31 outputs the cumulative amount of data read from the measurement target queue to the measurement value storage unit 32 and the transmission amount calculation unit 33. In operation SCC, the measurement value storage unit 32 stores the cumulative amount of data output from the transmission cumulative amount measurement unit 31 for each of the queues 21-1 to 21-N.
  • the measurement value storage unit 32 outputs the accumulated amount of read data stored in the previous measurement for the measurement target queue to the transmission amount calculation unit 33.
  • the transmission amount calculation unit 33 calculates the amount of data read from the target queue between the previous measurement time and the current measurement time as the transmission data amount transmitted from this queue.
  • the time measuring unit 41 measures the current time.
  • the time storage unit 42 stores the current time as the measurement time of the measurement target queue and outputs the stored previous measurement time to the measurement interval calculation unit 43.
  • the measurement interval calculation unit 43 calculates the measurement interval T1 at which the measurement is performed on the measurement target queue from the difference between the previous measurement time output from the time storage unit 42 and the current time.
  • the rate calculation unit 34 calculates the output rate RO of the packet output from the measurement target queue from the transmission data amount input from the transmission amount calculation unit 33 and the measurement interval T1 input from the measurement interval calculation unit 43. calculate.
  • the rate calculation unit 34 may output a weighted moving average value of the output rate RO instead of the sequentially calculated output rate RO. By using the weighted moving average value, when a sudden rate change occurs, the influence can be eliminated and stable control can be performed.
  • each of the operations SCA to SCH may be a step.
  • the queue output rate is measured based on the data read amount.
  • data write timing detection means for detecting data write to the queue may be provided, and the output rate may be measured based on the data write amount at the time of data write.
  • the measured values of the output rates of the respective queues are measured at the timing when the measured values of the output rates of the respective queues are changed by measuring the output rates of the respective queues when reading the data from the queues or writing the data to the queues. Can be determined in real time. For this reason, it is possible to improve followability with respect to fluctuations in output rate. Further, useless measurement processing can be omitted when data reading or writing does not occur.
  • FIG. 13 is a configuration diagram illustrating a second configuration example of the input packet buffer 11-1 shown in FIG.
  • Reference numeral 27 indicates a queue length storage unit
  • reference numeral 28 indicates a dwell time measurement unit.
  • the other reference numerals are the same as the constituent elements having the same reference numerals in FIG.
  • the input packet buffer 11-1 includes a queue 21, a queue length measurement unit 22, a residence time prediction unit 24, a moving average calculation unit 25, a packet discard unit 26, a queue length storage unit 27, and a residence time measurement unit 28.
  • the queue length measurement unit 22 For each packet, the queue length measurement unit 22 has a queue length when each packet arrives at the queue 21 (hereinafter referred to as “queue length upon arrival”) and a queue length when the head packet is read from the queue 21 (hereinafter “ Current queue length ”). The queue length measurement unit 22 stores the arrival queue length in the queue length storage unit 27 for each packet.
  • the residence time measuring unit 28 measures the residence time of each packet in the queue 21 by calculating the difference between the arrival time and the read time from the queue 21 for each packet.
  • the queue length measurement unit 22 may output the load moving average value as a measurement result instead of the measurement value itself that is sequentially measured when the arrival queue length and the current queue length are measured.
  • the weighted moving average value as a measurement result in this way, it is possible to prevent the predicted value of the residence time from becoming unstable due to a sudden change in the queue length.
  • a simple average method, a simple exponential average method, a least square method, or the like may be applied as another method for obtaining an average value other than the weighted moving average value.
  • FIG. 14 is a method for explaining a third example of the disclosed packet discarding method.
  • the queue length measurement unit 22 measures the queue length of the queue 21 at the time of packet arrival, that is, the queue length at arrival.
  • the queue length measurement unit 22 stores the arrival queue length in the queue length storage unit 27.
  • the residence time measuring unit 28 measures the residence time of each packet in the queue 21 from the difference between the arrival time of the packet and the queue 21 reading time.
  • the queue length measurement unit 22 measures the queue length when the packet is read from the queue 21, that is, the current queue length for the packet whose arrival queue length is measured in operation SDA.
  • the residence time prediction unit 24 calculates the rate of change of the current queue length with respect to the arrival queue length (current queue length / arrival queue length) for each packet.
  • the residence time prediction unit 24 determines the product of the rate of change measured in operation SDE and the packet residence time as a predicted value of the residence time.
  • the moving average calculation unit 25 calculates the average predicted value TF of the residence time determined by the residence time prediction unit 24.
  • the packet discard unit 26 determines whether or not the average predicted value TF calculated by the moving average calculation unit 25 exceeds a predetermined allowable staying time THT. When the average predicted value TF does not exceed the allowable staying time THT (operation SDG: N), the input packet buffer 11-1 returns the processing to operation SDA.
  • the packet discard unit 26 moves the process to operation SDH.
  • operation SDH the packet discard unit 26 discards the arrived packet without holding it in the queue 21. That is, the packet discarding unit 26 performs tail drop processing based on the predicted residence time.
  • operation SDI when discarding a packet, the packet discard unit 26 explicitly notifies the transmission source device that congestion has occurred in the switch 10. Thereafter, the input packet buffer 11-1 returns the process to the operation SBA.
  • the packet discard unit 26 performs congestion determination by comparing the average predicted value TF with the allowable staying time THT. Instead of this, the packet discarding unit 26 may perform the WRED by determining the discard rate of the input packet according to the average predicted value TF, similarly to the processing of operations SH, SI, SJ, and SG shown in FIG. Good. In another embodiment, each of the operations SDA to SDI may be a step.
  • the residence time prediction unit 24 calculates the prediction value based on the change rate of the queue length, so that the residence time can be predicted in consideration of the change tendency of the queue length.
  • FIG. 15 is a configuration diagram illustrating a third configuration example of the input packet buffer 11-1 shown in FIG.
  • Reference numeral 50 indicates a queue length threshold value determination unit
  • reference numeral 51 indicates a packet discard control unit
  • reference numeral 52 indicates a head drop processing unit 52.
  • the input packet buffer 11-1 includes a packet discrimination unit 2, a packet distribution unit 4, N queues 21-1 to 21-N, a queue length measurement unit 22, and a packet discard unit 26.
  • the input packet buffer 11-1 includes a rate measurement control unit 30, a transmission accumulation amount measurement unit 31, a measurement value storage unit 32, and a transmission amount calculation unit 33.
  • the input packet buffer 11-1 includes a queue length threshold value determination unit 50, a packet discard control unit 51, and a head drop processing unit 52.
  • the functions of the rate measurement control unit 30, the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, and the transmission amount calculation unit 33 are the same as the functions described with reference to FIG. That is, the rate measurement control unit 30, the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, and the transmission amount calculation unit 33, for each of the queues 21-1 to 21-N, for each predetermined measurement cycle T0. Measure the amount of data sent out from the queue.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth rule defined for the transmission source user, and classifies the packet into a packet that complies with the rule and a packet that does not.
  • the packet distributor 4 distributes the input packet to any one of the queues 21-1 to 21-N according to the destination of the input packet, the user, the application, and the like.
  • the head drop processing unit 52 measures the residence time of each packet in the queues 21-1 to 21-N. When the packet stays in the queue exceeding the reference value, the head drop processing unit 52 discards the packet from the head of the queue regardless of whether or not the rules regarding the input bandwidth are observed.
  • the packet discard control unit 51 includes the queue length LQ measured by the queue length measurement unit 22 for each of the queues 21-1 to 21-N, and the queue length threshold determination unit 50 calculates the queues 21-1 to 21-N. It is determined whether or not the long threshold THQ is exceeded. Since the output rate of packets from each of the queues 21-1 to 21-N is equal to (transmission data amount / measurement period T0), when the queue length LQ is longer than the queue length threshold value THQ, the estimated residence time (queue (LQ / output rate) becomes longer than the allowable staying time THT. The packet discard control unit 51 outputs to the packet discard unit 26 an instruction to perform tail drop for a queue whose queue length LQ exceeds the queue length threshold THQ.
  • the packet discard unit 26 does not hold this packet in the queue when a packet that is scheduled to be held in the tail drop and does not comply with the input bandwidth rule is input. Dispose of. Even when a packet that is scheduled to be held in a queue where tail drop is to be performed, the packet discarding unit 26 places this packet in the queue when a packet that complies with the input bandwidth regulations is input. Hold.
  • FIG. 16 is a method for explaining a fourth example of the disclosed packet discarding method.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth specification defined for the transmission source user, and classifies the packet into a packet that complies with the specification and a packet that does not. .
  • the packet discard unit 26 holds a packet that complies with the input bandwidth regulation in a queue.
  • the loops SEB to SFB are repeated for each of the queues 21-1 to 21-N.
  • the rate measurement control unit 30 sets each of the N queues 21-1 to 21-N as a target queue for measuring the output rate of the packet. Selection is periodically performed sequentially at the measurement period T0.
  • the transmission cumulative amount measuring unit 31 counts the amount of data transmitted from each of the queues 21-1 to 21-N and obtains the cumulative amount. In operation SEC, the transmission cumulative amount measurement unit 31 outputs the cumulative amount of data transmitted from the selected measurement target queue to the measurement value storage unit 32 and the transmission amount calculation unit 33. In operation SED, the measurement value storage unit 32 stores the cumulative amount of the transmission data amount output from the transmission cumulative amount measurement unit 31 for each of the queues 21-1 to 21-N.
  • the measurement value storage unit 32 outputs to the transmission amount calculation unit 33 the cumulative amount of transmission data stored for the measurement target queue at the previous measurement.
  • the transmission amount calculation unit 33 calculates the transmission data amount transmitted from the target queue between the previous measurement time and the current measurement time.
  • the queue length threshold value determination unit 50 determines the transmission data amount input from the transmission amount calculation unit 33, the allowable stagnation time THT that is a predetermined constant, and a predetermined measurement cycle T0 for the measurement target queue.
  • the queue length threshold THQ is calculated.
  • the queue length measurement unit 22 measures the queue length LQ of the queue to be measured.
  • the packet discard control unit 51 determines whether or not the queue length LQ of the queue to be measured exceeds the queue length threshold THQ calculated by the queue length threshold determination unit 50.
  • the queue length LQ does not exceed the queue length threshold THQ (operation SEH: N)
  • the input packet buffer 11-1 moves the process to operation SFA.
  • the packet discard unit 26 discards an arrival packet that does not comply with the input bandwidth regulations without holding it in the target queue. To do.
  • the packet discard unit 26 explicitly notifies the source device of the discarded packet that congestion has occurred in the switch 10.
  • the input packet buffer 11-1 moves the process to operation SFA.
  • each of the operations SEA to SFB may be a step.
  • the reference value compared with the packet residence time may be a value longer than the allowable residence time THT.
  • the amount of data transmitted from each queue is measured at a constant predetermined period T0.
  • the calculation circuit of the queue length threshold THQ can be simplified.
  • the head drop processing unit 52 may be omitted. At this time, all packets may be discarded by the packet discard unit 26 regardless of whether or not the rules regarding the input bandwidth are observed.
  • the length of allowable staying time may be varied depending on whether or not the rules regarding the input bandwidth are observed. For example, when determining whether or not to discard a packet that complies with the regulations regarding the input bandwidth, a relatively long allowable staying time may be used as compared with a packet that does not comply. The same applies to the following fourth to seventh configuration examples.
  • FIG. 17 is a configuration diagram illustrating a fourth configuration example of the input packet buffer 11-1 shown in FIG.
  • the input packet buffer 11-1 includes a packet discrimination unit 2, a packet distribution unit 4, N queues 21-1 to 21-N, a queue length measurement unit 22, and a packet discard unit 26.
  • the input packet buffer 11-1 includes a rate measurement control unit 30, a transmission accumulation amount measurement unit 31, a measurement value storage unit 32, and a transmission amount calculation unit 33.
  • the input packet buffer 11-1 includes a read timing detection unit 40, a time measurement unit 41, a time storage unit 42, and a measurement interval calculation unit 43.
  • the input packet buffer 11-1 includes a queue length threshold value determination unit 50, a packet discard control unit 51, and a head drop processing unit 52.
  • Rate measurement control unit 30 transmission cumulative amount measurement unit 31, measurement value storage unit 32, transmission amount calculation unit 33, read timing detection unit 40, time measurement unit 41, time storage unit 42, measurement interval
  • the function of the calculation unit 43 is the same as each function described with reference to FIG.
  • the rate measurement control unit 30 sets the read queue to the amount of data to be transmitted. Specify the queue to be measured.
  • the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, and the transmission amount calculation unit 33 calculate the data amount read from the queue between the current measurement and the previous measurement for the measurement target queue. Calculate as a quantity.
  • the time measurement unit 41, the time storage unit 42, and the measurement interval calculation unit 43 calculate a measurement interval between the current measurement and the previous measurement.
  • the functions of the packet discard control unit 51, the packet discard unit 26, the packet determination unit 2, the packet distribution unit 4, and the head drop processing unit 52 are the same as the functions described with reference to FIG.
  • FIG. 18 illustrates a fifth example of the disclosed packet discarding method.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth specification defined for the transmission source user, and classifies the packet into a packet that complies with the specification and a packet that does not. .
  • the packet discard unit 26 holds a packet that complies with the input bandwidth regulation in a queue.
  • the read timing detection unit 40 detects whether data has been read from any of the queues 21-1 to 21-N. When reading of data is not detected (operation SGB: N), the input packet buffer 11-1 returns the processing to operation SGB.
  • the transmission accumulated amount measuring unit 31 counts the amount of data read from the queue to be measured from which reading is detected, and the accumulated amount. Ask for.
  • the transmission cumulative amount measurement unit 31 outputs the cumulative amount of data read from the measurement target queue to the measurement value storage unit 32 and the transmission amount calculation unit 33.
  • the measurement value storage unit 32 stores the cumulative amount of data output from the transmission cumulative amount measurement unit 31 for each of the queues 21-1 to 21-N.
  • the measurement value storage unit 32 outputs the accumulated amount of read data stored in the previous measurement for the measurement target queue to the transmission amount calculation unit 33.
  • the transmission amount calculation unit 33 calculates the amount of data read from the target queue between the previous measurement time and the current measurement time as the transmission data amount transmitted from this queue.
  • the time measuring unit 41 measures the current time.
  • the time storage unit 42 stores the current time as the measurement time of the measurement target queue, and outputs the stored previous measurement time to the measurement interval calculation unit 43.
  • the measurement interval calculation unit 43 calculates the measurement interval T1 at which the measurement is performed for the measurement target queue from the difference between the previous measurement time output from the time storage unit 42 and the current time.
  • the queue length threshold value determination unit 50 inputs the allowable constant staying time THT, which is a predetermined constant, the transmission data amount input from the transmission amount calculation unit 33, and the measurement interval calculation unit 43, for the measurement target queue.
  • the queue length threshold THQ is calculated according to the measurement interval T1.
  • the subsequent operations SGJ to SHD are the same as operations SEG to SFA shown in FIG.
  • the input packet buffer 11-1 returns the processing to operation SGA.
  • each of the operations SGA to SHD may be a step.
  • the amount of data sent from the queue is measured based on the amount of data read.
  • data write timing detection means for detecting data write to the queue may be provided, and the amount of data sent from the queue may be measured based on the data write amount at the time of data writing. The same applies to the sixth embodiment described below.
  • the queue length threshold THQ when reading data from the queue or writing data to the queue, by determining the queue length threshold THQ, at the timing when traffic to each queue actually occurs, The queue length threshold THQ can be determined in real time. For this reason, it is possible to improve the followability with respect to fluctuations in traffic. Further, useless measurement processing can be omitted when data reading or writing does not occur.
  • FIG. 19 is a configuration diagram illustrating a fifth configuration example of the input packet buffer 11-1 shown in FIG.
  • the input packet buffer 11-1 includes a packet determination unit 2, a packet distribution unit 4, N queues 21-1 to 21-N, a queue length measurement unit 22, a residence time prediction unit 24, a packet discard unit 26.
  • the input packet buffer 11-1 includes a rate measurement control unit 30, a transmission accumulation amount measurement unit 31, a measurement value storage unit 32, and a transmission amount calculation unit 33.
  • the input packet buffer 11-1 includes a read timing detection unit 40, a time measurement unit 41, a time storage unit 42, and a measurement interval calculation unit 43.
  • the input packet buffer 11-1 includes a packet discard control unit 51 and a head drop processing unit 52.
  • the rate measurement control unit 30, the packet discrimination unit 2, the packet distribution unit 4, the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, the transmission amount calculation unit 33, and the head drop processing unit 52 are shown in FIG. It is the same as each element shown in.
  • the queue length measurement unit 22 measures the queue length for the queue to be measured, selected by the rate measurement control unit 30.
  • the residence time prediction unit 24 predicts the residence time according to the queue length measured by the queue length measurement unit 22, the data transmission amount of the measurement target queue measured by the transmission amount calculation unit 33, and the measurement cycle T0.
  • the residence time prediction unit 24 may output the weighted moving average value as the predicted value TF instead of the predicted value TF itself. Note that, as another method for obtaining an average value other than the weighted moving average value, a simple average method, a simple exponential average method, a least square method, or the like may be applied.
  • the packet discard control unit 51 determines the discard rate of the input packet based on the estimated residence time TF.
  • the method for determining the discard rate may be the same as the method described with reference to FIG.
  • the packet discard unit 26 designates this packet as the packet discard control unit 51. Discard at the disposal rate determined by.
  • FIG. 20 illustrates a sixth example of the disclosed packet discarding method.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth specification for the transmission source user, and classifies the packet into a packet that complies with the specification and a packet that does not. To do.
  • the packet discard unit 26 holds a packet that complies with the input bandwidth regulation in a queue.
  • the loops SIB to SJC are repeated for each of the queues 21-1 to 21-N.
  • the rate measurement control unit 30 sets each of the N queues 21-1 to 21-N as a target queue for measuring the packet output rate. Selection is periodically performed sequentially at the measurement period T0.
  • the transmission data amount of the target queue is calculated by the same processing as the processing of operation SEC to operation SEE shown in FIG.
  • the queue length measurement unit 22 measures the queue length for the target queue.
  • the residence time prediction unit 24 performs measurement according to the queue length measured by the queue length measurement unit 22, the data transmission amount of the measurement target queue measured by the transmission amount calculation unit 33, and the measurement cycle T0. A predicted residence time TF for the target queue is calculated.
  • the packet discard control unit 51 determines the discard rate of the input packet based on the estimated residence time TF.
  • the packet discard unit 26 is determined in operation SIH. Dispose of at the disposal rate
  • the packet discard unit 26 performs the same determination as in operation SJ shown in FIG. 8 to determine whether congestion has occurred.
  • operation SIJ: N the input packet buffer 11-1 shifts the processing to operation SJB.
  • operation SIJ: Y the packet discard unit 26 explicitly notifies the apparatus that has transmitted the discard packet that congestion has occurred in the switch 10. Thereafter, the input packet buffer 11-1 shifts the processing to operation SJB.
  • each of the operations SIA to SJB may be a step.
  • FIG. 21 is a configuration diagram illustrating a sixth configuration example of the input packet buffer 11-1 shown in FIG.
  • the input packet buffer 11-1 includes a packet determination unit 2, a packet distribution unit 4, N queues 21-1 to 21-N, a queue length measurement unit 22, a residence time prediction unit 24, a packet discard unit 26.
  • the input packet buffer 11-1 includes a rate measurement control unit 30, a transmission accumulation amount measurement unit 31, a measurement value storage unit 32, and a transmission amount calculation unit 33.
  • the input packet buffer 11-1 includes a read timing detection unit 40, a time measurement unit 41, a time storage unit 42, and a measurement interval calculation unit 43.
  • the input packet buffer 11-1 includes a packet discard control unit 51 and a head drop processing unit 52.
  • the rate measurement control unit 30, the packet discrimination unit 2, the packet distribution unit 4, the transmission cumulative amount measurement unit 31, the measurement value storage unit 32, and the transmission amount calculation unit 33 are the same as the respective elements shown in FIG. It is. Further, the read timing detection unit 40, the time measurement unit 41, the time storage unit 42, the measurement interval calculation unit 43, and the head drop processing unit 52 are the same as the respective elements shown in FIG. The packet discard control unit 51 and the packet discard unit 26 are the same as the respective elements shown in FIG.
  • the queue length measurement unit 22 measures the queue length of the queue to be measured, which is selected by the rate measurement control unit 30.
  • the dwell time predicting unit 24 includes a queue length measured by the queue length measuring unit 22, a data sending amount of the measurement target queue measured by the sending amount calculating unit 33, and a measurement interval determined by the measurement interval calculating unit 43.
  • the residence time prediction unit 24 may output the weighted moving average value as the predicted value TF instead of the predicted value TF itself. Note that, as another method for obtaining an average value other than the weighted moving average value, a simple average method, a simple exponential average method, a least square method, or the like may be applied.
  • FIG. 22 shows a seventh example method of the disclosed packet discarding method.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth specification defined for the transmission source user, and classifies the packet into a packet that complies with the specification and a packet that does not. .
  • the packet discard unit 26 holds a packet that complies with the input bandwidth regulation in a queue.
  • the read timing detection unit 40 detects whether or not data has been read from any one of the queues 21-1 to 21-N. When data reading is not detected (operation SBAB: N), the input packet buffer 11-1 returns the processing to operation SBAB.
  • operation SBAB When data reading is detected (operation SBAB: Y), for the measurement target queue from which reading has been detected, in operations SBAC to SBAH, in the same manner as operations SGC to SGH shown in FIG. The interval T1 is measured.
  • the queue length measurement unit 22 measures the queue length for the target queue.
  • the residence time prediction unit 24 is determined by the queue length measured by the queue length measurement unit 22, the data transmission amount of the measurement target queue measured by the transmission amount calculation unit 33, and the measurement interval calculation unit 43. In accordance with the measured interval T1, the predicted residence time TF for the measurement target queue is calculated.
  • Subsequent operations SBBA to SBBE are the same as operations SIH to SJB shown in FIG. After operation SBBE, input packet buffer 11-1 returns the processing to operation SBAA. In another embodiment, each of the operations SBAA to SBBE may be a step.
  • the head drop processing unit 52 is omitted, and all packets are discarded by the packet discard unit 26 regardless of whether or not the rules regarding the input bandwidth are observed. May be a target.
  • the values of the above-described parameters MinTh, MaxP, and MaxTh used for determining the discard rate may be changed between packets that comply with the regulations regarding the input bandwidth and packets that do not comply with it. For example, when deciding whether to discard packets that comply with the rules regarding input bandwidth, parameters are set so that the discard rate is relatively small compared to packets that do not comply. Also good. The same applies to the following seventh configuration example.
  • the packet discard control unit 51 and the packet discard unit 26 calculate the predicted residence time value TF, and discard the packet at a discard rate according to the predicted residence time value. did. Instead, the packet discard control unit 51 determines whether or not the predicted residence time TF is larger than the allowable staying time THT, and the packet discarding unit 26 satisfies the predicted value TF> the allowable staying time THT. Arriving packets that arrive in the queue may be discarded.
  • FIG. 23 is a configuration diagram illustrating a seventh configuration example of the input packet buffer 11-1 shown in FIG.
  • Reference numeral 60 indicates a time measurement unit
  • reference numeral 61 indicates a time storage unit
  • reference numeral 62 indicates a dwell time calculation unit.
  • the input packet buffer 11-1 includes a packet discrimination unit 2, a packet distribution unit 4, N queues 21-1 to 21-N, a queue length measurement unit 22, a packet discard unit 26, and a queue length storage unit. 27.
  • the input packet buffer 11-1 includes a packet discard control unit 51, a head drop processing unit 52, a time measurement unit 60, a time storage unit 61, and a residence time calculation unit 62.
  • the packet discriminating unit 2, the packet distributing unit 4, the packet discarding unit 26, and the head drop processing unit 52 are the same as the respective elements shown in FIG.
  • the queue length measurement unit 22 measures an arrival time queue length LQA that is a queue length when each packet arrives at the queues 21-1 to 21-N.
  • the queue length measurement unit 22 measures the current queue length LQC, which is the queue length when reading the first packet from the queues 21-1 to 21-N.
  • the queue length measurement unit 22 stores the arrival queue length LQA in the queue length storage unit 27 for each packet.
  • the time measuring unit 60 for each packet the time when each packet arrives at each queue 21-1 to 21-N (hereinafter referred to as "arrival time") and the head packet as each queue 21-1 to 21-N. Measure the time when reading from (referred to as “current time”).
  • the time measuring unit 60 stores the arrival time in the time storage unit 61 for each packet.
  • the residence time calculation unit 62 measures the residence time TS of each packet in each of the queues 21-1 to 21-N by calculating the difference between the arrival time and the current time for each packet.
  • the packet discard control unit 51 determines in advance the queue length LQA upon arrival, the current queue length LQC, and the residence time TS determined by the queue length measurement unit 22 for the packets stored in the respective queues 21-1 to 21-N. Whether or not the following conditional expression (1) is satisfied is determined for each queue based on the allowable remaining time THT. Allowable staying time THT ⁇ arrival queue length LQA ⁇ staying time TS ⁇ current queue length LQC (1)
  • TF (stay time TS ⁇ current queue length LQC / arrival queue length LQA)
  • conditional expression (1) is predicted value TF> stayable allowable time THT. Is equivalent to
  • the packet discard control unit 51 determines whether or not the following conditional expression (2) is satisfied for each queue based on the residence time TS and a predetermined reference value MINTS. Residence time TS> predetermined reference value MINTS (2)
  • the packet discard control unit 51 outputs an instruction to perform a tail drop for the queue satisfying the conditional expressions (1) and (2) to the packet discard unit 26.
  • the residence time TS actually becomes a certain size even if the predicted value TF of the residence time exceeds the allowable residence time THT. If not, packet discard can be stopped.
  • FIG. 24 is a method for explaining an eighth example of the disclosed packet discarding method.
  • the packet discriminating unit 2 discriminates whether or not the input packet complies with the input bandwidth specification defined for the transmission source user, and classifies the packet into a packet that complies with the specification and a packet that does not. To do.
  • the packet discard unit 26 holds a packet that complies with the input bandwidth regulation in a queue.
  • the queue length measurement unit 22 measures the arrival time queue length LQA for each packet arriving at each queue.
  • the queue length measurement unit 22 stores the arrival queue length LQA in the queue length storage unit 27 for each packet.
  • the time measurement unit 60 measures the arrival time when each packet arrives at each queue for each packet.
  • the time measurement unit 60 stores the arrival time in the time storage unit 61 for each packet.
  • the residence time calculation unit 62 measures the residence time TS of each packet in each of the queues 21-1 to 21-N by calculating the difference between the arrival time and the current time for each packet.
  • the queue length measurement unit 22 measures the current queue length LQC when the packet is read from the queue 21 for the packet whose arrival queue length LQA is measured in operation SBCB.
  • the packet discard control unit 51 determines whether both the conditional expression (1) and the conditional expression (2) are satisfied. When one or both of conditional expression (1) and conditional expression (2) are not satisfied (operation SBCH: N), input packet buffer 11-1 moves the process to SBDA.
  • each of the operations SBCA to SBDA may be a step.
  • a division circuit can be dispensed with.
  • the packet discard control unit 51 and the packet discard unit 26 discard a packet when the retention time TS ⁇ arrival queue length LQA is larger than the allowable retention time THT ⁇ current queue length LQC. Instead, the packet discard control unit 51 calculates a predicted value of the stay time based on the stay time TS, the current queue length LQC, and the arrival time queue length LQA, and an input packet corresponding to the predicted value of the stay time. The discard rate may be determined. The packet discard unit 26 may perform WRED processing based on the determined discard rate.
  • the packet discard control unit 51 and the packet discard unit 26 perform the packet discard process only when the conditional expression (2) is satisfied, that is, only when the residence time TS exceeds the predetermined reference value MINTS. It is carried out. Similarly, also in the first to sixth configuration examples, the packet discarding process may be performed only when the residence time TS exceeds the predetermined reference value MINTS.
  • the present invention can be used for a packet buffer device that temporarily holds packets that have arrived.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Multimedia (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

　パケットバッファ装置１１－１は、到着したパケットを一時的に保持するキュー２１と、到着したパケットがキュー２１内に滞留する時間を予測する滞留時間予測手段２４と、滞留時間予測手段２４により決定された予測時間ＴＦが所定の第１基準値ＴＨＴを超えるとき、到着したパケットを廃棄するパケット廃棄手段２６と、を備える。

Description

パケットバッファ装置及びパケット廃棄方法
　本発明は、到着したパケットを一時的に保持するパケットバッファ装置におけるパケットの廃棄方法に関する。
　近年のインターネットの普及に伴い、種々のＷＥＢサーバ、電子メール、ＩＰ電話や動画転送といった様々なサービスを、インターネット上で実現する動きが活発化している。このため、インターネットを支えるネットワークノード装置における、サービス品質（QoS: Quality of Service）制御の重要性がますます高まっている。
　次世代ネットワークなどで提供されるサービスは、原則として、十分なデータ伝送帯域幅をネットワークに用意することによってサービスの品質が保証される。一方で、ＷＥＢサーバによるサービス、ＩＰ電話サービスや動画転送サービスでは、通常のインターネット上でサービスが提供されるため、十分なデータ伝送帯域幅が与えられるとは限らない。
　なお、パケットバッファが輻輳した際のデータ廃棄方法としては、テイルドロップ（Tail Drop）とランダム初期検知（RED: Random Early Detection）が提案されている。また、パケットの滞在時間に応じてパケットの廃棄率を変化させることによりＲＥＤを実施するエッジ・ノード装置が提案されている。さらに、基地局から移動局へ送信するパケットが基地局のバッファに滞留する予定時刻を算出するデータ流入量制御装置が開示されている。さらに、転送データに登録されているデータ受取先での到着必須時刻を読み取り、到着必須時刻までに到着しないと判定したとき、データパケットを廃棄するデータ伝送方法が開示されている。
特開２００５－３４８１６６号公報 特開２００８－５３８５１号公報 特開平９－１８５１０号公報
B.Braden, D.Clark, J.Crowcroft, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC2309, IETF, April 1998
　データ伝送を行うネットワーク上で十分なデータ伝送帯域幅が保証されない環境下では、ネットワーク上で発生する輻輳の影響を受けて、大きな遅延変動が発生する。この遅延変動は遅延ジッタとも呼ばれる。電話サービスや動画提供サービスにおいて大きな遅延変動が発生すると、快適な視聴に支障をきたす。Ｗｅｂサービスにおいても、遅延変動はユーザへのレスポンス時間に影響を与える。また、データ転送においても遅延変動は実効スループットに影響を与え、転送効率を悪化させる要因にもなる。
　このように、輻輳発生時における遅延変動を低減することは、ネットワークのサービス品質を確保する上で重要である。上記問題点に鑑み、開示の装置及び方法は、到着したパケットを一時的に保持するパケットバッファ装置において、輻輳発生時における出力パケットの遅延変動を低減することを目的とする。
　実施例の一形態によれば、到着したパケットを一時的に保持するキューと、到着したパケットがこのキュー内に滞留する時間を予測する滞留時間予測手段と、この滞留時間予測手段により決定された予測時間が所定の第１基準値を超えるとき到着したパケットを廃棄するパケット廃棄手段と、を備えるパケットバッファ装置が与えられる。
　所定時間を超えてキュー内に滞留することが予定される到着パケットを廃棄するため、輻輳が発生しても、パケットバッファ装置において生じる遅延変動が低減される。
出力レートの変動と遅延変動との関係を説明するグラフである。 滞留時間に基づくパケット廃棄制御の第１例を説明する図である。 滞留時間に基づくパケット廃棄制御の第２例を説明する図である。 滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その１）である。 滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その２）である。 滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その３）である。 滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その４）である。 滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その５）である。 開示のスイッチの全体構成を説明する図である。 図５に示す入力パケットバッファの第１構成例を説明する構成図である。 開示のパケット廃棄方法を説明する第１例の方法である。 開示のパケット廃棄方法を説明する第２例の方法である。 図６に示すレート測定部の第１構成例を説明する構成図である。 開示のレート測定方法の第１例説明する方法である。 図６に示すレート測定部の第２構成例を説明する構成図である。 開示のレート測定方法の第２例を説明する方法である。 図５に示す入力パケットバッファの第２構成例を説明する構成図である。 開示のパケット廃棄方法の第３例を説明する方法である。 図５に示す入力パケットバッファの第３構成例を説明する構成図である。 開示のパケット廃棄方法の第４例を説明する方法である。 図５に示す入力パケットバッファの第４構成例を説明する構成図である。 開示のパケット廃棄方法の第５例を説明する方法である。 図５に示す入力パケットバッファの第５構成例を説明する構成図である。 開示のパケット廃棄方法の第６例を説明する方法である。 図５に示す入力パケットバッファの第６構成例を説明する構成図である。 開示のパケット廃棄方法の第７例を説明する方法である。 図５に示す入力パケットバッファの第７構成例を説明する構成図である。 開示のパケット廃棄方法の第８例を説明する方法である。
符号の説明
　１０　　スイッチ
　１１－１～１１－Ｌ　　入力パケットバッファ
　１２　　パケット交換部
　１３－１～１３－Ｌ　　出力パケットバッファ
　２１、２１－１～２１－Ｎ　　キュー
　２２　　キュー長測定部
　２３　　レート測定部
　２４　　滞留時間予測部
　２６　　パケット廃棄部
　Ｐ　　パケット
　以下、添付する図面を参照して実施例を説明する。上述の通り、パケットバッファ装置が輻輳した際のデータ廃棄方法としては、テイルドロップとＲＥＤが知られている。テイルドロップでは、パケットバッファ装置はその内部のキュー内に格納されたデータ量がある規定値を超えるか否かを判定する。キュー内のデータ量が規定値を超えたとき、パケットバッファ装置は、その後に到着するパケットをキュー内に格納せずに廃棄する。なお、キュー内に格納されるデータ量のことを、以下の説明において「キュー長」と示すことがある。なお、キューと、入力および／または出力パケットバッファとの技術的関係については後述する。
　ＲＥＤは、送信元装置のＴＣＰ制御において、パケット廃棄が発生するとパケットの送信レートを下げるという機能を利用する輻輳制御方法である。パケットバッファ装置は、輻輳が発生しそうなとき早めに、ある廃棄率でパケットを廃棄する。そうすることにより、輻輳が大きくなる前に送信元装置に輻輳の発生を通知して輻輳を解消する。すなわち、パケットバッファ装置は、ある廃棄率でランダムにフローを破棄することで、このキューに収容されるフロー全てのレートを同時に下げ、パケット転送のスループットが劣化する現象を避ける。
　上記のテイルドロップ及びＲＥＤは、いずれもキュー長に基づくパケットの廃棄制御である。パケットバッファ装置においては、ＱｏＳ制御の際に、キューに優先度を与えられるのが一般的である。優先度がより低いキューの出力レートは、優先度がより高いキューへ入力されるトラヒック量に依存してリアルタイムに変化する。
　ここで、キュー内の滞在時間は、「キュー内の滞留時間＝キュー長（データ量）／出力レート」で定まるため、遅延変動は出力レートに依存する。図１は、出力レートの変動と遅延変動との関係を説明するグラフである。図１に示す実線が出力レートの変動を示し、破線が遅延時間を示す。図示するとおり、出力レートが増加するに応じてキュー内の滞留時間すなわち遅延が増加し、出力レートの変動が遅延変動を生じることがわかる。このように、上記のテイルドロップやＲＥＤといったキュー長に基づく廃棄制御では、輻輳時に発生する出力レート変動により遅延変動を招いてしまうという問題がある。
　図２は、滞留時間に基づくパケット廃棄制御の第１例を説明する図である。参照符号１はパケットバッファ装置を示し、参照符号Ｐ１及びＰ２はパケットバッファ装置１に入力された入力パケットを示す。参照符号３－１～３－Ｎは、入力パケットを一時的に保持するＮ個のキューを示し、参照符号２はパケット判別部を示し、参照符号４はパケット分配部を示し、参照符号５はスケジューラを示す。なお、このパケットバッファ装置はレイヤ２およびレイヤ３のパケット転送装置に適用可能である。
　パケット判別部２は、入力パケットＰ１、Ｐ２が、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。図２において、パケット判別部２は白抜きの矩形で示すパケットＰ１は規定を遵守しているパケットをマーキングし、ハッチングされた矩形で示すパケットＰ２は、規定を遵守していないパケットをマーキングした例を示す。
　パケット分配部４は、入力パケットの宛先、ユーザ、アプリケーションなどに応じて、入力パケットを、キュー３－１～３－Ｎのいずれかに分配する。スケジューラ５は、所定の優先度や出力帯域幅に応じて、キュー３－１～３－Ｎからパケットを読み出して出力する。図２に示すパケット廃棄制御では、現在、パケットがキューに滞留している滞留時間を測定する。測定された滞留時間が基準値を超える場合には、入力帯域幅に関する規定を遵守していないパケットＰ２を廃棄する。以下、このような廃棄制御を、「滞留時間に基づくテイルドロップ」（Time Based Tail Drop）と呼ぶことがある。
　または、測定された滞留時間に応じて変化する廃棄率を決定し、決定された廃棄率で、入力帯域幅に関する規定を遵守していないパケットＰ２を廃棄する。以下、このような廃棄制御を、「滞留時間に基づく重み付けランダム初期検知」（Time Based WRED）と呼ぶことがある。ＷＲＥＤは、Weighted Random Early Detectionの略である。
　図３は、滞留時間に基づくパケット廃棄制御の第２例を説明する図である。図２に示す構成要素と同じ構成要素に同じ参照符号を付する。図３に示すパケット廃棄制御では、現在、パケットがキューに滞留している滞留時間を測定し、基準値を超えてキュー内に滞留したパケットをキューの先頭から廃棄する。以下、このような廃棄制御を、「滞留時間に基づくヘッドドロップ」（Time Based Head Drop）と呼ぶことがある。
　滞留時間に基づくテイルドロップや滞留時間に基づくＷＲＥＤでは、パケットバッファ装置１は滞留時間に基づいて廃棄制御を行っている。このとき、パケットバッファ装置１は、滞留時間としてキューの先頭パケットの滞留時間を用いていた。このため先頭パケットの滞留時間が基準値を超えて廃棄処理が開始した時点で既にキュー内にパケットがたまり過ぎている。このため、廃棄処理が開始するとキューが空になるまで滞留時間が増加し、キューが空になったときにまた滞留時間が急減する現象が生じていた。この理由を図４Ａ～図４Ｅに沿って説明する。
　図４Ａ～図４Ｅは、滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図である。図４Ａの状態において、パケットの入力レートが出力レートよりも大きいため、キュー３－１のキュー長は増加傾向にあるが、まだ、キューの先頭パケットの滞留時間は、パケット廃棄を始める基準値ＴＨＴＤに達していない。
　その後、図４Ｂの状態になると、キュー３－１のキュー長が図４Ａの状態と比べて増加する。このため、図４Ｂの状態では、図４Ａの状態よりもキュー３－１内に滞留する時間が長くなるため、パケットの遅延時間が長くなる。この様子を図４Ｅに示す。矢印Ａ～Ｄは、それぞれ図４Ａ～４Ｄの状態における遅延時間を示す。
　図４Ｃの状態になると、キュー３－１の先頭パケットの滞留時間が基準値ＴＨＴＤを超えているため、パケットバッファ装置１は、テイルドロップ又はＷＲＥＤを開始する。この結果、キュー３－１にはパケットが入力されなくなるが、キュー３－１内には、すでに多量のパケットが保持されている。このため、キュー３－１内のパケットが全て出力されるまで、キュー先頭に到達したパケットの滞留時間は増加し続ける。そして図４Ｄの状態になり、キュー３－１内が空になると滞留時間が「０」に戻り、キュー内へのパケットの格納が再開される。このため遅延時間が急減する。このように、滞留時間に基づくテイルドロップ及び滞留時間に基づくＷＲＥＤにおいても、輻輳時に遅延変動が発生するという問題があった。
　図５は、開示のスイッチの全体構成を説明する図である。スイッチ１０は、複数の入力ポートのいずれかから入力されたパケットを、複数の出力ポートのいずれかへ出力する装置である。スイッチ１０は、例えばレイヤ２スイッチやレイヤ３スイッチであってよい。参照符号１１－１～１１－Ｌは入力パケットバッファを示し、参照符号１２はパケット交換部１２を示し、参照符号１３－１～１３－Ｍは出力パケットバッファを示す。Ｌ個の入力パケットバッファ１１－１～１１－Ｌは、入力ポートから入力したパケットを一時的に保持し、スケジューリングした後に、パケット交換部１２へ入力する。パケット交換部１２は、入力したパケットに示されるアドレス情報に従って、パケットを出力する出力ポートを決定し、決定された出力ポートに接続される出力パケットバッファへパケットを出力する。Ｍ個の出力パケットバッファ１３－１～１３－Ｍは、パケット交換部１２から出力されたパケットを一時的に保持し、スケジューリングした後に出力ポートから出力する。
　なお、パケット交換部１２が、その内部にパケットバッファを備えていてもよい。パケット交換部１２のパケットバッファは、例えば、パケット交換部１２の入力ポートから入出力ポートから出力される経路上のいずれかにおいて、パケットを一時的に保持するために使用される。また他の実施例では、入力パケットバッファ１１－１～１１－Ｌ及び出力パケットバッファ１３－１～１３－Ｍのいずれか又は両方を省いてもよく、パケット交換部１２内に、パケットバッファを集約してもよい。
　図６は、図５に示す入力パケットバッファ１１－１の第１構成例を説明する構成図である。他の入力パケットバッファ１１－２～１１－Ｌや、出力パケットバッファ１３－１～１３－Ｍや、パケット交換部内に設けられるパケットバッファも同様の構成であってよい。以下の示す、入力パケットバッファ１１－１の第２構成例～第７構成例においても同様である。参照符号２１はキューを示し、参照符号２２はキュー長測定部を示し、参照符号２３はレート測定部を示し、参照符号２４は滞留時間予測部を示し、参照符号２５は移動平均演算部を示し、参照符号２６はパケット廃棄部を示し、参照符号Ｐはパケットを示す。入力パケットバッファ１１－１は、キュー２１、キュー長測定部２２、レート測定部２３、滞留時間予測部２４、移動平均演算部２５及びパケット廃棄部２６を備える。
　キュー２１は、入力パケットバッファ１１－１へ入力されたパケットを一時的に保持するための待ち行列であり、入力パケットを先入れ先出し方式で保持する。キュー長測定部２２は、キュー２１内に保持されているデータ量、すなわちキュー長ＬＱを測定する。キュー長測定部２２は、順次測定されるキュー長の測定値そのものに代えて、その加重移動平均値を測定結果として出力してもよい。加重移動平均値を用いることで突発的なキュー長変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。レート測定部２３は、キュー２１から出力されるパケットの出力レートＲＯを測定する。
　滞留時間予測部２４は、測定されたキュー長ＬＱを出力レートＲＯで除することにより、現時点においてパケットがキュー２１内にどれくらい滞留するかの予測値ＴＦを決定する。すなわち滞留時間予測部２４は、予測値を、（予測値＝キュー長ＬＱ／出力レートＲＯ）により算出する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の予測値の加重移動平均値ＴＦを算出する。以下、滞留時間の予測値の加重移動平均値を「平均予測値ＴＦ」と示す。パケット廃棄部２６は、平均予測値ＴＦに基づいて、到着パケットをキュー２１に格納する前の廃棄処理を行う。なお、平均予測値ＴＦを求める他の方法として単純平均法、簡易指数平均法、最小二乗法などがある。これらの方法を移動平均演算部２５に適用することも可能である。
　図７は、開示のパケット廃棄方法の第１例を説明する方法である。オペレーションＳＢにおいてレート測定部２３は、キュー２１から出力されるパケットの出力レートＲＯを測定する。レート測定部２３による出力レートＲＯの測定処理の例は後述する。オペレーションＳＣにおいてキュー長測定部２２は、キュー２１のキュー長ＬＱを測定する。オペレーションＳＤにおいて滞留時間予測部２４は、（予測値＝キュー長ＬＱ／出力レートＲＯ）により、予測値を算出する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の平均予測値ＴＦを算出する。
　オペレーションＳＥにおいてパケット廃棄部２６は、移動平均演算部２５が算出した平均予測値ＴＦが、所定の滞留可能許容時間ＴＨＴを超えるか否かを判定する。平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えないとき（オペレーションＳＥ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＢに戻す。
　平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えるとき（オペレーションＳＥ：Ｙ）、パケット廃棄部２６は処理をオペレーションＳＦへ移す。オペレーションＳＦにおいてパケット廃棄部２６は、到着したパケットをキュー２１に保持せずに廃棄する。すなわち、パケット廃棄部２６は、キュー２１におけるパケットの滞留時間の予測値に基づくテイルドロップ処理を行う。
　またオペレーションＳＧにおいてパケット廃棄部２６は、パケット廃棄についてこのパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。パケット廃棄部２６は、例えばＴＣＰ／ＩＰの輻輳情報通知機能（Explicit Congestion Notification）に従って、明示的に輻輳の発生を送信元の装置に通知する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢ乃至オペレーションＳＧの各オペレーションはステップであってもよい。
　本実施例によれば、輻輳が発生したときキュー２１内に滞留するパケットの滞留時間はほぼ滞留可能許容時間ＴＨＴ程度となるため、入力パケットバッファ１１－１において生じる遅延変動が低減される。
　ＴＣＰ制御では、再送タイムアウト時間を計測してパケットの再送制御が行われる。本実施例によれば、伝送経路に設けた入力パケットバッファにおける遅延変動が低減されるので、安定した再送制御が可能となり、パケットのスループット向上に資する。
　また、図４Ａ～４Ｅを参照して説明したような、一度、テイルドロップが発生したときキューが空になるまで廃棄が継続する、バースト的な廃棄が抑制される。このためバースト的な廃棄により生じていた、ＴＣＰフローが一斉にレートを下げてしまう現象を回避することが可能となる。
　図８は、開示のパケット廃棄方法の第２例を説明する方法である。オペレーションＳＢ～ＳＤにより、図７に示すオペレーションＳＢ～ＳＤと同様にして、平均予測値ＴＦが決定される。オペレーションＳＨにおいてパケット廃棄部２６は、平均予測値ＴＦに応じて、入力パケットの廃棄率を以下の通り決定する。ここで廃棄率とは、所定時間当たりの入力パケットの全数に対する、パケット廃棄部２６により廃棄されるパケット数の割合である。
　パラメータＭｉｎＴｈを、入力パケットを廃棄し始める滞留時間の予測値の閾値（廃棄開始時予測値）とする。パラメータＭａｘＰを、入力パケットの廃棄率の最大値（最大廃棄率）とする。パラメータＭａｘＴｈを、廃棄率が最大廃棄率ＭａｘＰに至る滞留時間（最大廃棄時予測値）とする。
　平均予測値ＴＦがＭｉｎＴｈ以下であるとき、パケット廃棄部２６は正常に転送可能なパケットの廃棄率を０にする。すなわち、ＴＦ≦ＭｉｎＴｈのとき入力パケットは廃棄されない。平均予測値ＴＦがＭａｘＴｈ以上のとき、パケット廃棄部２６は、廃棄率をＭａｘＰにする。平均予測値ＴＦがＭｉｎＴｈより大きくＭａｘＴｈ未満であるとき、パケット廃棄部２６は、廃棄率を、（廃棄率＝ＭａｘＰ×（平均予測値ＴＦ－ＭｉｎＴｈ）／（ＭａｘＴｈ－ＭｉｎＴｈ））により決定する。
　オペレーションＳＩにおいてパケット廃棄部２６は、到着したパケットをＳＨにて決定した廃棄率で廃棄する。すなわち、パケット廃棄部２６は、キュー２１におけるパケットの滞留時間の予測値に基づくＷＲＥＤを行う。オペレーションＳＪにおいてパケット廃棄部２６は、平均予測値ＴＦがＭｉｎＴｈより大きいか否かを判定することにより、輻輳が発生したか否かを判定する。パケット廃棄部２６が輻輳が発生していないと判定したとき（オペレーションＳＪ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＢに戻す。
　輻輳が発生したと判定したとき（オペレーションＳＪ：Ｙ）、オペレーションＳＧにおいてパケット廃棄部２６は、廃棄パケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢ乃至オペレーションＳＪの各オペレーションはステップであってもよい。
　本実施例によれば、輻輳が発生したとき、平均予測値ＴＦが廃棄開始時予測値ＭｉｎＴｈを超えた頃からパケットの廃棄が開始され、パケット廃棄を検知した送信元装置からのパケットのフローのレートが低減される。この結果、平均予測値ＴＦが過度に大きくなると予想されるときには、キュー２１内にパケットが蓄積されないので、パケットの滞留時間は、上記各パラメータに応じて定まる設定値に近づくように制御される。この結果、入力パケットバッファ１１－１において生じる遅延変動が低減される。
　図９は、図６に示すレート測定部２３の第１構成例を説明する構成図である。本実施例では、入力パケットバッファ１１－１は入力パケットを一時的に保持するためのＮ個のキュー２１－１～２１－Ｎを有している。キュー２１－１～２１－Ｎは、入力パケットバッファ１１－１へ入力されたパケットを一時的に保持するための待ち行列であり、宛先、ユーザ、アプリケーションなどによって分類された入力パケットを、各分類ごとに先入れ先出し方式で保持する。参照符号３０はレート測定制御部を示し、参照符号３１は送出累積量測定部を示し、参照符号３２は測定値記憶部を示し、参照符号３３は送出量算出部を示し、参照符号３４はレート算出部を示す。レート測定部２３は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、レート算出部３４を備える。
　レート測定制御部３０は、Ｎ個のキュー２１－１～２１－Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。レート測定制御部３０は、選択したキューを、送出累積量測定部３１及び測定値記憶部３２へ通知する。送出累積量測定部３１は、各キュー２１－１～２１－Ｎから送出されるデータ量をカウントしてその累積量を求める。レート測定制御部３０から測定対象のキューを通知されたとき、その測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。
　測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１－１～２１－Ｎ毎に記憶する。また、レート測定制御部３０から測定対象のキューを通知されたとき、前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、今回測定した送出データ量の累積量を送出累積量測定部３１から受信し、前回測定した送出データ量の累積量を測定値記憶部３２から受信する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量（＝今回測定した送出データ量の累積値－前回測定した送出データ量の累積値）を算出する。送出量算出部３３は、算出した送出データ量をレート算出部３４へ出力する。
　レート算出部３４は、送出量算出部３３から入力した送出データ量から、測定対象のキューから出力されるパケットの出力レートＲＯ（＝送出データ量／測定周期Ｔ０）を算出し、出力する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。加重移動平均値を用いることで突発的なレート変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。
　図１０は、開示のレート測定方法の第１例を説明する方法である。図７及び図８に示すオペレーションＳＢにおいて測定される出力レートは、図１０を参照して以下に説明するレート測定方法によって測定することができる。
　レート測定制御部３０は、Ｎ個のキュー２１－１～２１－Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。選択された各キューについて、送出累積量測定部３１、測定値記憶部３２、送出量算出部３３及びレート算出部３４が、パケットの出力レートを算出することにより、繰り返しループＳＢＡ～ＳＢＦが実行される。
　送出累積量測定部３１は、各キュー２１－１～２１－Ｎから送出されるデータ量をカウントしてその累積量を求める。オペレーションＳＢＢにおいて送出累積量測定部３１は、選択された測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＢＣにおいて測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１－１～２１－Ｎ毎に記憶する。
　オペレーションＳＢＤにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量を算出する。オペレーションＳＢＥにおいてレート算出部３４は、送出量算出部３３から入力した送出データ量から、測定対象のキューから出力されるパケットの出力レートＲＯを算出する。その後、レート測定制御部３０は、次のキューを選択して処理をオペレーションＳＢＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＡ乃至オペレーションＳＢＦの各オペレーションはステップであってもよい。
　本実施例では、上記の通り、一定間隔で周期的に各キューの出力レートを測定することにより、測定間隔の算出を省略することができる。このため処理内容が簡略化することができ、多数のキューに対するリアルタイムな測定処理を短時間に行うことが可能となる。
　図１１は、図６に示すレート測定部２３の第２構成例を説明する構成図である。本実施例においても、入力パケットバッファ１１－１は入力パケットを一時的に保持するためのＮ個のキュー２１－１～２１－ＮをＮ個有している。参照符号４０は読み出しタイミング検出部を示し、参照符号４１は時刻測定部を示し、参照符号４２は時刻記憶部を示し、参照符号４３は測定間隔算出部を示す。レート測定部２３は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、レート算出部３４と、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。
　送出累積量測定部３１、測定値記憶部３２及び送出量算出部３３の機能は、図９を参照して説明したそれぞれの機能と同様である。読み出しタイミング検出部４０は、各キュー２１－１～２１－Ｎのいずれかからデータの読み出しがあったとき、データが読み出されたキューをレート測定制御部３０に通知する。レート測定制御部３０は、通知されたキューを、パケットの出力レートを測定する対象となるキューとして、送出累積量測定部３１、測定値記憶部３２及び時刻記憶部４２へ通知する。
　時刻測定部４１は現在時刻を測定する。レート測定制御部３０から測定対象のキューを通知されたとき、時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。測定間隔算出部４３は、算出した測定間隔Ｔ１をレート算出部３４へ出力する。
　レート算出部３４は、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１から、測定対象のキューから出力されるパケットの出力レートＲＯ（＝送出データ量／測定間隔Ｔ１）を算出し、出力する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。
　図１２は、開示のレート測定方法の第２例を説明する方法である。図７及び図８に示すオペレーションＳＢにおいて測定される出力レートは、図１２を参照して以下に説明するレート測定方法によって測定することができる。オペレーションＳＣＡにおいて読み出しタイミング検出部４０は、各キュー２１－１～２１－Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＣＡ：Ｎ）、レート測定部２３は処理をオペレーションＳＣＡに戻す。
　データの読み出しが検出されたとき（オペレーションＳＣＡ：Ｙ）、オペレーションＳＣＢにおいて送出累積量測定部３１は、測定対象となる、読み出しが検出されたキューから読み出されたデータ量をカウントしてその累積量を求める。送出累積量測定部３１は、測定対象のキューから読み出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＣＣにおいて測定値記憶部３２は、送出累積量測定部３１から出力されたデータ量の累積量を、各キュー２１－１～２１－Ｎ毎に記憶する。
　オペレーションＳＣＤにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した読み出しデータ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから読み出されたデータ量を、このキューから送出される送出データ量として算出する。
　オペレーションＳＣＥにおいて時刻測定部４１は、現在時刻を測定する。オペレーションＳＣＦにおいて時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。オペレーションＳＣＧにおいて測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。
　オペレーションＳＣＨにおいて、レート算出部３４は、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１から、測定対象のキューから出力されるパケットの出力レートＲＯを算出する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。加重移動平均値を用いることで突発的なレート変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。なお、別な実施の態様においては、上記オペレーションＳＣＡ乃至オペレーションＳＣＨの各オペレーションはステップであってもよい。
　本実施例では、キューからのデータの読み出し時に、データの読み出し量に基づいてキューの出力レートを測定することとした。これに代えて、キューへデータの書き込みを検出するデータ書き込みタイミング検出手段を設けて、データ書き込み時にデータの書き込み量に基づいて出力レートを測定してもよい。
　本実施例では、キューからのデータの読み出し時又は、キューへのデータの書き込み時に各キューの出力レートを測定することにより、各キューの出力レートの測定値が変動するタイミングで、これらの測定値をリアルタイムで決定することができる。このため、出力レートの変動に対する追従性を向上することができる。また、データの読み出しや書き込みが発生しない場合に、無駄な測定処理を省略することができる。
　図１３は、図５に示す入力パケットバッファ１１－１の第２構成例を説明する構成図である。参照符号２７はキュー長記憶部を示し、参照符号２８は滞留時間測定部を示す。他の参照符号は、図６において同じ参照符号を付した構成要素と同様である。入力パケットバッファ１１－１は、キュー２１、キュー長測定部２２、滞留時間予測部２４、移動平均演算部２５、パケット廃棄部２６、キュー長記憶部２７及び滞留時間測定部２８を備える。
　キュー長測定部２２は、パケット毎に、各パケットがキュー２１に到着したときのキュー長（以下「到着時キュー長」と示す）と、先頭パケットをキュー２１から読み出すときのキュー長（以下「現キュー長」と示す）を測定する。キュー長測定部２２は、到着時キュー長を、パケット毎にキュー長記憶部２７に記憶する。
　滞留時間測定部２８は、パケット毎に、その到着時刻とキュー２１からの読み出し時刻との差を算出することにより、キュー２１内における各パケットの滞留時間を測定する。滞留時間予測部２４は、各パケット毎に、到着時キュー長に対する現キュー長の変化率（現キュー長／到着時キュー長）を算出し、この変化率とこのパケットの滞留時間との積を滞留時間の予測値（予測値＝滞留時間×現キュー長／到着時キュー長）として決定する。
　なお、キュー長測定部２２は、到着時キュー長及び現キュー長を測定する際に、順次測定される測定値そのものに代えて、その荷重移動平均値を測定結果として出力してよい。このように加重移動平均値を測定結果として用いることで、突発的なキュー長の変化により滞留時間の予測値が不安定になることが回避される。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。
　図１４は、開示のパケット廃棄方法の第３例を説明する方法である。オペレーションＳＤＡにおいてキュー長測定部２２は、パケット到着時におけるキュー２１のキュー長、すなわち到着時キュー長を測定する。オペレーションＳＤＢにおいてキュー長測定部２２は、到着時キュー長をキュー長記憶部２７に記憶する。
　オペレーションＳＤＣにおいて滞留時間測定部２８は、パケットの到着時刻とキュー２１読み出し時刻の差から、キュー２１内における各パケットの滞留時間を測定する。オペレーションＳＤＤにおいてキュー長測定部２２は、オペレーションＳＤＡにおいて到着時キュー長を測定したパケットについて、このパケットをキュー２１から読み出した時のキュー長、すなわち現キュー長を測定する。
　オペレーションＳＤＥにおいて滞留時間予測部２４は、各パケット毎に、到着時キュー長に対する現キュー長の変化率（現キュー長／到着時キュー長）を算出する。オペレーションＳＤＦにおいて滞留時間予測部２４は、オペレーションＳＤＥで測定した変化率とパケットの滞留時間との積を滞留時間の予測値として決定する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の平均予測値ＴＦを算出する。
　オペレーションＳＤＧにおいてパケット廃棄部２６は、移動平均演算部２５が算出した平均予測値ＴＦが、所定の滞留可能許容時間ＴＨＴを超えるか否かを判定する。平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えないとき（オペレーションＳＤＧ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＤＡに戻す。
　平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えるとき（オペレーションＳＤＧ：Ｙ）、パケット廃棄部２６は処理をオペレーションＳＤＨへ移す。オペレーションＳＤＨにおいてパケット廃棄部２６は、到着したパケットをキュー２１に保持せずに廃棄する。すなわち、パケット廃棄部２６は滞留時間の予測値に基づくテイルドロップ処理を行う。またオペレーションＳＤＩにおいてパケット廃棄部２６は、パケットを廃棄するとき、このパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＢＡに戻す。
　なお、本実施例においてパケット廃棄部２６は、平均予測値ＴＦを滞留可能許容時間ＴＨＴと比較して輻輳判定を行った。これに代えてパケット廃棄部２６は、図８に示すオペレーションＳＨ、ＳＩ、ＳＪ及びＳＧの処理と同様に、平均予測値ＴＦに応じた入力パケットの廃棄率を決定することによってＷＲＥＤを行ってもよい。なお、別な実施の態様においては、上記オペレーションＳＤＡ乃至オペレーションＳＤＩの各オペレーションはステップであってもよい。
　本実施例によれば、滞留時間予測部２４がキュー長の変化率に基づいて予測値を計算することで、キュー長の変化傾向を考慮した滞留時間の予測を行うことが可能となる。
　図１５は、図５に示す入力パケットバッファ１１－１の第３構成例を説明する構成図である。参照符号５０はキュー長閾値決定部を示し、参照符号５１はパケット廃棄制御部を示し、参照符号５２はヘッドドロップ処理部５２を示す。
　入力パケットバッファ１１－１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１－１～２１－Ｎと、キュー長測定部２２と、パケット廃棄部２６とを備える。入力パケットバッファ１１－１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１－１は、キュー長閾値決定部５０と、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。
　レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２及び送出量算出部３３の機能は、図９を参照して説明したそれぞれの機能と同様である。すなわち、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２及び送出量算出部３３は、各キュー２１－１～２１－Ｎについて、所定の測定周期Ｔ０毎に、各キューから出力される送出データ量を測定する。
　パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット分配部４は、入力パケットの宛先、ユーザ、アプリケーションなどに応じて、入力パケットを、キュー２１－１～２１－Ｎのいずれかに分配する。ヘッドドロップ処理部５２は、各パケットのキュー２１－１～２１－Ｎでの滞留時間を測定する。基準値を超えてパケットがキュー内に滞留した場合、ヘッドドロップ処理部５２は、入力帯域幅に関する規定を遵守しているか否かに関わらずパケットをキューの先頭から廃棄する。
　キュー長閾値決定部５０は、各キュー２１－１～２１－Ｎについて、送出量算出部３３が算出した送出データ量を受信する。キュー長閾値決定部５０は、各キュー２１－１～２１－Ｎについて、送出量算出部３３から入力した送出データ量と、所定の定数である滞留可能許容時間ＴＨＴと、所定の測定周期Ｔ０に応じて、キュー長閾値ＴＨＱ（キュー長閾値ＴＨＱ＝滞留可能許容時間ＴＨＴ／測定周期Ｔ０×送出データ量）を算出する。キュー長閾値決定部５０は、キュー長閾値ＴＨＱをパケット廃棄制御部５１へ出力する。
　パケット廃棄制御部５１は、キュー長測定部２２が各キュー２１－１～２１－Ｎについて測定したキュー長ＬＱが、キュー長閾値決定部５０が各キュー２１－１～２１－Ｎについて算出したキュー長閾値ＴＨＱを超えるか否かを判定する。各キュー２１－１～２１－Ｎからのパケットの出力レートは、（送出データ量／測定周期Ｔ０）と等しいため、キュー長ＬＱがキュー長閾値ＴＨＱよりも長い場合、滞留時間の予測値（キュー長ＬＱ／出力レート）が滞留可能許容時間ＴＨＴよりも長くなる。パケット廃棄制御部５１は、パケット廃棄部２６に対して、キュー長ＬＱがキュー長閾値ＴＨＱを超えるキューについてテイルドロップを行う指示を出力する。
　パケット廃棄部２６は、テイルドロップが行われるべきキューへ保持されることを予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、キューに保持せずに廃棄する。パケット廃棄部２６は、テイルドロップが行われるべきキューへ保持することを予定されているパケットであっても、入力帯域幅に関する規定を遵守しているパケットが入力されたとき、このパケットをキューに保持する。
　図１６は、開示のパケット廃棄方法の第４例を説明する方法である。オペレーションＳＥＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。
　以下、各キュー２１－１～２１－Ｎのそれぞれについて、繰り返しループＳＥＢ～ＳＦＢ繰り返す。繰り返しループＳＥＢ～ＳＦＢにて繰り返される各処理において、レート測定制御部３０は、Ｎ個のキュー２１－１～２１－Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。
　送出累積量測定部３１は、各キュー２１－１～２１－Ｎから送出されるデータ量をカウントしてその累積量を求める。オペレーションＳＥＣにおいて送出累積量測定部３１は、選択された測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＥＤにおいて測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１－１～２１－Ｎ毎に記憶する。
　オペレーションＳＥＥにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量を算出する。オペレーションＳＥＦにおいてキュー長閾値決定部５０は、測定対象のキューについて、送出量算出部３３から入力した送出データ量と、所定の定数である滞留可能許容時間ＴＨＴと、所定の測定周期Ｔ０に応じて、キュー長閾値ＴＨＱを算出する。
　オペレーションＳＥＧにおいて、オペレーションＳＣにおいてキュー長測定部２２は、測定対象となるキューのキュー長ＬＱを測定する。オペレーションＳＥＨにおいてパケット廃棄制御部５１は、測定対象となるキューのキュー長ＬＱが、キュー長閾値決定部５０が算出したキュー長閾値ＴＨＱを超えるか否かを判定する。キュー長ＬＱがキュー長閾値ＴＨＱを超えないとき（オペレーションＳＥＨ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＦＡへ移す。
　キュー長ＬＱがキュー長閾値ＴＨＱを超えるとき（オペレーションＳＥＨ：Ｙ）、オペレーションＳＥＩにおいてパケット廃棄部２６は、入力帯域幅に関する規定を遵守していない到着パケットを、対象のキューに保持せずに破棄する。オペレーションＳＥＪにおいてパケット廃棄部２６は、廃棄したパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。入力パケットバッファ１１－１は処理をオペレーションＳＦＡに移す。
　オペレーションＳＦＡにおいてヘッドドロップ処理部５２は、測定対象となるキュー内に保持されたパケットの滞留時間を測定する。基準値を超えてパケットがキュー内に滞留した場合、ヘッドドロップ処理部５２は、入力帯域幅に関する規定を遵守しているか否かに関わらずパケットをキューの先頭から廃棄する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＥＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＥＡ乃至オペレーションＳＦＢの各オペレーションはステップであってもよい。
　ヘッドドロップ処理部５２が、パケットを廃棄するか否かを判定するために、パケットの滞留時間と比較する基準値は、滞留可能許容時間ＴＨＴよりも長い値を使用してよい。このような値を使用することにより、入力帯域幅に関する規定を遵守していないパケットを、入力帯域幅に関する規定を遵守しているパケットよりも先に破棄することができる。
　第３構成例によれば、一定の所定周期Ｔ０で各キューからの送出データ量を測定する。これにより、キュー長閾値ＴＨＱの計算式（キュー長閾値ＴＨＱ＝滞留可能許容時間／測定周期Ｔ０×送出データ量）において、係数（滞留可能許容時間／測定周期Ｔ０）を定数とすることができる。このため、キュー長閾値ＴＨＱの計算回路を簡単化することができる。
　なお、上記構成例において、ヘッドドロップ処理部５２を省略してもよい。このとき、入力帯域幅に関する規定を遵守しているか否かに関わらず、全てのパケットをパケット廃棄部２６による廃棄の対象としてよい。また、入力帯域幅に関する規定を遵守しているか否かに応じて、滞留可能許容時間の長さを異ならせてもよい。例えば、入力帯域幅に関する規定を遵守しているパケットを廃棄するか否かを判定する場合には、遵守していないパケットの場合と比べて、比較的長い滞留可能許容時間を用いてもよい。以下の第４構成例～第７構成例においても同様である。
　図１７は、図５に示す入力パケットバッファ１１－１の第４構成例を説明する構成図である。入力パケットバッファ１１－１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１－１～２１－Ｎと、キュー長測定部２２と、パケット廃棄部２６とを備える。入力パケットバッファ１１－１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１－１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１－１は、キュー長閾値決定部５０と、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。
　レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３の機能は、図１１を参照して説明したそれぞれの機能と同様である。読み出しタイミング検出部４０が、各キュー２１－１～２１－Ｎのいずれかからデータの読み出しがあったことを検出したとき、レート測定制御部３０は、読み出しがあったキューを、送出データ量の測定対象となるキューとして指定する。送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３は、測定対象となるキューについて今回の測定時と前回の測定時の間にキューから読み出されたデータ量を、送出データ量として算出する。時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３は、今回の測定時と前回の測定時の間の測定間隔を算出する。
　キュー長閾値決定部５０は、各キュー２１－１～２１－Ｎについて、送出量算出部３３が算出した送出データ量を受信する。キュー長閾値決定部５０は、各キュー２１－１～２１－Ｎについて、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１に応じて、キュー長閾値ＴＨＱ（キュー長閾値ＴＨＱ＝滞留可能許容時間ＴＨＴ／測定間隔Ｔ１×送出データ量）を算出する。キュー長閾値決定部５０は、キュー長閾値ＴＨＱをパケット廃棄制御部５１へ出力する。
　パケット廃棄制御部５１、パケット廃棄部２６、パケット判別部２、パケット分配部４及びヘッドドロップ処理部５２の機能は、図１５を参照して説明したそれぞれの機能と同様である。
　図１８は、開示のパケット廃棄方法の第５例を説明する方法である。オペレーションＳＧＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。
　オペレーションＳＧＢにおいて読み出しタイミング検出部４０は、各キュー２１－１～２１－Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＧＢ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＧＢに戻す。
　データの読み出しが検出されたとき（オペレーションＳＧＢ：Ｙ）、オペレーションＳＧＣにおいて送出累積量測定部３１は、読み出しが検出された測定対象となるキューから読み出されたデータ量をカウントしてその累積量を求める。送出累積量測定部３１は、測定対象のキューから読み出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＧＤにおいて測定値記憶部３２は、送出累積量測定部３１から出力されたデータ量の累積量を、各キュー２１－１～２１－Ｎ毎に記憶する。
　オペレーションＳＧＥにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した読み出しデータ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから読み出されたデータ量を、このキューから送出される送出データ量として算出する。
　オペレーションＳＧＦにおいて時刻測定部４１は、現在時刻を測定する。オペレーションＳＧＧにおいて時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。オペレーションＳＧＨにおいて測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。
　オペレーションＳＧＩにおいてキュー長閾値決定部５０は、測定対象のキューについて、所定の定数である滞留可能許容時間ＴＨＴと、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１に応じて、キュー長閾値ＴＨＱを算出する。以下に続くオペレーションＳＧＪ～ＳＨＤの処理は、図１６に示すオペレーションＳＥＧ～ＳＦＡと同じである。オペレーションＳＨＤの後、入力パケットバッファ１１－１は処理をオペレーションＳＧＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＧＡ乃至オペレーションＳＨＤの各オペレーションはステップであってもよい。
　なお本実施例では、キューからのデータの読み出し時に、データの読み出し量に基づいてキューからの送出データ量を測定することとした。これに代えて、キューへデータの書き込みを検出するデータ書き込みタイミング検出手段を設けて、データ書き込み時にデータの書き込み量に基づいてキューからの送出データ量を測定してもよい。以下に示す第６実施例においても同様である。
　第４構成例によれば、キューからのデータの読み出し時又は、キューへのデータの書き込み時に、キュー長閾値ＴＨＱを決定することにより、各キューへのトラヒックが実際に生じたタイミングで、これらのキュー長閾値ＴＨＱをリアルタイムで決定することができる。このため、トラヒック量の変動に対する追従性を向上することができる。また、データの読み出しや書き込みが発生しない場合に、無駄な測定処理を省略することができる。
　図１９は、図５に示す入力パケットバッファ１１－１の第５構成例を説明する構成図である。入力パケットバッファ１１－１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１－１～２１－Ｎと、キュー長測定部２２と、滞留時間予測部２４と、パケット廃棄部２６とを備える。入力パケットバッファ１１－１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１－１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１－１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。
　レート測定制御部３０と、パケット判別部２と、パケット分配部４と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、ヘッドドロップ処理部５２は、図１５に示すそれぞれの要素と同様である。キュー長測定部２２は、レート測定制御部３０により選択された、測定対象となるキューについてキュー長を測定する。滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定周期Ｔ０に応じて、滞留時間の予測値ＴＦ（予測値ＴＦ＝キュー長×測定周期Ｔ０／データ送出量）を算出する。滞留時間予測部２４は、この予測値ＴＦそのものに代えて、その加重移動平均値を予測値ＴＦとして出力してよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。
　パケット廃棄制御部５１は、滞留時間の予測値ＴＦに基づいて、入力パケットの廃棄率を決定する。廃棄率の決定方法は、図８を参照して説明した方法と同様であってよい。パケット廃棄部２６は、廃棄率が決定されたキューへ保持されることが予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、パケット廃棄制御部５１により決定された廃棄率で廃棄する。
　図２０は、開示のパケット廃棄方法の第６例を説明する方法である。オペレーションＳＩＡにおいて、パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。
　以下、各キュー２１－１～２１－Ｎのそれぞれについて、繰り返しループＳＩＢ～ＳＪＣを繰り返す。繰り返しループＳＩＢ～ＳＪＣにて繰り返される各処理において、レート測定制御部３０は、Ｎ個のキュー２１－１～２１－Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。
　オペレーションＳＩＣ～オペレーションＳＩＥにおいて、図１６に示すオペレーションＳＥＣ～オペレーションＳＥＥの処理と同様の処理にて、対象となるキューの送出データ量が算出される。オペレーションＳＩＦにおいてキュー長測定部２２は、対象となるキューについてキュー長を測定する。オペレーションＳＩＧにおいて滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定周期Ｔ０に応じて、測定対象のキューについて滞留時間の予測値ＴＦを算出する。
　オペレーションＳＩＨにおいてパケット廃棄制御部５１は、滞留時間の予測値ＴＦに基づいて、入力パケットの廃棄率を決定する。オペレーションＳＩＩにおいてパケット廃棄部２６は、対象となるキューへ保持されることが予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、オペレーションＳＩＨで決定された廃棄率で廃棄する。
　オペレーションＳＩＪにおいてパケット廃棄部２６は、図８に示すオペレーションＳＪと同様の判定を行い輻輳が発生したか否かを判定する。輻輳が発生していないと判定されたとき（オペレーションＳＩＪ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＪＢに移す。輻輳が発生したと判定したとき（オペレーションＳＩＪ：Ｙ）、オペレーションＳＪＡにおいてパケット廃棄部２６は、廃棄パケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＪＢに移す。
　オペレーションＳＪＢにおいてヘッドドロップ処理部５２は、測定対象となるキュー内に保持されたパケットの滞留時間を測定する。ヘッドドロップ処理部５２は、基準値を超えてキュー内に滞留するパケットをキューの先頭から廃棄する。その後、入力パケットバッファ１１－１は処理をオペレーションＳＩＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＩＡ乃至オペレーションＳＪＢの各オペレーションはステップであってもよい。
　図２１は、図５に示す入力パケットバッファ１１－１の第６構成例を説明する構成図である。入力パケットバッファ１１－１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１－１～２１－Ｎと、キュー長測定部２２と、滞留時間予測部２４と、パケット廃棄部２６とを備える。入力パケットバッファ１１－１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１－１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１－１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。
　レート測定制御部３０と、パケット判別部２と、パケット分配部４と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３は、図１７に示すそれぞれの要素と同様である。また、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３と、ヘッドドロップ処理部５２は、図１７に示すそれぞれの要素と同様である。パケット廃棄制御部５１とパケット廃棄部２６は図１９に示すそれぞれの要素と同様である。
　キュー長測定部２２は、レート測定制御部３０により選択された、測定対象となるキューについてキュー長を測定する。滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定間隔算出部４３により決定された測定間隔Ｔ１に応じて、滞留時間の予測値ＴＦ（予測値ＴＦ＝キュー長×測定間隔Ｔ１／データ送出量）を算出する。滞留時間予測部２４は、この予測値ＴＦそのものに代えて、その加重移動平均値を予測値ＴＦとして出力してよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。
　図２２は、開示のパケット廃棄方法の第７例の方法である。オペレーションＳＢＡＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。
　オペレーションＳＢＡＢにおいて読み出しタイミング検出部４０は、各キュー２１－１～２１－Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＢＡＢ：Ｎ）、入力パケットバッファ１１－１は処理をオペレーションＳＢＡＢに戻す。
　データの読み出しが検出されたとき（オペレーションＳＢＡＢ：Ｙ）、読み出しが検出された測定対象のキューについて、オペレーションＳＢＡＣ～ＳＢＡＨにおいて、図１８に示すオペレーションＳＧＣ～ＳＧＨと同様にして、送出データ量と測定間隔Ｔ１が測定される。
　ＳＢＡＩにおいてキュー長測定部２２は、対象となるキューについてキュー長を測定する。オペレーションＳＢＡＪにおいて滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定間隔算出部４３により決定された測定間隔Ｔ１に応じて、測定対象のキューについて滞留時間の予測値ＴＦを算出する。以下に続くオペレーションＳＢＢＡ～ＳＢＢＥの処理は、図２０に示すオペレーションＳＩＨ～ＳＪＢと同じである。オペレーションＳＢＢＥの後、入力パケットバッファ１１－１は処理をオペレーションＳＢＡＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＡＡ乃至オペレーションＳＢＢＥの各オペレーションはステップであってもよい。
　上記第５構成例及び第６構成例においても、ヘッドドロップ処理部５２を省略し、入力帯域幅に関する規定を遵守しているか否かに関わらず、全てのパケットを、パケット廃棄部２６による廃棄の対象としてよい。また、入力帯域幅に関する規定を遵守しているパケットと遵守していないパケットの間で、廃棄率の決定に使用する上述のパラメータＭｉｎＴｈ、ＭａｘＰ及びＭａｘＴｈの値を変えてもよい。例えば、入力帯域幅に関する規定を遵守しているパケットを廃棄するか否かを判定する場合には、遵守していないパケットの場合と比べて、比較的小さい廃棄率となるようにパラメータを定めてもよい。以下の第７構成例においても同様である。
　なお、第５構成例及び第６構成例において、パケット廃棄制御部５１及びパケット廃棄部２６は、滞留時間の予測値ＴＦを算出し、この滞留時間の予測値に応じた廃棄率でパケットを廃棄した。これに代えて、パケット廃棄制御部５１は、滞留時間の予測値ＴＦが滞留可能許容時間ＴＨＴより大きいか否かを判定し、パケット廃棄部２６は、予測値ＴＦ＞滞留可能許容時間ＴＨＴとなるキューに到着する到着パケットを廃棄してもよい。
　図２３は、図５に示す入力パケットバッファ１１－１の第７構成例を説明する構成図である。参照符号６０は時刻測定部を示し、参照符号６１は時刻記憶部を示し、参照符号６２は滞留時間算出部を示す。入力パケットバッファ１１－１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１－１～２１－Ｎと、キュー長測定部２２と、パケット廃棄部２６と、キュー長記憶部２７を備える。入力パケットバッファ１１－１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２と、時刻測定部６０と、時刻記憶部６１と、滞留時間算出部６２を備える。
　パケット判別部２と、パケット分配部４と、パケット廃棄部２６は、ヘッドドロップ処理部５２は、図１５に示すそれぞれの要素と同様である。キュー長測定部２２は、パケット毎に、各パケットがキュー２１－１～２１－Ｎに到着したときのキュー長である、到着時キュー長ＬＱＡを測定する。またキュー長測定部２２は、先頭パケットをキュー２１－１～２１－Ｎから読み出すときのキュー長である、現キュー長ＬＱＣを測定する。キュー長測定部２２は、到着時キュー長ＬＱＡを、各パケット毎にキュー長記憶部２７に記憶する。
　時刻測定部６０は、パケット毎に、各パケットが各キュー２１－１～２１－Ｎに到着したとき時刻（以下「到着時刻」と示す）と、先頭パケットを各キュー２１－１～２１－Ｎからから読み出すときの時刻（以下「現時刻」と示す）を測定する。時刻測定部６０は、到着時刻を、各パケット毎に時刻記憶部６１に記憶する。滞留時間算出部６２は、各パケット毎に、その到着時刻と現時刻との差を算出することにより、各キュー２１－１～２１－Ｎ内における各パケットの滞留時間ＴＳを測定する。
　パケット廃棄制御部５１は、キュー長測定部２２が各キュー２１－１～２１－Ｎに格納されたパケットについて決定された、到着時キュー長ＬＱＡ、現キュー長ＬＱＣ及び滞留時間ＴＳと、予め定めた滞留可能許容時間ＴＨＴとに基づいて、各キュー毎に次の条件式（１）が満たされるか否かを判定する。
　滞留可能許容時間ＴＨＴ×到着時キュー長ＬＱＡ　＜　滞留時間ＴＳ×現キュー長ＬＱＣ　　…（１）
　ここで、滞留時間の予測値ＴＦを、ＴＦ＝（滞留時間ＴＳ×現キュー長ＬＱＣ／到着時キュー長ＬＱＡ）によって決定するとすれば、条件式（１）は予測値ＴＦ＞滞留可能許容時間ＴＨＴと等価である。
　パケット廃棄制御部５１は、滞留時間ＴＳと、所定の基準値ＭＩＮＴＳに基づいて、各キュー毎に、次の条件式（２）が満たされるか否かを判定する。
　滞留時間ＴＳ＞所定の基準値ＭＩＮＴＳ　　…（２）
　パケット廃棄制御部５１は、パケット廃棄部２６に対して、上記条件式（１）及び（２）を満たすキューについてテイルドロップを行う指示を出力する。条件式（１）に加えて条件式（２）を加えることにより、滞留時間の予測値ＴＦが滞留可能許容時間ＴＨＴを超えていても、実際には、滞留時間ＴＳがある程度の大きさになっていない場合にはパケット廃棄を停止することができる。
　図２４は、開示のパケット廃棄方法の第８例を説明する方法である。オペレーションＳＢＣＡにおいて、パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。
　オペレーションＳＢＣＢにおいてキュー長測定部２２は、各キューに到着するパケット毎に到着時キュー長ＬＱＡを測定する。オペレーションＳＢＣＣにおいてキュー長測定部２２は、到着時キュー長ＬＱＡを、各パケット毎にキュー長記憶部２７に記憶する。オペレーションＳＢＣＤにおいて時刻測定部６０は、パケット毎に、各パケットが各キューに到着したときの到着時刻を測定する。オペレーションＳＢＣＥにおいて時刻測定部６０は、到着時刻を、各パケット毎に時刻記憶部６１に記憶する。
　オペレーションＳＢＣＦにおいて滞留時間算出部６２は、各パケット毎に、その到着時刻と現時刻との差を算出することにより、各キュー２１－１～２１－Ｎ内における各パケットの滞留時間ＴＳを測定する。オペレーションＳＢＣＧにおいてキュー長測定部２２は、オペレーションＳＢＣＢにおいて到着時キュー長ＬＱＡを測定したパケットについて、このパケットをキュー２１から読み出した時の現キュー長ＬＱＣを測定する。
　オペレーションＳＢＣＨにおいてパケット廃棄制御部５１は、上記条件式（１）及び条件式（２）の両方が満たされるか否かを判定する。条件式（１）及び条件式（２）の一方又は両方が満たされないとき（オペレーションＳＢＣＨ：Ｎ）、入力パケットバッファ１１－１は処理をＳＢＤＡへ移す。
　条件式（１）及び条件式（２）の両方が満たされるとき（オペレーションＳＢＣＨ：Ｙ）、オペレーションＳＢＣＩにおいてパケット廃棄制御部５１は、条件式（１）及び条件式（２）の両方が満されるキューについてテイルドロップを行う指示をパケット廃棄部２６へ出力する。パケット廃棄部２６は、テイルドロップが行われるキューへ、入力帯域幅に関する規定を遵守していないパケットが到着したとき、このパケットを破棄する。オペレーションＳＢＣＪにおいてパケット廃棄部２６は、廃棄したパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。入力パケットバッファ１１－１は処理をオペレーションＳＢＤＡに移す。オペレーションＳＢＤＡにおいてヘッドドロップ処理部５２は、図１６に示すオペレーションＳＦＡと同様の処理を行う。その後、入力パケットバッファ１１－１は処理をオペレーションＳＢＣＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＣＡ乃至オペレーションＳＢＤＡの各オペレーションはステップであってもよい。
　本実施例によれば、上記条件式を判定する際に除算を用いないので、除算回路を不要とすることができる。
　なお、本実施例においてパケット廃棄制御部５１及びパケット廃棄部２６は、滞留時間ＴＳ×到着時キュー長ＬＱＡが、滞留可能許容時間ＴＨＴ×現キュー長ＬＱＣよりも大きいときパケットを廃棄した。これに代えて、パケット廃棄制御部５１は、滞留時間ＴＳと現キュー長ＬＱＣと到着時キュー長ＬＱＡとに基づき、滞留時間の予測値を算出し、この滞留時間の予測値に応じた入力パケットの廃棄率を決定してよい。また、パケット廃棄部２６は、決定された廃棄率に基づくＷＲＥＤ処理を行ってもよい。
　また本実施例においてパケット廃棄制御部５１及びパケット廃棄部２６は、上記条件式（２）が満たされる場合に限り、すなわち滞留時間ＴＳが所定の基準値ＭＩＮＴＳを超える場合にのみ、パケットの廃棄処理を行っている。同様に、上記の第１構成例～第６構成例においても、滞留時間ＴＳが所定の基準値ＭＩＮＴＳを超える場合にのみ、パケットの廃棄処理を行ってもよい。
　以上、本発明の好適な実施態様について詳述したが、当業者が種々の修正及び変更をなし得ること、並びに、特許請求の範囲は本発明の真の精神および趣旨の範囲内にあるこの様な全ての修正及び変更を包含することは、本発明の範囲に含まれることは当業者に理解されるべきものである。
　　上記実施例の記載に基づき以下のように発明を構成してもよい。
（１）
　到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
　前記滞留時間予測ステップにより決定された予測時間が所定の第１基準値を超えるとき、到着したパケットを廃棄するパケット廃棄ステップと、
　を含むパケット廃棄方法。（図７）
（２）
　前記パケット廃棄ステップは、前記予測時間が前記第１基準値を超える超過量に応じて、到着したパケットを廃棄する割合を変化させる（１）に記載のパケット廃棄方法。（図８）
（３）
　到着したパケットについて予測された前記予測時間が前記第１基準値を超えるとき、前記到着したパケットの送信元装置へ、輻輳の発生を通知する（１）に記載のパケット廃棄方法。
　本発明は、到着したパケットを一時的に保持するパケットバッファ装置に利用可能である。

Claims (14)

  1. 　到着したパケットを一時的に保持するキューと、
    　到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
    　前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超えるとき、到着したパケットを廃棄するパケット廃棄手段と、
    　を備えるパケットバッファ装置。
  2. 　到着したパケットを一時的に保持するキューと、
    　到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
    　前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄手段と、
    　を備えるパケットバッファ装置。
  3. 　前記予測時間が前記第１基準値を超えるとき、到着したパケットの送信元装置へ、輻輳の発生を通知する輻輳発生通知手段を備える請求項１に記載のパケットバッファ装置。
  4. 　前記キューに保持されている到着パケットのデータ量であるキュー長を測定するキュー長測定手段と、
    　キューから出力されるパケットの出力レートを測定するレート測定手段と、を備え、
    　前記滞留時間予測手段は、測定された前記キュー長と測定された前記出力レートとに基づいて、前記予測時間を決定する請求項１～３のいずれか一項に記載のパケットバッファ装置。
  5. 　前記キューに保持されているデータ量であるキュー長を測定するキュー長測定手段と、
    　パケット到着時において測定された前記キュー長を記憶する記憶手段と、
    　前記キュー内に滞留するパケットの滞留時間を測定する滞留時間測定手段と、を備え、
    　前記滞留時間予測手段は、パケット到着時から現時点までの前記キュー長の変化率と、現時点で測定した前記滞留時間とに基づいて、前記予測時間を決定する請求項１～３のいずれか一項に記載のパケットバッファ装置。
  6. 　前記レート測定手段は、一定周期で、前記キューから出力されるパケット量を測定し、各周期間におけるパケット出力量と前記周期に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
  7. 　前記レート測定手段は、前記キューにおけるパケットの書き込み時において前記キューへ書き込まれるパケット累積量を測定し、前回書き込み時と今回書き込み時との間のパケット累積量の差と、前回書き込み時と今回書き込み時との間の時間間隔に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
  8. 　前記レート測定手段は、前記キューにおけるパケットの読み出し時において前記キューから読み出されるパケット累積量を測定し、前回読み出し時と今回読み出し時との間のパケット累積量の差と、前回読み出し時と今回読み出し時との間の時間間隔に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
  9. 　前記レート測定手段は、順次測定した出力レートの測定値の加重平均値を前記出力レートとして出力する請求項４に記載のパケットバッファ装置。
  10. 　前記キュー長測定手段は、順次測定したキュー長の加重平均値を前記キュー長として出力する請求項４又は５に記載のパケットバッファ装置。
  11. 　前記キュー内に滞留するパケットの滞留時間を測定する滞留時間測定手段を備え、
    　前記パケット廃棄手段は、測定される滞留時間が所定の第２基準値未満のとき、前記予測時間が前記第１基準値を超えていても前記パケットを廃棄しない請求項１又は３のいずれか一項に記載のパケットバッファ装置。
  12. 　到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
    　前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超えるとき、到着したパケットを廃棄するパケット廃棄ステップと、
    　を含むパケット廃棄方法。
  13. 　到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
    　前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄ステップと、
    　を含むパケット廃棄方法。
  14. 　到着したパケットについて予測された前記予測時間が前記基準値を超えるとき、前記到着したパケットの送信元装置へ、輻輳の発生を通知する請求項１２に記載のパケット廃棄方法。
PCT/JP2009/052110 2009-02-06 2009-02-06 パケットバッファ装置及びパケット廃棄方法 Ceased WO2010089886A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2010549323A JP5146548B2 (ja) 2009-02-06 2009-02-06 パケットバッファ装置及びパケット廃棄方法
PCT/JP2009/052110 WO2010089886A1 (ja) 2009-02-06 2009-02-06 パケットバッファ装置及びパケット廃棄方法
US13/195,109 US8937962B2 (en) 2009-02-06 2011-08-01 Packet buffering device and packet discarding method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2009/052110 WO2010089886A1 (ja) 2009-02-06 2009-02-06 パケットバッファ装置及びパケット廃棄方法

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US13/195,109 Continuation US8937962B2 (en) 2009-02-06 2011-08-01 Packet buffering device and packet discarding method

Publications (1)

Publication Number Publication Date
WO2010089886A1 true WO2010089886A1 (ja) 2010-08-12

Family

ID=42541807

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2009/052110 Ceased WO2010089886A1 (ja) 2009-02-06 2009-02-06 パケットバッファ装置及びパケット廃棄方法

Country Status (3)

Country Link
US (1) US8937962B2 (ja)
JP (1) JP5146548B2 (ja)
WO (1) WO2010089886A1 (ja)

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120246276A1 (en) * 2011-03-22 2012-09-27 Hitachi, Ltd. Data synchronization server, system, and data transfer bandwidth control method
JP2016201641A (ja) * 2015-04-08 2016-12-01 三菱電機株式会社 通信装置およびバッファ制御方法
JP2020519059A (ja) * 2017-04-11 2020-06-25 テレフオンアクチーボラゲット エルエム エリクソン（パブル） 通信ネットワークにおいてパケットをハンドリングするための、第１の通信ノード、第１の通信ノードによって実施される方法、コンピュータプログラムおよびコンピュータ可読記憶媒体
JP2022523195A (ja) * 2019-02-22 2022-04-21 華為技術有限公司 メモリ管理方法及び装置
US11432196B2 (en) 2017-11-10 2022-08-30 Nec Corporation Control device, control method, and non-transitory computer readable medium storing program
CN116170380A (zh) * 2023-04-21 2023-05-26 中国科学技术大学 基于拥塞预测的ecn标记策略和队列管理方法及系统
JPWO2024142182A1 (ja) * 2022-12-26 2024-07-04
JP2025509699A (ja) * 2022-03-15 2025-04-11 クロックワーク システムズ インコーポレイテッド クロック同期されたエッジベースのネットワーク機能におけるシャドウバッファの展開
US12363015B2 (en) 2021-04-23 2025-07-15 Clockwork Systems, Inc. Clock-synchronized edge-based network functions
JP7786619B2 (ja) 2022-12-26 2025-12-16 Ｎｔｔ株式会社 ネットワーク制御装置、ネットワーク制御方法、および、ネットワーク制御プログラム

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5146548B2 (ja) * 2009-02-06 2013-02-20 富士通株式会社 パケットバッファ装置及びパケット廃棄方法
US20130272121A1 (en) * 2012-04-17 2013-10-17 Cygnus Broadband, Inc. Systems and methods for application-aware admission control in a communication network
US8787163B1 (en) * 2010-02-24 2014-07-22 Marvell International Ltd. Method and apparatus for adjusting the size of a buffer in a network node based on latency
US8537670B2 (en) * 2010-09-14 2013-09-17 George Mason Research Foundation, Inc. Router congestion control
US9391840B2 (en) * 2012-05-02 2016-07-12 Solarflare Communications, Inc. Avoiding delayed data
US20140105218A1 (en) * 2012-10-12 2014-04-17 Prashant H. Anand Queue monitoring to filter the trend for enhanced buffer management and dynamic queue threshold in 4g ip network/equipment for better traffic performance
US9128721B2 (en) * 2012-12-11 2015-09-08 Apple Inc. Closed loop CPU performance control
US9582440B2 (en) 2013-02-10 2017-02-28 Mellanox Technologies Ltd. Credit based low-latency arbitration with data transfer
US9641465B1 (en) * 2013-08-22 2017-05-02 Mellanox Technologies, Ltd Packet switch with reduced latency
US20150256598A1 (en) * 2014-03-10 2015-09-10 JamKazam, Inc. Distributed Recording Server And Related Methods For Interactive Music Systems
US9755932B1 (en) * 2014-09-26 2017-09-05 Juniper Networks, Inc. Monitoring packet residence time and correlating packet residence time to input sources
JP2017028431A (ja) * 2015-07-21 2017-02-02 富士通株式会社 伝送装置及び流量計測方法
US9407585B1 (en) 2015-08-07 2016-08-02 Machine Zone, Inc. Scalable, real-time messaging system
US9602455B2 (en) 2015-08-07 2017-03-21 Machine Zone, Inc. Scalable, real-time messaging system
US9319365B1 (en) * 2015-10-09 2016-04-19 Machine Zone, Inc. Systems and methods for storing and transferring message data
US9602450B1 (en) 2016-05-16 2017-03-21 Machine Zone, Inc. Maintaining persistence of a messaging system
US9608928B1 (en) 2016-07-06 2017-03-28 Machine Zone, Inc. Multiple-speed message channel of messaging system
US9967203B2 (en) 2016-08-08 2018-05-08 Satori Worldwide, Llc Access control for message channels in a messaging system
US10374986B2 (en) 2016-08-23 2019-08-06 Satori Worldwide, Llc Scalable, real-time messaging system
US10305981B2 (en) 2016-08-31 2019-05-28 Satori Worldwide, Llc Data replication in scalable messaging system
US9667681B1 (en) 2016-09-23 2017-05-30 Machine Zone, Inc. Systems and methods for providing messages to multiple subscribers
US11153174B2 (en) * 2018-06-15 2021-10-19 Home Box Office, Inc. Data service overload detection and mitigation
JP6933815B2 (ja) * 2018-08-27 2021-09-08 日本電信電話株式会社 通信制御システム及び通信制御方法
TWI708488B (zh) * 2019-08-20 2020-10-21 智易科技股份有限公司 傳輸系統、傳送裝置及傳輸路徑分配方法
US20210328930A1 (en) * 2020-01-28 2021-10-21 Intel Corporation Predictive queue depth
US11470010B2 (en) 2020-02-06 2022-10-11 Mellanox Technologies, Ltd. Head-of-queue blocking for multiple lossless queues
WO2022259502A1 (ja) * 2021-06-11 2022-12-15 日本電信電話株式会社 パケットキャプチャ装置およびパケットキャプチャ方法
US12474833B2 (en) * 2021-11-02 2025-11-18 Mellanox Technologies, Ltd Queue bandwidth estimation for management of shared buffers and allowing visibility of shared buffer status
US11973696B2 (en) 2022-01-31 2024-04-30 Mellanox Technologies, Ltd. Allocation of shared reserve memory to queues in a network device
US12375404B2 (en) 2022-08-25 2025-07-29 Mellanox Technologies, Ltd Flow-based congestion control

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004532566A (ja) * 2001-04-09 2004-10-21 テレフオンアクチーボラゲット エル エム エリクソン（パブル） キューバッファ制御方法
JP2005027199A (ja) * 2003-07-04 2005-01-27 Ntt Docomo Inc パケット中継装置及びパケット中継方法
WO2005020524A1 (ja) * 2003-08-20 2005-03-03 Nec Corporation セッション中継装置及び中継方法

Family Cites Families (51)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2540930B2 (ja) * 1988-02-19 1996-10-09 日本電気株式会社 輻輳制御装置
AU7206994A (en) * 1993-06-09 1995-01-03 Intelligence At Large, Inc. Method and apparatus for multiple media digital communication system
JP3432955B2 (ja) 1995-06-30 2003-08-04 株式会社東芝 ネットワークシステムのデータ伝送方法および装置
US5859980A (en) * 1996-02-08 1999-01-12 Advanced Micro Devices, Inc. Network interface having adaptive transmit start point for each packet to avoid transmit underflow
US5928327A (en) * 1996-08-08 1999-07-27 Wang; Pong-Sheng System and process for delivering digital data on demand
US5926458A (en) * 1997-01-31 1999-07-20 Bay Networks Method and apparatus for servicing multiple queues
US6075791A (en) * 1997-10-28 2000-06-13 Lucent Technologies Inc. System for guaranteeing data transfer rates and delays in packet networks
US6064676A (en) * 1998-01-14 2000-05-16 Skystream Corporation Remultipelxer cache architecture and memory organization for storing video program bearing transport packets and descriptors
US6292490B1 (en) * 1998-01-14 2001-09-18 Skystream Corporation Receipts and dispatch timing of transport packets in a video program bearing stream remultiplexer
US6477143B1 (en) * 1998-01-25 2002-11-05 Dror Ginossar Method and apparatus for packet network congestion avoidance and control
US6597662B1 (en) * 1998-03-24 2003-07-22 Nortel Networks Limited Apparatus and method for optimizing max-min fair rate control in ABR sessions
JP3711752B2 (ja) * 1998-07-09 2005-11-02 株式会社日立製作所 パケット通信装置
JP2000031997A (ja) * 1998-07-15 2000-01-28 Fujitsu Ltd 帯域管理装置及びその方法
JP3602972B2 (ja) * 1998-07-28 2004-12-15 富士通株式会社 通信性能測定装置及びその測定方法
US7392279B1 (en) * 1999-03-26 2008-06-24 Cisco Technology, Inc. Network traffic shaping using time-based queues
US6570872B1 (en) * 1999-04-06 2003-05-27 Nortel Networks Limited Self-configuring distributed switch
US6768717B1 (en) * 1999-05-28 2004-07-27 Network Equipment Technologies, Inc. Apparatus and method for traffic shaping in a network switch
TW456122B (en) * 1999-11-29 2001-09-21 Jang Jeng Shang Bandwidth division switching device and method
US6690645B1 (en) * 1999-12-06 2004-02-10 Nortel Networks Limited Method and apparatus for active queue management based on desired queue occupancy
EP1240753A1 (en) * 1999-12-13 2002-09-18 Nokia Corporation Congestion control method for a packet-switched network
US6865185B1 (en) * 2000-02-25 2005-03-08 Cisco Technology, Inc. Method and system for queuing traffic in a wireless communications network
US6977895B1 (en) * 2000-03-23 2005-12-20 Cisco Technology, Inc. Apparatus and method for rate-based polling of input interface queues in networking devices
US6738386B1 (en) * 2000-05-11 2004-05-18 Agere Systems Inc. Controlled latency with dynamically limited queue depth based on history and latency estimation
US20020018474A1 (en) * 2000-06-01 2002-02-14 Seabridge Ltd. Efficient packet transmission over ATM
JP3584859B2 (ja) * 2000-06-29 2004-11-04 日本電気株式会社 パケットスケジューリング装置
JP3687501B2 (ja) * 2000-07-05 2005-08-24 日本電気株式会社 パケット交換機の送信キュー管理システム及び管理方法
US6885666B1 (en) * 2000-08-14 2005-04-26 Advanced Micro Devices, Inc. Apparatus and method in a network switch for synchronizing transfer of a control tag to a switch fabric with transfer of frame data to a buffer memory
US6829244B1 (en) * 2000-12-11 2004-12-07 Cisco Technology, Inc. Mechanism for modem pass-through with non-synchronized gateway clocks
JP4512699B2 (ja) * 2001-01-11 2010-07-28 富士通株式会社 フロー制御装置およびノード装置
US7203170B2 (en) * 2001-05-01 2007-04-10 Integrated Device Technology, Inc. Network switch port with weighted random early discard
US6701389B2 (en) * 2001-06-07 2004-03-02 International Business Machines Corporation Bandwidth allocation in accordance with shared queue output limit
JP3908483B2 (ja) * 2001-06-28 2007-04-25 富士通株式会社 通信装置
US6741603B2 (en) * 2001-07-09 2004-05-25 Overture Networks, Inc. Use of a circular buffer to assure in-order delivery of packets
EP1530761A4 (en) * 2001-09-19 2008-01-23 Bay Microsystems Inc VERTICAL PROCESSING OF INSTRUCTIONS AND DATA IN A NETWORK PROCESSOR ARCHITECTURE
US7145914B2 (en) * 2001-12-31 2006-12-05 Maxxan Systems, Incorporated System and method for controlling data paths of a network processor subsystem
US7177274B2 (en) * 2002-06-19 2007-02-13 Telefonaktiebolaget Lm Ericsson (Publ) Methods of transmitting data packets without exceeding a maximum queue time period and related devices
US7376141B2 (en) * 2002-12-17 2008-05-20 Raytheon Company Method and system for encapsulating variable-size packets
JP2004266389A (ja) * 2003-02-28 2004-09-24 Matsushita Electric Ind Co Ltd パケット転送制御方法及びパケット転送制御回路
US7441267B1 (en) * 2003-03-19 2008-10-21 Bbn Technologies Corp. Method and apparatus for controlling the flow of data across a network interface
FR2854296A1 (fr) * 2003-04-24 2004-10-29 France Telecom Procede et dispositif pour differenciation implicite de la qualite de service dans un reseau
US7372865B2 (en) * 2003-07-09 2008-05-13 Fujitsu Limited Processing data packets using time stamped marker packets
DE102004018200A1 (de) * 2004-04-15 2005-11-10 Deutsche Thomson-Brandt Gmbh Verfahren zum Verarbeiten einer Folge von Datenpaketen in einer Empfängervorrichtung sowie Empfängervorrichtung
JP4588365B2 (ja) 2004-06-03 2010-12-01 三菱電機株式会社 エッジ・ノードおよび移動通信システム
JP4446166B2 (ja) * 2004-10-14 2010-04-07 ソニー株式会社 送信装置および方法、記録媒体、プログラム、並びに制御装置
US7660252B1 (en) * 2005-03-17 2010-02-09 Cisco Technology, Inc. System and method for regulating data traffic in a network device
JP2006279514A (ja) * 2005-03-29 2006-10-12 Fujitsu Ltd 通信制御装置および通信制御方法
JP4751791B2 (ja) * 2006-08-22 2011-08-17 株式会社エヌ・ティ・ティ・ドコモ データ流入量制御装置及びデータ流入量制御方法
US20080291833A1 (en) * 2007-05-25 2008-11-27 Gustav Gerald Vos Method for buffer control for network device
JP5083097B2 (ja) * 2008-07-30 2012-11-28 日本電気株式会社 ジッターバッファ制御方法と通信装置
JP5146548B2 (ja) * 2009-02-06 2013-02-20 富士通株式会社 パケットバッファ装置及びパケット廃棄方法
JP5365415B2 (ja) * 2009-08-25 2013-12-11 富士通株式会社 パケット中継装置および輻輳制御方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004532566A (ja) * 2001-04-09 2004-10-21 テレフオンアクチーボラゲット エル エム エリクソン（パブル） キューバッファ制御方法
JP2005027199A (ja) * 2003-07-04 2005-01-27 Ntt Docomo Inc パケット中継装置及びパケット中継方法
WO2005020524A1 (ja) * 2003-08-20 2005-03-03 Nec Corporation セッション中継装置及び中継方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
KAZUMI KUMAZOE ET AL.: "Improving Delay Characteristics of Real-Time Flows by Adaptive Early Packet Discarding", CHARACTERISTICS OF REAL-TIME FLOWS BY ADAPTIVE EARLY PACKET DISCARDING, THE INTERNATIONAL CONFERENCE ON INFORMATION NETWORKING 2006 (ICOIN 2006), vol. 01, pages 463 - 472 *

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120246276A1 (en) * 2011-03-22 2012-09-27 Hitachi, Ltd. Data synchronization server, system, and data transfer bandwidth control method
US8862700B2 (en) * 2011-03-22 2014-10-14 Hitachi, Ltd. Data server, system, and data transfer bandwidth control method
JP2016201641A (ja) * 2015-04-08 2016-12-01 三菱電機株式会社 通信装置およびバッファ制御方法
JP2020519059A (ja) * 2017-04-11 2020-06-25 テレフオンアクチーボラゲット エルエム エリクソン（パブル） 通信ネットワークにおいてパケットをハンドリングするための、第１の通信ノード、第１の通信ノードによって実施される方法、コンピュータプログラムおよびコンピュータ可読記憶媒体
US11924689B2 (en) 2017-11-10 2024-03-05 Nec Corporation Control device, control method, and non-transitory computer readable medium storing program
US11432196B2 (en) 2017-11-10 2022-08-30 Nec Corporation Control device, control method, and non-transitory computer readable medium storing program
US11695710B2 (en) 2019-02-22 2023-07-04 Huawei Technologies Co., Ltd. Buffer management method and apparatus
JP7241194B2 (ja) 2019-02-22 2023-03-16 華為技術有限公司 メモリ管理方法及び装置
JP2022523195A (ja) * 2019-02-22 2022-04-21 華為技術有限公司 メモリ管理方法及び装置
US12363015B2 (en) 2021-04-23 2025-07-15 Clockwork Systems, Inc. Clock-synchronized edge-based network functions
JP2025509699A (ja) * 2022-03-15 2025-04-11 クロックワーク システムズ インコーポレイテッド クロック同期されたエッジベースのネットワーク機能におけるシャドウバッファの展開
JP7710620B2 (ja) 2022-03-15 2025-07-18 クロックワーク システムズ インコーポレイテッド クロック同期されたエッジベースのネットワーク機能におけるシャドウバッファの展開
JPWO2024142182A1 (ja) * 2022-12-26 2024-07-04
WO2024142182A1 (ja) * 2022-12-26 2024-07-04 日本電信電話株式会社 ネットワーク制御装置、ネットワーク制御方法、および、ネットワーク制御プログラム
JP7786619B2 (ja) 2022-12-26 2025-12-16 Ｎｔｔ株式会社 ネットワーク制御装置、ネットワーク制御方法、および、ネットワーク制御プログラム
CN116170380A (zh) * 2023-04-21 2023-05-26 中国科学技术大学 基于拥塞预测的ecn标记策略和队列管理方法及系统
CN116170380B (zh) * 2023-04-21 2023-08-29 中国科学技术大学 基于拥塞预测的ecn标记策略和队列管理方法及系统

Also Published As

Publication number Publication date
JP5146548B2 (ja) 2013-02-20
US8937962B2 (en) 2015-01-20
JPWO2010089886A1 (ja) 2012-08-09
US20110286468A1 (en) 2011-11-24

Similar Documents

Publication Publication Date Title
JP5146548B2 (ja) パケットバッファ装置及びパケット廃棄方法
CN104272680B (zh) 用信号通知拥塞
KR101071898B1 (ko) 네트워크 지연 제어
EP2404238B1 (en) Method and system for i/o driven rate adaptation
US6765905B2 (en) Method for reducing packet data delay variation in an internet protocol network
US7573827B2 (en) Method and apparatus for detecting network congestion
EP2761826B1 (en) Attribution of congestion contributions
EP2237496A1 (en) Pre-congestion notification (PCN) as a base for admission control and flow termination
US20160057065A1 (en) Re-marking of packets for queue control
JP2012160987A (ja) 帯域監視装置、及びパケット中継装置
CN101567851B (zh) 用于调整数据业务流的传输速度的方法和设备
KR101333856B1 (ko) 트래픽 부하를 관리하는 방법
US7035216B2 (en) Congestion control unit
JP7211765B2 (ja) パケット転送装置、方法、及びプログラム
GB2535819A (en) Monitoring network conditions
EP2985963A1 (en) Packet scheduling networking device
Sup et al. Explicit non-congestion notification: A new AQM approach for TCP networks
Agarwal et al. Link utilization based AQM and its performance
Barakat et al. A markovian model for TCP analysis in a differentiated services network
US20100214914A1 (en) Method of bandwidth management in packet networks
JP3813473B2 (ja) パケット廃棄装置
JP4977677B2 (ja) エッジノードおよび帯域制御方法
Fgee et al. Selective Early Detection (SED) Queue Management Algorithm: A Modified Version of (RED)
Kim et al. An active queue management for QoS guarantee of the high priority service class
JP3739324B2 (ja) セッション数比率ＱｏＳ制御方法、プログラム、および音声ゲートウェイ装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 09839663

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2010549323

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 09839663

Country of ref document: EP

Kind code of ref document: A1