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]