// The Song Remains The Same

A man who carries a cat by the tail learns something he can learn in no other way.

– Mark Twain

Data Mining is defined as:

“the process of extracting patterns from data. “

Any of these groups of data has a set of examples or instances that can be grouped together in a binary file, a text file, or a database and examined electronically by a data miner and their tools. Some people seek to gain knowledge about the data from data mining, yet others take the instances and make sets of rules about how the data works, or even more complicated mathematical models that describe very hard to see trends. But how do we actually “mine” this data? How can we break down this process of pattern extraction into more discrete steps?

…

The Process of Data Mining

The process of data mining has 4 major components used for knowledge construction:

• Concepts
• Examples
• Instances
• Attributes

where each of these components work together to form a process where we condense patterns from the vapor of nuances in our data. These patterns can later be used as a valuable resource.

…

Concepts

A concept is the thing to be learned, what we are after, the model of the structural pattern within the data. Some examples of concepts are

• abnormal vs normal system operation
• the canonical “Bell, Funnel, Cylinder” dataset - understanding the difference between these shapes in noisy timeseries data
• recognizing how similar or different two peices of information are
• the type of books I would like to be shown based on my past purchases on amazon (recommendation engines)

The reader can think of concepts in the same way they learn a “concept” themselves — a topic that we study and look at descriptions, examples, and information about in order to get a better understanding of.

…

Examples

Examples are defined as:

• inputs to a learning scheme ( clustering, classification, association, etc )
• a set of instances ( described below )
• a dataset ( example: The waveform dataset at the UCI Dataset repository )

Examples are a rather restricted form of input that we use to educate our system with. We use examples as input data that we know correspond to concepts we want to our system to learn.

…

Instances

Instances (which are specific types of examples) are records in database or text file. Examples of instances include:

• recorded symptoms of patients as they enter an emergency room as well as what type of ailment they actually had
• a window of timeseries data from a temperature sensor
• a line in a log file

Preparing instances for the data mining process usually takes the bulk of our time.

…

Attributes

Attributes are the fields in the record/instance that contain the actual data. Each attribute can have different types of data in it. Types include

• Numeric - Integers, Longs, any type of numeric data
• Nominal - distinct symbols generally serving as labels or names. (ex: “sunny”, “overcast”, “rainy” )
• Ordinal - impose order on values yet not distance between the values is defined ( example: “hot” > “mild” > “cold” )
• Interval - are not only ordered but measured in fixed and equal units (example: temperature, or year).
• Ratio - quantities are ones for which the measurement defines a zero point (example: distance) and are treated as real numbers.

No relation is implied among nominal values, but equality tests can be performed. Also, the distinction between nominal and ordinal values are not always clear.
The question beyond “what are the components of data mining?” is “how do we use these concepts?”. In the following section, we take a very general look at how we can use the above components to build a process in which we extract patterns from collections of data.

…

Putting the Components Together

In order to learn concepts, we need examples; These examples are made up of instances which were selected to show a specific piece of data corresponding to a class or type. If a system that is looking for patterns sees similar instances resulting in the same output again and again, the system may conclude that this general class of instance corresponds to this outcome. It could be said that the system has now “learned” this “concept”.

An interesting example of this is illustrated with a classifier; A classifier is an system that takes input data and predicts the input data’s class or type. In this example scenario we show a classifier 2 sets of timeseries data:

• A set of timeseries data that shows operation of a wind turbine under normal operation.
• A seperate set of timeseries data that shows the wind turbine operating under duress or abnormally

With proper training, our classifier can learn the difference and classify future wind turbine timeseries data it hasnt seen before. Of course these classifiers aren’t perfect, but they can be trained to get far more answers right rather than wrong. To see an example of a similar classifier in real life, check out the timeseries classifier open sourced in the openPDC project. In future articles we’ll talk more about how the openPDC timeseries classifier is built, trained, and classifies terabytes of timeseries data. For now, let’s move on to some general ideas about how we build which datasets which power our data mining processes.

…

Dataset Construction

Beyond the above components, to construct a dataset, we have to do 4 things:

• Gather the data - (ex: by hand, mechanical turk, ETL)
• Review the content and context of the data - (ex: open data in excel, graph some values)
• Verify, Validate, and Plug the data - (does the data make sense? are values in bounds?)
• Get to know the data - (get comfortable with this type of data)

When we gather our data, we have to ask questions like

• Where does the data come from?
• Did it come from a single source or from multiple sources?
• Is it clean data? Are their missing or bad values in the instances?

The content of the data gathered can vary greatly, and has to be checked thoroughly to protect against invalid data. If our data is bad or noisy, our results can be rendered useless or even worse, dangerous. Noisy data can have decimal places off, can have missing data, missing attributes, or be recorded in different formats or types in the same attribute field.

The data cleansing process can easily take up the bulk of a data miner’s time since there can be millions of records to review. Getting to know the data takes time and much energy, but its results cannot be replaced. Many hours are generally expected to be invested in this process. Graphing a single attribute to look for any statistical outliers, taking the mean, and taking the standard deviation are some of the ways we can get to know the data.

Another important thing to consider is as we do get to know the data, we have access to many sensitive and private pieces of information. What is our responsibility in handling this data? In the next post on machine learning I’m going to take examine some of the implications of ethics in data mining.

…

Conclusion

Datamining is the process by which we extract patterns from data and store these patterns for later use. We’ve taken a look at the components of data mining and given a very broad description on the beginnings of how to mine this data. Although we know a little bit about the process of data mining, we need to know how to represent and store the patterns extracted during the process. In the next installment of this series, we’ll take a more in-depth look at how we model and represent the patterns, or knowledge, we have mined from our data.

…

References

To learn more about these topics in depth, please take a look at Ian Witten’s Data Mining book:
http://www.cs.waikato.ac.nz/~ml/weka/book.html

I love it when a plan comes together.

— Hannibal, The A-Team

Disclaimer: I’m a contributor on the openPDC and I work for TVA/NERC. These are my personal views and in no way espouse the opinion or position of my employer or the Federal government. These are simply my thoughts from an outside viewpoint on where I could see this open source project going and not necessarily any real roadmaps or internal plans.

Recently TVA and the NERC open sourced a key part of the “smartgrid” that deals with concentration, storage, and processing of transmission and generation phasor measurement unit (PMU) data. This project is referred to as the Open Phasor Data Concentrator (openPDC) and is housed at http://openpdc.codeplex.com where members of the power community (and interested enthusiasts) can examine or contribute to the project. From the website the project is described as:

The openPDC is a complete set of applications for processing streaming time-series data in real-time. Measured data is gathered with GPS-time from multiple input sources, time-sorted and provided to user defined actions, then dispersed to custom output destinations for archival.

The website goes on further to describe the project in more detail:

