[INET'99] [ Up ][Prev][Next]

Surveyor: An Infrastructure for Internet Performance Measurements

Sunil KALIDINDI <sunil@advanced.org>
Matthew J. ZEKAUSKAS <matt@advanced.org>
Advanced Network & Services
USA

Abstract

As the Internet becomes larger and more complex, sound methodologies to characterize Internet performance and a scalable measurement infrastructure become indispensable. Surveyor is a measurement infrastructure that currently measures end-to-end unidirectional delay, packet loss, and route information along Internet paths. It is deployed at about 50 higher education and research sites around the world. This paper describes the Surveyor infrastructure and initial results from the project. We have developed techniques for scalable and accurate measurements, tools for analysis, and an architecture for long-term storage and data access. Initial results illustrate the value of one-way measurements as opposed to traditional round-trip measurements.

Contents

Introduction

Historically, the Internet has been inadequately measured [Paxson*98]. Today, the situation is even worse. The tremendous growth in the numbers of hosts, networks, network types, and network peering points results in a general lack of understanding of network performance. We believe that consistent measurement of well-defined performance metrics would enable better network engineering and operations.

The Surveyor project consistently measures end-to-end unidirectional delay, loss, and routing among a diverse set of measurement probes throughout the Internet. The goal of the project is to create technology and infrastructure to allow users and service providers (at all levels) to have an accurate common understanding of the performance and reliability of paths through the Internet. Surveyor measures the one-way delay [Almes*98a] and one-way loss [Almes*98b] metrics being developed by the Internet Protocol Performance Metrics (IPPM) working group of the Internet Engineering Task Force (IETF). Surveyor is currently deployed at 41 sites in the higher education and research communities, including universities, U.S. national labs, and international sites.

Roadmap

The next section describes the principles underlying the Surveyor infrastructure. We then describe the components of the infrastructure itself. We describe the basic analyses that have been performed for the life of the project and then report on some interesting initial results related to asymmetries seen by Surveyor that cannot be seen using round-trip measures. We then review the work related to Surveyor and conclude with a description of future work for the project.

Surveyor's approach to measurements

The Surveyor project's goal is to measure the performance of wide-area network connectivity among the participants, using well-defined metrics over long periods. If a participant is measuring a sufficiently large number of paths, the performance data may be somewhat representative of the participant's general Internet connectivity. However, we make no claim that these data represent either the Internet as a whole or the performance of a particular application. Rather, these data help pairs of sites understand the underlying network connectivity between them.

The guiding principles to achieve our goal are as follows:

Measurement methodology

Currently, the Surveyor infrastructure measures one-way delay, one-way loss, and route information along Internet paths. One-way delay and loss are measured according to the IETF IPPM one-way delay metric [Almes*98a] and one-way packet loss metric [Almes*98b]. (Detailed methodology can be found in the documents cited.) Route information is gathered by using a modified version of traceroute [Jacobson89].

Delay and loss

Delay and loss are measured using the same stream of active test traffic. A Poisson process on the sending machine schedules test packets. Most of our paths use a lambda of 2 per second, so on average, two packets are sent out per second. This traffic is too heavy for the New Zealand and Swiss sites, so they use a lambda of 1 per second.

A lambda of 2 per second was initially chosen as a pragmatic compromise. Because Internet traffic is apparently fractal in nature (or behaves as though it were fractal), more frequent tests are desired to obtain more detail. One goal is to use the data for research, so we did not want to skew the tests in answering particular questions. However, the tests cannot be too frequent, because the amount of test traffic should not perturb the measurements. In addition, we had disk space limits: two packets per second is 178,800 measurements a day per path. Initially, this required greater than 2 megabytes per day plus other relational database overhead.

Each test packet is of minimal size: 12 bytes of user data, essentially a sequence number and a timestamp. The test packets are sent using User Datagram Protocol (UDP), so the actual packet size, excluding any Media Access Control (MAC) header, is 40 bytes. The minimal test packet was chosen because the initial goal is to have a good understanding of how the underlying paths perform, that is, to obtain a "baseline." As new analyses are developed, we will consider sending out packet trains or packets of variable size.

Because the Surveyor measurement machines are equipped with GPS hardware for time synchronization, timestamps carried by test packets have global meaning. The receiving machine determines the delay of the test packet directly: it simply subtracts the time in the received packet from the current time. Because the packets are timestamped, and the receiver knows the schedule they will be sent on, the receiver knows when a sent packet does not arrive. This is how packets are known to be lost. In the current implementation, if a packet does not arrive within 10 seconds, it is assumed to be lost. Lost packets are treated as sent packets with infinite delay.

Route information

Route information is gathered for the same paths as delay and loss. The information is gathered using a modified version of traceroute [Jacobson89]. The modifications are threefold. First, we are more persistent in the face of failure. If an Internet Control Message Protocol (ICMP) "time to live" (TTL) exceeded message is not forthcoming, we try 10 rather than the default 3 times. Second, we are less persistent in the face of success. Rather than send out three probes for each TTL failure or success, we stop sending probes once we are successful. Third, we do not keep any of the timing information. Round-trip times generated by traceroute are notoriously inaccurate, because the response message is generated by an exceptional condition at each hop along the path. Rather than rely on this data, we do not keep it at all.

Route information is gathered based on a schedule generated by a truncated Poisson process. The lambda is 1 every 10 minutes, so on average a traceroute should be generated once every 10 minutes. However, the longest time between measurements increases to more than 1 hour in practice, which makes the routing measurements less useful. Therefore, we schedule a routing measurement at least once every 10 minutes, and more frequently if the Poisson process schedule indicates that a packet should be sent sooner.

Components of the surveyor infrastructure

There are three major components of the Surveyor infrastructure: measurement machines, the database, and the analysis server. The measurement machines are the dedicated machines that we deploy at participating sites. The measurement machines report back to a central database that catalogs all the performance data. Finally, analyses are performed by, and made available through, an analysis server. The analysis server is accessed via Hypertext Transfer Protocol (HTTP).

The measurement machines

Each Surveyor measurement machine is a Dell desktop PC. We have machines with 200-, 333-, and 400-MHz Pentium processors deployed in the field. In addition to the basic PC, each machine has an appropriate network interface card, and a GPS card. We currently support Ethernet (both 10bT and 100bT), Fiber Distributed-Data Interface, and Optical Carrier (OC)-3 asynchronous transfer mode (ATM) network interfaces. We use GPS receiver cards manufactured by TrueTime in the field. These cards keep the current time on-board (so a read on the system bus is required to read the time). We have both Industry Standard Architecture (ISA) and Peripheral Component Interconnect (PCI) flavor cards. The GPS cards use an antenna and GPS daughter board manufactured by Trimble. An RG-59 or RG-58 coaxial cable, depending on wire run length, is used to connect the antenna to the card.

The machines run the BSDI version 3.1 operating system. BSDI was originally chosen because it is the same operating system run by many Internet service providers, and we were able to capitalize on existing talent to obtain a driver for our GPS card.

Software to measure one-way delay and loss

The methodology to measure one-way delay and loss is described above. The accuracy of the measurements is determined in part by the degree of time synchronization among the Surveyor measurement machines. Using the GPS cards, synchronization on the order of 2 microseconds is achieved. The IPPM one-way delay metric is defined by "wire times" -- that is, the time the first bit of the test packet is transmitted and the time the last bit of the packet is received by the network interface. However, software is performing the measurements, and the timestamps it takes are called "host times." These differ from wire times because of software and hardware overhead. In addition, measurement software is easier to implement and manage as user-level code. Taking timestamps at user level makes the host time even further away from the wire time, and as the measurement load on the machine increases, the measurement error that is due to the time difference between the time a test packet is timestamped at user-level and the wire time increases.

This situation presents a problem of scale -- the accuracy of the measurements suffers as the number of measurements increases.

To solve this problem, Surveyor has implemented a modification to the BSDI network drivers. The simple modification involves setting up flags to indicate that a given socket is used for performance tests. Inside the kernel code, this flag is checked, and if the flag is set, a timestamp is taken inside the kernel itself, so that it is not necessary to wait for the user-level process to receive the test packet and then timestamp it. This modification enables accurate measurement even at high load. Calibration of the measurements using this kernel modification on the Surveyor platform has yielded an error bar of better than 20 microseconds for 95% of the packets, even when measuring 100 paths from and to a given measurement machine.

Central database

All measurements are transferred to a central database machine for later analysis and long-term storage. We are currently using a four-processor Silicon Graphics Origin 200 as the database server. It has a 600-gigabyte redundant array of independent disks attached via Fibre Channel.

The Surveyor measurement machines collect performance data and buffer them to a local disk. Once every few minutes, the measurement machines are polled for new performance data; if found, the data are uploaded to the central database. Both the polling and data transfer occur using ssh. The measurement machines trust the central database machine's key, but the central database does not trust any of the measurement machines. Thus, if a measurement machine is compromised, it will affect only the local measurements. The database machine is conservatively configured.

We have developed a simple database structure to efficiently store the one-way delay and loss data. The database is based on the Unix directory structure, and the data itself are stored in binary files. Originally, the raw data were stored in a relational database, but we found that we were not performing any sophisticated queries (in most cases, nothing more sophisticated than "give me all data for a specified path on a certain day"). The resources required to maintain the database (both central processing unit and disk) were excessive given that we were not using the relational database capabilities. In conversations with other large measurement groups, we found similar stories -- that the raw data were generally kept in raw disk files, with databases used for various database summaries.

Similarly, the routing measurements are kept in a highly compressed structure. The only difference is that the routes are kept in ASCII, not binary.

Because of our test protocol, there is no need to correlate information from different machines to compute the low-level one-way delay, loss, or route information. Thus, as soon as the information arrives from one machine, it can be filed away or presented to a user in close to real time.

Data analysis Web server

Since the first measurement machines have been deployed, we have generated summary statistics (described in detail in the next section) for each path and produced a 24-hour plot of the summary statistics and for each path. All daily statistics are based on Universal Time Coordinated (UTC), and generation of statistics starts soon after midnight UTC.

The daily summary plots, traceroute data, and the "raw" daily summary statistics are made available using an HTTP server. Primary access is to the plots and traceroute data; the raw data are intended for other analysis programs. There are three daily plots available for each path: one showing summary statistics on delay, one showing loss throughout the day, and one showing a histogram of delay values.

Currently, there are four general views of the plots available: calendar, per site, per path, and animated. The calendar view allows the choice of a specific path on a specific day. The per-site view allows you to see all paths entering and leaving a given site on a given day. The per-path view allows you to see both the path from a given source to a given destination, and the reverse path, for a given number of days. Finally, the animated view shows one direction of the per-path view, but presents the data as a single animated GIF instead of a sequence of GIFs, one per day.

In all but the animated view, the user can drill down to a specific path on a specific day. That display includes a table of traceroutes collected on that day, and a specific traceroute can be selected to display.

Initial analyses

For each of the paths, records consisting of the pair <time-the-packet-was-sent, one-way-delay-observed> are kept in a central database. If the packet was lost, the observed delay is recorded as infinite. In addition, for each of the paths and for each day, summary statistics are computed for each minute in the day and are stored in a "summary database." The IETF IPPM documents define several summary statistics. We divide each day (UTC) into 1,440 minutes. Because almost all paths average two measurements per second, each minute contains roughly 120 measurements. For each minute, we compute the following summary statistics:

The minimum and the 50th and 90th percentiles are based on the IPPM type P one-way-delay-percentile statistic. The percentage of packets lost is based on the IPPM type P one-way-packet-loss-average statistic. Type P, the type of the packets, is 12-byte UDP using unspecified ports. Note that because lost packets are considered to have infinite delay, it does not make sense to discuss averages and standard deviations.

From these summaries, we generate two types of plots, percentiles of delay and percentage loss. In addition, we generate a histogram of delay values binned into 5-millisecond increments.

Percentiles of delay

An example of a delay percentiles plot is shown in Figure 1. This plot represents a path from the East Coast of the U.S. to the Netherlands. The x-axis represents time, given in hours since midnight UTC. The y-axis represents one-way delay in milliseconds. The blue dots represent the minimums during each 1-minute interval, the green dots represent 50th percentile values, and the red dots represent 90th percentile values. When the 90th percentile is infinite (more than 10% packet loss), it is plotted as a red dot at the top of the graph. Gaps in the graph represent a period of no measurement activity, which usually occurs because one or the other end loses GPS lock; rather than trusting the internal oscillator on our GPS card, we choose to halt measurements.

There are three distinct sources of delay experienced by Internet Protocol (IP) packets: transmission delay, propagation delay, and queuing delay. Transmission delay is the delay due to the time taken to transmit a packet across a network interface. Propagation delay is the delay due to the finite speed of electrons and photons along the path from source to destination. Queuing delay is the delay due to the packet's waiting to be serviced in various network queues, principally the queues of routers.

In modern high-speed networks, transmission delay is very small, so that most of the constant delay is due to propagation. For example, our 40-byte test packets take about 7 microseconds on a T3 interface and about 220 microseconds on a T1 interface. Typical wide-area network paths have a propagation delay on the order of tens of milliseconds. For example, considering the propagation speed of light through fiber to be approximately 200 kilometers per second, the U.S. coast-to-coast path has a propagation delay of approximately 20 milliseconds.

Almost all the links being tested are T3 and faster. Typically, therefore, along a given path, propagation delay is much higher than transmission delay. Also, as long as IP routing remains constant for a given path, both transmission and propagation delay are constant. (Level 2 routing, if used, would also have to remain constant -- with the same ATM and/or Synchronous Optical Network [SONET] path used.)

Therefore, the minimum possible delay for a given path is the sum of transmission and propagation delay, is constant, and can be approximated to the propagation delay. Step functions in the minimum delay often indicate routing changes. Delays higher than the minimum delay are due to the additional queuing delay. Queuing delay is usually due to congestion; hence, delays that are higher than the minimum possible are indicators of congestion.

When the path is uncongested, the minimum observed delay in the given minute (blue dots in Fig. 1) is close to the propagation delay. We have found that even in a congested path, at least one of the test packets is not likely to experience congestion. Therefore, the blue points remain the same and stay close to the propagation delay. Changes in the value of the blue points typically indicate a change in the path or an extreme case of congestion. The green and red points indicate congestion. When the path is uncongested, they are also close to the propagation delay and hence are close to the blue points. During periods of congestion, the green and red points differ considerably from the blue points. The distance between them is a measure of variance and, hence, congestion.

Note that any one of the percentile values (other than the minimum, which has the physical analog of propagation delay) in isolation is not very useful and can sometimes be misleading. For example, consider two 1-minute intervals that have less than 50th percentile, 90th percentile pairs of less than 10,100 and less than 80,85. If we are looking at the 90th percentile values in isolation, we might erroneously conclude that the second minute was less congested than the first (because the 90th percentile delay in the second minute [85] was lower than in the first minute [100]).

Percent loss

Figure 2 shows the percentage loss graph for the same path as Figure 1. Again, the x-axis represents time in hours since midnight UTC. The y-axis represents the percentage of packets lost. A separate red dot is plotted for each minute. Red dots at the top of the graph represent periods where the percentage of packets lost during that interval are greater than or equal to the maximum value of y.

The lines that appear at lower percentages (1%-3%) result from the fact that one or two packet losses in the interval are about 1% or 2%. As the number of packet losses increases, the number of packets at a given value decreases, and the result of the division is more evenly spread among the integral loss values, resulting in a more "blurry" cluster.

As noted in the metric document, healthy Internet paths should be operating at loss rates of less than 1% (particularly if high-delay-bandwidth products are to be sustained). (See [Mathis*97] for a discussion of the effect of losses on Transmission Control Protocol [TCP] for different bandwidth paths.) A high percentage of loss is another indication of a congested path.

Delay histogram

Figure 3 shows the histogram of delays along the same path shown in Figures 1 and 2. The x-axis represents the delay buckets in milliseconds. The y-axis represents the percentage of packets that fell into a given bucket during the day. We use 5-millisecond buckets and draw a bar up to the percentage of packets that fell into a bucket. For example, if 40% of the packets have a delay value greater than or equal to 15 milliseconds and less than 20 milliseconds, the value of the bar starting at 15 and ending at 20 would be 40.

A single spike would indicate low queuing over one route. Multiple spikes indicate multiple routes, or multiple phases, throughout the day (e.g., a period of little congestion together with a period of moderate congestion). A smooth histogram indicates persistent congestion. Because multiple peaks can have different meanings, the histogram should be used in conjunction with the other plots.

Some initial results

The current set of 41 participants is mostly concentrated in North America. The North American sites consist of 24 U.S. universities (including Hawaii, but not [yet] Alaska), 8 U.S. national laboratories, 3 sites in the Canadian research and education network, and 2 other research institutions. The remaining non-U.S. sites (other than the Canadian sites) consist of one each in New Zealand, Switzerland, Norway, the Netherlands, and Germany. We have other sites pending. The heavy emphasis on research-and-education indicates that the sites do not represent commercial or home Internet access. However, these sites do have an additional burden in that they are often connected to multiple networks, usually a research network (such as the very high-speed Backbone Network Service [vBNS]) and one or more "commodity" Internet providers.

Surveyor is currently measuring over 1,000 paths among these sites. There are about 10 transatlantic paths and about 10 transpacific paths. We now examine properties of the paths, first showing some specific examples and then looking for some general features of the paths under test.

Specific examples

The following specific examples provide a sampling of the type of features that can be seen from the daily graphs.

Routing change along a path

Figure 4 shows a routing change between two sites. The two sites are in the eastern U.S., so the change took place in the early morning and is represented by a discontinuity in the delay. The minimum delay along this path dropped by about 10 milliseconds. The receiving site is multi-homed, and it changed the way its network was advertised, resulting in the routing change. The reverse path had no such discontinuity. It would be impossible to know from round-trip delay measurements which path (if any) changed.

Asymmetry in routing

Figure 5 and Figure 6 together show an asymmetry in routing reflected in the delay measurements. Figure 5 represents a path from two sites on the East Coast of the U.S. The path is fairly direct, and the minimum latency between the sites is approximately 7 milliseconds. Figure 6 represents the reverse path. Here, the minimum latency is about 75 milliseconds. A check of the routing data showed the problem -- the reverse path is via the West Coast of the U.S., and the extra latency is due to the round-trip across the U.S. and back.

Performance of high-speed research network

Figure 7 and Figure 8 show a path between a site on the East Coast of the U.S. and a site on the West Coast of the U.S. over two consecutive days. The old path was fairly congested. About 2 hours before the end of the first day, the destination site was connected to the vBNS. The source site was already connected to the vBNS. Within 4 hours, the path had stabilized over the vBNS to the point at which all of the 90th percentile delays were practically identical to the minimum delays, showing very little congestion. The four bursts at approximately 14, 16, 18, and 20 hours were later found to be caused by bulk transfer tests being carried out from the source site to a third site.

General features

Because of space and time constraints, we will examine only 1 month of our data. We have chosen November 1998 because it is the most recent full month that does not contain long periods of school holidays. Because most of our machines are university-based, extended holidays could affect the results. The purpose of this study, however, was only to get a feel for some of the features of our paths under test. Again, our data do not represent either the Internet in general or any application in particular.

Overall packet loss

We started by considering overall packet loss for the month of November. Our packet loss figures show only the loss of our measurement traffic, not the total number of packets lost along a given path. Also, our traffic is not representative of any particular application, because the packets are sent out using a Poisson schedule. Nevertheless, these loss statistics provide a rough idea of a lower bound on the loss that applications among our participating sites might have seen over the month.

Table 1: Overall packet loss
Regions Number Entire Day Worst Quarter of the Day Worst Hour of the Day
All paths 1084 1.06% 1.44% 4.88%
U.S.-U.S. 1060 1.04% 1.40% 4.79%
U.S.-Europe 12 1.39% 1.52% 5.71%
U.S.-New Zealand 10 2.58% 4.04% 11.15%
Europe- New Zealand 2 0.58% 1.51% 6.97%

Table 1 presents the percentages of our measurement packets lost over the entire month. We compute the percentage of packets lost on each path and then average the paths. We then group the paths by the regions they cross: U.S.-U.S. (all paths within the U.S.), U.S.-Europe (transatlantic), U.S.-New Zealand (transpacific), and Europe-New Zealand. The number of paths in each group is also reported.

Aggregation over the entire day tends to obscure periods of heavy congestion. Therefore, we also consider the loss statistics for the worst 6 hours in the day (worst quarter of the day) and for the worst hour in the day in terms of packet loss. In each case, for each day, we find the contiguous hour or 6 hours with the worst loss, and we report that. The particular hour or 6 hours may vary from day to day. We then average all of the worst hours (or quarter days) for a path over the month and then calculate an average over all paths (or by region).

The results show that paths are pretty good overall, with less than 2% loss for all paths except between the U.S. and New Zealand, which is known to be a congested path because of lack of capacity. On the other hand, it is surprising that within the U.S., the average for the entire month is still about 1%. There are still some bad paths between some of our U.S. sites.

Reducing our focus to the worst 6 hours of the day did not cause loss figures to rise much -- again, except for New Zealand. Reducing the focus still further to the worst hour of the day shows that the worst hour is significantly worse than the rest of the day; the overall average rises by a factor of about 3.

Paths with high loss

We now examine the opposite question: How many paths have losses that are greater than a given threshold? Tables 2 through 4 show this data grouped by region.

Table 2: Percentage of U.S.-U.S. paths with losses greater than threshold
Packet Loss % Threshold Entire Day Worst Quarter Worst Hour
1% 34.1% 25.7% 70.3%
2% 12.6% 16.1% 53.9%
5% 2.2% 3.4% 32.1%
10% 0.4% 0.6% 11.9%
20% 0% 0.2% 0.5%
Table 3: Percentage of U.S.-Europe paths with losses greater than threshold
Packet Loss % Threshold Entire Day Worst Quarter Worst Hour
1% 33.3% 33.3% 83.3%
2% 25.0% 8.33% 66.7%
5% 8.3% 8.3% 33.3%
10% 0% 8.3% 2.5%
20% 0% 0% 0%
Table 4: Percentage of U.S.-New Zealand paths with losses greater than threshold
Packet Loss % Threshold Entire Day Worst Quarter Worst Hour
1% 70% 70% 100%
2% 40% 70% 100%
5% 20% 30% 70%
10% 0% 30% 60%
20% 0% 0% 10%

Table 3 shows that almost 12 percent of our paths inside the U.S. have an hour period in which the loss averages greater than 10%. These paths are particularly bad for TCP traffic, especially if it is interactive. Table 4 shows that the paths to Europe are worse in general as expected. However, only 2.5% of these paths have greater than 10% average loss in their worst hour. (Recall that there are a small fraction of paths [12 vs. 1,084], so the sample size is small.) Table 5 shows that the paths to New Zealand across the Pacific are worse still, which again is expected because of the current lack of transpacific bandwidth.

Asymmetry in loss

For a given path, the aggregate percentage packet loss over the month of November is computed in both the forward and reverse directions. If the percentage packet loss in the forward and reverse direction differs by more than a certain threshold, we consider the paths to be asymmetric for the month. We define the "threshold" to be the difference in loss in the forward and reverse directions as a percentage of the lower of the two. For example, a threshold of 100% means that there was twice as much loss in one direction as in the reverse direction).

