Information

Networking II
CPEN441

JOSEPH DOUMIT, PhD

SPRING 2026
Course Information
Prerequisites
◦ CPEN241

Communication:
◦ Announcements on Moodle
◦ Emails: [Link]@[Link]

Office Hours
◦ TTh 15:30 – 17:00 (EC 249)
◦ Or by appointment

Work and Grading

◦ Exam (30%), Project (30%), and Final (40%)

CPEN441 – INFORMATION NETWORKING II Joseph Doumit, PhD 2

Course Overview

o2. Getting Connected

CPEN441 – INFORMATION NETWORKING II

Chapter 2: Getting
Connected
We will cover these skills

o Different communication media for data transmission

o Encoding bits for correct reception

o Techniques for detecting and handling transmission

errors

o Methods to ensure reliable links despite transmission

issues

o The Media Access Control (MAC) problem

o Carrier Sense Multiple Access (CSMA) networks

Chapter Outline

o1. Perspectives on connecting

o2. Encoding

o3. Framing

o4. Error detection

o5. Reliable transmission

o6. Multiple access networks

o7. Summary

CPEN441 - CHAPTER 2: GETTING CONNECTED

Chapter Outline

o1. Perspectives on connecting

CPEN441 - CHAPTER 2: GETTING CONNECTED

Perspectives on Connecting

An end-user’s view of the Internet

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 7

Perspectives on Connecting
Link Capacity and Shannon-Hartley Theorem

Gives the upper bound to the capacity of a link in terms of

bits per second (bps) as a function of signal-to-noise ratio of
the link measured in decibels (dB).
C = Blog2(1+S/N)
◦ Where B = 3300 – 300 = 3000Hz, S is the signal power, N the average
noise.
◦ The signal to noise ratio (S/N) is measured in decibels is related to dB
= 10 x log10(S/N). If there is 30dB of noise then S/N = 1000.
◦ Now C = 3000 x log2(1001) = 30kbps.
◦ How can we get 56kbps?

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 8

Perspectives on Connecting
Links

All practical links rely on some sort of electromagnetic radiation

propagating through a medium or, in some cases, through free space
One way to characterize links, then, is by the medium they use
◦ Typically copper wire in some form (as in Digital Subscriber Line (DSL) and coaxial
cable),
◦ Optical fiber (as in both commercial fiber-to-the home services and many long-
distance links in the Internet’s backbone), or
◦ Air/free space (for wireless links)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 9

Perspectives on Connecting
Links

Another important link characteristic is the frequency

◦ Measured in hertz, with which the electromagnetic waves oscillate
Distance between the adjacent pair of maxima or minima of a wave
measured in meters is called wavelength
◦ Speed of light divided by frequency gives the wavelength.
◦ Frequency on a copper cable range from 300Hz to 3300Hz; Wavelength for 300Hz
wave through copper is speed of light on a copper / frequency
◦ 2/3 x 3 x 108 /300 = 667 x 103 meters.
Placing binary data on a signal is called encoding.
Modulation involves modifying the signals in terms of their frequency,
amplitude, and phase.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 10

Perspectives on Connecting

Links

Electromagnetic spectrum

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 11

Perspectives on Connecting

Links

Common services available to connect your home

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 12

Chapter Outline

o2. Encoding

CPEN441 - CHAPTER 2: GETTING CONNECTED

Encoding

NRZ

Signals travel between signaling components; bits flow between adaptors

NRZ encoding of a bit stream

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 14

Encoding
Problems with NRZ

Baseline wander
◦ The receiver keeps an average of the signals it has seen so far
◦ Uses the average to distinguish between low and high signal
◦ When a signal is significantly low than the average, it is 0, else it is 1
◦ Too many consecutive 0’s and 1’s cause this average to change, making it
difficult to detect
Clock recovery
◦ Frequent transition from high to low or vice versa are necessary to enable clock
recovery
◦ Both the sending and decoding process is driven by a clock
◦ Every clock cycle, the sender transmits a bit and the receiver recovers a bit
◦ The sender and receiver have to be precisely synchronized

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 15

Encoding
NRZI

◦ Non Return to Zero Inverted

◦ Sender makes a transition from the current signal to encode 1 and stay at the
current signal to encode 0
◦ Solves for consecutive 1’s

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 16

Encoding
Manchester encoding

◦ Merging the clock with signal by transmitting Ex-OR of the NRZ encoded data and
the clock
◦ Clock is an internal signal that alternates from low to high, a low/high pair is
considered as one clock cycle
◦ In Manchester encoding
◦ 0: low→ high transition
◦ 1: high→ low transition

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 17

Encoding
Problem with Manchester encoding

