IP traceback is critical for identifying sources of attacks and instituting protection measures for the Internet.
Savage et al.[1] suggested probabilistically marking packets as they traverse routers through the Internet.
This approach would require more state information in each packet than simple node marking but would converge much faster.
[1] Due to the high number of combinations required to rebuild a fragmented edge id, the reconstruction of such an attack graph is computationally intensive according to research by Song and Perrig.
[2] Accordingly, Song and Perrig propose the following traceback scheme: instead of encoding the IP address interleaved with a hash, they suggest encoding the IP address into an 11 bit hash and maintain a 5 bit hop count, both stored in the 16-bit fragment ID field.
If a router decides not to mark the packet it merely increments the hop count in the overloaded fragment id field.
They describe a more realistic topology for the Internet – that is composed of LANs and ASs with a connective boundary – and attempt to put a single mark on inbound packets at the point of network ingress.
Their idea is to put, with random probability of .5, the upper or lower half of the IP address of the ingress interface into the fragment id field of the packet, and then set a reserve bit indicating which portion of the address is contained in the fragment field.
Their approach is similar in that they wish to use and encoded IP address of the input interface in the fragment id field of the packet.
[4] They attempt to mitigate the collision problem by introducing a random distributed selection of a hash function from the universal set, and then applying it to the IP address.
Through a complicated procedure and a random hash selection, they are capable of reducing address collision.
In dynamic marking it is possible to find the attack agents in a large scale DDoS network.
In the mark-based method, the detection engine takes into account the marks of the packets to identify varying sources of a single site involved in a DDoS attack.
In order to satisfy the end-to-end arguments approach, fate-sharing and also respect to the need for scalable and applicable schemes, only edge routers implement a simple marking procedure.
The fairly negligible amount of delay and bandwidth overhead added to the edge routers make the DDPM implementable.
[5] S. Majumdar, D. Kulkarni and C. Ravishankar proposes a new method to traceback the origin of DHCP packets in ICDCN 2011.
A bit is then set at the index generated to create a fingerprint when combined with the output of all other hash functions.
The paper shows a simple family of hash functions suitable for this purpose and present a hardware implementation of it.
They admit their algorithm is slow (O(N2)) and with only 3.3 million packet hashes being stored the approximate time before the digest tables are invalid is 1 minute.
Bellovin suggests that the selection also be based on pseudo-random numbers to help block attempts to time attack bursts.
To bypass this restriction and automate this process, Stone proposes routing suspicious packets on an overlay network using ISP edge routers.