【文章內(nèi)容簡介】 幀后，在MAC地址表中查找數(shù)據(jù)幀中的目的MAC地址。如果找到，就將該數(shù)據(jù)幀發(fā)送到相應的端口；如果找不到，就向所有的端口發(fā)送。同時利用接收數(shù)據(jù)幀中的源MAC地址來建立MAC地址表。選路和轉(zhuǎn)發(fā)的區(qū)別主要是，選路在IP層，根據(jù)目的IP地址找到出接口；轉(zhuǎn)發(fā)在數(shù)據(jù)鏈路層，根據(jù)MAC地址對數(shù)據(jù)進行轉(zhuǎn)發(fā)。另外，轉(zhuǎn)發(fā)表和路由表不同，轉(zhuǎn)發(fā)表中的一行包括從網(wǎng)絡號到發(fā)出接口的映射和一些MAC信息，而路由表是由路由選擇算法建立的一個表，它通常包含從網(wǎng)絡號到下一跳IP地址的映射，轉(zhuǎn)發(fā)表可以由特殊的硬件來實現(xiàn)，而路由表很少這樣。為了實現(xiàn)三層交換技術，交換機將維護一張至少包括“目的IP地址，下一跳MAC地址”在內(nèi)的硬件轉(zhuǎn)發(fā)表。當交換機接收到數(shù)據(jù)時，根據(jù)報文中的“目的IP地址”查詢硬件轉(zhuǎn)發(fā)表，根據(jù)匹配結(jié)果進行相應的數(shù)據(jù)轉(zhuǎn)發(fā)，并且采用硬件芯片或高速緩沖區(qū)支持，可以達到線速。在交換機剛啟動完畢時，交換機就把設備的軟件路由表下載到ASIC芯片上。在需要進行三層交換的報文到達交換機后，交換機首先會查詢最長匹配硬件轉(zhuǎn)發(fā)表，但由于MAC地址是未知的，無法同時下載，此時的硬件轉(zhuǎn)發(fā)表是無效的，所以無法進行硬件數(shù)據(jù)轉(zhuǎn)發(fā)。因此，交換機將利用CPU對數(shù)據(jù)進行軟件路由轉(zhuǎn)發(fā)，交換機在數(shù)據(jù)轉(zhuǎn)發(fā)過程中獲取下一跳IP地址和數(shù)據(jù)轉(zhuǎn)發(fā)出口的MAC地址，然后會被自動下載到三層硬件轉(zhuǎn)發(fā)表，此時包含了下一跳IP地址和數(shù)據(jù)轉(zhuǎn)發(fā)出口MAC地址的硬件轉(zhuǎn)發(fā)表項才真正生效。在這之后，發(fā)往相同目的IP網(wǎng)段的報文到達交換機都可以直接通過最長匹配硬件轉(zhuǎn)發(fā)表進行硬件轉(zhuǎn)發(fā)，而其他網(wǎng)段的數(shù)據(jù)轉(zhuǎn)發(fā)則需要重復上述過程。習題8：匯編語言函數(shù)可參考net/。習題9：由于通常情況下，IP報文首部發(fā)生變化的字段主要是TTL。而檢驗和字段是伴隨TTL字段變化而變化的，因此根據(jù)RFC1624可以設計一種不需要重新計算檢驗和的修正方法。具體方法參見RFC1642.習題10：使用散列結(jié)構(gòu)并通過分離鏈接的方法處理散列沖突，在元素個數(shù)保持一定規(guī)模的情況下可以保證insert和search的時間復雜度為O(1)。但是隨著元素規(guī)模的擴大，insert和search的時間復雜度會逐漸脫離常數(shù)。同時，選擇散列函數(shù)時需要非常謹慎。對于元素關鍵字隨機化程度較高的情況，可采用二分搜索樹的實現(xiàn)方式。這種方式可以保證search的時間復雜度為O(log n)，但是對元素關鍵字隨機化程度的要求比較高。為了防止不平衡的二分搜索樹出現(xiàn)，可采用AVL樹或者紅黑樹作為路由結(jié)構(gòu)。只是兩者在元素的insert操作時需要一些額外的時間。目前廣泛流行的路由表結(jié)構(gòu)是采用radix樹的構(gòu)造。它可以保證最壞情況下search的時間復雜度達到O(log n)。第5章習題解答參考思路習題1: 本題主要考查對ICMP軟件整體結(jié)構(gòu)的理解程度，幫助學生梳理ICMP軟件中函數(shù)之間的關系，從而更好地掌握ICMP軟件中函數(shù)的功能和處理機制。習題2:（1）終點不可達報文：當路由器不能為報文找到路由或者主機不能交付報文時，丟棄該報文并發(fā)送該類型報文給源主機；（2）源點抑制報文：當路由器或主機因擁塞而丟棄報文時，向源主機發(fā)送該類型報文；（3）超時報文：當路由器收到TTL為零的報文或目的主機在規(guī)定的時間內(nèi)沒有收到所有的分片報文時，向源主機發(fā)送該類型報文；（4）參數(shù)錯誤報文：當路由器或主機收到存在二義性或字段缺失的報文時，丟棄該報文并發(fā)送該類型報文；（5）改變路由報文：當路由器收到本應發(fā)往其他路由器的報文時，把該報文發(fā)送給正確的路由器，并發(fā)送該類型報文通知源主機更正路由，以幫助更新路由。ICMP的5種差錯報告報文結(jié)構(gòu)如下： （1）終點不可達報文 類型：3代碼：0~15檢驗和未使用（全0）收到的IP數(shù)據(jù)報的一部分，包括IP數(shù)據(jù)報首部以及數(shù)據(jù)報數(shù)據(jù)的前8個字節(jié)（2）源點抑制報文 類型：4代碼：0檢驗和未使用（全0）收到的IP數(shù)據(jù)報的一部分，包括IP數(shù)據(jù)報首部以及數(shù)據(jù)報數(shù)據(jù)的前8個字節(jié)（3）超時報文 類型：11代碼：0或1檢驗和未使用（全0）收到的IP數(shù)據(jù)報的一部分，包括IP數(shù)據(jù)報首部以及數(shù)據(jù)報數(shù)據(jù)的前8個字節(jié)（4）參數(shù)錯誤報文類型：12代碼：0或1檢驗和指針未使用（全0）收到的IP數(shù)據(jù)報的一部分，包括IP數(shù)據(jù)報首部以及數(shù)據(jù)報數(shù)據(jù)的前8個字節(jié)（5）改變路由報文類型：5代碼：0~3檢驗和目標路由器IP地址收到的IP數(shù)據(jù)報的一部分，包括IP數(shù)據(jù)報首部以及數(shù)據(jù)報數(shù)據(jù)的前8個字節(jié)習題3:本題主要考查對PING程序?qū)崿F(xiàn)及與ICMP報文聯(lián)系的掌握程度，幫助學生更深入地了解ICMP報文的實現(xiàn)。 習題4:。/** icsetbuf 為ICMP報文申請一個緩沖區(qū)* icsetbuf()函數(shù)為ICMP報文分配緩沖區(qū)，設置了兩個變量，其中一個變量指出該報文是否是一個差錯報告報文（或是一個信息請求）；而另一個指出這個報文的類型是否是對上一個請求做出的應答。* 該函數(shù)很直觀，具體分四種情況：對絕大多數(shù)的應答，icsetbuf()函數(shù)重新利用抵達的請求報文占用的緩沖區(qū)（即返回由入口參數(shù)pa1提供的地址）；對于沒有具體實現(xiàn)的報文類型，icsetbuf()函數(shù)釋放引起差錯的報文，返回SYSERR；對含有大量數(shù)據(jù)的ICMP報文，icsetbuf()函數(shù)為其分配一個大緩沖區(qū)；對其他不能利用原緩沖區(qū)的報文，icsetbuf()函數(shù)為它們分配一個標準緩沖區(qū)。**/struct ep *icsetbuf(type, pa1, pisresp, piserr)int type。char *pa1。 /*舊的報文（如果有的話） */Bool *pisresp, /*查詢報文*/ *piserr。 /*差錯報告報文*/{ Struct ep *pep。 /*正在處理的以太網(wǎng)幀*/ *pisresp = *piserr = FALSE。 switch (type) { case ICT_REDIRECT:/*重定向報文*/ pep = (struct ep *)getbufi()。/* char *getbufi(poolid)申請小緩沖區(qū)*/ if (pep == NULL) return(NULL)。 blkcopy(pep, pa1, MAXNETBUF)。/* 函數(shù)原型為blkcopy(to, from, nbytes)*/ pa1 = (char *)pep。 *piserr = TRUE。 break。 case ICT_DESTUR:/*終點不可達報文*/ case ICT_SRCQ: /*源點抑制報文*/ case ICT_TIMEX: /*超時報文*/ case ICT_PARAMP: /*參數(shù)錯誤報文*/ pep = (struct ep *)pa1。 *piserr = TRUE。 break。 case ICT_ECHORP:/*ECHO應答報文*/ case ICT_INFORP:/*消息應答報文*/ case ICT_MASKRP:/ *ICMP掩碼應答報文*/ pep = (struct ep *)pa1。 *pisresp = TRUE。 break。 case ICT_ECHORQ:/*ECHO請求報文*/ case ICT_TIMERQ: /*時間戳請求報文*/ case ICT_INFORQ: /*消息請求報文*/ case ICT_MASKRQ: /*ICMP掩碼請求報文*/ pep = (struct ep *)getbufi()。 /*申請大緩沖區(qū)*/ if (pep == NULL) return(NULL)。 break。 case ICT_TIMERP: /* 時間戳應答報文 */ /* IcmpOutTimestampsReps++。 */ IcmpOutErrors。 /* Kludge：超時報文數(shù)加1 */ freebuf(pa1)。 return(NULL)。 } switch (type) { /* 更新MIB 統(tǒng)計信息量*/ case ICT_ECHORP: IcmpOutEchos++。 break。 case ICT_ECHORQ: IcmpOutEchoReps++。 break。 case ICT_DESTUR: IcmpOutDestUnreachs++。 break。 case ICT_SRCQ: IcmpOutSrcQuenchs++。 break。 case ICT_REDIRECT: IcmpOutRedirects++。 break。 case ICT_TIMEX: IcmpOutTimeExcds++。 break。 case ICT_PARAMP: IcmpOutParmProbs++。 break。 case ICT_TIMERQ: IcmpOutTimestamps++。 break。 case ICT_TIMERP: IcmpOutTimestampReps++。 break。 case ICT_MASKRQ: IcmpOutAddrMasks++。 break。 case ICT_MASKRP: IcmpOutAddrMaskReps++。 break。 } return pep。}char *getbufi(poolid)/*從預先設定的緩沖池申請緩沖區(qū)，如果沒有可用的緩沖區(qū)則立即返回*/struct ep { /* 以太幀結(jié)構(gòu)*/ IPaddr ep_nexthop。 /* niput函數(shù)使用 */ short ep_len。 /*以太幀長度 */ struct eh ep_eh。 /*以太幀首部 */ char ep_data[EP_DLEN]。 /*以太幀的數(shù)據(jù)部分*/}。/* ECHOMAX必須是偶數(shù)*/define ECHOMAX(pip) (MAXLRGBUFIC_HLENIP_HLEN(pip)EP_HLEN)/*MAXLRGBUF 最大緩沖區(qū)*//*IC_HLEN 8*//*IP_HLEN(pip) ((pipip_verlen amp。 0xf)2) *//*EP_HLEN 以太幀首部+以太幀長度+下一跳地址*//* * icsetdata 設置數(shù)據(jù)段，返回值是數(shù)據(jù)的長度 * */int icsetdata(type, pip, pa2)int type。struct ip *pip。char *pa2。{ struct icmp *pic = (struct icmp *)pipip_data。 int i, len。 switch (type) { case ICT_ECHORP: /*ECHO應答報文*/ len = pipip_lenIP_HLEN(pip)IC_HLEN。/* 長度 = IP報文長度IP首部長度ICMP首部長度*/ if (isodd(len))/* isodd()函數(shù)：判斷其參數(shù)是不是奇數(shù),如果是奇數(shù)就返回TRUE,否則返回FASLE和錯誤值*/ picic_data[len] = 0。 /*ICMP數(shù)據(jù)區(qū)CRC校驗 */ return len。 case ICT_DESTUR:/*終點不可達報文*/ case ICT_SRCQ: /*源點抑制報文*/ case ICT_TIMEX: /*超時報文*/ picic_mbz = (long) 0。 /*必須為0 */ break。 case ICT_REDIRECT:/*重定向報文*/ blkcopy(picic_gw, pa2, IP_ALEN)。 /* blkcopy(to, from, nbytes) 重定向到網(wǎng)關*/ break。 case ICT_PARAMP:/*參數(shù)錯誤報文*/ len = (int)pa2。 picic_ptr = (char)len。/*參數(shù)指針*/ for (i=0。 iIC_PADLEN。 ++i)/*參數(shù)長度*/ picic_pad[i] = 0。 break。 case ICT_MASKRP:/*掩碼應答報文*/ blkcopy(picic_data, pa2, IP_ALEN)。 /*函數(shù)原型為blkcopy(to, from, nbytes)*/ break。 case ICT_ECHORQ: /*ECHO請求報文*/ if ((unsigned)pa2 (unsigned)(ECHOMAX(pip))) pa2 = (char *)(ECHOMAX(pip))。 for (i=0。 i(int)pa2。 ++i) picic_data