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

一. LLDP拓撲發(fā)現(xiàn)原理

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

二. ryu拓撲發(fā)現(xiàn)原理

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

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

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

3. 控制器向交換機S2中下發(fā)流表，流表規(guī)則為：將從非Controller接收到LLDP數(shù)據(jù)包發(fā)送給控制器;

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

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

三. 改進后的ryu拓撲發(fā)現(xiàn)機理

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

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

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

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

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

四. 代碼分析

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

* SwitchData類：包含了時間戳以及交換機所包含的LLDP數(shù)據(jù)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類的映射，維護了一個類似雙向鏈表的數(shù)據(jù)結構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消息數(shù)量，由一個端口一個，改為一個交換機一個PacketOut消息，LLDP數(shù)據(jù)包負載中的域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.控制器向流表下發(fā)一條規(guī)則：所有從端口Controller接收到的LLDP數(shù)據(jù)包，依次將其源MAC地址置為端口MAC地址，然后從相應的端口轉發(fā)出去;

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消息處理機制，根據(jù)LLDP數(shù)據(jù)包的來源，可以得到目的交換機，目的端口，通過解析LLDP數(shù)據(jù)包，得到源MAC和源交換機，通過源MAC地址查找對應的端口號;

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

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

五. 實驗驗證

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

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

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