Pim

An Architecture Stephen

Deering

(Xerox),

for Wide-Area

Deborah

Estrin

Ching-Gung

Liu

Multicast

(USC),

Dino

Farinacci

(USC),

Liming

Wei

Abstract

The multica.st

routing

within

regions

width

is universally

senders

to

across

a wide

ets

where

mechanisms

a group

is widely

plentiful.

those

group

area,

or membership

report

group

are

schemes

intended

for use

represented

When

members,

these

were

sparsely

distributed

are not

information

and

efficient;

data

many

links

that

use within

These

sent

do

efficient;

data

respectively. trees

distributed. control

data

This

paper

internets. dent

We

particular

tify

the

betical

toward groups.

ing

traditional

and data and fort.

bugs

Estrin,

each

of the

receivers

for

address

as the

More

recently of his

Liu,

Foundation

the need to protocol and

Wei and

for

dependent

on

it seems appropriate

authors,

as a mean

effort Liu

who

shortest development supported

idea of

and

listed of

and effort,

supporting

and

path distribution as part of hls by grants

from

in

iden. alpha-

several Wei

more

likely

branch (e.g.

dist ante-vector to

the

the

packet

are of the

processto

deliver

multicast

case of link-state

on a subnetwork attached to that router

the

domain’s

topology

ing

protocol.

Upon

uses the information the

packet’s

re-

[5]

packet

be able

the

it

be-

to splice

A multica.st to

extension

existing

to

OSPF),

a RIP-

an extenis executed

delivery

changes

paths

of group

by one and that an

of the router

and

unicast and

routing image

link-state data

the

shortest-path to its

memrouters broad-

in the same up-to-date

a multicast

subnetwork

procedure

grows,

extension

routers

information

for

directly

forwarding.

protocols,

to determine

join

packet

the

their

group

protocol

maintains

send

is used

or MOSPF,

are detected subnetwork,

receiving

source

all

and

tree.

an

protocol,

through

topology

reach

will

an

to all other

Each

to

on

distribution

data

the information

router

receiver

multicast

that

non-member—to

as the

unica.st

of

use

of senders

protocol

of

Deer-

collection

simply

receiver-initiated

unicast

link-state

[6],

or

form

by

the

of a packet

DVMRP,

to construct

to

of members

of the

protocols

from

estab-

established

separation

a new

unicast

domain

126

that in

ship

is to de-

order

Senders

properties;

protocol,

casts

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. SIGCOMM 94 -8/94 London England UK (D 1994 ACM 0-89791 -682-4/94/0008..$3.50

work

group.

address

This

scaling

a nearby

In the

National

in

model,

existence

routing

bership directly

Microsystems,

data

membership

the

good

critical provided

occa-

receivers

in terms

and

host—member

subnetworks.

very

to accomplish

Farinacci,

not

or all members

is assigned

The

group

learn

on routers

trees (SPT) simulation ef. the

any

attached

sion

sparse

) are to

efficiently

network

group.

group.

A

to

address

destination

of the

has

like

join

some

of the

1P multicast

allows

comes

any

protocols

Est rin, fixed

to

sending

supporting

of Deering,

identified

implementation

are

original

architecture

were Sun

Indepen-

of this

is measured

entire

a multicast

a group.

onto

the

sources

detailed

as part

routing

inter-domain)

as Protocol

is not

list,

proposed

The

to support contributed

Science

by

as a collaborative

Jacobson.

it

efficiently (and

when

dis-

are

or member-

MOSPF

that

group are

schemes

not lead

purpose

members

a rntdtica.st

[2],

routers

protocol.

discovered

developed

approach

because

Jacobson

messages

protocol

the

for

wide-area

of this author

played

order.

multicsst were

to

routing

length

the roles

span

(PIM)

unicast

architecture

that

refer

Multicast

0 Given

an

groups

of

do

processing, the

to the

when

members,

Background the

ceivers

describes

across

packets

1.1 In

message

required

intended

However, these

case

Efficiency

were

represented

architecture even

DVMRP

of DVMRP)

that

The

distribution

ing

the

links

lishes

to

to multicast

