[發(fā)明專利]一種使用拓?fù)浞稚⒍搪窂郊木W(wǎng)絡(luò)路由方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710528851.7
• 申請(qǐng)日: 2017-07-01
• 公開（公告）號(hào): CN107294852B
• 公開（公告）日: 2019-12-27
• 發(fā)明（設(shè)計(jì)）人: 陳光;胡勇堅(jiān);崔躍利;梅盼;鄔玲偉;王三秀
• 申請(qǐng)（專利權(quán)）人: 臺(tái)州學(xué)院
• 主分類號(hào): H04L12/733
• 分類號(hào): H04L12/733;H04L12/727
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

一種使用拓?fù)浞稚⒍搪窂郊木W(wǎng)絡(luò)路由方法，依次執(zhí)行如下過程：過程一、收集網(wǎng)絡(luò)的拓?fù)湫畔?；過程二、預(yù)先為網(wǎng)絡(luò)中的每一對(duì)節(jié)點(diǎn)o、d，計(jì)算并存儲(chǔ)節(jié)點(diǎn)o到節(jié)點(diǎn)d的拓?fù)浞稚⒍搪窂郊疨S_o,d，其中PS_o,d是指包含一條或多條節(jié)點(diǎn)o到節(jié)點(diǎn)d的長(zhǎng)度較短且彼此間拓?fù)渲丿B較少路徑的集合；過程三、對(duì)于每個(gè)待傳輸?shù)木W(wǎng)絡(luò)數(shù)據(jù)包Φ，為Φ從它的起始節(jié)點(diǎn)到目的節(jié)點(diǎn)的拓?fù)浞稚⒍搪窂郊羞x出一條估計(jì)傳輸時(shí)延最小的路徑P作為路由路徑。本發(fā)明提出的網(wǎng)絡(luò)路由方法，能綜合利用網(wǎng)絡(luò)的拓?fù)浼皞鬏敔顩r信息，為計(jì)算機(jī)通信網(wǎng)絡(luò)中的網(wǎng)絡(luò)數(shù)據(jù)包快速確定可盡量避開網(wǎng)絡(luò)中擁塞區(qū)域的路由路徑，有效提升網(wǎng)絡(luò)的整體傳輸性能。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)科學(xué)和計(jì)算機(jī)通信網(wǎng)絡(luò)領(lǐng)域，特別是指一種使用拓?fù)浞稚⒍搪窂郊木W(wǎng)絡(luò)路由方法。

背景技術(shù)

計(jì)算機(jī)通信網(wǎng)絡(luò)是支撐現(xiàn)代信息社會(huì)的重要基礎(chǔ)設(shè)施，這類網(wǎng)絡(luò)通過運(yùn)行一定的路由協(xié)議將攜帶信息的網(wǎng)絡(luò)數(shù)據(jù)包從網(wǎng)絡(luò)的一個(gè)起始節(jié)點(diǎn)傳輸至一個(gè)目的節(jié)點(diǎn)。在計(jì)算機(jī)通信網(wǎng)絡(luò)中，應(yīng)用高效的路由方法，能保證網(wǎng)絡(luò)具備優(yōu)良的傳輸性能，即網(wǎng)絡(luò)不易發(fā)生擁堵，網(wǎng)絡(luò)數(shù)據(jù)包能快速抵達(dá)目的節(jié)點(diǎn)。當(dāng)前，在現(xiàn)有計(jì)算機(jī)通信網(wǎng)絡(luò)中，大量應(yīng)用成熟的商用路由協(xié)議棧，如OSPF協(xié)議、BGP v4協(xié)議等。這類路由協(xié)議的一個(gè)重要理論基礎(chǔ)是經(jīng)典的最短路徑路由方法。

計(jì)算機(jī)通信網(wǎng)絡(luò)是典型的復(fù)雜網(wǎng)絡(luò)，可以使用拓?fù)渚W(wǎng)絡(luò)來(lái)進(jìn)行描述，拓?fù)渚W(wǎng)絡(luò)的節(jié)點(diǎn)即通信網(wǎng)絡(luò)中的各類節(jié)點(diǎn)，如計(jì)算機(jī)終端、路由器等網(wǎng)絡(luò)設(shè)備；若現(xiàn)實(shí)中兩個(gè)節(jié)點(diǎn)間存在一條直達(dá)的物理通信鏈路，如光纖、無(wú)線信道等，則在拓?fù)渚W(wǎng)絡(luò)中它們間存在連邊。近年來(lái)，伴隨著網(wǎng)絡(luò)科學(xué)理論及應(yīng)用研究的興起與發(fā)展，網(wǎng)絡(luò)路由方法的研究有了新的進(jìn)展。相關(guān)方面，科研人員提出了多種新的路由方法，它們大致可分為兩類：(1)固定路由方法：預(yù)先為網(wǎng)絡(luò)的所有起始、目的節(jié)點(diǎn)對(duì)計(jì)算好路由路徑，在網(wǎng)絡(luò)數(shù)據(jù)包傳輸時(shí)直接使用這些路徑進(jìn)行路由傳輸；(2)動(dòng)態(tài)路由方法：在網(wǎng)絡(luò)數(shù)據(jù)包傳輸過程中實(shí)時(shí)動(dòng)態(tài)計(jì)算路由路徑?？梢钥闯?，經(jīng)典的最短路徑路由方法屬于固定路由方法的范疇。

