ALOHAnet

ALOHAnet was a pioneering computer networking system developed at the University of Hawaii[?]. It was first deployed in 1970, and while the network itself is no longer used, one of the core concepts in the network is the basis for the almost-universal Ethernet.

History

Norm Abramson was a professor of engineering at Stanford, but was also an avid surfer. After visiting Hawaii in 1969, he inquired at the University of Hawaii if they were interested in hiring a professor of engineering. He joined the staff in 1970 and started working on a radio-based data communications system to connect the Hawaiian islands together, with funding from Larry Roberts[?].

By late 1970 the system was already in use, the world's first wireless packet-switched network. Abramson then managed to get a IMP from Roberts and connected ALOHAnet to the ARPANET on the mainland in 1972. It was the first time another network was connected to the ARPAnet, although others would soon follow.

Description

Prior to ALOHAnet, most computer communications tended to share similar features. The data to be sent was turned into an analog signal using a device similar to a modem, which would be sent over a known connection like a telephone line. The connection was point-to-point, and set up (typically) by manual control.

In contrast ALOHAnet was a true network. All of the computers "connected" to ALOHAnet could send data at any time without operator intervention, and any number of computers could be involved. Since the medium was a radio, there were no fixed costs so the channel was "left open" and could be used at any time.

Using a shared signal in this way leads to an important problem, if two systems on the network – known as nodes – send at the same time, both signals will be ruined. Some sort of system needs to be in place to avoid this problem. There are a number of ways to do this.

One would be to use a different radio frequency for every node, a system known as frequency multiplexing. However this would require each mode added to able to be "tuned in" by all of the other machines. Soon there would be hundreds of such frequencies, and radios capable of listening to this number of frequencies at the same time are very expensive.

Another solution is to have "time slots" into which each node is allowed to send, known as time division multiplexing. This is easier to implement because the nodes can continue to share a single radio frequency. On the downside if a particular node has nothing to send, their slot goes wasted. This leads to situations where the available time is largely empty and the one node with data to send has to do so very slowly just in case one of the other 100 nodes decides to send something.

ALOHAnet instead invented a new solution to the problem, one that has since gone on to become the standard, carrier sense multiple access. In this system there is no fixed multiplexing at all. Instead each node listens to see if anyone else is using the channel, and if they don't hear anyone, they start talking.

Normally this would mean that the first node to start using the radio would have it for as long as it wanted, which means the other nodes "can't get a word in edgewise". In order to avoid this problem the ALOHAnet made the nodes break down their messages into small packets, and send them one at a time with gaps between them. This allowed other nodes to send out their packets in between, so everyone could share the medium at the same time.

There is one last problem to consider. If two nodes attempt to start their broadcast at the same time, you'll have the same sorts of problems you would with any other system. In this case ALOHAnet invented a very clever solution. After sending any packet the nodes listened to see if their own message was sent back to them by a central hub. If they got their message back, they could move on to their next packet.

If instead they never got their packet back, that would mean that something prevented it from arriving at the hub – like a collision with another node's packet. In this case they simply waited a random time and tried again. Since each node picked a random time to wait, one of them would be the first to re-try, and the nodes would then see that the channel was in use when they tried. No collision.

This sort of collision avoidance system has the advantage of allowing any one node to use the entire network's capability if no one else is using it. It also requires no "setup", anyone can be hooked up and start talking without any additional information like the frequency or time slot to use.

On the downside if the network gets busy, the number of collisions can rise dramatically to the point where every packet will collide. For ALOHAnet the maximum channel utilisation was around 18%, and any attempts to drive the network over this would simply increase collisions, and the overall data throughput would actually decrease.

Slotted Aloha was a modification to the Aloha protocol which raised the channel utilisation efficiency up to around 35%. With this method, a centralised clock sent out small clock tick packets to the outlying stations. Outlying stations were only allowed to send their packets immediately after receiving a clock tick. If there is only one station with a packet to send, this guarantees that there will never be a collision for that packet. On the other hand if there are two stations with packets to send, this algorithm guarantees that there will be a collision, and the whole of the slot period up to the next clock tick is wasted. With some mathematics, it is possible to demonstrate that this protocol does improve the overall channel utilisation, by reducing the probability of collisions by a half.

The relatively low utilisation turns out to be a small price to pay given the advantages. A slight modification of this system for wired networks by Bob Metcalfe[?] improved collision avoidance on busy networks, and this became the standard for Ethernet. Today the technique is known as CSMA/CD, carrier sense, multiple access, collision detection.

Collision detection mechanisms are much more difficult to implement in wireless systems when compared to wired/cabled systems, and Aloha did not even attempt to check for collisions. In a wired system, it is possible to abandon the transmission of colliding packets by first detecting the collision, and then notifying the senders. This is not generally a feasible option in wireless systems, and was not attempted in Aloha.

The ALOHAnet itself was run using 9600 baud modems across Hawaii. The system uses two 100 kHz "channels" (slices of frequency), one known as the broadcast channel at 413.475 MHz, and the other the random access channel at 407.350 MHz. The network was a star, with a single central computer (a HP 2100[?]) at the university receiving all messages on the random access channel, and then re-broadcasting them to all of the nodes on the broadcast frequency. This setup reduced the number of collisions possible, there could be no collisions at all on the broadcast frequency, for what that was worth. Later upgrades added repeaters that also acted as hubs, greatly increasing the area and total capability of the network.

Send and receive packets were identical. The packet had a 32-bit header with a 16-bit parity check, followed by up to 80 bytes of data and another 16-bit parity check.

Links:

ALOHA Packet Broadcasting: A Retrospect (http://www.ulib.org/webRoot/Books/Saving_Bell_Books/SBN%20Computer%20Strucutres/csp0432.htm)