2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Level Crossing Ordering of Markov Chains: Computing End to End Delays in an All Optical Network

Download122 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2007.1985,
        author={Ana Buši´c and Tadeusz Czach\^{o}rski and Jean-Michel Fourneau and Krzysztof Grochla},
        title={Level Crossing Ordering of Markov Chains: Computing End to End Delays in an All Optical Network},
        proceedings={2nd International ICST Conference on Performance Evaluation Methodologies and Tools},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Level crossing comparison of Markov chains stochastic ordering end to end delay deflection routing},
        doi={10.4108/valuetools.2007.1985}
    }
    
  • Ana Buši´c
    Tadeusz Czachórski
    Jean-Michel Fourneau
    Krzysztof Grochla
    Year: 2010
    Level Crossing Ordering of Markov Chains: Computing End to End Delays in an All Optical Network
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2007.1985
Ana Buši´c1,*, Tadeusz Czachórski2,*, Jean-Michel Fourneau3,*, Krzysztof Grochla2,*
  • 1: PRiSM CNRS UMR 8144 Université de Versailles Saint-Quentin 45 Av. des Etats Unis, 78000 Versailles, France
  • 2: IITIS-PAN, Ul. Balticka 5, 44-100 Gliwice, Poland
  • 3: INRIA project MESCAL Laboratoire Informatique de Grenoble CNRS UMR 5217 Montobonnot, France
*Contact email: abusic@prism.uvsq.fr, tadek@iitis.gliwice.pl, jmf@prism.uvsq.fr, kgrochla@iitis.gliwice.pl

Abstract

We advocate the use of level crossing ordering of Markov chains and we present two applications of this ordering to analyze the deflection routing in an all optical packet network. As optical storage of packets is not available, we assume that the routing protocol is based on deflection. This routing strategy does not allow packet loss. However it keeps the packets inside the network, increases the delay and reduces the bandwidth. Thus the transport delay distribution is the key performance issue for these networks. Here, we consider the deflection routing of a packet in a hypercube. First we assume that the deflection probability is known and we build an absorbing Markov chain to model the packet inside the network. Then we present a more abstract model of the topology and we show that under weak assumptions bounds on the deflection probability provide bounds on the end to end delay. This result is based on level-crossing comparison of Markov chains. Then we present an approximate model of the switch to obtain a fixed point system between two sub-models. The first subsystem describes the global network performance while the other one models the stochastic behavior of the packet. The fixed point system is solved by a numerical algorithm and the convergence of this algorithm is proved using again the theory of level crossing comparison of Markov chains. Proving convergence is a new application for the theory of Markov chain comparison and this example can be generalized to many algorithms based on Markov chains.