MOBILE COMPUTING (ECS-087)

B.Tech VIII CS / IT

UNIT III
Recommended Books:
. IN
E S
1. T
J. Schiller, Mobile Communications,
O
Addison Wesley
2. Asok K.S Talukder, Mobile Computing-Technology,
Applications & ServiceU N
Creation, TMH
3. T
Raj Kamal,Mobile Computing, Oxford University Press
P IP, Addison Wesley
4. UMobile
Charles Perkins,
5. M.V.D. Heijden, M. Taylor, Understanding WAP, Artech
House

06/18/19 1
 DATA MANAGEMENT IN MOBILE
COMPUTING
• Most mobile technologies physically support broadcast data management
mechanism and a server can take advantage of push to disseminate
information to all mobile clients in its cell. On the other hand, in pull-based
. IN
scheme, clients only access data when needed. These two facts introduce

ES
new mechanisms for data management different from the traditional
algorithms proposed for traditional client-server distributed database
systems
O T
• U N
Mobile Data Management
T
UP
1. Global Data Management (network level):
• Location
• Addressing
• Replication
• Broadcasting, etc.
2. Local Data Management (end user level):
• Energy efficient data access
• Management of disconnection
• Query processing
06/18/19 2
 DATA MANAGEMENT ISSUES IN MOBILE
COMPUTING
The various issues in data management are :

•
IN
Data Dissemination by using Broadcast Data Management.
.
• S
Cache Consistencies and Data Replication
E
• T
Location Data Management (Location specific queries)
O
•
• U N
Issues in sensor data processing and pervasive computing
Location and context aware computing
T
UP
• Disconnection (Voluntary, Involuntary)
• Wireless Medium . Portability
• Speed of wireless link . Handoff
• Scalability . Limited by battery power
• Wireless Security Issues . Mobility
• Transaction Management . Query Processing

06/18/19 3
 Broadcast Data Management Architecture
• What is broadcasted
• trade-off
– periodicity of broadcast
– divergence of the cached copies that
can be tolerated
. IN
• The more the inconsistency tolerated
the less often the updates need to be ES
broadcasted
O T
•
•
Cache coherence preservation
U N
Large communication
P Tdelay
increases the cost of validation of

•
cached objects U
only validates on demand could
reduce validation frequency
– but this approach would worsen
consistency since it increases the
possibility of some old objects being
accesses while disconnected

06/18/19 4
 Cache Consistency
• Caching is useful during frequent relocation and connection to
different areas.
. IN
•
S
alleviate the performance and availability limitations during weak-
connections and disconnections E
• O T
reduce contention on the small bandwidth wireless network
• U N
improve query response time, and to support disconnected or
T
UP
weakly connected operations
• may request different levels of cache consistency Hampered by
disconnection and mobility of clients.
• Solutions:
– Periodically broadcasting the actual data.
– Control information such as lock tables or logs.

06/18/19 5
 Cache Preservation for Disconnection
• Coda’s file system allows the cached objects in
the mobile host to be updated without any co-
ordination. N
. I
ES
• When it is connected, the system propagates the
O T
modifications and detects update conflicts.
N
• Coda proposed three states:
U
– Hoarding T
• UP relies on server replication, always on
Client cache manager
alert for possible disconnection, ensures the critical objects
are cached when disconnected.
– Emulation (upon disconnection)
• Relies solely on the contents of the cache.
– Reintegration (upon reconnection)
• Revalidate all cached objects before use to detect updates at
06/18/19
the server. 6
 Data Replication In Mobile
Computing
• Replication is the process of sharing information so as to ensure
consistency between redundant resources, such as software or
hardware components, to improve reliability, fault-tolerance, or
accessibility. It could be data replication if the same data is stored on
. IN
multiple storage devices, or computation replication if the same

ES
computing task is executed many times. A computational task is
typically replicated in space, i.e. executed on separate devices, or it
O T
could be replicated in time, if it is executed repeatedly on a single

•
device.
U N
It is common to talk about active and passive replication in systems
T
UP
that replicate data or services. Active replication is performed by
processing the same request at every replica. In passive replication,
each single request is processed on a single replica and then its state
is transferred to the other replicas. If at any time one master replica is
designated to process all the requests, then we are talking about the
primary-backup scheme (master-slave scheme) predominant in
high-availability clusters. On the other side, if any replica processes a
request and then distributes a new state, then this is a multi-primary
scheme (called multi-master in database field)

06/18/19 7
 Data Replication In Mobile Computing
• Replication can also occur in one or two directions
– In one way replication, any changes made at the target data bases are not
reflected in the source databases.
– In two way replication, same records can be changed simultaneously at
different locations.
• Generally Replication is expressed in two ways:
IN
– Online Data Replication: In Online data replication over a n/w such as the
.
ES
Internet, the data backup is made on a real time basis where in the data from
the host server is copied onto the remote location as soon as the data is
changed.
O T
– Offline Data Replication : In offline data replication, a backup of the data
N
file is taken on a remote location on an offline basis; such as once a day.
U
•
T
Advantages: Availability ,Parallelism and Better performance

UP
• Disadvantages: Increase the overhead on update, duplicacy
• Areas of usage: Distributed Systems and Databases
• A Replication scheme determines
– The no. of replicas which is referred to as replication level.
– The location of replicas in a distributed system which is referred to as
replication placement.
• Replication scheme configuration is represented by three plans:-
1. Placement Plan 2. Localization Plan 3. Consistency Plan

