[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04 05

Network Management Research Group                               M-S. Kim
Internet-Draft                                                 Y-G. Hong
Intended status: Informational                                      ETRI
Expires: January 4, 2018                                        Y-H. Han
                                                                KoreaTec
                                                            July 3, 2017


  Intelligent Management using Collaborative Reinforcement Multi-agent
                                 System
                          draft-kim-nmrg-rl-00

Abstract

   This document describes an intelligent reinforcement learning agent
   system to autonomously manage agent path-planning over a
   communication network.  The main centralized node called by the
   global environment should not only manage all agents workflow in a
   hybrid peer-to-peer networking architecture and, but transfer and
   share information in distributed nodes.  All agents in distributed
   nodes are able to be provided with a cumulative reward for each
   action that a given agent takes with respect to an optimized
   knowledge based on a to-be-learned policy over the learning process.
   A reward from the global environment is reflected to the next
   optimized action for autonomous path management in distributed
   networking nodes.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 4, 2018.








Kim, et al.              Expires January 4, 2018                [Page 1]


Internet-Draft                 Network RL                      July 2017


Copyright Notice

   Copyright (c) 2017 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Conventions and Terminology . . . . . . . . . . . . . . . . .   3
   3.  Motivation  . . . . . . . . . . . . . . . . . . . . . . . . .   3
     3.1.  General Motivation for Reinforcement Learning . . . . . .   3
     3.2.  Reinforcement Learning in networks  . . . . . . . . . . .   4
     3.3.  Motivation in our work  . . . . . . . . . . . . . . . . .   4
   4.  Related Works . . . . . . . . . . . . . . . . . . . . . . . .   4
     4.1.  Autonomous Driving System . . . . . . . . . . . . . . . .   4
     4.2.  Game Theory . . . . . . . . . . . . . . . . . . . . . . .   4
     4.3.  Wireless Sensor Network (WSN) . . . . . . . . . . . . . .   5
     4.4.  Routing Enhancement . . . . . . . . . . . . . . . . . . .   5
   5.  Multi-agent Reinforcement Learning Technologies . . . . . . .   5
     5.1.  Reinforcement Learning  . . . . . . . . . . . . . . . . .   5
     5.2.  Policy using Distance and Frequency . . . . . . . . . . .   5
     5.3.  Distributed Computing Node  . . . . . . . . . . . . . . .   6
     5.4.  Agent Sharing Information . . . . . . . . . . . . . . . .   6
     5.5.  Sub-goal Selection  . . . . . . . . . . . . . . . . . . .   6
   6.  Proposed Architecture for Reinforcement Learning  . . . . . .   6
   7.  Use case of Multi-agent Reinforcement Learning  . . . . . . .   8
     7.1.  Distributed Multi-agent Reinforcement Learning: Sharing
           Information Technique . . . . . . . . . . . . . . . . . .   8
     7.2.  Use case of Shortest Path-planning via sub-goal selection   9
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
   9.  Security Considerations . . . . . . . . . . . . . . . . . . .  10
   10. Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  10
   11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     11.1.  Normative References . . . . . . . . . . . . . . . . . .  10
     11.2.  Informative References . . . . . . . . . . . . . . . . .  10
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  12





Kim, et al.              Expires January 4, 2018                [Page 2]


Internet-Draft                 Network RL                      July 2017


1.  Introduction

   In large infrastructures such as transportation, health and energy
   systems, collaborative monitoring system is needed, where there are
   special needs for intelligent distributed networking systems with
   learning schemes.  Agent Reinforcement Learning (RL) for autonomous
   network management, in general, is one of the challengeable methods
   in a dynamic complex cluttered environment over a network.  The goal
   for autonomous network management using RL is self-management to
   manage optimized agent work-flow without minimal human dependency by
   learning process [RFC7575].  The system is needed by the development
   of computational multi-agents learning process in large distributed
   networking nodes, where the agents have limited and incomplete
   knowledge, and they only access local information in distributed
   networking nodes.

   Reinforcement Learning can become an effective technique to transfer
   and share information among agents, as it does not require a priori
   knowledge of the agent behavior or environment to accomplish its
   tasks [Megherbi].  Such a knowledge is usually acquired and learned
   automatically and autonomously by trial and error.

   Reinforcement Learning is Machine Learning techniques that will be
   adapted to the various networking environments for automatic
   networks[I-D.jiang-nmlrg-network-machine-learning].  Thus, this
   document provides motivation, learning technique, and use case for
   network machine learning.

2.  Conventions and Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

3.  Motivation

3.1.  General Motivation for Reinforcement Learning

   Reinforcement Learning is a system capable of autonomous acquirement
   and incorporation of knowledge.  It can continuously self-improve
   learning process with experience and attempts to maximize cumulative
   reward to manage an optimized learning knowledge by multi-agents-
   based monitoring systems[Teiralbar].  The maximized reward can be
   increasingly optimizing of learning speed for agent autonomous
   learning process.






Kim, et al.              Expires January 4, 2018                [Page 3]


Internet-Draft                 Network RL                      July 2017


3.2.  Reinforcement Learning in networks

   Reinforcement learning is an emerging technology in terms of
   monitoring and managing network system to achieve fair resource
   allocation for nodes within the wire or wireless mesh setting.
   Monitoring parameters of the network and adjusts based on the network
   dynamics can demonstrate to improve fairness in wireless environment
   Infrastructures and Resources [Nasim].  The fundamental goal for
   Reinforcement Learning is self-management, which is comprised of a
   couple of properties such as self-healing (adaptive function in the
   environment and heal problems automatically) and self-optimizing
   (function for automatically determine ways to optimize their behavior
   against a set of well-defined goals) [RFC7575].

3.3.  Motivation in our work

   There are many different networking management issues such as
   connectivity, traffic management, fast internet without latency and
   etc.  We expect that ml-based mechanism such as reinforcement
   learning will provide solutions of networking issues with multiple
   cases against human operating capacities even if it is a
   challengeable area due to a multitude of reasons such as large state
   space search, complexity in giving reward, difficulty in agent action
   selection, and difficulty in sharing and merging learned information
   among the agents in a distributed memory node to be transferred over
   a communication network [Minsuk].

4.  Related Works

4.1.  Autonomous Driving System

   Autonomous vehicle is capable of self-management for automotive
   driving without human supervision depending on optimized trust region
   policy by reinforcement learning that enables learning of more
   complex and special network management environment.  Such a vehicle
   provides a comfortable user experience safely and reliably on
   interactive communication network [April] [Markus].

4.2.  Game Theory

   The adaptive multi-agent system, which is combined with complexities
   from interacting game player, has developed in a field of
   reinforcement learning.  In the early game theory, the
   interdisciplinary work was only focused on competitive games, but
   Reinforcement Learning has developed into a general framework for
   analyzing strategic interaction and has been attracted field as
   diverse as psychology, economics and biology [Ann].




Kim, et al.              Expires January 4, 2018                [Page 4]


Internet-Draft                 Network RL                      July 2017


   AlphaGo is also one of the game theories using reinforcement
   learning, developed by Google DeepMind.  Even though it began as a
   small learning computational program with some simple actions, it has
   now trained on a policy and value networks of thirty million actions,
   states and rewards for optimal management using learning process.

4.3.  Wireless Sensor Network (WSN)

   Wireless sensor network (WSN) consists of a large number of sensors
   and sink nodes for monitoring systems to manage event parameters such
   as temperature, humidity, air conditioning, etc.  Reinforcement
   learning in WSNs has been applied in a wide range of schemes such as
   cooperative communication, routing and rate control.  The sensors and
   sink nodes are able to observe and carry out optimal actions on their
   respective operating environment for network and application
   performance enhancements [Kok-Lim].

4.4.  Routing Enhancement

   Reinforcement Learning is used to enhance multicast routing protocol
   in wireless ad hoc networks, where each node has different
   capability.  Routers in the multicast routing protocol are determined
   to discover optimal route with a predicted reward, and then the
   routers create the optimal path with multicast transmissions to
   reduce the overhead in Reinforcement Learning[Kok-Lim].

5.  Multi-agent Reinforcement Learning Technologies

5.1.  Reinforcement Learning

   Agent reinforcement Learning is ml-based unsupervised algorithms
   based on an agent learning process.  Reinforcement Learning is
   normally used with a reward from centralized node (the global
   environment), and capable of autonomous acquirement and incorporation
   of knowledge.  It is continuously self-improving and becoming more
   efficient as the learning process from an agent experience to
   optimize management performance for autonomous learning
   process.[Sutton][Madera]

5.2.  Policy using Distance and Frequency

   Distance and Frequency algorithm uses the state occurrence frequency
   in addition to the distance to goal.  It avoids deadlocks and lets
   the agent escape the Dead, and it was derived to enhance agent
   optimal learning speed.  Distance-and-Frequency is based on more
   levels of agent visibility to enhance learning algorithm by an
   additional way that uses the state occurrence frequency.[Al-Dayaa]




Kim, et al.              Expires January 4, 2018                [Page 5]


Internet-Draft                 Network RL                      July 2017


5.3.  Distributed Computing Node

   Autonomous multi-agent learning process for network management
   environment is related to transfer optimized knowledge between agents
   on a given local node or distributed memory nodes over a
   communication network.

5.4.  Agent Sharing Information

   This is a technique how agents can share information for optimal
   learning process.  The quality of agent decision making often depends
   on the willingness of agents to share a given learning information
   collected by agent learning process.  Sharing Information means that
   an agent would share and communicate the knowledge learned and
   acquired with or to other agents using reinforcement learning.

   Agents normally have limited resources and incomplete knowledge
   during learning exploration.  For that reason, the agents should take
   actions and transfer the states to the global environment under
   reinforcement learning, then it would share the information with
   other agents, where all agents explore to reach their destination via
   a distributed reinforcement reward-based learning method on the
   existing local distributed memory nodes.

   MPI (Message Passing Interface) is used for communication way.  Even
   if the agents do not share the capabilities and resources to monitor
   an entire given large terrain environment, they are able to share the
   needed information to manage collaborative learning process for
   optimized management in distributed networking
   nodes.[Chowdappa][Minsuk]

5.5.  Sub-goal Selection

   A new technical method for agent sub-goal selection in distributed
   nodes is introduced to reduce the agent initial random exploration
   with a given selected sub-goal.

   [TBD]

6.  Proposed Architecture for Reinforcement Learning

   The architecture using Reinforcement Learning describes a
   collaborative multi-agent-based system in distributed environments as
   shown in figure 1, where the architecture is combined with a hybrid
   architecture making use of both a master and slave architecture and a
   peer-to-peer.  The centralized node(global environment), assigns each
   slave computing node a portion of the distributed terrain and an
   initial number of agents.



Kim, et al.              Expires January 4, 2018                [Page 6]


Internet-Draft                 Network RL                      July 2017


       +-------------+                           +-----------------+
       |             |<......>| node 1 |<.......>|    terrain 1    |
       |             |                           +-----------------+
       | Global env. |
       |  (node 0)   |                           +-----------------+
       |             |<......>| node 2 |<.......>|    terrain 2    |
       +-------------+                           +-----------------+

        Figure 1: Hybrid P2P and Master/Slave Architecture Overview

   Reinforcement Learning actions involve interacting with a given
   environment, so the environment provides an agent learning process
   with the elements as followings:

   o  Agent actions, states and cumulative rewards

   o  One or more obstacles, and goals

   o  Initially, random exploration in a given node

   o  Next, optimal explorations under reinforcement learning

   Additionally, agent actions with states toward its goal as below:

   o  Agent continuously actions to avoid an obstacle based on its
      policy and move to one or more available positions until it
      reaches its goal(s)

   o  After an agent reaches its destination, it can use the information
      collected by initial random learning process to next learning
      process for optimal management

   o  Agent learning process is optimized in the following phase and
      exploratory learning trials

   In shown as Figure2, we illustrate the fundamental architecture for
   relationship of an action, state and reward, and each agent explores
   to reach its destination(s) under reinforcement learning.  The agent
   does an action that leads to a reward from achieving an optimal path
   toward its goal.  Our works will be extended depending on the
   architecture.










Kim, et al.              Expires January 4, 2018                [Page 7]


Internet-Draft                 Network RL                      July 2017


                                    +---------------------+
        ....state and reward........+ Global Environment +|<............
        .                           +---------------------+            .
 +------+------+                                                       .
 | Multi-agent |                                                       .
 +------+------+                    +---------------+                  .
        ............action.........>+  Destiantion  +...................
                                    +---------------+

                      Figure 2: RL work-flow Overview

7.  Use case of Multi-agent Reinforcement Learning

7.1.  Distributed Multi-agent Reinforcement Learning: Sharing
      Information Technique

   In this section, we deal with case of a collaborative distributed
   multi-agent, where each agent has same or different individual
   destination in a distributed environment.  Since sharing information
   scheme among the agents is problematic one, we need to expand on the
   work described by solving the challenging cases.

   Basically, the main proposed algorithm is presented by distributed
   multi-agent reinforcement learning as below:

   +-------------------------------------------------------------------+
   | Proposed Algorithm                                                |
   +-------------------------------------------------------------------+
   | (1) Let Ni denote the number of node (i= 1, 2, 3 ...)             |
   |                                                                   |
   | (2) Let Aj denote the number of agent                             |
   |                                                                   |
   | (3) Let Dk denote the number of destination                       |
   |                                                                   |
   | (4) Place initial number of agents Aj, in random position (Xm,    |
   | Yn)                                                               |
   |                                                                   |
   | (5) Every Aj in Ni                                                |
   |                                                                   |
   | -----> (a) Do initial exploration (random) to corresponding Dk    |
   |                                                                   |
   | -----> (b) Do exploration (using RL) for Tx denote the number of  |
   | trial                                                             |
   +-------------------------------------------------------------------+

                        Table 1: Proposed Algorithm





Kim, et al.              Expires January 4, 2018                [Page 8]


Internet-Draft                 Network RL                      July 2017


   +-------------------------------------------------------------------+
   | Random Trial                                                      |
   +-------------------------------------------------------------------+
   | (1) Let Si denote the the current state                           |
   |                                                                   |
   | (2) Relinquish Si so that the other agent can occupy the position |
   |                                                                   |
   | (3) Assign the agent new position                                 |
   |                                                                   |
   | (4) Update the current state Si -> Si+1                           |
   +-------------------------------------------------------------------+

                           Table 2: Random Trial

         +-------------------------------------------------------+
         | Optimal Trial                                         |
         +-------------------------------------------------------+
         | (1) Let Si denote the the current state               |
         |                                                       |
         | (2) Let ACj denote an action                          |
         |                                                       |
         | (3) Let DRm denote discount reward                    |
         |                                                       |
         | (4) Choose ACj <- Policy(Si, ACj)                     |
         |                                                       |
         | (5) Move an available posiion                         |
         |                                                       |
         | (6) Update learning process in the global environment |
         |                                                       |
         | (7) Update the current state Si < Si+1                |
         +-------------------------------------------------------+

                          Table 3: Optimal Trial

   Multi-agent reinforcement learning in distributed nodes can improve
   the overall system performance to transfer or share information from
   one node to another node in following cases; expanded complexity in
   RL technique with various experimental factors and conditions,
   analyzing multi-agent sharing information for agent learning process.

7.2.  Use case of Shortest Path-planning via sub-goal selection

   Sub-goal selection is a scheme of a distributed multi-agent RL
   technique based on selected intermediary agent sub-goal(s) with the
   aim of reducing the initial random trial.  The scheme is to improve
   the multi-agent system performance with asynchronously triggered
   exploratory phase(s) with selected agent sub-goal(s) for autonomous
   network management.



Kim, et al.              Expires January 4, 2018                [Page 9]


Internet-Draft                 Network RL                      July 2017


   [TBD]

8.  IANA Considerations

   There are no IANA considerations related to this document.

9.  Security Considerations

   [TBD]

10.  Acknowledgements

   David Meyerm, who chief scientist and VP in Brocade, has provided
   significant comment and feedback for the draft.

11.  References

11.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC7575]  Behringer, M., Pritikin, M., Bjarnason, S., Clemm, A.,
              Carpenter, B., Jiang, S., and L. Ciavaglia, "Autonomic
              Networking: Definitions and Design Goals", RFC 7575,
              DOI 10.17487/RFC7575, June 2015,
              <http://www.rfc-editor.org/info/rfc7575>.

