The Internet is dynamically shared by numerous flows of data traffic. Network congestion occurs when the aggregate flow rate persistently exceeds the network capacity, leading to excessive delivery delay and loss of user data. To control network congestion, a flow needs to adapt the sending rate to its inferred level of congestion, and a packet switch needs to report its local level of congestion. In this framework of Internet congestion control, it is important for flows to react promptly against congestion, and robustly against interfering network events resembling congestion. This is challenging due to the highly dynamic interactions of various network components over a global scale. Prior approaches rely predominantly on empirical observations in experiments for constructing and validating designs. However, without a careful, systematic examination of all viable options, more efficient designs may be overlooked. Moreover, experimental results have limited applicability to scenarios beyond the specific experimental settings. In this thesis, I employ a novel, systematic design approach. I formalize the design process of Internet congestion control from a minimal set of empirical observations. I prove the robustness and optimality of the attained design in general settings, and validate these properties in practical experimental settings. First, I develop a systematic method for enhancing the robustness of flows against interfering events resembling congestion. The class of additive-increase-multiplicative-decrease (AIMD) algorithms in Transmission Control Protocol (TCP) is the set of dominant algorithms governing the flow rate adaptation process. Over the present Internet, packet reordering and non-congestive loss occur frequently and are misinterpreted by TCP AIMD as packet loss due to congestion. This leads to underutilization of network resources. With a complete, formal characterization of the design space of TCP AIMD, I formulate designing wireless TCP AIMD as an optimal control problem over this space. The derived optimal algorithm attains a significant performance improvement over existing enhancements in packet-level simulation. Second, I propose a novel design principle, known as pricing-link-by-time (PLT), that specifies how to set the measure of congestion, or “link price”, at a router to provide prompt feedback to flows. Existing feedback mechanisms require sophisticated parameter tuning, and experience drastic performance degradation with improperly tuned parameters. PLT makes parameter tuning a simple, optional process. It increases the link price as the backlog stays above a threshold value, and resets the price once the backlog goes below the threshold. I prove that such a system exhibits cyclic behavior that is robust against changes in network environment and protocol parameters. Moreover, changing the threshold value can control delay without undermining system performance. I validate these analytical results using packet-level simulation. The incremental deployment of various enhancements have made Internet congestion control highly heterogeneous. The final part of the thesis studies this issue by analyzing the competition among flows with heterogeneous robustness against interfering network events. While rigorous theories have been a major vehicle for understanding system designs, the thesis involves them directly in the design process. This systematic design approach can fully exploit the structural characteristics, and lead to generally applicable, effective solutions. / published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Not available / text

Not available / text

Not available / text

Not available / text

Chen, Liang. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 164-175). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

Lau Kwok Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 66-67). / Abstracts in English and Chinese. / Acknowledgement --- p.1 / Abstract --- p.2 / 摘要 --- p.3 / Chapter Chapter 1 --- Introduction --- p.6 / Chapter Chapter 2 --- Background and Related Work --- p.9 / Chapter 2.1 --- Application-Layer Bandwidth Differentiation --- p.9 / Chapter 2.2 --- Related Work --- p.14 / Chapter 2.2.1 --- Bandwidth Differentation --- p.14 / Chapter 2.2.2 --- Shared Congestion Management --- p.15 / Chapter 2.2.3 --- Flow Partition --- p.16 / Chapter Chapter 3 --- VPS Protocol Architecture --- p.17 / Chapter 3.1 --- Virtual and Actual Flows --- p.18 / Chapter 3.2 --- VPS Controller --- p.21 / Chapter Chapter 4 --- ACK Translation --- p.25 / Chapter 4.1 --- Fast Retransmit and Fast Recovery --- p.27 / Chapter 4.2 --- Timeout --- p.30 / Chapter 4.3 --- Packet and ACK Reordering --- p.33 / Chapter 4.4 --- False Duplicate ACK Suppression --- p.35 / Chapter 4.5 --- Maxburst --- p.37 / Chapter 4.6 --- Memory Overhead and Computation Complexity --- p.38 / Chapter Chapter 5 --- Bandwidth Differentiation --- p.41 / Chapter 5.1 --- Distribution of Virtual Packets --- p.41 / Chapter 5.2 --- Temporary Suspension of Actual Flows --- p.43 / Chapter 5.3 --- Receive Window Limit --- p.44 / Chapter 5.4 --- Limited Data Transmission --- p.44 / Chapter Chapter 6 --- Performance Evaluatoin --- p.45 / Chapter 6.1 --- Performance Metric --- p.45 / Chapter 6.2 --- Simulation Setup --- p.46 / Chapter 6.3 --- Performance over Different Time Scales --- p.47 / Chapter 6.4 --- Performance over Different Bottleneck Bandwidth --- p.53 / Chapter 6.5 --- Performance over Different Application-specified Ratios --- p.54 / Chapter 6.6 --- Performance over Different Number of Flows --- p.57 / Chapter 6.7 --- Heterogeneous Receivers --- p.60 / Chapter Chapter 7 --- Conclusions and Future Work --- p.65 / Bibliography --- p.66

