A Packet Scheduling Algorithm for Both Throughput and Delay Differentiated Service with the Granularity of Sessions

Kihyun Pyun,Dong-Ho Cho 한국통신학회 2003 한국통신학회 학술대회논문집 Vol.2003 No.7

스마트폰 앱을 활용한 출석부 구성 및 활용 시스템의 설계와 구현

편기현(Kihyun Pyun) 한국콘텐츠학회 2014 한국콘텐츠학회논문지 Vol.14 No.9

Existing attending management systems require a high cost and are lack of convenience. In this paper, we propose a convenient and practical attending management system as follows: First, our system allows us to construct an attendance book in an easy and simple way. A professor does not have to provide the information of students using the small screen of his smartphone. Instead, each student manages his own information via the app designed for a student in our system. Then the professor can construct the attendance book using another app designed for the professor by confirming the requests from the app designed for a student. Second, our system enables a professor to utilize the pictures of students as well as other information of students to have a good relationship with students. Third, our system provides a functionality of checking attendance automatically by calling the names of students via the app designed for the professor. Then the professor has only to match the name with the face of each student. Fourth, our system provides a functionality of checking attendance in a very fast manner. Our system can complete this behavior within a short time since all students can join the attendance simultaneously by using the app designed for the student. Fifth, our system can prevent an illegal attendance easily by utilizing the distance information. 기존의 출석 관리 시스템은 비용 측면에서 너무 과도하거나 편의성 측면에서 불편한 점이 많다. 편리하고 실용적인 출석 관리 시스템을 위해 본 논문에서 제안한 출석 관리 시스템은 다음과 같은 기능을 제공한다. 첫째, 출석부 구성이 쉽고 간단하다. 교수가 직접 수십 명이 넘는 학생들의 명단을 화면이 작은 스마트폰을 통해서 일일이 작성하는 것이 아니라 학생 개개인이 각자의 학생앱을 통해서 자신의 정보를 기록하고 교수는 교수앱을 통해 출석부 작성 요청을 승인만 하면 출석부가 구성된다. 둘째, 사진과 같이 학생과의 교감을 높일 수 있는 다른 부가 정보도 학생 이름과 함께 편리하게 수집된다. 셋째, 자동 출석 부르기 기능을 제공하여 교수앱을 통하여 이름을 불러주고 교수는 학생들의 얼굴과 이름을 쉽고 편리하게 확인할 수 있다. 넷째, 출석을 부를 시간이 부족한 경우를 위하여 빠른 출석 검사 기능을 제공한다. 교수앱을 통해 빠른 출석을 실행한 후 학생앱을 통해 학생들이 출석을 동시에 수행할 수 있어 수십 초 안에 출석 검사를 완료할 수 있다. 다섯째, 학생앱과의 거리 정보를 활용하여 쉽게 부정 출석을 확인할 수 있다.

Standard ML 프로그램 식들의 유추된 타입들을 보여 주는 도구의 개발

편기현(Kihyun Pyun),이광근(Kwangkeun Yi) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

Standard ML(SML)에서는 함수나 변수의 타입을 프로그래머가 직접 기술할 필요가 없이 컴파일러가 타입 유추를 통해 알아 낸다. 그러나, 정의한 함수나 변수를 사용하거나 타입 오류가 발생시 타입 오류가 발생한 곳을 찾기 위해서는 프로그래머가 직접 타입 유추를 해야한다. 본 연구에서는 TV(Type Viewer)라 불리는 도구를 개발하였다. 이 도구는 Emacs 편집기에서 쉽고 간편하게 SML 프로그램내의 최소 타입(minimal type)을 볼 수 있게 함으로써 프로그램을 작성하거나 타입 오류가 발생한 곳을 찾는데 도움을 준다.

사용자 기반 상대적 차별화를 위한 계층적 결손 보완 라운드 - 로빈 스케줄링 알고리즘

편기현(Kihyun Pyun),이종열(Jong-Yeol Lee),조성익(Sung-Ik Cho) 한국정보과학회 2005 정보과학회논문지 : 정보통신 Vol.32 No.6

