# A Mathematical Model for Efficient and Fair Resource Assignment in Multipath Transport
## 3 Mathematical Model
### Extension of the Objective Function for Fairness
#### 3.2.3 Network Flow Fair Allocation (NFF)
\(cong\_group\_id_{ij}^{st}=1\) when the flow \([s,t]\in K\) shares the congested link \((i,j)\in A\) with other flows. Equation (20) means when flow \([s,t]\in K\) and all other flows \([q,r]\in K\) sharing the same congested link \((i,j)\in A\) i.e., \(cong\_group\_id_{ij}^{st}=1\) and \(cong\_group\_id_{ij}^{qr}=1\) then \(cong\_flow\_diff_{ij}^{st}\) is the sum of the allocation differences between the flow \([s,t]\in K\) and all other flows \((q,r)\in K\). After calculating the allocation differences between the same congested flow group, \(\delta_{\text{congested}}\) sums the total allocation difference of all those flows:  
\[ \begin{split} cong\_flow\_diff_{ij}^{st}&\\ &=\sum\limits_{(q,r)\in K}\mid(cong\_group\_id_{ij}^{st}\cdot( \varphi^{st}-\varphi^{qr})\\ \cdot cong\_group\_id_{ij}^{qr})\mid&\\ &\forall(i,j)\in K,[s,t]\in K,\end{split}  \tag{20}\]  
\[\delta_{\text{congested}}=\sum\limits_{[s,t]\in K}\sum\limits_{(i,j)\in A} cong\_flow\_diff_{ij}^{st}. \tag{21}\]  
Figure 8: Scenario as in Figure 7, but NFF-objective-II prevents flow \([a,d]\) from using multipath although it does not harm any other flow. Figure 10: Scenario from Figure 9, but NFF-objective-III enforces multipath for flows \([a,d]\) and \([e,h]\) and as a result restricts flow \([m,n]\). Figure 9: Example scenario for NFF with optimum allocation. Blue circles: nodes; black arrows/ numbers: links with capacities; colored arrows/numbers: flows with capacity assignments. All values in Mbps. Formulating the equation sets to identify the flows sharing the same congested link requires that all links which are congested for the flows \([s,t]\in K\) are identified. A link is said to be congested only when the link is fully utilized. In the constraints, a number of variables is defined which keeps track of whether a link is fully loaded, how many congested flows are on the link and whether these flows share the link with flows which are congested on another link. Equation (22) is the revised objective function for network flow fair allocation comparing the flows sharing the same congested link. \(\delta_{\text{congested}}\) is dependent on the allocation of flows sharing a congested link which might lead to having a smaller number of common congested links among the flows which means multipath capable flows might not use multipath in cases where using multipath would create a common congested link with other flows. Consider the scenario in Figure 11 with two flows \([a,f]\) and \([m,n]\). Allocation of the multipath capable flow \([a,f]\) is limited on link \((a,b)\) and \((d,e)\), the single path flow \([m,n]\) is limited on the link \((m,b)\). The resulting maximum allocation is \(20\,Mbps\) for flow \([a,f]\) and \(90\,Mbps\) for the flow \([m,n]\). This leads to the network flow fair solution of \(20\,Mbps\) to the flow \([a,f]\) and \(90\,Mbps\) to the flow \([m,n]\) sharing the congested link \((b,c)\). Since the flows share a congested link, their allocation difference is considered in the variable \(\delta_{\text{congested}}\) of the objective function NFF-objective-IV. \(M\) is the total allocation to multipath flows as defined in Equation (8). The value of the objective function for this allocation is \((20+90)-(90-20)+20=60\):  
\[\text{NFF-objective-IV:}\] \[\text{maximize}:\quad Alloc-\delta_{\text{congested}}+M. \tag{22}\]  
The value of \(\delta_{\text{congested}}\) is determined by a number of equations which perform the following tasks:  
* Compute the allocation on a link or if it is congested (Equations (A51) and (A52)). * Compute how many flows on a link are congested (Equations (A53) to (A55)). * Check whether a given flow shares a link with other flows (Equations (A56) to (A58)). However, if the flow \([a,f]\) uses only one path as in Figure 12 and does not use the path \([a,b,c,f]\), then flows \([a,f]\) and \([m,n]\) do not have a shared congested link which would nullify the value of \(\delta_{\text{congested}}\) and \(M\). In that case, the allocations of the flows are \([a,f]=10\,Mbps\) and \([m,n]=90\,Mbps\).