Patent ID: 8306045

Claim:
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 pointers with pointer addresses corresponding to each address of the packet buffer; 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 being formed by a link list through pointers corresponding to addresses, out of the corresponding address groups, to which packets can be written and managing an order of writing packets into addresses in the corresponding address group; a plurality of second queues, each second queue corresponding to a property of packets, each second queue managing an order for reading packets from the addresses of the packet buffer which packets have been written into; a first controller for associating each address group with a write period by switching an address group to be written into in every predetermined unit period such that the address group to be written into is different for each of consecutive write periods, the number of which is identical to the number of the plurality of address groups, the first controller writing packets into addresses in the address group to which the packets are to be written according to the order indicated by the first queue corresponding to the address group, and adding the addresses into which the packets have been written to a second queue that corresponds to the property of the packets, the first controller being configured to write packets into addresses of the packet buffer corresponding to the pointers on the link list of the first queue corresponding to the write period at a time when writing packets, disconnect the pointers from the link list of the first queue, and form the second queue through the pointers as a link list formed by the pointers; and a second controller for calculating a residence period of the packet of the address corresponding to a start pointer of the second queue based on a first write period to which an address group including the address corresponding to the start pointer of the second queue and a present time indicated by the timer, and removing all addresses having packets written within the first write period from the second queue when the packet is determined to be discarded based on the residence period thereof by disconnecting all pointers connected to the second queue that are in the same write period as a start pointer of the second queue, connecting the pointers to the first queue, setting a front pointer of the following period as new start pointer of the second queue.