jbuck@epimass.UUCP (05/08/86)
I like maps. I decided to make a map of the backbone of Usenet. Not Gene's map, mind you, though I started from it. Rather, what sites are REALLY responsible for getting the news delivered. My understanding of what "backbone" is, is the core of the net. When an article travels from point A to point B, it should enter and leave the backbone in its path only once. If a particular path is frequently traveled between two backbone sites, that path is topologically part of the backbone, in that it supplies extra redundancy to the net. Speaking very loosely (the math types may flame me if they like), I set out to find the "transitive closure" of the backbone. Here is the algorithm I used: Start with a large collection of paths from news messages (I had 10000 or so); chop off the usernames and use sort -u to get rid of duplicates. Replace all consecutive strings of backbone sites from Gene's map with "~". A single tilde might represent something like decvax!decwrl!glacier!oliveb. Eliminate all paths except those that have two or more tildes. For the remaining paths, a message has entered, left, and reentered the backbone. Eliminate things like ~!site!~ if site could be deleted and the path would be valid (if I happen to talk to two sites who also talk to each other, I add no redundancy because if one site goes down, no news flows). The remaining sites or strings of sites between tildes are candidates for adding to the "transitive closure". To be conservative, I didn't add those paths that occurred only one or two times, but I found lots of heavily used paths, many of which seem to carry more traffic than some official backbone sites. Once the new sites are added, repeat the whole procedure with the larger set of backbone sites. Keep going until nothing changes (it took six or seven iterations, I think). Here is the result for North America. Two sites, drillsys and cuae2, have been removed because they don't appear to meet the definition of a backbone site (if anything goes through drillsys, other paths always beat it to the Bay Area, and I can't believe cuae2 is the only net access to Illinois). All the other sites on the official map will be reentered by the algorithm above if you remove them. "^" and ")" represent lines crossing over without connecting. Links outside North America have been removed. cbosgd------------------------------------clyde---------watmath........utzoo | | : | /--mhuxr------mhuxn------------\ | : | / \ | : ihnp4-------alberta------ubc-vision \ burl ---allegra--------------^---+ / | : \ | / : | | | +--------uw-beaver ulysses-------------bellcore : | | | | | \----<CHAIN>---/ | : | | | bullwinkle tektronix-------------------------decvax----linus | | | | | / /| | \ | | | | /---intelca--)---------^-\ <mod.*>----ucbvax--/ / | | | | | | | / | | \ \ / | | | | | | qantel------------)------\ | oliveb------glacier----decwrl / | | | | | | | \ | / / | | | | | | | hplabs-------sdcrdcf ittatc | | | | | | rochester : | | | | | | | | \ : sdcsvax-------dcdwest | | | | | | \ hao | | | | | | | \ : ncr-sd---ncrcae--ncsu | | | | +--^--houxm----whuxl---^------^----whuxlm-------------\ \ | | | | | \ : | \ | | | | | \-seismo........gatech-----akgua----mcnc-)-philabs | | / |\ \ | | | lll-lcc-----lll-crg--------/ | \ \--------------------------------)--cmcl2 | / | \ | \_____ | | | / | \ | \ ulowell---wanginst | | / | caip-----harvard-----)----------------)---------------+ / / | | /|\ \ | | / topaz styx--nike / | \ think-)----------------)---------mit-eddie | \ \--------/ / | \ | | | | \ / | \ | ci-dandelion | | \-------------/ | -----^---husc6-\ | | +--------uwvax---------+ | \--talcott---panda--genrad \---------------------+ <CHAIN> above, connecting bellcore and ulysses, is the path petrus!sabre!zeta!epsilon!gamma believe it or not, this beats the straight route quite often. This may have been because either bellcore or ulysses was down for a while recently. The chain allegra!princeton!orsvax1!pyrnj!caip also passes a good amount of news. I've seen a few occurrences of wanginst!vaxine!encore!linus too. These two chains should be added, but I had trouble drawing them in. Notice there are three extra east-west connections, two to Southern CA: uw-beaver!bullwinkle!rochester!seismo (Wash state - NY - VA) decvax!ittatc!dcdwest!sdcsvax (NH - Conn. - S. Calif.) mcnc!ncsu!ncrcae!ncr-sd!sdcsvax (N. Carolina - S. Calif.) Southern Californians have repeatedly complained that the backbone map doesn't reflect reality for them (it suggests that their news comes by way of Silicon Valley). It doesn't; their news mostly comes from the East Coast. The extended map shows better than the official one how important decvax is to the net topology. Does anyone know who husc6 is? They aren't on the UUCP map, but a lot of news arriving here in the SF Bay Area goes through their machine. This map is really a snapshot, assembled from two week's worth of traffic. There's no telling if sites on it have broken software or only pass subsets of news. Someone following the same method from a different part of the country might come up with a slightly different set (I think). Suggestions for improving the method are welcome. -- - Joe Buck {ihnp4!pesnta,oliveb}!epimass!jbuck Entropic Processing, Inc., Cupertino, California Better living through entropy!