Transcript LGW2EChapter5Presentation3v2

Chapter 5
Peer-to-Peer Protocols
and Data Link Layer
PART II: Data Link Controls
Framing
Point-to-Point Protocol
High-Level Data Link Control
Data Link Controls
Main Purpose:
To enable the transfer of frames of information over the digital bit
or octet stream provided by the physical layer
A
Packets
Packets
Data link
layer
Data link
layer
Physical
layer
Frames
Physical
layer
B
Data Links Services
 Framing : To indicate the
boundaries that define frames
 Error control: To ensure reliable
transmission
 Flow control: To prevent the
transmitter from overflowing the
receiver buffer
 Multiplexing: To carry information
from multiple user
 Link Maintenance
 Security: Authentication &
Encryption
Data Link Controls
Packets
A



Data link
layer
Physical
layer
Packets
Frames
Data link
layer
Physical
layer
B
Examples
 PPP
 HDLC
 Ethernet LAN
 IEEE 802.11 (Wi Fi) LAN
Directly connected, wire-like
Losses & errors, but no out-of-sequence frames
Applications: Point-to-point communication lines;Direct Links; LANs;
Connections across WANs where frames follow the same path
Chapter 5
Peer-to-Peer Protocols
and Data Link Layer
Framing
What is Framing


Framing involves identifying the beginning and end
(boundaries) of a block of information within digital
stream
Encapsulating a network layer datagram into a bit
stream.

Add header, mark and detect frame boundaries, …
Framing
transmitted
frames
received
frames


Framing
0110110111
0111110101

Mapping stream of
physical layer bits into
frames
Mapping frames into
bit stream
Frame boundaries can
be determined using:




Character Counts
Control Characters
Flags
CRC Checks
Character-Oriented Framing
Data to be sent
A DLE B ETX DLE STX E
After stuffing and framing
DLE STX A DLE DLE B ETX DLE DLE STX E DLE ETX

Frames consist of integer number of bytes



Special 8-bit patterns used as control characters


Asynchronous transmission systems using ASCII to transmit printable
characters
Octets with HEX value <20 are nonprintable
STX (start of text) = 0x02; ETX (end of text) = 0x03;
Byte used to carry non-printable characters in frame




DLE (data link escape) = 0x10
DLE STX (DLE ETX) used to indicate beginning (end) of frame
Insert extra DLE in front of occurrence of DLE STX (DLE ETX) in frame
All DLEs occur in pairs except at frame boundaries
HDLC: Bit Stuffing Framing
HDLC frame
Flag Address Control
Information
FCS
Flag
any number of bits




Frame delineated by flag character
HDLC uses bit stuffing to prevent occurrence of flag
01111110 inside the frame
Transmitter inserts extra 0 after each consecutive
five 1s inside the frame
Receiver checks for five consecutive 1s



if next bit = 0, it is removed
if next two bits are 10, then flag is detected
If next two bits are 11, then frame has errors
Example: Bit stuffing & destuffing
(a)
Data to be sent
0110111111111100
After stuffing and framing
0111111001101111101111100001111110
(b)
Data received
01111110000111011111011111011001111110
After destuffing and deframing
*000111011111-11111-110*
PPP : Byte Stuffing Framing
Flag
Address
01111110 1111111
Control
00000011
Protocol
Information
CRC
Flag
01111110
integer # of bytes
All stations are to
accept the frame



Specifies what kind of packet is contained in the
payload, e.g., LCP, NCP, IP, OSI CLNP, IPX
PPP uses similar frame structure as HDLC, except


Unnumbered
frame
Protocol type field
Payload contains an integer number of bytes
PPP uses the same flag, but uses byte stuffing
Problems with PPP byte stuffing


Size of frame varies unpredictably due to byte insertion
Malicious users can inflate bandwidth by inserting 7D & 7E
PPP : Byte Stuffing Framing
PPP is character-oriented version of HDLC
 Flag is 0x7E (01111110)
 Control escape 0x7D (01111101)
 Any occurrence of flag or control escape inside of frame is
replaced with 0x7D followed by
original octet XORed with 0x20 (00100000)

Data to be sent
7E
41
41
7D
42
7E
50
70
46
7D
5D
42
7D
5E
50
70
After stuffing and framing
46
7E
Generic Framing Procedure (GFP)

Byte stuffing




Adds an extra byte to the signal that needs to be
transmitted
Results in unpredictable frame size
Provides opportunity for malicious users to inflate the
bandwidth consume by inserting flag patterns within a
frame
GFP  New standard for framing to overcome
shortcomings in PPP framing
Generic Framing Procedure (GFP)
GFP payload area
2
2
2
2
0-60
PLI
cHEC
Type
tHEC
GEH
Payload
length
indicator
Core
header
error
checking
Payload
type

