2009年6月28日 星期日

多存取協定 ( Multi-access Protocol )

多存取協定 ( Multi-access Protocol )

ALOHA
 
 純 ALOHA ( Pure ALHA )
 ALHA系統基本想法很簡單:使用者只要有資料傳送,就讓資料傳送。當然這樣會發生碰撞,而碰撞的框架(資料框/frame)會損毀。由於廣播回饋的特性,藉由聽取頻道,傳送端一定可以發現傳送的框架是否損毀。
   
 如果使用LAN,回饋會馬上傳回來,使用衛星,則約有 270 msec 的延遲,傳送端才能知道是否成功。框架如果損毀,傳送端須等待一隨機時間,然後再傳送。傳送時間必須是亂數,否則同樣這些框架會一再碰撞。多使用者共享一個頻道,會導致衝突的系統,稱為競爭 ( Contention ) 系統。
  
 槽式ALOHA (Slotted ALOHA )
 為一種可將 ALOHA 容量加倍的方法 ( 1972 Roberts 提出 )。將時間切割為離散式區間,每個區間對應到一個frame。要達到同步的一個方法,就是讓其中一個工作站像時鐘一般,在每個區間發射一個訊號。
Pure ALOHA造成碰撞(collision)的機率極高,為改善網路效能,有人提出slotted ALOHA,將通訊頻道的使用分成一小段時間,約是將一個資料框送上介質的時間,所有的網路節點在時間上必須同步,只有在固定時段上才能傳送資料框,也表示只有在這些時段上才會發生碰撞。
 
 相對於 Pure ALOHA ,Slotted ALOHA 並不需要電腦送出回歸鍵 ( return ),才開始傳送,而是需要等到下一個時槽開始,才能傳送。
 
載子感測多存取 ( Carrier Sense Multiple Access )
   
 機率為1之持續性載子感測多重存取( 1-persistent CSMA ,Carrier Sense Multiple Access )
 當工作站有資料要傳送時,首先監聽頻道上是否有他人在傳輸。如果頻道很忙,則工作站會先等待,直到頻到閒置下來為止。當工作站偵測頻道閒置,則開始傳送框架。如果有碰撞發生,工作站再等待一到隨機時間,然後重新傳送。
 
 此協定之所以稱為機率為1之持續性,是因為只要一發現頻道是閒置時,工作站傳輸的機率為1。
 
 非持續性載子感測多重存取 ( Nonpersistent CSMA )
 在傳送前,工作站首先感應頻道。如果沒有其他人在傳送,則此工作站開始傳送,如果頻道已在使
 用,此工作站並不會為了要抓住前一次傳輸的結束,而持續的感應。相對的,它會等待一個隨機時
 間,然後重覆此演算法。
 
 機率為p之持續性載子感測多重存取( p-persistent CSMA ,Carrier Sense Multiple Access )
 應用於時槽式頻道。當工作站開始準備要傳送時,它會開使感應頻道。如果頻道閒置,則有p的傳送機率,而有q = 1 - p 的機率會延到下一個時槽。如果下一個時槽也是閒置,則可傳輸或再往後延遲,機率仍為p和q。
 
具有碰撞偵測的載子感測多存取
( Carrier Sense Multiple Access with Collision Detection ; CSMA/CD )

原理
在網路上任何一台工作站主機欲與網路上任何一台工作站或伺服器從事資料傳輸時,
該主機要先傾聽 (listen) 網路上是否有其它工作站也在發出要求上網路的信號,如果剛好兩台工作站主機一起同時發出信號,結果勢必產生信號碰撞,此時兩台工作站同時退出上網路爭奪戰,等一段任意時間 (random time) 後再重新發出上網路信號,如果很慶幸此時網路上沒有任何其他信號存在後,該工作站可以傳輸資料至其欲送達之目的地﹔

如果很不幸又發生碰撞或是網路還在從事資料傳輸工作,碰撞事件免不了要發生,因此該工作站仍須等一段任意時間候再嘗試下次機會。這種運作方式稱之為 CSMA/CD。亦即為多重存取/碰撞偵測 (Carrier Sense Multiple Access/Collision Detection, CSMA/CD) 基頻技術傳送封包 (packet)。
當碰撞發生被偵測出來以後,雙方的節點都要送出一個擁塞 (jam) 信號到整個網路,此時網路上所有節點都要停止傳輸動作,並進入等待狀態 (wait state),等待下一個機會。
當兩工作站感應頻道閒置時,而同時開始傳送frame,兩者幾乎可以同時偵測出碰撞。與其讓它傳完整個frame(or packet),卻處處受到干擾,倒不如一旦偵測到碰撞,馬上就停止傳送。很快終止損壞框架的傳輸,可以節省時間以及頻寬。

