# US 8,149,856 B2 · Packet relay device and queue scheduling method > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,149,856 B2 - Document ID: US8149856B2 - Status: Granted - Kind: B2 - Application number: 12/566,277 - Filed: 2009-09-24 - Published: 2010-01-21 - Granted: 2012-04-03 - Earliest claimed: 2007-03-27 - Assignees: Fujitsu Limited - Inventors: Hiroyuki Kogata; Hisaya Ogasawara; Akio Shinohara - Web page: https://patentgrep.com/patent/US8149856B2 ## CPC - H04L 49/90: Buffering arrangements - H04L 47/50: Queue scheduling - H04L 47/623: {Weighted service order} - H04L 49/901: using storage descriptor, e.g. read or write pointers - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Each of the plurality of queues stores packet data of a received packet. The read concession assignor assigns one of the plurality of queues with a read concession for a predefined time period. The overdraft storage stores an overdraft amount in connection with each of the plurality of queues. The read adequacy determiner determines, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue. The overdraft updater updates at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession. ## Claims ### Claim 1 A packet relay device for relaying a packet, the packet relay device comprising: a plurality of queues each for storing packet data of a received packet; a read concession assignor for assigning one of the plurality of queues with a read concession for a predefined time period, the read concession allowing the packet relay device to read packet data stored in a queue assigned with the read concession; an overdraft storage for storing an overdraft amount in connection with each of the plurality of queues, the overdraft amount indicating an amount of packet data read from a queue during a time period while another queue is assigned with the read concession; a read adequacy determiner for determining, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue; and an overdraft updater for updating at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession. ### Claim 2 (depends on 1) The packet relay device of claim 1, wherein the read concession assignor assigns one of the plurality of queues with the read concession in accordance with weights predefined for each of the plurality of queues. ### Claim 3 (depends on 1) The packet relay device of claim 1, wherein the read concession assignor assigns, when more than one queue out of the plurality of queues is nonempty, one of the more than one queue with the read concession for the predefined time period in accordance with weights predefined for each of the more than one queue. ### Claim 4 (depends on 1) The packet relay device of claim 1, wherein the read adequacy determiner determines to read packet data from the one queue when the overdraft amount stored in connection with the one queue is nonpositive. ### Claim 5 (depends on 1) The packet relay device of claim 1, wherein the overdraft updater adds to the first overdraft amount an amount of packet data read from the first queue during the time period while the second queue is assigned with the read concession, and subtracts from the second overdraft amount the amount of packet data read from the first queue. ### Claim 6 (depends on 1) The packet relay device of claim 1, wherein the plurality of queues consists of a primary queue and a secondary queue, the overdraft storage stores one overdraft amount, the read adequacy determiner determines to read packet data from the secondary queue when the one overdraft amount is nonnegative, and the overdraft updater adds to the one overdraft amount an amount of packet data read from the primary queue during a time period while the secondary queue is assigned with the read concession, and subtracts from the one overdraft amount an amount of packet data read from the secondary queue during a time period while the primary queue is assigned with the read concession. ### Claim 7 (depends on 1) The packet relay device of claim 1, wherein the plurality of queues consists of a primary queue and a secondary queue, and the overdraft updater adds to a primary overdraft amount stored in connection with the primary queue an amount of packet data read from the primary queue during a time period while the secondary queue is assigned with the read concession when a secondary overdraft amount stored in connection with the secondary queue is nonpositive, and subtracts from the secondary overdraft amount the amount of packet data read from the primary queue when the secondary overdraft amount is positive. ### Claim 8 A queue scheduling method executed by a packet relay device for relaying a packet, the packet relay device including a plurality of queues each for storing packet data of a received packet, the queue scheduling method comprising: assigning one of the plurality of queues with a read concession for a predefined time period, the read concession allowing the packet relay device to read packet data stored in a queue assigned with the read concession; storing an overdraft amount in connection with each of the plurality of queues, the overdraft amount indicating an amount of packet data read from a queue during a time period while another queue is assigned with the read concession; determining, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue; and updating at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession. ### Claim 9 (depends on 8) The queue scheduling method of claim 8, wherein in the assigning one of the plurality of queues with the read concession, the one of the plurality of queues is assigned with the read concession in accordance with weights predefined for each of the plurality of queues. ### Claim 10 (depends on 8) The queue scheduling method of claim 8, wherein in the assigning one of the plurality of queues with the read concession, when more than one queue out of the plurality of queues is nonempty, the one of the more than one queue is assigned with the read concession for the predefined time period in accordance with weights predefined for each of the more than one queue. ### Claim 11 (depends on 8) The queue scheduling method of claim 8, wherein in the determining whether to read packet data from the one queue, it is determined to read packet data from the one queue when the overdraft amount stored in connection with the one queue is nonpositive. ### Claim 12 (depends on 8) The queue scheduling method of claim 8, wherein in the updating at least one of the first overdraft amount and the second overdraft amount, an amount of packet data read from the first queue during the time period while the second queue is assigned with the read concession is added to the first overdraft amount, and the amount of packet data read from the first queue is subtracted from the second overdraft amount. ### Claim 13 (depends on 8) The queue scheduling method of claim 8, wherein the plurality of queues consists of a primary queue and a secondary queue, one overdraft amount is stored in the storing the overdraft amount, it is determined to read packet data from the secondary queue when the one overdraft amount is nonnegative in the determining whether to read packet data from the one queue, and in the updating at least one of the first overdraft amount and the second overdraft amount, an amount of packet data read from the primary queue during a time period while the secondary queue is assigned with the read concession is added to the one overdraft amount, and an amount of packet data read from the secondary queue during a time period while the primary queue is assigned with the read concession is subtracted from the one overdraft amount. ### Claim 14 (depends on 8) The queue scheduling method of claim 8, wherein the plurality of queues consists of a primary queue and a secondary queue, and in the updating at least one of the first overdraft amount and the second overdraft amount, an amount of packet data read from the primary queue during a time period while the secondary queue is assigned with the read concession is added to a primary overdraft amount stored in connection with the primary queue when a secondary overdraft amount stored in connection with the secondary queue is nonpositive, and the amount of packet data read from the primary queue is subtracted from the secondary overdraft amount when the secondary overdraft amount is positive. ### Claim 15 A non-transitory computer-readable medium storing a program that causes a computer to execute a queue scheduling method, the computer serving as a packet relay device for relaying a packet, the computer including a plurality of queues each for storing packet data of a received packet, the queue scheduling method including: assigning one of the plurality of queues with a read concession for a predefined time period, the read concession allowing the packet relay device to read packet data stored in a queue assigned with the read concession, storing an overdraft amount in connection with each of the plurality of queues, the overdraft amount indicating an amount of packet data read from a queue during a time period while another queue is assigned with the read concession, determining, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue, and updating at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein in the assigning one of the plurality of queues with the read concession, the one of the plurality of queues is assigned with the read concession in accordance with weights predefined for each of the plurality of queues. ### Claim 17 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein in the assigning one of the plurality of queues with the read concession, when more than one queue out of the plurality of queues is nonempty, the one of the more than one queue is assigned with the read concession for the predefined time period in accordance with weights predefined for each of the more than one queue. ### Claim 18 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein in the determining whether to read packet data from the one queue, it is determined to read packet data from the one queue when the overdraft amount stored in connection with the one queue is nonpositive. ### Claim 19 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein in the updating at least one of a first overdraft amount and a second overdraft amount, an amount of packet data read from the first queue during the time period while the second queue is assigned with the read concession is added to the first overdraft amount, and the amount of packet data read from the first queue is subtracted from the second overdraft amount. ### Claim 20 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the plurality of queues consists of a primary queue and a secondary queue, one overdraft amount is stored in the storing the overdraft amount, it is determined to read packet data from the secondary queue when the one overdraft amount is nonnegative in the determining whether to read packet data from the one queue, and in the updating at least one of a first overdraft amount and a second overdraft amount, an amount of packet data read from the primary queue during a time period while the secondary queue is assigned with the read concession is added to the one overdraft amount, and an amount of packet data read from the secondary queue during a time period while the primary queue is assigned with the read concession is subtracted from the one overdraft amount.