All posts by Mosharaf

DNS Performance and the Effectiveness of Caching

J. Jung, E. Sit, H. Balakrishnan, “DNS Performance and the Effectiveness of Caching,” IEEE/ACM Transactions on Networking, V. 10, N. 5, (October 2002). [PDF]

Summary

Hierarchical design and aggressive caching are considered to be the main two reasons behind the scalability of DNS. Both factors seek to reduce the load on the root servers at the top of the name space hierarchy; in addition, caching tries to limit client-perceived delays and wide-area network bandwidth usage. This paper analyzes three network traces collected from two different sites during different time periods to study the effectiveness of these factors.

The Data

This study is based on three separate traces (two from MIT and one from KAIST). The authors collected both the DNS traffic and its driving workload, i.e., outgoing DNS queries and corresponding incoming answers (within 60s window) as well as outgoing TCP connections’ SYN, FIN, and RST packets. DNS lookups related to outgoing non-TCP traffic as well as lookups resulting from incoming TCP traffic are excluded, which amount for 5% and 10% of overall lookups, respectively and considered to be negligible.

Observations

By analyzing the collected data and performing trace-based simulation, the authors had following observations:

  • Distribution of popular names follow the Zipf’s law, meaning a small fraction of the names are queried large fractions of the time. As a result, popular names can be cached efficiently with smaller TTL values, whereas unpopular names fail to take advantage of caching with larger TTL values.
  • Sharing cache among groups of clients has limited gain in terms of cache hit after the total member count crosses 20-25. This is also due to the Zipfian distribution of name popularity and TTL.
  • The authors found that the client-perceived latency is adversely affected by number of referrals, and caching NS records to reduce the number of referrals will decrease latency as well as load on the root servers.
  • Distribution of names causing negative responses follows a heavy tailed distribution as well. As a result, hit rate of negative caching is also limited.
  • Many DNS servers are too persistent in retrying and overload the network. 63% of the traced DNS query packets were generated by lookups that obtained no answers.

Critique

The authors have done a great job in collecting and analyzing a large amount of data to provide some insights counter-intuitive to common beliefs. However, there are some issues regarding their collected data. It is not sure why they completely ignored UDP traffic. Several observations are made based on how things have changed in 12 months from the two MIT traces, which is effectively drawing conclusions from just two data points. Another thing is that they saw something and sort of explained that to put forth some conclusions counter-intuitive to previous observations by other fellows; however, it is not sure whether they would have seen something common, had they used other people’s data. In short, the collected data might not have been varied enough to draw conclusions about the whole Internet.

Development of the Domain Name System

P. Mockapetris, K. Dunlap, “Development of the Domain Name System,” ACM SIGCOMM Conference, 1988. [ACM]

Summary

The Domain Name System (DNS) was first proposed (circa 1982) to address the problems faced by the then existing HOSTS.TXT-based “host name to address” translation mechanism, which was suffering from scalability and distribution issues along with other problems common to any centralized system. This paper (circa 1988) gives an overview of the experiences in using DNS since its inception.

DNS Design

DNS design was motivated by several requirements: scalability, performance, decentralization, interoperability, and support for various topologies and OSes. Based on these goals, DNS was designed as a hierarchical name space to create a distributed and lean database that primarily maps names to addresses and performs some other mapping tasks. The internal name space is a variable-depth tree, where each node in the tree has an associated label. The domain name of a node is the concatenation of all the labels. Data for each name in DNS is organized as a set of resource records (RRs), each carrying a pre-defined type and class field, followed by applications data.

The DNS tree is divided into zones controlled by different organizations. Each zone can be a contiguous section of the tree, even though it is typically a simple subtree. Administrative authority flows hierarchically from top-to-bottom among zones. The active components of DNS are name servers, which store information and answer queries, and resolvers, which interface to client programs and find appropriate name servers. A particular name server can support any number of zones which may or may not be contagious and the name server need not be part of that zone. Answers originating from zone data are marked as being authoritative. DNS resolvers and combined name server/resolver programs also cache responses for later use. Each RR contains a TTL field that controls how long it can be cached.

