Transcript Document

Chapter 13
Ad Hoc Networks
1
Outline











Introduction
Characteristics of MANETs
Applications
Routing
Table-driven Routing Protocols
Source-initiated On-demand Routing
Hybrid Protocols
Vehicular Area Network (VANET)
Security Issues in Mobile Ad hoc Networks
(MANETs)
Network Simulators
Summary
2
Introduction




A Mobile Ad hoc Network (MANET) is an
autonomous system of nodes (MSs) (also serving
as routers) connected by wireless links
No infrastructure exists in a MANET
The network’s wireless topology may change
dynamically in an unpredictable manner since
nodes are free to move and each node has limited
transmitting power
Information is transmitted in a store-and
forward manner (peer-to-peer) using multi-hop
routing
3
Introduction (Cont’d)




Each node is equipped with a wireless transmitter
and a receiver with an appropriate antenna
We assume that it is not possible to have all nodes
within each other’s radio range
When the nodes are close-by i.e., within radio
range, there are no routing issues to be addressed
At a given point in time, wireless connectivity in
the form of a random multi-hop graph exists
between the nodes
4
A Mobile Ad Hoc Network
(MANET)
MS2
MS2
MS4
Asymmetric link
MS3
MS5
MS7
Symmetric link
MS1
MS6
5
Direct Transmission versus
Multi-hop
A
A
B
C
D
E
B
Energy Consumption
Time delay
6
Characteristics of MANETs




Dynamic topologies: Network topology may
change dynamically as the nodes are free to move
Bandwidth-constrained, variable capacity links:
Realized throughput of wireless communication is
less than the radio’s maximum transmission rate
Collision occurs frequently
Energy-constrained operation: Some nodes in the
ad hoc network may rely on batteries or other
exhaustible means for their energy
Limited physical security: More prone to physical
security threats than fixed cable networks
7
Applications




Defense applications: On-the-fly communication set up
for soldiers on the ground, fighter planes in the air, etc.
Crisis-management applications: Natural disasters,
where the entire communication infrastructure is in
disarray
Tele-medicine: Paramedic assisting a victim at a
remote location can access medical records, can get
video conference assistance from a surgeon for an
emergency intervention
Tele-Geoprocessing applications: Combines
geographical information system, GPS and high
capacity MS, Queries dependent of location
information of the users, and environmental
monitoring using sensors
8
Applications



Vehicular Area Network: in providing emergency
services and other information in both urban and
rural setup
Virtual navigation: A remote database contains
geographical representation of streets, buildings, and
characteristics of large metropolis and blocks of this
data is transmitted in rapid sequence to a vehicle to
visualize needed environment ahead of time
Education via the internet: Educational opportunities
on Internet to K-12 students and other interested
individuals. Possible to have last-mile wireless
Internet access
9
Routing in MANETS - Goals



Provide the maximum possible reliability - use
alternative routes if an intermediate node fails
Route network traffic through the path with
least cost metric between the source and
destination
Give the nodes the best possible response time
and throughput
10
Need for Routing








Route computation must be distributed. Centralized
routing in a dynamic network is usually very expensive
Routing computation should not involve the
maintenance of a global state
Fewer nodes must be involved in route computation
Each node must care about the routes to its destination
and must not be involved in frequent topology updates
Stale routes must be either avoided or detected
Broadcasts should be avoided (highly unreliable)
If topology stabilizes, routes must converge to optimal
routes
It is desirable to have a backup route when the primary
route has become stale
11
Routing Classification
The existing routing protocols can be classified as:
 Proactive: when a packet needs to be
forwarded, the route is already known
 Reactive: Determine a route only when there is
data to send
Routing protocols may also be categorized as:
 Table Driven protocols
 Source Initiated (on demand) protocols
 Hybrid protocols
12
Table Driven Routing Protocols



Each node maintains routing information to all
other nodes in the network
When the topology changes, updates are
propagated throughout the network
Examples are:
 Destination Sequenced Distance Vector
routing (DSDV)
 Cluster-head Gateway Switch routing (CGSR)
 Wireless Routing Protocol (WRP)
13
Destination Sequenced Distance
Vector Routing (DSDV)

Based on the Bellman-Ford algorithm

Each mobile node maintains a routing table in
terms of number of hops to each destination

Routing table updates are periodically
transmitted

