計算機網路(上)

Chap01 Introduction

Terminologies

connected computing devices

  • hosts: end systems
    • running network apps
    • sends packets of data
    • breaks message into smaller chunks, known as packets
  • bandwidth: transmission rate
    • link capacity(maximum rate)
    • link bandwidth(available rate)
  • Packet switches: forward packets(chunks of data) by routers and switches
  • protocols: define format, order of messages sent and received and actions taken on message transmission and receive
    • TCP, IP, HTTP, Skype, 802.11
  • Internet standards
    • RFC: Request for comments
    • IETF: Internet Engineering Task Force
  • Internet
    • network of networks
    • Interconnected ISPs
    • Infrastructure that provides services to applications
      • Web, VoIP, email, games…
    • provides programming interface to apps

Network Structure

  • network edge
    • hosts: clients and servers(often in data centers)
  • network core
    • interconnected routers, network of networks
  • access networks, physical media
    • wired, wireless communication links

Access Network

digital subscriber line (DSL)

DSL透過電話線的附加頻段在話音訊帶上傳送大量資料
typically (< 1 Mbps/< 10 Mbps)

cable network

unlike DSL, which has dedicated access to central offic

frequency division multiplexing: different channels transmitted
in different frequency bands
將多路基頻訊號調製到不同頻率載波上再進行疊加形成一個複合訊號

HFC: hybrid fiber coax(混合式光纖同軸電纜)
其主幹是光纖(Fiber)網路(fiber attaches homes to ISP router),末端枝幹是雙向同軸電纜線(Coaxial Cable)
在主幹網路上,每條光纖採用環狀結構連接,確保一條網路斷線時,另外一條網路仍能傳遞資料,以光波傳輸訊號,傳輸距離長,提供高速連接至光纖節點(Fiber node),由光接收機將光訊號轉為電視訊號,再改經同軸電纜傳送至用戶終端。HFC 網路的頻寬達750MHz,以6MHz來劃分整體的頻道,可容納高達110個類比視訊頻道,或1000個數位節目。

asymmetric: up to 30Mbps/2 Mbps
homes share access network to cable headend

home network

Enterprise access networks (Ethernet)

  • 一種電腦區域網路組網技術(IEEE 802.3),它規定了包括實體層的連線、電訊號和介質存取層協定的內容
  • typically used in companies, universities
  • today, end systems typically connect into Ethernet switch

Wireless access networks

connect via base station aka “access point”

  • wireless LANs:
    • within building (100 ft)
    • 802.11b/g (WiFi): 11/54 Mbps transmission rate
  • wide-area wireless access
    • provided by telco (cellular蜂巢式) operator, 10’s km and 1~10 Mbps
    • 3G, 4G(速度,範圍): LTE

Physical media

  • twisted pair (TP, 雙絞線): two insulated copper wires
    Category 5: 100 Mbps, 1 Gpbs Ethernet
    Category 6: 10Gbps
    是由兩條相互絕緣的導線按照規格互相纏繞在一起而製成,屬於資訊通訊網路傳輸介質。
  • coaxial cable(同軸電纜):
    • two concentric(同心) copper conductors
    • bidirectional
    • broadband(寬帶): multiple channels on cable
  • HFC Hybrid Fiber Coaxial(as above)
  • fiber optic cable: glass fiber carrying light pulses
    • high-speed(10’s-100’s Gpbs) point-to-point transmission
    • low error rate: immune to electromagnetic noise
  • radio
    • no physical wire , bidirectional
    • propagation(傳播) environment effects:
      • reflection
      • obstruction(妨礙) by objects
      • interference
    • radio link types:
      • terrestrial(地面波) microwave - up to 45 Mbps channels
      • LAN (e.g., WiFi) - 11Mbps, 54 Mbps
      • wide-area (e.g., cellular) - 3G cellular: ~ few Mbps
      • satellite - Kbps to 45Mbps channel (or multiple smaller channels)
        • 270 msec end-end delay

The network core: interconnected routers

packet-switching: hosts break application-layer messages into packets

forward packets from one router to the next, across links on path from source to destination

Two key network-core functions

routing: determines source-destination route taken by packets
routing algorithms
forwarding: move packets from router’s input to appropriate router output

circuit switching

電路交換要求必須首先在通信雙方之間建立連接通道。在連接建立成功之後,雙方的通信活動才能開始。
通信活動的過程中,連接將始終佔用著通信系統分配給它的資源(通道、頻寬、時隙、碼字等等)(no sharing)
circuit segment idle if not used by call (no sharing)
Commonly used in traditional telephone networks
多工:FDM & TDM