(in

routing

state,

case

by

and

is widely

group area,

the

many

a multicast

sparsely

those

(in

velop

schemes

a group

existing

proposed

in MOSPF

a wide

information

or senders,

Introduction

across

over

complements

plentiful. to

packets

sent

members 1

where

senders

sparsely

report

(LBL),

as those

multicaat

regions

and

sionally

here such

implemented

traditional

tributed ship

proposed

is universally

members,

not lead to receivers or senders, respectively. We have developed a multicast routing architecture that efficiently establishes distribution trees across wide area internets, where many groups will be sparsely represented. Efficiency is measured in terms of the state, control message processing, and data packet processing, required across the entire network in order to deliver data packets to the members of the group. Our Protocol Independent Multicast (PIM) architecture: (a) maintains the traditional 1P multicast service model of receiver-initiated membership; (b) can be configured to adapt to different multicast group and network characteristics; (c) is not dependent on a specific unicast routing protocol; and (d) uses soft-state mechanisms to adapt to underlying network conditions and group dynamics. The robustness, flexibility, and scaling properties of this architecture make it well suited to large heterogeneous inter-networks. over

4].

or bandwidth

pack-

are occasionally

[3,

Jacobson

mechanisms

in [1, 2] and

for

Van

(USC)O

routing

Deering

or band-

members,

(cisco),

architecture

multicast Existing

Routing

packet,

group

of

routthe

membertree

destination

(SPT) group

[WR3’”) ‘\

$

\_/””

-------

J’ Domsin {,

‘

B

1

f

/’

““i.::._~

(a)

Figure

members. major

Broadcasting

factor

larger,

The

Dijkstra

other

major

the

thus

limiting

delivery

no

forwards

the

incoming

incoming

interface

arriving the

data

packet,

term

Reverse-Path

router

to

stream

toward resulting

leaves

still

to

routers process groups.

that the

nected

not

subsequent particular

has the

been MBON

the

members

packet.

Pruned

branches

branches members

and

cast

groups

densely

of the

number number

particular

of

of

packets

the

formation

ad-

anyway.

sparsely

multicsst

with

The

pruning

of

municate

are

distance-vector deployed

in

still

have

packets,

and

of

its

all

schemes

by using unicsst parent information

reduce

the

routing protocol [2, 4].

number

of

occasional

information

outgoing

inte~aces

sets,

and

measured

links,

i.e.,

in

state,

multicast only (inter)

storage

and

reports

needed

in

of our

that groups

multi-

also

that

are

have

processing (link-state),

since

most

the

parts

proposed

will

When

network

is warranted,

are

rout-

when

of interest.

the

bandwidth,

work

efficiently likely

in-

of the is to

support to

be

most

inter-networks.

types

then

group,

the

entire

in

local

be

further

to the

to keep track of child-

cast (CBT)

127

stabilize

far

time

we have

be all

prune that

int ernet.

such

A those

periodically,

[10]

send

that

and

to

do not

the

with

the entire

to

throughout

sites

illustrated

If a

as DVMRP

starts

broadcast

messages

the

are no other

in the

domain

wiU

com-

of a particular

distri-

bold

source’s

internet

lines

packets when

the

by contrasting

it

out.

motivated

our

design

densely-distributed-membership

protocols.

protocol

to

throughout

branches

traditional

send

However,

broadcast

routing

in

packets wilf

pruned-off

broad-

mechanism

of the that

There

routing

Subsequently

1(b).

domains. active

members will

domains

is a member

of the

internet.

tree

inadequacies

three

currently

a source

data

the

are

There

in each group

when its

figure

will

con-

I iUustrate There

1P multica.st

the

bution

active

figure

an internet.

of this

Thus 1 some

and

network in

emphasis

and tree

G, located

have

protocol, regions

is

properties the

protocols

in

via

is used,

to

schemes,

multicast

hundreds

However,

is likely

for

sender

distance-vector

packets

mechanisms.

traditional

branches

of

membership

distributed

examples

existing

having

tree

the

The

Overhead

1.3

back”

packets

of

size

Overhead

in

internet,

all

destinations

delivery

of the

or links

in wide-area

members

truncated-broadcast

be evaluated

mes-

be pruned

group

data

multicast

prevalent

can

(distance-vector)

develop the

on up-

members,

multicast

to

issues

size

scaling

populate

then

network

within

wide-area

scaling

the

in routers

broadcasting

or

of destinations

of distance-vector

area:

protocol groups,

and

good

subnetworks

members,

group,

total

E [9].

have

overhead

“grow

data

schemes

or data

prune

again

scale

of groups,

bandwidth.

link-state

the

present

will

will

and

of

tree

to

numbers

with

members.

consumed

ing

group

of

group

of resources

most

growth

number of

Existing

if the

message

The

groups,

processing,

a router

to group

of

terms

avoid

packet

a prune

leading

size

overhead

interface

When

capability

larger

to the wide

of a multicast

of its

distribution

the

thus

a data

scalability

terms

no mem-

source

shortest-path

these

on the

periodic

One by

of the data

the

case

are not

the

DVMRP,

the

of any the

no send

The

group.

Internet, In

carry

the

with

members

be small.

will

no multicast

sent

greater

group

finds

it

branches

period;

are still

being

the

if it

members.

Compared

to

tree

a time-out

if there

group,

[8].

multicast

router

Also

the

receives

Extending

1.2

Path

to

with

dropped;

(RPF)

subnetwork,

are sparse.

receiving

is used

to

of which

[7],

except

through

is silently

in a source-specific

having

after

packet

the source the

come packets

many

its

much

com-

the

broadcasting).

not

send

subnetworks,

sages prune thus

to

and

to a group

interfaces

mechanism

Forwarding

a new

all

truncated

data

a leaf

attached

out

to leaf subnetworks

does

uses

the

to

dressed its

(aka

packet

that

attached

packets

group

data

packet

1. A special

of data

a router group,

limits

supporting

construct

the

severely

networks

basis.

is sent

behavior

larger

sources

and

about

casting

to

of the

of Reverse

packet

Trees

do-

to

protocols

subnetwork,

knowledge

the

cost

wide

variants

data

in

multicast

routing

first

receive

performed

active

using

scaling

processing

on an internet

the

source

has

in that

all

trees

When

a particular

forwarding

is the

multica.st

[8].

packet

bers

for

distribution

Forwarding

group

calculations

applicability

Distance-vector multic~t

this

factor

trees

its

must

every

of Multicast

is one

from

router for

1: Example

information

multicast

information

shortest-path-tree

pute

from

membership

link-state

networks—every

membership

main.

of

preventing

wide-area,

store

(c)

(b)

More

recently,

was proposed

the

to address

1P multiCore

Based

similar

Tree scaling

----~.... ---Y 300 Groups in each network

In 50-node networks

—

SPT

------

Cenler+ased

N

#+

J-——___

N&vi4Nod:

8

3

7

12

t&worf

Deg:w

2: Comparison

of shortest-path

well

delay.

optimal

simulated number

To

get

core-based an

optimal

delay

graphs

of different

random

within

maximum in figure

ferent

50-node

domly. based

It can be seen trees with optimal

of the

shortest-path

trees

interactive

applications

For it

delay

is desirable

longer

delays

With

versus For

to

node

degree,

10-member

that core

link

of the

within

the

ber and figure that

and

very

well

under

may

be better

may

perform

sources

teleconferencing)

port

both

the

max-

group in

500

chosen

better

members

shortest-path core-based

potential

low

latency

PIM,

ran-

the

receivers

can

could

even

trees

to

damental

avoid

significant

the

2 Note not

that

1, there symmetric,

although are for

no

some real

more

data details

error

traffic bars

points

sources to

rate

SPT(S)

(e.g.,

real

flexibly

multica.st

sup

architecture, a configuration

the

two

issues

of broadcasting the

internet,

good-quality

described

packets and

when to do so

distribution

trees

for

or

group

a group-shared make

this

choose

can tree.

choose The

decision

different

to

use

shortest-

first-hop

routers

independently.

types

of trees

of

A for

re-

different

B capability

to support

difference protocol

different

between

PIM

engineering

and

tree

types

CBT.

is the

There

differences

fun-

are other

as well

4.

tree. concentration

3A more complete

prob-

4 Two

below

data

while

becomes

populate

a multicast

trees

is critical,

overhead

supports

path

sources.

type trees

applications.

dif-

ceiver

rate

one

types

other shared

of low

be ideal

address

sparsely

that

the

ad-

perform

protocol.

to

the

data

their

may

example,

numbers

within

a multicast

while

would

of tree

have

applications),

high

of trees

avoid

a way

large

It

3.

is designed to

In

for

networks

experiment

of tree

For

discovery

selection

within

The where

types

for

the

averaged.

in this

types

type

of conditions,

well

three and

were

from

tree

situations.

suited

heterogeneous

of the

maximum

very

between

flows

on

num-

concentrations.

both One

class

resource

be

PIM

with

one

were

flows

generated,

measurements

traffic

active

maximum

degree

were

It is clear

that

in other

time

decision

us

the

node

the

greater to

may

the

of

~00

of traffic

of traffic

disadvantages.

(e.g.,

so that

each

degrees.

exhibits

is evident

number

networks

a plot

node

vantages

For

generated

were

32 members

recorded

number

shows

CBT It

above:

tree

maximum

the then

random

randomly

there

of which

measured

network.

different

in

network,

members,

network,

500

2(b)

with

each

40

We

eight,

measured

2.

the

to the

each

we

we tried

groups

senders.

simulations

In

having

also

large

ratio

all

tree

conducted

networks.

groups

the maximum delays of coreplacement, are up to 1.4 times

of an optimal

respect

use

the

center-based

we also

over

experimented show

shortest-path

each

with

measured

and We

cases,

and

50-node

of how

average

algorithm

We

group,

CBT

graphs

tree

degrees.

delay

2(a).

in

graphs.

each node

understanding

perform

core-based

of different

imum

a better

trees

trees

lem,

problems. CBT uses a single delivery tree for each group, rooted at a “core” router and shared by all senders to the group. As desired for sparse groups, CBT does not exhibit the occasional broadcasting or flooding behavior of earlier protocols. However, CBT does so at the cost of imposing a single shared tree for each multicast group. If CBT were used to support the example group, then a core might be defined in domain A, and the distribution tree illustrated in figure 1(c) would be established. This distribution tree would also be used by sources sending from domains B and C. This would result in concentration of all the sources’ traffic on the path indicated with bold lines, We refer to this as trafic concentration. This is a potentially significant issue with CBT, or any protocol that imposes a single shared tree per group. In addition, the packets traveling from Y to Z will not travel via the shortest path used by unicast packets between Y and Z. We need to know the kind of degradations a core-based tree can incur in average networks. David Wall [11] proved that the bound on maximum delay of an optimal core-based tree) is 2 times the tree (which he called a center-based shortest-path

Ncd;Degr~e

(b)

(a) Figure

1

Tree

in

below

the 1 —

delay the

graph distribution

1,

extend is

obvious

Soft uses

see [12].

ery

128

state explicit of control

analysis

engineering

versus

of these tradeoffs tradeoffs

explicit

hop-by-hop messages.

reliability

mechanisms As

can be found

m

[12]

are:

described

mechanism: to

achieve

in

the

next

reliable section,

CBT delivPIM

1.4

Paper

In the sign 2),

remainder

describe

to interoperate

of this

paper

we enumerate

the

for

wide-area

multicast

routing

requirements

ments

2

organization

a specific

(sections

3),

protocol

and

discuss

specific

for

realizing

these

open

issues

(section

had

de-

In support

of this

require-

ticaat,

in support

4).

this

design

objectives

in

mind

when

and

bers

of receivers,

ration

of roles

The

designing

Sparse

Group

We define

a sparse

group

ber of networks/

domains

is significantly

smaller

domains

in

area

is too

that

the

with

than

Internet,

(b)

large/wide

(c) the

inter-network

ciently

resource

group

the to rely

schemes.

Sparse

therefore

we must

groups

numbers

of receivers.

the

are

support

on scope

not

is not

suffi-

In this and

of current with

High-Quality

As

We

wish

low-delay

needed

by the

application.

posing

a single

shared

forwarded dent

give

were

(a)

and

tree

on a single sources

the

shared

tree

Routing The

(SPTS)

Protocol

protocol

1P multicast

simultaneously

tree,

or (b)

destinations

significantly

traffic the

shorter

time

rely

to adapt be

is

protocol

of

accomplish

make

use

of how

of the

those

changes,

the

this

unicast

particular

by

letting

unicaat

tables

link-state

interoperabfity multicast

inter-domain.

For

of a distribution 1P multicast PIM.

additional

tree protocol,

In some

routing, example, may and

cases it will

protocol

traditional

both the

be necessary

or configuration

intra-domain

point(s)

(RPs)

RPs

used

are

and

multicaat use

receivers senders

downto re-

tree. tree

construction rendezvous

“meet”

new

announce

about

(or

per-group

to

to

to learn

local

as

data

messages

distribution

1P

by

such

multicast

prune

must

a

multicast,

without

PIM

join explicit

and

mode for

by receivers

shortest

portion

protocols

and

(G),

to impose

other

the

some

means of reliability. This the protocol and covers a failures in a single simple can introduce additional

by

new

warding

entry

state

sources.

their

existence

senders

of a group

set

(oif),

right

information

keeps,

except

source

address.

Figure

interface. keeps

that

joining

ceiver

wants

it

We denote

saves

such

information

the

RP

is a wildcard

address flag

a simple

join

a PIM

scenario group

via

multicaat

5 we ~i~~ di~cus~ how Rps are selected 6 The oif’s and iif’s of (S ,G) entries shortest path tree rooted at S.

129

aa the

(iif)

multicsst

. for-

can match packets from any if the packets come through

same

a multicast to

addre~s

interface

an entry an

(S,G)

in

place

indicating

(*, G). entry of

that

the this

entry.

3 shows

sender

the

There

tree

1P multicast

multicas.t

incoming

is

is cur-

(S, G).

incoming entry

(S),

routers that

existing

source

entry for a shared tree for its associated group,

(*jG)

in

information

running i.e.,

forwarding for

maintained

forwarding

routers

interface

to this

is a shared

2. Incoming interface check on all multicast data packets: If multicsst data packets loop, the result can be severe; unlike unicast packets, multicsst packets can fan out each time they loop. Therefore we assert that all multicast data packets should be subject to an incoming interface check comparable to the one performed by DVMRP and MOSPF.

tree

as the

as MOSPF,

We refer

the

in order

such

outgoing

An source

by

path

same

maintained

and

A uses periodic refreshes as its primary approach reduces the complexity of wide range of protocol and network mechanism. On the other hand, it message protocol overhead.

dense

the

of

existing

by sending

1P

explicit

from

from

members

tree

routers

send

to

ways:

is assumed

until

tries number

differs

mode

on

establish as dense

a minimal

downstream)

dense

themselves

driven,

schemes multicaat

PIM

rely

to

mode

distribution

in

routers

fundamental

(or

protocols

groups,

5

portion

by some

overhead

local

protocol

routing

so that

in two

mode

data

The

RPF

the inter-domain

so

tables,

intra-domain

be established

on)

phase.

to such

sparse it.

PIM

of each

network

we refer

membership

whereas

multi-

are computed.

with

with

move

rently

require

schemes

members

in

Interoperability: We

point

baaed service

of the

populated

the

receive

are sent

roughly ●

(and

to state

serviced.

multicast

all

network

stream)

protocol

routing

soft

multicast

being

densely

contrast,

packets

at the

the

adapt

a single

with

description

distribution

messages;

routing but

the

DVMRP,

is existing

sepa-

senders.

avoiding

an overview

trees; In

join

shortthan

for in

sparse

2.

to topology

independent

We

independent

on

num-

logical

gracefully

to deliver

traditional

PIM

path

in the

with detailed

data

1! routers

are superior

Independent:

should

employed. caat

are

indepen-

in

tree.

functionality same

packets

the

the

1P mul-

large

by (a) using

along

are

a more

actions

the

routers

when

shared

and

are

data

service

constrain

when

tree,

(b)

packets

distribution

im-

data

to

this

adapting

we start

multicast.

we avoid

trees

send

poor

all concentrated path

which a common

sources

experience

between

distribution

Source-specific

lengths est

in

along

source.

multiple

would

data

very

and

able

changes

designed

driven

mode

In particular,

to receivers

of their

when

●

Distribution:

to support

(c)

routing

described,

which

large

data

Data

be

We achieve

and

section

efficient b

existing

Protocol

then

“small”;

groups

with with

receivers

should

as unicast

PIM

3

an and

necessarily

proto-

/

span

overhead

dynamic

long

present

control;

group

unicast

num-

of networks

members

by the

to ignore

the

members

number

group

spanned rich

(a)

routing

maintain

mechanisms,

of failure,

Support: as one in which

of groups

between

changes.

refreshment Efficient

interoperation we should

protocol

routing

architecture: ●

intra-domain

Robustness:

●

several

some

(section

Requirements

We

with

cols.

of an

a receiver RP.

the

its

first-hop

group, in section

in all routers

and

When

a re-

4 together

form

a

f 2. 3ender sends a PIM register to the RP} .. .,-------------------..-...----....................... ? 3. After receiving PIM r ister from~i ! fheso.rca. RPaendsa%M ioin : ‘“+

;

..

‘%,,%

Recx+iver

‘%- . ....................................... ..v

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

/ 1. Racewer sands a PIM jom toward the RP '\..:.!."!..Y!.:.P!!!

Figure

PIM-speaking sage

router

toward

cessing

one

of this

multicast

the

router

(D

in

piggybacked

group.

source.

The

on

RP

Processing

(there

responds

of these

source

in figure to the

rooted

router

message

ceived

for each

router

the

RP

new

One

the

or more

and

The

the

prune

i.e.,

one

will

address(es)

RP

The

to their

are

3.1

Local

another

local

sends

to

sending

to

then

be

one

a shared tree instead If shortest path trees grows will

bY checking

but

are very

the

possibility

very

sparse

report

Even

when outgoing

a new

sparse

about

such

which has are desired

large,

some

be needed; the incoming

the

less per-source then when the form

see section interface

of aggregation 4.

re-

numbers

average

support

is and

and

mode,

but

as MOSPF, In

this

case

or sparse

different

interfaces. added

description.

overnum-

a group

as dense these

data group

the

protocol

de-

a particular

From R,

this

(or

IGMP

point

on we

member)

of

the

s [5]

will

identify

RP

there

has are

mapping

using will

RP,

flag

allow

differential

For

the

sake

of clarity,

section

it

throughout

most

4 for

further

some

in

may

be

require mode

the

that PIM

scheme

variant

individual

to

IGMP

will assume sparse mode.

a dense

mode,

an RP

in

provided

do not mode

(i.e.,

as needing exists

the router with PIM

or a dense

router

group

provided

associated

handled

the

if there

interfaces

DVMRP

complexities See

an

incoming

a report address(es)

entries)

mapping

is no

RP

a new

multicast

by checking

no

receives

has

of PIM interfaces

treatment we of

will

the

of

ignore protocol

discussion

of

8 A de~ignated router ia the one that takes responmbdlty for serving the members on a mult]-access LAN, ‘The mechanism for learning this mappmg of G to RP(s) is somewhat orthogonal to the specification of this protocol; however, we require some mechanism in order for the protocol to work, At the very least this information must be manually configurable. We propose the use of a new host message that would allow hosts to inform their directly-connected PIM-speaking routers of G, RP(s) mappings. This is important for dynamic groups where hosts participate in spe. cial applications to advertise and learn of multicast addresses and their associated RP(s),

or

We selected

in it routing

4.

appropriate configuration file, then that the group is not to be supported some

sources’

is to

resource

router’s

to see if it

DR

support

there

messages,

or may

large

the

is very

(e.g.

identifying

(DR)

checks . A

G

mode

pres-

does

in figure

it has no existing

If

ques-

but

message

router

G,9it

with which

in

of receivers,

describes

as a receiver,

a designated

the

(e.g.,

a host

group

by

information

to be lower

to a directly-connected

a new

mapping.

connected

configured

of sources

a group

as shown

such

group

mechanism

distribute

If there

a group

with head.

mechanism

may

the

ap

than

G.

[13].

are

7~ knows,

with

number

tends

report

When

PIM

RP

IGMP

message,

associated

A sparse

directly

the

section

hosts joining

G, in response

for

initially An

network.

is identified

enumeration

of sources.

low,

the

protocol hosts

rates

of sources

PIM,

used

of this

A host

re-

routers).

explicit

enumeration

of sources

by

are

rate

anticipated larger

detail.

group,

group

toward

to receivers,

receiver’s

associated

used

avoids

in

information

through

message

the

using

(RPs)

sources

router that

join

mapping

be learned

PIM

in more

refer

to router

message

data

remainder

sign

query

first-

a PIM

packets B, then

when

and

is much

the

the source-

sending

data

a PIM

from

PIM-speaking

router

proxy

After

D to router

points

packets

of

ber

by

And

average

existing

the

the

joins

many

of receivers

discovery). for

from

are desired,

source

source. (router

rendezvous

data

PIM

quire

RP

the

in

number

of sources.

large,

routers

path

eventually

each

3 sends

ence

RPs

the

because the

number

register

toward

receivers

tradeoff

one for

group,

IGMP

for

path

B in figure

be any

tion.

the

7.

to propagate mode

a join

delivery

trees

member

tree

toward

on the

A),

can

distribution

distribution

join

a packet

placations,

RP(s)

by intermediate between

this

Pro-

first-hop

the

with

mesup

a PIM to

rendezvous

When

the

sends

sending

messages

up

sets

receiver.

packet,

by

join

group,

group,

3)

routers

3) sets

the

senders

RP(s).

If source-specific PIM

to

data

the

routers

RP

figure

a PIM

for

multicast

the

are no intermediate

source hop

the

to

PIM-speaking that

from

sending

3: How

3) sends

