Multicast Routing Papers: DVMRP and MOSPFBridges and Extended LANsLearning BridgesSlide 4Example: Learning BridgesSlide 6Slide 7Slide 8Slide 9Example: Learning Bridges(cont)Slide 11Spanning Tree AlgorithmMulticast Routing in Datagram Internetworks and Extended LANsEfficient multicast in Extended LANsHow to locate receiversHow to locate receivers (contd)Bridge Multicast TableSingle Spanning-Tree Multicast RoutingAnother exampleSuppressing Membership ReportsWhy change the destination?PowerPoint PresentationDistance Vector Multicast RoutingBroadcast Trees and Multicast Trees in Point-to-Point Networks with an underlying unicast routing protocolReverse Path Flooding (RPF) algorithm (broadcast in point-to-point networks)ExampleInternetworks (review)A problem with original RPFReverse Path Broadcasting (RPB)Is LAN l the parent of R on the tree?Is LAN l a child of R on the tree?Slide 32Slide 33ObservationsOverheadOverhead (continued …)Slide 37Pruning the Tree(small detour) Why not do membership reports?What do we do?Truncated Reverse-Path Broadcast (TRPB)Leaf Truncation exampleSlide 43Algorithm Implementation.Leaf Link or not?Leaf BitmapsReceivers on a Link?Overview of “bitmaps” requiredReverse Path Multicasting (RPM)Slide 50Slide 51NMR expirationPros and ConsLink-State Multicast RoutingSlide 55Slide 56How do you know who are the sources?MOSPF CacheSlide 59Computer NetworksDr. Jorge A. CobbMulticast Routing Papers: DVMRP and MOSPF2LANs have physical limitations (e.g., 2500m)Bridges connect two or more LANs together.They are transparent to hosts (does not change packets in any way)•Bridges see all messages in its attached LANs•Copy message from one LAN to another if necessary Bridges and Extended LANsABridgeB CX YZPort 1Port 2Port 3H IJ3Forward messages only when necessary (without modifying the message in any way).Maintain a forwarding table•Often incomplete (initially empty!)•Learn table entries based on source address of messages seen.•If destination is not on table, forward over all other portsLearning Bridges ABridgeB CX YZPort 1Port 2Port 3H IJHost PortA 1B 1C 1X 2Y 2H 34I sends a message to ZBridge “learns” I comes from port 3•I is added to the table•Z is unknown•bridge copies the message over BOTH port 1 and port 2Learning Bridges ABridgeB CX YZPort 1Port 2H IJHost PortA 1B 1C 1X 2Y 2H 3Port 3Z sends a message to I (e.g. some reply)Bridge “learns” Z comes from port 2•Z is added to the table•bridge copies the message ONLY over port 3 (I is already in the table)5Example: Learning BridgesB1B7B6B5B8B4B3B2IJLKMPN OIBridge HostLAN6Example: Learning BridgesAssume initially all bridges forwarding tables are empty Host I sends data message to Host J: This data message is broadcasted to every LAN. Why? Because no one knows where J is! Due to which, every bridge learns about host I location and creates forwarding table entry for Host I.7Example: Learning BridgesB1B7B6B5B8B4B3B2IJLKMPN OIBridge HostLANIJIIJIJIIJII I III8Example: Learning Bridges Host J then sends data message to Host I: Since all bridges have an entry for host I, message goes only through Host J B7 B8 B3 B2 B1 Host I Only these bridges have now an entry for Host J. All other nodes do not, e.g., B4 does not forwarding table entry for Host J. Note that from now on (until the lifetimes expire) all data messages between Host I and Host J go only through the LANs on the path from Host I to Host J.9Example: Learning BridgesB1B7B6B5B8B4B3B2IJLKMPN OIBridge HostLANIIII I IIIJIJIJJIJJIJJJ10Example: Learning Bridges(cont) Host K sends a data message to Host J:•The nodes seeing this data message are B4 B5 B6 B3 B8 B7 only these nodes learn Host K location. Host k packet has been broadcast in a limited fashion.11Example: Learning BridgesB1B7B6B5B8B4B3B2IJLKMPN OIBridge HostLANIIII I IIIJJJJJKJKJKJKKKKKK12Spanning Tree Algorithm Problem: loopsBridges run a distributed spanning tree algorithm •Logically delete certain bridges to have a spanning tree•We will assume we have a spanning tree B3ACEDB2B5BB7KFHB4JB1B6GIB3ACEDB5BB7KFHB4JB1GIComputer NetworksDr. Jorge A. CobbMulticast Routing in Datagram Internetworks and Extended LANsS. Deering and D. CheritonACM Transactions on Computer Systems199014Efficient multicast in Extended LANsHow to do efficient multicast in Extended LANs? (I.e. in LANs with bridges) (NOT IP !!!!)A simple way: bridges propagate multicast (and broadcast) packets across every segment of the extended LAN•Way too inefficient, especially for multicast applications with sparsely located receivers How to do multicast efficienty in Extended LANs?15How to locate receiversIf bridges know which interface leads to members of a given group, they will forward the packets on those interfaces only•Remember, we have a tree•There is only one path from the bridge to each receiver.But, in general, how do bridges learn which interface leads to individual hosts?•When a packet arrives from a host, bridge records the (source-host addr, interface, age) into a table•What about receivers?•Receivers don’t send data!How to locate receivers (contd)We want to forward multicast packets only over LANs leading to receiversTo learn the location of receivers, we force receivers (i.e., group members) to periodically transmit a membership-reportA member (receiver) of a group G periodically sends a membership-report of the form:•LAN source address = G, •LAN destination address = “ALL-BRIDGES” multicast address.1617Bridge Multicast TableArrows indicate the direction where group members are locatedA bridge receiving a repot records the incoming interface of the report as an outgoing interface for group GIt then forwards the report over all of its interfaces in the extended LAN (why over all interfaces? I.e., why a broadcast?)Multicast table at each bridge has the following row for each multicast group: (muticast addr, (outgoing interface, age), (outgoing interface, age), … )18Single Spanning-Tree Multicast RoutingBridge algorithm (summary)•If packet arrives and source address is a mcast group (i.e. a report), •record arriving interface as an outgoing-interface with an age of zero for this mcast address•and forward to all other interfaces.•Periodically increment age of outgoing interface•when age=expiry threshold, delete this outgoing-interface info from the table’s
View Full Document
Unlocking...