STANLEY WINKLER
`Editor and Program
`Chairman
`
`CARL HAMMEi
`Conference Chairman
`
`AFIPS
`
`CONFERENCE
`PROCEEDINGS
`
`1976
`
`~ATIONAL
`COMPUTER
`CONFERENCE
`
`Member National Bicentcnninl
`Service A Ilia nee
`
`AFIPS PRESS
`210 SUMMIT AVENUE
`MONTVALE, NEW JERSEY 07645
`
`June 7-10, 1976
`
`New York City, New York
`
`Petitioner Emerson's Exhibit 1048
`Page 1 of 10
`
`

`

`The ideal! and opinion!! exprc!lllCd herein are solely those of the authors and
`are not necessarily representative of or endorsed by the 1976 National
`Computer Conference or the American Federation of Information ProcesS(cid:173)
`ing SocietieR, Inc.
`
`Library of Congress Culalog Card Number 55-44701
`AFIPS PRESS
`210 Summit A\"enue
`Moul vale. New Jersey 07645
`
`© 1976 by the American Federation of Information Proces.~ing Socielies,
`Inc., Montvale, New Jersey 07G45. All rights reserved. This book, or purls
`the reof, may not be reproduced in any form without permiH~ion of the
`publi11her.
`
`P r inted in the United Stales of America
`
`Petitioner Emerson's Exhibit 1048
`Page 2 of 10
`
`

`

`On me ai:>ureme nl facilities rn packet radio :;ystC' ms*
`
`l1y FOUAD A. TOBAGI, STANLEY E. LIEBlmSON and
`LEO:\ARD KLE INROCK
`I '1111·r•••l11 of Califoniia,
`(.,, Angt·I~•. California
`
`ABS'rRACT
`
`The growth of computer networkll has proven both the
`need for and the success of resource sharing t!'Ch(cid:173)
`nology. A new resource sharing technique, utilizing
`broadcast channels, has been under de,·elopmenl 11~ a
`Packet Radio system and will shortly undergo testing.
`ln this pnper, we consider thnl Packet Radio system.
`and examine the mensuromcnl la8k8 necessary to sup(cid:173)
`port such important measurement go;1ls as the vnli(cid:173)
`dalion of mathematical models. the evaluation of sys.
`tern protocols and the detection of de:sign flaws. We
`de8cribe the data necessary to measure the many
`aspects of network behavior, the tools needed to gather
`this data and the means of collecting it at a central
`location; 1111 in u fashion consistent with the system
`protocols and hardware constraints, :1nd with minimnl
`impact on the ~yslem operation itself.
`
`IN'rIWDUCTION
`
`This paper is prim;irily concerned with the unique
`measurement aspects of Pal·ket Radio Systems as
`regard!! network evaluation, 11nd considers the design
`of a set of measurement facilities, lhe development of
`data gathering techniques with in t he framework of the
`iiyi1lem design and the use of thm;c measurements to
`evaluate lhe !<YSlern pel'formance and its operational
`algorithms.
`The need for sharing of computer resources by orga.
`nizing these resources into computer networks has
`been long recognized' and the feasibility of construct(cid:173)
`ing such networks has been demonstrated by many
`successfully operating network systems. Perhaps the
`most prominent example is t he ARPANET.' which
`utilizes the technique of packet-switching, appropriate
`for bursty computer network traffic, thus achieving
`better sh11ring of the communication resources.
`The ARPA "ET emerged in 1969 as the first major
`packet-switching network experiment;
`since
`the
`essence of an experiment i;\ measurement, and in line
`
`•This work wa• supported hy th~ Ad,·nnced Research ProjeclK
`AgPnr)' <>f th~ l>cpnrtmcnt of D~f~nsP (DA HC-15-73-C-OSCS).
`
`with Hamming'x observation that "it is difficult to have
`a science without meallurement", considerable care was
`taken from the beginning in the design and develop(cid:173)
`ment effort lo include the tools necessary and appro(cid:173)
`priate to satisfy the many measurement goals. As a
`result of well designed experiments on the ARPA:-1ET
`using these tools. valuable insight hns been gained
`reg:1rding the network usage and behavior.'
`The Pncket Radio System is another yet different
`example of 11 computer resource sharing network.' It
`is being developed by the Advanced Research Projects
`Agency in order to demonstrate the applicability of the
`packet rndio concept in organizing computer resources
`into a computer communications network. It is this
`packet radio network which is of concern to us in this
`paper. The network is currently in its design phase,•
`and, as was the cuse with the ARPA NET, car e is being
`taken to include the ability to measu1·e network be(cid:173)
`havior. UCLA is in charge of thiil meaimrement efforl.
`This concern for measurement ill due to several
`factors. Firstly, these measurements pro\•ide a means
`to e,·aluate the performance of the operational pro(cid:173)
`tocols employed and the identification of their key
`parameters. Moreover, this realistic obsen·ation of the
`system behavior will assist in the validation and im(cid:173)
`provement of existing analytical models devised to
`study some of these operational scheme!!, such as lhc
`access modes and routing strategiell."• Secondly. these
`measurements will allow for the detection of system
`inefficiencies and the identification of dei1ign flaws such
`as the in11d,·erlent creation of a deadlock condition.'
`Thirdly, measurement facilities and data. when used to
`improve network design, are a valtuible feedback
`process in which dei;ign deficiencies are detected and
`subsequently corrected. Wire networks differ from
`radio networks mainly in the omni-directional broad(cid:173)
`cast nature of the communication and conse<1uently the
`protocols employed; therefore, it calls for new ap(cid:173)
`proaches in lhe c.1Pi1ign and implementntion of the
`measurement facilities and their UMe.
`
`• A prelirninar)- clNnon1trnlion of the H)1¥tt.1m tj;I under w:iy. A
`prototrpc nrtwork i~ l>t>inp; srt up in thr Pnlt1 Alto, Californin,
`:tt-Pn.
`
`589
`
`Petitioner Emerson's Exhibit 1048
`Page 3 of 10
`
`

