Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

An Energy-Efficient Concurrency Control Method for Mobile Transactions with Skewed Data Access Patterns in Wireless Broadcast Environments

무선 브로드캐스트 환경에서 편향된 엑세스 패턴을 가진 모바일 트랜잭션을 위한 효과적인 동시성 제어 기법

  • Published : 2006.02.01
Download PDF
⟨ Previous Next ⟩

Abstract

Broadcast has been often used to disseminate the frequently requested data efficiently to a large volume of mobile clients over a single or multiple channels. Conventional concurrency control protocols for mobile transactions are not suitable for the wireless broadcast environments due to the limited bandwidth of the up-link communication channel. In wireless broadcast environments, the server often broadcast different data items with different frequency to incorporate the data access patterns of mobile transactions. The previously proposed concurrency control protocols for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. However, these protocols perform poorly when the data access pattern of update mobile transaction are not uniform but skewed. The update mobile transactions with skewed data access patterns will be frequently aborted and restarted due 4o the update conflict of the same data items with a high access frequency. In this paper, we propose an energy-efficient concurrence control protocol for mobile transactions with skewed data access as well as uniform data access patterns. Our protocol use a random back-off technique to avoid the frequent abort and restart of update mobile transactions. We present in-depth experimental analysis of our method by comparing it with existing concurrency control protocols. Our performance analysis show that it significantly decrease the average response time, the amount of upstream and downstream bandwidth usage over existing protocols.

브로드캐스트는 하나 또는 여러 개의 채널을 이용해서 다수의 모바일 클라이언트들이 빈번하게 필요로 하는 데이타를 효과적으로 전송하기 위한 방법 중의 하나이다. 무선 브로드캐스트 환경에서는 채널의 상향 대역폭의 한계로 인해 기존의 동시성 제어 기법은 적합하지 않다. 무선 브로드캐스트 환경에서 서버는 종종 모바일 클라이언트의 접근 패턴을 고려하여 편향된 접근 빈도를 갖는 서로 다른 데이터 아이템을 브로드캐스트 하기도 한다. 무선 브로드캐스트 환경에서 모바일 트랜잭션을 위한 기존의 제안된 동시성 제어 기법들은 일정한 데이타 접근 패턴에 중점을 두고 있다. 하지만, 기존의 기법들은 데이터의 접근 패턴이 일정하지 않고 편향된 경우에는 오히려 심각한 성능 저하를 발생시킨다. 편향된 데이타 접근패턴을 갖는 갱신 모바일 트랜잭션들은 높은 접근 빈도를 같은 데이타를 동시에 접근하고자 하는 다른 모바일 트랜잭션들 간의 충돌로 인해 실행이 취소되고 재실행될 것이다. 본 논문에서는 일정한 데이타 접근패턴뿐만 아니라 편향된 데이타 접근 패턴을 갖는 모바일 트랜잭션을 위한 에너지 효율적인 동시성 제어기법을 제안한다. 본 논문에서는 임의 백오프 기법을 통해 갱신 모바일 트랜잭션의 빈번한 실행 취소와 재실행을 방지한다. 우리는 기존의 동시성 제어 기법과의 비교를 통해 본 논문에서 제안하는 기법을 심층적으로 분석한다. 또한 실험을 통해 기존의 기법들에 비해 평균 접근 시간, 상향 및 하향 통신 대역폭의 사용량이 현저히 줄어드는 것을 보임으로써 제안하는 기법의 성능을 검증한다.

Keywords

