NETWORK TRAFFIC SHAPING FOR LOW POWER AND LOSSY NETWORKS

• US 20140105015A1
• Filed: 10/16/2012
• Published: 04/17/2014
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Hong, Wei, Paek, Jeongyeup, Vasseur, Jean-Philippe
• Granted Patent: US 9,667,536 B2
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02

Abstract

In one embodiment, data packet messages are received in a Field Area Router (FAR) sent from one or more sources toward one or more destination devices in a Low-Power Lossy Network (LLN). An LLN routing topology for the data packet messages is interpolated in the FAR. An expected time for the data packet messages to reach a destination device in the LLN is determined based upon the routing topology interpolation. Traffic shaping is applied by thse FAR for the data packet messages based upon the determined expected time for the data packet messages to reach destination devices in the LLN.

Claims

1. A method, comprising:

receiving, at a Field Area Router (FAR) device, data packet messages sent from one or more sources toward one or more destination devices in a Low-Power Lossy Network (LLN);

interpolating, in the FAR, LLN routing topology for the data packet messages;

determining an expected time for the data packet messages to reach a destination device in the LLN based upon the routing topology interpolation; and

applying traffic shaping by the FAR for the data packet messages based upon the determined expected time for the data packet messages to reach destination devices in the LLN.

2. A method as recited in claim 1, wherein the data packet messages are received in the FAR from non-LLN sources.

3. A method as recited in claim 1, wherein the applying traffic shaping step includes delaying transmission of the data packet messages in the LLN.

4. A method as recited in claim 1, wherein the determining an expected time step includes determining a number of nodal hops data packet messages travel to reach destination devices in the LLN.

5. A method as recited in claim 1, wherein the determining an expected time step is a function of Carrier Sense Multiple Access (CS MA) backoff, packet length and bit rate regarding transmission of data packet messages in the LLN.

6. A method as recited in claim 1, wherein the determining an expected time step includes determining the quality of nodal links data packet messages will travel across to reach destination devices in the LLN.

7. A method as recited in claim 6, wherein determining an expected time for data packet messages to reach destination devices is a function of both a determined nodal path length and the determined quality of nodal links data packet messages will travel across to reach destination devices in the LLN.

8. A method as recited in claim 1, wherein the determining an expected time step includes determining a number of intermediate nodal hops that are shared by various nodal paths to various destination devices in the LLN.

9. A method, comprising:

receiving, at a Field Area Router (FAR) device, data packet messages from a Low-Power Lossy Network (LLN);

interpolating, in the FAR, LLN routing topology for data packet messages to be received from the LLN;

determining an approximate number of data packet messages the FAR is to receive from the LLN; and

applying traffic shaping by the FAR for the data packet messages transmitting in the LLN to be received by the FAR based upon the determined number of data packet messages the FAR is to receive from the LLN.

10. A method as recited in claim 9, wherein the applying traffic shaping step includes delaying transmission of data packet messages in the LLN to be received by the FAR.

11. A method as recited in claim 9, wherein the step of determining a number of data packet messages the FAR is to receive from the LLN includes the step of dividing a channel capacity of the FAR by an amount of 1-hop and 2-hop nodal devices in the LLN which transmit data packet messages to the FAR.

12. A method as recited in claim 11, wherein the dividing step uses the formula (A+2(B))/N whereby A equals the amount 1-hop nodal devices, B equals the amount of 2-hop nodal devices, and N equals the channel capacity of the FAR.

13. A method as recited in claim 9 wherein the applying traffic shaping step includes implementing traffic shaping on each nodal device in the LLN so as to be applied to each data packet message received by each nodal device wherein the FAR communicates traffic shaping information to each nodal device.

14. A method as recited in claim 13 wherein the applying traffic shaping step further includes the FAR communicating a number of 1-hop and 2-hop nodal devices in the LLN to each nodal device in the LLN.

15. A method as recited in claim 13 wherein the applying traffic shaping step further includes the FAR communicating a data message packet traffic profile to each nodal device in the LLN.

16. A method as recited in claim 9 wherein the applying traffic shaping step further includes the FAR adjusting a capacity allocation for each nodal device in the LLN.

17. A method as recited in claim 9 wherein the step of adjusting a capacity allocation for each nodal device in the LLN is based upon the number of nodal devices in the LLN, the routing topology and traffic activity for the LLN.

18. A method, comprising:

receiving, at a Field Area Router (FAR), multicast data packet messages to be forwarded to a Low-Power Lossy Network (LLN);

interpolating, in the FAR, a LLN routing topology for the received multicast data packet messages; and

applying traffic shaping by the FAR for the multicast data packet messages by modeling the time it takes for a data packet message to propagate across a prescribed amount of nodal hops in the LLN prior to the FAR initiating subsequent transmission of multicast data packet messages in the LLN.

19. A method as in claim 18, wherein the time modeling step includes use of one of:

naive flood, trickle flood or reduced-topology flood data packet message routing techniques.

20. A method as recited in claim 18, wherein the time modeling step includes the FAR modeling a time it takes to propagate the multicast data packet message in the LLN without reliance on the LLN routing topology.

21. An apparatus, comprising:

one or more network interfaces configured to communicate with a Low Power and Lossy Network (LLN);

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

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

receive data packet messages sent from one or more sources intended for transmission toward one or more destination devices in the LLN;

interpolate a routing topology for the data packet messages intended for transmission to the LLN;

determine, an expected time for the data packet messages to reach a destination device in the LLN based upon the routing topology interpolation; and

apply traffic shaping for the data packet messages based upon the determined expected time for data packet messages to reach destination devices in the LLN.

22. An apparatus as recited in claim 21, wherein the applying traffic shaping step includes delaying transmission of the data packet messages in the LLN.

23. An apparatus as recited in claim 21, wherein the determining an expected time step includes determining a number of nodal hops for data packet messages to reach destination devices in the LLN.

24. An apparatus, comprising:

one or more network interfaces configured to communicate with a Low Power and Lossy Network (LLN);

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

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

receive data packet messages from LLN devices;

interpolate a routing topology for data packet messages to be received from the LLN;

determine an approximate number of data packet messages to be received from the LLN; and

apply traffic shaping for the data packet messages transmitting in the LLN based upon the determined number of data packet messages to be received from the LLN.

25. An apparatus as recited in claim 24, wherein the step of determining a number of data packet messages to be received from the LLN includes the step of dividing a channel capacity of the FAR by an amount of the 1-hop nodal devices and 2-hop nodal devices in the LLN which data packet messages travel across subsequent to reaching the FAR.