FIDO/FIDONET ROUTING, TOPOLOGY, HISTORY AND RECENT CHANGES
Tom Jennings, 1:125/111
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 (more to follow) you might find the design hasŤ
become interesting.
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, five 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 inbetween 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 unlike 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. Version 12M supports Wazoo and fileŤ
requests.
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 20Ť
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 60 - 90Ť
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(13) nodes; version 12'sŤ
implementation 65,000. 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 three (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. Third, the current scheme, 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.
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.Ť
Additionally, the function of region hosts as another layer ofŤ
organizational heirarchy 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 heirarchical model ofŤ
net/node is extremely useful (if not indispensible) 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.
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Ť
atributes 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 sucessfulŤ
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 tolopogy, 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 ot the number of theŤ
net or zone, with the magic zero added as the least signifigantŤ
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 incompatibilies, 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!)