Which makes you wonder why we don’t use them more.

Not only are they dependent on the weather, but they are also considerably slower than an airplane. I’ve been thinking about how to make them faster, and my inspiration came from a book about airplanes – The Deltoid Pumpkin Seed by John McPhee. This book documents, in popular language, the experiences of a group of entrepreneurs and engineers to build a hybrid airplane/airship (the Aereon) that would have a small engine and use helium to improve its lift characteristics.

Why not do the same thing with a sailboat? Especially since most of the drag comes from the “wetted hull”, it would make sense to lift the hull out of the water as much as possible and leave only the keel submerged. Ship designers have been doing this for years with cleaver hull designs intended to lift themselves out of the water as they get up to speed, but the Aereon design suggests another way – helium.

What seems to make sense to me would be to build a trimaran and fill the outriggers with helium.

Though I still have a hard time believing some of these claims, I have to admit that this technology shows promise.

The Coulomb barrier that must be overcome to fuse two protons is about 5 MeV – not something you’d expect at room temperature, but well within the range of a standard particle accelerator. The problem is the minute cross section of the nucleus – protons with enough energy to fuse are far more likely to be scattered away from each other unless they are precisely aligned in a head-on collision.

That’s where the cold fusion claims start to get interesting. All of the cold fusion reports that I read involved palladium as a catalyst. Now palladium has the unusual property that it can absorb significant quantities of hydrogen. There doesn’t seem to be a consensus on exactly how this works, but one explanation is that the hydrogen nuclei can move fairly freely within the palladium crystal mesh. Now if I wanted to line something up at atomic dimensions, a crystal would be the obvious choice, and if I wanted to line something up while its moving, then I would want a crystal that allowed my particle mobility. So palladium seems like an obvious choice to line up moving protons to precisely collide them.

The approach I’m thinking of right now is to use a particle accelerator to achieve the energies needed for fusion, since I still don’t see it happening with only thermal or low voltage electrical energy, but to fire the accelerated protons into a palladium crystal in order to achieve the alignment necessary for fusion.

We could model this theoretically using Schroedinger’s equation, but actually solving this equation seems very daunting. A more promising approach would be to run some experiments to examine how proton beams interact with palladium crystals. In the limit as the energy approaches zero, the crystal should just absorb the beam, since it absorbs elemental hydrogen, so we can expect some kind of interesting behavior. I’d particularly hope to find some special angles and probably special energies at which a proton beam, fired into a palladium crystal, can travel for significant distances within the crystal with only mild dissipation. Common sense now tells us that such a beam will eventually become aligned with the crystal, and if two such beams are fired into a large enough crystal from opposite ends, they will hopefully be aligned by the time they meet and the middle and we’ll stand a good chance of getting a nuclear fusion reaction.

Carrying this one step further, we’d like to minimize the thermal vibrations of that crystal in order to maximize its alignment, so I’d like to conduct these experiments not only at room temperature, but also at low temperatures, say liquid nitrogen and liquid helium temperatures. It would be ironic indeed if the primary problem with cold fusion to date is that it isn’t cold enough.

Not a very encouraging result for those of us designing routing protocols.

Yet there is hope. The result is only an average. We can do better than the average if we allow our routing function to be skewed towards certain network topologies. And it occurs to me that the Internet doesn’t change fast enough that we can’t skew our routing function towards the current network topology.

How can we do this? With dynamic addressing: skewing our address summarization scheme to reflect the current network topology.

Of course, we’re already doing this, to an extent. It’s what every IP network engineer does when he assigns summarization blocks; they correspond to groupings of devices within the network topology.

But I’d like to take this quite a few steps farther. I’d like the summarization blocks themselves to be automatically allocated. I’d like to be able to handle the case where a WiFi link connects devices from two different ISPs, or when a company wants to become multi-homed with two ISPs. In both cases, we’re connecting devices together from radically different summarization blocks. How can we handle this?

By dynamically readdressing the network. When new links appear, exception routes are placed into routing tables. Over time, the network readdresses itself so that those exceptions can now be summarized together.

Let’s take a simple example – a single autonomous system uniformly running OSPF. When a new link appears, routers recompute their routing tables and then auto-summarize – automatically group addresses into routing table blocks. Then another algorithm runs, which computes, for each router, the compete set of destinations which should be routed to each next hop. The collection of all of these sets forms a topology on the destinations. The objective is to now (re)assign addresses so that as many of those subsets as possible can be neatly summarized. Then we reassign addresses to the network devices and gradually morph our addressing structure toward this new topology.

Obviously, there are performance issues here. These algorithms can be quite time consuming if they are run on every route flap. Finding a suitable address assignment might be an NP-complete problem. How do you handle a link between two autonomous systems? We probably want to consider possible future link failures, as well, when assigning those addresses.

But let’s leave all that stuff out for now. It’s not too hard to see what changes we need to start making now to head in this direction, and it’s starting to sound like a routing loop on this blog – we need to shed our dependence on static IP addresses.

We need dynamic DNS. Not like we’ve got it today, so heavily packet filtered that it’s almost useless, taken on as an afterthought, client-only dynamic DNS. Dynamic DNS, coupled with DHCP, needs to be our default mode of operation. A machine boots, be it client, server, or even router. It DHCPs to get its IP addresses and then uses a cryptographically secured transaction to install them on its DNS name. It has to be prepared for those addresses to timeout and be replaced with different ones, which will be migrated into its DNS information. Protocols like TCP have to be prepared for mobility, in the sense that even a server (yikes!) may be changing IP addresses mid-session.

And yes, routers too have to use DHCP. In fact, routers have to become not only DHCP servers, but they need to participate in a next generation DHCP that assigns entire blocks of addresses. A router requests a block of x number of addresses for its subnet, and then hands those addresses out to its clients. And has to be prepared for that entire block to timeout and be replaced by another.

While all that is being implemented (or not), we can start experimenting with protocols and algorithms to actually implement dynamic address allocation (or not). And defeat Thorup and Zwick’s n^2 by constantly shifting the network to adjust.

