Study of Proposed Internet Congestion Control Mechanisms NIST

Mills, et al. Special Publication 500-282 iii 

Acknowledgments 

The foundation for this work began in 2000, when Jian Yuan, now an associate professor 

in the department of electronic engineering at Tsinghua University, arrived at the 

National Institute for Standards and Technology (NIST) to begin four years of 

collaboration with Kevin Mills. Dr. Yuan introduced to NIST the idea of viewing large 

communication networks as complex systems, and worked together with Dr. Mills to 

explore the implications of investigating the Internet as a complex system. During that 

time, Dr. Yuan developed a cellular automata model of an Internet-like network, which 

served as the basis from which MesoNet was created. MesoNet is the reduced parameter 

discrete-event simulator used in the experiments reported in this study. The collaboration 

between Drs. Yuan and Mills led to creation of two proposals: (1) to develop a project on 

measurement science for complex information systems and (2) to formulate a complex 

systems research program within the Information Technology Laboratory (ITL) at NIST. 

In 2006, Dr. Mills submitted a project proposal to an internal NIST competition, 

known as innovations in measurement science (IMS), aiming to gain approval from the 

NIST director to apply measurement science to complex information systems. William 

Jeffrey, the NIST director at that time, supported the project proposal, which also found 

favor with Cita Furlani, director of ITL. In parallel, a group of ITL researchers, including 

Chris Dabrowski, Fern Hunt, Vladimir Marbukh and Kevin Mills, proposed the creation 

of an ITL program to study complex systems in general. This second proposal was well 

received by the management team within ITL, which founded a complex systems (CxS) 

program and recruited Sandy Ressler as the program manager. Sandy has provided 

steadfast support to the work documented in this report. In fact, he added resources to the 

project so that we could explore the use of interactive visualization as a tool to reveal 

global behavior in large distributed systems. Further, he regularly attended the biweekly 

project meetings and provided many useful suggestions for improving the content and 

presentation of the work. 

In 2007, while we were exploring potential challenge problems for a measurement 

science of complex systems, Vladimir Marbukh suggested that we consider the collection 

of congestion control algorithms being proposed to augment or replace congestion 

control procedures within the standard transmission control protocol (TCP), which 

operates within every computer connected to the Internet. Ultimately, Vladimir’s 

suggestion led to the study documented in this report. Through the Internet Congestion 

Control Research Group (ICCRG) of the Internet Research Task Force (IRTF), we 

contacted the community of researchers involved in developing future congestion control 

mechanisms for the Internet. Several members of the ICCRG had performed empirical 

studies of selected congestion control algorithms operating within a small topology. 

These empirical results proved invaluable in verifying our models of individual 

congestion control algorithms. Wesley Eddy and Michael Welzl, co-chairs of the ICCRG, 

encouraged us to share our work with the group and provided ample agenda time at 

several meetings for us to first present our methods and later our findings. We also 

appreciate the general support for our work from researchers within the ICCRG 

community, as well as several researchers within the Transport Modeling Research 

Group (TMRG) of the IRTF. 
Study of Proposed Internet Congestion Control Mechanisms NIST

Mills, et al. Special Publication 500-282 iv 

In addition to support from Internet researchers, we also benefited from the work 

of several colleagues who made temporary visits to NIST. For example, Brittany Devine 

worked on the project for three months under the Summer University Research 

Fellowship (SURF) program administered by the National Science Foundation (NSF). 

Brittany contributed prototype code to make measurements on flow groups, as explained 

in Chapter 8. Edward Schwartz, one of the study authors, also worked on the project for 

three months under the SURF program. Ed, now a doctoral student at Carnegie Mellon 

University, developed the initial models of CTCP, FAST, HSTCP, H-TCP and Scalable 

TCP that were used within this study. Ed also conducted some preliminary experiments 

comparing CTCP, FAST and standard TCP under select scenarios. Cedric Houard 

contributed two years of work to the project as a guest scientist visiting from France. 

Specifically, Cedric developed DiVisa, an interactive system for visualizing 

multidimensional data. 

 Supported by these many valuable contributions, the authors produced the current 

report to document a set of methods, models, experiments and findings, which were 

produced largely over the period of 2006-2009. The study encompasses a wide scope and 

substantial breadth, which could not be documented completely in less than 500 pages. 

We are indebted to Christopher Dabrowski and Stefan Leigh, two NIST colleagues who 

made careful, independent readings of the entire report, and who also provided many 

useful suggestions for improving the manuscript. The review provided by Dabrowski and 

Leigh upheld the highest standards of NIST requirements for internal review prior to 

