RCRT: Rate-Controlled Reliable Transport Protocol for Wireless Sensor Networks

The paper talks about a protocol that is built for applications that require the transport of high-rate data and which have got a little attention so far. But there are problems in supporting these applications which are limited radio bandwidth and these applications being loss-intolerant. The application data might be compressed to reduce bandwidth requirements but still they require reliable delivery. The protocols like these which handle voluminous data are normally seen to result in poor network performance just because of the volume of data they handle. An experiment performed is Los Angeles is cited as an example of this in the paper. This is just because of congestion as the design for such protocols is not carefully handled. Congestion in the network can lead to serious latency and eventually will lead to packet losses.

RCRT protocol is different than the already existing protocols as all the protocols studied so far either deal with one of the two issues but not both of them. The two issues being end-to-end delivery and congestion control. It seems strange to study this fact as both of these issues seem interlinked to give out a good network performance. RCRT protocol also demands the network to be able to support multiple concurrent streams from each sensor node as this seems to be the future which will make this protocol to be used widely. RCRT protocol also separates the capacity allocation policy to each node from the underlying transport mechanisms which makes this protocol to stand out.

End-to-end delivery of data and avoiding congestion control are the two basic features of this protocol. The entire protocol revolves around the sink which is the destination, also discovers the missing packets and explicitly requests them form the sensors. Sink decides that the network is congested if the time to repair a loss is significantly higher than a round-trip time. There are six goals which motivate the design of RCRT protocol which are Reliable end-to-end transmission, Network efficiency, support for concurrent applications, flexibility, minimal sensor functionality and robustness.

Three distinct Components which make RCRT different from other protocols are the Congestion detection component, Rate adaptation component and Rate Allocation component. End-to-End Reliability is one of the main features of RCRT and is implemented with the use of NACKs (Negative Acknowledgements). The design of RCRT protocol leverages the fact that the sink has enough memory to keep the track of all missing packets. The sink keeps track of sequence number of received packets and a gap in this sequence number indicates packet loss. NACKs ( which avoid ACK implosion and thus reduces overhead) are used to indicate the respective sensor node of the loss of packets. The source node overwrites its retransmit buffer once it receives cumulative ACKs in the feedback packet. The sink also maintains a list of out-of-order packets for each flow to provide in-order delivery of data packets to the application.

Feedback packets are structured in such a way that they are self-contained so even if one of them is lost, the next feedback packet will adjust the node’s rate. Feedback packet contains assigned rate r, a list of NACKed sequence numbers, a cumulative ACK and the average value of RTT for that node. Due to increase in overhead, feedback packets are sent only on one of the conditions Detection of one or more missing packets, the node is sending at a rate different from the assigned rate, a duplicate packet with an already acknowledged sequence number has been received, a feedback packet has been explicitly requested by the node (generally happens after half of the retransmit queue is filled).

Some of the issues RCRT tackles which have not been addressed in the previous protocols are of detecting the loss of last packet during connection tear-down where the sender and the sink synchronize their sequence numbers. RCRT adaptation to the network scenario will be delayed in case of bursty losses and loss of consecutive feedback packets but will eventually control the situation as it will receive one packet from at least one of the congested nodes.

The drawbacks of this protocol are not addressed in the paper and all of them are left for future work. RCRT protocol supports multiple concurrent applications but coordination between rate allocation across multiple sinks is yet to be taken care of. RCRT adjusts the total flow in the network and hence unconstrained bottleneck regions also get affected. As RCRT makes decisions on RTT timescales, the convergence time could be large in case of networks with high maximum RTT. Also since each of the nodes experience congestion for different fractions of their lifetimes, demand proportional allocation policy used by RCRT is possible but difficult to implement on a long term basis which is left to future work. Also in real world when the protocol is implemented it needs to deal with issues such as network partition which the author does not address in here.

