Simulation of the paper

sim.py

#!/usr/bin/env python
# encoding: utf-8
import random

# Parameters: N for N clusters,
# P for the computing power of a cluster,
# M for M requests at epoch t,
# T for the teardown time of a request.
# Qmin, Qavg, Qmax are for probability
# distribution law II(Qmin, Qavg, Qmax).
# ksi is prediction error,
# rho represents the dependency between two
# consecutive resource utilization values.
N, P, M, T = 30, 4, 100, 25
Qmin, Qavg, Qmax = 0, 1, 3
ksi, rho = 0.1, 0.5
p1 = ((Qmax-Qavg)*1.0)/((Qmax-Qmin)*(Qavg-Qmin))
p2 = ((Qavg-Qmin)*1.0)/((Qmax-Qmin)*(Qmax-Qavg))

# Status of a request after assigned.
# 0 for reject, 1 for drop, 2 for accept
status = [2] * M

# Z1[n][t] stores the estimated load of cluster n
# at epoch t, Z2[n][t] stores the real load of 
# cluster n at epoch t.
Z1, Z2 = [], []
for n in range(N):
  Z1.append([])
  Z2.append([])
  for t in range(T):
    Z1[n].append(0)
    Z2[n].append(0)
    
def select(p1, p2):
  """ Randomly select a cost."""
  p = p1+p2
  rand = random.uniform(0, p)
  if (rand > 0.0)  & (rand <= p1):
    cost = random.uniform(Qmin, Qavg)
  else:
    cost = random.uniform(Qavg, Qmax)
  return cost
  
def uniform():
  """ Uniform distribution function."""
  return random.uniform(-ksi*Qavg, ksi*Qavg)

# For generating the estimated computing power and
# the real computing power of a request at epoch t.
# For request m, X1[m][t] is the estimated computing
# power at epoch t, X2[m][t] is the real computing
# power at epoch t.
X, Y = [None]*T, [None]*T
X1, X2 = [None]*M, [None]*M
for m in range(M):
  Y = [select(p1, p2) for t in range(T)]
  for t in range(T):
    if t == 0:
      X[t] = Y[t]
    else:
      X[t] = rho*Y[t] + (1-rho)*X[t-1]
  X1[m] = X
  X2[m] = [(x+uniform()) for x in X]

def rand(c):
  # Usage: cluster = rand(clusters)
  return c[random.randint(0, len(c)-1)]

def ML(clusters, C):
  # Usage: cluster = ML(clusters, C)
  m = M
  result = 0
  for cluster in clusters:
    if  len(C[cluster]) < m:
      m = len(C[cluster])
      result = cluster
  return result

def MinCC(clusters, m):
  # Usage: cluster = MinCC(clusters, m)
  min, sum, result = 0, 0.0, clusters[0]
  for t in range(T):
    sum += (Z1[result][t]*X1[m][t])
  min = sum/T
  for cluster in clusters:
    sum = 0.0
    for t in range(T):
      sum += (Z1[cluster][t]*X1[m][t])
    if min > (sum/T):
      min = sum/T
      result = cluster
  return result

def MaxCC(clusters, m):
  # Usage: cluster = MaxCC(clusters, m)
  max, sum, result = 0, 0.0, clusters[0]
  for t in range(T):
      sum += (Z1[result][t] * X1[m][t])
  max = sum/T
  for cluster in clusters:
    sum = 0.0
    for t in range(T):
      sum += (Z1[cluster][t]*X1[m][t])
    if max < sum/T:
      max = sum/T
      result = cluster
  return result

def MP(clusters, m):
  # Usage: cluster = MP(clusters, m)
  result = cluster = clusters[0]
  sum1, sum2 = 0.0, 0.0
  for t in range(T):
    sum1 += ((Z1[cluster][t]+X1[m][t])**2)
    sum2 += (Z1[cluster][t]+X1[m][t])
  sum1 /= T
  sum2 = (sum2/T)**2
  min = sum1-sum2
  for cluster in clusters:
    sum1, sum2 = 0.0, 0.0
    for t in range(T):
      sum1 += ((Z1[cluster][t]+X1[m][t])**2)
      sum2 += (Z1[cluster][t]+X1[m][t])
    sum1 /= T
    sum2 = (sum2/T)**2
    if (sum1-sum2) < min:
      min = sum1-sum2
      result = cluster
  return cluster

def GFK(clusters, m, K):
  # Usage: cluster = GFK(clusters, m, 1)
  # OR: cluster = GFK(clusters, m, 2)
  result = clusters[0]
  min = 0.0
  for t in range(T):
    min += ((P-Z1[result][t]-X1[m][t])**K)
  min /= T
  for cluster in clusters:
    sum = 0.0
    for t in range(T):
      sum += ((P-Z1[cluster][t]-X1[m][t])**K)
    sum /= T
    if sum < min:
      min = sum
      result = cluster
  return result 

def main():
  for request in range(M):
    # For every request, if one cluster can meet
    # this request, choose it as a candidate.
    candidates = []
    for a_cluster in range(N):
      for t in range(T):
        if (X1[request][t] + Z1[a_cluster][t]) > P:
          break
      if X1[request][t] + Z1[a_cluster][t] <= P:
        candidates.append(a_cluster)
    if len(candidates) == 0:
      # There are no clusters that can 
      # meet this request, reject it.
      status[request] = 0
    elif len(candidates) > 0:
      cluster = rand(candidates)
      for t in range(T):
        if (X2[request][t] + Z2[cluster][t]) > P:
          # After calculating, find that the cluster
          # can't meet this request, drop it.
          status[request] = 1
          break
      if (X2[request][t] + Z2[cluster][t]) <= P:
        # After Calculating, find that the cluster can
        # meet the request during every period, accept it.
        for t in range(T):
          Z1[cluster][t] += X1[request][t]
          Z2[cluster][t] += X2[request][t]
   
  c1, c2, c3 = 0, 0, 0
  for request in range(M):
    if status[request] == 0:
      c1 += 1
    elif status[request] == 1:
      c2 += 1
    elif status[request] == 2:
      c3 += 1

  f = open("data.txt", 'a')
  f.write(str(c1) + " " + str(c2) + " " + str(c3) + "\n")
  f.close()

if __name__ == "__main__":
  main()