No. of Full Duplex Links ?

That must be why you're taking a class, and an obvious test.

Most reputable schools expect their students to do their own research and homework. It would be better for you in the long run if you were to do so. I would suggest hitting up your local public or school library.

I agree. Every node connects to 5 other nodes. That makes a total of 30 ports connected. Each port is one end of a duplex link. Hence, 15 duplex links.

Bert

x=n*(n-1)/2

n=No. of nodes x=No. of links

=> x=6*(6-1)/2=15

Anupam schrieb:

In article , Helmut Ulrich wrote: :x=n*(n-1)/2

:n=No. of nodes :x=No. of links

Correct, that's the formula.

The other numeric response got the right answer but for the wrong reason ;-) The divide by 2 isn't "because the links are full duplex".

The correct formula, the one Helmut gave, is the closed-form solution for the summation of the series 1 + 2 + 3 + ... + N-1 .

You pick any one node to start, say A, and create a full duplex link to each of the other nodes, {B, C, D, E, F}. That's going to be N-1 links for N nodes. You then proceed to the second node, B, and create a full duplex link to each node that it hasn't already been connected to. It has already been connected to A, so the connections will go to {C, D, E, F}. That's N-2 connections. Proceed to the third node, C, and create a full duplex link to each node that it hasn't already been connected to. C has already been connected to A (step 1) and B (step 2), so {D, E, F} are left, which is N-3 links. Keep going this way and you will eventually get down to the last connection, which will run between the second last node and the last node in the list.

Total the links: (N-1) + (N-2) + (N-3) + ... + 1, which is just another way of writing 1 + 2 + 3 + ... + N-1, or

N-1 ---- \\ x / ----- x = 0

in more symbolic terms. The simple algebraic form of this summation is (N * (N-1)) / 2 [This will always be an integer because either N or N-1 will be divisible by 2.]

And that's the formulae Helmut gave. The rest of the above is just the reasoning as to *why* that formula is the correct one.

If you wanted to create a fully connected mesh from simplex links, then the number of links required to form the fully connected mesh of 6 nodes would be 30. Because for each node, you would establish one link to each of 5 other nodes. That creates 30 simplex links.

The reason only 15 links are needed in a switched mesh is because it is understood that each of the links is duplex.

The question is, does logic create the algebraic equation that describes the problem, or does algebra create the logic? I contend the former is true.

Bert

In article , Albert Manfredi wrote: :If you wanted to create a fully connected mesh from simplex links, then :the number of links required to form the fully connected mesh of 6 nodes :would be 30. Because for each node, you would establish one link to each :of 5 other nodes. That creates 30 simplex links.

It depends on what you mean by 'fully connected'. 'Fully connected' does not -necessarily- mean that traffic has to be able to flow in both directions directly between any two given links, not even when you are referring to a 'mesh' network.

For example, in graph theory, "fully connected" could mean that there is no one link that you could cut that would create two disconnected graphs. Or it could mean that there is no one link that you could cut that would destroy the possibility of traversing the graph between some pair of nodes. (Graph traversal == routing). You can create that topology with no more than 15 simplex links.

Proof: Create unidirectional links ('directed edges') from node 0 to

1, 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 to 0 Now create unidirectional links from node 0 to 2, 1 to 3, 2 to 4, 3 to 5, 4 to 0, 5 to 1. Each node ('vertex') has two outbound links, N to (N+1) mod 6, and N to (N+2) mod 6; thus cutting any one directed edge will not disconnect any node's ability to transmit. Each node/vertex also has two inbound links, (N-1) mod 6 to N, and (N-2) mod 6 to N; thus cutting any one directed edge will not disconnect any node's ability to transmit. This 12 edge topology is sufficient to ensure redundant routing. To satisfy the 'mesh' condition, add the three directed edges, 0 to 3, 1 to 4, 2 to 5. There is now some unidirectional connection between any two nodes, either allowing transmission from the first to the second or else from the second to the first. This is a 'mesh' in a graph sense. Adding extra nodes does not destroy the already established redundant routing, it just makes some of the routings more efficient. We thus have a fully connected mesh consisting of 15 simplex links. At most one intermediate hop is required to get between any two points.

More generally, this algorithm works when there are 5 or more nodes: when you have 5 or more nodes, you can create a redundant routed mesh of simplex links with N*(N-1)/2 unidirectional simplex links.

..... Besides, the question was about "full duplex links". The networking opposite of "full duplex" is not "directed simplex" but rather "half duplex" -- one direction at a time. The number of links needed for a mesh doesn't change whether the links are full duplex or half duplex. That's why your reasoning about "divide by two because of the full duplex" is faulty.

