基于主動(dòng)和被動(dòng)模型的網(wǎng)絡(luò)測(cè)量算法研究及實(shí)現(xiàn).pdf

1、隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大和各種復(fù)雜業(yè)務(wù)的應(yīng)用，如何有效獲得網(wǎng)絡(luò)狀態(tài)信息對(duì)優(yōu)化網(wǎng)絡(luò)設(shè)置加強(qiáng)網(wǎng)絡(luò)管理、提高網(wǎng)絡(luò)服務(wù)質(zhì)量和確保網(wǎng)絡(luò)安全至關(guān)重要。網(wǎng)絡(luò)測(cè)量是獲取網(wǎng)絡(luò)狀態(tài)信息的直接有效手段。根據(jù)測(cè)量方式的不同，網(wǎng)絡(luò)測(cè)量一般分為被動(dòng)測(cè)量和主動(dòng)測(cè)量。被動(dòng)測(cè)量方式通過(guò)在網(wǎng)絡(luò)中接入測(cè)量探針，記錄和統(tǒng)計(jì)網(wǎng)絡(luò)鏈路或節(jié)點(diǎn)上業(yè)務(wù)流量的信息。主動(dòng)測(cè)量通過(guò)向目標(biāo)鏈路或目標(biāo)節(jié)點(diǎn)發(fā)送探測(cè)包來(lái)測(cè)量鏈路或端到端的延遲、帶寬和丟包率等網(wǎng)絡(luò)性能參數(shù)。不管是主動(dòng)測(cè)量還是被動(dòng)測(cè)量，都

2、需要付出一定的測(cè)量代價(jià)。測(cè)量代價(jià)一般分為設(shè)備部署維護(hù)代價(jià)、測(cè)量行為對(duì)網(wǎng)絡(luò)影響產(chǎn)生的代價(jià)和測(cè)量信息收集代價(jià)。隨著現(xiàn)代網(wǎng)絡(luò)測(cè)量所需測(cè)量信息的增多，測(cè)量頻率的加快，網(wǎng)絡(luò)測(cè)量代價(jià)不斷提高。因此，對(duì)降低測(cè)量代價(jià)的網(wǎng)絡(luò)測(cè)量模型及算法的深入研究變得極具現(xiàn)實(shí)意義。
　　 對(duì)于基于主動(dòng)模型的網(wǎng)絡(luò)測(cè)量，降低測(cè)量代價(jià)的優(yōu)化方法主要通過(guò)減少測(cè)量站點(diǎn)部署，減少探測(cè)包的發(fā)送。測(cè)量站點(diǎn)的部署問(wèn)題可映射為最小覆蓋問(wèn)題，當(dāng)確定部署站點(diǎn)后，則需求取合理的測(cè)量分配，

3、使得測(cè)量代價(jià)相對(duì)較低?，F(xiàn)實(shí)中網(wǎng)絡(luò)路由信息動(dòng)態(tài)變化，這就要求測(cè)量方案具有動(dòng)態(tài)適應(yīng)性，保證在所有網(wǎng)絡(luò)變化的情況下仍能對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行測(cè)量。另外測(cè)量站點(diǎn)的選取也制約著測(cè)量分配，如何取得站點(diǎn)和測(cè)量分配的平衡是研究中應(yīng)當(dāng)考慮的問(wèn)題。而在基于被動(dòng)模型的網(wǎng)絡(luò)測(cè)量中，優(yōu)化方法是尋找最少的測(cè)量部署站點(diǎn)集，并盡可能減少對(duì)網(wǎng)絡(luò)信息的重復(fù)測(cè)量。其中測(cè)量站點(diǎn)的選取問(wèn)題可映射為頂點(diǎn)覆蓋問(wèn)題，通過(guò)對(duì)流量規(guī)律利用，可將問(wèn)題歸約為弱頂點(diǎn)覆蓋問(wèn)題，從而一步減少測(cè)量站點(diǎn)的部署

4、。另外通過(guò)對(duì)網(wǎng)絡(luò)協(xié)議原理，對(duì)網(wǎng)絡(luò)流量進(jìn)行劃分，則可進(jìn)一步減少對(duì)網(wǎng)絡(luò)業(yè)務(wù)的重復(fù)測(cè)量。
　　 本文就主動(dòng)測(cè)量的站點(diǎn)選取、測(cè)量分配和被動(dòng)測(cè)量的站點(diǎn)選取算法進(jìn)行了研究實(shí)現(xiàn)。在主動(dòng)測(cè)量中，引入了基于鏈路使用代價(jià)的測(cè)量模型，充分利用探測(cè)結(jié)果來(lái)減少測(cè)量包發(fā)送的數(shù)量并降低測(cè)量代價(jià)?；诖四Ｐ偷臏y(cè)量分配方案根據(jù)探測(cè)結(jié)果動(dòng)態(tài)分配探測(cè)包，使其適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境。對(duì)于被動(dòng)網(wǎng)絡(luò)測(cè)量，引入流守恒規(guī)律將站點(diǎn)選取問(wèn)題映射為弱頂點(diǎn)覆蓋問(wèn)題，然后通過(guò)先貪婪求解