Adaptive marking for WRED with intra-flow packet priorities in network queues

• US 9,680,760 B2
• Filed: 07/16/2013
• Issued: 06/13/2017
• Est. Priority Date: 07/16/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Lai, Cheng-Jia, Wang, Wenyi, Yang, Shih-cheng Stan
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): ANDREWS, HOYET H
• Application Number:
  US13/943,018
• Publication Number:
  US 20150023366A1
• Time in Patent Office: 1,428 Days
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04N 21/64792 Controlling the complexity of the content stream, e.g. by dropping packets intermediate media network packet handling H04L65/765; proxy provisioning conversion or adaptation for reducing the amount or size of exchanged application data H04L67/5651; negotiation of resources in wireless networks H04W28/16

Abstract

In one embodiment, a router receives a packet, and determines an intra-flow packet priority level of the packet. The router may then map the intra-flow packet priority level to a weighted random early detection (WRED) marking based on running statistics of intra-flow packet priority levels across received flows, and marks the packet with the mapped WRED marking. By placing the marked packet into an outgoing network queue for transmission, the router may then forward or drop the marked packet based on the network queue, accordingly.

Claims

1. A method, comprising:

receiving, at a network device, a packet;

determining, by the network device, an intra-flow packet priority level of the packet, wherein the intra-flow packet priority level is a priority of the packet within a particular flow in relation to other packets in the particular flow and intra-flow priority distribution is different across received flows at the network device;

mapping, by the network device, the intra-flow packet priority level to a weighted random early detection (WRED) marking based on running statistics of intra-flow packet priority levels across received flows;

marking, by the network device, the packet with the mapped WRED marking to normalize intra-flow priority markings for WRED in a manner that is adaptive to traffic characteristics of each received flow;

placing, by the network device, the marked packet into an outgoing network queue for transmission; and

forwarding or dropping the marked packet by the network device based on the network queue, wherein the received flows have equal per-flow packet drop rates and thresholds among packets in different flows, and each particular flow of the received flows has different packet drop rates and thresholds among packets inside each particular flows, respectively.

2. The method as in claim 1, further comprising:

normalizing the mapping of the intra-flow packet priority level to a WRED marking based on running statistics of intra-flow packet priority levels across received flows.

3. The method as in claim 2, further comprising:

recalculating normalization periodically.

4. The method as in claim 2, further comprising:

recalculating normalization per packet.

5. The method as in claim 2, further comprising:

recalculating normalization using a heuristic algorithm.

6. The method as in claim 2, further comprising:

mapping each lower intra-flow packet priority level to a lower WRED marking as much as possible.

7. The method as in claim 1, wherein the intra-flow packet priority level is based on at least one of a packet type or a packet marking.

8. The method as in claim 1, wherein the WRED marking is a Differentiated Services (DiffServ) marking.

9. The method as in claim 1, wherein the packet is a video packet.

10. The method as in claim 9, wherein the intra-flow packet priority level is based on whether the packet is an instantaneous decode refresh (IDR) packet, a sequence parameters packet, a referenced P packet, a non-referenced P packet, or a non-referenced B packet.

11. An apparatus, comprising:

one or more network interfaces to communicate within a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive a packet;

determine an intra-flow packet priority level of the packet, wherein the intra-flow packet priority level is a priority of the packet within a particular flow in relation to other packets in the particular flow and intra-flow priority distribution is different across received flows;

map the intra-flow packet priority level to a weighted random early detection (WRED) marking based on running statistics of intra-flow packet priority levels across received flows;

mark the packet with the mapped WRED marking to normalize intra-flow priority markings for WRED in a manner that is adaptive to traffic characteristics of each received flow;

place the marked packet into an outgoing network queue for transmission; and

forward or drop the marked packet based on the network queue, wherein the received flows have equal per-flow packet drop rates and thresholds among packets in different flows, and each particular flow of the received flows has different packet drop rates and thresholds among packets inside each particular flows, respectively.

12. The apparatus as in claim 11, wherein the process when executed is further operable to:

normalize the mapping of the intra-flow packet priority level to a WRED marking based on running statistics of intra-flow packet priority levels across received flows.

13. The apparatus as in claim 12, wherein the process when executed is further operable to:

recalculate normalization either periodically, per packet, or using a heuristic algorithm.

14. The apparatus as in claim 12, wherein the process when executed is further operable to:

map each lower intra-flow packet priority level to a lower WRED marking as much as possible.

15. The apparatus as in claim 11, wherein the intra-flow packet priority level is based on at least one of a packet type or a packet marking.

16. The apparatus as in claim 11, wherein the WRED marking is a Differentiated Services (DiffServ) marking.

17. The apparatus as in claim 11, wherein the packet is a video packet.

18. One or more non-transitory computer-readable storage media encoded with software comprising computer executable instructions and when the software is executed operable to:

receive a packet;

determine an intra-flow packet priority level of the packet, wherein the intra-flow packet priority level is a priority of the packet within a particular flow in relation to other packets in the particular flow and intra-flow priority distribution is different across received flows;

map the intra-flow packet priority level to a weighted random early detection (WRED) marking based on running statistics of intra-flow packet priority levels across received flows;

mark the packet with the mapped WRED marking to normalize intra-flow priority markings for WRED in a manner that is adaptive to traffic characteristics of each received flow;

place the marked packet into an outgoing network queue for transmission; and

forward or drop the marked packet based on the network queue, wherein the received flows have equal per-flow packet drop rates and thresholds among packets in different flows, and each particular flow of the received flows has different packet drop rates and thresholds among packets inside each particular flows, respectively.

19. The computer-readable storage media as in claim 18, wherein the software when executed is further operable to:

normalize the mapping of the intra-flow packet priority level to a WRED marking based on running statistics of intra-flow packet priority levels across received flows.

20. The computer-readable storage media as in claim 18, wherein the intra-flow packet priority level is based on at least one of a packet type or a packet marking.