End-to-end routing behavior in the Internet
- 28 August 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 26 (4) , 25-38
- https://doi.org/10.1145/248157.248160
Abstract
The large-scale behavior of routing in the Internet has gone virtually without any formal study, the exception being Chinoy's analysis of the dynamics of Internet routing information [Ch93]. We report on an analysis of 40,000 end-to-end route measurements conducted using repeated "traceroutes" between 37 Internet sites. We analyze the routing behavior for pathological conditions, routing stability, and routing symmetry. For pathologies, we characterize the prevalence of routing loops, erroneous routing, infrastructure failures, and temporary outages. We find that the likelihood of encountering a major routing pathology more than doubled between the end of 1994 and the end of 1995, rising from 1.5% to 3.4%. For routing stability, we define two separate types of stability, "prevalence" meaning the overall likelihood that a particular route is encountered, and "persistence," the likelihood that a route remains unchanged over a long period of time. We find that Internet paths are heavily dominated by a single prevalent route, but that the time periods over which routes persist show wide variation, ranging from seconds up to days. About 2/3's of the Internet paths had routes persisting for either days or weeks. For routing symmetry, we look at the likelihood that a path through the Internet visits at least one different city in the two directions. At the end of 1995, this was the case half the time, and at least one different autonomous system was visited 30% of the time.Keywords
This publication has 19 references indexed in Scilit:
- Routing in multihop packet switching networks: Gb/s challengeIEEE Network, 1995
- A parameterizable methodology for Internet traffic flow profilingIEEE Journal on Selected Areas in Communications, 1995
- Network support for multimedia A discussion of the Tenet approachComputer Networks and ISDN Systems, 1994
- The synchronization of periodic routing messagesIEEE/ACM Transactions on Networking, 1994
- Empirically derived analytic models of wide-area TCP connectionsIEEE/ACM Transactions on Networking, 1994
- Multicast routing in datagram internetworks and extended LANsACM Transactions on Computer Systems, 1990
- Poisson Arrivals See Time AveragesOperations Research, 1982
- The New Routing Algorithm for the ARPANETIEEE Transactions on Communications, 1980
- Routing Techniques Used in Computer Communication NetworksIEEE Transactions on Communications, 1980
- A Review of the Development and Performance of the ARPANET Routing AlgorithmIEEE Transactions on Communications, 1978