How do I diagram ping between servers on the Net?

Networking & Multiplayer
#1

If I know the ping between several servers on the Internet, how do I diagram that ping as a two-dimensional map of the “location” of those servers? Has anyone developed an algorithm to achieve this?

I want to write a program that uses that map to assemble those servers into a network for grid computing. The network hosts a world that comprises a grid of squares. Each server hosts a square, and the four closest servers host squares that border the original server’s square. The result is a mesh network.

#2

Search for RFC’s on DNS and geographical location. There are standards for approximating a PC’s latitude and longitude based on IP address (IIRC it’s actually based on the DNS…but I haven’t looked for years).

Alternatively, there are commercial providers who for a small fee do the job for you. They have names like “GeoIP”. Some have “free” versions which are less accurate.

#3

I do not want a map that measures the geographical distance between servers. I do want a map that measures the ping between servers. If two servers are separated by a vast ocean but low ping, then the those two servers should be relatively close to each other on the map, without any regard to the geographical distance between them.

#4

[quote]I do not want a map that measures the geographical distance between servers.
[/quote]
OK. But that’s what the term “location” refers to by default; it would have helped if you’d defined your concept of “location” (your definition still isn’t complete, see below).

Do some searches on graph theory and IIRC Klein maps (items in a Klein map move about, and push each other out of the way).

However, I think you need to go away and think about your problem a bit more. You don’t seem to have worked it out very well - e.g. have you tried drawing what you’re imagining, to check if it’s even possible to draw meaningfully in 2D? My current understanding of what you’re after suggests it’s not going to be possible to draw, physically, in 2D without making a complete mess. It’s like when people want to draw medium sized binary trees - they soon find out that an exponential is rather hard to draw on any finite 2D surface.

Perhaps you could do a sketch / diagram and that would save you having to explain more precisely?

#5

[quote]If I know the ping between several servers on the Internet, how do I diagram that ping as a two-dimensional map of the “location” of those servers? Has anyone developed an algorithm to achieve this?
[/quote]
Actually, do you mean “diagram”? Because:

Which sounds like you just want a data structure, not a diagram.

#6

the traceroute command will show you all the hops between two end points.

If you search the RFCs you could find the protocol for thqt and re-implement, but it might be easier just to exec otu and catch the output for processing.

JK

#7

Google didn’t find any Web pages containing “IIRC Klein maps.” However, a weighted graph in which “items in a Klein map move about, and push each other out of the way” is exactly what I need. What I need is a weighted graph that represents servers by vertices and ping by edges.

If a network hosts a world that comprises a grid of squares, then each server hosts a square in the network’s world. If a server is connected to another server, then the server’s square borders the other server’s square in the network’s world. If a client moves from square to square in the network’s world, then the client moves from server to server.

A weighted graph illustrates which squares are east, west, north, or south of which squares. A server is connected to a maximum of the four closest servers. A mesh network is the result.

If a server is connected to four servers, then the server’s square borders the four servers’ squares in the network’s world. If a server is connected to three servers, then the server’s square is at the edge of the network’s world. If a server is connected to two servers, then the server’s square is at the corner of the network’s world. If a server is connected to only one other server, then the server’s square borders the other server’s square, with nothing at the square’s other borders.

Second Life implements a similar system. Read “Enabling Player-Created Online Worlds with Grid Computing and Streaming” at http://www.gamasutra.com/resource_guide/20030916/rosedale_pfv.htm.

#8

Hmm, blablabhablahba i think you are being a little hard on him. He did say that he wanted to find the ping between servers, not the distance. In the context of his applicaiton, servers with low pings are close, servers with large pings are far. Hence, they can have a location relative to the source server.

As far as wat JC is looking for: I thought they introduced the ability in jdk 1.4 (maybe even 1.3) that allow you to do more low level networking calls (I think one such thing was ICMP?? Not sure about that it’s foggy but I thought it was used in programs such as PING to measure latency). You’ll have to look into that. However, I think the best you will be able to do is find the locations of the other hosts relative to the host that is actually measuring the latency. In other words: if you do a traceroute, you are getting the latency from your machine to each machine in the route (not the latency between each machine in the chain). I could be wrong, but i’m almost positive about this. So, that means that each host would have to run your program to measure it’s latency betwen each other host in the graph and report that information back to a central host that can then diagram the locations based on the data from each host. Sound complicated? Yeah, sorta. However, here’s a program that is very very nice with graphing:

yEd Graph Editor (JNLP enabled! and free)

This is a very very nice tool, it will attempt to layout as cleanly as possible even the most complicated graphs. I think the graph mode you will want to use is Smart Organic Layout. Once you figure out the data you want to diagram, you can possibly write a file in the format that yEd can read, and you can use the yEd tool to layout the graph.