06/18/19 8
 Data Replication In Mobile Computing

• Backup is different from replication, since it saves a copy of data

unchanged for a long period of time. Replicas on the other hand are
IN
frequently updated and quickly lose any historical state.
•
S .
Asynchronous Replication:- It is a technique for replicating data

TE
b/w database where the system being replicated does not wait for
the data to have been recorded on the duplicate system before
proceeding.
N O
• Advantage:
T U
UP
– It has the advantage of speed, at the increased risk of data loss during
communication or duplicate system failure.
– Asynchronous replication technology is the latest approach to providing
fault tolerance for server and n/w storage.
– Unlike replication technologies, asynchronous technology works by
capturing changes in files at the operating system level. Previous
replication technologies work within applications or at the hardware
layer.

06/18/19 9
 Data Replication In Mobile Computing
• Synchronous Replication:- It is a technique for replicating data b/w
databases where the system being replicated does wait for the data to have
been recorded on the duplicate system before proceeding. Synchronous
replication has the advantage that it is guaranteed that the duplicate system
has a copy of the data, but the disadvantage that the primary system must
wait for the secondary system before proceeding, leading to an increased
response time.
. IN
ES
• Because of the increased response time and communication delays,
synchronous replication is often impractical unless the secondary system is
T
physically located close to the primary system.
O
• Why Asynchronous Replication:?
U N
• Replication can be achieved in two ways –
T
UP
• Synchronous, where consistency of data b/w replicas is strictly maintained.
• Asynchronous, where data consistency is loosely maintained.
• Synchronous replication increases the duration of application transactions &
cannot be completed until all the replicas have been brought to the same
state.
• Asynchronous replication does not prolong the transaction much, as it
updates the replicas in a separate transaction from the application
transaction. Asynchronous rep. is most suitable where latency before
achieving consistency among replicas is permissible.

06/18/19 10
 Data Replication In Mobile Computing
• How Asynchronous
Replication Works:- Appli
catio
• This new approach to server n
& storage replication captures Oper
ating
file changes at the operating Syste

.IN
system level, providing m
FS
improved fault tolerance. Server-

S
User Server- B
1. User changes a file, executes A

a transaction or enters new

info into a database. TE TCP/IP

2. Data flows from the user to

N O
the server’s application layer,
operating system & file
T U File System

UP
system in close to real time. Filter Drive

3. Data then flows to the storage

h/w.
4. The file system filter driver
captures a copy of the data &
sends a copy to the server B Storage H/W

as bandwidth .
Storag
5. Server B now has a back-up e
copy of data which is then
stored in h/w.

06/18/19 11
 Data Replication In Mobile Computing
• Users of mobile computers access a large no. of databases online via wireless n/ws.
• It is important that mobile computers access online database in a way that minimizes
commn. This can be achieved via appropriate data allocation.
• To optimize the commn. cost b/w mobile computers & the stationary computer that
stores the online database, data allocation methods performed in two cost
models –
•
. IN
connection Based – User is charged per minute of connection
•
•
Message Based – User is charged per msg.
ES
E.g. If a User frequently reads a Data-item x & x is updated infrequently, then it is

O T
beneficial for the user to allocate a copy of x to his mobile computer. This way the
reads access the local copy & do not require commn. The infrequent updates are
N
transmitted from the online database to the mobile computer.
U
•
T
In contrast, if the user reads x infrequently compared to the update rate, then a

UP
copy of x should not be allocated to the mobile computer. Instead, access should be
on-demand, every read request should be sent to the stationary computer that stores
the online database.
• Thus, one –copy & two-copies are the two possible allocation schemes of the item x
to the mobile computer.
• In the Second scheme, only stationary computer has a copy of x; whereas in
the First scheme, both stationary & mobile computer have a copy of x.
• In static allocation method, the allocation scheme does not change over time;
whereas in a dynamic one, it does.
• The allocation scheme changes from two copies to one copy as a result of a larger
no. of writes than reads in a window of four minutes.
06/18/19 12
 Data Replication - Issues
• How to manage data replication?
• How to locate objects of interest?
• When do we need to replicate the data on a mobile site?
• How users’ moves affect the replication scheme?

IN
• Is mobile environment requiring dynamic replication schemes?
• Do we need new replication algorithms?
S .
•
TE
Bandwidth Considerations and Data Transfer Rates
• Frequent Network Failures
N O
•
U
MUs often have limited battery-life.
T
UP
• Wireless communication is expensive!
• Locality Migration: If a MU has initiated a transaction, and moves, the
location of the MU within the network must be found prior to
completing the transaction
• Frequent Planned Disconnections
• Recovery Services: Where are we going to store the recovery logs?
• Consistency Semantics: If process are frequently interrupted, they
may leave data objects in an inconsistent state.
• Security
06/18/19 13
• Human interface: How do we pose queries from a handheld device
 Replication Schemes For Mobile Environment
• Eager Replication: It attains replication by keeping all
replicas exactly synchronized at all nodes. This in turn is
achieved by updating all replicas in one transaction. No
concurrency anomalies occur since Neager replication
I
gives serializable execution. EagerS.replication is not a
TE
proper choice for a mobile environment since eager
replication reduced updateO performance with extra
updates, and in a mobile U N
environment the nodes are
normally disconnected.PT
U algorithms are more suited to
• Lazy Replication: These
the mobile environment . The synchronization occurs
after the updating transactions commits. That is,
replication is asynchronous in nature. The problem with
lazy replication is that it may allow a transaction to see a
very old committed value.
06/18/19 14
 Replication Schemes For Mobile
