opnet-chord算法仿真

1111 Performance EvaluationPerformance EvaluationPerformance EvaluationPerformance Evaluation and Modeling and Modeling and Modeling and Modeling of of of of the Chord DHT Structured the Chord DHT Structured the Chord DHT Structured the Chord DHT Structured Overlay for AdOverlay for AdOverlay for AdOverlay for Ad----Hoc NetworksHoc NetworksHoc NetworksHoc Networks Aisling O’ Driscoll, Susan Rea, Dirk Pesch Cork Institute of Technology, Ireland, 2008 E-mail: {aisling.odriscoll, susan.rea, dirk.pesch}@cit.ie AbstractAbstractAbstractAbstract Peer-to-Peer (P2P) structured overlays have been established as an efficient approach for query resolution over large scale wired networks. Due to the distributed characteristics of P2P, structured P2P approaches have also been proposed for ad-hoc networks. However a comprehensive performance evaluation is needed and the precise network topology conditions under which an overlay algorithm may be rendered inoperable/inefficient must be explicitly defined. This paper presents a custom implementation of the Chord P2P structured overlay in OPNET, and evaluates its performance over ad-hoc networks given variable underlay conditions. IntroductionIntroductionIntroductionIntroduction Efficient and reliable data location and query resolution are vital topics in all infrastructureless networks. The widespread adoption of ad-hoc networks will not be realised without reliable application support and given this absent infrastructure, client- server applications are not feasible. Thus distributed network applications based on indirect routing must be sustained. Whilst traditional MANET routing protocols will endeavour to route packets efficiently to a particular destination, indirect routing investigates how to efficiently and reliably locate a particular data item when the node responsible for that data item is not known. This is a vital issue that must be addressed if completely distributed cross layer P2P systems are to be realised. First generation unstructured P2P lookup techniques are regarded as a sub-optimal solution because whilst they are highly resilient, they increase network congestion, limit scalability and do not return adequate search efficiency. Subsequently P2P networks have matured from their original unstructured form, to structured overlays like Distributed Hash Tables (DHTs) which are considered state of the art for optimal search efficiency. Overlay or structured P2P techniques create an abstraction of the underlying network so that higher layer applications or protocols such as those used for file sharing and distributed multimedia applications e.g. voice and video can efficiently locate a data item/user without having to resort to flooding queries. DHT algorithms are also efficient in that each network node only maintains bounded state information about a sub-set of the network which is more effective than maintaining a large routing table. Many DHT algorithms have been proposed but Chord, an algorithm specified by MIT [1], has emerged as the most widely adopted overlay technique, primarily because of its simplicity and its proven robustness given moderate churn over wired networks. This is further supported by the fact that Chord is currently being used as the basis for early P2PSIP work, having been adopted by the IETF P2PSIP WG as the base DHT algorithm. Recently, DHTs and in particular Chord have also been proposed for supporting P2P communication in vehicular [2] and sensor environments [3], opposites in the ad-hoc networking spectrum. Therefore the potential for distributed P2P networking applications using a structured lookup algorithm such as Chord is vast. However, whilst it has been proven that a structured approach improves lookup performance in a high bandwidth wired network, overlay networks may create unnecessary overhead that could negatively impact performance given an unstable environment such as a MANET. Dynamic node behaviour and mobility within the network may also lead to overlay inconsistency, incorrect lookups and long delays. Given that the base purpose of a P2P overlay is an efficient method to search for and retrieve information about the location of peers in a distributed environment, it must be evaluated whether a DHT can sustain its performance under ad-hoc conditions. This paper presents a Chord implementation in OPNET, which is evaluated over variable ad-hoc underlay conditions. Whilst the focus of this paper is on evaluating Chord over ad-hoc networks, the model could also be used to evaluate the feasibility of a structured approach for query resolution over infrastructure- based wireless networks or wired networks and can be used to evaluate the suitability of P2P applications in a range of scenarios such as vehicular and sensor networks. This paper is organized as follows. In section II the operation of the Chord overlay is described and in section III we describe our OPNET implementation of this DHT algorithm. In section IV, we evaluate the model and present initial simulation results. Concluding remarks are offered in section V. Chord DHTChord DHTChord DHTChord DHT Overview Overview Overview Overview Chord has one main operation – to retrieve the IP address of the node that has a data item, otherwise known as a lookup. It does this by associating each node with an ID, n, and each data item with an ID known as the key, k. Nodes then form a one dimensional identifier circle modulo 2 m , known as the identifier circle, where m is the number of bits in the ID. The key k is hosted by the node in the ring whose ID is greater than or equal to k. This node is then known as the key’s successor, successor(k). As a result of the circular structure, a key with ID greater than the highest node ID in the ring is stored at the node with the lowest node ID. As illustrated in Figure 1, the successor of k58 i.e. the next node clockwise, is n61 where k58 is then located. Chord’s most basic lookup process, whereby a node only stores its own successor in the ring and key requests are forwarded from successor node to successor node until the keys successor is found, results in messages linear to the number of nodes in the circle [4]. 2222 Figure 1: Operation of the Chord DHT Algorithm Therefore a more scalable technique is used where each node stores a database of IDs, known as a finger table, pointing to a subset of other nodes in the identifier circle. Assuming a circle with m-bit identifiers, a finger table has a maximum of m entries. For node n, the table entry at row i identifies the first node that succeeds n by at least 2 i-1 i.e. successor (n+2 i-1 ) where mi1 ≤≤ . For example in Figure 1, the second finger of n2 (2+2 1 =4) is n21 and the sixth finger (2+2 5 =34) is n35. As a finger table can store at most m entries its size is independent of the number of keys or nodes forming the DHT. A node forwards queries for k to the closest predecessor of k in the ID circle according to its finger table. When the query reaches a node such that k lies between the node and the nodes successor, the node reports its successor as the answer to the lookup. This results in an average of O(log(N)) routing hops for a Chord circle with N nodes. This method minimises the table lookup sizes resulting in a scalable distributed approach. An OPNET ChordAn OPNET ChordAn OPNET ChordAn OPNET Chord Model Model Model Model OPNET has been used to develop a simulation model for Chord and the algorithm has been implemented as previously described and as specified in [1]. The Chord DHT has been implemented as a custom process model and depending on the configured underlying routing protocol, is invoked after an initialisation interval by either the manet_rte_mgr process model in the case of OLSR, as illustrated in Figure 2 (a), or from the manet_mgr process model in the case of DSR and AODV as illustrated in Figure 2 (b). This is based on a modified version of the manet_station_adv node model and is achieved via a statistic wire. The 30 second initialisation interval allows for network convergence and for the routing protocol to reach a steady state. The process model interfaces directly with UDP for the transmission and reception of custom Chord packets via a randomly chosen port number. The Chord process model is illustrated in Figure 2 (c) and is now described in further detail. Init State: This is the first state entered upon invocation of the model. In this state, the state variables used throughout the simulation are initialised. The SHA-1 function is then used to calculate a 160 bit cryptographic checksum for any number of input bytes and generates the Chord node IDs based on an input of a 4 byte IPv4 address – This is based on a modified free SHA-1 library [5]. Once every node has been assigned their node ID, the Chord ring is formed with nodes listed in increasing order in a clockwise format as discussed and illustrated in Figure 1. Each nodes finger table is then created and populated, with three successors recorded to provide fault tolerance should the current successor fail as a consequence of node mobility or churn. Each node then schedules their first query request in the form of a self-interrupt after a uniform random delay between 0-10s so as to avoid a traffic pattern consisting of bursty lookups coinciding with the inter-request interval. The inter-request interval is a custom attribute that the user can configure to determine how often a node should query the Chord overlay for a particular key. Wait State: The process now enters an idle state and waits for an incoming event. This can be either an outgoing packet such as a DHT query or reply packet, an incoming packet from the radio channel, the expiration of a clock timer such as that used to monitor query re-transmissions or the periodic stabilisation procedure or an interrupt invoking node churn. Gen_Lookup State: A timer expires according to the configured inter-request interval and schedules a self interrupt that triggers the DHTC_LOOKUP_TIMER_EXPIRY event resulting in a transition to the Gen_Lookup state. In this state, keys are generated for query requests based on 32 bit randomly generated numbers and are hashed using the SHA-1 function. If a node determines that it owns the key, an alternative query request is generated. Each node consults its finger table to determine the closest predecessor node to this key. Should the node determines that the owner of the key is its immediate successor in its finger table, then this is still deemed to be a successful query lookup but a query packet is not transmitted. Instead, a custom statistic recording the number of successful table query resolutions is incremented. This scenario is most likely to occur in a small network of nodes. 3333 Figure 2 (a): Chord Node Model over OLSR Figure 2 (b): Chord Node Model over AODV and DSR Figure 2 (c): Chord Process Model The alternative and more common scenario is that upon consulting its finger table the node determines the closest predecessor to the key and forms a DHTC_QUERY packet. This unicast packet contains the source IP of the querying node, the destination IP of the closest predecessor node and the requested hashed key. It also contains a list to which the query originator will add its own IP address along with every node that processes this query – This will later be used as the basis for the overlay stretch statistic that evaluates the number of overlay hops in comparison with the hops incurred in the underlay network. The start time of the key request and the number of hops incurred to resolve the query are also recorded in the packet. The DHTC_QUERY packet is then sent to UDP for lower layer processing and transmission. The Gen_Lookup state is also invoked if the DHTC_REPLY_TIMER_EXPIRY event occurs. This interrupt occurs if a DHTC_REPLY packet had not been received for a previously transmitted key query before the query retransmission interval expires. The query retransmission interval has a default value of 15s. This could be a consequence of heavy network traffic resulting in large packet delays or a lack of response due to overlay inconsistency as a result of mobility or churn. The original query request is then retransmitted for a maximum of three attempts at which point it is considered an unresolved request i.e. failure of the overlay lookup algorithm. Process_Pkt State: When a packet arrives from the lower layer processes, the DHTC_PACKET_RECEIVE_EXPIRY event is triggered. The packet type determines how the packet should be processed. If a DHTC_REPLY packet is received it is first determines if the correct successor for this key was reported. If not the inconsistent overlay statistic is incremented, otherwise the lookup is considered successfully resolved. If the received packet type is a DHTC_QUERY packet, the receiving node must evaluate whether the requested key lies between itself and its immediate successor. If this is the case then a DHTC_REPLY packet is formed with a destination address of the first hop IP address in the list. Otherwise the node will make a decision on where to forward the query based on the contents of its finger table, will increment the hop count and list of IP addresses and will pass the packet to UDP. Gen_Churn State: The dynamic joining and leaving of nodes to/from the network is often referred to as node churn. A node failure/recovery object was initially used to simulate node churn according to a scripted process to enable the outcome to be clearly anticipated. However this evolved into the Gen Churn state which uses a stochastic method to generate node failures and recoveries according to a poisson distribution of times and locations. This represents the “random” arrival/departure of nodes and is invoked if the DHTC_FAIL_TIMER_EXPIRY event occurs. Handle_Churn State: As a consequence of the Gen_Churn state a failure or recovery interrupt will be generated. Depending on the interrupt type (OPC_INTRPT_FAIL or OPC_INTRPT_RECOVER) the appropriate handle function is invoked. Should a node want to join the overlay, it must be assigned a node ID, contact the bootstrap node to find out its successor, transmit a DHTC_NOTIFY message to notify its successor of its presence and build its fingers table. To check if nodes have departed the network, all Chord node periodically run the fix_fingers function to update their finger tables. 4444 Stabilize State: This function is run periodically on each node to validate and update its successor pointers. A node requests its successor to returns its predecessor. If the answer is the same as the node’s ID then the topology is unchanged. However if a new node joined the overlay in the interim, the requesting node must update its successor pointer to that of the new node and notifies the new node that it is it’s predecessor. Simulations & Preliminary Simulations & Preliminary Simulations & Preliminary Simulations & Preliminary ResultsResultsResultsResults To analyse the performance of the Chord model, a number of custom output statistics are available and the following is a description of the DHT behaviour that each statistic measures. Base Statistics: • Query Packets Transmitted: The global number of DHT_QUERY packets transmitted during the simulation. • Query Packets Forwarded: The global number of DHT_QUERY packets forwarded by intermediate nodes towards the key successor during the simulation. • Reply Packets Transmitted & Received: The global number of DHT_REPLY packets transmitted and received during the simulation. This does not reflect if a reply returns the correct/incorrect successor, simply that a reply to a query was received. • Queries Resolved via a Table Lookup: The number of queries resolved by consulting the nodes finger table. If a node’s immediate successor is responsible for the key this is considered a successful table lookup i.e. it is unnecessary to transmit a DHTC_QUERY packet. Request Success Ratio: The ratio of requests to which the originator received a correct response in comparison to those to which a response was never received as a consequence of incorrect routing or packet loss. Average ETE Delay: Time between generating a lookup request and receiving the response. This includes performing the Chord algorithm and processing the UDP packets in the underlay. Network Load: The total load in packets per second generated as a result of the global number of queries. This includes DHTC_QUERY packets, forwarded query packets and DHTC_REPLY packets. This excludes queries resolved via a table lookup as this does not result in any traffic being transmitted onto the network. Overlay Hops: The number of hops through which the query must pass before the lookup is resolved. The node that generates the request and every node that receives the request append their IP address to the hop list before forwarding the query packet to the next node in the lookup path. Along with validating that the model is performing as anticipated, this statistic will form the basis for an overlay stretch statistic in future work i.e. whether the overlay path results in an unnecessarily long physical route in the underlay. Overlay Consistency: The number of lookups to which a response was received but is incorrect due to node churn, mobility or the periodic nature of the stabilisation procedure. All scenarios are run for ten minutes of simulated time and use the system parameters as shown in Table 1. Chord Parameters Values Length of Simulation Run 10 minutes Length of run prior to gathering statistics 5% of simulated time (initialisation period) Number of Devices 5, 50, 100 Transmission Range 300m (-90dBm, 1mW) Inter-Request Interval 5s, 10s, 15s Environment Size 1km x 1km Table 1: Chord Simulation Parameters It is assumed throughout the simulations that all nodes have a maximum transmission range of approximately 300 metres as recommended by the IEEE 802.11 standard. The transmission range is calculated according to the free space loss channel model as a function of transmission power, reception power threshold and path loss with a default transmit power of 1mW and a reception power threshold of -90dBm. The SHA-1 function is used to generate Chord node IDs based on an input of a 4 byte IPv4 address. The DHT model currently assumes static node membership. Theoretical vs Empirical Performance In order to validate our model we analysed the theoretical estimate of the performance of Chord against its simulated behaviour in the model. Simulations were run for the number of devices and inter- request intervals as shown in Table 1. Choosing a scenario with 50 nodes and assuming an inter-request interval of 10 seconds for this test scenario, each node should generate 57 query requests during the simulation discounting the initialisation period i.e. 2850 query requests should theoretically be generated in total. According to the Chord algorithm - O(log(N)), there should be an estimated total of 11149 packets transmitted (2850 * O(log(50))). The actual total number of packets transmitted (inc