As far as the data you are going to try to diagram, Blahblahabbahahaa is right, the diagram will look very messy if you have edges going from each node to every other node in the graph. (20 nodes will have 380 edges!) So, perhaps you only want to capture the 'closest neighbor (or in your case, the 4 closest neighbors) and attach edges between those nodes, and then let yEd lay it out for you.

But your first problem is going to be programatically findnding the ping times between those servers. Quick and dirty could be to exec a ping to each server and capture the output, but I was almost certain they added an API that allows you to write your own ping. Maybe google search on +ping and +java will turn something up.

-Chris

#9

I should have looked further: yEd uses a file storage mehanism called yFiles (found on the same site). while yEd is free, i’m not sure about yFiles. But maybe you could try creating your graphs in yFiles format and use yEd to lay it out. In any case, have fun!

-Chris

#10

Ok, last follow up. I did some searching on ICMP (needed to do full-fledged pings), and as of a 4/2003 post, there was no ability in java to do this, outside of using JNI. So, your options are as follows:

1: Take a look at http://www.geocities.com/SiliconValley/Bit/5716/ping/index_eng.html to see if a Win32-only native lib will work for you.

2: Write your own JNI lib that will get at the proper native calls.

3: Parse the output of Ping.

4: Write a program that measures the response time between sending a packet to an echo server and receiving a response. This is very inaccurate however.

5: Wait for ICMP support in the JDK (doesn’t seem to be comming any time soon).

Hope this helps.

-Chris

#11

[quote]Ok, last follow up. I did some searching on ICMP (needed to do full-fledged pings), and as of a 4/2003 post, there was no ability in java to do this, outside of using JNI. So, your options are as follows:
[/quote]
It’s in 1.5, IIRC, Not as the ability to craft arbitrary ICMP messages, but as a specific feature to support ping.

PS IIRC = If I recall correctly :slight_smile:

The real problem is not just the number of edges, it’s the fact that some people assume you can just say “take the nearest four only”, and it will work when in fact that is not necessarily a mathematically possible algorithm, unless you have a particularly cunning co-ordinate system and/or graphing algorithm.

e.g. what do you do when you have servers ABCDEFGHI like this:

A B C
D E F
G H I

and E’s four closest neighbours become A, B, F and H, but all the rest remain the same?

You now have a topology that is mathemtically impossible in 2D cartesians because you hadn’t thought about your definition of “location” and “closest” properly. Drawing it is going to be a major PITA.

If I sounded harsh it’s just because I’m pressed for time right now, and if I’ve understood jc’s aims properly, then fundamentally jc needs to go and think about this some more.

It would also help if jc put together some use-cases to explain why and how this information will be used, for instance why don’t you just make the relative locations permanent and ignore the ping time?

#12

Only had time to skim it, but…their system is completely different (I may have misunderstood from reading too fast, apologies in advance if so).

They do not move their servers around, they ahve a static topology that ignores ping times.

I’m afraid I can’t see any valid reason why you want to do what you are describing, so I’m probably missing the point somewhere here…?

#13

Well, I want to write a manager that manages a mesh network for grid computing, allows donors to donate servers to the mesh network, and intelligently incorporates those servers into the mesh network.

Items in a Klein map move about, and push each other out of the way. Thus, the Klein map represents servers by vertices and ping by edges. However, if the edges are invisible, then a scatter plot is the result. After all, we care only where servers are on the Klein map, not necessarily the ping between them.

I realize that my original idea will not work, so I devised another. The manager analyzes the Klein map, superimposes a grid of squares over the Klein map, and instructs each square’s most powerful server to host a square in the network’s world. If the first server is adjacent to the second server, then the first server’s square is adjacent to the second server’s square in the network’s world.

Alternatively, the manager analyzes the Klein map, superimposes a grid of squares over the Klein map, and clusters together each square’s servers to host a square.

#14

