Week 13 Review
Advanced Network Technologies
Review
School of Computer Science
Dr. Wei Bao | Lecturer
Protocol Stack
› application: supporting network applications
– FTP, SMTP, HTTP
› transport: process-process data transfer
– TCP, UDP
› network: routing of datagrams from source to
destination
– IP, routing protocols
› link: data transfer between neighboring network
elements
– Ethernet, 802.11 (WiFi)
› physical: bits “on the wire”
application
transport
network
link
physical
Video/Audio
Over TCP/UDP
Multimedia network network Support
Internet Protocol Stack: Practice
application
transport
network
link
physical
HTTP, FTP, SMTP, DNS, P2P,
SIP, RTP, MQTT, CoAP, QUIC
Wireless
network
TCP, UDP, Transport Protocol
MPTCP
Socket
Internet Protocol Stack: Theory
Max min fairness
application
transport
network
link
physical
Network
Optimization
Queueing Theory
Principles
of
CDMA
Example of
Game Theory
Erlang B
Erlang C
SNR vs. BER
Web with cache: performance (assignment 1 Q2)
TCP delay analysis
(assignment 2 Q1)
Linear Block Code
CRC Code
Convolutional Code
Socket programming
Internet Protocol Stack: Programming/Experiment
application
transport
network
link
physical
Wireshark
Queue/Token simulator
Socket
CoAP experiment
Convolutional
code
decoder
Internet Protocol Stack
application
transport
network
link
physical
HTTP, FTP, SMTP, DNS, P2P
HTTP
HTTP: hypertext transfer
protocol
› Web’s application layer
protocol
› client/server model
– client: browser that
requests, receives, (using
HTTP protocol) and
“displays”Web objects
– server: Web server sends
(using HTTP protocol)
objects in response to
requests
PC running
Firefox browser
server
running
Apache Web
server
iPhone running
Safari browser
HTTP requestHTTP response
HT
TP
req
ues
t
HT
TP
res
pon
se
HTTP connections
non-persistent HTTP
› at most one object sent
over TCP connection
– connection then closed
› downloading multiple
objects required multiple
connections
persistent HTTP
›multiple objects can be
sent over single TCP
connection between
client, server
FTP: the file transfer protocol
FTP
client
FTP
server
TCP control connection,
server port 21
TCP data connection,
server port 20
› SMTP: delivery/storage to receiver’s server
› mail access protocol: retrieval from server
– POP: Post Office Protocol [RFC 1939]: authorization, download
– IMAP: Internet Mail Access Protocol [RFC 1730]: more features, including
manipulation of stored msgs on server
– HTTP: Using a browser to access a webmail https://webmail.sydney.edu.au
sender’s mail
server
SMTP SMTP
mail access
protocol
receiver’s mail
server
(e.g., POP,
IMAP)
user
agent
user
agent
requesting host
cis.poly.edu
gaia.cs.umass.edu
root DNS server
local DNS server
dns.poly.edu
1
2
3
4
5
6
authoritative DNS server
dns.cs.umass.edu
7
8
TLD DNS server
› host at cis.poly.edu wants
IP address for
gaia.cs.umass.edu
iterated query:
v contacted server
replies with name of
server to contact
v “I don’t know this
name, but ask this
server”
DNS
.edu DNS server
45
6
3recursive query:
v puts burden of name
resolution on
contacted name
server
v heavy load at upper
levels of hierarchy?
requesting host
cis.poly.edu
gaia.cs.umass.edu
root DNS server
local DNS server
dns.poly.edu
1
2
7
authoritative DNS server
dns.cs.umass.edu
8
DNS
TLD DNS server
.edu DNS server
0
0.5
1
1.5
2
2.5
3
3.5
0 5 10 15 20 25 30 35
N
M
in
im
um
D
is
tr
ib
ut
io
n
T
im
e P2P
Client-Server
P2P Principle
13
(2) Alice randomly unchokes Bob
(3) Alice becomes one of Bob’s top-four providers;
(4) Bob becomes one of Alice’s top-four providers
higher upload rate: find better
trading partners, get file faster !
BitTorrent: tit-for-tat
1
4
(1) Alice sends chunks to those four peers currently sending her chunks at highest rate
Circular DHT with shortcuts
› each peer keeps track of predecessor, successor, short cuts.
15
1
3
4
5
8
10
12
15
Who’s responsible
for key 1110 (14) ?
Internet Protocol Stack
application
transport
network
link
physical
CoAP, MQTT, QUIC
CoAP
Battery powered device providing CoAP.
Communication uses UDP over a
Personal area network (PAN) protocol. Gateway
Client
• CoAP provides a request/response interaction like HTTP.
• Over UDP.
• GET, PUT, observe
HTTP
CoAP
MQTT
18
• MQTT: Lightweight, publish-subscribe network
protocol that transports messages between devices.
• Runs over TCP
• Two types of entities:
• Broker: server receives and forwards messages.
• Client: device connected to broker
https://mqtt.org/
QUIC
Over UDP
Avoid head-of-line blocking.
UDP does not care about
ordering of packet and if
packet get lost.
QUIC is solving this issue
and it will take care of
packet lost in particular
stream.
https://medium.com/faun/http-2-spdy-
and-http-3-quic-bae7d9a3d484
Connection ID
QUIC
Frame
Stream 1
Offset
Length
Frame
Stream 2
Offset
Length
Frame
ACK
Frame
Other
frame
type
QUIC header
Connection
ID
Packet
number
Protocol Stack
application
transport
network
link
physical
TCP, UDP, Transport Protocol
Socket
process
socket
use header info to deliver
received segments to correct
socket
demultiplexing at receiver:handle data from multiple
sockets, add transport header
(later used for demultiplexing)
multiplexing at sender:
transport
application
physical
link
network
P2P1
transport
application
physical
link
network
P4
transport
application
physical
link
network
P3
Multiplexing/demultiplexing
22
› no connection establishment
(which can add delay)
› simple: no connection state at
sender, receiver
› small header size
› no congestion control: UDP
can blast away as fast as
desired
source port # dest port #
32 bits
application
data
(payload)
UDP segment format
length checksum
length, in bytes of
UDP segment,
including header
why is there a UDP?
UDP
23
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt2
pkt1
ack1
ack0
ack2
(a) no loss
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt2
ack1
ack0
ack2
(b) packet loss
pkt1
X
loss
pkt1
timeout
resend pkt1
Stop and wait
24
send pkt0
send pkt1
send pkt2
send pkt3
(wait)
sender receiver
receive pkt0, send ack0
receive pkt1, send ack1
receive pkt3, discard,
(re)send ack1rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
send pkt3
send pkt4
send pkt5
Xloss
receive pkt4, discard,
(re)send ack1
receive pkt5, discard,
(re)send ack1
rcv pkt2, deliver, send ack2
rcv pkt3, deliver, send ack3
rcv pkt4, deliver, send ack4
rcv pkt5, deliver, send ack5
ignore duplicate ACK
0 1 2 3 4 5 6 7 8
sender window (N=4)
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
GBN
25
send pkt0
send pkt1
send pkt2
send pkt3
(wait)
sender receiver
receive pkt0, send ack0
receive pkt1, send ack1
receive pkt3, buffer,
send ack3rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
Xloss
receive pkt4, buffer,
send ack4
receive pkt5, buffer,
send ack5
rcv pkt2; deliver pkt2,
pkt3, pkt4, pkt5; send ack2
record ack3 arrived
0 1 2 3 4 5 6 7 8
sender window (N=4)
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
record ack4 arrived
record ack5 arrived
Selective repeat
26
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8 9
TCP flow control
› receiver “advertises” free buffer
space by including rwnd value in
TCP header of receiver-to-
sender segments
– RcvBuffer size set via socket
options (typical default is 4096
bytes)
– many operating systems autoadjust
RcvBuffer
› sender limits amount of unacked
(“in-flight”) data to receiver’s
rwnd value
› guarantees receive buffer will not
overflow
27
buffered data
free buffer spacerwnd
RcvBuffer
TCP segment payloads
to application process
receiver-side buffering
TCP Congestion Control
› sender limits transmission:
› cwnd is dynamic, function of perceived
network congestion
TCP sending rate:
› roughly: send cwnd
bytes, wait RTT for
ACKS, then send more
bytes
28
last byte
ACKed sent, not-
yet ACKed
(“in-
flight”)
last byte
sent
cwnd
LastByteSent- LastByteAcked < cwnd sender sequence number space rate ~~ cwnd RTT bytes/sec timeout ssthresh = cwnd/2 cwnd = 1 MSS dupACKcount = 0 retransmit missing segment L cwnd > ssthresh congestion
avoidance/
additive
increase
cwnd = cwnd + MSS (MSS/cwnd)
dupACKcount = 0
transmit new segment(s), as allowed
new ACK.
dupACKcount++
duplicate ACK
fast
recovery/
multiplicative
decrease
cwnd = cwnd + MSS
transmit new segment(s), as allowed
duplicate ACK
ssthresh= cwnd/2
cwnd = ssthresh + 3
retransmit missing segment
dupACKcount == 3
timeout
ssthresh = cwnd/2
cwnd = 1
dupACKcount = 0
retransmit missing segment
ssthresh= cwnd/2
cwnd = ssthresh + 3
retransmit missing segment
dupACKcount == 3cwnd = ssthresh
dupACKcount = 0
New ACK
slow
start/
exponential
increase
timeout
ssthresh = cwnd/2
cwnd = 1 MSS
dupACKcount = 0
retransmit missing segment
cwnd = cwnd+MSS
dupACKcount = 0
transmit new segment(s), as allowed
new ACKdupACKcount++
duplicate ACK
L
cwnd = 1 MSS
ssthresh = 64 KB
dupACKcount = 0
New
ACK!
New
ACK!
New
ACK!
TCP Congestion Control
29
TCP round trip time, timeout
› timeout interval: EstimatedRTT plus “safety margin”
30
DevRTT = (1-b)*DevRTT +
b*|SampleRTT-EstimatedRTT|
(typically, b = 0.25)
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT “safety margin”
EstimatedRTT = (1- a)*EstimatedRTT + a*SampleRTT
typical value: a = 0.125
Protocol Stack
application
transport
network
link
physical
MPTCP
Socket
https://pocketnow.com/multipath-tcp
MPTCP in Stack
Application
MPTCP
Subflow
(TCP)
Subflow
(TCP)
IP
MPTCP in Stack
• Initialization: MP_CAPABLE, JOIN,Token
• Sequence number: Subflow sequence number +
data sequence number
• Flow control: Receive window size is for all subflows.
• Congestion control: Updated AIMD for fairness.
Video/Audio
SIP, RTP
Over TCP/UDP
Network Support
Internet Protocol Stack
34
application
transport
network
link
physical
constant bit
rate video
transmission
C
um
ul
at
iv
e
da
ta
time
variable
network
delay
client video
reception constant bit
rate video
playout at client
client playout
delay
bu
ffe
re
d
vi
de
o
Multimedia networking
Buffer underflow!
Cannot be played on time
Streaming multimedia: DASH
Chunk
1
Chunk
2
Chunk
3
… Chunk
N
Chunk
1
Chunk
2
Chunk
3
… Chunk
N
Chunk
1
Chunk
2
Chunk
3
… Chunk
N
Low quality
High quality
Bandwidth
Chunk
1
Chunk
2
Chunk
3
…
Adaptive playout delay
› goal: low playout delay, low delay loss rate
› approach: adaptive playout delay adjustment:
– estimate network delay, adjust playout delay at beginning of each talk
spurt
– silent periods compressed and elongated
› adaptively estimate packet delay: (EWMA – exponentially weighted
moving average):
di = (1-a)di-1 + a (ri – ti)
delay estimate
after ith packet
small constant, time received – time sent
(timestamp)
measured delay of ith packet
(ri – ti)
v also useful to estimate average deviation of delay, vi
Adaptive playout delay
› estimates di, vi calculated for every received packet, but used only
at start of talk spurt
› for first packet in talk spurt, playout time is:
vi = (1-b)vi-1 + b |ri – ti – di|
playout-timei = ti + di + Kvi
C
um
ul
at
iv
e
da
ta
time
Delay jitter
talk spurt 1
adjust
delay
…
talk spurt 2
ri – ti Determine di + Kvi
di + Kvi
1
1. Alice sends INVITE
message to UMass
SIP proxy.
2. UMass proxy forwards request
to Poly registrar server
2 3. Poly server returns redirect response,
indicating that it should try
3
5. eurecom
registrar
forwards INVITE
to 197.87.54.21,
which is running
Bob’s SIP client
5
4
4. Umass proxy forwards request
to Eurecom registrar server
8
6
7
6-8. SIP response returned to
Alice
9
9. Data flows between clients
UMass
SIP proxy
Poly SIP
registrar
Eurecom SIP
registrar
Bob
197.87.54.21
Alice
128.119.40.186
SIP
• payload type (7 bits): indicates type of encoding currently
being used.
• sequence # (16 bits): increment by one for each RTP
packet sent
• timestamp field (32 bits long): sampling instant of first byte
in this RTP data packet
• Sequence + timestamp： packet loss or new talk spurt.
payload
type
sequence
number
type
time stamp Miscellaneous
fields
RTP
Synchronization
Source ID (SSRC)
Scheduling policies: priority
priority scheduling: send
highest priority queued packet
non-preemptive
› multiple classes, with different
priorities
– class may depend on marking
or other header info, e.g. IP
source/dest, port numbers, etc.
– real world example?
high priority queue
(waiting area)
low priority queue
(waiting area)
arrivals
classify
departures
link
(server)
1 3 2 4 5
5
5
2
2
1
1
3
3 4
4
arrivals
departures
packet
in
service
Scheduling policies (con’t)
Round Robin (RR) scheduling:
› multiple classes, with equal priority
› cyclically scan class queues, sending one complete packet from
each class (if available)
1 23 4 5
5
5
2
3
1
1
3
3 4
4
arrivals
departures
packet
in
service
Scheduling policies (con’t)
Weighted Fair Queuing (WFQ):
› Each class i is assigned a weight wi
› Guarantee: if there are class i packets to send (during some interval) then
class i receives a fraction of service which is
wi / ( ∑wj )
› On a link with transmission rate R, class i achieves throughput
Rwi / ( ∑wj )
Policing mechanisms: implementation
token bucket: limit input to specified burst size and average rate (useful to police
the flow)
› bucket can hold b tokens
› a packet must remove a token from bucket to be transmitted into the network
› tokens generated at rate r token/sec unless bucket full (token ignored)
› over interval of length t: number of packets admitted less than or equal to (rt + b)
› Token-generation rate r limits the rate at which packets enter the network
Internet Protocol Stack
application
transport
network
link
physical
Wireless
network Principles
of
CDMA
SNR vs. BER
Linear Block Code
CRC Code
Convolutional Code
Wireless Physical layer
› SNR versus BER tradeoffs
– Different physical layer modulation:
10 20 30 40
QAM256 (8 Mbps)
QAM16 (4 Mbps)
BPSK (1 Mbps)
SNR(dB)
B
ER
10-1
10-2
10-3
10-5
10-6
10-7
10-4
What is the meaning of dB?
Normal/Gaussian distribution, Q fucntion
Week 9, Assignment 2 Q4
In final exam.
CDMA
+
Inner product(received signal,
1’s chipping sequence)
Sender 1
Sender 2
…
Sender N
1’s chipping
sequence
2’s chipping
sequence
N’s chipping
sequence
…
x
x
x
Inner product(received signal,
2’s chipping sequence)
Inner product(received signal,
N’s chipping sequence)
…
Hidden terminal and exposed terminal
A
B
C
Hidden terminal problem Exposed terminal problem
Mobility via indirect routing
wide area
network
home
network
visited
network
3
2
4
1
correspondent
addresses packets
using home address of
mobile
home agent intercepts
packets, forwards to
foreign agent
foreign agent
receives packets,
forwards to mobile
mobile replies
directly to
correspondent
1 2
3
4
Mobility via direct routing
home
network
visited
network
correspondent
requests, receives
foreign address of
mobile
correspondent forwards
to foreign agent
foreign agent
receives packets,
forwards to mobile
mobile replies
directly to
correspondent
4G LTE
Mobility
Management
Entity (MME)
Serving Gateway (S-GW)
Home Subscriber Service
(HSS)
PDN gateway (P-GW)
…
to
Internet
Mobile device
(UE)
Base station
(eNode-B)
Wireless, mobility: impact on higher layer protocols
› logically, impact should be minimal …
– best effort service model remains unchanged
– TCP and UDP can (and do) run over wireless, mobile
› … but performance-wise:
– packet loss/delay due to bit-errors (discarded packets, delays for link-layer
retransmissions), and handoff
– TCP interprets loss as congestion, will decrease congestion window un-necessarily
Bit Check in Matrix format
Linear Block Code
dataword generator matrix codeword
identity submatrix parity submatrix
dG=c
1*k vector k*n matrix 1*n vector
𝑐! 𝑐” 𝑐#
1 0 0 1 1 1 0
0 1 0 0 1 1 1
0 0 1 1 1 0 1
= 𝑐! 𝑐” 𝑐# 𝑐! + 𝑐# 𝑐! + 𝑐” + 𝑐# 𝑐! + 𝑐” 𝑐” + 𝑐#
Decode:
cHT=dGHT =0
Not 0? Error detected.
CRC
D=101110 G=1001
Step 1 Left shift 101110 3 bits
101110000
Generate D.2r
Given D, GBegin
Implementation Math Explanation
Step 2 Remainder[101110000/1001]=011 R= remainder [D.2r /G]
Step 3 To send: 101110 011 D.2r +R
Remainder [101110 011/1001]=0 D.2r +R is divisible by G
Step 5 Receiver: check if the received
bits are divisible by 1001
D.2r +R is divisible by G
there is no error
Generator r+1 bits
Left shift r bits
Internet Protocol Stack: Theory
application
transport
network
link
physical
Queueing Theory
Erlang B
Erlang C
Web with cache performance
Max min fairness
Example of
Game Theory
Example of Game Theory
User 1
User 2
1’s decision
(1, 2) utility
2’s decision
Transmit Keep silent
Transmit (-5,-5) (0,15)
Keep silent (15,0) (0,0)
1
1
0
p2
p1
p1=3/4
p2=3/4
Three equilibria
Pure strategy
Pure strategy
Mixed strategy
Max-min fairness
A
B
C
D
How to judge if max-min fairness is satisfied.
How to find max-min fairness: Bottleneck approach
2/3
1/3
1/3
1/3
1/3
1/3
1/3
Bottleneck!
Bottleneck!
2/3
Each link between two routes with capacity 1
Queueing System
• W: average waiting time in queue
• X: average service time
• T: average time spent in system (T = W + X)
• NQ = average number of customers in queue
• ρ = utilization = average number of customers in service
• N = average number of customer in system (N = NQ + ρ)
• Want to show later: N = λT (Little’s theorem)
• λ Average arrival rate
NQ
W X
ρ N
T
Number
Time+
+
=
=
Stationary Distribution Derivation
Transition diagram and balanced equations
Stationary distribution
Average # of users
Average waiting time
In final exam.
λ λ λ λ λ
2μ kμ (S －1)μ Sμ3μ
M/M/m/m ……
μ
(m=S)
M/M/m/m Queue Model
Q: What is the probability if a new arrival is dropped?
PS
Poisson arrival sees time average.
∑Sn=0(λ /μ)n / n!
(λ /μ)S / S!
Erlang B Formula
Erlang B formula
PS =
Erlang B formula, or Erlang loss formula, the formula for
the blocking probability
PS is also called grade of service (GOS).
Traffice Intensity in Erlangs
Number ofChannels
Erlang B chart
log-log chart
Erlang C
An arriving unit will need to wait if all servers are busy
(it is not blocked)
Examples: Call centers
M/M/m queue
λ λ λ λ λ
2μ kμ (S －1)μ Sμ3μ
M/M/m
……
μ
(m=S) S+1 S+2 …
Sμ Sμ
λ λ λ
Sμ
Erlang C
Pw: The probability that a new arrival has to wait (cannot be
served immediately).
λ λ λ λ λ
2μ kμ (S －1)μ Sμ3μ
M/M/m
……
μ
(m=S) S+1 S+2 …
Sμ Sμ
λ λ λ
Sμ
Pw =∑∞n=SPn
Erlang C
Pw: The probability that a new arrival has to wait (cannot be
served immediately). Erlang C formula
Pw =∑∞n=SPn
Pw =
∑S-1n=0(λ /μ)
n
(λ /μ)S
S!
S
S- λ / μ
n!
(λ /μ)S
S!
S
S- λ / μ
+
Pw is grade of service (GOS).
Erlang C Chart
Assignment 1
Final exam
› The marks of final exam sum up to 100 and it is worth 60% of
your overall mark.
› Online, take-home short release, (type D)
› 130 minutes + upload time
› Double-pass policy.
› 7 questions in total.
– Calculation, short answer, and extended response
– 7th question is a bonus question
› Type into a document or write on a paper and then scan;
Combine all your answers in a single pdf and upload
› Spend time wisely. Question 1 doesn’t mean easiest.
Final exam
›No programming questions
›No Wireshark questions
74
Office hour
› By appointment
– wei. .au
– zhengjie. .au
– .edu.au
› Assignment 2 Q&A, other Q&A session
– 17-Nov (Wed), 6pm (tentative), Zoom
– Non-compulsory, no recording
› Last-chance office hour
– 19-Nov (Fri), 3pm (tentative), Zoom
– Non-compulsory, no recording
75
mailto:wei. .au
mailto:zhengjie. .au
mailto: .edu.au
Survey
› Unit of Study Surveys (USS) for Semester 2 are now open!
› Login to the University’s Student Survey System now to complete a
survey:
› https://student-surveys.sydney.edu.au/students/complete/
› Survey completed will give them an entry into a prize draw to win a range
of Apple products including a 64gb Apple iPad Air, an Apple Watch and JB
HiFi Gift Cards
76
https://student-surveys.sydney.edu.au/students/complete/