잠재 부하 정보와 HTTP 연결의 에이징을 통한 HTTP 연결 스케줄링 알고리즘

김시연,김성천,Kim Si-Yeon,Kim Sungchun 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.11

HTTP/l.0과 새로운 HTTP/1.1이 함께 사용됨으로써 단일 HTTP 연결이 단일 사용자 요청을 의미하던 환경에서 연구되었던 웹 서버 부하 분산 정책은 수정이 불가피하게 되었다. HTTP/l.0 환경에서는 사용자의 단일 요청만을 가지고 서버를 할당하였으나, 지속적인 HTTP 연결을 지원하게 되면서 하나의 HTTP 연결을 통해 여러 개의 요청을 서버에게 요구할 수 있으므로, 첫 번째로 도착한 요청 하나만으로는 앞으로 그 HTTP 연결을 통해 전송될 사용자의 요청이 서버의 자원을 얼마나 소비하게 될 것인지 전혀 예상할 수 없게 된다. 본 논문에서는 HTTP/1.1을 효율적으로 지원하는 부하 분산 정책을 제안하고자 한다. 이 정책은 사용자의 첫 번째 요청이 전달되면 그 요청의 내장 객체 정보와 현재 살아있는 HTTP 연결의 에이징(aging)을 고려하여 서버를 선택하는 알고리즘이다. 그리고 디스패처의 잘못된 분산 결정으로 인해 시스템의 성능에 누적되는 악영향을 최소화하기 위한 기법도 제시한다. With HTTP/1.0, a single request means a single HTTP connection so that the granular unit of dispatching is the same as real load. But with persistent HTTP connection, multiple requests may arrive on a single TCP connection. Therefore, a scheme that dispatches load at the granularity of individual requests constrains the feasible dispatching policies In this paper we propose a new connection dispatching polity for supporting HTTP/1.1 persistent connections in cluster-based Web servers. When the request of a base html file arrives, the dispatcher gets the subsequent load arriving on that connection using the embedded objects information. After the dispatcher stores the load information in Load Table, the dispatcher employs the connection aging strategy on live persistent connections on the passage of time. The results of simulation show about $1.7\%\~16.8\%$ improved average response time compared to existing WLC algorithm.

다양한 형태의 멀티미디어 데이터를 위한 통신 프로세서의 효율적 관리 방법에 대한 연구

김승욱(Sungwook Kim),김성천(Sungchun Kim) 한국통신학회 2007 韓國通信學會論文誌 Vol.32 No.1B

이질적 웹 서버 클러스터 환경에서 효율적인 우선순위 가중치 맵핑

김진영(Jinyoung Kim),김성천(Sungchun Kim) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.11·12

인터넷 서비스에 대한 요청의 기하학적인 증가와 그 요구의 양과 질에 대한 다양성은 이질적인 능력을 지닌 서버들로 구성된 웹 서버 클러스터를 구축하게 되었다. 클러스터 환경에서 가장 결정적인 역할을 하는 요청 대 서버의 맵핑 기법이 최근 활발히 논의되고 있다. 기존의 맵핑 방식은 요청의 수를 기반으로 서버들이 동일한 양의 부하를 할당받는 것을 목적으로 한다. 하지만, 최근의 다양한 서비스의 증가로 인해 단순한 부하의 균등화만으로 적절한 지연 시간을 기대할 수 없게 되었다. 이에 요구되는 내용을 기반으로 맵핑을 수행하여 응답 시간을 단축하고 전체 서버들의 캐시 적중률도 높이는, 내용-기반 맵핑(content-based mapping)이 최근의 인터넷 환경에서 매우 긍정적으로 평가받고 있다. 이에 본 논문에서는 내용-기반 맵핑 방식을 이질적 환경에 적합하도록 개선시킨 우선 순위 최상 임의 가중치 맵핑(Prioritized Highest Random Weight Mapping, PHRW Mapping)을 제안하였다. 요구되는 내용을 기반으로 맵핑하며, 이질적 서버들에 대해 능력에 따라 우선 순위를 부여하여 높은 성능의 서버가 많은 요청들을 처리하는 방식이다. 이를 통해 이질적인 서버들로 구성된 클러스터에서 매우 효과적으로 적용하며, 특히 지연 시간에 제한을 갖고 있는 실시간 데이타 서비스의 지연 시간을 효과적으로 감소시킨다. 알고리즘과 시뮬레이션을 통하여, 제안된 기법을 사용하는 경우 짧은 지연 시간을 보장하여 전체 시스템의 성능이 향상됨을 증명하였다. For many years clustered heterogeneous web server architecture has been formedon the internet because the explosive internet services and the various quality of requests. The critical point in cluster environment is the mapping schemes of request to server, and recently this is the main issue of internet architecture. The topic of previous mapping methods is to assign equal loads to servers in cluster using the number of requests. But recent growth of various services makes it hard to depend on simple load balancing to satisfy appropriate latency. So mapping based on requested content to decrease response time and to increase cache hit rates on entire servers - so called "content-based" mapping is highly valuated on the internet recently. This paper proposes Prioritized Highest Random Weight mapping(PHRW mapping) that improves content-based mapping to properly fit in the heterogeneous environment. This mapping scheme that assigns requests to the servers with priority, is very effective on heterogeneous web server cluster, especially effective on decreasing latency of reactive data service which has limit on latency. This paper have proved through algorithm and simulation that proposed PHRW mapping show higher-performance by decrease in latency.

