Figure 1 depicts the basic components of the Etherphone system in a simple configuration [25]. Each personal workstation is associated with, but not directly attached to, a microprocessor-based telephone instrument called an Etherphone. Etherphones digitize, packetize, and encrypt telephone-quality voice and transmit it directly over an Ethernet. A voice control server provides control functions similar to a conventional business telephone system and manages the interactions between all the other components. In particular, it allows voice-carrying conversations to be established between two or more Etherphones, workstations, or servers. A voice file server, discussed further in Section 3.1, provides storage for recorded voice. The system can also include other specialized sources or sinks of voice, such as a text-to-speech server that receives text strings and returns the equivalent spoken text to the user's Etherphone.

Workstations are the key to providing enhanced user interfaces and control over the voice capabilities. We rely on the extensibility of the local programming environment—be it Cedar, Interlisp, or the Xerox Development Environment—to facilitate the integration of voice into workstation-based applications. Workstation program libraries implement the client programmer interface to the voice system.

All of the communication required for control in the voice system, such as conversation establishment, is accomplished via a remote procedure call (RPC) protocol [4]. Multiple implementations of the RPC mechanisms permit the integration of workstation programs and voice applications programmed in different environments. During the course of a conversation, RPC calls emanating from the voice control server inform participants about various activities concerning the conversation. Active parties in a conversation exchange voice using a voice transmission protocol [23].

The server software and the initial workstation software was developed in the Cedar programming environment [24]. More information on the equipment and protocols used in the Etherphone system, as well as the applications built to date, can be found in related papers [23] [25].

To record or playback a voice rope, a conversation is set up between the voice manager and an Etherphone. The main operations supported by the voice manager are as follows:

The voice manager generates event reports upon the start and completion of a queued operation. The requestID returned by each invocation is used to associate reports with specific operations. In particular, the voice manager makes the following call to all participants in a conversation to inform them of the status of various requested operations concerning that conversation:

Once recorded, voice ropes can be used in editing operations to produce new, immutable voice ropes. Several of the operations on Cedar ropes, such as producing substrings or concatenating existing strings, are directly applicable to voice. Their transliteration for voice ropes yields these functions:

The voice manager also provides operations for managing voice references. These operations provide a sort of directory for voice ropes. Although simple applications can use this directory as their means for naming and locating voice ropes, that is not its primary purpose. As with any storage system, unreferenced storage space should be reclaimed. With voice, or other voluminous media such as video, the need is particularly acute. In the Etherphone system, client code must assist with garbage collection by using the directory operations to express an interest in each referenced voice rope. We list the client operations here, deferring to Section 3.4 a discussion of the rationale for this approach and a description of the underlying implementation. The interest operations are:

The class identifies the way in which the voice rope is being used by a particular application. For example, we use the class "FileAnnotation" to indicate that a document stored in a named file is annotated by a set of utterances; the interest field is the file name. The class "Message" indicates that the reference is a part of an electronic mail message incorporating recorded voice, and the interest is the unique postmark supplied by the message system.

A combination of client workstation software and automatic collection methods must hide these interest operations from actual users. Client applications must always register interests in order to ensure retention of voice ropes to which they hold references. For some classes, clients must also explicitly FORGET their interests; for others, such as the "FileAnnotation" class, automatic methods described in Section 3.4 make this unnecessary.

A voice file server differs from normal file servers [22] in that it must support the real-time requirements of voice. In particular, it must be able to maintain a sustained transfer rate of 64 Kbits/sec, and it should be able to support several such transfers simultaneously. There is no inherent reason why a general-purpose file server could not be extended to support these stringent real-time requirements. However, the file systems we had available at the onset of this project, having been optimized for different styles of access, could not, in fact, support them. At present, our file server is a special-purpose system built on top of Cedar's standard file system [24].

We will not describe the workings of the Etherphone voice file server in any detail. It implements the operations needed to allocate, record and play back voice files that are named by unique identifiers (VFIDs). Tables locating the boundaries between sound and silence are stored along with the voice to permit efficient execution of the DESCRIBE operation.

