Multipath routing identification for network measurement built on end-to-end packet order

Multipath routing, which provides multiple paths for ubiquitous communications, has been considered as promising routing mechanism to optimize network performance for Internet. However, it will incur adverse effects on the existing and emerging network measurement schemes, for example incomplete and inaccurate measurement results, to understand network characteristics, since many of them commonly do the work under single-path routing rather than multipath-routing. In order to eliminate this emerging issue on single-path-based network measurement in Internet, it requires to identify whether there is multipath routing between two reachable hosts in the network. Notice that no out-of-order delivery among a strip of packets along multiple paths seldom occurs, in this paper, an efficient multipath routing identification approach has been proposed to achieve this goal, by introducing a composite probe built on out-of-order delivery. We have elaborated our theoretical observation on the current probe composed of a strip of packets, and then presented our composite probe design in detail. Our proposed approach not only can efficiently identify the existing multipath routing, but also accurately recognize its type, referring to flow-based or packet-based routing. Corroborated by experiments and simulations, conducted on Planetlab and NS2, respectively, our approach outperforms other schemes in terms of effectiveness and accuracy.