Download the full-sized PDF of Cache architectures to improve IP lookupsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Cache architectures to improve IP lookups Open Access


Other title
IP lookups, Routing, Switching, Caching
Type of item
Degree grantor
University of Alberta
Author or creator
Ravinder, Sunil
Supervisor and department
MacGregor, Mike (Computing Science)
Nascimento, Mario A (Computing Science)
Examining committee member and department
Elmallah, Ehab (Computing Science)
Tellambura, Chinthananda (Electrical and Computer Engineering)
Department of Computing Science

Date accepted
Graduation date
Master of Science
Degree level
IP address lookup is an important processing function of Internet routers. The challenge lies in finding the longest prefix that matches the packet’s destination address. One of the issues concerning IP address lookups is the average lookup time. In previous works, caching was shown to be an effective method to minimize the average lookup time. Caching involves storing information on recent IP lookup results in order to decrease average lookup times. In this thesis, we present two architectures that contain a prefix cache and a dynamic substride cache. The dynamic substride cache stores longest possible substrides from previous lookups, and is used in conjunction with a prefix cache. Successful hits in both the caches help reduce the number of worst-case lookups in the low level memory containing the IP routing table in a trie data structure. From simulations, we show that the two architectures show up to 99.9%global hit rate. Furthermore we present analytical models to find optimal designs for the two architectures. We also show that the architectures can support incremental updates once appropriate modifications are made to the trie data structure.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1239274
Last modified: 2015:10:12 19:26:31-06:00
Filename: thesis_sunil_ravinder.pdf
Original checksum: 4ca19d86c50d3b53f4c82e877a34a861
Well formed: true
Valid: false
Status message: Improperly formed date offset=1228915
File title: rrc3_1.eps
File author: sunil ravinder,,,
Page count: 92
Activity of users you follow
User Activity Date