Ng Ping-chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 71-72). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview and Motivation --- p.1 / Chapter 1.2 --- Background of Offered Load Control --- p.2 / Chapter 1.3 --- Background of Stability Control --- p.3 / Chapter 1.4 --- Organization of the Thesis --- p.4 / Chapter Chapter 2 --- Performance Problems and Solutions --- p.6 / Chapter 2.1 --- Simulation Set-up --- p.6 / Chapter 2.2 --- High Packet-Drop Rate --- p.7 / Chapter 2.3 --- Re-routing Instability --- p.8 / Chapter 2.3.1 --- Hidden-Node Problem --- p.8 / Chapter 2.3.2 --- Ineffectiveness of Solving Hidden-Node Problem with RTS/CTS …… --- p.9 / Chapter 2.4 --- Solutions to High-Packet Loss Rate and Re-routing Instability --- p.10 / Chapter 2.4.1 --- Link-Failure Re-routing --- p.11 / Chapter 2.4.2 --- Controlling Offered Load --- p.13 / Chapter 2.5 --- Verification of Simulation Results with Real-life Experimental Measurements --- p.14 / Chapter Chapter 3 --- Offered Load Control --- p.16 / Chapter 3.1 --- Capacity Limited by the Hidden-node and Exposed-node Problems --- p.16 / Chapter 3.1.1 --- Signal Capture --- p.18 / Chapter 3.1.2 --- Analysis of Vulnerable Period induced by Hidden Nodes --- p.20 / Chapter 3.1.3 --- Analysis of Vulnerable Period induced by Exposed Nodes --- p.21 / Chapter 3.1.4 --- Sustainable Throughput --- p.22 / Chapter 3.2 --- Capacity Limited by Carrier Sensing Property --- p.23 / Chapter 3.3 --- Numerical Results --- p.26 / Chapter 3.4 --- General Throughput Analysis of a Single Multi-hop Traffic Flow --- p.29 / Chapter 3.5 --- Throughput Analysis on Topologies with Variable Distances between Successive Nodes --- p.31 / Chapter Chapter 4 --- Discussions of Other Special Cases --- p.33 / Chapter 4.1 --- A Carrier-sensing Limited Example --- p.33 / Chapter 4.2 --- A Practical Solution to Improve Throughput --- p.34 / Chapter Chapter 5 --- Achieving Fairness in Other Network Topologies --- p.36 / Chapter 5.1 --- Lattice Topology --- p.36 / Chapter Chapter 6 --- Stability Control --- p.39 / Chapter 6.1 --- Ad-hoc routing protocols --- p.39 / Chapter 6.2 --- Proposed scheme --- p.40 / Chapter 6.2.1 --- Original AODV --- p.41 / Chapter 6.2.2 --- AODV with Proposed Scheme --- p.42 / Chapter 6.2.2.1 --- A Single Flow in a Single Chain of Nodes --- p.43 / Chapter 6.2.2.2 --- Real-break Case --- p.44 / Chapter 6.3 --- Improvements --- p.45 / Chapter Chapter 7 --- Impacts of Data Transmission Rate and Payload Size --- p.48 / Chapter 7.1 --- Signal Capture --- p.48 / Chapter 7.2 --- Vulnerable region --- p.50 / Chapter Chapter 8 --- Performance Enhancements in Multiple Flows --- p.53 / Chapter 8.1 --- Impacts of Re-routing Instability in Two Flow Topology --- p.53 / Chapter 8.2 --- Impacts of Vulnerable Periods in Multiple Flow Topologies --- p.55 / Chapter 8.2.1 --- The Vulnerable Period induced by Individual Hidden-terminal Flow --- p.57 / Chapter 8.2.2 --- The Number of Hidden-terminal Flows --- p.58 / Chapter 8.2.3 --- Correlation between Hidden-terminal Flows --- p.60 / Chapter Chapter 9 --- Conclusion --- p.63 / Chapter Appendix A: --- General Throughput Analysis of a Single Multi-hop Traffic Flow --- p.67 / Chapter A.l --- Capacity Limited by Hidden-node and Exposed-Node --- p.67 / Chapter A.1.1 --- Sustainable Throughput --- p.68 / Chapter A.2 --- Capacity Limited by Carrier Sensing Property --- p.68 / Bibliography --- p.71

