Congestion Detection inLossless Networks
Yiran Zhang, Yifan Liu, Qingkai Meng, Fengyuan Ren

Tsinghua University

To appear at SIGCOMM’21

Lossless Network• Lossless network has become an attractive trend in many application
scenarios
HPC

Distributed
Storage

Data Center
Applications

Lossless Network2

Drop-free Hop-by-Hop Flow Controls• Converged Enhanced Ethernet (CEE): Priority Flow Control (PFC)
Upstream Port

Downstream Port
Data
PAUSE
RESUME

Xoff Xon

3

Drop-free Hop-by-Hop Flow Controls• InfiniBand: Credit-based Flow Control (CBFC)
Upstream Port

FCCL

FCTBS

Data

FCCLDownstream Port

Buffer size

ABR

4

Drop-free Hop-by-Hop Flow Controls
PFCCBFC

The switch ports alternate between sending (ON) andpausing (OFF) to guarantee the drop-free property

5End-to-end Congestion Control• To mitigate the side-effects of hop-by-hop flow controls:
Head-of-line blocking,Unfairness,
Deadlock..

6

End-to-end Congestion Control• To mitigate the side-effects of hop-by-hop flow controls:
Head-of-line blocking,Unfairness,
Deadlock..

The cornerstone of end-to-end congestion control:

Congestion Detection
7

Existing Congestion Detection Mechanisms
CEE

InfiniBand

Congestion management developedby Data Center Bridging Task Group:• Congestion Point (CP) for
congestion detection• Reaction Point (RP) for ratecontrol.

InfiniBand Specification specifies theframework of congestion control:• The switch detects congestion• Channel Adapter (CA) conducts
injection throttling.

8

Existing Congestion Detection Mechanisms
CEE
DCQCN detects congestion basedon queue size :• CP marks packets with ECN
according to RED algorithm.
• A single bit ECN marking indicatesthe presence of congestion.

InfiniBand
IB CC combines credits informationand queue size to detect congestion :• If the queue of an output port
exceeds a threshold and there areavailable credits to send packets (i.e.,packets are not delayed due to lackof credits), marks packets with
Forward ECN.

9

Lossless networks
Hop-by-hop Flow Controls

Congestion Detection

Interaction?
10

Experimental observations• Simulations under typical network scenarios○ Topology: a common unit in the multi-rooted topology. 40Gbps, 4us link delay.
○ DCQCN (for CEE), IB CC (for InfiniBand)

64KB concurrent burst
11Interaction: single congestion point scenario• Congestion point: P3• Congested flow: F1S0F0F1S1S2F2T0P0L0T2P2P3T1R0R1BurstP1

A0 ... A14

F0 = F2 = 5Gbps

12

Interaction: single congestion point scenario• P2 congestion detection behavior:Queuelength (KB)

F0 and F2 are not congested

F0 and F2 are mistakenly
marked as congested

Markedpackets

CEE

13

Interaction: single congestion point scenario• P2 congestion detection behavior:Queuelength (KB)

F0 and F2 are not congested

F0 and F2 are mistakenly
marked as congested

Markedpackets

InfiniBand

14

Interaction: single congestion point scenario• P2 sending pattern:

F0 and F2 are not congested
Sendingrate (Gbps)
ON-OFF à Continuous ONCEE

InfiniBand15

Interaction: single congestion point scenario
In CEE, queue-based congestion detection alone is essentiallyinadequate.
With only queue length information, ECN can not distinguish between
queue buildup caused by congestion and PAUSEs.
•OFF16

Interaction: single congestion point scenario
In CEE, queue-based congestion detection alone is essentiallyinadequate.
With only queue length information, ECN can not distinguish between
queue buildup caused by congestion and PAUSEs.
•Check queue lengthON

17

Interaction: single congestion point scenario
In InfiniBand, periodical updated credits of CBFC also confuse
congestion detection.
The ports affected by CBFC can also receive a few credits periodically.
Packets arriving after the arrival of new credits may be perceived to havesufficient credits to send out.
•Credits
18

Interaction: multiple congestion points scenario• Congestion points: P2 and P3.
• Congested flows: F0, F1, F2
S0F0F1S1S2F2T0P0L0T2P2P3T1R0R1BurstP1A0 ... A14

F0 = F2 = 25Gbps

19

Interaction: multiple congestion points scenario• P2 sending pattern:

F0 and F2 are congestedSending
rate (Gbps)
ON-OFF à Continuous ON

CEE

InfiniBand20