오버레이 네트워크에서 멀티미디어 서비스를 위한 적응적인 부하균형 기법

김승욱(Sungwook Kim),김성천(Sungchun Kim) 한국정보과학회 2007 정보과학회논문지 : 정보통신 Vol.34 No.4

셀룰러/랜 기반의 중첩 네트워크는 유선 네트워크에 비해 상대적으로 제한된 대역폭을 가지는 특성으로 인해 효율적인 대역폭 관리에 대한 관심이 증가하고 있다. 본 논문에서는 멀티미디어 중첩 네트워크상에서 트래픽의 이동을 통한 온라인 부하분산 알고리즘을 제안하였다. 이 방법은 각 네트워크간 트래픽 부하의 균형을 통해 지역적으로 발생하는 과부하 현상을 극복하고 높은 대역폭 효율성을 보장한다. 컴퓨터 시뮬레이션을 통하여 대역폭 관리를 위해 제안된 기존의 타 기법들과의 비교, 분석을 수행하여 제안된 방법이 다양한 네트워크 트래픽 상황에서 우수한 성능을 가지는 것을 확인할 수 있었다. New multimedia services over the cellular/WLAN overlay networks require different Quality of Service (QoS). In the cellular/WLAN overlay structure, the main issue of load balancing is to balance the available bandwidth among different networks. In this paper, we propose a new online network management scheme. Our proposed scheme is designed to improve bandwidth utilization by balancing the traffic load between the cellular network and WLANs. Simulation results indicate the superior performance of our proposed framework to strike the appropriate performance balance between contradictory QoS requirements under widely varying diverse traffic loads.

메시지 패싱 시스템의 통신 특성을 고려한 개선된 테스크 스케줄링 기법 (pp.394-396)

노두호(Duho Ro),김성천(Sungchun Kim) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅰ

본 논문에서는 메시지 패싱 시스템에서의 태스크 스케줄링에 대해 다룬다. 병렬/분산 시스템의 어플리케이션의 태스크에 대한 적절한 스케줄링이 이루어지지 않는 경우, 병렬/분산 처리를 이용한 이득을 기대하기는 어렵기 때문에 이 주제에 대한 연구는 컴퓨터 아키텍처의 발달과 함께 지속되고 있으며, 많은 연구들이 태스크 스케줄링에 대한 다양한 기법들을 제안하고 있다. 하지만 통신비용을 데이터를 소모하는 한쪽의 테스크에만 부과하는 기존 기법들을 메시지 패싱 시스템에 적용하기는 부족한 면이 있다. 본 논문에서는 기존 연구의 모델과 메시지 패싱 시스템에서 통신비용이 통신과 관계된 모든 노드에서 발생함을 고려하여 리스트 스케줄링 기법에 기초한 개선된 우선순위 함수와 새로운 프로세서 선택 기준을 제안한다. 이를 두 가지 제안을 적용한 태스크 스케줄링 기법은 메시징 패싱 시스템에서 통신비용이 누적되는 특징으로 발생하는 비효율적인 스케줄링을 개선한다.

메시지 패싱 시스템의 통신 특성을 고려한 개선된 태스크 스케줄링 기법 (pp.347-352)

노두호(Dooho Noh),김성천(Sungchun Kim) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.5·6

