網(wǎng)絡(luò)路由傳輸策略的研究進展

程 燦，郭 強，劉建國

?

網(wǎng)絡(luò)路由傳輸策略的研究進展

程 燦，郭 強，劉建國

(上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心 上海楊浦區(qū) 200093)

隨著復(fù)雜網(wǎng)絡(luò)在眾多領(lǐng)域的廣泛應(yīng)用，如何提高網(wǎng)絡(luò)的傳輸效率成為了其進一步應(yīng)用的瓶頸。本文分別從基于節(jié)點和邊信息的路由策略，改變拓?fù)浣Y(jié)構(gòu)的路由策略，路徑選擇策略以及排隊策略四個方面展開，對網(wǎng)絡(luò)中的路由傳輸策略進行介紹，并對其中具有重要影響的方法進行詳細(xì)闡述。最后提出了這一領(lǐng)域中未來可能的研究方向。本文有助于相關(guān)學(xué)者快速了解當(dāng)前網(wǎng)絡(luò)中路由傳輸策略的研究進展，并能夠幫助網(wǎng)絡(luò)設(shè)計者以及管理者更好地提高網(wǎng)絡(luò)的傳輸效率，最大程度上避免傳輸過程中的交通擁塞。

復(fù)雜網(wǎng)絡(luò); 交通擁塞; 路由策略; 傳輸效率

隨著信息技術(shù)的飛速發(fā)展，人們的生活被各種網(wǎng)絡(luò)包圍著，包括e-mail網(wǎng)絡(luò)[1]、電話網(wǎng)絡(luò)[2]、電力網(wǎng)絡(luò)[3]、飛機航線網(wǎng)絡(luò)[4]、交通網(wǎng)絡(luò)[5]、因特網(wǎng)和萬維網(wǎng)[6-7]等。1998年，文獻(xiàn)[3]提出了小世界網(wǎng)絡(luò)模型，進一步，文獻(xiàn)[8]提出了無標(biāo)度網(wǎng)絡(luò)的模型，對實際的復(fù)雜系統(tǒng)進行網(wǎng)絡(luò)建?！，F(xiàn)代社會處在一個大數(shù)據(jù)、大流量的時代，高度依賴于這些網(wǎng)絡(luò)系統(tǒng)的正常高效運行。然而，在處于擁塞的情況下，這些網(wǎng)絡(luò)的傳輸效率會大大降低并可能造成網(wǎng)絡(luò)系統(tǒng)的癱瘓，極大地影響人們的工作與生活。所以，研究如何提高這些網(wǎng)絡(luò)的傳輸效率從而避免擁塞，具有很重要的現(xiàn)實意義。

以計算機網(wǎng)絡(luò)中的信息傳遞為例，通常，當(dāng)網(wǎng)絡(luò)中節(jié)點(邊)的負(fù)荷超過了它們的容量(帶寬)時，信息擁塞就會發(fā)生。學(xué)者們通過研究網(wǎng)絡(luò)中的路由傳輸策略對網(wǎng)絡(luò)進行優(yōu)化，進而提高網(wǎng)絡(luò)的傳輸效率。根據(jù)目前的研究，學(xué)者們首先從宏觀角度將路由傳輸策略分為基于網(wǎng)絡(luò)結(jié)構(gòu)和基于動力學(xué)的路由策略兩大類。進一步，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的類型，基于網(wǎng)絡(luò)結(jié)構(gòu)的路由策略又可被劃分為基于節(jié)點和邊信息的路由策略以及改變拓?fù)浣Y(jié)構(gòu)的路由策略。同時，基于動力學(xué)的路由策略又可以按照是否改變傳播路徑細(xì)分為路徑選擇策略以及排隊策略。目前的路由策略中有一些具有重要影響，例如，文獻(xiàn)[9]首次提出按度分配節(jié)點的容量，開啟了容量分配策略的先例，學(xué)者們自此開始考慮賦予各節(jié)點不同的傳輸數(shù)據(jù)包的能力。文獻(xiàn)[10]提出了改變拓?fù)浣Y(jié)構(gòu)的路由策略，通過刪減網(wǎng)絡(luò)中的關(guān)鍵連邊實現(xiàn)網(wǎng)絡(luò)的優(yōu)化。這類策略雖然操作簡單，但有時實用性不高。文獻(xiàn)[11]首次提出了一種高效的路徑選擇策略，主張數(shù)據(jù)包應(yīng)盡量避開hub節(jié)點而選擇邊緣節(jié)點進行傳輸。在這個策略的啟發(fā)下，學(xué)者們開始關(guān)注到邊緣節(jié)點的重要性，但hub節(jié)點本身具有的很高的傳輸能力沒有得到充分利用。文獻(xiàn)[12-13]認(rèn)為網(wǎng)絡(luò)吞吐量的大小取決于網(wǎng)絡(luò)中節(jié)點的最大介數(shù)，因此提出了一種路徑選擇策略使網(wǎng)絡(luò)中節(jié)點的最大介數(shù)值達(dá)到最小。雖然這種策略下網(wǎng)絡(luò)的吞吐量得以提高，但是計算復(fù)雜度卻很高。文獻(xiàn)[14-15]提出了基于局部信息的路徑選擇策略，只需要了解網(wǎng)絡(luò)的局部信息即可實現(xiàn)優(yōu)化，因此對于一些實際的大型網(wǎng)絡(luò)更具有實用價值。學(xué)者們還從節(jié)點處數(shù)據(jù)包傳遞順序的角度出發(fā)，提出了一系列排隊策略，使節(jié)點處的數(shù)據(jù)包按照一定規(guī)則有序傳遞，降低了網(wǎng)絡(luò)中數(shù)據(jù)包的平均傳輸時間。

