CMPE 150 Introduction to Computer Networks Set 13 Internet Multicasting Dr Soumya Roy soumya cse ucsc edu Spring 2003 UCSC cmpe150 1 Homework Assignments Homework assignment 3 Chapter Four Due by May 22 Spring 2003 UCSC cmpe150 2 Multicast one sender to many receivers Multicast act of sending datagram to multiple receivers with single transmit operation analogy one teacher to many students Spring 2003 UCSC cmpe150 3 Uses of Multicasting Multimedia broadcast IP radio webcasts Teleconferencing multiparty videoconferencing with Mbone CUSeeMe Database replication Distributed computing immediate updates to all members Real time workgroups multimedia collaboration System management concerted file updates to group of hosts Stock ticker low bandwidth quotes to millions of hosts cf Pointcast Spring 2003 UCSC cmpe150 4 Multicast one sender to many receivers Question how to achieve multicast Spring 2003 UCSC cmpe150 5 Multicast via Unicast source sends N unicast datagrams one addressed to each of N receivers routers forward unicast datagrams Spring 2003 multicast receiver red not a multicast receiver UCSC cmpe150 6 Application Layer Multicast routers forward unicast datagrams Spring 2003 end systems involved in multicast copy and forward unicast datagrams among themselves multicast receiver red not a multicast receiver UCSC cmpe150 7 Network Multicast routers forward unicast and multicast datagrams Spring 2003 UCSC multicast receiver red not a multicast receiver cmpe150 8 Tunneling Q How to connect islands of multicast routers in a sea of unicast routers physical topology logical topology mcast datagram encapsulated inside normal non multicastaddressed datagram normal IP datagram sent thru tunnel via regular IP unicast to receiving mcast router receiving mcast router unencapsulates to get mcast datagram Spring 2003 UCSC cmpe150 9 IP Multicast Architecture Based on Steve Deering s original proposal SIGCOMM 88 Proceedings his PhD thesis It consists of three basic components Group addressing based on globally unique identifiers IP multicast addresses Separation of senders and receivers with anonymous receiver affiliation A tree based routing and group structure Spring 2003 UCSC cmpe150 10 IP Multicast Architecture contd 128 59 16 12 128 119 40 186 multicast group 226 17 30 197 128 34 108 63 128 34 108 60 multicast group concept use of indirection hosts addresses IP datagram to multicast group routers forward multicast datagrams to hosts that have joined that multicast group Spring 2003 UCSC cmpe150 11 IP Multicast Addresses 28 bits for groups 250 million groups Two kinds of supported addresses Permanent e g 224 0 0 1 all systems on LAN 224 0 0 2 all routers on LAN Temporary must be created before they can be addressed join and leave Spring 2003 UCSC cmpe150 12 IP Multicast Addressing Problem There are plenty of IPv4 and IPv6 addresses for globally unique multicast addresses The problem is how to assign these addresses permanently or temporarily to multicast groups Using globally unique multicast addresses requires Internet wide coordination in the assignment of identifiers to groups Evolving solution Make multicast identifiers locally unique examples are now evolving e g EXPRESS Simple Multicast use the IP address of a core and a multicast address that the core uses for only one group as the identifier of a group Spring 2003 UCSC cmpe150 13 IGMP Internet Group Management Protocol host sends IGMP report when application joins mcast group router sends IGMP query at regular intervals host belonging to a mcast group must reply to query report query Spring 2003 UCSC cmpe150 14 Joining a mcast group twostep process IGMP IGMP wide area multicast routing IGMP Spring 2003 UCSC cmpe150 15 Per Source Per Group Tree Spring 2003 UCSC cmpe150 16 Shortest Path Tree Multicast forwarding tree tree of shortest path routes from source to all receivers Dijkstra s algorithm S source LEGEND R1 1 2 R4 R2 3 R3 Spring 2003 router with attached group member 5 4 R6 router with no attached group member R5 6 R7 UCSC i link used for forwarding i indicates order link added by algorithm cmpe150 17 Reverse Path Forwarding rely on router s knowledge of unicast shortest path from it to sender each router has simple forwarding behavior if mcast datagram received on incoming link on shortest path back to center then flood datagram onto all outgoing links else ignore datagram Spring 2003 UCSC cmpe150 18 Reverse Path Forwarding example S source LEGEND R1 R4 router with attached group member R2 router with no attached group member R5 R3 R6 datagram will be forwarded datagram will not be forwarded R7 result is a source specific reverse SPT may be a bad choice with asymmetric links Spring 2003 UCSC cmpe150 19 Reverse Path Forwarding pruning prune msgs sent upstream by router with no downstream group members LEGEND S source R1 router with attached group member R4 R2 P R5 R3 Spring 2003 R6 P R7 UCSC P router with no attached group member prune message links with multicast forwarding cmpe150 20 Distance Vector Multicast Routing Protocol DVMRP DVMRP distance vector multicast routing protocol RFC1075 flood and prune reverse path forwarding source based tree RPF tree based on DVMRP s own routing tables constructed by communicating DVMRP routers no assumptions about underlying unicast odds and ends commonly implemented in commercial routers Mbone routing done using DVMRP Spring 2003 UCSC cmpe150 21 Problems with Basic Approach Flooding the Internet to establish a multicast routing tree is not an option This is the key reason why multicasting based on DVMRP cannot be deployed on a large scale The problem stems from the lack of addressing information in an IP multicast address Where is a multicast group on the Internet The solution to this problem is to use special nodes as the address of a group Spring 2003 UCSC cmpe150 22 Per Group Shared Tree Spring 2003 UCSC cmpe150 23 Shared Tree Shared tree Shared Tree Steiner Tree Steiner Tree minimum cost tree connecting all routers with attached group members Problem is NP complete heuristics exists Not used in practice Computational complexity Information about entire network needed Monolithic rerun whenever a router needs to join leave Spring 2003 UCSC cmpe150 25 Center based trees single delivery tree shared by all one router identified as center of tree to join edge router sends unicast join msg addressed to center router join msg processed by intermediate routers and forwarded towards center
View Full Document
Unlocking...