CODING FOR IMPROVED THROUGHPUT PERFORMANCE IN NETWORK SWITCHES
ABSTRACT
Network switches and routers need to serve packetwrites and reads at rates that challenge the most advancedmemory technologies. As a result, scaling the switching rates iscommonly done by parallelizing the packet I/Os using multiplememory units. For improved read rates, packets can be codedupon write, thus giving more flexibility at read time to achievehigher utilization of the memory units. This paper presents adetailed study of coded network switches, and in particular, howto design them to maximize the throughput advantages overstandard uncoded switches. Toward that objective, the papercontributes a variety of algorithmic and analytical tools toimprove and evaluate the throughput performance. The mostinteresting finding of this paper is that the placement of packetsin the switch memory is the key to both high performance andalgorithmic efficiency. One particular placement policy we call“design placement” is shown to enjoy the best combination ofthroughput performance and implementation feasibility
EXISTING SYSTEM:
The use of coding for improved memory read rates joinsa large body of recent work aimed at objectives of a similarflavor, see e.g. the survey in, the effect ofMDS coding on content download time was analyzed for twocontent access models, where an improvement in performancewas achieved. In, latency delay was reduced by choosingMDS codes of appropriate rates. Latency comparison betweena simple replication scheme and MDS codes was pioneered byHuang et al. using queuing theory. It was shown that fork =2, the average latency for serving a packet decreasessignificantly when a certain scheduling model is used. Thisanalysis was later extended by Shah et al., wherebounds on latency performance under multiple schedulingpolicies were investigated. In and then in, switch codingis done under a strong model guaranteeing simultaneousreconstruction of worst-case packet requests
PROPOSED SYSTEM;
In the coded switching paradigm we propose in this paper,our objective is to maximize the number of full packets readfrom the switch memory simultaneously in a read cycle.The packets to read at each read cycle are specified in arequest issued by the control plane of the switch. As weshall see, coding the packets upon their write can significantlyincrease the number of read packets, in return to a smallincrease in the write load to store the redundancy. Thus codingcan significantly increase the overall switching throughput.In this paper we identify and study two key components forhigh-throughput coded switches: 1) Read algorithms that canrecover the maximal number of packets given an arbitraryrequest for previously written packets, and 2) Placementpolicies determining how coded chunks are placed in theswitch MUs. Our results contribute art and insight for eachof these two components, and more importantly, they revealthe tight relations between them. At a high level, the choice ofplacement policy can improve both the performance and thecomputational efficiency of the read algorithm. To show theformer, we derive a collection of analysis tools to calculateand/or bound the performance of a read algorithm given theplacement policy in use. For the latter, we show a hugegap between an NP-hard optimal read problem for one policy(unrestricted placement), and extremely efficient optimalread algorithms for two others (cyclic and design placements).
CONCLUSION
In this paper, we studied placement policies and readalgorithms of coded packets in a switch memory. The studyrevealed that coding can significantly improve switchingthroughput, and that the choice of placement has significanteffect on performance and complexity. We proved that inits most general form, the problem of obtaining maximumthroughput for a set of requested packets is a hard problem.Therefore, we moved to propose two practical placementpolicies and efficient optimal read algorithms, with betterthroughput performance in certain cases compared to thegeneral non-structured placement policy.We demonstrated tradeoffs between write flexibility, readalgorithmcomplexity and performance. In particular, we sawthat no choice of placement policy is universally optimal,and provided analytic tools for choosing a policy wisely. Ourwork leaves many interesting problems for future research. Forexample, one may consider other structured write policies byimposing different constraints rather than restricting pairwiseintersections. It is also interesting to consider variable-lengthcodes (i.e., varying values of k and n values for each packet),to match the expected switch load.
REFERENCES
[1] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey onnetwork codes for distributed storage,” Proc. IEEE, vol. 99, no. 3,pp. 476–489, Mar. 2011.
[2] G. Joshi, Y. Liu, and E. Soljanin, “Coding for fast content download,” inProc. 50th Annu. Allerton Conf. Commun., Control, Comput. (Allerton),Oct. 2012, pp. 326–333.
[3] G. Joshi, Y. Liu, and E. Soljanin, “On the delay-storage trade-off incontent download from coded distributed storage systems,” IEEE J. Sel.Areas Commun., vol. 32, no. 5, pp. 989–997, May 2014.
[4] G. Liang and U. C. Kozat, “FAST CLOUD: Pushing the envelope ondelay performance of cloud storage with coding,” IEEE/ACM Trans.Netw., vol. 22, no. 6, pp. 2012–2025, Dec. 2014.
[5] L. Huang, S. Pawar, H. Zhang, and K. Ramchandran, “Codes canreduce queueing delay in data centers,” in Proc. IEEE Int. Symp. Inf.Theory (ISIT), Jul. 2012, pp. 2766–2770.
[6] N. Shah, K. Lee, and K. Ramchandran, “When do redundant requestsreduce latency?” in Proc. 51st Annu. Allerton Conf. Commun., Control,Comput., Oct. 2013, pp. 731–738.
[7] N. B. Shah, K. Lee, and K. Ramchandran, “The MDS queue: Analysingthe latency performance of erasure codes,” in Proc. IEEE Int. Symp. Inf.Theory (ISIT), Jun. 2014, pp. 861–865.
[8] Z. Wang, O. Shaked, Y. Cassuto, and J. Bruck, “Codes for networkswitches,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2013,pp. 1057–1061.
[9] Z. Wang, H. M. Kiah, and Y. Cassuto, “Optimal binary switch codeswith small query size,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT),Jun. 2015, pp. 636–640.
[10] T. K. Moon, Error Correction Coding: Mathematical Methods andAlgorithms. Hoboken, NJ, USA: Wiley, 2005.