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

o5. End-to-End Protocols

CPEN441 – INFORMATION NETWORKING II

Chapter 5: End-to-
End Protocols
We will cover these skills

o Understanding the demultiplexing service

o Discussing simple byte stream protocol

End-to-end Protocols

Common properties that a transport protocol can be

expected to provide
◦ Guarantees message delivery
◦ Delivers messages in the same order they were sent
◦ Delivers at most one copy of each message
◦ Supports arbitrarily large messages
◦ Supports synchronization between the sender and the receiver
◦ Allows the receiver to apply flow control to the sender
◦ Supports multiple application processes on each host

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 5

End-to-end Protocols

Typical limitations of the network on which transport protocol

will operate
◦ Drop messages
◦ Reorder messages
◦ Deliver duplicate copies of a given message
◦ Limit messages to some finite size
◦ Deliver messages after an arbitrarily long delay

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 6

End-to-end Protocols

Challenge for Transport Protocols

◦ Develop algorithms that turn the less-than-desirable properties of the
underlying network into the high level of service required by
application programs

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 7

Chapter Outline

o1. Simple Demultiplexer (UDP)

o2. Reliable Byte Stream (TCP)

o3. Remote Procedure Call

o4. Summary

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS

Chapter Outline

o1. Simple Demultiplexer (UDP)

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS

Simple Demultiplexer (UDP)

Extends host-to-host delivery service of the underlying

network into a process-to-process communication service
Adds a level of demultiplexing which allows multiple
application processes on each host to share the network

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 10

Simple Demultiplexer (UDP)

Format for UDP header (Note: length and checksum fields

should be switched)

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 11

Simple Demultiplexer (UDP)

UDP Message Queue

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 12

Chapter Outline

o2. Reliable Byte Stream (TCP)

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS

Reliable Byte Stream (TCP)

In contrast to UDP, Transmission Control Protocol (TCP) offers

the following services
◦ Reliable
◦ Connection oriented
◦ Byte-stream service

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 14

Reliable Byte Stream (TCP)
Flow control vs Congestion control

Flow control involves preventing senders from overrunning

the capacity of the receivers
Congestion control involves preventing too much data from
being injected into the network, thereby causing switches or
links to become overloaded

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 15

Reliable Byte Stream (TCP)
End-to-end Issues

At the heart of TCP is the sliding window algorithm (discussed

in Chapter 2)
As TCP runs over the Internet rather than a point-to-point link,
the following issues need to be addressed by the sliding
window algorithm
◦ TCP supports logical connections between processes that are
running on two different computers in the Internet
◦ TCP connections are likely to have widely different RTT times
◦ Packets may get reordered in the Internet

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 16

Reliable Byte Stream (TCP)
End-to-end Issues

◦ TCP needs a mechanism using which each side of a connection will

learn what resources the other side is able to apply to the
connection
◦ TCP needs a mechanism using which the sending side will learn the
capacity of the network

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 17

Reliable Byte Stream (TCP)
TCP Segment

TCP is a byte-oriented protocol, which means that the

sender writes bytes into a TCP connection and the receiver
reads bytes out of the TCP connection.

Although “byte stream” describes the service TCP offers to

application processes, TCP does not, itself, transmit individual
bytes over the Internet.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 18

Reliable Byte Stream (TCP)
TCP Segment

TCP on the source host buffers enough bytes from the

sending process to fill a reasonably sized packet and then
sends this packet to its peer on the destination host.
TCP on the destination host then empties the contents of the
packet into a receive buffer, and the receiving process
reads from this buffer at its leisure.
The packets exchanged between TCP peers are called
segments.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 19

Reliable Byte Stream (TCP)

TCP Segment

How TCP manages a byte stream.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 20

Reliable Byte Stream (TCP)

TCP Header

TCP Header Format

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 21

Reliable Byte Stream (TCP)
TCP Header

The SrcPort and DstPort fields identify the source and destination ports,
respectively.
The Acknowledgment, SequenceNum, and AdvertisedWindow fields
are all involved in TCP’s sliding window algorithm.
Because TCP is a byte-oriented protocol, each byte of data has a
sequence number; the SequenceNum field contains the sequence
number for the first byte of data carried in that segment.
The Acknowledgment and AdvertisedWindow fields carry information
about the flow of data going in the other direction.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 22

Reliable Byte Stream (TCP)
TCP Header

The 6-bit Flags field is used to relay control information between TCP
peers.
The possible flags include SYN, FIN, RESET, PUSH, URG, and ACK.
The SYN and FIN flags are used when establishing and terminating a
TCP connection, respectively.
The ACK flag is set any time the Acknowledgment field is valid,
implying that the receiver should pay attention to it.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 23

