Working on an implementation of an IsoGrid switch – Spec Update

Over the last 6 months, I’ve been implementing an IsoGrid switch. I call it the CrowdSwitch. Much progress has been made and I’m starting to get excited about how far I’ve come. This work led me to make some improvements to the IsoGrid spec; the latest version is released below. Our next steps are:

  1. Publish CrowdSwitch design basics at isogrid.org/crowdswitch [Sept 13 2017: Done!]
  2. Work on completing the engineering system for the CrowdSwitch product (build, test, bug management, etc.) [Sept 1 2017: Initial work done!]
  3. Try to find some motivated software systems engineers who want to contribute development time to the project
  4. Continue to make progress on the code

IsoGrid Protocol Spec changelist for version 0.230 vs. 0.225:

  • Clarified wording
  • Specified bit and byte ordering (Little-Endian)
  • µPkt is now statically sized (8 words)
  • IsoStreamFooter design changed
  • Alternatives to Parity
  • Removed µRoute
  • Changed µPkt extensibility model
  • Payments changed from floating-point to fixed-point for latency benefits
  • Renamed CachedRoutes/Routes to Breadcrumbs, and added more details
  • Added a new requirement to µPktWithReply
  • Large refactor of InitIsoStream type hierarchy and requirements
  • Refactored IsoStreamRoute tags
  • Added a DelayAccept member and associated requirements to InitEccFlow and AcceptEccFlow; to address a security issue
  • Add detail about fan-outs using the LinkTunnel pattern
  • Refactored LocatorHash to be 64 bytes (to fit in µPkt)
  • Idea about Breadcrumbs for HashMatch
  • Idea about Micro-Payments within a computer to fairly allocate resources; say, in a VM environment.

Here’s the latest spec:

IsoGrid Protocol Specification v0.230.

CC0

To the extent possible under law, Travis.Martin has waived all copyright and related or neighboring rights to:

IsoGrid Protocol Specification v0.230.
This work is published from: United States.

This document is still an early draft. If you’d like to help improve it, contact Travis.Martin at this domain. Discussion at Hacker News!

Scalability of Isochronous Mesh Networking to 2^40 Switches

When discussing mesh networking, the common refrain is “mesh networking is not scalable”. Here is data and code that indicates it can scale ‘enough’ to support a full-scale global isochronous mesh network of 2^40 nodes with mostly stable links. These data were generated by running a mesh routing algorithm on each node in simulated networks sized from 2^7 to 2^23. Note that this algorithm isn’t the full spec’d IsoGrid algorithm, just a framework to test scalability.

Assumptions

This simulation and analysis makes the following assumptions:

  1. The link layer is isochronous
  2. The network layer is source-routed
  3. Latency per hop is bounded by a constant time that is comparable to the time it takes for light to propagate across a hop
  4. The links (on average) stay up for longer than a day (no mobile nodes)
  5. Nodes join the network in a bootstrapping process inspired by S/Kademlia
  6. The simulation of networks sized from 2^7 to 2^23 is enough to extrapolate likely scalability to 2^40
  7. The global network topology is approximated by placing nodes in a 2D grid pattern and linking each node to the 4 nearest nodes (except at the edges and corners).
  8. Each node has 100Gib/s (or more) total switching capacity
  9. Each bootstrapping message is around 1kB
  10. The cost of network transit is directly proportional to physical distance

It follows from #1 & #2 that latency per hop can be bounded by a constant. See the IsoGrid Protocol Specification v0.225 for details on why. Specifically, #3 is reasonable at least until 2^47 nodes (~1 node per square meter of the land surface of the earth). Light takes ~5ns to travel 1m in optical fiber. With 128 bit words switched isochronously at an achievable 100Gib/s, each hop in this full-scale scenario has on the order of 1.2ns extra latency.

#4 reveals an acceptance that mesh networks with highly mobile nodes (actually nodes with highly transient links) aren’t likely to be scalable. But the switches that form the network don’t have to be mobile, just like the core routers of the Internet aren’t mobile.

The current TCP/IP Internet routing table is NOT scalable: Each node must know about all other nodes. #6 means that the following is only likely true but isn’t proven: Isochronous&source-routed mesh networks can scale to 2^40 nodes with conservative assumptions about topology and current technology. If, instead, one assumes a more 3D topology would develop naturally in the full-scale scenario (urban environments, satellites, and rooftop wireless laser hops), then it scales beyond 2^50 nodes.

