Internet DRAFT - draft-xwwang-sonnetworkprotocol

draft-xwwang-sonnetworkprotocol






Network Working Group                                      XingWei. Wang
Internet-Draft                                              ZhanKao. Wen
Intended status: Standards Track                              WeiXin. Wu
Expires: May 21, 2010                                      WeiDong. Wang
                                                                 Yao. Fu
                                                                     NEU
                                                       November 17, 2009


                       Adaptive Routing Protocol
                 draft-xwwang-sonnetworkprotocol-02.txt

Abstract

   This document describes an Adaptive Routing Protocol.  It provides a
   routing protocol of Swarm Intelligence based network model, to a
   certain extent, this protocol can solve problems accompanied by
   network expansion and Dynamic network Increasing.  This paper
   presents a routing protocol to adapt the self-organizing network,
   defines a set of terms and describes the message format and
   appropriate action sequences.

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.

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

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the



Wang, et al.              Expires May 21, 2010                  [Page 1]

Internet-Draft          Adaptive Routing Protocol          November 2009


   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.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Term . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Motives and existent problems  . . . . . . . . . . . . . . . .  8
   5.  Related issues . . . . . . . . . . . . . . . . . . . . . . . . 10
     5.1.  Route information classification . . . . . . . . . . . . . 10
     5.2.  Routing strategy classification  . . . . . . . . . . . . . 11
   6.  Message format and function definition . . . . . . . . . . . . 13
     6.1.  OSPFv3 Routing Protocol expansion in the area  . . . . . . 13
     6.2.  BGP4+ Routing Protocol expansion outside the area  . . . . 15
     6.3.  Neighbor Information Table . . . . . . . . . . . . . . . . 18
   7.  Adaptive Unicast Routing Protocol  . . . . . . . . . . . . . . 20
     7.1.  Unicast Routing Table  . . . . . . . . . . . . . . . . . . 20
     7.2.  Protocol Action Sequence . . . . . . . . . . . . . . . . . 22
   8.  Adaptive Multicast Routing Protocol  . . . . . . . . . . . . . 24
     8.1.  Multicast Membership Management  . . . . . . . . . . . . . 24
     8.2.  Adaptive Multicast Routing . . . . . . . . . . . . . . . . 25
     8.3.  Bandwidth Allocation . . . . . . . . . . . . . . . . . . . 27
     8.4.  Multicast Member Joining and Leaving . . . . . . . . . . . 30
     8.5.  Multicast Routing Tree Establishment . . . . . . . . . . . 31
     8.6.  Multicast Member Leaving . . . . . . . . . . . . . . . . . 34
     8.7.  Multicast Routing Tree Reconstruction  . . . . . . . . . . 36
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 39
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 40
   11. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 41
   12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 42
     12.1. Normative References . . . . . . . . . . . . . . . . . . . 42
     12.2. Informative References . . . . . . . . . . . . . . . . . . 42
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 43







Wang, et al.              Expires May 21, 2010                  [Page 2]

Internet-Draft          Adaptive Routing Protocol          November 2009


1.  Introduction

   This document describes an Adaptive Routing Protocol.  It provides a
   routing protocol of Swarm Intelligence based network model, to a
   certain extent, this protocol can solve problems accompanied by
   network expansion and Dynamic network Increasing.  This paper
   presents a routing protocol to adapt the self-organizing network,
   defines a set of terms and describes the message format and
   appropriate action sequences.










































Wang, et al.              Expires May 21, 2010                  [Page 3]

Internet-Draft          Adaptive Routing Protocol          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
   [RFC2119].













































Wang, et al.              Expires May 21, 2010                  [Page 4]

Internet-Draft          Adaptive Routing Protocol          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.

   Autonomous System (AS)

      consisted of a group of routers exchanging routing information via
      a common routing protocol.

   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



Wang, et al.              Expires May 21, 2010                  [Page 5]

Internet-Draft          Adaptive Routing Protocol          November 2009


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

   Delay-Jitter

      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.

   Router ID



Wang, et al.              Expires May 21, 2010                  [Page 6]

Internet-Draft          Adaptive Routing Protocol          November 2009


      a 32-bit number assigned to each router running the corresponding
      protocol.  This number uniquely identifies the router within an
      autonomous System.

   Network

      an IPv4 or IPv6 network/subnet/supernet.  It is possible for one
      physical network to be assigned multiple IP network/subnet
      numbers.  These are considered to be separate networks.  Point-to-
      point physical networks are an exception - they are considered a
      single network no matter how many (if any at all) IP network/
      subnet numbers are assigned to them.

   Interface

      the connection between a router and one of its attached networks.
      An interface has state information associated with it, which is
      obtained from the underlying lower level protocols and the routing
      protocol itself.  An interface to a network has associated with it
      a single IP address and mask (unless the network is an unnumbered
      point-to-point network).  An interface is sometimes also referred
      to as a link.

   Neighboring routers

      two routers that have interfaces to a common network.  Neighbor
      relationships are maintained by, and usually dynamically
      discovered by, OSPF's Hello Protocol and BGP's Open Protocol.

   Next-Generation Internet

      involved with a number of projects intended to improve Internet
      performance and/or content quality in regions of various sizes and
      location.

















Wang, et al.              Expires May 21, 2010                  [Page 7]

Internet-Draft          Adaptive Routing Protocol          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          Adaptive Routing Protocol          November 2009


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

   Now, the complexity of the communications network has become an
   increasingly serious problem, the latest research of self-organizing
   system indicates that a solution to it can be found.  Self-organizing
   network is built up based on the characteristics and behaviors of
   self-organizing.  In this document, we will introduce adaptive
   routing protocols in self-organizing network.










































Wang, et al.              Expires May 21, 2010                  [Page 9]

Internet-Draft          Adaptive Routing Protocol          November 2009


5.  Related issues

   Routing is important in any network.  With expansion of network scale
   and emergence of multimedia and real-time services, user requirements
   on QoS (Quality of Service) become higher and higher, and QoS routing
   with various performance parameters considered is becoming an
   essential issue to be handled in self-organizing network.  Thus,
   adaptive routing protocols need to be developed to support QoS
   routing.

5.1.  Route information classification

   Network state refers to all the information related with the current
   network conditions.  Link state and distance vector algorithms all
   are based on network state when routing, and thus their performance
   is significantly dependent on its freshness and richness.  According
   to its storage location, it can be classified into three categories:
   local, global and aggregated state.

   1.  Local state

          It refers to information on conditions of a node and its
          directly connected links, such as their bandwidth, delay,
          delay jitter and error rate, etc.  It is basic information
          about network state.

   2.  Global state

          It refers to network-wide condition and often can be got by
          effectively combining local states of all nodes in the network
          in certain manner.

          With expanding of network scale, the global state information
          space is becoming explosive.  In general, even if for a node
          to collect and keep network global state is not completely
          impossible, it is very difficult due to huge time and space
          overhead.

   3.  Aggregation state

          In order to reduce the amount of network global state
          information and thus improve network scalability, the
          hierarchical network architecture is often adopted.  The
          internal status information of low-level sub-network is
          compressed and delivered to the high-level and aggregated
          there.  Such kind of compressed global state is called
          aggregated state.




