Math Question: Network Theory

[Diamond]

I was considering putting these questions on sci.math but I thought I'd try here first:

I am aware of Euler's formula V+R-L=1 which applies to any network, but not much else.

Consider that each connection in a network has a finite bandwidth (like say a water pipe network, or a road traffic network). Is there topologically an optimum design of network which maximizes total bandwidth of the network (eg does the optimum network have the fewest junctions/cross-overs)? What is the relationship between network capacity and junctions (if any)?

 

[Tez]

I'm guessing its a somewhat nasty tradeoff in any real-life situations. For example, in an optical fibre network the tranmission down the fibre is almost instantaneous compared to electronic switching at junctions (a holy grail of optical communications is an "all-optical" switch - which of course will never really be all-optical since photons only interact with each other with a probability that goes something like (1/137)^8!). The signal also needs to be boosted. So I imagine most of the optimizations are extremely messy and probably NP complete.

This reminds me of the following cute puzzle: How do you connect 4 towns that lie on the vertices of a square using the shortest total length of road possible. (i.e. must be possible to drive from any town to any other town!)

 

[Diamond]

Answer: I don't know.

I just wondered if there was a topologist in the house....

 

[ceptimus]

reminds me of the following cute puzzle: How do you connect 4 towns that lie on the vertices of a square using the shortest total length of road possible. (i.e. must be possible to drive from any town to any other town!)

That ought to be over in the puzzle forum! My guess, and it is just a guess, is that the roads would look a bit like this:

[SIZE=4]\_/
/ \[/SIZE]

 

[69dodge]

Originally posted by Diamond
Consider that each connection in a network has a finite bandwidth (like say a water pipe network, or a road traffic network). Is there topologically an optimum design of network which maximizes total bandwidth of the network (eg does the optimum network have the fewest junctions/cross-overs)? What is the relationship between network capacity and junctions (if any)?

I'm not quite sure what you're asking. How are you defining "the total bandwidth of the network"? And what are we given to work with as we try to maximize it?

If you want a large bandwidth between two points, just use lots and lots of parallel connections between them. No?

 

[Tez]

Answer: I don't know.

I just wondered if there was a topologist in the house....

No

Answer: I don't know what youre asking.

Is it a pure topology question like: Does the smallest triangulation of a higher genus surface entail more nodes than that of a lower genus?

If you can phrase the question in a way I can understand I may, or may not, know the answer. Algebraic topology is one of my side passions...

 

[DanishDynamite]

I was considering putting these questions on sci.math but I thought I'd try here first:

I am aware of Euler's formula V+R-L=1 which applies to any network, but not much else.

Consider that each connection in a network has a finite bandwidth (like say a water pipe network, or a road traffic network). Is there topologically an optimum design of network which maximizes total bandwidth of the network (eg does the optimum network have the fewest junctions/cross-overs)? What is the relationship between network capacity and junctions (if any)?

There are established algorithms for determining the maximum throughput of a given network. I.e, given a network N with source s, sink t and capacities c(k) for every connection k, the maximum flow from s to t can be determined.

In regard to your question, you'll need to be a little more specific. What are the parameters of the network? Must there, for example, be a given number of nodes? Can any two nodes be connected by a maximum capacity connection? When you say "maximize total bandwith", do you mean maximizing the sum of the throughputs from any random node to any other random node? Etc, etc.

 

[EvilYeti]

Is there topologically an optimum design of network which maximizes total bandwidth of the network (eg does the optimum network have the fewest junctions/cross-overs)? What is the relationship between network capacity and junctions (if any)?

The optimum network would be each node connected to every other node, i.e. the maximum possible junctions. For example, imagine a network of 10 PC's each with a dedicated connection to each of its nine peers.

If each connection was 100Mbit full duplex, the total capacity of the network would be 9 Gigabit. Contrast with a maximum capacity of 2 Gigabit if the servers were connected via a 100MB switch.

