Congestion-based traffic shaping for distributed queuing in shared-media communication networks

• US 8,699,333 B2
• Filed: 09/29/2011
• Issued: 04/15/2014
• Est. Priority Date: 09/29/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Lee, Andrew
• Application Number:
  US13/248,799
• Publication Number:
  US 20130083658A1
• Time in Patent Office: 929 Days
• Field of Search: 370/235, 370/230, 370/392, 370/412, 370/444, 370/445, 370/252, 370/465
• US Class Current: 370/230
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18

Abstract

In one embodiment, a device in a shared-media communication network determines a priority of a packet to be queued at the device, and based on the priority determines a length of time the packet is allowed to be queued before being successfully transmitted. After attempting to successfully transmit the queued packet within the shared-media communication network, in response to reaching a threshold amount of the length of time without having successfully transmitted the queued packet, the device may transmit a “shaping” request to one or more reachable neighbors in the shared-media communication network. Specifically, the shaping request is for a temporary reduction in bandwidth utilization by the reachable neighbors for traffic having a comparatively lesser priority than the priority of the packet.

Claims

1. A method, comprising:

determining a priority of a packet to be queued at a device in a shared-media communication network;

determining, based on the priority, a length of time the packet is allowed to be queued before successfully transmitting the packet;

attempting to successfully transmit the queued packet within the shared-media communication network; and

in response to reaching a threshold amount of the length of time without having successfully transmitted the queued packet, transmitting a request from the device to one or more reachable neighbors in the shared-media communication network, the request for a temporary reduction in bandwidth utilization by the reachable neighbors for traffic having a lesser priority than the priority of the packet.

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

receiving an incoming request at the device from a particular reachable neighbor of the one or more reachable neighbors, the incoming request for a temporary reduction in bandwidth utilization by the device for traffic having a lesser priority than an indicated priority within the incoming request; and

, in response,

temporarily reducing bandwidth utilization by the device for traffic at the device having a lesser priority than the indicated priority within the incoming request according to the incoming request.

3. The method as in claim 1, wherein the threshold amount is complete expiration of the length of time.

4. The method as in claim 1, wherein the length of time is unlimited for one or more priorities lesser than a threshold priority.

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

determining that a portion of received traffic at the device has a particular priority that is equal to or greater than the priority of the packet; and

, in response, suppressing transmission of the request.

6. The method as in claim 1, wherein the one or more reachable neighbors are configured to forward the request one hop further from the device.

7. The method as in claim 1, wherein the bandwidth reduction is selected from a group consisting of:

an absolute bandwidth reduction;

a fraction of channel capacity of the shared-media communication network; and

a fraction of currently utilized capacity of the shared-media communication network by each respective reachable neighbor.

8. The method as in claim 1, wherein the priority of the packet is limited to either being a priority packet or a non-priority packet.

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

receiving configuration of how to classify priority of packets from a global device selected from a group consisting of;

a network management server (NMS);

a root node of a directed acyclic graph (DAG);

a head-end application device;

a dynamic host configuration protocol (DHCP) server; and

a Constrained Application Protocol (CoAP) server.

10. The method as in claim 1, wherein determining the priority of the packet is based on a factor selected from a group consisting of:

a priority field within the packet;

a packet type of the packet;

a traffic class of the packet;

a particular flow associated with the packet;

a particular differentiated services (DS) byte value within the packet;

a particular destination address of the packet;

a particular source address of the packet; and

a certain factor based on deep packet inspection of the packet.

11. A method, comprising:

receiving an incoming request at a device in a shared-media communication network from a particular reachable neighbor of one or more reachable neighbors, the incoming request for a temporary reduction in bandwidth utilization by the device for traffic having a lesser priority than an indicated priority within the incoming request; and

, in response,

temporarily reducing bandwidth utilization by the device for traffic at the device having a lesser priority than the indicated priority within the incoming request according to the incoming request.

12. The method as in claim 11, further comprising:

determining a priority of a packet to be queued by the device during the temporary reduction of bandwidth utilization;

determining that the priority is equal to or greater than the indicated priority within the incoming request; and

, in response,

attempting to successfully transmit the queued packet within the shared-media communication network without consideration of the temporary reduction of bandwidth utilization.

13. The method as in claim 11, further comprising:

forwarding the incoming request from the device one hop further from the particular reachable neighbor.

14. The method as in claim 11, wherein the bandwidth reduction is selected from a group consisting of:

an absolute bandwidth reduction;

a fraction of channel capacity of the shared-media communication network; and

a fraction of currently utilized capacity of the shared-media communication network by the device.

15. The method as in claim 11, further comprising:

receiving, within the incoming request, a specified duration for which the bandwidth utilization is to be temporarily reduced.

16. The method as in claim 11, wherein priority of a packet in the communication network is limited to either being a priority packet or a non-priority packet.

17. An apparatus, comprising:

one or more network interfaces to communicate with one or more reachable neighbors in a shared-media communication 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;

determine a priority of a packet to be queued at the apparatus;

determine, based on the priority, a length of time the packet is allowed to be queued before successfully transmitting the packet;

attempt to successfully transmit the queued packet within the shared-media communication network; and

transmit a request to the one or more reachable neighbors in the shared-media communication network in response to reaching a threshold amount of the length of time without having successfully transmitted the queued packet, the request for a temporary reduction in bandwidth utilization by the reachable neighbors for traffic having a lesser priority than the priority of the packet.

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

receive an incoming request from a particular reachable neighbor of the one or more reachable neighbors, the incoming request for a temporary reduction in bandwidth utilization by the device for traffic having a lesser priority than an indicated priority within the incoming request; and

, in response,

temporarily reduce bandwidth utilization by the apparatus for traffic at the apparatus having a lesser priority than the indicated priority within the incoming request according to the incoming request.

19. An apparatus, comprising:

one or more network interfaces to communicate with one or more reachable neighbors in a shared-media communication 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 an incoming request from a particular reachable neighbor of the one or more reachable neighbors, the incoming request for a temporary reduction in bandwidth utilization by the apparatus for traffic having a lesser priority than an indicated priority within the incoming request; and

, in response,

temporarily reduce bandwidth utilization by the apparatus for traffic at the apparatus having a lesser priority than the indicated priority within the incoming request according to the incoming request.

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

determine a priority of a packet to be queued by the apparatus during the temporary reduction of bandwidth utilization;

determine that the priority is equal to or greater than the indicated priority within the incoming request; and

, in response,

attempt to successfully transmit the queued packet within the shared-media communication network without consideration of the temporary reduction of bandwidth utilization.

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

forward the incoming request one hop further from the particular reachable neighbor.

22. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor on a device in a shared-media communication network operable to:

determine a priority of a packet to be queued at the device;

determine, based on the priority, a length of time the packet is allowed to be queued before successfully transmitting the packet;

attempt to successfully transmit the queued packet within the shared-media communication network; and

transmit a request from the device to one or more reachable neighbors in the shared-media communication network in response to reaching a threshold amount of the length of time without having successfully transmitted the queued packet, the request for a temporary reduction in bandwidth utilization by the reachable neighbors for traffic having a lesser priority than the priority of the packet.

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

receive an incoming request at the device from a particular reachable neighbor of the one or more reachable neighbors, the incoming request for a temporary reduction in bandwidth utilization by the device for traffic having a lesser priority than an indicated priority within the incoming request; and

, in response,

temporarily reduce bandwidth utilization by the device for traffic at the device having a lesser priority than the indicated priority within the incoming request according to the incoming request.