[네트워크] 21. Multicasting Routing

21.1 Introduction

Unicasting

• One source and one destination network. One-to-one relationship
• Each router in the path of the datagram tries to forward the packet to one and only one of its interfaces.
• Unicasting (one-to-one), Multicasting(one-to-many), Broadcasting (one-to-all)

Multicasting

• One source and a group of destinations.
  • One to many relationship
• Source address is a unicast address, but the destination address is a group address, a group of one or more destination networks in which there is at least one member of the group that is interested in receiving the multicast datagram.
• Applications: Access to distributed DB, teleconferencing(원격 회의), distance learning(원격 강의)

IPTV: 9시 뉴스를 보는 회원에게만 multi cast로 보냄.

 

Multicasting vs. Multiple Unicasting

multicasting router가 없던 시절 unicast router를 통해 multiple unicasting으로 같은 데이터를 반복적으로 보냈었다.

• 비효율적이고 트래픽을 많이 만들어낼 수 밖에 없음

 

Multicast Addresses

• 모든 host(A, B, C, D)들은 unique address가 있음
• 그룹에게 보내야 할 때는 packet header에 multicast address를 명시해야 한다.
  • 226.14.18.7
  • 해당 address를 갖는 멤버가 누군지 관리하는 기능이 있어야 함 -> IGMP에서 관장

 

Multicast Addresses in IPv4

• The number of addresses is huge, 2²⁸
  • 1110(D class)으로 시작하는 모든 주소 (224~239)

이 아래는 몰아도 됨

• Divided into several subblocks
  • Local network control block : 224.0.0.0/24
  • Internetwork control block : 224.0.1.0/24
  • Source-specific multicast (SSM) block : 232.0.0.0/8
    • 특정 source와 연관된 multicasting
  • GLOP block : 233.0.0.0/8
  • Administratively scoped block : 239.0.0.0/8

Delivery at Data-Link Layer

• In multicasting, the delivery at the Internet level is done using network-layer multicast addresses. However, data-link layer multicast addresses are also needed to deliver a multicast packet encapsulated in a frame. (considering ARP in unicasting)
• An Ethernet multicast physical address is in the range
• 01:00:5E:00:00:00 to 01:00:5E:7F:FF:FF

• 이더넷의 경우 앞의 25bit가 multicast임을 나타내고 뒤에 23bit의 실질적인 주소가 들어가는데 32-bit multicast address에서 앞의 4bit(1110)을 제외하면 28bit 이기 때문에 뒤의 23bit를 자르게 되면 사용되지 않는 5bit가 생겨난다.(즉, 32개의 address)
• 설사 나에게 multicasting 되어 data link layer를 통해 이더넷으로 왔더라도 그 그룹의 멤버가 아니라면 discard (double check)

 

Network with No Multicast Support

• To send a multicast packet through most of WANs, a process called tunneling is used

• 어떻게 multicast를 지원하지 않는 망에서 unicast로 multicast처럼 보낼까? -> tunneling!
• multicast를 지원하는 network 사이에 unicast network이 존재하는 경우 그것들을 일단 unicast로 통과(tunneling) 시켜서 목적지에 도착한 후 multicasting이 지원되도록 하는 것.

 

Collecting Information about Group

• Creation of forwarding tables in both unicast and multicast routing involves two steps:
  • 1. A router needs to know to which destinations it is connected.
  • 2. Each router needs to propagate information obtained in the first step to all other routers so that each router knows to which destination each other router is connected.
  • Unicast versus multicast advertisement

• 어떤 것 어느 그룹에 속해있는지와 같이 그룹 멤버쉽가 관련된 정보는 자동으로 얻어지는 것이 아니라 또 다른 보조적인 프로토콜이 필요함 -> 좀이따 배울 IGMP

 

Multicast Forwarding

• Unicasting and multicasting are different in two aspects:

• unicast와 다르게 multicast는 어디로 보내는지(destination)와 더불어 누가 보내는 지(source)를 알아야 하기 때문에 더 복잡하다.(같은 그룹에게 보내는 경우)

 

Multicast Protocols

• Two approaches: Source-based tree and group-based tree approach
• The number of routing trees (m groups and n sources)
• source-based tree approach : m x n
  • 보내는 자가 각 그룹별로 membership을 보고 tree 구성
• group-based tree approach : m
  • 중간에 center를 두고 center에서 만들어 냄.

