Improved Doubletree Algorithm to Discovery Large-Scale Topology

There is a growing interest in how to effectively and efficiently perform the topology discovery task in a network-friendly manner Monitoring Internet topology was a tractable problem. Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. Unfortunately, they have a problem of how to perform such measurements efficiently and in a network-friendly manner. When scaled up, such methods will generate so much traffic that they will begin to resemble distributed denial-of-service attacks.

The current trend towards a relevant highly distributed system by increasing the number of monitors is not a trivial matter. Duplication of effort close to the monitors wastes time by re-exploring previously discovered parts of the network, not to mention that probes converging from a set of sources towards a given destination can resemble a distributed denial-of-service(DDoS) attack as the probes converge from a set of sources towards a given destination. Improved Doubletree, which deals with these issues while keeping high network coverage.

The existing Doubletree algorithm faces the problem of redundancy. To solve this, the Improved Doubletree algorithm is proposed which reduces redundancy while maintaining nearly the same level of nodes and link coverage. Algorithm quantifies the amount of redundancy in classic Internet topology discovery approaches by taking into account the perspective of a single monitor (intramonitor) and that of an entire system (intermonitor). Improved Doubletree simultaneously meets the conflicting demands of reducing intramonitor and intermonitor redundancy. In both the above cases a hop in the middle that is between monitor and destination will be selected by Hop Selection to increase efficiency.