《les原理》PPT課件

1、Computer Network,Chapter 11:Packet Switching,分組交換,Principles:原理,Circuit switching designed for voice Resources dedicated to a particular call Much of the time a data connection is idle Data rate is fixed Both ends must operate at the same rate,Basic Operation:基本操作,Data transmitted in small packets T

2、ypically 1000 octets Longer messages split into series of packets Each packet contains a portion of user data plus some control info Control info Routing (addressing) info Packets are received, stored briefly (buffered) and past on to the next node Store and forward,Use of Packets：使用分組,Advantages：優(yōu)點

3、,Line efficiency：線路效率 Single node to node link can be shared by many packets over time Packets queued and transmitted as fast as possible Data rate conversion：數(shù)據(jù)率匹配 Each station connects to the local node at its own speed Nodes buffer data if required to equalize rates Packets are accepted even when

4、 network is busy Delivery may slow down Priorities can be used：優(yōu)先級的使用,Switching Technique:交換技術(shù),Station breaks long message into packets Packets sent one at a time to the network Packets handled in two ways Datagram：數(shù)據(jù)報 Virtual circuit：虛電路,Datagram：數(shù)據(jù)報,Each packet treated independently Packets can ta

5、ke any practical route Packets may arrive out of order Packets may go missing Up to receiver to re-order packets and recover from missing packets,Datagram Approach,Datagram Approach,Multiple Channels,Virtual Circuit：虛電路,Preplanned route established before any packets sent Call request and call accep

6、t packets establish connection (handshake) Each packet contains a virtual circuit identifier instead of destination address No routing decisions required for each packet Clear request to drop circuit Not a dedicated path,Switch Virtual Circuit,Switched Virtual Circuit,Switched Virtual Circuit,Virtua

7、l Circuits v Datagram,Virtual circuits Network can provide sequencing and error control Packets are forwarded more quickly No routing decisions to make Less reliable Loss of a node looses all circuits through that node Datagram No call setup phase Better if few packets More flexible Routing can be u

8、sed to avoid congested parts of the network,Packet Size,分組大小 傳輸時間,Data:40 Header:3,Circuit v Packet Switching,Performance Propagation delay:傳播時延 Transmission time:傳輸時間 Node delay:節(jié)點時延,Event Timing,電路交換 虛電路分組交換 數(shù)據(jù)報分組交換,節(jié)點,呼叫 請求 信號,呼叫 請求 信號,呼叫 接受 信號,呼叫 接受 信號,傳播時延,處理時延,應(yīng)答信號,應(yīng)答信號,用戶數(shù)據(jù),External and Inter

9、nal Operation,Packet switching - datagrams or virtual circuits Interface between station and network node Connection oriented Station requests logical connection (virtual circuit) All packets identified as belonging to that connection these nodes are in a set M. At stage (k+1),the node not in M that

10、 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.,？,？,？,K,K+1,definition,N=set of nodes in the network S=source node M=set of nodes so far incorporated by the algorithm dij =link cost from node i to j ;dii=0; =cost of the least-

11、cost path from node s to node n,Dijkstras algorithm,1.initialize M=s ; for ns 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 M 3.Update least-cost paths: If the latter term is the minimum,the path from s to n is

12、 now the path from s to w,concatenated with the link from w to n.,Basic idea of Dijkstras algorithm,1,i,j,j:(k+1)st closest node,Complement of M,set M of k closest nodes to node 1,Shortest path from the (k+1)st closest node must pass exclusively through nodes in P,Bellman-Ford algorithm,V : D(v):節(jié)點v

13、到目標(biāo)節(jié)點的最短距離 n: 當(dāng)前計算的最短通路上v節(jié)點的下一節(jié)點 1：初始化；設(shè)置D(1)=0,所有非目標(biāo)節(jié)點加上標(biāo)志 2：重復(fù)；對每一個非目標(biāo)節(jié)點v用下式更新D(v) 節(jié)點w為v的相鄰節(jié)點,Example using the B 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 pack

14、ets,PLP packets,Data packets,Control packets,RR,RNR,REJ,Others,Data packets,Q,D,0,1,LCN,8 7 6 5 4 3 2 1,LCN,LCN,M,0,P,P,P(s),P(s),M,0,User Data,User Data,Q,D,1,0,LCN,3bit序列號,7bit序列號,M:more,LCN,LCN,P,Packet type,0,P,RR,RNR,and REJ packets,Q,D,0,1,8 7 6 5 4 3 2 1,1,Q,D,1,0,LCN,8 7 6 5 4 3 2 1,LCN,1,Pa

15、cket type,0,0,000-RR 001-RNR 010-REJ,Other control packets,Q,D,0,1,LCN,8 7 6 5 4 3 2 1,LCN,1,Packet type,1,Additional information,Control Packet Formats(?11),（000010）,（000011）,（000100）,（000101）,（0010000）,（001001）,Control Packet Formats (?11),（000110）,（000111）,（111110）,（111111）,（111100）,（111101）,Flow

16、 and Error Control,HDLC (Chapter 7),Packet Sequences:分組排序,Complete packet sequences Allows longer blocks of data across network with smaller packet size without loss of block integrity A packets M bit 1, D bit 0 B packets The rest Zero or more A followed by B,x.25 packet sequences,Original seq. Combined seq. Packet Packet Type M D type M D A 1 0 A 1 0 A 1 0 A 1 0 A 1 0 A 1 0 A 1 0 B 0 1 B 0 1 Segmented seq B 0 0 A 1 0 B 0 0,Sequence and Subsequences,Reset and Restart,Reset：復(fù)位 Reinitialize virtual circuit Sequence numbers set to zero Packets in transit