Environment
• Several replication schemes for mobile environments have been proposed are in use.
Some of those are :

. IN
1. Replication achieved through dynamic data allocation :In this method the

ES
switching takes place between one-copy and two-copy schemes
2. Adaptive Data Replication :Adaptive replication is a generalization of the

O T
principle of caching. In adaptive replication the number of copies of an object, the
location of these copies, and which updates are propagated to each copy,
N
change dynamically depending on a given cost function .
U
T
3. Active Replication : Active replication is performed by processing the same request at

UP
every replica.
4. Optimistic Replication: Optimistic replication (also known as lazy replication) is a
strategy for replication in which replicas are allowed to diverge. Traditional pessimistic
replication systems are based on the principle of single-copy consistency. that is, users
should observe the system to behave as if there was only one copy of the data. Optimistic
replication does away with this in favor of eventual consistency, meaning that replicas are
guaranteed to converge only when a system is idle.
5. User Profile Replication:-A dynamic replication scheme which employs user profiles for
recording user' mobility schedules, access behavior and read/write patterns, and actively
reconfigures the replicas to adjust to the changes in user locations and system status.
Simulation results demonstrate that the scheme can accurately predict the data requirement
to facilitate effective replication, reduce response time, and increase data availability.

06/18/19 15
 Issues in Location Data Management

The location of a user can be regarded as a data

item whose value changes with . INevery move
E S
1. How to know the current Tposition of the MU?
N O
2. Where to store the location information?
T U
3. Who should beP responsible for determining
U
and updating of information?
• Location management involves, searching,
reading, informing, and updating

06/18/19 16
 Location Data Mgmt. - Solutions
• Stores the profiles of users currently located in that area for whom
the area is not their home
1. Home Location Register (HLR)
2. Improved: Visitor Location Register (VLR)
•
. IN
Decomposing PCS (Personal Communication System) network into
regions and use regional directories.
ES
• T
Per-user caching where geographical areas cache the last known
O
location of certain users for fast lookup.
• U N
Hierarchical distributed database architecture.
T
UP
1. each leaf database covers a specific geographical region
2. maintains location information for all users currently residing in that
region
• assignment of location databases to the nodes of a signaling
network.
• It uses dynamic programming to optimize the mapping.
• maps a database hierarchy to the network configuration, based on
fixed calling and mobility patterns.
06/18/19 17
 Wireless Security Issues
• Handhelds, being small, portable devices, are easily lost or stolen. About 250K
PDAs were lost in US airports during 2002.(Gartner report)
•
IN
Handhelds are frequently used in hostile environments like hotspots, customer

• S .
sites, business partner offices, and industry conferences.
Attackers are drawn to locations where business travelers gather, because
TE
targets are more plentiful and it is easier to go unnoticed.
•
O
Handhelds are also potentially vulnerable to viruses, worms, trojans, and
spyware.
N
• U
Most are Win32 viruses that can be spread from unprotected handhelds to
T
desktops through synchronization, email, or file shares.
UP
– Self-replicating worms like Bugbear, Klez, and Spida flood email and file
servers, delete registry keys, kill processes, disable software, and carry
trojans.
– Trojans can log keystrokes, launch denial of service (DoS) zombies, or let
attackers assume remote control of infected hosts.
– Spyware in cookies and programs like Kazaa are not overtly malicious, but
leak potentially sensitive information about your computing behavior.
• Mobile phones that can download games, ring tones, and other software have
opened a new avenue for hackers to exploit.

06/18/19 18
 Practical Security Strategies for Security

• Set power-on passwords. According to Gartner, the biggest risk

associated with Pocket PCs is that no power-on password is required by
default.
. IN
• Use mobile firewall to block unauthorized handheld network activity
ES
• Defends against port scans, unauthorized requests, unwanted peer-to-
attacks. O T
peer connections, denial of service floods, and other network-borne

U N
• Encrypt sensitive values, database records, key files and folders, or
T
entire compact flash cards..

UP
• Protect traffic sent and received by handhelds. Consider encrypted,
authenticated VPN tunnels to ensure the privacy and integrity of
communication between handhelds and connected networks.
• If credentials must be saved on a handheld, encrypt them.
• Detect and eradicate viruses.
• Backup handheld data regularly. Frequent backups can reduce loss of
data and downtime when a Pocket PC is lost, stolen, wiped clean, or
damaged beyond repair.

06/18/19 19
 Pervasive Computing
• Technology View
– Computers everywhere – embedded into fridges,
.
washing machines, door locks, cars,INfurniture, people
intelligent environment E S
T
– Mobile portable computingOdevices
– Wireless communication N– seamless mobile/fixed
T U
• User View
– Invisible UP
– implicit interaction with your environment
• Augmenting human abilities in context of tasks
• Ubiquitous = mobile computing + intelligent
environment
06/18/19 20
 Context Awareness
• Context defined by:
– "any information that can be used to characterize the situation of
entities."
– Current location . IN
ES
– Need location detection eg GPS or base station
– Indoors – radio beacon, IR
O T
• User activity
– Walking, driving a car, runningU
N
T for a bus – how to detect this?

