The main objectives of this dissertation are to analyze Markov models of the multichannel carrier sense multiple access with collision detection (MCSMA/CD) and the multichannel random token protocols, and to investigate their priority schemes and voice/data integration in the random token protocol.
It is well known that in a broadcast system the channel capacity is inversely proportional to the increasing ratio of the end-to-end propagation delay to the packet transmission time. With high transmission rates, the packet transmission time becomes small, and thus this ratio increases dramatically. As a result, the introduction of high bandwidth channel into a broadcast system may result in only a marginal increase in the actual network capacity. To solve this problem in a high-speed broadcast system and to use current access protocols, we adopted a multiple channel configuration.
We first developed semi-Markov models of the two protocols and obtained the throughput and delay performances of the systems using those two multichannel random access protocols. We used the nonpersistent CSMA/CD protocol for a multichannel system and considered four channel selection schemes. We also considered the effects of destination conflicts. We showed that the delay-throughput performance of MCSMA/CD is the best when the idle channel selection scheme is used among the four channel selection schemes. We also showed that the performance degradation due to destination conflicts becomes significant as the load increases and more channels are used. To prevent he performance degradation due to destination conflicts we introduced conflict detection and multiple reception, and showed that the performance is enhanced with conflict detection or multiple reception. The choice between conflict detection and multiple reception is a function of cost and performance.
In addition, we considered the optimal number of channels that gives the best performance for a given system configuration. It was shown that the number of channels that yields the best delay-throughput performance varies as the traffic loads vary. We can obtain the optimal number of channels by solving the system equations we have derived. This optimization can be targeted for a given expected system load to obtain the maximum throughput at high loads.
Also, we developed an infinite population model of the multichannel random token protocol by using renewal theory. Since the random token protocol is a modified version of the p-persistent CSMA/CD, we adopted the destination-oriented channel selection scheme in which no destination conflict occurs. It is reasonable to use persistent channel selection schemes for persistent protocols in a multichannel environment. We showed that the channel capacity is increased as more channels are used. We also showed that the random token protocol is less sensitive to the ratio of the end-to-end propagation delay to the packet transmission time than the CSMA protocol. We can determine the optimal number of channels in the same way as for MCSMA/CD.
Next, we considered the priority schemes of the MCSMA/CD and the random token protocols. Since there exist various kinds of traffic in a network, a priority function may be required to meet the needs of various traffics. Although multiple priority classes may exist in the network, we considered two priority classes for the convenience of analysis. We invoked a priority function in the channel selection scheme for MCSMA/CD since we used a nonpersistent channel selection scheme. Users with low priority cannot select a channel if the number of idle channels is less than a certain number. In that way, the priority function is obtained for MCSMA/CD. We invoked a priority function for the random token protocol by giving earlier scheduling time to users with high priority. For the prioritized MCSMA/CD, we used the same model developed for the analysis of MCSMA/CD. We modeled the prioritized random token protocol by using two interacting Markov chains. We showed the effect of a priority function for both protocols. The delay-throughput performance of high-priority class is greatly improved at the expense of performance degradation of low-priority class. For the prioritized MCSMA/CD. We can optimize the system by controlling the number of channels with which users of low-priority class determine whether they can access a channel. We can also optimize the system for the prioritized random token protocol by controlling the length of the scheduling period.
Finally, we integrated voice and data in the random token protocol. Voice is served in the same way as the time decision multiple access(TDMA) method. We used three-state model of voice source, and a movable boundary scheme in a frame. We obtained the voice clipping probability, the fraction of wasted bandwidth, and the call-blocking probability. To maintain the quality of voice signal, voice calls are blocked when the number of voice calls already set up is large and therefore the clipping probability becomes more than a certain threshold value. If we assume that the voice calls occur according to a Poison process, then the call blocking probability is equal to the Erlang's loss formula. We showed that when the number of voice calls is less than about twice the maximum number of voice slots in a frame, the voice clipping probability is less than 0.005. Data is served by the random token protocol. We modeled the system by using the technique used for the analysis of the prioritized random token protocol. We regarded the voice region in a frame as a long packet, and assumed that only one voice user exist and that the voice user has high priority. We performed an analysis of data under the voice and data integrated environment. We obtained the delay-throughput performance of data with various configurations. It was shown that data performs well in a voice/data integrated system. Thus, the voice/data integration protocol based on the random token protocol has many practical advantagers over previous protocols, because it has very low overhead and it does not require system clocks for synchronization.
본 논문의 주된 목적은 고속 통신망을 위한 multichannel random access protocol들에 대한 성능 분석과 그 protocol들의 priority scheme, voice/data integration에의 응용등을 다루는데 있다.
Broadcast bus 형태의 망은 전달지연시간 (propagation delay = τ ) 대 패켓 전송시간 (packet transmission time = T)의 비 α(=τ /T)에 따라 성능이 다르며, α가 커질수록 성능이 떨어진다. 고속통신의 필요성이 증가함에 따라 채널의 전송 속도도 고속이 요구되는데, broadcast bus 형태의 망에서는 채널속도가 증가하면 패켓전송 시간 T가 작아지므로, 즉 α가 커지므로, 실질적으로 채널 속도 증가에 비해 성능은 그다지 향상되지 않는다. 따라서, 본 논문에서는 broadcast bus형 network을 고속 통신망에서 사용하기 위해서 multichannel 구조를 채택하였으며, 여기에 쓰이는 random access protocol들을 제안하고 성능 분석을 하였다.
첫째로, nonpersistent CSMA/CD protocol과 random token protocol을 multichannel network에 적용한 MCSMA/CD와 multichannel random token protocol에 대한 성능 분석을 하였다. Imbedded Markov chain을 사용하여 MCSMA/CD protocol을 approximate modeling하여 delay-throughput 성능을 구하였다. Multichannel network에서는 채널을 선택하는 channel selection 기능이 추가되어야하는데, 여기서는 4가지의 channel selection 방법(random selection, idle channel selection, source-oriented selection, destination-oriented selection)을 고려하였다. 또한, multichannel network에서는 한 사용자에게 여러 개의 packet이 동시에 도착하는 경우 destination conflict가 발생한다. Destination conflict가 발생하는 경우 성능을 향상시키기 위해 conflict detection 및 multiple reception을 제안하였다. 한편, p-persistent CSMA의 변형된 형태인 random token protocol에 대한 분석을 하고, destination-oriented selection을 사용하여 multichannel network에 적용을 시킨다. Infinite population model로 renewal theory를 이용하여 throughput 분석을 하였으며, finite population model로 imbedded Markov chain을 이용하여 delay 분석을 하였다.
다음으로, 이 두 protocol들에 priority function을 추가하여 분석을 하였다. Priority class는 둘인 것으로 가정하였다. MCSMA/CD protocol에는 channel selection 방법에 priority function을 추가하였다. Idle channel selection을 사용했으며, low priority 사용자는 idle channel의 수가 일정한 수를 넘어야 access할 수 있게하는 방법으로 priority function을 구현했다. MCSMA/CD 분석에 사용한 model을 이용하여 delay-throughput 성능을 구하였다. 한편, random token protocol에서는 scheduling period에 priority function을 추가했다. High priority 사용자에게는 low priority 사용자보다 빠른 scheduling time을 주어서 priority function을 구현하였다. 두 개의 interactive Markov chain을 이용하여 delay-throughput 성능을 구하였다.
마지막으로, random token protocol을 기본으로 하여 voice와 data를 집적하는 protocol을 제안하고 voice와 data에 대한 분석을 하였다. 채널은 frame 구조로 이루어지며 movable boundary scheme을 사용했다. Voice는 TDM과 같은 서비스를 제공 받는다. Voice source는 three state model을 사용하였으며, Markov chain을 이용하여 voice의 clipping probability, wasted bandwidth 비 및 call blocking probability를 구하였다. Data 사용자들은 frame에서 voice 사용자들이 쓰고 남은 부분을 random token protocol로 access한다. Frame의 voice region을 하나의 긴 packet으로 간주하고 data packet보다 high priority를 갖는 것으로 가정하여 prioritized random token protocol 분석에 사용했던 방법으로 data의 delay-throughput 성능을 구하였다. 본 논문에서 얻은 결과들에 대하여 simulation 결과를 첨가하였고, 매우 근사한 결과를 나타내는 것을 보임으로써 분석의 정확성을 뒷받침했다.
