Active network vision and reality: lessons from a capsule-based system

Summary

This paper describes active networks and some of the problems they face. The idea of active networks is to allow user-extensible network functionality. In other words users can run custom programs in the network. This has two potential benefits:

1. Enables a range of new applications
2. Allows services to be location independent

The main problems are performance and security. The authors describe the ANTS system which addresses these concerns.

ANTS allows users to send executable capsules to active nodes in the network. These capsules contain Java code of a limited size which is executed on a special JVM. This JVM contains security restrictions to prevent the code from damaging the underlying system.

The authors also evaluate the performance of ANTS capsules. They find them to be about twice as slow as a C implementation.

Finally, the authors argue that the main benefit of active networks is not a "killer app" but rather the flexibility to add functionality over time.

Thoughts

It is not entirely clear when active networks are better than a separate service running on a networked server. While the idea of decoupling services from a specific location sounds tantalizing, it would be very hard to implement in practice. In a way services such as Amazon EC2 have taken over many of the use cases Active Networks target. For example, services such as video trans-coding can be run on rented, networked, hardware in the EC2 cloud.

Resilient Overlay Networks

Summary

The goal of this paper is to use an overlay network to increase reliability of transmission.

The authors observe that connectivity problems are most often due to BGP faults and misconfigurations rather than link failures. So, it is likely that different nodes are still reachable and they may be able to connect to the final destination. RON takes advantage of this fact to route packets through other reachable nodes to the final destination.

For all nodes in the overlay network RON keeps track of latency, loss rate and throughput obtained through periodic probes. Client may specify their own metrics to use in place of the defaults. RON uses link-state dissemination to buildup forwarding tables. Path selection is done based on the metrics collected about each virtual link.

The authors find that RON improves the packet loss rate by about 5%. It also improved latency for packets that would normally traverse slow links.

Thoughts

RON is a neat idea but it seems like a "hack" to fix a failure of the underlying routing protocols. Maybe some of this functionality should be built into router rather than implemented as an overlay.

On Inferring Autonomous System Relationships in the Internet

The goal of this work is to discover the types of relationships between ASes using publicly observable route announcements. The authors observe BGP announcements from the Route Views router and apply heuristics to classify relationships into provider, peer, and sibling.

The key idea is to use the "Valley Free" property to classify relationships. This property states that:

• A provider-to-customer edge can be followed by only provider-to-customer and sibling-to-sibling edges.
• A peer-to-peer edge can be followed by only provider-to-customer or sibling-to-sibling edges.

These rules encode the economics of network relationships. For example, it does not make sense to provide transit for a peer to another peer because that does not benefit one's customers. The authors also use the size of an AS to estimate its status. Larger ASes are assumed to have a higher degree.

Using these heuristics the authors find that most relationships are provider-to-customer with a small percentage of peering and siblings.

On Power-Law Relationships of the Internet Topology

This paper describes Internet topology and growth using power laws. The authors find that a surprising number of Internet attributes grow as a power function. They study traces of the Internet over a year in 1998.

The key findings are:

1. The out degree of a node is proportional to the rank of that node to the power of a constant. This means that the out degrees of nodes on the internet follow a "power law" distribution
2. The frequency of an out degree is proportional to the out degree of the power of a constant. The authors find the constant to be negative implying that there are a small number of nodes with a large out degree and a larger number of nodes with a small out degree.
3. The total number of nodes within h hops is proportional to the number of hops to the power of a constant. In other words the number of reachable nodes grows as a power function of the number of hops.
4. The eigenvalues of a graph are proportional to the order to the power of a constant.

Overall the authors explain these surprisingly regular relationships by stating that changes propagate up through the network. In other words adding nodes at the bottom forces additional connectivity at the top.

The authors suggest several applications of this work including tuning protocol performance and extrapolating Internet growth.

It would be interesting to see how well these laws extrapolate; are they still applicable today?

White Space Networking with Wi-Fi like Connectivity

Thoughts

This paper addresses the problem of creating wireless access points operating in the "white spaces" of the UHF band. The authors first identify the key challenges of using white spaces:

1. Spatial variation in spectrum availability - in different areas there will be different channels that are unused and thus available for wireless devices.
2. Spectrum fragmentation - TV channels and microphones get priority in the UHF band so the spectrum is split up by the existing users.
3. Temporal variations - Wireless microphones can turn on and off at any time. The wireless access point cannot cause any interference.

The proposed design consists of three parts: spectrum assignment, AP discovery and disconnection. The spectrum assignment algorithm must choose which of the available channels to use. It considers information from clients in order to detect interference both at the sender and the receiver. A bit vector of available channels and a vector of airtime utilization is generated by each node. The access point uses this information the choose the best available channel.

