A location-based mobility tracking scheme for PCS networks

This paper introduces a location-based locating strategy for Personal Communication Services (PCS) systems. In the proposed scheme, location updates are based on the value of a movement counter. The update of the movement counter is based on information on the locations visited by a mobile terminal (MT) since the last location update. In particular, the cell identifiers and the corresponding movement counter values are maintained in the MT for a part of the visited cells since the last location update. When the MT enters a cell whose identifier is not stored in the MT, the movement counter increases by one. If the movement counter reaches the update threshold, a location update is triggered; otherwise, the cell identifier and the corresponding movement counter value are stored in the MT. When the MT enters a cell whose identifier is in the MT, the movement counter is assigned with the counter value kept in the MT for this cell, and all cells with greater counter values in the MT are removed. The proposed scheme allows the dynamic selection of the update threshold according to each user's calling and mobility patterns. Analytical and simulation models have been developed to compare the proposed scheme with both the movement-based scheme and the distance-based scheme. Results demonstrate that when the call-to-mobility ratio (CMR) is low, the proposed scheme can achieve a significant cost reduction compared to the movement-based scheme. For example, when the CMR is 0.01, a savings of around 25% in the optimal total cost per call arrival is achieved with the proposed scheme. Moreover, the proposed scheme is easier to implement than the distance-based scheme.     

Design and analysis of location management for 3G cellular networks

Location management is a key issue in personal communication service networks to guarantee the mobile terminals to continuously receive services when moving from one place to another. We study two location management schemes, a dynamic movement-based scheme (DYNAMIC-3G) and a static scheme (STATIC-3G), for 3G cellular networks where home location registers, gateway location registers (GLRs), and visitor location registers form a three-level hierarchical mobility database structure. For both schemes, the cost functions are formulated analytically. We prove that there is an optimal movement threshold that minimizes the total cost function of DYNAMIC-3G and propose a binary search algorithm to find the optimal threshold. Furthermore, we present performance evaluation and comparison of the proposed schemes with the previous schemes in 2G cellular networks where the GLR is not present. Our studies validate the optimality of the DYNAMIC-3G scheme and show that the proposed schemes outperform the previous schemes, especially when the remote-local-cost ratio is high. The comparison results between DYNAMIC-3G and STATIC-3G indicate that DYNAMIC-3G should be adopted when the mobility rate is low, and STATIC-3G should be adopted otherwise. Furthermore, DYNAMIC-3G tends to perform better than STATIC-3G when the paging cost is high or the number of cells in a location area is large.     

面向更新密集型应用的内存数据库高效检查点技术

面向更新密集型应用的内存数据库系统,其检查点技术应符合几个关键的要求,包括检查点操作对正常事务处理的干扰尽可能小、能够处理存取倾斜状况、支持数据库系统的快速恢复、提供恢复过程中的系统可用性等.该文提出一种事务一致的分区检查点技术,采用基于元组的动态多版本并发控制机制,避免了读写事务的加锁冲突,提高系统吞吐能力;检查点操作以只读事务形式实现,存多版本并发控制下,避免检查点操作对正常事务处理的堵塞;由于检查点文件是事务一致的,只需要记录事务的Redo 日志信息,在系统恢复过程中,只需要对日志文件进行一遍扫描处理,加快恢复过程;基于优先级的数据分区装载和恢复,使得恢复过程中新事务的数据存取请求迅速得到满足,保证了恢复过程中的系统可用性.由于采用两级版本管理机制以及动态版本共享技术,多版本管理的空间开销降低到可以接受的水平.实验结果表明,文中提出的检查点技术方案获得比模糊检查点技术高27%的系统吞吐量,同时版本管理的空间开销在可接受的范围之内,满足高性能应用的要求.     

Distributed Multi-Level Recovery in Main-Memory Databases

