4 0 0 Internet’s Critical Path Horizon 2 n Sergi Valverde1 and Ricard V. Sol´e1,2 a J 1 ICREA-Complex Systems Lab, Universitat Pompeu Fabra, DrAiguader 80, 08003 Barcelona, Spain 5 2 SantaFe Institute,1399 HydePark Road, NewMexico 87501, USA 1 ] February 2, 2008 n n Abstract. Internet is known to display a highly heterogeneous structure and complex fluctuations in its - s traffic dynamics. Congestion seems to be an inevitable result of user’s behavior coupled to the network i dynamicsandit effectsshould beminimized bychoosingappropriateroutingstrategies. Butwhat arethe d requirementsofroutingdepthinordertooptimizethetrafficflow?Inthispaperweanalysethebehaviorof . t Internettraffic with a topologically realistic spatial structureasdescribed in apreviousstudy (S-H.Yook a m etal.,Proc.NatlAcad.Sci.USA,99(2002)13382).Themodelinvolvesself-regulationofpacketgeneration and different levels of routing depth. It is shown that it reproduces the relevant key, statistical features - d of Internet’s traffic. Moreover, we also report theexistence of a critical path horizon defining a transition n from low-efficient traffic to highly efficient flow. This transition is actually a direct consequence of the o web’s small world architectureexploited bytherouting algorithm. Onceroutingtables reach thenetwork c diameter, the traffic experiences a sudden transition from a low-efficient to a highly-efficient behavior. It [ is conjectured that routingpolicies might havespontaneously reached such acompromise ina distributed manner. Internet would thusbeoperating close to such critical path horizon. 1 v PACS. 89.75.-k ComplexSystems–05.70.Ln Nonequilibriumandirreversiblethermodynamics–87.23.Ge 0 7 Dynamics of social Systems 2 1 0 1 Introduction 4 0 The efficient performance of any communication network / t is jeopardized by congestion problems, which often show a up in unpredictable ways. This seems the case, for exam- m ple, of so called Internet storms [2]. Such problems were - early identified in different types of engineered networks. d n Norbert Wiener for example mentions that “a switching o service involving many stages and designed for a certain c level of failure shows no obvious signs of failure until the : traffic comes up to the edge of the critical point, when it v i goes completely into pieces, and we have a catastrophic X traffic jam” [3]. These observations allow to formulate a r number of key questions concerning communication nets, a such as: How do critical traffic levels are reached? What is the nature of these thresholds? How appropriate rout- ing algorithms modify this behavior? Are there optimal routing strategies? Fig. 1. Small Internet-like network (see text for generation Modeling Internet dynamics has been an active area methoddescription).Theparametershavebeensettothepo- overthelastdecade.Theapproachesincludedetailedsim- sitioncorrespondingtoInternetinthe(D ,α,σ)-phasespace: f ulations [4], simple statistical models and verbal models M= 250, <k>=4, D =1.5, α=1, σ=1. f [5].Inthiscontext,in[6]weinvestigatedtheexistenceofa jamming phase transition between the free phase and the congestedphaseina modelofnetworktrafficoverregular meshes. This phase transition depends on traffic density. [7]. At the critical regime, the distribution of congestion It was conjectured that large-scale network traffic self- duration lengths scales as a power-law [9][7]. organizes near the critical point of the transition, which Suchaself-organizedscenarioisreinforcedbyarecent is linked to high network efficiency and unpredictability study suggesting that Internet fluctuations are a conse- 2 Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon quenceoftheinternaldynamicsofthesystem[10].Against <N > previousclaims,there is mounting empiricalsupportthat λ ≈ (2) C networktrafficheterogeneityisaconsequenceofcollective <T > dynamics and not because of the high variability injected where the latency is defined as the time comprised from by external sources. the creationofapacketuntilits deliveringatthe destina- InthispaperwewillshowthatInternetisabletoroute tion host. The mean latency < T > is averaged over all efficiently its inner flow of packets because a special com- successfullyreleasedpackets.Following[7]wewillindicate bination of local routing rules and a particular network by ξ the number of local congested neighbors: architecture. As we will see, Internet routing reaches an optimal, low-cost traffic flow as a result of a trade-off be- ξ = θ[n(i,t)] (3) tween random and deterministic routing schemes. k∈XC(i) where θ[x] = 1 for x > 0 and zero otherwise. The packet 2 Modelling Internet’s traffic injection rate for host i is updated as follows: Following previous approaches [6][7] let us consider net- min{1,λi(t)+µ} ξ =0 work defined on a graph Ω with M nodes (figure 1). The λi(t+1)= λi(t) 0<ξ <ki (4) numberoflinks connectingagivennode withanother(ir-  0 ξ =ki respective of their characteristics) will be indicated as k . i Thesubsetofclosestnodesofs ∈ΩisC .Onlyafraction where µ is theso-called driving parameter. The sec- i i of fixed ρ < (0,1] nodes is selected as source and desti- ond rule allows a particular host to stabilize around a nationtrafficendpoints (hosts).Hostlocationsarechosen givenrate. Traffic rate increases conservativelyand drops randomly. The other (1−ρ)M nodes can only store and down to zero when all neighboring nodes are congested. forward incoming messages (routers). Thereadermustbeawarethattheaboverulesarenotin- Both host and routers can route only one packet at a tendedtobeadetailedmodelofrealtrafficsources.Traffic time(theroutingpolicyisdescribedbelow).Eachnodes sources can not be described with an universal distribu- i isprovidedwithafinitequeueofpacketswaitingforcom- tion probability. Moreover, it seems that a rich variety of munication resources (free links). Queues are not allowed distributions(exponential,bi-modalorlog-normal)apply. to store more than H packets simultaneously. New pack- As we will see later in the paper, it is unlikely that the ets arriving at an already saturated queue will be simply variability of traffic sources will be the cause of the scal- removedfromthesystem.Thisprovidesaverysimpledis- ingdetectedinInternettraffic.Moreover,this modeldoes sipativemechanismusefulforrecoveringfromheavytraffic not introduce any explicit correlations between sources congestion. If n(s ,t) is the number of packets at s , the (i.e.: like in active conversation between two hosts) so i i total number of packets in the system will be the dynamics can not be the by-product of pre-defined source correlations. Because the system is poised to crit- N(t)= n(s ,t) (1) icality (the so-called fluid packet flow regime) the global i dynamics emerge from the collective behavior of its com- sXi∈Ω ponents.Ultimatesourcedetailsareirrelevantinthiscon- which is the key quantity which has to be analysed here. text. Moreover, although TCP is more realistic than our Any microscopic host behavior compatible with the simplified local rules (also much more complex) our con- fluid scenario must ensure a controlled injection of pack- jectureisthatthelarge-scaledynamicswillnotbegreatly etsinordertonotfloodingthenetwork(andthusentering changed by the local behavior of hosts within this fluid the congested state). Note that in a fluid traffic regime it flow regime. This idea has been partly answered in a re- isunlikelythatpacketswillbealiveforanarbitrarilylong cent work [8] in which it has been shown that IP level time.Afluidityrequirementwillnecessarilyimposeahard traffic (packet dynamics) does not depend to any signif- constraint on the maximum time spent by a packet trav- icant extent on the TCP arrival process (host behavior), elling across the network. The simplest way of ensuring supporting our view that traffic dynamics is not a conse- fluidpacketflowistostopthesourcesemittingnewpack- quence of detailed source (host) behavior. ets whendetecting localcongestion,thatis,whenthereis Forahomogeneousnetworkwithaveragedegree<k > no empty spaceinthe sourceneighborhoodCi to fill with (andfinite<k2 >)itcanbe shown,following[7]thatthe new packets. If no self-regulation is present, it has been time evolution of packet density Γ(t) = N(t)/M in the shown that there is a sudden and sharp jamming transi- limit of H →∞ is defined by the mean field equation: tionfromthefreetothecongestedstatedependingonthe mean (system) packet generation rate hλi. At the critical dΓ <k > =ρλ− Γ(1−Γ) (5) point between the two phases the system displays opti- dt D mum(global)performance.Ifself-regulationis allowed,it can be shown [7] that simple traffic source rules are able whereD indicates the networkdiameter(alsothe average toself-organizethetrafficnetworkaroundadefinitemean transienttime,assumingpacketsjump fromnode to node ratehλi,whichscalesasthe quotientbetweentheaverage with the same average time scale). It is not difficult to system load <N > and the averagedpacket latency hTi: showthatthe equilibriumpoints ofthe previousequation Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon 3 are given by Γ± = [1 ±(1 −4ρλD/ < k >)1/2]/2. For sj λ > λc ≡< k > /4Dρ, the fixed points vanish and no δm(s ) i finitedensityexists.Inthis“congestedphase”thedensity of packets grows without bounds. For λ < λ , a finite c stable density 1 4ρλD 1/2 m Γ− = 1− 1− (6) si 2 <k> " (cid:18) (cid:19) # is observable (the other fixed point Γ is unstable). For + the particular case ρ=1 analysed by Fuk´s and Lawnizak [12], we recover their critical point λ = 2/L for dynam- c ics taking place on a square lattice, i. e. D = L/2. If a feedback exists between λ and γ, some finite equilibrium Fig. 2. Network dynamics and routing: it involves a given densityΓ∗willbeachievedinthepreviousmodelandthus depthofroutingm(apathhorizon).Apackettravelingfromsj no divergence will be allowed to occur. In this case, the tosiwithintheδm(si)domain(ofdepthm)isdeterministically mean field model indicates that a scaling relation will be routed along the shortest path (d(j,i) ≤ m). The packet tra- observed, i. e. verseshosts(squares)androuters(circles)indistinctly.Packets λ∼ρ−1 (7) travelingoutsidethem-domain(i.e.ford(j,i)>m)havemore than one path choice and perform random walks. As soon as between the (self-organized) packet release rate and the the packet enters into the m-domain, the packet is determin- density of hosts (which is here the only relevant external istically routed along the shortest path. Here we would have parameter).Suchascalingrelationwasshowntooccurin m=2. the previous model. The previous mean field calculation was done by as- sumingthatafixedλisbeignused.Thepreviousrulesac- bothofthemrealandnegative:thepointattractorisglob- tuallyintroduceself-regulationofinjectionratesbytraffic. allystable.Numericalsimulationsofthe modelonaPois- In other words,if traffic levelN defines an order parame- sonian graph (where the previous approximation would ter,itwillinteractwithacontrolparameter(λ), reducing held) agree with these predicted values. Topological fea- it when N is large and incresing it when low. The feed- tures are included only as averagedquantities, here mean back between these two key quantities results in a state degree < k > and diameter D. However, our interest is dominatedbyfluid,butfluctuatingtrafficwithmanychar- to explore the traffic dynamics on a realistic network ar- acteristicsincommonwith observedInternet’s dynamical chitecture, in order to provide the closest modeling ap- patterns. proach under the previous rules. It has been shown that Inordertoexplictlyconsiderthefeedbackbetweenor- the Internet does not display the homogeneous architec- der and control parameters, we can consider a new mean ture assumed by the Poissonian graphs [13]. In the next field approximation based on the previous local rules. It sectionthenetwork’stopologyusedinouranalysisispre- canbeshown,asumingfiniteH,thatthenewsetofequa- sented.Togetherwith an explicitdefinition of the routing tions is now: algorithm, they will complete our model’s description. dΓ γ <k > =ρλ 1− − Γ (8) dt H D (cid:16) (cid:17) 3 Network topology dλ Γ =µ(1−λ)− (9) dt <k > In previous analyses [6] [7] the topology of the graph was for low density levels (i. e. Γ ≪ H, consistently with a chosentobealattice.Althoughthismightseemalimited fluidtraffic)thesinglefixedpoint(obtainedfromdΓ/dt= topological arrangement, it has been successfully tested dλ/dt=0) is on real hardware and the presence of a phase transition fullyconfirmed[14].Moreover,meshconnectedtopologies 1 Γ∗ (Γ∗,λ∗)= ,1− (10) maybethemostefficientsolutionatthelimitofverylarge <k> + 1 <k >M! parallel computer architectures [15][16]. ρD µ<k> Regular lattices fail to describe Internet topology.Re- the Jacobi matrix L for the previous set of equations is markably, Internet displays a scale-free architecture [13]. given by Theoriginsandcausesofthistopologyhavebeenthesub- L= −<Dk> ρ (11) ject of most discussion and controversy.It has been show −1 −µ thatmostexistingInternetgeneratorsfallinaverydiffer- (cid:18) <k> (cid:19) entregionofthephasespacewhererealInternetislocated The associated eigenvalues are [1]. This phase space is defined by (D ,σ,α), where every f 2 parameter defines a major force shaping a different as- 1 <k > <k > 4ρ Λ± = − +µ ± +µ − pect of the large-scale Internet topology. Note that this 2 (cid:18) D (cid:19) s(cid:18) D (cid:19) <k > modeldoesnotdefinealldetailedcorrelationsobservedin   4 Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon Internet and/or the precise functional form of Internet’s {paths} path length and degree distribution (i.e.: the exact expo- RW nent of the scale-free distribution). This is a minimal set of universal parameters that any realistic Internet model must satisfy and it is a very good approximation to the large-scale topology. The spatial distribution of Internet nodes is not ran- dom. It has been noticed a strong correlation between SP fractaldistributionofcitiesandInternetnodes.The mea- suredfractaldimensionisD =1.5.Whengeneratingthe f Internet-likenetwork,thepositionofnodesisobtainedby samplingaRayleigh-L´evydustofthesamefractaldimen- sion. The likelihood of placing a link between two nodes m>D (Ω ) m=0 si and sj depends both onthe (euclidean) link length wij max 0<m<D (Ω ) max and linear preferential attachment: Fig. 3. Hierarchy of path sets defined by the routing policy. kα j Every routing scheme explores a fraction of network paths (a Π(k ,d )≈ j ij wσ subset of the entire path set P(Ω)). Pure random walk strat- ij egy (m=0) visits all available paths, even shortest paths. In Note that longer links cost more and thus will be se- fact,randomwalktravelmorefrequentlyalongthoseshortests lected with less probability. Traditional topology gener- paths. The more restrictive set is associated to pure shortest atorsbasedonWaxmanmodel[17]wronglyassumeexpo- path routing (m≥[hdi]), which chooses a small fraction of all nential decay instead of linear cost decay. On the other possible routes on thenetwork. side, there is empirical evidence that highly connected nodes will be linked with higher probability. Increasing α will favor linking to nodes with higher degree, while a but no more. No information will be stored about nodes higher σ will penalize longer links. From real measure- outside the node domain. This idea is indicated in figure ments[1],ithasbeenidentifiedthepositionofInternetat 2, where a given target node s is shown at the center D = 1.5, σ = 1 and α = 1. Here, all numerical simula- i f of its m-sphere. When a foreign node s ∈ Ω−Γ(m)(s ) tions have been performedusing this topologicalarrange- j i send a packet towards s , while moving in the outside of ment (figure 1). i thesphereitperformsasarandomwalk.Oncethe packet hits the boundary of the sphere, ∂Γ(m)(s ), it is routed i along the shortest path [19]. 4 Path horizon and routing tables An important ingredient when modeling network dynam- 5 Efficiency and network’s exploration ics is to describe the paths followed by packets towards their destinations, that is, the routing policy. By prop- The depth of routing parameter m induces a hierarchy erly defining this routing algorithm, we will complete our of path subsets over the entire set of available network model’s definition. paths(seefigure3).Therandomm=0anddeterministic Realroutingprotocolsdonotdrivepacketsatrandom. m = M routing represent the most general and restric- Instead,they try to route packetsalongthe mostefficient tive subsets, respectively. Increasing m will progressively routes (i.e: minimize distance or latency). At the same reducethe randomnessatroutingdecisions.Here,wefind time, it is unrealistic to assume that all packets follow a nested collection of subsets corresponding to the inter- optimal paths because the large amount of global infor- mediate situations 0 < m < M. The relative size of each mation replicated at every single node. Clearly,the paths subset can be approximated by measuring the fraction of tracedbypacketsinrealnetworksareproperlycharacter- nodes F visited by packets: ized as a trade-off between random diffusion and optimal routing. This is reflected in the real Internet by its two- M levelroutingorganization.Nodes aregroupedin so-called 1 F = θ[A ] (12) i AutonomousSystems(AS)anddifferentroutingrulesap- M i=1 ply at each level. Intra-AS routing is based on shortest X path routing but inter-AS routing does not cleary follow where A is the probability of visiting the node s . This i i any minimization criteria. term depends both on the network dynamics and the ge- Asimplewaytoexplorethe cost/efficiencytrade-offis ometrical situation of the node within the network. Con- byintroducingaparameterdefiningthevisibilityscopeof siderable effort has been devoted to characterize the like- the node (depth of routing parameter m or node domain lihoodofvisiting anode ina purelystatic fashion.Inthis diameter),that is,asphere Γ(m)(s ) ofradius m centered context, two relevant centrality (or ’load’ [20][21]) mea- i at every node s ∈ Ω (figure 1). We allow every node to sures are Random Walk Centrality [22] and Betweenness i known every other node at a distance of m hops or less Centrality[23]whichcertainlyrepresentthetwoextremes Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon 5 1.0 75 a b 1.0 0.8 60 y des0.9 <T>45 Efficienc00..46 no 30 0.2 d e 15 0.0 sit0.8 0 5 m 10 15 0 5 m 10 15 vi 150 of c d n 00..2255 135 o0.7 Fracti λ00..2200 Load120 00..1155 0.6 105 00..1100 90 0.00 5.00 10.00 15.00 0 5 10 15 m m 0.5 0 2 4 6 8 10 Path horizon m Fig. 5. Exploring the network traffic dependency on depth of routing parameter (m). The lines connect the points for il- Fig. 4. The fraction of visited nodes depends on the amount lustratingpurposes only.(A)Mean latency isconsiderably re- oforderdefinedbythedepthofroutingparameter.Determin- duced when enough system information is given to individual ism sharply constraints the routing paths. Every point was nodes. Most packets are forwarded along the minimum num- obtainedaveragingoveranensembleoffourdifferentnetworks ber of hops. (B) Global throughput is optimal at the criti- and every single network was simulated in five different host cal point when path horizon is about the network diameter. configurations. Network parameters: M = 512, < k >= 4, (C) Mean packet rate also drops down at intermediate value. ρ = 0.1, µ = 0.01, H = 10, D = 1.5, σ = 1, α = 1 and f (D) Mean workload also experiences sudden transition from T =7×105 steps. heavy to light load. Network parameters: M=250, < k >= 4, D = 1.5, σ = 1, α = 1. Simulation parameters: ρ = 0.1, f µ = 0.01, H = 10, T = 105 steps. The shape of these plots does not depend on network size, that is, the optimal point is always found at m=[hdi]. of our hierarchy of path subsets. Anyway, the correlation ofthesemeasurementswithdynamiccentralityA isweak, i to say the least. 6 Average stretch In figure 4 the numerically measured F(m) for a fi- nite range of m values is shown. This fraction equals 1 The average stretch s measures the efficiency of routing for random routing 0 ≤ m < [hdi], where hdi is the av- bycomparingthe number ofhopshtraversedbya packet eraged shortest path length and [x] denotes the integer to the shortest path distance d between source and desti- part of x. Random routing does not discard any network nation: node.Asharptransitiontakesplacefromthispoint[hdi]< m ≤ M and a large fraction of network nodes (about 45 h s= percent) are never visited by deterministic routing. This d severly restricts the diversity of routes and yields a load- insensitive system [24]. The system requires a certain de- Compactroutingschemesminimizetheaveragestretch gree of noise in order to avoid sending packets through whilemaintainingthesizeofroutingtablessmall[25].Re- already collapsed nodes while it is enabled to choose less ducing the average strech will progressively raise up the optimal but free routes. Note that depth of routing pa- memory requirements at each router. Assuming Thorup- rameter m defines an order parameter because quantifies Zwick(TZ)compactroutingscheme[26],theaveragestretch thedegreeoforderexistinginthesystem.Theexistenceof canbeexpressedasafunctionofthedistancedistribution anorderparameterconfirmsthecriticalnatureofInternet and the graph size M only: hsi = f(hdi,σd) [27]. This traffic. TZ scheme ensures a nearly optimal lower memory upper bound for hsi=3 in generic networks. For scale-free net- Numerical simulations have shown that flow is max- works, TZ achieves lower bounds. In particular, for the imized at the order-disorder transition point m = [hdi]. Internet interdomain graph (Autonomous Systems) with This can be observed in network throughput reaching a degree distribution exponent γ ≈ 2.1 and M = 104, the maximum at this point (see figure 5). Throughput is de- TZ averagestretchhsi≈1.14[27]. Also, the averagenum- finedbythequotientofthenumberofsuccessfullyreleased ber ofentriesinthe routingtables is approximately52.It packets and the sum of all packets generated during the turnsoutthat hsi(hdi,σ )surface hasunique minimums. d simulation. In the next section, we will show that several Strikingly, the points corresponding to Internet distance real statistics can be reproduced by the system dynamics distributionareveryclosetothem[27].Thissuggeststhat poised to criticality. Internet topology is shaped by some hidden optimization 6 Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon 15 110022 110022 A flow in flow out r o10 ct a h f 110011 ct 110011 e σ σ r 5 St 0.5 0.5 0 110000 0 2 4 6 8 110000 1 e B 1100--11 110000 110011 110022 110033 1100--11 110000 110011 110022 110033 Siz 0.8 Mean flow Mean flow s/ or Fig. 7. Therelationship betweenfluctuationsandtheaverage hb 0.6 incoming node flux (a similar distribution holds for average g outgoingrouterflux).Theplot showsthatbothquantitiesare ei N 0.4 related by a power law of exponent 1/2, which is consistent # n withthemeasurementsfromInternetrouters.Networkparam- ea 0.2 eters: M=500, <k >=4, Df =1.5, σ =1, α=1. Simulation M parameters:ρ=0.1,µ=0.01, H=10,T=10000 steps.Mea- surementwindow=200.Thedistributionswereobtainedfrom 0 0 2 4 6 8 anstatisticalensembleof10networks,everynetworksimulated Path horizon m 5 times with hosts located at 5 different configurations. Fig. 6. (A) Average stretch (B) Average fraction of nodes inside m-domain is an estimation of the amount of informa- tion required by each node. Here open circles correspond to tweenthemeanfluxandthesizeoffluctuationsaroundthe the Internet’s nodel. For comparison, the simulation has been average [10]. Previous explanations of ocurrence of self- repeated in a poissonian network of same size and mean de- similarity in traffic networks are based on the superposi- gree (filled circles). Network parameters: M =500, <k>=4, tion of many and high-variable (infinite variance) sources D = 1.5, σ = 1, α = 1. Simulation parameters: ρ = 0.1, f [11]. This point of view discards the effects of the sys- µ=0.01,H =10,T =5×104timesteps.Measurementwindow tem’s collective dynamics and considers that Internet is =200. Thedistributionswereobtainedfrom anstatistical en- an externally driven system. Real data shows that Inter- sembleofthreenetworks,everynetworksimulatedthreetimes netdynamics cannotbe simply reducedto the behaviour with hosts located at different configurations. of traffic sources. Let us define the incoming (outgoing) flux f as the i amountofpacketsreceived(forwarded)atrouters during i criteria.Anyway,TZ scheme is not a realistic Internet in- agivenandfixedperiodoftime.Foreveryrouter,compare terdomain routing scheme because assumes that global the average flux hf i with the dispersion σ around the i i topologyviewisavailable.We havenumericallymeasured mean. It has been noticed that for several real systems theaveragestretchandtheaveragefractionofneighbours the following scaling relation holds: at distance m for our routing scheme (see figure 6). Note that the critical path horizon m = [hdi] is very close to σ ≈hfiα the minimum average stretch. where α is an exponent which can take the values of 1/2 and 1 [10]. This suggests that real systems can be 7 Network fluctuations and performance classified in two main classes depending on the value of this exponent. The relevant exponent in this context is Inorderto testthe goodnessofthemodelpresentedhere, α = 1/2, which has been observed in daily traffic mea- it is interesting to compare some real Internet statistics surements at 374 geographically distinct Internet routers with their respective model measurements. In particular, [10]. Systems exhibiting the 1/2 exponent are representa- those measurementswillbe collectedfor the model atthe tive of endogeneous dynamics, that is, determined by the critical path horizon, that is, when m=[hdi]. system’s internal collective fluctuations. Moreover, mea- When understanding the competition between a net- surementsonourmodelreproducethesameexponent(see work’s internal collective dynamics (i.e: Internet traffic) figure 7). andexternalenvironmentalchanges(i.e:trafficsourcesor A measure of Internet end-to-end performance is the host behaviour), it is useful to study the relationship be- normalizedlatency time τ [28]definedasthe quotientbe- Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon 7 tweenlatencytimeL(measuredasRound-Trip-Time)and 1100--22 geographicaldistance w: L τ = 1100--33 w -2.5 There are several factors governing τ. First, propa- ) gation rate is finite. There is a minimum delay because (t av1100--44 P packets can not move faster than speed of light. Second, the number of nodes traversed departs from the mini- mumfoundalongthegeodesicpathfromnodetodestina- H=10 1100--55 tion. And third, packets spent some time at every inter- mmediate node because queueing delays. Define τmin = H=5 L /w as the normalized latency without taking into min acount queue delays and τav = Lav/w as the normalized 1100--66 10-1 110000 101 latency while considering all factors affecting packet la- tav tency. Theirprobabilitydistributionshavebeenmeasuredfrom Fig. 8. Normalized latency τav distributions at the critical point m = [hdi] follows power law of exponent ∼ −2.45 and two years of PingER [29] data and follow power-law scal- fits very well the real measurements (see text). Here, we plot ing with stable exponents of about -3.0 for τ and -2.5 min thedistributions for H =5(shaded line) andH =10 (contin- for τ [28]. Numerical simulations on the model poised av uous line) showing that the long tail does not depend on the to criticality reproduced the power-law P(τ ) probabil- av maximum queue size. Any deviation from m = hdi results in itydistribution.Theexponentofthedistributionisabout an exponential distribution, deviating from real observations. -2.45, which is very close to real observations (see figure Network parameters: M =1000, <k >=4, D =1.5, σ =1, f 8). The previous results seems to be quite robust and in- α = 1. Simulation parameters: ρ = 0.1, µ = 0.01, H = 5,10 dependent of most model parameters changes. An inter- andT =5×105steps.Thedistributionswereobtainedfroman esting thing to note is that current model cannot repro- statisticalensembleof10differentnetworksandeverynetwork duce the existing correlation between τmin and τav and was simulated fivetimes with different host arragements. geographicaldistancew reportedbypreviousstudies[28]. The reason might be that propagation rate is (unrealis- tically) assumed to be infinite in the model. It might be thatthisfactorhaslittleinfluenceinshapingtheτ prob- provide better response. This is reflected in the optimal av ability distribution. Moreover,it is worthnoting that any andloweraveragestretchobservedinrealInternet,which deviation of the order parameter from the critical regime is close to global minimum [26]. This suggest hat some resulted in an exponential distribution for τ , reinforc- hidden optimization is at work. Clearly, an unresponsive av ing the view of an optimally efficient and self-organized system will be no good. How a distributed collection of Internet. designers were able to define this globally efficient infras- tructure is a question that deserves attention. 8 Discussion This paperis dedicated tothememory of PerBak. This work wassupportedbyagrantBFM2001-2154 andbytheSantaFe In this paper we have shown that a simple model of traf- Institute. ficdynamicsincorporatingtheappropriateInternet’snet- work topology is able to recover several statistical fea- turesofrealtraffic.Moreimportant,wehaveseenthatthe References routing algorithms can take advantage of the small-world structure of the web by reaching a critical path horizon 1. S-H.Yook,H.Jeong,andA-L.Barab´asi,Proc.NatlAcad. close to the network’s average path length. In doing so, Sci. USA,99, 13382, (2002) a highly efficient system is reached at low cost: routing 2. B. A. Huberman and R.M. Lukose,Science, 277, (1997) strategies only need to consider a small depth. Once the 3. N. Wiener, Cybernetics, John Wiley and Sons, New York m parameter reaches the network’s diameter, no further (1949) information is required to properly reach the target. A 4. James H. Cowie, David M. Nicol, Andy T. Ogielski, Com- full-system deterministic routing strategy is actually un- puting in Science and Engineering, 1(1), 42-50 (1999) necesaryandwouldbe toocostly.Instead,the constraints 5. W. Willinger, R. Govindan, S. Jamin, V. Paxson, and S. imposedbynetwork’sarchitectureallowtoexploittheim- Shenker,PNAS 99 (Suppl.1), 2573-2580 (2002) plicitinformationdefinedbythesmall-worldarchitecture. 6. R.V. Sol´e and S. Valverde,Physica A, 289, 595 (2001) ItmightbethatInternetevolvesinawaythatthrough- 7. S.Valverdeand R.V. Sol´e, Physica A, 312, 636 (2002) putorglobalperformanceismaximized.Thistrendiscon- 8. N. Hohn,D. Veitch and P. Abry,In;ACM/SIGCOMM In- strained within the limits of available communication re- ternetMeasurementWorkshop,Marseille,France.pp.63-68. sources. Inside this regime, Internet is shaped in order to (2002) 8 Sergi Valverde,Ricard V.Sol´e: Internet’sCritical Path Horizon 9. K.Fukuda,AStudy of Phase Transition PhenomenainIn- ternet Traffic, PhD Thesis, Keio Univ.(1999) 10. M. Argollo de Menezes and A-L. Barab´asi, cond-mat/0306304 (2003) 11. W.Willinger,M.S.Taqqu,R.ShermanandD.V.Wilson, IEEE/ACM Trans. on Networking, 5(1), 71-86 (1997) 12. H.Fuk´sand A. T. Lawniczak, adap-org/9909006 (2001) 13. M. Faloutsos, P. Faloutsos and C. Faloutsos, ACM SIG- COMM 29(4), 251-262, (1999) 14. K.Bolding,M.L.FulghamandL.Snyder,Tech.RepCSE- 94-02-04 (1994) 15. P.M. B.Vit´anyi,SIAMJ.Comput. 17,4, 659-672, (1988) 16. G. Bilardi and F. P. Preparata, CS-93-20, Dept. Comp. Sci. , Brown Univ.(1993) 17. B. Waxman, IEEE J. Selec. Areas Commun., SAC-6(9), 1617-1622, (1988) 18. A. V´azquez, R. Pastor-Satorras, and A. Vespignani, cond-mat/0206084 (2002) 19. When the link decision is ambiguous (more than one link can be selected) the less visited link until the moment is chosen(thiscouldbeimplementedbymaintainingacounter of the numberof packetsforwarded through thelink). 20. J. Dong Noh and H Rieger, cond-mat/ 0307719 (2003) 21. K.-I. Goh, B. Kahng, and D. Kim, Traffic and Granular Flow ’01, Springer, Berlin (2003) 22. M. E. J. Newman, cond-mat/0309045 (2003) 23. L.C. Freeman, Sociometry 40, 35 (1979) 24. D. H. Lorenz, A. Orda, D. Raz and Y. Shavitt, TR-2001- 17, DIMACS(2001) 25. L.J.Cowen,Proc.ofthe10thAnnualACM-SIAMSymp. on Discrete Algorithms, (1999) 26. M. Thorup and U. Zwick, Proc. 33th Annual ACM Sym- posium on Theory of Computing (SPAA),1-10 (2001) 27. D. Krioukov, K. Fall and X. Yang, cond-mat/0308288 (2003) 28. R.Percacci and A. Vespignani, cond-mat/0209619 (2002) 29. Internet End-to-end Performance Monitoring, http://www-iepm.slac.stanford.edu.