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