Transcript 投影片 1 - NTUT

Chia-Hui Huang
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
1
 Multicast Concepts
 IP Multicast
 Application Layer Multicast
 Simulation tools
 Summary
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
2
 What is multicast ?
 Multicast applications
 Why multicast ?
 Terminologies
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
3
 Multicast communications refers to one-to-many or
many-to-many communications.
140.124.180.0/24
140.124.181.0/24
Sender
Receiver
140.124.182.0/24
140.124.183.0/24
140.124.180.0/24
140.124.181.0/24
Sender
Receiver
Receivers
Receiver
140.124.182.0/24
140.124.183.0/24
Unicast forwarding
Receiver
Receivers
Multicast forwarding
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
4
 Multicast Applications
 One-to-many
 Scheduled audio/video distribution
 End System Multicast
 File Distribution
 …
 Many-to-many
 Multimedia Conferencing
 Concurrent Processing
 Multi-player Games
 P2P file sharing
 …
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
5
Bandwidth
Consumption
Server
Load
Multicast
vs.
Unicast
User
Latency
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
6
IP Multicast
Application
Layer
Multicast
Multicast
Techniques
Overlay
Multicast
Network
Type
Overlay
Network
Topology
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
7
 IP Multicast fundamentals
 Multicast Group
 IP Multicast Routing Protocols
 IP Multicast Requirements (Constrains/Drawback)
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
8
 Components of the IP Multicast service
 IP Multicast Addressing
 IP Group Management
 Multicast Routing
 One to many communication over an IP infrastructure
 Multicast groups are identified by IP addresses in the range
224.0.0.0 – 239.255.255.255 (class D address)
 The IP Multicast service is unreliable
 UDP
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
9
 IP multicast Group
 Receivers must Join multicast
group (IGMP)
 Sender send to group address
 Multicast router find delivery
paths and replicate the packet
Receiver
Receiver
Group Member 2 Group Member 1
Sender & Receiver
Group Member 1
Sender
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
Receiver
Group Member 1
Group Member 2
10
 Graph problem
 Build a spanning tree between all members of a multicast
group
 Solutions
 Shortest Path Tree (Source-Based Tree)
 Minimum-Cost Tree ( shared tree )
 Steiner tree problem
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
11
 Multicast routing in practice
 Source-Based Tree
 Build a tree that minimizes the path cost from the source to each
receiver – shortest path tree
 Builds one shortest path tree for each sender
 Tree is build from receiver to the sender – Reverse Path Forwarding
 Shared Tree
 Build a single distribution tree that is shared by all senders
 Select one router as a “core” (rendezvous point)
 All receivers build a shortest path to the core
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
12
 Multicast forwarding techniques (RFC1075)
 Reverse Path Forwarding (RPF)
 Avoid duplicate packets ( look-free forwarding )
 RPF check
 When a multicast packet is received, note its source ( S ) and interface ( I )
 If I belongs to the shortest path from S, forward to all interfaces except I
 If test in step 2 is false, drop the packet
 Packet is never forwarded back out the RPF interface
 Reverse Path Multicasting ( RPM )
 Take into account Multicast Group Membership
 Flood-and-Prune (cascade of prune messages)
 Both the group membership and Internet topology can change
dynamically …
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
13
 Prune Message
 Removes a link from the multicast tree
Who sends prune message ?
1. A router with no group members in its local network and no
connection to other routers ( sent on RPF interface )
2. A router with no group members in its local network which has
received a prune message on all non-RPF interfaces ( sent on RPF
interface )
3. A router with group members which has received a packet from a
non-RPF neighbor ( to non-RPF neighbor )
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
14
Multicasting
Protocols
Source-Based
Tree
DVMRP
Share Tree
MOSPF
CBT
PIM
PIM-DM
PIM-SM
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
15
 DVMRP
 Distance Vector Multicast Routing Protocol
 Each router maintains a multicast routing table by
exchanging distance vector information among routers
 Flood multicast packets based on RPF rule (flood-and-prune)
 Pruning / Grafting strategies
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
16
 CBT
 Core-Based Tree
 Core placement
 Manual
 Bootstrap
 Tree formation
 JOIN_REQUEST
 Transit states (router)
 JOIN_ACK
 Confirmed states (router)
 Data forwarding
 Source to core router – unicast (group-id is placed in the option field of
packet)
 Multicast packets span the tree based on the packet’s group-id
 Tree maintenance
 ECHO_REQUEST, ECHO_REPLY
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
17
 Support for IP Multicast ( multicast functions )
Multicast Routing
protocol
Router
Replicate
&
Forward
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
18
 Multicast Service Requirements
