Title: A Survey on Measurement Tools Available For Internet

Author: Asrar Ul Haque
email:  ahaque@mcs.kent.edu , homepage: http://www.mcs.kent.edu/~ahaque

Prepared for Prof. Javed I. Khan
Department of Computer Science, Kent State University
Date: November 2001



Abstract: The efficient measurement of Internet state has become an important field to more effectively utilize Internet. In this servey the available tools and methologies have been explored. With the recents claims that measurement leads to NP-hard problems and that the existing tools might give erroneaous results and that the there is need for more diversified measurements, it is felt that more needs to be done in this area. 

Other Survey's on Internetwork-based Applications
Back to Javed I. Khan's Home Page

Table of Contents:

Recent Advances

Internet Measurement Insfrustructure

       Public Insfrustructure
       Private Insfrustructure

Future Challenges



 

Introduction:

The explosive growth of Internet has motivated deployment of a great variety of applications  ranging from simple text based application, to multimedia, IP-telephony and metacomputing services to name a few. This has created the ever increasing demand for bandwidth, predictable Quality of Service (QoS), and traffic management. The efficiency of resource allocation and the quality of service provded by the Internet depends critically on effective traffic management [3].
 

 What is to be Measured

Collection and analysis of basic traffic statistics is fundamental to providers' ability to design and and operate networks and to ensure the QoS for the time sensitive web applications. In addition to link utilization statistics, according CAIDA , both long-term aggregated statistics and short-term per flow statistics provide necessary insights relating to The sheer volume of the traffic and the high capacity of modern Internet trunks, however, make traffic monitoring for these and other purposes an increasingly challenging endeavor.

Backbone engineering and planning are among the most pressing needs for reliable forms of traffic data and analyses. Key elements of these analyses are aggregate traffic data at the IP layer, including port and protocol statistics (packets and bytes per port and per protocol) and traffic matrix statistics (how many packets and bytes were sent from network A to network B).

One participant of ISMA'97 from ANS described what forms of measurement data that he and other backbone engineers need most, suggesting that critical data not readily available include:

From the diversified web application point of view, [11] argues that emerging tele-interaction applications  (such as tele-surgery, remote instrument control) will require handle on the delay incurred at the video frame level, which is exactly not the same as the packet delay. The trend suggests that as more advanced, and complex netcentric applications are being envisioned more versatile network state information would have to be exchanged.
 

Classification

The way different properties related to Internet is measured can be classified into various groups.

General Classes of Measurement Approaches

Aggregation-based approaches are deterministic functions of the observed data [3] . They usually compute the sum or the maximum of some metric over the dataset (e.g. sum of packets traversing over a link during an interval, or the maxiend-to-end round trip delay for a set of packets.)

Whereas sampling based approaches extract a random subset of all the possible observations. This sample subset is supposed to be representative of all of the whole.
 

Active or direct measurements are network probes developed to measure the capabilities of the Internet. Active and passive measurements can be compared to car maintenance[6] . When you are trying to determine what is wrong with your car, you can either check your car’s oil level or give your car a test drive. A test drive would be an active measurement as it changes the state of the vehicle in question, while an oil check would be a passive measurement, which generally has no effect on the state of the car. With active measurements, one can generally retrieve additional information about a network’s capabilities, at the cost of adding interference and/or injecting probing packets into the network. Conceptually, [3] observed that, an passive or indirect measaurement method relies on a network model and network status information to infer the spatial flow of traffic through the domain. Some values, like the delays which are dynamic, changing with the traffic pattern and congestion in the network, may be significantly affected by the overhead of traffic generated by the protocol that performs the delay estimation by actively injecting packets into the network; hence, any such protocol must minimize this traffic overhead [12] .
  With explosion of Internet scability of any measuremening tools/architecture is an important issue. [12] suggests a hierarchical structure to achieve scalability. Moreover, both [12] and [11] sends messages to immidiate children nodes to make their architecture scalable.

Combinations
 

In this approach, e.g. link measurement, aggregate traffic statistics are measured on a per-link basis, and are reported periodically. Matrics typically include number of bytes and packets dropped within a reporting period. Some of these statistics are defined as part of the SNMP MIBS . [3] argued that since some information is lost during aggregaton and that this appraoch is better suited to detect potential problems, rather than to actually analyze the problem and modify routing information to remedy it. In this approach, e.g. flow aggregation, one or several routers within the domain collect per-flow measurements. A router has to maintain a cache of active flows. One disadvantage of flow aggregation is the amount of measurement data can be considerable and the traffic generated can impose a significant load on the network.
  In this approach, e.g. active end-to-end probes, hosts connected to the network send probe packets to one or several other hosts to estimate path metrics, such as the packet loss rate and round trip delay [ 8, 9, 10 ].

