I realize that this description is very "bottom-up" in its approach, and that this may be a problem for some readers, who would only like to find out how to get NadaNet running. Therefore, I have added a new "top-down" description of the Applesoft extensions designed for those who are more concerned with the functional level than with the implementation level.

Nevertheless, this description serves a useful purpose for those who are curious about the design choices made and their rationale, so I have updated this original document to correspond with the current state of the NadaNet implementation. I have also made a separate document descibing the Parallel Work Simulator.

In 1996, I began thinking about how one might network Apple II computers using only its built-in serial I/O: the pushbutton inputs and the annunciator outputs, and wondered what could be done with such a network. I have worked intermittently on this project over the intervening years, more frequently since I have retired. This document describes its current state.

The possibility of creating a useful network using only wire and software was esthetically appealing. Because it initially required no hardware other than the connecting wires, I dubbed it "NadaNet" ("nada" is Spanish for "nothing"). It was an interesting challenge to design an Ethernet-like network from the ground up. The exercise provided an experimental vehicle to illuminate the various issues and tradeoffs in creating and using such a network. It also became a tool for exploring various higher-level applications of networking, such as client-server and parallel computing.

To add more processors and save space, I decided that I would package several Apple //e main boards together, without keyboards or peripheral slot cards. I settled on a wooden cube about one foot on a side which I slotted to hold up to 8 main boards. For more information, see AppleCrate: An Apple II-Based Parallel Computer.

For simplicity, I decided to use only a single wire (plus a ground wire), connected at each machine to both a pushbutton input and an annunciator output. The first question was, "How fast can an Apple signal over such a link using only software?"

My first experiments in 1994 used tight, precisely timed loops to send and receive the data bits. I found that I could signal at a rate of 14 cycles per bit, for a raw data rate of about 70kbps. Because of the differences in mechanisms for setting annunciators versus reading pushbuttons, the send routine was the speed-limiting factor. However, 70kbps seemed sufficient to enable the other experiments, so I coded the first SENDPKT and RCVPKT routines using this approach.

I later realized that I could significantly speed up the data rate by unrolling the send and receive loops, resulting in signaling at the rate of 9 cycles per bit, for a raw data rate of 110kbps. This version of SENDPKT required a somewhat more space-consuming tree-structured byte send routine. Because of the limited range of relative conditional branches, I also had to split the "send byte" tree into two halves, with an extra (unconditional) branch between them. This adaptation to the 6502 resulted in the fourth bit cell being 3 cycles longer, or 12 cycles, but the overall 50% speedup was substantially unchanged.

In late Spring of 2005, I was contacted by Stephen Thomas, who had found my web site and was intrigued by NadaNet. He pointed out that RCVPKT, by using an ROL to shift in the pushbutton value, was creating "bus fights" when it wrote back to the input address. He suggested new receive code which eliminated this problem. We began an email conversation that culminated in his development of an improved SENDPKT and RCVPKT that require less space, only 8 cycles per bit (an 11% raw speed boost), and tolerate longer networks. The change required modifying the low-level packet format, including inverting the sense of data "on the wire" and regularizing the timing of the checkbyte. One consequence of these changes is that NadaNet version 2.0 does not interoperate with previous versions. To get the benefits of version 2.0, all copies of Nadanet must be version 2.0. Because of the early stage of NadaNet "rollout", this should not present much of a problem.

The sustainable data transfer rate of NadaNet in its current form, including protocol overhead, is over 10,600 bytes per second. In typical applications, much less than 100% network utilization should be expected, since delays in a contention-based network grow rapidly as utilization approaches 100%. My testing confirms that delays remain low with utilizations of up to 80%, so much of the theoretical capacity is available for practical use.

Because the sending and receiving machines are operating with different clocks, the receiving machine must "lock" to the sending machine’s transmission rate. In addition to the natural relative drift of asynchronous machines, another timing issue mandates even greater timing adaptability.

I chose to send "packets" up to 256 bytes long (plus one check byte). I also wanted to allow packets to be aligned differently with respect to page boundaries on the sending and receiving machines. Since an indexed Load on a 6502 requires an extra cycle when a page boundary is crossed, this means that the sending loop can run relatively slower by 1 cycle per byte during parts of a packet.

To accommodate this variation and the natural variation arising from asynchrony, a digital phase-lock loop is implemented in the receive byte loop by making it run two cycles per byte faster than the sending loop. RCVPKT then samples a "servo" transition sent at a fixed timing location between bytes to determine whether or not to introduce an additional three-cycle delay in the loop. Thus, if the receive loop gets ahead of the sending loop (which it will, on average, 2 out of 3 iterations), it is delayed by three cycles. This additional delay moves its data sampling point back to an optimal point in the bit cell. The result is that the receiving machine always samples the sending machine’s signal within cycles 5-7 of the 8-cycle bit cell, in spite of machine timing variations and page crossings.

Including the extra servo transition and overhead, the total time per byte sent (excluding the packet start sequence and the end-of-packet check byte) is 94 or 95 cycles per byte (depending on page crossing on the sending machine).

The "control" packets used to perform all protocol functions are 8-byte packets. With packet overhead and check byte included, the time required "on the wire" to send an 8-byte packet is 887 cycles, or about 0.87 milliseconds.

Each packet begins with a "ONE" start pulse of at least 31 cycles duration. The trailing edge of this start pulse serves to start the RCVPKT synchronization sequence.

The next packet prolog event is another transition to ONE, which provides "coarse" synchronization, bringing the read loop within 6 cycles of synchronization with the SENDPKT routine. The next significant transition is the servo transition for the first byte, which is used to bring RCVPKT into "fine" synchronization, within 3 cycles of SENDPKT. This establishes the RCVPKT data sampling time between cycles 5-7 of the 8-cycle bit cell, which is optimal sync. This condition will continue to be maintained by the RCVPKY digital phase-lock loop described above.

The data bits are sent, high bit first, at a rate of 8 cycles per bit. Note that the sense of data is inverted on the wire, with a data 0 sent as ONE and a data 1 sent as ZERO.

After the low bit is sent, while preparing for the next byte, a ZERO is sent for 22 or 23 cycles (depending on page crossing). The next transition to ONE state is the "servo transition" which RCVPKT uses to maintain synchronization with SENDPKT. Note that transitions to ONE are driven by the emitter followers in the NadaNet adapters, so they are sharper transitions than transitions to ZERO created by resistive pulldown of the network bus. All NadaNet critical timing is referred to transitions to ONE because of they are more accurately timed.

The ONE state is held for 8 cycles prior to beginning transmission of the next data byte.

After all data bytes have been sent, the check byte is sent with the same timing as all other bytes.

In order to perform work across the network, "command protocols" are defined to establish an orderly means for all machines to share the network and to communicate effectively.

The first requirement for an arbitration scheme is that it avoids most "collisions", or attempts by more than one machine to send simultaneously. NadaNet’s primary means of avoiding collisions is an arbitration process which, when the network is busy, results in machines sending packets while other machines continue to wait their turn. A lightly loaded network is a different case, and will be considered separately.

Arbitration consists of continuously sampling the network for activity, and, when inactivity is sensed, waiting for a defined period of idle time (dependent on machine ID) before attempting to send. The minimum arbitration time is about one millisecond. The minimum arbitration time requirement is chosen to be greater than the time between packets that comprise most protocols, so that each protocol is composed of an atomic series of packets, uninterrupted by any other traffic. A few service protocols can require more than a millisecond to reply to a request, so they "lock" the net until they can respond by holding the net in a ONE state, effectively extending the start pulse for the next packet. (See Network Locking, below.)