Each entry in the table is marked by a sequence
number which helps to distinguish stale routes
from new ones, and thereby avoiding loops
14
DSDV

A new route broadcast contains:




Destination address
Number of hops required to reach destination
Sequence number of information received about the
destination
To minimize the routing updates:


Either full dump carrying all available routing
information
Smaller incremental packets containing the change in
information since last full dump
15
DestinationID
15
Dest
NextNode
Dist
SeqNo
2
2
1
22
3
2
2
26
4
5
2
32
5
5
1
134
6
6
1
144
7
2
3
162
8
5
3
170
9
2
4
186
10
6
2
142
11
6
3
176
12
5
3
190
13
5
4
198
14
6
3
214
15
5
4
256
14
13
11
12
9
8
10
4
6
7
5
3
2
1
SourceID
(a) Topology graph of the network
Figure 7.5. Route establishment in DSDV
(b) Routing table for Node 1
16
11
DestinationID
15
Node
Movement
Dest
NextNode
Dist
SeqNo
2
2
1
22
3
2
2
26
4
5
2
32
5
5
1
134
6
6
1
144
7
2
3
162
8
5
3
170
9
2
4
186
10
6
2
142
11
5
4
180
12
5
3
190
13
5
4
198
14
6
3
214
15
5
4
256
14
13
11
12
9
8
10
4
6
7
5
3
2
1
SourceID
Figure 7.6. Route maintenance in DSDV
17
DSDV (Cont.)

Advantages:



Route setup process is very fast
Make the existing wired network protocol apply to ad
hoc network with fewer modifications
Disadvantages:


Excessive control overhead during high mobility
Node must wait for a table update message initiated by
the destination node
 Cause stale routing information at nodes
18
Cluster-head Gateway Switch
Routing (CGSR)






CGSR is a clustered multi-hop mobile wireless network with
several heuristic routing schemes
A distributed cluster-head (CH) selection algorithm is used to
elect a node as the cluster head
It modifies DSDV by using a hierarchical CH to route traffic
Gateway nodes serve as bridge nodes between two or more
clusters
A packet sent by a node is first routed to its CH and then the
packet is routed from the CH to a gateway of another cluster
and then to the CH and so on, until the destination cluster head
is reached
Frequent changes in the CH may affect the performance of the
routing protocol
19
CGSR (Cont’d)
6
12
5
11
4
10
7
2
1
9
8
3
Gateway Node
Cluster Head
Internal Node
Routing in CGSR from node 1 to node 12
20
CGSR (Cont’d)

Advantages:



Better bandwidth utilization
Easy to implement priority scheduling scheme
Disadvantages:



Increase in path length
Instability when cluster-head are high mobility
Battery-draining rate at cluster-head is more than a
normal node
 Frequent changes in the cluster-head = multiple path
break
21
Source-Initiated On-Demand
Routing






Reactive Protocol:
Dynamic Source Routing (DSR)
Ad hoc On-Demand Distance Vector (AODV)
Temporary Ordered Routing Algorithm (TORA)
Associativity Based Routing (ABR)
Signal Stability Routing (SSR)
22
Dynamic Source Routing Protocol
(DSR)



Beacon-less: no hello packet
Routing cache
DSR contains two phases


Route Discovery (find a path)
 Flooding RouteRequest with TTL from source
 Response RouteReply by destination
 If an forwarding node has a route to the destination
in its route cache, it sends a RouteREply to the
source
Route Maintenance (maintain a path)
 RouteError packets are generated when a node
encounters a fatal transmission
23
Routing Discovery
DestinationID
15
14
13
Network Link
11
12
9
RouteRequest
8
10
RouteReply
4
6
7
Path1: 1-2-3-7-9-13-15
Path2: 1-5-4-12-15
Path3: 1-6-10-11-14-15
5
3
2
1
SourceID
Figure 7.10. Route establishment in DSR.
24
DestinationID
15
14
13
Network Link
11
12
9
Selected Path
8
Routing Maintain
RouteError
10
4
6
7
Broken Link
5
3
2
1
SourceID
Figure 7.11. Route maintenance in DSR.
25
DSR (Cont’d)

Advantage




No need to updating the routing tables
Intermediate nodes are able to utilize the Route Cache
information efficiently to reduce the control overhead
There are no “hello” messages needed (beacon-less)
Disadvantage


