Network Tomography Under Multipath Routing

Network tomography is a kind of network measurement techniques.It is able to employ end-to-end measurements to obtain performance parameters of the intervening network,such as the link delay distribution,while without requiring any measurement support from the intervening network.Not only for the normal network users,but also for the network administrators,network tomography is a very important approach of network monitoring.However,with the rapid increase of the scale of the Internet as well as the development and the application of a great amount of new techniques,some characters of the Internet are changing gradually.For a typical instance,network load-balancing techniques will introduce multipath routing to networks,and make multiple routing path exist between end-nodes,changing the classical tree-structured topology of the single-source network while presenting new requirements for the network measurement techniques such as network tomography.This dissertation,which focuses on the new scenario of multipath routing,conducts research efforts on four major aspects that are the identification of multipath routing in networks,the identification of end-to-end probing paths under multipath routing,the network topology tomography under multipath routing,and the identification of congestion links under multipath routing,etc.,and obtains the corresponding achievements as below:<1>.In terms of the identification issue of multipath routing in networks,first by using a statistical model to describe the end-to-end arrival order the probing packets,we prove in theory that the probability of no out-of-order delivery of the probing packets has distinguishabilities towards network routing,i.e.,it demonstrates consistent results when we compare such probability under single-path routing network to the one under multipath routing.Then based on the network end-to-end measurements of the packet arrival orders,we propose a probing scheme which can not only detect multipath routing(in networks)from single-path routing,but also can tell the types of multipath routing.Theoretical results show that our proposed identification scheme of multipath routing in networks can achieve a desirably low failure probability.And evaluation results further validate efficiency of our proposed scheme.<2>.In terms of the identification issue of probing paths under multipath routing,we propose a tomographic approach to identify the probing paths of the deployed flows between end-nodes.For a given single-source networks under multipath routing,our proposed scheme first calculates and deploys the minimum number of probing flows between end-nodes that enable us a failure probability of their path measurement coverage no greater than a given threshold.Then according to the similarities between the path delay performances of the probing flows,we detect the probing flows that share the same end-to-end path.After that,we propose and prove a sufficient condition that the topology of the intervening network needs to meet for the successful identification of probing paths of the flows deployed there.Simulation results show that our proposed scheme achieves desirable results of the identification of end-to-end paths for the probing flows.<3>.In terms of the identification issue of network topologies under multipath routing,we first employ the approaches of graph cut to theoretically prove that the corresponding non-tree topology of the single-source network under multipath routing is able to be decomposed into a tree topology and a multi-source single-path routing topology,through which we demonstrate the identifiability of the topology of the single-source network under multipath routing.Then with the network end-to-end measurement of the packet arrival orders,we propose a detection scheme that is able to tell whether there are cut-share between paths.After that,we further propose an identification algorithm of the end-to-end paths for both sub-topologies in the single-source multipath routing network.Simulation results validate the desirable performance of our proposed scheme.<4>.In terms of the identification issue of network congestion links under multipath routing,first we theoretically prove that the link delay variances of single-source networks under multipath routing is identifiable.Then based on the extra constraint information of delay performances and differences of path congestion degrees extracted from the end-to-end measurements,we transform the identification issue of congestion links of single-source networks under multipath routing into constraint optimization problems,and propose a series of corresponding algorithms to solve them.Thanks to the extra helpful information extracted from end-to-end measurements and the proper adjustments against the characters of the topology of the single-source networks under multipath routing,evaluation results demonstrate that our proposed algorithms gain better detection performances of congestion links than existing methods.By solving the problems demonstrated above,this dissertation extends the application scope of network tomography to networks where multipath routing is enabled.The related achievements can not only help the practical use and deployments of network tomography under multipath routing,but also can help the research of tomographic approaches in complex network scenarios such as the non-stationary network,and greatly enhance the practicability of network tomography.