■ Process of finding a path from a source to every destination in Process of finding a path from a source to every destination in
the network the network
■ Suppose you want to connect to Antarctica from your desktop Suppose you want to connect to Antarctica from your desktop
◆ what route should you take? what route should you take?
◆ does a shorter route exist? does a shorter route exist?
◆ what if a link along the route goes down? what if a link along the route goes down?
◆ what if you’re on a mobile wireless link? what if you’re on a mobile wireless link?
■ Routing deals with these types of issues Routing deals with these types of issues
Basics
■ A A routing protocol routing protocol sets up a sets up a routing table routing table in in routers routers and and switch switch
controllers controllers
■ A node makes a A node makes a local local choice depending on choice depending on global global topology: this topology: this
is the fundamental is the fundamental problem
Key problem
■ How to make correct local decisions? How to make correct local decisions?
◆ each router must know each router must know something something about global state
■ Global state Global state
◆ inherently large inherently large
◆ dynamic dynamic
◆ hard to collect hard to collect
■ A routing protocol must intelligently summarize relevant A routing protocol must intelligently summarize relevant
information information
Requirements
■ Minimize routing table space Minimize routing table space
◆ fast to look up fast to look up
◆ less to exchange less to exchange
■ Minimize number and frequency of control messages Minimize number and frequency of control messages
■ Robustness: avoid Robustness: avoid
◆ black holes black holes
◆ loops loops
◆ oscillations oscillations
■ Use optimal path Use optimal path
ads load, avoiding oscillations, but misorders stochastic spreads load, avoiding oscillations, but misorders
■ Single vs. multiple path Single vs. multiple path
◆ primary and alternative paths (compare with stochastic) primary and alternative paths (compare with stochastic)
■ State-dependent vs. state-independent State-dependent vs. state-independent
◆ do routes depend on current network state (e.g. delay) do routes depend on current network state (e.g. delay)
Outline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile hostsTelephone ne
Telephone network topology
■ 3-level hierarchy, with a fully-connected core 3-level hierarchy, with a fully-connected core
■ AT&T: 135 core switches with nearly 5 million circuits AT&T: 135 core switches with nearly 5 million circuits
■ LECs may connect to multiple cores LECs may connect to multiple cores
Routing algorithm
■ If endpoints are within same CO, directly connect If endpoints are within same CO, directly connect
■ If call is between COs in same LEC, use one-hop path between If call is between COs in same LEC, use one-hop path between
COs COs
■ Otherwise send call to one of the cores Otherwise send call to one of the cores
■ Only major decision is at toll switch Only major decision is at toll switch
◆ one-hop or two-hop path to the destination toll switch one-hop or two-hop path to the destination toll switch
◆ (why don’t we need longer paths?) (why don’t we need longer paths?)
■ Essence of problem
◆ which two-hop path to use if one-hop path is full which two-hop path to u
Features of telephone network routing
■ Stable load Stable load
◆ can predict pairwise load throughout the day can predict pairwise load throughout the day
◆ can choose optimal routes in advance can choose optimal routes in advance
■ Extremely reliable switches Extremely reliable switches
◆ downtime is less than a few minutes per year downtime is less than a few minutes per year
◆ can assume that a chosen route is available can assume that a chosen route is available
◆ can’t do this in the Internet can’t do this in the Internet
■ Single organization controls entire core Single organization controls entire core
◆ can collect global statistics and implement global changes can collect global statistics and implement global changes
■ Very highly connected network Very highly connected network
■ Connections require resources (but all need the same) Connections require resources (but all need the same)
The cost of simplicity
■ Simplicity of routing a historical necessity Simplicity of routing a historical necessity
■ But requires But requires
◆ reliability in every component reliability in every component
◆ logically fully-connected core logically fully-connected core
■ Can we build an alternative that has same features as the Can we build an alternative that has same features as the
telephone network, but is cheaper because it uses more telephone network, but is cheaper because it uses more
sophisticated routing? sophisticated routing?
◆ Yes: that is one of the motivations for ATM
◆ But 80% of the cost is in the local loop But 80% of the cost is in the local loop
✦ not affected by changes in core routing not affected by changes in core routing
◆ Moreover, many of the software systems assume topology Moreover, many of the software systems assume topology
✦ too expensive to change them
The cost of simplicity
■ Simplicity of routing a historical necessity Simplicity of routing a historical necessity
■ But requires But requires
◆ reliability in every component reliability in every component
◆ logically fully-connected core logically fully-connected core
■ Can we build an alternative that has same features as the Can we build an alternative that has same features as the
telephone network, but is cheaper because it uses more telephone network, but is cheaper because it uses more
sophisticated routing? sophisticated routing?
◆ Yes: that is one of the motivations for ATM
◆ But 80% of the cost is in the local loop But 80% of the cost is in the local loop
✦ not affected by changes in core routing not affected by changes in core routing
◆ Moreover, many of the software systems assume topology Moreover, many of the software systems assume topology
✦ too expensive to change them
Metastability
■ Burst of activity can cause network to enter metastable state Burst of activity can cause network to enter metastable state
◆ high blocking probability even with a low load high blocking probability even with a low load
■ Removed by trunk reservation Removed by trunk reservation
◆ prevents spilled traffic from taking over direct path
Trunk status map routing (TSMR)
■ DNHR measures traffic once a week DNHR measures traffic once a week
■ TSMR updates measurements once an hour or so TSMR updates measurements once an hour or so
◆ only if it changes “significantly” only if it changes “significantly”
■ List of alternative paths is more up to date List of alternative paths
Real-time network routing (RTNR)
■ No centralized control No centralized control
■ Each toll switch maintains a list of lightly loaded links Each toll switch maintains a list of lightly loaded links
■ Intersection of source and destination lists gives set of lightly Intersection of source and destination lists gives set of lightly
loaded paths loaded paths
■ Example Example
◆ At A, list is C, D, E => links AC, AD, AE lightly loaded At A, list is C, D, E => links AC, AD, AE lightly loaded
◆ At B, list is D, F, G => links BD, BF, BG lightly loaded At B, list is D, F, G => links BD, BF, BG lightly loaded
◆ A asks B for its list A asks B for its list
◆ Intersection = D => AD and BD lightly loaded => ADB lightly Intersection = D => AD and BD lightly loaded => ADB lightly
loaded => it is a good alternative path loaded => it is a good alternative path
■ Very effective in practice: only about a couple of calls blocked in Very effective in practice: only about a couple of calls blocked in
core out of about 250 million calls attempted every day core out of about 250 million calls attempted every day
Outline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile hosts
Distance vector routing
■ Environment Environment
◆ links and routers unreliable links and routers unreliable
◆ alternative paths scarce alternative paths scarce
◆ traffic patterns can change rapidly traffic patterns can change rapidly
■ Two key algorithms Two key algorithms
◆ distance vector distance vector
◆ link-state link-state
■ Both assume router knows Both assume router knows
◆ address of each neighbor address of each neighbor
◆ cost of reaching each neighbor cost of reaching each neighbor
■ Both allow a router to determine global routing information by Both allow a router to determine global routing information by
talking to its neighbors talking to its neighbors
Basic idea
■ Node tells its neighbors its best idea of distance to Node tells its neighbors its best idea of distance to every every other other
node in the network node in the network
■ Node receives these Node receives these distance vectors distance vectors from its neighbors from its neighbors
■ Updates its notion of best path to each destination, and the next Updates its notion of best path to each destination, and the next
hop for this destination hop for this destination
■ Features Features
◆ distributed distributed
◆ adapts to traffic changes and link failures adapts to traffic changes and link failures
◆ suitable for networks with multiple administrative entities
Why does it work
■ Each node knows its true cost to its neighbors Each node knows its true cost to its neighbors
■ This information is spread to its neighbors the first time it sends This information is spread to its neighbors the first time it sends
out its distance vector out its distance vector
■ Each subsequent dissemination spreads the truth one hop Each subsequent dissemination spreads the truth one hop
■ Eventually, it is incorporated into routing table everywhere in the Eventually, it is incorporated into routing table everywhere in the
network network
■ Proof: Bellman and Ford, 1957 Proof: Bellman and Ford, 1957
Dealing with the problem
■ Path vector Path vector
◆ DV carries path to reach each destination DV carries path to reach each destination
■ Split horizon Split horizon
◆ never tell neighbor cost to X if neighbor is next hop to X never tell neighbor cost to X if neighbor is next hop to X
◆ doesn’t work for 3-way count to infinity (see exercise) doesn’t work for 3-way count to infinity (see exercise)
■ Triggered updates Triggered updates
◆ exchange routes on change, instead of on timer exchange routes on change, instead of on timer
◆ faster count up to infinity faster count up to infinity
■ More complicated More complicated
◆ source tracing source tracing
◆ DUAL
Outline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile
Link state routing
■ In distance vector, router knows only In distance vector, router knows only cost cost to each destination to each destination
◆ hides information, causing problems hides information, causing problems
■ In link state, router knows entire network topology, and In link state, router knows entire network topology, and
computes shortest path by itself computes shortest path by itself
◆ independent computation of routes independent computation of routes
◆ potentially less robust potentially less robust
■ Key elements Key elements
◆ topology dissemination topology dissemination
◆ computing shortest routes computing shortest routesLink state: topology dissemination
■ A router describes its neighbors with a A router describes its neighbors with a link state packet (LSP) link state packet (LSP)
■ Use Use controlled flooding controlled flooding to distribute this everywhere to distribute this everywhere
◆ store an LSP in an store an LSP in an LSP database LSP database
◆ if new, forward to every interface other than incoming one if new, forward to every interface other than incoming one
◆ a network with E edges will copy at most 2E times a network with E edges will copy at most 2E timesSequence numbers
■ How do we know an LSP is new? How do we know an LSP is new?
■ Use a sequence number in LSP header Use a sequence number in LSP header
■ Greater sequence number is newer Greater sequence number is newer
■ What if sequence number wraps around? What if sequence number wraps around?
◆ smaller sequence number is now newer! smaller sequence number is now newer!
◆ (hint: use a large sequence space) (hint: use a large sequence space)
■ On boot up, what should be the initial sequence number? On boot up, what should be the initial sequence number?
◆ have to somehow purge old LSPs have to somehow purge old LSPs
◆ two solutions two solutions
✦ aging aging
✦ lollipop sequence space lollipop sequence spaceAging
■ Creator of LSP puts timeout value in the header Creator of LSP puts timeout value in the header
■ Router removes LSP when it times out Router removes LSP when it times out
◆ also floods this information to the rest of the network (why?) also floods this information to the rest of the network (why?)
■ So, on booting, router just has to wait for its old LSPs to be So, on booting, router just has to wait for its old LSPs to be
purged purged
■ But what age to choose? But what age to choose?
◆ if too small if too small
✦ purged before fully flooded (why?) purged before fully flooded (why?)
✦ needs frequent updates needs frequent updates
◆ if too large if too large
✦ router waits idle for a long time on rebooting router waits idle for a long time on rebootingA better solution
■ Need a Need a unique unique start sequence number start sequence number
■ a is older than b if: a is older than b if:
◆ a < 0 and a < b a < 0 and a < b
◆ a > o, a < b, and b-a < N/4 a > o, a < b, and b-a < N/4
◆ a > 0, b > 0, a > b, and a-b > N/4 a > 0, b > 0, a > b, and a-b > N/4More on lollipops
■ If a router gets an older LSP, it tells the sender about the newer If a router gets an older LSP, it tells the sender about the newer
LSP LSP
■ So, newly booted router quickly finds out its most recent So, newly booted router quickly finds out its most recent
sequence number sequence number
■ It jumps to one more than that It jumps to one more than that
■ -N/2 is a -N/2 is a trigger trigger to evoke a response from community memory
Recovering from a partition
■ On partition, LSP databases can get out of synch On partition, LSP databases can get out of synch
■ Databases described by database descriptor records Databases described by database descriptor records
■ Routers on each side of a newly restored link talk to each other Routers on each side of a newly restored link talk to each other
to update databases (determine missing and out-of-date LSPs) to update databases (determine missing and out-of-date LSPs)Router failure
■ How to detect? How to detect?
◆ HELLO protocol HELLO protocol
■ HELLO packet may be corrupted HELLO packet may be corrupted
◆ so age anyway so age anyway
◆ on a timeout, flood the information on a timeout, flood the informationSecuring LSP databases
■ LSP databases LSP databases must must be consistent to avoid routing loops be consistent to avoid routing loops
■ Malicious agent may inject spurious LSPs Malicious agent may inject spurious LSPs
■ Routers must actively protect their databases Routers must actively protect their databases
◆ checksum LSPs checksum LSPs
◆ ack LSP exchanges ack LSP exchanges
◆ passwords passwordsComputing shortest paths
■ Basic idea Basic idea
◆ maintain a set of nodes P to whom we know shortest path maintain a set of nodes P to whom we know shortest path
◆ consider every node one hop away from nodes in P = T consider every node one hop away from nodes in P = T
◆ find every way in which to reach a given node in T, and find every way in which to reach a given node in T, and
choose shortest one choose shortest one
◆ then add this node to P then add this node to PExampleLink state vs. distance vector
■ Criteria Criteria
◆ stability stability
◆ multiple routing metrics multiple routing metrics
◆ convergence time after a change convergence time after a change
◆ communication overhead communication overhead
◆ memory overhead memory overhead
■ Both are evenly matched Both are evenly matched
■ Both widely used Both widely usedOutline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile hostsChoosing link costs
■ Shortest path uses link costs Shortest path uses link costs
■ Can use either static of dynamic costs Can use either static of dynamic costs
■ In both cases: cost determine amount of traffic on the link In both cases: cost determine amount of traffic on the link
◆ lower the cost, more the expected traffic lower the cost, more the expected traffic
◆ if dynamic cost depends on load, can have oscillations if dynamic cost depends on load, can have oscillations
(why?) (why?)Static metrics
■ Simplest: set all link costs to 1 => min hop routing Simplest: set all link costs to 1 => min hop routing
◆ but 28.8 modem link is not the same as a T3! but 28.8 modem link is not the same as a T3!
■ Give links weight proportional to capacity Give links weight proportional to capacityDynamic metrics
■ A first cut (ARPAnet original) A first cut (ARPAnet original)
■ Cost proportional to length of router queue Cost proportional to length of router queue
◆ independent of link capacity independent of link capacity
■ Many problems when network is loaded Many problems when network is loaded
◆ queue length averaged over a small time => transient spikes queue length averaged over a small time => transient spikes
caused major rerouting caused major rerouting
◆ wide dynamic range => network completely ignored paths wide dynamic range => network completely ignored paths
with high costs with high costs
◆ queue length assumed to predict future loads => opposite is queue length assumed to predict future loads => opposite is
true (why?) true (why?)
◆ no restriction on successively reported costs => oscillations no restriction on successively reported costs => oscillations
◆ all tables computed simultaneously => low cost link flooded all tables computed simultaneously => low cost link floodedModified metrics
◆ queue length averaged over queue length averaged over
a small time a small time
◆ wide dynamic range queue wide dynamic range queue
◆ queue length assumed to queue length assumed to
predict future loads predict future loads
◆ no restriction on no restriction on
successively reported costs successively reported costs
◆ all tables computed all tables computed
simultaneously simultaneously
◆ queue length averaged over queue length averaged over
a longer time a longer time
◆ dynamic range restricted dynamic range restricted
◆ cost also depends on cost also depends on
intrinsic link capacity intrinsic link capacity
◆ restriction on successively restriction on successively
reported costs reported costs
◆ attempt to stagger table attempt to stagger table
computation computationRouting dynamicsOutline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile hostsHierarchical routing
■ Large networks need large routing tables Large networks need large routing tables
◆ more computation to find shortest paths more computation to find shortest paths
◆ more bandwidth wasted on exchanging DVs and LSPs more bandwidth wasted on exchanging DVs and LSPs
■ Solution: Solution:
◆ hierarchical routing hierarchical routing
■ Key idea Key idea
◆ divide network into a set of domains divide network into a set of domains
◆ gateways connect domains gateways connect domains
◆ computers within domain unaware of outside computers computers within domain unaware of outside computers
◆ gateways know only about other gateways gateways know only about other gatewaysExample
■ Features Features
◆ only a few routers in each level only a few routers in each level
◆ not a strict hierarchy not a strict hierarchy
◆ gateways participate in multiple routing protocols gateways participate in multiple routing protocols
◆ non-aggregable routers increase core table space non-aggregable routers increase core table spaceHierarchy in the Internet
■ Three-level hierarchy in addresses Three-level hierarchy in addresses
◆ network number network number
◆ subnet number subnet number
◆ host number host number
■ Core advertises routes only to networks, not to subnets Core advertises routes only to networks, not to subnets
◆ e.g. 135.104.*, 192.20.225.* e.g. 135.104.*, 192.20.225.*
■ Even so, about 80,000 networks in core routers (1996) Even so, about 80,000 networks in core routers (1996)
■ Gateways talk to backbone to find best next-hop to every other Gateways talk to backbone to find best next-hop to every other
network in the Internet
External and summary records
■ If a domain has multiple gateways If a domain has multiple gateways
◆ external external records tell hosts in a domain which one to pick to records tell hosts in a domain which one to pick to
reach a host in an external domain reach a host in an external domain
✦ e.g allows 6.4.0.0 to discover shortest path to 5.* is e.g allows 6.4.0.0 to discover shortest path to 5.* is
through 6.0.0.0 through 6.0.0.0
◆ summary summary records tell backbone which gateway to use to records tell backbone which gateway to use to
reach an internal node reach an internal node
✦ e.g. allows 5.0.0.0 to discover shortest path to 6.4.0.0 is e.g. allows 5.0.0.0 to discover shortest path to 6.4.0.0 is
through 6.0.0.0 through 6.0.0.0
■ External and summary records contain distance from gateway to External and summary records contain distance from gateway to
external or internal node external or internal node
◆ unifies distance vector and link state algorithms unifies distance vector and link state algorithmsInterior and exterior protocols
■ Internet has three levels of routing Internet has three levels of routing
◆ highest is at highest is at backbone backbone level, connecting level, connecting autonomous autonomous
systems (AS) systems (AS)
◆ next level is within AS next level is within AS
◆ lowest is within a LAN lowest is within a LAN
■ Protocol between AS gateways: exterior gateway protocol Protocol between AS gateways: exterior gateway protocol
■ Protocol within AS: interior gateway protocol Protocol within AS: interior gateway protocolExterior gateway protocol
■ Between untrusted routers Between untrusted routers
◆ mutually suspicious mutually suspicious
■ Must tell a Must tell a border gateway border gateway who can be trusted and what paths who can be trusted and what paths
are allowed are allowed
■ Transit Transit over over backdoors backdoors is a problemInterior protocols
■ Much easier to implement Much easier to implement
■ Typically partition an AS into Typically partition an AS into areas areas
■ Exterior and summary records used between areas Exterior and summary records used between areasIssues in interconnection
■ May use different schemes (DV vs. LS) May use different schemes (DV vs. LS)
■ Cost metrics may differ Cost metrics may differ
■ Need to: Need to:
◆ convert from one scheme to another (how?) convert from one scheme to another (how?)
◆ use the lowest common denominator for costs use the lowest common denominator for costs
◆ manually intervene if necessary manually intervene if necessaryOutline
■ Routing in telephone networks Routing in telephone networks
■ Distance-vector routing Distance-vector routing
■ Link-state routing Link-state routing
■ Choosing link costs Choosing link costs
■ Hierarchical routing Hierarchical routing
■ Internet routing protocols Internet routing protocols
■ Routing within a broadcast LAN Routing within a broadcast LAN
■ Multicast routing Multicast routing
■ Routing with policy constraints Routing with policy constraints
■ Routing for mobile hosts Routing for mobile hostsCommon routing protocols
■ Interior Interior
◆ RIP RIP
◆ OSPF OSPF
■ Exterior Exterior
◆ EGP EGP
◆ BGP BGP
■ ATM
◆ PNNI PNNIRIP
■ Distance vector Distance vector
■ Cost metric is hop count Cost metric is hop count
■ Infinity = 16 Infinity = 16
■ Exchange distance vectors every 30 s Exchange distance vectors every 30 s
■ Split horizon Split horizon
■ Useful for small subnets Useful for small subnets
◆ easy to install easy to installOSPF
■ Link-state Link-state
■ Uses areas to route packets hierarchically within AS Uses areas to route packets hierarchically within AS
■ Complex Complex
◆ LSP databases to be protected LSP databases to be protected
■ Uses Uses designated routers designated routers to reduce number of endpoints
