Internet DRAFT - draft-xwwang-sonnetworkmodel

draft-xwwang-sonnetworkmodel






Network Working Group                                      XingWei. Wang
Internet-Draft                                             XiuShuang. Yi
Intended status: Standards Track                                Yu. Wang
Expires: May 21, 2010                                         Ming. Dong
                                                             Qiang. Chen
                                                                     NEU
                                                       November 17, 2009


                     Self-organizing network model
                  draft-xwwang-sonnetworkmodel-02.txt

Abstract

   In this paper, a swarm intelligence based self-organizing network
   model was introduced to network providers.  The problems of the
   existing network as well as the characteristics of the NGI (Next
   Generation Internet) were described to illustrate the motivation of
   the proposed self-organizing network model.  A network architecture
   model based on swarm intelligence was introduced, the used technical
   terms was defined.  The network parameters, network behaviors and
   node stability under the proposed model were described.  Especially,
   some important QoS routing elements under the proposed model, such as
   the user QoS routing requirements, link satisfaction degree, utility
   computation, unicast path and multicast tree evaluation, mathematical
   model of QoS route optimization and small-world behaviors, were
   introduced.

Status of this Memo

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

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.



Wang, et al.              Expires May 21, 2010                  [Page 1]

Internet-Draft        Self-organizing network model        November 2009


   This Internet-Draft will expire on May 21, 2010.

Copyright Notice

   Copyright (c) 2009 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 BSD License.



































Wang, et al.              Expires May 21, 2010                  [Page 2]

Internet-Draft        Self-organizing network model        November 2009


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Requirements . . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Term . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  6
   4.  Motives and existent problems  . . . . . . . . . . . . . . . .  8
   5.  Related issues . . . . . . . . . . . . . . . . . . . . . . . . 10
     5.1.  Swarm Intelligence . . . . . . . . . . . . . . . . . . . . 10
     5.2.  QoS Routing  . . . . . . . . . . . . . . . . . . . . . . . 12
   6.  Self-organizing Network Design Paradigm  . . . . . . . . . . . 15
     6.1.  DESIGN LOCAL BEHAVIOR RULES THAT ACHIEVE GLOBAL
           PROPERTIES . . . . . . . . . . . . . . . . . . . . . . . . 15
     6.2.  EXPLOIT IMPLICIT COORDINATION  . . . . . . . . . . . . . . 15
     6.3.  MINIMIZE LONG-LIVED STATE INFORMATION  . . . . . . . . . . 15
     6.4.  DESIGN PROTOCOLS THAT ADAPT TO CHANGES . . . . . . . . . . 15
   7.  Network Model  . . . . . . . . . . . . . . . . . . . . . . . . 17
     7.1.  Network Parameters . . . . . . . . . . . . . . . . . . . . 17
     7.2.  Network Self-organization Behavior Design  . . . . . . . . 17
     7.3.  Node Stability Degree  . . . . . . . . . . . . . . . . . . 20
   8.  Routing Request  . . . . . . . . . . . . . . . . . . . . . . . 23
     8.1.  User QoS Unicast Routing Request . . . . . . . . . . . . . 23
     8.2.  User QoS Multicast Routing Request . . . . . . . . . . . . 23
   9.  Link QoS Evaluation  . . . . . . . . . . . . . . . . . . . . . 24
     9.1.  Link Parameter Membership Degree . . . . . . . . . . . . . 24
     9.2.  QoS Satisfaction Degree  . . . . . . . . . . . . . . . . . 25
     9.3.  Link QoS Evaluation  . . . . . . . . . . . . . . . . . . . 27
   10. Utility Calculation and Gaming Analysis  . . . . . . . . . . . 28
     10.1. Cost and Price . . . . . . . . . . . . . . . . . . . . . . 28
     10.2. Utility  . . . . . . . . . . . . . . . . . . . . . . . . . 30
     10.3. Gaming . . . . . . . . . . . . . . . . . . . . . . . . . . 30
   11. Unicast Path and Multicast Tree Evaluation . . . . . . . . . . 32
   12. Mathematical Model . . . . . . . . . . . . . . . . . . . . . . 33
     12.1. Unicast Mathematical Model . . . . . . . . . . . . . . . . 33
     12.2. Multicast Mathematics Model  . . . . . . . . . . . . . . . 33
   13. Small World Behavior . . . . . . . . . . . . . . . . . . . . . 35
   14. Route Strategies . . . . . . . . . . . . . . . . . . . . . . . 39
   15. Security Considerations  . . . . . . . . . . . . . . . . . . . 40
   16. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 41
   17. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 42
   Appendix A.  References  . . . . . . . . . . . . . . . . . . . . . 43
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 45










Wang, et al.              Expires May 21, 2010                  [Page 3]

Internet-Draft        Self-organizing network model        November 2009


1.  Introduction

   In this paper, a swarm intelligence based self-organizing network
   model was introduced to network providers.  The problems of the
   existing network as well as the characteristics of the NGI (Next
   Generation Internet) were described to illustrate the motivation of
   the proposed self-organizing network model.  A network architecture
   model based on swarm intelligence was introduced, the used technical
   terms was defined.  The network parameters, network behaviors and
   node stability under the proposed model were described.  Especially,
   some important QoS routing elements under the proposed model, such as
   the user QoS routing requirements, link satisfaction degree, utility
   computation, unicast path and multicast tree evaluation, mathematical
   model of QoS route optimization and small-world behaviors, were
   introduced.




































Wang, et al.              Expires May 21, 2010                  [Page 4]

Internet-Draft        Self-organizing network model        November 2009


2.  Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
   NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
   thisdocument are to be interpreted as described in RFC 2119 .














































Wang, et al.              Expires May 21, 2010                  [Page 5]

Internet-Draft        Self-organizing network model        November 2009


3.  Term

   The used terms in this document are defined as follows.  Pay
   attention: because they may have other definitions out of the self-
   organizing network, these terms only have the defined specific
   meaning in this document, thus not universal.

   Self-organization

      originated from simply local interaction between entities,
      possessing system-wide adaptive structure and function emergence.

   Swarm intelligence

      referring to the characteristics of the advanced intelligent
      behavior generations by cooperation among simple individuals.

   Router

      referring to the smart routing node with the characteristics of
      the biological behaviors and the capabilities of packet forwarding
      and processing.

   Link

      referring to the communication media providing interconnections
      among routers and end systems.

   QoS

      referring to the aggregated effect of the service performance,
      reflecting the user satisfaction degree on the service.  It can be
      described by a set of parameters, such as bandwidth, delay, delay
      jitter and error rate.

   Bandwidth

      referring to the amount of the transferred data per unit time,
      that is, the data transferring capability of the link.  In this
      paper, the overall bandwidth and the available bandwidth of the
      link are considered.

   Delay

      referring to the elapsed time by transferring packet from one
      place to another.

   Delay-Jitter



Wang, et al.              Expires May 21, 2010                  [Page 6]

Internet-Draft        Self-organizing network model        November 2009


      referring to the difference between the maximum and the minimum of
      the delay for transferring packet from one place to another.

   Error Rate

      referring to the ratio of the amount of the corrupted data to the
      total amount of the transferred data.  It has nothing to do with
      the service type and only have relations with the link type and
      the current network status.

   Node stability

      referring to the degree of the node status remaining relatively
      invariable.  The nodes with stronger stabilities are preferred
      when routing.

   User requirements

      referring to the demand of the user on the network QoS.  They are
      described fuzzily with intervals.

   Satisfaction degree of the user to the link

      referring to the satisfaction degree of the user to the QoS
      provided by his used link.

   Cost

      referring to the expense of the consumed resources when the
      network provider offered the service to the user.

   Pricing

      referring to the network service price charged by the network
      provider to the user.

   Small world edges

      referring to the frequently used paths when a pair of nodes
      communicated.  They are so-called preferred 'short-cut' when
      routing.










