Advanced Network Technologies Review
Dr. Wei Bao | Lecturer School of Computer Science
Protocol Stack
application
transport
network
link
physical
› 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”
Internet Protocol Stack: Practice
application
HTTP, FTP, SMTP, DNS, P2P, SIP, RTP, MQTT, CoAP, QUIC
Video/Audio Over TCP/UDP
Multimedia network network Support
Socket
transport
network
TCP, UDP, Transport Protocol MPTCP
Wireless network
link
physical
Internet Protocol Stack: Theory
application
Web with cache: performance (today’s tutorial)
Network Optimization
transport
Max min fairness
TCP delay analysis (assignment 2 Q1)
network
Queueing Theory
Erlang B Example of
Principles Game Theory of
CDMA
SNR vs. BER
link
physical
Internet Protocol Stack: Programming/Experiment
Wireshark
application
transport
CoAP experiment
Socket
Socket programming
network
Queue simulator
link
physical
Internet Protocol Stack
application
HTTP, FTP, SMTP, DNS, P2P
transport
network
link
physical
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
iPhone running Safari browser
server running
Apache Web server
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
TCP control connection, server port 21
FTP TCP data connection, FTP client server port 20 server
Email
user agent
SMTP SMTP
sender’s mail server
mail access protocol
(e.g., POP, IMAP)
user agent
› SMTP: delivery/storage to receiver’s server › mail access protocol: retrieval from server
receiver’s mail 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
DNS
root DNS server
› host at cis.poly.edu wants IP address for gaia.cs.umass.edu
iterated query:
contacted server replies with name of server to contact
“I don’t know this name, but ask this server”
2
3
TLD DNS server
7
.edu DNS server
local DNS server
dns.poly.edu
1 8
requesting host
cis.poly.edu
4
5
6
authoritative DNS server
dns.cs.umass.edu
gaia.cs.umass.edu
DNS
recursive query:
puts burden of name resolution on contacted name server
heavy load at upper levels of hierarchy?
2
7
local DNS server
dns.poly.edu
18
requesting host
cis.poly.edu
3
root DNS server
6
TLD DNS server
5
4
.edu DNS server
authoritative DNS server
dns.cs.umass.edu
gaia.cs.umass.edu
P2P Principle
3.5 3 2.5 2 1.5 1 0.5 0
P2P
Client-Server
0 5 10 15 20 25 30 35 N
13
Minimum Distribution Time
BitTorrent: tit-for-tat
(1) Alice sends chunks to those four peers currently sending her chunks at highest rate
(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 !
1
Circular DHT with shortcuts
1
3
4 5
8
› each peer keeps track of predecessor, successor, short cuts.
Who’s responsible for key 1110 (14) ?
15 12
10
15
Internet Protocol Stack
application
CoAP, MQTT, QUIC
transport
network
link
physical
CoAP
• CoAP provides a request/response interaction like HTTP. • Over UDP.
• GET, PUT, observe
Gateway
Personal area network (PAN) protocol.
Battery powered device providing CoAP. CoAP Communication uses UDP over a
Client
HTTP
MQTT
• 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/
18
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 header
Connection ID
Packet number
Frame
Stream 1 Offset Length
QUIC
Frame
Stream 2 Offset Length
Frame ACK
Frame
Other frame type
Protocol Stack
application
Socket
transport
TCP, UDP, Transport Protocol
network
link
physical
Multiplexing/demultiplexing
multiplexing at sender:
handle data from multiple sockets, add transport header (later used for demultiplexing)
demultiplexing at receiver:
use header info to deliver received segments to correct socket
socket
process
application
P1 P2
transport
network
link
physical
application
P4
transport
network
link
physical
application
P3
transport
network
link
physical
22
UDP
32 bits
length, in bytes of UDP segment, including header
why is there a UDP?
› 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 #
length
checksum
application data
(payload)
UDP segment format
23
Stop and wait
sender
receiver
rcv pkt0 send ack0
rcv pkt1 send ack1
sender
send pkt0 rcv ack0
receiver
pkt0 rcv pkt0 ack0 send ack0
send pkt0 pkt0 rcv ack0 ack0
send pkt1 pkt1X loss
send pkt1 pkt1 rcv ack1 ack1
send pkt0 pkt2
ack2 send ack0
timeout
rcv pkt0
resend pkt1
pkt1
rcv pkt1 ack1 send ack1
pkt2 rcv pkt0 ack2 send ack0
(b) packet loss
(a) no loss
rcv ack1 send pkt0
24
GBN
sender window (N=4)
012345678 012345678 45678 45678
012345678 012345678
sender
receiver
receive pkt0, send ack0 receive pkt1, send ack1
receive pkt3, discard, (re)send ack1
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
send pkt0 send pkt1 send pkt2 send pkt3
0123
0123
012345678 012345678 01 678 01 678
rcv ack0, send pkt4 rcv ack1, send pkt5
ignore duplicate ACK
pkt 2 timeout
send pkt2 send pkt3 send pkt4 send pkt5
Xloss (wait)
2345
2345
25
Selective repeat
sender window (N=4)
012345678 012345678 45678 45678
012345678 012345678
012345678
01 678 01 678 01 678
012345678 0123456789
sender
receiver
receive pkt0, send ack0 receive pkt1, send ack1
receive pkt3, buffer, send ack3
receive pkt4, buffer,
send ack4 receive pkt5, buffer,
send ack5
rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2
send pkt0 send pkt1 send pkt2 send pkt3
0123
0123
Xloss (wait)
rcv ack0, send pkt4 rcv ack1, send pkt5
record ack3 arrived
pkt 2 timeout
send pkt2
record ack4 arrived record ack5 arrived
2345
2345
2345
26
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)
to application process
buffered data
free buffer space
RcvBuffer
rwnd
– many operating systems autoadjust RcvBuffer
› sender limits amount of unacked (“in-flight”) data to receiver’s rwnd value
› guarantees receive buffer will not overflow
TCP segment payloads receiver-side buffering
27
TCP Congestion Control
sender sequence number space
TCP sending rate:
› roughly: send cwnd bytes, wait RTT for ACKS, then send more bytes
cwnd
last byte ACKed
sent, not- yet ACKed (“in- flight”)
last byte sent
› sender limits transmission:
› cwnd is dynamic, function of perceived network congestion
LastByteSent-LastByteAcked < cwnd
rate ~
cwnd RTT
bytes/sec
28
TCP Congestion Control
duplicate ACK dupACKcount++
slow
start/ exponential increase
New ACK!
new ACK
New ACK! .
new ACK
cwnd = cwnd + MSS (MSS/cwnd) dupACKcount = 0
transmit new segment(s), as allowed
Λ
cwnd = 1 MSS ssthresh = 64 KB dupACKcount = 0
timeout
ssthresh = cwnd/2
cwnd = 1 MSS dupACKcount = 0 retransmit missing segment
dupACKcount == 3
ssthresh= cwnd/2 cwnd = ssthresh + 3 retransmit missing segment
cwnd = cwnd+MSS
dupACKcount = 0
transmit new segment(s), as allowed
cwnd > ssthresh
Λ
timeout ssthresh = cwnd/2
congestion avoidance/ additive increase
duplicate ACK dupACKcount++
cwnd = 1 MSS dupACKcount = 0 retransmit missing segment
timeout
ssthresh = cwnd/2
cwnd = 1
dupACKcount = 0 retransmit missing segment
fast recovery/ multiplicative decrease
duplicate ACK
cwnd = cwnd + MSS
New ACK!
New ACK
cwnd = ssthresh dupACKcount = 0
dupACKcount == 3
ssthresh= cwnd/2
cwnd = ssthresh + 3 retransmit missing segment
transmit new segment(s), as allowed
29
TCP round trip time, timeout
› timeout interval: EstimatedRTT plus “safety margin” EstimatedRTT = (1- α)*EstimatedRTT + α*SampleRTT
typical value: α = 0.125 DevRTT = (1-β)*DevRTT +
β*|SampleRTT-EstimatedRTT| (typically, β = 0.25)
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT
“safety margin”
30
Protocol Stack
application
Socket
transport
MPTCP
network
link
physical
MPTCP in Stack
Application
MPTCP
Subflow (TCP)
Subflow (TCP)
IP
https://pocketnow.com/multipath-tcp
MPTCP in Stack
• Initialization: MP_C APABLE, 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.
Internet Protocol Stack
application
Video/Audio SIP, RTP
Over TCP/UDP Network Support
transport
network
link
physical
34
Multimedia networking
constant bit rate video
transmission
client video reception
constant bit rate video
playout at client
variable network delay
Buffer underflow!
Cannot be played on time
client playout delay
time
buffered video
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
High quality
Low 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−α)di-1 + α (ri – ti)
delay estimate small constant, time received – time sent
after ith packet (timestamp)
measured delay of ith packet
Adaptive playout delay
also useful to estimate average deviation of delay, vi vi = (1−β)vi-1 + β |ri – ti – di|
› 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: playout-timei = ti + di + Kvi
Delay jitter
talk spurt 2
…
talk spurt 1
di + Kvi Determine di + Kvi
adjust delay
ri – ti
time
SIP
2. UMass proxy forwards request
to Poly registrar server
23
Poly SIP registrar
3. Poly server returns redirect response, indicating that it should try bob@eurecom.fr
UMass SIP proxy
1. Alice sends INVITE message to UMass
SIP proxy. 1
Alice 128.119.40.186
8
4. Umass proxy forwards request to Eurecom registrar server 4
7
6-8. SIP response returned to Alice
9
9. Data flows between clients
6
5
Eurecom SIP registrar
5. eurecom registrar forwards INVITE to 197.87.54.21, which is running Bob’s SIP client
Bob 197.87.54.21
RTP
payload type
sequence number
time stamp
Synchronization Source ID (SSRC)
Miscellaneous fields
type
• 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.
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)
arrivals
departures
classify link
low priority queue (server)
(waiting area)
2 1345
arrivals
packet in service
departures
1
3
2
4
5
1324 5
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)
2 1345
arrivals
packet in service
departures
1
3
2
4
5
1334 5
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
Wireless network
SNR vs. BER
Principles of
CDMA
physical
46
Wireless Physical layer
› SNR versus BER tradeoffs
– Different physical layer modulation:
10-1 10-2 10-3
10-4 10-5
10-6 10-7
What is the meaning of dB? Normal/Gaussian distribution, Q fucntion Week 9, Assignment 2 Q4
In final exam.
10 20 30 40
SNR(dB)
QAM256 (8 Mbps) QAM16 (4 Mbps)
BPSK (1 Mbps)
BER
CDM A
x
Sender 1
Sender 2 x +
2’s chipping sequence
Inner product(received signal, 1’s chipping sequence)
Inner product(received signal, 2’s chipping sequence)
………
x
Sender N
1’s chipping sequence
N’s chipping sequence
Inner product(received signal, N’s chipping sequence)
Hidden terminal and exposed terminal
A
C
B
Hidden terminal problem
Exposed terminal problem
Mobility via indirect routing
home agent intercepts packets, forwards to foreign agent
wide area
network
1
foreign agent receives packets, forwards to mobile
visited network
home network
3 4
2
correspondent addresses packets using home address of mobile
mobile replies directly to correspondent
Mobility via direct routing
correspondent forwards to foreign agent
foreign agent receives packets, forwards to mobile
visited network
home network
1
2
3 4
correspondent requests, receives foreign address of mobile
mobile replies directly to correspondent
4G LTE
Mobile device (UE)
Mobility Management Entity (MME)
Home Subscriber Service (HSS)
to Internet
PDN gateway (P-GW)
Base station
(eNode-B)
…
Serving Gateway (S-GW)
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
Internet Protocol Stack: Theory
application
Web with cache performance (today’s tutorial)
transport
network
Queueing Theory
Erlang B
link
physical
Queueing System
NQ +ρ= N Number W +X= T Time
• 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
Stationary Distribution Derivation
Transition diagram and balanced equations Stationary distribution
Average # of users
Average waiting time
In final exam.
Internet Protocol Stack
application
transport
network
Max min fairness
link
physical
Max-min fairness
How to judge if max-min fairness is satisfied.
How to find max-min fairness: Bottleneck approach
Each link between two routes with capacity 1 2/3
A 2/3 B 1/3
C 1/3 D 1/3
1/3 1/3
Bottleneck!
1/3
Bottleneck!
Assignment 1 common mistake
Correct solution
Common mistake
Why is it wrong?
Common mistake
P(A and B) = P(A) P(B) is true for independent events.
d1’>rab is happens, -> more likely rab is small -> more likely d2’> rab is also true.
Q: Could you give an example when the above approach is correct? A: rab is a constant. d1’, d2’, d3’, d4’ are independent and thus d1’>rab, d1’>rab, d3’>rab, d4’>rab are independent!
These are not independent events!
Another correct way
Because rab, d1’, d2’, d3’, d4’ are continuous random variable, and independent and they follow the same distribution, (i.i.d. independent and identically distributed), so that they have the same probability, i.e., 1/5, to be the smallest one.
Therefore P(rab >min(d1’, d2’, d3’, d4’) )=4/5
Simple way to verify 4/5
Final exam
› The marks of final exam sum up to 100 and it is worth 60% of your overall mark.
› Online, open book, (type C)
› 130 minutes + buffer time + upload time
› Double-pass policy.
› 7 questions in total.
– Calculation, short answer and extended response
› Type your answers in the blank below, or write down, scan/photograph, and upload in the end.
› Spend time wisely. Question 1 doesn’t mean easiest.
Final exam
›No programming questions ›No Wireshark questions
66
Office hour
› By appointment
– wei.bao@sydney.edu.au
– zhengjie.yang@sydney.edu.au – zwan5430@uni.sydney.edu.au
› Assignment 2 common mistakes and Q&A session – 4-Dec-2020 (Fri), 3pm (tentative), Zoom
– Non-compulsory, no recording
› Last-chance office hour
– 7-Dec-2020 (Mon), 3pm (tentative), Zoom – Non-compulsory, no recording
67
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
› 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
68