Since machines contending to send will all see the same network activity and inactivity, if they all used the same arbitration time, all contending machines would attempt to seize the network simultaneously, resulting in frequent, repeating collisions.

Therefore, the arbitration interval for each machine is set to a base "minimum arbitration" time plus a time dependent on the machine’s unique ID number. This results in machines getting access to the network with a fixed priority, with lower machine IDs receiving higher priority.

On the other hand, if the network is lightly loaded, it is less probable that one or more senders will be waiting on a current sender to synchronize their arbitration timing, so collisions can occur randomly. These collisions occur because there is a finite time between an arbitrator sensing the idle state of the network and asserting a lock to sieze it. During this window, another arbitrator can also decide that it has "won", and a collision is the result.

The probability of a collision is directly proportional to the length of the "sense-to-seize" window and inversely proportional to the mean time between arbitrations.

In the current implementation, the window is 20 cycles. Let us assume that "lightly loaded" means less than 50% network load, and a typical request protocol duration is 3000 cycles. In this case, the mean time between arbitrations will be 6000 cycles, and the probability of a random collision is 20/6000, or about 0.3%. At this rate, a random collision can be expected to occur about every 2 seconds.

When a collision does occur, it causes a checksum error on the initial request packet of a protocol, which results, 1 millisecond later, in a receive timeout on the non-existant ACK packet. When this occurs, all requests (except BPOKE, see below) re-arbitrate and re-send every 20 milliseconds for a total of up to 3 seconds (default), after which the request fails by timing out.

Of course, as network usage rises, the "busy network" case dominates, and random collisions decrease in frequency. In practice, while collisions must be considered in the design of reliable protocols, they are not a significant operational issue.

            +-----+-----+-----+-----+-----+-----+-----+-----+
            | REQ | MOD | DST | FRM |  ADDRESS  |  LENGTH   |
            +-----+-----+-----+-----+-----+-----+-----+-----+

A control packet consists of 8 bytes of data. The first byte (REQ) specifies the type of request to which a protocol pertains. All control packets within a request protocol will have this command type as their initial byte.

The second byte (MOD) is a "modifier" which specifies a particular type of packet within a request protocol (for example, "REQ" starts a protocol and "ACK" indicates a positive response to the request).

The third and fourth bytes specify the unique ID number of the destination (DST) and sending machine (FRM), respectively.

The last four bytes contain command-specific parameter or response data, often an address and length.

Each protocol begins with a successful arbitration for control of the net.

After winning the arbitration, a protocol is initiated by a control packet with a "request" modifier, including up to 4 bytes of parameters for the requested command.

For almost all protocols, a good request packet leads to an ACK or NAK response from the target machine, containing up to 4 bytes of response data. (An erroneous request packet results in no response, and a subsequent retry.)

For protocols requiring transfer of more than 4 bytes of data, a series of data packets with a length of 256 bytes may follow, with the final packet being 1 to 256 bytes in length.

If the request response or transfer of data requires acknowledgement (for example, because the request has a side effect which would prevent recovery by simply retrying the request), the protocol will conclude with a "Data ACK" control packet. This packet authorizes the receiver to change state in accord with the request.

In summary, a protocol begins with arbitration, consists of a request control packet and one or more control and data packets, and concludes with a network idle state of at least a minimum arbitration period. (Since a following protocol begins with an arbitration.)

Note that there is no "out-of-band" signal that distinguishes a data packet from a control packet. An 8-byte data packet could be mistaken for a control packet if it were not for the fact that data packets occur only within the context of protocols, and are delayed less than a minimum arbitration time from a preceding packet in the protocol.

If the network has been idle for at least a minimum arbitration period, then the next packet will be the initial "request" packet of a protocol.

