Lecture 21 Optimal Routing Eytan Modiano Eytan Modiano Slide 1Optimal 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 isknown in advance – Traffic between source-destination pair can be split along multiplepaths with infinite precision • Find the paths (and associated traffic flows) along which to routeall of the traffic such that the total cost is minimized Eytan Modiano Slide 2Formulation 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 3Formulation continued • Optimal routing problem can now be written as: Min D(F) S.t. ∑ Xp = rw , ∀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 4Optimal 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 evaluated at the total flow corresponding to xp • D’xp consists of first derivative lengths along path p Eytan Modiano Slide 5Optimal routing solution continued • Suppose now that X* = {x*p} is an optimal flow vector for some S-D pair w with paths PW • Any shift in traffic from any path p to some other path p’ cannot possiblydecrease 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∂xp' ∂xp ∂xp' ∂xp • 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 Eytan Modiano Slide 6Example Eytan Modiano Slide 7Example, continued Eytan Modiano Slide 8Routing in the Internet • Autonomous systems (AS) – Internet is divided into AS’s each under the control of a singleauthority • 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 9Distance 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 Dij ~ 1/(µ−λ) (estimate delay through link) Update every 90 seconds Multi-path routing capability Eytan Modiano Slide 10Link State Protocols • Based on Dijkstra’s Shortest path algorithm – Avoids loops – Routers monitor the state of their outgoing links – Routers broadcast the state of their links within the AS – Every node knows the status of all links and can calculate all routes using dijkstra’s algorithm Nonetheless, nodes only send packet to the next node along the route withthe packets destination address. The next node will look-up the address inthe routing table • Example: Open Shortest Path First (OSPF) commonly used in theinternet • Link State protocols typically generate less “control” traffic thanDistance-vector Eytan Modiano Slide 11Inter-Domain routing • Used to route packets across different AS’s • Options: – Static routing - manually configured routes – Distance-vector routing Exterior Gateway Protocol (EGP) Border Gateway Protocol (BGP) • Issues – What cost “metric” to use for Distance-Vector routing Policy issues: Network provider A may not want B’s packets routed throughits network or two network providers may have an agreement Cost issues: Network providers may charge each other for dlivery of packets Eytan Modiano Slide 12Bridges, Routers and Gateways • A Bridge is used to connect multiple LAN segments – Layer 2 routing (Ethernet) – Does not know IP address – Varying levels of sophistication Simple bridges just forward packets smart bridges start looking like routers • A Router is used to route connect between different networks usingnetwork layer address – Within or between Autonomous Systems – Using same protocol (e.g., IP, ATM) • A Gateway connects between networks using different protocols – Protocol conversion – Address resolution • These definitions are often mixed and seem to evolve! Eytan Modiano Slide 13Bridges, routers and gateways Ethernet A Ethernet B Bridge IP Router Small company Gateway Service provider’s ATM backbone ATM switches (routers) Gateway Another provider’s Frame Relay Backbone Eytan Modiano Slide