Automated policy generation for mobile communication networks

• US 8,724,508 B2
• Filed: 08/26/2011
• Issued: 05/13/2014
• Est. Priority Date: 07/10/2006
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Inventors: Chiang, Cho-Yu Jason, Levin, Gary, Gottlieb, Yitzchak, Chadha, Ritu, Li, Shih-wei
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): LOUIS, VINNCELAS
• Application Number:
  US13/219,222
• Publication Number:
  US 20120250575A1
• Time in Patent Office: 991 Days
• Field of Search: 370252-254, 370230-2301, 370/351, 370/395.21, 370/255, 370/237, 709223-225, 710/36
• US Class Current: 370/254
• 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 simulation of a mobile ad hoc network comprising;

a plurality of nodes having packet interface queues, at least one node of the plurality of nodes utilizing a priority queue as its packet interface queue and having a policer; and

the policer using a token bucket configured to drop any incoming packets that would cause the token bucket to overflow; and

maximizing, using a computing device, a utility function of the simulation of the mobile ad hoc network configured to generate an optimal bucket size for the token bucket and using as input;

an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

2. The method of claim 1 wherein the utility function comprises U_i;

wherein

3. The method of claim 2 wherein an overall utility function for all classes comprises U;

wherein U=Σ

W_i*U_i; and

wherein W_i comprises a weight schedule.

4. The method of claim 3 wherein W_i comprises an exponential weight schedule.

5. The method of claim 1 wherein building the simulation of the mobile ad hoc network comprises compiling information regarding communication resources, communication patterns, and node movement for the mobile ad hoc network.

6. The method of claim 1 wherein the package interface queues comprise Expedited Forwarding queues scheduled by a priority queuing algorithm.

7. The method of claim 6 wherein the package interface queues further comprise Assured Forwarding queues scheduled by a weighted fair queuing algorithm.

8. The method of claim 1 wherein the simulation further comprises a quality of service assurance solution comprising an admission control component and a quality adjustment component.

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

building a simulation of a mobile ad hoc network comprising;

a plurality of nodes having packet interface queues, at least one node of the plurality of nodes utilizing a priority queue as its packet interface queue and having a policer; and

the policer using a token bucket configured to drop any incoming packets that would cause the token bucket to overflow; and

maximizing a utility function of the simulation of the mobile ad hoc network configured to generate an optimal bucket size for the token bucket and using as input;

an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

10. The non-transitory computer readable medium of claim 9 wherein the utility function comprises U_i;

wherein

11. The non-transitory computer readable medium of claim 10 wherein an overall utility function for all classes comprises U;

wherein U=Σ

W_i*U_i; and

wherein W_i comprises a weight schedule.

12. The non-transitory computer readable medium of claim 11 wherein W_i comprises an exponential weight schedule.

13. The non-transitory computer readable medium of claim 9 wherein building the simulation of the mobile ad hoc network comprises compiling information regarding communication resources, communication patterns, and node movement for the mobile ad hoc network.

14. The non-transitory computer readable medium of claim 9 wherein the package interface queues comprise expedited forwarding queues scheduled by a priority queuing algorithm.

15. The non-transitory computer readable medium of claim 14 wherein the package interface queues further comprise assured forwarding queues scheduled by a weighted fair queuing algorithm.

16. The non-transitory computer readable medium of claim 9 wherein the simulation further comprises a quality of service assurance solution comprising an admission control component and a quality adjustment component.

17. A simulation generator apparatus for mobile ad hoc networks, the simulation generator apparatus comprising:

a computing device configured to access a simulation of a mobile ad hoc network comprising;

a plurality of nodes having packet interface queues, at least one node of the plurality of nodes utilizing a priority queue as its packet interface queue and having a policer; and

the policer using a token bucket configured to drop any incoming packets that would cause the token bucket to overflow; and

an optimization engine in communication with the computing device, the optimization engine configured to maximize a utility function of the simulation of the mobile ad hoc network configured to generate an optimal bucket size for the token bucket and using as input;

an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

18. The simulation generator apparatus of claim 17 wherein the utility function comprises U_i;

wherein

19. The simulation generator apparatus of claim 18 wherein an overall utility function for all classes comprises U;

wherein U=Σ

W_i*U_i; and

wherein W_i comprises a weight schedule.

20. The simulation generator apparatus of claim 19 wherein W_i comprises an exponential weight schedule.

21. The simulation generator apparatus of claim 17 wherein the computing device configured to receive the simulation comprises the computing device configured to received information regarding communication resources, communication patterns, and node movement for the mobile ad hoc network.

