## 4 Algorithms
**Algorithm Calculator**  
**Input:**_PerforTable[][]_ or _resource information /* *._rrd \(\parallel\) *.log */  
**Output:**_PerforTable[][]_  
**{If** (receive network status and node information from Collector) /* collected by Ganglia and NWS */  
Store the information in _LocalBuffer_,  
**Else** (Time \(T\) times out)  
{Send a _CalculatorRequest_ to Front Unit;  
Wait for a time period, e.g., _T1_, so as to receive _PerforTable[][]_; /* including other MCI servers'  
**For** (\(w=L\); \(w\geqq I\); \(w\)-) /* checking nodes that have left the system; L is the number of tuples in the underlying MCI server's service area, excluding other MCI servers' performance tables */  
**{If** (the IP in _PerforTable[w][1]_ does not appear in the _receiving-node-IPs_ received from Ganglia /* the resource node has left the system */)  
**If** (the corresponding node, e.g., D, is executing a job, e.g., y)  
{_enqueueRequest_ (y, _GBQ(\(R_{y}\))_);  
**If** (D has \(q\) requests waiting in its waiting queue)  
{**For** (i = 1; i < \(q\) + 1; i++)  
_enqueueRequest_(i, _GBQ(\(R_{i}\))_);}  
Delete the w\({}^{\text{th}}\) tuple from _PerforTable[][]_;}  
**If** (a _receiving-node-IP_ in _LocalBuffer_ has no corresponding tuple in _PerforTable[][1]_)  
/* a new node, _receiving-node-IP_, received from the Ganglia */  
{Create a new tuple for the new node in _PerforTable[][]_;  
Insert information of the new node to the tuple based on the data collected by Ganglia and NWS; _/*_ including columns 1-7, 10 and 11 of the new tuple in of _PerforTable[][]_ */  
**For** (\(q=1\); \(q\leqq L\)'; \(q\)++) /* _PerforTable[][]_, including child MCI servers' performance tables, currently has \(L\)' tuples; calculating performance scores for nodes */  
{_PerforTable[q][8]_ = \(\sum\limits_{k=2}^{6}\) _PerforTable[q][k]_;  
_/*_ updating the tuple _PerforTable[q][]_ where k = 2 to 6 represent columns 2 to 6 of _PerforTable[][]_, and 8 is the 8 th column, i.e., Performance Score field */  
**If** (_PerforTable[q][8]_ \(\geqq 17\))/* level-1 */  
**{If** (_PerforTable[q][10]_ = _null_) _/* a newly arriving node */_  
_PerforTable[q][10]_ = 1;/* its Original-Performance-Score=1 */  
_PerforTable[q][9]_ = 1;/* its Performance-Level = 1 */  
**Else** **if** (15 \(\leqq\)_PerforTable[q][8]_ \(\leqq 16\)) /* level-2 */  
**{If** (_PerforTable[q][10]_ = _null_) _PerforTable[q][10]_ = _2; /* its Original-Performance-Level=2 */  
Figure 6: The algorithm performed by Calculator periodically. **Figure 7** (Figure 8) shows the allocation part (semi-preemption part) of the algorithm, _i.e._, SPA() (_i.e._, PreemptiveSPA()), performed by Scheduler. As stated above, Scheduler periodically or on receiving a performance-table-newly-updated message from Calculator invokes SPA() to allocate resource nodes to serve user requests. Resource preemption is only on local resource nodes. **SPA**(request _x_)/*Semi-preemptive Algorithm performed by Scheduler; resource allocation portion*/  
\(\{R_{x}=\textit{Type}(x);\)  
Send a _SchedulerMessage_ to Front Unit;  
Wait for a time period to receive _PerforTable[][][]_; /* loading performance table under the assumption that this table currently has \(L\) tuples */  
For (_i_ = 1;_i_ \(\leqq\)  3; i++)  
\(\{L_{i}=\{\mbox{IP}|\textit{PerforTable[IP][9]}=i\};\)  
/* currently level-_i_ resource nodes, _i_=1,2,3 */  
\(OL_{i}=\{\mbox{IP}|\textit{PerforTable[IP][10]}=i\}\}\);  
/* originally level-_i_ resource nodes, _i_=1,2,3 */  
\(C_{11}=\) R1 % of the highest perfor. scores of \(OL_{1}\); /* the set of R1 %, see Equation (2) */  
\(C_{21}=\) R2 % of the highest perfor.