A Formal Model for Path Set Attribute Calculation in Network Systems

Giovanni Fiaschi ID, Carlo Vitucci ID, Thomas Westerbäck ID, Daniel Sundmark ID, Thomas Nolte ID · 2025

Read A Formal Model for Path Set Attribute Calculation in Network Systems by Giovanni Fiaschi ID, Carlo Vitucci ID, Thomas Westerbäck ID, Daniel Sundmark ID, Thomas Nolte ID (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05334.txt.

Introduction

Giovanni Fiaschi and co-authors set out a formal model for scoring sets of paths in a network, not just single paths. Path choice drives telecom and transport systems, and each choice needs a score to rank it against rivals.

Past work scored single paths in depth, but sets of paths lacked the same care. Fiaschi stresses that a set's traits rest on which properties one picks, more so than for lone paths. His model gives a shared tongue for those scores, so backup route sets can be judged on firm ground.

Catalog record

CREATORGiovanni Fiaschi ID, Carlo Vitucci ID, Thomas Westerbäck ID, Daniel Sundmark ID, Thomas Nolte ID
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05334

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Formal Model for Path Set Attribute Calculation in Network Systems Giovanni Fiaschi ID, Carlo Vitucci ID, Thomas Westerbäck ID, Daniel Sundmark ID, Thomas Nolte ID Abstract In graph theory and its practical networking applications, e.g., telecommunications and transportation, the problem of finding paths has particular importance. Selecting paths requires giving scores to the alternative solutions to drive a choice. While previous studies have provided comprehensive evaluation of single-path solutions, the same level of detail is lacking when considering sets of paths. This paper emphasizes that the path characterization strongly depends on the properties under consideration. While property-based characterization is also valid for single paths, it becomes crucial to analyse multiple path sets. From the above consideration, this paper proposes a mathematical approach, defining a functional model that lends itself well to characterizing the path set in its general formulation. The paper shows how the functional model contextualizes specific attributes. I Introduction A network is a concept often used in several domains: a number of devices or users connected to transfer and exchange data. As a very general definition, in this paper a network is any collection of objects in which some pairs of these objects are connected by links [ 10 ] . One major application field for the network concept is the telecommunications domain, particularly packet switching, whose purpose is to route packets among devices. Another field of application is transportation, where the purpose is to send vehicles through roads from one place to another. Routing is the process of choosing a path or a set of paths across one or more networks. Choosing paths implies considering several alternatives, giving a score to each of them, and eventually selecting the highest-scoring alternative. The described selection process is what existing routing algorithms do. Solid solutions exist for single-path routing, where a path is given a cost or length value, which is the sum of the costs of its component edges. When evaluating sets of multiple paths, scoring criteria are not equally clear. This paper proposes a mathematical model to determine descriptive and representative characteristics of path sets. The model has practical applications in telecommunication systems. Section II analyses how research has tackled the problem of characterizing network connectivity. Section III recalls essential elements of graph theory and their interpretation for this context. Section IV shows how edge attributes should be composed to calculate equivalent attributes in arbitrary path sets. Section V introduces representations and transformations of path sets to help the property calculation. The full calculation proposal is presented in Section VI and illustrated with notable examples. Section VII analyses the correlation between the paper’s proposal and the network polymatroid representation, with an analysis on the discussed attributes. Eventually, Section VIII contains the paper’s conclusions and possible future developments. II Related Works In telecommunications, and more generally in graph theory, analysing the best route is still a research topic. The simplest case, or single-path analysis, is a well-defined problem: finding the shortest route between two points. The “cost” could represent several properties: distance, time, money, and others. Here, algorithms such as Dijkstra [ 8 ] and Bellman-Ford [ 1 , 13 ] have stood the test of time. They focus on calculating the most efficient route, minimizing cost while crossing from one point to another. While most practical approaches focus on additive costs, there exist proposals considering single-path routing generalizations to arbitrary costs [ 24 ] . When searching for multiple paths, minimizing the cost alone is not sufficient. Since a single path already secures connectivity between the two points, a cost-based approach would just avoid additional paths. The reason for searching multiple paths is to improve other properties, such as fault resiliency. Previous approaches addressed the problem by adding a diversity score to the set of paths they aimed to find, sometimes implicitly. The diversity concept has several issues. Firstly, there are multiple diversity definitions between two paths. Secondly, extending the diversity concept from a pair of paths to a set of more than two is non-trivial and always risks missing some important properties of the set. Finally, all the definitions of diversity originate from another property, most often the cost, which does not necessarily relate to the property that needs improvement by adding multiple paths; in general, such an approach may mislead the search. Algorithms solving the K shortest path problem, such as Yen [ 28 ] or Eppstein [ 11 ] search for multiple paths while minimizing them with a minimum total cost, where the definition of diversity relies implicitly on the presence of at least one different edge, which in most cases is not effective. Others, such as Suurballe [ 26 ] and Bhandari [ 3 ] , focus on finding completely disjoint paths that do not share common features. Meanwhile, researchers such as Liu [ 18 ] and Chondrogiannis [ 6 ] have explored how to integrate diversity more directly, defining the diversity of a path set as the minimum diversity among any two paths in the set. Borodin et al. [ 4 ] use diversity for high-quality result diversification in information retrieval, database management, and structure localization. Fiaschi et al. [ 12 ] apply Borodin’s concepts to path search by combining cost and diversity with a parameter tuning their relative importance. Network graph analysis frequently utilizes the polymatroid mathematical model because it effectively captures the complex constraints of connectivity and interference while simplifying the development of optimization algorithms [ 14 ] . Notable examples where polymatroids serve as the primary mathematical model for analysing information flow are the works of Riemensberger et al. [ 21 ] , Chekuri et al. [ 5 ] , and Lee et al. [ 17 ] . III Routing Elements Fig. 1 : Generic Graph example Graphs Both undirected graphs and directed graphs are considered in graph theory [ 22 ] . This paper will focus solely on directed graphs, as they are more applicable to telecommunication and transportation examples [ 19 ] , where network links are traversed in a specific direction. For an abstract mathematical representation, a network is represented as a directed graph \mathcal{G}=(V_{g},E_{g}) (see Figure 1 ), defined by a set V_{g} of vertices (the network nodes) and a set E_{g} of edges (the network links), where E_{g} is a subset of V_{g}\times V_{g} , the set of ordered pairs of vertices. Directed Paths Intuitively, a directed path in a directed graph is an essential concept in applications such as telecommunications and transportation, as it models a route from one network node to another and provides means to convey useful entities between the end nodes, such as information in telecommunications and physical vehicles in transportation. Formally, a directed path from a source vertex s to a destination vertex d , is a sequence of edges p= \{(v_{0},v_{1}) , … (v_{i-1},v_{i}) , (v_{i},v_{i+1}) , … (v_{n-1},v_{n})\} such that v_{0},v_{1},\ldots,v_{n} are distinct vertices, s=v_{0} , d=v_{n} and (v_{i-1},v_{i})\in E_{g} for i=1,2,\dots,n . Other equivalent definitions may be found in literature [ 17 , 15 , 20 ] . Connections In graph theory, a vertex x is connected to a vertex y if a directed path exists from x to y [ 25 , 16 ] .

Read the complete text