Access point discovery is performed using the SIFT algorithm which allows "clients to discover APs without tuning into all possible channel combinations." This allows fast discovery and reconnection.

Finally, when the access point or a client discovers a new user of the spectrum they broadcast this information on a special backup channel. The access point periodically scans the backup channel and the client switches to it when packets are not received. The backup channel is used to choose a new channel and have all clients switch to it.

The authors evaluate their system and show that it quickly detects access points and effectively disconnects when a primary user appears.

Interactive WiFi Connectivity For Moving Vehicles

Summary

The key idea of this paper is to exploit opportunistic reception of packets by all base stations within range of the source to improve connectivity of WiFi for moving vehicles. The paper motivates this work by noting that currently 802.11b connections can only connect to one base station at a time. The authors compare the performance and connectivity of several hand off mechanisms:

• RSSI - picks the BS with highest signal strength
• BRR - picks the BS with the highest beacon reception ratio
• Sticky - keeps the current BS until it is absent for some time
• History - picks the historically best BS at this location
• BestBS - picks the single best BS using an ideal model
• AllBSes - opportunistically uses all BSes in the vicinity

They find that AllBSes performs best by about 25%, RSSI, BRR, and History all perform similarly. Sticky performs worst. Motivated by the results of this study the authors design a system that uses all BSes in the area to improve connectivity.

The design uses beacons to designate an anchor or primary base station and all other base stations are designated as auxiliary. When the source broadcasts a packet, if the anchor hears it then it broadcasts an ACK. All the auxiliary nodes listen for packets. If an auxiliary node hears a packet but does not hear an ACK shortly after, it probabilistically relays the overheard packet to the anchor. Also, when switching anchors the new anchor will "salvage" unsent packets from the old anchor.

The authors show that their proposed algorithm significantly outperforms BRR in all cases and approaches the ideal performance.

Thoughts

The idea proposed in this paper seems very similar to ExOR idea of exploiting overhearing only applied to a set of access points with a "back-plane" instead of a full mesh network.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

Summary

ExOR is a protocol for multi-hop wireless networks where data is sent and opportunistically heard by intermediate nodes. The routing decisions are made based on which nodes happen to hear the packet rather than a preconceived route.

Specifically, the sender creates a prioritized list of intermediate receivers which is sent with the data. The prioritization is done by computing the ETX metric from each node to the destination. A schedule is setup such that each node in the prioritized list has a chance to broadcast its received data. All nodes listen to broadcasts and if they overhear some packets being sent they avoid re-sending those packets. In the end most of the packets (~90%) reach the final destination. The remaining 10% can be sent by traditional routing methods.

The authors evaluate the system using the RoofNet deployment of 38 nodes distributed over six square kilometers in Cambridge, Massachusetts. They show that they achieve two to four times the throughput of traditional TCP.

Thoughts

Overall this is a cleaver way to use the broadcast nature of wireless communication to improve throughput. It would be interesting to look at forms of forward error correction to encode the 10% of the data that is lost in the process.

XORs in The Air: Practical Wireless Network Coding

Summary

The key idea of this paper is to take advantage of the broadcast nature of wireless and coding to reduce the number of packets that must be sent to transmit data.

The proposed design, COPE, uses three main techniques:

1. Opportunistic learning. COPE overhears packets destined for other nodes and stores them for some time
2. Opportunistic coding. COPE tries to send data encoded in such a way that multiple receivers can extract the packets they need using the data they already have.
3. Learning neighbor state. COPE guesses what packets neighbors may have using the ETX metric.

COPE works by basically "adding" together packets such that multiple recipients can "subtract" the data they already have and obtain a new piece of data. In practice this is accomplished using XOR. This technique is particularly useful when multiple nodes are exchanging data.

The authors find a 3-4x performance improvement when using COPE for UDP flows.

Thoughts

This is a clever use of the broadcast nature of wireless to improve performance. I am actually quite surprised it works as well as it does.

A High-Throughput Path Metric for Multi-Hop Wireless Routing

Summary

This paper presents a new metric, expected transmission count (ETX), for choosing high-throughput paths in a multi-hop wireless network. This metric takes into account link loss rates, asymmetry in loss ratios and interference among the successive links in a path. The authors evaluate this metric in a real test environment and compare it to minimum hop count.

The authors first analyze the shortcomings of the minimum hop-count metric. They find that minimum hop count performs well "whenever the shortest route is also the fastest route." However, minimum hop-count does not consider loss rates which the authors find to vary widely in their test environment. Also, minimum hop-count does not have a way to choose among multiple paths of the same length.