Experiences

  • At the time of writing this paper, most queries could be classified into four categories: all information (25-40%), host name to address mappings (30-40%), address to host mappings (10-15%), and MX lookups (10%).
  • Response times experienced by clients varied from 500ms to 5s.
  • The authors also observed that negative responses was around 10-50% and hence, should also be cached similar to positive responses.
  • TTLs are often misused and misinterpreted by the system administrators.

Comments

This paper discusses the basics of DNS and some general system design/development principles. The most important thing to notice in this paper is the lack of concern about security (which is similar to many other papers from that era). Otherwise, despite many problems, DNS is sort of successful since it has managed to survive the boom of Internet sites and users, and still working.

Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications

I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,” ACM SIGCOMM Conference, 2001. [PDF]

Summary

Chord is a DHT-based distributed lookup protocol – one of too many actually – for P2P systems that looks up a value given a key. What makes it more interesting than its counterparts is specially its simplicity, then logarithmic space and message-passing requirements, and its resiliency under high churn and failure scenarios. Chord strives for load balancing through consistent hashing, decentralization and scalability inherently required for P2P systems, availability during high churn and failure, and flexible naming.

Nodes and keys are distributed on an identifier circle in Chord, where identifiers are derived using consistent hashing. Consistent hashing assigns a key to a node (successor node) whose identifier is equal to or follows the identifier of that key in the identifier space. For correctness, each node only needs to maintain address of/connection to its successor in the identifier circle, at the very least. A lookup for  a key is performed by sequentially following successor nodes until it reaches the node that holds the value for that key. Note that, the goal at every step is to reduce the distance toward the final node on the identifier circle.

For faster distance reduction, i.e., for faster search, each node in Chord also maintains a skip list, aka a finger table. Each finger table has some entries, where consecutive entries hold addresses of nodes farther and farther away on the identifier circle. The authors propose storing O(log N) entries with ith entry holding the address of the node with distance 2i or the immediately next one if there is no node in exactly 2i distance.

To join Chord, a joining node gets its successor node by asking a known bootstrapping node. Once it has the successor node, it runs a stabilization mechanism (which is actually run periodically by every node) that notifies its successor and predecessor nodes to update their successor and predecessor pointers. This ensures Chord’s correctness. Lazily, in the background, everyone updates their finger tables taking advantage of possible optimizations.

To ensure correctness and resilience under failures, Chord proposes using multiple successors instead of just one. As long as there is a single successor alive, Chord will be able to find all the keys. Note that the keys that have values stored on failed nodes cannot be restored. To avoid that, the authors propose a similar mechanism where values are replicated on multiple successive nodes. In general, they resort to the age-old systems tradition of “make multiple copies when you can’t take failures.”

Thoughts

This is most probably the most cited systems paper in recent history, maybe even in whole CS, and rightly so. The beauty of this paper is its simplicity. There are hardly any paper in P2P that does not cite it, and any work that has to use some DHT search end up using Chord because its so damn easy to code and use (at least it seemed so).

It was not clear what the authors wanted to do with the circle partitioning scenario or how stabilization protocol is going to handle that. The notion of a higher layer application entity is not well explained. When it does something and when it does not is not clear in multiple scenarios. Was there any dire need to introduce that entity in this paper? In the evaluation section, the high churn scenario starts with only 500 nodes in the simulation! This significantly lower than other settings (with at least 104 nodes) and questions the reliability of the findings. Its sure though, after this paper several tens of papers came out dissecting its tiniest of details; so the churn problem is most probably taken care of by now.

Looking Up Data in P2P Systems

H. Balakrishnan, F. Kaashoek, D. Karger, R. Morris, I. Stoica, “Looking Up Data in P2P Systems,” Communications of the ACM, V. 46, N. 2, (February 2003). [ACM]