Congestion Control
Flow Control
Group State
Multicast Service
Requirements
Security
Consequence …
Disabled
by router
Reliability
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
19
Implement
Multicast
Service at the
End System ???
No infrastructure
(router) support
is needed
Overlay
Multicast !!
???
Alternate
technique for
multicasting
???Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
Application
Layer
Multicast !!
2015/7/16
20
 Application Layer Multicast (ALM) concepts
 Routing Protocols
 Issues ( research topics )
 Mechanism
 Theoretical
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
21
 Application Layer Multicast (ALM)
 Implement multicast functionality at the application layer
 Application layer multicast data packets are replicated at end-hosts
 End-hosts form an overlay network
 No underlying topology information
 Metrics – performance penalty
 Link stress
 Number of duplicate copies of a packet over a physical link
 Max stress
 Total stress
 Relative Delay Penalty ( RDP )
 Relative delay increase between two nodes against unicast delay between
the same two nodes
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
22
 ALM routing protocols organize the group into
 Control topology ( P2P overlay network )
 Data topology
ALM Routing
Protocols
Mesh-first
ESM (Narada)
Tree-first
Yoid
Implicitly
HMTP
NICE
CAN
Scribe
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
23
 Mesh-first - ESM
 Control topology
 Mesh structure
 Data topology
 tree structure
 created using RPF, e.g. DVMRP
 Tree-first - HMTP
 Control topology
 tree structure
 Construct a shared data delivery tree directly
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
24
 Implicitly - NICE
 Control topology
 According to some specific properties ( e.g. distance )
 Mesh / Tree structure
 Data topology
 Deliver data according to some ”forwarding rules”
 AL Multicast is an application of P2P network
 Group management mechanism of P2P network form control
topology of AL Multicast
 E.g.
 CAN – CAN P2P network
 Scribe – pastry P2P network
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
25
 Group management ( P2P Network )
 Static
 Dynamic
 Maintenance ( Join, Leave and failure)
 Routing protocol
 Number of sources
 Single source
 Multiple sources
 Service specific
 Reliable, trust, delay, bandwidth consumption … etc
 Congestion & flow control
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
26
 Performance Metrics
 Link stress
 RDP
 Number of hops and delays between parent and child hosts
in an overlay tree
 Degree of hosts
 Bottleneck
 …
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
27
 Cost of ALM
 Overlay cost – number of underlying hops traversed by every
overlay link

Lo (h, k , n) denotes overlay cost for an overlay o when n is the
number of hosts
 Underlying tree model – k-ary tree
 Normalized Overlay Cost
 Overlay cost vs. average number of hops for unicast
Lo (h, k , n)
Ro (h, k , n) 
U o (h, k )
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
28
 Characteristic of normalized overlay cost
Ro (h, k , n)  n x
Chuang and Sirbu (1998) found that the ratio between the total
number of multicast links and the average unicast path length
exhibits a Power-law.
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
29
 Optimal solution ( normalized overlay cost )
 IP Multicast
LIPMulticast (n)
 n0.8
U o (h, k )
 ALM – Sonia Fahmy and Minseok Kwon (2003)
 Receivers at leaf nodes
Lo (h, k , n)
0.92
Ro (h, k , n) 
n
U o (h, k )
 Receivers at leaf or non-leaf nodes
Lo (h, k , n)
Ro (h, k , n) 
 n0.83
U o (h, k )
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
30
 General simulator
 OMNet++
 OverSim Framework – P2P simulation framework
 INET Framework – implement protocol stack of wire and wireless
network
 NS-2
 Peer-to-Peer network simulator
 P2PSim
 OverlayWeaver
 PlanetSim
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
31
IP Multicast
But ... Multicast So ...
Disabled by
Efficiency
Service
router
Requirements
Alternative ...
Application Layer
Multicast
Design
Network
Issues
infrastructure But ...
remain
unchanged
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
Design
Trade-off
2015/7/16
32
Issues & Trade-off
Group
Management
Mesh
vs.
Tree
Congestion
& Flow
Control
Routing
Protocol
Source Tree
vs.
Shared Tree
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
33
1. D. Waitzman, C. Partridge and S. Deering, “Distance Vector
Multicast Routing Protocol,” RFC 1075, IETF Network Working
Group, November 1988.
2. A. Ballardie, “Core Based Trees (CBT) Multicast Routing
Architecture,” RFC 2201, IETF Network Working Group, September
1997.
3. B. Quinn and K. Almeroth, “IP Multicast Applications: Challenges
and Solutions,” RFC 3170, IETF Network Working Group,
September 2001
4 S. Banerjee and B. Bhattacharjee, “A Comparative study of
application layer multicast protocols,” Unpublished report,
Department of Computer Science, University of Maryland, available
at
Wireless and Broadband Network Laboratory
2015/7/16
34
http://pages.cs.wisc.edu/~suman/pubs.html
(WBNLAB) Dept. of CSIE, NTUT
5. J. Chuang and M. Sirbu, “Pricing multicast communications: A cost
based approach,” in Proc. Internet Society INET, Jul. 1998.
6. Sonia Fahmy and Minseok Kwon, “Characterizing Overlay
Multicast Networks and Their Costs,” IEEE Transaction on
Networking, Vol. 15, no. 2, April 2007
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
35
Appendix
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
36
source
H1
(a) Set routing tables according to RPF
R1
R2
R5
source
H1
R1
R2
R3
H2
R4
R6
R8
H3
Joined
source
R7
R3
H2
H4
Joined
R1
H5
R6
ne
Pru
R4
Prune
H3
R7
Pru
ne
Pru
ne
R7
Pru
Pru
(b) Flood
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
ne
R6
ne
H5
H4
Joined
ne
Prune
R8
H2
e
Prune
Prune
n
Pru
Prune
H3
Joined
R4
R3
R2
Pru
R5
H1
R8
H5
2015/7/16
H4
Joined
(c) Prune
37
source
H1
source
R1
R4
H3
Joined
H2
R7
H4
Joined
R2
R3
Core
Router
H2
R4
R6
Join
R5
Join
J oin
Join
Core
Router
R1
R3
Join
R2
H1
R8
R6
R5
H3
Joined
R7
H5
Joined
(a) Receiver sends a Join message to RPF
neighbor with respect to core router
H4
Joined
R8
H5
Joined
(b) Data forwarding
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
38
 A network built on top of one or more existing
