화상회의를 위한 효율적인 온-라인 프레임 스케줄링 알고리즘 = An Efficient On-line Frame Scheduling Algorithm for Video Conferences

국문 초록 (Abstract)

본 논문에서는 화상회의 시스템의 서비스 품질(QoS)을 최대화하기 위해 프레임 복원 태스크들에게 프로세서 시간을 효율적으로 분산하는 방안을 제시하고자 한다. 압축된 프레임은 복원에 소요된 프로세서 시간이 증가함에 따라 복원된 영상의 QoS 또한 증가하는 특성을 가진다. 따라서 각 프레임별 복원영상의 품질은 복원을 위해 주어진 서비스 시간의 QoS 함수로 표현될 수 있다. 또한 각 화상회의 스트림은 연속된 프레임간 밀접한 시간 의존성을 가진다. 이러한 특성과 QoS 함수를 기반으로 본 논문에서는 총 QoS를 최대화하면서 모든 프레임이 아닌 일부 프레임들만 스케줄링하는 온-라인 프레임 스케줄링 알고리즘을 제안한다. 실험 결과 시스템 부하가 증가함에 따라 제안 알고리즘은 기존 EDF에 비해 보다 부드럽게 화질이 감소하고, 연속된 프레임들이 끊김 없이 출력되어 보다 자연스런 화자의 동작을 보일 수 있었다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose an algorithm that distributes processor time to the tasks decoding encoded frames with a goal maximizing total QoS (quality of services) of video conference system. An encoded frame has such a characteristic that the QoS of recovered frame image also increases as the processor time given for decoding the frame gets to increase. Thus, the quality of decoded image for each frame can be represented as a QoS function of the amount of service time given to decode. In addition, every stream of video conference has close time-dependency between continuous frames belonging to the same stream. Based on the time-dependency and QoS functions, we propose an on-line frame scheduling algorithm which does not schedule all frames in the system but just a few frames while maximizing total QoS of video streams in the conference. The simulation results show that, as the system load gets to increase, the proposed algorithm compared to the existing EDF algorithm can reduce the quality of decoded frame images more smoothly and show the movements of conference attendees more naturally without short cutting.

참고문헌 (Reference)

• 1 "Scheduling Tasks with Ready Times and Deadlines to Minimize Average Error"
• 2 "Scheduling Periodic Jobs That Allows Imprecise Results" 1156-1173, 1990
• 3 "Scheduling Algorithms for Multiprogramming in a Hard Real- Time Environment" 20 : 46-61,
• 4 "Scheduling Algorithm for Real-Time Imprecise Computations to Minimize Maximum Weighted Error Using the Linear Programming Method" 33 (33): 1301-1302, July1997.
• 5 "Perceptual Optimization of Image Coding Algorithms" 69-72, 1995.
• 6 "Optimal Reward-Based Scheduling for Periodic Real-Time Tasks" 50 (50): 111-130, feb.2001.
• 7 "On-line Scheduling Policies for a Class of IRIS Increasing Reward with Increasing ServiceReal-Time Tasks," 45 : 802-813, July1996.
• 8 "On-Line Scheduling of Imprecise Computations to Minimize Error" pp. 280-289 : -1992, calif.
• 9 "Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops" 14 : 24-44, 1993.
• 10 "Minimizing Maximum Weighted Error for Imprecise Computation Tasks" 16 : 431-452, 1994.
• 11 "Introduction to Wavelets and Wavelet Transforms" Prentice-hall 1998
• 12 "Intrastream Synchronization for Continuous Media Streams A Survey of Playout Schedulers" 16 (16): 30-40, May2002.
• 13 "Efficient On-line Processor Scheduling for a Class of IRIS Increasing Reward with Increasing Service Measurement and Modeling of Computer Systems" 217-228,
• 14 "Comment on On-line Scheduling Policies for a Class of IRIS Real-Time Tasks" 50 (50): 526-528, May2001.
• 15 "Coding of Moving Pictures and Associated Audio For Digital Storage Media at up to About 1.5 Mbit/s" 1993.
• 16 "An Imprecise DCT Computation Model for Real-time Applications" 153-161, 1997
• 17 "An Empirical Study of Delay Jitter Management Policies" 2 (2): 267-279, 1995
• 18 "Algorithms for Scheduling Imprecise Computations with Timing Constraints to Minimize Maximum Error" 44 (44): 1995.03
• 19 "Algorithms for Scheduling Imprecise Computations with Timing Constraints" 20 (20): 537-552, 1991.06
• 20 "Algorithms for Scheduling Imprecise Computations [for Multiprogramming in a Hard Real- Time Environment" 58 46-68 61, 1973
• 21 "A Jitter Management Policy for Monitoring System using JPEG IEEE Proceedings on Consumer Electronics" 214-215, Oct.1996.
• 22 "A Heuristic Scheduling Algorithm for Reducing the Total Error of an Imprecise Multiprocessor System with 0/1 Constraint" 2 (2): Dec.1997.