CellStructureRouting
Here's an outline of a possible way to organize nodes into a hierarchical cell structure in a decentralized and organic way.
In the following, "node" means a routing entity that can take an incoming payment on any of its links and convert it to an outgoing payment on any of its other links. A Ripple user on a host may have some accounts that don't convert to other accounts. In that case, the user should form multiple routing entities, so every link in each is convertible to every other link. (This is true for any Ripple routing scheme.)
Set an upper limit to the number of entities per cell at each level of the hierarchy, say 24. So max. 24 nodes per cell, 24 cells per supercell, 24 supercells per superdupercell, etc. Maybe 100 is a better number? Needs simulation.
Any node may join any cell that any of its neighbours belong to. To join a cell, it notifies those neighbours in the cell it wishes to join, who then notify their neighbours in the cell, and so on until the whole cell knows. It must also inform its previous cell, if any, that it is leaving. (This might leave room for some cheating by joining multiple cells, I'll have to think more.)
Each link for every node in a cell is known to every other node in the cell. Links are classified according to capacity (sum of available credit in either direction). Each end of a link has three states: green (OK), amber (less available credit than the capacity of the next lowest classification), and red (no available capacity). Link states are kept updated throughout the cell regularly.
Each link for every node in every neighbouring cell is also known, but updated much less frequently.
Each cell has a coordinator node, which is initially decided at the formation of the cell (there would be some method of creating a cell out of nothing when two unaffiliated nodes link together). The coordinator can assign that responsibility to another node in the cell at any time.
When a cell reaches the maximum number of nodes, it splits in two. The coordinator decides the membership of the two new cells according to some measure of connectedness, and informs all members of the cell.
The same structure applies at the next level of hierarchy: supercells are created out of connected cells, any cell may join any supercell it is connected to at any time (this decision is made by the cell's coordinator). A cell aggregates its node-level links to other cells and advertises them to neighbouring cells. Every cell in a supercell knows all the cell-level connections in the supercell, as well as cell-level connections in neighbouring supercells. A supercell has a single coordinator cell that determines how and when the supercell splits.
As soon as there are two connected nodes, they must form a cell. As soon as there are two connected cells, they must form a supercell. As soon as there are two connected supercells, they must form a superdupercell, and so on to as many levels as necessary. A node can start its own cell if it wants.
A node's routing ID is the sequence of the IDs of all the various cell levels it is a member of.
Questions
Is there a way to split without a coordinator?
It should be possible to coordinate splitting a single cell, but it seems hard to coordinate splitting a supercell or greater unless each subelement is spoken for by a single node. If a coordinator is needed to split higher-level cells, then it might as well coordinate local splitting, etc. as well.
Does the coordinator need to be the one to send updates to neighbouring cells, or can any node just pass along what they know?
Any node should be able to pass along what they know about the current state of the cell/supercell. The coordinator is purely for splitting the cell and making decisions about joining supercells.
What happens when when the coordinator goes offline?
Nothing. Any node may leave a cell that has a missing or irresponsible coordinator or is otherwise dysfunctional. Presumably other nodes would leave too, meaning there is a good likelihood they would end up together in another cell under a different coordinator Over time, cells that were managed responsibly by coordinators with very high uptime would persist the longest and have the largest membership.
What's the ideal size for a cell?
Not sure. Maybe maximum cell size should be decided by the cell coordinator, and broadcast to members as part of a cell policy bulletin message. That way cell sizes could adapt over time as network conditions change and hopefully come to some kind of happy equilibrium. This equilibrium would be democratic, since every user has equal opportunity to create their own cells with their own size policy, and unpopularly-sized cells would have dwindling membership. Likely the range of max. sizes would vary depending on the needs and capabilities of different users and/or hosts.