# Introduction

ontent Delivery Network (CDN) is a large distributed network of multiple data centers scattered over the earth surface [1]  [3]. Today CDNs deliver a huge number of internet content including text, scripts and images and also on-demand streaming media files. Content providers pay CDN operators (e.g. Akamai, Mirror Image Internet etc.) for delivering the aforesaid contents to their customer to improve the overall network performance [2].

In this paper we have introduced a tool for partitioning earth surface using K-d Tree and also a closest edge server is selected based upon proposed least response time load balancing strategy. II.


# Background Studies a) Content Delivery Network (CDN)

Increasing the global availability of the internet content, improving the page load time and reducing the bandwidth cost CDN edge servers are scattered over the earth surface. When users from different location are requesting for a particular web content which is algorithmically direct to the nearest edge server to achieve the goal. In this paper we have instigated a technique for partitioning earth surface using the K dimensional tree (K-d tree) and select the nearest edge server using least response time load balancing method which is discussed below.


# b) K-dimensional Tree (K-d tree)

K-d Tree is space partitioning data structure for arranging coordinate points (latitude, longitude) over the earth surface. It can be sub-divided the earth surface into a non-overlapping regions [4] [5] [7]. In this context we have described an efficient edge server searching technique using K-d tree.


# c) Least Response Time

The Least Response Time is a one of the most popular load balancing technique is used in this context [13]  [14]. Using the aforesaid load balancing algorithm, to regulate how to dispense load among the edge servers. This paper we have used the network "ping" command to get average response time of the edge servers which are scattered over the earth surface [10].


# III.


# Proposed Algorithm

In our proposed algorithm we have prepared an efficient tool for CDN provider which is supervising a CDN to select low latency edge server. The set of edge servers are considered as the set of coordinate points P (e.g. latitude and longitude) scattered over geographical region and here we build a K-d tree using P which is scattered over the earth surface as shown in figure 2 and logically partition the edge servers into a nonoverlapping region as like figure 3 [6]. Using function kd_closestpointsearch, we have found nearest edge servers of the current location of end-user (e.g. Kolkata) [8] [9] [11]. Then we can calculate accurate network latency using "ping" command over the closest edge servers' IP address to find the minimum average latency time for delivering web content of a particular host server [10]. Executing "ping" command we get status
( D D D D D D D D )
Year 2014 G and result information of the edge server, if the status value is 0 means server is active otherwise 1 signifies the server is dead.

Our proposed algorithm is developed using Matlab R2012b which is described below [11] [12]. In figure 3, the black maker is depicted that the current location of end-user and the closest edge server, among different edge servers, is waiting to send the web content to the end user that is our primary challenge.   


# Simulation analysis

Step 1 : Latitude and Longitude value of different edge servers are assigned in lat and lon array variables, which are enlisted in table 1    Step 2 : The IP Address of different location of edge servers are assigned in ipaddr variables and the IP Address of edge servers along with domain names are listed in table 3.

Step 3 : The edge servers are decomposed using K-d tree as shown in figure 3.

Step 4 : Using kd_closestpointsearch function we have search closest edge server of the current location of end-user and consequently find out the accurate network latency time using "ping" command.

Step 5 : The connection is established between least average response time active edge server located at Singapore and end-user from Kolkata for sending the web content as shown in figure 4.


# V. conclusion

Our proposed tool and simulation results proclaim minimum network latency and minimum packet loss in selection of closest edge server over the earth surface. In this paper we have used K-d tree algorithm for decomposing the earth surface. Usage of kd_closestpointsearch method helps us to find the nearest edge server of the end-user. Our proposed tool can be used in wireless network and wired network for delivering the web content efficiently to improve the throughput of total network. 


