深度探秘

遲到的資料，等於沒到

多媒體是「即時系統」

當你看影片、講網路電話時，音訊與視訊是連續、即時產生並即時消費的資料。每一個音訊取樣、每一張視訊影格都有自己的「上場時刻」。

重點：晚到的元素毫無價值，通常會直接被丟棄。一張該在第 3 秒顯示的影格，第 3.5 秒才到，已經沒人需要它了。

所謂即時系統 (real-time system)，就是必須「依照外部決定的時間表」完成工作並交出結果。系統達成這種準時交付的程度，就叫做這個應用享有的服務品質 (Quality of Service, QoS)。

和傳統即時系統哪裡不一樣？

航空電子、空中交通管制這類傳統即時系統，資料量小、硬截止期限不頻繁，但錯過一次就可能釀災，所以做法是「資源開超大、固定排程，保證最壞情況都撐得住」。

多媒體則不同：

• 高度分散，跑在通用環境裡，要和其他應用搶頻寬與運算資源。
• 需求是動態的：視訊會議參加人數多寡，需要的頻寬就跟著變。
• 使用者想權衡取捨：願意降低視訊頻寬，好讓語音或文件編輯同時進行。

所以桌面上的串流多半只能拿到盡力而為 (best-effort) 的品質。

生活妙喻

趕高鐵的便當

把影格想成「月台便當」

想像一家便當店要把熱便當送上每一班即將進站的高鐵。

• 每班車＝一個播放時刻（影格該顯示的瞬間）。
• 熱便當＝一張影格或一段音訊。
• 便當晚一秒到月台，車已經開走，這個便當就沒用了，直接丟掉——這正是「late delivery is valueless」。

傳統即時系統像是運鈔車：班次少、絕不能出錯，所以乾脆派十倍人力、走專用道，保證萬無一失。

多媒體則像在尖峰時段的市區送便當：訂單忽多忽少（動態需求），路上還有別人的車在搶道（和其他應用競爭），而你只能盡力而為。

這就是為什麼一般作業系統「人人有飯吃但都吃不飽」的盡力而為排程，撐不起多媒體。

實用超能力

為什麼你的串流靠『緩衝』活著

現實世界怎麼擠出可用品質？

在這個還沒有完善 QoS 的網路世界，能跑的應用都用了聰明的妥協：

• Web 多媒體（YouTube、Hulu、BBC iPlayer）：在接收端大量緩衝 (buffering)，先囤一段資料再播，藉此抹平頻寬與延遲的波動，代價是來源到畫面可能延遲好幾秒。
• 隨選視訊 (Video-on-demand)：用專用頻寬＋專用伺服器，再加上目的端緩衝。

但高度互動的應用就難多了，例如：

flowchart TD
  A[來源產生影格] --> B[網路傳輸有延遲與抖動]
  B --> C[接收端緩衝囤積一段]
  C --> D[平穩播放給使用者]
  B -. 太晚到 .-> E[直接丟棄該影格]

下次看到影片開頭那一圈轉圈圈，你就知道：它正在偷偷囤緩衝，好讓後面播得順。

深度探秘

連續其實是『快到看不出來的離散』

「連續」是錯覺

我們說影音是連續 (continuous) 的，但那只是使用者的觀感。在系統內部，連續媒體其實是一連串快速替換的離散值：

• 影像陣列每秒被替換 25 次，就騙過眼睛看成流暢的電視畫面。
• 聲音振幅值每秒被替換 8000 次，就成了電話品質的語音。

「時間相依」決定資料的意義

多媒體串流是時間相依 (time-based)，也叫 isochronous（等時）：每個元素被播放或錄製的時刻，定義了串流的內容與語意。播早了、播晚了，資料的正確性就變了。因此支援多媒體的系統，處理資料時必須保留時序。

串流很「肥」，壓縮是必須

未壓縮的標準電視就要超過 120 Mbps，已超出 100 Mbps 乙太網路的容量！所以壓縮不可或缺——它能把頻寬需求降低 10 到 100 倍，但時間需求一點都不會變。

生活妙喻

翻頁動畫書與真空壓縮袋

連續＝翻頁動畫

小時候在筆記本角落畫的翻頁動畫：每頁只是一張靜止圖（離散值），但快速翻動時，眼睛就看成連續的動作。影片每秒換 24–25 張圖，就是同一個把戲。

時間相依＝歌曲的節拍

一首歌的每個音符何時響起決定了旋律。如果你把音符隨意提早或延後，曲子就走音了——這就是「時刻定義語意」。換句話說，資料不只要對，還要在對的時間出現。

壓縮＝真空收納袋

未壓縮的影片像一床蓬鬆的大棉被，塞不進行李箱（網路頻寬）。用**真空壓縮袋（壓縮演算法）**抽掉空氣，體積縮成 1/10～1/100，就塞得進去了。

但注意：壓縮袋讓棉被變小（省頻寬），卻不會改變你必須準時把棉被送到的期限（時間需求不變）。而且打開壓縮袋（解壓縮）要花力氣（增加 CPU 負擔）。

實用超能力

壓縮的代價與不對稱設計

壓縮省了頻寬，卻多了 CPU 負擔

壓縮雖然減少網路頻寬需求，卻在來源與目的端的處理器上加重負擔。這份工作以前常交給專用硬體——也就是顯卡上的編解碼器 (codec, coder/decoder)。

但現在 PC 越來越強，許多 codec 改用軟體實作，好處是更有彈性：能支援特定格式、特定應用邏輯，並同時處理多條媒體串流。

MPEG 的『不對稱』巧思

MPEG 視訊壓縮是不對稱 (asymmetric) 的：

• 壓縮演算法複雜（做一次就好）。
• 解壓縮相對簡單（每個接收端都要做）。

flowchart LR
  A[原始影像] --> B[複雜壓縮 一次完成]
  B --> C[小體積 MPEG 串流]
  C --> D[簡單解壓縮 每個接收端]
  D --> E[還原畫面]

為什麼這樣設計很聰明？在桌面視訊會議中，壓縮常由一顆硬體 codec 完成，而每位與會者電腦上要解壓縮多條串流則用軟體做。如此一來，會議人數可以自由增減，不必受限於每台電腦裡有幾顆 codec 晶片。

深度探秘

頻寬、延遲、遺失率

用三個數字描述一條串流

要和系統談服務品質，應用得用一組參數說清楚自己的需求。最關鍵的三個是：

• 頻寬 (Bandwidth)：資料流過串流或元件的速率（每秒多少資料）。
• 延遲 (Latency)：單一資料元素從來源走到目的地所需的時間。它會隨系統負載而變動，這個變動量稱為抖動 (jitter)——正式定義是延遲的一階導數。
• 遺失率 (Loss rate)：因為晚到的資料沒有價值，無法準時送達的元素會被丟棄。完美管理下不該發生，但保證每個元素都準時的成本太高（得保留遠超平均的資源去應付偶發尖峰），因此常接受一定的遺失率——通常低於 1%，品質關鍵的應用更低。

三者相互牽動

這三個參數不是各自獨立的：

• 現代系統的遺失多半不是位元錯誤，而是緩衝區溢位或資料太晚到達。所以頻寬越大、延遲越低，遺失率就越可能低。
• 資源頻寬相對於負載越小，訊息就越會在它前面累積，需要的緩衝區就越大；緩衝區越大，訊息越可能要排隊等前面的人，延遲也就越大。

flow spec：一整包參數

一組 QoS 參數合起來稱為流量規格 (flow specification, flow spec)。RFC 1363 把它定義成 11 個 16 位元數值，分別描述頻寬（含突發性）、延遲（含可接受的抖動）與遺失特性。

生活妙喻

高速公路上的車流

把串流想成一條高速公路

• 頻寬＝每分鐘能通過收費站的車輛數（車流速率）。
• 延遲＝一輛車從上交流道到下交流道花的時間。
• 抖動＝這趟時間忽快忽慢的程度：早上 20 分鐘、塞車時 50 分鐘，這個落差就是抖動。
• 遺失率＝因為太塞而乾脆放棄、改道或被攔下的車比例。

為什麼它們牽動彼此？

如果車道太窄（頻寬不足），車子就在交流道前大排長龍（緩衝累積）。你得蓋一個超大的等候區（大緩衝區）來容納，但等候區越大，每輛車排隊等越久（延遲變大）；要是等候區也滿了，後面的車只能被擋下（遺失）。

反過來，路夠寬（頻寬大）＋不塞（延遲低），就很少有車需要被丟掉（遺失率低）。

而 flow spec 就像你交給交通局的一張完整需求單：「我每分鐘要送這麼多車、單趟最多忍受幾分鐘、抖動別超過多少、最多容許掉幾輛。」

實用超能力

抖動怎麼靠緩衝抹平

抖動：互動應用的隱形殺手

硬體裝置通常能穩定地以固定速率呈現資料；但軟體解碼（例如軟體視訊解碼器）就得特別小心抖動。解法是緩衝：先囤一點資料，遇到忽快忽慢時用囤積量補上，輸出就平穩了。

但緩衝有上限——因為端到端總延遲是受限的（互動會議要求 ≤150 ms）。你不能為了消除抖動而無限囤積，否則延遲就爆了。

不同應用的延遲門檻

一個關鍵公式：別讓影格在緩衝裡待太久

若串流影格速率為 $R$，為了避免積壓，一張影格在緩衝區中平均停留時間不應超過：

$$ \frac{1}{R} $$

例如 $R = 25$ 影格/秒，則平均停留不應超過 $\frac{1}{25} = 0.04$ 秒（40 ms）。一旦處理速度跟不上抵達速度，積壓就會堆高、緩衝可能溢位，端到端延遲也會跟著惡化。

深度探秘

QoS 管理員的兩大任務

誰負責保證資源？

資源（CPU 時間、網路頻寬、記憶體）能被保證，前提是有一個元件專責配置與排程它們——這就是 QoS 管理員 (QoS manager)。它的工作分兩大子任務：

1. QoS 協商 (negotiation)

應用把資源需求（flow spec）告訴 QoS 管理員。管理員拿這需求去比對可用資源資料庫與目前的承諾，回覆能或不能。

若回覆「不能」，應用可以重新配置成較低需求，再談一次。

2. 允入控制 (admission control)

若評估結果是「可以」，管理員就保留 (reserve) 所需資源，並發給應用一份資源合約 (resource contract)，載明已保留的資源與一個時間限制。之後應用就能放心執行。

• 若需求減少，釋出的資源回到資料庫成為可用。
• 若需求增加，就重新啟動一輪協商與允入控制。

允入控制的本質：回絕那些會破壞現有 QoS 保證的新請求，避免資源超載。

生活妙喻

餐廳訂位系統

把 QoS 管理員想成『餐廳訂位櫃台』

你打電話訂位（送出 flow spec）：「今晚 8 點，6 人桌，要靠窗。」

• 協商：櫃台查訂位簿（可用資源資料庫），看 8 點還有沒有 6 人靠窗桌。
  • 若沒有，它會說「靠窗沒了，4 人桌＋加椅可以嗎？」——這就是重新配置成較低需求再談一次。
• 允入控制：談妥後，櫃台把那張桌子鎖起來保留，給你一張訂位確認（資源合約），註明位子、人數和保留到幾點（時間限制）。

重點是：櫃台會回絕那些一旦答應就會害到已訂位客人的請求。如果店已客滿，第 21 組客人就算肯付錢也只能婉拒——這正是允入控制『保護現有保證』的精神。

若你臨時改成 4 人（需求減少），多出的位子還給訂位簿；改成 10 人（需求增加），就得重新查、重新談一次。

實用超能力

送方發起 vs 收方發起

分散式協商：沿著資料流談

串流的元件常分散在多個節點，每個節點都有 QoS 管理員。最直接的做法是沿著資料流從來源到目標逐站協商：來源送出 flow spec 給本地管理員，逐站轉發，到達目標後再把『能否提供』的結果回傳給來源。

多個接收者怎麼辦？

送方發起 (sender-initiated)

當串流有多個目標時，中間節點彙整各目標的回饋取最差值：可用頻寬取最小、延遲取最長、遺失率取最大。SRP、ST-II、RCAP 採此法。缺點是把共同的最差 QoS 強加給所有目標。

收方發起 (receiver-initiated)

對異質目標（能力差很多），應讓每個目標拿到各自最佳的品質。RSVP 就是這類：來源廣播串流的存在與特性，目標主動連到最近的節點取資料，並可搭配過濾技術取得合適品質。

flowchart TD
  A[來源] --> B[送方發起：取所有目標最差值]
  A --> C[收方發起：每個目標各取最佳]
  B --> D[適合同質目標]
  C --> E[適合異質目標 如 RSVP]

實務上還常為每個參數同時給『期望值』與『最差可接受值』，例如『想要 1.5 Mbps，但 1 Mbps 也能接受』。像 HeiRAT 系統甚至要使用者只定兩個參數，第三個交給系統最佳化。

深度探秘

漏桶與令牌桶

為什麼要塑形流量？

串流的實際傳送往往忽多忽少（突發, bursty），但排程器最喜歡規律的請求。流量塑形 (traffic shaping) 就是用輸出緩衝把資料流『撫平』，讓實際流量盡量貼近描述。

突發性的數學模型：LBAP

線性受限到達程序 (LBAP) 定義：任何長度 $t$ 的時間區間內，串流中的訊息數最多為：

$$ R \cdot t + B $$

其中 $R$ 是速率，$B$ 是最大突發量。

漏桶 (Leaky bucket)

想像一個底部有洞的水桶：可任意倒水進去直到滿，水則以固定速率 $R$ 從底部漏出。

• 確保串流永遠不會以高於 $R$ 的速率流出。
• 緩衝大小 $B$ 決定能容忍多大的突發而不丟資料，也限制元素停留時間。
• 缺點：完全消除突發——但有時沒必要這麼嚴。

令牌桶 (Token bucket)

以固定速率 $R$ 產生令牌收集在容量 $B$ 的桶裡。要送 $S$ 大小的資料，桶裡至少要有 $S$ 個令牌，送完就扣掉。

• 它保證任何區間 $t$ 內送出的資料不超過 $R \cdot t + B$（正是 LBAP 的實作）。
• 好處：串流閒置一陣子後，可以動用累積的令牌做較大的突發。
• 若要再壓掉超大突發，可在令牌桶後面再串一個流速 $F$（$F$ 須明顯大於 $R$）的漏桶。

生活妙喻

水桶與遊樂園快速通關券

漏桶＝底部破洞的水桶

不管你怎麼忽快忽慢地倒水進去，水都只會以固定速度從底洞漏出。倒太快、桶滿了就溢出來（丟資料）。它把任何起伏都磨成一條平穩的細流——徹底消除突發。

令牌桶＝遊樂園的快速通關券

園方每隔固定時間發一張快速通關券（令牌），你可以先存著不用，券放在一個有上限的票夾裡（桶容量 $B$）。

• 平常人少時券一直累積。
• 等到你想衝熱門設施（突發），可以一口氣掏出一疊券插隊進場——這就是「閒置後允許較大突發」。
• 但你手上券再多，發券速度（$R$）不變，長期下來進場總量仍受 $R \cdot t + B$ 限制。

漏桶像嚴格的水龍頭（一視同仁、絕不突發）；令牌桶像存券制度（平常忍著、需要時爆發），更貼近多媒體有時大塊、有時零碎的真實流量。

實用超能力

硬保證 vs 軟保證

資源保留：要給多少？

要對串流提供某種 QoS，常見做法是保留一部分資源頻寬專用。

• 若要任何時刻都滿足需求，就得依最大頻寬保留——這是提供硬保證 (hard / deterministic guarantee) 的唯一方法，適合不能容忍品質下降的應用，例如醫療影像（X 光影片掉格可能漏看症狀）、影片錄製（掉格會永久留痕）。
• 網路保留很單純：頻寬 $B$ 的網路可允入頻寬總和不超過 $B$ 的串流，例如 16 Mbps 的權杖環可承載 10 條 1.5 Mbps 視訊。
• 但 CPU 就難算：執行時間取決於處理器，常只能靠量測估計，誤差大。

統計多工：賭它不會同時爆

依最大需求保留常造成浪費（MPEG 實際用量常遠低於峰值）。於是常見做法是超額預訂 (overbook) 資源，得到統計／軟保證 (statistical / soft guarantee)——只在很高機率下成立，使用率更好，但同時尖峰時品質可能下降，應用須能承受。

統計多工的假設是：串流夠多時，總頻寬趨於穩定（有人量大就有人量小，互相抵消）。

但這只對『不相關』的串流成立！ 實驗顯示真實多媒體流量具自相似性 (self-similar)：把一堆突發串流加總，總流量仍然突發，並不會被抹平。

深度探秘

有資源還不夠，要排得對

效能 ≠ 準時

要提供 QoS，系統不只要有足夠資源（效能），還要在需要的時刻把資源給對的行程（排程）。資源排程器依某些準則決定行程的優先權。

傳統分時系統的 CPU 排程多看回應性與公平性：I/O 密集的工作給高優先權以求快速回應，CPU 密集的給較低優先權，同類行程一視同仁。這些準則在多媒體仍有效，但截止期限的存在改變了排程問題的本質。

公平佇列 (Fair queuing)

當多條串流爭用同一資源，必須講公平，防止行為不良的串流吃掉太多頻寬。最直接的做法是對同類串流做輪詢 (round-robin) 排程：

• 封包級 (packet-by-packet) 輪詢：一次處理一個封包。
• 位元級 (bit-by-bit) 輪詢：在位元層次輪流，對不同封包大小與到達時間更公平。這類方法稱為公平佇列 (fair queuing)。

加權公平佇列 (Weighted fair queuing)

基本輪詢給每條串流相同頻寬。若要照顧各串流不同的頻寬需求，可擴充位元級方案，讓某些串流每輪傳更多位元——這就是加權公平佇列。

生活妙喻

自助餐分菜的智慧

公平佇列＝自助餐排隊夾菜

想像一鍋限量的紅燒肉（共享資源），一群人排隊夾（多條串流）。

• 封包級輪詢：每人一次只能夾一整塊就到隊尾重排。問題是有人夾到大塊、有人夾到小塊，份量不均。
• 位元級輪詢：規定每人一次只能夾一口的量（位元），輪流夾。無論肉塊大小，大家拿到的總量更接近——這就是位元級更公平的精神。

至於『行為不良的串流』，就像那個拿大盤子想一次鏟走半鍋的人——公平佇列就是用『一次只能夾一口、輪流來』來治他。

加權公平佇列＝VIP 多分一點

如果今天有人是付了雙倍餐費的 VIP（頻寬需求較大），可以規定他每輪能多夾幾口。大家還是輪流、還是公平，只是按權重分配——這就是加權公平佇列。

實用超能力

位元級理想如何在現實落地

不能真的『一個位元一個位元』送

位元級輪詢是個理想模型——封包當然不可能拆成單一位元交錯傳送。實作上的巧思是：

給定影格速率，可以計算每個封包『理論上應該在何時送完』，再依這個計算結果排序封包的傳送順序。

這樣就能逼近真正位元級輪詢的行為。差別只在於：當一個大封包正在送，它可能擋住一個本來在位元級方案下會優先的小封包。但好消息是——沒有任何封包會被延誤超過一個最大封包傳送時間。

flowchart TD
  A[計算每個封包理論完成時刻] --> B[依完成時刻排序傳送]
  B --> C[逼近位元級輪詢的公平性]
  C --> D[大封包可能短暫擋住小封包]
  D --> E[但延誤不超過一個最大封包傳送時間]

實用價值：你的路由器、視訊伺服器就用這類公平佇列，確保一個下載大檔的鄰居不會把你的視訊通話頻寬整碗端走，同時又能給重要串流（加權）多一點頻寬。

深度探秘

兩種經典即時排程

前提：資源沒被超配

即時排程演算法假設 CPU 資源沒有被超額配置（這是 QoS 管理員的責任），然後在這前提下把 CPU 時段分給各行程，確保它們準時完成。傳統規律連續串流的模型，非常適合即時排程。

EDF：最早截止期限優先

Earliest-Deadline-First (EDF) 幾乎成了即時排程的代名詞：每個工作項都帶一個截止期限，排程器永遠先處理截止期限最早的那個。在多媒體中，每個抵達行程的媒體元素就是一個工作項。

EDF 的強項：對單一資源依時間準則而言是最佳的 (optimal)——只要存在能滿足所有時間需求的排程，EDF 一定找得到 [Dertouzos 1974]。

缺點：每個訊息都要做一次排程決策，開銷大。

RM：速率單調

Rate-Monotonic (RM) 針對週期性行程，依速率指定優先權：工作項速率越高的串流，優先權越高。它基於存在較久的元素（串流）來排程，效率更好。

RM 的最佳性條件：在頻寬利用率低於 69% 的情況下是最佳的 [Liu and Layland 1973]。剩下的頻寬可給非即時應用。

處理突發：deadline/workahead

為應付突發的即時流量，可讓串流中的訊息提前成批抵達，但只在其規律抵達時刻才對它套用 EDF——這就是 deadline/workahead 排程。

生活妙喻

交報告與固定打掃班表

EDF＝先做最快截止的作業

期末週你手上有一堆作業，每份都有繳交期限。EDF 的策略很直覺：永遠先寫『最快要交』的那份。哪份 deadline 最近就先動手，寫完再看下一個最近的。

• 好處：只要『理論上能全部如期交出』，這個策略保證做得到（最佳性）。
• 壞處：你每完成一件就得重新看一次『現在哪份最急』（每個訊息一次決策，開銷大）。

RM＝按『多久做一次』排固定班表

換個情境：宿舍打掃。RM 的策略是看頻率：倒垃圾每天要做（高頻率→高優先），拖地每週一次（低頻率→低優先）。你按這個固定的優先順序排班，而不是每次都重新評估。

代價：這套固定班表只有在你沒把行程表塞太滿（利用率 < 69%） 時，才保證每件事都來得及。塞超過，就可能有事情開天窗。

實用超能力

怎麼選？EDF 還是 RM？

兩者的取捨

flowchart TD
  A[要排程即時工作] --> B{截止期限多變還是週期規律}
  B -->|多變| C[EDF 依最早截止期限挑]
  B -->|週期規律| D[RM 依速率定靜態優先權]
  C --> E[單一資源最佳但每訊息決策]
  D --> F[開銷小 但須利用率低於 69%]

為什麼這對你重要

當你看一段流暢的串流時，背後的作業系統正用這類演算法，確保每張影格的解碼工作在它該顯示之前完成。理解 EDF／RM，你就懂為什麼即時系統不能把 CPU 排到 100% 滿載——RM 需要保留約三成餘裕，剩下的才安心交給背景的非即時工作。

深度探秘

保證不了，就主動降級

調適的必要

當某個 QoS 無法保證、或只能以某機率保證時，應用必須調適 (adapt)——隨可用品質起伏調整自己的表現。對連續媒體而言，這就轉化成不同等級的呈現品質。

最簡單的調適是丟掉一些資訊：音訊取樣彼此獨立，丟了立刻被聽見；Motion JPEG 每張影格獨立，掉格較可容忍；但 MPEG 的一張影格依賴相鄰影格，對遺漏較不耐受——錯誤要花更久才能恢復，甚至會被放大。

若頻寬不足又不丟資料，串流延遲會越積越大。非互動應用或可忍受（但最終可能緩衝溢位）；互動應用則不行。若串流落後播放時刻，就該加快播放速率追回進度。

縮放 (Scaling)

若調適只在目標端做，瓶頸的負載並未減輕，過載依舊。聰明的做法是在串流進入瓶頸資源之前，於源頭就把它調整到可用頻寬——這就是縮放 (scaling)。

縮放最適合用在即時取樣的串流；對已儲存的串流，若得整段解壓再重編才能降級，就太麻煩了。

縮放演算法依媒體而異，但核心都是對訊號做子取樣 (subsample)。音訊可降低取樣率，或在立體聲中丟掉一個聲道——可見不同方法作用在不同粒度上。

生活妙喻

寄包裹前先精簡行李

在源頭瘦身，才不會卡在門口

想像你要把一大箱行李寄過一道很窄的門（瓶頸）。

• 在目標端調適＝箱子硬塞到門口才開始丟東西——可是門前已經塞車了，過載沒解決。
• 縮放（源頭調適）＝還沒出門就先精簡行李，把箱子縮到能順利通過那道窄門的大小。瓶頸前的塞車自然消失。

子取樣＝抽掉一部分內容

縮放的本質是子取樣：像把一本厚相簿每隔幾張抽掉一張，或把彩色照片印成黑白——資訊變少、體積變小，但還看得懂。

為什麼即時取樣最好縮放？

即時取樣就像現場錄音邊錄邊調品質，要降級很自然。但若是早就壓好封存的影片，要降級可能得整片拆封、重剪、再封裝，費工又費時——這就是「對已儲存串流可能太麻煩」的意思。

實用超能力

視訊的五種縮放法

影像縮放的五種招式

需要時這些方法可組合使用。

縮放系統怎麼運作？

flowchart LR
  A[源頭 scaler 縮放器] --> B[網路與瓶頸]
  B --> C[目標 monitor 監視器]
  C -->|偵測到延遲 送 scale-down| A
  C -->|一段時間後 試著 scale-up| A

目標端的監視器 (monitor) 記錄訊息抵達時間，發現延遲（瓶頸徵兆）就送降級訊息給源頭，源頭的縮放器 (scaler) 隨即降低頻寬；過一陣子再試著升級。若瓶頸還在，監視器會再偵測到延遲、再降級。

關鍵挑戰：避免不必要的升級、防止系統來回震盪 (oscillating)——一下降一下升，反而更糟。

深度探秘

縮放的盲點

縮放在多接收者情境的問題

縮放是在源頭修改串流。但若一條串流要送給多個接收者，問題就來了：

當通往某一個目標的路徑出現瓶頸，這個目標送出降級訊息，源頭一降級，所有接收者都拿到變差的品質——即使其他人原本完全有能力處理原始串流。

這就像因為一位客人吃不下，整桌人都被迫只能吃半份。

過濾 (Filtering)

過濾 (filtering) 的目標是給每個接收者各自最佳可行的 QoS，做法是在從源頭到目標的路徑上、於每個相關節點各自進行縮放。

• RSVP 就是支援過濾的 QoS 協商協定。
• 前提：串流必須被切成一組階層式子串流 (hierarchical substreams)，每一層再疊加更高的品質。
• 路徑上各節點的容量決定該目標能收到幾層子串流。

在哪裡過濾？

所有用不到的子串流，要盡可能在靠近源頭處就被過濾掉（甚至就在源頭），以免白白傳輸之後又被丟棄的資料。但有個例外：若下游某處還有能承載整條子串流的路徑，就不在這個中間節點過濾掉它。

生活妙喻

中央廚房的分流出餐

縮放像『一鍋煮到底』，過濾像『分流調味』

回到那桌客人：

• 縮放：廚房只煮一種口味、一種份量送上整桌。只要有一位客人受不了辣，整鍋就得調淡——大家一起吃清淡版。
• 過濾：改成中央廚房 + 沿途分站的模式。主菜分成基本層、加料層、頂級層（階層式子串流），在送餐路徑的各個分站，依照那一桌的胃口與通道寬窄決定加幾層料。能吃辣又坐大桌的客人拿到頂級全配，胃口小的那桌只拿基本層。

為什麼盡量在靠源頭處過濾？

如果某一層料注定沒人要，就在廚房（源頭）就別做別送，免得大老遠運過去再倒掉，白白佔用通道（頻寬）。但只要下游還有一桌吃得下，這層料就得繼續往下送，不能在半路砍掉。

實用超能力

階層子串流如何運作

階層式子串流：一層一層疊品質

過濾要能運作，串流必須被分層編碼：

• 基本層：最低可用品質（人人都收得到）。
• 增強層 1、2、3…：每多收一層，品質就更好（更高解析度／更高張數）。

路徑上每個節點依其容量，決定要讓幾層通過、濾掉哪些。

flowchart TD
  S[源頭 分層串流] --> N1[中間節點 依容量過濾]
  N1 --> T1[高頻寬目標 收基本層加多層增強]
  N1 --> N2[較窄節點 再過濾]
  N2 --> T2[中頻寬目標 收基本層加一層增強]
  N2 --> T3[低頻寬目標 只收基本層]

縮放 vs 過濾，一次看懂

實用價值：這正是現代直播／多人視訊背後的可調式編碼 (scalable coding) 思路——同一場直播，光纖觀眾看 4K、行動網路觀眾看 480p，彼此互不拖累。

深度探秘

用平價 PC 服務上萬觀眾

Tiger 的設計目標

Tiger 是微軟研究院開發的視訊檔案伺服器，典型應用是付費隨選電影。設計目標包括：

• 大規模隨選視訊：可擴充到同時服務一萬名客戶；客戶幾秒內就看到首批影格，並能隨意暫停、倒帶、快轉。熱門電影會被多位客戶不同步、時間錯開地同時觀看。
• 服務品質：固定速率供應、抖動小、遺失率極低。
• 可擴充且分散：靠增加電腦來擴充。
• 低成本硬體：用商品級 PC 與標準硬碟。
• 容錯：任一伺服器或硬碟故障後，服務不明顯降級仍持續。

硬體架構

• cub（幼虎）：一群相同的 PC，每台接 2–4 顆標準硬碟，配 Ethernet 與 ATM 網卡，負責實際搬運視訊資料。
• controller（控制器）：另一台 PC，不碰多媒體資料，只處理客戶請求與管理 cub 的工作排程。

flowchart TD
  CTRL[控制器 處理請求與排程] --> C0[cub 0]
  CTRL --> C1[cub 1]
  CTRL --> C2[cub 2]
  C0 --> ATM[ATM 交換網路]
  C1 --> ATM
  C2 --> ATM
  ATM --> CLIENTS[客戶端 顯示視訊]

生活妙喻

撲克牌發牌與備份莊家

條帶化＝把整副牌發給所有人

如果整部電影只存在一顆硬碟，那顆碟就會被同看這部熱門片的觀眾擠爆。Tiger 的做法是條帶化 (striping)：把電影切成約 1 秒、約 0.5 MB 的區塊 (block)（兩小時電影約 7000 塊），輪流分散存到所有 cub 的硬碟，到最後一顆碟就『繞回』第 0 顆。

就像發撲克牌：一張一張輪流發給每個人，沒有人手上是一整副完整的牌——負載自然被攤平。

鏡像＝把備份拆碎分散

條帶化有個風險：任一碟或 cub 壞掉，每部電影都會出現破洞。Tiger 用鏡像 (mirroring) 解決：把每個區塊拆成數份次要副本 (secondaries)，份數由去叢集因子 (decluster factor) d（典型 4–8）決定，分散到 disk i+1 到 i+d。

妙處：一旦某 cub 倒下，補位的工作被攤分到好幾個 cub，而不是壓垮某一個。decluster factor 為 8 時，平常約 7/8 資源做正常工作，留 1/8 應付故障補位。

實用超能力

分散式排程與容錯

排程：slot 與兩個時間

Tiger 設計的心臟是排程，組織成一串 slot，每個 slot 代表『播放某部電影一個區塊』所需的工作。每位觀看者 (viewer) 對應一個 slot，記錄客戶位址、播放的檔案、目前位置、播放序號等。

兩個關鍵時間：

• 區塊播放時間 $T$：客戶端顯示一個區塊所需時間，約 1 秒，並須在各串流區塊間維持間隔 $T$。
• 區塊服務時間 $t$：cub 完成『讀區塊→封包化送上 ATM→更新狀態傳給下一個 cub』的最大時間，$t$ 遠小於 $T$。

一顆碟能服務的串流數約為：

$$ \frac{T}{t} $$

典型 $\frac{T}{t} > 4$。例如 5 個 cub、每個 3 顆碟，約可同時送 70 條串流；14-cub、56-disk 的設定實測可送 602 條 2-Mbps 串流。

容錯實測

flowchart LR
  A[主要區塊不可用 因 cub 或碟故障] --> B[改取鏡像的次要副本]
  B --> C[由 d 個 cub 分擔額外負載]
  C --> D[客戶端緩衝組裝後播放]

當主要區塊因故障取不到，就改抓鏡像的次要副本，額外負載由 $d$ 個 cub 分擔，只要排程留一點餘裕即可不中斷。實測：一個 cub（含 3 碟）故障下，資料遺失率僅 0.02%，遠優於設計目標。

深度探秘

把大檔切碎、四處平行下載

BitTorrent 的核心點子

BitTorrent 是專為下載大型檔案（含視訊）設計的點對點檔案分享應用。注意：它不是即時串流，而是先把檔案下載下來、之後再播。

核心設計是：把檔案切成固定大小的 chunk，這些 chunk 散落在點對點網路各處。客戶可同時從不同站點平行下載多個 chunk，大幅減輕任一站點的負擔——相較於從單一伺服器用 HTTP 下載，這對熱門大檔好得多。

.torrent 與 tracker

檔案要分享時，會建立一個 .torrent 檔，內含中介資料：

• 檔名與長度；
• tracker 的位置（URL）——一台集中式伺服器，管理該檔的下載；
• 每個 chunk 的 SHA-1 checksum，供下載後驗證內容。

用 tracker 是對『純點對點』原則的妥協，但能集中維護上述資訊。tracker 負責追蹤該檔的下載狀態（誰有完整檔、誰在下載），但一旦把部分節點清單給了新加入者，它的任務就結束了——後續排程是去中心化、由各 peer 自行決定。

生活妙喻

拼圖交換社團

把檔案想成一盒拼圖

• 整個檔案＝一盒完整拼圖。
• chunk＝一片片拼圖。
• 你不必跟同一個人要走全部拼圖，而是同時向好幾位社友各要幾片，很快就湊齊（平行下載）。

社團裡的角色

檔案就這樣像病毒般在社團裡擴散：需求越高，散布越快。leecher 湊齊後變 seeder，供應源越來越多。

實用超能力

tit-for-tat 與 rarest-first

怎麼鼓勵大家當『好公民』？

BitTorrent 靠 peer 既貢獻也索取才能運作。它內建獎勵機制 tit-for-tat（以牙還牙／禮尚往來）：

優先把資料下載權給那些曾經或正在上傳給你的人。這既是獎勵合作的誘因，也鼓勵『邊下載邊上傳』，把頻寬用到最滿。

機制細節：

• 一個 peer 同時對 $n$ 個 peer 解除阻塞 (unchoke)，依滾動計算的下載速率每 10 秒重新決定要 unchoke 誰。
• 每 30 秒對一個隨機 peer 做樂觀解除阻塞 (optimistic unchoking)，讓新進 peer 有機會參與、建立信譽。

rarest-first：先抓最稀有的

flowchart TD
  A[peer 檢視連線對象有哪些 chunk] --> B[找出最稀有的 chunk]
  B --> C[優先下載它]
  C --> D[稀有 chunk 快速散布 提升整體可得性]

BitTorrent 搭配 rarest-first 排程：peer 優先下載在其連線對象中最稀有的 chunk。這確保不易取得的片能快速散播開來，避免某些片成為瓶頸而拖垮整個 swarm 的健康度。

實用啟示：tit-for-tat 用『互惠』對抗搭便車，rarest-first 用『先補稀有』維持資源多樣性——兩者合起來讓去中心化下載又快又穩。

深度探秘

把智慧放在網路邊緣

即時廣播的挑戰

在網際網路上做即時視訊廣播極具挑戰：要能擴展到大量使用者、耗用大量頻寬與運算、滿足嚴格即時需求、且能適應網路變化。

從 IP multicast 到端系統途徑

最早的實驗直接建在 IP multicast 上，但缺點不少：許多路由器不支援、需在路由器維護 soft state，更根本的是違反端到端原則 (end-to-end principle)——這原則主張通訊功能唯有靠端點上的應用參與才能完整可靠地實現。

因此現今多採端系統途徑 (end-system approach)，又稱應用層多播 (application-level multicast)：控制與智慧放在網路邊緣而非網路內部，並形成一個覆蓋網路 (overlay network) 來承載多媒體流量。

ESM 的定位

End System Multicast (ESM) 是 CMU 開發、後由 Conviva 商品化的結構化點對點 (structured P2P) 即時視訊多播方案：peer 自組成一棵樹進行即時遞送。它的另一關鍵目標是透過自我組織 (self-organization) 來韌性面對節點加入／離開／故障與網路變化。

對照：CoolStreaming 走非結構化 (unstructured)、資料導向路線（類似 BitTorrent，但有滑動視窗的即時約束）；CDN（如 Akamai）則是基礎設施式而非 P2P。

生活妙喻

口耳相傳的人龍傳水

ESM 的樹＝人龍傳水桶

想像一場山林失火，源頭水源是 S（樹根，串流來源）。大家排成一棵人龍樹：A 從 S 接水，B、C 再從 A 接，依此往下傳。每個人把水（影格）傳給自己的『孩子』。

成員管理＝口耳相傳的八卦

沒有人掌握全體名冊。每個人只記得部分成員（partial view），並定期用 gossip（八卦／流言）協定：隨機挑一位成員，把自己知道的一小撮名單（附上『上次聽到他是什麼時候』的時間戳）分享過去。靠這種口耳相傳，名冊雖不完整卻夠用。

加入＝找一個好爸爸

新來的 G 先問源頭 S 要一份隨機候選名單，然後挨個探測 (probe)：看每位候選人目前拿到的吞吐量與延遲、以及他已經帶幾個孩子（飽和度）。G 會：

• 淘汰已飽和的候選（孩子太多）；
• 估算每位候選能提供的服務（吞吐取『對方回報』與『歷史資料』的較小值；延遲＝來源回報延遲＋探測延遲）；
• 以最佳可用頻寬為主選爸爸，若無頻寬資訊則看延遲。

實用超能力

離開、故障與效能感知調適

節點離開與故障

• 優雅離開：離開者先通知孩子，並繼續轉發一段時間，避免下游服務中斷。
• 故障：父節點定期送 alive 訊息給孩子，孩子收不到就判定故障。

兩種情況下，所有孩子都要重跑父節點選擇程序，並額外檢查候選不是自己的後代（以免接成迴圈）。

效能感知調適：讓樹自我最佳化

每個節點持續監控父節點給的服務。若偵測速率明顯低於來源預期速率，就觸發調適——但為避免抖動式亂跳 (thrashing)，須先等一段偵測時間 (detection time) 才決定換爸爸。

flowchart TD
  A[節點監控父節點服務] --> B{速率明顯低於預期}
  B -->|否| A
  B -->|是 且超過偵測時間| C[重跑父節點選擇]
  C --> D[換到更佳父節點]
  D --> E[樹持續重新評估 自我組織最佳化]

例如 C 覺得透過 A 拿到的吞吐不理想，跑一次父節點選擇後，改當 E 的孩子。整棵樹就這樣不斷重新評估、自我組織以最佳化整體效能（以吞吐為主、延遲為次）。

實用啟示：ESM 展示了如何只靠邊緣節點的局部資訊（部分名冊＋探測＋監控），就讓一個大規模即時廣播樹在動態網路中持續自我修復與最佳化。