시간 복잡도를 개선한 웹 서버 배치 알고리즘
A Replica Placement Algorithm reducing Time Complexity
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최근 웹 서비스 사용자와 웹상에 대용량 콘텐츠의 급증으로 웹 서버의 부하가 가중되고 서비스의 질이 떨어지는 문제가 발생하였다. 이러한 문제의 해결로 콘텐츠를 다수의 지역 서버에 복제하고 복제 서버로 하여금 클라이언트의 요청을 처리하도록 하여 웹 서버의 부하를 줄이고 트래픽을 분산하는 콘텐츠 분산 네트워크 기술이 사용되고 있다. 그러나, 이러한 다수의 복제 서버 사용하는 환경에서는 복제 서버의 효용을 극대화 할 수 있는 배치 전략이 필요하다. 본 논문에서는 지연과 트래픽에 기반한 각 노드의 비용이 임계 값을 초과하지 않도록 bottom-up 다이나믹 프로그래밍 방법을 이용하여 복제 서버를 배치하도록 함으로써 빠르고 안정적인 서비스가 가능하도록 하였다. 제안하는 알고리즘은 O(n2)보다 작은 O((n-d h )·| ch v |)의 시간 복잡도로 복제 서버 배치 문제를 해결하였다.
Abstract
Recently, contents distribution technologies have been used to cope with the explosive demand for Web services. In this paper, we addressed the issue of the optimal placement of replicas in the environment where Web contents are replicated. We placed replicas so that clients can have access to replicas with the proper delay and bandwidth. We attempted to solve the problem via dynamic programming considering cost of delay and traffic. We have come up with O((n-d h)·| ch v |) time complexity that is less than O(n2). We defined the threshold and proved that our algorithm guarantees the reliable services.
참고문헌 (13)
- "Web Caching and Replication" (2002), Addison Wesley Professional
- "CDN：Content Distribution Network", tr-125, pp.2002~ (2002), School of Computer Science Department, Stony Brook University
- "A Measurement Study of Peer-to-Peer File Sharing Systems" (2002)
- "ICDN Brokering" (2001)
- "On the Placement of Web Server Replicas" (2001)
- "On the Optimal Placement of Web Proxies in the Internet：Linear Topology" (1998)
- "On the Optimal Placement of Web Proxies in the Internet" (1999)
- "On the Placement of Internet Instrumentation" (2000)
- ""Topology-Informed Internet Replica Placement" (2001)
- "Constrained Mirror Placement on the Internet" (2001)
- "The Cache Location Problem", Vol.8,(no.2), pp.568~582 (2000)
- "An Improved Overlay Multicast Scheme for Enhancing Transport Efficiency of High Capacity Contents" (2003), Soongsil University
- "The Japan Cache Project：An Experiment on Domain Cache" (1997)