Lectures 21: Routing in Data Networks Eytan Modiano Eytan Modiano
Lectures 21: Routing in Data Networks Eytan Modiano Eytan Modiano Slide 1
Packet Switched Networks Messages broken into Packets that are routed To their destination Packet Network Buffer Packet Switch Eytan Modiano
Packet Switched Networks Packet Network PS PS PS PS PS PS PS Buffer Packet Switch Messages broken into Packets that are routed To their destination Eytan Modiano Slide 2
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
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 3
Broadcast Routing Route a packet from a source to all nodes in the network Possible solutions Flooding: Each node sends packet on all outgoing links Discard packets received a second time Spanning Tree Routing: Send packet along a tree that includes all of the nodes in the network Eytan Modiano
Broadcast Routing • Route a packet from a source to all nodes in the network • Possible solutions: – Flooding: Each node sends packet on all outgoing links Discard packets received a second time – Spanning Tree Routing: Send packet along a tree that includes all of the nodes in the network Eytan Modiano Slide 4
Graphs A graphG=(N, A) is a finite nonempty set of nodes and a set of node pairs a called arcs or links or edges) N={123} N={1,2,3,4 A={12),(2,3),(1,4,(24)} A={(1,2) Eytan Modiano
Graphs • A graph G = (N,A) is a finite nonempty set of nodes and a set of node pairs A called arcs (or links or edges) 1 2 3 1 2 3 4 N = {1,2,3} N = {1,2,3,4} A = {(1,2),(2,3),(1,4),(2,4)} A = {(1,2)} Eytan Modiano Slide 5