Summary

P2P systems have attracted large following due to their manageability, flexibility, resource-aggregation capabilities, and fault-tolerance properties. One of the biggest challenges in this area of research is finding a given data item in a large P2P system in a scalable manner. This paper provides a brief overview of the lookup problem, mostly from a DHT-based structured P2P systems’ points of view.

Centralized and hierarchical lookup of data in conventional systems suffer from scalability and resiliency issues. To overcome that, P2P systems developed a notion of symmetric lookup algorithms, which can be primarily categorized into unstructured, semi-structured, and structured mechanisms. DHT-based solutions to the lookup problem are both structured and symmetric and work well in dynamic environments where nodes join and leave the network as well as can randomly fail. In its core, a DHT implements just one function, lookup(key), that finds a data item given its uniquely identifiable key: nodes forward requests they cannot retrieve locally to nodes whose ID is closer to the destination based on some distance function. It also stores keys in a load-balanced way among the participating nodes, before it can actually look them up.

The authors divide DHT-based lookup systems into single- and multi-dimensional implementations and briefly explain three examples. Chord and Pastry use single-dimensional circle and tree structures, respectively; whereas, CAN uses a d-dimensional Cartesian coordinate space. All of them try to route a query to the data node based on a distance metric, as mentioned earlier, and provide different complexities based on space-time trade-offs. The characteristics of the distance function highly affects the workflow of a DHT implementation. For example, being not symmetric, Chord’s distance metric requires it to use a stabilization protocol in the background unlike Pastry, which uses a symmetric distance metric. Several open challenges, circa 2002-03, are listed at the end of the paper. Most, if not all, of them are either completely solved by now or reached their saturation points.

Active Network Vision and Reality: Lessons from a Capsule-Based System

D. Wetherall, “Active Network Vision and Reality: Lessons from a Capsule-Based System,” 17th Symposium on Operating Systems Principles, (December 1999). [PDF]

Summary

Active networks were a radical concept of allowing untrusted sources to execute codes on network operators’ hardware to allow faster and easier deployment of diverse distributed applications. Consequently, it also ran the risk of security violations on multiple levels, which essentially dissuaded most people – specially network operators or ISPs – to actually deploy it. Over time, the proponents of active networks had to make some compromise to increase its security and viability. This paper addresses different issues in three areas of active networks based on the authors’ experience of using ANTS, an experimental active networks implementation.

Active Networks (ANTS) Overview

Active networks consists of active nodes, which are basically programmable routers and can execute active codes carried around in capsules based on a type field. To develop a new service, the first step is to write a new set of forwarding routines implementing the desired behavior using a subset of Java (16KB max code size). The ANTS toolkit provides a core set of APIs that restricts what sort of routines can be developed. Once the code is written, it is signed and put up on a directory service. Anyone, who wants to use that service, can lookup the directory, fetch the code and register the service with the local active node. Once the local node calculates the types it is expected to find in capsules for that particular service and disseminate the code throughout the network (through caching and lazy dissemination), the service is ready to go. Capsule processing is pretty straightforward once the code is distributed: after reception, capsules are first demultiplexed using their type field to find references to code, which are then securely executed inside sandboxes, and the process goes on till capsules reach their destinations. There are additional mechanisms such as TTL, fingerprints etc. to provide security at the cost of performance.

Practicality of Active Networks

The authors argue that practical implementation and deployment of active networks hinge on the feasibility of using capsules, the openness of the framework regarding who can introduce new services, and the flexibility of the framework in respect to possible new applications.

  • While capsules provide a more secure way of code dissemination (using fingerprints) and can be performance optimized (by carrying references to code instead of carrying the actual code, using caching), there is still a performance tradeoff. The authors argue that performance overhead of using capsules is minimal and can be contributed mostly to the use of Java.
  • Making active networks more open attracts security risks in terms of protection against attacks as well as from global and local resource management perspective. To mitigate threats, the authors propose using (hierarchical) fingerprinting, restricted API, and strict isolation between different services’ codes. To avoid resource management threats, the authors propose partial solutions using TTL, restricted API, and eventually fall back to using trusted authority provided digital signature.
  • Finally, this paper argues that the biggest gain of active networks is not some “killer app”, rather the flexibility it provides to gradually change things over time. Five different applications are reported to be implemented using active networks methodologies. The authors postulate that successful active network app must be: expressible using the available API, compact and fast, and incrementally deployable.

