Network Working Group J.L. Lan Internet Draft J.H. Zhang Expires: December 30, 2011 B.Wang W.F. Liu National Digital Switching System Engineering and Technological Research Center, P.R.China X.Li BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS Node Potential Oriented Multi-NextHop Routing Protocol draft-ndsc-npmnrp-routing-protocol-02.txt Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, and it may not be published except as an Internet-Draft. 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 January 20, 2009. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include NDSC Expires December 30, 2011 [Page 1] Internet-Draft The NPMNRP Routing Protocol July 2011 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Abstract The Node Potential Oriented Multi-Nexthop Routing Protocol (NP- MNRP)bases on the idea of "hop-by-hop routing forwarding, multi- backup next hop" and combines with the phenomena that water flows from higher place to lower. NP-MNRP defines a metric named as node potential, which is based on hop count and the actual link bandwidth, and calculates multiple next-hops through the potential difference between the nodes. Table of Contents 1. Introduction.................................................3 2. Conventions used in this document............................5 3. Terminology..................................................5 4. Protocol operation...........................................8 4.1. Network prefix Information Advertisement................8 4.1.1. Methodology........................................8 4.1.2. Network Layer Reachable Information Advertisement..9 4.2. Neighbor Node Discovery and Adjacency Establishment....11 4.3. Calculation of Node Potential Value....................13 4.3.1. Protocol Packets Sending and Processing...........13 4.3.1.1. Network Layer Graph Routing Request Packet processing............................................13 4.3.1.2. Network Layer Graph Information Advertisement Packet sending........................................14 4.3.2. Calculation of the Node Potential Value...........14 4.4. network Event Sensing..................................16 4.4.1. Message Sending and Processing....................16 4.4.2. Forward Direction link Sensing....................17 4.4.3. Inverse Link Sensing..............................18 4.5. Update of the Node Potential...........................19 4.5.1. Update of Network Layer Value.....................19 4.5.2. Update of Node Potential Value....................20 5. Routing Information Base....................................22 6. NP-MNRP Packets Format......................................23 6.1. Encapsulation of NP-MNRP Packets.......................23 6.2. Packet Format..........................................24 6.2.1. The NP-MNRP Packet Header.........................24 6.2.2. Various types of Protocol Packets.................26 6.2.2.1. Network Layer Reachable Information Flood Advertisement Packet, NLRI-FAP........................26 NDSC Expires December 30, 2011 [Page 2] Internet-Draft The NPMNRP Routing Protocol July 2011 6.2.2.2. Network Layer Reachable Information Specific Request Packet, NLRI-SRP..............................27 6.2.2.3. Network Layer Reachable Information Direction Answer Packet, NLRI-DAP...............................28 6.2.2.4. Network Layer Graph Construction Trigger Packet, NLG-CTP...............................................31 6.2.2.5. Network Layer Graph Information Advertisement Packet, NLG-IAP.......................................31 6.2.2.6. Network Layer Graph Routing Request Packet, NLG-RRP .....................................................32 6.2.2.7. Network Layer Graph Request Update Packet, NLG-RUP .....................................................33 6.2.2.8. Link State Detect Packet, Detect.............34 6.2.2.9. REPLY Message Packet, REPLY..................35 7. References..................................................36 8. Acknowledgments.............................................37 1. Introduction The inspiration of this routing protocol comes from the natural water flow, which is a phenomenon of potential energy driven. Water flows through all feasible channels from a high potential site to a low potential site. If in every router all feasible next-hops for one certain destination can be found, then all the packets to that destination can be transferred in many paths. This routing protocol obeys the Internet philosophy of "hop-by-hop routing paradigm" and enhances it with "multiple feasible next-hops". That means that the protocol can manage to calculate multiple next- hops for each node and does not find multi-path end to end. The forwarding direction of packets is constrained by routing metrics. Different packets to one destination can be distributed into multiple next-hops in parallel, which can make full use of all feasible next hops, so that the link utility ratio is globally even. NDSC Expires December 30, 2011 [Page 3] Internet-Draft The NPMNRP Routing Protocol July 2011 Compared with the nature water flow phenomenon, the routing protocol defines a routing metric named as node potential in communication networks. Node potential is a parameter to measure the ability to transfer packets from one certain node to its destination. So the routing protocol is named as the node potential oriented multiple next-hops routing protocol (NP-MNRP for short). NP-MNRP is designed to calculate multiple next-hops for one destination in networks without knowing the globally topology information. Distance vector routing protocols such as RIP and BGP are used for reference. The NP-MNRP protocol consists of the network reachable information advertisement process and the node potential calculation process. But unlike those protocols, NP-MNRP ensures the following properties: (1) Multiple feasible next-hops for each destination. When a node finds the main next-hop unreachable, it chooses one from the backup next-hops to forward the packet. (2) Accelerate the convergence speed and reduce route flap. Compared with the single shortest-path routing, NP-MNRP can effectively avoid congestion and shorten protection switching delay. The path establishment and maintenance can be accomplished by routing information advertisement mechanism between peers. The control overhead of the protocol is smaller than other multi-path routing protocols. When kinds of concurrent failures occur in networks, NP- MNRP can provide more feasible next-hops and high recovery probability. NDSC Expires December 30, 2011 [Page 4] Internet-Draft The NPMNRP Routing Protocol July 2011 2. Conventions used in this document In examples, "C:" and "S:" indicate lines sent by the client and server respectively. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [RFC2119]. In this document, these words will appear with that interpretation only when in ALL CAPS. Lower case uses of these words are not to be interpreted as carrying RFC-2119 significance. In this document, the characters ">>" preceding an indented line(s) indicates a compliance requirement statement using the key words listed above. This convention aids reviewers in quickly identifying or finding the explicit compliance requirements of this RFC. 3. Terminology Carrier Network: It refers to the network in which the nodes run the Node Potential Oriented Routing Protocol. User Network: It refers to the network that needs message transfer service provided by the Carrier Network. Boundary Node: According to the nodes' location in the carrier network, the nodes are divided into boundary nodes and intermediate nodes. Boundary nodes are further divided into two categories according to the flow direction. In terms of user network flow, the node which flows into the carrier network, is called the ingress node; the node which flows out of the carrier network, is called egress node. Intermediate Node: It refers to the other nodes in the carrier network except the Boundary Nodes. NDSC Expires December 30, 2011 [Page 5] Internet-Draft The NPMNRP Routing Protocol July 2011 Potential Reference Node: It refers to the egress nodes through which the user network traffic flows out from the carrier network. In the route calculation process, these nodes will set their node potential value to zero and act as reference nodes in the node potential computation procedure. Network Layer Diagram: It refers to the diagram that describes the distribution of all nodes' layer value relative to a destination node. Node Potential: It is a metric that measures the accessibility from a node to zero potential nodes in the carrier network. Router ID: It refers to a 32-bit number assigned to each router running the NP-MNRP protocol. This number uniquely identifies the router in the carrier network. One algorithm for Router ID assignment is to choose the largest or smallest IP address assigned to the router. Set of Available Next-hops: It refers to the set of available next- hops of node i when it sends packets to the destination node j, which is denoted as A (i,j). Network Layer Reachable Information Flood Advertisement Packet (NLRI- FAP): The packet is used to advertise the information of binding relations between network prefix and egress nodes to its neighbors. The IP address and subnet mask of its binding user network are included in this packet. Network Layer Reachable Information Specific Request Packet (NLRI- SRP): The packet is used to request a particular egress node for NDSC Expires December 30, 2011 [Page 6] Internet-Draft The NPMNRP Routing Protocol July 2011 certain prefix binding relationship information. IP address and subnet mask of user network whose binding relationship needs to know are included in this packet. Network Layer Reachable Information Direction Answer Packet (NLRI- DAP): The packet is used to respond to a Network Layer Reachable Information Specific Request Packet. The IP address and subnet mask of user network and its bound router ID are included in this packet. Network Layer Graph Construction Trigger Packet (NLG-CTP): The packet is used to trigger the building of network layer diagram. Network Layer Graph Information Advertisement Packet (NLG-IAP): The packet is used to advertise its layer information relative to one egress node to its neighbors. The egress node ID and its layer value relative to this egress node are included in this packet. Network Layer Graph Routing Request Packet (NLG-RRP): The packet is used to request the neighbors' layer information relative to one egress node and this egress node ID is included in this packet. Network Layer Graph Request Update Packet (NLG-RUP): The packet is used to inform the nodes which are on a particular layer relative to one destination node, to rebuild their layer information and that layer value is included in this packet. Link State Detect Packet (Detect): The packet is used to detect the link status between itself and its neighbors. The sequence number of this packet and the period for sending Detect are included in this packet. NDSC Expires December 30, 2011 [Page 7] Internet-Draft The NPMNRP Routing Protocol July 2011 REPLY Packet (REPLY): The packet is used to respond to the Detect indicating the good link state. The sequence number of this packet and the period for sending Detect are included in this packet. 4. Protocol operation 4.1. Network prefix Information Advertisement 4.1.1. Methodology Because the NP-MNRP protocol is designed as an IGP inside the autonomous system, it should route transit network traffic and local network traffic. The network IP prefix is divided into two parts: the IP prefix information of the transit network and the IP prefix information of the network running the NP-MNRP protocol. CNRT: Carrier Network Router ---- ---- ---- / \ / \ / \ * UN1 * * UN2 * * UN3 * \----/ \----/ \----/ | | | ******|*******************|*******************|****** * +-----+ +-----+ +-----+ * * |CNRT1|-------------|CNRT2|-------------|CNRT3| * * +-----+ +-----+ +-----+ * * | | | * * | | | * * +-----+ +-----+ +-----+ * * |CNRT5|-------------|CNRT6|-------------|CNRT4| * * +-----+ CN +-----+ +-----+ * ******|***************************************|****** __|_ __|_ /----\ /----\ * UN5 * * UN4 * \----/ \----/ Figure 1 Network Model NDSC Expires December 30, 2011 [Page 8] Internet-Draft The NPMNRP Routing Protocol July 2011 In view of the NP-MNRP protocol, the network is divided into the user network and the carrier network, as shown in Figure 1. The user network is abbreviated as UN and the carrier network is abbreviated as CN. Each node in CN will run NP-MNRP protocol to establish a multiple next-hops routing information base. Otherwise, it is not necessary for nodes in UN to run the NP-MNRP protocol. The nodes in UN will finish local communication and transmit the network traffic whose destinations are not in the user network itself to the Carrier network. The network prefix of UN is named as Network Layer reachable information. The carrier network mainly transfers transit traffic for UN. The network prefix of CN is treated as network topology information and will be advertised by potential calculation process. The boundary nodes of CN are also named as egress nodes. They advertise network layer reachable information to neighbor nodes periodically and initiate the node potential calculation procedure. This advertisement method separates the information of the CN topology from the network layer reachable information and advertises them in different manners. The advertisement of topology information is independent on network layer reachable information. From this way, the flexibility of routing information distribution can be enhanced. 4.1.2. Network Layer Reachable Information Advertisement Network layer reachable information that means the user network prefix is advertised through NLRI-FAP, NLRI-SRP and NLRI-DAP packets. The boundary nodes in CN are responsible for advertising user network reachable information, as shown in Figure 2. NDSC Expires December 30, 2011 [Page 9] Internet-Draft The NPMNRP Routing Protocol July 2011 The boundary nodes in CN advertise network layer reachable information to neighbor nodes periodically through NLRI-FAP. Once receiving the NLRI-FAP, the nodes in CN extract network prefix information from packets and add them to the network layer reachable information database of their own. ................ . UN . . Host1 Host2 . . \ / . . \ / . . +-----+ . . |UNRT1| . . +-----+ . Host1 Host2 .Host1 Host2 .......|........ \ / \ / ****************|*****************\ /*********************\ /*** * +------+ +------+ * +-----+* * +-----|CNBRT1|------------|CNBRT2|----------------|UNRT2|* * | +------+ +------+ * +-----+* * | | | | * * | | | * | * * | +-----+ +-----+ +-----+* | * * | |CNRT6|-------------|CNRT3|-------|CNRT2|* | * * | +-----+ +-----+ +-----+* | * * | | | | * | * * | | | | * | * * +------+ +-----+ +-----+ +------+* | * * |CNBRT4|---|CNRT5|-------------|CNRT4|------|CNBRT3|-------+ * * +------+ +-----+ CN +-----+ +------+* * ******|******************************************/ \************ ......|......... / \ +-----+ . Host1 Host2 |UNRT3| . +-----+ . / \ . / \ . Host1 Host2 . ................ NDSC Expires December 30, 2011 [Page 10] Internet-Draft The NPMNRP Routing Protocol July 2011 Figure 2 Network layer reachable information advertisements CNRT: Carrier Network Router; CNBRT: Carrier Network Boundary Router When the nodes in CN don't know user network prefix, these nodes will act as inquirers and send NLRI-SRP to query other nodes and set a query timer. When a node receives the NLRI-SRP, and the network prefix information or attached router information is in its database, it responds to the inquirer with an NLRI-DAP packet. Otherwise, it sends the NLRI-SRP packet to its neighbors except for the enquirers. This process will continue until the inquirer get an response from other nodes or such query timer is timed out. When bound to the egress node (relative information is absent in the network layer reachable information database of the node), the node sends NLRI-SRP flooding to the inquirer, called the enquirer. 4.2. Neighbor Node Discovery and Adjacency Establishment When a new node joins in the network, other nodes discover it and initialize their local routing tables as the following steps: (1): Broadcast a Detect packet and a NLG-CTP packet. This node sets the sequence number of Detect with 0.The Detect will be sent periodically by defaulted period set in the protocol; (2): When other nodes receive a Detect packet or a NLG-CTP packet, they operate as follows: (a) If the received Detect comes from an unknown node and its sequence number equal to 0, the receivers know that a new node is NDSC Expires December 30, 2011 [Page 11] Internet-Draft The NPMNRP Routing Protocol July 2011 added to the network, and add it to their neighbor node database and record Detect's sequence number; (b) Reply to the unknown node with a REPLY packet; Send an NLG-IAP packet which contains all egress nodes information in the database. (c) According to the computation rules of node potential, they compute layer value and potential value relative to the egress node. (3): When receiving a REPLY packet and an NLG-IAP packet, the new node operates as follows: (a) Adds the neighbor node to routing information database; (b) According to NLG-IAP, it calculates its own layer value in the following formula: L(i,i)=0; L(i,j)=min[L(k,j)]+1, for each k blongs to Ki, j blongs to N, and k,j are not equal to i. L(i,j) is the layer value of node i reference to egress node j, N is the set of network nodes, Ki is the set of neighbor nodes about node i. (c) Based on the layer values of its neighbors, bandwidth and its own layer value, the new node computes node potential value of its neighbors and its own. NDSC Expires December 30, 2011 [Page 12] Internet-Draft The NPMNRP Routing Protocol July 2011 4.3. Calculation of Node Potential Value NP-MNRP defines node potential value as a mixed metric of hop count and bandwidth. Hop count metric records the number of routers which a packet passes through and each router is recorded as one hop. The actual link bandwidth is allocated\configured by router in the network initialization. 4.3.1. Protocol Packets Sending and Processing 4.3.1.1. Network Layer Graph Routing Request Packet processing Network Layer Graph Routing Request Packet (NLG-RRP) has two different types. One type is the all-nodes layer information request packet which will request the receiver to send layer information of all nodes. The other is the partial-nodes layer information request packet which will request the receiver to send layer information of the specified nodes. The NLG-RRP will be used in the following conditions: Condition 1: When a new node is attached to the network, all nodes layer information request packet will be sent to its neighbors. Condition 2: When the node wants to get some certain network prefix information from its neighbors, partial nodes layer information request packet will be sent. Once receiving a NLG-RRP packet, each node should process as the following steps: NDSC Expires December 30, 2011 [Page 13] Internet-Draft The NPMNRP Routing Protocol July 2011 (a): Firstly, the type of the packet will be verified whether or not it is a correct NLG-RRP packet. (b): When NLG-RRP is the all-nodes layer information request packet, it sends its own layer information relative to the other nodes to the request node. (c): When NLG-RRP is the partial-nodes layer information request packet, it sends its own layer information relative to the destination node in the packet to the query node. 4.3.1.2. Network Layer Graph Information Advertisement Packet sending The Network Layer Graph Information Advertisement Packet (NLG-IAP) is broadcasted to its neighbors in the following cases: Case 1: All-nodes' layer values are specified after the network layer graph has been divided. Case 2: When layer information of any node is changed, which may be caused by the change of layer values of some routers when they receive NLG-FAP or some new nodes are added to the network. Case 3: An NLG-RRP packet is received and the receiver's layer information reference to certain egress node is changed. The processing rules of NLG-IAP are described in Section 3.5. 4.3.2. Calculation of the Node Potential Value In NP-MNRP, the node potential value is a mixed metric, including hop count and actual link bandwidth. Each egress node activates its NDSC Expires December 30, 2011 [Page 14] Internet-Draft The NPMNRP Routing Protocol July 2011 neighbors to build Network Layer graph by sending an NLG-CTP packet to neighbors. It is calculated as follows: (1) In the algorithm initialization, egress node assigns its layer value as 0, and then sends a NLG-CTP packet to its neighbors, which contains the actual link bandwidth. (2) The neighbor node that received a NLG-CTP packet from the 0- layer node sets itself as 1-layer, and generates a NLG-CTP packet and sends to its neighbors., and so on. (3) Repeat the above step (2) until the nodes whose layer value are smaller than f-layer which have been determined. (4) After the f-layer has been constructed completely, each node in F-layer knows that it is in F-layer and knows which neighbors are in F-1 layer. The nodes in F-1layer know which ones are in F layer, which ones are in F-1 layer, and which ones are in f-2 layer. (5) Suppose F-layer has been constructed, and the algorithm has not been terminated, then the construction of the f +1 layer will begin. The nodes in F-layer will send an NLG-CTP packet to its neighbors. (6) When all the nodes are traveled, the algorithm ends. All nodes in the network not only are aware of their own layer value but also know their neighbors' layer value and the actual bandwidth between themselves. Next each node calculates the potential value as follows: NDSC Expires December 30, 2011 [Page 15] Internet-Draft The NPMNRP Routing Protocol July 2011 (1) 0-layer nodes directly define their own potential value as 0; (2) Each node of the other layers chooses the largest potential value node among its neighbors in the same and lower layers as its reference node for defining potential value, then defines its potential values as the reference node's potential value plus one and its neighbors' potential value are equal to their layer value. (3) When all the neighbors' potential value are defined, the node will choose the neighbor nodes whose potential values are less than its potential values as its feasible next-hops. 4.4. network Event Sensing The NP-MNRP protocol can sense events such as new nodes are added to the network or a neighbor node is down. The node senses these events by sending out the Detect packet and receiving the REPLY packet periodically. 4.4.1. Message Sending and Processing Each NP-MNRP node broadcasts periodically a Detect packet. When a Detect packet is received, the receiver sends a REPLY packet to the sender. The detailed steps are as follows: Step1: Each node broadcasts periodically a Detect packet. Detect carries a sequence number and the detect message's periodic interval. Step2: When a Detect packet is received, its sequence number is compared with the expected sequence number for this neighbor. Then the receiver sends a REPLY packet to the sender and evaluates inverse link quality according to the sequence number. NDSC Expires December 30, 2011 [Page 16] Internet-Draft The NPMNRP Routing Protocol July 2011 Step3: When a Reply packet is received, its sequence number should be equal to the sequence number of the Detect packet's sequence number. Then the receiver evaluates link quality according to the sequence number and the use of sent/receive message time. 4.4.2. Forward Direction link Sensing A(Ti) represents the mean interval from node i sending out the Detect packet to receiving the REPLY packet. FA (Ti) represents the latest mean interval time. Node i adjusts the period of sending out a Detect packet according to the following rules: (1) If FA(Ti) < A(Ti), it means that the link quality is stable. At this period, when three continuous Detect packets are all low, then increase the Detect interval; (2) If FA(Ti) > A(Ti), it means that the link quality is unsteady or becomes bad. At this period, when three continuous Detect packets are all high, then reduce the Detect interval; (3) When a Detect packet is sent out but a REPLY packet is not received in the 2*FA(Ti) time, the node will reduce the period into half, then continue sending out the next sequence number Detect packet. If a REPLY packet is still not received, the node insulates that node and thinks of link breakdown or link congestion. (4) The isolate node will not be used as the next-hop to forwarding packets. The processing node should continue sending the Detect packet and adjust strategies according to the following conditions: NDSC Expires December 30, 2011 [Page 17] Internet-Draft The NPMNRP Routing Protocol July 2011 (a) If three continuous REPLY packets are received, then the node deletes the isolate node and uses nodes which reply to the REPLY packet as the next-hops to forwarding packets. (b) If no packet is received after 6 Detect intervals, so that the node is thought to be breakdown, no longer send the Detect packet again , and wait for 6 Detect intervals, if still not receiving a Detect packet from other node, so judge the node breakdown and delete all its neighbors' routing information; (c) If the node can receive a Detect packet or a REPLY packet which is sent out from the isolation node, and then it will continue sending a Detect packet until the isolation node recovery or judge node breakdown. 4.4.3. Inverse Link Sensing Each node broadcasts periodically Detect packets. Every Detect packet carries a sequence number and the interval. When a Detect packet is received, the sequence number is compared with the next expected sequence number for this neighbor, if the sequence number of the received Detect packet is higher than the expected, then one or more Detect packets have been missed. If the sequence number is lower, then this neighbor decreases the Detect interval, and part of the history must be undone. From the history of received Detect packets, a node computes an estimate of the inverse link quality. NDSC Expires December 30, 2011 [Page 18] Internet-Draft The NPMNRP Routing Protocol July 2011 4.5. Update of the Node Potential 4.5.1. Update of Network Layer Value As the set of next-hop is empty, the node will trigger update about the layer value through the following operations: (1) Firstly, the node will check whether the set of its neighbors on the same layer is empty. If not, it will change itself layer value and generate NLG-IAP packets that are sent to its neighbors. (2) If the set is empty, then the node will perform the following steps: (a) Flooding NLG-RUP packets, whose layer value will be revised to the old layer value minus 2, however, if old layer value minus 2 is less than 0, the value is set to 0. What's more, all information about this egress node will be deleted. (b) The node which received an NLG-RUP packet will check if it has ever received this message. If having received such a message, the packet will be ignored, otherwise the layer value in this packet will be viewed. If the value is greater than the value of its own, the node will discard the packet, otherwise, go on flooding NLG-RUP packets to its neighbors and delete all information about this egress node. (c) If the layer value in the packet is equal to its own, the node will stop flooding to send NLG-RUP and send an NLG-CTP packet about the egress node. NDSC Expires December 30, 2011 [Page 19] Internet-Draft The NPMNRP Routing Protocol July 2011 (d) The Neighbor node which received an NLG-CTP packet will calculate its new layer value. If new value is the same with the original, the node stops sending NLG-CTP packets and the layer value update algorithm will terminate. 4.5.2. Update of Node Potential Value The potential value of the nodes will be updated in the following conditions. (1) Potential value update caused by NLG-IAP packet. The main contents of an NLG-IAP packet are layer information of a node relative to the egress node in the network. The node adjusts its potential value according to the NLG-IAP packets received from its neighbors. Specific updates come as follows: (a) NLG-IAP packet generation When the node finds its layer information relative to one certain egress node changed, the new layer information relative to all egress nodes will be written into its generated NLG-IAP packet. (b) NLG-IAP to send The node will broadcast its generated NLG-IAP packets to its neighbors, and then wait for confirmation from its neighbors. When the node receives REPLY pockets with sequence number 0XFFFF from its neighbors, this update ends. (c) When the node received the NLG-IAP packet, it performs the following steps: NDSC Expires December 30, 2011 [Page 20] Internet-Draft The NPMNRP Routing Protocol July 2011 Firstly, this node will verify the NLG-IAP packet. If the packet is validated, it sends a REPLY packet with sequence number 0XFFFF to the source node of the NLG-IAP packet. Secondly, this node will extract layer information from the NLG-IAP packet supposing a received routing entries includes RUIi =< RouterID, EgressnodeID, Layi> and the corresponding routing entry stored in the database is RUI'I =< RouterID, EgressnodeID, Lay'i>, when one of the following three cases are met, the node updates its own routing table according to the information received. Case 1: If the EgressnodeID included in the received routing table entry dose not exist in its own routing table, the router will add it and send an NLG-RRP packet about the destination address of the network to its neighbors. After receiving NLG-IAP packets, it will calculate its layer value relative to this egress node according to the formula in 3.2, get the neighbors' layer value, and then define the neighbors' potential value relative to this destination node. Case 2: If the EgressnodeID included in the received routing table entry exists in its own routing table and Lay'i < Layi, the router will adjust its neighbors' layer value and potential value. If the neighbor's potential value is greater than its own and the neighbor node is just in its own next-hop collection, the router will remove the node from next-hop collection, if not, do nothing. Case 3: If Layi < Lay'i, then the router will adjust this neighbor node's layer value and potential value. If the neighbor's potential value is less than its own and the neighbor node is not in its own NDSC Expires December 30, 2011 [Page 21] Internet-Draft The NPMNRP Routing Protocol July 2011 next-hop collection, then the router will add it into the next-hop collection, if it exists, nothing needs to be done. However, the router will not adjust its layer value and potential value in this case. (2) Potential value update caused by the change of layer value When the node's layer value reference to a particular destination node changes, firstly it will modify layer value of itself and its neighbors. Then the new potential value will be calculated according to the update strategy. 5. Routing Information Base Each routing node maintains the Routing Information Base to forward IP packets. The NP-MNRP protocol can calculate multi-nexthop routing information in the network. The route computation process descried in Section 3 will record all the feasible next-hops for every destination. The multi-nexthop routing entry is composed of three fields. The first field is named as the destination IP address field. The second field is named as the destination IP address mask filed. The first and second fields are 32-bit numbers which define network destination information of each routing entry. And the route information base is indexed by the first and second field. The third field is named as the feasible nexthop filed, whose form is a couple of next-hop IP address value and node potential difference value. The next-hop IP address is the IP address of the NDSC Expires December 30, 2011 [Page 22] Internet-Draft The NPMNRP Routing Protocol July 2011 neighbor node which will act as a feasible next-hop for this routing node to forward IP packets to the network destination. Compared with the single next-hop routing information, the number of the feasible next-hop filed in a multi-nexthop routing entry may be a value bigger than one. The routing node will gain more agility in the IP packet forwarding procedure. It can choose , forward all the packets to one best next- hop and use other feasible next-hop entries as backup entries. Through this way, the network availability will be improved in the scene where network failure or mal-function occurs frequently. It can also choose and forward all the IP packets to all feasible next-hop entries. In this manner, this routing node can assign each next-hop a traffic ratio for each destination. All the packets will be forwarded to all available next-hops . This will make the network resource utilization more even and avoid network congestion in some ways. 6. NP-MNRP Packets Format The NP-MNRP protocol runs directly over the IP network layer. Before any packet format is described, the details of the NP-MNRP encapsulation are explained. 6.1. Encapsulation of NP-MNRP Packets NP-MNRP runs directly over the Internet Protocol's network layer. Therefore, NP-MNRP packets are encapsulated solely by IP and local data-link headers. NP-MNRP does not define a way to fragment its protocol packets, and depends on IP fragmentation when transmitting packets larger than the network MTU. NDSC Expires December 30, 2011 [Page 23] Internet-Draft The NPMNRP Routing Protocol July 2011 NP-MNRP uses IP protocol number 99. Routing protocol packets are sent with the IP precedence set to the inter-network Control. NP-MNRP protocol packets should be given precedence over regular IP data traffic, in both sending and receiving. 6.2. Packet Format There are nine distinct NP-MNRP packet types. All NP-MNRP packet types begin with a standard 20 byte header. This header is described first. Each packet type is then described in a succeeding section. In these sections each packet's division into fields is displayed, and then the field definitions are enumerated. 6.2.1. The NP-MNRP Packet Header Every NP-MNRP packet starts with a standard 20 byte header. This header contains all the information necessary to determine whether the packet should be accepted for further processing. This determination is described in Section 5.2 of the specification. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | Type | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ NDSC Expires December 30, 2011 [Page 24] Internet-Draft The NPMNRP Routing Protocol July 2011 Version:The NP-MNRP version number. This specification documents version 1 of the protocol. Type:The length of the NP-MNRP protocol packet in bytes. This length includes the standard NP-MNRP header. --------------------- | Type| Description | |-----|--------------- | 1 | NLRI-FAP | | 2 | NLRI-SRP | | 3 | NLRI-DAP | | 4 | NLG-CTP | | 5 | NLG-IAP | | 6 | NLG-RRP | | 7 | NLG-RUP | | 8 | Detect | | 9 | REPLY | --------------------- Router ID:The Router ID of the packet's source.It is the minimum or maximum IP address or any IP address in all the interfaces; however, it WOULD be always fixed once the agreement starts. Check Sum:The standard IP checksum of the entire content of the packet starts with the NP-MNRP packet header but excluding the 64-bit authentication field. If the length of the package is less than 16- bit, 0 byte WOULD be added before the checksum byte. Authentication Type:Identify the authentication procedure used for the packet. Authentication is discussed in the specification. Authentication Info:64-bit authentication information field depends on the chosen authentication type, to carry identification information such as identity authentication. NDSC Expires December 30, 2011 [Page 25] Internet-Draft The NPMNRP Routing Protocol July 2011 6.2.2. Various types of Protocol Packets NP-MNRP protocol packets have a total of 9 species. 6.2.2.1. Network Layer Reachable Information Flood Advertisement Packet, NLRI-FAP The NLRI-FAP packet is the NP-MNRP packet type 1.The packet is sent by an egress node in the carrier network and is used to advertise the user network prefix information which is bound to this node. The node that received this packet WOULD consider this egress node reachable and the user network which is bound to this node reachable too. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 1 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ...... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP address of the network:The IP address of a user network is bound to this egress node. NDSC Expires December 30, 2011 [Page 26] Internet-Draft The NPMNRP Routing Protocol July 2011 Subnet Mask of the Network:The subnet mask of user network is denoted in the above field. 6.2.2.2. Network Layer Reachable Information Specific Request Packet, NLRI-SRP The NLRI-SRP packet is the NP-MNRP packet type 2.This packet is used by the node in the carrier network to request the network layer reachable information. When the node doses not know which egress node one network prefix is bound to, the NLRI-SRP packet is sent. If the IP address and the subnet mask of the network 1 is all 0, all the network prefixes WOULD be requested, and usually this request is sent by a node which just joins into the carrier network. NDSC Expires December 30, 2011 [Page 27] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 2 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ...... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP address of the network:The IP address of a user network whose binding relationship this node want to request. Subnet Mask of the Network The Subnet mask of a user network denoted is in the above field, whose binding relationship this node wants to request 6.2.2.3. Network Layer Reachable Information Direction Answer Packet, NLRI-DAP The NLRI-DAP packet is the NP-MNRP packet type 3. The node that receives the NLRI-SRP packet WOULD check its information database to seek for the corresponding binding relationship. If the binding relationship exists in its own information database, it WOULD send an NDSC Expires December 30, 2011 [Page 28] Internet-Draft The NPMNRP Routing Protocol July 2011 NLRI-DAP packet to the requesting node, if not, it WOULD send NLRI- SRP packets to its all neighbor nodes except for the requesting node. If a node which sends the NLRI-SRP packets at the same time receives more than one packets about the same IP prefix binding relationship, and these packets are conflictive, it WOULD go on sending NLRI-SRP packets, until the egress node which the network prefix is bound to answers the request. NDSC Expires December 30, 2011 [Page 29] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 3 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ...... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP address of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subnet mask of the network n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP Address of the Network:The IP address of a user network whose binding relationship this node wants to know in the receiving NLRI- SRP packet. Subnet Mask of the Network:The subnet mask of a user network denoted in the above field, whose binding relationship this node wants to know in the receiving NLRI-SRP packet. Egress Node ID:This field denotes the user network, whose IP address and subnet mask emerge in the front two fields, is bound to this egress node. NDSC Expires December 30, 2011 [Page 30] Internet-Draft The NPMNRP Routing Protocol July 2011 6.2.2.4. Network Layer Graph Construction Trigger Packet, NLG-CTP The NLG-CTP packet is the NP-MNRP packet type 4.When one egress node joins into the carrier network, it WOULD send this packet to urge the other nodes to build network layer graph relative to itself. 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 4 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Layer value | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Egress Node ID:The node that received this packet calculates its layer value relative to this egress node. Layer Value:This is the sender's layer value relative to the node denoted in the above field 6.2.2.5. Network Layer Graph Information Advertisement Packet, NLG-IAP The NLG-IAP packet is the NP-MNRP packet type 5. This packet is sent to all neighbor nodes using multicast address to advertise its layer value relative to the node whose ID is included in this packet, this packet is usually to start the neighbor nodes to adjust their potential dynamically. NDSC Expires December 30, 2011 [Page 31] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | 5 | packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Layer value 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ....... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Layer value n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Egress Node ID:The receiver need adjust its layer value relative to this node Layer Value:This is the layer value of the sender relative to the egress node denoted in the above field. 6.2.2.6. Network Layer Graph Routing Request Packet, NLG-RRP The NLG-RRP packet is the NP-MNRP packet type 6. This packet is used by one node to request the neighbor nodes to send their own layer information relative to the appointed egress node to it. This packet has two types: one is for all nodes and the other is for some nodes. NDSC Expires December 30, 2011 [Page 32] Internet-Draft The NPMNRP Routing Protocol July 2011 If the egress node ID in the packet is empty, the packet is the NLG- RRP packet for all nodes, if not; the packet is the NLG-RRP packet for the appointed nodes included in this packet. 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | 6 | packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ....... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Egress Node ID:This field denotes the receiver needed to respond its layer value relative to this egress node. 6.2.2.7. Network Layer Graph Request Update Packet, NLG-RUP The NLG-RUP packet is the NP-MNRP packet type 7. When a node finds its next hops and its neighbors on the same layer are all unreachable, it sends this packet to neighbors to update its layer value. NDSC Expires December 30, 2011 [Page 33] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | 7 | packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Egress node ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Layer value | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Egress Node ID:This field denotes the receiver needs to update its value relative to this node Layer Value:The layer value in NLG-RUP packet is the layer value relative to high egress node minus 2. 6.2.2.8. Link State Detect Packet, Detect The Detect packet is the NP-MNRP packet type 8. This packet is periodically sent to neighbor nodes to evaluate the link quality. NDSC Expires December 30, 2011 [Page 34] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | 8 | packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence number | Period | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Sequence Number:The sequence number in this packet is the sequence number of the Detect message, and it is an increasing positive integer. Period:The period in this packet is the interval time between this and the last one. 6.2.2.9. REPLY Message Packet, REPLY The REPLY packet is the NP-MNRP packet type 9. The node that received a detect packet will send a reply packet to the sender, which can evaluate the reverse link quality according to this packet. The sequence number in this packet denotes it is the reply to the Detect message that has the corresponding sequence number. If the number is all-1, it means the packet is the confirmation message to an NLG-IAP message. NDSC Expires December 30, 2011 [Page 35] Internet-Draft The NPMNRP Routing Protocol July 2011 0 1 2 3 4 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Byte 1 | Byte 2 | Byte 3 | Byte 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | 9 | packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Sum | Authentication Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 0-3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication Info(8 array 4-7) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Serial number | Period | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Serial Number:The sequence number in this packet is the sequence number of the REPLY, and it is an increasing positive integer. Period:This field denotes that the node sending this packet will send Detect messages at this period. 7. References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997. NDSC Expires December 30, 2011 [Page 36] Internet-Draft The NPMNRP Routing Protocol July 2011 8. Acknowledgments This research was sponsored by the National High-Tech Research and Development Plan of China under grant numbers 2007AA01Z2a1 and 2008AA01Z214; the National Grand Fundamental Research Program of China under grant number 2007CB30710; the National Key Technology R&D Program of China under grant number 2008BAH37B02. This document was prepared using 2-Word-v2.0.template.dot. Authors' Addresses Julong Lan National Digital Switching System Engineering and Technological Research Center NDSC, No.7 , Jianxue Street,Jinshui District Zhengzhou, 450002, P.R.China Phone: +86-371-8163-2988 Email: ndscljl@163.com URI: http://www.ndsc.com.cn/ Jianhui Zhang National Digital Switching System Engineering and Technological Research Center NDSC, No.7 , Jianxue Street,Jinshui District Zhengzhou, 450002, P.R.China Phone: +86-371-8163-2988 Email: ndsc155@163.com URI: http://www.ndsc.com.cn/ Bin Wang National Digital Switching System Engineering and Technological Research Center NDSC, No.7 , Jianxue Street,Jinshui District Zhengzhou, 450002, P.R.China Phone: +86-371-8163-2909 Email: wbin2006@gmail.com URI: http://www.ndsc.com.cn/ Wenfen Liu National Digital Switching System Engineering and Technological Research Center NDSC, No.7 , Jianxue Street,Jinshui District Zhengzhou, 450002, NDSC Expires December 30, 2011 [Page 37] Internet-Draft The NPMNRP Routing Protocol July 2011 P.R.China Phone: +86-371-8163-0340 Email: wenfenliu@sina.com URI: http://www.ndsc.com.cn/ Xin Li BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS No.10 Xi Tu Cheng Road Haidian District Beijing,100876 P.R.China Phone: +8613581614576 Email: cplalx@gmail.com http://www.bupt.edu.cn/ NDSC Expires December 30, 2011 [Page 38]