Basically, you’d need a computer chip attached to a human nerve. In an age of VLSI, I doubt that building the chip would be that hard. To tackle the spinal cord injury, for example, I’d imagine a chip built into a titanium vertebrae, and connected to a control unit much like a pacemaker. Probably two chips built into two titanium vertebrae, one to attach to either side of the spinal cord break.

The surface of the chip would be an dense grid of electrodes, each capable of sending or receiving small electrical impulses. A microprocessor would be responsible for mapping electrodes on one chip to electrodes on the other, thus insuring that electrical impulses were communicated across the break. Building a chip with a dense enough grid doesn’t seem like anything that can’t be done using contemporary technology.

The hard part, I think, would be attaching the chip to the spinal cord. I think an anisotropic conductive adhesive, probably an epoxy, should do the trick. You’d need an conductive adhesive (obviously) to transmit the nerve impulses, but it couldn’t conduct in any direction. Imagining the spinal cord connected vertically to the chip (in the x-y plane), you’d need an adhesive that would only conduct in the z-direction (that’s the anisotropic part).

Conductive adhesives are available, and in fact widely used in the electronics industry for connections that can’t be done with solder, either because of the heat required or because the materials (like silicon) won’t stick to solder. They’re generally made by suspending tiny spheres of silver in the epoxy, which touch each other and conduct after the epoxy dries around them. That’s an isotropic adhesive, which conducts in all directions.

That wouldn’t work for our purpose, because we’d need an anisotropic adhesive. Such things exist, mostly in film form, where the film has been designed to conduct only along its narrow width. I don’t think a film would do, either.

We’d need an anisotropic epoxy. For starters, how would we set the direction of the anisotropism? My first idea would be to use a magnetic field while the epoxy is setting, much like the way iron shavings line up in a magnetic field. In fact, this might be almost exactly what is needed. Instead of tiny spheres of metal, we need to figure a way to manufacture tiny slivers of metal, coated with an insulator except at their tips. Maybe shape the tips like a ball and socket so they tend to link up in a chain instead of touching laterally. Or maybe something else is needed, some kind of chemical conductor that would line up at the molecular level.

In any event, it seems like something worthwhile investigating. I’m not a doctor, but the adhesive seems to me to be the main obstacle to this.

A quarter century later, I think we can offer a more balanced perspective. Host-based authentication in general is now viewed as suspect and has largely been abandoned in favor of cryptographic techniques, particularly public-key cryptosystems (think ssh) which didn’t exist when TCP/IP was first designed. We are better able to offer answers to key questions concerning the separation of identity, address, and route. In particular, we are far less willing (at least in principle) to confuse identity with address, if for no other reason than an improved toolset, and thus perhaps better able to judge source routing, not as a fundamental security loophole, but as a design feature that became exploitable only after we began using addresses to establish identity.

Can we “fix” source routing? Perhaps, if we will completely abandon any pretext of address-based authentication. What, then, should replace it? I suggest that we already have our address-less identifiers, and they are DNS names. Furthermore, we already have a basic scheme for attaching cryptographic keys to DNS names (DNSSEC), so can we put all this together and form a largely automated DNS-based authentication system?

The basic idea is that we authenticate using DNS names (not IP addresses), so it stands to reason that a basic operation has to be obtaining a connection’s remote DNS name in a secure manner. Or perhaps I should say, obtain a connection’s remote DNS names, because it will become clear that we want a connection endpoint to have multiple ones. How can we do this? Several options suggest themselves:

• Modify the transport protocols to communicate the endpoint’s DNS names
• Modify the IDENT protocol so that it can identify remote DNS names
• Use IPSEC (somehow)

Let’s assume for the moment that we’ve solved this problem. The remote endpoint claims to be one or more DNS names and has communicated that information to us. Now we need to authenticate it. The obvious way is a DNS lookup on the name to obtain a public key. The remote endpoint now has to back up its claim by using the matching private key in some way. We want the entire session to be authenticated, not just one little piece of it, so “some way” seems to imply signing all the IP packets. We don’t want to use the private key from the DNS lookup to sign all the packets, because that would expose too much information about a fairly long-lived key, so probably something like using the key pair from the DNS lookup to establish some per-session keys and then using them to sign the packets would be more agreeable.

Sounds a lot like IPSEC.

The problem, as always, lies in key management. IPSEC was designed largely to protect host-to-host communications, not application-to-application, and the structure of its key management reflects this. IKEv2, probably the most widely used IPSEC key management protocol, operates using privileged daemons on reserved port numbers (500 and 4500). This seems to preclude the possibility of having multiple distinct identities associated with different processes on the same machine.

So maybe simpler would be better. Just cryptographically sign each packet using an AH header that matches a DNS-published public key. Use DNS’s existing mechanisms to periodically time out that public key and replace it (maybe once an hour), thwarting attempts to take advantage of the exposure of the key to crack it. The need for a transition period seems to dictate that multiple public keys can be associated with a single DNS name, and that signing with one of them is sufficient to establish identity.

Of course, using any kind of public key whose exchange hasn’t been protected by encryption exposes it, so it would seem that this simple scheme is about the best we can do without some kind of handshake exchange. In particular, the simple scheme can naturally support multicast. Also, the use of multiple public keys suggests the possibility of a transition that starts using a “low security” key as described in the previous paragraph, then transitions to a “high security” key that is used to authenticate and encrypt the exchange of a session key.

In short, while IPSEC’s basic packet headers seem quite suitable for this purpose, its key management scheme seems cumbersome and overblown. I’ll use the simplified variant just described for the rest of this essay.

Returning now to the question of communicating DNS identity, it doesn’t matter (all that much) since any such communication isn’t trusted until it is verified. Probably the most theoretically rigorous approach would be to specify the DNS name as part of the IP packet header, so your packet headers now contain the source location (IP address), source identifier (DNS name), and authentication (AH header). Other, less elegant but more palatable approaches (from an efficiency standpoint), would be to use an enhanced IDENT protocol, or an extra TCP header during TCP initialization, or some other out-of-band mechanism.

