Transcript IP MULTICAST

IP MULTICAST
• IP Address => Host Identifier
THE ABILITY
TO DELIVER
AN IP PACKET( DATAGRAM )
TO
MULTIPLE DESTINATION
( HOST GROUP )
IP MULTICAST SUPPORT
• Multicast IP Address
• Mapping to LAN
Multicast
• Group Management
Router Protocol at IP
LevelHost A
Host B
– HOST
GROUP
Host C
IP MULTICAST ADDRESS
• IP Address Space: 11100000000000000000000000000000
Class D
224.0.0.0
239.255.255.255 11101111111111111111111111111111
1110
Well-known
IP Multicast Address
224.0.0.0
Base Address (Reserved)
224.0.0.1
224.0.0.2
224.0.0.3
224.0.0.4
224.0.0.5
224.0.0.6
224.0.0.7
224.0.0.8
224.0.0.9
224.0.0.10
224.0.0.11
224.0.0.12 224.0.0.255
All Systems on this Subnet
All Routers on this Subnet
Unassigned
DVMRP Routers
OSPFIGP OSPFIGP All Router
OSPFIGP OSPFIGP Designated Routers
ST Routers
STHosts
RIP2 Routers
IGRP Routers
Mobile-Agents
Unassigned
IP MULTICAST ADDRESS TO
ETHERNET MAPPING
• Ethernet: 48 bit -> 23 bit
23 bit
Class D Address
1110
Group ID copied to Ethernet address
0000000100000000010111100
0
1
0
0
5
E
Ethetnet Address
HOST GROUP
• Set of Hosts Listening to A Particular IP
Multicast Address
• A Set of Zero or More Hosts
• Membership -> Dynamic
– Hosts는 언제나 가입/탈퇴
– Member의 수와 위치 제한 없음
• Permanent or Transient
• All Hosts Group
– 224.0.0.1
– All systems on this subnet
– Automatically join
ACTIVATION
multicast
router
multicast
router
1. Query to all hosts group
multicast
router
multicast
router
3. A hosts expires the
2. Start delay timer fordelay timer
group membership
( 0 ~ D seconds)
multicast
router
4. The host sends Report 5. Hosts in the group stop the delay timer
IGMP MESSAGE FORMAT
0
3 4
Version
7 8
Type
15 16
Unused
31
Checksum
Group Address
IP header
IGMP message
20 bytes
8 bytes
MULTICAST ROUTING PROTOCOL
IGMP
Multicast Routing Protocol: MOSPF, DVMRP,..
MULTICAST ROUTING ALGORITHMS
•
•
•
•
•
•
Flooding
Spanning Tree
Reverse-Path Forwarding (RPF)
Reverse-Path Forwarding with Prunes
Steiner Tree
Core-Based Tree
FLOODING
• Simplest Multicast Routing Algorithm
• Procedure
– receive a multicast packet
– test for the first reception
– if first, forward the packet on all
(exception the incoming interface)
interfaces
• Insufficient Use of Router Memory
SPANNING TREE
• A Tree Structure Where Only One
Active Path Connects Any Routers
(No Loop)
Router
Leaf
SPANNING TREE (CONTINUED)
• Multicast Packets are Forwarded Along the
Spanning Tree
• One Spanning Tree for the Entire Internet
• Easy to Implement
• Traffic is Centralized on a Small Number of
Links
• Group Membership not Considered
• Does not Provide the Most Efficient Path
Between Members
REVERSE PATH FORWARDING
• Different Spanning
Tree for Each
(RPF)
Active (Source, Group) Pair
– When a multicast packet is received,
note source (S) and Interface (I)
– If I belongs to the shortest path toward
1
2
1
2
S, forward to all interfaces except I.
– If the
test
in the above is false, refuse
1
2
B
C
A
B
C
Athe packet.
B
C
3 A
3
4
3
4
5
5
D
E
6
D
4
E
6
From Source A
5
D
E
6
From Source C
RPF (Continued)
• Guarantee the Fastest Possible Delivery,
as Multicasting Follows the Shortest Path
from Source to Destination
• Because a Different Tree is Computed for
Each Source, the Packet Are Spread over
Multiple Links Resulting in better Network
Utilization
• Group Membership is not Considered
RPF WITH PRUNES
• Group Membership Considered
• Avoid Forwarding Datagrams onto a
Subnet Without Members
– The first packet is flooded on the whole
network
– Prune messages are sent back from leaf nodes
without group members
– Propagated back to source, forming minimal
tree
• Drawbacks
– The first packet is flooded on the whole
network
STEINER TREE
• Minimize the Number of Links to
Connect the Group Members
1
2D
2
• Source:
C,
Reception:
A,
A
B
C
A
B
C
1
3
3
4
D
4
5
E
6
RPF Tree
5
D
E
6
Steiner Tree
CORE BASED TREE (CBT)
• Core - a Fixed Point is the Center of
the Multicast Group
• Recipients Send JOIN Message to the
Core, to form a Tree
• One Spanning Tree per Group
• Traffic Concentration Problem
• Scalable
• Variation - Multiple Cores
CBT
• A single bidirectional shared tree for a
group
• Adv.
– reduction of state info. That needs to be
maintained at each router
• Disadv.
– traffic concentration
– delivery delay can be higher than in sourcebased shortest path trees
Multicast Routing
• DVMRP
– Distance vector
multicast routing
protocol
– Reverse-path
distance vector (I.e.,
router calculates
reverse optimum
path, from source
to itself)
• MOSPF
– Multicast open
shortest path first
– Uses group
membership packet
– Creates a shortestpath spanning tree
DVMRP
• RFC 1075
• Similar to Routing Information Protocol
(RIP)
– <destinations, distances>
• distance: hop count
– difference
• reverse-path distance
• handling of tunnels
– periodic exchange for the routing information
• Maintain Separate Tables for Unicast &
Multicast
• Reverse Path Forwarding Algorithm &
MOSPF
• 패킷의 전달 경로는 패킷의 시작점과 목적지
에 의해 결정됨.
• OSPF를 이용 최단 경로 결정
• 그룹 구성원간에는 하나의 최단 경로만 존재
• 데이터 링크 멀티캐스팅
• Forwarding
– forwading cache
• Dijkstra algorithm을 이용한 최단경로 설정은 과부하 작
업임
• local group database
– {group A, Net1}
• shortest path tree
MOSPF
• An enhancement of the unicast routing
protocol OSPF
• Designed to operate within a single
AS(autonomous system)
• OSPF
– Link-State Protocol
– Complete picture of the topology of AS
• MOSPF
– Add Group membership-LSA
• Intra-area multicasting, Inter-area
multicasting, Inter-AS multicasting
MOSPF
• Protocol Data Structures
– Local Group Database
• Local group DB: [group, subnet]
• Create group-member-LSAs (Link State
Advertisement)
– Forwarding Cache
• [Upstream node, Downstream Interfaces
(interface:hops)]
– Multicasting routing capability
– Inter-area Multicast forwarder
MOSPF
• Protocol
– Joining a multicast group
•
•
•
•
•
IGMP query
IGMP response
Create an entry in local group database
Send group membership LSA
Create an entry in local group database
Create a forwarding cache entry
– Leaving the multicasting group
PIM(Protocol Independent
Multicast)
• IETF IDMR WG에서 현재 개발중
• Motivation:
– DVMRP good for dense group
membership
– Need shared/source-based tree
flexibility
– Independence from Unicast Routing
• PIM implementations do require the
presence of some unicast routing protocol
to provide routing table information and
adapt to topology changes.
PIM-DM(2)
• If a router receives a multicast packet from
source S to group G, it first checks in the
standard unicast routing table that the
incoming interface is the one that is used
for sending unicast packets toward S. If
this is not the case, it drops the packets
and sends back a “prune (S,G)” message
on the incoming interface.
• The router will then forward a copy of the
message on all the interfaces for which it
has not already received a
“prune(S,G)”message. If there are no such
PIM-DM(3)
• Multiple Routers on a
Broadcast Network
– S sends a multicast
message; M is a group
member.
– C sends a prune back,
which would kill the
group for M as well.
– Solution: The prune
messages are always
sent to the “all-routers”
multicast address
(224.0.0.2).
– Upon seeing the prune
message, B would rejoin
the group.
PIM-DM(4)
• Multipath on
Broadcast
Networks
– S sends a multicast
packet to group M on E1.
– Both A-C and B-D
routers pick it up and
transmit on E2
(multiple copies).
– Solution: both C and D
will see each other’s
packet, and note that
the group route points
to the interface where it
was received.
PIM-DM(5)
• DVMRP와 다른점
– PIM-DM은 토폴로지의 변화를 반영하기 위해 유니
캐스트 라우팅 프로토콜의 존재를 가정한다.
– Child interface를 계산하지 않고 Explicit prune
message가 downstream link로 부터 오기 전까지는
단순히 멀티캐스트 트래픽을 포워드 한다.
• PIM-DM control message의 처리와 data
packet forwarding과정은 PIM-SM과 통합되어
있어서 하나의 라우터가 다른 그룹에 대해서
는 다른 mode로 작동할 수 있다.
PIM-SM
• Dense Mode와 다른점
– 라우터가 명시적으로 Join 메시지를 보내
야 한다.
– Rendezvous Point를 이용한다.
• Host joins a group
PIM-SM
• Source send to a multicast group
PIM-SM
• RP-Shared Tree or Shortest Path
Tree(SPT)
WGs in IETF Routing Area
IS-IS for IP Internets (ISIS)
Unicast Routing
Inter-Domain Routing (IDR)
Open Shortest Path First IGP (OSPF)
Routing Information Protocol (RIP)
UniDirectional Link Routing (UDLR)
Inter-Domain Multicast Routing (IDMR)
Multicast Extensions to OSPF (MOSPF)
Multicast Routing
Protocol Independent Multicast (PIM)
Border Gateway Multicast Protocol (BGMP)
Multicast Source Discovery Protocol (MSDP)
Mobile Environment
IP Routing for Wireless/Mobile Hosts (MobileIP)
Mobile Ad-hoc Networks (MANET)
Data Link Switching MIB (DLSwMIB)
General Switch Management Protocol (GSMP)
Switching
Multiprotocol Label Switching (MPLS)
SNA DLC Services MIB (SNADLC)
Virtual Router Redundancy Protocol (VRRP)
Routing Protocols Summary
Unicast
Multicast
RIP
DVMRP
OSPF
MOSPF
ISIS
PIM-DM
UDLR
PIM-SM
Intra-AS
Inter-AS
CBT
BGP
IDRP
SSM
SGM
BGMP
Long-Term Approach
MSDP
Short-Term Approach