SDN網絡的一大特點就是資源由控制器集中管理，控制器管理網絡，最基本的當然需要知道網絡的拓撲，而網絡拓撲可能時時發生變化，所以控制器需要時時監測，對于整個網絡來說，控制器擔負了太多的計算任務，所以如果能夠幫助控制器減壓，則會提高整個網絡的性能。本篇文章將以ryu控制器為例，首先介紹傳統網絡和現在SDN網絡的拓撲發現原理，然后介紹改進算法，最后講解改寫后的代碼邏輯。

一. LLDP拓撲發現原理

傳統網絡中的鏈路發現協議為LLDP(Link Layer Discovery Protocol)，LLDP允許局域網中的結點告訴其他結點他自己的capabilities和neighbours。在傳統以太網交換機中，交換機從自己的每個端口發送LLDP數據包，這個數據包不會被其他交換機轉發，壽命只有一跳，LLDP負載被封裝在以太網幀中，結構如下圖，其中深灰色的即為LLDP負載，Chassis ID TLV, Port ID TLV和Time to live TLV三個是強制字段，分別代表交換機標識符(在局域網中是獨一無二的)，端口號和TTL。這個數據發出并被鄰居結點收到之后進行解析，就可以知道這條鏈路的源目的交換機以及源目的接口。

二. ryu拓撲發現原理

OpenFlow的官方沒有規定標準的拓撲發現方法，現在的OFDP(OpenFlow Discovery Protocol)利用的仍然是傳統網絡中的鏈路發現協議LLDP，接下來介紹ryu如何利用LLDP發現拓撲，假設現在有兩個OpenFlow交換機連接在控制器上，如下圖，簡述拓撲發現步驟(以S1作為主體，S2的類似)：

1. SDN控制器構造PacketOut消息向S1的三個端口分別發送上圖所示的LLDP數據包，其中將Chassis ID TLV和Port ID TLV分別置為S1的dpid和端口號;

2. 控制器向交換機S1中下發流表，流表規則為：將從Controller端口收到的LLDP數據包從他的對應端口發送出去;

3. 控制器向交換機S2中下發流表，流表規則為：將從非Controller接收到LLDP數據包發送給控制器;

4. 控制器通過解析LLDP數據包，得到鏈路的源交換機，源接口，通過收到的PacketIn消息知道目的交換機和目的接口;

現在的ryu發現拓撲是對整個數據平面的所有交換機的所有端口發送PacketOut數據包，對于Fattree等網絡來說，端口的數量是交換機數量的k倍，因此導致了很多資源的消耗，所以是否可以對這個拓撲發現的機制進行改進，讓發送的PacketOut消息和交換機的數量相同?

三. 改進后的ryu拓撲發現機理

為了實現上面所提到的改進目標，需要將LLDP負載中的Port ID TLV進行改進，或者有其他的域和Port ID TLV一一映射也可以，這里提供一種解決辦法，在LLDP數據包從交換機端口轉發出去的時候，將這個以太網數據包的源MAC地址替換成為這個端口的MAC地址，而控制器在早先的配置階段已經獲得了關于交換機的端口的所有信息，所以對控制器來說，MAC地址和交換機的端口號是一一對應的，下面詳細講述改進方案。

1. 更新控制器的LLDP PacketOut消息數量，由一個端口一個，改為一個交換機一個PacketOut消息，LLDP數據包負載中的域Port ID TLV值置為零;

2. 控制器向流表下發一條規則：所有從端口Controller接收到的LLDP數據包，依次將其源MAC地址置為端口MAC地址，然后從相應的端口轉發出去;

3. 更新控制器的PacketIn消息處理機制，根據LLDP數據包的來源，可以得到目的交換機，目的端口，通過解析LLDP數據包，得到源MAC和源交換機，通過源MAC地址查找對應的端口號;

4. 由于是修改的代碼，所以不要忘了刪除原來的以端口主導的相關代碼。

四. 代碼分析

首選需要添加的一些變量和類

* SwitchData類：包含了時間戳以及交換機所包含的LLDP數據Shell

class SwitchData(object): 
  
#store the lldp information 
  
#send one LLDP information per switch 
  
def init (self, lldpdata): 
super(SwitchData, self).init() 
self.lldp_data = lldp_data 
self.timestamp = None 
self.sent = 0 
def lldp_sent(self): 
    self.timestamp = time.time() 
    self.sent += 1 
  
def lldp_received(self): 
    self.sent = 0 
  
def lldp_dropped(self): 
    return self.sent 
  
def clear_timestamp(self): 
    self.timestamp = None 
  
def __str__(self): 
    return 'SwitchData<timestamp=%s, sent=%d>' \ 
        % (self.timestamp, self.sent) 

* SwitchDataState：類似于PortDataState類，繼承自字典，保存從Switch類到SwitchData類的映射，維護了一個類似雙向鏈表的數據結構Shell

class SwitchDataState(dict): 
# dict: Switch class -> SwitchData class 
# slimed down version of OrderedDict as python 2.6 doesn't support it. 
_PREV = 0 
_NEXT = 1 
_KEY = 2 
def __init__(self): 
    super(SwitchDataState, self).__init__() 
    self._root = root = []          # sentinel node 
    root[:] = [root, root, None]    # [_PREV, _NEXT, _KEY] 
                                    # doubly linked list 
    self._map = {} 
  
