O(log n) dynamic packet routing
Sartaj K. Sahni, Kun Suk Kim · 2003
A data structure is developed that permits one to find longest matching prefixes as well as to insert and delete a prefix in O(log n) time, where n is the number of prefixes in the router table. Experimental results using a real IPv4 routing database are also presented.