The application of the in-tree knapsack problem to routing prefix caches

tree knapsack problem;routing prefix caching;approximation algorithms;dynamic programming;Computer Science

Nicholson, Patrick

University of Waterloo

关键词: tree knapsack problem;    routing prefix caching;    approximation algorithms;    dynamic programming;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4364/1/uw-ethesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.