Tomography: traffic measurement/control and topology construction

1. Overview
2. Research Agenda
3. Participants
4. Major Publications
5. Funding Source
6. Related Links

Overview

To facilitate design and development of better resource management protocols, it will be greatly helpful to better understand the dynamic behaviors of Internet traffic and their impacts on the end-to-end path attributes and properties. For example, Internet traffic has been observed to exhibit long range dependency (LRD). While the LRD characteristic of network traffic introduces difficulty and complexity into traffic and resource management, the existence of nontrivial correlation structure at larger time scales can be judiciously exploited for better congestion and resource control. Similarly, discovery of Internet topology also has many advantages for design and deployment of topology sensitive services and applications, such as nearby server selection, overlay network construction, routing path construction, and peer-to-peer computing. The knowledge of network topology enables each host in these systems to make better decisions by exploiting its topological relations with other hosts. This project thus aims to address the following three issues: 

(i) How to perform non-intrusive, accurate, active/passive traffic measurement to better understand the nature of the traffic and to infer relevant network attributes; 

(ii) how to model, detect, and exploit the abundant correlation structure to improve the performance of resource and traffic control mechanisms; and 

(iii) how to estimate the network distance between arbitrary hosts without direct measurement between these hosts.

Research Agenda (click here for details)

To address the above issues, we are carrying out R&D work in the following thrusts: 

(1). Hierarchical model for Internet traffic 
(2). Active and passive measurement (new, unfunded) 
(3). Constructing Internet coordinate systems (new, unfunded) 
(4). Resource control that exploits long range dependency

Participants

• Yuan Gao (Ph.D. 2002) 
• Guanghui He (Postdoc 2004-2005; Ph.D. 2004) 
• Hyuk Lim (Postdoc 2003-2006)

Major Publications