advertised

by intermediate

branch

start

message,

in figure RPs

message

tree

sources

(A

of the

‘)

.!Rrn..R?.!?:!.!:.!:.:!::!!:!/'

table,

that it is at a point where the shortest path tree and the RP tree branches diverge. A flag, called SPT bit, is included in (S,G) entries to indicate whether the transition from shared tree to shortest path tree has finished, This minimizes the chance of losing data packets during the transition.

130

............................................ . .,.

........ ........................................,

\“

f 4. Send PIM message to B:\ ~ “5 G , Multieasl t address= -----

Create (*,G) entry: Multicast ddmss= ..-. ..-— .—--. ..—

{,.

:$;%!;%%? Iii;={,)( incoming intertaee = {3} RP-Time~ Started

H!Hc:fil!lwctit}

r

~ +

“\,

““

\

.......................,,:/j

LAN

{I.

Receiver

o-

;

IGMP

‘\_..y!’V ~.......(o )/’/

\

‘~~”iGMp--.) :, ‘ report G,; .... . ..............

~ Lh&gfited

a single direct the

‘\.

4:

Example:

how

a special

new

terface

bit

this

in

over

The (*,G)

The

DR

sets

router

being

in the

from

new

RP

10*

IGMP

discuss RPs

address

the

the

in

join

later

is included

so that

The

outgoing

report

will

is set

to the

RP.

is set,

to

RP-timer

for

WC

entry.

the

RP-rooted a PIM

with

join

the

list.

shared

RP

The

WC

with

that

the

receiver

sources

via

this

bit

flags

shared

expects

(shared

bits

to

tree)

the

The

an

is

RP

recognizes messages

in the

tree.

The

receive path

down

allows

downstream

become

indicates

that

RP

there-

RP.

the

PIM

of outgoing upstream

a PIM

The

with

router

join

packet

interbe-

message

in

payload

con-

WCbit

},

