## 3 FLARoute: Fair Locality Aware Routing
### FLARoute Design
#### 3.2.4 Phase 4: Fair Message Forwarding  
With respect to improving fairness without compromising throughput, FLAFord, the algorithm for making forwarding decisions in FLARoute, tries to minimize the usage of nodes with higher burden, and provides delivery backup through less burdened relays. In general, whenever \(m\), a new message, is generated at the source, and needs to be routed to \(d_{m}\), its destination, FLAFord sends \(m_{h}\), the first copy of the message, through the \"higher-utility path\" and subsequent copies, each denoted by \(m_{l}\), through the \"less-burden path\". A \"burden balancing\" mechanism further relieves more burdened nodes of messages sent through the less-burden path. Higher-utility path and less-burden path. In order to maintain the throughput of the underlying routing protocol, messages are forwarded towards popular nodes. Unfortunately, such nodes may have higher relative burden. To account for fairness, such nodes are used sparingly by allowing them to forward only a single copy of each message (i.e., the message is removed from the buffer after it has been forwarded). Therefore, for each generated message \(m\), only one copy (i.e., the first copy), \(m_{h}\), is forwarded through the higher-utility path. Allowing popular nodes to forward only one copy of each message reduces the number of messages they need to transmit, thereby reducing their relative burden as well. Definition 1 (Higher-utility path). _A node a forwards to an encountered node \(b\) the message \(m_{h}\) if and only if \(U_{b}(d_{m})>U_{a}(d_{m})\)._  
Although forwarding a message through the higher-utility path (i.e., through nodes with higher popularity) promises higher delivery guarantees, allowing only a single copy through such path may result in message loss, especially during buffer overflows. This brings about the need to provide backup via less burdened nodes, that although may require more copies to guarantee delivery, can afford more transmissions due to their lower relative burden. Definition 2 (Less-burden path). _A node a forwards to an encountered node \(b\) the message \(m_{l}\) if either of the following holds true: (i) \(\left[U_{b}(d_{m})>U_{a}(d_{m})\right]\bigwedge\left[b(B_{i})<a(B_{i})\right]\), where \(a(B_{i})\) and \(b(B_{i})\) are the instantaneous relative burdens on \(a\) and \(b\), respectively, in \(\Delta Tb_{i}\), the current time slot; or (ii) \(b(B_{i})<\left[a(G_{i})\times\gamma\right]\), where \(a(G_{i})\) is the instantaneous maximum burden estimate at \(a\), and \(\gamma\) is a percentage--we have taken \(\gamma\) as 20% as we consider burden below this value to be relatively low._  
If the encountered node has a higher forwarding utility for the destination, the first condition considers its instantaneous relative burden before forwarding the message. This way, messages are forwarded to progressively less burdened nodes while increasing delivery guarantees. Note that with PoiUtility (cf., Section 3.2.1), there is a higher availability of relays satisfying this condition, since more number of nodes with relatively low popularity (or burden) are able to participate in routing. Therefore, what is required is a way to bypass nodes with relatively high popularity (or burden)--which has been provided by the first condition. We consider nodes whose relative burden is less than \(\gamma\) of the maximum burden estimate as \"low burdened\". Hence, in the second condition, messages are forwarded to low burdened nodes, irrespective of their forwarding utility. Burden Balancing. The burden on a node increases with the number of copies it forwards for each message in its buffer. FLAFord reduces the burden on \"high burdened\" nodes (i.e., nodes whose relative burden is greater than or equal to \(\gamma\) of the maximum burden estimate) by allowing them to forward fewer copies of a single message.