Research Article
Only the source’s and sink’s neighborhood matters: convergence results for unicast and multicast connections on random graphs and hypergraphs.
@INPROCEEDINGS{10.4108/icst.valuetools.2013.254415, author={Muriel Medard and J\^{e}r\~{o}me Casse}, title={Only the source’s and sink’s neighborhood matters: convergence results for unicast and multicast connections on random graphs and hypergraphs.}, proceedings={7th International Conference on Performance Evaluation Methodologies and Tools}, publisher={ICST}, proceedings_a={VALUETOOLS}, year={2014}, month={1}, keywords={network coding random networks}, doi={10.4108/icst.valuetools.2013.254415} }- Muriel Medard
Jérôme Casse
Year: 2014
Only the source’s and sink’s neighborhood matters: convergence results for unicast and multicast connections on random graphs and hypergraphs.
VALUETOOLS
ACM
DOI: 10.4108/icst.valuetools.2013.254415
Abstract
We study the maximum ow on random weighted directed graphs and hypergraphs, that generalize Erdos-Renyi graphs. We show that, for a single unicast connection chosen at random, its capacity, determined by the max-ow between source and sink, converges in probability to the capacity around the source or sink. Using results from network coding, we generalize this result to di erent types multicast connections, whose capacity is given by the max- ow between the source(s) and sinks. Our convergence results indicate that the capacity of unicast and multicast connections using network coding are, with high probability, una ected by network size in random networks. Our results generalize to networks with random erasures.
Copyright © 2013–2024 ICST