Data And Computer Communications - Data Link Layer [2]

Medium Access Control (MAC)

Multiple access protocols are a set of protocols operating in the Medium Access Control sublayer (MAC sublayer) of the Open Systems Interconnection (OSI) model. These protocols allow a number of nodes or users to access a shared network channel.

Consider an audio conference where

• if one person speaks, all can hear
• if more than one person speak at the same time, all voices are garbled

How should participants coordinate actions so that

• the number of messages exchanged per second is maximized
• time spent waiting for a chance to speak is minimized

In real life, Shared (Broadcast) transmission medium is mostly used (Ethernet, Wavelan, Satallite, Cocktail party etc.)

• message from any transmitter is received by all receivers
• two or more simultaneous transmissions by nodes: interference
• collision if a node receives two or more signals at the same time
• colliding messages are garbled

This is the Multiple Access Problem. We use Multiple Access Protocols to tickle it.

• How to allocate a single multi-access channel among competing users

Multiple access protocols:

• Determines how nodes share channel, i.e., determine when node can transmit
• Communication about channel sharing must use channel itself
• Goals are:
  • maximize message throughput
  • minimize mean waiting time

The MAC Protocols can be divided into 3 broad classes:

• Random Access / Partitioning (dynamic)
  • channel not divided, allow collisions
  • “recover” from collisions
  • carrier sensing: easy in some technologies (wire), hard in others (wireless)
  • CSMA/CD used in Ethernet
• Controlled Access
  • Nodes take turns, but nodes with more to send can take longer turns
  • polling from a central site, token passing
• Channel Partitioning, by time or frequency
  • divide channel into smaller “pieces” (time slots, frequency, code)
  • allocate piece to node for exclusive use
  • Time Division, Frequency Division, Code Division

Random Partitioning (dynamic)

When a node has packets to send:

• transmit at full channel data rate R.
• no a priori coordination among nodes
• In that case, when 2 or more tranmitting node, collision happened.

Random access MAC protocol specifies:

• How to detect collisions
• How to recover from collisions (e.g. via delayed retransmissions)

Examples of random access MAC protocols are:

• ALOHA
• Slotted ALOHA
• CSMA, CSMA/CD, CSMA/CA

ALOHA

The basic idea is applicable to any system in which uncoordinated users are competing for the use of a single shared channel.

There are 2 Types of ALOHA:

• Pure ALOHA
• Slotted ALOHA

Pure ALOHA

The idea of an ALOHA system is simple.

• Let users transmit whenever they have data to sent.
• If there are collisions, the both collided frames will be destroyed
• Due to the feedback property of broadcasting (ACK), a sender can always find out whether or not its frame was destroyed (or collision) by listening to the channel.
• If the frame was destroyed, the sender just waits a random amount of time (called back-of time) and sends it again.
• The waiting time must be random. If the waiting time is fixed, the same frames will collide over and over, in lockstep.
• Different stations wait for different amount of time will decrease the probability of further collision.

If the first bit of a new frame overlaps with just the last bit of a frame almost finished, both frames will be totally destroyed and both will have to be retransmitted later.

^In practice, sending and recieving frame are bidirectional.

In pure ALOHA, frames are transmitted at completely arbitrary times.

ABC frames are both destroyed.

There are 2 cases. When Sending A, It is possible that A would overlap with Previous message B, or future message C. To prevent collision, we need to ensure $t-T_{fr}$ to $t+T_{fr}$ has no other message transmit. Therefore the Vulnerable time = $2 \times T_fr$ (We assume all msg are same length)

• Vulnerable time = $2 \times T_{fr}$

• Throughtput = $G \times e^{-2G}$; Where G is the number of stations wish to transmit in the same time.

• Maximum Throughput = 18.4% for G=0.5

  • Only 18.4% of the channel will be utilized for sending data. Other time will either be idle time or collision time.

Slotted ALOHA

It was developed just to improve the efficiency of pure ALOHA as the chances for collision in pure ALOHA are high.

In Slotted ALOHA, assumed that:

• All frames are of same size
• Time is divided into equal size slots, the time to transmit one frame.
• Sending of data is allowed only at the beginninng of these slots
• Nodes are synchronized.
• If two or more nodes transmit in the slot, all nodes detect collision.

Operation of Slotted ALOHA:

• When the node obtains fresh frame, it transmits in the next slot
• If No collision, the node can send new frame in the next slot
• If collision, node retransmits frame in each subsequent slot until success

Pros of Slotted ALOHA:

• simple
• single active node can continuously transmit at full rate of channel
• highly decentralized: only slots in nodes need to be in sync

Cons of Slotted ALOHA:

• there are still collisions, wasting slots
• idle slots
• nodes may be able to detect collision in less than time to transmit packet
• clock synchronization can be a problem

We only need to worry if there is complete overlap. Therefore Vulnerable time = $T_{fr}$

• Vulnerable time = $T_{fr}$
• Throughtput = $G \times e^{-G}$; Where G is the number of stations wish to transmit in the same time.
• Maximum Throughput = 36.8% for G=1

Pure ALOHA vs Slotted ALOHA

Pure ALOHA	Slotted ALOHA
Any station can transmit the data at any time.	Any station can transmit the data at the beginning of any time slot.
The time is continuous and not globally synchronized.	The time is discrete and globally synchronized
Vulnerable time in which collision may occur = $2 \times T_{fr}$	Vulnerable time in which collision may occur = $T_{fr}$
Probability of successful transmission of data packet = $G \times e^{-2G}$	Probability of successful transmission of data packet = $G \times e^{-G}$
Maximum efficiency = 18.4%	Maximum efficiency = 36.8%
Main advantage: Simplicity in implementation.	Main advantage: It reduces the number of collisions to half and doubles the efficiency of pure ALOHA.

How Throughtput is calculated?

