文档介绍：动态路由主讲人:中山大学软件研究所李磊教授一前言近年来,中国的电信网络建设飞速发展,无论从规模上和装备上都达到或接近国际先进水平,但这才仅仅是完成了中国电信网络建设的第一步,同时也是最容易的一步。如何充分地发挥这些先进设备的能力,进一步增加效益是电信部门十分迫切的任务,也是一项比网络建设更困难的任务。中国电信网络的进化经过了同西方发达国家基本相似的过程,由分级网络向无级网络和由部分连通到全连通的进化过程。尤其是在经济较发达的广东省,已经逐步完成了分级网向无级网的进化,并且网中所有的节点都是全联通的。这些都为进一步提高网络管理水平和进一步发挥设备能力奠定了基础。动态路由是目前少数发达国家研究和采用的先进的电信网络管理的技术。由于他们采用了这项技术,使得他们的电信网络可靠性得到增加,接通率提高,信息交换的费用降低,更能适应当今新业务层出不穷的需要,同时由于服务质量的改善,吸引了更多的新客户。总之,采用这项技术可大大地提高网络的经济效益。中国是一个幅员辽阔和电信用户众多的国家。如果在我国成功的研制和采用这项技术,将会带来难以计算的经济效益。因此,我们提出此项研究的中心内容之一就是充分利用广东的现有条件,研制出适合广东省电信网络环境的动态路由系统。国内外研究情况西方发达国家从80年代起开始研究动态路由,例如美国AT&T在1987年在美国长途网中实现了动态路由。虽然选路策略十分初等(DNHR,on-HierarchicalRouting),但是他们仍旧取得了相当成功的经济效益。1991年他们又研究成功了更先进的选路策略(RTNR,workRouting),进一步改善了网络性能,带来更大的经济效益。加拿大也是电信发达的国家之一。加拿大北方电信(NT)也提出了他们的选路策略(DCR,DYNAMICALLYCONTROLLEDROUTING)并且取得了同样的成功。目前,NT已将此项技术在世界范围推广。还值得一提的是英国也研究出了一种非常简单但有效的动态路由方法(DAR,DynamicAlternateRouting)。虽然DAR是一种局部优化方法但十分有效。我国则晚至1987年才开展对电话网无级动态路由的研究。从我们能够查到的文献来看,国内在这方面的研究基本上处于学****理解和分析各种模型的阶段。虽然,人们已经认识到了研究和实现动态路由的重要性和必要性,但是迄今还没有得到令人满意的结果。三系统研究目标与研究内容研究出适合于广东省电信网络基础的动态路由算法。算法应具有适用性、有效性和先进性。研制出动态路由系统。系统应具有实用性、易用性和灵活性。采用全局性优化算法。:电话网络由n个交换机组成,每对交换机之间是若干条中继(可能为0)组成的直达电路。交换机与电路构成电话网络。例如:AcbBCa其中,A,B,C表示交换机,a,b,c表示直达电路。交换机i到j的中继数量用Lineij表示。每一个交换机有一定的容量,交换机i的容量用Capi表示,所以电话网的静态结构可以表示如下:=(CAP,LINE)CAP=(Capi)nLINE=(Lineij)n×nS1S2……Snline210line12S2S1……0Sn矩阵LINE表示两个交换机Si,Sj之间的电路数Linei,j+1,短阵CAP表示交换机的处理能力,例如:总的电路数。[Cap1……Capn]话务:每对交换机之间需要通过的话务流量,单位是爱尔兰。话务量可以用一个矩阵表示如下:TRAF=(Trafficij)n×n同理可以定义S→S之间的话务量Traffic。路由:从交换机i到j的话务,如果超过i、j间直达电路能承受的话务量,就会产生话务溢出,此时需为溢出话务选择一迂回路由节点。需要选择的路由共有n(n-1)个,可以一路由矩阵表示如下(其中Routeii没有意义,可设为0):ROUTE=(Routeij)n×nS1S2……Sn0S40SiSn……S1S2目标矩阵ROUTE,固定路由,意为ROUTE矩阵是不变的。目前是手工调整,也就是调整这个矩阵。对固定选路策略来说,迂回路由是固定的。动态路由要解决的问题是根据当前的状态(每一个选择都是一个状态),网络静态结构和最近一段时间的话务流量,动态确定下一时刻每两个交换机之间的迂回路由,以使得网络的总的话务阻塞率最小。我们可以理解为有一个n×n的棋盘:A1A2A3A4An-1AnA1A2A3A4An同时把A1……An看作是不同颜色的棋子。这n-1种颜色不能包括Ai和Aj的颜色在棋盘的对角线上不准摆上棋子(自己到自己不需要迂回)。在棋盘的其它地方只能摆n-1种颜色的棋子(表示不同的迂回节点)。每一种不同的摆法就是一个方案。一共有多少种方案?在其中那一个是最好的方案?,事实上不存在有效的