We propose a process algebra for link layer protocols, featuring a unique mechanism for modelling frame collisions. We also formalise suitable liveness properties for link layer protocols specified in this framework. To show applicability we model and analyse two versions of the Carrier-Sense Multiple Access with Collision Avoidance (CSMA CA) protocol. Our analysis confirms the hidden station problem for the version without virtual carrier sensing. However, we show that the version with virtual carrier sensing not only overcomes this problem, but also the exposed station problem with probability 1. Yet the protocol cannot guarantee packet delivery, not even with probability 1.
Multiple analyses were performed for the CSMA CD protocol (CSMA with collision detection), a predecessor of CSMA CA that has a constant backoff, i.e. the backoff time is not increased exponentially, see @cite_12 @cite_3 @cite_24 @cite_5 @cite_8 . In all these approaches frame collisions have to be modelled explicitly, as part of the protocol description. In contrast, our approach handles collisions in the semantics; thereby achieving a clear separation between protocol specifications and link layer behaviour.
@cite_8 @cite_3 @cite_24 @cite_5 @cite_12
2001480730 1600358513 1988873236 2001714096
CSMA with Enhanced Collision Avoidance (CSMA ECA) uses a deterministic backoff after successful transmissions to significantly reduce the number of collisions. This paper assesses by means of simulations the throughput and conditional collision probability obtained from a single-hop ad-hoc network using CSMA ECA. A comparison with the legacy CSMA CA reveals that the proposed protocol outperforms the legacy one in all considered scenarios. Specifically, it is shown that CSMA ECA presents advantages for both rigid and elastic flows. Carrier sense multiple access with enhanced collision avoidance (CSMA ECA) is a distributed MAC protocol that allows collision-free access to the medium in WLANs. The only difference between CSMA ECA and the well-known CSMA CA is that the former uses a deterministic backoff after successful transmissions. Collision-free operation is reached after a transient state during which some collisions may occur. This paper shows that the duration of the transient state can be shortened by appropriately setting the contention parameters. Standard absorbing Markov chain theory is used to describe the behaviour of the system in the transient state and to predict the expected number of slots to reach the collision-free operation. The paper also introduces CSMA E2CA, in which a deterministic backoff is used two consecutive times after a successful transmission. CSMA E2CA converges quicker to collision-free operation and delivers higher performance than CSMA ECA, specially in harsh wireless scenarios with high frame-error rates. The last part of the paper addresses scenarios with a large number of contenders. We suggest dynamic parameter adjustment techniques to accommodate a varying (and potentially high) number of contenders. The effectiveness of these adjustments in preventing collisions is validated by means of simulation. Carrier Sense Multiple Access Collision Detection (CSMA CD) is the protocol for carrier transmission access in Ethernet networks (international standard IEEE 802.3). On Ethernet, any Network Interface Card (NIC) can try to send a packet in a channel at any time. If another NIC tries to send a packet at the same time, a collision is said to occur and the packets are discarded. The CSMA CD protocol was designed to avoid this problem, more precisely to allow a NIC to send its packet without collision. This is done by way of a randomized exponential backoff process. In this paper, we analyse the correctness of the CSMA CD protocol, using techniques from probabilistic model checking and approximate probabilistic model checking. The tools that we use are PRISM and APMC. Moreover, we provide a quantitative analysis of some CSMA CD properties. Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA ECA) is a recently proposed modification to the well-known CSMA CA protocol. By using a deterministic backoff after successful transmissions, the number of collisions decreases. This article presents a model that captures the behaviour of CSMA ECA in both saturated and non-saturated scenarios. The results, which are validated by simulations, show that CSMA ECA effectively prevents collisions and, therefore, it can deliver a higher throughput than CSMA CA.