packet switching

封包在節點間單獨路由,不需要在傳輸前先建立通訊路徑
store and forward: entire packet must arrive at router before it can be transmitted on next link
If arrival rate exceeds transmission rate of link:

  1. packets will queue, wait to be transmitted on link
  2. packets will be lost if memory(buffer) fills up

why packet switching better than circuit switching

  1. packet switching allows more users to use network!
    Ex.
    1 Mb/s link
    each user is [100 kb/s when “active”] and [active 10% of time]
    with 35 users, probability > 10 active at same time is less than .0004(計算的機率)
  2. great for bursty data(resource sharing)
  3. excessive congestion possible: packet delay and loss
    • need protocols needed for reliable data transfer, congestion control

Q: How to provide circuit-like behavior?
bandwidth guarantees needed for audio/video apps

Internet structure: network of networks

End systems connect to Internet via access ISPs (Internet Service Providers)
ISPs must be interconnected



IXP Internet exchange point


“tier-1” commercial ISPs (e.g., Level 3, Sprint, AT&T, NTT), national & international coverage
content provider network (e.g, Google): private network that connects it data centers to Internet, often bypassing tier-1, regional ISPs

packet delay

Four sources of packet delay


dproc: noda processing
check bit errors
determine output link
typically < msec

dqueue: queueing delay

dtrans: transmission delay(檔案傳輸)(受限於頻寬,一次只能傳送一定大小)
L: packet length (bits)
R: link bandwidth (bps)
dtrans = L/R

dprop: propagation delay(傳輸速度(約光速))
d: length of physical link
s: propagation speed in medium (~2x108 m/sec)
dprop = d/s

traceroute program: provides delay measurement from source to router along end-end Internet path towards destination

throughput: rate (bits/time unit) at which bits transferred between sender/receiver
instantaneous: rate at given point in time
average: rate over longer period of time
link on end-end path that constrains end-end throughput(被最慢的部分限制)

Protocol “layers”

AIR TRAVEL

layers: each layer implements a service
via its own internal-layer actions
relying on services provided by layer below

  1. explicit structure allows identification, relationship of complex system’s pieces
  2. modularization eases maintenance, updating of system
    change of implementation of layer’s service transparent to rest of system(不互相影響)
    e.g., change in gate procedure doesn’t affect rest of system

layer model
Layer Model

  • application: supporting network applications
    • FTP, SMTP, HTTP
  • transport: process-process data transfer
    • TCP, UDP
  • network: routing of datagrams from source to destination
    • IP, routing protocols
  • link: data transfer between neighboring network elements
    • Ethernet, 802.11 (WiFi), PPP
  • physical: bits “on the wire”

iso layer model
ISO/OSI layer model (7 layers)
additional 2 layers

  • presentation: allow applications to interpret meaning of data
    • encryption, compression, machine-specific conventions
  • session: synchronization, checkpointing, recovery of data exchange

Internet stack “missing” these layers!
these services, if needed, must be implemented in application

Encapsulation

包裝好(加上header),運送,再拆封包
Encapsulation

Security

網路本無考慮安全性
本來的想法: 「互相相信的使用者組成的透明網路」

Bad guys: put malware into hosts via Internet

  • 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: can record keystrokes, web sites visited, upload info to collection site

被感染的電腦可當作botnet(彊屍電腦),用來寄垃圾郵件,或進行DDoS攻擊

Denial of Service (DoS): 控制多台電腦,持續提出要求,使伺服器癱瘓
attackers make resources (server, bandwidth) unavailable to legitimate traffic by overwhelming resource with bogus traffic

packet “sniffing ”(追蹤)
從 broadcast media (shared ethernet, wireless) 拿取目的地非自己的封包,以獲得資訊。(正常情況:丟棄)

IP spoofing(謊報)
send packet with false source address(假造他人名義送出封包)

History

1961-1972: Early packet-switching principles
1972:
NCP (Network Control Protocol) first host-host protocol
first e-mail program
ARPAnet has 15 nodes

1974:Cerf and Kahn - architecture for interconnecting networks
Cerf and Kahn’s internetworking principles define today’s Internet architecture:

  • minimalism, autonomy - no internal changes required to interconnect networks
  • best effort service model
  • stateless routers
  • decentralized control

1983:deployment of TCP/IP
1983:DNS defined for name-to-IP-address translation
1985:ftp protocol defined

early 1990s:Web
hypertext [Bush 1945, Nelson 1960’s]
HTML, HTTP: Berners-Lee
1994: Mosaic, later Netscape

late 1990’s: commercializationof the Web
instant messaging, P2P file sharing
network security to forefront

2005-present
Service providers (Google, Microsoft) create their own networks
Bypass Internet, providing “instantaneous”access to search, emai, etc.

Chap02 Application Layer

protocol

使程式更加好寫
不需要從網路核心開始實作,直接call function

優勢:
可在不同裝置(end-system)上運行
網路通訊

註:網路核心程式不會主動執行

structure

client-server structure

  • server:

    • always-on host
    • permanent IP address
    • data centers for scaling
  • clients:

    • communicate with server
    • may have dynamic IP addresses
    • do not communicate directly with each other(client間互相不知道)
      peer-to-peer (P2P) structure
  • no always-on server

    • arbitrary end systems directly communicate
  • peers both request services and provide services

  • self scalability(可擴展) – new peers bring new service capacity, as well as new service demands(愈多人加入,service功能相對應愈強)

  • complex management(not easy to implement)

Socket

  • process sends/receives messages to/from its socket, by transport infrastructure

Addressing processes
host device has unique 32-bit IP address
identifier (IP address and port numbers)
example port numbers:
HTTP server: 80
mail server: 25

Application layer protocol

define: when and how processes transfer messages

  • types of messages exchanged: e.g., request, response
  • message syntax: fields(欄位) in messages
  • message semantics: meaning of information in fields

Ex. HTTP, SMTP, Skype

transport service

  • data integrity(file transfer)
  • timing
  • throughput
    • multimedia vs elastic(有彈性的) apps
  • security

transport protocols services

TCP(transport layer)

  • reliable transport
  • flow control: sender won’t overwhelm receiver
  • congestion control(擁塞控制, 網路處理過多封包):throttle sender when network overloaded
  • connection-oriented(須先建立連接):setup required between client and server processes
    does not provide:
    timing, throughput, security ,

UDP(transport layer)

  • does not provide all of the service,
  • far faster than TCP
  • used in multimedia, internet telephone

SSL(app layer)

  • encrypted TCP connection
  • data integrity
  • end-point authentication
  • SSL socket API

HTTP

  • hypertext transfer protocol
  • 客戶端終端(用戶)和伺服器端(網站)請求和應答的標準,使用Web瀏覽器、網路爬蟲或者其它的工具
  • each object is addressable by a URL, include host name and path name
  • use TCP to send HTTP messages
  • stateless: server maintain no information about client
  • RTT(Round-trip delay time): time for a small packet to travel from client to server and back(來回時間)
  • 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

HTTP Request message format
http message

  • request line(method, URL, version..)
    • method field
    • POST: modify file in specified URL
    • URL: use GET
    • GET: get file content in specified URL
    • PUT: replace file in specified URL
    • HEAD: get information about a resource
  • header lines(fields)
  • body(context)

HTTP Response message format
reponse

  • status line
    • protocol
    • status code
    • status phrase

status code

  • 200 OK
  • 301 Moved Permanently
    • requested object moved, new location will send later in this msg (Location:)(重定向)
  • 400 Bad Request
    • request msg not understood by server
  • 404 Not Found
    • requested document not found
  • 505 HTTP Version Not Supported

try connect HTTP

telnet [host name] 80
GET [path name] HTTP/1.1

User-server state: cookies

help server keep states

Ex.
when initial HTTP requests arrives at site, site creates:
unique ID
entry in backend database for ID
cookie file kept on user’s host

Help for interaction
cookie

cache for proxy server

for any request, check it is in cache or not,
if it is, return cache

typically cache is installed by ISP (university, company, residential ISP)
reduce response time and traffic

Conditional GET: if client has up-to-update object, no need to send again
client send request: if-modified-since:

FTP

file transfer protocol
using TCP
ftp: RFC 959
(1)control connection:(port 21)
(2)data connection:(port 20)
Out-of-band (頻帶外)Control

server receives file transfer command, server opens 2nd TCP data connection (for file) to client
after transferring one file, server closes data connection

maintain state: current directory and earlier authentication

FTP 命令(Command)與回應(Reply)

(1).命令(command):從Client端到Server端

常見命令如下:

USER username :把使用者代號傳給伺服器
PASS password :把使用者密碼傳給伺服器
LIST :要求server傳回目前遠端目錄下的檔案列表 此檔案列表會透過資料連線(新建立且non-persistent) 而非control connection連線來傳送
RETR filename : 用來擷取遠端主機目前目錄下的某個檔案 此命令會使遠端主機開一筆data connection傳送請求的檔案
STOR filename : 把某個檔案存到遠端主機目前目錄下
(2).回應(Reply):從Server端到Client端

常見回應如下:

331 Username OK,password require
125 Data connection already open;transfer starting
425 Can’t open data connection
452 Error writing file
(3)
不管是Command或Reply都會送出7-bit ASCII值的control connection

EMAIL

  1. 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連線是由想要接收檔案的主機所建立

telnet URL 25
S: 220 hamburger.edu
C: HELO crepes.fr
S: 250 Hello crepes.fr, pleased to meet you
C: MAIL FROM: <alice@crepes.fr>
S: 250 alice@crepes.fr... Sender ok
C: RCPT TO: <bob@hamburger.edu>
S: 250 bob@hamburger.edu ... Recipient ok
C: DATA
S: 354 Enter mail, end with "." on a line by itself
C: Do you like ketchup?
C: How about pickles?
C: .
S: 250 Message accepted for delivery
C: QUIT
S: 221 hamburger.edu closing connection

RFC 822: standard for text message format

header body
header lines, e.g.,
To:
From:
Subject:
Body: the “message”
ASCII characters only

mail access protocol: get mail from user

POP:Post Office Protocol [RFC 1939]
authorization + download
authorization phase + transaction phase
download and keep

IMAP:Internet Mail Access Protocol [RFC 1730]:
比POP更進一步,除了download郵件外還可以在server上管理目錄,可以做更多的動作,
像郵件目錄的搬移等都得靠IMAP
keep all message at server
keep state

HTTP:gmail, Hotmail, Yahoo! Mail, etc.

DNS

DNS(domain name system),透過 DNS,我們不需要知道主機的 IP ,只要知道該主機的名稱就能連線

distributed hierarchical database 樹狀查詢
DNS 將主機名稱的管理分配在不同層級的 DNS 伺服器當中,有 IP 異動時也容易修改,而不用透過上層 ISP 的維護。

IPv4 已經接近發送完畢的階段,因此已逐漸拓展到 128bits 的 IPv6 。可以透過主機名稱就解析到 IP 的 DNS 服務,此外,目前全世界的 WWW 主機名稱也都是透過 DNS 系統在處理 IP 的對應,所以,當 DNS 掛點時,我們將無法透過主機名稱來連線,那就幾乎相當於沒有 Internet 了。

  1. DNS (domain name system)服務:nslookup

tree like
服務:把主機名稱轉成ip位置
Host aliasing(主機別名):一台主機可有多個別名(當然也有正規主機名稱canonical hostname 通常不好記)
dns可用別名查詢得到正規主機名稱及ip
Mail server aliasing
Load distribution:一個網站可能有多台伺服器 每個伺服器的ip和主機名稱不同 有要求傳送過來時 dns會一直改變回傳的伺服器的主機名稱及ip 這樣就不會有許多要求都由同一伺服器回應 可達到分配效果

  1. DNS伺服器架構
    root DNS servers: 13 (labeled A through M)
    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 DNSname server
not strictly belong to hierarchy
each ISP (residential ISP, company, university) has one
also called “default name server”
when host makes DNS query, query is sent to its local DNS server
has local cache of recent name-to-address translation pairs (but may be out of date!)
acts as proxy, forwards query into hierarchy

iterated query:
“I don’t know this name, but ask this server”
asking
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)

DNS registrar(網域販賣商)

queryand replymessages, both with same message format

  1. DNS Vulnerabilities(弱點)

DDoS:發出大量的DNS查詢(ex ICMP ping) 使封包多到塞滿link 讓大多數使用者發出的合法DNS查詢因ink塞滿得不到答案 服務無法被使用
Not useful in root server(cache in TLD), but useful at TLD

DoS(Denial-of-Service) 為一種網路攻擊 讓網路 主機等 無法被合法使用者使用

man-in-the-middle attack
DNS poisoning – send incorrect file to DNS server, which cache

P2P

p2p > client server when there are a lot of user
p2pgraph

(1) Client-server archtecture

設一個server要傳給n個client 檔案大小為f 上傳速度為us

上傳給n個點每個點一份f 故上傳時間為 nf/us

dmin 為n台電腦中下載速度最小的 故下載時間最多為f/dmin

distribution time >= MAX{nf/us , f/dmin} 只要N夠大 則時間會隨著N的數量線性增加

(2) P2P architecture

設一個server要傳給n個client 檔案大小為f 上傳速度為us
只有伺服器有檔案 伺服器必須把檔案放入LINK中一次 最低上傳時間為 f/us

同Client-server archtecture , dmin 為n台電腦中下載速度最小的 故下載時間最多為f/dmin

整個系統上傳總容量為us(第一個點)+u1+u2+….+un 上傳給n個對等點 共上傳nf 時間為nf/(us(第一個點)+u1+u2+….+un )

distribution time >= MAX{f/us , f/dmin , nf/(us+u1+u2+….+un)}

Structure

file divided into 256Kb chunks
peers in torrent send/receive file chunks

tracker:tracks peers
participating in torrent

torrent:group of peers exchanging chunks of a file

peer joining torrent registers with tracker to get list of peers, connects to subset of peers (“neighbors”)

churn(流失):peers may come and go

requests missing chunks from peers, rarest first
sending chunks: tit-for-tat

Alice sends top four peers which send to her.
other peers are choked by Alice every 30 seconds(receive only one chunk from her)
re-evaluate top 4 every10 secs

想要獲得更快的下載速度,就應該先將檔案分享給別人。Optimistic Unchoking是說,每個人每30秒就挑網路中任意一個人,將檔案上傳給他。這麼作的用意是發掘網路上未知的潛力檔案提供者:假如A與K之前並未有檔案的往來,但其實這兩個人住得很近,網路互傳的速度比其他人快。今天A透過Optimistic Unchoking隨機給K上傳了一些檔案片段,讓K驚覺A的上傳速度很快,進而允許A從K處下載檔案片段。如果A與K之間的連線速度很慢,那麼過30秒之後,A會停止提供檔案給K,而去別處尋找下一個候選人

http://mmdays.com/2007/04/06/bt1/

Distributed Hash Table
(key, value)
key: movie title value: IP address

put (key,value) pair in the peer that is closest(successor) to the key

Circular DHT with shortcuts
possible to design shortcuts so O(log N) neighbors, O(log N) messages in query
建捷徑於與目前key差一個bit的數- > => 一次至少可以縮短一半的距離
circular DHT

each peer knows address of its two successors
each peer periodically pings its two successors to check aliveness
if immediate successor leaves, choose next successor as new immediate successor

Chap03 Transport Layer

transport layer: logical communication between processes
=> breaks app messages into segments, passes to network layer

UDP

  • streaming multimedia apps (loss tolerant, rate sensitive)
  • DNS
  • SNMP

small header size
no congestion control: UDP can blast away as fast as desired

reliable transfer over UDP
add reliability at application layer to get application-specific error recovery

no connection establishment (which can add delay)

  • simple: no connection state at sender, receiver
  • small header size
  • no congestion control: UDP can blast away as fast as desired

UDP segment format

source port , dest port
length checksum
data

use checksum to detect error


Reliable data transfer

top-10 important network topic
=> unreliable channel with reliable data transfer(RDT) protocol

using unreliable data transfer channel

RDT 2.0: bit error -> use ctrl msgs
checksum to detect bit errors
acknowledgements (ACKs), negative acknowledgements (NAKs)

RDT 2.1: ctrl msg error -> use seq number
seq number prevent duplicate data, resend when corrupt
two seq (0,1) is enough

RDT 2.2: no NAK, resend when ACKs with the same seq num

RDT 3.0: lose packet -> add wait time, resend when timeout
3.0 sender

rdt3.0雖然確保了資料的可靠性,可是它採用Stop-and-Wait機制,效能很低
utilization of sender = 0.008(transmit time) / 30.008(transmit time+RTT) = 0.00027

Pipelined Protocol

可以讓傳送端同時傳送多個封包不需等待確認。必須增加封包的暫存空間與序列號碼。
暫存的區域中存在著窗格大小(Window Size),存放著各種封包(已確認、已送出但未收到ACK、未送出的封包等等)

Go-Back-N(GBN)

type
gbn
gbn sender
SENDER:

  1. nothing when receive corrupt response
  2. move window when receive ACK response
  3. send all packets in window when oldest packet in window timeout