Comments

This paper does an excellent job in summarizing the active networks landscape as well as providing a overview of the challenges that exist toward its realization, complimented by solution hints. Active and programmable networks were one of the very few really awesome networking concepts that could do a lot in changing the research and commercial landscape. Unfortunately, at that time the available hardware were not fast nor programmable enough. In addition, there was and still is a lot of skepticism and prejudice among network operators regarding opening up their networks to untrusted sources.

However, in last couple of years, network virtualization has emerged as the solution for a secure, flexible, and extensible future networking platform that combines the programmability of active and programmable networks with concepts of overlay networks and VPNs. The main reasons behind this is, first and most importantly, programmability nowadays is cheaper and faster (with the wide-spread use of FPGAs and/or network processors) and secondly, using so-called “safe” hardware or execution environments do not take as much performance hit as they used to a decade ago.

To conclude, active network was too futuristic for its time and no one is still completely sure whether its time has come yet!

Resilient Overlay Networks

D. Andersen. H. Balakrishnan, F. Kaashoek, R. Morris, “Resilient Overly Networks,” 18th Symposium on Operating Systems Principles, (December 2001). [PDF]

Summary

Routing scalability in BGP comes at the cost of reduced fault-tolerance and slower fault-recovery procedures. BGP hides paths due to policy concerns, damps routing updates to avoid route flapping, and has or uses little information about live traffic. As a result, sometimes it takes many minutes to sense and recover from an outage or traffic overload. This paper proposes using an overlay (RON) to actively and passively probe and monitor traffic conditions on links to provide resilient and faster paths circumventing faults in the network, given that there is physical path redundancy.

A RON creates a clique of distributed overlay nodes that are tightly connected and continuously share information between themselves (using a link state protocol) through aggressive probing and monitoring to maintain high throughput virtual links (with minimal bandwidth usage). Whenever a usual physical path experiences excessive delay or completely goes out, a RON node uses RON virtual links to route packets through other RON nodes. As a result, RON can detect route faults faster and can provide alternative paths quicker than BGP. Other goals of RON include, application defined path selection (by allowing applications to define their own metric of the “goodness” of a link) and to provide a framework for implementing expressive routing policies.

A RON client interacts with RON using an API interface, called conduit. The entry RON node conduit classifies a packet, tags it, selects a path, encapsulates it in RON header, and forwards it to the next RON node (if the usual physical path is experiencing outage or performance hit). Intermediate RON nodes keep forwarding the packet by guided by their database of policies as well as tag-action mappings until the packet reaches the exit RON node where it is decapsulated and delivered to the destination host. Forwarding component of a RON node also uses caching based on flow id for faster processing of packets. Each RON node maintains three different metrics – loss rate, latency, and TCP throughput – for each link. In  addition, RON also allows creation of app-defined metrics and update mechanisms for further flexibility.

RON provides very high connectivity among its nodes and provides guarantees that there is always a path to reach from one RON node to another unless the RON graph is partitioned. The bootstrapping of RON nodes starts with a static list and dynamically updates and adds new RON nodes over time. The cost of keeping such tight coupling through periodic flooding is postulated to be negligible to the gain provided by maintaining them.