Table 5: Percentage of paths with asymmetric loss
Threshold Paths Greater than Threshold Only Those Paths with Greater than 1% Loss
25% 70% 15%
50% 56% 10%
100% 46% 5%
200% 27% 3%

Percentage loss in 46% of the paths was more than double the percentage loss in the reverse path. This shows a high degree of asymmetry in loss. However, a 100% difference in which the losses rise from 0.2% to 0.4% might not be considered significant, so we also show the asymmetry when both directions have greater than a 1% loss. In that case, 5% of the paths have at least double the loss in one direction than in the other direction, which is still significant.

Regional asymmetry

Here, we group losses of paths that leave (or enter) the U.S. by the destination region.

Table 6: Asymmetry in loss by region
Duration U.S. to Europe Europe to U.S. U.S. to New Zealand New Zealand to U.S.
Daily average 2.11% 0.67% 3.52% 1.63%
Worst quarter 4.92% 2.44% 9.19% 5.39%
Worst hour 10.96% 7.14% 21.32% 14.75%

As expected, the transpacific paths are more congested (as measured by losses) than the transatlantic paths. The losses are also asymmetric: the heaviest losses are in the direction of most traffic, away from the U.S.

Asymmetry in propagation delays

Typically, for the kind of paths we measure in Surveyor, propagation delay is much higher than transmission delay, and the minimum possible delay for a given path can be approximated to propagation delay. Delays higher than the minimum delay are due to the additional queuing delay, which is usually caused by congestion.