The Route Maintenance protocol does not locally
repair a broken link
There is always a small time delay at the begin of a new
connection
26
Ad hoc On-Demand Distance Vector
Routing (AODV)
 AODV is an improvement over DSDV, which
minimizes the number of required broadcasts by
creating routes on demand
 Nodes that are not in a selected path do not
maintain routing information or participate in
routing table exchanges
 A source node initiates a path discovery process
to locate the other intermediate nodes (and the
destination), by broadcasting a Route Request
(RREQ) packet to its neighbors
27
AODV (Cont’d)


Every node has a routing table. When a node
knows a route to the destination, it sends a route
reply to the source node
The major difference between DSR and AODV



DSR uses source routing in which a data packet
carries the complete path to traversed.
AODV stores the next-hop information corresponding
to each flow for data packet transmission.
Message types



Route Requests (RREQs)
Route Replies (RREPs)
Route Errors (RERRs)
28
AODV (Cont’d)

RouteRequest packet carries:




RouteReply packet:


SreID, DestID, DestSeqNum, BcastID, and TTL
DestSeqNum indicates the freshness of the route is
accepted
An intermediate node receives a RouteRequest packet.
It either forwards it or prepares a RouteReply if it has a
valid route to the destination
A node receives RouteReply packet will record the
information as the next hop toward the destination
AODV does not repair a broken path locally
29
DestinationID
15
14
13
Network Link
11
12
9
RouteReply
8
10
RouteRequest
Cached Route: 14-15
4
6
7
Path1: 1-5-10-14-15
Path2: 1-5-4-12-15
5
3
2
1
SourceID
Figure 7.12. Route establishment in AODV.
30
Route Maintenance
DestinationID
15
14
13
Network Link
11
12
9
Route for 1 -> 15
8
RouteError
10
4
6
7
Broken Link
5
3
2
1
SourceID
Figure 7.13. Route maintenance in AODV.
31
AODV (Cont’d)

Advantage




Establish on demand
Destination sequences are used to find the latest path to
destination
The connection setup delay is less
Disadvantage



Intermediate node can lead to inconsistent route
Beacon-base
Heavy control overhead
32
Temporarily Ordered Routing
Algorithm (TORA)







TORA is a highly adaptive loop-free distributed
routing algorithm based on the concept of link
reversal
TORA minimizes reaction due to topological
changes
Algorithm tries to localize messages in the
neighborhood of changes
TORA exhibits multipath routing capability
Can be compared with water flowing downhill
towards a sink node
The height metric is used to model the routing
state of the network
Nodes maintain routing information to one-hop
neighbors
33
Link reversal routing algorithms
Updatestream
DownStream
34
TORA (Cont’d)



The protocol performs three basic functions:
--- Route creation
--- Route maintenance
--- Route erasure
A separate directed acyclic graph (DAG) is
maintained by each node to every destination
Route query propagates through the network till
it reaches the destination or an intermediate node
containing route to destination
35
TORA (Cont’d)
 This
node responds with update and sets its height
to a value greater than its neighbors
 When a route to a destination is no longer valid, it
adjusts its height
 When a node senses a network partition, it sends
CLEAR packet to remove invalid routes
 Nodes periodically send BEACON signals to sense
the link status and maintain neighbor list
36
Route Establishing
(logical time, NodeID’, Height’, Height, NodeID)
37
Route Maintenance
(logical time,NodeID’,Height’,Height,NodeID)
38
TORA (Cont’d)



The height metric in TORA depends on logical
time of a link failure
The algorithm assumes all nodes to be
synchronized.
TORA has 5-tuple metric:
 Logical time of link failure
 Unique ID of the node that defined the new
reference level
 A reflection indicator bit
 A propagation ordering parameter
 Unique ID of the node
39
TORA (Cont’d)

The first three elements together describe the
reference level

Oscillation can occur using TORA, similar to
count-to-infinity problem

TORA is partially reactive and partially proactive
40
Hybrid Protocols

Zone Routing Protocol (ZRP)

Fisheye State Routing (FSR)

Landmark Routing (LANMAR)

Location-Aided Routing (LAR)
41
Zone Routing Protocol (ZRP)

Intra-zone routing protocol (Proactive routing)




