Scott is a scientific advisor at the Schlumberger Laboratory for Computer Science. He can be reached via Internet at guthery@austin.slcs.slb.com.
The walkie-talkies of computing are personal digital assistants, or PDAs. Apple's Newton, AT&T's EO, Casio's Zoomer, and IBM's Simon all open the possibility of direct, computer-to-computer connections using wireless personal-communication systems. Network vendors will contend that central switches are necessary for communication among a large number of people, and while central switches do add features to network communication, switchless network communciation that relays messages from one node to another is also possible. This article will explore possibilities for switchless networks which I will call "EchoNets."
Suppose that every minute or so your PDA broadcasts a message such as, "Curly here. Anybody out there?" Then, suppose I happen to walk by with my PDA turned on. It answers, "Yeah, Moe here. What's up, Curly?" Yours replies, "I've got 15 messages for you," and sends my PDA the messages. "Thanks," mine says, "and here are eight for you." "See ya, Curly," yours says. "Ciao, Moe," says mine, and they go their separate ways.
This is a basic EchoNet message exchange, a form of which is used in existing computer networks, including Usenet, FidoNet, and Relaynet. In fact, the news groups in FidoNet [Bush 93] are actually called "echoes," and mail is called "echomail." The difference between the use of the EchoNet-style
protocols by PDAs and their use in existing networks is that the nodes in existing networks exchange messages with nodes that are known and relatively fixed over time. In a PDA EchoNet, a node is constantly polling for and talking to strangers.
Obviously, if I'd queued up a message to you in my PDA or if you'd entered a message to me in yours, we would have communicated without a switch. This is plain-vanilla, peer-to-peer communication. But suppose my sister had written a message to you last night on her PDA. Sometime during the night, her PDA engaged in a message exchange with mine, and I unwittingly carried her message with me when I left for work this morning. When I walked by your PDA, I delivered her message to you. In a sense, my PDA was the network backbone that carried my sister's message to you.
EchoNets are by no means a recent discovery. One of the earliest networks in the Internet, the DARPA Packet Radio Network, used a "flooding" protocol, which is a form of EchoNet. And the gateways and bridges in modern switched networks are really nothing more than EchoNet nodes with fixed neighbors. So even switched networks may have EchoNet subnets.
However, we've become so accustomed to the features provided by switches that we think communication systems require them. While it will be useful for PDAs to be able to connect to pay-per-message switched networks such as cellular, telephone, satellite, and cable systems, it's important to realize that you are buying the added features of the switch and billing, as much as the raw network capability itself. It's also useful to realize that you can communicate without them.
Of course, one downside of EchoNet messaging is that the mail may not go through. And even if it eventually does go through, you have no idea about nor any control over how long it will take to deliver your message. It's like Usenet or FidoNet e-mail, only worse--much worse.
To get an EchoNet mail message from me to you, we need a chain of PDAs: First, I have to pass near A, then some time later, A has to exchange messages with B, and so forth, until you finally cross paths with Z. While it's helpful that the whole chain of PDAs need never exist in totality at any one point in time, you and I are clearly at the mercy of many chance events and random happenings. What this means is that you can probably get EchoNet mail reliably to people in the crowd you hang out with, but it's unlikely that you can get EchoNet mail to your friend in Tuva. In fact, it could be argued that EchoNets aren't good at all for person-to-person e-mail when you know exactly who you want to send the message to and what their address is.
Where EchoNets beat traditional e-mail (and telephone and surface mail, for that matter) is when you don't know who you want to send the message to, or when you don't know how to get in touch with them. In this case, you want to broadcast your message in the hopes that the person or people you're looking for will receive it. Thus, it is the receiver or receivers of the message, rather than the sender, who determines to whom the message is addressed.
Just like a piece of e-mail, an EchoNet message comes with a number of header fields (see Figure 1) which describe it. Header fields help you scan the incoming EchoNet messages quickly to find the ones that are meant for you. You'll probably want to activate some sort of automatic text filter to sift through all the incoming messages and set aside ones that fit you and your profile of interests.
It's important to remember that, unlike Usenet newsgroup messages, you're both a potential recipient and a relay point for all of the EchoNet messages you receive. Just because you find a message you think is addressed to you, doesn't mean you shouldn't pass it on. There may be other people who are interested in the message, and you're part of the chain that is going to get it to them.
By default, you should also relay messages that aren't addressed to you along with ones that are. On the other hand, you're free to look over your message traffic and delete any messages you don't want your PDA to pass along. In an analogy to the memes (or thoughts) of human communication, EchoNet messages are kind of like e-memes. E-memes that people like--that they want to tell other people about--are passed on. E-memes that people don't like die off quickly, either by being read and deleted, or by being killed by automatic purge rules.
Besides passing e-memes, you can also annotate or elaborate on them. In this case, your observation becomes linked to the e-meme it comments on, and when the e-meme is sent to another PDA, these links are preserved so that you really can read and add to threads of thought.
Have you noticed that Internet and FidoNet messages often arrive signed by everybody who handled them along the way? There are some interesting personal privacy implications if you extend this networking custom to an EchoNet. For example, if I get a message that has a path from Bob to Jim to Sally to Pete, then I could try to deduce that Jim was in the vicinity of Sally at some time. Due to name spoofing and path hacking (not to mention people borrowing each other's PDAs), this isn't ironclad evidence, but it is providing some information about the whereabouts of both your PDA and, by association, yourself.
Fortunately, EchoNet can forgo this cyberspace territorial-marking custom. There is nothing in the EchoNet relay algorithm that requires knowledge of how the message got to your PDA or the fact that it ever went through it. You can participate in EchoNets completely anonymously, or under a pen name. EchoNet pen names are like the handles of CB radio and the nicknames of Internet Relay Chat, with the advantage that you don't ever have to use an FCC-approved call sign or NIC-approved Internet address.
Privacy on an EchoNet is a little more problematic. If I can't understand what the message says, it's hard for me to figure out if it's for me or not. If it's encrypted and I don't have the key, then I'm pretty sure it isn't. Furthermore, if I can't read the message, then I can't determine if I want to pass it on or not and probably won't. Therefore, since encrypted e-memes will probably die out faster than unencrypted ones, I'd expect to see a resurgence of the clear text forms of encoding. This leads you to wonder which properties of an e-meme make it travel the farthest.
Psychologists who study cliques have devised fascinating ways of measuring the who-knows-whom connectivity between people. In one experiment, you're given a booklet describing a target person. This description does not include his or her name or whereabouts. You're asked to enter your name and address in the booklet, then pass it to somebody you know who stands a chance of getting the booklet to the target. The person to whom you give the booklet repeats the process, and sooner or later the booklet ends up in the hands of the person it describes. By counting the names in the booklet when it arrives, the psychologist obtains an upper-bound estimate of the who-knows-whom distance between you and the target. These experiments are called "studies of the small-world problem."
Suppose the people receiving the booklet had also been requested to enter some other information about themselves, rather than just entering their names and addresses. Then the booklets would accumulate a survey of all the people who handled them. Now suppose that the people are PDAs and the booklets are e-meme threads. What you have is a low-cost way of taking measurements and surveys.
For measurements, specially equipped PDAs can operate completely autonomously. At regular time intervals, the measurement's sensor is read, and a time- and location-stamped sensor value is queued as an outgoing e-meme. Over time, some of these readings find their way back to the person interested in them. While the coverage both in time and space is unpredictable, expenses are kept to a minimum and the flow is continuous.
An e-meme survey is more in the spirit of EchoNet. In this case, your PDA receives a questionnaire as the head of a thread of responses. The thread head asks you to append the thread with your response to the questionnaire. You're free to throw the whole thing away or look at the responses of other people before you add your own. As with PDA measurements, we don't exactly have a controlled experiment, but then, we don't have to bear the cost of conducting one, either.
A downside of e-meme surveys can be getting the raw data back to the person conducting the survey. If the PDAs are moving around, you cover a wide area but may only get back a portion of the measurements you took. On the other hand, if the PDAs are relatively immobile, you'll cover less area but stand a better chance of collecting more data. In this case, you can take advantage of the fact that the PDAs are immobile and upgrade the basic EchoNet protocol to include a notion of routing.
What if, in sending around passive text fragments, there were some way of sending executable code fragments? I think this is what people have in mind when they talk about Knowbots and General Magic Telescript agents. If there were some way of telling friendly viruses from evil ones, then a code fragment that hopped from PDA to PDA, gathering up data and then heading home at the end of the day, would be a terrific way to cover a lot of territory quickly. If nothing else, the quitting-time algorithm will be fun to design.
What if our PDAs aren't roaming around but are sitting still, in a classroom, for example, or at a concert or in an office? Here, rather than trusting to random passoffs to get messages through, the PDAs can run a routing algorithm so that each PDA knows exactly which PDAs are out there and which PDAs a message has to go through to get to a particular PDA.
The simplest routing algorithm begins by each PDA figuring out who it is directly connected to. It does this using the usual message-exchange protocol, but rather than exchanging messages, it exchanges connectivity information. "Curly here. Anybody out there?" one says, and gets back a bunch of messages: "Yeah, Sleepy here. What's up?" "Yeah, Sneezy here. What's up?" "Yeah, Doc here. What's up?" "Yeah, Bashful here. What's up?" Now Curly knows he's directly connected to Sleepy, Sneezy, Doc, and Bashful, and each of these knows they are directly connected to Curly.
With this information, Curly can address messages directly to particular PDAs rather than broadcasting them to everybody and having to deal with all their responses. "Curly here. Who are you connected to, Sleepy?" Sleepy responds to Curly, "Sleepy here. I'm connected to Doc and Snow White, Curly." "Ahah! A new player," thinks Curly. What Curly has discovered is that there is a Snow White out there that he can get a message to by way of Sleepy. "Curly here. Give this to Snow White, Sleepy: 'Yo, SW, what's cookin'?' "
What you have here is explicit routing. Rather than just broadcasting a message into the ether, Curly sent it directly to Sleepy along with explicit instructions to pass it directly to Snow White. We've also added the peer-to-peer "Who are you connected to?" message. By coupling this message with direct addressing, any PDA can discover the entire known universe and its connectivity. Knowing this, your PDA can present you with a list of all the PDAs with which you can communicate on EchoNet and can send any message directly to the one you pick. In a sense, your PDA is functioning as a router or a switch as well as a source, sink, and passive relay point. You're realizing some of the advantages of a switched network without building a central switch through which all traffic must flow.
There are hundreds of networkdiscovery and network-routing algorithms and protocols. Many can be used in EchoNets and switched nets. In fact, an EchoNet can be thought of as just a network, in which every node is also a router. Recently, the Internet technical community has become interested in supporting Internet connectivity to mobile hosts (see the accompanying text box entitled "Mobile Internetworking") and has published the "Internet Packet Transmission Protocol," which discusses a possible routing algorithm for this situation.
This primitive network-discovery and routing algorithm is an example of a large class of distributed-system algorithms that has received attention over the last 15 years. Dijkstra's classic paper [Dijkstra 80] and Chang's independent discovery [Chang 82] have set the tone and direction for much of this work. Chang's paper is a more readable introduction to distributed algorithms even though Dijkstra's paper has priority. Yang and Marsland's recent note [Yang 93] is an excellent annotated bibliography on two important problems in this field.
Dijkstra and Chang showed that it is possible to design practical algorithms for EchoNets which enable any node in the network to discover information about the whole network or about any particular node in the network. In fact, Chang called these algorithms "echo algorithms" because a broadcast question produces an echoed response. "Practical" here means that the answer is obtained in a deterministic and computable amount of time and that the EchoNet message traffic generated by the broadcast request eventually dies out.
The Dijkstra/Chang echo algorithm proceeds as follows: The initial, inquisitive node sends its question to each of the nodes to which it is connected. Upon initially receiving the question, each node relays the question to all the nodes to which it is connected except for the initial node. If the receiving node has no other nodes to which it can send the question, then it sends the accumlated answer back to the node that sent it the question. Finally, when a node receives answers from all the nodes to which it sent the question, it in turn sends the accumulated answers to the node that first sent it the question.
In his paper, Chang gives a number of applications of this basic echo algorithm along with some performance calculations and special-case improvements. One of the applications, the Single-Source Sort, is particularly applicable to our PDA-to-PDA communication situation. The idea is that a new node is joining an existing EchoNet and wants to pick a unique identity. The new node sends out the question, "What is your name?" Each node's echo is its own name, appended to the list of names it has received from the nodes it has contacted. What arrives back at the new node is a list of the names of all the nodes in the EchoNet. All the new kid on the block has to do now is pick a name that isn't on the list.
Dijkstra/Chang-style echo algorithms are fine for determining static properties of an EchoNet (such as the list of the names of all the nodes in the network); but what about dynamic properties? Suppose all the nodes in an EchoNet wanted to cooperate in accomplishing a task of some sort. How would they keep track of the current state and progress of their combined effort, or stay coordinated?
One way would be to have everybody synchronize their actions to a global clock, then treat the dynamic state as simply a series of static states separated by network-wide time synchronization points. From an individual node's point of view, the drill might look something like this (see, for example, [Flammer 92]):
Chandy and Lamport [Chandy 85] describe an algorithm whereby nodes in an EchoNet can determine the global state of a cooperative effort without a global clock. They called their algorithm a "distributed snapshot" by analogy to a group of photographers (the nodes) who take several pictures (the local states) and piece together the results (by exchanging messages) to form a "meaningful" panoramic picture (the global state) that is larger than a picture that any one photographer's camera could handle. In this context, "meaningful" means that the composite picture is sufficient for coordinating the nodes and getting the cooperative effort accomplished.
The Chandy/Lamport algorithm provides a method for "strobing" the recording of a node's local state by a mechanism other than a global alarm clock. The method is based on the sending of a special "Record your state!" message around the network. After the message has been received and obeyed by all nodes, the recorded local states are collected to form a description of the global state; this global state description is distributed to all nodes using an echo algorithm.
Since the "Record your state!" message reaches nodes at different times, you have to record not only the state of each of the nodes but the state of what causes nodes to change state; videlicet, the in-transit message traffic between nodes. The resulting global state is rather like a little film clip that we can run forward and backward to see what the network was up to during a tiny interval of time. The Chandy/
Lamport algorithm is a careful specification of how the local states of the nodes and the communication channels are to be recorded so that this movie is a useful representation of the net's state.
The Chandy/Lamport distributed snapshot algorithm works like this:
Initiation Rule: Send the "Record your state!" message to each node to which you're connected and then record your state before you send any further messages.
Unrecorded State Rule: If you receive a "Record your state!" message and you have not already recorded your state, then: 1. Record your state; 2. record the fact that the state of the channel between you and the node that sent you the message is "Empty"; 3. start recording all subsequent messages you receive from other nodes; and 4. send the "Record your state!" to each node to which you are connected.
Recorded State Rule: If you receive a "Record your state!" message and you already have recorded your state, then record the fact that the state of the channel between you and the node that sent you the message is the sequence of the messages you got from this node between the time you recorded your state and the current "Record your state!" message.
The algorithm gives receivers the obligation of recording the in-flight messages. The recording starts at a node when the first "Record your state!" message appears on any channel and stops channel-by-channel when "Record your state!" appears on each channel.
What the Dijkstra/Chang and Chandy/
Lamport algorithms give us is a way for many mobile computers to act cooperatively. While each individual PDA is keenly aware of its own surroundings, it can also count on the "eyes and ears" of the other PDAs in its EchoNet to act as lookouts in regions beyond its own ken. I think of PDAs knitted together by these algorithms as being similar to the compound eye of an insect or a very large array radio antenna. In a sense, the reality of each PDA has been extended to the area covered by the entire EchoNet of which it is a member.
It's interesting that this relatively complex form of network behavior has been achieved without a central switch. Switchless networks like EchoNets certainly have their drawbacks, such as indeterminate message delivery. The advantages, however, include robustness due to absence of a single point of failure and the ease with which nodes can enter and leave the communication mesh. In the era of mobile wireless computing, we may find situations where it just doesn't make sense to send the message downtown and back if it only has to get to someone standing next to me. We may also find useful forms of network communication that don't send us a bill at the end of the month.
Acharya, Arup, and B.R. Badrinath. "Delivering Multicast Messages in Networks with Mobile Hosts." Proceedings of the 13th International Conference on Distributed Computing Systems. May 25--28, 1993, Pittsburgh, PA.
Bush, Randy. "FidoNet: Technology, Tools, and History." Communications of the ACM (August 1993).
Chandy, K. Mani, and Leslie Lamport. "Distributed Snapshots: Determining Global States of Distributed Systems." ACM Transactions on Computer Systems, (February 1985).
Chang, Ernest J.H. "Echo Algorithms: Depth Parallel Operations on General Graphs." IEEE Transactions on Software Engineering (July 1982).
Chow, Ching-Hua. "On Multicast Path Finding Algorithms." Proceedings of IEEE Infocom '91.
Dijkstra, E.W., and C.S. Scholten. "Termination detection for diffusing computations." Inf. Proc. Lett. (August 1980).
Ioannidis, John, and Gerald Q. Maguire, Jr. "The Design and Implementation of a Mobile Internetworking Architecture." Proceedings of the 1993 Winter USENIX Meeting, January 25--29, 1993, San Diego, CA.
Flammer, George H. Method for Synchronizing a Wide Area Network without Global Synchronization. U.S. Patent #05130987.
Ioannidis, John. Protocols for Mobile Internetworking. Ph.D. Thesis, Columbia University, 1993.
Trask, Jeremy R., and Anthony Wiener. "Data Communication System." U.S. Patent 4,937,569, June 26, 1990.
Uehara, Keisuke, et al. "Enhancement of VIP and Its Evaluation." Proceedings of INET '93, August 17--20, San Francisco, CA.
Wada, Hiromi, Tatsuya Ohnishi, and Brian Marsh. "Packet Forwarding for Mobile Hosts." Internet Draft, July 1993.
Yang, Zhonghua, and T. Anthony Marsland. "Annotated Bibliography on Global States and Times in Distributed Systems." ACM Operating Systems Review (July 1993).
To: EchoNet Implementers Everywhere From: Earl of Echoes in Austin Subject: Improved Short-Hop Protocol Keywords: EchoNet, Transfer Rules Send-Date: September 6, 1993 Route: Bubba in Temple, Jenny Jet in Dallas
Mobile Internetworking
A number of similar schemes (Ioannidis, Uehara, and Wada, for example) have been proposed for extending TCP/IP, and hence, the Internet, to mobile computers. The situation is a little more complicated because, as originally conceived, TCP/IP addresses combine two distinctly different pieces of information: unique name and current location (kind of like "Minnesota Fats" or "Boston Blackie"). When host computers were immobile, this didn't matter; if they did move, we changed their names. Clearly this solution won't work for a computer tooling down Route 66.
A design criterion for all of the mobile-internetworking proposals is to minimize the impact of supporting mobile hosts on the existing network as much as possible. Thus, not only should everything that works today continue working, but a stationary host should be able to communicate with a mobile host just as if it were another stationary host. Basically, this means that the mobile host's address doesn't change, at least from the point of view of other hosts communicating with it.
The Internet Packet Transmission Protocol (IPTP) proposed in a July 1993 Internet Draft (Wada) endows a mobile host with two addresses: a home address (the unique name, "Blackie") and an away address (the current location, "Boston"). The home address doesn't change and is the permanent name of the host known to the world. The away address does change and is the address at which the mobile host can currently be reached. The only change to the network is the addition of a piece of software called a Packet Forwarding Server to the mobile host's home network, which keeps track of where the mobile host is and forwards messages to it.
As the mobile host moves around, it acquires an away address from each local network whose territory it enters, and it sends this away address back to its home network's Packet Forwarding Server. In this way the home network always knows where the mobile host is and how to reach it. Messages to a mobile host are always sent to its home address; when they're received, the Packet Forwarding Server readdresses them to the mobile host's away address. Messages from a mobile host go directly to whom they are addressed and need not detour through the Packet Forwarding Server on the mobile host's home network. The return address on these messages is the mobile host's home address, not its temporary away address.
As hosts and routers on the Internet are willing to become more mobile-host-aware, there are a number of efficiencies that can be introduced into this minimum-impact protocol, and many of these are described in the referenced papers. For example, a sender might indicate that it is willing to track the mobile host as well so the mobile host could set its return address to its away address rather than its home address.
--S.B.G.
Copyright © 1994, Dr. Dobb's Journal