...
| 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
...
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.
...
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 {τ1, τ2, …} 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 = t1, 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 [t1, t2]?
If we assume that the (i - 1)th arrival is the last one before time t = t1 and that it occurs at t = t1 – t’. Then the answer is given by:
What is the probability that exactly one arrival occurs in [t1, t2]? We know that:
But this determines the probability that one or more arrivals occur in [t1, t2], 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(t1) = the number of arrivals in the time interval [0, t1] for a Poisson arrival process with an arrival rate of two per second. A(t1) is a Poisson-distributed RV with PMF:
What is the probability that A(t1) 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.