UC San Diego

Over the last three decades the Internet has evolved from a network of a dozen academics to one that spans the globe and is the primary medium of electronic communication. When the two most fundamental Internet protocols---IP and TCP---were designed, they were intended to address the problems of the day: addressing, routing, reliable delivery, and, eventually, congestion. This dissertation studies how these protocols may be augmented to adjust to today's reality and cope with the possibility of cheating- --the overuse of network resources---by network users. We study cheating in the Internet in two contexts. First, we examine strictly limiting the resources a user or entity can consume in the network. Second, we study self- interested, greedy users who want to consume as many resources as possible. The key challenge in both of these contexts is not primarily in designing cheat-proof mechanisms, but in doing so while avoiding unwanted network or architectural overhead. For the former, we develop the notion of Distributed Rate Limiting, which enables a network service provider to cap the aggregate bandwidth consumed by a user at different locations in the network. Distributed Rate Limiters operate at the network layer and aim to emulate the behavior of today's centralized limiters with low inter-limiter communication overhead. For the latter---for developing a transport layer that not only copes with the vicissitudes of network application traffic, but also with the desires and motivations of network users---we develop the notion of Decongestion Control, a congestion control paradigm in which users attempt to maximize their individual throughput in the course of normal operation. In networking canon, dropped packets >represent wasted resources, and thus traditional network congestion control protocols aim to avoid sending at a rate that induces packet loss. We study whether the benefits of a transport layer that embraces---rather than avoids---widespread packet loss and user self interest outweigh the potential loss in efficiency. For both of these systems, we identify numerous potential benefits to and applications for both the network provider and network user alike, and develop a framework in which such systems can subsequently be evaluated. For Distributed Rate Limiting we identify two important metrics---the inter-flow fairness and the rate that a limiter can deliver under shifting traffic patterns ---and evaluate how communication overhead impacts the algorithms we >present with respect to these metrics. For Decongestion Control, we similarly identify and examine the principal challenges---that the protocol must provide >performance not worse than TCP and that its widespread use must not cause congestion collapse.