종단간 상이한 QoS를 갖는 멀티미디어 연출 재생을 위한 CFG 기반의 변환 경로 생성 알고리즘 A Context Free Grammar based Algorithm for Generating Playable Transcoding Paths of the Multimedia Presentation with Different End-to-End QoS원문보기
멀티미디어 연출을 재생하는 단말기나 통신망이 다양해짐에 따라 멀티미디어 데이터를 저장하고 있는 근원지의 데이터 서비스 품질과 재생하는 목적지의 서비스 품질이 다른 경우가 많이 발생하고 있다. 이러한 멀티미디어 연출을 재생하기 위해서 근원지의 데이터를 목적지에서 요구하는 재생 서비스 품질에 맞추어 변환하는 과정이 반드시 필요하다. 문제는 하나의 멀티미디어 연출 프로그램이라도 그것이 재생되는 단말기나 통신망의 환경에 따라 변환 경로가 달라져야 한다는 점이다. 즉 고정된 변환 경로를 사용할 수 없고 재생되는 단말기나 통신망이 정해지면 그에 맞는 변환 경로를 다시 생성해야 한다는 점이다. 본 논문은 주어진 변환 자원과 통신망을 고려하여 근원지 데이터를 목적지에서 요구하는 재생 서비스 품질에 맞게 변환하는 경로를 찾는 알고리즘과 그 경로가 목적지에서 요구하는 서비스 품질에 맞게 재생 가능한지를 검사하는 방법을 제시한다. 본 논문이 제시한 변환 경로를 생성하는 알고리즘은 변환 자원과 변환 규칙을 문맥 자유 문법(Context Free Grammar)으로 기술 할 수 있도록 함으로 변환 경로를 컴파일러 기법을 이용하여 생성할 수 있도록 하였다. 그리고 재생 가능성을 검사하기 위하여 변환 과정에서 소요되는 시간과 지연 등을 계산하는 방법과 요구하는 시간 내에 이루어 질 수 있는지 검사하는 방법을 제안하였다. 그리고 이러한 방식을 실험실에서 개발한 Transcore라는 멀티미디어 스트림 엔진과 VIP라고 하는 저작도구에 구현하였고 간단한 시나리오에 적용한 결과를 마지막으로 기술하였다.
멀티미디어 연출을 재생하는 단말기나 통신망이 다양해짐에 따라 멀티미디어 데이터를 저장하고 있는 근원지의 데이터 서비스 품질과 재생하는 목적지의 서비스 품질이 다른 경우가 많이 발생하고 있다. 이러한 멀티미디어 연출을 재생하기 위해서 근원지의 데이터를 목적지에서 요구하는 재생 서비스 품질에 맞추어 변환하는 과정이 반드시 필요하다. 문제는 하나의 멀티미디어 연출 프로그램이라도 그것이 재생되는 단말기나 통신망의 환경에 따라 변환 경로가 달라져야 한다는 점이다. 즉 고정된 변환 경로를 사용할 수 없고 재생되는 단말기나 통신망이 정해지면 그에 맞는 변환 경로를 다시 생성해야 한다는 점이다. 본 논문은 주어진 변환 자원과 통신망을 고려하여 근원지 데이터를 목적지에서 요구하는 재생 서비스 품질에 맞게 변환하는 경로를 찾는 알고리즘과 그 경로가 목적지에서 요구하는 서비스 품질에 맞게 재생 가능한지를 검사하는 방법을 제시한다. 본 논문이 제시한 변환 경로를 생성하는 알고리즘은 변환 자원과 변환 규칙을 문맥 자유 문법(Context Free Grammar)으로 기술 할 수 있도록 함으로 변환 경로를 컴파일러 기법을 이용하여 생성할 수 있도록 하였다. 그리고 재생 가능성을 검사하기 위하여 변환 과정에서 소요되는 시간과 지연 등을 계산하는 방법과 요구하는 시간 내에 이루어 질 수 있는지 검사하는 방법을 제안하였다. 그리고 이러한 방식을 실험실에서 개발한 Transcore라는 멀티미디어 스트림 엔진과 VIP라고 하는 저작도구에 구현하였고 간단한 시나리오에 적용한 결과를 마지막으로 기술하였다.
Since various terminals and different networks get involved in playing of a multimedia presentation, the case that the presentation QoS at a destination should be different from the QoS of multimedia data at a source occurs frequently. For playing the multimedia presentation, the multimedia data at ...
Since various terminals and different networks get involved in playing of a multimedia presentation, the case that the presentation QoS at a destination should be different from the QoS of multimedia data at a source occurs frequently. For playing the multimedia presentation, the multimedia data at a source should be transcoded into the multimedia data satisfying the QoS required at the terminal. The problem of generating the transcoding path is that, for a given multimedia presentation, different transcoding paths depending the terminal and networks should be generated. That is, a fixed transcoding path cannot be applied to a multimedia presentation. Instead, whenever the terminal and network to play the presentation get determined, a proper transcoding path should be regenerated automatically. In this paper, the algorithm for generating the transcoding path and the method for checking the playability of the generated path are proposed. The generating algorithm adopted the technique of Context Free Grammar in describing the set of transcoding resources and a user's transcoding rules in order to utilize the well-known compiler techniques. For the playability check, a method of computing the transcoding time and the delay time between data units are proposed. Finally all the proposed methods were implemented in the stream engine, called Transcore and the presentation-authoring tool, called VIP, we had developed. And the test results with a sample scenario were presented at the last.
Since various terminals and different networks get involved in playing of a multimedia presentation, the case that the presentation QoS at a destination should be different from the QoS of multimedia data at a source occurs frequently. For playing the multimedia presentation, the multimedia data at a source should be transcoded into the multimedia data satisfying the QoS required at the terminal. The problem of generating the transcoding path is that, for a given multimedia presentation, different transcoding paths depending the terminal and networks should be generated. That is, a fixed transcoding path cannot be applied to a multimedia presentation. Instead, whenever the terminal and network to play the presentation get determined, a proper transcoding path should be regenerated automatically. In this paper, the algorithm for generating the transcoding path and the method for checking the playability of the generated path are proposed. The generating algorithm adopted the technique of Context Free Grammar in describing the set of transcoding resources and a user's transcoding rules in order to utilize the well-known compiler techniques. For the playability check, a method of computing the transcoding time and the delay time between data units are proposed. Finally all the proposed methods were implemented in the stream engine, called Transcore and the presentation-authoring tool, called VIP, we had developed. And the test results with a sample scenario were presented at the last.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이를 위해서 본 논문에서는 변환 자원들에 대한 연결인변환 경로를 응용의 부담을 줄이면서 자동 생성하기 위해서 경험자의 변환 자원에 대한 순서 결정 지침을 시작으로하는 CFG를 이용하였다. 또한 그 결과로 나온 변환 경로가여러 변환 자원을 통과하는 동안 생긴 지연에도 불구하고목적지가 요구하는 데로 재생이 가능한지를 확인하는 방법을 제안하고 구현하였다.
가설 설정
현재 시스템에는 파일 형식 트랜스코더 2개(입력 속성 MPEG-1, 출력 속성 H.263인 것과 입력 속성 H.263, 출력속성 MPEGT인 것), 프레임 율 트랜스코더 4개(입출력 속성이 모두 H.263 인 것, 모두 MPEG-1 인 것, 모두 YUV인것과 모두 RGB인 것), 크기 트랜스코더 4개(입출력 속성이모두 H.263인 것, 모두 MPEGT인 것, 모두 YUW인 것과모두 RGB인 것), 색상 트랜스코더 4개(입출력 속성이 모두 H.263인 것, 모두 MPEGT인 것, 모두 YUV인 것과 모두 RGB인 것), MPEG-1 디코더 1개(입력 속성 MPEG-1, 출 '력 속성 YUV), H.263 디코더 1개(입력 속성 H.263, 출력속성 YUV), H.263 엔코더 2개(입력 속성 YUV, 출력 속성 H263인 것과 입력 속성 RGB, 출력 속성 H.263인 것), MPEG-1 엔코더 2개(입력 속성 YUV, 출력 속성 MPEG-1 인 것과 입력 속성 RGB, 출력 속성 MPEG-1 인 것)를 가지고 있다고 가정한다.
제안 방법
CFG 1은 프레임 율, 크기, 색상, 파일 형식, 디코더의 순서로 변환 자원을 통과하도록 하기 위해서 시작 생성 규칙을 S ::= S. 하였다.
<표 5-3>과 같이 근원지 서비스 품질이 CIF, 30프레임/ 초, 24비트 칼라, MPEG-1 파일이며, 목적지 서비스 품질은 QCIF, 5프레임/초, 8비트 흑백, H.263 파일을 재생하는 경우에 6번의 실험을 하였고, 그 결과를 작성하였다.
생성한다. 그런데 이때 모든 변환 자원들의 연결을 시도하지 않고 경험자의 변환 자원 결합에 대한 지침을시작으로 하는 CFG를 이용하는 방법의 틀을 제안한다. CFG 기반 변환 경로 생성에 대한 전반적인 알고리즘은다음과 같다.
따라서 응용의 부담을 줄이면서 변환경로를 생성하는데 CFG(Context Free Grammar)를 이용하는 방법의 틀을 제공하고, 그 결과로 나온 변환 경로가 재생가능한지를 확인하는 재생 가능한 변환 경로를 생성하는 알고리즘을 제안하였다. 그리고 이러한 방법을 '당 실험실에서개발한 TransCore라는 멀티미디어 스트림 엔진과 멀티미디어 연출 저작 도구인 VIP에 구현하여 적용하였다.
근원지와 목적지가 서로 다른 재생 서비스 품질의 멀티미디어 스트림을 재생하기 위해서 CFG를 이용한 변환 경로를 자동으로 생성하였다. 또 자동으로 생성된 변환 경로상에서 여러 개의 변환 자원을 통과하여 지연이 된 스트림이 목적지가 원하는 대로 재생 가능한지를 재생 가능성 검사로 확인하여 재생 가능하다라고 판단되면, 이 경로는 재생 가능한 변환 경로라고 한다.
그런데 이 경우에 선행변환 자원의 출력 스트림이 갖는 데이터 형식과 동일한 형식의 입력을 수용하는 모든 가용 자원을 연결하다가 목적지가 원하는 서비스 품질에 도달하면 변환 경로의 생성을 중지하도록 한다면, 변환 자원들간에 연결되는 경우의 수가 너무 많아져서 시스템 부담이 증가할 것이다. 따라서 경험자의변환 자원 결합에 대한 지침을 시작으로 하는 CFG를 이용하여 변환 경로를 자동 생성하는 방법의 틀을 제안한다. 둘째, 변환 자원이 연결된 변환 경로일지라도 많은 변환자원을 통과하는 동안 스트림이 지연되어 목적지가 원하는대로 재생이 가능하지 않을 수도 있으므로, 스트림이 목적지가 원하는 대로 도착하는지를 확인하는 방법이 필요하다.
둘째, 변환 자원이 연결된 변환 경로일지라도 많은 변환자원을 통과하는 동안 스트림이 지연되어 목적지가 원하는대로 재생이 가능하지 않을 수도 있으므로, 스트림이 목적지가 원하는 대로 도착하는지를 확인하는 방법이 필요하다. 따라서 변환 경로에 대해서 목적지가 요구하는 대로 재생가능한지를 확인하는 방법을 제공하여 재생 가능한 변환 경로를 생성하는 알고리즘을 구현한다.
그런데 이러한 변환 경로의 생성을 시도할 때 아무런 전략을 고려하지 않는다면, 모든 변환 자원의 종류에 대하여순열의 형태로 연결을 시도할 것이므로 응용 프로그램의 부담이 증가하게 된다. 따라서 응용의 부담을 줄이면서 변환경로를 생성하는데 CFG(Context Free Grammar)를 이용하는 방법의 틀을 제공하고, 그 결과로 나온 변환 경로가 재생가능한지를 확인하는 재생 가능한 변환 경로를 생성하는 알고리즘을 제안하였다. 그리고 이러한 방법을 '당 실험실에서개발한 TransCore라는 멀티미디어 스트림 엔진과 멀티미디어 연출 저작 도구인 VIP에 구현하여 적용하였다.
자동 생성 .방법과 그 변환 경로가 목적지가 원하는대로 재생이 가능한지 확인하는 재생성 검사 방법을 제안한다. 그런데 이러한 변환 경로의 생성을 시도할 때 아무런 전략을 고려하지 않는다면, 모든 변환 자원의 종류에 대하여순열의 형태로 연결을 시도할 것이므로 응용 프로그램의 부담이 증가하게 된다.
그런데 상황에 따라 필요한 변환 자원의 종류가 다르고, 변환 자원이 여러개 필요할 때는 그 변환 자원들을 연결하는 방법도 여러 가지이므로, 변환 경로를 자동적으로 생성하여야 한다. 변환 경로를 생성할 때 모든 변환 자원의 종류에대하여 연결을 시도하면, 응용 프로그램의 부담이 증가하므로, CFG를 이용하는 방법의 틀을 제공하여 응용의 부담을줄이면서 변환 경로를 생성하는 알고리즘을 제안한다.
실제 LDU간 도착시간 간격인 종단간 지연과 요구 LDU 간 도착시간 간격을 비교하여 재생 가능성 검사를 한다. 이것을 식으로 표현하면 다음과 같다.
그런데 환경에 따라 변환 자원의 종류가 다르므로 근원지와목적지가 서로 다른 재생 서비스 품질의 멀티미디어 스트림을 재생하기 위해서는 상황에 따라 모두 다른 변환 자원들의 연결인 변환 경로를 자동적으로 생성하여야 한다. 이를 위해서 본 논문에서는 변환 자원들에 대한 연결인변환 경로를 응용의 부담을 줄이면서 자동 생성하기 위해서 경험자의 변환 자원에 대한 순서 결정 지침을 시작으로하는 CFG를 이용하였다. 또한 그 결과로 나온 변환 경로가여러 변환 자원을 통과하는 동안 생긴 지연에도 불구하고목적지가 요구하는 데로 재생이 가능한지를 확인하는 방법을 제안하고 구현하였다.
이를 위해서 본 논문에서는 변환 자원들의 연결인 변환경로의 자동 생성 .방법과 그 변환 경로가 목적지가 원하는대로 재생이 가능한지 확인하는 재생성 검사 방법을 제안한다.
재생 가능성을 결정하기 위해 목적지의 LDU 도착 시간 간격과 변환 경로의 실제 LDU간 도착시간 간격을 비교한다. 이 두 값을 비교하여 실제 LDU간 도착시간 간격이 목적지의 요구 LDU 도착시간 간격보다 크면, 목적지가 원하는대로 멀티미디어 스트림을 재생할 수 없으므로 재생이 불가능하다라고 판단하고, 그렇지 않으면 재생 가능하다라고판단한다.
그런데 이렇게 연결된 변환 경로는여러 개의 변환 자원을 통과하는 동안 지연되어 목적지가원하는 대로 재생이 가능하지 않을 수도 있으므로, 여러 개의 변환 자원을 통과한 후에도 목적지가 원하는 대로 재생이 가능한지 확인하여야 한다. 즉, 변환 경로가 재생 가능한지를 확인하여 재생 가능한 변환 경로를 생성하도록 한다.
이것을 판단하기 위해서 다음 과정을 거쳐재생성을 검사한다. 즉, 여러 변환 자원을 통과하여 지연된실제 스트림이 목적지에 도착하는 시간 간격과 목적지가 요구하는 스트림의 도착시간 간격을 비교한다. 이 비교에서 실제로 목적지에 도착하는 스트림의 시간 간격이 요구하는 시간 간격보다 크면, 여러 변환 자원을 통과하는 동안 너무 많이 지연되어서 요구대로 재생할 수 없다는 것을 의미한다.
프레임 율 트랜스코더, 크기 트랜스코더, 색상 트랜스코더, 파일 형식 트랜스코더, 디코더, 엔코더의 모든 변환 자원을 통과하는데 걸리는 시간인 지연을 더한 종단간 지연을 구하여 실제 LDU간 도착시간 간격을 파악한다.
대상 데이터
근원지와 목적지의 서비스 품질 정보는 연출 제어 프로그램을 통해서 알 수 있으며, 시스템이 갖고 있는 가용 자원은과 같이 11개와 15개로 실험하였다.
이론/모형
이러한 변환 경로를 아무런전략없이 생성한다면, 존재하고 있는 트랜스코더들의 순열만큼이 되어 시간 복잡도는 N이 필요한 가용 자원의 개수일 때, T(N) = O(N!)이 된다. 따라서, 시스템의 부담을 줄이면서 변환 경로를 자동으로 생성하기 위해서 CFG의 형식을 이용한다.
성능/효과
따라서 경험자의 변환 자원 결합에 대한 지침을 시작으로 하는 CFG를 이용하여 변환 경로를 생성한다면, 가용 자원의 수가 11개의 경우에 생성 규칙 CFG 2, CFG 3에 따라 각각 7개와 4개, 가용 자원의수가 15개의 경우에는 42개씩의 변환 경로를 생성하였다. 이것은 모든 가용 자원의 연결을 시도했을 때보다 훨씬 적은 수의 변환 경로가 생성된것을 의미하는 것으로, 경험자가 제시하는 변환 자원 결합규칙에 의한 변환 경로 생성이 필요함의 의미한다.
비교한다. 이 두 값을 비교하여 실제 LDU간 도착시간 간격이 목적지의 요구 LDU 도착시간 간격보다 크면, 목적지가 원하는대로 멀티미디어 스트림을 재생할 수 없으므로 재생이 불가능하다라고 판단하고, 그렇지 않으면 재생 가능하다라고판단한다. 따라서 모든 변환 경로에 대하여 재생 가능한지그렇지 않은지를 결정한다.
후속연구
따라서 경험자의변환 자원 결합에 대한 지침을 시작으로 하는 CFG를 이용하여 변환 경로를 자동 생성하는 방법의 틀을 제안한다. 둘째, 변환 자원이 연결된 변환 경로일지라도 많은 변환자원을 통과하는 동안 스트림이 지연되어 목적지가 원하는대로 재생이 가능하지 않을 수도 있으므로, 스트림이 목적지가 원하는 대로 도착하는지를 확인하는 방법이 필요하다. 따라서 변환 경로에 대해서 목적지가 요구하는 대로 재생가능한지를 확인하는 방법을 제공하여 재생 가능한 변환 경로를 생성하는 알고리즘을 구현한다.
따라서 근원지와 목적지가 서로다른 재생 서비스 품질의 멀티미디어 스트림을 재생하기 위해서 상황에 따라 다른 변환 자원들의 연결인 변환 경로를자동적으로 생성하여야 한다. 또 멀티미디어 스트림이 여러개의 변환 자원을 통과하는 동안 지연되어 목적지가 원하는대로 재생이 가능하지 않을 수도 있으므로, 여러 개의 변환자원을 통과한 후에도 목적지가 원하는 대로 재생이 가능한지를 확인하여야 한다.
참고문헌 (20)
강의선, '압축상태에서 MPEG2 P프레임을 H.263 P프레임으로 변환하기 위한 Gudided Search 방법 연구', 숭실대학교 대학원 컴퓨터학과 석사학위논문, pp.1-15, 2001
박대원, '휴대폰에 추가 소프트웨어 없이 영상 스트림 전송 방법 연구', 숭실대학교 대학원 컴퓨터 학과 석사학위논문, pp.17-19, 2001
오미경, '이동형 운영체제를 위한 적응적 스트림 처리기 설계 및 구현', 숭실대학교 대학원 컴퓨터학과 석사학위논문, pp. 3-7, 2001
이조원, '압축된 영역에서의 영상 크기 축소 트랜?코더의 성능 향상 방법의 연구', 숭실대학교 대학원 컴퓨터학과 석사학위논문, pp.5-13, 2001
Akbar, Mohammad M., Manning, Eric G., Shoja, Gholamali C., 'Admission control and quality adaptation in the disributed multimedia server system (DMSS),' Proceedings of SPIE Internet Multimedia Management Systems Ⅱ, pp.246-257, 2001
Anderson, D. P, 'Metascheduling for Continuous Media,' ACM Transactions on Computer Systems, Vol.11, No.3, pp.226-252, 1998
Chen MJ. Chu MC. Pan CW. k., 'Efficient Motion-Estimation Algorithm for Reduced Frame-Rate Video Transcoder,' IEEE Transactions on Circuits & Systems for Video Technology, Vol.12, pp.269-275, 2002
Dan, A., Sitaram, D., 'Session Scheduling and Resource Sharing in Multimedia Systems,' Multimedia Information Storage and Management, Kluwer Academic Publishers, pp.257-269, 1996
Guobin Shen, Bing Zeng, Ya-Qin Zhang, and arid Ming L. Liou, 'Transcoder with Arbitrarily Resizing Capability,' Proceedings of the IEEE International Symposium on Circuits and Systems, Vol.5, pp.25-28, 2001
Hafid A, Vonbochmann G, Dssouli R, 'A Quality of Service Negotiation Approach with Future Reservations(NAFUR)-A Detailed Study,' Computer Network & Isdn Systems, Vol.30, No.8, 1998
Huang V. Zhuang WH., 'QoS-Oriented Access Control for 4G Mobile Multimedia CDMA Communications,' IEEE Communications Magazine, Vol.40, No.3, pp.118-125, 2002
Jin Soo Jang, Woo Hyun Ahn, Daeyeon Park, 'A Server Framework Scheduling Multimedia plications 1n. peg Syste Environment,' Proceedings of the 8th International Conference on Parallel and Distributed Systems, pp.562-569, 2001
Kim, Y. H., 'Dynamic QoS Control Technique in Multimedia Multicast Commun ication,' Master's Dissertation, pp.13-21, 1996
Kwang-deok Seo, Seong-cheo Heo, Jae-Kyoon Kim, 'A Rate Control Algorithm Based on Adaptive R-Q Model for MPEG-1 to MPEG-4 Transcoding in DCT Domain,' Proceedings of the 2002 IEEE International Conference on Communications, Vol.1, pp.109-113, 2002
Lin, C., Chang, S., 'Modeling and Transformation of Multimedia Data,' Multimedia Information Storage and Management. Kluwer Academic Publishers, pp.303-307, 1996
Lombaedo, A., Schembra, G., Morabito, G., 'Traffic Specification for the Transm ission of Stored MPEG video on the Internet,' Multimedia, IEEE Transaction, Vol.3, Issue 1, pp.5-10, March, 2001
Niklas Bjork and Charilaos Chistopoulos, 'Transcoder Architechtures for Video Coding,' IEEE Transactions on Consumer Electronics, Vol.44, No.1, February, 1998
Ozgur Gurbuz, Herry Own, 'Dynamic Resource Scheduling for Variable QoS Traffic in W-CDMA,' Proceedings of the 1999 IEEE International Conference on Communications, Vol.2, pp.703-707, 1999
Reghavan, S. V., Tripathi, S. K., 'Networked Multimedia Systems,' Prentice Hall. New Jersey, pp.34-37, pp.72-73, pp.193-194
※ AI-Helper는 부적절한 답변을 할 수 있습니다.