Because it is likely that even during periods of moderate congestion there will be at least one test packet in a given minute that will experience little or no congestion (recall that there will be about 120 measurements in a given minute), the minimum observed delay in the minute can be approximated to the propagation delay during the minute. Furthermore, if the route is stable during the 24-hour period and there is no extreme congestion, the minimum delays for the day would all be the propagation delay along the path and would all be approximately the same. Therefore, we restrict ourselves to paths in which the minimum values are all approximately the same, because for those paths, the minimum is most likely to approach the propagation delay.

We consider all the per-minute minimum delays for a given day and sort them. If the difference between the 90th percentile of the minima and the 0th percentile of the minima is greater than 1 millisecond, we consider the path to have "unstable" propagation delay and do not consider it in the analysis. If the difference between the 90th percentile of the minima and the 0th percentile of the minima is less than 1 millisecond, then we take the propagation delay of the given path for that given day to be the 0th percentile of the 1-minute minima.

If the propagation delays for the day in the forward and reverse directions differ by more than 5 milliseconds, we consider the paths to have asymmetric propagation delays during that day. We then compute the percentage of the considered paths that are asymmetric.

Table 7: Asymmetry in minimum delays
Total path-days for which data are available 24,453
"Unstable" path-days 7,003
Total path-days considered 17,450
Asymmetric path-days 1,754
Percentage of asymmetric path-days of those considered 10.05%

