工程硕士班《通信网理论基础》(2).ppt

通信网理论基础第三部分图论基础与应用基本概念图的一个例子图的邻接矩阵邻接矩阵一例Terminology简单路径(1)简单图(2)有向图加权图加权图与邻接矩阵V1至V6的路径距离和路径长度树树中顶点的等级关系树的例子图生成树生成树的“先广搜索”算法例上例的图示AvoidingLoopsAvoidingLoopsSpanningTreeAlgorithmLAN1LAN1LAN1最短距离路径的距离最短长度路径路由决策一跳的代价Dijkstra算法(1)–定义Dijkstra算法(2)–步骤Dijkstra算法原理图示Dijkstra’s算法(3)–说明Dijkstra算法用于例图Bellman-Ford算法(1)–定义Bellman-Ford算法(2)–步骤Bellman-FordAlgorithm(3)–说明Bellmin-Ford算法原理图示Bellman-Ford算法用于例图Dijkstra和Bellman-Ford算法的运算结果比较所需要的信息–Bellman-Ford算法比较两种算法所需要的信息-------------Dijkstra算法其他事项AutonomousSystemsASNumberInterandIntraDomainRoutingOutlineRFC1058
RIPbasedonrouted,“routed”,distributedinBSDUNIX
Usesthedistance-vectoralgorithm
RunsontopofUDP,portnumber520
Metric:numberofhops
Maxlimitedto15
suitableforsmallnetworks(localareaenvironments)
valueof16isreservedtorepresentinfinity
smallnumberlimitsthecount-to-infinityproblemRIPOperationRIPProtocolCommand:requestorresponse
Version:v1orv2
Oneormoreof:
AddressFamily:2forIP
IPAddress:networkorhostdestination
Metric:numberofhopstodestination
Doesnothaveaccesstosubnetmaskinformation
Cannotworkwithvariable-lengthsubnetmasks
RIPv2(RFC2453):
Subnetmask,nexthop,routingdomain
canworkwithCIDR
stillusesmaxcostof16OutlineUsedinOSPFtodistributelinkstate(LS)information
Forwardincomingpackettoallportsexceptwherepacketcamein
Packeteventuallyreachesdestinationaslongasthereisapathbetweenthesourceanddestination
Generatesexponentialnumberofpackettransmissions
Approachestolimit#oftransmissions:
UseaTTLateachpacket;won’tfloodifTTLisreached
Eachrouteraddsitsidentifiertoheaderofpacketbeforeitfloodsthepacket;won’tfloodifitsidentifierisdetected
Eachpacketfromagivensourceisidentifiedwithauniquesequencenumber;won’tfloodifsequencenumberissameExampleOSPFTopologyToimprovescalability,ASmaybepartitionedintoareas
Areaisidentifiedby32-bitAreaID
Routerinareaonlyknowscompletetopologyinsidearea&limitsthefloodingoflink-stateinformationtoarea
Areaborderrouterssummarizeinfofromotherareas
Eachareamustbeconnectedtobackbonearea(0.0.0.0)
Distributesroutinginfobetweenareas
In