一類分布式網(wǎng)絡(luò)恢復(fù)協(xié)議的可實(shí)現(xiàn)協(xié)議

一類分布式網(wǎng)絡(luò)恢復(fù)協(xié)議的可實(shí)現(xiàn)協(xié)議（王亞宏、鄔賀銓）
    摘要認(rèn)可實(shí)現(xiàn)的角度，對(duì)現(xiàn)有的一類基于數(shù)字交叉連接設(shè)備的分布式網(wǎng)絡(luò)
恢復(fù)協(xié)議進(jìn)行比較詳細(xì)的分析，提出其中共同存在的一些問題，并給出了一些
可能的解決方案。
    關(guān)鍵詞  分布式網(wǎng)絡(luò)恢復(fù)  數(shù)字交叉連接  網(wǎng)絡(luò)恢復(fù)協(xié)議
    一、引言
    現(xiàn)代信息社會(huì)中，通信網(wǎng)成為支撐現(xiàn)代經(jīng)濟(jì)的最重要的基礎(chǔ)結(jié)構(gòu)之一。隨
著電信網(wǎng)規(guī)模和容量的不斷擴(kuò)大以及通信傳輸技術(shù)朝著超高速和大容量的方向
發(fā)展，對(duì)傳送網(wǎng)的生存性提出了愈來愈高的要求。
    基于數(shù)字交叉連接（DXC）設(shè)備的網(wǎng)絡(luò)恢復(fù)是基于DXC設(shè)備固有的交叉連接
功能，通過提供為受影響的業(yè)務(wù)進(jìn)行重新配置路由來實(shí)現(xiàn)的�；�于DXC的網(wǎng)絡(luò)
恢復(fù)最主要的特點(diǎn)是能夠高度共享網(wǎng)絡(luò)中的冗余資源，20%-30％的冗余容量就
可以達(dá)到較高的業(yè)務(wù)保護(hù)能力。并且基于DXC的分布式網(wǎng)絡(luò)恢復(fù)的方法有可能
實(shí)現(xiàn)網(wǎng)絡(luò)自愈。在發(fā)生故障時(shí)，能自動(dòng)對(duì)受損的工作通道進(jìn)行恢復(fù)，恢復(fù)時(shí)間
較短，有可能實(shí)現(xiàn)無損傷恢復(fù)，因此得到十分廣泛的研究。目前的分布式網(wǎng)絡(luò)
協(xié)議的機(jī)理是相似的，可將其歸為一類，本文中，第二節(jié)先介紹這一類分布式
網(wǎng)絡(luò)恢復(fù)協(xié)議的原理和單個(gè)協(xié)議的特點(diǎn)；第三節(jié)中從一個(gè)可實(shí)現(xiàn)的角度分析該
類分布式網(wǎng)絡(luò)恢復(fù)協(xié)議，提出該類協(xié)議的一些共同問題，并給出一些相應(yīng)的解
決方法：最后在第四節(jié)中對(duì)基于DXC的網(wǎng)絡(luò)恢復(fù)策略作了小結(jié)。
    二、分布式網(wǎng)絡(luò)恢復(fù)協(xié)議
    自從1987年W.D.Grover提出第一個(gè)基于DXC分布式網(wǎng)絡(luò)恢復(fù)協(xié)議以來，由
于分布式網(wǎng)絡(luò)恢復(fù)時(shí)間快等特點(diǎn)，得到十分廣泛的研究。現(xiàn)有的分布式網(wǎng)絡(luò)恢
復(fù)協(xié)議除了Grover的SHN（自愈網(wǎng)）算法，還有Bellcore的FITNESS對(duì)算法、
RREACT算法、Komine算法、雙向算法和Trans算法等。這些協(xié)議的原型是相似
的，一般基于三個(gè)階段的網(wǎng)絡(luò)過程。下面以單鍵路失效時(shí)鏈路恢復(fù)為例描述這
三個(gè)過程。
    當(dāng)一條鏈路的失效被檢測(cè)到后，該受損鏈路的兩端節(jié)點(diǎn)一個(gè)被指定為發(fā)送