In this paper we present recovery techniques for distributed main-memory databases, specifically for client-server and shared-disk architectures. We present a recovery scheme for client-server architectures which is based on shipping log records to the server, and two recovery schemes for shared-disk architectures—one based on page shipping, and the other based on broadcasting of the log of updates. The schemes offer different tradeoffs, based on factors such as update rates.Our techniques are extensions to a distributed-memory setting of a centralized recovery scheme for main-memory databases, which has been implemented in the Dalì main-memory database system. Our centralized as well as distributed-memory recovery schemes have several attractive features—they support an explicit multi-level recovery abstraction for high concurrency, reduce disk I/O by writing only redo log records to disk during normal processing, and use per-transaction redo and undo logs to reduce contention on the system log. Further, the techniques use a fuzzy checkpointing scheme that writes only dirty pages to disk, yet minimally interferes with normal processing—all but one of our recovery schemes do not require updaters to even acquire a latch before updating a page. Our log shipping/broadcasting schemes also support concurrent updates to the same page at different sites.     

Design and analysis of a fault tolerant hybrid mobile scheme

Mobile computing systems provide users with access to information regardless of their geographical location. In these systems, Mobile Support Stations (MSSs) play the role of providing reliable and uninterrupted communication and computing facilities to mobile hosts. The failure of a MSS can cause interruption of services provided by the mobile system. Two basic schemes for tolerating the failure of MSSs exist in the literature. The first scheme is based on the principle of checkpointing used in distributed systems. The second scheme is based on state information replication of mobile hosts in a number of secondary support stations. Depending on the replication scheme used, the second approach is further classified as a pessimistic or an optimistic technique. In this paper, we propose a hybrid scheme which combines the pessimistic and the optimistic replication schemes. In the proposed scheme, an attempt is made to strike a balance between the long delay caused by the pessimistic and the high memory requirements of the optimistic schemes. In order to find the best ratio between the number of pessimistic to the number of optimistic secondary stations in the proposed scheme, we used fuzzy logic. We also used simulation to compare the performance of the proposed scheme with those of the optimistic and the pessimistic schemes. Simulation results showed that the proposed scheme performs better than either schemes in terms of delay and memory requirements.     

Evaluating location management schemes for third generation mobile networks

Several strategies have been proposed recently to improve the performance of the IS-41 location management scheme. A forwarding pointers' strategy and a built-in memory strategy are proposed to reduce the signaling cost for location update and improve the IS-41 location update procedure. In this paper, we present a performance analysis of each strategy in an arbitrary time interval. In this analysis, users are classified by their call to mobility ratio which is defined as the call arrival rate divided by the mobility rate. We evaluate each of these strategies using this call to mobility ratio in order to come up with a set of recommendations that determine when each strategy is beneficial and for which class of users. We provide also a simplified analysis of the database loads generated by each strategy.     

Checkpointing strategies in database systems and their performance evaluation

A transaction-oriented database system is investigated, where checkpointing is carried out after a certain number of transactions are processed. The design objective is to maximize the system availability given the failure rate, checkpointing time, error recovery time, and other system parameters. Several checkpointing strategies have been proposed and analysed. The effect of error latency is also considered.     

移动网络中基于数据到达速率的数据传输能耗优化策略

数据传输能耗是移动网络能耗的重要部分,提高数据传输能耗效率是优化移动网络能耗的重要课题。考虑数据具有传输延时的要求,研究了基于数据到达速率的数据传输平均能耗最小化问题。利用无线信道质量随机变化的特征,构建基于数据到达速率的平均能耗最小化问题,然后将其转化为最优停止问题,证明最优停止规则存在。最后通过求解最优近视停止规则来获得各侦测时刻的最优传输速率阈值,实现基于数据到达速率的数据传输能耗优化策略。对提出的策略与其他策略就平均能耗、平均传递率和平均调度周期进行了仿真对比,结果表明提出的策略具有较小的平均能耗和较高的平均传递率,取得了较好的能耗优化效果。     

Analytical results for optimal choice of location update intervalfor mobility database failure restoration in PCS networks

When the location information for a mobile user in the Home Location Register (HLR) is corrupted or obsolete, the new arriving calls to the user may be lost. In order to minimize the effect of such HLR mobility database failure, a location update scheme called period location updating is proposed, and the cost analysis is performed. Analytical results for the failure recovery time distribution and the average number of call losses, which are crucial for cost analysis, are presented. The optimal location update period is given analytically as a function of other traffic parameters. This optimal choice of location update period lays the foundation for the adaptive adjustment of the location update period in failure restoration for PCS networks     

基于移动的位置管理策略中最优寻呼研究