The authors evaluated the RON system on two RON networks, one with 12 nodes (RON1) and the other with 16 nodes (RON2) distributed over the Internet, each with N*(N-1) links. RON nodes were hosted two types of networks: highly reliable educaional and research network (Internet2) and commercial networks. All improvement regarding commercial paths came from commercial network by explicitly prohibiting them from using Internet2 paths. Major results are as follows:

  • RON1 managed to successfully detect and recover from 100% of total outages and all periods of sustained high loss rates of 30% or more; RON2 did the same with 60% success rate. The authors did not shed much light on why RON2 couldn’t do as well as RON1; they just mentioned that in the RON2 almost always unreachable node was completely isolated due to network disruption.
  • For a RON of 50 nodes, there is a 30Kbps overhead to keep its nodes informed and operational.
  • RON took 18s on the average to route around an outage or a failure. An emulated 3-node RON topology was used to show that there is a 13s turn-around time for RON facing a flooding attack; however, how it would’ve performed with larger number of nodes remains open.
  • RON doubled TCP throughput in 5% of the samples and reduced the loss probability by 0.05 or more in 5% of the samples (may or may not be different).
  • Most importantly, they found that in most cases going through a single RON node is good enough. The whole paper revolves around this observation and RON workflow is also influenced by this.

Critique

The idea presented in this paper is interesting from a conceptual point of view and really worth reading or thinking about. However, from a practical point of view, there are several reasons why RON is not going to make it:

  • First of all, RON will mess with the underlying traffic matrices of the ISPs, which might result in route instability; as RON starts flowing traffic in some routes that ISP traffic matrices do not want to use, ISPs will update their traffic matrices to counter RON and eventually there will be a cat-and-mouse chase between them.
  • Second, RON will introduce extra latency and bandwidth consumption in intermediate nodes and specific links due to probing, encapsulating/decapsulating etc; the evaluation provided in the paper is limited to only two scenarios which may or may not generalize to larger cases.
  • Third, RON depends on cliques between all the RON nodes and uses flooding between them; this will not scale.
  • Fourth, the authors do not discuss how someone will pick nodes where to put RON nodes; it seems there should be strategic configurations that will give more leverage than others.
  • In addition, there are NAT issues as pointed out by the authors.

Overall, it is a nice paper and a good conceptual exercise, but not practical for the current Internet ecosystem.

On Inferring Autonomous System Relationships in the Internet

L. Gao, “On Inferring Autonomous System Relationships in the Internet,” IEEE/ACM Transactions on Networks, V. 9, N. 6, (Dec. 2001), pp. 733-745. [PDF]

Summary

Business relationships among the ASes in the Internet are kept secret, similar to any other business deals. The only thing available to outsiders are the BGP route announcements that can be accumulated and read from different vantage points. This paper presents heuristics to infer the different business relationships (customer-provider, peer-to-peer, and sibling-to-sibling) seen in the Internet with a very high accuracy (99.1% in some cases).

The inference procedure depends on rational selective export rules for announcing routes to customers, providers, peers, and siblings; e.g., peers never transits for each other, siblings always transits for each other, and customer-provider share a one-way transit from provider-to-customer direction and not vice versa. Based on this observation, the authors also define the Valley-Free property of routes, which says that

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

Essentially there are some patterns of different types of routes, and the authors exploit their presence to identify different relationships. They also assume that larger ASes have higher degree and provider ASes are bigger than their customer ASes.

There are 3 phases to the proposed inference algorithm. First, all AS-pairs are coarsely classified into customer-provider and sibling relationships. Next, all AS-pairs that cannot have peering relationships are identified. Finally, peering relationships are identified from the remaining connected AS-pairs based on the heuristic that their comparative sizes remain within a factor R.

The authors used RouteViews-collected BGP routing table entries and using their algorithms found AS relationships, which were validated by secret AT&T data. By changing the approximation parameters they managed to achieve 99.1% accuracy. It should be noted that they were mostly wrong-inferring sibling relationships. They postulate that this error can happen due to several possible reasons: router configurations errors, misconfiguration of export rules, unusual AS relationships, and possible problem with the proposed heuristics, but they do not elaborate on that.

Critique

