Sarit Buzaglo – Consecutive Switch Codes


Event Details

  • Date:

Switch codes are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is a device that is used to connect between a computer network and external devices. The main task of the network switch is to process and forward packets from the input ports to the output ports. Assume that in each time slot, called a generation, each input port transmits one data packet and each output port receives one packet. Upon arrival, the packets from the input ports are stored in a switch fabric comprising multiple memory banks. Then, the network switch processes packets from these banks and outputs one packet through each of the output ports.

Switch codes are a coding scheme which enables one to encode the input packets into the banks such that the packet requests by the output ports can be answered efficiently. Mathematically speaking, a switch code is required to satisfy the following property. Assume that there are $n$  input ports, $k$ output ports, and $m$ banks. In each generation the $n$ packets from the input ports are encoded into $m$ packets which are stored in the banks. Then, every request from the output ports for $k$ packets, which may come from previous generations, has to be answered by reading at most one packet from each bank.

In this work we present a construction of binary switch codes that improves upon the best binary switch codes for the case $n=k$. We also study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we callconsecutive requests. In an $\ell$-consecutive request of $k$ packets, the $k$ packets are required to belong to $\ell$-consecutive generations. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of our construction of combinatorial 2-consecutive switch codes.

Joint work with Eitan Yaakobi, Yuval Cassuto, and Paul H. Siegel.