networks
Overlay link
Receivers
Source
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
39
Host
Router
1
1
3
A
A
B
4
2
1
1
A
1
25
2
1
27
Application Layer Multicast
3
Unicast
1
1
4
1
25
2
1
3
27
3
B
1
4
3
29
2
4
2
1
A
27
2
4
B
1
B
2
Network Layer Multicast
1
3
2
4
Wireless and Broadband
Network
Laboratory
Application
Layer
Multicast 2015/7/16
(WBNLAB) Dept. of CSIE, NTUT
<1,2> and <1,3> = 1
29
<1,4> = 27
1
The penalty of
Application
Multicast !!
40
Given: A Weighted graph G(V , E ) and a vertices subset
S V
Find: A tree of minimal weight which spanning S
 NP-Complete problem
 Approximation
Approxm iationRatio
achievedcost
optim alcost
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
41
 Steiner tree vs. minimum spanning tree
2
 Steiner point
2
1
2
1
1
2
1
1
1
2
2
(a) Network graph
1
Steiner point
1
1
2
2
2
2
2
1
1
1
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
(b) Steiner Tree
2
2015/7/16
(c) Minimal Spanning Tree
42
 ESM
 Narada
 Narada Components
 Mesh management
 Ensure mesh remains connected in face of membership changes
 Random join
 Mesh optimization
 Members periodically probe other members at random and
 Add new link/ Drop existing link
 Spanning tree construction
 Source rooted shortest delay spanning trees of mesh
 Constructed using well known routing algorithms
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
43
 Host Multicast Rendezvous Point ( HMRP )
 Maintain the root address of current tree
 Cluster nearby members together
 Round-Trip Time ( RTT ) as measurement metric
 Every member must maintain information …
 List of children – for join procedure
 Root path – for leave, improvement and partition recovery
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
2015/7/16
44
B
A
Join Request
A
C
D
B
E F
C
D
E F
N
N
New
Member
New
Member
(a)
(c)
A
B
Join
Request
A
C
D
E F
Query
Nearest
B
C
N
New
Member
D
E F
N
(b)
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
Join
Request
(d)
2015/7/16
New
Member
45
 NICE Hierarchy
 Hierarchical arrangement of members
Topological clusters
Layer 2
Layer 1
G
C
B
Layer 0
G
C
E
G
K
H
K
A
D
F
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
I
2015/7/16
J
46
 A – layer 0
A7
 B – layer 1
B1
 C – layer 2
C0
 Rendezvous Point
 RP
B0
A0
A7
Create control
topology
according to
“distance”
A1
B2
A2
A7
RP
A7
RP
RP
Join
B1
B1
B1
Join
C0
Join
Join
New
New
New
C0
C0
A1
B0, B1, B2
C0
A1
A1
Join
Attach
B0
A0
A2
B2
B0
A0
A2
B2
Wireless and Broadband Network Laboratory
(WBNLAB) Dept. of CSIE, NTUT
B0
A0
2015/7/16
A2
B2
47
 Data delivery path
 A0 as source
 A7 as source
Forwarding rules :
Source : Forward to cluster members and cluster leader
Cluster Leader : cluster members
 C0 as source
A7
B1
B1
C0
C0
A1
B1
C0
A1
A1
B0
A0
A7
A7
B2
A2
(a) A0 is the source
B0
A0
B2
A2
(b) Network
A7 is the Laboratory
source
Wireless and Broadband
(WBNLAB) Dept. of CSIE, NTUT
B0
A0
2015/7/16
B2
A2
(c) C0 is the source
48