位置管理是个人通信网络的一个挑战性问题,用于跟踪移动台,有位置更新与寻呼两个基本操作.在一些知名的位置管理策略中,基于移动的位置管理策略(movement-based location management scheme)具有简单易行的特点:各移动台只需记住所越过的小区边界次数,一旦这个数超过事先定义的一个整数--移动门槛,就进行位置更新操作.在移动台的呼入符合泊松分布,移动台在各个小区的逗留时间符合指数分布的条件下,推导了基于移动的位置管理策略中移动台移动距离的概率分布及平均距离公式,并基于这些概率分布给出了最优顺序寻呼算法.最后,给出数值分析结果,以说明所给出的寻呼策略比其他已有策略更优.     

A mobility support scheme for 6LoWPAN

This paper proposes a mobility support scheme for 6LoWPAN. In the scheme, the control information interaction for the mobile handoff is achieved in the link layer, and the routing of the control information is automatically performed through the network topology, which saves the power and the delay time consumed by the routing establishment. In addition, neither does the mobile entity need a care-of address during the mobility process, nor is involved in the mobile handoff process, which reduces the mobile entity’s power consumption and prolongs its life span. From the theoretical and simulative perspectives, the paper analyzes the performance parameters, including the mobility handoff cost, the mobility handoff delay time and packet loss rate, and the analytical results show that the performance of the scheme is better than other schemes.     

Necessary and sufficient conditions for transaction-consistent global checkpoints in a distributed database system

Checkpointing and rollback recovery are well-known techniques for handling failures in distributed systems. The issues related to the design and implementation of efficient checkpointing and recovery techniques for distributed systems have been thoroughly understood. For example, the necessary and sufficient conditions for a set of checkpoints to be part of a consistent global checkpoint has been established for distributed computations. In this paper, we address the analogous question for distributed database systems. In distributed database systems, transaction-consistent global checkpoints are useful not only for recovery from failure but also for audit purposes. If each data item of a distributed database is checkpointed independently by a separate transaction, none of the checkpoints taken may be part of any transaction-consistent global checkpoint. However, allowing individual data items to be checkpointed independently results in non-intrusive checkpointing. In this paper, we establish the necessary and sufficient conditions for the checkpoints of a set of data items to be part of a transaction-consistent global checkpoint of the distributed database. Such conditions can also help in the design and implementation of non-intrusive checkpointing algorithms for distributed database systems.     

An efficient checkpointing method for multicomputers with wormhole routing

Efficient checkpointing and resumption of multicomputer applications is essential if multicomputers are to support time-sharing and the automatic resumption of jobs after a system failure. We present a checkpointing scheme that is transparent, imposes overhead only during checkpoints, requires minimal message logging, and allows for quick resumption of execution from a checkpointed image. Furthermore, the checkpointing algorithm allows each processorp to continue running the application being checkpointed except during the time thatp is actively taking a local snapshot, and requires no global stop or freeze of the multicomputer. Since checkpointing multicomputer applications poses requirements different from those posed by checkpointing general distributed systems, existing distributed checkpointing schemes are inadequate for multicomputer checkpointing. Our checkpointing scheme makes use of special properties of wormhole routing networks to satisfy this new set of requirements.     

移动IPv6路由优化模型的性能分析和适应性策略

移动IPv6中为解决三角路由(triangle routing,简称TR)问题,采用路由优化(route optimization,简称RO)作为缺省方案.但是,路由优化在减小路由开销的同时引入了新的信令开销,因此,并非在任何情况下路由优化都优于三角路由.目的是对比在不同网络条件下路由优化和三角路由的开销,提出更有效的适应性路由优化策略.采用数学模型进行分析,引入数据到达率、移动切换率及MN(mobile node)和HA(hone Agent),CN(correspondent node)的位置关系等关键参数,得到分别采用RO和TR的总开销的表达式;引入数据到达率和移动率比值(packet-to-mobility,简称PMR)、节点间距离的关系来权衡数据和信令开销,得到总开销随相关参数变化的数值结果;基于这些分析提出了PMRRO(packet-to-mobility route optimization)适应性路由优化策略:以总开销的最小化为目标,以PMR阈值作为指标,通过适应性调整来决策MN和CN之间的路由选择.模拟验证表明,该策略有比单纯采用TR和RO更好的性能,是为移动管理减少开销、提高效率提出的可行方案.     

基于GLR的动态位置管理方法

