Dissertation
High performance cache architectures for IP routing: replacement, compaction and sampling schemes
Washington State University
Doctor of Philosophy (PhD), Washington State University
08/2007
DOI:
https://doi.org/10.7273/000005787
Abstract
IP routing is an important operation in the forwarding of packets through the
Internet. It decides how and where to deliver incoming packets to the appropriate output
interface of a router. The process is performed by looking up IP addresses in a routing
table stored in memory. The speed of this operation has a great influence on the overall
performance of network processors. With the growth of Internet, the routing table
lookups are required to be faster to match the increasing link bandwidth.
This dissertation presents novel cache-based schemes to obtain high routing table
lookup performance. This study involves the following aspects. In regard to the cache
architectures, a victim cache is implemented to store the entries discarded by the main
cache. A randomly selected index (RSI) method is designed to redirect indexes away
from those entries that have a large possibility to cause conflict misses. As for the cache
replacement policy, two new policies that tend to remove an inactive entry by considering
its previous access references are introduced and evaluated. In order to reduce memory
size, novel route entry compaction schemes are designed based on the special features of
Ternary Content Addressable Memory. In addition, two improved sampling techniques
are introduced to alleviate the port error which is a side-effect of caching. A set
associative caching scheme specially implemented for the compaction schemes is also
described.
These schemes are evaluated through extensive simulation based on IPv4 and
IPv6 routing information. The results show our schemes can significantly enhance cache
hit rate up to more than 20%. The higher hit rate makes average memory access time
shorter, this in turn speed up the route lookups. Moreover, a small port error ratio is
beneficial to reduce the possibility of incorrect routing.
Metrics
3 File views/ downloads
17 Record Views
Details
- Title
- High performance cache architectures for IP routing
- Creators
- Ruirui Guo
- Contributors
- Jose G Delgado-Frias (Chair) - Washington State University, School of Electrical Engineering and Computer ScienceJabulani Nyathi (Committee Member)Krishnamoorthy Sivakumar (Committee Member) - Washington State University, Voiland College of Engineering and Architecture
- Awarding Institution
- Washington State University
- Academic Unit
- School of Electrical Engineering and Computer Science
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 119
- Identifiers
- 99901054938501842
- Language
- English
- Resource Type
- Dissertation