Efficient prefix updates for IP router using lexicographic ordering and updateable address set
MetadataShow full item record
Dynamic IP router table schemes, which have recently been proposed in the literature, perform an IP lookup or an online prefix update in O(log2|T|) memory accesses (MAs). In terms of lookup time, they are still slower than the full expansion/compression (FEC) scheme (compressed next-hop array/code word array (CNHA/CWA)), which requires exactly (at most) three MAs, irrespective of the number of prefixes |T| in a routing table T. The prefix updates in both FEC and CNHA/CWA have a drawback: Inefficient offline structure reconstruction is arguably the only viable solution. This paper solves the problem. We propose the use of lexicographic ordered prefixes to reduce the offline construction time of both schemes. Simulations on several real routing databases, run on the same platform, show that our approach constructs FEC (CNHA/CWA) tables in 2.68 to 7.54 (4.57 to 6) times faster than that from previous techniques. We also propose an online update scheme that, using an updatable address set and selectively decompressing the FEC and CNHA/CWA structures, modifies only the next hops of the addresses in the set. Recompressing the updated structures, the resulting forwarding tables are identical to those obtained by structure reconstructions, but are obtained at much lower computational cost. Our simulations show that the improved FEC and CNHA/CWA outperform the most recent O(log2|T|) schemes in terms of lookup time, update time, and memory requirement.
Showing items related by title, author, creator and subject.
Van Der Werf, Steven Martĳn (2010)In recent years, a great deal of attention has been given to wireless connectivity solutions that are capable of establishing wireless ad-hoc networks between mobile nodes. Whilst most of these networks are formed using ...
Crochemore, M.; Iliopoulos, Costas; Kubica, M.; Rytter, W.; Walen, T. (2010)Su?x arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute e?ciently two new tables storing di?erent types of ...
Webb, Steven Daniel (2010)Network computer games are played amongst players on different hosts across the Internet. Massively Multiplayer Online Games (MMOG) are network games in which thousands of players participate simultaneously in each instance ...