Protocol design in an uncooperative internet
Stefan Savage, Thomas E. Anderson, Brian N. Bershad · 2002
In this dissertation, I examine the challenge of building network services in the absence of cooperative behavior. Unlike local-area networks, large scale administratively heterogeneous networks, such as the Internet, must accommodate a wide variety of competing interests, policies and goals. I explore the impact of this lack of cooperation on protocol design, demonstrate the problems that arise as a result, and describe solutions across a spectrum of uncooperative behaviors. In particular, I focus on three distinct, yet interrelated, problems—using a combination of experimentation, simulation and analysis to evaluate solutions. First, I examine the problem of obtaining unidirectional end-to-end network path measurements to uncooperative endpoints. I use analytic arguments to show that existing mechanisms for measuring packet loss are limited without explicit cooperation. I then demonstrate a novel packet loss measurement technique that sidesteps this requirement and provides implicit cooperation by leveraging the native interests of remote hosts. Based on this design, I provide the first experimental measurements of widespread packet loss asymmetry. Second, I study the problem of robust end-to-end congestion signaling in an environment with competitive interests. I demonstrate experimentally that existing congestion signaling protocols have flaws that allow misbehaving receivers to “steal” bandwidth from well-behaved clients. Following this I present the design of protocol modifications that eliminate these weaknesses and allow congestion signals to be explicitly verified and enforced. Last, I explore the problem of tracking network denial-of-service attacks in an environment where attackers explicitly conceal their true location. I develop a novel packet marking approach that allows victims to reconstruct the complete network path back to the victim. I evaluate several versions of this technique analytically and through simulation. Finally, I present a potential design for incorporating this mechanism into today's Internet in a backwards compatible manner.