Method and system to represent the impact of load variation on service outage over multiple links

• US 9,426,075 B2
• Filed: 03/10/2014
• Issued: 08/23/2016
• Est. Priority Date: 03/12/2013
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Senarath, Nimal Gamini, Callard, Aaron James, Cheng, Ho Ting
• Primary Examiner(s): SMARTH, GERALD A
• Application Number:
  US14/203,276
• Publication Number:
  US 20140269332A1
• Time in Patent Office: 897 Days
• Field of Search: 370/238
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Increased resource utilization efficiency can be improved by modeling path costs during admission and path-selection. Specifically, path costs for candidate paths are modeled based on load characteristics (e.g., current load, load variation, etc.) of links in the candidate paths. Path costs can represent any quantifiable cost or liability associated with transporting a service flow over the corresponding path. For example, path costs can correspond to a probability that at least one link in the path will experience an outage when transporting the service flow, a price charged by a network operator (NTO) for transporting the traffic flow over the candidate path, or a total network cost for transporting the flow over a candidate path. The candidate path having the lowest path cost is selected to transport a service flow.

Claims

1. A method for resource provisioning, the method comprising:

identifying, by a controller, one or more candidate wireless paths for carrying a service flow to a destination, the one or more candidate wireless paths including at least a first wireless path comprising a first set of links connected in series;

obtaining load characteristics associated with the first set of links;

determining a first cost for carrying the service flow over the first wireless path in accordance with the load characteristics associated with the first set of links; and

prompting establishment of the first wireless path when the first cost for carrying the service flow over the first wireless path is less than a threshold, wherein the first cost includes a component corresponding to a probability that one or more links in the first set of links will experience an outage if the service flow is carried over the first wireless path.

2. The method of claim 1, wherein the load characteristics include a load on each link in the first set of links.

3. The method of claim 1, wherein the load characteristics include a load variation on each link in the first set of links.

4. The method of claim 1,

wherein determining the first cost comprises computing a component of the first cost in accordance with the following formula:

cost=Σ

_i=1ⁿ−

log(1−

P_oi), where P_oi is the probability of outage of an i^th link in the first set of links, and n is the number of links in the first set of links.

5. The method of claim 1, wherein determining the first cost comprises:

computing a component of the first cost in accordance with the following formula;

cost=log(1/P_s),

where P_s is the probability of success over the first wireless path.

6. The method of claim 1, wherein determining the first cost comprises:

computing a component of the first cost in accordance with the following formula;

cost=Σ

_i=1ⁿC(L_i, σ

_i), where C(L_i, σ

_i) is the cost function for the first wireless path, L_i is the mean load on an i^th link in the first set of links, σ

_i is the load variation on an i^th link in the first set of links, and n is the number of links in the first set of links.

7. The method of claim 1, wherein a component of the first cost corresponds to a total network cost for transporting the service flow over the first wireless path.

8. The method of claim 1, wherein the first set of links includes a first radio interface between a first transmitter and the destination.

9. The method of claim 8, wherein a component of the first cost corresponds to interference experienced on a second radio interface as a result of communicating the service flow over the first radio interface.

10. The method of claim 1, wherein the first cost consists of the component corresponding to the probability that one or more links in the first set of links will experience an outage if the service flow is carried over the first wireless path.

11. A method for resource provisioning, the method comprising:

identifying, by a controller, one or more candidate paths for carrying a service flow to a destination, the one or more candidate paths including at least a first path comprising a first set of links connected in series;

obtaining load characteristics associated with the first set of links;

determining a first cost for carrying the service flow over the first path in accordance with the load characteristics associated with the first set of links, wherein determining the first cost comprises computing the first cost in accordance with the following formula;

cost=Σ

_i=1ⁿC(L_i, σ

_i, L_i1, σ

_i1, L_i2, σ

_i2, .. L_im, σ

_im,), where C(L_i, σ

_i) is the cost function for the first path, L_i is a loading parameter on an i^th link in the first set of links, σ

_i is the load variation on an i^th link in the first set of links, L_ij is a loading parameter of the j^th neighbor of the i^th link, σ

_ij is the load variation of the j^th neighbor of the i^th link, n is the number of links in the first set of links, m is the number of neighbors for the i^th link; and

prompting establishment of the first path when the first cost is less than a threshold.

12. The method of claim 11, wherein L_i is a mean load on the i^th link in the first set of links, and L_ij is a mean load on the j^th neighbor of the i^th link.

13. An apparatus comprising:

a processor; and

a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

identify one or more candidate wireless paths for carrying a service flow to a destination, the one or more candidate wireless paths including at least a first wireless path comprising a first set of links connected in series;

obtain load characteristics associated with the first set of links;

determine a first cost for carrying the service flow over the first wireless path in accordance with the load characteristics associated with the first set of links; and

