Although the Internet was designed to handle non-real time data traffic, it is being used increasingly to carry voice and video. One important class of contributors to this growth are Internet telephones. Critical to more widespread use of Internet telephony is smooth interoperability with the existing telephone network. This interoperability comes through the use of Internet telephony gateways (ITGs) which perform protocol translation between an IP network and the public switched telephone network (PSTN). In order for an IP host to call a user on the PSTN, the IP host must know the IP address of an appropriate gateway. We consider the problem of finding these gateways. An analysis of a number of protocol architectures is presented, including hierarchical databases, multicast advertisement, routing protocols, and centralized databases. We propose a new protocol architecture, called Brokered Multicast Advertisements (BMA) which serves as a lightweight, scalable mechanism for locating ITGs. The BMA architecture is general, and can be applied to location of any service across a wide area network.