Resumen de Methods and elements of graph theory and fuzzy logic for communication network management
Lissette Valdés Valdés
This thesis aims to study the applicability of graph theory and fuzzy logic elements to various management tasks of a communication network.
We focus our work on two major fields: communication networks and fuzzy logic with their two fundamental aspects (fuzzy inference and arithmetic properties of fuzzy numbers). Also, every addressed problem is defined and treated based on Graph Theory. From this perspective, we include networks associated with graphs in our research, where we interpret each of its components as graph elements. We intend to describe each problem with a high mathematical abstraction level and specify them in engineering problems. They are related to selecting the server node in a P2P (Peer to Peer) network, the optimal route in a generic communication network considering different metrics defined on its links, and establishing the shorter edge-disjoint pair of paths between servers and clients. We apply ad hoc algorithm-based techniques for a given problem and fuzzy logic-based.
We develop and propose solutions to three problems in chapters 3, 4, and 5. In the following, we summarize each of them:
Chapter 3: The server node selection according to a goodness index in the server-client path in a Peer to Peer (P2P) Network We discuss the complexity of implementing our fuzzy inference algorithm by fuzzifying the input and output variables (in our case, given a server-node path, the inputs are the number of hops and the Expected Transmission Count, and the output is the goodness index of the path. We also examine the introduction of the inference rules, the inference engine, and the defuzzification of the fuzzy solution to convert it into a single crisp value.
We analyze two different transmission scenarios: a network without obstacles and a network with obstacles between nodes. We compare our strategy with the Random Selection of the server node, which is currently the most used, and the Min-Hop strategy, which chooses the path with the minimum number of hops.
The Random Selection strategy is the least efficient in a network without obstacles concerning the required transmission time and network-level traffic load. There are no crucial differences between Min-Hop and our approach in a regular system due to the Min-Hop is very efficient in this kind of network, so the impact of fuzzy logic cannot be shown entirely in this experiment.
On the other hand, our strategy produces the best results concerning the download time for a node when obstacles are present. Also, in this scenario, the Min-Hop strategy is the least efficient because it does not consider the network's actual state but only the number of hops.
Chapter 4: Analysis of the efficiency of different cost functions in a high capacity network links to optimize the traffic load between two nodes A Communication Network Management System takes the measurements of its state variables at specific times, considering them constant in the interval between two consecutive measurements. Nevertheless, this assumption is not correct since these variables evolve in real-time. Therefore, uncertainty in measures cannot be efficiently managed using crisp variables or control based on fuzzy inference models. We face this problem by modeling the communications network as a type V fuzzy graph, where we defined the sets of nodes and links as crisp sets, but we modeled each link's cost as a triangular fuzzy number. We consider each cost function's crisp and fuzzy variant (fuzzy number) applied to the search for the shortest path between two nodes.
We based the optimal search strategies on a Dijkstra algorithm adapted to the fuzzy case where triangular fuzzy numbers are compared through their Total Integrals We perform an experimental study using a 56-nodes network based on the topology of the backbone network of Nippon Telegraph and Telephone Corporation as a reference. In the network, we calculate the total number of received bits divided by the total number of sent bits throughout an experiment (MDR). This value indicates the probability that sent data is finally received. We compare our functions and strategies with their crisp equivalents. We use for the comparison the Mean of the MDR in ten experiments. The results show that fuzzy strategy 3 surpasses their analogous crisp ones (strategies 1 and 2) slightly but in a statistically significant way. The GMDR of Strategy 5 (fuzzy) surpasses its crisp equivalent (Strategy 4), but their confidence intervals are overlapped. Thus we consider both results statistically the same. Strategies 6 and 7 have the same GMDR values with practically equal confidence intervals. Also, since these strategies search for paths with the minimum number of hops, they contribute to a lesser flow of information through the network. Therefore, Strategies 6 and 7 benefit from the low consumption of resources compared to Strategies 1 to 5. Finally, our new Strategy 8 (fuzzy), with a Global Mean Delivery Rate (GMDR) very close to 1, has a wide superior performance compared to the rest of the analyzed strategies.
Chapter 5: Search of the shortest pair of edge-disjoint paths using fuzzy costs in a high-performance network with priority traffic The communication network's survivability is very important due to the systems' different services for society and the economy. Survivability can be defined as the network's ability to continuously support the committed Quality of Services (QoS) in the presence of various failure scenarios. The system must remain operational regardless of whether a failure occurs (in a node or a line). Related to survivability is the concept of Self-Healing, in which in a saturation situation, the traffic between two nodes can be organized by dividing it between two alternative paths. That would lower the saturation conditions and improve the bandwidth of both paths. It is not our only interest that both paths are link-disjoint, but also the sum of their costs is minimal. In this way, when both paths are used simultaneously, we would be optimizing the cost of sending the information and reducing the network's saturation. On the other hand, the search for alternative paths improves the communication security of priority sources since it is more challenging to capture a complete ordered message by external elements. The difference with finding the shortest and backup paths is that using both paths simultaneously (the pair of edge-disjoint paths whose total sum of their costs is the minimum) reduces the probability of information losses and increases the security (or privacy) of communications.
As in chapter 4, we associate the network to a type V fuzzy graph whose vertices and edges correspond to the network's nodes and links, respectively. We face uncertainty in the network's operating system by considering the edges' cost as triangular fuzzy numbers. First, we briefly provide the general configuration that the shortest pair of paths should have and define a formula to compute the pair's total cost. Then, we describe an algorithm that finds the shortest pair of edge-disjoint paths in the graph (FSPPA). The FSPPA uses a fuzzy adaptation of the Modified Dijkstra algorithm (MFDA) as a sub-algorithm. We can apply the MFDA in a mixed graph containing edges and some arcs whose costs are negative triangular fuzzy numbers.
To illustrate the algorithm's effectiveness, we apply FSPPA to a network with a high traffic load. We carry out ten replications per experiment with different seeds each, and all the information flows sent between the nodes are made according to probability distributions. Each node can have two types of communication sources: source F1 (regular sending of information), which always sends the data by the shortest path between the source and destination nodes, and source F2 (priority message source), which sends the data throughout the paths of the shortest pair of edge-disjoint paths. Note that a node with source F2 can apply the FSPPA and work as source F1. We measure the transmission quality in the network through the Packet Delivery Ratio (ratio between delivered and sent packets). Having a strategy with a small number of privileged nodes with source F2 is quite interesting and useful. The algorithm proposed by us provides a solution to make this strategy works.