The open source phasor data concentrator (openPDC) is a system that can be used to process complex events and respond to dynamic changes in fast moving data. More specifically, the openPDC can process complex events that can be described as “time-stamped measured values”. These measured values are simply numeric quantities that have been acquired at a source device and are typically called points, signals, events, time-series values or measurements. Examples of measurements include temperature, voltage, vibration, location, luminosity and, of course, phasors. When a value gets measured, an exact timestamp is taken, typically using a GPS-clock for accuracy – the value, along with its timestamp, is then streamed to the openPDC where it can be “time-aligned” with other incoming measurements so that an action can then be taken on a complete slice of data that was all measured at the exact same moment in time.

The U.S. power grid is run by multiple private and government run power companies which must all work together in order to keep power flowing and downtime to a minimum. The openPDC allows a regional grid operator to collect PMU data from multiple sources and either archive it or forward it on to a larger concentration point. The NERC designated TVA as the official repository for the collection and archival of U.S. power grid PMU data (although currently only the eastern half is online). Given that large scale data warehousing and analysis is no mean feat, Hadoop was chosen as the architecture for the PMU data repository.

Hadoop is a framework for running applications on large clusters built of commodity hardware. Hadoop includes the Hadoop Distributed File System (HDFS) and the Map Reduce programming model. The openPDC project includes the necessary Hadoop components (InputFormat and RecordReader) to allow Hadoop to work directly with openPDC data points.

The openPDC collects data from around the US power grid for archival and analysis. The openPDC is designed to talk directly to PMU sensor devices and transmit it back to collection nodes. At collection nodes the data is archived in a binary format by the Historian (also included in the openPDC project). This archival format can then be used directly with Hadoop via the classes included in the openPDC project (Inputformat / RecordReader).

Hadoop works well for a project such as the openPDC in that:

• Its based on commodity hardware
• Its performance generally scales linearly with the size of the input data
• Its programming model Map Reduce is simple and robust
• It doesn’t lock a project into a proprietary system

The openPDC is really interesting from an engineering perspective in that it provides an open source “building block” for smart grid participants and researchers to work with to develop more layers of the smart grid. I look at the openPDC in the same role as Google’s Android platform in that it:

• Allows researchers to focus on research and not on implementing protocols
• Allows vendors to focus on a common building block
• Gives companies with less resources an opportunity to compete without having to “re-invent the wheel”
• Gives companies a way to collaborate on a common building block to drive improvement of their market

In addition to the obvious use cases within the smart grid, the openPDC is well suited to collect time-series data from just about any type of sensors. Once the proper adapters for the specific sensor is written, time series data could then be easily collected, concentrated, and archived for easy analysis in a Hadoop cluster. To me this seems like a very good collection and analysis framework to use with a system like a TinyOS mesh network. Complex distributed systems can be difficult to build from scratch and using building block components such as openPDC greatly lowers the overall cost of development.

Development overhead is greatly reduced with the openPDC just like Android can cut down development costs significantly for cell phone companies. In a similar way, Hadoop cuts down costs in that Hadoop is open source and an open platform. From a tax payer’s standpoint, Hadoop is really nice in that our Federal Government is using an open source alternative and saving your tax dollars. On top of that, a government entity is open sourcing a key piece of smart grid technology — the openPDC. I believe this is a unique situation where a government entity made extremely effective and intelligent use of resources that benefited society. Hopefully we’ll continue to see these type initiatives spring up in the future.

openPDC Coverage:

• http://www.chattanoogan.com/articles/article_160601.asp
• http://www.tva.gov/news/releases/octdec09/data_collection_software.htm
• http://forum.complexevents.com/viewtopic.php?f=17&t=217
• http://news.cnet.com/8301-13846_3-10393259-62.html?tag=mncol;title
• http://earth2tech.com/2009/11/10/the-google-android-of-the-smart-grid-openpdc/
• http://agilecat.wordpress.com/2009/11/17/overview-of-hadoop-conference-2009-in-japan-english-edition/
• http://econgreen.blogspot.com/2009/11/set-phasors-to-smart.html

�

Disclaimer: This is my personal opinion and in no way reflects the opinion of my employer.

Today parallel programming at the commodity level is a booming sector both from big tech standpoint and from a small grassroots “web 2.0″ standpoint; Most everyone who is connected to the internet has more data than they know what to do with. As I use Hadoop on a daily basis, recently I sat down and took a look at the two research papers [1,2] published by Microsoft on their competing platform “Dryad“. Given that I’ve heard some discussion informally comparing the two platforms, I decided to write up my own comparison. I’m going to state upfront that I have only seen Microsoft comparing Dryad against the Map Reduce model in general, and not specifically Hadoop itself. However, it seems like Dryad and Hadoop are going to at least have some overlap in userbase. Therefore I think its a worthwhile exercise to compare them — if only to help someone figure out which one is right for them. The major areas that I wanted to compare the two platforms on were:

• Processing Model
• Tools
• Storage
• Community
• Performance
• Cost

Hadoop employees the venerable Map Reduce [4] programming model that was made popular at Google. Map Reduce has proven quite reliable and robust given its strong community based around the open source version of it, hadoop. With Dryad, Microsoft proposes using a Directed Acyclic Graph (DAG) to combine computational “vertices” with communication “channels” to model data flow graphs.

A DAG is somewhat analagous to the Map Reduce model yet is more complex and can model Map Reduce itself (among other flows). The Dryad team states

The application can discover the size and placement of data at run time, and modify the graph as the computation progresses to make efficient use of the available resources.

Dryad’s argument is that Map Reduce is too simplistic and that

In all these programming paradigms, the system dictates a communication graph, but makes it simple for the developer to supply subroutines to be executed at specified graph verticies.

…

Map Reduce was designed to be accessible to the widest possible class of developers, and therefore aims for simplicity at the expense of generality and performance. By fixing the boundary between the communication graph and the subroutines that inhabit its verticies, the model guides the developer towards an appropriate level of granularity.

The more I read through the Dryad paper, the more I began to see their argument in that Dryad allowed the programming to be more expressive with a more general parallel computing model. However, is Dryad’s additional complexity a net gain in practical terms? The researchers in Berkley’s RAD lab don’t think so; In their paper on the Nexus [3] project, they state:

However, making a programming model too general increases complexity (Dryad is arguably more complex than Map Reduce) and decreases the opportunity to optimize programs using application specific knowledge.

going on to state:

We believe that no single general programming model for the cloud will exist. Instead, multiple cluster computing frameworks will emerge, providing various programming models with different tradeoffs.

which I feel is a pretty sage observation, at least in a general sense — design is about tradeoffs.

Dryad has some interesting tools, obviously integrating nicely with the .NET framework with DryadLINQ expressions. Hadoop has an interesting array of tools including

• Pig - A high-level data-flow language and execution framework for parallel computation.
• Hive - A data warehouse infrastructure that provides data summarization and ad hoc querying.
• Cascading
• HBase
  
• Thrift

and many other projects that have a cozy relationship with the Hadoop / HDFS ecosystem. Another inherent aspect to Hadoop’s array of tools is the fact that the project is open source and you can freely download the source code to add bug fixes or new features as you see fit. With Dryad, this is sadly not an option.

