Network Effects Archives

October 17, 2006

Web 1.0 (beta), continued

Basic Description:


Microcontrollers (in this case PICs) programmed with identical code. Physicality (pin layouts, etc) may differ from node to node within certain restrictions.


The network uses the standard RS-232 serial protocol for data transfer, with the addition of a proprietary signaling system that uses the same wire to send ready-to-send, ready-to-receive, and receive-success messages. Each packet consists of the target node address, the address of the sending node, the hopcount, and a four byte payload.


Data is transfered serially using a wired connection.


In the protocol, locations are specified by an eight bit address, allowing up to 255 nodes. In the current hardware implementation, however, the nodes are addressed at boot time by hard-wiring four pins of the microcontroller, thus limiting the network to the four low-order bits of the address, or 16 nodes.

Network Stack:

The stack for this implementation is very simple, as (using the Internet comparison) only levels up to and including the IP level of the stack are included. A TCP-like protocol could be constructed atop this stack, and then any desired application protocols further atop that protocol. As it stands, however, the network implements:

[End to end addressed packet transfer]
[RS-232 plus additional signaling]
[TTL logic I/O]

Visual Explanation:

Each processor in the video is connected to a set of three LEDs, enabling the viewer to see network traffic in process.

Red -> Node is transferring data
Yellow -> Node is receiving data
Green (in combination with Red or Yellow) -> Transfer / Receive succeeded
Blinking green and yellow -> Packet arrived at ultimate destination

Each node has a local address (in this case, 0-5). Each node can then send a packet of data to any other address in the network. The transport protocol is simple (and unreliable) and consists simply of handing the packet off to a random node, attempting first to connect to any node which is not the source of the data. Thus if node 0 sends a packet to node 4, if the packet is not addressed to node 4, node 4 will attempt to pass the packet on to any node connected to it that is not node 0. If this fails, it will pass the packet back to node 0.

The video shows 5 packets being sent from the lower right node of the network to the node in the upper left corner. This shows the variable routing and a few of the possible routes a packet can take in the process.

Full Description:

The network was designed to be a lowest common denominator of mesh network design - a basis for possible future development. As such, it is a success. With a limited number of nodes, packets move from point A to point B in a reasonable number of hops, but it is clear that a good deal more work would be in order to develop a scalable network.

Fig. 1 - Schematic of TX/RX circuit

The network consists of PIC microcontrollers communicating via RS-232 serial with the addition of the ability to use that same data line for signaling from the recipient both of ready to listen and data received signals. This is achieved using the circuit shown in Fig. 1. The transmit pin for each data line is connected via a resistor to a second pin of the microcontroller which is configured as an input. Then this second pin is connected to the receive pin of the remote device. Then when a node wants to transmit, it asserts its TX pin high, which also raises TXACK and RX to high through the resistor. Then, assuming the there is a remote device connected that is not busy and sees the signal, it asserts its RX pin low, which pulls the TXACK pin on the transmitting device low as well (the resistor prevents an over-current between the two driven outputs). The transmitting device sees this ready signal, waits a specified small amount of time for the receiver to enter listening mode and then sends the data. After the data is sent a similar exchange takes place to confirm receipt.

Routing takes place via an extremely simple protocol. Each device can be connect to as many as three other devices. These connections are sensed each time a packet is sensed via the protocol described above. When a packet originates, it is sent randomly to one of the three possible connections or the first one that successfully receives it. If the packet is not at its ultimate destination, it is forwarded to another random node, with precedence given to nodes that are not the node from which it was received. This prevents two node looping. Even this one simple rule provides an enormous reduction in hop count over a purely random scheme and creates a somewhat usable, if poorly scaling, network.

Fig. 2 - Probabilty calculations for arrival in 5 hops or less across 6 nodes

As you can see in Fig. 2, for one particular simple six node topology, the probability of a packet arriving from one extreme of the network to the other in 5 hops or less (without making a loop) is 75%. In Fig. 3, two nodes are added, and while the similar case (no loop) entails only one more hop, delivery only succeeds within six hops 56% of the time.

Fig 3. - Probabilty calculations for arrival in 6 hops or less across 8 nodes

On the other hand, in the six node example, by tolerating a single loop which allows up to 9 hops, the probability of success increases to 93.75%, which can be seen in Fig. 4. Analysis of the eight node example quickly becomes difficult because of the greater number of combinations of loops, but it seems that allowing one loop (up to around 12 hops) increases its chances of success to around 78%. Time permitting, computer simulation would allow a better analysis of larger networks of this type.

Fig 4. - Probabilty calculations for arrival in 12 hops or less across 8 nodes

I did not have a specific numeric estimate of performance prior to construction and analysis, but the six node network performs somewhat better than I expected and the eight node network somewhat worse. This horrendous scaling could be improved with a topological shift to a small world system, where a number of these meshes could be connected together via specifically designated router nodes with the address space configured such that it can be deduced from the address whether a packet should stay within a subnet or propagate onward to another. The relative success of the mesh with small-scale networks suggests that this could be a workable solution, although the benefits over a more standard non-mesh topology are dubious given the rudimentary routing system.

