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：优点优点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：数据率匹配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：优先级的使用switching technique:交换技术交换技术zstation breaks long message into packetszpackets sent one at a time to the networkzpackets handled in two waysydatagram：数据报yvirtual circuit：虚电路datagram：数据报数据报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:节点时延event timing 电路交换电路交换 虚电路分组交换虚电路分组交换 数据报分组交换数据报分组交换节点节点呼叫呼叫请求请求信号信号呼叫呼叫请求请求信号信号呼叫呼叫接受接受信号信号呼叫呼叫接受接受信

9、号信号传播时传播时延延处理时处理时延延应答信号应答信号应答信号应答信号用户数据用户数据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)外部数据报。分组独立传输，分组以目的站点外部数据报。分组独立传输，分组以目的站点地址为标记。分组的到达可能失序。地址为标记。分组的到达可能失序。internalvirtualcircuit anddatagram operation(a)(a)内部虚电路。两个站点之间的分组传输路由已经内部虚电路。两个站点之间的分组传输路由已经定义好并设置好标记，所有从该虚电路上走的分组

12、沿定义好并设置好标记，所有从该虚电路上走的分组沿同一条路径传输，并按序到达。同一条路径传输，并按序到达。(b)(b)内部数据报。每个分组由网络独立处理，分组以内部数据报。每个分组由网络独立处理，分组以目的地址为标记，到达目的节点时可能失序。目的地址为标记，到达目的节点时可能失序。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：稳定性yfairness：公平性yoptimality：最优性yefficiency：高效性performance criteria:性能准则zused for selection of routezminimum hop：跳数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网络信息资源网络信息资源和和更新定时更新定时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中心路由选择表中心路由选择表节点节点1目录目录 节点节点2目录目录 节点节点3目录目录节点节点3目录目录 节点节点4目录目录 节点节点5目录目录到节点到节点从节点从节点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 的数据率链路的概率选择链路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(以信息源为依据)ylocal (isolated)孤立式xroute to outgoing link with shortest queuexcan include bias for each destinationxrarely used - do not make use of easily available infoyadjacent nodes分布式yall 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):节点v到目标节点的最短距离yn: 当前计算的最短通路上v节点的下一节点初始化；设置d(1)=0,所有非目标节点加上标志重复；对每一个非目标节点v用下式更新d(v)y节点w为v的相邻节点)(,(vdn),( ),()()(wvlwdminvdexample using the b & d algorithms.(作业)42315613411124dij=djix.25-访问分组交换网的协议标准访问分组交换网的协议标准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用户数据和用户数据和x.25x.25协议控制信息协议控制信息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.链路建立和虚电路建立的区别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