1. Yuan Gao, Guanghui He, and Jennifer C. Hou, ``On leveraging traffic predictability in active queue management,'' Proc. IEEE INFOCOM 2002, June 2002 (11 pages, acceptance ratio = ~20.5%). 
2. Guanghui He, Yuan Gao, Jennifer C. Hou, and Kihong Park, ``A case for exploiting self-similarity of Internet traffic in TCP congestion control,'' Proc. 10th IEEE Int'l Conf. on Network Protocols (ICNP'02), November 2002 (acceptance ratio = ~15%). 
3. Yuan Gao and Jennifer C. Hou, ``A state feedback control approach to stablizing AQM queues for ECN-enabled TCP connections,'' Proc. IEEE INFOCOM 2003, April 2003 (acceptance ratio = ~21%). 
4. Guanghui He and Jennifer C. Hou, ``On exploiting long range dependency in measuring cross traffic,'' Proc. IEEE INFOCOM 2003, April 2003 (acceptance ratio = ~21%). 
5. Hyuk Lim, Jennifer C. Hou, and Chong-ho Choi, ``Constructing an Internet coordinate system based on delay measurement,'' Proc. ACM Internet measurement conference, October 2003 (acceptance ratio = ~29%; one of the four manuscripts forwarded to ACM/IEEE Trans. on Networking for fast track publication). 
6. Guanghui He, Yuan Gao, Jennifer C. Hou, and Kihong Park, ``On exploiting self-similarity of Internet traffic in TCP congestion control,'' Elsevier Computer Networks, Volume 45, Issue 6, pp. 743--766, August 2004.
7. Hyuk Lim, Jennifer C. Hou, and Chong-ho Choi, ``Constructing Internet coordinate system based on delay measurement,'' IEEE Trans. on Networking, Vol. 13, No. 3, pp. 513-526, June 2005.
8. Guanghui He and Jennifer C. Hou, ``An in-depth, analytical study of sampling techniques for self-similar Internet traffic,'' IEEE Int'l Conf. on Distributed Computing Systems (ICDCS'05), June 2005 (acceptance ratio = 14%).
9. Guanghui He and Jennifer C. Hou, "On sampling self-simiar Internet traffic," Elsevier Computer Networks, Vol. 50, No. 14, pp. 2919-2936, November 2006.
10. Guanghui He, Jennifer C. Hou, Wei-Peng Chen, and Takeo Hamada, ``One size does not fit all: a detailed analysis and modeling of P2P traffic,'' Proc. of IEEE Globecom, November 2007 (acceptance ratio = 30%).
11. Guanghui He, Jennifer C. Hou, Wei-Peng Chen, and Takeo Hamada, ``Characterizing individual user behaviors in WLANs,'' ACM/IEEE 10th International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM'07), November 2007 (acceptance rate = 40/161 = 25%).
12. Hyuk Lim and Jennifer C. Hou, "Identifying Lossy Links in Wired/Wireless Networks: Problem, Solution, and Empirical Evaluation," Proc. of Third Annual International Wireless Internet Conference (WICON'07), October 2007 (invited).
13. Hyuk Lim and Jennifer C. Hou, ``Identifying lossy links in wired and wireless networks by exploiting sparse characteristics,'' Elsevier Computer Networks, to appear (accepted in May 2007).
14. Hyuk Lim and Jennifer C. Hou, ``End to end measurement of available bandwidth based on a packet pair delay model,'' submitted to Computer Networks, November 2006  

Demo and Software Release

(1) End-to-end available bandwidth measurement: bTrack
(2) End-to-end cross traffic measurement.

Funding Source

Related Links

Detailed Description of Research Agenda

The seminal work of Leland et al. has laid the groundwork for understanding the self-similarity nature of Internet traffic and its impact on network performance. Since then, significant efforts have been made to track down the origin of self-similarity in network traffic. Part of the research along this direction has primarily focused on application level dynamics (e.g., file size) and human factors (e.g., human thinking time) that may contribute to LRD. Not until recently have protocol and network dynamics been studied as possible causes of LRD in network traffic. 

While LRD or self-similarity (a.k.a. mono-fractal scaling) is characterized by a single scaling law that holds globally in time and essentially involves only one parameter --- the Hurst parameter, multifractal scaling allows for time-dependent scaling laws and hence offers great flexibility in describing irregular phenomena that are local in time. The latter is typically caused by network-specific mechanisms that operate at small time scales and, depending on the state of the network, can have a more or less severe impact on packet dynamics within individual connections. In a first attempt to allow for a more complete description of network traffic, Riedi et al. and Ribeiro et al. presented traffic models with additive and multiplicative structures. Pursuing in the wavelet domain, they analyze, based on binomial cascades, a multiplicative model that exhibits the multifractal property of network traffic at small time scales and matches the LRD property at large time scales. In essence, cascade models attempt to account for multifractality by viewing networks together with their protocols and controls as a process that fragments units of information in one layer in the networking hierarchy into smaller units in the next layer. 

Although cascade models are well-suited in explaining multifractality, they lack in the explicit physical meaning in reflecting network protocols (from the application layer to the physical layer) to the corresponding cascade models. In this part of the project, we propose a simple hierarchical model that has an one-on-one correspondence to protocols in the protocol hierarchy of IP networks. We envision the traffic governed by protocols as hierarchical on/off processes. At the up-most level, the hierarchical model is an ON/OFF model with an ON period corresponding to the active period induced by, for example, a HTTP request and an OFF period to the user's thinking time. Each ON period is, in turn, composed of one or more level-1 on and off periods, with an level-1 on period corresponding to a TCP connection for transmitting embedded object(s) and an off period to the time incurred in three-way handshaking and other processing delays. Each level-1 on period is, in turn, composed of TCP slow start, congestion avoidance, and timeout/exponential back-off phases and hence can be further decomposed into level-2 on and off periods. In essence, an on period that corresponds to the active period in a protocol layer can be decomposed into smaller on and off periods to account for activities carried out in the lower protocol layer. 

We validate the hierarchical model with traces gathered at IRCache.net and Lucent Technologies Bell Labs. In particular, we identify all the ON/OFF period and level-1/level-2 on/off periods within the traces and fit them into heavy tailed distributions. We prove via analytic derivation and empirical studies that this simple model does exhibit LRD and multifractality. Finally, we analyze the queuing behavior of a fluid queuing system with this hierarchical model as input and prove that in the long run, multifractal traffic has the potential of causing heavier queuing tails than mono-fractal traffic. To the best of our knowledge, this is the first work that links protocol behaviors in the protocol stack with ON/OFF models in a natural way and thus provides a vehicle to mathematically studying the causes of long range dependence across the protocol stack. 

Figure1: The incoming traffic in the first 40 second period of the trace (a). Each spark/bar corresponds to a TCP connection. The dense spark/bar areas are indentified as level-0 ON periods. (b) gives an enlarged view of the same trace in [0,7] second. The level-0 ON period approximately around 5 second consists of four smaller level-1 on/off periods. 

(2). Active and passive measurement 

Active measurement

To measure network attributes such as the available bandwidth along a path, the amount of cross traffic, and the packet loss rate along a path, on an end-to-end basis, one usually injects one or more unicast/ multicast probe packets, measures/records either (i) their round trip time (as in the one-packet technique) or (ii) the difference in the arrival times of two consecutive packets (as in the packet-pair techniques), and uses the measurement results to infer the network attribute of interest. 

The major problem associated with existing mechanisms is that they rest on one or more of the following assumptions: (i) there is at most one bottleneck link on the path; (ii) the cross traffic either does not exist or has a minimal impact on probe packets; and (iii) the queuing effect of probe packets on links other than the link under measurement can be ignored. As these assumptions may not hold in reality, the results obtained using the existing approaches are often unsatisfactory. How to ensure the measurement method is accurate, yet non-intrusive (i.e., neither introduces a significant amount of probe packets into the network nor interferes other traffic on the path), and can adapt to dynamic traffic/system changes is crucial to obtaining a comprehensive view of the networked system. 

We are advancing the research frontier along this avenue by (1) Devising an end-to-end measurement mechanism that does not rely on the aforementioned assumptions: We have devised a deterministic model for using the packet pair technique to measure the available bandwidth on an end-to-end path. This model does not rely on any of the above assumptions and characterizes accurately the relation between the inter departure time of probe packets in a packet pair at a sender and their inter arrival time at a receiver. In non-decreasing, piecewise linear function of the inter-departure time on a multiple-hop path. 

Specifically, consider M links on an end-to-end path. Let C_i and r_i denote, respectively, the link capacity and the amount of cross traffic on the i^th link. Furthermore, let T_i denote the inter departure time from the i^th queue. Then the inter departure time T_i becomes the inter arrival time at the (i+1)^th queue, and T_in = T₀ and T_out = T_M. Let q_i denote the queue length when the first probe packet arrives at the i^th queue, u_i = r_i / C_i denote the link utilization by cross traffic, and T^*_i = (L + q_i)/(C_i-r_i) denote the characteristic function. Assume that the s_th queue has the minimum available bandwidth on the path (i.e., s = arg min_i (C_i - r_i)). If T_in is greater than the second largest characteristic value on the path, then T_out can be derived as
T_out = u_s T_in + L / C_s - u_s sum^s-1_i=1( q_i / C_i ) + sum^M_i=s+1( q_i / C_i ),   if T_in < T^*_s + sum^s-1_i=1( q_i / C_i ),
       = T_in - sum^M_i=1( q_i / C_i ),  otherwise.

Note that T_out is a piecewise increasing linear function of T_in with two different slopes u_s and 1. The value of T_in at which the slope of T_out changes depends on q_i's (i.e., the queue size when the last bit of the first probe packet arrives at every queue). 

Based on the above deterministic packet pair model, we will devise an end-to-end measurement mechanism, called btrack, to track the available bandwidth on a path. Ideally the available bandwidth on an end-to-end path can be measured by searching for the largest characteristic value. However, this value depends on both the size of probe packets and the number of packets accumulated at the queues along the path, and the latter may not be readily available. Instead of using characteristic values, we propose to use the relative distance between two characteristic values of two pairs of probe packet of different packet sizes. The sender transmits two pairs of probe packets of different sizes L_a and L_b to the receiver. After measuring the inter-arrival times of the two pairs of probe packets, the receiver estimates the available bandwidth on the end-to-end path via D = T^*_a - T^*_b = (C_s - r_s) / (L_a - L_b). Note that D is a function of the difference in the packet sizes of probe packets and the available bandwidth. The effect of queuing delay on the end-to-end path (q_i's) is cancelled out. 

Btrack will be non-intrusive and the bandwidth consumed by the probing traffic will be small, independent of the value of the available bandwidth and can be adjusted by varying the probing period and the packet sizes of probe packets. We will complete the detailed design and implement btrack in the Linux kernel. We will also empirically evaluate the performance of btrack against other existing tools (e.g., pathload) first on a well-controlled campus network (so that results can be validated) and then on the Internet. Finally, we will integrate btrack into the user-level protocol stack library so as to provide another dimension of network attributes that are otherwise not available in the stack library. 

Passive Measurement 

In addition to employing end-host-based, active measurement methods, we will also investigate, in collaboration with Dr. Bill Cleveland at Purdue University, packet-sampling-based passive measurement methods. The packets that arrive on a link are time-stamped, and their headers are captured. This can be accomplished by a passive device attached to the link. 

Packet traces collected through sampling provide not only a view of the link where the device is attached, but substantial information about a view across the Internet along all of the paths taken by the connections whose packets use the link. For example, consider the three-way handshake that opens a TCP connection. The first SYN packet arrives at the monitored link, is time-stamped, and then proceeds to the server. The server immediately sends a SYN/ACK packet that arrives at the link, is time-stamped, and proceeds to the client. The client immediately sends an ACK packet that arrives at the link, is time-stamped, and proceeds to the server. The time between the SYN time-stamp and the SYN/ACK time-stamp is a measure of the round-trip time between the link and the server. Similarly, the time between the SYN/ACK time-stamp and the ACK time-stamp gives the round-trip time between the link and the client. Studying the round-trip times through time gives information about congestion along the respective paths. Note that not all packets will be measured; instead statistical sampling methods will be devised to select packets for capture. The sampling will, however, be based in part on the packet contents (otherwise, the above round-trip time measurement example will not work). This can be accomplished by reading certain fields in the packet header, and then (1) selecting candidate packets based on these fields and (2) sampling a fraction of those candidate packets whose hash values are in certain intervals. 

We will also implement a set of rules to perform trajectory sampling, meaning that packets on a network are randomly sampled, and once a packet is selected for sampling it is collected and time-stamped at each ingress router line card where it appears. In this fashion, the trajectory of the packet through the network from the initial ingress port until it reaches the final egress port can be observed. The sampled packet fully characterizes the path in terms of delay and jitter, allows verification of routing decisions, and provides input to traffic engineering algorithms. If an end host complains of excessive delay or jitter, packet sampling can verify whether or not the problem exists and isolate it to a particular node in the network. Trajectory sampling can also be used to generate actual traffic matrices for each node of the network, and provides a measure of not only the bandwidth used on each link, but also the source and destination of traffic through every router in the network. We will evaluate the promise thoroughly, compare it with active measurement methods, and provide measurement results to the measurement and diagnostics system at an end-host so as to augment the dimension of network attributes available for network diagnostics. 

(3). Constructing Internet coordinate systems 

In this part of the project, we focus on topology construction based on end-to-end delay (round-trip time) measurement, and use the term "network distance" for the round-trip time between two hosts. The primary goal of constructing network topology is to enable estimation of the network distance between arbitrary hosts without direct measurement between these hosts. Several approaches have been proposed, among which IDMaps and GNP may have received the most attention. Both assume a common architecture that consists of a small number of well-positioned infrastructure nodes (called beacon nodes). Every beacon node measures its distances to all the other beacon nodes and uses these measurement results to infer the network topology. A host estimates its distance to the other ordinary hosts by measuring its distances to beacon nodes (rather than to the other hosts). A host benefits from using this architecture, as it needs only to perform a small number of measurements and will be able to infer its network distance to a large number of hosts (such as servers). 

One important issue in realizing these measurement architectures is how to represent the location of a host. IDMaps and Hotz's triangulation, for example, use the original distances to beacon nodes to represent the location of a host, while GNP transforms the original distance data space into a Cartesian coordinate system and uses coordinates in the coordinate system to represent the location. The major advantage of representing network distances in a coordinate system is that it enables extraction of topological information from the measured network distance data. As a result, the accuracy in estimating the distance between two arbitrary hosts will be improved. This is especially true when the number of available beacon nodes is small. To this end, we present a new coordinate system called the Internet Coordinate System (ICS). The distances from a host to beacon nodes are expressed as a distance vector, where the dimension of the distance vector is equal to the number of beacon nodes. As each beacon node defines an axis in the distance data space, the bases may be correlated. We apply the principal component analysis (PCA) to projects the distance data space into a new, uncorrelated and orthogonal Cartesian coordinate system of (much) smaller dimensions. The linear transformation essentially extracts topology information from delay measurements between beacon nodes and retains it in a new coordinate system. By taking the first several principal components (obtained in PCA) as the bases, we can construct the Cartesian coordinate system of smaller dimensions while retaining as much topology information as possible. 

Based on the PCA-derived Cartesian coordinate system, we then propose a method to estimate the network distance between arbitrary hosts on the Internet. The network distances between beacon nodes are first analyzed to retrieve the principal components. The first several components are scaled by a factor (such that the Euclidean distances in the new coordinate system approximate the measured distances) and used as the new bases in the coordinate system. The coordinate of a host is then determined by multiplying its original distance vector to (a subset of) beacon nodes with the linear transformation matrix consisting of the principal components. As compared to GNP, ICS is computationally more efficient because it only requires linear algebra operations. In addition, the location of a host is uniquely determined in the coordinate system. Another advantage of ICS is that it incurs smaller measurement overhead, as a host does not have to make delay measurement to all the beacon nodes, but only to a subset of beacon nodes. This is especially desirable in the case that some of the beacon nodes are not available (due to transient network partition and/or node failure). Finally, we show via Internet experimentation with real-life data sets that ICS is robust and accurate, regardless of the number of beacon nodes (as long as it exceeds certain threshold) and the complexity of network topology. 

(4). Resource control that exploits long range dependency 

Analytical and empirical studies have shown that self-similar traffic can have a detrimental impact on network performance including amplified queuing delay and packet loss ratio. On the flip side, the ubiquity of scale-invariant burstiness observed across diverse networking contexts can be exploited to better design resource control algorithms. 

In this part of the project, we have investigated the issue of exploiting traffic predictability to enhance the performance of active queue management (AQM) and to improve the throughput attainable by TCP connections. We have shown that the correlation structure present in long-range dependent traffic can be detected on-line and used to accurately predict the future traffic. To this end, we have designed and introduced two non-model-based traffic predictors: LMMSE and simple. 

Figure 2: Packet drop probability as a function of current queue size and predicted incoming traffic 

Then we figure in, with the objective of stabling the instantaneous queue length, the prediction results in the calculation of the packet dropping probability. The resulting scheme is termed as predictive AQM (PAQM). Through analytical reasoning, we show that PAQM is a generalized version of random early detection (RED) that takes the future arrival rate as a new dimension of congestion index. By stabilizing the queue at a desirable level with consideration of future traffic, PAQM enables the link capacity to be fully utilized, while not incurring excessive packet loss ratio. Through ns-2 simulation, we have compared PAQM against existing AQM schemes with respect to different performance criteria, and shown that under most cases PAQM outperforms stabilized RED (SRED) in stabilizing the instantaneous queue length, and adaptive virtual queue (AVQ) in reducing packet loss ratio and better utilizing the link capacity. 

Figure 3: The phase plot that illustrates how fairness is achieved in the case that N connections traverse a bottleneck link. A TCP connection usually goes through several AI and MD phases, and follows the dashed line to reach the optimal operational point. If the optimal operational point can be accurately predicted, a TCP connection may follow the solid line and directly go to the point in one round trip time without incurring packet losses. 

Along a similar line of reasoning, we have devised an novel scheme, called TCP with traffic prediction (TCP-TP), that exploits the prediction result to infer, in the context of AIMD steady-state dynamics, the optimal operational point at which a TCP connection should operate. Specifically, as shown in the phase plot in Figure 3, the optimal operational point of N TCP connections sharing the capacity, C, of a bottleneck link is the interaction of line f + B =C and line f/B= 1/(N-1), where f and B are the throughput attained by the TCP connection of interest and the other N-1 connections (which are taken as background traffic). Without traffic prediction, a TCP connection usually reaches the optimal point through several additive increase (AI) and multiplicative decrease (MD) phases (Figure 3). With accurate traffic prediction, we show that if all TCP connections are synchronized in making their congestion control decisions, a TCP connection can reach the optimal point in one RTT without commencing MD phases (and hence without incurring packet losses). This leads to significant performance improvement in terms of fast convergence to the optimal operational point, packet loss rate, and attainable throughput. 

In the case of existence of prediction errors, we show via phase plots that with the use of the MD phase, TCP-TP can still retain the stability established in the AIMD algorithm. Moreover, we analyze rigorously the the impact of prediction errors on fairness, and show when the prediction error is 100% (i.e., the predicted value is twice as large as the original value), the index of fairness only degrades 2.5%. Finally we demonstrate the change needed to incorporate the traffic prediction extension into TCP is minimal (tens of lines of code changes) by implementing TCP-TP both in FreeBSD 4.1 and conducting experiments. In the case that TCP connections do not synchronize in window adjustment and are subject to different RTTs, we show via simulation and FreeBSD implementation and experimentation that both TCP and TCP-TP cannot achieve fairness, but a TCP-TP connection still performs better than TCP (67% improvement in terms of packet loss ratio).