Caching policy and cache allocation design in active reliable multicast


Student thesis: Master's Thesis

View graph of relations


  • Ho Lun WONG

Related Research Unit(s)


Awarding Institution
    Award date16 Oct 2000


    Local loss recovery for reliable multicast can provide significant performance improvement in terms of loss recovery latency, bandwidth consumption and network throughput. Active Reliable Multicast (ARM) is a novel loss recovery scheme for large-scale reliable multicast, where local loss recovery is performed by special routers called active routers. When sufficient cache is available at each active router, ARM gives good loss recovery performance. In practice, cache size is limited and the loss recovery performance of ARM heavily depends on the cache allocation scheme used and the caching policy adopted. When a multicast session starts, a cache allocation scheme determines the amount of cache to be allocated at each active router for supporting this session. For a given cache allocation at an active router, a caching policy specifies which packet should be cached and when a cached packet should be flushed. In this thesis, we first focus on constructing an analytical model for studying the loss recovery performance of ARM. For analytical tractability, a simple first-in-first-out caching policy, called Simple FIFO caching, is adopted such that all cached packets at an active router form a FIFO queue. If a packet arrives and found the queue is full, the "oldest" cached packet will be pushed out for accommodating the new packet. For a given multicast session/tree, the expected loss recovery latency is derived as a function of the cache allocation pattern and the packet loss probabilities on individual links. To further enhance the loss recovery performance of ARM, a probabilistic FIFO caching policy, called P-FIFO caching, is proposed to avoid pre-mature flushing of cached packets. That is when a packet arrives at an active router, it is cached with a predetermined probability. The performance of ARM using P-FIFO caching is compared with that using Simple FIFO caching and that using Timer-based caching policy (proposed by the original ARM). We show that P-FIFO caching gives a comparable performance with a fine-tuned Timer-based caching policy, but with a much less implementation complexity. Since determining optimal cache allocation pattern for a multicast session is a combinatorial optimization problem, searching by enumeration is generally not feasible. Three heuristic cache allocation schemes, namely Equal Sharing, Least Requirement First (LRF) and Proportional Allocation, are proposed for practical size networks. Equal Sharing simply divides the amount of cache equally among all active routers. LRF allocates caches to the active routers with the least basic cache requirements first. Using Proportional Allocation, the amount of caches allocated to an active router is proportional to its basic cache requirement and subject to the total amount of cache constraint. A large part of this thesis is devoted to performance evaluation of ARM using various combinations of four cache allocation schemes, namely optimal allocation (for small size networks), Equal Sharing, LRF and Proportional Allocation, and three caching policies, namely Timer-based, Simple FIFO and P-FIFO caching policies. Three different input traffic models are used; they are constant packet rate, Poisson arrival and ON-OFF traffic model. From the extensive analytical and simulation results, we found that Proportional Allocation with P-FIFO caching policy generally gives the lowest packet loss recovery latency, smallest number of negative acknowledgements received by the sender, and minimal repair packet bandwidth consumption.

      Research areas

    • Multicasting (Computer networks), Cache memory