As I was reading up on Dryad I was really surprised to find that Microsoft does not include any sort of distributed filesystem “out of the box” for use with the system. Internally, Microsoft uses the Cosmos file system — but this is unfortunately not even available in the academic preview. Instead, there are bindings for NTFS and SQL Server which left me somewhat puzzled. If you want to position a product to go up against a solid engineering effort such as Hadoop, how can you leave out the distributed storage part of it? Hadoop on the other hand comes out of the box with HDFS and also works wiht KFS, HBase, Amazon S3, and others. To be fair, the Dryad team has only compared itself to the Map Reduce programming model and not the Hadoop project itself (HDFS included), so it is premature to make a comparison on this point — but its something that stood out to me.

The community aspect of Hadoop is a really nice feature from the perspective of a developer. The community is extremely active (and vocal) and will engage most any Hadoop related topic with very detailed discussions. A wonderful thing about open source is that a popular project generally has a strong and voracious user and developer base. Even though Microsoft is known to have its own enthusiastic supporters, at the present time Dryad has little beyond a small select academic circle using it. Until a production grade package for Dryad is released the jury will be out on what kind of community it will command.

As I don’t have a Dryad cluster to run tests on currently I am not able to run my own performance tests on it (unlike with Hadoop where I have access to a cluster). I would really like to see more apples to apples comparisons to see if Dryad’s added complexity yields performance increases that are worth the extra design overhead. I’ve learned the hard way that for anything you are going to rely on you need to do your own benchmarking in order to know true “real world” performance of a system (mesh networking coming to mind here). The 2007 Dryad paper [1] understandably did not have a comparison to Hadoop, but I was somewhat surprised to see the 2008 paper [2] not have a direct comparison (instead, the paper talked about Map Reduce in a general sense).To be fair, Hadoop may not have been on the Dryad team’s radar until the paper was well underway, and as I pointed out before, may not be a focal point for them in terms of market segment.

However, I did notice that the Dryad team tested against Jim Gray’s Terasort benchmark [5] and reported numbers for an array of cluster sizes, with their performance being reported as 319 seconds on 240 nodes for sorting 10^12 bytes. Hadoop currently holds the Terasort record [6] by sorting 10^12 bytes in 62 seconds. However, the primary difference was that yahoo team used 1,460 nodes in their Hadoop cluster. As anyone knows these sorts of tests are highly sensitive to parameter tuning and other conditions, so it is somewhat difficult to extrapolate what Dryad’s performance would be at 1,460 nodes. I did develop a quick and dirty fitted logarithmic curve for Dryad’s Terasort performance, and came up with ~800 seconds at 1460 Dryad nodes. (Update: Dimitri Ryaboy has since pointed out a flaw in this projection, in that there is more data involved in the sort basis as Dryad is sorting 3.87 GB per node. This inflates the total number of bytes past the 1TB mark and makes this projection suspect at best. Without an “apples-to-apples” setup, its difficult to get a better assessment. Originally the projection was done out of curiosity and meant to be taken with a very large grain of salt.) However, I did this just for curiosity — its unfair to even begin to project out performance given the myriad of variables involved in these type setups. Regardless, I can safely say that I feel like Hadoop’s implementation of Map Reduce is not holding it back performance wise in terms of the Terrasort benchmark when compared with the DAG implementation of Terasort. I would also be willing to bet that the Dryad team will step up to the plate and make a serious run at the Terasort benchmark now that the Hadoop team at Yahoo has taken the crown.

How much our computation time costs us is generally a prime concern for most big data businesses. Both clusters require a capital outlay for hardware, so as long as you are using commodity hardware (and here we assume you are) then this is a wash. However, the per node license costs is typically where vendors make their money in the OS and RDBMs scenes. With Dryad we only know that it runs on Windows HPC Server so your per node cost would have to reflect that (probably not cheap) and then there more than likely would be a per node license fee for each Dryad node (unless they release a all-in-one package/license). So cost with Dryad, at least in stark comparison with Hadoop, would be an issue for any sizable cluster. There is also the added costs of support, where I’m sure Microsoft would offer a support contract option, and Hadoop has a few vendors that offer enterprise support. Other than that, I feel that the Hadoop community is a strong factor in keeping costs low as you can either request a feature or patch it in yourself — which can save you a lot of time in contrast to waiting for that next 18 month release cycle.

Hadoop offers a robust computing platform that while may be considered more simple than Dryad’s DAG, has proven to be a reliable and powerful parallel computing solution. Sometimes less is more, but until we see more hard numbers published I will cut the Dryad team some slack there. When dealing with “warehouse scale computing”, I believe that the algorithm is going to dominate performance with generalized optimizations lagging behind that. In terms of relevance to the developer community, Dryad having a more complex processing data flow may or may not provide enough incentive to take on its much higher total cost of ownership — only a fully completed Dryad product will be able to accurately answer that. Taking on Hadoop directly may never even be in the Dryad team’s plans as they seem to be targetting a more general parallel programming case; If you are looking to do certain types of parallel processing intensive computations, you may want to give Dryad’s DAG model a look. However, without a “in the box” storage solution like HDFS and more compelling reasons to deal with their more general programming model,  I feel that Dryad may have a hard time finding fans in the general hadoop ecosystem.

References

[1] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly, Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks, http://research.microsoft.com/en-us/projects/dryad/eurosys07.pdf

[2] DryadLinq: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language, http://research.microsoft.com/en-us/projects/dryadlinq/dryadlinq.pdf

[3] Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ion Stoica, Scott Shenker, Nexus: A Common Substrate For Cluster Computing, http://www.usenix.org/event/hotcloud09/tech/slides/hindman.pdf

[4] Jeff Dean, Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, http://labs.google.com/papers/mapreduce.html

[5] Terasort, http://sortbenchmark.org/

saw them hurrying from either side

and each shade kissed another, without pausing,

Each by the briefest society satisfied.

(Ants, in their dark ranks, meet exactly so,

rubbing each other’s noses, to ask perhaps

What luck they’ve had, or which way they should go.)

— Dante, Purgatorio, Canto XXVI

Before I went back to grad school, I had been studying self organization and emergent systems as a side interest. While in grad school, when the opportunity to work on mobile ad hoc networks came along, I jumped at the chance to apply a swarm based routing algorithm in real research. My master’s thesis (TinyTermite [1,3]) ended up applying social insect inspired routing algorithms on wireless mesh networks (along with improving security in the base routing algorithm). In a previous article, we took a look at discovery and social insects;  Just like in nature, the base algorithm Termite [2] uses local information to make the wireless mobile ad hoc networks (MANET) self organize and adapt to their conditions.

