In this dissertation, we address formal analysis of efficient multicast in IP networks. The multicast is a effective mechanism for communicating among large number of group members. First, we present a BestRelay relation for constructing multicast overlay tree. It can be used for a reliable multicast retransmission tree over IP multicast network and also for a overlay multicast relaying tree over IP unicast routing. Efficiency of retransmission trees for a reliable multicast is mainly depends on locations of repairers, which are in charge of retransmitting lost packets. We propose an algorithm for each receiver to find a repairer for efficient recovery. The resulting tree for retransmission is organized by pairs of a receiver and a repairer which is the host "nearest" to the receiver among the multicast group members "nearer" to the sender. We formally prove that the proposed algorithm realizes reliable multicast with only constant times of a lower bound cost achievable through impractical router support. We also evaluate the algorithm through extensive simulations. Overlay multicast has been proposed for implementing multicast in the application layer as a practical alternative of IP multicast. Since a packet in overlay multicast is transmitted via unicast between end hosts, the same packet can be sent over a link multiple times, and thus, the main challenge of overlay multicast is how to organize multicast delivery trees to minimize bandwidth consumption. In this dissertation, we present a formal analysis of bandwidth efficiency of overlay multicast using a simple tree construction algorithm using BestRelay. Our analytic result shows that the bandwidth consumption of overlay multicast can be bounded by twice of that of optimal IP multicast. We confirm this result through simulation as well.
이 논문은 인터넷에서 효율적인 멀티캐스트를 위한 이론적 분석을 보여준다. 멀티캐스트는 여러 호스트로 구성된 그룹간의 통신을 효과적으로 하기 위한 방법이다. 먼저 우리는 호스트 그룹안에서 BestRelay 관계를 정의한다. 이것은 IP 멀티캐스트 상에서 신뢰성을 보장하기 위한 재전송 트리로 사용되거나 응용프로그램 수준에서 유니캐스트를 이용한 오버레이 멀티캐스트를 위해 사용될 수 있다. 재전송 트리의 효율성은 잃어버린 패킷을 수정해주는 호스트의 위치에 종속된다. 우리는 멀티캐스트 그룹의 수신 호스트가 효율적인 재전송 호스트를 찾을 수 있는 알고리즘을 제안한다. 이를 통해 구성된 재전송 트리에서 각 수신 호스트는 재전송 호스트를 자기 자신보다 송신자에 가까운 호스트 중에서 자신에게 가장 가까운 호스트로 삼는다. 우리는 이론적인 증명을 통해서 이 트리를 이용한 재전송 트리가 현실에서는 불가능한 이론적인 최적의 방법을 사용할 때에 비해 상수배의 비용이 필요함을 보였다. 또한 많은 환경에서의 시뮬레이션을 통해 이 알고리즘을의 평가하였다. 오버레이 멀티캐스트는 IP 멀티캐스트의 실용적인 대안으로 응용 프로그램 수준에서 멀티캐스트를 수행한다. 오버레이 멀티캐스트에서는 호트스간에 유니캐스트를 통해 패킷이 전송되기 때문에, 같은 패킷이 하나의 링크에 여러번 전송될 수 있다. 따라서, 오버레이 멀티캐스트에서는 비용을 줄이는 중계 트리를 어떻게 구성하는가가 중요한 문제이다. 우리는 이 논문에서 BestRelay를 이용한 오버레이 트리가 최적의 IP 멀티캐스트에 비해 2배 이하의 대역폭만을 요구함을 이론적으로 증명하였다. 시뮬레이션 결과는 이 증명을 실제적으로 보여준다.