◦ Doubles the rate at which the signal transitions are made on the link
◦ Which means the receiver has half of the time to detect each pulse of the signal
◦ The rate at which the signal changes is called the link’s baud rate
◦ In Manchester the bit rate is half the baud rate

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 18

Encoding

Example

Different encoding strategies

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 19

Encoding
4B/5B encoding

◦ Insert extra bits into bit stream so as to break up the long sequence of 0’s and 1’s
◦ Every 4-bits of actual data are encoded in a 5- bit code that is transmitted to the
receiver
◦ 5-bit codes are selected in such a way that each one has no more than one
leading 0(zero) and no more than two trailing 0’s.
◦ No pair of 5-bit codes results in more than three consecutive 0’s

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 20

 Encoding
4B/5B encoding

0000 → 11110 16 left

0001 → 01001 11111 – when the line is idle
0010 → 10100 00000 – when the line is dead
.. 00100 – to mean halt
..
1111 → 11101 13 left : 7 invalid, 6 for various control signals

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 21

Chapter Outline

o3. Framing

CPEN441 - CHAPTER 2: GETTING CONNECTED

Framing

We are focusing on packet-switched networks, which means

that blocks of data (called frames at this level), not bit
streams, are exchanged between nodes.
It is the network adaptor that enables the nodes to
exchange frames.

Bits flow between adaptors, frames between hosts

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 23

Framing

When node A wishes to transmit a frame to node B, it tells its

adaptor to transmit a frame from the node’s memory. This
results in a sequence of bits being sent over the link.
The adaptor on node B then collects together the sequence
of bits arriving on the link and deposits the corresponding
frame in B’s memory.
Recognizing exactly what set of bits constitute a frame—that
is, determining where the frame begins and ends—is the
central challenge faced by the adaptor

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 24

Framing
Byte-oriented protocols

◦ To view each frame as a collection of bytes (characters) rather than

bits
◦ BISYNC (Binary Synchronous Communication) Protocol
◦ Developed by IBM (late 1960)
◦ DDCMP (Digital Data Communication Protocol)
◦ Used in DECNet

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 25

Framing
Byte-oriented protocols – BISYNC

◦ Frames transmitted beginning with leftmost field

◦ Beginning of a frame is denoted by sending a special SYN
(synchronize) character
◦ Data portion of the frame is contained between special sentinel
character STX (start of text) and ETX (end of text)
◦ SOH : Start of Header
◦ DLE : Data Link Escape
◦ CRC: Cyclic Redundancy Check

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 26

Framing

Byte-oriented protocols – BISYNC

BISYNC Frame Format

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 27

Framing
Point-to-Point Protocol (PPP)

Recent PPP which is commonly run over Internet links uses sentinel approach
◦ Special start of text character denoted as Flag
◦ 01111110
◦ Address, control : default numbers
◦ Protocol for demux : IP / IPX
◦ Payload : negotiated (1500 bytes)
◦ Checksum : for error detection

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 28

Framing

Point-to-Point Protocol (PPP)

PPP Frame Format

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 29

Framing
Byte-counting approach

Byte-counting approach
◦ DDCMP
◦ count : how many bytes are contained in the frame body
◦ If count is corrupted
◦ Framing error

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 30

Framing

Byte-counting approach – DDCMP

DDCMP Frame Format

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 31

Framing
Bit-oriented protocols – HDLC

◦ HDLC : High Level Data Link Control

◦ Beginning and Ending Sequences
01111110

HDLC Frame Format

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 32

Framing
Bit-oriented protocols – HDLC

HDLC Protocol
◦ On the sending side, any time five consecutive 1’s have been transmitted from the body of the message (i.e.
excluding when the sender is trying to send the distinguished 01111110 sequence)
◦ The sender inserts 0 before transmitting the next bit

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 33

Framing
Bit-oriented protocols – HDLC

HDLC Protocol
◦ On the receiving side
◦ 5 consecutive 1’s
◦ Next bit 0 : Stuffed, so discard it
1 : Either End of the frame marker
Or Error has been introduced in the bitstream
Look at the next bit
If 0 ( 01111110 ) → End of the frame marker
If 1 ( 01111111 ) → Error, discard the whole frame
The receiver needs to wait for next
01111110 before it can start
receiving again

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 34

Chapter Outline

o4. Error detection

CPEN441 - CHAPTER 2: GETTING CONNECTED

Error Detection

Bit errors are introduced into frames

◦ Because of electrical interference and thermal noises
Detecting Error
Correction Error
Two approaches when the recipient detects an error
◦ Notify the sender that the message was corrupted, so the sender can send
again.
◦ If the error is rare, then the retransmitted message will be error-free
◦ Using some error correct detection and correction algorithm, the receiver
reconstructs the message

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 36