Fully meshed networks aren't practical, hence all the research into maximizing network capacity while minimizing cost (which increases with the number of connections and junctions). In addition, in the real world there is almost always some cost, usually latency, with adding nodes to a network. So that has be taken into consideration as well.

 

[jj]

What's the traffic load?

If you dismiss an ( N^2 - N)/2 network (full connection) then you need to know what the traffic load is like.

 

[Diamond]

Thanks for the replies. I'll have to be more specific.

The network has to connect nodes using the minimum number of connections. Each node most have at least one connection each to two other nodes (for resilience in case a node is not available). If I were building a network to service say, a US state, what would be the optimum way, topologically, to build it in such a way that every node is guaranteed the bandwidth of the connections they are connected to ?

I understand (or thought I understood) that the number of junctions in the network as well as the capacity of intervening links between source and sink controls how much bandwidth is actually available. Is this correct?

My intuition says that the optimum network is a ring, but is there a mathematical way of showing this?

DD: I would like to know what those algorithms are.

 

[davidhorman]

That ought to be over in the puzzle forum! My guess, and it is just a guess, is that the roads would look a bit like this:

[SIZE=4]\_/
/ \[/SIZE]

On a square? Wouldn't that just be:

\/
/\

Edit: doh, silly me, of course you save more by having the single horizontal bar...

Reminds me though, one way to solve this "minimum road length" problem is place rods on a board, each one indicating a town, then dip the whole thing in bubble solution. Pull it back out and the bubble film will contract to the smallest length. Probably only works for simple maps though.

David

 

[69dodge]

Suppose the towns lie at the corners of a unit square.

The X-shaped roads have a total length of 2 sqrt(2) = 2.828...

The H-shaped roads have a total length of 1 + sqrt(3) = 2.732..., if the sides of the H are tilted at 30 degrees from the vertical.

 

[DanishDynamite]

DD: I would like to know what those algorithms are.

Well, writing down the algorithm would require a fair amount of common terminology and my old university textbook is in Danish. However, any book on network theory should contain Dinic's algorithm. This is the most efficient algorithm for small networks (<100 nodes). If you want to go straight to the source, the algorithm was first published by Dinic here:

E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl., 11:1277-1280, 1970

Other algorithms exist, such as the Edmonds-Karps algorithm, which are somewhat more easily accessable but less efficient.

 

[Diamond]

DD: Thanks

Is there a formula that relates the number of junctions in a network to the capacity of the network? Is there any way to work out what the optimum network (capacity) is related to the topology?

 

[DanishDynamite]

DD: Thanks

Is there a formula that relates the number of junctions in a network to the capacity of the network? Is there any way to work out what the optimum network (capacity) is related to the topology?

I'm still not 100% sure I understand the question. Earlier, you said:

The network has to connect nodes using the minimum number of connections. Each node most have at least one connection each to two other nodes (for resilience in case a node is not available).

If the above was the sum total of requirements, i.e at least two connections per node and a minimum of connections, then your intuitive solution of a ring network is obviously correct as you would have a network with an average of one connection per node. And you can't go lower than that because then at least one node would have just one or no connection. (Given n nodes, a "simple tree" topology requires n-1 connections, and a "simple tree" is the minimum topology necessary for there to be a path between any two nodes).

However, you also said:

If I were building a network to service say, a US state, what would be the optimum way, topologically, to build it in such a way that every node is guaranteed the bandwidth of the connections they are connected to ?

What exactly do you mean, here? Do you mean that each node should have the full use of the connected capacities for its own purposes (i.e. no part of the connected capacities is used for simple forwarding of messages from other nodes)? If this is the case, then your minimum network would be the maximum network (each node connected to every other node).

BTW, have you considered the need for a "cost function" based on the length of connections? If the length of connections is a factor (e.g. the cost of 100 miles of wire is more costly than 1 mile of wire) then a ring network isn't necessarily the optimal solution.