Wang, et al.              Expires May 21, 2010                 [Page 10]

Internet-Draft          Adaptive Routing Protocol          November 2009


5.2.  Routing strategy classification

   Nodes collect appropriate network state information through
   interactions among them and then do routing under proper strategy.
   According to the type of state which a node maintains and the
   location where routing is carried out, routing strategies can be
   classified into three categories: source routing, distributed routing
   and hierarchical routing.

   1.  Source Routing

          Each source node collects and maintains complete global state.
          For sending packets, only source node calculates a feasible
          path from it to destination.  To establish a connection
          between them, it informs other nodes on the path of necessary
          routing information by control messages.  This routing
          strategy called source routing.

          Source routing concept and its algorithm are very simple.  It
          is easy to be realized and evaluated.  Centralized route
          computation at source node can avoid shortcomings existed in
          distributed routing, such as deadlock and loop caused by
          inconsistent network state data.  However, since each source
          node needs to collect and maintain the complete global state,
          source routing has the following problems:

          +  Maintenance overhead of global state is huge, because link
             state exchanging is needs.

          +  Time and storage overhead is huge, because routing is based
             on global state.

          +  Possibly obsolescent global state may lead to very bad
             routing performance.

          With network scale expansion, the above three problems become
          more prominent.  Taking network scalability into
          consideration, it is not practical to use source routing in
          large-scale QoS supported network.

   2.  Distributed Routing

          Each node collects and maintains a part of network state.
          When routing, multiple nodes in the network do route
          calculation independently based on its maintained state
          information, and then get a feasible route.





Wang, et al.              Expires May 21, 2010                 [Page 11]

Internet-Draft          Adaptive Routing Protocol          November 2009


          In distributed routing, each node does not know the complete
          feasible path, it just know its next hop node on the path,
          other parts on the path from the next hop node to the
          destination is calculated by the next hop node.  The current
          Internet routing strategy is distributed routing.  In
          distributed routing, calculations are distributed among all
          involved nodes with computation complexity reduced, even some
          algorithms only ask for local states, therefore it has good
          scalability.  However, distributed routing is more complex,
          especially it is very difficult to design good heuristics for
          multi-constrained QoS routing.  In addition, each node does
          routing independently based on its own maintained local
          information, this may cause loop generated on route due to
          inconsistent information, and thus additional loop detection
          algorithm is needed.

   3.  Hierarchical routing

          Hierarchical topology is formed through network node
          aggregation and each node needs to maintain aggregation state.
          To establish a connection, a source node sends control message
          along a feasible path.  When a border node receives the
          message as logic node representing the domain, it expands the
          feasible path via source routing, until passing through the
          domain.

          Hierarchical routing is used to solve scalability issue
          existed in source routing.  OSPF uses two-level routing
          structure with area introduced.  When routing, link state is
          used within the area, and distance vector is used between
          areas.  Comparing with source routing, it reduces the amount
          of information exchanged among nodes and their computation
          complexities, and thus has good scalability.  However,
          aggregated state may cause information loss, and then may have
          negative effect on QoS routing.

          In Self-organizing network, each node has its own local view
          and is equal to each other.  Their behaviors are coordinated
          through distributed algorithm.  The operation principles and
          mechanisms of OSPFv3 are very similar with self-organizing
          network's.  Thus, OSPFv3 protocol [RFC2328] is extended to
          achieve adaptive unicast routing protocols within the area.









Wang, et al.              Expires May 21, 2010                 [Page 12]

Internet-Draft          Adaptive Routing Protocol          November 2009


6.  Message format and function definition

6.1.  OSPFv3 Routing Protocol expansion in the area

   QoS state message format is shown in Fig 1:

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |          Group Id             |    Message Id |    Max Id     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                 Timestamp message sent                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Available bandwidth       |          Packet Loss          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |          Stability            |               0               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Interval Time |    Length     |          Checksum             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 1: QoS state message format

   Each field of QoS state message is defined as follows:

      Group id

         It is used to identify a group of QoS state messages.  Messages
         with the same group ID should be handled by the router in the
         same manner and messages with different group ID can not be
         handled simultaneously.  The average values of QoS parameters
         can be got by dealing with packets with the same group ID.

      Message Sequence Number

         It is used to indicate its order of a message in its group,
         numbered from 1 on.

      Maximum Message Sequence Number

         It is used to tell the largest message sequence number in a
         group.

      Timestamp message sent

         It is the specific time point when a message sent from a
         router.  It is measured in millisecond with January 1 1970, 00:
         00:00.000 GMT as benchmark.




Wang, et al.              Expires May 21, 2010                 [Page 13]

Internet-Draft          Adaptive Routing Protocol          November 2009


      Available bandwidth

         It specifies the available bandwidth of the interface where the
         message is sent.  It is filled in by the sending router based
         on its interface records.

      Packet Loss Rate

         It specifies the packet loss rate of the interface where the
         message is sent.  It is filled in by the sending router based
         on its interface records.

      Stability

         It specifies stability of sending node of this packet and is
         filled in by routing algorithm.

      Message interval time

         It specifies the time when the next packet will be sent.  A
         timer is set at its receiving router based on this value.  If
         timeout, the receiving router considers the packet is
         considered to be lost.

      Length

         It specifies the message length.

      Checksum

         It is used to check whether there are errors occurred in this
         message.

   When a router received a QoS state message, it uses the following
   method to calculate the specific QoS information of the link where
   the message came.

      Available Bandwidth

         Get directly from the corresponding field of QoS state message.

      Delay

         del(i)=(R(i)-S(i)-T(i))/2.R(i) is the receiving router time
         when it received the ith QoS state response message.  S(i) is
         the sending router time when it sent the ith QoS state message.
         T(i) is the time interval between the time when the receiving
         router received the ith QoS state message and the time when it



Wang, et al.              Expires May 21, 2010                 [Page 14]

Internet-Draft          Adaptive Routing Protocol          November 2009


         sent the ith QoS state response message.

      Delay jitter

         jt(i)=del(i)-del(i-1),del(i-1) is the delay of the (i-1)th QoS
         state message.

      Packet loss rate

         Get directly from the corresponding field of QoS state message.

      Bandwidth utilization

         bwu(jk)=(bw(tl)-bw(jk))/bw(tl),bw(tl) is total bandwidth of the
         link and get from the link interface record.

      Stability Degree

         Get directly from the corresponding field of QoS state message.

      After it has received all the QoS state message of the same group,
      the receiving router gets the bandwidth, delay, delay jitter,
      packet loss rate, stability degree and bandwidth utilization
      values from each received message and use their averages as the
      corresponding link QoS information.

