| Brett Meador, brett.j.meador@boeing.com (A project report written under the guidance of Prof. Raj Jain) |
Download |
The mathematical subject of Topology investigates objects whose characteristics are constant through distortion. Objects can be topologically equivalent while appearing physically different. As an example, any two objects formed with a simple rubber band are topologically equivalent so long as the band is not parted. A noteworthy practical analysis technique based on Topology is Kirchoff circuit analysis. Computer Network Topology is an extension of basic Topology. This discipline examines the configuration of computer system elements and their associated interconnections. Physical Network Topology emphasizes the hardware associated with the system including workstations, remote terminals, servers, and the associated wiring between assets. Logical Network Topology (also known as Signal Topology) emphasizes the representation of data flow between nodes, not dissimilar from Graph Theory analysis. The logical topography of a network can be dynamically reconfigured when select network equipment, such as routers, is available. An example comparing Physical and Logical Topologies is provided in Figure 1
Operations Research (OR) performance analysis topics associated with Computer Network Topology tend to be concerned with logical topology instead of the purely physical. This paper will review several performance analysis study examples with the intent of demonstrating the importance of topological considerations in network design. Although the problem set in this survey is limited several of the analysis techniques discussed are applicable to other network analysis problems. Since Logical Network Topology builds upon the underlying Network Physical Topology the set of standard computer physical topologies will reviewed first as background to the performance analysis discussion. This will be followed by a brief description of Graph Theory, and then the network analysis examples.
A review of common Physical Network Topologies provides a basis for the analysis discussion presented in section 4. In this section the attributes and problems associated with Bus, Ring, Star, Tree and Mesh Network Topologies are presented.
In Bus Network Topology a single cable is used to connect all devices on the net. This cable is often referred to as the network Backbone. When communication occurs between nodes the device sending the message broadcasts to all nodes on the network, but only the desired recipient digests the message. Advantages of this type of Physical Topology include ease of installation and minimization of the required cabling. Further, failure of a node attached to the network has no effect on other nodes attached to the network. Also messages from one node can be seen near simultaneously by all other nodes on the network. Disadvantages of this configuration include performance limits on the number of network nodes, and complete network communication stoppage if the cable fails. Figure 2 shows an example of Bus Network Topology.
Ring Network Topology has each node in a network connected to two other nodes in the network in conjunction with the first and last nodes being connected. Messages from one node to another then travel from originator to destination via the set of intermediate nodes. The intermediate nodes serve as active repeaters for messages intended for other nodes. Some forms of Ring Network Topology have messages traveling in a common direction about the ring (either clockwise or counterclockwise) while other forms of this type of configuration (called Bi-directional Rings) have messages flowing in either direction with the help of two cables between each connected node. In some cases blocking devices are required in a Ring Topology Network in order to prevent packet storming, the condition where packets not consumed by a network node fall into an unlimited loop about the ring. Ring Network Topology is typically employed in networks where inter node traffic volume is small. A disadvantage of the basic Ring Network Topology is the relatively long transmission time between nodes in the ring as compared with Bus Network Topology. Further, like Bus Network Topology, failure of the cabling between any two nodes has a broader impact on network communication as a whole, possibly leaving no path from message originator to recipient. Relative inter node communication delays are still a disadvantage of the Bi-directional Ring network, however the dual nature of the cabling between nodes allows traffic to be shunted to an alternate path, thereby rectifying connection disruption between any two nodes in the network. This is a considerable reliability advantage over the basic Ring Network Topology or the Bus Network Topology. Ring Network Topologies do have unique disadvantages relative to other topologies concerning expansion or reconfiguration. If a node is added new cabling is required to connect the node to its two neighbors. Networks are not often constructed with pre-wired positions to account for expansion. Figure 3 shows examples of Ring Network Topologies.
Star Network Topology requires the use of a central top level node to which all other nodes are connected. This top level node may be a computer, or a simple switch, or just a common connection point. Messages received by the top level node can either be broadcast to all subordinate nodes, or if the top level device is of high enough fidelity, sent only to the desired subordinate node. Inter node messaging delays are reduced with this configuration. An important advantage of the Star Network Topology comes from the localization of cabling failures inherent in this configuration. Failure in the connection between the top level node and any subordinate node, or failure in a subordinate node will not disrupt the entire network. Because Star Network Topologies are commonly used in LANs spanning a larger geometric area than Bus or Ring Network Topologies. One disadvantage of this configuration is the need for more cabling. Another disadvantages lies with the top level node. Any failure in this device will halt any communication on the network. One additional limitation of the Star Network Topology concerns the limited number of top level node connection points. Figure 4 shows an example of Star Network Topology.
Tree Network Topology is constructed from either making a set of Star Network Topologies subordinate to a central node, or by linking a set of Star Network Topologies together directly via a bus, thereby distributing the functionality of the central node among several Star Network Topology top level nodes . Figure 5 provides an example of each configuration. The top level nodes from each Star Network are the elements linked via a bus in the second arrangement. In simple Tree Network Topology no Star Network Topology subordinate nodes are connected to the bus. Messages in a Tree Network Topology can be either broadcast from the central node to all interconnected Star Networks, or targeted to select Star Networks. One major advantage of the Tree Network Topology is the ease at which the network can be expanded. Expansion can be as simple as linking in an additional Star Network Topology onto the bus. Also, like the Star Network Topology there is localization of cabling failures with this configuration. However, if a Star Network top level node in the fails, or cabling to it fails an entire section of the network is lost to communication as opposed to just one subordinate node as in pure Star Network Topology.
Mesh Network Topologies capitalize on path redundancy. This Topology is preferred when traffic volume between nodes is large. A proportion of nodes in this type of network have multiple paths to another destination node. With the exception of the Bi-directional Ring ( and this was only when a failure was detected ) each of the topologies discussed so far had only one path from message source to message destination. Thus the probability of single point network failure is greatly minimized with Mesh Network Topology. A major advantage of the Mesh Network Topology is that source nodes determine the best route from sender to destination based upon such factors connectivity, speed, and pending node tasks. A disadvantage of Mesh Network Topologies is the large cost incurred in setting up the network. A further disadvantage of this type of network is the requirement for each node to have routing algorithm for path computation. A full mesh is described as each node being directly connected to every other node in the network. This type of topology is usually restricted to networks with a small number of nodes. A partial mesh is described as having some nodes in the network being indirectly connected to others in the network. Figure 6 provides an example of both full and partial mesh networks. The internet employs Mesh Network Topology.
It should be noted that variations of the described networks are common. Many networks are described as being Hybrids Topologies, combining features from two or more of the above. Figure 7 provides an example of a Star Wired Ring Network Topology. Here the top level node of a basic Star Topology network acts only to route messages in a circular sequential fashion about the subordinate nodes, as if there were a physical Ring Topology in place.
Graph theory is the study of a collection of points called vertices or nodes and any lines connecting them, called arcs. Often a cost or capacity is associated with each arc. A graph which conveys direction on each arc is called a directed graph, while one which conveys no direction or omni direction is an undirected graph. Graph theory has application in practical routing and network flow problems. It is these applications using undirected graphs that is of interest to Computer Network Topology. One of these routing problems deals with sizing arc capacity in order to accomodate traffic requirements. Another is in the determination of feasible and required node interconnectivity. A third is in the process of obtaining a subset of the overall graph, called a Spanning Tree which connects every desired node with a path, but has no paths which can start and end on the same node (such a path is called a cycle). A Spanning Tree which is constructed with the constraint of some minimum cost is called a Minimum Spanning Tree . A Spanning Tree of an example Mesh Topology Network is conveyed in Figure 8.
In simple cases the Minimum Spanning Tree problem is addressed with an algorithm that involves picking an arbitrary node and connecting it to a neighbor while preserving lowest cost, and then repeating this procedure connecting an unconnected lowest cost neighbor to the aggregate. However, this procedure may be too elementary for real world networks and other more complex algorithms may be substituted.
Topological related analysis subjects can be as varied as the possible configurations of the network. In this paper discussion will be focused on examples available in literature pertaining to the subjects of network routing, network sizing, and network corruption analysis. From these examples the reader can extrapolate alternate analysis techniques for application to related topological problems.
Reference 1 discusses an analysis approach for Minimum Spanning Tree calculation while minimizing network delay. Although the intended beneficiary of Reference 1 are LAN and MAN configurations, the approach can also be applied to Mesh Network Topology. The motivation for this calculation is the prevention of network packet looping, that is, the reception of the packet no more than once at any given node. The Minimum Spanning Tree Topology chosen by this effort remains constant for node to node message transmission until a failure occurs at some point in the underlying network, at which time the Minimum Spanning Tree Topology is re-evaluated with the remaining operational assets. The basic objective function chosen for minimization can be generally described by:
Minimize Delay = Summation of Tree Nodal Processing + Summation of Arc delays
Arc delays can develop from routers, bridges, or other traffic devices. In keeping with this equation each node in the network is represented by a MX/M/1 queue. Using this representation and Littles formula a delay at each node can be computed. Arcs delays can be computed from traffic level requirements. Thus the score by which Minimum Spanning Trees will be compared can be computed through the application of Queuing Theory in conjunction with combinatorial trials. As described in Reference 1 the computation of the Minimum Spanning Tree reduces to searching for delay minima among the set of candidate trees. Depending upon the quantity of nodes and arcs a global minimum may not be practical. Of particular concern is the requirement for the algorithm to settle on a high fidelity configuration when the tree search is halted, instead of on a local cost minimum. This is achieved through utilization of an Annealing algorithm, which in reality is a local area search which can accept suboptimal trees in order to escape local cost minima. The acceptance of suboptimal trees is implemented with a slowly decreasing probability ( the Annealing process) which is utilized after it is determined that the delays associated with the candidate tree are smaller than for the tree currently considered the likely Minimum Spanning Tree. Of interest in this article in the method of selection of candidate Minimum Spanning Trees. Upon completion of processing of the current candidate tree the next is selected from the set having all branches in common with the current tree save for one. This selection criterion assures successive trees reside within the same local search area considered by the Annealing algorithm. It should be noted that the methodology described in Reference 1 can be applied to other topological networks with cost not necessarily equating to delay. Also slight modifications to the methodology can be implemented which would allow tailoring to a particular analysis. For example reference 1 states that other queue models can be considered for the nodes, possibly increasing the processing time of the algorithm. Also other candidate tree selection schemes could be considered.
Reference 7 also discusses a computation algorithm for routing optimization in a Mesh Topology Network. However, in this analysis the packet transmission time is not the focus, rather it is the hardware inter node cabling cost which is to be minimized. The scope of this study is at the inter node load level and not that of the individual packet. In this analysis approach first the network is decomposed into a configuration of point to point links, unidirectional rings, and bi directional rings. Next constraint equations are determined to account for maximum demand level for links and rings, and the maximum bandwidth between nodes. Load assignments on the network are then determined given the constraints, and the cost associated with these assignments is recorded. This process is than repeated with different sets of load assignments. When the pool of possible assignments is exhausted, the load assignments list with smallest cost then serves as the basis for routing optimization on the network.
Reference 8 discusses the concept of a Tree-Bus Topological Network. Key to this concept is the absence of any intermediate processing, there is no active component on the net between any two given nodes, with the possible exception of some signal power boost devices. Any packet sent out from one node is sent to every node on the net. Figure 9 conveys the basic topology at work. Although the reference was written with Fiber-Optic networks in mind it is a good example of the impact of topology on network sizing.
The advantage of the Tree-Bus Topology lies in its ability to support a much larger network than simple Bus Topology due to intermediate signal amplification and inherent power features in a light signal versus an electronic one. Calculating the size of the network is then reduced to a signal loss analysis problem. As stated in reference 8 the following variables are defined.
Xdb = difference between transmitted signal and minimum detectable signal at any node
Cdb = signal loss at coupling device tying together any two busses
Bdb = signal loss at a node
K = number of nodes on all parallel Bus Networks
If the sizing is concerned with just one level of the tree:
2*(C + B* K) ≤ X
Or
K ≤ X/(2*B) minus C/B
This formula conveys the number of network nodes as a function of signal losses and minimum deltas. Note that the inclusion of power boosting devices at the intermediate node can greatly boost the number of nodes in the network.
Network viruses are small sections of code which will replicate themselves in other host routines in order to cause either runtime inefficiencies or system failures. Reference 2 discusses an analysis approach for studying virus behavior on various network topologies when a countermeasure (ostensibly a virus definition upgrade) is simultaneously propagating. Again Graph Theory provides starting point for the analysis. The network is represented by two undirected graphs. Every node in the actual network is represented on each graph, it is the arc rules and structure which varies between the two graphs. The first graph represents the virus spreading network, its arc rules are related to the type of virus being propogated ( Email connection exploitation would be an example). The second graph represents the countermeasure network, its arc rules are governed by protection dissemination strategy. A small scale example of this Graph Theory representation is provided in Figure 10.
The two graphs are tied together via two state variables to represent the common node. The first variable represents the status of the virus in the node. The second variable represents the status of the countermeasure in the node. The first variable moves between states susceptible, infected, and removed from further consideration. Acceptance of the countermeasure is probabilistic and is required to move from susceptible to removed. Node infection is required to move from susceptible to infected. The second variable moves between states unwarned, warning, and warned largely tracking the state of acceptance of the countermeasure.
Once the state transition rules have been defined for the two varables and a set of initial conditions are determined for the case in question a simulation is used to execute the model until the network arrives at a steady state. Regardless of the outcome Reference 2 conveys that the chief value collected for each case in the study consists of the quotient = (peak percentage of nodes infected) / settling time. This value is then compared against that of other simulated cases to arrive at a decision regarding an optimal countermeasure dissemination practice.
Computer Network Topology brings inherent advantages and disadvantages to any system under study. Description of some of these advantages and disadvantages for several standard physical topologies has been provided in this paper. OR performance analysis studies do not solely focus on physical topology, but logical topology as well. Graph Theory provides a useful tool in prosecuting these analysis. This paper has provided several examples of analysis approaches for dealing with topologically related problems. Those areas covered included routing analysis, network sizing, and network corruption. The techniques covered in this discussion can be adapted to related computer network applications. Understanding of Computer Network Topology is fundemental to any network analysis effort, and may prevent wasted effort in the pursuit of less productive analysis approaches.
LAN - Local Area Network
MAN - Metropolitan Area Network
OR - Operations Research
db - Decibels
[Reference 1] Cem Ersoy, Shivendra PanWar "Topological Design of Interconnected LAN-MAN Networks" IEEE INFOCON 1992.
[Reference 2] Li Chiou Chen "The Impact of Countermeasure Propagation on the Prevalence of Computer Viruses" IEEE Transactions on Systems, MAN, and Cybernetics PartB; Cybernetics Volume 34 Number 2 April 2004
[Reference 3] Geon Yoon, Dae Hyun Kwan, Soon Chang Kwon, Yong Oon Park, Young Joon Lee "Ring Topology-based Redundency Ethernet for Industrial Network" SICE-ICASE International Joint Conference 2006
[Reference 4] Nicholas F. Maxemchuk, Ram Krishnan "A Comparison of Linear and Mesh Technologies---DQDB and Manhattan Street Network" IEEE Journal on Selected Areas in Communications, Volume 11, Number 8, October 1993
[Reference 5] http://www.networktutorials.info/topology.html
[Reference 6] , http://compnetworking.about.com/od/networkingdesign/a/topologies.htm
[Reference 7] Jin Depeng, Zeng Lieguang "An Optimization Methodology for Ring Based SDH Netw" IEEE 2000
[Reference 8] Mario Gerla, Luigi Fratta "Tree Structured Fiber Optics MANs" IEEE Journal on Selected Areas in Communications, Vol 6 No. 6, July 1988
[Reference 9] John M. Harris, JefferyL. Hirst, Micheal Massinghoff "Combinatronics and Graph Theory" Springer Publishing, 2007, pages 5-7
[Reference 10] Gerald J. Lieberman, Frederick Hillier "Introduction to operations Research" McGraw –Hill 2007, pages 384-388
[Reference 11] , http://mathworld.wolfram.com/Topology.html
[Reference 12] http://mathworld.wolfram.com/Graph.html