TinyTermite is a novel probabilistic routing algorithm that is secure against selective forwarding and replay attacks. We use a technique called “suspicion” (or suspicion pheromone) to track possibly compromised neighbor nodes. As suspicion builds up and decays for each neighbor, TinyTermite is able to deal with uncertain stimulus and react properly. TinyTermite is fully implemented on the TinyOS based Intel Mote2 platform and experiments were done to compare its performance with that of the traditional Termite algorithm. With TinyTermite we implemented a swarm based routing algorithm that uses a digital pheromone to drive stigmergy among nodes in a mobile ad hoc network. The network is completely decentralized, just like the ants, and can adapt in uncertain conditions by leveraging stigmergy and indirect communication.

MANETs use a group of nodes to move information from a source node to a destination node without having a central authority directing the operations. MANETs can be quickly and inexpensively set up as needed and require no centralized administration or fixed network infrastructure such as base stations or access points. MANETs have begun to move into the commercial industry as a way to track inventory, route traffic, and move information. However, for applications such as military uses, disaster relief, and mine site operation, security and reliability are key.

With MANETs, we do not assume every node can hear every other node; This is a typical characteristic of these type networks. Wireless networks are inherently less reliable than wired networks due to interference. Routing is a key problem in any information network. MANETs are very dynamic when compared with their statically wired cousins. To route a packet, a node needs to know only the next hop to forward a packet to; However, this can be quite a difficult problem when a MANET’s topology changes frequently. Some key routing algorithms in the field are:

• AODV
• DSR
• OSLR
• DSDV

The underlying algorithm that TinyTermite is based on is called Termite. Termite is a biologically inspired routing algorithm for MANETs that is based on previous work in adapting the effects of stigmergy. Termite models how termite colonies lay pheromone to communicate in a decentralized manner. The concept of pheromone (as I’ve talked about before) is taken directly from the social insect metaphor where social insects use the chemical pheromone as a way to communicate indirectly. Termite piggybacks pheromone on normal network traffic which “trains” the network in an “on-line” manner. A more common technique is to send special packets out with the purpose of updating routing information around the network.

Termite is based on stigmergy powered by digital pheromone, which creates patterns of self organization in the ad hoc network. Termite was developed by Martin Roth and Stephen Wicker at Cornell. I’ve talked about stigmergy quite a bit in previous articles and in my graduate research I actually got a chance to create social intelligence between embedded devices. It was a lot of fun to see a flock of tiny devices “come alive” and show “bottom up” intelligence.

TinyOS is an open source operating system and platform intended for wireless sensor networks. TinyOS is an embedded operating system written in the nesC programming language as a set of cooperating tasks and processes. TinyOS started as a collaboration between the University of California, Berkeley in co-operation with Intel Research. Since that time the project has grown into an international consortium, the TinyOS Alliance. There is a lot of interesting research based around wireless mobile ad hoc network (MANETs).

The primary language, nesC (network embedded systems C), used for development on TinyOS is a component-based, event-driven programming language (quick tutorial for the interested). It’s basically C with some minor quirks and less features. However, the real difference is whichever compiler variant you end up using for your mote platform as some compilers are far more mature than others.  We worked on the Imote2 hardware which is considerably more advanced than earlier TinyOS based motes. Each Imote2 mote has a 415MHZ clock rate and 32 Megs or ram running on an Intel XScale2 processor. The one thing the XScale2 does not have is a floating point processor on its ALU, which provided some hurdles to overcome with floating point processing. I taught 3 days of a graduate class on communications as part of my graduate research work. I’ve posted my slides (slides are located here and here) from class on developing for the platform for those interested in what the platform is like. My sessions were on specifically the TinyOS platform and programming in the nesC language.

I spent a lot of time studying the basics of ad hoc networks, routing, and self organization while doing our research. It really made me re-evaluate what an operating system actually is and is not (a browser is not an operation system). I also became a tremendously better programmer having to work on an embedded processor with much tighter constraints that on a desktop machine. Spending a lot of time in ad hoc networks also made me think about other domains where we having an uncertain topology of “nodes” where dynamic decentralized discovery is needed — namely linked web data and the self organizing web data ecosystem. It also made me think of new ideas on how computing is evolving and where we can draw on themes from wireless ad hoc networks and apply them to other domains.

The field of self organization is amazing and I really enjoyed being able to work in academia doing research in that arena. It gave me a new appreciation for the non-mainstream area of computer science where I had to rely more on theory background and less of dogmatic ideas of mainstream programming. I also got to see my own work in self organization come alive, which was a thrill for me. Somewhere along the dull days of research, I scribbled down the words “elegant complexity emerges from brilliant simplicity” as a footnote on a draft of my thesis; I think that holds, especially in “bottom up” emergent systems. I think all too often in design we forget occam’s razor and try to overdo it. Termite is a great example of this as it uses no special packets to broadcast network topology yet continuously explores possible new routing solutions.

TinyTermite is completely decentralized and I believe provides a good example of the possibilities of decentralized dynamic discovery. I’ve already touched on some ways that this type of discovery could be useful in other domains, such as open linked web data. I also believe as the web continues to take over the desktop that we will see more techniques borrowed from mesh networks and applied to the internet as it becomes more like a single machine. In future articles I want to sketch out more ways I believe that could happen.

References

[1] J Patterson, TinyTermite: A Secure Routing Algorithm (Master’s Thesis)

[2] M Roth, S Wicker, Termite: A Swarm Intelligent Routing Algorithm for Mobile Wireless Ad-Hoc Networks

[3] M Sartipi, J Patterson, TinyTermite: A Secure Routing Algorithm on Intel Mote 2 Sensor Network Platform, Innovative Applications of Artificial Intelligence 2009

Where there is an ecosystem, there are local experts. An outsider can muddle through an unfamiliar wilderness at some level, but to thrive or to survive a crisis, he’ll require local expertise. Gardeners regularly surprise academic experts by growing things they aren’t supposed to be able to grow because, as local experts, they tune into the neighborhood soil and climate.

— from the book Out of Control: The New Biology of Machines, Social Systems, & the Economic World by Kevin Kelly, Image courtesy of Boston.com’s “The Big Picture“; Mountainous countryside near Maelifellssandur, Myrdalsjökull Region, Iceland. Once the young lava fields of Iceland cool down, life begins anew little by little. Ice, wind and water flatten and carve out shapes to begin with, then, during the summer, bacteria, lichen and fungi prepare the soil for plants, in particular mosses which adapt to an environment which remains difficult. These plants colonise the most favourable sites and terrain little by little, forming a new ecosystem. [map] (© Yann Arthus-Bertrand)

Much like the physical world, our current web of data on the internet is growing and adapting to its environment. Everyday this web of linked data becomes a more intertwined ecosystem that grows along side other regions of linked data, linking the sub-ecosystems together. Each area of this ecosystem, just like in nature, has its own peculiarities and personality. There is a lot of movement in the linked data space, from the concept of “the cloud” to other technologies like Azure and RDF. Some themes I keep seeing are:

• The inherent social nature of the web
• Interconnectedness vs the “sandbox” mentality
• Implications of interconnectedness
• Wiring into open ecosystems and creating more value

