연속적 멀티미디어 트래픽의 서비스 질 보장을 위한 스케쥴링

길아라 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.1

분산 환경의 많은 멀티미디어 응용들은 연속적 음성/화상 자료들을 위한 실시간 특성을 가지는 패킷들을 생성하고, 실시간 태스크 스케줄링 이론에 따라 이들을 전송한다. 본 논문에서는 광대역폭 통신망을 기반으로 하는 분산 멀티미디어 응용의 연속 미디어를 위한 트래픽의 특성을 모델링하고. 보다 사용자의 요구에 따른 서비스 질의 보장을 위하여 비선점적 경성 실시간 태스크 스케줄링 이론인 PDMA 알고리즘을 도입한다. 또한. 응용 시스템의 고 품질 서비스를 유지하기 위하여 새로운 트래픽 발생 요청이 현재 진행 중인 서비스 내용에 영향을 주지 알도록 제어하는 사용권 제어 기법을 제안한다. 제안하는 사용권 제어 기법은 PDMA 알고리즘을 위한 충분조건식이기 때문에 이를 만족하는 메시지 집합에 대하여 PDMA 알고리즘은 항상 실행가능한 스케줄을 찾을 수 있다. 따라서, 새로운 요청을 포함하는 전체 메시지 집합이 제안하는 사용권 제어 기법의 조건들을 만족하면, 새로운 요청에 의한 트래픽의 발생을 허용한다. 그렇지 않은 경우 새로운 요청을 거절한다. 끝으로 본 논문에서 제안하는 사용권 제어 기법을 이용하는 스케줄링의 실용성을 입증하기 위한 모의실험 결과를 보인다 Many of multimedia applications in distributed environments generate the packets which have the real-time characteristics for continuous audio/video data and transmit them according to the teal-time task scheduling theories. In this paper, we model the traffic for continuous media in the distributed multimedia applications based on the high-bandwidth networks and introduce the PDMA algorithm which is the hard real-time task scheduling theory for guaranteeing QoS requested by the clients. Furthermore, we propose the admission control to control the new request not to interfere the current services for maintaining the high quality of services of the applications. Since the proposed admission control is sufficient for the PDMA algorithm, the PDMA algorithm is always able to find the feasible schedule for the set of messages which satisfies it. Therefore, if the set of messages including the new request to generate the new traffic. Otherwise, it rejects the new request. In final, we present the simulation results for showing that the scheduling with the proposed admission control is of practical use.

연속적 멀티미디어 트래픽의 서비스 질 보장을 위한 스케쥴링

길아라 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.27 No.6

Many of mutlimedia applications in distributed environments generate the packets which have the real-time characteristics for continuous audio/video data and transmit them according to the real-time task scheduling theories.In this paper, we model the traffic for continuous media in the distributed multimedia applications based on the high-bandwidth networks and introduce the PDMA algorithm which is the hard real-time task scheduling theory for guaranteeing QoS requested by the clients. Furthermore, we propose the admission control to control the new request not to interfere the current services for maintaining the high quality of services of the applications. Since the proposed admission control is sufficient for the PDMA algorithm, the PDMA algorithm is always able to find the feasible schedule for the set of messages which satisfies it. Therefore, if the set of messages including the new request satisfies the conditions of the proposed admission control, it admits the new request to generate the new traffic. Otherwise, it rejects the new request. In final, we present the simulation results for showing that the scheduling with the proposed admission control is of practical use. 분산 환경의 많은 멀티미디어 응용들은 연속적 음성/화상 자료들을 위한 실시간 특성을 가지는 패킷들을 생성하고, 실시간 태스크 스케쥴링 이론에 따라 이들을 전송한다.본 논문에서는 광대역폭 통신망을 기반으로 하는 분산 멀티미디어 응용의 연속 미디어를 위한 트래픽의 특성을 모델링하고, 보다 사용자의 요구에 따른 서비스 질의 보장을 위하여 비선점적 경성 실시간 태스크 스케쥴링 이론인 PDMA 알고리즘을 도입한다. 또한, 응용 시스템의 고 품질 서비스를 유지하기 위하여 새로운 트래픽 발생 요청이 현재 진행 중인 서비스 내용에 영향을 주지 않도록 제어하는 사용권 제어 기법을 제안한다. 제안하는 사용권 제어 기법은 PDMA 알고리즘을 위한 충분조건식이기 때문에 이를 만족하는 메시지 집합에 대하여 PDMA 알고리즘은 항상 실행가능한 스케쥴을 찾을 수 있다. 따라서, 새로운 요청을 포함하는 전체 메시지 집합이 제안하는 사용권 제어 기법의 조건들을 만족하면, 새로운 요청에 의한 트래픽의 발생을 허용한다. 그렇지 않은 경우 새로운 요청을 거절한다. 끝으로 본 논문에서 제안하는 사용권 제어 기법을 이용하는 스케쥴링의 실용성을 입증하기 위한 모의실험 결과를 보인다.

