MURAL - Maynooth University Research Archive Library

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

    Cui, Ying and Medard, Muriel and Yeh, Edmund and Leith, Douglas J. and Li, Fan and Duffy, Ken R. (2017) A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem. IEEE/ACM Transactions on Networking, 25 (6). pp. 3441-3454. ISSN 1063-6692

    Download (3MB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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.

    Item Type: Article
    Keywords: Network coding; network mixing; general connection; resource optimization; distributed algorithm;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 11620
    Identification Number:
    Depositing User: Dr Ken Duffy
    Date Deposited: 05 Nov 2019 14:19
    Journal or Publication Title: IEEE/ACM Transactions on Networking
    Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads