Methods and apparatus for efficiently establishing communications connections, e.g., for a secondary application, are described. A device to device communications network has established routing paths, e.g., corresponding to a first application. Different segments of the network use different gateways. Individual communications devices within a segment of the network may have incomplete information on the routing within the segment. A wireless communications device advertises the gateway device which it uses for the first application. A first communications device seeking to establish a communications connection with a second communications device for a second application uses obtained gateway information to make transmission and/or routing decisions, e.g., identifying a third communications device which can bridge a routing path gap between two segments of the network.