8.1 Approximation of the QoS Observations of the Single Stage Game

169

allocations during an SSG, is aperiodic. As already stated in Section 7.2.2.1, p. 135, the observed delay variation Ξobsi is not used here. An upper bound can be derived from the approximation, which is given in the following equation for the

sake of completeness. Again, TXOPlimit ∆demi Θdemi for any i Ν ={1, 2} . The upper bound of the observed delay variation is given as

Ξobsi = ∆dem−i Θdem−i , i, −i Ν ={1, 2} .

8.1.4Result

As the result, the expected throughput observations Θobsi ,−i can be approximated by Equation (8.11), and for the observed allocation periods ∆obsi ,−i an upper bound is given by Equation (8.12). In summary, with

Θobsi ≤ Θdemi , ∆obsi ≥ ∆demi , i Ν ={1, 2} .

(8.13)

The model P results in the following analytical approximation for the observation of an SSG:

Θi

Θ−i

→

P :=

dem ,

dem

i

−i

∆dem

∆dem

i

i

. (8.14)

Θi

= min

Θi

,

Θdem∆dem

i

−i

obs

dem

i

−i

,

i, −i Ν ={1, 2}

Θdem∆dem +Θdem∆dem

i

i

−i

−i

∆obs = ∆dem +∆dem

Θdem

Here, it is not necessary to indicate that the demand of the opponent player may be an estimation from the history of earlier games. This may be the case however if P is used by a player to decide what action to take next. A player does not have the knowledge about the demand of the opponent player, it estimates this from the history of actions with the prediction method as explained in Section 7.4, p. 152. In the following Section 8.1.5, the model is evaluated against simulation, before an analysis of the SSG is given in Section 8.2.

8.1.5Evaluation

In this section, a comparison of the model with simulation results is presented to assess how accurate the Markov model P represents the outcome of the SSG. Three different scenarios have been selected to review all relevant configurations. In the first case scenario, the player 1 demands a smaller resource allocation interval than player 2, and the demands for the share of capacity of player 1 are

170	8. The Superframe as Single Stage Game

varied. In the second case both players demand the same resource allocation interval, and in the third case player 1 demands a larger resource allocation interval than player 2. In all cases, the demand for the share of capacity (demand for throughput) of player 1 is varied, and results are given with respect to this varying demand. In simulation, EDCF-background traffic of1 Mbit/s , with a TXOPlimit of 100µs was assumed. The analytical approximation does not capture the EDCF specifically. With SFDUR=200ms , the maximum duration of the EDCFTXOPs, defined by the TXOPlimit is smaller than the minimum duration of the resource allocations by the players. Hence, there are only minor influences on the game outcomes that result from the EDCF. The EDCF background traffic is nevertheless helpful in simulation. Even if it does not significantly influence the results of the observed shares of capacity and of the observed resource allocation intervals for the two players, simulation results becomes more realistic because of the random characteristic of the EDCF medium access.

8.1.5.1First Case: Player 1 Demands Shorter Resource Allocation Intervals than Player 2

First, results are compared for a scenario where player 1 demands a shorter resource allocation interval ∆1dem = 0.02 than is demanded by player 2, ∆dem2 = 0.03 , that means that ∆1dem< ∆dem2 . Figure 8.2, p. 173, shows the resulting outcomes of an SSG for both players, calculated with the analytical model P, as well as simulated. The demand for share of capacity of player 1 is varied between Θ1dem = 0

and Θ1dem = 0.9 . The left figure of Figure 8.2 shows the observed shares of capacity Θ1,2obs over the varying Θ1dem , and the right figure shows the observed resource

allocation intervals ∆1,2obs over Θ1dem . It can be seen that the observed share of capacity increases with increasing demand up to a certain saturation point, according to simulation and analytical approximation (solid lines in the left figure). The observed share of capacity of player 2 keeps constantly at its demanded level, as long as the channel is not heavily overloaded (dotted lines in the left figure). This is captured by the simulation and the approximation. The reason for the result that player 2 achieves its demand in share of capacity is as follows. It is very unlikely that player 1 takes resources that player 2 wanted to allocate by itself: once player 2 successfully allocated a resource, it keeps operating for a relative long time of

d 2 = Θdem2 ∆dem2 SFDUR = 0.4 0.03 200ms = 2.4ms ,

repeated every D2 = ∆dem2 SFDUR = 6ms . According to Equation (7.14), the players tolerate delays of resource allocation of

