Hui Zhang
Ramesh Govindan
Abstract
The Internet's latency expansion determines the asymptotic performance of large-scale distributed systems (such as Peer-to-Peer systems), but previous studies on the Internet have defined expansion in terms of router-level hops. In this paper, we empirically determine the Internet's latency expansion characteristics using measurements from two different Internet topology datasets. Our results show that the Internet router-level topology exhibits a power-law latency expansion, in contrast to its exponential expansion rate in terms of hops.
- I. Abraham, D. Malkhi and Oren Dubzinski. LAND: Strech (1+epsilon) Locality Aware Networks for DHTs. the ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, LA, 2004. Google Scholar
Digital Library
- W. Aiello, F. Chung, and L. Lu, A Random Graph Model for Massive Graphs. the 32nd Annual Symposium on Theory of Computing, 2000. Google ScholarDigital Library
- B. Bollobas. Random Graphs. Academic Press, Inc. Orlando, Florida, 1985.Google Scholar
- C. J. Bovy, H. T. Metrodimedjo, G. Hooghiemstra, H. Uijterwaal, and P. Van Mieghem. Analysis of End-to-end Delay Measurements in Internet. the 3th International workshop of Passive and Active Network Measurement, 2002.Google Scholar
- C. Faloutsos, P. Faloutsos, and M. Faloutsos. On Power-law Relationships of the Internet Topology. ACM SIGCOMM, 1999. Google ScholarDigital Library
- R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. IEEE INFOCOM, 2000.Google ScholarCross Ref
- D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-restricted Metrics. ACM Symposium on Theory of Computing (STOC '02). May 2002. Google ScholarDigital Library
- D. Kempe, J. Kleinberg. Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. FOCS 2002, Vancouver. Google ScholarDigital Library
- A. Lakhina, J. W. Byers, M. Crovella, and P. Xie. Sampling Biases in IP Topology Measurements. IEEE INFOCOM, 2003.Google ScholarCross Ref
- H. Lim, J. C. Hou, and C. Choi. Constructing Internet Coordinate System Based on Delay Measurement. Internet Measurement Conference (IMC), 2003. Google ScholarDigital Library
- B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman and Co, New York, rev. 1983.Google Scholar
- E. Ng, and H. Zhang. Predicting Internet Network Distance with Coordinated-nased Approaches. IEEE INFOCOM, 2002.Google ScholarCross Ref
- V. N. Padmanabhan, L. Subramanian. An Investigation of Geographic Mapping Techniques for Internet Hosts. ACM SIGCOMM, 2001. Google ScholarDigital Library
- V. Paxson, J. Mahdavi, A. Adams, and M. Mathis. An Architecture for Large-Scale Internet Measurement. IEEE Communications, 36 8, 48--54 (1998) Google ScholarDigital Library
- R. Percacci, and A. Vespignani. Scale-free Behavior of the Internet Global Performance. European Physical Journal B 32, p. 411--414, 2003.Google Scholar
- G. Phillips, S. Shenker, H. Tangmunarunkit. Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law. ACM SIGCOMM, 1999. Google ScholarDigital Library
- PlanetLab homepage. http://www.planet-lab.org/.Google Scholar
- C. G. Plaxton, R. Rajaraman, and A. W Richa. Accessing Nearby Copies of Replicated Objects in A Distributed Environment. the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, 1997. Google ScholarDigital Library
- N. Spring, R. Mahajan, D. Wetherall. Measuring ISP Topologies with Rocketfuel. ACM SIGCOMM, 2002. Google ScholarDigital Library
- L. Tang, and M. Crovella. Virtual Landmarks for the Internet. Internet Measurement Conference (IMC), 2003. Google ScholarDigital Library
- L. Tang, and M. Crovella. Geometric Exploration of the Landmark Selection Problem. the 5th International workshop of Passive and Active Network Measurement, 2004.Google Scholar
- H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger, Network Topology Generators: Degree-Based vs. Structural. ACM SIGCOMM 2002. Google ScholarDigital Library
- H. Zhang, A. Goel, and R. Govindan. Incrementally Improving Lookup Latency in Distributed Hash Table Systems. ACM SIGMETRICS 2003. Google ScholarDigital Library
Index Terms
- An empirical evaluation of internet latency expansion
Recommendations
Evaluation of query expansion using MeSH in PubMed
This paper investigates the effectiveness of using MeSH® in PubMed through its automatic query expansion process: Automatic Term Mapping (ATM). We run Boolean searches based on a collection of 55 topics and about 160,000 MEDLINE® citations used in the ...
Empirical term weighting and expansion frequency
EMNLP '00: Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics - Volume 13We propose an empirical method for estimating term weights directly from relevance judgments, avoiding various standard but potentially trouble-some assumptions. It is common to assume, for example, that weights vary with term frequency (tf) and inverse ...
On Internet-of-Things (IoT) gateway coverage expansion
AbstractThe Internet of Things (IoT) has developed rapidly in recent years where significant numbers of devices have been connected to the network and this will increase over the ensuing years. There is also a trend to shift the IoT topology ...
Highlights- In a mesh network, a gateway may handle multiple routers.
- Routers might have ...
Comments