工程碩士班《通信網(wǎng)理論基礎》

1、l圖 G(V,E) 由兩個集合加以定義: 頂點 (或節(jié)點) 集合 V= v1,v2,v3.vn ; 邊集合 E=e1,e2,e3em ; G=V, E l邊由一對直接關連的頂點的組合定義 如果: (i,j) E,則頂點i和 j稱為相鄰的 頂點的數(shù)目稱為圖的“階”;邊的數(shù)目稱為圖的“尺寸”; 許多圖的算法的運行時間與圖的“階”和“尺寸”相關l鄰接矩陣是用數(shù)學方式來表示圖l頂點編號: 1,2,3,|V|l|V| x |V| 鄰接矩陣 A=(ai,j) 定義為: ai,j = 1 if (i,j) E (ij是圖的一條邊) 0 otherwisel對于邊沒有方向性的圖(即邊的兩頂點的順序不影響邊的性

2、質),鄰接矩陣A是對稱矩陣.l關聯(lián)同一對頂點的邊稱為: 平行邊l關聯(lián)同一頂點的邊稱為: 環(huán)l既無平行邊,又無環(huán)的圖稱為: 簡單圖l頂點 i 到頂點 j的路徑是: 頂點和邊的交替序列起于i,止于j; 每條邊只與序列中直接在它前面和直接在它后面的頂點相連 簡單路徑 : 頂點和邊在序列中只出現(xiàn)一次的路徑 l在簡單圖中,簡單路徑可以由頂點序列來定義 每個頂點與序列中在其前面和后面的頂點相鄰 序列中沒有重復的頂點l由V1 到 V6 (不完全) V1,V2,V3,V4,V5,V6 V1,V2,V3,V5,V6 V1,V2,V3,V6 V1,V2,V4,V3,V5,V6 V1,V2,V4,V5,V6 V1,

3、V3,V2,V4,V5,V6 V1,V3,V6 V1,V4,V3,V6l總共14條(其余的請自行列出)l兩頂點間的所有路徑中有一條最短路徑,如:V1,V3,V6l頂點間的距離是所有路徑中邊數(shù)最少的路徑的邊的數(shù)目l回路是起于和止于同一頂點的路徑 例如:. V1,V3,V4,V1l邊有方向性的圖l有向圖 G(V,E) 的邊由一對頂點的有序組合來定義l代表邊的線段用箭頭表示其方向l允許存在平行邊,只要它們的方向相反l便于用圖表示通信網(wǎng)絡 每條有向邊表達一個方向上的數(shù)據(jù)流l仍然可用鄰接矩陣表示 除非每對相鄰的頂點用平行邊連接,否則鄰接矩陣是不對稱的l或加權有向圖l每條邊有一與之關聯(lián)的數(shù)(權值w)-便于

4、說明路由算法l鄰接矩陣定義為: ai,j = wi,j if (i,j) E 0 otherwisewi,j 是與邊( i, j )關聯(lián)的權值l路徑長度是權值之和l最短距離路徑不一定是長度最短路徑(見下面兩張PPT)路徑 距離 長度V1,V2,V3,V4,V5,V6511V1,V2,V3,V5,V648V1,V2,V3,V6310V1,V2,V4,V3,V5,V6510V1,V2,V4,V5,V647V1,V3,V2,V4,V5,V6516V1,V3,V6210V1,V4,V5,V634l樹是圖的子集l以下幾項定義是等效的: * 樹是一種簡單圖,頂點i 和 j 之間只有一條簡單路徑 * N個頂