the

own

address

this

entry

(*,G)

entry

routers

unreachable

is set

by

tree

and

RPs

to detect

not The

to

null.

attempt incoming

RP

periodically

established

and

does

upstream.

for

the

when

triggers

dis-

group.

their

joining

reachaand

This

current

RP

toward

an al-

to shortest

path

RP.

shared

a PIM-speaking

tree

router

(RP tree)

paths,

sourced

by an address

cast SPT

bit it

next

entry

(Sn,G). that

been

completely

not uses

PIM

join

the the

shared (Sn,G)

message

toward

the

When cleared, the

131

interface

shortest setup,

to get

which

to receive used

to reach

5, router

path and

are

a multi-

(Sri, G), tree in

packets

be

source,

sent

A

with

branch

the

from

upstream

Sn, with

PIM-join={Sn},

a router starts

G that

have

for

with

mean Sn.

A

entry. will

new

Multicast-address=G,

tree

for

not

has

group

in figure

entry

the

which

the

packets

it does

forwarding

tree,

join

As shown

indicating

has

to

data

which

cleared still

hop

notices

Sn for

multicast

is set for

A

face check for that entry should be the RPF interface to the RP, not to the source. PIM prune messages with the RP bit set cause this blt to be set in the associated forwarding entry. The RP b]t in an (S,G) entry indicates that periodic PIM join/prune should be sent toward the RP