It is only used in the routing zone.
It brakes all nodes in the routing zone into interior
nodes and peripheral nodes.
Each node maintain routing path to all nodes in the
routing zone by exchanging periodic route update
packets.
Inter-zone routing protocol (Reactive routing)
42
15
14
13
12
9
11
8
10
Routing Zone with Radius = 2
4
6
Routing Zone with Radius = 1
7
5
Network Link
3
1
2
Routing Zone for Node 8
Figure 7.26. Routing Zone for node 8 in ZRP.
43
ZRP (Cont’d)



When a node s has packets to be sent to a node d
 It checks whether node d is with in its zone.
 If d isn’t in the zone, s broadcasts (uses unicast routing)
the RouteRequest to its peripheral nodes.
 If any peripheral node finds d in its zone, it sends a
RouteReply back to s indicating the path.
 Otherwise, the peripheral node rebroadcasts the
RouteRequest again.
The query control must ensure that redundant or
duplicate RouteRequests are not forwarded.
The zone radius has significant impact on the
performance.
44
15
14
13
12
9
11
8
16
10
RouteRequest
4
6
7
5
RouteReply
3
1
Routing Zone with Radius = 2
2
Network Link
Routing Zone for Node 8
Figure 7.27. Path finding between node 8 and node 16.
45
15
14
13
Zone F
Zone E
12
Zone F
Zone E
Zone A
Zone D
Zone B
Zone C
9
11
8
10
4
6
Zone G
7
5
Zone G
Zone A
Zone D
3
1
2
Zone B
(a) Node-level topology in ZHLS
Zone C
(b) Zone topology for the nodelevel topology in (a)
Figure 7.28. Zone-based hierarchical link state routing protocol.
46
ZRP (Cont’d)

Advantage


ZRP reduces the control overhead employed in on-demand
approach and the periodic flooding of routing information
in table-driven.
Disadvantage


In the absence of a query control, ZRP tends to produce
higher control overhead (redundant or duplicate packets).
The decision on the zone radius has a significant impact on
the performance of the protocol
47
Location-Aided Routing

Main Idea




Using location information to reduce the number of
nodes to whom route request is propagated.
Location-aided route discovery based on “limited”
flooding
With the availability of GPS, the mobile hosts knows
their physical locations
Assumption:


Each host in the ad hoc network knows its current
location precisely (location error considered in one of
their simulations)
Source node S knows that destination node D was at
location L at time t0, and that the current time is t1
48
Location-Aided Routing (LAR)




Expected Zone: the destination node is expected
to be presented in the area
Request Zone: the path-finding control packets
are permitted to be propagated in the area
LAR1: the source node specifies the request-zone
in the RouteRequest packet
LAR2: source node includes the distance between
itself and the destination node
49
Expected Zone
Expected zone of D: the region that node S
expects to contain node D at time t1, only an
estimate made by node S
50
Request Zone

LAR’s limited flooding
 A node forwards a route
request only if it belongs
to the request zone
 The request zone should
include
 expected zone
 other regions around
the expected zone

Trade-off between


latency of route
determination
the message overhead
51
Membership of Request Zone

How a node determine if it is in the request
zone for a particular route request?

LAR scheme 1

LAR scheme 2
52
LAR Scheme 1
53
LAR Scheme 2
S knows the location (Xd, Yd)
of node D at time t0
Node S calculates its distance
from location (Xd, Yd): DISTs
Node I receives the route
request, calculates its distance
from location (Xd, Yd): DISTi
For some parameter δ,
If DISTs + δ ≥ DISTi, node I
replaces DISTs by DISTi and
forwards the request to its
neighbors; otherwise discards
the route request
54
Error in Location Estimate


Let e denote the maximum error in the
coordinates estimated by a node.
Modified LAR scheme 1
e+v(t1-t0)
D
(Xd, Yd)
Expected
Zone
55
Expected Zone & Request Zone
15
14
13
12
9
11
8
(X1, Y2+r)
(X2+r, Y2+r)
10
4
6
5
Network Link
r
7
D (X2, Y2)
RoutReply
3
1
S (X1, Y1)
2
ExpectedZone
RoutRequest
(X2+r, Y1)
RequestZone
Figure 7.16. RequestZone and ExpectedZone in LAR1.
56
15
14
13
Destination Node
D (X2, Y2)
9
8
12
11
10
Network Link
4
6
7
5
RoutReply
Source Node
S (X1, Y1)
1
3
2
RoutRequest
Figure 7.17. Route establishment in LAR2.
57
LAR (Cont’d)