Etherphones encrypt voice using DES electronic-codebook (ECB) encryption [17] as it is transmitted. The voice file server simply stores the voice in its encrypted form. This adds a requirement in the voice rope component to manage encryption keys. The stored voice is never decrypted except by an Etherphone when being played back.

Voice ropes and interests could be implemented using specialized data structures. However, we realized that the facilities of a database would serve these needs well, and the performance requirements were not particularly stringent. The objects representing voice ropes are immutable; multi-object atomic updates are not required; and, the usage of the system is expected to generate relatively infrequent changes to small numbers of voice segments, each several seconds or even minutes in duration. An original prototype voice rope system was built using an existing entity-relation database system (Cypress) in the Cedar environment. [7]. Cypress provides transaction semantics for reliability and data consistency, typed data, facilities for constructing elaborate queries, and adequate steady-state performance. However, in the current Cypress implementation, the overhead of opening and committing transactions is too great to permit sharing a database among many client programs that are making frequent updates. For these reasons, a simple, robust database representation that is particularly well-suited to voice ropes was developed.

A data base entry is a simple sequence of key/value pairs, each represented as a text string. The database system stores each entry in a write-ahead log [11]. Unlike most database systems in which the data is logged only until it can be committed and written to a more permanent location, the log is itself the permanent source of data. Once logged, the data is never moved. To allow rapid queries or enumeration of database entries, B-Tree indices [2] are built to map the values of one or more keys to the corresponding locations in the log file. This log-based database package was inspired by similar methods found in the Walnut electronic mail system [9] and recommended by Lampson [13].

In addition to processing queries, the database system supports atomic insert, replace, and delete operations for single entries. If a crash occurs while writing a log entry, the incomplete entry is discovered upon recovery. If a crash occurs while updating a B-Tree index, the log must be replayed to build the index from scratch, which is an expensive operation. However, since an untimely hardware crash is a rare event, rebuilding an index when necessary seems less costly than building and running a transaction system to update the log and indices atomically.

Since no long-term locks are maintained, multiple clients can easily interleave queries and updates. The append-only log leads to predictable and consistent performance (except during crash recovery), with no lengthy pauses due to transaction conflicts. A compaction operation is provided that enumerates the current entries (in the order specified by the primary key) to produce a new, minimum-length log file; the old one can be saved on archival storage, then deleted.

The data structure representing a voice rope consists of a list of [VFID, interval] pairs. Simple voice ropes consist of a single interval within a single voice file, often the whole file. More complex voice ropes can be constructed using the editing operations presented in section 2.2. For example, suppose two simple voice ropes, VR1 and VR2, exist with the following structures:

To record a new voice rope, the voice manager calls on the voice file server to allocate and then record a voice file. Once recording completes, a simple voice rope is added to the voice rope database to represent the complete voice file just recorded. A database index allows voice rope structures to be retrieved efficiently by VRID; an index is also maintained on VFIDs, which is useful in garbage collection.

When playing a voice rope, the voice manager retrieves the voice rope's structure from the database, distributes the encryption keys of the various intervals to the parties participating in the conversation, and calls upon the voice file server to play the intervals of the voice rope in the appropriate order. Requesting the playback of several intervals in succession relies on the asynchronous nature of the voice file server operations to ensure that gaps do not get inserted between the intervals. Secure RPC [5] is used to distribute encryption keys safely.

The structure of voice ropes is kept "flat" to optimize playback. By having each voice rope refer directly to voice files, only a single database access is required to determine the voice rope's complete structure. An alternative design, more closely modeled on the Cedar Rope abstraction, would store complex voice ropes as intervals of other voice ropes. In such a design, a voice rope would conceptually be the root of a tree of other voice ropes with intervals of voice files at the leaves of the tree. This alternative design would reduce the work associated with each editing operation, but would increase the number of database accesses required to play a voice rope. The flat design was chosen because it improves playback behavior, and, in practice, playback is much more frequent than editing. Moreover, it yields simpler and more compact data structures when used (as intended) to represent small numbers of coarse-grained edits to voice.

