*민* 스토어

*민*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

1개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

[정보통신]연속미디어 전송을 위한 지연 보장 멀티캐스트 루팅 알고리즘 논문

인터넷공학기초 PROJECT학년: 3 성명: 이민규 학번:o 논문 제목: Multicast Routing for Multimedia communicationo 논문 저자: V. Kompella, J. Pascuale, G. Polyzoso 저자의 소속: IEEE/ACM Transaction on Networkingo 본 논문의 입수처 혹은 방법: http://www-cse.ucsd.edu/~pasquale/Papers/multimulti93.pdf연속미디어 전송을 위한 지연 보장 멀티캐스트 루팅 알고리즘 논문1. 요약- 연속미디어나 어느 특정 시간 내에 모든 수신자로의 전송이 요구되는 전송을 위 해서는 전송 지연 시간을 보장하는 새로운 루팅 알고리즘이 요구됨.- 연속 미디어 전송에서 지연 시간을 보장하며 최적의 비용을 갖는 새로운멀티캐스트 루팅 알고리즘을 제안하였고 제안된 알고리즘은 지연을 고려하지않은 비용면에서 KBM 알고리즘, 지연보장에 따른 비용증가도 Kompella알고리즘에 비해 효율적이었다. 또한 시간 복잡도 면에서도 Kompella의 알고리즘이O(△)인반면 제안된 알고리즘은 O()임을 보여 연속 미디어 멀티캐스팅서비스에서 매우 효율적으로 사용할수 있다.- 의존적인 통신을 위해 멀티캐스트 트리 건설을 위해 발견적 교수법을 제안- Source에서 각각의 목적지까지 길들을 따라 끝과 끝을 접하여 지연을 제한.- 경계값과 경계 지연이 독립적인 metrics를 갖는 최소 비용의 멀티캐스트 트리.- 무리한 멀티캐스트 트리를 계산하는 것의 문제는 NP-complete 이다.- 발견적 교수법은 많은 수의 그래프들에 의한 시뮬레이션에 의해 결정된 것처럼비용의 관점에서 좋은 평균임을 증명.2. 서론※ 본 연구의 접근 방법 및 집필(연구) 사유- 고속화와 광대역화 통신망 환경하에 다양한 종류의 서비스들이 개발되어실용화 되고 있다. 비디오나 오디오 분배 서비스, 화상, 회의,분산 데이터 베이스 응용, 컴퓨터 보조 협동 작업 등을 지원하기 위해서는동일한 데이터를 다수의 수신자에게 동시에 전송하는 멀티캐스트 통신이 요구됨- 일반적인 멀티캐스트 루팅은 그래프상의 링크에 단일 요소만을 고려하여 문제를 해결하였다. 예를 들어 비용의 최소화,지연의 최소화,대역폭의 최소화처럼단일 요소를 고려하여 경로를 결정하였으나 통신기술의 발전으로 여러 가지제약 조건들을 고려해야하는 루팅으로 복잡해지고 있음- 비록 속도가 느리지만, 비디오와 오디오 적용이 효과적- 네트워크들에 매우 중요한 기구로서 바라봄- Kadaba 와 Jaffe[6]은 멀티캐스트의 비용과 지연의 두 가지 수단을 최적화하는것을 포함하는 문제점을 연구.- DT와 CT을 최소화 하는 것 사이에 맞을 수 있었는지를 타협점 조사- 우리들의 접근과 [6]의 그것 사이에 주된 차이- 근본적인 차이는 우리들이 경계 비용과 경계 지연이 다른 기능이라고 생각※ 관련 연구의 연구 역사(history)- 멀티캐스트 경로에 가장 좋은 해결책은 트리구조를 포함- 트리에서 효과적인 멀티캐스트 경로 기초를 형성하는 것에 대한 2가지 이유a. 데이타는 트리의 경로들을 따라 다양한 목적지들에 평행하게 전송b. 데이타 복사의 최소수가 트리의 갈래에서 오직 필요한 데이터의중복과 전송- 멀티캐스트 트리 건설을 위한 최적화 목적으로 계발된 알고리즘들은 2가지a. 최소평균경로 지연이다.(멀티캐스트 그룹내의 근원에서 각 목적지까지최소 경로 지연의 평균)?최소 평균 경로 지연 트리는 Dijkstra's shortest path algorithm[2]를사용한 o()로 만들 수 있다.(n은 그래프에서 노드의 개수)b. 효율성의 측정은 비용의 관점에서 멀티캐스트 트리( CT(멀티캐스트 경계 값의 합)?최소 비용 트리는 steiner tree[5]라고 불림.?steiner tree를 발견하는 것의 문제점은 NP-complete 이다.?경계들이 단위 원가를 가지고 있을지라도, 문제는 NP-complete.- 저비용 멀티캐스트 경로 구조 [1], [6], [13], [14]들은 몇몇 알고리즘들은대략적으로 steiner tree를 위해 발견적 교수법에 바탕을 둠.?경험 관찰은 발견적 교수법이 빠르게 near-optimal tree들을 산출한 것.?0()에서 0()까지 분포하면서 알고리듬은 다항 시간 소요.?두 배에 달하는 최적 해결점의 비용 내에 해결점들을 만듬.- 두 개의 수단(CT와 VT)은 대화식 멀티미디어 통신을 위해 좋은 멀티캐스트도로의 특성을 나타내기 위하여 개별적으로 불충분.- 멀티캐스트 경로의 수행은 두개 요소.a. 근원에서 각각의 목적지에 이르는 개별적인 경로를 따라 끝과 끝의지연의 제한.b. 네트워크 대역폭 이용의 관점에서 멀티캐스트의 트리의 최소 비용- 공식에서, 멀티캐스트 트리는 constrained steiner tree 이다.3. 본론※ 연구의 모델링 방법통신망은 비방향성 그래프 G(V,E)로 정의하며 여기서 V는 노드의 집합이며 E는 링크의 집합이다.그래프 G(V,E)는 두 개의 가중치(weight)를 가지는 그래프로 가중치는 다음과 같은 함수로 표현된다.c:C->링크에 대한 비용(cost)d:E->링크에 대한 지연(delay)s⊂V는 송신 노드⊂V는 수신노드 집합m:의 크기n:그래프 내의 노드 수INPUT: 비용 함수 c:E->와 d: E->를 갖는 비방향성 그래프 G=(V,E), 송신노드 s, 수신 노드 집합OUTPUT: 멀티캐스트 트리 TStep1: 수신 shemh부터 그래프를 탐색하면서 탐색되는 노드에 대해 휴리스틱 함수를 적용한다. 동일한 노드가 네 개 이상 탐색될 경우 지연이 가장 적은 노드와 함수 값이 작은 두 개의 노드만 남기고 나머지는 제거하여 지연이 보장되는 후보 트리를 구한다.Step2: Step1에서 구해진 후보 트리에 대해 수신 노드가 아닌 단말 노드(leaf mode)fm,f 제거한다.Step3: Step2에서 구해진 후보 트리 내의 링크 중에서 멀티캐스트 트리 내에 반드시 포함되어야 하는 링크를 선택하여를 만든다.Step4:각각의 수신 노드들을 이에 최단 비용 경로로 연결하여 멀티 캐스트 트리 T를 구한다.※ 연구의 가정 항목가정: 최대 지연 내에 전송 가능한 노드들은 적어도 한 개 이상의 경로가 후보 트리 내에 존재하게 된다.증명: 만일 해가 존재한다면 송신 노드로부터 그 노드까지 하나 이상의 경로가 존재하게 된다. 이는 CST 알고리즘에서 그래프상의 노드를 탐색해 나갈 때 지연이 최소인 경로와 최대 허용 지연 내의 두 개의 후보 경로를 구하게 되는데 이 중에서 지연이 최대인 경로는 해가 존재할 경우 반드시 존재하게 된다.그러므로 해가 존재할 경우 반드시 그 노드로 최대 지연 내로 전송 가능한 경로가 존재한다.※ 모델의 분석 방법 및 분석: 수학적 분석 혹은 시뮬레이션※ 분석의 검토 및 결과CST 알고리즘의 성능 분석을 위하여 SPT 알고리즘과 비교를 해보았다.실험에서 선택되는 노드들은 무작위로 주어졌고, 그 수는 가변적인 형태로 실험하였다. 또한 특정 노드로의 전송이 어떤 경로로도 최대 허용 지연 내로 불가능한 경우는 근본적으로 전송이 불가능하므로 실험에서 배제되었다. 알고리즘의 성능은 비효율성 값으로 평가하였다.비효율성에 대한 식은 다음과 같다.비효율성 = 알고리즘의 비용 / SPT의 비용Fig.7은 수신 노드 집합 변화에 따른 각각의 알고리즘의 비용 변화를 보여준다. 이는 수신 노드의 크기에 따른 알고리즘의 민감도를 보여주는 것이다. 그림에서 알 수 있듯이 노드 증가에 따른 비용증가가 SPT 알고리즘은 CST 알고리즘에 비해 급격히 변화함을 알 수 있다. Fig.8과 10은 각각 노드수와 노드 그룹 사이즈에 대한 비효율성을 나타내고 있다. 그래프에서 볼수 있듯이 SPT 알고리즘은 CST 알고리즘에 비해 약 70%~80% 정도 효율이 떨어짐을 알 수 있다. 그림 4-6에서는 동일한 수신 노드에 대한 최단지연 경로 알고리즘과 Kompella 알고리즘 그리고 DMBT 알고리즘의 비효율성을 보여주고 있다. 실험 결과 최단 지연 경로 알고리즘은 비용에 해한 고려가 없기 때문에 최적의 비용에 대해 1.34배의 높은 비용의 경로가 구해짐을 알 수있다. Kompella 알고리즘은 평균적으로 KMB 알고리즘에 대해 1.1배의 비교적 좋은 성능을 보였다. 제안된 알고리즘이 스테이너 노드를 고려하기 때문에 Kompella의 알고리즘에 비해 좋은 성능을 나타내게 된다. 지연 보장에 대해 각 알고리즘을 평가한 결과 KBM 알고리즘은 비용은 최적에 근사했으나 임의의 노드에 대해 최대 허용 지연 내에 전송 가능한 경로가 존재함에도 불구하고 최대 지연 내에 전송 가능한 경로를 발견하지 못하였다. 그러나 DMBT 알고리즘은 최대 허용 지연 내에 전송 가능한 모든 수신 노드로의 지연을 보장하였다.

공학/기술| 2006.09.04| 9페이지| 1,500원| 조회(272)

멀티캐스트, 광대역, 캐스트, 최소화, 지연, 광대역화통신망

미리보기

닫기