High priority traffic separation in shared Ethernet networks

Submitted to the 4th International Workshop on RealTime Networks – RTN 2005 July 5, 2005, Palma de Mallorca, Spain High Priority Traffic Separation in Shared Ethernet Networks1 1 This work has been partially supported by IDMEC and by FCT (project ADVANSYS and BD 13203/2003). Ricardo Moraes Department of Mechanical Engineering University of Porto, Portugal [email protected] Francisco Vasques Department of Mechanical Engineering University of Porto, Portugal vasqu[email protected] Abstract In this paper, it is proposed an enhanced algorithm for the collision resolution in shared Ethernet networks. Such algorithm, referred as high priority Binary Exponential Backoff (h-BEB), provides high priority traffic separation, enabling the support of real-time communications. To our best knowledge, the h-BEB algorithm is the first collision resolution algorithm that allows Ethernet standard devices to coexist with modified stations in the same network segment, imposing higher priority for the transfer of privileged traffic. The probabilistic and simulation analysis of the traffic separation shows that it guarantees for an h-BEB station a predictable and significantly smaller access delay, when compared with the access delay for standard Ethernet stations. 1. Introduction Ethernet is a well-known and extensively used network technology. The first standardized version was approved and released in 1985 as the ANSI/IEEE 802.3 Standard [1]. Simplicity was one of the main reasons for the success of Ethernet networks. Such simplicity derives from its MAC protocol, which is based on the collision detection and resolution between randomly initiated transmissions. A full-duplex operating mode of Ethernet networks has been introduced in the early 90s (IEEE 802.1D) [2], using bridges (referred as Ethernet Switching Hubs) to interconnect node stations. Such full-duplex operating mode enables the micro-segmentation of the network, by regenerating information only to the receiving port of the bridge, avoiding therefore collisions between messages. 1.1. Rationale for the Proposal of a New Algorithm Numerous Ethernet networks still operate in heterogeneous environments, with Ethernet Switching Hubs interconnecting both independent node stations and Ethernet Repeater Hubs (Figure 1). In such heterogeneous environments, the Switching Hubs impose separate collision domains at each port (network segmentation), allowing the implementation of service policies with different priorities. However, within each of the collision domains (i.e., among node stations interconnected by a Repeater Hub), the network still operates in the traditional shared Ethernet mode; that is, collisions are solved by means of a probabilistic contention resolution algorithm, where the retransmission probability does not depend on the type of traffic, but just on the state of the collision counter of each particular station. Figure 1: Heterogeneous Ethernet environment. As a consequence, within each of the collision domains, it is not possible to provide traffic separation. To separate traffic, which is a requirement to support real-time communication in unconstrained environments, there are usually two different approaches: either avoiding collisions, by controlling the medium access rights of each station (TDMA scheme, token passing, etc), or ensuring a deterministic collision resolution, by modifying the collision resolution algorithm. A third approach (that is not deterministic) is to reduce the number of occurring collisions, enhancing the network responsiveness to real-time message requests. The drawback of such traditional approaches is that they do not allow the coexistence of Ethernet standard devices together with modified devices in the same network segment, which means that legacy shared Ethernet systems are not able to support real-time communications without extensive modifications. To address this problem, we propose the “high priority Binary Exponential Backoff (h-BEB)” collision resolution algorithm, which allows Ethernet standard devices to coexist with one h-BEB modified station, imposing a higher priority for the transfer of h-BEB related traffic. As a consequence, it becomes possible the implementation of traffic separation policies, which are the foundation for the support of real-time Collision Domain Collision Domain Repeater HUB Switching Hub Repeater HUB ServerWorkstation communication, in heterogeneous Ethernet environments. 2. The High Priority Binary Exponential Backoff Algorithm (h-BEB) The CSMA/CD (Carrier Sense Multiple Access with Collision Detection) protocol is the Media Access Control (MAC) protocol of Ethernet networks. Basically, the CSMA/CD protocol works as follows: when a station wants to transmit, it listens to the transmission medium. If the transmission medium is busy, the station waits until it goes idle; otherwise, it immediately transmits. If two or more stations simultaneously start to transmit, the transmitted frames will collide. Upon the collision detection, all the transmitting stations will terminate their transmission and send a jamming sequence to ensure that all the transmitting stations recognize the collision and abort the transmission. When the transmission is aborted due to a collision, it will be repeatedly retried after a randomly evaluated delay (backoff time) until it is successfully transmitted or definitely aborted (after a maximum number of 16 attempts) [1]. Transmit Frame Bus Busy? Colision Detect Start Transmission Wait Finish yes yes no Transmission Done? no send jam Done: TransmitOk yes Increment Attempts to many attempts? wait backoff time compute backoff Done: ExcessiveCollision Error yes no no Transmit Frame Bus Busy? Colision Detect Start Transmission Wait Finish yes yes no Transmission Done? no send jam Done: TransmitOk yes Increment Attempts to many attempts? Done: ExcessiveCollision Error yes no no (a) (b) Figure 2: CSMA-CD protocol with BEB resp. h-BEB collision resolution algorithms. A station implementing the h-BEB algorithm has the same operating behavior, except for the backoff delay, which is set to 0. In such case, an h-BEB station starts immediately to transmit after the end of the jamming sequence. This behavior guarantees the highest transmitting probability to the h-BEB station, in a shared Ethernet segment with multiple BEB stations. The hBEB station will always try to transmit its frame in the first available slot after the jamming sequence, while all the other stations implementing the BEB algorithm will wait between 0 and 2 n-1 slot times, where n is the number of collision resolution rounds. Figures 2 (a) and (b) summarize the dynamic behavior of the CSMA/CD protocol with, respectively, the BEB and the h-BEB collision resolution algorithms. The h-BEB collision resolution algorithm is therefore able to impose real-time traffic separation, as the traffic generated by the h-BEB station will always be transferred before the traffic generated by the other stations. Therefore, this algorithm is adequate to support real-time communications in shared Ethernet segments, as long as all the real-time traffic in the network is generate by the h-BEB station. This behavior is highly adequate to, for instance, realtime video/voice transferring applications in legacy shared Ethernet networks. By simply plugging a notebook computer with the modified hardware to the shared Ethernet segment, it becomes possible to transfer traffic at a higher priority than the traffic generated by all the other stations. 3. Exact Performance Analysis in Heavily Loaded Network Scenarios One of the first Ethernet performance analysis was presented by Metcalfe and Boggs [3], where the authors presented an exact probabilistic analysis for heavily loaded network scenarios. In that analysis, a constant retransmission probability for each slot has been assumed, and the successful retransmission probability (on the next slot) has been considered to be equal to a constant: p. Such probability A is maximized when p=1/K (equal probability of successful retransmission). Such assumption is an interesting approximation for the real backoff function, as has been shown in multiple simulation studies (e.g. [4] [5]). Thus, ( ) 1 11 − −= K KA (1) The probability that the contention interval will be exactly n slots is: 1 )1(− −×= n nAAP n>=1 (2) Obviously, the assumption that each station transmits with an equal probability p=1/K is not suitable for the analysis of the h-BEB algorithm, as in the h-BEB case one of the stations (the privileged station) transmits at a higher probability. Therefore, new and adequate formulae have been devised to perform the probabilistic analysis of the h-BEB collision resolution algorithm. In [6], it has been demonstrated that the probability of the h-BEB station sending a message in the ith collision round (after an initial collision), is given by: ( ) ∑ = − ×         −= N j jn j j N NnP 0 21),( (3) where the coefficients of the Pascal Triangle are given by:         j N = )!(! ! jNj N − (4) n is the number of collision resolution rounds, and N is the number of BEB stations in the network (N+1 is the total number of stations). 4. Comparative Analysis A comparative analysis of both collision resolution algorithms has been performed, considering a shared Ethernet environment where 64 standard Ethernet stations are interconnected with a special station implementing either the h-BEB (enhanced Ethernet mode) or the BEB (traditional Ethernet mode) collision resolution algorithms (Figure 3). Ethernet bus - 10 Mbp s Station BEB Number 1Station BEB Number 2Station BEB Number 64 ... Special Station implementing h-BEB algorithm E n h a n c e d E t h e r n e t m o d e Ethernet bus - 10 Mbp s Station BEB Number 1Station BEB Number 2Station BEB Number 64 ... Special Station implementing BEB algorithm Traditional Ethernet node Figure 3: Shared Ethernet environment. 4.1. Exact Analytical Results for an Heavily Loaded Network Scenario Probabilistic analytical results obtained from Equation (2) were compared with those obtained from Equation (3). Figure 4 represents the probability of transmission for the special station after n collision resolution rounds, for both the traditional and the enhanced Ethernet modes. It becomes clear that the special station has a much higher transmission probability in the enhanced mode than in the traditional mode (as it was expected). According to Figure 4 it is also possible to observe that, in a heavily loaded network scenario, approximately 95% of the messages from the h-BEB station will be transferred before 8 collision rounds. On the other hand, the probability to transfer a message, in the same heavily loaded network scenario, using the BEB algorithm (traditional mode) is smaller than 2%, whatever the considered collision round. It is also possible to evaluate the network accessibility, that is, the probability that the contention interval will be exactly n slots. From the network accessibility results [6], it can be verified that the network accessibility is slightly smaller in the enhanced mode than in the traditional mode, for the initial collision resolution rounds. These are expected results, as in the enhanced mode, the special station does not allow any other station to transmit, while it has not succeed to transfer its packets. Therefore, the contention period will be longer than in the traditional mode, whenever the special station has packets to be transferred. Figure 4: Transmission probability – 65 stations. 4.2. Simulation Results A simulation model was implemented using the Network Simulator (NS-2) tool [7], considering a 10 Mbps Ethernet network, where each station has a Poisson traffic source with a fixed packet length of 250 bytes. For each simulated load value, 75×104 packets are successfully transmitted. Figure 5 illustrates the average achievable throughput for both the enhanced and the traditional Ethernet mode scenarios. It can be seem that the throughput is very similar in both scenarios, as the lines are almost superposed. The average throughput can also be compared with its theoretical maximum, which clearly shows that for network loads above 65%, there is a high rate of packets loss in the network. Nevertheless, it has been observed that the h-BEB station never discards any packet, whatever the simulated network load. Figure 5: Throughput in an Ethernet segment. The average delay for transferring a packet from the special station is represented in Figure 6. These results show that the special station implementing the h-BEB algorithm has a very small average packet delay. On the other hand, it is also clear that, the average packet delay exponentially increases with the offered load in the traditional mode, up to an offered load above 75%, where the packet loss starts to be significant. These results clearly show that, whatever the network load, the average packet delay is nearly constant in the enhanced mode. These are very important results, as they forecast predictable communication delays for the h-BEB station for a considerable load range, which is a fundamental requirement to support real-time communication. Figure 6: Average delay for the special station. Finally, an important parameter for real-time communication is also the standard deviation of the average packet delay, which is directly related to the message transfer jitter. For the case of the special station implementing the h-BEB algorithm, the message transfer jitter is nearly constant, whatever the simulated network load (Figure 7). However, for the traditional Ethernet mode, the message transfer jitter is of the same order as the average packet delay, which is clearly not adequate for the support of real-time communications. Figure 7: Standard deviation for the special station in a large population Ethernet segment. 5. Conclusions and Future Work This paper proposes the use of a modified algorithm: the h-BEB algorithm, for the collision resolution in shared Ethernet networks. The exact probabilistic analysis shows that for a heavily loaded network scenario, an h-BEB station has a significantly higher probability to send a message up to the ith collision round than any BEB station. For more realistic network load scenarios a simulation analysis has been done. The performance measures included: throughput, average packet delay and standard deviation of the average packet delay (transfer jitter). It has be shown that the h-BEB collision resolution algorithm guarantees, whatever the network load, an average access delay significantly smaller for the h-BEB station, when compared with the access delay for the BEB stations. More significantly, almost constant values for both the average access delay and the related standard deviation have been observed for the traffic transferred by the h-BEB station. This is a very important result, as it forecasts a predictable communication delay when supporting real-time communications. The main drawback of the current version of the hBEB algorithm is that it allows at most one h-BEB station per shared Ethernet segment. The plan for future work is to extend the number of h-BEB stations in the same shared Ethernet segment. By means of a token passing procedure. By controlling the token holding time of each h-BEB station, it is possible to guarantee the realtime behavior of the supported applications. References [1] "IEEE standards for local area networks: carrier sense multiple access with collision detection (CSMA/CD) access method and physical layer specifications," in ANSI/IEEE Std 802.3-1985, 1985. [2] "IEEE Standard for Local and metropolitan area networks Media Access Control (MAC) Bridges," in IEEE Std 802.1D-2004 (Revision of IEEE Std 802.1D-1998), 2004, pp. 0_1-269. [3] R. M. Metcalfe and D. R. Boggs, "Ethernet: distributed packet switching for local computer networks," Communications of the ACM, vol. 19, pp. 395-404, 1976. [4] S. S. Lam and L. Kleinrock, "Packet Switching in a Multiaccess Broadcast Channel: Dynamic Control Procedures," vol. CM-23, pp. 891-904, 1975. [5] G. T. Almes and E. D. Lazowska, "The behavior of Ethernet-like computer communications networks," presented at Proceedings of the Seventh Symposium on Operating Systems Principles, 10-12 Dec. 1979, Pacific Grove, CA, USA, 1979. [6] R. Moraes and F. Vasques, "A Probabilistic Analysis of Traffic Separation in Shared Ethernet Systems Using the h-BEB Collision Resolution Algorithm," presented at 13th International Conference on Real-Time Systems - RTS'2005, Paris - France, 2005. [7] "ns-2 Network Simulator," 2.27 ed, 2004. Available at: http://www.isi.edu/nsnam/ns/