Skip to main content
eScholarship
Open Access Publications from the University of California

UC Santa Cruz

UC Santa Cruz Electronic Theses and Dissertations bannerUC Santa Cruz

Algorithmic and System Innovations for Network Data Plane: Efficiency, Scalability, and Flexibility

Abstract

Due to the advanced reliability, scalability, and cost-effectiveness, more and more businesses are turning to cloud computing, and large-scale cloud networks have been connecting users, data, and machines more tightly than any past time. According to Forbes, the cloud computing is enjoying a more than 15 percent of growth per year in the global market size. And, Flexera reports that more than half of the investigated companies, being enterprise or small businesses, are using more cloud services than they expect, due to the impact of COVID-19. Among the investigated companies, the top concern in cloud computing is cost effectiveness. However, Moore’s law fails in recent years because the cost for a single gate of an integrated circuit is not decreasing anymore. Hence, architectural reorganizations and algorithmic innovations are two main approaches to achieve higher effectiveness in the post Moore's law era.

To support massive network traffics from numerous end devices, most cloud networks require high capacity Forwarding Information Bases (FIBs). The growth of the FIB limits the performance of network operations and increases infrastructure cost. We propose to reorganize the functions of the standard SDN model, and extract the common update calculations from the data plane to the control plane [ICNP’19]. We call this `skeleton-based update'.

Based on the reorganized skeleton-based update model for SDN, this dissertation presents a new algorithm, Ludo hashing [ACM SIGMETRICS’20] for fast key-value lookup. Ludo achieves the most compact memory cost among all alternative algorithms by saving 40% to 80%+ space compared to existing dynamic solutions. Ludo hashing is specially designed for cloud computing and distributed systems, and is ready to be applied to many applications, e.g., network forwarders, Content distribution network (CDN), cloud load balancers, Network Address Translation (NAT), and data sharing or collaboration tasks for IoT devices. We then designed Concury [SOCC'20], a fast and light-weight software load balancer for cloud networks. Concury improves the throughput by >2x and costs the smallest memory compared to state-of-the-art L4LB algorithms, while providing weighted load balancing. Concury is read only during connection establishments and terminations, while the connection consistency is still guaranteed by design.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View