# CoFi: Coding-Assisted File Distribution over a Wireless LAN
## 6 Reverse Engineering of CoFi and 802.11
### Performance from a Fairness Point of View  
In the literature of network resource allocation [36], two notions of fairness are widely adopted: Max-min fairness and proportional fairness. Consider the MAC as a bandwidth (or channel time) resource allocation protocol, then the former fairness measure essentially strives to allocate more channel time to the weak link [37; 38], while the latter allocates the link bandwidth according to the quality of each link. More specifically, with the maxmin fairness measure, a MAC protocol with persistent retransmission solves the following optimization problem:  
\[\text{max}t \tag{6}\]  
\[\text{subject to}:t\leq T_{i},\ \forall 1\leq i\leq K \tag{7}\]  
\[\sum_{j=1}^{K}\frac{T_{j}}{p_{j}}\leq R \tag{8}\]  
where \(t\) is the effective throughput of the client with the weakest link condition. It can be easily proved that \(t\leq R\cdot(T/K)=R/\sum_{j=1}^{K}x_{j}\), which is achievable when \(\forall i\), \(T_{i}=R\cdot(T/K)=R/\sum_{j=1}^{K}x_{j}\). This is exactly the asymptotic throughput provisioned by the 802.11 protocol. Therefore, we have the following observation:  
**Theorem 1**.: _802.11 MAC essentially solves an optimization problem that achieves maxmin throughput fairness._  
It is well known that maxmin fairness strives to allocate the same level of resources to all clients, thus resulting in low efficiency. This reveals the fundamental reason behind the low performance of 802.11 under unsatisfactory channel conditions.  
In contrast, with the proportional fairness measure, a MAC protocol without persistent retransmission solves the following optimization problem:  
\[\text{max}\sum_{j=1}^{K}\text{ln}\big{(}F_{j}\big{)} \tag{9}\]  
\[\text{subject to}:F_{i}\leq T_{i}^{\prime}=\frac{R}{K}\cdot p_{i} \tag{10}\]  
where \(F_{i}\) is the effective throughput that we can really get. Similar to the 802.11 case, we can solve this problem by upper-bounding the objective. The solution \((R/K)\cdot p_{i}\) is exactly the asymptotic throughput of CoFi without MAC caching. Therefore, we have:  
**Theorem 2**.: _CoFi without MAC caching essentially solves an optimization problem that achieves proportional throughput, fairness._  
In other words, high-quality links will enjoy a high throughput, while low-quality links are not starved. Such a proportional throughput measure may result in an imbalanced throughput allocation when the link qualities are different. The CoFi protocol with MAC caching offers a way to balance the throughput by replacing the low quality (AP\(\rightarrow\)client) link with a high quality (relay\(\rightarrow\)client) link. Therefore, CoFi essentially strikes a balance between the maxmin and proportional fairness measures.  
Through the above analysis, it can be seen that 802.11 and CoFi are essentially distributed approximate solutions to certain optimization problems, but the optimization objectives are different. The network source allocation problems are also equivalent to a discrete combinatorial optimization problem under certain constraints, which may be considered to solve by stochastic optimization algorithms [39; 40; 41].