Advantage



Reduce control overhead
Increase utilization bandwidth
Disadvantage

Depend heavily on availability of GPS
58
Protocol Characteristics (1/2)
Routing
Protocol
Route
Acquisition
DSDV
Computed a No
priori
DSR
AODV
Flood for
Route
Discovery
On-demand, Yes.
only when
Aggressive use
needed
of caching
may reduce
flood
On-demand, Yes.
only when
Controlled use
needed
of cache to
reduce flood
Delay for
Route
Discovery
Multipath
Capability
Effect of Route Failure
No
No
Updates the routing
tables of all nodes
Yes
Not explicitly.
Route error propagated
The technique of up to the source to
salvaging may
erase invalid path
quickly restore a
route
Yes
No, although
Route error propagated
recent research
up to the source to
indicate viability erase invalid path
59
Protocol Characteristics (2/2)
Routing
Protocol
Route
Acquisition
Flood for
Route
Discovery
Delay for Route Multipath
Discovery
Capability
Effect of Route
Failure
TORA
Ondemand,
only when
needed
Basically one
for initial
route
discovery
Yes. Once the
DAG is
constructed,
multiple paths
are found
Yes
Error is recovered
locally
ZRP
Hybrid
Only outside
a source's
zone
Only if the
destination is
outside the
source's zone
No
Hybrid of updating
nodes' tables within
a zone and
propagating route
error to the source
LAR
Ondemand,
only when
needed
Reduced by
using location
information
Yes
No
Route error
propagated up to the
source
60
Multipath Routing





Multipath provides redundant paths between
source and destination.
Routes are disconnected frequently in ad hoc
networks due to mobility or poor wireless link
quality
Multipath routing could lead to out-of-order
delivery, resequencing of packets at the destination
and increased collision
Can aid in secured routing against denial of service
Various unipath protocols can discover multiple
paths
61
On-Demand Multipath Routing



Extension of DSR protocol
Route discovery by flooding the network query:
two possible extensions
First extension: destination responds to a set of
query packets- source has multiple routes


An intermediate link failure on the primary source
route results in a rote error packet being sent to the
source, which then will use an alternative route
Second extension: destination replies to all
intermediate nodes along primary paths- giving
alternate disjoint routes to all those nodes
62
Multipath Routing
P2
P4
n1
L1
n2
L2
n3
L3
n4
L4
Lk
S
nk+1
D
P3
P1
Route construction and maintenance in On Demand
Multipath Routing Protocol
63
Ad Hoc On-Demand Distance
Vector-Backup Routing





AODV-BR constructs routes on demand
Uses alternate path if primary path disrupted
Utilizes mesh arrangement to provide alternate paths
Two phases: Route Construction and Route Maintenance
Route construction: Source initiates route discovery by
flooding:
 Intermediate nodes stores previous hop and source node
information upon receiving non-duplicate path request
 Mesh construction and alternate paths established
during route reply phase
 Node chooses the best route among multiple route
responses
 When route response reaches the source, primary route
is established
64
Multipath Routing (Cont’d)

Route Maintenance and Mesh Routes




Primary path used unless failure
In case of route failure, one hop data broadcast is
performed
Neighbors having entry to destination in alternate route
table send unicast packet
A node on primary path detects a route failure, sends a
route error packet to source to ensure usage of a fresh
and optimal route that reflects the network topology
65
Multipath Routing: AODV-BR
Primary route
5
Alternate route
2
1
4
6
7
Multiple routes from
Node 1 to Node 7
3
5
1
2
4
3
6
7
Alternate route
used when
primary
disconnects
66
Vehicular Area Network (VANET)


Basic objective is to find some relevant local information, such as close
by gas stations, restaurants, grocery stores, and hospitals
Primary motivation is to obtain knowledge of local amenities
67
VANET (Cont’d)
Hello beacon signals are sent to determine other
vehicle in the vicinity
Table is maintained and periodically updated in each
vehicle
Vehicle in an urban area move out relatively low
speed of up to 56 km/hr while
Speed varies from 56 km/hr to 90 km/hr in a rural
region
Freeway-based VANET could be for emergency
services such as accident, traffic-jam, traffic detour,
public safety, health conditions, etc.
Early VANET used 802.11-based ISM band
68
VANET (Cont’d)
75 MHz has been allocated in 5.850 - 5.925 GHz
band
 Coverage distance is expected to be less than 30 m
