游戏式路由算法教学初探

胡青松，张 典，张 申，王艳芬

(中国矿业大学信息与电气工程学院物联网研究中心，江苏 徐州 221000)

“计算机网络”是一门实践性、很强的专业课程。本文在我校教改基金资助下，在课堂和实验中引入精心设计的互动式辅助游戏，以游戏聚合知识群，引导学生参与课程教学的各个环节。实践证明，这不但可以让网络领域中众多的知识点前后紧密衔接，而且能够显著提升学生的自学意识、合作意识和工程意识，培养其知识建构的能力。本课题具有较强的可复制性，能够方便的推广到工程类专业的网络类课程的教学实践中。我们和学生一起精心构思、设计和实现路由游戏，将该课程的原理融入到游戏的各个环节。

本文以路由信息协议(RIP)为例，介绍游戏式路由算法这一教学方法[1，2]。

1 “计算机网络”的RIP寻路原理

RIP协议即路由向量协议，它选择路由的依据是从源节点到目标节点的跳数最少。算法运行之初，路由器只知道到与其直接相连的网络的距离，以后通过交换路由器表项来更新路由信息[3]。RIP路由器收到地址为X的邻居路由器的RIP报文后，按照如下算法处理。

(1)修改收到的RIP报文的所有表项，令其“下一跳”字段为X，“距离”字段值加1。

(2)对于修改后的RIP报文，先根据“目的网络”判断，如果不在本路由器的路由表中，则把RIP报文的当前表项添加到本路由表;接着根据“下一跳”判断，若等于本路由表中表项的“下一跳”字段，则用该RIP表项替换本路由表的对应表项;最后根据“距离判断”，选取距离小的作为更新的依据。如果上述条件均不满足，则保持路由表项不变。

(3)若超时时间到达后还没有收到相邻路由器的RIP报文，则把该邻居路由器设为不可达。

(4)返回。

2 RIP路由游戏

2.1 游戏的设计思路

路由游戏的目的是为了让学生形象的理解所学知识点，降低学习难度。这就要求我们在设计游戏的时候，必须能够反映理论的实质。就我们的教学而言，最起码要能体现路由算法的基本运作过程。因此，我们在设计和实施路由游戏的时候，应该按照RIP导路原理进行。

RIP协议的核心思想是相邻网络之间的信息交换，使得彼此之间可以知道对方的最新网络状况，从而决定是否通过对方为“下一跳”传递数据。游戏规则是:我们将一名学生视为计算机网络中的一台计算机，将一个班的学生分为若干组，每组学生内的某个学生(组长)视为具有路由功能的路由器，并且假设都是域内路由器，因为RIP是域内路由协议。信息的传递通过学生之间传递便签条的方式进行，条上记录着各个组自己所知道的路由信息。

2.2 基本路由游戏

学生在学习RIP路由算法的时候，主要是难以理清算法的流程，无法领会这种在邻居间通过信息交换的方式实现路径选择的思想，而这一思想是众多路由算法的基础和灵魂。有鉴于此，本文打算通过游戏的方式(也是一种动手的方式)，加深学生对理论的理解，帮助他们融会贯通。我们采用如下的做法。

(1)预备—将一个班的学生按照学号排序，请班长利用离散正态随机数生成器(Excel和Matlab均有此项功能)生成5个数(假设为n1…n5)，要求这5个数相加之和等于该班学生总数(30人)，且任意一个数不能小于2。分组结果如图1所示。

(2)分组并选举组长—从全班选择最小学号的n1个所对的学生组成第1组，接下来的n2个学生组成第2组，以此类推，将全班学生分成5组，一个组对应于路由算法中的一个网络。从5个组中随机选择一名学生充当组长，组长充当路由器功能，其它学生充当该路由器所管辖的计算机。

在路由算法中，除了路由器之外，普通计算机一般不参与寻路过程。但是，我们在教学过程为了调动所有学生的积极性，在实施的时候有少许改变:教师分发一些便签给他们，让他们辅助组长完成路由选择;收到来自其它组的便签后，一起进行计算以确定下一跳。

(3)构成网络—我们的课程开设在一个比较大的教室，目的是让各组学生能够相对独立的聚集在教室的某一个区域，以便模拟实际的计算机网络的空间分散性;然后，由组长确定自己的邻居组，邻居组之间用一条红色的绳子连接起来，表示网络之间的链接;这样，便可形成初始网络，如图2所示。为了节省游戏时间，最好不要让所有组都能够两两直接相连，即不要形成全连接。组内的成员需要利用便签记录自己的邻居信息。

图1 学生初始分组情况

图2 分组形成的网络拓扑

(4)用便签记录本组的当前信息—便签按行记录信息，每一行包括三部分信息，即目标组(初始的时候只有邻居组，随着游戏的进行，目标不一定是自己的邻居组)到达目标组应该以哪个组作为下一跳，到达目标组共需要经过几组(跳数)。

(5)邻居组交换便签—各组将自己便签所记录的信息抄录一份交给自己的邻居(有几个邻居就需要抄录几份，可以由成员同时进行)。

(6)更新便签—某组(比如编号为2的组)收到邻居组的便签后，组内所有学生共同讨论该如何更新标签。其具体方法是:将收到的便签的每一行的下一跳修改为邻居组编号(比如为3)，跳数加1，得到修改后的便签;然后逐一检查改后便签的每一行，并与自己组的便签比较，先看改后便签的组编号(每一行的第一部分)。如果在自己的便签中不存在以该组编号为目标的行，就将改后便签的这一行原封不动的添加到自己的便签中;如果自己的便签中存在以该组编号为目标的行，再比较这两个便签行的第二部分(下一跳)。如果不一样，就将自己便签的行所对应的第二部分改成改后便签行的第二部分的值。如果一样，就将自身的便签第三部分的值设定为这两个便签行的第三部分的值的较小一个。这样将会得到本组的新标签，自己的旧便签和收到的邻居便签被扔掉。

(7)结束判断—如果所有组在收到邻居组标签后，计算之后的便签内容不再变化，说明各组已经知道了本网络的所有寻路情况，路由过程结束;否则跳转到(5)。

根据我们的经验，以上游戏做完大概需要25分钟左右。在教学过程中，可以根据需要决定是否继续做下面的扩展游戏。

2.3 扩展路由游戏

扩展游戏1(旧组离开，假定离开的组的编号为5):离开组的组长和所有成员不再参与游戏。此时，组4和组1将到达组5的距离设定为16(RIP中距离为16表示不可达)，然后按照正常游戏过程的第5～7步进行。

扩展游戏2(在扩展游戏1的基础上，将组5重新加入):此时，组5先向其邻居组4和组5递交便签，声明自己的位置，然后按照正常游戏过程的第4～7步进行。

完整的路由游戏流程如图2所示。

图2 路由游戏的流程

3 效果评价

学习“计算机网络”课程的两个班同时参与RIP协议的原理讲解环节，一班听完内容讲解以后到答疑室观看Flash动画，以加深对原理的理解，二班则留在教室参加路由游戏。

在下一次课的时候，做如下课堂测试。

(1)为什么RIP协议仅仅通过邻居之间的信息交换就能最终建立起有关全网的路由表?这个问题是以状态信息交换为基础的路由算法的基础。

(2)当某个路由器离开网络以后，RIP协议是否能够快速发现这个问题?这个问题直指RIP好消息传得快，坏消息传得慢的核心。

(3)为什么相邻路由器所交换的信息需要目标地址、下一跳和跳数这三个参数?这个问题对于路由表以及路由原理的理解至关重要。

(4)教师随便在黑板上画一个简单的网络，要求学生给出各个路由器的路由表。这可以真实地检验学生对原理的理解和灵活运用的能力。

实践表明，一班有近1/3的学生对问题(1)和问题(2)概念不清，答非所问，说明一些深层次的内容还有待明晰。而二班的学生则能用实际例子加以说明，对这两个问题的理解非常形象，说明路由游戏对学生的学习起到了较大的帮助。对于问题(3)和问题(4)，两个班的学生基本都能正确回答，这说明在某些内容没有弄清之前，教学实践也能得到正确的结果，从而给教学效果的检验带来误区。

4 结语

本文从工科教学的基本要求出发，为学生创造更多参与的机会，以互动游戏的方式来帮助学生理解“计算机网络”课程中网络协议这一难学的章节，不但充分调动了学生的积极性和手、脑、眼等各个身体感官，而且大大激发了学习兴趣，降低了学习难度。在课时允许的条件下，OSPF等路由层协议、数据链路层的透明网桥的工作原理等知识点的讲解，均可以采用这种教学方式。

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

[2]谢希仁.计算机网络(第五版)[M].北京:电子工业出版社，2008