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
Connected graph a graph is connected if a path exists between each pair of nodes Connected Unconnected An unconnected graph can be separated into two or more connected components
Connected graph • A graph is connected if a path exists between each pair of nodes. 1 2 4 3 1 2 3 Connected Unconnected • An unconnected graph can be separated into two or more connected components. Eytan Modiano Slide 6
Acyclic graphs and trees An acyclic graph is a graph with no cycles a tree is an acyclic connected graph 3 Acyclic, unconnected Cyclic, connected not tree not tree The number of arcs in a tree is always one less than the number of nodes Proof: start with arbitrary node and each time you add an arc you add a node >n nodes and N-1 links. If you add an arc without adding a node the arc must go to a node already in the tree and hence form a cycle
Acyclic graphs and trees • An acyclic graph is a g raph with no cycles. • A tree is an acyclic connected graph. 1 2 4 3 1 2 3 1 2 3 Acyclic, unconnected Cyclic, connec ted not tree not tree • The number of arcs in a tree is always one less than the number of nodes – Proof: start with arbitrary node and each time you add an arc you add a node => N nodes and N-1 links. If you add an arc without addin g a node, the arc must g o to a n o d e already in the tree and h e n ce form a cycle Eytan Modiano Slide 7
Subgraphs G=(N, A)is a subgraph ofG=(N, A)if 1)G is a graph 2)N is a subset of N 3)A is a subset of A One obtains a subgraph by deleting nodes and arcs from a graph Note: arcs adjacent to a deleted node must also be deleted Graph G Subgraph of G
Subgraphs • G' = (N',A') is a subgraph of G = (N,A) if – 1) G' is a graph – 2) N' is a subset of N – 3) A' is a subset of A • One obtains a subgraph by deleting nodes and arcs from a graph – Note: arcs adjacent to a deleted node must also be deleted 1 2 4 3 1 2 3 – Graph G Subgraph G' of G Eytan Modiano Slide 8
Spanning trees T=(N, A)is a spanning tree of G=(N, A)if T is a subgraph of G with N=N and T is a tree Graph G Spanning tree of G
Spanning trees • T = (N',A') is a spanning tree of G = (N,A) if – T is a subgraph of G with N' = N and T is a tree 1 2 4 3 5 1 2 4 3 5 Graph G Spanning tree of G Eytan Modiano Slide 9
Spanning trees Spanning trees are useful for disseminating and collecting control information in networks; they are sometimes useful for routing To disseminate data from node n Node n broadcasts data on all adjacent tree arcs Other nodes relay data on other adjacent tree arcs To collect data at node n. All leaves of tree(other than n)send data Other nodes (other than n) wait to receive data on all but one adjacent arc, and then send received plus local data on remaining arc
Spanning trees • Spanning trees are useful for disseminating and collecting control information in networks; they are sometimes useful for routing • To disseminate data from Node n: – Node n broadcasts data on all adjacent tree arcs – Other nodes relay data on other adjacent tree arcs • To collect data at node n: – All leaves of tree (other than n) send data – Other nodes (other than n) wait to receive data on all but one adjacent arc, and then send received plus local data on remaining arc Eytan Modiano Slide 10