Two tiered packet labeling for data network traceback

Details Two tiered packet labeling for data network traceback Two tiered packet labeling for data network traceback

2006-06-30

2009-11-17

Cho, Hong (Department: 2419)

Multiplex communications

Network configuration determination

C370S392000, C370S401000

Reexamination Certificate

active

07619990

ABSTRACT:
Disclosed is a two tier packet labeling technique for use in connection with network traceback in a network having multiple autonomous systems, with routers and other network resources within each autonomous system. Tier 1 labels are assigned at the autonomous system level, and tier 2 labels are assigned at the router level. In order to reduce the number of labels that are required, a technique called logical partitioned coloring may be used, in which certain autonomous systems and border routers may be logically partitioned into a plurality of mesh connected nodes, and the labels are assigned to these mesh-connected nodes. During network operation the network routers store either tier 1 or tier 2 labels in data packets. The determination of whether to store a label in any particular packet, and the determination of which label to store, may be determined probabilistically by the network router.

REFERENCES:
patent: 6473421 (2002-10-01), Tappan
patent: 6925081 (2005-08-01), Meda
patent: 7076559 (2006-07-01), Ghanwani et al.
patent: 2004/0093521 (2004-05-01), Hamadeh et al.
patent: 2005/0008015 (2005-01-01), Meda
patent: 2005/0226245 (2005-10-01), Meda
patent: 2005/0278779 (2005-12-01), Koppol et al.
patent: 2006/0198321 (2006-09-01), Nadeau et al.
patent: 2006/0272018 (2006-11-01), Fouant
patent: 2007/0206605 (2007-09-01), Ansari et al.
S. Savage, et al., “Practical Network Support for IP Traceback”, in Proc. ACM SIGCOMM, pp. 295-306, Aug. 2000.
S.M. Bellovin, “ICMP Traceback Messages”, IETF Network Working Group, Internet Draft:draft-bellovin-itrace-00.txt, Mar. 2000.
A.C. Snoeren, et al., “Single-Packet IP Traceback”, in Proc. ACM SIGCOMM, Aug. 2001.
M. Sung, et al., “IP-Traceback Based Intelligent Packet Filtering: A Novel Technique for Defending Against DDoS Attacks”, in IEEE TPDS, 2003.
H. Burch, et al., “Tracing Anonymous Packets to Their Approximate Source”, in Proc. UNENIX LISA, Dec. 2000.
Li, et al., “Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation”, in Proc. IEEE Symp. on S&P, 2004.
A. Belenky, et al., “IP Traceback with Deterministic Packet Marking”, in IEEE Communication Letters, vol. 7, No. 4, pp. 162-164, Apr. 2003.
M. Goodrich, “Efficient Packet Marking for Large Scale IP Traceback”, in Proc. ACM CCS, pp. 117-126, 2002.
D. Song, et al., “Advanced and Authenticated Marking Schemes for IP Traceback”, in Proc. IEEE INFOCOM, 2001.
D. Dean, et al., An Algebrac Approach to IP Traceback, in ACM TISSEC, vol. 5, No. 2, pp. 119-137, 2000.
M. Adler, “Tradeoffs in Probabilistic Packet Marking for IP Traceback”, in Proc. STOC, pp. 407-418, 2002.
T. Peng, et al., “Adjusted Probabilistic Packet Marking for IP Traceback”, in Proc. Networking, 2002.
B. Rizvi, et al., “Analysis of Adjusted Probabilistic Packet Marking”, in Proc. IPOM, 2003.
Q. Dong, et al., “Efficient Probabilistic Packet Marking”, in Proc. IEEE ICNP, 2005.
K. Park, et al., On the Effectiveness of Probabilistic Packet Marking for IP Traceback under Denial of Service Attack, in Proc. INFOCOMM, 2001.
I. Hamadeh, et al., “Performance of IP Address Fragmentation Strategies for DDoS Traceback”, in Proc. IEEE IPOM, 2003.
M. Waldvogel, “GOSSIBvs.IP Traceback Rumors”, in Proc. ACSAC, 2002.
M. Ma, “Tabu Marking Scheme for IP Traceback”, in Proc. IEEE IPDPS, 2005.
T. Ogawa, et al., “Branch Label Based Probabilistic Packet Marking for IP Traceback”, in IEEE ICON, 2003.
B. Al-Duwairi, et al., “Topology Based Packet Marking”, in Proc. IEEE ICCCN, 2004.
M. Muthuprasanna, et al., “Space-Time Encoding for DDoS Attack Traceback”, in Proc. IEEE GLOBECOM, 2005.
K. Choi, et al., “A Marking Scheme Using Huffman Codes for IP Traceback”, in Proc. ISPAN, 2004.
C. Bai, et al., “Alegebraic Geometric Code Based IP Traceback”, In Proc. IEEE IPCCC, 2004.
Y. Sawai, et al., “Performance Evaluation of Inter-Domain IP Traceback”, in Proc. IEEE ICT, 2003.
V. Paruchuri, et al., “Authenticated Autonomous System Traceback”, in Proc. IEEE AINA, 2004.
C. Gong, et al., “Single Packet IP Traceback in AS-Level Partial Deployment Scenario”, in Proc. IEEE GLOBECOMM, 2005.
B. Al-Duwairi, et al., “Novel Hybrid Schemes Employing Packet Marking and Packet Logging for IP Traceback”, in IEEE TPDS, 2005.
C. Gong, et al., “IP Traceback Based on Packet Marking and Logging”, in Proc. ICC, 2005.
E. Lloyd, et al., “On the Complexity of Distance-2 Coloring”, in Proc. IEEE ICCI, 1992.
S. Das, et al., “Star-Coloring of Graphs for Conflict-Free Access to Parallel Memory Systems”, in Proc. IEEE IPDPS, 2004.
S. T. McCormick, “Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem”, in Mathematical Programming 26 (1983), 153-171.
A. Gebremedhin, et al., “Parallel Distance-k Coloring Algorithms for Numerical Optimization”, in Proc. Euro-Par, 2002.
D. Bozdag, et al., “A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers”, in Proc. HPCC, 2005.
A. Yaar, et al., “FIT: Fast Internet Traceback”, in.Proc. IEEE INFOCOMM, 2005.
P. Mahadevan, et al., “Lessons from Three Views of the Internet Topology”, CAIDA Technical Report TR-2005-02.
D. Magoni, et al., “Analysis of the Autonomous System Network Topology”, in ACM CCR, Jul. 2001.
M. Fayed, et al., “On the Size Distribution of Autonomous Systems”, Technical Report, Boston University, Jan. 2003.
Q. Vohra, et al., “BGP Support for Four-Octet AS Number Space”, IETF Network Working Group, Internet-Draft:draft-ietf-idr-as4bytes-12.txt, Nov. 2005.
N. Spring, et al., “Measuring ISP Topologies with Rocketfuel”, in Proc. ACM SIGCOMM, 2002.
H. von Schelling, “Coupon Collecting for Unequal Probabilities”, in American Mathematical Monthly, 1954.
S. Lu, et al., “Filling a Penny Album”, in CHANCE, 2000.

Affiliated with

Also associated with

Rating

Two tiered packet labeling for data network traceback does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Two tiered packet labeling for data network traceback, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two tiered packet labeling for data network traceback will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4143712