在總線型網絡中，每個站點都能獨立地決定幀的發送（沒有主站點和從站點之分），很顯然，如果兩個或多個站點同時向總線上發送幀，就會産生媒體通路沖突（僅指在沒采用信道複用情況下），導緻所發送的幀都出錯。是以，在這種總線型網絡中，一個使用者資料發送的成功與否，很大程度上取決于發送資料時是否會與其它使用者發送的資料産生總線媒體争用。這時就需要一種能有效避讓沖突發生的技術，確定每個站點在向總線上發送資料時，其它站點均不發送資料，也就是如何使各個站點能盡快地檢測到總線媒體是否空閑。本節所介紹的CSMA（載波偵聽多路通路）就是這樣一種能比較有效解決總線型網絡中媒體争用的技術。
“非-堅持”中的“非”的意思就是指各站點<b>不連續偵聽</b>總線媒體是否空閑，即在發現媒體忙時，先停止偵聽，等過一段時間再來偵聽。具體來講，“非-堅持CSMA”就是某站點發現總線媒體上沒有資料在傳輸時（處于閑狀态），立即發送在等待發送的資料；如果檢測到總線媒體上有資料在傳輸時（處于忙狀态），則等待一段時間再來偵聽，再忙時再等待一段時間來偵聽，以此類推，直到發現總線媒體處于空閑時本站點才可發送資料。
如圖6-7所示的是一個“非-堅持CSMA”媒體通路控制示例。示例中某站點準備要發送一個資料幀Fi。它第一次檢測時發現總線是處于忙狀态，于是隔了一段時間t1後，再來偵聽，還發現總線媒體是處于忙狀态，于是它再隔一段時間t2來偵聽，終于在第三次偵聽時發現總線媒體是處于閑狀态，于是這個站點立即把Fi幀發送出去。
<a href="http://blog.51cto.com/attachment/201302/090413154.png" target="_blank"></a>
圖6-7 “非-堅持CSMA”媒體通路控制示例
這時大家可能已經有疑問了，那就是這個“非-堅持CSMA”算法中，在上次偵聽發現媒體處于忙狀态時需要等待多長時間再來偵聽媒體的狀态呢？答案是不固定的，這個等待的時間是根據“非-堅持CSMA”算法随機産生的（具體産生機制大家可不必深究）。如果采用TDM（時分複用）傳輸方式，則這個延遲時間就是一個時隙長度。
雖然“非-堅持CSMA”算法可以在一定程度上減少沖突的發生，但還是不能完全消除沖突的發生，因為畢竟每個站點發送的資料速度不一樣，資料在信道中傳輸是需要時間的，而且等待的時間也不一定就可以滿足一個幀完全傳輸完畢，是以盡管每個站點都是在檢測到媒體空閑時才發送資料，但仍可能存在前一個幀還在信道中傳輸時，後一個站點的幀就追上來了，發生沖突。
另外，“非-堅持CSMA”算法還存在一個明顯的缺點，這就是一旦偵聽到媒體忙就馬上延遲一個随機時間再重新偵聽，但很可能在再次偵聽之前信道就已經空閑了。也就是“非堅持CSMA”不能把信道剛一變成空閑的時刻找出，影響了信道使用率的提高。是以這種算法主要适用于小型的總線，或者樹形拓撲結構網絡中，不适用于像現在大型的樹形結構以太網中。為了克服這一缺點，可采用下面介紹的兩種“堅持CSMA”。
“1-堅持”中的“1”有兩層含義：一是指發現總線媒體忙時<b>一直持續、不間斷偵聽</b>，直到發現媒體處于閑狀态；二是在偵聽到媒體處于空閑狀态後<b>一定（也就是</b><b>100%</b><b>）發送資料</b>。前面介紹的“非-堅持CSMA”算法是在發現媒體忙後，即随機等待一個延時，然後繼續偵聽，發現媒體處于閑狀态後立即發送資料；而此處的“1-堅持CSMA”算法中是在發現媒體忙時不等待、繼續偵聽，一旦發現空閑即立即發送資料；在資料傳送過程中發生沖突時放棄目前的資料傳送任務，才等待一個延時後再繼續偵聽。
如圖6-8所示的是一個“1-堅持CSMA”媒體通路控制示例。示例中某站點準備要發送一個資料幀Fi。它第一次檢測時發現總線是處于忙狀态，于是繼續偵聽（不等待），第二次偵聽還是還發現總線媒體是處于忙狀态，于是它再繼續偵聽，一直到第n次偵聽時才發現總線媒體是處于閑狀态，于是這個站點立即把Fi幀發送出去。
<a href="http://blog.51cto.com/attachment/201302/090435452.jpg" target="_blank"></a>
圖6-8 “1-堅持CSMA”媒體通路控制應用示例
很明顯，這種算法相對前面介紹的“非-堅持”算法來說的優點就是提高了媒體的使用率，每個站點都在抓住一切有利時機發送資料，因為在沒有發生沖突時是無需等待一個随機延遲就立即進行繼續偵聽，不會出現媒體處于空閑狀态仍沒有站點發送資料的情況。但是，該算法仍有兩個緻命的弱點：一是在有多個站點發送資料的情況下，這種毫不等待的算法，也就使得沖突時常發生。原因就是前面所說的，可能在網絡中同時有多個站點在同一時間檢測到媒體空閑（因為中間沒有一個延遲，也就是一直在偵聽媒體狀态），而立即進行了資料發送，是以更容易發生沖突。二是這種算法發現在媒體忙時一直偵聽，占用了大量網絡和裝置資源。是以“1-堅持CSMA”算法也僅适用于小型的總線型或者樹形拓撲結構網絡，不适用于像現在大型的樹形結構以太網中。
既然前面介紹的兩種算法都存在明顯的不足，自然就會有人繼續後面的開發，于是就生産了新的“p-堅持CSMA”退避算法。其實，“p-堅持CSMA”算法是前面介紹的“非-堅持CSMA”和“1-堅持CSMA”這兩種算法的一種折中算法，取兩者的長處，而盡量克服了兩者的不足。
了解“p-堅持CSMA”退避算法的關鍵就是其中的“p”，是指偵聽到媒體空閑時發送資料的機率（小于1，也就是小于100%），就是指站點在發現媒體空閑時可以立即發送資料的機率為p，也就是<b>不一定（不是</b><b>100%</b><b>）</b>發送資料，還有（1-p）機率是不發送資料。其目的就是為了避免與其他站點發生沖突。
具體來講，“P-堅持CSMA”算法的具體媒體通路控制方法與前面介紹的“1-堅持CSMA”類似，也是在偵聽到媒體處于忙狀态時<b>持續偵聽</b>，當偵聽到媒體處于空閑狀态時，但此時站點<b>不一定</b>會馬上發送資料，根據機率p（這個p值是算法事先确定好的）來選擇發送資料，而在另一個（1-p）機率的時候，即使媒體處于空閑狀态，也會延遲一段時間t（這個t是指端到端的“傳播延時”）後再重新偵聽媒體狀态。
上面所說的“傳播延時”是有計算公式的，具體如下：
傳播延時（μs）=兩站點間的距離（m）÷ 信号傳播速度（m/s）
這裡最難了解就是p機率了。打個比方，p為0.8，也就是80%的空閑狀态下是可以立即發送資料的，還有20%（1-p）的機率是不發送資料，是延遲一個t時間（也就是“傳播延時”）再來偵聽媒體狀态。如果在某段時間中，前面已有一個空閑狀态下沒有發送資料，則下一個空閑狀态下就很可能會立即發送資料了（畢竟有80%的可能性是要發送資料的），否則如果前面連續幾個空閑狀态下都立即發送了資料，則下一個空閑狀态下就可能不發送資料了。總體來說，是否發送資料是随機的，沒有固定哪個空閑狀态下必須發送資料，或者不發送資料，但整體通信過程中在空閑狀态下發送資料的機率都是在p以内。
如圖6-9所示的是一個“p-堅持CSMA”媒體通路控制示例。示例中某站點準備要發送一個資料幀Fi。它第一次檢測時發現總線是處于忙狀态，于是繼續偵聽（不等待），第二次偵聽還是還發現總線媒體是處于忙狀态，于是它再繼續偵聽，第3次偵聽時發現總線媒體是處于閑狀态，但根據機率計算出現在不能發送資料，于是等待一個t時間後，再來偵聽媒體狀态，到第4次偵聽時發現媒體還是處于空閑狀态，根據機率計算得出馬上可以發送資料了，于是把Fi幀發送出去。
<a href="http://blog.51cto.com/attachment/201302/090453856.jpg" target="_blank"></a>
圖6-9 “p-堅持CSMA”媒體通路控制應用示例
從以上分析可以看出，“P-堅持”退避算法是一種既能像“非-堅持CSMA”算法那樣減少沖突，又能像“1-堅持CSMA”算法那樣減少媒體空閑時間的折中方案，也就是綜合了前面所介紹的兩種算法的優點，以實作優缺點互補。
當當網上的連結：http://product.dangdang.com/main/product.aspx?product_id=23166396
京東網上的連結：http://book.360buy.com/11165825.html
卓越網上的連結：http://www.amazon.cn/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C-%E7%8E%8B%E8%BE%BE/dp/B00B0S7LDU/ref=sr_1_1?s=books&ie=UTF8&qid=1358153421&sr=1-1
互動出版網上的連結：<b>http://www.china-pub.com/STATIC/zt_mb/zt_huodong_2013_3.asp?filename=2013_jsj_srwl_130124</b>
互動出版網上本書正在進行“買一贈一”活動（25号截止），詳情點選：http://www.china-pub.com/STATIC/zt_mb/zt_huodong_2013_3.asp?filename=2013_jsj_srwl_130124
本文轉自王達部落格51CTO部落格，原文連結http://blog.51cto.com/winda/1137518如需轉載請自行聯系原作者
茶鄉浪子
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)