{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using Distributions, StatsPlots, StatsBase" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "run_test (generic function with 1 method)" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "algorithm_names = [\"Round robin\" \"Least occupied\" \"Random\" \"Random 2\"]\n", "\n", "function run_test(c::Int, ρ::Float64, T::Int; shedding=Inf)\n", " nodes_round_robin = zeros(Int, c)\n", " nodes_least_conn = zeros(Int, c)\n", " nodes_random = zeros(Int, c)\n", " nodes_random_2 = zeros(Int, c)\n", "\n", " μ = 10 # requests per step\n", " arrival_dist = Poisson(μ*ρ*c)\n", " completion_dist = LogNormal(log(μ)-0.5)#Exponential(10)\n", "\n", " robin = 0\n", "\n", " results = (Int[],Int[],Int[],Int[])\n", "\n", " for t in 1:T\n", " for n in 1:c\n", " completions = Int(round(rand(completion_dist)))\n", " nodes_round_robin[n] -= min(nodes_round_robin[n], completions)\n", " nodes_least_conn[n] -= min(nodes_least_conn[n], completions)\n", " nodes_random[n] -= min(nodes_random[n], completions)\n", " nodes_random_2[n] -= min(nodes_random_2[n], completions)\n", " end\n", "\n", " arrivals = Int(round(rand(arrival_dist)))\n", " for i in 1:arrivals\n", " # Round robin - chooses next server in turn\n", " j = robin%c+1\n", " nodes_round_robin[j] += 1\n", " robin += 1\n", " \n", " # Least - choose the node with least elements\n", " j = argmin(nodes_least_conn)\n", " nodes_least_conn[j] += 1\n", " \n", " # Randomn - choose a random node\n", " j = rand(1:c)\n", " nodes_random[j] += 1\n", " \n", " # Random-2 - choose the node with least elements from 2 random nodes\n", " j2 = rand(1:c)\n", " if nodes_random_2[j] > nodes_random_2[j2]\n", " nodes_random_2[j2] += 1\n", " else\n", " nodes_random_2[j] += 1\n", " end\n", " end\n", " \n", " for n in 1:c\n", " nodes_round_robin[n] = min(nodes_round_robin[n], shedding)\n", " nodes_least_conn[n] = min(nodes_least_conn[n], shedding)\n", " nodes_random[n] = min(nodes_random[n], shedding)\n", " nodes_random_2[n] = min(nodes_random_2[n], shedding)\n", " end\n", "\n", " append!(results[1], nodes_round_robin[1])\n", " append!(results[2], nodes_least_conn[1])\n", " append!(results[3], nodes_random[1])\n", " append!(results[4], nodes_random_2[1])\n", " end\n", " results\n", "end" ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [], "source": [ "Ρ = [0.1;0.25;0.55:0.1:0.96]\n", "results = [run_test(20, ρ, 200_000; shedding=Inf) for ρ in Ρ];" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Histogram" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "histogram([getfield(results[5],i) for i in 1:4], normed=true, nbins=[200 25 200 30], xlims=(0,60), ylims=(0,0.18), yticks=false, showaxis=:x, leg=:none, size=(400, 600), layout=(4,1), title=algorithm_names, tick_direction=:out, widen=true)\n", "vline!([[mean(getfield(results[5],i))] for i in 1:4], lw=3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Over load factor" ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Mean\n", "μ = [[mean(getfield(results[j],i)) for i in 1:4] for j in 1:length(Ρ)]\n", "plot(Ρ, hcat(μ...)', size=(600,250), label=algorithm_names, leg=:topleft, xaxis=\"Load factor\", yaxis=\"Average\", tick_direction=:out)" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Standard deviation\n", "σ = [[std(getfield(results[j],i)) for i in 1:4] for j in 1:length(Ρ)]\n", "plot(Ρ, hcat(σ...)', size=(600,250), label=algorithm_names, leg=:topleft, xaxis=\"Load factor\", yaxis=\"√Variance\", tick_direction=:out)" ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 109, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Entropy\n", "S₀ = entropy(getfield(results[5],1))\n", "plot([entropy(getfield(results[5],i))/S₀ for i in 1:4], seriestype=:bar, xticks=(1:4, algorithm_names), leg=false, size=(350,200))" ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S₀ = entropy(getfield(results[1],1))\n", "S = [[entropy(getfield(results[j],i))/S₀ for i in 1:4] for j in 1:length(Ρ)]\n", "plot(Ρ, hcat(S...)', size=(300,150), label=algorithm_names, leg=:none, xaxis=\"Load factor\", yaxis=\"Entropy\", tick_direction=:out)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Over cluster size" ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [], "source": [ "C = [1:19;20:10:50]\n", "results = [run_test(c, 0.8, 200_000) for c in C];" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Mean\n", "μ = [[mean(getfield(results[c],i)) for i in 1:4] for c in 1:length(C)]\n", "plot(C, hcat(μ...)', ylims=(0,NaN), size=(600,250), label=algorithm_names, leg=:bottomright, xaxis=\"Servers\", yaxis=\"Mean\", tick_direction=:out)" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Standard deviation\n", "σ = [[std(getfield(results[c],i)) for i in 1:4] for c in 1:length(C)]\n", "plot(C, hcat(σ...)', ylims=(0,NaN), size=(600,250), label=algorithm_names, leg=:outerbottomright, xaxis=\"Servers\", yaxis=\"√Variance\", tick_direction=:out)" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Entropy\n", "S₀ = entropy(getfield(results[1],1))\n", "S = [[entropy(getfield(results[c],i))/S₀ for i in 1:4] for c in 1:length(C)]\n", "plot(C, hcat(S...)', ylims=(0,NaN), size=(600,250), label=algorithm_names, leg=:outerbottomright, xaxis=\"Servers\", yaxis=\"Relative entropy\", tick_direction=:out)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Reciprocal of LogNormal\n", "If $X \\sim LogNormal(x,1)$ then $\\frac{1}{X} \\sim LogNormal(-x,1)$ ?\n", "\n", "Not exactly by quite close:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "samples = 1.0 ./ rand(LogNormal(log(1)-0.5), 100_000)\n", "histogram(samples, normed=true, xlims=(0,15), bins=400, label=\"Computed\")\n", "plot!(0:0.1:15, LogNormal(-log(1)+0.5), lw=3, label=\"LogNormal(-x,1)\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Argument for random-2\n", "\n", "Round robin is the default and easiest to understand but the least connections is superior at distributing requests evenly in the face of variable completion times. Least connections have a couble of disadvantages:\n", "\n", "1) When a new server comes online it will be overloaded with requests until it comes up to speed. This isn't desirable in our case because of the warmup time of the server.\n", "2) Each load balancer only has a partial view of the upstream servers\n", "3) Least connections is computationally (slightly) more CPU intensive" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.0", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.0" } }, "nbformat": 4, "nbformat_minor": 4 }