172Principles原理

1、computer networkchapter 11:packet switching分組交換分組交換principles:原理原理zcircuit switching designed for voiceyresources dedicated to a particular callymuch of the time a data connection is idleydata rate is fixedxboth ends must operate at the same ratebasic operation:基本操作基本操作zdata transmitted in small pac

2、ketsytypically 1000 octetsylonger messages split into series of packetsyeach packet contains a portion of user data plus some control infozcontrol infoyrouting (addressing) infozpackets are received, stored briefly (buffered) and past on to the next nodeystore and forwarduse of packets：使用分組使用分組advan

3、tages：優(yōu)點優(yōu)點z line efficiency：線路效率ysingle node to node link can be shared by many packets over timeypackets queued and transmitted as fast as possiblez data rate conversion：數(shù)據(jù)率匹配yeach station connects to the local node at its own speedynodes buffer data if required to equalize ratesz packets are accep

4、ted even when network is busyydelivery may slow downz priorities can be used：優(yōu)先級的使用switching technique:交換技術(shù)交換技術(shù)zstation breaks long message into packetszpackets sent one at a time to the networkzpackets handled in two waysydatagram：數(shù)據(jù)報yvirtual circuit：虛電路datagram：數(shù)據(jù)報數(shù)據(jù)報zeach packet treated independe

5、ntlyzpackets can take any practical routezpackets may arrive out of orderzpackets may go missingzup to receiver to re-order packets and recover from missing packetsdatagram approachdatagram approach,multiple channelsvirtual circuit：虛電路虛電路zpreplanned route established before any packets sentzcall req

6、uest and call accept packets establish connection (handshake)zeach packet contains a virtual circuit identifier instead of destination addresszno routing decisions required for each packetzclear request to drop circuitznot a dedicated pathswitch virtual circuitswitched virtual circuitswitched virtua

7、l circuitvirtual circuits v datagramzvirtual circuitsynetwork can provide sequencing and error controlypackets are forwarded more quicklyxno routing decisions to makeyless reliablexloss of a node looses all circuits through that nodezdatagramyno call setup phasexbetter if few packetsymore flexiblexr

8、outing can be used to avoid congested parts of the networkpacket size分組大小分組大小傳輸時間傳輸時間data:40header:3circuit v packet switchingzperformanceypropagation delay:傳播時延ytransmission time:傳輸時間ynode delay:節(jié)點時延event timing 電路交換電路交換 虛電路分組交換虛電路分組交換 數(shù)據(jù)報分組交換數(shù)據(jù)報分組交換節(jié)點節(jié)點呼叫呼叫請求請求信號信號呼叫呼叫請求請求信號信號呼叫呼叫接受接受信號信號呼叫呼叫接受接受信

9、號信號傳播時傳播時延延處理時處理時延延應答信號應答信號應答信號應答信號用戶數(shù)據(jù)用戶數(shù)據(jù)external and internal operationzpacket switching - datagrams or virtual circuitszinterface between station and network nodeyconnection orientedxstation requests logical connection (virtual circuit)xall packets identified as belonging to that connection &

10、; sequentially numberedxnetwork delivers packets in sequencexexternal virtual circuit servicexe.g. x.25xdifferent from internal virtual circuit operationyconnectionlessxpackets handled independentlyxexternal datagram servicexdifferent from internal datagram operationexternal virtual circuit anddatag

11、ram operation(a)(a)外部虛電路。在兩個站點之間建立一條邏輯連接外部虛電路。在兩個站點之間建立一條邏輯連接. .分組以虛電路和序號為標記，分組按照順序到達。分組以虛電路和序號為標記，分組按照順序到達。(b)(b)外部數(shù)據(jù)報。分組獨立傳輸，分組以目的站點外部數(shù)據(jù)報。分組獨立傳輸，分組以目的站點地址為標記。分組的到達可能失序。地址為標記。分組的到達可能失序。internalvirtualcircuit anddatagram operation(a)(a)內(nèi)部虛電路。兩個站點之間的分組傳輸路由已經(jīng)內(nèi)部虛電路。兩個站點之間的分組傳輸路由已經(jīng)定義好并設置好標記，所有從該虛電路上走的分組

12、沿定義好并設置好標記，所有從該虛電路上走的分組沿同一條路徑傳輸，并按序到達。同一條路徑傳輸，并按序到達。(b)(b)內(nèi)部數(shù)據(jù)報。每個分組由網(wǎng)絡獨立處理，分組以內(nèi)部數(shù)據(jù)報。每個分組由網(wǎng)絡獨立處理，分組以目的地址為標記，到達目的節(jié)點時可能失序。目的地址為標記，到達目的節(jié)點時可能失序。combinations (1)zexternal virtual circuit, internal virtual circuitydedicated route through networkzexternal virtual circuit, internal datagramynetwork handles

