* Fido/FidoNet Routing, Topology, History, and Recent Changes Tom Jennings, 1:125/111 15 June 89 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 you might find the design has become¨ interesting once again. (And starting July 89, Fido/FidoNet is once again shareware. File Request "ABOUT" and "FILES" from 1:125/111 for complete details.) 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, four 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 in between 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 different from 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; starting with 12M Wazoo and .REQ file¨ requests are supported. 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 30¨ 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 30 - 60¨ 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(e13) nodes; version 12's¨ implementation 65,535. 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 four (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. The third 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. The fourth adds "points",¨ allowing for the next (or current, I am a bit slow sometimes)¨ wave of BBS technology. 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. The function of region hosts as another layer of organizational¨ hierarchy 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 hierarchical model of¨ net/node is extremely useful (if not indispensable) 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. You need to remember that the mathematical model used frequently¨ has nothing to do with the "real" world. This is as it should be.¨ However, you need a good solid theoretical base for the network¨ otherwise the world falls apart. The router bridges the two¨ otherwise-incompatible worlds. 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¨ attributes 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 successful¨ 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 topology, 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 of the number of the¨ net or zone, with the magic zero added as the least significant¨ 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 incompatibilities, 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!) NEW SOFTWARE POLICY This is the new (June 1989) software policy for the Fido/FidoNet¨ package. Please read it carefully. First, some important definitions: Hobbyists run BBSs for their own personal reasons. Their BBS is¨ not associated with their employer or any business. How they run¨ their BBS is none of my business, ie. private, public,¨ subscription, collective or chattel slavery. Commercial users are companies, corporations, proprietorships or¨ any other business entities that run a BBS, either publicly or¨ privately, associated with their business. "Non-profit" and "not¨ for profit" organizations are included in this category. And here's the deal: HOBBYISTS AND INDIVIDUALS: Fido/FidoNet is shareware; you can¨ download the software itself, minus documentation, from the Fido¨ Software BBS. There is no machine-readable documentation. (If you¨ thought the version 11 docs were unwieldy ... besides I pay¨ royalties to the author). I will provide no direct support.¨ Hobbyists can receive the latest version on diskette plus printed¨ and bound documentation for $50. If you later desire updates via¨ diskette instead of download, updates (including printed errata¨ sheet) cost $20 plus the original Fido Software diskette. $5¨ discount on either for US ca$h payment. COMMERCIAL USERS: Fido/FidoNet is a usual licensable product; the¨ license fee is $175, as it has been for two years. You will¨ receive the latest software version, complete documentation, and¨ support via the Fido Software BBS and voice telephone. (This has¨ proved to be more than adequate for over two years.) Deals, exceptions and special arrangements can be made on a case¨ by case basis. In all cases, bugs are fixed promptly, as they¨ have been for five years. This is basically the policy that was¨ in force through 1987. It worked pretty well, there were very few¨ problems, and most of those were caused by my ambiguity. SHAREWARE DISTRIBUTORS: I do not wish Fido/FidoNet to be¨ distributed by "shareware distributors", "libraries" or other¨ similar organization. The problems are too numerous to count:¨ shipping ancient, incomplete versions; missing critical files;¨ giving out incorrect information regarding support; giving bad¨ operating advice, etc. Never mind the fact that they are using¨ the software for profit, regardless of claims to the otherwise¨ and suggesting that their customers pay instead.