Note that the actual voice is neither moved nor copied once recorded in a voice file, even during editing. The voice also is never decrypted by the voice file server. The encryption keys for the various intervals that compose a voice rope are stored in the database along with the voice rope's structure. Independently enciphering small blocks of voice using ECB encryption [17] ensures that voice can be edited on millisecond-resolution boundaries while remaining encrypted.

This section presents the rationale for the interest operations of section 2.3 and describes their implementation. These operations were included primarily to permit automatic reclamation of storage for voice ropes and their associated voice files.

Once all voice ropes that reference a given voice file have been deleted, no voice rope will ever again refer to that voice file. The voice file can then be deleted as well. This condition is easily determined by a database query. The more difficult problem is deciding when voice ropes themselves can be reclaimed.

From the client standpoint, the most straightforward method for garbage collecting voice ropes would be periodically to examine all of the clients' storage for references to voice ropes, then to collect any unreferenced ropes in a conventional sweep pass. Unfortunately, this sort of distributed garbage collector would be impossible to implement in our open, relatively heterogeneous, environment. We do not wish to restrict the uses clients make of voice ropes, or how and where clients store VRIDs.

A common alternative is to provide a reference counting scheme in which counters are used to determine the number of clients interested in a particular object. When an object's counter goes to zero, the object's storage can be reclaimed. The burden is placed on clients to increment and decrement the counts for the objects that they are using.

The use of standard reference counting presents formidable problems in a distributed environment. Reference counts cannot be managed reliably unless an atomic transaction spans the use of the reference and the reference count operation. Without transactions, if the server or client fails in the process of incrementing or decrementing a reference count, the client may be left in an uncertain state regarding the outcome of the operation. In particular, client failure-recovery procedures might incorrectly repeat a reference count operation. Furthermore, it is not always possible to arrange for a reference count to be decremented (such as when a reference-containing file residing on an uncooperative server is deleted). Finally, reference counts are anonymous, giving no help in locating erroneous references.

Interests were designed to remedy these shortcomings associated with simple reference counts. In a way, interests represent a return to the full-scan method first proposed: since an examination of the entire environment is not possible, clients are required to record their voice rope interests in a known place. The interests serve as proxies for the actual references for reclamation purposes. Interests address two problems: how to retain voice ropes for which references exist, and how to determine when it is permissible to reclaim them.

In summary, garbage collection takes place on three levels. The voice manager deletes voice files when they are no longer referenced by voice ropes. Voice ropes are deleted if no interests exist for them. Interests are either explicitly forgotten by client applications or automatically deleted based on a class-specific test for validity.

Manipulating stored voice solely by textual references, besides allowing efficient sharing and resource management, makes it easy to integrate voice into documents. For example, we were able to build a local voice mail system without changing the mail transport protocols or servers. Also, annotated documents can be stored on conventional file servers that are not aware that the documents logically contain voice.

Significant performance benefits accrued by having documents refer to voice that is stored remotely. Although most requests to record or playback voice ropes are initiated from a workstation, the voice data is never received by the workstation; instead, it is transmitted directly to the associated Etherphone.

These techniques for sharing, however, require clients to have high-bandwidth network access to the voice manager. Transferring voice-annotated documents between remote sites would require special mechanisms such as DARPA's experimental multimedia mail protocol [19]

We have gained considerable experience with the voice manager by building a voice editing system in Cedar. Figure 4 displays a document containing voice annotations, and just below it a visual representation of one of the voice annotations that has been opened up for editing. The bar patterns in the visual representation indicate with solid bars the contiguous intervals (talkspurts) of voice or other sounds, separated by white regions that represent periods of silence [1]. Given a voice rope representing the entire annotation, the DESCRIBE operation is sufficient for generating such a display.

