CaltechAUTHORS
  A Caltech Library Service

Multiple-Access Network Information-Flow and Correction Codes

Dikaliotis, Theodoros K. and Ho, Tracey and Jaggi, Sidharth and Vyetrenko, Svitlana and Yao, Hongyi and Effros, Michelle and Kliewer, Jörg and Erez, Elona (2011) Multiple-Access Network Information-Flow and Correction Codes. IEEE Transactions on Information Theory , 57 (2). pp. 1067-1079. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20110314-145005157

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110314-145005157

Abstract

This work considers the multiple-access multicast error-correction scenario over a packetized network with z malicious edge adversaries. The network has min-cut m and packets of length l, and each sink demands all information from the set of sources S. The capacity region is characterized for both a "side-channel" model (where sources and sinks share some random bits that are secret from the adversary) and an "omniscient" adversarial model (where no limitations on the adversary's knowledge are assumed). In the "side-channel" adversarial model, the use of a secret channel allows higher rates to be achieved compared to the "omniscient" adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the "omniscient" adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential in lm, while the second uses a novel multiple-field-extension technique and has O(lm(|S|) complexity, which is polynomial in the network size. Our code constructions are "end-to-end" in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2010.2095130 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5695099&tag=1PublisherUNSPECIFIED
Additional Information:© 2011 IEEE. Manuscript received April 18, 2010; revised August 03, 2010; accepted September 24, 2010. Date of current version January 19, 2011. The work of T.K. Dikaliotis, S. Vyetrenko, T. Ho, M. Effros, and E. Erez was supported by BAE Systems National Security Solutions, Inc. under subcontract #069153 and by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego, CA, under Contract N66001-08-C-2013, AFOSR under Grant 5710001972, Caltech’s Lee Center for Advanced Networking, and NSF Grant CNS-0905615. The work of S. Jaggi was supported by the RGC GRF Grants 412608 and 412809, the CUHK MoE-Microsoft Key Laboratory of Human-centric Computing and Interface Technologies, the Institute of Theoretical Computer Science and Communications, and Project No. AoE/E-02/08 from the University Grants Committee of the Hong Kong Special Administrative Region, China. The work of H. Yao was supported by the National Natural Science Foundation of China Grant 61033001 and 61073174, the National Basic Research Program of China Grant 2007CB807900 and 2007CB807901, the Hi-Tech research and Development Program of China Grant 2006AA10Z216. The work of J. Kliewer was supported by NSF Grant CCF-0830666. The first five authors, T. K. Dikaliotis, T. Ho, S. Jaggi, S. Vyetrenko, and H. Yao had equal contribution to this work and they are named in alphabetical order. The material in this paper was presented (in part) at the 2009 IEEE International Symposium on Information Theory, Seoul, South Korea, July 2009, and at ITW 2010, Dublin, Ireland, Aug./Sep. 2010. This paper is part of the special issue on “Facets of Coding Theory: From Algorithms to Networks,” dedicated to the scientific legacy of Ralf Koetter.
Funders:
Funding AgencyGrant Number
BAE Systems National Security Solutions, Inc.069153
Defense Advanced Research Projects Agency (DARPA) UNSPECIFIED
Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego, CA N66001-08-C-2013
Air Force Office of Scientific Research (AFOSR)5710001972
Caltech Lee Center for Advanced Networking UNSPECIFIED
NSFCNS-0905615
NSFCCF-0830666
RGC GRF 412608
RGC GRF 412809
CUHK MoE-Microsoft Key Laboratory of Human-centric Computing and Interface Technologies UNSPECIFIED
Institute of Theoretical Computer Science and Communications UNSPECIFIED
University Grants Committee of the Hong Kong Special Administrative Region, ChinaAoE/E-02/08
National Natural Science Foundation of China 61033001
National Natural Science Foundation of China 61073174
National Basic Research Program of China 2007CB807900
National Basic Research Program of China 2007CB807901
Hi-Tech research and Development Program of China 2006AA10Z216
Subject Keywords:Double extended field; Gabidulin codes; network error-correction; random linear network coding; subspace codes
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11769542
Record Number:CaltechAUTHORS:20110314-145005157
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110314-145005157
Official Citation:Dikaliotis, T.K.; Ho, T.; Jaggi, S.; Vyetrenko, S.; Hongyi Yao; Effros, M.; Kliewer, J.; Erez, E.; , "Multiple-Access Network Information-Flow and Correction Codes," Information Theory, IEEE Transactions on , vol.57, no.2, pp.1067-1079, Feb. 2011 doi: 10.1109/TIT.2010.2095130 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5695099&isnumber=5695090
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22870
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:15 Mar 2011 21:16
Last Modified:23 Aug 2016 09:59

Repository Staff Only: item control page