計算機網絡楊獻春教學講稿2004dcc

1、Data Communications Data Communications and Networkingand Networking 2022-3-9Department of Computer Science and Technology, Nanjing University2擁塞? ? 擁塞擁塞產生于通過網絡傳輸的分組數量接近網絡的最大分組處理能力之時 擁塞控制擁塞控制旨在保持分組數量不超越致使性能急劇下降的水平 數據網本質上是一個由隊列組成的網絡 一般而言，達到80%利用率是一條警戒線 隊列的有限長度意味著數據可能因溢出而丟失2022-3-9Department of Comput

2、er Science and Technology, Nanjing University3What is Congestion?What is Congestion? Congestion occurs when the number of packets being transmitted through the network approaches the packet handling capacity of the network Congestion control aims to keep number of packets below level at which perfor

3、mance falls off dramatically Data network is a network of queues Generally 80% utilization is critical Finite queues mean data may be lostQueues at a NodeQueues at a NodeAny given node has a number of I/O ports: One or more to other nodes Zero or more to end systemsWhy?2022-3-9Department of Computer

4、 Science and Technology, Nanjing University512.1 12.1 擁塞對網絡性能的影響擁塞對網絡性能的影響 到達的分組存放在輸入緩存中 考察每個分組并作出路由選擇判決 將分組移至輸出緩存 排隊輸出的分組盡快地發(fā)出 統(tǒng)計時分復用 若分組到達過快以至來不及選路, 或者說輸入快于輸出, 緩沖會溢滿 兩種通用策略 丟棄分組 使用流量控制2022-3-9Department of Computer Science and Technology, Nanjing University612.1 12.1 Effects of CongestionEffects o

5、f Congestion Packets arriving are stored at input buffers Examines each packet and makes routing decision Packet moves to output buffer Packets queued for output are transmitted as fast as possible Statistical time division multiplexing If packets arrive too fast to be routed, or to be output, buffe

6、rs will fill Two general strategies Can discard packets Can use flow controlInteraction of QueuesInteraction of Queues Can propagate congestion through network2022-3-9Department of Computer Science and Technology, Nanjing University812.1.1 12.1.1 Ideal Ideal PerformancePerformance理想性能理想性能10.80.5網絡傳播

7、時延網絡傳播時延+節(jié)點處理時延節(jié)點處理時延+節(jié)點排隊時延節(jié)點排隊時延 ThroughputPower Delay2022-3-9Department of Computer Science and Technology, Nanjing University912.1.2 12.1.2 實際性能實際性能 理想情況是假定緩存空間無限且無額外開銷 實際應用中緩存是有限的 在交換擁塞控制報文時產生額外開銷2022-3-9Department of Computer Science and Technology, Nanjing University1012.1.2 12.1.2 Practical

8、PerformancePractical Performance Ideal assumes infinite buffers and no overhead Buffers are finite Overheads occur in exchanging congestion control messages2022-3-9Department of Computer Science and Technology, Nanjing University11Effects of Effects of Congestion -Congestion -No ControlNo Control 負荷

9、較輕時 隨負荷增長，網絡吞吐率及網絡利用率增加 進入中度擁塞（A點） 隨負荷增長，網絡吞吐率增長減慢 負載不均勻導致部分節(jié)點丟棄分組 平衡負載的選路分組增加開銷，降低數據通信量 進入嚴重擁塞（B點） 隨負荷增長，網絡吞吐率反而下降 有限緩存丟棄分組導致重傳 應答延滯使已交付分組重傳12.2 12.2 Congestion ControlCongestion Control 擁塞控制擁塞控制Mechanisms for Congestion ControlMechanisms for Congestion Control2022-3-9Department of Computer Science

