# US 2012/0250575 A1 · Automated Policy Generation for Mobile Communication Networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0250575 A1
- Document ID: US20120250575A1
- Status: Published application
- Kind: A1
- Application number: 13/219,222
- Filed: 2011-08-26
- Published: 2012-10-04
- Earliest claimed: 2006-07-10
- Assignees: TTI Inventions C LLC
- Inventors: Cho-Yu Jason Chiang; Gary Levin; Yitzchak Gottlieb; Ritu Chadha; Shih-wei Li
- Web page: https://patentgrep.com/patent/US20120250575A1

## CPC

- 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)
- H04L 41/0894: Policy-based network configuration management
- H04L 41/5003: Managing SLA; Interaction between SLA and QoS
- H04L 41/5019: Ensuring fulfilment of SLA
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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 configured to generate optimal bucket sizes and using as input: an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

### Claim 2 (depends on 1)

The method of claim 1 wherein the utility function comprises Ui;
wherein
U
i
=
(
Na
i
(
Na
i
+
Nr
i
+
Nd
i
)
)
*
(
Ns
i
Na
i
)
*
S
i
;
wherein Nai comprises a number of alive flows at a time of observation; Nri comprises a number of rejected flows in an observation period; Ndi comprises a number of downgraded flows in the observation period; Nsi comprises a number of satisfied flows at the time of observation; and Si comprises a stringency constant of the class i.

### Claim 3 (depends on 2)

The method of claim 2 wherein an overall utility function for all classes comprises U;
wherein U=ΣWi*Ui; and
wherein W, comprises a weight schedule.

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 1)

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.

### Claim 9

A tangible 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 configured to generate optimal bucket sizes and using as input: an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

### Claim 10 (depends on 9)

The tangible computer readable medium of claim 9 wherein the utility function comprises Ui;
wherein
U
i
=
(
Na
i
(
Na
i
+
Nr
i
+
Nd
i
)
)
*
(
Ns
i
Na
i
)
*
S
i
;
and
wherein Nai comprises a number of alive flows at a time of observation; Nri comprises a number of rejected flows in an observation period; Ndi comprises a number of downgraded flows in the observation period; Nsi comprises a number of satisfied flows at the time of observation; and Si comprises a stringency constant of the class i.

### Claim 11 (depends on 10)

The tangible computer readable medium of claim 10 wherein an overall utility function for all classes comprises U;
wherein U=ΣWi*Ui; and
wherein W, comprises a weight schedule.

### Claim 12 (depends on 11)

The tangible computer readable medium of claim 11 wherein Wi comprises an exponential weight schedule.

### Claim 13 (depends on 9)

The tangible 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.

### Claim 14 (depends on 9)

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

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 9)

The tangible 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.

### Claim 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 configured to generate optimal bucket sizes and using as input: an alive flow ratio in an observation period, a ratio of satisfied flows over alive flows, and a stringency constant.

### Claim 18 (depends on 17)

The simulation generator apparatus of claim 17 wherein the utility function comprises Ui;
wherein
U
i
=
(
Na
i
(
Na
i
+
Nr
i
+
Nd
i
)
)
*
(
Ns
i
Na
i
)
*
S
i
;
and
wherein Nai comprises a number of alive flows at a time of observation; Nri comprises a number of rejected flows in an observation period; Ndi comprises a number of downgraded flows in the observation period; Nsi comprises a number of satisfied flows at the time of observation; and Si comprises a stringency constant of the class i.

### Claim 19 (depends on 18)

The simulation generator apparatus of claim 18 wherein an overall utility function for all classes comprises U;
wherein U=ΣWi*Ui; and
wherein Wi comprises a weight schedule.

### Claim 20 (depends on 19)

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

### Claim 21 (depends on 17)

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.

### Claim 22 (depends on 17)

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

### Claim 23 (depends on 22)

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

### Claim 24 (depends on 17)

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.

### Claim 25

A method comprising:
obtaining routing topology and alive traffic flows 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; and
determining, using a computing device, a network configuration setting for the communication network corresponding to the optimal utility value.

### Claim 26 (depends on 25)

The method of claim 25 wherein determining the optimal utility value comprises obtaining a total broadcast channel capacity for the communication network and partitioning the total broadcast channel capacity among a set of priority classes to rout a maximum utility subset of point-to-point demand matrices for each priority class.

### Claim 27 (depends on 25)

The method of claim 25 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i

∑
s
,
d
∈
V

X
isd
D
i
;
and
wherein wi comprises a weight factor, Xisd comprises a binary variable configured to accept or reject demands for traffic of priority class i; and Di comprises the total number of point-to-point demands for the priority class i.

### Claim 28 (depends on 25)

The method of claim 25 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i


∑
s
,
d
∈
V

C
i

X
isd
+
D
i

