Transcript A Transaction Model to Improve Data Availability in Mobile Computing

Highly Available and Secure
Fault-tolerant Mobile
Computing
Sanjay K. Madria
Department of Computer Science
University of Missouri-Rolla
[email protected]
1
Mobile Constraints
Low bandwidth.
Frequent disconnections but predictable.
High bandwidth variability.
Monetarily Expensive.
Broadcast is physically supported in a cell.
Limited battery power and storage.
Fast changing locations.
2
MH – Mobile Host
MSS – Mobile Support Station
Cell
MH
MH
Fixed
Host
MH
MSS
MSS
MH
Fixed Network
Mbps to Gbps
MSS
MSS
Fixed Host
Fixed Host
MH
Cell
MH
MH
MH
Cell
Trusted Part
Wireless connection (unreliable)
Fixed and dedicated connection (reliable)
Mobile Architecture.
3
Objectives

To Improve Data Availability in Mobile
Computing

- Transaction models for mobile computing
(Journal Paper appeared in DPDB’01)

To provide Secure Fault-tolerant Mobile
systems
– To provide uninterrupted secure service to the
mobile hosts when base station moves or fails.
(Paper in IC Internet Computing’00 and Research
Grants of 80K)
4
How Mobile Transactions are different ?

Long-lived transactions due to the mobility and
frequent disconnection.

To split computations, some of which execute on
mobile host while others on MSS.

To share partial results with others.

Computations and communications supported by
MSS.

Mobile hosts move from one cell to another, but the
execution must continue
5
 To maintain mutual consistency of data objects
Prewrite Mobile Transaction Model

Introduce a prewrite operation before a write
operation; makes visible (the exact or abstract) the
value that data object will have after the commit of the
transaction.

pre-committed – MT has announced all the prewrites
values and read all the required data objects, but has
not been finally committed (updates on database are
not performed).

A pre-committed MT’s results are made visible at MH
and MSSs before the final commit.
6

Shifts the resource consuming part of the MT’s
execution (updates of the database on disk) to the
MSS.

Pre-committed avoids costly undo or
compensating action.

Pre-read returns a prewrite value whereas a read
returns a write value.

MTs are serialized based on their pre-commit
order.
7
Example 1: Long-duration Transaction
Application
 “House-construction” and “House-buying”
Transactions
– “Model House” as prewrite
Example 2: Data Structure Application

Record Delete Operation in Hashing
 Storage allocator and deallocator to work
concurrently
8
Mobile Transaction Processing with
Prewrites

MH has limited server capability
Start________Reads/Prewrite________Pre-commit________Writes_________Commit
Part of transaction executed at MH

Part of transaction executed at MSS
Example – News-reporter Transaction

MH has very slow CPU and small memory; I/O device
only.
 Example – Image Retrieval Transaction
