Integrating network structure and dynamic information for better routing strategies on scale-free networks

Abstract

For certain scale-free networks, different presupposition of packet generation rate can result in different transmission performance. In this thesis, we study the information traffic in Barabási-Albert scale-free networks where the information generation rate varies with time as a periodic function. We observe that when the fluctuation in packet generation rate increases, the average transit time increases and network performance degrades. In order to improve the transportation efficiency in this situation, we propose a new routing method called mixed routing. It operates in two modes: 1) when the packet generation rate is small, we use the shortest path to deliver the packet to the destination; 2) when the packet generation rate is large, the traffic load in central nodes are redistributed to other non-central nodes, using the so-called efficient routing method. We find that the time shifting between the two modes is very critical for the routing performance. In this thesis, we provide an efficient method to determine when to shift the routing modes in order to obtain good network performance. Moreover, we study information packet routing processes on scale-free networks by mimicking the Internet traffic delivery strategies. We incorporate both the global network structure information and the local queuing information in the dynamic processes. We propose several new routing strategies to guide the packet routing. The performance of the routing strategies is measured by the average transit time of the packets as well as their dependence on the traffic amount. We find that the routing strategies which integrate both global network structure information and local dynamic information perform much better than the traditional shortest-path routing protocol which takes into account only the global topological information. Moreover, from comparative studies of these routing strategies, we observe that some of our proposed methods can decrease the average packet transit time but the performance is closely dependent on the total amount of traffic, while some other proposed methods can have good performance independent of the total amount of traffic with hyper-excellent average packet transit time.

Date of Award	2 Oct 2009
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wing Ming Eric WONG (Supervisor)