Week 11 mobile entwork analysis advanced protocols
Advanced Network Technologies
Mobile Network Analysis, Bit Error Detection and Correction
School of Computer Science
Dr. Wei Bao | Lecturer
Bit Error Detection and Recovery
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
q Error detection not 100% reliable!
o protocol may miss some errors, but rarely
o larger EDC field yields better detection and correction
otherwise
f(D)=EDC f(D’)=EDC’?
Cyclic Redundancy Check (CRC)
› d data bits
› r CRC bits
› Sender: send d+r bits
› Receiver: check d+r bits
› Q: How to design the r bits?
Cyclic Redundancy Check (CRC)
› Binary, modulo 2 domain
› addition, subtraction
– 1+1=0, 1-1=0,
– 1+0=1, 1-0=1
– 0+1=1, 0-1=1
– 0+0=0, 0-0=0
› “-”, “+”, are equivalent to, XOR, Å
› 11+11=00: no carry over
› Multiplication
– 11*100=11*22=1100 (left shift 2 bits)
– 11*11=11*10+11*1=110+11=101
Cyclic Redundancy Check (CRC)
r Division
Cyclic Redundancy Check (CRC)
› view data bits, D, as a binary number
› choose r+1 bit pattern (generator), G
› goal: choose r CRC bits, R, such that
–
– receiver knows G, divides
detected!
– can detect all burst errors less than r+1 bits
› widely used in practice (Ethernet, 802.11 WiFi)
CRC Example
Goal:
D.2r + R divisible by G
Approach:
Divide D.2r by G, get remainder R
D.2r + R = D.2r – R = D.2r Å R ,
divisible by G
D.2r Å R is what we want
R = remainder[ ]D
.2r
G
Example : D = 101110, G=1001
CRC coded: 101110011
Note: remainder[101110011/1001]=0
CRC Example
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
Pag
e9
Convolution Encoder and Viterbi Decoder
› k number of message symbols
› n number of codeword symbols
› r rate = k/n
› K number of input symbols used by encoder to compute each output
symbol (decoding time exponentially dependent on K)
Pag
e10
Convolution Encoder
flip flop
(stores one bit) k = 15, n = 30, r = ½, K = 3
output upper input followed by
lower input
Pag
e11
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
Pag
e12
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
…1 1 1 0 1 0 0 0
1 1 1
1 0 1
0
0
Pag
e13
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
…0 1 1 1 0 1 0 0
1 1 1
1 0 1
1
1
Pag
e14
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
… 0 0 1 1 1 0 1 0
1 1 1
1 0 1
1
0
Pag
e15
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
… 1 0 0 1 1 1 0 1
1 1 1
1 0 1
0
0
Pag
e16
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
1 0 0
1 1 1
1 0 1
1
1
Pag
e17
Encoding Example
Input: 010111001010001
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
Both flip flops set to 0 initially.
1 0 0
1 1 1
1 0 1
0
0
Pag
e18
Encoding Example
010111001010001 ⊛ 1 1 1
Output: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11
1 1 1 and 1 0 1 are two generators.
Convolution operation is performed: Input ⊛ Generator
1 1 1
1 0 1
010111001010001 ⊛ 1 0 1
Pag
e19
State Transitions of the two Flip Flops
input symbol is 1
input symbol is 0
arcs labeled with output symbols
Pag
e20
Decoding (errors exisit)
Errors: 00 11 11 00 01 10 01 11 11 10 00 00 11 00 11
(min # of inconsistent output bits)
Trying to find the input sequence who
corresponding output matches the
received output as closely as possible.
Pag
e21
Viterbi Decoding – Accumulated Error Metric
(min # of inconsistent output bits)
Trying to find the
input sequence who
corresponding output
matches the received
output as closely as
possible.
Pag
e22
Accumulated Error Metric
Pag
e23
Decoder Trellis
Pag
e24
Decoder Trellis
Pag
e25
Decoder Trellis
Pag
e26
Final Decoder Trellis
Pag
e27
Origin of Viterbi Decoding
› Complexity O(S2k)
› S: number of states, k size of input
› Disadvantage S = 2K-1, K-1 (number of flip flop stores), K (Size of
Generator)
› Andrew J. Viterbi, “Error Bounds for Convolutional Codes and an
Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on
Information Theory, Volume IT-13, pp. 260-269, April 1967.
› Viterbi is a founder of Qualcomm.
QUIC
Quick UDP Internet Connections
RFC 9000
Experimental protocol, deployed at Google starting in
2014
○ Between Google services and Chrome
○ Improved page load latency, video rebuffer rate
○ Successful experiment today
○ ~35% of Google’s egress traffic (~7% of Internet
traffic)
○ Akamai deployment in 2016
QUIC Work Group formed in Oct 2016
○ Modularize and standardize QUIC in parts
○ HTTP as initial application
May 2021: RFC 9000
QUIC history
QUIC overview
https://www.ietf.org/proceedings/98/sli
des/slides-98-edu-sessf-quic-tutorial-
00.pdf
Built-in security (and performance)
https://blog.cloudflare.com/the-road-to-quic/
Head-of-line blocking
Multiple streams of data to reach all the endpoints
independently, and hence independent of packet
losses involving other streams.
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
Connection ID
Connection ID: identifier that is used to identify
a QUIC connection
Review:
TCP uses (source IP, destination IP, source port
number, destination port number) to identify socket.
UDP uses (destination IP, destination port number) to
identify socket.
What happens device is migrated (e.g., from 4G to
WiFi)
Connection ID for smooth handover.
Packet Number and Offset
Packet number: monotone, non-repeating
Offset + length: Protect the order of the stream
Packet is lost: Application decides if retransmit the lost
frames.
Loss detection separates from loss recovery
Other frame types
Examples:
MAX_STREAM_DATA: connection level flow control
MAX_DATA: stream level flow control
PING/PONG: to verify that their peers are still alive
CONNECTION_CLOSE: the connection is being closed.
Connection-level and stream-level flow control
Congestion control
• Similar to TCP but more advanced.
• Monotone packet number: No RTT estimation
ambiguity if packet is lost.
• Timeout:
smoothed_rtt + max(4*rttvar, kGranularity) +
max_ack_delay
kGranularity: timer granularity, 1ms
max_ack_delay: the maximum amount of time by which the
receiver intends to delay acknowledgments for packets
Congestion control
• Slow start
• Congestion avoidance (linear increase).
• Recovery period (halve window size).
• Loss detection:
• By ACK (similar to 3 duplicate ACKs)
• By timeout
• Loss causes recovery
• Persistent Congestion causes “slow start” (RFC 9002)
• A sender establishes loss of all in-flight packets sent over a
long enough duration, the network is considered to be
experiencing persistent congestion.
CoAP
Constrained Application Protocol
IETF RFC 7252
CoAP for IoT
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.
• Smaller messages than HTTP and with very low overhead.
• Suitable for IoT devices (sensors and actuators) with limited memory and storage.
• For example, to obtain a current temperature, send a GET request.
• To turn on/off or toggle LEDs we use PUT requests.
HTTP
CoAP
CoAP
CoAp
› Has a scheme coap://
› Based on UDP.
› Has a well known port.
› GET, PUT, DELETE
› Confirmable messages (CON) requires an ACK with message ID. The message ID
of the ACK matches the message ID of the confirmable message.
› Non-confirmable (NON) messages do not require an ACK. Less reliable.
› Responses are matched with requests via the client generated Token.
› Example:
CoAP Client CoAP Server
—-> CON {id} GET /basement/light Confirmable request has an ID
<---- ACK {id} 2.05 Content {“status” : “on”} Piggy back response and same ID CoAP message types › CoAP supports different message types: - Confirmable (CON) - Reliable message, need ACK. CON and ACK have the same ID. - Non-confirmable - No need ACK - Acknowledgment - Reset - Server has troubles managing the incoming request. CoAP Uses Timeouts over UDP CoAP Client CoAP Server ----> CON {id} GET /basement/light lost request
timeout
— –> CON {id} GET /basement/light finally arrives
<---- ACK {id} Content {“status” : “on”}
The {id} allows us to detect duplicates.
CoAP Request/Acknowledge/Callback
CoAP Client CoAP Server
----> CON {id} PUT /basement/cleanFloor Token: 0x22 Needs time
<---- ACK {id} I am on it! <----- CON {newID} Content /basement/cleanFloor Token: 0x22 Done ----> ACK {newID}
The same token is used to identify this request and the service response.
Cache
Max-Age option
indicates cache lifetime
https://community.arm.com/cfs-file/__key/telligent-evolution-components-
attachments/01-1996-00-00-00-00-53-31/ARM-CoAP-Tutorial-April-30-2014.pdf
Block-Wise Transfer
nr: block number.
m: more block
indicator.
sz: size
block1: for request.
block2: for
response.
https://community.arm.com/cfs-file/__key/telligent-evolution-components-
attachments/01-1996-00-00-00-00-53-31/ARM-CoAP-Tutorial-April-30-2014.pdf
CoAP Publish/Subscribe
CoAP Client CoAP Server
—-> CON GET /basement/light Observe: 0 Token: 0x22 Registration
<---- ACK Observe: 27 Token 0x22 Current state
<---- CON Observe: 28 Token: 0x22 {“light” : ”off”}
-----> ACK Token: 0x22
<---- CON 200 Observe: 29 Token: 0x22 {“light” : ”on”} Notification of stage change -----> ACK Token: 0x22
The GET includes an “Observe” message to establish a subscription request.
The response includes an “Observe” to say this is a publication.
The value included with Observe response is there for possible re-orderings.
Token matches
CoAP Resource Discovery
CoAP Client CoAP Server
—-> CON {id} GET /.well-known/core
<---- ACK {id} Content “/sensor/temp /sensor/light”
----> CON {id} GET /sensor/light
<---- ACK {id} Content “dim”
----> CON {id} GET /sensor/temp
<---- ACK {id} Content “72”
CoAP Packet Format
Version (VER)
Indicates the CoAP version number.
Type (2 bits)
Request
0 : Confirmable : This message expects a corresponding Acknowledgement message.
1 : Non-confirmable : This message does not expect a confirmation message.
Response
2 : Acknowledgement : This message is a response that acknowledge a confirmable message
3 : Reset : This message indicates that it had received a message but could not process it.
Token Length (4 bits)
Indicates the length of the variable-length Token field
Request/Response Code (8 bits)
For example 2.05 Content similar to HTTP 200. 4.00 Bad request
Message ID (16 bits)
Token
REST (Representational state transfer)
A set of operations to be used for creating Web services
Server provides access to resources and client accesses and modifies the
resources: stateless operations.
GET: read information
PUT: update information
POST: create information
DELETE: delete information
Both HTTP and CoAP are based on REST.
MQTT
Message Queuing Telemetry Transport
ISO/IEC 20922
MQTT
54
MQTT: Lightweight, publish-subscribe network protocol that transports
messages between devices.
Runs over TCP/IP
For IoT networks
Two types of entities:
Broker: server receives and forwards messages.
Client: device connected to broker
Purpose: publish-subscribe information.
https://mqtt.o
rg/
MQTT Topics
Information is organized as topics.
Publish
Subscriber subscribes topics.
Publisher has a new item of data to distribute.
Publisher sends to broker.
Broker distributes to clients subscribed to the topic.
Publisher does not need to know number/location of the
subscribers.
Subscriber does not need to configure publishers.
MQTT Topics
Topics are structured in hierarchy, using / as delimiter
e.g.,house/room1/maindoor
Wildcard for multiple topics
# multiple-level topics must be in the end
house/#
house/room1/maindoor
house/room1/window
house/room2/maindoor
house/room2/window
house/maindoor
+ single-level topics
house/+/maindoor
house/room1/maindoor
house/room2/maindoor
MQTT Packet
Fixed header
MQTT Packet
Type:
CONNECT: connection request
CONNACK: connection ACK
PUBLISH: publish message
SUBCRIBE: subscribe request
SUBACK: subscribe ACK
UNSUBSCRIBE: unsubscribe request
UNSUBSCRIBEACK: unsubscribe ACK
others
Flag: mostly reserved.
For PUBLISH packets, it contains duplicate transmission flag and QoS level.
Remaining length:
Length of the packet (variable header + payload)
Variable Header
MQTT QoS level
Data loss can sill occur if TCP connection is down and messages in
transit is lost.
QoS 0: At most once - the message is sent only once and the client
and broker take no additional steps to acknowledge delivery (fire and
forget).
e.g., temperature sensor
QoS 1: At least once - the message is re-tried by the sender multiple
times until acknowledgement is received (acknowledged delivery).
e.g., door sensor (status of door)
QoS 2: Exactly once - the sender and receiver engage in a two-level
handshake to ensure only one copy of the message is received
(assured delivery).
e.g., smoke sensor (alarm signal)
MQTT QoS level
QoS 0: At most once - the message is sent only once and the client
and broker take no additional steps to acknowledge delivery (fire and
forget).
https://www.hivemq.com/blog/mqtt-essentials-part-6-mqtt-quality-of-service-levels/
MQTT QoS level
QoS 1: At least once - the message is re-tried by the sender multiple
times until acknowledgement is received (acknowledged delivery).
https://www.hivemq.com/blog/mqtt-essentials-part-6-mqtt-quality-of-service-levels/
MQTT QoS level
QoS 2: Exactly once - the sender and receiver engage in a two-level
handshake to ensure only one copy of the message is received.
PUBREC: publication received.
PUBREL: publication released.
PUBCOM: publication completed.
(Other MQTT packet types.）
https://www.hivemq.com/blog/mqtt-essentials-part-6-mqtt-quality-of-service-levels/
MPTCP
Multi-path TCP
IETF RFC 6824 (older version)
IETF RFC 8684 (latest version)
https://pocketnow.com/multipath-tcp
MPTCP in Stack
Application
MPTCP
Subflow
(TCP)
Subflow
(TCP)
IP
Different IP addresses for different subflows.
SYN+Option
SYN+ACK+Optio
n
ACK
SYN+OtherOption
SYN+ACK+OtherOption
ACK
Option Field
Token
MyToken=5678
YourToken=6543
SYN, Portsrc=1234,Portdst=80
+Option[Token=5678]
SYN+ACK+Option[Token=6543]
ACK
MyToken=6543
YourToken=5678
SYN, Portsrc=1235,Portdst=80
+Option[Token=6543]
…
SYN
MP_CAP
ABLE
Initiation and Join
SYN/ACKMP_CAPABLE
Initiation and Join
Initiation and Join
SYN
JOIN
Initiation and Join
SYN/A
CK
JOIN
Initiation and Join
MPTCP sequence numbers
• MPTCP uses a Data Sequence Number (DSN) to
number all data sent over the MPTCP connection.
• Each subflow has its own sequence number space.
Host A Host B
Address A1 Address A2
SEQ: 1400, DSN: 19600
ACK: 1401, DA: 19601
SEQ: 1401, DSN: 19601
SEQ: 7001, DSN: 19602
Address B1
ACK: 1402, DA: 19602
ACK: 1403, DA: 19604
SEQ: 1402, DSN: 19603
1400 1401 1402 1400 1401 1402
7002
ACK: 7002, DA: 19603
SEQ: 7002, DSN: 19604
ACK: 7003, DA: 19605
1960
0
19601 1960
2
1960
3
1960
4
1960
0
19601 1960
2
1960
3
1960
4
700170027001
DSN
subflow1
subflow2
DSN
subflow1
subflow2
http://www.cis.udel.edu/~amer/856/mptcp.12f.pptx
MPTCP sequence numbers
If one subflow fails, the
other subflow can be used
for retransmission.
source port # dest port #
application
data
(variable length)
sequence number
acknowledgement number
receive window
Urg data pointerchecksum
Codehead
len
not
used
options (variable length)
MPTCP sequence numbers
Subflow source port # Subflow dest port #
application
data
(variable length)
Subflow sequence number
Subflow acknowledgement number
receive window
Urg data pointerchecksum
head
len
not
used
Data sequence number
Data acknowledge number
Other options
Code
Flow Control
Receive Window: The receive window in the TCP header
indicates the amount of free buffer space for the whole
data-level connection (as opposed to the amount of space for
this subflow) that is available at the receiver.
Congestion Control
Can we run regular TCP congestion control on each subflow?
No. Not fair.
MPTCP should take as much capacity as TCP at a bottleneck link,
no matter how many subflows MPTCP is using.
A MPTCP with
two subflows
A regular TCP
Congestion Control
For each ACK received on subflow i, increase cwnd_i by
𝑚𝑖𝑛
𝛼 & 𝑏𝑦𝑡𝑒𝑠_𝑎𝑐𝑘𝑒𝑑 & 𝑀𝑆𝑆!
𝑐𝑤𝑛𝑑"#"$%
,
𝑏𝑦𝑡𝑒𝑠_𝑎𝑐𝑘𝑒𝑑 & 𝑀𝑆𝑆!
𝑐𝑤𝑛𝑑!
𝛼 = 𝑐𝑤𝑛𝑑"#"$% &
𝑚𝑎𝑥! ⁄𝑐𝑤𝑛𝑑! 𝑅𝑇𝑇!
&
∑! ⁄𝑐𝑤𝑛𝑑! 𝑅𝑇𝑇!
&
α: aggressiveness of the multipath flow
bytes_acked: number of bytes newly acknowledged
cwnd_total: sum of the congestion windows of all subflows
(need to use ssthresh_i instead of cwnd_i if subflow is in fast retransmission)
RTT_i: round-trip time (smoothed round-trip time estimate used by TCP) of subflow i.
MSS_i: maximum segment size on subflow i
cwnd_i: congestion windows of subflow i
For each packet loss, halve the window size cwnd_i
More details: see RFC 6356