The main objectives of this dissertation are to suggest some collision resolution algorithms (CRAs) in a multiple access broadcast network and to investigate their performance characteristics when limited sensing and full feedback sensing schemes are applied.
The tree protocol and its variants have been studied as stable and effective methods of resolving collision. Among them, the tree protocol with collision detection (Tree/CD) recently attracted considerable attention because of better throughput and delay performance than any other CRAs including the Ethernet protocol. However, its performance has not been sufficiently studied yet.
Thus, we first analyze the delay performance of the Tree/CD protocol. Considering the regenerative property of the delay process, we derive the upper and lower bounds of the average packet delay. Over a wide range of arrival rates and slot length T, our analysis agrees closely with simulation results. We also investigate a collision resolution protocol that utilizes the information of collision multiplicity.
With the number of collided packets known, the system shows performance enhancement over the Tree/CD protocol in both throughput and delay characteristics. This results from the fact that arrival intervals are split adaptively, not just halved, according to the number of packets that were involved in the collision.
In addition, we analyze the throughput performance of the limited sensing Tree/CD protocol. It is shown that, though a little degradation is observed because of a restiction that the users cannot listen to all feedbacks, the throughput becomes almost the same as that of a full-feedback system when the allowed successive slots in a CRI is as large as 5.
Then, we examine the performances of collision resolution protocols with random packet sizes. With packets of arbitrary length, the protocol need to enable users to detect the end of transmission. The delay and variance characteristics of both the ternary and binary protocols are derived for various packet length distributions using the M/G/1 queueing model. The analysis results are confirmed by computer simulations.
For the situation where a collision is not distinguishable from an idle state, as in the spread spectrum system, we consider the binary feedback protocol. Here it is noted that the success/failure (S/F) feedback algorithm is suitable for the protocol with random packet sizes. We show that the suggested protocols have the flexibility on the packet length as well as the operational stability. Moreover, their throughput performance can be enhanced dramatically by keeping the communicating regions small enough so that the propagation delay may be short.
Finally, we propose a priority CRA that is capable of supporting different types of traffics consisting of M ($ge$2) priority classes. Some researchers have studied priority CRAs supporting only two classes based on the binary collision/noncollision (C/NC) feedback algorithm. Here, it is shown that the suggested algorithm yields better performance compared with other priority schemes that support two classes. This is possible partly because the system utilizes the ternary feedback scheme instead of binary feedback, and partly because the algorithm eliminates the possibility of collision among different classes. We also show that the maximum total throughput is maintained regardless of the number of priority classes.
The throughput performance of the priority CRA, with the limited sensing scheme included, is analyzed for the two protocols; the clipped binary tree protocol and the Tree/CD protocol. Then the delay characteristic is evaluated for the full-feedback sensing Tree/CD protocol using the modified M/D/1 priority queueing model. Due to the flexibility of supporting various priority traffics and the capability of stable and high throughput, the proposed priority CRA has advantages when applied to packet radio networks and local area networks.
본 논문의 주된 목적은 다중 접속방송망을 위한 충돌 해결 알고리즘을 제안하고, limited sensing 및 full feedback sensing 환경 하에서 그 성능을 고찰하는 데 있다.
Tree 프로토콜과 그를 기초로 한 여러 프로토콜들은, 충돌 해결을 위한 안정하고 효율높은 방법으로서 많이 연구되어 왔다. 그 중에서 충돌 감지 tree 프로토콜 (Tree/CD)은 Ethernet 프로토콜을 비롯한 다른 알고리즘보다 우수한 성능을 보임으로써 최근 주목을 받고 있으나, 아직 충분한 성능분석이 이루어 지지 않은 상태이다.
따라서 우선 Tree/CD의 정확한 지연특성을 분석하였다. Regenerative 특성을 고려하여 평균 패킷 지연의 상한과 하한치를 유도했고 이 결과는 트래픽 밀도 및 슬롯 길이의 여러 값들에 대해 simulation 결과와 잘 일치하였다. 그리고 충돌한 패킷의 중첩도가 각 노드에 알려지는 경우에 대해 Tree/CD의 성능을 분석하고 성능 향상을 보였는데, 이것은 충돌의 중첩도에 따라 적응적으로 패킷의 grouping이 이루어지기 때문이다.
또한 limited sensing, 즉 각 노드가 어느 순간 이후의 제한적인 feedback만을 듣는 경우에 대해 Tree/CD의 최대 처리율을 고찰하였다. Full feedback sensing 프로토콜보다 약간의 성능저하가 있지만 충돌해결 동안 허용되는 idle 슬롯의 수를 5정도로 하면 거의 같은 처리율을 보였다.
다음으로, 임의의 패킷 길이를 가지는 충돌 해결 알고리즘의 성능을 분석하였다. 패킷은 특정한 확률분포를 가지는 임의의 길이이므로, 프로토콜은 패킷전송의 끝을 감지하도록 했으며 ternary feedback 및 binary feedback 알고리즘을 모두 고려하였다. Geometric, uniform, two-valued 및 constant의 분포에 대해 M/G/1 큐잉 모델로써 평균 패킷 지연과 variance를 구하였고 그 결과는 simulation으로 확인하였다. Binary feedback 프로토콜중에서는 success/failure(S/F) 방법만이 임의의 패킷 길이에 대해 적용가능하며 S/F 시스템은 데이타의 충돌과 idle을 구별할 수 없는 대역 확산 통신 시스템이 그 예라고 할 수 있다. 제안된 프로토콜은 동작의 안정성뿐 아니라 패킷길이의 유연성이 있으며, cell단위의 통신영역을 작게 만든다면 거의 1에 가까운 처리율을 얻을 수 있다.
마지막으로, 둘 이상의 priority traffic을 지원하는 충돌해결알고리즘을 제안하였다. Collision/non-collision (C/NC) feedback을 이용하여 두 개의 priority class만을 지원하는 알고리즘이 연구된 바가 있는데, 제안된 알고리즘이 이들보다 좋은 처리율 및 지연특성을 가지는 것을 보였다. 이것은 ternary feedback을 이용하는 사실과, 다른 priority class간의 충돌을 허용하지 않는 알고리즘의 특성에 기인한다고 할 수 있다. 특히, 모든 class의 전체처리율은 priority class의 수에 상관없이 일정함을 보였다.
제안된 알고리즘을 0.487 프로토콜과 Tree/CD 프로토콜에 적용한 경우에 대해 처리율 및 지연성능을 분석하였는데 패킷 지연을 분석하기 위하여는 M/D/1 priority 큐잉 모델을 이용하였다. 제안된 priority 충돌 해결 알고리즘은 많은 priority class를 지원한다고 하는 유연성과 안정하고 높은 처리율특성을 보이므로, 패킷 무선망과 LAN에 적용될 때 장점을 가진다고 할 수 있다.