# US 2009/0257441 A1 · Packet forwarding apparatus and method for discarding packets

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2009/0257441 A1
- Document ID: US20090257441A1
- Status: Published application
- Kind: A1
- Application number: 12/361,655
- Filed: 2009-01-29
- Published: 2009-10-15
- Earliest claimed: 2008-04-15
- Assignees: Fujitsu Limited
- Inventors: Akihiro Hata; Hiroshi Tomonaga; Katsumi Imamura
- Web page: https://patentgrep.com/patent/US20090257441A1

## CPC

- H04L 47/10: Flow control; Congestion control
- H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT]
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 49/90: Buffering arrangements
- H04L 49/9047: including multiple buffers, e.g. buffer pools
- H04L 49/9078: {using an external memory or storage device}
- H04L 49/254: {Centralised controller, i.e. arbitration or scheduling}
- H04L 49/503: {Policing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The packet forwarding apparatus of the present invention includes a packet buffer for temporarily storing packets to be forwarded, a timer for measuring the time of every predetermined unit period, a plurality of first queues corresponding to each of a plurality of address groups that form the packet buffer, a plurality of second queues that are provided corresponding to the property of the packets, a first controller for executing the writing of the packets, and a second controller for executing the discarding of the packets. According to this invention, through managing the first queues and the second queues, packets in the packet buffer can be discarded without the packets being read from the packet buffer.

## Claims

### Claim 1

A packet forwarding apparatus, comprising:
a packet buffer for temporarily storing packets to be forwarded;
a timer for measuring the time of every predetermined unit period;
a plurality of first queues, each first queue corresponding to each of a plurality of address groups that form the packet buffer, each first queue managing the order of writing packets to the addresses in the corresponding address group;
a plurality of second queues, each second queue corresponding to property of packets, each second queue managing the order for reading packets from the addresses that have been written to the addresses of the packet buffer;
a first controller for associating each address group with a write period by switching an address group to be written in every unit period, writing packets to the address group to which the packets are to be written according to the order of the addresses indicated by the first queue corresponding to that address group, and adding the addresses that have been written to a second queue that corresponds to the property of the packets; and
a second controller for calculating a residence period of the packet of the first address indicated by the second queue in the packet buffer based on a first write period specified from the address group to which the first address belongs and the present time indicated by the timer, and removing all addresses written within the first write period from the second queue when packets are determined to be discarded based on the residence period.

### Claim 2 (depends on 1)

The packet forwarding apparatus according to claim 1, wherein:
pointers are provided having pointer addresses corresponding to each address of the packet buffer;
the first queue is formed by a link list through pointers corresponding to addresses, out of the corresponding address groups, to which packets can be written;
the first controller writes packets in addresses of the packet buffer corresponding to pointers on the link list of the first queue corresponding to the write period at a time when writing packets, disconnects these pointers from the link list of the first queue, and form the second queue through these pointers as a link list formed by the pointers; and
the second controller disconnects all pointers connected to a second queue that are in the same write period as the start pointer of the second queue from the second queue when packets are determined to be discarded based on this start pointer, and connects these pointers to the first queue.

### Claim 3 (depends on 1)

The packet forwarding apparatus according to claim 1, further comprising:
a first counter for counting the number of packets written to the packet buffer within a period; and
a second counter for counting the number of packets read from the packet buffer, out of the packets written in the packet buffer within said period, wherein the number of packets discarded in said period is calculated by subtracting the value counted by the second counter from the value counted by the first counter.

### Claim 4 (depends on 1)

The packet forwarding apparatus according to claim 1, wherein
priority for each of the plurality of the second queues is set in advance based on the property of the packets; and
when the discarding of packets in a period is determined based on two or more second queues, a process with respect to these two or more second queues in that period is performed according to the order of the priority.

### Claim 5 (depends on 1)

The packet forwarding apparatus according to claim 1, wherein
the process with respect to the plurality of the second queues of the first controller and the second controller is performed by time-sharing within the unit period.

### Claim 6 (depends on 1)

The packet forwarding apparatus according to claim 1, wherein
a delay threshold that is compared with the residence period when judging about the discarding of a packet is set in advance for each of the plurality of the second queues.

### Claim 7 (depends on 1)

The packet forwarding apparatus according to claim 1, wherein
when the predetermined unit period is set to be T1 and the maximum delay period allowed for a packet is set to be T2, the number of the first queues provided is equal to or above T2/T1.

### Claim 8

A method for discarding packets for a packet forwarding apparatus comprising a packet buffer for temporarily storing packets to be forwarded, and a timer for measuring the time of every predetermined unit period, the method for discarding packets comprising:
providing a plurality of first queues, each first queue corresponding to each of a plurality of address groups that form the packet buffer, each first queue managing the order of writing packets to the addresses in the corresponding address group;
providing a plurality of second queues corresponding to the property of the packets;
switching an address group to be written in every unit period, and writing packets to the address group to be written according to the order of the addresses indicated by the first queue corresponding to that address group;
adding the addresses to which packets are written to the second queue corresponding to the property of the packets;
calculating a residence period of the packet of the first address indicated by the second queue in the packet buffer based on a first write period specified from the address group to which the first address belongs and the present time indicated by the timer; and
removing all addresses written in the first write period from the second queue when the packets are determined to be discarded based on the residence period.

### Claim 9

A packet forwarding apparatus, comprising:
a packet buffer for temporarily storing packets to be forwarded;
a timer for measuring the time of every predetermined unit period;
a third queue for managing the order of writing packets to the addresses of the packet buffer;
a plurality of fourth queues, each fourth queue corresponding to the property of the packets, each fourth queue managing the order for reading packets from the addresses that have been written to the addresses of the packet buffer along with the write period for each address in the queue;
a third controller for writing packets according to the order of the addresses indicated by the third queue, and adding the addresses that have been written with the write periods to the fourth queue corresponding to the property of the packets; and
a fourth controller for calculating a residence period of the packet of the first address indicated by the fourth queue in the packet buffer based on a first write period for the first address and the present time indicated by the timer, and removing all addresses written in the first write period from the fourth queue when packets are determined to be discarded based on the residence period.

### Claim 10 (depends on 9)

The packet forwarding apparatus according to claim 9, wherein:
pointers are provided having pointer addresses corresponding to each address of the packet buffer;
the third queue is formed by a link list through pointers corresponding to addresses, out of the corresponding address groups, to which packets can be written;
the third controller writes packets in addresses of the packet buffer corresponding to pointers on the link list of the third queue at a time when writing packets, disconnects these pointers from the link list of the third queue, form the fourth queue through these pointers as a link list formed by the pointers, and associate each pointer of the fourth queue with a write period; and
the fourth controller disconnects all pointers connected to the fourth queue that are in the same write period as the start pointer of the fourth queue from the fourth queue when packets are determined to be discarded based on the write period associated with this start pointer, and connects these pointers to the third queue.

### Claim 11

A method for discarding packets for a packet forwarding apparatus comprising a packet buffer for temporarily storing packets to be forwarded, and a timer for measuring the time of every predetermined unit period, the method for discarding packets comprising:
providing a third queue for managing the order of writing packets to the addresses of the packet buffer;
providing a plurality of fourth queues corresponding to the property of the packets;
writing packets according to the order of the addresses indicated by the third queue;
adding an address in which a packet is written along with the write period to the fourth queue corresponding to the property of that packet;
calculating a residence period of the packet of the first address indicated by the fourth queue in the packet buffer based on a first write period for the first address and the present time indicated by the timer; and
removing all addresses written in the first write period from the fourth queue when packets are determined to be discarded based on the residence period.
