Research Dead Ends

Not every experiment yields a product released to the general public. Here are some of the things I worked on that didn't see the light of day.

Internet Access Cartridge for Game Consoles

IAs the mid-1990s approached, the IBM Global Network was supposedly looking for opportunities to acquire more customers. This was the era of dial-up and walled gardens like America Online, Compuserve, and Prodigy had been the vendor of choice for many people. With rise of backbones that bypassed the NSFNET acceptable use policy, Earthlink, AT&T, Sprint, etc. were able to provide direct access to the Internet to residential customers and small businesses. A customer normally required a PC with a modem; the use of generic hardware provided very little barrier to inhibit a customer from selecting one Internet Service Provider over another.

IBM Research had lead the effort to build out the NSFNET and formed ANS with MCI. ANS ended up devoting much of their resources to deploying modem banks for American Online at points-of-presence across the country. To address the problem of getting customers for IBM Global Network, we proposed an Internet Access Cartridge for 16-bit game consoles (like the Super Nintendo Entertainment System or Sega Genesis), with a target price of less than $100. It would have a modem, a Point-to-Point protocol stack and DRAGONS Display Manager as the dedicated application. DRAGONS Display Managers provided a graphic user interface capability for applications running within a DRAGONS infrastructure and were first fielded commercial in the 9076 SP1. Each instance of a DRAGONS Display Manager appeared as an object within the transparently distributed object-oriented infrastructure provided by DRAGONS Data Engines and provided facilities similar in concept to an X11 server, but at a much higher abstraction level; closer to the granularity of Motif rather than the primitives of the X11 client library. Widgets like menu bars and scrolled windows were available as well as graphics primitives like lines, bitmaps, GIF and JPEG images. Graphic elements could have callbacks associated with them, so clicking on a line could result in a command being invoked or message being sent back to an object within the distributed infrastructure. Issues like repainting windows that were exposed, figuring out if the mouse was positioned on top of a line, etc. were handled by the DRAGONS Display Manager core, freeing programmers to ignore the complexity of those implementation details. Commands could be entered by the user, loaded from local files or (most usefully) transmitted by DRAGONS-based applications. Some example ALIAS commands to define operator command lines:

ALIAS browser SEND_ARGS createObject $RootObject ObjectBrowser
ALIAS xgmon EXEC launchApp /usr/lpp/xgmon/bin/xgmfe+ -m "3"
ALIAS test10 DRAW_SCALED_GIF /MainWindow earth.gif 1 1 1 1 500 500 5
ALIAS dumpPS SEND_ARGS createObject $RootObject DumpVirtualConsoleToFilter "Plot for" "VC_PSfilter" ""
ALIAS flashNode SEND_ARGS createObject $RootObject SP1PollCommand flashNode
Sample OIL code from the DRAGONS implementation of Distributed Starship:
StarshipGUI:activateGUI(oid obj)
        string          parent;
        int             rc;
        assoc(any)      emptyAssoc;
        string          cmdString;