In short, our identifiers are DNS names. We have signed public keys in DNS. Hosts or applications possessing the matching private keys are able to act as the entity named by the matching DNS name. The application uses some kind of API to install a private key that will be used to sign all of its packets. It also announces its DNS name (in IP header options, or TCP header options, or via an IDENT daemon). All of this is enough to allow the recipient to validate the identity of its remote peer, independent of its IP address.

Package all of this up into a library, and authentication takes a relatively simple form – applications need only to check the remote DNS name against a list of valid names. Regular expressions seem a natural choice. The kind of DNS wildcard syntax used by NFS exports files or X Windows xauth now look a lot more attractive as a generic authentication framework.

Since DNS is hierarchal, fine-grained authentication seems to fit naturally into this model. For example, I don’t want my login sessions authenticated on a per-host basis, but rather on a per-user basis. This can be accomodated simply by adding DNS names for individual users. Rather than having a single DNS name for a single host, a host can manage an entire zone underneath its name. Each machine can run its own DNS server and manage its own DNS space, so “bigsky.freesoft.org” can create a DNS name “baccala.bigsky.freesoft.org” for one of its users. Attach a public key to that DNS name, and remote applications can specify “baccala.bigsky.freesoft.org” in their authentication list to allow access to this user account. Since DNS is not tied specifically to any one naming scheme, organizations have a great deal of flexibility in managing their zones. Specifically, the same authentication scheme, unmodified, could also be used to create a single domain-wide user account “baccala.freesoft.org”, or “baccala.users.freesoft.org”, and it would all be transparent to remote applications, so long as local applications possessed the correct matching private keys.

Applications would naturally possess multiple identities – one for the user account they run under, one for the machine they run on, maybe other for user groups or workstation clusters. How does an application know which one to use? This could be negotiated using some kind of key exchange protocol, but that wouldn’t be realistic in a multicast environment. So probably the best thing is to allow multiple AH headers to stamp multiple identities on a single packet. Then, it’s up to the application to decide which set of identities to use for a particular transaction, subject always of course to the proviso that it must possess the correct set of private keys. And this implies that a remote entity may have multiple identities, any one of which, presumably, can be used for an authentication process.

More can be done. If we want to encrypt without pre-shared keys, a similar scheme can be used – obtain a public key from DNS and encrypt packets so that only the matching private key can decrypt. Again, when you think about a multicast environment, it starts to look a lot more attractive that running a key exchange protocol between every pair of hosts.

But I’ll stop here. My point is this: we’re now able to assemble an authentication scheme based on cryptographically secure DNS identifiers, and we’ve have enough problems with address-based authentication that we should. If we finally ditch this idea that you can convert an IP address into a DNS name, and instead insist that that translation only really works in the other direction, we can overcome the real design flaw that doomed source routing.

A university is a corrupt institution.

First, universities are successful. I have nothing against success per se, but what it takes to succeed in this society is some kind of accommodation with capitalism; you can’t really make it in this world otherwise. A restaurant is a capitalist organization; a soup kitchen is not, and therein you find the greatest distinction between them. Both feed people. One refuses its food to anyone who can not or will not pay; the other offers its food free of charge. One occupies prime real estate and sports swank decor; the other is relegated to the cheapest digs and plainest furnishings. One turns a tidy profit for its owners; the other is dependant on hand outs. One is moral; the other is not.

Likewise with schools. Walk onto a university campus and you will be immediately impressed by the gleaming architecture, the broad walkways, the teeming student life. Yet at what cost? $100 textbooks, multi-thousand-dollar tuitions, credit-card restricted access to journal articles. A university, like a restaurant, has reached an accommodation with capitalism, and it is this: they are selling education.

As obvious as this may sound, it has taken me years to really accept this. I turned first against our laws, then against our economic system, then against our leaders, finally against our system of government, but still I clung to our school system. I applied as a teacher after I had reached a point where I would work for almost no one else. Why? Because they are educators, I told myself, remember the sanctity of knowledge.

They’re educators the way Bill Gates is a programmer.

Don’t get me wrong – I have friends who are university professors, just like I have friends who are restauranteurs, who are businessmen, who are soldiers. If I held everyone I knew to some moral gold standard, there’d be no one left, including myself. Yet, by and large, we can judge large institutions by the values they promote, and a core value of modern higher education is this:

Education is something to be packaged and sold.

Where does the money come from? Anytime you see success in this society, you have to ask: where does the money come from? It’s not a charity, because if so it would look like a homeless shelter, not a 5-star hotel. And the answer is simple: it comes from the students. Those few with the absolute best grades (or the greatest skill pitching a baseball) get scholarships, the rest pay. If they can’t pay now, then there’s always a nice student loan package so they can pay later. After all, what are the students there for? To learn? That’s quaint, but in the real world they’re there to improve their future job prospects. So the students will use their degrees to make more money, some of that money goes to paying off their loans, the university gets to build its new library, everybody is happy. Right?

A friend of mine has a daughter in her first year of college. After a semester of bad grades, he refused to pay for another, so she took out a student loan. I have to wonder – does an 18-year-old really understand how long you have to work for somebody else to pay back $8,000? I know I didn’t. When I think back on my undergraduate years, the first thing that comes to mind is huge waste of my parent’s money.

Let me qualify that, lest you be left with the notion that I advocate a throw-the-kids-out-on-their-own approach to funding college tuition. I had a good time at college and I got a solid undergraduate education in physics. That’s what my parents were paying for, right? Never mind that the library card would have been a lot cheaper than the tuition, because my parents would never have paid for my room and board if it came with nothing more than a library card. After I left college, I then got the full dose of throw-the-kids-out-on-their-own. After a while, I contemplated suicide. Maybe I wouldn’t be here now if my parents hadn’t paid for that extra five years of growing-up time.

