Data And Computer Communications - Data Link Layer [1]

Data Link Layer

Data link layer has responsibility of transferring data (a frame) from one node to adjacent node over a link. Make sure the transition is error-free.

Make uses of physical layer to send a board of bits

• The data unit (packet) is a frame

Nodes and Links

Functions of Data Link Layer

• Framing
  • Packetization
• Flow Control
  • Avoid Data Loss at Recieving end (recieving buffer will not overflow)
• Error Control
  • Error Detection
  • Recover the Error
• Access Control
  • Medic access control (control use of channel, make sure only 1 user 1 time)
• Addressing

LLC and MAC Sublayers

Data Link Layer consist of 2 Sublayers:

• LLC (Logical Link Control)
  • Interoperability for different LANs
• MAC (Media access control)
  • Operation of the access methods

Error Detection

To see if any error has occurred.

• We are not even interested in the number of corrupted bits.
• A single-bit error is the same as a burst error.

Types of Errors

Single-Bit Error

Only 1 bit in the data unit has changed

• A single-bit error can occur in the presence of white noise.

Burst Error

2 or more bits in the data unit have changed

• Burst errors can be caused by impulse noise. The effects of burst errors are greater at higher data rate.

Error correction

• We need to know the exact number of bits that are corrupted
• We need to locate the error location in the message

Redundancy bits

• To detect or correct errors, redundant bits of data must be added

Block Coding

• Message is divided into $k$-bit blocks
  • Known as datawords
  • $2^k$ Datawords
• $r$ redundant bits are added
  • Blocks become $n=k+r$ bits
  • Known as codewords
  • $2^n$ Codewords

Dataword = Message

Codeword = Message and redundancy

Error Detection in Block Coding

• The receiver has (or can find) a list of valid codewords.
• If the original codeword has changed -> error

Hamming Distance

The Hamming Distance between two words is:

the number of differences between corresponding bits

e.g.

• d(01, 00) = 1
• d(010, 100) = 2

Minimum Hamming distance

• the smallest Hamming distance between all possible pairs of codewords in a codebook

e.g. 00000, 01011, 10101, 11110

• d(00000, 01011) = 3
• d(00000, 10101) = 3
• d(00000, 11110) = 4
• d(01011, 10101) = 4
• d(01011, 11110) = 4
• d(10101, 11110) = 3

Therefore the Minimum Hamming distance = 3

• Hamming pairwise distances means a table of all possible combination.

  e.g. 00000,10101,01010

	00000	10101	01010
00000	/	3	2
10101	3	/	2
01010	2	5	/

Hence, the minimum Hamming distance is 2.

To guarantee the detection of up to $s$-bit errors,

the minimum Hamming distance $d_{min}$ in a block code must be $s + 1$

Error Detection Methods

Single Parity check

Parity Check is based on addition.

Adding a single bit (Parity bit) to a block according to the two schemes:

• Even Parity
• Odd Parity

1. Both Receiver node and Sender node know the scheme they are using. (Even or Odd)
2. The sender node will send the data through transmission medium after adding a parity bit.
3. Receiver node will receieve the data, then count the bits and detect error
4. If no error found, parity bit is dropped and data is accepted by Receiver node

Even Parity

If Number of Block contain Odd number of 1s:

• Add a 1 behind to maintain the even number of 1s

Else

• Add a 0

Odd Parity

If Number of Block contain Odd number of 1s:

• Add a 0 behind to maintain the odd number of 1s

Else

• Add a 1

Problem of Single Parity check

• can only detect an odd number of errors
• can only detect all single-bit errors
• cannot detect burst errors
• If the total number of errors in each data unit is even, error cannot be detected (even parity check!)
  • e.g. 110111010 => 111101010 (bold = error, italic = parity bit)
• When the data block is badly garbled by a long burst error, the probability of detecting the error is 0.5 and therefore not acceptable

Cyclic redundancy check (CRC)

Cyclic redundancy check (CRC) is based on binary division.

Adding a sequence of redundant bits to the end of a data unit

so the resulting data unit becomes exactly divisible by a second predetermined binary number

CRC Generator

For Generator (Sender):

• Setup a long division of (Dataword + extra 0s)
  • The divisor in a cyclic code is normally called the generator polynomial or simply the generator
  • the number of extra 0s is equal to (number of bits of divisor -1)