10、 and Technology, Nanjing University1312.2.1 12.2.1 反壓反壓 倘若節(jié)點擁塞，可能減緩或阻停來自其它節(jié)點的分組流量 可能引起其它節(jié)點不得不對分組進入速率施加控制 流量限制傳播回源節(jié)點 可以對產生大部分通信量的邏輯連接給予限制 用于允許逐跳擁塞控制的面向連接網絡 (如 X. 25) ATM和幀中繼中不采用 因其無逐跳限制流量的功能 近年僅為IP開發(fā)出基于流量的機制 IPv6分組中的逐跳選項首部（15.4.5），所攜信息必須被沿途每個路由器檢查2022-3-9Department of Computer Science and Technology,

11、 Nanjing University1412.2.1 12.2.1 BackpressureBackpressure If node becomes congested it can slow down or halt flow of packets from other nodes May mean that other nodes have to apply control on incoming packet rates Propagates back to source Can restrict to logical connections generating most traff

12、ic Used in connection oriented that allow hop by hop congestion control (e.g. X.25) Not used in ATM nor frame relay Only recently developed for IP2022-3-9Department of Computer Science and Technology, Nanjing University1512.2.2 12.2.2 阻流分組阻流分組 控制分組 由發(fā)生擁塞的節(jié)點生成 送至源節(jié)點 例如， ICMP 源站抑制 來自路由器或目的站 源站削減流量直至再無

13、源站抑制報文 為每個丟棄的分組或預見的擁塞發(fā)送抑制報文 相當粗糙的機制 預測擁塞發(fā)送的抑制報文所指的數據報可能正確交付2022-3-9Department of Computer Science and Technology, Nanjing University1612.2.2 12.2.2 Choke PacketChoke Packet Control packet Generated at congested node Sent to source node e.g. ICMP source quench From router or destination Source cuts b

14、ack until no more source quench message Sent for every discarded packet, or anticipated Rather crude mechanism2022-3-9Department of Computer Science and Technology, Nanjing University1712.2.3 12.2.3 隱式擁塞信令隱式擁塞信令 傳輸時延會隨擁塞而增加 分組可能被丟棄 隨著擁塞的隱含指示，源站能夠檢測到這些 在無連接（數據報）網絡中是有用的 例如，基于 IP的因特網 (TCP 包含擁塞控制和流量控制 見

15、第 17章) 用于幀中繼 LAPF控制協(xié)議2022-3-9Department of Computer Science and Technology, Nanjing University1812.2.3 12.2.3 Implicit Congestion Implicit Congestion SignalingSignaling Transmission delay may increase with congestion Packet may be discarded Source can detect these as implicit indications of congesti

16、on Useful on connectionless (datagram) networks e.g. IP based (TCP includes congestion and flow control - see chapter 17) Used in frame relay LAPF2022-3-9Department of Computer Science and Technology, Nanjing University1912.2.4 12.2.4 顯式擁塞信令顯式擁塞信令 網絡會對漸增的擁塞向端系統(tǒng)告警 端系統(tǒng)采取步驟減輕供給網絡的負載 反向 在所需分組的相反方向上采取擁塞避

17、免措施 前向 在所需分組的相同方向上采取擁塞避免措施2022-3-9Department of Computer Science and Technology, Nanjing University2012.2.4 12.2.4 Explicit Congestion Explicit Congestion SignalingSignaling Network alerts end systems of increasing congestion End systems take steps to reduce offered load Backwards Congestion avoidan

18、ce in opposite direction to packet required Forwards Congestion avoidance in same direction as packet required2022-3-9Department of Computer Science and Technology, Nanjing University21顯式信令種類顯式信令種類 二進制 在分組中置位一個比特來指示擁塞 基于信用值 指示源站可以發(fā)送多少分組 常見于端到端流量控制 基于速率 提供明確的數據率上限 例如， ATM2022-3-9Department of Compute

19、r Science and Technology, Nanjing University22Categories of Explicit SignalingCategories of Explicit Signaling Binary A bit set in a packet indicates congestion Credit based Indicates how many packets source may send Common for end to end flow control Rate based Supply explicit data rate limit e.g.