ETX is designed to address these issues. It works by predicting the number of transmissions required to deliver data. In other words, it computes 1 / (df X dr) where df is the probability that the data packet makes it across the link and dr is the probability the ACK is successfully returned. df and dr are computed empirically by occasionally sending probe packets and counting the delivery rate.

The authors implement ETX in the DSDV routing algorithm and compare it to the original DSDV using minimum hop-count. They find that ETX provides a throughput improvement in all cases but it is less significant when large packets are used because the small probe packets do not accurately model the transmission probability for large packets.

Thoughts

ETX is clearly a better metric than minimum hop when dealing with lossy links. It could be improved by estimating actual throughput, as in RoofNet, not just transmission count. This would account for different transmission rates. Finally, it seems that the link loss probabilities could be computed/updated from the data actually being sent not just the probe packets. Overall, this paper presents a simple and clearly useful idea.

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

Summary

This paper compares four multi-hop routing protocols, DSDV, TORA, DSR and AODV, using a network simulator. The simulation is done in a modified ns-2 network simulator with an 802.11 MAC implementation and a realistic radio signal attenuation model.

The authors briefly describe each of the protocols being considered:

1. DSDV: Each node maintains a table with the next hop for all destinations. Routing updates are broadcast.
2. TORA: Routes discovered on demand. Quickly establishing routes is preferred over choosing the shortest path.
3. DSR: The source decides the full route of each packet. Routes are discovered through flooding "Route Request" packets.
4. AODV: Combines route request and maintenance from DSR with hop-by-hop routing from DSDV.

In the evaluation the authors simulated 50 nodes over an area of 1.5k x 300m. The nodes moved at different rates and in different patters. The measured metrics were packet delivery ratio, routing overhead and path optimality.

Packet delivery rates were good (>95%) for DSR and AODV at all rates of mobility. However, DSDV had a poor delivery ratios when nodes moved quickly and TORA could not handle a large number of sources.

The routing overhead also changed significantly with the movement of nodes. In both DSR and AODV the routing overhead was much higher at high mobility. DSDV overhead remained fairly constant and TORA had the constantly very high overhead.

Thoughts

This seems like a thorough and useful analysis of routing protocols. However, the protocols being compared are fairly old. I am curious if any of these are still used today or if they have been superseded. Also, it is not clear how well this simulation would translate to real-world performance.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes the design of a wireless mesh network. The key goal of the design is ease of deployment. So nodes are in unplanned locations and they use omni-directional antennas to avoid having to configure antenna placement. This necessitates a multi-hop routing and path optimization to provide adequate throughput.

The network is auto-configuring and has only some nodes that act as external gateways to the Internet. It uses an internal addressing system based on the MAC address of the Ethernet cards to route within the mesh. At the gateways, NAT is used to translate internal addresses to external ones. This means that connections are tied to a specific external gateway and cannot shift if network conditions change. However, new connections always use the "optimal" gateway.

To route within the wireless mesh each node uses Dijkstra's algorithm to choose the best path. The cost of each link is estimated using an "estimated transmission time" metric. This takes into consideration the throughput bit-rate of the link and the probability of delivery at that bit-rate. For example, "a single-hop route with 40% loss can deliver more data than a two-hop route with perfect links." By considering these trade-offs the node is able to maximize its throughput.

The authors deploy a system of 33 nodes and 4 gateways on rooftops in Cambridge Massachusetts by asking volunteers to install the nodes. They obtain an average throughput of 627 kbits/s with links having a median loss rate of 20%. The throughput is mostly dependent on the number of hops with just 89 kbit/s at 5 hops.

Modeling Wireless Links for Transport Protocols

Summary

This paper details the key features of models of wireless links. The goal is to help address the issue of how to modify TCP and link-layer protocols to improve performance over wireless links.

This paper points out the key problems in current wireless models: unrealistic assumptions, small parameter space, overly realistic and lack reproducibility. Next, they list characteristics of wireless links and how to model them:

1. Error Losses: represent packet loss after link-layer retransmission attempts. Model by dropping packets with some probability.
2. Delay Variation: represents delay due to link-layer recovery, etc. Model by randomly suspending transmission.
3. Packet Reordering: caused by retransmission attempts. Model by randomly swapping packets or delaying single packets.
4. Resource Allocation: some wireless links temporarily allocate bandwidth to streams. Model by introducing delay when a packet arrives to a queue that has been empty for longer than the channel holding time.
5. Bandwidth Variation: may occur on CDMA and UMTS links. Model by occasionally reducing bandwidth of the link.
6. Bandwidth Asymmetry: wireless links typically have asymmetric bandwidths.
   

