∫ntegrabℓε ∂iﬀerentiαℓs · unorganised notes, code, and writings of random topics

Bansal and Modha (2004) CAR: Clock with Adaptive Replacement (FAST)

March 29, 2010 paper

This is an improvement over ARC by combining ARC with Clock (second-chance) cache replacement algorithm. Like ARC, there are two LRU queues and each queue is separated from cache (\(T\)) and directory (\(T+B\)). But instead of a simple queue, the LRU are now implemented in a circular queue with a... [more]

Megiddo and Modha (2004) Outperforming LRU with an Adaptive Replacement Cache Algorithm (IEEE Computer)

March 29, 2010 paper

Also as “ARC: A Self-Tuning, Low Overhead Replacement Cache” by the same authors. In Proceedings of 2nd USENIX Conference on File and Storage Technologies (FAST), pp.115–130, San Francisco CA, Mar 31–Apr 2 2003. [more]

Fredman and Tarjan (1987) Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms (JACM)

March 15, 2010 paper

This is the paper that proposed Fibonacci Heap (aka F-heap). Detail is also found on http://en.wikipedia.org/wiki/Fibonacci_heap and also chapter 20 of Introduction to Algorithms 2/e. [more]

Liu et al (2008) Modeling and Quantifying the Impact of P2P File Sharing Traffic on Traditional Internet Traffic (22nd AINA)

March 9, 2010 paper

The PFTK formula gives the steady state throughput of a bulk transfer TCP flow as a function of loss rate and RTT: [more]

Divakaran et al (2010) Size-based Flow Scheduling in a CICQ Switch

March 6, 2010 paper

CICQ = Combined Input-crosspoint Queued Switch [more]