# A Mathematical Model for Efficient and Fair Resource Assignment in Multipath Transport
## 3 Mathematical Model
### MINLP Model without Fairness  
The objective function, in case no fairness is considered, only specifies the aggregate throughput of all flows in the network. It does make use of multipath transport for a given flow, but only if a higher aggregate throughput for the entire network can be achieved. Let \(K\) be the set of all traffic demands' resp. data flows in the network. Let \([s,t]\in K\) be a flow between the stations \(s\) and \(t\) and \(\varphi_{st}\) be the capacity which is allocated to that flow. The symbol \(\varphi_{st}\) which denotes, as already said, the _assigned_ capacity to a single or multipath flow should not be confused with the _fixed_ capacity \(cap_{gh}\) of a link; they are not necessarily identical. Let \(Alloc\) be the aggregated allocation of \(K\) as shown in Equation (5):  
Figure 5: Efficiency (\(\alpha=0\)) vs. fairness (\(\alpha=1\)) example. Blue circles: nodes; black arrows: links; colored arrows: data flows; numerical values: link speeds resp. flow assignments in Mbps. Figure 6: Efficiency-fairness graph for scenario in Figure 5, based on Ref. [30]. _Aggregated allocation of all flows:_  
\[Alloc=\sum_{[s,t]\in K}q^{st}. \tag{5}\]  
In case that only the aggregated allocation should be maximized and the fairness is not considered, which is called max-flow allocation, the objective function then only consists of the variable \(Alloc\) as given in Equation (6):  
_Max-flow allocation objective:_  
\[\text{maximize}:\quadAlloc. \tag{6}\]  
The constraints for the max-flow model apply to any network with single or multipath data flows. They are also used in the fairness implementations described later where they are supplemented by fairness-specific constraints. In this section, the constraints are discussed in a textual way, the formal description is given in Appendix A. Specifically, the formulations for the general constraints independent from the allocation method are given in the Appendix A.1. The equation numbers in parentheses starting with \"A\" refer to the Appendix A. _Flow conservation constraint_ (Ref. [16]): At each node except for the communication endpoints, the number of ingoing and outgoing flows must be equal; routers do not act as source or sink (Equation (A1)). _Capacity limitation constraints_ (Ref. [16]):  
* The overall throughput on a link, summed up for all flows, cannot be higher than the physical speed of the link (Equation (A2)). * A flow can only occupy capacity on a link if the latter is part of the flow's path. The maximum available capcity is the physical speed of the link (Equation (A3)). _Path constraint:_ In a given network, there are interfaces which act as a data source while others become a data sink. The number of available paths cannot exceed the product of sources and sinks, i.e., the data between each pair of connected interfaces is transferred via exactly one path (Equation (A4)). Due to the fact that a subflow corresponds to exactly one path, the same constraint also holds for the number of subflows (Equation (A5)). _Multipath flow identifier constraint:_ In the (N)LP formulation, variables have to be specified to identify whether or not a node is part of any path between a source and a sink node, i.e., acting as an intermediate node (Equations (A6) and (A7)). Further variables identify whether a flow which makes use of a node is a multipath flow (Equations (A8) and (A9)). _Multipath subflow identification constraints:_ These constraints control a set of helper variables, where one variable exists for each combination of any subflow and any link. By means of these variables, the following constraints are enforced:  
* A multipath flow which does not use a particular link cannot have a subflow on that link (Equation (A10)). * If a link is used by a multipath flow, at least one of the subflows has to use that link (Equation (A11)). * A given subflow can occur at maximum once on a particular link (Equation (A12)). * Keep track of whether a flow has a subflow on a particular link (Equation (A13)).