Classification Table
[4] shows differents projects which are now underway targetting different groups.
 
Comparation of Publicly Accessible Internet Insfrustructure
Project
Target Audience
Type (Active/Passive)
Analysis Type
CoralReef Traffic Engr, Internet Researchers Passive Workload
IEPM Network For HEP Community Active Performance
I2 (Abilence) High-availability Baclbone For Academic Researchers Passive & Active Workload & Performance
Mantra Internet Researchers MBGP Routing Multicast Performance
MAWI (WIDE) Internet Researchers Passive  Workload, Performance
NIMI Global Internet Comminity, Internet Researchers Active Workload, Performance
NLANR (MOAT) AMP Internet Researchers Active Performance
NLANR (MOAT) PMA Internet Researchers Passive  Performance
NI ACI NWS PACI High_Performance Application Users and Developers Active & Passive  Workload, Performance
PPNCG UK Particle Physics Community Active Performance
RIPE-RIS European Internet Comminity Passive  Performance
skitter Global Internet Comminity, Internet Researchers Acitve Topology, Routing
Surveyor US Higher Education Community Acitve Topology, Performance
TRIUMP Canadian Particle Physics Community Acitve Topology, Performance
U-Oregon Route Views Traffic Engr, Internet Researchers Passive Topology, Routing
WAND Internet Researchers Passive Workload, Performance 

NP Hard

[2] demonstrated that the problem of collecting link-bandwidth utilization information from an underlying network while minimizing the required number of SNMP probes gives rise to a novel, NP-hard generalization of the traditional Vertex Cover (VC) problem [17] , termed Weak VC. [2] proposed a new, polynomial-time heuristic algorithm for Weak VC that is provably near-optimal (with a logarithmic worst-case performance bound). They also showed that the optimal probe computation problem can be mapped to the well-known Facility Location Problem (FLP), which allows to use the polynomial-time  approximation algorithm of Hochbaum [18] to obtain a provably near-optimal set of IP probes.

Recent Advances

[12] presented network delay estimation protocols that can be used in multicast environments. Their protocol can be used in unstructured multicast protocols such as SRM [13] ; they extend it into one that can be used in a hierarchical multicast protocols such as RMTP [14] . The basic protocol estimates the delay from each node to every other node in a multicast group during a multicast transmission session, and applies where there is no logical structure among the receivers in the session. Receivers do not send any message directly to the sender. This avoids the implosion problem at the sender. The basic protocol can be extended to obtain a protocol that estimates the delay from a sender to every receiver in a hierarchically structured reliable multicast protocol such as RMTP [14] , TMTP [15] , and SHARQFEC [16] . A particularly attractive feature of this protocol is that only receivers that are the immediate children of the sender send messages directly to it; other receivers do not send any message directly to the sender. This avoids the implosion problem at the sender.
 

SPAND (Shared Passive Network PerformanceDiscovery) is a system that facilitates the development of adaptive network applications. In each domain, applications make passive application-specific measurements of the network and store them in a local centralized repository of network performance information. Other applications may retrieve this information from the repository and use the shared experiences of all hosts in a domain to predict future performance. In this way, applications can make informed decisions about adaptation choices as they communicate with distant hosts. All messages between the components of SPAND system use a format similar to Active Messages [20] . A SPAND message contains a handler string, an active flag, a data length, and a message-specific payload.

[21] looked at both of the problems of determining the setting of the retransmission timer (RTO) for a reliable protocol, and estimating the bandwidth available to a connection in the context of TCP, using a large TCP measurement set [22] for trace-driven simulations. For RTO estimation, they evaluated a number of different algorithms, finding that the performance of the estimators is dominated by their minimum values, and to a lesser extent, the timer granularity, while being virtually unaffected by how often round-trip time measurements are made or the settings of the parameters in the exponentially-weighted moving average estimators commonly used. For bandwidth estimation, they explored techniques previously sketched in the literature [23, 24] and found that in practice they perform less well than anticipated. [21] developed a receiver-side algorithm that performed significantly better.

Knowledge of the up-to-date bandwidth utilizations and path latencies is critical for numerous important network management tasks, including application and user profiling, proactive and reactive resource management and traffic engineering, as well as providing and verifying QoS guarantees for end-user applications. Indeed, these observations have led to a recent flurry of both research and industrial activity in the area of developing novel tools and infrastructures for measuring network bandwidth and latency parameters [2] . Examples include SNMP and RMON measurement probes [1] , Cisco’s NetFlow tools [25] , the IDMaps [26] , [27] and Network Distance Maps [28] efforts for measuring endto-end network  latencies, the pathchar tool for estimating Internet link characteristics [29] , [30] , and packet-pair algorithms for measuring link bandwidth [31] , [32] . A crucial requirement for such monitoring tools is that they be deployed in an intelligent manner in order to avoid placing undue strain on the shared resources of the production network