router

a shared

wants

a new Sn

timer

‘nter-

the

forwarding

from

on

members,

shortest

initiates

PIM-

the incoming

the

(*,G)

Switching from tree (SPT)

time entry

each

sends

generated

directly-connected

NULL. ~p bit in ~ forwarding

its for

are

tributed

When as

routers should create or add to (*,G) for10 . The pIM join message payload contains PIM-join={RP,RPbit,WCbit},

entry

RP

join

which

on list

multicast

ad-

packets

and

the

its

a PIM

PIM-join={RP,RPbit,

RP’s

messages

has

nothing

address

includes

to send join btity

for

RP

list

the

uDdates

receives

interface to

on this

and

or it

The

is added

Based

receiver

interface

timer

set;

set.

Multicast-address=G,

3.3

with

WC

bits

when

PIM-prune=NULL.

tree

message and

(*, G).

tains

that

is received

for

creates

(*,G)

arrived

be

A wildcard

The

message

RP

message

tree

router for

and

ternate

associated

entries

this

reachability

shared

umtream

the join

in-

indicating

occur

which

from the

up

in

interface

was received

interface entry

it

sets

the

3.2).

list

“’

G

RP-addreaa. C outgoing intetfaee tist = 1} incoming mtertaee = NU 1-L, ./.

they

tween

a multicast

entry,

packets this

that

MuIticast-address=G, prune=

the

RP

prune

upstream

warding

RP

incoming

creates

its

indicates

fore

We

multiple

messages.

with

an

and order

faces

unicast

an

time

‘y’”:;:$’:j~tg=

~ , ~ JI

forwarding-entry

assume

entry.

in its join

is listed

also

4) creates

forwarding

The

Establishing

dress

clarity.

with

. The

join

which

(see section

3.2

of

we will

A in figure

the

to send

DR

each

sake

(*,G)

associated

is a (*,G)

reset

for

member. used

(WC)

joins, in the

3.9.

router

record

description

operation

in upstream

is set to that the

the

to

cache

included

bit

for

(e.g.,

forwarding

a receiver

are numbered

Each

of this

in section

DR

\

................................................

For more details about IGMP query and report messages, seeRFCI112.

issues.

just

document

Rendezvous Point (RP) for group G

~6. Send PIM message to C“, Multicaat address= G ~ JOIN= C, RPbii,WCbti} ! ,/’ \ PRUN i = NULL . . ......................................... . .

extensibfity

The

2

‘>: jz3. Create (*,G) entry: Multicest address= G ; RP-addreaa = C outgoing interlace Iiit = {1 } i incoming intertaee = {2} I ‘\. RP-timec Statied . . ........................................... /’

remainder

RP

n

,-- ......................> ...............

practical

I

Router

Actions

the

~ ,,

Source ‘“

% .. ............................................

Figure

very

----1

i

(+)

For

‘“x..

1

1,

these

~., \

/,’

Hoat

!

‘“”/ \

“ ~

~

‘1 ~

G

has packets

the

best

Sn in the join

to

list:

PIM-prune=NULL.

a (Sn,G) from

entry the

Sn, it sets the

new SPT

with

SPT

source bit,

and

bit

Sn on sends

... ........................................... .. Multicast address=

G

:

/

i

i /’

LAN Receiver

;

/’

\

/!’ ,/

“\

2

1

Rendezvous Point (RP) for group G ~ Designated Router

\

\ tiLN I 4 ....................... . . ................... j’1. Create (Sn,G) entry: ‘] Multicast address= G ; Source address. Sn outgoing interfaca list= (1)1 incoming interface = {2} ,) .. ..............................................

Figure

5: Example:

Switching

Actions

a PIM

prune

differs

from

cating

that

RP.

In

toward its

RP

if its

shortest

path

it no longer

wants

the

PIM

message

shared tree

tree

to receive

toward

incoming

it

When

the

list

is copied

are

replicated

when

(Sn,G)

all

along

this

the

i.e.

new

packet

will

unless

all

the

local

shortest

from

receivers path

is created,

(*, G),

in

a data

entry,

entry

from

Sn

arrives

continue

and

the

that

cache

time).

an (S, G)

a DR

entry

toward

from

the

may

outgoing tree

tree.

In

interface

of PIM

branches

ment;

this

refresh

matches

receive

way

on

source

the receivers

(and

therefore

the

source)

source

within

would

eliminate

stream

when

the

small

adopt

some

numbers

data over

the

suboptimal

DR

may

also

distribution

packets

tree

interval of

distributed

of

3.5

choose

indefinitely

this

instead

ing

This

state

In

the

PIM

steady

messages

is en route forwarding (*,G) 11A

state

maintenance each

upstream

router

of

router

sends

may

be

RP

tree.

on

the

Re-

to each

of the

next

hop

to the

~egatlve

These

messages

cache entry

are sent

is a (S,G)

entry

refreshes routers

on the Rp

each

some

new

PIM

the

could new

depend

message

time

a new

(Sn,G)

be applied,

