k-ary n-cube網(wǎng)絡(luò)中的死鎖及負(fù)載均衡研究.pdf

1、作為互連網(wǎng)絡(luò)中一種流行的拓?fù)渚W(wǎng)絡(luò)，k—ary n—cube網(wǎng)絡(luò)目前面臨著多應(yīng)用、多業(yè)務(wù)以及業(yè)務(wù)分布不均等問題，這就要求設(shè)計(jì)的路由算法要有較強(qiáng)的負(fù)載均衡能力，以及所采用的死鎖解決算法具有適應(yīng)各種網(wǎng)絡(luò)業(yè)務(wù)的能力。 當(dāng)前相關(guān)技術(shù)都沒有很好地解決這些問題，如負(fù)載均衡路由算法存在著資源利用失衡等問題；死鎖方面則存在著死鎖檢測時(shí)誤檢率過高等問題。基于此，本文的主要工作和貢獻(xiàn)包括如下兩方面： 1．在研究現(xiàn)有死鎖技術(shù)的基礎(chǔ)上，提出了基于

2、環(huán)的死鎖檢測路由算法（Cycle based Deadlock Detection routing algorithm，CDD）。與傳統(tǒng)檢測算法僅采用超時(shí)機(jī)制不同，CDD從信道依賴環(huán)——死鎖形成的原因入手對(duì)死鎖進(jìn)行檢測。根據(jù)k—ary n—cube網(wǎng)絡(luò)拓?fù)涮匦裕珻DD分別檢測同維環(huán)中形成的死鎖與不同維（即異維）環(huán)中形成的死鎖。在同維中CDD運(yùn)用流控策略，即分組進(jìn)入當(dāng)前所在信道前，該信道的緩存剩余量大小進(jìn)行檢測；在異維中CDD則通過分組的

3、轉(zhuǎn)向來檢測。CDD繼而對(duì)那些初步檢測判定為死鎖的分組，分別根據(jù)其所申請(qǐng)的所有輸出信道處于忙狀態(tài)的時(shí)間間隔做最后的檢測。本文運(yùn)用OPNET仿真軟件對(duì)其進(jìn)行仿真，結(jié)果表明，CDD與現(xiàn)有soft—based死鎖檢測算法相比，具有較低的死鎖誤檢率，較低的時(shí)間門限值敏感性等。 2．針對(duì)現(xiàn)有負(fù)載均衡路由算法存在的問題，提出了跨區(qū)域的適應(yīng)性路由算法（Quadrant Crossing Routing algorithm，QCR）。QCR按照分