5、點的簡單圖如果只有N-1 條邊,沒有回路 * N個頂點的簡單圖如果只有N-1條邊,而且是連通的l可以指定一個頂點為“根” 根通常畫在上部 與根鄰接的頂點畫在下一層l這些頂點可以到達樹根,路徑距離為1l每個頂點(除根外)有一個父頂點 靠根一邊的鄰接頂點l每個頂點有0個或幾個子頂點 離根遠的鄰接頂點 沒有子頂點的頂點稱為葉l層次等級 直接在根下面的頂點是第一層 第一層頂點的子頂點是第二層l從圖G中選擇一些邊和頂點構成G的子圖 每條被選上的邊的兩個關聯(lián)頂點必須同時選上l圖 G(E,V) 是圖G(E,V) 的子圖,如果: V V , E E 并且對每一條E中的邊e.如果 e 關聯(lián) v and w, 則

6、 v, w Vl圖G的子圖T是一顆生成樹,如果: T 是樹 包含G的所有頂點l從圖G中刪去一些邊,使所有的回路不復存在,但保持圖的連通性:l圖G的生成樹通常并不唯一l將頂點劃分成不同的層次l在處理下一層之前,先處理完本層的所有頂點l從任一頂點x 開始l指定它為0層 所有它的鄰接頂點屬于1層 設 Vi1, Vi2, Vi3, Vij,是 i層的頂點 所有Vi1 的鄰接頂點中不屬于1,2,i層的頂點指定為(i+1)層 所有Vi2的鄰接頂點中不屬于1,2,3,i, (i+1)層的頂點也指定為(i+1)層 直到所有頂點被處理完畢l選擇頂點順序 如: V1,V2,V3,V4,V5,V6l選擇“根” 例如

7、 V1l現(xiàn)在樹T只包含一個頂點V1 ,不含邊l在樹上增加邊(V1,x) 和頂點x, 但不要形成回路:將邊 (V1,V2), (V1,V3), (V1,V4) 和頂點 V1,V2, V3加入到樹中,這是第一層l在第一層的頂點上按序重復上述過程,得到第二層 是否所有頂點都處理完? 如果沒有,在第二層的頂點上重復處理過程,得到第三層.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)Select a root bridge among all the bridges. root bridge = the low

8、est bridge ID.Determine the root port for each bridge except the root bridge root port = port with the least-cost path to the root bridgeSelect a designated bridge for each LAN designated bridge = bridge has least-cost path from the LAN to the root bridge. designated port connects the LAN and the de

9、signated bridge All root ports and all designated ports are placed into a “forwarding” state. These are the only ports that are allowed to forward frames. The other ports are placed into a “blocking” state.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)

10、(1)(1)(1)(2)(2)(2)(2)(3)Bridge 1 selected as root bridgeLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Root port selected for every bridge except root portRRRRlBFS算法可以得到從根頂點s到所有其他頂點的最短距離路徑和距離 (s,v) l任何從s 到v 的路徑中BFS給出的路徑是距離最短的,即該路徑邊數(shù)之和最小。l分組交換,幀中繼,ATM等網(wǎng)絡可以看作一張圖 每個節(jié)點是圖中一頂點 每一鏈路是一對平行邊l對于互聯(lián)網(wǎng)

11、(Internet 或 intranet) 每個路由器是一個頂點 如路由器直接相連,雙向連接相當于一對平行邊 如多于兩個路由器,則由多對平行邊構成表示網(wǎng)絡的圖 一對邊連接一對路由器l為將分組由源送到目的,需要路由決策 等效于在圖上找出路徑l基于最小代價 最少跳數(shù)( hop )l每條邊(一跳)的權重為1 l相當于最短距離路徑 或者, 每跳有一相關聯(lián)的代價(見下一PPT) 路徑的代價是路徑中各鏈路的代價之和 需要找出最小代價路徑l相當于加權圖中的最小長度路徑l反比于路徑的容量l正比于當前的負荷l鏈路的貨幣價值l幾種因素的組合l在不同方向上的代價可能不同lN = 網(wǎng)絡頂點的集合ls = 源頂點 (

12、起始點 )lT = 到目前為止算法已經(jīng)用到的頂點的臨時集合lTree = T中頂點組成的生成樹,它包括從s到T中每個頂點的最小代價路徑上的邊lw(i,j) = 從頂點i 到頂點 j的鏈路代價, w(i,i) = 0 w(i,j) = if i, j 不直接連接 w(i,j) 0 if i,j 直接連接lL(n) = 當前知道的從s到n的最小代價路徑的代價cost 運算結束是它就是從s到n的最小代價路徑的代價l初始化lT = Tree = s 臨時頂點集合中暫時只含源頂點lL(n) = w(s,n) for n s ; 到鄰點的初始路徑代價就是鏈路代價l取下一個頂點l找 x T 使 L(x) =