The web is, and will continue to be, a very social place. The nature of intelligence is social, so the (open?) social graph will naturally be a conduit of related information. Some data will be explicitly linked via technologies like XRD (and other discovery techniques), other data will be implicitly linked via tech like what our friends are talking about or doing (XRD and LRDD are key in this space). I believe that friendfeed and “follow” are early “primordial soup”-type social discovery techniques. As this space evolves we’ll continue to see projects such as laconi.ca and magnolia2 pop up, projects that allow for far more decentralization of user information yet employ smart and simple federation techniques to allow for identity to emerge from the nebulous pockets of personal information scattered around the web.

Interconnectedness is another facet of an ecosystem, as the output of one system is the input of another system. Companies can no longer afford to dictate how the internet as a “platform” works as there is only value in the network effect; Companies have to come to the realization that value is in the connections, yet not so much in just the information itself. Far too many companies want to try and create stockholder value through creating a small closed ecosystem (a “sandbox”) and then trapping users inside that sandboxed ecosystem, holding them hostage with no other choices after lock-in. Today the internet is about value coming from choice and “sandboxes” limit this value through their constrictive nature. In the new linked data ecosystem, a sandbox or data island has little to no value as it does not benefit from relationships with other data, providing less context through fewer connections. We are quickly coming to a day where how we connect our data determines just how much value that data can have as it determines or limits how the data can interact with the greater data ecosystem.

In the current climate, sandboxes lose value with time due to the lack of connections. With open linked data, the ecosystem is always growing, as well as connections, so data accrues value naturally with time. I liken this to how money can earn interest in your bank account, but not in a mason jar buried in your back yard. An interesting example of connecting data together was a mashup between twitter and yahoo data:

That inspired Singh to create the TweetNews mashup, combining the real-time search Yahoo’s BOSS tools with the freshness of Twitter. As an added bonus each story listed in TweetNews’ results also shows the relevant tweets, which themselves often have additional links. A quick search this morning for “flight 1549″ yielded seven unique links from just the top result.

TweetNews is not only a fantastic resource, but might well be the best mashup we’ve ever seen. The remarkable part is that Singh was able to create it with less than one hundred lines of code — a testament to the power of Yahoo Boss and APIs like Twitter’s.

Mashups like this are the basis for a whole class of simple interconnected web building blocks that will evolve the data ecosystem towards new and interesting places. We need connections not only between sites, but between data as well, to create feedback (which we established earlier as a driver of growth in a system). Feedback along a system of connections in an ecosystem will create the building blocks for all sorts of new and interesting systems.

The interaction of an ecosystem’s parts at the local level create the ecosystem through emergent ripples. The local interactions we start with dictate which possible set of stable states we could arrive at. Open and free local interactions will more likely result in a more democratic and decentralized web data ecosystem. Closed and proprietary local parts will result in very muted, controlled, and color-less reactions. The freedom of choice at the local level is what drives any dynamic decentralized system, and users need to be able to choose where their data goes, and how it gets used. However, every ecosystem has to start somewhere, and the mechanics to boot up a successful ecosystem can be daunting.

In the book “Out of Control“, Kevin Kelly talks about recreating a lost biological ecosystem from scratch, and the difficulties involved in such a process:

The problem Wingate faced was the perennial paradox that all whole system makers confront: where do you start? Everything requires everything else to stay up, yet you can’t levitate the whole thing at once. Some things have to happen first. And in the correct order.

This is basically the issue of having a highly interdependent system that needs the parts to grow together in a cooperative but autonomous manner. Kelly goes on to make several other observations about ecosystems:

• It was very easy to arrive at a stable ecosystem, if you didn’t care what system you arrived at.
• The larger an Ecosphere is, the longer it takes to stabilize, and the harder it is to kill it. But once in gear, the collective give and take of a vivisystem takes root and persists.
• Evolution not only evolves the functioning community, but it also finely tunes the assembly process of the gathering until the community practically falls together.

Which sum together to essentially mean that an ecosystem doesn’t just happen in an instant, it has to be “booted up”, so to speak, and even beyond that it has to organically develop in a cooperative manner. The advantage for any biological ecosystem is summed up by Kelly as:

Given a slim foothold, the remarkable latent power in interconnected green things can launch the law of increasing returns: “Them that has, gets more.”

Which brings us back to our system of linked web data; I hypothesize that the same effect is true for web linked data, as there is and will continue to be remarkable latent power in interconnected linked data (and services) which will continue to launch the law of increasing returns. I also assert that web linked data and dynamic discovery will be a driving force in the next wave of web technology. Linking of data and automated discovery (via techniques such as MetaData discovery / LRDD) will be the catalyst for co-evolution in future web iterations, but the evolution of these discovery and connection mechanisms won’t be without their growing pains.

Having a thriving, growing vivisystem of interconnected data is a high and mighty idea, but there are many considerations to take a look at under this scenario.

• Technological hurdles
• Not all data will be linked
• Not every application needs to be open source
• Privacy and Control balance
• Threats to entrenched institutions, Opportunities for the grassroots players

Technology is generally a double edged sword; we come up with great ideas that can advance the art, but then have to go about finding design tradeoffs so that current technology can meet future needs. The first generation of the web had us in a single document mindset with some slightly dynamic interactions. The second (current, or “web 2.0″ as Oreilly calls it) generation has been about moving towards social networks, explosion of rich online media, with an explosion of personal publishing. All of this has provided us with an abundance of information about us scattered across the web.

I believe the next wave of the web will focus on dynamic discovery and federation of these resources to produce more sophisticated and intuitive social media. However, currently we struggle with finding and linking this data together in a easy and cohesive manner, as we have bits of data scattered across a very distributed data store (the internet). If we look at it from a computer science historical standpoint, I think the biggest issue with respect to linked data is basically web2.0’s version of shared memory and interprocess communication. I think this topic will have to be widely discussed as we approach issues such as:

How will we share and relate facebook data with myspace data, and pull that merged data store into a third party application securely and intuitively enough for the average user?

Another issue that I’ve seen brought up is the fact that not all data should be linked together. I think this is very important from the since that data control should be granular enough that we (the user and owner of our data) can make those distinctions at our own discretion. Data ownership and privacy will continue to be big topics in this arena.

Regardless of the hurdles, the companies that continue to wire into the data ecology will find their net returns magnified over time. The companies that continue to live in their sandbox will have to rely on considerable barriers to entry surrounding their market in order to continue operation. Automated discovery and wireup of services will be a key driver in the bootup of the web data ecology. More and more, the data ecology will tie together the desktop, web, traditional media, organizations, entities and closed systems into a computing space that is more open and interconnected than ever before.

Without its software, a computer is basically a useless lump of metal.

- first line of the book “Operating Systems: Design and Implementation”

So, in my last article, we took a look at the last 50 or so years of operating system evolution. In this article, I want to take a short look at the current state of what an operating system is and does. So what exactly is an operating system?

