Dynamic rednet routing?

As far as I can tell (the code is very messy and undocumented), Cookiebal's Skynetapi program unnecessarily broadcasts every message to every connected node every time, wasting system resources. What I would do is:

The first time a computer (computer #1) wants to send a message to another computer (computer #4), this happens:
#1 broadcasts a FINDPATH message (containing no data but the id of itself and the recipient) to all computers within range (routing computer #2).
Each computer which received the message then broadcasts another FINDPATH message (appending its own ID to the message) until the FINDPATH message reaches computer #4.
By this time, the FINDPATH message looks something like

{FINDPATH, 1, 4, 2, 3}
{FINDPATH, origin computer, intended receipient, in-between nodes}

Computer #4 then records this path (1-2-3-4 or vice versa) and sends a PATH message to #3

{PATH, 4, 1, 3, 2}
{PATH, origin computer, intended receipient, in-between nodes}

#3 then sends a PATH message to the next node in the list (#2) containing the same message, until the PATH message reaches computer #1.
Now computers #1 and #4 know the shortest path between them and can send data directly.

{DATA, 1, 4, 2, 3, hello!}
{DATA, origin computer, intended receipient, in-between nodes, data to send}

If a routing computer is unable to pass the data on to the next node in the list, the computer notifies the origin computer, which then sends another FINDPATH.

If the receipient computer receives two FINDPATH messages (two different possible routes to pass on a message), it uses the first FINDPATH received (the path requiring the least number number of in-between nodes)

This looks like it could work; the only issue I can see is that you need to keep track of which computers the message has visited; if you don't, you could have a flood of FINDPATH messages constantly traveling in an infinite loop, which would bring your network to its knees. Just checking if the current computer is somewhere on the path should be enough, but it probably wouldn't produce optimal efficiency; the messages would eventually stop, but there would be some duplicates.

If each computer has a record of the FINDPATH messages it's seen, you can just have each computer ignore FINDPATH messages for source/destination pairs it's already processed. If you need to be able to resend the FINDPATH messages, you could also add a sequential ID and only consider a message a duplicate when it has the same ID.

I have tried this. Yes, it works, but it causes a storm of packets. The key is to use transmission IDs. However, there is one scenario that I had problems with.
In short, it's a computer sending two packets in rapid succession:

1. Computer N sends a packet to computer M with the transmission ID 1.
2. Computer M receives that packet, updates its stored ID for that computer, and then broadcasts it.
3. Immediately afterwards, computer N sends a packet to computer M with the transmission ID 2. M receives this packet, updates it's stored ID, and passes it to O.
4. Meanwhile, computer O has received packet 1 and broadcasts it to computers M and P. It then receives packet 2 and transmits that to M and P.
5. However, computer M has already received packet 2, so it's stored ID is 2. When it receives packet 1, it retransmits it (even though it has already passed said packet to O) to O, who sends it back.
6. Computer M then processes packet 2, which it erroneously transmits to O, who sends it back, and thus we enter an infinite loop of retransmit/recieve.

The only way one can completely avoid this problem is to wait until your packets have drained from the network before transmitting new packets. For large networks, one cannot know if packets have drained or not (but one could use a timeout). This impacts performance severely.

I'm sorry if that seems a bit incomprehensible. There's also the problem of privacy: If you use rednet.broadcast, then anyone can see your messages. You can mitigate this by using rednet.send and a "ping message" that is broadcasted, but that reveals a weak link in your system. The upper point still stands, though.

KillaVanilla, on 28 December 2012 - 09:31 AM said:

snip

You could store several packet id's, and clean them on a timeout. I'm coding something similar to this, but with an automatic clean-up of 1-hop connections on a timeout specified by the to-be timed-out computers. That way, a turtle may set it's delay based on movement, and in general a computer could increase over time as it realized it wasn't being shutdown too quickly.

As for efficiency, my timeouts are first handled in Lua, and then a timeout for CC is calculated from them (by the scheduler I made).

For privacy, what do you mean with weak-link? Spamming the broadcaster?

KillaVanilla, on 28 December 2012 - 09:31 AM said:

snip (infinite loop, privacy, etc)

Sorry to be a bit blunt, but did you actually read my post fully?
Okay, you do have a point about the infinite loop thing, but seeing as each in-between node

pokepal101, on 27 December 2012 - 04:34 PM said:

appends its own ID to the message

If a node knows which computers are within range (ANNOUNCE packets?), it can selectively "broadcast" to only those computers which have not yet received the packet.

Also, on the issue of privacy, if you meant anyone can see your data in the FINDPATH packets,

pokepal101, on 27 December 2012 - 04:34 PM said:

FINDPATH message (containing no data but the id of itself and the recipient)

If you meant within the DATA packets, ONION ROUTING! :D/>

Onions make your eyes water, I hope thats not the same case with the code.
:)/> What is this exactly?

HotGirlEAN, on 28 December 2012 - 03:25 PM said:

Onions make your eyes water, I hope thats not the same case with the code.
:)/> What is this exactly?

Onion routing is wrapping up your commands like a fancy game of pass the parcel (or an onion, whichever your prefer). In this example, wrapping paper represents encryption.
Computer #2 receives a parcel with a note, saying "give this to #3". #2 gives it to #3, who takes off a layer of wrapping paper (encryption) and finds another parcel with a note, saying "give this to #4". The process continues until the (now fully unwrapped) parcel reaches the receiver.

But wouldn't this cause a bunch of unwanted lag?

HotGirlEAN, on 28 December 2012 - 03:35 PM said:

But wouldn't this cause a bunch of unwanted lag?

No more lag than Skynetapi, which broadcasts every message to every computer.
This system is designed to minimise the load on in-between nodes. The path used for any message is the path (not necessarily the shortest) involving the least in-between nodes.

EDIT: Derp, thought you meant the idea in general. Yes, onion routing would probably increase lag, but if you're using a really (and I mean reealllly) simple encryption algorithm, the difference should be negligible. Unless you want to send a copy of Windows 7 over to the farlands or something.