陳 量，瞿 輝（重慶金美通信有限責(zé)任公司，重慶　400030）

?

基于SDN思路的組播實(shí)現(xiàn)

陳 量，瞿 輝
（重慶金美通信有限責(zé)任公司，重慶400030）

摘 要：軟件定義網(wǎng)絡(luò)SDN的思想是將網(wǎng)絡(luò)控制平面和數(shù)據(jù)轉(zhuǎn)發(fā)平面分離，采用標(biāo)準(zhǔn)化南向接口協(xié)議，集中的控制路由交換設(shè)備的轉(zhuǎn)發(fā)行為，實(shí)現(xiàn)網(wǎng)絡(luò)可定制和可擴(kuò)展。為避免傳統(tǒng)組播路由協(xié)議的復(fù)雜性和各設(shè)備廠商協(xié)議實(shí)現(xiàn)的不一致性，基于SDN思想在控制平面設(shè)計(jì)組播網(wǎng)絡(luò)服務(wù)，實(shí)現(xiàn)網(wǎng)絡(luò)組播業(yè)務(wù)功能。組播網(wǎng)絡(luò)服務(wù)通過(guò)標(biāo)準(zhǔn)OpenFlow協(xié)議和廣域網(wǎng)中的路由器建立控制連接，下發(fā)對(duì)應(yīng)網(wǎng)絡(luò)控制規(guī)則，基于鏈路發(fā)現(xiàn)協(xié)議LLDP和標(biāo)準(zhǔn)ICMP協(xié)議獲取網(wǎng)絡(luò)拓?fù)浜徒M播組拓?fù)?，建立組播樹(shù)；在此基礎(chǔ)上，再基于組播組業(yè)務(wù)特性選取最短路徑樹(shù)、低代價(jià)最短路徑樹(shù)等路徑計(jì)算算法，計(jì)算組播轉(zhuǎn)發(fā)路徑并下發(fā)到路由器中實(shí)現(xiàn)組播業(yè)務(wù)轉(zhuǎn)發(fā)。該方法經(jīng)過(guò)設(shè)計(jì)驗(yàn)證，并和傳統(tǒng)組播路由協(xié)議對(duì)比分析，具備強(qiáng)大的擴(kuò)展性和靈活性，實(shí)現(xiàn)簡(jiǎn)單，易于部署。

關(guān)鍵詞：軟件定義網(wǎng)絡(luò)；OpenFlow協(xié)議；鏈路發(fā)現(xiàn)協(xié)議；低代價(jià)最短路徑樹(shù)；組播；擴(kuò)展性

1 引 言

SDN（軟件定義網(wǎng)絡(luò)）作為一種革命性的網(wǎng)絡(luò)新技術(shù)，已逐步得到推廣應(yīng)用?；诳刂坪娃D(zhuǎn)發(fā)分離的思想，將原有網(wǎng)絡(luò)設(shè)備交互實(shí)現(xiàn)的復(fù)雜協(xié)議轉(zhuǎn)換為靈活的、可編程的軟件化網(wǎng)絡(luò)服務(wù)，能夠提供更加統(tǒng)一的網(wǎng)絡(luò)控制手段［1-2］。

在當(dāng)前廣域網(wǎng)組網(wǎng)應(yīng)用中，傳統(tǒng)的PIM、DVMRP等組播路由協(xié)議應(yīng)用并不廣泛，受限于每一跳網(wǎng)絡(luò)設(shè)備均需支持組播路由協(xié)議，組播業(yè)務(wù)需克服較大的協(xié)議開(kāi)銷(xiāo)和不同廠商可能存在的協(xié)議實(shí)現(xiàn)不一致等問(wèn)題。為規(guī)避上述問(wèn)題，部分應(yīng)用參考P2P技術(shù)，采用了應(yīng)用層組播技術(shù)，該機(jī)制不依賴(lài)于第3層組播路由協(xié)議，但在網(wǎng)絡(luò)傳輸效率上不如IP層組播，需要功能強(qiáng)大的服務(wù)器進(jìn)行支撐。