Error Detection

Common technique for detecting transmission error

◦ CRC (Cyclic Redundancy Check)
◦ Used in HDLC, DDCMP, CSMA/CD, Token Ring
◦ Other approaches
◦ Two Dimensional Parity (BISYNC)
◦ Checksum (IP)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 37

Error Detection

Basic Idea of Error Detection

◦ To add redundant information to a frame that can be used to
determine if errors have been introduced
◦ Imagine (Extreme Case)
◦ Transmitting two complete copies of data
◦ Identical → No error
◦ Differ → Error
◦ Poor Scheme ???
◦ n bit message, n bit redundant information
◦ Error can go undetected
◦ In general, we can provide strong error detection technique
◦ k redundant bits, n bits message, k << n
◦ In Ethernet, a frame carrying up to 12,000 bits of data requires only 32-bit CRC

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 38

Error Detection

Extra bits are redundant

◦ They add no new information to the message
◦ Derived from the original message using some algorithm
◦ Both the sender and receiver know the algorithm

m r m r
Sender Receiver

Receiver computes r using m

If they match, no error

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 39

Error Detection
Two-dimensional parity

Two-dimensional parity is exactly what the name suggests

It is based on “simple” (one-dimensional) parity, which
usually involves adding one extra bit to a 7-bit code to
balance the number of 1s in the byte. For example,
◦ Odd parity sets the eighth bit to 1 if needed to give an odd number
of 1s in the byte, and
◦ Even parity sets the eighth bit to 1 if needed to give an even number
of 1s in the byte

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 40

Error Detection
Two-dimensional parity

Two-dimensional parity does a similar calculation for each

bit position across each of the bytes contained in the frame
This results in an extra parity byte for the entire frame, in
addition to a parity bit for each byte
Two-dimensional parity catches all 1-, 2-, and 3-bit errors and
most 4-bit errors

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 41

Error Detection

Two-dimensional parity

Two Dimensional Parity

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 42

Error Detection
Internet checksum algorithm

Not used at the link level

Add up all the words that are transmitted and then transmit
the result of that sum
◦ The result is called the checksum
The receiver performs the same calculation on the received
data and compares the result with the received checksum
If any transmitted data, including the checksum itself, is
corrupted, then the results will not match, so the receiver
knows that an error occurred

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 43

Error Detection
Internet checksum algorithm

Consider the data being checksummed as a sequence of

16-bit integers.
Add them together using 16-bit ones complement arithmetic
(explained next slide) and then take the ones complement
of the result.
That 16-bit number is the checksum

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 44

Error Detection
Internet checksum algorithm

In ones complement arithmetic, a negative integer −x is

represented as the complement of x;
◦ Each bit of x is inverted.

When adding numbers in ones complement arithmetic, a

carryout from the most significant bit needs to be added to
the result.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 45

Error Detection
Internet checksum algorithm

Consider, for example, the addition of −5 and −3 in ones

complement arithmetic on 4-bit integers
◦ +5 is 0101, so −5 is 1010; +3 is 0011, so −3 is 1100

If we add 1010 and 1100 ignoring the carry, we get 0110

In ones complement arithmetic, the fact that this operation
caused a carry from the most significant bit causes us to
increment the result, giving 0111, which is the ones
complement representation of −8 (obtained by inverting the
bits in 1000), as we would expect

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 46

Error Detection
Cyclic redundancy check (CRC)

Reduce the number of extra bits and maximize protection

Given a bit string 110001 we can associate a polynomial on
a single variable x for it.
1.x5+1.x4+0.x3+0.x2+0.x1+1.x0 = x5+x4+1 and the degree is 5.
A k-bit frame has a maximum degree of k-1

Let M(x) be a message polynomial and C(x) be a generator

polynomial.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 47

Error Detection
Cyclic redundancy check (CRC)

Let M(x)/C(x) leave a remainder of 0.

When M(x) is sent and M’(x) is received we have M’(x) =
M(x)+E(x)
The receiver computes M’(x)/C(x) and if the remainder is
nonzero, then an error has occurred.
The only thing the sender and the receiver should know is
C(x).

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 48

Error Detection
Cyclic redundancy check (CRC)

Polynomial Arithmetic Modulo 2

◦ Any polynomial B(x) can be divided by a divisor polynomial C(x) if B(x) is of

higher degree than C(x).

◦ Any polynomial B(x) can be divided once by a divisor polynomial C(x) if

B(x) is of the same degree as C(x).

◦ The remainder obtained when B(x) is divided by C(x) is obtained by

subtracting C(x) from B(x).

◦ To subtract C(x) from B(x), we simply perform the exclusive-OR (XOR)