The normal state of a "slave" machine is to be endlessly re-calling the SERVER loop whenever it is not doing some other task. The SERVER loop exits to the caller whenever a request is processed, a key is pressed, or the iteration count expires so that the caller can perform other work. A 1-byte counter controls the internal iteration of the SERVER loop. Normally, SERVER is entered (and exits) with this counter equal to zero, so that SERVER iterates up to 256 times before returning to its caller. If desired, it can be preset to a different value to cause fewer iterations before returning. If the network is idle, each iteration will take approximately 20ms.

The SERVER loop polls for the initial messages of request protocols. To synchronize with the start of a protocol, it waits on first entry for the network state to remain either idle or locked for three-quarters of the minimum arbitration period. This time is sufficient to ensure that the next packet seen will be the start of a protocol, but not so long that a request coming a minimum arbitration delay after the end of the previous message will be missed. SERVER performs this resynchronization whenever it receives a control message not directed to the serving machine..

When it receives a service request directed to the machine on which it is running, it services it by jumping to the associated request service routine.

The service routine performs any additional protocol steps required by the service, and then returns to the code that called SERVER.

For some commands, the time to respond to a request may exceed the minimum arbitration interval, which would break the atomicity rule for a protocol. In these cases, the machine making the delayed response may lock the network by asserting a ONE on the net for a period which should not generally exceed 35 milliseconds (set by the slowdown interval of a Zip Chip, which the network code accommodates). If there are no accelerators involved, the lock period is not limited, though long locks are undesirable.

The effect of asserting ONE is to extend the "start" pulse of the following packet. The locked state is terminated naturally by the completion of the following packet.

The PEEK request allows the requesting machine to request the serving machine to send ‘length’ bytes of its memory, starting at ‘address’, placing the data at the requesting machine’s ‘locaddr’.

The requesting machine begins by sending the PEEK request and the address and length parameters. The serving machine responds by sending an ACK packet. If the length specified is 4 bytes or less, then the data will be returned to the requester in the ACK packet and the protocol ends.

If the data length is more than 4 bytes, then additional data packets are sent until the request is satisfied.

The protocol terminates without a Data ACK, since the requestor can retry the request if an error occurs.

The POKE request allows the requesting machine to request the serving machine to store ‘length’ bytes in its memory, starting at ‘address’. The data is sent from the requesting machine’s ‘locaddr’.

The requesting machine begins by sending the POKE request and the address and length parameters. The serving machine responds by sending an ACK packet.

The requester then sends data packets until the request is satisfied.

The protocol terminates with a Data ACK from the serving machine, to confirm to the requestor that the data was transferred without error.

The CALL request allows the requesting machine to request the serving machine to call code at ‘address’ in its memory, passing the supplied parameters in the A and X registers.

The requesting machine sends the CALL request and the address and register parameters. The serving machine responds by sending an ACK packet, then calls the requested address.

The PUTMSG request allows the requesting machine to request a message server machine to store a message of type ‘class’ and ‘length’ bytes in its message store for later retrieval by the same or a different machine. The message length must be between 1 and 255 bytes. It is located at the requesting machine’s ‘locaddr’.

The requesting machine begins by sending the PUTMSG request and the class and length parameters. The serving machine responds by sending an ACK packet if it can comply, or a NAK if has insufficient space. (Because this determination can take longer than a minimum arbitration time, PUTMSG locks the network until it can send ACK or NAK.)

The requester then sends a data packet of ‘length’ bytes.

The protocol terminates with a Data ACK, to confirm to the requester that the data was transferred without error.

The GETMSG request allows the requesting machine to request a message server machine to retrieve the oldest message of type ‘class’ in its message store. The message, if any, is stored at the requesting machine’s ‘locaddr’ and its length is returned in ‘length?’.

The requesting machine begins by sending the GETMSG request and the class parameter. If the server has no stored messages of the requested class, then it returns a NAK packet and the protocol ends. (Because this determination can take longer than a minimum arbitration time, GETMSG locks the network until it can send ACK or NAK.)

If the server has a message of the requested class, it responds by sending an ACK packet containing the length of the message, followed by a data packet containing the message itself.

