游戲式路由算法教學初探

胡青松，張 典，張 申，王艷芬

(中國礦業(yè)大學信息與電氣工程學院物聯(lián)網(wǎng)研究中心，江蘇 徐州 221000)

“計算機網(wǎng)絡”是一門實踐性、很強的專業(yè)課程。本文在我校教改基金資助下，在課堂和實驗中引入精心設計的互動式輔助游戲，以游戲聚合知識群，引導學生參與課程教學的各個環(huán)節(jié)。實踐證明，這不但可以讓網(wǎng)絡領域中眾多的知識點前后緊密銜接，而且能夠顯著提升學生的自學意識、合作意識和工程意識，培養(yǎng)其知識建構的能力。本課題具有較強的可復制性，能夠方便的推廣到工程類專業(yè)的網(wǎng)絡類課程的教學實踐中。我們和學生一起精心構思、設計和實現(xiàn)路由游戲，將該課程的原理融入到游戲的各個環(huán)節(jié)。

本文以路由信息協(xié)議(RIP)為例，介紹游戲式路由算法這一教學方法[1，2]。

1 “計算機網(wǎng)絡”的RIP尋路原理

RIP協(xié)議即路由向量協(xié)議，它選擇路由的依據(jù)是從源節(jié)點到目標節(jié)點的跳數(shù)最少。算法運行之初，路由器只知道到與其直接相連的網(wǎng)絡的距離，以后通過交換路由器表項來更新路由信息[3]。RIP路由器收到地址為X的鄰居路由器的RIP報文后，按照如下算法處理。

(1)修改收到的RIP報文的所有表項，令其“下一跳”字段為X，“距離”字段值加1。

(2)對于修改后的RIP報文，先根據(jù)“目的網(wǎng)絡”判斷，如果不在本路由器的路由表中，則把RIP報文的當前表項添加到本路由表;接著根據(jù)“下一跳”判斷，若等于本路由表中表項的“下一跳”字段，則用該RIP表項替換本路由表的對應表項;最后根據(jù)“距離判斷”，選取距離小的作為更新的依據(jù)。如果上述條件均不滿足，則保持路由表項不變。

(3)若超時時間到達后還沒有收到相鄰路由器的RIP報文，則把該鄰居路由器設為不可達。

(4)返回。

2 RIP路由游戲

2.1 游戲的設計思路

路由游戲的目的是為了讓學生形象的理解所學知識點，降低學習難度。這就要求我們在設計游戲的時候，必須能夠反映理論的實質(zhì)。就我們的教學而言，最起碼要能體現(xiàn)路由算法的基本運作過程。因此，我們在設計和實施路由游戲的時候，應該按照RIP導路原理進行。

RIP協(xié)議的核心思想是相鄰網(wǎng)絡之間的信息交換，使得彼此之間可以知道對方的最新網(wǎng)絡狀況，從而決定是否通過對方為“下一跳”傳遞數(shù)據(jù)。游戲規(guī)則是:我們將一名學生視為計算機網(wǎng)絡中的一臺計算機，將一個班的學生分為若干組，每組學生內(nèi)的某個學生(組長)視為具有路由功能的路由器，并且假設都是域內(nèi)路由器，因為RIP是域內(nèi)路由協(xié)議。信息的傳遞通過學生之間傳遞便簽條的方式進行，條上記錄著各個組自己所知道的路由信息。

2.2 基本路由游戲

學生在學習RIP路由算法的時候，主要是難以理清算法的流程，無法領會這種在鄰居間通過信息交換的方式實現(xiàn)路徑選擇的思想，而這一思想是眾多路由算法的基礎和靈魂。有鑒于此，本文打算通過游戲的方式(也是一種動手的方式)，加深學生對理論的理解，幫助他們?nèi)跁炌āＮ覀儾捎萌缦碌淖龇ā?/p>

(1)預備—將一個班的學生按照學號排序，請班長利用離散正態(tài)隨機數(shù)生成器(Excel和Matlab均有此項功能)生成5個數(shù)(假設為n1…n5)，要求這5個數(shù)相加之和等于該班學生總數(shù)(30人)，且任意一個數(shù)不能小于2。分組結果如圖1所示。

(2)分組并選舉組長—從全班選擇最小學號的n1個所對的學生組成第1組，接下來的n2個學生組成第2組，以此類推，將全班學生分成5組，一個組對應于路由算法中的一個網(wǎng)絡。從5個組中隨機選擇一名學生充當組長，組長充當路由器功能，其它學生充當該路由器所管轄的計算機。

在路由算法中，除了路由器之外，普通計算機一般不參與尋路過程。但是，我們在教學過程為了調(diào)動所有學生的積極性，在實施的時候有少許改變:教師分發(fā)一些便簽給他們，讓他們輔助組長完成路由選擇;收到來自其它組的便簽后，一起進行計算以確定下一跳。

(3)構成網(wǎng)絡—我們的課程開設在一個比較大的教室，目的是讓各組學生能夠相對獨立的聚集在教室的某一個區(qū)域，以便模擬實際的計算機網(wǎng)絡的空間分散性;然后，由組長確定自己的鄰居組，鄰居組之間用一條紅色的繩子連接起來，表示網(wǎng)絡之間的鏈接;這樣，便可形成初始網(wǎng)絡，如圖2所示。為了節(jié)省游戲時間，最好不要讓所有組都能夠兩兩直接相連，即不要形成全連接。組內(nèi)的成員需要利用便簽記錄自己的鄰居信息。

圖1 學生初始分組情況

圖2 分組形成的網(wǎng)絡拓撲

(4)用便簽記錄本組的當前信息—便簽按行記錄信息，每一行包括三部分信息，即目標組(初始的時候只有鄰居組，隨著游戲的進行，目標不一定是自己的鄰居組)到達目標組應該以哪個組作為下一跳，到達目標組共需要經(jīng)過幾組(跳數(shù))。

(5)鄰居組交換便簽—各組將自己便簽所記錄的信息抄錄一份交給自己的鄰居(有幾個鄰居就需要抄錄幾份，可以由成員同時進行)。

(6)更新便簽—某組(比如編號為2的組)收到鄰居組的便簽后，組內(nèi)所有學生共同討論該如何更新標簽。其具體方法是:將收到的便簽的每一行的下一跳修改為鄰居組編號(比如為3)，跳數(shù)加1，得到修改后的便簽;然后逐一檢查改后便簽的每一行，并與自己組的便簽比較，先看改后便簽的組編號(每一行的第一部分)。如果在自己的便簽中不存在以該組編號為目標的行，就將改后便簽的這一行原封不動的添加到自己的便簽中;如果自己的便簽中存在以該組編號為目標的行，再比較這兩個便簽行的第二部分(下一跳)。如果不一樣，就將自己便簽的行所對應的第二部分改成改后便簽行的第二部分的值。如果一樣，就將自身的便簽第三部分的值設定為這兩個便簽行的第三部分的值的較小一個。這樣將會得到本組的新標簽，自己的舊便簽和收到的鄰居便簽被扔掉。

(7)結束判斷—如果所有組在收到鄰居組標簽后，計算之后的便簽內(nèi)容不再變化，說明各組已經(jīng)知道了本網(wǎng)絡的所有尋路情況，路由過程結束;否則跳轉(zhuǎn)到(5)。

根據(jù)我們的經(jīng)驗，以上游戲做完大概需要25分鐘左右。在教學過程中，可以根據(jù)需要決定是否繼續(xù)做下面的擴展游戲。

2.3 擴展路由游戲

擴展游戲1(舊組離開，假定離開的組的編號為5):離開組的組長和所有成員不再參與游戲。此時，組4和組1將到達組5的距離設定為16(RIP中距離為16表示不可達)，然后按照正常游戲過程的第5～7步進行。

擴展游戲2(在擴展游戲1的基礎上，將組5重新加入):此時，組5先向其鄰居組4和組5遞交便簽，聲明自己的位置，然后按照正常游戲過程的第4～7步進行。

完整的路由游戲流程如圖2所示。

圖2 路由游戲的流程

3 效果評價

學習“計算機網(wǎng)絡”課程的兩個班同時參與RIP協(xié)議的原理講解環(huán)節(jié)，一班聽完內(nèi)容講解以后到答疑室觀看Flash動畫，以加深對原理的理解，二班則留在教室參加路由游戲。

在下一次課的時候，做如下課堂測試。

(1)為什么RIP協(xié)議僅僅通過鄰居之間的信息交換就能最終建立起有關全網(wǎng)的路由表?這個問題是以狀態(tài)信息交換為基礎的路由算法的基礎。

(2)當某個路由器離開網(wǎng)絡以后，RIP協(xié)議是否能夠快速發(fā)現(xiàn)這個問題?這個問題直指RIP好消息傳得快，壞消息傳得慢的核心。

(3)為什么相鄰路由器所交換的信息需要目標地址、下一跳和跳數(shù)這三個參數(shù)?這個問題對于路由表以及路由原理的理解至關重要。

(4)教師隨便在黑板上畫一個簡單的網(wǎng)絡，要求學生給出各個路由器的路由表。這可以真實地檢驗學生對原理的理解和靈活運用的能力。

實踐表明，一班有近1/3的學生對問題(1)和問題(2)概念不清，答非所問，說明一些深層次的內(nèi)容還有待明晰。而二班的學生則能用實際例子加以說明，對這兩個問題的理解非常形象，說明路由游戲?qū)W生的學習起到了較大的幫助。對于問題(3)和問題(4)，兩個班的學生基本都能正確回答，這說明在某些內(nèi)容沒有弄清之前，教學實踐也能得到正確的結果，從而給教學效果的檢驗帶來誤區(qū)。

4 結語

本文從工科教學的基本要求出發(fā)，為學生創(chuàng)造更多參與的機會，以互動游戲的方式來幫助學生理解“計算機網(wǎng)絡”課程中網(wǎng)絡協(xié)議這一難學的章節(jié)，不但充分調(diào)動了學生的積極性和手、腦、眼等各個身體感官，而且大大激發(fā)了學習興趣，降低了學習難度。在課時允許的條件下，OSPF等路由層協(xié)議、數(shù)據(jù)鏈路層的透明網(wǎng)橋的工作原理等知識點的講解，均可以采用這種教學方式。

[1]De Weck O L，Kim I Y，Hassan R.Active Learning Games[Z].Kingston，Ontario，Canada:2005

[2]謝希仁.計算機網(wǎng)絡(第五版)[M].北京:電子工業(yè)出版社，2008