Interaction: multiple congestion points scenario• A closer observation on the comparison between the single
congestion point scenario and multiple congestion points scenario
Queuelength (KB)

The same queue length evolution for a port in an ONOFF sending pattern.
P2 sending
rate (Gbps)

ON-OFF

P2 is not congested

ON-OFF

P2 is congested

21Interaction: multiple congestion points scenario• A closer observation on the comparison between the single
congestion point scenario and multiple congestion points scenario
Queuelength (KB)

Whether congestion happens at a port in an ON-OFF
sending pattern may be unknowable !

P2 sending
rate (Gbps)

ON-OFF

P2 is not congested

ON-OFF

P2 is congested

22Interaction: multiple congestion points scenario• The ON-OFF regulation of hop-by-hop flow controls masks thereal input rate.
Once PAUSEs/no credits propagate to the upstream switches, the sending rate of
the upstream ports is regulated to an ON-OFF pattern. Upstream ports will send
previously accumulated packets at line rate when receiving RESUME/credits.
Switch view:

PAUSEs/no credits

Upstream switches

Downstream switch

23

Insights Summary• Existing congestion detection mechanisms fail to cognize the impact of
ON-OFF sending patterns, leading to inaccurate congestion detection
results in lossless networks.
• A port may have the same queue length evolution and sending pattern,
but the real congestion state is diverse.

We need to re-understand port states in lossless networks !
24

Understanding Port States in Lossless Networks• Non-congestion : The port is persistently ON and without queuebuildup.

ON

25

Understanding Port States in Lossless Networks• Congestion : The port is persistently ON. The output rate is at full
rate with queue buildup not caused by OFF.

ON

26

Understanding Port States in Lossless Networks• Undetermined : The output rate is in an ON-OFF style. The cause ofqueue buildup may be ambiguous.

OFF

27

Understanding Port States in Lossless Networks• Undetermined : The output rate is in an ON-OFF style. The cause ofqueue buildup may be ambiguous.

ON28

Understanding Port States in Lossless Networks• Undetermined : The output rate is in an ON-OFF style. The cause ofqueue buildup may be ambiguous.
○ receiving PAUSEs/no credits ✓○ excessive input traffic✕

F0 = F2 = 5Gbps

29

Understanding Port States in Lossless Networks• Undetermined : The output rate is in an ON-OFF style. The cause ofqueue buildup may be ambiguous.
○ receiving PAUSEs/no credits ✓○ excessive input traffic✓

F0 = F2 = 25Gbps

30

Understanding Port States in Lossless Networks• Undetermined• Enter:○ Once the port is paused due toreceiving PAUSEs/no credits

Undetermined
Sending
Rate0.

ONOFFONOFFON• Leave:

OFFTime○ Recovering to send packets in acontinuous ON pattern.
○ The real state emerges after leaving
the undetermined state :non-congestion/congestion
31

Ternary Port States in Lossless Networks• Non-congestion (0): The port is persistently ON and without queuebuildup.
• Congestion (1): The port is persistently ON. The output rate is atfull rate with queue buildup not caused by OFF.
• Undetermined (/): The output rate is in an ON-OFF style. The causeof queue buildup may be ambiguous.

32

Our proposal:
Ternary Congestion Detection○ Ternary states transitions detection○ Ternary congestion notification toenhance CC decisions
33

Transitions among Ternary States
Non-congestion① Continuous ON,
queue length > threshold② Continuous ON,
queue length < threshold④ Continuous ON,③ ON-OFFqueue length < threshold orqueue decrease
Queuelength⑥ ON-OFF

Undeterminedt

Congestion⑤ Continuous ON,
queue length > threshold andqueue not decrease
Queuelengtht
34

Transitions among Ternary States
Non-congestion① Continuous ON,
queue length > threshold② Continuous ON,
queue length < threshold④ Continuous ON,③ ON-OFFqueue length < threshold or
queue decrease⑥ ON-OFF

Congestion⑤ Continuous ON,
queue length > threshold andqueue not decrease

Undetermined35

Transitions among Ternary States• Key insight on capturing state transitions:○ A port in a continuous ON sending pattern has infinite Ton.
○ A port in an ON-OFF sending pattern usually has a limited Ton since
the port is paused intermittently.

max(Ton)……
…………

TonTonTon

infinite Ton
36

Conceptual ON-OFF model
Upstream Port

Downstream PortRiRdONOFF

𝜏
Rate

B1 B0

Length37

Conceptual ON-OFF model(1)• Introducing congestion degree ℇ ::(2)

• max(Ton) :(3)38Ternary Congestion Notification• Utilize 2-bit ECN/FECN codepoint• Conditional marking
UE can only be marked when the current code point is not CE. CE ismarked whenever the port is in a congestion state.

○ Undetermined flows○ Congested flows
39

TCD workflow
Step 1. Whether in theundetermined state ?

Ton : The difference between thecurrent timestamp and the timestampwhen the latest OFF period ends.

tcur

toff

40

TCD workflow contd.
Step 2. Whether leaving
the undetermined state
just now ?

41

TCD workflow contd.
Step 3. Whether in thecongestion or noncongestion state ?

Queue length/decrease ?

……

42

Practical DesignCEE

InfiniBand• Recommended ε value: 0.05

• Tc : credit update period)* +,)* +,• 𝑇&' = ) = ) . /0

• max( Ton):
34𝜇s/27𝜇s for 40Gbps/100Gbps
Ethernet.
(link delay 1𝜇s, B1-B0 = 2000B)-*• max( Ton): Tc
no larger than 65536 symbol
time.

43

Evaluation• Testbed• Typical scenarios• Victim scenario• ……

TCD basic properties• Case study (TCD cooperates with CC):
TCD benefit
DCQCN, IB CC, ……
More in the paper…

44Testbed• Implementation: DPDK. Intel 82599 NICs.
• F0: 1Gbps. F1: 8Gbps. F0 is victim during FN launching.

F0 marking
fraction

FN starts

CEE

FN ends

InfiniBand45

Typical Scenario Validation• Single congestion point scenario
UEUE[CEE] P2

[CEE] P1

Congestion happens in P3[InfiniBand] P2

P2: Undetermined à Non-congestion
P1: Undetermined[InfiniBand] P146

Typical Scenario Validation• Multiple congestion points scenarioUE[CEE] P2

CEUE

[CEE] P1

Congestion happens in P3 then P2

CE[InfiniBand] P2

P2: Undetermined à Congestion
P1: Undetermined[InfiniBand] P147

Victim scenario• S0 flows are potential victim flows.
S0 flows marked with CE:
All links are 40Gbps except:
Link S0-T0: 20Gbps
Link S1-T0: 20Gbps• CEE (DCQCN): Hadoop workload.
• InfiniBand (IB CC): MPI and I/Omessages in typical sizes.
48

Case study: TCD cooperates with CC
How to combine TCD with CC in lossless networks ?
• Aggressive rate decrease for congested flows
They are real contributors to congestion.

• Gentle rate adjustment for undetermined flows○ Undetermined flows may be victim flows that should not back off.
○ Blindly increasing the rate of undetermined flows may exacerbate
congestion spreading.
E.g., If a packet is marked with UE, keep the flow rate until it becomes
uncongested or congested.
49

Case Study: DCQCN• Aggressive rate decrease for congested flows
rate reduction factor 𝛂 from default 0.5 to 1.2• Gentle rate adjustment for undetermined flows
keep the rate unchanged when receiving a CNP marked with UE

50

Case Study: DCQCN• Victim scenario

S0 flows FCT performance

All links are 40Gbps except:
Link S0-T0: 20Gbps
Link S1-T0: 20Gbps○ Reduce congestion spreading from the root
○ Avoid throttling unrelated flows mistakenly

51

Case Study: DCQCN• Large-Scale Simulations

52

Case Study: IB CC• Aggressive rate decrease for congested flows
rate reduction step from 1 to 2

• Gentle rate adjustment for undetermined flows
keep the rate unchanged when receiving a CNP marked with UE

1.22× betteroverall average
FCT than IB CC

53

Case Study: TIMELYWith only end-to-end delay (or changes in delay), it is tough for end
hosts to differentiate queueing delay caused by congestion from queueing
delay caused by hop-by-hop flow controls.
• Aggressive rate decrease for congested flows
rate reduction factor 𝛃 from default 0.8 to 1.6• Gentle rate adjustment for undetermined flows
keep the rate unchanged when gradient > 0 and Tlow < RTT < Thigh54

Case Study: TIMELY• Large-Scale Simulations

55

Conclusion• Re-understand congestion detection in lossless networks, including
ternary port states (congestion, undetermined and non-congestion) andtheir transitions.
• TCD for mainstream lossless networks (CEE and InfiniBand).
• TCD cooperates with end-to-end congestion controls to make better
decisions.
We envision that TCD will motivate further exploration ofcongestion controls considering ternary states.
56

Thanks !
zyr17@mails.tsinghua.edu.cn

57