1 On the Tomography of Networks and Multicast刘四爷
Trees
Reuven Cohen,Danny Dolev,Shlomo Havlin,Tomer Kalisky,Osnat Mokryn,Yuval Shavitt
Abstract—In this paper we model the tomography of scale free networks by studying the structure of layers around an arbitrary network node.Wefind,both analyt-ically and empirically,that the distance distribution of all nodes from a specific network node consists of two regimes. Thefirst is characterized by rapid growth,and the cond decays exponentially.We also show analytically that the nodes degree distribution at each layer is a power law with an exponential cut-off.We obtain similar empirical results for the layers surrounding the root of multicast trees cut from such networks,as well as the Internet.
I.I NTRODUCTION
In recent years there is an extensive effort to model the topology of the Internet.While the exact nature of the Internet topology is in debate[5],it was found that many realistic networks poss a power law,or scale free degree distribution[13],[14],[18],[6],[10].Albert and Barab´a si[2],[1]suggested a dynamic graph generation model for such networks.One of their mainfindings was the lf similarity characteristi
c of such networks.In-terestingly,empiricalfindings on partial views obtained similar results,which may lead to the assumption that due to the lf similarity nature of the Internet structure, this characteristic would be expod through different cuts andfilters.
In this paper we study the tomography of scale free networks and multicast trees cut from them.We u the Molloy Reed graph generation method[19]in conjunc-tion with similar techniques to study the layer structure (tomography)of networks.Specifically,we study the number and degree distribution of nodes at a given (shortest path)distance from a chon network node. We show analytically that the distance distribution of all nodes from a specific network node consists of two regimes.Thefirst can be described as a very rapid growth,while the cond is found to decay exponentially. We also show that the node degree distribution at each layer obeys a power law with an exponential cut-off. We back our analytical derivations with simulations,and show that they match.
As noted by Lakhina et al.[17],it is a significant challenge to test and validate hypothes about the Internet topology,becau of lack of highly accurate maps.Our analyticalfindings suggest a simple local test for the validity of the power law model as an exact model of the Internet.Indeed ourfindings suggest that there is a good agreement of the empirical and analytical results.The slight difference we had can be attributed to bias in data collection and to cond order phenomena such as,degree c
orrelation,hierarchies,and geographical considerations.
We also study shortest path trees cut from scale free networks,as they may reprent the structure of multicast trees.We investigate their layer structure and distribution.We show that the structure of a multicast tree cut from a scale free network exhibits a layer behavior similar to the network it was cut from.We validate our analysis with simulations and real Internet data.We believe that enriching our understanding of the structure of multicast trees,can aid us in developing better multicast ,in the past we ud the statistics of high degree nodes to devi better algorithms for estimating the multicast group size[10].
The paper is organized as follows.Section II details previousfindings.In ction III we introduce the process ud for generating scale free graphs and their layers. Then,we analyze the resulting tomography of such networks,and back the results with simulations and real data in ction IV.In Section V we investigate the tomography of multicast trees cut from such networks, and back ourfindings with real Internet data.
II.B ACKGROUND
A.Graph Generation
Recent studies have shown that many real world networks,and,in particular,the Internet,are scale free networks.That is,their degree distribution follows a power law,,where is an appropriate normalization factor,and is the exponent of the power law.
Several techniques for generating such scale free graphs were introduced[2],[19].Molloy and Reed suggested an interesting construction method for scale free networks in[19].The construction was part of a
2
model describing an“exposure”process ud to evaluate the size of the largest component in a random scale free network.We term this model the MR model.The construction method is as follows.A graph with a given degree distribution is generated out of the probability space(enmble)of possible graph instances.For a given graph size,the degree quence is determined by randomly choosing a degree for each of the nodes from the degree distribution.Let us define as the t of chon nodes,as the t of unconnected outgoing links from the nodes in,and as the t of edges in the graph.Initially,is empty.Then,the links in are randomly matched,such that at the end of the process, is empty,and contains all the matched links, .Throughout this paper,we refer to the t of links in as open connections.
Note,that while in the BA model the graph degree distribution function emerges only at the end of the process,in the MR model the distribution is known a-priori,thus enabling us to u it in our analysis during the construction of the graph.
B.Distribution Cut-Off
Recent work[9],[7],has shown that the radius1,, of scale free graphs with is extremely small and scales as.The meaning of this is that even for very large networks,finite size effects must be taken into account,becau algorithms for traversing the graph will get to the network edge after a small number of steps.
Since the scale free distribution has no typical degree, its behavior is influenced by externally impod cutoffs, i.e.minimum and maximum values for the allowed degrees,.The fraction of sites having degrees above and below the threshold is assumed to be.The lower cutoff,,is usually chon to be of order,since it is natural to assume that in real world networks many nodes of interest have only one or two links.The upper cutoff,,can also be enforced externally(say, by the maximum number of links that can be physically connected to a router).However,in situations where no such cutoff is impod,we assume that the system has a natural cutoff.
1We define the radius of a graph,,as the average distance of all nodes in the graph from the node with the highest degree(if there is more than one we will arbitrarily choo one of them).The average hop distance or diameter of the graph,,is restricted to:
(1) Thus the average hop quence is bound from above and from below by the radius.
To estimate the natural cutoff of a network,we assume that the network consists of nodes,each of which has a degree randomly lected from the distribution .An estimate of the average value of the largest of the nodes can be obtained by looking for the smallest possible tail that contains a single node on the average[8]:
(2) Solving the integral yields,which is the approximate natural upper cutoff of a scale free network[8],[11],[20].
In the rest of this paper,in order to simplify the analysis prented,we will assume that this natural cutoff is impod on the distribution by the exponential factor
.
III.T OMOGRAPHY OF S CALE F REE N ETWORKS
In this ction we study the statistical behavior of layers surrounding the maximal connected node in the network.First,we describe the process of generating the network,and define our terminology.Then,we analyze the degree distribution at each layer surrounding the maximally connected node.
A.Model Description
We ba our construction on the Molloy-Reed model[19],also described in ction II.The construction process tries to gradually expo the network,following the method introduced in[9],[7],and is forcing a hierarchy on the Molloy-Reed model,thus enabling us to define layers in the graph.
We start by tting the number of nodes in the net-work,N.We then choo the nodes degrees according to the scale-free distribution function, where is the normalizing constant and is in the range,for some chon minimal degree and the natural cutoff of the distribution[8],[11].
At this stage each node in the network has a given number of outgoing links,which we term open con-nections,according to its chon degree.Using our definitions in II,the t of links in is empty at this point,while the t of outgoing open links in contains all unconnected outgoing links in the graph.
We proceed as follows:we start from the maximal degree node,which has a degree,and connect it ran-domly to available open connections,thus removing the open connections from(efigure1(a)).We have now expod thefirst layer(or shell)of nodes,indexed
3 as.We now continue tofill out the cond layer
in the same way:We connect all open connec-
tions emerging from nodes in randomly
chon open connections.The open connections may
be chon from nodes of layer No.(thus creating a
loop)or from other links in.We continue until all
open connections emerging from layer No.have been
connected,thusfilling layer(efigure1(b)).
Generally,to form layer from an arbitrary layer
天麻能治风湿吗
,we randomly connect all open connections emerging
from to either other open connections emerging from
or chon from the other links in(efigure1(c)).
Note,that when we have formed layer,layer has
no more open connections.The process continues until the t of open connections,,is empty.
B.Analysis
We proceed now to evaluate the probability for nodes with degree to reside outside thefirst layers,denoted by.
The number of open connections outside layer No., is given by:
(3)
Thus,we can define the probability that a detached node with degree will be connected to an open connection emerging from layer by
(4)
for large enough values of.
亚马逊河有多长
Thus,the probability that a node of degree k will be outside layer No.is:
(5) Thus we derive the exponential cutoff:
(8) and Therefore:
.
4
each layer have more than one incoming connection. An example for this ca is when so that most of the sites in the network have only one connection. Figure3shows results for with similar agreement. Note the exponential cutoff which becomes stronger with
怀孕是女儿的症状
.
It is important to note that the simulation results give the probability distribution for the giant percolati你不再属于我
on cluster,while the analytical reconstruction gives the probability distribution for the whole graph.This may explain the difference in the probability distributions for lower degrees:many low degree nodes are not connected to the giant percolation cluster and therefore the probability distribution derived from the simulation is smaller for low degrees.
Figure4and Figure5show the same analysis for a cut of the Internet at router level(Lucent mapping project[3],LC topology-e table I).The actual probability distribution is not a pure power law,rather it can be approximated by for small degrees and at the tail.Our analytical reconstruction of the layer statistics assumes,becau the tail of a power law distribution is the important factor in determining properties of the system.This method results in a good reconstruction for the number of nodes in each layer,and a qualitative reconstruction of the probability distribution in each layer.
In general,large degree nodes of the network mostly reside in the lower layers,while the layers further away from the source node are populated mostly by low degree nodes[10].This implies that the tail of the distribution affects the lower layers,while the distribution function for lower degrees affects the outer layers.Thus the deviations in the analytical reconstruction of the number of nodes per layer for the higher layers may be attributed to the deviation in the assumed distribution function for low degrees(that is:instead of).
Our model does not take into account the corre-lations in node degrees,which were obrved in the Internet[21],and hierarchical structures[24].This may also explain the deviation of our measurements from the model predictions.
泰迪多少钱
V.E MPIRICAL F INDINGS ON THE T OMOGRAPHY OF
M ULTICAST T REES
In this ction,we detail some of ourfindings on the structure and characteristics of the depth rings around the root node of shortest path trees.All of ourfindings were also validated on real Internet data.A.Topology and Tree Generation
Our method for producing trees is the following.First, we generate power law topologies bad on the Barab´a si-Albert model[1].The model specifies4parameters:, ,and4.Where is the initial number of detached nodes,and is the initial connectivity of a node.When a link is added,one of its end points is chon randomly, and the other with probability that is proportional to the nodes degree.This reflects the fact that new links often attach to popular(high degree)nodes.The growth model is the following:with probability,new links are added to the topology.With probability,links are rewired,and with probability a new node with links is added.Note that,and determine the average degree of the n
odes.We created a vast range of topologies,but concentrated on veral parameter combinations that can be roughly described as very spar(VS),Internet like spar(IS)and less spar (LS).Table I summarizes the main characteristics of the topologies ud in this paper.
From the underlying topologies,we create the trees in the following manner.For each predetermined size of client population we choo a root node and a t of clients.Using Dijkstra’s algorithm we build the shortest path tree from the root to the clients.To create a t of trees that realistically remble Internet trees,we defined four basic tree types.The types are bad on the rank of the root node and the clients nodes.The rank of a node is its location in a list of descending degree order, in which the lowest rank,one,corresponds to the node with the highest degree in the graph.For the ca of a tree rooted at a big ISP site,we choo a root node with a low rank,thus ensuring the root is a high degree node with respect to the underlying topology.Then,we either choo the clients as high ranked nodes,or at random, as a control group.Note,that due to the characteristic of the power law distribution,a random lection of a rank has a high probability of choosing a low degree node.The next two tree types have a high ranked root, which corresponds to a multicast ssion from an edge router.Again,the two types differ by the clients degree distribution,which is either low,or picked at random. The tree client population is chon at the range for the10000node generated topology,
for the100000node generated topology,and
for the trees cut from real Internet data. For each client population size,14realizations were generated for each of the four tree types.All of our results are averaged over the realizations.The variance of the results was always negligible.
4The notations in[1]are,,and.
5 Name Parameters Avg.Node degree
generated10000
generated10000
generated10000
generated50000;100000
real data Internet
买红酒real data Internet
骆驼祥子感想6
a network with nodes,,and .Symbols reprent simulation results while black lines are a numerical solution for the derived recursive relations.
Fig.4.Number of nodes at each layer for a router level cut of
the Internet with
nodes (LC topology).Analytical reconstruction for is done with ,and .
were shown to hold for all trees cut from all generated topologies,even for trees as small as 200nodes.
In this work we further investigated the tomography of the trees,and looked at the degree distribution of nodes at different depth rings around the ,tree layers.It was rather interesting to obrve that any layer with sufficient number of nodes to create a valid statistical sample obeyed a degree-frequency relationship which was similar to a power law,although with different slopes.We suspect that this is due to the exponential
for a router level cut of the Internet with nodes (LC topology).Qualitative analytical reconstruction is done with ,
and
.phenomenon discusd in the previous ctions.6shows this for the third layer around the root nodes at distance three from the root)of a 300tree cut from a big IS topology (100000nodes).root was chon with a high degree,and the clients a low degree.Although the number of nodes is small,we e a very good fit with the power law.7shows an excellent fit to the power law for the layer around the root of a 10000client tree,cut from same topology.This phenomenon is stable regardless tree type,and the client population size.Note that range of the power laws en in figures 6and 7is than one order of magnitude.This could indicate a to exponential behavior.
understand the exact relationship of the degree-at different layers,we plotted the distribution of each degree at different layers.Cheswick at al.[6]found a gamma law for the number of nodes at a certain distance from a point in the Internet.Our results show that the distribution of nodes of a certain degree at a certain distance (layer)from the root ems clo to a gamma distribution,although we did not determine its exact nature.Figure 8shows the distribution of the distance of two degree nodes,and Figure 9the distribution of the distance of high degree ,nodes with a degree six and higher.In both figures the root is a low degree node,and the tree has 1000low degree clients.As can be en,the high degree nodes tend to reside much clor to the root than the low degree nodes,and in adjacent layers.In this example,most of
