Enhanced approach on solving Online Knapsack Problem to improve Load Balancing

Distributing data flows of given bandwidth between various disjoint network paths of given bandwidth capacity, is a non-trivial task when the flows are considered unsplittable, thus we cannot send its packet via different paths, but all packets of a flow must be transmitted within the same path. This problem can be described as a modification of the well-known Knapsack problem. In this paper, we solve the Knapsack problem applied to resource allocation. We try to match items to individual knapsack and to use the maximum capacity of all knapsacks. Packing of items is managed by the QFLA algorithm, which tries to pack the coming item to knapsack with the biggest remaining capacity and if it is impossible then try to move items between knapsacks to make a bigger capacity of some knapsack and to place the item there. It is necessary to work in the real-time so we decided to use the structure of Binary Search Trees. It is used to keep knapsack ordered with its remaining capacity.