Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    Efficient prefix updates for IP router using lexicographic ordering and updateable address set

    Access Status
    Fulltext not available
    Authors
    Soh, Sieteng
    Hiryanto, L.
    Rai, S.
    Date
    2008
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Soh, S. and Hiryanto, L. and Rai, S. 2008. Efficient prefix updates for IP router using lexicographic ordering and updateable address set. IEEE Transactions on Computers. 57 (1): pp. 110-125.
    Source Title
    IEEE Transactions on Computers
    DOI
    10.1109/TC.2007.70776
    ISSN
    0018-9340
    School
    Department of Computing
    URI
    http://hdl.handle.net/20.500.11937/15759
    Collection
    • Curtin Research Publications
    Abstract

    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.

    Related items

    Showing items related by title, author, creator and subject.

    • Architecture and performance of multi-hop wireless ad-hoc routing protocol (MultiWARP)
      Van Der Werf, Steven Martijn (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 ...
    • Efficient algorithms for two extensions of LPF table: the power of suffix arrays
      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 ...
    • Computational studies of some static and dynamic optimisation problems
      Lee, Wei R. (1999)
      In this thesis we shall investigate the numerical solutions to several important practical static and dynamic optimization problems in engineering and physics. The thesis is organized as follows.In Chapter 1 a general ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.