Abstract
Cloud applications bring new challenges to the design of network elements, in particular accommodating for the burstiness of traffic workloads. Shared memory switches represent the best candidate architecture to exploit buffer capacity; we analyze the performance of this architecture. Our goal is to explore the impact of additional traffic characteristics such as varying processing requirements and packet values on objective functions. The outcome of this work is a better understanding of the relevant parameters for buffer management to achieve better performance in dynamic environments of data centers. We consider a model that captures more of the properties of the target architecture than previous work and consider several scheduling and buffer management algorithms that are specifically designed to optimize its performance. In particular, we provide analytic guarantees for the throughput performance of our algorithms that are independent from specific distributions of packet arrivals. We furthermore report on a comprehensive simulation study which validates our analytic results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiello, W., Kesselman, A., Mansour, Y.: Competitive buffer management for shared-memory switches. ACM Transactions on Algorithms 5(1) (2008)
Aiello, W., Mansour, Y., Rajagopolan, S., Rosén, A.: Competitive queue policies for differentiated services. J. Algorithms 55(2), 113–141 (2005)
Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing 35(2), 278–304 (2005)
Alizadeh, M., Edsall, T., Dharmapurikar, S., Vaidyanathan, R., Chu, K., Fingerhut, A., Lam, V.T., Matus, F., Pan, R., Yadav, N., Varghese, G.: CONGA: distributed congestion-aware load balancing for datacenters. In: ACM SIGCOMM 2014 Conference, pp. 503–514 (2014)
Azar, Y., Litichevskey, A.: Maximizing throughput in multi-queue switches. Algorithmica 45(1), 69–90 (2006)
Azar, Y., Richter, Y.: An improved algorithm for CIOQ switches. ACM Transactions on Algorithms 2(2), 282–295 (2006)
BBC News. US Watchdog to Propose New Net Neutrality Rules (2014). http://www.bbc.com/news/technology-27141121 .
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
Feng, W.C., Kandlur, D.D., Saha, D., Shin, K.G.: Stochastic fair blue: A queue management algorithm for enforcing fairness. In: INFOCOM, pp. 1520–1529 (2001)
Chowdhury, M., Zhong, Y., Stoica, I.: Efficient coflow scheduling with varys. In: SIGCOMM, pp. 443–454 (2014)
Chuprikov, P., Nikolenko, S.I., Kogan, K.: Priority queueing with multiple packet characteristics. In: INFOCOM, pp. 1–9 (2015)
Costa, P., Donnelly, A., Rowstron, A.I.T., O’Shea, G.: Camdoop: Exploiting in-network aggregation for big data applications. In: Proc. 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2012), pp. 29–42 (2012)
Das, S., Sankar, R.: Broadcom smart-buffer technology in data center switches for cost-effective performance scaling of cloud applications (2012). https://www.broadcom.com/collateral/etp/SBT-ETP100.pdf
Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica 53(4), 523–548 (2009)
Eugster, P., Kogan, K., Nikolenko, S., Sirotkin, A.: Shared memory buffer management for heterogeneous packet processing. In: ICDCS (2014)
Floyd, S., Jacobson, V.: Random early detection gateways for congestion avoidance, pp. 397–413 (1993)
CAIDA The Cooperative Association for Internet Data Analysis. http://www.caida.org/
Goldwasser, M.: A survey of buffer management policies for packet switches. SIGACT News 41(1), 100–128 (2010)
Hong, C.-Y., Kandula, S., Mahajan, R., Zhang, M., Gill, V., Nanduri, M., Wattenhofer, R.: Achieving high utilization with software-driven WAN. In: ACM SIGCOMM 2013 Conference, pp. 15–26 (2013)
Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Wanderer, J., Zhou, J., Zhu, M., Zolla, J., Hölzle, U., Stuart, S., Vahdat, A.: B4: experience with a globally-deployed software defined wan. In: ACM SIGCOMM 2013 Conference, pp. 3–14 (2013)
Keslassy, I., Kogan, K., Scalosub, G., Segal, M.: Providing performance guarantees in multipass network processors. IEEE/ACM Trans. Netw. 20(6), 1895–1909 (2012)
Kesselman, A., Kogan, K., Segal, M.: Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing. Distributed Computing 23(3), 163–175 (2010)
Kesselman, A., Kogan, K., Segal, M.: Improved competitive performance bounds for CIOQ switches. Algorithmica 63(1-2), 411–424 (2012)
Kesselman, A., Kogan, K., Segal, M.: Best Effort and Priority Queuing Policies for Buffered Crossbar Switches. Chicago Journal of Theoretical Computer Science (2012)
Kesselman, A., Kogan, K.: Nonpreemptive Scheduling of Optical Switches. IEEE Transactions on Communications 55(6), 1212–1219 (2007)
Kesselman, A., Lotker, Z., Mansour, Y., Patt-Shamir, B., Schieber, B., Sviridenko, M.: Buffer overflow management in QoS switches. SIAM Journal on Computing 33(3), 563–583 (2004)
Kesselman, A., Mansour, Y.: Harmonic buffer management policy for shared memory switches. Theor. Comput. Sci. 324(2-3), 161–182 (2004)
Kogan, K., López-Ortiz, A., Nikolenko, S., Scalosub, G., Segal, M.: Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors. CoRR, abs/1202.5755 (2013)
Kogan, K., López-Ortiz, A., Nikolenko, S., Sirotkin, A.: Multi-queued network processors for packets with heterogeneous processing requirements. In: COMSNETS, pp. 1–10 (2013)
Kogan, K., López-Ortiz, A., Nikolenko, S., Scalosub, G., Segal, M.: Balancing work and size with bounded buffers. In: COMSNETS, pp. 1–8 (2014)
Kogan, K., López-Ortiz, A., Nikolenko, S.I., Sirotkin, A.V., Tugaryov, D.: FIFO queueing policies for packets with heterogeneous processing. In: Even, G., Rawitz, D. (eds.) MedAlg 2012. LNCS, vol. 7659, pp. 248–260. Springer, Heidelberg (2012)
Kogan, K., López-Ortiz, A., Nikolenko, S., Sirotkin, A.: A taxonomy of semi-FIFO policies. In: IPCCC, pp. 295–304 (2012)
Kogan, K., Nikolenko, S., Keshav, S., López-Ortiz, A.: Efficient demand assignment in multi-connected microgrids with a shared central grid. In: SustainIT, pp. 1–5 (2013)
Mansour, Y., Patt-Shamir, B., Lapid, O.: Optimal smoothing schedules for real-time streams. Distributed Computing 17(1), 77–89 (2004)
Nikolenko, S.I., Kogan, K.: Single and multiple buffer processing. In: Encyclopedia of Algorithms. Springer (2015)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)
Yang, H.-C., Dasdan, A., Hsiao, R.-L., Parker Jr., D.S.: Map-reduce-merge: simplified relational data processing on large clusters. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 1029–1040 (2007)
Yu, Y., Gunda, P.K., Isard, M.: Distributed aggregation for data-parallel computing: interfaces and implementations. In: SOSP, pp. 247–260 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Eugster, P., Kesselman, A., Kogan, K., Nikolenko, S., Sirotkin, A. (2015). Essential Traffic Parameters for Shared Memory Switch Performance. In: Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2015. Lecture Notes in Computer Science(), vol 9439. Springer, Cham. https://doi.org/10.1007/978-3-319-25258-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-25258-2_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25257-5
Online ISBN: 978-3-319-25258-2
eBook Packages: Computer ScienceComputer Science (R0)