13、 min L(j), j Tl將 x 加入到 T 和 Tree 中l(wèi)將關聯(lián)x,且使L(x) 成為最小代價的邊加入到Tree中l(wèi)它是路徑的最后一跳l更新最小代價路徑lL(n) = minL(n), L(x) + w(x,n) n Tl如果后一項最小,從s到n的路徑就是從s到x的路徑與從x到n的邊的連接整理ppt34TSNXnw(x, n)L(n)L(x)已算出最短路徑的點的集合找 x T 使 L(x) = min L(j), j Tl x TL(n) = minL(n), L(x) + w(x,n) n T所以，S需要知道w(x,n)-各點與其鄰點間直接相連鏈路的代價因而需要與所有其他各點交換路

14、由信息某點（s) 已知網(wǎng)絡中其他各點到其鄰點的鏈路的代價值w(x,n), 計算S到其他各點的最短路徑l當所有頂點都加入到T以后,算法結束l需要 |V| 次迭代l結束時 L(x) 是s 到 x 的最小代價路徑的代價值 Tree 是原圖的一顆最小生成樹l定義了從s到其他頂點的最小代價路徑l每次迭代有一個新的頂點加入到T中,運行時間是 |V|2 量級ls = 源頂點(起始點)lw(i,j) = 從頂點i 到頂點 j 的鏈路的代價值 w(i,i) = 0 w(i,j) = 如 i, j 不直接相連 w(i,j) 0 如 i,j 直接連接lh = 在算法的當前步驟中路徑的最大鏈路數(shù)lLh(n) = 從頂

15、點s 到 n 的最小代價路徑的代價,限制條件是路徑的鏈路數(shù)不超過hl初始化lL0(n) = n slLh(s) = 0 hl更新l對每個相繼的 h 0l對每個n s, 計算: Lh+1 (n) = minLh(j)+ w(j,n), jl找到實現(xiàn)最小值的頂點jl,將n與該前趨頂點j相連,l刪除n與此前計算得到與j不同的前趨頂點的連接,l從s到n的路徑以j到n的鏈路結束l結果與 Dijkstra 算法的結果相同l運行時間是 |V| x |E| 的量級整理ppt40Sn已知 n 與其鄰點間鏈路的代價值w(j,n); j 到s 的最短路徑的代價值L(j); 找n 到s的最短路徑；jl對每個n s,

16、計算: Lh+1 (n) = minLh(j)+ w(j,n), jw(j,n)（已知，因為與n直連）L(n)L(j)n點在計算時需知其鄰接點的L(j)當前估計的到S的最短路徑的長度，和它到自己的鄰點的鏈路的代價值，所以為了求出到所有點的最短路徑，每點需與其鄰接點交換各自到所有其他點的最短路徑長度的當前估計值l頂點n處的計算需要知道到所有鄰接點的鏈路的代價,以及從源點到這些點的路徑的總代價el每個頂點需要維持一個到網(wǎng)絡中所有其他頂點的路徑及其代價的表l與其直接鄰接頂點交換上述信息l每個頂點都用Bellman-Ford 算法步驟 2 中的表達式更新其路徑與代價表l步驟 3 要求每個頂點知道網(wǎng)絡拓