publication. Of course, in a report of such length, scope and depth, errors undoubtedly 

remain. Responsibility for such residual errors lies squarely at the feet of the authors. 

Note: the document cover and chapter dividers contain images generated from the study text with 

http://www.worldle.net/
Study of Proposed Internet Congestion Control Mechanisms NIST

Mills, et al. Special Publication 500-282 v 

Executive Summary 

When first introduced in the early 1980s the Internet appeared to be an interesting 

engineering curiosity, providing resource sharing and data communication services to 

support scientific researchers. Beginning with the introduction of the World Wide Web 

(circa 1995), the fundamental data communication services provided by the Internet 

transformed into a global infrastructure for commerce, education and entertainment. Later 

developments (circa 2005) built upon so-called Web Services to provide innovative 

social networking technologies that citizens the world over can use to organize and 

collaborate around collective interests. Along the way, innovative cell phones and other 

handheld devices were introduced and integrated with the Internet and the Web to extend 

available information and interaction services to people anytime, anywhere. The future 

promises a globe interconnected by large, distributed information networks, where people 

routinely interact in new and unexpected ways. Realizing this future relies in large part 

on our ability to understand and engineer globally distributed systems of interconnected 

hardware and software components, including their use by people. At present, society is 

technologically capable of building such systems but lacks the fundamental knowledge 

required to understand and predict macroscopic behaviors that may arise from complex 

interactions as such systems evolve with the addition of new technologies and new 

patterns of use. A similar lack of knowledge may impede progress with respect to other 

large systems engineered by society. For these reasons, researchers in the Information 

Technology Laboratory (ITL) of the National Institute of Standards and Technology 

(NIST) embarked upon a measurement science based program of research for complex 

systems. The NIST Complex Systems Program aims to investigate and evaluate methods 

and tools that system designers might adopt to improve scientific understanding of large 

distributed systems, such as information networks, electric grids and transportation webs. 

As part of the NIST Complex Systems Program, this special publication 

investigates and evaluates modeling and analysis methods that can be applied to predict 

and understand macroscopic behavior and variations in user experience that may arise as 

engineers introduce changes in software components into a large information network, 

such as the Internet. The Internet consists of millions (someday billions) of 

interconnected components that may be changed independently. For example, every time 

vendors of major operating systems introduce software updates, millions of users 

download new software modules into computers connected to the Internet. As another 

example, users may download software to support new functions, such as social 

networking or distributed gaming. At the current state of the art, system designers lack 

techniques to predict global behaviors that may arise in the Internet as a result of 

interactions among existing and altered software components. Similarly, hardware faults 

and unexpected usage patterns may occur within the Internet. Engineers have insufficient 

methods and tools available to forecast global behaviors and resulting effects on 

individual users. The study described in this special publication aims to improve existing 

knowledge about a range of methods and tools that could be applied to understand and 

predict behavior in such complex information systems. 

To give our study a concrete context, we selected a challenging problem of 

current interest and relevance for the Internet at large. Specifically, we study the likely 

consequences for macroscopic behavior and for individual users should any of several 
Study of Proposed Internet Congestion Control Mechanisms NIST

Mills, et al. Special Publication 500-282 vi 

proposed mechanisms be introduced to augment or replace congestion control procedures 

in the standard transmission control protocol (TCP), which is currently deployed to 

regulate the rate of information transfer among computers connected to the Internet. 

Congestion control procedures allow individual computers to measure available capacity 

on network paths and to attempt to transfer information as quickly as possible. Because 

conditions vary with time, congestion control procedures also enable detection of 

congestion that may arise as too many computers attempt to use a network path. Upon 

detecting congestion, TCP first substantially slows a computer’s rate of transfer and then 

attempts to slowly increase the rate. Researchers have predicted that the standard TCP 

congestion control procedures will inhibit users from realizing increased transfer speeds 

as capacity expands in the Internet backbone from the current rate of 10 Gigabits per 

second (Gbps) to 100 Gbps and beyond. For this reason, various researchers have 

proposed changes to the congestion control procedures implemented in standard TCP. At 

the current state of the art, such proposed changes have been studied on individual longlived flows using analytical methods and also studied using simulation and empirical 

measurements in small topologies with limited types of data traffic. Though researchers 

and engineers would like to predict the effects of such changes on macroscopic behavior 

and on individual users, no techniques are currently available to make such extrapolations 

to large, fast topologies transporting hundreds of thousands of simultaneous data transfers 

of various sizes under a wide range of network conditions. The study documented in this 

special publication describes and evaluates modeling and analysis techniques applied to 

