Evolution of multicast

Anders Iver Gjermo (ai@gjermo.com)

2015-03-06

1988

Multicast is old!

Stephen Deering

introduces the first concrete ideas about multicast in his Ph.D. dissertation.

One year before Tim Berners-Lee’s proposals for the World Wide Web.

1992

First wide scale test

Audiocast from the IETF meeting in San Diego over MBone.

World Wide Web still has less than 100 pages.

`mrouted`

Application layer implementation running on connected workstations.

Traffic is routed through unicast-encapsulated tunnels between members.

{
    "nodes": [
        { "type": "member", "count": 6 },
        { "type": "other", "count": 6 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 1 },
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 7 },
        { "type": "no", "source": 1, "target": 2 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 8 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 3, "target": 8 },
        { "type": "no", "source": 3, "target": 9 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 4, "target": 10 },
        { "type": "no", "source": 4, "target": 11 },
        { "type": "no", "source": 5, "target": 8 },
        { "type": "no", "source": 5, "target": 10 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 6, "target": 10 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 7, "target": 10 },
        { "type": "no", "source": 8, "target": 11 },
        { "type": "no", "source": 10, "target": 11 }
    ],
    "tunnels": [
        [0,6,10,4],
        [1,2],
        [2,9,3],
        [2,8,4],
        [4,8,5]
    ]
}

Early MBone network

“Broadcast and prune”

Source sends on all interfaces.
Routers do RPF checks on incoming traffic.
- Drop traffic if RPF fails,
- or respond with prune msg.
Edge/leaf discover group members through IGMP.
- Forward traffic to members,
- or respond with prune msg.
Routers receiving prune msgs on all interfaces, will forward towards source.
Repeat periodically.

DVMRP

Distance Vector Multicast Routing Protocol

Used broadcast and prune, but:

no pruning at all in the beginning, and RPF checks on neighbors to select output interfaces.

1994/95

MBone is expanding

A big concert with The Rolling Stones is broadcasted.

links appear in Russia & Antarctica.

Hardware support & new protocols.

PIM-DM

Protocol Independent Multicast - Dense Mode

Similar to DVMRP, but:

Uses whatever unicast routing table is available (protocol independent).
Does not do RPF checks on neighbors.

MOSPF

Multicast extensions to Open Shortest Path First

Broadcasts group membership info within an AS.
- Allows each router to have a complete picture.
- Requires more state to be maintained per router.
Shortest path trees per group are build using Dijkstra.
Data streams is only sent to group members.

{
    "nodes": [
        { "type": "green", "count": 4 },
        { "type": "orange", "count": 5 },
        { "type": "other", "count": 3 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 1 },
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 7 },
        { "type": "no", "source": 1, "target": 2 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 8 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 3, "target": 8 },
        { "type": "no", "source": 3, "target": 9 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 4, "target": 10 },
        { "type": "no", "source": 4, "target": 11 },
        { "type": "no", "source": 5, "target": 8 },
        { "type": "no", "source": 5, "target": 10 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 6, "target": 10 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 7, "target": 10 },
        { "type": "no", "source": 8, "target": 11 },
        { "type": "no", "source": 10, "target": 11 }
    ],
    "tunnels": [
        [0,1],
        [1,2],
        [2,8],[3,8],
        [4,10],
        [5,10],
        [5,7],
        [5,8],
        [6,10]
    ]
}

Two groups with MOSPF generated trees

1998

The problem with dense mode protocols

becomes obvious when MBone is flooded with tens of gigabits of traffic during an Internet2 member meeting in San Francisco.

Engineers start rolling out PIM-SM in response.

PIM-SM

Protocol Independent Multicast - Sparse Mode

Uses (like PIM-DM) the underlying unicast routing table, but introduces the concept of a rendezvous point (RP), or core,

and requires goup members to send explicit join messages.

Building the receiver tree:

A RP is configured for each group.
- Groups may share RP, but each group can only have one.
- RPs must be discovered by all routers through a bootstrap protocol.
Receivers send join messages to the RP.
- Forwarding state is created at each router between the RP & source.
- This forms a reverse shortest path three rooted at the RP.

