Optimal Placement of NAK-Suppressing Agents for Reliable Multicast: A Partial Deployment Case

摘要

In reliable multicast, receivers use negative acknowledgments (NAKs) to inform the sender about their packet loss. The growth in the number of NAK messages received by the sender results in the well-known feedback (or NAK) implosion problem. Therefore, one important issue for reliable multicast protocols is to utilize an effective mechanism to collect NAK messages from the receivers. One way to avoid feedback implosion at the sender site is to place NAK-suppression agents on the internal nodes (routers) of the network. These agents will forward a single copy of the incoming NAK messages toward the sender site and will suppress additional redundant copies coming from the receivers. In this paper, we consider an agent placement (activation) problem for reliable multicast. First, we assume a network environment where a number of internal nodes (routers) have NAK-suppression capabilities. Then, we try to select a subset of these nodes for NAK suppression task for a given reliable multicast application. Our main selection criteria is to choose a minimum number of such nodes for the task and have a notion of load-balancing among them. In this context, we study two agent activation problems: the Load-Balanced Agent Activation Problem (LBAAP) and the Budgeted Agent Activation Problem (BAAP) and present efficient algorithms for optimal activation of agents. The problems that we consider in this paper are generalized versions of the respective problems introduced by Daescu et al. [3].