104 replies to this topic

[CoolisTheName007]

Lyqyd, on 21 May 2012 - 12:00 AM, said:

I will say that routing tables have trouble populating if a router isn't the first computer set up, or if computers previously set up are not rebooted after the last one is set up. This is because only routers will automatically distribute their route table when a computer starts up, to avoid some serious lag issues in dense networks.

Does that means that if hosts startups before routers, all is lost? What about server restarts?
2nd EDIT: Do you mean problems on chunk loading? If so, consider:
-on 1st startup, e.g., block placement or program start, computers/turtles/routers (in the context of a more dynamic network, I would prefer the categories router/non-router) would update their routeTable: non-routers by waiting for a router to communicate, routers as usual
-then all save the routeTable to disk;
-on following startups, they reload the routeTable from disk;
-on normal operation after startup, this system is compatible with the static network that is implemented. For a new dynamic implementation, it needs behaviour that for each failed communication (failed as non-responding target during time-out) updates the routeTable and saves the new version. I suppose that's what the github issue talks about, so I would better get back to reading the API!

3rd EDIT: I thought about the problem of a computer starting up on a unknown location, and then provoking a huge network traffic as each router to which the HA packet got to had to send an update of the routerTable to everyone else (is that right?). I suggest having the new computer itself broadcast an HA, receiving the routerTable's from each reachable router, merging them somehow and sending an H(routerTable update) to each router and non-router; if the computer is a non-router it would have to distinguish between different groups of routers which aren't connected between them (maybe storing a network's members in the routerTable?).
Also, how do you deal with concurrent updates to different?
In graph language, each new edge of the connections graph is sent to everyone on the network?

That was a mess. Long story short: I want to help to make this API capable of supporting dynamic networks. In graph language, in the current version you have two kind of nodes : routers and non-routers, which forcefully are end nodes, eg. nodes with only one edge. How would you describe the new node update procedure in this language, as soon as a node enters the graph? Is every new edge sent to every router?
In a more dynamic network approach, you seem (in the issue in github) to be describing a removal procedure, that is triggered by a timeout and then the same mechanism, sending to all routers a removal message?
This would help me get an idea of where to optimize. For instance, reformulating the way connections are stored, maybe transmit the full map in a update as the trade-off for reducing communications.
I like to read mathematical papers on graphs; I found this one about dynamic networks and I'm going to be reading it.
Where did you get your ideas, or where do you think I could get some?

[Lyqyd]

We'll use hosts and routers. Routers are a subset of hosts, with additional responsibilities and properties.

Each host, when booting, announces its presence. Each host receiving an announcement sets the gateway and cost for that host to zero (it is a bad idea to attempt to use computer zero as a router for this reason). All traffic directed to nearby hosts is sent directly; routers are only used to communicate to hosts who are further than maximum range allows or that we do not know are within range yet. Each router receiving an announcement transmits its full routing table to that host. The new host, upon receipt of this table, adds paths to all of the hosts in that router's table, unless it already has better routes to those hosts. The router all sends notice of the new host to all routers it knows about (but these routers do NOT update their full list of hosts with this new knowledge at this time) In this way, all routers know about all hosts attached to the network and know how to get to these hosts. Using this method, each host on the network needs only to know which router to send its packets to in order to pass them in the direction of the host it wishes to reach; it does not need to know the full path that packet will take. It does know how many hops it will take to reach that host (cost), so that better routes can be used as they are discovered. In graph terms, each new node is told about connected routing nodes and which nodes may be reached through those routing nodes, but no further information. It may also discover other nodes nearby as they announce themselves.

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.

To address some of the strikethrough:
When initializing a network, it may not seem to be created properly until all computers have been restarted (to allow the computers to learn about each other by all of them seeing all announcement packets). That was really all the quoted post was getting at.

[CoolisTheName007]

Thanks for the fast reply!
You did give a lot of intel, on which I elaborate:
So a routing table element consists of a target (identified by ID, name and type, router or non-router ('host that is not a router' is quite long)) and the first router to which a signal must be sent in order to be forwarded to the target, which you call gateway.
So in, the case of an update triggered in router A by an HA packet sent directly by a new host B, A adds the new one edge route to it's routing table, packs an custom (cost updated, ect.) version of it's routing table for B and sends it directly to B, in what it's called a HT packet.
Then it sends( through the gateways it knows, i.e. using the routing table) to all routers, including the ones that aren't directly connected (the gateway field is overwriten as the signal travels, resulting in each router along the way storing the correct gateway), an HI packet that updates the routers with a new route to B. What you mean with:

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

The router all sends notice of the new host to all routers it knows about (but these routers do NOT update their full list of hosts with this new knowledge at this time)

is that router G receiving an HI packet sends no message to hosts about available targets?
I suppose that the net API automatically rewrites the packet gateway field as they pass through the routers.
Knowing this, in a dynamic network each node is a router, in order to keep maximum connectivity; this can cause lag issues, with this system, as you noted:

Quote

This is because only routers will automatically distribute their route table when a computer starts up, to avoid some serious lag issues in dense networks.

I thought about storing routeTable in disk memory to avoid startup lag, but that only deals with server restarts and not the following situation:

Computer B starting up is analogous to moving into range/activating/ect, something dynamic networks should handle well.
In this system, such an event in a dense network/ n computers (routers) in range of each other would trigger: a broadcast of an HA packet +each router R sending an HT packet to B + each router R sending an HI packet to each other router R' = 1+n+n*n~n^2 messages in few ticks. Is this what you meant in the above quote? Or were you just talking about multiple non-routers connecting at startup to one router?

EDIT: I'm halfway through reading the paper I linked. Their idea is to partition the graph in cliques (clusters) (a set of nodes where each node is connected to all of the other nodes in the set), and for each clique choose some boundary nodes, that will act as routers for all the other nodes in the clique. On a node startup or disconnect, they use a series of algorithms to determine an acceptable choice of clusters and boundary nodes, and updates are only sent through boundary nodes. I will complete this later with an analysis of them.
Update: see below posts, I'm now reading content linked from wikipedia.

[Lyqyd]

You are correct on the nature of the interaction with HA, HT and HI packets (Host Announcement, Host Table and Host Information, respectively, are the long names for these).

Gateway and cost values are both updated as the packet traverses the network.

The previous startup behavior was for all hosts to acknowledge the new host joining the network, so that it would have full knowledge of local computers. This caused problematic lag even in a single player game, when a cluster of computers would be loaded at once. Changing to having hosts silently update when they receive an HA and only routers pass them a full host table significantly reduced startup lag. Making all hosts routers for a dynamic network would just bring back the old behavior, only worse (since all of them would also send HI packets to all other hosts in the network).

With the advent of distance information (LyqydNet was started before it was available), we have new options. Automatic configuration of hosts into routers based on the physical layout of the network is one possibility, though not necessarily an easy one. I would be interested in seeing workable ideas for an implementation of the clique algorithm for rednet.

[CoolisTheName007]

I'm checking out the wikipedia article on routing: http://en.wikipedia.org/wiki/Routing; it seems a better summary than the first decent article I found; I could classify the method used by the paper as a link-state algorithm confirming my suspicions that calculating and updating the connection graph each update was way too many calculations. EDIT: Although, distance based organising seems interesting...
Maybe the optimized one will be better; as a last resource, one could slow down routing table updates to reduce lag; btw, the classification of LyquidNet would be an 'almost' complete distance vector algorithm (it misses the dynamic update).

EDIT:
-(Fixing excess HI packets):
Also a possible optimization for the current LyquidNet would be making the new host gather the routing tables from it's neighbours, calculating the shortest path to each router R, and sending to the calculated best gateway G a new type of packet, that agglomerates all routers with the same gateway G; for each destination gateway G', in case the routers have different gateways at that step, the package would be split up in two.
What I've just described is also a more efficient protocol to send a packet to different locations (which could be implemented separately).
A consequence of this would be eliminating the excess traffic caused by excess HI packets, but from your recent post I take that sending HT packets from routers to a new host is also a lag-heavy operation.
-(Fixing new node causing too many HT packets being emitted):
Implementing a step by step reception of HT packets?

[kazagistar]

CoolisTheName007, on 14 November 2012 - 08:45 AM, said:

What I've just described is also a more efficient protocol to send a packet to different locations (which could be implemented separately).

His code is on github... you can branch it, modify the algorithms, and then send him a pull request.

[CoolisTheName007]

kazagistar, on 14 November 2012 - 10:25 AM, said:

CoolisTheName007, on 14 November 2012 - 08:45 AM, said:

What I've just described is also a more efficient protocol to send a packet to different locations (which could be implemented separately).

His code is on github... you can branch it, modify the algorithms, and then send him a pull request.

(I meant that parentheses not as a request for implementation, but to reinforce the fact that the protocol can be used for more than sending route updates)
I know his code is on github, it's great! You asked some questions to Lyquid in the first page of comments, so I suppose you have your own ideas about this?
I will probably make pull requests after I'm sure of what to code; Lyquid has already put a great deal of work in it's API, and gathered important knowledge about routing with rednet, so I would rather cooperate/get some intel from him, instead of just reverse engineering it.
The problem of running a dynamic network is more complex than the one of a static network, or almost static as LyquidNet is, so just starting coding would be too premature.

[Lyqyd]

CoolisTheName007, on 14 November 2012 - 08:45 AM, said:

-(Fixing excess HI packets):
Also a possible optimization for the current LyquidNet would be making the new host gather the routing tables from it's neighbours, calculating the shortest path to each router R, and sending to the calculated best gateway G a new type of packet, that agglomerates all routers with the same gateway G; for each destination gateway G', in case the routers have different gateways at that step, the package would be split up in two.
What I've just described is also a more efficient protocol to send a packet to different locations (which could be implemented separately).
A consequence of this would be eliminating the excess traffic caused by excess HI packets, but from your recent post I take that sending HT packets from routers to a new host is also a lag-heavy operation.

I'm not entirely certain I followed the first sentence. A good fix for HI floods in the all-hosts-are-also-routers scenario is to have the joining host send out all of the HI packets to all of the routers it learns about from the received HT packets, rather than each router sending them out. In the all-hosts-are-also-routers scenario, this means n packets rather than n² packets. This has the problem of not discovering the best path to the host necessarily, but instead a workable path to each host. It may be possible to construct a scenario in which this method creates a multiple-hops-longer-than-necessary route, which I don't consider a good tradeoff. I think that an all-hosts-are-also-routers networking API would need to be specifically designed around that fact.

CoolisTheName007, on 14 November 2012 - 08:45 AM, said:

-(Fixing new node causing too many HT packets being emitted):
Implementing a step by step reception of HT packets?

Not sure what you mean here.

[CoolisTheName007]

I stand corrected, my HI packets fix was incomplete. As for the rest:
I mean that in order to reduce traffic flow caused by too many nodes sending their HT tables to the same new host, one could devise a protocol to slow down or parse the process in lag-relative smaller steps. I agree that a dynamic network API would have to be it's own thing, mainly due to the extra load it may cause; in general one would like to have control over how dynamic and how static a network is.
I'll finish reading the articles on the protocols defined in Wikipedia before posting more. Right now, I'm reading http://ccrg.soe.ucsc....dual.ton93.pdf linked from http://en.wikipedia.org/wiki/EIGRP.

[wilcomega]

i suggest you making a installer that downloads all the stuff for you. because i do want to use this but not download all those programs. and can i install it on every computer apart or do i have to put it in the lua folder?

[Lyqyd]

wilcomega, on 15 November 2012 - 05:29 AM, said:

i suggest you making a installer that downloads all the stuff for you. because i do want to use this but not download all those programs. and can i install it on every computer apart or do i have to put it in the lua folder?

I will probably make an installer for it at some point in the near future. My main focus right now is work on stuff for LyqydOS. Installing it on each computer will be fine, as long as you make sure to load the APIs (net, connection, netfile) before starting anything else from LyqydNet.

[wilcomega]

ok nice, i suggest you making a secure connection. that one is encrypted with a random password maybe?

[Lyqyd]

I haven't seen any good encryption implementations entirely in Lua, certainly nothing that I would trust to be an integral part of the system. Apps using LyqydNet could always use their own encryption on their messages, if desired. LyqydNet doesn't care at all what the message itself contains, so encrypted or plaintext will work just as well.

[Sukasa]

I've been trying to set up a basic network, but so far my attempt has been stymied by a crash in net

I get the error

net:185: attempt to index ? (a nil value)

after connecting the first host to a two-router network in SMP.

I am using Railcraft World Anchors to ensure both routers are loaded. The first router has the computer label "_COREROUTER," and is placed near the server spawn. The second router is "_EDGEPOINTROUTER", and is roughly 2000 blocks away. Before trying anything, I ensure that all three computers are off and that their Rednet modems are not enabled. When I start up the Edgepoint router first and then the spawn router, everything seems to work fine. netmon on the spawn router shows the line

13: HT:4,4;13:0,0;R _EDGEPOINTROUTER> @ 1358.1178

I then start up the (only) host on the network, SpawnTerm, which is also at spawn. If I then go back to _COREROUTER and check netmon's output, this is what I get:

CraftOS 1.4
13: HT:4,4;13:0,0;R _EDGEPOINTROUTER> @ 1358.1178
12: HA:4,4;C SpawnTerm @ 60.967205
13: HI:4,4;12:13,1;C SpawnTerm @ 1358.1178
net:185: attempt to index ? (a nil value)

I poked into net and found that the line in question is

if routeTable[routeNum].gateway ~= 0 and dist then

I changed that to

local r_test = routeTable[routeNum]
if r_test.gateway ~= 0 and dist then

and found that the problem is that routeTable[routeNum] is apparently nil.

On SpawnTerm, the hosts file is the following

7:13,1:R nil

Am I setting the network up wrong somehow, or could GPS hosts (running the default GPS daemons that come with CC) be interfering with lyqydnet?

EDIT: After working at this some more, I've found a bit more information.

Seems packet_recieve mangles the message somehow, and instead of returning something useful returns nil. I added some debug code to display the contents of message, id, dist, and what message was before packet_recieve() was called. The output I got from that is this:

ERROR: NIL ROUTE
MSG NIL (the variable message is nil)
ID: 13 (The ComputerID of _EDGEPOINTROUTER)
DIST: 1358.1178
ORIG: HI:4,4;12:13,1;C SpawnTerm (The string passed to packet_recieve())

[Lyqyd]

I have a sneaking suspicion that this is a bug I've solved downstream of the master repository (I believe the develop branch on github is free of this issue). Thank you for the excellent bug report; I shall be sure to investigate this evening.

[Sukasa]

If more content, such as the world or configuration files would assist in debugging, I'll be happy to supply these. Also, this problem occurs in SMP. I have not tested this in SSP.

[Lyqyd]

Okay, I think I've got it solved. If you could re-download the net API file and re-test adding a new computer in the same way, that would be much appreciated. I had apparently forgotten to special-case HI packets in the same way as HA and HT for new computers joining the network, which was the source of the problem. The latest revision should solve that issue.

Thanks again for the awesome bug report!

[Sukasa]

My pleasure. I've updated to the newer net, and the error is not occurring anymore. Unfortunately, I have a new issue for you.

It's quite the edge case in this instance, but I found a problem when using a "routers on towers, hosts on the ground" setup. Since hosts (on my server) have only a transmit range of 256 blocks at ground level, but routers are high enough to have a transmit range of nearly 2000 blocks (as per my config), there's a specific error that's possible.

Since it's the range of the transmitting modem that determines whether a packet is sent or not, it's possible (and in my case, I think has happened) that a host might avoid transmitting through a nearer router (that it can transmit to) in favour of a more distant router it cannot reach. Such an issue is showing up on my server, where I have two hosts and two routers. The routers are around Y 200, so they have a massive transmit range. The hosts are around Y 64, so their range is only a few hundred blocks. The problem I have is that the two hosts have valid routes if they cross both routers, but they see their more-distant router as the preferred route (as the route packet from that router reaches the host) instead of the nearer route with a slightly higher hop count.

The gist of the issue is that the hosts are trying to route packets through routers they cannot reach, instead of transmitting to a nearer router they can reach, because there is no confirmation that a link is two-way when establishing routes - the hosts get a packet from the router, and mistakenly assume that because they can hear the other party, the other party can hear them.

In my case, I plan on just changing transmit ranges so that they're even throughout the server independent of altitude for the time being, as a work-around.

[Lyqyd]

That's interesting. I'd have to play around with that a little bit, because as far as I am aware, the determination of whether a packet from one computer to another is based on the larger of the two ranges, such that any computer within the very large range of a high-up computer can communicate with it in both directions, even though its (shorter) range wouldn't normally allow it to. If that's not the case, it certainly brings up a sticky problem, since the range of the computer isn't really knowable.

[Sukasa]

Just as a thought, what about a simpler 'prefer longer routes, if the router is geographically closer'? If a host can get onto the network at all, then it's guaranteed that at least one router is within range of the host. Therefore, one solution (albeit not the best) is to provide a way for a host to prefer a longer route, if the first hop in that route is closer than the current 'fastest.' It bypasses the issue of not knowing your transmit capabilities and would definitely improve network resiliency at the expense of some efficiency.