6.2.  BGP4+ Routing Protocol expansion outside the area

   A new message, named as BGP_QoSstate message, is introduced with
   message type 5 in BGP4+ [RFC4760].  Just as KEEPALIVE message, a
   router running BGP4+ sends BGP_QoSstate message to its peers in its
   neighborhood periodically, inform them its link bandwidth and packet
   loss rate, measuring its land delay, delay jitter and system load.
   After these peers have received these BGP_QoSstate messages, they can
   get the link QoS information among them according to pre-defined
   calculation rules.  If a router doesn't support BGP_QoSstate message,
   it just ignore the message due to the unknown message type.
   BGP_QoSstate message format is shown in Fig 2:













Wang, et al.              Expires May 21, 2010                 [Page 15]

Internet-Draft          Adaptive Routing Protocol          November 2009


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       *                                                               *
       |                                                               |
       *                            Tag                                *
       |                                                               |
       *                                                               *
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |             Length            |    Type=5     |               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                   Message Sent Timestamp                      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Available bandwidth       |       Packet Loss Rate        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Stability Degree         |    Message Interval Time      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |          Checksum             |                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                   Figure 2: BGP_QoSstate message format

   Each field of BGP_QoSstate message is defined as follows:

      Tag

         It is 16 bytes long, used for security and synchronization
         detection,.

      Length

         It is 2 bytes long, specifying the length of this message.

      Type

         It is 1 byte long, specifying the type of this message.  Here,
         its type is set to be 5.

      Message sent timestamp

         It specifies the router time when this message was sent with
         January 1 1970, 00:00:00.000 GMT as reference point and
         millisecond as unit.






Wang, et al.              Expires May 21, 2010                 [Page 16]

Internet-Draft          Adaptive Routing Protocol          November 2009


      Available bandwidth

         It specifies the available bandwidth of the output interface
         when this message is sent by the router.  It is filled in by
         the sending router based on the interface record.

      Packet loss rate

         It specifies the packet loss rate of the output interface when
         this message is sent by the router.  It is filled in by the
         sending router based on the interface record.

      Stability Degree

         It specifies the stability degree of the sending node, filled
         by the routing algorithm.

      Message interval time

         It specifies the time when the next packet will be sent.  A
         timer is set at its receiving router based on this value.  If
         timeout, the receiving router considers the packet is
         considered to be lost.

      Checksum

         It is used to check whether there are errors occurred in this
         message.

   Similar to OSPF extension with a area, the peer router in the
   neighborhood uses the following method to calculate the specific QoS
   information of the link where the message came after it has received
   the BGP_QoSstate message.

      Available Bandwidth

         Get directly from the corresponding field of BGP_QoSstate
         message.

      Delay

         del(i)=(R(i)-S(i)-T(i))/2.R(i) is the receiving router time
         when it received the ith BGP_QoSstate response message.  S(i)
         is the sending router time when it sent the ith BGP_QoSstate
         message.  T(i) is the time interval between the time when the
         receiving router received the ith BGP_QoSstate message and the
         time when it sent the ith BGP_QoSstate response message.




Wang, et al.              Expires May 21, 2010                 [Page 17]

Internet-Draft          Adaptive Routing Protocol          November 2009


      Delay jitter

         jt(i)=del(i)-del(i-1),del(i-1) is the delay of the (i-1)th
         BGP_QoSstate message.

      Packet loss rate

         Get directly from the corresponding field of BGP_QoSstate
         message.

      Bandwidth utilization

         bwu(jk)=(bw(tl)-bw(jk))/bw(tl),bw(tl) is total bandwidth of the
         link and get from the link interface record.

      Stability Degree

         Get directly from the corresponding field of BGP_QoSstate
         message.

   After it has received the BGP_QoSstate message, the receiving router
   calculates the corresponding link QoS information, including the
   bandwidth, delay, delay jitter, packet loss rate, stability degree
   and bandwidth utilization.

6.3.  Neighbor Information Table

   After QoS routing information of intro-area and inter-area routing
   protocols is distributed and recorded, each node combines its
   received information from its neighboring nodes and forms a
   comprehensive neighborhood information table, providing information
   about each of its neighbor nodes, such as IP address (IA), interface
   name (IN), link bandwidth (BW), bandwidth utilization (BU), delay
   (DL), delay jitter (DJ )and packet loss rate (PL).

















Wang, et al.              Expires May 21, 2010                 [Page 18]

Internet-Draft          Adaptive Routing Protocol          November 2009


             | IPv6   IF    BW       BU       DL       DJ       PL
             |            Kbits/s    %        ms       ms       %
         ----+---------------------------------------------------------
          N1 | 1::2  eth0  48500      3        1        1        0
             |
          N2 | 2::1  eth1  46500      7        0        1        0
             |
          N3 | 3::1  eth2  45000      10       1        0        0
             |
          N4 | 4::1  eth3  40000      20       0        0        0
             |

                      Figure 3: Neighbor Information

   Here, all nodes are equal and each node only needs to know QoS
   routing information about its neighbor nodes no matter they are
   within the same area or not.  Routing algorithm generate the routing
   table based on the neighbor information table.

   Neighbor information table is generated and maintained by the
   extended OSPFv3 and BGP4+ jointly.  However, the extended BGP4+ is
   optional, it only needs to run on the AS border router.  The extended
   OSPFv3 and BGP4+ receives QoS state message in every QoS state
   message interval period, and neighbor node QoS information is
   calculated and saved with neighbor information table updated in real-
   time.  Therefore, neighbor information table is always up-to-date.

























Wang, et al.              Expires May 21, 2010                 [Page 19]

Internet-Draft          Adaptive Routing Protocol          November 2009


7.  Adaptive Unicast Routing Protocol

7.1.  Unicast Routing Table

   After routing information both inside and outside area is updated,
   each routing node use default routing algorithm to calculate the
   standard routes and generate standard route table based on its stored
   link state information.  At the same time, the extended routing
   protocols, which are bound with the distributed routing algorithm in
   self-organizing network, use QoS information in neighbor information
   table to calculate service-specific QoS routing and generate the
   extended routing table.  During this process, interactions only
   proceed among neighbor nodes.


       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Destination IP address         | Flag |Service type number|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Standard   | Next Hop Router Address (Standard)   | Interface |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |ServiceCode | Next Hop Router Address (Service 1)  | Interface |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Bandwidth (Service 1)    |       Delay (Service 1)       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    Delay Jitter (Service 1)   |  Packet Loss Rate (Service 1) |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  Stability Degree (Service 1) |BandwidthUtilization(Service 1)|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                              ...                              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |ServiceCode | Next Hop Router Address (Service n)  | Interface |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Bandwidth (Service n)    |       Delay (Service n)       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    Delay Jitter (Service n)   |  Packet Loss Rate (Service n) |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  Stability Degree (Service n) |BandwidthUtilization(Service n)|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

               Figure 4: Extended QoS unicast routing table

   Entries in the extended QoS unicast routing table are defined as
   follows:

      Destination IP Address

         It is 128 bits long.  It can be a host or sub-network address,
         which is determined by the Flag field in QoS unicast routing



Wang, et al.              Expires May 21, 2010                 [Page 20]

