Shortest path routing algorithms dominate the Internet, but have their limitations that degrade the network performance as the traffic load is increasing. Shortest path routing may cause congestion on certain links while other links remain underutilized. Two-phase routing algorithms can reduce congestion due to adverse traffic patterns by means of load balancing. In this paper, we present the performance of two-phase routing algorithms in real wide area network topologies, and regular topologies typical for data centers. Also, we will analyze the influence of load balancing on goodput of TCP transport protocols in datacenter networks.

In this paper, a practical routing protocol that maximizes the guaranteed node traffic loads in reliable networks is designed and analyzed. The derived node traffic loads can be routed for every traffic pattern, and regardless of the possible single node or link failures. First, it is described how load balanced shortest path routing (LB-SPR) can be optimized to maximize the value of the guaranteed node loads. By assigning the node weights which are fed into the linear program for the routing optimization, different network nodes can be guaranteed different traffic loads, according to their estimated demands. Then, the throughputs of the reliable networks using LB-SPR are determined. The obtained values are compared with the throughputs of the reliable networks using the regular shortestpath routing. The analysis is performed for the real networks, and the regular network topologies, and it is shown that the use of LB-SPR can significantly increase the network throughput.

The Internet traffic is growing, and its nature changes because of new applications. Multimedia applications require bandwidth reservations that were not needed initially when the file transfers dominated the Internet. P2P applications are making traffic patterns impossible to predict, and the traffic loads generated at nodes need to be routed regardless of the traffic pattern. When the guaranteed node traffic loads are known, bandwidth reservations can be made simple as will be explained in the paper. The shortest path routing (SPR) protocols used on the Internet today do not maximize the guaranteed node traffic loads, and do not provide scalable and fast bandwidth reservations. Load balancing can improve the network throughput for arbitrary traffic pattern. In this paper we analyze and implement a routing protocol that is based on load balancing and a commonly used shortest path routing protocol, and is, consequently, termed as LB-SPR. LB-SPR is optimized for an arbitrary traffic pattern, i.e. it does not assume a particular traffic matrix. Optimization assumes only the weights assigned to the network nodes according to their estimated demands. It will be shown that the optimized routing achieves the throughputs which are significantly higher than those provided by the currently used SPR protocols, such as OSPF or RIP. Importantly, LB-SPR calculates the guaranteed traffic loads and so allows fast autonomic bandwidth reservations which are the key for the successful support of triple-play applications, including video and audio applications that require high QoS. An actual modification of the TCP/IP stack that includes LBSPR is also described. Using the signaling mechanisms of the OSPF protocol, the information needed to perform the routing optimization is automatically distributed among the network nodes whenever the network topology changes. The LB-SPR implementation is validated on a sample network using a popular virtualization tool - Xen.

In this paper, we propose the oblivious routing scheme based on shortest-path routing and load balancing. We present the LP model that finds the optimal routing. Then we compare the performance of the proposed scheme with the performance of the shortest-path routing for some regular and real-case network topologies. We show that the proposed routing strategy allows to achieve higher guaranteed traffic from/to a node in the network, compared to the case of the classical shortest-path routing.