Ryu拓撲發現原理分析
Ryu拓撲發現的核心模塊是ryu/topology目錄下的switches.py，拓撲發現的應用是同目錄下的dumper.py。在dumper.py中，會利用_CONTEXTS來實例化switches.py中的Switches類，然后將拓撲發現的相關信息通過日志方式(LOG.debug)顯示。啟動命令如下所示：
ryu-manager –verbose –observe-links ryu.topology.dumper
或者
ryu-manager –verbose –observe-links ./ryu/topology/dumper.py
其中–verbose參數用于顯示LOG.debug信息，–observe-links用于指明拓撲發現。
接下來對拓撲發現的核心模塊switches.py進行分析。
1. Port類
存儲端口相關信息，數據成員有：
self.dpid = dpid self._ofproto = ofproto self._config = ofpport.config self._state = ofpport.state self.port_no = ofpport.port_no self.hw_addr = ofpport.hw_addr self.name = ofpport.name
其中要特別注意的是dpid和port_no，即交換機ID和端口號，這兩個信息在下發流表項時很重要。
2. Switch類
存儲交換機相關信息，數據成員有：
self.dp = dp self.ports = []
其中dp是Datapath類的實例，該類定義在在ryu/controller/controller.py，主要屬性有：
self.socket = socket self.address = address self.is_active = True self.id = None # datapath_id is unknown yet self.ports = None
ports是一個由Port類實例組成的列表，存儲該交換機的端口。
3. Link類
保存的是源端口和目的端口(都是Port類實例)，數據成員有：
self.src = src self.dst = dst
4. PortState類
該類繼承自dict，保存了從port_no(int型)到port(OFPPort類實例)的映射。該類主要用作self.port_state字典的值(鍵是dpid)，用于存儲dpid對應的交換機的所有端口情況。
OFPPort類定義在ryu/ofproto目錄下對應的ofproto_v1_X_parser.py中(X代表版本號)，繼承自一個namedtuple，保存有port_no等信息。
5. PortData類
保存每個端口與對應的LLDP報文數據，數據成員有：
self.is_down = is_down self.lldp_data = lldp_data(這是LLDP報文的數據) self.timestamp = None self.sent = 0
每調用一次lldp_sent函數，便會把self.timestamp置為當前的時間(time.time())，并將self.sent加1;每調用一次lldp_received函數，便會把self.sent置為0。
6.PortDataState類
繼承自dict類，保存從Port類到PortData類的映射。該類維護了一個類似雙向循環鏈表的數據結構，并重寫了__iter__()，使得遍歷該類的實例(self.ports)時，會按照該雙向循環鏈表從哨兵節點(self._root)后一個節點開始遍歷。
包含一個add_port函數，傳入port和lldp_data，port作鍵，構建的PortData類實例作為值。
包含一個lldp_sent(self,port)函數，根據傳入的port(Port類實例)獲得對應的PortData類實例port_data，然后調用port_data.lldp_sent()(該函數會設置時間戳)，再調用self._move_last_key(port)，把該port移到類似雙向循環鏈表的數據結構中哨兵節點的前面(相當于下次遍歷的末尾);***返回port_data。
7. LinkState類
繼承自dict，保存從Link類到時間戳的映射。數據成員self._map字典用于存儲Link兩端互相映射的關系。
8. LLDPPacket類
靜態方法lldp_packet(dpid,port_no,dl_addr,ttl)用于構造LLDP報文，靜態方法lldp_parse(data)用于解析LLDP包，并返回源DPID和源端口號。
9. Switches類
該類是Ryu拓撲發現的核心所在。Switches類是app_manager.RyuApp類的子類，當運行switches應用時會被實例化，其__init__函數主要包括：
self.name = ‘switches’
self.dps = {} # datapath_id => Datapath class
self.port_state = {} # datapath_id => ports
self.ports = PortDataState() # Port class -> PortData class
self.links = LinkState() # Link class -> timestamp
self.is_active = True
self.dps字典用于保存dpid到Datapath類實例的映射，會在_register函數中添加新成員，_unregister函數中刪除成員。遍歷該字典可以得到連接的所有交換機。
self.port_state字典中鍵為dpid，值為PortState類型。遍歷該字典可以得到所有交換機對應的端口情況。當交換機連接時，會檢查交換機的id是否在self.port_state中，不在則創建PortState類實例，把交換機的所有端口號和端口存儲到該實例中;交換機斷開時，會從self.port_state中刪除。
self.ports是PortDataState類的實例，保存每個端口(Port類型)對應的LLDP報文數據(保存在PortData類實例中)，遍歷self.ports用于發送LLDP報文。
self.links是LinkState類的實例，保存所有連接(Link類型)到時間戳的映射。遍歷self.links的鍵即可得到所有交換機之間的連接情況。
如果ryu-manager啟動時加了–observe-links參數，則下面的self.link_discovery將為真，從而執行if下面的語句：
self.link_discovery = self.CONF.observe_links if self.link_discovery: self.install_flow = self.CONF.install_lldp_flow self.explicit_drop = self.CONF.explicit_drop self.lldp_event = hub.Event() self.link_event = hub.Event() self.threads.append(hub.spawn(self.lldp_loop)) self.threads.append(hub.spawn(self.link_loop))
綜上所述，該初始化函數__init__()主要是創建用于存儲相關信息的數據結構，創建兩個事件，然后調用hub.spawn創建兩個新線程執行self.lldp_loop和self.link_loop兩個函數。
#p#
9.1 lldp_loop函數
lldp_loop函數里是一個while循環，只要self.is_active為真，就一直循環執行。(close函數會把self.is_active置為False，該函數在離開模塊時自動被調用)。
(1)執行self.lldp_event.clear()，將Event類實例lldp_event的_cond屬性設為False，用于線程間同步。
提到線程同步，常用的函數有：
Event.wait()
Event對象的wait的方法只有內部信號為真的時候才會很快的執行并完成返回。當Event對象的內部信號標識為假時，則wait方法一直等待其為真時才返回。同時可以對wait設置timeout，當達到timeout設置的時間的時候就可以完成返回或執行。
Event.set()
將標識位設為Ture
Event.clear()
將標識伴設為False。
Event.isSet()
判斷標識位是否為Ture。
(2)創建ports_now和ports兩個列表，分別存儲尚未發送過LLDP報文的端口和已發送過LLDP報文并且超時的端口。
(3)遍歷self.ports(PortDataState類的實例)，獲得key(Port類實例)和data(PortData類實例)，如果data.timestamp為None(該端口還沒發送過LLDP報文)，則將key(端口)加入ports_now列表;否則，計算下次應該發送LLDP報文的時間expire，如果已經超時，則放到ports列表，否則就是還沒到發送時間，停止遍歷(發送LLDP報文時是按序發的，找到***個未超時的端口，后面的端口肯定更沒有超時，因為后面端口上次發送LLDP是在前一端口之后，前一個都沒超時后面的自然也沒超時)。
(4)遍歷ports_now列表，對每個端口調用self.send_lldp_packet(port)，發送LLDP報文。
send_lldp_packet函數執行過程如下：
a. 調用PortDataState類的lldp_sent函數，該函數會設置時間戳，移動相應端口在雙向循環鏈表中的位置，***返回PortData類實例port_data;
b. 如果該端口已經down掉，直接返回，否則執行下一步;
c. 根據port.dpid得到對應的Datapath類實例dp，如果不存在，則直接返回，否則執行下一步;
d. 發送LLDP報文。具體地：(1)生成actions：從port.port_no端口發出消息;(2)生成PacketOut消息：datapath指定為上一步得到的dp，actions為前面的，data為步驟a中返回的port_data的lldp_data;
(5)遍歷ports列表，對每個端口調用self.send_lldp_packet(port)，發送LLDP報文。
9.2 link_loop函數
link_loop函數也是一個while循環，只要self.is_active為真，就一直循環執行;
(1)執行self.link_event.clear()，將Event類實例link_event的_cond屬性設為False，用于線程間同步;
(2)創建deleted列表;
(3)遍歷self.links(LinkState類實例)，獲得link(Link類實例)和timestamp時間戳。如果已經超時，且該link對應的源端口是否在self.ports中，并且發送LLDP次數已超過self.LINK_LLDP_DROP，則添加到deleted列表中;
(4)遍歷deleted列表，執行：
a. 對其中的每條需要刪除的link調用link_down函數(該函數會刪除self.links中link對應的項目，并刪除self.links._map中link對應的項目)，并觸發EventLinkDelete事件。
b. 得到link對應的反向link，如果反向link不在deleted列表中，則將self.links中反向link的時間戳置為超時的事件，并將對端端口從self.ports的雙向循環鏈表中移動到哨兵節點的后面(下次檢查的開頭)，以便盡早檢查反向link是否也斷開了。
9.3 state_change_handler
該函數用于處理EventOFPStateChange事件，當交換機連接或者斷開時會觸發該事件。
如果狀態是MAIN_DISPATCHER：
(1)從ev.datapath獲得Datapath類實例dp，如果該dp的dpid已經在self.dps里有，則報出重復鏈接的警告。
(2)調用_register()，將dp.id和dp添加到self.dps中;如果該dp.id不在self.port_state中，則創建該dp.id對應的PortState實例，并遍歷dp.ports.values，將所有port(OFPPort類型)添加到該PortState實例中。
(3)調用_get_switch()，如果dp.id在self.dps中，則創建一個Switch類實例，并把self.port_state中對應的端口都添加到該實例中，最終返回該實例。
(4)如果交換機沒有重復連接，觸發EventSwitchEnter事件。
(5)如果沒設置self.link_discovery，返回;否則執行下一步。
(6)如果設置了self.install_flow，則根據OpenFlow版本生成相應流表項，使得收到的LLDP報文(根據目的MAC地址匹配)上報給控制器。
(7)如果交換機沒有重復連接，則遍歷(3)中得到的switch.ports的所有端口，如果端口port不是被保留的，則調用self._port_added(port)，該函數會調用LLDPPacket.lldp_packet()函數生成LLDP報文數據lldp_data(用于和“port.is_down()”一起構造PortData類實例)，然后調用PortDataState類的add_port(port,lldp_data)。
add_port()函數會檢查port是否在self.ports中，不在則將該port添加到雙向循環鏈表中哨兵節點的后面(下次檢查的開頭)，并把port和對應的PortData類實例(該端口對應的LLDP報文數據)添加到self.ports中。
(8)調用self.lldp_event.set()
如果狀態是DEAD_DISPATCHER：
(1)如果dp.id為None，即握手之前交換機就斷開連接了，則直接返回;否則執行下一步。
(2)調用_get_switch()獲得Switch實例;
(3)調用_unregister()，從self.dps和self.port_state中刪除該dpid對應的數據;
(4)觸發EventSwitchLeave事件。
(5)如果沒有設置link_discovery，返回;否則執行下一步。
(6)遍歷switch.ports中的每個端口port，如果不是保留端口，則調用PortDataState類的del_port()，將self.ports中port對應的數據刪除;調用Switches類的_link_down()。_link_down函數執行如下操作：
a. 調用LinkState類的port_deleted函數。在port_deleted函數里，首先調用get_peer()獲得對端端口，然后生成兩個Link對象(src->dst和dst->src)，并將這兩個對象從self.links中刪除(反向Link可能不存在);刪除src->dst和dst->src之間的映射(存儲在_map字典中)。***返回傳入的port對應的對端port和傳入的port本身。
b. 根據返回的“傳入的port對應的對端port和傳入的port本身”，創建Link對象，觸發EventLinkDelete事件(如果反向連接也存在，會觸發兩次EventLinkDelete事件)。
c. 調用self.ports.move_front(dst)，該函數會從self.ports中得到dst對應的PortData類實例port_data，如果port_data不為None，則調用clear_timestamp函數將其timestamp屬性置為None，并將dst移動到雙向循環鏈表中哨兵節點的后面(下次檢查的開頭)。
(7)調用self.lldp_event.set()。
#p#
9.4 port_status_handler
該函數用于處理EventOFPPortStatus事件，該事件是交換機主動發給控制器的。
如果原因為“添加”：
(1)在self.port_state里dp.id對應的PortState實例中添加該端口，并觸發EventPortAdd事件。
(2)如果沒有設置self.link_discovery，則返回;否則執行下一步。
(3)調用_get_port函數，該函數首先根據傳入的dpid得到Switch實例，然后遍歷實例的ports列表，找到并返回傳入的端口號對應的端口(Port類實例)。如果找到了端口并且端口不是保留的，則調用_port_added()，該函數會獲得LLDP相關的數據部分(用于構造PortData類實例)，然后調用PortDataState類的add_port()，該函數會將Port和對應的PortData映射關系存儲到self.ports中;調用self.lldp_event.set()。
如果原因為“刪除”：
(1)在self.port_state里該dpid對應的PortState實例中刪除該端口，并觸發EventPortDelete事件。
(2)如果沒有設置self.link_discovery，則返回;否則執行下一步。
(3)調用_get_port函數，該函數首先根據傳入的dpid得到Switch實例，然后遍歷實例的ports列表，找到并返回傳入的端口號對應的端口(Port類實例)。如果找到了端口并且端口不是保留的，則:
a. 調用del_port()，將該端口及對應的PortData從self.ports刪除;
b. 調用_link_down()，該函數會調用LinkState類的port_deleted函數，并返回傳入的port對應的對端port和傳入的port本身。在port_deleted函數里，首先調用get_peer()獲得對端端口，然后生成兩個Link對象(src->dst和dst->src)，并將這兩個對象從self.links中刪除(反向Link可能不存在);刪除src->dst和dst->src之間的映射(存儲在_map字典中)。根據返回的“傳入的port對應的對端port和傳入的port本身”，創建Link對象，觸發EventLinkDelete事件(如果反向連接也存在，會觸發兩次EventLinkDelete事件)。調用self.ports.move_front();
c. 調用self.lldp_event.set()。如果原因為“修改”：
(1)修改self.port_state里該dpid對應的PortState實例值，并觸發EventPortModify事件。
(2)如果沒有設置self.link_discovery，則返回;否則執行下一步。
(3)調用_get_port函數，該函數首先根據傳入的dpid得到Switch實例，然后遍歷實例的ports列表，找到并返回傳入的端口號對應的端口(Port類實例)。如果找到了端口并且端口不是保留的：
a. 調用PortDataState類的set_down()，該函數會調用Port類的is_down()，檢測端口是否已關閉;獲得Port對應的PortData實例，調用PortData的set_down函數，將對應的is_down修改為當前狀態(布爾值);調用PortData的clear_timestamp()，將對應的timestamp修改為None。如果檢測端口沒有關閉，調用_move_front_key()。set_down函數返回是否已關閉的檢測結果。如果檢測結果是已關閉，則調用_link_down()。
b. 調用self.lldp_event.set()。
9.5 packet_in_handler
該函數用于處理EventOFPPacketIn事件。
(1)如果沒有設置self.link_discovery，直接返回;否則執行下一步。
(2)嘗試調用LLDPPacket.lldp_parse(msg.data)來按照LLDP報文格式解碼收到的報文，獲得源交換機dpid和源端口號(該LLDP報文從哪臺交換機的哪個端口發出的)。如果不是LLDP報文格式，返回;否則執行下一步。
(3)獲得目的交換機的dpid和目的端口(上報Packet_In消息的交換機dpid和接收到LLDP報文的端口號)。
(4)調用_get_port函數，得到源端口對應的Port類實例。如果不存在或者該實例的dpid跟目的dpid相同，則直接返回;否則執行下一步。
(5)調用PortDataState類的lldp_received函數，該函數會再調用PortData類的lldp_received函數，將對應的self.sent值置為0。
(6)調用_get_port函數，得到目的端口對應的Port類實例。如果不存在該實例，則返回;否則執行下一步。
(7)調用LinkState類的get_peer函數，得到源端口原先對應的目的端口。如果該目的端口存在，且與現在解析得到的目的端口不同，則說明原先的鏈路已斷開，觸發EventLinkDelete事件。
(8)根據源端口和目的端口構造Link類實例，如果該實例不存在于self.links，則說明是新鏈路，觸發EventLinkAdd事件。
(9)調用LinkState類的update_link函數，該函數會將上一步構造的Link類實例加上時間戳存儲到self.links中，并構造逆向鏈路，返回逆向鏈路是否在self.links中的布爾值。如果逆向鏈路還不存在，那很有可能會馬上存在，因此調用PortDataState類的move_front函數，將目的端口移動到雙向循環鏈表中哨兵節點的后面(下次檢查的頭部)，盡早檢查;調用self.lldp_event.set()。
(10)如果設置了self.explicit_drop，則調用_drop_packet函數。
10. 拓撲發現概述
Switches類的初始化函數__init__()創建用于存儲相關信息的數據結構(self.dps、self.port_state、self.ports和self.links)，創建兩個事件(self.lldp_event 和self.link_event)，然后調用hub.spawn創建兩個新線程執行self.lldp_loop和self.link_loop兩個函數。其他工作就交給事件觸發和事件處理函數了。
交換機連接時觸發EventOFPStateChange事件，在對應的處理函數state_change_handler中會把連接上的交換機存儲到self.dps中，并把交換機的端口情況存儲到self.port_state中，并生成相應的LLDP報文數據，存儲在self.ports中(鍵為Port類型，值為PortData類型，PortData類的數據成員lldp_data存儲LLDP報文數據)。
lldp_loop函數會不停遍歷self.ports，并在需要的時候由send_lldp_packet函數執行發送LLDP報文的操作。
當LLDP報文被送回到控制器時，觸發EventOFPPacketIn事件，對應的處理函數packet_in_handler會解析LLDP報文，得到交換機之間的連接信息(Link類)，存儲到self.links中。
link_loop函數會遍歷self.links，及時檢查鏈路是否還是活的。
后記：
實際使用Ryu獲取拓撲信息時，更好的方式是使用Ryu提供的REST API，具體方法將在下文中介紹。但分析switches.py的過程對了解Ryu的工作機制和應用編寫方法還是蠻有用的。
