2008-10-09 Readings - Making the Best of Broadcast

ExOR: OPPORTUNISTIC MULTI-HOP ROUTING FOR WIRELESS NETWORKS

Sanjit Biswas and Robert Morris

Summary:

Describes ExOR, a routing + MAC protocol for multi-hop wireless networks. Basic idea is that since each transmission is broadcast, some packets may be received by far away highly lossy links. Traditional routing (ETT/ETX flavor) would not take advantage of such opportunities, and all data would go along fixed route. Key elements include a packet buffer to store received packets in a batch, a mechanism to determine what is the set of nodes that may have received the packet, a mechanism to determine which nodes actually received the packet, and a mechanism to determine which node should next transmit towards the destination. Measurements under certain contexts show it's a significant improvement over ETX.

Discusisons & Criticisms:

Yet another study done on the Roofnet platform. Basically the whole train of work would be waste if one day someone shows directional antenna > omnidirectional antenna, or someone finds something really wrong with Roofnet.

Knee-jerk skepticism re multi-hop wireless networks.

The Roofnet paper also came out at the same time as this (SIGCOMM 2005 for this and MobiComm 2005 for Roofnet). Roofnet uses ETT as a significant improvement over ETX. Why wasn't ETT talked about here?

Also, per ETX paper, ETX is highly susceptible to discrepancies between loss rate measurement packet size and data packet size. In particular, for the ETX implementation in the ETX paper, packets at 1024 bytes perform VERY POORLY. The ExOR comparison measurements here use 1024 bytes packets, without telling us whether the ETX problems noted in the ETX paper have been properly mitigated. So comparison conclusions are sketchy.

Would be interesting for them to present the "average" hop count reduction that ExOR makes. From the Sally Floyd wireless modeling paper, we know that any intermediate transmission should be minimized because wireless is by nature not duplex.

Reduced throughput variation was cool though.


XORs IN THE AIR: PRACTICAL WIRELESS NETWORK CODING

Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, Jon Crowcroft

Summary:

Presents COPE (never said what it stands for), a new architecture for wireless mesh networks. Basic ideal is to have a relay XOR packets and send out. Omnidirectional broadcast means XOR packets can be decoded by each sender if they know their own transmitted packet, and they're receiving an unknown packet. This would potentially cut the transmission count. Benefits of architecture can be characterized as coding gain (reduction in packet transmission needed per data) and coding/MAC gain (increased throughput due to traditional MAC fairness throttling relay send rate). Need mechanisms to opportunistically listen, opportunistically code through XOR, and learn neighbor state. Measurements on single floor wireless testbed show significant improvement for both TCP and UDP.

Discussions & Criticisms:

My standard skeptical reaction towards wireless multi-hop networks.

Also, a fundamental reservation about the overall approach. The authors showed that the traditional MAC concept of "fairness" is broken in a multi-hop context. So shouldn't the approach be redesigning the MAC instead of adding more complexity to cover up a broken MAC?

TCP losses > 10% and the thing still work? What happened to the 3% figure above which loss rate TCP basically fail and not make progress?

Good to see them use ETT routing as outlined in Roofnet paper.

Throughput was their only performance metric. Latency?

Also, their results for TCP is for an artificially compressed topology, and they themselves admit limited improvement with COPE in a real topology.

Increased RTT could push memory needs to unacceptable levels.

Overall, not sure if adding COPE is the right approach to address the problems they identified. Maybe designing a better MAC for wireless mesh would be more helpful.

2008-10-07 Readings - Routing in Ad-hoc Networks

A HIGH THROUGHPUT PATH METRIC FOR MULTI-HOP WIRELESS ROUTING

Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris.

Summary:

Presents the ETX (Estimated transmission count) metric. Motivated by the fact that conventional DSDV hop-count metric is broken - picks long links with high error rates instead of short links with low error rates. Routing packets get through in DSDV but data packet does not. ETX calculated as 1/(df x dr) where df and dr are the forward and reverse delivery probabilities, and their product is the probability that a packet is transmitted successfully. df and dr found using dedicated link probe packets, sent according to some known size and average frequency. Can be implemented by modifying DSDV and DSR. Performance is best when the network has many loss links, or transmitters have low power. For a given network, performance improve is best for multi-hop links. Discrepancy between size of link probe packets and data packets can decrease performance.

Discussions & Criticisms:

Still don't somewhat skeptical about the multi-hop wireless network concept ... Where would such networks be needed, given that we have so much wired infrastructure in place, even in 3rd world countries? Seems only needed for sensor nets and other such niche applications.