(note

e.g.,

a merge

contain

source.

only

The

the

delivery

on positive

acknowledge-

from

next

be recovered

at the

periodic

processing

packet

of that

and

if it

132

packet

all

(whose

the

timers

actions

that

continuously,

even

during

the

tree.

First,

when

with

does

not

match

the

incoming

is forwarded

to the

interface

a data

SPT

bit,

that

of the SPT Data

that

matches

(S,G)

entry,

to

interface

packets

which from

(S,G)

forwarding

prune

list

aa it

causee

PIM

message

in

a new entry.

in a triggered S to

then

turn

the

packet

the

trigger

that

source

can

PIM

messages in

source.

the

In

if the

addition,

with

a cleared

packet

matches

Data

toward

of a new

the in

may

particular

creation

list

and

packets In

S to be included join

the

entry;

is forwarded

trigger

causes

(*jG)

if

entry,

in (*, G)

prunes.

This

be included

toward

for

(*, G).

bit is set for that entry. packets never trigger prunes. actions

packet

bit,

the

of the

to

a data SPT

listed

of the

are

are

from

on an (S, G) entry

the incoming

There

transition

interface

interfaces

matches

packet

and

a cleared

the outgo-

if packets

according

outgoing

in the

expired).

introduced

entry

packet

not

existis per-

otherwise

listed

are

(S,G)

it is sent

path

have

to

check

is dropped,

an

the

shortest

similar

interface

interface

to

data

The RP bit is set, indicating that the associated prune messages should be sent up the shared tree toward the RP. In addition, the outgoing interface from which it receives a PIM prune message with (S ,G ) and the RP bit m the prune list, is deleted from the outgoing interface list Data packets matching the negative cache are not sent to that interface

the to

a manner

incoming

on

trigger

tree

fails

list

in

An

matches

the

to capture

processed

a shared

when

periodically

A

basis

message

not

will

are

exception

then

short-

to each source, S, for which it has a multicast entry (S, G); as well as for the RP listed in the

entry.

does

is forwarded

packet

state

periodic

may

PIM

schemes.

be delivered

sporadically.

of moving

for

about

data

interface

two

up-

shared

remain

the

packets

packets

i.e.,

state

function

multicast

packet

tree.

Steady

damping

changes.

time.

incoming 3,4

is established

messages

formed

mes-

packets

manner

of the to

join

(S, G)

event-triggered

entry

Multicast

ing

up

n seconds.

are sent

in

paths

setting

m data

sending

membership

an

to prune

a PIM

received

of packets

However,

of not

and

information

lost

tree

this

packets

choose

sending

it has

overhead

delivered The

a policy not

until

on

Optionally

Data that

sage

est path

sent

some

path

occur

topology,

also

forwarding

themselves. Note

to shortest

they

incremental

and

to

until

a negative

shared

path

is

Sn via

Sn in

tree

order

state,

indi-

from

includes

rune list, with RP bit set indicating that ?1 should be set up on the way to RP.

shared

in the

interface

interface,

packets

RP,

from

are numbered

incoming

. . . . + ............................................ ( 5. Affer receivin pscketa from Sn>~ Set (Sri, G)’s % PT-bit = 1, and ~ Send prune to C: ~ MultiCast address= G : JOIN = NULL PRUNE = {Sri} \ . ........................................................ /’

4 .....-—— .. ........................... ——-... j’3. Create (Sn,G) entry ‘1: MultiCast addreas = G ~ ~ Scurrx address= Sn ~ outgoing interface lists {1) ~ : incoming interface = {2} ; ,/ ,,, SPT-bii = O . .............................................Z

in the RP;

just

a triggered

Timers

3.6 A

timer

each

Unreachable

is maintained

(S,G)

terface

or

(*, G)

is added. is received

try

(S,G)

(i.e.,

face

is deleted

from

and

period

Certain a prune

from

LAN,

time

join

inter-

When

the

is sent

up-

3 times

the

after

list.

onto

the

is any

is the the

All

refresh

(S,G) sends

the

prune.

The

router

that

only

and

of hear

LAN

prune.

For on

hop

all

same

to

hop

are in the

then

joined

Unicast

When

routing

unicast

routing

affect ed multicast

RPs.

Sources

ular,

if the

interface its

incoming

it is deleted

The

PIM-speaking

new

interface

multicaat prune

or

RP;

the

join

“,

with

out

is going

in the

outgoing

list.

sends

a PIM

the

routers

join

routers

interface.

that

It

this

part

the

join

RP.

points

and

reaching

there

and

is one

receivers

a, reliability lZ ~hen

RP actually

then

there

being

is no

able

all

paths

to receivers.

the

an outgoing

interface

path

used

includes

for

the

group

registers

and

receivers

RPs

fails,

receivers

reachability of the

mes-

alternative

action.

via

in

if

the

receivers

distribution

established

at some and

folwill

receivers the

shortest-path will

will

be

to-

receivers source

are

to

reach

travel

new

receive

some senders.

is used,

most

path

to via

from

data

(S,G)

shortest source

to

Similarly,

re-

via

RP

packets

However,

data

the

the the

receivers.

up new

a shortest

distribution,

added

be delivered

continue to

to

paths from

arrive

will

packets

RP.

packets

to pick

over

will

propagated

source The

upstream

initiate

will

the

distribution

sent

packets

order

continue

in order

the

RP

have

from

established.

interfaces

data

packets

RP(s)

out

sends

a PIM

Open

the

when

packets

will

sourcearrive

at

tree.

Issues

Before

concluding

further

research,

●

we discuss

Interoperation

here,

scenarios

about but

sources there

listed

several

engineering,

open

issues

or experimental

with

dense

that

require

attention.

mode

networks

/

re-

gions:

distribution

is

or collection

whether or

dense

in

that

dense

bership

entry, we should also reset the interface timers for all (S ,G ) entries which contain that interface in their outgoing interface list. Because some of the outgoing interfaces in (S ,G) entry are copied from (* ,G) outgoing interface list, they may not have explicit join messages from the downstream routers. 13 Negative Cwhe entries on the RP tree must be kept alive by re-

flood

the

region

or

mode

or in

to

is high

membership

For

example, may

intra-domain configured 1SFor this

~e=on

or

as default

If

the

since

of

to operate group

mem-

is plentiful

multicaating in general

source WAN

to some link

aa default

intra-campus

then (RPM)

most

it or

links

destination.

or inter-domain

sparse-mode.

links

will

Most

probably

be

dense-mode.

we have also developed

scheme that uses DVMRP-like tocol independent [13]

133

mode.

some

member-

scarcity/availability

or bandwidth path

to

a distribution

sparse

an expensive

be configured

the

be able as described

group

be configurable

reports, from

join

of the

should

use reverse

be on a path

PIM

to

density on

should

mode

multicaat

on

will link

ceipt of Prunes. We do not want to delete such entries if (* ,G) entry exists; otherwise, data packets will travel down both RP tree and SPT. It may not result in periodic duplicates (because of the RPF check), but it does waste a )ot of network bandwidth. 14see [14], this address (224.0.0.2) is also used by routers to send PIM query packets to neighbor routers Q. the same LAN

mode

density

is efficient

of networks

use sparse

15. Links

bandwidth

in (* ,G)

to

depending

ships in

is ~e~et for

packets

receivers

and

4

outgoing

issue. ~ timer

messages

join

data

outgoing

receivers

it expects

RP failure

to rendezvous,

special

PIM

to the

entry

the

is operational,

of the

concern

list

but

one

to take

group,

is estab-

RPs, RP

to

RP,

the

the

tree, If

receiving

the

interface

source

the

If one of the

the

Multicaat

A network

rendezvous

each of

joins

messages

“upstream”

Data

away.

Multiple

need

receivers

PIM

choose 3.9

do not

distribution

to the

ceivers

and

message

that

if the link

sending

the

timer

In partic-

appears

the

the old interface,

upstream

is done

from

upstream

over

check

RP. stop

the

(S,G)

When

header.

are updated.

a single

for

P Reports

used,

RP

once

additional

or LAN

interface router

to inform

datagrams message

to inform tree

new

list,

an RPF entries

to

each

this

entry

interface

IGM

each

start

from

the

both

to a spe-

members

summary,

specific

changes

will

are

RP

a router

is reset If

(*jG)

set

outgoing

toward will

timer

A new

interface

RPs

reachabdby

Summary

ward

changes

forwarding

that

and

tree 3.8

toward

The

an alternate

The

RP

is received.

RP.

on which

packets

sages

before

same

IGMP

join

that

up

RP.

multiple

only

is set.

new

incoming

interfaces

data

travel

upstream

is sent the

the

new

received.

by the

override

source

on

looks

the

those

low

for

joins/prunes

the join routers

router

the

is established

message

toward

the

upstream

if there

list, to

to hear

own

LAN)

previous

the

others

their

reason

and

LAN

reachability

were

In

(S,G)

interface

go to single

we want

this

for

interface the

should

which the

of the

onto

suppress

address

prune

a timer

only

3.10

incom-

interfaces

incoming

members,

using

entry

remain

whose

message

outgoing

spe-

members.

outgoing

this

as its

previous time

its

a prune

prune

right

those

all

message

same

1P address

haa

has non-null

they

the

a router

routers

so that

multicast

when

a join

is the

prune

override

with

reach

When

receives

there

is used: multica.sts

join

whether downstream

has the

at the

detect active

LAN

and

router

require router

with

other

that

the

however,

lished

detected

a (*, G)

the a join

are

When

RP

sends to

subnetworks

configurations

it must

router

LAN.

router

the same

an

expires,

en-

message

a LAN-connected

routers protocol

iuterface

go to null,

the

interface

a prune

subnetwork

the

following

(and

a PIM

outgoing

on multi-access

When

downstream

cial

outgoing is null

is deleted

multi-access

other

and

in-

forwarding

corresponding

routers

consideration.

ing

time

that

the

when

wit h local

sends

PIM-speaking

The

the

the

entry

each for

in

‘3.

3.7

cial

is reset

is set

listed

12.

list

the

interface

timer

interface

expires,

interface

stream

timer

or (*, G))

outgoing

The

on that

a timer

outgoing

each

entry.

The

message When

for

RPs

it y message.

RPF,

but that

a dense mode is unicast

mUkicSSt

routing

pro-

The

primary

issue

a distribution sparse the

mode

data

join some

way

from

(or

dense

on getting

tion

to

the

send

explicit

A second trees

the

be the

entry

source,

and

border

routers

should

one

bers

this

to

In

that

informa-

border

data

join

case

it.

for the

the

value

(to

are

there

information

several

lists.

router

serving

in

PIM

message

One

size and

might

the

●

entry

PIM

message

very

coarse

routes

PIM

there

is

to

system (RDIs)

have

address

this

the

nism

for

propagating

send

appropriate

V. the

cloud.

externally When

In and

data

forwarded

the

for

threshold

exchange

for

unaggregatable

) (BR) join

to PIM

use

this

do

not

approach

efficient

to

and

map

this

case

refer

proxies

MOSPF in

scheme

BRs

would

themselves arrived, cloud

PIM

that

service,

data

routers

packet would

from

should

of

packets

to

anyway

the

RPs RP

most

for not when

will

not

receivers,

The

RP

un-

address

discovered

address,

information

of the

we need

be dynamically

query

The

by

of a direc-

obtained

messages.

with

data

SPT.

is the

associated

of the

for

be

members

there

because

multicaat

RP-report

Interaction

If

do-

aa well

clouds,

join

or can

or

their

path

any it

of one

Nevertheless,

used

be

to

overhead

to be on the

the

addresses

messages

via

mapping

some

of G to

be cached. policy-based

by

to

so long

and

PIM path

to

being

symmetric

If

tree

internally.

PIM

be

route.

see a new

134

there

may

same

as the

QOS

travel

extent

policy

routing: over

policy-

that

does

not

distribution

and

reach

register the

then

unicast prohibit

route

have

the

is an This

RP

or

joins travel

computed [17]

should

be sent

option

needs

for

source

is indi-

and

for-

carry

willing hop-by-hop multicast

be

as de-

that

two

does,

routing bits

set,

then

the

an embedded added

QOS

flag.

by

with

can

upstream that the downstream. This

and route to

indicated

routers

16] should

multicast

symmetry

SDRP

some

QOS

PIM-speaking

and

multicaat

chosen

messages.

[15,

flag

of

paths

appropriate

BGP/IDRP

message

the

if they forward will allowed to

generic not

the

consider

the

symmetry

the

but

that

to

join

as being

does

packets

policy-sensitive we need

cated

flags:

PIM

would

routes

termine that data packets

as

outside

a PIM

data

explicitly.

obtain

the

and

does,

traffic

warding

it

1P to

sources

as sources

the and

for

are

RP

local

placement

distribution

from

PIM

To

the

as suggested

within

to proxies

trees

can

router has

sending

with

happens

tory

implies use

to

the

to be delivered

members.

be configured

packets

(e.g.

in

from

path

this

the

prune

packets,

Ja-

However,

for

is no wasted

it needed

on the

routing

mecha-

requires

data

and

(S, *) entries

group

If an RP

concerned

constrained

travel

domain

advertisement

aggregation

internet.

convenient

there

to those

new

the

continually

since

remain

PIM

domain

domain the

●

(au-

will

protocol’s

within

and domain

routing

the

be

groups;

domain

the

message

default

PIM-speaking

shortest

RP

messages

or

and

mes-

routing,

is

may

RPs:

group.

then

mapping

aggregate

to

it

across

(Deering

multica.st in

and

sources RP

can

specific

PIM

large,

addressed

creating

entity

less it also

carry

cases.

address

m~lticast

is to

inject the

and

to

arrive

more

of the

in

of

will

very

authors

identifying

of the

group

with

to for-

respect

messages

fanout

1P

processing

only this

respect

the

PIM

member”

and

packets into

the

link-state

In

need

techniques,

in

of

only

a particular

efficient

delivery

where

numbers

However

Jacobson.

the

speci-

compromise

of state

of the

proposed

for

be overly

inter-domain from

the

possibility

messages

for

int&~

main address when control packets. Another

tree

grows

we have

and

RP

multicast

in most/many

Then

a “local possible

each devel-

problem.

Selecting

members

are

used

with

members

a source

router~s

use

is both

all

(AS)

can

of RPF).

on to

some

could

numbers

Two

directly-connected

the

issues

messages

when

possibility

).

BRs

case

new

protocol

to

receivers

aggregation

far

cobson)

aggregate

with

be a large

for

tonomous

BR.

the

addition

proxy

get

distribution

aJlow

thus

level

optimal

source(s)

map

one

identifiers

or register

and the

used

able then

the

or

sources

of groups

to

sources.

up the

highest setting

PIM

be inefficient

border

in

of memory

is optimal

will

aggregate

the

the

when

toward

being

identifier,

step

the

aggregation of

large

across

the

However, to

travel

are

level

amount

source

supported

important

It is also

size.

would

routers

the

This

closer

will

which

most

using

space.

exist,

sages

aggregating

level

the

information

at routers

of

IP-addressable

PIM:

for

subnet

an address entry.

warding

that for

being

as an

affecting

the

is

mem-

entries.

consider for

forwarding

to

the

forwarding

available

If

motivations

specification;

routing

of

number

whereas

is more

designated for

a par-

prune

the

An

beyond

current

with entry this

is

forward

is currently

be determined),

quality

most There

which

and

repeating

deployable

number

necessary

individusJ

and

when

The

responsibility

of

information

associated

avoid

be

absence the

As

1P cloud

LAN.

Aggregation

tree

without

accommodating

PIM

from

sources

in their LAN

onto

packets

which

put

serving

takes

on the

would

determine

a forwarding

technique

protocol

when the

routers

clouds”

router

for

therefore to the

router that

and

to

This

to

source

cache

order

oped current

are

problem

in

packet.

need

particular

multicast

could

data

then

the

fication.

sent We

for

on the router

source

traveling

be

existence

“1P

border

point

is analogous one

region.

joins.

having

these

which

should

the

have

would

BR

sources.

in splicing

ticular

than

first

to

joins.

issue

is identifying

This

and

the

packets

or

explicit

member

routers,

packet

data

not

They

entry

The

explicit

mode

from

to address

group

border

the

sparse

without

the

of

between the

needs

would

source.

onto

part,

words,

down

region

region

or

region

emanating

mode

regions

and

other

upstream

on a mechanism

relies

In mode

packets

mode

mode,

pulling an

data

whole

incompatabdity

mode.

a dense

a sparse

working

●

in

of initially

Normally,

mode

in

ofdense

of sparse

through)

through the

is the

nature

member

dense

comprised,

regions,

driven

nature

group

in splicing

tree

to

SDRP PIM

join

messages.

Its

ing

to

router’s

will

indicate

the

absence

implies

that

and

multicast and

multicast

with

Once

the

verse

as

will

inst aJls.

one

and

after

tablish

some the

vations would ting

up

path via

it

sends

another

path

out

the

occur

the

es-

the

re-

senders

[5]

if

S. Deering.

we expect suited

a reservation

receiver

that

[6]

J. Moy.

[7]

J.

Moy.

Draft, [8]

PIM

select

an

1993.

Y.

K.

Dalal

and

21(12):1040-1048,

initree reser-

path

path,

then

RP

path,

avoid

the

toward

[10]

particular

source(s).

This

work

will

the

that

the

protocol

affect

We have

A.

message

and

wait

new

shortest

initiated

[11]

for

uses

router

reverse

path

is sJso a subject use of the

for

protocol,

[12]

since

presented

for

both

shared not

(4)

and

soft

maintain

and

or

the

to

the

David

[13]

L. Wei

and

to the

to operate

to different

efforts

criteria

solved.

in,

efforts

architecture

network

there

of

and

are underway

are still to some

in other

reservation

areas

severaJ

[16]

using

such

issues