`

`590
`
`National Computer Conference. 1976
`
`In the following section. \1e present an O\'er\'iew of
`the packet radio !iY!ilcm concepts and a brief clescrip(cid:173)
`lion of the currently ><pecafied operational procedure:<.
`In a later section. we describe the network mea:;url'·
`ment facilities which con«i .. t of the measurement tools
`and the techniques for datll collection. In the la:-1t sec(cid:173)
`tion. we identify and diqcu!<~ in some detail the desir(cid:173)
`able measurement functions lo satisfy the ncecl for
`\•alidation aml pl'rformnnrc> c•\•11h1:1tion outlined above.
`
`TllE PACKET RADIO 8Y8'1'F.M
`
`Se\'eral papers have a lr<'ady nppeai-crl in the> liter(cid:173)
`ature which dcst•rilll' lht~ packet n1dio conce1)l and
`discuss many of lhc i>1>1uc:1 involved in the system
`design.' • •• 1 n thi>< :<ection, we briefly describe these
`system components and operntional procedures neces(cid:173)
`~ary lo understand the mensurement consideration8
`presented below.
`There are three ba!<ic functional components of ll
`packet radio system:
`
`(i) packet radio lerminals-the11e are the sources
`and desli naliom1 of traffic on the packet radio network.
`(ii) packet radio 11lations-thcsc function ;ts S/ r'
`switches for local tratnc aud aK interfaces between the
`broadcast system and other computers or networks.
`Also. they perform directory, monitoring and control
`functions for the overall system, and they play a cen(cid:173)
`tral role in that all tr11flic passes through the station.
`i.e., we ha,·e ;i centralized network.
`(iii) p;ickel radio repeaters-their function is to
`extend the effective rnnge of terminals and stations b~·
`acting as Store-and-Forward relay!!.
`
`The re(Jealer, which ha~ been de,·eloped by Collins
`Radio and is called a packet radio unit (PRU). con(cid:173)
`::iisls of a radio lrun:;ceiver and a microprocessor. The
`runclion of the PRU is lo receive and transmit packets
`according to dynamic routing and control algorithms
`11pecifled by the station. For simplicity and uniformit~·
`of design, the PRU is used as the front-end of terminal
`clc\•ices and of lltations, interfacing them with the
`radio net.
`In Figure 1 we show an oversim1>lificd
`picture of the PRU identifying il11 various !ICClion~:
`the radio transceiver, the store-and-forward software,
`the control process, and the measurement process.
`In thi!I initial system, the terminals, stations and
`repeaters are linked together by a single broadcast
`channel using omni-directional antennas. The re(cid:173)
`peater;; do not determine routes. All the routing com(cid:173)
`putations are performed by the i1tation. A hierarchical
`routing algorithm is used which makes the routing in
`the broadcast network re~emble routing in a point-to.
`point network by forming 11 hierarchicnl t ree :itruclure.
`This structure i~ constructed by ha,·ing the station
`assign to each repealer a lnbel which defines its position
`in the tree. A packet is routed along the path deter(cid:173)
`mined by the tree. requiring the packet header to con-
`
`r
`
`_..- - - --.. ...
`
`Radio
`Transceiver
`
`Store & Forna rd
`
`Control
`
`Measurement
`
`I I
`
`'
`Optional Interface~
`
`Tenninal Device
`or
`Station Computer
`
`Figure 1-ThP parktt radio unit
`
`tain a string of appropriate repeater IO's, or labels.
`Thu~. neighboring repeaters hearing the broadcasted
`1>acket but not on the determined path will reject the
`packet rather than relay il. However, this algorithm
`is flexible in that it ullows the repeater to seek an a].
`lcrnate 1·oute for a packet when 11 path !leems to be
`blocked. Moreover, the station with its monitoring
`procedures can dynamically re:ilructure the tree by re.
`labeling any of the repeater!! in response to component
`failures or traffic congestion.
`In order to achieve reliable packet transport, ac(cid:173)
`knowledgment procedure!! are required. There are
`two types of acknowledgments; the end-to-end ac-
`
`Petitioner Emerson's Exhibit 1048
`Page 4 of 10
`
`

