Networking chapter 5

The data link layer and physical layer

data link layer

• Responsible for carrying a packet from one hop (computer/router) to the next hop

• Has local responsibility, unlike the network layer

• Between physical(receives services from) and network layer(gives services to)

error control

• Refers to both error detection and error correction

• In the data link layer, it refers primarily to methods of error detection and retransmission

error detection and correction

• Mainly a data link layer function

• Mechanism for detecting any abnormalities in data during transfer from one device to another

• Include redundant error detection (and correction) codes with the data

types of errors

• Single-bit

• Burst

single-bit error

• Only one bit in a data unit (byte, character, packet, etc.) has changed

• Less likely to occur in serial transmission

• Most likely to occur in parallel transmission

burst error

• 2 or more bits in the data unit have changed

• Most likely to occur in serial transmissions

types of error correction

• By retransmission

• Forward

forward error correction

• Include enough redundant information (called error-correcting codes) to enable the receiver to deduce what the transmitted data must have been

• Applicable on unreliable channels such as wireless links

error correction by retransmission

When an error is detected, the receiver will tell the sender to retransmit the entire data unit

error-detecting codes

• Include only enough redundant information to allow the receiver to deduce that an error occurred (not which error) and have it requrest retransmission

types of error-detecting

• Parity check

• Cyclic redu

parity check

• Most common error-detecting code

• Has two varieties,

simple parity check

• A redundant bit is added to every data unit so that the total number of 1s in the unit becomes even or odd

• Can detect all single-bit errors

• Can detect burst errors only if the total number of errors in each data unit is odd

two-dimensional parity check

• A block of bits(data) is organized in a table (rows and columns)

• Adds an extra row & column (row and column parities)

• Adds more overhead

• Can detect most errors

• If 2 bits in one data unit are damaged and the two bits in exactly the same position in another data unit are also damaged, the checker will not detect an error

cyclic redundancy check

• Based on binary division

• The CRC is appended to the end of a data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number

data link control

• Combination of flow control and error control

• Important responsibilities for reliable data delivery across the link

flow control

• Refers to a set of procedures used to restrict the amount of data that the sender can send before receiving an acknowledgement

• It is an end-to-end mechanism for regulating traffic between source and destination

congestion control

• A mechanism used by the network to limit congestion

• Difficult to separate from flow control so we will refer to both as flow control

limiting factors of flow control

• Speed of the receiver to process incoming data

• Amount of memory (buffer) to store incoming data before processed

• Network capacity

halt transmission

Because the rate of processing is normally slower than rate of transmission, the receiver must be able to inform the sender to temporarily ____ _________ until it is ready to receive more

lack of flow control

When overload occurs

• Queues build up

• Packets are discarded

• sources retransmit messages

• congestion increases → instability occurs

outside the network

flow control prevents network instability by keeping packets waiting _______ ___ ________ rather than in queues inside the network - avoids wasting network resources

automatic repeat request

Anytime an error is detected, specified frames are retransmitted. This process is called _________ ______ _______

flow and error control mechanisms

1. Unrestricted Simplex Protocol

2. Stop-And-Wait ARQ

3. Sliding Window Protocols

unrestricted simplex protocol

• Transmission from sender to receiver (simplex transmission)

• Processing time is ignored, the receiver is assumed to process the received data infinitely quickly

• Infinite buffer space assumed to be available

• Communication channel assumed to be free of error

stop-and-wait ARQ

• Protocols in which the sender sends one frame and then waits for an acknowledgement before proceeding

• Data traffic is simplex, but frames travel in both directions; hence a half-duplex physical channel suffices

• This protocol fails if ack frames by the receiver do not arrive or are late; the sender may time-out and send a frame again creating duplicate frames

  • The solution is to give sequence numbers to data frames and acks

situations of stop-and-wait ARQ

• Normal operation

• The frame is lost

• The ack is lost

• The ack is delayed

sliding window protocols

