Processing user requests quickly requires not only fast servers, but also demands methods to quickly locate idle servers to process those requests. Methods of finding idle servers are analogous to open addressing in hash tables, but with the key difference that servers may return to an idle state after having been busy rather than staying busy. Probing sequences for open addressing are well-studied, but algorithms for locating idle servers are less understood. We investigate sequential probing with a random start as a method for finding idle servers, especially in cases of heavy traffic. We present a procedure for finding the distribution of the number of probes required for finding an idle server by using a Markov chain and ideas from enumerative combinatorics, then present numerical simulation results in lieu of a general analytic solution.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1118 |
| Date | 01 January 2018 |
| Creators | Miller, Joshua |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HMC Senior Theses |
| Rights | @2018 Joshua A. Miller, default |
Page generated in 0.002 seconds