Efficient and Dynamic Routing Topology Inference From End-to-End Measurements

1.ABSTRACT :

                   

                Inferring the routing topology and link performance from a node to a set of other nodes is an important component in network monitoring and application design. In this paper we propose a general framework for designing topology inference algorithms based on additive metrics. The framework can flexibly fuse information from multiple measurements to achieve better estimation accuracy. We develop computationally efficient

(polynomial-time) topology inference algorithms based on the framework. We prove that the probability of correct topology inference of our algorithms converges to one exponentially fast in the number of probing packets. In particular, for applications where nodes may join or leave frequently such as overlay network construction, application-layer multicast, peer-to-peer

file sharing/streaming, we propose a novel sequential topology inference algorithm which significantly reduces the probing overhead and can efficiently handle node dynamics. We demonstrate the effectiveness of the proposed inference algorithms via Internet experiments.

2. EXISTING SYSTEM :

                                   Developing a scalable tool to infer the routing topology and link performance from a node to a set of other nodes is an

important challenge. There are two primary approaches to infer the routing

topology and link performance in a communication network:

2.1. One approach is to use tools based on measurements or feedback messages of the internal nodes (e.g., routers). Such an approach is limited as today’s communication networks are evolving towards more decentralized and private administration. A common approach to obtain the routing topology from a source node to a destination node in the Internet is to use trace route. Trace route relies on internal routers responding to trace route requests and returning ICMP (Internet Control Message Protocol) messages. However, an increasing number of routers in the Internet today will block trace route requests due to privacy and security concerns. These routers are known as anonymous routers [30] and their existence makes the routing topology inferred by trace route-like tools inaccurate. Furthermore, trace route-like tools cannot discover layer-2 switches and MPLS (Multiprotocol Label Switching) paths that are increasingly being deployed.

             

2.2. The other approach, known as network tomography, utilizes end-to-end packet probing measurements (such as packet loss and delay measurements) conducted by the end hosts and does not require extra cooperation from the internal nodes(except the basic packet forwarding functionality). Under a network tomography approach, a source node will send probes to a set of destination nodes.       .

3.PROPOSED SYSTEM :

              We propose a general framework for designing topology inference algorithms based on additive metrics. The framework can flexibly fuse information from multiple measurements to achieve better estimation accuracy. We develop computationally efficient (polynomial-time) topology inference algorithms based on the framework. We prove that the probability of correct topology inference of our algorithms converges to one exponentially fast in the number of probing packet.

                                  We proposed a sequential topology inference algorithm to address the probing scalability problem and handle dynamic node joining and leaving efficiently. The proposed algorithms provide powerful tools for large scale network inference in communication networks. A general framework for designing network routing topology inference algorithms based on additive metrics. We show how to construct additive metrics and estimate the (shared) path lengths using end-to-end multicast and unicast packet probing measurements as well as trace route type measurements. The framework can flexibly fuse information available from multiple measurements to achieve better estimation accuracy and

faster convergence rate.

4.HARDWARE REQUIREMENTS:

•         System                : Pentium IV 2.4 GHz.

•         Hard Disk            : 40 GB.

•         Floppy Drive       : 1.44 Mb.

•         Monitor                : 15 VGA Colour.

•         Mouse                 : Logitech.

•         Ram                     : 256 Mb.

5.SOFTWARE REQUIREMENTS:

•         Operating System       : - Windows XP Professional.

•         Front End                              : - Asp .Net 2.0.

•         Coding Language       : - Visual C# .Net.