Algorithms and architecture designs for network addressing and routing scalability and router performance

This thesis addresses several issues in network scalability and router performance to sustain the rapid growth of the Internet.; In part I, we focus on network addressing and routing scalability, in particular, address allocation algorithms and alternative routing schemes to control and reduce routing table size. Our work on address allocation attempts to quantify the performance of allocation policies by modeling critical features that lead to fragmentation - a key problem in IPv4. We propose a growth-based scheme that allocates addresses taking into account potential user growth. Optimality of this scheme over existing practices is demonstrated through theoretical proof, simulations, and experiments on real data. To dramatically reduce routing table sizes and provide sub-linear scaling with network size, compact routing schemes have been proposed using landmark-based routing. The tradeoff is that the routing paths are no longer guaranteed to be the shortest. We further investigate the space-path tradeoff by analyzing a specific class of graphs and by presenting an efficient algorithm that (approximately) finds the optimum space-path tradeoff for any given network.; In part II of this thesis, a couple of problems are examined to improve router performance. The first one is buffer sizing - a key issue in router design that impacts queuing delay and network stability. A previously overlooked factor - fairness - is demonstrated to play a dominant role in determining buffer sizes. Our analysis suggests that there is an intrinsic trade-off between fairness in packet drops and desynchronization among TCP-Reno flows in routers using drop-tail queue management. By spreading packet drops over longer periods of time rather than only when the buffer is full, we show promise of achieving fairness, desynchronization, small buffer size, and 100% link utilization at the same time. The second result on router performance is a new device, called ElephantTrap, developed for routers to efficiently identify large flows. This device differs from previous ones in a way that it does not attempt to accurately estimate the size of the flows it is trapping. This leads to an extremely lightweight design and a surprisingly good performance. ElephantTrap can be used for diagnostics, anomaly detection and traffic engineering.