5 Application of Network Tomography in LANs

5 Application of Network Tomography in LANs

5.1 The Applicability of the Delay Model

The notions of the delay model provide useful instruments to conduct a link-level delay distribution inference in a network. The measurements can be obtained by adopting one of the techniques described in the Section 4 such as Ping, Traceroute or Pathchar. The choice of the delay model and the reliability of the measurements are to be decided jointly. Only in this case it is possible to obtain optimal result from the estimations. Actually, it is necessary to know how high is the gap, if it exist, between the theoretical instruments provided by the delay model and their applicability. The aim of this section is to reduce this gap and allow the simplest solutions to obtain reliable results.

The present section describes in details the procedure to calculate the estimate of the link delay distribution. It provides, in particular, a general process to compute the iterative analyses of the steady probability distribution described in the Section 3.

The reliability of the results can be tested only by implementing the inference model to a network. An application in a LAN is the easiest way to proof the theoretical forecast, and to test a large scale theory such as Internet Tomography to a small network. Successively it is mentioned the choice of Ping to obtain the measurements. Although, some changes of Ping’s program, are also described to provide reliable measurement to the inference model.

The applicability of a model covers a delicate aspect of an inference model. It is not always possible to test an inference model with simple solutions. Based on the analysis of link delay estimation by Lo Presti in a LAN, this can be possible and the aim of this Chapter is to provide its process of work.

5.2 Modeling Delay

Let T=(V,L) be a logical tree . V represents the set of vertices, with the source 0, the receivers R and the branch point of phys. The packets pair is sent down along the tree

from the root. Let us denote for each node ka random variable^D_ktaking values in the positive real line^R 

 

.^D_k is the random delay that a packet could spend to traverse the link^{( ( ), )f k k L}.^D₀ represents the delay on the root and by convention ^D_k=0. ^D_k=

indicates a dropped packet along the link. The key hypothesis is that the independence of the measured delays along each link can be assumed. For this reason ^D_kare assumed to be independent. It is possible to define the cumulative delay experienced along a path from the root to the node k, like the sum of each random variable ^D_k along the path,

k j k j

X D

  .

According to the discretization by Lo Presti described in the Section 3, each link delay is discretized to a set Q={0,q,2q,…,iq,Bq,}, where q is the width bin, B+1 is the number of possible bin, and  represents the event of packet lost. The probability distribution of^D_k is denoted by  expressed in the Equation 3.4 in the Section 3, and  is the set of_k distribution for each link k V expressed in the Equation 3.5 in the Section 3.

A measurement is the one way delay from the root to the end receivers represented by the set R(k). The set of children of a generic node j is denoted by d(j). Let us define

( )

R k k R

X  X _ as the one way delay occurred on the way from the source to the receivers belonging to the set R(k). ^X_Ris also discretized to the set Q. Figure 3.6 in the Section 3, depicts the space  of ^X_R, in which ^_R=QxQ. The Equation 3.18 in the Section 3 shows the way to obtain ^{ˆ ( )}_k ^d . Using the EM algorithm to maximize the likelihood function

( , ; )

L X D  in the Equation 3.17, the maximum likelihood estimate of^{ˆ ( )}_k ^d , with kV is

( ) ˆ ( ) ˆ ( )

k

( )

k

k d Q k

n d n d

d n d n











(5.1)

Let us focus now on the computation of ^{n dˆ ( )}_k . Knowing ^{n dˆ ( )}_k for each dQ, the probability distribution along the k-th link_k^{( )d} can be obtained. In the Equation 3.26 in the Section 3, let us call the measurement xij depending on i,j simply^x_R. This is the case, in which R(k) is composed of two end receivers. If there are more subsets of two end receivers of R(k), it is necessary to introduce a summitry with i,j indexes.

The computation of ^{n dˆ ( )}_k is quite complicated. The second step of EM algorithm[7,28,29]

shows how ^{n dˆ ( )}_k can be computed.

_{( )} 1 ˆ

ˆ ( )_k ⁿ _l [ _k | _R ^m_R] n d m P D d X x

 

   

( )

ˆ^{( )}_l

[ | ]

R R R k R R

x

n x P D d X x

 

   

^{( )}

( )

ˆ ( ) ˆ

[ | ]

( ) ˆ ( )

[ ]

l R R l

R R k l

R k

x R R

P X x D d

n x d

P X x









 

  

(5.2)

