Networking - Towards a complete solution

Introduction:
This post is intended to be a hub for general discussion and planning of a complete networking framework (a set of programs).
It was created hoping that the several members of the CC community that showed interest in this subject over the last few days post their opinions and findings here, and that eventually this may result in collaborative project.
I will try to complete this post with anything interesting about the problem; I also will attempt to establish vocabulary in order to improve communication between developers.

Preliminary Research:
By searching Wikipedia, I first came across the Communication Protocol page, and from there to one of the models for a communication protocol, the OSI model page. Here they describe several layers on which a protocol depends, and IMO the first one counting from down that ComputerCraft doesn't has is the network layer. For building such a layer, we already have unique identifiers for computers, so all we need is a routing protocol.

However, different situations demand different protocols; e.g. a crew of turtles is a dynamic network while stationary high altitude computers would form a static network. Respectively, a geographic routing greedy-random-greedy protocol and the Babel routing protocol IMO are the basic solutions for those problems, but I'm still not sure. For more about routing protocols, Wikipedia is a good place; I've just found this paper that studies the case of mobile networks.
Also, while real-life networks suffer of radio interference and unpredictable movements of nodes, in Minecraft, with some basic setting up and tracking, nodes know exactly when they will go out of range (except in case of storms). So a routing protocol which uses this fact could end up being more lightweight.

In any case, I suggest that we (whoever is interested) try to develop a general framework to allow communication between protocols.

Basic vocabulary:
-interface: a mechanism through which two computers can communicate directly,e.g. rednet, redstone, LAN cables, http.
-node: a computer with the capability of communicating with other computers, regardless of interface.
-neighbors of a node A regarding an interface I: any computer that A can communicate with directly by using interface I. When the interface is not specified, assume that it is to all interfaces we refer.
-path: a sequence of nodes, each in range of the next one.
-network: a tuple (networkID, nodes, protocol) where the protocol is a set of rules that enables the nodes to communicate;

Network ID's allow to separate systems as wanted.