Wang, et al.              Expires May 21, 2010                  [Page 7]

Internet-Draft        Self-organizing network model        November 2009


4.  Motives and existent problems

   With the growing network scale and the increasing network dynamics,
   there exist huge challenges to the existing network models and
   routing schemes.  The expanded scale asks the network to possess the
   strong self-organizing and self-management capabilities at the same
   time the highly dynamics desires the distributed and adaptive routing
   without network-wide global information.  With the convergence of
   various networking technologies, numerous computers, mobile
   terminals, and sensors around the world are connected to the Internet
   with a variety of fixed, mobile, wireless, optical and other
   broadband internet access scheme, making the network scale grow
   continuously.  At the same time, network applications are becoming
   pervasive around individuals, homes, offices, vehicles, buildings and
   wider areas.  All these have increased the time and space
   complexities of the network topologies and dynamics dramatically,
   thus aggravated the management burdens of the network administrators
   even and the users.  In order to help them get rid of the complex
   network management works and minimize the network administration
   staff, the so-called self-organizing network should be designed and
   developed.

   Self-organizing phenomenon is prevalent in our lives and around the
   world.  In the natural world, fish swarms with good structures swims
   in the seas and rivers, ant colonies find their food along the
   shortest route.  Such these are good examples of self-organizing
   behaviors.  In fact, all participating entities establish an
   organizational structure without a coordination center when self-
   organizing.  Instead, these entities interact directly and react to
   changes in their local environment continuously.

   Self-organizing does not just mean distributed and localized control;
   in fact, it is also the results of structures and functionalities of
   the independent individuals and the relationships among them.  In the
   self-organizing systems, the simple actions of these individuals at
   microscope level can lead to the complex behaviors system-wide.  This
   kind of phenomenon is known as the "emerging".

   Another important feature of self-organizing system is its adaptation
   to its environmental changes.  In fact, it continuously adapts to
   changes implicitly.  For example, it often makes restructuring to
   react to its internal or external changes.  By doing so, it tries to
   converge to the desired good structure and avoid the bad one.

   Combining its inherent properties of adaptation and distribution, the
   self-organizing system will be robust to failures and corruptions.
   There does not exist single failure point and it can self-repair and
   self-correct errors without external help.  Therefore, it will not



Wang, et al.              Expires May 21, 2010                  [Page 8]

Internet-Draft        Self-organizing network model        November 2009


   collapse suddenly; when some problems occurred, it still runs with
   degraded performance.

   At present, the complexity of the communications network has become
   an increasingly serious problem.  Recent progresses of the self-
   organizing system are indicating that some answers may be found to
   this problem.  Self-organizing network model is based on the building
   up characteristics and behaviors of self-organizing.  In this paper,
   a network model with characteristics and behaviors of the self-
   organizing system is established and called self-organizing network
   model.








































Wang, et al.              Expires May 21, 2010                  [Page 9]

Internet-Draft        Self-organizing network model        November 2009


5.  Related issues

   Routing is important in the network.  With the expansion of the
   network scale and emergence of multimedia and real-time services, the
   user requirements on QoS (Quality of Service) become higher and
   higher, and QoS routing with various performance parameters
   considered is becoming one essential issue to be handled in any
   network model.

   Due to strong self-organizing feature inherent in swarm intelligence,
   the swarm intelligence based algorithms and strategies can be used to
   solve QoS routing under the self-organizing network environment.
   Thus, some basic knowledge on swarm intelligence and QoS routing are
   introduced at first before the proposed self-organizing network model
   is described.

5.1.  Swarm Intelligence

   Swarm intelligence refers to the generation of complex intelligent
   behavior through cooperation among simple individuals.  A significant
   milestone to indicate that the concept of swarm intelligence was
   formally put forward was the publication by Oxford University Press
   in 1999 of the monograph named "Swarm Intelligence: From Natural to
   Artificial System" authored by E Bonabeau, M Dorigo and others.

   The concept of swarm intelligence comes from the observations on the
   behaviors of some kinds of insects in the natural world, such as ants
   and bees.  One single ant's intelligence is not high, however, if a
   few ants come together, they can convey the foods to their nests,
   which they found on the road.  If there is a crowd of ants, they can
   work together to build a strong and beautiful nest, to resist the
   external threatens,and to multiply and bring-up their
   offspring.  This kind of intelligent behaviors emerged from such
   social living beings are known as the swarm intelligence.

   For swarm intelligence, the following five basic principles should be
   obeyed:

      Proximity Principle:

         Swarm can carry out simple calculation on space and time.

      Quality Principle:

         Swarm is able to respond to the quality factors in its
         environment.





Wang, et al.              Expires May 21, 2010                 [Page 10]

Internet-Draft        Self-organizing network model        November 2009


      Principle of Diverse Response:

         The acting scope of the swarm should not be too narrow.

      Stability Principle:

         Swarm should not change their behavior whenever its environment
         changes.

      Adaptability Principle:

         Swarm can change its behavior in due situation in case of not
         too high cost incurred.

      Swarm intelligence has following characteristics:

         Control is distributed without any center.  It can adapt to the
         current network status more easily.  It is more robust and
         individual failure can not affect the problem- solving
         capability of the swarm.

   Each individual in the swarm can affect its environment.  This is a
   way of indirect communication between individuals, called as
   stigmergy.  As the information transmission and individual
   cooperation can be done in indirect communication in swarm
   intelligence, the communication overhead increases slowly with the
   individual number, thus there exists better scalability in swarm
   intelligence.

   The individual's ability and its followed rules in the Swarm
   intelligence are very simple.  Thus, the realization of swarm
   intelligence is easy with simplicity.

   The complex behaviors of the swarm emerge from the interactions among
   simple individuals, thus, the swarm has the feature of self-
   organizing.

   Internet is a loosely-connected network to interconnect various sub-
   networks around connectivity.  In Internet, routing has essentially
   got rid of the centralized control existed in traditional
   telecommunications networks with some taste of self-organization.
   However, self-organizing only reflects at router level.  There are a
   variety of different routing protocols with different routing
   algorithms running in the router.  In order to make network operate
   coordinately, a large number of information on link and network
   status need to be exchanged among routers, their routing tables are
   calculated and updated, leading to poor scalability.  The deficiency
   of the existing routing architecture on scalability and robustness



Wang, et al.              Expires May 21, 2010                 [Page 11]

Internet-Draft        Self-organizing network model        November 2009


   emerged with the rapid growth of Internet.  In order to meet the
   requirements of new network applications, scalable routing
   architecture and efficient routing algorithm need to be developed.

   At present, with network scale expanded, sub-networks diversified and
   speed increased, simplifying network node organization and management
   is becoming one of the critical ways to reduce network cost, improve
   network utilization and enhance network reliability.

   By applying swarm intelligence to network routing, routing agents can
   be created at network nodes and cooperate along certain rules to find
   the optimal route with network scalability, adaptability and
   robustness improved.