operation on each pair of matching coefficients.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 49

Error Detection
Cyclic redundancy check (CRC)

Let M(x) be a frame with m bits and let the generator

polynomial have less than m bits say equal to r.
Let r be the degree of C(x). Append r zero bits to the low-
order end of the frame, so it now contains m+r bits and
corresponds to the polynomial xrM(x).

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 50

Error Detection
Cyclic redundancy check (CRC)

Divide the bit string corresponding to xrM(x) by the bit string

corresponding to C(x) using modulo 2 division.
Subtract the remainder (which is always r or fewer bits) from
the string corresponding to xrM(x) using modulo 2 subtraction
(addition and subtraction are the same in modulo 2).
The result is the checksummed frame to be transmitted. Call
it polynomial M’(x).

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 51

Error Detection
Cyclic redundancy check (CRC)

CRC Calculation using Polynomial Long Division

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 52

Error Detection
Cyclic redundancy check (CRC)

Properties of Generator Polynomial

◦ Let P(x) represent what the sender sent and P(x) + E(x) is the received string. A 1 in
E(x) represents that in the corresponding position in P(x) the message the bit is
flipped.

◦ We know that P(x)/C(x) leaves a remainder of 0, but if E(x)/C(x) leaves a remainder

of 0, then either E(x) = 0 or C(x) is factor of E(x).

◦ When C(x) is a factor of E(x) we have problem; errors go unnoticed.

◦ If there is a single bit error then E(x) = xi, where i determines the bit in error. If C(x)
contains two or more terms it will never divide E(x), so all single bit errors will be
detected.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 53

Error Detection
Cyclic redundancy check (CRC)

Properties of Generator Polynomial

◦ In general, it is possible to prove that the following types of errors can
be detected by a C(x) with the stated properties
◦ All single-bit errors, as long as the xk and x0 terms have nonzero coefficients.
◦ All double-bit errors, as long as C(x) has a factor with at least three terms.
◦ Any odd number of errors, as long as C(x) contains the factor (x+1).
◦ Any “burst” error (i.e., sequence of consecutive error bits) for which the length of
the burst is less than k bits. (Most burst errors of larger than k bits can also be
detected.)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 54

Error Detection
Cyclic redundancy check (CRC)

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

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 55

Chapter Outline

o5. Reliable transmission

CPEN441 - CHAPTER 2: GETTING CONNECTED

Reliable Transmission

CRC is used to detect errors.

Some error codes are strong enough to correct errors.
The overhead is typically too high.
Corrupt frames must be discarded.
A link-level protocol that wants to deliver frames reliably must
recover from these discarded frames.
This is accomplished using a combination of two fundamental
mechanisms
◦ Acknowledgements and Timeouts

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 57

Reliable Transmission

An acknowledgement (ACK for short) is a small control

frame that a protocol sends back to its peer saying that it
has received the earlier frame.
◦ A control frame is a frame with header only (no data).

The receipt of an acknowledgement indicates to the sender

of the original frame that its frame was successfully
delivered.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 58

Reliable Transmission

If the sender does not receive an acknowledgment after a

reasonable amount of time, then it retransmits the original
frame.
The action of waiting a reasonable amount of time is called
a timeout.
The general strategy of using acknowledgements and
timeouts to implement reliable delivery is sometimes called
Automatic Repeat reQuest (ARQ).

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 59

Reliable Transmission
Stop-and-wait protocol

Idea of stop-and-wait protocol is straightforward

◦ After transmitting one frame, the sender waits for an

acknowledgement before transmitting the next frame.

◦ If the acknowledgement does not arrive after a certain period of

time, the sender times out and retransmits the original frame

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 60

 Reliable Transmission

Stop-and-wait protocol

Timeline showing four different scenarios for the stop-and-wait algorithm.

(a) The ACK is received before the timer expires; (b) the original frame is lost; (c) the ACK is lost; (d) the timeout fires too soon

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 61

Reliable Transmission
Stop-and-wait protocol

If the acknowledgment is lost or delayed in arriving

◦ The sender times out and retransmits the original frame, but the receiver will think
that it is the next frame since it has correctly received and acknowledged the first
frame
◦ As a result, duplicate copies of frames will be delivered

How to solve this

◦ Use 1 bit sequence number (0 or 1)
◦ When the sender retransmits frame 0, the receiver can determine that it is seeing a
second copy of frame 0 rather than the first copy of frame 1 and therefore can
ignore it (the receiver still acknowledges it, in case the first acknowledgement was
lost)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 62

Reliable Transmission

Stop-and-wait protocol

Timeline for stop-and-wait with 1-bit sequence number

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 63
Reliable Transmission
Stop-and-wait protocol

The sender has only one outstanding frame on the link at a time
◦ This may be far below the link’s capacity

Consider a 1.5 Mbps link with a 45 ms RTT

◦ The link has a delay  bandwidth product of 67.5 Kb or approximately 8 KB
◦ Since the sender can send only one frame per RTT and assuming a frame size of 1
KB
◦ Maximum Sending rate
◦ Bits per frame  Time per frame = 1024  8  0.045 = 182 Kbps
Or about one-eighth of the link’s capacity
◦ To use the link fully, then sender should transmit up to eight frames before having to
wait for an acknowledgement

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 64

Reliable Transmission

Sliding window protocol

Timeline for Sliding Window Protocol

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 65

Reliable Transmission
Sliding window protocol

Sender assigns a sequence number denoted as SeqNum to each

frame.
◦ Assume it can grow infinitely large

Sender maintains three variables

◦ Sending Window Size (SWS)
◦ Upper bound on the number of outstanding (unacknowledged) frames that the sender
can transmit
◦ Last Acknowledgement Received (LAR)
◦ Sequence number of the last acknowledgement received
◦ Last Frame Sent (LFS)
◦ Sequence number of the last frame sent

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 66

Reliable Transmission
Sliding window protocol

Sender also maintains the following invariant

LFS – LAR ≤ SWS

Sliding Window on Sender

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 67

Reliable Transmission
Sliding window protocol

When an acknowledgement arrives

◦ the sender moves LAR to right, thereby allowing the sender to transmit another
frame

Also the sender associates a timer with each frame it transmits

◦ It retransmits the frame if the timer expires before the ACK is received

Note that the sender has to be willing to buffer up to SWS frames

◦ WHY?

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 68

Reliable Transmission
Sliding window protocol

Receiver maintains three variables

◦ Receiving Window Size (RWS)
◦ Upper bound on the number of out-of-order frames that the receiver is willing to accept
◦ Largest Acceptable Frame (LAF)
◦ Sequence number of the largest acceptable frame
◦ Last Frame Received (LFR)
◦ Sequence number of the last frame received

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 69

Reliable Transmission
Sliding window protocol

Receiver also maintains the following invariant

LAF – LFR ≤ RWS

Sliding Window on Receiver

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 70

Reliable Transmission
Sliding window protocol

When a frame with sequence number SeqNum arrives, what does the
receiver do?

◦ If SeqNum ≤ LFR or SeqNum > LAF

◦ Discard it (the frame is outside the receiver window)
◦ If LFR < SeqNum ≤ LAF
◦ Accept it
◦ Now the receiver needs to decide whether or not to send an ACK

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 71

Reliable Transmission
Sliding window protocol

◦ Let SeqNumToAck
◦ Denote the largest sequence number not yet acknowledged, such that all
frames with sequence number less than or equal to SeqNumToAck have been
received

◦ The receiver acknowledges the receipt of SeqNumToAck even if

high-numbered packets have been received
◦ This acknowledgement is said to be cumulative.
◦ The receiver then sets
◦ LFR = SeqNumToAck and adjusts
◦ LAF = LFR + RWS

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 72

Reliable Transmission
Sliding window protocol

For example, suppose LFR = 5 and RWS = 4

(i.e. the last ACK that the receiver sent was for seq. no. 5)

LAF = 9

If frames 7 and 8 arrive, they will be buffered because they are within the receiver window

But no ACK will be sent since frame 6 is yet to arrive

Frames 7 and 8 are out of order
Frame 6 arrives (it is late because it was lost first time and had to be retransmitted)
Now Receiver Acknowledges Frame 8
and bumps LFR to 8
and LAF to 12

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 73

Reliable Transmission
Issues with sliding window protocol

When timeout occurs, the amount of data in transit decreases

◦ Since the sender is unable to advance its window

When the packet loss occurs, this scheme is no longer keeping the
pipe full
◦ The longer it takes to notice that a packet loss has occurred, the more severe the
problem becomes

How to improve this

◦ Negative Acknowledgement (NAK)
◦ Additional Acknowledgement
◦ Selective Acknowledgement

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 74

Reliable Transmission
Issues with sliding window protocol

Negative Acknowledgement (NAK)

◦ Receiver sends NAK for frame 6 when frame 7 arrive (in the previous example)
◦ However this is unnecessary since sender’s timeout mechanism will be sufficient to catch the situation

Additional Acknowledgement
◦ Receiver sends additional ACK for frame 5 when frame 7 arrives
◦ Sender uses duplicate ACK as a clue for frame loss

Selective Acknowledgement
◦ Receiver will acknowledge exactly those frames it has received, rather than the highest number frames
◦ Receiver will acknowledge frames 7 and 8
◦ Sender knows frame 6 is lost
◦ Sender can keep the pipe full (additional complexity)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 75

Reliable Transmission
Issues with sliding window protocol

How to select the window size

◦ SWS is easy to compute
◦ Delay  Bandwidth
◦ RWS can be anything
◦ Two common setting
◦ RWS = 1
No buffer at the receiver for frames that arrive out of order
◦ RWS = SWS
The receiver can buffer frames that the sender transmits
It does not make any sense to keep RWS > SWS
WHY?

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 76

Reliable Transmission
Issues with sliding window protocol

Finite Sequence Number

◦ Frame sequence number is specified in the header field
◦ Finite size
◦ 3 bit: eight possible sequence number: 0, 1, 2, 3, 4, 5, 6, 7
◦ It is necessary to wrap around

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 77

Reliable Transmission
Issues with sliding window protocol

How to distinguish between different incarnations of the

same sequence number?
◦ Number of possible sequence number must be larger than the
number of outstanding frames allowed
◦ Stop and Wait: One outstanding frame
◦ 2 distinct sequence number (0 and 1)
◦ Let MaxSeqNum be the number of available sequence numbers
◦ SWS + 1 ≤ MaxSeqNum
◦ Is this sufficient?

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 78

Reliable Transmission
Issues with sliding window protocol

SWS + 1 ≤ MaxSeqNum
◦ Is this sufficient?

◦ Depends on RWS
◦ If RWS = 1, then sufficient
◦ If RWS = SWS, then not good enough
For example, we have eight sequence numbers
0, 1, 2, 3, 4, 5, 6, 7
RWS = SWS = 7
Sender sends 0, 1, …, 6
Receiver receives 0, 1, … ,6
Receiver acknowledges 0, 1, …, 6
ACK (0, 1, …, 6) are lost
Sender retransmits 0, 1, …, 6
Receiver is expecting 7, 0, …., 5

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 79

 Reliable Transmission
Issues with sliding window protocol

To avoid this,

If RWS = SWS

SWS < (MaxSeqNum + 1)/2

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 80

Reliable Transmission
Issues with sliding window protocol

Serves three different roles

◦ Reliable
◦ Preserve the order
◦ Each frame has a sequence number
◦ The receiver makes sure that it does not pass a frame up to the next higher-level
protocol until it has already passed up all frames with a smaller sequence number
◦ Frame control
◦ Receiver is able to throttle the sender
◦ Keeps the sender from overrunning the receiver
◦ From transmitting more data than the receiver is able to process

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 81

Chapter Outline

o6. Multiple access networks

CPEN441 - CHAPTER 2: GETTING CONNECTED

Multiple Access Networks
Ethernet

Most successful local area networking technology of last 20 years.

Developed in the mid-1970s by researchers at the Xerox Palo Alto
Research Centers (PARC).
Uses CSMA/CD technology
◦ Carrier Sense Multiple Access with Collision Detection.
◦ A set of nodes send and receive frames over a shared link.
◦ Carrier sense means that all nodes can distinguish between an idle and a busy link.
◦ Collision detection means that a node listens as it transmits and can therefore
detect when a frame it is transmitting has collided with a frame transmitted by
another node.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 83

Multiple Access Networks
Ethernet

Uses ALOHA (packet radio network) as the root protocol

◦ Developed at the University of Hawaii to support communication across the
Hawaiian Islands.
◦ For ALOHA the medium was atmosphere, for Ethernet the medium is a coax cable.

DEC and Intel joined Xerox to define a 10-Mbps Ethernet standard in

1978.
This standard formed the basis for IEEE standard 802.3
More recently 802.3 has been extended to include a 100-Mbps version
called Fast Ethernet and a 1000-Mbps version called Gigabit Ethernet.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 84

Multiple Access Networks
Ethernet

An Ethernet segment is implemented on a coaxial cable of up to 500 m.

◦ This cable is similar to the type used for cable TV except that it typically has an
impedance of 50 ohms instead of cable TV’s 75 ohms.

Hosts connect to an Ethernet segment by tapping into it.

A transceiver (a small device directly attached to the tap) detects when the
line is idle and drives signal when the host is transmitting.
The transceiver also receives incoming signal.
The transceiver is connected to an Ethernet adaptor which is plugged into
the host.
The protocol is implemented on the adaptor.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 85

Multiple Access Networks
Ethernet

Ethernet transceiver and adaptor

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 86

Multiple Access Networks
Ethernet

Multiple Ethernet segments can be joined together by repeaters.

A repeater is a device that forwards digital signals.
No more than four repeaters may be positioned between any pair of
hosts.
◦ An Ethernet has a total reach of only 2500 m.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 87

Multiple Access Networks