and data rates of 500 kbps
 FCC has allocated 7 new channels of in 902 - 928
MHz range to cover a distance of up to 1 km using
OFDM
 It is relatively harder to avoid collision or to
minimize interference
 Slotted ALOHA does not provide good
performance
 Non-persistent or p-persistent CSMA is adopted

69
Vehicular Area Network (VANET)
Characteristic
Urban Area
Rural Area
Freeway-based
1. Connectivity
High
Sparse
Unpredictable
2. Application
Streaming media;
Geographical
emergency information; information
geographical
information
Emergency use
3. Mobility
Low; slow changes in
connectivity
Low medium
High-speed; rapid
changes
in link topology
4. Mobility
pattern
Random road
Most likely
fixed path
Fixed
5. Routing
Geographic
Geographic
Connectivity-aware
Routing
6. Area of
communication
Small region
Small area
Large space
70
Vehicular Area Network (VANET)
Characteristic Urban Area
Rural Area
Freeway-based
7. Delay
Mostly acceptable
Acceptable
Not acceptable
8. Type of
Information
Nearby grocery stores,
restaurants, gas
stations; and hospitals;
rarely for emergency;
safely for pedestrian
or cyclists
Nearby
amenities;
notifying
emergency of
a vehicle
Congestion; detour;
accident; traffic jam;
emergency; road
geometry warning; railroad crossing;
overweight vehicle
9. Volume of
Information
Low to medium
Low:
infrequent
message
Large: frequent data
10. Data
Push
Delivery mode
Push
Pull or Push
11. Security
Requirements
Short term
Relatively long term
Short term
71
Security Issues in MANETs





Missing authorization facilities hinders the usual practice of
distinguishing nodes as trusted or non-trusted
Malicious nodes can advertise non-existent links, provide
incorrect link state information, create new routing
messages and flood other nodes with routing traffic
Attacks include active interfering, leakage of secret
information, eavesdropping, data tampering,
impersonation, message replay, message distortion, and
denial-of-service (DoS)
Encryption and authentication can only prevent external
nodes from disrupting the network traffic
Internal attacks are more severe, since malicious insider
nodes are protected with the network’s security mechanism
72
Disrupting Routing Mechanism by
A Malicious Node







Changing the contents of a discovered route
Modifying a route reply message, causing the packet to be
dropped as an invalid packet
Invalidating the route cache in other nodes by advertising
incorrect paths
Refusing to participate in the route discovery process
Modifying the contents of a data packet or the route via
which that data packet is supposed to travel
Behaving normally during the route discovery process but
drop data packets causing a loss in throughput
Generate false route error messages whenever a packet is
sent from a source to a destination
73
Attacks by A Malicious Node





Can launch DoS attack
A large number of route requests due to DoS
attack or a large number of broken links due to
high mobility
Can spoof its IP and send route requests with a
fake ID to the same destination
Routing protocols like AODV, DSDV, DSR have
many vulnerabilities
Authority of issuing authentication is a problem as
a malicious node can leave the network
unannounced
74
Security Approaches

Intrusion Detection System (IDS)





Automated detection
Subsequent generation of an alarm
IDS is a defense mechanism that continuously monitors
the network for unusual activity and detects adverse
activities
Capable of distinguishing between attacks originating
from inside the network and external ones
Intrusion detection decisions are based on collected audit
data
75
Security Approaches (Cont’d)

Intrusion Response Mechanism (IRM)


Depends on the type of intrusion
Likely responses include: reinitializing communication
channels between nodes, identifying the compromised
nodes, and staring a re-authentication process among
all nodes
76
Requirements for an Intrusion
Detection System





IDS must effectively detect and classify malign and
benign activity correctly
IDS should detect a large percentage of intrusions
IDS must be capable of recovering from system crashes
Intrusion Detection in MANET
 IDS is limited to observing only the traffic coming in
and out of the node
Six functional components of an IDS agent are:
77
Distributed IDS

Anomaly detection procedure:
 The normal profiles i.e., the normal behavior patterns:
are computed using trace data from a traing
procedure
 The deviations from the normal profiles are recorded
during a testing process
 A detection model is computed from the deviation data