References

  1. S. Acharya, M. Franklin, S. Zdonik, and R. Alonso, 'Broadcast Disks: Data Management for Asymmetric Communication Environments,' Proc. ACM SIGMOD International Conference on Management of Data, pp. 199-210, 1995 https://doi.org/10.1145/223784.223816
  2. S. Acharya, M. Franklin, and S. Zdonik, 'Balancing Push and Pull for Data Broadcast,' Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 183-194, 1997 https://doi.org/10.1145/253260.253293
  3. P. A. Bernstein, V. Hadzilacos, N. Goodman, 'Concurrency Control and Recovery in Database Systems,' Addison Wesley, Massachusetts, 1987
  4. H. Cho, 'Concurrency Control for Read-Only Client Transactions in Broadcast Disks,' IEICE Trans. Commun., vol.E86-B, no.10, 2003
  5. V. Lee, K-W. Lam, T-W Kuo, 'Efficient validation of mobile transactions in wireless environments,' The Journal of Systems and Software, pp.183-193, 2004 https://doi.org/10.1016/S0164-1212(03)00084-0
  6. Shanmugasundaram, J., Nithrakashyap, A., Sivasankaran, R., Ramamritham, K., 'Efficient concur-rency control for broadcast environments,' In: ACM SIGMOD International Conference on Management of Data, 1999 https://doi.org/10.1145/304182.304190
  7. E. Pitoura, P. K. Chrysanthis, 'Scalable Processing of Read-Only Transactions in Broadcast Push,' ICDCS, Austin, TX, 432439, 1999 https://doi.org/10.1109/ICDCS.1999.776545
  8. P. A. Franaszek, J. T. Robinson, and A. Thomasian, 'Access invariance and its use in high contention environments,' IBM Res. Rep. RC 14704, 1989
  9. P. A. Bernstein, Va. Hadzilacos, N. Goodman, 'Concurrency Control and Recovery in Database Systems,' Addison Wesley, Massachusetts, 1987
  10. Kung, H. T., Robinson, J. T., 'On optimistic methods for concurrency control,' ACM Transactions on Database Systems 6(2), pp. 213-226, 1981 https://doi.org/10.1145/319566.319567
  11. Lee, V.C.S., Kwok-Wa Lam, Son, S.H., 'On transaction processing with partial validation and timestamp ordering in mobile broadcast environments,' IEEE Transactions on computers, 51, 10, pp. 1196-1211, 2002 https://doi.org/10.1109/TC.2002.1039845
  12. II Young Chung, Bhargava, B., Mahoui, M., Lilien, L., 'Autonomous transaction processing using data dependency in mobile environments,' Distributed Computing Systems, 2003. FTDCS 2003. Proeedings. The Ninth IEEE Workshop on Future Trends of, 28-30, pp 138-144, 2003 https://doi.org/10.1109/FTDCS.2003.1204325
  13. Haerder, T., 'Observations on optimistic concurrency control schemes,' Information Systems 9 (2), 1984 https://doi.org/10.1016/0306-4379(84)90020-6
  14. Yu, P. S., DIAS, D. M., 'Analysis of hybrid concurrency control schemes for a high data contention environment,' IEEE Transactions on Software Engineering, 18, 2, pp. 118129, 1992 https://doi.org/10.1109/32.121754
  15. P. S. Yu, D. M. Dias, 'Impact of large memory on the performance of optimistic concurrency control schemes,' in Proc. Int. Conf. on Databases, Parallel Architectures, and their applications (PARBASE-90), (Miami Beach, FL), pp, 86-90, Mar. 1990 https://doi.org/10.1109/PARBSE.1990.77120
  16. P. S. Yu, D. M. Dias, S. S. Lavenberg, 'On modeling database concurrency control,' IBM. Yorktown Heights, NY, Res. Rep. RC 15386, 1990
  17. H. D. Schwetman, 'CSIM: A C-based Process Oriented Simulation Language,' Proceeding 1986 Winter Simulation Conference, 1986 https://doi.org/10.1145/318242.318464
  18. Mesquite Software, Inc, CSIM18 Simulation Engine USER'S GUIDE, 1987-1994
  19. D. Knuth, 'The Art of Computer Programming Second Edition, Vol Ill,' Addison Wesley, 1998
  20. G. K. Zipf, 'Human Behaviour and the Principle of Least Effort: An Introduction to Human Ecology,' Addison Wesley Press, Cambridge, Massachusetts, 1949
  21. J. Gray, P. Sundaresan, S. Englert, K. Baclawski and P. Weinberger, 'Quickly Generating Billion-record Synthetic Databases,' Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994 https://doi.org/10.1145/191839.191886
  22. T. Imielinski, S. Viswanathan, B. Badrinath. 'Data on air: Organization and acces,' IEEE Transactions on Knowledge and Data Engineering, 9(3):353-372, 1997 https://doi.org/10.1109/69.599926
  23. S. K. Lee, C. S. Hwang, Kitsuregawa, M. 'Using predeclaration for efficient read-only transaction processing in wireless data broadcast,' IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on, 15(6): 15791583, 2003 https://doi.org/10.1109/TKDE.2003.1245294