Este capítulo detalha o funcionamento do XTC, fornecendo a descrição das etapas do projeto. 
\section{Visão Geral}
\label{sec:xtc.visaGeral}
O XTC proposto neste projeto é um mecanismo de controle de vazão para roteadores virtualizados baseados em Xen. Esse mecanismo é projetado
para executar no Provedor de Infraestrutura (InP), ajustando o \textit{cap} de cada roteador virtual conforme a vazão máxima desejada. 
A limitação da vazão permite isolar roteadores virtuais de uma mesma máquina física, auxiliando um ambiente de redes virtuais a cumprir o requisito de Isolamento mostrado na Seção~{\ref{sec:virtualizacaoRedes}}.
O XTC é uma proposta flexível para controle de vazão em redes virtuais, pois não controla individualmente cada interface de rede de um roteador virtual através de 
técnicas de controle de pacotes conhecidas como o TC (\textit{Traffic Control}) do Linux~\cite{almesberger2001linux}. 
Ao invés disso, controla o tráfego como um todo, atuando na capacidade do roteador de encaminhar pacotes através da fatia de CPU atribuída a ele. Isso faz com que 
o XTC permita que o administrador de um roteador virtual tenha liberdade em controlar o tráfego de cada interface de rede, preservando a noção
de ``rede virtual'' dada ao administrador. Assim, o mecanismo possui como objetivo 
apenas orquestrar a máxima vazão agregada oferecida para cada roteador de uma máquina física, deixando para o administrador do roteador virtual a tarefa de gerenciamento 
do tráfego de suas interfaces. Essa característica do XTC possibilita que os requisitos de Flexibilidade e Gerenciabilidade da Seção~{\ref{sec:virtualizacaoRedes}}  não sejam violados.
Além disso, no XTC é necessário apenas um controlador para cada roteador virtual e não para cada interface de rede, favorecendo assim o requisito de Escalabilidade da Seção~{\ref{sec:virtualizacaoRedes}}.

\begin{figure}
\centering

\subfigure[Diagrama de blocos.]
{\label{fig:tcm}
\includegraphics[width=0.6\textwidth]{./figuras/tcm.eps}}
\hfill
\subfigure[Exemplo de utilização do XTC.]
{\label{fig:systemOverview}
\includegraphics[width=0.379\textwidth]{./figuras/systemOverview.eps}}

\caption{XTC: \textit{Xen Throughput Control.}}

\end{figure}

O XTC é um sistema de controle realimentado, como visto na Figura~\ref{fig:tcm}, que atua no \textit{cap} atribuído a cada roteador virtual para atingir uma determinada vazão. 
Para isso, o sistema mede periodicamente a vazão do roteador virtual e calcula o erro entre essa medida e a vazão de referência. Esse valor de referência representa o valor de vazão desejado no roteador virtual.
 Assim, o bloco Controlador
calcula e ajusta o \textit{cap} do roteador virtual de acordo com o valor do erro medido. Esse bloco consiste em um controlador do tipo Proporcional-Integral (PI).
O bloco Sistema Xen modela o comportamento da vazão do roteador virtual conforme o \textit{cap} atribuído. A modelagem desse bloco é realizada a partir de dados 
experimentais. Esse bloco é importante para o projeto do Controlador, pois é essa modelagem que serve como base para a escolha dos parâmetros do controlador PI. Inicialmente, esses parâmetros foram
 calculados manualmente. Como é mostrado adiante, o bloco Regulador Autoajustável é utilizado para calcular esses parâmetros automaticamente a partir de uma estimativa
do comportamento do Sistema Xen.

A Figura~\ref{fig:systemOverview} mostra um exemplo de utilização do XTC. Nesse exemplo, existe uma instância do XTC para cada roteador virtual. O Mecanismo de Policiamento (MP)
 controla todos os XTCs, sendo responsável por ativar ou desativar cada instância. O MP também é responsável por informar a vazão de referência de cada XTC. As ações
 do MP são realizadas baseadas no conhecimento do ambiente obtido através de medidas de utilização e políticas definidas pelo administrador do sistema. Como exemplo,