Our study on interdomain traffic engineering focuses on AS Path Prepending (ASPP), a popular way for inbound traffic engineering. In order to improve the current situation that ISPs often practise this approach in a trial-and-error basis, we propose a greedy algorithm to help ISPs perform this approach systematically and efficiently. Then we demonstrate two fundamental issues of decentralized selfish traffic engineering, routing instability and global network performance degradation, based on an abstract model where ISPs perform traffic engineering for their individual load balance. We also present a real-world pathologic case of prepending instability from our measurement study. Some simple guidelines are given for ISPs to avoid such routing instability. / Our work on peering strategy is to help ISPs understand the economic implications of various traffic patterns and make proper decisions to optimize their business. We first conduct an economic analysis for an overlay streaming network to gain some insights on the free ride phenomenon. We further improve the analysis by taking the response of subscribers into consideration and formulate the dynamic market as a multi-leader-follower game to capture the Nash Equilibrium of the routing tussle among the major players of the Internet marketplace. Based on this framework together with a gravity traffic model, we present some important observations on the implications of overlays on ISPs' peering strategy. / Over the past several years, numerous types of "overlay" networks change the interdomain traffic pattern and ISPs lose the routing control of some interdomain traffic flows due to the application layer routing. As a result, some ISPs may provide unintended transit service for other local ISPs. It upsets the traditional business model and makes ISPs' peering strategies more complicated. / The Internet has quickly evolved into a vast global network owned and operated by thousands of interconnected Internet Service Providers. Each of these ISPs, as one autonomous system, has its individual economic interests. ISPs can achieve their objectives through peering strategy and interdomain traffic engineering. These two issues are important for ISPs' business and have significant implications on the Internet architecture. / Wang, Hui. / "September 2007." / Adviser: Dah Ming Chiu. / Source: Dissertation Abstracts International, Volume: 69-08, Section: B, page: 4865. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 163-170). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Leung Ka Hing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 94-96). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Characterization and Performance Analysis --- p.8 / Chapter 2.1 --- Two-class Proportional Differentiated Service --- p.11 / Chapter 2.2 --- N-class Proportional DS --- p.13 / Chapter 3 --- Experiments of Proportional Delay Differentiation using the It- erative Algorithm --- p.20 / Chapter 3.1 --- Experiments using Poisson arrivals --- p.21 / Chapter 3.2 --- Experiments using other arrivals distributions --- p.33 / Chapter 4 --- Dynamic Adjustment --- p.37 / Chapter 4.1 --- Adjustment algorithms --- p.37 / Chapter 5 --- Experiments of Proportional Delay Differentiation using Dy- namic Adjustment --- p.41 / Chapter 5.1 --- Illustration of dynamic adjustment --- p.43 / Chapter 5.2 --- Poisson --- p.45 / Chapter 5.3 --- Pareto --- p.48 / Chapter 5.4 --- MMPP --- p.54 / Chapter 5.5 --- Heterogeneous traffic classes --- p.60 / Chapter 5.6 --- Experiments for short time-scale analysis --- p.62 / Chapter 6 --- Multiple nodes --- p.69 / Chapter 7 --- Summary of the Experiments Results --- p.75 / Chapter 8 --- Improvement of WTP --- p.78 / Chapter 8.1 --- Algorithm --- p.78 / Chapter 8.2 --- Experiments --- p.80 / Chapter 9 --- Possible Extensions --- p.85 / Chapter 9.1 --- Application Extension --- p.85 / Chapter 9.2 --- Performance Quantification --- p.87 / Chapter 10 --- Conclusion --- p.90