2019/08/12 by Shu Yang, Laizhong Cui, Yang, Shu +13
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #FOS: Computer and information sciences #Network Packet Processing and Optimization #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.1908.04374
openalex publication_date 2019/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Higher dimensional classification has attracted more attentions with increasing demands for more flexible services in the Internet. In this paper, we present the design and implementation of a two dimensional router (TwoD router), that makes forwarding decisions based on both destination and source addresses. This TwoD router is also a key element in our current effort towards two dimensional IP routing. With one more dimension, the forwarding table will grow explosively given a straightforward implementation. As a result, it is impossible to fit the forwarding table to the current TCAM, which is the de facto standard despite its limited capacity. To solve the explosion problem, we propose a forwarding table structure with a novel separation of TCAM and SRAM. As such, we move the redundancies in expensive TCAM to cheaper SRAM, while the lookup speed is comparable with conventional routers. We also design the incremental update algorithms that minimize the number of accesses to memory. We evaluate our design with a real implementation on a commercial router, Bit-Engine 12004, with real data sets. Our design does not need new devices, which is favorable for adoption. The results also show that the performance of our TwoD router is promising.