A relay node is configured to discover a route between a route origination node and a route destination node in a mesh communication network. The relay node in this regard generates a route request message that requests a route from the route origination node through the mesh communication network to the route destination node. The relay node transmits the route request message via unicast or broadcast, depending respectively on whether a routing table at the relay node has or does not have an entry indicating a known route to the route destination node.