IP traceback technique allows a victim to trace the routing path that an attacker has followed to reach his system. It has an effect of deterring future attackers as well as capturing the current one. FMS (Fragment Marking Scheme) is an efficient implementation of IP traceback. Every router participating in FMS leaves its IP information on the passing-through packets, partially and with some probability. The victim, then, can collect the packets and analyze them to reconstruct the attacking path. FMS and similar schemes, however, suffer a long convergence time to build the path when the attack path is lengthy. Also they suffer a combinatorial explosion problem when there are multiple attack paths. This paper suggests techniques to restrain the convergence time and the combinatorial explosion. The convergence time is reduced considerably by insuring all routers have close-to-equal chance of sending their IP fragments through a distance-weighted sampling technique. The combinatorial explosion is avoided by tagging each IP fragment with the corresponding router’s hashed identifier.