네트워크 제공자들뿐만 아니라 인터넷 사용자들도 최선 서비스(best-effort service)를 뛰어 넘어 사용자들 간에 서로 다른 서비스 품질을 받기를 열망하고 있다. 이 논문은 사용자 세션 단위로 차별화 서비스를 제공할 수 있는 알고리즘을 제안한다. 제안하는 알고리즘은 결손 보완 라운드-로빈 알고리즘을 기반으로 확장한 계층적 결손 보완 라운드-로빈 알고리즘이다. 이 알고리즘의 주 장점은 응용의 타입을 별도로 구분하지 않으면서도 FTP와 같이 대역폭에 민감한 응용뿐만 아니라 VoIP와 같이 지연에 민감한 응용의 품질 차별화를 제공할 수 있다는 점이다. 품질 차별화 서비스를 제공함에 있어서 네트워크 제공자 측면에서 중요한 점은 예측성과 제어성이다. 우리는 수학적 분석과 모의실험 실험을 통해서 제안하는 알고리즘이 예측성과 제어성이 기존의 결손 보완 라운드-로빈 알고리즘보다 월등히 뛰어남을 보인다. 그럼에도 불구하고 계층적 결손 보완 라운드-로빈 알고리즘의 구현 복잡도는 O(1)이다. The Internet users as well as network providers are eager to have different qualities of service among users beyond the best-effort. In this paper, we propose a scheduling algorithm that provides a differentiated service in the granularity of user sessions. The proposed algorithm is a Hierarchical Deficit Round-Robin (H-DRR) algorithm that is an extension of an existing DRR algorithm. A main advantage is that H-DRR provides service differentiation for throughput-intensive applications such as FTP as well as delay-sensitive applications such as telnet or VoIP without distinguishing the types of applications. The most importance in providing a service differentiation in term of network providers is to have controllability and predictability. We show that H-DRR is superior to DRR in terms of controllability and predictability through both mathematical analysis and simulation experiments. Nevertheless, H-DRR requires O(1) complexity for implementation.

패킷 스케쥴링을 위한 결손 보완 계층적 라운드로빈 알고리즘

편기현(Kihyun Pyun),조성익(Sung-Ik Cho),이종열(Jong-Yeol Lee) 한국정보과학회 2005 정보과학회논문지 : 정보통신 Vol.32 No.2

지난 십여년동안 각 세션에게 대역폭을 공평하게 분배하기 위한 많은 연구가 수행되었다. 이 문제에 있어서 가장 중요한 도전은 확장성 있는 구현(scalable implementation)을 실현하면서도 동시에 높은 공평성을 성취하는 것이다. 여기서 높은 공평성이란 작은 시간 구간에 대해서도 대역폭이 공평하게 분배되는 것이다. 불행히도 현존하는 스케쥴링 알고리즘들은 확장성 있는 구현에 문제점이 있거나 혹은 공평성이 현저히 낮다는 결점을 갖고 있다. 본 논문에서 우리는 확장성을 잃지 않으면서도 동시에 합리적인 수준의 공평성을 제공하는 패킷 스케쥴링 알고리즘을 제안한다. 제안하는 알고리즘은 결손을 보완하는 계층적 라운드-로빈 알고리즘이다. 계층적 라운드-로빈 알고리즘은 구현 복잡도가 상수 시간인 반면, 성취할 수 있는 공평성은 PGPS(Packet-by-Packet Generalized Processor Sharing) 알고리즘과 비슷함을 보인다. PGPS 알고리즘은 N을 세션 수라고 할 때 정렬된 우선 순위 큐를 사용하기 때문에 O(log N) 구현 복잡도를 가지므로 확장성이 떨어진다. For the last several decades, many researches have been performed to distribute bandwidth fairly between sessions. In this problem, the most important challenge is to realize a scalable implementation and high fairness simultaneously. Here high fairness means that bandwidth is distributed fairly even in short time intervals. Unfortunately, existing scheduling algorithms either are lack of scalable implementation or can achieve low fairness. In this paper, we propose a scheduling algorithm that can achieve feasible fairness without losing scalability. The proposed algorithm is a Hierarchical Deficit Round-Robin(H-DRR). While H-DRR requires a constant time for implementation, the achievable fairness is similar to that of Packet-by-Packet Generalized Processor Sharing(PGPS) algorithm. PGPS has worse scalability since it uses a sorted-priority queue requiring O(log N) implementation complexity where N is the number of sessions.

패킷 네트워크에서 지연과 버퍼 크기 한계를 추출할 수 있는 분석 도구

편기현(Kihyun Pyun),송준화(Junehwa Song),이흥규(Heung-Kyu Lee) 한국정보과학회 2003 정보과학회논문지 : 정보통신 Vol.30 No.5

