FIT3165 / FIT4165 COMPUTER NETWORKS
WEEK 6 – DATA LINK LAYER
Faculty of Information Technology © 2022 Monash University
Copyright By PowCoder代写 加微信 powcoder
Data Link Layer
6.1 INTRODUCTION
6.2 DATA LINK CONTROL (DLC)
6.3 MULTIPLE ACCESS PROTOCOLS 6.4 LINK-LAYERADDRESSING
6.5 MID SEMESTER TEST (WEEK 7)
INTRODUCTION
Data link layer – Introduction
• The Internet is a combination of networks glued together by connecting devices (routers or switches).
• If a datagram is to travel from a host to another host, it needs to pass through these networks.
• The figure shows communication between Alice and Bob, using the same scenario we followed previously.
Figure: Communication at the data-link layer
Nodes and Links
Figure: Nodes and Links
• Although communication at the application, transport, and network layers is end-to-end;
• Communication at the data-link layer is node-to node.
• As we have learned in the previously, a data unit from one point in the Internet needs to pass through many networks (LANs and WANs) to reach another point.
• Theses LANs and WANs are connected by routers. It is customary to refer to the two end hosts and the routers as nodes and the networks in between as links.
Two Types of Links
• Although two nodes are physically connected by a transmission medium such as cable or air, we need to remember that the data-link layer controls how the medium is used.
• We can have a data-link layer that uses the whole capacity of the medium; we can also have a data-link layer that uses only part of the capacity of the link. In other words, we can have a point-to-point link or a broadcast link.
Two Sublayers
• To better understand the functionality and services provided by the link layer, we can divide the data-link layer into two sublayers:
• data link control (DLC) and media access control (MAC).
• The data link control (DLC) sublayer deals with all issues common
to both point-to-point and broadcast links;
• the media access control (MAC) sublayer deals only with issues specific to broadcast links.
Figure: Data-link layer divided as two sublayers
DATA LINK CONTROL (DLC)
Data Link Control (DLC)
The data link control deals with procedures for communication between two adjacent nodes in the network. It’s functions include:
■ framing – how to organize the bits that are carried by the physical layer.
■ flow and error control – Techniques for error detection are discussed at the end of this
■ Error detection and correction
• Data transmission in the physical layer means moving bits in the form of a signal from the source to the destination.
• The data-link layer, on the other hand, needs to pack bits into frames, so that each frame is distinguishable from another.
❑ Frame Size
❖ Character-Oriented Framing
❖ Bit-Oriented Framing
Figure: A frame in a bit-oriented protocol
Figure: Bit stuffing and unstuffing
Figure: A frame in a character-oriented protocol
Figure: Byte stuffing and unstuffing
Flow and Error Control
Error Detection and Correction
❑ Error Control
• At the data-link layer, if a frame is corrupted between the two nodes, it needs to be corrected
before it continues its journey to other nodes.
• However, most link-layer protocols simply discard the frame and let the upper-layer protocols handle the retransmission of the frame.
• Some wireless protocols, however, try to correct the corrupted frame.
Flow Control
We covered flow and error control in Transport Layer TCP protocol in Lecture-3.
One of the responsibilities of the data-link control sublayer is flow and error control at the data-link
Error Detection and Correction
Introduction
❖ Types of Errors
❖ Redundancy
❖ Detection versus Correction
Block Coding
Cyclic Codes
❖ Cyclic Redundancy Check
❖ Polynomials
❖ Requirement
❖ Performance
❖ Advantages of Cyclic Codes
❖ Error Detection
❖ Hamming Distance
❖ Minimum Hamming Distance for
Error Detection
Linear Block Codes
❖ Parity-Check Code
❑ Checksum
❖ Internet Checksum
❖ Algorithm
❖ Other Approaches to the
Types of errors and Block coding
Figure: Bit Errors – Single-bit and burst error
Example – Block coding
Let us assume that
DATAWORD = k bits =2;
CODEWORD = n bits = 3
Table shows the list of datawords and codewords.
we will see how to derive a codeword from a dataword.
Table: A code for error detection
Figure: Process of error detection in block coding
Example – Hamming distance
Hamming Distance: The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
•In other words, it measures the minimum number of substitutions required to change one string into the other, or
•The minimum number of errors that could have transformed one string into the other.
Figure: Geometric concept explaining dmin in error detection
• The minimum Hamming distance for our first code scheme (Table 5.1) is dmin=2.
• This code guarantees detection of only a single error.
• For example, if the third codeword (101) is sent and one error occurs, the received
codeword does not match any valid codeword.
• If two errors occur, however, the received codeword may match a valid codeword and
the errors are not detected.
• (dmin= d = s + 1 or s= 1).
Example 2 Example 3
• A code scheme has a Hamming distance dmin = 4.
• This code guarantees the detection of up to three errors
• (dmin= d = s + 1 or s= 3).
• The code in Table 5.1 is a linear block code because the result of XORing any codeword with any other codeword is a valid codeword.
• For example, the XORing of the second and third codewords creates the fourth one.
• In our first code (Table 5.1), the numbers of 1s in the nonzero codewords are 2, 2, and 2. So the minimum Hamming distance is dmin = 2.
Example – Parity check
Table: Simple EVEN parity-check code C(5, 4)
Figure: Encoder and decoder for simple EVEN parity-check code
Example – Parity check
Let us look at some transmission scenarios. Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases of EVEN parity:
• Both even parity and odd parity can only detect odd number of inversions in the dataword.
• It cannot detect even number of inversions in the dataword.
Example – Cyclic Redundancy Check (CRC)
The cyclic redundancy check (CRC) is a technique used to detect errors in digital data. CRC is a hash function that detects accidental changes to raw computer data commonly used in digital telecommunications networks and storage devices such as hard disk drives. This technique was invented by W. .
Table: A Cyclic Redundancy Check (CRC) code with C(codeword=7, Dataword=4)
Figure: CRC encoder and decoder
Division in CRC encoder
Figure: Division in CRC encoder
Division in CRC encoder – corrupted or not
Figure: Division in CRC encoder
Division in CRC decoder – corrupted or not
Figure: Division in the CRC decoder for two cases
CRC Standard polynomials
Designing polynomials
❑ The selection of the generator polynomial is the most important part of implementing the CRC algorithm.
❑ The polynomial must be chosen to maximize the error-detecting capabilities while minimizing overall
collision probabilities.
❑ The most important attribute of the polynomial is its length (largest degree(exponent) +1 of any one term in the polynomial), because of its direct influence on the length of the computed check value.
The most commonly used polynomial lengths are:
✔ 9 bits (CRC-8)
✔ 17 bits (CRC-16)
✔ 33 bits (CRC-32)
✔ 65 bits (CRC-64)
Basic Concept
• Suppose the message is a list of five 4-bit numbers that we want to send to a destination.
• In addition to sending these numbers, we send the sum of the numbers.
• For example, if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12, 0, 6, 36), where 36 is the sum
of the original numbers.
• Receiver adds the five numbers and compares the result with the sum.
• If the two are the same, the receiver assumes no error, accepts the five numbers, and discards the
sum. Otherwise, there is an error somewhere and the message not accepted.
Checksum – Example (1)
In the previous example, the decimal number 36 in binary is (100100)2. To change it to a 4-bit number we simply add the extra leftmost 2-bit to the right 4-bits as shown below, to get the 4-bit code.
● Instead of sending 36 as the sum, we can send 6 as the sum (7, 11, 12, 0, 6, 6).
● The receiver can add the first five numbers in one’s complement arithmetic.
● If the result is 6. the numbers are accepted otherwise, they are rejected.
● The sender adds all five numbers to get the sum 6.
● The sender then complements the result to get the checksum 9, which
● Note that 6 = (0110)2 and 9 = (1001)2 ; they are complements of
each other.
● The sender sends the five data numbers and the checksum (7, 11, 12,
● If there is no corruption in transmission, the receiver receives (7, 11,
12, 0, 6, 9) and adds them in one’s complement to get 15
(7 + 11 +12 +0 +6 = Sum =36 = 10 01002 )
0110 =6 10
6 Wrapped Sum Complement of 0110 = 1001 =9
CHECKSUM=9
Checksum – Example (2)
Procedure to calculate the traditional checksum
IEEE 802.3 Frame Format
Preamble: 7-octet pattern of alternating 0s and 1s used for bit synchronization.
Start Frame Delimiter (SFD) is a sequence 10101011, locates the start of the frame
Destination and Source MAC / Physical 48 bit address
Frame Check Sequence
i.e. CRC of data from DA to Pad
Data Link Sublayers
SUB-1 LOGICAL LINK CONTROL (LLC)
✔Frames the network layer packet ✔Identifies the network layer protocol ✔Provides flow control
✔Provides error control
✔Link management
SUB-2 MEDIA ACCESS CONTROL (MAC )
✔Frame addressing (synchronisation) ✔Marks the beginning and ending of the frame
The frame is encoded into a signal
as BITS (physical layer 1)
Flow control
• Ensure sending entity does not overwhelm receiving entity
– by preventing buffer overflow
• Influenced by:
– transmission time
> time taken to emit all bits of a frame onto the medium
– propagation time
> time for a bit to traverse the link between source and destination.
• Assume here no errors but different delays
– Point-to-Point links – fixed
– Circuit switched, ATM networks – variable
Flow control – Stop and Wait
1. source transmits frame
2. destination receives frame and replies with acknowledgement (ACK)
3. source waits for ACK before sending next frame
4. destination can stop the flow by not sending ACK
5. works well for a few large frames
6. Stop and wait becomes inadequate if large block of data is split into small frames
Destination
Flow control – Sliding Windows
• Allows multiple numbered frames to be in transit
• Receiver should have buffer space for W frames
• Transmitter sends up to W frames without ACK
• ACK includes number of next frame expected
• Sequence number is bounded by size of field (k)
– frames are numbered modulo 2k
– giving max window size W of up to 2k – 1
• Receiver can stop further transmission with ACK
(Receive Not Ready)
• To resume it must send a normal acknowledge to resume
• For full-duplex link, ACK’s can piggyback on frames
Flow control – Sliding Windows – Example
RR4 (receive ready for frame 4)
Error Control
• Detection and correction of errors such as:
– lost frames
– damaged frames
• Common techniques for error control is by using:
– errordetection
– positive acknowledgment
– retransmission after timeout
– negative acknowledgement & retransmission
Automatic Repeat Request (ARQ)
• Collective names for such error control mechanisms are referred to as ARQ:
• The effect of ARQ is to convert
unreliable data link 🡪 into an reliable one
• Three versions of ARQ methods:
– Stop-and-wait ARQ
– Go-back-N ARQ
– Selective-rejectARQ(selective retransmission)
Error Control – Stop and Wait
Sender Receiver
Sender Receiver
Sender Receiver
• Example with both types of errors
• Pros and cons
– inefficient
Timeout Timeout
Timeout Timeout
Error Control – Go Back N
• Based on sliding window
• If no error, ACK as usual
• Use window to control number of outstanding frames
• If error in frame-N, reply with rejection REJ (-ve ACK)
– discard that frame and all future frames until error frame received correctly
– transmitter must go back to N and retransmit that frame and all subsequent frames
• The go-back-N technique accounts for:
✔ Damaged frame. ✔ Lost Frame
✔ DamagedACK ✔ Damaged Reject
Error Control – Selective Reject (SREJ)
• Also called selective retransmission
• Only rejected frames are retransmitted
• Subsequent frames are accepted by the receiver and buffered
• Minimizes retransmission
• Receiver must maintain large enough buffer
• More complex logic in transmitter
• Hence less widely used
• Useful for satellite links with long propagation delays
GBN Vs SREJ
Two Data Link Control (DLC) Protocols
● After finishing all issues related to the DLC sublayer, we discuss two DLC protocols that actually implemented those concepts.
● The first, Logical Link Control (LLC) is the base of many protocols that have been designed for LANs.
● The second, Point-to-Point (PPP), is a protocol derived from High Level Data Link Control (HDLC) and is used for point-to-point links.
● Need layer of logic above Physical
● To manage exchange of data over a link
Configuration and Transfer Modes
○ • frame synchronization
○ • flow control
○ • error control
○ • frame addressing
○ • control and data on same link
○ • link management
Transfer Phases
Multiplexing
Multilink PPP
High Level Data Link Control (HDLC)
• An important data link control protocol, specified as ISO 3009, ISO 4335
• Station 3 types:
– Primary – controls operation of link ( One-Pri, many-Secondary)- commands
– Secondary – under control of primary station – responses
– Combined – combined stations issues commands and responses
• Link configurations 2 types:
– Unbalanced – 1 primary, multiple secondary (unbalanced because primary controls secondary stations) (support – full and half duplex)
– Balanced – 2 combined stations(primary & Secondary) (support – full and half duplex)
• Data transfer modes 3 types:
– Normal Response Mode (NRM)
– Asynchronous Balanced Mode (ABM) – most widely used!
– Asynchronous Response Mode (ARM)
HDLC Transfer Modes
• Normal Response Mode (NRM)
– Unbalanced config, primary initiates transfer
– Secondary sends only when permitted by
– No communication between secondaries
– Typically used in multipoint lines, e.g. host + terminals
• Asynchronous Balanced Mode (ABM)
– balanced config, either station initiates transmission, has no polling overhead, Most widely used, requires combined stations, Best mode for point-to-point lines.
• Asynchronous Response Mode (ARM)
– unbalanced config, secondary may initiate and transmit without permission from primary, rarely used
– Primary is responsibility for the line, initialization, error recovery, and logical disconnection
HDLC Frame Structure
• Synchronous transmission of frames
• Single frame format used for both data and control exchange
Abort Idle
Aborted HDLC Frame
Flag Fields and Bit Stuffing
• Delimit frame at both ends with 01111110
• Receiver hunts for flag sequence to synchronize
• Bit stuffing used to avoid confusion with data containing flag sequence 01111110
0 inserted after every sequence of five 1s
if receiver detects five 1s it checks next bit
if next bit is 0, it is deleted (was stuffed bit)
if next bit is 1 and seventh bit is 0, accept it as flag sequence
if sixth and seventh bits 1, sender is indicating abort
HDLC Address Field
• Identifies the secondary station if it transmitted or is to receive the frame
• Usually 8 bits long
• May be extended to multiples of 7 bits
– Leftmost Bit of each octet is (1) or (0) – Tx or Rx
– The remaining 7 bits of each octet form the address.
• All “ones” address 11111111 is broadcast
HDLC – Control Field (8 bits)
• Different for different frame type
– I: Information – carry data to be transmitted for the user (next layer up)
> Additionally – Flow and error control with ARQ with piggybacked on information frames
– S: Supervisory – ARQ when piggyback is not used
– U: Unnumbered – provides supplementary link control functions
• Starting 1-2 bits of control field identify frame type
HDLC – Control Field (16 bits)
• Use of Poll (P) / Final (F) bit depends on context
– in command frame it is referred as Poll – P bit, set to1 to solicit (poll)
response from peer
– in response frame it is referred as F bit set to 1 to indicate response to soliciting command
• Sequence number usually 3 bits
– can extend to 7 bits as shown below
HDLC – Information and FCS fields
• Information Field
– The information field is present only in Information I-frames and some Unnumbered U-frames
– Must contain integral number of octets
– Variable length
• Frame Check Sequence Field (FCS)
– Used for error detection
– Used for line reliability
– Used and depends on line quality and reliability
– Either 16 bit CRC or 32 bit CRC used for FCS
HDLC Operation
• Consists of exchange of:
Information (I-Frame) Supervisory (S-Frame) and Unnumbered (U-Frame)
Has three phases
– Firstinitialization
– Second data transfer
by either side, set mode (NRM, ABM, or ARM) & sequence of 3-bit or 7-bit agreed
Logical connection is established.
▪ with flow and error control
▪ using both I & S-frames (RR, RNR, REJ, SREJ)
▪ (RR) RecieveReady, (RNR) RecieveNotReady,
▪ (REJ) Reject, and (SREJ) SelectiveReject
▪ Frames with sequence # of modulo 8 (3-bit) or modulo-128 (7-bit)
– Thirddisconnect
▪ when ready to disconnect or connection fault noted
MULTIPLE ACCESS PROTOCOLS
Taxonomy of Multiple Access Protocols
❖ Pure ALOHA
❖ Slotted ALOHA
❖ Vulnerable Time
❖ Persistence Methods
❖ Minimum Frame Size
❖ Procedure
❖ Energy Level
❖ Throughput
❖ Traditional Ethernet
Random Access
• In random-access or contention methods, no station is superior to another station and none is assigned the control over another.
• At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.
• This decision depends on the state of the medium (idle or busy).
• In other words, each station can transmit when it desires on the condition that it follows the predefined procedure, including the testing of the state of the medium.
Procedure for pure ALOHA protocol
Kmax = Maximum number of retransmission
ALOHA (Back off time) – Example
The stations on a wireless ALOHA network are a maximum of 600 meters apart. If we assume that signals propagate at a speed of 3 × 108 m/s, find the back-off time.
• We can find Max propagation time = = distance/signal speed
Tp = (600) / (3 × 108) = 2 𝜇s.
• For K = 2, the range of random number = R={0
• Back-off time= TB = R x Tp = { 0, 2, 4, 6} 𝜇s.
This means that TB can be 0, 2, 4, or 6 𝜇s, based on the outcome of the ra
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com