About protocols:
-the protocol may use several interfaces;
-the protocol must expose the following functionality:
–association of aliases to a computer ID
–at each node:
set an alias to the node, that will be always go with the node ID.
a data structure representing tuples (nodeID, aliases, cost) where nodeID goes through all the nodes it knows can reach inside the network (Note that some protocols don't even know who they can reach)
a messaging function(target,message); no conditions are on this function, which may fail even if the there is a path between the emitter and the target.

A node can belong to several networks..
In addition to that, there are gateways: nodes that provide a link between specifiable networks to which they belong (an exception will soon appear). Gateways (may?) must provide an alias to the networks they use that identifies them as a gateway.
Until now, i haven't mentioned how does a 'normal' node accesses networks and uses them. In this language, there would be a parasite protocol, which would be able to message direct neighbors which were either
-other parasites from the same network;
-gateways allowed to communicate with that parasite network;
This breaks the rule of gateways belonging to the networks they communicate with (shrug).
Gateways can then forward messages to the networks they belong to, or directly to other connected parasites.

For each networking case, one would decide how, if any, gateways announced their presence, or, if parasites announced their presence; if gateways send through the network info about which parasites are connected to them (that's the reason for aliases: identification of gateways spread across a network). Based on these needs, helper functions and what I'm going to call gateway protocols could be written.

Helper Programs:
I use CC-emulator for debugging, and some improvements would ease it:
- a scroll-able shell, for reading lengthy output, possibly an upgrade of this one by Espen;
- a replacement for the rednet API that would enable setting computers' positions and simulate rednet based on those;



FAQ:
-Isn't rednet enough?
Direct connections by rednet have range limitations.
-Why not using the http API to channel signals through the internet and back to Minecraft:
lame because it breaks the 4th wall and not everyone can use http.
-Hasn't someone solved this already?
Some partial solutions (do not get me wrong, the may be partial but some are fantastic) are:
-LyqydNet: a solution that lacks dynamic behavior, such as node recovery.

Loose thoughts:
-storms: (maybe) we don't want to have networks reset themselves just because 'a wild storm has appeared' and suddenly no-one is in reach . Ideas?

Wow, looks like you did your research. I look forward to reading the rest of this intelligent conversation.

I've done some work on this a few months ago. I implemented arp and a Distance Vector Routing thingy. I suspended it though. I followed two courses on networking at university now and I'm greatly interested on this subject. My ultimate goal was implementing tcp and udp on top of it and eventually port LuaSocket over so we can use existing networking programs in CC. :D/> Is that part of this discussion as well? I'd love to talk about this further here. I like your proposal on the interface, it seems complete to me. :)/>

Instead of the OSI model, why don't we use the layers from the TCP/IP suite? Not the protocols themselves, just the layers.

KillaVanilla, on 26 November 2012 - 01:15 PM said:

Instead of the OSI model, why don't we use the layers from the TCP/IP suite? Not the protocols themselves, just the layers.

They need an interface for routing and flow control.

Wouldn't that be included in the internet layer?

If you mean the internet protocol, flow control is implemented in there (it's also implemented in lower layers). It still needs an interface for routing though.

Orwell, on 26 November 2012 - 01:10 PM said:

snip

Omg, thanks, someone who isn't out of it's field of research. I heard about LuaSocket; I'm porting over luasched to computercraft, it should be on my github (now that I have require ported, it's going well, but I did replaced the module(…) technique cause it's already old story for the new Lua; also I already ported Lumen, but it has less functionality). luasched has some kind of interface for LuaSocket.

KillaVanilla, on 26 November 2012 - 01:15 PM said:

Instead of the OSI model, why don't we use the layers from the TCP/IP suite? Not the protocols themselves, just the layers.

You do realize the TCP/IP layers are the OSI model, right?

dissy, on 26 November 2012 - 01:33 PM said:

KillaVanilla, on 26 November 2012 - 01:15 PM said:

Instead of the OSI model, why don't we use the layers from the TCP/IP suite? Not the protocols themselves, just the layers.

You do realize the TCP/IP layers are the OSI model, right?

TCP/IP only implements part of the network layer (layer 3 in the OSI model) and the above layers. So it's not all of OSI. While normally a lot of of the routing is done in layer 3 of the OSI model, you might not need to use it. The internet protocol suite might suit for the conditions that rednet gives us. It depends on implementation though.

Orwell, on 26 November 2012 - 01:42 PM said:

dissy, on 26 November 2012 - 01:33 PM said:

KillaVanilla, on 26 November 2012 - 01:15 PM said:

Instead of the OSI model, why don't we use the layers from the TCP/IP suite? Not the protocols themselves, just the layers.

You do realize the TCP/IP layers are the OSI model, right?

TCP/IP only implements part of the network layer (layer 3 in the OSI model) and the above layers. So it's not all of OSI. While normally a lot of of the routing is done in layer 3 of the OSI model, you might not need to use it. The internet protocol suite might suit for the conditions that rednet gives us. It depends on implementation though.

That isn't quite correct.

Layer 1 is the physical layer, such as ethernet. Which we do have - rednet.
Layer 2 is the data layer, such as MAC addressing. It would be possible to use the unique IDs of the computers for this, or it could be reinvented.
Layer 3 is the network layer, which includes IP, TCP, and others (UDP and ICMP, for basic functionallity)
So far there is no native method to do this, but I have seen a small handfull of APIs that do provide addressing and routing. We at least know it's easily possible.

Beyond that however, we would only need to address the layer 4 (transport) layer, basically as an API to present to the user.
By definition layers 6 and 7 are for presentation and application respectively. This would be the part implimented in the users software, so not of too much concern (beyond the original API to let that happen of course)

Once a general purpose layer 2 and/or 3 is created however, it is only a matter of how complex of an API someone would want to create for how full of a stack we can have. I do agree however that an over simplified version would be preferred.

On a seperate note, I was not arguing it would be impossible, nor to match the layers exactly. My only point was the parent poster was basically saying "Instead of using OSI layers, why don't we use OSI layers!" which made no sense :P/>

On a slightly seperate note, while such a project would be a huge undertaking, I am also not trying to imply to anyone not to try! It would be very epic to pull off :D/>

I too have had the desire to have such a network stack before in computer craft, even pondered starting such a thing for a few minutes. But for me at least, it would be too big of a project to take on by myself.
Having it as a group effort would both help greatly, as well as break the task up into more manageable chunks.

I haven't worked with the nitty-gritty details of networking since around 2001, and have changed jobs (and semi-professions) a good 3 times since then. Pulling this one off will definately need a younger and more energetic crowed than I could be a part of.

(in answer to two posts above)
I was just arguing that TPC/IP is not the entire OSI model. Also, tcp and udp are in the transport layer, not the networking layer. As implemented in real life, IP overlaps with the networking layer. I did say though that it could be possible that implementing TCP/IP only could suffice in the case of rednet. So we're kinda on the same line I think.

Orwell, on 26 November 2012 - 02:06 PM said:

(in answer to two posts above) I was just arguing that TPC/IP is not the entire OSI model. Also, tcp and udp are in the transport layer, not the networking layer. As implemented in real life, IP overlaps with the networking layer. I did say though that it could be possible that implementing TCP/IP only could suffice in the case of rednet. So we're kinda on the same line I think.

We do appear on the same page. I think the confusion is why you brought up TCP isn't the whole OSI model?
The person I replied to originally didn't say use just TCP, he said use the tcp/ip layerS (plural) instead of the OSI layers.

Anyway, I think a good starting point would be basically Layer 2.
Computers already have a unique ID in them, an equivilent of MAC addresses. Adding a real addressing scheme on top of that would provide a nice method to attach names to those addresses, and perform routing, as well as provide an API upwards to use them.

The original Arpanet used 16 bits for the IP address when it started, and only switched over to 32 bits once it out-grew that.
As long as we keep to the assumption that the addressing scheme will stay within a single world/server, 32 bit addresses should be enough for us (famous last words eh!)

While it would be wonderful to have some inter-addressing method to link multiple worlds/servers together, that adds not just complexity, but the requirement of someone to manage address allocations. Frankly, that's just a nightmare to run in a fair and level headed way (See FidoNet history for a good reason why to avoid it)

Focusing on addressing within a single world/server would keep things managable, without putting a single person in control of the entire system. A (relatively) small address space would then still work. I doubt computer craft networks will explode the way the Internet did in the 90s ;}

According to the Lua guides, Lua internally stores numbers as "double-precision floating-point", which is 32 bit. That alone would give us the same addressing space as the whole IPv4 Internet has, so I suspect it would last for a very long time.

As long as there is a built in way of avoiding address colisions, even the server admin would not have to do anything special to allow this type of networking to span the world, although that would make routing much harder.
Another option would be allow the server admin to assign blocks of addresses to users, and let the users decide if and how to route between their own networks. That adds complexity but would allow for individual LANs and linking LANs together, way more secure than say rednet-broadcast that is server wide.

Perhaps use two Lua numbers for the full address. The first assigned to you by the admin as your network number (or zero for a private network, similar to 192.168.x.x is used), and the second can be used however the user wants?

The only problem with making such assumptions is existing worlds. For example, saying computer ID 0 is the DHCP server might not be a good idea if the admin isn't the one with ID 0.
A good system would let multiple users on the same server/world setup individual networks, but with enough expandibility built in for them to link to each other in the future if they wanted to, all without involving an admin.

Some careful planning can avoid such "messes" coming up in the future.

dissy, on 26 November 2012 - 02:30 PM said:

snip

I've thought very little about addressing schemes; my main concern is to build a framework for layer 2; do you think that every routing protocol allowing aliases, i.e. something that is always externally available together with the respective computer ID (which can be info about the type of node, or an address, pratically anything) would be enough for real addressing?

I feel like we are over complicating this. What good does an amazing networking and routing system do us if it takes a wizard to set it up and configure it correctly? I think one of the main goals should be to provide a seamless interface to programs using even just the basic rednet API calls.

So, what is the threshold of user involvement in creating the network? Do special computers need to be configured for routing (as LyqydNet requires), or do certain computers decide to be routers on their own. Personally, I lean toward the former, since a computer can be set aside to not be touched for that specific purpose. Should the users have to set up anything else to get the network started? Maybe a startup entry or two?

Once we've decided on how much user involvement should be required, we move on to our sources of data. We know the following things with a little basic work:

- Computer ID
- Computer Label (do we allow unlabeled computers to join?)
- Distance from computer to router
- Type of computer

So, we know these things about every host that joins the network. It makes sense to use this data to the fullest extent. We can use the label for a more-user-friendly way of addressing each computer (more complex addressing schemes do not seem to provide any benefits in the context of rednet networking). This is especially handy for giving users a nicer way to connect to their server computers, as it is much easier to remember that your file server is named LyqydsFileServer than to remember that computer number 17 is the file server (or worse yet, that some arbitrary number the network API made up represents the file server).

After we've answered these basic questions about how the network should behave from the users' perspective, we can begin diving into what is necessary to achieve our functionality goals. So far, I believe these are our main functionality goals:

- Routing between computers.
- Automatic network connectivity if in range of network.
- Roaming computers always being routable while in network range (that is, routes to turtles changing as they move in and out of range of various routers), including normal computers that occasionally get moved.
- Minimal unnecessary packet traffic to reduce lag.
- Host-to-host unrouted traffic when hosts are in range of each other.

Basically, I think we should approach this from a more pragmatic angle: What are our functionality and presentation goals, and what tools do we use to achieve them? I've already gotten some great ideas for LyqydNet from reading this thread and thinking about all of this again. I just hope to steer the discussion more toward the practical and pragmatic side of things. Grand ideas and the "perfect" system are great, but let's not use things that are overkill on our problem set. :-)

As far as I understand, the number one limiting factor on network size and complexity is the size of the pullEvent queue. I might be misinformed, but it seems to me that there is an essentially linear queue of events that gets proccessed, and it has a size that is limited globally. Any packet sent while the queue is full will be discarded. This causes a large number of networking problems which are wholly "non-traditional".

Assume the maximum number of queued events is X.

1. If there are X+2 nodes, and each node broadcasts a message to each of its neighbors, which then broadcasts to each of its neighbors, it is possible that EVERY SINGLE MESSAGE to a specific node will get discarded every single time an attempt to send is made (unless of course the event queue is nondeterministic, which I doubt). This means updates must be sent through a more complex algorithm to get larger network sizes.
2. If more then X computers turn on at the same time (say, someone turning the game on), then if each computer has to do ANYTHING related to networking, even if it is just setting a delay timer or sending a single message, then some of them will fail to initialize.
3. If more then X computers set a timer of some sort (say, as a delay between message sends) then some of them will simply fail to trigger the timer.

Of course, I might have horribly misunderstood how the event queue in computercraft works. I will look into this more deeply, and see if it really is the central bottleneck I suspect it is. If so, then some kind of automaticly constructed tree architecture might be needed for larger scale networks.

Automatically changing routes to roaming computers would be impossible without routinely pinging each computer.
The only problem with this is that it creates a lot of spam; I know this because I have a routing algorithm that does the same thing.

I agree with Lyqyd… why all of the complication. I use my basic myNet system. you can only send a given message once every second (you can send limitless messages, the messages just cannot be identical) and it routes through every PC running it without interrupting it in any way… here is a link to the pastebin. I was also planning on adding a ping function to see if you can reach a certain ID but that is soooo easy I am sure anyone could do it and the 1 second message ban is also quite long. I am sure it could be decreased to 0.2 seconds

About the OSI mode/tcp/ip argument…

As it applies to Computercraft, this is the OSI model (At least the lower layers):
1) Physical: This is still your modem, RP cables, etc.
2) Data Link: This is rednet. Simple, dumb, direct communication based on physical addressing.
3) Network: This is where your work starts. This is the API that you create, like LyqydNet, etc.
4) Transport: This should probably also probably be a part of your API.