20、ATM2022-3-9Department of Computer Science and Technology, Nanjing University2312.3 12.3 通信量管理通信量管理 公平性 最后到達最先丟棄策略并不保證對不同流量體現(xiàn)公平 為每個邏輯連接或每對源-目的站維持緩存大小相同的一個隊列，通信量負荷最大的隊列應更頻繁丟棄分組 服務質量(QoS) 不同的連接可以希望不同的對待 ISA和DS 見16.2和16.4 預約 例如， ATM 用戶與網絡之間的通信量合約 RSVP協(xié)議 見16.32022-3-9Department of Computer Science and Te

21、chnology, Nanjing University2412.3 12.3 Traffic ManagementTraffic Management Fairness Quality of service May want different treatment for different connections Reservations e.g. ATM Traffic contract between user and network RSVP protocol - see Chapter 162022-3-9Department of Computer Science and Tec

22、hnology, Nanjing University2512.4 12.4 分組交換網中的擁塞控制分組交換網中的擁塞控制 發(fā)送控制分組到某些或全部源節(jié)點 在擁塞期間需要額外的通信量 依賴路由選擇信息 可能會反應過快 端到端探測分組 增加網絡開銷 當分組穿越節(jié)點時向其添加擁塞信息 或者反向或者前向2022-3-9Department of Computer Science and Technology, Nanjing University2612.4 12.4 Congestion Control in Packet Congestion Control in Packet Switched

23、 NetworksSwitched Networks Send control packet to some or all source nodes Requires additional traffic during congestion Rely on routing information May react too quickly End to end probe packets Adds to overhead Add congestion info to packets as they cross nodes Either backwards or forwards2022-3-9

24、Department of Computer Science and Technology, Nanjing University27虛電路或幀中繼連接上的通信量虛電路或幀中繼連接上的通信量 通信量本質上是突發(fā)性的 接收系統(tǒng)期望以突發(fā)方式接收從各條連接上進入的通信量 網絡不必在出口節(jié)點復制進入通信量完全相同的時序模式 可使用簡單的STDM在一個物理UNI之上容納多條邏輯連接2022-3-9Department of Computer Science and Technology, Nanjing University28Traffic on Virtual Circuits or Frame

25、Traffic on Virtual Circuits or Frame Realy ConnectionsRealy Connections Traffic is bursty in nature Receiving system expects to receive incoming traffic on each connection in a bursty fashion Network does not need to replicate the exact timing pattern of incoming traffic at exit node Simple STDM can

26、 be used to accommodate multiple logical connections over physical UNI2022-3-9Department of Computer Science and Technology, Nanjing University2912.5 ATM通信量管理通信量管理 ATM通信量特點 速度高、信元長度小、額外開銷比特有限 仍在演變 主要論題 通信量及擁塞控制需求 反應遲滯 / 速度影響 信元時延偏差 通信量與擁塞控制框架 通信量管理和擁塞控制技巧2022-3-9Department of Computer Science and Te

27、chnology, Nanjing University3012.5 12.5 ATM Traffic ManagementATM Traffic Management High speed, small cell size, limited overhead bits Still evolving Key Topics Requirements Latency / Speed Effects Cell Delay Variation Traffic and Congestion Control Framework Traffic Management & Congestion Con

28、trol Techniques2022-3-9Department of Computer Science and Technology, Nanjing University3112.5.1 ATM通信量及擁塞控制的需求通信量及擁塞控制的需求 多數通信量并不服從流量控制 因信元傳輸時間比之傳播時延大幅減小顯得反饋遲緩 廣泛的應用要求 差異很大的通信量模式 不同的網絡服務 高速交換與傳輸增加了易變性2022-3-9Department of Computer Science and Technology, Nanjing University3212.5.1 12.5.1 Requiremen

29、ts for ATM Traffic and Requirements for ATM Traffic and Congestion ControlCongestion Control Majority of traffic not amenable to flow control Feedback slow due to reduced transmission time compared with propagation delay Wide range of application demands Different traffic patterns Different network

30、services High speed switching and transmission increases volatility2022-3-9Department of Computer Science and Technology, Nanjing University3312.5.2 12.5.2 反應遲滯反應遲滯 / 速度影響速度影響 ATM 150Mbps 插入單個信元大約需2.8x10-6秒 跑完網絡全程的時間取決于傳播時延和交換時延 假定以2/3光速傳播 倘若源站和目的站處于美國東西兩端, 傳播時間約 48x10-3 秒 采用隱式擁塞控制, 在丟棄信元通知報文到達源站之時為

31、止, 已經傳輸了7.2x106比特 參見教材第313頁倒數第4行的計算（英文版p.396） 因此這對ATM不是一個好策略 當源站對擁塞指示反應過來時，網絡擁塞得一塌糊涂2022-3-9Department of Computer Science and Technology, Nanjing University3412.5.2 12.5.2 Latency/Speed EffectsLatency/Speed Effects ATM 150Mbps 2.8x10-6 seconds to insert single cell Time to traverse network depends

32、on propagation delay, switching delay Assume propagation at two-thirds speed of light If source and destination on opposite sides of USA, propagation time 48x10-3 seconds Given implicit congestion control, by the time dropped cell notification has reached source, 7.2x106 bits have been transmitted S

33、o, this is not a good strategy for ATM2022-3-9Department of Computer Science and Technology, Nanjing University3512.5.3 12.5.3 信元時延偏差信元時延偏差 對于ATM話音/視頻, 數據是一信元流 穿越網絡的時延必須短小 交付速率必須恒定 運送中總是存在一些偏差 信元交付給應用之前增加一點可調時延，使之能夠為應用維持恒定的比特率2022-3-9Department of Computer Science and Technology, Nanjing University3

34、612.5.3 12.5.3 Cell Delay VariationCell Delay Variation For ATM voice/video, data is a stream of cells Delay across network must be short Rate of delivery must be constant There will always be some variation in transit Delay cell delivery to application so that constant bit rate can be maintained to

35、 applicationTime Re-assembly of CBR CellsTime Re-assembly of CBR CellsV(i)=V(i-1)-ti-(ti-1+d)2022-3-9Department of Computer Science and Technology, Nanjing University38網絡對信元時延偏差的影響網絡對信元時延偏差的影響 分組交換的網絡 排隊時延 路由選擇判決時間 幀中繼 同上，但程度較輕 ATM 比幀中繼還小 ATM協(xié)議就是為使交換節(jié)點處理開銷最小化而設計的 ATM交換機有著極高的吞吐率 唯一值得注意的時延偏差來自擁塞 必須不接受

36、引起擁塞的負荷 丟棄引起網絡擁塞的信元2022-3-9Department of Computer Science and Technology, Nanjing University39Network Contribution to Network Contribution to Cell Delay VariationCell Delay Variation Packet switched networks Queuing delays Routing decision time Frame relay As above but to lesser extent ATM Less than

37、 frame relay ATM protocol designed to minimize processing overheads at switches ATM switches have very high throughput Only noticeable delay is from congestion Must not accept load that causes congestion2022-3-9Department of Computer Science and Technology, Nanjing University40UNI上的信元時延偏差上的信元時延偏差 應用

38、程序產生固定速率的數據 ATM的三層處理仍會引起時延偏差 交織的信元來自不同連接 運行維護管理（OAM）信元也必須與用戶信元相交織 若使用SDH幀, 這些幀的額外開銷比特插入物理層 無法預測這些時延2022-3-9Department of Computer Science and Technology, Nanjing University41Cell Delay Variation At The UNICell Delay Variation At The UNI Application produces data at fixed rate Processing at three lay

39、ers of ATM causes delay Interleaving cells from different connections Operation and maintenance cell interleaving If using synchronous digital hierarchy frames, these are inserted at physical layer Can not predict these delaysOrigins of Cell Delay VariationOrigins of Cell Delay Variation2022-3-9Depa

40、rtment of Computer Science and Technology, Nanjing University4312.5.4 12.5.4 通信量與擁塞控制框架通信量與擁塞控制框架 ATM層通信量控制與擁塞控制應該為所有可預見的網絡服務支持QoS類別 應該不依賴于與具體網絡相關的 AAL協(xié)議，也不依賴于高層的具體應用協(xié)議 應該使網絡以及端到端系統(tǒng)的復雜性最小化2022-3-9Department of Computer Science and Technology, Nanjing University4412.5.4 12.5.4 Traffic and Congestion