Reliable Byte Stream (TCP)
TCP Header

The URG flag signifies that this segment contains urgent data. When
this flag is set, the UrgPtr field indicates where the nonurgent data
contained in this segment begins.
The urgent data is contained at the front of the segment body, up to
and including a value of UrgPtr bytes into the segment.

The PUSH flag signifies that the sender invoked the push operation,
which indicates to the receiving side of TCP that it should notify the
receiving process of this fact.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 24

Reliable Byte Stream (TCP)
TCP Header

Finally, the RESET flag signifies that the receiver has become confused,
it received a segment it did not expect to receive—and so wants to
abort the connection.
Finally, the Checksum field is used in exactly the same way as for
UDP—it is computed over the TCP header, the TCP data, and the
pseudoheader, which is made up of the source address, destination
address, and length fields from the IP header.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 25

Reliable Byte Stream (TCP)
Connection Establishment/Termination in TCP

Timeline for three-way handshake algorithm

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 26

Reliable Byte Stream (TCP)
Sliding Window Revisited

TCP’s variant of the sliding window algorithm, which serves several

purposes:
◦ (1) it guarantees the reliable delivery of data,
◦ (2) it ensures that data is delivered in order, and
◦ (3) it enforces flow control between the sender and the receiver.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 27

Reliable Byte Stream (TCP)
Sliding Window Revisited

Relationship between TCP send buffer (a) and receive buffer (b).

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 28

Reliable Byte Stream (TCP)
TCP Sliding Window

Sending Side
◦ LastByteAcked ≤ LastByteSent
◦ LastByteSent ≤ LastByteWritten

Receiving Side
◦ LastByteRead < NextByteExpected
◦ NextByteExpected ≤ LastByteRcvd + 1

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 29

Reliable Byte Stream (TCP)
TCP Flow Control

LastByteRcvd − LastByteRead ≤ MaxRcvBuffer

AdvertisedWindow = MaxRcvBuffer − ((NextByteExpected − 1) −
LastByteRead)
LastByteSent − LastByteAcked ≤ AdvertisedWindow
EffectiveWindow = AdvertisedWindow − (LastByteSent − LastByteAcked)
LastByteWritten − LastByteAcked ≤ MaxSendBuffer
If the sending process tries to write y bytes to TCP, but
(LastByteWritten − LastByteAcked) + y > MaxSendBuffer
then TCP blocks the sending process and does not allow it to generate more
data.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 30

Reliable Byte Stream (TCP)
Protecting against Wraparound

SequenceNum: 32 bits longs

AdvertisedWindow: 16 bits long
◦ TCP has satisfied the requirement of the sliding

◦ window algorithm that is the sequence number

◦ space be twice as big as the window size
◦ 232 >> 2 × 216

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 31

Reliable Byte Stream (TCP)
Protecting against Wraparound

Relevance of the 32-bit sequence number space

◦ The sequence number used on a given connection might wraparound
◦ A byte with sequence number x could be sent at one time, and then at a later
time a second byte with the same sequence number x could be sent
◦ Packets cannot survive in the Internet for longer than the MSL
◦ MSL is set to 120 sec
◦ We need to make sure that the sequence number does not wrap around within a
120-second period of time
◦ Depends on how fast data can be transmitted over the Internet

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 32

Reliable Byte Stream (TCP)
Protecting against Wraparound

Time until 32-bit sequence number space wraps around.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 33

Reliable Byte Stream (TCP)
Keeping the Pipe Full

16-bit AdvertisedWindow field must be big enough to allow the sender

to keep the pipe full
Clearly the receiver is free not to open the window as large as the
AdvertisedWindow field allows
If the receiver has enough buffer space
◦ The window needs to be opened far enough to allow a full
◦ delay × bandwidth product’s worth of data
◦ Assuming an RTT of 100 ms

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 34

Reliable Byte Stream (TCP)
Keeping the Pipe Full

Required window size for 100-ms RTT.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 35

Reliable Byte Stream (TCP)
Triggering Transmission

How does TCP decide to transmit a segment?

◦ TCP supports a byte stream abstraction
◦ Application programs write bytes into streams
◦ It is up to TCP to decide that it has enough bytes to send a segment

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 36

Reliable Byte Stream (TCP)
Triggering Transmission

What factors governs this decision

◦ Ignore flow control: window is wide open, as would be the case when the
connection starts
◦ TCP has three mechanism to trigger the transmission of a segment
◦ 1) TCP maintains a variable MSS and sends a segment as soon as it has collected MSS
bytes from the sending process
◦ MSS is usually set to the size of the largest segment TCP can send without causing local IP to fragment.
◦ MSS: MTU of directly connected network – (TCP header + and IP header)
◦ 2) Sending process has explicitly asked TCP to send it
◦ TCP supports push operation
◦ 3) When a timer fires
◦ Resulting segment contains as many bytes as are currently buffered for transmission

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 37