The rest of the layers are up to whatever program you write that makes use of your API. Remember the OSI model, it exists for a reason. Focus your efforts on layer 3 and 4.

Lyqyd, on 27 November 2012 - 09:32 AM said:

snip

I agree on the pragmatism part; however, separating functionality and establishing standards would allow different programmers to reuse code and/or make it compatible with other networks models; based on your recent post about terminal redirection, you believe at least in establishing standards.
Now for a full commentary on your post:

Lyqyd, on 27 November 2012 - 09:32 AM said:

I feel like we are over complicating this. What good does an amazing networking and routing system do us if it takes a wizard to set it up and configure it correctly? I think one of the main goals should be to provide a seamless interface to programs using even just the basic rednet API calls.
Simple rednet communication would imply knowing the inner communication protocols. But I think you mean users shouldn't worry about setting up gateways, routers and their behaviour. And they will not! Programmers just have to write a compatible routing protocol, a gateway protocol, and a parasite protocol; and provide their version of configurations. The simplest case would just 2 config files/startup otpions, specifying the config for routers (in this simple case every router is a gateway) and the config for parasites. The main idea is to provide a framework where coding networks is easy, so satisfying different needs would be easy.

So, what is the threshold of user involvement in creating the network? Do special computers need to be configured for routing (as LyqydNet requires), or do certain computers decide to be routers on their own. Personally, I lean toward the former, since a computer can be set aside to not be touched for that specific purpose. Should the users have to set up anything else to get the network started? Maybe a startup entry or two?