41、Traffic and Congestion Control FrameworkControl Framework ATM layer traffic and congestion control should support QoS classes for all foreseeable network services Should not rely on AAL protocols that are network specific, nor higher level application specific protocols Should minimize network and e

42、nd to end system complexity2022-3-9Department of Computer Science and Technology, Nanjing University45通信量控制策略本質通信量控制策略本質 確定是否可以容納一條給定的新連接 與用戶設備協(xié)商需要支持性能參數 實際上用戶與網絡達成一份通信量合約 網絡答應在該連接上以某種性能級別支持通信量 用戶承諾不超越通信量參數限制2022-3-9Department of Computer Science and Technology, Nanjing University46Nature of Strateg

43、yNature of Strategy Determine whether a given new connection can be accommodated Agree performance parameters with subscriber In effect, subscriber and network enter into a traffic contract Network agrees to support traffic at a certain level of performance on this connection Subscriber agrees not e

44、xceed traffic parameter limits2022-3-9Department of Computer Science and Technology, Nanjing University47考慮的時序考慮的時序 信元插入時間 往返傳播時間 連接持續(xù)時間 長期2022-3-9Department of Computer Science and Technology, Nanjing University48Timings ConsideredTimings Considered Cell insertion time Round trip propagation time C

45、onnection duration Long term2022-3-9Department of Computer Science and Technology, Nanjing University492022-3-9Department of Computer Science and Technology, Nanjing University5012.5.5 12.5.5 通信量管理與擁塞控制技巧通信量管理與擁塞控制技巧 使用VP管理資源 連接許可控制 使用參數控制 選擇性信元丟棄 通信量整形2022-3-9Department of Computer Science and Tech

46、nology, Nanjing University5112.5.5 12.5.5 Traffic Management and Traffic Management and Congestion Control TechniquesCongestion Control Techniques Resource management using virtual paths Connection admission control Usage parameter control Selective cell discard Traffic shaping2022-3-9Department of

47、Computer Science and Technology, Nanjing University52利用利用VPVP進行資源管理進行資源管理 根據服務特性區(qū)別不同的通信流量 用戶到用戶應用 用戶到網絡應用 網絡到網絡應用 網絡資源管理涉及的QoS參數 信元丟失率 信元傳送時延 信元時延偏差2022-3-9Department of Computer Science and Technology, Nanjing University53Resource Management Using Virtual Paths Separate traffic flow according to se

48、rvice characteristics User to user application User to network application Network to network application Concern with: Cell loss ratio Cell transfer delay Cell delay variationConfiguration of VCCs and VPCsConfiguration of VCCs and VPCs2022-3-9Department of Computer Science and Technology, Nanjing U

49、niversity55在在VPCVPC內部分配內部分配VCCVCC VPC內的所有VCC應該體驗類似的網絡性能 分配容量的選項 聚集峰值需求 統(tǒng)計復用2022-3-9Department of Computer Science and Technology, Nanjing University56Allocating VCCs within VPCAllocating VCCs within VPC All VCCs within VPC should experience similar network performance Options for allocation: Aggrega

50、te peak demand Statistical multiplexing2022-3-9Department of Computer Science and Technology, Nanjing University57連接許可控制連接許可控制 防止網絡過載的第一道防線 用戶通過選擇一種QoS為新連接(VCC或VPC)規(guī)定通信量 僅當網絡能夠滿足該需求時才認可該連接 通信量合約 最大信元速率 信元時延偏差 持續(xù)信元速率 突發(fā)容限2022-3-9Department of Computer Science and Technology, Nanjing University58Conne

51、ction Admission Control First line of defence User specifies traffic characteristics for new connection (VCC or VPC) by selecting a QoS Network accepts connection only if it can meet the demand Traffic contract Peak cell rate Cell delay variation Sustainable cell rate Burst tolerance2022-3-9Departme

52、nt of Computer Science and Technology, Nanjing University592022-3-9Department of Computer Science and Technology, Nanjing University602022-3-9Department of Computer Science and Technology, Nanjing University61使用參數控制使用參數控制 監(jiān)控連接確保通信量遵從合約 防止網絡資源因某條連接而超載 在 VCC和 VPC兩級上實現(xiàn) 包含兩個獨立的功能 最大信元速率及相關的信元時延偏差的控制 持續(xù)信

53、元速率及相關的突發(fā)容限 丟棄不遵從通信量合約的信元 被稱為通信量管制2022-3-9Department of Computer Science and Technology, Nanjing University62Usage Parameter Control Monitor connection to ensure traffic conforms to contract Protection of network resources from overload by one connection Done on VCC and VPC Peak cell rate and cell d

54、elay variation Sustainable cell rate and burst tolerance Discard cells that do not conform to traffic contract Called traffic policing2022-3-9Department of Computer Science and Technology, Nanjing University63信元丟棄策略信元丟棄策略 加標簽方法及相關的通信量合約 選擇性信元丟棄CLP的應用作為課后作業(yè)，仔細研讀教材第321頁2022-3-9Department of Computer S

55、cience and Technology, Nanjing University64通信量整形通信量整形 通信量管制的輔助策略 使通信量平穩(wěn)并減少信元堆積 令牌桶2022-3-9Department of Computer Science and Technology, Nanjing University65Traffic Shaping Smooth out traffic flow and reduce cell clumping Token bucketToken BucketToken Bucket例例 一個ATM網絡使用令牌桶方案的通信量管制。每5ms放入桶內的一個新的令牌。試問

56、最大的可持續(xù)的凈數據率（不包含信元首部）是多少？解答解答 已知每5ms放入信令桶的一個新的令牌， 則1秒鐘可放入2105個令牌，即每秒可傳送2105個信元。 每個信元不包括首部有48個八比特組，即 848384個比特。 因此，最大的可持續(xù)的凈數據率 R 3842105 768105 76.8Mbps令牌桶計算題2022-3-9Department of Computer Science and Technology, Nanjing University6812.6 12.6 ATM-ABRATM-ABR通信量管理通信量管理 應用于CBR、VBR的上述方法稱為開環(huán)控制 某些應用未很好定義通信量

57、特性 Web, FTP, RPC, NFS 盡最大努力 允許這些應用分享未用容量 如果擁塞構成，信元被丟棄 閉環(huán)控制 多個ABR連接共享可用容量 該共享容量在最小信元速率(MCR)與最大信元速率(PCR) 之間變化 因為反饋使ARB流量受到可用容量的限制 在反饋時延期間緩沖吸收超出的通信量 信元丟失率低閱讀ABR服務主要特性 P.3232022-3-9Department of Computer Science and Technology, Nanjing University6912.6 ATM-ABR Traffic Management Some applications (Web,

58、file transfer) do not have well defined traffic characteristics Best efforts Allow these applications to share unused capacity If congestion builds, cells are dropped Closed loop control ABR connections share available capacity Share varies between minimum cell rate (MCR) and peak cell rate (PCR) AR

59、B flow limited to available capacity by feedback Buffers absorb excess traffic during feedback delay Low cell loss2022-3-9Department of Computer Science and Technology, Nanjing University7012.6.1 12.6.1 反饋機制反饋機制 傳輸速率特性 允許的信元速率 ACR 最小的信元速率 MCR 最大信元速率 PCR 初始信元速率 ICR 以ACR=ICR開始 根據來自網絡的反饋調整ACR 資源管理信元 擁塞

60、指示比特 CI 不增加比特 NI 顯式信元速率字段 ER2022-3-9Department of Computer Science and Technology, Nanjing University7112.6.1 Feedback Mechanisms Transmission rate characteristics: Allowed cell rate Minimum cell rate Peak cell rate Initial cell rate Start with ACR=ICR Adjust ACR based on feedback from network Resource