Lecture 20 Routing in data Networks Eytan Modiano
Lecture 20 Routing in Data Networks Eytan Modiano Eytan Modiano Slide 1
Routing Must choose routes for various origin destination pairs (o/d pairs) or for various sessions Datagram routing: route chosen on a packet by packet basis Using datagram routing is an easy way to split paths Virtual circuit routing: route chosen a session by session basis Static routing: route chosen in a prearranged way based on O/D pairs
Routing • Must choose routes for various origin destination pairs (O/D pairs) or for various sessions – Datagram routing: route chosen on a packet by packet basis Using datagram routing is an easy way to split paths – Virtual circuit routing: route chosen a session by session basis – Static routing: route chosen in a prearranged way based on O/D pairs Eytan Modiano Slide 2
Routing is a global problem 5 units 5 units 10 15 units Either session Both sessions alone is best must split their routed through traffic between center path, but OAll links two paths both cannot oAll links have go throug have capacity center capacity 10 units o 10 units Static routing is not desirable Datagam routing is a natural way to split the traffic How?
Routing is a global problem 5 units 5 units All links have capacity 10 units Either session alone is best routed through center path, but both cannot go through center. • Static routing is not desirable All links have capacity 10 units 10 units 15 units Both sessions must split their traffic between two paths. • Datagam routing is a natural way to split the traffic – How? Eytan Modiano Slide 3
Shortest Path routing Each link has a cost that reflects The length of the link Delay on the link Congestion ss cost Cost may change with time The length of the route is the sum of the costs along the route The shortest path is the path with minimum length Shortest Path algorithms Bellman-Ford: centralized and distributed versions Dijkstra’ s algorithm Many others
Shortest Path routing • Each link has a cost that reflects – The length of the link – Delay on the link – Congestion – $$ cost • Cost may change with time • The length of the route is the sum of the costs along the route • The shortest path is the path with minimum length • Shortest Path algorithms – Bellman-Ford: centralized and distributed versions – Dijkstra’s algorithm – Many others Eytan Modiano Slide 4
Directed graphs(digraphs) A directed graph(digraph)G=(N,A is a finite nonempty set of nodes N and a set of ordered node pairs a called directed arcs. N={1,2,34} A={(1,2),(2,1),(1,4) (4,2),(4,3),(3,2)} Directed walk:(4, 2, 1, 4, 3, 2) Directed path:(4, 2, 1) Directed cycle: (4, 2, 1, 4) Data networks are best represented with digraphs, although ty pically links tend to be bi-directional (cost may differ in each direction) For simplicity we will use bi-directional links of equal costs in our examples
Directed graphs (digraphs) • A directed graph (digraph) G = (N,A) is a finite nonempty set of nodes N and a set of ordered node pairs A called directed arcs. 1 2 3 4 N = {1,2,3,4} A = {(1,2), (2,1),(1,4), (4,2), (4,3),(3,2)} • Directed walk: (4,2,1,4,3,2) • Directed path: (4,2,1) • Directed cycle: (4,2,1,4) • Data networks are best represented with digraphs, although typically links tend to be bi-directional (cost may differ in each direction) – For simplicity we will u se bi-directional links of equ al costs in our examples Eytan Modiano Slide 5