Efficient prefix updates for IP router using lexicographic ordering and updateable address set
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 w...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
IEEE computer society
2008
|
| Online Access: | http://hdl.handle.net/20.500.11937/15759 |
| _version_ | 1848748980452720640 |
|---|---|
| author | Soh, Sieteng Hiryanto, L. Rai, S. |
| author_facet | Soh, Sieteng Hiryanto, L. Rai, S. |
| author_sort | Soh, Sieteng |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T07:13:40Z |
| format | Journal Article |
| id | curtin-20.500.11937-15759 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:13:40Z |
| publishDate | 2008 |
| publisher | IEEE computer society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-157592017-09-13T14:07:14Z Efficient prefix updates for IP router using lexicographic ordering and updateable address set Soh, Sieteng Hiryanto, L. Rai, S. 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. 2008 Journal Article http://hdl.handle.net/20.500.11937/15759 10.1109/TC.2007.70776 IEEE computer society restricted |
| spellingShingle | Soh, Sieteng Hiryanto, L. Rai, S. Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title | Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title_full | Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title_fullStr | Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title_full_unstemmed | Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title_short | Efficient prefix updates for IP router using lexicographic ordering and updateable address set |
| title_sort | efficient prefix updates for ip router using lexicographic ordering and updateable address set |
| url | http://hdl.handle.net/20.500.11937/15759 |