* Fido/FidoNet Routing, Topology, History, and Recent Changes
Tom Jennings, 1:125/111
15 June 89
Fido/FidoNet, like all other FidoNet mailers and BBSs, generatesچ
messages, and puts them into packets that are later delivered toچ
some appropriate destination by the mailer itself. All of theچ
different mailers use different approaches as to just how you theچ
sysop control where, how and when packets (and the messages theyچ
contain) get delivered.
In light of all the mailer systems out there today, I don't thinkچ
many are aware of just how Fido/FidoNet does it's routing. With aچ
few recent changes you might find the design has becomeچ
interesting once again. (And starting July 89, Fido/FidoNet is
once again shareware. File Request "ABOUT" and "FILES" from
1:125/111 for complete details.)
FIDO
Fido was originally just a bulletin board; the first FidoNet wasچ
a separate program that was run from a batch file with a fewچ
small hooks into the BBS. (The origin of the Fido version 9 - 11چ
MAIL.SYS file.) Fido (the BBS) only let users generate messages;چ
FidoNet (the mailer) put messages into packets and deliveredچ
them.
At this point, four years later, Fido and FidoNet are pretty wellچ
integrated, and this latest revision completes the weld.چ
Logically, to the user and sysop, the two remain quite separate,چ
and many (non-FidoNet) Fido systems are BBS only. (Most of myچ
commercial customers are BBS only.) It is just as easy to runچ
FidoNet without Fido.
Fido's packeting/mailing system works in four discrete phases.چ
First, the destination node addresses for all the existingچ
messages is determined. This is done by the "router", more onچ
which follows. Second, the messages are put into packets by theچ
"packeter" (I never was very good at names). Third, the phaseچ
that is most obvious to sysops watching the screen, is when theچ
packets are delivered; Fido makes outgoing phone calls and sendsچ
the packets. Packets can also be received in between outgoingچ
calls. The last phase deletes un-sent packets, and marks theچ
original messages that went into the packets as "(SENT)" asچ
appropriate. This ends the FidoNet session.
Note that different from Opus and other similar mailers, Fidoچ
only puts a copy of the message into a packet; during the fourthچ
phase Fido again processes each message, and marks it or deletesچ
it as determined by the success of that packet delivery.
This is a fairly large amount of processing to do when looked atچ
on a per-message basis, and is why Fido's FidoNet has always beenچ
slower to packet than other systems. In return there are manyچ
advantages, that will become more obvious later.
FIDO AND FIDONET
Originally, as was stated before, Fido and FidoNet were twoچ
separate programs. Even when integrated into one package,چ
starting with Fido version 9 or 10, FidoNet was only usable whenچ
a FidoNet scheduled event was actually running; "continuous mail"چ
is (relative to Fido) a new concept. Version 12 (Aug. 1987) couldچ
accept incoming continuous mail, but not send mail unless aچ
FidoNet event was running; starting with 12M Wazoo and .REQ fileچ
requests are supported.
Starting with version 12N, the FidoNet portion of Fido can beچ
accessed at any time; packet creation and routing is underچ
complete control, and can be altered, automatically using theچ
routing language on a event by event basis throughout the day, orچ
manually as the sysop sees fit, up to the point when the specificچ
message has been delivered. Events themselves can be turned onچ
and off from within Fido, allowing very high-level control overچ
packet routing.
You can have Fido create packets available for pickup, with anyچ
arbitrary routing, at any time of day. For example, you can haveچ
HOLD packets of long-distance systems waiting for pickup fromچ
9:00AM til 6:00PM, while enabling outgoing calls on local-dialچ
systems, in between human callers, or any other construct allowedچ
by the routing language, without restriction. There is aچ
"penalty" of 30 - 60 seconds to prepare for a new schedule; onceچ
started, access is in the under 100 mS range.
On my 8MHz "turbo" junk-pclone, 80mS 20 meg drive, Fido takes 30چ
seconds to load, create outgoing packets and be ready for anچ
incoming call (human or otherwise). On this crappy hardware,چ
incoming echomail is received, unpacketed, tossed, the echo areasچ
then scanned and outgoing packets made and delivered in 30 - 60چ
seconds, in between human callers, using DCM and barefootچ
Fido/FidoNet 12N.
The largest network Fido/FidoNet can (mathematically!) handle isچ
(32767 * 32767 * 32767) or 3.5 x 10(e13) nodes; version 12'sچ
implementation 65,535. A recompile (change a table index from 16چ
to 32 bits) will make Fido handle about 4 billion nodes with someچ
performance loss and increased (disk) overhead, about 2چ
bytes/node. Performance with 65,000 nodes would still be betterچ
than Fido 12M's.
Current nodelist overhead (NODELIST.132) is: NODELIST.BBS 304,532چ
(physical data); NODELIST.NMP 53,920 (nodemap; see below);چ
NODELIST.IDX 53920 (main index); NODELIST.NDX 2900 (host index).چ
NODELIST.SYS is no longer used.
FIDONET TOPOLOGY
The router design mimics exactly the FidoNet network topology.چ
The network went through four (so far...) stages: a "flat"چ
system, ie. point to point; addresses were a simple number 1 -چ
32767. The second formalized the concept of "nets", incorporatingچ
the routing optimization formerly done with Fido's primitiveچ
router. The third includes zones, which are similarچ
mathematically to nets, but in real life act quite differently,چ
with "zone gates" concentrating mail between zones (generallyچ
continents) because of real-life issues of telephone connectچ
costs and equipment compatibility. The fourth adds "points",چ
allowing for the next (or current, I am a bit slow sometimes)چ
wave of BBS technology.
OOPS BACKTRACK A LITTLE:
A small aside on nets and regions: "regions" originally were onlyچ
a way for nodes not in a net (ie. not inside a local callingچ
area) to be syntactically compatible with the "net/node"چ
addressing scheme; since most nodes were in the most heavilyچ
populated areas, cities, where nets naturally form, "regions"چ
would be where nodes not in cities would be found. Nodes inچ
regions (marked REGION in the nodelist) act as any other node,چ
but the mailers do not do the automatic routing to the "host" forچ
the region -- mail is sent direct, or point to point.
The function of region hosts as another layer of organizationalچ
hierarchy is a recent addition, and not part of the topologyچ
itself. Still further, there is nothing magic about the numbersچ
themselves -- regions being numbered 1 - 99, nets 100 - 999 etcچ
is a totally arbitrary decision on the part of the keepers-of
the-lists. The only magic numbers are 0's -- these indicate theچ
host for the entity, ie. zone, net or region.
ROUTER DESIGN
Back to the router design. While the hierarchical model ofچ
net/node is extremely useful (if not indispensable) there areچ
still thousands of exceptions, usually on a system by systemچ
basis; you forward mail for one system that is local but is aچ
toll call for other net members. Your net has a sugar daddy thatچ
can make long distance outgoing calls. One system calls in toچ
pickup their mail. Commonly called systems are more efficientlyچ
handled in some special way.
You need to remember that the mathematical model used frequentlyچ
has nothing to do with the "real" world. This is as it should be.چ
However, you need a good solid theoretical base for the networkچ
otherwise the world falls apart. The router bridges the twoچ
otherwise-incompatible worlds.
Fido's router design can handle any topology based on our addressچ
syntax: zone:net/node, plus any arbitrary number of exceptions.چ
To do this, the router is very simple -- not complex.
Logically, the router is an N x N crossbar switch, where N is theچ
number of nodes in the nodelist. You can imagine a crossbarچ
switch by drawing on paper a grid:
IN
--> 1 ----O---O---O---O---O
| | | | |
2 ----O---O---O---O---O
| | | | |
3 ----O---X---O---O---O
| | | | |
4 ----O---O---O---O---O
| | | | |
5 ----O---O---O---O---O
| | | | |
1 2 3 4 5
OUT
Shown is a 5 x 5 crossbar switch. The O's represent an OFF (butچ
potential) connection; X's represent a ON connection. Theچ
connection (3,2) is ON, all others closed. If a signal wereچ
applied to Input 3, it would appear also on Output 2. (ASCIIچ
graphics are terrible, sorry!) You will notice that by placingچ
X's and O's appropriately, any input can be connected to anyچ
output.
A "real" crossbar switch can route one signal to manyچ
destinations; just place X's along the same horizontal row in theچ
example above. Any node can route to any node; times (N) nodes isچ
(N * N) possible states. Not pleasant to think about in realچ
terms -- a 5000 node nodelist would mean 25,000,000 states toچ
represent on your disk! This is not a very useful side effect forچ
us; our messages have a single destination address.
Fido's router places one limitation upon the crossbar design:چ
there can be only one possible destination per node. It can stillچ
be any possible node, but only one at a time. This means theچ
router can consist of (2 * N) entries -- the originating node andچ
the destination node.
You can imagine Fido's router as the crossbar switch above, or asچ
I do, a simple two column table:
----+----
1 | _
2 | _
3 | 2
4 | _
5 | _
The _'s represent potential, but OFF connections. #3 has beenچ
routed to #2 by merely filling in that table entry. This table isچ
called the NodeMap.
(Fido's nodemap also contains a third column, where attributesچ
like HOLD, SEND-TO, PICKUP and other things are stored. Theseچ
attributes are built into the nodemap for programming convenienceچ
only, they are not really part of the router per se.)
HOW THE ROUTER WORKS
At FidoNet mail time, Fido prepares the router files beforeچ
making packets and outgoing phone calls. The basic net hostچ
routing is performed, then any routing specified by the sysop inچ
route language files.
Before any routing, the table looks like this:
ADDRESS ROUTE-TO ATTRIBUTES
1:1/1 1:1/1 (none)
1:1/2 1:1/2 ...
... ... ...
1:125/0 1:125/0
1:125/20 1:125/20
1:125/111 1:125/111
... ...
2:500/0 2:500/0
2:500/2 2:500/2
... ... ...
Basic default routing is applied, which does the FidoNet-as-we-
know-it net and zonegate routing (see the Appendix A: DEFAULTچ
ROUTING section):
ADDRESS ROUTE-TO ATTRIBUTES
1:1/1 1:1/1 ...
1:1/2 1:1/2
... ...
1:125/0 1:125/0
1:125/20 1:125/0
1:125/111 1:125/0
... ...
2:500/0 1:1/2
2:500/2 1:1/2
... ...
At this point Fido performs any additional routing you may haveچ
specified, such as overriding the routing, HOLD packets, enablingچ
only certain nodes or groups of nodes per schedule, etc. Thingsچ
like HOLD, PICKUP, SEND-TO and other basic concepts are asچ
attributes within the nodemap.
The nodemap is built on disk, and can be saved between schedulesچ
so that it an be used over and over; this is called a "QUICK"چ
FidoNet event. It takes my Fido system mentioned aboveچ
approximately 90 seconds to completely build the nodemap (aboutچ
100 route language statements); subsequent "QUICK" events take aچ
fraction of a second.
PACKET CREATION
Fido creates packets when a FidoNet schedule starts (which isچ
controlled by Fido's scheduler and is outside this discussion).چ
For every message in the netmail message area, Fido consults theچ
nodemap, in two steps:
First, the actual destination (for example: 1:125/111) is lookedچ
up in the ADDRESS column of the nodemap. The ROUTE-TO columnچ
determines where this message goes, ie. into which packet. If theچ
destination node is not found, the message is marked (ORPHAN).
Secondly, Fido looks up the packet (ROUTE-TO) address (1:125/0)چ
itself, in the ADDRESS column. This is done to locate theچ
ATTRIBUTE bits for the destination node. If the bits indicate itچ
is OK to packet this message (SEND-TO set, etc) then the packeterچ
creates the packet.
This is done for all messages in the netmail area; once all theچ
packets are built then FidoNet can dial out, allow incomingچ
pickups, etc.
Messages put into packets are not modified in any way; packetsچ
contain a copy of the original message. The post-FidoNet processچ
takes care of messages that have been sent.
FIDONET SESSION COMPLETION
When a FidoNet schedule is over, Fido processes packets that wereچ
received from other mailers and cleans up any packets it hadچ
created earlier.
Packets that are un-sent are merely killed; the messages thatچ
these packet(s) were created from still exist in the netmailچ
area; when a FidoNet session start again, Fido may put theچ
messages into a packet to the same destination node or possiblyچ
another; since packeting is done only before actual mailing theچ
routing can be altered at any point up to actual successfulچ
transmission.
Packets that are sent, or picked up, are handled slightlyچ
differently. The packets themselves are deleted, but Fido onceچ
again refers to the router to mark the messages that comprisedچ
the packet as (SENT), or kills them if they were indicatedچ
(KILL/SENT) by the originator.
Appendix A: DEFAULT ROUTING
Fido/FidoNet's routing is not "built-in" nor hard-coded; if itچ
were not told otherwise, Fido would send messages to theچ
destinations in the message itself. The routing needed to make aچ
practical mailer are added as layers upon this base; the tradeoffچ
is speed vs. flexibility and accuracy. (Speed is, um, somewhatچ
improved over older implementations...)
What the real-life Fido does at FidoNet mail time is make a passچ
through the table, and fill in the "default" routing that definesچ
the FidoNet topology, which is our zone:net/node with routing toچ
HOSTs for nets, which goes like this:
-For nodes in our own net, send direct (point to
point)
-For nodes in a net in our zone, outside our net,
send to it's host (net/0)
-For nodes in a region in our zone, sent direct
-For nodes in another zone, send to it's zone
host (zone:0/0)
The first three make sense in the network as we know it; theچ
fourth requires some background.
FidoNet's topology is based upon a gimmick: the address of theچ
logical host for any net or zone is composed of the number of theچ
net or zone, with the magic zero added as the least significantچ
address field. A net or region host is net/0 or region/0; a zoneچ
host is zone:0/0. FidoNet sysops use net/0 routinely; no one usesچ
zone:0/0 routinely, if at all.
The difference is that the addressing scheme, the topology, is aچ
mathematical construct, and has nothing to do with the realچ
world, ie. overseas phone calls, governmental regulations,چ
manufacturer incompatibilities, etc. The addressing scheme needsچ
to be rigorous and provide a solid design base for allچ
implementations.
If we didn't have real-life complications like the above, neverچ
mind how overloaded the poor zone host computer would be, theچ
mathematical model might fit the real world. Obviously itچ
doesn't, and never did.
The solution in Fido's scheme is to merely modify the defaultچ
routing. There exists a keyword in Fido's routing languageچ
(called, not surprisingly, "ZoneGate") that does exactly what itچ
sounds like: it routes all mail destined for another zone to anyچ
arbitrary node designated "zone gate".
Zone Gates were thunk up at the now notorious "New Hampshireچ
meeting" in '86 or so. The idea was to make it so that net/nodeچ
mailers, ie. not zone-aware, could route messages destined forچ
other zones. The thing was called the "IFNA Kludge", and consistsچ
of two parts: (1) an addressing kludge to trick the mailer toچ
route the interzone message to a node in it's own zone, and (2)چ
to have the full zone:net/node origination and destinationچ
addresses buried in the message body itself, hidden behind a lineچ
that began with Control-A, so that message editors could learn toچ
ignore it. (For your curiosity: full address consists of the veryچ
first line in the message, that looks like: "^AINTL z:n/f z:n/f",چ
where the first address is the destination node address, theچ
second the originator.)
The addressing trick is: "Address the message for zone (N) toچ
node 1/(N) in my zone". Node 1/(N) is designated the zone gate;چ
for example, the zonegate for Europe, Zone 2, node 1/2, in theچ
North American zone 1. And so on.
Fido is a registered trademark of Tom Jennings
FidoNet is a registered trademark of Tom Jennings
(Sorry, I gotta say this!)
NEW SOFTWARE POLICY
This is the new (June 1989) software policy for the Fido/FidoNetچ
package. Please read it carefully.
First, some important definitions:
Hobbyists run BBSs for their own personal reasons. Their BBS isچ
not associated with their employer or any business. How they runچ
their BBS is none of my business, ie. private, public,چ
subscription, collective or chattel slavery.
Commercial users are companies, corporations, proprietorships orچ
any other business entities that run a BBS, either publicly orچ
privately, associated with their business. "Non-profit" and "notچ
for profit" organizations are included in this category.
And here's the deal:
HOBBYISTS AND INDIVIDUALS: Fido/FidoNet is shareware; you canچ
download the software itself, minus documentation, from the Fidoچ
Software BBS. There is no machine-readable documentation. (If youچ
thought the version 11 docs were unwieldy ... besides I payچ
royalties to the author). I will provide no direct support.چ
Hobbyists can receive the latest version on diskette plus printedچ
and bound documentation for $50. If you later desire updates viaچ
diskette instead of download, updates (including printed errataچ
sheet) cost $20 plus the original Fido Software diskette. $5چ
discount on either for US ca$h payment.
COMMERCIAL USERS: Fido/FidoNet is a usual licensable product; theچ
license fee is $175, as it has been for two years. You willچ
receive the latest software version, complete documentation, andچ
support via the Fido Software BBS and voice telephone. (This hasچ
proved to be more than adequate for over two years.)
Deals, exceptions and special arrangements can be made on a caseچ
by case basis. In all cases, bugs are fixed promptly, as theyچ
have been for five years. This is basically the policy that wasچ
in force through 1987. It worked pretty well, there were very fewچ
problems, and most of those were caused by my ambiguity.
SHAREWARE DISTRIBUTORS: I do not wish Fido/FidoNet to beچ
distributed by "shareware distributors", "libraries" or otherچ
similar organization. The problems are too numerous to count:چ
shipping ancient, incomplete versions; missing critical files;چ
giving out incorrect information regarding support; giving badچ
operating advice, etc. Never mind the fact that they are usingچ
the software for profit, regardless of claims to the otherwiseچ
and suggesting that their customers pay instead.