數學魔術 紓通網路

撰文/艾佛羅斯(Michelle Effros) 寇特(Ralf Koetter) 梅達德(Muriel Medard)
翻譯/鍾樹人

 

　　現代通訊系統的歷史，早已刻劃了驚人的真知灼見。兼具數學家及工程師身份的夏儂（Claude E. Shannon），在近60年前就曾發動一場這樣的革命：他為通訊建立了新的數學理論基礎，亦即現今所稱的「資訊理論」，這項成果後來有了相當實用的發展，可進行資料的壓縮與可靠的傳輸。今天的網際網路、有線與無線電話系統，以及包含硬碟、CD、DVD與快閃記憶體等的儲存裝置裡，都看得到資訊理論的應用。

　　夏儂所處理的，是透過電話線進行通訊的個別電話。現今，越來越多資訊在共享網路上傳輸（好比網際網路），多位使用者同時透過相同的媒介通訊，可能是纜線、光纖，用無線系統的話，媒介則是大氣。共享網路或許能提高通訊系統的用處與效率，但也造成大家對共有資源的競爭。舉例來說，許多人都必須爭著連上伺服器以下載歌曲，或連上熱點來無線上網。

　　因此，挑戰在於如何讓大家和平共享網路資源──家裡有多個小孩的父母想必都清楚這個問題。網路技師在面對這項挑戰時，一般都會試著提供更多資源，但這種策略往往無法勝任。舉例來說，銅線、纜線或光纖現在已能提供寬頻給公司行號和住家使用，但鋪設費用卻相當昂貴，而且難以更動和擴充。超寬頻和複合天線傳輸系統可服務更多的無線網路用戶，但隨著需求越來越高，未來還是可能不敷使用。

　　我們也需要可提升效率的技術。網際網路與其他的共享網路目前大都透過路由器來轉送訊息，路由器也就是位於節點的交換器，而節點則是訊號傳輸路徑（或稱連結）交會的地方。路由器可把流入的訊號，轉送到通往訊號最終目的地的連結上。但如果我們追求的是效率，路由器仍會是最適合安裝在交會點上的裝置嗎？甚至，交換系統仍是正確的選擇嗎？

　　直到七年以前，還很少人會提出這樣的疑問。但德國俾勒菲特大學的阿斯威第（Rudolf Ahlswede），以及當時任職於香港中文大學的李碩彥、楊偉豪與蔡寧，在七年前發表了石破天驚的研究成果，為共享網路的資訊配送引進新途徑。這個方法稱為網路編碼（network coding），其中以編碼器取代路由器，並且傳送與訊息相關的證據，而非訊息本身。當接收器收到證據時，即可結合各項線索，推導出原始訊息。

　　這個方法聽起來或許有違直覺，但目前尚處於研究階段的網路編碼，卻具有可大幅提升各種通訊系統速度與可靠性的潛力，而且可能引發這個領域的下一場革命。當然，研究人員也在尋找其他可改善效率的方法，但就我們目前所知，其他方法一般只是延伸現有的途徑罷了。

不再把位元當車輛

　　阿斯威第與同事的提案，部份是以夏儂的想法為基礎，也就是，傳送關於訊息的證據，實際上可能比直接傳送資料本身來得更加有用。他們也知道，接收器一旦累積了足夠的線索，就能推導出原始資料，並不需要蒐集到已傳輸的所有證據。不同類型的線索可彼此替代，重要的是，當累積的線索整合在一起時，要能拼湊出原始訊息。（若事先把製造證據的規則告知接收器，或把該證據的使用方式夾帶在證據本身當中傳送，接收器就有辦法從證據中取得線索。）

　　傳統上都把通訊通道比擬為道路，而位元就像道路上行進的車輛，網路編碼卻打破了這樣的觀點。不過，若能了解通訊的運輸模型，倒是能幫助我們探討新架構的運作方式，並理解它為何深具潛力。

　　夏儂以數學證明了每個通道各有容量，也就是在特定時間內所能傳送的資訊量。只要不超過通道的容量，就有可靠的通訊。以交通狀況來做比擬，那麼某道路的容量，就等於這條道路每秒可安全承載的車輛數。假設交通流量低於道路容量，從道路一端進入的車輛，一般都一定能安全完整地從道路另一端出來（姑且不論少數的意外事件）。工程師根據這種運輸模型，建立了越來越複雜的通訊系統。舉例來說，夏儂所想的電話系統，會為每一次通話安排一條不同的「道路」；在傳統電話線上，兩通電話絕對不會同時透過相同的頻率共享同一條線路。

　　電腦網路（尤其是網際網路）基本上是個充滿交會、分歧與交叉道路的迷宮。在不同電腦之間傳輸的訊息，一般都要經由數條道路，才會抵達目的地。來自某訊息的位元，會被分成多個封包（也就是資訊超級高速公路上的共乘車輛或巴士），每個封包都會標明欲前往的目的地。路由器就位在道路交會的十字路口，檢查每個封包的標頭，然後把封包轉送到目的地去。

　　這個運輸模型造就了今日複雜的通訊系統，但諷刺的是，也正是這個模型阻礙了進步，畢竟位元不是車輛。狹路相逢的兩輛車只能輪流通過瓶頸，但兩個位元若同時抵達瓶頸，卻有更多選項，這正是網路編碼可以發揮之處。

網路編碼怎麼運作？

　　這裡，虛構了一個含有六個節點的網路，幫我們釐清這些可能的選擇。回想一下，在電腦裡，所有的訊息都由一連串的二進位碼組成。假設在網路裡，每個連結（也就是路徑）每秒可攜帶一個位元（0或1），而且只能順著箭號所指的方向前進。位於網路節點A的用戶艾咪，想以每秒一位元的速度把訊息傳到節點D給黛娜。另一方面，位於節點B的班恩，也希望在相同時間、以相同速度，把訊息傳到節點C給卡爾。那麼，艾咪和班恩的需求能同時達成，並且不超過任何連結的傳輸容量上限嗎？

　　若是路由系統，前景似乎並不樂觀。從艾咪到黛娜，以及從班恩到卡爾，這兩條路徑都必須經過連結，於是這個連結就成了只能單線通車的狹橋。位於節點E的路由器，也就是連結的起點，每秒總共接收到二位元的資料（一位元來自連結，一位元來自連結），但由於連結的容量只有一位元，路由器每秒只能傳送一位元資料給連結。在這個運輸模型中，這種瓶頸會造成可怕的塞車，越來越多位元隨著時間累積，等待輪到自己前進的時機。

　　但若採用新方法，把一般的路由器換成編碼器，解決塞車的方法就不會只有請出交通警察一項了。編碼器所傳送的並不是累積在瓶頸處那些真實的位元串流，而是相當不同的訊息。舉例來說，它可能把某一秒內抵達的1全部累加起來，如果總和為偶數，編碼器會送出一個0；如果是奇數，則送出一個1。因此，如果連結同時從連結和各收到一個1和0，最後會送出一個1；如果從連結和收到兩個0，或兩個1，則傳送一個0。這個結果再由路由器F分別轉送到連結和，給卡爾和黛娜。

　　這個方法把節點E收到的兩個位元，轉換成混合的單一位元。這樣的位元串流似乎沒什麼道理，我們提出的編碼器，等於以混淆兩者的方式，把兩通電話混合成另一通了。也正因為這種顯而易見的怪誕特性，讓這個方法長久以來一直乏人問津。

　　但表面上的瘋狂有時卻是真正的創新。混合的位元串流或許無法完整描述原始的傳輸，但卻能提供有關兩者的證據。讓我們另外透過連結，把艾咪的訊息傳送給卡爾，並且沿著連結，把班恩的訊息傳給黛娜。傳送這兩個訊息會動用到網路資源：連結與，但在路由系統中，想滿足艾咪與班恩的需求，並不會使用到這兩個連結。卡爾的節點收到來自艾咪的傳輸，並且根據每次由連結傳來的訊息，即可知道艾咪與班恩所發送的1的個數總和為偶數或單數。如果卡爾所在的節點，也「知道」連結起始點處的編碼器所用的規則，或是能根據證據本身自行得出規則，那就能從累積的證據裡解出班恩傳送的訊息。相同地，黛娜所在的節點也能解出艾咪的訊息。

顯而易見的好處

　　這個策略完成了兩項原本在運輸模型的限制下根本無法想像的目標。首先，位元離開一個節點後，可同時傳送到兩條路徑上；這可是車輛無法達成的事。其次，兩個位元串流在抵達瓶頸的起始點時，可結合成單一串流；當兩部車狹橋相逢時，可沒辦法合成單一車體，得等其中一輛先行通過，另一輛才可能過橋。

　　以上我們所提的六節點模型，與李碩彥等人和阿斯威第小組於2000年最初發表的模型略有差距，但仍可示範資料處理的方式。這種方式可避開瓶頸，因此可能在不增加通道的狀況下，提高網路的容量。若單單採用路由器，我們的六節點網路，將保持平均每秒0.5位元的同步傳輸速度。（因為這兩個彼此競爭的傳輸須共享連結，所以對競爭的兩個需求來說，有效的資料傳輸率應各為每兩秒一位元，亦即每秒0.5位元。）但若採用網路編碼，同一系統所能支援的同步傳輸率，卻是每秒一位元，可見網路編碼使容量倍增了。

　　網路編碼有時甚至能讓容量增加更多，有時卻沒有效果，但這個方法永遠不會減損網路的容量，因為即使在最差的狀況下，它也只是模擬路由器系統的行為。而且，它應該可提升網路的可靠性，並且更有效地防禦重要網路使其不受攻擊，因為證據具有可替代性，這表示即使有些證據封包遺失了，也不至造成問題。

多播網路上的應用

　　截至目前為止，有關網路編碼應用的研究大都把重心放在多播網路上，在這類網路中，所有的接收器都必須取得相同的訊息。例如網路電玩，每當一位玩家動作之後，就必須靠多播系統更新每一位玩家的畫面。透過網路播送影片或現場轉播的體育賽事，以及在線上對廣大客戶群發表新軟體，也都需要透過多播網路。這類網路目前仍採用路由器，讓我們回到剛才的運輸比喻，有助於解釋為什麼這類系統常常很難設計。

　　假設國內的公路上湧現了大量車潮。每個路由器，就像一個站在交叉路口指揮交通的警察。後來的車輛排在先抵達的車陣之後，交通警察依次詢問每輛車的目的地，然後為車輛指引方向。系統設計的目標，是讓每個路由器在引導車流時，不僅能讓後來的每一輛車快速抵達目的地，也能讓全國整體的運輸系統盡可能地滿足更多駕駛的需求。

　　即使是中央部會層級的設計師，備有全國所有道路的地圖，仍然很難決定每個路由器該套用哪些規則，才是最好的策略。若網路狀況會隨時間改變，設計起來就更難了：交通尖鋒時刻、修路、車禍、體育賽事，這些都會經常改變道路及道路需求。

　　直覺上看來，根據網路編碼來設計系統應該會更難，因為有更多選擇必須列入考慮。某個節點可能會仿效路由器，原封不動地轉送資料；但這個節點在傳送資料之前，也可能把兩個以上的資料串流混合成一個，而混合方式可能還需要進一步考慮；還有，不同的節點可能採用不同的演算法。

　　幸好，這個邏輯並不正確。有時，更多的選擇其實反而讓事情簡化。少了編碼，多播系統的結構工程師得盡可能列出從發送器到每個接收器之間的路徑，然後決定網路可同時支援其中多少路徑。即使是簡單的網路，想要找出並測試所有的路徑組合，仍是令人抓狂的工作。

　　相對之下，利用網路編碼架構的多播系統卻相當容易設計。驚人的是，編碼網路所運用的數學函數，只有加法和乘法。另外，網路中每個編碼器裡所選用的函數或規則，雖然與訊息及其他編碼函數無關，而且完全不考慮網路的整體設計，但是系統整體的運作，卻有很高的機率會發揮出最佳效能。就算系統會隨著時間改變，好比移動式或可重組態網路，但是它們並不需要重新設計，就可以一直保持最佳狀態。

明日網路暢通無阻

　　因此，若把路由器換成編碼器，網路的運作將會變得極為不同。訊息在網路上傳送的方式也會跟著改變：不僅不同的傳輸可共享「道路」，不同來源的訊息也可緊密組合在一起。或許有人會擔心，把不同的傳輸組合在一起，可能影響到訊息的安全性。但更可能的狀況是，在網路中流動的將是無法局部解密的代數流。網路用戶將在不知不覺中彼此合作，互蒙其利，不僅可更頻繁或更快下載資料，而且在無線網路中，也能改善能量使用的效率。（因為每一次的無線傳輸都會消耗能量，而網路編碼系統的節點，可把來自鄰近的不同訊息結合在一起，一次傳輸出去，因此可降低能量的耗損。）

　　不僅如此，下載影片時的遲滯現象，以及漏接行動電話的狀況，也會大為減少。在網際網路上，路由器故障或因維修而暫停服務，以及遺失封包的現象層出不窮。正因為如此，人們有時必須重新下載網頁，有時網頁也會費時很久才出現在螢幕上。有了網路編碼，網路將會變得更可靠，因為不需要集合所有的證據，就能連結成功。

　　網路管理者並不需要增加額外的通訊通道，就能提供這類好處，因為現有的通道可發揮更大的用處。也因為如此，網路編碼可與其他的通訊技術互補，讓使用者能物盡其用。

　　有的時候，用戶可能感覺得到網路編碼的運作，因為有些常見於應用的運作方式可能發生改變，譬如點對點傳輸。到目前為止，想要下載某一個檔案，一般都會先找出誰的機器裡存有自己想要的電子檔。然而，在採用網路編碼的系統裡，檔案再也不是以完整的形式、或可辨識的片段存在。

　　不過，用戶本人在下載目標檔案時，並不需要知道該如何取得必要的證據。當使用者的電腦或電話把下載檔案的請求送到網路內，這個用戶的電腦或區域伺服器就會在網內搜尋，找出與目標檔案相關的證據。這些證據是一群與目標檔案有關、以代數混合的資訊片段，可協助還原出原始檔案。拼拼圖時，是把整體圖案所分割出來的可辨識的小圖片湊合在一起，但網路編碼系統並非如此，伺服器或個人的電腦要拆解的是一組代數算式。另外，幸運的是，在這整個過程當中，大部份人都對這些運作一無所知，就好像大部份人也不知道行動電話含有繁複的錯誤校正運算一樣。

　　美國軍方已經體認到網路編碼的可靠性，將提供資金，贊助研究網路編碼在移動式特定網路（mobile ad hoc network）上的應用。移動式特定網路可快速形成，在瞬息即變的環境中深具價值，譬如在戰場上，一定要有可靠的通訊，但卻很難架設與維護光纖纜線或行動基地台。在特定網路中，每位士兵的無線電都可變成通訊系統裡的節點，而每個節點都會向外搜尋，與鄰近的節點連接，進而建立起相互連結的網路。每個節點都可傳送並接收訊息，並擔任中間媒介，把訊息轉送到目標接收器。這項技術大幅提升了通訊能力，遠比單一節點的傳輸範圍要廣得多；而且極具彈性，因為網路會跟著使用者移動，不斷根據需求重新組態、重新建立連結。

　　網路編碼在改變網路作用方式之餘，也可能以超乎我們想像的方式影響人類社會。但值此同時，身為網路編碼研究者的我們，正在思考實作上的障礙。事實上，把路由器系統轉換成網路編碼系統，還算是較小的問題。更換時只要循序漸進，而非一次全面換新，就可處理系統轉換的問題。有些路由器只需要重新設計程式，另外一些無法執行編碼運算的路由器，則可漸漸替換掉。

　　如何處理更換機器之外的議題，反而才是較大的挑戰。舉例來說，當接收器節點可取得足夠的證據，從混合的資訊裡還原出原始資料時，混合資訊就是不錯的策略。這種狀況在多播網路裡一向成立，但在一般狀況下就未必如此了。不僅如此，在某些狀況下，譬如傳送多個多播訊息時，使用者可能很難、或甚至無法從混合資訊裡解讀出適當的結果。那麼，當多個通訊共享同一個網路時，節點要怎麼判斷出哪些訊息可以混合，哪些又不行？其他的問題還包括：網路編碼在無線網路與有線網路中的應用有何區別？網路編碼在安全性上的優勢與意義為何？當不同使用者的資料不得不混合在一起傳送時，通訊服務又該如何計費呢？通訊網路已成為許多人生活中不可或缺的一部份，我們與其他人正在匯集全球各地的研究力量，努力提升通訊網路的傳輸容量；與此同時，我們也在思考該如何解決上述的種種難題。

【本文轉載自《科學人雜誌》2007年7月號】