理解并研究復(fù)雜網(wǎng)絡(luò)上的路由策略、控制網(wǎng)絡(luò)擁塞，是急需處理的重要問題之一。因此有必要對網(wǎng)絡(luò)中的路由傳輸策略進行全面回顧與分析。目前關(guān)于網(wǎng)絡(luò)路由傳輸?shù)木C述中，文獻(xiàn)[16]通過模擬和仿真無標(biāo)度網(wǎng)絡(luò)和均勻網(wǎng)絡(luò)上的交通狀況，系統(tǒng)地研究了網(wǎng)絡(luò)傳輸?shù)囊幌盗薪y(tǒng)計特性與網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系；文獻(xiàn)[17]從整體和局部分別出發(fā)，回顧了具有重要意義的路由策略；文獻(xiàn)[18]將路由策略劃分為“硬策略”與“軟策略”，主要回顧了路徑選擇策略以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變的路由策略。本文對網(wǎng)絡(luò)的路由傳輸策略進行了更系統(tǒng)的回顧與分析，對于路由策略的劃分更具體細(xì)致，介紹更詳細(xì)全面。本文首先介紹了與這項研究相關(guān)的一些基本指標(biāo)，然后回顧了提高網(wǎng)絡(luò)傳輸效率的四類路由策略——基于節(jié)點和邊信息的策略，改變拓?fù)浣Y(jié)構(gòu)的策略，路徑選擇策略以及排隊策略，最后提出了網(wǎng)絡(luò)路由傳輸策略未來可能的研究方向。

1 基本指標(biāo)介紹

在網(wǎng)絡(luò)路由傳輸策略的研究中，不失一般性，網(wǎng)絡(luò)中的節(jié)點同時被視作主機和路由器，即每個節(jié)點都可以產(chǎn)生、傳送并且接受數(shù)據(jù)包。網(wǎng)絡(luò)中的邊可以看作是數(shù)據(jù)包傳遞的可能的路徑。每單位時間內(nèi)網(wǎng)絡(luò)中有個新的數(shù)據(jù)包產(chǎn)生，這些數(shù)據(jù)包都隨機地選擇出發(fā)點和終點。到達(dá)終點的數(shù)據(jù)包將會從網(wǎng)絡(luò)中移除。

以下是網(wǎng)絡(luò)中的路由傳輸策略所涉及到的一些基本指標(biāo)，包括容量、介數(shù)、臨界值以及序參數(shù)，它們可以衡量網(wǎng)絡(luò)的吞吐狀況。

網(wǎng)絡(luò)的傳輸效率有兩個衡量指標(biāo)，網(wǎng)絡(luò)的吞吐量以及平均傳輸時間。網(wǎng)絡(luò)的吞吐量越大，平均傳輸時間越短，網(wǎng)絡(luò)的傳輸效率就越高。因此，所有的路由傳輸策略都旨在擴大網(wǎng)絡(luò)吞吐量和減少數(shù)據(jù)包的平均傳輸時間。

2 基于節(jié)點和邊信息的路由策略

當(dāng)節(jié)點處的數(shù)據(jù)包數(shù)量超過了節(jié)點的容量，或者連邊處的數(shù)據(jù)包數(shù)量超過了邊的帶寬時，網(wǎng)絡(luò)會出現(xiàn)擁塞現(xiàn)象。在廣泛應(yīng)用的最短路徑路由策略[22](shortest path routing strategy)下，阻塞總是首先出現(xiàn)在hub節(jié)點處然后再擴散至整個網(wǎng)絡(luò)。因此，當(dāng)整個網(wǎng)絡(luò)的節(jié)點總?cè)萘恳欢〞r，只要分配給hub節(jié)點更大的容量就能有效緩解擁塞進而提高網(wǎng)絡(luò)的最大吞吐量。類似地，當(dāng)網(wǎng)絡(luò)中邊的總帶寬一定時，分配給關(guān)鍵連邊更大的帶寬也能提高網(wǎng)絡(luò)的傳輸效率。

2.1 改變節(jié)點處理能力的分配策略

文獻(xiàn)[9]提出了另外兩個模型，分別是按節(jié)點度的大小以及介數(shù)的大小來分配容量。

模型1:(4)

模型2:(5)

文獻(xiàn)[24]提出了一個有限的數(shù)據(jù)包容量傳輸模型。在這個模型中，節(jié)點的容量與度之間呈線性關(guān)系，即節(jié)點的容量為：

文獻(xiàn)[26]進一步提出了一個適應(yīng)性的容量傳輸機制。在這個機制下，節(jié)點的容量與排隊長度呈線性關(guān)系，即：

2.2 帶寬的重新分配策略

在相同的路由策略下，若兩個網(wǎng)絡(luò)采用不同的帶寬分配策略，網(wǎng)絡(luò)的吞吐量也會不同[27]。因此可以通過重新分配各連邊的帶寬來增加網(wǎng)絡(luò)的總?cè)萘俊Ｎ墨I(xiàn)[28]引入了可調(diào)參數(shù)，并根據(jù)連邊的重要性分配帶寬。每條連邊的重要性由它兩端節(jié)點的度的乘積來衡量。連接節(jié)點和的連邊的帶寬為：

文獻(xiàn)[30]進一步提出了一個基于排隊長度的動態(tài)帶寬分配策略，即按照每個時間點處每條邊的排隊長度來分配帶寬：

目前的研究還只是停留在研究節(jié)點的總?cè)萘恳欢ɑ蛘哌B邊的總帶寬一定的情況下的最優(yōu)分配策略。然而在實際網(wǎng)絡(luò)中，這兩個限制往往同時發(fā)生。因此，有必要在未來的工作中研究在容量和帶寬都有限時的最佳分配策略。

3 改變拓?fù)浣Y(jié)構(gòu)

改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是可以提高網(wǎng)絡(luò)傳輸效率的另一路由策略。研究表明交通動力學(xué)很大程度上取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)[21,31]，因此通過在網(wǎng)絡(luò)中刪減或增加一些邊也能提高網(wǎng)絡(luò)的吞吐量。文獻(xiàn)[20]證明了同構(gòu)網(wǎng)絡(luò)(homogeneous network)比異構(gòu)網(wǎng)絡(luò)(heterogeneous network)能承載更多的數(shù)據(jù)包，因為介數(shù)很大的節(jié)點在均勻網(wǎng)絡(luò)中的數(shù)量相對較少。文獻(xiàn)[16]通過對無標(biāo)度網(wǎng)絡(luò)和均勻網(wǎng)絡(luò)上的交通狀況進行模擬仿真，也證明了這個結(jié)論。文獻(xiàn)[10]進而提出一種按照邊兩端節(jié)點的介數(shù)乘積進行刪邊擴容的方法(high-betweenness-first link removal strategy)，以減少網(wǎng)絡(luò)中介數(shù)較大的節(jié)點的個數(shù)。即計算網(wǎng)絡(luò)中每條邊兩端點的乘積的值并按從大到小的順序進行刪減。結(jié)果證明，刪減一定數(shù)量的邊有利于擴大網(wǎng)絡(luò)的吞吐量，刪減過多的邊則會適得其反。文獻(xiàn)[32]從度的角度出發(fā)，提出了按照邊兩端節(jié)點度的大小進行刪邊的策略(high- degree-first link removal strategy)。具體的實施步驟如下：計算網(wǎng)絡(luò)中每條邊的兩端點的乘積的值并按從大到小的順序進行刪減，每次刪邊后計算網(wǎng)絡(luò)的吞吐量并通過比較得到最大值。在非均勻網(wǎng)絡(luò)中，hub節(jié)點一般要承載更多的信息負(fù)荷，導(dǎo)致它們周圍的邊很容易發(fā)生堵塞，移除一些易發(fā)生堵塞的邊能夠使網(wǎng)絡(luò)中的信息負(fù)荷重新分配，從而提高網(wǎng)絡(luò)的吞吐量。但這兩種方法都會增加平均路徑的長度，導(dǎo)致傳輸效率不會大幅度提高。

另外，一些學(xué)者從算法的角度出發(fā)，也提出了一些改變拓?fù)浣Y(jié)構(gòu)的路由策略。例如，基于模擬退火算法(simulated annealing)中得出的最優(yōu)結(jié)果[33]，文獻(xiàn)[34]提出了VNDR策略。該策略的主要步驟如下：

3) 重復(fù)步驟1)和2)，直到達(dá)到預(yù)設(shè)的重復(fù)次數(shù)。

無標(biāo)度網(wǎng)絡(luò)上的一系列實驗表明，在該策略下網(wǎng)絡(luò)能達(dá)到的最大吞吐量優(yōu)于采用按度或介質(zhì)刪邊擴容所得到的結(jié)果。當(dāng)同時采用最短路徑路由策略時，VNDR策略在沒有大幅度提高平均路徑長度的情況下，同時達(dá)到了擴大網(wǎng)絡(luò)吞吐量和減少平均路由時間的目標(biāo)。

文獻(xiàn)[35]還提出了一種在無標(biāo)度網(wǎng)絡(luò)中增加節(jié)點和連邊的有效方法?？紤]到通過兩個節(jié)點之間的最短路徑很有可能經(jīng)過hub節(jié)點，并且最短路徑越長，通過的可能性越大，他們主張在擁有最長的最短路徑的節(jié)點之間連接一條邊，使數(shù)據(jù)包可以直接在它們之間傳遞而不需要經(jīng)過hub節(jié)點，從而提高網(wǎng)絡(luò)的傳輸效率。增加節(jié)點也運用同樣的方法，即增加的節(jié)點選擇兩個擁有最長的最短路徑的節(jié)點進行連邊。

改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的路由策略具有高效、簡潔的特點。在高峰期時，實際交通網(wǎng)絡(luò)系統(tǒng)中暫時關(guān)閉一些擁擠路段、實際通訊網(wǎng)絡(luò)中關(guān)閉一些鏈路即可實現(xiàn)優(yōu)化，緩解擁塞現(xiàn)象，提高網(wǎng)絡(luò)傳輸效率。但另一方面，采用這種策略的實用性不高。例如，在航空網(wǎng)絡(luò)中，由于客流量的需求很大，因此在高峰期時取消一些重要航班是不可行的。另外，增加一些重要城市的機場數(shù)量是另一種改變拓?fù)浣Y(jié)構(gòu)的策略，然而這需要花費大量的人力、物力以及時間。所以，此類策略雖然操作簡單，但在一些實際網(wǎng)絡(luò)中可行性不高。

4 路徑選擇策略

根據(jù)文獻(xiàn)[18]的研究，前面提到的兩類提高運輸效率的路由策略被稱為“硬策略”(hard strategy)。一般情況下，這類策略的成本比較高，實用性不強。事實上，之前的研究已經(jīng)證明，即使在異構(gòu)網(wǎng)絡(luò)中，網(wǎng)絡(luò)動力學(xué)也可以被同質(zhì)化(homogenized)，這已經(jīng)在提高網(wǎng)絡(luò)同步性(network synchronization)方面得到了運用[36]。因此，目前在提高網(wǎng)絡(luò)運輸效率方面的大多數(shù)研究都集中于尋找新的路徑選擇策略，即所謂的“軟策略”(soft strategy)[18]。雖然找到全局最優(yōu)的路徑選擇策略是一個NP難題[37]，此前的研究中還是涌現(xiàn)出不少優(yōu)秀策略，它們很大程度上提高了網(wǎng)絡(luò)的傳輸效率，包括靜態(tài)的全局[11-13,22,38-41]和局部策略[14-15]以及一系列動態(tài)策略[42-49]。

4.1 靜態(tài)路徑選擇策略(static routing strategy)

最早的路徑選擇策略是隨機游走(random walk)，由于它在網(wǎng)絡(luò)的傳輸和搜索機制中廣泛應(yīng)用[20,50]，因此被學(xué)者們普遍研究[51-52]。但是它的過程太簡單以至于無法準(zhǔn)確反映出一個真實交通運輸或信息傳輸系統(tǒng)的情況。經(jīng)典的最短路徑路由策略[22]是指每個數(shù)據(jù)包都沿著從起點到終點最短的那條路徑進行傳輸，由于它的經(jīng)濟成本和技術(shù)成本較低，因此被廣泛應(yīng)用于交通和通訊網(wǎng)絡(luò)中[9,53-55]。然而，若采用最短路徑路由策略，hub節(jié)點會承受很重的信息負(fù)荷，進而造成嚴(yán)重的擁塞。

為緩解hub節(jié)點處的擁塞問題，文獻(xiàn)[11]提出了一種高效的路由策略(efficient routing strategy)，又稱為ER策略，通過引入一個可調(diào)參數(shù)，使負(fù)荷從中心節(jié)點處重新分配一部分到邊緣節(jié)點處。對于起點為，終點為，經(jīng)過節(jié)點的路徑，定義為：

(12)

考慮到ER策略忽略了很多中心節(jié)點，使它們的運輸能力沒有得到充分利用，造成很大浪費，文獻(xiàn)[40]對ER策略進行了改進，提出了一種積極的路由策略(active routing strategy)，進一步對網(wǎng)絡(luò)動態(tài)進行同質(zhì)化。在這個策略中，對于起點為，終點為，經(jīng)過節(jié)點的路徑，定義為：

文獻(xiàn)[41]平衡了最短路徑策略和ER策略，提出了一種概率路由策略(probability routing strategy)，使hub節(jié)點得到更高效的利用。通過找到從到的所有路徑中使達(dá)到最大的路徑作為最優(yōu)路徑，的定義為：

文獻(xiàn)[12-13]認(rèn)為網(wǎng)絡(luò)吞吐量的大小取決于網(wǎng)絡(luò)中節(jié)點的最大介數(shù)。假設(shè)各節(jié)點的容量相等，那么堵塞一定首先發(fā)生在介數(shù)最大的節(jié)點上。因此，他們提出了一種最優(yōu)路由策略(optimal routing strategy)，即設(shè)計了一個算法使數(shù)據(jù)包盡量避免經(jīng)過介數(shù)較大的節(jié)點，從而使網(wǎng)絡(luò)中最大介數(shù)的值降到最低。在這種情況下，網(wǎng)絡(luò)吞吐量得以提高，并且超過了文獻(xiàn)[56]對于網(wǎng)絡(luò)可達(dá)到的最大容量的理論預(yù)測。同時，BA網(wǎng)絡(luò)上的實驗表明，網(wǎng)絡(luò)處于擁塞狀態(tài)時，最優(yōu)路由策略下的數(shù)據(jù)包的平均傳輸時間小于在最短路徑策略下的傳輸時間。

上面提到的路徑選擇策略都是基于全局信息的方法，然而針對大型網(wǎng)絡(luò)，全局信息很難把握，因此這些策略有時并不實用。文獻(xiàn)[14-15]提出了基于局部拓?fù)湫畔⒌穆酚刹呗?local routing strategy)，即每個節(jié)點都對與它最近的鄰居節(jié)點進行局部搜索，若數(shù)據(jù)包的終點在搜索范圍內(nèi)，則直接傳輸?shù)浇K點；若不在范圍內(nèi)，則按照一種偏好概率傳遞數(shù)據(jù)包：

另外，文獻(xiàn)[57]針對節(jié)點生成率不斷變化的網(wǎng)絡(luò)提出了一種混合路由策略(mixed routing strategy)。即當(dāng)節(jié)點生成率較低時，使用最短路徑策略；生成率較高時采用局部路由策略。無標(biāo)度網(wǎng)絡(luò)上的實驗結(jié)果表明該策略下網(wǎng)絡(luò)的傳輸效率超過了單獨使用兩策略中的任意一個。

4.2 動態(tài)路徑選擇策略(dynamic routing strategy)

之前提到的一系列靜態(tài)路徑選擇策略都是基于靜態(tài)信息的路由策略。在這些策略下，一旦網(wǎng)絡(luò)建立，每個數(shù)據(jù)包的最佳路徑同時也是確定的。為了更充分利用網(wǎng)絡(luò)靜態(tài)的拓?fù)浣Y(jié)構(gòu)信息以及動態(tài)的路由信息，學(xué)者們提出了一系列動態(tài)路徑選擇策略。動態(tài)路徑選擇策略同樣也是考慮局部的網(wǎng)絡(luò)結(jié)構(gòu)信息，但不同于局部路由策略，它會綜合考慮局部靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)以及動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)(例如節(jié)點處的排隊長度等)。

文獻(xiàn)[42-43]綜合考慮了最短路徑和在節(jié)點處的等待時間，提出了一種適應(yīng)性的局部動態(tài)路由方法，即數(shù)據(jù)包在選擇鄰居節(jié)點進行傳遞時要同時考慮該節(jié)點到終點的距離以及在該節(jié)點處的等待時間。等待時間的長短由節(jié)點處的排隊長度來決定，隊列越長，等待時間也越長。進一步，文獻(xiàn)[44]對此方法進行了改進，即數(shù)據(jù)包在傳遞時不僅要考慮鄰居節(jié)點的排隊長度，同時還要考慮整個路徑上所有節(jié)點的排隊長度。文獻(xiàn)[45]也同樣綜合考慮了路徑的長度以及整條路徑上的節(jié)點處的等待時間，但從不同角度出發(fā)，提出了一種全局動態(tài)路由策略：

文獻(xiàn)[46]引入一個可調(diào)參數(shù)，整合了局部靜態(tài)信息和動力學(xué)信息，提出了一種局部動態(tài)路由策略，即數(shù)據(jù)包從節(jié)點傳遞到節(jié)點的概率為：

(18)

對于動態(tài)路由策略，往往需要一個時間差來更新動力學(xué)信息，因此雖然網(wǎng)絡(luò)的吞吐量提高了，運輸時間卻可能增加，結(jié)果對于提高實際網(wǎng)絡(luò)的傳輸效率只能提供很有限的幫助。因此如何降低這個時間差是未來研究工作中的一大挑戰(zhàn)。

5 排隊策略

上面提到的所有方法大多都遵循先進先出(FIFO)原則，即先到達(dá)某個節(jié)點的數(shù)據(jù)包優(yōu)先被傳遞到下一節(jié)點。另外，后進先出(LIFO)原則在研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與交通流量的統(tǒng)計特性之間的相互影響方面有所應(yīng)用[16,58-59]。然而，有時拋棄這些經(jīng)典原則、設(shè)計新穎高效的排隊策略也能提高網(wǎng)絡(luò)的傳輸效率。

文獻(xiàn)[60]摒棄了FIFO策略，對數(shù)據(jù)包的傳遞設(shè)定條件，即如果數(shù)據(jù)包的傳遞要經(jīng)過的連邊沒有發(fā)生擁塞，那么它們會按順序傳輸；反之，將會留在節(jié)點處。在這種策略下，可以順暢流通的數(shù)據(jù)包便不會被耽擱，節(jié)省了整個網(wǎng)絡(luò)中數(shù)據(jù)包的傳輸時間，提高了效率。