But this isn’t about the kids. This about the schools and the teachers. How can they push multi-thousand dollar loan forms in front of teenagers and tell them to sign? How can they outlaw on-line public libraries so that Springer Verlag can cut them in on fat publishing deals? How dare they act like anyone without some paper on the wall is incompetent?

Coming back to my graduate school application, I was really in a moral dilemma. I wasn’t going to pay, but would I accept a T.A.’s position if it was offered? Wouldn’t I be then part of the thing that I despise? At the lowest rung, of course, but still, I’d be taking money from these kids to teach, right? I met my rejection with a number of emotions, but one of them was definitely relief. Like I said, it was a positive experience.

I’ve had it. I won’t pay, and I won’t participate. I won’t let my education become corrupt.

Could pocket Spanish-English dictionaries be a thing of the past?

The prospect is tantalizingly close. Anyone with a megabit Internet connection (cable or DSL) and a reasonably modern computer has a client system that can support this. Yet no Internet video clients (to my knowledge) can provide DVD-style interaction. And free software video production tools, while available, lag somewhat behind. Enough groundwork has probably been laid, though, to allow an interactive video client to be built.

Just as fifteen years ago the network provided FTP sites where users could download information piecemeal, so is the Internet’s current video offerings – a little bit here, a little bit there. Just as the World Wide Web melded the graphical user interface with a global data network, we can now contemplate melding the DVD user interface with the Internet to provide hyperlinked on-demand video.

What kind of new content could this support?

Consider, first, news service. Currently, we have traditional national and local news broadcasts, typically a half hour each in length, along with 24 hour cable news channels that basically repeat the same information over and over again, on roughly a half hour or hourly cycle. A news broadcast delivered using dynamic DVD, on the other hand, could be many hours in “length”, accessible via hyperlinks from a traditional half-hour summary. A report on the day’s political events in Washington could linked to full recordings of various speeches. Excepts from an interview could be linked to the full interview itself. A 30-second summary spot could be linked to an entire half-hour report on just that one subject. Weather reports could be hyperlinked together so that travelers could pick a city and see the local report for their destination.

Sporting events could be delivered using DVD’s largely overlooked ‘angle’ feature, which allows viewers to pick from one of up to nine different simultaneous video feeds, allowing viewer selection different camera angles on the event. Highlight footage to link into a recorded history of the entire game, and several different highlights could be made available for each game

And, of course, conventional DVDs could be delivered in this format.

Could the Internet actually delivery the performance needed to make such a system widely deployable? Unfortunately, the current answer is probably “no”. As I have discussed on this blog, caching and multicast are two critical technologies that the contemporary Internet is unable to support for fundamental technical reasons. Without caching and multicast, a video web could only work the way the World Wide Web works – by requiring each server to transmit the same data over and over again. With text and graphics, this is a nuisance. With video, it will probably be a show stopper.

A stopgap solution might be available by providing digital multicast feeds via cable TV. This would be a hybrid of conventional cable video broadcasts and cable Internet service. Using the same basic technology of cable Internet and 10-BROAD-36, a cable provider could broadcast one or more transmit-only digital channels (similar to HDTV). The difference would be that the digital signal would be in some kind of yet unspecified dynamic DVD format that would contain navigation information and be cached onto a set-top box.

What would be required to view dynamic DVD? Certainly a computer would work, but you could probably just build a DVD player with a built-in hard drive. Of course, a DVD player basically is a computer, so maybe the distinction isn’t that great. Instead of a computer that comes with a keyboard and a monitor, you could just build a computer with a standard TV video output and remote control input. In fact, I think I would favor this approach just for reasons of standardization.

So, using either the Internet or a enhanced digital cable TV feed, we could build either a Video Web, or at least provide a far superior NBC Nightly News.

I starting thinking about this, but more along the lines of building the tables dynamically, using a pool of cooperating computers on the Internet. The idea would be to direct your search towards certain game positions that you wanted to analyze. This would work well in static analysis and also in relatively slow correspondence time controls (like Gary Kasparov vs The World, or the upcoming The World vs Arno Nickel).

A big key here would be to segment your search space so that individual computers can calculate part of it independently and then return the results to a server. I think we can do this with chess because pawns can’t move backwards and captures can’t be reversed, either. So we can ask each computer to analyze up to a capture or pawn movement. We treat the pawn positions as static, and all the other pieces (the ‘mobile’ pieces) move around them. As soon as a pawn moves or a capture occurs, we’re into a different table. So long as, say, all but four of the pieces are pawns, these files are of reasonable size (a few MB) and can be computed in a reasonable time.

Pruning

We prune if we don’t want to fully analyze out the tree past the table we’re now building. Of course, this will affect the accuracy of the table; the table is a result of BOTH the position it was set up for AND the pruning decisions (and any pruning decisions made on the future tables used to calculate this one).

We specify pruning in a simple way – by omitting future tables for moves we don’t want to consider. This can be dangerous, so we require this feature to be specifically enabled for each move by a command-line switch. Actually, we use two switches, one to calculate a table for OUR SIDE to move, and another if it is the OTHER SIDE to move.

So, --prune-our-move e3e4 prunes a pawn move (assuming this is a table with a static pawn on e3) by simply ignoring e3e4 as a possible move.

Pruning an opponent’s move is more complex because we step a half-move into the future and consider our own next move. This costs us little, since we can control our own move and therefore don’t have to consider all possibilities, and improves a lot. If future tables exist for any of our responses, they are used. If no such future tables exist, then the move is regarded as a lost game.

So, --prune-his-move e7e8 prunes a pawn promotion (assuming a static pawn on e7) by considering all possible positions resulting after the pawn promotion (to either Q or N) AND the answering move. The resulting game is regarded as a win for white unless both Q and N promotions have an answer that leads to another table with a win or draw for black.

For example, let’s say we’re looking at a Q-and-P vs. Q-and-P endgame. There are four mobile pieces (2 Ks and 2 Qs), so we can handle this. But if one of the pawns queens, then we’ve got a game with five mobile pieces, and that’s too complex. But we don’t want to completely discard all possible enemy promotions, if we can immediately capture the new queen (or the old one). So we specify something like --prune-his-move e7e8 and pass in a tablebase for a Q-and-P vs. Q endgame.

