In this work, we develop a distributed source routing algorithm for topology discovery suitable for ISP transport networks, that is however inspired by opportunistic algorithms used in ad hoc wireless networks. We propose a plug-and-play control plane, able to find multiple paths toward the same destination, and introduce a novel algorithm, called adaptive probabilistic flooding, to achieve this goal. By keeping a small amount of state in routers taking part in the discovery process, our technique significantly limits the amount of control messages exchanged with flooding -- and, at the same time, it only minimally affects the quality of the discovered multiple path with respect to the optimal solution. Simple analytical bounds, confirmed by results gathered with extensive simulation on four realistic topologies, show our approach to be of high practical interest.
Routing is a critical component of the Internet, and as such has long been studied by the scientific community. The problem of finding a interconnecting any two nodes of a graph is solved by well-known algorithms like Dijkstra and Bellman-Ford, which have been implemented in widely deployed protocols such as OSPF and RIP, respectively. However, interconnecting nodes through a single path (typically, the shortest) does not make the network resilient against failures and traffic surges. Hence, different techniques relying on have been proposed. For instance, ECMP @cite_10 aims at balancing load over multiple paths of equal cost. In standard IP MPLS networks, the control and data planes are generally considered jointly; multipath routing is then achieved through a centralized algorithm, solving some standard multicommodity flow problem @cite_15 @cite_4 .
@cite_15 @cite_10 @cite_4
2120608001 2169246522
IP networks were designed to provide general connectivity. At their advent, routing methods focused only on finding one optimal path between given endpoints. Although many solutions to sending traffic via multiple paths have appeared over time, the majority of current IP networks are still managed to support only single-path transmissions. This survey examines various approaches which can provide multipath transmissions in existing IP networks. Firstly, the most recognizable solutions are presented, and later, less well-known proposals are introduced. We show how it is possible to realize multipath transmission in source and hop-by-hop routing, multi-topology routing, bio-inspired routing solutions, Valiant's routing, Multi-Protocol Label Switching, Software-Defined Networks, Flow-Aware Multi-Topology Adaptive Routing, Shortest-Path Bridging, Transparent Interconnection of Lots of Links, network virtualization, and Multipath TCP. Moreover, the mentioned approaches are compared, contrasted and subjectively assessed. The goal of the survey is to show that multipath transmissions can be achieved in the current IP networks and in many different ways. The Internet would be more efficient and robust if routers could flexibly divide traffic over multiple paths. Often, having one or two extra paths is sufficient for customizing paths for different applications, improving security, reacting to failures, and balancing load. However, support for Internet-wide multipath routing faces two significant barriers. First, multipath routing could impose significant computational and storage overhead in a network the size of the Internet. Second, the independent networks that comprise the Internet will not relinquish control over the flow of traffic without appropriate incentives. In this article, we survey flexible multipath routing techniques that are both scalable and incentive compatible. Techniques covered include: multihoming, tagging, tunneling, and extensions to existing Internet routing protocols. Routing protocols using the distributed Bellman-Ford (DBF) algorithm converge very slowly to the correct routes when link costs increase, and in the case when a set of link failures results in a network partition, DBF simply fails to converge, a problem which is commonly referred to as the count-to-infinity problem. We present the first distance-vector routing algorithm, MDVA, that uses a set of loop-free invariants to prevent the count-to-infinity problem. MDVA, in addition, computes multipaths that are loop-free at every instant. In our earlier work we shows how such loop-free multipaths can be used in traffic load-balancing and minimizing delays, which otherwise are impossible to perform in current single-path routing algorithms.