o MP pode detectar uma situação de gargalo e limitar a vazão de cada roteador utilizando o XTC. Assim, o mecanismo garantirá os requisitos de cada
roteador virtual. Este trabalho aborda apenas o projeto do XTC, sendo o papel do MP executado manualmente.

\section{Modelagem do Sistema Xen}
\label{sec:modelagem}

O bloco Sistema Xen modela o comportamento da vazão encaminhada por um roteador virtual de acordo com o \textit{cap} atribuído a ele. Para construir esse modelo,
utiliza-se uma abordagem de caixa preta~\cite{wang-utilization}. Nessa abordagem as variáveis internas do sistema são desconhecidas e então  o modelo é construído a partir da relação entre a entrada e saída do sistema com base em dados experimentais obtidos a partir
das etapas descritas a seguir.

\subsection{Aquisição dos Dados de Treinamento do Sistema}
\label{sec:treinamento}
Para a modelagem do Sistema Xen é utilizado um experimento para extrair a relação entre \textit{cap} e vazão, utilizando a plataforma de testes descrita na Seção~\ref{sec:testbed}
com a máquina CT desligada. Nesse experimento pacotes são enviados do GT para o RT,
através de um roteador virtual da máquina ET, utilizando taxa e tamanho de pacote fixos. Esse envio de pacotes consiste em um fluxo UDP (\textit{User Datagram Protocol}) gerado pelo Iperf~\cite{tirumala2004iperf}
durante 30~segundos. O experimento é realizado para diversos valores de \textit{cap} atribuídos ao roteador virtual e a vazão média obtida é medida.
A Figura~\ref{fig:capVariation02_64} mostra o resultado utilizando pacotes de 64 bytes de dados e diferentes taxas de pacotes (em kilopacotes por segundo). O eixo~X representa o \textit{cap} atribuído
ao roteador e o eixo~Y mostra a vazão obtida. É importante notar que a relação entre \textit{cap} e vazão depende da taxa de pacotes do fluxo encaminhado pelo roteador.
Quanto maior a taxa, mais CPU será necessária pois o roteador virtual deverá encaminhar mais rapidamente os pacotes entre suas interfaces virtuais para atingir a vazão do fluxo enviado.
Outra característica, não apresentada nesses resultados, é o tamanho do pacote. Tamanhos maiores de pacote resultam em maior vazão para
a mesma taxa de pacotes.

A Figura~\ref{fig:capVariation02_64} mostra também que o aumento da vazão ocorre até certo valor de \textit{cap}. A vazão obtida atinge um valor igual à
taxa de bits gerada pois o roteador virtual recebeu quantidade suficiente de recursos de CPU. Apesar disso, abaixo desse valor de \textit{cap}, a vazão se altera 
de forma aproximadamente logarítmica. Assim, essa região é considerada na modelagem do sistema como a região de interesse.
Também foram realizados experimentos com pacotes de 1470 bytes, que mostraram o mesmo comportamento logarítmico observado para pacotes de 64 bytes. 
A diferença, porém, foi no aumento da vazão para cada valor de \textit{cap} que é um efeito esperado para pacotes maiores.
Consequentemente, neste trabalho serão utilizados fluxos de 64 bytes para permitir taxas maiores de pacotes em um enlace Gigabit.
É importante notar também que, como este experimento utiliza o parâmetro \textit{cap}, que é uma porcentagem de CPU, os valores de vazão
obtidos serão dependentes das máquinas utilizadas. Entretanto, o comportamento apresentado neste experimento se manterá independente
das máquinas utilizadas. Como o projeto do XTC depende do modelo obtido neste experimento, o mecanismo necessita de um treino inicial
para uma determinada especificação das máquinas utilizadas. Apesar disso, considerando a utilização do Regulador Autoajustável
que ajusta o XTC a mudanças no sistema, essa necessidade não é um obstáculo.

%
%Gerado com o script generate_result_throughput_64.gnu
\begin{figure}
\centering
\includegraphics[width=0.65\textwidth]{./graficos/capVariation02_64.eps}
\caption{Variação de \textit{cap} para pacotes de 64 bytes.}
\label{fig:capVariation02_64}
\end{figure}

