# Adaptive Maximums of Random Variables for Network Simulations

Authors: Rong Nan Chiou; Chia-Nian Shyi
Journal: Journal of Computer Systems, Networks, and Communications
 (2009)

---

## Abstract

In order to enhance the precision of network simulations, the paper proposes an approach to adaptively decide the maximum of random variables that create the discrete probabilities to generate nodal traffic on simulated networks.
In this paper, a statistical model is first suggested to manifest the bound of statistical errors. Then, according to the minimum probability that generates nodal traffic, a formula is proposed to decide the maximum. In the formula, a precision parameter is used to present the degree of simulative accuracy. Meanwhile, the maximum adaptively varies with the traffic distribution among nodes because the decision depends on the minimum probability generating nodal traffic. In order to verify the effect of the adaptive maximum on simulative precision, an optical network is introduced. After simulating the optical network, the theoretic average waiting time of nodes on the optical network is exploited to validate the exactness of the simulation. The proposed formula deciding the adaptive maximum can be generally exploited in the simulations of various networks. Based on the precision parameterK, a recursive procedure will be developed to automatically produce the adaptive maximum for network simulations in the future.


---

## Body

## 1. Intoduction

Simulations are an important technique for the design of systems,
the estimation of performance, and the maintenance of systems [1, 2]. It is widely used in various
fields. For the simulation of complex systems, how to save computing time is an important topic. Moreover, it is also worthwhile to discuss
how to reach acceptable simulative precision. In general, to promote simulative precision will lower simulative efficiency. Therefore, in order to enhance the simulative
precision of complex systems, it is very important to take appropriate tradeoff between precision and efficiency.For example, DQDB
networks are systems with asynchronous
transfer mode (ATM) and time-division
multiple access (TDMA) [3]. Its medium access
control (MAC) protocol
is so complex that the performance analysis of the network is very difficult [4, 5]. To make an exact analysis on the performance of the network is almost impossible [5]. Most papers
estimate the performance of the network by simulations [6–20]. Thus, it only depends on
the precision of simulations to exactly comprehend the behavior of the complex
system. However, if simulative precision is overpromoted, simulative efficiency
will be suppressed. Therefore, how to reach the acceptable simulative
precision and meanwhile take good
tradeoff between precision and efficiency is an important problem for
simulating complex systems. It
is worthwhile to explore, but there are few papers discussing the problem.In simulations, random variables are used to create various
distribution functions of probabilities. These probabilities are applied to direct the input
amplitude of signals or noise as simulating communication systems [1, 2]. For network simulations, probabilities are exploited to control the generation of nodal traffic. The probabilities
assigned to represent nodal traffic are continuous. However, the probabilities created from random variables are
discrete. Due to the inherent
difference between the continuous and discrete probabilities, simulative errors will take place absolutely.In order to take precise simulations, this paper suggests a statistical model. Based
on the model, it is obvious that simulative
precision only depends on the maximum of random variables controlling the generation of network traffic. Based on the perception, a simple formula is proposed
to decide the feasible lower bound of maximums
of random variables. In the formula, the
feasible lower bound is dependent on a precision parameter, denoted byK, and the minimum
probability generating nodal traffic. The larger the precision parameter, the
more the simulative precision. Then, a prime number that is
slightly greater than the lower
bound can be chosen as the maximum of random variables. The chosen maximum can
adapt to the traffic distribution of simulated networks. So, the
adaptive maximum cannot only result
in acceptable simulative precision but
also take desired efficiency. In practice, due to the approach deciding the adaptive maximum, simulative systems can make optimal tradeoff between reaching high precision and saving computing time.So as to understand the
effect of the adaptive maximum on simulative precision, an optical TDMA network
is introduced. The MAC protocol of the optical TDMA network implements traffic
control. The average waiting time of a node on the network is in inverse
proportion to the traffic of the node [21]. Due to the quantitative analysis of
the optical TDMA network, the root-mean-square (rms)
difference between the simulative and theoretic average waiting times of nodes is calculated to validate the
exactness of simulations.In Section2, the suggested statistical model exhibits the relationship between the
statistical error and the maximum of random variables. The discussion for deciding the adaptive maximum of
random variables will also be shown in this section. The MAC protocol
performing traffic control and some working conditions assumed for simulating optical TDMA networks are presented in Section 3. Section 4 illustrates the effect
of the adaptive maximum on the performance estimated by simulations. The validation of simulations will also be shown in this section. Section 5 includes conclusions.


## 2. The Decision of Adaptive Maximums

