CaltechAUTHORS
  A Caltech Library Service

Switch Codes: Codes for Fully Parallel Reconstruction

Wang, Zhiying and Kiah, Han Mao and Cassuto, Yuval and Bruck, Jehoshua (2017) Switch Codes: Codes for Fully Parallel Reconstruction. IEEE Transactions on Information Theory, 63 (4). pp. 2061-2075. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20170315-151626957

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:20170315-151626957

Abstract

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2017.2664867DOIArticle
http://ieeexplore.ieee.org/document/7843662/PublisherArticle
Additional Information:© 2017 IEEE. Manuscript received November 29, 2015; revised September 25, 2016; accepted January 13, 2017. Date of publication February 6, 2017; date of current version March 15, 2017. Z. Wang was supported by NSF under Grant CCF-1566587. H. M. Kiah was supported by the Singapore Ministry of Education Tier 1 under Grant 2016-T1-001-156. Y. Cassuto was supported by the Israel Science Foundation joint ISF-UGC program. Part of the results in this paper were presented at the 2013 and 2015 IEEE International Symposia on Information Theory. Communicated by A. G. Dimakis, Associate Editor for Coding Techniques.
Funders:
Funding AgencyGrant Number
NSFCCF-1566587
Ministry of Education (Singapore)2016-T1-001-156
Israel Science FoundationUNSPECIFIED
Subject Keywords:Distributed-storage codes, network switches, batch codes, combinatorial designs
Record Number:CaltechAUTHORS:20170315-151626957
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170315-151626957
Official Citation:Z. Wang, H. M. Kiah, Y. Cassuto and J. Bruck, "Switch Codes: Codes for Fully Parallel Reconstruction," in IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2061-2075, April 2017. doi: 10.1109/TIT.2017.2664867
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:75155
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:16 Mar 2017 17:00
Last Modified:16 Mar 2017 17:00

Repository Staff Only: item control page