Simulation Environment

In this section, we discuss why we use a network simulator, how we simulated the network and why we believe the results are valid.

We use a network simulator because 1) we want verifiable and reproducible results, 2) we want to test the algorithms in a variety of conditions, and 3) we believe the limitations of current simulator technology have limited and accountable effects on our experiments. We discuss this final point in Section VI-B.

Simulator Goals and Setup

In this section, we describe our goals for the simulator and how we configure it to meet those goals.

Our goal for the simulation is to stress the algorithms in both optimal and pathological conditions. We want to know how the worst possible conditions affect these algorithms. The bottleneck bandwidth algorithms are affected by the following conditions:

1. Lack of Queueing at Bottleneck Link

This destroys the causality between packet arrival times and the bottleneck bandwidth.

2. Queueing after Bottleneck Link

This destroys the causality between packet arrival times and the bottleneck bandwidth.

3. Packet Loss

This causes algorithms to take longer to converge.

4. Changing Bottleneck Bandwidth

Some algorithms detect this faster than others.

5. Asymmetric Bandwidth

This could cause algorithms that assume symmetric bandwidth paths to fail. In particular, TCP packets arriving through a high bandwidth downlink will cause many acks to exit the low bandwidth uplink. These low potential bandwidth acks may cause MBF algorithms to fail (see Section V-A).

To model these conditions in a controlled manner, we used the ns network simulator [10]. We generated an 87 node network using the tiers topology generator [3]. tiers generates a network that reflects the semi-hierarchical topology of the Internet. The topology consists of 4 Wide Area Network (WAN) nodes, 16 Metropolitan Area Network (MAN) nodes, and 67 Local Area Network (LAN) nodes and includes redundant links between different MAN nodes and LAN nodes.

The client is usually 9 hops from the server and sometimes as many as 14 hops away, depending on which links have failed.

The traffic measured is one TCP connection from the client to the server beginning at 0.5 seconds into the simulation. The client and server are on different LANs and MANs. The simulation runs for 30 seconds of simulation time. The different link characteristics are summarized in Table III.

Table I: Types of Client Connections.

Link Type	Bandwidth	Latency
Cable Modem Uplink	500Kb/s	3ms
Cable Modem Downlink	10Mb/s	3ms
Ethernet	10Mb/s	3ms

Table II: Traffic Source Parameters: This table lists the traffic source parameters used by ns in our simulations. Size is the size of packets. Burst and Idle give the average on and off times for sending packets. Shape is the shape parameter used for the Pareto distribution generator.

Size	Burst	Idle	Shape
1500 bytes	1000ms	500ms	1.5
576 bytes	500ms	1000ms	1.5
41 bytes	50ms	1000ms	1.5

Table III: Simulator Link Characteristics: Type 1 links are used to carry packets unless they fail, in which case type 2 links are used.

Type	From	To	Modeling	BW	Latency
1	WAN	WAN	T3	44Mb/s	40ms
1	WAN	MAN	Ethernet	10Mb/s	20ms
1	MAN	MAN	Ethernet	10Mb/s	10ms
1	MAN	LAN	Ethernet	10Mb/s	10ms
1	LAN	LAN	Ethernet	10Mb/s	5ms
2	WAN	MAN	T1	1.5Mb/s	20ms
2	MAN	LAN	T1	1.5Mb/s	20ms

We varied three simulation parameters: client connectivity, congestion, and link failure model. We used the two client connections listed in Table I. Only the client is connected to the network using one of the client connections. All other nodes use links described in Table III.

We created congestion by placing three traffic sources at each LAN node. Each source sends data according to a Pareto distribution [7]. The parameters for these traffic sources are summarized in Table II. We varied congestion by using average data rates of 0Kb/s, 400Kb/s, and 1Mb/s. The variety of levels of congestion allows us to explore situations where the packets to and from the client did not queue together at the bottleneck link and/or did queue after the bottleneck link.

We varied the link failure model by using either no failure or a deterministic failure model where selected links along the path from client to server fail at specific times. The first link fails for 5.0 seconds beginning at 10.0 seconds. The second link fails for 6.0 seconds at 20.0 seconds. We chose the following two links for failure: client LAN to client MAN, and WAN to server MAN. Link failures cause packets to be lost, and when combined with redundant links, create the possibility for multiple paths, asymmetric bandwidth, and changing bottleneck bandwidth.

Simulator Validity

We believe that the limitations of current simulator technology have limited effect on our results. Although the Internet exhibits effects that no current simulator can reproduce [13], our results do not depend on having high fidelity. Our goal is not to determine precisely how well these algorithms perform in the Internet on average. Our goal is to compare how well these algorithms perform under certain conditions known to exist in the Internet.