• Multicasting Open Shortest Path First Protocol(MOSPF)
• Distance Vector Multicast Routing Protocol(DVMRP)
• PIM - DM: Protocol Independent Multicasting Dense Mode(촘촘)
• PIM - SM: Protocol Independent Multicasting Sparse Mode(멀찍이 떨어져 있는)
• Core Based Tree(CBT)
  • Rendezvous Point

 

Multicast Distance Vector (DVMRP)

• Distance Vector Multicast Routing Protocol: the extension of RIP
• Create a source-based multicast tree in three steps:
  • Reverse path forwarding (RPF): Accept packets on the shortest path from source
    • 특정 router가 모든 path로 forwarding 각각의 router는 reverse로 가장 shortest path로 온 것만 받는다.
    • N receives two copy
  • Reverse path broadcasting (RPB) : Designated parent router
    • multiple connection이 있으면 designated parent router를 정하고 그 지정 router로만 받고 나머지는 받지 않는다.
    • N receives only one copy
    • all network receive a copy
  • 둘 다 기본적으로 broadcast임.
  • Reverse path multicasting (RPM)(아래에서 설명)

 

Multicast Distance Vector (DVMRP)

• Create a source-based multicast tree in three steps:
• Reverse path forwarding (RPF)
• Reverse path broadcasting (RPB)
• Reverse path multicasting (RPM) : Pruning & grafting
  • Pruning과 grafting을 통해서 바로 전 단계인 RPB는 모든 곳으로 다 보내고 온 것에서 멤버가 없는 것들은 잘라내고 멤버가 있으면 덧붙이는 것의 과정
    • active member

Multicast Link State (MOSPF)

• Multicast Open Shortest Path First: the extension of OSPF
• Source-based tree approach to multicasting.
• To extend unicasting to multicasting, each router needs to have another database, as with the case of unicast distance-vector routing, to show which interface has an active member in a particular group.
• Steps to forward a multicast packet received from source S and to be sent to destination G (group of recipients):
  • To create a shortest-path tree with S as the root using Dijkstra algorithm and all destinations as the leaves
    • source S를 가지고 dijkstra algorithm을 이용하여 모든 destination으로 가는 shortest path tree를 만든다.
  • The router finds itself in the shortest-path tree created in the first step.(broadcast)
  • To prune the broadcast tree and to change it to a multicast tree.
  • The router can now forward the received packet out of only those interfaces that corresponds to the branches of the multicast tree
  • 즉, broadcast tree에서 멤버가 없는 것들은 잘라내서 multicast tree로 바꾸는 과정

 

Example of Tree Formation in MOSPF

OSPF라는 기본 정적인 구조를 갖는 네트워크 architecture를 connection에 따라서 만들어진 table을 group member 측면과 누구로부터 왔는지 측면에 따라서 가지치기(Pruning)로 forwarding table을 만들어야 하는 과정이 필요해짐 .

 

Protocol Independent Multicast (PIM)

• Common protocol that needs a unicast routing protocol for its operation, but the unicast protocol can be either a distance-vector protocol or a link-state protocol.
• PIM needs to use the forwarding table of a unicast routing protocol to find the next router in a path to the destination, but it does not matter how the forwarding table is created.
• PIM can work in two different modes: dense and sparse
• PIM-DM

• PIM-SM

• group shared tree
  • join message를 랑데뷰 포인터로 보냄
  • 랑데뷰 포인터가 center를 담당하여 center에서 multicast를 담당

 

Interdomain Multicast Protocols

• Multicast Boarder Gateway Protocol (MBGP)
  • One common protocol for interdomain multicast routing
  • The extension of BGP
  • Provide two paths between ASs: one for unicasting, one for multicasting
  • Shared-group multicasting routing protocol in which one router in each AS is chosen as the rendezvous point (RP)

 

21.5 IGMP

• IGMP (Internet Group Management Protocol) defined at the network layer
• Used for collecting information about group
• One of the auxiliary protocols, like ICMP, which is considered part of the IP.
• IGMP messages, like ICMP messages, are encapsulated in an IP datagram.
• Two types of messages in IGMP version 3, query and report messages
  • A query message is periodically sent by a router to all hosts attached to it to ask them to report their interests about membership in groups.
  • A report message is sent by a host as a response to a query message
• General query, group-specific query, source-and-group-specific query message
• Report: Member report (Join), Leave report