We also check for immediate checkmates or stalemates.

Pruning doesn’t affect the size of the resulting tablebase. We discard the extra information. If the pruned move is actually made in the game, then you have to calculate all possible next moves and check your tablebases for them. This seems reasonable.

In short, intelligent pruning is essential to making this work. Let’s say we get into a rook and 3 pawn vs. bishop and 4 pawn endgame (or something like that). We can’t just solve the whole thing. If all the pawns queened, we’d get 7 queens on the board and that would be impossible. So we have to prune out these highly unlikely combinations. We can also prune our own moves aggressively, because we don’t have to make them! Pruning makes this whole idea feasible.

Program Design

Let’s keep the program simple. It’s designed to be run on a whole bunch of machines over the Internet, each one calculating a different table, that all then get linked together. Each table goes into a different file. The server assigns a program the task of computing a certain file. The files needed for this task are downloaded. Then the program runs locally, just calculating the requested table/file. When done, the file is uploaded back to the server.

File naming syntax: wPIECES-bPIECES.tbl

PIECES is a list of ‘mobile’ pieces (K, Q, R, B, N) followed by pawn positions in algebraic notation.

wKQ-bKQ.tbl is a (K+Q) vs. (K+Q) endgame

wKQe6-bKQ.tbl is a (K+Q+pawn-on-e6) vs. (K+Q) endgame

Certain symmetry relations exist. We don't need both wKQ-bK.tbl and wK-bKQ.tbl; just one will suffice. wKQe6-bKQ.tbl is basically the same as wKQd6-bKQ.tbl or wKQ-bKQe3.tbl

Need an algorithm to determine symmetry; maybe white should always have numerically superior side and pawns should always skew towards lowest letters and highest numbers.

We need some tables to compute others. For example, to compute wKQd6-bKQ.tbl, we need wKQd7-bKQ.tbl (possible pawn advance), wKd6-bKQ.tbl (possible x of white queen by black king or queen), wKQd6-bK.tbl (possible x of black queen by white king or queen), wKQd7-bK.tbl (possible x of black queen by d6xe7) and wKQc7-bK.tbl (possible x of black queen by d6xc7).

Some of these can be pruned. If we're looking for a forced win by white, we can omit the rarer tables and treat any move into them as a forced win for black. If we can still force a win for white, we know that it can be done without moving into any missing table. This might result in some obviously won positions being reported as undecided.

File format is designed to be mmap'ed into the program's memory space; it can be compressed with gzip for transport.

File looks like an array [64][64]...[64][2]. There are as many [64]'s as mobile pieces, and correspond to them in the order listed in the filename, so the first [64] is always white's king. The [2] determines whose move it is - white to play (0) or black to play (1).

Each entry in the array is a four-byte structure:

struct {
	unsigned char	movecnt;
	unsigned char	white_wins_moves;
	unsigned char	black_wins_moves;
	unsigned char	draw_moves;
}

We init by running through the array, flagging illegal positions (all one bits, maybe), flagging positions that are checkmates for one side or the other as won but 'unpropagated' (how?), flagging stalemates as drawn but 'unpropagated' (how?) and otherwise computing the number of moves away from this position, storing that number in movecnt and setting the other fields to zero.

Now we run through the table, looking for 'unpropagated' positions and propagating them. This means backtracking one half move. If the position is black to play and is won for white (or vice versa), then we back up to every position that could have gotten here by one move (white's) and flag that position won for white and 'unpropagated'. If the position is white to play and is won for white (or vice versa), then we back up to every position that could get here by one move (black's), decrement movecnt by one and increment its white_wins_moves by one. If its movecnt is now zero, we evaluate it. It won't have any black_wins_moves (because it would have been flagged immediately won for black). So its moves are all either draws or wins for white. If there are no draws (only forced wins for white), we flag it as won for white and 'unpropagated'. Otherwise, we flag it as drawn and 'unpropagated'. If we're back propagating a draw, we'll be incrementing draw_moves.

And I skipped a step. The first step after initialization is to run through all the tables this one depends on, and back propagate from those positions (all marked either won for one side or drawn) to the current table.

Now we just keep running through the table, finding entries marked 'unpropagated', propagating them and marking them 'propagated'.

Finally, everything left should be the positions that will be drawn by repetition with best play from both sides, and should be flagged as such.

It would seem that this algorithm will avoid draws by repetition because it will always make forward progress if possible, except in very long winded positions in something like a three knights endgame.

Finally, we'd like the positions to be flagged not only won, lost, or drawn, but also with the number of moves required for a win. This seems to require a modification to the basic algorithm, since we can't just flag a move as won, but maybe not. If we process all the won positions first, then everything flagged will be a mate in one. Then we process all the mates in one; everything flagged will be a mate in two, etc.

So, we really don't need the four-byte structure. We don't need a 'mover_wins_moves' field, because if we find even a single move where the mover wins, we're done with this position. We need 'movecnt', 'opponent_wins_moves', and 'draw_moves'. We could lose one of these if we re-calculate the number of moves available in this position. I think the quickest way to do this is to scan the table for all possibles movements of the mobile pieces and see if the positions are marked invalid or not. Looks like a space-vs-speed tradeoff.

So, we could get down to a two-byte structure.

struct {
	unsigned char	movecnt;
	unsigned char	opponent_wins_moves;
}

movecnt's high-order bit could be reserved for the 'propagated' flag, which leaves room for 127 possible moves. This seems OK. 3Q+K would have at most 92 moves available to them.

Once 'propagated' is set, the meaning of the structure changes. Now we have two more bits indicating:

	00 - draw
	01 - win for white
	10 - win for black
	11 - invalid move

The remaining 13 bits can store a 'mate in' count, up to 8192! We should add another flag bit to indicate if the 'mate in' count is total moves or just to get to the next table.

