[pt] Esta dissertação investiga a aplicação dos métodos de
Reinforcement Learning na descoberta de rotas ótimas em uma
rede de comunicação. Uma rede de comunicação real possui um
comportamento dinâmico, mudando seu estado com o tempo. Os
algoritmos de roteamento devem, portanto, oferecer rapidez
na resposta às mudanças do estado da rede. O objetivo do
trabalho é avaliar a aplicação de técnicas de Reinforcement
Learning (RL) como base de algoritmos adaptativos de
roteamento de pacotes. O problema de roteamento de pacotes
sob a visão de RL consiste na definição de cada nó na rede
como um agente RL, sendo que este agente deve definir ações
de forma a minimizar uma função objetivo que pode ser o
tempo de roteamento dos pacotes. Um dos objetivos do RL é
precisamente aprender a tomar as ações que minimizem uma
função. O trabalho consistiu de 4 etapas principais: um
estudo sobre a área de Reinforcement Learning (RL); um
estudo sobre a área de redes de comunicação e roteamento de
pacotes; a modelagem do problema de roteamento como um
sistema RL e implementação de diferentes métodos de RL para
obter algoritmos de roteamento; e o estudo de casos.
O estudo na área de Reinforcement Learning abrangeu desde
as definições mais fundamentais: suas características, os
elementos de um sistema RL e modelagem do ambiente como um
Processo de Decisão de Markov, até os métodos básicos de
solução: Programação Dinâmica, método de Monte Carlo, e o
método de Diferenças Temporais. Neste último método, foram
considerados dois algoritmos específicos: TD e Q-Learning.
Em seguida, foi avaliado o parâmetro Eligibility Traces
como uma alternativa para apressar o processo de
aprendizado, obtendo o TD(lambda) e o Q(lambda)
respectivamente. O estudo sobre Redes de Comunicação e
Roteamento de pacotes envolveu os conceitos básicos de
redes de comunicações, comutação por pacotes, a questão do
roteamento de pacotes e os algoritmos existentes
adaptativos e não adaptativos, que são utilizados na
atualidade. Nas redes de comunicação, definidas como um
conjunto de nós ligados através de enlaces de comunicação,
para se enviar uma mensagem de um nó a outro, geralmente, a
mensagem é quebrada em pedaços, chamados pacotes, e
enviados através de outros nós, até chegar ao destino.
Deste modo surge o problema de escolher os nós que levem o
pacote o mais rápido possível até o nó destino. Os
algoritmos analisados foram: Shortest Path Routing que
procura os caminhos com menor número de nós
intermediários, não sendo sensível às mudanças na carga nem
na topologia da rede; Weighted Shortest Path Routing, que
oferece um melhor desempenho a partir de uma visão global
do estado da rede, que nem sempre é fácil de obter em redes
reais e o algoritmo de Bellman-Ford, baseado em decisões de
roteamento locais e atualizações periódicas, com algumas
limitações para obter políticas em altas cargas. Este
último é um dos algoritmos mais utilizados na atualidade,
sendo base de muitos protocolos de roteamento existentes.
A modelagem do problema de roteamento como um sistema RL
foi inspirada por uma característica na definição de um
sistema RL: um agente que interage com o ambiente e aprende
a atingir um objetivo. Assim, a modelagem dos algoritmos
tem como objetivo aprender a descobrir as rotas que
minimizem o tempo de roteamento de pacotes desde uma origem
até um dado destino. A avaliação de uma rota escolhida não
pode ser obtida antes que o pacote alcance o seu destino
final. Este fato faz com que os processos de aprendizado
supervisionado tenham dificuldade de se aplicar a esse
problema. Por outro lado, o Reinforcement Learning não
necessita de um par entrada-resposta para fazer o
aprendizado, permitindo-lhe abordar o problema com relativa
facilidade. Na modelagem efetuada, cada nó na rede se
comporta como um agente de RL que age na própria rede, a
qual é o ambiente. A informação das rotas é armazenada nas
funções de valor existentes em todos os nós da rede para / [en] This dissertation investigates the application of
Reinforcement Learning methods to the discovery of
optimal routes in communication networks. Any current
communication network displays dynamic behavior,
changing its states over time. Therefore, the routing
algorithms must react swiftly to changes in the network
status. The objective of this work is to evaluate the
application of some Reinforcement Learning techniques to
define adaptive packet routing algorithms. The packet
routing problem under the RL vision consists in the
definition of each node on network as an RL agent. Thus,
each agent must take actions in order to minimize an
objective function such as end to end packet routing delay.
One main objective of the RL is precisely learning to
take the actions that minimize a given function.
This thesis is consists of 4 main parts: first, a study of
Reinforcement Learning (RL); a study of the
communication networks and packet routing; the routing
problem model as a RL system and the implementation
of several RL methods in order to obtain some routing
algorithms; e finally, the case study.
The study of Reinforcement Learning extends from the more
basic definitions, Reinforcement Learning
features, elements of a RL system and environment modeling
as a Markovian Decision Process, to the basic
methods of solution: Dynamic Programming, Monte Carlo
methods and Temporal Differences methods. In this
last case, two specific algorithms have been considered: TD
and Q-Learning, and, finally, the Eligibility Traces
are evaluated as a useful tool that permits us to
accelerate the learning process leading to the TD(lambda)
and the Q(lambda) routing algorithms. The study on
communication networks and packet routing
involves the foundations of communication networks, packet
switching, the packet routing problem, and adaptive and non-
adaptive routing algorithms used
at the present time. Communication networks are defined as
a set of nodes connected through communication
links. In order to send a message from a source node to a
destination node usually the message is broken into
segments called packets, and these are sent through other
nodes until arriving at the destination. In this way the
problem appears to choose the path which takes the shortest
possible time for the packet to reach the destination
node. The following algorithms have been analyzed: Shortest
Path Routing that looks for paths with minimal
hop number, not being sensible to the changes of load level
and network topology; Weighted Shortest Path
Routing that offers better performance from a global vision
of the state of the network, which is not always easy
to get in real networks; on the other hand, the Bellman-
Ford routing algorithm was studied, this is based on local
routing decisions and periodic updates, with some
limitations to obtain policies in high load conditions.
Bellman-Ford
is one of the algorithms most used at the present time,
being the basis for many existing routing protocols.
The modeling of the routing problem as a RL system was
inspired by one of the main features of the
definition of an RL system: an agent who interacts with the
environment and learns to reach an objective;
therefore, the modeling of the routing algorithms has as
its objective to learn to discover the paths that minimize
packet routing time from an origin to an destination. The
evaluation of a chosen route cannot be completed
before the package reaches its final destination. This fact
implies that supervised learning cannot be applied to
the routing problem. On the other hand, Reinforcement
Learning does not need a input-output pair for the
learning process, allowing it to approach the problem with
relative ease. In the modeling, each network node is
viewed as a RL agent that acts in the same network; the
network is the environment. The routing information is
stored in the existing value functions in all nodes in the
network, for each node and all another destination node / [es] Esta disertación investiga la aplicación de los métodos de
Reinforcement Learning en la determinación de rutas óptimas
en una red de comunicación. Una red de comunicación real
posee un comportamiento dinámico, donde su estado varia en
el tiempo. Los algoritmos de ruta óptima deben, por lo
tanto, ofrecer rapidez en la respuesta a las variaciones
del estado de la red. El objetivo de este trabajo es
evaluar la aplicación de técnicas de Reinforcement Learning
(RL) como base de algoritmos adaptativos de problemas de
ruteamiento en redes. Este problema consiste en la
definición de cada nodo de la red como un agente RL. Este
agente debe definir acciones de modo a minimizar una
función objetivo que puede ser el tiempo de ruteamiento.
El trabajo consta de 4 etapas principais: un estudio sobre
el área de Reinforcement Learning (RL); un estudio sobre
redes de comunicación y problema de ruteamiento; el modelo
de ruta óptima como un sistema RL y la implementación de
diferentes métodos de RL para obtener algoritmos de ruta
óptima; y un estudio de casos.
El estudio en el área de Reinforcement Learning va desde
las definiciones fundamentales: características, elementos
de un sistema RL y modelaje del ambiente como un Proceso de
Decisión de Markov, hasta los métodos básicos de solución:
Programación Dinámica, método de Monte Carlo, y método de
Diferencias Temporales. En este último método, fueron
considerados dos algoritmos específicos: TD e Q-Learning.
A seguir, fue evaluado el parámetro Eligibility Traces como
una alternativa para agilizar el proceso de aprendizaje,
obteniendo el TD(lambda) y el Q(lambda) respectivamente.
El estudio sobre Redes de Comunicación y Problema de
Transporte incluye los conceptos básicos de redes de
comunicaciones, la cuestión de la ruta óptima y los
algoritmos adaptativos y no adaptativos existentes, que se
utilizan actualmente. Los algoritmos analizados fueron:
Shortest Path Routing, que busca los caminos con menor
número de nodos intermedios, no siendo sensible a
variaciones en la carga ni en la topología de la red;
Weighted Shortest Path Routing, que ofrece un mejor
desempeño a partir de una visión global del estado de la
red, que no siempre es fácil de obtener en redes reales; y
el algoritmo de Bellman-Ford, que tiene como base
decisiones de rutas locales y actualizaciones periódicas,
con algunas limitaciones para obtener políticas en altas
cargas. Este último es uno de los algoritmos más utilizados
en la actualidad, siendo base de muchos protocolos de
trazado de ruta existentes. La solución para modelar el
problema de ruteamiento como un
sistema RL fue inspirada por una característica en la
definición de un sistema RL: un agente que interactúa con
el ambiente y aprende a alcanzar un objetivo. Así, el
modelo tiene como objetivo aprender a determinar las rutas
que minimizen el timpo desde el origen hasta un destino
dado. La evaluación de uma ruta seleccionada no puede ser
obtenida antes que el paquete alcance su destino final.
Esto hace que los procesos de aprendizaje supervisionado
tengan dificultades para ser aplicados a este problema. Por
otro lado, Reinforcement Learning no necesita de un par
entrada-salida para el aprendizaje, permitiendo así,
abordar el problema con relativa facilidad. En el modelo
establecido, cada nodo en la red se comporta como un agente
de RL que actúa en la propria red.
La información de las rutas se almacena en las funciones de
valor existentes en todos los nodos de la red para cada
nodo destino diferente. Esta información contiene un valor
estimado del tiempo requerido para un paquete para llegar
hasta el nodo destino. La actualización de esos valores se
realiza durante la transición del paquete hasta el vecino
seleccionado. En este trabajo se implementaron varios
algoritmos de ruta óptima. Cada uno de los algoritmos
aplica características de las técnicas en Reinforcement
Learning: o Q(lambda)-Routing, y el TD-Routing. En el
estudio d
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:1348 |
| Date | 13 March 2001 |
| Creators | YVAN JESUS TUPAC VALDIVIA |
| Contributors | MARCO AURELIO CAVALCANTI PACHECO, MARCO AURELIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0039 seconds