Network Working Group XingWei. Wang Internet-Draft ZhanKao. Wen Intended status: Standards Track WeiXin. Wu Expires: June 4, 2009 WeiDong. Wang Yao. Fu NEU December 2008 Adaptive Routing Protocol draft-xwwang-sonnetworkprotocol-00.txt 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 June 4, 2009. Copyright Notice Copyright (c) 2008 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Wang, et al. Expires June 4, 2009 [Page 1] Internet-Draft Adaptive Routing Protocol December 2008 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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Definitions of commonly used terms . . . . . . . . . . . . . . 5 4. Motives and existent problems . . . . . . . . . . . . . . . . 7 5. Related issues . . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Route information classification . . . . . . . . . . . . . 9 5.2. Routing strategy classification . . . . . . . . . . . . . 10 6. Message format and function definition . . . . . . . . . . . . 12 6.1. OSPFv3 Routing Protocol expansion in the area . . . . . . 12 6.2. BGP4+ Routing Protocol expansion outside the area . . . . 14 6.3. Designing of Neighbor Information Table . . . . . . . . . 17 7. Unicast Adaptive Routing Protocol . . . . . . . . . . . . . . 19 7.1. Designing of Unicast routing table . . . . . . . . . . . . 19 7.2. The protocol action sequence . . . . . . . . . . . . . . . 21 8. Adaptive Multicast Routing Protocol . . . . . . . . . . . . . 23 8.1. Management of Multicast Members . . . . . . . . . . . . . 23 8.2. Service adaptive unicast routing . . . . . . . . . . . . . 24 8.3. Bandwidth allocation . . . . . . . . . . . . . . . . . . . 25 8.4. Multicast member joining and removing . . . . . . . . . . 28 8.5. Establishment of Multicast Routing Tree . . . . . . . . . 30 8.6. The Multicast Member leaving . . . . . . . . . . . . . . . 32 8.7. Reconstruction of Multicast Routing Tree . . . . . . . . . 34 9. Security Considerations . . . . . . . . . . . . . . . . . . . 37 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 39 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 40 12.1. Normative References . . . . . . . . . . . . . . . . . . . 40 12.2. Informative References . . . . . . . . . . . . . . . . . . 40 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 41 Wang, et al. Expires June 4, 2009 [Page 2] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 3] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 4] Internet-Draft Adaptive Routing Protocol December 2008 3. Definitions of commonly used terms This section provides definitions for terms that have a specific meaning to the Adaptive Routing Protocol and that are used throughout the text. Router A level three Internet Protocol packet switch. Formerly called a gateway in much of the IP literature. Autonomous System A group of routers exchanging routing information via a common routing protocol. Abbreviated as AS. Router ID A 32-bit number assigned to each router running the corresponding protocol. This number uniquely identifies the router within an Autonomous System. Network In this memo, an IPv4 or IPv6 network/subnet/supernet. It is possible for one physical network to be assigned multiple IP network/subnet numbers. We consider these 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. Swarm Intelligence Wang, et al. Expires June 4, 2009 [Page 5] Internet-Draft Adaptive Routing Protocol December 2008 Swarm intelligence (SI) is artificial intelligence based on the collective behavior of decentralized, self-organized systems. Next-Generation Internet Next Generation Internet refers to a number of projects intended to improve Internet performance and/or content quality in regions of various sizes and location. Wang, et al. Expires June 4, 2009 [Page 6] Internet-Draft Adaptive Routing Protocol December 2008 4. Motives and existent problems As network expansion and dynamic network increasing, it is a challenge to the existing network model and routing mechanism. The expanding of the network needs strong self-organizing and self- management capabilities. Dynamic network also needs a distributed and adaptive routing mechanism, where a node does not need to manage the global network information. With the combination of various technologies, especially mobile, wireless and high bandwidth internet access enter homes, and numbers of mobile terminals, sensors in companies, the Internet scale expands continually. Now, the Internet has been applied all over the body, individual, family, transport and broader. All of these have increased the time and space complexity of network topology, also increased network dynamic complexity. At the same time, burden of network administrators and users increased. In order to alleviate burden on users and administrators, make them extricated from complex network configuration, a self-organizing network need to be designed and developed, as far as possible to minimize members' involvement. Self-organizing phenomenon is prevalent in our lives. In the natural world, fish have a good organization into a structure of the group around, ants can find the shortest path to the food, and all of these are good examples of self-organizing behavior. In the act of self- organizing phenomena, all of the entities establish a organizational structure which does not need a coordination center. Instead, these entities interact changed directly and constantly reacting to the local environment. Self-organizing is not just distributed localized control, it is a result of independent entity's relationship, structure and function. In the self-organizing systems, simple entity's acting in the micro- level can reach to the entire system's complex acting. This phenomenon known as the "emerging." Another important characteristic of Self-organizing system is the adaptation to system environment changing. In fact, these entities have been in a constant implicit way to adapt to the changing. For example, the self-organizing system often re-restructuring as reaction triggering to the internal and external changing. By doing so, it towards a desired useful structure and avoid to other structures. Combining the self-organizing inherent adaptive and distributed properties is robustness towards failure and damaging. There is no single point of failure in the system, and the damage can be repaired in the system without outside helping. Therefore, self-organizing system will not collapse suddenly, it just downgraded slowly when it Wang, et al. Expires June 4, 2009 [Page 7] Internet-Draft Adaptive Routing Protocol December 2008 has problems. Now, the complexity of the communications network has become an increasingly serious problem, the latest research of self-organizing system indicates that a solution can be found. Self-organizing network model is based on the building up characteristics and behaviors of self-organizing. In this paper, we will introduce a routing protocol to adapt the self-organizing network. Wang, et al. Expires June 4, 2009 [Page 8] Internet-Draft Adaptive Routing Protocol December 2008 5. Related issues Routing is the main problem in the network environment. With the continuous expansion of internet scale, emerging of multimedia services and real-time operations, the QoS need is improved unceasingly. QoS routing based on various performance parameters is the key issues in any network model. In the self-organizing network environment, the solution to the QoS- based routing problem is using Routing algorithm and Routing Strategy based on Swarm Intelligence. 5.1. Route information classification Network status information means all the information refers to the current network. It is not only the origin information linking state algorithm relies on, but also the basis of the distance vector algorithm. Therefore, when calculating a viable path, Routing Performance is closely with the present network condition. According to the physical location of networking status, it can be divided into three categories: Local state, Global state and Aggregation state. 1. Local state Local state means the information about a node or a link that connected directly. The Local state is the base of other link states, it include transmission delay, delay jitter, available bandwidth, packet Loss. 2. Global state With the expanding of the network scale, The Global state information becoming explosive. Global state means the combination of the entire network node's local state. It is impossible for a node to keep the global state and calculation feasible path. 3. Aggregation state In order to reduce the information of Global state and improve scalability, we use hierarchical network structure, it compresses the information gathered from low-level network and spread to high-level. In this process, the compressed information of global state called aggregation state. Wang, et al. Expires June 4, 2009 [Page 9] Internet-Draft Adaptive Routing Protocol December 2008 5.2. Routing strategy classification Through routing interaction, each node collects the appropriate network state information and uses corresponding routing strategy. According to the type of information each node maintained and destination of routing, routing strategies can be divided into Source Routing, Distributed Routing and Hierarchical routing. 1. Source Routing Each source node collects and maintains the complete Global state. Before the packet send, only the source node calculates a viable path from the source node to the target node. To establish a connection, the source node informs the other nodes on the path about how to routing by control message. This routing strategy called source routing. Source routing algorithm and the concept is very simple, easy to implement and evaluate. Source node's centralized calculation can avoid kinds of shortcomings of distributed calculation, such as inconsistent data in each node may cause the deadlock and the loop. However, since each source node needs to collect and maintain the whole Global state, the source routing has the following problems: + As the source routing needs link state interactive, the overhead of maintaining Global state is large. + Source node calculates a viable path by Global state, so the overhead of time and space is large. + The obsolescence of Global state source node maintained cause a great affection to routing performance. With the expansion of the network scale, these three issues become more prominent. Take the scalability into consideration, it is not feasible to use source routing in the large-scale and QoS supported network. 2. Distributed Routing Each source node collects and maintains certain network state information. A number of nodes in the network do distributed calculation independently based on this information, in order to find a viable path. This routing strategy called Distributed Routing. Wang, et al. Expires June 4, 2009 [Page 10] Internet-Draft Adaptive Routing Protocol December 2008 In Distributed Routing, each node does not know the full viable path, it just know the viable path to the next hop node. The further viable path from next hop to the destination is calculated by next hop. The current Internet routing strategy is Distributed Routing. Distributed Routing spreads calculations into all nodes, reduces the complexity of the calculations, and even some algorithm only require locale state, therefore it has good scalability. However, distributed processing is more complex, especially in the multi-QoS bound difficult to design a good heuristic. In addition, each node calculates a viable path depend on the local information independently, it may be cause loop since inconsistent information, which requires additional loop detection algorithm. 3. Hierarchical routing Network nodes together through the aggregation of multi-level topology, each node preserve the state of aggregation. To establish a connection, the source node sends control message along the viable path, when a group border node receives the message as a group's logic node representing the group, it expand the viable path use source routing, until passing through the group. This routing strategy called Hierarchical Routing. Hierarchical routing is to solve source routing scalability issue. OSPF protocol achieved two-layer routing structure through regional agreements (Area), using link state within the region and distance vector between regions. Comparing to source routing, hierarchical routing reduces the information nodes interacted and the computational complexity, has a good scalability. However, information gathered led to the loss of state, it cause a great negative affection to QoS routing. In Self-organizing network, each node has its partial view, the equal status of all nodes, network nodes through the distributed algorithm to coordinate each other's behavior, and the working principle and mechanism of OSPFv3 are very similar with self-organizing network Characteristics , so we expand the OSPFv3 protocol [RFC2328], achieve self-adaptive unicast routing protocols within the region. Wang, et al. Expires June 4, 2009 [Page 11] Internet-Draft Adaptive Routing Protocol December 2008 6. Message format and function definition 6.1. OSPFv3 Routing Protocol expansion in the area QoS state message format: 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Available bandwidth | Packet Loss | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Stability | 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interval Time | Length | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1 The field of QoS state message is defined as follows: Group id Router can deal with the packets with the same group number; can not deal with packets with different group number. Router get an average of QoS information by calculate the packets with same group number. Message id Message id is the sequence number of packet, from the beginning of 1. Message max id Message max id is the largest number in a group. Timestamp of packet send It specifies the number of milliseconds since January 1 1970, 00:00:00.000 GMT. Available bandwidth Wang, et al. Expires June 4, 2009 [Page 12] Internet-Draft Adaptive Routing Protocol December 2008 It specifies Available bandwidth of sending interface. It is filled by the router based on the interface record. Packet Loss It specifies Packet Loss of sending interface. It is filled by the router based on the interface record. Stability It specifies stability of sending node, filled by routing algorithm. Message interval time It specifies the time next packet will be send. Router set a timer depends on this value. If times up, router consider that packet is lost. Length It specifies The length of the message. Checksum This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. When router receive QoS state message, it use the following method calculate QoS information. Bandwidth Read directly from Bandwidth field of QoS state message. Delay del(i)=(R(i)-S(i)-T(i))/2.R(i) is router time when it receive the ith QoS state response message. S(i) is router time when it send the ith QoS state message. T(i) is the other router time between it receive the ith QoS state message and send the ith QoS state response message. Wang, et al. Expires June 4, 2009 [Page 13] Internet-Draft Adaptive Routing Protocol December 2008 Delay jitter jt(i)=del(i)-del(i-1),del(i) is the delay of the ith QoS state message. Packet Loss Read directly from Packet Loss field of QoS state message. Bandwidth utilization bwu(jk)=(bw(tl)-bw(jk))/bw(tl),bw(tl) is total bandwidth, can get from interface data. Stability Read directly from Stability field of QoS state message. After router receive all the QoS state message in the same group, on the basis of each packet, it calculates bandwidth, delay, delay jitter and packet loss rate, stability, bandwidth utilization, and calculates average as a corresponding link QoS information. 6.2. BGP4+ Routing Protocol expansion outside the area We design a new message format: BGP_QoSstate message, packet type is 5.Just like KEEPALIVE message in BGP4+ [RFC4760], BGP_QoSstate message sends to router's neighbors periodically, inform bandwidth, packet loss, delay, delay jitter and system load status to it's neighbors. When a neighbors receive a BGP_QoSstate message, it calculate it's BGP neighbor routers' QoS information according to the pre-set algorithm. If router doesn't support BGP_QoSstate packet, it ignore this type of packet. Wang, et al. Expires June 4, 2009 [Page 14] Internet-Draft Adaptive Routing Protocol December 2008 BGP_QoSstate 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | * * | | * Tag * | | * * | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | Type=5 | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Timestamp | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Available bandwidth | Packet Loss | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Stability | Interval Time | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2 The field of BGP_QoSstate message is defined as follows Tag It is used for security detection and synchronization detection, 16 bytes. Length It specifies the length of BGP packet, 2 bytes Type It specifies the type of message, 1 byte, BGP_QoSstate message type is 5. Timestamp of packet send It specifies the number of milliseconds since January 1 1970, 00:00:00.000 GMT. Wang, et al. Expires June 4, 2009 [Page 15] Internet-Draft Adaptive Routing Protocol December 2008 Available bandwidth It specifies available bandwidth of sending interface. It is filled by the router based on the interface record. Packet Loss It specifies Packet Loss of sending interface. It is filled by the router based on the interface record. Stability It specifies Stability of sending node, filled by routing algorithm. Packet interval time It specifies the time next packet will be send. Router set a timer depends on this value. If times up, router consider that packet is lost. Checksum This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. When router receive BGP_QoSstate message, it use the following method calculate QoS information. Bandwidth Read directly from Bandwidth field of BGP_QoSstate message. Delay del(i)=(R(i)-S(i)-T(i))/2.R(i) is router time when it receive the ith BGP_QoSstate response message. S(i) is router time when it send the ith BGP_QoSstate message. T(i) is the other router time between it receive the ith BGP_QoSstate message and send the ith BGP_QoSstate response message. Delay jitter jt(i)=del(i)-del(i-1),del(i) is the delay of the ith BGP_QoSstate message. Wang, et al. Expires June 4, 2009 [Page 16] Internet-Draft Adaptive Routing Protocol December 2008 Packet Loss Read directly from Packet Loss field of BGP_QoSstate message. Bandwidth utilization bwu(jk)=(bw(tl)-bw(jk))/bw(tl),bw(tl) is total bandwidth, can get from interface data. Stability Read directly from Stability field BGP_QoSstate message. After router receive all the BGP_QoSstate messages in the same group, on the basis of each packet, it calculates bandwidth, delay, delay jitter and packet loss rate, stability, bandwidth utilization, and calculates average as a corresponding link QoS information. 6.3. Designing of Neighbor Information Table When a node receives QoS state in area and BGP_QoSstate between area, it combine all neighbors' QoS information to a Neighbor Information Table, it include all neighbors' router ip address, interface name, link bandwidth, bandwidth utilization, delay, delay jitter, packet loss rate. Neighbor Information Table: | 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 This designing has been put aside current concept about area and outside area, comply with self-organizing network design features. Each network node has equal status, and only the QoS routing information of connected neighbors, regardless of neighbors in area or neighbors outside area. Routing algorithm generate routing tables by calculating neighbors adjacent nodes' QoS information based on Wang, et al. Expires June 4, 2009 [Page 17] Internet-Draft Adaptive Routing Protocol December 2008 Neighbor Information Table. Neighbor Information Table need to Co-generate and maintain with expanding of OSPFv3 and BGP4+, and BGP4+ is optional, only running on the AS border router. The expanding protocol receives QoS state message in every QoS state interval time, calculate and save neighbors' QoS information, and updates Neighbor Information Table in real-time. Neighbor Information Table is always up-to-date. Wang, et al. Expires June 4, 2009 [Page 18] Internet-Draft Adaptive Routing Protocol December 2008 7. Unicast Adaptive Routing Protocol 7.1. Designing of Unicast routing table After information updating from inner area and outside area, each router node use the default routing algorithm to calculate the standard route table. At the same time, extension routing algorithm use QoS information in the Neighbor Information Table to calculate QoS routing for the extension routing table. The definition of QoS unicast routing table is as follows +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination address | Flag |Service type number| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Standard | Next Hop Router(Standard) | Interface | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |ServiceCode | Next Hop Router(Service 1) | Interface | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bandwidth (Service 1) | Delay (Service 1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Delay Jitter (Service 1) | Packet Loss (Service 1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Stability (Service 1) | Bandwidth Usage (Service 1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |ServiceCode | Next Hop Router(Service n) | Interface | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bandwidth (Service n) | Delay (Service n) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Delay Jitter (Service n) | Packet Loss (Service n) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Stability (Service n) | Bandwidth Usage (Service n) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4 Destination Address 128 bits. It can be a complete host address or a network address, which is depended on Flag field in Unicast routing table. Next Hop Router 128 bits. For direct forwarding, Next Hop Router is the destination address of the message. For indirectly forwarding, Wang, et al. Expires June 4, 2009 [Page 19] Internet-Draft Adaptive Routing Protocol December 2008 Next Hop Router is the address of router who will forward the packet next. Flag 4 bits. When the destination ip address is a network address this field is set to 0, otherwise set to 1. Interface 8 bits. It is corresponding to the router forwarding interface. Service Type Number 8 bits. It specifies the service number router support. Standard Flag 8 bits. When the followed Next Hop Router Address is generated by standard OSPFv3 routing protocols, Standard Flag field is set to 1. Service Code 8 bits. It specifies the followed Next Hop Router Address is generated corresponding to the Service Code. Bandwidth, Delay, Delay Jitter, Packet Loss Rate, Bandwidth Utilization, Stability they are all 16 bits. They specify values of Bandwidth, Delay, Delay Jitter, Packet Loss Rate, Bandwidth Utilization, and Stability from router to next router. The unit of Bandwidth is Kbps. The unit of Delay and Delay Jitter is ms. The Unicast Routing Table we defined is effective only to indirectly forwarding (the destination address is not a local link address).In the direct forwarding environment, The Unicast Routing Table is the same as OSPFv3 routing table. In the packet forwarding process, router uses the following algorithm to find the corresponding routing item. 1. Search the Unicast routing table to match the Destination Address filed in the IPv6 header. If found, router gets Next Hop Router and Interface from Unicast routing table, then goto step 3. Wang, et al. Expires June 4, 2009 [Page 20] Internet-Draft Adaptive Routing Protocol December 2008 2. If not found match routing, then search the system routing table, if found, get next hop router and interface from system routing table, otherwise drop the packet. 3. If next hop router or interface is a local address, the router will not forward the packets, goto step 5. 4. Forward packet according to next hop router and interface. 5. Packet forwarding process end. 7.2. The protocol action sequence The process of IPv6 adaptive unicast extending routing is as follows: 1. The router in the area sends QoS state message to its neighbors to inform Bandwidth, Packet Loss Rate, Stability and Timestamp. 2. The neighbor receives QoS state message. It calculates average bandwidth, delay, delay jitter, packet loss rate, bandwidth utilization and stability, and then updates linking state database and neighbor information table. 3. If the state around the router changed, the router updates linking state database and neighbor information table, and sends router LSA message to inform other router in the area. 4. The Border Gateway router receives UPDATE message sending by Neighborhood Peer, analysis the expansion MP_REACH_NLRI in the message and sends AS-External-LSA to inform other routers in the area. 5. The Border Gateway router receives BGP_QoSstate message sending by Neighborhood Peer and sends response message. Meanwhile, it calculates the QoS of the path. 6. The Border Gateway router updates neighbor information table through the QoS information. 7. The router calculate stander default routing by OSPFv3 unicast rouging algorithm, and calculates QoS routing to update the extending unicast routing table by routing algorithm of Self- organizing network. Wang, et al. Expires June 4, 2009 [Page 21] Internet-Draft Adaptive Routing Protocol December 2008 Action sequence of QoS unicast routing protocol __________ __________ | __________ __________ | | | 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 Wang, et al. Expires June 4, 2009 [Page 22] Internet-Draft Adaptive Routing Protocol December 2008 8. Adaptive Multicast Routing Protocol 8.1. Management of Multicast Members Multicast member use MLDv2(Multicast Listener Discovery v2) protocol [RFC3810] to notify router it will join or leave a multicast group, and want to receive or reject packets from specific source. Multicast member must be able to set up a multicast channel, include multicast source and multicast group.IPv6 router use MLDv2 on the direct link to find multicast listener ,and get interesting multicast address.MLDv2 protocol support designated multicast channel address(multicast source and multicast group) and source filter. To achieve adaptive multicast QoS, multicast members need to provide information about Service Type. format of the expansion MLDv2 protocol 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6 Type There are three types of MLD messages: Multicast Listener Query (Type = decimal 130) Multicast Listener Queries are sent by multicast routers in Querier State to query the multicast listening state of neighboring. Multicast Listener Report (Type = decimal 131) Multicast Listener Reports are sent by IP nodes to report (to neighboring routers) the current multicast listening state, or changes in the multicast listening state, of their interfaces. Wang, et al. Expires June 4, 2009 [Page 23] Internet-Draft Adaptive Routing Protocol December 2008 Multicast Listener Done (Type = decimal 132) When a node ceases to listen to a multicast address on an interface, it SHOULD send a single Done message to the link- scope all-routers multicast address (FF02::2), carrying in its Multicast Address field the address to which it is ceasing to listen. Maximum Response Delay The Maximum Response Delay field specifies the maximum time allowed before sending a responding Report Service Type The Service Type specifies the service type code of multicast request messages. Multicast Address For a General Query, the Multicast Address field is set to zero. For a Multicast Address Specific Query, it is set to the multicast address being queried. For Multicast Listener Report or Multicast Listener Done message, it is set to the multicast address being joining or leaving. In order to compatibility with standard MLDv2 protocol, we use Reserved field for Service Type. If the router doesn't support Service Type, it will initialized to zero by the sender and ignored by receivers. 8.2. Service adaptive unicast routing PIM-SSM uses the PIM-SM functionality to create an SPT between the receiver and the source, but builds the SPT without the help of an RP. In a PIM SSM-configured network, a host subscribes to an SSM channel, announcing a desire to join group G and source S. The directly connected PIM sparse-mode router, the receiver's DR, sends an (S,G) join message to its RPF neighbor for the source. The (S,G) Join message initiates the source tree, then builds it out hop by hop until it reaches the source. Then using the source tree, multicast traffic is delivered to the subscribing host. We use Unicast Adaptive Routing Protocol to expansion PIM-SSM protocol. In PIM-SSM protocol, Service Type field specify the type of sending message. This field is set to 0 when sending a "hello" message, or set to 1 when sending a Join/Prune message. The PIM-SSM protocol integrate Join message and Prune message as two fields can be blank Wang, et al. Expires June 4, 2009 [Page 24] Internet-Draft Adaptive Routing Protocol December 2008 in one message. For establishment of a suitable multicast routing tree for Service Type and in premise of QoS requirement, we expand the standard PIM-SSM protocol, add "Join/Prune" message. PIM-SSM Join/Prune message format 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unicast Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7 When router receive Multicast Listener Report message sending by Multicast Member, it use Expanding MLDv2 protocol to get Service Type of Multicast Group and deliver it to PIM-SSM protocol. PIM-SSM search QoS Unicast Routing Table based on the Service Type, find RPF neighbor and interface, establish corresponding multicast table entry, and send PIM-SSM Join message to the RPF neighbor. As the same to expanding MLDv2 protocol, we expand standards PIM-SSM Join/ Prune message, set the reserved filed as Service Type. Upstream routers receive PIM-SSM Join/Prune message, find corresponding routing entry. If not find, it use standards unicast routing table to find RPF neighbor. 8.3. Bandwidth allocation Throughout the adaptive expanding to MLDv2 and PIM-SSM protocol, on the premise of adaptive unicast routing, we can create a multicast tree to meet service type needs. We expand the RSVP protocol to support Bandwidth information. RSVP is not a routing protocol, it can work together with multicast routing protocol, and get routing information through local routing database. In multicast process, members send MLDv2 packet to join a Multicast Group, and then send RSVP packet in the multicast packet transmission path to allocate bandwidth. Routing protocol decides the packet transmission, and RSVP only concerned about if the packet got satisfied QoS when packet transmission. As the multicast group and multicast tree topology it generated is dynamic and often changed, RSVP can adjust RSVP state and flow control state dynamically. RSVP send refresh message along the path regularly to keep the RSVP state of router or host. There are two bandwidth demands for multicast members, first is data Wang, et al. Expires June 4, 2009 [Page 25] Internet-Draft Adaptive Routing Protocol December 2008 flow demand in the process of Layered Multicast, second is Bandwidth Requirements Range. 1. In Layered Multicast, router should record data level on each forwarding port; use RSVP based adaptive Layered Multicast mechanism. 2. In Bandwidth Requirements Range, router should create a number of Forwarding Queue. Each Forwarding Queue has a different queue bandwidth and forwarding priority. The greater Bandwidth, the higher the priority, and the better the QoS. Router settings available bandwidth and priority for Forwarding Queue based on the bandwidth needs and link information of downstream multicast members. To Forwarding Queues for the same Service Type, can be set up different Sub Forwarding Queues according to different Multicast Group, and allocate various bandwidth and priority. If bandwidth of Service Type Forwarding Queue is insufficient, many multicast group can share the same Forwarding Queue. RSVP protocol [RFC2210] includes 7 kinds of messages and 15 common objects [RFC2211]. Each object has a unique Class-Num. C-Types are defined for the two Internet address families IPv4 and IPv6.When in ipv4 network, it is set to 1, and set to 2 in ipv6. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Flag | Message Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RSVP Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TTL | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RSVP Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8 Wang, et al. Expires June 4, 2009 [Page 26] Internet-Draft Adaptive Routing Protocol December 2008 RSVP object 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 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. In support of Layered Multicast and Flow Control, we add new objects to standard RSVP protocol. We add data_description object to RSVP_PATH message for Description of number of Layered Encoding Layer and Encoding Scheme. The object number is 200.And object number is 201 for description of the largest bandwidth service can be applied for when using Flow Control Scheme. RSVP data_description object format 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Layer can be applied for (No: 200) | | Bandwidth can be applied for (No:201) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Scheme Description (No: 200) | | Field invalid (No: 201) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 10 We add resv_description object to RSVP_RESV message for description of layers upper and lower limits. The object number is 202.And object number is 203 for description of the Bandwidth Requirements Range. Wang, et al. Expires June 4, 2009 [Page 27] Internet-Draft Adaptive Routing Protocol December 2008 RSVP resv_description object format 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Minimum level (No: 202) | | Minimum Bandwidth (No:203) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Maximum level (No: 202) | | Maximum Bandwidth (No:203) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 11 Standard RSVP protocol use sender_tspec object and flowspec object to transfer source and destination information. Sender_tspec object number is 12, specify the sender's transmission characteristics, included in RSVP_PATH message. Flowspec object number is 9, specifies the QoS application required for, included in RSVP_RESV. As the new defined object use two types of control scheme, router should be informed which scheme to use when receiving RSVP_PATH message and RSVP_RESV message. So, we expand standard RSVP protocol sender_tspec and flowspec object. We use reserved field of sender_tspec, route announces information occupy 14 bits, the last 2 bits is Flag field. Flag field depend on Bandwidth allocation type,0 means router doesn't support Layered Multicast and Flow Control, then ignore the object,1 means support Layered Multicast,2 means support Flow Control. Use Reserved field of sender_tspec, bandwidth allocation information occupy 14 bits, the last 2 bits is Flag field. The value of Flag field is as followers:0 means doesn't support Layered Multicast and Flow Control, then ignore the object,1 means support Layered Multicast,2 means support Flow Control. 8.4. Multicast member joining and removing Each network node know direct connected link information about transmission delay, the remaining available bandwidth through Link State Routing Protocol, and find the shortest path from peer to peer through QoS information. Each node can get the current multicast source address through SAP protocol [ref9]. 1. The process of node joining Wang, et al. Expires June 4, 2009 [Page 28] Internet-Draft Adaptive Routing Protocol December 2008 1. The Request Node send ReqBid packet to the source through the shortest path. 2. When the node along the way receive ReqBid packet, if the node is not a tree node, it forwards packet according to the original path. Otherwise, it responses Bid packet to the request node and becomes a response node, then change the ReqBid packet TTL to 2 and spread the ReqBid packet. 3. When a node receive spreading ReqBid packet, it drops the packet if it has became a Response Node. Otherwise, it responses Bid packet to the request node and becomes a Response Node, then reduce the ReqBid packet TTL by 1.If ReqBid packet TTL still greater than 0, the node will spread the ReqBid packet further. 4. The Bid packet collect QoS information of application needed along the way. When the Request Node receive first Bid packet, it set up a timer whose value is 4 times of the link Average Delay. When times up, the Request Node chooses a best one (meets the QoS demands and has the minimum price) from all the receiving Bid packet, then sends Join packet to the node who sending the best Bid packet. 5. The tree node who receiving the Join packet begins to forward multicast data. In order to avoid loop and duplication Bid packet, the tree node drops Bid packet from others tree node. If node is not a Response Node, it becomes Response Node, and send new Bid packet to the Request Node. When there are multiple Response Point, the node will chose a best one according to service QoS demands [ref8]. 2. The process of node leaving 1. If a node has child nodes in the multicast tree, it just cancel the receiving state. 2. If a node has no child nodes in the multicast tree, it send Prune packet to the source direction. 3. The node receiving Prune packet from child node will cancel forwarding data to the child. If the node still has nodes in other multicast tree, the process is done. Otherwise goto step 4. 4. If node is the multicast source or a multicast receiver, the process is done. Otherwise, the node sends Prune packet to the source direction, then goto step 3. Wang, et al. Expires June 4, 2009 [Page 29] Internet-Draft Adaptive Routing Protocol December 2008 8.5. Establishment of Multicast Routing Tree After the establishment of Multicast Routing Tree, node sends RSVP message to transfer Bandwidth Request. The process of establishment is as follows: 1. The multicast source gets information from multicast members through SAP (Session Announcement Protocol). 2. Multicast members send MLDv2 Multicast Listener Query message to Direct Connect Router according to Service Type and Multicast Address. 3. The Direct Connect Routers search Unicast Routing Table based on the group information in Multicast Listener Query message, find RPF neighbor and interface, and send PIM-SSM Join message to the RPF neighbor. 4. Router who received PIM-SSM Join message sends new PIM-SSM Join message to the RPF router through Unicast Routing Table. All the middle routers have to repeat this step until The Multicast Source Direct Connect Router received PIM-SSM Join message. 5. The Multicast Source Direct Connect Router sends ICMPv6 message to inform Multicast Source. 6. The Multicast Source fills RSVP_PATH message with data_description object, and sends it. 7. All Multicast Tree routers modify the data_description object according to downstream link information when receiving RSVP_PATH packet. 8. Multicast Member selects control scheme, fills RSVP_RESV message packet with resv_description object and sends it to Direct Connect Router. 9. After the Multicast Tree routers received the RSVP_RESV message, a decision should be made based on type of Control Scheme. If Control Scheme is Flow Control, goto step 10, otherwise, allocate Forward Level on the multicast forwarding interface. If the allocating failed, the router sends RSVP_RESVERR message to all multicast member, otherwise mergers reserved resources and sends new RSVP_RESV message to the upstream router. 10. Multicast Tree routers compute actual allocating bandwidth through game analysis method [ref10], and set up Forwarding Queue and Filter on the forwarding interface according to Wang, et al. Expires June 4, 2009 [Page 30] Internet-Draft Adaptive Routing Protocol December 2008 source, group address and service type, then allocate bandwidth. If the allocation failed, the router sends RSVP_RESVERR message to all multicast member, otherwise mergers reserved resources and sends new RSVP_RESV message to the upstream router. 11. The Multicast Source sends RSVP_RESVCONF message to confirm allocation success after receiving RSVP_RESV message. The joining process of multicast member success. Wang, et al. Expires June 4, 2009 [Page 31] Internet-Draft Adaptive Routing Protocol December 2008 Establishment of multicast routing tree __________ __________ __________ __________ | | | | |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 8.6. The Multicast Member leaving The member leaves Multicast Group through sending PIM-SSM Prune message to upstream node. 1. Multicast Member sends MLDv2 Multicast Listener Done message to Direct Connect Router, announce it will leaving the group. Wang, et al. Expires June 4, 2009 [Page 32] Internet-Draft Adaptive Routing Protocol December 2008 2. The router removes multicast member record with designated source and group address in MLDv2 message, and checks if there are other members with the same group address. If so, goto step 6, otherwise removes corresponding routing entry. 3. If the router is The Multicast Source Direct Connect Router, goto step 6. 4. Router checks if there is downstream neighbors, if so goto step 6, otherwise sends PIM-SSM Prune message to upstream router neighbors and delete corresponding routing entry. 5. Goto step 3. 6. The process of Multicast Member leaving ended. It should judge Control Type when deleting corresponding routing entry of downstream neighbors. If Control Type is Layered Multicast, the router delete corresponding information directly, otherwise delete corresponding multicast information after revoking corresponding Forwarding Queue and Filter. Wang, et al. Expires June 4, 2009 [Page 33] Internet-Draft Adaptive Routing Protocol December 2008 Multicast member leaving process __________ __________ __________ __________ | | | | | | |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 8.7. Reconstruction of Multicast Routing Tree As the network topology and routing changing [ref11] can cause some established path in QoS Multicast Tree is not available, and new path needs to be added in QoS Multicast Tree, so the Re-routing is needed. There are two steps to carry out Re-routing:1.Adding a new path into QoS Multicast Tree. 2. Removing original path which is not available. Use the following method to achieve multicast routing tree reconstruction. Each PIM-SSM router keeps a timer, it searches Unicast Routing Table to find upstream neighbor address and sends PIM-SSM Join message to upstream neighbor when times up. If network topology or routing changes, the protocol will chose a new upstream neighbor adaptively, and joins QoS Multicast Tree through PIM-SSM hop by hop. At the same time, the new bandwidth will be allocated through refreshing of RSVP message. The process is described as follows. Wang, et al. Expires June 4, 2009 [Page 34] Internet-Draft Adaptive Routing Protocol December 2008 1. When times up, the router searches Unicast Routing Table to find upstream neighbor address and sends PIM-SSM Join message to upstream neighbor. 2. Router who received PIM-SSM Join message sends new PIM-SSM Join message to the RPF router through Unicast Routing Table. All the middle routers have to repeat this step until router in The Multicast Routing Tree received PIM-SSM Join message. 3. Multicast Member refreshes RSVP_RESV message, sends it to Direct Router. 4. After the Multicast Tree routers received the RSVP_RESV message ,a decision should be made based on type of Control Scheme. If Control Scheme is Flow Control, goto step 5, otherwise, allocate Forward Level on the multicast forwarding interface. If the allocating failed, the router sends RSVP_RESVERR message to all multicast member, otherwise mergers reserved resources and sends new RSVP_RESV message to the upstream router. 5. Multicast Tree routers compute actual allocating bandwidth through game analysis method, and set up Forwarding Queue and Filter on the forwarding interface according to source, group address and service type, then allocate bandwidth. If the allocation failed, the router sends RSVP_RESVERR message to all multicast member, otherwise mergers reserved resources and sends new RSVP_RESV message to the upstream router. 6. The Multicast Source sends RSVP_RESVCONF message to confirm allocation success after receiving RSVP_RESV message. The re- joining of multicast member success. Each PIM-SSM router keeps a downstream neighbor overtime timer, it use the following method to prune not available path when times up. 1. Removes corresponding routing information about downstream neighbor, reduces the number of downstream neighbors by 1. 2. If the number of downstream neighbors is 0,the router send PIM- SSM Prune message to upstream neighbor router. Then upstream neighbor router prune corresponding nodes in The Multicast Routing Tree. Wang, et al. Expires June 4, 2009 [Page 35] Internet-Draft Adaptive Routing Protocol December 2008 Multicast tree resconstraction __________ __________ __________ __________ | | | | |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 Wang, et al. Expires June 4, 2009 [Page 36] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 37] Internet-Draft Adaptive Routing Protocol December 2008 10. IANA Considerations This document has no actions for IANA. Wang, et al. Expires June 4, 2009 [Page 38] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 39] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 40] Internet-Draft Adaptive Routing Protocol December 2008 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 June 4, 2009 [Page 41]