Best Paper Award 2013

Best Paper Award

Bitwise Operation-Based In-Network Processing for Loss Tomography

Takahiro Matsuda , Tetsuya Takine

[Trans. Commun., Vol. E96-B No.2, Feb. 2013]

Takahiro Matsuda

Tetsuya Takine

　Network monitoring is an important aspect of network management and design. In this paper, the authors study network tomography, which is a technique for inferring internal network characteristics through end-to-end measurements. In particular, the authors focus on loss tomography, network tomography for link loss rates. Because in many cases, loss tomography is formulated as an ill-posed linear inverse problem, link loss rates cannot be uniquely estimated.
　Network coding-based loss tomography is a promising technique with potential to solve this problem. In network coding, intermediate nodes are allowed to encode several received packets into coded packets before forwarding. Network coding-based loss tomography has two advantages: it can be applied to general directed acyclic networks; and it can reduce the number of forwarded packets in the network. However, when linear network coding defined on a finite field is used, the field size should be increased according to the size of the network.
　In this paper, the authors propose bitwise operation-based in-network processing for loss tomography. The proposed scheme enables us to infer link loss rates with simple operations in intermediate nodes. In the proposed scheme, the coding information of each probe packet is composed of a bit sequence whose length is equal to the number of paths between source and receiver nodes and, in each intermediate node, coding operations are defined by simple bitwise operations. The authors also provide a procedure for computing likelihood functions which can be utilized in conducting statistical inference of link loss rates.
　This paper is notable from both theoretical and practical perspectives because the bitwise operation approach used in the proposed scheme is highly practical. It is also notable in terms of readability. Therefore, this paper makes a significant contribution and is deserving of the Best Paper Award.