%

\subsection{Desenvolvimento do Modelo}
\label{sec:desenvolvimentoModelo}

A modelagem do Sistema Xen utiliza os resultados da Seção~\ref{sec:treinamento} para representar esse bloco com uma função de transferência discreta.
Para isso, modelou-se o Sistema Xen por um sistema de primeira ordem dado pela Equação~\ref{eq:xenSystemModel}:
%
\begin{equation}
  y(k + 1) = ay(k) + bu(k).
 \label{eq:xenSystemModel}
\end{equation}
%
Como foi utilizado um sistema linear
para representar o comportamento não linear do sistema, a Equação~\ref{eq:xenSystemModel} é um modelo linearizado do sistema.
Nessa linearização considera-se que o sistema é linear em torno de um ponto de operação.
Assim, os sinais $y(k)=\tilde{y}(k) - \bar{y}$ e $u(k)=  \tilde{u}(k) - \bar{u}$ são valores de \textit{offset} de seus pontos de operação, onde
$\tilde{y}(k)$ e $\tilde{u}(k)$ são os valores reais dos sinais do Sistema Xen e $\bar{y}$ e $\bar{u}$ são os pontos de operação.

Na Equação~\ref{eq:xenSystemModel}, $y(k)$ e $u(k)$ indicam, respectivamente, a vazão obtida no roteador e o $\log_{10}(cap)$ na entrada do sistema na amostra $k$. Utiliza-se
o valor $\log_{10}(cap)$ ao invés do $cap$ absoluto devido à relação aproximadamente logarítmica entre \textit{cap} e vazão na região de interesse. 
A Figura~\ref{fig:capVariation02_64_log} mostra a relação entre a vazão e o $\log_{10}(cap)$, que
é uma relação mais próxima de ser linear na região de interesse do que a apresentada na Figura~\ref{fig:capVariation02_64}.
Assim, o modelo de primeira
ordem da Equação~\ref{eq:xenSystemModel} atende às necessidades da modelagem e simplifica o projeto do mecanismo.

\begin{figure}
\centering
\includegraphics[width=0.65\textwidth]{./graficos/capVariation02_64_log.eps}
\caption{Variação do $\log_{10}\textit{cap}$ para pacotes de 64 bytes.}
\label{fig:capVariation02_64_log}
\end{figure}

Para encontrar a função de transferência do Sistema Xen,
aplica-se a Transformada Z em ambos os lados da Equação~\ref{eq:xenSystemModel} e, a partir de manipulações algébricas, 
obtém-se a função $G(z)$ da Equação~\ref{eq:xenSystemTransferFunction}.
%
%
\begin{equation}
  G(z)=\frac{Y(z)}{U(z)} = \frac{b}{z-a}.
 \label{eq:xenSystemTransferFunction}
\end{equation}

  O próximo passo para modelar o Sistema Xen é obter os valores das constantes $a$ e $b$ que caracterizam esse sistema na Equação~\ref{eq:xenSystemTransferFunction}.
Como mencionado anteriormente, o comportamento do Sistema Xen e, consequentemente, $a$ e $b$, dependem da taxa de pacotes e do tamanho do pacote
do fluxo encaminhado. As constantes $a$ e $b$ também podem modelar fluxos agregados considerando-os como um único fluxo com o valor médio de suas 
taxas e tamanhos de pacotes.

 Para mostrar que um sistema de primeira ordem atende às necessidades da modelagem, o Sistema Xen é modelado encaminhando um fluxo com taxa de pacotes constante de 100~kp/s (kilopacotes por segundo)
