A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem
Open Access
- 6 October 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 25 (6) , 3441-3454
Abstract
The problem of finding network codes for general connections is inherently difficult in capacity constrained networks. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on highly restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a path-based constraint satisfaction problem (CSP) and an edge-based CSP. While CSPs are NP-complete in general, we present a path-based probabilistic distributed algorithm and an edge-based probabilistic distributed algorithm with almost sure convergence in finite time by applying communication free learning. Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.Keywords
All Related Versions
Funding Information
- NSFC (61401272, 61521062)
- National Science Foundation (CNS-1205562)
This publication has 28 references indexed in Scilit:
- A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem2015
- On the representability of integer polymatroids: Applications in linear code construction2015
- Linear index coding and representable discrete polymatroids2014
- Decentralized Constraint SatisfactionIEEE/ACM Transactions on Networking, 2012
- An Edge Reduction Lemma for linear network coding and an application to two-unicast networks2012
- Truncation Technique for Characterizing Linear PolymatroidsIEEE Transactions on Information Theory, 2011
- The Internet Topology ZooIEEE Journal on Selected Areas in Communications, 2011
- Pairwise Intersession Network Coding on Directed NetworksIEEE Transactions on Information Theory, 2010
- On the Index Coding Problem and Its Relation to Network Coding and Matroid TheoryIEEE Transactions on Information Theory, 2010
- Networks, Matroids, and Non-Shannon Information InequalitiesIEEE Transactions on Information Theory, 2007