The contribution is great and important, but somehow the way its written makes a reader want not to read it. Unfortunately, it is unnecessarily long and artificially complicated.  Also some of the mathematical stuff seemed not-so-necessary. When a few lines can clearly explain something, why bother using equations, mathematical symbols, theorems, lemmas just to scare people away!!! Plus, this paper should’ve been read with other BGP related papers.

On Power-Law Relationships of the Internet Topology

M. Faloutsos, P. Faloutsos, C. Faloutsos, “On Power-Law Relationships of the Internet Topology,” ACM SIGCOMM Conference, (September 1999). [PDF]

Summary

This paper explores the underlying regularities of the Internet structure and uses power laws to capture the properties of the AS-graph. The results presented in this paper are based on three AS-level as-complete-as-possible traces of the Internet over a 14 months period from Nov’97 to Dec’98. Within this 14 months, the Internet had a 45% growth. To include the intra-domain characteristics, the authors also used a node-level trace of the whole Internet circa ’95.

The authors observed that the then-existing metrics to capture the characteristics of the Internet were mostly minimum, maximum or average values, which failed to capture the inherent skewness of Internet-related distributions. Based on this observation, they tried and managed to fit the collected trace data to power-law curves with very high accuracy.

This paper proposes three power laws and one approximation (due to lack of data points, they couldn’t strongly suggest it to be a law!), and define four exponents/power-law curves:

  1. Rank exponent, R: The out-degree of a node is proportional to its rank to the power of a constant R. From the traces, the authors found that the rank exponent R significantly varies between different types of graphs (e.g., AS-level and node-level) to be able identify them.
  2. Out-degree exponent, O: The frequency of an out-degree is proportional to the out-degree to the power of a constant O. This law suggests that there is an underlying out-degree distribution of Internet-like graphs, and the authors propose the use of this metric to rule out synthetic graphs that does not have similar out-degree exponents.
  3. Hop-plot exponent, H: The total number of pairs of nodes within a certain number of hops of a node is proportional to the number of hops to the power of H. It can also be used to separate between different types of graphs.
  4. Eigen exponent: The eigenvalues of a graph are proportional to the corresponding order to the power of a constant E. The authors found that this exponent remained sort of constant over time to suggest that it is size-invariant; but they found that it can also be used to identify different classes of graphs.

Because the power laws show consistent correlation among traces, they authors propose them to be used to assess the realism of synthetic graphs, to help analyze the average-case behavior of network protocols, and to concisely define Internet-like graphs. The paper also provides several formulas to calculate the number of edges, nodes, density of nodes of such graphs.

Thoughts

The authors have done an excellent job to draw conclusions from a vast amount of data to provide structure to the Internet graph. It was really interesting to see that there is order somewhere under the seemingly chaotic world of computer networks and their interconnections. In fact, as the authors point out, power-laws can be observed in many other types of social, scientific, and biological networks. I wonder why?

White Space Networking with Wi-Fi like Connectivity

P. Bahl, R. Chandra, T. Moscibroda, R. Murty, M. Welsh, “White Space Networking with Wi-Fi like Connectivity”, ACM SIGCOMM Conference, (August 2009). [PDF]

Summary

With the FCC opening up the unused portions of the UHF spectrum, also known as the “white spaces”, researchers have set upon implementing WiFi over the newly acquired territory. Such networking is different from existing WiFi technologies along three axes: spatial variation, temporal variation, and fragmentation of the UHF spectrum. This paper presents WhiteFi, the first WiFi over white spaces that implements adaptive spectrum assignment algorithm to tackle spatial variation and fragmentation, and proposes a low overhead protocol to handle temporal variation. This paper is concerned with the “only one Access Point (AP) with multiple clients” scenario, and unlike the existing solutions, WhiteFi works on variable channel widths and uses SIFT (Signal Interpretation before Fourier Transform) for faster and better detection of data transmissions.

The Three Challenges