Having the link k fixed, the count ^{n idˆ ( )}_k for each iqQ can be calculated in the Equation 5.2. The iterative algorithm is expressed by the distribution  computed at the step l . Let_k us focus the attention on each of the components of the Equation 5.2.

Computation of ^{n(x )}_R

xRis a 2 x n vector. n represents the number of packets pairs sent to the end receivers of the set R. Each line of _xR belongs to a finite space defined by _R=QxQ. _{n x( R)}represents the number of times the same discretized measurement is present in the vector^x_R.

Computation of P_{ˆ( )l} [X_R x_R]

  and P_{ˆ( )l} [X_R x D_R| _k d]

  

This is the most complex aspect of the computation. Let R(k) the set of receivers descendent from the node kV. If kR, there will be assumed R(k)={k}.

Let us define Y_{R k}( ) ( )Y_{j j R k} ( ) as the delay observed from receivers descendent from node k. Let ZR k( ) YR k( )Yf k( ) be the delay measured from node f(k) down to the receivers of k. Let us denote _k(z_{R k}( ); ) ^P Z[ _{R k}( ) ^z_{R k}( )], kV, z_{R k( )}^{num R k( ( ))}.If , for example , the tree is composed of three vertices, Figure 5.1 shows the corresponding zR k( )for a node k.

The _k(z_{R k}( ); ) respects the following recursion

