Analysis of Computer Networks

The goal of this chapter is to provide a review of the principles of probability, random variables, and distributions.

We saw in Sect. 1.11 on page 10 that many systems are best studied using the concept of random variables where the outcome of a random experiment was associated with some numerical value. Next, we saw in Sect. 1.28 on page 31 that many more systems are best studied using the concept of multiple random variables where the outcome of a random experiment was associated with multiple numerical values. Here we study random processes where the outcome of a random experiment is associated with a function of time [1].

In this chapter we will study the long-term behavior of Markov chains. In other words, we would like to know the distribution vector s(n) when n → ∞. The state of the system at equilibrium or steady state can then be used to obtain performance parameters such as throughput, delay, loss probability, etc.

Reducible Markov chains describe systems that have particular states such that once we visit one of those states, we cannot visit other states. An example of systems that can be modeled by reducible Markov chains is games of chance where once the gambler is broke, the game stops and the casino either kicks him out or gives him some compensation (comp). The gambler moved from being in a state of play to being in a comp state and the game stops there.

We saw in Chap. 4 that a Markov chain settles down to steady-state distribution vector s when n → ∞. This is true for most transition matrices representing most Markov chains we studied. There are other times however when the Markov chain never settles down to an equilibrium distribution vector no matter how long we iterate.

Queuing analysis is one of the most important tools for studying communication systems. The analysis allows us to answer endless questions about the system performance. This chapter explains that queuing analysis is a special case of Markov chains.

Modeling a protocol or a system is just like designing a digital system, or any system for that mater. There are many ways to model a protocol based on the assumptions that one makes. My motivation here is simplicity and not taking a guided tour through the maze of protocol modeling.

*****

In this chapter we illustrate how to develop models for several medium access control (MAC) protocols that are commonly used in computer communications.

The IEEE 802.11 (WiFi) is the most widely used medium access control protocol for wireless local area networks (LANs).

The IEEE 802.16 (WiMAX) provides a wireless high speed access (2–11 GHz) to users through a centralized base station that can cover several thousand square kilometers. In that sense, WiMAX is a metropolitan area network (MAN). The base stations are connected together and to the rest of the Internet using high speed wired links or microwave links. The IEEE 802.16e-2005 allows mobile users.

Path loss, or free-space propagation, occurs due to the spread of the signal beam over distance and absorption through the channel. It is a large-scale phenomenon since variations in the signal occur over distances large compared to the signal wavelength. Figure 13.1 shows path loss due to two types of antennas. Figure 13.1a shows two omnidirectional antennas being used by the transmitter and receiver. The combined antenna gain G = 1.

Conventional radio (CR) networks require a dedicated channel with little or no interference and provides a fixed functionality for all users.

Different models are used to describe different types of traffic. For example, voice traffic is commonly described using the on–off source or the Markov modulated Poisson process (MMPP). Studies suggest that traffic sources such as variable bit rate (VBR) video and Ethernet traffic are better represented by self-similar traffic models [2–7]. The important characteristics of a traffic source are its average data rate, burstiness, and correlation. The average data rate gives an indication of the expected traffic volume for a given period of time. Burstiness describes the tendency of traffic to occur in clusters. A traffic burst affects buffer occupancy and leads to network congestion and data loss. Data burstiness is manifested by the autocorrelation function which describes the relation between packet arrivals at different times. It was recently discovered that network traffic exhibits long-range dependence, i.e. the autocorrelation function approaches zero very slowly in comparison with the exponential decay characterizing short-range dependent traffic [2–7]. Long-range dependent traffic produces a wide range in traffic volume away from the average rate. This great variation in traffic flow also affects buffer occupancy and network congestion. In summary, high burstiness or long-term correlation leads to buffer overflow and network congestion. We begin by discussing the different models describing traffic time arrival statistics.

A scheduling algorithm must be implemented at each network router or switch to enable the sharing of the switch limited resources among the packets traveling through it. The resources being shared include available link bandwidth and buffer space. The main functions of a scheduler in the network are (1) provide required quality of service (QoS) for the different users, by making proper choices for selecting next packet for forwarding to the next node; (2) select next packet for dropping during periods of congestion when the switch buffer space is starting to get full, and (3) provide fair sharing of network resources among the different users.