Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Dynamic Multicriteria Alternative Routing for single- and multi-service reservation-oriented networks and its performance

  • Published:
Annals of Telecommunications Aims and scope Submit manuscript

Abstract

We propose a new Dynamic Multicriteria Alternative Routing (DMAR) method that applies to reservation-oriented networks. DMAR combines a dynamic alternative routing scheme with a periodic update of alternative paths according to a multicriteria algorithm that aims to balance the traffic between traffic flows in single-service networks and also between services in multi-service environments. We conducted extensive simulations to compare the performance of DMAR with that of other reference alternative routing schemes in single- and multi-service networks with several topologies and load scenarios, namely with non-stationary traffic. We show that DMAR efficiently adjusts to traffic changes while often presenting better network performance than the reference alternative routing schemes, particularly in the multicriteria sense.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

References

  1. Ash G (1995) Dynamic network evolution, with examples from AT&T’s evolving dynamic network. IEEE Communications Magazine 33:26–39

    Article  Google Scholar 

  2. Gibbens R (1988) Dynamic routing in circuit-switched networks: the dynamic alternative routing strategy. Ph.D. thesis, University of Cambridge

  3. Girard A (1990) Routing and dimensioning in circuit-switched networks. Addison-Wesley Publishing Company, Reading

    Google Scholar 

  4. Wang M, Li S, Wong E, Zukerman M (2013) Blocking probability analysis of circuit-switched networks with long-lived and short-lived connections. J Opt Commun Netw 5(6):621–640

    Article  Google Scholar 

  5. Wang M, Li S, Wong E, Zukerman M (2014) Performance analysis of circuit switched multi-service multi-rate networks with alternative routing. IEEE/OSA J Lightwave Technol 32(2):179–200

    Article  Google Scholar 

  6. Conte M (2003) Dynamic routing in broadband networks. Kluwer Academic Publishers, Norwell

    Book  Google Scholar 

  7. Katib I, Medhi D (2009) Adaptive alternate routing in WDM networks and its performance tradeoffs in the presence of wavelength converters. Opt Switch Netw 6(3):181–193

    Article  Google Scholar 

  8. Lin H, Wang S, Tsai C, Hung M (2008) Traffic intensity based alternate routing for all-optical WDM networks. J Lightwave Technol 26:3604–3616

    Article  Google Scholar 

  9. Lin H, Wang S, Hung M (2008) Finding routing paths for alternate routing in all-optical WDM networks. J Lightwave Technol 26:1432–1444

    Article  Google Scholar 

  10. Kist A, Harris R (2003) Scheme for alternative packet overflow routing (SAPOR). In: Workshop on High Performance Switching and Routing, HPSR. IEEE, pp 269–274

  11. Srivastava S, Krithikaivasan B, Beard C, et al (2004) Benefits of traffic engineering using QoS routing schemes and network controls. Comput Commun 27:387–399

    Article  Google Scholar 

  12. Ash G, McDysan D (2012) Generic connection admission control (GCAC) algorithm specification for IP/MPLS networks. RFC 6601. http://www.ietf.org/rfc/rfc6601.txt

  13. Martins L, Francisco C, Redol J, Craveirinha J, Clímaco J, Monteiro P (2009) Evaluation of a Multiobjective alternative routing method in carrier IP/MPLS networks. In: Proceedings of the 8th International IFIP-TC 6 Networking Conference, Networking 2009, pp 195–206

  14. Clímaco J, Craveirinha J, Girão-Silva R (2016) Multicriteria analysis in telecommunication network planning and design: a survey. Int Ser Oper Res Manag Sci 233:1167–1233

    Google Scholar 

  15. Martins L, Craveirinha J, Clímaco J, Gomes T (2005) On a bi-dimensional dynamic alternative routing method. Eur J Oper Res Spec Issue Adv Complex Syst Model 166(3):828– 842

    MathSciNet  MATH  Google Scholar 

  16. Martins L, Craveirinha J, Clímaco J (2006) A new multiobjective dynamic routing method for multiservice networks: modelling and performance. CMS 3(3):225–244

    Article  MathSciNet  Google Scholar 

  17. Kelly FP (1988) Routing in circuit-switched networks: optimization, shadow prices and decentralization. Adv Appl Probab 20:112–144

    Article  MathSciNet  Google Scholar 

  18. Francisco C, Martins L, Medhi D (2018) Traffic model for dynamic multicriteria alternative routing for single- and multi-service reservation-oriented networks. Tech. Rep. 1, INESC-Coimbra, available online: https://www.uc.pt/en/org/inescc/res_reports_docs/research_reports

  19. Kaufman JS (1981) Blocking in a shared resource environment. IEEE Trans Commun 29(10):1474–1481

    Article  Google Scholar 

  20. Mitra D, Morrison JA (1994) Erlang capacity and uniform approximations for shared unbuffered resources. IEEE/ACM Trans Netw 2(6):558–570

    Article  Google Scholar 

  21. Medhi D, Guptan S (1997) Network dimensioning and performance of multiservice, multirate loss networks with dynamic routing. IEEE/ACM Trans Netw 5:944–957

    Article  Google Scholar 

  22. Medhi D (2002) QoS Routing computation with path caching: a framework and network performance. IEEE Commun Mag 40(12):106–113

    Article  Google Scholar 

  23. Sivasankar R, Ramam S, Subramaniam S, Rao T, Medhi D (2000) Some studies on the impact of dynamic traffic in a QoS-based dynamic routing environment. In: Proceedings of 2000 IEEE International Conference on Communications (ICC), vol 2, pp 959–963

  24. Mesquite Software: CSIM. http://www.mesquite.com/

  25. Chemouil P, Filipiak J, Gauthier P (1990) Performance issues in the design of dynamically controlled circuit-switched networks. IEEE Commun Mag 28(10):90–95

    Article  Google Scholar 

