Network Utility Maximization: Solving TCP Optimization Problems
TCP, in computer networks, solves an optimization problem related to max-min rate allocation. This lecture discusses the role of TCP in maximizing network utility and its impact on protocol design. With a focus on distributed algorithms, utility functions, and examples, the content explores the intricate details of network utility maximization for efficient data transmission.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
6.829 Computer Networks Lecture 6: Network Utility Maximization Mohammad Alizadeh Fall 2016 1
What Problem is TCP really solving? Max-min rate allocation? x1 = ? 1 Mb/s x2 = ? x3 = ? x1 1/3 x2 1/3 x3 1/3 Max- min TCP Assuming equal RTTs 2 1/3 1/3 1/3
What Problem is TCP really solving? Max-min rate allocation? 1 Mb/s 1 Mb/s x1 = ? x3 = ? x2 = ? x1 1/2 x2 1/2 x3 1/2 Max- min TCP 3 ~0.4 ~0.6 ~0.6
What Problem is TCP really solving? 1 Mb/s 1 Mb/s 1 Mb/s x1 = ? x3 = ? x2 = ? What is the difference between these links? 4
Network Utility Maximization TCP is solving an optimization problem! Spurred a lot of research on analyzing and designing network protocols from the lens of optimization > 5000 citations 6
Outline for Rest of Lecture Network Utility Maximization (NUM) Distributed Algorithm for NUM TCP s NUM Problem 7
Utility Function Good model for elastic flows e.g. file downloads The benefit derived from sending at rate x We ll assume U(.) is increasing & concave 8
Examples of Utility Functions log(x) x -1 x 9
Network Utility Maximization (NUM) c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 maximize log(x1) + log(x2) + log(x3) subject to: x1 + x2 1 x1 + x3 1 10
Network Utility Maximization (NUM) c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 maximize log(x1) + log(x2) + log(x3) x1 x2 x3 subject to: 1 1 1 1 0 1 0 1 11
NUM: General Case N N flows L links (xi) Ui maximize i=1 subject to: c1 c2 x1 x2 0 1 0 1 1 1 0 1 0 0 RLxN routing matrix 0 0 1 1 0 cL xN 12
NUM Example 1: Throughput Maximization c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 maximize x1 + x2 + x3 x1 = 0 Mb/s x2 = 1 Mb/s x3 = 1 Mb/s subject to: x1 + x2 1 x1 + x3 1 13
NUM Example 2: Proportional Fairness c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 maximize log(x1) + log(x2) + log(x3) x1 = 1/3 Mb/s x2 = 2/3 Mb/s x3 = 2/3 Mb/s subject to: x1 + x2 1 x1 + x3 1 14
NUM Example 3: -fairness c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 1-a 3 xi 1-a 0 (a constant) maximize alpha = 0 = 1 Objective i=1 Thrput Maximization Proportional Fairness subject to: x1 + x2 1 x1 + x3 1 Max-min Fairness 15
Outline The Network Utility Maximization (NUM) Problem Distributed Algorithm for NUM TCP s NUM Problem 16
Proportional Fairness Example c1 = 1 Mb/s c2 = 1 Mb/s x1 x3 x2 maximize log(x1) + log(x2) + log(x3) subject to: x1 + x2 1 x1 + x3 1 17
Distributed Algorithm c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 pl= congestion price for link l price per unit of bandwidth (pl 0) qi = total price for source i Sum of prices on source i s path 18
The Source Problem c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 Pick rate xi to maximize utility: log(xi) qi xi xi = 1/qi benefit cost This is done independently at each source. 19
The Network Problem c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 Adapt link prices periodically based on congestion pl(t+1) = [ pl(t) + (yl(t) cl) ]+ total traffic at link l [.]+ = max(., 0) 20
The Network Problem c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 Adapt link prices periodically based on congestion pl(t+1) = [ pl(t) + (yl(t) cl) ]+ This is done independently at each link. 21
Putting it All Together c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 Sources x1(t) = 1 / (p1(t) + p2(t)) x2(t) = 1 / p1(t) x3(t) = 1 / p2(t) Links p1(t+1) = [p1(t) + (y1(t) c1)]+ p2(t+1) = [p2(t) + (y2(t) c2)]+ 22
Example 23
Outline The Network Utility Maximization (NUM) Problem NUM Distributed Algorithm TCP s NUM Problem 24
TCP + PI c1 = 1 Mb/s c2 = 1 Mb/s x1 p2 p1 x3 x2 Sources x1(t) = 1 / RTT1 Links p1(t)+ p2(t) p1(t) p2(t) p1(t+1) = [p1(t) + (y1(t) c1)]+ p2(t+1) = [p2(t) + (y2(t) c2)]+ x2(t) = 1 / RTT2 x3(t) = 1 / RTT3 25
What is TCPs Utility Function? 26
