Network Measurement 

Get Complete Project Material File(s) Now! »

CHAPTER 2 Literature Review

In this chapter, we describe the motivation for the develop-ment of our beacon software, and follow this up with dis-cussions on network measurement methods.
One of the problems associated with the growth of the Internet is network con-gestion. As the number of hosts increases, the amount of tra c emitted by routers increases accordingly. As a result, router queues vary signi cantly in length and can at times ll up completely. This causes variations in the arrival time of packets (jitter). As packets continue to arrive at the queue, routers are forced to perform tail drop on the queue causing packet loss.
In the event of congestion, applications that uses TCP as a transport protocol experience degraded performance because the TCP protocol was not designed for high latency networks (see queue oscillation [10, 11, 12] on Chapter 11). Responding to packet loss and jitter, network measurement tools were developed to monitor networks and to provide appropriate solution for packet loss and jitter. In this chapter, we will discuss some of the active measurement tools and studies using them.
There are two methods to monitor a network; passive and active measure-ments [13]. The di erence between the two methods is that passive measurement
records information from the ow of existing packets.
In contrast, active measurement introduces arti cial tra c into the network for the purpose of monitoring the impact of router queue and routing behaviour on the transmission of packets.

 Passive Measurement

Passive measurement is the process of monitoring the status of networks without modifying or introducing any tra c. The monitoring process may involve the use of network interface status, tra c load in routers, length of queues, and routing tables to assess the current state of a network [13].
There exist two models of passive measurement. Firstly, there is the pull model used in the Simple Network Measurement Protocol (SNMP) [14]. In this model, SNMP requires the installation of a hierarchical database known as the management information base (MIB) [15]. After the installation of the MIB in a server (SNMP manager), the MIB pulls metrics such as platform resource utilisation, network tra c, and error counts [16] from routers/switches and stores them as records.
In the second approach, passive measurement utilities such as NTOP [17] with Nprobe [18], or Cisco net ow [19] use the push model for monitoring tra c. In this model, a device known as net ow/IPFIX collector records information seen on a network interface, such as the IP address, network/application layer protocols, and inter-arrival time of packets.
There are two ways to install a collector. It can be activated on a Cisco switch/router with switched port analyser (SPAN) and related net ow com-mands [20], or it can be installed in a dedicated machine. A good example of such a method is the installation of Nprobe with various con gurations of IPFIX templates [21] to intercept and classify tra c into characteristics such as the tra c utilisation of hosts, access attempts from external IP addresses etc.
The results from tra c classi cation are also exportable into analysis applica-tions such as NTOP that display information in the form of graphs and tables. Despite the di erences between the above models, passive measurement utilities monitor and capture information for reporting on events such as the current net-work load, network congestion, malicious activities, and packet errors. In this thesis, we use NTOP and Nprobe to gain satellite link utilisation information on Tuvalu (see Chapter 11).

Active Measurement