5.2.  QoS Routing

   With the internet scale expanded and multimedia and real-time service
   emerged, the user QoS requirement is improved.  Research on QoS can
   help to improve network efficiency and reduce network cost.  By QoS
   mechanisms, the network provider can provide differentiated services
   according to different user QoS requirements with user satisfaction
   degree and network provider profit improved.  Thus, QoS support is
   essential in self-organizing network.

   There are mainly two ways to enhance QoS.  One is node control and
   the other is network-wide or local network control.  Routing affect
   network performance directly and thus QoS routing is critical to
   provide QoS.

   The main goal of QoS routing is to choose one route with user QoS
   requirement met at the same time ensure network resource efficiency.

   QoS routing involves the following two aspects:

   1.  Choosing Measurement parameters

          Measurement parameters are routing metrics and affect routing
          algorithm complexity directly.  They can be divided into three
          categories: convex, additive and multiplicative parameters.

   2.  Routing

          According to the given metrics and current network status, try
          to find an route to guarantee QoS.

   There are mainly three kinds of routing strategies: source,
   distributed and hierarchical routing.




Wang, et al.              Expires May 21, 2010                 [Page 12]

Internet-Draft        Self-organizing network model        November 2009


   Source routing changes the distributed problem to the centralized
   one.  It is easy to be implemented and can avoid loop when routing.
   However, a huge amount of global network status need to be exchanged
   and reserved, transmission and calculation overhead is too heavy
   especially for large scale network.  In addition, the obsolete and
   inaccurate global status information even may lead to routing failed.

   Distributed routing has shorter response time and routing algorithm
   is scalable.  However, it may lead to loop due to only local
   information used when routing decision made.

   Hierarchical routing can not only reduce information exchanged but
   also avoid loop generated when routing.  It is scalable, however, it
   is difficult to deal with QoS parameter aggregation properly.

   According to the destination number, routing can be divided into two
   categories: unicast and multicast, correspondingly unicast and
   multicast routing algorithm.

   For QoS routing, there are two basic problems: optimization and
   bounded performance.  The former tries to find a route with the
   optimal QoS metric values, asking for optimal solution; the latter
   tries to find a route with the bounded QoS metric values, only asking
   for the feasible solution.

   QoS routing algorithms usually have the following characteristics:

   1.  Non-NP

          Usually QoS routing is NP-complete.  It often needs to be
          solved using intelligent optimization or heuristic algorithm.

   2.  Adaptation

          It should adapt to network status change automatically,
          promoting load balancing and avoid network congestion.

   3.  Deal with inaccurate routing information

          The information used when routing, for example, the network
          status and the user QoS requirement, often is fuzzy.

   4.  Fairness

          The billing paid by the user should be proportional to his
          received QoS level.  For multicast, the billing maybe need to
          be apportioned among its members fairly.




Wang, et al.              Expires May 21, 2010                 [Page 13]

Internet-Draft        Self-organizing network model        November 2009


   5.  Robustness

          It can do re-routing or has one or multiple alternative
          path(s) when failure occurred.















































Wang, et al.              Expires May 21, 2010                 [Page 14]

Internet-Draft        Self-organizing network model        November 2009


6.  Self-organizing Network Design Paradigm

6.1.  DESIGN LOCAL BEHAVIOR RULES THAT ACHIEVE GLOBAL PROPERTIES

   To design a network function that establishes a global property, this
   paradigm is to distribute the responsibility among the individual
   entities: no single entity is "in charge" of the overall
   organization, but each contributes to a collective behavior.
   Following this paradigm, localized behavior rules must be deviced, if
   applied in all entities, automatically lead to the desired global
   property (or at least approximate it). "localized" mean that entities
   have only a local view of the network and interact with their
   neighbors and changes in the network have initially only local
   consequences.

6.2.  EXPLOIT IMPLICIT COORDINATION

   Implicit coordination means that coordination information is not
   communicated explicitly by signaling messages, but is inferred from
   the local environment.  A node observes other nodes in its
   neighborhood; based on these observations, it draws conclusions about
   the status of the network and reacts accordingly.

6.3.  MINIMIZE LONG-LIVED STATE INFORMATION

   To achieve a higher level of self-organization, the amount of long-
   lived state information should be minimized.  In general, the more
   localized the interactions are and the less coordination is needed,
   the less state information must be maintained.

6.4.  DESIGN PROTOCOLS THAT ADAPT TO CHANGES

   The need for the capability of nodes to react to changes in the
   network and its environment typically arises from changed resource
   constraints, changed user requirements, node mobility, or node
   failures.  Since there are no centralized entities that could notify
   the nodes about changes, each node has to continuously monitor its
   local environment and react in an appropriate manner.  Three levels
   of adaptation can be distinguished.

      Level 1:

         A protocol is designed so that it can cope with changes, such
         as failure and mobility.

      Level 2:





Wang, et al.              Expires May 21, 2010                 [Page 15]

Internet-Draft        Self-organizing network model        November 2009


         A protocol is designed to adapt its own parameters (e.g., value
         of timers, cluster size) as a reaction to changes in order to
         optimize system performance.

      Level 3:

         A protocol is designed so that it realizes if the changes are
         so severe that the currently employed mechanism is no longer
         suitable.  To detect such situations the environment is
         observed, and significant changes in major parameters trigger a
         fallback or alternative solution.

   Typically, these levels of adaptation are combined using control
   loops.

   There are also advanced levels of adaptation (e.g., learning
   algorithms) that effectively change the algorithms in the nodes.
   Here, these algorithms are not included for self-organized
   networking, as their application in a dynamic network is typically
   quite complex and difficult to predict.  In addition, dynamically
   changing algorithms might lead to difficulties in implicit
   communication, as the interpretation of the environment depends on
   the knowledge of their behavior.




























Wang, et al.              Expires May 21, 2010                 [Page 16]

Internet-Draft        Self-organizing network model        November 2009


7.  Network Model

   Self-organizing network model can be denoted as a graph G(V, E), V is
   node set, representing the routers which have the characteristics of
   biological behaviors and have the capabilities of information
   transmission and processing in the network; E is edge set,
   representing the links in the network.

7.1.  Network Parameters

   In order to describe the network status, certain parameters are
   introduced as follows:

      To the edge, consider the following parameters:

         total bandwidth (tbw), available bandwidth (abw), delay (dl),
         delay jitter (jt) and error rate (ls).  It is assumed that the
         specific delay, delay jitter and error rate experienced by the
         service through the link have nothing to do with the service
         type, only having relations with the link type and the current
         network status.

      To the node, consider the following parameters:

         Stability degree (st).

7.2.  Network Self-organization Behavior Design

   Nodes in self-organizing network have characteristics of biological
   diversity.  In this document, the following network self-organization
   behaviors are introduced:

   1.   Incarnation

           A new node is generated with certain necessary information
           initialized.

   2.   Environment Awareness

           A node is aware of parameters of its connected links, for
           example, their total bandwidth, available bandwidth, delay,
           delay jitter and error rate.

           A node is aware of the status of its neighboring nodes, for
           example, their load and stability degree.






Wang, et al.              Expires May 21, 2010                 [Page 17]

Internet-Draft        Self-organizing network model        November 2009


   3.   Relation establishment/elimination

           Efficient and directly-connected edge establishment

              With routing continuously, a node in the network will
              gradually memorize some frequently-used paths to other
              nodes.  Such paths are called small world edges.  If some
              small world edge is frequently used as the next hop in
              some route when routing, a directly-connected edge should
              be established between the two end nodes of this small
              world edge whenever possible, so that the efficiency of
              routing and transmission.

              Here, the main consideration is the used frequency of a
              small world edge as one hop when routing.  Only when its
              used frequency is above one preset threshold during
              certain period of time, does it be considered to establish
              one directly connected link between its two end nodes.

              A node maintains a counter for each of its memorized small
              world edges.  Every times when a small world edge used as
              one hop on a route successfully, its corresponding counter
              should be increased by 1, and when its value is above the
              preset threshold, a request to establish a directly
              connected edge is issued.  In order to keep the state
              refresh, all counters will be reset periodically.

           Enhanced edge establishment

              When one edge is often rejected as one hop on a route due
              to its inability of meeting the user QoS requirement, its
              performance should be enhanced to provide better QoS.  A
              node sets one rejection counter for each of its connected
              edge, and whenever the edge is rejected as the next hop,
              the corresponding counter is increased by 1.  If the
              counter value is above the preset threshold, a request to
              enhance the corresponding edge's performance is issued.

           Edge deletion

              When any edge is never be used after an enough long time
              period (a measurement period), it should be deleted.  A
              node maintains a timer for each of its connected edges.
              The timer's initial value is set as the measurement
              period.  If the edge was used before its corresponding
              timer time out, the timer is reset; otherwise, once the
              timer timed out, an request to delete its corresponding
              edge will be issued.



