tu.scheduling.ipynb

{
 "metadata": {
  "name": "tu.scheduling"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Scheduling problem specification\n",
      "=================================\n",
      "\n",
      "We have:\n",
      "    \n",
      "- $servers$, a set of active servers constituting the cloud, cardinality $n$\n",
      "- $VMs$, a set of VMs provided to the users, cardinality $m$\n",
      "\n",
      "Both sets can change in any moment by creating/deleting VMs or adding/removing servers. These events are not controlled by the scheduler.\n",
      "\n",
      "The cloud provider defines a set of $r$ resource types reserved for a VM that have to be specified through an SLA. The exact values specified through individual SLAs for these resources are an ordered r-tuple of numbers, defined as a VM's $spec$:\n",
      "    \n",
      "$spec_{vm} = \\left(res_{vm,i},\\, \\forall i \\in \\{1, \\ldots, r\\}\\right),\\, \\forall vm \\in VMs$\n",
      "\n",
      "\n",
      "Similarly, the capacity of a server is defined as a r-tuple of the resource amounts it has:\n",
      "\n",
      "$spec_{s} = \\left(cap_{s,i},\\, \\forall i \\in \\{1, \\ldots, r\\}\\right),\\, \\forall s \\in servers$\n",
      "\n",
      "In every moment, every VM has to be allocated to some server (belong to its $alloc$ set) that acts as its host. This is the first problem constraint (C1):\n",
      "\n",
      "$\\left(\\forall s \\in servers \\to alloc_s \\subseteq VMs \\right)\\, s.t. \\left( \\forall vm \\in VMs,\\, \\exists_{=1} s \\in servers \\to vm \\in alloc_s \\right)$\n",
      "\n",
      "The other constraint (C2) is that at any given time a server cannot host VMs that require more resources in sum that it can provide.\n",
      "\n",
      "$\\forall s \\in servers,\\, \\forall i \\in \\{1, \\ldots, r\\}  \\to  \\sum_{vm \\in alloc_s} res_{vm,i} < cap_i$\n",
      "\n",
      "Implementation\n",
      "---------------"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# some non-semantic functionality common for VMs and servers\n",
      "class Machine(object):\n",
      "    def __init__(self, *args):\n",
      "        self.spec = {}\n",
      "        for (i, arg) in enumerate(args):\n",
      "            self.spec[resource_types[i]] = arg\n",
      "    def __str__(self):\n",
      "        return str(self.spec)\n",
      "\n",
      "# the model\n",
      "class VM(Machine):\n",
      "    def __init__(self, *args):\n",
      "        super(VM, self).__init__(*args)\n",
      "        self.res = self.spec\n",
      "\n",
      "class Server(Machine):\n",
      "    def __init__(self, *args):\n",
      "        super(Server, self).__init__(*args)\n",
      "        self.cap = self.spec\n",
      "        self.alloc = set()\n",
      "\n",
      "# constraint checking\n",
      "# C1\n",
      "def is_allocated(servers, vm):\n",
      "    for s in servers:\n",
      "        if vm in s.alloc:\n",
      "            return True\n",
      "    return False\n",
      "\n",
      "def all_allocated(servers, VMs):\n",
      "    for vm in VMs:\n",
      "        if not is_allocated(servers, vm):\n",
      "            return False\n",
      "    return True\n",
      "\n",
      "#C2\n",
      "def within_capacity(s):\n",
      "    for i in resource_types:\n",
      "        used = 0\n",
      "        for vm in s.alloc:\n",
      "            used += vm.res[i]\n",
      "        #print('%d vs %d' % (used, s.cap[i]))\n",
      "        if used > s.cap[i]:\n",
      "            return False\n",
      "    return True\n",
      "\n",
      "def all_within_capacity(servers):\n",
      "    for s in servers:\n",
      "        if not within_capacity(s):\n",
      "            return False\n",
      "    return True"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 204
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Example\n",
      "-------"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "resource_types = ['RAM', '#CPUs']\n",
      "\n",
      "# some servers\n",
      "s1 = Server(4000, 2)\n",
      "s2 = Server(8000, 4)\n",
      "servers = set([s1, s2])\n",
      "\n",
      "# some VMs\n",
      "vm1 = VM(2000, 1);\n",
      "vm2 = VM(2000, 2);\n",
      "VMs = set([vm1, vm2])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 205
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(s1)\n",
      "print(s2)\n",
      "print(vm1)\n",
      "print(vm2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "{'RAM': 4000, '#CPUs': 2}\n",
        "{'RAM': 8000, '#CPUs': 4}\n",
        "{'RAM': 2000, '#CPUs': 1}\n",
        "{'RAM': 2000, '#CPUs': 2}\n"
       ]
      }
     ],
     "prompt_number": 206
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# allocate and check capacity and allocation\n",
      "s1.alloc.add(vm1)\n",
      "print(all_within_capacity(servers))\n",
      "print(all_allocated(servers, VMs))\n",
      "\n",
      "s1.alloc.add(vm2)\n",
      "print(all_within_capacity(servers))\n",
      "print(all_allocated(servers, VMs))\n",
      "\n",
      "s1.alloc.remove(vm2)\n",
      "s2.alloc.add(vm2)\n",
      "print(all_within_capacity(servers))\n",
      "print(all_allocated(servers, VMs))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "True\n",
        "False\n",
        "False\n",
        "True\n",
        "True\n",
        "True\n"
       ]
      }
     ],
     "prompt_number": 207
    }
   ],
   "metadata": {}
  }
 ]
}