基于 OLSR 路由协议的 HIDA 算法概要

第一篇：基于 OLSR 路由协议的 HIDA 算法概要

— 147— 36卷 第 9期

ol.36 No.9 2010年 5月

Ma 基于 OLSR 路由协议的 HIDA 算法 姚 胜,冷甦鹏

(电子科技大学通信抗干扰技术国家级重点实验室,成都 610054 摘 要:针对 Ad Hoc网络中的虫洞攻击,根据最优链路状态路由(OLSR协议的运行特点,提出检测伪邻居的 HELLO 间隔分布式算法(HIDA。仿真结果表明,在网络平均节点数大于

4、节点随机最大移动速率大于 2 m/s时, HIDA 算法能达到 80%以上的虫洞攻击检测率。关键词:无线自组织网络;邻居探测;虫洞攻击;最优链路状态路由协议;HELLO 间隔分布式算法

HIDA Algorithm Based on OLSR Routing Protocol YAO Sheng, LENG Su-peng(National Key Lab of Communication Anti-interference Technology, University of Electronic Science and Technology of China, Chengdu 610054 【 Abstract 】 Aiming at the wormhole attack in Ad Hoc network, according to Optimized Link State Routing(OLSR protocol, this paper presents a HELLO Interval Distributed Algorithm(HIDA to detect fake neighbor.Simulation results show that HIDA has wormhole attack detection rate above 80% when network average node number is greater than 4, node random maximal migration rate is greater than 2 m/s.【 Key words】 Wireless Ad Hoc Network(WANET;neighbor probing;wormhole attack;Optimized Link State Routing(OLSR protocol;HELLO Interval Distributed Algorithm(HIDA

计 算 机 工 程 Computer Engineering第 V y 2010 术·

文章编号:1000— 3428(201009— 0147— 03 文献标识码:A 中图分类号:TP393 ·安全技 1 概述

移动 Ad Hoc网络是一种自适应的自组织网络,由于它

性能优越,因此在越来越多场合得到应用。目前关于 Ad Hoc自组网的研究大多集中在基于可信任环境下的通信和路由有 效性。由于 Ad Hoc自组网无线信道的开放性,因此极易遭 到攻击。攻击方通过攻击无线网络协议,窃取传输信息使网 络无法正常工作。因此,无线网络的安全问题引起了很多关 注。路由协议是节点通信的基础,协议运行环境为移动多跳 传输,这使 Ad Hoc网络路由协议的可靠性必须依赖所有节 点协调工作。如果网络中存在节点异常工作或被攻击节点入 侵等情况, 则会导致路由协议崩溃, 整个网络不能正常工作。因此,必须提升 Ad Hoc网络的安全性能。

在移动 Ad Hoc网络中的虫洞攻击是一种很特殊的恶意 攻击形式。它通过控制路由入侵网络, 破坏性大且很难探测。一般的安全策略如加密认证很难抵御虫洞攻击,因此,本文 以最优链路状态路由(Optimized Link State Routing, OLSR协 议为模型进行针对性的改进。

虫洞攻击一般由 2个能直接通信的攻击节点协同发动, 它们之间的链路称为“隧道”(其长度大于普通节点的信号覆 盖半径,在路由上体现为 1跳距离 是发动攻击的基础 [1]。虫 洞攻击示意图如图 1所示,其中, A 和 B 是距离较远的 2个 节点,不在信号覆盖范围内;X 和 Y 是协同攻击节点,在它 们之间建立一条私密的链路形成“隧道”。在这个网络中, 通过彼此接收到对方的 HELLO 报文来确定邻居探测。当 A 向

周围邻居发送 HELLO 报文时, X 收到该报文后通过隧道 传给 Y , 由 Y 原封不动地重放到网络中, B 接收到 A 的 HELLO 报文,判定 A 为 1跳邻居。同理, A 认为 B 是自己的邻居。因此, A, B以及所有位于 X, Y传播范围内正常节点的邻居 表中均会存在伪邻居。若路由协议是以最短路径优先原则建

立路由表项, A 到 B 的最短距离为(2n +2 跳, 则 A 的 n 跳内 的邻居会通过“隧道”建立路由表项到达 B。所有节点的通 信都暴露在攻击节点下,通过路由信息的扩散传播会使网络 极大范围内的节点通信受控于攻击节点,攻击者对通过其路 径的信息进行窜改或丢弃等恶意操作使网络中部分节点无法 通信,甚至使整个网络瘫痪。

图 1 虫洞攻击示意图 2 相关研究

由于移动 Ad Hoc网络极易受到各种攻击,因此已提出 很多安全协议。虽然安全路由协议有很多,但没有一种能应 对所有恶意攻击,尤其是能绕过网络加密认证系统的虫洞攻 击,加密认证系统对虫洞攻击没有任何作用。因此,要对路 由协议单独进行针对性改进,使网络能抵御虫洞攻击。

Packet Leashes[2]是经典的抵御虫洞攻击的方法。其原理

基金项目:国家自然科学基金资助项目(60802024;教育部博士点新 教师基金资助项目(200806141014;通信抗干扰技术国家级重点实验 室基金资助项目

作者简介:姚 胜(1983-, 男, 硕士研究生, 主研方向:数据通信, 无线自组织网络,网络安全;冷甦鹏,副教授、博士 收稿日期:2009-11-28 E-mail :linmin17125@163.com 是在数据报文中附加限制报文最大传输距离的信息。这种信息可以分为 2种:位置限制和时间限制。该方法 需要网络提供一个强大的密钥管理和时钟同步系统,对网络 带宽有很高的要求。另一种检测虫洞攻击的方法是计算节点 每跳传输时延或位置信息,它通过包含虫洞链路的 2个节点 之间的传输时延远大于真实 1跳邻居传输时延进行判断。TTM [3]是针对 AODV 协议计算路由发现过程中的每跳传输时 延来检测是否有不正常链路存在。这种时延机制能有效抵御 虫洞攻击,但加重了路由协议的开销,使其效率下降。然而, 一些虫洞攻击可通过 at the bit level或 at the physical layer发 起很难被时延分析检测到。

文献 [4]提出一种针对按需的路由协议,利用路由统计信 息检测虫洞攻击,通过在源节点和目的节点之间建立多跳路 由路径来判断统计信息中是否存在嫌疑链路。这种多路径方 法很可能由于统计信息不足导致误判,效率较低。另外,一 些方法大多依赖精确时钟同步的假设或需要特殊设备,很难 应用到实际网络中。

综上所述,这些安全路由协议都存在局限性,它们一般 都对网络进行严格的假设, 建立的理论模型与实际相差较大, 并且一些提出方法需要特殊硬件设备等。由于这些机制的引 入很难在路由协议的性能表现和抵御虫洞攻击的有效性方面 取得平衡,因此需要进一步对提升它们的安全性能,降低路 由协议复杂度和网络开销。基于 OLSR 路由协议的 HIDA 算法 3.1 OLSR路由协议

移动 Ad Hoc网络中的路由协议分为表驱动路由协议和 按需路由协议。OLSR 路由协议属于表驱动链路状态路由协 议,适合应用于大型密集网络。该协议通过节点周期性地交 换各种控制信息来建立分布式计算和更新网络拓扑,节点根 据最短路径优先原则来计算路由表。

OLSR 协议运行的基础是 2种主要的控制报文:HELLO 报文和 TC(Topology Control报文。HELLO 报文在 1跳的范 围内被周期性广播,不被转发,它用于建立节点的邻居表(包 括邻居节点地址以及本节点到邻居节点的延迟 和计算节点 的多点中继集(Multipoint Relay, MPR。TC 报文包含节点 MPR 邻居的信息被广播到全网,只有属于 MPR 的邻居节点 能转发 TC 控制报文。这种机制有效地控制了 TC 报文在网络 中广播的规模,减少了网络负荷,避免形成广播风暴。节点 根据收到的 TC 报文中节点的邻居关系独立计算网络的拓扑 图,依据最短路径优先原则计算路由表。OLSR 路由协议包 括 4个主要过程:邻居探测, MPR 选择, TC 报文扩散和路 由表计算,其中,通过发送 1跳内 HELLO 报文进行邻居侦 听是该协议运行的基础。

由图 1可以看出,虫洞攻击发动时会使 2个攻击节点的 传输范围内所有正常节点相互收到 HELLO 报文,使它们成 为伪邻居。由于节点依据这种错误的拓扑关系进行路由计算, 因此破坏了 OLSR 路由协议的正常运行。伪邻居的产生是虫 洞攻击发动的基础,避免伪邻居的产生有效抵御虫洞攻击。3.2 算法实现

本文基于虫洞攻击提出一种检测伪邻居的安全路由算 法—— HELLO 间隔分布式算法(HELLO Interval Distributed Algorithm, HIDA,并对 OLSR 协议进行相应改进。本文模 型是一个大型密集的 Ad Hoc网络,节点不频繁的随机移动, 移动速率不高。改进思想是依据 OLSR 路由协议运行的特点, 通过比较正常邻居和伪邻居的产生是否导致非法拓扑结构来 判断是否存在虫洞攻击。

伪邻居的判断示意图如图 2所示,假设互为邻居的正常 节点 A, B, C都位于攻击节点 X 的覆盖范围内,并假设 Y 覆 盖范围内正常节点中存在 2跳邻居 M 和 N。当发生虫洞攻击 时,在某个 HELLO 2 s间隔内, A, B, C节点均会收到 M 和 N 的 HELLO 报文并更新各自邻居表。这时就能进行判断:新出现的 M 和 N 可不可能是 A 的正常邻居节点。若 M 和 N 均 为 A 的正常邻居节点,那么说明它们在 HELLO 间隔内均从 A 的覆盖范围之外移动到 A 覆盖范围之内。因此, A 应处于 M 和 N 的移动范围重合处,即图中阴影处。

同样, B 和 C 节点也是如此。因为在 HELLO 间隔这段时 间内,低速节点运动距离很小,这样 A, B, C 3个节点几乎同 时位于以 M 和 N 移动距离为长和宽的矩形区域内,而这个面 积相对于节点的通信覆盖范围太小,本文认为网络中不存在 这样不合理的拓扑机构,即认为 M 和 N 均是 A 的伪邻居, 网络中存在虫洞攻击。

(a判断过程

(b判断结果

图 2 伪邻居的判断示意图

依据上述分析可知, HIDA 算法的主要思想是:某节点 A 若在 HELLO 间隔这段时间内第 1次收到 2个节点 M 和 N 的 HELLO 报文, 并且这 2个节点不互为邻居, 同时检测到它们 不在 A 的 1跳和 2跳邻居表内。在 HELLO 间隔中, A 通过 接收到已存在的邻居节点的 HELLO 报文可以计算这个短时 间内收到 M 和 N 的 HELLO 报文的正常邻居节点个数, 若该 邻居节点个数大于或等于 2个,则 A 就可判定 M 和 N 为伪 邻居, 忽略它们的 HELLO 报文以及 M 和 N 邻居表中节点的 HELLO 报文,该算法从收到一个未知的新 HELLO 报文开始 启动,并在 2倍 HELLO 间隔时间内周期地进行计算。4 仿真分析

文献 [5]提出另一种基于 OLSR 路由协议的防御虫洞攻击 算法:异常拓扑分布式算法(Abnormal Topology Distributed Algorithm, ATDA,它利用拓扑分析的方法,依据网络中发 生虫洞攻击时引入的不正常节点密集度进行检测,本文对 HIDA 和 ATDA 2种算法进性仿真分析并比较性能。

本文仿真通过 NS2软件平台实现。在仿真时,对 NS2 — 148—

中 OLSR 协议模块进行相应改动,添加 HIDA 算法,完成该 协议的安全改进并建立仿真模型。本文共进行 3次仿真,其 中,前 2次仿真对 ATDA 和 HIDA 2种算法进行性能比较;第 3次仿真是对 HIDA 算法的有效性进行分析。3次仿真的 场景参数各不相同,但都是节点随机均匀分布在 800 m×800 m的矩形区域中,节点的通信距离是 100 m。

在不同节点数(节点数分别是 20, 40, 60, 80, 100, 120, 140, 160, 180, 200下,随机生成拓扑 100次,每次均进行一次虫 洞攻击,所有节点随机移动,最大移动速度是 2 m/s,仿真时 间为 20 s,不同节点数下 2种算法攻击检测率的比较结果如 图 3所示。

0.0 0.20.40.60.8 1.0 节点数

攻 击 检 测 率

图 3 不同节点数下 2种算法的攻击检测率比较

在不同的移动速率下,节点数为 100,所有节点随机移 动,速率大小服从均匀分布,最大速率分别为 0 m/s, 1 m/s, 2 m/s, 4 m/s, 6 m/s, 8 m/s, 10 m/s,随机生成拓扑 200次并进 行 100次攻击,仿真时间为 20 s。2种算法的攻击误判率、漏判率比较如图 4、图 5所示。2 4 6 8 10 0.00 0.050.100.150.20 节点最大移动速率 /(m·s-1 攻 击 误 判 率

图 4 2种算法的攻击误判率比较

节点最大移动速率 /(m·s-1 攻 击 漏 判 率 02 4 6 8 10 0.20.40.6 图 5 2种算法的攻击漏判率比较

在不同节点数、不同移动速率下,节点数分别为 60, 80, 120,节点随机移动最大速率为 0, 1 m/s, 2 m/s, 4 m/s, 6 m/s, 8 m/s, 10 m/s,仿真时间为 70 s,分析 HIDA 算法在成功检测 虫洞攻击的情况下，HIDA 算法伪邻居的误判率和漏判率结 果如图

6、图 7所示。

节点最大移动速率 /(m·s-1 伪 邻 居 误

判 率

图 6 HIDA算法的伪邻居误判率比较 0.0 0.20.40.60.8 1.0 节点最大移动速率 /(m·s-1 伪 邻 居 漏 判 率

图 7 HIDA算法的伪邻居漏判率比较 5 结束语

通过仿真比较可知,本文 HIDA 算法相对于 ATDA 算法 在网络节点分布不是很密集时性能表现更加优越,能取得更 高的检测率。在不同节点移动速率下, HIDA 算法的攻击漏 判率更低,但攻击误判率在节点高速移动下表现却稍差。在 成功检测到虫洞攻击的情况下, HIDA 算法对伪邻居的判断 在节点低速移动下也具有较高性能,但在高速移动情形下协 议还需进一步研究。

综上所述, HIDA 算法在低速密集的无线自组织网络中 对虫洞攻击的防御表现出优越性能,同时该协议的运行不会 对网络产生多余流量,保证了协议的高效性。

参考文献

[1] Hu Yih-Chun, Perrig A, Johnson D B.Wormhole Attacks in Wireless Networks[J].IEEE Journal on Selected Areas in Communications, 2006, 24(2: 370-380.[2] Hu Yih-Chun, Perrig A, Johnson D B.Packet Leashes: A Defense Against Wormhole Attacks in Wireless Ad Hoc Net-works[C]//Proc.of the 22nd Annual Joint Conference of IEEE Computer and Communications Societies.Pittsburgh, USA: IEEE Press, 2003.[3] Tran Phuong-Van, Hung Le-Xuan, Lee Young-Koo, et al.TTM: An Efficient Mechanism to Detect Wormhole Attacks in Wireless Ad Hoc Networks[C]//Proc.of CCNC’07.Las Vegas, USA: IEEE Press, 2007.[4] Qian Lijun, Song Ning, Li Xiangfang.Detecting and Locating Wormhole Attacks in Wireless Ad Hoc Networks Through Statistical Analysis of Multi-path[C]//Proc.of 2005 IEEE Wireless Communications and Networking Conference.[S.l.]: IEEE Press, 2005.[5] Maheshwari R, Gao Jie, Samir R D.Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information[C]//Proc.of INFOCOM’07.[S.l.]: IEEE Press, 2007.编辑 陆燕菲

— 149—

第二篇：计算机网络实验报告(路由算法、Socket编程)

计算机网络实验报告

班级： 姓名： 学号：

实验一

一． 实验目的及要求

编写程序，模拟距离矢量路由算法的路由表交换过程，演示交换后的路由表的变化。

二． 实验原理

距离矢量路由算法是这样工作的：每个路由器维护一张路由表（即一个矢量），它以网络中的每个路由器为索引，表中列出了当前已知的路由器到每个目标路由器的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新他们的内部路由表。

举例来说，假定使用延迟作为“距离”的度量标准，并且该路由器发送一个列表，其中包含了他到每一个目标路由器的延时估计值；同时，他也从每个邻居路由器接收到一个类似的列表。假设一个路由器接收到来自邻居x的一个列表，其中x（i）表示x估计的到达路由器i所需要的时间。如果该路由器知道他到x的延时为m毫秒，那么他也知道在x（i）+m毫秒之间内经过x可以到达路由器i。一个路由器针对每个邻居都执行这样的计算，就可以发现最佳的估计值，然后在新的路由器表中使用这个最佳的估计值以及对应的输出路线。

三．源程序：

#include “stdio.h” #include “stdlib.h” #include “malloc.h” #include “graphics.h” #include “dos.h” #define VERNUM 7

typedef struct {

int dis;

int flag;

int flag2;}RoutNode;

char tmp[10];RoutNode data[VERNUM][VERNUM];

void welcome();

void InitRoutData(FILE* pfile);

void PrintRoutData();

void SendInf(int recv, int send);

void Exchange();

int main(){

int start, end, i, j, m, n;

FILE *pfile;

welcome();

pfile = fopen(“1.txt”, “r”);

if(pfile == NULL)

{

printf(“the file wrong,press any key to come back.n”);

getch();

return;

}

else

InitRoutData(pfile);

fclose(pfile);

printf(“nthe original route table:n”);

for(i = 0;i

{

printf(“%c||”, i + 65);

for(j = 0;j < VERNUM;j++)

if(data[i][j].dis > 0)

printf(“<%c %d> ”, j + 65, data[i][j].dis);

printf(“n”);

}

PrintRoutData();

getch();

for(i = 0;i < VERNUM;i++)

{

for(m = 0;m < VERNUM;m++)

for(n = 0;n < VERNUM;n++)

data[m][n].flag = 0;

Exchange();

PrintRoutData();

getch();

}

printf(“nexchange the route table:n”);

return 0;}

void welcome(){

int gdriver=DETECT,gmode;

registerbgidriver(EGAVGA_driver);

initgraph(&gdriver, &gmode,“C:Win-TC”);

cleardevice();

setbkcolor(CYAN);

setviewport(0,0,639,479,1);

clearviewport();

setbkcolor(BLUE);

setcolor(14);

rectangle(200,200,440,280);

setfillstyle(1,5);

floodfill(300,240,14);

settextstyle(0,0,2);

outtextxy(50,30,“Distance Vector Routing Algorithm”);

setcolor(15);

settextstyle(1,0,4);

outtextxy(260,214,“Welcome to use!”);

line(0,80,640,80);

getch();

delay(300);

cleardevice();} void InitRoutData(FILE* pfile){

char num[10];

int i = 0;

char c;

int m, n;

fseek(pfile, 0, 0);

for(m = 0;!feof(pfile)&& m < 7;m++)

{

for(n = 0;!feof(pfile)&& n < 7;n++)

{

while(!feof(pfile))

{

c = fgetc(pfile);

if(c == ',')

{

num[i] = '';

data[m][n].dis = atoi(num);

data[m][n].flag = 0;

data[m][n].flag = 0;

i = 0;

break;

} /*end of if*/

else if((c >= '0' && c <= '9')|| c == '-')

{

num[i++] = c;

} /*end of else if*/

} /*end of while*/

} /*end of for(n = 0*/

} /*end of for(m = 0*/ }

void PrintRoutData(){

int i, j;

for(i = 0;i < VERNUM;i++)

{

settextstyle(1,0,3);

sprintf(tmp,“ %c”,i + 65);

outtextxy(i*80+50,130,tmp);

outtextxy(10,160+i*40,tmp);

}

for(j = 0;j< VERNUM;j++)

{

for(i = 0;i < VERNUM;i++)

{

if(data[i][j].dis <= 0&&i!=j)

{

if(data[i][j].flag2 ==1)

{

setfillstyle(SOLID_FILL,5);

bar(80*i+50,40*j+155,80*i+120,40*j+185);

delay(50000);

data[i][j].flag2 =0;

}

setfillstyle(SOLID_FILL,3);

bar(80*i+50,40*j+155,80*i+120,40*j+185);

settextstyle(1,0,2);

sprintf(tmp,“-”);

outtextxy(80*i+65,40*j+165,tmp);

}

else

if(data[i][j].dis >=0)

{

if(data[i][j].flag2 ==1)

{

setfillstyle(SOLID_FILL,5);

bar(80*i+50,40*j+155,80*i+120,40*j+185);

delay(50000);

data[i][j].flag2 =0;

}

setfillstyle(SOLID_FILL,3);

bar(80*i+50,40*j+155,80*i+120,40*j+185);

settextstyle(1,0,2);

sprintf(tmp,“%d”,data[i][j].dis);

outtextxy(80*i+65,40*j+165,tmp);

}

} /*end of for(j = 0*/

} /*end of for(i = 0*/ }

void SendInf(int recv, int send){

int i;

for(i = 0;i < VERNUM;i++)

{

if(data[send][i].dis > 0&& data[send][i].flag!=1)

{

if(data[recv][i].dis <= 0&&recv!=i)

{

data[recv][i].dis = data[send][i].dis + data[recv][send].dis;

data[recv][i].flag =1;

data[recv][i].flag2 =1;

}

else if(data[recv][i].dis > data[send][i].dis + data[recv][send].dis)

{

data[recv][i].dis = data[send][i].dis + data[recv][send].dis;

data[recv][i].flag =1;

data[recv][i].flag2 =1;

}

} /*end of if*/

} /*end of for*/ }

void Exchange(){

int i, j;

for(i = 0;i < VERNUM;i++)

{

for(j = 0;j < VERNUM;j++)

{

if(data[i][j].dis > 0&& data[i][j].flag!=1)

{

SendInf(i, j);

} /*end of if*/

} /*end of for(j = 0*/

} /*end of for(i = 0*/ }

四、实验心得体会

通过本次实验训练，我了解了距离矢量路由算法的基本原理，复习了C语言编程的内容，通过对路由算法的实现，加深了对路由表交换的理解。

实验二

一、实验目的及要求

编写程序，联系Socket编程和TCP/IP协议的应用，要求实现Server端和Client端的信息通信。

二、实验原理

在TCP/IP编程中，为客户端和服务器端提供相同的端口号和IP地址号，实现Server端和Client端互联，运用Java文件流的知识，实现两端的信息传递。

三、源程序

/********************ChatClient*********************/ import java.awt.*;import java.awt.event.*;import java.io.*;import java.io.IOException;import java.net.*;

public class ChatClient extends Frame{

Socket s = null;DataOutputStream dos = null;TextField tf = new TextField();TextArea ta = new TextArea();

public static void main(String[] args){ new ChatClient().launchFrame();}

public void launchFrame(){ setLocation(400,300);this.setSize(300,300);add(tf,BorderLayout.SOUTH);add(ta,BorderLayout.NORTH);pack();tf.addActionListener(new tfListener());this.addWindowListener(new WindowAdapter(){

public void windowClosing(WindowEvent e){

disconn();

System.exit(0);

} });setVisible(true);conn();}

public void conn(){ try {

s = new Socket(“127.0.0.1”,5555);

dos = new DataOutputStream(s.getOutputStream());

System.out.println(“客户端连接成功!”);} catch(UnknownHostException e){

e.printStackTrace();} catch(IOException e){

e.printStackTrace();} }

public void disconn(){ try {

dos.close();

s.close();} catch(IOException e){

e.printStackTrace();} }

private class tfListener implements ActionListener {

public void actionPerformed(ActionEvent e){

String str = tf.getText().trim();

ta.setText(str);

tf.setText(“");

try {

dos.writeUTF(str);

dos.flush();

} catch(IOException e1){

e1.printStackTrace();

}

}

} }

/********************ChatServer******************/ import java.io.IOException;import java.net.*;import java.io.*;

public class ChatServer {

public static void main(String[] args){

boolean started = false;

try {

ServerSocket ss = new ServerSocket(5555);

started = true;

while(started){

boolean bConn = false;

Socket s = ss.accept();

bConn = true;

System.out.println(”一个客户端已连接");

DataInputStream dis = new DataInputStream(s.getInputStream());

while(bConn){

String str = dis.readUTF();

System.out.println(str);

}

}

}

dis.close();} } catch(IOException e){ e.printStackTrace();}

四、实验心得体会 通过本次实验的练习，熟悉了TCP/IP协议，对套接字等概念有了深入的了解，对用Java语言实现Socket编程并实现客户端和服务器端的信息交互有了一定的了解。

第三篇：路由协议的常见分类

路由协议的常见分类

网关-网关协议（GGP）

核心网关为了正确和高效地路由报文需要知道Internet其他部分发生的情况，包括路由信息和子网特性。

当一个网关处理重负载而使速度特别慢，并且这个网关是访问子网的惟一途径时，通常使用这种类型的信息，网络中的其他网关能剪裁交通流量以减轻网关的负载。

GGP主要用于交换路由信息，不要混淆路由信息（包括地址、拓扑和路由延迟细节）和作出路由决定的算法。路由算法在网关内通常是固定的且不被GGP改变。核心网关之间通过发送GGP信息，并等待应答来通信，之后如果收到含特定信息的应答就更新路由表。注意GGP的最新改进SPREAD已经用于Internet,但它还不如GGP普及。GGP被称为向量-距离协议。要想有效工作，网关必须含有互联网络上有关所有网关的完整信息。否则，计算到一个目的地的有效路由将是不可能的。因为这个原因，所有的核心网关维护一张Internet上所有核心网关的列表。这是一个相当小的表，网关能容易地对其进行处理。外部网关协议（EGP）

外部网关协议用于在非核心的相邻网关之间传输信息。非核心网关包含互联网络上所有与其直接相邻的网关的路由信息及其所连机器信息，但是它们不包含Internet上其他网关的信息。对绝大多数EGP而言，只限制维护其服务的局域网或广域网信息。这样可以防止过多的路由信息在局域网或广域网之间传输。EGP强制在非核心网关之间交流路由信息。由于核心网关使用GGP,非核心网关使用EGP,而二者都应用在Internet上，所以必须有某些方法使二者彼此之间能够通信。Internet使任何自治（非核心）网关给其他系统发送“可达”信息，这些信息至少要送到一个核心网关。如果有一个更大的自治网络，常常认为有一个网关来处理这些可达信息。

和GGP一样，EGP使用一个查询过程来让网关清楚它的相邻网关并不断地与其相邻者交换路由和状态信息。EGP是状态驱动的协议，意思是说它依赖于一个反映网关情况的状态表和一组当状态表项变化时必须执行的一组操作。

内部网关协议（IGP）

有几种内部网关协议可用，最流行的是RIP和HELLO,另一个协议称为开放式最短路径优先协议（OSPF），这些协议没有一个是占主导地位的，但是RIP可能是最常见的IGP协议。选择特定的IGP以网络体系结构为基础。

RIP和HELLO协议都是计算到目的地的距离，它们的消息包括机器标识和到机器的距离。一般来讲，由于它们的路由表包含很多项，因此消息比较长。RIP和HELLO一直维护相邻网关之间的连接性以确保机器是活跃的。

路由信息协议使用广播技术。意思是说网关每隔一定时间要把路由表广播给其他网关。这也是RIP的一个问题，因为这会增加网络流量，降低网络性能。

HELLO协议与RIP的不同之处在于HELLO使用时间而不是距离作为路由因素。这要求网关对每条路由有合理的准确时间信息。由于这个原因，所以HELLO协议依赖于时钟同步消息。

开放式最短路径优先协议是由Internet工程任务组开发的协议，希望它能成为居于主导地位的IGP.用“最短路径”来描述协议的路由过程不准确。更好一些的名字是“最优路径”,这其中要考虑许多因素来决定到达目的地的最佳路由。

xp系统下载

第四篇：多播路由选择协议

12.7IPX路由选择协议

IPX中使用的两个主要的路由选择协议是RIP（IPX的距离向量协议，IPX’s distance vector protocol）和NLSP（IPX的链路状态协议，IPX’s link state protocol）。维持IPX路径的所有路由选择协议也会维持SAP列表，这样它才能跟踪服务。

IPX RIP与TCP/IP有许多相似之处。它们都可以使用水平分割或毒性逆转来帮助防止路由选择循环和加快会聚时间。它们也都有15个跳数限制，并且都定期发送完整的路由选择表更新，使用60秒钟而不是30秒钟的更新间隔，而且IPX RIP会发送SAP信息以及路由选择信息。IPX RIP公布的额外SAP信息是更新间隔较长的原因所在。

注意：不要混淆TCP/IP RIP和IPX RIP。虽然它们有许多相似之处，但是它们属于两个不同的协议。

直到最近几年，Novell才开始将NLSP作为默认的路由选择协议，而且默认情况下，在支持RIP兼容性的NetWare服务器上也支持NLSP。NLSP是一个链路状态协议，它允许在大型网络上构建分层的区域，就像OSPF和BGP那样。你也可以使用EIGRP来分配IPX路由选择信息，但是因为EIGRP是Cisco专用的，所以你只有在Cisco路由器之间、支持NetWare服务器的网段之间、或者支持RIP或NLSP的NetWare资源之间使用它才能正常工作。NLSP路由器交换诸如连接状态、路由成本、吞吐量、最大数据包（MTU大小）以及通过RIP（外部网络号）了解的网络之类的信息。这种信息在LSP（链路状态数据包）中携带。通过与它的对等路由器交换信息，每一个NLSP路由器都可以构建和维护整个互联网络的逻辑图。因为NLSP是链路状态路由选择协议，所以只有当路由或服务中出现变化时，或者每隔两个小时，哪一个首先出现变化时，NLSP才传输路由选择信息。

第五篇：典型单路径路由协议

典型单路径路由协议

无线传感器网络和Adhoc网络一样，是无线自组织网络的一种，因此，它的路由协议也可以从无线Adhoc网络得到一些启发。本节首先对无线Adhoc网络的路由协议AODV进行研究，详细介绍其路由实现原理。然后详细介绍北京交通大学下一代互联网互联设备国家工程实验室代写计算机职称论文自行研制和开发的路由协议MSRP，MSRP借鉴了AODV的思想，但是又做了很大的简化。本论文所设计的多径路由机制是在MS即的基础上做了创新和改进。本节评价了它的优点和缺点，指出了需要改进的地方。

1.AODV路由协议AODVI’jj(AdhoeOndemandDistanceVectorRouting)是一种按需驱动的路由协议，它能够在移动节点之间建立动态多跳路由并维护一个Adhoc网络。AODV能让节点快速建立到新目的节点的路由，而且不需要节点维护处于非活动状态路径的路由。在链路损坏或者网络拓扑发生变化时，网络中多个移动节点能够及时做出反应，网络能够快速自愈。当网络链路出现断裂时，AODV能够通知所有受影响的节点，让它们及时删除使用该链路的路由。AODV一个很重要的创新点是对每一条路由使用了一个目的序列号，任何一个路由表项必须包含到目的节点的最新的序代写计算机硕士论文列号信息。目的节点序列号由目的节点产生。每一个目的节点在它发送给请求节点的任何路由信息中都会包含这个序列号，使用目的序列号可以保证路由无环路，也利于编程实现。当出现两条路由到达目标节点时，请求节点会选择序列号比较大的路由。节点收到任何有关报文，只要其中有关于目的序列号的信息，该目的节点的序列号就会更新。网络中的节点各自保存和维护自己的序列号。一个目的节点在下列两种情况下产生自己的序列号:

1、在建立一个路由发现之前，它产代写计算机毕业论文生自己的序列号，避免与以前建立的到无线传感器网络路由协议的研究该源节点的反向路由冲突;

2、在产生一个RREP回复双EQ之前，将自己节的序列号更新为目前节点的序列号和路由请求中该节点序列号两者的最大值。下一跳链路丢失时，序列号不再更新。这时候，对于使用该下一跳的每一条路由，节点都将其目的序列号加一，并将该路由标计为失效。只有再次收到“足够新”路由信息时(序列号等于或大于该记录的序列号)，该节点才会将路由表中相应信息更新。AoDv定义了三种报文类型:路由请求(RREQs)、路由回复(RREPs)、路错误(计算机专业职称论文RERRs)。这些消息包装在uDP报文中，端口654，并使用通常的IP报头，请求节点使用自己的IP地址作为路由消息中的“源IP地址”字段。对于广播消息，使用IP广播地址255.255.255.255。这意味着这些消息不会被盲目的转发。但是，AODV确实需要某些报文(例如路由请求消息)能够大范围甚至在整个网络中洪，IP报文的TTL字段可以用来限定传播范围。只要通信的两个端有到对方的有效路由，那么AODV就不参与。当节点需一个到新目的节点的路由时，该节点会广播路由请求进行寻找。当该路由请求达目的节点，或者一个中间节点具有一个到目的节点的“足够新，的路由时，这条路由便可以确定下来。每一个收到路由请求的节点都会缓存一个到源节点的反路由，这样，“路由回复”便会从最终目的节点或者满足请求条件的中间节点顺利递到源节点。节点会监测有效路由下一条链路的状态。当监测到有链路发生断裂时，节会发送路由错误消息来通知其他节点:链路已经丢失，需要重新寻找路由。“路错误”消息用来表明一些节点通过该断裂的链路己经不可达。为了采用这种错误告的机制，所有节点保存一个“前驱列表”，前驱列表包含一些邻居的IP地址，些邻居节点可能使用本节点作为到达目的地的下一跳。前驱列表的信息可以很易的在路由回复的时候获取，因为从定义上来说，“路由回复”就是要发送给前歹J表中的节点的。AODv是个路由协议，因此它有自己的路由表管理机制。即使是暂时的路信息(例如到路由请求源节点的暂时的反向路由)，也需要在路由表中保存。AOD的路由表有以下几个组成部分:目的IP地址、目的序列号、有效目的序列号标以及其他的标志(如有效、无效、可修复、正在修复中)、网络接口、跳数、下跳、前驱列表、生命期(路由表的失效或删除时间)。

1AODV路由建立过程当一个节点发现自己需要路由却不存在路由信息的时候，它发起路由请RREQ，RREQ中的目的节点序列号是从路由表中的目的节点序列号域中拷贝过来的，是最新的。如果序列号未知，那么路由请求报文中U位(未知序列号，表明发送路由请求的节点对目的序列号一无所知)置1。路由请求报文中，源节点序列号是节点自身的序列号，在插入到该路由请求报文中之前会进行加一操作。路由请求ID也是在最新的ID号上面进行加一操作，每一个节点仅仅维护一个路由请求ID。广播路由请求之前，源节点将缓存该路由请求ID和源节点IP地址，这样，当该节点再次收到相同的路由请求时，会忽略该请求，从而避免广播包风暴。类类型型JJJRRRGGGDDDUUU保留留跳数数路路由请求IDDD目目的IP地址址目目的序列号号源源IP地址址源源序列号号路由请求报文格式FigZ一3RREQmessageformat节点收到RREQ之后，首先会创建或者更新到上一跳的路由，然后检查是否在PATHDISCOVERYTIME时间内收到过相同的路由请求。如果收到源IP和请求ID相同的路由请求，那么节点会直接丢弃路由请求。如果收到不同的路由请求，节点增加路由请求报文中的跳数字段，然后节点查询到源节点的反向路由，如果没有，会创建一条路由，如果找到，可能会更新路由表中的序列号。当节点接收到一个传给源节点的路由回复时，报文将沿着反向路由发送到源节点。同时，收到RREQ的中间节点，查看自己的路由表中是否有到目的节点的有效的路由，即路由表中的目的节点的序列号不小于RREQ中携带的序列号;若没有，中间节点更新路由表并向其邻居转发RREQ;若存在到目的节点的路由或该中间节点就是目的节点，将发送RREP报文给源节点，RREP中包含新的目的序列号和路由，转发RREP的节点更新路由表。源节点收到后，就获得了到目的节点的路由。节点在以下两种情况下产生路由回复，节点本身是目的节点;2)节点是中间节点，有到目的节点的路由，该路由有效，并且序列号等于或者大于路由请求报文中的目的序列号。无线传感器网络路由协议的研究类类型型RRRAAA保留留前缀缀跳数数目目的IP地址址目目的序列号号源源IP地址址生生命期期路由回复报文FigZ一4RREpmessageformat如果目的节点产生路由回复，并且路由请求中的序列号等于节点序列号，么节点将增加自己的序列号。目的节点将自己的序列号放入路由回复报文中，将其中的跳数字段设置为O。如果中间节点产生路由回复，那么该节点将把自己知道的目的节点的序列号拷贝到路由回复报文中。同时，中间节点把路由表中该节点到目的节点的跳数拷贝到路由回复的跳数字段中。在路由回复向源节点递的过程中，每经过一个节点，跳数字段加一。源节点与目的节点之间可能需要建立双向通信链路，此时仅仅建立一条从节点到目的节点的路由是不够的，目的节点也需要建立一条反向路由。为此，节点将RREQ中的G位(免费路由回复标志;表明是否需要发送免费路由回复到标IP地址)设为1，这样中间节点就得知源节点需要和目的节点建立双向通信。一般来说，一个节点收到路由请求并且向源节点发送路由回复之后，会直将路由请求报文丢弃。如果路由请求报文中’G’字段被置1，那么中间节点还需向路由请求的目的节点发送“免费路由回复”。免费路由回复从中间节点逐跳传到目的节点，就好像目的节点发起过到源节点的路由请求，中间节点发起了路回复。中间节点接收到路由回复之后，首先会在路由表中查找到上一跳的路由，果没有找到，会创建一条没有有效序列号的路由表项。然后，节点给路由回复跳数字段值加一。如果到目的地址的路由表不存在，节点会建立一条到目的地的路由表项。如果到目的节点的路由表存在，那么中间节点会比较路由表中目序列号和路由回复报文中的序列号，比较之后，更新路由表中的序列号。这样，当前节点就可以用这条路由来转发到目的节点的数据包。如果当前点不是路由请求的源节点，那么节点转发该路由回复到去往路由请求源节点的一跳。节点发送路由回复时，到目的地的前驱列表也被更新，即把路由回复的一跳节点放入到前驱列表中。AODV路由维护过程节点通过广播本地HELLO消息来提供链路的链接信息。每次经过HELLOINTERVAL时间间隔，节点检查自己在这段时间内有没有发过广播包，如果没有发过，则发送一个TTL值为1的HELLO报文。节点可以通过监听从邻居发来的HELLO数据包来确定链路连接性。如果规定的时间内，节点收到邻居的HELLO报文，经历一段时间后再也没有收到该邻居发来的任何信息，那么节点会认为该邻居节点已经失效。每次节点收到来自邻居的HELLO报文，节点应该确保自己有一条到邻居的路由。如果没有的话要创建路由，如果有的话需要更新生命期。当节点检测到路由回复失败后，会将这样的节点放入到黑名单中。检测的方式可以采用链路层或者网络层的ACK。节点在经过规定的时间后会从黑名单列表中清除。一般来说，路由错误和链路断裂的处理需要一下几个步骤:l)将已有的路由表项设为无效2)列出所有受影响的路由3)决定哪一个邻居节点可能受到影响4)将合适的路由错误消息发送给相应的邻居节点路由错误消息可以多种方式传播。前驱节点个数很多情况下，一般采用广播的形式，如果前驱节点只有一个，可采用单播，如果不适合采用广播，可以依次单播到每一个前驱节点。类类型型NNN保留留不可达目的节点序列号号不不可达目的节点IP地址址不不可达目的节点序列号号其其他不可达目的节点IP地址址其其他不可达目的节点序列号路由错误报文FigZ一5RERRmessageformat节点在以下情况下会发送路由错误消息:l)在利用有效路由发送数据时检测到下一跳失效，此时，节点在自己的路由表中搜寻所有利用下一跳的路由表项;无线传感器网络路由协议的研究2)收到一个数据包，但路由表中没有相应的路由;3)收到邻居的路由错误消息。对于第一种情况，节点会搜索路由表，列出所有因为邻居失效而不可达的终目的节点。对于第二种情况，只有一个最终目的节点不可达，即数据包的最地址。对于情况三，节点也会搜索路由表，当找到邻居节点为下一跳路由时也将其加入列表。列表中的一些不可达地址可能会被邻居节点使用，因此必要时向邻居发送路由错误消息。当一条链路断裂时，如果到目的节点的跳数不超过上限，断裂的上游节点以采取本地修复的策略。节点先缓存数据包，然后把该不可达目的序列号加一，发起到该目的节点的路由请求，节点会一直等待路由回复。如果本地修复没有功，那么节点将发送路由错误消息。本地修复可能引起到目的节点的路径比较长而且可能会增加传送到目的节点的数据包的数量，因为当发送路由错误消息时，数据包是不会被丢弃的。本地修复之后再发起路由错误消息可能会让源节点找更好的路径。

2.MSRP路由协议MSRp(MieroSensorRoutingprotoeol)是北京交通大学下一代互联网互联备国家工程实验室自主开发的微型传感路由器路由协议，能够结合传感器网络特点，实现动态、自组织地寻路和数据转发。由于MS砂是一种单路由策略，某些扩展应用过程中需要解决减少路由失效带来的数据延迟和基于按需选路导的能量消耗不均匀的问题。因此，本文需要在MSRP的基础上提出一种多路径由机制，在此给出MSRP工作过程的简要描述。MSRP路由建立过程MSRP路由协议为了减少存储表项以及发送和接收报文的大小，MSRP使IEEE802定义的64比特接口标识符，而不是IPv6地址进行路由过程，IP地址根据地址映射规则，由唯一的IEEE802.15.4定义的64比特接口标识符进行定。因此IPv6微型协议栈可以根据MSRP建立的路由进行数据传输。MSRP是一个简单的单路径路山协议，路由发现时，MSRP用广播，为了广RREQ分组，通过设置目的地址为广播短地址(oxFFFF)来获得广播包。Ms不支持中间节点回复RREP分组，只允许目的节点回复RREP分组。同时，它持中间节点选择性地广播路由请求(RREQ)，当发现自己有到目的节点的路由就不再广播RREQ分组，而是选择单播双EQ分组到路由表中到目的节点的下一跳节点。当节点要发送数据包却没有到目的节点的路由信息时，节点缓存数据包，发起路由查询过程，广播路由请求报文。路由请求报文(RREQ)包括目的地址、源地址、路由请求ID、跳数等。路由请求ID和源地址用于唯一标识一个RREQ。每个节点维护一个入口表用于一记录其它节点来的RREQ，入口表包括源地址和路由请求ID。当中间节点收到RREQ时，先查找入口表，如果是第一次收到该RREQ分组，则插入入口表，如果已经有相关的入口表项，则丢弃RREQ。如果第一次收到该RREQ，则查找路由表，如果有到目的节点的路由信息，则单播RREQ到路由表中下一跳节点，如果没有路由信息，就继续广播RREQ，直到目的节点。在RREQ传送到目的节点的过程中，节点建立到源节点的反向路由，这样RREP可以沿着反向路由到达源节点。当目的节点收到RREQ时，首先节点缓存RREQ分组消息，由于广播RREQ寻路过程，节点接收到多条路由发送的分组消息，所以需要等待合理时间T，进行判断多路由的优劣，这里构造了一个最优路由判断函数f(X，Y):f(X，Y)=Am+Bh+Cn…(公式l)其中m为源节点到目的节点经过的电量不足节点的个数，h为源节点到目的节点的跳数，n为从源节点到目的节点弱链路的条数。A、B、C为不同网络环境下的待定参数，均为2的非负整数次方，并满足A>>C>B。在开阔地带室外网络环境下，取A=256，B=l，C=20目的节点为每个到达的RREQ以及当前节点到达RREQ源节点的路由(如果路由表中存在的话)计算其f值，跳数X值越小并且链路质量值越大，则f值越高，选择f值最大的路由进行回复。路由回复报文(RREP)包括源节点、目的节点以及跳数。建立到目的节点的路由，然后查找到节点反向路由，转发RREP。若发送RREQ的源节点收到RREP，则发送数据。这样由建立过程就完成了。MSRP也进行简单的路由修复。当链路出现故障时，发送路由错误报文(RER给链路的上一跳节点。同时执行以下步骤:l)将直接相关的路由设为无效路由;2)统计所有受影响的路由目的节点;3)统计所有受影响的邻居节点;4)向受影响的邻居发送RERR消息。建建立到目的节节点点的路由由发发送数据据据查找到源节点的的路路路路由，转发RREPPP节点收到RREP流程图FigZ一7FlowehartofnodesreeeivingRREP2.2.3AODV和MSRP的评价AoDv*”+是一种基于距离矢量的按需路由协议。协议采用了三种报文格式RREQ、RREP、RERR，它们的结构比较复杂。还使用了序列号避免环路和HELLo消息来检测链路的连接性。AODV支持中间节点应答，能使源节点快速获得路