Table 7 shows the results for November 1998. We find that between 7% (considering all paths) and 10% (considering just stable paths) of the path-days over the entire month were asymmetric by greater than 5 milliseconds. Therefore, the majority of the paths were roughly symmetric over the month as measured by propagation delay, but paths were still asymmetric for a significant percentage of days.

Related work

There are a number of related measurement efforts developed concurrently with Surveyor. The most closely related include Vern Paxson's thesis work, the Internet Performance Measurement and Analysis (IPMA) project, the PingER project, the Waikato Applied Network Dynamics (WAND) project, the RIPE Test-Traffic project, and the National Internet Measurement Infrastructure (NIMI) project.

Vern Paxson's thesis work [Paxson96a, Paxson96b, Paxson97a, Paxson97b] deployed Network Probe Daemons at 50 sites throughout the Internet. This study included routing, round-trip delays, and loss measures (as well as a detailed study of TCP dynamics). This groundbreaking study showed asymmetry in routing. It also showed the problems with using daemons that reside on general-purpose workstations, where the load cannot be controlled and whose time could only be synchronized by Network Time Protocol. Surveyor uses dedicated machines with GPS hardware for time synchronization and central management.

The routing protocol collectors of the IPMA project [Labovitz*99] are a wide-area deployment of measurement daemons. These daemons keep track of routing protocol updates to understand the dynamic routing behavior in the Internet. Surveyor measures path routing, but only instantaneously, using a slightly modified traceroute program.