基于SDN思想構(gòu)建網(wǎng)絡(luò)，能夠?yàn)閷?shí)現(xiàn)廣域網(wǎng)組播業(yè)務(wù)提供一個(gè)新的技術(shù)思路。目前較為流行的SDN控制器，能夠提供網(wǎng)絡(luò)拓?fù)涑尸F(xiàn)、路由計(jì)算、流量工程等基本網(wǎng)絡(luò)控制服務(wù)，并基于標(biāo)準(zhǔn)的南向接口協(xié)議對(duì)路由器進(jìn)行控制。由此，SDN控制器也能夠在動(dòng)態(tài)獲取組播成員網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上，結(jié)合組播路徑樹(shù)算法，為每一個(gè)路由器生成組播轉(zhuǎn)發(fā)規(guī)則，并通過(guò)標(biāo)準(zhǔn)協(xié)議進(jìn)行下發(fā)，從而實(shí)現(xiàn)IP層高效的組播業(yè)務(wù)轉(zhuǎn)發(fā)。該方式能夠降低組播路由協(xié)議的開(kāi)銷(xiāo)，避免不同廠商設(shè)備協(xié)議實(shí)現(xiàn)的不一致性，并能夠靈活部署和升級(jí)。

針對(duì)SDN網(wǎng)絡(luò)，結(jié)合路由器OpenFlow協(xié)議特性和組播樹(shù)路徑計(jì)算算法，使用SDN控制器獲取組播拓?fù)洳?shí)現(xiàn)組播轉(zhuǎn)發(fā)控制。第2章描述總體思路，包括參考模型及設(shè)計(jì)約束條件；第3章描述具體實(shí)現(xiàn)流程，主要是基于OpenFlow及LLDP協(xié)議實(shí)現(xiàn)組播拓?fù)涫占?；?章就組播路徑算法進(jìn)行應(yīng)用舉例；第5章對(duì)方案進(jìn)行分析；最后是結(jié)束語(yǔ)。

2 總體思路

2.1參考模型及架構(gòu)設(shè)計(jì)

SDN的應(yīng)用案例最為經(jīng)典的是Google的B4網(wǎng)絡(luò)［3］。Google發(fā)現(xiàn)其全球數(shù)據(jù)中心之間的鏈路帶寬利用率較低，而且利用現(xiàn)有商業(yè)產(chǎn)品難以滿(mǎn)足其接近100%鏈路利用率的需求，因此采用了SDN設(shè)計(jì)思路對(duì)數(shù)據(jù)中心之間的通信系統(tǒng)進(jìn)行改造，稱(chēng)為B4網(wǎng)絡(luò)。如圖1所示，B4網(wǎng)絡(luò)中設(shè)計(jì)了集中的流量工程服務(wù)器，能夠利用整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔⒑蛠?lái)自應(yīng)用的流量需求計(jì)算出一組接近全網(wǎng)最優(yōu)的數(shù)據(jù)轉(zhuǎn)發(fā)規(guī)則，并將轉(zhuǎn)發(fā)規(guī)則下發(fā)到數(shù)據(jù)中心對(duì)外通信路由器中。重新設(shè)計(jì)的對(duì)外通信路由器接受流量工程服務(wù)器下發(fā)的路由轉(zhuǎn)發(fā)策略進(jìn)行業(yè)務(wù)轉(zhuǎn)發(fā)，實(shí)現(xiàn)基于業(yè)務(wù)的隧道（Tunnel）選取和流量量化分?jǐn)偂?/p>

圖1 B4流量工程系統(tǒng)的軟件架構(gòu)圖

基于該思路可同樣設(shè)計(jì)對(duì)應(yīng)的組播路徑計(jì)算服務(wù)器來(lái)實(shí)現(xiàn)組播功能。具體參考架構(gòu)如圖2所示。本方案目前不考慮獨(dú)立的路由器和控制器間帶外信道，故參考模型較之圖1的實(shí)現(xiàn)更簡(jiǎn)化，SDN控制器只需和單一路由器互連即可。

圖2 組播路徑計(jì)算軟件架構(gòu)

在圖2中，SDN控制器能夠通過(guò)標(biāo)準(zhǔn)協(xié)議獲取廣域網(wǎng)的三層網(wǎng)絡(luò)拓?fù)洌⒛軌蚋鶕?jù)組播請(qǐng)求獲取組播組成員。基于拓?fù)渚S護(hù)模塊形成的網(wǎng)絡(luò)拓?fù)浼敖M播組成員分布，控制器采用組播樹(shù)生成算法形成組播轉(zhuǎn)發(fā)樹(shù)，并為網(wǎng)絡(luò)中的路由器形成組播轉(zhuǎn)發(fā)規(guī)則，由SDN控制器將轉(zhuǎn)發(fā)規(guī)則下發(fā)到路由器中，從而實(shí)現(xiàn)組播業(yè)務(wù)。

2.2設(shè)計(jì)約束

基于SDN控制思想，需要滿(mǎn)足如下條件才能在實(shí)際網(wǎng)絡(luò)中應(yīng)用：

（1）路由交換設(shè)備支持標(biāo)準(zhǔn)OpenFLow規(guī)范。隨著SDN技術(shù)的發(fā)展，目前各路由器廠商已經(jīng)逐步支持OpenFlow規(guī)范標(biāo)準(zhǔn)并實(shí)現(xiàn)了Hybrid混合路由器，本方案僅需路由器支持標(biāo)準(zhǔn)規(guī)范而無(wú)需特殊擴(kuò)展［4］。

（2）廣域網(wǎng)三層IP組網(wǎng)基于標(biāo)準(zhǔn)商業(yè)路由協(xié)議，如OSPF、IS-IS或EIGRP路由協(xié)議，路由協(xié)議產(chǎn)生的路由表作為基本的三層轉(zhuǎn)發(fā)規(guī)則，控制器借此帶內(nèi)信道和各個(gè)路由器進(jìn)行連接。

3 基于OpenFlow實(shí)現(xiàn)SDN控制

3.1拓?fù)湫畔@取

3.1.1 基本拓?fù)浍@取

目前較為通用的網(wǎng)絡(luò)拓?fù)浍@取方式是基于SNMP協(xié)議，查詢(xún)網(wǎng)絡(luò)中路由器的路由表信息和接口信息，再對(duì)收集信息進(jìn)行分析實(shí)現(xiàn)。該方法需在控制器中引入SNMP服務(wù)器，并且如果網(wǎng)絡(luò)容量較大，信息傳遞和處理的開(kāi)銷(xiāo)均較大。

在SDN控制器上實(shí)現(xiàn)LLDP協(xié)議功能（Link Layer Discovery Protocol，鏈路層發(fā)現(xiàn)協(xié)議）［5］能夠?qū)崿F(xiàn)拓?fù)浒l(fā)現(xiàn)，簡(jiǎn)單且擴(kuò)展性強(qiáng)。目前OpenDaylight開(kāi)源SDN控制器已經(jīng)應(yīng)用LLDP協(xié)議實(shí)現(xiàn)對(duì)應(yīng)功能［6］。

如圖3所示，路由器相互組網(wǎng)并且和SDN控制器建立OpenFlow控制連接，過(guò)程符合OpenFlow規(guī)范定義［7］。當(dāng)SDN控制器和每臺(tái)路由器建立連接后，能夠識(shí)別并標(biāo)識(shí)每一臺(tái)被控設(shè)備。對(duì)于每一臺(tái)路由器，SDN控制器通過(guò)OFPT_FLOW_MOD消息下發(fā)基礎(chǔ)流表，其中包括支持LLDP協(xié)議的對(duì)應(yīng)規(guī)則：

接收識(shí)別LLDP協(xié)議，并將該報(bào)文以Packet-In轉(zhuǎn)發(fā)到控制器；（規(guī)則1）

在WAN網(wǎng)絡(luò)中，SDN控制器和所有設(shè)備沒(méi)有帶外連接，將不具備流表處理的報(bào)文轉(zhuǎn)發(fā)給控制器會(huì)嚴(yán)重影響整個(gè)網(wǎng)絡(luò)的性能，所以建議路由器將不能識(shí)別的報(bào)文進(jìn)行丟棄，僅匹配流表的報(bào)文才進(jìn)行對(duì)應(yīng)處理。

圖3 LLDP實(shí)現(xiàn)

