Lecture 21 Optimal Routing Eytan Modiano
Lecture 21 Optimal Routing Eytan Modiano Eytan Modiano Slide 1
Optimal Routing View routing as a"globaloptimization problem Assumptions: The cost of using a link is a function of the flow on that link The total network cost is the sum of the link costs The required traffic rate between each source-destination pair is known in advance Traffic between source-destination pair can be split along multiple paths with infinite precision Find the paths(and associated traffic flows )along which to route all of the traffic such that the total cost is minimized
Optimal Routing • View routing as a “global” optimization problem • Assumptions: – The cost of using a link is a function of the flow on that link – The total network cost is the sum of the link costs – The required traffic rate between each source-destination pair is known in advance – Traffic between source-destination pair can be split along multiple paths with infinite precision • Find the paths (and associated traffic flows) along which to route all of the traffic such that the total cost is minimized Eytan Modiano Slide 2
Formulation of optimal routing Let Dij (fi be the cost function for using link (i,j) with flow fij Fij is the total traffic flow along link(i,j) Dijo can represent delay or queue size along the link Assume Difj is a differentiable function Let D(f)be the total cost for the network with flow vector F Assume additive cost: D(F)=Sum difj(fij) For S-d pair w with total rate r Pw is the set of paths between S and d Xp is the rate sent along path pE P psb=h,b∈W S1.)X l pcontaining(i,j)
Formulation of optimal routing • Let Dij (fij) be the cost function for using link (i,j) with flow fij – Fij is the total traffic flow along link (i,j) – Dij() can represent delay or queue size along the link – Assume Dij is a differentiable function • Let D(F) be the total cost for the network with flow vector F • Assume additive cost: D(F) = Sum(ij) Dij (fij) • For S-D pair w with total rate rw – Pw is the set of paths between S and D – Xp is the rate sent along path p ∈ Pw S.t. ∑ Xp = rw, ∀ w ∈ W fij = ∑ Xp p ∈Pw all pcontaining (i, j) Eytan Modiano Slide 3
Formulation continued Optimal routing problem can now be written as: MinD(FSt.Xn=rn,Vw∈W p∈P n2>∑x∑ X=rVw∈W pcontains(i,j) P
Formulation continued • Optimal routing problem can now be written as: Min D ( F) S.t. ∑ Xp = r w , ∀ w ∈ W p ∈ Pw ⇒ Min ∑ D(i, j) ∑ Xp s.t. ∑ Xp = rw , ∀ w ∈ W (i, j) pcontains(i , j) p ∈Pw Eytan Modiano Slide 4
Optimal routing solution Let dD()/dxp be the partial derivative of d with respect to Xp ·Then Drn dD()dx= Sum (epb(l】) Where D'(ii) is evaluated at the total flow corresponding to xp D'xo consists of first derivative lengths along path p
Optimal routing solution • Let dD(*)/dxp be the partial derivative of D with respect to Xp • Then, • D’xp = dD(*)/dxp = Sum(i,j) ∈p D’(I,j) – Where D’(i,j) is evaluat ed at the total flow corresponding to xp • D’xp consists of first derivative lengths along path p Eytan Modiano Slide 5
Optimal routing solution continued Suppose now that X*=ix* 3 is an optimal flow vector for some S-D pair w with paths P, decrease the total cost (since X* is assumed optima\ o' cannot possibly Any shift in traffic from any path p to some other pat Define A as the change in cost due to a shift of a small amount of traffic( 8) from some path p with xp>0 to another path p aD(X*)、ODX )aD(X*)、D(X 0→ Vp∈P Optimality conditions(necessary and sufficient optimal flows can only be positive on paths with minimum first derivative lengths All paths along which rw is split must have same first derivative lengths
Optimal routing solution continued • Suppose now that X* = {x* p } is an optimal flo w vector for some S-D pair w with paths PW • Any shift in traffic from any path p to some other path p’ cannot possibly decrease the total cost (since X* is assumed optimal) • Define ∆ as the change in cost due to a shift of a small amount of traffic ( δ) from some path p with x*p > 0 to another path p’ ∆ = δ ∂D ( X*) − δ ∂D ( X*) ≥ 0 ⇒ ∂D ( X*) ≥ ∂D ( X*), ∀ p' ∈ Pw ∂x p' ∂x p ∂xp' ∂xp • Optimality conditions ( necessary and sufficient): – optimal flows can only be positive on paths with minimum first d erivative lengths – All paths along which rw is split must have same first derivative lengths Eytan Modiano Slide 6
Example
Example Eytan Modiano Slide 7
Example, continued
Example, continued Eytan Modiano Slide 8
Routing in the Internet Autonomous systems(As) Internet is divided into as's each under the control of a single authority Routing protocol can be classified in two categories Interior protocols-operate within an As Exterior protocols-operate between AS's Interior protocols Typically use shortest path algorithms Distance vector- based on distributed bellman-ford link state protocols-Based on"distributed"Dijkstra's
Routing in the Internet • Autonomous systems (AS) – Internet is divided into AS’s each under the control of a single authority • Routing protocol can be classified in two categories – Interior protocols - operate within an AS – Exterior protocols - operate between AS’s • Interior protocols – Typically use shortest path algorithms Distance vector - based on distributed Bellman-ford link state protocols - Based on “distributed” Dijkstra’s Eytan Modiano Slide 9
Distance vector protocols Based on distributed Bellman-Ford Nodes exchange routing table information with their neighbors Examples Routing information protocols(RIP) Metric used is hop-count (dij=1 Routing information exchanged every 30 seconds Interior Gateway Routing Protocol (IGRP) CISCo proprietary Metric takes load into account Dif]-1/(u-m)(estimate delay through link) Update every 90 seconds Multi-path routing capability
Distance vector protocols • Based on distributed Bellman-Ford – Nodes exchange routing table information with their neighbors • Examples: – Routing information protocols (RIP) Metric used is hop-count (dij=1) Routing information exchanged every 30 seconds – Interior Gateway Routing Protocol (IG RP) CISCO proprietary Metric takes load into account Dij ~ 1/(µ−λ) (estimate delay through link) Update every 90 seconds M ulti-path r outing capability Eytan Modiano Slide 10