Case Study - VoIP Model Graph Transformation
Rules
Mayur Bapodra, Reiko Heckel
Department of Computer Science, University of Leicester, UK
[email protected], [email protected]
1
Introduction
This report details a case study based on a very simple overview of peer-to-peer
(P2P) connections over a voice over IP (VoIP) network such as that used for
Skype. We present the concrete version of the model (with aggregating attributes
already added) followed by the resulting abstract model.
Rule name abbreviations that have been used in accompanying research are
given after each rule name.
2
Concrete Model
The VoIP network is constructed from Client and Super nodes, each servicing
a single user, administrated by a central registry. Figure 1 shows the concrete
type graph. User represents a physical user. Client represents a node that users
attach to in order to make a call. Users can also attach to a Super node, but since
Supers form the overall communication network via ovl edges, linking Clients to
each other through this network, the user in question must meet a bandwidth
threshold. In our model, we simplify this threshold by not explicitly measuring
bandwidth, but instead controlling the likelihood that a user has the minimum
bandwidth through stochastic parameters.
Our smallest start graph is shown in Figure 2. It consists of the registry
node, one super node (with associated user) and six disconnected users. In the
abstract model we aim to simplify the type graph by hiding User and Client
types. There are therefore three aggregating attributes in this model to retain
information. The Registry stores the number of clients not yet connected to the
overlay network via a link edge to a Super (as freeClients). It also stores the
number of users that have not yet turned on their VoIP program and therefore
do not have an associated Client or Super node (as offlineUsers). Additionally,
Supers store the number of clients linked to them. The OCL constraints giving
their values in the concrete model are as follows:
context: Registry
inv: self.offlineUsers = User.allInstances -> count (u:User |
Node.allInstances -> forall(n:Node | n.usr 6= u))
2
Fig. 1. Concrete type graph
context: Registry
inv: self.freeClients = Client.allInstances -> count (c:Client |
c.link -> isEmpty())
context: Super
inv: self.clients = Client.allInstances ->
count (c : Client | c.link = self)
The behavioural semantics of the model are explained through the GT rules.
Figure 3 shows the creation of a new client when a user connects to the VoIP
program. The NAC shows that the user must not already be connected. The new
client is connected at the registry. The condition on the offlineUsers aggregating
attribute is naturally redundant since we have the user node and the NAC at
the concrete level.
Figure 4 illustrates a user wishing to communicate with another via the
overlay network set up between Super nodes. The client must not have an existing
link to a super node, and the super it connects to must have fewer than five
clients. This is considered the maximum shareable bandwidth before a super
node is overloaded. Note that ideally, although redundant, a NAC should also
be present to represent this condition, but we omit it and leave the condition on
the aggregating attribute only for simplicity.
Figure 5 shows the promotion of a client to a super when it is connected to
an overloaded super node. This reduces some of the pressure on the overused
super node.
Figure 6 depicts the rule that is analogous to the creation of a new client,
except that the user has sufficient bandwidth to support a super node. The super
node is immediately connected to the overlay network via an existing super node.
3
Fig. 2. Concrete start graph
Fig. 3. New client, concrete GT rule (NC )
Fig. 4. Link client, concrete GT rule (LC )
4
Fig. 5. Promote client, concrete GT rule (PC )
Fig. 6. New super, concrete GT rule (NS )
Figure 7 shows the termination of a client while it is connected to the overlay
network (i.e., during a call). The rule represents the shutting down of the VoIP
program by a user.
Fig. 7. Terminate linked client, concrete GT rule (TL)
The rule in Figure 8 represents the shutting down of the VoIP program by a
user that is connected directly through a super node. This is only allowed if there
is at least one other super node present. To prevent violation of the dangling
condition, we must explicitly represent all other graph vertices the deleted node
is connected to. Furthermore, all clients that were connected to the deleted super
node are returned to the registry. Through the deletion of a super node by this
rule, the overlay network may become disconnected so that some clients may
become unreachable from others.
Figure 9 depicts the loss of an unlinked client, i.e., a user switching off the
VoIP program without being in a call.
5
Fig. 8. Terminate super, concrete GT rule (TS )
Fig. 9. Terminate unlinked client, concrete GT rule (TU )
Finally, Figure 10 describes the creation of redundant links between supers in
order to make the overlay network more robust. Client pairs are less susceptible
to becoming disconnected when a super is terminated if there is more than one
path between the supers to which they are connected. Note that the rule has two
NACs: one stating that there should be no existing overlay connection between
the supers that are to be newly linked, and secondly, that there is no alternate
pathway between these supers via a fourth super node.
Fig. 10. Create shortcut, concrete GT rule (CS )
The global behaviour of interest in this model is the proportion of total clients
at any time that are connected to the overlay network, and the proportion of
total super node pairs that are unreachable from each other (i.e., there is no
transitive closure of the ovl edge between them).
6
For the former, we create a probe rule that searches matches for Client nodes,
and another that searches matches for Client nodes linked to Super nodes, dividing the second by the first to find the measure we require. This measurement
is taken after every step in the simulation and we use the average value over
each of these steps as our result.
Transitive closure measurements require modifications to the standard VIATRA2 installation [1]. A description of the necessary steps are outlined by the
authors in an online addendum to [1] at http://viatra.inf.mit.bme.hu/grats. We
specify the pattern between just two super nodes with a pair of oppositely directed ovl edges between them. The transitive closure version of the probe then
looks for all pairs of super nodes between which there is a chain of ovl edges. A
negation of this pattern then finds all such pairs between which there is no such
transitive connection. We divide this number of pairs by the total number of
super node pairs to find our measure. Just as with the connected client measure,
we take the average of this value over all simulation steps.
Code Fragment 1.1 shows the VTCL specification implementing the entire
behaviour of the concrete model, complete with probes and auxiliary patterns.
Code Fragment 1.1. VTCL Specification of Concrete Model
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
namespace p2p ;
i m p o r t DSM. metamodels . p2p TG ;
import datatypes ;
@incremental
machine r u l e s a n d c o n s t r a i n t s {
// /////////////////////////////////////////
// PATTERNS
// ////////////////////////////////////////
p a t t e r n UserConnected (U) = {
User (U) ;
P2PNode (N) ;
P2PNode . u s r ( U1 , N, U) ;
}
p a t t e r n C l i e n t L i n k e d (C) = {
C l i e n t (C) ;
Super ( S ) ;
C l i e n t . l i n k ( L , C, S ) ;
}
p a t t e r n C l i e n t s (C) = {
C l i e n t (C) ;
}
p a t t e r n S u p e r P a i r s ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
}
s h a r e a b l e p a t t e r n S u p e r L i n k e d ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
Super . o v l ( Ov1 , S1 , S2 ) ;
Super . o v l ( Ov2 , S2 , S1 ) ;
}
7
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
@ I n c r e m e n t a l ( r e i n t e r p r e t=t r a n s i t i v e C l o s u r e , o f P a t t e r n=S u p e r L i n k e d )
p a t t e r n t r a n s i t i v e C l o s u r e O f S u p e r L i n k e d ( S1 , S2 ) = {}
// /////////////////////////////////////////
// CONCRETE RULES
// ////////////////////////////////////////
g t r u l e NewClient ( ) = {
p r e c o n d i t i o n p a t t e r n l h s (U, OU, FC, R) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
User (U) ;
neg f i n d UserConnected (U) ;
}
action {
l e t C=undef ,
C1=undef ,
U1=undef ,
Model=DSM. models . model
in seq {
new ( C l i e n t (C) i n Model ) ;
rename (C, ” c l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name (C) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( P2PNode . u s r ( U1 , C, U) ) ;
rename ( U1 , ” u s r ” ) ;
new ( R e g i s t r y . c l i e n t ( C1 , R, C) ) ;
rename ( C1 , ” c l i e n t ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( C1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) − 1 ) ) ;
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . NewClient a p p l i e d t o c r e a t e C l i e n t ”
+ name (C) ) ;
}
}
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
}
gtrule LinkClient () = {
p r e c o n d i t i o n p a t t e r n l h s (FC, Cl1 , C, S , S C ) = {
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
Super . c l i e n t s ( S Cx , S , S C ) ;
check ( t o I n t e g e r ( value ( S C ) ) < 5) ;
R e g i s t r y (R) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
C l i e n t (C) ;
R e g i s t r y . c l i e n t ( Cl1 , R, C) ;
neg f i n d C l i e n t L i n k e d (C) ;
}
action {
l e t L=u n d e f
in seq {
d e l e t e ( Cl1 ) ;
new ( C l i e n t . l i n k ( L , C, S ) ) ;
rename ( L , ” l i n k ” ) ;
setValue ( S C , t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) + 1) ) ;
8
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) − 1 ) ) ;
p r i n t l n ( ”GT RULE . . . L i n k C l i e n t a p p l i e d t o l i n k C l i e n t ”
+ name (C) ) ;
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
}
}
}
g t r u l e PromoteClient ( ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S , C, U, L , U1 , S C ) = {
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
c h e c k ( t o I n t e g e r ( v a l u e ( S C ) ) >= 5 ) ;
Super . c l i e n t s ( S Cx , S , S C ) ;
C l i e n t (C) ;
C l i e n t . l i n k ( L , C, S ) ;
User (U) ;
P2PNode . u s r ( U1 , C, U) ;
}
action {
l e t S2=undef ,
S CNew=undef ,
S CNew X=undef ,
Ovl1=undef ,
Ovl2=undef ,
U2=undef ,
Model=DSM. models . model
in seq {
p r i n t ( ”GT RULE . . . P r o m o t e C l i e n t a p p l i e d t o promote
C l i e n t ” + name (C) ) ;
d e l e t e (L) ;
d e l e t e ( U1 ) ;
d e l e t e (C) ;
138
139
140
141
142
143
new ( Super ( S2 ) i n Model ) ;
rename ( S2 , ” s u p e r ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( S2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
144
145
146
147
148
new ( e n t i t y ( S CNew ) i n S2 ) ;
rename ( S CNew , ” C l i e n t s ” ) ;
s e t V a l u e ( S CNew , 0 ) ;
new ( i n s t a n c e O f ( S CNew , r e f ( ”DSM. metamodels . p2p TG . Super
. Clients ”) ) ) ;
new ( Super . c l i e n t s ( S CNew X , S2 , S CNew ) ) ;
rename ( S CNew X , ” c l i e n t s ” ) ;
149
150
151
152
153
new ( Super . o v l ( Ovl1 , S2 , S ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S , S2 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
setValue ( S C , t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) − 1) ) ;
154
155
156
157
158
159
160
161
162
163
164
165
166
167
new ( P2PNode . u s r ( U2 , S2 , U) ) ;
rename ( U2 , ” u s r ” ) ;
p r i n t l n ( ” t o Super ” + name ( S2 ) ) ;
}
}
}
g t r u l e NewSuper ( ) = {
9
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
p r e c o n d i t i o n p a t t e r n l h s (U, S , OU) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
User (U) ;
Super ( S ) ;
neg f i n d UserConnected (U) ;
}
action {
l e t S2=undef ,
S CNew=undef ,
S CNew X=undef ,
Ovl1=undef ,
Ovl2=undef ,
Us1=undef ,
Model=DSM. models . model
in seq {
new ( Super ( S2 ) i n Model ) ;
rename ( S2 , ” s u p e r ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( S2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
190
191
192
193
194
new ( e n t i t y ( S CNew ) i n S2 ) ;
rename ( S CNew , ” C l i e n t s ” ) ;
s e t V a l u e ( S CNew , 0 ) ;
new ( i n s t a n c e O f ( S CNew , r e f ( ”DSM. metamodels . p2p TG . Super
. Clients ”) ) ) ;
new ( Super . c l i e n t s ( S CNew X , S2 , S CNew ) ) ;
rename ( S CNew X , ” c l i e n t s ” ) ;
195
196
197
198
199
200
201
new ( P2PNode . u s r ( Us1 , S2 , U) ) ;
rename ( Us1 , ” u s r ” ) ;
new ( Super . o v l ( Ovl1 , S2 , S ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S , S2 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) − 1 ) ) ;
p r i n t l n ( ”GT RULE . . . NewSuper a p p l i e d t o c r e a t e Super ” +
name ( S2 ) +” w i t h C l i e n t s a t t r i b u t e v a l u e ” + v a l u e (
S CNew ) ) ;
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
}
}
}
g t r u l e TerminateLinkedClient () = {
p r e c o n d i t i o n p a t t e r n l h s (C, S , S C , OU, U1 , L ) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
Super . c l i e n t s ( S Cx , S , S C ) ;
User (U) ;
C l i e n t (C) ;
P2PNode . u s r ( U1 , C, U) ;
C l i e n t . l i n k ( L , C, S ) ;
}
action {
d e l e t e (L) ;
d e l e t e ( U1 ) ;
setValue (S C ,
t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) − 1) ) ;
10
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e L i n k e d C l i e n t a p p l i e d t o
t e r m i n a t e C l i e n t ” + name (C) ) ;
d e l e t e (C) ;
}
}
g t r u l e TerminateUnlinkedClient () = {
p r e c o n d i t i o n p a t t e r n l h s (C, OU, FC, U1 , C1 ) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
User (U) ;
C l i e n t (C) ;
P2PNode . u s r ( U1 , C, U) ;
R e g i s t r y . c l i e n t ( C1 , R, C) ;
}
action {
d e l e t e ( C1 ) ;
d e l e t e ( U1 ) ;
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) − 1 ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e U n l i n k e d C l i e n t a p p l i e d t o
t e r m i n a t e C l i e n t ” + name (C) ) ;
d e l e t e (C) ;
}
}
g t r u l e TerminateSuper ( ) = {
p r e c o n d i t i o n p a t t e r n l h s (OU, FC, S2 , R, S C ) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
Super ( S1 ) ;
Super ( S2 ) ;
Super . C l i e n t s ( S C ) ;
Super . c l i e n t s ( S CX , S2 , S C ) ;
}
action {
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) + t o I n t e g e r ( v a l u e
(S C) ) ) ) ;
i t e r a t e c h o o s e w i t h a p p l y r e l i n k C l i e n t s ( S2 , R) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e S u p e r a p p l i e d t o t e r m i n a t e
Super ” + name ( S2 ) ) ;
d e l e t e ( S2 ) ;
}
280
281
282
283
284
285
286
287
288
289
290
291
292
293
}
gtrule CreateShortcut () = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
Super ( S3 ) ;
11
294
295
296
297
298
299
300
301
302
303
304
305
Super . o v l (O1 , S3 , S1 ) ;
Super . o v l (O2 , S3 , S2 ) ;
neg f i n d S u p e r s C o n n e c t e d ( S1 , S2 ) ;
neg f i n d S u p e r s B y p a s s ( S1 , S2 , S3 ) ;
}
action {
l e t Ovl1=undef ,
Ovl2=u n d e f
in seq {
new ( Super . o v l ( Ovl1 , S1 , S2 ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S2 , S1 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
}
}
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
}
gtrule countClients ( in S ,
i n R,
i n Count ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S , L , C) = {
Super ( S ) ;
C l i e n t (C) ;
C l i e n t . l i n k ( L , C, S ) ;
R e g i s t r y (R) ;
}
action {
l e t C1=u n d e f
in seq {
s e t V a l u e ( Count , t o S t r i n g ( t o I n t e g e r ( v a l u e ( Count ) ) + 1 ) ) ;
d e l e t e (L) ;
new ( R e g i s t r y . c l i e n t ( C1 , R, C) ) ;
rename ( C1 , ” c l i e n t ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( C1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
}
}
}
gtrule
r e l i n k C l i e n t s ( in S ,
i n R) = {
p r e c o n d i t i o n p a t t e r n l h s ( S , L , C, R) = {
Super ( S ) ;
C l i e n t (C) ;
C l i e n t . l i n k ( L , C, S ) ;
R e g i s t r y (R) ;
}
action {
l e t C1=u n d e f
in seq {
d e l e t e (L) ;
new ( R e g i s t r y . c l i e n t ( C1 , R, C) ) ;
rename ( C1 , ” c l i e n t ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( C1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
}
}
}
// /////////////////////////////////////////
// PROBE RULES
// ////////////////////////////
12
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
g t r u l e P r o b e C o n n e c t e d C l i e n t s ( i n o u t C) = {
p r e c o n d i t i o n f i n d C l i e n t L i n k e d (C)
}
g t r u l e P r o b e A l l C l i e n t s ( i n o u t C) = {
p r e c o n d i t i o n f i n d C l i e n t s (C)
}
g t r u l e P r o b e D i s c o n n e c t e d ( i n o u t S1 , i n o u t S2 ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
neg f i n d t r a n s i t i v e C l o s u r e O f S u p e r L i n k e d ( S1 , S2 ) ;
}
}
g t r u l e P r o b e A l l S u p e r P a i r s ( i n o u t S1 , i n o u t S2 ) = {
p r e c o n d i t i o n f i n d S u p e r P a i r s ( S1 , S2 )
}
g t r u l e P r o b e S u p e r s ( i n o u t S1 ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 ) = {
Super ( S1 ) ;
}
}
}
3
Abstract Model
In the abstract model, we retain only the Super and Registry types, with the
inheritance of Super from Node as an inconsequential artefact. The abstract type
graph is shown in Figure 11. The abstraction in this case does not reduce the
number of rules, but with fewer graph elements in each rule and in each instance
graph, there are fewer and smaller matches for each rule. Therefore, an increase
in performance during stochastic simulation is still expected. The start graph is
reduced to just two elements: the registry and the first super node, as shown in
Figure 12.
Fig. 11. Abstract type graph
13
Fig. 12. Abstract start graph
Figures 13 to 19 show the projection of the concrete rules to the abstract
type graph. Note that except for those of create shortcut, all NACs are lost but
conditions on aggregating attributes still remain.
Fig. 13. New client, abstract GT rule (A NC )
Fig. 14. Link client, abstract GT rule (A LC )
The probes responsible for finding disconnected pairs of super nodes can still
be used in the abstract model since the Super type is still present. However, to
calculate the proportion of clients that are connected to the overlay network, the
clients attribute of Super must be accessible along with the freeClients attribute
of Registry. The sum of the clients attribute for all super nodes divided by this
value plus the freeClients value gives us the measure we require.
Since the reading of attribute values is not currently supported by VIATRA2, a hard coded, model specific solution was implemented as a temporary
measure. Probe rules were created to pass required attribute entities in the modelspace to the simulation engine. The hard coded solution recognized the probe
by name and returns/sums the required attribute value for all matches of the
probe rather than simply counting matches themselves. The solution will be incorporated into the stochastic simulation package of VIATRA2 once a naming
convention/methodology for attribute value probes is decided upon.
14
Fig. 15. Promote client, abstract GT rule (A PC )
Fig. 16. New super, abstract GT rule (A NS )
Fig. 17. Terminate linked client, abstract GT rule (A TL)
Fig. 18. Terminate super, abstract GT rule (A TS )
Fig. 19. Terminate unlinked client, abstract GT rule (A TU )
Fig. 20. Create shortcut, abstract GT rule (A CS )
15
The portion of the rules.vtcl file that defines these abstract rules is given in
Code Fragment 1.2.
Code Fragment 1.2. VTCL Specification of Abstract Model
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// /////////////////////////////////////////
// ABSTRACT RULES
// ////////////////////////////////////////
g t r u l e Abstract NewClient () = {
p r e c o n d i t i o n p a t t e r n l h s (OU, FC) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
c h e c k ( t o I n t e g e r ( v a l u e (OU) ) > 0 ) ;
}
action {
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) − 1 ) ) ;
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . NewClient a p p l i e d t o c r e a t e C l i e n t ” ) ;
}
}
gtrule Abstract LinkClient () = {
p r e c o n d i t i o n p a t t e r n l h s (FC, S , S C ) = {
R e g i s t r y (R) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
c h e c k ( t o I n t e g e r ( v a l u e (FC) ) > 0 ) ;
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
Super . c l i e n t s ( S Cx , S , S C ) ;
check ( t o I n t e g e r ( value ( S C ) ) < 5) ;
}
action {
setValue ( S C , t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) + 1) ) ;
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) − 1 ) ) ;
p r i n t l n ( ”GT RULE . . . L i n k C l i e n t a p p l i e d t o l i n k Super ” +
name ( S ) ) ;
}
}
g t r u l e Abstract PromoteClient () = {
precondition pattern lhs (S , S C) = {
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
Super . c l i e n t s ( S Cx , S , S C ) ;
c h e c k ( t o I n t e g e r ( v a l u e ( S C ) ) >= 5 ) ;
}
action {
l e t S2=undef ,
S CNew=undef ,
S CNew X=undef ,
Ovl1=undef ,
Ovl2=undef ,
Model=DSM. models . model
in seq {
16
63
64
new ( Super ( S2 ) i n Model ) ;
rename ( S2 , ” s u p e r ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( S2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
65
66
67
68
69
new ( e n t i t y ( S CNew ) i n S2 ) ;
rename ( S CNew , ” C l i e n t s ” ) ;
s e t V a l u e ( S CNew , 0 ) ;
new ( i n s t a n c e O f ( S CNew , r e f ( ”DSM. metamodels . p2p TG . Super
. Clients ”) ) ) ;
new ( Super . c l i e n t s ( S CNew X , S2 , S CNew ) ) ;
rename ( S CNew X , ” c l i e n t s ” ) ;
70
71
72
73
74
new ( Super . o v l ( Ovl1 , S2 , S ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S , S2 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
setValue (S C ,
t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) − 1) ) ;
p r i n t l n ( ”GT RULE . . .
+ name ( S2 ) ) ;
P r o m o t e C l i e n t a p p l i e d t o new Super ”
}
}
}
g t r u l e Abstract NewSuper ( ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S , OU) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
c h e c k ( t o I n t e g e r ( v a l u e (OU) ) >0) ;
Super ( S ) ;
}
action {
l e t S2=undef ,
S CNew=undef ,
S CNew X=undef ,
Ovl1=undef ,
Ovl2=undef ,
Model=DSM. models . model
in seq {
new ( Super ( S2 ) i n Model ) ;
rename ( S2 , ” s u p e r ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( S2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( e n t i t y ( S CNew ) i n S2 ) ;
rename ( S CNew , ” C l i e n t s ” ) ;
s e t V a l u e ( S CNew , 0 ) ;
new ( i n s t a n c e O f ( S CNew , r e f ( ”DSM. metamodels . p2p TG . Super
. Clients ”) ) ) ;
new ( Super . c l i e n t s ( S CNew X , S2 , S CNew ) ) ;
rename ( S CNew X , ” c l i e n t s ” ) ;
new ( Super . o v l ( Ovl1 , S2 , S ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S , S2 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) − 1 ) ) ;
p r i n t l n ( ”GT RULE . . . NewSuper a p p l i e d t o c r e a t e Super ” +
name ( S2 ) ) ;
17
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
}
}
}
gtrule Abstract TerminateLinkedClient () = {
precondition pattern lhs (S , S C ,
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n
R e g i s t r y . o f f l i n e U s e r s (Ou , R,
Super ( S ) ;
Super . C l i e n t s ( S C ) i n S ;
Super . c l i e n t s ( S Cx , S , S C ) ;
check ( t o I n t e g e r ( value ( S C ) )
}
OU) = {
R;
OU) ;
> 0) ;
action {
setValue ( S C , t o S t r i n g ( t o I n t e g e r ( value ( S C ) ) − 1) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e L i n k e d C l i e n t a p p l i e d t o
t e r m i n a t e C l i e n t on Super ” + name ( S ) ) ;
}
}
gtrule Abstract TerminateUnlinkedClient () = {
p r e c o n d i t i o n p a t t e r n l h s (OU, FC) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
c h e c k ( t o I n t e g e r ( v a l u e (FC) ) >0) ;
}
action {
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) − 1 ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e U n l i n k e d C l i e n t a p p l i e d ” ) ;
}
}
g t r u l e Abstract TerminateSuper () = {
p r e c o n d i t i o n p a t t e r n l h s (OU, FC, S2 , R, S C ) = {
R e g i s t r y (R) ;
R e g i s t r y . O f f l i n e U s e r s (OU) i n R ;
R e g i s t r y . o f f l i n e U s e r s (Ou , R, OU) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
Super ( S1 ) ;
Super ( S2 ) ; // t o d e l e t e
Super . C l i e n t s ( S C ) ;
Super . c l i e n t s ( S CX , S2 , S C ) ;
}
action {
s e t V a l u e (FC, t o S t r i n g ( t o I n t e g e r ( v a l u e (FC) ) + t o I n t e g e r ( v a l u e
(S C) ) ) ) ;
s e t V a l u e (OU, t o S t r i n g ( t o I n t e g e r ( v a l u e (OU) ) + 1 ) ) ;
p r i n t l n ( ”GT RULE . . . T e r m i n a t e S u p e r a p p l i e d t o t e r m i n a t e
Super ” + name ( S2 ) ) ;
d e l e t e ( S2 ) ;
18
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
}
}
gtrule Abstract CreateShortcut () = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
Super ( S3 ) ;
Super . o v l (O1 , S3 , S1 ) ;
Super . o v l (O2 , S3 , S2 ) ;
neg f i n d S u p e r s C o n n e c t e d ( S1 , S2 ) ;
neg f i n d S u p e r s B y p a s s ( S1 , S2 , S3 ) ;
}
action {
l e t Ovl1=undef ,
Ovl2=u n d e f
in seq {
new ( Super . o v l ( Ovl1 , S1 , S2 ) ) ;
rename ( Ovl1 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl1 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
new ( Super . o v l ( Ovl2 , S2 , S1 ) ) ;
rename ( Ovl2 , ” o v l ”+s t r . r e p l a c e A l l ( s t r . r e p l a c e A l l ( s t r .
toLowerCase ( name ( Ovl2 ) ) , ” ” , ” ” ) , ”un” , ” ” ) ) ;
}
}
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
}
// /////////////////////////////////////////
// PROBE RULES
// ////////////////////////////
g t r u l e P r o b e D i s c o n n e c t e d ( i n o u t S1 , i n o u t S2 ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 , S2 ) = {
Super ( S1 ) ;
Super ( S2 ) ;
neg f i n d t r a n s i t i v e C l o s u r e O f S u p e r L i n k e d ( S1 , S2 ) ;
}
}
g t r u l e P r o b e A l l S u p e r P a i r s ( i n o u t S1 , i n o u t S2 ) = {
p r e c o n d i t i o n f i n d S u p e r P a i r s ( S1 , S2 )
}
g t r u l e P r o b e S u p e r s ( i n o u t S1 ) = {
p r e c o n d i t i o n p a t t e r n l h s ( S1 ) = {
Super ( S1 ) ;
}
}
g t r u l e P r o b e A t t r i b u t e F r e e C l i e n t s ( i n o u t FC) = {
p r e c o n d i t i o n p a t t e r n l h s (FC) = {
R e g i s t r y (R) ;
R e g i s t r y . F r e e C l i e n t s (FC) i n R ;
R e g i s t r y . f r e e C l i e n t s ( Fc , R, FC) ;
}
}
gtrule Probe AttributeConnectedClients ( inout S C) = {
precondition pattern lhs (S C) = {
Super ( S ) ;
Super . C l i e n t s ( S C ) ;
Super . c l i e n t s ( S CX , S , S C ) ;
}
}
19
4
Bayesian Network
The dynamic incidence matrix produced for abstract rules over the concrete
model (i.e., diagonal analysis) is given in Table 1. The arbitrary partial order on
rules names was decided as LC > N S > N C > T U > P C > T S > T L > CS.
The resulting Bayesian network is shown in Figure 21.
Fig. 21. BN generated for VoIP case study (TP abbreviates throughput)
0
0
0
A TU
A CS
0
0
0
NC
1.26
(0.104)
-0.186
(0.025)
-0.564
(0.086)
0
0.203
0
(0.323)
0
Applied Rule
PC
TL
0.696 0.00384
(0.51) (0.00511)
0.213
0
(0.0338)
0.536
0.713 (0.124)
(0.267)
-1.0
-0.00839
0
(0.0)
(0.00753)
-0.379
0
0
(0.0401)
1.18
1.88
0
(0.0273) (0.171)
NS
0.423
(0.0353)
-0.252
(0.0311)
-0.2
(0.155)
-0.494
0.464
0
(0.0314) (0.0320)
2.41
0
0
(0.141)
0
Start LC
-1.44
0
(0.106)
1.0
0
(0.0)
1.0
0
(0.0)
0.0192
0
(0.00861)
0.503
0
(0.0314)
A TS
A TL
A PC
A NS
A NC
A LC
Rule name
TS
0.275
(0.0991)
0.254
(0.031)
0.205
(0.155)
-0.00026
(0.00115)
-0.360
(0.0342)
-1.19
(0.0278)
0.239
(0.0304)
-0.521
(0.131)
0
0
0
0
0
0
CS
-0.378
0
(0.0512)
-2.49
0
(0.133)
0
0
0
TU
-0.884
(0.144)
0.142
(0.0368)
0.337
(0.103)
Table 1. Dynamic incidence matrix for abstract rules over concrete model (aggregate of diagonal conflicts and dependencies)
20
21
References
1. Bergmann, G., R´
ath, I., Szab´
o, T., Torrini, P., Varr´
o, D.: Incremental pattern matching for the efficient computation of transitive closure. In: Sixth International Conference on Graph Transformation. Bremen, Germany (09/2012 2012)

Ergebnissliste Hier

inv

UCDRAGON ARM7 BASED BOARD uCdragon –YL