DATA COMMUNICATIONS AND
NETWORKING
ผศ.ดร.ณัฐกานต์ พุทธรักษ์
Lecture 5
ภาคการศึกษาที่ 1 ปี การศึกษา 2562
พุธ: 8.45 – 12.00น. and 13.00 – 16.15น.
@E12-403
1
LAST CLASS
Switching Networks
Circuit Switching
Packet Switching
Structure of Switch
LAN Technologies
2
TODAY’S OUTLINE
Data Link Layer (Cont’d)
การตรวจสอบและแก้ไขความผิดพลาด (Error
detection and Correction)
Network Layer
IP, ICMP, ARP
3
ERROR DETECTION AND CORRECTION
Error detection and correction are
implemented either at the Data link layer or
the Transport layer at the OSI model
During the transmission of data, a bit 0 might
changed to 1 or 1 to 0 due to unpredictable
interference from heat, magnetism and other
form of electricity.
TYPES OF ERRORS
Single-Bit error
Multiple-Bit error
Burst Error
5
ERROR DETECTION
How do we know that there is an error?
- Comparison between the transmitted data
and the received one, if we have a copy of
the original data, and see if they are the
same or not?
- Whether the decoded data make sense or
not?
6
REDUNDANCY
Mechanism used for error detection
Send every data unit twice
Bit-for-Bit comparison between the two
version of the data is done by the receiving
device
Disadvantage: very slow
7
Instead of repeating the entire data stream, a
shorter group of bits may be appended to the
end of each unit called (extra bits) and used for
detecting errors at the destination.
The receiver examine the entire data
stream through a checking function.
These extra bits are discarded as soon as
the accuracy of the transmission has been
determined (data stream passes the
checking criteria)
8
Redundancy
9
DETECTION METHODS
1. Vertical redundancy Check (VRC)
2. Longitudinal Redundancy Check (LRC)
3. Cyclic Redundancy Check (CRC)
4. Checksum
10
VERTICAL REDUNDANCY CHECK (VRC)
Called a parity check
The most common and least expensive mechanism used
for error detection
A parity bit is appended to every data unit,
So number of 1s in the unit becomes even, including the
parity bit (even parity)
Even parity generator is used to determine whether the
parity bit (0 or 1)
11
VRC
The receiver checks the received
bits through an even-parity
checking function and determine
whether the received data is
accepted or not
VRC detects all Single-bit errors
VRC detects Burst errors, if the total
number of errors in each unit is odd
Odd-parity could be also used
12
EXAMPLE: GIVEN THE FOLLOWING WORD TO BE TRANSMITTED:
1110111 1101111 1110010 1101100 1100100
Adds the parity bit as follows
11101110 11011110 11100100 11011000 11001001
The number of 1’s in the receiver side (6, 6, 4, 4, 4) so the data will
be accepted
If the receiving data as follows:
11111110 11011110 11101100 11011000 11001001
The number of 1’s in the receiver side (7, 6, 5, 4, 4) so the data will
be rejected
13
LONGITUDINAL REDUNDANCY CHECK
(LRC)
A block of bits is organized in a table
A block of bits is divided into rows
Calculate the parity bit of each column
Create new row of bits that represents the
parity bit of all columns
14
LRC PERFORMANCE
LRC detects burst errors
Fail, if two bits in one data unit are damaged and two
bits in exactly the same position in another data unit
are also damaged
15
EXAMPLE: SUPPOSE THE FOLLOWING BLOCK IS SENT:
10101001 00111001 11011101 11100111 10101010
(LRC)
The received bits are:
10100011 10001001 11011101 11100111 10101010
(LRC)
The whole block is discarded (no matching bits are shown in
blue)
10100011 10001001 11011101 11100111 10101010
(LRC)
16
PROBLEM
Consider two data units.
11110000
11000011
00110011 LRC
If the first and the last bits in each of them are
changed, making the data unites,
01110001
01000010
00110011 LRC
The error can not be detected by LRC. 17
VRC and LRC (2-Dimensional Parity)
18
ตัวอย่าง: บิตข้อมูลจํานวน 25 บิตนี้ ถูกเข้ารหัสด้วยรหัส LRC และ
VRC แบบ odd parity ซึ่งมีความผิดพลาดอยู่ 1 บิต จงคํานวณว่าบิต
ที่ผิดพลาด (error) อยูท่ ี่ตาํ แหน่ งใด?
00100 00111 11001 11011 11010
19
CYCLIC REDUNDANCY CHECK (CRC)
A predetermined divisor of n+1 bits
A string of n 0s is appended to the data unit
Based on Binary division
Divides the data with the appended 0s by the
divisor using binary division
The remainder is called CRC (n-bits), and will
replaced the n 0s.
20
The data unit with the appended CRC (remainder) is
send to the receiver
The receiver divides the received data by the same
divisor.
If the remainder is zero then the data is passed (no
errors)
Otherwise an error occurs
21
CRC encoder and decoder
22
POLYNOMIALS
CRC generator (divisor) is represented by an
algebraic polynomial
The polynomial should not divisible by x and
should be divisible by (x + 1)
Standard polynomials are: CRC-12, CRC-
16, CRC-ITU-T, CRC-32
23
Polynomial and Divisor
24
Standard Polynomials
25
A polynomial to represent a binary word
26
CRC division using polynomials
1.27
Division in CRC encoder
28
Division in the CRC decoder for two cases
29
CRC PERFORMANCE
CRC detects all Burst errors that affect an
odd number of bits
CRC detects all Burst errors of length less
than or equal to the degree of the
polynomial
CRC detects all Burst errors of length
greater than the degree of the polynomial
with a very high probability
30
CHECKSUM
Divides the data unit into k sections each of n-bits
Add all sections together using one’s complement
Complement the sum and call it checksum
The checksum is sent with the data
The receiver divides the data into k sections
each of n-bits
Add them with the checksum, complement the
sum
If it is zero then the data is accepted;
otherwise rejected 31
Checksum
32
EXAMPLE
The following data is to be send using a checksum
of 8 bits (10101001 00111001)
Add them using one’s complement
10101001
00111001
sum 11100010
Checksum 00011101 10101001 00111001 00011101
33
The sent data 10101001 00111001
00011101
10101001
00111001
00011101
sum 11111111
Complement 00000000 (the data is accepted)
34
If the received data is
10101111 11111001 00011101
10101111
11111001
00011101
result 1 11000101
carry 1
sum 11000110
Complement 00111001 (the data is corrupted)
35
ERROR CORRECTION
Can be handled in two ways:
1. The receiver asks the sender to retransmit the entire
data unit.
2. The receiver can use error correcting code to correct
the errors.
Error-correcting codes are more sophisticated than
error-detection codes
Error-correcting codes require more redundancy bits to
correct the errors
Most error-correcting codes are limited to correct one,
two, or three-bit errors 36
SINGLE-BIT ERROR CORRECTION
A bit has two states (0 and 1)
These two states are enough to detect an
error but not to correct it
The problem is how to locate the position of
the invalid bit or bits.
Number of redundancy bits are added to
the data unit for error correction
37
Block Coding
38
DATA AND REDUNDANCY BITS
If m represent the number of bits in the data units, then r which
represents the number of redundancy bits can be determined
according to the following equation:
2r >= m + r + 1
For example if m = 7 then r = 4 according to the
Equation 24 >=7 + 4 + 1
Note: m+r =n
39
PROCESS OF ERROR DETECTION IN BLOCK CODING
40
HAMMING CODE
Number of redundancy bits (according to the number of
bits in the data units) are added to the data units.
These bits are placed in position 1, 2, 4, 8 ... That are
powers of 2
For example, for 7 bits data unit, the hamming code will
be:
42
The r bit in each position is the VRC bit for one
combination of data bits
The combinations used to calculate each of the four r
values for a 7 bit data unit are as follows:
r1 : bits 1, 3, 5, 7, 9, 11
r2 : bits 2, 3, 6, 7, 10, 11
r4 : bits 4, 5, 6, 7
r8 : bits 8, 9, 10, 11
Each data bit may be included in more than one
VRC calculation
r bits are included in only one
43
r bits are calculated as follows:
r1 bit is calculated using all bit positions whose
binary representation includes a 1 in the
rightmost position
r2 bit is calculated using all bit positions with a
1 in the second position, and so on
44
Hamming Code
45
Hamming Code
46
CALCULATING THE R VALUES
Calculate the even parities for the various bit
combinations.
The parity value for each combination is the
value of the corresponding r bit.
For example:
The value of r1 is calculated to provide even
parity with bits 3, 6, 7, 10, and 11
47
Example of Hamming Code
Direction
48
ERROR DETECTION AND CORRECTION
Assume that bit number 7 has been changed from 1
to 0
The receiver recalculates four new VRCs using the
same sets of bit used by the sender plus the relevant
parity (r) bit for each set
Assembles the new parity values into a binary
number in order of the r positions
The new binary number represent the location of the
bit in error
The receiver can revise its value and correct the error
49
Single-bit error
50
Error
Detection
51
EXAMPLE
A byte of data: 10011010, How can we encode this
data with Hamming code? (First bit is 1)
52
NETWORK LAYER
Responsibilities and Services
Packetizing
Routing and Forwarding
Packet Switching
IP address
53
NETWORK LAYER PROTOCOL
Position of IP and other network-layer protocols in TCP/IP
protocol suite
54
IP DATAGRAM
55
Multiplexing and demultiplexing using the value of the protocol field
56
ICMPv4
58
Contents of data field for the error messages
59
DEBUGGING TOOLS
Ping
traceroute
60
PING
61
TRACEROUTE
62
ARP
Address mapping => Static
=> Dynamic
63
ARP OPERATION
64
FOUR CASES USING ARP
65
HUBS
physical-layer (“dumb”) repeaters:
bits coming in one link go out all other links at same rate
all nodes connected to hub can collide with one another
no frame buffering
no CSMA/CD at hub: host NICs detect collisions
twisted pair
hub
66
SWITCH
link-layer device: smarter than hubs, take active
role
store, forward Ethernet frames
examine incoming frame’s MAC address, selectively
forward frame to one-or-more outgoing links when
frame is to be forwarded on segment, uses CSMA/CD
to access segment
transparent
hosts are unaware of presence of switches
plug-and-play, self-learning
switches do not need to be configured
67
SWITCH: ALLOWS M U LT IP LE SIMULTANEOUS
TRANSMISSIONS
A
hosts have dedicated, direct C’ B
connection to switch
1 2
switches buffer packets 6 3
5 4
Ethernet protocol used on each
incoming link, but no collisions; C
full duplex
B’ A’
each link is its own collision domain
switch with six interfaces
switching: A-to-A’ and B-to-B’ (1,2,3,4,5,6)
simultaneously, without collisions
not possible with dumb hub
68
SWITCH TABLE
A
Q: how does switch know that A’ C’ B
reachable via interface 4, B’
reachable via interface 5? 1 2
6 3
A: each switch has a switch 5 4
table, each entry: C
(MAC address of host, interface to
reach host, time stamp) B’ A’
looks like a routing table! switch with six interfaces
(1,2,3,4,5,6)
Q: how are entries created,
maintained in switch table?
something like a routing protocol? 69
Source: A
Dest: A’
SWITCH: SELF-LEARNING A A A’
C’ B
switch learns which hosts can
be reached through which 1 2
6 3
interfaces
5 4
when frame received, switch
“learns” location of sender: C
incoming LAN segment
records sender/location pair in B’ A’
switch table
MAC addr interface TTL
A 1 60 Switch table
(initially empty)
70
SWITCH: FRAME FILTERING/FORWARDING
When frame received:
1. record link associated with sending host
2. index switch table using MAC dest address
3. if entry found for destination
then {
if dest on segment from which frame arrived
then drop the frame
else forward the frame on interface indicated
} forward on all but the interface
on which the frame arrived
else flood 71
Source: A
SELF-LEARNING, Dest: A’
FORWARDING: EXAMPLE A A A’
C’ B
frame destination unknown: 1 2
flood A6A’ 3
5 4
destination A location C
known: selective send A’ A
B’ A’
MAC addr interface TTL
A 1 60 Switch table
A’ 4 60 (initially empty)
72
INTERCONNECTING SWITCHES
switches can be connected together
S4
S1
S3
A S2
F
D I
B C
G H
E
Q: sending from A to G - how does S1 know to
forward frame destined to F via S4 and S3?
A: self learning! (works exactly the same as in single-
switch case!)
73
INSTITUTIONAL NETWORK
mail server
to external
network
router web server
IP subnet
74
SWITCHES VS. ROUTERS
both store-and-forward devices
routers: network layer devices (examine network layer headers)
switches: link layer devices
routers maintain routing tables, implement routing
algorithms
switches maintain switch tables, implement filtering,
learning algorithms
75
NEXT CLASS
Internet and TCP/IP by
ผศ.ดร. นภัทร สระเอี่ยม
76