The protocol terminates with the requester sending a Data ACK to confirm to the server that the data was transferred without error. Upon receiving the Data ACK, the post office server deletes the message from its queue.

The PEEKINC request requests the destination machine to send 2 bytes of its memory, at ‘address’, and then increment that memory by ‘increment’. The original value prior to the increment is returned in ‘value?’.

The requesting machine sends the PEEKINC request containing the ‘address’ and ‘increment’ parameters. The serving machine responds by sending an ACK packet containing the original, unincremented value.

PEEKINC is a "network atomic" protocol that allows machines to allocate work or to rendezvous after completing a unit of work.

The BPOKE (Broadcast POKE) is a broadcast request for all serving machines to store a 2-byte ‘value’ in their memories at ‘address’.

The requesting machine sends the BPOKE request containing the ‘address’ and ‘value’ parameters. Since it is a broadcast request, there are no ACK packet(s).

BPOKE allows a machine to send a signal to all serving machines simultaneously. For example, It can be used to "trigger" the continuation of computation after a rendezvous has been detected.

Because BPOKE is not acknowledged, it cannot detect errors in its reception. Therefore, if BPOKE is to be reliably sent, it is necessary to prevent collisions. This is achieved by arbitrating for the network and locking it. After delaying for about 20 milliseconds in the locked state, any in-process collisions with other senders resolves to their subsequent arbitration. The request then completes by sending the BPOKE packet. This long "lead-in" to the BPOKE request also allows for a BASIC polling loop that may spend several milliseconds each iteration outside of SERVER.

Early in the design of the AppleCrate, it became clear that, since the machines would have no I/O capabilities other than the network, they would need to be booted from the network. This required that the ROMs on the boards be replaced with EPROMs containing modified RESET code to perform the network boot.

The BOOT protocol is a bit unusual, in that the Master machine initiates it as a delayed broadcast response to one or more GETID requests sent by the machines requesting booting.

When a network-booting machine is reset, it does standard initialization, then does a Paddle 3 read to create a unique temporary machine ID. (AppleCrate boards use the Paddle 3 timer as a pulse stretcher for an attached "send" LED, so each board is provided with a resistor chosen to produce a unique paddle read result.)

It then uses this temporary ID to make a GETID request to the Master (machine ID = 1). If the Master does not respond, then the ROM boot code re-sends the GETID request about every 100ms. until it receives a response.

The Master GETID service routine looks at the requesting ID, and if it is temporary (>127) it assigns the next available permanent ID and sends it in an ACK to the requesting machine. (If the sender already has a permanent ID, then the Master simply returns it in the ACK.)

If the GETID is successful, the requesting machine sets its ID to the assigned value and Data ACKs the Master, confirming that the ID has been received and installed. The Master then allocates the ID and notes that a GETID has been processed.

The requesting machine then enters a RCVPKT loop looking for a BOOT request control packet, either broadcast or directed to it specifically. If more than 5 seconds elapse without receiving a BOOT request, the machine will re-issue a GETID (this time using its assigned ID code).

Meanwhile, the Master’s SERVER loop is counting the approximate passage of time. After about one second has passed without processing any GETID requests, the Master checks to see if any GETIDs were received earlier. If they were, then the Master sends a broadcast BOOT request containing the target address and length of the boot code to follow. The reason for delaying the boot response is to allow multiple simultaneously reset machines to "check in" with GETIDs and prepare themselves so that they can all be broadcast-booted simultaneously.

The booting machines, upon receipt of a directed or broadcast BOOT request packet, receive the boot code directly into the address, and with the length, specified in the BOOT request. Upon the error-free completion of this transfer, the video display is cleared, a banner showing the machine ID is written, and control is given to the initial address of the boot code. If an error is detected during the transfer, the booting machine will retry the process starting with another GETID.