[17]

extensions

to

Simulation

and

[18]

config-

S. Deering gram

PIM

actions [2]

and

not

completely

require

on Computer

S. Deering.

Mult:cast

work.

thesis,

PhD

and

Systems, Routing Stanford

Multicast

extended

routing

routing

LANs.

pages

reand

in data-

ACM

85-111,

in a Datagmm University,

Y.

and

University,

Selective

June

1980.

of multicast

Report

Department,

trees

USC-CS-93-560,

University

of Southern

1993.

Estrin,

D.

extensions

Estrin,

D.

and

T.

4 (BGP-4).

and

routing

V.

to sparse

multicast

Jacobson. multicast

1993.

, editors.

Internet

Jacobson.

1993.

October

Li

V.

to dense

Farinacci,

for

Draft,

and

routing

October

extensions

Internet

Farinacci, for

Draft,

D.

router

Rekhter

S. Hares

D.

and

John

September

Estrin,

A

Draft,

border

January

gateway 1994.

Scudder.

IDRP

for

1P.

Internet

1993.

Trans-

May

1990.

Internet-

1991.

135

T.

Li,

Y.

routing

ing

specification.

L.

Zhang,

1993.

coordination

as inter-domain

D. Cheriton.

Broadcast

A comparison

Technical

Internet

S. Deering,

sion

expects

protocols.

internetworks

Estrin.

D.

router

S Jamin.

References [1]

D.

S. Deering,

Draft,

of multi-

to characterize

issues

Core

SIGCOMM,

190.

September

demand

environments

of the

ACM

(3) and

issues.

of the

Society

Internet

J. Crowcroft.

the

Stanford

NO.

Science

protocol

responsively

types

is in progress.

deployment

[15]

supports

conditions. PIM

forward-

of the ACM,

accommodates

to varying

types

complexity

Solutions

resource

The

and of

for

thesis,

algorithms.

groups.

(1)

protocols; and

Francis,

Mechanisms

Report

IGMP

mul-

in one protocol;

unicsst

adaptation

message

types

to reliably

implementation

implementation Due

tree

path

& videocast.

Proceeding

PhD

California,

advertise(2)

Reverse

1993.

Wall.

Computer

not

approach

groups;

underlying

trees.

of routing Our

Internet

future and

membership

mechanisms

and

IGMP

uration

problem

internets.

multicast path

the

efficient

protocol

existing

with

on

state

groups, A

shortest

multicast

graceful cast

distributed

depend

uses

area

receiver-initiated,

sparsely

does

to the

wide

experience.

Communications

audio

P. F. In

Francisco,

IGMP

a solution

in large,

and

RFC1247.

1993.

trees.

and

itself.

constrained,

ment

IETF

Broadcast.

rout-

reservations

previous

1991.

Metca.lfe.

packets.

J. Ballardie,

San

[14]

packets

August

be-

Conclusions

ticast

1988.

1P multicasting,

2, October

R. M.

1(4):19,

groups. 5

Distance

November

1978.

R. Frederick.

based

receiver

over

receiver

the

for

Analysis

of broadcast

News,

set-

source

the

[9]

message

to

version

MOSPF:

could

establish

alternative

Draft,

S. Deering.

protocol,

extensions

July

ing

then

initiated

is blocked

can

and

routing

OSPF

switching

source’s

this

Partridge,

Host

avoid

distribution

messages

to receiver

Internet

RFC1112.

Technical

In summary

OSPF.

RFC1075.

path.

ing is well

to

path

and

travel

C.

multicaat

that

to es-

the

Waitzman,

state

messages

RP

to

been

receiver

RP

reservation

message

has

PIM

The

join

its

to

send

tree

on

PIM

PIM

follow the

the to

the

it could

a reservation its

so via

tree.

first

send

fore

delay that

travel

would

packets

shortest

over

and to

wants

routes

all

the

D.

vector

1989.

tree

messages

extension

1992.

reservation

messages

according

However,

receive

[4]

carry

branch.

initiated

Multicast

route.

should state

J. Moy. September

symmetry

to cause

distribution

path

reservation-oriented tiaJly

[3]

presence

[18]:

path

travel

PIM

tree

reservation

of senders

messages

SDRP

carry

of it

receiver

RSVP

to the

forwarding

RSVP

shortest

Its

also

inside

accord-

table.

that

distribution

Interaction

tablished

and

route

the

such

should

bits

SDRP

forwarding

according

SDRP

on an alternative

setup

routing

QOS

an optional

●

indicate

forwarding

This

message

will

unicast

R.

and

Braden,

D.

Packet

Internet-llraft,

Resource

1 functional

Rekhter,

protocol:

D.

reservation specification.

Zappala.

format March

Estrin, protocol

and

Source forward-

1993. S.

Herzog, (RSVP)

Interraet-Draft,

and - ver-

Ott

obei