Ho, Tracey and Médard, Muriel and Koetter, Ralf (2005) An information-theoretic view of network management. IEEE Transactions on Information Theory, 51 (4). pp. 1295-1312. ISSN 0018-9448 http://resolver.caltech.edu/CaltechAUTHORS:HOTieeetit05
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:HOTieeetit05
We present an information-theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the input-output relations of network nodes in terms of network codes. This very general concept of network behavior as a code provides a way to quantify essential management information as that needed to switch among different codes (behaviors) for different failure scenarios. We compare two types of recovery schemes, receiver-based and network-wide, and consider two formulations for quantifying network management. The first is a centralized formulation where network behavior is described by an overall code determining the behavior of every node, and the management requirement is taken as the logarithm of the number of such codes that the network may switch among. For this formulation, we give bounds, many of which are tight, on management requirements for various network connection problems in terms of basic parameters such as the number of source processes and the number of links in a minimum source-receiver cut. Our results include a lower bound for arbitrary connections and an upper bound for multitransmitter multicast connections, for linear receiver-based and network-wide recovery from all single link failures. The second is a node-based formulation where the management requirement is taken as the sum over all nodes of the logarithm of the number of different behaviors for each node. We show that the minimum node-based requirement for failures of links adjacent to a single receiver is achieved with receiver-based schemes.
|Additional Information:||© Copyright 2006 IEEE. Reprinted with permission. Manuscript received July 28, 2003; revised June 2, 2004. [Posted online: 2005-04-04] This work was supported in part by the National Science Foundation under Grants CCR-0325496, CCR-0093349, by AFOSR under Grant PT. HoY-1362, and by the HP Wireless Center. T. Ho performed this work while working toward the Ph.D. degree at the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge. Communicated by G. H. Sasaki, Associate Editor for Communication Networks.|
|Subject Keywords:||Graph theory, network coding, network management, network restoration, Shannon theory|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||01 Oct 2006|
|Last Modified:||26 Dec 2012 09:03|
Repository Staff Only: item control page