104 replies to this topic

[CoolisTheName007]

EDIT:this discussion is being continued in this topic:Networking - Towards a complete solution

Some 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

[gmt2001]

This topic is starting to make my head hurt

CoolisTheName007, on 24 November 2012 - 11:18 AM, said:

communication handshake (not sure how to call it, basically making sure the message reached the target), would be made at this level, if necessary

Would Message Acknowledgement be what your looking for?

[CoolisTheName007]

gmt2001, on 27 November 2012 - 07:35 AM, said:

snip

Thanks for the interest! In order to simplify stuff and get something new done, I've started to think how to do a general purpose framework for networking.
See the edit on my last post.

[Lyqyd]

I've added basic route invalidation in cases where routed packets were not acknowledged by the receiving host. This seems to work quite well, but testing is not necessarily complete at this time. This update has been pushed to the main repo, so it's available if you'd like to play around with it.

[electrickite]

Lyqyd, on 13 May 2012 - 05:00 AM, said:

No hard modification of the ROM files is necessary to run this.

Can you provide any guidance on how to install this on an SMP server without modifying the ROM files? The APIs could be included in the startup file, but I'm not sure what to do with the programs folder. How would I get the reboot/shutdown/exit programs to work? Thanks!

[PaidLeber]

downloaded the latest copy of the repo from github.. installed to .minecraft/mods...etc once I start the world, I get the following from all routers and turtles that load up the api on reboot:

net:189:bad argument: string expected, got nil
Press any key to continue..

The api worked fine the last pull that I did (about a week ago). I redownloaded the api to get the routerDaemon updated.

[PaidLeber]

Ahh.. looks like I pulled from the wrong branch..

[Lyqyd]

electrickite, on 10 January 2013 - 06:13 AM, said:

Lyqyd, on 13 May 2012 - 05:00 AM, said:

No hard modification of the ROM files is necessary to run this.

Can you provide any guidance on how to install this on an SMP server without modifying the ROM files? The APIs could be included in the startup file, but I'm not sure what to do with the programs folder. How would I get the reboot/shutdown/exit programs to work? Thanks!

The reboot/shutdown/exit programs (as well as the other programs it comes with) could all go in the root of the computer's drive. Then, when you type reboot, it'll find the reboot program in the root of the drive first and run it instead of the reboot program in rom.

PaidLeber, on 13 January 2013 - 08:01 AM, said:

Ahh.. looks like I pulled from the wrong branch..

Hope you got it resolved, then! Let me know if you have further troubles with it.

[PaidLeber]

My issue is that I'm not observing any routing behavior from the routers. Here is my setup:

I have a client computer that opens a connection and sends a vector to a turtle's background server. The turtle then moves to that location using your locationapi. Works great within ~64 block radius. After about 64 blocks I can't open a connection to the turtle (i.e.default computercraft.cfg modem_range=64 value). Fine... so I added a lyqydNet router with a simple background server at 254y blocks up "satellite" from the client computer in creative mode.

From the satellite computer, I can open a connection to the turtle or the client computer. From the turtle or client computer, I can open a connection to the satellite router... but I can't get routed packets to the satellite then to the turtle.

I've also tried placing a router ~32 blocks between the client computer and the turtle, but still no luck.


client and turtle startup is:

shell.run("modread")
shell.run("netd")
net.netInit()


shell.run("turtlenav")


satellite and middle router startup is:

shell.run("modread")
shell.run("netd")
shell.run("routed")
net.netInit()

Host discovery works fine as far as I can tell.. I can see all the hosts and routers in the etc/hosts on all systems. Is there anything else that I'm missing?

[Lyqyd]