NadaNet is a TTL-level serial network in which ONE is represented as a logic high (greater than +2 volts) and ZERO is represented as a logic low (less than +0.7 volts). The fanout capability of a TTL annunciator output is sufficient to drive a dozen or so TTL pushbutton inputs if they are not otherwise connected, as in the case of the early Apple II machines.

Although NadaNet began—and was named—for not requiring any extra hardware, some changes Apple made in the Apple //e pushbutton circuits necessitated hardware buffering.

The Open- and Closed-Apple keys on the post-][plus machines are connected to pushbutton inputs 0 and 1. In order to function in the same manner as game controller buttons, the keyboard contains 470-ohm pulldown resistors for each Apple key, and pressing the key connects the corresponding pushbutton input to +5 volts.

In addition, to support board self-test at the factory, the main board contains 11K pullup resistors pulling a keyboard-less pushbutton input to +5v.

The effect is that the pushbutton inputs on later machines are relatively low-impedance inputs, each of which sinks on the order of 10mA when driven high. While an annunciator output could drive one or two such inputs, any attempt to connect more than a small number of machines together directly would overwhelm the drive capability of the annunciator outputs of the machines.

My solution was to add emitter followers to drive the pushbutton inputs and the network. These emitter followers are built onto a 16-pin header (or machined-pin socket) that plugs into the 16-pin game port and provides the network and ground wires to connect to the network bus. The wiring diagram is shown below. (Note that the usual 0.1uF decoupling capacitor between +5v and ground is not shown in the diagram.)

The 4.7K pulldown resistor on the network adapters is sufficient if there are no more than eight feet of shielded cable per machine. If more cable is used, then an additional pulldown resistor shunting the net should be added to speed up the fall time of the network signals. A good rule of thumb is that the effective pulldown resistance should be about 45000/L ohms, where L is the total length of shielded audio/video cable used, and the effective resistance of all pulldowns in parallel should not be less than 180 ohms (corresponding to a maximum cable length of 250 feet). CAT-5 twisted pair has a lower capacitance per foot than shielded cable, so about 3 feet of CAT-5 cable is equivalent to 1 foot of shielded cable.

I chose standard RCA connectors for NadaNet because they are inexpensive, plentiful, shielded, and intrinsically polarized. Standard audio or video cables are used to interconnect adapters, and standard Y-adapters are used to daisy-chain machines when needed.

NadaNet was originally conceived with the Apple ][ plus in mind. As later machines became targets, the interface changed somewhat to accommodate the changed input specifications of those machines. It should work well on all models of Apple II except the Platinum //e and other //e’s of late vintage. These machines had 0.1uF capacitors added between the pushbutton inputs and ground, effectively precluding fast signaling. To use one of these later machines on NadaNet will require locating the PB1 capacitor (C95) and snipping one lead to eliminate it from the circuit. This will have no ill effects on your machine at all. (C95 is the third capacitor from the rear of the main board just behind the cassette in and cassette out jacks.)

I have tested NadaNet with the IIgs, and it works when running at 1MHz in the network code. I am planning a IIgs version of NadaNet which will incorporate "slowdown" and "restore speed" code to allow operation outside NadaNet to proceed at the control panel-selected speed. (One IIgs peculiarity I note is that the 16-pin game port is mechanically "rotated" 180 degrees relative to all other Apple II machines—something to watch out for!)

Since my primary Apple //e machine has a Zip Chip accelerator installed, the NadaNet code contains instructions which will cause the Zip Chip (and some other accelerators) to slow down during the network code. The slowdown code does not attempt to control the chip directly, but simply makes a reference to a slot 6 Disk Controller I/O address. By default, most accelerators slow down for many milliseconds when such an address is referenced, since it is commonly used for a 5.25" disk controller, which requires a 1MHz speed. No actual disk controller needs to be installed in slot 6 for this to work, as long as the acceleration mechanism slows down on slot 6 accesses.