UP
• Ambient environment
– In theatre, alone, in meeting
• Local resources or services available
• Device capabilities
• Screen, input, processing power, battery life ….
• Current QoS availability – particularly for radio links

06/18/19 21
 Characteristics of wireless communications

• Limited resources:
• Limited memory . IN
ES
• Limited computational power T
• N O
Small screen U
• P T
Limited battery Ulife
• Relatively unreliable
• Variability in resources
• Frequent location updated
06/18/19 22
 Characteristics of mobile elements
• Network Disconnections
• Voluntary or forced
• Predictable or sudden. . IN
• Short disconnections and long ES
• Disconnected operation
O T
• Frequent disconnections
U N
• T
Predictable disconnections
• UP
Physical support for broadcast
• Asymmetry
• Monetarily expensive
• Relatively unreliable
• High bandwidth variability
• Low bandwidth
06/18/19 23
 Portability
• Network Disconnections
. IN
• Voluntary or forced ES
O T
• Predictable or sudden.
U N
T
• UP
Short disconnections and long
• Disconnected operation

06/18/19 24
 Adaptive Clustering For Mobile
Wireless Networks
• Clustering – It can be considered as the most important unsupervised learning
problem. It deals with finding a structure in a collection of unlabeled data.
• Definition of clustering – “The process of organizing objects into groups whose
members are similar in some way.”
•
. IN
A cluster is therefore a collection of objects which are “similar” s/w them & are

•
“dissimilar” to the objects belonging to other clusters.
Clustering : Two approach used for clustering
ES
–
T
Distance : Two or more objects belong to the same cluster if they are close’ according to a
O
given distance. This is called distance-based clustering.

–
U N
Conceptual : Two or more objects belong to the same cluster if this one felines a concept
T
“common” to all that objects, called conceptual clustering.
P
• Goal: To determine the intrinsicU
grouping in a set of unlabeled data.
• Requirements: clustering algo. should satisfy
 scalability
 ability to deal with noise & outliers
 high dimensionality
 interpretability & usability
 dealing with different types of attributes
 discovering clusters with arbitrary shape

06/18/19 25
 Adaptive Clustering For Mobile
Wireless Networks
• Applications: clustering algo. Can be applied in many field
– Marketing – group of customers with similar behaviour
– Biology – classification of plants & animals

IN
– Libraries – book ordering
–
–
S .
Insurance – identifying groups of motor insurance policy holders
Earth quake studies – cluster observed earthquake epicenters
–
–
www – document classification
TE
City planning – identifying groups of houses acc. To their house type
• Clustering Algos. It may be classified as –
– k-means (Exclusive)
N O
– Fuzzy C-means (Overlapping)
T U
UP
– Hierarchical clustering (Hierarchical)
– Mixture of Gaussians ( Probabilistic)
• Architecture:
• In cellular (single hop) n/ws, all stations learn of each other requirements, either directly or
through a control station (eg. BS) making the resource allocation easier. This can be extended to
multi hop n/ws by creating cluster of radio, in such a way that access can be controlled &
bandwidth can be allocated in each cluster. Most clustering Architectures of mobile radio n/ws are
based on the concept of cluster head. Clusterhead acts as a local coordinator of transmission
within the cluster.
• Multihopping : It means the ability of the radios to relay packets from one to another without the
base stations.

06/18/19 26
 Adaptive Clustering For Mobile
Wireless Networks
• In the proposed network architecture, nodes are
organized into non overlapping clusters. The clusters are
independently controlled N dynamically
and .Iare
reconfigured as nodes move. This E S network architecture
has three main advantages.
O T
U N
• First, it provides spatial reuse of the bandwidth due to
node clustering.
P T
U
• Secondly, bandwidth can be shared or reserved in a
controlled fashion in each cluster.
• Finally, the cluster algorithm is robust in the face of
topological changes caused by node motion, node failure
and node insertion/removal.

06/18/19 27
 Adaptive Clustering For Mobile Wireless Networks

• Adaptive Clustering in Mobile Wireless Networks:-

• The clusters are independently controlled & are dynamically reconfigured as node
move. This n/w architecture has 3 main advantage –
•
. IN
It provide spatial reuse of bandwidth due to node clustering bandwidth can be shared

• ES
or reserved in a controlled fashion in each cluster.
Finally, the cluster algo. is robust in the face of topological changes caused by node
motion, node failure & mode insertion/removal.
O T
•
•
U N
Eg. Shows cellular ,model used in wireless networks –
P,Q.R & S are fixed BSs connected by a wired backbone nodes 1 through 8 are
mobile nodes.
T
UP
• A mobile node is only one hop away from a BS.
• Communication b/w two mobile nodes must be through fixed BSs & the wired
backbone.
• If a BS fails, a mobile node may not be able to access the wired n/w in a single hop.
• Thus the, multihop requirement may arise in cellular n/ws. If a BS fails, a mobile
node may not be able to access the wired n/w in a single hop.
• If BS Q fails, node 4 must access BSs P or R through node 2 or node 5, much acts as
a wireless multihop repeaters.

06/18/19 28
 Conventional Cellular Network (Single Hop)

3 7 8

P Q R S
5
. IN
1
2 4
ES
6
O T
N
U When BS Q Fails
Multihop Situation
T
UP
3 7 8

