Wednesday, October 7, 2009

22. A Performance Comparison of Multi-Hop Wireless Ad hoc Network Routing Protocols

This paper describes a wireless networks without fixed access points. This point-to-point connection is commonly refered to as ad hoc network. Four design choices were compared, namelyu, DSDV, TORA, DSR, and AODV. An extended version of ns-2 network simulator was used to test these different designs.

Each node in this infrastructureless network is linked by a single physical channel, and the power level where the packet was received is compared to two values,

sent to MAC layer
------------------ value 1) carrier sense threshould
packet error
------------------ value 2) receive threshould
noise

Distributed Coordination Function (DCF) is implemented to model the medium access control. it is similar to MACA and MACAW which use physical carrier sense and virtual carrier sense to reduce collisions.

Four protocols compared through topology change, see how packets react to it:
  • Destination-Sequenced Distance Vector (DSDV): hop-by-hop distance vector. All nodes broadcast routing updates.
  • Temporally-Ordered Routing Algorithm (TORA): "link reversal" discover routes on demind, sometimes longer routes are used to avoid discovering new routes.
  • Dynamic Source Routing (DSR): complete list of nodes it passes through
  • Ad Hoc On-Demand Distance Vector (AODV): combination of DSR and DSDV. combines 1) DSR: route discovery and route maintenance; 2)DSDV: hop-by-hop routing, sequence #s, perodic beacons

21. A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper is trying to solve the connection problems on multi-hop wireless networks like the previous paper on Rooftop network. But instead of having the antennae on the rooftops, this time it is placed in a university building with 29 nodes totally. The authors didn't really mention how they chose the locations of their hotspots, however. And they put it clear that mobility of these wireless access points are not put into consideration.

The factor they are trying to change in the 802.11b network this time, is the hop counter for routing protocols. It uses an Expected Transmission Count (ETX) which incorporates the ideas of:
  • masking transmission errors, so that all but the worst connections appear loss-free
  • finding a path with the fewest expected number of (re)transmissions
  • predicting packet loss ratios in both directions of each link, so asymmetrical link speeds are taken into consideration
  • penalizing interference between hops on multi-hop network
ETX = 1 / ( forward delivery ratio * reverse radio ), assumptions:
  1. for protocols with link-layer retransmissions, such as 802.11b
  2. fixed transmit power for the wireless
The fact that ETX does not avoid congested links makes it free from load-adaptive link delays. It also prefers paths less than 3 hops even when 4+ hops have better throughput, and avoiding wireless interference.

Wednesday, September 30, 2009

20. Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes an experimental 37-nodes wireless network in Cambridge, Massachusetts. Users volunteer to install an antenna on their roofs and either connect it to a home broadband connection or not. Average throughput of the Rooftop network is 627 Kbps with averaging 3 hops.

Roofnet uses a unique addressing system on top of IP addresses. A special routing protocol, Srcr, was also introduced to automatically update the routing table among different wireless access points. Since most of the links in between are rather weak, the routing must find an optimum throughput itself. This is called Estimated Transmission Time (ETT).

Roofnet also uses its own algorithm, SampleRate, to determine the bit rates of 1, 2, 5.5, 11Mbps in 802.11b network. The decision is based on actual data speed rather than periodic probes.

Comments:
  • The beauty of this system is that, you don't need elaborate planning ahead where to put the wireless hops. The antenna is omni-directional, and software is self-configured.
  • I'm not sure if this is ever popular in the States, but there's this thing called FON, which basically gives you an almost-free wireless AP if you agree to share your existing Internet access, whether charging your users or not. And when you are out of your own FON AP, you can access others' depending on your sharing mode. This is/was very, very, very popular in Spain. Would it be possible to apply similar techniques to the FON firmware and give it a try?

19. Modeling Wireless Links for Transport Protocols

This paper provides a lot of background knowledge of wireless links and reviews several protocol solutions. As stated in previous papers, wireless networks have different bandwidth, lossy link, channel allocation delays, and asymmetrical data flows. Ad-hoc and sensor wireless networks are not discussed here, and the focus is mainly in wireless unicast transport protocols.

The main issues why TCP doesn't work well in wireless links are listed as follows,
  • packet loss is considered as network congestion, lossy link isn't implemented in a separate packet header
  • high round-trip time (RTT)
But in order to achieve interoperability between wireless and LANs, it is still beneficial to use the same TCP stack. Some error assumptions can be made on wireless links. For example, in poor GSM connections, timeouts should be rather common if running on TCP, but real world simulations show otherwise because the delay pattern is more of jitter in packet arrivals, resulting in higher values of TCP retransmit timer.

