# TCP/IP 筆記

## 參考資料
:::spoiler
https://www.796t.com/content/1544205423.html
http://chriswenyuan.blogspot.com/2017/05/c-sockraw-ping.html
https://blog.csdn.net/slslslyxz/article/details/111145473
:::

## ***Link-State vs. Distance-Vector***
* Link-State
每個節點都必須知道網路中所有連結的成本
* Distance-Vector
每次循環時，再直接相鄰的節點之間進行訊息交換
## ***期末考***

## ***A problem with distance vector routing***
:::warning

* **Defining Infinity**
The first obvious solution is to **redefine infinity to a smaller number**, such as 16
* Split Horizon
Taking information from node A, modifying it,and sending it back to node A is what creates the confusion.資料是誰給的就不要送回去給他
* Split Horizon and Poison Reverse
資料是誰給的就可以送回去給他，但 ==replace the distance with infinity== as a warning: “Do not use this value; what I know about this route comes from you.”
* **能用 Split Horizon and Poison Reverse 解決 2 node 的問題，但 3 node 沒辦法 ， 因此還是要把無限是成一個較小的數字(Defining Infinity)**
:::


## ***RIP timer***
:::warning

* Periodic Timer: (**25-35 sec**)
每個 router 都有一個，隨機設為25-35 sec 時間到就把跟新的資訊送出去，and the timer is randomly set once again
* Expiration Timer (**180 sec**)
每一個 router 跟新的時間，如果超過 180 秒沒跟新，就把 cost 設為 16 表示無法到達 ，但是她那一欄 table 仍然保留。
* Garbage Collection Timer (**120 sec**)
如果cost 設為 16 , a timer called the garbage collection timer is set to 120 s，When the count reaches zero, the route is purged from the table.
:::


## ***OSPF***

* Area : AS 內部的小區塊 ，LSP 在 area 內部做廣播(flooding)

### ***type of link VS link state***
:::warning

* type of link 是聯線的型態
* p2p
* transient
* stub
* link state 是公告的資訊類型 (==**LSA**==)*link state advertisiment*
* router link LSA **(intra Area)**
* network link LSA **(intra Area)**
* Summary link to network LSA (幫 Area 做摘要後丟出去)
* Summary link to AS boundary route LSA (幫 AS 做摘要後丟出去)
* External link LSA (AS外資訊的摘要)
:::

### ***type of link***

### ***type of OSPF packet***
:::warning

* **Router link and network link LSA** :

在 area 內部做 flooding ，根據自身是甚麼類型傳送不同的 LSA 。 是 router 傳送 Router link LSA ，是 network 傳送 network link LSA 。最後在根據 LSA 做出 topology 用來算最短路徑 。

flood the area with information about the router links and network links inside an area

* **The summary link to network LSA** :

area border router 用 flooding 告訴其他 router 到自己 area 內 network 的 cost 是多少

is used by the area border router to announce the existence of other networks outside the area.

* **Summary Link to AS Boundary Router LSA**

告訴其他 AS 自己內部 network 的 summary ，並送到 backbone 去

* **External Link LSA**

外部 AS 告訴內部的 AS 外面的世界

:::


### ***OSPF 範例***

#### ***建立 area 1 cost 表格的步驟***
:::success

1. 先在各個 area 內部做 flooding ，會先完成這兩塊
:::spoiler
:::

:::success
2. area border router 幫自己的 area 做 summary ，並送到 backbone 去，在 backbone 做 flooding ， backbone 的 table 就完成了

:::spoiler

**backbone 會有其他 network 的 summary**


:::
:::success
3. area border router 把在 backbone 做 flooding 得到的其他 area 的資料，經過計算得出到其他 area 的 network 的最短距離，最後帶回去給自己的 area 完成 table

:::warning
### ***用 RT3 RT4 到 N7 為例***
1. RT3 RT4 先算到其他 area border router 的 cost
> RT3 到 RT7 RT10 的最短距離分別為經過 RT5 RT6 cost 為 20 15
> RT4 到 RT7 RT10 的最短距離分別為經過 RT5 RT6 cost 為 14 22
2. RT3 RT4 再算經由上一步得出的 cost 與之前的 summary ， 求出最短距離 ， 在帶回去給自己的 area 完成 table
> 由先前的 summary 可知 RT10 RT7 到 N7 的 cost 都是 5
> RT3 經由 RT7 RT10 到 N7 的距離為 25 20 保留小的帶回去 area 完成 table
> RT4 經由 RT7 RT10 到 N7 的距離為 19 27 保留小的帶回去 area 完成 table

:::

## ***BGP(PATH VECTOR ROUTING)***
Distance vector and link state routing 都是在 AS 內的
AS 間用 PATH VECTOR ROUTING
> 1. AS 間交換資訊的 router 叫做 speaker router
> 2. path vector 能夠避免迴圈

> 有 BGP 連線的是直接連線 ， 並非位置決定 。例如 R1 R3 如果有 BGP 連線，就是直接連線。
## ***Multicasting***

### ***Group ID***
* multicast address : class D ， 1110 開頭 。

:::info
***Mapping class D to Ethernet physical address***

physical address 前面那串會是固定的 ， 會有 32(2^5) 個 multicast address 對到同一個 physical address ， 但 dest 收到他沒有的 group 的東西時會忽略掉。


:::
:::info
#### ***Tunneling***

* 有的 router 沒辦法做multicast ， 因此在傳送時在外面包一層大家都看得懂的東西 ， 讓他能順利傳到目的地 。


:::

### ***IGMP***

* network 告訴 router 要加入哪個 group
* host 能夠指定他只要，或不要那些 source 送過來的

The record also shows one of the two modes: include mode or exclude mode

#### ***IGMP Messages***
:::success
* membership query message 是由 router 發出詢問 network 要加入那些 group

A membership query message is sent by a router to find active group members in the network

> ***general query message*** :
>
> router 叫他所有的 interface 告訴他完整的 group
>
> the querier router probes each neighbor to report the whole list of its group membership (interest in any multicast group).
>
> ***group-specific query message***:
>
> router 問 interface 是否還要加入這個 group
>
> report if it is still interested in a specific multicast group
>
> ***group-and-source-specific query message*** :
>
> router 問 interface 他是否還要加入這個 group ， 並且來自某個 source
>
> report if it is still in a specific multicast group, x.y.z.t, coming from any of the N sources
:::
#### ***IGMP Protocol Applied to Host***
1. ***socket state :***

host 紀錄每個 process 要加入的 group 與例外的 source

> 

2. ***Interface state***

經過整理 ， 一個 group 保留一列就好 ，送到 router 時比較有效率 。


3. ***Router States***


:::

### ***multicast routing protocols***

* 分成 Source-based Tree 跟 Group-shared tree
* Source-based Tree 根據 source 的不同創出不同的最小路徑樹 。 就算是同個 group ， tree 也不會一樣。
:::spoiler

:::

* Group-shared tree 是把東西都先 encapsulates the packet in a unicast packet 再由他送到 core router ， 同個 group 的 tree 都一樣。
:::spoiler

:::
### ***MOSPF***
***without area***

> 在整個 AS 內部做 multicast ， **在 OSPF 下再加上Group membership LSA ，標註有加哪個 group** ，因為是 link state ， 每個 router 都能畫出完整的圖 。 **當有 packet 要做 multicast 的時候 ， 會立刻畫出 Source-based Tree 到各個有加入該 group 的 router** 。

***with area***

當要 multicast 的時候
1. 先在自己的 area 先做傳送 ， 送到各個 group number
2. area 內的 router 一定要送一份到各個 border router 去
:::spoiler
* border 都要設為 ==Wild-Card Multicast Receivers== ，multicast 一定要送一份到各個 border router 去

> n4 送到有 group a 的 number rt2 border router rt3 rt4

:::
3. 再由 area border router 經由 backbone router ，從那個 border router 生出一顆 trea 送到所有需要該 group 的 area 的 border router
4. 如果 source 在的 area 有不只一個 ， 會用由 summary 產生的相反的 cost ， source area border router 選出到其他的 border router 最短的路徑 ， 合力長出 source base tree

:::info
**summary link LSA 給的是由 border router 到 source 的 cost ， 因此當 border router 要做 multicast 時 ， 會當作自己不在 area 內 ， 所以他並不知道 source 到他的 cost ， 他有的只是 summary ， 而 summary 的方向是相反的 。**
:::
> 

5. 到 dest 時 ， 如果 dest area 有多個 border router 只會由反向 cost 最短的 border router 送到 dest

> area 2 只由 RT10 送

## ***DVMRP***
==**DVMRP 是先做 broadcasting 再慢慢修改**==

> 先flooding，有3個改進flooding的方法

## ***RPF(Reverse Path Forwarding)***
一樣 flooding ，但router 只收來自從 source 到 router 最短路徑來的 packet ，並做 forwarding
* router 會找 multicast packet 的 source address 在查 unicast routing table 看是不是來自最短路徑
* 能解決 loop 的問題


## ***RPB(Reverse Path Broadcasting)***
用 RPF 可能會有 network 收到兩份 packet ，這時這個 network 周圍的 router 就會比看誰到 source 是最短距離 ， 由那個 router 送。這樣就只會收到一份了

* 經過 RPB 所有 network 都會收到一次的 packet


## RPM

經過 RPB 所有 network 都會收到一次的 packet ， 再用 RPM 修

purn 剪
graft 接
> net3 是經過 RPB 由其他 router 送

## ***Group-shared tree***
### ***BGP***
先把 packet 包在 unicast 裡 ， 送給 core router 再由 core router 做 unicast 。
* 一個 group 一顆 tree
* 每個 router 都會用 unicast 告訴 core router 是否要加入這個 group ， 所以 BGP 是從 group members 開始長的


## ***Comparisons***
:::warning
* DVMRP and MOSPF 的 tree 是從 source 開始長的
* BGP 是從 group members 開始長的
* DVMRP 是先做 broadcasting 再慢慢修改
* CBT 的 tree 因為 group members 的 join 是會慢慢修改的 ， DVMRP and MOSPF 都是有 packet 來直接長出來
:::

## ***Transport layer***
### ***TCP***
* service 要有 error control 需要 : ***sequence number*** ， ***check sum*** ， ***ack*** ， ***timer***
### ***TRANSPORT-LAYER PROTOCOLS***

> 4 個都有 error control 跟 flow control 的功能

* Stop-and-Wait Protocol
* Go-Back-N Protocol
* Selective-Repeat Protocol
* Piggybacking

## ***Stop-and-Wait Protocol***

* ==***sender 傳過來的 seq num 是多少 ack 回seq num +1***==
* ==sender source 的 windo sizewindo size 都是 1==
* 限制 sender 一定要等到有 ack 才能送下一個 ， 以達到流量控制 。
* 設有 timer 再有問題時做 resent ， 達到 error control
* sequence number 為一個 bit (0 and 1)

:::warning
windo size 表示一次最多能送幾個 byte 出去
:::


> 當 sender 傳過來的 sequence num 錯時 ， recever 會 discard 掉 ， 再傳一次他要收的 ack

## ***Go-Back-N Protocol***

* ==***sender 傳過來的 seq num 是多少 ack 回seq num +1***==
* ==**sender windo size 小於 2^m - 1** ， **source 的 windo size 是 1**==
* 當 sequence num 是 m 個 bit 時 ， sender 的 windo size 要小於 2^m - 1

:::warning
windo size 表示一次最多能送幾個出去 ，不可能會大於

如果等於的話 ， 當送出去 receiver 有收到 ， 但 ack 都掉的話 ， sender 不知道 receiver 有收到 ， 因此 timer 時間到時會重送 ， 這時 receiver 就會無發分辨這是新的還是舊的 。


***without timeout***

> **沒收到前面 seq num 的 ack 但是有他之後的**，代表前面的有收到但是 ack 可能在中間掉了 ， **依然能夠滑動 windo**


***with timeout***

> 當 sender 一次送多個 packet ，但有個半路掉了 n 時 ， 因為 receiver windo size 只有 1 ， 且一直不會滑動 ， 會忽略其他的 seq num 並一直回 ack n+1 ， 因此 source 的 windo 也一直不會滑動 ， 當 time out 時會從掉的那個 n 重送 。


:::

## ***Selective-Repeat Protocol***
* ==***window size 最多是 seq num 的一半***==
* ==***sender 傳過來的 seq num 是多少 ack 就回多少***==
* sender 有收到 ack 且他前面的 seq num 都有收到，windo 就會往前滑 ， 如果一直沒有收到 seq num 的 ack 最終 **==timeout==** 了 ， ==**只需要重送那個沒有收到 ack 的 seq num**==

> 因為如果 receiver 全都有收到 windo 滑動了 ， 但 ack 都掉了 sender 的 windo 沒動 ， 這時如果window size 大於 seq num 的一半 ，seq num 會重複 ， receiver 會以為是新的 seq num
> 

* sender 有收到 ack 且他前面的 seq num 都有收到，windo 就會往前滑 ， 如果一直沒有收到 seq num 的 ack 最終 **==timeout==** 了 ， ==**只需要重送那個沒有收到 ack 的 seq num**==

## ***Piggybacking***

* 用在 Go-Back-N Protocol
* 不特別在傳 ack ， 當有資料要傳時，在順便連 ack 一起傳


## ***TCP***
### ***Header***


### ***Control***

## ***connection control***
### ***建立連線***
1. server passive open : accept() ， client active open : connect()
2. client 傳 SYN message 給 server ， 告訴 server 他開始的 seq num 是 8000 ， 8000 是沒有資料的
:::warning
SYN message 不能有 data
:::
4. server 用piggybacking 同時傳 SYN+ACK ， 告訴 client 他有收到了 ， 和起始的 seq num 是 15000 ， client connection open
5. client 單獨傳 ack ， seq num 為 8000 帶表沒有帶 data ， server connection open


### ***傳 DATA***

:::warning
PSH flag 代表不管送的人一次送多少個 byte ， 就算只有一個 segment 只有一個 byte 都要送出去 。 收的人要不要送到 buffer 讓他等了，直接往上送到 process

:::

### ***CLose***

***using three-way handshake***


***Half-Close***