P Q R S
5
1
2 4
6
06/18/19 29
 The Multicluster Architecture:
• The Multicluster Architecture: A major challenge in multihop is the ability to
account for resources so that bandwidth reservation can be placed on then.
• This solution can be extended to multihop n/ws by creating clusters of
radius, in such a way that acces can be controlled bandwidth can be
allocated in each cluster. Most hierarchical clustering architectures based on

IN
the concept of clusterhead.
• .
The clusterhead acts as a local coordinator of transmissions within the
cluster. S
• TE
It differs form the base station concept in current cellular systems, in that it

N O
does not have special h/w in fact is dynamically selected among the set of
stations. However, it does extra work w.r.t. ordinary stations & therefore it
T U
may become the bottleneck of the cluster . The objective of the proposed

UP
clustering algorithm is to find an interconnected set of clusters covering the
entire node population.
• The clustering Algorithm: in order to support multimedia traffic, the wirelss
n/w layer must guarantee Qos (bandwidth & delay) to real time traffic
components.
• To provide Q.s to multimedia, consists of following two steps-
• 1. Partitioning: of the multihop n/w into clusters, so that controlled,
accountable bandwidth sharing can be accomplished in each cluster.
• 2. Establishment: of virtual circuits with Q.S. guarantee.

06/18/19 30
 The Multicluster Architecture:
• Objective:- of the clustering also is to partition the n/w into several
cluster .
•
IN
Within each cluster, node can communication with each other in
.
•
atmost two hops.
ES
The cluster can be constructed based on node ID
•
O T
Assumptions underlying the construction of the algo in a radio n/w
• N
A1: Every node has a unique ID know the IDs of its 1 hop neighbors
U
• T
A2 : A msg sent by a node is received correctly within a finite time

• UP
by all its 1-hop neighbors.
A3: n/w topology does not change during the algorithm execution. In
this algo each node only broadcasts one cluster msg before
the algo. stops and the time complexity is O(|V|) where V is he set
of nodes .
• The clustering algo converges very rapidly. In the worst case, the
convergence is linear in the total number of nodes.

06/18/19 31
 Consider the System Topology
1 14 15
12 13
2
3 11 16 17
10
4
6

19
5
. IN7

18 20
ES
8
O T
9

U N
AfterTClustering
UP
C1 C3
1 14 15 C6
C2 12 13
2
3 11 16 17
10
4
6
5 7
19
18 20 C5
06/18/19 C4 8 9 32
 The Multicluster Architecture:
• After clustering we can find 6 cluster in the system ,
which are {1,2},{3,4,11},{5,6,7,8,9},{10,12,13}
{14,15,16,17}{18,19,20} . IN
weShave to show that
• To prove correctness of the algo E
O T
– every node eventually determines its cluster.
U N
– In a cluster, any two nodes are at most two hops away
T
UP
– the algo. terminates
• In the multicluster architecture , repeaters relay packets
true one cluster to another . every repeater is time
shared among the set of adjacent cluster ,

06/18/19 33
 Cluster maintenance

• Cluster maintenance :- In the dynamic radio n/w

• nodes can change location
• nodes can be removed and
. IN
• nodes can be added
ES
• T
A topological change occurs when a node discount connects , thus
O
altering the cluster structure. System performance is affected by
N
frequent cluster change therefore ,it is imp to design a cluster
U
T
maintenance scheme to keep the cluster infrastructure as stable as
UP
possible the cluster maintenance scheme was designed to minimize
the number of node transitions from, one cluster to another. Two
step are required to maintain the cluster architecture
• Step 1 - check if there is any member of my cluster has moved out
of my locality.
• Step 2 - If step 1 is successful , decide whether I should change
cluster or remove the nodes no is my location from my cluster.

06/18/19 34
 Cluster maintenance
• Fig (a) show there are 5 nodes in the cluster the hop distance is no
more than 2 because of mobility, the topology changes to the
. IN
configuration fig (b) in this nodes 4 is the highest {1,2,3} do not
S
changes cluster however node 5 should either join another cluster
E
or from a new cluster
O T
•
N
Reclustering:- we let the highest connectivity node its neighbors to
U
T
stay in the original cluster remove the other nodes

2 5 UP
2 5
1
1
4 3
4 3

Fig (a)
06/18/19
Fig (b) 35
• Cluster head acts as a local coordinator of transmissions
within the cluster.
• IT differs from the base not have special n/w in jack is
dynamically selected among the set oj stations waver it
does extra work w r t ordinary stationN therefore it may
become the bottleneck of the clusterS.I
• ‘Mobile nodes are partitioned into T Ecluster a cluster head
is selected using a distributed Oalgo.
N
U range of the cluster head
• all nodes in the common
belong to its cluster P
T
U
• A node that is in the common range of two or more
cluster head a called a gateway nodes
• A cluster head change occurs only when two cluster
head come into one cluster or one of the nodes moves
out of the range of all the cluster heads.
06/18/19 36
• Internal Node
• Cluster Head
• Gateway Node
. IN
ES 12
6 O T
U N
5 T 11

4 UP 7 10

2
8 9
1
3

06/18/19 37
 QoS Routing
