# Dynamic Cost-Aware Routing of Web Requests
## 5 Cost-Aware S-Model Reward Penalty Epsilon (CA-S) Learning Automaton  
A proxy server operates as a front end for a given web service. The service is handled by a set of origin servers and each server may be deployed at a different DC location. The proxy receives web requests from the users and forwards them to the origin servers following certain criteria. The reply from each origin server is sent to the proxy, which forwards the content to the client. The CA-S LA supporting the proxy's decisions allows for achieving an adaptive and autonomous selection of servers based on observed costs that are mapped to selection probabilities.  
Servers start with equal probability. When the LA receives a response from an origin server, it notes the request response time and the origin server's power level to calculate a combined cost that serves to either increase (reward) or decrease (penalize) its selection probability. In the S-model LA, the actions are rewarded or penalized in a proportional amount to the performance. The amount of reward is larger for a higher favorable response and smaller for a lower favorable response. In the same way, the amount of penalty is larger for higher unfavorable performance and smaller for lower unfavorable response. The performance of the server is given by the combined cost of energy and revenue loss. The LA computes the normalized cost value of the current server to make the reward or penalty proportional. The calculation of the normalized cost and the reinforcement equations used to update the selection probabilities are explained next.  
The combined cost \(z(t)\), as defined by Equation (5), is computed for all of the servers after each transaction, using the response time (delay) and energy cost as explained in Section 3. Even though the response is received from the selected server, the costs are updated for all server entries to accommodate the time varying electricity prices at each location. The exponential average cost \(prev\_cost\) at an instance \(t\) is calculated from the current cost \(z(t)\) as follows:  
\[prev\_cost(t)=\alpha*z(t)+(1-\alpha)*prev\_cost(t-1), \tag{6}\]  
where \(\alpha\) is the weight given to the most recent value. The cost obtained from the selected server at a location (index) \(v\) at time \(t\) is normalized as \(\beta_{v}(t)\):  
\[\begin{split}&\beta_{v}(t)=\frac{\left(prev\_cost_{v}(t)-m_{1}(t) \right)}{m_{2}(t)-m_{1}(t)}\,\text{ where}\\ & m_{1}(t)=\min\left\{prev\_cost_{1}(t),prev\_cost_{2}(t),\cdots, prev\_cost_{r}(t)\right\}\ \text{ and}\\ & m_{2}(t)=\max\left\{prev\_cost_{1}(t),prev\_cost_{2}(t),\cdots, prev\_cost_{r}(t)\right\}.\end{split} \tag{7}\]  
The normalized value \(\beta_{v}\) of \(prev\_cost\) determines the amount of reward or penalty. If the selected server gives the minimum delay and minimum energy cost among all servers then \(\beta_{v}\) will be zero and it will receive a larger reward; if the selected server gives the largest \(prev\_cost\), it will be penalized more because \(\beta_{v}\) will be larger. The selection probabilities of the servers are updated as follows:  
\[\begin{split}& P_{i}\left(t+1\right)=P_{i}\left(t\right)+a\left(1 -\beta\right)\left(1-P_{i}\left(t\right)\right)-b\beta\ P_{i}\left(t\right), for\ i=v,\\ & P_{i}(t+1)=P_{i}(t)-a\left(1-\beta\right)P_{i}(t)+b\beta\left( \frac{1}{N-1}-P_{i}(t)\right),\forall\ i\
eq v.\end{split} \tag{8}\]  
The constants \(a\) and \(b\) are the learning parameters. The use of \(\beta_{v}\) in reinforcement equations makes the learning rate adaptive to the servers' responses. Figure 2 explains the action flow executed by the LA when making a server selection and the learning flow when a response arrives. Optionally, automaton decisions can be further modulated with a random walk process, which occurs with probability \(P_{rw}\), to reduce the risk of reaching a local minima.