Topology-d is a service that estimates the state of networked resources by periodically computing the end-to-end latency and available bandwidth. Using its delay and bandwidth estimates, topology-d computes a fault tolerant, minimum-cost spanning tree connecting participating site.

TReno meaures the throughput of a given link independent of the particular TCP implementation on the end host. bprobr and cprobe probe the network (bandwidth) by sending several pairs (bprobr) or a short train of packets (cprobr) .

Internet Measurement Infrastructure

 

 

Several projects with measurement infrastructures for monitoring Internet Traffic are currently in place. These utilize either public or private infrastructure. CAIDA provides short summaries of those current measurement projects offering public reports.
 

Public Measurement Infrastructure

Private Measurement Infrastructure with Public Reports

Challenges for the New Decade

Challenges for the New Decade http://www.caida.org/outreach/papers/ieee0001/

As we enter the new decade, organizations engaged in analyzing macroscopic, infrastructure-wide traffic behavior [5] suggests that we must focus on

Progress requires both top-down and bottom-up momentum: users, researchers, and application developers must scope out the measurements essential to understanding Internet behavior and growth; ISPs need to deploy and evaluate measurement technology for their own network design, operation, and cost recovery. This work should be accompanied by more thoughtful infrastructure-relevant analysis of existing data. In particular, we need better correlation among data sources and types and greater feedback into the design of future data acquisition techniques as well as Internet technologies themselves.

Unlike many other fields of engineering, Internet data analysis is no longer justifiable as an isolated activity. The ecosystem under study has grown too large and is under the auspices of too many independent, uncoordinated entities. Nonetheless, as the system continues to evolve rapidly, the depth and breadth of our understanding of it should follow in close pursuit.