Wang, et al.              Expires May 21, 2010                 [Page 18]

Internet-Draft        Self-organizing network model        November 2009


           When a node died, its connected edges are deleted.

   4.   Load migration

           In order to balance the network load and thus efficiently use
           network resources, load migration is introduced for node.  It
           is realized by proper load apportion among these neighboring
           nodes not by physically changing node location.

           According to the trigger manner, it can be classified into
           active and passive migration.

              Passive migration

                 It is such a situation that a node was forced to
                 migrate a fraction of its load to its neighboring
                 node(s) if permitted because it is overloaded.

                 A node monitors its own load.  When its load is above
                 the preset threshold for the preset time period
                 delta(t2), the node issue a request to its neighboring
                 nodes for load migration.  They determine if this
                 request can be accepted and the amount of the migrated
                 load based on their own loads.

              Active migration

                 It is such a situation that when it is light-loaded
                 continuously, a node begins to probe whether its
                 neighboring nodes are overloaded, and actively accept
                 the whole or partial amount of volunteering migrated
                 load by the overloaded node(s) based on its own
                 conditions.

                 A node monitors its own load.  When it is light-loaded,
                 that is, below a preset threshold, for a preset time
                 period delta(t3), the node begins to observe the load
                 status of its neighboring nodes.  If some of them are
                 found to be overloaded for a preset time period
                 delta(t1), the active migration is initiated.

              Here, delta(t1) < delta(t2) < delta(t3).

   5.   Cloning

           Cloning means copying routing information from one node to
           another.  The cloning-generated node can not only replace the
           cloned node to work, but also can be used to share its load.



Wang, et al.              Expires May 21, 2010                 [Page 19]

Internet-Draft        Self-organizing network model        November 2009


   6.   Reproduction

           Reproduction means that two or more nodes transfer their
           routing information integratedly into a node.  Thus, the
           reproduced node can not only replace their parent nodes to
           work, but also can be used to share their loads.

   7.   Dormancy

           When a node does not run any task over a time period above a
           preset threshold, it becomes dormant to reduce its power
           consumption.

   8.   Coma

           A node enters into the so called coma state temporally if it
           can not act normally due to some in-vital errors, for
           example, bugs in routing software, occurred.  A coma node
           will restore after a period of self healing or by certain
           external forces.

   9.   Wake up

           Wake up the coma or dormant node to resume their work.  If in
           the routing process, a node can not find the proper next hop
           routing from its neighbors, it will wake up its coma or
           dormant neighbor if any.

   10.  vivification

           A coma or dormant node self-restore to resume its work.

   11.  succour

           A coma node restores to resume its work with external
           intervention.

   12.  death

           A node can work no longer due to vital failure occurred, for
           example, some unrepairable hardware failures.

7.3.  Node Stability Degree

   1.  Factors related with node stability degree

          Many behaviors in self-organizing network can lead to node
          instability, for example, node migration, dormancy, coma and



Wang, et al.              Expires May 21, 2010                 [Page 20]

Internet-Draft        Self-organizing network model        November 2009


          death and so on, and in most cases these behaviors have
          relations with node loads.  The factors related with node
          instability are described as follows.

          External factors

             It mainly refers to neighboring node load.  It has great
             effect on node migration behavior and thus affects node
             stability degree severely.

          Internal factor

             It mainly refers to a node's own load.  Overloaded may lead
             to coma even migration and light-loaded migration even
             death.

   2.  Stability calculation

          Based on the above, when node stability degree calculated, a
          node's own and its neighbors' load should be taking into
          account with emphasis.

          Introduce the following four parameters for each node: total
          CPU cycles TCPU, available CPU cycles ACPU, total buffer size
          TBUF and available buffer size ABUF.  Then, define CPU and
          buffer availability ratio as follows:

             RAC=ACPU/TCPU (Formula 1)

             RAB=ABUF/TBUF (Formula 2)

          Define node load descriptor as follows:

             LD=1/(a/(RAC) + b/(RAB)) (Formula 3)

          Here, a and b are tuning factors to reflect relative
          significance degrees of CPU and buffer utilization on node
          load, a,b>0, a + b = 1.  Apparently, 0 <= LD <=1, and the
          smaller the LD, the much light the node load.

          Define node stability degree as follows:

             ST=a*LD(nb)+b*(1 -2*|1/2-LD|) (Formula 4)

          Here, a and b are tuning factors to reflect relative
          significance degrees of neighboring node load and node's own
          load on node stability, a, b > 0, a + b = 1.  A node may have
          several neighboring nodes.  If so, LD(nb) is the LD of the



Wang, et al.              Expires May 21, 2010                 [Page 21]

Internet-Draft        Self-organizing network model        November 2009


          node with the heaviest load.  Apparently, 0 <= ST <=1.

   According to formula, the smaller the ST, the much stable the node.
   When its neighboring node load becomes much light, the stability
   degree of a node becomes higher, because the possibility of its
   light-loaded neighbors migrating load to it becomes lower; otherwise,
   the stability degree of a node becomes lower.  When the node load
   varies from its median value, its node stability degree becomes
   lower; the much approaching the median value, the much stable the
   node, because the possibility of migrating load between it and its
   neighbors become lower.








































Wang, et al.              Expires May 21, 2010                 [Page 22]

Internet-Draft        Self-organizing network model        November 2009


8.  Routing Request

   Because it is difficult to describe user QoS requirement exactly, the
   interval is used to describe it.

8.1.  User QoS Unicast Routing Request

   Define user QoS unicast routing request as R(v( , s), v( , d), delta(
   , bw), delta( , dl), delta( , jt), delta( , ls), p).  Here, v(s)
   belongs to V and is its source node; v(d) belongs to V and is its
   destination node, delta(bw)=[bw_r(L), bw_r(H)] is its bandwidth
   constraint interval, delta(dl)=[bl_r(L, ), bl_r(H, )] is its delay
   constraint interval, delta(jt)=[jt_r(L, ), jt_r(H, )] is its delay
   jitter constraint interval, delta(ls)=[ls_r(L, ), ls_r(H, )] is its
   error rate constraint interval, p is the upper bound of the price the
   user willing to pay.

8.2.  User QoS Multicast Routing Request

   At first, consider a user heterogeneous QoS multicast routing
   request, that is, each multicast member has different QoS requirement
   and the upper bound of the price he is willing to pay, denoted as
   R(v( , s), v(d), delta(d, bw), delta(d, dl), delta(d, jt), delta(d,
   ls), p(d, )). delta(d, bw)=[bw_r(L, d), bw_r(H, d)], delta(d,
   dk)=[dl_r(L, d), dl_r(H, d)], delta(d, jt)=[jt_r(L, d), jt_r(H, d)],
   delta(d, ls)=[ls_r(L, d), ls_r(H, d)] and p(d, ) is corresponding to
   the multicast member v(d).the ceiling of the cost what the users want
   to pay.  For a homogeneous one, each member has the same QoS
   requirement and the upper bound of the price he is willing to pay.






















