You Can Get There from Here: Routing in the Internet

摘要

Routing in the Internet is performed with the help of IP forwarding lookup tables; however, searching these tables efficiently for the "next hop" is nontrivial, and complex data structures make an important contribution in this regard. This article surveys the three main approaches to the problem and investigates the associated data structures and algorithms. We also explore variations on these approaches and conclude with a discussion of current trends.