Internet-Draft          Adaptive Routing Protocol          November 2009


         table.

      Next Hop Router Address

         It is 128 bits long.  For direct forwarding, that is,
         destination address is local link, Next Hop Router Address is
         just message destination address.  For indirectly forwarding,
         Next Hop Router Address is just the address of the router which
         forwards the message next on route.

      Flag

         It is 4 bits long.  When the destination ip address field
         refers to a sub-network, it is set to 0; otherwise, it refers
         to a host and set to 1.

      Interface

         It is 8 bits long, specifying the corresponding router packet
         forwarding interface.

      Service Type Number

         It is 8 bits, specifying the amount of services the router
         supports.

      Standard Flag

         It is 8 bits long.  When its followed Next Hop Router Address
         is assigned by standard OSPFv3 routing protocol, it is set to
         1.

      Service Code

         It is 8 bits long, specifying its followed Next Hop Router
         Address is derived from its corresponding service type.

      Bandwidth, Delay, Delay Jitter, Packet Loss Rate, Bandwidth
      Utilization, Stability Degree

         They are all 16 bits long.  They specify the specific used
         bandwidth, delay, delay jitter, packet loss rate, bandwidth
         utilization, and stability degree from this router to the next
         hop router corresponding to the specific service.  Bandwidth
         unit is Kbps and time unit is ms.

   The above defined extended QoS unicast routing table is valid only
   for indirectly forwarding, that is, destination IP address field is



Wang, et al.              Expires May 21, 2010                 [Page 21]

Internet-Draft          Adaptive Routing Protocol          November 2009


   not local link.  For direct forwarding, it is just the same as OSPFv3
   routing table.

   When forwarding packet, the following procedure is used to do route
   searching:

   1.  Match destination address field in IPv6 message header with the
       destination IP address field in each entry of the routing table.
       If a entry with the same destination address is found, get Next
       Hop Router Address and Interface from the entry, go to step 3.

   2.  Search system routing table: if a matched entry is found, get the
       next hop router address and interface; otherwise, drop packet and
       go to step 5.

   3.  If the next hop router address and interface is corresponding to
       local link, do not forward packet and go to step 5.

   4.  Forward packet to the next hop router's interface.

   5.  Packet forwarding ends.

7.2.  Protocol Action Sequence

   The working procedure of the extended adaptive unicast routing
   protocol based on IPv6 is as follows:

   1.  A router in an AS sends QoS state messages to its neighbors to
       inform them of its available bandwidth, packet loss rate,
       stability degree with sending timestamp.

   2.  After it has received QoS state messages of the same group, a
       neighbor node calculates the averages of the message-carried
       available bandwidth, delay, delay jitter, packet loss rate,
       bandwidth utilization and stability degree, and then update its
       link state and neighbor information table.

   3.  If network state around the router has changed, the router
       updates its own protocol's link state database and its own
       neighbor information table, and sends a router LSA message to
       notify other routers in the same AS of the link state change.

   4.  Border gateway router receives UPDATE message sent by its
       neighboring peer and analyzes the extended MP_REACH_NLRI in it.
       Accord to the content of NLSI, it generates AS External LSA
       message, inform other routers in the AS of routing information.





Wang, et al.              Expires May 21, 2010                 [Page 22]

Internet-Draft          Adaptive Routing Protocol          November 2009


   5.  Border gateway router receives BGP_QoSstate message sent by its
       neighboring peer and sends a response message.  Meanwhile, it
       calculates link QoS.

   6.  Border gateway router updates neighbor information table
       according to the QoS information got in step 5.

   7.  Calculate standard default routing with OSPFv3's own unicast
       rouging algorithm; calculate QoS routing with the specific
       routing algorithm in self-organizing network, generate/ update
       the extended QoS unicast routing table.

   Protocol message action sequence is shown in Fig 4.


         __________       __________   |    __________       __________
        |          |     |  Border  |  |   |  Border  |     |          |
   Time |  Router  |     | Gateway  |  |   | Gateway  |     |  Router  |
    |   |__________|     |__Router__|  |   |__Router__|     |__________|
    |        |                |        |        |                 |
    |        |--------------->|        |        |---------------->|
    |Step1,2 |   QoS state    |        |        |   QoS state     |
    |        |<---------------|        |        |<----------------|
    |        |                |--------|------->|                 |
    | Step3  |                |  BGP_|QoSstate  |                 |
    |        |                |<-------|--------|                 |
    |        |                |        |        |                 |
    |        |                |        |        |                 |
    |        |                |        |        |                 |
    |        |                |--------|------->|                 |
    | Step4  |                |     BGP4+       |                 |
    |        |                |<-------|--------|                 |
    |        |                |        |        |                 |
    |        |--------------->|        |        |---------------->|
    | Step5  |   OSPFv3       |        |        |    OSPFv3       |
    |        |<---------------|        |        |<----------------|
    |        |                |        |        |                 |
    |        |                |        |        |                 |
    |        |                |        |        |                 |

                Figure 5: Protocol message action sequence










Wang, et al.              Expires May 21, 2010                 [Page 23]

Internet-Draft          Adaptive Routing Protocol          November 2009


8.  Adaptive Multicast Routing Protocol

8.1.  Multicast Membership Management

   A multicast member can use MLDv2 (Multicast Listener Discovery v2)
   protocol [RFC3810] to notify routers of which multicast group it want
   to join or leave and which source it want to receive from or reject
   packets from.  It must be able to set up a multicast channel,
   including multicast source and multicast group address.  A IPv6
   router uses MLDv2 to discover those multicast listeners in its
   directly connected links, and get its interested multicast
   address.MLDv2 allows its user to designate a multicast channel
   address, including both multicast source and multicast group.  It
   also allows source filtering, that it, it allows a user to express
   from which source the user wants to receive or reject.  In order to
   support adaptive QoS multicast, a multicast member needs to provide
   information about Service Type.  Thus, when a multicast member uses a
   MLDv2 sending multicast listener report message to notify routers of
   which group he wants to join, it is also necessary for him to report
   multicast service type.  The extended MLDv2 message format is defined
   as follows:

   Format of the extended MLDv2 message

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    Type       |     Code      |            Checksum           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Max Response Delay        |         Service Type          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Multicast Address                         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 6: Format of the extended MLDv2 message

      Type

         It is used to differentiate MLDv2 message type.  There are
         three different types of MLD messages.  If it is a Multicast
         Listener Query message used by a multicast router to query
         multicast members' state, its type is set to be 130; if it is a
         Multicast Listener Report message used by a multicast member to
         report its joining in a multicast group, its type is set to be
         131; if it is a Multicast Listener Done message used by a
         multicast member to report its leaving a multicast group, its
         type is set to be 132.




Wang, et al.              Expires May 21, 2010                 [Page 24]