• Then XOR operation and get the Remainder(CRC)
• Codeword = Dataword + Remainder(CRC)

Example of Generator:

CRC Checker

For Checker (Reciever)

• setup a long division of Codeword (or Errored Codeword)
  • use the same divisor
  • don’t add any extra 0s this time since we are decoding
• Then XOR operation and get the Remainder
• If Remainder = 0, Dataword can be accepted
  • It means No bit is corrupted
  • Some bits are corrupted, but the decoder failed to detect them
• Otherwise Dataword is discarded because error found
  • one or more bits is corrupted

Example of Checker:

XOR Table:

• Two bits the same , output = 0
• Two bits different , output = 1

Video Explaination

Polynomial Representation

• More common representation than binary form
• Easy to analyze
• Divisor is commonly called generator polynomial

Example

Standard Polynomials are:

• CRC-8, used in ATM header
• CRC-10, used in ATM AAL
• CRC-16, used in HDLC
• CRC-32, used in LANs

Strength of CRC

Strength of CRC can be analyzed using polynomial

$$M(x) \cdot x^{n}=Q(x) \cdot G(x)+R(x)$$

where

• $M(x)$ - Original message
• $G(x)$ - Generator polynomial of degree $n$
• $R(x)$ - Generated CRC

Transmitted message is

$$M(x) \cdot x^{n}-R(x)$$

which is divisible by $G(x)$

Received message is

$$M(x) \cdot x^{n}-R(x)+E(x)$$

where $E(x)$ is bit errors

If Receiver does not detect any error when $E(x)$ is divisible by $G(x)$,

it means either:

• No error $E(x) = 0$
• Undectectable error $E(x) \neq 0$

Checksum

Checksum = Check + sum

• Sender - checksum creation
• Reciever - checksum validation

Checksum creation

For sender

• Break message into into ‘k’ number of blocks with ‘n’ bits in each block
• Sum all the ‘k’ data blocks, add the carry to the sum if any
• Apply 1’s complement to the sum (invert all bits)
• You get the checksum

Checksum validation

For reciever

• Collect all the data blocks including the checksum
• sum all the data blocks and checksum
• Get the sum and apply 1’s complement to get the result
• if the result is 0, accept, otherwise discard

Actually if you see the sum is all 1s it means the result is 0 -> Accept

Video Explaination

Forward Error Correction

Once error is detected, correction can be handled through:

• Retransmission
  • The receiver asks the sender to retransmit the entire data unit (will be discussed)
• Forward Error Correction
  • The receiver can use an error-correcting code, which automatically corrects certain errors

Determine Numbers of Redundant bits

Consider only a single-bit error in k bits of data,

• Possibilities for an error: k
• Possibility for no error: 1
• Total No. of possibilities = k + 1

To Distinguish these possibilities, we need to add $r$ redundant bits:

$$2^r \geq k+r+1$$

Why k+r+1? Because we the r bits are also transmitted along with data.

Hamming Code

• Hamming Code is type of Error Correcting Code (ECC)
• Provides error detection and correction mechanism
• Adopt parity concept, but have more than one parity bit
• Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors

Hamming Code is widely used in computer memory (known as ECC memory)

To Generate a hamming code:

• All bits positions that are powers of 2 is our parity bits (i.e. 1,2,4,8,16) (count from rightmost)
• Parity bit 1: Check 1,3,5,7,9… (from 1, check 1 bit, skip 1 bit) count the numbers of 1s
  • If number of 1s = even, set that parity bit to 0
  • If number of 1s = odd, set that parity bit to 1
• Party bit 2: Check 2~3,6~7,10~11… (from 2, check 2 bit, skip 2 bit) count the numbers of 1s
  • If number of 1s = even, set that parity bit to 0
  • If number of 1s = odd, set that parity bit to 1
• Parity bit 4: Check 4~7, 12~15, 20~23… (from 4, check 4 bit, skip 4 bit) count the numbers of 1s
  • If number of 1s = even, set that parity bit to 0
  • If number of 1s = odd, set that parity bit to 1
• For Parity bit 8, 16, 32… same idea
• Parity bit 8, Parity 16

Quick way to determine a hamming code is correct or not:

• List the recieved message
• Locate the Parity bits, which is 2^n position counting from the rightmost
• Find the "1"s position of recieved message
• put all the position numbers of “1” into xor operation
• If the result is equal to parity bits, it is correct. Otherwise error

Video Explaination

Note we might counting from the right, so the rightmost is p1.

Depends on how we are going to create data word including parity bits

Burst Error Correction - Interleaving

Flow and Error Control

Flow Control

Protocol For noiseless channel

Flow control refers to a set of procedures used to:

• restrict the amount of data that the sender can send before waiting for acknowledgment.

• prevent buffer overflow (the sending entity does not overwhelm the receiving entity)

Flow Control is Influenced by:

• Transmission time
  • Time taken to emit all bits into medium
• Propagation time
  • Time for a bit to traverse the link

Stop and Wait Flow Control

• Source transmits frame
• Destination receives frame and replies with acknowledgement (ACK)
• The acknowledgement (ACK) require next frame
• Source waits for ACK before sending next frame
• Destination can stop flow by not sending ACK

• Frame transmission time = Data size/Data rate

  • The amount of time the channel transmits useful data bits

• Transmission time for 1 Cycle = 2 (propagration time) + frame transmission time

  • Also known as Total time examined

Link Utilization for Stop and Wait Flow Control

Also known as Normalized Throughput

Link Utilization is the fraction of time the channel is used to transmit useful data bits.

Link Utilization for Stop and Wait Flow Control:

$$U = \frac{\text{frame transmission time}}{\text{2 (propagration time) + frame transmission time}} = \frac{1}{1+ 2\frac{\text{(propagration time)}}{\text{frame transmission time}}}$$

Sliding Window Flow Control

• Allow multiple frames to be in transit
• Receiver has a buffer of storing $W$ frames
• Transmitter can send up to $W$ frames without ACK
• W is based on window size (1 Window = $W$ frames)
• Each frame is numbered, so it called sequence number
• ACK includes the sequence number of the next frame expected

Sender can send multiple frames before receiving the acknowledgement for the first frame.

Link Utilization for Sliding Window Flow Control

Consider a full duplex point-to-point line:

• The sender begins to transmit at time t = 0, then the ACK for the first frame reaches it at t = 2a+1. (Ignore the transmission time of the ACK frame)

全雙工通信（Full duplex Communication）是指在通信的任意時刻，線路上存在A到B和B到A的雙向信號傳輸。 全雙工通信允許數據同時在兩個方向上傳輸，又稱為雙向同時通信，即通信的雙方可以同時發送和接收數據。 … 這種方式要求通訊雙方均有發送器和接收器，同時，需要2根數據線傳送數據信號。

Link utilization for Sliding Window Flow Control:

$$U=\left\{\begin{array}{cc} 1 & W \geq 2 a+1 \\ \frac{W}{2 a+1} & W<2 a+1 \end{array}\right.$$

where

• $1 = \text{frame transmission time}$
• $a = \frac{\text{(propagration time)}}{\text{frame transmission time}}$

Video Explaination

Error Control

Protocol For noisy channel

The Detection and correction of errors contains the 2 situations:

• Lost frames: a frame fails to arrive at the other side
• Damaged frames: frame arrives but some of the bits are in error

Automatic Repeat Request (ARQ)

ARQ is a collective name for error control mechanisms.

ARQ turns an unreliable data link into a reliable one:

• Automatic retransmit the frame(s) if ACK doesn’t come back within a fixed period of time

The Different versions of ARQ are:

• Stop and Wait
• Go-Back-N
• Selective Repeat (Selective-Reject / Selective-Retransmission)

Stop and Wait ARQ

The sender(transmitter) transmits a single frame, must wait for ACK before sending next frame.

Note: The sender needs to maintain a copy of a transmitted frame until ACK is received.

There can be 2 types of error, Lost/damage of the frame or Lost/damage of the ACK.

For damaged frame, reciever will discard the frame and won’t send the ACK.

• Sender has a timer. If No ACK and timer timeout, retransmit the frame.

For damaged ACK, sender will not regonize it.

• Sender has a timer. If No ACK and timer timeout, retransmit the frame.
• Reciever will get 2 copies of frame (or even more than 2).
  • Then Reciever will discard the duplicated frame, because reciever is asking for a different frame

Why only Frame 0 and 1?

Because We only need to know whether the frame is duplicated or not. 0 and 1 is enough to classify.

The Timer of sender function like this:

• Sender start sending frame - start the timer
• Sender recieve ACK - stop the timer
• Sender timer timeout - Restart a time-out timer and start the timer again (also sender the frame)

If ACK is Delayed:

• Numbered acknowledgments are needed if an acknowledgment is delayed and the next frame is lost.

Piggybacking

The data in one direction is piggybacked with the acknowledgment in the other direction.

Detailed Example

Performance of Stop-and-Wait ARQ

$$\text { Utilization }=\frac{\text { Time for transmitter to emit a single frame }}{\text { Total time that line is engaged in the transmission of a single frame }}$$

For Error Free:

$$U = \frac{\text{frame transmission time}}{\text{2 (propagration time) + frame transmission time}} = \frac{1}{1+ 2\frac{\text{(propagration time)}}{\text{frame transmission time}}}$$

also known as

$$U = \frac{1}{1+2a}$$

If there is Error:

$$U=\frac{1}{N_{r}(1+2 a)}$$

Where

• $N_r$ is the expected number of transmissions of a frame

$$N_{r}=\mathrm{E}(\text { transmissions })=\sum_{i=1}^{\infty}\left(i \times P_{r}[i \text { transmissions }]\right) = \sum_{i=1}^{\infty}\left(i P^{i-1}(1-P)\right)=\frac{1}{1-P}$$

• $P$ is the probability that a single frame is in error.
• Assume that ACKs and NAKs are never in error, the probability the it will take exactly $i$ attempts to transmit a frame successfully is $P^{i-1}(1-P)$

Therefore The Utilization for Stop and Wait ARQ is:

$$U = \frac{1-P}{1+2a}$$

Disadvantages of Stop-and-Wait ARQ

• Only 1 frame at a time
• Not properly utilizing the entire bandwidth
  • lead to poor performance

Video Explaination

Go-Back-N ARQ

• Based on sliding window flow control

  • Sender sends up to W frames before worrying about acknowledgements
  • It keeps a copy of these frames
  • W is based on window size

• Sender can send multiple frames before receiving the acknowledgement for the first frame.

• If the ACK of a frame is not received within an agreed upon time period, all frames in the current window are transmitted.

Then what’s special?

• The size of the sending window determines the sequence numer of the outbound frames.
• Frames are number sequentially, useing $m$ bits to identify the sequence number of each frame
  • $m$ bits = $2^m$ frames
• N is the sender window size, which = $2^m$
• Reciever window size = 1
• Maximum Sender’s window size = $2^m - 1$

Why $2^m - 1$?

In Go-Back-N ARQ, the size of the send window must be less than 2m; the size of the receiver window is always 1.

Go-Back-N ARQ - Handling Error

If Damaged Frame (error in frame i so receiver discards frame i) :

• Receiver will either:
  • do nothing and wait until the sender times out
  • send a Reject(i) signal to the sender
• Then send will resend the frames starting from i

If Lost Frame (frame i is lost or out of sequence) :

• Reciever will either:
  • do nothing and wait until the sender times out
  • send a Reject(i) signal to the sender
• Then send will resend the frames starting from i

Sender Sliding Window

Reciever Sliding Window

Example

Performance of Go-Back-N ARQ

Selective Repeat ARQ

Also called selective retransmission or selective reject ARQ.

• Also Based on sliding window flow control
• More efficient: minimizes the amount of retransmission
• Receiver must maintain a large enough buffer
• More complex logic in transmitter to send a frame out of sequence

Then what’s special?

• Only resend the corrupted data
• Allow the receiver to keep track of the received frame
• Introduce a negative acknowledgment (NAK) that reports the sequence number of a damaged frame
• the size of the sender and receiver window must be at most one-half of $2^m$.

Sender Sliding Window

Reciever Sliding Window

Performance of Selective Repeat ARQ

Video Explaination

High-level data link control (HDLC)

HDLC supports both half-duplex and full-duplex communications over point-to-point and multipoint links.

全雙工通信（Full duplex Communication）是指在通信的任意時刻，線路上存在A到B和B到A的雙向信號傳輸。 全雙工通信允許數據同時在兩個方向上傳輸，又稱為雙向同時通信，即通信的雙方可以同時發送和接收數據。 … 這種方式要求通訊雙方均有發送器和接收器，同時，需要2根數據線傳送數據信號。

根據收發頻率的異同，單工通信可分為同頻通信和異頻通信。 半雙工通信（Half-duplex Communication）可以實現雙向的通信，但不能在兩個方向上同時進行，必須輪流交替地進行。 在這種工作方式下，發送端可以轉變為接收端；相應地，接收端也可以轉變為發送端。 但是在同一個時刻，信息只能在一個方向上傳輸。

HDLC has become the basis for most data link protocols used today including:

• Point-to-Point Protocol (PPP)
• Frame Relay
• Link Access Protocols (LAPs)
• Most LANs and MANs

HDLC Stations and Configurations

Station Types

Computers are the stations and mainly classified into Primary and Secondary.

• Primary Station
  • has complete control of the link and sends commands to secondary stations
• Secondary Station
  • receives commands and send response to primary station
• Combined Station
  • sends command and response

Config: Unbalanced (Master/Slave configuration)

• 1 Primary station
  • Order command to the Slaves (Secondary stations)
• More than 1 Secondary stations
  • Make Response to the Master (Primary Station)

Config: Balanced

• 2 Combined stations
  • Both can do Command or Response

HDLC Transfer Modes

The mode of communication describes who controls the link

• Normal Response Mode (NRM)
  • used with an unbalanced configuration
  • secondary device must have permission from the primary device before transmitting
• Asynchronous Balanced Mode (ABM)
  • used with an balanced configuration
  • only combined stations connected in point-to-point are used
  • no need permission before tramisttion

HDLC Frame Types

Information frames (I-frames)

• Used to transport user data
• control information relating to user data

Supervisory frames (S-frames)

• Serve as control purpose
• ACK frame

Unnumbered frames (U-frames)

• Reserved for system management

HDLC Frame Structures

All HDLC frame types share a similar basic structure.

Frame may contain up to six fields:

• Beginning Flag
• Address
• Control
• Information (absent in S-frames)
• Frame Check Sequence (FCS)
• Ending flag

Flag Field

A synchronization pattern for the receiver

The flag field is a fixed pattern. It is always 01111110.

• There is 1 flag at the beginning and 1 flag at the end of the frame.
• The ending flag of 1 frame can be used as the beginner flag of the next frame.

Example:

01111110[XXXXX]01111110

01111110[XXXXX]01111110[XXXXX]01111110[XXXXX]01111110

[XXXXX] means the other fields.

Problem of Flag field

Since 01111110 is reserved for flag field, what if data field of HDLC also contain 01111110?

• Receiver wrongly interprets the data
• Lack of data transparency

To solved this, Bit stuffing is introduced to guarantee the flag field sequence does not appear anywhere else in the frame.

Bit Stuffing

To Guarantee the flag field sequence does not appear anywhere else in the frame

How?

• Adding a extra 0 whenever 5 consecutive 1s in the data

• So Receiver does not misinterpret the data as flag

• Bit stuff is applied to the whole Frame content, not only data field

Bits are unstuffed after Frame recieved.

Address Field

Address Field is only used in unbalanced structure, used by Primary Station.

Address field contains the address of the secondary station that is either the originator or destination of the frame.

• The address field can be 1 byte (8bits) or more than 1 bytes.

Inside 1 byte of address field :

• 7 bits are used to idenify stations (128 stations)
• Last bit is 1

Large network requires multiple-byte address fields

so Address Field can be extended to multiple bytes

• For extended bytes: Only the last byte’s last bit is 1, Other bytes’ last bit is 0.

Control Field

The Control Field is Only 1 Byte.

It can be I-Frame, S-Frame or U-Frame, according to it’s First/ First two bits.

• I-Frame
  • First bit is 0
  • 3 bits used as N(S) field
    • Sequence number of the frame we are sending
    • Since only 3 bits to indicate sequence number, 2^3 is the maximum window size
      • sequence number is limited 0~7
  • 3 bits used as N® field
    • ACK number (Make use of Piggybacking, simply embed ACK into data)
  • 1 bit indicate Poll / Final
• S-Frame
  • First 2 bits is 10
  • Will not contain user data therefore no N(S) field
  • 2 bits are used to indicate different purpose
  • Can serve as ACK frame so there is N® field
  • 1 bit indicate Poll / Final
• U-Frame
  • First 2 bits is 11
  • 5 bits are used to indicate different purpose
  • 1 bit indicate Poll / Final

• I-frame contains both N(S) and N® fields
• S-frame contains an N® only
  • S-frames are used to return N® for flow control when the receiver does not have data to send
• U-frame has neither N(S) nor N® fields
  • U-frames are used for system management information, but not for user data exchange or acknowledgement

Poll / Final Bit

• Poll (or Select) Bit is sent by Primary Station, asking whether the secondary has anything to send
  • Known as Polling Operation
  • When used with Receive Ready(RR), It is Poll
  • When used with Recieve not ready(RNR), It is Select
• Final Bit is sent by Secondary Station, replying that there is nothing to send.
  • If there is something to send, Secondary station will just send the I-Frame.

Control Codes in S-Frame

S-frame is used for acknowledgement, flow control, and error control

In S frame, there are 2 bits served to indicate different purpose

• Recieve ready - device is ready to recieve data
• Recieve not ready - device is not ready to recieve data
• Reject - Negative ACK in ARQ (used in Go-Back-N ARQ)
• Selective-reject - Negative ACK (used in Selective-Repeat ARQ)

In Normal operations (Error free), we only use Recieve ready(RR) and Recieve not ready(RNR).

When It is RR (Receive Ready), the Operation can be:

• Poll – When transmitted by primary with P/F bit set, RR asks if it has anything to send
• Negative response to poll – RR tells primary that secondary is ready, but has nothing to send.
  • If there is something to send, Secondary station will just send the I-Frame.
• Positive response to select – When a secondary is able to receive a transmission from the primary

When It is RNR (Receive Not Ready), the Operation can be:

• ACK – RNR returned by a receiver to a sending station acknowledges receipt of all frames up to, but not including the frame indicated in the N® field
• Select – When a primary wishes to transmit data to a specific secondary, it alerts the secondary by sending an RNR frame with the P/F (used as P) set
• Negative response to select – When a selected secondary is unable to receive data, it returns an RNR

When It is REJ (Reject):

• The negative acknowledgement returned by a receiver in a go-back-n ARQ error correction system
• In an REJ frame, the N® field contains the number of the damaged frame

When It is SREJ (Selective-reject)

• The negative acknowledgement returned by a receiver in a selective- reject ARQ error correction system

Control Codes of U-Frame

U-frame is used to exchange session management and control information between connected devices

In U frame, there are 5 bits served to indicate different purpose

2^5 = 32 possible combinations

In general, U-frame control functions are of 5 types:

• Mode setting – set NRM, ARM or ABM modes
• Disconnection – negative acknowledgement of mode setting commands
• Unnumbered exchange – exchange of specific data such as date and time
• Initialization mode – initialize data link functions
• Miscellaneous – exchange of address, resetting of sequence numbers, etc

Information Field and Piggybacking

I-Frame use Information Field to store User Data

S-Frame does not have Information Field

U-frame may use Information Field to store management information

• contains user data (variable length) in I-frames
• contains network management data (if any) in U-frames

The main purpose of I-frames is to carry user data in the Information field, but they also use N(S) and N® fields to acknowledge receipt of frames

• The combination of data and acknowledgement in one single frame is called piggybacking

Frame check sequence (FCS)

Used for error dectection.

• 2 or 4-byte CRC

HDLC Operation

HDLC operations consists of：

* exchange of information
* supervisory
* unnumbered frames

It have three phases:

• Initialization
  • by either side, set mode & seq
  • Uses U-Frame
• data transfer
  • with flow and error control
  • using both I & S-frames (RR, RNR, REJ, SREJ)
• disconnect
  • when ready or fault noted
  • Uses U-Frame

Examples

• N(S) - Add 1 when Sender send an I-frame

  • Sequence number of the frame we are sending
  • Since only 3 bits to indicate sequence number, 2^3 is the maximum window size
  • sequence number is limited 0~7

• N® - Add 1 when Reciver send an I-frame

  • ACK number (Make use of Piggybacking, simply embed ACK into data)

>

Note In Example 5 there is a typo. the 3th frame (data frame2) is I,2,0.

Point-to-Point Protocol (PPP)

One of the most common protocols for point-to-point access.

• PPP Provides router to router and host-to-network
• Millions of Internet users who need to connect their home computers to the server of an Internet service provider use PPP.

The designers of PPP have included several services to make it suitable for a point- to-point protocol, but have ignored some traditional services to make it simple.

• Establishment of the link and the exchange of data

• Authentication (optional)

• Provide connections over multiple links (Multilink PPP)

• No flow control

• No error control (only error detection)

• No sequence numbering

PPP Framing

PPP uses a character-oriented (or byte-oriented) frame.

• Flag (1byte + 1byte): Frame starts and ends with a specific 1-byte paterrn of 01111110
• Address(1byte): A constant value and set to 11111111 (broadcast address)
• Control(1byte): A constant value and set to 00000011 (imitating unnumbered frames in HDLC)
• Protocol(1 or 2bytes): Define what is being carried in the data field (User Data / Other Info)
• FCS(2 or 4bytes): Frame Check Sequence is simply 2-byte or 4-byte CRC.
• Payload(and padding): The data field is a sequence of bytes with the default of a maximum of 1500 bytes; but this can be changed during negotiation.
  • padding is needed if the size is less than the maximum default value

Byte Stuffing is used. We add a Escape character (01111101) before the flag in the data field in indicate that is not a real flag. Just a data.

01111101 01111110

If the Data field contain Escape character, It will also be stuffed with another Escape character, to indicate it is a real Escape character.

01111101 01111101

PPP Transition Phases

A PPP connection goes through phases include:

• Establish (Link Setup)
• Authenticate (Access Control)
• Network (Network Control)

Although PPP is a link-layer protocol, it uses another set of protocols to establish the link, authenticate the parties involved, and carry the network-layer data.

Three sets of protocols are defined to make PPP powerful:

• the Link Control Protocol (LCP)
• two Authentication Protocols (APs)
• several Network Control Protocols (NCPs)

Known as PPP Multiplexing.

We need protocol field to indicate which protocol is using this data field.

PPP Architecture is basically Link Layer protocol but trying to link up to network layer.

Link Control Protocol (LCP)

LCP is responsible for establishing, maintaining, configuring, and terminating links.

• provides negotiation mechanisms to set options between the two end points.

Data format of LCP:

• ID field holds a value that matches a request with a reply.
• Length field defines the length of the entire packet.
• Information field contains information, such as options, needed for some LCP packets.

Options

Many options that can be negotiated between two end points.

Options are inserted in the information field of the configuration packets. In this case, the information field is divided into three fields: option type, option length, and option data.

Option include:

• Maximum receive unit (payload field size)
• Authentication protocol
• Prtocol field compression
• Address and control field compression

Authentication Protocols (AP)

PPP is designed for use over dial-up links where verification of user identity is necessary.

PPP has 2 protocols for authentication:

• Password Authentication Protocol (PAP)
• Challenge Handshake Authentication Protocol (CHAP)

Password Authentication Protocol (PAP)

Very Straight Forward. Only 2-way handshaking.

• The user who wants to access a system just send login information directly into server and a password
• Then the system will check the validity of the identification and password and either accepts or denies connection.

It is not secure. the password is a plain text.

Challenge Handshake Authentication Protocol (CHAP)

CHAP is a three-way handshaking authentication protocol that provides greater security than PAP.

• System send a challenge code to the user
• based on challenge code, user do some calucation then come up with a result
• the result will send back to the system
• System do the same calucation to check whether the result is correct and send by the reply.

People cannot derive your password through the challenge value, so it is more secure

Network Control Protocols (NCP)

PPP is a multiple-network-layer protocol that it can carry network- layer data packet from different network layer protocols defined by the Internet, OSI, Xerox, DECnet, AppleTalk, Novel and so on.

PPP has defined a specific Network Control Protocol for each network protocol:

• Internet Protocol Control Protocol (IPCP)
  • Most common to access to internet
• OSI Network Control Protocol
• Xerox NS IDP Control Protocol

Internet Protocol Control Protocol (IPCP)

2 way handshake. Request and then ACK.

After the network-layer configuration is completed by one of the NCP protocols, the user can exchange data packets from the network layer.

• IP datagram encapsulated in a PPP frame.

Example of PPP Transition

LCP(Setup) -> PAP or CHAP (Auth) -> IPCP(Network) -> LCP(Terminate)

All protocol use the same PPP frame to carry the data.