 |
| No items matching your keywords were found. |
Edt Popular
TECHNIQUES TO FACILITATE INFORMATION EXCHANGE IN MOBILE COMMERCE
TECHNIQUES TO FACILITATE INFORMATION EXCHANGE IN MOBILE COMMERCE
Dr.Hari Ramakrishna
Professor, Department of CSE,
Chaitanya Bharathi Institute of technology
Gandipet -500 075, Hyderabad,
dr.hariramakrishna@rediffmail.com
K.Ravi
Asst. Professor
Dept. of Informatics
Alluri Institute of Management Sciences
K.Anil Kumar
Assoc. Professor
Dept. of Informatics
Alluri Institute of Management Sciences
ABSTRACT
Data management issues related to organizing and retrieving information from wireless channels has posed challenges for the database community. In this paper, we discuss data dissemination to mobile clients and present solutions that address the bandwidth and energy limitations resulting from short battery life of the mobile units. We also add a subscription-based data access layer on top of this. Our solutions overall propose a secure and scalable wireless data dissemination architecture. Our broadcast organization and subscription-based access protocols are geared to work hand-in-hand to facilitate a complete content distribution solution via broadcasts.
Keywords: Mobile Information, Exchange, Broadcasting, Secure Data, CBS, VBS
1. INTRODUCTION
As more and more e-commerce applications are brought to the mobile platform, the users have increasingly become reliant on mobile data. Mobile commerce applications cover a wide range from short and multimedia messaging and wireless mail, to downloadable multimedia. Financial services, business-to-business m-commerce, as well as consumer m-commerce are areas that will potentially use mobile data. With the extensive use of location-based services, more data will be available to information providers for relaying to the clients.
All these applications, when deployed, can quickly fill the airwaves and cause service disruption or service quality problems. Therefore, it is important to distinguish the types and priorities of data and design the information exchange protocols accordingly. In the rest of this paper, we will concentrate on "rapidly changing data" that potentially has many users (e.g., stock market data) and present techniques to disseminate the data in an efficient manner.
The challenges of designing and implementing wireless networks are important ones for the telecommunications research community. At the same time, data management issues related to organizing and retrieving information from wireless channels have posed challenges for the database community as well. Some of the software problems, such as data management, transaction management, database recovery, etc., have their origins in distributed database systems. In mobile computing, however, these problems become more difficult to solve, mainly because of the narrow bandwidth of the wireless communication channels, the relatively short active life of the power supplies (battery) of mobile units, and the changing locations of required information due to client mobility. Solutions to such problems should also adequately deal with the requirement of securely accessing data from the wireless channels.
In this paper, we will discuss data dissemination to mobile clients and will first present solutions that address the bandwidth and energy limitations resulting from short battery life of the mobile units. We will then turn our attention to add a subscription-based data access layer on top this. Our solutions overall propose a secure and scalable wireless data dissemination architecture.
This paper is organized as follows. After a brief introduction to the mobile data concept, we first present a general architecture, requirements and trade-offs in designing a data dissemination application. We then present our solutions that provide 1) energy efficient and timely data delivery and access, and 2) subscription-based secure access to wireless data. We provide a brief literature review and outline the significance of our work and future research directions.
2. ARCHITECTURE FOR MOBILE INFORMATION EXCHANGE
In this paper, we present the "broadcasting" paradigm in data dissemination. We first present a mobile architecture and describe the parameters. We then present the two problems that we are addressing in this paper: the broadcasting problem and the subscription-based data access problem.
2.1 MOBILE ARCHITECTURE
A general architecture of a mobile platform was given by Dunham and Helal and is shown in Figure 1. It is a distributed architecture where a number of computers, fixed hosts and base stations, are interconnected through a high speed wired network. Fixed hosts are general purpose computers which are not equipped to manage mobile units but can be configured to do so. Base stations are equipped with wireless interfaces and communicate with mobile units to support data access
Figure 1: A general architecture of a mobile platform
The mobile units are battery-powered portable computers, which move around freely in a restricted area, referred to here as a geographic mobility domain. The size restriction on a unit's mobility is mainly due to the limited bandwidth of wireless communication channels. To manage the mobility of units, the entire geographic mobility domain is divided into smaller domains called cells. The mobile discipline requires that the movement of mobile units be unrestricted within the geographic mobility domain (inter-cell movement).
The mobile computing platform can be effectively described under the client/server paradigm. Thus, sometimes we refer to a mobile unit as a client and sometimes as a user. The base stations are identified as servers. Each cell is managed by a base station, which contains transmitters and receivers for responding to the information processing needs of clients located in the cell. We assume that the size of a cell is such that the average query response time is much smaller than the time required by the client to traverse it. Therefore, it will seldom occur that a user submits a query and exits the cell before receiving the response.
Clients and servers communicate through wireless channels. The communication link between a client and a server may be modeled as multiple data channels or a single channel. We assume a single channel since the objective is the efficient use of the overall bandwidth. We further assume that this channel consists of both an uplink for moving data from client to server and a downlink for moving data from server to client.
2.2 DATABASE ARCHITECTURE AND ITS CHARACTERISTICS
The data in this application is characterized as rapidly changing users often query servers to remain up-to-date. More specifically, they will often want to query the server for their data item of interest. Typical examples of this type of data are stock, weather, and airline information. We assume the following for fully characterizing our mobile database.
1. The database is updated asynchronously, i.e., by an independent external process. Also, such updates arrive with high frequency, signifying that the database is rapidly changing. Examples of such information are stock, weather, etc.
2. Users are highly mobile and randomly enter and exit from cells. There is a parameter called Residence Latency (RL), which characterizes the average duration of a user's stay in the cell.
3. User reference behavior is localized; e.g., some stocks are more popular than others.
4. Servers are stateless, i.e., they maintain neither client arrival and departure patterns nor client-specific data request information. We assume a stateless server, because we believe that the cost of maintaining a stateful server in a mobile environment would be prohibitively expensive. We want to emphasize, however, that our scheme will work with stateful servers as well.
3. BROADCASTING PROBLEM
Wireless networks differ from wired networks in many ways. Database users over a wired network remain connected not only to the network, but also to a continuous power source. Thus, response time is the key performance metric. In a wireless network, however, both the response time and the active life of the user's power source (battery) are important. While a mobile unit is listening or transmitting on the line, it is considered to be in active mode. Assuming a power source of 10 AA batteries and a laptop equipped with CD-ROM and display, estimated battery life in active mode is approximately 2.7 hours.
In order to conserve energy and extend battery life, a clients slips into doze (standby) mode, in which it is not actively listening on the channel. Clients expend significantly less energy in doze mode than in active mode. Therefore, one of the major goals of our scheme is to minimize the amount of time a client must spend in active mode to retrieve the data items it requests.
The problem addressed may be captured by the following question: given that users are highly mobile in their mobility domain, what are good strategies that the server can use to decide on what data to provide? The assumption is that such strategies need to adapt to user demand patterns in the highly mobile environment. We are also interested in the question of retrieval strategies: given that good strategies are found, what are good retrieval algorithms by which users can retrieve/download data from the server, with a minimum of energy expenditure? The basic idea is one of "mixed broadcasting," i.e., automatic as well as on-demand broadcasting.
- We define the following terms:
- Access Time (AT): Access time refers to the time elapsed between query submission and receipt of the response.
- Tuning Time (TT): Tuning time is the duration of time that the client spends actively listening on the channel
The meaning of these terms is illustrated in Figure 2. Consider a client who submits a request at time T0 and receives the response at time T7. In this scenario, if the client listens continuously from the time a query is submitted until the response is received, then
AT = TT = T7 - T0. On the other hand, if the client slips into doze mode intermittently, then TT is noticeably less than AT, significantly reducing battery usage. In this case, AT= T7 - T0, and TT = (T7 - T6) + (T5-T4) + (T3-T2) + (T1-T0).
Figure 2: Access and tuning times
This results in energy conservation, as the client is in active mode for only short periods of time. The question, of course, is how to determine the smallest possible tuning intervals. An ideal approach appears to be providing the client with precise knowledge of when its requested information will be broadcast.
Our aim is to find optimal points in the two-dimensional space of AT and TT. This becomes difficult, because there appears to be a trade-off between AT and TT; attempts to reduce one tend to increase the other. For example, access time is directly related to the size of the broadcast, i.e., AT is smaller for a smaller broadcast size. On the other hand, providing information for selective auto-tuning, i.e., informing the user precisely where its required data is located in the broadcast, reduces tuning time. However, inclusion of such tuning information would increase the overall size of the broadcast by including overhead, which in turn could increase AT. Conversely, eliminating this overhead will reduce AT at the expense of an increased TT, because the user will not know precisely when to tune in.
3.1 SUBSCRIPTION-BASED DATA ACCESS PROBLEM
In this paper, we address another critical problem: providing secure access control in broadcast schemes. To get a feel for this problem, consider the classical broadcast environment, where an information server broadcasts to a large number of clients using a shared channel. Each broadcast consists of a number of data objects that clients are interested in. Each client is interested in a certain number of these objects and subscribes to them. Subscription refers to a contract that each client enters into with an agent, which entitles the client to access a data object for a specific period of time. Once the contracted period for a subscription is over, the subscription is considered to have expired and the client cannot access the data object any longer without resubscribing. Therefore, broadcast protocols should provide adequate security and should scale well with the number of clients using the system.
Subscription-based access to broadcasts necessitates the use of encryption techniques in order to let only the legitimate subscribers to access the broadcasts. Therefore, the broadcast protocols should have the ability to distribute encryption keys to clients in an efficient manner. We present protocols that add a security layer on top of the basic broadcasting model discussed earlier. In this system, a server broadcasts data items over a shared communication channel, and clients tune in to the broadcasts to download their subscribed items. We add an access control layer that involves encrypting the data items and then adding smart controls on top of the encryption logic.
To enable the deployment of such applications, the following functionalities are necessary.
1. A client must only be able to access the data items that it is subscribed to. In other words, the access to all items that a client is not subscribed to must be blocked. An intuitively natural way to tackle this problem is by encrypting the data items in some way.
2. A client must only be able to access items as long as its subscription to that item has not expired. This is a non-trivial problem—clearly, in order to be given access to an item, assuming items are encrypted, a client needs to be provided with some sort of decrypting mechanism to retrieve this item. When its subscription expires, however, the client is still left with the decrypting mechanism, which compromises security. One obvious way of course is to change the security mechanism of a data item every time a subscription expires to that item. This is, however, prohibitively expensive, given the large number of (client, subscribed_item) pairs present in a system of reasonable size.
3. The protocol(s) must be scalable, i.e., increasing the number of clients should not deteriorate the quality of service.
4. FINALLY, THE PROTOCOL THAT IMPLEMENTS THE ABOVE TWO FUNCTIONALITIES MUST PROVIDE AN ADEQUATE LEVEL OF security, i.e., it should not be easy to breach the security provided by the access control mechanism.
4. BROADCASTING SOLUTIONS
Two broadcasting solutions to the broadcasting problem specified above are the Variable Broadcast Size (VBS) and the Constant Broadcast Size (CBS) protocols. These techniques, first proposed in Datta, Celik, Kim, VanderMeer and Kumar, seek to achieve a minimal tuning time while reducing the access time. However, it is important to understand the broadcast structure before explaining the protocols
4.1 BROADCAST STRUCTURE
Broadcast structure refers to the specific broadcast organization that we assume in developing our strategies. It is important to understand this structure in order to properly appreciate our protocols. We assume a (1, m) indexing strategy outlined in Imielinski et al. In this scheme, index information is provided at regular intervals in the broadcast. More specifically, a complete index is inserted m times in a broadcast at regular intervals.
Figure 3 illustrates our broadcast structure. A broadcast is a sequence of data blocks (containing data) and index segments (containing access information) as shown in Figure 3A. Using the (1, m) data organization methodology, an index segment appears every 1/mth of the broadcast, i.e., there are m index segments. Clearly, each of the m data blocks is also of equal size. Each data block is composed of one or more data clusters as shown in Figure 3B, where each data cluster consists of a collection of tuples of a single data item of interest. For example, assume the broadcast consists of stock information, and each tuple is a triple <stock_id, price, market>. In such a scenario, the data items of interest would be represented by stock IDs. Consider a particular stock ID, e.g., IBM. All IBM records would comprise a data cluster. A data cluster may span more than one data block.
Figure 3: Broadcast structure
Data clusters are composed of data buckets shown in Figure 3, which contain data records as well as some tuning information (denoted by the 5-tuple <X,Y,Z,N, EB> in the figure) explained below.
We assume that each client has its own items of interest (e.g., clients are not interested in all stocks, but instead in specific ones). For the purposes of this study, we assume a client has a single data item of interest. As explained above, all records pertaining to this item appear in a specific data cluster which we refer to as the client's Data Cluster of Interest (DCI). Within the broadcast, the data clusters are organized in order of decreasing popularity, such that the most popular item will be broadcast first, and the least popular item will be broadcast last. This helps to reduce the access times for popular items.
An index segment is a series of buckets containing index tuples and some other special tuning information. We first describe the index tuples. Each index tuple consists of a 4- tuple, <K,B,C,EC>, that not only informs the client precisely where the DCI appears in the broadcast, but also provides information about updates to the cluster since the previous broadcast. The structure of the index segment is shown in Figure 3D. K, B, C and EC are defined below.
K:
The cluster's key value (e.g., for an IBM cluster, the key value is IBM).
B:
The ID of the first bucket of the data cluster.
C:
The offset from B to the first dirty bucket (bucket where changes have occurred since the last broadcast) of the data cluster. If all buckets in the data cluster are clean, C takes a default value of -1.
EC:
The time when the cluster is scheduled to be dropped from the broadcast.
The dirty/clean information (i.e., B and C) are included to handle the rapidly changing data scenario explained earlier in this paper. We assume a tree-like structure for the index. Thus, clients must begin reading the index at the root in order to find the pointers to their DCIs.
As mentioned above and shown in Figure 3C and Figure 3D, all buckets, whether index or data, have a special tuple displayed as a 5-tuple <X,Y,Z,N,EB>. This information is provided to orient clients as they initially tune in to a broadcast. The X, Y, Z, N and EB terms are defined as follows.
X:
An offset to the first bucket of the next nearest index segment.
Y:
An offset to the end of the broadcast, i.e., the start of the next broadcast.
Z:
Shows the bucket's type (data or index) and contains tuning information for items updated since the previous broadcast. It can hold one of four possible values: Z = -2 indicates an index bucket. Z = 0 indicates a data bucket and that the bucket is clean, i.e., unmodified since the previous broadcast. Z = i, where i is a positive integer, indicates a data bucket and that the bucket is dirty, i.e., modified since the previous broadcast. Moreover, the actual i value, i.e., the positive integer, is an offset to the next dirty bucket in the same data cluster. Z = -1 indicates a data bucket and that it is the last dirty bucket of the data cluster.
N = 0
Indicates a data bucket and that is the last data bucket of the data cluster.
N = i
Indicates that this is not the last bucket of a DCI, and the offset to next data bucket of the same DCI is i.
EB:
The expected departure time (EDT) of the data item in the bucket. Obviously, the EB value of every bucket in the same data cluster is going to be identical and equal to the EDT of the of the cluster key.
4.2 PROTOCOLS TO SUPPORT ADAPTIVE BROADCAST CONTENT AND EFFICIENT RETRIEVAL
In the following, we describe two adaptive broadcast protocols which seek an optimal balance of access time (quality of service or average query response time) and tuning time for energy consumption.
As mentioned earlier, periodicity is an important parameter in designing broadcast strategies. A periodic broadcast signifies that the broadcast "size" (i.e., number of buckets) is fixed. One can ascribe both advantages (e.g., predictability) as well as disadvantages (e.g., loss of flexibility) to periodicity. To study such effects, we describe two sets of protocols below for the periodic and the aperiodic cases. We refer to the periodic protocol as the constant broadcast size (CBS) strategy, whereas the aperiodic broadcast protocol is termed a variable broadcast size (VBS) strategy.
Finally, note that these protocols support a mixed mode retrieval policy, i.e., when a client arrives in a cell, it first tunes in to the broadcast to see if its DCI is already there. If not, the client explicitly sends a request to the server through the uplink for that item. Thus items may be found readily in the broadcast or may have to be placed "on demand." This policy has been deemed the most "general" policy in the literature.
5. CONSTANT BROADCAST SIZE STRATEGY
We first present the server protocol, i.e., the strategy used by the server in deciding upon the broadcast content. We then present the client protocol, i.e., how the client retrieves data from the broadcast.
5.1 CBS SERVER PROTOCOL
In this strategy, broadcast size is limited, and the broadcast is periodic. Periodicity mandates an equal size for every broadcast (recall that we consider both size and time in terms of buckets). If there are too few requested items to fill the broadcast period, the broadcast will contain dead air. On the other hand, if there are more requested items than space in the broadcast, the server must prioritize requested items to decide which to include in the broadcast set. This prioritization mechanism should simultaneously satisfy two properties: popularity consciousness and avoidance of chronic starvation. Popularity consciousness means that items that are requested more often should have a greater chance of being included in the broadcast than less popular items. Avoidance of chronic starvation means that if a client requests a "less popular" item, it should not be chronically starved, i.e., the item should appear in the broadcast at some point during that client's residence in the cell. At a minimum, our protocol attempts (but does not guarantee) to provide access to a requested data item at least once during a client's probable stay in the cell; that is, within RL time of the request.
A system of priority ranking of items based on two factors, i.e., a Popularity Factor (PF) and an Ignore Factor (IF) is the following:
The popularity factor of item at time T, denoted by identifies the number of clients in the cell at time T who are interested in X. When a client requests X, is increased by 1. However, every time it is incremented, the system records the corresponding time. Let the timestamp of the ith increment be denoted by.. Then, a corresponding decrement of 1 is performed on the value of the popularity factor at time. This reflects the (anticipated) departure of the client whose request caused the ith increment.
The Ignore Factor (IF) is proposed to counterbalance the PF's effect. The IF ensures that less popular but long-neglected items get an opportunity to be included in the broadcast. The IF of a data item X at time t is simply the number of broadcasts that this item has not been included in the broadcast (i.e., ignored) since it was requested and is denoted by
Let TReq be the time the item was requested and PB be the period of the broadcast preset under the constant size strategy. The ignore factor at a time Ti is defined as follows:
Priority computation using IF and PF: An item's priority can be computed based on the following expression:
Where ASF is an Adaptive Scaling Factor which is an exponential weighting factor based on a nearest neighbor approach. Its purpose is to increase the likelihood that items which have been ignored for a long time will appear in the broadcast. PF and IF differ largely in scale; if ASF is relatively low, PF dominates the priority [removed]limited by the number of clients in a cell). If, however, an item has been ignored for a long time, we would like IF to dominate. A larger ASF value will achieve this. ASF is initialized to a base value for 1 for all data items and reset to this base value each time the item is included in the broadcast. It is incremented when the average time the clients have been waiting for a data item exceeds a preset value.
Having explained the underlying concepts, we are now prepared to describe the server protocol for constructing a broadcast. Prior to a broadcast epoch (the time at which a new broadcast is scheduled to begin), i.e., in its broadcast preparation stage, the server prioritizes all items which have been requested, i.e., items with a PF > 0, and sorts the items in order of descending priority. It then adds items to the broadcast set until the broadcast is full. For all requested but excluded items, their IFs are adjusted.
5.2 CBS CLIENT PROTOCOL
We now describe a client protocol designed to cleverly retrieve data from the broadcast in cooperation with the server protocol defined above. When a client senses the need for a particular data item, it begins the retrieval process by tuning in to the broadcast at an arbitrary time and reading a bucket. We remind the reader that the data cluster in the broadcast that holds the item of a client's interest is referred to as the Data Cluster of Interest (DCI).
The random initial probe in a continuous flow of broadcasts creates a large number of tuning possibilities. Note that because we assume a tree-like rather than a linear index structure, the client must start reading from the top of the index segment (i.e., the root). If it does not find a pointer to its DCI (i.e., DCI is not in the current broadcast set), then it requests the item and tunes to the initial index of every succeeding broadcast until either the DCI is found in the broadcast or it departs from the cell.
5.3 VARIABLE BROADCAST SIZE STRATEGY
Having discussed a periodic broadcasting strategy, we now turn our attention to an aperiodic broadcasting scenario. This strategy is called the variable broadcast size (VBS) strategy. Note that while the broadcast size varies across broadcasts, at the start of each individual broadcast the size is known; therefore, the start of the subsequent broadcast is known as well. However, the server has no knowledge beyond that, as it does not know what requests may arrive during the current broadcast.
VBS Server Protocol
The server protocol for VBS is much simpler than that for the constant size strategy. All requested items are included, i.e., all items with a PF greater than 0 are added to the broadcast set. The broadcast length changes as items are added and deleted. Items remain in the broadcast for RL units of time from their latest request and are subsequently dropped from the broadcast set. Within the broadcast, items (i.e., DCIs) are ordered based on descending popularity. Since no item is ignored, there is no notion of ignore factor in VBS.
VBS Client Protocol
The client protocol in this strategy is similar to that of the CBS strategy. The main difference is in the client's response to finding that its DCI is not in the broadcast. Here, if its DCI is not in the broadcast, or if it has missed its DCI and the item will be dropped when the next broadcast is composed, the client requests the item and exits from the protocol. Since its DCI is guaranteed to be in the succeeding broadcast, it begins the retrieval process at the beginning of the next broadcast and finds its DCI in that broadcast.
5.4 PERFORMANCE OF THE CBS AND THE VBS PROTOCOLS
An empirical performance evaluation by means of an extensive simulation study reveals that the CBS and the VBS protocols perform differently under different system characteristics.The Access Time (AT) metric is used to measure the quality of the broadcasting service. The smaller the AT, the faster the clients are receiving their data items from the broadcast. The Tuning Time metric, explained earlier, is originally proposed to approximate the energy expenditure of the clients that download data from the broadcast. A more direct measure of the energy expenditure is the Normalized Energy Expenditure (NEE). NEE is simply the energy spent on average by a client to download a bucket of data. The simulation study allows us to keep track of the energy spent by each client's mobile unit (a combination of the CPU, the disk, the mobile data card, and the display). NEE is derived by dividing the total energy that the client has spent by the total number of data buckets that it has downloaded from the broadcast. In our simulations, a bucket is 128 Bytes.
The simulation results distinguish between the hot and the cold items. Twenty percent of the data items are hot, meaning that they are more popular and requested more often than the cold data items.
The simulation is run for various client arrival rates that reflect the frequency of requests made to the broadcast server. The arrival rates are represented on the horizontal axis in the figures.
The access times for the CBS and VBS protocols corresponding to clients that requested hot and cold clients are shown in Figure 4A and Figure 4B, respectively. The NEEs for the CBS and VBS protocols are shown in Figure 5A and Figure 5B.
Figure 4: Experimental results: [A] AT curves for CBS and VBS hot clients; [B] AT curves for CBS and VBS cold clients
Figure 5: Experimental results— [A] NEE curves for CBS and VBS hot clients; [B] NEE curves for CBS and VBS cold clients
Both sets of curves show that for hot clients, CBS outperforms VBS at all but very low loads, i.e., where the CBS broadcast is not full. Here, the VBS dominates. For cold clients, for all load levels, the VBS protocol either outperforms or performs identically to the CBS protocol. This is reasonable, since the CBS protocol is optimized to provide better service to clients interested in more popular items at the expense of service for cold items
6. SOLUTIONS FOR SECURE DATA ACCESS FROM BROADCASTS
In this paper, we present two protocols that provide secure data access from the broadcasts by the clients: Subscribe, and Drop Groups Both protocols rely on a security layer supported by the communication infrastructure. We explain the protocols and the broadcast structure that incorporates the security mechanism.
6.1 PROTOCOLS TO SUPPORT SECURE DATA ACCESS FROM BROADCASTS
The protocols use encryption techniques to scramble the communication between the data server and the clients. Two types of encryption keys: Client keys and data keys are implemented. For the client keys, a public key cryptosystem such as RSA, used. For data keys, a symmetric system such as DES by is appropriate. The public key of client cj, which is assumed to be known by the server, is denoted by PKj. cj's corresponding private key, which is assumed to be secret to cj, is denoted by SKj. Messages encrypted with PKj can only be decrypted by cj using SKj. Each data item Di has a data key, denoted by DKi, for use in the symmetric system. The data keys are initially known by the server only but will also be securely transmitted to subscribers of Di. New data keys will be chosen as needed to ensure that only current subscribers can read a particular broadcast.
6.2 THE SUBSCRIBE PROTOCOL
In accordance with the basic cryptosystem described above, the SubScribe protocol operates as follows: When broadcasting Di, the server encrypts it with DKi, producing the ciphertext DKi(Di) of Di, denoted by Ti. Ti is included in the data component of the data block corresponding to DKi. Subsequently, only clients knowing DKi are able to access Di. Thus, the data key DKi is included (in an encrypted fashion) in the key component of the data block corresponding to Di. In order to provide maximum efficiency, the data key is only changed when clients drop their subscriptions. The protocol has two components: a server side, or information delivery component, and a client side, or information access component.
6.3 SUBSCRIBE SERVER SIDE PROTOCOL
The server side protocol is responsible for the delivery strategy for data items. It distinguishes between two types of data items: (a) data items whose subscriber set in the current broadcast includes every client who were subscribed to this item in the previous broadcast as well—these items are referred to as NODROP items, and (b) data items not satisfying the previous criterion, i.e., items which have lost some subscribers in the current broadcast. We will refer to these as DROP items. To include a DROP item, say Di, in the broadcast, the server chooses a new data key, DKi, and creates a data block for this item as follows:
1. Data Component: The server encrypts Di with DKi and includes the ciphertext in the data component.
2. Key Component: For each client in the subscriber set of Di, the server encrypts DKi with the client's public key and includes the ciphertext in the key component. In other words the key component of DROP items essentially becomes a concatenation of ciphertext chunks, where each ciphertext chunk represents an encryption of DKi with a specific subscriber's public key.
To include a NODROP item into the broadcast, the server uses the same data key that was used in the previous broadcast for this data item. This is possible due to the fact that using this data key does not compromise security—all prior subscribers are still subscribed to this item. Also, in this case (potentially) substantial savings are realized as the key need not be sent to all the prior subscribers. The server composes the key component by encrypting the data key only for the new subscribers. Existing clients are notified of the fact that the data key remained the same by inserting a special offset value of -1 in an index in front of the data block for that data item. In both the DROP and NODROP cases, index records are created by the server for constructing the two types of indexes described before.
6.4 THE DROP GROUPS PROTOCOL
In the SubScribe protocol, the broadcast is organized in such a way that each data item is encrypted with its own key and is broadcast together with the key information intended for each subscriber. This key information for each client is obtained by encoding the data item key using the public key of the recipient. That is, the broadcast server sends off as many encodings as there are clients. This effectively renders the size of the broadcast unpredictable. Particularly when the number of subscribers is high, the key segment may become very large and significantly increase the size of the broadcast. Obviously, a longer broadcast means a reduced quality of service. Therefore, there is a scalability issue.
The Drop Groups (DG) Protocol is designed to bound the size of the key component in a broadcast regardless of the number of clients in the system.
DG achieves scalability by using a novel grouping criterion. DG assigns each client to predetermined groups and assigns each group a group key valid until the group changes. This is similar to the Group Key approach. In the Group Key protocol, subscribers of an item usually form a group and are given a group key valid until there are drops (i.e., subscription expiration) from the group. When a drop occurs, a new group key must be generated and distributed to remaining subscribers so that the dropped subscribers don't have access to new values of the data item. In DG, however, we propose to further divide the groups of a data item into subgroups using an additional criterion. The new criterion we use is the time to drop, which is simply the amount of time until a client's subscription for a data item expires. Therefore, two subscribers, A and B, of data item i are in the same group if and only if their subscription for i expires at the same time. Of course, in order to achieve this sort of grouping, we have to ensure that subscription expirations are bunched together at discrete epochs. This is done as explained later.
The choice of the time to drop as the grouping criteria is crucial. This is designed to remedy a major problem associated with the group key approach, namely, the key expiration problem in a dynamic environment. In this environment, the period of validity of a key is small, necessitating the generation of a new key frequently. Although key generation is rather fast and cheap, it is costly to distribute this new key to the clients
In DG, since all subscribers in the same group will be dropped at the same time, it is never necessary to issue a new group key and distribute it to the group. Furthermore, when a new client contacts the subscription server, the client is given a group key for each data item that it is interested in. The client then listens to the broadcast prepared by the subscription server and downloads the data items.
The time continuum is divided into subscription epochs such that subscription expirations are only scheduled to happen at the end of an epoch. For example, if the epoch length is 1 hour, and client A wants to subscribe to a data item for 2.5 hours, it must choose to subscribe for either two or three hours. To limit the number of epochs, a limit is set on the horizon of subscription. For example, if a subscription epoch is one hour long, and the horizon is 24 hours, then there are 24 possible subscription epochs that clients may choose from. Note that real-world analogies exist for this scenario: readers may subscribe to journals between 1 and 24 months and receive issues monthly. The server can adjust the duration of an epoch depending on the popularity or subscription patterns of the clients of an item. Given such a framework, given a subscription horizon of H epochs, in the key component, there can be at most H group keys preceding the data item regardless of the number of subscribers in each group. Therefore, if there are d data items with H groups in each, then there will be dH group keys in the broadcast. At the end of each subscription epoch, d groups will be dropped, and d groups will be added, one group per each data item. Essentially, this bounds the number of groups. Clearly, this is a big step towards limiting the size of the broadcast, thus satisfying the scalability requirement.
6.5 DROP GROUPS ARCHITECTURE
In this environment, there are two separate servers, the Subscription Server (SServ) and the Broadcast Server (BServ). When a client wishes to access the service, it first contacts the SServ that handles the subscription requests. After exchanging information with the SServ, the client listens to the broadcast prepared by the BServ until its subscription expires. Once the client contacts the SServ, it communicates the request to the BServ, which incorporates the requested data item in the broadcast.
The two servers need to maintain communication between each other mainly for exchanging information specific to data items. The client needs to contact the SServ but has no interaction with the BServ except for listening to the broadcast.
In DG, client keys are used for communicating with the Subscription Server. Authentication, subscription and the initial key exchange are performed using public and private keys. The group key of a data item Di for epoch k is denoted by GKki. Thus, Rki, the data key for Di encrypted with GKki; i.e. GKki(DKi) is included in the key component of the data block corresponding to Di.
6.6 BROADCAST ORGANIZATION IN DG
The organization of a broadcast implementing the DG protocol is shown in Figure 6. A broadcast starts off with a broadcast index, followed by a sequence of data blocks. The broadcast index segment and all the data blocks contain an orientation header (OH). The OH consists of a single element, namely an offset to the start of the next broadcast. This pointer is intended as a "tuning-aid" for clients
Figure 6: Detailed view of broadcast structure in DG
The Broadcast Index (BI) precedes everything else in a broadcast. The BI consists of index records that hold pointers to each item's data block in the current broadcast. More specifically, an index record consists of a 2-tuple < item id, offset to data block>. A client obtains pointers to its desired data items from the BI and then sleeps, only to wake up at the desired points in time.
The BI is followed by a sequence of data blocks. A data block consists of four parts.
1.
OH that contains the 2-tuple <offset to item (OTI), flag>. The flag bit is set if the item key has changed since the previous broadcast. When clients download the OH, if the flag bit is not set, they don't need to download the Key Segment if they have the key to the data item from the previous broadcast.
2.
Data block index consists of the <group number, offset to key segment (OKS)>. The OKS element associated with client ID cj indicates where cj can find the key information for its group.
3.
The second part in a data block is the key component. It contains key chunks for all the groups subscribed to Di, i.e., it contains Rki for all groups k that have at least one subscriber.
4.
The last part of a data block is the data component. This contains Ti, a data item Di encrypted with data key DKi.
Therefore, a client, upon successfully downloading the key chunk and Ti, can obtain Di
7. SUMMARY
In this paper, we looked at the problem of data organization and access in mobile networks using broadcasts, and subscription-based data access from broadcasts. The protocols presented here provide efficient methods for designing a broadcasting application to counter the effects of infrastructural inadequacies such as low bandwidth and limited battery power. Paper 3 concentrates on deciding the broadcasting strategy (indexing, broadcast organization, and broadcast period). Paper 4 builds upon these results and prescribes a security layer on top of the basic broadcast structure. Any subscription-based access protocol may be implemented with either the constant broadcast strategy or with the variable broadcast strategy. Based on the characteristics of the data, network capacity, and customer needs, the right combination of protocols should be determined.
Our solutions can be implemented in a wide range of data and content delivery applications, ranging from financial data to wireless Internet services. The dynamic content in a Web page can be distributed to the subscribers via broadcasts. The users could cache the static elements of the page (frames, appearance, etc.) and obtain the freshest content (stock quotes, traffic, movie times, etc.) from the broadcasts. Broadcasting is also a good candidate for providing access to enterprise applications: mobile workers can subscribe to data items that they need to run the application, and any updates to the data items can be broadcast using our protocols. The security of such a system is enhanced if an encryption mechanism such as the one described in the Drop Groups protocol is used. The most general case for using our protocols is for content distribution to handheld devices, such as cellular phones and the PDAs (Personal Digital Assistants, such as Palm). Here, either the wireless carrier alone, or a content provider in alliance with the wireless carrier, could operate the broadcasting application.
The broadcasts should be prepared considering the current and near future demands of the clients. For example, assume that the broadcasts are prepared based on the requests of the clients within a geographic area. When new clients come into that broadcast area, their items of interest may not be included in the current broadcast. Then, these clients will have to resubscribe to the broadcast and wait until these items are broadcast. However, if the broadcasts are prepared preemptively, i.e., by estimating the incoming clients' requests, then resubscription can be prevented. To do this, the broadcast application needs to keep track of the movements of the clients in the wireless network. However, keeping track of client movements is both costly and difficult to manage. Therefore, trade-offs between preemptively including the data items in the broadcasts and managing the location information of the clients must be considered. We have started researching this area. We plan to derive analytical solutions that optimize bandwidth utilization and cost of operating the system.
8. REFERENCES
[1]. Acharya, S., Alonso, R., Franklin, M., & Zdonik, S. (1995). Broadcast disks: Data management for asymmetric communication environments. Proceedings of ACM SIGMOD, San Jose, California, pp. 199–210.
[2]. Alonso, R., & Korth, H. (1993). Database issues in nomadic computing. Proceedings of the ACM-SIGMOD.
[3]. Celik, A., & Datta, A. (2000). A scalable approach for subscription-based information commerce. Workshop on Electronic Commerce and Web-Based Information Systems (WECWIS), Milpitas, CA, USA.
[4]. Celik, A., Datta, A., & Narasimhan, S. (2000). Secure data delivery protocols for information commerce in a push-based environment. IEEE Transactions on Systems, Man and Cybernetics, 30 (4).
[5]. Datta, A. (1994). Research issues in databases for active rapidly changing data systems (ARCS). ACM Sigmod Record, 23 (3).
[6]. Datta, A., Celik, A., Kim, J. K., VanderMeer, D., & Kumar, V. (1997). Adaptive broadcast protocols to support power conservant retrieval by mobile users. Proceedings of the Thirteenth International Conference on Data Engineering (ICDE), Birmingham, UK.
[7]. Datta, A., Celik, A., Wright, R., & Biliris, A. (1998). SubScribe: Secure and efficient data delivery/access services in a push-based environment. Proceedings of the International Conference on Telecommunications and Electronic Commerce (ICTEC), Dallas, TX, USA.
[8]. Datta, A., VanderMeer, D., Celik, A., & Kumar, V. (1999). Adaptive broadcast protocols to support efficient and energy conserving retrieval from databases in mobile computing environments. ACM Transactions on Database Systems, 24 (1), 1–79.
[9]. Dunham, M. H., & Helal, A. (1995). Mobile computing and databases: Anything new? ACM SIGMOD Record, 24 (4), 5–9.
[10]. Imielinski, T., & Badrinath, B. R. (1994). Mobile wireless computing: Challenges in data management. Communications of the ACM, 37 (10), 18–28.
[11]. Imielinski, T., Vishwanathan, S., & Badrinath, B. R. (1997). Data on air: Organization and access. IEEE Transactions on Knowledge and Data Engineering, 9 (3), 353–372.
[12]. Kenyon, C., & Schabanel, N. (1999). The data broadcast problem with non-uniform transmission times. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore, Maryland.
[13]. Lo, C.-C. & Chen, Y.-J. (1999). Secure communication mechanisms for GSM networks. IEEE Transactions on Consumer Electronics, 45 (4).
[14]. Oh, J., Hua, A., & Prabhakara, K. (2000). New broadcasting techniques for an adaptive hybrid data delivery in wireless mobile network environment. Proceedings of the IEEE International Performance, Computing and Communications Conference (IPCCC 2000), Phoenix, Arizona.
[15]. Rivest, R., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21 (2).
[16]. Shepherd, S. J. (1995). A high speed software implementation of the Data Encryption. Computers and Security, 14 (4), 349–357.
[17]. Su, C.-J., Tassiulas, L., & Tsotras, V. J. (1999). Broadcast scheduling for information distribution. Wireless Networks, 5 (2).
[18]. Vaidya, N. H., & Hameed, S. (1999). Scheduling data broadcast in asymmetric communication environments. Wireless Networks, 5 (3).
About the Author
K.Ravi
Asst. Professor
Dept. of Informatics
Alluri Institute of Management Sciences
Does the book of Revelations mention TV as medium to usher in the "Mark of the Beast"?
September 7 2007
VeriChip Corporation To Be Featured on Discovery Channel’s MythBusters on Sunday, Sept 9
DELRAY BEACH, FL – September 7, 2007 – VeriChip Corporation (NASDAQ: CHIP), a provider of RFID systems for healthcare and patient-related needs, announced today that the Company and its VeriMed™ Patient Identification System will be featured in a recorded segment on Discovery Channel’s MythBusters on Sunday, September 9, at 11:00 p.m. EDT. In the segment, the MythBusters team debunks the myth that the VeriMed™ microchip is not safe to use with magnetic resonance imaging machines. In addition, one of the hosts of MythBusters volunteers to get a VeriMed microchip on camera.
MythBusters is a television program on the Discovery Channel that tests the validity of various rumors and urban legends in popular culture.
Why don't they debunk the myth that this chip is the Mark of the Beast?
I gotta tell ya, I have absolutely no patience with the "Left Behind" interpretation of the Bible. But stuff like this makes me a little squeamish. Did you see how they're implanting these in Chinese workers? Complete with their medical history - including if they've had children, their employer, their religion? Scary stuff in some ways.
EDT ON LINE 30 -EDSON FARMACIA POPULAR.mov