17、撲的完整信息,因而: 必須知道網(wǎng)絡中所有鏈路的代價值 每個頂點必須與所有其他頂點交換信息l究竟哪個算法好,需要考慮算法的運行時間等其他因素l當網(wǎng)絡拓撲和鏈路代價處于準靜態(tài)時,兩種算法都收斂l給出相同的結果l如果鏈路代價變化,算法會企圖跟上這種變化l如果鏈路代價與通信流量有關,而后者又與路由選擇有關,則: 存在反饋 可能產生不穩(wěn)定lGlobal Internet viewed as collection of autonomous systems. lAutonomous system (AS) is a set of routers or networks administered by a

18、single organization lSame routing protocol need not be run within the ASlBut, to the outside world, an AS should present a consistent picture of what ASs are reachable through itlStub AS: has only a single connection to the outside world. lMultihomed AS: has multiple connections to the outside world

19、, but refuses to carry transit trafficlTransit AS: has multiple connections to the outside world, and can carry transit and local traffic.lFor exterior routing, an AS needs a globally unique AS 16-bit integer numberlCurrently, there are about 11,000 registered ASs in Internet (and growing)lStub AS,

20、which is the most common type, does not need an AS number since the prefixes are placed at the providers routing tablelTransit AS needs an AS numberlRequest an AS number from the ARIN, RIPE and APNICRRRRRRRRAS AAS BAS CIGPEGPIGPIGPInterior Gateway Protocol (IGP): routing within AS RIP, OSPFExterior

21、Gateway Protocol (EGP): routing between ASs BGPv4Border Gateways perform IGP & EGP routinglBasic RoutinglRouting Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)lRFC 1058lRIP based on routed, “route d”, distributed in BSD UNIXlUses the distance-vector algo

22、rithmlRuns on top of UDP, port number 520lMetric: number of hopslMax limited to 15 suitable for small networks (local area environments) value of 16 is reserved to represent infinity small number limits the count-to-infinity problem lRouter sends update message to neighbors every 30 seclA router exp

23、ects to receive an update message from each of its neighbors within 180 seconds in the worst caselIf router does not receive update message from neighbor X within this limit, it assumes the link to X has failed and sets the corresponding minimum cost to 16 (infinity)lUses split horizon with poisoned

24、 reverse lConvergence speeded up by triggered updates neighbors notified immediately of changes in distance vector table lRouters run RIP in active mode (advertise distance vector tables)lHosts can run RIP in passive mode (update distance vector tables, but do not advertise)lRIP datagrams broadcast

25、over LANs & specifically addressed on pt-pt or multi-access non-broadcast netslTwo RIP packet types: request to ask neighbor for distance vector table response to advertise distance vector tablelperiodically; in response to request; triggeredCommand Version ZeroAddress family identifier ZeroIP a

26、ddressZeroZeroMetric0 8 16 31. . .Request/Response1/22 for IPRIPentryUp to 25 RIP entries per messagelCommand: request or responselVersion: v1 or v2lOne or more of: Address Family: 2 for IP IP Address: network or host destination Metric: number of hops to destinationlDoes not have access to subnet m

27、ask informationlCannot work with variable-length subnet masksRIP v2 (RFC 2453):lSubnet mask, next hop, routing domainlcan work with CIDRlstill uses max cost of 16lBasic RoutinglRouting Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)lUsed in OSPF to distribute

28、 link state (LS) informationlForward incoming packet to all ports except where packet came inlPacket eventually reaches destination as long as there is a path between the source and destinationlGenerates exponential number of packet transmissionslApproaches to limit # of transmissions: Use a TTL at

29、each packet; wont flood if TTL is reached Each router adds its identifier to header of packet before it floods the packet; wont flood if its identifier is detected Each packet from a given source is identified with a unique sequence number; wont flood if sequence number is same10.5.1.110.5.1.310.5.1

30、.510.5.1.210.5.1.410.5.1.6At steady state: lAll routers have same LS databaselKnow how many routers in networklInterfaces & links between routerslCost of each linklOccasional Hello messages (10 sec) & LS updates sent (30 min)lTo improve scalability, AS may be partitioned into areas Area is i