Wang, et al.              Expires May 21, 2010                 [Page 23]

Internet-Draft        Self-organizing network model        November 2009


9.  Link QoS Evaluation

   It is difficult to measure network status exactly, thus fuzzy
   information handling is necessary.

9.1.  Link Parameter Membership Degree

   1.  Bandwidth membership degree

          Assume the available bandwidth abw(l) of the link e(l) belongs
          to [abw(L, l), abw(H, l)], the membership degree function of
          the actually occupied bandwidth bw by a user on e(l) to it is
          defined as follows:

             f(l, abw, bw)=1, bw<=abw(L, l)

             f(l,abw,bw)=1/2-1/2*sin{pi/
             [abw(H,l)-abw(L,l)]*[bw-(abw(L,l)+abw(H,l))]/2},
             abw(L,l)<bw<=abw(H, l)

             f(l, abw, bw)=0, bw>abw(H, l) (Formula 5)

          The above formula assumes that the bandwidth membership degree
          function is subject to the smaller form of the mountain-shaped
          distribution.

   2.  Delay membership degree

          Assume the delay dl(l) of the link e(l) belongs to [dl(L, l,
          dl(H, l))], the membership degree function of the actually
          experienced delay dl by a user on e(l) to it is defined as
          follows:

             f(l, dl, dl)=1 ,dl<=dl(L, l)

             f(l, dl, dl)=1/2+1/2*sin{pi/ [dl(H,l)-dl(L,l)]*[dl-
             (dl(L,l)+dl(H,l))/2]} ,dl(L,l)<dl<=dl(H, l)

             f(l, dl, dl)=0 ,dl>dl(H, l) (Formula 6)

          The above formula assumes that the delay membership degree
          function is subject to the larger form of the mountain-shaped
          distribution.

   3.  Delay-Jitter membership degree

          Assume the delay jitter jt(l) of the link e(l) belongs to
          [jt(L, l, jt(H, l))], the membership degree function of the



Wang, et al.              Expires May 21, 2010                 [Page 24]

Internet-Draft        Self-organizing network model        November 2009


          actually experienced delay jitter jt by a user on e(l) to it
          is defined as follows:

             f(l, jt, jt)=1 ,jt<=jt(L, l)

             f(l, jt, jt)=1/2+1/2*sin{pi/ [jt(H,l)-jt(L,l)]*[jt-
             (jt(L,l)+jt(H,l))/2]} ,jt(L,l)<jt<=jt(H, l)

             f(l, jt, jt)=0 ,jt>jt(H, l) (Formula 7)

          The above formula assumes that the delay jitter membership
          degree function is subject to the larger form of the mountain-
          shaped distribution.

   4.  Error Rate membership degree

          Assume the error rate ls(l) of the link e(l) belongs to [ls(L,
          l, ls(H, l))], the membership degree function of the actually
          experienced error rate ls by a user on e(l) to it is defined
          as follows:

             f(l, ls, ls)=1 ,ls<=ls(L, l)

             f(l, ls, ls)=1/2+1/2*sin{pi/ [ls(H,l)-ls(L,l)]*[ls-
             (ls(L,l)+ls(H,l))/2]} ,ls(L,l)<ls<=ls(H, l)

             f(l, ls, ls)=0 ,ls>ls(H, l) (Formula 8)

          The above formula assumes that the error rate membership
          degree function is subject to the larger form of the mountain-
          shaped distribution.

9.2.  QoS Satisfaction Degree

   The satisfaction degree functions of the user to his actually
   received QoS from the link are defined as follows.

   1.  Bandwidth

          The satisfaction degree function of the user to his actually
          occupied bandwidth bw from the link e(l) is defined as
          follows:

             S(l,bw,bw)=0 ,bw<bw_r(L, )

             S(l,bw,bw)=e^(-((bw_r(H, )-bw)/(bw-bw_r(L, )))^2)
             ,bw_r(L,)<=bw<bw_r(H, )




Wang, et al.              Expires May 21, 2010                 [Page 25]

Internet-Draft        Self-organizing network model        November 2009


             S(l,bw,bw)=1 ,bw>=bw_r(H, )(Formula 9)

          According to the above formula, a user become much satisfied
          with bw increased.  When bw reaches bw_r(H, ), he becomes the
          most satisfied.

   2.  Delay

          The satisfaction degree function of the user to his actually
          experienced delay dl(l) from the link e(l) is defined as
          follows:

             S(l,dl,dl)=1 ,dl<dl_r(L, )

             S(l,dl,dl)=1-e^(-((dl_r(H, )-dl)/(dl-dl_r(L, )))^2)
             ,dl_r(L, )<=dl<dl_r(H, )

             S(l,dl,dl)=0 ,dl>=dl_r(H, ) (Formula 10)

          According to the above formula, a user become much satisfied
          with dl(l) decreased.  When dl(l) decreases to dl_r(L, ), he
          becomes the most satisfied.

   3.  Delay jitter

          The satisfaction degree function of the user to his actually
          experienced delay jitter jt(l) from the link e(l) is defined
          as follows:

             S(l,jt,jt)=1 ,jt<jt_r(L, )

             S(l,jt,jt)=1-e^(-((jt_r(H, )-jt)/(jt-jt_r(L, )))^2)
             ,jt_r(L, )<=jt<jt_r(H, )

             S(l,jt,jt)=0 ,jt>=jt_r(H, ) (Formula 11)

          According to the above formula, a user become much satisfied
          with jt(l) decreased.  When jt(l) decreases to jt_r(L, ), he
          becomes the most satisfied.

   4.  Error rate

          The satisfaction degree function of the user to his actually
          experienced error rate ls(l) from the link e(l) is defined as
          follows:

             S(l,ls,ls)=1 ,ls<ls_r(L, )




Wang, et al.              Expires May 21, 2010                 [Page 26]

Internet-Draft        Self-organizing network model        November 2009


             S(l,ls,ls)=1-e^(-((ls_r(H, )-ls)/(ls-ls_r(L, )))^2)
             ,ls_r(L, )<=ls<ls_r(H, )

             S(l,ls,ls)=0 ,ls>=ls_r(H, ) (Formula 12)

          According to the above formula, a user become much satisfied
          with ls(l) decreased.  When ls(l) decreases to ls_r(L, ), he
          becomes the most satisfied.

9.3.  Link QoS Evaluation

   The evaluation function of the user on the link provided bandwidth,
   delay, delay jitter and error rate and the comprehensive one on the
   link provided QoS are defined as follows:

      g(l, bw) = f(l, bw, ubw)*S(l, bw, ubw) (Formula 13)

      g(l, dl) = f(l, dl, udl)*S(l, dl, udl) (Formula 14)

      g(l, jt) = f(l, jt, ujt)*S(l, jt, ujt) (Formula 15)

      g(l, ls) = f(l, ls, uls)*S(l, ls, uls) (Formula 16)

      W(l) = a(bw)*g(l, bw) + a(dl)*g(l, dl) + a(jt)*g(l, jt) +
      a(ls)*g(l, ls) (Formula 17)

   Here, a(bw), a(dl), a(jt) and a(ls) are weights of bandwidth, delay,
   delay jitter and error rate, indicating their relative importance on
   the user QoS requirement, 0<=a(bw), a(dl), a(jt), a(ls)<=1, a(bw) +
   a(dl) + a(jt) + a(ls) = 1.  W(l) in [0, 1], and the bigger it is, the
   higher evaluation the user on the link provided QoS.




















Wang, et al.              Expires May 21, 2010                 [Page 27]

Internet-Draft        Self-organizing network model        November 2009