Internet-Draft          Adaptive Routing Protocol          November 2009


      Maximum Response Delay

         It is only valid in Multicast Listener Query message.  A host
         must issue a multicast membership report message before the
         Maximum Response Delay is exhausted.

      Service Type

         It specifies the service type corresponding to a multicast
         routing request.

      Multicast Address

         For a general multicast address query, it is set to be 0; for a
         specific multicast address query, it is set to multicast
         address to be queried; In Multicast Listener Report or
         Multicast Listener Done message, it is set to the multicast
         address to be joined in or left respectively.

   In order to keep compatible with standard MLDv2 protocol, the
   Reserved field in standard MLDv2 message format is used as the
   Service Type field in the extended MLDv2.  If a multicast member does
   not support these new types of services, this field is set to be 0.
   When it receives such a message, a router just handle the message as
   a standard MLDv2 one.

8.2.  Adaptive Multicast Routing

   PIM-SSM query the unicast routing table based on the multicast source
   address and multicast address in the received MLDv2 message, and send
   multicast joining message to neighbor node along .  Then, this
   message is forwarded hop by hop until reaches the source.  At this
   time, the shortest path tree is established.  PIM-SSM is the variant
   of PIM-SM to support source specific multicast.  It builds the
   shortest path tree with multicast source as its root by the shortest
   path tree algorithm.  It also provides dynamic management and
   maintenance of multicast tree.  PIM-SSM is based on unicast routing.
   The IPv6-based adaptive unicast routing protocol in section 3.1 is
   used when extending PIM-SSM.

   In PIM-SSM protocol, Message Type field is used to specify the
   message with 0 to indicate "hello" message and 1 "Join/Prune"
   message.  When a SSM router receives a MLDv2 message sent by a
   multicast member with a directly connected link, it will query the
   unicast routing table with the multicast source address in the
   message as destination IP address, and regards the found next hop
   routing interface as the upstream RPF interface, then a PIM-SMM
   joining message is sent to the upstream neighbor router from this



Wang, et al.              Expires May 21, 2010                 [Page 25]

Internet-Draft          Adaptive Routing Protocol          November 2009


   interface.  After this joining message is received, the upstream
   router creates a status entry belonging to the multicast and forward
   this message.  This message is forwarded hop by hop until reaches a
   router in the multicast.  If there are no longer any multicast member
   directly connected with a SSM router, a PIM-SSM pruning message is
   sent to the upstream neighbor router from the RPF interface.  After
   the pruning message is received, the upstream router deletes the
   corresponding multicast status entry and no longer forward any
   message belonging to the multicast from the corresponding interface.

   PIM-SSM protocol combines the contents of the joining and pruning
   messages and makes them into two different fields in the same message
   which can be empty.  In order to build a multicast routing tree with
   specific service QoS requirement met, the extended PIM-SSM "Join/
   Prune" message format is defined as follows.  Here, when service type
   field is 1, it specifies a join message; when it is 2, it specifies a
   prune one.


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Ver |  Type | Service Type  |            Checksum           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              Upstream Neighbor Unicast Address                |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 7: PIM-SSM Join/Prune message format

   When a router receives a Multicast Listener Report message sent by a
   multicast member, it uses the extended MLDv2 protocol to get the
   Service Type of the Multicast and deliver it to PIM-SSM protocol.
   PIM-SSM queries QoS Unicast Routing Table based on the Service Type
   to find its upstream neighbor unicast address and RPF interface.
   Then, a corresponding multicast table entry is created in the router
   and a PIM-SSM Join message is sent to its upstream neighbor.  It is
   the same as the extended MLDv2 protocol, the reserved field in the
   standard PIM-SSM Join/Prune message is used as Service Type one,
   telling the multicast service type in the join message.  The upstream
   router can query the corresponding routing table entry based on the
   service type in its received PIM-SSM Join/Prune message.  If there
   are no entries corresponding to the type of service in the unicast
   routing table, the standard unicast routing table is used to find the
   upstream neighbor unicast address.







Wang, et al.              Expires May 21, 2010                 [Page 26]

Internet-Draft          Adaptive Routing Protocol          November 2009


8.3.  Bandwidth Allocation

   By extending MLDv2 and PIM-SSM protocol to support service
   adaptation, a multicast tree with service QoS requirement met can be
   built in the premise that the adaptive unicast routing exists.  The
   above needs to extend RSVP protocol to provide bandwidth requirement
   information.

   RSVP is not a routing protocol, however, it can run together with
   multicast routing protocol and get routing information through local
   routing database.  When multicasting, members send MLDv2 message to
   join in multicast at first, and then send RSVP messages to get
   bandwidth along multicast packet transmission path.  It is routing
   protocol to decide where a packet go, however, RSVP is only concerned
   about if a packet can get satisfied QoS along its transmission path.
   As a large multicast group is often dynamic and thus its generated
   multicast tree topology is usually changeable, RSVP can adjust its
   state and do flow control dynamically along its traversed routers and
   hosts.  RSVP send refresh message along the path regularly to keep
   resource reservation state in the router and host up-to-date.

   There are two different kinds of bandwidth requirements for multicast
   members, one is dataflow requirement at different layer level in the
   layered multicast, another is bandwidth requirement interval.

   1.  When layered multicast is used, a router needs to record dataflow
       layer level to be forwarded on each of its multicast forwarding
       interface.  It uses RSVP based adaptive layered multicast
       mechanism described in the next section.

   2.  When bandwidth requirement interval is used, a router needs to
       set a number of different forwarding queues in its forwarding
       interfaces.  Each forwarding queue has different bandwidth and
       forwarding priority.  The greater the bandwidth, the higher the
       priority and then the better the QoS.  A router allocates
       bandwidth and set priority for each queue based on the downstream
       multicast member bandwidth requirement and the downstream link
       status.  At each queue for the same type of service, different
       sub-queues can be set up corresponding to different multicast
       session with different bandwidth and priority.  If the residual
       bandwidth of a queue is not sufficient, several multicast session
       can share bandwidth if their application natures allow.

   RSVP protocol [RFC2210] includes 7 kinds of messages and 15 common
   objects [RFC2211] and their formats are shown in Fig.7 and 8
   respectively.  Each object has a unique Class-Num and its C-Types is
   used to specify its used protocol family.  When IPv4 used, C-Types is
   set to be 1; when IPv6 used, it is set to 3.



Wang, et al.              Expires May 21, 2010                 [Page 27]

Internet-Draft          Adaptive Routing Protocol          November 2009


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Version     |   Flag      |        Message Type           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        RSVP Checksum                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            TTL                |             Reserved          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                         RSVP Length                           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 8: RSVP message header


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |          Length               |    Type       |   C-Type      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                      Object Content...                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 9: RSVP object header

   RSVP protocol messages include RSVP_PATH, RSVP_RESV, RSVP_PATHERR,
   RSVP_RESVERR, RSVP_PATHEAR, RSVP_RESVTEAR, and RSVP_RESVCONF.  RSVP
   objects include session, rsvp_hop, integrity, time_values,
   error_spec, scope,style, flowspec, filter_spec, sender_template,
   sender_tspec, adspec, policy_data and resv_confirm.  To support
   layered multicast and flow control, new control objects are added to
   standard RSVP protocol.

   Data_description object is added to RSVP_PATH message.  When it is
   used to describe the layer number and the encoding scheme under the
   layered encoding scheme, the object number is 200.  When it is used
   to describe the maximum bandwidth a service can apply under flow
   control scheme, the object number is 200.













