COMPACT MODELS OF RANDOM POLLING SYSTEMS - Modelling with Generalised Stochastic Petri Nets - page 210

Table 9.5: State space cardinality for various GSPN models of a random
polling system with two servers and queue capacities equal to one. The
notation is of the form n + m where n is the number of tangible markings
and m is the number of vanishing markings

N Fig. 9.4 Fig. 9.5 Fig. 9.6 Fig .9.7 Fig. 9.8

2 57 + 62 21 + 34 9 + 24 6 + 8 6 + 5

3 474 + 384 90 + 141 26 + 80 9 + 12 9 + 7

4 2712 + 1744 312 + 476 72 + 240 12 + 16 12 + 9

5 12480 + 6640 960 + 1435 192 + 672 15 + 20 15 + 11

6 49776 + 22560 2736 + 4026 496 + 1792 18 + 24 18 + 13

7 — 7932 + 10745 1248 + 4608 21 + 28 21 + 15

8 — 19200 + 27640 3072 + 11520 24 + 32 24 + 17

9 — — 7424 + 28160 27 + 36 27 + 19

10 — — 17664 + 67584 30 + 40 30 + 21

50 — — — 150 + 200 150 + 101

100 — — — 300 + 400 300 + 201

requirements that our computer s 2 cannot satisfy.

9.3 Beginning to Exploit Symmetries

The symmetries of the random polling system considered in this chapter can
be exploited in the development of abstract GSPN models. In this section
we use symmetries to obtain simpler server routing subnets.
Since the server routing probabilities do not depend on the index of the
queue the server is leaving, we need not provide separate submodels for the
server routing after the visit at different queues; we can thus simplify the
GSPN model as in Fig. 9.5, providing a more abstract view of the server
routing process.
Note that the GSPN model in Fig. 9.5 is similar to that of Fig. 9.4, except
for the server routing part. Indeed, in this case the server routing submodel
is obtained by folding the four server routing submodels of Fig. 9.4 onto
a single subnet.

Place p r is the folded equivalent of places p (0 r ,p (1 r ,p (2)

r ,
and p (3 r , and each one of the four immediate transitions that in Fig. 9.5
represent the choice of the next queue, is obtained by folding four immediate
transitions of Fig. 9.4; for instance, t r0 represents the choice of queue 0 and

2 The GSPN models described in this chapter were implemented and solved by means
of the GreatSPN [16] package on SUN4 workstations.