Multicast

0
20
Multicast - DVMRP, MOSPF, PIM
Multicast – DVMRP, MOSPF, PIM

Multicast routing

  • Unicast: single source sends to a single destination
  • Multicast: hosts are part of a multicast group
    packet sent by any member of a group is received by all
    Efficiency and Logical Addressing
  • Useful for
    multiparty video conference
    distance learning
    resource location

Multicast group

Multicast group

 

  • Associates a set of senders and receivers with each other
    but independent of them
    created either when a sender starts sending from a group
    or a receiver expresses interest in receiving
    even if no one else is there!
  • Sender does not need to know receivers’ identities
    the rendezvous point

Addressing

  • Multicast group on the Internet has its own Class D address
    looks like a host address, but isn’t
  • Senders send to the address
  • Receivers anywhere in the world request packets from that address
  • “Magic” is in associating the two: dynamic directory service
  • Four problems
    which groups are currently active
    how to express interest in joining a group
    discovering the set of receivers in a group
    delivering data to members of a group

Expanding ring search

Expanding ring search

  • A way to use multicast groups for resource discovery
  • Routers decrement TTL when forwarding
  • Sender sets TTL and multicasts
    reaches all receivers <= TTL hops away
  • Discovers local resources first
  • Since heavily loaded servers can keep quiet, automatically distributes load

Multicast flavors

  • Unicast: point to point
  • Multicast:
    point to multipoint
    multipoint to multipoint
  • Can simulate point to multipoint by a set of point to point unicasts
  • Can simulate multipoint by a set of point to multipoint multicasts
  • The difference is efficiency

Example

Multicast flavors

  • Suppose A wants to talk to B, G, H, I, B to A, G, H, I
  • With unicast, 4 messages sent from each source
    links AC, BC carry a packet in triplicate
  • With point to multipoint multicast, 1 message sent from each source
    but requires the establishment of two separate multicast groups
  • With multipoint to multipoint multicast, 1 message sent from each source,
    single multicast group

Shortest path tree

Shortest path tree

  • Ideally, want to send exactly one multicast packet per link
    forms a multicast tree rooted at the sender
  • Optimal multicast tree provides the shortest path from sender to every receiver
    the shortest-path tree rooted at the sender

Issues in wide-area multicast

  • Difficult because
    sources may join and leave dynamically
    need to dynamically update the shortest-path tree
    leaves of the tree are often members of broadcast LAN
    would like to exploit LAN broadcast capability

Issues in wide-area multicast

  • would like a receiver to join or leave without explicitly notifying the sender
  • otherwise, it will not scale

Multicast in a broadcast LAN

  • Wide area multicast can exploit a LAN’s broadcast capability
  • E.g. Ethernet will multicast all packets with multicast bit set on destination address
  • Two problems:

what multicast MAC address corresponds to a given Class D IP address?
does the LAN have contained any members for a given group (why do we need to know this?)

Class D to MAC translation

Class D to MAC translation

  • Multiple Class D addresses map to the same MAC address
  • Well-known translation algorithm => no need for a translation table

Internet Group Management Protocol

  • Detects if a LAN has any members for a particular group
    If no members, then we can prune the shortest path tree for that group by telling parent
  • Router periodically broadcasts a query message
  • Hosts reply with the list of groups they are interested in
  • To suppress traffic
    reply to a random timeout
    broadcast reply
    if someone else has expressed interest in a group, drop out
  • To receive multicast packets:
    translate from class D to MAC and configure the adapter

Wide area multicast

  • Assume
    each endpoint is a router
    a router can use IGMP to discover all the members in its LAN that want to subscribe to each multicast group
  • Goal
    distribute packets coming from any sender directed to a given group to all routers on the path to a group member

Simplest solution

  • Flood packets from a source to entire network
  • If a router has not seen a packet before, forward it to all interfaces except the incoming one
  • Pros
    simple
    always works!
  • Cons
    routers receive duplicate packets
    detecting that a packet is a duplicate requires storage, which can be expensive for long multicast sessions

A clever solution

  • Reverse path forwarding
  • Rule
    the forward packet from S to all interfaces if and only if a packet arrives on the interface that corresponds to the shortest path to S
    no need to remember past packets
    C need not forward packet received from D

Reverse Path Forwarding

Cleverer

  • Don’t send a packet downstream if you are not on the shortest path from the downstream router to the source
    How do you know that – one approach is RPB like
  • C need not forward packet from A to E

cleverer

  • Potential confusion if downstream router has a choice of shortest paths to source (see figure on the previous slide)

Pruning

  • RPF/B does not completely eliminate unnecessary transmissions

