A Caltech Library Service

An information-theoretic view of network management

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. doi:10.1109/TIT.2005.844062.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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
Issue or Number:4
Record Number:CaltechAUTHORS:HOTieeetit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5108
Deposited By: Archive Administrator
Deposited On:01 Oct 2006
Last Modified:08 Nov 2021 20:22

Repository Staff Only: item control page