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