Winter 91 - ASYNCHRONOUS BACKGROUND NETWORKING ON THE MACINTOSH
ASYNCHRONOUS BACKGROUND NETWORKING ON THE
MACINTOSH
HARRY R. CHESLEY
LACS is a program that provides lightweight asynchronous conferencing for
Macintosh® computers connected to the same AppleTalk® network. This article
discusses the techniques used for implementing the asynchronous network operations,
techniques that work well even when the application is running in the background
under MultiFinder®. While the article provides the basic algorithms and techniques,
the Developer Essentialsdisc includes full source code for the entire LACS application.
Every Macintosh includes a local area network--LocalTalk ® . Any two or more
Macintosh computers can easily be configured to communicate with each other, passing
data back and forth to work together as a larger system. There are many applications of
computers that require or benefit from this sort of multiple workstation operation.
Most of these applications involve groups of people working together and are known as
collaborative computing, or computer supported cooperative work. While there are
limited numbers of applications available in this category today, the numbers are
increasing rapidly, and the potential for this genre is exciting.
Similarly, with the advent of MultiFinder and the ability to run programs in the
background while the user continues working on a foreground application, it has
become possible to write applications that operate on the user's behalf even when not
immediately controlled by the user. These sorts of background "daemons" have long
been available on mini, main-frame, and even workstation computers, but are
relatively new to personal computers.
Network and background applications are, by their very nature, asynchronous.
Network applications must communicate with other machines that may be slower than
the local machine or busy with some other task. The other machines may even be
temporarily turned off. Background operations must step very lightly to make sure
that they don't affect the responsiveness of the system as perceived by the user. This
usually involves using asynchronous techniques.
Asynchronous programs are often the hardest to design and develop. Our minds don't
deal well with multi-threaded algorithms. And the Macintosh today has little in the
way of development tools to help in this respect--there are no facilities for
lightweight processes within Macintosh applications, for example.
The Lightweight Asynchronous Conferencing System (LACS) is a program that uses
asynchronous background networking to propagate information from machine to
machine. It distributes messages over a network of locally connected Macintosh
computers. The LACS implementation provides examples of how to do the following:
• Invoke network operations asynchronously.
• Use an abstract superclass to simplify asynchronous design.
• Use NBP and ADSP.
• Operate in the background under MultiFinder.
• Implement a distributed database without requiring central control or
coordination.
This article describes LACS, concentrating on the first two of these elements, with
some limited discussion of the other items. You 're encouraged to examine the source
code of LACS (provided on the Developer Essentials disc) in order to uncover more
details.
THE LIGHTWEIGHT ASYNCHRONOUS CONFERENCING SYSTEM
(LACS) APPLICATION
LACS spreads messages from machine to machine across the local network. It is
designed to run in the background under MultiFinder and communicate quietly with
other machines. It uses the AppleTalk Name Binding Protocol (NBP) to find other
machines to communicate with, and it uses the AppleTalk Data Stream Protocol (ADSP)
to actually exchange messages. When new messages come in, the Notification Manager
is used to alert the user.
LACS is written in Object Pascal using MacApp ®. It uses object-oriented techniques
to simplify the problem of implementing periodic asynchronous functions. To
accomplish this, it uses an abstract superclass that provides a framework for other
classes of the same type.
From the user's point of view, the application consists of three windows: Messages,
New Message, and Status. Figure 1 shows these three windows. To create a new
message, the user simply types in the New Message window and clicks the Send
Message button. The message can be any text the user wants--but no pictures or
graphics in this edition. The application then spreads the message to other locally
connected Macintosh computers. When a new message arrives from another machine, it
appears in the Messages window on that machine. The Messages window displays two
lists of messages, one for those which have yet to be read and one for those which the
user has already read at least once. Only the first few words of each message appear in
the read or unread list. When the user clicks on an entry in one of the lists, the full
text of the message appears in a third section of the window. The Status window
contains information about how many messages have been seen, what other machines
are actively communicating, and so on.
There is more to the program than is covered in this brief description; for example,
users can set expiration dates for the messages they create. You might want to run
LACS to experience what it does and how it goes about it. However, the above
description is sufficient for our purposes here. The basic operation and intent of the
program is quite simple.
ALGORITHM FOR DISTRIBUTING MESSAGES
From the programmer's point of view, LACS maintains a distributed database of
messages across multiple loosely connected computers. The central problem is how to
distribute database updates across the network quickly and efficiently. The solution
comes from a paper published by Xerox PARC: Epidemic Algorithms for Replicated
Database Maintenance. (See references at the end of the article. Seems like everything
interesting comes from PARC, doesn't it?) In fact, LACS was directly inspired by
reading this paper.
In oversimplified form, the algorithm operates as follows: When a new message is
first heard, it is considered "hot." The program then tries to tell other network nodes
the new message. When a node passes on a message, the receiving node tells whether
it's already heard the message or not. The more times the program tries to spread the
message to nodes that have already heard it, the cooler the message becomes.
Eventually it becomes completely cold and the program stops trying to spread the
message to more nodes. The people at Xerox called the action of this algorithm "rumor
mongering.
Figure 1 LACS User Interface
In LACS, the algorithm is implemented on top of the AppleTalk protocols. The Name
Binding Protocol (NBP) is used to register LACS on the network. This allows the
application to find other machines that are interested in exchanging messages. Each
copy of LACS registers itself using the local machine's Chooser name with an NBP type
of "LACS." The program then builds a list of other nodes of type "LACS." Rather than
trying to maintain a list of all the systems on the net (potentially a very large list), it
keeps up to ten nodes with which it communicates directly. These nodes communicate
with up to ten others, they communicate with up to ten others, and so forth.
Periodically, one of the entries in the local list is replaced with another machine
chosen at random, so that the list slowly changes over time. The Apple Data Stream
Protocol (ADSP) is used to communicate between LACS systems. This protocol provides
reliable byte-stream connections, correcting for any errors in transmission across
the network. When a LACS machine decides to spread a message, it makes an ADSP
connection with another LACS node. It exchanges messages with the other machine and
then closes the ADSP connection.
MESSAGE EXCHANGE PROTOCOL
LACS implements a message exchange protocol on top of ADSP's reliable byte stream.
This message exchange protocol consists of separate commands, each having a command
name and a series of parameters. For example, the "Here's a new message" command
includes the message itself, its origination and expiration dates, and other related
information as parameters.
The ADSP session consists of a series of command exchanges. The originating node
starts the conversation. The destination node then responds with a command of its own.
Usually, the conversation starts with an attempt by the originator to pass on a
message; this is known as "pushing." But under some circumstances, the originator
may instead ask the other machine for a message; this is known as "pulling." In that
case, the other machine takes control of the conversation and sends a message. When
the controlling side has nothing further to say, the connection is closed.
The message exchange protocol commands include
• "Here's a new message.
Valid responses: "I've seen it." or "I haven't seen it.
• "Give me a hot message.
Valid responses: "Here's a new message.
• "Give me a message; I don't care if it's hot or cold.
Valid responses: "Here's a new message.
The responses "I've seen it" and "I haven't seen it" are actually implemented as
commands as well. But they are only generated in response to a "Here's a new message
command.
The protocol is very simple and is designed to use only ASCII text in the commands and
responses. This makes it easy for someone to write a program other than LACS that can
become part of the community of message spreaders. For example, a gateway could
spread messages from the local network to a wider area network. Or an archive agent
could collect and save messages.
Internally, LACS keeps track of the number of times it successfully or unsuccessfully
tried to pass on a message. The number of failed attempts is used to determine when a
message becomes cold and also how long to wait until the next attempt to pass it on.
The program actually implements several variations of the basic algorithm, which can
be selected by changing a few global parameters to the program. The default
parameters are
• Cool off messages deterministically (as opposed to stochastically).
• Consider a message to be cold after 30 redistribution failures. This
makes it highly likely that all machines will see each message, since each
machine tries 30 times to redistribute it. Of course, once most machines have
seen the message, most redistribution attempts will fail, since they will more
than likely pick a machine that has already seen the message.
• Push messages (rather than pull). This means that connections are only
made when there actually are messages to be transmitted.
• When picking another LACS machine with which to communicate, look in
the local AppleTalk zone twice as frequently as in other zones. This tends to
reduce network overhead by keeping communications local.
• Use an exponential back-off when determining how long to wait before
attempting to distribute the message again. This allows for quick initial
redistribution, but keeps the messages "hot" for some time, so that they get to
machines that were turned off when the message initially entered the network.
See the paper mentioned earlier from Xerox PARC, the source code of LACS, and the file
"About LACS" on the Developer Essentials disc for complete details of the algorithm
and variations used in LACS.
ASYNCHRONOUS OPERATION: TPERIODIC
LACS requires that several activities proceed asynchronously. Since it runs in the
background under MultiFinder, it cannot wait for the completion of a network
operation. It has to release control to the foreground process as quickly as possible. In
addition, there are several semi-independent activities in the program. Making them
dependent on each other, even to the extent that only one operates at a time, would
unnecessarily complicate the design.
The semi-independent, asynchronous activities in LACS include the following:
• Build and maintain a list of AppleTalk zones.
• Build and maintain a list of other LACS nodes with which to communicate.
• Initiate outgoing communication sessions.
• Receive incoming communication sessions.
• Perform housecleaning operations, such as saving the message database to
disk periodically.
In order to keep the design manageable, it is important to be able to separate these
activities into distinct code modules. Each individual piece is relatively easy to
understand and implement. It's only when they're taken together that the problem
becomes difficult.
This design separation is provided by building an abstract superclass, TPeriodic, that
implements periodic asynchronous operations. The model for TPeriodic is that
asynchronous periodic activities follow a particular pattern:
1. Wait for a set period of time.
2. Initiate an asynchronous action.
3. Check repeatedly to see if the action has completed.
4. Do something with the result.
5. Repeat from step 1.
The concrete subclasses of TPeriodic include TZoneLookup, TNodeLookup, TGossip, and
TDocumentSaver. Each of these subclasses are discussed in more detail in subsequent
sections.
INTERFACE
The interface to TPeriodic looks like this:
PeriodicStates = (kPeriodicInactive, kPeriodicWaiting,
kPeriodicActive);
TPeriodic = object(TEvtHandler)
fInactiveIdle: longInt; { Idle period when inactive. }
fActiveIdle: longInt;
{ Idle period when waiting for completion. }
fState: PeriodicStates; { Current state. }
procedure TPeriodic.IPeriodic(initialIdle, inactiveIdle,
activeIdle: longInt);
{ Initialize the periodic object. }
procedure TPeriodic.Free; override;
{ Free the periodic object. }
procedure TPeriodic.WaitForAsync;
{ Wait until any asynchronous activity is finished. }