Graph Theoretic Approaches for Analyzing Routes, Flows, and Subnetworks in Communication Networks PDF Download

Author: Zohre Ranjbar-Mojaveri
Publisher:
ISBN:
Category : Computer networks
Languages : en
Pages :

Get Book

Book Description
Modeling networks as different graph types and discovering novel route finding strategies, as well as avoiding congestion in dense subnetworks via graph-theoretic approaches, contribute to overall blocking probability reduction in communication networks. We develop methods for modeling congested subnetworks and graph density measures to identify routes that avoid dense subgraphs for local or global congestion avoidance. We thoroughly review various concepts of graph density, as well as associated theorems and algorithms to identify and extract a densest subgraph from an input graph, according to different definitions of graph density. The Disjoint Connecting Paths problem, and its capacitated generalization, called Unsplittable Flow problem, play an important role in practical applications such as communication network design and routing. These tasks are NP-hard in general, but various polynomialtime approximations and efficiently solvable special cases are known. We present a solution that provides a relatively simple, efficient algorithm for the Unsplittable Flow problem in large, general directed graphs, where the task is NP-hard, and is known to remain NP-hard even to approximate up to a large factor. The efficiency of our algorithm is achieved by sacrificing a small part of the solution space. This also represents a novel paradigm for approximation: rather than giving up the search for an exact solution, we restrict the solution space to a subset that is the most important for applications, and excludes only a small part that is marginal in some well-defined sense. Specifically, the sacrificed part only contains scenarios where some edges are very close to saturation. Since nearly saturated links are undesirable in practical applications, therefore, excluding near-saturation is quite reasonable from the practical point of view. Referring the solutions that contain no nearly saturated edges as safe solutions, and call the approach safe approximation we prove that this safe approximation can be carried out efficiently. That is, once we restrict ourselves to safe solutions, but keeping the graph completely general, finding the exact optimum by a randomized polynomial time algorithm is feasible. As a further piece of graph theory based analysis, we study random graphs instances in which the edges are allowed to be dependent. The importance of random graphs in networking is provided by the fact that they are frequently used to model the network topology of radio networks. However, the most studied variant of random graph models, the Erd ̋os-Rényi random graph, is insufficient for this purpose, because of its strong simplifying assumption that the edges are stochastically independent. We generalize this model by allowing edge dependence, in a quite general way. We call our model p-robust random graph. It means that every edge is present at least with a given probability p, regardless of the presence/absence of other edges. This allows significant dependencies, but keeping independent edges as a special case. For our main result, we consider monotone graph properties: properties that are preserved whenever more edges are added. Many important graph properties are monotone. Our main result, which requires a rather sophisticated proof, is that for any monotone graph property, the p-robust random graph has at least as high probability to have the property as an Erd ̋os-Rényi random graph with edge probability p. This provides a useful general tool, as it allows the adaptation of many results from classical Erd ̋os-Rényi random graphs to a non-independent setting, via using them as lower bounds. Finally, to complement the theoretical investigations with a practical approach, we consider a fundamental component for packet traffic filtering in computer networks, called Access Control List (ACL). Packet filtering via ACL controls inbound or outbound packet traffic and provides the ability to manage the network traffic flow through a network element to optimize quality of service (QoS), network security, as well as network performance. In general, filtering packet traffic and applying rules of permit/denial to data packets flowing into network nodes are facilitated by ACL. As an industry use case, we propose a procedure of adding a link load threshold value to the Access Control List rules option, which acts on the basis of a threshold value. This enhanced ACL is helps to avoid congestion in targeted subnetworks via the link load threshold value, which allows to decide that the packet traffic is rerouted by the router to avoid congestion, or packet drop is initiated on the basis of packet priorities. We demonstrate the system operation via numerical simulation.