EDIT:this discussion is being continued in this topic:
Networking - Towards a complete solutionSome info: it seems that there is quite a lot of academic work about what is called geographic routing, i.e. routing when the position of hosts are known. I will complete this post with more details later.
UPDATE: Reading
this. They propose several memory-less algorithms, the base idea is:
-reroute message to neighbors nearer to the target than the host; if not possible then perform a certain type of random walk until a host nearer to the target is found, and repeat. How the random walk is performed is where the magic lies, and that's what I'm deciphering now.
UPDATE: for using CC's shifting range,there may be some kind of transformation that would allow to treat the range as fixed. Quite selfishly, I start to dislike the variable range.
UPDATE: their algorithm limits it's update sequences to 3 hops of distance + #neighbors, and limits the memory needed in each transmitter. However, they don't specify any on_failure or on_boot behavior, which is what I'll be thinking about.
PS: Any word on the high range being one way? Cause that is a game changer
EDIT: apparently it's both ways, otherwise GPS wouldn't work.
UPDATE: finished reading and understanding the article; plus started looking into Babel, which is somehow like Cisco Systems algorithm. It is also a distance vector algorithm, but with a lot of tweaks.
UPDATE: After researching a lot, I believe the following protocols will cover most networking needs on CC:
-
Babel Protocol (BP): an advanced distance vector dynamic protocol, with configurable update speed, documented, and implemented in C; with simplifications regarding to the fact that we only use one interface, rednet, which fortunately have already been studied
here; aliases such as labels also are something that would have to be put in.
–EDIT: a possible improvement would be limiting broadcasts to starting up hosts and routers;
- a 3D greedy-random-greedy geographic routing protocol (GR), for fast changing networks such as a crew of turtles.
In general, one would need an API/abstract class that would enable communication between different kinds of networks; a request to this API would have as arguments a tuple (message, target ID, network ID).
-each computer can be present in several networks;
-independently of the protocol implementation, using coroutines one can easily make several protocols coexist in the background; but it would be preferable to provide a step function for the network processes;
-a network has a protocol and it's own separate variables; this means that, for maximum efficiency, protocols API's must be able to generate several network instances without conflicts; then again one can just reload the file in a separate environment and start a new network from there;
-network ID's would exist to enable separation of different purpose networks or even players network's, as in:
-simple agreements to not use the same ID
In case that's not enough:
-creating network ID specific white-lists, e.g. anyone connecting to network N must be on a pre-defined whitelist associated with N;
-equiping a network with encryption:
Note that encryption is only necessary when performing broadcasts, an essential feature of self configuring networks, and that shipping the API with a default encryption would preserve easy setup.
first idea: any kind of encryption that relies on a constant and/or cyclic (that repeats after a reasonable game time-scale) process to generate and synchronize an encryption key (e.g. combinations of a user entered key + os.time) is unsafe, because it is only needed to intercept a broadcast (e.g. a catastrophic one would be an hello signal), wait some time and repeat it. Unfortunately for the hacker, broadcasts in networks are used for neighbor discovery only; even if someone managed to get the right message and repeat it each minecraft day at the same interval of some seconds, the network would repair itself after a while (both in the case of BP and GR). But what about other broadcasts?
second idea: each rednet message contains the sender ID (in retrospect, this is quite a violation of the sandbox and virtual experience, but I'm grateful for it).
Say A wants to send M to B, and C is a malevolent computer listening to their communications. Also, assume both A and B share an encryption method, where decryption is D and encryption is E, that has the following property: it is very hard to replace m1 in M'=E(m1..separator..m2) by m3, knowing only m1 and M', where .. is string concatenation, mi's are strings and separator is a fixed string. IMO both private and public key methods that follow this condition should exist already. Then, A sends to B the message E(id(A)..separator..M). B decrypts it and only accepts the message if the id in the message matches the sender ID. C can't easily replace the id in the message by it's own, so we have a safe system!!!
EDIT: I've found a Lua implementation of RC4. Albeit it's the worst in security, apparently it's great for software. SECOND EDIT: Nope, won't work with a fixed key. But I do think that using the id's is the right thing.
THIRD EDIT: A more concise formulation of the most basic security (first router is trusted) is:
What would you do to ensure that B, via broadcasting, informs A of it's existence and certifies itself as belonging to the same permission group as A, without enabling malevolent computer C to do the same? (C knows both the ID's and general programs that A and B are running, but A and B can share a private key previously set). The main interest is that the key is not a white-list, though probably one could update one over the network as needed.
Take in account that an efficient algorithm is preferred.
This should be enough to allow for extremely safe transmissions in dynamic networks (see LyqydNet) , if you trust the routers in between.
For now:
-Babel protocol;
-Geographic routing protocol;
I still don't know how to model host to network /host to network to host (see a pattern?) communication. Here's a sketch.
- a to be designed protocol (NRP) to deal with non-routers (NR) intercommunication;message acknowledgement (thanks gmt2001 for the vocabulary), would be made at this level, if necessary.
Router side:
-router A can send over BP commands to NRP on other routers, e.g. router B, such as:
1-send to a certain NR believed to be connected to B a certain message; this requires no knowledge whatsoever about connected NR's.
Opposed to that, we have special tables for storing
2-send to B an update about certain or all NR's connected to A; B would store those as a (NR,A) pair.
NR side:
a-sending controls to the router side;
b-message and handshake: send message M to target T, target replies with a confirmation and we are done.
c-updating neighborhood:
c1- listens to hello signals; may be slow;
c2- broadcasts a hello, and waits for 'I heard you' replies; then it creates it's own direct NR's/R's list.
Loose notes:
-high traffic server restarts can be dealt with by saving to disk stable routing information,i.e. Babel would save to disk but geographic routing wouldn't need to, since it generates less traffic.
PS: no full editor -> no links, no indentation
