Client and server devices identify each other over a LAN or similar network through a series of unicasts. Rather than broadcasting a service announcement or discovery request as a broadcast or multicast, for example, a device instead transmits a series of unicast messages using a finite set of recipient network addresses and port numbers. Responses to the unicast messages can be collected and tracked to thereby allow subsequent communications to occur via unicasts with only the recognized addresses, with a multicast to only the recognized addresses, and/or otherwise as desired. By allowing the clients and servers to communicate with a finite set of unicast messages, a “broadcast” type message can be sent on the network without a need for router configuration. Moreover, unicasts can be sent using different protocols (e.g., TCP) than the subsequent traffic (e.g., UDP), thereby making discovery of compatible devices on the network more reliable.