3.3 Mobile Agent-based Topology Discovery
3.4.2 Life span of a mobile agent
agent, the average life span of a mobile agent can be inferred as follows.
E[TL] = E[
XN k=1
tk]
= E[E[
XN k=1
tk|N]]
= X∞ n=1
P r(N =n)E[
XN k=1
tk|N =n]
= X∞ n=1
P r(N =n)E[
Xn k=1
tk]
= X∞ n=1
nP r(N =n)E[tk]
= E[N]E[tk]. (3.10)
2. Analysis on a given network
For a given network that has r0 receiver nodes, l0 links, and n0 nodes in total including the management node, the average number of mobile agents generated for topology discovery can be estimated based on the above result. If there isn’t any cycle in the network, the number of linksl0 is equal ton0−1. Otherwise,l0 cannot be decided simply by the total number of nodes.
From the network in Figure 3.3 we know that the first mobile agent spawned in the man-agement station generates three mobile agents at the start. They are dispatched into each direction of the network. When the mobile agents pass through branches, new mobile agents are generated so that each downstream link has one agent to continue searching. All the links and nodes will be marked correctly after they have been visited as Figure 3.3 shows. In this network, mobile agents terminate themselves in two cases. One is when they arrive at the receivers, the other is when they visit a link that has already been marked “N”, indicating that another agent has already visited the link.
The average life span of all mobile agents spawned for the task of discovering topology of a network can be calculated according to Equation (3.10). Because automatic topology discovery by mobile agents uses flooding algorithm, each link is visited only by one mobile agent.
Therefore, the average number of hops a mobile agent made to finish the topology discovery task is the total number of hops H made by all discovery agents divided by the total number of generated discovery agents M in the network. The number of links in the network is the total number of hops made by all discovery agents, i.e., l0 =H. The total number of discovery agents generated in the network is determined by the number of receivers and the number of cycles in the network. To each receiver, there must be one discovery agent dispatched from
Figure 3.3: Network topology discovered by flooding algorithm using mobile agents the root. Each cycle connecting the root to either one “end-node” (when the cycle contains an even number of links) or two “end-nodes” (when the cycle contains an odd number of nodes), where an “end-node” has an “upstream” link and an “N” link on the cycle which are marked by two discovery agents dispatched to the node. While one agent will continue search on a downstream link, the other agent will be terminated because the end-node is already marked
“visited” by the first agent. Therefore, each cycle will add two additional discovery agents if the cycle contains an odd number of links, and one discovery agent if it contains an even number of links, all terminated at “end-nodes”, into the network. Assuming that both cases occur at an equal probability, we have that the total number of discovery agents is:
M =r0+3
2C, (3.11)
whereC is the number of cycles in the networks.
Thus, the average number of hops a mobile agent made to finish the topology discovery task is:
E(N) = H
M = l0
r0+32C. (3.12)
Then, according to Equation (3.10) and (3.12), the average life span of a mobile agent in the network shown in Figure 3.3 is,
E(TL) =E(N)·E(tk) .
= l0·E(TC)
r0+32C , (3.13)
whereE(tk) can be approximated to E(TC) becausetk,1≤k≤N−1, is the cycle time of the mobile agent excepttN doesn’t include the travel time.
Thus, we can estimate the total time TT D required to finish topology discovery. An upper bound and a lower bound are given by the following inequality. Consequently, while the man-agement station initiates the topology discovery task, it can estimate when the task will be finished so that it can start to construct the topology based on the collected information.
E[TL]≤TT D≤E[M]·E[TL]. (3.14) The lower bound is given because the time of topology discovery must be greater than the expected life span of a mobile agent. However, the time required by the topology discovery task is less than the total life span of all the mobile agents.
3. Analysis on the life span distribution function
In order to describe the variable life span, we assume that the life span pdf isl(t), and denote the Laplace transform ofl(t) by L(s).
L(s) = E[e−sTL]
= X∞ n=1
E[e−sTL|N =n]P r(N =n)
= X∞ n=1
E[
YN k=1
e−stk|N =n]P r(N =n)
= X∞ n=1
(C(s))n−1D(s)P r(N =n), (3.15)
where, C(s) =E[e−stk], 1 ≤k≤ N−1 and D(s) =E[e−stN] becausetN is the dwell time of the mobile agent when it visits the N-th host.
In the task of Internet topology discovery(ITD), a mobile agent encounters either a leaf node or a non-leaf node by the algorithms proposed in Section 3.3.1. Suppose a mobile agent encounters a leaf node with probability pI, and a non-leaf node with probability 1−pI, in a hop. As we have said, the mobile agent is terminated at leaf nodes. Therefore, the probability that a mobile agent is terminated after the n-th hop is,
P rI[N =n] = (1−pI)n−1pI. (3.16) In the task of multicast topology discovery(MTD), the nodes a mobile agent visits are either internal un-visited routers or receivers because there isn’t cycle in multicast network. Assume that pM is the probability of a mobile agent encountering a leaf node in each hop. So the probability of a mobile agent that is terminated after the n-th host-visit in the MTD case is,
P rM[N =n] = (1−pM)n−1pM. (3.17)
Then L(s) can be obtained by replacingP rin Equation (3.15) with P rI in Equation (3.16) for ITD case and withP rM in Equation (3.17) for the MTD case respectively.
We can determine the pdf of life span distribution by inverse Laplace transform of L(s).
The mean and variance of the life span of a mobile agent are given as follows.
Lemma 10 The mean and variance of TL can be calculated by the following equations.
E[TL] =−dL(s)
s |s=0, (3.18)
D[TL] = ∂2L(s)
∂s2 |s=0−[dL(s)
ds |s=0]2. (3.19)
Proof of Lemma 10 is identical to the proof of Lemma 9.