{
    "nodes": [
        { "type": "core", "count": 1 },
        { "type": "other", "count": 6 },
        { "type": "member", "count": 5 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 1 },
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 3 },
        { "type": "no", "source": 0, "target": 5 },
        { "type": "no", "source": 0, "target": 8 },
        { "type": "no", "source": 1, "target": 2 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 3, "target": 8 },
        { "type": "no", "source": 3, "target": 9 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 4, "target": 10 },
        { "type": "no", "source": 4, "target": 11 },
        { "type": "no", "source": 5, "target": 9 },
        { "type": "no", "source": 5, "target": 10 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 6, "target": 10 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 8, "target": 11 },
        { "type": "no", "source": 10, "target": 11 }
    ],
    "tunnels": [
    ]
}

PIM-SM Reverse Shortest Path Tree

Sending data:

Each source initially sends multicast data through a unicast tunnel to the RP (“register” packets).
If the RP have forwarding state for the group (ie receivers), data is forwarded down the tree.
If not, the RP may tell the source to stop transmitting.
In addition, the RP may request multicast data (without tunneling) from the source.

{
    "nodes": [
        { "type": "core", "count": 1 },
        { "type": "other", "count": 6 },
        { "type": "source", "count": 1 },
        { "type": "member", "count": 4 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 1 },
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 3 },
        { "type": "no", "source": 0, "target": 5 },
        { "type": "no", "source": 0, "target": 8 },
        { "type": "no", "source": 1, "target": 2 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 3, "target": 8 },
        { "type": "no", "source": 3, "target": 9 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 4, "target": 10 },
        { "type": "no", "source": 4, "target": 11 },
        { "type": "no", "source": 5, "target": 9 },
        { "type": "no", "source": 5, "target": 10 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 6, "target": 10 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 8, "target": 11 },
        { "type": "no", "source": 10, "target": 11 }
    ],
    "tunnels": [
        [8,0],
        [9,5,5,0],
        [10,5],
        [11,10]
    ]
}

CBT

Core Based Trees

Similar to PIM-SM, but:

Uses a single tree for all groups, resulting in less state to maintain at the cost of less optimal trees.

The tree is bidirectional, meaning that traffic from source to RP can be sent down the tree by any node. This avoids the same packets traveling in both directions at the cost of slightly higher complexity.

Further problems with MBone

Multicast networks have had a flat topology, built out of tunnels between nodes in different ASs, leading to a number of problems.

Scalability

Large number of routes became a big problem for MBone, peaking at over 10k routes.

To manage larger networks, route aggregation and hierachical routing is needed.

Manageability

Lack of central management and formal procedures resulted in many cases of sub-optimal routing, such as a high number of tunnels routed over the same link.

There was no protocol to manage information across domain boundaries, causing routing problems to spread throughout the topology.

Interdomain Multicast

Three main problems:

Multicast routing,
Source discovery,
Interdomain tree construction.

MBGP/PIM-SM/MSDP

MBGP

Multiprotocol extensions to Border Gateway Protocol

Allows multicast routing across domains by exchange of reachability information.

With MBGP each AS advertises the set of routes it can reach with associated costs. Border routers can compute the set of ASs to traverse to reach any given network.

MBGP does not carry information about groups or sources, only reachable multicast-enabled networks.

MSDP

Multicast Source Discovery Protocol

Representatives (a RP) in each domain announce active sources.

Information is flooded, and each receiving peer uses RPF checks to avoid loops.

PIM-SM (again)

PIM-SM can be used in order to join multicast trees in other domains.

A RP is needed in each AS, serving receivers within the domain.

Additionally, the RP functions as a PIM receiver:

When a source is advertised, a join message is sent towards the source if the RP has any members for the group.

Once data is received from the source, it is forwarded down the local shared tree.

Remaining problems

Join latency

SA messages are sent periodically, resulting in significant possible delay from a when a receiver joins to they get the first packets.

This may be solved by having MSDP peers cache SA messages, at the cost of extra complexity.

Bursty sources

Sources sending short bursts of data with several minutes of silences.

The original packets may never reach receivers since forwarding state may not yet be established.

Established state may be dropped between bursts due to timeouts.

The result is that no packets ever reach group members.

Scalability

MSDP may not be particularly scalable given it’s flooding strategy.

A few thousand active sources would result in a large number of SA messages (with embedded data).

It was still seen as an acceptable short-term solution at the time.

Long term solutions

BGMP

Border Gateway Multicast Protocol

Based on the idea that there is a single logical root domain for every group.

Constructs bidirectional trees that are shared between domains and using a single root.

A strict address allocation scheme is needed to avoid interdomain dependencies.

