As the interest in cloud computing grows ranging from individuals to corporates and governments, efficient service discovery has become paramount for satisfactory user experience. Due to the distributed nature of cloud services we propose an unstructured P2P discovery model for service discovery in cloud environment. Traditional query routing heuristics in P2P systems functions purely at the overlay layer. These heuristics do not posses knowledge of the underlying physical topology which leads to performance bottleneck. This paper addresses this problem by proposing a novel P2P model with the awareness of the underlying network in order to leverage the performance of distributed service discovery in cloud environment. This is achieved by applying the concept of Application Oriented Networking (AON), which has the capability of message level intelligence. Our claim is proved by results obtained through prototype simulation. © 2011 IEEE.