Active measurement generally involves the exchange of arti cially generated traf-c between hosts. During the exchange process, one of the host transmits tra c whereas the other host awaits the arrival of packets. Using the IP address to identify the transmitting host, a port number to identify the service, and a serial number to identify packets, the receiving node records information such as the amount of data, the receive time of packets, information from packet headers, and the number of packets that were received.
By processing this information, one can observe characteristics in networks such as bandwidth, link capacity, delay variation (jitter), packet loss, changes in path, and out-of-order arrivals of packets. Examples of active measurement utilities will be discussed in Section 2.4 of this chapter.
Our research was motivated by a number of standards. Firstly the standards on One-way Active Measurement Protocol (OWAMP) [22] and Two-way Active Mea-surement Protocol (TWAMP) [23] provided a step by step guide on unidirectional and bidirectional active measurement. The two standards were also adopted in the active measurement tool OWAMP, and we discuss the details of this tool in Sec-tion 2.4. Moreover, we use the de nition in the IP Performance Metrics (IPPM) standard [24] to discuss jitter in Chapter 5.
Developed by the IPPM working group of the Internet Engineering Task Force (IETF), the Surveyor utility is capable of measuring end-to-end one-way delay [25], packet loss [26], and route information along Internet paths [27]. This tool uses Jacobson’s modi ed version of the Traceroute utiltiy [28] and a GPS corrected clock to measure one-way delay and loss. Data generated from Surveyor are archived into a repository server for further processing. In their website [27], the authors provide results on changes in the path of packets, asymmetry in routes, and the performance of high-speed research networks. Note that our software uses the method in the standards [25, 26] for our unidirectional experiments.
Based on the standards [29, 30, 31], the Regional Internet Registry (RIR) for the European region (RIPE NCC) developed a global network of measurement hosts known as Test Tra c Measurement Service (TTMS) project [32]. As described in their website, TTMS uses dedicated measurement devices (test boxes) that generates tra c with the Ping [33] and Traceroute [34] utilities. The data that is generated from these tools include round trip delay, packet loss rate, and delay variations (jitter). These data are further processed and displayed in graphs for monitoring of networks [35].
In addition, the TTMS project also provide access to a database of routing information that one may use to track changes in the path of packets. These data are also archived for users to be able to perform long term trend analysis. Note that the TTMS project later became the RIPE Atlas [36] project.
Starting with their paper on the proposal for a scalable Internet-wide architec-ture [37], Francis et al. developed the distributed Internet measurement (DIMES) project to measure and disseminate distance information on a global scale. On top of this, they provide open access to their data allowing content service providers to determine suitable locations on the Internet for the placement of content service provider servers.
This results in minimal latency between clients and content service providers. Other uses of the DIMES project include determining available bandwidth, link capacity, packets reordering, and queuing delay [38].
In an attempt to better understand the behaviour and the evolution of the Internet, the Center for Applied Internet Data Analysis (CAIDA) developed the Microscopic project [39] to collect two types of data. Firstly, it collects Internet Protocol (IP) forwarding path information from Traceroute-like active measure-ments. Secondly, this project collects routing information from routing tables of the inter-domain Border Gateway Protocol (BGP).
To collect IP path information, the skitter [40]/scamper [41] tool is installed in the Archipelago measurement infrastructure (Ark) [42] to perform parallel Traceroute-like active measurements into a number of targeted IPv4 or IPv6 ad-dresses. The scamper tool is also con gurable to perform Traceroute with Internet Control Message Protocol (ICMP), TCP, or UDP packets and to discover paths with the maximum transmission unit (MTU) option [43].
In addition, the Microscopic project uses RouteViews [44] to collect information such as inter-domain Autonomous System (AS) paths from BGP routing tables. The BGP information (AS paths and IP addresses) are aggregated into a database that researchers can access for building Internet topologies.
Hosted at research institutions, routing centers (Internet2’s Abilene backbone), and other Internet connected servers, the PlanetLab [45] project is based on a large number of volunteered hosts. These hosts execute a software known as MyPLC which manages activities such as bootstrapping of nodes, distribution of software updates, auditing of systems activity, and for managing user accounts.
The objective of the PlanetLab project is to support distributed virtualisation by enabling an application to run on a slice of PlanetLab’s network-wide hardware resources. Once an application is scheduled on a slice, users can perform short-term experiments with a variety of planetary-scale services such as le sharing and network embedded storage [46], content distribution networks [47, 48], routing and multicast overlays [49], Quality of Service (QoS) overlays [50], scalable object loca-tion [51], anomaly detection [52], and network measurement [53].
On top of this, the PlanetLab project o ers researchers real world experience with path characteristics such as congestion, link failures, and other link behaviour. The nodes can be con gured to perform long term measurement with services such as CoDEEN [47], Coral CDN [48], the ScriptRoute network measurement service [54], Chord [55] and OpenDHT [56] scalable object location services, and the PIER [57] network monitoring services.
In spite of the bene ts provided by these studies/projects, we did not use them for the following reasons;
Firstly, the objective of most of these projects focus on tracing reach-ability of hosts and mapping the path of packets on a hop by hop basis. However, our objective is to nd out the impact of jitter, packet loss and out-of-order arrivals on the performance of VoIP and other real-time applications. Secondly, the use of most of the tools in these projects requires full administrative control of nodes to run their software. However we generally do not have this permission.
Furthermore, some of these projects employ the virtualisation concept (e.g.) PlanetLab uses virtualisation technologies that enable users to share hardware re-sources such as memory and real-time clock. This is a problem because the sharing of resources introduces delay when we require access to real-time clock for timestamp-ing purpose. In addition, PlanetLab nodes run many other di erent experiments, and there is possibility for other experiments to interfere with our experiments.
In addition, most of these projects run on academic networks. For example, Cla y et al. [58] pointed out that a typical PlanetLab network consists of research networks where most of the packets travel through non-commercial backbone links. As a result, any information observed may not re ect the experience of packets on commercial networks.
Lastly, most of the nodes have limited resources. For example, a PlanetLab node sometimes use capped bandwidth, and limited processor time and storage capacity [58]. This may restrict the type of experiments that we can perform.
One thing that is common among many existing network measurement projects, is that they use a variant of Ping or Traceroute to perform active measurement. We presents the functionality of some of these tools in Section .

