[發(fā)明專利]固定沖突率重傳延時(shí)方法和系統(tǒng)

無效

• 申請?zhí)枺?/td>: 02118823.8
• 申請日: 2002-04-29
• 公開（公告）號: CN1384645A
• 公開（公告）日: 2002-12-11
• 發(fā)明（設(shè)計(jì)）人: 李金鵬;羅伯特·C·王
• 申請（專利權(quán)）人: 朗迅科技公司
• 主分類號: H04L12/28
• 分類號: H04L12/28;H04L12/24
• 代理公司: 中國國際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所
• 代理人: 蔣世迅

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

本發(fā)明一般涉及多個(gè)用戶競爭接入數(shù)據(jù)網(wǎng)絡(luò)的數(shù)據(jù)爭用解，更具體說，是涉及解決數(shù)據(jù)沖突的系統(tǒng)和方法。

背景技術(shù)

在把多個(gè)用戶與一共享通信信道連接的任何網(wǎng)絡(luò)中，當(dāng)出現(xiàn)爭用時(shí)，通常用某種方法解決由哪一個(gè)用戶獲得該信道的使用。當(dāng)兩個(gè)或更多用戶同時(shí)試圖在同一帶寬中發(fā)送數(shù)據(jù)時(shí)，即發(fā)生沖突，數(shù)據(jù)可能丟失。解決用戶之間的爭奪并從數(shù)據(jù)沖突中恢復(fù)的各種方法，常常被稱為媒體接入控制(MAC)協(xié)議。

MAC協(xié)議的一種主要類型，是隨機(jī)接入型。該類型協(xié)議采用分組爭用技術(shù)，如時(shí)分式ALOHA或載波檢測多址(Carrier?Sense?MultipleAccess，CSMA)來處理信道爭用。時(shí)分式Aloha通過把信道分為時(shí)隙，并要求各用戶在每一時(shí)隙開始時(shí)發(fā)送，以降低數(shù)據(jù)沖突的數(shù)量。在時(shí)分式ALOHA系統(tǒng)中，當(dāng)兩個(gè)或更多用戶同時(shí)向同一時(shí)隙發(fā)送時(shí)，出現(xiàn)沖突。CSMA通過讓用戶監(jiān)控?cái)?shù)據(jù)信道，以確定該信道是否忙或可供發(fā)送使用。在CSMA系統(tǒng)中，當(dāng)兩個(gè)或更多用戶同時(shí)檢測到一信道空閑并同時(shí)發(fā)送時(shí)，出現(xiàn)沖突。

一種獨(dú)立的MAC協(xié)議類型，是按需分配型。該類型協(xié)議通過把信道分為若干預(yù)約時(shí)隙(reservation?slot)，并要求用戶預(yù)約一用于發(fā)送的信道時(shí)隙，據(jù)此管理網(wǎng)絡(luò)爭用。與隨機(jī)接入?yún)f(xié)議不同，按需分配型系統(tǒng)上的用戶得到保證，一旦實(shí)現(xiàn)了成功的預(yù)約，則數(shù)據(jù)將無沖突地發(fā)送。但是，當(dāng)兩個(gè)或更多用戶試圖同時(shí)在同一帶寬中進(jìn)行預(yù)約時(shí)，則在發(fā)送的預(yù)約階段，按需分配沖突仍然出現(xiàn)。

當(dāng)把多個(gè)用戶與一共享通信信道連接時(shí)，不論是用隨機(jī)接入?yún)f(xié)議還是用按需分配協(xié)議，數(shù)據(jù)沖突都是無法回避的事實(shí)。為避免每次沖突發(fā)生時(shí)丟失數(shù)據(jù)，MAC協(xié)議使用沖突解或重傳延時(shí)算法從沖突中恢復(fù)，并確定何時(shí)重發(fā)沖突的數(shù)據(jù)。

本領(lǐng)域有三種廣為人知的重傳延時(shí)算法類型。第一種是分解算法，亦稱樹算法。第二種是自適應(yīng)p持續(xù)算法(adaptive?p-persistencealgorithm)，而第三種是二進(jìn)制指數(shù)重傳延時(shí)(binary?exponentialback-off，BEB)算法。每一算法按不同的途徑確定何時(shí)重發(fā)先前沖突的數(shù)據(jù)。

