Automated policy generation for mobile communication networks

• US 8,023,423 B2
• Filed: 07/06/2007
• Issued: 09/20/2011
• Est. Priority Date: 07/10/2006
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Licensing Co LLC (Telefonaktiebolaget LM Ericsson)
• Inventors: Chiang, Cho-Yu Jason, Li, Shih-wei, Gottlieb, Yitzchak, Levin, Gary, Chadha, Ritu
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Louis; Vinncelas
• Application Number:
  US11/825,365
• Publication Number:
  US 20080195360A1
• Time in Patent Office: 1,537 Days
• Field of Search: 370/252, 370/254, 370/395.21, 706/4, 706/23, 706/48, 706/10, 709223-225, 726/1, 713/321
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA

Abstract

A solution to the problem of automated policy generation for mobile ad hoc networks includes an optimization-based, utility-driven approach aimed at generating optimal policies with respect to the given network objectives. The combination of optimization heuristics and network simulation is used to solve the problem. Specifically, the problem of automated generation of network management policies based on available network plans and related information is solved by converting the policy generation into the following optimization problem: given network information and objectives as input, generate optimal policies as output. The optimization process is guided by a utility function based on performance evaluation criteria reflecting the network objectives.

Claims

1. A method comprising:

building a model of a communication network;

receiving representations of performance objectives of the communication network; and

maximizing with a computing device a possible utility, Utility_max;

wherein Utility_max=MAX{Utility_i}_{i=1, 2, 3, . . .} ,

wherein Utility_i=U(NM, Policy_i),

wherein NM comprises a data representation of the communication network, U comprises a function of the performance objectives, and Policy_i comprises an i^th policy to be evaluated, and

wherein the maximizing comprises finding a policy set, Policy_max, that optimizes the performance objectives U with a utility value, Utility_max;

wherein finding the policy set comprises finding a set of policies that represent configuration settings to optimize performance objectives for the communication network.

2. The method of claim 1, wherein building the model of the communication network comprises compiling information regarding communication resources, communication patterns, and node movement for the communication network.

3. The method of claim 1, wherein optimizing the performance objectives U comprises optimizing performance metrics comprising one or more of packet loss ratio, packet transmission delay, or jitter.

4. The method of claim 1, wherein optimizing the performance objectives U comprises optimizing a composite function combining multiple distinct network objectives.

5. The method of claim 1, wherein optimizing U comprises using a parallel simulated annealing algorithm.

6. The method of claim 1, wherein building the model of the communication network comprises building a simulation model.

7. The method of claim 6, wherein finding a policy set comprises finding a policy set wherein NM comprises a data representation of a mobile ad hoc network simulation model, Policy_i comprises a set of policies that represents configuration settings for the communication network, and U comprises a utility function whose value comprises computations based on collected simulation run statistics.

8. The method of claim 6, wherein building the simulation model comprises building a ns2 network simulator.

9. The method of claim 1, wherein building the model comprises building a mathematical model.

10. The method of claim 1, wherein building the model of the communication network comprises building a model of a mobile ad hoc network.

11. The method of claim 1 wherein the maximizing comprises iteratively evaluating adjusted policy sets and saving a policy set that results in a maximum utility.

12. The method of claim 1 wherein the finding the policy set comprises:

generating utility values in parallel for a set of policy set parameters;

generating at least one additional set of policy set parameters to evaluate in response to generating utility values in parallel for the set of policy set parameters;

generating utility values in parallel for the additional set of policy set parameters;

repeating the generating utility values and the generating at least one additional set of policy set parameters to converge to a result.

13. The method of claim 1 further comprising applying the policy set, Policy_max, to the communication network.

14. A policy generator apparatus for networks, the policy generator apparatus comprising:

a computing device configured to receive a model of a network and performance objectives of the network;

a policy optimization engine in communication with the computing device, the policy optimization engine configured to maximize possible utility, Utility_max;

wherein Utility_max=MAX{Utility_i}_{i=1, 2, 3, . . .} ,

wherein Utility_i=U(NM, Policy_i)and

