Table of Contents

Question of the Day

If you were to design a network to potentially be shared by many users, how would you control access to it?

Assigned Reading

N/A

Physical Local Area Networks

Characteristics

Physical LANs are quite common in computer networks and have the following characteristics:

• Cover a limited geographic area
• Support high data rates
• Constructed with a reliable physical medium
• Are inexpensive to deploy
• Consist of a shared physical medium
• Support broadcast communications
• Store and forward and routing are unnecessary

There are many network protocols used in physical LANs, such as:

• CSMA/CD (Carrier Sense Multiple Access with Collision Detection): Ethernet, ALOHA
• Token ring: IBM, FDDI

Common Topologies

The data unit on a LAN is referred to as a frame (not a packet). When a frame is transmitted, it propagates over the entire physical medium. How a frame is forwarded depends on the LAN topology used. There are two popular LAN topologies:

• Bus
• Ring

Bus Topology

Each end host on a bus has a transceiver that transmits and passively monitors the bus for passing transmissions. Synchronization is performed on frame headers, which contain control information. In a bus topology, every end host connected to the bus receives the header of all transmissions on the bus. If an end host receives a frame header addressed to a different end host, the rest of the frame will be ignored.

Ring Topology

In a ring topology, each end host has a transceiver that breaks the circuit of the ring. Unlike a bus topology where each end host passively listens to the bus, each end host actively participates in the ring regardless of a frame’s destination. If an end host receives a frame with header addressed to itself, the end host will copy the frame from the ring; otherwise, the end host will forward the frame towards the next end host on the ring. In a ring topology, frames typically flow in a single predetermined direction.

Similar to cut-through switching, cut-through forwarding can allow an end host to begin transmission of a frame on its outbound transceiver before it receives the entire frame. If the end host determines after reading the frame header that the frame is destined for another end host on the ring, it can begin transmission.

The source end host of a frame will remove the frame from the ring and not forward it once it arrives back at the source host.

End Hosts

In a physical LAN, an end host contains a network interface card (NIC) for transmitting and receiving frames on the LAN. The NIC provides controlled access to the physical medium of the LAN. Thus, a NIC implements the physical and data link layers of the OSI model network stack or the physical, media access control (MAC), and logical link control (LLC) layers of the IEEE standards based network stack.

Media Access Control Techniques

There are a variety of methods for controlling access to the physical medium of a LAN when there are multiple end hosts sharing the LAN. These techniques are collectively known as media access control (MAC) and are highly dependent on the topology of the LAN. Oftentimes, the MAC technique can have a significant impact on the overall performance of the LAN.

Fixed Assignment MAC

A LAN with fixed assignment MAC pre-allocates fractions of the bandwidth capacity to end hosts. Two popular fixed assignment MACs are known as time division multiple access (TDMA) and frequency division multiple access (FDMA).

Time Division Multiple Access

In TDMA, each end host is pre-allocated a fixed duration time slot in which it (and only it) has the ability to transmit on the shared physical medium of the LAN. An example of TDMA is a shared T1 link where multiple telephone calls are multiplexed onto the single T1 link in predefined time slots.

Frequency Division Multiple Access

In FDMA, each end host is pre-allocated a unique frequency at which it can transmit data continuously. An example of FDMA is an analogue cellular telephone tower, which assigns connected cellular devices unique frequencies for conducting phone calls.

Note that in TDMA, if the traffic pattern of end hosts is bursty, many time slots may be wasted if the end hosts do not have any data to transmit in their predefined slots. Likewise, in FDMA, if the traffic pattern is bursty, end hosts may not utilize their allocated frequency all the time, resulting in wasted bandwidth. This is a problem inherent to fixed assignment MAC techniques.

Random Access MAC

The goal of random access MAC is to allocate the physical medium to end hosts based on demand. As such, the link capacity is fully allocated to all end hosts at any given time; however, note that only one end host can transmit on the physical medium at a time. Thus, in random access MAC, a mechanism is required to detect whether or not an end host is currently transmitting, as well as to detect and mitigate transmission collisions. 

A collision is defined as the event when two or more end hosts transmit on a random access MAC physical LAN simultaneously, resulting transmission overlap perceived at any end host on the LAN. If a collision occurs in a random access MAC, all involved transmissions fail and must be retransmitted at a later time.

The advantage of random access MAC is the ability for an end host to utilize 100% of the link capacity as needed. However, the disadvantage is that if the demand for LAN access is high, many collisions and retransmissions can occur, resulting in a lower successful data transfer rate. Throughput is defined as the amount of data transmitted successfully (i.e. without collisions). If collisions are high, the throughput of a random access LAN can be a fraction of the total link capacity.

Ethernet is a widely used example of random access MAC. And, although not widely used in modern times, the ALOHA protocol is a classic example of random access MAC.