As mentioned earlier, UHF white spaces are different from ISM bands used in the existing WiFi in three ways:

  • Spatial variation: The set of channels occupied by TV transmitters and the number of stations operating in an area vary from one place to another with significant variance. As a result, an AP must select a channel after proper consulting with all its clients based on their location.
  • Spectrum fragmentation: Since UHF bands already have incumbent TV channels, they are fragmented irrespective of urban and rural areas. As a result, radios working in white spaces must use variable channel widths, which makes channel assignment and AP discovery harder than that in ISM bands.
  • Temporal variation: Channel occupancy by incumbents also vary based on time. Since the FCC does not allow messing up incumbents, the AP and its clients must move away as soon as they detect a microphone (working on UHF) starts working.

Proposed Solution

The proposed solution consists of an adaptive allocation/assignment algorithm, a lightweight protocol, a specialized hardware to glue them together.

  • Hardware: The authors developed KNOWS, a specialized hardware platform with a PC, a scanner, and a UHF translator, to support WhiteFi. The PC controls the others, the translator translates backs and forth from WiFi, and the scanner samples UHF spectrum to find white spaces.
  • Spectrum assignment: The AP must pick a channel that can be used by all the clients. So once it finds one, it keeps checking periodically to find a better one (voluntary) or to move away from a conflicting channel (involuntary). For finding a channel, the authors propose a channel probing mechanism based on a new metric that can predict channel availability with high accuracy. The AP evaluates all possible channels and picks the one that maximizes the metric and works for all its clients. Then the AP broadcasts the new channel for its clients to switch to. The information between the AP and its clients are passed using a bitmap where each bit says whether a channel is or can be used or not. To avoid moving back and forth between channels without much gain, the authors also used hysteresis process.
  • AP discovery: Since the AP can use more than one channel, finding an AP is computationally harder for its clients in WhiteFi than that in WiFi. The authors introduced a new signal analysis technique SIFT, which basically determines packet widths based on signal amplitudes with small number of false positives. Two different versions of SIFT are proposed:
    1. L-SIFT linearly scans all the channels, and
    2. J-SIFT scans in a top-down manner from higher MHz channels to lower ones in a staggered manner, and once it detects the presence of a WhiteFi transmitter, it identifies the center frequency.
  • Handling disconnections: To cope with sudden appearance of an incumbent transmitter, the authors propose to keep a backup channel where everyone periodically pings about their status. To backup the backup, an arbitrary available channel is used as a secondary backup.

Evaluation

The authors performed most of their evaluation using simulation, because they could not test on real white spaces, citing FCC regulations! And there are no surprising finding either: SIFT is mostly accurate across different channels, J-SIFT does really well in discovering APs, disconnection handling works, and the proposed metric closely follows availability to make the proposed assignment algorithms perform really well in real time.

Thoughts

The problem is really fresh and exciting, as is the solution, except for the gory signal analysis part (fortunately or unfortunately that’s a big contribution). Its great to see the ‘first’ paper in a completely new area! One can predict that this paper will be really big (at least in terms of citation) in the long run if all the hype about white spaces hold up.

There are a few comments. Throughout the evaluation section, the authors keep talking about the optimal omni-potent algorithm that works best for any channel. How did they come up with that, and how it influenced their design? While evaluation the impact of spatial variation, the authors used some minimum and maximum probabilistic values. Where and how did they come up with those values? If there is any other studies of white spaces, they don’t mention it.

Unlike 10MHz and 20MHz packets, 5MHz packets have little or no variation with respect to any parameter. What is the reason? Are they parameter insensitive or the parameters are not fine tuned enough to catch their sensitivity. It would have been better to see some explanation.

Interactive WiFi Connectivity For Moving Vehicles

A. Balasubramanian, R. Mahajan, A. Venkataramani, B. N. Levine, J. Zahorjan, “Interactive WiFi Connectivity For Moving Vehicles”, ACM SIGCOMM Conference, (August 2008). [PDF]