The PingER project [Matthews*98, Cottrell98] deploys software to monitoring sites throughout the high-energy physics research community. It, too, aims to make consistent, long-running measurements. Surveyor measures unidirectional delay and loss instead of round-trip delay and loss. Surveyor and PingER also use different measurement schedules: PingER sends a series of ICMP echo request messages grouped together on a fixed schedule; Surveyor constantly sends out small UDP packets on a Poisson schedule.

The WAND project has made some unidirectional latency and loss measurements. [Graham*98a, Graham*98b]. Like Surveyor, WAND uses GPS to synchronize clocks. Unlike Surveyor, WAND can capture packets passively. In particular, it was designed to capture ATM cells passively, recording a timestamp and signature of each cell. These signatures can be correlated offline to find one-way delays accurate to 10 nanoseconds. In the WAND project, an Ethernet interface that uses the same technique has been developed, and an IP packet-over-SONET interface. Surveyor uses active measurements and thus does not have to address the problems of capturing user data.

The RIPE Test-Traffic project [RIPETT] is the project most similar to Surveyor. It, too, is an implementation of the IETF IPPM one-way delay and loss metrics. Its scope is the European networks that cooperate with RIPE. This is an important project, because multiple implementations of the same metric help to validate both the metric and each other's findings.

NIMI [Adams*98, Paxson*98] is a general measurement infrastructure that is intended to form a ubiquitous platform for network measurements. The prototype NIMI implements round-trip delay, loss, and unidirectional routing measurements. NIMI intends to synchronize its clocks closely enough to perform the IPPM one-way delay metrics. If NIMI becomes ubiquitous, the Surveyor measurements could be implemented as one of many measurements performed by NIMI.