스니핑 공격에 대응하는 애드-혹 무선 센서 네트워크를 위한 보안 라우팅 프로토콜

길아라(A Ra Khil) 한국정보과학회 2013 정보과학회논문지 : 정보통신 Vol.40 No.1

단일 경로 라우팅을 통하여 유효정보를 전송하는 무선 센서 네트워크는 유효정보를 도청하고자 하는 악의적인 스니핑 공격에 더 취약하다. 본 논문에서는 전송하고자 하는 유효 정보의 분할된 각 부분 정보만을 포함하는 패킷들을 각기 다른 경로를 통하여 서로 일정 거리를 유지하도록 하여 전송함으로써 스니핑 공격에 대응할 수 있는 애드-혹 무선 센서 네트워크를 위한 다중 경로 보안 라우팅 프로토콜을 제안한다. 분할된 부분 정보를 포함하는 패킷들을 다중 경로를 통하여 전송하는 방법은 유효 정보의 도청의 위험률을 현저하게 줄일 수 있다. 제안된 다중 경로 보안 라우팅 프로토콜의 단일 경로 라우팅 프로토콜 대비 향상된 보안성과 에너지 효율성은 NS-2를 이용한 모의실험 결과로 나타내 보인다. The wireless sensor network transferring packets with the valid information via a single-path routing is more vulnerable to the malicious sniffing attack which tries to eavesdrop on the valid information. In this paper, we propose a multi-path secure routing protocol for ad-hoc wireless sensor networks transferring packets which include parts of the valid information to the sink node through the multiple-paths against sniffing. Transferring packets with parts of the valid information over the multiple-paths significantly reduces the risk of the eavesdropping on the valid information. The enhanced security and the energy efficiency of the proposed multi-path routing protocol are shown by the simulated results using the NS-2 by comparing with single-path routing protocol.

에너지 효율적인 격자형 무선 센서 네트워크를 위한 비 중복 방향성 메시징 프로토콜

길아라(A Ra Khil) 한국정보과학회 2013 정보과학회논문지 : 시스템 및 이론 Vol.40 No.1

저 전력 기술은 제한된 자원을 가진 무선 센서 네트워크의 생존기간 연장을 위하여 요구되는 가장 중요한 기술이다. 특히, 노드들의 중복된 메시지 송수신 및 불필요한 통신 참여를 줄이는 방법은 저전력 무선 센서 네트워크의 핵심 기술이다. 방향성 메시징(Directional Messaging: DM) 프로토콜은 방향성 정보를 포함하는 메시지를 네트워크의 특정 영역으로만 전송하도록 함으로써 노드들의 불필요한 통신 참여를 줄이는 에너지 효율적인 메시지 프로토콜이다. 그러나 방향성 메시징 프로토콜은 탐색 영역 경계선 주변에 위치한 노드들이 중복된 메시지를 송·수신한다는 문제가 있다. 본 논문에서는 격자형 토폴로지를 기반으로 하는 무선 센서 네트워크를 위한 방향성 메시징 프로토콜의 탐색 영역의 경계선 근접 노드들의 중복된 메시지 송수신을 줄임으로써 전체 에너지 효율성을 개선하는 비 중복 방향성 메시징 프로토콜을 제안한다. 제안된 프로토콜의 기존의 방향성 메시징에 비하여 향상된 에너지 효율성은 NS-2를 이용한 모의실험 결과로써 나타내 보인다. The low-power technology is the most important technology required to prolong the network lifetime of wireless sensor network with limited resources. Especially, reducing redundant message transmission and unnecessary communication participation is the core of the low-power wireless sensor network. The Directional Messaging (DM) protocol is the energy efficient message protocol which reduces unnecessary communication participation by sending messages with directional information only to the specified area in a network. However, there is the problem in the DM that the border nodes of search areas receive and send redundant messages. In this paper, we propose the non-redundant directional messaging protocol which improves the energy efficiency of wireless sensor network by reducing redundant message transmission on the border nodes of search areas in the DM protocol. We also show the improved energy efficiency of the proposed protocol comparing with the Directed-Messaging protocol by the simulated results using NS-2 simulator.

연속적 미디어의 서비스 질 보장을 위한 스케쥴링

길아라(Ara Khil),구제웅(Jewoong Ku) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

