電子科技大學(xué)高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)第四章-中繼原理匯編

1Chapter4RelayprincipleWhat’sRelaymeans?ReceivePDUfromoneport,andrelayPDUtoanotherport2IntroductionRepeaterEthernetSwitchIPRouterPDUprocessing&RelaymachinePDUinPDUoutIntroductionRelaymayoccursatalllayers3RelayRelayRelayRelayRelayPhyLinkNetworkTransportApplicationRepeaterBridgeRouterTrans.GatewayApp.GatewayIntroductionRelayExamples4phyMACphyMACphyMACphyMACRelay4-PortsEthernetswitch(Layer-2relay)MAC實(shí)體收到以太幀后，取出DU和形成ICI，向上遞交所有SAP通道都進(jìn)入中繼Relay根據(jù)ICI信息(源、目的MAC地址)中繼DU到另一個(gè)出口Relay對(duì)DU的不同處理功能，形成多種類型的二層設(shè)備IntroductionIPRouter5phyMACphyMACphyMACphyMACIPRelay4-PortsIPRouter(Layer-3relay)MAC實(shí)體收到以太幀后，取出DU和形成ICI，向上遞交DU是IP實(shí)體的PDU(IP報(bào)文)，IP實(shí)體根據(jù)IP報(bào)文中的地址信息(源IP和目的IP地址)，中繼IP報(bào)文Relay對(duì)PDU的不同處理，形成多種類型的三層設(shè)備(網(wǎng)絡(luò)層設(shè)備)同樣，傳送層中繼、應(yīng)用層中繼形成了豐富的組網(wǎng)設(shè)備IntroductionIPRoutervs.Ethernetswitch兩種完全不同中繼類型一個(gè)用協(xié)議來中繼，一個(gè)在協(xié)議外中繼一個(gè)利用PDU首部的信息，一個(gè)利用ICI信息進(jìn)行中繼6電子科技大學(xué)—通信與信息工程學(xué)院Router-

ColorandsubduedRouter

w/SiliconSwitchProtocolTranslatorCiscoWorks

WorkstationTerminalServerAccess

ServerNetFlow

RouterWorkgroup

DirectorNetworkManagementAppliancePCRouter

CardCisco

HubCiscoMeetingPlaceExpressSoftware-

BasedRouteronFile/ApplicationServerBridgeWorkgroup

Switch

Color/SubduedSmallHub(10BaseTHub)100BaseT

HubCDDI/

FDDIConcentratorPCAdapterCardIcons:CiscoProductsWavelength

RouterTransPathuBR910

CableDSUWorkgroup

Switch

Voice-EnabledStorageSolution

Engine

(SSE)IOSSLBVIP電子科技大學(xué)—通信與信息工程學(xué)院Route/SwitchProcessor

withandwithoutSiPCwith

SoftwarePCwithRouter-BasedSoftwareSwitchProcessorATM

SwitchLAN2LANSwitchMicroWeb

ServerISDN

SwitchMGX8000

Multiservice

SwitchMulti-

Switch

DeviceBroadband

RouterContentEngineCiscoCACisco

5500

FamilyIcons:CiscoProducts(Cont.)PXFManagementEngine

(ME1100)ASICProcessorGeneralProcessorIP

TransportConcentratorBBSMITPATASIPProxyServerVoiceGatewayApplicationVelocitySystem電子科技大學(xué)—通信與信息工程學(xué)院Cisco4310EndOfficeSystemNetRangerNetSonarCisco

7507Cisco

7505Cisco

7500

(7513)Icons:CiscoProducts(Cont.)EdgeLabel

Switch

Router

withNetFlowSystem

ControllerCisco

Directory

ServerIP

Standard

andOld

(Some

Prefer)MultilayerSwitch,

withandwithoutText

andSubduedEdgeLabelSwitch

RouterCisco1000Voice-Enabled

AccessServer

(orVoice-EnabledCommunicationsServer)Voice-

Enabled

RouterCisco6920

RateMuxApplicationControlEngineProgramSwitchRouter

withTDMADMFirewall

Services