• Stop-and-wait ARQ is not efficient (only one frame is sent)

• Method of transmitting multiple frames while waiting for an ack

• Uses full-duplex transmission

• Two protocols

  • Go-Back-N ARQ

  • Selective Repeat ARQ

• Uses numbered frames

• Uses sequence numbers of the range of 2^m - 1 where m is the number of bits of the sequence number in the frame header

go-back-N-ARQ

• The sender and receiver have sliding windows of size max(2^m - 1) and 1 respectively

  • Other protocols such as TCP allow variable size windows

• The sender’s window holds frames sent but not acknowledged

• The sender sets a timer for each frame sent; the receiver has no timer

• The receiver sends positive acknowledgements if a frame has arrived safe and in order

• If a frame is damaged or out of order, the receiver discards it and keeps silent and discards all subsequent frames; this causes the timer of the sender to expire and goes back and resends all frames, beginning from the one with the expired timer

• The receiver does not need to acknowledge frames individually

• In GO-Back-N ARQ, the task of the receiver is simplified; no need to buffer out-of-order frames; they are simply discarded

  • This protocol is inefficient for a noisy link that has a high probability of damage resulting in the resending of multiple frames

• Requires resending only the damaged frame

• Defines a negative ack (NAK) that reports the sequence number of a damaged frame before the timer expires

• The sender and receiver windows are both at most half of 2m

• The receiver's window defines the range of acceptable sequence numbers

examples of data link protocols

• High-level data link control

• Point-to-point protocol

high-level data link control

• An ISO standard

• An actual protocol designed to support both half-duplex and full-duplex communication over point-to-point and multipoint links that implements the ARQ mechanisms

point-to-point protocol

Used in the Internet for router-to-router and home user-to-ISP traffic

Medium access control sublayer

In a network, two devices can be connected by a dedicated link or a shared link. Types include:

• Point-to-point access

• Multiple access

point-to-point access

When two devices are connected by a dedicated link and this link can be used by them at any time

multiple access

• When two devices are connected by a shared link

• When two devices in a this situation get access to the link or a channel in the link, they may need to use a point-to-point access protocol to exchange data

multiple access protocols

• Address the problems of controlling the access to the medium

• Similar to the rules of speaking in an assembly:

  • The right to speak is upheld

  • Two people do not speak at the same time

  • Do not interrupt each other

  • Do not monopolize the discussion

categories of multiple access protocols

1. Random Access Protocols (try your best like taxis do)

2. Controlled-Access Protocols (get permission)

3. Channelization Protocols (simultaneous use)

random access protocols

• Each station has the right to use the medium without being controlled by another station.

• collision may occur if more than one station tries to send

• We need a procedure to answer the following questions

  • When can a station access the medium?

  • What can the station do if the medium is busy?

  • How can the station determine the success or failure of the transmission?

  • What can the station do if there is an access conflict?

types of random access protocols

• MA - Multiple access

• CSMA - Carrier Sense MA

• CSMA/CD - CSMA with Collision Detection

• CSMA/CA - CSMA with Collision Avoidance

multiple access of random access protocol

• ALOHA is the earliest RA method developed at the University of Hawaii in the early 1970s

• Originally designed to be used on a radio LAN with a data rate of 9600 bps

• Can also be used in satellite and wireless transmissions

how MA of RAP works

• A base station serves as a central controller

• Each station sends a frame to the base station with an uploading frequency of 407 MHz (solid line)

• The base station sends it to the receiver using a downloading frequency of 413 MHz (dashed line)

• Potential collisions exist (on the upload link) so wait for acknowledgement

• If none arrives, wait a period of time (2 times the maximum propagation delay) send again if back off limit did not reach

• The time it waits increases from one trial to the next

versions of MA of RAP

• pure ALOHA

• slotted ALOHA

slotted ALOHA

• Time is divided into discrete intervals of one packet duration

• Transmitting a frame is allowed only at the beginning of a slot

• Still collision is possible; collided packet are retransmitted after a random delay

carrier sense MA

• Polite version of ALOHA

• To minimize the chance of collision, each station first listens to the medium before sending - “listen before talk”

• If the channel is busy, it waits until it is idle

• Otherwise it transmits if a collision occurs, it waits a random amount of time and starts listening again

• the chance of collision is minimized but may still occur because of the propagation delay (a station doesn’t know if another one has just started transmitting) orif two or more stations start transmitting at the same time

persistence strategies

• non-persistence

• persistence

non-persistent

• Sense a line and send if it is idle otherwise wait a random amount of time before listening

  • Less greedy than continuously listening

• Reduces the chance of collision, but also reduces the efficiency of the network and has longer delays

persistant

• Sense a line and “send” if it is idle

• Otherwise listen

• Two variations of sending

  • 1-persistent

  • p-persistent

1-persistent

If the line is idle, send immediately (with probability 1)

p-persistent

• If the line is idle, send with probability p and refrain from sending with probability 1-p

• Implementation: the station generates a random number between 1 and 100; if it is <p, then it sends, otherwise it refrains

• Reduces the chance of collision and improves efficiency

• Depends on the value of p

CSMA with collision detection

• Adds a procedure to handle a collision

  If a collision is detected and to reduce the probability of collision the second time, the sender waits - it has to back off

• It waits a little the first time, more if a collision occurs again, much more if it happens a third time, and so on; finally gives up

• Line sensing is done by using one of the persistent strategies

• Used in traditional ethernet; CSMA was never implemented

exponential backoff method of CSMA/CD

The amount of time to wait after a collision is between 0 and 2^N * maximum_propogation_time where N is the number of attempted transmissions

jam

Sending a ___ alerts the other stations and also to discard the part of the frame received

CSMA with collision avoidance

• Avoids collision

• Uses one of the persistence strategies

  • After it finds the line idle It waits an IFG (interframe gap) amount of time

  • It then waits another random amount of time, after that it sends the frame and sets a timer

  • If it receives an ack before the timer expires, the transmission is successful

  • Otherwise something is wrong (the frame or the ack is lost) - waits for a backoff amount of time and re-senses the line

• Used in wireless LANs

controlled access protocols

• the stations consult one another to find which station has the right to send

• A station can not send unless it has been authorized by other stations

types of controlled-access protocols

1. Reservation

2. Polling

3. Token Passing

reservation

• A station needs to make a reservation before sending data

• Time is divided into intervals

• In each interval, a reservation frame precedes the data frames sent in that interval

• If there are N stations in the system, there are exactly N reservation mini-slots in the reservation frame

polling

• For topologies in which one device is designated as a primary station and the other stations are secondary stations

• The primary asks the secondaries if they have data to send (polling)

• When the secondary has data to be sent, the primary tells the secondary to get ready to receive (selecting)

token passing

• A station is authorized to send data when it receives a special frame called a token

• The stations are arranged around a ring (each station has a predecessor and a successor)

• A token circulates around the ring when no data is transmitted

• When a node wants to transmit:

  • Wait for a free token

  • Remove token from ring (replace with busy token)

  • Transmit message

  • When done transmitting, replace free token on ring

token

• Bit sequence

• Used in token passing

• Free: 01111110

• Busy: 01111111

token failures

• Tokens can be created or destroyed by noise

• distributed solution

  • Nodes are allowed to recognize the loss of a token and create a new token

  • Collision occurs when two or more nodes create a new token at the same time → need collision resolution algorithms

node failure in token processing

since each node must relay all incoming data, the failure of a single node will disrupt the operation of the ring

example of token passing protocol

• FDDI - Fiber Distributed Data Interface - is a 100 Mbps fiber optic token ring LAN standard

• It is also used for MANs

channelization protocols

The available bandwidth of a link is shared in time, frequency, or through code, between different stations

types of channelization protocols

1. FDMA - Frequency Division MA

2. TDMA - Time Division MA

3. CDMA - Code-Division MA

frequency division MA

• The available bandwidth is divided into channels; each station uses its allocated band to send its data; each band is reserved for a specific station (it belongs to it all the time)

• A data link layer protocol that uses FDM at the physical layer

• Used in cellular telephone and satellite networks

time-division MA

• The entire bandwidth is just one channel

• The stations share the capacity of the channel in time

• Each station is allocated a time slot during which it can send data

• A data link layer protocol that uses TDM at the physical layer

• Also used in cellular telephone

code-division MA

• Differs from FDMA because only one channel occupies the entire bandwidth of the link

• Differs from TDMA because all stations can send data simultaneously (no time sharing)

• Based on coding theory

• Proposed several decades ago, but implemented recently due to advances in technology

WAN and modem connections

There are various data link protocols that are required for ___ and _____ _________

logical link control

Data link protocol of LAN

examples of data link layer protocols

1. Synchronous

2. High-Level

3. Serial Line Interface

4. Point to Point

5. Link control

6. Link Access Procedure

7. Network Control

synchronous data link protocol

• Basically communication protocol of computer

• Usually supports multipoint links even error recovery or error correction also.

• It is usually used to carry SNA (Systems Network Architecture) traffic and is present precursor to HDLC

• Designed and developed by IBM in 1975

• Used to connect all of the remote devices to mainframe computers at central locations

• May be in point-to-point or point-to-multipoint connections.

• Used to make sure that the data units should arrive correctly and with right flow from one network point to next network point

high-level data link protocol

• basically a protocol that is now assumed to be an umbrella under which many Wide Area protocols sit

• Adopted as a part of X.25 network

• Originally created and developed by ISO in 1979

• Based on SDLC

• Provides best-effort unreliable service and also reliable service

• A bit-oriented protocol that is applicable for point-to-point and multipoint communications

serial line interface protocol

• An older protocol that is just used to add a framing byte at end of IP packet

• Basically a data link control facility that is required for transferring IP packets usually among Internet Service Providers and a home user over a dial-up link.

• Is an encapsulation of the TCP/IP especially designed to work with over serial ports and several router connections simply for communication

• Has some limitations like it does not provide mechanisms such as error correction or error detection.

point-to-point protocol

• Basically used to provide same functionality as SLIP

• The most robust protocol that is used to transport other types of packets also along with IP Packets

• Can also be required for dial-up and leased router-router lines

• Provides framing method to describe frames

• It is a character-oriented protocol that is also used for error detection

• Provides two protocols:

  • LCP is used for bringing lines up, negotiation of options, and bringing them down

  • NCP is used for negotiating network-layer protocols

• Required for same serial interfaces like that of HDLC

link control protocol

• Was originally developed and created by IEEE 802.2.

• Also used to provide HDLC style services on LAN (Local Area Network).

• Basically a PPP protocol that is used for establishing, configuring, testing, maintenance, and ending or terminating links for transmission of data frames.

link access procedure

• Are basically a data link layer protocols that are required for framing and transferring data across point-to-point links.

• It also includes some reliability service features

• Three types

  • Balanced

  • D-channel

  • Frame-Mode Bearer Services

• Originated from IBM SDLC, which is being submitted by IBM to the ISP simply for standardization

network control protocol

• An older protocol that was implemented by ARPANET.

• Basically allows users to have access to use computers and some of the devices at remote locations and also to transfer files among two or more computers.

• It is generally a set of protocols that is forming a part of PPP

• Always available for each and every higher-layer protocol that is supported by PPP.

• Replaced by TCP/IP in the 1980s

physical layer

• The foundation of connectivity

• Is the “basement” of the OSI model

• Doesn’t understand “files” or “webpages” - Only understands bits and the physics required to move them

three pillars of the physical layer

• Physical components: NICs, connectors (RJ-45, LC/ST), and cables

