DOC PREVIEW
Berkeley ELENG 122 - Lecture Notes

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 1 EE 122: Multicast Ion Stoica TAs: Junda Liu, DK Moon, David Zats http://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford, and colleagues at UC Berkeley) 2 Motivation Example: Internet Radio  Live 8 concert  Send ~1,000 Kb/s video streams  Peak usage > 100,000 simultaneous users  Consumes > 100 Gbps  If 1000 people are in Berkeley, and if the concert were broadcast from a single location, 1000 unicast streams are sent from that location to Berkeley 3 This approach does not scale… Backbone ISP Broadcast Center 4 Instead build trees Backbone ISP Broadcast Center Copy data at routers At most one copy of a data packet per link • LANs implement link layer multicast by broadcasting • Routers keep track of groups in real-time • Routers compute trees and forward packets along them2 5 Multicast Service Model  Receivers join a multicast group which is identified by a multicast address (e.g. G)  Sender(s) send data to address G  Network routes data to each of the receivers  Note: multicast vs. broadcast  Broadcast: packets are delivered to all end-hosts in the network  Multicast: packets are delivered only to end-hosts that are in (have joined) the multicast group R0 joins G R1 joins G Rn-1 joins G S R0 R1 . . . [G, data] [G, data] [G, data] [G, data] Rn-1 Net 6 Multicast Service Model (cont’d)  Membership access control  Open group: anyone can join  Closed group: restrictions on joining  Sender access control  Anyone can send to group  Anyone in group can send to group  Restrictions on which host can send to group 7 Multicast and Layering  Multicast can be implemented at different layers  data link layer  e.g. Ethernet multicast  network layer  e.g. IP multicast  application layer  e.g. End system multicast  Which layer is best? 8 Multicast Implementation Issues  How are multicast packets addressed?  How is join implemented?  How is send implemented?  How much state is kept and who keeps it?3 9 Data Link Layer Multicast  Recall: end-hosts in the same local area network (LAN) can hear from each other at the data link layer (e.g., Ethernet)  Reserve some data link layer addresses for multicast  Join group at multicast address G  Network interface card (NIC) normally only listens for packets sent to unicast address A and broadcast address B  To join group G, NIC also listens for packets sent to multicast address G (NIC limits number of groups joined)  Implemented in hardware, thus efficient  Send to group G  Packet is flooded on all LAN segments, like broadcast  Can waste bandwidth, but LANs should not be very large  Only host NICs keep state about who has joined → scalable to large number of receivers, groups 10 Problems with Data Link Layer Multicast  Single data link technology  Single LAN  Limited to small number of hosts  Limited to low diameter latency  Essentially all the limitations of LANs compared to internetworks 11 Network Layer (IP) Multicast  Overcomes limitations of data link layer multicast  Performs inter-network multicast routing  Relies on data link layer multicast for intra-network routing  Portion of IP address space defined as multicast addresses  228 addresses for entire Internet  Open group membership  Anyone can send to group  Flexible, but leads to problems 12 IP Multicast Routing  Intra-domain  Source Specific Tree: Distance Vector Multicast Routing Protocol (DVRMP)  Shared Tree” Core Based Tree (CBT)  Inter-domain  Protocol Independent Multicast  Single Source Multicast4 13 Distance Vector Multicast Routing Protocol (DVRMP)  An elegant extension to DV routing  Use shortest path DV routes to determine if link is on the source-rooted spanning tree  Three steps in developing DVRMP  Reverse Path Flooding  Reverse Path Broadcasting  Truncated Reverse Path Broadcasting 14 Reverse Path Flooding (RPF)  Extension to DV unicast routing  Packet forwarding  If incoming link is shortest path to source  Send on all links except incoming  Packets always take shortest path  assuming delay is symmetric  Issues  Some links (LANs) may receive multiple copies  Every link receives each multicast packet, even if no interested hosts s:2 s s:1 s:3 s:2 s:3 r 15 Example  Flooding can cause a given packet to be sent multiple times over the same link  Solution: Reverse Path Broadcasting x y z S a b duplicate packet 16 Reverse Path Broadcasting (RPB)  Chose parent of each link along reverse shortest path to source  Only parent forward to a link (child link)  Identify Child Links 1. Routing updates identify parent 2. Since distances are known, each router can easily figure out if it's the parent for a given link 3. In case of tie, lower address wins x y z S a b 5 6 child link of x for S forward only to child link Parent of z on reverse path5 17 Don’t Really Want to Flood!  This is still a broadcast algorithm – the traffic goes everywhere  Need to “Prune” the tree when there are subtrees with no group members  Solution: Truncated Reverse Path Broadcasting 18 Truncated Reverse Path Broadcasting (TRPB)  Extend DV/RPB to eliminate unneeded forwarding  Identify leaves  Routers announce that a link is their next link to source S  Parent router can determine that it is not a leaf  Explicit group joining on LAN  Members periodically (with random offset) multicast report locally  Hear and report, then suppress own  Packet forwarding  If not a leaf router or have members  Out all links except incoming r1 r2 S NL NL NL L L L – leaf node NL – Non-leaf node 19 Pruning Details  Prune (Source,Group) at leaf if no members  Send Non-Membership Report (NMR) up tree  If all children of router R send NRM, prune (S,G)  Propagate prune for (S,G) to parent R  On timeout:  Prune dropped  Flow is reinstated  Down stream routers re-prune  Note: a soft-state approach 20 Pruning Details  How to pick prune timers? 


View Full Document

Berkeley ELENG 122 - Lecture Notes

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?