Wang, et al.              Expires May 21, 2010                 [Page 28]

Internet-Draft          Adaptive Routing Protocol          November 2009


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  Ver  |  Resv |             Object Length                     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      The layer number to be reserved (No. 200)                |
       |       Bandwidth to be reserved (No.201)                       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            Encoding Scheme Description (No: 200)              |
       |                     invalid (No: 201)                         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 10: RSVP data_description object format

   Resv_description object is added to RSVP_RESV message.  When it is
   used to describe the lower and upper bound of the layer number to be
   reserved by destination host under the layered encoding scheme, the
   object number is 200.  When it is used to describe the bandwidth
   interval a service can apply under flow control scheme, the object
   number is 203.  Resv_description object format is defined as follows.


        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  Ver  |  Resv |             Object Length                     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  The lower bound of the layer number to be reserved (No: 202) |
       |  The lower bound of the bandwidth to be reserved (No: 203)    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  The upper bound of the layer number to be reserved (No: 202) |
       |  The upper bound of the bandwidth to be reserved (No: 203)    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 11: RSVP resv_description object format

   The above two objects are not standard RSVP defined ones, thus their
   numbers are defined as 200-203.  According to RSVP, if a object has a
   number with its top two bits as 11, its state is guaranteed to be
   kept at any intermediate router, and during refresh period the
   message will be transferred.

   Standard RSVP protocol use sender_tspec and flowspec object to
   transfer source and destination information.  Here, sender_tspec
   object number is in RSVP_PATH message with value12.  It specifies
   dataflow characteristics generated by sender.  Flowspec object number
   is in RSVP_RESV with value 9.  It specifies QoS required by
   application.  Because two defferent control scheme are used when



Wang, et al.              Expires May 21, 2010                 [Page 29]

Internet-Draft          Adaptive Routing Protocol          November 2009


   newly added objects are defined, any traversed router should be
   informed of which scheme is actually used at this time when a source
   sends a RSVP_PATH message or a destination receives a RSVP_RESV
   message.  Therefore, ender_tspec and flowspec object in standard RSVP
   protocol are extended.

   The standard reserved field in sender_tspec is used with 14 bits
   occupied by route announcement information and the other 2 bits as
   flags F. F field is used to specify bandwidth allocation type: if F
   is 0, it indicates that neither layered multicast nor flow control is
   supported and thus this object is just ignored by the router; if F is
   1, it indicates that layered multicast is supported; if F is 2, it
   indicates that Flow Control is supported.

   The standard reserved field in flowspec is used with 14 bits to
   describe bandwidth allocation information and the other 2 bits as
   flags F. F field has the same meaning as sender_tspec's.

8.4.  Multicast Member Joining and Leaving

   Based on link state, each routing node gets information on its direct
   connected links such as transmission delay and available bandwidth
   through link state routing Protocol.  It tries to find the QoS
   constrained point-to-point shortest path based on Dijkstra Algorithm.
   In addition, a node can get the current multicast source address
   through SAP protocol [ref9], who requests to join in the multicast.
   The procedure is described as follows:

   1.  Node joining process

       1.  A request node sends a ReqBid message to multicast source
           along the shortest path to it.

       2.  When a node receives a ReqBid message, if it is not on the
           tree, it just forwards it; otherwise, it replies a Bid
           message to the request node and becomes a response node.
           Then, it set TTL in ReqBid message to be 2 and spread it.

       3.  When a node receives a spread ReqBid message, if it is a
           response node, it just drops the message; otherwise, it
           replies a Bid message to the request node along the shortest
           path and becomes a response node with TTL in the ReqBid
           message decreased by 1, if TTL in the ReqBid message is still
           greater than 0, the node will spread the ReqBid message
           further.

       4.  Application needed QoS information is collected in the Bid
           message along its way.  When the request node receives the



Wang, et al.              Expires May 21, 2010                 [Page 30]

Internet-Draft          Adaptive Routing Protocol          November 2009


           first Bid message, it set up a waiting timer which is 4 times
           of link average delay.  When the timer timeouts, the Request
           Node chooses the best one with both QoS requirement met and
           minimum pricing offered from all its received Bid message,
           and then sends a Joining message to the response node which
           sent that best Bid message.

       5.  The multicast status is set at the traversed node by the
           joining message.  The tree node, which has received the Join
           message, begins to forward the multicast data to the request
           node.  In order to avoid generating loop and reduce
           duplicated Bid message, when a tree node receives Bid
           messages from other tree nodes, it just drops them.  If the
           node itself is not a Response Node, it becomes such a
           Response Node and send a new Bid message to the Request Node.
           It has been proven that this can lead to a multicast tree
           without any loop.  If there are several such Response Node,
           the best one is chosen, which is the most suitable to the
           specific service QoS requirement [ref8].

   2.  Node leaving process

       1.  If a node has child nodes in the multicast tree, it just
           cancel its receiving state.

       2.  If a node has no child node in the multicast tree, it sends
           Prune message towards the multicast source.

       3.  The node which received the Prune message from its child node
           stops forwarding data to this child node.  If it still has
           other child nodes in the multicast tree, the end; otherwise,
           goto step 4.

       4.  If node is a multicast receiver or the multicast source, the
           end; otherwise, it sends the Prune message towards the
           source, goto step 3.

8.5.  Multicast Routing Tree Establishment

   After the establishment of the multicast routing tree, Bandwidth
   Request is communicated with RSVP message and the actually allocated
   bandwidth is determined by gaming analysis.  How to establish a
   multicast tree is described as follows:

   1.   The multicast source communicates with multicast members through
        SAP (Session Announcement Protocol) to get information about
        this multicast session.




Wang, et al.              Expires May 21, 2010                 [Page 31]

Internet-Draft          Adaptive Routing Protocol          November 2009


   2.   Multicast members send MLDv2 Multicast Listener Query message to
        their directly connected router according to Service Type and
        Multicast Address.

   3.   These directly connected routers generate PIM-SSM Join messages
        based on the multicast session information in Multicast Listener
        Query messages.  Then, they query Unicast Routing Table and
        forward PIM-SSM Join message to their upstream neighbor router
        from RPF interfaces.

   4.   These routers generate new PIM-SSM Join messages based on their
        received PIM-SSM Join messages.  Then, they query Unicast
        Routing Table and send newly generated PIM-SSM Join messages
        from RPF interfaces.  All intermediate routers repeat this step,
        until PIM-SSM Join messages reach that router which is directly
        connected with multicast source.

   5.   The router which is directly connected with multicast source
        sends a ICMPv6 message to inform this of Multicast Source.

   6.   The Multicast Source fills data_description object and generates
        RSVP_PATH message, then sends it as multicast data.

   7.   All routers in the multicast tree modify the data_description
        object in their received RSVP_PATH message according to their
        downstream link state.

   8.   After Multicast Members have received RSVP_PATH messages, they
        choose control scheme.  Then, they fill resv_description objects
        according to data_description objects in the received RSVP_PATH
        messages, generate RSVP_RESV messages and send them to the
        directly connected routers.

   9.   After received RSVP_RESV messages, multicast tree routers get
        Control Scheme type.  If Control Scheme is Flow Control, goto
        step 10; otherwise, assign the forwarded flow layer on the
        multicast forwarding interface: if assignment failed,
        RSVP_RESVERR message is sent to the multicast member, joining
        failed; otherwise, resource reservations are merged and new
        RSVP_RESV messages are generated and sent to the upstream
        routers.

   10.  The actually allocated bandwidth are determined through gaming
        analysis [ref10], and the corresponding Forwarding Queues and
        Filters are set up on multicast forwarding interface based on
        source address, multicast address and service type, then
        bandwidth is allocated: if allocation failed, RSVP_RESVERR
        messages are sent to multicast members, joining failed;