Finally the paper makes some recommendations. They suggest that bit errors should be handled at the link layer using FEC and retransmissions. However, explicit corruption notification can be used to inform TCP when transmission fails after link-layer recovery attempts. TCP should be more resilient to reordering which would give link-layer protocols more flexibility in recovery. Finally, where possible, link layer protocols should reduce delay variation but delay tolerant TCP may be useful as well.

Thoughts

This paper seemed to state fairly obvious characteristics of wireless links and modeling techniques. The key contribution seems to be in pulling all of these characteristics together and stating where previous work has failed to do so.

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

Summary

This paper explores different mechanisms to deal with loss in wireless networks. Specifically, it compares the performance of three classes of solutions:

1. End-to-end protocols
2. Link-layer protocols
3. Split-connection protocols

End-to-end protocols include standard TCP Reno and modifications. The basic problem is that standard TCP uses packet loss as a signal of congestion, however, in wireless networks packet losses can occur due to noise or interference, treating these losses as congestion degrades performance. The authors find that basic TCP Reno achieves a throughput of 50% of the maximum with a 2.3% packet loss rate on the wireless link. Other variations of TCP Reno include partial acknowledgments (new Reno) which performs better because it can fill large holes, resending one packet for each additional ACK (after 3 duplicates). A different approach is to use explicit loss notification, this allows the sender to maintain the congestion window size while retransmitting lost packets. Both of these modifications perform similarly.

The second class of solutions is link-layer protocols. These solutions perform re-transmissions at the link layer and attempt to hide the lossy link from TCP. The problem with this approach is that re-transmitting at the link-layer can lead to out of order packets received at the destination. This will cause duplicate ACKs which will activate TCP fast retransmit unnecessarily. Several solutions are explored, all involve "TCP awareness" or suppressing duplicate ACKs for packets that have already been retransmitted. The authors find that this solution is best, out performing the end-to-end solutions.

The final class of solutions is split-connection protocols. These isolate TCP from the wireless link by using a different connection to make the wireless hop. If the protocol used for the wireless hop is optimized to handle losses then the overall throughput is quite good. However, the authors argue that this approach breaks the end-to-end principle and is not necessary for good performance.

Thoughts

I am curious to know what is actually done in 802.11b/g/n networks. The link-layer recovery seems like a fairly clear solution but admittedly requires duplicating recovery functionality.

MACAW: A Media Access Protocol for Wireless LAN's

Summary

This paper analyzes the existing MACA wireless protocol and proposes changes that improve fairness and performance. The key problem they address is how to handle congestion fairly and efficiently. First the authors make several observations about congestion:

1. Contention is at the receiver not the sender
2. Congestion is location dependent
3. MACs should propagate congestion information explicitly
4. MACs should propagate synchronization information about contention periods

 The first two observations motivate using a RTS/CTS protocol instead of a carrier-sense protocol. With just carrier sensing, senders can potentially interfere with other senders that are out of range ("hidden terminal" scenario). Similarly, carrier sensing may prevent transmission even when the receivers are out of range ("exposed terminal" scenario). The solution is to use RTS/CTS, where each sender first requests to send and all stations hearing the RTS delay transmission for the length of a reply. If the receiver sends a CTS, then the sender can send and all stations hearing the CTS must wait. The key is that delaying transmission is now tied to who can hear (and thus interfere with) the messages.

This paper proposes several optimizations to the RTS/CTS protocol. Namely, using additive decrease and multiplicative increase of the backoff counter which is used to determine how quickly to re-try transmission. The paper also proposes a fairness optimization: keeping per-stream backoff counters and ordering data using "shortest wait time." They also propose using link-layer ACKs to allow faster retransmissions and DS messages to avoid collisions at the senders, who must now also receive ACKs.

Thoughts

There are a lot of similarities between the techniques used in this paper, at the MAC level, and previous papers we read that dealt with TCP/IP.  For example, the backoff counter operates much like the inverse of the congestion window in TCP/IP, dictating how much to wait before sending rather than the sending rate. Similarly, keeping per-stream queues and using shortest wait-time ordering has been used in routers (Analysis and Simulation of a Fair Queueing Algorithm). Finally, sending ACKs at the link layer is similar to ACKs at the transport layer. All of these similarities make me wonder if it is good that the same type of solutions apply at different layers of if there should be a single mechanism that solve these problems at all layers.

Finally, I am curious if any of this is used in today's wireless networks. I know my home router has RTS/CTS settings but they are turned off by default. Is this not the case for larger enterprise networks?