• We have made the frames all the same length.
• We assume that the infinite population of users generates frames (both new frames and retransmitted frames) according to a Poisson distribution with mean G frames per frame time.
• G is called offered load.
• Under all loads, the throughput is just the offered load, G, times the probability of a transmission being successful, i.e. $S = GP_0$
  • where $P_0$ is the probability that a frame does not suffer a collision, i.e. the probability of a transmission being successful.
• Now the probability that k frames are generated during a given frame time is given by the Poisson distribution
  • $P_{r}(k)=\frac{G^{k}}{k !} e^{-G}$
• The probability of zero frames is just $e^{-G}$.
• In an interval of two frame times long, the mean number of frames generated is 2G.
• The probability of no other traffic being initiated during the entire vulnerable period is thus given by
  • $P_{0}=P_{r}(0)=e^{-2 G}$
• Hence the throughput S is $S=G P_{0}=G e^{-2 G}$

Carrier Sense Multiple Access (CSMA) Protocols

In CSMA, a station that wishes to transmit attempts to avoid collisions by first listening to the medium to determine if another transmission is in progress.

• To minimize the chance of collision and increase performance
• Principle of CSMA: “sense before transmit” or “listen before talk”
  • Before sending the data, the station first listens to the channel to see if anyone else is transmitting the data at that moment
  • Carrier busy = Transmission is taking place
  • Carrier idle = No transmission currently taking place

When the channel is sensed to be idle (no transmission taking place), a station can take one of three different approaches (depending on the network design) to insert a packet onto the channel:

• non-persistent CSMA
• p-persistent CSMA
• 1-persistent CSMA (a special case of the p-persistent scheme)

Non-persistent CSMA:

Before sending, a station senses the channel.

• If the channel (medium) is idle, the station transmits a frame
• If the channel (medium) is busy, the station wait random amount of time and re-sense the channel

Better channel utilization but longer delays than 1-persistent CSMA.

1-persistent CSMA:

Before sending, a station senses the channel.

• If the channel (medium) is idle, the station transmits a frame with the probability of 1
• If the channel (medium) is busy, the station senses the channel continuously until channel becomes idle

Since the station transmits the frame with the probability of 1 when the carrier or channel is idle, this scheme of CSMA is called as 1-persistent CSMA.

p-persistent CSMA:

p-persistent CSMA applies to slotted channels

Before sending, a station senses the channel.

• If the channel (medium) is idle, transmit with a probability p; with a probability q = 1 – p, defer until the next slot
• If the channel (medium) is busy, the station senses the channel continuously until channel becomes idle

Collisions can still occur for all types of CSMA Scheme.

• due to propagation delay, two nodes may not hear each other’s transmission
• role of distance & propagation delay in determining collision probability

In above example, B first send the frame. While it is propagating, C sense the channel and think the channel is idle. Therefore C also send the frame and collision happened.

• Vulnerable time = Propagation time

See a Non-persistent CSMA collision example:

• Propagation time = a
• If within Propagation time there is other transmittion, Collision happens

CSMA/CD (Carrier Sense Multiple Access with Collision Detection):

If two stations sense the channel to be idle and begin transmitting simultaneously, they will both detect the collision almost immediately.

Rather than finish tramitting their garbled frames, they should abruptly stop transmitting as soon as the collision is detected.

The idea is to quickly terminating damaged frames to save time and bandwidth.

• Collisions detected within short time

• Colliding transmission aborted (a brief jamming signal to notify all stations of this collision), reducing channel wastage

• Widely used on wired LANs in the MAC sublayer

  • Easy in wired LANs: measure signal strength, compare transmitted, received signals
  • Difficult in wireless LANs: receiver shut off while transmitting

• Ethernet uses CSMA/CD to access.

The same variations exist as in CSMA; that is, there are nonpersistent, l- persistent, and p-persistent methodologies, each of which can have a slotted or unslotted version.

Let A, B, and C be the three stations attempting to transmit in a local area network using 1-persistent CSMA/CD with the exponential backoff algorithm. At a moment, they all sense the channel idle and send the data at the same time, hence, collision happens. What is the probability that the collision problem be resolved in their first retransmission after the collision?

When A,B,C send the data at the same time, collision happens. The collision is detected and thus a jamming signal is sent to clear the channel. Then pick a random number R between 0 and $2^k-1$ where K is 1 because it is the first collision. The random number R determines how long should the stations wait. ($T_B = R \times T_p$) The possible outcome of R after first collision would be:

For R numbers of ABC: 000, 001, 010, 011, 100, 101, 110, 111

• The probabilty of transmitting any data in first retransmission successfully = 3/8 = 0.375

Controlled Access

In controlled access, the stations consult one another to find which station has the right to send.

• A station cannot send unless it has been authorized by other stations.
• Three controlled-access methods:
  • Reservation
  • Polling
  • Token Passing

Reservation

Before sending the data, make reservation.

Reservation is first sent, then the data frame is sent.

• Time is divided into intervals.
• In each interval, a reservation frame precedes the data frames sent in that interval.
• No Collision would happen

Polling

Just like in HDLC, 1 Primary station will control the data sending of Secondary stations.

Device only being polled will send the data.

Device not polled will not be able to send the data.

• The primary device controls the link, the secondary devices follow primary device’s instructions.
• It is up to the primary device to determine which device is allowed to use the channel at a given time.
• No Collision would happen

Concerns (Drawbacks):

• polling overhead
• latency
• single point of failure (master)
  • If the master failed, no one can send

Token Passing (Token Controlled Technique)

Tokens are special bit patterns or packets, usually several bits in length.

• Token circulates from node to node when there is no message traffic.
• If a station want to send data, It holds the token until finish the transmittion. Then release the token.
• Only station get the token can send the data
• No Collision would happen

These techniques can be employed in ring or bus topologies.

Example: In a token ring the stations are connected logically in a ring with each station transmitting to the next sequentially around the ring.

Concerns (Drawbacks):

• token overhead
• latency
• single point of failure (token)
  • if the token is missing no one can send

Channel Partitioning