gbn receiver
RECEIVER:

  1. 永遠送出ACK,為目前收到的最高序號
  2. 只收比目前收到的最高序號多一號的packet

Selective Repeat(SR)

SR
每個packet各自傳送,各自有timer

max seq# = window size * 2
假想有限序號0,1,2,3 窗格大小為3, 接收端收到0,1,2, 所以接收端的觀點應為:0,1,2,[3,0,1],2 當接收端回傳給傳送端的ACK遺失時, 將導致傳送端逾時而重送0,1,2 然而接收端想要的是第二批的0,1 而傳送端所傳送的封包卻是第一批的0,1。

TCP

  • reliable, in-order byte steam
    • no “message boundaries”
  • pipelined
  • congestion and flow control
    • 決定 window size
  • full duplex data(雙方皆可傳)
  • MSS(maximum segment size): 傳送的segment最大長度
  • connection-oriented
    • handshaking (exchange of control msgs)

segment
sequence numbers(Seq): 送過去的packet的起始編號(0, 1)
acknowledge number(ACK): 預期對方會送來的編號
telnet
對A來講前一個收到B傳回來的資料Seq為78,下一個期待收到的為79,所以傳回ACK=79,而data為’C’這和ACK,Seq都沒關聯
A所傳的Seq是42,對B來講下一個應該要收到43,於是傳回ACK=43,而A在ACK=79中告訴B下一個應該送79過去,於是B傳Seq=79

  • TCP傳送端
    • 逾時重送封包
    • cumulative ACK
    • TCP sender
  • TCP接收端
    • 預期封包抵達事件
      • 回傳期望下一次收到的封包之序號ACK
    • 非預期封包抵達事件
      • 暫存封包, 送出期望收到的封包之序號ACK

Estimate best timeout value

SampleRTT: record the time of last transmission
exponential weighted average let value smoother
EstimatedRTT = (1- a) x EstimatedRTT + a x SampleRTT (typical a = 0.125)

devrtt
將變異數納入考慮: TimeoutInterval = EstimatedRTT + 4*DevRTT

TCP fast retransmit: 收到三次相同ACK,傳送端就會立刻傳送接收端所預期的封包

Flow Control (流量控制): 讓reiceiver buffer不致overflow
記錄buffer剩餘的空間有多少(rcvWindow)
當rcvWindow=0時,傳送端會持續傳送一個1byte的區段給接收端以確認緩衝區可否繼續接收資料

TCP Connection Management (連線管理)

http://www-sop.inria.fr/members/Vincenzo.Mancuso/ReteInternet/06_tcp_part2.pdf

防止delay duplicate problem

3-way handshake:(open connection)
一方傳SYN, 另一方回傳ACK/SYN, 一方回傳ACK。

4-way handshake:(close connection)
一方傳FIN, 另一方回傳ACK。另一方傳FIN, 一方回傳ACK。(可以handle同時想結束的情形)

congestion control(擁塞控制)

保持在網路上的封包數量,不讓整體效能下降(buffer overflow, queueing in router)

  • End-to-End (implicit)
    • 依據往返延遲時間來降低視窗大小
    • TCP採用此種方式
  • Network-assisted (explicit)
    • Router會依據網路壅塞情況,提供傳送端明確的網路壅塞狀態且回報
    • 回饋傳送給傳送端 或 在封包中的某個欄位記錄

cwnd(send window size)

  1. AIMD (Additive-Increase, Multiplicative-Decrease): cwnd一次增加一定(+1)值,loss時成比例減少(/2)
  2. Slow Start: cwnd呈次方成長(*2)

TCP Sender Congestion Control

grows by slowstart to threshold, then grows linearly

  • loss by timeout
    • cwnd = 1
  • loss by 3 duplicate ACKs:
    • TCP Tahoe - cwnd = 1
    • TCP RENO - cwnd /= 2, threshold = cwnd

Average throughout = (1 + 0.5)/2 = 0.75W/RTT

TCP Fairness

有相同需求的兩端會在bandwidth share附近震盪兩邊互相影響下是公平的

但是UDP在的話就不太公平了,如多媒體。現在像youtube會在UDP上加上一些TCP friendly

開多個TCP connection: 速度加快…

Summary

  • TCP creates rdt service on top of IP’s unreliable service
    • pipelined segments
    • cumulative acks
    • single retransmission timer
  • retransmissions triggered by
    • timeout events
    • duplicate acks

Reference

CFChou講義