But ■■■ how do routers know where to forward frames? * How do routers learn when the network topology changes? That' s what routing protocol does
But… How do routers know where to forward frames? How do routers learn when the network topology changes? That’s what routing protocol does…
Routing Goal: determine good"path sequence of routers through network from source to destination * good path” typically means minimum cost path other definitions also possible 2021/2/8
Routing Goal: determine “good” path (sequence of routers) through network from source to destination “good path” Typically means minimum cost path Other definitions also possible 2021/2/8 7
Dynamic Routing P traffic can be very bursty Dynamic adjustments in routing typicall operate more slowly than fluctuations in traffic load Dynamically adapting routing to account for traffic load can lead to wild unstable oscillations of routing system Usually, IP routing protocols do not dynamically route around network congestion 2021/2/8
Dynamic Routing IP traffic can be very bursty Dynamic adjustments in routing typically operate more slowly than fluctuations in traffic load Dynamically adapting routing to account for traffic load can lead to wild, unstable oscillations of routing system Usually, IP routing protocols do not dynamically route around network congestion. 2021/2/8 8
Graph Model Represent each router as node Direct link between routers represented by edge Symmetric links undirected graph Edge cost cx,y) denotes measure of difficulty of using link delay, s cost, or congestion level Task Determine least cost path from every node to every other node Path cost d(x, y)=sum of link costs 2021/2/8
Graph Model Represent each router as node Direct link between routers represented by edge Symmetric links undirected graph Edge “cost” c(x,y) denotes measure of difficulty of using link delay, $ cost, or congestion level Task Determine least cost path from every node to every other node Path cost d(x,y) = sum of link costs 2021/2/8 9
A Simple Model(Cont 6 D B 2021/2/8
A Simple Model (Cont.) 2021/2/8 10 A E F C D B 2 3 6 4 1 1 1 3