Wang, et al.              Expires May 21, 2010                 [Page 32]

Internet-Draft          Adaptive Routing Protocol          November 2009


        otherwise, resource reservations are merged and new RSVP_RESV
        messages are generated and sent to the upstream routers.

   11.  If the Multicast Source received RSVP_RESV message, it sends a
        RSVP_RESVCONF message to confirm allocation success.  The
        multicast member joining succeeds.

   Each multicast member can do the above procedure independently and
   simultaneously.  With new branches grafted to the tree constantly, a
   multicast tree is built dynamically.  Apparently, steps 1-4
   correspond to tree building and step 6-11 correspond to gaming
   analysis and bandwidth allocation.  The message interaction sequence
   is shown in Fig. 11.






































Wang, et al.              Expires May 21, 2010                 [Page 33]

Internet-Draft          Adaptive Routing Protocol          November 2009


          __________       __________       __________       __________
         |          |     |          |     |Multicast |     |          |
    Time |Multicast |     |  Router  |     |  Direct  |     |Multicast |
     |   |__Member__|     |__________|     |__Router__|     |__Source__|
     |        |                |                |                 |
     |        |                |  Send SAP      |                 |
     | Step 1 |<---------------|----------------|-----------------|
     |        | Send MLDv2     |                |                 |
     |        | Query Message  |                |                 |
     | Step 2 |--------------->|                |                 |
     |        |                | Send PIM-SSM   |                 |
     |        |                | Join Message   |                 |
     |Step 3,4|                |--------------->|                 |
     |        |                |                |                 |
     |        |                |                |  Send ICMPv6    |
     | Step 5 |                |                |---------------->|
     |        |                |                |  Send RSVP_PATH |
     | Step 6 |                |                |<----------------|
     |        | Modify resv_description object  |                 |
     |        |        send RSVP_PATH           |                 |
     | Step 7 |<---------------|----------------|                 |
     |        |                |                |                 |
     |        | Send RSVP_RESV |                |                 |
     | Step 8 |--------------->|                |                 |
     |        |                |  Send RSVP_RESV|                 |
     | Step 9 |                |----------------|---------------->|
     |        |    Send RSVP_RESVERR            |                 |
     |        |<---------------|----------------|                 |
     |        |                |    Send RSVP_RESV                |
     | Step 10|                |----------------|---------------->|
     |        |     Send RSVP_RESVERR           |                 |
     |        |<---------------|----------------|                 |
     |        |                |                |                 |
     |        |                | Send RSVP_RESVCONF               |
     | Step 11|<---------------|----------------|-----------------|
     |        |                |                |                 |

              Figure 12: Multicast routing tree establishment

8.6.  Multicast Member Leaving

   A member leaves a multicast by sending a PIM-SSM Prune message to its
   upstream node.  It is described as follows:

   1.  A Multicast Member sends a MLDv2 Multicast Listener Done message
       to it Directly Connected Router to announce its desire to leaving
       the multicast.




Wang, et al.              Expires May 21, 2010                 [Page 34]

Internet-Draft          Adaptive Routing Protocol          November 2009


   2.  The router removes the multicast member record based on the
       source and the multicast address in MLDv2 message and checks if
       there are other members with the same multicast address.  If so,
       go to step 6, otherwise removes corresponding routing table
       entry.

   3.  If the router is directly connected with the Multicast Source,
       goto step 6.

   4.  The router checks if it has downstream neighbors: if so, go to
       step 6; otherwise, query multicast routing table and send a PIM-
       SSM Prune message to its upstream neighbor router and then delete
       the corresponding routing table entry.

   5.  Goto step 3.

   6.  Multicast Member leaving is over.

   When deleting the corresponding downstream neighbor information in
   routing table entry, what to be done is based on Control Type.  If
   Control Type is Layered Multicast, the corresponding information is
   deleted directly; otherwise, the corresponding multicast information
   is deleted only after the corresponding Forwarding Queue and Filter
   are deleted.

   The message interaction sequence in multicast member leaving
   procedure is shown in Fig. 12.
























Wang, et al.              Expires May 21, 2010                 [Page 35]

Internet-Draft          Adaptive Routing Protocol          November 2009


          __________       __________       __________       __________
         |          |     |          |     |          |     |Multicast |
    Time |Multicast |     |  Router  |     |  Router  |     |  Direct  |
     |   |__Member__|     |__________|     |__________|     |__Router__|
     |        |                |                |                 |
     |        | Send MLDv2     |                |                 |
     |        |  Done message  |                |                 |
     | Step 1 |--------------->|                |                 |
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                | Send PIM-SSM   |                 |
     |        |                |  Prune message |                 |
     | Step 2 |                |--------------->|                 |
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |                | Send PIM-SSM    |
     |        |                |                |  Prune message  |
     |Step 3-6|                |                |---------------->|
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |                |                 |

      Figure 13: The message interaction sequence in multicast member
                             leaving procedure

8.7.  Multicast Routing Tree Reconstruction

   With network topology and route changes, some paths in a QoS
   Multicast Tree may become invalid at the same time some new paths
   need to be grafted to the tree, multicast tree reconstruction and
   rerouting is necessary.  Rerouting needs the following two steps: one
   is to find a new path for the multicast member and merged into the
   tree, another is to delete no longer useful branch in the tree.  The
   following procedure is used to realize multicast tree construction.

   Each PIM-SSM router maintains a timer.  When the timer timeouts, the
   router queries its Unicast Routing Table to find its upstream
   neighbor address and send a PIM-SSM Join message to this neighbor.
   If network topology or unicast route changes, a new upstream neighbor
   is chosen adaptively and joins into the tree hop by hop through PIM-
   SSM.  At the same time, enough bandwidth is allocated along the new
   path through periodical refreshment of RSVP message.  The above
   procedure is described as follows.

   1.  When the timer timeouts, the router queries its Unicast Routing
       Table to find its upstream neighbor address, and then generates a
       PIM-SSM Join message and sends it to the upstream neighbor.




Wang, et al.              Expires May 21, 2010                 [Page 36]

