05. Local Area Networks and Ethernet

Misc.

Geometric RV:

Type 1, Bernoulli trial: returns probability of k failures before success: $P(k)=p(1-p)^k$ , Expected value is $(1-p)/p$
Type 2, probability of k trials before first success: $P(k)=p(1-p)^{k-1}$ , expected value $1/p$

LANs

Packet-switched networks
Limited geographic extension; usually less than a kilometer
Usually uses a shared transmission medium to multiple stations
Usually controlled by one particular entity
Often higher data rates than in WAN
Broadcast transmissions possible

Standards

Standards typically specify these layers:

Physical layer (PHY)
- Transmission media
- Network adapters
- Modulation schemes
- Data rates
- Network topologies
Medium Access Control (MAC) sub-layer
- Specifies how stations share the transmission medium
Possibly the link layer; error control and flow control (error control coding often done in hardware in the PHY layer)

IEEE 802 Series

IEEE = Institute of Electrical and Electronics Engineers. ISO has adopted several IEEE standards, including:

802.1: Overview, bridging, network management
802.2 Logical Link Control
802.3: Ethernet
802.11: WLAN
802.15: WPAN including Bluetooth

802.2 and 802.1’s MAC bridging are layer 2 protocols and thus, they are independent of the layer 1 protocols being used (WLAN, MAN etc.).

Rarely used today. All stations are attached via a tap line to the bus. Thus, signals are heard by all stations - it is a broadcast medium, so frames include a destination address. Parallel transmissions may collide, garbling packets.

Due to signal attenuation, the bus length is limited to a few hundred meters at most.

In addition, if the bus cable is damaged, the entire network will stop working.

Star Topology

Stations attached to a central unit via their own private cable. The cable often has separate cables for transmit and receive directions, allowing full-duplex.

The central unit can act as a repeater or bridge/switch. As a repeater, it copies incoming signals to all other outputs, which may congest the network. As a bridge/switch, it copies incoming frames to only where the destination is. The latter allows transmissions to occur in parallel.

There is still a signal point of failure, but the impact of a cut cable is much smaller.

Wireless Topologies

Wireless transmission media are much more prone to errors, and stations cannot necessarily hear all stations - the channel is time-varying and the links are volatile and unpredictable.

MAC Fundamentals

These schemes allow a set of distributed stations to efficiently coordinate access to a common channel. More specifically:

There are a number of stations wishing to communicate
There is a shared communications channel/resource that can be used by one station at a time
No other means for information exchange between stations exists

It is often regarded as a separate sub-layer between the PHY and link-layer.

Assumptions:

The shared channel is a broadcast medium - this may not be true for wireless transmission media
If parallel transmissions occur, all contending transmissions are garbled - once again, this may not be true for wireless transmission media

Desirable properties:

Small medium access delay - time between the arrival of a packet and start of a successful transmissions
- Collisions, waiting times etc. affect this
- Small access delay desirable if medium is lightly loaded
Fairness and fair re-use of unused resources
Low overhead and high throughput
Stability - increasing load should not decrease throughput

Orthogonal MAC Schemes

The behavior of one station does not influence the behavior of other stations. This is done by exclusively allocating resources to individual stations.

FDMA: frequency division multiple access; TDMA: time division; SDMA: space division; CDMA: code division.

FDMA

Each station is given a band of frequencies - a sub-channel they have exclusive transmission access to.

The channel bandwidth is subdivided into N sub-channels, with guard bands acting as safety margins between sub-channels and the fringe of the channel. This reduces interference between adjacent sub-channels.

To receive data, a station must have a separate receiver for each channel or a single tunable receiver - the latter has the issue of coordination as it must switch (related - tuning takes time) to the channel before data is transmitted onto the channel.

Performance

If the total available bandwidth is B (bps), station i is assigned 1/N of B (approximately - guard bands ignored) on a long-term basis.

Medium access delay is 0 as i can start the transmission immediately without risk of collision.

If a packet has size B/N bits, transmission takes one second. Thus:

\begin{aligned}. E[\text{Completion Time}] &= E[\text{Transmission Delay}] + E[\text{Access Time}] \\. &= E[\text{Transmission Delay}] + 0 \\. &= 1 s. \end{aligned}.