As already mentioned in their own evaluation, any time you have a transmission count based thing you would likely have issues with packet size variations. Glad to see they modified the metric to ETT (Estimated transmission time) for Roofnet.

Also, the metric solves specifically the problem of conventional DSDV not finding routes with low loss rates. What about other metrics for evaluating a routing algorithm? Overhead (for both traffic and latency)? Stability? Speed of convergence? Topology changes (either nodes moving or link quality change)?

It wasn't immediately clear that with ETX replacing hop-count in DSDV, DSDV will preserve its loop-free property.

I think the whole wireless multi-hop routing thing has gone through the typical borrow-first refine-later process. That process is pretty evident in the paper.



A PERFORMANCE COMPARISON OF MULTI-HOP WIRELESS AD HOC NETWORK ROUTING PROTOCOLS

Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva.

Summary:

Compares the performance of DSDV, TORA, DSR, and AODV protocols. Emphasize the performance of protocols under various degrees of mobility. Done in ns2 with several modification to take care of wireless link details. Movement patterns with each node move to a random destination at a constant uniformly distributed speed, and then pause for a range of discrete pause times. Nodes send at constant bit rate, and various number of nodes send for various scenarios. Figure of merit include delivery ratio, and number of routing packets (overhead). Bottom line finding: AODV and DSR performs well, DSDV and TORA not so well.

Discussions & Criticisms:

Routing skepticism re multi-hop wireless networks.

The study emphasize mobility a lot. Good thing their results extend to pretty long pause times (900 seconds = 15 minutes), else we wouldn't know the protocol performance for stable topologies. I would argue they need even longer pause times. 30 sources and 15 minutes pause time = a topology change roughly every 30 seconds - still a very very non-stable network.

Also another interesting axis to plot might be the performance vs. the speed at which the nodes moved.

Maybe the Roofnet guys need to build a car-roof net and repeat this experiment for a "real" implementation comparison. Would be more convincing than ns2 stuff.

2008-10-02 Readings - Wireless Networks in the Real World

MODELING WIRELESS LINKS FOR TRANSPORT PROTOCOLS

Andrei Gurtov, Sally Floyd

Summary:

Talks about how to model real world wireless links. Critical topic because modeling and simulation is precursor to any extensive and/or expensive field tests. Includes discussion about essential aspects of models, examples of bad models in literature, modeling various link characteristics, modeling queue management, effect on mobility, and wireless link vs. transport protocol issues.

Background:

Needs to know basic wireless 802.11 type knowledge.

Discussions and Criticisms:

Paper talks well about science. More helpful would be a operational checklist of common modeling pitfalls, and list of how to model each aspect of network. This way somebody wanting to use wireless link models can quickly reference the essential results of the work. For my own future reference, I make the list below.

Common modeling pitfalls (may apply for wired as well)

Unrealistic models:
- TCP with unrealistically high loss rates.
- Evaluating active queue management by focusing on TCP start-up.
- Assuming regular inter-packet delays.
- Constant TCP retransmission timer.
- Using deprecated TCP versions.
- Modeling WLAN as duplex.

Modeling a subset of parameter space:
- Evaluate using a single flow.
- Assume a particular link is bottleneck and not try the opposite assumption.
- Assume reserves transmission.

Overly realistic models:
- Focus on transient implementation flaws.

Lack of reproducibility (my routine complaint against a lot of methodological descriptions, far less emphasized today as it was in the early days of modern science):
- Not giving enough modeling details.

Also, list of wireless link aspects being modeled:

- Error loss & corruption.
- Delay variation.
- Packet reordering.
- On-demand resource allocation.
- Bandwidth variation.
- Asymmetry in bandwidth/latency.
- Queue management.
- Mobility.


ARCHITECTURE AND EVALUATION OF AN UNPLANNED 802.11B MESH NETWORK

John Bicket, Daniel Aguayo, Sanjit Biswas, Robert Morris.

Summary:

Talks about the architecture and realization of the Roofnet system. Key aspects of the system include totally unplanned - volunteers sign up and get antenna kit, omnidirectional antennas, use multi-hop routing, with estimated transmission time (ETT) metric - derived from estimated transmission count (ETX), which is presented in a separate paper.

Background:

Probably should read the ETX paper before this one. Also 802.11b knowledge. Maybe something about the different mesh routing algorithms would also help.

Discussions & Criticisms:

Pretty thorough performance characterization. However most of the results have no baseline for comparison - ok it's good, but HOW good is it? Not clear what should be the baseline of comparison either. Some kind of planned network? Directional antenna? Single hop to gateway? Some mixture of everything?