def _remove_key(self, key): 
    link_prev, link_next, key = self._map.pop(key) 
    link_prev[self._NEXT] = link_next 
    link_next[self._PREV] = link_prev 
  
def _append_key(self, key): 
    root = self._root 
    last = root[self._PREV] 
    last[self._NEXT] = root[self._PREV] = self._map[key] = [last, root, key]                                                                
  
def _prepend_key(self, key): 
    root = self._root 
    first = root[self._NEXT] 
    first[self._PREV] = root[self._NEXT] = self._map[key] = [root, first, key]                                                                  
  
def _move_last_key(self, key): 
    self._remove_key(key) 
    self._append_key(key) 
  
def _move_front_key(self, key): 
    self._remove_key(key) 
    self._prepend_key(key) 
  
def add_switch(self, dp, lldp_data): 
    if dp not in self: 
        self._prepend_key(dp) 
        self[dp] = SwitchData( lldp_data) 
  
def lldp_sent(self, dp): 
    switch_data = self[dp] 
    switch_data.lldp_sent() 
    self._move_last_key(dp) 
    return switch_data 
  
def lldp_received(self, dp): 
    self[dp].lldp_received() 
  
def move_front(self, dp): 
    switch_data = self.get(dp, None) 
    if switch_data is not None: 
        switch_data.clear_timestamp() 
        self._move_front_key(dp) 
  
def get_switch(self, dp): 
    return self[dp] 
  
def del_port(self, dp): 
    del self[dp] 
    self._remove_key(dp) 
  
def __iter__(self): 
    root = self._root 
    curr = root[self._NEXT] 
    while curr is not root: 
        yield curr[self._KEY] 
        curr = curr[self._NEXT] 
  
def clear(self): 
    for node in self._map.values(): 
        del node[:] 
    root = self._root 
    root[:] = [root, root, None] 
    self._map.clear() 
    dict.clear(self) 
  
def items(self): 
    'od.items() ->;gt; list of (key, value) pairs in od' 
    return [(key, self[key]) for key in self] 
  
def iteritems(self): 
    'od.iteritems -> an iterator over the (key, value) pairs in od' 
    for k in self: 
        yield (k, self[k]) 

接著簡述修改的核心代碼，對應上面第三部分提到的四點

1. 更新控制器的LLDP PacketOut消息數量，由一個端口一個，改為一個交換機一個PacketOut消息，LLDP數據包負載中的域Port ID TLV值置為零;

#construct LLDP packet for switch 
def switchadded(self, dp): 
lldpdata = LLDPPacket.lldppacket( 
dp.dp.id, 0, '00:00:00:00:00:00', self.DEFAULTTTL) 
self.switches.addswitch(dp, lldpdata) 

2.控制器向流表下發一條規則：所有從端口Controller接收到的LLDP數據包，依次將其源MAC地址置為端口MAC地址，然后從相應的端口轉發出去;

if dp.ofproto.OFPVERSION>= ofprotov12.OFPVERSION: 
for portinfor in self.portstate[dp.id].values(): 
if portinfor.name != "tap:": 
actions.append(dp.ofprotoparser.OFPActionSetField(ethsrc=portinfor.hwaddr)) 
actions.append(dp.ofprotoparser.OFPActionOutput(portinfor.portno)) 
#actions = [dp.ofprotoparser.OFPActionOutput(self.portstate[dp].portno)] 
out = dp.ofprotoparser.OFPPacketOut( 
datapath=dp, inport=dp.ofproto.OFPP_CONTROLLER, 
bufferid=dp.ofproto.OFPNOBUFFER, actions=actions, 
data=switchdata.lldpdata) 
dp.sendmsg(out) 
else: 
LOG.error('cannot send lldp packet. unsupported version. %x', 
dp.ofproto.OFPVERSION) 

3.更新控制器的PacketIn消息處理機制，根據LLDP數據包的來源，可以得到目的交換機，目的端口，通過解析LLDP數據包，得到源MAC和源交換機，通過源MAC地址查找對應的端口號;

for port in self.portstate[srcdpid].values(): 
if port.hwaddr == srcmac: 
srcportno = port.portno 

4.由于是修改的代碼，所以不要忘了刪除原來的以端口主導的相關代碼。完整的代碼見github。

五. 實驗驗證

用Mininet建立一個二層二叉樹，s3作為根節點分別連接s1和s2。如下圖：

寫個簡單的ryu應用來調用拓撲發現模塊提供的API接口，應用為topo_learner.py,代碼見github用wireshark抓取OpenFlow和LLDP數據包來進行驗證

首先抓取交換機對控制器的響應消息，查看交換機的端口以及對應的MAC地址，從解析可以看到這是s3交換機，擁有四個端口(分別連接控制器，s1,s2,h3)，下圖是截取到的一個LLDP數據包，可以看出圖中藍色背景的LLDP的數據包的源MAC地址是s3交換機的3端口的MAC地址，說明前面的代碼修改成功。