Limitations of Passive and Active

Measurement Methods

In order to measure anything in any given scenario, there needs to be tra c to measure. Our research questions (which will be discussed in the next chapter) look at scenarios where two nodes are separated by long distance paths. Normally we would not expect tra c between those nodes to occur naturally. Even where such tra c occurs it may not be on a regular basis. Moreover, even if there is tra c on a regular basis it may be di cult to put probes on or near the nodes because we do not control most networks of interest. In the context of passive measurement, we would thus expect little or no tra c unless we generate any.
A common deployment scenario for passive measurement is a local network where one has control of the network infrastructure for installing/activating monitoring probes. Because there is no control over the generation of network tra c, users of passive measurement are unable to control the transmit time of packets, the time di erence between the transmitting node and the monitoring probe, the total number of transmitted packets, and the intertransmission time of packets.
Without this information, one cannot use passive measurement together with the UDP protocol to determine characteristics such as latency, jitter, MOS, packet loss, and out of order arrivals. However path characteristics including some types of jitter, out of order arrivals, length of the path taken by packets, and bu er time/size requirements can be measured or estimated for the TCP protocol.
We thus decided to use active measurement for the following reasons: Firstly, it lets us place nodes in networks we have no control over, and the probe position in the network topology is not so important. Secondly, we can collect timing and other information at the transmitting node which we can use to determine char-acteristics including MOS, latency, jitter, packet loss, and order of packet arrival. In addition, we can probe the network with standardised TCP tra c to determine bu er time/size requirements.
One drawback of active network measurement is that the generated tra c may interfere with existing production tra c, which is a limitation for low bandwidth networks such as the satellite network we encountered in the Paci c. This prevented us from doing extensive TCP/NC download series experiments in some of the islands, e.g., Niue and Tuvalu.

Measurement Tools

