Fastand Efficient Memory Managementfor Non-FIFORouters (Invited Paper)
Chuanxiong Guo · 2006
Currentmemorymanagementschemesarenot suitable fornon-FIFOrouters either because oflowmemory utilization orbecause ofhightimecomplexity duetothefact thatthefirst-in-first-o ut characteristic doesnotholdanymore. Inthispaper, we develop anefficient PacketSizeDistribution basedMemoryManagement (PSDMM)schemewhichprovides efficient memoryutilization fornon-FIFO routers andpreserves 0(1)timecomplexity atthesametime.PSDMM utilizes the Cumulative Distribution Function (CDF)ofthepacketsizeto split thememoryintopoolswithfixedblocksizes, andby carefully choosing thenumberofpoolsandtheblocksizes, PSDMM improves thememoryutilization fromless than40%to about90%underreal Internet traffic conditions. PSDMM adapts tovarious packet sizedistributions automatically whentraffic pattern changes andcanbeimplemented inhigh-speed QoS- enabled routers orhigh-end server systems duetoitsconstant timecomplexity andhighefficiency. IndexTerms-Non-FIFOrouter, Memory Management, PacketSizeDistribution, Time-Complexity