본 논문은 가변 패킷을 사용하는 일반적인 망에서 실시간 세션이 이종의 여러 스케쥴러들을 통과할 때 네트워크가 보장하는 지연의 한계를 추출하는 범용 도구를 제안한다. 이 도구는 이질적인 각 스케쥴러를 동질적인 서비스 곡선 서버로 특성화한다. 우리는 서비스 곡선 서버가 LR 서버보다 엄격히 큰 범주의 스케쥴러들을 특성화할 수 있음을 보인다. 즉, 모든 LR 서버는 서비스 곡선 서버로 특성화할 수 있고, 또한 RC-EDF와 SC 알고리즘 조차도 서비스 곡선 서버로 정확히 특성화할 수 있음을 보인다. 이와 같이 서비스 곡선 서버는 LR 서버에 비해서 범용성 관점에서 큰 장점이 있으면서도 분석 결과가 정확하다. 우리는 LR 서버들로 분석할 수 있는 네트워크의 경우도 서비스 곡선 서버로 분석했을 때, 두 경우 모두 동일한 지연의 한계를 추출함을 수학적으로 증명한다. In this paper, we propose a general analysis tool that derives guaranteed delay bounds for real-time sessions when those sessions pass through heterogeneous schedulers in general packet networks. This tool characterizes each different scheduler by a homogeneous service curve server. We show that service curve servers can characterize a strictly larger class of schedulers than LR servers. That is, we can characterize not only all LR servers but also RC-EDF and SC scheduler by service curve servers. Even with such advantage over LR servers, service curve servers provide accurate analysis results. We prove mathematically that if we analyze a network that can be analyzed by both LR servers and service curve servers, both cases yield the same delay bound.

CDMA2000 1xEV-DO 이동통신 망에서 일대일 주문형 비디오 서비스를 위한 비디오 트레이스 기반 무선 MAC 스케줄러

편기현(Kihyun Pyun) 한국정보과학회 2009 정보과학회논문지 : 정보통신 Vol.36 No.4

CDMA2000 1xEV-DO 이동통신 시스템에서 주문형 비디오 서비스를 고품질로 제공하면서도 합리적 수준의 시스템 성능을 제공하는 무선 MAC 스케줄러를 제안한다. 제안하는 스케줄러는 응용 계층에 존재하는 비디오 데이터 정보를 MAC 계층에 존재하는 스케줄러가 활용하여 주문형 비디오 서비스의 품질이 개선되도록 한다. 우리는 시뮬레이션 실험을 통해서 제안하는 방식이 이전에 제안된 비디오 트레이스 방식과 비교 했을 때 VBR(Variable-Bit-Rate) 비디오의 비디오 프레임 변화가 클수록 더 뛰어난 품질과 성능을 제공함을 보인다. A wireless MAC scheduler for CDMA2000 1xEV-DO that provides a high level of quality-of-service(QoS) for video-on-demand(VOD) applications while achieving a reasonable level of system throughput is proposed. The proposed scheduler that exists in the MAC layer utilizes the video data information that resides in the application layer such that it improves the QoS for VOD applications. We show by simulations that our approach is better than the previous scheduler which is also based on video traces for VBR videos that have high variability between video frames.

계층간 최적화를 위해 비디오 트레이스에 기반한 무선 MAC 스케줄러

片基鉉(Kihyun Pyun),趙成翊(Seong-Ik Cho) 대한전기학회 2006 전기학회논문지 D Vol.55 No.5

A wireless MAC scheduler that provides a high level of quality-of-service (QoS) for video-an-demand (VOD) applications while achieving a reasonable level of system throughput is proposed. The proposed scheduler considers both channel qualities of mobiles and the urgency of real-time packets coming from VOD applications in a cross-layer approach between application and MAC layers.

고정크기 패킷 네트워크 환경에서 할당율에 비례한 저지연 한계를 제공하는 계층적 라운드 - 로빈 알고리즘

편기현(Kihyun Pyun) 한국정보과학회 2005 정보과학회논문지 : 정보통신 Vol.32 No.2

