Patent ID: 8761012

Claim:
A packet relay apparatus configured to relay a packet by utilizing a multi-stage queue structure, comprising: a receiver configured to receive a packet; a determiner configured to determine whether to drop the received packet at a latter stage, based on former-stage queue information representing a state of a former-stage queue at any former stage to which the received packet belongs, and latter-stage queue information including a drop probability and representing a state of a latter-stage queue at the latter stage to which the received packet belongs; a buffer memory configured to hold the received packet on the basis of the determination by the determiner; and a queuing controller configured to queue the received packet into the former-stage queue or the latter-stage queue in the buffer memory if the determiner determines not to drop the received packet, wherein when an average queue length is less than a maximum threshold value and greater than a minimum threshold value which is decreased by a drop threshold weight, the drop probability DP is defined as DP=(MAX_DP+β)( Q AVE−MIN_TH( N+ 1)+β)/(MAX_TH( N+ 1)−MIN_TH( N+ 1)+β), wherein MAX_DP is a maximum drop probability, α is the drop probability weight, β is the drop threshold weight, QAVE is the average queue length, MAX_TH(N+1) is the maximum threshold value, and MIN_TH(N+1) is the minimum threshold value.