GFP
payload
GFP combines frame length indication with CRC



GFP
Type
header extension
headers
error
checking
GFP payload
PLI indicated length of frame, then simply count characters
cHEC (CRC-16) protects against errors in count field (single-bit
error correction + error detection)
GFP designed to operate over octet-synchronous physical
layers (e.g. SONET)


Frame-mapped mode for variable-length payloads: Ethernet
Transparent mode carries fixed-length payload: storage devices
GFP Synchronization &
Scrambling

Synchronization in three-states
 Hunt state: examine 4-bytes to see if CRC ok



Pre-sync state: tentative PLI indicates next frame



If N successful frame detections, move to sync state
If no match, go to hunt state
Sync state: normal state




If no, move forward by one-byte
If yes, move to pre-sync state
Validate PLI/cHEC, extract payload, go to next frame
Use single-error correction
Go to hunt state if non-correctable error
Scrambling
 Payload is scrambled to prevent malicious users from inserting
long strings of 0s which cause SONET equipment to lose bit
clock synchronization
Chapter 5
Peer-to-Peer Protocols
and Data Link Layer
Point-to-Point Protocol
PPP: Point-to-Point Protocol

Data link protocol for point-to-point lines in Internet


Method to encapsulate IP packets over PPP links
Router-router; dial-up to router, PC to ISP using modem
1. Provides Framing and Error Detection

Character-oriented HDLC-like frame structure
2. Link Control Protocol


Bringing up, testing, bringing down lines; negotiating
options
Authentication: key capability in ISP access
3. A family of Network Control Protocols specific to
different network layer protocols

IP, OSI network layer, IPX (Novell), Appletalk
PPP Applications
PPP used in many point-to-point applications
 Telephone Modem Links
30 kbps
 Packet over SONET
600 Mbps to 10 Gbps


IP→PPP→SONET
PPP is also used over shared links such as
Ethernet to provide LCP, NCP, and
authentication features


PPP over Ethernet (RFC 2516)
Used over DSL
PPP Frame Format
Flag
01111110
Address
1111111
Control
00000011
1 or 2
variable
2 or 4
Protocol
Information
FCS
All stations are to
accept the frame
Flag
01111110
CRC 16 or
CRC 32
HDLC
Unnumbered frame
• PPP can support multiple network protocols simultaneously
• Specifies what kind of packet is contained in the payload
•e.g. LCP, NCP, IP, OSI CLNP, IPX...
PPP Example
PPP Phases
Home PC to Internet Service
Provider
Dead
7. Carrier
1. PC calls router via modem
dropped
2. PC and router exchange LCP
packets to negotiate PPP
Failed
parameters
Establish
Terminate
3. Check on identities
4. NCP packets exchanged to
2. Options
configure the network layer, e.g.
negotiated
6. Done
TCP/IP ( requires IP address
Failed
assignment)
Authenticate
5. Open
5. Data transport, e.g. send/receive
IP packets
6. NCP used to tear down the
network layer connection (free up
3. Authentication
IP address); LCP used to shut
4. NCP
completed
down data link layer connection
configuration Network
7. Modem hangs up
1. Carrier
detected
PPP Authentication

Password Authentication Protocol





Initiator must send ID & password
Authenticator replies with authentication success/fail
After several attempts, LCP closes link
Transmitted unencrypted, susceptible to eavesdropping
Challenge-Handshake Authentication Protocol
(CHAP)





Initiator & authenticator share a secret key
Authenticator sends a challenge (random # & ID)
Initiator computes cryptographic checksum of random # &
ID using the shared secret key
Authenticator also calculates cryptocgraphic checksum &
compares to response
Authenticator can reissue challenge during session
Example: PPP connection setup
in dialup modem to ISP
LCP
Setup
PAP
IP NCP
setup
Chapter 5
Peer-to-Peer Protocols
and Data Link Layer
High-Level Data Link Control
High-Level Data Link Control
(HDLC)



Bit-oriented data link control
Derived from IBM Synchronous Data Link
Control (SDLC)
Related to Link Access Procedure Balanced
(LAPB)


LAPD in ISDN
LAPM in cellular telephone signaling
Network
layer
NLPDU
Network
layer
“Packet”
DLSDU
DLSAP
DLSAP
Data link
layer
DLPDU
“Frame”
Physical
layer
DLSDU
Data link
layer
Physical
layer
HDLC Data Transfer Modes

Normal Response Mode (NRM)

Used in polling multidrop lines
Commands
Primary
Responses
Secondary

Secondary
Asynchronous Balanced Mode (ABM)

Used in full-duplex point-to-point links
Primary Commands
Secondary

Secondary
Responses
Responses Secondary
Commands
Primary
Mode is selected during connection establishment
HDLC Frame Format
Flag Address Control


Information
FCS
Flag
Control field gives HDLC its functionality
Codes in fields have specific meanings and uses


Flag: delineate frame boundaries
Address: identify secondary station (1 or more octets)




In ABM mode, a station can act as primary or secondary so
address changes accordingly
Control: purpose & functions of frame (1 or 2 octets)
Information: contains user data; length not standardized, but
implementations impose maximum
Frame Check Sequence: 16- or 32-bit CRC
Control Field Format
Information Frame
1
2-4
0
N(S)
5
6-8
P/F
N(R)
P/F
N(R)
Supervisory Frame
1
0
S
S
Unnumbered Frame
1



1
M
M
S: Supervisory Function Bits
N(R): Receive Sequence Number
N(S): Send Sequence Number
P/F


M
M
M
M: Unnumbered Function Bits
P/F: Poll/final bit used in interaction
between primary and secondary
Information frames


Each I-frame contains sequence number N(S)
Positive ACK piggybacked


3 or 7 bit sequence numbering


N(R)=Sequence number of next frame expected
acknowledges all frames up to and including N(R)-1
Maximum window sizes 7 or 127
Poll/Final Bit


NRM: Primary polls station by setting P=1; Secondary
sets F=1 in last I-frame in response
Primaries and secondaries always interact via paired P/F
bits
Supervisory frames
Used for error (ACK, NAK) and flow control (Don’t Send):
 Receive Ready (RR), SS=00


REJECT (REJ), SS=01


Negative ACK indicating N(R) is first frame not received
correctly. Transmitter must resend N(R) and later frames
Receive Not Ready (RNR), SS=10


ACKs frames up to N(R)-1 when piggyback not available
ACKs frame N(R)-1 & requests that no more I-frames be sent
Selective REJECT (SREJ), SS=11

Negative ACK for N(R) requesting that N(R) be selectively
retransmitted
Error Detection & Loss Recovery






Frames lost due to loss-of-synch or receiver buffer
overflow
Frames may undergo errors in transmission
CRCs detect errors and such frames are treated as
lost
Recovery through ACKs, timeouts & retransmission
Sequence numbering to identify out-of-sequence &
duplicate frames
HDLC provides for options that implement several
ARQ methods using the combination of information
and supervisory frame: Stop-and-Wait, Go-Back-N,
Selective Repeat
Unnumbered Frames

Setting of Modes:




Information Transfer between stations


UI: Unnumbered information
Recovery used when normal error/flow control fails



SABM: Set Asynchronous Balanced Mode
UA: acknowledges acceptance of mode setting commands
DISC: terminates logical link connectio
FRMR: frame with correct FCS but impossible semantics
RSET: indicates sending station is resetting sequence
numbers
XID: exchange station id and characteristics
Connection Establishment &
Release


Supervisory frames used to establish and release
data link connection
In HDLC



Set Asynchronous Balanced Mode (SABM)
Disconnect (DISC)
Unnumbered Acknowledgment (UA)
SABM
UA
Data
transfer
DISC
UA
Example: HDLC using NRM
(polling)Address of secondary
A polls B
N(R)
N(S) N(R)
X
A rejects fr1
B, SREJ, 1
A polls C
C, RR, 0, P
A polls B,
requests
selective
retrans. fr1
Secondaries B, C
Primary A
B, RR, 0, P
B, I, 0, 0
B, I, 1, 0
B, I, 2, 0,F
B sends 3 info
frames
C, RR, 0, F
C nothing to
send
B, I, 1, 0
B, I, 3, 0
B, I, 4, 0, F
B resends fr1
Then fr 3 & 4
B, SREJ, 1,P
A send info fr0
to B, ACKs up to 4
B, I, 0, 5
Time
Frame Exchange using
Asynchronous Balanced Mode
Combined Station B
Combined Station A
B, I, 0, 0
A, I, 0, 0
B, I, 1, 0
X
B sends 5
frames
B, I, 2, 1
A, I, 2, 1
B, I, 3, 2
B, REJ, 1
B, I, 4, 3
B goes
back to 1
A, I, 1, 1
A ACKs fr0
A rejects
fr1
A, I, 3, 1
B, I, 1, 3
B, I, 2, 4
B, I, 3, 4
B, RR, 2
A ACKs fr1
B, RR, 3
A ACKs fr2
Flow Control



Flow control is required to prevent transmitter from
overrunning receiver buffers
Receiver can control flow by delaying
acknowledgement messages
Receiver can also use supervisory frames to
explicitly control transmitter

Receive Not Ready (RNR) & Receive Ready (RR)
I3
I4
I5
RNR5
RR6
I6
TUTORIAL
Q1

Suppose that two peer-to-peer processes
provide a service that involves the transfer of
discrete messages. Suppose that the peer
processes are allowed to exchange PDUs that
have a maximum size of M bytes including H
bytes of header. Suppose that a PDU is not
allowed to carry information from more than one
message.
Q1
a)
Develop an approach that allows the peer
processes to exchange messages of arbitrary
size.
To exchange messages of arbitrary size, large
messages must be segmented into parts of MH bytes each in length to be transmitted in
multiple PDUs. Small messages must be
placed in a single PDU.
Q1
b) What essential control information needs to be
exchanged between the peer processes?
The peer processes need to communicate information
that allows for the reassembly of messages at the
receiver. For example, the first PDU may contain the
message length. The last PDU may contain and endof-message marker. Sequence numbers may also be
useful to detect loss in connection oriented networks
and to help in reconstruction of the messages in
connectionless networks. Lastly, since variable size
PDUs are permitted, the size of the PDU payload
must be transmitted in the PDU header.
Q2

In Stop-and-Wait ARQ why should the receiver
always send an acknowledgment message each
time it receives a frame with the wrong
sequence number?
The sender cannot send the next frame until it
has received the ACK for the last frame so, if the
receiver gets a frame with the wrong sequence it
has to be a retransmission of the previous frame
received. This means that the ACK was lost so
the receiver has to ACK again to indicate the
sender that it has received the frame.
Q







Consider the following questions for Stop-and-Wait ARQ:
(a) What does it mean when the receiver receives a
segment with the wrong sequence number?
The receiver receives a duplicate frame. The frame is
a retransmission, which means the previous ACK is
lost.
(b) What is the disadvantage of having a prematuretimeout?
Redundant retransmissions.
(c) What is the disadvantage of having too long of a
timeout interval?
Slow reaction to packet loss.
Q


Suppose that a receiver in its effort to control the
bursts from the transmitter it delays sending
ACKs until it has enough empty buffers. What is
a possible problem with such a strategy? How
can these problems be resolved?
Delaying the acknowledgements may be
interpreted as lost packet and/or congestions
thus it will trigger unwanted actions (e.g., packet
retransmissions) at the sending side. A possible
solution is to allow the receiver to explicitly tell
the transmitter how much data to send (e.g., use
a flow control window as in TCP).
Q3

Explain the differences between PPP and
HDLC.
HDLC can support various data transfer modes,
supports multipoint links and point to point links, and can
implement error control and flow control mechanisms.
PPP uses HDLC-like frames but does not use error
control and flow control protocols. Instead PPP supports
powerful link and network control PPP is character
based and can be implemented on any physical layer,
HDLC is bit based and can be implemented only on bit
synchronous physical layer
Q4
Suppose you are using a PC at home, which
is connected to the Internet using a modem
over a telephone communication link. The
modem can transfer data at a maximum rate
of 28,800 bits/sec.
a) How long would it take to download a file
(which is 1000000 bytes long) from a server
your PC is connected to?
Time = Amount of Data/Transfer Rate =
(1000000 * 8 bits) / 28800 bps = 278 seconds
= 4.63 minutes

Q4

Suppose that the answer to (a) is X
seconds and you transferred the same
sized files numerous times. You find that
the actual time to transfer always takes
longer than X seconds. Give a plausible
explanation for this.


Bit errors can occur on communication links
Retransmission of damaged frames must occur
and thus it takes longer than the theoretical
transmission time.
Q5

Name and describe two types of frame errors
that occur in the transmission of frames

Lost Frame -- A frame fails to arrive at the
receiver. A noise burst may damage a frame
to the extent that the receiver is not aware
that a frame has been transmitted.
Damaged Frame -- A recognizable frame
does arrive but some of the bits are in error.

Q6

Suppose a user has two browser applications active at
the same time, and suppose that the two applications
are accessing the same server to retrieve HTTP
documents at the same time. How does the server tell
the difference between the two applications?
A client application generates an ephemeral port number
for every TCP connection it sets up. An HTTP request
connection is uniquely specified by the five parameters:
(TCP, client IP address, ephemeral port #, server IP
address, 80). The two applications in the above
situations will have different ephemeral port #s and will
thus be distinguishable to the server.
Q7




Suppose a computer is moved from one
building to another within a campus. Does the
physical address need to change? Does the
IP address need to change? Does it make a
difference if the computer is a laptop?
The physical address does not change. It is
globally unique to the computer's NIC card.
The IP address may need to be changed to
reflect a new subnetwork id and host id.
The situation is the same for laptops.