Reliable Byte Stream (TCP)
Silly Window Syndrome

If you think of a TCP stream as a conveyer belt with “full” containers

(data segments) going in one direction and empty containers (ACKs)
going in the reverse direction, then MSS-sized segments correspond to
large containers and 1-byte segments correspond to very small
containers.
If the sender aggressively fills an empty container as soon as it arrives,
then any small container introduced into the system remains in the
system indefinitely.
That is, it is immediately filled and emptied at each end, and never
coalesced with adjacent containers to create larger containers.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 38

Reliable Byte Stream (TCP)
Silly Window Syndrome

Silly Window Syndrome

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 39

Reliable Byte Stream (TCP)
Nagle’s Algorithm

If there is data to send but the window is open less than MSS, then we
may want to wait some amount of time before sending the available
data
But how long?
If we wait too long, then we hurt interactive applications like Telnet
If we don’t wait long enough, then we risk sending a bunch of tiny
packets and falling into the silly window syndrome
◦ The solution is to introduce a timer and to transmit when the timer expires

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 40

Reliable Byte Stream (TCP)
Nagle’s Algorithm

We could use a clock-based timer, for example one that fires every
100 ms
Nagle introduced an elegant self-clocking solution
Key Idea
◦ As long as TCP has any data in flight, the sender will eventually receive an ACK
◦ This ACK can be treated like a timer firing, triggering the transmission of more data

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 41

Reliable Byte Stream (TCP)
Nagle’s Algorithm

When the application produces data to send

if both the available data and the window ≥ MSS
send a full segment
else
if there is unACKed data in flight
buffer the new data until an ACK arrives
else
send all the new data now

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 42

Reliable Byte Stream (TCP)
Adaptive Retransmission

Original Algorithm
◦ Measure SampleRTT for each segment/ ACK pair
◦ Compute weighted average of RTT
◦ EstRTT =  x EstRTT + (1 -  )x SampleRTT
−  between 0.8 and 0.9

◦ Set timeout based on EstRTT

◦ TimeOut = 2 x EstRTT

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 43

Reliable Byte Stream (TCP)
Original Algorithm

Problem
◦ ACK does not really acknowledge a transmission
◦ It actually acknowledges the receipt of data
◦ When a segment is retransmitted and then an ACK arrives at the sender
◦ It is impossible to decide if this ACK should be associated with the first or the second transmission for calculating RTTs

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 44

Reliable Byte Stream (TCP)
Karn/Partridge Algorithm

Associating the ACK with (a) original transmission versus (b) retransmission

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 45

Reliable Byte Stream (TCP)
Karn/Partridge Algorithm

Do not sample RTT when retransmitting

Double timeout after each retransmission

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 46

Reliable Byte Stream (TCP)
Karn/Partridge Algorithm

Karn-Partridge algorithm was an improvement over the original approach, but it does not eliminate congestion

We need to understand how timeout is related to congestion

◦ If you timeout too soon, you may unnecessarily retransmit a segment which adds load to the network

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 47

Reliable Byte Stream (TCP)
Karn/Partridge Algorithm

Main problem with the original computation is that it does not take variance of Sample RTTs into consideration.

If the variance among Sample RTTs is small

◦ Then the Estimated RTT can be better trusted
◦ There is no need to multiply this by 2 to compute the timeout

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 48

Reliable Byte Stream (TCP)
Karn/Partridge Algorithm

On the other hand, a large variance in the samples suggest that timeout value should not be tightly coupled to the
Estimated RTT

Jacobson/Karels proposed a new scheme for TCP retransmission

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 49

Reliable Byte Stream (TCP)
Jacobson/Karels Algorithm

Difference = SampleRTT − EstimatedRTT

EstimatedRTT = EstimatedRTT + ( alpha × Difference)
Deviation = Deviation + beta (|Difference| − Deviation)
TimeOut = μ × EstimatedRTT + lambda × Deviation
◦ where based on experience, μ is typically set to 1 and lambda is set
to 4. Thus, when the variance is small, TimeOut is close to
EstimatedRTT; a large variance causes the deviation term to
dominate the calculation.

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 50

Chapter Outline

o3. Remote Procedure Call

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS

Chapter Outline

o4. Summary

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS

Summary

We have discussed how to convert host-to-host packet

delivery service to process-to-process communication channel.
We have discussed UDP
We have discussed TCP
We have discussed RPC

CPEN441 - CHAPTER 5: END-TO-END PROTOCOLS Joseph Doumit, PhD 53