e tamanho de pacote de 64 bytes. Esse exemplo é usado até o final desta seção como prova de conceito. 
Para modelar o bloco Sistema Xen utilizou-se a abordagem do tipo caixa preta, como em~\cite{wang-utilization}. Nessa abordagem primeiramente
são obtidos dados experimentais variando a entrada do sistema e observando a saída resultante, como feito na Seção~\ref{sec:treinamento}.
A partir desses resultados os parâmetros $a$ e $b$ do modelo são calculados utilizando regressão por mínimos quadrados.
No presente trabalho, esse método utiliza os dados de treinamento obtidos na Seção~\ref{sec:treinamento} para um fluxo com as características
do exemplo e calcula os valores de $a$ e $b$ em torno de um ponto de operação. Os valores do ponto de operação utilizados são os valores médios na região de interesse, dados 
por $\bar{y}= 40~Mb/s$ e $\bar{u}=1,39$. Essa região foi escolhida como a que representa o comportamento do sistema enquanto o \textit{cap}
ainda possui efeito e a vazão não satura. No exemplo, essa região corresponde a $cap\leq60$ como indicado na Figura~\ref{fig:capVariation02_64}. 
Para realizar a regressão por mínimos quadrados utilizou-se a função \texttt{mldivide} do MATLAB~\cite{matlab}.
Na chamada dessa função são fornecidas as entradas e as saídas correspondentes obtidas experimentalmente e o MATLAB retorna os valores de $a$ e $b$ do modelo.
O Apêndice~\ref{apendiceModelagem} apresenta o \textit{script} do MATLAB utilizado para os cálculos dos parâmetros.
A partir dos dados retornados pelo MATLAB, obtém-se
$a=0,0915$ e $b=32259$. 

Para calcular a acurácia do modelo em relação aos dados experimentais utiliza-se a métrica $R^2$ e o Gráfico de Resíduos.
A Equação~\ref{eq:rsquare} mostra o cálculo da métrica $R^2$, na qual ${y}$ é um vetor com os valores reais de vazão obtidos no experimento, $\hat{y}$ é um vetor
com os valores de vazão estimados pelo modelo para cada valor de \textit{cap} utilizado no experimento e $var(y)$ é a variância de ${y}$.
A métrica $R^2$ quantifica a variação da saída capturada pelo modelo e varia de 0 (pior modelo) para 1 (melhor modelo). 
A partir do \textit{script} do Apêndice~\ref{apendiceModelagem}, calcula-se a métrica $R^2$ com os valores de $a$ e $b$ encontrados
nesse exemplo e obtém-se $R^2=0,9899$, o que sugere uma boa modelagem. A Figura~\ref{fig:graficoResiduos}
mostra o Gráfico de Resíduos que representa a saída prevista pelo modelo, ou a vazão do roteador, como uma reta e os valores reais obtidos no experimento como pontos.
É importante observar que esse gráfico possui valores negativos de vazão pois representam o valor de \textit{offset} em torno do ponto de operação de $40~Mb/s$.
Assim, por exemplo, um valor no gráfico de $-5Mb/s$ equivale a uma saída de $35~Mb/s$.
Em um modelo perfeito, os pontos experimentais sempre estarão sobre a curva no Gráfico de Resíduos.
Assim, a partir da Figura~\ref{fig:graficoResiduos}, pode ser observado que os pontos experimentais estão bem próximos 
da curva, o que sugere mais uma vez uma boa modelagem. 
%
%
\begin{equation}
  R^2=1-\frac{var({y-\hat{y}})}{var({y})}.
 \label{eq:rsquare}
\end{equation}


\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{./graficos/modelEvaluation_100_log.eps}
%\includegraphics{./graficos/modelEvaluation_100_log.eps}
\caption{Gráfico de Resíduos.}
\label{fig:graficoResiduos}
\end{figure}
 
\section{Projeto do XTC}
\label{sec:projeto}
O mecanismo principal do XTC consiste dos blocos Controlador e Regulador Autoajustável cujos projetos são apresentados a seguir.

\subsection{Controlador}
\label{sec:projetoControlador}