10.  Utility Calculation and Gaming Analysis

   According to economics principles, commodity pricing should be based
   on supply and demand relations at market at the same time commodity
   prices have effects on supply and demand relations.

   In order to improve communication quality, users want to occupy
   bandwidth on the link as much as possible, however, this will lead to
   network resource shortage.  In this case, network providers will
   raise their resource prices, and then users have to pay more for
   network usage.  In order to increase their revenue, network providers
   want to increase network resource prices, however, some users will
   abort to use their network resources no longer, and thus leading to
   their revenue down.  As a result, network providers have to cut down
   their resource prices to attract their users back.  In general, How
   much resources users consume should be based on their own conditions
   and resource pricings in order to maximize their own interests while
   resource prices should be determined by their providers based on
   current supply and demand relations at market so that their profits
   maximized.

   Not only bandwidth but also delay, delay jitter and error rate should
   be considered when routing.  Thus, delay, delay jitter and error rate
   have effects on resource pricing and then on users interests and
   network providers revenue.

10.1.  Cost and Price

   Cost refers to resource expense network provider suffered for
   providing service.  Here, network resource only refers to bandwidth.
   Assume bandwidth cost per unit is cb on the link el.  For the
   provided bandwidth ubw, cost suffered by the network provider is as
   follows:

      Cost(l) = c(b) * ubw (Formula 18)

   Price refers to charge user pay for consuming network resource.  If
   the occupied bandwidth on link el by user is ubw, price paid by the
   user is as follows:

      Pay(l)=p*ubw +p(fk) (Formula 19)

   p is bandwidth base-price and is related with bandwidth utilization.
   When bandwidth utilization is high, its provider may consider to
   increase p, and when it is low, its provider may consider to decrease
   p.





Wang, et al.              Expires May 21, 2010                 [Page 28]

Internet-Draft        Self-organizing network model        November 2009


      p=p(min), h<h(min)

      p=c(b)*(1+a*h(-2, 0))/(1+a*h(-2, )) , h(min)<=h<h(0)

      p=c(b)*[2-e^(-k(h-h(0)))], h(0)<=h<h(max)

      p=p(max), h(max)<=h<h(1)

      p is determined through auction (Formula 20)

      h=(tbw-abw)/tbw (Formula 21)

   h is link bandwidth utilization, h(0), h(1), h(min), h(max), p(min)
   and p(max) are set by network provider, a and k are calculated by
   formula as follows:

      a=(c(b)-p(min))/(p(min)*h(-2,min)-c(b)*h(-2,0)) (Formula 22)

      k=ln(2-p(max)/c(b))/(h(max)-h(0))^2 (Formula 23)

   p(fk) is floating price related with delay, delay jitter and error
   rate, given by network provider and shown as Table 1:

   Table 1 Floating Price

        Delay         Jitter      Error rate   Floating Price
      -------------------------------------------------------
      delta(1,dl)   delta(1,jt)   delta(1,ls)     p(f1)
      delta(2,d1)   delta(2,jt)   delta(2,ls)     p(f2)
      delta(3,d1)   delta(3,jt)   delta(3,ls)     p(f3)
         ...           ...           ...           ...
      delta(k,d1)   delta(k,jt)   delta(k,ls)     p(fk)
         ...           ...           ...           ...

                                 Figure 1

   Here

      delta(k, dl)=[dl(k, low), dl(k, high)],

      delta(k, dl)=[dl(k, low), dl(k, high)],

      delta(k, jt)=[jt(k, low), jt(k, high)],

      delta(k, ls)=[ls(k, low, jt(k, high))].






Wang, et al.              Expires May 21, 2010                 [Page 29]

Internet-Draft        Self-organizing network model        November 2009


10.2.  Utility

   Utilities are used to describe status about user interests and
   network provider profits.  User utility on his used link is mainly
   related with his link provided QoS evaluation value, his paid price
   and network provider bearing cost.  In general, the higher the user
   evaluation value on the link provided QoS, the nearer the user paid
   price to the network provider bearing cost, the larger the user
   utility on his used link.  The user utility uu(l) on the link e(l) is
   defined as follows:

      uu(l) = W(l) * (Cost(l) / Pay(l)) (Formula 24)

   The network provider utility on its provided link is mainly related
   with his got price from his user and his bearing cost for his
   provided link.  The network provider utility on the link e(l) is
   defined as follows:

      un(l) = (Pay(l) - Cost(l)) / Cost(l) (Formula 25)

10.3.  Gaming

   A user and a network provider play game on a link e(l).  The user
   gaming strategy set is m different allocated bandwidth: ubw(1),
   ubw(2), ..., ubw(m).  Here, ubw(i) is the allocated bandwidth on the
   link e(l) under the No.i user strategy.

   The network provider strategy set is n different link bandwidth
   price: P(1), P(2),...,P(n), determined by formula 20 based on formula
   19 and Table 1.

   Once a user's QoS requirement is given, the corresponding user and
   network provider strategy set can be determined.

   Calculate utility matrix R(m*n)=[uu(ij), un(ij)].  Its rows and
   columns are corresponding to user and network provider strategies
   respectively. (ubw(i), P(j)) is the user utility and uu(ij) and the
   network provider utility un(ij) under the strategy pair (ubw(i),
   P(j)).  The purpose of the gaming is trying to find out the best
   strategy pair (ubw(i), P(j))(best), under which both the user and the
   network utility reaches and approaches Parato optimum under Nash
   equilibrium.

   According to Nash equilibrium definition, the element with Nash
   equilibrium achieved in utility matrix should meet the following
   conditions:





Wang, et al.              Expires May 21, 2010                 [Page 30]

Internet-Draft        Self-organizing network model        November 2009


      uu(ij) => uu(i(*)j) ,i(*) =1,2,...,m

      un(ij) => un(ij(*)) ,i(*)=1,2,...,n (Formula 26)

   If such a element found, its corresponding strategy pair (ubw(i),
   P(j)) is the one with Nash equilibrium achieved when the user and the
   network provider play game on the link.

   However, such a element may not exist and multiple such elements may
   exist simultaneously.  In this case, Pareto dominance, defined as
   follows, need to be compared further.

      pareto(ij)=a/uu(ij)+b/un(ij) (Formula 27)

   a and b are preference weights for user and network ultilities, a, b
   > 0, a+b=1.  Apparently, a element with smaller Pareto dominance is
   more Pareto optimal.  A strategy pair with the smallest Pareto
   dominance is chosen as the optimal one (if multiple such ones exist,
   choose one at random).
































Wang, et al.              Expires May 21, 2010                 [Page 31]

Internet-Draft        Self-organizing network model        November 2009


11.  Unicast Path and Multicast Tree Evaluation

   When a unicast path or multicast tree is evaluated, there are two
   factors considered significantly: user and network provider utility.
   The objective of routing optimization is to try to maximize user
   utility, network provider utility and their sum simultaneously, so
   that their utility win-win are prompted.

   The evaluation functions of the unicast path P and the multicast tree
   T are defined as follows:

      J(p)=a(up)/UU(P) + a(np)/UN(P) (Formula 28)

      J(T)=a(ut)/UU(T) + a(nt)/UN(T) (Formula 29)

      UU(P)=sigma(uu(l), l belonging to P) / L(P) (Formula 30)

      UU(T)=sigma(sigma(uu(i, l), l belonging to (s-i)), l belonging to
      T) (Formula 31)

      UN(P)=sigma(un(l), l belonging to P)/L(P) (Formula 32)

      UN(T)=sigma(un(l), l belonging to T)/L(T) (Formula 33)

   Here, UU(P) and UU(T) are user utilities on P and T respectively,
   UN(P) and UN(T) are network provider utilities on P and T
   respectively, L(P) and L(T) are hop numbers of P and T respectively,
   a(up) and a(ut) are user utility preference weights, a(np) and a(nt)
   are network provider preference weights respectively, 0<a(up), a(np),
   a(ut), a(nt )<1, a(up)+a(np) =1, a(ut)+a(nt) = 1.

   According to formula 28 and 29, when both the user and the network
   utilities are larger, the evaluation value of the corresponding
   unicast path or multicast tree is smaller, otherwise it is larger.
   Therefore, the evaluation value of the optimal unicast path or
   multicast tree is smallest.