Advantages and Disadvantages

N stations can transmit in parallel, and there is no need for time synchronization between the transmitters.

However, each station either needs N receivers or tuneable receivers, frequency synchronization is needed, and there is no re-use.

In addition, there needs to be some way of allocating sub-channels; if there is a central station in charge of keeping track which channels are being used and processing allocations requests, what happens if it crashes?

Hence, FDMA is good for CBR but bad for VBR.

TDMA

Time is subdivided into successive super-frames of duration T_SF, with each super-frame being subdivided into N subframes (plus guard times to compensate for synchronization errors). Hence, time slots are assigned exclusively and on a longer-term basis a station i for transmission.

Performance

Each station gets the full bandwidth B (bps) for 1/N of the time (ignoring guard times).

If:

Station i owns one time slot
T_SF is 1 second
A time-slot has enough bandwidth to transmit B/N bits
A packet of B/N bits arrives at a random time to station i

Thus:

\begin{aligned}. E[\text{Access Delay}] &= \frac{T_{SF}}{2} = 0.5 s \text{ (on average)} \\. E[\text{Completion Time}] &= E[\text{Access Delay}] + E[\text{Transmission Delay}] \\. &= 0.5 s + 1/N s <= 1 s \text{( less than for} N > 2\text{)}. \end{aligned}.

Thus, on average, TDMA allows starting later and finishing sooner due to the full bandwidth being exclusively available.

Advantages and Disadvantages

Compared to FDMA, asymmetric bandwidth assignments is much easier - one station can use multiple time slots rather than having multiple receivers running simultaneously. In addition, it has better completion times on average, and does not require tunable receivers or multiple receivers.

The downsides are that tight time-synchronizations between stations is required and there is a high expected access delay on idle systems.

In addition, TDMA also requires signalling and shared state to allocate time slots and so has the same issues.

Hence, TDMA is also good for CBR but bad for VBR traffic.

Random Access Protocols

These protocols do not reserve channel resources or require a central station/shared state. Access to the medium is unpredictable, using randomness to avoid collisions.

ALOHA

N uncoordinated transmitters and one receiver (a base station). A collision occurs if two packets overlap at the receiver.

When a new packet arrives, it is put in a queue. Once the current packet is transmitted, it checks the queue and transmits the packet after a random backoff.

If the queue is empty, it calculates the checksum and transmits the frame immediately, then starts an acknowledgement timer.

The receiver sends an immediate ack on successful reception of a packet; if the ack timer expires, the transmitter enters backoff mode:

The transmitter chooses a random backoff time
When the backoff timer expires, the transmitter retransmits the frame
If the number of failed trials exceeds the threshold, the frame is dropped.

The choice of random distribution for backoff times plays a key role in controlling the delay, throughput and stability. Often, the distribution depends on the number of collisions seen by the frame.

ALOHA is simple to implement and if the network load is small, new frames are sent immediately - zero access delay, with the full channel bandwidth.

However, if A and B sends packets of the same length, there is a vulnerability period two frames long where a collision will occur if B sends the frame - one frame before and while A is sending the packet.

ALOHA has good throughput for low loads, but beyond a certain point, the increasing collision rate leads to decreased throughput - it is an unstable protocol.

If all packets have the same length and the package transmission time is \tau.

CSMA - Carrier Sense Multiple Access

These protocols assume that stations can determine the state of the medium (busy or idle) (almost) instantaneously.

This is called carrier-sensing or clear channel assessment, and allows for listen-before-talk: before transmitting a frame, it performs the CS operation. If the channel is busy, the station defers the transmission using some strategy. It usually has a maximum number of deferrals/backoffs for a frame. Note that this does not eliminate collisions completely - collisions can occur if the time difference between two stations starting a transmission is smaller than the propagation delay.

This works well when medium the propagation time is small compared to the packet length as it allows other stations to notice transmissions quickly after it is started. Thus, it can occur in local area networks, but is absolutely useless if the sender may have stopped the transmission by the time the receiver detects the start of the frame.

Non-persistent CSMA

After getting a new packet from the higher layer (with an empty queue), the station performs the carrier-sense operation. If the medium is idle, it can transmit immediately but if the medium is busy, it generates a backoff time from a random distribution. Then it can repeat the process until it succeeds or reaches some threshold.

In the case of a collision, a backoff time is chosen and the process repeats. How can collisions be detected? One solution is to expect an acknowledgement for each frame.

Performance issue: there is a high probability that the medium will be idle for some time after the previous transmission finishes (especially if the packet is long), lowering utilization.

If it is known there is a small number of transmitters, using a distribution returning small waiting time reduces the time gaps between packets, increasing throughputs.

p-persistent CSMA

A parameter p is known to all stations.

If the medium is busy, it defers until the end of the ongoing transmission.

It will then divide the time onto time slots, which should be just large enough to run the following:

With probability p it starts its transmission; otherwise, it defers for a further time slots
If it defers, it checks the medium, waiting until the end of the transmission if a new one starts
If a collision occurs, the process starts over

Choosing p is an issue, with a low value leading to stability in high load but low throughput as the medium will be idle after a transmission ends.

1-persistent CSMA or CSMA/CD

If the medium is busy, it defers until the end of the transmission.

When the medium becomes idle, the station sends unconditionally. This avoids idle times between transmissions.

However, if multiple stations start transmitting, a collision occurs and the transmitters detect this immediately - they need to be able to transmit and sense simultaneously. In this case:

The transmission is aborted
A jamming signal is sent to inform all stations about the collision
A collision resolution procedure is started (e.g. backoff)

Ethernet

Frame Format

| Length | Name |. | ------- | ----------- |. | 7 | Preamble |. | 1 | SOF |. | 6 | DstAddr |. | 6 | SrcAddr |. | 2 | Length/Type |. | 46-1500 | Payload |. | 4 | FCS |.

Uses Manchester encoding.

Preamble: for bit synchronization
Start of Frame: end of preamble, also for synchronization
Destination address
Source address
Length/Type field
Payload
- Minimum length due to CSMA protocol
- If higher level sends payload that is too small, the payload is padded: how does the receiver know which bits are padding? They can’t; it must pass it onto the higher layers
  - IP protocol: has length information embedded in it, so must use that
Frame Check Sequence: CRC checksum

Ethernet Addresses

A 48 bit, globally unique address. Each vendor gets its own address range and each Ethernet adapter has its own address.

Addresses are written as six colon-separated bytes in hexadecimal representation.

Special addresses:

The broadcast address is FF:FF:FF:FF:FF:FF
Addresses where the first bit is 1 are multicast addresses (except the broadcast address)
Addresses where the first bit is 0 are unicast addresses

Address filtering: a station will throw away any unicast addresses not addressed to itself.

Length/Type field

When L/T is bigger than or equal to 0x0600, it is a type field: it indicates the higher-layer protocol encapsulated in the Ethernet frame. Hence, it allows protocol multiplexing - a service to multiple higher-level protocols can be provided using a single lower-level SAP. Some common protocols:

| Type field | Protocol |. | ---------- | --------------- |. | 0x0800 | IPV4 |. | 0x0806 | ARP |. | 0x86DD | IPV6 |. | 0x8863 | PPPoE Discovery |. | 0x8864 | PPPoE Session |.

When L/T is less than or equal to 1500, it indicates the length of the payload; the first two bytes of the payload indicates the type (hopefully).

PHY

There are several different physical layers such as coaxial cables, twisted pair cables, and fibre cables.

Ethernet also supports two fundamentally different topologies: broadcast (almost never used today) and switched Ethernet.

Broadcast Topologies

All stations share the medium and hence, MAC is needed
Stations operate in half-duplex mode - they cannot simultaneously send and receive
In Ethernet, this can be achieved using the bus topology with coaxial cable or with hub-based topology
Called Half-Duplex Mode

Switched Topologies

Stations are attached to (possibly cascaded) switches via point-to-point links - a private cable. Hence, no MAC is needed (but is still used) and parallel transmissions are possible, although there may be contention for resources in the switch.

Stations operate in full-duplex mode - each link uses pairs of cables.

This is required for 100 Mbps and higher PHYs - basically all modern Ethernet.

Half-Duplex Ethernet MAC Protocol

CSMA/CD - Carrier-Sense-Multiple-Access with Collision-Detection.

This has very short medium access delays under light load, but the collision rate increases under heavy load with many stations - do not operate Ethernet beyond 50-60% load.

Assumes that parallel transmissions lead to collisions and that stations can monitor the medium for collision while transmitting - this works by checking the voltage on the medium and checking if this exceeds the voltage applied by the transmitter.

A new packet arrives at the MAC. The local collision counter,coll is set to 0
Carrier-sense operation performed
- If idle, the transmission starts immediately
- If busy, listen until the channel becomes idle. Start the transmission immediately
While transmitting, check for a collision. If this is detected
- Abort frame transmission and send a short jamming signal
- Increment coll. If coll > 16, drop the frame and set coll to 0
- Wait for a random time (backoff time) and go to the second step
If no collision is detected, transmit the whole frame and reset coll

Backoff time computation

The computation uses a truncated binary exponential backoff algorithm.

A random integer is uniformly generated the range $[0, 2^{min(10, coll)} - 1]$ - this is the backoff window, and is multiplied by the slot time.

The slot time is a common parameter that is just large enough to cover the maximum round-trip time and processing delays such that if two stations start transmitting one slot apart, the later one will notice.

The algorithm starts by assuming the number of contenders is small - if this is the case, you do not need many windows. If this fails many times, then it is likely that there are many contenders, so you need to increase the number of windows to reduce the probability of collision.

Minimum Frame Size/Slot Time

The minimum frame size (64 bytes for 10 Mbps) is chosen to ensure the transmitter can detect collisions - it can only detect collisions while it is still transmitting.

NB: the preamble and SOF are not included in the frame size calculation.

The maximum cable length and processing time from repeaters/hub is defined in the standard, so it is possible to generate the worst case:

Station A starts transmitting
Just before it reaches station B, station B starts transmitting
Station A can only detect the collision while it is still transmitting
Hence, the worst case delay is twice the propagation delay, plus some buffer for processing time

Bridges and Switches

Often, existing LANs need to be coupled together - this can be done at several different levels.

Layer	Name of device
PHY	Repeater/Hub
MAC	Bridge/Layer-2 switches
Network	Router
Application	Gateway

Marketing departments do not necessarily follow this terminology.

Repeaters and Hubs

Repeater

Repeaters are dumb devices which simply amplify a signal on the analog level. They amplify existing noise and add their own noise to the signal, but have very small delays and are completely protocol or modulation-agnostic.

Regenerating Repeater

These demodulates an incoming signal on a symbol-per-symbol basis and modulates it again.

They do no error checking so regeneration can introduce errors.

Hub

Hubs are centralized repeaters - they broadcast signals coming in on one port to all other ports. Only one station can transmit at a time,.

Hubs may or may not be regenerative.

Basically a bus, except in a star topology, so a single broken cable won’t kill the entire network.

Bridges

Bridges interconnect LANs on the MAC layer. They mostly connect LANs of the same type (e.g. Ethernet), or at least ones with the same MAC address structure. Bridges can be cascaded.

Bridges understand/interpret fields related to the MAC protocol (source/address fields); repeaters and hubs do not.

Basic Operation

Packet transmitted on LAN A
All stations on LAN A, plus the bridge, receive the packet
If the bridge knows the destination address belongs to a station in LAN A, it does nothing
- The bridge learns which stations are attached to which LANs over time by reading the source addresses of the packets transmitted on each LAN.
Otherwise, it transmits it to all other LANs it is connected too
- This is dangerous when several bridges are used and loops are present

Advantages

Reliability: failures in one LAN do not affect others as they are only interconnected by the bridge
Performance: allows several parallel transmissions as long as the packets do not cross LANs
Security: local traffic is not transmitted to other LANs

Layer-2 Switches

Stations are attached to the switch via point-to-point/private links with separate transmit/receive line (full-duplex). Hence, there is no broadcast medium so no need for a MAC. Instead, stations contend for the resources of the switch.

Switches transmit frames only to the correct output port, and can process frames in parallel - hence, they can increase network capacity as compared to LANs with a broadcast medium.

Frames arriving in parallel to the same destination are buffered.

Switches are transparent to stations.

Comparison to hub

Hub builds a broadcast medium - only one station can transmit at a time
A switch can accept up to N parallel transmissions, where N is the number of stations in the LAN
Each attached station can receive packets at full medium capacity