There are 3 Types of Channel Partitioning MAC Protocols:

• TDM (Time Division Multiplexing)
  • channel divided into N time slots, one per user;
  • inefficient with low duty cycle users and at light load.
• FDM (Frequency Division Multiplexing)
  • frequency subdivided

Time Division Multiple Access (TDMA)

Divide the channel into time slots

• Access to channel in “rounds”
• Each station gets own fixed length slot (length = packet trans time) in each round
• Unused slots go idle
• Only 1 user can use the particular time slot -> no collision

The only drawback is if the user do not use it, the slot would be idle and wasted

Example: 6-station LAN, slots 1,3,4 have packets, slots 2,5,6 idle

Frequency Division Multiple Access (FDMA)

Divide channel into frequency domain subchannel

• Channel spectrum divided into frequency bands
• Each station assigned own fixed frequency band
• Unused transmission time in frequency bands go idle

The only drawback is if the user do not use it, the subchannel would be idle and wasted

Example: 6-station LAN, 1,3,4 have packets, frequency bands 2,5,6 idle

Code Division Multiple Access (CDMA)

CDMA simply means communication with different codes.

Use different code to divide the channel into different subchannel

• Only one channel occupies the entire bandwidth of the link.
• All stations can send data simultaneously, no timesharing
• One channel carries all transmissions simultaneously.
• Each user assigned with a unique code $c_i$
• For sending data $d_i$ vector, it multiplies the sending user ( $= d_i \times c_i$)
• After multiplying, all messages are added together and send to the channel. (Multiplexing)
• To decode the data, mutliply the whole message with the user code $c_i$ to get decoded message $n \times d_i$ where $n$ is the number of stations.

The assigned codes have two properties:

• If we multiply each code by another, we get 0.
• If we multiply each code by itself, we get $n$
  • where $n$ is the number of stations.

$$d a t a=\left(d_{1} \cdot c_{1}+d_{2} \cdot c_{2}+d_{3} \cdot c_{3}+d_{4} \cdot c_{4}\right) \cdot c_{1}=4 \cdot d_{1}$$

CDMA is based on coding theory.

• Each station is assigned a code, which is a sequence of numbers called chips
• The Code must be in Orthogonal sequences (One example is Walsh codes)
  • Each station is made of n elements, where n is the no. of stations.
  • The inner product of two equal sequences is equal to n.
  • The inner product of two different sequences is 0.

E.g.

Order 1 Wash Matrix

$$\mathrm{W}_{1}=[+1]$$

Order 2 Wash Matrix

$$\mathrm{W}_{2}=\left[\begin{array}{ll} +1 & +1 \\ +1 & -1 \end{array}\right]$$

Order 4 Wash Matrix

$$\mathrm{W}_{4}=\left[\begin{array}{cccc} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & -1 & +1 \end{array}\right]$$

The relationship is like this:

Order 2N Wash Matrix

Let n = 4, Using the Order 4 Wash Matrix

$c_1 = [+1 + 1 +1 +1]$ = first row of Order 4 Wash Matrix

$c_2 = [+1 -1 +1 -1]$ = second row of Order 4 Wash Matrix

$c_3 = [+1 +1 -1 -1]$ = third row of Order 4 Wash Matrix

$c_4 = [+1 -1 -1 +1]$ = fourth row of Order 4 Wash Matrix

The inner product of two different sequences is 0.

$c_1 \times c_2 = [+1 + 1 + 1 +1]\cdot[+1-1+1-1]$

$= (1)(1) + (1)(-1) + (1)(1) + (1)(-1) = 0$

The inner product of two equal sequences is equal to N. The idea is the same.

Data representation in CDMA

Silence means no data sent.

Example:

• Each user assigned with a unique code $c_i$
• For sending data $d_i$ vector, it multiplies the sending user ( $= d_i \times c_i$)

After multiplying, all messages are added together and send to the channel. (Multiplexing)

Example:

[-1 -1 -1 -1] + [-1 +1 -1 +1] + [0 0 0 0]​ + [+1 -1 -1 +1] = [-1 -1 -3 1]

To decode the data, mutliply the whole message with the user code $c_i$ to get decoded message $n \times d_i$ where $n$ is the number of stations.

To get $d_i$ , just divide $n\times d_i$ by $n$.

Example: Decode $c_2$ message

[-1 -1 -3 1] x [+1 -1 +1 -1] = $n \times d_i$

$n \times d_i = (-1)(+1) + (-1)(-1) + (-3)(+1) + (+1)(-1)$

$n \times d_i = -1 + 1 -3 -1 = -4$

Since $n = 4$

$d_i = -4/4 = -1$

Therefore Bit 0

Local Area Network (LAN)

The use of shared transmission media or shared switching capacity to achieve high data rates over relatively short distances.

• Trying to link up several devices nearbys to form a network and then to exchange data between different devices. They are using the shared media.

LAN Techologies:

• Topology: bus, tree, ring and star
• Transmission Medium
• Medium Access Control (because shared media)

Common LAN Standards

LANs are dominated by 4 main architectures:

• Ethernet
• Token Ring
• Token Bus
• Fiber Distributed Data Interface (FDDI)

The first three are IEEE802 standards (i.e. originated from Project 802 of IEEE), while FDDI is an ANSI standard

IEEE Project 802 specifies the detailed functions of layers 1 and 2 (and small parts of layer 3)

The data link layer of existing LANs in use today are based on HDLC. Each is modified slightly for the specific needs or designs.

IEEE802 Standards:

• Ethernet is now defined by the IEEE802.3 standard

802.3 Ethernet Stardards

The most common LAN technology is Ethernet.

Ethernet is a communication protocol for Local Area Network (LAN) using same media interfaces (mainly RJ45 or fiber).

• Ethernet is now defined by the IEEE802.3 standard
• Ethernet was classified (Early state deployment) as:
  • Baseband (digital signaling using the Manchester scheme)
  • Broadband (analog signaling using PSK)
• Ethernet uses CSMA/CD as the access method

Now the most common one is Gigabit Ethernet.

Notation for Ethernet Standards

Some examples of baseband standards:

10Base5, 10Base2, 10Base-T, 100Base-T (Fast Ethernet)

• Field 1: <data rate in Mbps>
• Field 2: <signaling method>
  • Base(digital) or Broad(analog)
  • Nowadays all BaseBand.
• Field 3: <max. segment length in 100m> or <cable type>
  • The letter “T” stands for “twisted pair”.
  • The letter “F” stands for “fiber”.

Topology in Ethernet

• Traditional Ethernet features a shared- medium bus (Bus Topology)
• All signals are broadcast to every connected node (the links are half-duplex)
• For 10Base-T, the physical topology is a star, but the logical topology is a bus (Hubs)

^ Nowadays we use switch or hubs, but the idea is the same. They are working in shared environment.

Data Access in Ethernet

In the Ethernet there is no ACK, We are using CSMA/CD so we can ensure the transmittion is successful or not.

• Any device want to send the data simply put the data on the media
• Every deivce can see the destination of the frame (Shared/ Boardcast environment)
  • picks up the frames intended for itself (based on the physical address, which matches its own address)
• No need to send back ACK once received message

802.3 Ethernet Frame Structure

Preamble + SFD = 7 bytes with pattern 10101010 followed by one byte with pattern 10101011

• used to synchronize receiver, sender clock rates

• Preamble: 7 bytes with pattern 10101010
• SFD: 1 byte flag 10101011
  • Start frane delimiter
• Destination address and Source address (both 6 bytes)
  • If adapter receives frame with matching destination address, or with broadcast address (e.g. ARP packet), it passes data in frame to network-layer protocol
  • Otherwise, adapter discards frame
• Type: 2 bytes
  • indicates the higher layer protocol (mostly IP but others may be supported such as Novell IPX and AppleTalk)
• Data and Padding:
  • Minimum payload length 46 bytes
  • Maximum payload length 1500 bytes
• CRC: 4 bytes
  • checked at receiver, if error is detected, the frame is simply dropped

• 8 bytes Header (Preamble + SFD)
• 18 bytes overhead (Addresses + Type + CRC)
• Minimum payload length: 46 bytes
• Maximum payload length: 1500 bytes

For Frame Length, headers are ignored

• Minimum Frame Length: 18 + 46 = 64 bytes (512 bits)
• Maximum Frame Length: 18 + 1500 = 1518 bytes (12144 bits)

Why the Minimum Frame Length is 64 bytes?

Example:

A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal, as we see later) is 25.6 μs, what is the minimum size of the frame?

The frame transmission time is $T_{fr} = 2 × T_p = 51.2 μs$. This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision. The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet.

802.3 Ethernet Addressing

The MAC address is often referred to as the Ethernet Address on an Ethernet network. They are in fact the same thing.

MAC Address

The MAC (Media Access Control) address is a devices hardware address. Each device on a local area network must have a unique MAC address assigned. The MAC address is often referred to as the Ethernet Address on an Ethernet network. They are in fact the same thing.

MAC Address Also known as LAN / physical / Ethernet address.

• used to get datagram from one interface to another physically-connected interface (same network)
• 48-bit MAC address (for most LANs) burned in the adapter ROM
• Least significant bit of the first byte (last bit of first byte) defines the type of address
  • 0 - unicast (1 to 1 connection)
  • 1 - multicast (1 to many selective connection)

Example:

Some might use 0601:0201:2C4B for better notation.

MAC address and LAN address is the same thing

As mentioned, each network interface will be assigned 1 MAC address. The Address will be unique.

• Each adapter on LAN has unique LAN address.
• Broadcast address = FF-FF-FF-FF-FF-FF

• MAC address allocation administered by IEEE
• Manufacturer buys portion of MAC address space (to assure uniqueness)
• MAC flat address is portable
  • can move LAN card from one LAN to another
• IP hierarchical address NOT portable
  • depend on IP subnet to which node is attached
• If you move a device from one network to another network, MAC address doesn’t change. Only the IP address will change.

Address Resolution Protocol (ARP)

We look to frame structure. If we want to send data using Ethernet, we need to specify the end point within a link. That means we need to specify the source and destination address in the frame. That means in order to send the data we need to know the MAC address of the destination address.

We need ARP for knowing the MAC address of the destination address, by knowing the IP address.

• Each IP node (Host, Router) on LAN has ARP table
• ARP Table: IP/MAC address mappings for some LAN nodes
  • < IP address; MAC address; TTL>
  • TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)

If the host want to send data to a particular destination,

• First check for ARP table to see wthether it has the MAC address for that given IP address
• If no, we make use of ARP protocol to help us to find out the mapping

HOW ARP Protocol map the MAC address and IP address together?

Simply ask on the same network (using Broadcast address FF-FF-FF-FF-FF-FF ) and get the reply of MAC address.

• Asking all the members in the same network for MAC address on given IP address
  • using Broadcast address FF-FF-FF-FF-FF-FF
• Then get back the reply of the MAC address by that IP address
  • then record into ARP table
• ARP request is broadcast (1 to all)
• ARP reply is unicast (1 to 1)

Example:

• A wants to send datagram to B, and B’s MAC address not in A’s ARP table.
• A broadcasts ARP query packet, containing B’s IP address
  • Destination MAC address = FF-FF- FF-FF-FF-FF
  • all machines on LAN receive ARP query
• B receives ARP packet, replies to A with its (B’s) MAC address
  • frame sent to A’s MAC address (unicast)
• A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)
  • soft state: information that times out (goes away) unless refreshed
• ARP is “plug-and-play”:
  • nodes create their ARP tables without intervention from network administrator

How about if the Source and the Destination are not in the same network?

• Assume A knows B’s IP address, send datagram from A to B via R
• There are multiple ARP tables in router R, one for each IP network (LAN)

• A creates datagram with source A, destination B
• A uses ARP to get R’s MAC address for 111.111.111.110
• A creates link-layer frame with R’s MAC address as destination, frame contains A- to-B IP datagram
• A’s adapter sends frame
• R’s adapter receives frame
• R removes IP datagram from Ethernet frame, knows it is destined to B
• R uses ARP to get B’s MAC address
• R creates frame containing A-to-B IP datagram sends to B

Hubs

Hub is basically serval ports for us to connect devices.

Hubs are essentially physical-layer repeater.

• bits coming from one link go out all other links,
  • transmission from any station received by all other stations;
  • if two stations transmit at the same time, collision occurs
• no CSMA/CD at hub.
  • Only the adapters detect collisions
• provides network management functionality

Physically a star, logically a bus

Interconnecting with Hubs

If we want to form a larger network we use multiple hubs.

• Backbone hub interconnects LAN segments
• Extend maximum distance between nodes
• But individual segment collision domains become one large collision domain
• Cannot interconnect 10BaseT & 100BaseT

Switches

• Link layer device
  • Stores and forwards Ethernet frames
  • Examines frame header and selectively forwards frame based on MAC destination address
  • When frame is to be forwarded on segment, uses CSMA/CD to access segment
• Transparent
  • Hosts are unaware of presence of switches
• Plug-and-play, self-learning
  • Switches do not need to be configured

Frame Forwarding in Switch

Switches do not need to be configured.

A switch has a switch table

• The Entry in a switch table contains
  • MAC address
  • Interface (Port)
  • Time Stamp
• stale entries in table dropped (TTL can be 60 min)

Normally, Switch does not have a Switch table.

Switch learns which hosts can be reached through which interfaces

• when frame received, switch “learns” location of sender: incoming LAN segment
• records sender/location pair in switch table

Example:

• Device 1 want to send data to Device 4.
• Data Frame contain 1 as Source Address and 4 as Destination Address
• Switch table does not have record of Device 1
• Device 1 is added to the Switch table when passing the frame to switch

• Switch boardcast the data to see where is Device 4
• Device 4 capture the data, then Device 4 send data to reply Device 1.
• Data Frame contain 4 as Source Address and 1 as Destination Address
• Device 4 is added to the Switch table when passing the frame to switch
• This time Switching table knows the location of Device 1 already
• Data is forwarded to Port1 (Device 1)

Forwarding Methods of Switches

There are 2 types of Forwarding Methods of Switch. Depending on how we implement the switch function.

• Store-and-Forward
• Cut-Through

Store-and-Forward Switching

A store-and-forward switch receives the entire frame, and computes the CRC. If the CRC is valid, the switch looks up the destination address, which determines the outgoing interface. The frame is then forwarded out the correct port.

• Allows the switch to:
  • Check for errors (via FCS check)
  • Perform automatic buffering
• Slower forwarding process
  • need to wait for whole frame arrive then forward

Cut-Through Switching

A cut-through switch forwards the frame before it is entirely received. At a minimum, the destination address of the frame must be read before the frame can be forwarded.

• Allows the switch to start forwarding faster (normally in about 10 microseconds)
  • Only read to the destination address of the frame
• No FCS check
• No automatic buffering

Collision Domains

A collision domain is the segment where devices must compete to communicate.

• All ports of a hub belong to the same collision domain.
• Every port of a switch is a collision domain on its own.
• A switch break the segment into smaller collision domains, made device competition easier.

Switch: Traffic Isolation

• Switch installation breaks subnet into LAN segments
• Switch filters packets:
  • same-LAN-segment frames not usually forwarded onto other LAN segments
  • segments become separate collision domains

In the example, 3 Device compete in a collision domain

Switch: Dedicated Access

Switch has dedicated access.

This allow each devices connected to the Swtich send the data in the same time, without collision.

• Switch with many interfaces
• Hosts have direct connection to switch
• More than one station transmitting at a time, no collisions
• Full duplex
• Multiplying capacity of LAN

Each port is independent (Each port are not sharing medium)

Broadcast Domain

A broadcast domain is a collection of network devices that receive broadcast traffic from each other.

• In the same network = In the same broadcast domain
• Switches will forward broadcast traffic to all interfaces, except the one where it originated from.
• A lot of broadcast traffic might impact your network performance so reducing the size of the broadcast domain is something to consider.
• Routers do not forward broadcast traffic, they break broadcast domains.
• VLANs on switches also allow you to break broadcast domains.

Example: H1 send out the data, the other two device will also see the data.

Switch vs Router

• They are both store-and-forward devices
  • Routers: Layer 3 - network layer devices (examine network layer headers)
  • Switches are Layer 2 - link layer devices
• Routers maintain routing tables, implement routing algorithms
• Switches maintain switch tables, implement filtering, learning algorithms

Virtual LAN

A VLAN (virtual LAN) is a subnetwork which can group together collections of devices on separate physical local area networks (LANs).

• Virtual LAN Allow us to connect as far as we want
• Virtual means the device is virtually locate nearby

Why do we need VLAN?

A station is considered part of a LAN if it physically belongs to that LAN.

• The criterion of membership is geographic.

If we want to communicate between stations in two different geographical locations:

• We need to define a virtual local area network (VLAN) as a local area network configured by software, not by physical wiring.

• With VLAN, people can form networks without the restriction on physical locations

• VLANs make it easy for network administrators to partition a single switched network to match the functional and security requirements of their systems without having to run new cables or make major changes in their current network infrastructure.

• VLANs are often set up by larger businesses to re-partition devices for better traffic management

Virtual LANs

A virtual LAN, based on the VLAN 802.1Q standard, consists of a logical group of stations, independent of their actual physical locations. We can group our network no matter how far the devices locate.

• This switched network is logically segmented in such a way that stations can be grouped within an organization to provide an accounting VLAN, a marketing VLAN, etc.
• With VLAN, people can form networks without the restriction on physical locations
• The information used to identify a packet as part of a specific VLAN is inserted by a switch, and preserved through switch and router connections.
• One result of the logical segmentation is that one broadcast will reach every station belonging to the same VLAN, but not any other hosts.
  • in the same VLAN = same broadcast domain
• In addition, this switched network can be dynamically reconfigured without rewiring the wired connections between the switch and the various stations—a process that can save manpower for any organization that needs restructuring.

Two switches in a backbone using VLAN software

Example of VLANs in a company

We form different networks among different switches. Somehow we need to identify the different VLAN so that we can share traffic among the switches.

• We need a way to identify the VLAN number
• We some special operation in order to share the VLAN traffic among switches
• The port can be operated in 2 modes:
  • Access Mode
  • Trunk Mode

Access Mode or Trunk Mode

By default, a port is in access mode and carries traffic only for the VLAN to which it is assigned. In trunk mode, a port can carry traffic for multiple VLANs. For a trunk port, specify whether the port will carry traffic for all VLANs configured on the controller or for specific VLANs.

A switch port runs in either the access mode or the trunk mode.

• In the access mode: (normal operations)
  • interface belongs to one and only one VLAN
  • a switch port is normally attached to an end user device or a server
• In the trunk mode:
  • multiplexes traffic for multiple VLANs over the same physical link
  • In order to multiplex VLAN traffic, special protocols exist that encapsulate or tag,
    • i.e., mark, the frames so that the receiving device knows to which VLAN the frame belongs

Trunk protocols are either proprietary, e.g., Cisco proprietary Inter-Switch Link (ISL), or based upon IEEE 802.1Q standard.

Lets say We have 2 Switches here and form 2 different VLAN.

We want to share the VLAN traffic between 2 Switches.

So the 2 ports will be configurate to the Trunk mode operation so they are share the VLAN traffic.

• One device send the data, the other devices should see the same data because they are in the broadcast domain.

The VLAN Registration Protocol

Since VLAN switches are no longer plug-and-play, a mechanism is needed to save on the manpower required for the configuration of every VLAN switch.

• Switches should be able to register the set of VLANs to be trunked over a specific link without manually configuring every switch.
• A Generic VLAN Registration Protocol (GVRP) does exist in 802.1Q.
  • Used with IEEE 802.1Q-compliant dynamic VLAN creation and VLAN pruning on 802.1Q trunk ports.
• Used to maintain VLAN configuration consistency across the entire network and configures new VLANs.
• The VLAN is distributed through all switches in the domain, which reduces the configuration at every VLAN switch.

Tagging Ethernet Frames for VLAN Identification

How we can identify different VLAN in the Standard Ethernet?

• Achieved by Frame Tagging
  • Frame tagging is the process of adding a VLAN identification header to the frame.
  • It is used to properly transmit multiple VLAN frames through a trunk link.
• The protocol defines the structure of the tagging header added to the frame.

Tagging a frame by inserting a 802.1Q header

This information only appear in the Trunk mode

VLAN Configuration

There are typically 4 VLAN configuration options specified by either

• port group
• source MAC address
• network layer information, i.e., protocol or network address
• IP multicast group

Wireless LAN (WLAN or Wi-Fi)

Wireless Local Area Network is a shared environment.

• In the wireless environment
  • a signal sent from one user in the wireless LAN cannot be seen by all other users
  • attenuation will be much higher than wired environment
  • we need to handle mobile user who changes point of attachment to network

Wireless Network Architecture

The Elements of a Wireless Network:

• Wireless hosts - Laptop, Tablet, Smart Phone
  • can be in fixed location or moving
• Base station (Access Point) - Switch, Hub
  • forward the data of the wireless user to the wired internet
• Wireless link
  • link up the wireless host and base station together
  • Mulitple access protocol to control the use of the channel (Make sure no collision)

Wireless Link Characteristics

Differences from wired link:

• Decreased signal strength: radio signal attenuates as it propagates through matter (path loss)
• Interference from other sources: standardized wireless network frequencies (e.g., 2.4 GHz) shared by other devices (e.g., phone); devices (motors) interfere as well
• Multipath propagation: radio signal reflects off objects ground, arriving at destination at slightly different times

These disadventages make communication across (even a point to point) wireless link much more “difficult”.

All implementations (except the infrared), operate in the industrial, scientific, and medical (ISM) band, which defines three unlicensed bands in the three ranges 902- 928MHz, 2.400-4.835GHz, and 5.725-5.850GHz.

Wifi are usually 2.4 or 5 GHz.

High frequency would have higher bandwidth, resulting higher data rate.

Wireless LAN Configurations

There are 2 types of the configurations:

• Infrastructure Mode
• Ad hoc Mode

There are also 2 service sets are defined:

• Basic service set (BSS)
• Extended service set (ESS)

Infrastructure Mode

• Consist of at least 1 base station (access point)
• base station connects mobiles into wired network
  • communications are through the base station
• handoff: moving devices (e.g. mobile) changes base station providing connection into wired network
  • connect to nearest base station

On Single Hop: Host uses base station/access point to connect to the internet

On Multiple Hops: WMN uses wireless mesh router that serves as both access point and wireless router

Ad hoc Mode

• no base stations
• nearby devices will form a network exchange data by themselves
• nodes can only transmit to other nodes within link coverage
• nodes organize themselves into a network: route among themselves

On Single Hop: Point-to-point links

On Multiple Hops: Each host serves as routers (No base station)

Basic service set (BSS)

In infrastructure mode, Basic Service Set (BSS) (“cell”) contains:

• wireless hosts
• access points (base station)

In ad hoc mode, Basic Service Set (BSS) (“cell”) contains:

• only wireless hosts

Extended service set (ESS)

Extended Service Set involve multiple access points.

• Several BSSs connected by a distribution system form a so-called Extended Service Set (ESS), which behaves like a single network
• Distribution system can be any networks but usually a backbone wired Ethernet

Service Set Identifier (SSID)

SSID is used to identify the access point and its associated wireless network.

• When you choose Wi-Fi under Setting on your iPhone, for example, a list is displayed showing the SSID of each Access Point in range
• E.g. Each Service set has a SSID

How the people know the existence of a Wi-Fi network?

• The 802.11 standard requires that an Access Point periodically send beacon frames, each of which includes the Access Point’s SSID and MAC address.
• Your wireless device, knowing that Access Points are sending out beacon frames, scans the 11 channels (available frequency channels), seeking beacon frames from any Access Points that may be out there.

Beacon frame is one of the management frames in IEEE 802.11 based WLANs. It contains all the information about the network. Beacon frames are transmitted periodically, they serve to announce the presence of a wireless LAN and to synchronise the members of the service set.

802.11: Channels Association

Each Access Point (AP) will select one of the frequency channel to operate.

• AP admin chooses frequency for Access
• Interference possible if neighboring AP choose the same frequency channel

For the Host, in order to get access to a wireless network, It must associate with an particular Access Point.

• Scans channels, listening for beacon frames containing AP’s name (SSID) and MAC address
• selects AP to associate with
• may perform authentication process
• will typically run DHCP to get IP address in AP’s subnet

Passive Scanning and Active Scanning

There are 2 ways to scan channels.

Passive Scanning

Most of time we use Passive Scanning.

1. APs will send beacon frames to devices periodically. Wireless Device passively listen to the beacon frames to know the available channels
2. Association Request frame sent: H1 to selected AP
3. Association Response frame sent: selected AP to H1

Active Scanning

1. Probe Request frame broadcast from H1
2. Probes response frame sent from APs
3. Association Request frame sent: H1 to selected AP
4. Association Response frame sent: selected AP to H1

MAC layers in IEEE 802.11 standard

• Divided into LLC sublayer and MAC sublayer
• In MAC control, there are 2 functions
  • Point coordination function (PCF)
    • provide a contention-free service using Polling (Optional)
  • Distributed Coordination Function (DCF)
    • provide a contention service for users using Random Access Protocol (CSMA/CA)

Multiple Access in WIFI environment

CSMA - sense before transmitting

• Don’t collide with ongoing transmission by other node

We don’t use CSMA/CD here - Can’t do Collision detection in Wireless environment

• Difficult to receive (sense collisions) when transmitting due to weak received signals (fading)
• Cannot sense all collisions in any case: hidden terminal, fading
  • Hidden Node Problem

Therefore we need to use CSMA/C(ollision)A(voidance) to Avoid Collisions.

Hidden Node Problem

Wireless networks have fuzzier boundaries

• Each node may not be able to communicate with every other node
  • due to the limit of coverage

In this example,

• Device A can see the signal from both B and C
• Device B can’t see the signal from C
• Device C can’t see the signal from B
• Both B and C will sense channel and find it idle.
• If B and C both want to send the data to A at the same time, Collision will happen
• B and C cannot detect any collision because they cannot see the other signal
• B and C will think their transmittion were successful but in fact it is not.

Distributed Coordination Function (DCF)

The MAC’s distributed coordination function (DCF) uses CSMA/CA (collision avoidance) as the access method.

Wireless LANs do not implement CSMA/CD because:

• For collision detection (CD), a station would need to simultaneous send data and to receive collision signals. This would require costly stations and increased bandwidth requirements.
• Collision may not be detected because of the hidden-station problem.
• The communicating stations can be very far apart. Signal attenuation could make it difficult for a station at one end to hear a collision at the other end.

CSMA/CA (collision avoidance) with RTS/CTS

The Idea is to allow sender to “reserve” channel rather than random access of data frames.

Therefore collisions of long data frames can be avoided.

• Sender first transmit small RTS (Request to Send) packets to Receiver using CSMA
  • RTSs may still collide with each other (but they’re short)
• Receiver broadcasts CTS (Clear To Send) in response to RTS
• RTS heard by all nodes
  • sender transmits data frame
  • other stations defer transmissions

• IFS are interframe spacing, as waiting time To give sufficient time for processing data
• When a station acquires access to the channel, that station’s RTS-frame indicates the duration that station will occupy the channel.
• The NAV (Network Allocation Vector) is a timer at all other stations to show the time that must pass, before these other stations may next check the channel for idleness.

Before sending a frame, the source-station senses the medium by checking the energy level at the carrier frequency.

1. The sender uses a persistence strategy with back-off until the channel is idle.

2. After the channel is found to be idle, the station waits for a period of time -the “distributed inter-frame space”(DIFS).

3)The station sends a control frame - the “request to send”(RTS).

The destination-station receives the RTS and then waits a period of time -the “short inter-frame space”(SIFS).

The destination-station sends a control frame, the “clear to send”(CTS), to the source station.

The source-station sends data after waiting SIFS.

The destination-station waits SIFS, and then sends an acknowledgment to show that the frame has been received. (Acknowledgment is needed, because the source-station has no other means to check for its data’s successful arrival at the destination-station.)

When a station acquires access to the channel, that station’s RTS-frame indicates the duration that station will occupy the channel.

The NAV (Network Allocation Vector) is a timer at all other stations to show the time that must pass, before these other stations may next check the channel for idleness.

Collision still happens in Control message exchange. Example:

Priority IFS Values:

• SIFS (short IFS)
  • highest priority
  • for all immediate response actions
  • Used in following circumstances:
    • Acknowledgment (ACK)
    • Clear to Send (CTS)
    • Poll response
• PIFS (point coordination function IFS)
  • used by the centralized controller in PCF scheme when issuing polls
• DIFS (distributed coordination function IFS)
  • used as minimum delay for asynchronous frames contending for access
  • used for all ordinary asynchronous traffic

Point Coordination Function (PCF)

The point coordination function is

• optional,
• for an infrastructure network,
  • only infrastructure network has Access Point (AP)
• used mostly for time-sensitive transmission,
• implemented on top of the DCF,
• PCF has a centralized, contention-free polling access method.
  • The AP polls stations that can be polled, one station after another.
  • The polled station may send its data to the AP.

To prioritize PCF over DCF,

• SIFS is same as in DCF,
• PIFS (PCF IFS) is shorter than the DIFS.

An AP wanting to use PCF is prioritized over a station wanting to use only DCF simultaneously.

Due to the priority of PCF over DCF, stations that only use DCF may not gain access to the medium. To prevent this, a “repetition interval”, which is repeated continuously, has a contention-free (CF) period, which starts with a “beacon frame” and ends with a “CF end” frame during which NAV applies to all other stations. Contention period is used to allow the contention-based stations to use the medium.

• Beacon frame and CF end frame determine the NAV period
• In NAV period, User is not allowed to send data by its own using DCF
  • They can send data only when they are polled by the AP

In order to use the DCF function, we will divide the frame into 2 period:

• Contention-free period for using PCF
  • Access Point controls data sending
• Contention period for using DCF
  • User determine when to send using CSMA/CA

Example:

CFP: Contention-Free Period

CP: Contention Period

STA: Station

802.11 Wireless Frame Format

It is quite similar to Ethernet frames.

• Frame Control (FC): type of the frame and control information
• Duration (D): set the value of NAV (Duration of Data transmission)
• Addresses: MAC address
• SC: Sequence Control
• Frame body: Information based on the frame type
• Frame Check Sequence (FCS): CRC-32 error detection sequence

Total 34 byte headers

No Minimum Frame Requirement in WiFi environment because we are not using Collision Detection

RTS

• Only 2 Address Field (Source and Destination)

CTS or ACK

• For ACK, D is not needed.

802.11 Wireless Frame Addressing

Four cases to interpret the addresses in the frame depending on “To DS” and “From DS” in the FC field

Normally MAC address is used to serve as SSID.

If Source and Destination are in the Same Service Set (Same Wireless Network):

• To DS =0 and From DS=0
  • Not going to a distribution system
  • Not coming from a distribution system

If the Source is coming from outside distribution system:

• To DS =0 and From DS=1
  • Not going to a distribution system
  • Coming from a distribution system

If the Data is Sending to outside distribution system:

• To DS =1 and From DS=0
  • Going to a distribution system
  • Not coming from a distribution system

Access Point is Sending to other Acces Point

• To DS =1 and From DS=1
  • Going to a distribution system
  • Coming from a distribution system

Switching Networks

Why Switching?

• Point-to-point links are useful for connecting users at different locations to their ISP or remote computer
• However, how can the ISP connect a large number of users to the Internet and among themselves over a long distances?
  • One solution is also use point-to-point connection to create a mesh topology
  • A shared medium that allows only one transmission at a time is not efficient
• A much better approach to share a medium is switching
• The device that performs switching is called a Switch

The Network simply works like a Switch.

• Switched network consists of a number of switches connected one another, which provide connection to external nodes

There are two main types of switching technologies:

• Circuit-switching
• Packet-switching

Circuit Switching

The physical connection created by circuit switching is used by the two nodes exclusively, i.e. no other nodes share the bandwidth during the whole session

Circuit-switching creates a direct physical connection between two nodes

• Designed mainly to support telephone network
• No delay in the intermediate devices
• There is Substantial wastage if the connected nodes do not communicate all the time
  • If the nodes transfer data for 10% of time, then the remaining 90% of time is idle and wasted
  • It is inefficient for Internet browsing, but good for voice or other constant bit rate data transfer

Packet Switching

Internet and many other computer related types of traffic are bursty in nature, i.e. the transmission is highly irregular in time. E.g. Sometimes there are a lot of data to transfer, but at other times, there maybe nothing to send/receive.

In order to provide better way to send data over the switching network, we use Packet Switching.

• Designed mainly for data
• Data are broken down into separate units with variable lengths called packets before transmission
  • send the packet 1 by 1 to the network
  • Larger Packet size = more efficient
• In order to transfer packets across a packet-switched network and arrive at the specified destination, control information must be added to packets in a header and/or trailer.

There are two main approaches to implement packet switching

• Datagram approach
• Virtual circuit approach

Datagram approach

Packets under this approach is called a datagram

• Each packet is treated independently from one another
• Different Packets may take different paths to travel from the source to the destination
• Packets may arrive out of order, and the transport layer need to re-ordering them
• Internet is using Datagram approach

Example: In datagram approach, each transmission may use several routes (e.g. A’s datagram 4 go directly from S1 to S3 to S5, while datagram 1 go from S1 to S2 to S3 to S5)

Virtual circuit approach

In the virtual circuit (VC) approach, all packets of the same message is transferred via a preplanned route (the same route)

• Setup a virtual circuit first to determine the routes
  • Each packet take the fixed routes to travel from the source to the destination
• Packets arrive in original order
• Virtual Circuit Identifier (VCI) is used to identify the route
  • Incoming data are assigned with a Unique VCI number
  • Outgoing data are also reassigned with a Unique VCI number

Example:

Types of Virtual Circuit

Two main methods of setting up virtual circuit:

• Permanent virtual circuit (PVC)
• Switched virtual circuit (SVC)

Permanent virtual circuit (PVC)

• Set up by the network provider and is in place all the time
• No need to set up the VC before or terminate the VC after transmission

Switched virtual circuit (SVC)

• Set up every time when a VC is needed, and terminated after the transmission
• The same nodes may get the same or a different VC every time according to network conditions
• More flexible, but requires set up time before data transfer begins

Example: The three phases of a switched virtual circuit

Virtual Circuits vs Datagram Approach

• Virtual circuits
  • network can provide sequencing and error control
  • packets are forwarded more quickly
  • less reliable
• Datagram
  • no call setup phase
  • more flexible
  • more reliable

Circuit vs Packet Switching

Performance depends on various delays

• propagation delay
• transmission time
• node delay

Range of other characteristics, including:

• transparency
• amount of overhead

Event Timing