Communication Networks:Mathematical Techniques in NetworkingEECS 228aJean WalrandUniversity of CaliforniaBerkeley2Contentsn Overviewn Graph Theoryn Stochastic Modelsn Optimizationn Control Theoryn Game Theory3Overviewn Topics of courseq Not technology (hardware, protocols, products)q Mathematical techniquesn Why such a course?q Technology is easy to learn; many seminars/coursesq Techniques are usually deepq Course objective: panorama/guide to applied mathematicsn Level of presentationsq Intended for researchersq Focus on key ideas; illustrate with representative applicationsq Explain intuition behind methods and resultsq Sketch key argumentsq Indicate references for further reading4Overview (continued)n Course formatq For each topic: lectures + student presentationsq Course project: small research projectq Grading: presentations (65%) and project (35%)n Course Material (links on course web site)q Papers/Books q Slides of lecturesq Slides of student presentationsq Project reports5Overview (continued)n Quick look at techniques:q Graph Theoryq Stochastic Modelsq Optimizationq Control Theoryq Game Theory6Overview/Graph Theoryn Network as a graph:q Network = set of nodes connected by linksq Each link hasn capacity (e.g., 100Mbps) and propagation delayn reliabilityq Wireless links interferen Problems:q Routingn Shortest path; Path with sufficient capacityn Paths to achieve good long-term utilizationn Path with protectionn Multicast treesq Coloringn Scheduling transmissions that conflict (ad hoc network)n Assigning channels (cellular network, wi-fi, wi-max, ad-hoc)q Matching; Covering7Overview/Graph Theory - Examplesn Ad Hoc network: Scheduling2 nodes can transmit at a time à 40%Local constraints suggest 50%Gap between local (cliques) and globaln Wired network: Routing1 2345Conflict Graph12345672, 63, 112, 123, 84, 123, 7delaycostFind path from left to right with àDelay < 7àCost < 16-- Complexity of algorithm (P or NP)-- Good algorithms8Overview/Stochastic Modelsn Source/Channelq Entropy Rate/Shannon Capacity à See Information Theoryn Trafficq Variable rate: decay of correlation?n Queuingq Predicting backlog and delayq Scheduling: Stabilityn Networkq Random network: Connectivity; Small world effectsn Userq Activity model: depends on network capacity?n Web Siteq How are web sites organized?9Overview/Stochastic Models - Examplesn Sensor Networks: ConnectivityCan information propagate (infinitely) far?Percolation result: Yes (w.p.1) iff density is above critical valueTransmission rangeNoden Wired Networks: ConnectivityNumber of domains versus out-degree:“power law”10Overview/Stochastic Models - Examplesn Model of TCPq Key Ideas:n Sources adjust rate based on observed lossesn Losses depend on rate of sourceq Rate(Losses):n Instantaneous rate x(t): AIMDn Controlled by “Poisson Losses” (λ)n Analysis => E(x(t)) = R(λ)q Losses(Rate):n Router queue fed by arrivalsn Loss rate = increasing in queue lengthn Analysis => λ = L(R)11Overview/Optimizationn Routing: Path (lightpaths or flows) selectionsq On/Off line; Myopic or notn Network Designq Capacity Allocationn Power (Topology) Controln Techniques: Duality; LP; ILP12Overview/Optimization - Examplesn Routingq Ad hoc networkq Links interfereq Requests for flowsq Find paths to max.accepted flowsq Centralized/Off-line:ILPq On-line: Heuristic such asminimum interferenceq Note that greedy may notwork too well13Overview/Optimization - Examplesn NetworkProvisioningIPTCPResults: • For fixed c, there is optimum over R and x (may be unstable)• Optimum over c is hard … heuristics14Overview/Control TheoryProblem: • design marking scheme [q as function of y]• design rate adaptation scheme [x as function of q]so that• system is stable• flows are “fair”15Overview/Game Theoryn Routing; Flow Control; Pricingn Non-Cooperative: Users competen Cooperative: Agree to share profitsn Mechanism Design: Design game to promote good outcomen Price of Anarchy: Social cost of selfish behavior16Overview/Game Theory -Examplesn Flow ControlA BxC = 50 D Ey15, 1535, 1010, 3522, 22(x, y)AIncreases by 1Increases by 5D à Increases by 1 Increases by 5One shot: A has an incentive to “cheat”Long Term: Users have an incentive not to cheatToo aggressiveàLossesàThroughput falls17Overview/Game Theory -Examplesn Routingx11xActual CostSend rate 1 from S to D• Selfish (each packet chooses cheapest path): SABD è Total cost = 2• Centralized: 50% SAD, 50% SBD è Total cost = 1.5Cost of anarchy = 2/1.5 = 4/3 è Extends to linear costs and general topologyBraess Paradox: Remove link AB è Selfish becomes 1.5 (instead of 2)0SDAB18Overview/Game Theory -Examplesn Routing4562Actual CostMechanism:• Each link advertises its cost• Network computes a “price” per link• User choose least expensive pathIssue: Design prices so that• Incentive-compatible: Links advertise their true cost• Design scalable implementationSolution: • Price = reduction in cost of shortest path when link exists (VCG)• Implementation:
View Full Document
Unlocking...