prompt establishment of the first wireless path when the first cost for carrying the service flow over the first wireless path is less than a threshold, wherein the first wireless path includes at least one radio interface, and wherein a component of the first cost comprises an amount of interference that would be experienced on one or more neighboring wireless links as a result of communicating the service flow over the at least one radio interface.

14. The apparatus of claim 13, wherein the load characteristics include a load on each link in the first set of links.

15. The apparatus of claim 13, wherein the load characteristics include a load variation on each link in the first set of links.

16. The apparatus of claim 13, wherein the instructions to determine the first cost include instructions to:

compute a component of the first cost in accordance with the following formula;

cost=Σ

_i=1ⁿC(L_i, σ

_i, L_i1, σ

_i1, L_i2, σ

_i2, .. L_im, σ

_im,), where C(L_i, σ

_i) is the cost function for the first wireless path, L_i is a loading parameter on an i^th link in the first set of links, σ

_i is the load variation on an i^th link in the first set of links, L_ij is a loading parameter of the j^th neighbor of the i^th link, σ

_ij is the load variation of the j^th neighbor of the i^th link, n is the number of links in the first set of links, m is the number of neighbors for the i^th link.

17. The apparatus of claim 16, wherein L_i is a mean load on the i^th link in the first set of links, and L_ij is a mean load on the j^th neighbor of the i^th link.

18. The apparatus of claim 13, wherein the first cost consists of the component corresponding to the amount of interference that would be experienced on one or more neighboring wireless links as a result of communicating the service flow over the at least one radio interface.

19. An apparatus comprising:

a processor; and

a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

identify one or more candidate wireless paths for carrying a service flow to a destination, the one or more candidate wireless paths including at least a first wireless path comprising a first set of links connected in series;

obtain load characteristics associated with the first set of links;

determine a first cost for carrying the service flow over the first wireless path in accordance with the load characteristics associated with the first set of links; and

prompt establishment of the first wireless path when the first cost for carrying the service flow over the first wireless path is less than a threshold, wherein a component of the first cost corresponds to a probability that one or more links in the first set of links will experience an outage if the service flow is carried over the first wireless path.

20. The apparatus of claim 19, wherein the instructions to determine the first cost include instructions to:

compute a component of the first cost in accordance with the following formula;

cost=Σ

_i=1ⁿ−

log(1−

P_oi), where P_oi is the probability of outage of an i^th link in the first set of links, and n is the number of links in the first set of links.

21. The apparatus of claim 19, wherein the instructions to determine the first cost include instructions to:

compute a component of the first cost in accordance with the following formula;

cost=log(1/P_s),

where P_s is the probability of success over the first wireless path.

22. The apparatus of claim 21, wherein determining the first cost comprises:

computing a component of the first cost in accordance with the following formula;

cost=Σ

_i=1ⁿC(L_i, σ

_i), where C(L_i, σ

_i) is the cost function for the first wireless path, L_i is the mean load on an i^th link in the first set of links, σ

_i is the load variation on an i^th link in the first set of links, and n is the number of links in the first set of links.

23. The apparatus of claim 19, wherein the first cost consists of the component corresponding to the probability that one or more links in the first set of links will experience an outage if the service flow is carried over the first wireless path.

24. An apparatus comprising:

a processor; and

a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

identify one or more candidate wireless paths for carrying a service flow to a destination, the one or more candidate wireless paths including at least a first wireless path comprising a first set of links connected in series;

obtain load characteristics associated with the first set of links;

determine a first cost for carrying the service flow over the first wireless path in accordance with the load characteristics associated with the first set of links; and

prompt establishment of the first wireless path when the first cost for carrying the service flow over the first wireless path is less than a threshold, wherein the first set of links includes a first radio interface between a first transmitter and the destination, and wherein a component of the first cost corresponds to interference experienced on a second radio interface as a result of communicating the service flow over the first radio interface.

27. The apparatus of claim 24, wherein the first cost consists of the component corresponding to the interference experienced on the second radio interface as a result of communicating the service flow over the first radio interface.

25. A method for resource provisioning, the method comprising:

identifying, by a controller, one or more candidate wireless paths for carrying a service flow to a destination, the one or more candidate wireless paths including at least a first wireless path comprising a first set of links connected in series;

obtaining load characteristics associated with the first set of links;

determining a first cost for carrying the service flow over the first wireless path in accordance with the load characteristics associated with the first set of links; and

prompting establishment of the first wireless path when the first cost for carrying the service flow over the first wireless path is less than a threshold, wherein the first wireless path includes at least one radio interface, and wherein a component of the first cost corresponding to an amount of interference that would be experienced on one or more neighboring wireless links as a result of communicating the service flow over the at least one radio interface.

26. The method of claim 25, wherein the first cost consists of the component corresponding to the amount of interference that would be experienced on one or more neighboring wireless links as a result of communicating the service flow over the at least one radio interface.