ModuleCiscoUnityExpressCiscoUnityServerIntroduction本章主要討論識(shí)別和處理DU或PDU來進(jìn)行的中繼協(xié)議內(nèi)中繼和協(xié)議外中繼的討論中繼算法和性能中繼排隊(duì)模型不討論物理層中繼物理層還未達(dá)到識(shí)別和處理PDU的級(jí)別10Relay@PhysicalLayer物理層依靠外部規(guī)則中繼bit流11Bit流無信息可用，只能按預(yù)定規(guī)則進(jìn)行中繼Bit流入Bit流出預(yù)設(shè)中繼方向(電路交換)共享信道單入單出信號(hào)增強(qiáng)或變換RelayModel層間接口第二章給出了層間接口模型ICI、DU及SAP按照服務(wù)提供者(SP)規(guī)定的ICI提供相應(yīng)的參數(shù)Relay按照SP要求的ICI，接收、中繼轉(zhuǎn)發(fā)DU或PDU12phyMACphyMACphyMACphyMACRelayphyMACphyMACphyMACphyMACIPRelay協(xié)議外中繼協(xié)議內(nèi)中繼RelayModel外中繼一般化模型：不同鏈路層實(shí)體間的中繼，因此各個(gè)接口的ICI的內(nèi)容和形式都不相同Relay從一個(gè)接口接收DU，用輸入ICI計(jì)算中繼出口形成輸出ICI，轉(zhuǎn)發(fā)DU13phyLink4phyLink3phyLink2phyLink1RelayICI1ICI2ICI3ICI4【ICI0，DU】考察中繼轉(zhuǎn)發(fā)和上層實(shí)體發(fā)送DU的差別ICI0(ICI1

，ICI2

，ICI3

，ICI4）協(xié)議棧基本特性，無難題(ICI1

，ICI2

，ICI3

，ICI4)(ICI1

，ICI2

，ICI3

，ICI4)(不同ICI間轉(zhuǎn)換，外中繼最大難題)DUH1DUHk外中繼考察中繼前后報(bào)文變化RelayModel外中繼實(shí)例14phyMACphyMACphyMACphyMACRelayICI1ICI2ICI3ICI4以太網(wǎng)交換機(jī)各ICI相同格式，均為:[目的、源MAC地址]Relay沿用ICI內(nèi)容即可計(jì)算出口phyPPPphyPPPphyMACphyMACRelayICI1ICI2ICI3ICI4混合中繼PPP的ICI內(nèi)容為空如何考慮中繼方向算法phyPPPphyPPPphypppphypppRelayICI1ICI2ICI3ICI4PPP中繼PPP的ICI內(nèi)容為空如何考慮中繼方向算法不是所有協(xié)議都能實(shí)現(xiàn)外中繼RelayModel混合中繼和多PPP中繼15【ICI(源、目的MAC),DU】【ICI(源、目的MAC),DU】【ICI(null),DU】【ICI(null),DU】根據(jù)什么為DU選擇出口？根據(jù)什么，為ICI添加源、目的MACPPP入PPP出MAC入MAC出根據(jù)什么為DU選擇出口？PPP入PPP出多PPP中繼MACPPP混合中繼一般而言，除了像以太網(wǎng)這種特例外，外中繼幾乎是難以實(shí)現(xiàn)的，特別是多種不同協(xié)議之間的外中繼，幾乎是不可實(shí)現(xiàn)的RelayModel外中繼實(shí)例—網(wǎng)絡(luò)層的外中繼16IPv4IPv6RelayH4DUH6DU中繼DU，首部發(fā)生了切換外中繼重要的特性之一：中繼可跨接到不同的網(wǎng)絡(luò)上。外中繼似乎是異種網(wǎng)絡(luò)互聯(lián)的關(guān)鍵要素！如何克服不可實(shí)現(xiàn)與異種互聯(lián)需求的矛盾？關(guān)鍵問題：如何確定源和目的主機(jī)的地址（Iv4Iv6）RelayModel內(nèi)中繼17phyPPPphyPPPphyMACphyMACIPRelayIP的中繼的算法依據(jù)是IP分組的首部信息，與ICI無關(guān)(此例中，與鏈路層實(shí)體及它們的ICI無關(guān))ICI1ICI2ICI3ICI4H4DUH4DU輸出時(shí)，與外中繼不同點(diǎn)在于：不是用ICI計(jì)算中繼方向；而是獨(dú)立、自成體系的中繼方向算法(是協(xié)議功能的組成部分)中繼完整的IP報(bào)文18RelayModel鏈路層內(nèi)中繼FR、ATM、MPLS采用內(nèi)中繼有人認(rèn)為是鏈路層、也有人認(rèn)為應(yīng)該是網(wǎng)絡(luò)層每個(gè)接口都需要獨(dú)立的bit流上的幀同步功能(這是鏈路層的功能)。鏈路協(xié)議本身功能簡化到“基本無”網(wǎng)絡(luò)層把中繼功能下放給鏈路層實(shí)現(xiàn)，自己僅保留路由控制功能路由控制網(wǎng)絡(luò)層還是鏈路層？Phy幀同步差錯(cuò)控制Phy幀同步差錯(cuò)控制Phy幀同步差錯(cuò)控制Phy幀同步差錯(cuò)控制Phy幀同步差錯(cuò)控制relay內(nèi)還是外？RelayModel內(nèi)、外中繼發(fā)生在哪些層次上任意層次上都可有外中繼發(fā)生網(wǎng)絡(luò)層有內(nèi)中繼19RelayRelayRelayRelayRelayPhyLinkNetworkTransportApplication內(nèi)中繼鏈路傳輸，一般不考慮中繼功能端到端功能，協(xié)議不再考慮中繼功能內(nèi)中繼RelayModel高層的中繼QQ即時(shí)通信是一種應(yīng)用層內(nèi)中繼TCP橋接橋接兩段TCP，內(nèi)還是外中繼？20QQ服務(wù)器門戶網(wǎng)站文件服務(wù)器TCP1TCP2TCP橋接RelayModel信息網(wǎng)絡(luò)更多的應(yīng)用層或傳輸層中繼需要我們來開拓采用內(nèi)中繼還是外中繼技術(shù)？21RelayModel小結(jié)22phyMACphyMACphyMACphyMACRelayphyMACphyMACphyMACphyMACIPRelayRelay多入多出時(shí)，需要某些信息來支撐中繼算法在某些層、或在不同協(xié)議間采用外中繼中繼信息來源于ICI中繼的內(nèi)容是DU(上層的PDU)不同協(xié)議間中繼存在巨大障礙中繼是協(xié)議的內(nèi)在功能中繼信息是自身PDU定義的中繼的內(nèi)容是自身的PDU中繼前后都是自己的對(duì)等實(shí)體外中繼的繼續(xù)討論IPv4/IPv6網(wǎng)關(guān)23IPv4IPv6Relay地址映射問題IPv6IPv4TCP/UDPTCP/UDP應(yīng)用實(shí)體應(yīng)用實(shí)體應(yīng)用層數(shù)據(jù)包含IP地址的問題，如DNS：從域名解析IP地址；QQ：消息中包含IP地址；FTP：報(bào)文中包含IP地址在應(yīng)用層中出現(xiàn)的IP地址也需要轉(zhuǎn)換！24外中繼的繼續(xù)討論IPv4/IPv6中繼IPv6地址中劃出一部分直接映射成IPv4的地址IPv6訪問這些地址被中繼直接轉(zhuǎn)換成IPv4地址IPv4只能訪問IPv6的極少部分站點(diǎn)(中繼中人工設(shè)定)無法用IPv6地址，需要借助于DNS(域名系統(tǒng))中繼需要包含對(duì)DNS的轉(zhuǎn)換(應(yīng)用的轉(zhuǎn)換+中繼)(DNSALG)Web中含域名系統(tǒng)中繼需要處理WWW數(shù)據(jù)中的域名轉(zhuǎn)換(WWWALG)FTP中包含域名中繼需要處理FTP數(shù)據(jù)中的域名轉(zhuǎn)換(FTPALG)V4RelayV6IPv4網(wǎng)絡(luò)IPv6網(wǎng)絡(luò)DNSALGWWWALGFTPALGQQALG外中繼的繼續(xù)討論P(yáng)PP實(shí)現(xiàn)以太網(wǎng)遠(yuǎn)程橋接將兩邊的以太網(wǎng)連接成一個(gè)整體25PPP信道MACPPPphyphyRelayMACPPPphyphyRelay問題分析外中繼的繼續(xù)討論P(yáng)PP實(shí)現(xiàn)以太網(wǎng)遠(yuǎn)程橋接有PPPoE，是不是可以有EoPPP？以太網(wǎng)交換機(jī)模型+EoPPP模型遠(yuǎn)程橋接模型26MACPPPMACPPPMACMACRelayMACMACRelayPPPMACPPPphyphyMACPPPphyphyRelayMACMACRelay拓展：MAC可以放在UDP上嗎？是不是可以用IP網(wǎng)絡(luò)來橋接以太網(wǎng)？PPPDUEDUE27外中繼的繼續(xù)討論分布式網(wǎng)橋的中繼模型IP網(wǎng)絡(luò)MACMACMACMACMACMAC??MACMACMAC?28802.3—802.11中繼(WiFi)兩者協(xié)議不同，但具有相同的地址格式和服務(wù)原語802.11：無線信道上的以太網(wǎng)(競(jìng)爭(zhēng)信道)DASATData802.3FrameTData802.11FrameFCDurDASAAPTDataFCDurAPDASASADAAPABABTDataFCDurDAIDSACC802.11802.3具有完全相同的服務(wù)原語網(wǎng)絡(luò)ID外中繼的繼續(xù)討論外中繼更多的問題29Entity-AEntity-BRelay不同中繼信息之間的轉(zhuǎn)換AB不同MTU，A、B是否有分段/組合功能？Entity-BEntity-ASAP-ASAP-B不同SAP定義，是否能找到對(duì)應(yīng)關(guān)系？不同地址空間定義，是否能找到對(duì)應(yīng)關(guān)系？外中繼的繼續(xù)討論TCP和UDP如何實(shí)現(xiàn)外中繼？前面的TCP橋接的例子30TCPTCPRelayUDPUDPRelay錯(cuò)誤結(jié)構(gòu)描述TCP/UDPSAP在不同SAP之間中繼TCP通信連接TCP通信連接端點(diǎn)端點(diǎn)端點(diǎn)端點(diǎn)外中繼的繼續(xù)討論練習(xí)為了防止外部直接訪問文件服務(wù)器(安全考慮)，所有的文件上下載都必須經(jīng)過一臺(tái)關(guān)口控制服務(wù)器。該關(guān)口服務(wù)器的功能是接收外部連接，確認(rèn)正常情況下，關(guān)口服務(wù)器發(fā)起對(duì)文件服務(wù)器的連接，然后將這兩個(gè)TCP連接起來，中繼它們之間傳遞的信息。并且在它們通信過程中，觀察通信狀況，以便在出現(xiàn)有害現(xiàn)象時(shí)，及時(shí)切斷它們的通信，達(dá)到保護(hù)服務(wù)器的目的。試編寫這樣的軟件，逐步實(shí)現(xiàn)更多功能31以太網(wǎng)與TokenRing間轉(zhuǎn)換網(wǎng)關(guān)鏈路層中繼(協(xié)議轉(zhuǎn)換)網(wǎng)絡(luò)層中繼(如IP中繼)幾種典型中繼設(shè)備分析32802.3802.5Relay802.3802.5中繼要求1、兩種網(wǎng)的地址格式一致2、兩種網(wǎng)的SAP使用規(guī)則一致可用于運(yùn)載任意網(wǎng)絡(luò)層協(xié)議802.3802.5802.3802.5IPIPIP中繼條件：1、IP協(xié)議的內(nèi)容功能2、中繼與兩種網(wǎng)絡(luò)無關(guān)網(wǎng)絡(luò)層協(xié)議僅有IP中繼DU中繼IP報(bào)文33上頁協(xié)議轉(zhuǎn)換問題1.reformattheframeandcomputenewchecksum2.Reversethebitorder3.Copythepriority,meaningfulornot4.Generateafictitiouspriority5.Drainthering(somehow)6.Discardpriority7.SetAandCbits8.Worryaboutcongestion(fasttoslowLAN)9.WorryabouttokenhandoffACKbeingdelayedorimpossible10.PanicifframeistoolongfordestinationLAN1，41,2,4,81,5,8,9,1091,2,3,8,9,101,2,5,6,7,101,2,3,6,76,7802.3802.4802.5802.5802.3802.4幾種典型中繼設(shè)備分析以太網(wǎng)遠(yuǎn)程連接鏈路層中繼網(wǎng)絡(luò)層中繼一定要用鏈路層中繼(上層不是IP協(xié)議）34PPP信道802.3PPPRelayPPP中繼DU802.3Relay中繼DU由于PPP的ICI信息無助于中繼，該方案是不可實(shí)現(xiàn)的802.3PPPPPP802.3IPIP中繼是IP協(xié)議實(shí)現(xiàn)的，PPP和802.3互不相關(guān)，不存在轉(zhuǎn)換問題，方案可實(shí)現(xiàn)802.3PPP802.3Relay802.3PPP802.3Relay以太網(wǎng)間可中繼以太幀作為DU封裝到PPP中，不是轉(zhuǎn)換PPP僅是攜帶DU而已(EoPPP)幾種典型中繼設(shè)備分析ADSL接入鏈路層中繼網(wǎng)絡(luò)層中繼鏈路層中繼可實(shí)現(xiàn)方案35EtherPPP/ADSL主機(jī)采用以太網(wǎng)接口是因?yàn)闆]有其它高速接口可用802.3ADSLRelay中繼DUADSLModem同理，不可實(shí)現(xiàn)802.3PPPADSLPPPIPADSL路由器在IP上中繼，802.3和PPP與中繼無關(guān)，802.3ADSLRelayADSLModem兩端口的PPP中繼—可實(shí)現(xiàn)(PPPoE)PPPPPP802.3PPP中繼的性能特性中繼的時(shí)延特性中繼的固有時(shí)延T0T0=信道速率/幀長度固有時(shí)延相當(dāng)于增加了信道長度處理時(shí)延T1Relay接收完DU后，為其選擇出口的計(jì)算時(shí)延(計(jì)算量分析)處理時(shí)延T1直接影響中繼設(shè)備的吞吐性能若中繼設(shè)備為一個(gè)DU選擇出口的計(jì)算需要1us，則該設(shè)備的最大吞吐量為1MPDU/s排隊(duì)時(shí)延T2接收的DU排隊(duì)等待處理、排隊(duì)等待發(fā)送的時(shí)延排隊(duì)時(shí)延反映網(wǎng)絡(luò)的流量特性對(duì)通信的影響(排隊(duì)論分析)若多個(gè)接口的DU要從一個(gè)接口出，超出接口通信流量，引起排隊(duì)T0、T1基本是固定值，T2則是隨機(jī)的結(jié)論：中繼對(duì)報(bào)文傳輸帶來了隨機(jī)的延時(shí)36RelayDevice固有時(shí)延中繼時(shí)延排隊(duì)時(shí)延T0T1T1T2中繼的吞吐性能吞吐性能指標(biāo)中繼設(shè)備每秒從所有接口發(fā)出PDU的最大值pps（pdupersecond)DU入DU出接收處理(并行)發(fā)送處理(并行)中繼處理(串行)Relay設(shè)：Relay處理一個(gè)PDU所需的時(shí)間是T1，則中繼設(shè)備的最大吞吐量為:Thr=1/T1（pps）------中繼系統(tǒng)本身的最大能力，與速率無關(guān)，與排隊(duì)無關(guān)38RelayAlgorithm中繼分類中繼內(nèi)中繼外中繼連接模式的中繼無連接模式的中繼連接模式的中繼無連接模式的中繼連接--無連接間的中繼--PDU提供的連接ID做中繼線索--PDU源/目的地址做中繼線索--ICI提供源/目的地址做中繼線索--ICI提供連接ID做中繼線索--ICI中繼線索？？？無連接模式的中繼性能鏈路層、網(wǎng)絡(luò)層的中繼各PDU之間是獨(dú)立無關(guān)的常規(guī)中繼方式中繼轉(zhuǎn)發(fā)表39DU入DU出Relay依靠ICI(外中繼)或PDU首部(內(nèi)中繼)的地址信息，選擇出口目的地址出口地址12。。。1地址n4中繼轉(zhuǎn)發(fā)表(FT)轉(zhuǎn)發(fā)：DU出口=FT[目的地址].出口無連接模式的中繼性能轉(zhuǎn)發(fā)性能問題(DU出口=FT[目的地址].出口)FT表有多大？以太網(wǎng)地址48bits、IP地址32bits、IPv6地址128bits需要248(=218*230=256T)、232、2128條表項(xiàng)40415.PDUthroughputPDUthroughputperformanceNo.ofPDUpersecondRelay模塊每秒的PDU處理能力基本描述假設(shè)中繼系統(tǒng)有K個(gè)全雙工接口每個(gè)接口最大輸入能力是Ri個(gè)PDU/秒(pps，i=1，2,…,K)最大總輸入量為Rin=∑Ri當(dāng)輸出量也到達(dá)Rout=Rin時(shí)，稱中繼系統(tǒng)可線速工作實(shí)際系統(tǒng)中，Rout