拓?fù)渚S護(hù)模塊實(shí)現(xiàn)LLDP協(xié)議，完成網(wǎng)絡(luò)拓?fù)涞陌l(fā)現(xiàn)。SDN控制器針對(duì)每一個(gè)路由器發(fā)送單獨(dú)的Packet-Out格式報(bào)文，該報(bào)文中包含LLDP協(xié)議，并在ofp_action_header中指示路由器需將該LLDP報(bào)文轉(zhuǎn)發(fā)到所有活動(dòng)接口。

當(dāng)路由器的鄰居接收到LLDP報(bào)文時(shí)，因?yàn)榫邆渖衔拿枋龅囊?guī)則1，就會(huì)將接收的LLDP協(xié)議報(bào)文通過(guò)Packet_In發(fā)送給控制器。控制器收到Packet_ In消息后對(duì)數(shù)據(jù)包進(jìn)行分析，創(chuàng)建對(duì)應(yīng)路由器的連接記錄。網(wǎng)絡(luò)中所有路由器均基于該機(jī)制進(jìn)行LLDP協(xié)議處理，SDN控制器將能夠創(chuàng)建出完備的網(wǎng)絡(luò)拓?fù)洹?/p>

3.1.2 拓?fù)鋭?dòng)態(tài)維護(hù)

在SDN解決方案中，依靠如下方式實(shí)現(xiàn)拓?fù)鋭?dòng)態(tài)維護(hù)：

（1）SDN控制器的拓?fù)浒l(fā)現(xiàn)模塊定時(shí)進(jìn)行LLDP協(xié)議更新，以刷新完整的網(wǎng)絡(luò)拓?fù)洌?/p>

（2）基于OpenFlow協(xié)議，當(dāng)接口狀態(tài)變化時(shí)，路由器會(huì)通過(guò)ofp_port_status消息主動(dòng)向SDN控制器發(fā)送通告，控制器根據(jù)接口狀態(tài)消息能夠動(dòng)態(tài)維護(hù)網(wǎng)絡(luò)拓?fù)洌?/p>

（3）SDN控制器本身具備和路由器的TCP連接，該信息也可輔助判斷路由器是否脫網(wǎng)。

3.2組播成員獲取

組播成員獲取基于SDN控制器對(duì)路由器下發(fā)的OpenFlow流表規(guī)則：

接收識(shí)別IGMP協(xié)議報(bào)文，并將該報(bào)文以Packet-In轉(zhuǎn)發(fā)到控制器；（規(guī)則2）

當(dāng)終端主機(jī)加入某一組播組時(shí)，主機(jī)會(huì)定時(shí)發(fā)送IGMP協(xié)議報(bào)文。路由器能夠基于規(guī)則2識(shí)別IGMP報(bào)文，并將報(bào)文轉(zhuǎn)發(fā)到控制器，由控制器統(tǒng)一記錄組播組成員。

路由器本身并不需要處理不同IGMP協(xié)議版本，僅需識(shí)別IGMP協(xié)議并轉(zhuǎn)發(fā)，由控制器進(jìn)行不同協(xié)議版本的統(tǒng)一處理，故本方案能夠支持IGMPv1/2/3。當(dāng)加入組播的主機(jī)移除或關(guān)機(jī)，SDN控制器能夠通過(guò)IGMP定時(shí)匯報(bào)機(jī)制確定主機(jī)移除。

3.3組播源獲取

組播源的獲取可以采用多種方法，固定組播業(yè)務(wù)的源可在控制器上手工配置；臨時(shí)性組播業(yè)務(wù)的源可基于SDN控制器對(duì)路由器下發(fā)的OpenFlow流表規(guī)則：

接收識(shí)別組播業(yè)務(wù)報(bào)文，無(wú)組播流表時(shí)將該報(bào)文以Packet-In轉(zhuǎn)發(fā)到控制器；（規(guī)則3）

當(dāng)某一主機(jī)開(kāi)始發(fā)送組播業(yè)務(wù)數(shù)據(jù)時(shí)，直連路由器接收此報(bào)文后首先匹配組播轉(zhuǎn)發(fā)表。如果匹配成功，組播數(shù)據(jù)會(huì)被轉(zhuǎn)發(fā)；如果匹配失敗，路由器將基于規(guī)則3把報(bào)文發(fā)送到控制器上，由控制器根據(jù)〈數(shù)據(jù)源、數(shù)據(jù)目的、業(yè)務(wù)類(lèi)型〉確定組播樹(shù)的源?；诖艘?guī)則，控制器將獲取網(wǎng)絡(luò)中所有的組播活動(dòng)源節(jié)點(diǎn)和申請(qǐng)的組播業(yè)務(wù)類(lèi)型。

3.4拓?fù)鋽?shù)據(jù)庫(kù)

拓?fù)鋽?shù)據(jù)庫(kù)是控制器形成組播轉(zhuǎn)發(fā)表的唯一數(shù)據(jù)來(lái)源，通過(guò)拓?fù)浍@取、組播成員和組播源的獲取，將為組播轉(zhuǎn)發(fā)表的生成形成統(tǒng)一的數(shù)據(jù)庫(kù)支持。每個(gè)路由器在組播轉(zhuǎn)發(fā)的位置不同，控制器將為每個(gè)路由器生成獨(dú)立的組播轉(zhuǎn)發(fā)表。

拓?fù)湫畔⒌母?、組播成員的加入和離開(kāi)、組播源的配置、刪除和臨時(shí)加入都將導(dǎo)致拓?fù)鋽?shù)據(jù)庫(kù)的變化，也同時(shí)導(dǎo)致組播樹(shù)的重新計(jì)算。

拓?fù)鋽?shù)據(jù)庫(kù)描述整個(gè)網(wǎng)絡(luò)的連接情況和組播數(shù)據(jù)的發(fā)送和接收需求，表述形式以路由器ID作為索引，每一表項(xiàng)對(duì)應(yīng)一個(gè)路由器節(jié)點(diǎn)，具體內(nèi)容包括路由器ID、路由器所有接口、接口連接的對(duì)端路由器ID/接口名/IP地址、接口連接的組播數(shù)據(jù)源/組播地址、接口連接PC需要接收的組播地址等，如表1所示。

表1 組播拓?fù)鋽?shù)據(jù)庫(kù)形式

4 組播路徑計(jì)算實(shí)現(xiàn)

4.1組播算法選擇和使用

（1）組播算法選擇

當(dāng)前，組播樹(shù)計(jì)算的常用方法包括最短路徑樹(shù)、Steiner樹(shù)和低代價(jià)最短路徑樹(shù)三種。

2001-2012年海南省國(guó)際旅游外匯收入除2003年和2009年下降外，總體呈波動(dòng)上升趨勢(shì)。期間，2003年受亞洲“非典”公共危機(jī)事件影響，2008-2009年受全球金融危機(jī)影響出現(xiàn)下滑。其國(guó)際旅游外匯收入從2001年的1.06億美元上升到2012年的3.48億美元。12年間的平均國(guó)際旅游外匯收入為2.21億美元，約占全國(guó)的0.65%，排名在二十一位名上下波動(dòng)。2001-2012年海南省國(guó)際旅游外匯收入一直低于全國(guó)平均值，差距越來(lái)越大。

·最短路徑樹(shù)（shortest path tree，簡(jiǎn)稱(chēng)SPT）的優(yōu)點(diǎn)是它使得源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的時(shí)延最??；

·Steiner樹(shù)的優(yōu)點(diǎn)是使得網(wǎng)絡(luò)連接的總消耗最小，最大限度地共享帶寬，如果網(wǎng)絡(luò)中除源節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)都是目的節(jié)點(diǎn)，這棵樹(shù)就是最小生成樹(shù)（minimum spanning tree，簡(jiǎn)稱(chēng)MST）［8］；

·在復(fù)雜網(wǎng)絡(luò)中SPT可能不是唯一的，在眾多的SPT中網(wǎng)絡(luò)連接的總消耗最小的SPT樹(shù)就是低代價(jià)最短路徑樹(shù)（LCSPT），它的優(yōu)點(diǎn)是保證源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的時(shí)延最小，同時(shí)盡可能減少網(wǎng)絡(luò)連接的總消耗。

各種組播樹(shù)的示例，如圖4所示。

圖4 各種組播樹(shù)

基于傳統(tǒng)路由協(xié)議方式，網(wǎng)絡(luò)中所有路由器的協(xié)議算法必須一致，固定選擇一種算法。但是在本方案中，不同的組播組可以靈活選擇不同的組播樹(shù)算法。例如，針對(duì)視頻組播應(yīng)用，可以選擇SPT算法，使得業(yè)務(wù)時(shí)延最小；針對(duì)文件傳輸共享，則考慮消耗最小帶寬，選擇Steiner算法，應(yīng)用場(chǎng)景如圖5所示。

（2）組播樹(shù)計(jì)算觸發(fā)規(guī)則

對(duì)于組播樹(shù)（S，G）路由表項(xiàng)，需要確定組播數(shù)據(jù)源，從而啟動(dòng)對(duì)應(yīng)的組播樹(shù)算法進(jìn)行計(jì)算?；赟DN解決方案，組播樹(shù)觸發(fā)規(guī)則具備非常大的靈活性，可以基于多種規(guī)則來(lái)實(shí)現(xiàn)，同樣不同組播組可采用不同的觸發(fā)規(guī)則：

·對(duì)于已知組播源應(yīng)用：可以直接在控制器上通過(guò)配置方式直接指定組播源，當(dāng)控制器接收到IGMP報(bào)文后，源和組地址都具備，可以立刻觸發(fā)計(jì)算組播樹(shù)；

·對(duì)于未知組播源應(yīng)用：則可以考慮采用組播業(yè)務(wù)觸發(fā)機(jī)制。控制器預(yù)先向路由器下發(fā)一條流表（見(jiàn)3.3節(jié)），使得路由器將該組播組的組播業(yè)務(wù)通過(guò)Packet-In轉(zhuǎn)發(fā)到控制器上。當(dāng)控制器接收到組播業(yè)務(wù)后（假定此時(shí)已接收IGMP），源和組地址都具備，就能夠觸發(fā)組播樹(shù)計(jì)算，再將對(duì)應(yīng)（S，G）表項(xiàng)下發(fā)到相關(guān)路由器。此種方式的缺點(diǎn)是組播業(yè)務(wù)的響應(yīng)時(shí)間會(huì)相對(duì)較長(zhǎng)。如果組播應(yīng)用能夠先發(fā)送一定數(shù)量的啟動(dòng)報(bào)文，也能取得較好的效果；

·網(wǎng)絡(luò)拓?fù)渥兓涸谏鲜龌A(chǔ)上，當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，組播樹(shù)需要重新計(jì)算，以適應(yīng)動(dòng)態(tài)的網(wǎng)絡(luò)變化。

圖5 不同組播組可選擇不同組播樹(shù)算法

（3）組播樹(shù)的撤銷(xiāo)

路由器上的組播流表存在生命周期，因此控制器還需判斷何時(shí)停止對(duì)組播樹(shù)的更新計(jì)算。

·對(duì)于靜態(tài)配置觸發(fā)的，可以通過(guò)組播成員的配置取消來(lái)停止；

·對(duì)于動(dòng)態(tài)業(yè)務(wù)觸發(fā)的，可以由控制器獲取OpenFlow統(tǒng)計(jì)數(shù)據(jù)來(lái)判斷是否還有組播業(yè)務(wù)，從而停止對(duì)應(yīng)的更新計(jì)算。

4.2組播樹(shù)算法舉例

為研究SDN組播控制的可行性，選取快速低代價(jià)最短路徑樹(shù)（Fast Low-Cost Shortest Path Tree）算法［8］進(jìn)行驗(yàn)證。

FLSPT算法采用Dijkstra算法路徑遞增的基本思想，并結(jié)合DDMC算法［9］目的節(jié)點(diǎn)共享路徑的方法，通過(guò)用Dist向量保存節(jié)點(diǎn)到已計(jì)算目的節(jié)點(diǎn)的最近距離，在有多條最短路徑時(shí)總是選擇能夠使Dist向量值最小的路徑，最大限度地與其他目的節(jié)點(diǎn)共享路徑，因而能夠降低最短路徑樹(shù)的總消耗，適合計(jì)算目的節(jié)點(diǎn)較多的組播樹(shù)。算法基本思路如下：

給定圖G =（Y，E），節(jié)點(diǎn)s為組播源節(jié)點(diǎn)，目的節(jié)點(diǎn)集合為D，構(gòu)造以s為根節(jié)點(diǎn)且包含所有目的節(jié)點(diǎn)的最短路徑樹(shù)T。假定對(duì)于任意存在的邊（u，w），其權(quán)值為C（u，W）〉0。

引進(jìn)3個(gè)向量Dist，Mist和Parent。Dist［u］表示當(dāng)前搜索到的從源節(jié)點(diǎn)s到節(jié)點(diǎn)u的最短路徑長(zhǎng)度；Parent［u］表示在FLSPT算法所選擇的最短路徑上節(jié)點(diǎn)u的前一個(gè)節(jié)點(diǎn)，也就是最短路徑生成樹(shù)T上節(jié)點(diǎn)u的父節(jié)點(diǎn)；Mist［u］表示生成樹(shù)T上計(jì)算過(guò)的目的節(jié)點(diǎn)到節(jié)點(diǎn)u的最短距離。設(shè)ADJ（u）表示節(jié)點(diǎn)u的鄰接節(jié)點(diǎn)集，Q為一個(gè)待發(fā)展節(jié)點(diǎn)的序列，存儲(chǔ)已被訪(fǎng)問(wèn)但尚未被添加到生成樹(shù)T上的節(jié)點(diǎn)。

算法偽碼如下所示：

FLSPT算法

FLSPT Algorithm（G，s，D）

Init tree T with source node s and clear Q；

For all w∈V Do //算法初始化

If w∈ADJ（s）Then

Dist［w］←C（s，w）；Mist［w］←C（s，w）；Parent ［w］←s；

Q←Q∪｛w｝；

Else

Dist［w］←∞；Mist［w］←∞；Parent［w］←nil；

End If

End For

Dist［s］←0；Mist［s］←0；Parent［s］←nil；//源節(jié)點(diǎn)為第一個(gè)計(jì)算節(jié)點(diǎn)

while there exists a node in D that has not been added to tree T Do Select node u from Q while statisfies Dist［u］= min｛Dist［m］|m∈Q｝；

If u is a destination node Then //如果是目的節(jié)點(diǎn)則將最短路徑添加到T

Establish shortest path from source node s to node u；

Mist［u］←0；//如果是目的節(jié)點(diǎn)則需要將Mist向量清0

End If

For all w∈ADJ（u）Do

If Dist［w］=∞Then Q←Q∪｛w｝End If

If Dist［u］+ C（u，w）〈Dist［w］Then //調(diào)整節(jié)點(diǎn)的可達(dá)最短路徑長(zhǎng)度

Dist［w］←Dist［u］+ C（u，w）；Mist［w］←Mist ［u］+ C（u，w）；Parent［w］←u；

Else If Dist［u］+ C（u，w）= Dist［w］Then //最短路徑不唯一

If Mist［u］+ C（u，w）〈Mist［w］Then //發(fā)現(xiàn)更優(yōu)的父節(jié)點(diǎn)

Mist［w］←Mist［u］+ C（u，w）；Parent［w］←u；//記錄最優(yōu)父節(jié)點(diǎn)

End If

End If

End For

End While算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為：

T = T1 + T2 = O（n）+ O（nlogn + e）= O（n + nlogn + e）= O（nlogn + e）。

S = O（e + n）+4O（n）= O（e +5n）= O（e + n）。

5 對(duì)比分析

（1）報(bào)文開(kāi)銷(xiāo)分析

最流行的域內(nèi)多播路由協(xié)議包括：DVMRP、PIM-SM、PIM-DM，以使用最多的PIM-SM來(lái)分析多播路由協(xié)議和SDN組播實(shí)現(xiàn)的報(bào)文開(kāi)銷(xiāo)。

從表2可以看出，只要控制器下發(fā)的組播流表開(kāi)銷(xiāo)不大于PIM-SM的加入/離開(kāi)消息，那么SDN實(shí)現(xiàn)方式將小于PIM-SM的報(bào)文開(kāi)銷(xiāo)。

表2 PIM-SM和SDN組播實(shí)現(xiàn)的報(bào)文開(kāi)銷(xiāo)比較

（2）協(xié)議方式分析比較

表3提供了SDN組播實(shí)現(xiàn)方式和傳統(tǒng)組播路由協(xié)議的比較。

表3 SDN方式和傳統(tǒng)組播路由協(xié)議方式比較

6 結(jié)束語(yǔ)

SDN/OpenFlow技術(shù)為網(wǎng)絡(luò)控制帶來(lái)了巨大的靈活性。基于SDN的組播應(yīng)用解決方案，利用了SDN控制的思路，通過(guò)控制器的靈活編程和部署來(lái)控制路由器組播轉(zhuǎn)發(fā)行為。路由器僅需支持標(biāo)準(zhǔn)的OpenFlow協(xié)議，而無(wú)需其他擴(kuò)展?；诒痉桨福n題組下一步會(huì)對(duì)組播路由算法進(jìn)行豐富和改進(jìn)，并結(jié)合SDN流量工程服務(wù)以實(shí)現(xiàn)具備QoS保證的組播路徑選擇。

參考文獻(xiàn)：

［1］N McKeown，T Anderson，H Balakrishnan，et al.Openflow：enabling innovationin campus networks［J］.ACM SIGCOMM Computer Commun.Review，2008，38（2）：69-74.

［2］Open Networking Foundation.Software-Defined Networking：The New Norm for Networks White Paper［EB/OL］.2012.https：//www.opennetworking.org/images/stories/downloads/white-papers/wp-sdn-newnorm.pdf.

［3］Sushant Jain，Alok Kumar，Subhasree Mandal，et al.B4：Experience with a globally-deployedsoftware defined wan ［C］.In Proc.ACM SIGCOMM 2013 conf.on SIGCOMM，ACM，2013：3-14.

［4］張衛(wèi)峰.深度解析SDN-利益、戰(zhàn)略、技術(shù)、實(shí)踐［M］.北京：電子工業(yè)出版社，2014.Zhang Weifeng.SDN-Interest，Strategy，Technology and Practice［M］.Beijing：Publishing House of Electronics Industry（PHEI），2014.

［5］LAN/MAN Standards Committee of the IEEE Computer Society.Station and Media Access Control Connectivity Discovery IEEE std 802.1ABTM-2009［S］.IEEE，2009.

［6］OpenDaylight Project.OpenDaylight wiki［EB/OL］.2014.https：//wiki.opendaylight.org/view.

［7］Open Networking Foundation.Open Flow Switch Specification V1.3.2［S］.ONF，2013.

［8］WANG Tao，Li Wei-Shen.A Fast Low-Cost Shortest Path Tree Algorithm［J］.Journal of Software，2004，15 （5）：660-665.

［9］Shaikh A，Shin KG.Destination-driven routing for low-cost multicast［J］.IEEE Joural on Selected Areas in Communications，1991，5（3）：373-381.

·微機(jī)軟件·

Multicast Service Based on SDN

Chen Liang，Qu Hui
（Chongqing Jinmei Communication Co.，Ltd.，Chongqing 400030，China）

Abstract：Software Define Network（SDN）separates network control plane from data plane，uses standard southbound interface protocol to control the packet forwarder behave，and realizes network customized and extended.In order to avoid complexity of traditional multicast route protocol and inconsistency of different vendors，the SDN multicast network service is designed to implement multicast function.It uses OpenFlow protocol to control routers in WAN，Link Layer Discovery Protocol（LLDP）and ICMP protocol to get network topology and multicast topology，and choices Low-cost shortest path tree algorithm or others，according to different type of service，to calculate multicast forward path，finally downloads forward rules to router.The method，compared with multicast route protocol，is verified that it is expansibility and flexible for implementation and deployment.

Key words：Software Define Network；OpenFlow protocol；Link Layer Discovery Protocol；Low-cost shortest path tree；Multicast；Expansibility

DOI：10.3969/j.issn.1002-2279.2016.02.010

中圖分類(lèi)號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-2279（2016）02-0031-06

作者簡(jiǎn)介：陳量（1974-），男，湖北省武昌市人，高級(jí)工程師，主研方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，路由算法設(shè)計(jì)與分析。

收稿日期：2015-04-21