这里，所谓OpenFlow网络指的是相互连接的一组OpenFlow交换机的集合，并且这些交换机全部置于一个OpenFlow Controller或一个OpenFlow Controller的集群的管理之下。OpenFlow网络的路由服务指的是单纯地将一个数据包(Packet)从一个主机(Host)送到另一个主机，而不是三层IP路由协议1:1的实现。而主机也即是路由的目的地，可以是物理服务器或虚拟机(VM, Virtual Machine)。按照SDN的数据平面和控制平面相分离的模式和集中式管理的系统结构，OpenFlow网络的路由完全是由OpenFlow Controller根据用户的路由策略(Policy)生成并安装到每个OpenFlow交换机的Flow Table和Group Table的Flow Entry和Group Entry的集合来定义的。因此，本文假设读者朋友对OpenFlow交换机和OpenFlow Controller的基本概念有所了解，可参考ONF(Open Network Foundation)给出的“OpenFlow Switch Specification”相关章节。本文的讨论也以此文献给出的定义作为基础。
总体思路
主机和OpenFlow网络的连接方式直接影响OpenFlow网络的路由设置，本文的讨论包括三种最一般的情况：第一，主机和OpenFlow网络的交换机的端口直接相连，这是最简单的情况；第二，主机通过二层网络接入OpenFlow网络；第三，主机途径多个IP子网最终通过路由器和OpenFlow网络相连，主机接入的网络以及中间经过的网络都是传统的IP网络，使用传统的路由协议，如OSPF或BGP。为了叙述的方便，第一种连接方式和第二种连接方式下的主机看做OpenFlow网络的内部主机，而第三种连接方式下的主机看做OpenFlow网络的外部主机。所谓“外部”，这是因为OpenFlow网络无法直接“感知”到主机的存在。如图1所示。主机A与边缘交换机(Edge Switch)ES1的端口3连接(第一种方式)，主机B通过二层链路网络(1.1.1.0/24)和边缘交换机ES2的端口2连接(第二种方式)，主机C连入外部的IP网络(3.3.3.0/24)，路由器R是OpenFlow内部主机和外部主机通信的中介(第三种方式)，和边缘交换机ES3的端口2连接。
实现OpenFlow路由服务总的思路是：获取主机的信息及其接入OpenFlow网络的信息，计算主机之间的路径，对于路径上的每个交换机,通过下发的OpenFlow消息，改变它的Flow Table和Group Table来定义其转发行为，最终实现主机到主机的路由和通信。这些基本上都是OpenFlow Controller或在它之上的网络应用的功能。下文的讨论将不加区分的统统视为OpenFlow Controller的功能。
主机和接入
为了实现主机之间的路由与通信，OpenFlow Controller必须首先获取主机的相关信息。对于OpenFlow网络的内部主机，需要获取的信息包括：主机的IP地址，接入OpenFlow网络的边缘交换机及端口，以及主机的MAC地址。除了人工静态配置之外，网络的Orchestration系统可提供主机的IP地址和接入到OpenFlow网络的交换机及其端口，网络的Orchestration系统管理服务器和虚拟机在网络上的部署。比如，在云计算的数据中心，网络管理员可以通过OpenStack这样的Orchestration系统为客户定制IP子网。这样，IP子网中每个主机的IP地址和相连接的交换机及其端口的数据通过OpenStack的插件传递给Controller。而主机的MAC地址就需借助于ARP来动态获取。例如，在图1中，假设有一个发往主机A的数据包，但不知道主机A的MAC地址。此时，Controller可通过packet_out消息令边缘交换机ES1向端口3发送一个ARP请求，交换机ES1接收到主机A的回复报文后，因为它的Flow Table中没有和ARP报文匹配的Flow Entry，所以，缺省地，ES1将这个ARP回复报文打包成packet_in消息，发送给OpenFlow Controller。OpenFlow Controller解析这个报文，即可得到主机A的MAC地址。
对于OpenFlow网络的外部主机，OpenFlow Controller必须知道：和OpenFlow网络直接相连的路由器的IP地址和MAC地址，连接路由器的OpenFlow网络的边缘交换机和端口，外部主机所在子网的IP地址(Prefix)和掩码。路由器的IP地址和MAC地址，以及接入OpenFlow网络的边缘交换机和端口可按照上文描述的方式得到。而获取外部主机的IP子网的地址和掩码的功能则是由虚拟路由器(Virtual Router)来完成的。如图1所示，主机C所在的子网的IP地址和掩码(3.3.3.0/24)经过传统的分布式IP路由系统最终传递给路由器R。通过In Band或Out Of Band的方式，R和虚拟路由器事先建立了会话，如BGP会话，并交换路由可达信息。于是，虚拟路由器得到3.3.3.0/24的可达信息后，最终递交给OpenFlow Controller。有一些开源的程序可用来实现虚拟路由器，如Xorp、Quagga、ExaBGP等。一般地，虚拟路由器和外部的路由器的会话使用BGP协议。关于虚拟路由器的细节不是本文讨论的重点。
拓扑和路径
控制平面和数据平面的分离，形成以OpenFlow Controller为中心的集中的控制平台。OpenFlow网络中所有的交换机都在OpenFlow Controller的监管之下，于是，OpenFlow Controller就有机会掌握全局的网络拓扑视图以及每个交换机的状态。这样，OpenFlow Controller就能够更聪明地按照用户的路由策略来及时调整每个交换机的转发行为，从而更容易的实现如流量工程(Traffic Engineering)和快速故障恢复(Fail Over)这样的高级功能。这也是SDN的优势之所在。
一般地，OpenFlow Controller借助LLDP(Link Layer Discovery Protocol)协议发现OpenFlow交换机之间的连接状态。LLDP协议广泛地用于网络设备广播自己的ID，能力(Capabilities)和邻居。LLDP具有专用的MAC广播地址和EtherType，这样，OpenFlow Controller可以轻而易举的识别LLDP报文。网络拓扑的发现由OpenFlow Controller发起，OpenFlow Controller推送给每个OpenFlow交换机一个packet_out消息，指示交换机向所有的端口发出LLDP报文。与此同时，收到LLDP报文的交换机也会向它的所有的端口发送LLDP报文。然而，收到LLDP报文的交换机的Flow Table中没有和LLDP报文匹配的Flow Entry。因此，它就把收到的LLDP报文封装为packet_in消息发送给OpenFlow Controller。OpenFow Controller分析这些LLDP的报文，就能够知道交换机之间谁和谁通过哪个端口连接在一起。最终，OpenFlow Controller得到网络的完整的拓扑结构。
在OpenFlow网络的路由服务中，发现拓扑的目的是为了计算从一个边缘交换机到另一个边缘交换机之间的路径。为了讨论的方便，我们假设路由服务仅使用最短路径(Shortest Path)的策略。尽管这是最简单的情况，但可以举一反三地灵活运用这里给出的基本的原理和方法，实现更高级的更有价值的网络路由策略。网络的拓扑表现在数据结构上，就是一个图(Graph)。众所周知，给定一个像网络拓扑的那样的图，计算两点之间的最短路径的算法就是大名鼎鼎的Dijkstra's Algorithm。对于图中一个源节点，该算法可一次计算出到达所有其他节点的最短路径。算法的细节请参考Wikipedia的文档：http://en.wikipedia.org/wiki/Dijkstra's_algorithm。两点之间的最短路径也许并非只有一条，可能存在多条，我对此算法稍作扩展，能够计算出两点之间的所有最短路径。我的另一篇博客给出了这一扩展算法的C++实现，可直接编译运行。得到多条最短路径，就可以实现类似于ECMP的流量均衡(Traffic Ba lance)的路由策略。
对应于图1的情况，OpenFlow Controller使用Dijkstra's Algorithm得到主机A到主机B经过OpenFlow网络中的路径如下，其中的数字代表入端口或出端口。
同样地，主机A到主机C和主机C到主机B的路径如下：
当然，相反方向路径如Path(B, C)、Path(C, A)和Path(B, A)的计算自然也不在话下。
转发和路由
有了主机和接入到边缘交换机的信息，也能够算出边缘交换机到边缘交换机的路径。实现路由服务的最后一步是OpenFlow Controller向连接主机或子网的路径上的每个OpenFlow交换机下发Flow Entries，改变交换机的转发行为，以达到主机间通信的目的。如对于连接从主机A到主机B的路径Path(A, B)，下发到ES1和ES2的Flow Entry分别是：
这样，从主机A发往主机B的一个IP数据包就可以依次经过交换机ES1和ES2到达网络1.1.1.0/24。请注意，下发给交换机ES2的Flow Entry的action中，将把匹配到的数据包的目的MAC地址eth_dst更新为主机B的MAC地址。这样，数据包才会被二层(Ethernet)网络正确地转发到主机B。否则，数据包将被丢弃。
同样地，内部主机A到外部主机C的路由可由下面的Flow Entry来定义：
不难发现，OpenFlow网络把发往外部主机的数据包只送到相关的路由器，如上面例子中的路由器R。剩下的路由就交给外部的网络了，因为外部网络超出了OpenFlow Controller的控制范围。
最好，再看一个相反方向的从外部主机C到内部主机B的路由的实现：
需要指出的是，上文给出的下发到OpenFlow交换机的Flow Entries只是OpenFlow Controller实现路由服务的一种可能的方案，这里只是用来示例。而不同的OpenFlow Controller下发的Flow Entries会有所不同，但基本的原理应是大同小异。
我想，OpenFlow网络的路由服务的主要优点在于实现的灵活性，可根据实际的需求做具体的定制，而不受限于已有的路由协议标准和硬件基础设施的制约。正是有了SDN数据平面和管理平面的分隔，这种网络可编程的(Programable)灵活性才可能成为现实。
原文链接：OpenFlow网络中的路由服务