Wang, et al.              Expires May 21, 2010                 [Page 32]

Internet-Draft        Self-organizing network model        November 2009


12.  Mathematical Model

12.1.  Unicast Mathematical Model

   The objective of the QoS unicast routing optimization is as follows:
   with the user QoS requirement and the upper bound of the price the
   user willing to pay satisfied, try to maximize the user utility, the
   network provider utility and their sums on the path.  Its
   corresponding mathematical model is described as follows:

      UU(P) -> max{UU(P)} (Formula 34)

      UN(P) -> max{UN(P)} (Formula 35)

      UU(P) + UN(P) -> max{UU(P) + UN(P)} (Formula 36)

      s.t. main({abw}, e(l) is belonging to P(sd)) => bw_r( , l)
      (Formula 37)

      sigma(dl( , l), e(l) is belonging to P(sd)) <= dl_r( , h) (Formula
      38)

      sigma(jt( , l) <= jt_r( , h), e(l) is belonging to P(sd))(Formula
      39)

      1-pi((1-ls( , l)) e(l) is belonging to P(sd))(Formula 40)

      pay( , p) <= p (Formula 41)

12.2.  Multicast Mathematics Model

   The objective of the QoS multicast routing optimization is as
   follows: with the QoS requirement and the upper bound of the willing-
   to-pay price of each multicast member satisfied, try to maximize the
   user utility, the network provider utility and their sums on the
   tree.  Its corresponding mathematical model is described as follows:

      UU(T) -> max{UU(T)} (Formula 42)

      UN(T) -> max{UN(T)} (Formula 43)

      UU(T) + UN(T) -> max{UU(T) + UN(T)} (Formula 44)

      s.t. main({abw(d, l)}, e(l) is belonging to P(sd)) => bw_r(d, l)
      (Formula 45)

      sigma(dl(d, l), e(l) is belonging to P(sd)) <= dl_r(d, h) (Formula
      46)



Wang, et al.              Expires May 21, 2010                 [Page 33]

Internet-Draft        Self-organizing network model        November 2009


      sigma(jt(d, l) <= jt_r(d, h), e(l) is belonging to P(sd))(Formula
      47)

      1-pi((1-ls(d, l)) e(l) is belonging to P(sd))(Formula 48)

      pay(d, p) <= p(d, ) (Formula 49)

   The above is about heterogeneous multicast.  For homogeneous one, the
   values of bw_r(d, l), dl_r(d, h), jt_r(d, h), ls_r(d, h) and p(d) of
   all multicast members are the same.









































Wang, et al.              Expires May 21, 2010                 [Page 34]

Internet-Draft        Self-organizing network model        November 2009


13.  Small World Behavior

   1.  Small world behavior has the following characteristics

          High variability of node degree distribution can help to get
          short route and high clustering coefficient;

          When node degree distribution variability is not very high, it
          can not alone lead to small world behavior;

          Local connection preference can lead to small world behavior,
          especially in router-level network topology.

          Self-organizing network has behaviors with biological
          characteristics.  Node and edge are changing dynamically and
          they can be established, changed even removed, thus node
          degree distribution is variable.  In addition, in self-
          organizing network, interactions between nodes are localized,
          and then there exists local connection preference.  However,
          it needs an evolution process from a randomly generated
          network to a network with small world behaviors, and during
          this process the so-called small world behaviors can not be
          directly taken into use when routing.  Another point, in
          existing small world network models, node connection refers to
          directly connection and its distribution variability is
          regarding to such directly connected edge.  In this document,
          the frequently-used indirectly connected edge (see the
          mentioned small world edge section) substitutes the directly
          connected one to produce small world behaviors and guides the
          establishment of the efficient directly connected edge, taking
          advantage of small world behaviors.

          For example, a node A is directly connected with nodes A1, A2,
          A3 and A4, and routes with A as their source node and D1, D2
          and D3 as their destination nodes have been established.  If
          these three routes are frequently used in other routes
          successfully, three small word edges are considered to exist
          from A to D1, D2, D3.  When calculate node degree of A, these
          three small world edge are included.  Therefore, node degree
          distribution variability can be supported.

          Of course, use a path as an edge can bring some problems.
          After all, the complexity of dealing with a path is not the
          same as that of dealing with an edge when routing.  In
          addition, although a route often can be found in short time
          with small world edge used, its hop number may be larger and
          thus is not the optimal one.  For example, there are small
          world edges between S and M and between M and D. If used when



Wang, et al.              Expires May 21, 2010                 [Page 35]

Internet-Draft        Self-organizing network model        November 2009


          routing from S to D, a route is found very quickly with only
          two routing operations done.  However, the found route has 8
          hops.  If S->A->B->D are chosen as the route without small
          world edge used, it only has 3 hops.  In addition, small world
          edge recording also brings router extra storage overhead.

          In order to avoid the above problems appearing frequently when
          routing, not only the times of using small world edges when
          routing should be limited, for example, only at the last hop
          use a small world edge, that is, only use the small world edge
          with destination node reachable, but also a small world edge's
          hop number should be bounded when it is established.

   2.  Small world behavior realization in self-organizing network

       Table 2 List of worldlet Edge

         destination   intermediate   hop      used
         node      node sequence      count  times
       -------------------------------------------------------
         D(1)       (N(1),...)      5            m(1)
         D(2)       (N(4),...)      3            m(2)
         D(3)       (N(4),...)      3            m(3)
         ...           ...         ...             ...


                                   Figure 2

          When routing in self-organizing network, to find even a sub-
          optimal route quckly is often preferred to find a optimal one
          with much more time.  Thus, it is necessary to efficiently
          establish and use small world edge in routing.

             Small world edge usage

                With routing continuously, each routing node gradually
                accumulates some small world edges, and then convenient
                and short-cut reachable information to other nodes
                become more and more.  There is no doubt that using
                these well-known small world edges when routing can
                shorten routing time.

                Each routing node records these small world edges from
                which depart as in table 2.

                Table initialization: each routing node maintains a
                small world edge registration node shown as table 2.  At
                the beginning, it is initialized as an empty table.



Wang, et al.              Expires May 21, 2010                 [Page 36]

Internet-Draft        Self-organizing network model        November 2009


                Small world edge adding: It is carried out by routing
                algorithm.  Whenever a route is found successfully, if
                it is eligible to become a small world edge, its related
                information will be added to the registration table and
                its corresponding "used times" is set to be 0.

                Used times: Whenever a small world edge is successfully
                used in routing, its used times is increased by 1.

                Update: The registration table is scanned onec every
                delta(t(swp)), during which those small world edges with
                zero used times will be deleted and each remaining one's
                used times is reset to be 0.

             Routing success ratio

                It refers to the percentage of successful routing times
                in total routing times in a routing node.  Nodes with
                higher success ratio should be preferred when routing.
                Two counters are equipped with each node: successful
                routing times counter rcs(i) and total routing times
                counter rct(i).  Every time when routing is done,
                increase rct(i) by 1, and every time when routing is
                successful, increase rcs(i) by 1. rcs(i) and rct(i) are
                periodically refreshed, that is, every delta(t(rc))
                time, they are reset to be 0.

                The routing success ratio for node i is calculated as
                follows:

                   I(i) = rcs(i) / rct(i) (Formula 50)

             Address similarity degree

                Nodes with the same IP address prefix are likely to be
                located at neighborhood and close to each other.  The
                longer such the same prefix, the closer neighborhood
                these nodes located at.  For example, 202.118.1.64 and
                202.118.1.206 have the same prefix 202.118.1, the nodes
                with these two highly similar IP address should be very
                close to each other.  The percentage of the length of
                the same prefix of two addresses in the address length
                is defined as the so called address similarity degree.
                It can be gotten as follows: from left to right two
                addresses are compared bitwise, counting the times of
                the same bits appearing in the two addresses and record
                it as D, until different bits appeared.  Assume the
                address length is T, their address similarity degree is