Ethernet

Ethernet is a CSMA/CD or Carrier Sense Multiple Access with Collision Detection protocol. As a random access MAC, it allows all end hosts to attempt transmission on the physical LAN at a given time. Probabilistically speaking, it is possible for more than one end host to begin a frame transmission at a given time. And, given the physical properties of the LAN, it is possible that multiple end hosts could begin transmission around the same time despite each detecting an idle LAN. To detect and mitigate such scenarios, Ethernet allows NIC transceivers to listen to the LAN while they are transmitting.

ALOHA

Unlike Ethernet, ALOHA does not provide the ability for an end host to listen to the LAN while transmitting. As such, when a collision occurs, it is not detected by any end host until after all colliding transmissions are complete.

Demand Assignment MAC

As the name implies, demand assignment MAC attempts to allocate the entire link capacity based on demand. It improves upon random access MAC by allowing a single end host to access the physical medium at any given time based on the amount of data the end host would like to transfer. There are two types of demand assignment MAC:

• Distributed control demand assignment MAC
• Centralized control demand assignment MAC

Distributed Control Demand Assignment MAC

In distributed control demand assignment MAC, a single token circulates between hosts on the LAN. Only the end host in possession of the token is allowed to transmit on the LAN. When an end host is finished with a transmission, it passes the token to the next host.

Centralized Control Demand Assignment MAC

In centralized control demand assignment MAC, a single token is allocated to end hosts by a centralized controller. Only the end host in possession of the token is permitted to transfer on the LAN.

The advantage of both distributed and demand assignment MAC is that the overall performance of the LAN is not sensitive to demand. However, the disadvantage is that end hosts must wait on the token in order to transmit. The amount of time spent waiting is undefined and could be long depending on the amount of data to be transmitted by the host in possession of the token. Thus, starvation is a possibility and unfortunate side effect of demand assignment MAC.

Characterization of Network Traffic

Traffic load and its characteristics can be a major contributor to the overall performance of a LAN. In an ideal network, all traffic would be predictable such that link allocation could be allotted perfectly with zero collisions, zero wait for link access, and 100% link capacity achieved. Unfortunately, in the real world, network traffic tends to be bursty. This is due to the behavior of applications and users that utilize the underlying network. For example, the release of a new television show by an online streaming provider could result in a temporarily large increase in traffic and network demand by watchers.

This bursty nature network traffic motivates the use of probabilistic models to drive the design and implementation of networks. Such models should be simple enough to evaluate for correctness, accurate enough to emulate real network traffic, and robust enough for use in a wide variety of real world scenarios.

Examples of Network Traffic

Digitized Audio/Video

In remote audio and video conferencing, audio and/or video is sampled and relayed over the network to participating parties. Pulse code modulation takes an analog signal and samples it at a particular rate and resolution to encode it digitally. This fixed-size digital interpretation of the audio/video is then relayed over the network at predictable intervals in order to facilitate real time communications. 

Interactive Data Transactions

In ecommerce, users interact with remote web servers hosting content. For example, a user might browser different web pages searching for products, selecting more detailed views, which the web server then relays to the user on demand. This type of traffic pattern in irregular in time and size.

Statistical Modeling of Network Traffic

Memoryless Traffic Source

For many applications that relay data over the network, any additional time elapsed between data transmissions does not appear to depend on the time already elapsed since the previous data was transmitted. Such a source of data is referred to as a memoryless source. Let’s derive a mathematical model for such a memoryless source. 

Consider a data source that produces data arrivals (i.e. data units) at any time starting at time t = 0. Such a source is referred to as a continuous source, since it continuously transmits data at periodic intervals.

Let the number of arrivals through time t be denoted A(t), where A(t) takes on integer values. 

The time between the (i – 1)th and ith arrival is referred to as the interarrival time and is denoted τ_i. If we model each interarrival time τ_i as a RV, then A(t) is a random process (RP), and the arrival rate of the source is given as:

Suppose the interarrival times {τ₁, τ₂, …} are independent RVs and that for each i, τ_i has PDF such that:

where h(t) is the same function for all i. If this is true, then A(t) is the arrival process for a memoryless source. The remaining lifetime distribution for the RV τ_i is given by:

So, a source is memoryless if the interarrival times of its arrival process have a remaining lifetime distribution:

that does not depend on s. The arrival process of a memoryless source is an example of a continuous time Markov chain and a continuous time birth-death process.

Example 1

Assume the PDF and CDF of the above arrival process are as follows:

Suppose s = 1:

For example, s = 1, t = 1:

Suppose s = 2:

For example, s = 2, t = 1:

As indicated by the examples, the interarrival times depend on s. Thus, the source is not memoryless.

