Research Article
Fast and Efficient Memory Management for Non-FIFO Routers
@INPROCEEDINGS{10.1109/CHINACOM.2006.344693, author={Juan Chen and Chuanxiong Guo}, title={Fast and Efficient Memory Management for Non-FIFO Routers}, proceedings={1st International ICST Conference on Communications and Networking in China}, publisher={IEEE}, proceedings_a={CHINACOM}, year={2007}, month={4}, keywords={Non-FIFO router Memory Management Packet Size Distribution Time-Complexity}, doi={10.1109/CHINACOM.2006.344693} }- Juan Chen
Chuanxiong Guo
Year: 2007
Fast and Efficient Memory Management for Non-FIFO Routers
CHINACOM
IEEE
DOI: 10.1109/CHINACOM.2006.344693
Abstract
Current memory management schemes are not suitable for non-FIFO routers either because of low memory utilization or because of high time complexity due to the fact that the first-in-first-out characteristic does not hold anymore. In this paper, we develop an efficient packet size distribution based memory management (PSDMM) scheme which provides efficient memory utilization for non-FIFO routers and preserves O(1) time complexity at the same time. PSDMM utilizes the cumulative distribution function (CDF) of the packet size to split the memory into pools with fixed block sizes, and by carefully choosing the number of pools and the block sizes, PSDMM improves the memory utilization from less than 40% to about 90% under real Internet traffic conditions. PSDMM adapts to various packet size distributions automatically when traffic pattern changes and can be implemented in high-speed QoS-enabled routers or high-end server systems due to its constant time complexity and high efficiency.