Finding Alternate Paths in the Internet: A Survey of Techniques for End-to-End Path Discovery

Abstract

The Internet provides physical path diversity between a large number of hosts, making it possible for networks to use alternative paths when one path fails to deliver the required Quality of Service. However, for various reasons, many established protocols (e.g. de facto Internet inter-domain routing protocol, Border-Gateway Protocol - BGP) do not fully exploit such alternate paths. This paper surveys research into techniques for discovering end-to-end alternate paths, including those based on monitoring path performance, choosing paths that are maximally disjoint, and in routing across multiple paths. It surveys proposals for making BGP better able to exploit multiple paths and how multi-homing can create alternate paths. It also describes how alternate paths can be realized through detour routing (application layer mechanisms) and routing deflections (network layer mechanisms). It also discusses Fast Re-Route techniques for construction of backup routes. It concludes by surveying open research issues into the discovery and use of alternate paths in the Internet.