Optimizing and Modeling Dynamics in Networks Ibrahim Matta 1 Introduction The Internet has grown very large. No one knows exactly how large, but rough estimates indicate billions of users (around 1.8B in 2009, according to eTForecasts [4]), hundreds of millions of web sites (over 200M in February 2009, according to Netcraft [19]), and hundreds of billions of web pages (over 240B, according to the Internet archive [1]). The Internet is also very dynamic — users log in and out, new services get added, routing policies change, normal traffic gets mixed with denial-of-service (DoS) attack traffic, etc. An important question is: How do we manage such a huge and highly dynamic structure like the Internet? As a corollary, how can we build a network of the future unless we understand the steady-state and dynamics of what we build? In this chapter, we resort to two mathematical frameworks: optimization theory to study optimal steady states of networks, and control theory to study the dynamic behavior of networks as they evolve toward steady state.
Our emphasis will be on congestion control using the notion of prices to model the level of congestion, such as delays and losses, observed by users or traffic sources. Expected Background: We assume basic background in calculus and algebra. We also assume basic knowledge of systems modeling, optimization theory, Laplace transforms, and control theory — Keshav’s textbook [13] provides an excellent source for these mathematical foundations, in particular, chapters 4, 5, and 8. Basic knowledge of Internet’s Transmission Control Protocol (TCP) [11], namely Reno and Vegas [15] versions, as well as queue management schemes, namely Random Early Drop (RED) [6], should be helpful.
This chapter briefly covers needed background material to serve as a refresher or quick reference. The material of this chapter has been used at Boston University in a second (advanced) networking course taken by senior undergraduate and graduate students. Contribution and Outline: The purpose of this chapter is to make the application of optimization and control theory to congestion control more accessible through intuitive explanations and simple control ap- plications, using examples from Internet’s protocols. This chapter has been largely influenced by the work of Frank Kelly [12], which introduces the notion of “prices” and “user utility”, the work by R.
Srikant [24], which discusses the dynamics of user (traffic source) and network adaptations, and control theory texts and notes (e. The exposition here attempts to tie these various mathematical models and techniques through simple running examples and illustrations, modeling the dynamics of both flow control and routing. We start by motivating the network control problem using analogy to the problem of producing, pricing, and consuming gas/oil (Section 2). We introduce several examples of optimally allocating resources (link bandwidth) to users (traffic sources), resulting in different notions of fairness.
We then introduce dynamic equations that model source and link adaptation algorithms (Section 3). Since these are generally non-linear equations, we review the technique of linearization and how classical (linear) control theory can be used to I. Matta, “Optimizing and Modeling Dynamics in Networks”, in H.), Recent Advances in Networking, (2013), pp. Licensed under a CC-BY-SA Creative Commons license.
study stability and transient performance (Section 4). We use as a running example, a Vegas-like system controlled using different types of well-established controllers. Using linear approximation around a certain operating point, we can only study so-called local stability. To study general (global) stability of non-linear models, we introduce the control-theoretic Lyapunov method (Section 5).
We also show how the control-theoretic Nyquist stability method can be applied to the linearized model to study the impact of delay in feedback (i., measurements of the current state of the system). The material on the Nyquist method is a bit more advanced and can be skipped on a first reading. We generalize the notion of stability by introducing the concept of contractive mapping, and extend its application to routing dynamics (Section 6). Finally, we provide two case studies that apply control-theoretic techniques introduced in this chapter: the first study investigates stability under class-based scheduling of rate-adaptive traffic flows (Section 7), and the second study investigates stability of data transfer over a dynamic number of rate-adaptive transport connections (Section 8).
These case studies can be skipped on a first reading. The chapter concludes with a set of exercises (Section 9) and their solutions (Section 10). 2 Network Control as an Optimization Problem In this section, we describe Frank Kelly’s optimization framework [12], which models users’ expectations (requirements) with utility functions, and network congestion signals (e., loss, delay) as prices. The net- work is shown to allocate transmission rates (throughputs) to users (flows) in such a way as to meet some fairness objective.
The objective of a user, or what makes the user happy, can be mathematically modeled as a utility function. For example, drivers observe the“price” of transportation and make one of many possible decisions: drive, take the subway instead, walk, bike, or stay home. The decision may involve several factors like the price of gas, convenience, travel time, etc. For example, if it rains, you might decide to drive to work, or you might decide to walk to work to save money and can then afford to go to the movies later in the week.
Of course, how much driving a person does, is affected by all sorts of factors and user priorities are unknown to the system of gas stations and oil companies. But, each driver has her own utility! Figure 1 illustrates with a block diagram the closed-loop relationship between drivers (users), gas stations (where gas is sold to and consumed by users), and the market (which represents OPEC1 , the government, and oil companies that collectively produce gas and set market prices based on user demand). Drivers set the total demand by observing gas prices. Notice that the gas price includes at-the-pump gas price, and possibly other “exogenous” prices like tips for full service, fees for credit card payment, or additional local taxes.
Observe also that prices observed by users are delayed and do not typically represent the exact current state of the market given inherent delays in gas production, refinement, transportation, etc. This kind of block diagram is typical of many closed-loop (feedback) control systems where the system is said to reach equilibrium if the demand (for gas by drivers) matches the supply (of gas in the market). In data networks, users drive the demand on the network and have different utilities (expectations) when down- loading music, playing games, making skype (voice/video) calls, or denying others service by launching a denial-of-service (DoS) attack! In turn, the network observes that user demand and sets “prices”, where the price could be real money, or it could be some measure (indication) of congestion (e., delay, loss), or it could represent additional resources that need to be allocated to avoid congestion. An important question is: What is the goal of network design? Is it to make users happy? You hope so! Then, mathematically, we say the goal of the network is to maximize the sum of utilities for all its 1 OPEC is the Organization of the Petroleum Exporting Countries.
Figure 1: The gas control loop users [23].2 Figure 2 illustrates the data network equivalent of the gas control loop shown in Figure 1. We next consider the modeling of user utility and network behavior (resource allocation), before introducing the optimization framework to study the (optimal) steady state for the users and network. Figure 2: The network control loop 2.1 Modeling the User Users typically have different utilities, i. different applications may perform differently based on the level of service (e., loss, delay) they get from the network.
But, generally speaking, an application should perform better, the higher the rate (throughput) it is able to send at over the network. It is also generally the case that the gain (level of “happiness”) from higher throughput (i., marginal utility) diminishes as the throughput increases. Figure 3 shows such a utility function that is typical of what is called elastic traffic [23]. Formally, user r has utility Ur (xr ) when allocated rate xr > 0.
Ur (xr ) is an increasing, strictly concave function of xr 2 We note that maximizing the sum of utilities involves interpersonal utility comparison, which needs to be ameliorated by linking to a common good, such as money. And the derivative U̇r (xr ) → ∞ as xr → 0, and U̇r (xr ) → 0 as xr → ∞. Throughout this chapter we assume strictly concave utilities. Figure 3: Concave utility function Figure 4: Concave function.) is said to be concave if f (αx1 + (1 − α)x2 ) ≥ αf (x1 ) + (1 − α)f (x2 ), i., for any two points x1 and x2 , the straight line that connects f (x1 ) and f (x2 ) is always below or equal to the function f (.
Note that a differentiable concave function has a maximum value at some point xmax , and that the derivative f˙(xmax ) = 0. A strictly concave function would have a strict inequality, whereas a convex function has a cup-like shape and has a minimum instead.2 Modeling the Network We consider a network of J resources, e., transmission links as they are typically considered the bottleneck. We denote by R the set of all possible routes, and we assume that each user (source-destination traffic flow) is assigned to exactly one route r (i., static single-path routing)3. We then define a 0-1 routing matrix A such that: 1 if resource j is on route r ajr = 0 otherwise Figure 5 shows an example with three users over a network of seven links: the first user (“blue” flow) uses the route made of links 1, 4, and 6; the second user (“red” flow) uses the route made of links 2, 5, and 7; and the third user (“green” flow) uses the route made of links 1, 4, and 7.
So the routing matrix has seven rows and three columns. 3 Given each user has one flow over a single path, we use the terms “user”, “flow”, and “route” interchangeably. Figure 5: A network model 2.3 The Optimization Problem Now we are ready to formulate a (centralized) optimization problem that allows the network to allocate rates to users so that the sum of their utilities is maximized [12]. We refer to this problem as SY ST EM (U, A, C) where the inputs are the user utility functions Ur (.), the routing matrix A, and the (column) vector of link capacities C, and the output is the (column) vector of allocated rates x.
SY ST EM (U, A, C) : X max Ur (xr ) r∈R subject to Ax ≤ C over x ≥ 0 For such an optimization problem, it is known that there exists a unique solution. This is the case because the function to optimize is strictly concave and the link capacity inequality constraints Ax ≤ C form a so-called convex set (see Figure 6.) Figure 6: A convex set. A convex set intuitively means that any linear combination of any two points located on the boundary of the region, which is formed by the linear inequalities, lies within the region itself. The practical challenge in solving this problem however is that the network does not know the utilities of its users, let alone its centralized nature makes it computationally expensive to solve! To address these challenges, we start by decomposing the problem into R problems, one for each user r ∈ R, and one problem for the network (we will later decompose this network problem further into individual resource problems).
The network will present each user with a “price” λr ($/bit). Through these prices, the network attempts to infer user utilities.