可能遠(yuǎn)遠(yuǎn)小于Rin原因：Relay的處理能力不足本節(jié)探討Relay能力不足的原因及有關(guān)技術(shù)PDUinPDUOutRelayR1R2RKr1r2rK42RelayProcessingModelR1R2RKr1r2rK查表運(yùn)算中繼轉(zhuǎn)發(fā)表Qi1Qi2QiKQo1Qo2QoK輸入隊(duì)列輸出隊(duì)列并發(fā)輸入并發(fā)輸出串行運(yùn)算查表運(yùn)算速率P查表≥∑Ri=Rin（pps）輸入和輸出是K個(gè)接口并發(fā)處理的，只有中繼處理是串行進(jìn)行的(逐個(gè)PDU處理)。中繼系統(tǒng)要到達(dá)線速性能的基本條件：43RelayProcessingModel輸入輸出不匹配部分輸出排隊(duì)等候，而其它輸出隊(duì)列為空低效查表算法每秒為K個(gè)分組查表Rout=K<<Rin低效原因：表項(xiàng)太大R1R2RK查表運(yùn)算中繼轉(zhuǎn)發(fā)表Qi1Qi2QiKQo1Qo2QoKR1R2RK查表運(yùn)算中繼轉(zhuǎn)發(fā)表Qi1Qi2QiKQo1Qo2QoK查表算法是中繼系統(tǒng)性能的關(guān)鍵技術(shù)之一RelayProcessingModel采用地址中繼的表項(xiàng)IP地址32bit，若保存全部IP地址，至少需要4G*4的存儲(chǔ)空間IPv6地址128bit，幾乎不可能存儲(chǔ)全部地址MAC地址48bit，幾乎不可能存儲(chǔ)全部地址縮減地址存儲(chǔ)IP地址，存儲(chǔ)子網(wǎng)地址，涵蓋全部地址空間MAC地址？只存儲(chǔ)活動(dòng)主機(jī)的MAC地址？主機(jī)有變化，不行！分配一個(gè)足夠大(對(duì)網(wǎng)絡(luò)而言)又足夠小(對(duì)地址空間而言)的存儲(chǔ)空間，如2k、4k、8k個(gè)MAC存儲(chǔ)空間4445查表算法運(yùn)算量分析假定報(bào)文輸入最大速率為R（pps)中繼表有N條表項(xiàng),每條表項(xiàng)的需要CPU的運(yùn)算量為m則線速工作所需的查表運(yùn)算量為：Proc=R*(N/2)*m中繼查表運(yùn)算量實(shí)例一臺(tái)16口100Mbps以太網(wǎng)交換機(jī)、8k條表項(xiàng)100Mpps以太網(wǎng)最大報(bào)文速率=148.8kpps每條表項(xiàng)需要占用1個(gè)單元運(yùn)算量該交換機(jī)需要的查表運(yùn)算量為Proc=1*16*148.8k*8k/2=9523M=9.523G運(yùn)算單元(每個(gè)運(yùn)算單元需多少條CPU指令？)(每條指令需多少CPU時(shí)鐘？)(目前計(jì)算機(jī)的速度是多少？)46以太網(wǎng)交換機(jī)的查表算法以太網(wǎng)交換機(jī)不能采用逐項(xiàng)匹配查表算法Hash查表算法直接獲得目的MAC地址的輸出端口輸出端口=Table[Hash(Mac)]輸入輸出過程pdu=pk_get(in_strm);pk_send(pdu,table[hash(pdu->dMac)];Hash算法只需1次查表算法16口100M以太網(wǎng)交換機(jī)所需的查表運(yùn)算量Proc=16*148.8k=23808k=23.8M運(yùn)算單元以太網(wǎng)交換機(jī)無法回避的問題不同MAC產(chǎn)生同一hash值OutIFHashh12hMac8K個(gè)表項(xiàng)Hash索引表(48bits)(13bits)47中繼轉(zhuǎn)發(fā)表以太網(wǎng)交換機(jī)的排隊(duì)模型R1R2RK查表運(yùn)算Qi1Qi2QiKQo1Qo2QoK48IP路由器中的查表算法不能采用Hash算法(地址模糊)需要精確匹配每個(gè)子網(wǎng)地址、出口位置、下一網(wǎng)關(guān)IP地址數(shù)量IPv4–232，IPv6--2128IP路由器需要掌握每個(gè)IP地址的出口和方向IP路由表項(xiàng)有多大？IP路由器性能要求普通路由器：幾百~幾兆pps中心路由器：幾十~幾百及上千兆pps49PDUthroughputIP路由器查表算法分級(jí)(索引+查表)算法，以減少查表次數(shù)第一字節(jié)索引，將表分為256個(gè)子表，長度減少256倍，…優(yōu)化索引表結(jié)構(gòu)高速緩存將最近使用過的表項(xiàng)存入(較小的)高速緩存，提高查表命中率先查高速緩存，沒有時(shí)再按常規(guī)查詢IP交換機(jī)高速緩存硬件查表分級(jí)查表軟件實(shí)現(xiàn)分級(jí)查表算法示意圖索引索引順序查找高速緩存IP交換機(jī)(硬件中繼)硬件查表軟件查表特別現(xiàn)象：首次通信速度慢50PDUthroughputIP路由器查表算法分布式中繼和查表板內(nèi)中繼，僅需較小的板內(nèi)路由表(提升速度)板間中繼，全局路由表(硬件緩存+軟件查表)板內(nèi)路由表由全局路由維持和動(dòng)態(tài)更新LLLLLLLLLLLLLLLLIPrelayIPrelayIPrelayIPrelay板內(nèi)中繼板間中繼IP路由器51PDUthroughputMPLS中繼算法20bit標(biāo)簽值，標(biāo)簽總量220=1M每個(gè)報(bào)文流用同一個(gè)標(biāo)簽，只從同一個(gè)入口進(jìn)每個(gè)入口可以有多個(gè)流，各個(gè)流的標(biāo)簽值不同每個(gè)標(biāo)簽對(duì)應(yīng)一個(gè)出口，報(bào)文根據(jù)標(biāo)簽值從對(duì)應(yīng)出口中繼出去voidMPLSRelay(in,mp){LB=mp.LBL;if(tab[LB].Lnk1==in)Out=tab[LB].Lnk2;elseOut=tab[LB].Lnk1;SendTo(mp,Out);}DULBMPLSPDUMPLS報(bào)文中繼只需一次查表采用硬件中繼可輕松實(shí)現(xiàn)高達(dá)上百G吞吐性能52PDUthroughput—小結(jié)中繼類型根據(jù)查表方式分為：串行中繼、并行中繼串行中繼并行中繼并行中繼

查表參數(shù)：流標(biāo)識(shí)(ID)

查表方式：流標(biāo)識(shí)索引

查表速度：接口最大報(bào)文速率

缺點(diǎn)：同一個(gè)流須來自同一接口

優(yōu)點(diǎn)：高速中繼，可硬件實(shí)現(xiàn)串行中繼查表參數(shù)：目的地址查表方式：逐項(xiàng)搜索查表速度：報(bào)文速率*接口數(shù)*表深度缺點(diǎn)：查表速度要求太高無法實(shí)現(xiàn)優(yōu)點(diǎn)：一個(gè)報(bào)文流可從多個(gè)接口進(jìn)入6RelaytoSwitchIP路由器采用串行中繼，阻礙了向高性能發(fā)展提高路由器的性能方法提高中繼性能減少路由表項(xiàng)數(shù)提高中繼性能—IP交換技術(shù)從設(shè)備上提升性能從組網(wǎng)方式上提升性能減少路由表項(xiàng)—路由聚合、網(wǎng)絡(luò)拓?fù)渚酆?3IP交換技術(shù)1996年，是IP從中繼轉(zhuǎn)向路由的年代Ipsilon公司提出IP交換概念(1996)由IP路由器對(duì)ATM交換機(jī)實(shí)施控制當(dāng)檢測(cè)到大容量、長時(shí)間的業(yè)務(wù)時(shí)，IP路由器為該業(yè)務(wù)建立一條ATM傳輸路徑54IP中繼路徑為業(yè)務(wù)流建立ATM高速路徑將IP報(bào)文經(jīng)過多個(gè)路由器的路徑，轉(zhuǎn)變成一條ATM的傳輸路徑，從而實(shí)現(xiàn)了IP報(bào)文的快速傳輸路由器控制交換機(jī)IPATMATM通道控制源目的報(bào)文通道IP交換技術(shù)IBM提出聚合路由的IP交換技術(shù)(1996)在ATM網(wǎng)絡(luò)上建立多條點(diǎn)到點(diǎn)/點(diǎn)到多點(diǎn)的交換通路IP將路由表項(xiàng)通過聚合，映射到這些交換通路上55ATM網(wǎng)絡(luò)IBM的方案與Ipsilon的方案相比，對(duì)ATM網(wǎng)絡(luò)的部署和利用更簡單且更充分不需要探測(cè)大容量業(yè)務(wù)流不需要為業(yè)務(wù)流動(dòng)態(tài)建立通道路由聚合有效減少了表項(xiàng)數(shù)目沒有區(qū)分不同流的不同需求，相對(duì)粗糙業(yè)務(wù)流映射到幾個(gè)通路上IPATMMAC通道號(hào)+IP報(bào)文IP交換技術(shù)Cisco提出Tag-Switch用標(biāo)記的思想把尋址和轉(zhuǎn)發(fā)統(tǒng)一起來將路由過程和轉(zhuǎn)發(fā)過程分離56MACMACMACMAC尋址尋址尋址尋址路由Tag-switch(轉(zhuǎn)發(fā))IP實(shí)體路由器Tag+IP報(bào)文路由信息分發(fā)路由接口板思科的方案重點(diǎn)在不改變IP網(wǎng)絡(luò)的結(jié)構(gòu)下，提高路預(yù)期的吞吐率基于tag的高速交換IP交換技術(shù)IETF對(duì)幾種技術(shù)進(jìn)行綜合和標(biāo)準(zhǔn)化MPLS，Multi-ProtocolLabelSwitch57LBDUATM的通道使用過于復(fù)雜(VPI,VCI),ATM信元開銷過大Label用于中繼轉(zhuǎn)發(fā)(Cisco)，用于IP及其它協(xié)議用Label可建立任意兩點(diǎn)間的通道(IBM)可用Label動(dòng)態(tài)建立通道(Ipsilon)首部可嵌套實(shí)現(xiàn)多級(jí)通道首部一級(jí)通道二級(jí)通道二級(jí)通道LB1lbn587.RelayQoSQualityofServiceDelayfeatureJitter(Delayvariance)PDUflowFairnessHeavyloadandlightloadperformance問題描述一個(gè)大流量的數(shù)據(jù)和一個(gè)小流量的語音(如VoIP)同時(shí)經(jīng)過中繼系統(tǒng)，并從同一個(gè)出口送向目的地?cái)?shù)據(jù)流量雖大，但允許出現(xiàn)一定的延遲語音流量雖小，但對(duì)延遲有嚴(yán)格的要求大流量的數(shù)據(jù)對(duì)小流量的語音產(chǎn)生什么影響？采取什么措施才能讓二者都能得到滿意的效果？語音數(shù)據(jù)59QueuingTheory排隊(duì)模型無限容量的隊(duì)列，PDU(客人)隨機(jī)到達(dá)并排隊(duì)。侍者按先到先服務(wù)的方式為客人服務(wù)，每次服務(wù)一位客人。客人到達(dá)時(shí)間分布函數(shù)λ:客人平均到達(dá)率Pn(t):在時(shí)間t內(nèi)到達(dá)n位客人的概率每位客人服務(wù)時(shí)間長度(PDU長度)分布函數(shù)1/u:為平均服務(wù)時(shí)間長度侍者隊(duì)列60QueuingTheoryPDU中繼排隊(duì)描述PDU到達(dá)時(shí)間分布(均值為λ)PDU長度(均值為1/u)服務(wù)61QueuingTheorySomeResults隊(duì)列長度與PDU到達(dá)概率、PDU長度相關(guān)，也與信道速率有關(guān)隊(duì)列長度=n的概率為Pn平均隊(duì)列長度平均排隊(duì)時(shí)間C為信道速率，為信道的最大PDU速率，ρ為信道占用率62QueuingTheory考查平均排隊(duì)時(shí)間當(dāng)信道占用率低于50%時(shí)排隊(duì)時(shí)間較小(少于1個(gè)PDU)當(dāng)信道占用率達(dá)70%以上排隊(duì)時(shí)間急劇加大中繼系統(tǒng)QoS當(dāng)信道占用率較大時(shí)，將對(duì)中繼的服務(wù)質(zhì)量帶來重大影響前面(數(shù)據(jù)、語音)例子，數(shù)據(jù)通信量將嚴(yán)重影響語音通信質(zhì)量0.511510ρρ0.10.20.30.40.50.60.70.80.90.99ρ/(1-ρ)1/91/43/72/313/27/3499963BacktoRelayQoS解決QoS的途徑之一是采用多個(gè)隊(duì)列，將要求不同服務(wù)質(zhì)量的PDU分開排隊(duì)(分類)，侍者區(qū)分處理(隊(duì)列調(diào)度)。隊(duì)列侍者[分類][調(diào)度]64經(jīng)典排隊(duì)算法—PQPQ（PriorityQueuing,優(yōu)先級(jí)排隊(duì)）PDU按優(yōu)先級(jí)排到不同的隊(duì)列中侍者首先服務(wù)最高優(yōu)先級(jí)的隊(duì)列，只有優(yōu)先級(jí)高的隊(duì)列為空時(shí)，才服務(wù)下一優(yōu)先級(jí)的隊(duì)列研討PQ對(duì)中繼QoS的貢獻(xiàn)(定性分析話音和數(shù)據(jù)的中繼效果)PQ有哪些不足過于重優(yōu)輕慢的問題PQP0P1P2P3P0空P1空P2空P3空取出、發(fā)送1個(gè)PDUNNNN經(jīng)典排隊(duì)算法—PQ低優(yōu)先級(jí)的報(bào)文被拖延現(xiàn)象65PQ優(yōu)先級(jí)高中低輸出結(jié)果66經(jīng)典排隊(duì)算法—CQCQ（ClassQueuing,分類排隊(duì))將單一優(yōu)先級(jí)分類改變成一般分類概念進(jìn)行排隊(duì)優(yōu)先級(jí)、流量、實(shí)時(shí)性等為各隊(duì)列分配適當(dāng)?shù)牧髁勘壤~度調(diào)度遠(yuǎn)未達(dá)到比例額度的隊(duì)列中的PDU發(fā)送調(diào)度算法細(xì)節(jié)如何(1額度=?字節(jié))CQ的效果如何對(duì)語音和數(shù)據(jù)進(jìn)行分類？隊(duì)列額度高、隊(duì)列短問題需要相當(dāng)量的手工配置和調(diào)節(jié)CQC0C1C2C3C0？C1？C2？C3？取出、發(fā)送1個(gè)PDUNNNN是否已達(dá)到規(guī)定的流量分類67經(jīng)典排隊(duì)算法—FQFQ（FairQueuing，公平隊(duì)列調(diào)度）采用循環(huán)調(diào)度，保證各個(gè)隊(duì)列完全公平的（流量基本均等）調(diào)度方式規(guī)則，易于硬件實(shí)現(xiàn)將不同的傳輸(流量、實(shí)時(shí)性)需求轉(zhuǎn)變?yōu)榕抨?duì)算法討論：數(shù)據(jù)和語音的排隊(duì)方式FQF0F1F2F3F(i)空取出、發(fā)送1個(gè)PDUi++N選擇68經(jīng)典排隊(duì)算法—WFQWFQ（WeightedFQ，加權(quán)FQ）FQ通過加權(quán)，對(duì)各個(gè)隊(duì)列實(shí)現(xiàn)一定水平的配額分配。WFQQ0Q1Q2Q3W0W1W2W3F(i)？取出、發(fā)送1個(gè)PDUi++非空且未達(dá)到加權(quán)的流量dWi選擇各個(gè)隊(duì)列的流量分別為：W0，W1，W2，W3，…69更多的排隊(duì)算法CBWFQ基于類的加權(quán)公平隊(duì)列，混合的算法，集中了CQ和WFQ的優(yōu)點(diǎn)，可以支持N個(gè)流量類，每個(gè)流量類均有自己的隊(duì)列，隊(duì)列使用WRR算法進(jìn)行輪詢。是數(shù)據(jù)應(yīng)用中的很高效的算法，但不能為實(shí)時(shí)應(yīng)用提供嚴(yán)格的優(yōu)先級(jí)保障。LLQ低延時(shí)隊(duì)列。集成了CQ、PQ、WFQ的優(yōu)點(diǎn)。也可稱為PQ-CBWFQ。LLQ在CBWFQ的基礎(chǔ)上增加了嚴(yán)格的優(yōu)先級(jí)保證。常用于語音網(wǎng)絡(luò)。70排隊(duì)機(jī)制的算法模型排隊(duì)算法的一般模型包括三個(gè)算法分類—進(jìn)入不同的隊(duì)列算法調(diào)度—輸出調(diào)度算法資源—隊(duì)列緩沖區(qū)資源分配算法分類調(diào)度分類算法：源/目的地址協(xié)議流類型

