CS计算机代考程序代写 database algorithm Slide 1

Slide 1

CMPT 471
Networking II

Multicasting protocols
© Janice Regan, 2006-2017

© Janice Regan, 2006-2017
3
IGMP states: 1
Consider a router with at least one host on a connected network that is a member of a particular multicast group
Every 125 seconds the router will generate a query and send it to the multicast group..
When the host receives the query it moves from member state to delaying member state, it builds its report and sets its random delay timer (random in a specified interval which defaults to 10 sec)
If it hears another report before it is due to send its own it will drop the report without sending an moves back to idle member state. (v2 only)
When its timer expires it sends its report and moves back to idle member state.

© Janice Regan, 2006-2017
4
IGMP states: 2
Consider a router with a connected network. No host on that connected network is a member of the multicast group. Then consider that one host on the connected network wishes to join the multicast group
The host will be in the nonmember state.
The host builds a membership report packet.
The host starts a timer and sends the membership report packet
The host moves into the delaying member state.
When the timer expires the host resends the member report packet and moves into the member state.
Sending the membership report twice (each time in a best effort UDP packet) provides a measure of security that the membership report will reach the server

© Janice Regan, 2006-2017
5
Need for dynamic routing
Membership in groups changes not only when topology changes, but also when new hosts/application programs join/leave a group or update filtering information.
Routing requires knowledge of both source and destination to avoid loops (router A-B-C-A)
Senders need not be members of the multicast group and multicast messages may be routed across networks with no members in the multicast group. Routing must adapt to any sender.

© Janice Regan, 2006-2017
6
Reverse path forwarding
When a source wishes to flood a message across the network to reach all routers
Determine which interface the packet should arrive through
Extract the source address
Consult the routing table to determine which interface the packet would be sent through in if was to be forwarded to the source address. This is the reverse path interface
If the packet arrives on the reverse path interface flood it through all other interfaces
If the packet arrives on any interface other than the reverse path interface drop it

© Janice Regan, 2006-2017
7
Reverse path forwarding
Using the RPF algorithm the packet will be flooding throughout the internet reaching all potential group members
Multiple copies of each packet may reach any given network.
Copies of the packet are sent to networks that are not part of the path from source to receiver and have no members in the multicast group

Group has members only on networks with hosts illustrated

© Janice Regan, 2006-2017
10
Truncated RPF (1)
Reverse path forwarding with an added step
Each router keeps both a conventional routing table and a multicast routing table which is a list of multicast groups reachable through each interface
On a network with more than one directly connected multicast router TRPF may still result in multiple copies of a multicast packet reaching a multicast group member

© Janice Regan, 2006-2017
11
Truncated RPF (2)
If RPF indicates the message should be dropped, it is.
OTHERWISE
If a router has no members on any of its attached networks it will check an additional list of reachable multicast groups and forward the packet through interfaces that lead to members of the group. The router truncates forwarding (does not flood the packet through the interface) when no group members are reachable through that interface.

zz
Group has members only on networks with hosts illustrated

© Janice Regan, 2006-2017
14
reverse path multicasting (RPM):
TRPF + Any router that has no members attached and no paths to multicast group members will be ‘pruned’. A prune message will be sent back to the previous router for the flooded message telling it to stop sending messages to the originating router of the prune message.
The flood and prune process results in the gradual development of a source based tree for multicast routing.
A router that has previously sent a prune message may later send a graft message to ask for the resumption of exchange of multicast messages (for example if one of the hosts on its connected networks decides to join the multicast group)

© Janice Regan, 2006-2017
15
RPM: routing
When a new member (receiver) joins the group, the tree may need to be updated.
By flooding an announcement of the new member
By having each router remember how to contact the rest of the multicast group.
Distance Vector Multicast Routing Protocol (DVMRP) is an extension of distance vector routing protocols used for unicast (works with RIP). DVMRP implements RPM
DVRMP is (like RIP) an IRP, it is used for hosts and routers within a single AS. Parts of that AS may be at different physical locations and be connected by tunnels.

Like RIP, DVMRP is not very scalable, larger amounts of data are exchanged as the network grows, a small value for infinity is used, and information on prune messages must be kept so graft messages can be executed

© Janice Regan, 2006-2017
17
When DVMRP message are sent
Periodically a router should send out DVMRP messages with all of its routing information to all of its virtual interfaces (physical interfaces and tunnels).
Whenever a route is changed, a routing update should be sent for that route. These triggered updates should have added random delays.
To supply information about some or all routes in response to a request.
A request for all routes should be sent on all virtual interfaces when an DVMRP router is restarted.
If possible, on termination a DVMRP router should send out DVMRP messages with metrics equal to infinity for all of its routes, on all virtual interfaces.

© Janice Regan, 2006-2017
18
What is a DVMRP message
DVMRP uses the Internet Group Management Protocol (IGMP) to exchange routing datagrams.
DVMRP datagrams are composed of two portions: an IGMP header, and a stream of tagged data. The fixed length IGMP header of DVMRP messages is:

The version is 1. The type for DVMRP is 3.
CHECKSUM
Version
Type
Subtype
4
8
16
32

© Janice Regan, 2006-2017
19
What is a DVMRP message
Subtypes
1 = Response; provides routes to some destination(s).
2 = Request; requests routes to some destination(s).
3 = Non-membership report;
4 = Non-membership cancellation; the message cancels previous non-membership report(s).
Checksum is calculated over entire message
Tagged Data, each containing a command. Each command includes a tag and necessary data
A DVMRP message is limited to 512 bytes

© Janice Regan, 2006-2017
20
Implementing DVMRP
There are multiple ways to implement DVMRP routing on a UNIX system
mrouted is can be used to support DVMRP and multicast forwarding and tunnelling
quagga (or zebra) routing suite can be used not only to implement DVMRP distance vector routing protocol but also link state multicast routing protocols (more later) and unicast routing protocols.

© Janice Regan, 2006-2017
21
mrouted
Uses DVMRP (RFC 1075) to propagate multicast routing information between routers. (in version 3 only). A pruned routing tree is determined for each multicast group with routes that have no members pruned from the multicast tree
A router running mrouted is a multicast router and maintains a multicast routing table
mrouted does not replace conventional unicast routing processes, they work in parallel

© Janice Regan, 2006-2017
22
mrouted
mrouted provides multicast tunnels
Propagate multicast packets between network segments or AS’s that support multicasting through parts of the internet that do not support multicasting
Multicast IP packet is encapsulated in a unicast IP packet then unicast to the next router that supports multicasting

Comer 2000: fig 17.10

Comer 2000: fig 17.11

© Janice Regan, 2006-2017
25
MBONE
RFC 1458, 1889
Multicast backbone: a virtual network of multicast routers that form a backbone for multicast routing over the internet
Growing exponentially just like the internet

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

© Janice Regan, 2006-2017
27
A DVMRP example: RPF
STEP 1: Send packet from s to A (hops between routers all have cost 1). Reaches multicast router A

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

© Janice Regan, 2006-2017
31
A DVMRP example: TRPF
All destination networks without members need not be part of the broadcast tree

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

© Janice Regan, 2006-2017
32
prune
A DVMRP example: RPM
All destination routers that do not have outgoing paths to any group members send prune messages

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

prune
prune
prune

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

ack
ack
ack

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

© Janice Regan, 2006-2017
35
A DVMRP example: changes
Change Topology, new member added on network attached to router Q, sends ICMP report to join

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

Join report

© Janice Regan, 2006-2017
36
A DVMRP example: changes
Change Topology, new member added on network attached to router Q, sends ICMP report to join

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

Graft

© Janice Regan, 2006-2017
37
A DVMRP example: changes
Change Topology, new member added on network attached to router Q, sends ICMP report to join

mrouted

A
B
C
D
E
F
A

mrouted

P
Q

© Janice Regan, 2006-2017
38
Other multicast protocols
MOSPF (RFC 1585)
Multicast extension of OSPF.
Demand driven
uses OSPF topology information to compute a forwarding tree for each multicast source
Useful in a particular area of an AS.
Propagate membership information from each area to the backbone through MABRs (multicast area border routers)

© Janice Regan, 2006-2017
39
Other multicast protocols
PIM-SM, PIM-DM Protocol independent routing for sparse or dense multicast networks

© Janice Regan, 2006-2017
40
Sparse and dense multicast
Consider an internet composed of many network segments. One or more routers is connected to each segment.
If you expect most segments to contain hosts that will be part of a multicasting group you have a dense multicast network
If you expect only a few of the segments to contain hosts that will be a part of the multicast group you have a sparse multicast network.

© Janice Regan, 2006-2017
41
Sparse and Dense multicast
Consider an internet composed of many network segments. One or more routers is connected to each segment.
For PIM (protocol independent multicast) a different approach is taken for dense multicast networks (usually a single enterprise with a small number of ASs) and for sparse multicast networks ( ISP’s with varied usage, general internets)
DVMRP is the simplest form of Dense Multicast,
PIM-SM is the most commonly used multicast protocol

© Janice Regan, 2006-2017
42
PIM
PIM-DM Uses a broadcast and prune (flood and prune) process similar to DVRMP.
Forward multicast datagrams until told not to (pruned)
PIM-SM Uses a demand driven approach
Do not forward multicast datagrams until asked
End station sends request to its local multicast router.
Local multicast router propagates request to other multicast routers till the request reaches a router that is currently forwarding multicast packets.

© Janice Regan, 2006-2017
43
PIM-SM: finding active routers
Designate one or more routers as core routers or Rendezvous points (RP). Only one should be active
Each RP maintains a database of all its multicast groups and their sources.
Each multicast router must know the addresses of the RPs. (addresses learned using protocols we will not cover)
Each multicast group has one RP