• Routing :- For a n/w to deliver QOs guarantees that it must reserve control
resources.
Routing is the first step in reservation the routing product first hinds a path
with reservation along the path .The key resource for multimedia QoS support
is bar width bandwidth can be defined as the no of real time connections than
can pass through that node. A node can at most transmit one paket per frame
• QoS Routing scheme
. IN
• S
The goal of the bandwidth routing algo is to find the shortest path such that
E
O T
the free bandwidth is above the minimum requirement in shortest path
computation the weight of each link is equal to 1 in addition to load balancing

U N
our routing scheme also supports the alternative paths. This is very important
in a mobile environment where link will fail because of mobility in such an
T
environment, routing optimality is of secondary importance the routing

UP
protocol must be capable of finding new routes quickly when a topological
change destroys existing routes to this end we propose to maintain secondary
path a which can be used immediately when the primary path fails.
• Each node uses the primary route its packets when the first link on the path
(S,N) fails the secondary stand by path (S,N3 ) will be computed. The
secondary (stand by) route is easily computed using the DSDV algorithm
(Destination sequenced distance vector). Each neighbour of nodes s
periodically inform s of its distance to destination d the neighbor with shortest
dist yields the primary route the runner up yields the second rotue

06/18/19 38
 File System (Motivation)
A distributed file system enables the program to store and access remote file
exactly and allowing to the user to access files from any computer in an
intranet.
Goal:
• efficient and transparent access to shared files within a mobile environment
while maintaining data consistency
Problems:
. IN
S
– limited resources of mobile computers (memory, CPU, ...)
E
O T
– low bandwidth, variable bandwidth, temporary disconnection
– high heterogeneity of hardware and software components (no
standard PC architecture)
U N
T
– wireless network resources and mobile computer are not very

UP
reliable
– standard file systems (e.g., NFS, network file system) are very
inefficient, almost unusable
File system Requirement:
1 Replication 2. Transparency (location, access, mobility, performance,
scaling) 3. Current file update 4. Fault tolerance
5. Consistency 6. Security 7. Efficiency
Solutions
• replication of data (copying, cloning, caching)
• data collection in advance (hoarding, pre-fetching)
06/18/19 39
 File systems - consistency problems
THE big problem of distributed, loosely coupled systems
• are all views on data the same?
IN
• how and when should changes be propagated to what users?
.
Weak consistency
ES
O T
• many algorithms offering strong consistency (e.g., via atomic
updates) cannot be used in mobile environments
U N
• invalidation of data located in caches through a server is very
T
problematic if the mobile computer is currently not connected to the
network
UP
• occasional inconsistencies have to be tolerated, but conflict
resolution strategies must be applied afterwards to reach
consistency again
Conflict detection
• content independent: version numbering, time-stamps
• content dependent: dependency graphs

06/18/19 40
 File systems for limited connectivity
Symmetry
• Client/Server or Peer-to-Peer relations
IN
• support in the fixed network and/or mobile computers
.
• one file system or several file systems
ES
T
• one namespace for files or several namespaces
O
Transparency
U N
• hide the mobility support, applications on mobile computers should
T
UP
not notice the mobility
• user should not notice additional mechanisms needed
Consistency model
• optimistic or pessimistic
Caching and Pre-fetching
• single files, directories, subtrees, partitions, ...
• permanent or only at certain points in time

06/18/19 41
 File systems for limited connectivity II
Data management
• management of buffered data and copies of data
• request for updates, validity of data
. IN
• detection of changes in data
ES
Conflict solving
• application specific or general O T
• errors U N
T
UP
Several experimental systems exist
• Coda (Carnegie Mellon University), Little Work (University of
Michigan), Ficus (UCLA) etc.

Many systems use ideas from distributed file systems such as, e.g.,
AFS (Andrew File System)

06/18/19 42
 CODA( Command Data Availability) file
System
• Coda is a network file system developed as a research project at
Carnegie Mellon University since 1987 under the direction of
Mahadev Satyanarayanan. It descended directly from an older version of
AFS (AFS-2) and offers many similar features. The InterMezzo file system
was inspired by Coda. Coda is still under development, though the focus
has shifted from research to creating a robust product for commercial use.
. IN
• Coda has many features that are desirable for network file systems, and
several features not found elsewhere.
ES
O T
• disconnected operation for mobile computing
• is freely available under a liberal license
U N
• high performance through client side persistent caching
T
• security model for authentication, encryption and access control
UP
• continued operation during partial network failures in server network
• network bandwidth adaptation
• good scalability
• well defined semantics of sharing, even in the presence of network
failures
• Offers two different types of replication
1) Server replication 2) Caching on clients

06/18/19 43
 Coda File System
• disconnected operation for mobile clients
– reintegration of data from disconnected clients

IN
– bandwidth adaptation
• Failure Resilience
S .
– read/write replication servers
– resolution of server/server conflicts T E
– handle of network failures which partitionO the servers
– handle disconnection of clients
U N
• Performance and scalability
P T
performance U
– client side persistent caching of files, directories and attributes for high

– write back caching