NM comprises a data representation of the network, U comprises a function of the objectives of the network, and Policy_i comprises the i^th policy to be evaluated by finding a policy set, Policy_max, that optimizes U with a utility value, Utilitymax;

wherein the policy optimization engine is configured to find a set of policies that represent configuration settings to optimize objectives for the network.

15. The policy generator apparatus of claim 14, wherein the computing device is configured to receive the model of the network wherein the model comprises information regarding at least one of communication resources, communication patterns, or node movement for the network.

16. The policy generator apparatus of claim 14, wherein U comprises performance metrics comprising one or more of packet loss ratio, packet transmission delay, or jitter.

17. The policy generator apparatus of claim 14, where U comprises a composite function combining multiple distinct network objectives.

18. The policy generator apparatus of claim 14, wherein the policy optimization engine is configured to determine an optimal U using parallel simulated annealing algorithm.

19. The policy generator apparatus of claim 14, wherein computing device is configured to receive the model comprising a simulation model.

20. The policy generator apparatus of claim 19, wherein the policy optimization engine is configured to find a policy set wherein NM comprises a mobile ad hoc network simulation model, Policy_i comprises a specific set of policies that represent configuration settings for the network, and U comprises a utility function whose value comprises computations based on collected simulation run statistics.

21. The policy generator apparatus of claim 19, wherein the simulation model comprises a model build by a ns2 network simulator.

22. The policy generator apparatus of claim 14, wherein the model comprises a mathematical model.

23. The policy generator apparatus of claim 14, wherein the network comprises a mobile ad hoc network.

24. A non-transitory computer readable medium having instructions stored thereon, the instructions configured to cause a computing device to perform operations comprising:

build a model of a network;

receive performance objectives of the network; and

maximize possible utility, Utility_max;

wherein Utility_max=MAX{Utility_i}_{i=1, 2, 3, . . .} ,

wherein Utility_i=U(NM, Policy_i), and

wherein NM comprises a data representation of the network, U comprises a function of the performance objectives, and Policy_i comprises an i^th policy to be evaluated by finding a policy set, Policy_max, that optimizes the performance objectives U with a utility value, Utility_max;

wherein the operation of finding a policy set comprises finding a set of policies that represent configuration settings to optimize performance objectives for the network.

25. The non-transitory computer readable medium of claim 24, wherein the model of the network comprises compiled information regarding communication resources, communication patterns, and node movement for the network.

26. The non-transitory computer readable medium of claim 24, wherein the operation of optimizing the performance objectives U comprises optimizing performance metrics comprising one or more of packet loss ratio, packet transmission delay, or jitter.

27. The non-transitory computer readable medium of claim 24, wherein the operation of optimizing the performance objectives U comprises optimizing a composite function combining multiple distinct network objectives.

28. The non-transitory computer readable medium of claim 24, wherein the operation of optimizing U comprises using a parallel simulated annealing algorithm.

29. The non-transitory computer readable medium of claim 24, wherein the model of the network comprises a simulation model.

30. The non-transitory computer readable medium of claim 29, wherein NM comprises a mobile ad hoc network simulation model, Policy_i, comprises a set of policies that represent configuration settings for the network, and U comprises a utility function whose value comprises computations based on collected simulation run statistics.

31. The non-transitory computer readable medium of claim 24, wherein the model comprises a mathematical model.

32. The non-transitory computer readable medium of claim 24, wherein the network comprises a mobile ad hoc network.

33. The non-transitory computer readable medium of claim 24, wherein the operation of maximizing comprises iteratively evaluating adjusted policy sets and saving a policy set that results in a maximum utility.

34. The non-transitory computer readable medium of claim 24, wherein the operation of finding the policy set comprises:

generating utility values in parallel for a set of policy set parameters;

generating at least one additional set of policy set parameters to evaluate in response to generating utility values in parallel for the set of policy set parameters;

generating utility values in parallel for the additional set of policy set parameters;

repeating the generating utility values and the generating at least one additional set of policy set parameters to converge to a result.