Probably best to keep our program flexible by allowing for either four-byte or two-byte format to be used. Maybe different file extensions, or leave room for a header at the beginning of the file to indicate which format we use. Let's use a 256 byte header, put a version/format field in the first four bytes (ascii) and leave the remaining 252 bytes (for now) to double-check the file name, indicate that processing has been completed and we don't have corrupted data, text string to describe how the file was built, indicate which file dependencies were satisfied by actual files (and maybe their MD5 checksums) and which were pruned as forced wins or draws, and an MD5 of the rest of the file.

Have to see how gzip does, or might want a more compressed format for transport.

Could dump the move count and get a 2-bit-per-position format, but that's dangerous if we don't store the moves themselves, because then we would be moving in circles. This would only be good for transport to a 'slave' program computing another table, but we still wouldn't have exact move counts (couldn't tell if we should head for one move or another first in the next table).

.tbl for 'full' (maybe 2-byte) format
.tbc for 'compact' (2-bit) format - 1/8 size of full format

Compact format also has the disadvantage of not being able to convince people with a full move sequence, but this might not be a factor for any but the strangest cases (because we can usually figure out the move sequence from the compact format)

What tablebases to build?

all possible three- and four-piece tables are fundamental for more complex ones

an uncompressed two-byte four-piece table will be 64MB, so a complete set of all 30 of four-piece-ers will take up about 2GB (uncompressed)

wKQ-bK
wKR-bK
wKB-bK (building this and next one both checks program and avoids draws)
wKN-bK
wKP-bK (put this in its own table rather than 64 8K or 16K files?)
wKQ-bKQ
wKQ-bKR
wKQ-bKB
wKQ-bKN
wKQ-bKP (ditto for all these four-piece tables with pawns)
wKR-bKR
wKR-bKB
wKR-bKN
wKR-bKP
wKB-bKB (should handle both same color and different color bishops OK)
wKB-bKN
wKB-bKP
wKN-bKN
wKN-bKP
wKP-bKP
wKQQ-bK (some of these seem silly)
wKQR-bK
wKQB-bK
wKQN-bK
wKQP-bK
wKRR-bK
wKRB-bK
wKRN-bK
wKRP-bK
wKBB-bK (but some are important, for sure!)
wKBN-bK
wKBP-bK
wKNN-bK
wKNP-bK
wKPP-bK

Like an “applet” running on a client or a “servlet” running on a server, a “cachelet” runs on a cache. Data items have cachelets (to control their caching) associated with them. When a cache considers caching a data item, it downloads the cachelet, which then manages the cached data associated with it. Multiple cachelets can be running on the same cache, each managing a different set of data. Cachelets are untrusted, running in a Java VM on a foreign host.

Initially, when data is put into a system on a server, a cachelet is provided to manage it. So there’s always at least one copy of the data’s cachelet – the copy managing the original data on the origin server. Such a cachelet would be ‘nailed up’ – it would never get purged from its “cache”. Also, its “cached data” would take the form of files provided by the author containing the data itself. Ideally, we’d like this cachelet to be identical to all the others (i.e, no need for a special servlet), so the cachelet API should be built so that a file in the underlying filesystem can be treated as cached data.

Other caches might want a copy, too. The basic idea is that when a cachelet is going to transmit data it multicasts a notification to any interested caches. So how does a cache get “interested”? Well, the number one way is that it is located in physical (in a network sense) proximity to the path the data is going to take through the network. With this in mind, I can think of two possible models. The first uses a directed, scoped multicast, that could be implemented using a combination of Lightweight Multicast (LWM) and traditional multicast. When a transfer is about to begin, the source transmits a directed multicast to the destination with an annoucement of this. This can be formulated as a packet addressed to an “all caches” multicast address, along with an LWM header option directed at the unicast destination. Caches can then subscribe to this multicast address within some kind of radius or domain. As this a directed multicast passes along the source-to-destination path, any caches along the way subscribed to the “all caches” address will receive a copy of the notification.

Of course, this presupposes a capability (directed multicast) that doesn’t exist (yet). How can we achieve cache rendezvous without working multicast? It’s a hack, but we can expect data requests to be sent with the IP Record Route option, so the transmitting cachelet will have at least an “advisory route” about the path the data will be taking, which can be supplemented with local routing info and something like traceroute. Armed with this information, the transmitting cachelet does a series of DNS lookups, in in-addr.arpa (or part of the DNS tree structured like in-addr.arpa), to find caches that have registered (using dynamic DNS) their interest in a particular CIDR block. Now we have addresses of those caches that have expressed interest in any of the addresses along the path to the destination. We transmit a notification of the upcoming transfer to those caches, giving them the opportunity to subscribe to the (multicast) transfer, and proceed to transmit.

Having received a notification, a cache has to decide whether to cache the data. The first step is to download the cachelet. Presumably, this will almost always happen. Why? Because the cachelets will be designed to be flexible, so a single cachelet can manage many similar data feeds. That means you really only need a small number of cachelets in your entire network. The multicast announcement of the upcoming data transfer can include the URL of the cachelet. So once the cache’s got the cachelet, it has to…

1. initialize the cachelet

   an ISP might want to influence the caching decisions of its subscribers

   the simplest way to do this is for the ISP to provide a cachelet to run on its subscriber’s caches

   thus, we’ll need some kind of inter-cachelet communications standard to allow the ISP-provide cachelet to influence its fellows

   at the very least, upon initializing, the cachelet should multicast to an all-local-cachelets address, announcing its presence to other cachelets on the same cache

   no, our current multicast scheme can’t really handle this. Basically, we need multicast ports instead of multicast host addresses. We can punt on this and let it find out about other local cachelets because they’ve registered themselves (and their port numbers) in DNS

   it may also want to subscribe to multicast channels, or register itself using dynamic DNS

   consider cryptographic authentication of the cachelet

   might want to have it reviewed by a central authority