Yes, I came to the same conclusions as blahblahhahbabhah about the article: JC seems to be talking more about a ad hoc mesh network where, based on network latencies, the servers will arrange themselves. But, if he’s trying to recreate what they have done in second life, it’s not going to happen: You’ll end up in situations where there’s supposed to be a server to the east but that server has already been claimed as some other server’s north! It’s complicated. Plus, if this post is related to the ‘Replication of Server Sate’ post, you’ll notice that in the Second Life schema, no state is being replicated across servers (except perhaps for ‘fringe’ events that need to be seen across server boundaries, but that only ever impacts up to 4 servers.

-Chris

#15

Yes, I realize that my original idea will not work. What if a master server builds a Klein map, superimposes a grid of squares over the Klein map, creates a cluster in each square with said square’s servers, and instructs each square’s cluster to communicate with adjacent squares’ clusters only?

The grid of squares determines which squares are east, west, north, or south of which squares. Thus, a square at the center of the grid communicates with four adjacent squares, a square at the edge of the grid communicates with three adjacent servers, and a square at the corner of the grid communicates with two adjacent servers only.

#16

[quote]Yes, I realize that my original idea will not work. What if a master server builds a Klein map, superimposes a grid of squares over the Klein map, creates a cluster in each square with said square’s servers, and instructs each square’s cluster to communicate with adjacent squares’ clusters only?
[/quote]
The same problem exists: you can’t actually guarantee to make the Klein map, unless you are willing to work in a lot more than 2 dimensions.

Fundamentally you have several problems here:

[] A game where each map square is actaully a valley which you can’t see out of makes this all very sensible and clever; in similar games, ignore the next point…
[] It is foolish to try to do multi-server maps using a grid of squares and random self-organizing clusters spread over the internet. It simply doesn’t work. A lot of people have tried it and it is fundamentally really foolish - if they sat down and really thought about it they’d realise it was a dumb thing to do. I’m not suggesting you’re a fool - you’re wise enough to ask first, which is more than a lot do!
[*] It’s a bad architecture to try to do multi-server maps using a grid of squares. There’s some fundamental problems to do with synchronization that would make anyone who knew their stuff tear their hair out. In fact, a square grid is possibly one of hte most stupid things you can do, because there are obvious ways of doing it much better that are no more programming time but increase performance without increasing complexity. Shrug.

The fact that second life chose a square grid implies that their architects might not be very good - but there’s no way of being sure wihtout looking at the rest of their system; it might be that some aspect of the game design means this really doesn’t matter (in which case, fair enough). Looking at other online games, the chances are they probably hadn’t done something like this before.

#17

The OTHER big problem here ofcourse is that ping time is highly variable.

So your are either going to have to do some kind of average over a fairly long time or your grid will constantly be re-arranging itself.

#18

What if the MMOG comprises a master server that manages a distributed network of servers? If a client wants to participate in the MMOG, then the client queries the master server for a server list. Then the client connects to the server with the lowest ping.

Each server runs a common map and multicasts packets of its clients’ actions to every other server. The master server determines how many servers to which to multicast. Each packet’s header declares where on the map the packet’s client’s action occurred. If a server receives a packet in which the packet’s client’s action has no effect on the server’s own clients, then the server ignores the rest of the packet. This should substantially reduce each server’s required bandwidth.

#19

[quote]What if the MMOG comprises a master server that manages a distributed network of servers? If a client wants to participate in the MMOG, then the client queries the master server for a server list. Then the client connects to the server with the lowest ping.
[/quote]
Short answer: you’re getting into very seriously complex programming problems. Distributed systems tend to be very hard to do, to get right, and to make fast. Some people believe this is largely because the majority of programming and OS paradigms we have today were designed for non-distributed programming, so whilst we use a C derivative language to program it will always be difficult, etc. I suspect there’s a lot of truth there from what I’ve seen of some of the research environments.

But there’s also a lot of fundamental problems, mainly to do with uncertainty. A perfect OS still has a probability of crashing, even with automatic crash-prevention, because your hardware can never be perfect (cosmic rays corrupt your RAM every day, for instance). But on one PC the failure rates are so low you never need worry about this in ordinary programming - you assume that 1 + 1 always equals 2 (even though even something that simple can go wrong!). In distributed programming, the failure rates go up by a factor of billions, to the point where everything has a reasonably high chance of failing, acting in the wrong order, etc. This makes distributed programming very hard; you can check everything, but then you have so little performance you can’t run your app. Or you can check nothing, and find your app never works (note: this actually happened to The Sims Online, they couldn’t get the game to work at all for a long time, until they changed their development methodologies).

That’s a gross over simplification. If you are interested in this area in a personal sense, you should go and do a lot of background research in distributed systems - most of the books that are 10-15 years old are still 100% valid today because the same major netwokring etc problems exist (although you can ignore any chapters on “efficient algorithms for real-time backup to tape drives” etc ;D).

If you want a commercial solution now, you shouldn’t even beign to consider rolling your own. There are dozens of 3rd party systems available right now (including ours, although we soon will run out of resources to take on any more customers, at least for the next 4 months). They all have pros and cons, and few are particularly similar, so you need to evaluate each on a case-by-case basis.

#20

Or, to put it another way:

http://www.stratics.com/content/articles/mmoguide.php

The reason I’m saying this now is that the problems we’re highlighting at the moment are only the first in a list of a couple of hundred you’ll end up having to go through. If you were asking problems that were down at about number 50 then it would be worth us just answering them for you. As it is, I’m guessing you’ve not really looked at this in detail yet, and so I’m trying to make sure you understand how long a path you’re embarking on before you start :slight_smile: