부분 버퍼 공유 정책을 가지는 공간-시간 우선순위 대기행렬
Space and Time Priority Queues with Partial Buffer Sharing
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Recently, there have been studies on space and time priority queues, where space priorities are given to a class of packets that are sensitive to loss, and time priorities to another class of packets that are sensitive to delay. However, these studies have been restricted to such models with push-out space priorities. In this paper, we extend the studies to the space and time priority M/G/1 model with partial-buffer-sharing (PBS) space priorities, where the whole buffer is divided into two regions: one is shared by packets of all classes and the other is dedicated only for packets of the higher space-priority class. Since the PBS space-priority mechanism can be implemented more readily in communication systems than the push-out one, there have been a lot of contributions on PBS space-priority queues. However, there are no contributions on space and time priority queues with PBS space priorities. To analyze the proposed queueing model, we first study the probabilistic structure of the service time of a packet, which is more involved to analyze than the push-out alternative because it may be divided into three different regimes: a regime (S-period) from the beginning of the service until the shared buffer region becomes full, a second one (P-period) from the end of the S-period until the whole buffer becomes full, a third one (F-period) from the end of the P-period until the end of the service. Using the distributions of the S-, P-, F-periods, we then construct and analyze the embedded Markov chain and the corresponding semi-Markov process governing the system state, and also derive system performance measures such as expected sojourn times and loss probabilities of different priority classes of packets. In numerical examples, we finally explore the effect of the shared buffer size, which is a major system control parameter of PBS priority queues, and the distributions of the service times of packets of different classes on the system performance measures.
Abstract
Recently, there have been studies on space and time priority queues, where space priorities are given to a class of packets that are sensitive to loss, and time priorities to another class of packets that are sensitive to delay. However, these studies have been restricted to such models with push-out space priorities. In this paper, we extend the studies to the space and time priority M/G/1 model with partial-buffer-sharing (PBS) space priorities, where the whole buffer is divided into two regions: one is shared by packets of all classes and the other is dedicated only for packets of the higher space-priority class. Since the PBS space-priority mechanism can be implemented more readily in communication systems than the push-out one, there have been a lot of contributions on PBS space-priority queues. However, there are no contributions on space and time priority queues with PBS space priorities. To analyze the proposed queueing model, we first study the probabilistic structure of the service time of a packet, which is more involved to analyze than the push-out alternative because it may be divided into three different regimes: a regime (S-period) from the beginning of the service until the shared buffer region becomes full, a second one (P-period) from the end of the S-period until the whole buffer becomes full, a third one (F-period) from the end of the P-period until the end of the service. Using the distributions of the S-, P-, F-periods, we then construct and analyze the embedded Markov chain and the corresponding semi-Markov process governing the system state, and also derive system performance measures such as expected sojourn times and loss probabilities of different priority classes of packets. In numerical examples, we finally explore the effect of the shared buffer size, which is a major system control parameter of PBS priority queues, and the distributions of the service times of packets of different classes on the system performance measures.
참고문헌 (32)
- Arpaci, M., "Buffer management for shared-memory ATM switches", IEEE Communications Surveys & Tutorials, 3(1), pp.2~10 (2000)
- Avrachenkov, K. E., "Priority queueing with finite buffer size and randomized push-out mechanism", ACM SIGMETRICS Performance Evaluation Review, 31(1), pp.324~325 (2003)
- Avrachenkov, K. E., "Priority queueing with finite buffer size and randomized push-out mechanism", Performance Evaluation, 61(1), pp.1~16 (2005)
- Avrachenkov, K., "Randomized push-out disciplines in priority queueing", Journal of Mathematical Sciences, 122(4), pp.3336~3342 (2004)
- Discrete-time models for communication systems including ATM, "Bruneel, H.", ~ (1993)
- Carballo-Lozano, C., "Performance analysis of space-time priority queues", Performance Evaluation, 133, pp.25~42 (2019)
- IEEE INFOCOM’92: The Conference on Computer Communications, "1992"
- Eugster, P., "Admission control in shared memory switches", Journal of Scheduling, 21(5), pp.533~543 (2018)
- Gravey, A., "Mixing time and loss priorities in a single server queue", Proceedings of 13th international teletraffic congress, pp.147~152 (1991)
- Gudimalla, R. K., "Loss behaviour analysis of asynchronous internet switch under self-similar traffic input using MMPP", PH, k queueing system employing PBS mechanism, pp.International Journal of Communication Networks and Distributed Systems, 2017[DOI]
- Gudimalla, R. K., "Performance analysis of wavelength division multiplexing asynchronous internet router employing space priority mechanism under self-similar traffic input—multi-server queueing system with markovian input and erlang-k services", Applied Mathematics, 7(15), pp.1707~1725 (2016)
- Heyman, D. P., "Stochastic models in operations research. 1. Stochastic processes and operating characteristics" (1982), McGraw-Hill
- Huang, J., "Analysis of buffer sharing strategy for satellites in the intermittently connected GNSS satellite network", Proceedings of the ION 2017 pacific PNT meeting, pp.217~222 (2017)
- Kapadia, A. S., "Analysis of a finite capacity non preemptive priority queue", Computers & Operations Research, 11(3), pp.337~343 (1984)
- Kim, K., "Finite-buffer M", G, Mathematical Problems in Engineering, pp.2022, 2022[DOI]
- Kim, K., "(N, n)-preemptive priority queues", Performance Evaluation, 68(7), pp.575~585 (2011)
- Kim, K., "(N, n)-preemptive repeat-different priority queues", Journal of Society of Korea Industrial and Systems Engineering, 40(3), pp.66~75 (2017)
- Kim, K., "Space and time priority queues with randomized push-out scheme", Journal of Korean Society of Industrial and System Engineering, 46(2), pp.57~71 (2023)
- Kim, K., "The analysis of an opportunistic spectrum access with a strict T-preemptive priority discipline", Journal of Society of Korea Industrial and Systems Engineering, 35(4), pp.162~170 (2012)
- Kim, K., "T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks", Computers & Operations Research, 39(7), pp.1394~1401 (2012)
- Kleinrock, L., "Queueing systems, volume 2: Computer applications" (1976), Wiley
- Kroner, H., "Priority management in ATM switching nodes", IEEE Journal on selected areas in communications, 9(3), pp.418~427 (1991)
- Lee, Y., "Queueing system with multiple delay and loss priorities for ATM networks", Information Sciences, 138(1-4), pp.7~29 (2001)
- Lin, A. -M., "Priority queueing strategies and buffer allocation protocols for traffic control at an ATM integrated broadband switching system", IEEE Journal on Selected Areas in Communications, 9(9), pp.1524~1536 (1991)
- Mallikarjuna, B., "An effective management of scheduling-tasks by using MPP and MAP in smart grid", International Journal of Power and Energy Conversion, 13(1), pp.99~116 (2022)
- Perati, M. R., "Performance analysis of asynchronous priority-based internet router under self-similar traffic input-queueing system with markovian input and hyper-exponential services", International Journal of Operational Research, 40(2), pp.239~260 (2021)
- Phan, H., "Packet loss priority of cognitive radio networks with partial buffer sharing", 2015 IEEE international conference on communications (ICC), pp.7646~7652 (2015)
- Reddy, D. M., "Markovian model for internet router employing PBS mechanism under self-similar traffic", AIP Conference Proceedings (2020)
- Ross, S. M., "Stochastic Processes" (1996), John Wiley & Sons
- Sharma, V., "A finite buffer queue with priorities", Performance Evaluation, 47(1), pp.1~22 (2002)
- Takagi, H., "Queueing analysis, volume 1: Vacation and priority systems, part 1" (1991)
- Xue, H., "Packet scheduling for multiple-switch software-defined networking in edge computing environment", Wireless Communications and Mobile Computing, 2018 (2018)