_k^(z_{R k( )}^{; )} _k^(z_{R k( )}⁾ kR (5.3) _k( _{R k}^{( )}; ) _k( ) _{( ) j}( _{R j}^{( )} ; )

d Q j d k

z d z d

    

 

    kR (5.4)

In the Equation 5.4 z_{R k}( ) (z_{R j}( ))_{j d k} ( ).

Figure 5.1: For each k it is possible to calculatezR k( ). From the total YR k( )delay from the root till the set R(k) the Yf k( ) is subtracted.

There are the necessary instruments to calculatePˆ( )_l [X_R x_R]

  . In fact, it is sufficient to observe thatYR ZR(1), where 1 denotes the child node of the root node 0.

The Equation 5.5 shows that the delays observed at the receivers are equal to the delay experienced from the root down to the receivers of 1, which represent the set R.

Z_R(1) Y_R(1)Y_f(1)Y_R(1)Y₀ Y_R (5.5) It is possible then to define the computation of Pˆ( )_l [X_R x_R]

  as

P_{ˆ( )l} [X_R x_R]



₁(z_R(1);



ˆ^{( )l} )



₁(y_R;



ˆ^{( )l} ) (5.6)

The computation of Pˆ( )_l [X_R x_R|D_k d]

   can be obtained in a similar way, even if it is more complicated thanPˆ( )_l [X_R x_R]

  , because the probability in this case is calculated by conditioning to each possible value of dQ and for each measurement^x_R . The approach to compute this probability is the following :

_ˆ^{( )}_l [ | ] _{ˆ ,} ^{( )}_l [ ]

R R k k d R R

P_ X x D d P X x

     (5.7) where the distribution ˆ^{( )}_{k d}^l_, is obtained from  by setting ˆ^{( )l} ^{ˆ ( ') 1( )l d}  when d=d’ and

ˆ ( ') 0( )^l d

  otherwise. This process will be explained better in the next section where it is described the practical application and the computation of these probabilities. It is possible to define the computation Pˆ( )_l [X_R x_R|D_k d]

   as:

( ) ( )

,

1 ( ),

ˆ _l

[ | ]

ˆ _l

[

]

( ; ˆ )

k d

R R k R R R k dl

P

_

X x D d P X x y

 ^

 

   

(5.8)

Now all the probabilities in the Equation 5.2 are computed. It is vital to understand that the Equation 5.2 works, when a branch node k is chosen. Then n dˆ ( )_k must be calculated for each d. The computation of the Equation 5.7 is rather difficult, because it depends not only on the measurement but also on the current d. The implicit difficulty is that in order to calculate each probability, it is necessary to know the current distribution of the other link, which belongs to the path. It must be calculated for each link, and this increases the computational burden of the inference algorithm. The Equation 5.2 shows the recursion of the equation, where ^ˆ_k^{( )l} ( )d represents the probability delay distribution of link k, calculated in d and in the previous step. The choice of the initial distribution is vital if a fast convergence is required. It is described in [6]. It If the tree is of small dimension, an arbitrary initial distribution can be chosen for each link. The convergence is verified by the consistence property of the algorithm [13]. The only parameter which can vary is the number of necessary iterations to reach the steady solution of the distributions, that is the local maximum of the Likelihood Function.

5.3 Pseudo Code

The pseudo code to compute the link delay distribution will be described in the present section. It is composed of the above mentioned EM algorithm.

The variable l represents the current step. The variable threshold represents the parameter which allows the algorithm to know if the maximum is reached. In fact, by comparing the current inferred estimate with the previous one, the difference between them, can be defined. This value is expressed by the variable threshold. If the threshold is low, more iterations are necessary. The threshold defines the surface of the multidimensional maximum point. The maximum will be a point with a null surface, only if there is infinite equality of each component of the current estimate to each component of the previous one. In this case the threshold is represented by the value zero. In the practical application it is advisable to use a large threshold and then to decrease it until the computational burden will become too heavy and the number of the iterations be too high.

Usually, a threshold of one percent is sufficient. If the tree has few nodes, it is possible to decrement the threshold. The problem can be contained in the approximation processes of the compiling program. The pseudo code implemented by Francesco Lo Presti [29] is depicted in the Figure 5.2 .

procedure main { l=0 ; choose



ˆ^{( )l ;}

do { % computation of the expected counts for each kV

for each dQ n dˆ ( )_{k = 0 ;}

for each x_R_R n dˆ ( )_{k + =}

( ), ( ) ( )

)

, )

_ (1, , ˆ

( ) ˆ ( )

_ (1, ˆ

k dl l

R l k

compute yR

n x d

compute yR

 

  

end end end

%computation of the current estimates

for each kV for each dQ

^{( 1)}

ˆ ( ) ˆ

_k ^l

( ) n d

^k

;

d n



^



end end l ++;

} while |



ˆ^{( )l} 



ˆ^{( 1)l} |> threshold ;

 

ˆ  ˆ^{( )l ;} }

double function compute_(k, z, ) { if (k  R)

return



ˆ_k^{( )}z _; else

return _k

( )

( )

_ ( ,

_{R j}( )

, );

d Q

 d

j d k

compute  j z d 

 



 

}

Figure 5.2: The pseudo code.

5.4 Application to the Router Lab LAN

The goal of the present work is to apply Network Tomography on a LAN. Network Tomography is usually referred to Internet Tomography because it focuses on a large scale network. The aim of this work is to test a delay probability distribution inference in a small scale network. Applying the mentioned algorithm to a LAN, the theory to an accessible and bordered network can be used. All the experiments have be conducted in the Router Lab of the Department of Distributed System of the University of Wuerzburg (Germany). The physical network, to which the analysis of probability distribution delay is applied, is depicted in the Figure 5.3

Figure 5.3: The physical tree is composed by the root Ull and the end receivers Latona and Venus.

The host Ull represents the root or the source. Latona and Venus are the end receivers. n packet pairs are sent from Ull to Latona and Venus. Figure 5.3 shows the physical tree.

Applying the Model Tree described in the Section 3.2 , it is possible to make a graph of the logical tree shown in the Figure 5.4. Each link is labeled with a number. The branch node 2 is k, and the node 1 is its parents f(k). R(k), the set of end receivers that will receive the packet pairs sent from the root, are nodes 3 and 4.

Figure 5.5 shows the tree, to which the Lo Presti algorithm will be applied. The algorithm works on the link separated by a branch node. In this case the branch node is the number 2.

The goal is to estimate the delay distribution for the links 2, 3 and 4.

Figure 5.4. Logical tree. Denote the node k, its parent f(k) and the set of receivers R(k).

A packet pair is sent from root to host 3 and 4. The first member of the packet pair will reach the host 4 and the second member the host 3. Figure 5.6 shows how the two members of the packet pair travel in the network. The inference strategy works on the common path

Figure 5.5: The logical tree is composed of three links. The goal is to estimate the probability delay distribution ,₂  and3  .4

the packet pairs crosses. In fact, the algorithm cannot distinguish between the different links from root until node number 2, and considers the global link from the root to the host number 2. The branch nodes play a very important role in defining, which link can be analyzed by the algorithm. The key sentence is that the inference strategy works on the common path of the packet pairs. The measurement represents the one way delay from the

Figure 5.6: The first member travels with direction of the node 4, and the second member to node 3.

root to the set R(2). However, it is not necessary to work with this kind of measurement. In the Section 4 it is shown that to obtain this measurements is not an easy task and a synchronization between two hosts is required.

Figure 5.7: The red line show the one way direction, the black, show the coming back. It is easy to note the same shared path between the two directions.

Figure 5.7 helps to understand how the problem can be solved by means of applying the RTT measurement. The first and second members cover the same path to go and to come back. For example, the first member is directed to the end host 4, makes the trip 0, 2,4 and comes back covering the same path, 4, 2 ,0. There is no difference between the application of the inference to the one way measurement and the RTT, because the member makes the same way. It is a specific case for this application, when there is the certainty that the packet member travels along the same path. This simplification makes the RTT calculation preferable to calculating the one way delay. This computation can be made more easily applying one of the tools mentioned in the Section 4.

5.5 The Choice of Ping

In the Section 4 some tools to measure the RTT of the packets pair along a path have been described.

Ping, Traceroute and Pathchar are equivalent in the RTT computation where the ambient to measure is a small area network, such as LAN. The path is relatively short and the computation of the RTT is easy to conduct and its precision is reliable enough.

The goal is to choose one of these three programs. The aim of the present work is to offer an inference instrument able to operate in all the LANs. To obtain a universal instrument, it is preferable to focus on the most simple solutions.

In this case, Ping represents this simplest choice. Ping is an administrator’s tool that all hosts should implement. It does not have any restrictions to work. Ping is a common tool and is really easy in use. Traceroute and Pathchar are focused on other specific goals apart from RTT, such as the record of the routes, latency and bandwidth estimate. This information is not the subject of interest to the inference algorithm this work is devised to implement. Besides, Traceroute and Pathchar depend more heavily on the operative system of the machine in which they run. Ping, on the contrary, is a more transparent tool. In a LAN, the RTT of Ping is reliable, because the path to test is short and is composed of few routers.

The precision of the measurement is linked to the dimension of the bin size of the Lo Presti algorithm. In fact, why should be a higher degree of precision of the measurement required, if it will be eliminated during the discretization process? This example shows, why measurements and inference strategies should be chosen jointly.

The Figure 4.2 in the Section 4 shows an application of Ping. It works simply by typing the destination host to ping and the number and the dimension of the packet to send [30]. The goal is to obtain the RTT for a packet pair described in the Section 3. Two ICMP packets

should be sent consequently to the respective end host destinations as Figure 5.8 explains.

The Figure 3.2 in the Section 3 shows the trip of a packet pair along the path. The Ping program iputils-20020927 is able to ping one host at a time. It must ping two hosts at the same time. A first packet should be sent to the address of the first end node, and the second packet should be sent immediately after the first one to the address of the second node. The Figure 5.8 shows this request.

Figure 5.8: Two ICMP packet should be sent in the time ^t₁and ^t₂to the address 1 and 2.

It is vital to define the processing gap ^{PG |t}₁ ^t₂^| as the current time between the first and the second ICMP. The inference strategy requires a PG0 that is the second ICMP leaves immediately after the living of the first. Both packets should travel one after another and come back in the same order to the source. An PG0 allows the packets to test the same state of the traffic network and is essential for the reliability of the measurement. The algorithm works on the common path the two packets cover. The second ICMP tests the congestion of the first one. This permits the second packet to be behind the first one with a high probability. This operation should be implemented by Ping.

Let us focus the attention on the Ping iputils and its processing gap. Ping iputils allows to ping one host at a time and listen to the ICMP Echo Reply coming back. Only after the answer is received, another ICMP Echo Request is sent. This is a serious problem, because the Ping iputils allows to work only with one end host. There is not the possibility to initialize a sequence of two ICMP sending process to two different end hosts.

Figure 5.9: The normal operation of Ping iputils. The second packet can be sent only after the source has received the answer of the first one.

The implementation shown in Figure 5.8 must be reached by modifying the original program. Ping iputils is able to implement the operation shown in the Figure 5.9. The source sends the first packet and then, only after the Echo Reply is received, Ping sends another packet to the second host. This operation is rather difficult. In practice, to change the address of the first end host in the address of the second end host means to initialize another Ping process. The Figure 5.9 shows how large is the processing gap. This cannot be a reliable measurement and it cannot be applied to the inference strategy. It is necessary hence to modify the Ping iputils in a program able to work like the pseudo code depicted in the Figure 5.10. This pseudo code shows how the new modified Ping works. The icmp_seq represents an index which will play an important role in the modified Ping. n represents the number of the packets pairs to send. The result of the measurements is a n x 2 vector ^x_R. The original Ping program is replaced with the modified Ping program.

for icmp_seq=1 to n

send Packet 1(icmp_seq) to host 1 send Packet 2(icmp_seq) to host 2

print timestamp Packet 1returned (icmp_seq) from host 1 print timestamp Packet 2returned (icmp_seq) from host 2 end

Figure 5.10: The pseudo code represents the functioning of the modified Ping program.

Modified Ping

The original Ping is the version iputils-20020927, written by Mike Muuss, U.S. Army Ballistic Research Laboratory, in December 1983.

The most important modifications conducted in the process of the present work are:

1. Duplicating the buffers, the structures and the necessary variables to describe an ICMP packet. The task of a second buffer is to allocate the packet direct to the second host.

2. Duplicating the necessary variable to count the ICMP packet sent.

3. Adding a control to be able to specify in the command line the second host which has to be pinged.

4. Adding a code responsible to traduce the hostname string in the format network-byte- ordered.

5. Making a second socket (icmp_sock2).

6. Modifying the send_probe() function, so that it can send two messages by using the sendmsg() function, to the two different sockets. One socket is for the end host 1 and the second is for the end host 2.

7. Duplicating the checksum() function able to check the right returned second packet.

These are the most important steps of an accurate work of modificating. In fact, each step contains the defining the new variables, descriptors and functions.

The modified Ping has been elaborated and tested in the Wuerzburg at Router Lab of the 3 Department of Informatics(Germany). Figure 5.11 shows an application of the modified Ping. All the options of the Ping iputils-20020927 are maintained[30]. The most interesting options are the following.

The option –c responsible for managing the number of packet pairs to send. This quantity is represented by n in the pseudo code in the Figure 5.10. The other option is -s responsible to declare the dimension of the ICMP packet to send.

The Chapter 6 describes the results of the inference algorithm obtained by changing the dimension of the packets sent. It is very important, because the necessary delay to cover a path is proportional to the dimension of the packet and depends on the speed of the path.

Figure 5.11: An application of the modified Ping program. The end host Latona and Venus are pinged. N=4 and the dimension of the packet is 56 byte.

The icmp_seq is vital for the right functioning of this new tool of measurement. It represents the current packet pair sent. It can check the right order of each member of the packet pair. For example, the Figure 5.11 shows how the right order of the two members is achieved. This is really an important index, because it allows to notice if the second member goes past the first during the trip. The icmp_seq “labels” the member of the packet pair, making recognizable its arrival to the source.

Another advantage is that the icmp_seq can be used as a pointer in the construction of the vector ^x_R. Each line of ^x_Rcorresponds to a same icmp_seq, and the columns, to the first and second member of the same packet pair. All the measurements in this work are obtained by applying the modified Ping.

5.6 Implementation

This section explains how the modeling delay can be applied to the logical tree depicted in the Figure 5.5. The set of the nodes k is composed of node 2, 3 and 4. It is possible to define only a R(2), because the nodes 3 and 4 do not have children nodes. That is why the only node satisfying the condition kR is the node number 2. The Equations 5.3 and 5.4 can be written in the following way:



₃(z_R(3); )







₃(z_R(3)) k=3R (5.9)



₄(z_R(4); )







₄⁽z_R(4)⁾ k=4R (5.10)

²

(

_R⁽²⁾

; )

²

( )

₍₂₎ ²

(

_R⁽²⁾

; )

d Q j d

z d z d

    

 

   

k=2R (5.11)

From the Equation 5.1 it is possible to estimate the value of the delay probability for each value of dQ as

ˆ ( ) ˆ ( )

_k

n d

^k

d n



^ k={2,3,4} (5.12)

Choice of initial distributions ^ˆ_k⁽⁰⁾

The logical tree is of a small dimension. The typical initial delay probability distribution ^ˆ₂⁽⁰⁾,^ˆ₃⁽⁰⁾ , and^ˆ₄⁽⁰⁾ can be chosen. The most advisable choice is the uniform probability distribution depicted in the Figure 5.12. Each value dQ at the step zero has the same probability.

Figure 5.12: Each value belonging to the set Q has the same probability.

The algorithm works iteratively, and the distribution will change until the stationary probability distribution is reached. The algorithm models the distributions, giving more weight to the event of delay with more probability to be verified. The value of delay with a

null probability represents a delay that cannot ever be tested on the link. After a number of iterations, the algorithm reaches the steady solution and the distributions can be analyzed.

Computation of P_ˆ( )_l [XR xR]

This computation is obtained by using the Equation 5.6 and the recursion of the Equation 5.11. The Figure 5.13 shows the graphical procedure of the computation.

(0) 2 3 4 2 3 4

ˆ

[

_R

(2 ,3 )] (0)* (2 )* (3 ) ( )* ( )* (2 )

P X d d d d d d d



         





₂(2 )* (0)*d



₃



₄( )d (5.13)

Figure 5.13: A graphical approach to the computation of Pˆ( )_l [X_R x_R]

 

ˆ( )_l [ _{R R}]

P X x

  is calculated for each measurementx_R, and it does not depend on the value d, but only on the specific value of^x_R. Besides, the computation depends on the step l.

Each iteration of the algorithm changes the previous distributions, and a new computation of Pˆ( )_l [X_R x_R]

  must be calculated with the new distributions.

Computation of Pˆ( )_l [X_R x D_R | _k d]

  

This computation is the most complicated. There is not only the dependence by the measurement, but also by the value of d. This is a conditioned probability, which is the probability that a measurement assumes the value ^x_Ralong the path, by conditioning to a measured delay equal to d over the link k of the path. It is vital then to compute this probability dQ and ^x_R measured. This is the most difficult part of the algorithm, because the complexity increases if the bin size decreases and B augments.

The computation is obtained by using the same strategy as for the computation of

ˆ( )_l [ _{R R}]

P X x

  . It is necessary to compute the new probability distribution

ˆ , ( )_l [ _{R R}]

k d

P X x

  mentioned in the Equation 5.7 . It is obtained by setting the distribution ˆ ( ') 1_k d

  , where d’=d and ^{ˆ (2 ) 1}₂ ^d  ˆ ( ') 0_k d  otherwise.

Figure 5.14. The  is set for d’=2d and the ^ˆ₂ Pˆ( )_l [X_R (2 ,3 ) |d d D2 2 ]d

  

can be found.

For example, if the goal is to estimate Pˆ( )_l [X_R x_R|D_k 2 ]d

   , the distribution

ˆ ( ' 2 ) 1_k d d

   and the Equation 5.11 can be applied. The Figure 5.14 shows the graphical approach to understand the computation. In this case, given the measurement ^X_R=(2d,3d) the probability Pˆ( )_l [X_R (2 ,3 ) |d d D2 2 ]d

   is obtained by setting the distribution ˆ (2 ) 12 d

  .

Figure 5.14 shows a particular computation for d’=2d, given the measurementx_{R. In this} case the probability is expressed by the Equation 5.14.

_ˆ⁽⁰⁾

[ (2 ,3 ) |

2

2 ]

_ˆ2, ⁽⁰⁾

[

] 3(0)* 4( )

R d R R d

P

_

X d d D d P X x

  

   

(5.14)

When all the probabilities are computed dQ, the set of _{ˆ ,} ^{( )}_l [ _{R R}]

k d

P X x

  is obtained

and can be used in the Equation 5.2. By changing the node k the _ˆ3, ⁽⁰⁾[ _{R R}]

d

P X x

  and

ˆ4, (0)[ _{R R}]

d

P X x

  are computed.

The pseudo code described above makes the computation of ^{n dˆ ( )}_k easy.

The simplest example

The following is a theoretical example that shows the computation of ^{n dˆ ( )}_k given the one way measurement. n=4 , the bin size q=0.1 ms and B=5. The case of value  is omitted.

The algorithm is implemented in the Matlab language.

Define a vector of the measurement as

Xmeas=[0.123,0.21;0.24,0.281;0.123,0.23;0.27,0.367]

Choice of the discrete set Q

The first step is the discretization to the set Q={0,0.1,0.2,0.3,0.4} following the procedure explained in the Figure 4.2 the discretized ^X_measvector is the vector ^X_R:

XR=[1,2;2,3;1,2;3,4].

Choice of the initial probability delay distribution

The probability distribution at step l=0 has a uniform shape for each link. The Figure 5.15 shows the uniform distribution.

Figure 5.15. The initial delay probability distribution is an uniform discrete probability distribution.

Computation of P_ˆ( )_l [XR xR]

Applying the Equation 5.6, the vector P_ˆ(0)[XR xR] is

_R

1 2 2 3 1 2 3 4 X

 

 

 

 

 

 

 

 ₍₀₎ ˆ

0.0160 0.0240

[ ]

0.0160 0.0320

R R

P X x



 

 

 

 

 

 

 

  (5.15)

Computation of

P

_ˆ( )_l

[ X

_R

 x D

_R

|

_k

 d ]

According to the Equation 5.7, the vector Pˆ(0)[X_R x_R |D2 0]

   with k=2 is:

_R

1 2 2 3 1 2 3 4 X

 

 

 

 

 

 

 

 _{ˆ(0) 2}

0.0400 0.0400

[ | 0]

0.0400 0.0400

R R

P X x D



 

 

 

 

 

 

 

  

(5.16)

Computation of n dˆ ( )_k

By applying the Equation 5.2, the count nˆ (0)₂ can be computed:

⁽⁰⁾

(0)

2 (0)

2 ˆ 2

ˆ

[ | 0]

ˆ (0) ( ) ˆ (0)

[ ]

R

R R

x XR R R R

P X x D

n n x

P X x









 

  

=1.5833 (5.17)

Using the Equation 5.16 and 5.17 to calculate ˆn id₂^{( )} for 0 < i < B, the vector n dˆ ( )_{2 will} be obtained in one step.

₂

1.5833 1.5833 ˆ ( ) 0.5833 0.2500

0 n d

 

 

 

 

 

 

 

 

 



(5.18)

The new delay probability distribution after one step is obtained by applying the Equation 5.12.

₂⁽¹⁾

0.3958 0.3958 ˆ ( ) 0.1458 0.0625

0

 d

 

 

 

 

 

 

 

 

 



(5.19)

The first comparison of

 ˆ

₂⁽⁰⁾and

 ˆ

₂⁽¹⁾ shows how in the process of the iteration of the algorithm the distributions trying to reach the steady solution are modeled.

All the computations are made for the nodes k=3, 4 and the distributions

 ˆ

₃⁽¹⁾ and

 ˆ

₄⁽¹⁾

are the following:

₃⁽¹⁾

0.3958 0.3958 ˆ 0.1458 0.0625

0



 

 

 

 

  

 

 

 

 

₄⁽¹⁾

0 0.3958 ˆ 0.3958 0.1458 0.0625



 

 

 

 

  

 

 

 

 

(5.20)

Congruence

In a probability distribution the congruence property must be constantly referred to. The congruence means that the summitry of each component of a probability distribution must be unitary. It is necessary to control each step of the process.

Accuracy and number of steps

The accuracy is expressed by the threshold defined by the pseudo code. The advisable value is of 10e-2. The program works until this threshold is passed. The number of necessary steps to reach the steady solution changes and depends on the choice of the threshold.

Results

Threshold= 10e-2 Step=7

₂⁽⁷⁾

0.500 0.250

ˆ 0.250

0 0



 

 

 

 

  

 

 

 

 

₃⁽⁷⁾

0.001 0.999

ˆ 0

0 0



 

 

 

 

  

 

 

 

 

₄⁽⁷⁾

0 0.002

ˆ 0.998

0 0



 

 

 

 

  

 

 

 

 

(5.21)

These results represent the steady solution of the delay distribution probability along the links 2,3, and 4. Certainly, it is a really simplified example, and the shape of the distributions is readable enough. Next Chapter shows some experiments on a large time interval with a high number of bin. In this case the number of necessary iterations increases. The Figures 5.16 ,5.17 and 5.18 show the probability delay distributions obtained by Matlab.

-0.50 0 0.5 1 1.5 2 2.5 3 3.5 4

0.1 0.2 0.3 0.4 0.5

Delay Probability Distribution - Link 2

Delay d (ms)

Probability a2(d)

0.5

0.25 0.25

Figure 5.16: Delay Probability Distribution along link 2.

-0.50 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1 Delay Probability Distribution - Link 3

Delay d (ms)

Probability a3(d)

Figure 5.17: Delay Probability Distribution along link 2.

-0.50 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1 Delay Probability Distribution - Link 4

Delay d (ms)

Probability a4(d)

Figure 5.18: Delay Probability Distribution along link 2