An exploration technique allows a router to efficiently determine capabilities and configuration of a neighbor (peer) router. In addition, the technique enables peer routers of an adjacency to negotiate a capability "outside" of a protocol, such as a routing protocol, before a routing session is established between the routers. In this context, the term "outside" of the protocol denotes that there is no field within a protocol packet (message) implementation that can be used to negotiate the capability. Moreover, the inventive technique obviates the need to manually configure a router to support a particular capability and interoperate correctly within a network of routers that both support and are unaware of the capability.