:::danger
client 收到 FIN 時不能馬上關掉 ， 要等兩倍的 MSL因為
1. 如果 Client 回的 ack 傳送時掉了他又直接關掉 ， server 會一直收不到 ack 會一直重送，但沒人理他，永遠關不掉。
2. 在 EOF 之後中間可能還會有一些因為重傳 ， 亂七八糟的資料 ， 如果不等一段時間有可能會直接建立新的連線 ， 這時 client 會分不出來送過來的是新的資料 ， 還是舊的重傳的資料
* client 能用起始 seq num 大於最後一個 num 的方法解決這個問題 。

:::


## ***flow control***
:::warning
***windo size 不能做 shrinking***


:::
## ***Silly Window Syndrome***
:::spoiler

:::
## ***Rules for Generating ACK***
1. 使用 Piggyback
2. 不急著送出 ack，而是等待 500ms，才不會產生多餘的流量。
3. 不能同時有兩筆 in-order packet 未回送 ack
4. 收到沒照順序的 seq num 要馬上送出 ack
5. 收到補之前漏掉的 segment 要馬上送出 ack
6. 如果 ack 掉了 ，導致 sender 又重送，receiver 要馬上送出 ack
7.

## ***flow control VS Congestion control***
:::warning

flow control 是因為 receiver 的 buffer 快滿了 ， 告訴 sender 送慢一點

Congestion control 是因為網路壅塞 receiver 告訴 sender 送慢一點

:::
## ***Congestion control***

***exponential increase***

* Slow start
* exponential increase

> 一開始 windo size 是 1 ， 根據 ack 如過都是 RTT 回來 ， 做指數型的成長

***additive increase***


## ***Congestion example***

* 發生 ==timeout== 後，一開始 ==windo size 設為 1== ，==threshold 設為 上次 timeout 的 windo 大小的一半==
> threshold : 上次 timeout 的 windo 大小的一半
* 從 1 開始==做指數成長==，==為了避免壅塞到 threshold 改成 ***congestion avoidance***，開始做線性成長==
* 一直到有 timeout ， 在重複這個動作

* 如果傳送中有資料掉了 ， 出現==3次重複的 ACK== ，一樣視為有壅塞 ，但是不嚴重
* 所以起始的 ==windo size 設為之前的一半== ==threshold 也設為之前 windo size 設為的一半==，因此==做線性成長==


## ***timer***

***RTT 平均值***

* ***==重送的不算 RTT==***

> a 通常是 1/8

***RTT 標準差***

> b 通常是 1/4

***timeout 的時間 RTO***

* 重送資料的 timeout 不用原本 RTO 計算的方式 ， 直接設為原本 RTO 的兩倍
* 重送資料與他之後用的 timeout 都是原本 RTO 的兩倍
* 一直到有新的資料在 timeout 前有 ack 送回來 ， 就回復原本 RTO 的計算方法

***Example***


## ***最短路徑***
https://web.ntnu.edu.tw/~algo/Path.html
:::info
### Single Source Shortest Paths:Label Setting Algorithm

#include <iostream>
using namespace std;

void dijkstra(int source);

// 是否已經算出到點的最短距離
bool visit[6];

// point to point cost
int w[6][6];

// 靜態變數就算沒初始化，也設為0
// the shortest path to the point
int d[6];

// the parent of the point
int parent[6];

int main()
{
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> w[i][j];
        }
    }
    dijkstra(0);
    cout<< endl;
    for(int i=0;i<6;i++){
        cout<<d[i]<<' ';
    }
    cout<< endl;
}

// 限制 cost 沒負號
void dijkstra(int source)
{

    // initialize visit[] to false
    for (int i = 0; i < 6; i++)
    {
        visit[i] = false;
    }

    // source is shortest path itself
    visit[source] = true;
    d[source] = 0;
    parent[source] = source;

    // 把剩餘所有的點家道最短路徑
    for (int k = 0; k < 6 - 1; k++)
    {

        int a = -1;
        int b = -1;

        // 100 以上表示無限
        int min = 100;

        // 從已知最短路徑開始找，找出一條最短且聯外的邊
        for (int i = 0; i < 6; i++)
        {
            // 從已知最短路徑開始找
            // 找一個已在最短路徑樹上的點
            if (visit[i])
            {
                for (int j = 0; j < 6; j++)
                {
                    // 找一個不在最短路徑樹上的點
                    // 找出一條最短且聯外的邊

                    // 假設 a --> b --> c
                    // 找到時會把設做 min ， 在記錄到 d[b] 裡
                    // 並且會把他的 visit[b] 改成 true
                    // 這樣下次回圈就不會再有這次的 a 到 b 了
                    // visit[b] 開始找時 min 依然是 1e9
                    // 迴圈完後 min 為 b --> c 的 cost
                    if (!visit[j])
                    {
                        if (d[i] + w[i][j] < min)
                        {
                            a = i;
                            b = j;
                            min = d[i] + w[i][j];
                        }
                    }
                }
            }
        }

        // 起點有連通的最短路徑都已找完
        if (a == -1 || b == -1)
            break;

        // 不連通即是最短路徑長度無限長
        if (min == 100) break;

        // to b's shortest path is confirm
        visit[b] = true;

        // save the shortest path from source to b
        d[b] = min;

        // b is extend from a
        parent[b] = a;
    }
}

:::
:::info
## Dijkstra

#include <iostream>
using namespace std;
#define INF 1000
#define node_size 6
#define source 2
#define dest 5

void Dijkstra();
void path();

// 最短路徑
int d[node_size];

// 兩點間的距離
int w[node_size][node_size];

// 父節點
int parent[node_size];

// 是否為確定距離
int visit[node_size];

int main()
{

    for (int i = 0; i < node_size; i++)
    {
        for (int j = 0; j < node_size; j++)
        {
            cin >> w[i][j];
        }
    }

    Dijkstra();
    cout << endl;
    cout<<"source : "<<source<< endl<<"destination : "<< dest << endl;
    cout << endl
         << "source 到各點的距離 :";
    for (int i = 0; i < node_size; i++)
    {
        if (d[i] == INF)
        {
            cout << "INF" << ' ';
        }
        else
        {
            cout << d[i] << ' ';
        }
    }
    cout << endl<< endl;

    if (d[dest ] == INF)
    {
        cout << "無法到達" << endl<< endl;
    }
    else
    {
        path();
        cout << endl<< endl;
    }
}

void Dijkstra()
{
    for (int i = 0; i < node_size; i++)
    {
        d[i] = INF;
    }
    for (int i = 0; i < node_size; i++)
    {
        visit[i] = false;
    }
    for (int i = 0; i < node_size; i++)
    {
        parent[i] = -1;
    }

    d[source] = 0;

    

    parent[source] = source;

    // 要把所有路徑變成確定距離要 node_size 次
    for (int k = 0; k < node_size; k++)
    {
        // 從 a 點開始
        int a = -1;

        // 最短路徑
        int min = INF;

        // 直接找離 source 最近，且為暫時距離的點( d[i]!=INF && visit[i] == false )當 a
        for (int i = 0; i < node_size; i++)
        {
            // 沒 visit 過 && 離 source 最近
            if (!visit[i] && d[i] < min)
            {
                min = d[i];
                a = i;
            }
        }

        // 所有聯通的路都 visit 過了
        if (a == -1)
        {
            break;
        }

        // 因為是所有與原點暫時距離裡的最小值，可以設為確定距離之後都不會再跟改了
        visit[a] = true;

        // 算出各個與 a 點相連的暫時距離
        for (int j = 0; j < node_size; j++)
        {
            if (!visit[j] && d[a] + w[a][j] < d[j])
            {

                d[j] = d[a] + w[a][j];
                parent[j] = a;
            }
        }
    }
}

void path()
{
    int path[node_size];
    for (int i = 0; i < node_size; i++)
    {
        path[i] = -1;
    }

    // 終點
    path[node_size - 1] = dest;

    // 下一個路徑上上個路徑的父節點
    for (int i = node_size - 1; i >= 0; i--)
    {

        // parent[source]=source
        // 當到 source 時會一直在 source
        // 所以 path 到 souce 時就結束了，直接跳出去
        if (source == path[i])
        {
            break;
        }
        else
        {
            // 下一個路徑上上個路徑的父節點
            path[i - 1] = parent[path[i]];
        }
    }

    for (int i = 0; i < node_size; i++)
    {
        if (path[i] != -1)
        {

            cout << path[i];
            if (i != node_size - 1)
            {
                cout << " -> ";
            }
        }
    }
}

:::
::: info
## Bellman

#include <iostream>
using namespace std;

#define INF 1000
#define node_size 6
#define source 5
#define dest 0

void bellman();
void path();


// 已知的最短路徑
// 初始為 INF , d[source] 為 0
// 從已知最短路徑的點 a，和與其相連的點 b 算出暫時的最短路徑 d
// 窮舉邊ab：d[a] + w[a][b] < d[b]
// 以邊ab來修正起點到b點的最短路徑：d[b] = d[a] + w[a][b]
int d[node_size];

// 兩點間的距離
int w[node_size][node_size];

// 父節點
int parent[node_size];

int main()
{

    for (int i = 0; i < node_size; i++)
    {
        for (int j = 0; j < node_size; j++)
        {
            cin >> w[i][j];
        }
    }
    bellman();

    cout << endl;
    cout<<"source : "<<source<< endl<<"destination : "<< dest << endl;
    cout << endl
         << "source 到各點的距離 :";
    for (int i = 0; i < node_size; i++)
    {
        if (d[i] == INF)
        {
            cout << "INF" << ' ';
        }
        else
        {
            cout << d[i] << ' ';
        }
    }
    cout << endl<< endl;

    if (d[dest ] == INF)
    {
        cout << "無法到達" << endl<< endl;
    }
    else
    {
        path();
        cout << endl<< endl;
    }

   
}

void bellman()
{
    for (int i = 0; i < node_size; i++)
    {
        parent[i] = -1;
    }

    // d初始為 INF , d[source] 為 0
    for (int i = 0; i < 6; i++)
        d[i] = INF;
    d[source] = 0;

    parent[source] = source;

    // d 最多 node_size-1 個 INF
    for (int k = 0; k < node_size - 1; k++)
    {
        // 窮舉 找最短的路徑
        for (int i = 0; i < node_size; i++)
        {
            for (int j = 0; j < node_size; j++)
            {
                if (d[i] != INF && w[i][j] != INF)
                {
                    if (d[i] + w[i][j] < d[j])
                    {
                        d[j] = d[i] + w[i][j];
                        parent[j] = i;
                    }
                }
            }
        }
    }
}

void path()
{
    int path[node_size];
    for (int i = 0; i < node_size; i++)
    {
        path[i] = -1;
    }

    // 終點
    path[node_size - 1] = dest;

    // 下一個路徑上上個路徑的父節點
    for (int i = node_size - 1; i >= 0; i--)
    {

        // parent[source]=source
        // 當到 source 時會一直在 source
        // 所以 path 到 souce 時就結束了，直接跳出去
        if (source == path[i])
        {
            break;
        }
        else
        {
            // 下一個路徑上上個路徑的父節點
            path[i - 1] = parent[path[i]];
        }
    }

    for (int i = 0; i < node_size; i++)
    {
        if (path[i] != -1)
        {

            cout << path[i];
            if (i != node_size - 1)
            {
                cout << " -> ";
            }
        }
    }
}

:::
## 期中考

:::info
* The unit of communication at the physical layer is a **bit.**
* The unit of communication at the data link layer is a **frame.**
* The unit of communication at the network layer is a **datagram.**
* The unit of communication at the transport layer is **a segment, user datagram, or a packet**, depending on the specific protocol used in this layer.
* The unit of communication at the application layer is a **message**.
:::
:::info
* The physical layer
* The physical layer required to carry a bit stream over a physical medium
* data link layer
* move data into and out of physical link in the net work
* the data link layer oversees the delivery of the packet between two systems on the same subnet
* physical address
1. 用來決定在同個子網路中 frame 的傳送路徑
2. 同個子網路中不同device會被分到不同且唯一的 MAC address
* network later
* network layer is responsible for the ==source-to-destination delivery== of a packet, possibly across multiple networks (links)
* logical address
1. 在跨子網路的傳輸中決定傳送路線
* transport layer
* The transport layer is responsible for==process-to-process delivery==
* port address
1. The network layer gets each packet to the correct computer; the transport layer gets the entire message ==to the correct process== on that computer

* appliciation layer
* user interfaces


:::
:::info
* ==The physical addresses change from hop to hop,but the logical and port addresses usually remain the same.==
* **The least significant bit of the first byte** defines the type of **physiacl address**.If the bit is 0, the address is unicast; otherwise, it is multicast.
* The broadcast destination address is a special case of the multicast address in which all bits are 1s
:::


:::info
## net work device
* ==**bridges change collision domains, routers limit broadcast domains.**==
1.
* **repeater 不具有 filter 功能，增強電子訊號**
* **很多repeater組成collision domain**
2.
* **bridge 有 filter 功能 在子網利用physical address(mac address)決定傳送路徑**
* **很多collision collision domain 連至 bridge**
* **很多bridge 組成 broadcast domain(subnet 劃分broadcast domain)**
3.
* **在跨子網的router 利用phyiscal address (ip) 決定傳送路徑**
* **很多 broadcast domain 連至 router**

> ==*A bridge does not change the physical (MAC) addresses in a frame.
A router changes the physical addresses in a packet.*==


:::
:::info
## carrier sense multiple access with collision detection **(CSMA/CD)**
* ==the minimun frame size 是兩倍傳輸到終點的時間 * 傳輸速度==




:::
:::info
## CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)
1. **source 傳送 RTS 給 destination（Request to Send, RTS）**
2. **destination 傳送 CTS（Clear to Send, CTS） 給範圍內所有 devices 讓其他 device 不要傳送任何資料**
3. **source 收到 CTS 開始發送資料**
4. **destination 收完之後發送 ACK 告訴其他 device 可以開始傳送資料了**
5. 


:::

:::info
## bridge table

1. When station source sends a frame to station Dedtination
2. if the bridge does not have an entry for either Dedtination or source.
3. broadcast the frame
4. address 對的 dest 存取 , 其他 discard 掉
5. bridge 會知道 source 是從哪個 port 來的 , 記在 table 裡


:::

:::info

## classful ip address
:::
:::info

## clessless address
:::
:::info

* ==Limited broadcast== is the broadcast limited to a single LAN and which is to be received by all. It is sent to reserved Class E , IP address ==255.255.255.255==. The destination MAC address for such frames will be FF:FF:FF:FF:FF:FF.  ==The router simply drop the Limited broadcast address and does not forward it==.

* ==Direct Broadcast Address== (with the ==suffix set all to 1s==)
* ==Directed Broadcast address== is the local subnet broadcast address. If the subnet is 192.168.10.0 , the directed broadcast address will be 192.168.10.255 , which will be heard by all in the same subnet hosts. ==The router will receive such packet and process it.== The  destination mac address will still be FF:FF:FF:FF:FF:FF, as it is to be received by all hosts.
:::

:::info
## connection-oriented network

1. source 傳 ==request packet== 給 dest
2. R1 assign ==incoming label== 給 incoming port
3. R2 R3 ... 重複此動作到 Rn to dest
4. dest 將 ==respond packet== 回傳
5. Rn 收到後將 ==outgoing lable== 給該 port , 並將 incoming port 傳給 Rn-1 作為 Rn-1 的 outgoing port , 重複動作直到 source 收到 outgoing port
6. 連線建立完成

* source 沿建立好的連線把資料傳至 dest
* 傳完之後 source 傳==teardown packet== 給 dest
* dest 收到後回傳 ==confirmation message== 沿著所建立的連線將 label 刪除




:::

:::info
## direct delivery / indirect delivery

* direct delivery(datagram transport in same subnet)
* indirect delivery(datagram transport in different subnet)
* **to distinguish -> two ip & their mask ， if result is same direct delivery**
* The sender can easily determine if the delivery is direct. It can extract the network address of the destination (using the mask) and compare this address
:::
:::info
## NAT

### NAT table with only IP address

### NAT table with IP address & port address

:::

:::info
## Address aggregation

* beasuse **Address aggregation** the classless routeing table need to be **==write from top to down by netmask length==** ，because the **ip with longer mask may be an exception**



:::
:::info
## routing table

if 我有這個目的地的路由
從路由表中取得下一站的位址
將封包傳給下一站
else
決定目的地網路號碼

    if 我有這個網路的界面
    決定我的界面上這個網路的子網路遮罩
    else
    從這個網路的層級決定它的子網路遮罩
    endif
    
    利用遮罩套在目的地位址上﹐取得子網路
    
    if 我有這個子網路的界面
    將封包直接送往目的地
    else if 我的路由表格包含這個子網路的記錄
    從路由表格中取得下一站的位址
    將封包傳給下一站
    else if 我的路由表格中有一筆預設路由
    從路由表格中取得下一站的位址
    將封包傳給下一站
    else
    宣佈這個目的地無效
    endif
endif


:::

:::info
## IP datagram


* VER :
* ipv4 ipv6
* HELN :
* ==unit of 4-bite== defines the total length of the datagram header in 4-bit words(When there are no options, the header length is 20 bytes, and the value of this field is 5 (5 × 4 = 20))
* service type :
* service quility
* Total length :
* Length of data = total length − header length

> Though a size of 65,535 bytes might seem large, the Ethernet protocol has a minimum and maximum restriction on the size of data that can be encapsulated in a frame (46 to 1500 bytes). The datagram must be fragmented to be able to pass through those networks.
*L2 frame*

* Identification :
* identifies a datagram originating from the source host
* flag :
* **The third bit** is called the more fragment bit. If its value **is 1, it means the datagram is not the last fragment**; there are more fragments after this one. If its value is 0, it means this is the last or only fragment
* Fragmentation offset :
* It is the offset of the data in the original datagram measured in ==units of 8 bytes==
* Protocol :
* This 8-bit field defines the higher-level protocol that uses the services of the IP layer.
* Checksum :
* source ，destination :
* ==must remain unchanged during the time the IP datagram travels from host to host.==

:::
:::info
## fragmentation
Ethernet LAN is 1500 bytes,the maximum length of the IP datagram equal to 65,535 bytes, ==divide the datagram to make it possible to pass through these networks==. This is called fragmentation.

> Fragmentation offset : It is the offset of the data in the original datagram measured in ==units of 8 bytes==

:::
:::info

* Record-Route Option : the router adds the IP address of its interface from which the datagram is leaving

> 記 outgoing port

* Strict-source-route option

> Strict-source-route vs loose-source-route
> * Strict-source-route just can go through the router where it list
> * loose-source-route will go through router it list , but router to router might go through other router which it doesn't list

:::
:::info
## ARP
ARP accepts a logical address from the IP protocol, maps the address to the corresponding physical address and pass it to the data link layer.

1. A asking the ARP protocol to send a broadcast **ARP request(1)** packet
2. System B sends an **ARP reply(2)** packet that includes its physical address

==An **ARP request** is broadcast; an **ARP reply** is unicast.==



:::
:::info
## proxy ARP
the router acts on behalf of all of the hosts installed on the subnet. ==When it receives an ARP request with a target IP address that matches the address of one of its protégés== (141.23.56.21, 141.23.56.22, and 141.23.56.23),==it sends an ARP reply== and announces its hardware address as the target hardware address. When the router receives the IP packet, it sends the packet to the appropriate host.


:::
:::info
## Internet Control Message Protocol (ICMP)

> the first 8 bytes provide information about the port numbers (UDP and TCP) and sequence number (TCP)
:::
:::info
### ICMP type 3(destination-unreachable)
:::
::: info
### ICMP type 4(source quench)
:::
::: info
### ICMP type 11(time-exceeded)
:::
::: info
### ICMP type 12(Parameter Problem)
參數錯誤
:::
::: info
### ICMP type 5(Redirection)
:::

:::info
### **ICMP type 0 or 8(Echo-request and echo-reply messages)**

> 不管在往上能不能運作
:::
:::info
### **ICMP type 13 or 14(Timestamp-request and timestamp-reply message)**



:::
in window
1. Initialize wsa variable
2.
## [send()/recv() ](https://beej-zhtw-gitbook.netdpi.net/system_call_huo_bust/send_yu_recv__bao_bei_ff0c_wo_men_lai_liao_tian_ff01)
* **int send(int sockfd, const void msg, int len, int flags);**
sockfd 是你想要送資料過去的 socket descriptor（無論它是不是 socket() 傳回的，或是你用 accept() 取得的）
* **int recv(int sockfd, void *buf, int len, int flags);**;
sockfd 是要讀取的 socket descriptor
## [thread](https://shengyu7697.github.io/std-thread/)
* c++ std::thread 的建構子可以傳入 class 類別的函式，如下範例所示，
AA::start 分別建立 t1、t2 兩個執行緒，而 t1 建構子帶入 AA::a1 類別函式，AA::a1 前面記得要加上&，第二參數代表的是哪個類別，之後的參數為帶入類別函式的參數就像 t2 這樣。

#include <iostream>
#include <thread>

class AA {
public:
    void a1() {
        std::cout << "a1\n";
    }

    void a2(int n) {
        std::cout << "a2 " << n << "\n";
    }

    void start() {
        std::thread t1(&AA::a1, this);
        std::thread t2(&AA::a2, this, 10);

        t1.join();
        t2.join();
    }
};

int main() {
    AA a;
    a.start();

    return 0;
}

## [多執行序](https://www.796t.com/content/1549624162.html)
## [socket(domain, type, protocol)](http://www.tsnien.idv.tw/Internet_WebBook/chap8/8-5%20Socket%20%E5%BA%AB%E5%AD%98%E5%87%BD%E6%95%B8.html)
(A) **domain 參數**

參數 domain 或稱為 family，是用來選擇使用哪一種通訊協定的家族系列，domain 可選擇下列之一：

● AF_UNIX：Unix Internet Protocol。此通訊家族並不是真正的網路通訊協定，而是用來作 Unix 作業系統中，各程序（Process）之間的通訊使用。一般使用在回授（Loopback）傳輸提供者，而其應用在主機內程序之間的通訊。

● AF_INET：Internet Protocol。此為 TCP/IP 的 Internet 通訊協定，傳輸提供者可能是 TCP 或 UDP，也是本章討論的重點。

● AF_NS：Xerox NS Protocol。此為 Xerox 公司發展的通訊協定。

● AF_IMPLINK：Interface Message Protocol。此為一種智慧型的分封交換節點協定，這些節點都是使用點對點的連接方式，一般使用在租用電話線路來作資料傳輸使用。（不在本章討論範圍）

其中『AF_』代表 Address Family，有些系統使用『PF_』（Protocol Family），兩者是相通的。domain 參數也如同 sockadd_in 資料結構中的 sin_family 參數一樣。

(B) **type 參數**

參數 type 是設定該 Socket 的類型，可選擇下列類型之一：

● SOCK_STREAM：Stream Socket。傳輸提供者提供一個虛擬電路服務（TCP）。

● SOCK_DGRAM：Datagram Socket。提供電報傳輸服務（UDP）。

● SOCK_RAW：Raw Socket。通訊協定型態在傳輸層之下，譬如，在 AF_INET（傳輸層為 TCP 或 UDP）模式，SOCK_RAW 的通訊協定可以是 IP（Internet Protocol）或 ICMP（Internet Control Message Protocol）。

● SOCK_SEQPACKET：Sequenced Packet Socket。提供虛擬電路（TCP）並附有維護訊息的功能。

(C) **protocol 參數**

參數 protocol 是在某一個 domain 之下，選擇所要哪一種協定。例如選定 AF_INET domain 系列時，所使用的協定可以是 TCP、UDP 或 IP中的一種。但當設定 domain 和 type 值時，對於所使用的協定大多已經指定完成，因此 protocol 的值一般都設定為0。但有一特殊情況，如果 Socket 的型態是 SOCK_RAW 時，必須在參數中指定它的上層協定為 TCP、UDP、IP 或 ICMP。

inet_addr()便負責將字串型式的IP轉換為整數型式的IP