According to an argument in the paper, "If it takes more than few RTTs to recover the losses, then the network is more likely to congest." But the paper doesn’t explain much about why it is the case. To my knowledge, it is possible that more causes will cause the packet to be delayed for which the paper does not provide much information. The paper does not test the protocol with asymmetric nodes if the nodes have different sized retransmit buffers, nodes with smaller buffers may “hog” the traffic and essentially become higher priority than nodes that are capable of buffering packets. This could impact application performance if the application is expecting to receive traffic from multiple nodes for time-sensitive analysis. In a future paper,the authors could perform tests of the lifetime of the sources, as well as the sinks. I would assume the sinks would either have larger batteries or be connected to a constant source of power. Although reliability is an important factor in transporting large blocks of data, long battery life is an important feature that was not addressed.

Week 6: Typhoon

Typhoon: A Reliable Data Dissemination Protocol for Wireless Sensor Networks

Chieh-Jan Mike Liang, Razvan Musaloiu-E., and Andreas Terzis

We review Typhoon, a protocol developed at Johns Hopkins for disseminating large objects quickly and reliably. Typhoon reduces contention and promotes spatial re-use by combining spatially-tuned timers, prompt retransmissions and frequency diversity. The cornerstone of the Typhoon protocol is its use of snooping and channel switching to minimize transmissions/retransmissions and reduce collisions/contention, respectively. Channel switching was especially effective in order to avoid traffic generated on the default channel by hand-shaking and by Trickle- the protocol implemented on top of Typhoon to disseminate meta-data. Typhoon is ACK based, utilizing the stop-and-wait ARQ protocol, which is effectively a sliding window protocol with a window size of one. Typhoon is compared against Deluge, a NACK based protocol. Deluge is the de-facto standard for disseminating large objects in TinyOS. Through testing, Typhoon proved to be more efficient than Deluge by reducing dissemination time and energy consumption by up to three times.