Yikes! Turtle routing is a bit of a nasty spot, still. Once a host has a cost of 0, the routing table is highly unlikely to ever pick up a further route for it (this is planned to be fixed, but hasn't happened yet). You could try grabbing the net program (not to be confused with the net api!) and run "net route flush", which should clear the routing table on the host and allow it to pick up the turtle's correct route after it reboots.

[PaidLeber]

It works to an extent, but is still pretty awesome!

Just as future record, I have to "net route flush" and reboot both endpoints (computer and turtle) to get the connection (leave the satellite router alone). If the turtle stays out of the 64 block rednet limit there are no issues.

Once the turtle comes within range of the control computer however, the control terminal will update it's routes back to the shortest hop.

Maybe in the future, allow the user to hard code a route?

If I made actual etc/hosts file read only... would that stop the client from updating its routes? I'll give it a try.

Edited by PaidLeber, 13 January 2013 - 04:23 PM.

[Lyqyd]

Well, the plan is to have the system that detects undelivered packets that have gone through a router also handle packets on peer routes, so that they can be updated automatically regardless.

Glad you've found the API useful aside from the slight issue with turtles! I'll try to set aside some time soon to fix that.

[vcordie]

Lyqyd, on 13 November 2012 - 03:17 PM, said:

*snip*
This does not work as well with turtles, where a route may become invalid (turtle has moved into the territory of another router (this is why the turtle type is tracked separately from computers)), or with computers that are removed from the network (they remain in the routing tables indefinitely, and require a concerted effort to remove fully). The second problem is the issue that the github issue is meant to address, though a correctly formulated fix may address the turtle movement problem as well.

Is the fix for the turtle movement problem a high priority, or would you have to redesign the api to use a geographic routing protocol like this guy suggested in order to get turtles to work well with a long range rednet routing network:

CoolisTheName007, on 24 November 2012 - 11:18 AM, said:

*snip*
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.
*snip*

The ability to use a combination of this API and GPS hosts to set up a group of chunk loading turtles to A.
Automatically build a combined router+gps satellite network that serves and fits inside one or multiple chunks
B. Use pathfinding api already available on this forum to send mining turtles (with enderchests) to these chunks and quarry quarry quarry
C. report to a main computer how much each turtle has mined, their current fuel level, and their current location, to manually extract turtles who are just out of fuel and done

A proper gps+networking API that has turtle support can allow, with some fancy programming and the use of other apis, the ability to automatically set up turtles who go out on their own, and mine.
Or networks that automatically set themselves up in new areas
Or instead of mining turtles, how about building turtles
Or mapping turtles
Flower picking turtles?
The possibilitys are endless, heh.

</endrant>

[Lyqyd]

vcordie, on 12 February 2013 - 04:24 AM, said:

Lyqyd, on 13 November 2012 - 03:17 PM, said:

*snip*
This does not work as well with turtles, where a route may become invalid (turtle has moved into the territory of another router (this is why the turtle type is tracked separately from computers)), or with computers that are removed from the network (they remain in the routing tables indefinitely, and require a concerted effort to remove fully). The second problem is the issue that the github issue is meant to address, though a correctly formulated fix may address the turtle movement problem as well.

Is the fix for the turtle movement problem a high priority, or would you have to redesign the api to use a geographic routing protocol like this guy suggested in order to get turtles to work well with a long range rednet routing network:

No re-design required, just a little bit of tricky changes in the routing daemon, and possibly a little new code in the net API. I'll see if I can set aside some time soon to implement this.

I removed the idiotic post about necromancy and your reply to it, by the way. This project is certainly not dead.

[vcordie]

Good to hear, huzzah!

[Nikki]

This is pretty amazing, I've been surprised by ComputerCraft a few times in the month of using it, this is one of the few times I've just been blown away by the possibilities, I can't really think of a use for it right now, but it's nice to know it's always there

[shiry]

I've been trying this cool API out but i can't seem to get it to work

Here is my testing code

When running the client the function "connection.awaitResponse" keeps crashing with "connection:170: attempt to index ? (a nil value)

client:

shell.run("modread")
shell.run("netd")
net.netInit()
serverConnection = connection.open("testserver", 21, 2)
if not serverConnection then
print("Failed to connect")

else

while true do
write("message: ")
input = read()
connection.send(serverConnection, "data", input)
messageType, message = connection.awaitResponse(serverConnection,60)
print("Recieved: "..message)


end 
end

server:

shell.run("modread")
shell.run("netd")
net.netInit()
local connections = {}

while true do
conn, messType, message = connection.listen(21)
if connections[conn] and connections[conn].status == "open" then

if messType == "data" then
connection.send(conn, "data", "did you say: "..message.."?")
end
elseif messType == "query" then

if connections[conn] then
connections[conn].status = open
connections[conn].name = connection.name(conn)
else

local connect = {}
connect.status = "open"
connect.name = connection.name(conn)
table.insert(connections, conn, connect)
end
connection.send(conn, "response", "ok")
end
end

I have been trying to go through your code to see whats up but its rather large and I figured i might not be the first to run into this problem.

Also I am running computercraft through the newest version of tekkit light

EDIT: Okay I got a bit further apparently the connection is never made i updated client and server test code, however the connection is still failing.
Can it be because I am supposed to set server name somewhere?

Edited by shiry, 07 March 2013 - 04:24 AM.

[Lyqyd]

Is your server computer's label set to "testserver"? I will look into this and see if I can duplicate the bug.

[shiry]

Lyqyd, on 07 March 2013 - 05:20 AM, said:

Is your server computer's label set to "testserver"? I will look into this and see if I can duplicate the bug.

Hmm no i didn't but doing so didn't fix my problem

[shiry]

Lyqyd, on 07 March 2013 - 05:20 AM, said:

Is your server computer's label set to "testserver"? I will look into this and see if I can duplicate the bug.

Were you successful in duplicating the error?