The small set of editing operations provided by the voice manager has proven to be a sufficient base on which to build a complex voice editor and a dictation machine. However, to reduce traffic to the voice manager, the Cedar voice editor maintains its own data structures to represent the edited voice temporarily. That is, the voice editor ended up replicating much of the functionality of the voice manager, something we were trying to avoid. Only when a user elects to save the edited voice passage does the voice manager get called to perform the necessary operations. Given this arrangement, it may have been better to let clients simply pass the voice manager a complex voice rope that it could store in its database.

Experience indicates that editing a voice passage invariably produces a set of "temporary" voice ropes that are used in the construction of the finished result. These objects are eventually collected by the garbage collector, so they do not present much of a problem except that their creation requires seemingly unnecessary work of the voice manager. To alleviate the problem somewhat, the voice manager's interface was changed slightly so that an interval could be given for any voice rope in any operation. This substantially reduced the voice editor's use of the SUBSTRING operation.

Event reporting is important in allowing the voice editor to coordinate its visual feedback with the activities of the voice file server. In particular, the voice editor moves a cursor along the screen as a voice rope is being played (the gray marker below the word "score" in the voice displayed in Figure 4). A report indicating that the playback of a particular voice passage has started or finished is essential to synchronize the movement of the cursor with the transmission of voice data.

Although the voice file server writes files on disk so that 1-second segments can be continuously transferred, clients are allowed to edit voice ropes on 1-millisecond boundaries. The file server could not possibly playback a voice rope in real time if it had to perform a disk seek every millisecond. Fortunately, users of the voice editor are encouraged to insert, delete, and rearrange voice passages at the granularity of a sentence or phrase rather than trying to modify individual words or phonemes [1]. Thus, in practice, one rarely sees segments of a voice rope that are less than several seconds in length.

The notion of grouping interests into classes and providing class-specific garbage collection algorithms is a useful and workable concept. However, we are still groping with the details of how best to use these mechanisms. We have found several interest classes to be useful in Cedar.

The Cedar mail system, automatically registers and deregisters interests of class "Message" as voice messages are saved and deleted by users. In addition, a "Timeout" class has been used to retract an interest automatically after a certain amount of time. For instance, when sending a voice message, a timeout can be set by the sender that is long enough to give the recipients a chance to receive the message and register their own interests if so desired. Of course, problems can arise if a recipient is on vacation for a period of time longer than the timeout. For this reason, we have a means of archiving voice files before deleting them from the server.

For annotated documents in Cedar, the workstation software detects when a file is copied from the local disk to a public file server; it then automatically registers the appropriate "FileAnnotation" interests for the public file. Having workstation software automatically register interests as a file is copied to a file server works remarkably well. However, some important operations are not covered by this approach: renaming a file on a file server or copying files between two file servers. We see no way to detect such operations except by modifying file server software.

We have defined the "FileAnnotation" interest class such that its interest represents a publicly stored file name including the version number. With this scheme, interests must be reregistered for each new version of the file, that is, whenever a file is written to a public server. Unfortunately, the times that people want to annotate documents are precisely those times when the document is being updated often, so many interests are registered repeatedly. We rely on the garbage collector to get rid of old interests. An alternative would be to register a file without a version number, but that causes minor problems if voice is deleted from the file but the file itself remains in existence.

The voice file server, voice manager, and voice control server were implemented so that they could run on separate physical processors. That is, they all communicate among themselves and with voice clients using RPC. In practice, we run all three on the same Dorado. There is little to be gained by running them separately, since the voice file server cannot record or playback voice files if the control server is down. Similarly, the voice manager cannot record or playback voice ropes if the voice file server is down. For all practical purposes, voice can also not be edited if the voice file server is down, because users invariably need to listen to the voice passages that they are editing.

Thus, availability is not adversely affected by having the voice manager and file server colocated with the control server. If this server crashes or is otherwise unavailable, then no operations can be performed on stored voice. For the most part, this is simply an inconvenience to users in the same way that unavailability of conventional file servers is an inconvenience. In Cedar, the file servers containing the important system files, fonts, and documentation are replicated to improve their availability. We have not found it necessary to pay the cost to provide a highly-available voice file server.

