James McCauley
Mingjie Zhao
Sylvia Ratnasamy
Scott Shenker
ABSTRACT
A major staple of layer 2 has long been the combination of flood-and-learn Ethernet switches with some variant of the Spanning Tree Protocol. However, STP has significant shortcomings -- chiefly, that it throws away network capacity by removing links, and that it can be relatively slow to reconverge after topology changes. In recent years, attempts to rectify these shortcomings have been made by either making L2 look more like L3 (notably TRILL and SPB, which both incorporate L3-like routing) or by replacing L2 switches with "L3 switching" hardware and extending IP all the way to the host. In this paper, we examine an alternate point in the L2 design space, which is simple (in that it is a single data plane mechanism with no separate control plane), converges quickly, delivers packets during convergence, utilizes all available links, and can be extended to support both equal-cost multipath and efficient multicast.
- 1.Al-Fares, M., Loukissas, A., and Vahdat, A. A Scalable, Commodity Data Center Network Architecture. In Proc. of SIGCOMM (2008). Google Scholar
Digital Library
- 2.Al-Fares, M., Radhakrishnan, S., Raghavan, B., Huang, N., and Vahdat, A. Hedera: Dynamic Flow Scheduling for Data Center Networks. In Proc. of NSDI (2010). Google ScholarDigital Library
- 3.Benson, T., Akella, A., and Maltz, D. Network Traffic Characteristics of Data Centers in the Wild. In Proc. of ACM Internet Measurement Conference (IMC) (2012). Google ScholarDigital Library
- 4.P4 Behavioral Model. https://github.com/p4lang/behavioral-model.Google Scholar
- 5.Bosshart, P., Gibb, G., Kim, H.-S., Varghese, G., McKeown, N., Izzard, M., Mujica, F., and Horowitz, M. Forwarding Metamorphosis: Fast Programmable Match-Action Processing in Hardware for SDN. In Proc. of SIGCOMM (2013). Google ScholarDigital Library
- 6.Christensen, M., Kimball, K., and Solensky, F. Considerations for Internet Group Management Protocol (IGMP) and Multicast Listener Discovery (MLD) Snooping Switches. RFC 4541 (Informational), 2006.Google Scholar
- 7.Datasheet, Texas Instruments. DP83867IR/CR Robust, High Immunity 10/100/1000 Ethernet Physical Layer Transceiver. http://www.ti.com/lit/ds/symlink/dp83867ir.pdf, 2015.Google Scholar
- 8.Di Caro, G. A., and Dorigo, M. Two Ant Colony Algorithms for Best-Effort Routing in Datagram Networks. In Proc. of the IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS) (1998).Google Scholar
- 9.Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel, P., and Sengupta, S. VL2: A Scalable and Flexible Data Center Network. In Proc. of SIGCOMM (2009). Google ScholarDigital Library
- 10.He, K., Khalid, J., Gember-Jacobson, A., Das, S., Prakash, C., Akella, A., Li, L. E., and Thottan, M. Measuring Control Plane Latency in SDN-enabled Switches. In Proc. of the ACM SIGCOMM Symposium on Software Defined Networking Research (SOSR) (2015). Google ScholarDigital Library
- 11.IEEE Standards Association. 802.1ag-2007 - IEEE Standard for Local and Metropolitan Area Networks Virtual Bridged Local Area Networks Amendment 5: Connectivity Fault Management. http://standards.ieee.org/findstds/standard/802.1ag-2007.html.Google Scholar
- 12.IEEE Standards Association. 802.1aq-2012 - IEEE Standard for Local and metropolitan area networks–Media Access Control (MAC) Bridges and Virtual Bridged Local Area Networks–Amendment 20: Shortest Path Bridging. https://standards.ieee.org/findstds/standard/802.1aq-2012.html.Google Scholar
- 13.IEEE Standards Association. 802.1D-2004 - IEEE Standard for Local and metropolitan area networks: Media Access Control (MAC) Bridges. http://standards.ieee.org/findstds/standard/802.1D-2004.html.Google Scholar
- 14.IEEE Standards Association. 802.1Q-2014 - IEEE Standard for Local and metropolitan area networks–Bridges and Bridged Networks. http://standards.ieee.org/findstds/standard/802.1Q-2014.html.Google Scholar
- 15.IEEE Standards Association. 802.1s-2002 - IEEE Standards for Local and Metropolitan Area Networks - Amendment to 802.1Q Virtual Bridged Local Area Networks: Multiple Spanning Trees. http://standards.ieee.org/findstds/standard/802.1s-2002.html.Google Scholar
- 16.IEEE Standards Association. 802.2-1989 - IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 2: Logical Link Control. http://standards.ieee.org/findstds/standard/802.2-1989.html.Google Scholar
- 17.Johnson, D. B. Routing in Ad Hoc Networks of Mobile Hosts. In Proc. of Workshop on Mobile Computing Systems and Applications (WMCSA) (1994). Google ScholarDigital Library
- 18.Jose, L., Yan, L., Varghese, G., and McKeown, N. Compiling Packet Programs to Reconfigurable Switches. In Proc. of NSDI (2015). Google ScholarDigital Library
- 19.Katz, D., and Ward, D. Bidirectional Forwarding Detection (BFD). RFC 5880 (Proposed Standard), 2010.Google Scholar
- 20.Kempf, M. Bridge Circuit for Interconnecting Networks, 1986. US Patent 4,597,078.Google Scholar
- 21.Lakshminarayanan, K., Caesar, M., Rangan, M., Anderson, T., Shenker, S., and Stoica, I. Achieving Convergence-free Routing Using Failure-carrying Packets. In Proc. of SIGCOMM (2007). Google ScholarDigital Library
- 22.Liu, J., Panda, A., Singla, A., Godfrey, B., Schapira, M., and Shenker, S. Ensuring Connectivity via Data Plane Mechanisms. In Proc. of NSDI (2013). Google ScholarDigital Library
- 23.Liu, V., Halperin, D., Krishnamurthy, A., and Anderson, T. F10: A Fault-Tolerant Engineered Network. In Proc. of NSDI (2013). Google ScholarDigital Library
- 24.Markopoulou, A., Iannaccone, G., Bhattacharyya, S., Chuah, C.-N., and Diot, C. Characterization of Failures in an IP Backbone. In Proc. of INFOCOM (2004).Google ScholarCross Ref
- 25.McCauley, J., Sheng, A., Jackson, E. J., Raghavan, B., Ratnasamy, S., and Shenker, S. Taking an AXE to L2 Spanning Trees. In Proc. of HotNets (2015). Google ScholarDigital Library
- 26.McKeown, N., Anderson, T., Balakrishnan, H., Parulkar, G., Peterson, L., Rexford, J., Shenker, S., and Turner, J. OpenFlow: Enabling Innovation in Campus Networks. CCR 38, 2 (2008). Google ScholarDigital Library
- 27.Mininet. http://mininet.org/.Google Scholar
- 28.ns-3. http://www.nsnam.org/.Google Scholar
- 29.Perlman, R. An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN. In Proc. of SIGCOMM (1985). Google ScholarDigital Library
- 30.Perlman, R., Eastlake, D., Dutt, D., Gai, S., and Ghanwani, A. Routing Bridges (RBridges): Base Protocol Specification. RFC 6325 (Proposed Standard), 2011.Google Scholar
- 31.Singh, A., Ong, J., Agarwal, A., Anderson, G., Armistead, A., Bannon, R., Boving, S., Desai, G., Felderman, B., Germano, P., et al. Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google's Datacenter Network. In Proc. of SIGCOMM (2015). Google ScholarDigital Library
- 32.Waitzman, D., Partridge, C., and Deering, S. Distance Vector Multicast Routing Protocol. RFC 1075 (Experimental), 1988. Google ScholarDigital Library
Index Terms
- The Deforestation of L2
Recommendations
Taking an AXE to L2 Spanning Trees
HotNets-XIV: Proceedings of the 14th ACM Workshop on Hot Topics in NetworksI think that I shall never see
a structure more wasteful than a tree.
Most links remain idle and unused
while others are overloaded and abused.
And with each failure comes disruption
caused by the ensuing tree construction.
Thus, L2 must discard its ...
Reusability-aware cache memory sharing for chip multiprocessors with private L2 caches
In this paper, we propose a novel on-chip L2 cache organization for chip multiprocessors (CMPs) with private L2 caches. The proposed approach, called reusability-aware cache sharing (RACS), combines the advantages of both a private L2 cache and a shared ...
Comments