After the birth of the Internet in 1970s, the Internet has grown exponentially because it was not only used for academic and military purposes but also as commercial demand and the development of WWW (World Wide Web) in 1990s. While in the process of deploying the Internet, multicast technology was introduced, which can deliver not multiple copies of message but even a single copy of message to all members of its destination host group. IP Multicast technology still has several problems to solve even though much elaboration for research and deployment has been done since 1992. The best environment for receivers is to have network fault free environment. If it is not possible, the next best thing is fast detection and accurate fault isolation when a fault has occurred.
FAULT isolation is defined as a task of locating the on-tree router(s) or on-tree link(s) which is the origin of a fault. We use the term fault when it results in a change to at least one receiver’s path from the source. A fault may result from the network problems such as router crash, link failure, and significant packet loss, etc. Fault isolation is essential for network operators or system administrators who are responsible for supervision of their corresponding network. However, isolating a fault in multicast tree is difficult because of the multicast characteristics such as dynamic nature of group membership, anonymity of members, and use of User Datagram Protocol (UDP) that provides no feedback.
Several models have been suggested to diagnose a fault in multicast trees, but they are generally limited to single-source sessions. In practice, there are many multi-source multicast sessions, such as large-scale replicated database, large-scale multimedia conferencing, and Web cache protocols. If we apply the single-source models to a multi-source multicast session, the number of control messages and time required to isolate a fault increases exponentially.
In this paper, we propose an efficient multicast fault isolation scheme for multi-source sessions, called Suppressed One-way Source Probing (SOSP). The main goal of the scheme is to isolate a fault with short latency while maintaining low message complexity in multi-source multicast sessions. The sources send a special packet, probe, into multicast session periodically after writing its address. Routers involved in multicast tree record a routing path based on periodic probes from sources, and receivers isolate a fault region using the probes with efficient fault isolation algorithm. The sources generate probes into multicast tree, so it is source-probing mechanism. And it is also One-way mechanism because the sources do not send feed back after they send probes. However, naive one-way source probing mechanism may imply packet implosion problem in the network. So we introduce another mechanism to enhance the performance. That is probe suppression mechanism. The routers in a given multicast routing tree compress the probes to avoid packet implosion by the rule of suppression. So we named it as Suppressed One-way Source Probing (SOSP).
We use two metrics to evaluate the performances of our proposed scheme, SOSP. The first metric is the message complexity, which is defined as the number of probes delivered to the receivers and the routers involved in a target multicast routing tree before all the receivers isolate a fault after the fault has occurred. The second one is the fault isolation latency, which is the time elapsed from when a fault occurs till all the receivers isolate the fault.
We run many simulations to verify the performance using ns-2 with a transit-stub topology generated by the GT-ITM tool. The simulation results show that there exists an optimal suppression time, τ, which derives the minimal average fault isolation latency. We also find out that optimal suppression time, τ, depends on the source probing interval, δ. The SOSP reduces message complexity and enhances fault isolation latency remarkably, which also improves scalability. For practical deployment, we present an analytic mathematical formula to estimate optimal suppression time, which provides maximum performance for a given network status. We apply the intrinsically linear model to find a fitted regression line to the simulation results. Using the formula, we are able to estimate optimal suppression time easily in a given any source probing interval. The formula is derived from the simulation results but we expect that the formula can be applied as approximation when the proposed scheme is deployed in real networks.
1970년대에 인터넷의 태생 이후 인터넷의 그 사용 용도가 단지 학술, 군사적인 용도로 국한되지 아니하고 1990년대에 등장한 WWW(World Wide Web)의 확산으로 인한 상업적 수단으로 활용되면서부터 인터넷은 급격하게 성장하게 되었다. 인터넷의 보급과 더불어 동일한 복수개의 메시지 사본을 여러 명의 사용자에게 전송하는 방식이 아닌 단지 하나의 메시지로 동시에 여러 명에게 보낼 수 있는 방법인 멀티캐스트 기술이 소개되었다. 멀티캐스트 기술은 1992년도에 발표되어 사용되어 오면서 많은 연구에도 불구하고 아직 해결해야 할 몇 가지 문제점들을 내포하고 있다. 사용자의 입장에서보면 네트워크 내에 오류가 발생하지 않는 것이 최선이겠지만, 만약 그러한 오류가 발생한다면 빠른 오류탐지 (detection)와 정확한 지점의 오류탐색 (isolation)이 이루어져야 할 것이다.
오류 탐색의 정의는 오류의 원인이 되는 라우터나 링크의 위치를 찾아내는 것으로 정의할 수 있다. 여기서 오류(fault)라는 용어는 송신자로부터 적어도 하나이상의 수신자의 경로가 변경되는 결과를 가져올 때 사용된다. 오류는 라우터나 링크의 이상이나 심각한 패킷의 손실 등과 같은 문제로부터 야기될 수 있다. 오류탐색은 네트워크 운영자나 시스템 관리자 등과 같이 네트워크를 관리 감독하는 책임이 있는 사람에게 있어 필요한 작업중의 하나이다. 그러나, 멀티캐스트 네트워크에서 오류를 탐색하는 것은 어려운 작업이 되는데, 그 이유로는 그룹 사용자의 동적인 변화나 사용자의 익명성, 피드백(feedback)이 없는 User Datagram Protocol(UDP)의 사용 등과 같은 멀티캐스트의 특성들을 예로 들 수 있다.
멀티캐스트에 있어서의 오류를 탐지하기 위해 지금까지 다수의 방법들이 제안되었지만, 그 대부분은 단일 송신자 세션에서 동작되는 것으로 그 사용이 한정된다는 문제점이 있다. 현재 대규모 복제데이타베이스나 대규모 멀티미디어 회의, 웹 캐쉬 프로토콜과 같은 다양한 다수 송신자 멀티캐스트 세션들이 사용되고 있다. 만약 현재 제안되고 사용되어지는 단일 송신자 세션에서의 오류 탐색 방법들을 다수 송신자 멀티캐스트 세션에 그대로 적용한다면 탐지를 위한 메시지의 수와 오류를 탐색하는데 소요되는 시간들이 기하급수적으로 늘어나게 되는 문제가 있다. 따라서 현재의 단일 송신자 세션에서의 방법들을 직접 적용하는 데에는 근본적인 문제를 해결하기 전에는 한계가 있다.
본 논문에서는 Suppressed One-way Source Probing (SOSP)이라는 다수 송신자 멀티캐스트 세션에서 효율적으로 멀티캐스트 네트워크 오류를 탐지하고 오류지점을 탐색해 내는 방법을 제안한다. 이 방법의 주된 목적은 최소한의 메시지 복잡도(message complexity)를 유지하면서 가능한 빠른 시간 내에 오류의 지점을 탐색해 내는 것이다. 송신자는 주기적으로 자신의 주소를 기록한 조사패킷(probe)을 멀티캐스트 세션으로 전송한다. 중간 경로에 위치한 라우터들은 송신자로부터 보내오는 주기적인 조사패킷에 송신경로를 기록한 후 계속 전송한다. 마지막으로 이 조사패킷을 수신한 수신자는 이 조사패킷을 이용하여 오류지점을 탐색해 낼 수 있다. 송신자가 멀티캐스트 세션으로 조사패킷을 보내는 방법을 사용하므로 source-probing이 되고, 송신자가 조사패킷을 보내면 수신자에게까지 단방향으로만 나아가고 송신자는 어떠한 피드백도 받아보지 않기 때문에 one-way probing이 되는 것이다. 그러나 이러한 one-way source probing을 그대로 다수송신자 멀티캐스트 네트워크에 적용한다면 몇가지 문제를 야기시키는데 첫째, 조사패킷 폭주 문제를 야기시킬 수 있으며, 둘째, 라우터의 성능저하, 셋째, 수신자의 처리능력 저하 등의 문제를 야기할 수 있다. 따라서 본 논문에서는 그 효율성과 성능을 향상시키기 위해 조사패킷들의 병합 기법(suppression mechanism)을 고안하여 적용하였다. 멀티캐스트 트리내의 라우터들은 조사패킷 폭주 문제를 해결하기 위해 조사패킷들을 병합하므로 Suppressed One-way Source Probing (SOSP)라고 명칭하게 되었다.
SOSP의 성능을 측정하기 위해 두 가지의 계량지수를 사용하였다. 첫 번째 계량지수는 메시지 복잡도(message complexity)이다. 이는 오류가 발생한 이후 모든 수신자가 오류를 탐색해내기 전까지의 멀티캐스트 세션 내에 발생한 수신자와 라우터에게 보내어진 조사패킷의 수이다. 두 번째 계량지수는 오류탐색시간으로 모든 수신자가 오류를 탐색할 때까지 소요된 시간을 계량지수로 사용한다.
또한 현 인터넷 구조와 유사한 모델을 생성하기 위해 GT-ITM 제작도구를 사용하였고, 여기서 생성된 인터넷 구조를 모델로 적용하여 네트워크의 동작실험을 가능하게 해주는 ns-2시뮬레이터를 이용하여 실험을 실시하였다. 각종 변수, 즉 사용자 수, 패킷 손실률, 링크전송시간(RTT), 다양한 링크 대역폭, 송신자의 조사패킷 발생간격 등을 고려하여 실험한 결과 오류탐색시간을 평균적으로 최소화시켜주는 어떤 병합대기시간 (τ)이 존재한다는 것을 발견 할 수 있었다. 또한 실험결과로서 최적병합대기시간, τ는 송신측에서의 조사패킷 발생간격 (δ)에 의존적이며 어떤 함수로 나타낼 수 있음을 발견할 수 있었다. 본 논문에서 제안하는 SOSP는 확장성 문제도 해결함과 동시에 메시지 복잡도와 오류 탐색시간도 대폭 감소시키는 것으로 나타났다. 실 네트워크에서의 적용을 위해 네트워크 상태에 따라 최대한의 성능을 제공하는 최적의 병합대기시간을 계산하기 위해 최적 병합대기시간과 송신자 조사패킷 발생간격간의 함수를 나타내는 방정식을 유도해 내었으며 이러한 함수의 추정회귀식을 구하기 위해 단순회귀분석모델을 사용하여 방정식을 유도해 내었다.
이렇게 유도된 추정회귀식을 이용하면 송신자의 조사패킷 발생간격에 따른 라우터에서 조사패킷들에 대한 최대한의 성능을 제공하는 조사패킷 병합대기시간을 계산해 낼 수 있다. 이 방정식은 실험을 통하여 유도되었지만, 실제 네트워크에 적용하기 위한 추정값으로 사용될 수 있을 것이라고 기대한다.
