Router and queue processing method thereof

• US 20080212600A1
• Filed: 02/29/2008
• Published: 09/04/2008
• Est. Priority Date: 03/02/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Yoo, Tae-Joon
• Granted Patent: US 8,339,950 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A queue processing method and a router perform cache update and queue processing based upon whether or not the packet capacity stored in the queue exceeds a rising threshold, or whether the packet capacity stored in the queue is below a falling threshold after the packet capacity stored in the queue has exceeded the rising threshold. This queue processing method and router makes it possible to eliminate overhead associated with the update of flow information by using two caches, while concomitantly removing the inequality of packet flows via RED queue management with the expedient of using two caches.

Claims

1. A router, comprising:

a first cache storing flow information of receiving packets;

a second cache storing flow information of received packets, in a state where packet capacity stored in a queue satisfies a condition of either exceeding a rising threshold or of not being below a falling threshold after having exceeded the rising threshold; and

a packet processor dropping a received packet by applying a high drop probability when flow information of the received packet is stored in the second cache, in the state where the packet capacity stored in the queue satisfies a condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold.

2. The router according to claim 1, wherein the flow information includes:

IP address and port number, included in the received packet; and

a hit count of a packet received by the router and the packet having the IP address and the port number.

3. The router according to claim 1, wherein, when a capacity of the second cache is not full in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold, or of not being below the falling threshold after having exceeded the rising threshold, the packet processor stores the flow information of the received packet in the second cache, in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold.

4. The router according to claim 3, wherein, when the capacity of the second cache is full in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold, the packet processor drops flow information which has a hit count smaller than that of the received packet from the second cache, in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold.

5. The router according to claim 1, wherein the packet processor drops the received packet by applying a low drop probability when the flow information of the received packet is not stored in the second cache, in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold.

6. The router according to claim 1, wherein the packet processor clears the second cache and then controls a packet flow via drop-tail queue management when the packet capacity stored in the queue satisfies the condition of not exceeding the rising threshold or of below the falling threshold after having exceeding the rising threshold.

7. A queue processing method of a router, which includes a first cache storing flow information of receiving packets, and a second cache storing flow information of received packets, in a state where packet capacity stored in a queue satisfies a condition of either exceeding a rising threshold or of not below a falling threshold after having exceeded the rising threshold, the method comprising:

when a packet is received by a router comprised of a first cache and a second cache, checking whether the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of being below the falling threshold after having exceeding the rising threshold; and

when the packet capacity stored in the queue is determined to satisfy the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeded the rising threshold, dropping the received packet by selectively applying one of a high drop probability or a low drop probability in dependence upon whether flow information of the received packet is stored in the second cache.

8. The queue processing method according to claim 7, with the flow information including:

IP address and port number, included in the received packet; and

a hit count of a packet received by the router, the packet having the IP address and the port number.

9. The queue processing method according to claim 7, further comprised of when the packet capacity stored in the queue does not satisfy the condition of either exceeding the rising threshold or of being below the falling threshold after having exceeded the rising threshold, controlling a packet flow via drop-tail queue management.

10. A cache update method of a router, which includes a first cache storing flow information of receiving packets, and a second cache storing flow information of received packets, in a state where packet capacity stored in a queue exceeds a rising threshold, or is not below a falling threshold after exceeding the rising threshold, the method comprising:

checking in a router comprised of a first cache and a second cache, to determine whether a capacity of the second cache is full in the state where the packet capacity stored in the queue satisfies a condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold; and

when the capacity of the second cache is full in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeding the rising threshold, dropping flow information, which has a high count smaller than that of a received packet, from the second cache, in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeded the rising threshold.

11. The cache update method according to claim 10, further comprising:

when the capacity of the second cache is not full in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeded the rising threshold, storing flow information of the received packet in the second cache, in the state where the packet capacity stored in the queue satisfies the condition of either exceeding the rising threshold or of not being below the falling threshold after having exceeded the rising threshold.