Em um sistema de controle realimentado, o controlador em geral calcula o valor de entrada da planta controlada de acordo o valor de referência e o valor medido
na saída da planta. No caso do XTC, o Controlador deve decidir qual valor de \textit{cap} deve ser fornecido ao Sistema Xen para atingir a vazão de referência. Essa decisão
é realizada periodicamente de acordo com medidas na saída do Sistema Xen, que representa a vazão do roteador, e o conhecimento sobre decisões passadas do Controlador. O bloco
Controlador é do tipo Proporcional-Integral~(PI), que possui a lei de controle dada pela Equação~\ref{eq:piControlLaw}, possuindo assim
a função de transferência dada pela Equação~\ref{eq:piFcTransf}. Na Equação~\ref{eq:piControlLaw}, 
$u(k)$ é a decisão do controlador na amostra $k$, que representa o $\log_{10}(cap)$, e $e(k)$ é o erro calculado pela diferença entre a vazão de referência e a alcançada na amostra $k$.
É importante notar que esse bloco calcula a sua decisão atual baseado no valor atual e anterior do erro e também na sua própria decisão anterior. O controlador
PI foi escolhido por possuir erro zero em regime permanente, o que significa que $e(k)$ converge para zero com o aumento de $k$, e por possuir baixo tempo de assentamento. Um menor tempo de assentamento poderia ser alcançado utilizado um controlador Proporcional-Integral-Derivativo~(PID). Entretanto, o fator derivativo do PID pode causar oscilações na implementação prática de sistemas com alta variabilidade na saída, como as redes de computadores.
%
\begin{equation}
  u(k) = u(k-1) + (K_p + K_i)e(k) - K_pe(k-1).
 \label{eq:piControlLaw}
\end{equation}
%
%
\begin{equation}
 \frac{U(z)}{E(z)}=\frac{(K_p + K_i)z - K_p}{z-1}= K_p + \frac{K_iz}{z-1}.
 \label{eq:piFcTransf}
\end{equation}

O projeto de um controlador PI consiste na escolha dos parâmetros $K_p$ e $K_i$ da Equação~\ref{eq:piControlLaw} que possibilitem ao sistema atingir  as propriedades desejadas. Nessa primeira análise,
esses valores são calculados manualmente. Mais adiante é introduzido o Regulador Autoajustável, que calcula automaticamente esses parâmetros. Os valores de $K_p$ e $K_i$
influenciam no posicionamento dos pólos e zeros do sistema como mostrado na função de transferência do XTC completo, desconsiderando o Regulador Autoajustável, dada
por $Y(z)/R(z)$ na Equação~\ref{eq:completeSystemTransferFunction}. Essa equação é deduzida no Apêndice~\ref{apendiceProjetoControlador}. Nessa equação, $R(z)$ e $Y(z)$ denotam a transformada Z da vazão de referência e da vazão alcançada, respectivamente.
Os pólos e zeros da função de transferência influenciam as propriedades do sistema como estabilidade, tempo de assentamento e máximo \textit{overshoot}. O primeiro indica se o sistema
converge para um valor fixo em regime permanente, enquanto o segundo indica o tempo que demora para o sistema atingir esse valor. Por fim, o máximo \textit{overshoot}
indica a maior diferença entre a saída do sistema e seu valor em regime permanente.
%
\begin{equation}
  \frac{Y(z)}{R(z)}=\frac{z(K_p + K_i)b - K_pb}{z^2 + z[(K_p + K_i)b - (a + 1)] + (a - K_pb)}.
 \label{eq:completeSystemTransferFunction}
\end{equation}
%
A escolha dos parâmetros do controlador utiliza o método de posicionamento dos pólos, que escolhe os parâmetros do controlador de forma que os pólos do sistema
satisfaçam as propriedades desejadas. Esse método considera apenas a influência dos pólos na 
Equação~\ref{eq:completeSystemTransferFunction}. 
Apesar disso, o posicionamento dos zeros também influencia as propriedades do sistema mudando, por exemplo, o valor de máximo \textit{overshoot}. Para lidar com esse efeito,
foi escolhido um valor baixo de máximo \textit{overshoot}. Utilizando o exemplo da Seção~\ref{sec:modelagem}, no qual $a=0,0915$ e $b=32259$, escolheram-se valores de $K_p$ e $K_i$
de forma a posicionar os pólos para obter tempo de assentamento de 5 amostras e máximo \textit{overshoot} de 8\%. Assim, foram encontrados os valores $K_p=-3,4\times10^{-6}$ e $K_i=22,1\times10^{-6}$.
Os cálculos utilizados para a obtenção de $K_p$ e $K_i$ encontram-se no Apêndice~\ref{apendiceProjetoControlador}.

