Tuesday, October 28, 2008

Prof. R Jain talks at ACM MM

I'm at ACM MM 2008 (in Vancouver) right now, and the keynote talk is by Prof. Jain on Internet 3.0. Main poitns of concern: security, mobility, energy.

Monday, October 20, 2008

A first-principles approach to understanding the Internet's router-level topology

This paper tries to articulate the dangers of over-relying on probabilistic network topology models that matches macro statistics such as power laws on degree distributions. Its key observations (and shown in the experiments) are that different network topologies can have the same node degree distribution and that a graph that is "more likely" according to a degree distribution often have poor performance metrics due to the presence of highly connected hub nodes. The authors also tries to make the point that even when core routing topology stays the same, different end-user bandwidth demands would drive a different edge network topology leading to very different degree distributions - thus there may not be a single degree distribution for the Internet.

I think that the thesis of the paper does go deeper beyond the above arguments, but I had a hard time trying to grasp it (and may not still). The authors claim to be pushing for a new methodology to study and characterize Internet topology but they beat around the bush quite a bit. They state that technology and economic constraints are drivers for network topology, but the assertions made are qualitative statements, and are weakly followed through by the design of a "heuristically optimal" network which performs well but may not be "likely" according to a probabilistic toplogy model.

What I have hoped to see was a paper that says something along the following lines: if I have these technical constraints, and I want to satisfy certain economic conditions and some user demand (possibly heterogeneous), this is the kind of Internet network topology that I would see. There would be certain topology metrics that can be predicted and verified from collected data.

On power-law relationships of the internet topology

In this paper, the authors describe several power law relationships of quantities of interest in studying Internet topology, based on analysis of collected Internet data. If there are indeed such power laws, it would be useful in verifying or deciding between graph models used in simulations, in studying the theoretical performance of Internet protocols, or in modeling the evolution of the Internet. The power laws described in this paper are:
  • Node out-degree and its rank (in order of decreasing out-degree)
  • Out-degree frequency and out-degree
  • Number of pairs of nodes within h hops and h
  • Eigenvalue of connectivity graph and its order (in order of decreasing eigenvalue)
From these power laws, other relationships can also be elucidated, such as between edges and rank exponent and between average size of neighborhood within h hops and hop exponent.

It is interesting that such relationships exist, at least in the data that the authors examine. My biggest question would be how applicable are these laws over the years since this study was carried out. Related to this would be how time-invariant the exponents really are. My guess would be that the power laws would have exponents that are fairly constant over time, since they have to do with how hosts are connected to the internet through router, and the choices that are made are constrained by cost-effectiveness and hardware. Of course, if there was a major shift in technology or cost structure, this should also show up in the evolution of the exponents. The key point is that these laws should hold with just plain scaling.

I think that Section 5.1 would have been interesting to expand on. Namely, I would like to know if some of these power laws can be derived from first principles. As the authors pointed out, cost-effectiveness in designing networks can drive a common solution in network topology, hence leading to some of the power laws described in this paper.

Wednesday, October 8, 2008

XORSs in the air: Practical wireless network coding

The title says it all: the authors are interested in demonstrating network coding, a topic of much recent interest in network information theory, in a practical wireless testbed. Theoretical results have shown that in a network, allowing coding/mixing in the intermediary nodes achieves the multi-cast capacity in this network (while routing might not). As the authors node, the capacity and optimality of network coding is open for unicast traffic in an arbitrary network. As it turns out, that is also the scenario of interest in this paper. Another key difference is that a broadcast transmission from a node can be heard by many surrounding nodes, whereas in traditional network coding, a transmission is only heard by a node at the other end of the link.

I have to admit that I was expecting something a little different before reading this paper. I thought the paper was going to pick up from the previous paper, and describe a coding approach for exploiting path diversity for higher throughput for a single unicast flow. What the paper seem to be describing is for multiple unicast flows. If the packets from each flow are not shared, its not immediately clear to me why network coding helps. (The butterfly example is when the receivers all want the packets injected by the various sources). COPE seems to assume that the neighbors of a node would want to have all the packets that it has; why that is the case is not immediately obvious to me.

ExOR: Opportunistic multi-hop routing for wireless networks

This paper is based on the following idea: in a wireless network, a transmitting node can be heard by more than one neighboring nodes. Instead of just depending on one forwarding node as in traditional routing, why not use any node that received the data to do the forwarding? This can reduce the number of re-transmissions and increase throughput. More concisely, this paper aims at making practical use of path diversity in a wireless network.

