ProximityScheduler

Proximity Scheduler

Why proximity scheduler

In heterogeneous high performance computing environment on OpenStack, proximity of hosts is critical to achieve high performance due to the cost of communication among the hosts. Thus, the scheduler needs to be able to use topology and location information of each host to allocate a set of hosts that are located close each other.

Approach

Scheduler gets topology and location information at the time of deployment or at the time of system upgrade. When more than one instance is requested and proximity requirement is set, the scheduler allocates a set of hosts that are close each other. It involves modification of filter_scheduler to be able to consider available hosts at the same time and returns the best chosen hosts instead of returning one by one. Cost function also needs modification to consider the topology and location of each host to choose the best set of hosts.

Many different algorithms can be employed to choose the best set. For a large system, exhaustive search is not feasible, so a heuristic algorithm needs to be employed. One possible algorithm is using breadth-first search with modifications of considering more than one level when choosing next candidates. The algorithm can run N times with each different node as the first candidate host, where N is the number of available hosts. From the candidate hosts, a host that has least distance from already-chosen set of hosts is added to the chosen set.

The following algorithm illustrate it, but ntoe that it is not very accurate.

for each host h in available hosts:
    chosen_set(h) = h
    dist = 2
    while True:
        candidate_set = hosts that are not farther than dist from h
        while candidate_set is not empty:
            choose a host that has least distance from all of hosts in chosen_set
            add the chosen host to chosen_set; remove it from candidate_set
            if chose_set has the required number of host
                break
        dist++
choose the best chosen_set(h)

Files to be modified

nova/scheduler/filter_scheduler.py

Curent filter_scheduler chooses hosts one by one in greedy algorithm. This does not work for proximity scheduler that needs to get a set of hosts that are close each other. Thus, instead of getting hosts one by one, it needs to be modified a set of hosts at once.

nova/scheduler/least_cost.py

Least cost file needs modification to have the new host selection algorithm.