# 計算機網路概論 ## Chapter 1 Introduction ### 1.1 what is the Internet?  Internet: “network of networks”連接所有區域網路的網路:網際網路 Internet standards • RFC: Request for comments • IETF: Internet Engineering Task Force protocols define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt protocols:雙方溝通的一種標準格式，就像一種語言 ### 1.2 network edge 無線網路分為2種:  packet transmission delay:  固體傳輸介質:銅copper、光纖fiber、同軸電纜coax twisted pair (TP)雙絞線: * Category 5: 100 Mbps, 1Gbps Ethernet * Category 6: 10Gbps coaxial cable同軸電纜: * two concentric copper conductors兩根同心銅導體 * bidirectiona雙向的 * broadband: * multiple channels on cable * HFC混合光纖同軸 fiber optic cable光纖: * glass fiber carrying light pulses, each pulse a bit * high-speed operation: * high-speed point-to-point transmission (e.g., 10’s-100’s Gbps transmission rate) * low error rate: * repeaters spaced far apart中繼器相距很遠 * immune to electromagnetic noise不受電磁干擾 radio: propagation environment effects: * reflection * obstruction by objects * interference  ### 1.3 network core Packet-switching: store and forward: entire packet must arrive at router before it can be transmitted on next link整個數據包必須先到達路由器，然後才能在下一個鏈路上傳輸 end-end delay = 2L/R  queuing and loss: * if arrival rate (in bits) to link exceeds transmission rate of link for a period of time: * packets will queue, wait to be transmitted on link * packets can be dropped (lost) if memory (buffer) fills 如果內存（緩衝區）已滿，則數據包可能會被丟棄（丟失） circuit switching: 電路交換要求必須首先在通信雙方之間建立連接通道。在連接建立成功之後，雙方的通信活動才能開始。 通信活動的過程中，連接將始終佔用著通信系統分配給它的資源（通道、頻寬、時隙、碼字等等）(no sharing) dedicated resources: no sharing * circuit-like (guaranteed) performance * circuit segment idle if not used by call (no sharing * commonly used in traditional telephone networks Packet switching versus circuit switching: packet switching allows more users to use network!通常用戶只有10%時間是在傳輸的。 要如何讓每個ISP都能互相連通呢? 第一種方法:  可是這樣很麻煩，需要接一堆線，統一送到一個地方轉發較好 第二種方法:  如果有多個global isp那它們之間就要互連Internet exchange point  ISP也有層級的概念  ### 1.4 delay, loss, throughput in networks 經過某個節點所需delay共有四種  Queueing delay  使用`traceroute`指令可以看到封包經過哪些IP 轉發裝置的queue (aka buffer)被塞滿後，再寄進去的封包就會移失 蠻好理解的，傳輸頻寬會是中途經過的機器中最小的。  ### 1.5 protocol layers, service models 網路分層:   封包經過的路徑就長這樣  ### 1.6 networks under attack: security malware惡意軟體分為以下: * virus: self-replicating infection by receiving/executing object (e.g., e-mail attachment)附在別的軟體、檔案裡的病毒 * worm: self-replicating infection by passively receiving object that gets itself executed獨立出來的惡意軟體 * spyware malware can record keystrokes, web sites visited, upload info to collection site監聽、偷取個資... * botnet, used for spam. DDoS attacks殭屍網路，發大量請求，癱瘓系統 ## Chapter 2 Application Layer ### 2.1 principles of network applications 使程式更加好寫 不需要從網路核心開始實作，直接 call function 優勢： 可在不同裝置 (end-system) 上運行 網路通訊 possible structure of applications: * client-server * peer-to-peer (P2P) server通常有以下幾個特性: * always-on host * permanent IP address * data centers for scaling clients通常有以下幾個特性: * communicate with server may be intermittently connected * may have dynamic IP addresses * do not communicate directly with each other P2P architecture: * no always-on server * arbitrary end systems directly communicate * peers request service from other peers, provide service in return to other peers * self scalability – new peers bring new servicecapacity, as well as new service demands * peers are intermittently connected and change IP addresses * complex management Socket: process sends/receives messages to/from its socket, by transport infrastructure 網路插座（英語：Network socket；又譯網路插座、網路介面、網路插槽）在計算機科學中是電腦網路中行程間資料串流的端點。使用以網際協定（Internet Protocol）為通訊基礎的網路插座，稱為網際插座（Internet socket）。因為網際協定的流行，現代絕大多數的網路插座，都是屬於網際插座。 socket是一種作業系統提供的行程間通訊機制。 在作業系統中，通常會為應用程式提供一組應用程式介面（API），稱為插座介面（英語：socket API）。應用程式可以通過插座介面，來使用網路插座，以進行資料交換。最早的插座介面來自於4.2 BSD，因此現代常見的插座介面大多源自Berkeley插座（Berkeley sockets）標準。在插座介面中，以IP位址及通訊埠組成插座位址（socket address）。遠端的插座位址，以及原生的插座位址完成連線後，再加上使用的協定（protocol），這個五元組（five-element tuple），作為插座對（socket pairs），之後就可以彼此交換資料。例如，在同一台電腦上，TCP協定與UDP協定可以同時使用相同的port而互不干擾。 作業系統根據插座位址，可以決定應該將資料送達特定的行程或執行緒。這就像是電話系統中，以電話號碼加上分機號碼，來決定通話物件一般。  IP地址是否足以識別該進程process？ 答:不，許多進程可以在同一主機上運行 example port numbers: * HTTP server: 80 * mail server: 25 What transport service does an app need? * data integrity資料完整性 * throughput吞吐量 * timing延遲時間 * security安全性 ### 2.2 Web and HTTP  RTT（定義）：數據包從客戶端到服務器再返回的時間 Non-persistent HTTP: response time * one RTT to initiate TCP connection * one RTT for HTTP request and first few bytes of HTTP response to return * file transmission time * non-persistent HTTP response time = 2RTT+ file transmission time * non-persistent HTTP: one TCP connection send at most one object, connection close right after server responsed * one RTT build TCP connection + one RTT for HTTP request + file transmission time * persistent HTTP: send multiple object at one TCP connection * one RTT build TCP connection + one RTT for request x N files + file transmission time Nonpersistent HTTP：當每傳送一個物件，TCP connection就必須做一次，假設client跟server要求多個檔案，當第一個檔案傳輸後 會關閉連線，要下載第二個檔案的時候 必須再對server做一次要求(要求->回應->接收 整個步驟都會重新做)。這種模式主要為HTTP1.0使用，相較於HTTP1.1 較費時，因為有一部份的時間都花在建立連線上。 Persistent HTTP：接收多個物件時，client只需要向server建立一次連線即可，較省時。主要為HTTP1.1使用。 two types of HTTP messages: request, response  POST method:類似表單形式放在body裡上傳，較隱私 * web page often includes form input * input is uploaded to server in entity body URL method:資料是加在網址裡的，無隱私 * uses GET method * input is uploaded in URL field of request line: > `http://www.somesite.com/animalsearch?monkeys&banana`   HTTP response status codes: * 200 OK * request succeeded, requested object later in this msg * 301 Moved Permanently * requested object moved, new location specified later in this msg(Location:) * 400 Bad Request * request msg not understood by server * 404 Not Found * requested document not found on this server * 505 HTTP Version Not Supported many Web sites use cookies four components: 1. cookie header line of HTTP response message 2. cookie header line in next HTTP request message 3. cookie file kept on user’s host, managed by user’s browser 4. back-end database at Web site when initial HTTP requests arrives at site, site creates: * unique ID * entry in backend database for ID what cookies can be used for: * authorization * shopping carts * recommendations * user session state (Web e-mail) Web caches (proxy server):暫存最近下載的檔案，如果有人要存取，就不用再從原server拿，加快速度，減輕原server負擔，通常proxy server會架在離用戶端較近的地方。 ### 2.3 electronic mail SMTP, POP3, IMAP SMTP(Simple Mail Transfer Protocol) mail agent, mail box(in), message queue(out) The client SMTP will establish a TCP connection to port 25 at the server SMTP. persistent connections three phases of transfer * handshaking (greeting) transfer of messages closure * commands:ASCII text * response:status code and phrase * messages must be in 7-bit ASCI SMTP 是 push protocol, 即 TCP 連線是由想要送出檔案的主機所建立 HTTP 是 pull protocol, 即 TCP 連線是由想要接收檔案的主機所建立  簡單地說，SMTP管『發』，POP3/IMAP管『收』。 POP與IMAP有什麼區別 POP3協議允許電子郵件客戶端下載伺服器上的郵件，但是在客戶端的操作（如移動郵件、標記已讀等），不會反饋到伺服器上，比如通過客戶端收取了郵箱中的3封郵件並移動到其他文件夾，郵箱伺服器上的這些郵件是沒有同時被移動的 。 而IMAP提供webmail 與電子郵件客戶端之間的雙向通信，客戶端的操作都會反饋到伺服器上，對郵件進行的操作，伺服器上的郵件也會做相應的動作，同時，IMAP像POP3那樣提供了方便的郵件下載服務，讓用戶能進行離線閱讀。IMAP提供的摘要瀏覽功能可以讓你在閱讀完所有的郵件到達時間、主題、發件人、大小等信息後才作出是否下載的決定。此外，IMAP 更好地支持了從多個不同設備中隨時訪問新郵件。  總之，IMAP 整體上為用戶帶來更為便捷和可靠的體驗。POP3 更易丟失郵件或多次下載相同的郵件，但 IMAP 通過郵件客戶端與webmail 之間的雙向同步功能很好地避免了這些問題。 ### 2.4 DNS 將域名轉為IP位址的系統 * distributed database implemented in hierarchy of many name servers分布式server  Load distribution: 一個網站可能有多台伺服器 每個伺服器的 ip 和主機名稱不同 有要求傳送過來時 dns 會一直改變回傳的伺服器的主機名稱及 ip 這樣就不會有許多要求都由同一伺服器回應 可達到分配效果 Top-level domain (TLD) servers: 負責 Top-level domain 如 com, org, net, edu 也負責國家級的 Top-level domain 如 uk, fr, ca, jp Authoritative DNS servers: organization’s own DNS server Local DNS name server:DNS版的proxy server iterated query: “I don’t know this name, but ask this server”  recursive query don’t temperaly return to local DNS server  * cache entries timeout (disappear) after some time (TTL) * TLD servers typically cached in local name servers * thus root name servers not often visited * cached entries may be out-of-date record resource records (RR) 格式: (name, value, type, TTL) TTL(time to live) 欄位中 name 和 value 由 type 決定 Type=A : name 是正規主機名稱，value 是正規主機名稱為 name 的 IP address ex:(relay1.bar.foo.com , 145.37.9.126 , A) Type=CNAME : name 是主機別名，value 是別名為 name 的正規主機名稱 ex:(foo.com , relay1.bar.foo.com ,CNAME) Type=NS : name 是 domain (網域名稱), value 是 domain 為 name 的 Authoritative (官方) DNS server 名稱，此 Authoritative (官方) DNS server 會去取得該網域內的主機 ip 位置 ex:(foo.com , dns.foo.com , NS) Type=MX : name 是主機別名，value 是主機別名為 name 的 mail server 正規名稱 ex:(foo.com , mail.bar.foo.com , MX) ### 2.6 video streaming and content distribution networks (CDNs) DASH: Dynamic, Adaptive Streaming over HTTP * server: * divides video file into multiple chunks * each chunk stored, encoded at different rates * manifest file: provides URLs for different chunks * client: * periodically measures server-to-client bandwidth * consulting manifest, requests one chunk at a time * chooses maximum coding rate sustainable given current bandwidth * can choose different coding rates at different points in time (depending on available bandwidth at time) * CDN: stores copies of content at CDN nodes * e.g. Netflix stores copies of MadMen  ### 2.7 socket programming with UDP and TCP socket: door between application process and endend -transport protocol  Two socket types for two transport services: * UDP: unreliable datagram * TCP: reliable, byte stream-oriented #### Socket programming with UDP UDP: no “connection” between client & server * no handshaking before sending data * sender explicitly attaches IP destination address and port # to each packet * receiver extracts sender IP address and port# from received packet UDP: transmitted data may be lost or received out-of-order Application viewpoint: * UDP provides unreliable transfer of groups of bytes (“datagrams”) between client and server  #### Socket programming with TCP client must contact server * server process must first be running * server must have created socket (door) that welcomes client’s contact client contacts server by: * Creating TCP socket, specifying IP address, port number of server process * when client creates socket: client TCP establishes connection to server TCP * when contacted by client, server TCP creates new socket for server process to communicate with that particular client * allows server to talk with multiple clients * source port numbers used to distinguish clients (more in Chap 3) application viewpoint: * TCP provides reliable, in-order byte-stream transfer (“pipe”) between client and server    ## Chapter 3 Transport Layer ### 3.1 transport-layer services provide logical communication between app processes running on different hosts * network layer: logical communication between hosts * transport layer: logical communication between processes * relies on, enhances,network layer services  ### 3.2 multiplexing and demultiplexing  * host uses IP addresses & port numbers to direct segment to appropriate socket * recall: created socket has host-local port #: > DatagramSocket mySocket1 = new DatagramSocket(12534); * IP datagrams with same dest. port #, but different source IP addresses and/or source port numbers will be directed to same socket at dest TCP socket identified by 4-tuple: * source IP address * source port number * dest IP address * dest port number ### 3.3 connectionless transport: UDP “best effort” service, UDP segments may be: * lost * delivered out-of-order to app connectionless: * no handshaking between UDP sender, receiver * each UDP segment handled independently of others UDP use: * streaming multimedia apps (loss tolerant, rate sensitive) * DNS * SNMP reliable transfer over UDP: * add reliability at application layer * application-specific error recovery!   ### 3.4 principles of reliable data transfer top-10 list of important networking topics! reliable data transfer protocol (rdt) * use finite state machines (FSM) to specify sender, receiver  https://blog.csdn.net/qq_33936481/article/details/53152903 #### rdt1.0: reliable transfer over a reliable channel rdt1.0是假設使用最可靠的通道情況。主要有傳輸端與接收端兩個部分，資料傳輸方式很單純，傳輸端等待上層傳資料進來，收到上面的資料以後裝成封包送出去。 接收端收到封包以後，將封包解開，把訊息往上送  #### rdt2.0: channel with bit errors 2.0考慮到了資料錯誤的情形，當接收端收到資料，會有ACK(相當於OK)與NAK(相當於Send Again)兩種訊息，當資料接收到以後確認無誤，會送ACK給來源已確定資料無誤。當偵測到錯誤時 會傳回NAK通知來源端再送一次。    無錯誤場景  有錯誤的場景   #### rdt2.1: sender, handles garbled ACK/NAKs 2.1新增了sequence number，同樣使用ACK與NAK來確認訊息，封包的號碼可以用來確認是否重新傳輸封包。 例如接收端在等待編號0的封包，結果收到封包1，此時會回傳ACK1給來源端，而正在等候ACK0的來源端收到ACK1 表示封包0可能遺失，所以會再重送封包0。 sender:  receiver:   #### rdt2.2: a NAK-free protocol 一次使用兩種確認訊息 處理起來比較費力，因此2.2中移除NAK的訊息，在ACK中加入編號 就可以達到確認與否認的效果 * instead of NAK, receiver sends ACK for last pkt received OK * receiver must explicitly include seq # of pkt being ACKed * duplicate ACK at sender results in same action as NAK: retransmit current pkt  #### rdt3.0: channels with errors and loss 3.0同時考慮到封包遺失與資料錯誤的情形，除了使用ACK機制，另外在傳送端多了倒數計時器，封包送出去如果超過時間仍未收到ACK或是收到不正確編號的ACK，則再送出封包一次。      utilization:使用率 rdt3.0雖然確保了資料的可靠性，可是它採用Stop-and-Wait機制，效能方面無法讓人接受，因為送出封包後必須等待對方回應才能繼續傳送，假如連線Delay太長，整體效率會嚴重低落。 為解決這問題，後來發展出 Pipelined Protocol，可以讓傳送端同時傳送多個封包不需等待確認相對的，傳輸端與接收端都必須增加封包的暫存空間與序列號碼。當其中的封包出現錯誤時有不同的回覆方法，主要有Go-Back-N(GBN)與Selective Repeat(SR)兩種方法 https://blog.yfxie.com/comparison-of-network-gbn-sr-and-tcp/ #### Go-Back-N(GBN) 傳輸多個封包必須有個暫存的區域，暫存的區域中存在著窗格大小(Window Size) N，存放著各種封包(已確認、已送出但未收到ACK、未送出的封包等等)。 接收端也會開啟窗格來接收封包，會記著目前收到封包的編號，假設收到順序不對的封包N+1(等待接收第N個，下一個傳來的卻是第N+1號)，會將N以後的封包全部丟棄，此時傳送端一直沒收到ACK(N)，會把N號以後的封包全部重新傳送出去。  sender:  receiver:    GBN 傳送端重點 * 累積式確認：收到來自接收端回傳序號 n 的 ACK，表示小於 n 的封包都已經正確收到。 * 使用一個 Timer：綁定最早送出且未經確認的封包(Base)。 * 逾時事件：Timeout 時，若還未收到最早送出封包所回傳的確認，則重送所有未經確認的封包 base ~ (nextseqnum - 1)。 * 收到順序不正確的 ACK：不做任何事情。 * 收到順序正確的 ACK： 1. 將 base 設定為 ACK 的序號+1，造成窗格滑動，因此又稱 窗格滑動協定(Sliding-Window)。 2. 若還有可用封包可傳送的請況下，則重新啟動Timer。 3. 傳送新的封包 GBN接收端重點 * 收到正確順序的封包事件：回傳該封包序號的 ACK 給傳送端。 * 收到錯誤順序的封包事件：回傳最後一次收到正確序號的 ACK 給傳送端。 #### Selective Repeat(SR) GBN的傳送方法往往會造成不必要的重複，因此SR的傳送方法就是只針對未收到的封包做重新傳輸的動作。首先規劃出大小為N的窗格來限制大小，窗格的基底會停留在最近一個尚未收到ACK的封包區域，當封包時間逾時會重新送出封包，直到收到該封包的ACK 窗格基底才會往前移動。    SR(Selective Repeat) 選擇性重複 * SR 傳送端只重送接收端未正確收到的封包，可能是遺失或毀損。 * SR 會將脫序的封包暫存。 * SR 的傳送端、接收端雙方的 window 位置 各自不同。 * SR 窗格大小必須等於有限序號大小的一半。 SR傳送端重點 * 逾時事件：每個封包都綁有 timer，當各個封包的 ACK 逾時未收到，則重送該封包。 * 收到 ACK： 1. 標記對應序號的封包為已確認。 2. 若收到的 ACK 序號是 Base，則將 Base 移動到下個最小未經確認的封包上。 3. 若窗格移動到了尚未傳送的封包上，則同時送出這些未被送出的可用封包。 SR接收端重點 * 接收到目前 window 內任一封包： 1. 回傳收到的序號之 ACK 給傳送端。 2. 若收到的序號不是 base，則將封包暫存。 3. 若收到的序號是 base，將 base 與其後連續已收到的封包交由上層，並將 window 移動到最小預期收到的 位置上。例如：接收端窗格為 0、1、2、3、4，此時收到 1、2、3，將它們暫存起來，之後收到 0(base) ，則將 0、1、2、3 一次交給上層，並將 window 移動到4。 * 收到 window 之前的封包事件：再傳一次收到的序號之 ACK 給傳送端，倘若不傳，傳送端的 window 將永遠無法移動。 (之所以收到 window 之前的封包，表示上一次回傳給傳送端的 ACK 可能遺失了， 使得傳送端等到 timeout 仍沒收到 ACK 才再發一次之前的封包過來。) * 收到其它封包的事件：忽略該封包。 ### 3.5 connection-oriented transport: TCP  藍色的部分代表已確認收到但還沒送到應用層，黃色的部分代表Recieve Window，是等待被接收的封包，藍色加上黃色的部分是**接收緩衝區大小(rwnd)**。  藍色部分為已傳送但尚未被確認的，黃色部分為準備傳送，紅色部分為等待被放進Send Window，三個部分加起來是發送緩衝區大小。 傳送段會從ACK接收到現在的rwnd是多少，以此來決定Send Window應往右選幾格，也就是Sliding Window，如果接收端有問題就回直接回傳rwnd=0，傳送方就會停止傳送了，直到收到rwnd!=0為止。                 ## Chapter 4 Network Layer: The Data Plane Data Plane ### 4.1 Overview of Network layer * Data Plane一般用來將路由器裡的包從 Input 送到 Output，這個過程叫做 Forwarding。 * Control Plane 用於將包從一個路由器發到另一個路由器，這個過程叫做 Routing。  ### 4.2 What’s inside a router   ternary content addressable memories (TCAMs)        ### 4.3 IP: Internet Protocol  router只做切割，不負責合併，合併由最後host的IP層完成，然後傳到TCP層         NAT is controversial: * routers should only process up to layer 3 * address shortage should be solved by IPv6 * violates end-to-end argument * NAT traversal: what if client wants to connect to server behind NAT? * 手動修改router的translation table IPv6 datagram format: • fixed-length 40 byte header • no fragmentation allowed     ## Chapter 5 Network Layer: The Control Plane ### 5.2 routing protocols        https://www.itread01.com/hkcxqey.html