13、each packet separatelyydifferent packets for the same external virtual circuit may take different internal routesynetwork buffers at destination node for re-orderingcombinations (2)zexternal datagram, internal datagramypackets treated independently by both network and userzexternal datagram, interna

14、l virtual circuityexternal user does not see any connectionsyexternal user sends one packet at a timeynetwork sets up logical connectionsrouting-路由路由zcomplex, crucial aspect of packet switched networkszcharacteristics required：特性ycorrectness：正確性ysimplicity：簡潔性yrobustness：魯棒性one extreme to anotheryst

15、ability：穩(wěn)定性yfairness：公平性yoptimality：最優(yōu)性yefficiency：高效性performance criteria:性能準則zused for selection of routezminimum hop：跳數(shù)zleast cost：最小費用性能評估準則性能評估準則costing of routesdecision time and placeztimeypacket or virtual circuit basiszplaceydistributedxmade by each nodeycentralizedysource決策時間和地點決策時間和地點netw

16、ork information source and update timingz routing decisions usually based on knowledge of network (not always)z distributed routingynodes use local knowledgeymay collect info from adjacent nodesymay collect info from all nodes on a potential routez central routingycollect info from all nodesz update

17、 timingywhen is network info held by nodes updatedyfixed - never updatedyadaptive - regular updates網(wǎng)絡信息資源網(wǎng)絡信息資源和和更新定時更新定時routing strategieszfixed固定zflooding洪泛zrandom隨機zadaptive自適應路由選擇策略路由選擇策略fixed routing固定路由選擇zsingle permanent route for each source to destination pairzdetermine routes using a least

18、 cost algorithm (appendix 10a)zroute fixed, at least until a change in network topologyfixed routingtables中心路由選擇表中心路由選擇表節(jié)點節(jié)點1目錄目錄 節(jié)點節(jié)點2目錄目錄 節(jié)點節(jié)點3目錄目錄節(jié)點節(jié)點3目錄目錄 節(jié)點節(jié)點4目錄目錄 節(jié)點節(jié)點5目錄目錄到節(jié)點到節(jié)點從節(jié)點從節(jié)點flooding洪泛zno network info requiredzpacket sent by node to every neighborzincoming packets retransmitted on ev

19、ery link except incoming linkzeventually a number of copies will arrive at destinationzeach packet is uniquely numbered so duplicates can be discardedznodes can remember packets already forwarded to keep network load in boundszcan include a hop count in packetsflooding exampleproperties of flooding特

20、性zall possible routes are triedyvery robustzat least one packet will have taken minimum hop count routeycan be used to set up virtual circuitzall nodes are visitedyuseful to distribute information (e.g. routing)random routing隨機路由znode selects one outgoing path for retransmission of incoming packetzs

21、election can be random or round robinzcan select outgoing path based on probability calculationzno network info neededzroute is typically not least cost nor minimum hop 的數(shù)據(jù)率鏈路的概率選擇鏈路iriprrpiijjiiadaptive routing自適應路由自適應路由zused by almost all packet switching networkszrouting decisions change as condi

22、tions on the network changeyfailureycongestionzrequires info about networkzdecisions more complexztradeoff between quality of network info and overheadzreacting too quickly can cause oscillationztoo slowly to be relevant adaptive routing - advantageszimproved performancezaid congestion control (see

23、chapter 12)zcomplex systemymay not realize theoretical benefitsclassificationzbased on information sources(以信息源為依據(jù))ylocal (isolated)孤立式xroute to outgoing link with shortest queuexcan include bias for each destinationxrarely used - do not make use of easily available infoyadjacent nodes分布式y(tǒng)all nodes集

24、中式isolated adaptive routing獨立自適應路由選擇獨立自適應路由選擇least-cost algorithmszvirtually all packet switched networks base their routing decision on some form of least-cost criterion.zthe cost of a link may differ in its two directionszvariations of one of two common algorithms:ydijkstras algorithmybellman-ford

25、 algorithmdijkstras algorithmzfind the shortest paths from a given source node to all other nodes by developing the paths in order of increasing path length.zproceed in stages:yby the kth stage,the shortest paths to the k nodes closest to the source node have been determined;these nodes are in a set