Once we've decided on how much user involvement should be required, we move on to our sources of data. We know the following things with a little basic work:

- Computer ID
- Computer Label (do we allow unlabeled computers to join?)
- Distance from computer to router
- Type of computer

So, we know these things about every host that joins the network. It makes sense to use this data to the fullest extent. We can use the label for a more-user-friendly way of addressing each computer (more complex addressing schemes do not seem to provide any benefits in the context of rednet networking). This is especially handy for giving users a nicer way to connect to their server computers, as it is much easier to remember that your file server is named LyqydsFileServer than to remember that computer number 17 is the file server (or worse yet, that some arbitrary number the network API made up represents the file server).
The way I've described the requirements for networks, a protocol must provide the ability to ship extra information with an ID, which can be used for sending labels; gateways can detect each other if in the same network; from there, a gateway protocol could implement behavior to notify other gateways about hosts connected to it, labels inclusive; comparing to LyqydNet, routing between routers is separated from communication with non-router endpoints, which is done by gateways.

After we've answered these basic questions about how the network should behave from the users' perspective, we can begin diving into what is necessary to achieve our functionality goals. So far, I believe these are our main functionality goals:
Different situations need different solutions; this specific characteristics you say below could be implemented with the proposed system, by coding appropriate protocols. I would like t elaborate on the required protocols later.
Loose thought: a static routing algorithm such as LyqydNet, provided it allows some kind of system for removing parasites ('hosts') from the network either manually or by specific request by the parasite, is a solution for dealing with storms without having the entire network reset.
- Routing between computers.
- Automatic network connectivity if in range of network.
- Roaming computers always being routable while in network range (that is, routes to turtles changing as they move in and out of range of various routers), including normal computers that occasionally get moved.
- Minimal unnecessary packet traffic to reduce lag.
- Host-to-host unrouted traffic when hosts are in range of each other.

Basically, I think we should approach this from a more pragmatic angle: What are our functionality and presentation goals,
Since this is supposed to be a generalist framework, any that people need to. The ones described above cover a common need are a good place to start.
and what tools do we use to achieve them? I've already gotten some great ideas for LyqydNet from reading this thread and thinking about all of this again. I just hope to steer the discussion more toward the practical and pragmatic side of things. Grand ideas and the "perfect" system are great, but let's not use things that are overkill on our problem set. :-)
Agreed. But still I want to maintain the framework, which is not difficult to code.