9
Concurrent Operations
Case 1: Suppose a pre-read is currently being
executed at MH and at the same time, the
transaction that has announced the prewrite
values finally commits at MSS
T1__________r(x),pw(x)_______pc_______ w(x)_______c At MSS
T2____ pr(x) __________ c At MH
Time
10
Case 2: Consider
a case where a read
transaction commits at MH after the
transaction that announced the prewrite
operation, has been pre-committed.
T1__________r(x),pw(x)_______pc_______w(x)________c
T2__________r(x)__________c At MH
At MSS
Time
11
Operation Compatibility Matrix
Pre-read
Read
Pre-write
Write
Pre-read
Yes
Yes
No
Yes
Read
Yes
Yes
Yes
No
Pre-write
No
Yes
No
Yes
Write
Yes
No
Yes
No
12
Performance
(Simulation Parameters)
System Parameters
Description
Value
DB-size
Average size of the database
500
Num-MH
Number of MHs
Simulation parameter
Num-MSS
Number of MSSs
2
Trans-size
Average no. of objects per
transaction
6 objects
Pre-value-size
Average size of pre-write values
1/40 of write value
Max-Size
Maximum number of objects per
transaction
10 objects
Min-Size
Minimum number of objects per
transaction
2 objects
Local-object-MH
Ratio of objects found in cache at
MH
0.4
CPU-time
Time taken by CPU per request
12 msec
13
Simulation Parameters (Table continued)
I/O Time
Time taken by I/O per request both 30 msec
at MSS and MH
Num-transactionsMSS
Transactions at each MSS
Simulation parameter
Wireless-bandwidth
Data transfer rate from MH to
MSS
0.5 Mbps
Write-prob
Probability that object read will be Simulation parameter
written also
Trans-delay
Inter-arrival delay time
500 msecs
Prewrite-to-write
Delay in write
0.2 msecs
14
Throughput v/s MPL
Write-prob = 1/2
5
4.5
4
Throughput
3.5
2PL
3
WDL
2.5
OL
2
PTM
1.5
1
0.5
0
0
1.2
2
4
6
8
10
12
14
15
17
20
MPL
15
Throughput v/s MPL
12
Write-prob = 1/4
Throughput
10
8
2PL
WDL
6
OL
PTM
4
2
0
0
1.2
2
4
6
8
10
12
14
15
17
20
MPL
16
Transaction-Abort-ratio v/s MPL
Write-prob = 1/2
4
Transaction Abort-Ratio
3.5
3
2PL
2.5
WDL
2
OL
1.5
PTM
1
0.5
0
0
1.2
2
4
6
8
10
12
14
15
17
20
MPL
17
Transaction-Abort-ratio v/s MPL
Write-prob = 3/4
4
Transaction Abort-Ratio
3.5
3
2PL
2.5
WDL
2
OL
1.5
PTM
1
0.5
0
0
1.2
2
4
6
8
10
12
14
15
17
20
MPL
18
Serializable Schedules in Mobile Transaction Model
Case 1: In case of simple data objects, a history with a
prewrite is same as the history without a prewrite.
Case 2: Once a transaction’s prewrite-lock is updated to the
write-lock, it can not acquire any other lock.
Case 3: A prewrite-lock can not be updated to a write-lock
if some other transaction is holding a conflicting lock.
Case 4: A transaction, which returns an old value, can be
serialized in the history
19
Multi-version Model to Exploit
Availability in Mobile Computing

Start State, Commit, Termination
 MH process ops, but Terminate at MSS
 One Terminated version, but many
committed version
 MSS terminates them in–order of
commitment
20
Read-write Availability
MH
commit
Xi0
Zkts(k)
Xjts(j)
---
Transaction Tj
MSS
terminate
Xi0
Zi0
Zkts(k)
Transaction Tk
21
Write-Write Availability
MH
MSS
Two committed
versions
Xkts(k)
Xjts(j)
Zkts(k)
---
Transaction Tj
Xi0 Xkts(k)
Zi0
Zkts(k)
Transaction Tk
22
Fault Tolerant Authentication
in Mobile Computing
23
Objective

To provide uninterrupted secure service to
the mobile hosts when base station moves
or fails.
– Example – Battle Field
24
Mobile IP Entities

Mobile Host (MH) - Changes its point of
attachment to the internet from one link to
another.
 Home Agent (HA) - Router on MH’s home
network which tunnels datagrams (packets
of data) to MH when it is away from home.
 Foreign Agent (FA) - Router on MH’s
visited network which provides routing
services to the MH while registered.
25

To ensure security and theft of resources (like
bandwidth), all the packets originating inside the
network should be authenticated.
 MH sends a packet to its HA along with the
authentication information.
 Authentication is successful-> HA forwards the
packet. Otherwise, dropped.
Mobile Node
Authentication and
Forwarding Services
Arbitrary
Internet
Topology
Home Agent
26
Disadvantages of Typical Setup

Home Agent becomes a single point of
failure.

Home Agent becomes an attractive spot for
attackers.

Not scalable – large number of hosts overload
the Home Agent.
27
Research Goals

Eliminate the single point of failure.

Distribute the load and enhance scalability
and survivability of the system.

Failures -- transparent to applications

Easy to implement
28
Traditional Approaches

Using a Proxy Server that takes up the
responsibilities of the Base Station

Using a Second Base Station that forwards
the packets to the actual Home Agent, using
Mobile IP, which is now at a Foreign
Network.
29
Proxy-based solution
Destination Network
BS1
Source Network
Arbitrary Network
Arbitrary Network
BS
Foreign Network
30
Traditional Approaches
Disadvantages:

Manual updating of the routing tables
 Not transparent to applications
 Communication Delays
 Additional security threats as the packets
