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

Performance Evaluation of Stochastic Bipartite Matching Models

  • Conference paper
  • First Online:
Performance Engineering and Stochastic Modeling (EPEW 2021, ASMTA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 13104))

Abstract

We consider a stochastic bipartite matching model consisting of multi-class customers and multi-class servers. Compatibility constraints between the customer and server classes are described by a bipartite graph. Each time slot, exactly one customer and one server arrive. The incoming customer (resp. server) is matched with the earliest arrived server (resp. customer) with a class that is compatible with its own class, if there is any, in which case the matched customer-server couple immediately leaves the system; otherwise, the incoming customer (resp. server) waits in the system until it is matched. Contrary to classical queueing models, both customers and servers may have to wait, so that their roles are interchangeable. While (the process underlying) this model was already known to have a product-form stationary distribution, this paper derives a new compact and manageable expression for the normalization constant of this distribution, as well as for the waiting probability and mean waiting time of customers and servers. We also provide a numerical example and make some important observations.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Adan, I., Busic, A., Mairesse, J., Weiss, G.: Reversibility and further properties of FCFS infinite bipartite matching. Math. Oper. Res. 43(2), 598–621 (2017)

    Article  MathSciNet  Google Scholar 

  2. Adan, I., Kleiner, I., Righter, R., Weiss, G.: FCFS parallel service systems and matching models. Perform. Eval. 127–128, 253–272 (2018)

    Article  Google Scholar 

  3. Adan, I., Weiss, G.: Exact FCFS matching rates for two infinite multitype sequences. Oper. Res. 60(2), 475–489 (2012)

    Article  MathSciNet  Google Scholar 

  4. Adan, I., Weiss, G.: A skill based parallel service system under FCFS-ALIS - steady state, overloads, and abandonments. Stoch. Syst. 4(1), 250–299 (2014)

    Article  MathSciNet  Google Scholar 

  5. Berezner, S., Krzesinski, A.E.: Order independent loss queues. Queueing Syst. 23(1), 331–335 (1996)

    Article  MathSciNet  Google Scholar 

  6. Bonald, T., Comte, C., Mathieu, F.: Performance of balanced fairness in resource pools: a recursive approach. Proc. ACM Meas. Anal. Comput. Syst. 1(2), 41:1–41:25 (2017)

    Google Scholar 

  7. Busic, A., Gupta, V., Mairesse, J.: Stability of the bipartite matching model. Adv. Appl. Probab. 45(2), 351–378 (2013)

    Article  MathSciNet  Google Scholar 

  8. Caldentey, R., Kaplan, E.H., Weiss, G.: FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probab. 41(3), 695–730 (2009)

    Article  MathSciNet  Google Scholar 

  9. Comte, C.: Resource management in computer clusters: algorithm design and performance analysis. Ph.D. thesis. Institut Polytechnique de Paris (2019)

    Google Scholar 

  10. Comte, C.: Stochastic non-bipartite matching models and order-independent loss queues. Stochast. Models, 1–36 (2021). https://www.tandfonline.com/doi/full/10.1080/15326349.2021.1962352

  11. Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01492-5

    Book  MATH  Google Scholar 

  12. Gardner, K., Righter, R.: Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview. Queueing Syst. 3–51 (2020). https://doi.org/10.1007/s11134-020-09668-6

  13. Gardner, K., Zbarsky, S., Doroudi, S., Harchol-Balter, M., Hyytia, E.: Reducing latency via redundant requests: exact analysis. ACM SIGMETRICS Perform. Eval. Rev. 43(1), 347–360 (2015)

    Article  Google Scholar 

  14. Krzesinski, A.E.: Order independent queues. In: Boucherie, R.J., Van Dijk, N.M. (eds.) Queueing Networks: A Fundamental Approach. International Series in Operations Research and Management Science, vol. 154, pp. 85–120. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-6472-4_2

    Chapter  Google Scholar 

  15. Mairesse, J., Moyal, P.: Stability of the stochastic matching model. J. Appl. Probab. 53(4), 1064–1077 (2016)

    Article  MathSciNet  Google Scholar 

  16. Moyal, P., Busic, A., Mairesse, J.: A product form for the general stochastic matching model. J. Appl. Probab. 58(2), 449–468 (2021)

    Article  MathSciNet  Google Scholar 

  17. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)

    Article  MathSciNet  Google Scholar 

  18. Zhao, Y.: The number of independent sets in a regular graph. Comb. Probab. Comput. 19(2), 315–320 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Eindhoven University of Technology, Eindhoven, The Netherlands

    Céline Comte

  2. University of Amsterdam, Amsterdam, The Netherlands

    Jan-Pieter Dorsman

