Cui, Ying and Medard, Muriel and Yeh, Edmund and Leith, Douglas J. and Duffy, Ken R.
(2011)
Sample path large deviations of Poisson shot noise with heavy tail
semi-exponential distributions.
Journal of Applied Probability, 48 (3).
pp. 688-698.
ISSN 0021-9002
Abstract
The problem of finding network codes for general
connections is inherently difficult. Resource minimization for
general connections with network coding is further complicated.
The existing solutions mainly rely on very 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 (RLNC) 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 Constraint Satisfaction Problem (CSP) which we show can be
simplified to have a moderate number of constraints. While CSPs
are NP-complete in general, we present a probabilistic distributed
algorithm with almost sure convergence in finite time by applying
Communication Free Learning (CFL). Our approach allows fairly
general coding across flows, guarantees no greater cost than
routing, and shows a possible distributed implementation.
| Item Type: |
Article
|
| Additional Information: |
This is the preprint version of the published article, which is available at doi:10.1239/jap/1316796907 |
| Keywords: |
Heavy-tailed distribution; sample path large deviation; Poisson shot noise; |
| Academic Unit: |
Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: |
6217 |
| Identification Number: |
https://doi.org/10.1239/jap/1316796907 |
| Depositing User: |
Dr Ken Duffy
|
| Date Deposited: |
29 Jun 2015 14:40 |
| Journal or Publication Title: |
Journal of Applied Probability |
| Publisher: |
Applied Probability Trust |
| Refereed: |
Yes |
| URI: |
|
| 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)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric