-
Notifications
You must be signed in to change notification settings - Fork 0
/
paper-redesign-data-center.html
1556 lines (701 loc) · 87.3 KB
/
paper-redesign-data-center.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html class="theme-next pisces use-motion" lang="en">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge"/>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222"/>
<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2"/>
<link rel="stylesheet" href="/css/main.css?v=7.0.1"/>
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.0.1">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=7.0.1">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=7.0.1">
<link rel="mask-icon" href="/images/logo.svg?v=7.0.1" color="#222">
<script id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Pisces',
version: '7.0.1',
sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
back2top: true,
back2top_sidebar: false,
fancybox: false,
fastclick: false,
lazyload: false,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<meta name="description" content="本文屬於論文導讀系列，這次針對的是SIGCOMM 2017所發表的論文中關於Data Center架構的論文。SIGCOMM這個 Conference裡面都有很多跟網路相關且高品質的論文，除了學界之外，也常常有很多業界會將相關的研究與產品設計投稿於此，因此是個滿好學習網路概念的一個資源。本篇文章針對的主題是 Re-architecting datacenter networks and stack">
<meta name="keywords" content="high performance dc, sigcomm2017, MPTCP, DCTCP, Clos Network, P4, datacenter, high-end network">
<meta property="og:type" content="article">
<meta property="og:title" content="[論文導讀] Re-architecting datacenter networks and stacks for low latency and high performance">
<meta property="og:url" content="https://www.hwchiu.com/paper-redesign-data-center.html">
<meta property="og:site_name" content="Hwchiu Learning Note">
<meta property="og:description" content="本文屬於論文導讀系列，這次針對的是SIGCOMM 2017所發表的論文中關於Data Center架構的論文。SIGCOMM這個 Conference裡面都有很多跟網路相關且高品質的論文，除了學界之外，也常常有很多業界會將相關的研究與產品設計投稿於此，因此是個滿好學習網路概念的一個資源。本篇文章針對的主題是 Re-architecting datacenter networks and stack">
<meta property="og:locale" content="en">
<meta property="og:image" content="https://imgur.com/9TYGW7N.png">
<meta property="og:image" content="https://imgur.com/wA49CXp.png">
<meta property="og:image" content="https://imgur.com/oVl5iuy.png">
<meta property="og:image" content="https://imgur.com/itaq3gn.png">
<meta property="og:updated_time" content="2018-10-20T07:31:42.584Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="[論文導讀] Re-architecting datacenter networks and stacks for low latency and high performance">
<meta name="twitter:description" content="本文屬於論文導讀系列，這次針對的是SIGCOMM 2017所發表的論文中關於Data Center架構的論文。SIGCOMM這個 Conference裡面都有很多跟網路相關且高品質的論文，除了學界之外，也常常有很多業界會將相關的研究與產品設計投稿於此，因此是個滿好學習網路概念的一個資源。本篇文章針對的主題是 Re-architecting datacenter networks and stack">
<meta name="twitter:image" content="https://imgur.com/9TYGW7N.png">
<link rel="alternate" href="/atom.xml" title="Hwchiu Learning Note" type="application/atom+xml"/>
<link rel="canonical" href="https://www.hwchiu.com/paper-redesign-data-center.html"/>
<script id="page.configurations">
CONFIG.page = {
sidebar: "",
};
</script>
<title>[論文導讀] Re-architecting datacenter networks and stacks for low latency and high performance | Hwchiu Learning Note</title>
<script>
window.fbAsyncInit = function() {
FB.init({
appId : '',
xfbml : true,
version: 'v2.10'
});
};
(function(d, s, id) {
var js, fjs = d.getElementsByTagName(s)[0];
if (d.getElementById(id)) {return;}
js = d.createElement(s); js.id = id;
js.src = "//connect.facebook.net/en/sdk.js";
fjs.parentNode.insertBefore(js, fjs);
}(document, 'script', 'facebook-jssdk'));
</script>
<script async src="//www.googletagmanager.com/gtag/js?id=UA-54006186-1"></script>
<script>
var host = window.location.hostname;
if (host !== "localhost" || !true) {
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-54006186-1');
}
</script>
<noscript>
<style>
.use-motion .motion-element,
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-title { opacity: initial; }
.use-motion .logo,
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<script>
(adsbygoogle = window.adsbygoogle || []).push({
google_ad_client: "ca-pub-1100711228720990",
enable_page_level_ads: true
});
</script>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="en">
<div class="container sidebar-position-left page-post-detail">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-wrapper">
<div class="site-meta">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">Hwchiu Learning Note</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<h1 class="site-subtitle" itemprop="description">kubernetes, sdn, linux,devops</h1>
</div>
<div class="site-nav-toggle">
<button aria-label="Toggle navigation bar">
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br/>Home</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br/>About</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br/>Tags</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br/>Archives</a>
</li>
<li class="menu-item menu-item-sitemap">
<a href="/sitemap.xml" rel="section"><i class="menu-item-icon fa fa-fw fa-sitemap"></i> <br/>Sitemap</a>
</li>
</ul>
</nav>
</div>
</header>
<a href="https://github.com/hwchiu" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" style="fill: #222; color: #fff; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<div id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://www.hwchiu.com/paper-redesign-data-center.html"/>
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Hwchiu"/>
<meta itemprop="description" content="kubernetes/SDN/DevOps"/>
<meta itemprop="image" content="/images/avatar.jpg"/>
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Hwchiu Learning Note"/>
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">[論文導讀] Re-architecting datacenter networks and stacks for low latency and high performance
</h2>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2017-09-26 13:19:37" itemprop="dateCreated datePublished" datetime="2017-09-26T13:19:37+00:00">2017-09-26</time>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-calendar-check-o"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2018-10-20 07:31:42" itemprop="dateModified" datetime="2018-10-20T07:31:42+00:00">2018-10-20</time>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<span class="post-meta-item-text">Comments: </span>
<a href="/paper-redesign-data-center.html#comments" itemprop="discussionUrl">
<span class="post-comments-count disqus-comment-count" data-disqus-identifier="paper-redesign-data-center.html" itemprop="commentCount"></span>
</a>
</span>
<div class="post-description">本文屬於論文導讀系列，這次針對的是SIGCOMM 2017所發表的論文中關於Data Center架構的論文。SIGCOMM這個 Conference裡面都有很多跟網路相關且高品質的論文，除了學界之外，也常常有很多業界會將相關的研究與產品設計投稿於此，因此是個滿好學習網路概念的一個資源。本篇文章針對的主題是 Re-architecting datacenter networks and stacks for low latency and high performance, 該文主旨希望重新打造一個有真正高傳輸效能的資料中心，其中涉及了非常多的面相，從交換機的實現到上層 TCP 協定的修正，從諸多面向來探討傳統的諸多協定為什麼沒有辦法達到真正的高效能傳輸，該論文非常精彩，可以學習到非常多的概念與知識，非常歡迎閱讀。</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="Preface"><a href="#Preface" class="headerlink" title="Preface"></a>Preface</h1><p>本次的論文發表於 <strong>SIGCOMM 2017</strong>, 可以在<a href="http://dl.acm.org/citation.cfm?id=3098825" target="_blank" rel="noopener">這邊</a>找到網路上的文章。於 <strong>SIGCOMM 2017</strong>中，其所屬於的 section 是 <strong>Programmable Devices</strong>，所以可以料想到本文內容會跟 <strong>Programmable Devices</strong> 有些關係。果不其然的內容中有提到 <strong>P4</strong>, <strong>NetFPGA</strong>，處此之外，本篇內容也提到了 <strong>DPDK</strong>, <strong>Clos Network</strong>, <strong>MPTCP</strong>, <strong>DCTCP</strong>, <strong>incast</strong> 等，必須說本篇文章包含了內容實在廣泛，所以要花不少時間去釐清每個元件，才可以了解到本篇論文的內容。</p>
<p>由於本篇論文長達 <code>14</code> 頁,本來也有想過作了簡單的總結就好，大概講述一下想要做到什麼事情，怎麼做到之類的就好。<br>但是後來想一想，今天會有新東西誕生，勢必就是要解決舊東西的限制。<br>如果在學習之於，不但能夠學習新知識，更可以強化自己對於舊知識的概念，何樂而不為?</p>
<p>因此本篇一開始就先針對本文做一個簡單的介紹，直接瞭解到本論文希望做什麼，達到什麼目的，為什麼要這樣做。<br>有興趣的人可以在慢慢往下翻，畢竟內容實在有夠長..XD</p>
<h1 id="簡介"><a href="#簡介" class="headerlink" title="簡介"></a>簡介</h1><p>本論文所發生的場景是在 <strong>Data Center</strong>內，不適用於一般的網際網路，主要是因為網際網路充滿太多未知性與無法掌控的裝置，譬如每條 Link 的頻寬, Switch 的設定等。有這些未知的情況下，無法設計一個好的運作模式來滿足 <strong>Low Latency</strong> 與 <strong>High Throughut</strong> 的需求。因此環境都只考慮 <strong>Data Center</strong>。</p>
<p>本論文提出了 NDP (New Datacenter Protocol Architecture) 這個概念，其具體目標，評比對象以及實作方法如下。</p>
<p>本文希望能夠達到的需求有</p>
<ol>
<li>對於 <strong>short-flow</strong> 能夠有盡量低的 <strong>latency</strong></li>
<li>對於 <strong>long-flow</strong> 能夠有盡量高的 <strong>throughput</strong></li>
<li>對於一個高度負載的網路中，能夠充分利用整個網路拓墣上的 Link 來傳輸封包 (high network capacity)</li>
<li>能夠將 <strong>incast</strong> 情況對網路造成的影響降到最小</li>
</ol>
<p>本文評比對象有</p>
<ol>
<li><strong>DCTCP</strong> (Data Center TCP)</li>
<li><strong>MPTCP</strong> (Multi Path TCP)</li>
<li><strong>DCQCN</strong> (Data Center QCN)<blockquote>
<p>DCQCN is a congestion control protocol for large scale RDMA networks, developed jointly by Microsoft and Mellanox.</p>
</blockquote>
</li>
</ol>
<p>本文實作方法</p>
<ol>
<li>透過 <strong>DPDK</strong> 打造 NDP Application (拋棄 TCP, 重新打造 L4 Protocol)</li>
<li>於 <strong>NetFPGA SUME</strong>上面實作 NDP 相關功能，作為一個 <strong>Hardware Switch</strong></li>
<li>於 <strong>P4</strong>上面實作 NDP 相關功能，作為一個 <strong>Software Switch</strong></li>
</ol>
<p>看到這邊如果對於上述的內容感到興趣的話，就可以開始往下看了!</p>
<h1 id="Abstract"><a href="#Abstract" class="headerlink" title="Abstract"></a>Abstract</h1><p>近年來 <strong>Data Center</strong> 蓬勃發展，為了能夠在內部提供更良好的網路效能，不論是低延遲或是高產出，網路架構從早期的三層式架構(<strong>Fat tree</strong>)逐漸都轉換成 <a href="https://www.networkworld.com/article/2226122/cisco-subnet/clos-networks--what-s-old-is-new-again.html" target="_blank" rel="noopener">Clos Network</a>，然而傳統的 <strong>TCP</strong> 協定在設計上並不是針對 <strong>Data Cetner</strong>來設計的，因此其設計原理導致其不能滿足需求。<br>因此本論文提出了 NDP (new data-center transport architecture)，其能夠提供 <strong>short transfer</strong>接近完美的傳輸時間，同時對於廣泛的應用情況，如 <strong>incast</strong> 下亦能夠提供很高的傳輸效能。<br>NDP架構下， <strong>switch</strong> 採用非常小的 <strong>buffer</strong>來存放封包，當 <strong>buffer</strong> 滿載時，不同於傳統的將封包丟掉，NDP採取的是截斷封包的內容(payload)，只保留該封包的標頭檔，並且將此封包設定為高優度優先轉送。這種作法讓收端能夠有更完整關於送端的資訊，能夠動態的調整傳送速率。<br>本論文將 NDP 的概念實作於 <strong>Software switch</strong>, <strong>Hardware Switch</strong> 以及一般的 <strong>NDP application</strong>。這中間使用的技術與硬體分別包含了 <strong>DPDK</strong>、<strong>P4</strong> 以及 <strong>NetFPGA</strong>。<br>最後本論文進行了一系列效能評比，於大規模的模擬中證明了NDP能夠為整個 <strong>data center</strong> 提供低延遲與高輸出的特性。</p>
<h1 id="Introduction"><a href="#Introduction" class="headerlink" title="Introduction"></a>Introduction</h1><p>隨者 <strong>Data Center</strong> 爆炸性的成長，為了滿足其內部傳輸的需求(低延遲/高輸出)，有各式各樣的新方法或是舊有技術的改進用來滿足上述需求。譬如 TCP 改進的 DCTPC、本來就存在已久的 MPTCP 甚至是 RDMA (RoCE)。 若對 <strong>RDMA/RoCE</strong> 想要更瞭解，可以參考下列連結。<a href="https://www.hwchiu.com/rdma-introduction-i.html">RDMA Introduction (一)</a><br>再 <strong>RDMA</strong> 的網路環境中，為了減少封包遺失對整體傳輸造成的傳輸，都會希望能夠將整個網路傳輸打造成 <strong>lossless</strong> 的環境，為了達成這個方法，可以採用 <strong>Ethernet Flow Control</strong>， <strong>Explicit Congestion Notification</strong>(ECN) 或是 <strong>Priority Flow Control</strong>(PFC)。然而在 <strong> SIGCOMM 2016</strong> 微軟發了一篇 paper 再講 RDMA + PFC 的問題。其表明雖然 PFC 可以用來控制傳送封包的速率，藉此達到 <strong>lossless</strong> 的網路環境，但是一旦整體網路處於高度壅塞的情況時，資料封包與 <strong>PFC</strong> 控制封包的爭奪會使得整體網路沒有辦法繼續提供<strong>低延遲</strong>的優點，最後給出了一個結論 <em>“how to achieve low network latency and high network throughput at the same time for RDMA is still an open problem.“</em></p>
<p>在這篇論文內，作者提出了一個不同與以往思維的新協定 NDP 來滿足上述的要求。<br>NDP 不同於 <strong>TCP</strong>，不需要先透過三方交握來進行連線才可以傳輸封包，同時也避免掉 <strong>TCP</strong> <strong>slow start</strong> 的機制，可以連線一開始就採用全速的方式去傳送封包。<br>此外， NDP 採用了 <strong>per-packet multipath</strong> 而不是 <strong>per-connection multipath</strong> 的方式同時透過 NDP 協定的方式避免掉同條連線中封包順序亂掉(Out of order)所產生的問題。<br>對於 <strong>NDP switch</strong>來說，採用了類似 <strong>CP(Cut Payload)</strong> 的機制，當<strong>switch</strong> 的緩衝區滿載的情況下，對於接下來收到的封包不會直接丟掉，而是會將其 <strong>Payload</strong> 給移除，並且設定高優先度的方式將其標頭檔盡可能快速的傳送到目的地，讓接收段能夠有資訊瞭解到當前網路與發送端的狀態。<br>透過 <strong>CP</strong> 的機制可以對 <strong>metadata</strong> 達到近乎 <strong>lossless</strong> 的狀況，不過對於 <strong>data</strong> 來說則沒有辦法。不過因為 <strong>NDP</strong> 本身協定設計的方式，封包掉落所產生的影響並不會像 <strong>TCP</strong> 一樣有如此嚴重的影響。</p>
<h1 id="Design-Space"><a href="#Design-Space" class="headerlink" title="Design Space"></a>Design Space</h1><p>對於內部使用的 <strong>Data center</strong> 來說，其網路流量大部分都是屬於 <strong>Request/Reply</strong>,這種類似 RPC 方式的流量。這意味者以網路使用率來看其實不會一直處在滿載的狀況，但是對連線接收端的應用程式(譬如 server)來說，其所收處理的網路流量可能是大資料的傳輸，也可能是簡單資料的短暫連線。對於短暫連線來說，最大的重點就是<strong>低延遲</strong>，盡可能快的傳輸回去。<br>為了處理這個問題，今日有滿多的應用程式決定採取 <strong>reuse</strong> TCP 連線來處理多個 request，藉此方式減少 <strong>TCP</strong> 三方交握所產生的延遲。<br>然而，是否存在一種架構，不論當前整個網路系統是否處於高流量負載，該架構能夠讓應用程式不需要重複使用連線，讓每個 <strong>request</strong> 都是一條全新連線，同時又能夠接近完美的延遲(意味者不會像 <strong>TCP</strong> 都要先經過三方交握才可以開始傳資料)。<br>於是乎 <strong>NDP</strong> 的設計發想就出現了，為了達到上述的要求，首先必須要重新思考，當前網路架構中，是什麼因素阻礙了上述要求，這些阻礙要如何克服。<br>因此接下來的章節會講述這些因素。</p>
<h2 id="End-to-end-Service-Demans"><a href="#End-to-end-Service-Demans" class="headerlink" title="End-to-end Service Demans"></a>End-to-end Service Demans</h2><p>本文列出了四個 <strong>data center</strong> 內應用程式要追求的特性。</p>
<h3 id="Location-Independence"><a href="#Location-Independence" class="headerlink" title="Location Independence"></a>Location Independence</h3><p>一個分散式的應用程式其運行於<strong>data center</strong>內的任一機器上都不應該要影響應用程式本身的功能。由於目前都採用 <strong>clos network</strong> 的方式來設計網路拓樸，所以整個網路拓樸方面應該是能夠提供足夠的流量來使用，而不會變成一個理由或是瓶頸使得應用程式必須要選擇特定的機器才可以運行。</p>
<h3 id="Low-Latency"><a href="#Low-Latency" class="headerlink" title="Low Latency"></a>Low Latency</h3><p>雖然 <strong>Clos Network</strong> 的架構能夠提供足夠的頻寬給拓墣中內的服務器，對於流量的負載平衡能提供良好的效果，但是對於短暫連線來說，並沒有辦法提供低延遲的能力。<br>作者認為雖然能夠提供高流量輸出是一個很重要的議題，但是能夠提供低延遲的能力則是更重要且優先度更高。</p>
<h3 id="Incast"><a href="#Incast" class="headerlink" title="Incast"></a>Incast</h3><p><strong>Incast</strong> 這個專有名詞的介紹可以參考<a href="https://www.youtube.com/watch?v=-e5Rw2I3QJk" target="_blank" rel="noopener">Data Centers and TCP Incast - Georgia Tech - Network Congestion</a>，簡單來說就是同時間有大量的<strong>request</strong>進到<strong>data center</strong>內，這些<strong>request</strong>都會產生對應的<strong>reply</strong>然後這些<strong>reply</strong>連線同時間一起進入到 <strong>switch</strong>內，這會使得 <strong>switch</strong> 的緩衝區立刻滿載沒辦法繼續承受封包，導致部分的 <strong>TCP</strong> 連線需要降速重送。<br>作者認為一個好的網路架構遇到這種問題時，應該要能夠保護背後的應用程式連線，讓這些連線應該要盡可能地維持低延遲性。</p>
<h3 id="Priority"><a href="#Priority" class="headerlink" title="Priority"></a>Priority</h3><p>這邊特性老實說有點難以想像，我盡力的就我所瞭解的去解釋。<br>假設今天有一個應用程式，同時會發送不同的 <strong>request</strong> 到後端去處理，而這些 <strong>request</strong> 所產生的 <strong>reply</strong> 本身是有依賴的關係。<br>所以假如這多個 <strong>reply</strong> 沒有依照當初發送 <strong>request</strong> 的順序回來的話，在應用程式端這邊就必須要特別去處理，譬如說不要同時送多個<strong>request</strong>，不過這樣就沒有更好的效能表現。<br>因此對於應用程式來說，若本身能夠有一個優先度的機制，能夠決定那些封包要先處理，就可以解決上述的問題，而讓應用程式本身就可以更自由的去處理。</p>
<h2 id="Transport-Protocol"><a href="#Transport-Protocol" class="headerlink" title="Transport Protocol"></a>Transport Protocol</h2><p>目前 <strong>data center</strong> 內部採用的 <strong>Transport Protocol</strong> 雖然可以處理上述應用程式的問題，但是為了處理那些問題，反而會失去下列特性。<br>而 NDP 本身在設計時，希望能夠在滿足上述應用程式的需求，同時又保有下列的特性。</p>
<h3 id="Zero-RTT-connection-setup"><a href="#Zero-RTT-connection-setup" class="headerlink" title="Zero-RTT connection setup"></a>Zero-RTT connection setup</h3><p>目前主流的 <strong>TCP</strong> 協定再傳送資料前，必須要先進行一次三項交握，這意味者當 <strong>data</strong> 送出去前，至少要先花費 <strong>RTT*3</strong> 的等待時間。<br>對於低延遲的應用程式來說，希望能夠達到 <strong>RTT*0</strong>，至少 <strong>RTT*1</strong> 的等待時間就能夠將資料送出，這意味者對 <strong>NDP</strong> 來說，在資料發送前，整個連線不需要有三方交握類似的行為，才可以一開始就直接送出資料。</p>
<h3 id="Fast-start"><a href="#Fast-start" class="headerlink" title="Fast start"></a>Fast start</h3><p><strong>Data Center</strong> 不同於網際網路的地方在於網路拓樸中的每個 <strong>Switch/Link</strong> 都是自己掌握的。<br>所以 <strong>TCP</strong> 採用的 <strong>Slow Start</strong> 其實對於 <strong>Data Center</strong> 來說是沒有效率的，畢竟一開始就可以知道可用頻寬多少，不需要如同面對網際網路般的悲觀，慢慢地調整 <strong>Window Size</strong>，而是可以一開始就樂觀的傳送最大單位，在根據狀況進行微調。<br>若採取這種機制，則應用程式可以使用更快的速度去傳送封包。</p>
<h3 id="Per-packet-ECMP"><a href="#Per-packet-ECMP" class="headerlink" title="Per-packet ECMP"></a>Per-packet ECMP</h3><p>在 <strong>Clos Network</strong> 中，錯綜複雜的連結狀態提供了 <strong>Per-flow</strong> ECMP 一個很好發揮的場所，可以讓不同的連線走不同的路徑，藉此提高整體網路使用率。<br>然而如果今天 <strong>Hash</strong> 的結果相同的話，其實是有機會讓不同連線走相同的路徑，即使其他路徑當前都是閒置的。<br>若採取 <strong>MPTCP</strong> 這種變化型的 <strong>TCP</strong> 來處理的話，該協定本身的設計可以解決上述的問題，但是對於短暫流量或是延遲性來說，卻沒有很好的效果。<br>為了解決這個問題，如果可以將 <strong>Per-flow</strong> ECMP 轉換成 <strong>Per-Packet</strong> ECMP。因此 NDP 本身協定的設計就是以 <strong>Per-Packet</strong> ECMP 為主。</p>
<h3 id="Reorder-tolerant-handshake"><a href="#Reorder-tolerant-handshake" class="headerlink" title="Reorder-tolerant handshake"></a>Reorder-tolerant handshake</h3><p>假設我們已經擁有了 <strong>Zero RTT</strong> 以及 <strong>Per-packet ECMP</strong> 兩種特性，擇一條新連線的封包可能就會發生 <strong>Out of order</strong> 的情況，收送順序不同的狀況下，若對於 <strong>TCP</strong> 來說，就會觸發壅塞控制的機制進而導致降速。<br>因此 NDP 在設計時，必須要能夠處理這種狀況，可以在不依賴封包到達先後順序下去處理。</p>
<h3 id="Optimized-for-Incast"><a href="#Optimized-for-Incast" class="headerlink" title="Optimized for Incast"></a>Optimized for Incast</h3><p>即使整個 <strong>data center</strong> 的網路環境，如頻寬等資訊一開始就已經可以掌握， <strong>incast</strong> 的問題還是難以處理，畢竟網路中變化太多，也許有某些應用程式就突然同時大量產生封包，這些封包同時間到達 <strong>switch</strong> 就可能導致封包被丟棄。<br>因此 NDP 本身在設計時，也希望能夠解決這個問題。</p>
<h2 id="Switch-Service-Model"><a href="#Switch-Service-Model" class="headerlink" title="Switch Service Model"></a>Switch Service Model</h2><p>在一個 <strong>data center</strong>內，除了應用程式特定，傳輸層協議(<strong>Transport Protocol</strong>)之外，還有一個性質也是很重要的，這個性質與上述兩個性質關係緊密，一起影響整個網路的運作，這個性質就是 <strong>Switch Service Model</strong>。<br>作者認為這性質中，最重要的就是<strong>當 switch port 發生阻塞時會怎麼處理</strong>，這個性質會完全影響到傳輸層協定以及壅塞控制演算法(Congestion control algorithms)的設計，甚至是傳輸相關的概念，如 <strong>per-packet ECMP</strong> 都會被影響到。<br>作者提到，目前有很多種預防壅塞機制，譬如 <strong>Loss as a congestion</strong>，<strong>Duplicate or selective Acks</strong>等，其中 <strong>Duplicate or selective Acks</strong> 會主動去觸發重送，這種技巧對於長時間連線來說是好的，但是對於需要低延遲的短暫連線來說是不好的，主要是這些重送都會經過一個 <strong>RTO</strong>(Retransmission timeouts)，這個時間的長短都會產生一些負面的影響，因此也不是一個萬用的解法。</p>
<p><strong>ECN(Explicit Congestion Notification)</strong> 的出現幫助壅塞狀況提供了不少改進，譬如 <strong>DCTCP (data center TCP</strong> 就採用了這個技術來輔助。這個技術對於長時間的流量來說，能夠有效的減少封包遺失的數量，然而對短暫流量來說卻沒有太大的幫助，因為短暫流量太短暫了，根本來不及去接收 <strong>ECN</strong>的封包並處理。在現實情況中，<strong>switch</strong>本身會採用一個較大的緩衝區來處理資料封包以及ECN封包，這種設計對於 <strong>incast</strong> 的現象能夠有效地減緩封包被丟棄的情形。但是也因為緩衝區太大，每個封包在 <strong>Switch</strong> 內待的時間就會更長，因此重送機制的時間就會被拉長，導致低延遲性就會破功。<br>除此之外，對於 <strong>Lossless Ethernet</strong> 的傳輸來說，則是會透過 802.3X 的 <strong>Pause Frame</strong> 亦或是 802.1 Qbb 的 PFC <strong>(Priority Flow Control)</strong>。這類技術都是透過控制封包阻止送端停送封包，降低封包遺失的數量。然後這些就有技術也不是十全十美，以 <strong>PFC</strong> 來說，在一個高度乘載的網路拓樸中，有可能會有兩條不同的連線根據<strong>Hash</strong>導向走向相同，同時這兩個連線最初的設定是相同的優先度，則有可能會因為一條連線的壅塞進而導致其他連線也被影響到。<br>上述這些壅塞機制的設計除了 <strong>ECN</strong> 之外，其餘的對於 <strong>Per-packet ECMP</strong> 都沒有能夠提供良好的效果。<br>最後，提到了一種稱為 <strong>CP (Cut Payload)</strong> 的做法，這種機制就是當壅塞發生時，不丟棄整個封包，而只是丟棄封包的資料，而保留封包的標頭檔，對於一個常見的TCP封包來說，大概就是 (XX:14XX)的感覺。當應用程式端收到<strong>只有標頭檔，沒有資料的封包</strong>，就可以知道這個當前線路有壅塞的情況，可以進行對應的處理。<br>這種情況下，就可以避免減少 <strong>RTO</strong> 對於重送造成的時間延遲。<br>然而這種設計也有兩個問題(畢竟CP是1994提出的論文)</p>
<ol>
<li>整個 <strong>Switch</strong> 採取FIFO的機制，所以這些被砍掉資料的封包，也是要慢慢等待<strong>switch</strong>將封包處理完畢才可以往外轉送，這邊就會大幅增加這些封包的RTT時間</li>
<li>這個設計是基於 <strong>single-path</strong> 傳輸，沒有考慮到多條路徑傳輸，不論是 <strong>per-packet</strong> 或是 <strong>per-flow</strong> 的ECMP。</li>
</ol>
<p>在看完了以上這麼多段落後，大概可以歸納出作者心目中的完美協定，簡單複習一下</p>
<ol>
<li>對於短暫流量能夠提供低延遲，低延遲，低延遲 </li>
<li>對於長時間流量盡量能夠提供高流量輸出</li>
<li>per-packet ECMP</li>
<li>遇到 incast 等情況也能夠繼續保持低延遲</li>
</ol>
<p>因此接下來的章節，就會講述 NDP 到底如何實作並且盡可能地有提供上述性質。</p>
<h1 id="Design"><a href="#Design" class="headerlink" title="Design"></a>Design</h1><p>為了滿足上述的條件，NDP 在設計時就決定整個設計要包含完整架構，包含了<br>1.<strong>switch</strong>的行為<br>2.<strong>routing</strong><br>3.全新的 <strong>Transport</strong>協定</p>
<p>基本上可以使用下圖做一個概括性的統整，透過全新設計的 <strong>NDP</strong> 架構，能夠滿足該圖中的每個特性。<br>接下來會簡單介紹每個區塊大致上要做的事情。後面的章節才會詳細敘述其設計方法。<br><img src="https://imgur.com/9TYGW7N.png" alt=""></p>
<p>對於 <strong>Clos Network</strong> 拓樸來說，因為網路內擁有多條錯綜複雜的連結，因此整體網路的頻寬是足夠的。這對於想要執行 <strong>Load-Balanced</strong> 的應用來說是綽綽有餘的，然而為了避免流量都流經相同的路徑導致某些路徑上面有大量的流量進而導致封包掉落並且對於延遲性與流量輸出都有影響。因此必須要採取必要的措施將連線給打散到不同的路徑之中。<br>此外，對於短暫連線來說，<strong>per-packet</strong>的ECMP相對於 <strong>per-flow</strong>來說更有意義，但是<strong>per-packet</strong>的ECMP必定會遇到封包順序不同產生的 <strong>out of order</strong>情況。<br>為了滿足短流量低延遲的效果，發送端不能利去探測當前網路的頻寬來決定傳送速度，必須要在第一個封包就將資料送出，也就是所謂的 <strong>Zero RTT</strong>。<br>對於 <strong>switch</strong> 來說，要達到低延遲，則緩衝區不能夠太大，否則封包待在緩衝區內的時間過長，就會導致該封包要花更長的時間才能夠被送過去。<br>在小緩衝去的前提下，封包數量一多則緩衝區就會馬上爆滿。當封包掉落同時加上因為 <strong>per-packet</strong> ECMP 所產生的封包順序錯亂問題 (out of order)，這會使得收送端(receiver)會非常難去處理這些問題，無法辨別當前沒有收到封包到底是什麼原因。<br>若想要完整的避免封包遺失，則 <strong>switch</strong> 的緩衝區就要夠大，譬如採取 <strong>pause frame</strong>，亦或是 <strong>PFC</strong>這類型 <strong>lossless network</strong>。<br>然而這類技術都會因為當前連線產生的壅塞判斷去影響網路中其他連線，這就會使得某些連線沒有辦法達到低延遲的效果。<br>所以NDP設計的理念是一種介於 <strong>loss</strong> 與 <strong>lossless</strong> 的概念。<br>最後，採取的 <strong>Packet Trimming</strong>，其設計理念與 <strong>Cuy Payload</strong> 極為相似，此種情況下， <strong>switch</strong> 採用小緩衝區，當接收端發現封包只有標頭沒有內容時，就可以判斷當前網路有壅塞發生。為了可以讓重送時間盡可能的快，對於這些被截斷內容的封包， <strong>switch</strong> 應該要盡可能的快讓該類型的封包送出去。<br>這類型的封包到達接收端後，會讓接收端有資訊可以知道當前那些應用的封包到達，藉由這些資訊加上一個完整的封包池(receiver-pulled pool)，接收端就可以精準地控制那些封包要優先處理。</p>
<h2 id="NDP-Switch-Service-Model"><a href="#NDP-Switch-Service-Model" class="headerlink" title="NDP Switch Service Model"></a>NDP Switch Service Model</h2><p>前述有提到過 <strong>Cut Payload</strong> 的技術，透過把資料丟掉，單純送標頭檔給對方。<br>這邊不丟掉封包的原因是希望能夠通知 <strong>接收端</strong> 端關於封包的訊息，讓 <strong>接收端</strong> 端可以要求 <strong>送端</strong> 重送。這整體所消耗的時間會比接收端依賴 <strong>Retransmission Timeout</strong> 來的還要短。<br>然而。本文作者發現到，若採用最原生的 <strong>Cut Payload</strong> 實作其實會引發下列問題，因此要將其改良以解決這些問題。</p>
<p>直接以下圖來解釋，在一個 <strong>9KB jumbograms</strong> 的情況下，去探討應用程式之間的 <strong>goodput</strong>， <strong>goodput</strong> 與 <strong>throughput</strong> 的差異是 <strong>goodput</strong> 代表的是應用程式真正接收到的封包量，不包含<strong>協定標頭檔以及重送封包所造成的流量</strong>。<br><img src="https://imgur.com/wA49CXp.png" alt=""></p>
<p>圖中紅線的部分代表的是 <strong>原生 CP </strong>實作，而藍線的部分代表則是 <strong>NDP</strong> 的實作。<br>X 軸代表的是網路中有多少條連結上面被大量被切斷的封包(被砍掉內容，只剩下標頭檔)。<br>Y 軸代表的是在當前網路下，應用程式真正收到的 <strong>goodput</strong> 佔理想值多少百分比。(最高100%)。</p>
<p>圖中實線代表的是所有應用程式的平均<strong>goodput</strong>，而虛線代表的是10%最差應用程式們的平均<strong>goodput</strong>。<br>這邊先來看<strong>原生CP</strong>的效果，可以明顯看到實線的部分，會因為流量愈多，而使得整體的 <strong>goodput</strong> 就大幾乎呈線性下線。<br>而對於虛線來說，整個幾乎慘不忍睹，代表後半部分的應用程式根本沒有辦法擁有好的傳輸量。</p>
<p>除了上述模擬結果外，<strong>原生CP</strong>還有一個問題是採取 FIFO 的機制來收送一般封包與被切斷後的封包，這意味者 <strong>CP</strong> 想要讓 <strong>收端</strong>盡快地知道有封包要重送，但是這些被截斷的封包又要等待 <strong>switch</strong> 內的緩衝區都被消耗掉才有機會被送出，其實這一來一回對於整體的是會造成一些損傷的。</p>
<p>為了解決上述<strong>原生CP</strong> 帶來的問題， NDP 提出三大改革</p>
<ol>
<li><strong>NDP Switch</strong> 維護兩個佇列緩衝區，低優先度的用於資料傳輸，高優先度的用於被截斷封包的傳輸，ACKS 以及 NACKS。<ol start="2">
<li>作者認為這個設計聽起來有點詭異，看起來好像反而會讓資料封包更晚送出去，但是經過實驗證明，高優先度的封包到達<strong>接收端</strong>並且通知<strong>送端</strong>要重送封包時，通常 <strong>switch</strong> 低優先度緩衝去的封包都還沒有全部處理完畢。</li>
</ol>
</li>
<li>高優先度跟低優先的佇列緩衝區彼此之間採取的是 <strong>10:1</strong> 的輪流機制，每送十個高優先度的封包，就送一個低優先度的封包，這可以讓要重送的封包盡早通知到<strong>接收端</strong></li>
<li><p>為了打亂網路中平衡狀態(強者恆強，弱者恆弱)，每當低優先度的佇列滿載且遇到新封包時，這時候 <strong>Switch</strong> 有兩個行為會採用(機率分別是 50%)。</p>
<ul>
<li>將新到的封包截斷，送到高優先度佇列</li>
<li>將低優先度最後面的封包截斷，送到高優先度佇立，而剛進來的封包就送到低優先度佇列</li>
</ul>
</li>
<li><p>藉由上述兩種行為，作者說可以打亂網路的平衡，這點可以由圖2的虛線看到，在 NDP 的環境中，即使是效能最差 10% 應用程式的 <strong>goodput</strong> 跟平均也是差不多的。</p>
</li>
</ol>
<h3 id="Routing"><a href="#Routing" class="headerlink" title="Routing"></a>Routing</h3><p>前述已經提到， <strong>NDP</strong> 想要完成 <strong>per-packet</strong> ECMP而非 <strong>per-flow</strong> ECMP，於是作者在這邊提出了兩大類做法</p>
<ol>
<li>讓 <strong>switch</strong> 本身隨機當前封包該怎傳送</li>
<li>讓 <strong>送端</strong> 決定當前封包該怎傳送</li>
</ol>
<p>根據作者自己的實驗證明，讓<strong>送端</strong>去選擇封包該怎轉送會比讓 <strong>switch</strong> 去隨機轉送封包來得更有效率，同時因為 <strong>switch</strong> 本身不用去思考怎該怎轉送封包，每個封包處理的速度可以更快速，因此 <strong>switch</strong> 的緩衝區可以設置的更小，對於低延遲的特性有更好的支持。<br>NDP 認為，由於本文的環境是在 <strong>data center</strong> 內，網路拓樸的狀況都是可以事先知道的，譬如從<strong>送端</strong>到<strong>接收端</strong>共有那些路徑可以走。<br>因此 <strong>NDP</strong> 的實作方式是 <strong>送端</strong>事先要先瞭解到<strong>送端</strong>之間有哪些路徑可以走，然後每遇到一個封包，就挑一個路徑出來發送，下一個封包就送剩下的路徑們中間隨機挑一條去發送，當所有的路徑都已經走過一次後，就全部重新來過。<br>這樣的做法達到兩個優點<br>1) 藉由分散封包到所有路徑去傳送，能夠提升網路整體的使用率，並且減少某條網路成為瓶頸的可能性。<br>2) 每次挑選時都透過類似隨機的方式，可避免多個應用程式會走到相同的走法導致網路出現太規律的走法，進而導致使用率不佳或是某些路徑過於壅塞。</p>
<p>至於，關於 <strong>讓送端決定當前封包該怎傳送</strong> 怎麼實作，作者提出了三種方法。</p>
<ol>
<li>source-route:<ul>
<li>作者沒解釋，不確定其實作方式。</li>
</ul>
</li>
<li>label-switch:<ul>
<li>事先規劃好那些 <strong>label</strong> 走那些路徑，然後送端幫封包上 label</li>
</ul>
</li>
<li>destination addresses:<ul>
<li>根據目的端的位置來選擇，假如目的端有多個 <strong>IP</strong> 地址，則每個地址都可能有不同的走法。</li>
</ul>
</li>
</ol>
<h2 id="Transport-Protocol-1"><a href="#Transport-Protocol-1" class="headerlink" title="Transport Protocol"></a>Transport Protocol</h2><p>接下來作者要詳細介紹整個 NDP Transport protocol 的設計。</p>
<p>NDP 在設計 <strong>Transport</strong> 協定時是基於 <strong>receiver-driven</strong> 的理念去設計的。希望藉由這個設計能夠跟之前提過的各式各樣技術結合，如 <strong>multipath forwarding</strong>、 <strong>packet trimming</strong> 以及 <strong>short switch queues</strong>。藉由與這些技術結合，NDP 想要提供1)低延遲2)高產出的效能。</p>
<p>作者這邊提到，<strong>TCP</strong>因為早期設計給網際網路使用，所以設計理念是悲觀的，因為不知道整個網路上每個節點的狀況，盡可能的小心去使用。譬如所謂的 <strong>slow start</strong>、三方交握等原則。<br>此外，對於 <strong>TCP</strong> 來說，當今天若同時發生網路壅塞掉封包或是多重路徑路由所導致封包的順序不一致，這些情況會讓 <strong>TCP</strong> 無法分辨到底發生什麼事情，於是最後只好要求送端重傳，這行為無形間就降低了整體的傳送速率。</p>
<p>然而對 NDP 來說就不一樣，由於是在 <strong>data center</strong> 內，能夠事先知道整個網路節點的各情況，因此 NDP 希望採取的是樂觀的設計理念，包含了</p>
<ol>
<li>第一個 RTT 就送資料，不等三方交握</li>
<li>一開始就根據當前線路的最大乘載量去設定傳送速率，假設都沒有其他流量使用。</li>
<li>不依賴順序的協定內容</li>
</ol>
<p>NDP 採用了截斷封包的方式，透過標頭檔的內容告訴<strong>接收端</strong>到底哪些封包需要重送，這使得<strong>接收端</strong>有更明確的知識知道網路發生什麼情況，因此封包到達的先後順序就顯得不重要。</p>
<p>接下來使用下圖來解釋截斷封包的運作模式。<br><img src="https://imgur.com/oVl5iuy.png" alt=""></p>
<p>假設今天從 <strong>SRC</strong> 要傳送九個封包到達 <strong>DST</strong>，當封包到達 <strong>DST</strong> 上層的 <strong>switch</strong>(TOR) 時，因為 <strong>switch</strong> 的資料緩衝區(低優先度佇列)只能承受八個封包。所以第九個封包就被截斷了(時間點為 T(trim))<br>接下來透過不同優先度的佇列的設計，被截斷的封包可以在 T(header)的時間就馬上到達 <strong>DST</strong>， <strong>DST</strong> 在看到標頭檔後就馬上學習到第九個封包需要重送，因此馬上送個資訊回到送端。<br>此資訊到達送端的時間點為 T(rtx)，同時間 <strong>switch</strong> 還在處理剛剛的八個封包，大概處理到第二個左右。<br>當<strong>送端</strong>將第九個封包送到 <strong>switch</strong> 時，這時候 <strong>switch</strong> 處理到第六個左右，因此資料緩衝區不但有空間可以容納地九個封包，同時這過程中也沒有任何處於閒置的況狀，可以說是將緩衝區的使用率盡可能的提升。</p>
<p>所以到這邊為止，我們已經可以知道截斷封包能夠告訴<strong>收端</strong>哪些封包需要重送。<br>作者認為藉由上述的特性與 <strong>Zero RTT</strong> 的結合，認為讓<strong>送端</strong>去決定當收到一筆資料(Zero RTT)後<strong>送端</strong>要傳送多少封包是最佳的選擇。</p>
<p>接下來分成兩部份去介紹，第一部分介紹其設計理念及原則，第二部分則是詳細介紹步驟</p>
<ol>
<li>當送端一開始用全速去傳送封包後，接下來就會停止傳送封包</li>
<li>等待 <strong>接收端</strong> 發送請求要求 <strong>送端</strong> 繼續送封包</li>
<li>接收端可以根據當前本身收送封包的速率(譬如對外連結上有多條連線導致每條連線都沒有辦法用到最高速度)，因此會由 <strong>接收端</strong> 去決定 <strong>送端</strong> 當前要送多<br>快。</li>
<li>不論是重送的封包，抑或是全新的資料封包，<strong>接收端</strong>都可以要求<strong>送端</strong>去傳送。</li>
<li><strong>接收端</strong> 採用 <strong>Pull</strong> 的概念來達到控制 <strong>送端</strong> 的傳送速率，<strong>接收端</strong> 會維護一個 <strong>Pull</strong> 佇列，供所有連線一起使用。</li>
<li><strong>Pull</strong> 佇列內放置的是 <strong>Pull</strong> 封包，該封包要標示屬於哪個連線，以及一個計數，而該計數則是 <strong>per-sender</strong>的，用來記錄當前發送過多少個 <strong>Pull</strong> 封包。</li>
<li><strong>Pll</strong> 佇列預設會公平的去處理每個連線所對應的 <strong>Pull</strong> 封包，不過可以根據連線優先度調整其傳送的 <strong>Pull</strong> 封包數量，藉此提高對應送端的傳送速率。</li>
</ol>
<p>詳細描述每個步驟行為如下</p>
<ol>
<li>連線開始時，<strong>送端</strong>一開始就用全速將封包送往 <strong>接收端</strong>，這些封包都會包含類似 <strong>TCP</strong>的序號。</li>
<li>若<strong>接收端</strong>收到的是被截斷的封包，會立刻傳送 <strong>NACK</strong> 給<strong>送端</strong>，要求其將準備重送封包(還不需要重送)</li>
<li>若<strong>接收端</strong>收到的是資料封包，會立刻傳送 <strong>ACK</strong> 給 <strong>送端</strong>，通知其該封包已接收到(清除舊有資料，準備新封包，此時也還不會傳送)</li>
<li>當 <strong>接收端</strong> 收到封包(資料或是截斷封包)，都會馬上加入一個 <strong>Pull</strong> 封包到其 <strong>Pull</strong> 佇列中。</li>
<li>當 <strong>送端</strong> 收到由 <strong>接收端</strong>所發送的 <strong>Pull</strong> 封包時，會根據 <strong>Pull</strong> 封包內的計數來決定當下要傳送多少封包(可以是重送封包，也可以是新封包)</li>
<li>當 <strong>送端</strong> 將所有封包都傳送完畢後，就會將最後一個封包打上標誌，當 <strong>接收端</strong> 看到此標誌時就知道對應的 <strong>送端</strong> 已經沒有封包要送了，就將其對應的 <strong>Pull</strong> 風包給移除，避免下次產生不必要的請求傳輸。</li>
<li>若<strong>送端</strong> 之後又有資料想要傳輸，則必須主動傳輸給 <strong>接收端</strong>，而不會透過 <strong>接收端</strong>的 <strong>Pull</strong> 封包來取得。</li>
</ol>
<p>根據作者本身的實驗數據，其相關設定如下</p>
<ol>
<li><strong>switch</strong> 的資料緩衝區只有八個封包</li>
<li>MTU 設定為 9K (jumbograms)，</li>
<li>switch 能力為 10Gb/s</li>
<li>環境為 FatTree</li>
</ol>
<p>在此環境下，每個封包完整處理的時間為 7.2µs，若考慮到優先佇列的使用，最差情況下的處理時間是 400µs，此數據相對於一般來說其實是非常小的。<br>因此在 NDP 的環境中，RTO (Retransmission timeout) 可以設計得更小。</p>
<p>回過來看先前提過的問題， NDP 要如何在 <strong>incast</strong> 的狀況下有良好表現?<br>假設一開始有很多個 <strong>送端</strong>，每個都用全速傳輸。可以想像得到的是會有很多封包都被截斷，接者每個對應的 <strong>接收端</strong> 都可以採用 <strong>Pull</strong> 的概念控制對應 <strong>送端</strong>的傳送速率，就可以讓每個<strong>送端</strong>的傳送速率總和能夠符合 <strong>switch</strong> 的處理速度，藉此能夠讓被截斷的封包數量降到最小，甚至沒有。</p>
<h2 id="Coping-with-Reordering"><a href="#Coping-with-Reordering" class="headerlink" title="Coping with Reordering"></a>Coping with Reordering</h2><p>根據 <strong>Per-packet</strong> 多重路徑路由，對於<strong>送端/接收端</strong>來說，資料封包，<strong>Pull</strong> 封包， <strong>ACK</strong> 以及 <strong>NACK</strong> 在收到的時候是非常有機率是順序錯亂的。雖然 <strong>NDP</strong> 一開始的設計是不用擔心這個情況的。<br>不過作者提下有提了一個情境是關於 <strong>Pull</strong> 的問題，這邊實在講得太難讓人理解，我看了好久，思索許久，還是無法理解到底在說什麼。<br>所以決定暫時放棄這個段落。</p>
<h2 id="The-First-RTT"><a href="#The-First-RTT" class="headerlink" title="The First RTT"></a>The First RTT</h2><p>NDP 為了達到能夠在第一個封包就直接送資料而不採用 <strong>TCP</strong> 的三項交握後送資料，必須要處理三個問題</p>
<ol>
<li>避免遇到大量相通 <strong>Source IP</strong> 的垃圾封包影響<blockquote>
<p>(因為 TCP有連線認證，沒有連線的 TCP 封包不會被處理，避免被大量垃圾影響)</p>
</blockquote>
</li>
<li>避免同樣一條連線在 <strong>連線建立</strong>方面不小心處理多次</li>
<li>處理在 <strong>第一個 RTT</strong> 之間經由多重路徑路由造成順序錯亂的資料封包</li>
</ol>
<p>目前已知採用 <strong>First RTT</strong> 的實作，如 <strong>T/TCP</strong> 以及 <strong>TFO (TCP Fast Open)</strong>都有一些相關機制，譬如採用 <strong>Token</strong> 或是 <strong>Connection ID</strong> 來處理上述問題，但是沒有一個實作能夠同時處理三個問題。</p>
<ol>
<li>這個問題 NDP 不想處理，認為可以透過 <strong>Hypervisor/NIC</strong> 之類的方式預防<blockquote>
<p>逃避問題?</p>
</blockquote>
</li>
<li>在 <strong>送端/接收端</strong> 兩邊都設計了 <strong>time-wait</strong> 的狀態。<blockquote>
<p>這邊也看不太懂，到底要怎麼透過這個狀態處理此問題。估計不是重點，敘述很少。</p>
</blockquote>
</li>
<li>由於 <strong>per-packet</strong> ECMP 的關係，第一個到達<strong>接收端</strong>的封包往往不是第一個送出的封包，為了處理這個問題，<strong>送端</strong>第一次送出的封包都會帶有一個<strong>SYN</strong>的標誌以及該封包是第一次送出封包中的第幾個。藉由這個資訊就可以讓任何一個<strong>第一次送出</strong>中的任一個封包來建立連線。</li>
</ol>
<h2 id="Robustness-Optimizations"><a href="#Robustness-Optimizations" class="headerlink" title="Robustness Optimizations"></a>Robustness Optimizations</h2><p>假如網路一切都順順利利的運行，上述 <strong>NDP</strong> 的實作其實運作得非常良好，然而好景不常，網路常常會出問題，譬如 <strong>switch</strong> 或是 <strong>link</strong> 會損毀。<br>這種情況下， <strong>NDP</strong> 要怎麼處理這些問題來繼續保持其提供的低延遲與高輸出的特性。<br>常見的問題有</p>
<ol>
<li><strong>switch</strong>, <strong>link</strong> 損毀導致封包不通</li>
<li><strong>link</strong> 出問題，突然降速，譬如從 10Gbs 降速成 1Gbs</li>
</ol>
<p>作者表示，傳統的 <strong>single-path</strong> TCP 對於這些問題都沒有很好的處理方式，會讓整體的效能大幅度下降。 NDP 處理的方式就是採用大量的 <strong>Counter</strong>，去記住每條連線上面關於 <strong>ACK</strong> 以及 <strong>NACK</strong> 的數量，同時透過 <strong>per-packet</strong> 多重路由的方式來傳送封包。<br>因此 <strong>送端</strong> 會定期檢查，若當下所有可傳送路徑中，有某些路由上面的 <strong>counter</strong> 數值異常，代表可能出現問題，不論是降速抑或是網路不通。<br>此時就會將有問題的路由先從候選清單中排除，避免封包走到有問題的路由去。<br>作者表示，傳統的作法大部分都依賴路由協定去偵測問題並且動態修改路由表，這些雖然有效，但是要花費太多時間去處理，因此效果不彰。</p>
<h2 id="Rteurn-to-Sender"><a href="#Rteurn-to-Sender" class="headerlink" title="Rteurn-to-Sender"></a>Rteurn-to-Sender</h2><p>前述提過，採用 <strong>Cut Payload</strong> 的機制能夠有效的解決 <strong>incast</strong> 的網路問題，然而當 <strong>incast</strong> 的封包過多時， <strong>switch</strong> 上面的兩個佇列(高/低優先度)都可能會被塞滿，在這種情況下封包就會被丟棄了。<br>舉例來說，高優先度佇列可以存放<strong>1125 * 64-byte</strong>的封包量，而低優先度佇列只能存放 <strong>8 * 9K-bye</strong> 的封包量。假設 <strong>送端</strong>發送了一個封包過去，卻遲遲沒有等到回應，在經過 <strong>RTO</strong> 的時間後，就會重送封包。<br>根據前述的實驗， 最大的 <strong>RTT</strong> 時間是 <strong>400µs</strong>，因此作者認為最大的 <strong>RTO</strong> 設定為 1ms 即可。<br>然而根據 <strong>10Gbs</strong> 的傳輸能力來開，要處理<strong>1125 * 64B</strong> 的封包大概需要 8ms，這意味者重送的封包是可以在佇列被消耗完畢前送達到 <strong>switch</strong>，可以保障不會有 <strong>switch</strong> 處於閒置的狀態進而提高整體使用率。</p>
<p>為了追求極致的作者認為，在某些情況下，譬如高優先度的封包或是資料量極小的封包<br>當所有的佇列都滿的情況下，這時候 <strong>switch</strong> 就會採取神秘的作法，將封包的 <strong>source IP</strong> 以及 <strong>destination IP</strong> 給反轉，然後將該 <strong>header</strong> 迅速送回給 <strong>送端</strong>，告訴<strong>送端</strong>說你有封包要掉了，快重送。<br>然後這種機制只有在某些特殊情況下，可能網路當下有些問題之類的，作者想要加快更快的處理速度避免等待 <strong>RTO</strong>來處理</p>
<p>下圖是根據模擬環境得到的數據圖，該模擬環境如下</p>
<ol>
<li>432 機器</li>
<li>FatTree</li>
</ol>
<p><img src="https://imgur.com/itaq3gn.png" alt=""><br>該Y軸採用的是 CDF(cumulative distribution function)，X 軸紀錄的是當<strong>送端</strong>送出第一個封包到達其收到第一個<strong>ACK</strong>所花的時間。<br>此數值包含所有的 <strong>delay</strong>，也包含重送所導致的花費。</p>
<ol>
<li><strong>Permutation</strong> 顯示的是 <strong>432-node</strong> 中每個<strong>node</strong>都會往下一個 <strong>node</strong> 來進行連線，故會有 <strong>431</strong> 條連線</li>
<li><strong>Random</strong> 顯示的是 <strong>432-node</strong> 中每個<strong>node</strong>都會隨機找一個 <strong>node</strong> 來進行連線，故會有 <strong>431</strong> 條連線<br>上述這兩種 <strong>case</strong> 都表現不錯，能夠完整的用滿整個 <strong>FatTree</strong> 的網路頻寬，同時平均的 <strong>delay</strong> 大概落在 100ms。</li>
</ol>
<p>而接下來 <strong>Incast</strong> 的情況則是挑選<strong>100 node</strong> 同時間對同一個 <strong>node</strong> 進行發送的實驗，變異數則是每個連線的傳輸大小。<br>可以觀察到的，當傳送數量只有 <strong>135KB</strong> 時，整體的效能是比較差的。<br>原因是每個連線都能透過第一次的<strong>RTT</strong>就將所有的封包傳送出去，這情況導致大量的封包被截斷甚至超過緩衝區的數量。同時大概只有 <strong>25%%</strong> 左右的標頭檔被最佳化給送回給 <strong>送端</strong>去加速處理。<br>以 <strong>delay</strong> 來看，最後一個封包花了 <strong>11,055µs</strong> 去傳送。</p>
<p>假設今天整體傳送量更大，到達了 <strong>1350KB</strong>，雖然第一個封包傳輸的行為會跟 <strong>135KB</strong> 的實驗一致，但是後續 <strong>NDP</strong> 的設計能夠讓整體後續的處理更為平順以及更穩，所以其平均的處理時間大概只有 <strong>95µs</strong>。</p>
<h2 id="Congestion-Control"><a href="#Congestion-Control" class="headerlink" title="Congestion Control"></a>Congestion Control</h2><p>作者表示， <strong>NDP</strong> 本身沒有任何 <strong>Congestion Control</strong>，因為 <strong>Congestion Control</strong> 本身是為了下列兩個目的而誕生的。</p>
<ol>
<li><strong>Avoiding congestion collapse</strong></li>
<li><strong>fairness</strong></li>
</ol>
<p>而 <strong>NDP</strong> 本身實作的特性已經完全避免掉上述的問題，所以根本沒有必要去實作沒必要的 <strong>Congestion Control</strong>。</p>
<p>NDP 的設計下，每個連線一開始都樂觀地採用全速發送，同時因為協議設計的關係，<strong>接收端</strong>擁有大量關於當前連線的資訊，透過 <strong>pull</strong> 佇列的設計能夠讓每條連線平均的使用當前網路流量。<br>不過作者也有提到，由於<strong>接收端</strong>可以決定<strong>送端</strong>傳送封包的速率，因此若有些連線被標註是高優先度的，則可以使用比一般連線更多的流量。這種情況下就是故意造成不公平的，因此也不是大問題。</p>
<h2 id="Limitation-of-NDP"><a href="#Limitation-of-NDP" class="headerlink" title="Limitation of NDP"></a>Limitation of NDP</h2><p>接下來的章節中，作者透過實驗證明了在各種流量模式中，<strong>NDP</strong> 提供的效果非常接近於 <strong>Clos</strong> 網路架構理論上的效能。<br>在非對證的網路架構中，例如 <strong>BCube</strong>、 <strong>Jellyfish</strong>， <strong>NDP</strong> 的表現會稍微差一點，主要是當前網路壅塞時，<strong>送端</strong>會將封包透過不同距離的路徑來傳輸封包(就不是ECMP了)。於這種情況下，若採用 <strong>sender-based per-path</strong> 的多重路由就會有良好的效果。</p>
<blockquote>
<p>有一篇<strong>paper</strong>在講述上述的問題<br>C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving datacenter performance and robustness with Multipath TCP. In Proc. ACM SIGCOMM, Aug. 2011. </p>
</blockquote>
<p>對於一個超級高度負載的網路中心來說，當封包數量過多的時候，會發生<strong>送端</strong>發生的封包一直處於被截斷的情況，然而雖然表現不好，但是跟目前已知的協定，譬如 <strong>DCTCP</strong> 比起來， <strong>NDP</strong> 的效能還是勝出。</p>
<p>最後的問題就是 <strong>環境部屬問題</strong>， 只要當哪一天 <strong>P4</strong> 交換機能夠廣泛的部屬在 <strong>data center</strong> 中的時候，要部屬 <strong>NDP</strong> 就是很簡單的事情。此外，如何跟現有的 <strong>TCP</strong> 連線共存也是一個問題，因為 <strong>NDP</strong> 目前會吃掉該網路的流量導致 <strong>TCP</strong> 幾乎沒有辦法使用，因此在 <strong>P4</strong> 交換機端應該要有辦法去處理相關的問題。</p>
<h1 id="Summary"><a href="#Summary" class="headerlink" title="Summary"></a>Summary</h1><p>到這邊為止，已經可以大概知道 <strong>NDP</strong> 的設計思維，接下來就要探討其如何實作以及其實驗效能。<br>不過必須說，只有<strong>Paper</strong>而缺少投影片或是影片的情況下，很多敘述都要靠想像力去思考到底怎實作，花了不少時間在思考，甚至有些情境還想不出來到底是什麼，只能憑感覺去想像。當然，這個會有這些問題其實是因為自己知道的東西還不夠多，所以變成很多作者認為是基本概念的東西，對我來說都要重新思考學習，才會導致自己思考不夠完善。<br>只好繼續多念書多加強自己了</p>
</div>
<div class="popular-posts-header">Related Posts</div>
<ul class="popular-posts">
<li class="popular-posts-item">
<div class="popular-posts-title"><a href="/2016-08-31-825029.html" rel="bookmark">mTCP 讀後筆記</a></div>
</li>
<li class="popular-posts-item">
<div class="popular-posts-title"><a href="/ovs-dpdk-docker.html" rel="bookmark">OVS + DPDK + Docker 共同玩耍</a></div>
</li>
<li class="popular-posts-item">
<div class="popular-posts-title"><a href="/setup-mininet-like-environment.html" rel="bookmark">手把手打造仿 mininet 網路</a></div>
</li>
<li class="popular-posts-item">
<div class="popular-posts-title"><a href="/2014-08-16-debugcounter-in-floodlight.html" rel="bookmark">DebugCounter in Floodlight</a></div>
</li>
<li class="popular-posts-item">
<div class="popular-posts-title"><a href="/2016-03-27-switchdev-i.html" rel="bookmark">[Switchdev] Introduuction To Switchdev</a></div>
</li>
</ul>
<footer class="post-footer">
<div class="post-tags">
<a href="/tags/System/" rel="tag"># System</a>
<a href="/tags/Network/" rel="tag"># Network</a>
<a href="/tags/SDN/" rel="tag"># SDN</a>
<a href="/tags/Paper/" rel="tag"># Paper</a>
<a href="/tags/DPDK/" rel="tag"># DPDK</a>
<a href="/tags/P4/" rel="tag"># P4</a>
<a href="/tags/DataCenter/" rel="tag"># DataCenter</a>
</div>
<div class="post-nav">
<div class="post-nav-next post-nav-item">
<a href="/ovs-dpdk-docker-2.html" rel="next" title="OVS + DPDK + Docker 共同玩耍(二)">
<i class="fa fa-chevron-left"></i> OVS + DPDK + Docker 共同玩耍(二)
</a>
</div>
<span class="post-nav-divider"></span>
<div class="post-nav-prev post-nav-item">
<a href="/onos-trllis-testing.html" rel="prev" title="ONOS Trellis Testing">
ONOS Trellis Testing <i class="fa fa-chevron-right"></i>
</a>
</div>
</div>
</footer>
</div>
</article>
</div>
</div>
<div class="comments" id="comments">
<div id="disqus_thread">
<noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript>
</div>
</div>
</div>
<div class="sidebar-toggle">
<div class="sidebar-toggle-line-wrap">
<span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
<span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
<span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
</div>
</div>
<aside id="sidebar" class="sidebar">
<div class="sidebar-inner">
<ul class="sidebar-nav motion-element">
<li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
Table of Contents
</li>
<li class="sidebar-nav-overview" data-target="site-overview-wrap">
Overview
</li>
</ul>
<div class="site-overview-wrap sidebar-panel">
<div class="site-overview">
<div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
<img class="site-author-image" itemprop="image"
src="/images/avatar.jpg"
alt="Hwchiu"/>
<p class="site-author-name" itemprop="name">Hwchiu</p>
<div class="site-description motion-element" itemprop="description">kubernetes/SDN/DevOps</div>
</div>
<nav class="site-state motion-element">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">157</span>
<span class="site-state-item-name">posts</span>
</a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">