From WikiPedia
用載波偵聽多路訪問(CSMA)時,所有機器都在 bus 等偵聽通道連接(Multiple Access)。有時儘管偵聽通道已空閒(Carrier Sense:通道的監聽,例如以網卡確定無電壓起伏。),但由於通道傳播遲延的原因,前面已發送的數據尚未到達對方,因此發送的數據仍會發生衝突。 CSMA/CD是對CSMA方式的進一步改進。其原理是在偵聽通道閒置後,在發送數據時網路卡等設備會同時進行衝突檢測。(Collision Detection:當兩個波重疊時會造成電壓異常。)如果在發送數據過程中檢測到衝突,就立即停止發送數據,並在固定時間(一開始是 1 slot times)內等待隨機的時間,再重複發送。若依舊碰撞,則採用 en:truncated binary exponential backoff algorithm,十次之內停止前一次「固定時間」的兩倍時間內隨機再發送,十次後則停止前一次「固定時間」內隨機再發送。嘗試 16 次之後則放棄傳送。

CSMA/CD algorithm:

  • Adapter從network layer取得datagram(資料封包),建立frame。
  • 如果adapter sences(感測)channel(通道)是idle(閒置的),便傳送frame。若是busy,則wait到channel為idle為止,再傳送。
  • 沒有collision,如果該adapter在傳送frame時,沒有其他adapter在傳送(即也在使用channel),則該adapter便完成該frame的傳送。
  • 反之,有collision,有其他adapter在傳送,該adapter便會aborts停止傳送frame,而送出一48 bits的jam signal(擁擠訊號)。
  • 送出jam signal後,該adapter便會進入exponential backoff。第n次collision,adapter便從0~2n-1中隨機選一k值,並wait K*512個bit times,然後再去重新sences(感測)channel(通道)。例:第3次collision,從0,1,2,3,4,5,6,7中隨機選一值。


sources:
http://www.cs.nchu.edu.tw/~fileman/notepad/dc4_2.htm
http://www.scu.edu.tw/~distedu/chap4/section4-11.htm
http://zh.wikipedia.org/wiki/CSMA/CD
http://sls.weco.net/node/10698

2009年6月2日 星期二

網絡資源

網絡資源
source: http://news.cnblogs.com/n/47230/


1. MIT計算機教程

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/index.htm

大名鼎鼎的MIT免費教程,適合在校的學生.可惜我上學那會兒在追求APM(不是ACM).沒機會進MIT,但是你有機會和MIT的學生有相同的課程.如果你感興趣,還能發現其他專業的課程.我個人比較喜歡經濟學的一些課程.

2. http://www.euebook.com/

不多的基本免費的書,都是英文版的.

3. http://www.ibm.com/developerworks/

這個實在太有名了,有中文的,但是英文的資料很全.建議所有熱愛Open Source的人都去那裡逛逛.當然你足夠牛的話,還可以寫一些教程給他們,還能有稿費.

4. http://webcast.berkeley.edu/courses.php

這是大名鼎鼎的伯克利教程,而且是音頻版的.既可以學習專業知識,還可以鍛煉你的英語聽力,有空閒時間的朋友可以去淘淘.

5. http://onlinebooks.library.upenn.edu/

非常多的online books

6. http://books.google.com/

這就是著名的Google books計劃了.很多的書,尤其是喜歡看英文版書籍的,這裡頗豐富.

7. http://java.sun.com/docs/books/tutorial/index.html

學習java還是從這裡開始吧.

8. http://www.huihoo.com/

灰狐動力,我每隔一段時間都去看一下.無論做什麼項目,把這個網站當作FAQ用吧.

9. http://docs.huihoo.com/

灰狐動力的二級域名了,裡面的資料整理的不錯,會給你驚喜的!




1. Google Code university

http://code.google.com/edu/

這是一個學習的好地方,目的是為計算機學院的學生提供一些教程和示例代碼,涉及的範圍有AJAX編程、分佈式系統、網絡安全、算法、編程語言如python、java、C++,其中圖文並茂,並且有很多視頻,如果你英語足夠應付的話,這些視頻都是不可多得的資源。



2. tools, such as mysql,software configuration management

http://code.google.com/edu/tools101/index.html

這裡介紹了幾個工具,不知道Google為什麼把mysql放在tool的目錄裡。無所謂了,這裡介紹了一些mysql的基礎知識以及如何設計數 據庫.軟件版本控制的介紹中主要介紹了SVN。最後還介紹了linux中常用的命令、權限控制,以及grep的處理文本的常用方法。 (grep是linux下非常有用的命令,使用恰當可以節省你大量的時間,關於grep是什麼,請看這裡)


3.計算機課程資源

http://code.google.com/edu/resources/index.html

這裡列出了非常多的有用資源,涉及有離散數學、編程介紹、數據結構和算法、操作系統和並發、分佈式系統、網絡安全、計算機圖形學、資源豐富,這就是網絡啊!



4.推薦看一下這個鏈接:http://www.freebyte.com/programming/

裡面列出了非常多free的資源.


5.這是Google wave:

http://code.google.com/apis/wave/



6.這是Google android

官網被和諧了,可以看有人做的鏡像.

http://androidappdocs.appspot.com/