A partir dos parâmetros encontrados, o sistema de controle foi simulado utilizando a ferramenta Simulink~\cite{simulink} do MATLAB.
Para isso, implementou-se no Simulink o sistema da Figura~\ref{fig:tcm} desconsiderando o Regulador Autoajustável e forçando o sistema 
a possuir condições iniciais nulas.
A entrada do sistema, ou a Vazão de Referência, foi um degrau de $20~Mb/s$ e o período de amostragem utilizado foi de 1 segundo.
A Figura~\ref{fig:simulink} mostra os resultados da simulação.
Na simulação foi encontrado um tempo de assentamento de 10 amostras e 0\% de máximo \textit{overshoot}, que são aceitáveis para o XTC. Com esse resultado, pode ser observada
a diferença entre os resultados esperados e simulados como consequência de não ser considerada a posição dos zeros no método de posicionamento dos pólos.

\begin{figure}
\centering
\includegraphics[width=0.48\textwidth]{./graficos/simulink.eps}
\caption{Simulação do XTC.}
\label{fig:simulink}
\end{figure}

O XTC também utiliza o conceito de zona morta, no qual o sistema apenas atua no \textit{cap} quando o erro excede um limiar. 
Assim, o controlador é desligado quando o erro fica abaixo do limitar, deixando o sistema configurado com o último \textit{cap} utilizado.
Como o sistema atua realizando chamadas ao
Domínio 0, limitar as ações do Controlador reduz essas chamadas. Em sistemas nos quais uma máquina externa realiza essas chamadas, essa preocupação é
relevante pois reduz a troca de mensagens entre a máquina controladora e a máquina com Xen. Consequentemente, o conceito de zona morta também reduz o tráfego
de controle. O limiar de erro escolhido no XTC é de 10\% da vazão de referência.

\subsection{Regulador Autoajustável}
\label{sec:autoajustavel}
O cálculo manual dos parâmetros $K_p$ e $K_i$ do Controlador não é adequado
em sistemas com dinâmica rápida, como é o caso de roteadores, já que isso demandaria o cálculo prévio de diversos valores de parâmetros
que se adequem a cada característica do sistema e que detectem quando usar cada parâmetro. Além disso, mudanças não conhecidas ou não detectadas poderiam causar comportamento
indesejável do sistema. Para isso, o XTC utiliza técnicas de Controle Adaptativo para ajustar o mecanismo de acordo com essas mudanças.
O bloco Regulador Autoajustável é responsável por adaptar o Controlador às características do Sistema Xen. Esse bloco estima periodicamente as constantes $a$ e $b$
da Equação~\ref{eq:xenSystemTransferFunction} baseado na observação da decisão $u(k)$ do Controlador e na saída $y(k)$ do Sistema Xen. Para isso, utiliza o algoritmo
de projeção por gradiente~\cite{ioannou2006adaptive} dado pela Equação~\ref{eq:gradientAlg}, na qual $\alpha=0,001$ e $c=0,0001$. Com base nas constantes que caracterizam o sistema, o Regulador Autoajustável calcula
automaticamente novos valores de $K_p$ e $K_i$ 
pelo método de posicionamento dos pólos, como realizado na Seção~\ref{sec:projetoControlador}. Assim, o Regulador Autoajustável visa
fixar os pólos do sistema em uma posição, preservando as características desejadas.
Os pólos fixados pelo Regulador Autoajustável são os mesmos da Seção~\ref{sec:projetoControlador}, calculados no Apêndice~\ref{apendiceProjetoControlador}. Os valores  de $\alpha$ e $c$ foram escolhidos empiricamente, através de experimentos com o sistema.
%
\begin{equation}
\label{eq:gradientAlg}
\theta(k) = \theta(k-1) + \alpha\epsilon(k)\phi(k),
\end{equation}
%
\noindent
onde $\theta(k)=[b,a]^{T}$, $\nonumber \epsilon(k) = \frac{y(k) - \theta^{T}(k-1)\phi(k)}{c + \phi^{T}(k)\phi(k)}$ e $\phi(k)=[u(k-1),y(k-1)]^{T}$.
