# Game Theory-Based Load-Balancing Algorithms for Small Cells Wireless Backhaul Connections +
## 2 Materials and Methods
### Reference Load-Balancing Algorithms
#### 2.3.1 The Round Robin Reference Load-Balancing Algorithm  
This algorithm represents the simplest scheduling algorithm used in packet switched networks. In this case, it was converted into a LB algorithm over parallel tunnels as it is described below by Algorithm 4.  
```
Each new data flow initially is associated with default tunnel \(j=1\)
1:if\(f_{i}\) is a new flow
2: identify the last used tunnel \(z\leq N\)
3: select the next tunnel: \(z=(z+1)\text{mod}N\) and send flow \(f_{i}\) on tunnel \(z\)
4:endif
```  
**Algorithm 4** Round Robin Load-Balancing Algorithm  
This algorithm does not consider either the capacity of the tunnels or the characteristics of the flows, i.e., type of flow, bit rate, etc. The transfer rate on a given tunnel necessary to transmit all the packets routed on that tunnel could be significantly larger than the capacity of the tunnel, which will have consequently low performance.  
2.3.2. The Multiple Knapsack Reference Load-Balancing Algorithm  
The Multiple Knapsack algorithm tries to distribute a set of items on a set of containers, called knapsacks. Each knapsack is characterized by its capacity, and the knapsacks represent the tunnels in our scenario. Each item is characterized by a weight parameter and a value or utility. The items are representing in our scenario the flows, characterized by an average rate (weight) and a priority (utility). The algorithm tries to distribute the items on the knapsacks in such a way as to maximize the total utility while fulfilling the capacity limitations of the knapsacks [41; 42].  
The variant of this algorithm which was implemented and simulated is described by Algorithm 5 blows  
```
1: Each new data flow initially is associated with default tunnel \(j=1\).
2:do
3: compute the priority of the new data flows.
4: sort the flows in descending order of their priorities.
5:if flows \(f_{1}\), \(f_{2}\),... \(f_{k}\) have the same priority
6: sort flows \(f_{1}\), \(f_{2}\),... \(f_{k}\) in ascending order of their average bit rate.
7:endif
8: route the sorted flows on the available tunnels while fulfilling the conditions:
9: a. the sum rate of the flows routed on a tunnel is lower than the average capacity of the tunnel
10:endif
11: b. the sum of the priority of the flows routed through a tunnel is as high as possible.
12:while each flow is associated with a tunnel, or no tunnels are available
13:if flow \(f_{i}\) does not fit on one of the tunnels
14: check if it fits into one of the other available tunnels.
15:endif
16:if flow \(f_{i}\) cannot be routed over either of the tunnels
17: flow \(f_{i}\) will be routed over the default tunnel or will be rejected.
18:endif
19:endif
20:endif
21:endwhile
22:enddo
```  
**Algorithm 5** Multiple Knapsack load-balancing algorithm  
In what concerns the priorities of the flows, five classes were considered: class 1-gaming, video conferences, class 2-video streaming, class 3-voice over IP, class 4-web browsing using HTTP, and class 5-best effort FTP. In a simpler approach, the flows can be classified into only two classes, i.e., real-time with high priority and non-real-time with low priority. This algorithm works at flow level (not at packet level), and it is executed when a new flow is generated, or when a predefined timer expires, or the parameters of the networks (e.g., the quality of the wireless links) change significantly.