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