#7 means that taking a simple bisection of the square grid produces the nodes that have the heaviest bootstrapping data load to switch. In order to be a viable network, this load must be a small portion of the available bandwidth of those nodes. Higher physical bandwidth links and more stable links network wide make this better.

Simulation

The simulation code is shared here for verification and reproducibility purposes. This code is NOT production quality. It’s never been code reviewed. It’s more important to move to the next phase of development rather than spend time cleaning up the simulation code.

The simulation was built to have the following scalability properties, and the data confirms it was achieved:

  • The “Search Rounds” taken by each node to find its best matched nodes (XOR metric) grows as LOG2(N)
  • The “Highest Traffic on a Link” grows near N^(1/2)

Data

Raw data was collected by simulating the bootstrapping of various networks from 2^7 nodes to 2^23 nodes. A seed is used to drive a pseudo-random number generator to produce the node IDs. With the same seed, the first three columns are produced deterministically, but with a different seed the numbers move around a bit. In order to determine the growth rates with more accuracy, the simulation was repeated with different seeds (up to 2^21 nodes), and then averaged:

 Nodes Hops Traversed
Per node
Centerline crossing messages
Per node
Search Rounds
Per node
Avg. Mem.
Per node
(B)
Avg. CPU
Per node
(ms)
Highest
Traffic on a Link
(kB)
2^7 354.63 28.70 3.647 4916 1.00 324.65
2^9 797.70 29.89 5.607 7471 1.22 676.36
2^11 1718.72 31.80 7.597 11362 1.75 1439.18
2^13 3673.90 34.64 9.596 13538 2.44 3134.81
2^15 7819.45 37.56 11.596 16310 3.17 6799.43
2^17 16684.50 40.66 13.596 19211 3.99 14720.58
2^19 35614.29 43.87 15.596 21949 5.06 31768.34
2^21* 76090.86 47.35 17.60 # # 68570.64
2^23* 162771.73 50.98 19.60 # # 147642.81

*The 2^21 sim required a large system and many hours of compute time, so it was only run 7 times. The 2^23 sim required a very large system and two days of compute time, so it was only run once.
#Memory and CPU time aren’t meaningful when tested near the memory limits of the machine, (due to additional Garbage Collection) which occurred on the 2^21 and 2^23 node sims

Analyzing the effect of doubling the network size on each column, from left to right:

  1. If one normalizes the per-node cost (the number of hops traversed per node) by distance, then the per-node cost growth rate upon doubling the network size is low (<6%). This can be done by assuming the growing number of nodes are spread evenly over a non-growing space: Since the network is a square, this normalized growth rate was computed by multiplying by the square root of the network size.
  2. The number of messages per node that have to cross to the other side of the network is growing at only 3.9%
  3. The search rounds per node are tracking LOG2(N) perfectly
  4. The memory is growing at a low rate of 9%
  5. The CPU time is growing at a low rate of 13%
  6. The last column on the right (in bold) is the scalability bottleneck, growing at a rate of 47%

Download the data

Conclusion

As expected, the main bottleneck for mesh networks is the load on the network attributed to link and node updates. The worst case load would be a full re-bootstrap of the entire network, so this analysis focuses on that scenario. The bootstrap data load of the links that cross the centerline of the network goes up by 47% each time the network size doubles. Extrapolating the above simulations to bootstrapping a (truly epic) 2^40 node network:

  • Each node would take ~140KB of memory
  • Each node would consume much less than 1 second of Core i5 CPU time
  • Each centerline node would only have to switch 50-100GB

The last point seems like a lot of data for a simple bootstrap, but this would be 5-10 years in the future where 10Gb/s links would be the bare minimum, and this data can be transmitted in about a minute. Even if these extrapolations are low by a factor of 100, with the assumptions made above, the network would still perform well.

A full-scale global isochronous mesh network can scale to at least 2^40 switches

Discussion on Hacker News!

Scalable and Efficient Multi-Path Routing – Spec Update