文獻(xiàn)[61]提出了一種最短剩余路徑優(yōu)先的排隊策略(shortest-remaining-path-first strategy)，又稱為SRPF策略，即那些終點距離目前所在節(jié)點的路徑最短的數(shù)據(jù)包優(yōu)先被傳遞。為避免擁有較長路徑的數(shù)據(jù)包的等待時間過長，他們同時也設(shè)置了一個時間值，一旦數(shù)據(jù)包等待的時間超過了這個值便會被優(yōu)先傳遞。由于數(shù)據(jù)包的路由路徑?jīng)]有改變，所以SRPF策略下的整個網(wǎng)絡(luò)的吞吐量并沒有改變，但是整個過程的運輸時間減少了。相應(yīng)地，網(wǎng)絡(luò)的傳輸效率也得到提高。

文獻(xiàn)[62]對一定比例的數(shù)據(jù)包提前設(shè)定一個優(yōu)先級，使它們無論進入節(jié)點的時間如何，都能優(yōu)先被傳遞，然后對于同一優(yōu)先級的數(shù)據(jù)包再遵循FIFO原則。無標(biāo)度網(wǎng)絡(luò)上的實驗結(jié)果表明，在網(wǎng)絡(luò)發(fā)生擁塞時，這種排隊策略能很大程度上縮短數(shù)據(jù)包的平均傳輸時間，進而提高網(wǎng)絡(luò)的傳輸效率，然而當(dāng)網(wǎng)絡(luò)處于自由流通狀態(tài)時則會惡化傳輸狀況。在這種優(yōu)先級排隊策略的啟發(fā)下，文獻(xiàn)[63]提出了一種全局動態(tài)排隊策略，對于擁塞節(jié)點處的每個數(shù)據(jù)包賦予一個優(yōu)先參數(shù)：

由于排隊策略并沒有改變數(shù)據(jù)包的傳輸路徑，也沒有對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)做任何改變，因此網(wǎng)絡(luò)的吞吐量不會增加，只有數(shù)據(jù)包的傳輸時間可能縮短。所以，雖然排隊策略操作容易，但此類策略對于提高網(wǎng)絡(luò)的傳輸效率只能提供有限的幫助。

6 其他方法

之前回顧的提高網(wǎng)絡(luò)傳輸效率的四類路由策略都是基于一個前提假設(shè)的，即網(wǎng)絡(luò)中的所有節(jié)點都可以同時生成、傳遞并接受數(shù)據(jù)包。然而，現(xiàn)實網(wǎng)絡(luò)中的路由規(guī)則并不是完全一致的，相反，它們之間存在很大差異。很多實際網(wǎng)絡(luò)中的每個節(jié)點都有特定功能。例如物流網(wǎng)絡(luò)中顧客只能接受包裹，配送中心只能發(fā)出包裹，中轉(zhuǎn)站只能傳遞包裹等。所以，在這個課題中，有些方法是基于特定結(jié)構(gòu)的網(wǎng)絡(luò)的，例如中間節(jié)點只能發(fā)出包裹，邊緣節(jié)點可以傳遞和接收[64]；有些特定節(jié)點只能生成包裹，其他只能傳遞、接收[65-68]。研究這些具有特定結(jié)構(gòu)的網(wǎng)絡(luò)上的路由策略有利于解決特定的實際問題。例如，文獻(xiàn)[68]的方法對于物流配送中心的選擇問題很有實際意義，通過選擇合理的物流配送中心節(jié)點的位置實現(xiàn)了整個網(wǎng)絡(luò)的傳輸效率的優(yōu)化。

現(xiàn)實生活中的很多網(wǎng)絡(luò)都具有無標(biāo)度特性。因此，為了更好地解決實際網(wǎng)絡(luò)上的擁塞問題，大部分路由傳輸策略都是基于無標(biāo)度網(wǎng)絡(luò)做模擬仿真。不失一般性，這些無標(biāo)度網(wǎng)絡(luò)上的路由策略是本文回顧和總結(jié)的重點。另外，學(xué)者們對于少部分其他網(wǎng)絡(luò)上的路由策略也有一定研究，例如隨機網(wǎng)絡(luò)[9,25]、小世界網(wǎng)絡(luò)[25,69]、規(guī)則網(wǎng)絡(luò)[9]、樹狀網(wǎng)絡(luò)[9]、平面網(wǎng)絡(luò)[70]等。

7 總結(jié)與展望

近些年來，隨著互聯(lián)網(wǎng)的高速發(fā)展，網(wǎng)絡(luò)信息量呈現(xiàn)爆炸式增長；隨著工業(yè)發(fā)展和經(jīng)濟繁榮，車流量成倍增加；隨著家用電器和工業(yè)用電量的迅猛增加，電力傳輸網(wǎng)絡(luò)承載的負(fù)荷持續(xù)上升。這些變化造成了各網(wǎng)絡(luò)傳輸系統(tǒng)的高強度負(fù)載，極易導(dǎo)致網(wǎng)絡(luò)系統(tǒng)傳輸擁塞。而研究網(wǎng)絡(luò)的路由傳輸策略可以有效改善擁塞問題，提高網(wǎng)絡(luò)系統(tǒng)的傳輸效率，進而有效地提高網(wǎng)絡(luò)的負(fù)載能力，節(jié)省傳輸時間，方便人們的生活。從這個角度出發(fā)，研究網(wǎng)絡(luò)的傳輸策略具有很重要的現(xiàn)實意義。

總結(jié)起來，本文主要回顧了提高網(wǎng)絡(luò)傳輸效率的四類路由傳輸策略并對其中有重大影響的策略進行了具體介紹。盡管科研工作者們在此課題上已投入很多工作并做出一定的成績，這其中仍然存在一些問題還未解決并可能成為未來的研究方向。本文認(rèn)為網(wǎng)絡(luò)傳輸效率還可以在以下幾方面進行提高。

1) 相依網(wǎng)絡(luò)上的路由策略研究。現(xiàn)實生活中的各類復(fù)雜網(wǎng)絡(luò)系統(tǒng)之間往往是相互作用、相互依賴的[71]。例如，航空線路網(wǎng)絡(luò)、城市交通網(wǎng)絡(luò)以及鐵道線路網(wǎng)絡(luò)已經(jīng)達(dá)到高度耦合，形成多式聯(lián)運的運輸網(wǎng)絡(luò)；鐵道線路網(wǎng)絡(luò)系統(tǒng)需要電力網(wǎng)絡(luò)系統(tǒng)的供電支持；電力系統(tǒng)與通信網(wǎng)絡(luò)系統(tǒng)相互依賴。目前，雖然學(xué)者們對于相依網(wǎng)絡(luò)上的路由策略有一定研究，例如，文獻(xiàn)[72]以鐵道線路以及火車流量的耦合雙層網(wǎng)絡(luò)為例，對鐵路站點之間相依強度的統(tǒng)計特性進行了研究；文獻(xiàn)[73]以交通網(wǎng)絡(luò)為例，提出了一種相依網(wǎng)絡(luò)模型，對網(wǎng)絡(luò)上的協(xié)同路由進行了研究；文獻(xiàn)[74]對相依網(wǎng)絡(luò)中子網(wǎng)絡(luò)之間的拓?fù)浣Y(jié)構(gòu)關(guān)系進行了研究，然而大多數(shù)路由策略的研究還僅僅局限于單側(cè)網(wǎng)絡(luò)，進一步研究相依網(wǎng)絡(luò)上的路由策略具有很重要的現(xiàn)實意義。

2) 傳輸動力學(xué)誘導(dǎo)的網(wǎng)絡(luò)演化研究。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會影響網(wǎng)絡(luò)傳播動力學(xué)[58]，相應(yīng)地，網(wǎng)絡(luò)傳播動力學(xué)也可能會誘導(dǎo)網(wǎng)絡(luò)的演化。例如，對于城市交通網(wǎng)絡(luò)，人們會盡量避免高峰時期經(jīng)過一些擁擠路段，從而這些原本擁擠路段上的車流量會擴散到其它非中心路段。在實際網(wǎng)絡(luò)中總會存在網(wǎng)絡(luò)同步的現(xiàn)象，即相鄰的節(jié)點之間的動力學(xué)系統(tǒng)之間會相互影響[75-76]，而動力學(xué)系統(tǒng)與網(wǎng)絡(luò)結(jié)構(gòu)之間也必然存在著相互影響和作用[75]。然而目前的工作僅集中于研究網(wǎng)絡(luò)的結(jié)構(gòu)如何影響傳播動力學(xué)，卻較少對傳輸動力學(xué)誘導(dǎo)的網(wǎng)絡(luò)演化給予重視，這是以后研究的重要工作之一。

3) 時變網(wǎng)絡(luò)的路由傳輸策略?，F(xiàn)實網(wǎng)絡(luò)總是隨著時間不斷演化的[77]。城市公交網(wǎng)絡(luò)、軌道交通網(wǎng)絡(luò)、航空航線網(wǎng)絡(luò)等都在不斷擴充站點和路線；通信網(wǎng)絡(luò)中節(jié)點間的通信狀態(tài)只持續(xù)有限的時間；萬維網(wǎng)中的網(wǎng)站個數(shù)不斷呈現(xiàn)迅猛增加的狀態(tài)。因此考慮現(xiàn)實網(wǎng)絡(luò)的時變性，研究時變網(wǎng)絡(luò)上提高網(wǎng)絡(luò)傳輸效率的路由策略是一項很有前景的工作。

4) 路由策略的數(shù)學(xué)模型構(gòu)建。現(xiàn)階段對于網(wǎng)絡(luò)路由傳輸策略的研究僅限于對具體路由方法的運作機制進行描述，但并未進行嚴(yán)謹(jǐn)?shù)睦碚摂?shù)學(xué)證明，導(dǎo)致這些策略的內(nèi)部運行原理無法進行深入的理論解釋。因此，未來需要對路由策略的數(shù)學(xué)模型的構(gòu)建給予高度重視。

5) 有向網(wǎng)絡(luò)以及加權(quán)網(wǎng)絡(luò)的進一步關(guān)注。本文介紹的度量指標(biāo)以及路由傳輸策略大多是用來處理無向網(wǎng)絡(luò)及無權(quán)網(wǎng)絡(luò)的。這是最簡單的情況，但是實際復(fù)雜網(wǎng)絡(luò)很多都是有向和加權(quán)的，例如電力網(wǎng)絡(luò)，因特網(wǎng)等，所以對有向網(wǎng)絡(luò)以及加權(quán)網(wǎng)絡(luò)的研究需要給予更多關(guān)注。

6) 動態(tài)路徑選擇策略優(yōu)化。本文回顧了幾種動態(tài)路徑選擇策略。這些策略同時整合了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和局部動力學(xué)信息，對提高網(wǎng)絡(luò)吞吐量有很大幫助。然而，總是需要一個時間差來更新局部動力學(xué)信息，導(dǎo)致數(shù)據(jù)包的傳輸時間不會大幅度縮短，只能有限地提高網(wǎng)絡(luò)傳輸效率。因此，目前很棘手的一個問題就是研究如何將時滯降到最低，從而使動態(tài)策略更高效也更實用。

[1] EBEL H, MIELSCH L I, BORNHOLDT S. Scale-free topology of e-mail networks[J]. Physical Review E, 2002, 66: 035103.

[2] AIELLO W, CHUNG F, LU L. A random graph model for massive graphs[C]//Proceedings of the thirty-second annual ACM symposium on Theory of computing. Newyork: [s.n.], 2000: 171-180.

[3] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440- 442.

[4] LI W, CAI X. Statistical analysis of airport network of China[J]. Physical Review E, 2004, 69(4): 046106.

[5] HELBING D. Traffic and related self-driven many-particle systems[J]. Reviews of Modern Physics, 2001, 73(4): 1067.

[6] ALBERT R, JEONG H, BARABASI A L. Internet: Diameter of the world-wide web[J]. Nature, 1999, 401(6749): 130-131.

[7] KAHNG B, PARK Y, JEONG H. Robustness of the in-degree exponent for the world-wide web[J]. Physical Review E, 2002, 66(4): 046107.

[8] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[9] ZHAO L, LAI Y C, PARK K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2): 026125.

[10] ZHANG G Q, WANG D, LI G J. Enhancing the transmission efficiency by edge deletion in scale-free networks[J]. Physical Review E, 2007, 76(1): 017101.

[11] YAN G, ZHOU T, HU B, et al. Efficient routing on complex networks[J]. Physical Review E, 2006, 73(4): 046108.

[12] DANILA B, YU Y, MARSH J A, et al. Optimal transport on complex networks[J]. Physical Review E, 2006, 74(4): 046106.

[13] DANILA B, YU Y, MARSH J A, et al. Transport optimization on complex networks[J]. Chaos, 2007, 17(2): 026102.