The routing system itself could be improved if the size of each subnet remained relatively small by implementing a backpropagation system, wherein each packet was tagged with the address of each node through which it passed. Upon receipt of the packet, this information could be sent back to each of the nodes that were involved in the original transaction, and the hopcount of the outbound and inbound packets could be compared with any hopcounts of previous steps that were stored in memory to, over time, find an optimal next hop to reach any node in the network. This activity may need to be limited in order to balance the risk of flooding the network with optimization messages with the desire to adapt quickly to changes in topology.

After this first foray into mesh networking, I must say that I am pleased at the results of the basic implementation and would like to spend more time in the future to investigate and experiment with various learning schemes that could improve performance and scalability.

October 15, 2006

Web 1.0 (beta)

The first six nodes of a wired mesh network for Network Effects.

The network consists of two types of PIC microcontrollers variably interconnected into a fault-tolerant mesh network. Arduino support may be forthcoming along with source code. At this point, the network is intended more for topological research than for moving bytes, but the protocol could probably find its way into other projects. More to come...

September 6, 2006

The Death and Life of Great American Networks

The chapter, The Uses of Sidewalks: Safety, from the book The Death and Life of Great American Cities written by Jane Jacobs and published in 1961, is profoundly relevant today in its take on urban safety as a function of emergent effects of sidewalk as network. The closing paragraph of the chapter reads:

On Hudson Street, the same as in the North End of Boston or in any other animated neighborhoods of great cities, we are not innately more competent at keeping the sidewalks safe than are the people who try to live off the hostile truce of Turf in a blind-eyed cty. We are the lucky possessors of a city order that makes it relatively simple to keep the peace because there are plenty of eyes on the street. But there is nothing simple about that order itself, or the bewildering number of components that go into it. Most of those components are specialized in one way or another. They unite in their joint effect upon the sidewalk, which is not specialized in the least. That is its strength.

In example after example, Jacobs illustrates the beauty of the ordered city, not one held siege by heavy policing, but instead one that primarily polices itself. This, over 40 years later, is exemplified by the New York that I am lucky enough to inhabit today.

What is most significant here, is that the underlying network of all of this street level behavior, the sidewalk, is not specialized. Within reason, all types of people and behavior are tolerated and appreciated. The successful city realizes that with a few notable (and usually violent) exceptions, activity trumps inactivity, is beneficial for the network as a whole, and should be treated with equal respect, regardless of traditional moralist standards of "acceptable" behavior.

This activity then bolsters the strength of the network. It is a beautifully elegant natural solution, BitTorrent meets SneakerNet. Activity begets activity, and also provides the resources and safety necessary for this added activity. In this case, it is not bandwidth that is at issue, but instead eyes to monitor the safety of a city's streets.

The million dollar question remains, however — how to bolster this type of activity in a place where it currently does not exist by nature. Jacobs lists a number of failed attempts, typically very harsh segregation that is paralleled to the Turf system used by street gangs, but I have yet to find a clear answer in the positive as to how to all at once revitalize a neighborhood without running into the problems presented by artifically imposing culture upon a neighborhood.

What is clear, however, is the notion of sidewalk as network; specifically a network that benefits and flourishes under what may appear to some to be the burden of added activity. I think this is second nature to most of us that have lived in or visited thriving urban environments as well as their depressed counterparts. The phenomenon of safety in numbers seems second nature, but still some planners and developers must only feel safe when they are alone.

There are strong parallels here to the current debate over net neutrality, where as a knee jerk reaction to a few "internets" that were slow to arrive, small-minded regulators come to the quick "realization" that artificially imposed sanctions on usage patterns and their priorities are the answer, ignorant of the fact that this ruins the elegant simplicity of the network itself, much as some people feel that a bustling nightlife in their neighborhood will inevitably bring crime, when generally the opposite is actually true.

In the case of net neutrality, how hacker-proof will these prioritizing systems be? I have yet to see a non-trivial example of rights management or copy protection that a handful of well motivated college students were unable to crack. And then where are we? Not only do we have tubes half filled with trash, but the smelliest of the garbage, that of the criminals that have learned to defeat the system, has priority over the rest of our content. It's much the same argument as is often made against gun control, but I think precedent shows that these laws would be even more difficult to enforce.

If you don't believe me, go search Torrentz for your favorite high-priced software package. Almost invariably, its developers have spent countless dollars on implementing various copy protection strategies only for them to be almost immediately broken by "crackers" across the globe (don't steal software.). I think I hardly need to suggest what is likely to happen if means are opened to prioritize traffic on the internet. The fact is, I don't know, but I am willing to bet that it isn't the simplistic, utopian result that the regulators envision.

The broadest lesson to be taken from all of this is that whenever networks are examined beyond the most trivial of examples, whether in the technological or the human arena, things are rarely as simple and straightforward as they appear. Often precisely the opposite is true, and even more often, simplicity of policy is beauty in practice.

February 22, 2006

Flight Pattern Visualization

Beautiful visualization of flight activity over the United States by Aaron Koblin at UCLA.

December 24, 2005

About Me

Me at ITP Winter Show 2005

Welcome. I have started this site for myself and others as a memoir of my trip through life and, for now, the Interactive Telecommunications Program experience and as a place to log the ideas and thoughts that otherwise seem to slip away. I look forward to comments and criticisms, helping and being helped, and whatever else comes my way. Life is good.

Contact me.

View my resume.


Where am I?

Recent Photos

Powered by
Movable Type 3.35