Handbook of Data Structures and Applications, 2nd Edition

50

Multi-Dimensional Packet Classification^*

Pankaj Gupta^†

Cypress Semiconductor

50.1Introduction

Problem Statement

50.2Performance Metrics for Classification Algorithms

50.3Classification Algorithms

Background•Taxonomy of Classification Algorithms•Basic Data Structures•Geometric Algorithms•Heuristics•Hardware-Based Algorithms

50.4Summary

References

50.1Introduction

Chapter 49 discussed algorithms for 1-d packet classification. In this chapter we consider multi-dimensional classification in detail. First we discuss the motivation and then the algorithms for multi-dimensional classification. As we will see, packet classification on multiple fields is in general a difficult problem. Hence, researchers have proposed a variety of algorithms which, ...