Lecture 19 Broadcast routing Eytan Modiano
Lecture 19 Broadcast routing Eytan Modiano Eytan Modiano Slide 1
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
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 2
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} N=1234 A={(12),(2,3),(1,4),(2,4)} A={(1,2)
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 3
Walks and paths A walk is a sequence of nodes(n1, n2,. nk)in which each adjacent node paIr is an arc. a path is a walk with no repeated nodes 4 3 Wak(1,2,34,2) Path(12,34)
Walks and paths • A walk is a sequence of nodes (n1, n2, ...,nk) in which each adjacent node pair is an arc. • A path is a walk with no repeated nodes. 1 2 4 3 1 2 4 3 Walk (1,2,3,4,2) Path (1,2,3,4) Eytan Modiano Slide 4
Cycles A cycle is a walk(n1, n2,m, nk with n1 =nk, k>, and with no repeated nodes except n1 nk Cycle(1,24,3,1)
Cycles • A cycle is a walk (n1, n2,...,nk) with n1 = nk, k>3, and with no repeated nodes except n1 = nk Cycle (1,2,4,3,1) 1 2 4 3 Eytan Modiano Slide 5