4.7 broadcast and multicast routing

Braodcast routing

flooding

contorlled flooding

spanning tree

일단 Graph부터 정의해보자

Graph

• 여러 개의 vertex(node)가 edge로 연결되어 있는 자료 구조이다
• directed, undirected graph가 존재한다

Tree

• Graph의 한 종류이다
• cycle이 없어야한다
• 부모와 자식 개념이 있으며 최상위 node를 root node라고 부른다

Spanning Tree(신장 트리)

• Spanning Tree T는 undirected graph(무방향 그래프) G의 모든 vertex(꼭지점)를 포함하는 부분 집합
• undirected graph는 여러 개의 spanning tree를 가짐

Minimun Spanning Tree(MST, 최소 신장 트리)

• MST는 edge-weighted undirect graph에서 최소의 weight(가중치)를 가진 spanning tree
• Prim, Kruskal 알고리즘으로 다항시간 내에 찾을 수 있음

Prim Algorithm

• 나무를 보면서 나아가기

1. 임의의 edge을 선택
2. 선택한 edge로부터 가장 낮은 weight를 갖는 vertex를 선택
3. 모든 vertex가 선택될 때까지 반복

Kruscal Algorithm

• 숲을 보면서 나아가기

1. edge의 weight를 오름차순으로 정렬한다
2. 가중치가 가장 작은 간선을 순서대로 선택하면서 연결한다
3. cycle이 생기면 연결하지 않고 넘어간다

Prim vs Kruscal

• Prim은 최소 weight로 연결된 edge를 찾을 때 자료구조의 성능에 영향을 많이 받음
• Kruscal은 처음에 정렬하는데 시간이 많이 걸림
• edge의 개수가 적으면 Kruscal, 많으면 Prim이 낫다

References

• https://velog.io/@fldfls/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-MST-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%ED%94%84%EB%A6%BC-%EC%95

Multicast routing

source-based tree

• shortest path trees
  • Dijkstra algorithm
• reverse path forwarding(RPF)
  • source로부터 가장 짧은 길에서 온 것만 전달하고 나머지는 버림
  • pruning: group

    group-shared tree

• steiner tree(minimal spanning with attached group members)
  • minimum spanning tree를 일반화한 문제
  • NP-complete
  • 슈타이너 트리 2-근사 알고리즘
• center-based trees
  • center router에 연결된 tree에 닿을 때까지 unicast join-msg 전송

Multicast routing in the internet

• DVMRP(Distance-Vector-Multicast Routing Protocol)
  • 최초에 인터넷에서 사용됐던 multicast routing protocol
  • RPF와 pruning을 사용해서 source-based tree를 만든다
• PIM(Protocol-Independent Multicast)
  • 현재 가장 많이 사용되는 multicast routing protocol
  • 두 가지 multicast distribution scenrio가 있음
    • dense mode
      • DVMRP와 비슷하게 flood-and-prune reverse path forwarding techneique을 사용함
    • sparse mode
      • multicast distribution tree를 만들기 위해 randezvous point를 사용