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
本文档为【opnet-chord算法仿真】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。