[14] WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2): 026111.

[15] YIN C Y, WANG B H, WANG W X, et al. Efficient routing on scale-free networks based on local information[J]. Physics Letters A, 2006, 351(4): 220-224.

[16] TADIC B, RODGERS G J, THURNER S. Transport on complex networks: Flow, jamming and optimization[J]. International Journal of Bifurcation and Chaos, 2007, 17(7): 2363-2385.

[17] WANG B H, ZHOU T. Traffic flow and efficient routing on scale-free networks: a survey[J]. Journal of the Korean Physical Society, 2007, 50: 134.

[18] CHEN S, HUANG W, CATTANI C, et al. Traffic dynamics on complex networks: a survey[J]. Mathematical Problems in Engineering, doi: 10.1155/2010/732698.

[19] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[20] GUIMERA R, DIAZ-GUILERA A, VEGA-REDONDO F, et al. Optimal network topologies for local search with congestion[J]. Physical Review Letters, 2002, 89(24): 248701.

[21] ARENAS A, DIAZ-GUILERA A, GUIMERA R. Communication in networks with hierarchical branching[J]. Physical Review Letters, 2001, 86(14): 3196-3199.

[22] GOH K I, KAHNG B, KIM D. Universal behavior of load distribution in scale-free networks[J]. Physical Review Letters, 2001, 87(27): 278701.

[23] LIU Z, MA W, ZHANG H, et al. An efficient approach of controlling traffic congestion in scale-free networks[J]. Physica A, 2006, 370(2): 843-853.

[24] YANG H X, WANG W X, WU Z X, et al. Traffic dynamics in scale-free networks with limited packet-delivering capacity[J]. Physica A, 2008, 387(27): 6857-6862.

[25] LING X, HU M B, LONG J C, et al. Traffic resource allocation for complex networks[J]. Chinese Physics B, 2013, 22(1): 018904.

[26] CAO X B, DU W B, CHEN C L, et al. Effect of adaptive delivery capacity on networked traffic dynamics[J]. Chinese Physics Letters, 2011, 28(5): 058902.

[27] HU M B, WANG W X, JIANG R, et al. The effect of bandwidth in scale-free network traffic[J]. Europhysics Letters, 2007, 79(1): 14003.

[28] LING X, HU M B, DU W B, et al. Bandwidth allocation strategy for traffic systems of scale-free network[J]. Physics Letters A, 2010, 374(48): 4825-4830.

[29] JIANG Z Y, LIANG M G, ZHANG S, et al. An efficient bandwidth allocation strategy for scale-free networks[J]. International Journal of Modern Physics C, 2012, 23(10): 50065.

[30] JIANG Z Y, LIANG M G, LI Q, et al. Optimal dynamic bandwidth allocation for complex networks[J]. Physica A, 2013, 392(5): 1256-1262.

[31] TOROCZKAI Z, BASSLER K E. Network dynamics: Jamming is limited in scale-free systems[J]. Nature, 2004, 428(6984): 716-716.

[32] LIU Z, HU M B, JIANG R, et al. Method to enhance traffic capacity for scale-free networks[J]. Physical Review E, 2007, 76(3): 037101.

[33] PENNA T J P. Traveling salesman problem and Tsallis statistics[J]. Physical Review E, 1995, 51(1): R1-R3.

[34] HUANG W, CHOW T W S. An efficient strategy for enhancing traffic capacity by removing links in scale-free networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010(1): P01016.

[35] HUANG W, CHOW T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos, 2010, 20(3): 033123.

[36] MOTTER A E, ZHOU C S, KURTHS J. Enhancing complex network synchronization[J]. Europhysics Letters, 2005, 69(3): 334-340.

[37] BUI T N, JONES C. Finding good approximate vertex and edge partitions is NP-hard[J]. Information Processing Letters, 1992, 42(3): 153-159.

[38] JIANG Z Y, LIANG M G. Improved efficient routing strategy on scale-free networks[J]. International Journal of Modern Physics C, 2012, 23(2): 50016.

[39] DONG J Q, HUANG Z G, ZHOU Z, et al. Enhancing transport efficiency by hybrid routing strategy[J]. Europhysics Letters, 2012, 99(2): 20007.

[40] PU C L, ZHOU S Y, WANG K, et al. Efficient and robust routing on scale-free networks[J]. Physica A, 2012, 391(3): 866-871.

[41] ZHANG X, HE Z, HE Z, et al. Probability routing strategy for scale-free networks[J]. Physica A, 2013, 392(4): 953- 958.

[42] ECHENIQUE P, GOMEZ-GARDENES J, MORENO Y. Dynamics of jamming transitions in complex networks[J]. Europhysics Letters, 2005, 71(2): 325-331.

[43] ECHENIQUE P, GOMEZ-GARDENES J, MORENO Y. Improved routing strategies for Internet traffic delivery[J]. Physical Review E, 2006, 70(5): 056105.

[44] ZHANG H, LIU Z, TANG M, et al. An adaptive routing strategy for packet delivery in complex networks[J]. Physics Letters A, 2007, 364(3): 177-182.

[45] LING X, HU M B, JIANG R, et al. Global dynamic routing for scale-free networks[J]. Physical Review E, 2010, 81(1): 016113.

[46] WANG W X, YIN C Y, YAN G, et al. Integrating local static and dynamic information for routing traffic[J]. Physical Review E, 2006, 74(1): 016101.

[47] WU Z X, PENG G, WONG W M, et al. Improved routing strategies for data traffic in scale-free networks[J]. Journal of Statistical Mechanics: Theory and experiment, 2008(11): P11002.

[48] JIANG Z Y, LIANG M G. Incremental routing strategy on scale-free networks[J]. Physica A, 2013, 392(8): 1894- 1901.

[49] TAN F, XIA Y. Hybrid routing on scale-free networks[J]. Physica A, 2013, 392(18): 4146-4153.

[50] ADAMIC L A, LUKOSE R M, PUNIYANI A R, et al. Search in power-law networks[J]. Physical Review E, 2001, 64(4): 046135.

[51] NOH J D, RIEGER H. Random walks on complex networks[J]. Physical Review Letters, 2004, 92(11): 118701.

[52] DE MOURA A P S. Fermi-dirac statistics and traffic in complex networks[J]. Physical Review E, 2005, 71(6): 066114.