In June, I implemented (in C#) the first draft of a scalable and efficient multi-path route-finding algorithm to use on a simulated IsoGrid. The result of this work led me to make some improvements to the IsoGrid spec. My next step is to share out this IsoGrid simulation (along with the produced data) to prove to myself and others that a mesh protocol can actually be globally-scalable.

Here’s the changelist for version 0.225 vs. 0.220:

  • Described challenges of highly-mobile nodes to providing isochronous data transit services
  • Described LinkTunnel usefulness for creating fan-out links from the local node, to allow targeting of redundancy levels
  • Required that link advertisements must declare if links are direct or EccFlowLinkTunnel based
  • Revamped LocatorHash: Moved 3DGeoHash from being embedded within the LocatorHash to just being a part of the link and node advertisements
  • Deprecated the “random trailblazing” algorithm for scalable route tracking in favor of HMLM
  • Incorporated a ton of great ideas from S/Kademlia into HMLM
  • Described the multi-path routing algorithm based on Dijkstra’s Algorithm
  • Added some detail to the LocatorHashTree to ensure efficient caching of data in the CAS system
  • Renamed HostName -> NodeInfo
  • Renamed HostNameLocatorHash -> GetNodeInfoFromLocatorHash

Here’s the latest spec:

IsoGrid Protocol Specification v0.225.

CC0

To the extent possible under law, Travis.Martin has waived all copyright and related or neighboring rights to:

IsoGrid Protocol Specification v0.225.
This work is published from: United States.

This document is still an early draft. If you’d like to help improve it, contact Travis.Martin at this domain. Discussion at Hacker News!

IsoGrid Requirements

This post is excerpted from the IsoGrid Protocol Specification v0.220. If you’d like to skip ahead, check out the spec!

These are the requirements I started with before designing the IsoGrid.

Socioeconomic Vision:

  • Lower barriers to entry in markets for goods and services that rely on networks
  • Empower individuals to improve their lives
  • Increase individual freedom

Primary Technical Requirements

  • Very-low maximum-latency bounds
    • No overcommit, no oversubscribe
    • Always QOS
  • Efficiently scales to arbitrarily high bandwidth links
  • Efficiently scales to arbitrarily high node/switch count
  • Mesh Topology
    • Multi-path redundancy
    • Disaster Resistant
    • Seamless connectivity for mobile and “Internet of Things” nodes
    • Avoid global protocol mandates that limit economic freedom

Secondary Tech Requirements:

  • Differential GPS everywhere, even indoors?
  • Great multi-cast
    • Any switch is allowed to be a multi-caster
  • Support for asymmetric links
  • Enable high-quality crowd-sourced deep-space antenna arrays
  • Enable efficient use of long-haul space-based wireless laser meshes
  • IP Tunnels over The IsoGrid should be better than existing non-LAN networks with respect to:
    • Reliability
    • Latency
    • Cost
    • Speed
    • Security

Non-Goals:

  • Does not need to be limited to wireless networks
  • Does not need to be simple, or easy
  • Does not need to fit into existing hardware
  • Does not need to work easily with existing infrastructure
  • Does not need to preserve or promote existing power structures
  • Does not need to conform to any ‘model’ of networking

Discussion is at Hacker News!

Socioeconomic Effects of TCP/IP vs. IsoGrid

This post is excerpted from the IsoGrid Protocol Specification v0.220. If you’d like to skip ahead, check out the spec!

It should be immediately clear to the reader that communication protocols, like TCP/IP, have dramatically changed the world. What is less clear, however, is that the specifics of protocol design can have wide-ranging social and economic effects, some positive, some negative.

Rail Networks are to Road Networks, as the TCP/IP Internet is to the IsoGrid

Economies of Scale
Many networks have a design that reinforces economies of scale. One can see this clearly with the train railroad network: The bigger, more interconnected systems beat out the smaller, less interconnected systems. This also creates huge barriers for new entrants, making it practically impossible for them to compete against the established providers. We submit that economies of scale with the present Internet are creating fewer and fewer providers, and concentrating control in a few individuals in the same way that the rail system of the late 1800s did. This doesn’t have to be the case though. The grid topology of our roadways doesn’t seem to have these same effects. The barrier-to-entry for personal use of the roadways is much smaller compared to that of the railway providers. How small can we make the barriers to entry in the telecommunications market?

The Railroads lead to Railroad Tycoons
The Internet lead to Internet Tycoons
Where are the Roadway Tycoons?
In the same way, the IsoGrid is designed to be less effective than the Internet at centralizing wealth and power.

Isochronous Streams
The “Iso” in IsoGrid is short for Isochronous, meaning ‘same time’. Isochronous means that bits are sent (and then arrive) at a specific well-defined frequency. A theoretical isochronous stream running at a frequency of 1 MHz would transmit one word of data every millionth of a second. Implementations of Isochronous protocols can operate with statically sized buffers, and bounded latency guarantees. VoIP, Internet video, and Internet radio are best sent over an Isochronous connection. Over 50% of peak Internet traffic is actually perfectly suited to Isochronous streams. The early POTS telephone network operated with an analog audio stream, and so early digital communications protocols that evolved from this network could be considered Isochronous. However, over time, the world has instead settled on a packetized asynchronous solution, which is now called the Internet.
Being based on packets, the Internet has terrible support for isochronous connections. This is why your YouTube movies always need to ‘buffer’ before playing: It’s sending a few seconds (or more) of the video to the recipient before it starts playing so that it can compensate for the randomly-timed delivery of packets. If the net had support for true isochronous connections, then it would be possible to watch YouTube and Netflix videos without having to wait for the ‘buffering’ to complete.

Topology
At its core, IP allows a maximum of 255 hops for any packet. This inherently restricts the topology of the Internet: As it stands, it can never be a world-wide mesh. Instead, you end up with large hubs and choke-points.
So far, all attempts to create interop standards for nodes that can hop between networks have been unsuccessful. The IP addressing scheme also makes it very difficult to have a mesh: IP addresses are assigned hierarchically.
The name “Inter-Net” describes the problem directly: The Internet isn’t a global network that just anyone can contribute or connect to; instead, the Internet is just a protocol for inter-connecting the world’s centrally owned and operated networks.

Discussion is at Hacker News!

What’s wrong with Internet Protocol?

This post is excerpted from the IsoGrid Protocol Specification v0.220. If you’d like to skip ahead, check out the spec!

The goal of IP was simple: Create an interop-protocol to connect the world’s networks. In this regard, IP has seen fantastic success. However, it wasn’t designed with socioeconomic goals in mind. In this day and age, when much of global commerce seems to rely on IP, it’s tempting to think that “Anything can run on IP, can’t you solve <X> with an overlay network or a blockchain?” But this would be akin to asking “Why not build the grid of roads only on top of the hub-and-spoke railway network?” When you think about the goals of the IsoGrid, you’ll see that this is a ridiculous proposal. It’s reasonable to try to rely on the existing IP infrastructure in the early phases of building its successor: Like the railways connected the cities prior to interstate highway systems.

Below are the problems I see in TCP/IP, along with the succinct requirements for my proposed network protocol that overcomes these problems.

High and Unbounded Latency

IP switches have to decode the entire header of a packet and then lookup routing tables before the packet can be routed to the next switch. But it’s worse than that, with IP, there are no guarantees that a given packet will be routed within a certain amount of time, or even serviced at all. If 10 packets arrive on 10 different links at the same time, and all 10 have the same destination link, then some of the packets need to wait for their turn. If the switch in this case only has buffers for 8 packets, then the last 2 are simply dropped.

The IsoGrid must provide bounded latency, and must provide low latency even as the network scales up.

Wasteful Underused Links

The majority of the links that comprise the Internet run at less than 50% utilization. This is related to the same latency/buffering problem above: In order to have even reasonable latency and low levels of packet-loss, links must typically be at less than 50% utilization.

The IsoGrid must allow for 100% link utilization without any increase in latency on existing connections and without suffering congestive collapse.

Limited Node/Switch/Hop Counts

IP has limits on the number of switches, nodes, and hops that make it ill-suited to an “Internet-of-Everything”.

The IsoGrid must have no limits on the number of participating nodes or switches, and routes must be able to have an arbitrarily large number of hops.

Low Redundancy

Typically, most consumers and businesses have only a single link to the IP Internet. This is often because there is only one high-speed provider at a given location. But also, Internet links are mostly paid for by link bandwidth, rather than the actual bandwidth used. It becomes cost-prohibitive to pay for multiple under-utilized links. Finally, IP itself doesn’t have good support for multi-path.

The IsoGrid must promote a mesh topology, where it actually makes sense to have more than just one link.

Centralization of Power, and thus Wealth

With the IP Internet, Economies-of-Scale make massive centralized services cheaper than distributed services (even if similarly massive). These centralized services seem to leave little room for a healthy middle class.

With the IsoGrid, distributed services should be cheaper to provide than centralized services. Distributed services can spread the benefits of a growing economy more widely.

Choke-point Surveillance and Censorship

Because the Internet and the services running on it are so centralized, powerful governmental systems have the clear capability to surveil and/or censor it.

The IsoGrid must scale up to have no Choke-points or Check-Points: You should be able talk with your neighbors without permission from a central authority.

Vulnerable to Disaster

Major damage to a critical building in most major cities is likely to bring down IP Internet service in the region for weeks or months. War, terrorism, earthquakes, or coronal mass ejections could all completely bring down the Internet, knocking out both local and long distance communications, hindering recovery efforts.

The IsoGrid must not rely on central hubs.

Tragedy of the Commons

The Internet is a Commons, where everyone is expected to behave themselves or face removal from the network by network admins. This is expensive to police. The biggest example of this is how it costs practically zero for spammers to send comment and email spam.

The IsoGrid must not suffer from Tragedy of the Commons, it should rely on micro-payments in exchange for accepting requests.

Discussion is at Hacker News!

Scalable Mesh Routing Update

Yay! Giant swaths of the IsoGrid protocol spec have survived over 2 months of me stewing over them! Over the next week or so, I may publish a few blog posts using some of the new content found in the spec.

Here’s the changelist for version 0.220 vs. 0.215:

  • Outlined the application layer protocols for the IsoGrid stack
    • Scalable mesh mapping and routing using HashMatchLogMap (HMLM)
    • Distributed content addressable storage (CAS)
    • Distributed self-certified naming using HostNameLocatorHash
    • GeoHash abstracted within LocatorHash
  • Specify how to use uPktWithReply to calculate the round trip exchange rate and PaymentCredits to an arbitrary destination at the network layer
  • Rename ‘ReplyPaymentCredits’ to ‘ReplyCostAccumulator’
  • IsoStreamRoute ‘words’ -> ‘tags’
  • Specify in more detail how multiple IsoStreamRoute tags can be packed in a single word
  • Remove vestigial ‘InBandSignal’ references
  • Simplified the EccFlow session options and specified them in more detail
    • ControlSession specified in more detail
    • Switch EccFlow from AES-GCM to AES-OCB
    • Describe plan for future EccFlow initialization protocol evolution
  • Remove multiple priorities from GetBestRoutes (how can you have multiple priorities?)
  • Expand on the Distributed Naming problem and the IsoGrid solution

Here’s the latest spec:
IsoGrid Protocol Specification v0.220.

CC0
To the extent possible under law, Travis.Martin has waived all copyright and related or neighboring rights to:
IsoGrid Protocol Specification v0.220.
This work is published from: United States.

This document is still an early draft. If you’d like to help improve it, check out the IsoGrid Forum.

The next generation of networking: A globally-scalable distributed mesh of streams

The TCP/IP Internet has:

  • High and Unbounded Latency
  • Wasteful, Underused Links
  • Limited Node/Switch/Hop Counts (no IoT support)
  • Low Redundancy
  • A Tendency to Centralize Power
  • Choke-point Surveillance and Censorship
  • Disaster Vulnerabilities
  • Tragedy of the Commons

What follows is a free and open proposal for a solution: A new globally-scalable network protocol with a mesh topology. Instead of being limited to traditional address-routed packets, the protocol uses source routing to set up bounded-latency isochronous streams avoiding the problem of congestive collapse. Once a stream is set up, the route is given a numeric name to support routing micro-packets (µPkt) both directions along the route. In order to support isochronous streams across the entire network, the framerate of every link is a power of 2 frequency relative to TCG time, this opens the door to many new scenarios that require precise relative timekeeping. Micro-payments in arbitrary settlement instruments, which are made ‘by simple agreement’ between each neighbor along a route, are used to pay for sending data across the network, avoiding the Tragedy of the Commons. Client endpoints are responsible for building up multi-path redundant link maps through the network, relying on the advertised 3D-Geohash locations of the nodes to track only a subset of nodes within a given area; providing scalability, redundancy, and wider distribution of power. Contrasted with TCP/IP, the new protocol stack’s layering model provides additional options for streams, packets, safety, reliability, robustness, latency, and extensibility. Most importantly, the entire protocol was morally designed with its socioeconomic side-effects as a guide.

IsoGrid Protocol Specification v0.215.


CC0

To the extent possible under law, Travis.Martin has waived all copyright and related or neighboring rights to:
IsoGrid Protocol Specification v0.215.
This work is published from: United States.

This document is an early draft. If you’d like to help improve it, check out the IsoGrid Forum.