Wang, et al.              Expires May 21, 2010                 [Page 37]

Internet-Draft        Self-organizing network model        November 2009


                calculated as follows:

                   S=D/T (Formula 51)

                When routing, the address similarity degree between each
                candidate next hop node and the destination node is
                compared, and the node with the highest similarity
                degree should be preferred as the next hop because it
                should be nearest to the destination node.  Doing so can
                help to reduce both routing time and route hop count.









































Wang, et al.              Expires May 21, 2010                 [Page 38]

Internet-Draft        Self-organizing network model        November 2009


14.  Route Strategies

   At the initial phase of self-organizing network operating, the
   distributed routing algorithm is adopted to adapt to high network
   dynamics and variations.  At this phase the network-wide, especially
   backbone topology and routing information are collected gradually and
   then the self-organizing network will enter into relatively-stable
   phase with such information remaining invariable or varying little
   for a long time.  At this time, the centralized algorithm can be used
   to optimize routing and improve routing efficiency.  According to its
   situation of dynamics and variation, the distributed and centralized
   algorithm is used alternatively.







































Wang, et al.              Expires May 21, 2010                 [Page 39]

Internet-Draft        Self-organizing network model        November 2009


15.  Security Considerations

   Security is a big problem in self-organizing network.  Routing nodes
   in self-organizing networks directly interact among them in
   distributed peer-to-peer manner.  Each node contributes to complex
   network behavior with its own simple action.  Under such a situation,
   identity authentication and behavior monitoring become more difficult
   while detecting and defending malicious intrusion become harder.  If
   the new security architecture and technique are not developed for
   self-organizing network, the network will become more vulnerable.  In
   this document, the focus is on the basic architecture and QoS routing
   technique in self-organizing network, and security issues and
   techniques are not discussed.






































Wang, et al.              Expires May 21, 2010                 [Page 40]

Internet-Draft        Self-organizing network model        November 2009


16.  IANA Considerations

   This document has no actions for IANA.
















































Wang, et al.              Expires May 21, 2010                 [Page 41]

Internet-Draft        Self-organizing network model        November 2009


17.  Acknowledgments

   The author would like to thank Zhankao Wen, Weidong Wang, Weixin Wu,
   Jun Liu, Dengke Zhang, Jan Wu, Xiaolei Huang, Xiaofeng Liu, Yao Fu,
   Jun Hu, Guilin Liu, Peiyu Qin, Yulei Wu, Hanrui Wang and the rest of
   the Adaptive Routing Working Group for the ideas and support they
   have given to this project.












































Wang, et al.              Expires May 21, 2010                 [Page 42]

Internet-Draft        Self-organizing network model        November 2009


Appendix A.  References

   1.   Christian Prehofer, Christian Bettstetter.  Self-Organization in
        Communication Networks: Principles and Design Paradigms[J], IEEE
        Communications Magazine, 2005: 78-84.

   2.   Sudhir Dixit, Amardeo Sarma.  Advance in self-organizing
        networks[J], IEEE Communications Magazine, 2005: 76-77.

   3.   R. Ghnemat, C. Bertelle, G.H.E. Duchamp.  Self-Organization
        Simulation over Geographical Information System Based on Multi-
        Agent Platform[A], The European Simulation and modeling
        Conference[C], 2006: 23-25.

   4.   Beni, G., Wang, J. Swarm intelligence[A], In Proceedings of the
        Seventh Annual Meeting of the Robotics Society of Japan[C],
        1989: 425-428.

   5.   Susan Hackwood, Gerardo Beni.  Self organization of sensors for
        swarm intelligence[A], proceedings of the 1992 IEEE
        international conference on robotics and automation[C], 1992:
        819-825.

   6.   M. Dorigo, E. Bonabeau, G. Theraulaz.  Ant algorithms and
        stigmergy[J], Future Generation Computer System, 2000, 16(8):
        851-871.

   7.   YingHua Min. Computer network routing survey[J], computer
        Journal, 2003, 26(6): 642-648.

   8.   Wu Jiang, HuiLing Zhao.  Next generation IP backbone network
        technology- Multi-protocol Label Switching [M], 2001, 21-41.

   9.   Brunilde Sanso, Andre Girard, Florent Mobiot.  Integrating
        reliability and quality of service in networks with swhiched
        virtual circuits [J], Computers and Operations Research, 2005,
        32(1): 35-58.

   10.  C Bouras, A Gkamas, A Karaliotas, et al.  Architecture and
        performance evaluation for redundant multicast transmission
        supporting adaptive QoS [J], Multimedia Tools and Applications,
        2005, 25(1): 85-110.

   11.  Brunilde Sanso, Andre Girard, Florent Mobiot.  Integrating
        reliability and quality of service in networks with swhiched
        virtual circuits [J], Computers and Operations Research, 2005,
        32(1): 35-58.




Wang, et al.              Expires May 21, 2010                 [Page 43]

Internet-Draft        Self-organizing network model        November 2009


   12.  Zhong Fan, E S Lee. Multiple QoS constrained routing with
        inaccurate state information [J], Electronics Letters, 1999, 35
        (21): 1807-1808.

   13.  Li Wang, ZengZhi Li, ChengQian Song and so on. a dynamic
        multicast routing algorithm[J].2004, 32(8): 1245-1247.

   14.  Ariza, E. Casilari, F. Sandoval.  QoS routing with outdated
        network knowledge [J], Electronics Letters, 2000, 36(15): 1332-
        1334.

   15.  Xavier Masip Bruin, Sergio Sanchez Lopez, Josep Sole Pareta, et
        al.  A QoS routing mechanism for reducing the routing inaccuracy
        effects [J], LNCS 2601, 2003: 90-102.

   16.  F P Kelly, A Maulloo, D Tan. Rate control for communication
        networks: Shadow prices, proportional fairness and stability
        [J], Operational Research Society, 1998, 49(3): 237-252.

   17.  Tadashi Nakano, Tatsuya Suda.  Applying biological principles to
        designs of network services[J].  Applied Soft Computing, 2006:
        1-9.





























Wang, et al.              Expires May 21, 2010                 [Page 44]

Internet-Draft        Self-organizing network model        November 2009


Authors' Addresses

   XingWei Wang
   Northeastern University
   No.11, Lane 3, WenHua Road, HePing District
   Shenyang, Liaoning, China  110004


   Phone:
   Email: wangxw@mail.neu.edu.cn
   URI:


   Yi XiuShuang
   Northeastern University


   Phone:
   Email: xsyi@mail.neu.edu.cn
   URI:


   Yu Wang
   Northeastern University


   Phone:
   Email: wangy@mail.neu.edu.cn
   URI:


   Ming Dong
   Northeastern University


   Phone:
   Email: dongm@mail.neu.edu.cn
   URI:


   Qiang Chen
   Northeastern University


   Phone:
   Email:
   URI:




Wang, et al.              Expires May 21, 2010                 [Page 45]