Parenthetically, the definition of "fully connected" was never in doubt in this thread. I would have expected any ambiguity in that terminology to have surfaced in a previous response, rather than at this late date. You may find the definition at

and elsewhere.

Moving on, for the Spanning Tree Protocol to work, you need a topology in which all nodes are linked with duplex links, if these links are to be candidates for the spanning tree. So in order to talk sensibly about a fully connected mesh in the context of switched Ethernet mesh networks, each link is assumed to be duplex. Since Ethernet switches are connected together with full duplex links in practice, might as well accept that these duplex links are full duplex.

If that assumption were not correct, i.e. if you wanted to create a fully connected Ethernet mesh out of simplex links, you would *still* need to create two-way paths between each node to make them eligible for the spanning tree. In this case, the number of simplex links is n(n-1). That is, any given node connects to n-1 other nodes in the mesh with an outbound link, and this must be repeated for all n nodes in the mesh.

Matter of fact, n(n-1) applies to the number of *fibers* required to create a fully connected fiber optic Ethernet mesh, or of *copper twisted pairs* required to create the fully connected Ethernet mesh up to 100BASE-TX. And 2n(n-1) twisted pair would be required for

1000BASE-T, where four twisted pair are used in each link.

Not faulty at all. If I ever said "full duplex," I take it back. I thought I said duplex plain and simple. But in practice, since we the original question *was* after all about Ethernet bridges, this is a "making a distinction when there is no difference."

Again, in the context of switched Ethernet switches, which is the context here, the derivation of n(n-1)/2 is simple enough. The fully connected two-way link mesh can be created out of simplex links. If created out of simplex links, the algebraic expression is simply derived as n(n-1). Since the links used between Ethernet switches are instead (full) duplex, each pair of simplex links between any two switches is replaced with a single link (bundling two simplex fibers or two simplex twisted pair into single cables). Therefore, trivially, the number of links in the fully connected mesh of n nodes must be n(n-1)/2. This is precisely the logic I used in my original response.

It's not essential that only one derivation exist for the solution to a problem, right? Most of the time, the same answer will emerge if the logic followed in deriving the answer was correct. (I've seen some possible exceptions to this in probability problems.) What does matter is that algebraic expressions be understood to be the codification of the result of a logical path. Not the other way around.

Bert

In article , Albert Manfredi wrote: :Parenthetically, the definition of "fully connected" was never in doubt :in this thread.

I disagree. Clearly the original question was one of a "homework assignment" or an exercise for studying for a cert; as such, we would need to know the embedding pedagogical context in order to know what was meant by the various terms for the purpose of the exercise.

:Moving on, for the Spanning Tree Protocol to work, you need a topology :in which all nodes are linked with duplex links, if these links are to :be candidates for the spanning tree.

You are correct that links must be duplex in order for Spanning Tree Protocol to work. It is also the case that Spanning Tree Protocol cannot detect unidirectional links, and defaults to leaving a link unblocked unless it hears that it should be blocked, so if there is a unidirectional link, it messes up Spanning Tree Protocol. (Cisco has developed an algorithm to detect such unidirectional links and disable them.)

On the other hand, the original question mentioned nothing about spanning tree, so restricting oneself to what is STP compatable is a strawman arguement.

:Since Ethernet switches are :connected together with full duplex links in practice, might as well :accept that these duplex links are full duplex.

Once one goes beyond 100 meters, one doesn't connect ethernet switches with full-duplex links [unless perhaps one use's Cisco Long Reach Ethernet technology]: one uses fibre, typically a pair of unidirectional fibres.

:If that assumption were not correct, i.e. if you wanted to create a :fully connected Ethernet mesh out of simplex links, you would *still* :need to create two-way paths between each node to make them eligible for :the spanning tree.

Spanning tree is an *aid*, not a *requirement*.

:In this case, the number of simplex links is n(n-1).

Of which most would promptly be pruned from the spanning tree.

Let me turn the question around: suppose one did put together a fully meshed full-duplex network with N nodes. Now suppose spanning tree compatability is a requirement. How many of those links would actually be used?

The answer is that only N-1 of those N(N-1)/2 links would be used. That's because as soon as the nodes elect a root, then *by definition* in the STP, *all* links from the root are set to 'forwarding' and any pruning takes place on the non-root nodes. But the root is connected to all other nodes (because it is fully meshed), so in order to prevent cycles, -all- the other links, from any non-root node to any other non-root node, are going to have to be pruned.

So... if you are going to introduce extraneous factors such as STP into the question, then N*(N-1) and N*(N-1)/2 are pretty useless calculations. They aren't the number of links that will be used, and they aren't the number of potential spanning trees.