darrell@Odin.UCSD.EDU (Darrell Long) (03/22/88)
I haven't gotten a lot of response to this one, so I'll throw something in. #4 How do you locate a mobile object in a large-scale distributed system? Consider for example the Cellular phone network. It is easy for a mobile station to make a call to a fixed location (a home or business), but suppose that our friend is driving across country and his wife wants to call him? How does the network find a mobile station whose last known location was San Diego but may now be in Las Vegas? DL
sjm@computer-lab.cambridge.ac.uk (03/23/88)
We have addressed the problem of locating objects in the contents of the Amoeba system. Before explaining how we attempt to solve the problem I must give a little background. In Amoeba, objects are managed by services. Services can have a distributed implementation and many server processes. In principle, all server processes in a single service give identical service; if an object can be accessed through one of them, it can also be accessed through another. Objects are addressed using capabilities. Each capability consist of a port--which names the service that manages the object--and a private part--which names the object within the service. The port, for the purposes of locating servers, is just a random number. In a local-area network, locating aobjects is fairly straightforward: A client wishing to do an operation on an object locates a server by broadcasting a `where are you' message. The server responds and the request can be sent. The results of these locate operations are cached and our experience is that locates need not be done very often. Servers and clients can migrate and servers can crash to be replaced by new ones, because when cached information is found to be incorrect, a new locate can be done. (Servers and clients can even migrate in the middle of an operation, but this is another story.) Amoeba also runs over wide-area networks. In fact, Amoebas are running in half a dozen European countries and operations by clients in one country on objects on servers in another work. Locating objects over wide-area networks using broadcast is impractical, however. We have done the following: We consider the network to be essentially a two-level hierarchy. The bottom level is what we call the `local internet,' one or more local networks, connected by bridges or gateways. The essence of the local internet is that it is small enough to do broadcast over. Objects in a local interent are thus located using the broadcast method described above. The second level is the wide-area network. An Amoeba (i.e., Amoeba running over a local interent) is connected to the wide-area network via a gateway. The gateway converts from the high-performance Amoeba protocol which runs over the local internet to whatever has to run over the wide-area network (usually X.25, in Europe). It also assists in locate operations. Capabilities have a third field which I have not mentioned yet, called a location hint. The hint is essentially the name of a gateway on the local interent where the server for the associated object resides. What happens when a client locates a server for an object is this: The client broadcasts the port (with the hint) over the local internet as usual. If there is a local server, everything proceeds as described above. If there is not, and the hint indicates a remote gateway, the local gateway will respond as if it is the server. The request will then be sent to the gateway, the gateway will send the request to the remote gateway as prescribed by the hint, and the remote gateway will then broadcast for the server on its local internet. This should find the server. There are restrictions on the mobility of servers in this scheme. When a server migrates from one local internet to another, it can no longer be located. Note that this restriction does not apply to objects, as long as a server stays behind to do the forwarding. In the context of our project, we do not feel that this is a restriction; so far, there seems to be no need for migrating servers or objects over vast distances. So much for practicality. Paul Vitanyi and I have also done an analysis of the complexity of the locate problem. We have published preliminary results in a paper called `Distributed Match-Making in Computer Networks' in the proceedings of the 4th PODC (Minaki, Ont., 1985). We have proved there, that a truly distributed algorithm for locating objects, without using forwarding addresses, using n name servers, requires O(sqrt(n)) messages. This does not scale very well, obviously. Efficient locate algorithms must take into account that: 1. Local traffic dominates. Get that to work efficiently first. 2. You can't afford to broadcast over large networks. You must keep track of migrating object's locations, either by using forwarding addresses or by using name servers.
wyant@apollo.uucp (Geoffrey Wyant) (03/25/88)
> In a local-area network, locating aobjects is fairly straightforward: A > client wishing to do an operation on an object locates a server by > broadcasting a `where are you' message. The server responds and the > request can be sent. The results of these locate operations are cached > and our experience is that locates need not be done very often. > Servers and clients can migrate and servers can crash to be replaced by > new ones, because when cached information is found to be incorrect, a > new locate can be done. (Servers and clients can even migrate in the > middle of an operation, but this is another story.) There are two problems with this. First, broadcast isn't a particulary efficient way to locate an object. Secondly, it requires giving all processes the ability to broadcast. In practice, many system restrict this ability severely. We faced this same problem in developing NCS, a portable object-oriented distributed environment. We finally decided on the following solution. We have a replicated global registry in which type managers register their managed objects and the associated socket address. When a client wishes to invoke operations on an object, it calls the global location broker to get the socket address that can be used in subsequent calls on the object. This isn't a perfect solution as the socket address must be taken as a hint, but it seems to work well enough in practice. It also doesn't deal with the movement of an object while a client is bound to it, although we do have some ideas on how to handle that transparently. If you want more information on NCS, let me know and I can send you some papers we've written. -- Geoff Wyant -- UUCP: ...{yale,mit-eddie}!apollo!wyant