Lecture 21 Optimal Routing Eytan Modiano Eytan Modiano Slide 1 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 (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 r w – P w is the set of paths between S and D – X p is the rate sent along path p∈ P w S.t. ∑ X p = r w , ?w ∈ W fij = ∑ X p p∈P w all pcontaining ( i, j ) Eytan Modiano Slide 3 Formulation continued ? Optimal routing problem can now be written as: Min D(F) S.t. ∑ X p = r w , ?w ∈W p∈P w ? ? ? Min ∑ D (i, j) ? ∑ X p ? s.t. ∑ X p = r w , ?w ∈ W ( i, j ) ? ? pcontains (i , j) ? ? p∈P w Eytan Modiano Slide 4 Optimal routing solution ? Let dD(*)/dx p be the partial derivative of D with respect to X p ? Then, ? D’ xp = dD(*)/dx p = Sum (i,j)∈p D’ (I,j) – Where D’ (i,j) is evaluated at the total flow corresponding to x p ? D’ xp consists of first derivative lengths along path p Eytan Modiano Slide 5 Optimal routing solution continued ? Suppose now that X* = {x* p } is an optimal flow vector for some S-D pair w with paths P W ? 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' ∈ P w ?x p' ?x p ?x p' ?x p ? Optimality conditions (necessary and sufficient): – optimal flows can only be positive on paths with minimum first derivative lengths – All paths along which r w is split must have same first derivative lengths Eytan Modiano Slide 6 Example Eytan Modiano Slide 7 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 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 Dij ~ 1/(μ?λ) (estimate delay through link) Update every 90 seconds Multi-path routing capability Eytan Modiano Slide 10 Link 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 with the packets destination address. The next node will look-up the address in the routing table ? Example: Open Shortest Path First (OSPF) commonly used in the internet ? Link State protocols typically generate less “control” traffic than Distance-vector Eytan Modiano Slide 11 Inter-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 through its network or two network providers may have an agreement Cost issues: Network providers may charge each other for dlivery of packets Eytan Modiano Slide 12 Bridges, 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 using network 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 13 Bridges, 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 14