Internet-Draft          Adaptive Routing Protocol          November 2009


   2.  The router generates a new PIM-SSM Join message based on its
       received PIM-SSM Join message.  Then, it queries its Unicast
       Routing Table and send the newly generated PIM-SSM Join message
       to its upstream router from RPF interface.  All intermediate
       routers repeat this step until the PIM-SSM Join message reaches a
       router in the tree.

   3.  A Multicast Member refreshes RSVP_RESV message and sends the
       message to its directly connected router.

   4.  After received RSVP_RESV message, a multicast tree router gets
       Control Scheme type.  If Control Scheme is Flow Control, goto
       step 5; otherwise, assign the forwarded flow layer on the
       multicast forwarding interface: if assignment failed,
       RSVP_RESVERR message is sent to the multicast member, joining
       failed; otherwise, resource reservations are merged and new
       RSVP_RESV messages are generated and sent to the upstream
       routers.

   5.  The actually allocated bandwidth are determined through gaming
       analysis, and the corresponding Forwarding Queue and Filter are
       set up on multicast forwarding interface based on source address,
       multicast address and service type, then bandwidth is allocated:
       if allocation failed, a RSVP_RESVERR message is sent to the
       multicast member, joining failed; otherwise, resource
       reservations are merged and a new RSVP_RESV message is generated
       and sent to the upstream router.

   6.  If the Multicast Source received RSVP_RESV message, it sends a
       RSVP_RESVCONF message to confirm allocation success.  The
       multicast member re-joins into the tree successfully.

   Each PIM-SSM router maintains a downstream neighbor timeout timer.
   If the PIM-SSM message is not received until the timer timeouts, the
   following procedure is used to prune no longer useful path in the
   tree.

   1.  Delete the corresponding information about the downstream
       neighbor in the routing table entry and decreases the downstream
       neighbor number by 1.

   2.  If the downstream neighbor number becomes 0, a PIM-SSM Prune
       message is sent to the upstream neighbor router.  Then, the
       upstream neighbor router prunes the corresponding branch in the
       multicast routing tree.

   The message interaction sequence when reconstructing a multicast tree
   is depicted in the following figure.



Wang, et al.              Expires May 21, 2010                 [Page 37]

Internet-Draft          Adaptive Routing Protocol          November 2009


          __________       __________       __________       __________
         |          |     |          |     |Multicast |     |          |
    Time |Multicast |     |  Router  |     |  Tree    |     |Multicast |
     |   |__Member__|     |__________|     |__Router__|     |__Source__|
     |        |                |  Send PIM-SSM  |                 |
     |        |                |  Join Message  |                 |
     |Step 1,2|                |--------------->|                 |
     |        |Refresh RSVP_RESV                |                 |
     | Step 3 |--------------->|                |                 |
     |        |                | Send RSVP_RESV |                 |
     |        |                |----------------|--------------->|
     | Step 4 |                |                |                 |
     |        |   Send RSVP_RESVERR             |                 |
     |        |<---------------|----------------|                 |
     |        |                |                |                 |
     |        |                |   Send RSVP_RESV                 |
     | Step 5 |                |----------------|---------------->|
     |        |                |                |                 |
     |        |   Send RSVP_RESVERR             |                 |
     |        |<---------------|----------------|                 |
     |        |                |                |                 |
     |        |                |Send RSVP_RESVCONF                |
     | Step 6 |<---------------|----------------|-----------------|
     |        |                |                |                 |
     |        |                |                |                 |
     |--------|----------------|----------------|-----------------|
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |  Send PIM-SSM  |                 |
     |Step 1,2|                | Prune Message  |                 |
     |        |                |--------------->|                 |
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |                |                 |
     |        |                |                |                 |

     Figure 14: The message interaction sequence when reconstructing a
                        multicast tree is depicted












Wang, et al.              Expires May 21, 2010                 [Page 38]

Internet-Draft          Adaptive Routing Protocol          November 2009


9.  Security Considerations

   Adaptive Routing Protocol is based on OSPFv3 and BGP4+, so it also
   inherited their security.  All protocol exchanges are authenticated.
   Cryptographic authentication of OSPFv3 and BGP4+ is believed to be
   secure against passive attacks and provide significant protection
   against active attacks.  When using the Cryptographic authentication
   option, each router appends a "message digest" to its transmitted
   packets.  Receivers then use the shared secret key and received
   digest to verify that each received packet is authentic.

   The quality of the security provided by the cryptographic
   authentication option depends completely on the strentth of the
   message digest algorithm , the strentth of the key being used, and
   the corrent implementation of the security mechanism in all
   communication adaptive routing implementations.  It also requires
   that all parties maintain the secrecy of the shared secret key.

   None of the authentication types provide confidentiality.  Nor do
   then protect against traffic analysis.































Wang, et al.              Expires May 21, 2010                 [Page 39]

Internet-Draft          Adaptive Routing Protocol          November 2009


10.  IANA Considerations

   This document has no actions for IANA.
















































Wang, et al.              Expires May 21, 2010                 [Page 40]

Internet-Draft          Adaptive Routing Protocol          November 2009


11.  Acknowledgments

   The author would like to thank XiuShuang Yi, Yu Wang, Ming Dong, Jun
   Liu, DengKe Zhang, Jian Wu, XiaoLei Huang, XiaoFeng Liu, Qiang Chen,
   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 41]

Internet-Draft          Adaptive Routing Protocol          November 2009


12.  References

12.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2210]  Wroclawski, J., "The Use of RSVP with IETF Integrated
              Services", RFC 2210, September 1997.

   [RFC2211]  Wroclawski, J., "Specification of the Controlled-Load
              Network Element Service", RFC 2211, September 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC3810]  Vida, R. and L. Costa, "Multicast Listener Discovery
              Version 2 (MLDv2) for IPv6", RFC 3810, June 2004.

   [RFC4271]  Rekhter, Y., Li, T., and S. Hares, "A Border Gateway
              Protocol 4 (BGP-4)", RFC 4271, January 2006.

   [RFC4760]  Bates, T., Chandra, R., Katz, D., and Y. Rekhter,
              "Multiprotocol Extensions for BGP-4", RFC 4760,
              January 2007.

12.2.  Informative References

   [ref10]    Shi, Xiquan., "Game Theory", 2000.

   [ref11]    Chen, Shangbing., Zhao, Jun., He, XiaoYan., and JiXin.
              Qian, "A QoS-aware Dynamic Multicast Routing Algorithm
              with Topology Adaptation", 9 2002.

   [ref8]     M, Faloutsos., "QoSMIC: Quality of Service Sensitive
              Multicast Internet Protocol", 09 1998.

   [ref9]     Kocarev, Ljupco, and Vattay, "Complex Dynamics in
              Communication Networks", 2005.













Wang, et al.              Expires May 21, 2010                 [Page 42]

Internet-Draft          Adaptive Routing Protocol          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:


   ZhanKao Wen
   Northeastern University


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


   WeiXin Wu
   Northeastern University


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


   WeiDong Wang
   Northeastern University


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


   Yao Fu
   Northeastern University


   Phone:
   Email:
   URI:




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