# A Mathematical Model for Efficient and Fair Resource Assignment in Multipath Transport
## 2 Terminology
### Resources  
The following definitions of the resources are illustrated by the example in Figure 1. The blue circles identify the interfaces, the small grey dots attached to the nodes are the interfaces. The black arrows and numbers denote the links with their capacities in Mbps.  
**Definition 1**.: _Network: A network is a directed graph specified by_  
* _A set of nodes_ \(V\) _in the example network in Figure_ 1_--the nodes_ a to_ e_._
* _A set of interfaces_ \(L\) _that is greater than or equal to the number of nodes in the network. Each node has at least one interface, and each interface can only be part of exactly one node. In Figure_ 1_,_ \(L\) _is formed by the interfaces_ \(a1\)_,_ \(a2\)_,_ \(\dots\)_e_._
* _A connectivity matrix with elements_ \(cap_{ij}\geq 0\)_,_ \(i,j\in L\)_. If_ \(i,j\) _are directly connected by the same link, then_ \(cap_{ij}\) _specifies the link capacity in the direction from_ \(i\) _to_ \(j\)_; otherwise,_ \(cap_{ij}=0\)_. If_ \(i,j\) _belong to the same node, it is assumed that_ \(cap_{ij}\to\infty\)_. This means that nodes which act as forwarders, which could in practice be e.g., routers, are assumed to have infinite processing capacity--bottlenecks only occur on the links between nodes, but not inside the nodes. The connectivity matrix for the example of Figure_ 1 _is given in Table_ 1_. Empty elements have a value of 0 that is omitted for better overview._  
The definition of a network raises the question as to why the additional notions of the node and interface set are required for the definitions of the network's directed graph, besides the connectivity matrix. The reason are requirements of the linear programming formulation where interfaces have to be distinguished from the nodes.  
**Definition 2**.: _Path: When a data packet is forwarded from the sender to the receiver, it propagates across a number of nodes resp. their interfaces. A path is defined as the sequence of interfaces which the packet passes while being forwarded. The first interface of the path is the one of the sending node, the last one is the receiving node's interface._  
_The bandwidth of a path is the bandwidth of the path's slowest link, i.e., the \"weakest link in the chain\"._  
In the example of Figure 1, node a is the sender and node e the receiver. There are two possible paths \([\mathrm{a},\mathrm{b},\mathrm{d},\mathrm{e}]\) and \([\mathrm{a},\mathrm{c},\mathrm{d},\mathrm{e}]\) which are identified by the red and green arrows, respectively.  
**Definition 3**.: _Bottleneck: A link whose capacity is fully utilized by flows or subflows limits the speed of at least one (sub)flow. Such a link is called a bottleneck._  
In Figure 1, the path \([\mathrm{a},\mathrm{b},\mathrm{d},\mathrm{e}]\) is bottleneck by link \((\mathrm{a},\mathrm{b})\) which has a capacity of only \(10\,\mathrm{Mbps}\). Path \([\mathrm{a},\mathrm{c},\mathrm{d},\mathrm{e}]\) is bottleneck by link \((\mathrm{d},\mathrm{e})\) which allows a maximum \(30\,\mathrm{Mbps}\). Out of this capacity, \(10\,\mathrm{Mbps}\) are already used by the data transport via path \([\mathrm{a},\mathrm{b},\mathrm{d},\mathrm{e}]\) so that only \(20\,\mathrm{Mbps}\) are left.