Example 2

Assume the PDF and CDF of the above arrival process are as follows:

Suppose s and t are >= 0:

For example, s = 1, t = 1:

For example, s = 2, t = 1:

As indicated by the examples, the interarrival times do not depend on s. Thus, the source is memoryless.

Deriving the PDF and CDF of a Memoryless Source

What does the memoryless property tell us about the PDF of τ_i?

Recall that:

So:

If we set s = 0, we find that:

This implies that:

which means that we can rewrite:

as:

So:

If the PDF of τ_i is:

then:

So:

So:

But:

So:

And:

with initial condition:

Thus:

So, the CDF of a memoryless source is defined by:

And the PDF of a memoryless source is defined by:

Thus, a memoryless source will have exponentially distributed interarrival times.

Example 1

Suppose a memoryless data source has an arrival rate of four data units per second. What is the probability that the time between the first and the second arrivals is more than one second?

So:

Example 2

A memoryless data source with arrival rate λ starts at time 0. At t = 0, what is the density function of possible times for the first arrival?

At t = t₁, if no arrivals have occurred, what is the density of possible times for the first arrival?

Example 3

Suppose a memoryless source has an arrival rate of two per second. What is the probability that zero arrivals occur in the interval [t₁, t₂]?

If we assume that the (i - 1)th arrival is the last one before time t = t₁ and that it occurs at t = t₁ – t’. Then the answer is given by:

What is the probability that exactly one arrival occurs in [t₁, t₂]? We know that:

But this determines the probability that one or more arrivals occur in [t₁, t₂], which isn’t exactly what we’re after. We can show by solution of appropriate differential equations that:

Thus, the arrival rate of the memoryless source is:

which is a Poisson distribution.

Thus, it can be concluded that a continuous time, memoryless data source produces independent, exponentially distributed interarrival times. And, independent, identically distributed, exponentially distributed interarrival times result in a Poisson arrival process.

Example 4

Let A(t₁) = the number of arrivals in the time interval [0, t₁] for a Poisson arrival process with an arrival rate of two per second. A(t₁) is a Poisson-distributed RV with PMF:

What is the probability that A(t₁) is greater than two?

Fitting Models to Traffic Patterns

The arrival process of packet/frame can be modeled as a Poisson distribution given exponential interarrival times. If the interarrival times are fixed, such as in the audio/video example, a deterministic model is best suited. Lastly, an Erlang model best fits traffic such as the initiation of telephone calls. 

The lengths of packets/frames are commonly modeled as an exponential distribution given random traffic. However, if the traffic consists of fixed length packets/frames, then a deterministic model is more appropriate. On the other hand, a bimodal model is best suited for a mixture of short and long packets.

Poisson arrivals and exponential packet/frame lengths often provide a realistic model for interactive traffic in a computer network.

Measures of Network Performance

The performance of a computer network depends on:

• the initial state of the network
• the sequence of random inputs to the network (i.e. the arrivals)
• the random internal events within the network (i.e. data processing time, frame errors, retransmissions, etc.)
• the network architecture and protocols

Most analysis focuses on steady-state conditions, meaning the network has is exhibiting typical behavior. However, note that emphasis can also be placed on the network's response to a transient (i.e. one-time) event.

The type of performance measures to collect (i.e. means, percentiles, etc.) from the network depends on the goal of the analysis.

From a network operator's perspective, commonly sought after performance measures are throughput and utilization.

Throughput

The throughput of the network is the number of bits (or packets/frames) per second that were successfully transmitted at a given location (e.g. link or NIC) in the network. Note that any overhead for errors and retransmissions is not included in throughput. Throughput only includes the amount of data per second successfully transferred across the network as measured at a particular point. One can normalize throughput to a value between 0 and 1 by dividing by the transmission rate of the physical medium of the LAN.

Note that throughput can be computed for more than just a single physical point of a network. A "black box" network, which might consist of some unknown topology, can have its throughput measured by monitoring the total traffic per second that departs the network.

Furthermore, throughput can be computed from different perspectives in the network. If the goal is to compute the throughput of transmissions on the physical medium, then all bits from successfully transmitted frames are included in the calculation. On the other hand, if the goal is to compute the throughput of actual payload data across the network from end host to end host, the throughput computation will exclude the headers of the MAC protocol, as they would be considered overhead.

Utilization

The utilization of the network is the average fraction of time the physical medium of the LAN is busy. This includes all traffic, headers, unsuccessful transmissions, and retransmissions. Utilization can be determined by directly monitoring the physical medium of the LAN. If all transmissions on a LAN are successful, the utilization of the LAN is equal to the normalized throughput.

Related to utilization is channel efficiency, which is the utilization of the physical medium to carry actual data, excluding frame and MAC protocol overhead.