sched_simulation.py

def least_resources(new_per_zone, existing_per_zone):
  # assume a weight of 1 per pod, max 100 pods per node
  scores = []
  for i in range(len(new_per_zone)):
    zone_scores = []
    for j in range(len(new_per_zone[i])):
      pods = new_per_zone[i][j] + existing_per_zone[i][j]
      zone_scores.append(max(100-pods, 0))
    scores.append(zone_scores)
  return scores

def original_normalize(counts):
  total = sum(sum(c) for c in counts)
  min_score = min(min(c) for c in counts)
  scores = []
  for zone in counts:
    zone_scores = []
    for node in zone:
      if total-min_score == 0:
        s = 100
      else:
        s = (total-node) * 100 // (total-min_score)
      zone_scores.append(s)
    scores.append(zone_scores)
  return scores

def min_max_normalize(counts):
  total = sum(sum(c) for c in counts)
  min_score = min(min(c) for c in counts)
  max_score = max(max(c) for c in counts)
  scores = []
  for zone in counts:
    zone_scores = []
    for node in zone:
      if min_score + max_score == 0:
        s = 100
      else:
        s = (min_score+max_score-node) * 100 // (min_score+max_score)
      zone_scores.append(s)
    scores.append(zone_scores)
  return scores

def topology_spreading(new_per_zone, existing_per_zone):
  counts = []
  for zone in new_per_zone:
    zone_counts = []
    base_count = sum(zone)
    for node in zone:
      zone_counts.append(base_count+node)
    counts.append(zone_counts)

  return min_max_normalize(counts)

def score(new_per_zone, existing_per_zone):
  scores = []
  for zone in new_per_zone:
    scores.append([0] * len(zone))
  for w, f in [(2, topology_spreading), (1, least_resources)]:
    ns = f(new_per_zone, existing_per_zone)
    #print("partial scores: %s" % ns)
    for i in range(len(scores)):
      for j in range(len(scores[i])):
        scores[i][j] += ns[i][j] * w
  return scores

def find_max(scores):
  global_max = 0
  m_i = 0
  m_j = 0
  for i in range(len(scores)):
    zone = scores[i]
    for j in range(len(zone)):
      if zone[j] > global_max:
        global_max = zone[j]
        m_i = i
        m_j = j
  return m_i, m_j


def main(existing, new_pods):
  new_per_zone = []
  for zone in existing:
    new_per_zone.append([0] * len(zone))

  for p in range(new_pods):
    scores = score(new_per_zone, existing)
    i, j = find_max(scores)
    new_per_zone[i][j] += 1
    #print("SCORES:     %s" % scores)
    #print("NEW COUNTS: %s\n" % new_per_zone)
  print(new_per_zone)

if __name__ == '__main__':
  # main([[10, 0], [5, 15]], 20)
  # main([[20, 0], [10, 30]], 20)
  # main([[40, 0], [20, 60]], 20)
  # main([[80, 0], [40, 100]], 20)
  main([[10, 0, 10], [5, 15, 10]], 20)
  main([[20, 0, 20], [10, 30, 20]], 20)
  main([[40, 0, 40], [20, 60, 40]], 20)
  main([[80, 0, 80], [40, 100, 80]], 20)