Average distance for network topologies.

  • #1
nascentmind
52
0

Homework Statement


I want to derive a general formula to calculate the average distance of the nodes in a network topology. The topologies can be line(linear), ring, mesh etc. The different nodes are numbered 0,1,2.. N-1. I understand the diameter of the network etc.

Homework Equations


None.


The Attempt at a Solution


I am doing self study and the book simply provides the formula without any proofs. I am not sure what are the techniques or where to start to solve it.
 

Answers and Replies

  • #2
verty
Homework Helper
2,185
198
Perhaps the formula is intuitively understandable?
 
  • #3
nascentmind
52
0
Well the book says the average distance is roughly (2/3)N for a linear bi directional linked network. Its does not seem intuitive for me. Can you please provide some hints?
 
  • #4
nascentmind
52
0
Hmm. In case of unidirectional link the average distance of a ring I think I could derive as follows:

The sum of distance of a node to all other nodes : 0+1+2+3..+n-1 = n(n-1)/2
Total number of distances : (n-1).
Average distance : n(n-1)/2 /n-1) = n/2.

Please verify.

Now got to figure out bidirectional links and linear array.
 
  • #5
verty
Homework Helper
2,185
198
I'm thinking that in a unidirectional ring, the round-trip distance is the whole ring, so the average round-trip distance is the whole ring, or N. In a bidirectional ring, every node is like the center node in a bidirectional linear network. That case should be easier to understand than the linear case.

I'll think some more about this. (You're right, it isn't intuitive.)
 
  • #6
verty
Homework Helper
2,185
198
Have you got enough to go on? The linear case becomes much easier to understand if you experiment with small numbers of nodes.
 
  • #7
nascentmind
52
0
Have you got enough to go on?

I am not sure. The only thing I am going with is the (sum of distances)/(number of distances).
In case of linear link is there any hint I can use? The smaller sums tend to be the following:

For a 3 node linear link:
Distances from
1 {1,2}
2 {1,1}
3 {2,1}

Generalizing
1 {1..n-1}
2 {1,1..n-2}
3 {2,1,.., n-3}
.
.
n {n-1,.. 1}

Turns out the distances form a symmetric matrix. Now is there any properties of matrices I can use to get the sum of the distances?
 
  • #8
verty
Homework Helper
2,185
198
I don't want to say too much because I think you can solve this, but I'll give a hint:

2 nodes: 11

3 nodes: 12, 11, 21
or 11, 2112

4 nodes: 123, 112, 211, 321
or 11, 2112, 321123
 
  • #9
nascentmind
52
0
Am I in the right path if I do this?

(1+1) + (2+1+1+2) + (3+2+1+1+2+3)

i.e. 2 * n * (n-1)/2 = n*(n-1).

Hence the sequence n(n-1) + (n-1)(n-2)+...
n*n2 - n[1+3+5] + [2 + 6 + 12...]
 
  • #10
verty
Homework Helper
2,185
198
Do you recall that you were trying to find the average distance? If you know the sum of distances, then...
 
  • #11
nascentmind
52
0
Do you recall that you were trying to find the average distance? If you know the sum of distances, then...
Shouldn't I find a generic formula to find the sum of the distances?

In case of 4 nodes then the average distance is 20/12.
(The total number of distances will be n*(n-1))
 
  • #12
verty
Homework Helper
2,185
198
Shouldn't I find a generic formula to find the sum of the distances?

In case of 4 nodes then the average distance is 20/12.
(The total number of distances will be n*(n-1))

It's not a matter of should or shouldn't. If you want to, then do that. I'm being obtuse just because that is what you wanted, given that you said you wanted to derive (yourself) a formula for average distance between nodes in a network.

So the rest is up to you. The last hurdle was the number of nodes but you have a formula for that, so you have all the ingredients. Now just find the answer, what is the average distance versus N nodes?
 
  • #13
nascentmind
52
0
I am sorry , I am confused. I am not able to find the sum of the distances for N nodes. I have distances for 2,3,4.. nodes. I am failing to see how I have enough ingredients here :(
 
  • #14
verty
Homework Helper
2,185
198
You don't need a generic formula for N nodes. Find the average distance for 2,3,4,...

(You'll see, it works out pretty nicely.)
 
  • #15
nascentmind
52
0
I think I can see it now. 1,1.3,1.6.. difference is ~ 0.3

So the formula would be 0.7 + 0.3n ?
 
  • #16
nascentmind
52
0
Vertigo,
Am I right? If not can you provide me some more hints?
 
  • #17
verty
Homework Helper
2,185
198
That formula is not correct. It works only for small numbers of nodes. Can you see why?
 
  • #18
nascentmind
52
0
Not sure I can see it. I wrote a small program to print for 500 nodes. Seems to follow the pattern. I am not sure whether I am approaching this problem right as I seem to be simply brute forcing a solution :(
 
  • #19
verty
Homework Helper
2,185
198
It sounds like you know a lot more now about average distance in the linear case.
 
  • #20
nascentmind
52
0
I am completely out of ideas. Any more hints you can provide?
 
  • #21
nascentmind
52
0
I don't want to say too much because I think you can solve this, but I'll give a hint:

2 nodes: 11

3 nodes: 12, 11, 21
or 11, 2112

4 nodes: 123, 112, 211, 321
or 11, 2112, 321123

Why have you rearranged those numbers? I am not sure I get it.
 
  • #22
nascentmind
52
0
Vertigo,
Can I get some help please?
 
  • #23
nascentmind
52
0
Ok I haven't given up yet.

Not simplifying I get 1,4/3,5/3,2

Using Tn = a + (n-1) *d

a = 1, n = N-1 , d = 1/3

I get (n+1)/3. Am I right at least till here? Now how do I approximate it? For large N does the 1 matter? Can I approximate it to N/3?
 
  • #24
itgulpp
1
0
Hi,

How did you calculate that 1+4/3?? what is 1 what is 4/3 I don't get it. Can you please explain
 
  • #25
nascentmind
52
0
If you have the diagram below:

A-------B-------C

Then Distance from A to B = 1
distance from B to C = 1
distance from A to C = 2
Number of distances 3.

Average distance (1+1+2)/3. = 4/3
 
  • #26
twinu89
1
0
Hmm. In case of unidirectional link the average distance of a ring I think I could derive as follows:

The sum of distance of a node to all other nodes : 0+1+2+3..+n-1 = n(n-1)/2
Total number of distances : (n-1).
Average distance : n(n-1)/2 /n-1) = n/2.

Please verify.

Now got to figure out bidirectional links and linear array.

This is correct. For bidirectional links, the number of distances would rdouble as each link is now 2-way:
Avg. distance= {n(n-1)/2} / {2(n-1)} = n/4
 
  • #27
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
39,187
8,496
For bidirectional links, the number of distances would rdouble as each link is now 2-way:
Avg. distance= {n(n-1)/2} / {2(n-1)} = n/4
That argument does not work. If you are doubling the number of links you are summing over then you should be, perhaps, doubling the sum as well. Instead, need to think about the fact that no distance now exceeds n/2.
 

Suggested for: Average distance for network topologies.

  • Last Post
Replies
7
Views
122
  • Last Post
Replies
3
Views
513
  • Last Post
Replies
24
Views
1K
Replies
1
Views
361
Replies
4
Views
454
  • Last Post
Replies
10
Views
870
Replies
3
Views
311
Top