Towards asymptotic optimality in probabilistic packet marking

ABSTRACT

There has been considerable recent interest in probabilistic packet marking schemes for sending information from nodes (routers) along one or more paths traveled by a stream of packets to the end-host receiving that stream. A central consideration for such schemes is the tradeoff between the number B of possible states of the marking bits in a packet, the number of bits n of information being sent by the nodes, and the expected number of packets T required to reconstruct this information. For the case where the packets all travel along the same path, we prove a lower bound of T ≥ Ω(B2^2n/(B-1)), roughly the square of an earlier lower bound of Adler.For an upper bound, we consider a model where each of m nodes along a single path must send one of s possible messages (thus n = m log2 s total bits are sent). We prove that T ≤ O(m • 2^{2m(log2 s)/(B-1)}) suffices (the implicit constant depends on B and s); this almost matches the lower bound, and is roughly the square root of an earlier upper bound of Adler. The new bound holds for all B and s in two slightly relaxed models, while under the strictest requirements we prove it only for some special values of B and s. This is related to a challenging geometric problem: the existence of an s-reptile (B-1)-dimensional simplex, i.e. a simplex S that can be tiled by s congruent simplices similar to S.We also consider the case where the packets travel along multiple paths to the same destination. In this case, we present a new protocol and analysis technique that together allow us to significantly generalize over previous work the scenarios where the protocol is effective.

REFERENCES

• 1: Micah Adler, Tradeoffs in probabilistic packet marking for IP traceback, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509969]
• 2: M. Adler, J. Cai, J. K. Shapiro, and D. Towsley, Estimation of Congestion Price Using Probabilistic Packet Marking. In Proceedings of Infocom 2003.
• 3: C. Bandt, Self-similar sets. V. Integer matrices and fractal tilings of Rsp n. Proc. Amer. Math. Soc., 112(2):549--562, 1991.
• 4: Hal Burch, Tracing Anonymous Packets to Their Approximate Source, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 5: L. Danzer, B. Grünbaum, and V. Klee, Helly's theorem and its relatives. In Convexity, volume 7 of Proc. Symp. Pure Math., pages 101--180. American Mathematical Society, Providence, 1963.
• 6: D. Dean, M. Franklin, and A. Stubblefield, An Algebraic Approach to IP Traceback. In Proc. 2001 Network and Distributed System Security Symposium.
• 7: H. E. Debrunner, Tiling Euclidean d-space with congruent simplexes. In Discrete geometry and convexity (New York, 1982), volume 440 of Ann. New York Acad. Sci., pages 230--261. New York Acad. Sci., New York, 1985.
• 8: Thomas W. Doeppner , Philip N. Klein , Andrew Koyfman, Using router stamping to identify the source of IP packets, Proceedings of the 7th ACM conference on Computer and communications security, p.184-189, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352627]
• 9: Q. Dong, M. Adler, and K. Hirata, Efficient Schemes for Probabilistic Packet Marking. University of Massachusetts, Amherst Technical Report 2004-67.
• 10: G. Gelbrich, Crystallographic reptiles. Geom. Dedicata, 51(3):235--256, 1994.
• 11: Michael T. Goodrich, Efficient packet marking for large-scale IP traceback, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586128]
• 12: S. Lee and C. Shields, Tracing the Source of Network Attack: A Technical, Legal and Societal Problem. In Proceedings of the 2001 IEEE Workshop on Information Assurance and Security, June 2001.
• 13: L. Lovász, Semidefinite programs and combinatorial optimization. In B. Reed and C. Linhares-Sales, editors, Recent Advances in Algorithms and Combinatorics, pages 137--194. Springer, New York, 2003.
• 14: J. Matousek, Nonexistence of 2-reptile simplices. Discrete Comput. Geom., 2004. Submitted.
• 15: S.-M. Ngai, V. F. Sirvent, J. J. P. Veerman, and Y. Wang, On 2-reptiles in the plane. Geom. Dedicata, 82(1-3):325--344, 2000.
• 16: K. Park and H. Lee, On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack. In Proc. IEEE INFOCOM '01, pp. 338--347, 2001.
• 17: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 18: Stephen L. Snover , Charles Waiveris , John K. Williams, Rep-tiling for triangles, Discrete Mathematics, v.91 n.2, p.193-200, Aug. 28, 1991 [doi>10.1016/0012-365X(91)90110-N ]
• 19: D. X. Song and A. Perrig, Advanced and authenticated marking schemes for IP traceback. In Proc. IEEE INFOCOM '01, 2001.
• 20: R. Thommes and M. ,J. Coates, Deterministic Packet Marking for Congestion Price Estimation. In Proc. IEEE INFOCOM '04.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  E. Data
  E.4 CODING AND INFORMATION THEORY

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Keywords:
denial of service