to distinguish normalcy and anormalies
78
Mobile Agents



Mobile agents are agents that move around the network
Eliminates the need for moving large volume of data
If some portion of an IDS get destroyed, mobile agents
can still continue to work
79
Local Intrusion Detection System


A common communication framework to facilitate all
external and internal communication with LIDS
Several data collecting agents for different tasks, such as:

A local LIDS agent is in charge of local intrusion
detection and response

Mobile agents collect and process data from remote
hosts any additional investigation

A mobile agent should also be able to protect itself
from malicious mobile agent

MIB variables for mobile and LIDS agents are
obtained from local MIB agent

An SNMP-based agent allows optimized updates and
retrieval of the MIB variables used by intrusion
detection
80
IDS based on Static Stationary
Database



An IDS agent runs on each node as two parts
Mobile IDS agent resides on each node
o Five parts: a local audit trial, a local intrusion database
(LID), a secure communication module, anomaly
detection modules (ADMs), and misuse detection
modules (MDMs)
Stationary secure database
o Signature files of known attacks, established patterns of
users on the network, and the normal traffic flow of the
network
81
Cluster-based Intrusion
Detection System




MANETs can be organized into a number of clusters
A cluster head (CH) is selected that has connections to all
1-hop members
CH assignment must be fair and secure
Should detect Blackhole, packet drop attack, maximum
sequence number attacks, etc.
o Blackhole attack is suction attack where a malicious
node uses the routing protocol to advertise itself as
having the shortest path to the node whose packets it
wants to intercept
o Then drops the entire traffic
o Statistics like number of others packets forwarded,
number of packets originated etc. are collected to
monitor the activity of a node
82
Cluster Formation





Formed by dividing the network into manageable entities
CH also communicates with other clusters for cooperative
detection and response
Cluster management responsibility is rotated among the
capable members of the cluster for load balancing and
fault tolerance and must be fair and secure
Can be achieved by conducting regular elections
The proposed election process does not require the clique
computation or the neighbor information
83
Cluster Head Selection





Initial cluster head setup round composed of two steps:
Clique and Cluster head Computation
A clique is a group of nodes where every pair of members
can communicate through a direct wireless link
Once the protocol is finished, every node is aware of its
fellow clique members
The clique requirement can be relaxed right after the CH
has been identified with has direct links with all members
A count is maintained to remember many times an elected
node has refused to respond
84
Cluster-based Intrusion Detection






CH provides an opportunity for launching collaborative
intrusion detection
Detects intrusions under various attacks such as Blackhole,
routing loop, selfishness, and sleep deprivation in a
MANET environment
At CH, packet analysis of nodes’ traffic analysis reduces
processing at each node
IF CH finds some malicious, it informs its members and the
neighboring clusters to take certain set of actions
IDS can be either host-based or network based
The techniques to detect intrusion can be anomaly
detection or misuse/signature detection
85
Cluster-based Intrusion Detection
Cont.




The IDS can be categorized as misuse detection system or
anomaly detection system
Misuse detection or signature detection system is
generally used for known patterns of unauthorized
behavior
Anomaly detection system identifies intrusions using
‘normal’ activity baseline
Disadvantages of Misuse Detection:
o
Misuse detection system often fails if the database of
attack signatures is not up to date
o The bulk of database cannot be handled due to
memory constraints
86
Logging Module of CHs





CH captures all the traffic in the promiscuous mode
Keeps the data related to traffic such as number of packets
sent, received, forwarded or dropped in a database
Intrusion Information Module
o Every node must maintain a database such as
"intrusion interpretation base“
o Anomalous behaviors must also be well defined with
upper and lower threshold values
Intrusion Detection Module
o Detected by analyzing and comparing the traffic
patterns with normal behavior
o Packet monitoring level can be increased
Intrusion Response Module
o Response may be local to the cluster or global
87
Network Simulators




ns-2
o Utilizes discrete event-driven mechanism to simulate all
kinds of activities in networks
o Four schedulers available in ns-2: linked-list, heap,
calendar queue, and real-time
o Split-language programming
o Open source
o Visualization
o Support of emulation
o Support of mobility models
OPENT Modeler
QualNet
OMNeT++
88
Homework


13.2, 13.7, 13.12,(Due: Dec. 16)
Practice at home: 13.1, 13.13, 13.20
89