| Journal of Network and Systems Management |
| © Springer Science+Business Media, Inc. 2006 |
| 10.1007/s10922-005-9019-0 |
Gerhard Kramer1, 3
and Serap A. Savari2
| (1) | Mathematics of Communications Research Department, Bell Labs, Lucent Technologies, New Jersey, USA |
| (2) | Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan, USA |
| (3) | Mathematics of Communications Research Department, Bell Labs, Lucent Technologies, 600 Mountain Ave, Murray Hill, New Jersey, USA |
![]() |
Gerhard Kramer Email: gkr@research.bell-labs.com |
Published online: 15 March 2006
KEY WORDS: Network capacity - network coding - active networks - d-separation
In recent years there has been considerable interest in technologies known as active networks [1] that permit network nodes to execute computations specific to the packets passing through them. The programmability of infrastructure is the key innovation in this approach to network architecture; the added flexibility provides a means to implement novel transmission techniques to improve performance. A small subset of the literature on active networks can be found in [1–6].
and
, and each of the directed edges has unit capacity. Each source seeks to send a unit-rate information stream to its destination.
This is impossible in the traditional routing regime where intermediate relays can only forward the information received. However, with network coding [8] a processor that receives information can transmit a different function of this information on each of its outgoing edges. Fig. 1 illustrates that an appropriate choice of functions makes the desired rates feasible (the “
“ in Fig. 1 is the XOR of the bits x and y). In fact, both destination terminals can decode both messages.
Network coding has become an intensely studied interdisciplinary subfield of information theory since the publication of [8]. Recent work has exploited ideas and techniques from many areas including randomized algorithms, algebraic coding theory, matrix theory, and graph theory. An updated web page [9] lists many publications in the area.
There are several approaches to implementing network codes. One approach designs fixed coding functions for each processor based on a centralized knowledge of the network topology. A second approach (see, e.g., [10–12]) is motivated by issues arising in distributed or dynamic scenarios where centralized control is impractical. This approach has each vertex transmit on its outgoing edges a randomly chosen linear combination of the information from its incoming edges. For decoding, one requires packets to have headers that inform the destinations of which linear combinations were chosen to form the packets. Each header is modified dynamically as the packets flow through, and are combined by, the network vertices. For example, to keep the header size limited, relaying vertices might wish to decode packets and then re-encode them based on local information. The headers can thus be considered as executable code carried by the packets. Random network coding is therefore a promising active network application since it demonstrates the potential payoff in sending executable code rather than just data.
The headers in the above-mentioned example change the function of network vertices at a fast timescale. An example of an application that reconfigures the network at a slower time scale is when a centralized management system multicasts commands that tune the network, or perhaps even the network codes themselves. In the former case, one would network code the executable code itself. In the latter case, an active packet might contain executable code that installs network codes along certain paths or subgraphs based upon conditions that this active packet meets along its route. One can consider this to be an autonomously installed or temporary network-coded overlay network.
Another consideration in network communication is that the information sent from one processor to another might be lost, e.g., due to congestion, or is corrupted by errors. Active networks offer each processor the opportunity to change its coding functions depending on the error statistics. Since there is a tradeoff between network coding rate and reliability, actively managing network coding rates according to this tradeoff should prove useful.
Yet another application is a new approach to network management for protection from and recovery of link failures (see, e.g., [13, 14]). Here the network is modeled as a finite-state machine where the operation of a processor is affected by management signals that indicate the current link failures and/or directions for recovery behavior. Among the contributions of [13] are bounds on management requirements for several network connection problems.
A further benefit of network coding has been to improve the allocation of physical and medium-access layer resources in wireless ad hoc networks [15, 16]. For example, suppose one is given a collection of end-to-end communication demands and an objective of minimizing power consumption. It was demonstrated that network codes increase the energy efficiency over traditional routing for a particular cross-layer optimization over the physical layer, network layer, and link layer.
The aim of this paper is to develop theoretical bounds on the communication rates that can be attained using network coding. We thereby also determine bounds on the performance of active networks. The value of the theory is, e.g., to help determine how well tuned an active or coded network really is.
Our problem can be considered to be a generalization of the classical problem of bounding the maximal flow from one vertex to another in a graph subject to capacity limitations on arcs or edges. Fifty years ago, L. R. Ford, D. R. Fulkerson, and other individuals discovered the celebrated “max-flow min-cut” theorem that states that the maximal flow is the minimum capacity among all edge cuts separating the source and destination vertices [17–20]. A related bound additionally partitions the vertex set into two disjoint sets, and in [21] we developed this latter type of bound for network coding. However, as pointed out in [7, pp. 16–17], sometimes tighter bounds can be found by considering `disconnecting edge sets.` In this paper, we present an information-theoretic counterpart to this latter type of bound. We do this by borrowing from the artificial intelligence literature [22] the concept of d-separation in Bayesian networks.
Bayesian networks are graphs whose vertices represent random variables, and d-separation is a graphical procedure that establishes the conditional statistical independence of certain sets of these random variables. We will here consider special types of Bayesian networks known as functional dependence graphs (FDGs) and we use a strengthened version of an extension of d-separation called fd -separation that appeared in [23, ch. 2].
with vertex and edge sets
![]() |
(2.1) |
![]() |
(2.2) |
for
, and where
is the capacity of edge e. Consider further a subset
of
called terminals, some of which are sources and some of which are sinks. An edge cut is a set
of edges that disconnects sources from sinks. (Edge cuts in directed graphs are sometimes called directed cuts or disconnecting edge sets.) Rather intuitively, the sum of the routing rates of the source-destination pairs that are disconnected by
is upper bounded by the sum of the capacities of the edges in
.
We would like to apply edge-cut bounds to network coding. Such bounds clearly apply to undirected graphs and one can prove this by using the techniques of [21]. Unfortunately, a standard example shows that edge-cut bounds do not necessarily apply to directed graphs. Consider the network with unit-capacity edges shown in Fig. 1. There are two source-destination pairs
and
, and we write their respective rates as
and
. The set
is an edge cut for both sources so the edge-cut bound states that
with routing. However, network coding achieves
by forming the XOR of the bits x and y on the respective edges (1, 3) and (2, 3), and sending the result down edges (3, 4), (4, 5), and (4, 6). This example shows
that one cannot always rely on edge-cut bounds when using network codes. The main purpose of this paper is to develop an alternative
to edge-cut bounds that does apply to network coding. We further use the bound to derive new capacity theorems for network
information flow.
For our analysis, we assume that the reader is familiar with concepts of information theory (see [24, ch. 2]). We write
, and
for the respective entropy of the random variable X, the joint entropy of the random variables X and Y, and the entropy of X conditioned on Y. We further write I(X; Y) and I(X; Y|Z) for the respective mutual information between X and Y, and the mutual information between X and Y when conditioned on the random variable Z.
for the probability that
and
when the event
occurs, assuming that
. As usual, for discrete random variables we say that X and Y are statistically independent when conditioned on Z if
![]() |
(2.3) |
Alternatively, we say that
forms a Markov chain. We remark that
forms a Markov chain if and only if
![]() |
(2.4) |
| • | The network is clocked, i.e., a universal clock ticks N times. | ||
| • |
Vertex u transmits a symbol after clock tick and before clock tick n for .
|
||
| • |
Vertex receives symbols , at clock tick n. Note that there is a small delay between transmission and reception that ensures the network operates in a causal fashion. The output is in general a noisy function of the channel input , i.e., for all and all n we have
for some function
, where is a noise random variable that is statistically independent of all other noise and message random variables. For simplicity
we will often model the edge channels as being noise-free, i.e., we will mostly consider channels with for all u and . However, our results do extend to noisy channels. We demonstrate this by an example below.
|
||
| • |
There are K independent messages , in the network. One might think of the as being “commodities.'' For the multicommodity flow problem [27, p. 1221], message is associated with a vertex pair , and one wishes to transmit units of data from to simultaneously for all k. The meaning is that is the source vertex and is the sink or destination vertex. In communications, refers to the rate of message k.
|
||
| • |
A more general problem is the multimessage multicasting problem, where several destinations decode each message . We write for the number of destinations decoding . More precisely, message is associated with the vertices and one wishes to transmit units of data from to , simultaneously for all and .
|
||
| • |
Let be the set of messages originating at vertex u. The input is a function of and vertex u's past channel outputs
is a vector that includes the nth channel outputs from all edges incident to u. Note also that is any function of and , so that we are permitting joint channel coding, routing, and/or network coding. We distinguish between routing and network coding in that routing permits
message symbols and arriving packets (groups of input or output symbols) to be stored, reordered, and collected into other packets. Network coding, however, additionally
allows packets to be combined to create new packets.
|
||
| • |
Suppose is destined for vertex . After transmission is completed, vertex puts out its estimate of . Note that is a function of vertex 's messages and its channel outputs .
|
||
| • |
A rate-tuple ( is said to be achievable if there exist encoders and decoders such that
. The capacity region
is the closure of the set of achievable rate-tuples.
|
We will use the calculus of d-separation and fd-separation in FDGs. FDGs are graphs where the vertices represent random variables and the edges represent the functional
dependencies between the random variables [23, 26]. For instance, suppose we have
random variables that are defined by
independent (or source) random variables by
functions. An FDG
is a directed graph having
vertices representing the random variables and in which edges are drawn from one vertex to another if the random variable
of the former vertex is an argument of the function defining the random variable of the latter vertex.
is a function of the message
and
(in fact,
is a function of
and the past
only). The message estimate
of W
2 at vertex 1 is also a function of W
1 and
. The channel inputs
are a function of W
2 and
, and the estimate
is a function of
. The S
RV
=2 vertices representing the independent W
1 and W
2 are distinguished by drawing them with a hollow circle. Note that Fig. 3 is the line graph of Fig. 2 with the addition of vertices representing the messages and their estimates, and edges representing the functional relations
of these new vertices to the existing ones.
By d-separation we mean the following reformulation of a definition in [22, p. 117] that is described in [23, 26].
,
and
be disjoint subsets of the vertices of a FDG
.
is said to d-separate
from
if there is no path between a vertex in
and a vertex in
after the following manipulations of the graph have been performed.
A fundamental result of [22, section 3.3] is that d-separation establishes conditional independence in FDGs having no directed cycles. That is, if
d-separates
from
in
and we collect the random variables of the vertices in
and
in the respective vectors X, Y and Z, then X-Z-Y forms a Markov chain.
A simple extension of d-separation is known as fd-separation which uses the fact that the FDG represents functional relations, and not only Markov relations as in Bayesian networks (see [23, ch. 2]). For fd-separation, after the second step above one successively removes all edges coming out of vertices without incoming edges, excepting the source (or message) vertices. One can, in fact, also successively remove all edges on cycles without incoming edges, and we shall refer to this strengthened version of the definition in [23, p. 15] as fd-separation. We remark that fd-separation applies to FDGs with cycles, as long as all subgraphs of the FDGs are also FDGs (this result follows directly from [23, ch. 2] and will be proved in a future paper).
The bound we develop begins with a set of edges ɛd like the edge-cut bound. However, in addition to computing the sum of the capacities of these edges, we must perform a series of verification steps. Consider a set S d of source indices and an ordering of these indices via a one-to-one mapping π(·) from {1, 2,舰,|S d|} to S d, where |S d| is the cardinality of S d The reason for introducing this ordering will become clear when we consider some examples below.
and similarly for
and
. The following steps describe our bound for noise-free networks. Let
be the channel inputs of the edges ɛ
d
, S
d be the messages with indices in
, and
be the complement of S
d in {1,2, 舰, K}.
| 1) |
(Initialization) Consider the FDG corresponding to the network graph , i.e., the line graph of with the addition of vertices and edges representing the messages and their estimates (see, e.g., Figs. 2 and 3).
|
| 2) |
(Iterations) If is not disconnected (in an undirected sense) from one of its estimates , then stop (one has no bound). If is disconnected (in an undirected sense) from all of its estimates then:
|
| 3) |
(Termination and Bound) Increment k. If go to the previous step. If k=K+1, then we have
|
![]() |
(5.1) |
. The term “d-separation” describes the use of fd-separation in steps 1 and 2 above. We remark that the PdE bound includes as special cases those bounds based on edge cuts
that partition
into two disjoint sets ([21
],[24, section 14.10]).
and
, and the resulting graph
is shown in Fig. 4. We choose π(.) to be the identity mapping, i.e., we choose the ordering W
1, W
2. For k=1, we must check if W
1 is disconnected from ŵ1 in an undirected sense. However, there is an undirected path from W
1 to ŵ1 so we must stop without a bound. A similar conclusion to the procedure occurs if we choose the ordering W
2, W
1. Thus, as required, we cannot claim that
.
is the graph in Fig. 3. Suppose that C
e
=1 for all e. We choose
, and the resulting graph
is shown in Fig. 5. We next choose π(.) to be the identity mapping. For k=1, we must check if W
1 is disconnected from
which is indeed the case. The next graph
has only one edge and W
2 is disconnected from
. We thus have the desired bound R
1+R
2 (this type of edge-cut bound first appeared in [21]).
in the FDGs. One further replaces
by
in the first step in Section 5,where
is the complement of
in ɛ. The value Ce in (5.1) is now the capacity of the channel of edge e. For example, consider the FDG in Fig. 6 that is a noisy version of the FDG in Fig. 3. The noise random variables
are represented as open circles inside the triangle formed by the cycle
![]() |
replaced by
) will give graphs like those in Fig. 5.
The above procedure extends to undirected graphs with a few extra steps. The main addition is that one replaces every undirected
edge e=(u, v) with capacity C
e
by a pair of oppositely directed edges labeled by the entropies
and
. One then requires that
. We remark that it is often more convenient to draw only the bidirected version of the undirected graph without formally
converting it into a line graph.
(we have labeled only some of the edges to avoid cluttering the figure with notation). One can construct the FDG line graph
directly from this graph.
Suppose that the undirected edges have capacity two. Hu showed that the vertex-partitioning cut-set bound permits the rate
triple
but routing requires R
3=0 when (R
1, R
2)=(4, 2). We wish to determine if the same is true with network coding. We choose
and S
d={1} from which we obtain
, with equality only if C
63=C65=0. Similarly, with
and S
d={1} we require C
21=C
41=0 for R
1=4. Combining these results, we can restrict attention to the graph in Fig. 9.
Thus, if
and R
2=2 we require R
3=0 with or without network coding.
Suppose that the undirected edges have unit capacity. Okamura and Seymour showed that the vertex-partitioning cut-set bound
permits the rate-tuple
but routing cannot achieve this set of rates [29]. In fact, the best symmetric rate with routing is R
k
=3/4 for k=1, 2, 3, 4.
, and
. The resulting graph G
xyz is shown in Fig. 12. We find that
![]() |
(7.5) |
![]() |
(7.6) |
![]() |
(7.7) |
![]() |
(7.8) |
and
We find that
![]() |
(7.9) |
![]() |
(7.10) |
![]() |
(7.11) |
![]() |
(7.12) |
![]() |
(7.13) |
Upper bounds on network coding rates are currently being developed by other groups [30, 31]. Some of the distinguishing features of our work are (see [33]): the PdE bound applies to general multimessage multicast, we have a formal procedure for generating rate bounds by using FDGs and d-separation (which makes a connection to the artificial intelligence literature), the progressive nature of our fd-separation bound strengthens an approach based on cutting edges only at the first step, and FDGs let us treat noisy networks as well as noise-free ones.
| • | ɛ d : a set of edges |
| • | S d: a set of source indices |
| • |
π(.): a one-to-one mapping from to S
d.
|
| • |
a nonempty subset of for all .
|
For the last item, recall that Wk is associated with the vertices
, so we are considering some subset
of the vertices t
k
(i), i=1, 2,舰, D
k
. We write the corresponding subset of estimates as
.
![]() |
(A.1) |
and bound
![]() |
(A.2) |
, (b) follows because the messages and noise are statistically independent, and (c) follows by the chain rule for mutual information
and because success in step 2) in Section 5 implies that
![]() |
(A.3) |
![]() |
(A.4) |
![]() |
(A.5) |
![]() |
(A.6) |
| 1. | S. F. Bush and A. B. Kulkarni, Active Networks and Active Network Management, Kluwer Academic, New York, 2001. |
| 2. | S. F. Bush, Active Virtual Network Management Prediction: Complexity as a Framework for Prediction, Optimization, and Assurance, Available at http://arxiv.org/PS_cache/cs/pdf/0203/0203014.pdf |
| 3. | D. S. Alexander, W. A. Arbaugh, M. W. Hicks, P. Kakkar, A. D. Keromytis, J. T. Moore, C. A. Gunter, S. M. Nettles, and J. M. Smith, The SwitchWare Active Network Architecture, IEEE Network, Vol. 12, No. 3, pp. 27–36, 1998. |
| 4. | K. Calvert, ed. Active Networks Framework, Available at http://www.cc.gatech.edu/projects/canes/papers/arch-1-0.ps.gz |
| 5. | M. Hicks, P. Kakkar, T. Moore, C. Gunter, and S. Nettles, PLAN: A Programmable Language for Active Networks, ACM SIGPLAN Notices, Vol. 34, No. 1, pp. 86–93, 1999. |
| 6. | D. Wetherall, J. Guttag, and D. Tennenhouse, ANTS: Network Services Without the Red Tape, Computer, Vol. 32, No. 4, pp. 42–48, 1999. |
| 7. | L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962. |
| 8. | R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, Network information flow, IEEE Transactions on Information Theory, Vol. 46, No. 4, pp. 1204–1216, 2000. |
| 9. | R. Koetter, Available at http://tesla.csl.uiuc.edu/koetter/NWC/ |
| 10. | P. A. Chou, Y. Wu, and K. Jain, Practical network coding, In: Proceedings of the 41st Allerton Conference on Communication, Control and Computing, Monticello, IL, 2003. |
| 11. | T. Ho, M. Médard, J. Shi, D. R. Karger, and M. Effros, On randomized network coding, In: Proceedings of the 41st Allerton Conference on Communication, Control and Computing, Monticello, IL, 2003. |
| 12. | T. Ho, B. Leong, M. Médard, R. Koetter, Y.-H. Chang, and M. Effros, On the utility of network coding in dynamic environments, In: Proceedings of the International Workshop on Wireless Ad-hoc Networks (IWWAN), Oulu, Finland, 2004. |
| 13. | T. Ho, M. Médard, and R. Koetter, An Information-Theoretic View of Network Management, IEEE Transactions on Information Theory, Vol. 51, No. 4, pp. 1295–1312, 2005. |
| 14. | R. Koetter and M. Médard, An Algebraic Approach to Network Coding, IEEE/ACM Transactions on Networking, Vol. 11, No. 5, pp. 782–795, 2003. |
| 15. | Y. Wu. P. A. Chou, and S.-Y. Kung, Minimum-energy multicast in mobile ad hoc networks using network coding, In Proceedings of the Information Theory Workshop 2004, San Antonio, TX, 2004. |
| 16. | Y. Wu, P. A. Chou, Q. Zhang, K. Jain, W. Zhu, and S.-Y. Kung, Network Planning in Wireless Ad Hoc Networks: A Cross-Layer Approach, IEEE Journal on Selected Areas of Communications. Vol. 23, no. 1, pp. 136–150, 2005. |
| 17. | G. B. Dantzig and D. R. Fulkerson, On the max-flow, min-cut theorem of networks, In: H. W. Kuhn (ed.), Linear Inequalities, Annals of Mathematical Studies, Number 38, Princeton University Press, Princeton, NJ, pp. 215–221, 1956. |
| 18. | P. Elias, A. Feinstein, and C. E. Shannon, A Note on the Maximum Flow through a Network, IRE Transactions on Information Theory, Vol. 2, No. 4, pp. 117–119, 1956. |
| 19. | L. R. Ford and D. R. Fulkerson, Maximal Flow through a Network, Canadian Journal of Mathematics, Vol. 8, No. 3, pp. 399–404, 1956. |
| 20. | J. T. Robacker, On Network Theory, The RAND Corporation, Research Memorandum RM-1498, May 26, 1955. |
| 21. | G. Kramer and S. A. Savari, On networks of two-way channels, In: A. Ashikhmin and A. Barg (eds.), Algebraic Coding Theory and Information Theory, DIMACS Workshop, Dec. 15-18, 2003, Rutgers University, Vol. 68: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, Rhode Island, pp. 133–143, 2005. |
| 22. | J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo. CA, 1988. |
| 23. | G. Kramer, Directed Information for Channels with Feedback, Hartung-Gorre Verlag, Konstanz, 1998, ETH Series in Information Processing, Vol. 11. |
| 24. | T. M. Cover and J. A. Thomas, Elements of information Theory, Wiley, New York, 1991. |
| 25. | S. P. Borade, Network information flow: Limits and achievability, In: Proceedings of the IEEE International Symposium on Information Theory, Lausanne, Switzerland, p. 139, June 30-July 5, 2002. |
| 26. | G. Kramer, Capacity Results for the Discrete Memoryless Network, IEEE Transactions on Information Theory, Vol. 49, No. 1, pp. 4–21, 2003. |
| 27. | A. Schrijver, Combinatorial Optimization, Springer-Verlag, New York, 2003. |
| 28. | T. C. Hu, Multi-commodity Network Flows, Operations Research, Vol. 11, No. 3, pp. 344–360, 1963. |
| 29. | H. Okamura and P. D. Seymour, Multicommodity Flows in Planar Graphs, Journal of Combinatorial Theory, Series B, Vol. 31, No. 1, pp. 75–81, 1981. |
| 30. | N. J. A. Harvey, R. D. Kleinberg, and A. R. Lehman. On the Capacity of Information Networks, IEEE Transactions on Information Theory, in press. |
| 31. | K. Jain, P. A. Chou, V. V. Vazirani, R. Yeung, and G. Yuval, On the Capacity of Multiple Unicast Sessions in Undirected Graphs, IEEE Transactions on Information Theory, in press. |
| 32. | DIMACS Working Group on Network Coding, DIMACS Center, Rutgers University, Piscataway, NJ, Jan. 26–28, 2005, Available at http://dimacs.rutgers.edu/Workshops/NetworkCodingWG. |
| 33. | G. Kramer and S. A. Savari. Progressive d-separating edge set bounds on network coding rates, In: Proceedings of the 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, Sept. 2005. |