Y
isd
D
i
;
and
wherein wi comprises a weight factor, Ai comprises a fraction of requested value at which utility is obtained; Ci comprises the current utility achieved; Di comprises the current rate at which utility increases for priority class i; Xisd comprises a binary variable configured to accept or reject at least Ai of the requested value; and Yisd comprises the amount served above Ai.

### Claim 29 (depends on 25)

The method of claim 25 wherein determining the optimal utility value for the communication network further comprises determining quality of service parameters modeled as a partition of total broadcast channel capacity into capacity allocations for each priority class i.

### Claim 30 (depends on 25)

The method of claim 25 wherein the obtaining routing topology and alive traffic flows for the given time instant for the communication network comprises obtaining routing topology and alive traffic flows 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.

### Claim 31 (depends on 25)

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

### Claim 32

A tangible computer readable medium having instructions stored thereon, the instructions configured to cause a computing device to perform operations comprising:
obtaining routing topology and alive traffic flows for a given time instant for a communication network;
determining an optimal utility value for the communication network with a mathematical utility function; and
determining a network configuration setting for the communication network corresponding to the optimal utility value.

### Claim 33 (depends on 32)

The tangible computer readable medium of claim 32 wherein determining the optimal utility value comprises obtaining a total broadcast channel capacity for the communication network and partitioning the total broadcast channel capacity among a set of priority classes to rout a maximum utility subset of point-to-point demand matrices for each priority class.

### Claim 34 (depends on 32)

The tangible computer readable medium of claim 32 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i

∑
s
,
d
∈
V

X
isd
D
i
;
and
wherein wi comprises a weight factor, Xisd comprises a binary variable configured to accept or reject demands for traffic of priority class i; and Di comprises the total number of point-to-point demands for the priority class i.

### Claim 35 (depends on 32)

The tangible computer readable medium of claim 32 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i

∑
s
,
d
∈
V

C
i

X
isd
+
D
i

Y
isd
D
i
;
and
wherein wi comprises a weight factor, Ai comprises a fraction of requested value at which utility is obtained; Ci comprises the current utility achieved; Di comprises the current rate at which utility increases for priority class i; Xisd comprises a binary variable configured to accept or reject at least Ai of the requested value; and Yisd comprises the amount served above Ai.

### Claim 36 (depends on 32)

The tangible computer readable medium of claim 32 wherein determining the optimal utility value for the communication network further comprises determining quality of service parameters modeled as a partition of total broadcast channel capacity into capacity allocations for each priority class i.

### Claim 37 (depends on 32)

The tangible computer readable medium of claim 32 wherein the obtaining routing topology and alive traffic flows for the given time instant for the communication network comprises obtaining routing topology and alive traffic flows 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.

### Claim 38 (depends on 32)

The tangible computer readable medium of claim 32 wherein the operations further comprise determining a credibility of a simulation of the communication network with the optimal utility value.

### Claim 39

A network configuration generator apparatus for networks; the network configuration generator apparatus comprising:
a computing device configured to access routing topology and alive traffic flows for a given time instant for a communication network;
a network optimization engine in communication device and configured to:
determine an optimal utility value for the communication network with a mathematical utility function; and
determine a network configuration setting for the communication network corresponding to the optimal utility value.

### Claim 40 (depends on 39)

The network configuration generator apparatus of claim 39 wherein the network optimization engine configured to determine the optimal utility value comprises the network optimization engine configured to obtain a total broadcast channel capacity for the communication network and partition the total broadcast channel capacity among a set of priority classes to rout a maximum utility subset of point-to-point demand matrices for each priority class.

### Claim 41 (depends on 39)

The network configuration generator apparatus of claim 39 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i


∑
s
,
d
∈
V

X
isd
D
i
;
and
wherein wi comprises a weight factor, Xisd comprises a binary variable configured to accept or reject demands for traffic of priority class i; and Di comprises the total number of point-to-point demands for the priority class i.

### Claim 42 (depends on 39)

The network configuration generator apparatus of claim 39 wherein the mathematical utility function comprises U(X);
wherein
U

(
X
)
=
∑
i
∈
P

w
i

∑
s
,
d
∈
V

C
i

X
isd
+
D
i

Y
isd
D
i
;
and
wherein wi comprises a weight factor, Ai comprises a fraction of requested value at which utility is obtained; Ci comprises the current utility achieved; Di comprises the current rate at which utility increases for priority class i; Xisd comprises a binary variable configured to accept or reject at least Ai of the requested value; and Yisd comprises the amount served above Ai.

### Claim 43 (depends on 39)

The network configuration generator apparatus of claim 39 wherein the network optimization engine configured to determine the optimal utility value for the communication network further comprises the network optimization engine configured to determine quality of service parameters modeled as a partition of total broadcast channel capacity into capacity allocations for each priority class i.

### Claim 44 (depends on 39)

The network configuration generator apparatus of claim 39 wherein the network optimization engine configured to obtain the routing topology and alive traffic flows for the given time instant for the communication network comprises the network optimization engine configured to obtain routing topology and alive traffic flows 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.

### Claim 45 (depends on 39)

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