Ethernet

Ethernet repeater

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 88

Multiple Access Networks
Ethernet

Any signal placed on the Ethernet by a host is broadcast

over the entire network
◦ Signal is propagated in both directions.
◦ Repeaters forward the signal on all outgoing segments.
◦ Terminators attached to the end of each segment absorb the signal.

Ethernet uses Manchester encoding scheme.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 89

Multiple Access Networks
Ethernet

New Technologies in Ethernet

◦ Instead of using coax cable, an Ethernet can be constructed from a
thinner cable known as 10Base2 (the original was 10Base5)
◦ 10 means the network operates at 10 Mbps
◦ Base means the cable is used in a baseband system
◦ 2 means that a given segment can be no longer than 200 m

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 90

Multiple Access Networks
Ethernet

New Technologies in Ethernet

◦ Another cable technology is 10BaseT
◦ T stands for twisted pair
◦ Limited to 100 m in length
◦ With 10BaseT, the common configuration is to have several point to
point segments coming out of a multiway repeater, called Hub

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 91

Multiple Access Networks
Ethernet

Ethernet Hub

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 92

Multiple Access Networks
Access protocol for Ethernet

The algorithm is commonly called Ethernet’s Media Access Control

(MAC).
◦ It is implemented in Hardware on the network adaptor.

Frame format
◦ Preamble (64bit): allows the receiver to synchronize with the signal (sequence of
alternating 0s and 1s).
◦ Host and Destination Address (48bit each).
◦ Packet type (16bit): acts as demux key to identify the higher level protocol.
◦ Data (up to 1500 bytes)
◦ Minimally a frame must contain at least 46 bytes of data.
◦ Frame must be long enough to detect collision.
◦ CRC (32bit)

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 93

Multiple Access Networks
Ethernet frame

Ethernet Frame Format

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 94

Multiple Access Networks
Ethernet addresses

Each host on an Ethernet (in fact, every Ethernet host in the world) has
a unique Ethernet Address.
The address belongs to the adaptor, not the host.
◦ It is usually burnt into ROM.

Ethernet addresses are typically printed in a human readable format

◦ As a sequence of six numbers separated by colons.
◦ Each number corresponds to 1 byte of the 6 byte address and is given by a pair of
hexadecimal digits, one for each of the 4-bit nibbles in the byte
◦ Leading 0s are dropped.
◦ For example, 8:0:2b:e4:b1:2 is
◦ 00001000 00000000 00101011 11100100 10110001 00000010

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 95

Multiple Access Networks
Ethernet addresses

To ensure that every adaptor gets a unique address, each

manufacturer of Ethernet devices is allocated a different prefix that
must be prepended to the address on every adaptor they build
◦ AMD has been assigned the 24bit prefix 8:0:20

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 96

Multiple Access Networks
Ethernet addresses

Each frame transmitted on an Ethernet is received by every adaptor

connected to that Ethernet.
Each adaptor recognizes those frames addressed to its address and
passes only those frames on to the host.
In addition, to unicast address, an Ethernet address consisting of all 1s is
treated as a broadcast address.
◦ All adaptors pass frames addressed to the broadcast address up to the host.

Similarly, an address that has the first bit set to 1 but is not the
broadcast address is called a multicast address.
◦ A given host can program its adaptor to accept some set of multicast addresses.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 97

Multiple Access Networks
Ethernet addresses

To summarize, an Ethernet adaptor receives all frames and accepts

◦ Frames addressed to its own address
◦ Frames addressed to the broadcast address
◦ Frames addressed to a multicast addressed if it has been instructed

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 98

Multiple Access Networks
Ethernet transmitter algorithm

When the adaptor has a frame to send and the line is idle, it transmits
the frame immediately.
◦ The upper bound of 1500 bytes in the message means that the adaptor can
occupy the line for a fixed length of time.

When the adaptor has a frame to send and the line is busy, it waits for
the line to go idle and then transmits immediately.
The Ethernet is said to be 1-persistent protocol because an adaptor
with a frame to send transmits with probability 1 whenever a busy line
goes idle.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 99

Multiple Access Networks
Ethernet transmitter algorithm

Since there is no centralized control it is possible for two (or more)

adaptors to begin transmitting at the same time,
◦ Either because both found the line to be idle,
◦ Or, both had been waiting for a busy line to become idle.

When this happens, the two (or more) frames are said to be collide on
the network.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 100

Multiple Access Networks
Ethernet transmitter algorithm

Since Ethernet supports collision detection, each sender is able to

determine that a collision is in progress.
At the moment an adaptor detects that its frame is colliding with
another, it first makes sure to transmit a 32-bit jamming sequence and
then stops transmission.
◦ Thus, a transmitter will minimally send 96 bits in the case of collision
◦ 64-bit preamble + 32-bit jamming sequence

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 101