Before simulations, a set of continuous probabilities is assigned to predefine the
distribution of nodal traffic. In simulations, a set of discrete probabilities,
which corresponds to the set of
continuous probabilities, controls the generation of nodal traffic. The
difference between continuous and discrete probabilities is used to manifest the influence of
the maximum of integral random variables on simulative precision. Then the minimum probability in the set of continuous
probabilities is exploited to decide the adaptive maximum of integral random
variables.In simulated networks, every node has one queue. Queues consist
of cell (packet) buffers. Queues provide first-in-first-out (FIFO) service. The
first cell buffer in a queue is attached to the transmission
system of the simulated network. When an available slot on the transmission system is passed through, the contents of the first cell buffer will be written into the available
slot.The number of cells temporarily storing in queues is dependent on
the traffic generated by nodes. The heavier the nodal traffic, the longer the queuing delay. According to the complex MAC protocol of most networks,
an available slot on transmission
systems appears for some node
randomly. Hence, the prediction of the queuing delay of a specified cell is difficult. In order to
estimate performance, most simulations assume that networks are with heavy load [4, 6, 11, 21]. This
assumption will lengthen queues so
that the theoretic analysis of the
queuing delay of a specified cell will become more difficult. Therefore, how to
enhance the accuracy of queuing delays
is a key topic for network simulations. In order for taking precise simulations, a statistical model must be first
introduced. Based on the model,
the data resulted from simulations can
be applied to calculate the nodal
mean of queuing delays. The queuing delay is defined as the period for which a cell stays in queues.For a node within
networks, every cell generated by disassembling procedures is first
stored in queues. Before the cell is transferred to transmission
systems, it must be sequentially shifted
into the first cell buffer
of nodal queues. When the cell is within the first cell buffer, the MAC protocol will be exploited to decide the moment after that
the node can write the cell out. In above operations, there are two moments relative to the queuing delay. The first moment is the instant
that a cell enters queues. The
second one is the flash that
the cell is sent onto transmission
systems. LetIMi,j and OMi,j in sequence denote the first and second moments of the ith cell generated by the jth node, where i and j are the ordinal number
of cells and nodes, respectively. The queuing delay of the ith cell
generated by the jth node is
designated by Ci,j. Then Ci,j can be represented as(1)Ci,j=OMi,j−IMi,j,1≤i≤Max(R,j),0≤j≤N−1, where Max(R,j) is the ordinal number of
the last cell generated by the jth node, R is the maximum of the
integral random variable used to create
the set of discrete probabilities, and N is the number of nodes within networks.LetPI denote the probability that the Ith node generates traffic. These probabilities, PIs, are chosen in accordance with interested simulative scenarios. The chosen
probabilities are continuous, but their corresponding probabilities generated by an integral random variable are discrete. When a discrete probability
corresponds to a continuous
probability, both probabilities must
be equal theoretically. But, in
practice, the discrete probability is inherently
different from its corresponding continuous probability. If the difference between them is large, statistical delays could not converge on the precise level that is
acceptable.LetX represent an integral random variable that uniformly
distributes over [0, R]. Its probability density function fX(x) can
be presented by(2)fX(x)={1R,0≤x<R,0,otherwise.The random variableX is applied to create PIs for simulations. Let P^I denote the discrete probability corresponding
to PI. The difference between P^I and PI can be represented as(3)|PI−P^I|≤fX(x)=1R,whereP^I=Max(R,I)R.From (3), if R theoretically approaches infinite, the difference
will become zero. Therefore, (3) can be rearranged as(4)limR→∞P^I=PI.If a simulation is with a precise-probability set{P^I=PI,I=0,…,N−1},
the statistical delays of network simulations will also be precise. In a word,
when R theoretically approaches infinite, the statistical queuing delay will
converge precisely.After discussing the enhancement of statistical precision,
statistics of the queuing delay are presented. According to (1), the {Ci,j} is a set of positive random numbers. Let μ(j) denote the mean of
{Ci,j}. Then μ(j)
can be calculated by(5)μ(j)=1Max(R,j)∑i=1Max(R,j)Ci,j. The mean μ(j) represents the average queuing delay
of the jth node.IfR is theoretically infinite, the computing time taken in simulations is
also infinite. In practice, R can be chosen in accordance with PIs. If PIs is small, R must be large enough to
ensure statistical precision. In other words, R must adaptively vary with PIs to promote simulative
precision.LetPmin represent the minimum probability among PIs. Pmin must be
greater than the inverse of R for minimum precise requirement in simulations,
that is,(6)Pmin>1R.In order to guarantee
that the precise degree is acceptable,R must be chosen so that(7)Pmin≥KR, where
K>1 is a positive real number.Then,R, the adaptive
maximum, can be represented by the equation(8)R≥KPmin.In (8), the value K is a
precision parameter. To enlarge K will result in higher precision. On the other
hand, if simulative procedures are with overlarge K, they will consume more
computing time but promote little precision. Thus, the decision of the value K
is dependent on the acceptable degree of precision.Because the recursive
formula of the power-residue method is computationally very efficient [1, 22], it is widely adopted for generating random variables with uniform
distribution.  As the power-residue
method is exploited to generate the uniform-distribution random sequence, the
maximum of the integral random variable must be a prime number. Therefore, the
lower bound of R, indicated by RLB, must be first taken with the
following equation:(9)RLB=KPmin.Then, a prime number
that is slightly greater thanRLB can be assigned as the adaptive
maximum R. The adaptive maximum can result in the optimal tradeoff between
simulative precision and efficiency.


## 3. Optical TDMA Networks

In order for comprehending
the effect of adaptive maximums of random variables on the precision of network
simulations, an optical TDMA networks is introduced. Before depicting the
structure of the network, the deduction for the average waiting time of nodes
on the network (the waiting mean) is presented. The waiting time of a cell is the queuing delay that the
cell waits in the first cell buffer of queues for an available slot on
transmission systems. Based on the structure of the network, several working
conditions are assumed for simulations. Due to these working conditions, an MAC
protocol implementing traffic control is described.For TDMA networks, a node must send requests to
preserve empty slots when it is going to transmit messages. More requests
preserve more slots. As the number of preserved slots of a node becomes large,
the waiting mean of the node will be reduced. Therefore, if a node has more
traffic, its waiting mean will be decreased. The relationship between the waiting
mean and the traffic of theIth node [21] can be presented as(10)μ(I)=[1−(1−T(I))S(1−T(I))+1(1+(S(1−T(I))+1)T(I))]T(I), where
μ(I) and T(I) are the waiting mean and
traffic of the Ith node, respectively, and S is the slot rate of the
optical TDMA networks.Because optical TDMA
networks are high-speed networks, the slot rate can approach infinite. Therefore,μ(I) can be rearranged as(11)limS→∞μ(I)=limS→∞{[1−(1−T(I))S(1−T(I))+1(1+(S(1−T(I))+1)T(I))]T(I)}=1T(I).In (11), μ(I) is a function of T(I). It exhibits that the waiting mean of a node on an optical TDMA network
is in inverse proportion to the traffic of the node. The theoretic waiting mean
will be exploited to validate simulations in Section 4. The structure of
the optical TDMA network is shown in Figure 1.Figure 1
The structure of optical TDMA
networks.In Figure1, the
medium between the slot generator and the slot terminator is an optical fiber. The slot flow on optical fibers is sent by slot generators and sinks into slot
terminators. The number of nodes within the network is N. Nodes are
numbered from 0 to (N−1)
in sequent order. The ordinal number
of every node also relates to the nodal
position in the topology. The period
that the slot generator just completely sends a slot onto optical fibers is
called a slot time. A slot length is the distance that a slot spreads on the
optical fiber. Other working conditions concerning the space between adjacent
nodes, the length of messages, and the
traffic distribution among nodes are described as follows.For all interested
simulative scenarios, the space between adjacent nodes is one slot length. Messages are similar in
length. Every message can be contained in the payload of a slot.The traffic distribution
among nodes affects the operation of traffic control in the MAC protocol. For
the benefit of easily performing traffic control, a basic traffic denoted byTB is introduced. The amount of TB is dependent on the defined
distribution of traffic. In a scenario, the traffic of some node can be several
times the amount of TB. In order to obviously present the influence
of the adaptive maximum on simulative precision, it is assumed that traffic is
uniform distribution among nodes in every simulative scenario. Hence, the
traffic of every node in a simulative scenario is equal to one TB. Because
the optical fiber is a one-way bus, and all messages are not transmitted out of
the network, the (N−1)th node
does not generate any traffic. Let
TN denote the network traffic. Then TN can be presented
by(12)TN=∑I=0N−2T(I)=(N−1)TB. Therefore,
the TB in simulations can be shown as(13)TB=TN(N−1). Based
on the introduction of TB, the approach of traffic control can be
described as follows.In this paper, slot
frames are used to implement traffic control. The slot flow on optical fibers
is partitioned into frames. There are 1/TB slots in a frame. When a
frame is passed to the Ith node, the node can only write one message
into an empty slot within the frame when its queue is not empty. After the operation,
the node must immediately stop writing messages out regardless of whether its
queue is empty or not. After the moment, the node waits for the arrival of the
next frame to restart the controlling process.


## 4. Simulations

The simulation is applied to present the influence of the
adaptive maximum of a random variable on simulative precision. The waiting mean
of optical TDMA nodes manifests the precise degree caused by different adaptive
maximums. The simulative efficiency is dependent on the size of the adaptive
maximum. The larger the maximum of the random variable, the lower the efficiency
of the simulative system. On the other hand, the theoretic waiting mean
calculated by (11) will be used to validate simulative data. The
rms difference between the simulative and theoretic data, denoted by Drms, is defined as(14)Drms=(1N−1∑I=0N−2(μs(I)−μ(I))2)1/2, where μs (I)
and μ(I) are the simulative and theoretic waiting means of the Ith node,
respectively.Two parameters
must be chosen before simulations. The parameters are the number of nodesN and the network traffic TN. The chosen Ns and TNs are based
on interested scenarios. After
the choice of Ns and TNs, (13) can be exploited to calculate the
basic traffic TB. Because messages are one slot in length, the basic
traffic TB can be regarded as the minimum probability Pmin. In order for clearly distinguishing between precise degrees corresponding to
different adaptive maximums, small Pmin is necessary. So, the chosen
TN in all interested scenarios is equal to 0.25.In simulations, two scenarios are interested. In order to certainly
manifest the effect of adaptive maximums, theNs in two scenarios are 40 and 50, respectively. On account of sufficiently
exhibiting the influence of precision parameters on simulative precise degrees,
three Ks are assigned in every scenario. The three Ks in every scenario are 300, 3000, and 30 000, respectively. Then, (9) is used to calculate
the corresponding RLB of every K parameter. In accordance with the
power-residue method, the adaptive maximum R, which is a prime number and
slightly greater than its corresponding RLB, can be finally found. According to the description above, those relative parameters derived from the
TN, Ns, and Ks are listed in Table 1.Table 1
Relative parameters in two scenarios.
TNNPmin=TBKRLBR0.25400.006411300468004680730004680004680013000046800004680001500.005102300588005883130005880005880113000058800005880023For traffic control, the
number of slots in a frame, which is equal to 1/TB, must vary with
scenarios. Due to (13), the number of slots in a frame, denoted by NSF,
can be presented as(15)NSF=(N−1)TN. Hence,
the NSF of the scenario with 40 nodes is 156 and that of the
scenario with 50 nodes is 196. Because uniform traffic distribution is assumed,
the traffic of every node is equal to the TB in each scenario. Consequently,
the theoretic waiting mean calculated by (11) is the same as the NSF in each scenario.In the following figures that show simulative results,
the horizontal axis is the ordinal number of nodes. Because the ordinal number
of nodes is discrete, all curves in figures consist of piecewise lines. The
waiting mean of nodes on the vertical axis is expressed in slot times.After simulations, (5)
is used to calculate the simulative waiting mean of nodes. Figures 2 and 3 show
the variation of waiting means corresponding to two scenarios, respectively. In every figure, the horizontal
solid line represents the theoretic waiting mean. Other three curves are
relative to simulative data corresponding to three precision parameters. In two
figures, it is obviously exhibited that curves will become smoother when the
precision parameter K is enlarged.Figure 2
Waiting means of  40-node  optical TDMA networks.Figure 3
Waiting means of  50-node  optical TDMA networks.Based on the theoretic
waiting mean,Drmss calculated by (14) is used to validate the
simulations. Table 2 presents these Drmss. Every Drms represents the rms difference between the horizontal solid curve and a
simulative curve in each figure. Observing Table 2, larger precision parameter
K and smaller N will result in smaller Drms. Therefore, a simulative
curve will approach the horizontal solid line if precision parameter K is
consecutively enlarged. However, the decrease of Drmss does not
linearly correspond to the increase of K parameters. Consequently, simulative
procedures with overlarge K will consume more computing time but promote little
precision. To adjust K to a proper value can take an adaptive maximum to result
in an acceptable precise level with relative high efficiency. In a word,
network simulations with appropriate adaptive maximums can take optimal
tradeoff between simulative precision and efficiency.Table 2
Drmss corresponding to Ks and
Ns.
NK3003000300004027.404955.4899452.631335040.488278.3492873.369718


## 5. Conclusions

The paper discusses tradeoff between simulative precision and efficiency. Based on the
statistical model of queuing delays, the difference between continuous and discrete probabilities is
used to manifest the effect of the maximum of random variables on the
statistical error. Then a simple method with precision parameterK is proposed to decide the maximum of random variables. The maximum adapts to the minimum
probability among PIs. The adaptive maximum must be enlarged as the
minimum probability of PIs becomes smaller.In order to manifest the effect of the adaptive maximum on the
simulative precision, an optical TDMA network whose MAC protocol performs
traffic control is simulated. The average waiting time of some optical TDMA
node is in inverse proportion to the traffic of the node. The theoretic average
waiting time is exploited to calculateDrmss to validate the
exactness of simulations. Simulative results exhibit that the adaptive maximum
can take optimal tradeoff
between simulative precision and efficiency.In network simulations,
the adaptive maximum not only results in the acceptable degree of precision but
also suitably saves computing time. Based on the precision parameterK, a
recursive procedure will be developed to automatically generate the adaptive
maximum in future.



---

*Source: 383720-2009-04-05.xml*