Computer Networks Dr. Jorge A. Cobb Multicast Routing Papers: DVMRP and MOSPF2 l LANs have physical limitations (e.g., 2500m) l Bridges connect two or more LANs together. l 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 LANs A Bridge B C X Y Z Port 1 Port 2 Port 3 H I J3 l Forward messages only when necessary (without modifying the message in any way). l 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 ports Learning Bridges A Bridge B C X Y Z Port 1 Port 2 Port 3 H I J Host Port A 1 B 1 C 1 X 2 Y 2 H 34 l I sends a message to Z l Bridge “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 2 Learning Bridges A Bridge B C X Y Z Port 1 Port 2 H I J Host Port A 1 B 1 C 1 X 2 Y 2 H 3 Port 3 l Z sends a message to I (e.g. some reply) l 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)5 Example: Learning Bridges B1 B7 B6 B5 B8 B4 B3 B2 I J L K M P N O I Bridge Host LAN6 Example: Learning Bridges Assume 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.7 Example: Learning Bridges B1 B7 B6 B5 B8 B4 B3 B2 I J L K M P N O I Bridge Host LAN IàJ I IàJ IàJ I IàJ I I I I I I8 Example: 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.9 Example: Learning Bridges B1 B7 B6 B5 B8 B4 B3 B2 I J L K M P N O I Bridge Host LAN I I I I I I I I JàI JàI J JàI J JàI J J J10 Example: 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.11 Example: Learning Bridges B1 B7 B6 B5 B8 B4 B3 B2 I J L K M P N O I Bridge Host LAN I I I I I I I I J J J J J KàJ KàJ KàJ KKKKKK12 Spanning Tree Algorithm l Problem: loops l Bridges run a distributed spanning tree algorithm • Logically delete certain bridges to have a spanning tree • We will assume we have a spanning tree B3 A C E D B2 B5 B B7 K F H B4 J B1 B6 G I B3 A C E D B5 B B7 K F H B4 J B1 G IComputer Networks Dr. Jorge A. Cobb Multicast Routing in Datagram Internetworks and Extended LANs S. Deering and D. Cheriton ACM Transactions on Computer Systems 199014 Efficient multicast in Extended LANs l How to do efficient multicast in Extended LANs? (I.e. in LANs with bridges) (NOT IP !!!!) l 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?15 How to locate receivers l If 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. l 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) l We want to forward multicast packets only over LANs leading to receivers l To learn the location of receivers, we force receivers (i.e., group members) to periodically transmit a membership-report l A 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. 1617 Bridge Multicast Table Arrows indicate the direction where group members are located l A bridge receiving a repot records the incoming interface of the report as an outgoing interface for group G l It then forwards the report over all of its interfaces in the extended LAN (why over all interfaces? I.e., why a broadcast?) l Multicast table at each bridge has the following row for each multicast group: (muticast addr, (outgoing interface, age), (outgoing interface, age), … )18 Single Spanning-Tree Multicast Routing l Bridge 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 entry • if no outgoing-interfaces remain, delete the entire entry • If a packet arrives with a multicast destination address • forward a copy on every outgoing-interface recorded in the table entry (if any) excluding the arriving interface19 Another example B3 A C E D B5 B B7 K F H B4 J B1 G I G G = group G member (receiver) (color is only to distinguished what was learned from each membership report) G • Arrows indicate the location of the group member • Membership reports are forwarded over all links of a bridge What if a host at E sends a msg to group G? What if a host at A sends a msg to group G? What is the multicast table entry of G at each router?20 Suppressing Membership Reports
View Full Document
Unlocking...