Abstract: Three-dimensional terrain navigation is a hot application in network quality of geographic information system (GIS), large-scale and high intensity requests of which from clients have posed challenge on terrain data process in GIS servers. Servers are clustered to quicken terrain data response. The success factor of clustered servers is load balancing, which chooses an appropriate server to process requests by considering the type of requests and the status information of servers. Traditional load balancing algorithms either ignore server status resulting in blindness of dispatch decision, or overuse server status causing large overhead in its gather and maintenance. A distributed least cost algorithm is proposed by taking into account the waiting time of terrain data request in server queue and the process time of it in server, based on unit time cost vector. Dispatch probability space for each server is calculated and target server is determined through the landing point of a temporarily generated random number in the probability space. The scalability of the algorithm is satisfactory and the maintenance and update of clustered servers is flexible by configure the unit time cost vector. Extensive simulation indicates that for large-scale and high intensity terrain tile requests the least cost algorithm can balance servers efficiently and response the requests with minimal time. Simulation result also shows that under low intensity requests, the considered load balancing algorithms behave approximately the same, while under high intensity request, it is better to design load balancing by considering queue situation of clustered servers.