make such extrapolations for seven proposed alternatives to standard TCP congestion 

control procedures. 

We apply techniques often used by scientists at NIST when studying physical 

systems. First, we propose an abstract simulation model, representing a data 

communications network (including TCP) with only 20 parameters, as compared with the 

hundreds of parameters typically used in detailed Internet simulators. Second, we adopt 

2-level-per-factor experimental designs, which consider each parameter at only two 

values, as compared with the billion or so values that each parameter could possibly take 

on. Third, we leverage orthogonal fractional factorial (OFF) experiment designs that 

enable us to model a sparse but balanced set of parameter combinations spread widely 

throughout the space of possible combinations. Reducing the number of parameters, 

parameter levels and combinations enables feasible simulation of large networks under a 

wide range of conditions. Third, we use a variety of statistical analysis and visualization 

techniques designed to explore multidimensional data sets. Fourth, we use detailed 

analyses of time series as required to supplement findings from statistical analyses. We 

demonstrate that our proposed combination of modeling and analysis techniques allows 

us to predict the influence of seven proposed congestion control mechanisms on 

macroscopic network behavior and individual user experience. 

In summary, this special publication contributes to current knowledge about 

modeling and analysis techniques for complex information systems and also contributes 

to the body of knowledge surrounding proposals for improving congestion control 

mechanisms considered for deployment in the Internet. Six specific contributions 

improve current knowledge regarding techniques to understand and predict behavior in 

complex information systems. First, we summarize the current state of the art in 

modeling and analysis of communication networks and we identify several hard problems 
Study of Proposed Internet Congestion Control Mechanisms NIST

Mills, et al. Special Publication 500-282 vii 

that inhibit the study of large, fast networks. Second, we propose an approach to 

construct simulation models with a reduced parameter space. As a corollary contribution, 

we identify and explore some alternative, promising modeling approaches, including 

fluid flow models and hybrid models, which combine quantized time calculations with 

discrete events. Third, we describe and demonstrate how two-level OFF experiment 

designs can be applied to reduce the number of parameter combinations that must be 

considered, while yielding maximum information from available simulation resources. 

Fourth, we describe and apply a variety of analysis and visualization techniques for 

interpreting multidimensional data. We first use these techniques to conduct sensitivity 

analyses of our simulation model and then apply the techniques to compare congestion 

control mechanisms. Fifth, we evaluate our proposed modeling and analysis techniques, 

discussing the strengths and weaknesses of various methods and identifying those 

methods that proved most effective for our study. Sixth, we outline future research 

needed to improve upon the methods we evaluated. Our six contributions enhance 

understanding of methods and tools available to designers of complex systems. 

Four specific contributions add to the body of knowledge surrounding proposals 

for improving Internet congestion control. First, we characterize likely macroscopic 

behavior and user performance for seven proposed alternatives to TCP congestion control 

procedures. In doing so, we reveal that proposed improvements to TCP congestion 

control would benefit individual users under a specific combination of circumstances 

unlikely to arise very often in the general Internet. We also identify some cautionary 

findings with respect to various congestion control mechanisms we study. Second, we 

identify key behavioral characteristics to be considered when comparing congestion 

control mechanisms. We found these characteristics through analyses of experiment data, 

rather than through a priori analyses. Part of our method was to collect as much 

measurement data as possible and then to use statistical techniques (e.g., correlation and 

principal components analyses) to identify those measures representing different facets of 

system behavior. Then, given selected measures, we could determine the key factors 

influencing macroscopic behavior and user experience. Previous studies of congestion 

control mechanisms did not reflect these key factors. Third, we identify and compare the 

main differences among the congestion control mechanisms we studied. We show that, 

for the key behavioral factors we identify, one of the seven mechanisms we studied fares 

better than the others. Fourth, we suggest some future research directions related to 

Internet congestion control. Our four contributions should help researchers to better 

understand the problem space surrounding congestion control in the Internet. 

While the current study is quite comprehensive with respect to the study of large 

distributed systems, we have certainly not covered every method and technique that 

might prove useful. For example, a related project in the NIST Complex Systems 

Program is investigating how Markov models, coupled with perturbation analysis, 

Eigenanalysis and graph theory, can be used to identify specific aspects of system designs 

that might significantly degrade performance when subjected to failures. Further, while 

some of the methods we applied appear quite effective in the context of Internet 

congestion control, we also need to demonstrate effectiveness in other applications. In 

summary, this study makes substantial contributions to methods for modeling and 

analyzing complex information systems and also provides significant information to the 

community of researchers studying Internet congestion control.