Several models are suggested so that researchers can simulate more accurately,
  • Error losses and corruption: dropping packets probabilistically on a time-based loss, or by per-packet, or per-bit
  • Delay variation: by suspending data transmission.
  • Packet reordering: swapping two packets in the queue at a given time
  • On-demand resource allocation: giving and additional delay when packets arrive at queue
  • Bandwidth variation: changing bandwidth. e.g. CDMA2000 0.02-20s / 9.6~163Kbps.
  • Asymmetry in bandwidth and latency: configuring uplink/downlink with different parameters for bandwidth and latency.
  • Queue: WLAN, drop-tail; satellite, RED. (large buffer causes high queuing delay and poor loss recovery; small low link utilization and frequent packet drops)
Comment: This paper provides abundant background knowledge of wireless network and ways of simulating the iffy link environment. It is also very interesting to know that handovers happen once per minute while driving in a urban area.

Monday, September 28, 2009

18. A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

In TCP protocol, packet drops are mostly considered to be network congestion. But in wireless links, they could result from iffy link conditions. TCP doesn't tell the difference between these, and drops transmission window size before retransmitting packets, and the link speed will be going from bad to worse.

Two approaches:
  • hide non-congestion losses from TCP sender, making lossy link appears as high quality link with a reduced bandwidth. AIRMAIL, indirect-TCP, snoop protocols
  • make sender aware of wireless hops and packet losses are not because of congestion, good bandwidth
Several schemes were proposed and are compared in this paper, including
  • end-to-end retransmissions: selective ACKs (SACKs), Explicit Loss Notifications (ELN)
  • split-TCP connections: hide wireless link from sender
  • link-layer proposals: hide link losses from TCP sender by local retransmissions and forward error correction on wireless links
Benchmark was measured by throughput and goodput for wired and wireless link.

Comment: Would it be possible to apply XCP on wireless link because it has an extra field of congestion level, so that packet drops of lossy link can be distinguished from congestion?

17. MACAW: A Media Access Protocol for Wireless LAN's

Wireless network is a shared environment and resource is limited. WLAN are either token-based or multiple access. The protocols discussed in this paper focus on multiple access, including Carrier Sense Media Access (CSMA), Multiple Access Collision Avoidance (MACA), and their own modification of MACA, called MACAW.

CSMA:
  • avoid collisions by testing the signal strength nearby
  • collisions occur at receiver side, not sender
MACA:
  • A Request-to-Send RTS) packet is sent before the transmission starts, and receiver respondes with Clear-to-Send (CTS) packet.
  • Upon receiving a(n) RTS/CTS, all stations defer according to the proposed data transmission length included in the packet.
  • avoids collisions at receiver, not sender
  • Binary exponential backoff (BEB): backoff time is doubled after every collision, and reduced to min after every successful RTS-CTS exchange (unfair)
MACAW:
  • add a backoff counter in the packet header to achieve fairness
  • gentle adjustment when there's a collision (1.5x and -1, Multiplicative Increase and Linear Decrease, MILD)
  • multiple stream model to be fair among uplinks and downlinks
  • basic message exchange (802.11)
Comment: The idea of adding an ACK in RTS-CTS is great, and their high throughput / fair allocation lives up to the trend of today's network. I just wished they had more real world experiments to proove that MACAW is, indeed, better than MACA.

Thursday, September 24, 2009

16. Understanding TCP Incast Throughput Collapse in Datacenter Networks

The unique workloads and fast connection low latency characteristics of data centers somewhat differs from what TCP was designed for in the first place. The infamous TCP incast collapse is a major problem in modern data centers. This paper analyzes the dynamics of incast and provides experiment results among different solutions.

The authors approach the incast from three perspectives,
  1. it is not limited to particular network environments
  2. causes of the problem should be identified and symptoms should be predictable
  3. modifications to TCP stack to solve it
Method: synchronized read requests 100 blocks of data from a set of 1-48 storage servers

Things that do NOT help: TCP Reno, New Reno, SACK

Things do:
  • reducing min value of RTO (but randomizing the minimum and initial RTO doesn't work, which is against intuition),
  • fine-grained OS timers for sub-milisecond RTO,
  • randomizing RTO,
  • disabling TCP delayed ACKs when possible.

Comment: I like the way they search out all current solutions, but where are the analysis results from all these different working methods to TCP incast problem?