1204 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 46, NO. 4, JULY 2000Network Information FlowRudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Senior Member, IEEE, andRaymond W. Yeung, Senior Member, IEEEAbstract—We introduce a new class of problems called networkinformation flow which is inspired by computer network applica-tions. Consider a point-to-point communication network on whicha number of information sources are to be mulitcast to certain setsof destinations. We assume that the information sources are mu-tually independent. The problem is to characterize the admissiblecoding rate region. This model subsumes all previously studiedmodels along the same line. In this paper, we study the problemwith one information source, and we have obtained a simple char-acterization of the admissiblecoding rate region. Our result can beregarded as the Max-flow Min-cut Theorem for network informa-tion flow. Contrary to one’s intuition, our work reveals that it is ingeneral not optimal to regard the information to be multicast as a“fluid” which can simply be routed or replicated. Rather, by em-ploying coding at the nodes, which we refer to as network coding,bandwidth can in general be saved. This finding may have signifi-cant impact on future design of switching systems.Index Terms—Diversity coding, multicast, network coding,switching, multiterminal source coding.I. INTRODUCTIONLET be the set of nodes of a point-to-point communica-tion network. Such a network is represented by a directedgraph, where is the set of edges, such that in-formation can be sent noiselessly from nodeto node for all. An example of this type of networks is the Internetbackbone, where with proper data link protocols informationcan be sent between nodes essentially free of noise.Letbe mutually independent informationsources. The information rate (in bits per unit time) ofisdenoted by, and let . Letand be arbitrary mappings. The sourceis generated at node , and it is multicast to node forall. The mappings and the vector specify a setof multicast requirements.In this model, the graphmay represent a physical network,while the set of multicast requirements may represent the aggre-Manuscript received February 25, 1998; revised March 6, 2000. This workwas supported in part under Grants CUHK95E/480 and CUHK332/96E fromthe Research Grant Council of the Hong Kong Special Administrative Region,China. The material in this paper was presented in part at the IEEE InternationalSymposium on Information Theory, MIT, Cambridge, MA, August 16–21, 1998R. Ahlswede is with Fakultät für Mathematik, Universität Bielefeld, 33501Bielefeld, Germany (e-mail: [email protected]).N. Cai was with Fakultät für Mathematik, Universität Bielefeld, 33501Bielefeld, Germany. He is now with the Department of Information Engi-neering, The Chinese University of Hong Kong, N.T., Hong Kong (e-mail:[email protected]).S.-Y. R. Li and R. W. Yeung are with the Department of Information En-gineering, The Chinese University of Hong Kong, N.T., Hong Kong (e-mail:[email protected]; [email protected]).Communicated by R. L. Cruz, Associate Editor for Communication Net-works.Publisher Item Identifier S 0018-9448(00)05297-4.gated traffic pattern the network needs to support. In other sit-uations, the graphmay represent a subnetwork in a physicalnetwork, while the set of multicast requirements may pertain toa specific application on this subnetwork, e.g., a video-confer-ence call.In existing computer networks, each node functions as aswitch in the sense that it either relays information from aninput link to an output link, or it replicates information receivedfrom an input link and sends it to a certain set of output links.From the information-theoretic point of view, there is noreason to restrict the function of a node to that of a switch.Rather, a node can function as an encoder in the sense thatit receives information from all the input links, encodes, andsends information to all the output links. From this point ofview, a switch is a special case of an encoder. In the sequel, wewill refer to coding at a node in a network as network coding.Letbe a nonnegative real number associated with theedge, and let . For a fixed set of mul-ticast requirements, a vectoris admissible if and only if thereexists a coding scheme satisfying the set of multicast require-ments such that the coding rate from nodeto node (i.e., theaverage number of bits sent from nodeto node per unit time)is less than or equal tofor all . (At this point weleave the details of a coding scheme open because it is extremelydifficult to define the most general form of a coding scheme. Aclass of coding schemes called-codes will be studied in Sec-tion III.) In graph theory,is called the capacity of the edge. Our goal is to characterize the admissible coding rate re-gion, i.e., the set of all admissible , for any graph andmulticast requirementsand .The model we have described includes both multilevel diver-sity coding (without distortion) [12], [8], [13] and distributedsource coding [14] as special cases. As an illustration, let usshow how the multilevel diversity coding system in Fig. 1 canbe formulated as a special case of our model. In this system,there are two sources,and . Decoder 1 reconstructsonly, while all other decoders reconstruct both and . Letbe the coding rate of Encoder , . In our model, thesystem is represented by the graphin Fig. 2. In this graph,node 1 represents the source, nodes 2, 3, and 4 represent the in-puts of Encoders 1, 2, and 3, respectively, nodes 5, 6, and 7 rep-resent the outputs of Encoders 1, 2, and 3, respectively, whilenodes 8, 9, 10, and 11 represent the inputs of Decoders 1, 2, 3,and 4, respectively. The mappingsand are specified asand0018–9448/00$10.00 © 2000 IEEEAHLSWEDE et al.: NETWORK INFORMATION FLOW 1205Fig. 1. A multilevel diversity coding system.Fig. 2. The graphGrepresenting the coding system in Fig. 1.and represents the information rates of and .Now all the edges inexcept for corre-spond to straight connections in Fig. 1, so there is no constrainton the coding rate in these edges. Therefore, in order to deter-mining, the set of all admissible for the graph (with theset of multicast requirements specified byand , we setfor all edges in except for toobtain the admissible coding rate region of the problem in Fig. 1.A major finding in this paper is that, contrary to one’s in-tuition, it is in general not optimal to consider the