Paper Info
Title
Space Decomposition Techniques for Fast Layer-4 Switching
Abstract
Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the pack- ets. The filters are a powerful and uniform way to implement new network services such as fire walls, Network Address Translation (NAT), Virtual Private Networks (VPN), and per-flo w or class-based Quality of Service (QOS) guaran- tees (4). While several schemes have been proposed recently that can perform packet classification at high speeds, none of them achieves fast worst-case time for adding or deleting filters from the database (3, 8, 9). In this paper, we present a new scheme, based on space decomposition, whose search time is comparable to the best existing schemes, but which also offers fast worst-case filter update time. The three key ideas in this algorithm are as follows: (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, (2) fractional cascading and pre- computation to improve packet classification time, and (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation.
Year
Venue
Keywords
1999
Protocols for High-Speed Networks
fast layer-4 switching,space decomposition techniques,data structure,search space,quality of service
Field
DocType
ISBN
Fractional cascading,Computer science,Network packet,Network address translation,Quality of service,Software,Router,Computer engineering,Recursion,Distributed computing,Private network
Conference
0-7923-8690-6
Citations 
PageRank 
References 
63
13.68
6
Authors
3
Name
Order
Citations
PageRank
Milind M. Buddhikot173490.03
Subhash Suri25255455.58
Marcel Waldvogel31537166.65