Tables 4 & 5 pretty valuable - comparison of multi-hop and single-hop networks.

Two key insights:
- Transmissions on multi-hops will interfere with each other.
- 802.11 RTS/CTS is BROKEN. They found RTS/CTS doesn't do what it's supposed to do, and introduces overhead. The evaluation should be repeated for other more general 802.11 settings. If results are reproduced, then we need to give general advice that RTS/CTS should be turnned off.

One evaluation that I think they missed - evaluate network performance under heavy load/utilization. Their network is utilized around 70% - for the Internet gateway i.e. - can we push it up to heavier loads? Also, scalability of gateway - all traffic funnel through gateway, so gateway = bottleneck? This will be apparent only if the network more heavily loaded.

2008-09-30 Readings - Wireless Networks Overview and Architectures

Per suggestions in class, more succinctness to help facilitate peer discussion.

MACAW: A MEDIA ACCESS PROTOCOL FOR WIRELESS LAN's

Vaduvur Bharghavan, Alan Demers, Scott Shenker, Lixia Zhang

Summary:

Talks about some pretty generic problems in wireless networks. Happened to be in the context of some network with a five letter acronym. Hidden & exposed terminal problem in vanilla CSMA. RTS & CTS interaction. Inherent unfairness and starvation of "normal" exponential back-off, pretty hacky solution (can't think any better alternative ...). Multiple stream buffers. Need for ACK, DS, RRTS messages. Multicast problems. Need for per-destination backoff. Some issues for pathological topologies unresolved.

Background:

You'd better know your basic wireless CSMA/CA stuff and maybe see some of the RTS/CTS or exposed/hidden terminal problems before. Else it's gonna be tough going like the router papers. The pictures helped though.

Discussions & Criticisms:

Review of state of the art in 802.11 stuff? How much of the paper got into the current wireless protocols?

Mobility not touched - so results valid for mobile hosts. Moving hosts? Hosts on Eurotunnel type trains? Relativistic speeds in space not allowed :)

Scalability?

If there is a shortcoming of the paper is that the simulation is not described in any depth. Thus fails the "reproduceable" criteria for experiments? Too few papers outlines their methodology in a truly reproduceable fashion anyways ...




A COMPARISON OF MECHANISMS FOR IMPROVING TCP PERFORMANCE OVER WIRELESS LINKS

Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan and Randy H. Katz

Summary:

Comparative study of several techniques for handling wireless link layer losses. Including link layer retransmit mechanisms, both TCP aware ones (snoop) and not aware ones. End-to-end TCP loss recovery, like vanilla TCP Reno, TCP New Reno, TCP SACK, SMART TCP (cummulative ACK, and seq no. of pkt that caused receiver to generate the ACK), TCP Explicit Loss Notification (TCP ELN), and TCP ELN with retransmit on every duplicate ACK. Also looked at split-connection with TCP proxy and split-connection with TCP SMART.

Bottom line - link layer TCP aware stuff with SMART is best.

Background:

Most of the required background is already provided in the paper - just need to know what the techniques are and such. The snoop paper is worth a read though. Just because it also has Randy's name on it and this paper basically says snoop rocks.

Discussions & Criticisms:

Paper claims exponential distribution error model give results that are suggestive for other error models. Why is this the case? I think one of Stoica or Shenker or Paxson's early papers provided a good justification re why exponentail arrival/loss model is fairly general, but I forgot the reason. Anyone remember why?

Another methodology question. How do we ensure we get only controlled, artificially inserted errors and not "real" bit errors coming from the wireless link?

How much of this is just a glorified measurement and comparison of the snoop protocol with other stuff? Much of the result saz basically snoop rules.

Follow up results with regard to the temporal model of wireless loss?

Changing error rate results showed each solution has critical error rate above which throughput dramatically decreases, as marked by inflection points in Fig. 12. Would be interesting to plot the vertical axis in % of achievable theoretical throughput, given the error rate, and horizontal axis extend to the left for even higher error rates. Basically vanilla TCP Reno starts sucking majorly at very low error rates.

Fundamental question re Nyquist limit - AT&T WaveLAN at 915MHz means max theoretical data rate of ~2Gbps. 802.11 is at 3.7GHz (?). Hence 7.4Gbps max theoretical data rate. So future wireless tech fundamentally limited in speed? Ethernet is moving to 10Gbps soon, and 100Gbps Ethernet in the works. Would be weird to have dramatic speed mismatch. Whole new cycle of panic -> research -> more panic -> more research? Or we solve problem with CDMA or some ingenius crap like that ...