Computer software can be roughly divided into two kinds: the system programs, which manage the operation of the computer itself, and the application programs, which solve problems for the users. The most fundamental of all the systems programs is the operating system, which controls all the computer’s resources and provides the base upon which the application programs can be written. [1]

Ok, so, thats pretty interesting right? So, to be fair, when we say “computer”, exactly what are we referring to?

A modern computer system consists of one of more processors, some main memory, clocks, terminals, disks, network interfaces, and other input/output devices. All in all, a complex system. [1]

So we’ve established what an operating system is, and what its trying to work with (components of a computer) — but why do we need this so called “operating system”?

Writing programs that keep track of all these components and use them correctly, let alone optimally, is an extremely difficult job. If every programmer had to be concerned with how disk drives work, and with all the dozens of things that could go wrong when reading a disk block, it is unlikely that many programs could be written at all. [1]

So, basically what we are talking about when we say “operating system” is a layer of services that abstract a lower level of complexity away so that we can build other more complex services on top of them without re-inventing the wheel. A very popular and highly influential operating system is the unix operating system. In the book “Design of the Unix Operating System” [2], Bach takes a look at why Unix was successful:

• written in high level language, C, making it easy to read, change, and move to other systems
• simple ui, power to provide services that users want
• provides primitives that permit complex programs to be built from simpler programs
• uses a hierarchial file system that allows easy maintenance and efficient implementation
• uses a consistent format for files, the byte stream, making application programs easier to write
• proves a simple, consistent interface to peripheral devices
• is multi-user, multi-process system; each user can execute several process simultaneaously
• hides the machine architecture from the user, kaing it easier to write programs that run on different hardware implementations

Bach also gives us the famous Unix diagram on the front cover of the book:

Which shows up how the system is layered around the hardware “core”, abstracting underlying plumbing as it goes. In this way, Unix is a very interesting design in that it takes a lot of loosely coupled pieces, and allows for higher order functions to be built on top of them.

Another interesting more recently developed operating system is TinyOS. TinyOS is an open source operating system and platform intended for wireless sensor networks. TinyOS is an embedded operating system written in the nesC programming language as a set of cooperating tasks and processes. TinyOS started as a collaboration between the University of California, Berkeley in co-operation with Intel Research. Since that time the project has grown into an international consortium, the TinyOS Alliance. There is a lot of interesting research based around wireless mobile ad hoc network (MANETs).

An interesting contrast between TinyOS and Unix is that a lot of people assume that an operating system and a desktop or graphical user interface (of any sort, windows or command line) are necessary components of an operating system; this is in fact, false, as TinyOS is an example of an OS that runs with no visual interface other than 3 LEDs on the mote circuit board. It also has no direct user input device, as it is meant to run the low level services of a small embedded device.

Given that from the previous article we established a history of operating systems, and in this article we took at look at modern operating system design (Unix), and emerging design (TinyOS) — I believe it is safe to say that the concept of an operating system is shifting and changing in different ways. Where are the bounds of what can be considered an operating system? The “Web2.0″ media seems to want to annoint every vaguely new computing paradigm as an “operating system” such as

• facebook
• a webpage
• a web browser
• a web desktop
• a remote connection to a desktop

Given the arc of the previous article on the history of computing, and the current article’s focus on what modern operating system’s entail, I fail to see how a single web page or a web browser can possibly be defined as an “operating system”. None of the items listed above “manage the operation of the computer itself”. By the definition established above for an operating system, these components are not operating systems by any means. Tim Bray even tweeted:

I strive to maintain an open mind when nontechnical people talk about the “Internet OS” or “Web OS”. Sometimes it’s tough.

However, as time goes on, every domain evolves as equilibrium is death. Computing is no different, and in the age of the internet we are quickly becoming a highly interconnected society by means of more sophisticated tools. As the complexity of our system advances, new layers of abstraction are required to built yet even more complex tools and systems. There is no doubt that the computing experience is shifting and users’ expectations are shifting as well. We are increasingly entering an age where data moves everywhere and the user experience is no longer on the desktop, but where ever the user happens to be using a device and in whatever context the user is in, be it desktop, commandline, or webpage.

I believe past shifts in computing can give us insights in how future shifts may occur, from storage, to computing infrastructure, to cloud computing. I will content that these shifts will produce needs for new layers of abstraction, similar to how the concept of an operating system evolved from the need to abstract away things like disk block access. As more complex services evolve on the web that need abstraction and aggregation via their APIs, what will our abstraction mechanisms look like, and how is this epoch of computing evolution any different than what was faced back in the 50s and 60s? What will the diagram above (Unix layers) look like in the near future with respect to layers of abstraction needed to produce more complex internet applicatons? I think looking back to it is an interesting topic, just as Tim Oreilly talks about how a critical design aspect of future web apps is:

the Unix/Internet model of “small pieces loosely joined,” in which cooperating applications come together to build value greater than any of the pieces do alone.

Here very soon we may end up rethinking what an operating system really is, and quite possibly see our daily computing experience move away from being OS centered and towards a more ephemeral computing experience. In coming articles I’m going to take a look at how I think decentralized systems such as TinyOS will influence some older ideas to produce the next epoch of computing on the internet, and how the loosely coupled mindset of Unix may have a strong influence on this design as well.

References

[1] Andrew Tanenbaum, Operating Systems: Design and Implementation, Prentice Hall, 1987.

[2] M. Bach, Design of the Unix Operating System , Prentice Hall, 1986.

Long ago it became clear that in order to create more complex programs, we needed to shield programmers from the complexity of the hardware. [1]

In any discipline, it’s interesting to see where we’ve been to get an idea of where we might be heading. These days we hear a lot of things about cloud computing, browsers as “operating systems”, and web2.0; In order to setup some future articles (similar to what I am doing with self organization), I am going to write a bit about where operating systems have been, and then what the key principles of operating systems are — and then in future articles how this relates to evolution of the web. But first, let’s cover a little background.

The first era of the digital computer was in the time of Charles Babbage (1792 - 1871), a computer that never got built completely. This computer was largely conceptual and never got off of the drawing board, so to speak. Needles to say, it was based around the basics of computation and had no operating system to speak of. However, later on an operational difference engine was constructed from Babbage’s original plans and the London Science Museum has parts of Babbage’s uncompleted mechanisms on display.

The next era of computing I want to look at is the era of “punch cards”. A punch card (also known as a Hollerith card or IBM card) is a paper card that holds digital information encoded as holes or the absence of a hole. Punch cards, now obsolete as a medium, were widely used throughput the 19th century as control mechanisms for textile looms and certain musical instruments. In the 20th century punch cards were used as unit record machines for input, processing, and data storage. Punch cards were also used as the primary input medium for early digital computers for programs and data.

After punch cards, we see the first signs of the evolution of operating systems with vaccum tubes and plug boards (1945 - 1955) [1]. These operating systems were based a lot on intense technology developments from WWII. I’ve always viewed WWII as a major driver in advancing the state of computers in general as so much intensive research was poured into the subject in such a short period of time. Aspects of this era of computing include:

