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!)
