MaP: Increasing node capacity of programmable cloud gateways

Virtual routing table lookup is a crucial operation in multi-tenant cloud gateways, the essential devices to enable the elastic management of Virtual Private Clouds (VPCs). However, software-based cloud gateways face performance bottlenecks when handling ever-increasing traffic. To address this challenge, a recent trend involves accelerating virtual routing table lookups using programmable switches, with Sailfish being the state-of-the-art solution. Nonetheless, Sailfish's table scale on a single programmable switch is limited by the ASIC memory sizes. We introduce a novel scheme, named MaP (Merge and Partition), to significantly increase the memory efficiency on a single Tofino 1.0 programmable switch. MaP exploits the similarities in routing table entries across various VPCs for table compression and leverages the hardware architecture of programmable chips to minimize the memory occupancy. Performance evaluations using real-world virtual routing tables demonstrate that our approach reduces the memory cost from 25% to 47.7% compared to Sailfish, without negatively impacting the throughput and latency. With MaP, a single programmable switch can manage a massive table containing over 2 million entries for nearly 1 million VPCs, while only occupying 59.0% of memory and 63.0% of stages.