© Janice Regan, 2006-2017
44
PIM-SM: finding active routers
Designate one or more routers as core routers or Rendezvous points (RP). Only one should be active
Each RP maintains a database of multicast groups and their sources.
Each multicast router must know the addresses of the RPs. (addresses learned using protocols we will not cover)
A core based tree (CBT) rooted at the RP can then be generated. The CBT will connect to all active (with present members) routers
Used to route multicast datagrams to multiple groups
Demand driven, only add to the tree when a new host, which may be on an unserviced router, requests to become a member of the group

© Janice Regan, 2006-2017
45
Example:
Based on material from
ftp://ftp-eng.cisco.com/ipmulticast/training/Module1.pdf
https://www.cisco.com/c/dam/en/us/products/collateral/ios-nx-os-software/ip-multicast/prod_presentation0900aecd80310883.pdf

© Janice Regan, 2006-2017
46
Example: Receiver Joining Group
Uses RPF,
source is the RP for shared trees (RP to receivers),
New receivers register with RP then their local multicast router becomes part of the shared tree (if it is not already) and traffic flows up the shared tree to them

© Janice Regan, 2006-2017
47
PIM-SM: adding a receiver to CBT
The new receiver will send an IGMP report requesting that it join group G to its local router
If the local router is not a part of the CBT it will send a join message to the router one hop closer to the RP
If a the local router is already a part of the CBT for a local RP
it is already forwarding multicast packets.
The local multicast router will add the host to the multicast group and begin forwarding packets to the host from the RP

© Janice Regan, 2006-2017
48
PIM-SM: adding a receiver to CBT
If a the local router is not already a part of the CBT (shared tree) for a local RP
The local multicast router will send a join request to the next hop router on the path to the RP (along the unicast path)
When the join message reaches the next hop router that router will
add an entry in its forwarding table to forward group G multicast datagrams to the local router
If it is a member of the CBT for group G it will add the originating host to its list of member for group G
If it is not a member of the CBT it will send a join message to the router one hop closer to the RP

© Janice Regan, 2006-2017
49
PIM-SM: adding a receiver to CBT
The next hop router will (loops)
add an entry in its forwarding table to forward group G multicast datagrams to the originating router of the join message
If the next hop router is a member of the CBT for group G it will add the originating host to its list of member for group G
If it is not a member of the CBT it will send a join message to the router one hop closer to the RP
The loop above continues until a router that is a member of the CBT is reached

pim-SM

New receiver

Unicast join message

Resulting shared tree

© Janice Regan, 2006-2017
51
PIM-SM adding a source
A multicast data sender sends data to a multicast group.
The sender’s local router (DR) takes those data packets, unicast-encapsulates them, and sends them directly to the RP.
The RP receives these encapsulated data packets, decapsulates them, and forwards them onto the shared tree.
The packets then follow the shared multicast tree, being replicated wherever the RP Tree branches, and eventually reaching all the receivers for that multicast group.
The process of encapsulating data packets to the RP is called registering, and the encapsulation packets are known as PIM Register packets

pim-SM

receiver

shared tree

New source

Multicast data to group
Unicast encapsulated multicast data

© Janice Regan, 2006-2017
53
A PIM-SM example: changes
Continue to unicast encapsulated data directly to RP while building a source based tree
F

pim-SM

receiver

shared tree

New source

Source tree join messages

Data distribution down shared tree

© Janice Regan, 2006-2017
54
A PIM-SM example: changes
Multicast data can now travel through the source based tree. Send register stop message to stop encapsulated delivery
F

pim-SM

receiver

shared tree

New source

source tree

© Janice Regan, 2006-2017
55
Where are we now
The new receiver joined the shared tree
A new source has sent data to the multicast group.
It’s local router registered it with the RP
A source tree from the RP to the source has been built.
After building the source tree and initiating data transfer through the source tree the RP sent a register stop message to cease encapsulated delivery to RP
When the source sends data it now passes through the source tree to the RP
The data passes from the RP through the source tree then throught the shared tree to all the members of the multicast group

© Janice Regan, 2006-2017
56
What next?
This may be inefficient,
Taking a longer path to the RP and then the destination
May be a shorter path from the source to the receiver
May want to add the new source as a SBT (source based tree), a shortest path tree from the source to the receiver
Source based trees are built only for source-receiver paths carrying significant traffic. When a specific traffic level is attained between a source and receiver then the SBT will be determined.

© Janice Regan, 2006-2017
57
Building the SBT
The routers serving the receiver’s network will directly unicast a source join message to the router serving the destination’s network
The source join message travels through the network at each hop another link in the source based tree is established

© Janice Regan, 2006-2017
58
A PIM-SM example: changes
source join messages are sent to build a shortest path source based tree. Traffic still travels along the original source tree
F

pim-SM

receiver

shared tree

New source

source tree

Source join messages

© Janice Regan, 2006-2017
59
A PIM-SM example: changes
source prune messages are sent to switch over from the old source tree. Traffic now travels along the new source tree
F

pim-SM

receiver

shared tree

New source

source tree

Source prune messages

pim-SM

receiver

shared tree

New source

source tree

Source prune messages

pim-SM

receiver

shared tree

New source

source tree

prune

pim-SM

receiver

shared tree

New source

source tree

traffic

/docProps/thumbnail.jpeg

Related Posts