Business Library

In earlier articles relating to network design, we have looked at the ways in which networking topologies can be produced using mathematical heuristics. One question which was not answered at the time was "How many different configurations of what types are possible?". I will limit this article to include only feasible designs - that is ones in which all the nodes have a path, not necessarily direct, to every other node in the network. I will also concentrate on Wide Area Networks (WAN) rather than Local Area Networks (LAN) - although in general the same rules apply.

In fact there are only five different ways of interconnecting the nodes in a network:

	1. STAR - where each node has a direct connection to a single "hub" location.
	2. TREE - (also sometimes referred to as a BUS) where the fewest number of links, (nodes-1), is used to interconnect the network. Note that a STAR is a special kind of tree. A common tree configuration is a "Minimum Spanning Tree" - where the total length of the lines making up the tree is kept to a minimum.
	3. CYCLE - a network which uses the smallest number of links possible so that there is no single point of failure. The result is a network where every node has 2 links connected to it, and the entire network can be traversed by following a path around the network in either direction. If any link fails, the network remains connected - it is now a TREE.
	4. FULL MESH - where each location has a direct link with every other. This means that each site has (nodes-1) lines connected to it, which provides optimum performance and resilience. But what about the cost?
	5. PARTIAL MESH - where each location has one or more links with other locations, and the topology is not a STAR, TREE, CYCLE, or FULL MESH. Yes you guessed it - this is the catch all!

Well, that's pretty simple isn't it? How many different ways could we connect up any particular network using only these basic styles?

The answer is given in the formula shown here - where N is the number of locations, M is the number of possible connections N*(N-1)/2, and K is the number of connections in a given configuration. This probably doesn't make a lot of sense to most people - but it is shown to highlight that it is much more complex than you might first think! With only 4 nodes, there are 42 different topologies. If there are 16 locations, there are now more than 1.3*10²¹ possibilities - 1,300,000,000,000,000,000,000! Not all of these are sensible, but the point is that the number of possible topologies quickly becomes so large that it would take an extremely long time to consider all the options even with a computer. This is why mathematical heuristics have been used for many years to help limit the number of options looked at based on some cost, performance, or business criteria.

The next snag is that as the number of nodes increases, the five basic configurations no longer produce networks which are desirable:

• The number of lines can start to become excessive,
• The length of some of the lines might be too long, hence expensive, for the amount of traffic they need to carry,
• The number of "hops" via intermediate nodes between some of the end points can become excessive, or
• Not all the sites are the same - typically a small number of locations are major sources or sinks of traffic, whereas most will contain only "end users".

The simple tool demonstrated in the network heuristic article showed a practical solution to this dilemma - to split the network into a number of hierarchical layers, in this case two. Each layer is one of the basic network types - an access network which connects nodes to concentrators, and a backbone network which connects the concentrators to the central site. There can be any number of layers and each can use any of the basic network topologies, although two or three layers are most common. The access network is often used to connect individual offices with only limited resilience - a star configuration is very common - while the backbone network is normally more resilient. The example to the right shows four star access networks interconnected by a cycle backbone network.

A three layer network will typically insert an Area network between the Access and Backbone. For example, if there are multiple countries, it may make sense to have a national area network per country - as international communications circuits are very expensive. The backbone network will then interconnect the national area networks to provide international communications.

One final question - which locations should be used as concentrators? My simple tool selected them based purely on distance in order to minimise the cost. However, in real life not all locations are suitable - a farm in the Highlands of Scotland might be a location needing access to your network, but probably not a good place to concentrate connections! My simple tool also treated all locations as being the same idealised size - in real life this will not be the case and concentration points might be based on the largest concentrations of users or computer services. The communications lines needed to carry the traffic generated by each location are also unlikely to be the same - and now the problem can start to consider where the traffic is going and if something external to the network, such as a server, can be physically moved to keep the bulk of this traffic local?

Conclusion

• Designing a practical network is a complex task.
• Tools are available, and used, to make this task easier.
• External things can be changed to make the design easier - for example moving a particular server closer to the bulk of its users is likely to reduce line costs.

If you are interested in exploring the way in which real networks are optimised, take a look at Wide Area Network Design, Concepts and Tools for Optimization which was written by Robert S. Cahn, and published by Morgan Kaufmann - and is now available from the Local Links Bookshop.