File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Systematic design of internet congestion control : theory and algorithms

TitleSystematic design of internet congestion control : theory and algorithms
Authors
Advisors
Advisor(s):Li, VOKLeung, KC
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Lai, C. [賴成迪]. (2014). Systematic design of internet congestion control : theory and algorithms. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312348
AbstractThe 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.
DegreeDoctor of Philosophy
SubjectInternet
Telecommunication - Traffic - Management
Dept/ProgramElectrical and Electronic Engineering
Persistent Identifierhttp://hdl.handle.net/10722/206356

 

DC FieldValueLanguage
dc.contributor.advisorLi, VOK-
dc.contributor.advisorLeung, KC-
dc.contributor.authorLai, Chengdi-
dc.contributor.author賴成迪-
dc.date.accessioned2014-10-23T23:14:29Z-
dc.date.available2014-10-23T23:14:29Z-
dc.date.issued2014-
dc.identifier.citationLai, C. [賴成迪]. (2014). Systematic design of internet congestion control : theory and algorithms. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312348-
dc.identifier.urihttp://hdl.handle.net/10722/206356-
dc.description.abstractThe 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.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshInternet-
dc.subject.lcshTelecommunication - Traffic - Management-
dc.titleSystematic design of internet congestion control : theory and algorithms-
dc.typePG_Thesis-
dc.identifier.hkulb5312348-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineElectrical and Electronic Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5312348-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats