【正文】 片添加到鏈表尾部（一個(gè)常數(shù)時(shí)間操作） 優(yōu)化的 IP分片重組算法 ? 在有序鏈表的基礎(chǔ)上， 增加一個(gè)指向鏈表尾部的指針。 Linux分配器 ? Linux分配器 最初由 Doug Lea實(shí)現(xiàn)， 稱 為dlmalloc() ? 內(nèi)存 被 劃分成 128個(gè)內(nèi)存池 ： ? 前 64個(gè)內(nèi)存池，緩沖區(qū)大小分別為 1 23 …… 、 512字節(jié)（按 8字節(jié)步長增加） ? 后 64個(gè)內(nèi)存池，大小為 2的冪次 ? 分配器會(huì) 合并相鄰的空閑緩沖區(qū)，放入合適的緩沖池中 。 ? 優(yōu)點(diǎn)： ? 支持可變長度 的內(nèi)存分配，沒有內(nèi)存浪費(fèi) ，分配快 。 假設(shè)與實(shí)際相符嗎？ ? 分片重組優(yōu)化算法 隱含的假設(shè)： ? IP分片 按照 偏移量從小到大 的順序 發(fā)送 ? 多數(shù)情況下 IP包順序到達(dá) ? 實(shí)際測量： ? 許多 較新的實(shí)現(xiàn)（包括 Linux），發(fā)送端按照分片偏移量從大到小的順序發(fā)送 IP分片！ ? 原因：最后一個(gè)分片攜帶了 IP包總長度的信息，讓最后一個(gè)分片最先到達(dá)接收端，方便接收端為數(shù)據(jù)包分配適當(dāng)大小的緩沖區(qū)。 發(fā)送端頭部預(yù)測 ? 在 發(fā)送端發(fā)送的一系列 TCP 段 中， TCP頭部有變化的域 只有少數(shù)幾個(gè) 。 ? 可能有內(nèi)存空間浪費(fèi)，但實(shí)現(xiàn)簡單 。 共享緩沖區(qū) ? 假 如 一群用戶共用同一組空閑緩沖區(qū)，我們 希望共享緩沖區(qū)的分配是公平的： ? 這組緩沖區(qū)在需要的用戶之間近乎均等地分配 ? 共享緩沖區(qū)的用戶是變化的 ： ? 每個(gè)用戶分配的緩沖區(qū)數(shù)量應(yīng)當(dāng)能夠動(dòng)態(tài)調(diào)整 ? 當(dāng)有新用戶加入時(shí)，應(yīng)能從老用戶那兒奪取一些緩沖區(qū) 緩沖器竊取 ? 實(shí)現(xiàn)公平分配的一種方法是緩沖區(qū)竊?。? ? 若 所有緩沖區(qū) 已 用完，一個(gè) 分配較少的 用戶想多要一 些 緩沖區(qū)，就從當(dāng)前分配最多的用戶那兒竊取。 算法調(diào)整 ? 使 用第一個(gè)到來的分片 ， 判斷發(fā)送端按照 什么順序發(fā)送 IP分片。 ? 兩種預(yù)期的情形： ? 收到一個(gè)純 ACK段（無數(shù)據(jù)） ? 收到一個(gè)純數(shù)據(jù)段（ 確認(rèn)序號(hào) 無更新） ? 其它預(yù)期情形： ? 標(biāo)志位 常規(guī) 設(shè)置 ? 無窗口更新 接收端頭