now traverse long paths through Internet.
31
Proposed Schemes

We propose two schemes:
– Virtual Home Agent
– Hierarchical Authentication

They differ in the architecture and the
responsibilities that the Mobile Hosts and
Base Stations hold.
32
Authentication Using Virtual
Home Agent
Entities in the proposed scheme
 Virtual Home Agent(VHA) is an abstract
entity identified by a network address.

Master Home Agent(MHA) is the physical
entity that carries out the responsibilities of
the VHA.
33
Authentication Using Virtual
Home Agent

Backup Home Agent(BHA) is the entity
that backs-up a VHA. When MHA fails,
BHA having the highest priority becomes
MHA.

Shared Secrets Database Server is the entity
that manages and processes the queries on
the secret database.
34
Virtual Home Agent Set up
VHA ID = IP ADDR1
Master Home Agent(MHA)
Database Server
Shared Secrets
Database
Backup Home Agents
Other hosts in the network
35
Protocol Description

All the MHAs and BHAs join a preconfigured multicast group.

MHA and each BHA is assigned a priority
that indicates its preference to become a
MHA, when the current MHA fails.

MHA has the highest priority at any given
point of time.
36
Protocol Description

Periodically, MHA sends an advertisement
packet to the configured multicast group.

Purpose of this advertisement packet is to
let the BHAs know that MHA is still alive

Time-to-live is set to 1 in each
advertisement as they never have to be
transmitted outside the network.
37
Protocol Description


Advertisement Packet Format
VHA’s ID
MHA’s
priority
Authentication Information
VHA’s ID indicates the VHA that this Agent
is the Master.
 MHA’s priority is the priority of this MHA.
 Authentication Information is necessary to
void the masquerading attacks (i.e. anybody
posing as a Master after compromising it).

38
Protocol Description

BHAs only listen for advertisements, they do not
send the advertisements.

If a BHA did not receive any advertisement for
some period, starts the Down Interval Timer,
computed as follows

Down Time Interval = 5*Advertisement Interval
+ ((MHA’s priority-BHA’s priority)/MHA’s
priority)
39
Protocol Description

Down Interval Time takes care of packet
losses (as it is atleast 5 advertisement
intervals)

Down Interval Time is a function of BHA’s
configured priority (if the priority is more,
Down Interval Time is less).
40
Protocol Description

Down Interval Timer of the BHA having the
highest priority will expire first and that
guarantee BHA transitions from BHA to
MHA.

New MHA sends advertisements from now
onwards.
41
Protocol Description
Advantages of this Election Protocol

No communication between the BHAs is
required.
 There is no confusion about which BHA
becomes MHA (only the one whose timer
expires first)
 No additional security threats (like
manipulating priorities of BHAs)
42
Protocol Description
Backup State
Start State
Master State
State Transitions
43
Advantages of the proposed
scheme

Has only 3 states and hence the overhead of state
maintenance is negligible.

Very few tasks need to be performed in each state

Flexible – there could be multiple VHAs in the
same LAN and a MHA could be a BHA for
another VHA, a BHA could be a BHA for more
than one VHA at the same time.
44
Hierarchical Authentication
Scheme

Multiple Home Agents in a LAN are
organized in a hierarchy (like a tree data
structure).

A Mobile Host shares a key with each of the
Agents above it in the tree (Multiple Keys).

At any time, highest priority key is used for
sending packets or obtaining any other kind
of service.
45
Hierarchical Authentication
Scheme
A
K2
Database
B
K1
C
Database
D
E
F
G
(K1, P1)
(K2, P2)
46
Hierarchical Authentication
Scheme
Key Priority depends on several factors and
computed as cumulative sum of weighted
priorities of each factor.
Example factors:
 Communication Delays
 Processing Speed of the Agents
 Secret Key Usage
 Life Time of the Key
 Configurable Priorities
 Availability of secret key information to an
Agent
47
Hierarchical Authentication
Scheme

Hosts detect the Home Agent’s failure or
mobility when the Home Agent does not
send an acknowledgement for a request.

When the failure is detected, host reduces
the priority of the current key and picks up
highest priority key to be used now
onwards.
48
VHA Scheme
 Flat structure
 Host has only one key
