Where we are in the big picture!CS118!1!HTTP TCP IP Ethernet interface HTTP TCP IP Ethernet interface IP IP Ethernet interface Ethernet interface SONET interface SONET interface host host router router HTTP message TCP segment IP packet IP packet IP packet Where we are & schedule for next 3 weeks!! Week 7: network routing!" link-state and distance-vector algorithms!" Routing in the Internet: RIP, OSPF, BGP!! Week 8!" Tuesday: broadcast & multicast routing!" Thursday: link layer protocols!! Week 9!" Tuesday: Ethernet, switches!" Thursday: Wireless communication!! Week 10:!" Tuesday: Mobile networking!" Thursday: review!CS118!2!replicate at source Broadcast Routing!! Deliver packets from one host to all other hosts!! 2 ways to implement!CS118!3!R1 R2 R3 R4 source replication R1 R2 R3 R4 in-network replication replicate at branch points Broadcast by in-network replication!! Flooding: when a node receives a broadcast packet, sends a copy to all its neighbors!" Problem: packet looping!! Controlled flooding: node broadcasts a packet only if it hasn’t seen the same packet before!" Problem: Node must keep track of all packets already seen!! Reverse Path Forwarding (RPF): a node N forwards a packet from source S if the packet arrived on the shortest path from N to S!" Use the forwarding table to check!" eliminate looping!" Can still receive duplicate packets!CS118!4!R1 R2 R3 R4 R5 R6 R7 sourceDuplicate elimination: Spanning Tree!! First construct a spanning tree!! Nodes forward copies only along spanning tree!! All sources send data along the same tree!Q: how to choose the root of the tree?!A1: source-based spanning tree!CS118!5!A B G D E c F A B G D E c F (a) Broadcast initiated at A (b) Broadcast initiated at D source source A2: Center-based Spanning Tree!! First pick a center node (E in this example)!! Each node sends unicast join message towards the center node!" A join message is forwarded until it arrives at a node already on the spanning tree!CS118!6!A B G D E C F (a) Stepwise construction of spanning tree A B G D c F (b) Resulting spanning tree E Multicast!! Multicast: Delivering data to multiple (but not necessarily all) destinations!" Interested hosts join a multicast group!" Packets delivered to all members in the group!! Multicast routing!" Basic ideas: how to do it?!" 3 specific multicast routing protocols!# DVMRP: Distance Vector Multicast Routing Protocol!# MOSPF: Multicast OSPF!# PIM: Protocol Independent Multicast!CS118!7!Multicast data delivery!! Per-source-tree: one tree rooted at each sender to reach all receivers in the same multicast group!" 2 ways to build: link-state (MOSPF), RPF (DVMRP)!! Shared-tree: a single tree is used by all senders to the same multicast group!CS118!8!Shared tree Source-based trees Red host: member of multicast group Gray host: non-memberRecall: Reverse Path Forwarding!CS118!9!♦ a node N forwards packet from source S if it arrived on shortest path from N to S!♦ Assuming symmetric link cost, RPF builds a source-specific shortest path broadcast tree!– But we need a multicast tree!R1 R2 R3 R4 R5 R6 R7 packets from S to the multicast group will be forwarded LEGEND S: source packets will not be forwarded Pruning: Trim broadcast tree to mcast tree!! no need to forward packets down branches which has no mcast group members!! router with no downstream group members sends “prune” message upstream!" Routers keep state regarding prune msgs!CS118!10!R1 R2 R3 R4 R5 R6 R7 router with attached group member router with no attached group member prune message LEGEND S: source links over which mcast packets will be forwarded P P P A Quick Summary: Broadcast, Multicast!! Similarity: need to build a distribution tree!! Difference!A multicast tree = a broadcast tree with some branches trimmed off!" Only keep branches that lead to member hosts of the multicast group!! How to build a tree!" Per source tree: can be built by RPF!# Can also be built by knowing the complete graph: MOSPF!" Shared tree!# Pick a rendevzous point (RP) first!# Each router sends join message towards the RP!CS118!11!Distance-Vector Multicast Routing Protocol!! DVMRP routers run RIP to build (unicast) routing table!! Use RPF checking to build source-based tree!" First packet to mcast group floods everywhere!" Edge routers with no members send prune msg upstream!! soft state: router periodically delete prune state!" Sender may have finished by then!" If not, downstream router prune again!CS118!12!R1 R2 R3 R4 R5 R6 R7 P P ◆ If a new member shows up, routers can quickly graft onto mcast tree – sending a graft message to cancel the prune state sourceShortest Path Multicast Tree: MOSPF !! OSPF: Each node maintains a complete network graph !" Use Dijkstra algorithm to compute the shortest path!! MOSPF (Multicast OSPF)!" Carry multicast membership in link-state message!" For each source S: router Ri computes shortest path tree from S to reach all members, decides Ri's position on the tree to figure out where to forward packet from the source S!CS118!13!R1 R2 R3 R4 R5 R6 R7 router with attached group member router with no attached group member LEGEND S: source Center-based shared routing tree!! one router identified as “center” of tree!! Each router with mcast member attached sends unicast join-msg addressed to the center router!" join-msg processed at each intermediate router*!" join-msg either hits existing tree branch for this center, or arrives at center!" path taken by join-msg becomes new branch of tree!CS118!14!R1 R2 R3 R4 R5 R6 R7 * Join msg processing: recording • multicast group address • the interfaces associated with the multicast group: incoming and outgoing interfaces PIM: Protocol Independent Multicast!! independent from underlying unicast routing algorithm!! two different operational modes:!" Dense mode: group members densely packed!" Sparse mode: small number of group members, widely scatted in various places !! Do not send multicast packets anywhere until receivers explicitly request!CS118!15!PIM - Sparse Mode!! For each group: Build a center-based shared tree rooted at a rendezvous point (RP)!! router with members sends join msg to RP!" intermediate routers update state and forward join msgs!! Data
View Full Document
Unlocking...