[53] ZHAO L, PARK K, LAI Y C. Attack vulnerability of scale- free networks due to cascading breakdown[J]. Physical Review E, 2004, 70(3): 035101.

[54] PARK K, LAI Y C, ZHAO L, et al. Jamming in complex gradient networks[J]. Physical Review E, 2005, 71(6): 065105.

[55] WU Z X, WANG W X, YEUNG K H. Traffic dynamics in scale-free networks with limited buffers and decongestion strategy[J]. New Journal of Physics, 2008, 10(2): 023025.

[56] SREENIVASAN S, COHEN R, LOPEZ E, et al. Structural bottlenecks for communication in networks[J]. Physical Review E, 2007, 75(3): 036105.

[57] WANG D. Mixed routing strategy in scale-free networks[C]//The 25th Chinese Control and Decision Conference. Guiyang: IEEE, 2013: 5048-5051.

[58] TADIC B, THURNER S, RODGERS G J. Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations [J]. Physical Review E, 2004, 69(3): 036102.

[59] TADIC B, THURNER S. Information super-diffusion on structured networks[J]. Physica A, 2004, 332: 566-584.

[60] TANG M, ZHOU T. Efficient routing strategies in scale-free networks with limited bandwidth[J]. Physical Review E, 2011, 84(2): 026116.

[61] DU W B, WU Z X, CAI K Q. Effective usage of shortest paths promotes transportation efficiency on scale-free networks[J]. Physica A, 2013, 392(17): 3505-3512.

[62] KIM K, KAHNG B, KIM D. Jamming transition in traffic flow under the priority queuing protocol[J]. Europhysics Letters, 2009, 86(5): 58002.

[63] XU P, HONG C. A global dynamic queuing strategy on scale-free networks[C]//In Green Computing and Communications, 2013 IEEE and Internet of Things, IEEE International Conference on and IEEE Cyber, Physical and Social Computing. Beijing: [s.n.], 2013: 856-859.

[64] OHIRA T, SAWATARI R. Phase transition in a computer network traffic model[J]. Physical Review E, 1998, 58(1): 193-195.

[65] SOLE R V, VALVERDE S. Information transfer and phase transitions in a model of internet traffic[J]. Physica A, 2001, 289(3): 595-605.

[66] WOOLF M, ARROWSMITH D K, MONDRAGON-C R J, et al. Optimization and phase transitions in a chaotic model of data traffic[J]. Physical Review E, 2002, 66(4): 046106.

[67] VALVERDE S, SOLE R V. Self-organized critical traffic in parallel computer networks[J]. Physica A, 2002, 312(3): 636-648.

[68] CHEN Y H, WANG B H, ZHAO L C, et al. Optimal transport on supply-demand networks[J]. Physical Review E, 2010, 81(6): 066105.

[69] 張國清, 程蘇琦. 小世界網(wǎng)絡(luò)中的刪邊擴容效[J]. 中國科學(xué): 信息科學(xué), 2012, 42(2): 151-160.

ZHANG Guo-qing, CHENG Su-qi. Enhancing network capacity effects of edge-removal in small-world networks [J]. Scientia Sinica Informationis, 2012, 42(2): 151-160.

[70] DANILA B, SUN Y, BASSLER K E. Collectively optimal routing for congested traffic limited by link capacity[J]. Physical Review E, 2009, 80(6): 066116.

[71] KURANT M, THIRAN P. Layered complex networks[J]. Physical Review Letters, 2006, 96(13): 138701.

[72] WANG J L, ZHOU T, SHI J J, et al. Empirical Analysis of dependence between stations in Chinese railway station[J]. Physica A, 2009, 388: 2949-2955.

[73] GU C G, ZOU S R, XU X L, et al. Onset of cooperation between layered networks[J]. Physical Review E, 2011, 84: 026101.

[74] ZOU S R, ZHOU T, LIU A F, et al. Topological relation of layered complex networks[J]. Physica A, 2010, 374(43): 4406-4410.

[75] 趙明, 汪秉宏, 蔣品群, 等. 復(fù)雜網(wǎng)絡(luò)上動力系統(tǒng)同步的研究進展[J]. 物理學(xué)進展, 2005, 25(3): 273-295.

ZHAO Ming, WANG Bing-hong, JIANG Ping-qun, et al. Recent advancement in research of synchronization of dynamical systems on complex networks[J]. Progress In Physics, 2005, 25(3): 273-295.

[76] 趙明, 周濤, 陳關(guān)榮, 等. 復(fù)雜網(wǎng)絡(luò)上動力系統(tǒng)同步的研究進展Ⅱ——如何提高網(wǎng)絡(luò)的同步能力[J]. 物理學(xué)進展, 2008, 28(1): 22-34.

ZHAO Ming, ZHOU Tao, CHEN Guan-rong. A review on synchronization of dynamical systems on complex networksⅡ: How to enhance the network synchronizability[J]. Progress In Physics, 2008, 28(1): 22-34.

[77] HOLME P, SARAMAKI J. Temporal networks[J]. Physics Reports, 2012, 519: 97-125.

編 輯 蔣 曉

Advance in the Research on Routing Strategy of Networks

CHENG Can, GUO Qiang, and LIU Jian-guo

(Research Center of Complex Systems Science, University of Shanghai for Science & Technology Yangpu Shanghai 200093)

With the wide application of complex networks in many fields, how to improve the transportation efficiency has become the bottleneck of its further development in practice. This article classifies these routing ways from four aspects—reassigning the distribution of nodes’ capacity and links’ bandwidth, modifying network topology, designing routing strategies, and proposing queuing strategies. we also introduce some influential strategies in detail. Finally, we point out some potential directions in the future. This work is helpful for new learners and researchers to be familiar with this field and may be helpful for network designers or regulators to improve the network efficiency and avoid traffic jams.

complex networks; congestion; routing strategy; transportation efficiency

TP393

A

10.3969/j.issn.1001-0548.2015.01.001

2014-04-09；

2014-12-01

國家自然科學(xué)基金(71171136，61374177，71371125)；上海市一流學(xué)科建設(shè)項目(XTKX2012)；教育部人文社科基金(13YJA630023)；上海市大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(XJ2013120)

程燦(1993-)，女，本科生，主要從事網(wǎng)絡(luò)路由策略方面的研究.