Alas, this simple idea needs plenty of book-keeping to make it worthwhile, and the rest of the system description describes one such approach. To reduce packet overhead, only a small number of forwarding nodes are considered for each hop. Second, to avoid duplication of transmission, there needs to be some mechanism for nodes to know what other potential forwarding nodes have done. Here, the authors choose to send a batch of packets at a time to pipeline the transmission and agreement of which packets have been sent by forwarding nodes.

Partly due to the complexity of the book-keeping, I was not able to quite follow how this works beyond one hop. Clearly, from the experimental results, ExOR works for multiple hops. I also could not make up my mind how centralized/distributed this scheme is. A server seemed to be necessary to obtain a complete global picture of the network and send it to all nodes such that the source node can pre-compute which are good forwarding nodes. For dynamic networks, a periodic route finding seems expensive and unsatisfactory. Is there a way to discover multiple paths in a distributed fashion in a dynamic environment?

My overall sense of the paper is this: too many things seem to need to happen for it to work, its a wonder that the results are as good as that shown in the paper. It is nice though that the authors point out that path diversity works well only if there is indeed some diversity in loss patterns observed by forwarding nodes; if the losses are highly correlated (perhaps a localized jammer?), there is a performance gap. Still, all it takes is one forwarding node to receive the packet for it to go through.

Monday, October 6, 2008

A performance comparison of multi-hop wireless ad hoc network routing protocols

As its name suggests, this paper compares 4 routing protocols for in an ad hoc network scenario: DSDV (hop-by-hop routing, periodic broadcast updates), TORA (route discovery on demand), DSR (source routing, discovery on demand) and AODV (hop-by-hop routing, discovery on demand). The evaluations are performed on a network simulator, ns, using an updated physical and data link layer model.

The experimental methodology studies routing performance with varying node mobility, packet rates, and number of transmitting sources. Nodes use a "random waypoint" movement model, with a pause time (when the node is stationary) before moving to the next waypoint, at maximum speeds of 20 m/s (~45 mph) or 1 m/s (~2.25 mph). Transmitting sources are assumed to be constant bitrate sources. Its not clear what real-life scenarios this simulation is reflective of (perhaps vehicular adhoc networks?) at speeds of 20 m/s. If the goal is to evaluate the performance on topology changes at various speeds, then maybe limiting transmission to when sources/sinks are stationary would be more realistic.

The main results are that:
  • Packet delivery ratio is high (0.9-1) and relatively stable for TORA, DSR and AODV over a range of pause times (i.e. topology change rate), but is lower for DSDV at pause times less than 300s. However, at low speeds (1 m/s), all protocols have fairly similar performance.
  • TORA performance in packet delivery ratio degrades when the number of sources is high (i.e. 30)
  • Routing overhead is constant with respect to mobility for DSDV (as expected). Routing overhead scales with mobility for the other routing protocols, with TORA > AODV > DSR
  • Routing overhead is constant with respect to number of transmitting sources for DSDV (again as expected). It scales with number of transmitting sources for the other routing protocols. At 30 sources, TORA >> AODV >> DSR, with an order of magnitude of difference between each of them.
  • In terms of path optimality, both DSDV and DSR do very well, while TORA and AODV having significant number of packets routed through paths with 3/4 extra hops than the shortest path.
The main message is that there are no clear winners, and which protocol to use may well depend on what the operating conditions are.

Sunday, October 5, 2008

A high-throughput path metric for multi-hop wireless routing

The main contribution of this paper is in recognizing that choosing a route based on minimum hop-count may not always be the right thing to do, since it does not take into account the link loss rates. Furthermore, doing so might also tend to pick hops with long distances, which is likely to be correlated with high losses. Instead, the authors suggest using a metric that is based on minimizing the expected number of transmissions along the route. This is an additive metric, where the metric of each link is the expected number of transmissions (and re-transmissions) along that link, given by 1/(df*dr), where df and dr are the delivery ratios for the forward and backward directions. Both ratios can be estimated by using regularly broadcasted probe packets from each node.

What I thought was missing from the paper was an intuition of why this expected transmission count (ETX) is the right thing to do, under the assumptions that the radio uses a fixed power, and that the link layer uses re-transmissions as an error control mechanism. Ideally, one would want to choose a path that maximizes throughput. However, ETX seems to be minimizing the expected link latency (assuming no queueing delay). Even then, ETX does not take into account the turn-around time at each hop, although that probably is a second-order consideration. And why not use the expected transmission count of the bottleneck link as the metric? My best guess is that ETX accounts for both the number of hops (in a high hop count route) and the bottleneck (in a low hop count route) in a single easy to describe/implement package.

