4th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness

Research Article

Quality-of-Service Provisioning via Stochastic Path Selection under Weibullian Link Delays

  • @INPROCEEDINGS{10.1145/1577222.1577238,
        author={Suleyman Uludag and Ljubomir Perkovic and Anna Kashkanova and Kemal Akkaya},
        title={Quality-of-Service Provisioning via Stochastic Path Selection under Weibullian Link Delays},
        proceedings={4th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and  Robustness},
        publisher={ACM},
        proceedings_a={QSHINE},
        year={2007},
        month={8},
        keywords={QoS Routing Routing Delay Weibull inaccuracy networks stochastic path selection Algorithms Design Performance},
        doi={10.1145/1577222.1577238}
    }
    
  • Suleyman Uludag
    Ljubomir Perkovic
    Anna Kashkanova
    Kemal Akkaya
    Year: 2007
    Quality-of-Service Provisioning via Stochastic Path Selection under Weibullian Link Delays
    QSHINE
    ACM
    DOI: 10.1145/1577222.1577238
Suleyman Uludag1,*, Ljubomir Perkovic2,*, Anna Kashkanova1,*, Kemal Akkaya3,*
  • 1: Dept. of Computer Science University of Michigan - Flint Flint, MI 48502
  • 2: School of Computer Science DePaul University Chicago, IL 60604
  • 3: Dept. of Computer Science Southern Illinois University Carbondale, IL 62901
*Contact email: uludag@umich.edu, lperkovic@cs.depaul.edu, akashkan@umflint.edu, kemal@cs.siu.edu

Abstract

We study the problem of finding the most likely path satisfying a requested additive Quality-of-Service (QoS) value, such as delay. The link metrics are defined as random variables following Weibull probability distributions as empirically reported in [13] and analytically derived in [12]. The problem of finding the most likely path is NP-Hard [24]. Our approach involves reducing the complicated probability convolutions necessary to calculate the most probable path that satisfies a requested delay value. With the reduction of the objective function, an extended Bellman-Ford algorithm is devised to solve the problem. The resulting approach have the same complexity as the standard Bellman-Ford algorithm. Our reduced objective function only needs the location parameter of the Weibull distributions, hence avoiding the complexity of inferring the shape and scale parameters. We evaluate the performance of our approach by simulations and conclude with possible extensions of our work.