RAMA protocols

Root Addressed Multicast Architecture

Attempts to make fundamental changes in the multicast model in order to address issues such as security, billing and management.

The premise is that most applications are single-source or have an easily identifiable primary source.

This source acts as the root of the tree, eliminating the need for RPs.

Express multicast

is a single source protocol, which places the root of the tree at the source.

Group members send join messages along the reverse path to the source.

Specifically designed for subscriber-based systems, such as TV broadcasts, and allows closed groups with low routing complexity.

Simple multicast

is similar to Express Multicast, but offers multiple sources per group.

One source must be chosen as primary, and the tree is rooted at this node’s closest router.

Receivers send join messages to the primary, constructing a bidirectional tree.

Additional sources send packets towards the primary, but traffic is routed down the tree as soon as it reaches a participating router.

Layers of multicast

IP multicast

{
    "nodes": [
        { "type": "orange", "count": 4 },
        { "type": "member", "count": 6 }
    ],
    "links": [
        { "type": "ip", "source": 0, "target": 6 },
        { "type": "ip", "source": 0, "target": 5 },
        { "type": "ip", "source": 1, "target": 7 },
        { "type": "ip", "source": 2, "target": 7 },
        { "type": "ip", "source": 2, "target": 9 },
        { "type": "ip", "source": 3, "target": 4 },
        { "type": "ip", "source": 4, "target": 6 },
        { "type": "ip", "source": 4, "target": 7 },
        { "type": "ip", "source": 4, "target": 8 },
        { "type": "ip", "source": 5, "target": 7 },
        { "type": "ip", "source": 5, "target": 9 },
        { "type": "ip", "source": 5, "target": 6 },
        { "type": "ip", "source": 6, "target": 7 },
        { "type": "ip", "source": 6, "target": 9 },
        { "type": "ip", "source": 7, "target": 8 },
        { "type": "ip", "source": 8, "target": 9 }
    ],
    "tunnels": [
    ]
}

DVMRP, MOSPF, PIM-DM/SM, CBT

“Native multicast”

High cost of deployment.

Application layer

{
    "nodes": [
        { "type": "orange", "count": 4 },
        { "type": "other", "count": 6 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 5 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 4, "target": 6 },
        { "type": "no", "source": 4, "target": 7 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 5, "target": 9 },
        { "type": "no", "source": 5, "target": 6 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 6, "target": 9 },
        { "type": "no", "source": 7, "target": 8 },
        { "type": "no", "source": 8, "target": 9 }
    ],
    "tunnels": [
        [0,6,4,3],
        [1,7,4,3],
        [2,7,1]
    ]
}

End System Multicast, NICE, ALMI

Offers ease of deployment and moves intelligence to the edge of the network.

Overlay multicast

{
    "nodes": [
        { "type": "orange", "count": 4 },
        { "type": "member", "count": 2 },
        { "type": "other", "count": 4 }
    ],
    "links": [
        { "type": "no", "source": 0, "target": 6 },
        { "type": "no", "source": 0, "target": 5 },
        { "type": "no", "source": 1, "target": 7 },
        { "type": "no", "source": 2, "target": 7 },
        { "type": "no", "source": 2, "target": 9 },
        { "type": "no", "source": 3, "target": 4 },
        { "type": "no", "source": 4, "target": 6 },
        { "type": "no", "source": 4, "target": 7 },
        { "type": "no", "source": 4, "target": 8 },
        { "type": "no", "source": 5, "target": 7 },
        { "type": "no", "source": 5, "target": 9 },
        { "type": "no", "source": 5, "target": 6 },
        { "type": "no", "source": 6, "target": 7 },
        { "type": "no", "source": 6, "target": 9 },
        { "type": "no", "source": 7, "target": 8 },
        { "type": "no", "source": 8, "target": 9 }
    ],
    "tunnels": [
        [4,7,1],
        [4,3],
        [4,6,5],
        [5,0],
        [5,9,2]
    ]
}

Scattercast, Overcast, RMX, AMCast, OMNI

Somewhere between, where some nodes act as gateways.

Offers more flexibility and lower cost of deployment than IP.

Comparison

Metric	IP	ALM	OM
Ease of deployment	low	high	medium
Multicast efficiency	high	low	medium
Control overhead	low	high	medium

Thank you

Slides

aigjermo.github.io/multicast-presentation

Source

github.com/aigjermo/multicast-presentation