• Encoding: How we represent bits (e.g., electricity vs. light).

• Signaling: The actual method of sending the wave/pulse

throughput vs. goodput

• Advanced metric of quality of the physical layer

• While the Physical Layer handles Bandwidth (theoretical max), the user only cares about Goodput (the actual transfer rate of usable data after overhead).

physical representation of a bit

• Electrical (Copper): represented by voltage levels. For example, +5V might represent a 1 and 0V might represent a 0.

• Optical (Fiber): ): Bits are represented by light pulses. Presence of light (on) vs. absence of light (off), or specific wavelengths (colors).

• Wireless (RF): Bits are represented by shifts in frequency, amplitude, or phase of an electromagnetic wave.

modulation/line coding

To transmit a bit, the system must change a physical property of the transmission medium

networks that are using them

The data-link layer and the physical layer are the territory of the local and wide area networks. This means that when we discuss these two layers, we are talking about __________ ____ ___ ______ ____.

project 802

• In 1985, the Computer Society of the IEEE started a project to set standards to enable intercommunication among equipment from a variety of manufacturers

• This project does not seek to replace any part of the OSI model or TCP/IP protocol suite

  • It is a way of specifying functions of the physical layer and the data-link layer of major LAN protocols

• To achieve this, the IEEE divided the data link layer into two sublayers: upper and lower.

upper layer of data link

• Combination of flow control, error control, and part of the framing duties were collected into this sublayer

• Called logical link control

lower sublayer of data link layer

• Consists of media access control

• Called multiple access (MAC)

• MAC is for resolving access to shared media, if the channel is dedicated (point-to-point), we do not need this sublayer

logical layer control sublayer

Provides one single data link control for all IEEE LANs

media access control sublayer

• Created by IEEE project 802

• Defines the specific access method for each LAN

• In contrast to LLC, This sublayer contains a number of distinct modules

  • Each defines the access method and the framing format specific to the corresponding LAN protocol

  • Examples:

    • CSMA/CD for Ethernet LANs

    • Token passing method for Token Ring and Token Bus LANs

framing

________ is handled in both the LLC and MAC sublayer

ethernet evolution

1. Standard

2. Fast

3. Gigabit

4. 10 Gigabit

standard ethernet

• The original Ethernet technology

• Data rate of 10 Mbps

• Although most implementations have moved to other technologies in the ethernet evolution, there are some features of the this ethernet that have not changed during the evolution

characteristics of standard ethernet

• Connectionless and unreliable service

• Frame format:

• Frame length:

  • Minimum: 64 bytes (512 bits)

  • Maximum: 1518 bytes (12,144 bits)

fields of ethernet fram

• Preamble

• Start Frame Delimiter (SFD)

• Destination Address

• Source Address

• Type

• Data (46 - 1500 bytes)

• CRC (error detection information: CRC-32)

preamble

• Field of ethernet frame

• 7 bytes

• alternating 0s and 1s

• Used for synchronizing

start frame delimiter (SFD)

• Field of ethernet frame

• 10101011

• Indicates the start of the frame

• Last two bits (11) alerts that the next field is destination address

• Along with the preamble, it is added at the physical layer and not formally part of the frame

type field of ethernet frame

Define the upper-layer protocol using the MAC frame OR define the number of bytes in the data filed

ethernet addressing

• Each station on an Ethernet network has its own network interface card (NIC)

  • NIC fits inside the station and provides the station with a link-layer address

• Address Is 6 bytes (48 bits), normally written in hexadecimal notation, with a colon between the bytes

• Source address is always a unicast address

• Destination can be unicast, multicast, and broadcast

reason for complex encoding

• Self-Clocking: To prevent the receiver from "getting lost" during a long string of 0s.

• Noise Immunity: Making the signal distinct enough to survive interference.

• Efficiency: Sending more bits per second without increasing the frequency.

alphabet

signaling and encoding are known as the ________ of networking