…調(diào)度算法：

QoS

流量實(shí)時(shí)性

…緩沖區(qū)資源分配71隊(duì)列管理算法RED（RandomEarlyDetect，隨機(jī)早期檢測(cè)）當(dāng)隊(duì)列長度達(dá)到預(yù)設(shè)值后，按一定概率隨機(jī)丟棄進(jìn)入隊(duì)列的PDU，較好地控制了平均隊(duì)列長度輸出排隊(duì)（OQ，OutputQueuing)輸入處理后直接在輸出端口排隊(duì)N端口要求緩沖區(qū)以N倍速工作，高速下難實(shí)現(xiàn)輸入排隊(duì)（IQ，InputQueuing）在輸入端排隊(duì)，輸出有空時(shí)直接遞交發(fā)送受隊(duì)列頭阻塞問題制約輸入輸出聯(lián)合排隊(duì)（CIOQ,CombinedIOQ)掌握輸入輸出的擁塞情況算法復(fù)雜RED72網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）僅中繼系統(tǒng)的QoS是不夠的使用排隊(duì)和緩沖區(qū)管理提高自身的QoS需要網(wǎng)絡(luò)協(xié)議的QoS功能上的配合不同的應(yīng)用需要不同的QoS為中繼系統(tǒng)提供正確的QoS能力73網(wǎng)絡(luò)的QoS—例：IP的QoSIETF定義的IPQoS標(biāo)準(zhǔn)IntServ利用IP的ToS，針對(duì)每個(gè)流設(shè)置所需的QoSToS：TypeofServiceDelay,Throughput,DiffServ取代ToS，重新定義為DS。定義了相對(duì)簡單、粒度粗的QoS類，對(duì)同類的流進(jìn)行聚合控制。協(xié)議QoS為中繼系統(tǒng)實(shí)施QoS提供了具體措施各個(gè)IP路由器上獨(dú)立實(shí)施MPLS交換網(wǎng)統(tǒng)一實(shí)施74RelayQoS—小結(jié)排隊(duì)理論排隊(duì)輸出方式可能對(duì)QoS產(chǎn)生重大影響實(shí)時(shí)性問題、公平性問題通過不同的排隊(duì)調(diào)度，可提高中繼的QoS性能中繼在輸出端的排隊(duì)處理FIFOPQCQ簡單處理優(yōu)先隊(duì)列處理一般性的分類處理FQWFQCBWFQ公平性加權(quán)公平分類的加權(quán)公平網(wǎng)絡(luò)的QoS中繼的QoS僅有局部意義，網(wǎng)絡(luò)QoS則是全局的意義網(wǎng)絡(luò)的QoS可能犧牲某些中繼的QoS758.Multi-LayerSwitch在多個(gè)層次同時(shí)實(shí)現(xiàn)中繼交換首先需要回答這樣的問題：在一連串的中繼過程中，中繼是如何結(jié)束的？在端系統(tǒng)上結(jié)束中繼中繼系統(tǒng)可不可能也作為端系統(tǒng)？MACMACMACMACRelayIPEntityLLLLLRelayIPIP中繼MAC中繼MAC端系統(tǒng)中繼系統(tǒng)MAC端系統(tǒng)IPIP端系統(tǒng)中繼系統(tǒng)76Multi-LayerSwitch中繼系統(tǒng)作為端系統(tǒng)MACMACMACMACRelayIPEntityLLLLLRelayIP如果目的MAC地址是中繼系統(tǒng)的MAC地址之一--表示什么意思？--該如何處理？如果目的IP地址是中繼系統(tǒng)的一個(gè)IP地址--表示什么意思？--該如何處理？MPLS交換沒有此可能性--標(biāo)簽不帶尋址信息--只有在邊界交換機(jī)上才停止中繼77Multi-LayerSwitch中