Transcript Chapter 17

Internet Multicasting
Chapter 17
Hardware Broadcast
• Broadcast delivery
– Network delivers a copy of a packet to each destination
• Bus technology - single packet transmission
• Switches and point-to-point - copies of the packet are
forwarded across individual connections until all switches have
received a copy
– A computer specifies broadcast delivery by sending a
packet to a broadcast address
• In Ethernet the address field is all ones
• Hardware on each machine recognizes its own or a broadcast
address
– Disadvantage - Demand on resources
Multicasting
• A different type of multi-point delivery
– Allows each system to choose if it wants to participate
– The network interface hardware is configured to
recognize a multicast address for machines in a group
– Forwarding with unicast and broadcast depends on the
network topology
Ethernet Multicast
• An example of hardware multicasting
– Half of Ethernet addresses are reserved for multicasting
– The low order bit of the high-order octet distinguishes
unicast (0) from multicast(1) addresses
• In dotted hexadecimal: 01.00.00.00.00.0016
– Device driver software can reconfigure a device to
allow it to recognize one or more multicast addresses
• Example: 01.5E.00.00.00.01
IP Multicast
• The internet abstraction of hardware multicasting
• Characteristics
– Group address: class D address, some permanent, some
temporary
– Number of groups: limited by practical constraints on
routing table size, actual is 228
– Dynamic group membership: hosts can join or leave
anytime
– Use of hardware: if the underlying hardware permits
multicast, IP uses hardware to send, else it uses
broadcast or unicast to send!
IP Multicast
– Inter-network forwarding: multicast routers are required
to forward IP multicast (capability is usually added to
conventional routers)
– Delivery semantics: uses the same best-effort IP
delivery - multicast datagrams may be lost, delayed,
duplicated, delivered out of order
– Membership and transmission: any may send to the
multicast group; only the group may receive
Conceptual Pieces
• Requirements for internet multicasting
– a multicast addressing scheme
• allowing local autonomy in assigning addresses, but having
global meaning
– a notification and delivery mechanism
• making effective use of hardware multicast, but allowing IP
multicasting over networks without the hardware support
– internetwork forwarding facility
• routing over shortest paths, along paths that lead only to group
members, allowing hosts to join and leave when they choose
IP Multicast Addresses
• IP multicasting uses class D addresses - see
Figures 4.1 and 17.1
– The first four bits are 1110
– The remaining 28 bits specify a multicast group
– Multicast addresses:
• range is from 224.0.0.0 to 239.255.255.255
• lowest address 224.0.0.0 reserved
• up to 224.0.0.255 for routing /group maintenance
• see permanently assigned addresses in Figure 17.2
– notice all systems and all routers
IP Multicast Addresses
• A multicast address
– can only be used as a destination address
– cannot appear in the source address field or in a source
route or record route option
– cannot have ICMP error messages generated for them
(a ping to a multicast address will go unanswered)
• TTL field in multicast messages is decremented, when it
reaches 0, no message is sent
Mapping IP Multicast to
Ethernet Multicast
• The low-order 23 bits of the IP multicast address
is placed in the low-order 23 bits of the Ethernet
multicast address 01.00.5E.00.00.0016
• Thus, IP multicast address 224.0.0.2 becomes
01.00.5E.00.00.0216
• The mapping is not unique and IP software must
check for unwanted multicast datagrams
Multicast Scope
• Members have scope
– Members on a single network, scope is the network
– Members are in a single organization, scope is the
organization
• Each datagram also has scope (also called range)
– Control messages for communication between a host
and router on the same network have a TTL = 1
– Interprocess communication (two applications on the
same host) can have a TTL = 0
Extending Host Software to
Handle Multicasting
• Hosts participate in IP multicast at one of 3 levels
– Level 0 - host cannot send or receive multicast
– Level 1 - host can send, but cannot receive multicast
– Level 2 - host can send and receive multicast
• Modifications to allow sending
– application program specifies multicast address and
network interface software maps the IP into hardware
• Modifications to allow receiving
– application program indicates that it wants to join or
leave a group, and membership must be handled
Internet Group Management
Protocol (IGMP)
• To participate in a multicast that spans multiple
networks, the host must inform local multicast
routers
– Local routers pass membership information to other
routers
• IGMP is used to communicate group membership information
– IGMP is similar to ICMP in that it
• uses IP datagrams to carry messages
• is a standard for TCP/IP and is required on all machines that
receive IP multicast
– IGMP is considered an integral part of IP, not separate
Internet Group Management
Protocol (IGMP)
• IGMP has two phases
– Phase 1: A host joins a multicast group
• It sendsan IGMP message declaring its membership
• Local multicast routers receive the message and propagate
group membership information
– Phase 2: Local multicast routers poll hosts to see who
the remaining members are
• As long as at least one host responds, the router keeps the
group active
• If none respond, the router stops advertising
Internet Group Management
Protocol (IGMP)
• IGMP is designed to avoid adding overhead by
– datagrams that carry IGMP messages use hardware
multicast, if it is available
– multicast routers send a single query to request
information about all groups, not separate messages
– a single router is chosen to poll host membership
– hosts respond to IGMP queries at random intervals
– hosts listen for responses from other hosts and avoid
sending repetitive information (only one host in a group
needs to respond about membership)
Group Membership State
Transitions
• Three states of an entry in a host’s multicast group
tables are shown in Figure 17.4
– Nonmember joining
– Delaying member waits for random time to respond to
router’s query
– Before moving to Member state, the host knows that
another host responded, or its timer expires and this
host sends a response
• Routers generate queries every 125 seconds
• Hosts remain in Member state most of the time
IGMP Message Format
• Type - 1 octet
– General membership query, specific group query,
membership report, leave group, version 1 membership
report (backward compatibility)
• Response time -1 octet
– Maximum interval for which random response time is
determined (if 10, random value from 0 to 10 is chosen)
– If there are many hosts, delay value is larger
• Checksum - 2 octets
• Group address - 4 octets - specific group or all groups
Multicast Forwarding and
Routing Information
• Why is multicast routing difficult?
• Consider the architecture shown in Figure 17.7
– The router should not forward packets intended for the
dotted group across network 2
– If a host on network 2 joins the dotted group, routing
must change to accommodate it
– A multicast router must examine more than just the
destination address
– A host that is not a member may send a datagram to a
group
Basic Multicast Routing
• Reverse Path Forwarding (RPF)
– a multicast router has a conventional routing table with
shortest paths to all destinations
• the router extracts the source address and finds the interface
that leads to the source
• the router forwards a copy of the datagram over all other
interfaces, but not the one back to the source
• this means that RPF wastes bandwidth by transmitting over
networks that don’t lead to group members
• Truncated RPF (TRPF)
– checks to see that paths lead to group members
Consequences of TRPF
• Because TRPF relies on RPF to prevent loops,
TRPF delivers and extra copy of datagrams to
some networks
– duplicates are sent when the network is as Figure 17.8
– R3 and R4 both send copies to host B on network 4
• The source determines delivery path
– Figure 17.9 (a) shows what happens when X is source
• 2 copies go to network 5
– Figure 17.9 (b) shows what happens when Z is source
• 2 copies go to networks 2 and 4
Multicast Trees
• Paths define a forwarding tree, or a delivery tree
–
–
–
–
–
–
the tree contains no cycles
each multicast router corresponds to a node in the tree
a network connecting the routers is an edge in the tree
the source of a datagram is the root
the last router on the path is a leaf
Figure 17.9(a) is a tree, technically part (b) is not
• A forwarding tree defines a set of paths through
multicast routers from a source to all members of
a multicast group (size of tables is a concern)
The Essence of Multicast
Routing
• A Multicast Router must have knowledge of group
membership
• Group membership information must be
propagated across the internet
– Because membership can change rapidly, information at
a given router is imperfect and routing may lag changes
– Design tradeoff: routing overhead and inefficient data
transmission
Reverse Path Multicasting
• Underlying assumptions
– It is more important for a datagram to reach each
member of the group than it is to eliminate unnecessary
transmission
– Multicast routers contain a routing table with correct
information
– Needless transmission is eliminated when possible
• RPM uses a two-step process
– Copies of datagrams are broadcast to the internet
– Multicast routers inform each other of paths that don’t
lead to group members
Reverse Path Multicasting
• Membership information is propagated bottom-up
– It starts with hosts that join or leave the group
– Hosts communicate with their local router using IGMP
– When a router learns that no group member lie beyond a given
network interface, it stops forwarding and notifies the router on the
path back to the root
• When a router learns that there are no members
along a path, that path is pruned
• The system is data-driven
– A router does not send group information until datagrams arrive for
this group (data arrives and we know where to send messages)
Distance Vector Multicast Routing
Protocol
• DVMRP passes information about current
membership and the cost to transfer datagrams
between routers
– Resembles RIP
– Passes information about current membership and cost
of transferring datagrams
– For each possible (group, source) pair, the routers
impose a forwarding tree
– It defines an extended IGMP for multicasting
Mrouted
• Implements DVMRP for UNIX systems
• Mrouted provides
– Route propagation
• Entries in the table include a (group, source) pair and a
corresponding set of interfaces for forwarding
• Mrouted is used in addition to standard routing practice
– Multicast tunneling
• Not all internet routers can forward multicast datagrams
• Multicast datagrams can be tunneled through intermediate
routers that don’t participate in multicast routing
Mrouted
• Mrouted may be configured by a manager to
specify
– multicast groups that are permitted to advertise on each
interface
– how to forward datagrams
• associates a metric and threshold with each route
– a manager can assign a cost to each path
– threshold gives minimum TTL to complete the path
• A tunnel is shown in Figure 17.10 (IP-in-IP)
– a datagram is encapsulated in a unicast datagram and
sent across the nonparticipating network-Figure 17.11
Mrouted
• Multicast tunnels form the basis of the Internet’s
Muticast Backbone (MBONE)
– Often used in teleconferencing
• Consequences of tunneling
– Tunnel costs
– DVMRP must compute its own version of unicast
forwarding that includes the tunnels?
Limitations of DVMRP
• The volume of information kept is high
• Entries for previously active groups are stored
– So that it knows where to send a graft message when a
host joins a gorup that was pruned
• Propagation is slow
• Does not scale well
• Following are designs for overcoming these
limitations
Core Based Trees (CBT)
• Avoids broadcasting
– Instead of broadcasting until negative information is
propagated, it only propagates where hosts have joined
– This is demand driven
• When a host joins, the local router must inform other routers
before datagrams will be forwarded (membership information
sent first)
• Which routers should be informed?
– The internet is divided into regions
– Within each region there is a core router
– Tree is built as hosts send join requests to core
• Each router sends an echo request to check connectivity
Protocol Independent Multicast
(PIM)
• PIM consists of two protocols
– PIM Dense Mode (PIM-DM)
•
•
•
•
Most networks have hosts that listen to each multicast group
Uses RPF to broadcast datagrams to every group
Strops sending when it receives prune requests
Assumes router also uses conventional routing protocols
– PIM Sparse Mode (PIM-SM)
• Members of multicast groups occupy a small subset of possible
networks
• Like CBT, requiresa point to which joins are sent
• Builds a forwarding tree, trees rooted at rendezvous point
Multicast Extensions to OSPF
(MOSPF)
• Uses OSPF to form a forwarding tree for each
source
• Demand driven
• Sends all group information to all routers
Reliable Multicast and ACK
Implosions
• In theory
– Guarantees that group members receive data in order, without loss,
duplication or corruption
– More efficient than broadcast
• In actuality
– If a group has >1 sender, the notion of delivering in sequence is
meaningless
– Duplication happens even on small internets
– Certain applications are susceptible to delay or jitter (audio and
video)
– Reliable protocols require ACK’s => ACK implosion
Reliable Multicast and ACK
Implosions
• To overcome the ACK Implosion problem
– Multicasting is restricted to a single source
– Acknowledgement points are identified
• ACKs are processed further down the tree
– Datagrams are assigned unique number so that loss can
be detected
Summary
• IP multicasting uses class D address space
• Hardware multicast is used, if available
• Multicast groups are dynamic
– Hosts may join or leave at any time
• Not limited to a single physical network
• Group membership is communicated using IGMP
• Two approaches to propagation
– data-driven
– demand-driven
Summary
• More information is required in a multicast
forwarding table than in a unicast routing table
– Entries are required for each (group, source) pair
• Not all routers forward multicast traffic
– Tunnelling could be used
• A multicast datagram is encapsulated in a unicast datagram
• Reliable multicast uses a heirarchy of
acknowledgement points or send redundant
information
For Next Time
• Read Chapter 19