스트리밍을 위한 오버레이 멀티캐스트 네트워크 설계

본 논문에서는 멀티캐스트 오버레이 네트워크 설계를 위한 다항 시간 근사 알고리즘을 제시합니다. 이 알고리즘은 용량 및 신뢰성 제약 조건을 최적의 일정 상수 배수 이내로 만족하는 솔루션을 찾으며, 비용은 로그 상수 배수 이내로 맞춥니다. 우리의 알고리즘이 적용되는 네트워크의 클래스에는 Akamai Technologies가 인터넷을 통해 라이브 미디어 스트림을 제공하는 데 사용하는 네트워크가 포함됩니다. 특히, 우리는 세 단계의 노드로 구성된 네트워크를 분석합니다. 첫 번째 단계의 노드는 라이브 스트림이 시작되는 소스입니다. 소스는 각 스트림을 두 번째 단계의 하나 이상의 노드(리플렉터라고 부름)로 전달합니다. 리플렉터는 들어오는 스트림을 여러 개의 동일한 나가는 스트림으로 분할할 수 있으며, 이는 세 번째이자 마지막 단계의 노드(싱크라고 부름)로 전송됩니다. 스트림의 패킷이 한 단계에서 다음 단계로 이동하는 동안 일부 패킷이 손실될 수 있습니다. 싱크의 작업은 동일한 스트림의 여러 인스턴스에서 패킷을 결합(패킷 재정렬 및 중복 패킷 폐기)하여 최소 손실로 단일 인스턴스의 스트림을 형성하는 것입니다. 우리는 네트워크 내의 모든 노드 쌍 간의 손실 비율이 알려져 있으며, 서로 다른 쌍 간의 손실이 독립적이라고 가정하지만, 일부 손실이 상관관계가 있을 수 있는 확장을 논의합니다.