2. considering a new cache item

   a notification has been received of a current or near-future transfer

   do we want to cache it?

   we know: what it is (URL), where it will be (advisory route), and when it will be there (some kind of timestamp)

   cachelet may need to do some network chit-chat (i.e, download some information specific to this particular data item) before it can fully advise the host

   cachelet finally does advise the host: how badly do we want to cache this item (on a 0-255 scale, perhaps), how much space will probably be required to cache this item

   how does the host compare advise from different cachelets?

   it can measure how much data is being transfered how often from which cache items and use this as a baseline to compare advise

3. Cacheing a data item

   The transfer itself, ideally, should be multicast. We’re transmitting to, perhaps, a client as well as several caches. This is inherently multicast, but again, we can’t expect this to work in the current Internet. Probably we’ll transmit to the (closest?) cache that wants a copy, and it will have to turn around and relay the data to the client or other caches. If the client requested the data from the origin server using TCP, we’re got a real problem here. If we’re using HTTP, I guess the origin server can redirect the client to the cache (using “305 Use Proxy”, but this is for a single request only), but what we really want is something like TCP-over-multicast, some kind of reliable stream service which can deliver to multiple destinations – both the client and the cache. Again, beyond the capability of the contemporary Internet. If we redirect to the cache, there’s a denial of service issue here.

   We really need to rethink HTTP caching, probably with an eye towards using a local Java cache capable of caching, or at least matching, a entire block of URLs, possibily using regular expressions and a sub-cachelet scheme.

4. serving a data item

   cachelet gets a request from a data transfer

   the request goes to _the_cachelet_, not the cache

   the cachelet should ask the cache host if it’s OK to serve the data now (based on policy and things like host/network load) needs to be part of the cache/cachelet API

   cachelet might want to know general policy from the cache, so it can decide if it wants to advertise the ability to serve data at all

   cachelet might chit-chat over the network, then uses its high-speed API to begin the transfer

   the cache host itself does almost nothing other than assist the transfer

5. cachelet wants to preemptively cache, i.e, initiate its own transfer

   cachelet advises the host: how badly we want to cache, how much space

   might want to do multiple advisories – we want to cache X1 MB at priority Y1, and an additional X2 MB at (lower) priority Y2

6. cachelet wants to change its advice on previously cached data
7. host wants to clean out the cache

   maybe host keeps track of advice (priority) on cached data, so it already knows what it wants to clean out

   or maybe host uses a 0-255 priority to tell the cachelet how badly it wants to clean up the cache, and the cachelet then replies with the amount of data it’s willing to clean out at that priority

   this priority could be the same as the caching priority. That way, when a cachelet advices the host “I want to cache X MB of data at priority Y” and the host doesn’t have X MB free, it asks the other cachelets how much space they are willing to free up for data at priority Y

8. host is booting the cachelet off the cache

   this can happen at any time, but it’d be nice if the cache advised the cachelet and gave it a chance to clean up

Trying to get this cachelet scheme (or any caching scheme) working with the existing web architecture will be difficult. The web was never designed to cache, and its current design, particularly the way dynamic content is done, is very hostile to caching. Since you can’t cache the programs that produce the dynamic content, you can’t cache the dynamic content at all, and this kills it. The only way to cache the hordes of dynamic content running around the web is to convince web designers to write their dynamic content into cachelets. We can do this without overloading our caches if we specify that HTML dynamic content will only be served to the local host, thus ensuring that the computational cost is bourne not by an ISP’s cache but by the client’s local cache. Of course, there will have to be a significant installed base of Java caches before web designers will do this.

So I propose an end-around. Let’s build a _video_ client (see my other blog posting about this) designed to use cachelet-based caches to cache the video feeds. Nobody’s doing on-demand video on the Internet right now, so we’ve got the architecture to ourselves and can do it however we want. If we can get it working well, then hopefully everybody comes running to it as the next killer app (ohh, ahh, video over the internet), we start get cachelet-based video caches deployed widely, the web guys want to get in on the act, and we say, “why yes, it can cache HTML, you just need to do this…”

SCENARIOS

1. client downloading a new (video) item using lightweight multicast (LWM)
   1. client downloads applet
   2. applet wants a data transfer
   3. applet does a DNS lookup to find existing caches for data, and picks one based on nearest routing/closest match
   4. applet sends foreign cachelet a download request
   5. foreign cachelet multicasts a notification that download is commencing – possibly using DNS to lookup the IP addresses along the route to the applet and see if any caches have registered an interest in those addresses
   6. local cachelet picks up notification, decides it wants to cache, and subscribes to the multicast (along with the applet)
   7. transfer begins – both applet and local cachelet receiving
   8. local cachelet sends DNS update announcing that it can now serve the item
   9. applet gets DNS notification of “new” cache available and decides to switch to local cachelet because it’s closer
   10. RTP handoff
   11. foreign cachelet sees that no non-cachelets are left subscribed
   12. foreign cachelet accelerates the download

   At this point, since the cachelets are just talking to each other, they can increase the speed past real-time. This lets them probe the connection to see how much bandwidth it can support. If you start losing data, you can throttle back and retransmit(!) since you’re in the “future” as far as the user is concerned. You can dynamically pick a video resolution to suit your link capacity in this way. The applet/cachelet could be designed to anticipate future downloads, i.e, if the user is looking at menu X, then download the first second of each of the five different feeds linked to from that menu. A completely different applet/cachelet pair could be used for realtime feeds that couldn’t do this. A completely different applet/cachelet pair could be used for files and HTML that can’t tolerate data loss like RTP video.

   Of course, LWM is pie in the sky, so we need a fall back solution…

