MIST Multicast Implementation Study.ppt.ppt

Broadcast Routing Broadcasting: sending a packet to all N receivers routing updates in LS routing service/request advertisement in application layer (e.g., Novell) Broadcast algorithm 1: N point-to-point sends send packet to every destination, point-to-point wasteful of bandwidth requires knowledge of all destinations Broadcast algorithm 2: flooding when node receives a broadcast packet, send it out on every link node may receive many copies of broadcast packet, hence must be able to detect duplicates Broadcast Routing: Reverse Path Forwarding Goal: avoid flooding duplicates Assumptions: A wants to broadcast all nodes know predecessor node on shortest path back to A Reverse path forwarding: if node receives a broadcast packet if packet arrived on predecessor on shortest path to A, then flood to all neighbors otherwise ignore broadcast packet - either already arrived, or will arrive from predecessor Reverse Path Forwarding flood if packet arrives from source on link that router would use to send packets to source otherwise discard rule avoids flooding loops uses shortest path tree from destinations to source (reverse tree) Distributing routing information Q: is broadcast algorithm like reverse path forwarding good for distributing Link State updates (in LS routing)? A: First try (at LS broadcast distribution): each router keeps a copy of most recent LS packet (LSP) received from every other node upon receiving LSP(R) from router R: if LSP(R) not identical to stored copy then store LSP(R), update LS info for R, and flood LSP(R) else ignore duplicate How can this protocol fail? 2nd Try (at LS Broadcast Distribution) Each router puts a sequence number on its LSPs upon receiving LSP(R) from R if (seq # seq # of stored copy ) of LSP(R) then store LSP(R), update LS info for R, and flood LSP(R) else ignore duplicate How can this protocol fail? 3rd Try (at LS Broadcast Distribution) use lar