시간 복잡도를 개선한 웹 서버 배치 알고리즘

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회논문지C / 11권 / 3호 / 345 ~ 352페이지
· 저자명 : 김선호, 윤미연, 신용태

초록

최근 웹 서비스 사용자와 웹상에 대용량 콘텐츠의 급증으로 웹 서버의 부하가 가중되고 서비스의 질이 떨어지는 문제가 발생하였다. 이러한 문제의 해결로 콘텐츠를 다수의 지역 서버에 복제하고 복제 서버로 하여금 클라이언트의 요청을 처리하도록 하여 웹 서버의 부하를 줄이고 트래픽을 분산하는 콘텐츠 분산 네트워크 기술이 사용되고 있다. 그러나, 이러한 다수의 복제 서버 사용하는 환경에서는 복제 서버의 효용을 극대화 할 수 있는 배치 전략이 필요하다. 본 논문에서는 지연과 트래픽에 기반한 각 노드의 비용이 임계 값을 초과하지 않도록 bottom-up 다이나믹 프로그래밍 방법을 이용하여 복제 서버를 배치하도록 함으로써 빠르고 안정적인 서비스가 가능하도록 하였다. 제안하는 알고리즘은 O(n2)보다 작은 O((n-d h )·| ch v |)의 시간 복잡도로 복제 서버 배치 문제를 해결하였다.

참고자료

· 없음