# CoFi: Coding-Assisted File Distribution over a Wireless LAN
## 3 Coding Based Batching and Caching in CoFi
### Coding Based MAC Layer Caching
#### 3.3.1 The Relay Selection Problem  
When multiple potential relays are available for help, a relay selection algorithm must be applied, so as to avoid redundant transmissions. In the MORE multipath network coding protocol [19], a credit based algorithm is used that determines the number of coded packets each intermediate forwarder should transmit. The credit is computed at the source node in a centralized manner, based on the average quality of each link. The algorithm is applicable to mesh networks with static nodes and stable links, whose quality do not vary over a long period of time. In contrast, CoFi targets wireless LANs with possible mobile clients and varying link conditions. In such scenarios, measuring the average link quality (time-averaged packet reception rate) of all links online is infeasible due to its large traffic overhead.  
More specifically, we advocate a signal strength based on a single-relay selection algorithm. For each client, at most one relay is allowed to help by transmitting cached packets when it is experiencing severe losses. When multiple relays are available, the best is selected according to its potential. The potential of a client R as a relay for client C is defined as:  
\[P(\text{R}\rightarrow\text{C})=\min\{S(\text{AP}\rightarrow\text{R}),S(\text {R}\rightarrow\text{C})\} \tag{1}\]  
where \(S(\text{AP}\rightarrow\text{R})\) denotes the average signal strength from the AP to node R. The potential of each client C, i.e., \(P(\text{C}\rightarrow\text{C})\) equals the average signal strength from AP to itself. The selected best relay R, which has the highest potential, will be allowed to offer help for client C if and only if the following two conditions are satisfied:  
* \(P(\text{R}\rightarrow\text{C})-P(\text{C}\rightarrow\text{C})>\text{TS}\), where TS is a threshold that is used to avoid oscillation of relay selections due to instantaneous variation of channel condition. Currently, we set TS to 10 dB, which is the typical capture threshold used in wireless LANs that indicates a signal significantly overwhelms another. Our experience with the USRP programmable wireless transceiver [28] indicates that the typical variation of signal strength for a static link also lies within 10 dB.
* The packet loss rate of link \((\text{AP}\rightarrow\text{C})\) is larger than a threshold TL, which is the PHY level loss rate in a WLAN. This threshold should be set according to the typical QoS requirement of clients. In our experiments, TL is equal to the inverse of the maximum retry limit specified by the 802.11 MAC, i.e., when the PHY loss rate is larger than TL, the 802.11 protocol will suffer from low MAC level packet delivery ratio.  
Note that both the above two thresholds are hardcoded to typical values, requiring no runtime intervention.  
Figure 3: The caching scheme batch transmission and MAC in CoFi.  
The advantage of the signal-strength based approach lies in its simplicity and efficiency. Our measurement of wireless links (Section 5) indicates that most links experience a stable signal strength with small variance unless the clients move. Therefore, a few samples are enough to determine the average quality of a link. To obtain the signal strength from R to C, for instance, C only needs to overhear a number of ACKs that are sent from R and are intended for the AP. In contrast, measuring the MAC level packet loss ratio typically requires a large number of samples over a relatively long period of time.  
Existing work has mostly discarded signal strength as an indicator of the link quality [29; 30]. However, such measurements adopted 802.11 MAC layer throughput as the link quality metric. The 802.11 throughput is not in close correlation with the signal strength because of its persistent retransmission, per-packet ACK, and exponential backoff scheme. In CoFi, a single-direction transmission without backoff dominates the traffic, and the link rate is directly related with the signal strength.