Traffic Engineering and Time-varying Convex Optimization
Open Access
- Author:
- Su, Wenjing
- Graduate Program:
- Electrical Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- March 16, 2009
- Committee Members:
- Dr Lagoa, Dissertation Advisor/Co-Advisor
Constantino Manuel Lagoa, Committee Chair/Co-Chair
Tom Michael Cavalier, Committee Member
George Kesidis, Committee Member
Ji Woong Lee, Committee Member
Mario Sznaier, Committee Member - Keywords:
- traffic engineering
optimization
time-varying optimization - Abstract:
- Computer network traffic engineering aims at providing algorithms supporting Traffic Engineering (TE) for resource optimization (multi-path load balancing), Quality of Service (QoS), and Fast Failure Recovery (FFR) (dealing with link/node failures). This dissertation addresses two computer network traffic engineering problems: the multi-domain traffic engineering problem, and the overlay network traffic engineering problem. The solutions provided have their basis on nonlinear control theory. More precisely, they use concepts from sliding mode theory. The motivation for the study of the multi-domain traffic engineering problem comes from the increasing demand for the Internet to provide rich service quality features in support of sophisticated applications at a global scale, including TE, QoS, and FFR. We believe that, to be deployable at a global scale and to be integrated into the basic Internet architecture, a successful solution for a multi-domain environment must be distributed by design and in line with the distributed, two-level routing structure, and hop-by-hop forwarding paradigm of today’s Internet. In this dissertation, as a first but critical step toward finding such a solution, we develop a well-grounded theoretical underpinning for it. This family of control laws proposed for a multi-domain environment enables QoS-based TE and FFR features by performing per-hop edge-to-edge based traffic control at two levels (i.e., inter-domain and intra-domain), in alignment with the two-level routing structure and hop-by-hop forwarding paradigm of the Internet. Besides the multi-domain traffic engineering problem, we also address the overlay traffic engineering problem. Again, the approach used in the development of the control laws is based on the sliding mode theory. An overlay network, built at network application layer, is another prominent approach to provide QoS feature in the current best-effort Internet infrastructure. Given an overlay network, the goal of overlay network traffic engineering problems is to distribute traffic among available overlay paths in order to optimize the use of time-varying network resources. Due to the presence of time-varying network resources (link capacity), as well as the feasible set and the set of optimal solutions being time-varying, the problem is fundamentally a time-varying optimization problem and different from the problems previously addressed in the literature. And in this dissertation, we are able to find a new family of control laws, which addresses the time-varying problem. The family of control laws presented in this dissertation is shown to converge to the optimal (time-varying) traffic allocation and uses only the number of congested links in a forwarding path as feedback for the control, making it an ideal traffic control solution for the overlay network. Since the overlay network traffic engineering problem is a time-varying optimization problem, we also extend our research to more general time-varying optimization problems. For the problem with a twice differentiable strictly convex objective function, a Continuous First Order Algorithm (CFoA) is proposed. Moreover, in order to achieve “smoother” behavior than the CFoA, a Continuous Second Order Algorithm (CSoA) is also proposed. Both the CFoA and CSoA are shown to converge to and track the timevarying optimum. For a subclass of strictly convex objective functions having derivatives with “linear” discontinuity, a Sliding Algorithm (SA) is proposed, which is shown to converge to an arbitrarily small neighborhood of the time-varying optimum. Moreover, the SA is applied to solve time-varying linearly constrained optimization problems, and sufficient conditions for asymptotical convergence of the SA are provided.