2008-09-23 Readings - Routers

Did this NOT get published on time .... ?!?!?!?

Dude saz saved not published >.< style="font-weight: bold;">SCALING INTERNET ROUTERS USING OPTICS

Isaac Keslassy, ShangTse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ick McKeown

Summary: Talks about the architecture needed to build a 100Tbps router. Has order 10Gbps line cards. Proposes a setup where data passes through initial queues, virtual output queues, optical switching back plane, output queues. Main contribution is an argument about how the traditional cross-bar architecture just won't scale. "Speed independent" wave grating array thing really amazing - switching speed limit is no longer RC delay for buffers/lines, but Nyquist limit for modulating a light wave!

Background: Need basic router design knowledge. At least passing familiarity with cross-bars, head-of-line blocking, etc. Also some ideas about transistor circuits and optical stuff (like WDM) would be helpful.

Discussion & Criticism: Wouldn't it be awesome if the entire backbone is optical? Like optical end-to-end. With optical slow light buffers, optical switches, optical CPU (?!?!?), and electrical-optical transducers only at the end hosts.

The paper is a bit ... dense ... Had to trust that they did their due diligence with regard to proofs etc. Their "intuitive" explanations are not all that intuitive. Do router designers need to know all the stuff re transistors and optics? Really low level!!!!

Would be nice to have a photo of these things, with the line cards, cross bars etc. identified. Would be even more awesome to have a labeled photo showing a line card with all the subcomponents, like buffers etc.

This paper should be re-read after reading the 2nd paper.


A FAST SWITCHED BACKPLANE FOR A GIGABIT ROUTER

Nick McKeown

Summary: Talks about how to build a 10Gbps router. Marks the watershed from shared-bus routers to cross-bar routers (?)

Background: Need basic router design knowledge. At least passing familiarity with cross-bars, head-of-line blocking, etc. Also some ideas about transistor circuits and optical stuff (like WDM) would be helpful.

Discussion & Criticism: Wouldn't it be awesome if the entire backbone is optical? Like optical end-to-end. With optical slow light buffers, optical switches, optical CPU (?!?!?), and electrical-optical transducers only at the end hosts.

The paper is a bit ... dense ... Had to trust that they did their due diligence with regard to proofs etc. Their "intuitive" explanations are not all that intuitive. Do router designers need to know all the stuff re transistors and optics? Really low level!!!!

Would be nice to have a photo of these things, with the line cards, cross bars etc. identified. Would be even more awesome to have a labeled photo showing a line card with all the subcomponents, like buffers etc.

This paper should be re-read after reading the 2nd paper.

2008-09-18 Readings - Quality of Service

Written post-facto due to network prelim ...

FUNDAMENTAL DESIGN ISSUES FOR THE FUTURE INTERNET

Scott Shenker

Summary: Really helpful paper that frames many issues concerning the whole QoS business. Offers a game-theoretic, utility-maximization view of the goal of network design. Argues that global utility will be increased by introducing different services in the internet. Acknowledges that the increase in global utility may come at the cost of decrease in individual utility. Suggests that applications could receive services implicitly assigned by the network, or they could explicitly request services from the network. Pros and cons exist for each, no clear resolution, need pricing mechanisms to align incentives. Uses application utility/bandwidth profiles to argue for admission control. Over-provisioning seen as less cost-effect alternative.

Background: None really, just need to appreciate the network basics.

Discussion & Criticism: The paper already identified some of the potential issues. The application utility-bandwidth profiles would be hard to characterize in detail, but the general classes outlined in the paper are sufficient. However, the game theoretic argument may fall apart due to incentive mis-alignments. The biggest concern is that the global increase in utility should come at the cost of decreased utility for some users. Without any mechanism for utility transfer, there would be no incentives for the disadvantaged users to cooperate and switch to the global optimal. It's hard to imagine what utility transfer mechanisms can be usefully put in place. In business/economy, utility transfer is generally facilitated by a transfer of money. The mirror mechanism does not exist in the Internet.

Perhaps a more fundamental solution is a new architecture with better accounting abilities. Recall from the original DARPA design that accounting was of low priority.



SUPPORTING REAL-TIME APPLICATIONS IN AN INTEGRATED SERVICES PACKET NETWORK: ARCHITECTURE AND MECHANISM

David D. Clark, Scott Shenker, Lixia Zhang