The one exception to this concerns voice interests. It is often the case that clients wish to register or deregister interests in voice ropes independently of playing the referenced voice. For example, an interest of type "FileAnnotation" is registered when a voice-annotated document is copied from a personal workstation to a public file server. A user should not be prevented from performing such a copy simply because the voice manager is unavailable. We have also observed that the interests for voice messages fail to get properly registered or deregistered if a person saves or deletes a voice message while the voice server is down. This has led us to contemplate writing a program that enumerates a person's mail database and checks that all voice messages have properly registered interests. The better solution is to make the voice interest database highly-available. Rather than fully replicating the database, we are planning to provide a mechanism whereby operations to RETAIN or FORGET a voice interest are logged locally by a user's workstation if the voice server is unavailable; the operations in this log will be retried when the workstation detects that the server is reachable.

(Performance measurements of the system are not available for publication at this time, but we should be able to include some in the final paper. We are convinced that the time performance of both the voice file server and the voice rope facilities exceed the requirements of intended applications, so there will be little to learn there. What we need to measure is the way people use this stuff -- how many edits they make, at how fine a grain, etc. We also need to estimate and/or measure the cost of database log compaction, once the system is in heavy use. Space requirements for archiving actual digitized voice is also an issue.)

Several companies provide speech message systems that can be accessed from standard telephones; one of the earliest examples of this type of system was IBM's experimental Speech Filing System, which was operational in 1975 [10]. Certainly the Etherphone system's facilities can be accessed from telephones, but that was not the driving application. We were interested in allowing voice to be integrated easily into a user's existing means of digital communications, rather than forcing users to learn a completely new system. The Sydis Information Manager provides workstation control over the recording, editing, and playing of voice as in the Etherphone system, but requires special workstations called VoiceStations [18]. Ruiz also developed a prototype voice system that integrates voice and data into some simple workstation applications; however, he did not address the important issues of sharing stored voice [20].

Maxemchuk's speech storage system [15] provided many of the same facilities for recording, editing, and playing voice as our voice file server. (Actually, he provided much more control over the playback of voice than we do, such as the ability to vary playback speeds or adjust silence intervals.) Also, the division of function between a main computer and a storage computer is quite similar to the separation between our voice manager and voice file server. However, Maxemchuk's system edits voice using divide and join operations that modify the control sectors of stored voice messages. Our technique of building data structures that reference voice files better supports sharing, by making voice ropes immutable, and simplifies the requirements placed on the voice file server. For instance, our techniques are very amenable to write-once storage technologies such as optical disks.

Version Storage in the Swallow system [21] has many similar characteristics to our voice manager. That is, it manages immutable objects of various sizes. Also, its "structured version images" used for large objects are similar to the data structures used by the voice file server to describe voice files. However, unlike the voice manager, Swallow maintains histories to link together objects that are derived from one another and provides atomic operations on multiple objects. Also, it provides no editing mechanisms or garbage collection, just read and write operations.

The Diamond Document Store [26], like the Etherphone system, manages documents that contain various media elements by reference; it also allows documents to be shared among users by reference. A simple reference count scheme suffices for deallocating objects that reside in the Document Store but are not referenced by any document or document folder since the Diamond system does not allow documents stored outside the system to reference internally stored objects. The Etherphone system, on the other hand, strives to provide voice services that can be used along with other existing services, such as the Grapevine mail system [3] and Alpine file servers [6].

The Cambridge File Server [16] was perhaps the first network-accessible storage system to require clients to take an explicit action to prevent files from being automatically garbage collected. In particular, it deletes files that are not accessible from server-maintained, but client-updated "indices". Thus, these indices play much the same role as the voice manager's interest database.

Liskov and Ladin present an example of a distributed garbage collector [14]. Their approach requires all sites that store references to other objects to run a garbage collector locally and send information about non-local references to a reference server. In some sense, their use of a reference server is similar to our use of registered interests, but much more limited. One interesting contribution they make is how to build a highly-available reference server; we could use these techniques to build an interest server.