분산 환경의 많은 멀티미디어 응용들은 연속적 음성/화상 자료들을 위한 실시간 특성을 가지는 패킷들을 생성하고, 실시간 태스크 스케쥴링 이론에 따라 이들을 전송한다. 본 논문에서는 광대역폭 통신망을 기반으로 하는 분산 멀티미디어 응용의 연속 미디어를 위한 트래픽의 특성을 모델링하고, 보다 사용자의 요구에 따른 서비스 질의 보장을 위하여 비선정적 경성 실시간 태스크 스케쥴링 이론인 PDMA 알고리즘을 도입한다. 또한, 응용 시스템의 고 품질 서비스를 유지하기 위하여 새로운 트래픽 발생 요청이 현재 진행 중인 서비스 내용에 영향을 주지 않도록 제어하는 사용권 제어 기법을 제안한다. 제안하는 사용권 제어 기법은 PDMA 알고리즘을 위한 충분조건식이기 때문에 이를 만족하는 메시지 집합에 대하여 PDMA 알고리즘은 항상 실행가능한 스케쥴을 찾을 수 있다. 따라서, 새로운 요청을 포함하는 전체 메시지 집합이 제안하는 사용권 제어 기법의 조건들을 만족하면, 새로운 요청에 의한 트래픽의 발생을 허용한다. 그렇지 않은 경우 새로운 요청을 거절한다.

에너지 효율성 향상을 위하여 방향성 메시징을 사용하는 수정된 지그비의 설계 및 구현

길아라(A-Ra Khil) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.10

지그비는 저 전력, 저 비용, 낮은 데이터 전송 속도의 특징을 가지는 무선 개인 망(Low Rate Wireless Personal Area Networ: LR-WPAN)의 표준이다. 방향성 메시징 기법은 방송을 사용하는 무선 센서 네트워크에서 방향정보를 가지는 메시지를 특정 영역으로 전송함으로써 중복 메시지 전송을 줄이는 것을 통하여 에너지 효율성을 높이는 프로토콜이다. 본 논문에서는 에너지 효율성 향상을 위하여 방향성 메시징을 지원하도록 수정한 지그비를 사용하는 실험용 격자형 센서 네트워크를 설계하고 구현한다. 본 논문의 실험용 센서 네트워크는 방향성 정보를 사용하도록 수정한 ADV 메시지와 라우팅 관리 모듈을 지원하는 Nano-24 노드로 구성한다. 실험용 센서 네트워크의 에너지 효율 향상성은 실제 ADV 메시지 전송에 따른 실험 결과 분석울 통하여 나타내 보인다. ZigBee is the low power, low cost and low data rate wireless personal area network(LR-WPAN) standard. The Directed-Messaging is the protocol which improves the energy efficiency through reducing the redundant message transmission by transmitting messages with directional information toward the specified sub-network area in wireless sensor network using broadcasting. In this paper, we design and implement the experimental grid sensor network using ZigBee modified by the Directed-Messaging for the energy efficiency improvement. The experimental sensor network in this paper is configured with Nano24 supporting the ADV message and the routing management module modified to use the directional information. The energy efficiency improvement of the experimental sensor-network by evaluating the experimental results according to transmitting ADV message.

고차 논리 표현이 첨가된 Flat Concurrent Prolog

길아라(A R Khil),류기열(K Y Ryu),조정완(J W Cho) 한국정보과학회 1989 한국정보과학회 학술발표논문집 Vol.16 No.1

Flat Concurrent Prolog (FCP)는 일차 논리에 기초를 두고 설계된 언어로서 함수 언어의 고차 논리적 기능을 제공하도록 확장하는 것이 필요하다. 본 논문에서는 Prolog의 확장을 위해 DHD Warren이 제안한 번역 규칙을 응용하여, 술어 변수가 허용된 FCP 프로그램을 동일한 의미의 일차 논리 FCP 프로그램으로 번역하는 전 처리기를 제안함으로써 FCP를 확장한다. 본 논문에서 제안한 확장된 FCP는 일차 논리 언어로서의 언어적 semantics와 선언적 프로그래밍의 특성을 계속 유지하면서, 일차 논리 표현만으로는 구현이 어려운 여러 응용 분야를 지원한다.

초기호출시간이 지정된 실시간 주기적 태스크의 단일 프로세서 시스템 상에서의 비선점적 스케쥴링