26、 m.yat stage (k+1),the node not in m that has the shortest path from the source node is added to m.as each node is added to m,its path from the source is defined. ？ ？ ？kk+1definitionzn=set of nodes in the networkzs=source nodezm=set of nodes so far incorporated by the algorithmzdij =link cost from n

27、ode i to j ;dii=0;z =cost of the least-cost path from node s to node nnddijkstras algorithmz 1.initialize m=s ; for nsz 2.find the neighboring node not in m that has the least-cost path from node s and incorporate that node into m: find such that add w to mz 3.update least-cost paths: if the latter

28、term is the minimum,the path from s to n is now the path from s to w,concatenated with the link from w to n.mwjmjwddminmnallforddddwnwnn,minsnndd basic idea of dijkstras algorithm1ijj:(k+1)st closest nodecomplement of mset m of k closestnodes to node 1shortest path from the (k+1)st closest node must

29、 pass exclusively through nodes in pbellman-ford algorithmzv :yd(v):節(jié)點v到目標節(jié)點的最短距離yn: 當前計算的最短通路上v節(jié)點的下一節(jié)點初始化；設置d(1)=0,所有非目標節(jié)點加上標志重復；對每一個非目標節(jié)點v用下式更新d(v)y節(jié)點w為v的相鄰節(jié)點)(,(vdn),( ),()()(wvlwdminvdexample using the b & d algorithms.(作業(yè))42315613411124dij=djix.25-訪問分組交換網(wǎng)的協(xié)議標準訪問分組交換網(wǎng)的協(xié)議標準z 1974 , itu-tz int

30、erface between host and packet switched networkz almost universal on packet switched networks and packet switching in isdnz defines three layersyphysicalylinkypacketx.25 and osix.25 - physicalzinterface between attached station and link to nodezdata terminal equipment dte (user equipment)zdata circu

31、it terminating equipment dce (node)zuses physical layer specification x.21zreliable transfer across physical linkx.25 - linkzsequence of frames:幀序列形式幀序列形式zlink access protocol balanced (lapb)ysubset of hdlcysee chapter 7x.25 - packetzexternal virtual circuits：外部虛電路服務外部虛電路服務zlogical connections (virt

32、ual circuits) between subscribers用戶數(shù)據(jù)和用戶數(shù)據(jù)和x.25x.25協(xié)議控制信息協(xié)議控制信息x.25 networkx.25 networkdtedcedcedteframe layer domainframe layer domainpacket layer domainframe layer & packet layer domainsx.25 use of virtual circuitssending and receiving network layerpackets(encapsulated in i-frames)and using s-

33、frames to control the flowand error of those i-framesthree phases of the frame layerdtedcesabmuauadiscu-framess-framesi-framesu-frameslink setupdata and control transferlink disconnectconnection establishmentconnection establishmentclearingclearingvirtual circuit establishmentza link is setup betwee

34、n the local dte and dce and also between the remote dte and dce.za virtual circuit is established between the local dte and the remote dte.zdata are transferred between the two dtes.zthe virtual circuit is released.zthe link is disconnected.鏈路建立和虛電路建立的區(qū)別logic channel number(lcn)dte adte cdte blcn:88

35、lcn:34lcn:72lcn:276virtual circuit servicezvirtual call:虛呼叫ydynamically established at each sessionylcns are temporarily assignedzpermanent virtual circuit：永久虛電路yfixed network assigned virtual circuitylcns are permanently assigned by the network provider.virtual circuit numberingpvcsvc(switched virt

36、ual circuits)0001 2047 2048 4095assigned by dceassigned by dteone-way callsincomingone-way callsoutgoingtwo-way callsreservedmultiplexing：復用復用zpackets contain 12 bit virtual circuit numberzdte can establish 4095 simultaneous virtual circuits with other dtes over a single dte-dce linkvirtual call呼叫請求

37、呼叫請求入呼叫入呼叫呼叫接受呼叫接受呼叫連通呼叫連通清除請求清除請求清除指示清除指示清除證實清除證實清除證實清除證實packet format:分組格式分組格式headeruser data , control data, or nothinggfilcnpti4 bits 12 bits 8 bits or 16 bitsgeneral format identifier(gfi)logic channel number(lcn)packet type identifier(pti)general format identifier(gfi)gfiqd？q(qualifier):defines the source of control information. 0plp; 1other high-level protocols.d(delivery):defines which device should ack. packet 0local dce; 1remote dte.sequence numbers:013bits(modulo 8)107bits(modulo 128)two categories of packetsplp packetsdata packetscontrol packetsrr,rnr,rejothers data packetsqd