`

`:\lea.~uremcnt Pucilitie.~ in 1'11ck(~t Radio Systems
`
`591
`
`knowlcdgmcnl!I ( ~vrli:) between end devices, and bop(cid:173)
`by-hop acknowledgments (HBH) between repeaters.•
`l~xcept for the last hop on a packet's route, HBH ac(cid:173)
`knowledgmcntl! are pm1sive in that the relaying of
`n packet over a hop constitutes an acknowledgment
`of the lrani:;mis.~ion over the previous hop; this ""echo
`acknowledgment" is due to the omni-directional broad(cid:173)
`cast property. Al the last hop, an active II Bii acknowl(cid:173)
`edl('ment must be generated.
`
`M l•:ASUREMENT FACILITI ES
`
`0
`
`Several factors exist in the packet radio svstcm
`which do not allow for a simple transfer of ARPA.NET.
`like meai1urement facilities to 11 packet radio network.
`Althouirh the latter utilizes the same technique of
`packet-switching, the packet radio concept is unique
`in the constraints it places on all system operations and
`the mea~urement effort in parti<·ular.
`The radio broadcast nature of transmissions is such
`that the transmission of mea:mrement data not onl\"
`introduces o'·erhead o,·er its own path. but caus~s
`tram;mission interference at neighboring repealer=(cid:173)
`within hearing distances and creates additional o,·er(cid:173)
`head on those PRU's acti,·ities. Moreo,·er, the desire to
`keep the components small and portable. as well as the
`limited speed of the IMP'~ CPU within the PR Us. place
`significant constraints on the measurement facilities
`and their usage. The :.1,·ailable stor;1ge is extremeh
`limited and the O\"erheud placed on the PRU's CPU i
`s
`of ulmosl importuncc in (•\·alualing the fca:;ibilily of a
`measurement tool and of the collection of data in sup(cid:173)
`pol't of a measurement function. As the operation:1l
`protocols of the net nl'e different from wire nets, the
`mea!lu remcnl functions devised to support the en1lu(cid:173)
`at ion of thei r 1>crformance are unique. Thus, the
`measurement effort consisted of identifying the mea(cid:173)
`surement functions (as described in the fo llowing sec(cid:173)
`tion) nnd devising t he measurement facilities required
`lo 11upport tho;w runctionK unde r the const1·aints that
`the :1y:1tem impose:\, The development of the tool~
`was un ilcrnlivc dc11ign proce!I.~ seeking a balance be(cid:173)
`tween supporting lhc measurement functions and satis(cid:173)
`fying the i>ystcm constraints. as well as making sure
`that the nl!lwork communication protocols allow the
`implementation and proper functioning of those tools.
`ln this section. we describe the various types of
`stnli~ticll de:1ircd in lhc Packet Radio :\let,• the traf(cid:173)
`fic 11ources re<1uired in measurement experiments and
`the techniques a,·ailable for measurement data collec(cid:173)
`\\'e shall postpone until the next section the
`tion.
`detailed list or the quantities that wiU be measured b,·
`each of the types of statistics (tools).
`·
`
`C1111111lat11•• 11tnti11tir11 fC11mJ1tnts)
`
`As il11 name sull'ge~b these consist of data regarding
`a \•nricty of events, accumulated over a gi\"en period
`of tim~, und provided in the form of t1ums, frequencies
`and l11slograms. \\'e 11hall distinguish between those
`data collected nt the PR Us (PRU ba:;ed Cumstats)
`nncl those collected nl the end devices (the end-to-end
`Cum11tats). The PRU l>ased Cum)ltats pro\·ide infor(cid:173)
`mation about the /or(ll enviro11me11l and beha,·ior such
`aK tramc load, channel ncce8!1, routing performance,
`and repcal<'r ndivity. Conversely, end-to-end statis(cid:173)
`tics <·ollc•ctcd al network ~ourccs and sinks that is
`stHtions nnd t.ormirwl devices, will reflect mo~e global
`network behavior such as user delays and network
`t hroughpul.
`
`Tmrr xla/i.~tir11
`
`The trace capability allows one to literally follow
`a pncket through the network, and to trace the route
`which it lakes and the delays which it encounters at
`each ho1>.
`In the ARPA:\ET. selected !MPs gather
`data on packet!'\ to be traced (which ma,· include am·
`packet) and send this data to the colle~tion point a·s
`a 1ww packet. In the packet radio network. however,
`I hr collection of trare data at the repeaters is pro(cid:173)
`hibit<'d br the limited size of storage in the PRU. To
`m·(•rcome lhi:1 llroblcm. we ha\e introduced a new type
`of packet called the Pickup Packet.• These packets
`arc generated with an empty text field b~· traffic gen(cid:173)
`erntors nt end de,·ices. A" these packet11 flow nor mally
`in the network according to the tran:;porl protocols.
`::<elected repeaters will gather the trace ::statistics and
`will store them within the text field of the pickup
`packets themselves.
`
`S11<1p.~/wt sfafi.~ficx
`
`Snapshots give an instantaneous peek al a PHU.
`::showing its ::slate al that moment with regard lo buffer
`assignment and queue lengths. (ln the ARPANET,
`which ii1 a decentralized network in which each node
`contain!\ routing algorithms and data, snapshots also
`include routin11 related information: in the Packet
`Radio Network, such information is available at the
`stat ion). Change·~ lo appropriate :itaUon tables will
`be time 11tnm1>ed and collected a:1 the station's snap(cid:173)
`shot function.
`
`A rt i/irial I raJJii: f/Oleralor.~
`
`• Th•·~· l)JW• ur lth&h"tiC8. R,.; \q•lJ a~ traffic genPrator~. which
`hn\e ht'en wid1•I>· u•~d in \Rl'A!l:~;T mensuremenl ei<Jl"rimcnts
`will difT~r s1gnificuntly from tho.., of the Packet Radio =-:elwork
`in N>gard• to th~ SJK'('iflc qunntittes J(nther~ and the m~ans of
`<Oll<'Cttng lh~m at" rentro.1 l~ntion.
`
`The creation of stre11m~ of packets between given
`points in
`the net, with gi\·cn durations, interrnls.
`
`• Thr ncnlon of thr 11irku11 1mrk1•t wn• tir.t suiorestro hy H.
`Opdc·rb..oek.
`
`Petitioner Emerson's Exhibit 1048
`Page 5 of 10
`
`

`

`592
`
`National Computer Conference, 197G
`
`packet lengths, and packet types ( Information and
`Pickup Packets) is clearly a requirement of any ex(cid:173)
`perimental system. While it might be desirable to
`provide each PRU with the capability of creating such
`traffic, this additional burden on the PRU software can
`be avoided if there exists a reaRonable number of
`terminals with processors attncherl which, along with
`the station, will be prog1·:immed t.o provide the t.1-:1ffic(cid:173)
`source function s indicated above.
`Specifica lly, traffic-source fcatu1·cs which the termi(cid:173)
`nals (and Station) should provide arc: ( 1) I nforma(cid:173)
`tion Packets-
`the user specifies the packet length,
`frequency, destination and duration of one or more
`streams of lnformation Packets.
`(The text content
`may be arbitrary.)
`(2) Pickup Packets-the user
`specifles the llllCkct length , frequency, destinat ion and
`duration of one or more streams of P ickup Packets.
`In the initilll system, there will be a limited number
`of system elements, making it desirable to simulate in
`a terminal a multi-terminal environment. That is, the
`traffic generated at a single terminal will emulate the
`traffic that would be generated b~· several separate
`sources. A great deal of complexity is introduced in
`the de~ign of these devices because of the hardware
`and software capabilities re<1uired lo support this
`function . Feasibility and techniques of achieving this
`is under investigation.
`
`Slc1/ i1111 111£'a111ll'eme11t procc.ss
`
`Since the station is the central node and provides
`central control for the operation of the entire netwoi·k
`it the refore plays n central role in the execution of
`measurement functions. It is th rough the station that
`the initiation and termination of measurement ex(cid:173)
`In particular, the station
`periments is controlled.
`enaules and disables the Cumstat and Pickup packets
`fun ctions al the PRU':;, and assigns to the \·arious
`clements the intervals for Cumstat collections, and to
`the u rtificial traffic generator, their corresponding
`parameters. Moreover. it is to the station that all
`measurement data is ultimately destined; upon arrival
`nt the station, the data is time-stamped and stored in
`a single measurement file for off-line reduction and
`analysis. In addition, all changes to the station's in(cid:173)
`ternal tables (routing, connectivity, PRU operational
`parameters, etc.) will be reflected by an entry into
`the me1111urement file, thus allowing the correlation of
`measurement results to the actual netwoi·k configura(cid:173)
`tion. A (measurement) process at the st.ation will
`perform all of the above functions.
`
`MP<1s111·1·111p11/ d(l/a col/ecfio11
`
`As mentioned earlier, pickup packets are generated
`at stations and terminals. Those packets generated
`at a terminal are destined to (and collected at) the
`station; those generated by the station will be re-
`
`turned by their destinations to the station as 1·egular
`packets for collection into the measurement file.
`Let m; now discuss the techniques for centrall~· col(cid:173)
`lecting cumuh1tive statistics. The data. generated 11t
`the PRU's or terminal devices. must be transmitted
`lo the station using the PR Net it!lclf. One wuy of
`achieving this is to form at the PRU. at the end of
`each Cumslnt intcrvnl, n menourement pocket cnllcd
`the Cumstat packet, which is time-stamped and trans(cid:173)
`mitted to the station. The second method consii<ts of
`having the station send at regular intervals to ap(cid:173)
`propriate PRU's an executable control packet• called
`an Examine packet which collects time stamped Curn(cid:173)
`stat data and which returns back to the station.
`For purposes of analysis, it is desirable for the
`Cumstat data received at the station to correspond lo
`equal length time intervals at the generating device.
`This can be achieved in the automatic method if re(cid:173)
`liable ETE transmission exi.its, i.e., if ETE acknowl(cid:173)
`edgment capabilities are provided in all terminal de(cid:173)
`vices and PRU's, pre\·enting the loss of a Cumstat
`packet from it device on its way to the station. In
`the <1bsence of the ETE capabi lity i11 lhe PRU':;, one
`may decrease the Cumstat intervals (thus increasing
`the frequency of transmitting Cumstat dala), lhereby
`decreasing the ga)ls between conectly receh•ed Cum(cid:173)
`stat packets. With the Examine method, variable
`length Cumstat intervals will occur since Examine
`packets, sent at regular intervals from the station, are
`subject to (i) the net.work random delayll en route
`t.o the destination PRU, and (ii) the possibility of los;;
`in either direction.
`The choice of a collection method will have to take
`into consideration the overhead that il imposes on
`the PRU;; and on the network.
`
`MEASUREMENT FUNCTIONS
`
`We have described in the previous section the mea(cid:173)
`surement facilities that are desirable in <1 PRNET to
`suppoi·t the measurement functions. ln this section
`we shall identify and discuss these functions in ;;ome
`detail, determine the required data items and describe
`the role of these measurement facilities in supplying
`the data. These include: channel access, operational
`protocols, repealer performance, traffic characteris(cid:173)
`t ic:<. and the network's global performance.
`
`Chamiel access
`
`One of the main features that distinguish the Packet
`Radio Network from poi nl-Lo-poinl networks is that
`
`• An executable control packet is n packet thnt originates at the
`station and is destined to a l'Rll. It contains code to b.. executed
`hy th~ d<'stinntion P l{U. Jn particular, the f:xamine packet
`c.:Ortlaii•s lhC! necessary co<le to loud the contcnt.s of specified
`memory locations into the text of the packet to1· shipment back
`to the station.
`
`Petitioner Emerson's Exhibit 1048
`Page 6 of 10
`
`

`

`:\leasurement Facilitie:s in Packet Radio Systems
`
`593
`
`devices transmit packets over a broadcast channel by
`using a random access scheme. These random acce~s
`i;chemcs are characterized by the sharing of a single
`channel in a multi-access fashion, thus allowing for
`pncket interference to occur. Considerable progress
`has been made in analyzing these access modes, which
`include pure and slotted ALOHA and the more recently
`developed tec hniques of Carrier Sense Multiple Acces!I
`(CSMA) ."·" " Jn the initial experimental system pure
`ALOHA, 1-persistent CSMA and non-persistent CSMA
`will be a\·ailable. Our meas urement aims are to vali(cid:173)
`date the a nalytical models of the three access modes
`and to evaluate their perfo1·mance in realistic environ(cid:173)
`ments.
`In ernluating terminal access in a single hop system
`(a model commonly used in analysis), we consider an
`environment consisting of a s ingle station and a popu(cid:173)
`lation of terminals within range and in line-of-sight
`of the station. In order to dete rmine the relat ionships
`between the network throughput (rate of successfully
`received packets at the station} and channel traffic
`(rate of packet transmissions over the channel), a~
`well as t he relationship,; between the network through(cid:173)
`put and packet delays, the following quantities will
`be measured :
`(a} the number of transmissions a packet incur;;
`before success
`time elapsed since
`(b) t he one-hop packet delay:
`the packet is ready for transmission until it is ac(cid:173)
`knowledged, i.e., until its acknowledgment packet is
`received from the station
`(c) network th roughput: average number of pack(cid:173)
`ets received a t the station per unit time
`
`Items (a) and (b) are obtained in the fo rm of
`histograms by the Cumstat tools at the PRU and the
`end device respectively.
`rtem (b} may also be ob(cid:173)
`tained individually for each Pickup packet by having
`the originating device store in it its time of generation
`and its transmission times, and in the succeeding
`Pickup packet, store the time its acknowledgment ar(cid:173)
`rived. Item (c) is obtained at the station from end-to(cid:173)
`end cumulative statistics.
`The task of measuring performance of terminal ac(cid:173)
`ces." techniques in mul ti-repea ter environments cliffern
`from the previous one in t hat r epeater-to-repeater
`traffic is present contending on the same channel. The
`environment consists of a num ber of r epeaters and
`stations and a population of terminals, not necessaril y
`all within range and in line-of-sight. The same quan(cid:173)
`tities 11:1 li,;ted above, measured over the terminal-to(cid:173)
`repeater hop, will he collected using the same tools.
`
`0111•1·a/innt1/ prnlncnls
`
`Ackno..,· h~d;::men l prolotol•
`
`Echo ;1cknowledgmenl suffe1·s from packet inter(cid:173)
`ference. The delay unlil the echo acknowledgment is
`
`the
`received al the tran ~mi tter is random. Thus,
`packet may incur some additional transmissions be(cid:173)
`yond lhe first succei<sful one creating additional over(cid:173)
`head on the channel and in the PRUs. This number
`of additional t ransmissions is a measure of the in(cid:173)
`eflk .• mcy of echo <1cknowledgments; so too will be the
`numbe1· of packets dii;car ded at the transmitter be(cid:173)
`cause of lack of reception of the eeho acknowledg(cid:173)
`ment. That is, lhe transmitter reached the maximum
`number of retransmissions of a packet before the echo
`acknowledgment was received : although the packet
`may have been successful,
`the transmi tter declares
`itself unsuccessful in establishing communication!
`Thus, we shall measu1·e the efficiency of the Echo
`Acknowledgment protocol by meas uring the number of
`addilional lransm i~sions beyond success incurred by a
`1mckct. To compute this number, a PRU must have
`two pieces of information; it must know how many
`t imes t he packet has been transmitted, and it must
`also know which of those retransmissions was the one
`that 1·eached the next repeater successfully. Thi!I in(cid:173)
`forma tion will be contained in two fields in each packet
`header, which we refer to here as fields A and B. Field
`Bill used by the PRU to store the current tram>mission
`number of the packet. When the packet is successfully
`heard by the intended receh·er , t he contents of field B
`are saved by being stor ed into field A; when the Echo
`acknowledgment is successfully heard by the sending
`PRU. field A of the echo acknowledgment is compared
`with the cunent number of transmissions of the
`packet, i.e., the contents of field B in the sender's copy
`of the packet. If these two numbers differ, then the
`magnitude of that difference represents the number
`of times that the packet was retransmitted after it had
`already been successfully received at the next hop.
`This data is collected as part of the cumulative sta(cid:173)
`tistics of the sending PRU.
`
`Rouling protocols
`
`lhe hierarchical routing
`introduced
`Earlier we
`scheme in use, which is ba:;ed on a tree structure wi th
`the station as its root. The initial tree structure is
`cr eated dynamically by the Initialization Procedure
`in which the station uses PRU connecti\'ity informa(cid:173)
`tion to create a tree that minimizes the number of
`hops between each repeater and the station. Thus the
`muting strategy initially performs shortest path (min(cid:173)
`imum hop} routing from repeaters
`to station and
`from station to repeaters. H owever, when t he first
`choice shortest path cannot be used, the packet departs
`from this path and use;; a shorte11t 1~ath from its new
`location. This will occur when a repeater has trans(cid:173)
`mitted a packet O\'Cr a hop the maximum number of
`limes allowed without receiving an HBH acknowledg(cid:173)
`ment; t he repea ter then alters the packet's header (to
`what is called the "ALL" label} so that any repeater
`
`Petitioner Emerson's Exhibit 1048
`Page 7 of 10
`
`