The use of the experimental wireless testbed is quite convincing, first in motivating the need to move away from a hop-count metric in routing. I'm suprised by the significant assymetry in links; I wonder how "omni-directional" the antennae really is. The CDF also paints a convincing picture of the improvement provided by using ETX.

Wednesday, October 1, 2008

Architecture and evaluation of an unplanned 802.11b mesh network

As its title suggest, this paper discusses an implementation and evaluation of a wireless mesh network. I like the overall presentation; its clear in explaining what was done, actually carried out the system experiments and show plenty of experimental results. Despite that, I do have some concerns.

First, the assumption that "community wireless networks typically share a few wired Internet connections" is a little dubious. Perhaps there might be good reasons to back up such an assertion (maybe in a rural or undeveloped setting??), but these were not made clear. On the other hand, a deployed mesh node requires power at the very least, and in the urban setting where experiments were carried out (deployment in buildings), it is hard to imagine that the nodes cannot have access to a wired internet connection. I suppose there could be a cost pressure in having wired internet connection, so it could make sense to reduce that number. In that case, it should be make clear, and the trade-off between cost of wired connections and internet access throughput could be studied.

Second, and related to above, the experiments measure throughput between pairs of mesh nodes. While the results are well and good, it doesn't answer what users would care most about, that is, how fast internet access is. Given that wired connections are limited, the gateways represent a bottleneck to the internet. This point is important because the key assumption of the study is the limited number of nodes with wired internet access.

Third, it was not clear if throughput was measured simultaneously or one at a time. Section 3.7 mentions inter-hop interference, but that seems to be due to intermediate nodes performing hops on the same path between two sender/receiver nodes. Given that a typical use case would have at least some number of nodes trying to communicate with the gateway, it would have been nice to see how average throughput varies with the number of simultaneous communications.

A minor note on the effect of density (section 3.4). It would have been interesting to see how the empirical density for full connectivity compares with known theoretical results for full-connectivity in random graph theory, given the maximum range of the communications.

Now, to end on a positive note. I think the routing protocol presented here is useful not just for wireless mesh networks, but would also be useful for an overlay network. I'm not sure how routing for overlay networks work, but I'm guessing it won't be too different.

Modeling wireless links for transport protocols

In my opinion, the key contribution of this paper is in carefully reviewing aspects of wireless links (cellular, WLAN, satellite, etc.) and proposing how the salient features of each can be expressed in simulations. The proposals are also implemented in ns-2. One hope is that by standardizing simulation parameters, it makes it possible to compare results across papers. This is in turn motivated by the desire to understand how existing protocols are affected by wireless links, since the assumption has been that a packet loss is due to congestion rather than link errors, and how to modify protocols appropriately.

The key modeling proposals are:
  • Link errors: packet drops based on specified per-packet/per-bit errors, with possible use of a Gilbert-Eliot channel model. Where packets are dropped also depend on whether loss is caused by link corruption (after transmission) or by handover (before transmission).
  • Delay: suspend packet transmission
  • Reordering: swapping packets or delaying a packet while letting others pass. Also, whether or not to model it could depend on if its allowable.
  • Bandwidth allocation/variation: applicable for GPRS
  • Bandwidth assymetry
  • Queue management
  • Handovers (as a result of mobility): the level of modeling details depend on what is being studied. (e.g. full fledged vs modifying link characteristics)
It seems strange that the authors make a big deal about the dangers of modeling wireless as duplex when it actually is not, but then do not quite describe what is the approach that they took in the end. They do mention two possibilities, either reducing the advertised link-rate or modeling the half-duplex nature. But what did they do at the end of the day?

I do think that a good model of wireless links is a worthy enterprise, not just for pure network research, but also for applications-oriented research such as video streaming over wireless. A good model allows for quick prototyping and simulations before building the actual system to try it out. I also do wonder if there are any models of the end-to-end link, e.g. a model of the link between a server sending data over the internet with a wireless last-hop, where both congestion and link errors/delay come into play. Again, such a model would be useful for doing research on video streaming for example.

I also wish that the paper was written in a more systematic manner. For example, I think section 2 and 3 should be swapped, but perhaps its not possible to point out shortcomings of prior simulations without first describing the properties. Section 7 seems like an add-on, which I thought not totally relevant. Perhaps its to convince readers of the need for such a model. I also wish that there was a summary to inform readers of all the modeling aspects and parameters, maybe a table of some kind.