A Survey on Selective Routing Topology Inference Through Active Probing

Abstract

Although there are surveys summarizing the efforts toward discovering the Internet routing topology, no work has addressed how to infer the routing topology among a particular group of hosts scattered across the Internet. These two issues differ in scale, objective and solutions currently available. How to infer the routing topology among a group of hosts is non-trivial due to the complexity, size and decentralized nature of the Internet. Nevertheless, a cost-effective means of inferring topology would be of considerable benefit to many mechanisms, such as network monitoring, overlay topology construction and failure diagnosis. Since external information, such as routing table entries, is not publicly available to hosts, most of the methodologies employ an active probing mechanism to address this issue. For this reason our focus is on active probing based solutions, too. A comparison between generic Internet topology discovery and that between a specific group of hosts is elaborated in order to distinguish these two problems. Furthermore, we discuss the motivation that underlines the significance of various techniques addressing routing topology discovery among a group of hosts. We then classify the strategies into two types: Router-Assisted (RA) and Non-Router-Assisted (NRA), and analyze in detail their state-of-the-art position, merits and challenges, respectively. Conclusions and future directions are also presented.