Authors
  1. Céline Comte
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan-Pieter Dorsman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Céline Comte .

Editor information

Editors and Affiliations

  1. University Paris-Saclay, Gif-sur-Yvette, France

    Paolo Ballarini

  2. Telecom Sub Paris, Evry, France

    Hind Castel

  3. University of Patras, Patras, Greece

    Ioannis Dimitriou

  4. Università degli studi della Campania Luigi Vanvitelli, Caserta, Italy

    Mauro Iacono

  5. Faculty of Engineering, Information and Systems, Division of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Japan

    Tuan Phung-Duc

  6. Ghent University, Gent, Belgium

    Joris Walraevens

Appendix: Proofs of the Results of Sect. 3

Appendix: Proofs of the Results of Sect. 3

Proof of Corollary 1. Summing (8) over all \({\mathcal {A}}\in {\mathbb {I}}\) and rearranging the sum symbols yields

$$\begin{aligned} \nonumber&\sum _{(i, k) \in {\mathcal {I}}\times {\mathcal {K}}} \lambda _i \mu _k \sum _{\begin{array}{c} {\mathcal {A}}\in {\mathbb {I}}: i \in {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), \\ k \in {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}) \\&= \sum _{\begin{array}{c} (i, k) \in {\mathcal {I}}\times {\mathcal {K}}: \\ i \not \sim k \end{array}} \lambda _i \mu _k \sum _{\begin{array}{c} {\mathcal {A}}\in {\mathbb {I}}: \\ i \in {\mathcal {A}}, k \in {\mathcal {A}} \end{array}} \big ( \pi ({\mathcal {A}}) + \pi ({\mathcal {A}}{\setminus } \{i\}) + \pi ({\mathcal {A}}{\setminus } \{k\}) + \pi ({\mathcal {A}}{\setminus } \{i, k\}) \big ). \end{aligned}$$
(13)

The left-hand side of this equation is the left-hand side of (9). The right-hand side can be rewritten by making changes of variables. For instance, for each \(i \in {\mathcal {I}}\) and \(k \in {\mathcal {K}}\) such that \(i \not \sim k\), replacing \({\mathcal {A}}\) with \({\mathcal {A}}{\setminus } \{i, k\}\) in the last sum yields

$$\begin{aligned} \sum _{\begin{array}{c} {\mathcal {A}}\in {\mathbb {I}}: i \in {\mathcal {A}}, k \in {\mathcal {A}} \end{array}} \pi ({\mathcal {A}}{\setminus } \{i, k\})&= \sum _{\begin{array}{c} {\mathcal {A}}\subseteq {\mathcal {I}}\cup {\mathcal {K}}: i \notin {\mathcal {A}}, k \notin {\mathcal {A}}, \\ {\mathcal {A}}\cup \{i, k\} \in {\mathbb {I}} \end{array}} \pi ({\mathcal {A}}) = \sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \notin {\mathcal {A}}, k \notin {\mathcal {A}}, \\ i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}). \end{aligned}$$

The second equality is true only because \(i \not \sim k\). By applying changes of variables to the other terms, we obtain that the right-hand side of (13) is equal to

$$\begin{aligned}&\sum _{\begin{array}{c} (i, k) \in {\mathcal {I}}\times {\mathcal {K}}: \\ i \not \sim k \end{array}} \lambda _i \mu _k \Bigg ( \begin{aligned}&\sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \in {\mathcal {I}}, k \in {\mathcal {A}}, \\ i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}) + \sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \notin {\mathcal {I}}, k \in {\mathcal {A}}, \\ i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}) \\&+ \,\sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \in {\mathcal {I}}, k \notin {\mathcal {A}}, \\ i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}) + \sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \notin {\mathcal {A}}, k \notin {\mathcal {A}}, \\ i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}) \Bigg ) \end{aligned} \\&= \sum _{\begin{array}{c} (i, k) \in {\mathcal {I}}\times {\mathcal {K}}: i \not \sim k \end{array}} \lambda _i \mu _k \sum _{\begin{array}{c} {\mathcal {A}}\in {{\mathbb {I}}_0}: i \notin {\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}), k \notin {\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}) \end{array}} \pi ({\mathcal {A}}). \end{aligned}$$

Proof of Proposition 2. Let \(i \in {\mathcal {I}}\). We have \(L_i = \sum _{{\mathcal {A}}\in {{\mathbb {I}}_0}} \ell _i({\mathcal {A}})\), where