Summary: Describes the architecture and mechanism of what became the Intserv standards. Has nice taxonomy of internet applications vis-a-vis their delay and adaptation requirements. Outlines to token or leaky bucket mechanism to ensure provable delay and guaranteed service. It's actually token bucket + weighted fair queueing that does the trick. Scheduling employs ideas like spreading and transferring the jitter. Hinted at the need for pricing mechanisms to support. Outlines general issues associated with the need for admission control.

Background: Network basics.

Discussion & Criticism: The paper uses a totally over-elaborate and round about way to explain the token bucket mechanism. I guess second pass explanation would always be more succinct. But haven read a succinct explanation before, I really was quite struck by the complexity of their treatment. Mathematics quite elaborate but not a problem - they're presumably checked by Parekh and Galleger. The handshake for establishing the level of needed services was deferred to a late work. Scott said QoS has been a waste of time for him ... well what can we say ... Business + practicality > technology? Or maybe another warning sign that technology done without an eye to implementation practicality will inevitably fail? Scott is awesome for butchering his own work though.

2008-09-16 Readings - Router Congestion Control

RANDOM EARLY DETECTION GATEWAYS FOR CONGESTION AVOIDANCE

Sally Floyd & Van Jacobson

Summary: Outlines Random Early Detection (RED), an active queue management scheme that works with TCP to ensure better congestion avoidance. Basic idea is to keep queue sizes low while accommodating bursts in traffic. Does so by probabilistically marking packets when queue length exceeds a threshold. Presumably TCP senders/receivers respond to marked packets by adjusting their congestion windows. Contains detailed math regarding implementation and how to adaptively estimate various parameters. Has several desirable properties - flows get notified about congestion before packet drop, flows with larger share of bandwidth get more marked packets, avoids global synchronization where all flows reduce window at the same time upon congestion, no bias against bursty traffic, etc.

Background required: Need to know basic TCP. The paper itself provides overview of other needed material like ERD, DECbit, etc.

Discussion & Criticism: Did I miss this in the paper or did they not specify the details of how the TCP end hosts respond to market packets? The marked packets continue forward to destination, requiring the destination to send marked ACKs back to the sender, so that the sender may reduce its windows. Is this how it works or do they have explicit "marked" packets going back from router to sender directly? Do they mark packets by dropping them?!?!?

Also, much of their data proves only that RED actually works and does what it's supposed to do. The comparative data with drop tail gateways are not overwhelmingly convincing. Figure 5 comparing average queue size show RED is definitely better - but what's the significance? i.e. queue length of 70 is how much slower than queue length of 20? Also, does data from Fig. 5. conflict with data in Fig. 12-14 with regard to queue length and utilization? Seems like simulation results are very topology dependent. Also, it seems RED has same efficiency as drop tail and random drop schemes, per Fig. 12-14. The fairness for bursty traffic argument is dubious - one could say bursty traffic should get incentive in the routing layer to smooth out their behavior. Also not sure Fig. 16. tells what the authors claim it tells ...

Overall not clear how much better RED is compared with drop tail or other schemes. The other paper shows that RED sucks in certain conditions.


CONGESTION CONTROL FOR HIGH BANDWIDTH-DELAY PRODUCT NETWORKS

Dina Katabi, Mark Handley, Charlie Rohrs

Summary: Outlines XCP, a new transport level protocol that works well in both "conventional" environments and environments with high bandwidth-product links. XCP relies on XCP routers in the network to give explicit feedback regarding the state on congestion. The main mechanism is a congestion header where the sender indicates congestion window and RTT, and one or more routers may modify a feedback field. The feedback is a fine-grained indication of congestion (unlike binary indication - lost packet or no lost packet), and is mirrored from the receiver back to the sender. Contains detailed math from control theory to prove stability. Comparative data with other queue management schemes are reasonably convincing.

Background: Basic TCP. Paper contains overview of other required material like RED AVQ, CSFQ etc. (CSFQ is a previous reading). Did they confuse RED with REM?

Discusssion & Criticism: One should feel it highly unconventional to have a transport protocol that totally rely on routing infrastructure. This is a fundamental shift in design philosophy. It's not clear that the benefits of XCP (relatively clearly demonstrated) is worth giving up the ability to change transport protocols without modifying the underlying routing infrastructure.

Their claim regarding the security of the protocol sounds like total rubbish. The protocol protects against the particular kind of misbehaving flows that they identified - i.e. a fire-hose flow blasting away without regard to congestion control. But, they're missing the case where someone spoofs as a router and send packets with spurious congestion headers, telling everyone else to decrease their window, and the hacker's flow to increase window. The congestion info is sent in clear text, and there's no way to verify that the routers and not some hacker modified the markings. If we're to have active networks then we've got to make sure people can't abuse the network.