`

`594
`
`National Compult•r Conference, 1!)76
`
`within hearing di!:ltance and able to relay the packet
`in its intended direction will do so. This packet iq
`then said to be alternately routed. It is retransmitted
`with it;; ·'ALL" header until either an HBH acknowl(cid:173)
`edgment is recei,•ed or the maximum number of re(cid:173)
`transmissions is once :1gain reached, at which time
`the packet is discarded.
`The analysis of a routing algorithm, particularly in
`a broadcast, anrl thus mobile, network, is a complex
`taRk, in that routing is to1>ology. and load-dependent,
`anrl involves, with varying deg1·ees of subtlety, all of
`the system's protocolR. Thus, routing consideration~
`are really a synthe!lill of mo11t element!'! of lhe llystem
`design, and as Ruch, tht• meallurement oC the algorithm
`im•olves at time$ the i<tudy of the interaction of the
`many system protOl·ols.
`Given the patterns of input load on the network. the
`distribution of trnflir flow in the net is an indication of
`the behavior and efficiency of the routing and initiali(cid:173)
`zation algorithms. One may detect the concentrallon
`of traffic 011 specific routell crenting congestion while
`alternate routes are not assigned: thus smaller delay
`routes may have been ignored in favor of the shorter
`routes pro\"ided by the initinliznlion procedure.
`To obtain the diHtribution of lrnffic flow. the follow(cid:173)
`ing quanlitiell :ire to be mea~ured.
`
`(a) the total number of packets received and trans(cid:173)
`mitted at each repenter (obtained in the PRU Cum(cid:173)
`,;talq)
`(b) the fraction of time the transcei\·er is busy
`(obtained h~· snapshot statistic;1, or in the PRU Cum(cid:173)
`stat by regular ~amplinic of the transceh·er's state)
`
`the point-to-point nature of this routing
`Also.
`algorithm, restricting a packet at a given hop to a
`sinicle repeater as its immediate destination, doe!\ not
`take advantage of the broadcast nature of the channel.
`in which several neighbors may actually hear th<'
`transmission and be capable of relaying the packet.
`Thus the following quantity is relevant:
`
`(c) the number of packets correctly received and
`discnrdcd because they are destined to other com(cid:173)
`ponent,; in the net (obtained in the PRU Cumstat).
`
`.Moreover, to measure the potential of each neigh(cid:173)
`boring repeater (:<ay, repeater "n") as an immediate
`destination, it is essential to know the probability of
`succe!ls P(n) repeater n has to correctly receive a
`broadcast packet. This we do by maintaining in each
`PRU a table counting the number of successfully re(cid:173)
`ceived packets from each immediate neighbor. The
`ratio of the number of pncket!I correclly received from
`a given neighbor, to the number of packets transmitted
`by that neighbor, is a meaMure of P(n).
`Another important feature of a routing algorithm
`is its adaptability lo network changes: input traflir
`load. connecti\"ity and component failure and repair.
`In e,·aluating the dynamics of such an algorithm, three
`
`factors must be examined: lhe lime required to detect
`the network change, the time required to respond, and
`the quality of the response. The data items at each
`PRU necessary for these studies, which include some
`of those mentioned earlier, are:
`
`(a) tables counting the number of packets correctly
`receh•ed from immediate neighbors
`(b) number of packets alternately routed
`(c) number of packets discarded, suggesting route
`congestion or component failure
`(cl) percent of time repeater iK busy lr:lnsmitling
`and receiving
`
`These are obtained as cumulath·e statistics in the PRU.
`In addition, the Pickup packet is a valuable tool in
`routing studies in that it contains the actual and com(cid:173)
`plete route taken by the 1>ackel (pinpointing alternate
`routing), as well as time stamps to compute the queue(cid:173)
`ing and transmission delay!! incurred at each repe."lter.
`
`Repeate1-'s perfon11a11cr
`
`The evaluation of the performance of a repeater is
`most important in the 111wlyaiii of network behavior:
`it allows us to break down key network measures
`(!ntCh as packet delay and through1mt) into their ele(cid:173)
`mentary comµonents and lo examine the effect;; on
`these measures of the repealer activity and design
`(including buffer management, queueing discipline,
`ond packet processing priorities).
`The quantities relevant to 1>11cket delays are:
`
`(a) The proce.~sing time of a packet flowing through
`a re1>e1lter; this is counted in Pickup Packets as the
`lime lapse between the packet's arrival and the time
`it i;; placed on the transmi:1sio11 queue. This process(cid:173)
`ing includes various che<'kK such ns checksum, packet
`type, routing labels. etc.
`(b) the packet queueinlC delay at a repealer; this is
`also counted in Pickup Packets as the time elapsed
`from when the packet is placed on the transmission
`queue until it is considered for transmission (i.e.,
`until it is at the head of the line, in n first-eome-first(cid:173)
`ser\"ed discipline).
`(c) the packet's service time; this is also counted in
`Pickup packets as the time elapsed from when the
`packet is at the head of lhe queue until its echo-ac(cid:173)
`knowledgement is correctly received. Note that the
`actual service time (lime until the packet is correctly
`received at the next repenter) is smaller than the one
`measured here due to the echo acknowledgment pro(cid:173)
`tocol used in this system. Note also that the service
`time~ of consecutive 1