$$\begin{aligned} \ell _i({\mathcal {A}}) = \sum _{(c, d) \in \varPi _{\mathcal {A}}} |c|_i \pi (c, d), \quad {\mathcal {A}}\in {{\mathbb {I}}_0}. \end{aligned}$$

Let \({\mathcal {A}}\in {\mathbb {I}}\). If \(i \notin {\mathcal {A}}\), we have directly \(\ell _i({\mathcal {A}}) = 0\) because \(|c|_i = 0\) for each \((c, d) \in \varPi _{\mathcal {A}}\). Now assume that \(i \in {\mathcal {A}}\) (so that in particular \({\mathcal {A}}\) is non-empty). The method is similar to the proof of Proposition 1. First, by applying (1), we have

$$\begin{aligned} \ell _i({\mathcal {A}}) = \sum _{(c, d) \in \varPi _{\mathcal {A}}}&|c|_i \frac{\lambda _{c_n}}{\mu ({\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}}))} \frac{\mu _{d_n}}{\lambda ({\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}}))} \pi ((c_1, \ldots , c_{n-1}), (d_1, \ldots , d_{n-1})). \end{aligned}$$

Then applying (6) and doing a change of variable yields

$$\begin{aligned}&\mu ({\mathcal {K}}({\mathcal {A}}\cap {\mathcal {I}})) \lambda ({\mathcal {I}}({\mathcal {A}}\cap {\mathcal {K}})) \ell _i({\mathcal {A}}) \\&\begin{aligned}&= \lambda _i \sum _{k \in {\mathcal {A}}\cap {\mathcal {K}}} \mu _k \begin{aligned} \bigg (&\sum _{(c, d) \in \varPi _{\mathcal {A}}} (|c|_i + 1) \pi (c, d) + \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{i\}}} (0 + 1) \pi (c, d) \\&+ \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{k\}}} (|c|_i + 1) \pi (c, d) + \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{i, k\}}} (0 + 1) \pi (c, d) \bigg ), \end{aligned} \\&\quad + \sum _{j \in ({\mathcal {A}}{\setminus } \{i\}) \cap {\mathcal {I}}} \sum _{k \in {\mathcal {A}}\cap {\mathcal {K}}} \lambda _j \mu _k \begin{aligned} \bigg (&\sum _{(c, d) \in \varPi _{\mathcal {A}}} |c|_i \pi (c, d) + \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{j\}}} |c|_i \pi (c, d) \\&+ \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{k\}}} |c|_i \pi (c, d) + \sum _{(c, d) \in \varPi _{{\mathcal {A}}{\setminus } \{j, k\}}} |c|_i \pi (c, d) \bigg ), \end{aligned} \end{aligned} \\&\begin{aligned}&=\lambda _i \sum _{k \in {\mathcal {A}}\cap {\mathcal {K}}} \mu _k \left( \ell _i({\mathcal {A}}) + \pi ({\mathcal {A}}) + \pi ({\mathcal {A}}{\setminus } \{i\}) + \ell _i({\mathcal {A}}{\setminus } \{k\}) + \pi ({\mathcal {A}}{\setminus } \{k\}) + \pi ({\mathcal {A}}{\setminus } \{i, k\}) \right) \\&\quad + \sum _{j \in ({\mathcal {A}}{\setminus } \{i\}) \cap {\mathcal {I}}} \sum _{k \in {\mathcal {A}}\cap {\mathcal {K}}} \lambda _j \mu _k \left( \ell _i({\mathcal {A}}) + \ell _i({\mathcal {A}}{\setminus } \{j\}) + \ell _i({\mathcal {A}}{\setminus } \{k\}) + \ell _i({\mathcal {A}}{\setminus } \{j, k\}) \right) . \end{aligned} \end{aligned}$$

The result follows by rearranging the terms.

Proof of Proposition 3. Equation (11) follows by summing (10) over all \(i \in {\mathcal {I}}\cap {\mathcal {A}}\) and simplifying the result using (8).

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Comte, C., Dorsman, JP. (2021). Performance Evaluation of Stochastic Bipartite Matching Models. In: Ballarini, P., Castel, H., Dimitriou, I., Iacono, M., Phung-Duc, T., Walraevens, J. (eds) Performance Engineering and Stochastic Modeling. EPEW ASMTA 2021 2021. Lecture Notes in Computer Science(), vol 13104. Springer, Cham. https://doi.org/10.1007/978-3-030-91825-5_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-91825-5_26

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-91824-8

  • Online ISBN: 978-3-030-91825-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation