Abstract: Internet host clustering is emerging as a new pretreatment technique for many grid task scheduling algorithms.The efficiency and accuracy of current host clustering algorithms need to be further improved.The Internet host clustering problem is presented and formulated, focusing on grid application with various network performance requirements.A new density-based host clustering algorithm is put forward.The algorithm is evaluated with large scale simulation with over 5000 hosts.Simulation result demonstrates that the algorithm achieves better integrative performance on time, total effective clusters, etc. than the hierarchical and K-means heuristic algorithm.