Internet’s Critical Path Horizon

The internet is known to display a highly heterogeneous structure and complex fluctuations in its traffic dynamics. Congestion seems to be an inevitable result of users' behavior coupled with network dynamics and its effects should be minimized by choosing appropriate routing strategies. But what are the requirements of routing depth in order to optimize the traffic flow? In this paper we analyze the behavior of internet traffic with a topologically realistic spatial structure as described in a previous study (S-H. Yook et al., Proc. Natl. Acad. Sci. USA, 99 (2002) 13382). The model involves self-regulation of packet generation and different levels of routing depth. It is shown that it reproduces the relevant, key, statistical features of the internet's traffic. Moreover, we also report the existence of a critical path horizon defining a transition from poorly performing traffic to highly efficient flow. This transition is actually a direct consequence of the web's small world architecture exploited by the routing algorithm. Once routing tables reach the network diameter, the traffic experiences a sudden transition from poorly performing to highly efficient behavior. It is conjectured that routing policies might have spontaneously reached such a compromise in a distributed manner. The internet would thus be operating close to a critical path horizon.