Research On Valiant Load-Balancing In Broadband Communication Networks

THE approach of Valiant Load-Balancing is first proposed in multi-processor interconnection networks. In the approach of Valiant Load-Balancing, each node spreads the task assigned by the distributed system to all the nodes. The traffic load for the system is balanced and the efficiency is greatly improved. In recent years, with the explosive increase of Internet traffic and the enhancement of QoS (Quality of Service) demands, for broadband communication networks it is necessary to improve and innovate the framework, the routing algorithms and the realization of core switch node, etc. Correspondingly, the approach of Valiant Load-Balancing is applied in broadband communication networks, then new idea and new method is produced. This dissertation invetigated the problem of the application of Valiant Load-Balancing in broadband communication networks, including two perspectives: (l)the Valiant Load-Balanced two-stage switch; (2)the Valiant Load-Balanced robust routing algorithm in WDM (Wavelength Division Multiplexing) optical networks.The Valiant Load-Balanced switch consists of two stages. The first stage connects the inputs and the intermediate inputs, spreads the traffic uniformly among the intermediate inputs. The second stage connects the intermediate inputs and the outputs, finally transmits the traffic to the outputs. The Valiant Load-Balanced switch is simple to be scalable and has been proved to provide 100% throughput. However, in its basic fabric, the Valiant Load-Balanced switch mis-sequences the packets. In chapter 2, the author proposes an algorithm called BPS (Blank Packet Stuff), which maintains packet order by stuffing the blank packets to the full frame in the two-stage Valiant Load-Balanced switch and has excellent switching performance (in terms of mean delay and throughput). This algorithm is distributed and each port can operate independently.In WDM mesh networks, traditional static/dynamic routing and wavelength assignment (RWA) algorithms are based on an explicit knowledge of the traffic demand/traffic rate matrix, but in practice it is difficult to predict traffic pattern of each source-destination pair accurately. In chapter 3, the author investigates the problem of Valiant Load-Balanced robust routing algorithm under the model of polyhedral uncertainty (i.e., hose model) of the single-granularity lightpath connection requests (i.e., The bandwidth of the connection requests is equal to that of one wavelength) for WDM mesh networks. The research includes three perspectives. (1)For the static hose uncertainty model of WDM mesh networks, considering the optimization problem of minizing total network cost, the author presents the mathematic formulation (ILP, Integer Linear Programming), and proposes MRUF(Maximizing Resource Utilizaiton First) heuristic algorithm. MRUF algorithm calculates the traffic distribution fraction based on the maximization of the resource utilization, and consturcts the full-mesh virtual topology on the physical network. All traffic matrices under the static hose uncertainty model can be efficiently routed on the virtual topology. (2)Considering the problem of Valiant Load-Balanced robust routing in resilient WDM mesh networks, the strategy of dedicated-path protection is used. The author proposes TMRUF (Two-Step MRUF) heuristic algorithm. Simulation results shows TMRUF algorithm has the lower total network cost with the robust protection. (3)The author considers the problem of robust routing under the dynamic hose uncertainty model for the full-mesh logic optical network architecture. The author proposes a novel dynamic routing algorithm-LBADF (Load Balancing with Adjustable Distribution Fraction) based on Valiant Load-Balancing. LBADF algorithm can instantly adjust distribution fraction according to the number of the spare wavelengths on the links to optimize the performance of the network. LBADF algorithm has the lower blocking probability for the whole network than that of VLB (Valiant Load Balancing) algorithm, which has the fixed distribution fraction. And the maximum blocking probability for all the node pairs in the network can also be reduced correspondingly in LBADF algorithm.In WDM mesh networks, traditional traffic grooming algorithms are based on an explicit knowledge of the traffic demand matrix, but in practice it is difficult to predict multi-granularity traffic patterns of each source-destination pair accurately. In chapter 4, the author investigates the problem of Valiant Load-Balanced robust routing algorithm under the model of polyhedral uncertainty (i.e., hose model) of the multi-granularity connection requests (i.e., The bandwidth of the connection requests is not identical, and is less than that of one wavelength) for WDM mesh networks. The research includes two perspectives. (1)For the static hose uncertainty model of WDM mesh networks, the objective is to minimize total network cost. Considering there exists multi-granularity connection requests in the network and the connection request is not divided into sereval low-speed connection requests, the author proposes hose model separtion method to separate the hose uncertainty model into several sub-hose models according to the granularities of the connection requests, and calculate the traffic distribution fractions for the sub-hose models of different granulaties, respectively. The IMRUF(Improved MRUF) heuristic algorithm is proposed and evaluated. (2)Considering the optimization problem of maximizing hose model throughput, the author proposes SBR&MRUF (Shortest Balanced Routing&MRUF) heuristic algorithm. SBR&MRUF algorithm selects the shortest path for the short-distance node pairs, and selects the balanced routing path for the long-distance node pairs. Therefore SBR&MRUF algorithm has good network performance.In chapter 5, the author considers the problem of building cost-effective mesh networks which robust to the hose uncertainty model. The objective is to seek the minimum cost networks that can carry the class of hose demand matrices. The author compares several architectures that support the oblivious routing for the hose uncertainty model including traditional single-hop architecture based on a circuit switched core infrastructure, multi-hop (packet-switched) architecture based on point-to-point circuits in the core, and new Valiant's Load Balanced two-hop architecture; and proposes the NSRLB (Non-Uniform Selective Randomized Load Balancing) oblivious routing algorithm for the Valiant's Load Balanced two-hop architecture. The NSRLB algorithm has the advantage in terms of delay and jitter, and achieves the cost reduction over all architectures, including single-hop VPN tree, multi-hop VPN tree, and two-hop randomized load balancing and selective randomized load balancing.To verify and evaluate the proposed algorithms in this dissertation, simulation platform software using discrete event simulating methods is developed. And base on platform, the performances of all proposed algorithms are evaluated. Important data structures and some pseudo codes are given in chapter 6. Conclusions follow at the end of this dissertation.