2. client downloading a new (video) item using unicast
   1. client downloads applet
   2. applet wants a data transfer
   3. applet does a DNS lookup to find existing caches for data, and picks one based on nearest routing/closest match
   4. applet sends foreign cachelet a download request
   5. foreign cachelet unicasts notifications that download is commencing – possibly using DNS to lookup the IP addresses along the route to the applet and see if any caches have registered an interest in those addresses …and delays beginning the download for local cache notification…
   6. local cachelet picks up notification, decides it wants to cache, and notifies the foreign cachelet
   7. foreign cachelet notifies applet that it’s local cache will have the data
   8. transfer begins – only local cachelet receiving via unicast
   9. applet requests transfer from local cachelet
   10. local cachelet sends DNS update announcing that it can now serve the item (maybe – or maybe policy is that local caches only serve the local host)
   11. foreign cachelet accelerates the download

   Almost all of this can be implemented in Java using the applets and the cachelets. Only step (a) is performed using something like HTTP, and step (j) requires a standard cache-cachelet API. Otherwise, it’s all applet/cachelet and cachelet/cachelet communications (with standard stuff like DNS and RTP thrown in), and both applet and cachelet can be easily changed by the data author.

3. client downloading conventional (static) web page
   1. a standard HTTP cachelet has been distributed with the cache
   2. client web browser is set to use local cachelet as HTTP cache
   3. web browser wants a web page, so it queries local cache
   4. cachelet doesn’t have the page in its local cache
   5. cachelet does a DNS lookup to find existing caches for this page, and picks one based on nearest routing/closest match
   6. cachelet sends foreign cachelet a download request
   7. local cachelet downloads (how? probably TCP to foreign cachelet) a copy of the page
   8. local cachelet notifies DNS via dynamic update that it’s got a copy of the page
   9. local cachelet generates the web page for the browser
4. client downloading a dynamic HTML item using unicast
   1. a standard HTTP cachelet has been distributed with the cache
   2. client web browser is set to use local cachelet as HTTP cache
   3. web browser wants a web page, so it queries local cache
   4. cachelet doesn’t have the page in its local cache
   5. cachelet does a DNS lookup to find existing caches for this page, and picks one based on nearest routing/closest match
   6. cachelet sends foreign cachelet a download request
   7. foreign cachelet indicates in reply that a custom cachelet is used to serve content for this URL
   8. local cachelet downloads (how? probably TCP to foreign cachelet) a copy of the custom cachelet
   9. custom cachelet (local copy) notifies DNS via dynamic update that it’s running on this new cache
   10. custom cachelet (local copy) generates the web page for the browser

   We now have multiple HTML cachelets ‘slaved’ off a parent cachelet responsible for handling all browser interactions. Does Java provide us an easy way to hand off TCP connections from one cachelet to another?

   Also, now we are faced with the problem of cache discovery for web pages over DNS. Doing this right will make sure the rest of our scheme scales. For starters, consider some like cnn.com. Having a single DNS server listing all the caches with a copy of even just the home page would be crazy. What we really want to know is just those copies ‘nearby’ is a network sense. Nearby to what? Well, the DNS request includes the IP source address of the requester, so I’d say nearby the requesting IP address.

   For starters, consider the case where the DNS server(s) have complete information about where everything is cached. Except for the largest and most widely cached sites, this might be a perfectly workable model. When the DNS server sees that it can’t return a complete list of resource records in a single response packet, it sorts them according to which are closest to the requesting IP address and returns only the top hundred or so of them. The DNS server thus needs to have some routing information to sort the addresses (or just sort them by longest match IP address prefixes), but this seems fine. Also you’ll want redundant DNS servers, so a distributed database seems to be called for, but I’ve discussed how to do that in another blog.

   For the most popular sites, though, the shear number of entries on DNS servers in such a scheme would become prohibitive. But this case can be optimized away behind the scene – a DNS server responsible for only a limited area of the network would only need to know of cache entries roughly within that area. The behavior to the client should be _exactly_the_same_ – a set of resource records sorted to be ‘close’ to the requesting IP address. So we can leave the DNS protocol alone and study ways to build more optimized servers to handle this somewhat special case.

   In fact, we’ve already got a way to do this. The Java caches themselves can answer DNS queries. All that’s needed is a new type of cachelet that manages cached DNS resource records and answers DNS queries. A natural extension of the DNS ‘SRV’ resource record would allow DNS servers to operate on arbitrary port numbers, not just 53. So a DNS cachelet could bind to a random UDP port and handle DNS queries. We do need to make sure the cachelets can manage a distributed database as I described in the other blog. The main change required here is to make sure the DNS resolvers (both clients and recursive servers) can handle DNS servers on non-standard ports.

   OTHER SCENARIOS

5. ISP cache also wants a copy of something (multicast case)
6. ISP cache also wants a copy of something (unicast case)

In summary, we started trying to fix up the web’s caching scheme and have ended up with a model that seems like it can cache not only HTML and video, but also dynamic content and DNS. Probably it could do a lot more. Probably if we deployed Java caches widely on the network they’d become quite popular for all kinds of things I haven’t thought of. But if we put together a design that can handle web, video, dynamic content, and DNS without having to kludge any one of them, then it probably will be flexible enough to handle most future applications as well.

OTHER

Cachelets need some high-speed support services from the underlying host in order to perform some operations that can’t be done efficiently in Java. These can be provided by a Java Native Interface (JNI) add-on, and primarily include both sending and receiving RTP streams to/from a disk cache. The cachelet should be able to begin an RTP transfer (send or recv) and just let it proceed in background. For a receive stream, cachelet needs to see timestamps and sequence numbers on the received packets, possibily along with local timestamps for when packet were received, to determine if data is missing as well as calculating network jitter. RTP transmits might only include a subset of data from a received stream (let’s say the applet wants to fast forward through a cached video stream), and might proceed at a different rate from the received stream, so the cachelet needs to be able to set (and change) the base frequency for interpreting RTP timestamps. Also, we might be transmitting just ahead of a receive, so the cachelet should be able to set transmits on data that doesn’t exist yet, in the expectation that it will be there when needed. To allow cache repair, applet might request some out-of-band transfers of individual packets via UDP and can insert them into the cache, so the cachelet probably needs to be able to interact with data in the cache, but this should be discouraged for performance reasons. Also, to allow flexibility in caching, TCP streams should be supported. If you can’t get RTP through a firewall, you might want to receive data on a TCP stream, then transmit it on an RTP stream, so this should be supported.