Power Law Relationships of the Internet Topology

This paper investigates aspects of internet topology, determining whether power laws of the form "x is proportional to y^a" for quantities x, y, and constant "a" exist in the graphs representing the Internet at the inter-AS and inter-router level. The motivation of this is that using averages/min/max distills the data too far: it gives very little information about the actual distribution of values.

As an alternative, this paper proposes essentially ordering the nodes (whether they are ASs or routers) by some metric, and then expressing the slope of the distribution on a log-log scale (which is "a" in the power law). Then, to evaluate the accuracy/effectiveness of the power law, the authors correlate the slope with the actual values (i.e. they measure the closeness of the fit). In addition, it is important to remember the paper's goal is to come up with some good metrics to measure the validity of internet graph model generators.

The first thing that jumps out to me about the paper is that the dataset used to determine the fits is quite small: three inter-AS topologies from 6-month intervals and a single router topology from a different, earlier time period. Along with the fact that the datasets are so small, there is no measure of accuracy for any of the data points; the fact that the router topology does not correspond to the inter-AS data also makes it difficult to tell whether the fits mean anything.

Admittedly, I'm out of my depth in trying to evaluate the soundness of their statistical methods, but the authors seem conclude that the close correlations are evidence enough that the power laws actually mean something. Further, it is difficult to tell exactly what the power laws mean in terms of how ASs change their interconnections over time according to the goals and restrictions of each. For example, their 1.45x number of nodes increase per year seems like an interesting number; although it may hold for ASs, I think for routers it is unlikely to hold (not that they could test it, given their one data point) since ASs may add routers or replace them.

XORs in the Air

This paper extends the idea of using the broadcast nature of the wireless medium by adding another source of optimization: routers can encode packets if they know that the next hop can decode the packets; a router can know this by listening in on other transmissions. This basically allows the algorithm to increase the theoretical capacity of the wireless links, since in some cases multiple packets destined for several next hops can be sent as a single packet, given knowledge of what each destination has heard.

The routing algorithm, called COPE, eavesdrops on neighboring transmissions. Each transmission contains information about what packets that node has heard, as well as acknowledgements for packets it has received, along with the packet(s) it is transmitting (some XORed together). In some cases, it aggressively encodes packets without knowing for sure that the receivers can decode them; this utilizes ETX to figure out the forward probability of each link. One interesting thing here is that unlike ExOR, it seems all packets are sent this way and none use traditional routing (there is no arbitrary 90% metric of where to go from one regime to another).

COPE utilizes bitmaps in a number of cases to reduce the overhead of the routing algorithm. One place this occurs is in the ACKing mechanism; there is an independent link-layer ACK algorithm for COPE, necessary because the aggressive encoding may be too aggressive (and, of course, the links are shared/unreliable).

COPE for UDP increases throughput, sometimes by large amounts, depending on the particular topology. However, the major problem with COPE is that it interacts badly with TCP due to to TCP's problems with hidden nodes; COPE cannot help throughput because hidden nodes combined with congestion control gives small queues and little opportunity for coding. This weakness is pretty major, but I think that some obvious refinements may change this. For example, having TCP-awareness in the link algorithm (as in a previous paper we read) could make the ACKing mechanism of the link layer work better with TCP ACKs to avoid unnecessary congestion control.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

ExOR is the first wireless algorithm we look at that exploits the broadcast nature of wireless networks to build a new routing algorithm. In ExOR, the next hop is chosen after the transmission for that hop; that is, the route depends on who receives the message and not JUST on the current routing state of the network (as in DSDV) or the route information at the sender (like DSR). The major part of the algorithm is limiting duplicate transmissions from multiple nodes that think they should be sending the next hop; for this, each node listens to make sure any higher-priority intermediate node has not already forwarded the packet. Thus there is a tradeoff between waiting for a higher-priority routes and reducing overall routing latency.

ExOR's performance gain comes from essentially having many potential routes to choose from, unlike traditional routing which only has an all-or-nothing path for each hop. This works best when there is independent interference at each.

Looking at the algorithm as described, there's several design points that seem somewhat arbitrary. For example, the backoff when no information is available about higher-priority nodes is five packet times; I fail to see why this is a reasonable assumption, although it may work in practice. That is, there is no evidence this parameter is well-chosen. Another arbitrary number is the ultimate destination sending 10 batch map packets; again, there's no reason to expect this is optimal, nor is there reason to believe that the algorithm is insensitive to this parameter.

In their tests with UDP, ExOR improves throughput. Some of this is undoubtedly due to ExOR being able to choose paths as they are routed, but I would like to see how ExOR compares to a modified 802.11 algorithm that integrates two changes to ACKing: one, having ten ACKs sent instead of one, and second, having ACKs flow backwards to the source. I'm curious to see if the impact of these two decisions can be quantified, perhaps leading to a slight change in 802.11 routing to make it perform almost as well as ExOR.

Performance Comparison of Multihop Wireless Ad-Hoc Routing Protocols

This paper compares several different routing protocols (more accurately, it compares optimized versions of several different routing protocols) in a simulated wireless environment. It is interesting in that it is a first study of the relative performance of these protocols; I don't have too much criticism except that I'm not necessarily convinved that the protocols were "equally" optimized by the group. That is, the one that seemed most optimized is the protocol that performed best overall--- DSR.

Still, this is at least partially due to the use of source routing which seems to be a better fit than per-hop routing that some of the other algorithms use. Combined with eavesdropping, which allows state updates with less overhead, this gives each node an idea about the accessibility and route to each other node; with DSDV etc, the route information at each node is still about routes to all other nodes, but only keeps the next hop information.

The eavesdropping and caching employed by DSR are the reasons it performs best; both of these are optimizations to the original DSR algorithm.