者，另一個(gè)被指定為選擇者（根據(jù)事先指定的規(guī)則），參加恢復(fù)過程的其他節(jié)
點(diǎn)成為中介節(jié)點(diǎn)。首先，發(fā)送者向所有相鄰的節(jié)點(diǎn)廣播（洪泛）恢復(fù)消息，為
限制恢復(fù)消息數(shù)目和算法執(zhí)行時(shí)間，一般對(duì)消息選擇性廣播，例如限制消息的
轉(zhuǎn)接次數(shù)（跳數(shù)）；中介節(jié)點(diǎn)更新收到的恢復(fù)消息，并根據(jù)特定的算法向相鄰
節(jié)點(diǎn)選擇性廣播收到的恢復(fù)消息。當(dāng)恢復(fù)消息到達(dá)選擇者時(shí)，這就意味著存在
一條或多條恢復(fù)路徑。這時(shí)選擇者在選定的恢復(fù)路徑上向發(fā)送者發(fā)出確認(rèn)消息，
并預(yù)先保留該路徑上的空閑容量（預(yù)留也可在恢復(fù)消息廣播或證實(shí)消息廣播時(shí)
進(jìn)行）。
    當(dāng)發(fā)送者收到確認(rèn)消息并驗(yàn)證恢復(fù)通道后，它沿著所選定的恢復(fù)通道向選
擇者發(fā)送證實(shí)消息：當(dāng)中介節(jié)點(diǎn)收到證實(shí)消息，它根據(jù)證實(shí)消息消息中的指令
重新配置其交叉連接矩陣；在選擇者收到證實(shí)消息后，它重新配置其交又連接
矩陣，便受損的工作通道轉(zhuǎn)到新的恢復(fù)通道上。當(dāng)所有的受損容量得到恢復(fù)或
再也不能恢復(fù)，恢復(fù)過程結(jié)束。
    SHN算法是以單個(gè)受損信道為單位進(jìn)行恢復(fù)，并采用物理層信令。FINESS
算法則采用捆綁（bundling）恢復(fù)，采用多輪消息、“波動(dòng)”來搜尋所有的
可恢復(fù)通道。Trans算法與FINESS算法的不同在證實(shí)消息廣播階段，對(duì)每一條
恢復(fù)消息，它發(fā)送多條證實(shí)消息。Komine算法與FINESS算法的不同是它以最
短路徑優(yōu)先進(jìn)行受損通道的依次恢復(fù)，而FINESS算法則是最大恢復(fù)流量?jī)?yōu)先。
PREACT則是由恢復(fù)消息收集網(wǎng)絡(luò)中的各節(jié)點(diǎn)間的空閑信道數(shù)據(jù)，然后由選擇
節(jié)點(diǎn)進(jìn)行恢復(fù)通道選擇。雙向算法則與以上算法不同的是它是從受損鏈路的
兩個(gè)節(jié)點(diǎn)處同時(shí)發(fā)送恢復(fù)消息，通過兩種不同的恢復(fù)消息在中介節(jié)點(diǎn)處的耦
合來實(shí)現(xiàn)恢復(fù)通道的尋找和確認(rèn)。
    三、可實(shí)現(xiàn)分析
    認(rèn)可實(shí)現(xiàn)的角度來看，該類分布式網(wǎng)絡(luò)恢復(fù)協(xié)議存在的問題包括：2秒的
恢復(fù)時(shí)間限制、統(tǒng)一處理鏈路失效和節(jié)點(diǎn)失效、消息對(duì)空閑容量的爭(zhēng)奪、路
由成環(huán)、數(shù)據(jù)傳輸?shù)目煽啃砸约翱苫貜?fù)性恢復(fù)等方面。下面依次分析和討論。
    1.2秒的恢復(fù)時(shí)間限制
    從中分析業(yè)務(wù)對(duì)生存性的要求，一般將網(wǎng)絡(luò)自愈的恢復(fù)時(shí)間要求定為2秒，
以達(dá)到對(duì)大多數(shù)業(yè)務(wù)實(shí)觀無損傷（hitless）的恢復(fù)�，F(xiàn)有的分布式恢復(fù)方案
一般都沒有考慮實(shí)現(xiàn)替代路由的物理實(shí)現(xiàn)所需的時(shí)間，直到1994年T.H.Wu等
人提出在現(xiàn)有的DXC設(shè)備串行處理的結(jié)構(gòu)下，實(shí)現(xiàn)替代路由的交叉連接所需的
時(shí)間對(duì)分布式恢復(fù)的2秒的恢復(fù)時(shí)間R標(biāo)有很大的影響。提出采用捆綁恢復(fù)和
優(yōu)先級(jí)恢復(fù)以及采用分布式并行處理的DXC系統(tǒng)結(jié)構(gòu)的方法來實(shí)現(xiàn)2秒的恢復(fù)
時(shí)間目標(biāo)。
    另外，W.D.Grover等人在提出交叉殞連的方法，其中心思想是將基于D
XC的網(wǎng)絡(luò)中的空閑信道接一定的方法先預(yù)連起來，當(dāng)網(wǎng)絡(luò)中發(fā)生故障時(shí)，已
經(jīng)有交叉連接好的通道，只需采用簡(jiǎn)單切換的方法即可恢復(fù)一定的受損信道，
而無需測(cè)試，從而減少恢復(fù)時(shí)間。
    2．統(tǒng)一處理鍵路失效和節(jié)點(diǎn)失效
    該類協(xié)議一般都將節(jié)點(diǎn)失效等價(jià)于多鏈路失效，這樣從算法本身來說，
能夠處理節(jié)點(diǎn)失效的情況，盡管效率可能會(huì)低一一些。但是應(yīng)當(dāng)看到這是以
算法本身首先能區(qū)公故障是節(jié)點(diǎn)失效還是鏈路大效為前提的，而在實(shí)際中
（例如SDH中），這是不可能的，故障兩端的節(jié)點(diǎn)只能察覺發(fā)牛故障，而不
能分辨出是相鄰節(jié)點(diǎn)失效或只是鏈路失效。
    另外，大多數(shù)算法都基于發(fā)送者一選擇者機(jī)制，對(duì)于發(fā)送者、選擇者
的角色分配，～般都事先指定或根據(jù)節(jié)點(diǎn)的ID號(hào)自動(dòng)確認(rèn)，但是在節(jié)點(diǎn)故
障，設(shè)想一下，如果已確認(rèn)為發(fā)送者的節(jié)點(diǎn)發(fā)生失效，這時(shí)由于發(fā)送者已
失效，網(wǎng)絡(luò)根本就沒有恢復(fù)尋道消息的源，網(wǎng)絡(luò)對(duì)故障沒有任何處理。反
之，著已確認(rèn)為選擇者的節(jié)點(diǎn)發(fā)生失效，網(wǎng)絡(luò)中消息沒有了接收者，協(xié)議
同樣失效，而且，在節(jié)點(diǎn)故障情況下，是很難事先指定發(fā)送者和選擇者（
盡管Komine算法考慮節(jié)點(diǎn)失效的情況，但它依然是假定了發(fā)送者和選擇者
的事先確認(rèn)，所以依然存在上述的問題）。
    盡管節(jié)點(diǎn)失效的情況在網(wǎng)絡(luò)故障中是很少有的觀象，但是應(yīng)當(dāng)看到，
算法不應(yīng)在節(jié)點(diǎn)失效的這種情況下作出錯(cuò)誤判斷，它應(yīng)該要么進(jìn)行一定的
恢復(fù)，要么什么也別作。
    因此，對(duì)現(xiàn)有協(xié)議要么采用一定的機(jī)制進(jìn)行故障類型確認(rèn)，但這需要
延長(zhǎng)恢復(fù)時(shí)間或只采用通道恢復(fù)，這時(shí)由受損通道的源捐書點(diǎn)啟動(dòng)恢復(fù)過
程，但是這種情況下，會(huì)延長(zhǎng)恢復(fù)時(shí)間（需通道居告警信號(hào)），并且存分
多個(gè)不同節(jié)點(diǎn)對(duì)的消息，這些消息會(huì)加劇對(duì)空閑信道（或DXC端口）的爭(zhēng)
奪。
    我們提出一種能統(tǒng)一處理節(jié)點(diǎn)和鍵路實(shí)現(xiàn)的協(xié)議，稱為對(duì)稱的分布式
路由再選擇多法（SDRA：Symmetrical Distributed Rerouting Algorithm），
該協(xié)議基于節(jié)點(diǎn)問對(duì)稱的角色分配，其關(guān)鍵處在于在消息廣播的過程中進(jìn)
行故障類型確認(rèn)，通過消息耦合的兩種不同類型：節(jié)點(diǎn)耦合和鏈路耦合，
來區(qū)分節(jié)點(diǎn)失效和鏈路失效的情況。消息頭的第一字節(jié)為故障對(duì)應(yīng)瑞的節(jié)
點(diǎn)ID，第二字節(jié)為該發(fā)送消息的節(jié)點(diǎn)ID，在鏈路失效的情況下，兩消息相
遇時(shí)這兩字節(jié)的ID號(hào)構(gòu)成對(duì)應(yīng)關(guān)系，稱為鏈路耦合；在節(jié)點(diǎn)失效的情況下，
兩消息相遇時(shí)第一個(gè)字節(jié)ID號(hào)相同，稱為節(jié)點(diǎn)耦合；因此可判斷出是節(jié)點(diǎn)
失效和鍵路失效，從而統(tǒng)一處理。
    3．消息對(duì)空閑容量的爭(zhēng)奪
    即使在單鏈路失效、鏈路恢復(fù)的情況下，網(wǎng)絡(luò)中只存在一個(gè)節(jié)點(diǎn)對(duì)之
間的消息發(fā)送，也存在消息對(duì)空閑容量（或DXC空閑端口）的爭(zhēng)奪。這些
協(xié)議一般采用先到先服務(wù)的方式進(jìn)行，但叮能發(fā)生由于消息的爭(zhēng)奪而形成
死鎖的情況。在多鏈路失效和節(jié)點(diǎn)失效以及通道恢復(fù)的情況下，由于網(wǎng)絡(luò)
中存在多個(gè)源于不同源一宿節(jié)點(diǎn)對(duì)之間的消息，這些消息之間更容易發(fā)生
爭(zhēng)奪空閑信道的情況，而導(dǎo)致死鎖發(fā)生。而且，對(duì)于～個(gè)節(jié)點(diǎn)既充當(dāng)發(fā)送
者的角色，義充當(dāng)接送者的角色，對(duì)許多算法來說，合理有效的通道預(yù)留
是很難實(shí)現(xiàn)的。
     一種可行的解決方法，是對(duì)每一源宿節(jié)點(diǎn)對(duì)間的消息進(jìn)行分配優(yōu)先
級(jí)，采用比較優(yōu)先級(jí)的方法解決沖突，但要合理地進(jìn)行優(yōu)先級(jí)分配也是很
困難的，或者采用類似總線以太網(wǎng)的避免沖撞檢測(cè)的隨機(jī)退讓方法，但該
方法對(duì)恢復(fù)時(shí)間和效率以及穩(wěn)定性萬面的影響需作進(jìn)一步的考慮。
    4、路由成環(huán)
    在鏈路恢復(fù)的情況下，很容易造成路由環(huán)路，從而不必要地占用了網(wǎng)
絡(luò)中的可工信道，影響恢復(fù)效率，如果避免了路由環(huán)路，則恢復(fù)過程中會(huì)
釋放原來被路由環(huán)路占用的信道，這樣恢復(fù)效率會(huì)有所改善。
    5．?dāng)?shù)據(jù)傳輸?shù)目煽啃?br />    數(shù)據(jù)傳輸?shù)目煽啃允侵溉绾伪ＷC各節(jié)點(diǎn)間傳遞信息的各消息的完整性
和正確性。因此除了可靠的傳輸協(xié)議和糾錯(cuò)外，還需要考慮消息的安全性，
防止惡意節(jié)點(diǎn)的欺詐行為，特別是在多運(yùn)營(yíng)者的環(huán)境下，進(jìn)行消息認(rèn)證和
不可否認(rèn)的確認(rèn)是有必要的。一般可采用類似于網(wǎng)絡(luò)安全協(xié)議方法，如數(shù)
據(jù)加密，數(shù)字簽名等。
    6．可回復(fù)性恢復(fù)
    網(wǎng)絡(luò)恢復(fù)算法的可回復(fù)性是指在失效鏈路得到修復(fù)后，鏈路應(yīng)能回復(fù)
到失效發(fā)生前的正常情況下的路由配置，因?yàn)檎�常情況下的路由和流量配
置總是基于一定策略的最優(yōu)配置。一般來說，集中式恢復(fù)較分布式恢復(fù)易
實(shí)現(xiàn)可回復(fù)性，鏈路恢復(fù)較通道恢復(fù)易實(shí)現(xiàn)回復(fù)性。因此若需進(jìn)行可恢復(fù)
性恢復(fù)，需對(duì)協(xié)議進(jìn)行改進(jìn)，以保留故障發(fā)生前的配置數(shù)據(jù)；值得注意的
是：在通道恢復(fù)，由于有受損通道的容量釋放過程，實(shí)現(xiàn)可回復(fù)性是比較
困難的，代價(jià)較高，而可回復(fù)性恢復(fù)是非實(shí)時(shí)的，因此通過網(wǎng)管配合處理
應(yīng)當(dāng)更適宜。
    四、結(jié)束語
    本文從可實(shí)現(xiàn)的角度對(duì)現(xiàn)有的一類基于數(shù)字交叉連接設(shè)備的分布式網(wǎng)
絡(luò)恢復(fù)協(xié)議進(jìn)行了詳細(xì)的分析，提出其中存在的一些問題，并給出了一些
可能的解決方案。因此也應(yīng)當(dāng)看到，分布式的網(wǎng)絡(luò)恢復(fù)協(xié)議是不夠成熟的，
需作進(jìn)一步的研究。相對(duì)而言，集中式網(wǎng)絡(luò)恢復(fù)和混合的網(wǎng)絡(luò)恢復(fù)協(xié)議是
能夠在實(shí)際中首先得到應(yīng)用，但是在具體采用這兩類網(wǎng)絡(luò)恢復(fù)方案時(shí)，需
作進(jìn)一步的考慮，例如集中式網(wǎng)絡(luò)恢復(fù)協(xié)議需考慮更高的恢復(fù)效率以及更
好地與網(wǎng)絡(luò)規(guī)范和網(wǎng)絡(luò)管理相協(xié)調(diào)。