Failure
is transparent to the
user

No Priority is assigned to
the keys
Hierarchical Scheme
 Tree structure
 number of keys depend on
height of the tree.
 Hosts should be aware of
the failure of BS as which key
to be used depends on the base
station serving it.
 Each key has priority, the
key with the highest priority is
used for authentication.
49
Cluster for scalability
One IP Add.
Requests
Request
Distribution
Front End
Clients
Back-end
50
Locality-Aware Request Distribution
R1,R1,R1,R1,R1
Cache
R1
R1,R1,R1,R2,R3,R2,R1,R1,R2,R3
Back-end nodes
Front-end node
R2,R3,R2,R2,R3
Cache
R2, R3
51
Back-end Forwarding
Forwarded Request
Host
Front-end
Back-end nodes
52
Request Redirection
1. Request
Front End
2. Redirect to Back End
Front End
3. Redirected Request
Back-end
53
Conclusions

Discuss Transactions design to Increase
Data Availability (Application Oriented)
 Flat-model and tree based schemes for
fault-tolerant authentication in mobile
environment (System Oriented)
54
Future work

Quantifying the priorities for each factor
and computing the overall key priority as a
weighted function of all these factors.
 Designing a adaptable replication and
partitioning scheme for secret keys that
increases the system performance.
 Simulation of these approaches and
obtaining performance statistics.
55
Current Projects

WAP and WML for Web Engineering on
Mobile Platforms
– Different Approach to Content Management
and caching
– Developing Device dependent Software for
web Access (minimum number of clicks,
textual input, reduce latency)
– Requirement Engineering (capturing,
structuring, and accurately representing users
requirements)

Data, operational, functional constraints
– Performance and Design constraints
56
References

IP Mobility Support - RFC 2002.
 Group Key Management Protocol (GKMP)
Architecture - RFC 2094.
 Key Management for multicast : Issues and
Architectures - RFC 2627.
 Secure Group Communications using Key