iconNames[RACE_FEDERATION] = "federation.icon"; iconNames[RACE_KLINGON] = "klingon.icon"; iconNames[RACE_ROMULAN] = "romulan.icon"; iconNames[RACE_THOLIAN] = "tholian.icon"; iconNames[RACE_UNKNOWN] = "dot.icon"; iconNames[RACE_KZINTI] = "kzinti.icon"; iconNames[RACE_GORN] = "gorn.icon";
starship = obj; attributes = send "getAttributes" to starship; shipName = attributes["name"]; write_cout("activate ", shipName, "\n");
appName = formatIntoString("/Controls:%s", shipName); parent = appName;
cmdTotal = 0; dCmd[0] = DM_CMD_SEQUENCE; dCmd[1] = emptyArray;
cmd = emptyArray; cmd[0] = DM_CMD_CREATE_APP_SHELL; cmd[1] = parent; if (commandsEnabled) { cmd[2] = formatIntoString("%s Bridge Controls", shipName); } else { cmd[2] = formatIntoString("View from %s Bridge", shipName); } cmd[3] = 900; cmd[4] = 700; cmd[5] = shipName; dCmd[1][cmdTotal] = cmd; cmdTotal += 1;
cmd = emptyArray; cmd[0] = DM_CMD_CREATE_AND_MANAGE; cmd[1] = parent; cmd[2] = "Form"; cmd[3] = "form"; dCmd[1][cmdTotal] = cmd; cmdTotal += 1;
parent += "/form";
cmd = emptyArray; cmd[0] = "CHANGE_STATE"; cmd[1] = parent; cmd[2] = "colors"; cmd[3] = "black"; cmd[4] = "grey"; dCmd[1][cmdTotal] = cmd; cmdTotal += 1;
call "createMenuBar"(parent); call "createShieldDisplay"(parent); call "createPhaserDisplay"(parent); call "createTorpedoeDisplay"(parent); call "createShortRangeDisplay"(parent); call "createLongRangeDisplay"(parent); call "createCourseDisplay"(parent); call "createStatusDisplay"(parent); call "createTargetDisplay"(parent); call "createMessageDisplay"(parent);
cmd = emptyArray; cmd[0] = "REALIZE"; cmd[1] = appName; dCmd[1][cmdTotal] = cmd; cmdTotal += 1;
cmdString = encode_type(dCmd); rc = send "processEncodedCommand"(cmdString) to dispMgr;
send "notifyOnConnectionLoss"(thisObject) to dispMgr from nil;
send "registerDisplay"(thisObject) to slaveObj;
// force initial drawing for timelines... send "updateDisplays"(emptyAssoc) to thisObject; }

We had Unix-based implementations of the DRAGONS Display Manager that were initially based upon Motif and then ported to be based upon Qt so that Microsoft Windows could be supported with a native look-and-feel. For cost savings, ROMs were to be used in the Internet Acess Cartridge rather than EPROMs, so the capabilities would have been set in stone once the cartridges were manufactured. This is not a choice one would want to make if there was a fiscally feasible alternative. Having only the rendering facilities hard-coded meant that the parsing of HTML would be handled by servers at the ISP; as HTML evolved, only the server-side code would need be adjusted. New image formats, like PNG, could be handled by converting into GIF or JPEG. An example that arose during the design phase was the use of frames, an HTML element that had not been in use from the very beginning. That evolution would be handled by upgrades in the HTML parsing and layout on the server side. Since an Internet Access Cartridge would only work with infrastructure provided by IBM Global Services, it created an immediate barrier for a customer to change vendors thus creating an opportunity for lock-in. With the extensive installed base of game consoles (e.g., around 40 million apiece for the SNES and Genesis) and the relatively low target cost of less than $100, it could create customers out of households that did not have a computer.

The objection that was used to prevent pursuing this implementation was that it could create too much customer demand, requiring IBM Global Services to build out a large population of modem banks that would ultimately be unused once there was a transition away from dial-up connections. In response, we noted that unlike a normal dial-up offering, the maximum number of users was perhaps the only thing that could be controlled: simply manufacture a predetermined number of cartridges and you were guaranteed to never have more than that number of customers. Thus it was a strange objection. Cost or no perceived market interest would be great reasons to not pursue a venture, but too many potential customers when you can limit them simply by not making devices available? Not such a great reason. Ultimately, IBM Global Services was sold off to AT&T in 1998 and, in retrospect, one suspects the marching orders got changed: rather than obtain new residential and small office business, the goal was to get out of the business entirely.

In the outside world, WebTV pursued a similar idea using their own standalone box that sold for more than $300 in 1996.

VLAN Configuration using Genetic Algorithms

When hardware supporting Virtual LANs appeared, it wasn't immediately obvious how active management could improve their deployment. In our local infrastructure, a long-standing concern was the impact of broadcasts: a host would issue a broadcast and, if the broadcast was permitted to propagate off of the local LAN segment, it could interrupt thousands of machines residing within the building. If those thousands of machines all engaged in the same behavior, any given host would be busy being interrupted by a constant stream of broadcasts which were of zero interest. As an experiment, we used genetic algorithms to determine "optimal" groupings of hosts based on their communication patterns. Our initial goal was to evaluate these communication patterns and reconfigure the VLANs on a daily basis. We certainly did not set a high bar for performance: 12 hours of computation would have still been viable as a solution.

Quoting from the Protocol And Design section on the Wikipedia page describing VLANs:

Early network designers often configured VLANs with the aim of reducing the size of the collision domain in a large single Ethernet segment and thus improving performance. When Ethernet switches made this a non-issue (because each switch port is a collision domain), attention turned to reducing the size of the broadcast domain at the MAC layer.

With this context, it's easy to why we explored minimizing the amount of unwanted traffic seen by a host. The basic idea was that if two machines did not chat with each other, they should not be grouped on the same VLAN. A standard VLAN protocol makes provision for a finite number of distinct VLAN groups, but the limits are typically sufficiently generous for real-world deployments; for example, 802.1Q permits 4094 groups to be defined. A possible grouping of hosts to VLANs was evaluated using an objective function which:

A host which sent no broadcasts would be a candidate for assignment to almost any group since it had very little negative contribution. While choosing representations and objective functions can be an art, it's clear that the choices made in this implementation were arguably embarrassingly obvious.

The total possible groupings can be somewhat large, so exhaustively evaluating all combinations was assumed to be a nontrivial task. Searching a solution space in a quest for the "best" solution is one of the primary uses of genetic algorithms; rather than exhaustively try all possible combinations, the search is directed via heuristics towards productive combinations. For our experiment with VLAN configuration, we viewed a relative position on the "chromosome" as representing a host and the value of the "allele" at that position indicated the VLAN group to which the host would belong. For each evaluation step, we used historical data that indicated the amount of unicast traffic from between nodes (an N-by-N matrix) and the amount of broadcast traffic generated by each node. Note that perfection was not required: a less than perfectly optimal result still had utility. Communication patterns amongst nodes were expected to be similar from day to day, allowing the pool of chromosomes to be retained from the prior day's run and provide a high-quality initial configuration.

For initial testing, we fed the system artificial data which was intentionally constructed to have a particular "best" scenario. We measured to see if that solution would be found and how long it took. On the positive side of the ledger, the hoped-for solution was found and within 30 seconds. On the negative side...the solution was found within 30 seconds. When "hard" things appear "easy" they are readily devalued. Ultimately, VLAN-capable switches became platforms capable of supporting nontrivial firmware which could locally implement decision logic. All-stations broadcasts gave way to more prevalent usage of multicast, which allowed finer control of broadcast domains. Using the dynamic reconfiguration facilities of a VLAN to minimize useless broadcast traffic became an evolutionary dead-end (attempted pun intentional). Instead, VLANs became critically important in the arena of on-demand provisioning of servers: a rack of nodes could be assigned to a customer's existing pool of machines and become visible on the virtual LAN without any need to physically recable hosts and switches. The servers were also invisible to other customers, which prevented one customer from running a network sniffer application and gaining visibility into the operations of a different customer.

Are genetic algorithms useless? David E. Goldberg famously implemented a control system for gas pipelines in the course of his 1983 PhD dissertation and John Holland enthusiastically promoted it as an illustration of perhaps the best result that had been achieved by the end of the 1980s. The approach taken in such control systems was to implement a classifer system that manipulated a set of if-then rules encoded as "chromosomes". A variety of inputs would be available to provide information for the rules matching sytem, such as the reading of a pressure sensor, time of day, temperature, etc. A set of outputs would be provided to allow the rules to effect change on the sytem being controlled, like activating a compressor. The simulation would run in series of discrete time steps and the objective function would be used to evaluate the "goodness" of the current state. The initial starting condition is a pool of random bitstrings, which are literally gibberish: the system has to be trained over many generations for it to discard nonsense and counterproductive rules and retain or generate useful rules that yield good behavior. Only after the system has built up a pool of high-quality rules could one conceive of using them to control elements in the real world and it is doubtful that one would allow the evolutionary logic to remain active: in simulation, it's OK to have something blow up virtually, but it would be a really bad idea to have that occur in the real-world. The conclusion that it was an ineffective rule might be the same in both environments, but discovering that fact costs a lot more in the real-world.

One of the more interesting results was that the pipeline control system could learn to deal with leaks even though the control system was not provided an input dedicated to indicate that condition. It was thus able to operate effectively in the presence of incomplete information. One does not have to make available every possible input "sensor" and there can be some distinct advantages to not doing so as it restricts the size of the search space. On the other hand, there needs to be enough information available for patterns to be discerned.