본 논문에서는 메시지 패싱 시스템에서의 태스크 스케줄링에 대해 다룬다. 병렬/분산 시스템의 어플리케이션의 태스크에 대한 적절한 스케줄링이 이루어지지 않는 경우, 병렬/분산 처리를 이용한 이득을 기대하기는 어렵기 때문에 이 주제에 대한 연구는 컴퓨터 아키텍처의 발달과 함께 지속되고 있으며, 많은 연구들이 태스크 스케줄링에 대한 다양한 기법들을 제안하고 있다. 기존의 연구들은 공유 메모리 시스템을 가정하여 이루어졌기 때문에, 메시지 패싱 시스템에 기존의 기법을 적용하기가 힘들다. 본 논문에서는 기존 연구의 모델과 메시지 패싱 시스템의 통신 모델의 차이점으로 발생하는 통신비용의 누적을 고려하여 리스트 스케줄링 기법에 기초한 개선된 우선 순위 함수와 새로운 프로세서 선택 기준을 제안한다. 이들 두 가지 제안을 적용한 태스크 스케줄링 기법은 통신비용의 누적을 고려하지 않아 발생하는 비효율적인 스케줄링을 개선한다. This thesis deals with a task scheduling on a message-passing system. Scheduling and allocation are very important issues since the inappropriate scheduling of tasks cannot exploit the true potential of the system and it can offset the grain from parallelization. It is difficult to apply previous schemes to message-passing system, because previous schemes assume the shared memory system. This thesis proposes an modified priority function and processor selection technique that consider the problems caused by the difference between previous models and message-passing environments. The priority function includes the cumulative communication cost which causes task execution to be delayed. The processor selection technique avoids the situation that a child task is assigned to the same processor allocated to its parent task that has other unscheduled child tasks. We showed by some simulations that our modified features of task scheduling algorithm can make the better scheduling results than the previous algorithms.

하이퍼큐브에서 네트워크 전이 기법을 이용한 오류 허용 작업 부하 스케쥴

한상윤(Han SangYoun),김성천(Kim SungChun) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1A

단일 프로세서에서 다중 프로세서 환경으로 이동되는 추세에서 오류에 대한 투명성 보장과 작업부하의 균등화는 시스템 성능에 중요한 결정 요소이다. 작업부하의 균등화 기법인 Dimension Exchange Method는 하이퍼큐브를 위해 설계된 대표적인 기법이며 상당히 빠른 수행을 보장한다. 하지만 균등작업에서 사용되는 작업 정보의 양이 지역적이기 때문에 오류에 대한 적응성이 없어 높은 성능을 얻기가 어렵다. 본 논문에서는 오류가 내재된 하이퍼큐브에서 오류 허용 통신 트리 알고리즘을 제안한다. 이 알고리즘은 AND연산을 이용함으로 차원에 대한 비용함수를 사용하는 기존의 연구에 비해 효율성이 증가되었고 알고리즘이 간단하여 구현이 용이하다는 장점이 있다. 또한 제안된 알고리즘을 이용해 하이퍼큐브 위상을 트리로 변경하여 오류에 대한 투명성을 보장함과 동시에 트리 기반 작업부하 스케쥴링을 수행할 수 있는 타당성을 확보하여 기존의 Dimension Exchange Method의 단점을 극복하였다.

하이퍼 큐브 컴퓨터에서 효과적인 오류 허용 다중전송기법 (pp.273-279)

명훈주(Hunjoo Myung),김성천(Sungchun Kim) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.5·6

하이퍼큐브 컴퓨터는 정규적 구조(regular structure)와 짧은 지름(short diameter) 등 병렬 처리에 적합한 특징을 지니고 있기 때문에 이에 대해 많은 연구가 있어 왔다. 하이퍼큐브의 성능을 좌우하는 중요한 요소 중 하나는 프로세서간의 통신인데, 이 중 다중전송(multicast)은 하나의 전송데이터의 복제, 신호처리 등과 같은 다양한 응용 프로그램에서 이용되는 중요한 통신패턴이다. 병렬 컴퓨터에서 프로세서의 수가 증가함에 따라 구성요소들이 오류가 날 확률도 높아졌다. 이러한 이유로, 오류 난 구성요소들이 있어도 다중 전송이 가능하게 효율적으로 설계하는 것이 중요하다. 이러한 오류 허용 라우팅과 다중 전송은 오류 정보에 따라, 국지적 오류 정보를 바탕으로 하는 전략, 전역적 오류 정보를 바탕으로 하는 전략, 제한된 오류 정보를 바탕으로 하는 전략 등이 있는데, 이 중에서 후자가 정보 수집비용이 적으면서도 좋은 성능을 보인다. 본 논문에서는 최근에 제안된 완전 도달성 정보와 새로 추가한 국지적 정보를 이용해서 라우팅 알고리즘을 제안하고, 이것을 바탕으로 다중 전송 성공률이 높은 새로운 다중 전송 알고리즘을 제안한다. 제안 기법은 완전 도달성 정보와 국지적 정보를 이용하여 우회하는 경우와 다중전송 실패하는 경우를 줄임으로써, 기존의 기법보다 통신량의 차이는 거의 없으면서도 다중전송 성공률을 향상시킬 수 있음을 시뮬레이션을 통해 검증하였다. Hypercube multicomputers have been drawing considerable attention from many researchers due to their regular structure and short diameter. One of keys to the performance of Hypercube is the efficiency of communication among processors. Among several communication patterns, multicast is important, which is found in a variety of applications as data replication and signal processing. As the number of processors increases, the probability of occurrences of fault components also increases. So it would be desirable to design an efficient scheme that multicasts messages in the presence of faulty component.In fault-tolerant routing and mulicast, there are local information based scheme, global information based scheme and limited information based scheme in terms of information. In general, limited information is easy to obtain and maintain by compressing information in a concise format. In this paper, we propose a new routing scheme and a new multicast scheme using recently proposed fully reachability information scheme and new local information scheme. The proposed mulicast scheme increases multicast success possibility and reduce deroute cases. Experiments show that multicast success possibility can increase at least 15% compared to previous method.