• Security
– kerberos like authentication
– access control lists (ACL's)
• Well defined semantics of sharing
• Freely available source code

06/18/19 44
 File systems - Coda I
• Application transparent extensions of client and server
• changes in the cache manager of a client
• applications use cache replicates of files
•
IN
extensive, transparent collection of data in advance for possible
future use („Hoarding“)
S .
Consistency
TE
• system keeps a record of changes in files and compares files
after reconnection
N O
U
• if different users have changed the same file a manual
T
UP
reintegration of the file into the system is necessary
• optimistic approach, coarse grained (file size)

06/18/19 45
 File systems - Coda II
Hoarding
• function of file size and bandwidth Hoard
data whenever you can (when network
connectivity is available) - Hoarding
• user can pre-determine a file list with
priorities
• contents of the cache determined by the list
and LRU strategy (Least Recently Used) . IN
• explicit pre-fetching possible
ES
• periodic updating
O T
• Serve requests from hoard / cache when
disconnected – Emulating
U N
T
• Reconcile the hoard/cache with servers
UP
and propagate updates when you get
back connectivity – Reintegrating / Write
disconnected
Comparison of files
• asynchronous, background
• system weighs speed of updating against
minimization of network traffic
Cache misses
• modeling of user patience: how long can a
user wait for data without an error message?
06/18/19 46
 Venus States
(Disconnected operation)

Hoarding
. IN
ES
Disconnection O T
U N
Weak Strong
T Connection Connection

UP
Connection Write
Emulating Disconnected
Disconnection

06/18/19 47
 Hoarding
• State of normal operation (server connected).
• Venus gets useful data from server into client cache to get ready
for disconnection may occurs.
. IN
ES
• Which data should be cached based on prioritized algorithm
T
which consists of recent reference history and hoard database
O
(HDB).
U N
T
• HDB is entries of pathnames identifying objects that user

UP
explicitly stores ( un-cached).
• Coda determines file priority to place into caches when caches is
in equilibrium.
• Equilibrium is all these conditions are met:
– No un-cached file has higher priority than any cached file.
– Cache is full or no un-cached file has nonzero priority.
06/18/19 48
 Emulation
• State when disconnection occurs.
• Venus performs the jobs of server in cache. It
records sufficient information.IN in the log for
S
replay when it gets to reintegration.
E
• Each log contains system O Tcall arguments and
U N
states of objects referenced by the call for
T
UP
corresponding volumes.
• Venus also keeps its cache and related data
structure in non-volatile storage called
recoverable virtual memory (RVM) in case of
client reboots.
• RVM stores meta-data of replay logs, HDB,
06/18/19 49
cache directories, status blocks.
 Reintegration
• State when server connection is resumed.
• Venus updates changes made in emulation state to server
a volume at a time.
. IN
executed. ES
• Venus shift the replay log to ASVG in server to be

• 4 phases of replay algorithm: O T

U N
- phase 1: log is parsed and reference objects are locked.
T
UP
- phase 2: validate operation in the log.
- phase 3: data transfer
- phase 4: commit and release lock.
At the end, Venus frees replay logs and reset cache priority.
If there are conflicts (write/write) between copies in cache and
in server, there are automatic resolution or manual
correction depending on what was changed.
06/18/19 50
 Structure of a Coda Client

. IN To Coda
ES
O T Servers
Application
U N
T (Cache Manager)
UP
Venus

System Call Interface

Vnode Interface
06/18/19 Coda Mini Cache 51
 Structure of a Coda Client
• Coda client running an application such as browser or opening a file on its
system. Whenever a request is generated by an application it is forwarded to
file system through a system call. A system call is an operation through which
a program asks the kernel for service: for example, when opening the file the

. IN
kernel will want to do a lookup operation to find the inode of the file and
return a file handle associated with the file to the program. The inode
ES
contains the information to access the data in the file and is used by the
generated by system call interface.
O T
kernel, the file handle is for the opening program. This system call is

• N
In computing , an index-node(inode) is adata structure on a tradiitional Unix
U
T
file system. An inode or vnode(virtual file system node) stores all the

UP
information about a regular file, directory, or other file system object.Each file
is associated with an inode, which is identified by an integer number, often
referred to as an i-number or inode number.Inodes store information about
files and directories(folders) such as file ownership, access mode(read write,
execute permissions) and file type. The vnode interface is used to provide
interface between application and kernel for system call.
• Coda client has a Coda mini cache which stores a cache of recently
answered requests from the VFS. This is all managed by Cache manager
(Venus) which will check the client disk cache for required file, and in case of
a cache miss, it contact the servers to ask for that file.

06/18/19 52
 How Coda Works

. IN
ES
O T
U N
T
UP

06/18/19 53
 How Coda Works
• To understand how Coda can operate when the network connections to the
server have been severed, let's analyze a simple file system operation.
Suppose we type: ``cat /coda/tmp/foo'' to display the contents of a Coda file.
. IN
What actually happens? The cat program will make a few system calls in

ES
relation to the file. A system call is an operation through which a program
asks the kernel for service: for example, when opening the file the kernel will
O T
want to do a lookup operation to find the inode of the file and return a file
handle associated with the file to the program. The inode contains the
U N
information to access the data in the file and is used by the kernel, the file
T
handle is for the opening program. The open call enters the virtual file

UP
system (VFS) in the kernel, and when it is realized that the request is for a
file in the /coda file system it is handed to the Coda file system module in
the kernel. Coda is a pretty minimalistic file system module: it keeps a cache
of recently answered requests from the VFS, but otherwise passes the
request on to the Coda cache manager, called Venus. Venus will check the
client disk cache for tmp/foo, and in case of a cache miss, it contact the
servers to ask for tmp/foo. When the file has been located, Venus responds
to the kernel, which in turn returns the calling program from the system call.

06/18/19 54
 How Coda Works
• When the kernel passes the open request to Venus for the first time,
Venus fetches the entire file from the servers, using remote procedure

IN
calls to reach the servers. It then stores the file as a container file in

S .
the cache area (currently/usr/coda/venus.cache/). The file is now an
ordinary file on the local disk, and read-write operations to the file do
TE
not reach Venus but are (almost) entirely handled by the local file

N O
system (ext2 for Linux). Coda read-write operations take place at the
same speed as those to local files. If the file is opened a second time,
U
it will not be fetched from the servers again, but the local copy will be
T
UP
available for use immediately. Directory files (remember: a directory is
just a file) as well as all the attributes (ownership, permissions and
size) are all cached by Venus, and Venus allows operations to proceed
without contacting the server if the files are present in the cache. If the
file has been modified and it is closed, then Venus updates the servers
by sending the new file. Other operations which modify the file system,
such as making directories, removing files or directories and creating
or removing (symbolic) links are propagated to the servers also.

06/18/19 55
 File systems - Little Work

• Only changes in the cache manager of the client

• Connection modes and use
. IN
ES
O T
U N
T
UP

06/18/19 56
 File systems - further examples
Mazer/Tardo
• file synchronization layer between application and local file system
IN
• caching of complete subdirectories from the server
.
if possible ES
• “Redirector” responses to requests locally if necessary, via the network

O T
• periodic consistency checks with bi-directional updating
Ficus
U N
• not a client/server approach
T
UP
• optimistic approach based on replicates, detection of write conflicts,
conflict resolution
• use of „gossip“ protocols: a mobile computer does not necessarily need
to have direct connection to a server, with the help of other mobile
computers updates can be propagated through the network
MIo-NFS (Mobile Integration of NFS)
• NFS extension, pessimistic approach, only token holder can write
• connected/loosely connected/disconnected

06/18/19 57
 Disconnected operation
• Three states of Venus
– Hoarding . IN
• Network is connected ES
• Collect crucial files O T
– Emulation U N
T
UP
• Offline mode
• Venus simulate server
– Reintegration
• Network is connected
• Sync of files

06/18/19 58
 How a user program asks for service from the
kernel through a system call
• The kernel passes it up to Venus, by allowing Venus to read the request from
the character device/dev/cfso. Venus tries to answer the request, by looking in
it’s cache, asking servers, or possibly by declaring disconnection servicing it
in disconnected mode.
•
. IN
Disconnected mode kicks in when there is no n/w connection to any server
action. ES
which has the files; Also if server fails, disconnected operation can come into

•
O T
When the kernel passes the open request to venues for the first time, Venus

U N
fetches the entire file from the servers, using RPC (Remote Procedure Calls)
to reach the servers. It then stores the file as a container file in the cache area.
• T
The file is now an ordinary file on the local disk and read-write operations to

UP
the file do not reach Venus, but are (almost) entirely handled by the local file
system. coda read- write operation take place at the same speed as those to
local files.
• If the file is opened a second time, it will not be fetched from the servers
again,but the local copy will be available for use immediately.
• If the files has been modified and it is closed, then Venus updates the servers
by sending the new file.
• So, Coda caches all the info it needs on the Client, and only informs the server
of updates made to the file system.

06/18/19 59
 From Caching to disconnected
Operation
• As we know that coda caches all info needed to provide access
to the data. When updates to the file system are made, these
. IN
need to be propagated to the server. In normal connected
mode, such updates are propagated synchronously to the
ES
server i.e. when the update is complete on the client, it has
T
also been made on the server. If a server is unavailable, such
O
U N
an operation will incur a time- out error fail. In such cases, the
error must be reported to the calling program. However, the
T
UP
time out can be handled gracefully as follows-
• To support disconnected computers or to operate in the
presence of n/w failures, Venus will not report failures to the
user when an update incurs a time out; Instead, Venus realizes
that when server is unavailable, the update should be logged
on the client. During disconnection, all updates are stored in
the CML, the Client Modification Log, which is frequently
flushed to disk.
06/18/19 60
 Disconnected operation 2/2
• It only provides access to data that was cached.
• When disconnected operation ends, modified
IN files and
. are propagated to
directories from disconnected volumes
E S
the AVSG().
O T
• It is important to avoid
U N cache misses during
disconnected operation. T
U P
• Coda allows a user to specify a prioritized list of files and
directories that Venus should strive to retain in the
cache.
• Disconnected operation can also be entered voluntarily.
• A version vector mechanism is used by Coda to detect
inconsistencies
06/18/19 61
 Application of CODA
• Web server
• Shared files: . IN
S
Eor across an
in, e.g., Beowulf cluster T
enterprise N O
T U
UP NFS is inadequate
• especially where
• mobile/disconnected operation
• WAN

06/18/19 62
 Database systems in mobile
environments
Request processing
• power conserving, location dependent, cost efficient
• example: find the fastest way to a hospital
. IN
Replication management
ES
• similar to file systems
O T
Location management
U N
• tracking of mobile users to provide replicated or location dependent
T
UP
data in time at the right place (minimize access delays)
• example: with the help of the HLR (Home Location Register) inGSM
a mobile user can find a local towing service
Transaction processing
• “mobile” transactions can not necessarily rely on the same models
as transactions over fixed networks (ACID: atomicity, consistency,
isolation, durability)
• therefore models for “weak” transaction

06/18/19 63