2009/08/01 by Abhik Das, Das, Abhik, Shweta Agarwal +3
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #cs.IT #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.0908.0078
9 pages, 4 figures
arxiv created 2010/01/20 · arxiv updated 2010/02/08
This paper introduces the concept of incremental traceback for determining changes in the trace of a network as it evolves with time. A distributed algorithm, based on the methodology of algebraic traceback developed by Dean et al, is proposed which can completely determine a path of d nodes/routers using O(d) marked packets, and subsequently determine the changes in its topology using O(log d) marked packets with high probability. The algorithm is established to be order-wise optimal i.e., no other distributed algorithm can determine changes in the path topology using lesser order of bits (i.e., marked packets). The algorithm is shown to have a computational complexity of O(d log d), which is significantly less than that of any existing non-incremental algorithm of algebraic traceback. Extensions of this algorithm to settings with node identity spoofing and network coding are also presented.