Benefit of Network Coding for Probabilistic Packet Marking and Collecting Coupons from Different Perspectives at the Collector

Dung Tien NGO
Tuan Anh LE
Choong Seon HONG
Sungwon LEE
Won-Tae LEE
Jae-Jo LEE

IEICE TRANSACTIONS on Communications   Vol.E96-B    No.2    pp.489-499
Publication Date: 2013/02/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.489
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Quality of Communication Services Improving Quality of Life)
IP traceback,  probabilistic packet marking,  network coding,  coupon collector's problem,  different perspectives,  

Full Text: PDF>>
Buy this Article

Probabilistic Packet Marking (PPM) is a scheme for IP traceback where each packet is marked randomly with an IP address of one router on the attack path in order for the victim to trace the source of attacks. In previous work, a network coding approach to PPM (PPM+NC) where each packet is marked with a random linear combination of router IP addresses was introduced to reduce number of packets required to infer the attack path. However, the previous work lacks a formal proof for benefit of network coding to PPM and its proposed scheme is restricted. In this paper, we propose a novel method to prove a strong theorem for benefit of network coding to PPM in the general case, which compares different perspectives (interests of collecting) at the collector in PPM+NC scheme. Then we propose Core PPM+NC schemes based on our core network coding approach to PPM. From experiments, we show that our Core PPM+NC schemes actually require less number of packets than previous schemes to infer the attack path. In addition, based on the relationship between Coupon Collector's Problem (CCP) and PPM, we prove that there exists numerous designs that CCP still benefits from network coding.