確定該三種重傳延時(shí)類型算法中哪一種最佳，不存在唯一的標(biāo)準(zhǔn)。一個(gè)性能標(biāo)準(zhǔn)是吞吐量。一般說，吞吐量是在指定時(shí)間內(nèi)，從一個(gè)用戶傳送至另一個(gè)用戶的數(shù)據(jù)量。在各種爭用解的算法中，吞吐量常常用成功的傳送數(shù)與傳送機(jī)會(huì)總數(shù)之比來測量。例如，在使用按需分配協(xié)議的無線互連網(wǎng)接入系統(tǒng)中，吞吐量是完成的成功預(yù)約數(shù)與可用的預(yù)約時(shí)隙總數(shù)之比。

在前述三種重傳延時(shí)算法類型中，樹算法一般有最高的吞吐量。雖然各種樹算法的最大穩(wěn)定吞吐量仍舊不清楚，但樹算法曾達(dá)到0.4878的吞吐量。不過，該較高的吞吐量是有代價(jià)的。在該三種重傳延時(shí)算法類型的實(shí)施中，樹算法遠(yuǎn)遠(yuǎn)復(fù)雜得多，是最復(fù)雜的，又因?yàn)闃渌惴ㄒ蟾饔脩魧γ恳活A(yù)約時(shí)隙的三種可能條件(成功、沖突、空閑)有充分的了解，所以能實(shí)施樹算法的網(wǎng)絡(luò)，數(shù)量有限。

第二種重傳延時(shí)算法類型是自適應(yīng)p持續(xù)算法。自適應(yīng)p持續(xù)算法的原理，是利用預(yù)約時(shí)隙的反饋，計(jì)算由估算的現(xiàn)用用戶(參與競爭該帶寬的用戶)數(shù)確定的重發(fā)概率p。當(dāng)出現(xiàn)一空閑時(shí)隙時(shí)，該算法便增大p，當(dāng)檢測到?jīng)_突時(shí)，該算法便減小p。當(dāng)系統(tǒng)中有無限數(shù)量的用戶時(shí)，自適應(yīng)p持續(xù)算法可獲得的最大吞吐量最多是1/e＝0.3679。在此情況下，空閑出現(xiàn)的概率是1/e～0.3679，而沖突出現(xiàn)的概率是1-2/e～0.2642。

正如樹算法一樣，自適應(yīng)p持續(xù)算法要求的有關(guān)數(shù)據(jù)信道的反饋，許多網(wǎng)絡(luò)并不具備。在許多系統(tǒng)中，包括許多計(jì)算機(jī)和無線通信網(wǎng)絡(luò)中，各個(gè)用戶只知道他們自己的分組是否發(fā)送成功，但沒有網(wǎng)絡(luò)中其他信道狀態(tài)的信息。由于如此多的多用戶系統(tǒng)(包括Ethernet、CATV、和無線網(wǎng)絡(luò))不設(shè)置信道反饋要求，所以經(jīng)常把BEB算法用于沖突解。

不像樹算法和自適應(yīng)p持續(xù)算法，BEB算法不要求用戶提供任何數(shù)據(jù)信道的反饋。BEB的工作原理如下：當(dāng)分組到達(dá)發(fā)送隊(duì)列的隊(duì)首時(shí)，盡快完成即時(shí)首先發(fā)送。如果發(fā)送的用戶檢測到?jīng)_突，則在k個(gè)時(shí)隙后重發(fā)，這里k是均勻分布在區(qū)間[1，2ⁱ]上的隨機(jī)整數(shù)。在其上抽取均勻分布數(shù)的區(qū)間，本文此后稱為重傳延時(shí)窗口。如果i(沖突數(shù))大于16，則丟棄并撤消該分組。某一分組一旦發(fā)送成功或被撤消，i被復(fù)位為零。作為BEB基礎(chǔ)的邏輯是，對給定的分組，大量不成功發(fā)送，意味著更多用戶正在競爭該可用帶寬并應(yīng)打開更大的重傳延時(shí)窗口。