• Vacuum tubes and plugboards
• Absolute machine language
• No programming languages, no assembly
• Burned out vacuum tubes were more troublesome than software bugs
• Reliability an issue

The second generation (1955 - 1965) [1] was based around the development of the transistor and batch systems. Properties included

• These systems were more reliable and could be manufactured for mass production
• Clear separation between designer, builder, operator, programmer, and maintenance
• Generally only large institutions could afford the multi-million dollar price tag
• Code was first written in FORTRAN or Assembly, then punched in on cards
• Mostly used for scientific and engineering calculations, such as solving partial differential equations
• Typical operating systems in these times were Fortran Monitor System and IBSYS

The third generation (1965 - 1980) [1] was based around integrated circuits and multiprogramming. The IBM System/360 was a major part of this epoch that met the needs of a wide variety of customer. Properties of this generation included

• The evolution of families of machines that would run the same code
• First use of small scale integrated circuits in the IBM Sys360
• Programming was still very difficult
• Partitioning of memory for multiple concurrent jobs to be processed (multiprogramming)
• Concept of time sharing and terminals
• Development of the PDP-1 by DEC
• Dennis Ritchie rewrites UNIX in a high level language called “C”

The fourth generation (1980 - 1990) [1] was based around personal computers, most notable the Apple IIe, the Mac, and MSDos. Notable things about this period include

• Individuals could now afford home computers such as the Apple IIe [3]
• Advent of the GUI in devices such as the Mac [3]
• Widespread growth of software for personal computers
• Two operating systems have dominated since then, UNIX and MSDOS (plus their derivatives) [2]

As I mentioned above, I wrote up this review because I want to take a look at where we’ve been and see where we might be headed on our evolutionary arc of computing. Some themes I want to examine, in conjunction with themes on linked data, discovery, and self organization, are:

• What exactly makes up an operating system, and how have those properties shifted over time?
• What exactly is this so called “Cloud” computing?
• Why do some people keep saying the browser is an operating system? (hint: its not)
• How does our computing experience shift in the age of HTTP, linked data, and distributed identity?
• What can the biological world tell us about how to design systems of the future?

I think we can find some interesting trends along these arcs, and I believe we’ll see some patterns revisted.

References

[1] Andrew Tanenbaum, Operating Systems: Design and Implementation, Prentice Hall, 1987.

[2] M. Bach, Design of the Unix Operating System , Prentice Hall, 1986.

[3] A. Hertzfeld, Revolution in The Valley: The Insanely Great Story of How the Mac Was Made, O’Reilly Media, Inc., 2004.

Once the young lava fields of Iceland cool down, life begins anew little by little. Ice, wind and water flatten and carve out shapes to begin with, then, during the summer, bacteria, lichen and fungi prepare the soil for plants, in particular mosses which adapt to an environment which remains difficult. These plants colonize the most favourable sites and terrain little by little, forming a new ecosystem.

— from the book Out of Control: The New Biology of Machines, Social Systems, & the Economic World by Kevin Kelly

I believe we are building a unified ecosystem of web applications that will evolve and grow just like biological ecosystems do. In order to allow this ecosystem of data and applications to co-evolve and interlink over time, we need to provide a way for this ecosystem to discover and self organize itself. I believe XRDS-Simple can be one of the technologies that allows us to “boot up” the emerging web data ecosystem.

As we move into the economic downturn, startups (and grassroots efforts) will shift from focusing on the last epoch of social graph and media sites to looking at how we can do something with all these disparate pockets of our media around the web. Just like in the last economic downturn (2000), we will see a new set of seed ideas take hold in the web ecosystem and spring forth many new hits for this next epoch of the web. I believe one aspect of the next evolution of the web will be based around dynamic discovery of relative linked data.

In previous articles we saw how the natural world employs self organization to drive emergent processes. One of the underpinning mechanics of self organization is its decentralized nature. We saw how in ad-hoc networks a network could adapt and thrive under difficult conditions with no central leader. The internet is a loosely coupled set of computers, just like an ad-hoc network. Its an ad-hoc network of clients and servers within a system that faces many of the same obstacles a mesh network does — and has a tremendous amount of linked data contained inside.

This linked data is coming online at a rapid pace, but it continues to be pooled in silos; the data is linked, yet we still have to manually connect those links and use our data in seperate sandboxes (ex: my facebook and myspace data does not play together). Just as google found out, a tremendous amount of value lies in how information is linked together. Today users have their photos in a couple different services and the majority of the US has its social graph split between myspace and facebook. There are all sorts of bookmarking services, and we have accounts for all sorts of shopping sites scattered everywhere. As these clusters of data come online and grow, more value can be had in how they are connected and what can be done with these new connections. With respect to how we’re allowed to use our data, we’re sorta in the “Hotel California” phase of the web —

you can check in, but you can never check out.

In future iterations of the web I see users taking ownership of their data and creating a more personal user experience based on their existing data no matter what device they use or their location. This depends on how we link our data, how we allow our data to be discovered. So that begs the question, just how will we leverage this linked data and aggregate our information in more intelligent ways? I think a key lies in ad-hoc networks, social insects, and self organization — with one fundamental aspect being dynamic discovery.

Discovery is the key mechanic that connects relevant parts of a decentralized system. As the web and linked data get more complex, we can’t predict the ways in which will need to discover and use data. Search engines can only give us part of the solution as they make connections based on their own assumptions and biases. We saw how ants discover food sources using stigmergy yet with no central source of control. We also saw how an ad-hoc network leverages a similar stigmergy based mechanic to find quality routes through a chaotic network. Discovery needs a little more structure than we currently employ — it needs a “road sign” to know where and how to get to your data. Ants do this with pheromone build up, MANETs with routing tables, but how can we do this in a linked data world? I believe XRDS-Simple can provide us with the basic “n+1″ evolution of dynamic discovery we need for this emerging web data ecosystem.

XRDS-Simple (or XRDS-S - google group) as described by Eran Hammer-Lahav:

XRDS came out of the XRI world and is focused on service endpoint selection – connecting a list of concrete resources to an abstract identifier. When expending XRDS to HTTP URLs - non-abstract web resources - it providers a simple format for tagging resources and related services. These tags, called types, are URI-formatted strings which inform machines about the capabilities and characteristics of the resource they are associated with.

This means XRDS-S allows a service to discover attributes about a resource which can redirect a service towards other related or linked resources. XRDS-S is essentially an XML format for pointing towards a set of services related to a url. The current case I am most focused on is a user’s personal set of services, as in the places a user

• Keeps their images
• Keeps their bookmarks
• Delegates their identity provider to
• etc

If a user can control this index of their service “endpoints” (XRDS-S resource), the user can then provide specific levels of access to specific subsets of interested outside parties (a longer term goal). And when we have a robust technology that allows users to do this, I believe web data can interconnect and auto discover in ways we haven’t even through of yet.

