Ad-hoc networks are an emerging technology with immense potential. Recent advances in high-tech sensors, communication devices and microprocessors has given rise to a growing commercial interest in ad-hoc networks for inter-vehicular communications. Most of the research in inter-vehicular communication systems has focused on driver safety, accident reporting and multi-hop routing. There is an enormous potential for service deployment in such a network, when vehicles need access to services ``anytime, anywhere". The lack of infrastructure, coupled with the time-varying characteristics of vehicular ad-hoc networks, brings about new challenges to the design and deployment of services. This paper addresses these challenges and presents V2V-Net, a vehicle-to-vehicle overlay structure for service deployment in vehicular ad hoc networks. We discuss the main functionalities of the architecture and describe the algorithms for service registration and discovery. The service-architecture also considers the mobility of the vehicles and provides a mechanism by which this can be incorporated into the framework. Finally, the architecture was evaluated using simulations and the results show that the architecture performs well under different network conditions.