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.