[aprssig] Local Event using RELAY?

[Henk de Groot]

AE5PL Lists schreef:
> But the numbers you espoused from the ALOHA project are not about
> channel access only but about their findings with retries.

Here is a part from the book "Computer Networks" by Andrew S. Tanenbaum. I 
see you are correct, the 18.4% is about the *datalink* utilisation (the 
ALOHA channel, not the RF channel); how much data can be transported over 
this data connection when the RF channel access uses pure ALOHA. So on RF 
you would see at least 18.4% worth of packets that actually make it to the 
other side without damage plus all the packets that are corrupted along 
the way and therefore do occupy the RF channel but do not contribute to 
the amount of successfully transported data packets on the datalink layer.

So the utilisation of the RF channel must be (much) higher than the 
frequently quoted 18.4% in order to get the "optimal" datalink utilisation 
of 18.4%.

Thanks for making me read this text again.

Kind regards,

Henk.

P.S. text is in courier, I have no idea if the formulas and picutures
make sense using another font...

Sorry I can't show Figure 6.3, is not doable in ASCII...

-------------------------------------------------------------------------
6.1.2. Pure ALOHA and Slotted ALOHA

In the early 1970s, Norman Abramson (1970, 1973a, 1973b, 1977) and his 
colleagues at the University of Hawaii devised a new and elegant method to 
solve this problem. Their work has been extended by many researchers since 
then (Binder et al., 1975; Carleial and Hellman, 1975; Ferguson, 1975b; 
Lam, 1974; and Roberts, 1973, to name just a few). Although Abramson's 
work, called the ALOHA system, used ground based radio packet broadcasting 
rather than satellite packet broadcasting, the basic idea is applicable to 
any system in which uncoordinated users are competing for the use of a 
single shared channel. Nevertheless, there are some important differences 
between ground radio packet broadcasting and satellite packet radio 
broadcasting (notably the propagation delay). We will examine ground radio 
in general, and the University of Hawaii ALOHA system in particular, later 
in this chapter.

The basic idea of an ALOHA system is simple: just let the users transmit 
whenever they have data to be sent. There will be collisions, of course, 
and the colliding packets will be destroyed. However, due to the perfect 
feedback property of packet broadcasting, the sender of a packet can 
always find out whether or not his packet was destroyed by just listening 
to the downward rain of packets one round trip time after sending the 
packet. If the packet was destroyed, the sender just waits a random amount 
of time and sends it again. The waiting time must be random or the same 
packets will collide over and over, in lockstep. Systems in which multiple 
users share a common channel in a way that can lead to conflicts are 
widely known as *contention* systems.

A sketch of packet generation in an ALOHA system is given in Fig. 6 1. We 
have made the packets all the same length because it has been shown that 
the throughput of ALOHA systems is maximized by having a uniform packet 
size rather than allowing variable length packets (Abramson, 1977; 
Ferguson, 1975a; Gaarder, 1972).

         User
            ------------------------------------------------
          A          [==]  [==]
            ------------------------------------------------
          B             [==]
            ------------------------------------------------
          C       [==]         [==]                    [==]
            ------------------------------------------------
          D      [==] [==]              [==]       [==]
            ------------------------------------------------
          E [==]                    [==]      [==]
            ------------------------------------------------

          Fig. 6-1. In pure ALOHA, packets are transmitted at completely
          arbitrary times.

Whenever two packets try to occupy the channel at the same time there will 
be a collision and both will be garbled. You should realize that if the 
first bit of a new packet overlaps with just the last bit of a packet 
almost finished, both packets will be totally destroyed, and both will 
have to be retransmitted later. The checksum cannot (and should not) 
distinguish between a total loss and a near miss. Bad is bad.

A most interesting question is: What is the throughput of an ALOHA 
channel? Let us first consider an infinite collection of interactive users 
sitting at their terminals. A user is always in one of two states: 
thinking or blocked. Initially, all users are in the thinking state. 
Whenever someone decides what to do next, he types a line of text followed 
by a carriage return. At this point he is blocked and stops thinking. The 
microcomputer inside the terminal immediately locks the keyboard to 
prevent any more input. It then sends a packet containing the line to the 
satellite and waits R sec to see if it was successful. If so, the user's 
keyboard is unlocked. If not, the keyboard remains locked, and the packet 
is retransmitted over and over until it is successfully sent.

Let the "packet time" denote the amount of time needed to transmit the 
standard, fixed length packet (i.e., the packet length divided by the bit 
rate). At this point we assume that the infinite population of users 
generates new packets according to a Poisson distribution with mean S 
packets per packet time. (The infinite population assumption is needed to 
ensure that S does not decrease as users become blocked.) If S > 1, the 
user community is generating packets at a higher rate than the channel can 
handle, and nearly every packet will suffer a collision. For reasonable 
throughput we would expect 0 < S < 1.

In addition to the new packets, the users also generate retransmissions of 
packets that previously suffered collisions. Let us further assume that 
the probability of k transmission attempts per packet time, old and new 
combined, is also Poisson, with mean G per packet time. Clearly, G >= S. 
At low load (i.e., S ~= 0), there will be few collisions, hence few 
retransmissions, so G ~= S. At high load there will be many collisions, so 
G > S. Under all loads, the throughput is just the offered load, G, times 
the probability of a transmission being successful that is, S = GPo, where 
Po is the probability that a packet does not suffer a collision.

A packet will not suffer a collision if no other packets are sent within 
one packet time of its start, as shown in Fig. 6 2. Under what conditions 
will the shaded packet arrive undamaged? If any other user has generated a 
packet between t0 and t0 + t the end of that packet will collide with the 
beginning of the shaded one. In fact, the shaded packet's fate was already 
sealed even before the first bit was sent, but due to the long propagation 
delay, it has no way of knowing that another packet was already underway. 
Similarly, any other packet started between t0 + t and t0 + 2t will bump 
into the end of the shaded packet.

        | +--------------+            +--------------+ |
        | |              |            |              | |
        | +--------------+            +--------------+ |
        |      ^        +--------------+               |
        | Collides with |//////////////| Collides with |
        | the start of  +--------------+ the end of    |
        |  the shaded   |              |  the shaded   |
        |    packet     |              |     packet    |
        t0            t0 + t        t0 + 2t         t0 + 3t

          Fig. 6-2. Vulnerable period for the shaded packet.

The probability that k packets are generated during a given packet time is 
given by the Poisson distribution:

                    k  -G
                   G  e
           Pr[kl = -------
                      k!
                                             -G
so the probability of zero packets is just e  . In an interval two packet 
times long, the mean number of packets generated is 2G. The probability of 
no other traffic being initiated during the entire vulnerable period is
thus given by
       -G
Po = e  . Using S = GPo, we get

                                -2G
                          S = Ge

This result was first derived by Abramson (1970).

The throughput offered traffic relation is shown in Fig. 6 3. The maximum 
throughput occurs at G = 0.5, with S = 1/(2e), which is about 0.184. In 
other words, the best we can hope for is a channel utilization of 18%. 
This result is not very encouraging, but with everyone transmitting 
whenever he wants to, we could hardly have expected a 100% success rate.
-------------------------------------------------------------------------