A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem

Ying Cui, Muriel Medard, Edmund Yeh, Douglas Leith, Fan Lai, Ken R. Duffy

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)3441-3454
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume25
Issue number6
DOIs
StatePublished - Dec 2017
Externally publishedYes

Keywords

  • distributed algorithm
  • general connection
  • Network coding
  • network mixing
  • resource optimization

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem'. Together they form a unique fingerprint.

Cite this