References

  1. W. Stallings, “SNMP, SNMPv2, SNMPv3, and RMON 1 and 2”, Addison-

  2. Wesley Longman, Inc., 1999, (Third Edition).
  3. Yuri Breitbart, Chee-Yong Chan, Minos Garofalakis, Rajeev Rastogi, Avi Silberschatz. Efficiently Monitoring Bandwidth and Latency in IP Networks . INFOCOM2001.
  4. N. G. Duffield , Matthias Grossglauser. Trajectory sampling for direct traffic observation,  IEEE/ACM, Transactions on Networking (TON) June 2001 Volume 9 Issue 3
  5. Murray, M. and k. claffy. (2001). "Measuring the Immeasurable: Global Internet Measurement  Infrastructure." in: Proceedings of PAM2001 - A workshop on Passive and Active Measurements.Amsterdam, Netherlands. RIPE NCC. Apr,2001 .
  6. claffy, k. (2000). "Measuring the Internet." IEEE Internet Computing 4(1): 73-5.
  7. http://moat.nlanr.net/Papers/AMP_case_studies/body.pdf
  8. SNMP
  9. R. Caceres, N. G. Duffield, L. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Transactions on Information Theory, 45:2462-2480, 1999.
  10. G. Almes, S. Kalidindi, and Zekauskas. a One-way Delay Metric for IPPM. RFC 2679, available from http://www.ietf.org/rfc, September 1999.
  11. G. Almes, S. Kalidindi, and Zekauskas. a One-way Delay Metric for IPPM. RFC 2680, available from http://www.ietf.org/rfc, September 1999.
  12. J. I. Khan and A. U. Haque, An Active Programmable Harness For Measurment Of Composite Network States, IEEE International Conference on Networking, ICN2001, Colmer, France, June 2001, pp628-638.
  13. Volkan Ozdemir, S. Muthukrishnan, and Injong Rhee. Scalable, Low-Overhead Network Delay Estimation . INFOCOM2000.
  14. S. Floyd, V. Jacobson, S. McCanne, C. G. Liu, and L. Zhang. A reliable multicast framework for light-weight sessions and application level framing. In Proceedings of the ACM SIGCOMM Conference, pages 342–356, October 1995.
  15. S. Paul, K. K. Sabnani, J. C. Lin, and S. Bhattacharyya. Reliable multicast transport protocol (RMTP). In Proceedings of the IEEE INFOCOM, San Francisco, CA, March 1996.
  16. R. Yavatkar, J. Griffioen, and M. Sudan. A reliable dissemination protocol for interactive collaborative applications. In Proceedings of ACM Multimedia, 1996.
  17. R. G. Kermode. Scoped hybrid automatic repeat request with forward error correction (sharqfec). In Proceedings of the ACM

  18. SIGCOMM Conference, pages 278–289, October 1998.
  19. M.R. Garey and D.S. Johnson, “Computers and Intractability: A Guide to

  20. the Theory of NP-Completeness”, W.H. Freeman, 1979.
  21. D.S. Hochbaum, “Heuristics for the Fixed Cost Median Problem,” Mathematical

  22. Programming, vol. 22, pp. 148–162, 1982.
  23. Mark Stemm , Srinivasan Seshan, Randy H. Katz. A Network Measurement Architecture for Adaptive Applications, INFOCOM2000
  24. Von Eicken, D. Culler, S. C. Goldstein, and K. E. Schauer, “Active Messages: a Mechanism for Integrated Communication and Computation,” in Proc. International Symposium on Computer Architecture, 1992
  25. Mark Allman , Vern Paxson. On estimating end-to-end network path properties, ACM SIGCOMM Computer Communication Review , Proceedings of the conference on Applicati ons, technologies, architectures, and protocols for computer communication August 1999, Volume 29 Issue 4.
  26. Vern Paxson. End-to-End Internet Packet Dynamics. En ACM SIGCOMM, Septiembre 1997.
  27. Janey Hoe. Improving the Start-up Behavior of a Congestion Control Scheme for TCP. En ACM SIGCOMM, Agosto 1996.
  28. Mohit Arony Peter Druschel. TCP: Improving Startup Dynamics by Adaptive Timers and Congestion Control. Informe Técnico TR98-318, Universidad Rice de Ciencias de la Computación, 1998.
  29. “NetFlow Services and Applications,” Cisco Systems White Paper, 1999.
  30. P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gryniewicz, and Y. Jin, “An Architecture for a Global Internet Host Distance Estimation Service,” in Proc. of IEEE INFOCOM’99, March 1999.
  31. S. Jamin, C. Jin, Y. Jin, Y. Raz, Y. Shavitt, and L. Zhang, “On the Placement of Internet Instrumentation,” in Proc. of IEEE INFOCOM’2000, March 2000.
  32. W. Theilmann and K. Rothermel, “Dynamic Distance Maps of the Internet,” in Proc. of IEEE INFOCOM’2000, March 2000.
  33. V. Jacobsen, “pathchar – A Tool to Infer Characteristics of Internet Paths,” April 1997, ftp://ftp.ee.lbl.gov/pathchar.
  34. A.B. Downey, “Using pathchar to Estimate Internet Link Characteristics,” in Proc. of ACM SIGCOMM’99, August 1999.
  35. J.-C. Bolot, “End-to-End Packet Delay and Loss Behavior in the Internet,” in Proc. of ACM SIGCOMM’93, September 1993.
  36. K. Lai and M. Baker, “Measuring Bandwidth,” in Proc. of IEEE INFOCOM’99, March 1999.
  37. M. Cheikhrouhou, J. Labetoulle, “An Efficient Polling Layer for SNMP,” Proc. 2000 IEEE/IFIP Network Operations & Management Symposium
  38. Katia Obraczka , Grig Gheorghiu. The performance of a service for network-aware applications.  Proceedings of the SIGMETRICS symposium on Parallel and distributed tools August 1998
  39. V. Paxson. Towards a framework for defining Internet performance metrics. Proceedings of the INET 1996.
  40. M. Mathis and J. Madhavi. Diagnosting Internet congestion with transport layer performance tool. Proceedings of the INET 1996.
  41. V. jacobson. Pathcahr: A tool to infer charaacteristics of Internet paths. Available from ftp://ftp.ee.lbl.gov/pathchar/, April 1997.
  42. R. Carter and M. Crovella, Dynamic server selection using bandwidth probingin wide area network. Boston university Computer Science Department. TR-96-007, March 1996.

  43.  

     

Research Groups

The National Laboratory for Applied Network Research (NLANR) http://moat.nlanr.net/

IP Providers Metrics (IPPM) - subgroup of the IETF's Bench marking Working Group
(BMWG

IP Netwrk Management and Performance Department, AT&T Labs - Research

The Cooperative Association for Internet Data Analysis ( CAIDA )

Scope

I have extensively searched digital libraries of IEEE and ACM. I have also searched using search engine (google). I used different combinations search tags of "internet", "measurement", "congestion", "state" and, "mobile". I also looked at the sessions related to measurement of INFOCOM of years 2000 and 2001. The papers presented by CAIDA (found from their website) and their citations were of immense help.