I think XRDS-S can create more value for the user by giving control and ownership of data flow to the user, back to the owner, and ultimately give us a better computing experience. However, thats big pie in the sky talk. Let’s think more along the lines of building up the technology in terms of “n+1″, in terms of adding a basic new mechanic and see how it effects the emerging web data ecosystem.

In the short term, I’d like to explore more on how XRDS-S can be used to do some basic things like

• Allow a 3rd Party Service to discover your preferred bookmarking service, and automatically route the saved url to said service
• Automatically discover your media you have stored around the web
• Dynamically find a related service in an contextually sensitive way which enhances the user experience.

In coming articles, I want to take a look at how XRDS-S is emerging as a discovery technique, and scenarios where it can be used — and how it can be a road sign in the emerging digital ecosystem.

“Well, in our country,” said Alice, still panting a little, “you’d generally get to somewhere else — if you run very fast for a long time, as we’ve been doing.”

“A slow sort of country!” said the Queen. “Now, here, you see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!”

— Lewis Carroll’s Red Queen from Through the Looking-Glass

For my Master’s thesis, I did work in Mobile Ad Hoc NETworks (MANETs) and self organizing routing algorithms. At the present time, I can’t post my thesis online as we are waiting to see about some journal publications, but I’d like to talk a little about decentralized discovery in MANETs (however, I have a large article ready to go about my Master’s thesis, so when I get the clearance, it will be posted).

MANETs are decentralized networks that have no leader node or central controller where each node can only hear a subset of all nodes. Every node has to be a good citizen and agree to forward packets for other nodes in order for the network to function. Routing is a key issue in MANETs since a different set of obstacles are faced as opposed to traditional wired networks. There are many different ways that a network can approach the issue of routing, however there are two (main) classes in MANETs: Proactive and Reactive networks.

• Proactive: A proactive ad-hoc network seeks to constantly have the best possible global routing information in its routing tables, updating the routing table as new information comes online.
• Reactive: A reactive ad-hoc network only caches routing information in its tables relative to the routes it has seen recently or needs to forward the current packets in its queue

Beyond the type of MANET, another major designation is how the network routes its packets. There are generally two main types of of routing protocols used in packet-switched networks : link-state and distance vector.

With link state routing each node broadcasts to all other nodes in the network its view of the status of each of its adjacent network links — it sends its map. Each node then computes the shortest distance to each host based on the complete picture of the network formed from the most recent link information from all nodes. This approach is closer to the centralized version of the shortest path computation method, with each node maintaining a view of the network topology with a cost for each link. RIP and OLSR are link state algorithms.

A distance vector routing protocol requires that a router informs its neighbors of topology changes periodically — it sends its routing table. It also informs neighbors when changes are detected. They have less computational complexity and less message overhead. AODV and Termite are distance vector algorithms.

Termite is a biologically inspired routing algorithm for MANETs that is based on previous work in adapting the effects of stigmergy. Termite models how termite colonies lay pheromone to communication in a decentralized manner. The concept of pheromone (as I’ve talked about before) is taken directly from the social insect metaphor where social insects use the chemical pheromone as a way to communicate indirectly. Termite piggybacks pheromone on normal network traffic which “trains” the network in an “on-line” manner. A more common technique is to send special packets out with the purpose of updating routing information around the network.

Termite is based on stigmergy powered by digital pheromone, which creates patterns of self organization in the ad hoc network. Termite was developed by Martin Roth and Stephen Wicker at Cornell. Distance vector algorithms such as Termite use routing tables in order to choose a next hop for a packet. Each Termite node has a pheromone table (a routing table) in which it lists the neighbors that the node can hear locally. Termite uses this routing table, which has a goodness rating for taking a neighbor node as the next hop of a path towards a destination node, as a way to probabilistically choose a next hop for the packet (the higher the pheromone rating for a neighbor+destination pair, the higher the chance that that neighbor will be chosen for the next hop “towards” the destination). In Figure 1 and 2 below, we see how a packet traveling from the source node 0 to the destination node 6 updates the pheromone table at node 6 on its final hop.

Figure 1: Packet movement through Termite network. A packet moves from node 4 to node 6 on its final hop to the destination node 6.

Figure 2: Pheromone table update. As the packet in Figure 1 hops to node 6, node 6 updates its pheromone table to reflect the incoming packet’s information. The pheromone table is updated such that neighbor node 4’s destination entry for node 0 (source node) has its value adjusted. The rows in node 6’s pheromone table reflect the nodes that node 6 can hear locally. The destinations are nodes that node 6 knows about.

As packets move from node to node (they are routed at each hop), they follow the “pheromone gradient” that is relevant to their destination. The higher the level of destination pheromone for a next hop neighbor, the more likely a packet is to be routed towards the destination via that neighbor. Packets also carry a pheromone factor which represents the quality of the path that the packet has traveled and influences each node’s pheromone table that the packet passes through. The pheromone table for each hop is influenced by the amount of pheromone on the packet (the pheromone table is updated “towards” the source (as the destination in the table) and the previous hop (as neighbor that is updated). In this way, Termite updates node pheromone table in an on-line manner with no special control traffic.

If a destination node is requested that the forwarding node has no entry for in it’s pheromone table, the packet is stored in a queue, and a Route Request (RREQ) packet is broadcast. A RREQ packet is forwarded to neighbors who check to see if they have an entry for the requested destination. If the node does in fact have an entry for the requested destination, it generates a Route Reply (RREP) packet and sends it back towards the source node (node which generated the RREQ). At each hop the RREP influences the pheromone table so that the originator of the RREQ is linked with the node that had a next hop for its required destination. When the RREP reaches the source node, the source node’s pheromone table is updated and the queued data packet is forwarded.

The effects of the pheromone based probabilistic routing system with a RREQ / RREP discovery mechanism allow Termite to be flexible and robust in the face of many types of deployment climates. Just like with social insects foraging for food, Termite can endure and thrive in uncertain conditions where tradtional techniques would fail. Termite is a very interesting application of biologically inspired systems that use nature to find good engineering solutions. These types of biologically inspired decentralized systems show how emergence can be leveraged in technology. Kevin Kelly has an interesting take on the strategy of these biologically inspired system in that:

A network nurtures small failures in order that large failures don’t happen as often

— from the book Out of Control: The New Biology of Machines, Social Systems, & the Economic World by Kevin Kelly

These systems bend, but they rarely break. Highly linear, clockwork type systems are rarely this robust in the face of uncertainty (not that they don’t have their strengths). I see ad-hoc networks as a metaphor for a lot of different areas of technology and complex systems. Decentralized discovery seems to me as if it can be useful in a lot of different places.

Something that has really interested me is the parallel between ad-hoc networks and the emerging ad-hoc nature of today’s web of linked data. The more I dig, the more I see similarities in the development of a decentralized ecosystem that has value in how it is interconnected. As we’ve seen with Termite, there is also tremendous value in a system that is interconnected, yet loosely coupled.  Something I want to explore further is how we can add small properties to the web at the “node” level that give it more decentralized robustness, more ways to auto discover itself.