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 a random variabletaking values in the positive real line. is the random delay that a packet could spend to traverse the link. represents the delay on the root and by convention =0. = 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 are 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 along the path,.
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 is denoted by expressed in the Equation 3.4 in the Section 3, and is the set of 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 as the one way delay occurred on the way from the source to the receivers belonging to the set R(k). is also discretized to the set Q. Figure 3.6 in the Section 3, depicts the space of , in which =QxQ. The Equation 3.18 in the Section 3 shows the way to obtain . Using the EM algorithm to maximize the likelihood function
in the Equation 3.17, the maximum likelihood estimate of, with kV is
(5.1)
Let us focus now on the computation of . Knowing for each dQ, the probability distribution along the k-th link can be obtained. In the Equation 3.26 in the Section 3, let us call the measurement depending on i,j simply. 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 is quite complicated. The second step of EM algorithm[7,28,29] shows how can be computed.
(5.2)
Having the link k fixed, the count for each iqQ can be calculated in the Equation 5.2. The iterative algorithm is expressed by the distribution computed at the step l . Let us focus the attention on each of the components of the Equation 5.2.
Computation of
is a 2 x n vector. n represents the number of packets pairs sent to the end receivers of the set R. Each line of belongs to a finite space defined by =QxQ.represents the number of times the same discretized measurement is present in the vector.
Computation ofand
This is the most complex aspect of the computation. Let R(k) the set of receivers descendent from the node kV. If kR, there will be assumed R(k)={k}.
Let us define as the delay observed from receivers descendent from node k. Let be the delay measured from node f(k) down to the receivers of k. Let us denote , kV, .If , for example , the tree is composed of three vertices, Figure 5.1 shows the corresponding for a node k.
The respects the following recursion
kR (5.3)
kR (5.4)
In the Equation 5.4 .
Figure 5.1: For each k it is possible to calculate. From the total delay from the root till the set R(k) the is subtracted.
There are the necessary instruments to calculate. In fact, it is sufficient to observe that, 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.
(5.5)
It is possible then to define the computation of as
(5.6)
The computation of can be obtained in a similar way, even if it is more complicated than, because the probability in this case is calculated by conditioning to each possible value of dQ and for each measurement . The approach to compute this probability is the following :
(5.7)
where the distribution is obtained from by setting when d=d’ and 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 as:
(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 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 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;
do { % computation of the expected counts
for each kV
for each dQ
= 0 ;
for each
+ =
end
end
end
%computation of the current estimates
for each kV
for each dQ
end
end
l ++;
} while > threshold ;
;
}
double function compute_(k, z, ) {
if (k R)
return;
else
return
}
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, and.
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 and to the address 1 and 2.
It is vital to define the processing gap as the current time between the first and the second ICMP. The inference strategy requires a 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 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 . The original Ping program is replaced with the modified Ping program.