보장서비스에서 실시간 패킷 스케쥴링 알고리즘은 높은 네트워크 유용도와 확장성있는 구현의 양쪽 모두를 성취해야만 한다. 여기서 네트워크 유용도는 승인하는 실시간 세션의 수를 나타낸다. 불행히도, 현존하는 스케쥴링 알고리즘은 확장성있는 구현에 문제점을 갖거나 성취할 수 있는 네트워크 유용도가 낮다. 가령 타임스템프에 기반한 알고리즘은 N이 세션의 수를 나타낼 때 O(log N) 스케쥴링 복잡도를 가진다. 반면 라운드-로빈 알고리즘은 O(1) 복잡도를 가지지만 성취할 수 있는 네트워크 유용도가 낮다. 이 논문은 확장성을 잃지 않으면서도 높은 네트워크 유용도를 성취할 수 있는 스케쥴링 알고리즘을 제안한다. 제안하는 알고리즘은 서로 다른 시간 구간 크기에 대해서 다중 라운드를 활용하는 계층적 라운드-로빈 (H-RR) 알고리즘이다. 이 알고리즘은 우선 순위 큐를 사용하는 PGPS 알고리즘이 제공하는 것과 비슷한 지연의 한계를 제공하지만, 구현 복잡도가 상수라는 큰 장점을 갖는다. In the guaranteed service, a real-time scheduling algorithm must achieve both high level of network utilization and scalable implementation. Here, network utilization indicates the number of admitted real-time sessions. Unfortunately, existing scheduling algorithms either are lack of scalable implementation or can achieve low network utilization. For example, scheduling algorithms based on time-stamps have the problem of O(log N) scheduling complexity where N is the number of sessions. On the contrary, round-robin algorithms require O(1) complexity, but can achieve just a low level of network utilization. In this paper, we propose a scheduling algorithm that can achieve high network utilization without losing scalability. The proposed algorithm is a Hierarchical Round-Robin (H-RR) algorithm that utilizes multiple rounds with different interval sizes. It provides latency bounds similar to those by Packet-by-Packet Generalized Processor Sharing (PGPS) algorithm using a sorted-priority queue. However, H-RR requires a constant time for implementation.

상수의 데드라인 계산 비용으로 높은 네트웍 유용도를 얻는 서비스 곡선 할당 방식

편기현(Kihyun Pyun),송준화(Junehwa Song),이흥규(Heung-Kyu Lee) 한국정보과학회 2003 정보과학회논문지 : 정보통신 Vol.30 No.4

통합 서비스망은 실시간 응용들에게 고품질의 서비스를 제공하기 위해서 종단간 지연의 한계를 보장해야 한다. 이러한 보장 서비스는 라우터의 출력 포트에 설치되는 실시간 스케쥴러에 의해서 제공된다. 그러나 현재까지 연구된 스케쥴링 알고리즘들은 네트워크 유용도 혹은 확장성(scalability)에 문제점을 갖고 있다. 여기서 네트워크 유용도는 얼마나 많은 실시간 세션들을 승인할 수 있는 지를 의미한다. 본 논문은 서비스 곡선 알고리즘에서 높은 네트워크 유용도와 확장성 양쪽을 모두 성취할 수 있는 서비스 곡선 할당 방식을 제안한다. 서비스 곡선 알고리즘의 가장 큰 특징은 서비스 곡선 할당 방식에 따라서 네트워크 유용도와 확장성 모두가 결정된다는 점이다. 일상적인 믿음과 반대로, 데드라인을 계산할 때 전체 서비스 곡선이 아닌 일부만이 사용됨을 증명한다. 이 사실로부터 우리는 데드라인을 계산하는 비용이 상수 시간인 서비스 곡선 할당 방식을 제안한다. 또한, 수치결과를 통해서 제안하는 방식이 mutirate 알고리즘을 포함한 GPS 알고리즘들보다 더 높은 네트워크 유용도를 성취함을 보인다. 우리가 아는 한, 서비스 곡선 알고리즘이 제안하는 서비스 곡선 할당 방식을 채용하면 동일한 확장성을 갖는 스케쥴링 알고리즘들 중에 가장 높은 네트워크 유용도를 성취한다. Integrated services networks should guarantee end-to-end delay bounds for real-time applications to provide high quality services. A real-time scheduler is installed on all the output ports to provide such guaranteed service. However, scheduling algorithms studied so far have problems with either network utilization or scalability. Here, network utilization indicates how many real-time sessions can be admitted. In this paper, we propose service curve allocation schemes that result in both high network utilization and scalability in a service curve algorithm.In service curve algorithms, an adopted service curve allocation scheme determines both network utilization and scalability. Contrary to the common belief, we have proved that only a part of a service curve is used to compute deadlines, not the entire curve. From this fact, we propose service curve allocation schemes that result in a constant time for computing deadlines. We show through a simulation study that our proposed schemes can achieve better network utilizations than Generalized Processor Sharing (GPS) algorithms including the multirate algorithm. To our knowledge, the service curve algorithm adopting our schemes can achieve the widest network utilization among existing scheduling algorithms that have the same scalability.