|
`
`| COMPUTER
`| NETWORKS
`'| PROTOCOLS
`
`iedla
`
`D.W.DAVIES - D.L.A.BARBER
`W.L.PRICE:C.M.SOLOMONIDES
`
`Ll
`
`=
`
`
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 1
`
`

`

`

`

`

`

`
`
`
`
`158
`
`COMPUTER NETWORKS AND THEIR PROTOCOLS
`terminals are intendedto be located very close to broadcast systemsuser devices
`thus obviating the need for long and expensive land-based connections ‘4
`
`comparatively limited capacity. Such packet terminals can even be Mobile,
`
`mounted onvehicles, an important consideration in military and other contexts.
`The greatest portability is possible in packet radio systems, where hand-heldoy
`pocket terminals are quite feasible.
`3
`
`The technologyof all broadcast systems, whatever their nature, has a. great
`deal in common, though the problemsof contention resolution are somewhat
`
`different and require different techniques for their resolution. Much of today's
`technology has sprung from developments of the ALOHAsystem, which iga
`ground radio system. Weshall therefore consider this system first, then proceeg
`to a discussion of the more complicated ground radio systems; this will be
`followed by an account ofsatellite broadcast systems and cable broadcast
`systems.
`
`5.2 PACKET RADIO SYSTEMS
`
`The ALOHAsystemis essentially a UHF packet broadcast system created
`for very pragmatic reasons (including the poor quality of local telephonelines)
`by a team at the University of Hawaii; it first became operational in 1970. The
`system covers the Hawaiian Islands, Figure 5.2, and is centred on the island of
`Oahu. Inexpensive access is afforded to central time-sharing computer systems
`for several hundred terminal users. In the first instance communication ‘was
`limited to a large group of terminals in the Honolulu district within direct radio
`range of the central station. User-to-user communicationis also catered for.
`
`
`
`Kauai 3
`i
`
`
`Ors"
`
`
`Wo
`oo”
`
`yor
`
`M Menehune central station
`
`4 Repeater station
`» User node
`
`60 miles
`ed
`
`Figure 5.2 The ALOHAnetwork coverage
`
`Hawaii
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`

`

`159
`
` PACKET BROADCAST SYSTEMS
`
`The Basic ALOHA System
`The aim of the ALOHANETisto provide cheap and easy access for a large
`number of terminal users to central computing facilities. A summary of the
`ALOHAproject may be found in Binderet al.’ User-to-computer communi-
`cation is via a 100 kHz random-access channel at 407.350 MHz;the broadcast
`return channel, computer-to-user,
`is also of 100 kHz bandwidth at 413.475
`MHz.Direct user-to-user communication is not catered for (user-to-user com-
`munication is possible by transferring data to the central switch and then
`forwardingit to the destination user) and,until the addition of packet repeaters,
`the system waslogically equivalent to a star-connected network. The central
`communications processor, the Menehune (or packet station), located.at Hon-
`olulu on Oahu, which receives packets from users andis responsible for sending
`packets to them, is an HP 2100 minicomputer. Menehuneis a Hawaiian name
`for an imp—areference to the ARPA node. Thepacket transmission data rate
`is 9600 baud, packets consisting of a header (32 bits), a header parity check
`field (16 bits), and up to 80 bytes of data, followed by a data parity checkfield
`(16 bits). Maximumsize packets are therefore 704 bits in length and take about
`73 milliseconds to transmit; propagation timeis negligible in comparison.
`Control of the broadcast channel from the central computer to the users
`presents no problem, because only onetransmitter is using the channel. Packet
`headers contain user addresses which enable individualreceivers to identify the
`traffic intended for them. The user-to-computer channel, referred to above as
`random-access, could have been apportioned to individual users by a fixed
`allocation scheme, such as frequency division multiplexing or time division
`multiplexing. However, the nature of terminal traffic is almost always bursty
`and a fixed allocation would hardly make thebest use of the communication
`medium, hence the choice of a random-access scheme.
`This scheme, known as pure ALOHA,allowsa packet terminal to transmit
`packets at times which are completely independentof packet transmissions from
`other terminals. A natural consequence of this independence of action is that
`packets from different sources may be transmitted at the same time and therefore
`collide or overlap as they arrive at the Menehune central station; an overlap
`that affects only the smallest fraction of transmission time has the sameeffect
`as an overlap of complete packets; both packets are irretrievably corrupted,
`Figure 5.3 indicates the way in which overlaps may occur. Packets subject to
`such overlap are rejected by the Menehune and the fact of overlap is made
`knownto the respective transmitting terminals by absence of the acknowledge-
`ment signal which would otherwise be sent by the Menehune to the packet
`terminals. Packets refused by the Menehune on account of an overlap are
`retransmitted by the packet terminals after a time-out period. It is plainly
`obvious that an immediate retransmission of packets by these terminals, or,
`indeed, retransmission after a fixed, uniform timeinterval, would just result in
`
`
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`

`

`COMPUTER NETWORKS AND THEIR PROTOCOLS
`
`
`a second overlap; therefore retransmission takes place at each terminalafterq
`
`random delay. Clearly the numberofoverlaps is a function oftraffic intensity:
`the greaterthe traffic, the greater the probability of overlaps.It is also essential.
`that acknowledgement packets should be sent with highest non-preemptive
`priority from the Menehune to the packet terminals; otherwise unwanted—
`retransmission may occur.
`Error control on the broadcast channel (Menehune to packet terminals)
`presents difficulties. Ideally this should be on the samepositive acknowledgement
`basis as the error control in the other direction on the random-access channel,
`However, acknowledgement packets destined to the Menehune would have to
`contend for the random-access channel in just the same way as data packets.
`Binderet al? state that, because of this contention, at full channel loading each
`random-access packet must be retransmitted an averageof 1.7 times; thus each
`data packet or acknowledgement packet must be sent 2.7 times on average
`before it is successfully received. In an error-free situation, to ensure that the
`acknowledgement
`is successfully transmitted by the packet
`terminal, the
`Menechune must send the data packet 2.7 times on average, even though the
`packet may have arrived correctly the first time. Where errors occur, the
`multiple transmissions from the Menchunewill be essential if an acknowledge-
`ment system is to operate correctly. This is evidently very wasteful of bandwidth
`and can be avoided by not using acknowledgements in this channel, relying on
`low error rates and a system of reporting errors to the user, who may decide to
`repeat a transaction. Where, for particularusers,this is not acceptable, a system
`of positive acknowledgement may be introduced on a selective basis.
`Collision
`
`Terminal_1___§=[ ZZ __Jime
`
`
`—_
`t =
`1
`Terminal_2 __
`=a
`|
`_ _Time
`
`1
`
` 160
`
`
`
`Figure 5.3 Packet timing in pure ALOHA
`
`Terminal_3___
`
`Terminal_n
`
`[1
`
`——
`
`! Collision |
`cross-section,
`zt
`
`___Time
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`PMC Exhibit 2029
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`