Multiple Access Networks
Ethernet transmitter algorithm

One way that an adaptor will send only 96 bit (called a runt frame) is if
the two hosts are close to each other.
Had they been farther apart,
◦ They would have had to transmit longer, and thus send more bits, before detecting
the collision.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 102

Multiple Access Networks
Ethernet transmitter algorithm

The worst case scenario happens when the two hosts are at opposite
ends of the Ethernet.
To know for sure that the frame its just sent did not collide with another
frame, the transmitter may need to send as many as 512 bits.
◦ Every Ethernet frame must be at least 512 bits (64 bytes) long.
◦ 14 bytes of header + 46 bytes of data + 4 bytes of CRC

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 103

Multiple Access Networks
Ethernet transmitter algorithm

Why 512 bits?

◦ Why is its length limited to 2500 m?

The farther apart two nodes are, the longer it takes for a frame sent by
one to reach the other, and the network is vulnerable to collision
during this time

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 104

Multiple Access Networks
Ethernet transmitter algorithm

A begins transmitting a frame at time t

d denotes the one link latency
The first bit of A’s frame arrives at B at time t + d
Suppose an instant before host A’s frame arrives, host B begins to transmit its
own frame
B’s frame will immediately collide with A’s frame and this collision will be
detected by host B
Host B will send the 32-bit jamming sequence
Host A will not know that the collision occurred until B’s frame reaches it,
which will happen at t + 2 * d
Host A must continue to transmit until this time in order to detect the collision
◦ Host A must transmit for 2 * d to be sure that it detects all possible collisions

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 105

 Multiple Access Networks

Ethernet transmitter algorithm

Worst-case scenario:
(a) A sends a frame at time t; (b) A’s frame arrives at B at time t + d; (c) B begins transmitting at time t + d and
collides with A’s frame; (d) B’s runt (32-bit) frame arrives at A at time t + 2d.
CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 106
Multiple Access Networks
Ethernet transmitter algorithm

Consider that a maximally configured Ethernet is 2500 m

long, and there may be up to four repeaters between any
two hosts, the round trip delay has been determined to be
51.2 s
◦ Which on 10 Mbps Ethernet corresponds to 512 bits

The other way to look at this situation,

◦ We need to limit the Ethernet’s maximum latency to a fairly small
value (51.2 s) for the access algorithm to work
◦ Hence the maximum length for the Ethernet is on the order of 2500 m.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 107

Multiple Access Networks
Ethernet transmitter algorithm

Once an adaptor has detected a collision, and stopped its

transmission, it waits a certain amount of time and tries again.
Each time the adaptor tries to transmit but fails, it doubles the amount
of time it waits before trying again.
This strategy of doubling the delay interval between each
retransmission attempt is known as Exponential Backoff.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 108

Multiple Access Networks
Ethernet transmitter algorithm

The adaptor first delays either 0 or 51.2 s, selected at random.

If this effort fails, it then waits 0, 51.2, 102.4, 153.6 s (selected randomly)
before trying again;
◦ This is k * 51.2 for k = 0, 1, 2, 3

After the third collision, it waits k * 51.2 for k = 0…23 – 1 (again selected
at random).
In general, the algorithm randomly selects a k between 0 and 2n – 1
and waits for k * 51.2 s, where n is the number of collisions
experienced so far.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 109

Multiple Access Networks
Experience with Ethernet

Ethernets work best under lightly loaded conditions.

◦ Under heavy loads, too much of the network’s capacity is wasted by collisions.
Most Ethernets are used in a conservative way.
◦ Have fewer than 200 hosts connected to them which is far fewer than the maximum of
1024.
Most Ethernets are far shorter than 2500m with a round-trip delay of closer to
5 s than 51.2 s.
Ethernets are easy to administer and maintain.
◦ There are no switches that can fail and no routing and configuration tables that have
to be kept up-to-date.
◦ It is easy to add a new host to the network.
◦ It is inexpensive.
◦ Cable is cheap, and only other cost is the network adaptor on each host.

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 110

Chapter Outline

o7. Summary

CPEN441 - CHAPTER 2: GETTING CONNECTED

Summary

We introduced the many and varied type of links that are used to
connect users to existing networks, and to construct large networks
from scratch.
We looked at the five key issues that must be addressed so that two or
more nodes connected by some medium can exchange messages
with each other
◦ Encoding
◦ Framing
◦ Error Detecting
◦ Reliability
◦ Multiple Access Links
◦ Ethernet

CPEN441 - CHAPTER 2: GETTING CONNECTED Joseph Doumit, PhD 112