Conclusion and future work

We have presented our architecture for performing accurate measurements using sound, generally recognized methodologies. Our measurement infrastructure, Surveyor, is currently deployed at 41 research and education sites, with another 20 deployments currently under way. We have been taking consistent measurements beginning with our first two sites in mid-1997 and so far have stored every measurement taken.

Our experience to date has shown the utility of one-way measurements as opposed to round-trip measurements. We see many instances in which the forward and reverse paths are different. We are able to isolate changes in minimum delay, variation in delay, or loss to particular paths.

We are working on three areas for the future. First, there are some promising near-term deployments. We are placing Surveyor measurement machines in the middle of the Abilene network, which will give us an opportunity to examine piecewise paths. We have also modified the software to send out test packets with the Differentiated Services byte set to test quality-of-service-enhanced paths. We will be deploying measurement machines inside the QBone testbed. We have also been approached about measuring IPv6 or multicast paths. Second, we are working on some new reporting techniques -- in particular, Simple Network Management Protocol alerts to flag "interesting" paths, and more general near-real-time access. Both of these techniques will help network operators. Finally, we are working on some new analyses of the data. Although the daily reports are useful, we are collecting some unique data that will allow more detailed analyses. In addition, we are contemplating additional measurements among our machines to aid in new analyses, such as sending variable-sized packets or packet trains or simply recording the TTL value of received measurement packets.

