O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

49

IP Router Tables*

Sartaj Sahni

University of Florida

Kun Suk Kim

University of Florida

Haibin Lu

University of Florida

49.1Introduction

49.2Longest Matching-Prefix

Linear ListEnd-Point ArraySets of Equal-Length PrefixesTriesBinary Search TreesPriority Search Trees

49.3Highest-Priority Matching

The Data Structure BOBSearch for the Highest-Priority Matching Range

49.4Most-Specific-Range Matching

Nonintersecting RangesConflict-Free Ranges

Acknowledgments

References

49.1Introduction

An Internet router classifies incoming packets into flows utilizing information contained in packet headers and a table of (classification) rules. This table is called the rule table (equivalently, router table). The packet-header information that is used ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required