Closed-Form Formulas for Cluster Sizing for Two-Level Hierarchical Networks with Source Routing

Eric Rosenberg ()
Additional contact information
Eric Rosenberg: Seton Hall University

Journal of Optimization Theory and Applications, 2025, vol. 206, issue 2, No 25, 34 pages

Abstract: Abstract In a two-level hierarchical network, nodes are grouped into clusters. A node in one cluster sees the entire topology of that cluster, but only a summarized view of other clusters. With source routing, the source node of a connection does an initial route computation based on its view of the network, and additional route computations are performed as the connection makes its way towards the destination. We study the problem of choosing the number of clusters to minimize the total complexity of all the path computations required to compute a path from a source node to a destination node. We show that, under mild conditions, for all sufficiently large networks two-level hierarchical routing is superior to flat network routing. Utilizing the duality theory of geometric programming, we provide a closed-form solution estimate for the number of clusters to minimize the total routing complexity. We also provide a closed-form expression for a lower bound on the minimal total complexity. We illustrate the modelling assumptions for a variety of networks. Computational results for a range of network sizes and parameters show that our solution estimate yields near-optimal results.

Keywords: Hierarchy; Network design; Duality; Geometric programming; Fractal dimension (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02710-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:206:y:2025:i:2:d:10.1007_s10957-025-02710-8

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02710-8

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().