8.1 Approximation of the QoS Observations of		the Single Stage Game	171
SFDUR ∆tolerance2	= 200ms 10−4 ( 1 +100 −1) ≈1,8ms .
Thus player 2, although attempting to		allocate resources more	often, i.e.,

every 4ms , with variable duration, cannot prevent player 2 from accessing the channel as long as the resource allocation attempts do not collide. This is indicated by the simulation results, and the results of the analytical approximation. With heavy overload ( Θ1dem > 0.8 ), the approximation fails to model the effect of repeated collisions, which in general results in a loss of capacity for the player that demands the longer resource allocations, here the player 2.

The right figure in Figure 8.2 shows the observed resource allocation intervals ∆1,2obs . It can be seen that the observed resource allocation interval of player 2 increases with the increasing demand for share of capacity of player 1, which is again indicated by simulation and approximation. Note that an upper limit of the maximum observed resource allocation interval is approximated, according to Equation (8.12). The simulation results show some variations of the delay, which is a result of correlated resource allocation times and unpredictable collisions. Although demanding ∆1dem = 0.02 , the player 1 observes a larger resource allocation interval as this is obviously determined by the player that demands the longer resource allocations, here the player 2. Simulation and analytical approximation show the maximum observed resource allocation interval within one SSG. Note that the duration of a SSG is defined by the superframe duration, which is set to SFDUR=200ms in this thesis.

8.1.5.2Second Case: Player 1 and Player 2 Demand the same Resource Allocation Interval

In this section, results are compared for a scenario where player 1 and player 2 demand the same resource allocation interval ∆1dem = ∆dem2 = 0.02 . Figure 8.3, p. 173, shows the resulting outcomes of an SSG for both players, calculated with the analytical model P, and simulated. Whereas the results of the observed share of capacity show clear similarities in simulation and analytical approximation (left figure in Figure 8.3), it can be seen that the approximated observations of the maximum resource allocation intervals are satisfying for player 2, but too pessimistic for player 2 (right figure in Figure 8.3). This is due to the limitation an upper limit instead of an expected value is approximated. Theoretically, without regarding the EDCF-TXOPs, a maximum delay of resource allocations of player 1 is approximated to ∆1obs = 0.02 + ∆dem2 Θdem2 = 0.08 , see Equation (8.12). The simulation results show that this must not necessarily happen during an SSG, especially in times of low demand ( Θ1dem< 0.2 ). Note that when both players

172	8. The Superframe as Single Stage Game

demand the same resource allocation interval, correlations in time of resource allocation attempts are very likely, which make approximations difficult.

8.1.5.3Third Case: Player 1 Demands larger Resource Allocation Intervals than Player 2

Finally, results are compared for a scenario where player 1 demands a longer resource allocation interval ∆1dem = 0.02 than is demanded by player 2, ∆dem2 = 0.01 , that means that ∆1dem > ∆dem2 . From Figure 8.4 it can be observed that in this case the simulation results and the analytical approximation are very close to each other in nearly all cases.

8.1.5.4Conclusion

The Markov model P was introduced for an analytical approximation of the outcome (observation) of an SSG. The main motivation was (1) to allow an analysis of the game on a purely analytical basis, and (2) to allow a player to estimate possible outcomes of the game in advance, while decision taking. Both goals are met. The model P is accurate enough to allow players to capture the statistical characteristics of the SSG. Whereas the model is simple enough to allow players to estimate the outcomes of an upcoming game in advance, this model can also be used for the equilibrium analysis of the SSG, which is described in detail in the next section.

8.2Nash16 Equilibrium Analysis

Note again, that, in what follows, for any parameter that may change its value throughout the MSG, the dependency on the stage number n is not shown in the equations, for the sake of simplicity.

Having an accurately defined analytical approximation of the SSG, it is now possible to investigate the SSG in terms of stability, and payoff maximizing. The outcome of an SSG that is in the interest of the players is the payoff vector as defined in Equation (7.16). This payoff depends on the observed QoS parameters as defined in Equation (8.11) and Equation (8.12). A fundamental question to be answered is what action to take as best response to any action the opponent takes. Does this best response action, denoted as ai* for a player i, exist? If it exists, is it unique? A commonly used solution concept for the question of what action to be taken in an SSG is the Nash equilibrium solution concept (Nash 1950a, Nash 1950b).

16 John F. Nash (*1928), mathematician, USA