Today, with emerging technology such as Wi-Fi, 4G, and 5G, more heterogeneous mobile devices, including low-power IoT devices, are connected to the Internet. Those billions of connected devices generate a large volume of data and require accessing network services with low latency, making us optimize memory-efficient algorithms for low-cost and scalable network services. Ideally, we expect network services are memory-efficiency and computation-efficiency to meet objectives of high throughput and low latency. However, existing methods and systems face the following challenges: 1) high memory and resource requirements, hard to be deployed on devices with limited resources, 2) processing data slowly to meet objectives. To address these challenges, we propose designing and utilizing space-efficient data structures to redesign various network devices. Specifically, we first design a new memory-efficient data structure called Vacuum filters. Then my thesis focuses on two types of widely-used network services.

The first type of service is security and privacy service for end devices. Mainly, we focus on two fundamental problems. 1) speeding up the certificate validation process, which is the basic and important step before a secure channel is built between end devices. 2) privacy protection when end devices communicate with remote cloud servers. We utilize an efficient data structure called Othello to develop the Collaborative Certificate Validation protocol (CCV), which provides a fast certificate validation for IoT devices. In addition, we design the LOIS framework based on Vacuum filters to protect users' privacy when end devices communicate with remote cloud servers.

The second type of service is the design of efficient network functions (NFs). NFs are essential services on the network support layer. They also rely on efficient data structures and algorithms to achieve memory and computation efficiency. We observed that multiple, co-existed NFs on the same device have become common in today's programmable networks. Thus, we design a tool called HyperMerger which can automatically generate resource-efficient consolidated algorithms to support co-existed NFs simultaneously for both hardware and software platforms.