« Web 1.0 (beta) | Main | Lack of Focus + Featuritis + Poor Fundamentals = -$580 Million »

Web 1.0 (beta), continued

Basic Description:

Nodes:

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

Protocols:

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.

Transport:

Data is transfered serially using a wired connection.

Addresses:

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.

Music

Where am I?

Recent Photos

Powered by
Movable Type 3.35