Information Technology Reference
In-Depth Information
3
(4)
g
h
2
(4)
(4)
2
100
(1)
100
(1)
100
(1)
1
(1)
5
(1)
100
(1)
100
(1)
a
c
e
f
j
b
d
i
3
(4)
Fig. 5.
CFG used for illustrating ILP model
Equations 9 through 11 ensure that if
x
v
1
=
y
v
2
=1,then
p
v
1
,v
2
= 1, i.e.,
we incur the cost of switching from ET to TT mode. Similarly, the constraints
reflected in Equations 12 through 14 ensure that if there exists a switch from
TT to ET mode, then
q
v
1
,v
2
= 1 and we incur the cost
c
T→E
.
Constraints of Sampling Cost in TT Mode.
Finally, Equation 15 captures
the cost incurred from the sampling the monitor does in TT mode:
C
sample
=
π∈Π
(
CFG
)
(
c
TT
·F
π
·
N
samp
π
)
(15)
where
Π
(
CFG
) denotes the set of all subpaths
π
=
v
1
→ v
2
→···→ v
k
in
CFG
that satisfy the following four conditions:
1.
k
2
2.
indegree
(
v
i
)=
outdegree
(
v
i
)=1
,
2
≥
≤
i
≤
k
−
1
3.
indegree
(
v
1
)
=1
∨
outdegree
(
v
1
)
=1
4.
indegree
(
v
k
)
=1
∨
outdegree
(
v
k
)
=1
Π
(
CFG
)
5. for each (
v
i
,v
j
)
∈
A
,(
v
i
,v
j
) appears in exactly one
π
∈
For example, if we consider the CFG shown in Figure 5,
Π
(
CFG
)=
{
a
→
b
→
c
→
d
,
d
→
e
→
f
,
f
→
d
,
d
→
g
→
h
→
f
,
f
→
i
→
j
}
.Moreover,
in Equation 15,
F
π
is the expected number of times that
π
will execute at run
time.
(
v
i
,v
j
)
,
where (
v
i
,v
j
) is any arc on path
π
.
N
samp
π
is the number
of samples that the monitor takes when
P
executes
π
once:
F
π
=
F
W
(
γ
)+
c
hist
·
j
m
=
i
y
v
m
SP
N
samp
π
=
·
γ
=
v
i
→...→v
j
,
γ
∈
Γ
π
j
x
v
i−
1
·x
v
j
+1
·
y
v
l
(16)
l
=
i
where
W
(
γ
) returns the sum of weights of all arcs on the path
γ
∈
Γ
π
;
v
i−
1
and
v
j
+1
denote the immediate predecessor and successor of
v
i
,v
j
∈
V
, respectively;
and
SP
is the allowed sampling period of the monitor when it is operating in TT