In addition, I thought it interesting that TORA's short-lived routing loops created during route reversal lead to many packet drops; in hindsight, this seems like a poor decision in a routing algorithm (creating loops). Finally, the last interesting thing in this paper is that large packets are undesirable for the scenario used because of unfairness in MAC protocols; thus wireless routing should use smaller packets than those used in wired networks, where large packets can be desirable for amortizing the bandwidth-latency product.

HIgh-Throughput Path Metric for Multi-Hop Wireless Routing

This paper introduces a metric for discovering routes on wireless ad-hoc networks which performs better than the usual minimum hop-count metrics from wired networks. The previous paper used a metric that looked at the "expected transmission time" of a message based on the throughput and reliability of each link; in this paper, the presented algorithm refines this by looking at the expected transmission count. Unlike other metrics, this is not dependent on the momentary load characteristics of the network.

Minimum hop routing works when the shortest path is also the fastest; however, because of the characteristics of wireless networks, this is often not the case (for example, intermediate nodes in routing can interfere with acknowledgements from the previous node because transmitting the packet may override transmitting an ACK).

The algorithm looks at delivery ratios both TO other nodes and the delivery ratios of the ACKS, which is a good refinement. Based on these ratios, it decides which route to take. Because the link probes are sent at some fixed known rate, each node can calculate the delivery ratios even without full knowledge of the link state. However, I noticed this calculation could be somewhat off since the probes are jittered; couldn't this lead to artificially low ratios in some cases?

The paper analyzes adding ETX to DSDV and DSR. I thought their test methodology was a little odd because they use a snapshotted route table instead of allowing it to evolve through the test for DSDV. I'm not sure if this makes the numbers suspect, but it is something to keep in mind. Nevertheless, the measurements show ETX+DSDV is better than plain DSDV (although this may not hold if the tables evolve under heavy load...). However, ETX+DSR is not better than DSR; ETX uses rather small probes even to check for how the network route performs for large messages.

A simple modification to this algorithm could make performance better. Even doing something like using exponentially distributed probe sizes (and having them occur far apart for larger sizes) would give a better image of what the network routing actually will do for various size messages. Routes could be picked based on message size. Even using two different sizes ("small" and "large") may give a better view.

Architecture and Evaluation of Roofnet

Roofnet is a 802.11 mesh network near MIT that uses volunteers to host access points, providing multi-hop wireless links to the internet via NAT. The major goal here is to ease deployment by not constraining node placement, forcing configuration to occur automatically, and use multi-hop rather than single-hop routing to extend the footprint of the network even to nodes that by themselves do not have a wired connection. The use of multi-hop is one major difference between this network and those we have studied to date.

A custom route discovery mechanism called Srcr, is used to periodically detect best routes from an access point through the network. Although the algorithm is very simple, it seems to work, albeit in an unscalable way: the flood packets combined with the re-forwarding when new faster paths are discovered are unscalable and would probably hurt performance as the number of nodes increased or if nodes were so closely packed together that the local path explosion problem occurred (i.e. the best path keeps changing marginally because all paths are essentially equal with some jitter). Another custom algorithm manages bitrate selection, using heuristics that are not the same as 802.11: Roofnet will tolerate high packet loss if the obtained bandwidth is higher than a low-bitrate selection where loss is low. IIRC, 802.11 considers packet loss very bad and attempts to reduce bitrate even at the cost of overall throughput.

Interestingly, the network functions despite a number of shortcomings. For one, most paths go through the same "important" short high-speed links. Even though the network could survive losing some nodes, the loss of these most important nodes would disproportionately reduce connectivity. In addition, even in the full network, some pairs cannot route from one to another; this isn't so much of a problem if all communication is to the internet.

The major interesting result for me was the fact that this network uses the original CSMA/CA algorithm from 802.11 (not b) and has CTS/RTS disabled. It seems to me that with this kind of network, the hidden node problem would be a big deal; in fact that was my first thought when the network was described in section 2. However, their experimental results show that CTS/RTS doesn't help at all.

I would like to know why this is: it seems counterintuitive. Is it due to the particular implementation? I believe the CA part of CSMA/CA implements essentially what DS does, so perhaps CTS/RTS is redundant here. Still, it would be interesting to see how prevalent the hidden node problem is on their network and whether 802.11's CA is sufficient.

Modeling Wireless Links for Transport Protocols

This was an enjoyable paper about shortcomings and suggestions for improvement in previous work that modeled the performance of transport layers on wireless links. The paper begins by describing cellular, WLAN, and satellite networks and their various parameters; in this section, the cellular traffic is considered mostly to be WAP/low-BW internet access. Although this is reasonable for the time the paper was written, this is definitely changing with first-class browsers appearing on modern cellular networks; the traffic overall in the cellular networks probably looks like some mix of WAP-like and HTTP-like traffic (I assume that browse-over-proxy such as Opera Mini looks something in the middle of the two, but probably not entirely dissimilar).

The paper goes on to cite specific shortcomings in some previous models, with a range of egregiousness. Some are extreme: 40% packet loss, for example is one thing cited here (but I disagree with this paper: it is realistic since the subsequent paper we look at has similar loss rates). I was very surprised that some studies considered symmetric models for WLAN, given the inability of radio to send/recv at the same time (a physical limitation, I believe).

Lastly, the most useful sections were about modeling the various aspects of wireless links. In particular, these sections are well-organized, describing the effects, whether modeling them is important, and how to model them. I believe one simple modification to their On-Demand Resource Alloc model would make it more realistic: it seems that introducing a variable delay would make the latency spread out in the model as it does in the measured data; a simple uniform random delay between two thresholds seems enough.

Overall, the paper was very useful in helping understand issues of wireless link layer protocols and some of the ways they interact with the transport protocols. This even helped make the previous readings more clear.