为平衡位置更新代价和寻呼代价,结合网关位置寄存器的三层数据库结构,设计一种基于移动域的动态位置管理方法。根据移动速度和呼叫到达率调整移动域大小,降低位置管理总开销。根据呼叫移动比选择寻呼策略,优化位置管理性能。仿真结果表明,采用该方法可以获得最优移动阈值。     

Analysis of Checkpointing for Real-Time Systems

Predictable performance in the event of failuresis of paramount importance in most safety critical real-timesystems. Various hardware as well as software fault-toleranttechniques are employed towards this goal among which checkpointingis a relatively cost-effective scheme. Since checkpointing schemesdepend on time redundancy, they could affect the correctnessof the system by causing deadlines to be missed. This paper providesexact schedulability tests for fault tolerant task sets undera specified failure hypothesis and employing checkpointing toassist in fault recovery. The effects of checkpointing strategieson task response time are analysed and some insights for optimalcheckpointing are provided. The emphasis here is on utilizingthis analysis as an off-line design support tool.     

A proxy-based integrated cache consistency and mobility management scheme for client–server applications in Mobile IP systems

In this paper, we investigate a proxy-based integrated cache consistency and mobility management scheme for supporting client–server applications in Mobile IP systems with the objective to minimize the overall network traffic generated. Our cache consistency management scheme is based on a stateful strategy by which cache invalidation messages are asynchronously sent by the server to a mobile host (MH) whenever data objects cached at the MH have been updated. We use a per-user proxy to buffer invalidation messages to allow the MH to disconnect arbitrarily and to reduce the number of uplink requests when the MH is reconnected. Moreover, the user proxy takes the responsibility of mobility management to further reduce the network traffic. We investigate a design by which the MH’s proxy serves as a gateway foreign agent (GFA) as in the MIP Regional Registration protocol to keep track of the address of the MH in a region, with the proxy migrating with the MH when the MH crosses a regional area. We identify the optimal regional area size under which the overall network traffic cost, due to cache consistency management, mobility management, and query requests/replies, is minimized. The integrated cache consistency and mobility management scheme is demonstrated to outperform MIPv6, no-proxy and/or no-cache schemes, as well as a decoupled scheme that optimally but separately manages mobility and service activities in Mobile IPv6 environments.     

基于影子页面和混合日志的MMDB恢复方法

为了提升内存数据库从各种故障中恢复的速度,提出了基于影子页面技术、混合日志策略以及模糊检查点思想的内存数据库恢复方法。在分析内存数据库运行过程中主要的时间消耗点的基础上建立了内存数据库的系统模型,通过分析事务过程和检查点过程,讨论了该恢复策略的执行过程以及优点,讲述了内存数据库在此系统模型和恢复策略下的事务故障和系统故障的恢复过程以及系统的性能分析。     

A Survey of Distributed Database Checkpointing

Checkpointing a database is a vital technique to reduce the recovery time in the presence of a failure. For distributed databases, checkpointing also provides an efficient way to perform global reconstruction. In this paper, we survey and classify previous approaches for checkpointing a distributed database. Since the need for global reconstruction is infrequent in most distributed databases, a less restrictive and less resource-consuming approach to checkpoint distributed databases in an integrated distributed database system is recommended over a transaction consistent checkpoint approach. For a federated or multidatabase system, any type of global consistent checkpoint is difficult to achieve without violating local autonomy.     

Comparative analysis of different models of checkpointing andrecovery

Different checkpointing strategies are combined with recovery models of different refinement levels in the database systems. The complexity of the resulting model increases with its accuracy in representing a realistic system. Three different analytic approaches are used depending on the complexity of the model: analytic, numerical and simulation. A Markovian queuing model is developed, resulting in a combined Poisson and load-dependent checkpointing strategy with stochastic recovery. A state-space analysis approach is used to derive semianalytic expressions for the performance variables in terms of a set of unknown boundary state probabilities. An efficient numerical algorithm for evaluating unknown probabilities is outlined. The validity of the numerical solution is checked against simulation results and shown to be of acceptable accuracy, particularly in the stable operating range. Simulations have shown that realistic load-dependent checkpointing results in performance close to the optimal deterministic checkpointing. Furthermore, the stochastic recovery model is an accurate representation of a realistic recovery