×

The complexity of routing in hierarchical PNNI networks. (English) Zbl 1273.90044

Summary: We study the complexity of computing a route in a hierarchical PNNI network, with \(H\) levels of hierarchy, in which \(N\) nodes are grouped into clusters at each level. We determine cluster sizes that minimize an upper bound on the total time for all the path computations required to compute a route. Our model casts the problem as a nonlinear convex optimization problem, and employs nonlinear duality theory. We derive explicit closed form upper bounds on the minimum total path computation time, as a function of \(N\), for \(H=2\) and \(H=3\), and show how the upper bound, and the optimal cluster sizes, can be computed for any \(H\). We provide a conjecture on the complexity of PNNI routing for any \(H\), and use this conjecture to determine the limit of the complexity as \(H\to\infty\). We also prove that the minimum total path computation time is a non-increasing function of \(H\). Our results provide counterexamples to a claim by P. Van Mieghem [“Topology information condensation in hierarchical networks”, Comput. Netw. 31, No. 20, 2115–2137 (1999)] that a related top-down hierarchical routing method has lower computational complexity.

MSC:

90B18 Communication networks in operations research
68M10 Network design and communication in computer systems
65K10 Numerical optimization and variational techniques
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice-Hall, Englewood Cliffs
[2] Ash J, Choudhury G (2004) PNNI routing congestion control. IEEE Commun Mag 154–160
[3] Duffin RJ (1970) Linearizing geometric programs. SIAM Rev 12:211–227 · Zbl 0229.90047 · doi:10.1137/1012043
[4] Duffin RJ, Petersen EL, Zener C (1967) Geometric programming. Wiley, New York
[5] Gill PE, Murray W, Wright MH (1981) Practical optimization. Academic Press, New York · Zbl 0503.90062
[6] Iliadis I (2004) Optimal PNNI complex node representations for restrictive costs. Comput Commun 27:434–446 · Zbl 05396558 · doi:10.1016/j.comcom.2003.08.001
[7] Kleinrock L, Kamoun F (1977) Hierarchical routing for large networks: performance evaluation and optimization. Comput Netw 1:155–174
[8] Kleinrock L, Kamoun F (1980) Optimal clustering structures for hierarchical topological design of large computer networks. Networks 10:221–248 · Zbl 0448.68001 · doi:10.1002/net.3230100305
[9] Lai WS, Rosenberg E, Amiri L, Ball M, Levy Y, Shulman H, Tong H, Ungar M (2005) Analysis and design of AT&T’s global PNNI network. In: Proc of IEEE Pacific Rim conference on communications, computers, and signal processing (PacRim 2005), August 2005, pp 129–132
[10] Lai WS, Amiri L, Ball M, Rosenberg E, Tong H (2006) The scalable growth of AT&T’s global PNNI network. In: Proc of 2006 symposium on performance evaluation of computer and telecommunication systems (SPECTS 2006), Calgary, Alberta, Canada, 31 July–2 August 2006, pp 363–370
[11] Lai WS, Amiri L, Ball M, Jones D, Rosenberg E, Ungar M (2007) Topology aggregation in PNNI networks, part 1: link aggregation. In: Proc of IEEE Pacific Rim conference on communications, computers, and signal processing (PacRim 2007), 22–24 August 2007, pp 8–11
[12] Masip-Bruin X, Sánchez-López S, Solé-Pareta J, Domingo-Pascual J, Marin-Tordera E (2004) Hierarchical routing with QoS constraints in optical transport networks. In: Lecture notes in computer science, vol 3042. Springer, Heidelberg, pp 662–674
[13] Moy JT (1998) OSPF: anatomy of an Internet routing protocol. Addison-Wesley, Reading
[14] Orda A, Sprintson A (2003) Precomputation schemes for QoS routing. IEEE/ACM Trans Netw 11:578–591 · Zbl 05458813 · doi:10.1109/TNET.2003.815299
[15] Private network-network interface specification version 1.1 (2002) The ATM Forum Technical Committee. af-pnni-0055.002, April 2002
[16] Rockafellar RT (1970) Convex analysis. Princeton University Press, Princeton · Zbl 0193.18401
[17] Rosenberg E (1981a) Globally convergent algorithms for convex programming. Math Oper Res 6:437–444 · Zbl 0507.90072 · doi:10.1287/moor.6.3.437
[18] Rosenberg E (1981b) On solving a primal geometric program by partial dual optimization. Math Program 21:319–330 · Zbl 0467.90060 · doi:10.1007/BF01584252
[19] Rosenberg E (1982) A globally convergent condensation method for geometric programming. Utilitas Math 22:47–64 · Zbl 0501.90080
[20] Rosenberg E (2008) Error bounds for hierarchical routing. In: Raghavan S, Golden B, Wasil E (eds) Telecommunications modeling, policy, and technology, Chap 5. Springer, New York, pp 81–100
[21] Rosenberg E (2009) Minimizing hierarchical routing error. Comput Netw 53:1926–1938 · Zbl 1192.68053 · doi:10.1016/j.comnet.2009.02.022
[22] Rougier JL, Kofman D, Gravey A (2000) Optimization of hierarchical routing protocols. Perform Evaluation 41:227–245 · Zbl 1052.68530 · doi:10.1016/S0166-5316(00)00009-2
[23] Sánchez-López S, Solé-Pareta J, Comellas J, Soldatos J, Kylafas G, Jaeger M (2003) PNNI-based control plane for automatically switched optical networks. J Lightwave Technol 21:2673–2682 · doi:10.1109/JLT.2003.819547
[24] Simonnard M (1966) Linear programming, translated by WS Jewell. Prentice-Hall, Englewood Cliffs · Zbl 0154.19506
[25] Stewart JW (1999) BGP4: Inter-domain routing in the Internet. Addison-Wesley, Reading
[26] Van Mieghem P (1997) Estimation of an optimal PNNI topology. In: Proc of IEEE ATM’97 workshop, Lisbon, Portugal, 26–28 May 1997
[27] Van Mieghem P (1998) Routing in a hierarchical structure. In: Proc of the first IEEE internat conf on ATM: ICATM ’98, June 1998, Colmar, France, pp 378–384
[28] Van Mieghem P (1999) Topology information condensation in hierarchical networks. Comput Netw 31:2115–2137 · doi:10.1016/S1389-1286(99)00066-3
[29] Wilde DJ (1978) Globally optimal design. Wiley, New York
[30] Wu X, Murkerjee B, Ghosal D (2004) Hierarchical architectures in the third-generation cellular network. IEEE Wirel Mag 11:62–71
[31] Zener C (1971) Engineering design by geometric programming. Wiley, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.