Download references

Acknowledgments

Lúcia Martins has been supported by FCT (Fundação para a Ciência e a Tecnologia) under project grant UID/MULTI/-00308/2013 and by FEDER Funds and National Funds through FCT under the project CENTRO-01-0145-FEDER-029312.

Author information

Authors and Affiliations

  1. Nokia Solutions and Networks Portugal S.A., Estrada do Seminário 4, Edifício Conhecimento, Alfragide, 2610-171, Amadora, Portugal

    Catarina Francisco

  2. Electrical and Computer Engineering Department, University of Coimbra, 3030-290, Coimbra, Portugal

    Lúcia Martins

  3. Computer Science & Electrical Engineering Department, School of Computing and Engineering, University of Missouri–Kansas City, Kansas City, MO, 64110-2499, USA

    Deep Medhi

Authors
  1. Catarina Francisco
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lúcia Martins
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Deep Medhi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lúcia Martins.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix 1: Traffic matrices

1.1 1.1 Single-service network

Traffic “BH” in Table 1 is based on a voice service whose traffic pattern was made available by Sprint for the busiest hour for a 10-node network [21].

Dynamic traffic matrices present a time-varying traffic pattern that is mapped as a sinusoidal wave for each pair of nodes by considering the following time-dependent function: Traf(t) = Avg(1 + A sin(2πft + φ)). The Sprint-offered traffic matrices for the seven busiest hours period ([10,17[h) inspired the mapping into the sinusoidal waves defined as “7 BHs” in Table 1.

1.2 1.2 Multi-service network

Work in [11] applies to multi-service networks with a load distribution based on an actual service provider. This work was inspired by [11] leading to the following load distribution: 5(S1):20(S2):75(S3). This study assumes that the base rate is the bandwidth in use by service S1 and that all services require some multiple of this base rate. The multi-service networks were thus engineered with three services with the required bandwidth d=[1,6,10] for services S1, S2, and S3, respectively.

Traffic for service S1 is based on single-service traffic. The traffic that is offered to services S2 and S3 in every situation is such that maintains the load distribution before mentioned. To reduce the simulation time, the average values used by each service are affected by a multiplicative factor f =[1/3,2/9,1/2] for services S1, S2, and S3, respectively. In the dynamic traffic case, the amplitude variation is also affected by the same factor.

Appendix 2: Test networks

Table 2 presents all the networks used in this study. The dimensioning of the single-service networks was done in a simplistic manner based on the Sprint-offered traffic matrices for the seven busiest hours period, assuming the use of direct routing and using the inverse of Erlang B formula as first approach for a reference blocking probability value.

Network A was adjusted by simulation based on the busiest hour traffic to get a mean network blocking probability of approximately 1% for DAR.

Network C was dimensioned based on the traffic for the three time instants corresponding to the peak values of the offered traffic in Fig. 9, and using the fixed-point iterators in [18].

Network B is a sparser network and it resulted from the removal of approximately 10% (5 links) of the links in Network A (see Fig. 13). The first-choice path for each of the pairs of nodes is fixed and the same regardless of the routing method. The capacities of the links that are used in the two-arcs first-choice paths are increased, when compared with Network A, by the corresponding capacities of the removed links.

Fig. 13
figure 13

Network B—topology

Full size image

Multi-service networks D and E were obtained in a similar way as single-service networks A and C, respectively, and considering all the offered traffic as if it was single service.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Francisco, C., Martins, L. & Medhi, D. Dynamic Multicriteria Alternative Routing for single- and multi-service reservation-oriented networks and its performance. Ann. Telecommun. 74, 697–715 (2019). https://doi.org/10.1007/s12243-019-00715-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12243-019-00715-9

Keywords

Search

Navigation