11.2.  Informative References

   [I-D.jiang-nmlrg-network-machine-learning]
              Jiang, S., "Network Machine Learning", ID draft-jiang-
              nmlrg-network-machine-learning-02, October 2016.

   [Megherbi]
              "Megherbi, D. B., Kim, Minsuk, Madera, Manual., "A Study
              of Collaborative Distributed Multi-Goal and Multi-agent
              based Systems for Large Critical Key Infrastructures and
              Resources (CKIR) Dynamic Monitoring and Surveillance",
              IEEE International Conference on Technologies for Homeland
              Security", 2013.








Kim, et al.              Expires January 4, 2018               [Page 10]


Internet-Draft                 Network RL                      July 2017


   [Teiralbar]
              "Megherbi, D. B., Teiralbar, A. Boulenouar, J., "A Time-
              varying Environment Machine Learning Technique for
              Autonomous Agent Shortest Path Planning.", Proceedings of
              SPIE International Conference on Signal and Image
              Processing, Orlando, Florida", 2001.

   [Nasim]    "Nasim ArianpooEmail, Victor C.M. Leung, "How network
              monitoring and reinforcement learning can improve tcp
              fairness in wireless multi-hop networks", EURASIP Journal
              on Wireless Communications and Networking", 2016.

   [Minsuk]   "Dalila B. Megherbi and Minsuk Kim, "A Hybrid P2P and
              Master-Slave Cooperative Distributed Multi-Agent
              Reinforcement Learning System with Asynchronously
              Triggered Exploratory Trials and Clutter-index-based
              Selected Sub goals", IEEE CIG Conference", 2016.

   [April]    "April Yu, Raphael Palefsky-Smith, Rishi Bedi, "Deep
              Reinforcement Learning for Simulated Autonomous Vehicle
              Control", Stanford University", 2016.

   [Markus]   "Markus Kuderer, Shilpa Gulati, Wolfram Burgard, "Learning
              Driving Styles for Autonomous Vehicles from
              Demonstration", Robotics and Automation (ICRA)", 2015.

   [Ann]      "Ann Nowe, Peter Vrancx, Yann De Hauwere, "Game Theory and
              Multi-agent Reinforcement Learning", In book:
              Reinforcement Learning: State of the Art, Edition:
              Adaptation, Learning, and Optimization Volume 12", 2012.

   [Kok-Lim]  "Kok-Lim Alvin Yau, Hock Guan Goh, David Chieng, Kae
              Hsiang Kwong, "Application of reinforcement learning to
              wireless sensor networks: models and algorithms",
              Published in Journal Computing archive Volume 97 Issue 11,
              Pages 1045-1075", November 2015.

   [Sutton]   "Sutton, R. S., Barto, A. G., "Reinforcement Learning: an
              Introduction", MIT Press", 1998.

   [Madera]   "Madera, M., Megherbi, D. B., "An Interconnected Dynamical
              System Composed of Dynamics-based Reinforcement Learning
              Agents in a Distributed Environment: A Case Study",
              Proceedings IEEE International Conference on Computational
              Intelligence for Measurement Systems and Applications,
              Italy", 2012.