22. The simulation generator apparatus of claim 17 wherein the package interface queues comprise expedited forwarding queues scheduled by a priority queuing algorithm.

23. The simulation generator apparatus of claim 22 wherein the package interface queues further comprise assured forwarding queues scheduled by a weighted fair queuing algorithm.

24. The simulation generator apparatus of claim 17 wherein the simulation further comprises a quality of service assurance solution comprising an admission control component and a quality adjustment component.

25. A method comprising:

obtaining routing topology and channel capacity for a given time instant for a communication network;

determining, using a computing device, an optimal utility value for the communication network with a mathematical utility function using information from the routing topology and the channel capacity as input to partition the channel capacity among a set of priority classes to route a maximum utility subset of point-to-point demand matrices for each priority class; and

determining, using a computing device, one or more quality of service parameters for the communication network corresponding to the optimal utility value.

26. The method of claim 25 wherein the mathematical utility function comprises U(X);

wherein

27. The method of claim 25 wherein the mathematical utility function comprises U(X);

wherein

28. The method of claim 25 wherein determining the one or more quality of service parameters further comprises determining one or more quality of service parameters modeled as a partition of the channel capacity into capacity allocations for each priority class i.

29. The method of claim 25 wherein the obtaining routing topology and the channel capacity for the given time instant for the communication network comprises obtaining routing topology and channel capacity for a plurality of time instants for the communication network;

and

the determining the optimal utility value for the communication network with the mathematical utility function comprises determining an optimal value for the communication network for each of the plurality of time instants with the mathematical utility function.

30. The method of claim 25 further comprising determining a credibility of a simulation of the communication network with the optimal utility value.

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

obtaining routing topology and channel capacity for a given time instant for a communication network;

determining an optimal utility value for the communication network with a mathematical utility function using the routing topology and the channel capacity as input to partition the channel capacity among a set of priority classes to route a maximum utility subset of point-to-point demand matrices for each priority class; and

determining one or more quality of service parameters for the communication network corresponding to the optimal utility value.

32. The non-transitory computer readable medium of claim 31 wherein the mathematical utility function comprises U(X);

wherein

33. The non-transitory computer readable medium of claim 31 wherein the mathematical utility function comprises U(X);

wherein

34. The non-transitory computer readable medium of claim 31 wherein determining the one or more quality of service parameters further comprises determining one or more quality of service parameters modeled as a partition of channel capacity into capacity allocations for each priority class i.

35. The non-transitory computer readable medium of claim 31 wherein the obtaining routing topology and the channel capacity for the given time instant for the communication network comprises obtaining routing topology and channel capacity for a plurality of time instants for the communication network;

and

the determining the optimal utility value for the communication network with the mathematical utility function comprises determining an optimal value for the communication network for each of the plurality of time instants with the mathematical utility function.

36. The non-transitory computer readable medium of claim 31 wherein the operations further comprise determining a credibility of a simulation of the communication network with the optimal utility value.

37. A network configuration generator apparatus for networks;

the network configuration generator apparatus comprising;

a computing device configured to access routing topology and channel capacity for a given time instant for a communication network;

a network optimization engine in communication with the computing device and configured to;

determine an optimal utility value for the communication network with a mathematical utility function using the routing topology and the channel capacity as input to partition the channel capacity among a set of priority classes to route a maximum utility subset of point-to-point demand matrices for each priority class; and

determine one or more quality of service parameters for the communication network corresponding to the optimal utility value.

38. The network configuration generator apparatus of claim 37 wherein the mathematical utility function comprises U(X);

wherein

39. The network configuration generator apparatus of claim 37 wherein the mathematical utility function comprises U(X);

wherein

40. The network configuration generator apparatus of claim 37 wherein the network optimization engine configured to determine the one or more quality of service parameters further comprises the network optimization engine configured to determine one or more quality of service parameters modeled as a partition of the channel capacity into capacity allocations for each priority class i.

41. The network configuration generator apparatus of claim 37 wherein the network optimization engine configured to obtain the routing topology and the channel capacity for the given time instant for the communication network comprises the network optimization engine configured to obtain routing topology and channel capacity for a plurality of time instants for the communication network;

and

the network optimization engine configured to determine the optimal utility value for the communication network with the mathematical utility function comprises the network optimization engine configured to determine an optimal value for the communication network for each of the plurality of time instants with the mathematical utility function.

42. The network configuration generator apparatus of claim 37 wherein the computing device is further configured to determine a credibility of a simulation of the communication network with the optimal utility value.