태스크 실행 시간을 최적화한 개선된 태스크 중복 스케줄 기법 (pp.549-557)

장세이(Sei-Ie Jang),김성천(Sungchun Kim) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.6

최근 응용 프로그램들은 복잡한 데이타로 구성되어 있기 때문에 이를 효율적으로 처리할 수 있는 분산 메모리 기계(Distributed Memory Machine : DMM)의 필요성이 대두되었다. 특히 태스크 스케줄은 태스크 사이의 통신 시간을 최소화하여 응용 프로그램 전체의 실행 시간을 단축시키는 기법으로서, DMM의 성능을 향상시키는 매우 중요한 요소이다. 기존의 태스크 중복 스케줄(Task Duplicated based Scheduling : TDS) 기법은 두 개의 태스크 사이에 통신 시간이 많이 소요되는 것들을 하나의 클러스터(cluster)로 스케줄함으로써 통신 시간을 단축하여 실행 시간을 향상시키는 기법이다. 그러나 데이타를 전달하는 태스크와 이 태스크로 데이타를 전달받는 태스크 사이의 통신 시간을 최적화 하지 못하는 단점을 가진다. 따라서 본 논문에서는 이 두 태스크 사이의 최적화에 근접한 통신 시간을 갖는 개선된 중복 스케줄 (Modified Task Duplicated based Scheduling : MTDS) 기법을 제안하였다. 이 기법은 데이타를 전달한 태스크들을 클러스터링하기 위해 데이타를 전달받은 태스크에서 최적화 조건을 적용하여 검사한다. 그 결과 태스크 사이의 통신 시간을 단축하여 전체 태스크 실행 시간을 최소화하였다. 또한 시스템의 모델링을 통하여 MTDS 기법이 최상의 경우 TDS 기법보다 태스크 실행 시간을 70% 단축 시켰고 최악의 경우 TDS 기법과 동일한 실행 시간을 얻으므로 제안된 기법이 기존의 기법보다 우수함을 입증하였다. Distributed Memory Machine(DMM) is necessary for the effective computation of the data which is complicated and very large. Task scheduling is a method that reduces the communication time among tasks to reduce the total execution time of application program and is very important for the improvement of DMM. Task Duplicated based Scheduling(TDS) method improves execution time by reducing communication time of tasks. It uses clustering method which schedules tasks of the large communication time on the same processor. But there is a problem that cannot optimize communication time between task sending data and task receiving data. Hence, this paper proposes a new method which solves the above problem in TDS. Modified Task Duplicated based Scheduling(MTDS) method which can approximately optimize the communication time between task sending data and task receiving data by checking the optimal condition, resulted in the minimization of task execution time by reducing the communication time among tasks. Also system modeling shows that task execution time of MTDS is about 70% faster than that of TDS in the best case and the same as the result of TDS in the worst case. It proves that MTDS method is better than TDS method.

하이퍼큐브 다중컴퓨터 시스템에서의 통신 오버헤드를 줄이기 위한 동적 부하균등 기법

임화경(Hwakyung Rim),김성천(Sungchun Kim) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.5

하이퍼큐브 다중컴퓨터 시스템에서 기존의 로드밸런싱 기법들을 하이퍼큐브 구조의 특정인 n 차원에 의한 반복적인 실행으로 2ⁿlog2ⁿ의 통신 오버헤드 비용을 갖는다. 따라서, 이러한 통신 오버헤드를 감소시키기 위하여 하이퍼큐브 구조의 토폴로지와 독립적인 수행을 위해 선형 구조를 기반으로 한 동적인 로드 밸런싱 기법 및 구조를 제안한다. 그리고, 제안한 기법은 통신 오버헤드 비용으로 2 · 2ⁿ-⁴로 감소시켰으며, 이로 인해 시스템의 전체 성능을 약 30% 향상시켰음을 입증한다. The previous strategies of load balancing, on parallel multicomputer systems with the interconnection topology of a hypercube, are iteratively executing schemes based on the dimension of a cube. Hence, the communication overhead is 2ⁿlog2ⁿsteps. In this paper, we propose a new load balancing strategy, which is based on a linear structure to allow execution that is independent of the hypercube topology. We show the effectiveness of the proposed strategy, providing a performance improvement of 2 · 2ⁿ-⁴ in communication overheads, and obtain a speedup in system performance about 30%.