References

Adams*98
A. Adams, J. Mahdavi, M. Mathis, and V. Paxson, "Creating a Scalable Architecture for Internet Measurement," Proc. INET '98, 1998.
Almes*98a
G. Almes, S. Kalidindi, and M. Zekauskas, "A One-way Delay Metric for IPPM," work in progress, Dec. 1998.
Almes*98b
G. Almes, S. Kalidindi, and M. Zekauskas, "A One-way Loss Metric for IPPM," work in progress, Dec. 1998.
Brownlee98
N. Brownlee, University of Auckland, personal communication.
Graham*98a
I. D. Graham, S. F. Donnelly, S. Martin, J. Martens, and J. G. Cleary, "Nonintrusive and Accurate Measurement of Unidirectional Delay and Delay Variation on the Internet," Proc. INET '98, Jul. 1998.
Graham*98b
I. D. Graham, et al., Waikato Applied Network Dynamics (WAND) Project homepage, http://atm.cs.waikato.ac.nz/wand/, 1998.
Mathis*97
M. Mathis, J. Semke, J. Mahdavi, and T. Ott, "The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm," Computer Communication Review, Vol. 27, No. 3, Jul. 1997.
Cottrell98
L. Cottrell, "PingER Tools," http://www.slac.stanford.edu/xorg/icfa/ntf/tool.html, May 1998.
Jacobson89
V. Jacobson, traceroute, ftp://ftp.ee.lbl.gov/traceroute.tar.Z, 1989.
Labovitz*99
C. Labovitz, et al., "The Internet Performance and Analysis Project," http://www.merit.edu/ipma/.
Matthews*98
W. A. Matthews, R. L. A. Cottrell, and D. E. Martin, "Internet Monitoring in the HEP Community," Proceedings of Computing in High Energy Physics 1998 (CHEP98), Aug. 1998.
Padhye*98
J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, "Modelling TCP Throughput: A Simple Model and its Empirical Validation," Proc. SIGCOMM '98, pp. 303-314, September 1998.
Paxson96a
V. Paxson, "Towards a Framework for Defining Internet Performance Metrics," Proc. INET '96, Montreal, 1996.
Paxson96b
V. Paxson, "End-to-End Routing Behavior in the Internet," Proc. SIGCOMM '96, Stanford, Aug. 1996.
Paxson97a
V. Paxson, "Measurement and Analysis of End-to-End Internet Dynamics," Ph.D. Thesis, University of California, Berkeley, UCB-CSD-97-945, 1997.
Paxson97b
V. Paxson, "End-to-End Internet Packet Dynamics," Proc. SIGCOMM '97, Cannes, France, Sep. 1997.
Paxson*98
V. Paxson, J. Mahdavi, A. Adams, and M. Mathis, "An Architecture for Large-Scale Internet Measurement," IEEE Communications, Vol. 36, No. 8, Aug. 1998.
RIPETT
RIPE Network Coordination Centre, Test Traffic Project Homepage http://www.ripe.net/test-traffic/index.html.

[INET'99] [ Up ][Prev][Next]