Lorenzo De Carli
ABSTRACT
New protocols for the data link and network layer are being proposed to address limitations of current protocols in terms of scalability, security, and manageability. High-speed routers and switches that implement these protocols traditionally perform packet processing using ASICs which offer high speed, low chip area, and low power. But with inflexible custom hardware, the deployment of new protocols could happen only through equipment upgrades. While newer routers use more flexible network processors for data plane processing, due to power and area constraints lookups in forwarding tables are done with custom lookup modules. Thus most of the proposed protocols can only be deployed with equipment upgrades. To speed up the deployment of new protocols, we propose a flexible lookup module, PLUG (Pipelined Lookup Grid). We can achieve generality without loosing efficiency because various custom lookup modules have the same fundamental features we retain: area dominated by memories, simple processing, and strict access patterns defined by the data structure. We implemented IPv4, Ethernet, Ethane, and SEATTLE in our dataflow-based programming model for the PLUG and mapped them to the PLUG hardware which consists of a grid of tiles. Throughput, area, power, and latency of PLUGs are close to those of specialized lookup modules.
- M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In SIGCOMM, pages 63--74, Aug. 2008. Google Scholar
Digital Library
- D. G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker. Accountable internet protocol (AIP). In Proceedings of the ACM SIGCOMM, Aug. 2008. Google ScholarDigital Library
- Arvind and D. E. Culler. Dataflow Architectures. Annual Review of Computer Science, 1:225--253, 1986. Google ScholarDigital Library
- F. Baboescu, S. Singh, and G. Varghese. Packet classification for core routers: Is there an alternative to CAMs. In INFOCOM, Apr. 2003.Google ScholarCross Ref
- F. Baboescu, D. Tullsen, G. Rosu, and S. Singh. A tree based router search engine architecture with single port memories. In ISCA, June 2005. Google ScholarDigital Library
- F. Baboescu and G. Varghese. Scalable packet classification. In SIGCOMM, pages 199--210, Aug. 2001. Google ScholarDigital Library
- A. Basu and G. Narlikar. Fast incremental updates for pipelined forwarding engines. In INFOCOM, Apr. 2003.Google ScholarCross Ref
- M. Becchi and P. Crowley. An improved algorithm to accelerate regular expression evaluation. In ANCS, Dec. 2007. Google ScholarDigital Library
- M. Becchi and P. Crowley. Efficient regular expression evaluation: Theory to practice. In ANCS, December 2008. Google ScholarDigital Library
- N. Beheshti, Y. Ganjali, M. Ghobadi, N. McKeown, and G. Salmon. Experimental study of router buffer sizing. In Internet Measurement Conference, Oct. 2008. Google ScholarDigital Library
- F. Bonomi, M. Mitzenmacher, R. Panigraphy, S. Singh, and G. Varghese. Beyond Bloom filters: From approximate membership checks to approximate state machines. In SIGCOMM, Sept. 2006. Google ScholarDigital Library
- A. Broder and M. Mitzenmacher. Using multiple hash functions to improve IP lookups. In INFOCOM, pages 1454--1463, Apr. 2001.Google ScholarCross Ref
- L. D. Carli, Y. Pan, A. Kumar, C. Estan, and K. Sankaralingam. Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers. Technical Report TR1658, UW-Madison, Computer Science Department, May 2009.Google Scholar
- M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker. Ethane: taking control of the enterprise. In SIGCOMM, Aug. 2007. Google ScholarDigital Library
- M. Casado, T. Garfinkel, A. Akella, M. Freedman, D. Boneh, N. McKeown, and S. Shenker. SANE: A protection architecture for enterprise networks. In USENIX Security Symposium, Aug. 2006. Google ScholarDigital Library
- M. Casado, T. Koponen, D. Moon, and S. Shenker. Rethinking packet forwarding hardware. In HotNets-VII, Oct. 2008.Google Scholar
- F. Chung, R. Graham, and G. Varghese. Parallelism versus memory allocation in pipelined router forwarding engines. In SPAA, pages 103--111, June 2004. Google ScholarDigital Library
- Cisco Public Information. The cisco quantumflow processor: Cisco's next generation network processor. http://www.cisco.com/en/US/prod/collateral/routers/ps9343/solution_overview_c22-448936.html, 2008.Google Scholar
- D. Clark, J. Wroclawski, K. Sollins, and R. Braden. Tussle in cyberspace: Defining tomorrow's internet. In SIGCOMM, August 2002. Google ScholarDigital Library
- M. Degermark, A. Brodnik, S. Carlsson, and S. Pink. Small forwarding tables for fast routing lookups. In SIGCOMM, pages 3--14, Oct. 1997. Google ScholarDigital Library
- J. Dennis. A preliminary architecture for a basic data-flow processor. In ISCA '75, pages 126--132, January 1975. Google ScholarDigital Library
- W. Eatherton. The push of network processing to the top of the pyramid. Keynote Address at ANCS, Oct. 2005.Google Scholar
- P. Francis and R. Gummadi. IPNL: A NAT-extended internet architecture. In SIGCOMM, pages 69--80, Aug. 2001. Google ScholarDigital Library
- M. Gordon, W. Thies, M. Karczmarek, J. Lin, A. S. Meli, C. Leger, A. A. Lamb, J. Wong, H. Hoffman, D. Z. Maze, and S. Amarasinghe. A stream compiler for communication-exposed architectures. In ASPLOS 2002, San Jose, CA USA, Oct. 2002. Google ScholarDigital Library
- C. Guo, H. Wu, K. Tan, L. Shiy, Y. Zhang, and S. Luz. DCell: A scalable and fault-tolerant network structure for data centers. In SIGCOMM, pages 75--86, Aug. 2008. Google ScholarDigital Library
- P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Hot Interconnects VII, Aug. 1999.Google Scholar
- W. Jiang, Q. Wang, and V. K. Prasanna. Beyond TCAMs: An SRAM-based parallel multi-pipeline architecture for terabit IP lookup. In INFOCOM, Apr. 2008.Google ScholarCross Ref
- D. A. Joseph, A. Tavakoli, and I. Stoica. A policy-aware switching layer for data centers. In SIGCOMM, pages 51--62, Aug. 2008. Google ScholarDigital Library
- C. Kim, M. Caesar, and J. Rexford. Floodless in seattle: A scalable ethernet architecture for large enterprises. In SIGCOMM, pages 3--14, Aug. 2008. Google ScholarDigital Library
- E. Kohler, R. Morris, B. Chen, J. Jannotti, and F. Kaashoek. The Click modular router. ACM Trans. Comput. Syst., 18(3):263--297, Aug. 2000. Google ScholarDigital Library
- S. Kong, R. Smith, and C. Estan. Efficient signature matching with multiple alphabet compression tables. In SecureComm, Sept. 2008. Google ScholarDigital Library
- S. Kumar, M. Becchi, P. Crowley, and J. Turner. CAMP: fast and efficient IP lookup architecture. In ANCS, pages 51--60, Dec. 2006. Google ScholarDigital Library
- S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In SIGCOMM, Sept. 2006. Google ScholarDigital Library
- S. Kumar, J. Turner, and J. Williams. Advanced algorithms for fast and scalable deep packet inspection. In ANCS 2006, pages 81--92. Google ScholarDigital Library
- T. V. Lakshman and D. Stiliadis. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In SIGCOMM, pages 203--214, Sept. 1998. Google ScholarDigital Library
- E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235--1245, 1987.Google ScholarCross Ref
- K. Mai, T. Paaske, N. Jayasena, R. Ho, W. J. Dally, and M. Horowitz. Smart Memories: A modular reconfigurable architecture. In ISCA, pages 161--171, June 2000. Google ScholarDigital Library
- A. J. McAuley and P. Francis. Fast routing table lookup using CAMs. In INFOCOM, pages 1382--1391, Apr. 1993.Google ScholarCross Ref
- N. McKeown. The NetFPGA project. http://www.netfpga.org/.Google Scholar
- U. Saif, J. W. Anderson, A. Degangi, and A. Agarwal. Gigabit routing on a software-exposed tiled-microprocessor. In ANCS, pages 51--60, Oct. 2005. Google ScholarDigital Library
- K. Sankaralingam, R. Nagarajan, H. Liu, C. Kim, J. Huh, S. W. Keckler, D. Burger, and C. R. Moore. Exploiting ILP, TLP and DLP with the Polymorphous TRIPS Architecture. In ISCA '03, pages 422--433, June 2003. Google ScholarDigital Library
- D. Shah and P. Gupta. Fast updating algorithms for TCAMs. IEEE Micro, 21(1):36--47, Jan. 2001. Google ScholarDigital Library
- S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. In SIGCOMM, 2003. Google ScholarDigital Library
- I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana. Internet indirection infrastructure. In SIGCOMM, Aug. 2002. Google ScholarDigital Library
- S. Swanson, K. Michelson, A. Schwerin, and M. Oskin. Wavescalar. In MICRO '03, pages 291--302, December 2003. Google ScholarDigital Library
- M. B. Taylor, J. Kim, J. Miller, D. W. laff, F. Ghodrat, B. Greenwald, H. Hoffman, P. Johnson, W. L. Jae-Wook Lee, A. Ma, A. Saraf, M. Seneski, N. Shnidman, V. Strumpen, M. Frank, S. Amarasinghe, and A. Agarwal. The RAW Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs. IEEE Micro, 22(2):25--35, March 2002. Google ScholarDigital Library
- Xtensa lx2: The fastest processor core ever, http://www.tensilica.com/products/xtensa_lx.htm.Google Scholar
- S. Thoziyoor, N. Muralimanohar, and N. Jouppi. Cacti 5.0. Technical Report HPL-2007-167, HP Research Labs, 2007.Google Scholar
- B. Vöcking. How asymmetry helps load balancing. In IEEE-FOCS, pages 131--140, Oct. 1999. Google ScholarDigital Library
- H.-S. Wang, X. Zhu, L.-S. Peh, and S. Malik. Orion: a power-performance simulator for interconnection networks. In MICRO 35, pages 294--305, 2002. Google ScholarDigital Library
- A. Yaar, A. Perrig, and D. Song. SIFF: A stateless internet flow filter to mitigate DDoS flooding attacks. In Proceedings of the IEEE Symposium on Security and Privacy, May 2004.Google ScholarCross Ref
- X. Yang, D. Clark, and A. W. Berger. NIRA: a new inter-domain routing architecture. IEEE/ACM Transactions on Networking, 15(4):775--788, Aug. 2007. Google ScholarDigital Library
- X. Yang, D. Wetherall, and T. Anderson. A DoS-limiting network architecture. In SIGCOMM, Aug. 2005. Google ScholarDigital Library
- F. Zane, G. Narlikar, and A. Basu. CoolCAMs: Power-efficient TCAMs for forwarding engines. In INFOCOM, Apr. 2003.Google ScholarCross Ref
Index Terms
- PLUG: flexible lookup modules for rapid deployment of new protocols in high-speed routers
Recommendations
PLUG: flexible lookup modules for rapid deployment of new protocols in high-speed routers
SIGCOMM '09New protocols for the data link and network layer are being proposed to address limitations of current protocols in terms of scalability, security, and manageability. High-speed routers and switches that implement these protocols traditionally perform ...
Statistical Optimal Hash-based Longest Prefix Match
ANCS '17: Proceedings of the Symposium on Architectures for Networking and Communications SystemsLongest Prefix Match (LPM) is a basic and important function for current network devices. Hash-based approaches appear to be excellent candidate solutions for LPM with the capability of fast lookup speed and low latency. The number of hash table probes, ...
OpenFlow-based in-network Layer-2 adaptive multipath aggregation in data centers
In order to satisfy the high bandwidth and performance demands of applications, host servers are built with multiple network interfaces, and a data center network consists of multiple redundant links. It is important to make efficient use of all the ...
Comments