Graphs, Chung Kei Wong, Md. Gouda
57
Concurrency Control and Locking
Pre-Read-Lock(X): Grant the requested pre-read-lock to a
transaction T on X if no other transaction holds a prewritelock on X.
Read-Lock(X): Grant the requested read-lock to a transaction T
on X if no other transaction holds a write-lock on X.
Prewrite-Lock(X): Grant the prewrite-lock to a transaction T on X
if no other transaction holds are Prewrite- or pre-read-lock on
X.
(continued……….)
58
Write-Lock(X): Update a prewrite-lock on X held by a
transaction T to write-lock if
Begin
If the write-lock-wait queue for X is empty then
Begin
If the transaction T is pre-committed and no other
transaction holds a read-or write-lock on X then convert
prewrite-lock to write-lock;
End;
else
Begin
put the transaction T in a write-lock-wait queue for X;
End;
End.
59
Serializable Schedules in Mobile Transaction Model
1. Ti  { pri(x), ri(x), pwi(x), wi(x)x is a design object}  {pci, ci,
a i}
2. If ai  Ti if and only if pci  Ti and ci  Ti
3. If it is ci or ai then for any other operation p  Ti , p <i t and if t is
pci, then pci <i ci.
4. If pri(x), ri(x), pwi(x), wi(x)  T then either pri(x) <i wi(x), or
wi(x) <i ri(x), or ri(x) <i wi(x), pwi(x) <i pri(x) or pwi(x) <i wi(x),
or pri(x) <i ri(x).
Consider a set of transactions in T=(T1 , T2 …… Tn ) which are
modeled by a structure called a history. Formally [BHG], a
history H over T is a partial order
(, <n) where
i) H = nUi=1 Ti;
ii) <H  nUi=1 <i ; and
iii) for any two conflicting operations p and q either p <H q or q <H
60
p.
Case 1: In this case we consider simple data objects and see that a
history with a prewrite is same as the history without a prewrite.
Consider the following history H:
pwl1(x)pw1(x)rl2(x)r1(x)rul1(x)c2pc1(pwl1(x) wl1(x))prl3(x)pr3(x)
prul3(x)c3w1(x)wul1(x)c1
After taking into account these commutative operations, the above
history will be Equivalent to:
rl2(x)r2(x)rul2(x)c2pwl1(x)pw1(x)pc1(pwl1(x) wl1(x)) prl3(x) pr3(x)
prul3(x)c3w1(x) wul1(x)c1
Consider another history H’:
pwl1(x)pw1(x)rl2(x)r2(x)rul2(x)c2pc1(pwl1(x) wl1(x))pwl3(x)pw3(x)
pc3w1(x)wul1(x)c1(pwl3(x)  wl3(x))wl3(x)wul3(x)c3
61
Case 2: In this case we see that once a transaction’s prewrite-lock is updated to
the write-lock, it can not acquire any other lock.
Consider the following history:
pwl1(x)pw1(x)pc1(pwl1(x) wl1(x))prl2(x)pr2(x)pwl2(y)pw2(y)pc2
(pwl2(y)  wl2(y))w2(y)prul2(x) wul2(x)c2w1(x) rl1(y)r1(y)rul1(y)wul1(x)c1
Case 3: In this case, we see that a prewrite-lock can not be updated to a write-lock
if some other transaction is holding a conflicting lock.
Consider a partial history:
rl1(x)r1(x) pwl1(x) pw1(x)rl2(x)r2(x) pc1(pwl1(x)  wl1(x))
Consider another partial history:
pwl1(x) pw1(x) pc1(pwl1(x) wl1(x)) plw2(x) pw2(x)w1(x) pc2(pwl2(x)  w2(x))
Case 4: In this case, we see that a transaction, which returns an old value, can be
serialized in the history.
Consider a history:
rl1(x)r1(x)pwl1(x) pw1(x)rl2(x)r2(x)pc1rul2(x)c2(pwl1(x)  wl1(x))
62
Proof of Correctness
Property 1: If o is an operation then ol(x) < o(x) < ou(x).
Property 2: If pi(x) and qi(y) are two operations under Ti then pli(x) <
quli(y),
i.e., for all lock operations li  Ti and un-lock operations uli  Ti , li <
uli
Property 3: If (pwli(x)wli(x))  Ti then
1) For any operational oli  Ti , oli <i (pwli(x)wli(x)). That is, once a
prewrite-lock is converted to a write-lock, no other operation can
lock any data object.
2) For any operational puli  Ti, (pwli(x) wli(x)) < puli(x).
That is, a prewrite-lock is converted to a write-lock before any lock
is released.
63
Property 4: If pi(x) and qj (x) are two conflicting operations then
either
1) puli(x) <H qlj(x). If pi(x) is a prewrite operation then
(pwli(x)wli(x)) <H qlj(x).
If pi(x) is a read operation then pulj(x) <H (pwlj(x)wlj(x)). or
2) qulj(x) <H pli(x). If qj(x) is a prewrite operation then
(pwlj(x)wlj(x)) <H pli(x).
If qj(x) is a read operation then qulj(x) <H (pwli(x)wli(x)).
Property 5: If pci and ci are pre-commit and commit then pci <i ci in Ti
and for any pcj, if pci < pci then ci < ci . However, if the transaction
Tj is a read-only transaction and pci < prj then cj < ci or ci < cj .
Property 6: If pci  Ti then no ai  Ti.
Property 7: If pwi(x), wi(x)  Ti and pwj(x), wj(x)  Tj and if Ti  Tj
then
1) If pwli(x) < pwlj(x) then wli(x) < wlj(x).
2) If wli(x) < pwlj(x) then pwlj(x) < wi(x) < wlj(x) or wli(x) < pwj(x)
64
< wj(x).
Lemma 1: If T1  T2 in SG(H) then there exists an unlock operation
pul1  T1 or a lock convert operation (pwl1  wl1)  T1 such that
for all lock operations
ql2 T2 or a lock convert operation (pwl2  wl2)  T2 , pul1(x) <
ql2(x) or
(pwl1(x)  wl1(x))< ql2(x) or pul1(x) < (pwl2(x) wl2(x)).
Lemma 2: Let T1  T2  ….  Tn be a path in SG(H) where n>1.
Then for data objects x and y and some operations p1(x) and qn(y)
in H, pu1(x)< qln(y) or
(pwl1(x)  wl1(x))< qln(y) or pul1(x) < (pwln(y) wln(y)).
Theorem : Every history H obtained by the locking protocols given
before is serializable.
65