固定路由方法和動(dòng)態(tài)路由方法有各自的優(yōu)缺點(diǎn)。對(duì)于固定路由方法，路由路徑預(yù)先已計(jì)算，因此在傳輸階段將可以快速確定路由路徑，但其環(huán)境適應(yīng)能力不夠理想，若傳輸環(huán)境發(fā)生變化，如交通流的OD需求分布改變或部分節(jié)點(diǎn)故障等，它們將可能無(wú)法保證網(wǎng)絡(luò)的高效傳輸；對(duì)于動(dòng)態(tài)路由方法，由于路由路徑在網(wǎng)絡(luò)數(shù)據(jù)包傳輸過程中動(dòng)態(tài)計(jì)算，因此它們可根據(jù)傳輸環(huán)境確定高效的路由路徑，但路由路徑的動(dòng)態(tài)計(jì)算需要耗費(fèi)一定的計(jì)算資源(包括運(yùn)算時(shí)間和存儲(chǔ)空間)，這可能會(huì)給系統(tǒng)帶來(lái)較大的傳輸延時(shí)和運(yùn)行負(fù)擔(dān)。

考慮到在現(xiàn)有技術(shù)中，計(jì)算機(jī)通信網(wǎng)絡(luò)往往會(huì)進(jìn)行冗余配置，即在網(wǎng)絡(luò)中會(huì)設(shè)置一些環(huán)狀子圖結(jié)構(gòu)來(lái)確保系統(tǒng)運(yùn)行的穩(wěn)定性，這使得網(wǎng)絡(luò)中一對(duì)節(jié)點(diǎn)間往往可能存在多條彼此間重疊較少的路徑，本發(fā)明提出一種新的網(wǎng)絡(luò)路由方法，稱為一種使用拓?fù)浞稚⒍搪窂郊木W(wǎng)絡(luò)路由方法。該路由方法結(jié)合固定路由方法與動(dòng)態(tài)路由方法的優(yōu)點(diǎn)，預(yù)先為網(wǎng)絡(luò)中每一對(duì)起始、目的節(jié)點(diǎn)計(jì)算并存儲(chǔ)一條或多條長(zhǎng)度較短且彼此間拓?fù)渲丿B較少的路徑；在網(wǎng)絡(luò)進(jìn)入傳輸工作狀態(tài)后，根據(jù)網(wǎng)絡(luò)的傳輸狀況信息，快速為待傳輸?shù)木W(wǎng)絡(luò)數(shù)據(jù)包從已存儲(chǔ)的多條路徑中選擇一條估計(jì)傳輸時(shí)延最小的路徑作為路由路徑。理論上，該方法能為網(wǎng)絡(luò)數(shù)據(jù)包快速指派可盡量避開網(wǎng)絡(luò)擁塞區(qū)域的路由路徑，保證網(wǎng)絡(luò)優(yōu)良的傳輸性能。

在介紹本發(fā)明的具體內(nèi)容之前，首先對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)中網(wǎng)絡(luò)數(shù)據(jù)包的傳輸過程進(jìn)行簡(jiǎn)單的介紹：網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)都有一個(gè)網(wǎng)絡(luò)數(shù)據(jù)包發(fā)送隊(duì)列，該隊(duì)列一般來(lái)說(shuō)是一個(gè)先進(jìn)先出FIFO(First In First Out)的隊(duì)列，一段時(shí)間內(nèi)節(jié)點(diǎn)能按照自身的傳輸速率將網(wǎng)絡(luò)數(shù)據(jù)包發(fā)送隊(duì)列中位于隊(duì)首的一個(gè)或多個(gè)網(wǎng)絡(luò)數(shù)據(jù)包轉(zhuǎn)發(fā)。當(dāng)一個(gè)網(wǎng)絡(luò)數(shù)據(jù)包在一個(gè)節(jié)點(diǎn)上生成，即節(jié)點(diǎn)為網(wǎng)絡(luò)數(shù)據(jù)包的起始節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)將按照一定的規(guī)則為它選擇一條路由路徑；當(dāng)一個(gè)網(wǎng)絡(luò)數(shù)據(jù)包在起始節(jié)點(diǎn)中生成或抵達(dá)某一中繼節(jié)點(diǎn)時(shí)，它將首先被放入節(jié)點(diǎn)的網(wǎng)絡(luò)數(shù)據(jù)包發(fā)送隊(duì)列，直到上升至隊(duì)列的隊(duì)首時(shí)被轉(zhuǎn)發(fā)至其路由路徑的下一跳節(jié)點(diǎn)；當(dāng)一個(gè)網(wǎng)絡(luò)數(shù)據(jù)包抵達(dá)目的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)數(shù)據(jù)包完成傳輸，其傳輸生命周期結(jié)束，從網(wǎng)絡(luò)中被移除。