31、dentified by 32-bit Area ID Router in area only knows complete topology inside area & limits the flooding of link-state information to area Area border routers summarize info from other areaslEach area must be connected to backbone area (0.0.0.0) Distributes routing info between areaslInternal r

32、outer has all links to nets within the same arealArea border router has links to more than one arealbackbone router has links connected to the backbonelAutonomous system boundary (ASB) router has links to another autonomous system. ASB: 4ABR: 3, 6, and 8IR: 1,2,7BBR: 3,4,5,6,8Area 0.0.0.1Area 0.0.0.

33、2Area 0.0.0.3R1R2R4R5R7N1N2N3N4N5N6N7To another ASArea 0.0.0.0R = router N = networkR8R3R6lNeighbor routers: two routers that have interfaces to a common network Neighbors are discovered dynamically by Hello protocollEach neighbor of a router described by a state down, attempt, init, 2-way, Ex-Start

34、, Exchange, Loading, FulllAdjacent router: neighbor routers become adjacent when they synchronize topology databases by exchange of link state information Neighbors on point-to-point links become adjacent Routers on multiaccess nets become adjacent only to designated & backup designated routersl

35、Reduces size of topological database & routing trafficlReduces number of adjacencieslElected by each multiaccess network after neighbor discovery by hello protocollElection based on priority & id fieldslGenerates link advertisements that list routers attached to a multi-access networklForms

36、adjacencies with routers on multi-access networklBackup prepared to take over if designated router failslLink state info exchanged by adjacent routers to allow area topology databases to be maintained inter-area & inter-AS routes to be advertisedlRouter link ad: generated by all OSPF routers sta

37、te of router links within area; flooded within area onlylNet link ad: generated by the designated router lists routers connected to net: flooded within area onlylSummary link ad: generated by area border routers 1. routes to dest in other areas; 2. routes to ASB routerslAS external link ad: generate

38、d by ASB routers describes routes to destinations outside the OSPF net flooded in all areas in the OSPF netlOSPF packets transmitted directly on IP datagrams; Protocol ID 89lTOS 0, IP precedence field set to internetwork control to get precedence over normal trafficlOSPF packets sent to multicast ad

39、dress 224.0.0.5 (allSPFRouters on pt-2-pt and broadcast nets)lOSPF packets sent on specific IP addresses on non-broadcast netslFive OSPF packet types: Hello Database description Link state request; Link state update; Link state acklType: Hello, Database description, Link state request, Link state up

40、date, Link state acknowledgements Version Type Packet lengthRouter IDArea IDChecksum Authentication typeAuthenticationAuthentication0 8 16 31OSPFcommonheaderOSPFpacketbodyDatalDiscover neighbors by sending Hello packets (every 10 sec) and designated router elected in multiaccess networkslAdjacencies

41、 are established & link state databases are synchronizedlLink state information is propagated & routing tables are calculatedWe elaborate on OSPF stages in followinglHello interval: number of seconds between Hello packetslPriority: used to elect designated router & backuplDead interval:

42、# sec before declaring a non-responding neighbor down.lNeighbor: the Router ID of each neighbor from whom Hello packets have recently been receivedlSend Hello packets to establish & maintain neighbor relationship Network maskHello interval Options Priority0 16 24 31Dead intervalDesignated router

43、Backup designated routerNeighbor 1Neighbor n. . .lInit bit 1 if pkt is first in sequence of database description packetslMore bit 1 if there are more database description packets to followlMaster/Slave bit indicates that the router is the master. lLink state ad (LSA) header describes state of router

44、 or network; contains info to uniquely identify entry in LSA (type, ID, and advertising router).lCan have multiple LSA headers lOnce neighbor routers become adjacent, they exchange database description packets to synchronize their link-state databases. Interface MTU Options Zero I MDatabase Description Sequence Number0 16 24 29 31LSA HeaderMSlLS type: Router LSAs generated by all OSPF routers; Network LSAs generated by designated routers; Summary LSAs by area border routers; AS-external LSAs by ASBRslLS id: i