KaoS, on 27 November 2012 - 11:03 AM said:

I agree with Lyqyd… why all of the complication. I use my basic myNet system. you can only send a given message once every second (you can send limitless messages, the messages just cannot be identical) and it routes through every PC running it without interrupting it in any way… here is a link to the pastebin. I was also planning on adding a ping function to see if you can reach a certain ID but that is soooo easy I am sure anyone could do it and the 1 second message ban is also quite long. I am sure it could be decreased to 0.2 seconds

A system like that is indeed simple, but it's too simple to meet the goals of this project. Routing through every computer in range simultaneously is far too lag-inducing to be a viable system for large-scale routing.

KaoS, on 27 November 2012 - 11:03 AM said:

snip

The main idea of the complication (it isn't that complicated) it's that is just a support for whatever people want to code;
do not get me wrong, besides working out the framework, we'll have to work out/port/implement some set of protocols, otherwise we wouldn't have nothing. Your protocol could also be implemented, sure it's not good for median networks or servers with some load, but why not? It would be something to test on.

I made a packet routing system based on GPS locations. I never fully completed that project. how it as going to works is.

Every computer/turtle in the network is running the same node program. This means that every one of them can reroute a packet.

each node knows its GPS location. A node pings the nodes near it and they reply with there GPS location. this goes into its routing table. The nodes ping the network every few minuets. Turtles must be running a program that tracks there GPS position based on if movement work or not. these X Y Z variables are used by the node program. to send a packet the node goes through all the nodes in its routing table looking for the graphically closest node to the target or the target directly if available. The packet is sent to the nearest node where the process of finding the closes to the target is repeated until max hop is reached where packet is discarded. packets contain a header that has the GPS location and ID they want to go to and the body of that packet. This system would not requite the user to manually set up anything other that GPS towers.

I had a system working based on this method link here. it is badly coded and one of my first large projects after learning lua so it is not well designed.The main problem was that users would need to know close enough to the GPS location of the target.
[Dead Project] [ver=ALPHA]GPS based IP relay System "GP-IS"(working Internet in minecraft)
it would need layers over it to make it a reliable system

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

BigSHinyToys, on 27 November 2012 - 11:51 AM said:

snip

That's what is called geographical routing.
About a better behavior than just going back if there aren't any neighbors closer to the target: there are some based on randomizing your path choice until you find a node closer to the target, and that first keep themselves restricted to a sphere, and that progressively increase the sphere size as they fail to find new neighbors to visit. This is not a spontaneous idea, you can find it on the web, search for greedy random greedy 3D geographic routing.
; GPS isn't necessary if people have access to Rei's minimap and don't mind inserting coordinates; after that turtles can save their position to disk, but I think you know that.

KillaVanilla, on 27 November 2012 - 11:54 AM said:

snip

That's one of the tools we would need for some routing protocols; you may be interested in a project named Jumper, implemented in Lua (find it in github, user is Yonaba something) and that is a path-finding algorithm. You can use the same code to run Dijkstra's algorithm, and benefit of their implementation of binary heaps.

KillaVanilla, on 27 November 2012 - 11:54 AM said:

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

I had a labo session on OSPF the other day. It seemed to adjust routes very fast when changing the network. I'm not sure how it would behave in very large networks though. The one I had to build had only about 6 subnets and 4 pc's (each with 2 interfaces, so 8 hosts). OSPF uses path finding algorithms (usually dijkstra).

Edit: also, you don't need to actually know the graph in order to use dijkstra. You can let each node handle the calculation of the costs of each edge.

CoolisTheName007, on 27 November 2012 - 12:02 PM said:

BigSHinyToys, on 27 November 2012 - 11:51 AM said:

snip

That's what is called geographical routing.
About a better behavior than just going back if there aren't any neighbors closer to the target: there are some based on randomizing your path choice until you find a node closer to the target, and that first keep themselves restricted to a sphere, and that progressively increase the sphere size as they fail to find new neighbors to visit. This is not a spontaneous idea, you can find it on the web, search for greedy random greedy 3D geographic routing.
; GPS isn't necessary if people have access to Rei's minimap and don't mind inserting coordinates; after that turtles can save their position to disk, but I think you know that.

it didn't go back if there wasn't one close it goes through its neighbor nodes list getting a distance measurement to the target from that node then sends the packet to the closest. there is no randomization.

Orwell, on 27 November 2012 - 12:06 PM said:

KillaVanilla, on 27 November 2012 - 11:54 AM said:

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

I had a labo session on OSPF the other day. It seemed to adjust routes very fast when changing the network. I'm not sure how it would behave in very large networks though. The one I had to build had only about 6 subnets and 4 pc's (each with 2 interfaces, so 8 hosts). OSPF uses path finding algorithms (usually dijkstra).

OSPF is generally considered to be a fairly fast routing protocol, but it's not so much because it uses dijkstra as because it uses incremental routing updates.

BigSHinyToys, on 27 November 2012 - 12:07 PM said:

snip

The main idea of randomization is too ensure delivery with probability 1. Otherwise, a deterministic rule like yours could end up choosing always the same path, and:
-get stuck on a loop;
-always run out of maximum hops.

D3matt, on 27 November 2012 - 12:12 PM said:

Orwell, on 27 November 2012 - 12:06 PM said:

KillaVanilla, on 27 November 2012 - 11:54 AM said:

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

I had a labo session on OSPF the other day. It seemed to adjust routes very fast when changing the network. I'm not sure how it would behave in very large networks though. The one I had to build had only about 6 subnets and 4 pc's (each with 2 interfaces, so 8 hosts). OSPF uses path finding algorithms (usually dijkstra).

OSPF is generally considered to be a fairly fast routing protocol, but it's not so much because it uses dijkstra as because it uses incremental routing updates.

Do you mean that it's still rather slow compared to other routing mechanisms? Then you're probably right. I think when it comes to dynamically changing routes (moving turtles and such), that it's rather fast in finding a new route. Isn't that the main concern here? Communication over rednet is pretty fast, but when the route breaks and you have to wait a while for a new route, that would have a serious inconvenience.

KillaVanilla, on 27 November 2012 - 11:54 AM said:

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

…Aaaand it works.
Dijkstra's algorithm on pastebin

This implementation may not be entirely optimized, though. Tips on how to do so are welcome.

KillaVanilla, on 27 November 2012 - 12:24 PM said:

snip

As I said, binary heaps. They are just a efficient way to order sets.

CoolisTheName007, on 27 November 2012 - 12:26 PM said:

KillaVanilla, on 27 November 2012 - 12:24 PM said:

snip

As I said, binary heaps. They are just a efficient way to order sets.

Thanks, I'll look into it.

Orwell, on 27 November 2012 - 12:20 PM said:

D3matt, on 27 November 2012 - 12:12 PM said:

Orwell, on 27 November 2012 - 12:06 PM said:

KillaVanilla, on 27 November 2012 - 11:54 AM said:

In any case, I'm testing an implementation of Dijkstra's algorithm.
If this works, then the only thing stopping us is the issue of actually making the graph.

I had a labo session on OSPF the other day. It seemed to adjust routes very fast when changing the network. I'm not sure how it would behave in very large networks though. The one I had to build had only about 6 subnets and 4 pc's (each with 2 interfaces, so 8 hosts). OSPF uses path finding algorithms (usually dijkstra).

OSPF is generally considered to be a fairly fast routing protocol, but it's not so much because it uses dijkstra as because it uses incremental routing updates.

Do you mean that it's still rather slow compared to other routing mechanisms? Then you're probably right. I think when it comes to dynamically changing routes (moving turtles and such), that it's rather fast in finding a new route. Isn't that the main concern here? Communication over rednet is pretty fast, but when the route breaks and you have to wait a while for a new route, that would have a serious inconvenience.

I'm not sure I understand what you're asking, but OSPF is quite good at dynamically changing routes.

CoolisTheName007, on 27 November 2012 - 11:44 AM said:

KaoS, on 27 November 2012 - 11:03 AM said:

snip

The main idea of the complication (it isn't that complicated) it's that is just a support for whatever people want to code;
do not get me wrong, besides working out the framework, we'll have to work out/port/implement some set of protocols, otherwise we wouldn't have nothing. Your protocol could also be implemented, sure it's not good for median networks or servers with some load, but why not? It would be something to test on.

lolz not compex? :blink:/> you sir must be a genius. perhaps it's just the fact that I have absolutely no idea how networking is done on existing systems. I just did what seemed logical to me. by the 5th line of your post I had given up :)/> in my (seemingly incorrect) assumption that this was over complicated I neglected to mention how impressive this is. good work

KaoS, on 27 November 2012 - 12:42 PM said:

snip

I'll probably write a better description of the system, then maybe it'll be better understood.

CoolisTheName007, on 27 November 2012 - 11:31 AM said:

Simple rednet communication would imply knowing the inner communication protocols. But I think you mean users shouldn't worry about setting up gateways, routers and their behaviour. And they will not! Programmers just have to write a compatible routing protocol, a gateway protocol, and a parasite protocol; and provide their version of configurations. The simplest case would just 2 config files/startup otpions, specifying the config for routers (in this simple case every router is a gateway) and the config for parasites. The main idea is to provide a framework where coding networks is easy, so satisfying different needs would be easy.

So, if programmers are providing all of the network traffic protocols, what useful functionality does this "framework" you envision provide? It seems like this project is headed more towards creating some nebulous "framework" with very little useful function in and of itself. I had thought that the idea was to create a system which would provide a layer which takes care of all the details of routing and network connectivity, enabling the programs to use it to ignore all of the details of the implementation and simply send their data back and forth.

CoolisTheName007, on 27 November 2012 - 11:31 AM said:

Since this is supposed to be a generalist framework, any that people need to. The ones described above cover a common need are a good place to start.

Start on what? I don't see any actual content being discussed, only this "framework" with no specifics except to be an additional layer to write things for rather than creating an actual well-working networking system. I suppose I'm somewhat frustrated with the direction this project is heading because it seemed promising at first, but instead of creating one awesome networking system with some pooled talent and thought, the project is heading toward creating a framework that I think would end up being of very little practical use in subsequently creating an awesome networking system.

So, I will re-iterate the goals I see for an awesome networking system. I'd really like to see an outline of the goals you have for this framework project.

• Automatic routing of data between computers.
• Automatic connectivity to the network when in range.
• Roaming computers being routable while in network range.
• Minimal unnecessary packet traffic.
• Peer-to-peer traffic when in range of each other.
• Rednet send function override to enable routing for programs not written specifically for the API.
• An API exposed to programs written for the networking system that allows extra features:
• Socket or named port system for multiple background programs listening on one computer.
• Connection-based flow control, to make it easier to reject unwanted packets.
• ID lookup by computer label or other identifier.
• Minimal user setup required to configure network.
• Minimal work necessary on programmer's part to use the API, outside of writing the program itself.

I decided to make (yet another) routing protocol.
This protocol has a few ideas borrowed from IS-IS.

Instead of having one router that other computers register with, each computer acts as a router.
Every 30 seconds, each router broadcasts a "ping" message, and each router in range responds with a "pong" message. Both computers add each other to a "neighbor" table.
30 seconds later, an LSA (link-state advertisement) is transmitted to each neighboring node, containing a sequence ID and a list of neighboring nodes.
This LSA is then spread throughout the network.

Routing is then simple: Use Dijkstra's algorithm to find the shortest path to the destination and go from there.

No, Dijkstras is a misapplication of an algorithm into the wrong problem space.

Lets review some facts about CC, correct me if I am wrong:

1. We have a graph of nodes.
2. All edge lengths are 1.
3. Only one computer is processing one message at any given time.
4. Messages are proccessed in the order they are sent.

Just given 2, we already know that we can find shortest paths using a simple, O(n) complexity breadth first search, instead of the worse O(nlogn) complexity dijkstras. Moreover, since a breadth first search is usually implemented using a queue, if each node merely broadcasts a "node added" update to each neighbor, it will recieve the update from the closest neighbor to the updated node. Thus, each node needs to do a O(1) time complexity update to its table when it gets an add event, and a O(n) time complexty update when it gets a remove event to maintain a 100% accurate link-state diagram. Intelligently implemented, that could be reduced further for the average case.

The problem is, since the time complexity still has to be multiplied by the number of nodes, we end up with remove events costing a TOTAL of O(n^2) accross the network, as well as a O(n^2) memory cost. Is this acceptable? It would have to be tested, but with 1,000 nodes, it means 1,000,000*C operations for each change over the entire network, and a couple MB total server space taken up by the program states of all the computers. Memory-wise, this is fine, but the processing power required if all those nodes are turtles that will trigger at least one disconnect somewhere on the network every few ticks might cause some degree of trouble.

Thus, we reach the crux of the issue. The problem is not WRITING a networking program, the problem is writing a few networking programs, and then using them in different situations, all transparent to the person using the computer, who simply places a computer down, adds a file or two and a line to the startup file (or has his OS of choice do so for him) and then can freely send messages as far and wide as possible without any worry about server stability.

What CoolisTheName007 is trying to say I think is that no one algorithm will fit every single scenario, so a protocol of some kind should be established, so that different routing networks can interact. Or if not, well, that is what I think he is saying?

In any case, I will try to gather relative performance data about some networks, and maybe try to work out something for handling turtle mobility and storms.

1. You're correct.
2. I'm using the physical distance between nodes as the edge lengths in my network graph.
3. No; each computer processes messages one at a time, but many computers are doing the same thing alongside each other.
4. Correct.

Also, if one server is operating 1000 nodes, then there MAY be a few problems, but in the (minecraft) real world we only have to deal with about 100 - 200 nodes, which is a far cry from your 1000-node argument.

Are you really sure that CC is multithreaded?

Also I realize you are using distance in space as a routing metric, what was trying to point out was that to do so is far slower computationally then just making hop counts of 1.

If a networking protocol scales easily to very large numbers and has a lower server load, that would be considered a better design then a smaller, heavier one, no?

I see what you mean.

An easily scalable and lighter protocol would work better than a smaller, heavier one, true.

As for CC being multithreaded: I don't know; I simply assumed that it was.

Also, I took your advice and made an implementation that does breadth-first searches.

Lyqyd, on 27 November 2012 - 02:26 PM said:

snip

Sorry, I didn't mean this topic was intended only for the framework; the idea is to also collaborate on making the routing protocols. Personally I will have to delay my commits a bit, I suddenly can't spend too much time on CC. The goal outline you ask about is basically on the main topic, but it's about the framework, and not a specific set of protocols as you are describing. I'm going to add your goal outline for a set of protocols to the main post, if that's ok with you. As to prove that I want to collaborate on making the protocols too, here are my initial comments:

• Automatic routing of data between computers.
• Automatic connectivity to the network when in range.
• Roaming computers being routable while in network range.
• Minimal unnecessary packet traffic.
• Peer-to-peer traffic when in range of each other.
• Rednet send function override to enable routing for programs not written specifically for the API.
• An API exposed to programs written for the networking system that allows extra features:
• Socket or named port system for multiple background programs listening on one computer. I'm finishing porting luasched, and it has some socket functionality, designed to be used with LuaSocket. Perhaps their adaptation of LuaSocket to be able to work with coroutines could be useful.
• Connection-based flow control, to make it easier to reject unwanted packets. That's what I mean with network ID's, whitelists and encryption; protocols could also add their own marker to distinguish their packets from one another. Here's the prototype of a packet: 'NetworkID;ProtocolID;SenderAliases;message' where message is whatever the protocol wants.

​

• ID lookup by computer label or other identifier. That's what can be done if routing protocols allow aliases, and gateways share and keep track of them.
• Minimal user setup required to configure network.
• Minimal work necessary on programmer's part to use the API, outside of writing the program itself.

kazagistar, on 27 November 2012 - 07:01 PM said:

snip

Aleluia someone gets what I'm saying! Will be right back.
EDIT: CC is multi-threaded? That's the kind of insight I need when I'm thinking of making efficient programs.
Do you know how rednet internally works, what's it's limitations and what not? If you are already looking into it, don't mind answering, keep digging!

CoolisTheName007, on 28 November 2012 - 10:58 AM said:

- slice -

It runs alongside the shell, like so:

parallel.waitForAny(rednet.run, function() os.run({}, "rom/programs/shell") end)

Will reply more fully later, but wanted to quickly point out that CC is not multithreaded–part of the reason behind the too-long-without-yielding protection is to allow other computers a chance to think.

Added to the main topic this lines:

Helper Programs:
I use CC-emulator for debugging, and some improvements would ease it:
- a scroll-able shell, for reading lengthy output, possibly an upgrade of this one by Espen;
- a replacement for the rednet API that would enable setting computers' positions and simulate rednet based on those;

Ok, people, update:
-I've ported luasched, which I've released, but I' m thinking of going back to Lumen, that is being actively developed. These multitasking frameworks are very similar and include modifications of LuaSocket to make it work with multitasking. It also has a cool shell I hope to port.
Why porting this?
The idea is to run each protocol in it's coroutine, and using pipes/waits/ect as necessary to enable them to work together.
-About using aliases/labels to allow easy referencing:
I think we should split the problem by first coding protocols and sockets that allow only ID's, and then creating DNS servers.
Btw, simple clients should connect send messages to gateways by a generic protocol, not at socket level, I suppose? I'm having to read a lot on network structure lately.

PS: kazagistar made some tests days ago and sending n messages over rednet has the same time cost as performing n computations on a computer.

How do you test that?

Waaait, I just figured out how.

Anyways, I've slowed development on my own protocol; everyone else seems to be doing better. That, and the fact that this just doesn't interest me anymore.

Ok, I decided to re-post this from the rednet frequencies post here , because it's on topic; it's about making the current broadcast/frequencies, and consequently the automatic detection of neighbours, safe:

I don't want whitelists, because they require synchronizing the whitelist over the network; also, I want to keep lengthy encryption computations to a minimum. I'm thinking a local whitelist plus a header specifying that a msg is a broadcast to allow new members to join in. However, that msg must also validate the new member as safe, and if the msg is really independent of time and most network state, that is impossible, because an attacker can just copy it, wait for the new member to turn off and then fake it's way through by repeating the same message. So I suppose I will have to involve the sender's id somewhere in the msg, because that's one of the things rednet has, unique identifiers, and that may solve this.
EDIT: encode the new member M id in the message with a pre-shared key K; host decrypts the message and checks if decoded id matches the id given by the rednet event 1st parameter; attacker C though he has the message and M's id, won't be able to send a valid message because it would need to know K to encode it's id.
By buffering the encoded sequences, one can avoid virtually all encryption computations.
I'm not an expert in encryption, but I guess that deterministically assigning id's, plus in an ordered fashion, like it is done now, e.g. 1,2,3,… it's a killer for this idea.
Any reason it has to be this way?
EDIT:
I guess that mapping id's to some reasonably sized string in a bijective way would be enough.
Also, to ensure that the host is valid, one could send a random password encrypted in the message, and expect receiving back a certain transformation of it.

I’ve started an implementation of a full networking protocol stack, using the already existing networking protocols.
I’ve already completed (minus a few dependencies), the ethernet implementation, rdether, using modems. The code can be found here https://github.com/chorman0773/ccnet/blob/master/stack/rdether.lua

Once I finish with the deps, I intend to implement ipv4, then tcp/ip and udp/ip. More complex protocols will naturally follow.