現代通訊系統的歷史，早已刻劃了驚人的真知灼見。兼具數學家及工程師身份的夏儂（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年最初發表的模型（詳見54頁〈網路編碼迷蝴蝶〉）略有差距，但仍可示範資料處理的方式。這種方式可避開瓶頸，因此可能在不增加通道的狀況下，提高網路的容量。若單單採用路由器，我們的六節點網路，將保持平均每秒0.5位元的同步傳輸速度。（因為這兩個彼此競爭的傳輸須共享連結，所以對競爭的兩個需求來說，有效的資料傳輸率應各為每兩秒一位元，亦即每秒0.5位元。）但若採用網路編碼，同一系統所能支援的同步傳輸率，卻是每秒一位元，可見網路編碼使容量倍增了。
網路編碼有時甚至能讓容量增加更多，有時卻沒有效果，但這個方法永遠不會減損網路的容量，因為即使在最差的狀況下，它也只是模擬路由器系統的行為。而且，它應該可提升網路的可靠性，並且更有效地防禦重要網路使其不受攻擊，因為證據具有可替代性，這表示即使有些證據封包遺失了，也不至造成問題……
【更多精采內容~~請閱《科學人》雜誌 數學魔術‧疏通網路 2007年7月號】
留言列表
