06-09-2017, 11:05 AM
The routing path is at most 4 times the shortest path length and the maximum load at any node is at most 3 times that of the most balanced load algorithm without path length restriction. In addition, our routing algorithms make routing decisions only with local information and are therefore more adaptable to topology changes due to dynamic nodes insertions / deletions or due to mobility. Load balanced routing in a network, that is, minimize the maximum traffic load of any node leads to the unsplittable flows, is a well-known NP-hard problem. Finding practical algorithms remains a long-standing challenge. First, we provide a greedy routing scheme on a disk with a draw ratio of at most 2 and under which the maximum load is a factor 4 √ 2 less than the maximum load under the shortest route routing. This is the first simple routing scheme with a small stretch that has been shown to overcome the shortest route of routing in terms of load balancing. Then we arbitrarily transform a network into a disk by an area that preserves the map φ. It is shown that both the length of the trajectory and the maximum load of traffic in the original network only increase with an additional factor of d2, where d is the span of maximum length of φ. Combined with the result in a disc you again achieve both limited stretch and limited load balance ratio. Our simulation results evaluated the practical performance in both quality measures.