The general purpose of Typhoon is to disseminate large objects, for example source code updates which are usually between 50-100 KB in size. Typhoon handles these large objects by first breaking them into 1 KB pages. The pages are then split up into packets and sent over the wire. The stop-and-wait ARQ protocol means individual ACKs are sent for every packet. Because of this, the amount of time that goes by where a packet is lost without being retransmitted is small. Deluge uses a NACK based protocol, and it waits until the entire page is sent to NACK individual packets. When contrasted against Deluge, the class found that Typhoon benefits greatly from its quick ACKs as opposed to Deluge's slow NACKs. Typhoon also uses Trickle to disseminate meta-data on the default channel. Typhoon's only other transfers on the default channel are the node handshakes, after which nodes will go to a different random channel to begin transmitting data. This is the channel switching that the paper introduces. The class noted that some channels will have different properties such as link quality and contention than other channels, and so the channel randomness plays a critical role in the success of Typhoon. There is only one transmitter and one explicit receiver for each data transfer, although there may be other implicit receivers that snoop on the data transfer. They hear the PageOffer with the channel number and silently switch to that channel and collect the data that is sent. If any packets are lost, though, the entire page is discarded (since implicit receivers don't send ACKs). This is referred to as Typhoon's all-or-nothing snooping approach.

The class discussed the pros and cons behind Typhoon's all-or-nothing snooping approach. Some students believed that Typhoon would reduce a great amount of transmissions if snooping nodes were able to temporarily store the pages with missing packets, instead of unequivocally discarding them. In certain scenarios where a snooping node may only be missing a small number of packets from a page, the students argued it is very likely that ensuing snooping opportunities would involve that same page. This is because of Typhoon's wave-like dispersal, where nodes in close proximity are likely to require the same pages. The nodes with the unfinished page could then snoop on these ensuing transmissions (which would take place anyway) and acquire the missing packets. This would minimize the number of PageOffers and subsequent transmissions, and hopefully the number of necessary snoops to acquire a full page. The downside of this approach is the requirement that nodes store unfinished pages in their memory, which is minimal in the first place, and to keep track of which pages are unfinished and which packets they are missing from that page. The class came to the conclusion that it thinks the added complexity of this protocol modification is small compared to the benefit in speed and data reduction that Typhoon would receive from it.

The class also criticized the comparison of Typhoon in four modes:

• snooping and channel switching

• channel switching only

• snooping only

• neither snooping nor channel switching
  

The class made the observation that Typhoon was specifically designed to optimize its benefit from snooping and channel switching, and so to turn any of them off and then compare against the outcome is almost useless. The class did find the first two cases useful, as it showed the benefit of snooping for this particular protocol, and so we can weigh this benefit against the high data overhead that is mostly incurred from snooping. On the other hand, the class did not find the last two bullets useful at all. The class felt that snooping was more of an enhancement to channel switching, and that channel switching was essentially the backbone of the protocol, so providing data for Typhoon using snooping only or neither snooping nor channel switching was pointless and misleading. This is because without channel switching, all data is sent on the same channel, and considering Typhoon's aggressive behavior this would result in a disastrous protocol. The class argued that instead of contrasting snooping only, the authors should have compared the results against other full protocols that do not use channel switching or channel switching with snooping.

The class discussed the Trickle protocol in-depth because the authors did not go into it much, being that it was not the primary topic of the paper. The class commented on the fact that Typhoon waited some amount of time for Trickle to finish before starting up. The class believed that it makes sense to wait until Trickle has done its job before Typhoon starts up, because the nodes need to know what data they need in order to work properly in Typhoon (i.e. a node will know to send a PageRequest when they get a particular PageOffer). The class also wondered whether any other meta-data could be passed around in the Trickle phase, such as network typology data. The class believes that if network topology data can be quickly pushed to each node (perhaps only data regarding upstream links since Trickle disseminates downstream) then each node in Typhoon could more optimally get the data it needs. An example of such an ideal scenario would be a node avoiding a connection with a weak link neighbor because the node has many other stronger link neighbors at the same level of dissemination as the weak link neighbor.

The class also noted that the testbed experiments were very limited in scope. The authors compared Typhoon against Deluge with the CSMA MAC protocol using default values. The experiments were carried out in an office building where there was a notable bottleneck in the middle. The class argued that Deluge may not have been tuned best for that environment, whereas Typhoon was most definitely tuned correctly to showcase its best results.

Week 5: Presentation and Discussion of "Collection Tree Protocol"

O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis
SenSys 2009


This paper presents a collection tree protocol in wireless sensor networks -- CTP Noe, which has three contributions: first of all, it introduce two key principles, adaptive beaconing and datapath validation, to solve two tricky problems of routing in sensor networks, link dynamics and transient loops; second, it describes the design and implementation of CTP Noe; third, it provides a comparative study by estimating CTP Noe on 12 different testbeds.


We discuss a key problem first -- why collection preforms well in controlled situations yet poorly in practice? To know the reason, the authors have done some previous research on that, e.g., "An Empirical Study of Low Power Wireless" and "Four-bit Wireless Link Estimation". In short, the reason of this problem is that we don't understand low power link layer well or our model about it is impractical. On the one hand, current protocols typically use periodic beacons which can't adapt dynamic low power wireless link. On the other hand, rapid link topology changes bring transient loops which cause losses in data plane or long periods of disconnection. Previous solutions have to discard packets or pause the data transmission until next beaconing period. Why? Because in these solutions, topology repairs happen operates at a time scale orders of magnitude longer than data plane. So the authors' goal is to design a collection tree protocol which can adapt its beaconing rate efficiently and agilely, meanwhile, repair topology rapidly to avoid discarding packets and pausing the data transmission with a long time.


CTP Noe gives us a good solution with two mechanisms: datapath validation and adaptive beaconing. Datapath validation makes sure the routing protocol can update the stale datapath information in good time by using data packets. Adaptive beaconing increases agility and efficiency -- sending very few control beacons when the topology is consistent and quickly adapting when the datapath discovers a possible problem. With these two mechanisms, CTP Noe does not need to directly drop packets or pause a long time when meeting loops. How to achieve that? We discussed the reason at class. When transient loops occur, CTP Noe will decrease its beaconing interval to the lowest immediately which make it can repair the datapath at once. So packets only need to be paused for the length of the minimum beacon interval. However, former protocols, such as MultipleLQI and DSDV, can not achieve this, because fixing the datapath needs a long time. They have no choice: either drop or overflow.


Going in thorough details of implementation, we talked about several components in control plane and data plane. CTP Noe defines three events to trigger the beacon interval resetting: 1. P bit equals one; 2. cost drops significantly; 3. a topology inconsistency has been detected. We discussed the usage of these three events. In data plane design, some students misunderstand the concept of client queues. Actually the client here means an up-layer application or component of current sensor node. While the pool here is used to store coming packets from other sensors. Here the duplicate judgement is important because it decreases large and useless transmissions for duplicate packets from looping and false negatives of ack. For transmit timer, we discussed the reason why it needs at least two packet times between transmissions.


Finally, from all the figures and descriptions in evaluation, we can see that CTP Noe achieve reliability, robustness, efficiency and hardware independence. But in Figure 9, we don't know how to conclude that Channel 1 and 11 are most heavily used by the building occupants. 


Here's a few short descriptions from our reviews:

• The authors performed a good bit of research for the experiment, using a variety of testbeds and modifying the many of the parameters. In future tests, the authors could modify parameters that remained fixed over long periods in their tests. For example, IPI could be modified in tests instead of using fixed value. Also, nodes could be removed and reintroduced, instead of just removed(6.7). Another option is to add new nodes over some of the longer tests and look at delivery ratios.
• What happens in the event that the sink itself is intermittent?  Perhaps in a mobile ad hoc network, the sink leaves the network.  How do the nodes re‐route to a different sink? 
• It achieves the four major goals considerably but the question of this protocol being general to distance vector algorithms still remains to be answered, which on answered in the favor of collection protocols will take these protocol into much wider applications.

W4:A-MAC

Presentation Summary for “Design and Evaluation of a Versatile and Efficient Receiver-Initiated Link Layer for Low Power Wireless”


The paper proposes a new prototype link layer protocol for low power wireless communication. The key objective of the design is to minimize power use. The important idea behind the protocol is that receivers send periodic probes periodically. When a sender has a packet for that receiver, it responds to the probe with an Auto-ACK packet, which is generated by the hardware. The sender then waits a short, random period of time and then sends over the data payload. The receiver then sends another probe once the packet has been received, indicating the previous packet has been successfully received.

The novelty of this design is that it takes advantage of the auto-ack design of IEEE 802.15.4 standard to improve the efficiency of the protocol. Using the hardware ack mechanism, the A-MAC reduces the turnaround time from approximately 3.75ms (Compare to Ri-MAC) to exactly 192us, preventing overhearing of irrelevant nodes. In addition, the authors presents their discovery that if multiple acks are sent by multiple senders, as long as the path delay difference is less than 500ns, do not causes destructive collide and can be received successfully. This second advantages improves the efficiency and interference–resistant when there are environmental wireless interference source around, such as a 802.11 AP.
They also implemented variants of the protocol for broadcast and network wakeup. For broadcast, a sender waits for and acknowledges the probes from all of its neighbors and then sends the packet respectively. For wakeup, two approaches are given. The first is to use the same protocol is used to send for wakeup messages. However, the process is much slower as nodes send probes at a much lower rate when not awake. The second approach is to have a reserved broadcast address. This however, violates the 802.15.4 standard and is not supported by all hardware. The paper also presents a pollcast implementation.
The paper then presents many results of experiment showing that A-MAC is indeed power efficient and reliable, including multiple Ack robustness experiments, 802.11 interference experiments and micro and marcro- benchmarks. Results concluded that the performance is reasonable.

Students of CS450 discussed multiple topics about this paper:

1. When multiple senders want to send multiple data packets to the same receiver, it may repeat contentions. For example, when Node S1 and Node S2 want to send packet to node R, they both wait and answer the R’s periodical probe, send auto-acks and send data packets. Data packets will certainly cause contention, and then R declares a probe with contention window.S1 and S2 respectively flip coins and choose its backoff times. Let’s assume S1 timeout first and resent data packets. When S1 finishes sending the first data packet, R sends a probe in responding to S1. It is unclear that what S2 will do at this time. If S2 here reset itself and answer to the probe with auto-act and then send its packet, it is surely to cause contention once again, which means each data packets either from S1 or S2 will cause a new contention or even worse, increasing contention window. On the other hand if S2 does not reset at the arrival of R’s probe that replies S1’s data packet, S2 will wait until S2 timeouts, which is a suboptimal solution.

2. The disadvantage of receiver-initiated protocols is that because of periodic probing, their channel utilization scales with node density and probe frequency rather than strictly with traffic. Packet delivery ratio drops noticeably with increase in density and decreasing probe intervals.