길아라(Ara Khil),정의훈(Euihoon Jeong),맹승렬(Seungryoul Maeng) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 새로운 스케쥴링 전략과 새로운 스케쥴링 알고리즘을 제안하고 이들의 성능 분석을 위한 모의실험 결과를 보인다. 본 논문에서 제안하는 스케쥴링 전략은 우선, 태스크들의 주기와 초기호출시간을 이용하여 두 개의 스케쥴링 경계시간을 계산하고, 이들을 이용하여 주어진 문제를 각각 다른 시간구간 내에서 실행가능한 스케쥴을 찾는 두 개의 부-문제로 나눈다. 또한, 스케쥴링 경계시간점들의 효율적인 계산을 위한 각 태스크의 초기호출시간과 주기간의 합수를 찾는다. 본 논문에서 제안하는 스케쥴링 알고리즘은 최소 마감시간 우선 (earliest-deadline-first) 정책에 기반한 휴리스틱을 사용하여 주어진 시간구간 내에서 초기호출시간이 지정된 주기적 태스크 집합의 스케쥴링 성공율을 향상시킨다. 즉, 선택한 태스크의 스케쥴링 전에 다른 태스크들의 마감시간 초과 발생을 예상하여 스케쥴링 순서를 변경하므로써 마감시간 초과 발생을 회피한다. 결국, 제안된 알고리즘은 주어진 시간구간 내에서 최소 마감시간 우선 알고리즘으로 스케쥴링 가능한 태스크 집합에 대해서는 항상 실행가능한 시케쥴을 찾을 수 있다. 끝으로, 모의실험 결과로써 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능을 나타내 보인다.

[서평]Linux Kernel Internals(Second Edition)

길아라(Ara Khil) 한국정보과학회 1999 정보과학회지 Vol.17 No.5

초기호출시간이 지정된 실시간 주기적 태스크의 비선점적 스케쥴링

길아라(Ara Khil),맹승렬(Seungryoul Maeng) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.4

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard 문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 주기적 태스크의 반복성과 예측가능성을 이용하는 새로운 스케쥴링 전략과 새로운 비선점적 스케쥴링 알고리즘을 제안한다. 본 논문에서 제안하는 스케쥴링 전략은 주어진 문제를 각각 주어진 스케쥴링 시간구간내에서 순방향 또는 역방향으로 스케쥴링하는 두 개의 부-스케쥴링 문제로 나눈 후, 이들 두 개의 실행가능한 부-스케쥴들을 적용하는 시간구간에 따라 결합하여 하나의 완전한 실행가능한 스케쥴을 구하는 정적 스케쥴링 전략이다. 이 때, 보다 효율적으로 주어진 문제를 분할하기 위하여 초기호출 시간과 주기와의 관계식을 제시한다. 제안된 스케쥴링 알고리즘은 선택한 태스크 호출을 비선점적 최소 마감시간 우선 (earliest- deadline-first, EDF) 알고리즘으로 스케쥴링할 경우 발생할 수 있는 다른 태스크 호출의 마감시간 초과를 미리 계산한다. 계산 결과, 다른 태스크의 마감시간 초과가 예상되면, 선택한 태스크의 스케쥴링을 연기하므로써 예상된 마감시간 초과를 회피한다. 그렇지 않은 경우, 선택한 태스크 호출은 비선점적 최소 마감시간 우선 알고리즘의 경우와 통일한 방법으로 스케쥴링한다. 제안된 스케쥴링 알고리즘은 최소 마감시간 우선 알고리즘으로 실행가능한 스케쥴을 찾을 수 있는 태스크 집합에 대해서는 항상 실행가능한 스케쥴을 찾을 수 있다. 본 논문에서 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능은 모의실험 결과로써 나타내 보인다. The problem of non-preemptive scheduling of real-time periodic tasks with specified release times on a uniprocessor system is known as NP-hard problem In this paper, we propose the new scheduling strategy and the new scheduling algorithm which use the reperitiveness and the predictability of periodic tasks for improvements of schedulabilities of real-time periodic tasks with specified release times. The proposed scheduling strategy is the static scheduling strategy that suggests dividing the given problem into two subproblems which find feasible schedules in the forward scheduling or in the backward scheduling within specific time intervals and combining the two feasible schedules into a complete feasible schedule for the original problem. We present the release times as a function of periods for the efficient problem division. The proposed scheduling algorithm schedules periodic tasks by using the heuristic that precalculates if the scheduling of the selected task leads that a task misses a deadline when tasks are scheduled by the non-preemptive EDF algorithm. It defers the scheduling of the selected task to avoid the precalculated deadline-missing. Otherwise, it schedules the selected task in the same as the non-preemptive EDF algorithm. Our scheduling algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm. We show the improvements on the performance of the proposed scheduling strategy and scheduling algorithm by simulation results.