Router and method of managing packet queue using the same

• US 20060104294A1
• Filed: 11/14/2005
• Published: 05/18/2006
• Est. Priority Date: 11/16/2004
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Yoo, Tae-Joon
• Application Number:
  US11/271,862
• Publication Number:
  US 20060104294A1
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

A router for performing queue management for packet transmission is provided, which includes a first storage unit for storing and outputting packets input to request transmission from a source device to a destination device; a second storage unit for storing information on the packets stored in the first storage unit; and a packet-processing determination unit for determining whether the input packets are to be stored in the first storage unit, based on whether there is a available storage capacity in the first storage unit, and updating information on the packets into the second storage unit.

Claims

1. A router for performing queue management for packet transmission, comprising:

a first storage unit for storing and outputting packets input to request transmission from a source device to a destination device;

a second storage unit for storing information on the packets stored in the first storage unit; and

a packet-processing determination unit for determining whether the input packets are to be stored in the first storage unit, based on whether there is available storage capacity in the first storage unit, and updating information on the packets into the second storage unit based on the determination result.

2. The router according to claim 1, wherein said information stored the second storage unit comprises:

a flow ID (F) that is information on the source device that requests the packet transmission;

a hit count (H) indicative of the number of times at which the same source device requests the transmission; and

a p_pos_queue (P) indicative of information on where the packet stored in the first storage unit is positioned.

3. The router according to claim 2, wherein, when there is no storage space in the first storage unit and a summation of the hit counts is smaller than a set threshold, the packet-processing determination unit drops the input packet and updates the flow ID (F) for the dropped packet according to a least recently used (LRU) algorithm.

4. The router according to claim 2, wherein, when there is a storage space to store the packet in the first storage unit, the packet-processing determination unit stores the input packet in the first storage unit and updates information containing the flow ID (F) for said packet according to a least recently used (LRU) algorithm.

5. The router according to claim 2, wherein, when there is no storage space in the first storage unit and a summation of the hit counts is larger than a set threshold, the packet-processing determination unit detects, from the first storage unit, a packet of the flow ID (F) having the largest hit count (H) from the second storage unit, stores the input packet into an empty space of the first storage unit, and updates information on the stored packet into the second storage unit.

6. The router according to claim 5, wherein, when the flow ID (F) of the input packet is stored in the second storage unit and the hit count (H) is the maximum value, the packet-processing determination unit updates the flow ID (F) according to a least recently used (LRU) algorithm.

7. The router according to claim 6, wherein, when the flow ID (F) of the input packet is stored in the second storage unit and the hit count (H) is not the maximum value, the packet-processing determination unit decrements the maximum value of the hit count (H) stored in the second storage unit by ‘

1’ and

increments the hit count (H) for the input packet by ‘

1’

while updating the flow ID (F) according to the least recently used (LRU) algorithm.

8. The router according to claim 7, wherein, when the flow ID (F) of the input packet is not stored in the second storage unit and there is a space to update, the packet-processing determination unit stores an entry corresponding to the input packet into the second storage unit.

9. The router according to claim 8, wherein, when the flow ID (F) of the input packet is not stored in the second storage unit and there is no space to update, the packet-processing determination unit deletes an entry that is least recently used according to the least recently used (LRU) algorithm and updates the corresponding entry for the input packet at the deleted space.

10. A method of managing a queue for packet transmission using a router, comprising:

receiving packets requesting transmission from a source device;

determining whether there is an available storage space in a first storage unit for storing the packets;

when the storage space is not in the first storage unit, determining whether the packets are to be stored and dropped, based on a result of comparing the number of times at which the source device requests the transmission to a set threshold; and

updating information on the packets processed according to the determination result into a second storage unit that stores information on the packets.

11. The method according to claim 10, wherein the information on the packets stored in the second storage unit comprises:

a flow ID (F) that is information on the source device that requests the packet transmission;

a hit count (H) indicative of the number of times at which the same source device requests the transmission; and

a p_pos_queue (P) indicative of information on where the packet stored in the first storage unit is positioned.

12. The method according to claim 11, wherein updating the information comprises, when there is no storage space in the first storage unit and a summation of the hit counts is smaller than the set threshold, dropping the input packet and updating the flow ID (F) for the dropped packet according to a least recently used (LRU) algorithm.

13. The method according to claim 11, wherein updating the information comprises, when there is a storage space to store the packet in the first storage unit, storing the input packet into the first storage unit, and updating information containing the flow ID (F) for said packet according to a least recently used (LRU) algorithm.

14. The method according to claim 11, wherein updating the information comprises:

when there is no storage space in the first storage unit and a summation of the hit counts is larger than a set threshold, detecting, from the first storage unit, a packet of the flow ID (F) having the largest hit count (H) from the second storage unit;

storing the input packet into an empty space of the first storage unit; and

updating information on the stored packet into the second storage unit.

15. The method according to claim 15, wherein updating the information further comprises, when the flow ID (F) of the input packet is stored in the second storage unit and the hit count (H) is the maximum value, updating the flow ID (F) according to a least recently used (LRU) algorithm.

16. The method according to claim 15, wherein updating the information further comprises, when the flow ID (F) of the input packet is stored in the second storage unit and the hit count (H) is not the maximum value, decrementing the maximum value of the hit count (H) stored in the second storage unit by ‘

1’ and

incrementing the hit count (H) for the input packet while updating the 5 flow ID (F) by ‘

1’

according to the least recently used algorithm.

17. The method according to claim 16, wherein updating the information further comprises, when the flow ID (F) of the input packet is not stored in the second storage unit and there is a space to update, storing an entry corresponding to the input packet into the second storage unit.

18. The method according to claim 17, wherein updating the information further comprises, when the flow ID (F) of the input packet is not stored in the second storage unit and there is no space to update, deleting an entry that is least recently used according to the least recently used algorithm, and updating the corresponding entry for the input packet in the deleted space.