393 lines
16 KiB
Plaintext
393 lines
16 KiB
Plaintext
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!)
|