Recently, there has been growing interest in IP-over- WDM networks. A set of lightpaths that are established a priori defines the virtual topology of a Wavelength Division Multiplexing (WDM) optical network. Internet Protocol (IP) makes use of virtual topology to route its traffic in the optical form. If a physical link fails, then all lightpaths that are using the failed link also fail and may leave the virtual topology partitioned into a number of sets of nodes. Thus, a node belonging to one set of nodes cannot communicate with nodes in other sets. In such a case, the restoration of connectivity in the virtual topology may be indispensable. Hence, it may be necessary to alter the existing virtual topology in order to restore the connectivity. In this paper, we propose a distributed protocol for the restoration of connectivity in the virtual topology in the event of a link failure. The proposed protocol for connectivity establishment tries to minimize the number of changes committed to the virtual topology and assures all-to-all communication path (either using single hop or multi-hop path) in the virtual topology. The performance of our algorithm is studied based on the results obtained from extensive simulations.