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

##### Abstract

##### Abstract

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´enyi
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´enyi 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´enyi 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.