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.

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

Use this Persistent URL to link to this item:


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
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.
Funding AgencyGrant Number
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:
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
Deposited By: Kristin Buxton
Deposited On:16 Mar 2017 17:00
Last Modified:16 Mar 2017 17:00

Repository Staff Only: item control page