dwight@timeinc.UUCP (Dwight Ernest) (07/31/85)
[ Note: This series of articles was found on Compuserve and downloaded from HAMNET there on 21 July 1985 by Dwight Ernest KA2CNN 70210,523. ] An Introduction to networks by T.C. McDermott, N5EG networks SIG, TPRS [ part 1 ] This article is an introduction to the subject of a packet network. It describes what a network is, why a network is necessary to support amateur packet radio activity, and considerations that govern how a network may be constructed. There are many ways that a network can be designed, and it is beyond the scope of this article to elucidate them all. Rather, this article will focus on the simplifing assumptions that may be made in describing a network, and more specifically will concentrate on some suggestions for the Texas Packet Radio Society network which is called "TEXNET". Most of us are familiar with packet radio activity through our operations with the TAPR TNC board. This board implements what is called a "Local Area Network", or LAN for short. When we wish to communicate, we ask our TNC to CONNECT to another station. If that station is not within range of our transmitter, then we may connect to that station through a digi-peater, or through several digipeaters. This is a convienent extension of the X.25 protocol, and forms a large part of the difference between X.25 and the amateur version called AX.25. It would be possible to construct a network of stations that are all within range of the next station, and then to connect to any station in the network using this digipeat method, up to 8 stations distant. This would not require the extension of any of the TAPR software, nor would it require the development of any new hardware. Why then is this not an acceptable method to construct a network? Basically this method, although simple to implement has a serious flaw, it lacks "robustness". That is, the method fails to support adequate communications in the presence of a radio path that is not perfect. Secondly, it assures communications integrity through a method known as "end- to-end ACK". To understand this, it is necessary to understand how a TAPR digipeater works. The TAPR digipeater is a "dumb" digipeater. That is - the digipeater does not understand anything about the state of the two stations that are trying to communicate to each other through it. When one station wishes to connect to another station through a digipeater, it simply adds the digipeater's address in series with the address field of each and every packet. When the digipeater recognizes it's callsign, it repeats the packet. The digipeater does not know what kind of packet is being digipeated, and does not really care. The packet could be a call-request packet, or user-data, or an acknowledge packet, it really doesn't matter, it digipeats them all, blindly. Why is this important? Because it affects how the transmission and acknowledgment of data is handled between the two end stations trying to communicate with each other. When the sender, S, tries to send data to the receiver, R, through one or more intervening digipeaters, D1, D2, ... , Dn, it does this as follows: S : sends a packet D1: digipeats packet D2: digipeats packet R : receives packet, R : sends acknowledge back D2: digipeats acknowledge D1: digipeats acknowledge S : receives acknowledge, S : sends next packet. Although there can be several packets sent per acknowledge, it requires that a packet, and the acknowledge (ACK) make the round-trip from the sender to the receiver. Thus, the more digipeaters, the longer the round-trip time, and the lower the packet throughput. The above example assumed that there were no errors in the transmission. What happens if one of the packets and one of the acknowldeges is corrupted during transmission? S : sends packet D1: digipeats packet D2: doesn't hear packet from D1, so doesn't do anything S : still waiting for ACK from the receiver S : still waiting for ACK from the receiver S : still waiting for ACK from the receiver S : still waiting for ACK from the receiver S : still waiting for ACK from the receiver S : times out waiting for ACK, and re-transmits packet D1: digipeats the packet D2: digipeats the packet R : receives the packet, R : sends ACK back to sender D2: digipeats the ACK D1: doesn't hear packet from D2, so doesn't do anything S : still waiting for ACK from the receiver S : times out waiting for ACK, and re-transmits packet D1: digipeats the packet D2: digipeats the packet R : receives the packet, but it's a duplicate - throw away R : sends ACK back to sender D2: digipeats the ACK D1: digipeats the ACK S : receives the ACK, S : sends the next packet How long did this take? About 25 packet times. The situation gets worse when 8 digipeaters are chained together. In fact with 8 digipeaters the round-trip time reduces the channel throughput by a factor of approximately 16 (8 hops to R, and 8 hops for the acknowledge to come back) if there are no channel errors. If the probability that any single transmission is corrupted is about 70 percent, then with 8 hops the average round trip will take about 1000 packet times. In other words, nothing will get through. Why is the TAPR TNC built this way you might ask? For a very good reason - simplicity. To build a digipeater that behaves in a more coordinated fashion turns out to be a very complicated problem. The TAPR digipeater extension is far superior to the other alternative - no digipeater at all. The TAPR digipeater is elegantly simple, and a reliable way to improve the communications between two stations that are reasonably close, but not able to communicate directly. We have seen that one or two digipeaters may not degrade the throughput terribly, provided that the RF paths are highly reliable. Thus the digipeater solution may be called an LAN solution. That is, it is an acceptable network for small numbers of digipeaters, and high-quality circuits. A single digipeater in a superior location allows many stations within the coverage area of the digipeater to communicate. But the digipeater is not an acceptable solution when the need is to communicate over long distances, and with less than high-quality communications circuits. Thus is born the requirement for a NETWORK. This will be discussed in the next article of this series. -- ----------------------------------------------------------------------------- --Dwight Ernest KA2CNN \ Usenet:...vax135!timeinc!dwight Time Inc. Edit./Prod. Tech. Grp., New York City Voice: (212) 554-5061 \ Compuserve: 70210,523 Telemail: DERNEST/TIMECOMDIV/TIMEINC \ MCI: DERNEST "The opinions expressed above are those of the writer and do not necessarily reflect the opinions of Time Incorporated." -----------------------------------------------------------------------------
dwight@timeinc.UUCP (Dwight Ernest) (07/31/85)
[ Note: This series of articles was found on Compuserve and downloaded
from HAMNET there on 21 July 1985 by Dwight Ernest KA2CNN 70210,523. ]
An Introduction to Networks
part 2
by T.C. McDermott, N5EG
networks SIG, TPRS
In the last article the distinction between a LAN and long- haul
network was made. Also the performance problems associated with
unreliable radio circuits and the End-to-end ACK was discussed. This
article will present some other methods of information transfer
possible.
Another method of information transfer possible is "HOP-TO- HOP"
acknowledge. In this method, each packet, or small group of packets, is
acknowledged by every receiving station along the path from the sender
to the receiver. For example, using the same terminology as the last
article, S=sender, R=receiver, D1,D2, ... Dn = digipeaters.
S : send packet
D1 : ACK to S, repeat frame
D2 : ACK to D1, repeat frame
R : ACK to D2.
Why does this method improve the throughput of the system ? Because
now that the sender, S does not have to wait for the ACK to return from
R, S may send another packet after the ACK from D1. That is, it may
OVERLAP traffic.
S : send packet 1
D1 : ACK S-1, repeat 1
D2 : ACK D1-1, repeat 1 S : send packet 2
R : ACK D2-1 D1 : ACK S-2, repeat 2
D2 : ACK D1-2, repeat 2
R : ACK D2-2
In other words, once that S has received it's acknowledge, it may
transmit the next packet almost immediately (if D1 is on the same
channel, it should wait for the D2 --> D1 ack first, if the D2 --> D1
link is on a different frequency [as in a network] then S could transmit
the next packet immediately upon receiving the D1 ACK). What happens to
the flow of information in the presence of errors in the transmission ?
Lets look at an example:
S : send packet
D1 : ACK S, repeat packet
D2 : gets garbled packet from D1
D1 : waiting for ACK from D2
D1 : retransmits packet to D2 after time-out
D2 : ACK D1, repeat packet
R : ACK D2
In article one, with this same exact scenaro, it took 25 packet
times to accomplish the transfer of one packet from S to R through 2
digipeaters. In this example it took 6 packet times, a 417 %
performance improvement in the transmission time. This performance
improvement actually increases with more digipeaters, or worse RF paths.
In fact with 8 digipeaters, and a 70 % probability of a sucessful
packet-hop, this approach offers about a 10,000 % performance advantage
!
Additional to the transit time advantage (time delay per packet in
seconds-from-S-to-R), there is the advantage in throughput (bytes/sec.).
The throughput in the HOP-TO-HOP ack method is NOT dependent upon the
number of digipeaters. This is because as soon as the first digipeater
has acknowledged the reception of the senders' packet, the sender is
free to send the next packet, regardless of the number of hops in the
path. Contrast this to the end-to-end hop method, where the throughput
is very dramatically dependent upon the number of hops in the path.
What is required of the digipeaters in the network to handle this
type of repeating function, i.e. HOP-TO-HOP digipeating? Each
repeating station is required to contain a fair amount of memory, enough
to buffer every packet that it digipeats until that packet is
acknowledged by the next repeater. Since the repeater may receive
packets from several different stations at nearly the same time, and
perhaps some of them are occaisonally garbled in transmission to the
next repeater, then they must be stored in repeater memory until they
are sucessfully passed to the next repeater.
The repeaters must also implement some sort of flow control. If
packets arrive faster than they can be sent, then the buffer memory
could overflow. Thus the repeater must be able to tell the previous
repeater, or sender, that the packet is rejected, and to stop sending.
When the repeater clears the messages, and thus frees up some memory,
then it re-initiates packet transfer from the previous station. This
finite memory size limitation actually causes the end-to-end performance
of the network to become more heavily dependent upon the quality of the
RF links. Thus performance of the HOP-TO-HOP system is dependent upon
the probability of RF path-hop success, but is not heavily dependent
upon the number of repeaters in the path, unlike the END-TO-END scheme.
This was taken into account when I stated that the performance of the
HOP-TO-HOP ack with 8 digipeaters, and 70% path-hop probability of
success was about 10000% better than the END-TO-END method.
There is one intetersting dis-advantage to the HOP-TO-HOP scheme,
although it is not a strong disadvantage, and that is the issue of data
integrity. In the END-TO-END ack ( EEA ) scheme when the receiver
acquired the data, the ACK was sent. Thus when the sender receives the
ACK, there is certainty that the data was in fact received. In the
HOP-TO-HOP ack ( HHA ) all that is known when the sender receives the
ack, is that the first digipeater received the ack. A failure in the
network could still block the receiver from receiving the data - thus
the sender was ACK'ed even though the receiver had not received the
data. This is not as serious a problem as it sounds at first, however,
since there is still a method to determine whether the data is received
at the final destination correctly.
This is handled by layer 4 of the OSI model - the transport layer.
It is responsible for data integrity in the real world of unreliable
networks. One protocol for doing this is familiar to those of us with
AX.25 units, and this is the Virtual Circuit protocol. Each of us is
intimately familiar with virtual circuits. Any time that you connect to
another station, you have generated a virtual circuit. You and the
receiver communicate on a common channel with everybody else. But your
traffic only goes to your desired destination, not all destinations on
the channel. Thus there is a circuit between you and the connected
receiver on a channel with a (theoretically) unlimited number of
circuits. This is called a virtual circuit. The only reason there is a
circuit is because you and the connected receiver previously agreed to a
connection. The circuit is dissolved when you and the receiver agree to
this (disconnect). The next article in this series will deal with the
virtual circuit protocol on the network, as opposed to the virtual
circuit between the sender and the network, or between the receiver and
the network, which is something different.
--
-----------------------------------------------------------------------------
--Dwight Ernest KA2CNN \ Usenet:...vax135!timeinc!dwight
Time Inc. Edit./Prod. Tech. Grp., New York City
Voice: (212) 554-5061 \ Compuserve: 70210,523
Telemail: DERNEST/TIMECOMDIV/TIMEINC \ MCI: DERNEST
"The opinions expressed above are those of the writer and do not necessarily
reflect the opinions of Time Incorporated."
-----------------------------------------------------------------------------
dwight@timeinc.UUCP (Dwight Ernest) (07/31/85)
[ Note: This series of articles was found on Compuserve and downloaded from HAMNET there on 21 July 1985 by Dwight Ernest KA2CNN 70210,523. ] An Introduction to Networks part 3 by T.C. McDermott, N5EG networks SIG, TPRS The last article discussed End-to-end Vs. Hop-to-hop methods of acknowledge, and the attendant advantages of each. As you may recall, one of the disadvantages of the HHA was the possibility of a network failure still allowing the sender to have been acked for data that may not, in fact, have been received. Generally, this is not a problem. If communications fails along a path we naturally tend to want a re-transmission of the entire contents of whatever file we may have been sending. If we happened to be in the keyboard mode, then since the communications fialed, we cannot continue to send anyway. Thridly, our TNC's do not tell us how much data they have in their transmit buffers that has not been acknowledged, so the HHA network really doesn't differ from the types of responses that we are used to from the TNC - LAN system. If we must guarantee the absolute integrity of a file transfer, then we should implement some type of block numbering and sequencing program that controls the file transfer process. In essence, something like the MODEM7 protocol tacked on top of our existing TNC protocol would guarantee the complete integrity of files transfered. We would probably want to add onto the MODEM7 system a little bit, perhaps to record what was and was not sucessfully transfered, and perhaps a method of automatically re-establishing the connection to the other station, and continuing with the transfer process until it is sucessfully completed, and then tearing down the connection. This additional program that we would run on each of our end-user computers (both sender and receiver) is the LAYER 4 of the OSI model - the transport layer. Since the network we are talking about constructing is thus releived of absolute ACK integrity by the presence of this additional program (in those rare instances where it is really needed) then our netork is only restricted to providing a reasonable guarantee of integrity, perhaps guaranteeing that packets arrive in the correct sequence, and without bit errors. Thus with an emphasis on the HHA VS. the EEA methods, we have decided to build a network that optimizes throughput and response, allowing for a layer 4 program in the event it is needed, but not sacrificing the performance of the network for the vast majority of the uses of the network. This trade-off is usually described as a speed-integrity tradeoff in the literature. Now that a decision has been reached on the desired attributes of the network, that is speed, and simplicity, we may concentrate on one final interface aspect, and that is how the LAN (i.e. the TAPR TNC's) are to interface and establish connection through the network. This linkage is the peer communication between two layer 3 processes that is described by Tannenbaum [1]. In the 7-layer OSI model, subnet communication (that is communication through a network) is established between two layer 3 processes - that is, the TAPR TNC AX.25 mode, and the network entrance and exit layers. Although AX.25 is sometimes discussed as a layer 2 protocol, in the LAN application it is really a layer 3 process. It establishes, communicates, and terminates, and thus it is a layer 3 process. Similarly the network, upon command, will establish, communicate, and terminate, thus it also is performing a layer 3 function. Why the concern about which layers to call each other? Because it is desirable that the TNC's be able to use the network without any modification. Thus the network must be compatible to the way that the TNC establishes, maintains, and terminates connections, since the network must establish, maintain, and terminate connections to or from TNC's and itself. We are faced with the choices as to how the TNC and the network can talk with one another. One method of network interface is to assume that the network is transparent, that is it looks like a digipeater. Then you would use your TNC as though the network were a single digipeater (even though it might have many hops, it would appear to the TNC as one digipeater). Another method is to treat the network as a spearate LAN address. This is, you would connect to the network. Then the network would engage in an interactive session with you regarding the type of service that you needed, that is, who you wanted to talk to, and how to get through the network to that place. Once the network computer was satisfied, it would then engage in comunications between the endpoints. Your TNC would think it was connected to the network, not to your actual destination station. Each of these connection methods has advantages and disadvantages. We will discuss some of them here. The digipeater-emulation method is a very natural method to use, because the connection method is familiar to all of the TNC users. Let us establish the following scenario: WD0ETZ in Carrollton wishes to communicate with WD5GAZ in Houston. WD0ETZ knows that this distance will require the use of the network. So WD0ETZ proceeds as follows... Connect WD5GAZ VIA DALLAS This seems simple enough, but some interesting problems crop up almost immediately. How does the network know where to find WD5GAZ? What path is required to get there? WD0ETZ's TNC is going to want to see ACK's from WD5GAZ, not from DALLAS. First problems first. One way for the network to know how to find WD5GAZ is for it to keep tables in all of the sites of each and every network user. This is really not practical in an amateur environment because hams move, come, and go, and even change callsigns, and with very many users, it takes a lot of manual intervention to keep the tables current. It also takes a lot of computer power in the network to store and route messages based upon these tables. In the event of a network crash, the tables would have to be reloaded, etc. A simpler way would be for the originator, in this case WD0ETZ, to specify the network "hop-off" point, that is, the location in the network where WD5GAZ is likely to be found. For example: Connect WD5GAZ VIA DALLAS,HOUSTON Now the network knows that the entry point is this network (which is "DALLAS", the one hearing WD0ETZ) and the exit point is HOUSTON. Perhaps different types of names would be chosen for network nodes. Grid-squares and major city names seem to be two obvious choices. What about the route to take to get along the network? There is an incomplete but simple answer to this question - make a linear network (or a simple variant of linear). A linear network is one where the network is basically a straight line. Thus there is by definition only one path between any two points. A few other questions. What if WD5GAZ is not within range of the HOUSTON node, but perhaps within range of a station that is near to the node - for example suppose that WA5AAA is between the HOUSTON node and WD5GAZ. Then... Connect WD5GAZ VIA DALLAS,HOUSTON,WA5AAA What if WD0ETZ is not within range of the DALLAS node, but is within range of WB5QNG, who is within range of DALLAS ? Connect WD5GAZ VIA WB5QNG,DALLAS,HOUSTON,WA5AAA Well, the addressing would work. But the network entry point has to do some strange things to the address field. Remember in the HHA scheme it would be the address DALLAS that is actually ACKing WD0ETZ, and not WD5GAZ that would be ACKing WD0ETZ, so the network node has to play "fast-and-loose" with the address headers in the digipeat field. The other method is fairly straight forward. The user connects to the network, and then enters an interactive Q & A session: Connect DALLAS Welcome to TEXNET - DALLAS node. There are currently 4 other users connected to DALLAS. Enter destination callsign ? ( WD5GAZ would be entered here) Enter network exit node ? ( HOUSTON would be entered) Enter destination digipeaters ? (WA5AAA would be entered) CONNECTION ESTABLISHED - PROCEED Notice one thing in the above scenario: more than one station may be connected to the network node entry and exit points. This is something that is a little foreign to the AX.25 protocol, that is MULTIPLE VIRTUAL CHANNELS to a single TNC. In this case it is still compatible with AX.25 since both source and destinations callsigns are part of the AX.25 standard. Only the network nodes have to have this special property of having to be connected to several different stations simultaneously - thus the AX.25 code for these controllers is a little different from a normal implementation. But only the network requires these special TNC's (actually they are built into the node controller, and aren't identifable as a separate device). The reason that the network should allow for multiple virtual channels is to allow multiple people to simultaneously use the network. Since we will put high-speed radios in the network between nodes, we should take advantage of the bandwidth available. At this point we will not go into the network protocol required to implement these connection schemes, that "play-games" with the address header fields to keep our TNC's happy, and that perform the HHA transfer between the network nodes, do flow control inside the network, and route the signal to the destination. That is the subject of another article. The next article will deal with the type of hardware that will be required to support this concept of a network, and it turns out to be surprisingly modest. There are some other concerns about capacity, response time, channel utilization, reliability, and remote network "resuscitation" (in the event of software failure) that will also be addressed in part 4 of this series. -- ----------------------------------------------------------------------------- --Dwight Ernest KA2CNN \ Usenet:...vax135!timeinc!dwight Time Inc. Edit./Prod. Tech. Grp., New York City Voice: (212) 554-5061 \ Compuserve: 70210,523 Telemail: DERNEST/TIMECOMDIV/TIMEINC \ MCI: DERNEST "The opinions expressed above are those of the writer and do not necessarily reflect the opinions of Time Incorporated." -----------------------------------------------------------------------------
dwight@timeinc.UUCP (Dwight Ernest) (07/31/85)
[ Note: This series of articles was found on Compuserve and downloaded from HAMNET there on 21 July 1985 by Dwight Ernest KA2CNN 70210,523. ] An Introduction to Networks part 4 by T.C. McDermott, N5EG networks SIG, TPRS This article describes some requirements for network node hardware. One of the key concepts is the idea of modular implementation - to allow for changes in the way a network is designed. The network that has been evolving from the description in the 3 previous articles can be implemented in a backbone type of network. In this network there are two channels that are accesible at any node, the high-speed inter-node communication channel, and the 2-meter AX.25 channel. Thus the description of the hardware assumes that there are two synchronous channels per node. Each node has the capability to move traffic along between nodes (all on the high-speed channel) and also to drop and add traffic to the high-speed channel from the low-speed channel. One of the first assumptions is that the high-speed channel will operate at 9600 bits-per-sec (b/s). For a number of reasons (the formost of which is availability) the K9NG type of FSK modem on the 220 Mhz. band will be utilized. There are some performance advantages to be obtained with PSK, but the slow carrier-recovery loops that are normally used are not always compatible with the fast T/R-switching times needed in packet service. The low-speed channel will compatible with AX.25 TNC's, and thus is a 1200 b/s channel on the two meter band. We have thus partitioned the node into three major elements: 1. High-speed channel hardware. This includes 220 MHZ. radio, antennas, power splitter, 9600 b/s FSK modem (K9NG). 2. Low-speed channel hardware. This includes 2-M radio, antenna, and 1200 b/s AFSK modem. 3. Node-control computer. This includes 2 synchronous interfaces, T/R control circuits, RAM, ROM, and fail-safe sequence decoder. A simplification of the high-speed radio circuitry is to have only one 220 Mhz. transmitter and one 220 Mhz. receiver per node. Two high-gain directional antennas are used, with a 3-dB. power splitter near the antennas. Thus communications with the northerly- and southerly- nodes is possible with one radio. Extension of this concept to three or four nodes is possible but the RF losses start to get high. The design of the high-speed portion (the backbone) allows access to the node only by other nodes. This is done to eliminate direct channel contention between users and the inter-node communication. The users of the network do not, and indeed CANNOT communicate with it on 220 Mhz. The protocol on 220 Mhz. (in this implementation) is TEXNET-IP, which IS NOT compatible with AX.25 (and indeed, for the reasons expressed in parts 1-3, should not be compatible with AX.25). The 2-Meter section can use a commercially-available FM radio, and AFSK modem design. Each of the radio sections contains logic-level interfaces to the node control unit. This is done to facilitate the changeout of the node control processor should a new design or network protocol standard become available. It is anticipated that resolution of the various trade-offs involved in the implementation of a network will take several years to occur. In order to solve a pressing need within TPRS, the need for long- haul communication, we will go ahead and implement TEXNET with an eye towards changes and evolving standards. The node control computer consists of a Z80-SIO chip (which has two synchronous HDLC-type serial channels), a Z80 (4 Mhz.) microprocessor, 16K of ROM, 32K or RAM, some timer circuitry to develop the 1200-hz, 9600-hz, and 1200 x 32 = 38400 hz. clocks. The node also has two time-out timers to prevent transmitter lock-up on the 2-m and 220 Mhz. units, contains NRZ/NRZI coder, decoder, and clock-recovery circuits for the 1200 b/s channel. It also contains a special state machine that listens to the 220 Mhz. channel and clock. This circuit recognizes a special sequence (that obeys the HDLC coding rules) and interprets the reception of this sequence as a over-riding command that uses hardware to re-boot the node processor. Each node contains a unique code in its state machine. The code is chosen to be sufficiently long that the mean time to false is 6*10^7 years (assuming random data). A custom circuit board will be constructed to contain this controller. It may have been possible to modify one of the Xerox-820 boards, but it was felt that the changes required would reduce the reliability of the resultant assembly too much. The parts cost of byte-wide RAMs and ROMs has dropped recently, and these devices will should allow construction of the entire controller for slightly less than the price of just the 820 board when purchased surplus. The controller will be constructed mostly of CMOS circuitry, and will be powered at +5 V through a series regulator powered from +12 VDC. This will allow a single +12 V supply. The node will contain a gel-cel battery and a charger circuit. Thus the entire node will have something approaching un-interruptable power, while still having an acceptable power supply cost. The node controller card will be connecterized at the logic- level interfaces to the radio circuits. In the event a new controller design emerges, then upgrading of the node can be as simple as replacing the card. One of the objectives of this network design is to keep the cost of any node low. Our goal was $500.00. We anticipate that those groups who wish to joint TEXNET will assemble, place, and maintain their node, with the assitance of TPRS. We thus would release the design of the node to those groups, and perhaps sell or supply the circuit boards needed, as well as the software for the controller. In our design, each node will have the same software, except for routing tables. A first crack at the routing problem can be attempted with static routing tables, whcih will be in ROM, and different at every site. The subjects of routing, and other network topics will be discussed in part 5 of this series. -- ----------------------------------------------------------------------------- --Dwight Ernest KA2CNN \ Usenet:...vax135!timeinc!dwight Time Inc. Edit./Prod. Tech. Grp., New York City Voice: (212) 554-5061 \ Compuserve: 70210,523 Telemail: DERNEST/TIMECOMDIV/TIMEINC \ MCI: DERNEST "The opinions expressed above are those of the writer and do not necessarily reflect the opinions of Time Incorporated." -----------------------------------------------------------------------------