Summary

Current WiFi handoff methods, where a client remains connected to a single basestation (BS), lead to frequent disruptions in connectivity in highly mobile vehicular networks. This paper proposes ViFi, a protocol that opportunistically exploits BS diversity to minimize disruptions and can support interactive applications (e.g., Web browsing, VoIP). ViFi opportunistically connects a mobile client device to multiple BSes, and coordinates between those BSes using a distributed and lightweight probabilistic algorithm, to obviate hard handoffs.

Observations

The authors performed experiments on two testbeds (VanLan and DieselNet) with 6 handoff protocols (practical as well as optimal) to come up with the following conclusions that led to the ViFi design:

  • With a reasonable density BS deployment, a vehicle is often in range of multiple BSes. Existing handoff mechanisms do not take advantage of this property.
  • Packet loss, in each vehicle-BS connection, is independent and bursty. A BS that failed to receive something is more likely to fail in close temporal proximity than another BS which also overheard the same transmission.

ViFi Design

In its core, ViFi allows overhearing BSes to carry on a transmission towards the destination even though the intended BS failed to receive or acknowledge it. The main challenge here is to coordinate between BSes with minimal overhead and latency and with little to no disruption as BS set changes. To this end, ViFi designates one of the BS as the anchor and the rest as auxiliary BSes within the range of the sender based on some metric. Through periodic Beacons from the vehicle, BSes get to know each other (who is anchor etc.) as well as the sender vehicle. The operations of ViFi is symmetric in both directions (src and dst) and given in the following:

  1. src transmits the packet P.
  2. If dst receives P, it broadcasts an ACK.
  3. If an auxiliary BS hears P but not the ACK within a time period, it probabilistically relays P. (Note: Relaying takes place in the inter-BS backplane)
  4. If dst receives relayed P and yet to broadcast an ACK, it does so now.
  5. src retransmits when retransmission timer goes out. (Note: Retransmission timer is adaptively set based on how fast a vehicle receive ACKs)

Probability of relaying or not relaying is computed locally in each BS based on the accumulated information from overhearing and Beacons. The invariant in this probability calculation used by the authors is that the expected number of packets relayed across all auxiliary BSes is equal to 1 (which also makes sure that a packets is relayed at most once by a BS). There can be false positives and false negatives due to the independent calculation methods, but the authors postulate that that will be very low.

ViFi also supports salvaging, i.e., whenever a vehicle moves out of the range of an anchor, the new anchor contacts the previous anchor to take care of the un-forwarded packets to the vehicle. This ensures that TCP won’t assume congestion, when there is none.

Evaluation Results

  • Link layer performance of ViFi closely approximates the ideal solution in the testbeds.
  • Both Web and VoIP traffic enjoys better goodput and session connectivity using ViFi. Percentage gain varies based on testbed though. Salvaging gives 10% boost, but its not very useful for VoIP.
  • Medium usage/efficiency is usage is roughly the same for the increased performance.
  • Coordination mechanism has low false positives than naive approaches and higher, still small, false negatives.

Critique

The whole design and concept is intriguing; but they are all based on two controlled testbeds with dense BSes and only one vehicle. What will be the overhead on the backplane or the number of signal collisions, if there are many connections going on at the same time? To give credit to the authors, previous work on opportunistic algorithms also avoided this aspect as much as possible, even in stationary scenarios.

The authors point out the possible problems with a high number of equidistant auxiliary BSes, that might increase overhead and make selection process harder (now they select all, but selecting some out of many BSes as auxiliary will intrinsically introduce more errors). Deployment of enough BSes to make ViFi perform better than others is another problem. Such dense deployment is easier in urban areas, but will be much harder elsewhere.

Some parts of the work presented and the problem itself had been present in the context of cellular networks and addressed there to some extent. The authors sporadically mention that too, but never actually go deep into discussion or comparison.  A better comparison, even if qualitative, would have been nice in the relative work section.