Ping [33]: Ping uses ICMP to determine the round trip time (RTT) and the number of hops between nodes. The source sends small packets of 64 bytes (56 bytes of data and 8 bytes protocol information) known as ICMP echo requests to the destination and awaits ICMP echo responses from the destination. If there is a response, the destination host is declared reachable. The source also obtains information such as round trip time (RTT), packet loss, and the number of hops from the ICMP response.
Traceroute [59]: Traceroute uses UDP, TCP, and ICMP to determine the path taken by packets and the routers that forward packets between hosts. It sends a sequence of packets from the source to the destination. The packets contain a TTL [60] value that the application gradually increases at every transmission, starting from 1.
Every router reduces the TTL value by 1. When the application transmits the rst packet, the TTL value will be 1. The rst packet reaches the rst router, the router decrements the TTL value to 0 and drops the packet.
When a router drops the packet, it sends an ICMP time exceeded message back to the source. The source increases the TTL value to 2 and transmits the next packet. However this time the packet will be forwarded between the rst and second router, where the TTL value reaches 0. The second router drop the packet and reports back to the source with an ICMP time exceeded message. The application repeats this process until one of the transmissions reaches the destination. The end result of this process is the mapping of the likely path from source to destination, and the recording of the routers that have processed the transmitted packets.
Pathchar [61]: Pathchar also uses UDP and ICMP to infer the characteristics of individual links along an Internet path by measuring the RTT of packets. The RTT here is the time it takes for packets to travel from source to a router along the path and back to the source. Like Traceroute, Pathchar takes advantage of the TTL value of packets (using the ICMP time exceeded), to determine how many links a packet can traverse before the TTL value reaches zero and a router drops the packet.
Pathchar sends series of varying numbers of packets and varying packet sizes and measures the time until the source receives an ICMP time exceeded mes-sage from a router along the path [62]. By performing statistical analysis on the time until the ICMP message is received, Pathchar is able to determine latency and bandwidth on a link, the distribution of queue lengths and the probability that packets were dropped.
Clink [63]: Clink uses UDP to estimate bandwidth and latency of links be-tween source and destination. It sends large number of UDP packets and measures the RTT. Clink performs functions similar to Pathchar.
Pchar [64]: Pchar uses UDP to estimate bandwidth, latency, and packet loss on links along an end-to-end path. It perform similar functions as Pathchar (open source implementation of Pathchar).
Nettimer [65]: Nettimer uses TCP to estimate capacity in the form of bot-tleneck and available bandwidth, and actively probes the network using the packet-pair ’tailgating’ technique. In the tailgating technique, the source sends two packets within a short time interval between nodes.
While the packets travel from source to destination, they encounter delays from queuing and processing time in routers which change the interval between the packets. Upon arrival of the packets, the destination node records the interval between the packets to determine link capacity and bandwidth.

CHAPTER 1 Introduction 
1.1 Overview
CHAPTER 2 Literature Review 
2.1 Passive Measurement
2.2 Active Measurement
2.3 Limitations of Passive and Active Measurement Methods
2.4 Measurement Tools
CHAPTER 3 Network Measurement 
3.1 Motivation
3.2 Summary
CHAPTER 4 Beacon Software Requirements 
4.1 Functional Requirements
4.2 Denition
4.3 Non-Functional Requirements
4.4 Hardware Requirements
4.5 Summary
CHAPTER 5 Jitter 
5.1 What is Jitter?
5.2 Why Study Jitter?
5.3 Notation
5.4 Estimation of Jitter
5.5 Jitter
5.6 Coping with Jitter
5.7 Summary
CHAPTER 6 Estimation of Network Quality, Voice Quality, and Buer Requirements 
6.1 Motivation
6.2 Notation
6.3 Complexity Measures
6.4 Entropy Estimators
6.5 Mapping of Inter-Arrival Times
6.6 Adaptive Entropy
6.7 Estimated Mean Opinion Score (MOS)
6.8 Voice over TCP
6.9 Summary
CHAPTER 7 Challenges and Limitations 
7.1 Organisational Policy
7.2 Software and Hardware Issues Surrounding Deployments
7.3 Limited Resources
7.4 Limitations of the Software
7.5 Summary
CHAPTER 8 Backup and Processing of Log Files 
8.1 Data Backup Topology
8.2 Log File Processing
8.3 Summary
CHAPTER 9 Results 
9.1 Data Access Methods
9.2 Results
9.3 Summary
CHAPTER 10 Solution for High Latency Satellite Networks
10.1 High Latency and Low Bandwidth Networks
10.2 Network Coding (NC)
10.3 Deployment of TCP/NC
10.4 Summary
CHAPTER 11 TCP/NC Implementation Challenges and Results
11.1 Implementation Challenges
11.2 Preliminary Observations
11.3 Results
11.4 Summary
CHAPTER 12 Conclusion
12.1 Open Problems
12.2 Future Work
APPENDIX
GET THE COMPLETE PROJECT