Transcript 1. Foundation

1
2. GETTING
CONNECTED (PART 1)
Rocky K. C. Chang
Department of Computing
The Hong Kong Polytechnic University
7 February 2017
2
Many links on a network path
3
1. Overview of this chapter
• The lowest two layers:
Provide a virtual link for (unreliable) packets to above
Datalink layer
Datalink layer
Provide a virtual (unreliable) bit pipe to above
Physical layer
Physical layer
4
1. Overview of this lecture
• Direct link networks: point-to-point links or shared media
• Five problems:
• Bit synchronization
• Frame synchronization
• Error detection
• Reliable link service
• Multiple access control problem (for shared media only)
• LAN: Ethernet and Wireless
5
2. Some networking hardware
• Network nodes
• Switches and routers (highly specialized hardware)
• Hosts (general-purpose computers):
CPU
Cache
Memory
Network
adaptor
I/O bus
To network
6
2.1 Network hosts
• Network adaptors and device drivers
• All the networking functionality described in this chapter, except ARQ
schemes, is implemented in the network adaptor.
• The device driver interfaces between the network adaptor and the
OS.
• Unparalleled performance improvement of memory latency
and processor speed
• A network host runs at memory speeds, not processor speeds.
• Intel and Micron Produce Breakthrough Memory Technology
7
2.2 Network links
• A network link is a physical medium carrying signals in the
form of electromagnetic waves.
• Cabling:
• Local links (office, lab, campus): Twisted pairs, coaxial cables, and
optical fibers
• Leased links from carriers: T1, T3; and OC-N, where N = 1, 3, 9,
12, 18, 24, ….
• Links to residential home: POTS, ISDN, xDSL, CATV, ATM, etc.
• Wireless: radio, microwave, infrared, light; small area, cellular
network, satellite network.
8
2.2 Network links
Common services available to connect your home
9
2.2 Network links
• Generally, a packet may go through different types of
network link.
• The slowest link determines the end-to-end throughput.
• Bandwidth
• Narrowband vs. broadband (ISDN vs. B-ISDN)
• Increase bandwidth either by operating in a higher frequency band
or increase the signal-to-noise ratio
• Upper bound on the link’s data rate (Shannon-Hartley Theorem):
Blog2(1+S/N) in bits per second
10
2.2 Network links
• Bluetooth is based on a global radio-frequency (RF) standard,
operating on the 2.4 GHz ISM band.
• 3G mobile phone: 2,500MHz-2,690MHz band
11
2.2 Network links
• Sending binary bits onto a physical link (bit-serial
transmission):
• Encoding the bits before transmission (for the purpose of bit
synchronization to be discussed later).
• Modulation: a process by which a property or a parameter
(frequency, amplitude, phase) of a signal is varied in proportion to a
second signal.
• For encoding binary data onto electromagnetic signals
• Signals are carried in the form of electromagnetic waves.
12
3. The five problems
• Assume modulation schemes given.
• Five problems:
• Bit synchronization (need additional encoding data, such as from
Manchester encoding, to delineate bits)
• Frame synchronization (need additional protocols to delineate frames)
• Error detection (need additional algorithms to detect errors, if
occurred)
• Reliable link service (need additional schemes to recover from errors)
• Multiple access control problem (for shared media only; need
additional protocols to share the medium)
13
3.1 An Ethernet network adaptor
H
O
S
T
B
U
S
LAN controller
System
bus
interface
TX
FIFO
Data out
TX
802.3
MAC
RX
FIFO
Manchester codec
RX
Physical
signalling
Data in
Control in
Transceiver
Medium
attachment
unit
N
E
T
W
O
R
K
14
4. Problem 1: Bit synchronization (BS)
• Problem: How does a receiver synchronize with a sender,
so that bits can be decoded correctly from the signals?
Signalling component
Signal
Node
Adaptor
Adaptor
Bits
Node
15
4.1 BS: four encoding methods
• Assume that two discrete signals: high and low are used
to encode 0s and 1s.
• Solutions: NRZ, NRZI, Manchester, and 4B/5B:
Bits
NRZ
Clock
Manchester
NRZI
0
0
1
0
1
1
1
1
0
1
0
0
0
0
1
0
16
4.2 BS: NRZ and NRZI
• Non-return to zero (NRZ)
• 0: a low signal; 1: a high signal
• Problem: A consecutive of 0s or 1s causes baseline wander, as
well as not providing enough signal transitions for bit
synchronization.
• Non-return to zero inverted (NRZI)
• 1: making a transition from the current signal; 0: staying at the
current signal.
• Problem: The problem of having consecutive 0s remains.
17
4.3 BS: Manchester encoding
• Manchester encoding
• 0: low-to-high transition; 1: high-to-low transition (the result of
exclusive-OR of the NRZ-encoded data with the clock)
• Advantage: provide enough signal transitions for bit
synchronization.
• Disadvantage: double the rate of signal transitions.
• Baud rate is the rate at which the signal changes. In this case,
baud rate is double of data rate.
18
4.4 BS: 4B/5B encoding
• 4B/5B encoding
• Insert a bit to every four bits of data, such that consecutive 0s or 1s
will be broken up.
• (breaking up consecutive 0s) Each code must have no more than
one leading 0 and no more than two trailing 0s.
• E.g., 00110 and 01000 are not used.
• As a result, the encoded data would not contain more than 3
consecutive 0s.
• See Table 2.5 in the text for the encoding.
• (breaking up consecutive 1s) The resulting 5-bits are transmitted
using the NRZI encoding.
19
4.4 BS: 4B/5B encoding
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Data
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
5-bit codes
11110
01001
10100
10101
01010
01011
01110
01111
10010
10011
10110
10111
11010
11011
11100
11101
20
5. Problem 2: Frame synchronization (FS)
• Problem: Given that a receiver can synchronize bits sent
by a sender, how does the receiver recognize bits
belonging to the same frame?
Signalling component
Signal
Node
Adaptor
Adaptor
Bits
Frames
Node
21
5.1 FS: IP over Ethernet
• For example, when an IP datagram is handed down to an
Ethernet network adaptor, the IP datagram is sent out in
an Ethernet frame.
Dest
address
Src
address
Type
Type
0800
Data
IP datagram
CRC
22
5.2 Several solutions
• Byte-oriented protocols (e.g. PPP)
• Data unit in terms of bytes (ASCII, EBCDIC)
• Sentinel approach vs. byte counting approach
• Bit-oriented protocols (e.g. HDLC, Ethernet)
• Sentinel approach
• Clock-based framing (SONET)
• It addresses both the framing and encoding problems.
23
5.3 Byte-oriented protocols
• Sentinel approach to framing
• A special character 01111110 (0x7e) serves as a start-of-text
character (flag field)
• Character stuffing: escape this special character in the data by
prepending it with an escape character 0x7d.
• 0x7e escaped to 0x7d, 0x5e
• 0x7d escaped to 0x7d, 0x5d
24
5.3 Byte-oriented protocols
• PPP’s frame structure:
Flag
7E
Addr
FF
Control
03
Protocol
Protocol
0021
Information
IP datagram
CRC
Flag
7E
25
5.3 Byte-oriented protocols
• Byte-counting approach to framing, e.g. DECNET’s
DDCMP
• SYN character serves as a synchronization character.
• The COUNT field specifies how many bytes are contained in the
8
8
8
14
42
SYN
SYN
Class
frame.
Count
Header
16
Body
CRC
26
5.4 Bit-oriented protocols
• For example, High-Level Data Link Control (HDLC)
protocol.
• A special bit sequence 01111110 is transmitted when the link is idle.
• When this sequence appears in the data, it is escaped using bit
stuffing.
8
16
Beginning
sequence
Header
16
Body
8
Ending
CRC sequence
27
5.4 Bit-oriented protocols: bit stuffing
• On sending side:
• Except for transmitting the special 01111110 sequence, 0 is
inserted after 5 consecutive 1s.
• On receiving side:
• If five consecutive 1s arrive,
• if the next bit is 0, it must be a stuffed bit. It is therefore removed.
• If the next bit is 1,
• If the next bit is 0, then the sequence indicates the end of the frame.
• If the next bit is 1, there must be an error, and the whole frame is discarded.
28
5.4 Bit-oriented protocols: bit stuffing
• For example,
• Original bit stream:
• 011011111111111111110010
• After bit stuffing by source:
• 011011111011111011111010010
• After bit de-stuffing by receiver:
• 011011111111111111110010
• What happens if transmission errors
• occurred to the stuffed bits?
• occurred to the nonstuffed bits?
29
6. Problem 3: Error detection (ED)
• Transmission errors do occur, with different probabilities in
different media.
• Two general approaches:
• Error correction code (forward error correction)
• Error detection code + an error correction mechanism when errors
are detected.
• Insert redundancy for error correction or detection.
• Common error detection methods:
• Cyclic redundancy check (CRC)
• Checksum
30
6.1 ED: error detection codes
• Error detection codes are usually inserted in more than
one layer, e.g.
• HTTP
• TCP (16-bit checksum for the TCP header and data)
• IPv4 (16-bit checksum for the IP header)
• PPP/Ethernet (CRC-16, CRC-32 for the whole frame)
• Why don’t we just have CRCs on the datalink layer?
31
6.2 ED: two-dimensional parity
• The 2-dim parity catches all 1-, 2-, and 3-bit errors, and
most 4-bit errors.
Parity
bits
Data
Parity
byte
0101001
1
1101001
0
1011110
1
0001110
1
0110100
1
1011111
0
1111011
0
32
6.3 ED: Checksum
• Add up all the words that are transmitted and then
transmit the result of that sum.
• If any transmitted data, including the checksum itself, is corrupted,
then the results will not match.
• Internet checksum:
• A sender add 16-bit words using ones complement arithmetic, and
then take ones complement of the result. The result is stored in the
checksum field.
• A receiver performs 16-bit checksum. If no error, the checksum
should give all 1s.
33
6.3 ED: Checksum
• Ones complement arithmetic:
• A negative integer -x is represented as the complement of x.
• A carryout from the most significant bit needs to be added to the
result.
• For example: 4-bit word checksum
• Data: 1010 1100, and its checksum: 1000.
• Data sent: 1010 1100 1000
• Receiver adds all the data sent in 4-bit word in ones complement,
which gives 1111.
34
6.3 ED: Checksum
• Advantages:
• Use a relatively small number of bits.
• Easy to implement in software.
• Disadvantages:
• Not a strong error detection algorithm, as compared with CRC
35
6.4 ED: cyclic redundancy check (CRC)
• Think of an (n+1)-bit message, M(x), as a polynomial of
degree n, e.g.
• 10011010 as
• 1x7 + 0x6 + 0x5 + 1x4 + 1x3 + 0x2 + 1x1 + 0x0.
• Given a divisor polynomial of order k, C(x), find a code
word of k bits, such that M(x) concatenated with the code
word is divisible by C(x).
• P(x) is a concatenation of M(x) and the code word.
36
6.4 ED: cyclic redundancy check
• For example, C(x) = 1x3 + 1x2 + 0x1 + 1x0.
• The computed code word is 101.
• P(x) is given by 10011010 concatenated with 101, or 1x10 + 0x9 +
0x8 + 1x7 + 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 0x1 + 1x0.
• One may verify that P(x) is divisible by C(x), i.e. 0 remainder.
• Errors can be detected when the remainder is not zero when a
receiver divides P(x) by C(x).
37
6.4 ED: cyclic redundancy check
• To obtain the code word,
• Divide 1x10 + 0x9 + 0x8 + 1x7 + 1x6 + 0x5 + 1x4 + 0x3 + 0x2
+ 0x1 + 0x0 by 1x3 + 1x2 + 0x1 + 1x0 .
• Subtraction is performed by an exclusive-OR operation (XOR).
• The result is a 3-bit remainder, one bit less than the divisor
polynomial.
• It can be implemented efficiently in hardware.
38
6.4 ED: cyclic redundancy check
Generator
11111001
1101 10011010000
1101
Message
1001
1101
1000
1101
1011
1101
1100
1101
1000
1101
101
Remainder
39
6.4 ED: cyclic redundancy check
• Choice of the divisor polynomial:
• Express a corrupted message received by a receiver as P(x) + E(x),
where E(x) is an error polynomial.
• Errors go undetected if E(x) is divisible by C(x).
• For example, the CRC can catch
• all single-bit errors if the xk and x0 terms in C(x) have nonzero
coefficients, and
• any odd number of errors if C(x) contains the factor (x+1).
40
6.4 ED: cyclic redundancy check
• Six generator polynomials that have become
international standards are:
• CRC-8 = x8+x2+x+1
• CRC-10 = x10+x9+x5+x4+x+1
• CRC-12 = x12+x11+x3+x2+x+1
• CRC-16 = x16+x15+x2+1
• CRC-CCITT = x16+x12+x5+1
• CRC-32 =
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
41
THIS WILL BE
CONTINUED IN PART 2.