陈 量，瞿 辉（重庆金美通信有限责任公司，重庆　400030）



基于SDN思路的组播实现

陈 量，瞿 辉
（重庆金美通信有限责任公司，重庆400030）

摘 要：软件定义网络SDN的思想是将网络控制平面和数据转发平面分离，采用标准化南向接口协议，集中的控制路由交换设备的转发行为，实现网络可定制和可扩展。为避免传统组播路由协议的复杂性和各设备厂商协议实现的不一致性，基于SDN思想在控制平面设计组播网络服务，实现网络组播业务功能。组播网络服务通过标准OpenFlow协议和广域网中的路由器建立控制连接，下发对应网络控制规则，基于链路发现协议LLDP和标准ICMP协议获取网络拓扑和组播组拓扑，建立组播树；在此基础上，再基于组播组业务特性选取最短路径树、低代价最短路径树等路径计算算法，计算组播转发路径并下发到路由器中实现组播业务转发。该方法经过设计验证，并和传统组播路由协议对比分析，具备强大的扩展性和灵活性，实现简单，易于部署。

关键词：软件定义网络；OpenFlow协议；链路发现协议；低代价最短路径树；组播；扩展性

1 引 言

SDN（软件定义网络）作为一种革命性的网络新技术，已逐步得到推广应用。基于控制和转发分离的思想，将原有网络设备交互实现的复杂协议转换为灵活的、可编程的软件化网络服务，能够提供更加统一的网络控制手段［1-2］。

在当前广域网组网应用中，传统的PIM、DVMRP等组播路由协议应用并不广泛，受限于每一跳网络设备均需支持组播路由协议，组播业务需克服较大的协议开销和不同厂商可能存在的协议实现不一致等问题。为规避上述问题，部分应用参考P2P技术，采用了应用层组播技术，该机制不依赖于第3层组播路由协议，但在网络传输效率上不如IP层组播，需要功能强大的服务器进行支撑。

基于SDN思想构建网络，能够为实现广域网组播业务提供一个新的技术思路。目前较为流行的SDN控制器，能够提供网络拓扑呈现、路由计算、流量工程等基本网络控制服务，并基于标准的南向接口协议对路由器进行控制。由此，SDN控制器也能够在动态获取组播成员网络拓扑的基础上，结合组播路径树算法，为每一个路由器生成组播转发规则，并通过标准协议进行下发，从而实现IP层高效的组播业务转发。该方式能够降低组播路由协议的开销，避免不同厂商设备协议实现的不一致性，并能够灵活部署和升级。

针对SDN网络，结合路由器OpenFlow协议特性和组播树路径计算算法，使用SDN控制器获取组播拓扑并实现组播转发控制。第2章描述总体思路，包括参考模型及设计约束条件；第3章描述具体实现流程，主要是基于OpenFlow及LLDP协议实现组播拓扑收集；第4章就组播路径算法进行应用举例；第5章对方案进行分析；最后是结束语。

2 总体思路

2.1参考模型及架构设计

SDN的应用案例最为经典的是Google的B4网络［3］。Google发现其全球数据中心之间的链路带宽利用率较低，而且利用现有商业产品难以满足其接近100%链路利用率的需求，因此采用了SDN设计思路对数据中心之间的通信系统进行改造，称为B4网络。如图1所示，B4网络中设计了集中的流量工程服务器，能够利用整个网络的拓扑信息和来自应用的流量需求计算出一组接近全网最优的数据转发规则，并将转发规则下发到数据中心对外通信路由器中。重新设计的对外通信路由器接受流量工程服务器下发的路由转发策略进行业务转发，实现基于业务的隧道（Tunnel）选取和流量量化分摊。

图1 B4流量工程系统的软件架构图

基于该思路可同样设计对应的组播路径计算服务器来实现组播功能。具体参考架构如图2所示。本方案目前不考虑独立的路由器和控制器间带外信道，故参考模型较之图1的实现更简化，SDN控制器只需和单一路由器互连即可。

图2 组播路径计算软件架构

在图2中，SDN控制器能够通过标准协议获取广域网的三层网络拓扑，并能够根据组播请求获取组播组成员。基于拓扑维护模块形成的网络拓扑及组播组成员分布，控制器采用组播树生成算法形成组播转发树，并为网络中的路由器形成组播转发规则，由SDN控制器将转发规则下发到路由器中，从而实现组播业务。

2.2设计约束

基于SDN控制思想，需要满足如下条件才能在实际网络中应用：

（1）路由交换设备支持标准OpenFLow规范。随着SDN技术的发展，目前各路由器厂商已经逐步支持OpenFlow规范标准并实现了Hybrid混合路由器，本方案仅需路由器支持标准规范而无需特殊扩展［4］。

（2）广域网三层IP组网基于标准商业路由协议，如OSPF、IS-IS或EIGRP路由协议，路由协议产生的路由表作为基本的三层转发规则，控制器借此带内信道和各个路由器进行连接。

3 基于OpenFlow实现SDN控制

3.1拓扑信息获取

3.1.1 基本拓扑获取

目前较为通用的网络拓扑获取方式是基于SNMP协议，查询网络中路由器的路由表信息和接口信息，再对收集信息进行分析实现。该方法需在控制器中引入SNMP服务器，并且如果网络容量较大，信息传递和处理的开销均较大。

在SDN控制器上实现LLDP协议功能（Link Layer Discovery Protocol，链路层发现协议）［5］能够实现拓扑发现，简单且扩展性强。目前OpenDaylight开源SDN控制器已经应用LLDP协议实现对应功能［6］。

如图3所示，路由器相互组网并且和SDN控制器建立OpenFlow控制连接，过程符合OpenFlow规范定义［7］。当SDN控制器和每台路由器建立连接后，能够识别并标识每一台被控设备。对于每一台路由器，SDN控制器通过OFPT_FLOW_MOD消息下发基础流表，其中包括支持LLDP协议的对应规则：

接收识别LLDP协议，并将该报文以Packet-In转发到控制器；（规则1）

在WAN网络中，SDN控制器和所有设备没有带外连接，将不具备流表处理的报文转发给控制器会严重影响整个网络的性能，所以建议路由器将不能识别的报文进行丢弃，仅匹配流表的报文才进行对应处理。

图3 LLDP实现

拓扑维护模块实现LLDP协议，完成网络拓扑的发现。SDN控制器针对每一个路由器发送单独的Packet-Out格式报文，该报文中包含LLDP协议，并在ofp_action_header中指示路由器需将该LLDP报文转发到所有活动接口。

当路由器的邻居接收到LLDP报文时，因为具备上文描述的规则1，就会将接收的LLDP协议报文通过Packet_In发送给控制器。控制器收到Packet_ In消息后对数据包进行分析，创建对应路由器的连接记录。网络中所有路由器均基于该机制进行LLDP协议处理，SDN控制器将能够创建出完备的网络拓扑。

3.1.2 拓扑动态维护

在SDN解决方案中，依靠如下方式实现拓扑动态维护：

（1）SDN控制器的拓扑发现模块定时进行LLDP协议更新，以刷新完整的网络拓扑；

（2）基于OpenFlow协议，当接口状态变化时，路由器会通过ofp_port_status消息主动向SDN控制器发送通告，控制器根据接口状态消息能够动态维护网络拓扑；

（3）SDN控制器本身具备和路由器的TCP连接，该信息也可辅助判断路由器是否脱网。

3.2组播成员获取

组播成员获取基于SDN控制器对路由器下发的OpenFlow流表规则：

接收识别IGMP协议报文，并将该报文以Packet-In转发到控制器；（规则2）

当终端主机加入某一组播组时，主机会定时发送IGMP协议报文。路由器能够基于规则2识别IGMP报文，并将报文转发到控制器，由控制器统一记录组播组成员。

路由器本身并不需要处理不同IGMP协议版本，仅需识别IGMP协议并转发，由控制器进行不同协议版本的统一处理，故本方案能够支持IGMPv1/2/3。当加入组播的主机移除或关机，SDN控制器能够通过IGMP定时汇报机制确定主机移除。

3.3组播源获取

组播源的获取可以采用多种方法，固定组播业务的源可在控制器上手工配置；临时性组播业务的源可基于SDN控制器对路由器下发的OpenFlow流表规则：

接收识别组播业务报文，无组播流表时将该报文以Packet-In转发到控制器；（规则3）

当某一主机开始发送组播业务数据时，直连路由器接收此报文后首先匹配组播转发表。如果匹配成功，组播数据会被转发；如果匹配失败，路由器将基于规则3把报文发送到控制器上，由控制器根据〈数据源、数据目的、业务类型〉确定组播树的源。基于此规则，控制器将获取网络中所有的组播活动源节点和申请的组播业务类型。

3.4拓扑数据库

拓扑数据库是控制器形成组播转发表的唯一数据来源，通过拓扑获取、组播成员和组播源的获取，将为组播转发表的生成形成统一的数据库支持。每个路由器在组播转发的位置不同，控制器将为每个路由器生成独立的组播转发表。

拓扑信息的更新、组播成员的加入和离开、组播源的配置、删除和临时加入都将导致拓扑数据库的变化，也同时导致组播树的重新计算。

拓扑数据库描述整个网络的连接情况和组播数据的发送和接收需求，表述形式以路由器ID作为索引，每一表项对应一个路由器节点，具体内容包括路由器ID、路由器所有接口、接口连接的对端路由器ID/接口名/IP地址、接口连接的组播数据源/组播地址、接口连接PC需要接收的组播地址等，如表1所示。

表1 组播拓扑数据库形式

4 组播路径计算实现

4.1组播算法选择和使用

（1）组播算法选择

当前，组播树计算的常用方法包括最短路径树、Steiner树和低代价最短路径树三种。

2001-2012年海南省国际旅游外汇收入除2003年和2009年下降外，总体呈波动上升趋势。期间，2003年受亚洲“非典”公共危机事件影响，2008-2009年受全球金融危机影响出现下滑。其国际旅游外汇收入从2001年的1.06亿美元上升到2012年的3.48亿美元。12年间的平均国际旅游外汇收入为2.21亿美元，约占全国的0.65%，排名在二十一位名上下波动。2001-2012年海南省国际旅游外汇收入一直低于全国平均值，差距越来越大。

·最短路径树（shortest path tree，简称SPT）的优点是它使得源节点到每个目的节点的时延最小；

·Steiner树的优点是使得网络连接的总消耗最小，最大限度地共享带宽，如果网络中除源节点外的每个节点都是目的节点，这棵树就是最小生成树（minimum spanning tree，简称MST）［8］；

·在复杂网络中SPT可能不是唯一的，在众多的SPT中网络连接的总消耗最小的SPT树就是低代价最短路径树（LCSPT），它的优点是保证源节点到每个目的节点的时延最小，同时尽可能减少网络连接的总消耗。

各种组播树的示例，如图4所示。

图4 各种组播树

基于传统路由协议方式，网络中所有路由器的协议算法必须一致，固定选择一种算法。但是在本方案中，不同的组播组可以灵活选择不同的组播树算法。例如，针对视频组播应用，可以选择SPT算法，使得业务时延最小；针对文件传输共享，则考虑消耗最小带宽，选择Steiner算法，应用场景如图5所示。

（2）组播树计算触发规则

对于组播树（S，G）路由表项，需要确定组播数据源，从而启动对应的组播树算法进行计算。基于SDN解决方案，组播树触发规则具备非常大的灵活性，可以基于多种规则来实现，同样不同组播组可采用不同的触发规则：

·对于已知组播源应用：可以直接在控制器上通过配置方式直接指定组播源，当控制器接收到IGMP报文后，源和组地址都具备，可以立刻触发计算组播树；

·对于未知组播源应用：则可以考虑采用组播业务触发机制。控制器预先向路由器下发一条流表（见3.3节），使得路由器将该组播组的组播业务通过Packet-In转发到控制器上。当控制器接收到组播业务后（假定此时已接收IGMP），源和组地址都具备，就能够触发组播树计算，再将对应（S，G）表项下发到相关路由器。此种方式的缺点是组播业务的响应时间会相对较长。如果组播应用能够先发送一定数量的启动报文，也能取得较好的效果；

·网络拓扑变化：在上述基础上，当网络拓扑发生变化时，组播树需要重新计算，以适应动态的网络变化。

图5 不同组播组可选择不同组播树算法

（3）组播树的撤销

路由器上的组播流表存在生命周期，因此控制器还需判断何时停止对组播树的更新计算。

·对于静态配置触发的，可以通过组播成员的配置取消来停止；

·对于动态业务触发的，可以由控制器获取OpenFlow统计数据来判断是否还有组播业务，从而停止对应的更新计算。

4.2组播树算法举例

为研究SDN组播控制的可行性，选取快速低代价最短路径树（Fast Low-Cost Shortest Path Tree）算法［8］进行验证。

FLSPT算法采用Dijkstra算法路径递增的基本思想，并结合DDMC算法［9］目的节点共享路径的方法，通过用Dist向量保存节点到已计算目的节点的最近距离，在有多条最短路径时总是选择能够使Dist向量值最小的路径，最大限度地与其他目的节点共享路径，因而能够降低最短路径树的总消耗，适合计算目的节点较多的组播树。算法基本思路如下：

给定图G =（Y，E），节点s为组播源节点，目的节点集合为D，构造以s为根节点且包含所有目的节点的最短路径树T。假定对于任意存在的边（u，w），其权值为C（u，W）〉0。

引进3个向量Dist，Mist和Parent。Dist［u］表示当前搜索到的从源节点s到节点u的最短路径长度；Parent［u］表示在FLSPT算法所选择的最短路径上节点u的前一个节点，也就是最短路径生成树T上节点u的父节点；Mist［u］表示生成树T上计算过的目的节点到节点u的最短距离。设ADJ（u）表示节点u的邻接节点集，Q为一个待发展节点的序列，存储已被访问但尚未被添加到生成树T上的节点。

算法伪码如下所示：

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；//源节点为第一个计算节点

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 //如果是目的节点则将最短路径添加到T

Establish shortest path from source node s to node u；

Mist［u］←0；//如果是目的节点则需要将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 //调整节点的可达最短路径长度

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 //发现更优的父节点

Mist［w］←Mist［u］+ C（u，w）；Parent［w］←u；//记录最优父节点

End If

End If

End For

End While算法的时间复杂度和空间复杂度分别为：

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 对比分析

（1）报文开销分析

最流行的域内多播路由协议包括：DVMRP、PIM-SM、PIM-DM，以使用最多的PIM-SM来分析多播路由协议和SDN组播实现的报文开销。

从表2可以看出，只要控制器下发的组播流表开销不大于PIM-SM的加入/离开消息，那么SDN实现方式将小于PIM-SM的报文开销。

表2 PIM-SM和SDN组播实现的报文开销比较

（2）协议方式分析比较

表3提供了SDN组播实现方式和传统组播路由协议的比较。

表3 SDN方式和传统组播路由协议方式比较

6 结束语

SDN/OpenFlow技术为网络控制带来了巨大的灵活性。基于SDN的组播应用解决方案，利用了SDN控制的思路，通过控制器的灵活编程和部署来控制路由器组播转发行为。路由器仅需支持标准的OpenFlow协议，而无需其他扩展。基于本方案，课题组下一步会对组播路由算法进行丰富和改进，并结合SDN流量工程服务以实现具备QoS保证的组播路径选择。

参考文献：

［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］张卫峰.深度解析SDN-利益、战略、技术、实践［M］.北京：电子工业出版社，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.

·微机软件·

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

中图分类号：TP393

文献标识码：A

文章编号：1002-2279（2016）02-0031-06

作者简介：陈量（1974-），男，湖北省武昌市人，高级工程师，主研方向：计算机网络技术，路由算法设计与分析。

收稿日期：2015-04-21