# Global Journal of Computer Science and Technology
1![Figure 1 : An example of Content Delivery Network over the earth surface.](image-2.png "Figure 1 :")
2![Figure 2 : Location of edge servers over the earth surface](image-3.png "Figure 2 :")
3![Figure 3 : Location of edge servers over the earth surface using K-d Tree a) Algorithm for selecting edge server using K-d Tree 1. plot_stuff ?1 2. if (plot_stuff) 2.1 close all; end 3. A set lat = {lat 1 , lat 2, lat 3 , ?, lat M } of latitudes are assigned in [1 × M] array 4. A set lon = {lon 1 , lon 2 , lon 3 , ?, lon M } of longitudes are in [1 × M] array 5. sz = size(lon) 6. for i ?1 to sz 6.1 if lon(i) <= 0 6.1.1 lon(i) = lon(i)+360 6.2 end](image-4.png "Figure 3 :")
4![Figure 4 : Nearest edge server selection by our proposed methodology, example Selected edge server Singapore(Red Marker) & User's current location Kolkata (Black Marker)](image-5.png "Figure 4 :")
![](image-6.png "Volume")
1Year 201415Volume XIV Issue III Version ID D D D D D D D ) G(Location of edge server Kolkata Singapore Colombo London Chicago New Delhi Ankara Islamabad Santiago Mexico Kingston Buenos AiresLatitude 22.5667°N 1.3000°N 6.9344°N 51.5072°N 41.8819°N 28.6139°N 39.9300°N 33.7167°N 33.4500°S 19.000°N 44.2333°N 34.6033°SLongitude 88.3667°E 103.8000°E 79.8428°E 0.1275°W 87.6278°W 77.2089°E 32.8600°E 73.0667°E 70.6667°W 99.1333°W 75.6919°W 58.3817°WGlobal Journal of Computer Science and TechnologyHarare17.8639°S31.0297°ECape Town33.9253°S18.4239°ECanberra35.3075°S149.1244°E
2Location ofLatitudeLongitudeModifiedEdgeLongitudeServersKolkata22.566788.366788.3667Singapore1.3000103.8000103.8000Colombo6.934479.842879.8428London51.5072-0.1275359.8725Chicago41.8819-87.6278272.3722New Delhi28.613977.208977.2089Ankara39.930032.860032.8600Islamabad33.716773.066773.0667Santiago-33.4500-70.6667289.3333Mexico19.0000-99.1333260.8667Kingston44.2333-75.6919284.3081Buenos Aires-34.6033-58.3817301.6183Harare-17.863931.029731.0297Cape Town-33.9253-18.4239341.5761Canberra-35.3075149.1244149.1244
3LocationIP AddressDomain Nameof EdgeServersKolkata203.197.118.81www.jaduniv.edu.inSingapore137.132.21.27www.nus.edu.sgColombo192.248.17.88www.cmb.ac.lkLondon212.113.11.22www.lse.ac.ukChicago198.101.129.15www.uchicago.eduNew Delhi103.27.9.20www.du.ac.inAnkara80.251.40.153www.ankara.edu.trIslamabad61.5.158.124www.islamabadairport.com.pkSantiago158.170.64.116www.udesantiago.clMexico128.123.3.2www.nmsu.eduKingston130.15.126.136www.queensu.caBuenos190.224.163.23www.buenosairesherald.coAires4mHarare196.201.17.237www.caaz.co.zwCape41.72.141.237www.capetown.travelTownCanberra137.92.97.88www.canberra.edu.au
4LocationIP AddressStatus Averageof Edgetime(ms)ServersCanberra137.92.97.88DeadRequest timedoutKolkata203.197.118.81Active260Colombo192.248.17.88ActiveDestinationhostunreachableSingapore137.132.21.27Active238
			© 2014 Global Journals Inc. (US)Response Time load balancing algorithm is introduced to
			© 2014 Global Journals Inc. (US)
		
		
			

				


* 
	
		The Akamai Network: A Platform for High Performance Internet Applications
		
			ENygren
		
		
			RKSitaraman
		
		
			JSun
		
	
	
		ACM SIGOPS OSR
		
			44
			3
			
			2010
		
	




* 
	
		Globally Distributed Content Delivery
		
			JParikh
		
		
			HProkop
		
		
			RSitaraman
		
		
			JDilley
		
		
			BMaggs
		
		
			BWeihl
		
	
	
		IEEE INTERNET COMPUTING
		
			
			2002
		
	




* 
	
		Scaling a Monitoring Infrastructure for the Akamai Network
		
			TRepantis
		
		
			JCohen
		
		
			SSmith
		
		
			JWein
		
	
	
		ACM SIGOPS Operating Systems Review
		
			44
			3
			
			2010
		
	




* 
	
		Multidimensional binary search trees used for associative searching
		
			JLBentley
		
		10.1145/361002.361007
	
	
		Communications of the ACM
		
			18
			9
			509
			1975
		
	




* 
	
		Introduction to kd-trees
		
			SChandran
		
		
		
			University of Maryland Department of Computer Science
		
	




* 
	
		Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries
		
			JBRosenberg
		
		10.1109/TCAD.1985.1270098
	
	
		IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
		
			4
			1
			
			1985
		
	




* 
	
		An introductory tutorial on KD trees
		
			AMoore
		
		
	




* 
	
		Fast algorithms for the all nearest neighbors problem
		
			KLClarkson
		
		10.1109/SFCS.1983.16
	
	
		24th IEEE Symp. Foundations of Computer Science, (FOCS '83)
				
			1983
			
		
	




* 
	
		An O(n log n) Algorithm for the All-Nearest-Neighbors Problem
		
			PMVaidya
		
		doi:10. 1007/BF02187718
	
	
		Discrete and Computational Geometry
		
			4
			1
			
			1989
		
	




* 
	
		An Efficient Edge Servers Selection in Content Delivery Network Using Voronoi Diagram
		
			DSarddar
		
		
			SRoy
		
		
			RBose
		
		
			2014
			IJRITCC
			
		
	




* 
	
		An Algorithm for Finding Best Matches in Logarithmic Expected Time
		
			JHFriedman
		
		
			JBentely
		
		
			RAFinkel
		
	
	
		ACM Transactions on Mathematical Software
		
			3
			
			1977
		
	




* 
	
		Kd tree implementation in Matlab
		
			PVemulapalli
		
		
		
			2010
		
	
	Retrieved from MATLAB CENTRAL website




* 
	
		
		
			VPPatel
		
		
			HDPatel
		
		
			JPPatel
		
	
	
		A Survey on Load Balancing in Cloud Computing. IJERT
		
			9
			1
			2012
		
	




* 
	
		Load Balancing in cloud computing
		
			FFKherani
		
		
			JVania
		
		
			2014
			IJEDR
			
		
	




* 
	
		Green data center: how green can we perform
		
			RMata-Toledo
		
		
			PGupta
		
	
	
		Journal of Technology Research
		
			2
			1
			
			2010
			Academic and Business Research Institute