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