Kim, et al.              Expires January 4, 2018               [Page 11]


Internet-Draft                 Network RL                      July 2017


   [Al-Dayaa]
              "Al-Dayaa, H. S., Megherbi, D. B., "Towards A Multiple-
              Lookahead-Levels Reinforcement-Learning Technique and Its
              Implementation in Integrated Circuits", Journal of
              Artificial Intelligence, Journal of Supercomputing. Vol.
              62, issue 1, pp. 588-61", 2012.

   [Chowdappa]
              "Chowdappa, Aswini., Skjellum, Anthony., Doss, Nathan,
              "Thread-Safe Message Passing with P4 and MPI", Technical
              Report TR-CS-941025, Computer Science Department and NSF
              Engineering Research Center, Mississippi State
              University", 1994.

Authors' Addresses

   Min-Suk Kim
   ETRI
   161 Gajeong-Dong Yuseung-Gu
   Daejeon  305-700
   Korea

   Phone: +82 42 860 5930
   Email: mskim16@etri.re.kr


   Yong-Geun Hong
   ETRI
   161 Gajeong-Dong Yuseung-Gu
   Daejeon  305-700
   Korea

   Phone: +82 42 860 6557
   Email: yghong@etri.re.kr


   Youn-Hee Han
   KoreaTec
   Byeongcheon-myeon Gajeon-ri, Dongnam-gu
   Choenan-si, Chungcheongnam-do
   330-708
   Korea

   Phone: +82 41 560 1486
   Email: yhhan@koreatec.ac.kr






Kim, et al.              Expires January 4, 2018               [Page 12]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/