New Data Structures for IP Lookup and Conflict Detection
2009
In this paper we present a survey of new data structures for the representation of dynamic range router tables that employ most specific range matching. We present the min-augmented range tree with a relaxed balancing scheme, allowing updates and rebalancing tasks to be decoupled. Utilizing this scheme, IP lookups are not as much delayed as in a strict balancing scheme. Furthermore, we outline additional improvements to an existing online conflict detection approach, saving space and update costs. For offline conflict detection and resolution we describe an efficient sweepline algorithm.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
1
Citations
NaN
KQI