Diagonal tuple space search:A multidimensional packet classification scheme

The introduction of the quality of service (QoS), policy based routing and security to the Internet implies the need to classify IP packets based on multiple protocol fields. Theory has proved that any general multidimensional look-up algorithm is either time or storage hungry. However, it has been anticipated that more feasible algorithms could be obtained for conflict-free classifiers. This paper studies the implications of the conflict-free constraint for a well-known field in packet classification - the algorithms, which derive from the tuple space paradigm. Also a heuristic packet classification algorithm that makes use of the conflict-free constraint in multidimensional tuple space is introduced