Pruning

  • B and C get packets even though they do not need it
  • Pruning => router tells parent in tree to stop forwarding
    Can infer using routing tables (split horizon w/ poisonous reverse) and membership reports
  • Can be associated either with a multicast group or with a source and group
    trades selectivity for router memory (#groups x #sources in the group)

Rejoining

rejoining

  • What if host on C’s LAN wants to receive messages from A after a previous prune by C?
    IGMP lets C know of host’s interest
    C can send a join(group, A) message to B, which propagates it to A
    or, periodically flood a message; C refrains from pruning

DVMRP

  • Distance-vector Multicast routing protocol
  • Very similar to RIP
    distance vector
    hop count metric
  • Used in conjunction with
    flood-and-prune (to determine memberships)
    NMR/prunes store per-source and per-group information, aging of NMRs,
    reverse-path forwarding (to decide where to forward a packet)
    explicit cancel NMR messages to reduce join latency (but no source info, so still need flooding) and handle topology changes

A problem

  • Reverse path forwarding requires a router to know the shortest path to a source
    known from the routing table
  • Doesn’t work if some routers do not support multicast
    virtual links between multicast-capable routers
    the shortest path to A from E is not C, but F

DVMRP

  • Two problems
    how to build virtual links
    how to construct routing table for a network with virtual links

Tunnels

  • Why do we need them?

Tunnels

  • Consider packet sent from A to F via multicast-incapable D
  • If packet’s destination is Class D, D drops it
  • If the destination is F’s address, F doesn’t know the multicast address!
  • So, put packet destination as F, but carry multicast address internally
  • Encapsulate IP in IP => set protocol type to IP-in-IP

Multicast routing protocol

  • Interface on “shortest path” to source depends on whether path is real or virtual

Multicast routing protocol

  • Shortest path from E to A is not through C, but F
    so packets from F will be flooded, but not from C
  • Need to discover shortest paths only taking multicast-capable routers into account
    DVMRP

MOSPF

  • Multicast extension to OSPF
  • Routers flood group membership information with LSPs
  • Each router independently computes shortest-path tree that only includes multicast-capable routers
    no need to flood and prune
  • Complex
    interactions with external and summary records
    need storage per group per link
    need to compute shortest path tree per source and group

Core-based trees

  • Problems with DVMRP-oriented approach
    need to periodically flood and prune to determine group members
    need to source per-source and per-group prune records at each router
    Charge routers not involved in multicast
    Dependence on the similarity of multicast/unicast algorithms across the Internet.
  • Key idea with core-based tree
    coordinate multicast with a core router
    Each core router allowed 2^32 groups
    the host sends a join request to core router
    Name to (coreid, group id) resolution via a directory service
    routers along path mark incoming interface for forwarding

Example

Core Based Trees

  • Pros
    routers not part of a group is not involved in pruning
    explicit join/leave makes membership changes faster
    the router needs to store only one record per group
  • Cons
    all multicast traffic traverses core, which is a bottleneck
    traffic travels on non-optimal paths (delay CBT/SPT <= 2, from Wall 1980. Simulations in Deering96 show 1.4)
    Core placement?

Protocol independent multicast (PIM)

  • Tries to bring together best aspects of CBT and DVMRP
  • Desiderata
    Efficient Sparse Group Support, Low delay data distribution, independence from underlying unicast, robustness to routing changes, interoperability with DVMRP/MOSPF
  • Choose different strategies depending on whether multicast tree is dense or sparse
    flood and prune good for dense groups
    only need a few prunes
    CBT needs explicit join per source/group
    CBT good for sparse groups
  • Dense mode PIM == DVMRP
  • Sparse-mode PIM is similar to CBT
    but receivers can switch from CBT to a shortest-path tree

PIM basics

PIM basics 1

PIM basics 2

PIM basics

PIM basics

PIM

  • In CBT, E must send to core
  • In PIM, B discovers shorter path to E (by looking at unicast routing table)
    sends join message directly to E
    sends prune message towards the core
  • Core no longer bottleneck
  • Survives failure of core

PIM Basics

PIM Basics

  • the rendezvous point is sort of like Core in CBT
    because it no longer carries all the traffic like a CBT core
  • Rendezvous points periodically send “I am alive” messages downstream
  • Leaf routers set timer on receipt
  • If timer goes off, send a join request to alternative rendezvous point
  • Problems
    how to decide whether to use dense or sparse mode?
    how to determine “best” rendezvous point?

Routing vs. policy routing

  • In standard routing, a packet is forwarded on the ‘best’ path to destination
    the choice depends on load and link status
  • With policy routing, routes are chosen depending on policy directives regarding things like
    source and destination address
    transit domains
    quality of service
    time of day
    charging and accounting
  • The general problem is still open
    a fine balance between correctness and information hiding

Multiple metrics

  • Simplest approach to policy routing
  • Advertise multiple costs per link
  • Routers construct multiple shortest path trees

Multiple Metrics

Problems with multiple metrics

  • All routers must use the same rule in computing paths
  • Remote routers may misinterpret policy
    source routing may solve this
    but introduces other problems (what?)

Provider selection

  • Another simple approach
  • Assume that a single service provider provides almost all the path from source to destination
    e.g. AT&T or MCI
  • Then, choose policy simply by choosing provider
    this could be dynamic (agents!)
  • On Internet, can use a loose source route through service provider’s access point
  • Or, multiple addresses/names per host

Crankback

  • Consider computing routes with QoS guarantees
  • Router returns packet if no next hop with sufficient QoS can be found
  • In ATM networks (PNNI) used for the call-setup packet
  • On Internet, may need to be done for _every_ packet!
    Will it work?

Crankback

 

Related Post

LEAVE A REPLY

Please enter your comment!
Please enter your name here