How to install mpfr ?
1. first, install GMP to a specific location, eg /usr/local/gmp-5.0.1.
eg: ./comfigure --prefix=/usr/local/gmp-5.0.1
make
make install
2. next, when you build MPFR, use the "--with-gmp-build=" directive when you have installed a new version of gmp,
so that the compliler may not be confused with previous versions.
if I want to isntall MPFR to "/usr/local/mpfr-2.4.2", then type
eg: ./configure --prefix=/usr/local/mpfr-2.4.2 --with-gmp-build=/usr/local/gmp-5.0.1
make
make install
第二章 論心靈的本性 比物體更易於知道
昨天的沈思，令我心中充滿許多疑竇，以致想忘也忘不了，而且我還未看出, 到底有什麼方法可以把它們一掃而空，這就像忽然掉在深水中，既無法在水底穩穩地站住，又無法游到水面而感到手足無措一樣。
雖然如此，我仍然要盡最大的努力，重新沿著昨天所走過的途徑，把所有稍微可懷疑的事物, 置諸不理，宛如已發現它們是絕對虛妄似的。
此外，我還要一直沿著這條途徑走下去，直到找到一些確實的事物為止，即使一無所獲，但是我至少要明確地知道世界上有沒有確定的事物，才甘願罷休。
阿基米德只不過要求一個固定不移的點，就可以據此, 把整個地球從原來的位置移到另一個位置。
同樣的，如果我幸運地發現, 一件確定而不可懷疑的事物，就有權對自己的探究懷抱無窮的希望。
http://www.hfu.edu.tw/~huangkm/ration/desc-medit-2-ch.htm
GNU GMP
http://gmplib.org/
GNU MPFR
http://www.mpfr.org/
Mittwoch, 31. März 2010
Dienstag, 30. März 2010
Arduino : Building avr-gcc from source in Linux
Arduino : building avr-gcc from source in Linux
Before building avr-gcc, you need to install GMP (GNU Multi-Precision Library ) and MPFR.
http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library
http://en.wikipedia.org/wiki/MPFR
http://www.mpfr.org/
http://gmplib.org/
GNU MPFR is a portable C library for arbitrary-precision binary floating-point computation with correct rounding, based on GNU Multi-Precision Library. The computation is both efficient and has a well-defined semantics. It copies the good ideas from the ANSI/IEEE-754 standard for fixed-precision floating-point arithmetic.
The GNU Multiple-Precision Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on
2. I suggest to use the --prefix=/usr/local/gmp-5.0.1 and --prefix=/usr/local/mpfr-2.4.2 directives to install the library in specific locations , so as not to conflict with previous versions when you configure avr-gcc.
LEGOstudio (樂高) 大師五十川芳
http://www.isogawastudio.co.jp/legostudio/index.html
Before building avr-gcc, you need to install GMP (GNU Multi-Precision Library ) and MPFR.
http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library
http://en.wikipedia.org/wiki/MPFR
http://www.mpfr.org/
http://gmplib.org/
GNU MPFR is a portable C library for arbitrary-precision binary floating-point computation with correct rounding, based on GNU Multi-Precision Library. The computation is both efficient and has a well-defined semantics. It copies the good ideas from the ANSI/IEEE-754 standard for fixed-precision floating-point arithmetic.
The GNU Multiple-Precision Library, also known as GMP, is a free library for arbitrary-precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on
2. I suggest to use the --prefix=/usr/local/gmp-5.0.1 and --prefix=/usr/local/mpfr-2.4.2 directives to install the library in specific locations , so as not to conflict with previous versions when you configure avr-gcc.
LEGOstudio (樂高) 大師五十川芳
http://www.isogawastudio.co.jp/legostudio/index.html
building avr-gcc from source..
Arduino project
building avr-gcc from source..
see: Building and Installing the GNU Tool Chain
http://www.nongnu.org/avr-libc/user-manual/install_tools.html
before installing avr-gcc, I need to install GMP and MPFR first.
after installing gmp,
I then try to install MPFR 2.4.2 but I get a warning at the configure stage:
>
> checking if gmp.h version and libgmp version are the same... (5.0.1/4.2.2) no
> configure: WARNING: 'gmp.h' and 'libgmp' seems to have different versions or
> configure: WARNING: we cannot run a program linked with GMP (if you cannot
> configure: WARNING: see the version numbers above).
> configure: WARNING: However since we can't use 'libtool' inside the configure,
> configure: WARNING: we can't be sure. See 'config.log' for details.
--with-gmp-build=pathname
--with-gmp=pathname
--with-gmp-include=pathname
--with-gmp-lib=pathname
--with-mpfr=pathname
--with-mpfr-include=pathname
--with-mpfr-lib=pathname
2. If you do not have GMP (the GNU Multiple Precision library), the MPFR library and/or the MPC library installed in a standard location and you want to build GCC, you can explicitly specify the directory where they are installed (`--with-gmp=gmpinstalldir', `--with-mpfr=mpfrinstalldir').
3. The --with-gmp=gmpinstalldir option is shorthand for --with-gmp-lib=gmpinstalldir/lib and --with-gmp-include=gmpinstalldir/include.
Likewise the --with-mpfr=mpfrinstalldir option is shorthand for --with-mpfr-lib=mpfrinstalldir/lib and --with-mpfr-include=mpfrinstalldir/include,
include the --with-gmp-build=pathname of gmp directive to configure mpfr
4.If these shorthand assumptions are not correct, you can use the explicit include and lib options directly.
solution : ./configure --with-gmp-build= location of new gmp.h
eg ./configure --with-gmp-build=/root/Desktop/gmp-5.0.1/obj-gmp
eg. to configure gcc :
../configure --prefix=/usr/local/avr --target=avr --enable-languages=c,c++ --disable-nls --disable-libssp --with-dwarf2 --with-mpfr=/usr/local/lib --with-gmp=/root/Desktop/gmp-5.0.1/obj-gmp
5. if you see the error : libmpfr.so.1: cannot open shared object file
[configure-target-libgcc] Error 1, then . . .
You need to set LD_LIBRARY_PATH : in the .bashrc file in root directory...
export PATH
export JAVA_HOME=/usr/local/jdk1.6.0_10/bin
export AVR_HOME=/usr/local/avr/bin
export MPFR_HOME=/usr/local/mpfr-2.4.2-obj/lib
LD_LIBRARY_PATH=/usr/local/mpfr-2.4.2-obj/lib
export LD_LIBRARY_PATH
PATH=$LD_LIBRARY_PATH:$MPFR_HOME:$PATH:$HOME/bin:$JAVA_HOME:$AVR_HOME
6. It is usually a good idea to configure and build binutils in a subdirectory so as not to pollute the source with the compiled files. This is recommended by the binutils developers.
$ mkdir obj-avr
$ cd obj-avr
The next step is to configure and build the tools. This is done by supplying arguments to the configure script that enable the AVR-specific options. ( to install binutils)
$ ../configure --prefix=$PREFIX --target=avr --disable-nls
7. don't forget to set theLD_LIBRARY_PATH and path in your login environment apart from root.
8. if error, get prepared to delete the files in directory obj-avr and ./configure again !!------( finally, after 6 nights of frustation and despair, I "make install". ) ^ ^
building avr-gcc from source..
see: Building and Installing the GNU Tool Chain
http://www.nongnu.org/avr-libc/user-manual/install_tools.html
before installing avr-gcc, I need to install GMP and MPFR first.
after installing gmp,
I then try to install MPFR 2.4.2 but I get a warning at the configure stage:
>
> checking if gmp.h version and libgmp version are the same... (5.0.1/4.2.2) no
> configure: WARNING: 'gmp.h' and 'libgmp' seems to have different versions or
> configure: WARNING: we cannot run a program linked with GMP (if you cannot
> configure: WARNING: see the version numbers above).
> configure: WARNING: However since we can't use 'libtool' inside the configure,
> configure: WARNING: we can't be sure. See 'config.log' for details.
--with-gmp-build=pathname
--with-gmp=pathname
--with-gmp-include=pathname
--with-gmp-lib=pathname
--with-mpfr=pathname
--with-mpfr-include=pathname
--with-mpfr-lib=pathname
2. If you do not have GMP (the GNU Multiple Precision library), the MPFR library and/or the MPC library installed in a standard location and you want to build GCC, you can explicitly specify the directory where they are installed (`--with-gmp=gmpinstalldir', `--with-mpfr=mpfrinstalldir').
3. The --with-gmp=gmpinstalldir option is shorthand for --with-gmp-lib=gmpinstalldir/lib and --with-gmp-include=gmpinstalldir/include.
Likewise the --with-mpfr=mpfrinstalldir option is shorthand for --with-mpfr-lib=mpfrinstalldir/lib and --with-mpfr-include=mpfrinstalldir/include,
include the --with-gmp-build=pathname of gmp directive to configure mpfr
4.If these shorthand assumptions are not correct, you can use the explicit include and lib options directly.
solution : ./configure --with-gmp-build= location of new gmp.h
eg ./configure --with-gmp-build=/root/Desktop/gmp-5.0.1/obj-gmp
eg. to configure gcc :
../configure --prefix=/usr/local/avr --target=avr --enable-languages=c,c++ --disable-nls --disable-libssp --with-dwarf2 --with-mpfr=/usr/local/lib --with-gmp=/root/Desktop/gmp-5.0.1/obj-gmp
5. if you see the error : libmpfr.so.1: cannot open shared object file
[configure-target-libgcc] Error 1, then . . .
You need to set LD_LIBRARY_PATH : in the .bashrc file in root directory...
export PATH
export JAVA_HOME=/usr/local/jdk1.6.0_10/bin
export AVR_HOME=/usr/local/avr/bin
export MPFR_HOME=/usr/local/mpfr-2.4.2-obj/lib
LD_LIBRARY_PATH=/usr/local/mpfr-2.4.2-obj/lib
export LD_LIBRARY_PATH
PATH=$LD_LIBRARY_PATH:$MPFR_HOME:$PATH:$HOME/bin:$JAVA_HOME:$AVR_HOME
6. It is usually a good idea to configure and build binutils in a subdirectory so as not to pollute the source with the compiled files. This is recommended by the binutils developers.
$ mkdir obj-avr
$ cd obj-avr
The next step is to configure and build the tools. This is done by supplying arguments to the configure script that enable the AVR-specific options. ( to install binutils)
$ ../configure --prefix=$PREFIX --target=avr --disable-nls
7. don't forget to set theLD_LIBRARY_PATH and path in your login environment apart from root.
8. if error, get prepared to delete the files in directory obj-avr and ./configure again !!------( finally, after 6 nights of frustation and despair, I "make install". ) ^ ^
Sonntag, 28. März 2010
Bought Arduino
Today, I have bought a shanzhai Arduino at Shum Shui Po at HK$220.
I have also completed reading Descartes' Meditation.
http://www.ladyada.net/learn/arduino/
Arduino Tutorial
http://www.chinagfw.org/
http://www.arduino.cc/playground/Main/ManualsAndCurriculum
I have also completed reading Descartes' Meditation.
http://www.ladyada.net/learn/arduino/
Arduino Tutorial
http://www.chinagfw.org/
http://www.arduino.cc/playground/Main/ManualsAndCurriculum
Samstag, 27. März 2010
The Arduino way : What is called tinkering ?
The Arduino way : What is called tinkering?
I am reading " Getting Started with Arduino ".
What is called tinkering ? to tinker your life . . .
quoted from : www.exploratorium/tinkering
1. Tinkering is what happens when you try something you don't quite know
how to do, guided by whim, imagination, and curiousity.
2. When you tinker, there are NO instructions--but there are also no failures,
no right or wrong WAYS of doing things. It is abou figuring out how things work and reworking them.
Contraptions, machines, wildly mismatched objects working in harmony--this is the stuff of tinkering.
3. Tinkering is, at its most basic, a process that marries play and inquiry.
see also : Lawrence Lessing 's " Free Culture" and "The future of Ideas"
誰綁架了文化創意 : 一場數位時代的財產戰爭! / Lawrence Lessig 著 ; 劉靜怡譯
台北市 : 早安財經文化有限公司, 2008.
Remix : Making art and commerce thrive in the hybrid economy
http://www.lessig.org/blog/
http://zh.globalvoicesonline.org/hant/2010/02/17/5653/
I am reading " Getting Started with Arduino ".
What is called tinkering ? to tinker your life . . .
quoted from : www.exploratorium/tinkering
1. Tinkering is what happens when you try something you don't quite know
how to do, guided by whim, imagination, and curiousity.
2. When you tinker, there are NO instructions--but there are also no failures,
no right or wrong WAYS of doing things. It is abou figuring out how things work and reworking them.
Contraptions, machines, wildly mismatched objects working in harmony--this is the stuff of tinkering.
3. Tinkering is, at its most basic, a process that marries play and inquiry.
see also : Lawrence Lessing 's " Free Culture" and "The future of Ideas"
誰綁架了文化創意 : 一場數位時代的財產戰爭! / Lawrence Lessig 著 ; 劉靜怡譯
台北市 : 早安財經文化有限公司, 2008.
Remix : Making art and commerce thrive in the hybrid economy
http://www.lessig.org/blog/
http://zh.globalvoicesonline.org/hant/2010/02/17/5653/
Arduino : What is Physical Computing"
Arduino : What is Physical Computing?
quoted from " Getting Started with Arduino ", p.3
What is physical computing?
1. Physical Computing uses electronics to prototype new materials for designers and artist.
2. it involves the design of interactive objects that can communicate with humans using sensors and actuators controlled by a behaviour implemented as software running inside a microcontroller ( a small computer on a single chip ).
See also : the book "Physical computing"
http://en.wikipedia.org/wiki/D%C3%A9tournement
http://zh.wikipedia.org/zh-hk/%E6%83%A1%E6%90%9E%E6%96%87%E5%8C%96
http://www.followlsd.com
quoted from " Getting Started with Arduino ", p.3
What is physical computing?
1. Physical Computing uses electronics to prototype new materials for designers and artist.
2. it involves the design of interactive objects that can communicate with humans using sensors and actuators controlled by a behaviour implemented as software running inside a microcontroller ( a small computer on a single chip ).
See also : the book "Physical computing"
http://en.wikipedia.org/wiki/D%C3%A9tournement
http://zh.wikipedia.org/zh-hk/%E6%83%A1%E6%90%9E%E6%96%87%E5%8C%96
http://www.followlsd.com
EE5412--Revision for Exam
EE5412 Telecommunications Network Revision for exam
Summary :
---------------
LAN
Meaning of Pure Aloha, slotted Aloha
Progressive improvement on protocol from aloha toà csma/cd,ca
Random access
Reason for collision
CSMA – non-persistence, 1 persistence, p- persistence, slot tome, jam sequence,
Truncated binary exponential backoff – delay mechanism and its effect on LAN performance at light load and heavy load
Minimum frame size
Ethernet protocol, handling of collision
-------------
TCP/IP
Motivation for inter-networking
Setting of time-out value – Karn’s algorithm
IP address – Type, Special IP address, Address mask, subnet
DNS, ARP
TCP, UDP – difference
Congestion control – window flow control, slow start, congestion avoidance
Adaptive retransmission , Fast retransmit, fast recovery
IPV6 – motivation for change, features, enhancement over IPV4
VPN, NAT
General concept of mobile IP
----------------
Telephony
Definition of Traffic units – Erlang, CCS
Definition of GOS, true and apparent offered load,
Carried traffic, Traffic lost
circuit capacity calculation using Table
Types of Traffic Measurement
Model – loss call clear, loss call return,
Group size – Trunk efficiency and GOS sensitivity to load variation
Principle of Trunk reservation – trunk or circuit size calculation and reason
--------------------
Wireless Network –
Principle of frequency reuse and cellular technique
Cell capacity calculation
CDMA – characteristic,
Factors affecting network capacity
Wireless Media access - combing technique in media access control
Bluetooth – objective, topology, protocol architecture
Core protocol and its main function
II. Assignment :
Topic suggestion - Difference between Bluetooth and ZigBee network in terms of objective,
topology, protocol architecture etc
Reference web site - www.iec.org/online/tutorials
賣友求辱可以休矣！ 23 March 2010
──致湯家驊議員的公開信
公民黨立法會議員湯家驊，於本(三)月十四日，在港台英文節目《給香港的信》中，再次促請中共政府，與他有份參與的「 終極普選大聯盟 」對話，否則香港的「 溫和 」民主派將失去支持，使更多年輕一輩加入激進的政治組織如社民連 (radical political parties like the League of Social Democrats )，令社會出現更多示威和抗爭，將不利香港長遠的繁榮穩定，更不符合北京的利益。
在評論湯議員的言論之前，容我們先引述時事評論家馬家輝教授的一段文字：「 所謂『激進』的英文是 radical，在思想層面上，這不算是個壞名詞，甚至還是好的……馬克思說過，radical 就是 back to basics，也就是『回頭探索現象的基本根源』，所以在解除戒嚴前的台灣，radical 被譯為激進，但到了解嚴後，已被普遍改譯為『基進』 」(明報，A08，2010年1月19日 )。
按此一說法，湯議員的思想，看來還處於一些人殘存的思想戒嚴階段。當香港人為中國呼喊民主、人權、和平、公義的口號，對中共而言，都是要求它是從根本 或本質上作出改變，都是很radical 的，因此無論我們要求的普選是 2012，還是 2020，只要提倡廢除功能組別，無論你湯議員是屬於「溫和」民主派還是「 公投派 」，在中共眼中，都是一般激進。
所以，當聽到湯議員在《信》所說，不理解北京為何連民進黨也肯與之溝通，卻對他這些從無公開反共的民主派人士不瞅不睬，我們不禁失笑：政治溝通必須以平等作基礎，惟湯議員不選擇以國民的尊嚴向中共抗爭，而是以臣民之態哀求極權主義者開恩賜予民主，除非湯議員能對劉曉波、譚作人等人的判監不聞不問，並認同當年中共果斷採取措施平息了「 一九八九年春夏之交的政治風波 」，北京或許會把你視作「 起義來歸 」，否則只有加入民建聯，才有望踏出與北京的「 溝通之路 」。
Summary :
---------------
LAN
Meaning of Pure Aloha, slotted Aloha
Progressive improvement on protocol from aloha toà csma/cd,ca
Random access
Reason for collision
CSMA – non-persistence, 1 persistence, p- persistence, slot tome, jam sequence,
Truncated binary exponential backoff – delay mechanism and its effect on LAN performance at light load and heavy load
Minimum frame size
Ethernet protocol, handling of collision
-------------
TCP/IP
Motivation for inter-networking
Setting of time-out value – Karn’s algorithm
IP address – Type, Special IP address, Address mask, subnet
DNS, ARP
TCP, UDP – difference
Congestion control – window flow control, slow start, congestion avoidance
Adaptive retransmission , Fast retransmit, fast recovery
IPV6 – motivation for change, features, enhancement over IPV4
VPN, NAT
General concept of mobile IP
----------------
Telephony
Definition of Traffic units – Erlang, CCS
Definition of GOS, true and apparent offered load,
Carried traffic, Traffic lost
circuit capacity calculation using Table
Types of Traffic Measurement
Model – loss call clear, loss call return,
Group size – Trunk efficiency and GOS sensitivity to load variation
Principle of Trunk reservation – trunk or circuit size calculation and reason
--------------------
Wireless Network –
Principle of frequency reuse and cellular technique
Cell capacity calculation
CDMA – characteristic,
Factors affecting network capacity
Wireless Media access - combing technique in media access control
Bluetooth – objective, topology, protocol architecture
Core protocol and its main function
II. Assignment :
Topic suggestion - Difference between Bluetooth and ZigBee network in terms of objective,
topology, protocol architecture etc
Reference web site - www.iec.org/online/tutorials
賣友求辱可以休矣！ 23 March 2010
──致湯家驊議員的公開信
公民黨立法會議員湯家驊，於本(三)月十四日，在港台英文節目《給香港的信》中，再次促請中共政府，與他有份參與的「 終極普選大聯盟 」對話，否則香港的「 溫和 」民主派將失去支持，使更多年輕一輩加入激進的政治組織如社民連 (radical political parties like the League of Social Democrats )，令社會出現更多示威和抗爭，將不利香港長遠的繁榮穩定，更不符合北京的利益。
在評論湯議員的言論之前，容我們先引述時事評論家馬家輝教授的一段文字：「 所謂『激進』的英文是 radical，在思想層面上，這不算是個壞名詞，甚至還是好的……馬克思說過，radical 就是 back to basics，也就是『回頭探索現象的基本根源』，所以在解除戒嚴前的台灣，radical 被譯為激進，但到了解嚴後，已被普遍改譯為『基進』 」(明報，A08，2010年1月19日 )。
按此一說法，湯議員的思想，看來還處於一些人殘存的思想戒嚴階段。當香港人為中國呼喊民主、人權、和平、公義的口號，對中共而言，都是要求它是從根本 或本質上作出改變，都是很radical 的，因此無論我們要求的普選是 2012，還是 2020，只要提倡廢除功能組別，無論你湯議員是屬於「溫和」民主派還是「 公投派 」，在中共眼中，都是一般激進。
所以，當聽到湯議員在《信》所說，不理解北京為何連民進黨也肯與之溝通，卻對他這些從無公開反共的民主派人士不瞅不睬，我們不禁失笑：政治溝通必須以平等作基礎，惟湯議員不選擇以國民的尊嚴向中共抗爭，而是以臣民之態哀求極權主義者開恩賜予民主，除非湯議員能對劉曉波、譚作人等人的判監不聞不問，並認同當年中共果斷採取措施平息了「 一九八九年春夏之交的政治風波 」，北京或許會把你視作「 起義來歸 」，否則只有加入民建聯，才有望踏出與北京的「 溝通之路 」。
Freitag, 26. März 2010
EE4209/EE5809 Digital Audio Technology--Audio compression
EE4209/EE5809 Digital Audio Technology
Audio compression
dictionary-based methods (eg. LZW compression) use a look-up table of fixed-length codes, where one codeword
may correspond to a string of symbols rather than to a single symbol in the file being compressed.
Entropy compression uses a statistical analysis of the frequency of symbols and achieves compression by encoding more frequently-occurring symbols with shorter code words, with one codeword
assigned to each symbol.
Shannon-Fano and Huffman encoding are examples of entropy compression.
Arithmetic encoding benefits from a similar statistical analysis, but encodes an entire file in a single code word rather than creating a separate code for each symbol.
Adaptive methods gain information about the nature of the file in the process of compressing it, and adapt the encoding to reflect what has been learned at each step.
LZW compression is by nature adaptive because the code table is created "on the fly".
Huffman encoding can be made adaptive if frequency counts are updated as compression proceeds rather than being collected beforehand; the method adapts to the nature of the data as the data are read.
differential encoding is a form of lossless compression that reduces file size by recording the difference between neighboring values rather than recording the values themselves.
The compression rte of a compression algorithm is the ratio of the original file size a to the size of the compressed file b, expressed as a:b.
一、
在「 普選聯 」成立之初，中央對於溝通一度「 吹暖風 」，尤其全國人大常委范徐麗泰，承諾在北京兩會期間傳話，一度令大眾認為民主派與中央的關係取得突破。可惜事與願違，「 普選聯 」的意願化為高牆前空洞的回音。
相信「 普選聯 」諸君也不難發現，經過與林瑞麟和一眾建制派的對話後，要特區政府在政改諮詢文件中作出讓步的可能性極低，但特區政府以致中央仍然營造「 有得傾 」的氣氛，用心路人皆見：拉一派，打一派，「 冷處理 」甚至抹黑「 五區公投運動 」。
我們擔心「 普選聯 」諸君，每天戴著「溫和民主派」這頂主流傳媒所編織的桂冠，自我感覺良好，於是不惜與同屬民主派陣營的公社聯盟保持距離。
因此，蔡耀昌、單仲偕二人不敢公開表示將於5月16日投票支持「 盡快落實真普選，廢除功能組別 」。
我們認為，「普選聯」在「五一六投票」的態度模糊，將會影響支持民主派的選民的投票意向，戕害「 五區公投運動 」。
二、
魯迅曾說：「 中國人的性情是總喜歡調和，折中的。譬如你說，這屋子太暗，須在這裏開一個窗，大家一定不允許的。但如果你主張拆掉屋頂，他們就會來調和，願意來開窗了。 」
政治評論家李怡借魯迅這個比喻，為「五區公投運動」鳴鑼開道：「支持民主的市民應認識清楚：
一，沒有五區公投，就不會有中央和建制派對『終極普選』派的忽然善意......若想中央和建制派真正向真普選和廢功組這兩個底線作出讓步，市民就要全力支持『五區公投』派。
市民可以接受 『 終極普選 』派與中央協商甚或妥協，但任何協商必須有實力作基礎。
『 終極普選 』派的談判實力，就來自五區公投的選民投票率。這是數量化的真正的理性主義。」(蘋果日報社評，2010 年2月24日。)
沒有激烈主張，連平和改革也不行。
如果認為五區公投是激烈主張的話，以手中選票力撐這主張正是實現平和改革的必要手段，在5月16日投下歷史性一票，是義不容辭！
Audio compression
dictionary-based methods (eg. LZW compression) use a look-up table of fixed-length codes, where one codeword
may correspond to a string of symbols rather than to a single symbol in the file being compressed.
Entropy compression uses a statistical analysis of the frequency of symbols and achieves compression by encoding more frequently-occurring symbols with shorter code words, with one codeword
assigned to each symbol.
Shannon-Fano and Huffman encoding are examples of entropy compression.
Arithmetic encoding benefits from a similar statistical analysis, but encodes an entire file in a single code word rather than creating a separate code for each symbol.
Adaptive methods gain information about the nature of the file in the process of compressing it, and adapt the encoding to reflect what has been learned at each step.
LZW compression is by nature adaptive because the code table is created "on the fly".
Huffman encoding can be made adaptive if frequency counts are updated as compression proceeds rather than being collected beforehand; the method adapts to the nature of the data as the data are read.
differential encoding is a form of lossless compression that reduces file size by recording the difference between neighboring values rather than recording the values themselves.
The compression rte of a compression algorithm is the ratio of the original file size a to the size of the compressed file b, expressed as a:b.
一、
在「 普選聯 」成立之初，中央對於溝通一度「 吹暖風 」，尤其全國人大常委范徐麗泰，承諾在北京兩會期間傳話，一度令大眾認為民主派與中央的關係取得突破。可惜事與願違，「 普選聯 」的意願化為高牆前空洞的回音。
相信「 普選聯 」諸君也不難發現，經過與林瑞麟和一眾建制派的對話後，要特區政府在政改諮詢文件中作出讓步的可能性極低，但特區政府以致中央仍然營造「 有得傾 」的氣氛，用心路人皆見：拉一派，打一派，「 冷處理 」甚至抹黑「 五區公投運動 」。
我們擔心「 普選聯 」諸君，每天戴著「溫和民主派」這頂主流傳媒所編織的桂冠，自我感覺良好，於是不惜與同屬民主派陣營的公社聯盟保持距離。
因此，蔡耀昌、單仲偕二人不敢公開表示將於5月16日投票支持「 盡快落實真普選，廢除功能組別 」。
我們認為，「普選聯」在「五一六投票」的態度模糊，將會影響支持民主派的選民的投票意向，戕害「 五區公投運動 」。
二、
魯迅曾說：「 中國人的性情是總喜歡調和，折中的。譬如你說，這屋子太暗，須在這裏開一個窗，大家一定不允許的。但如果你主張拆掉屋頂，他們就會來調和，願意來開窗了。 」
政治評論家李怡借魯迅這個比喻，為「五區公投運動」鳴鑼開道：「支持民主的市民應認識清楚：
一，沒有五區公投，就不會有中央和建制派對『終極普選』派的忽然善意......若想中央和建制派真正向真普選和廢功組這兩個底線作出讓步，市民就要全力支持『五區公投』派。
市民可以接受 『 終極普選 』派與中央協商甚或妥協，但任何協商必須有實力作基礎。
『 終極普選 』派的談判實力，就來自五區公投的選民投票率。這是數量化的真正的理性主義。」(蘋果日報社評，2010 年2月24日。)
沒有激烈主張，連平和改革也不行。
如果認為五區公投是激烈主張的話，以手中選票力撐這主張正是實現平和改革的必要手段，在5月16日投下歷史性一票，是義不容辭！
Donnerstag, 25. März 2010
EE4209/EE5809 Digital Audio Technology--The 3 meanings of bandwidth
EE4209/EE5809 Digital Audio Technology
The 3 meanings of bandwidth :
1. Bandwidth as maximum rate of change in digital data communication. How fast can the signal be changed.
Assume that a signal is sent with two possible signal levels and a bandwidth of b Hz. Then the data rate, d, in bits/s is
d = 2b.
Allowing more than two signal levels such that more than one bit can be communicated at a time is called multilevel coding.
2. Bandwidth of a signal in terms of frequency.
For a signal that can be represented as a periodic waveform , let fmax be the frequency of the highest-frequency component and let fmin be the frequency of the lowest-frequency component.
Then, the width of the signal ,w is :
w = fmax - fmin
3. Bandwidth of a communication channel in terms of frequency. The range of frequencies allocated to a band constitutes the bandwidth of a channel., also called the width of a channel, since it correlated with the width of a signal.
Modulation adds frequency components called sidebands to the original carrier signal, and these sidebands must lie within the designated channel. So, the bandwidth of a channel affects the amount of information that can be communicated.
但是，身為「 普選聯 」核心成員的蔡耀昌和 單仲偕( 民主黨副主席 )，不久前在一個網台的論壇中，竟然對 5月16日 會否去投票一事上支吾以對。
我們認為，這顯示「 普選聯 」正處於進退維谷之境地：「 五一六投票 」等於支持「 五區公投 」，妨礙溝通大業。
SRW LIVE 勇者王誕生
http://www.youtube.com/watch?v=7Hou0zeofVs&feature=related
《青台友香聞》訪問黃毓民 Part 6/8
http://www.youtube.com/watch?v=wlI1_ZMqK6U&feature=related
The 3 meanings of bandwidth :
1. Bandwidth as maximum rate of change in digital data communication. How fast can the signal be changed.
Assume that a signal is sent with two possible signal levels and a bandwidth of b Hz. Then the data rate, d, in bits/s is
d = 2b.
Allowing more than two signal levels such that more than one bit can be communicated at a time is called multilevel coding.
2. Bandwidth of a signal in terms of frequency.
For a signal that can be represented as a periodic waveform , let fmax be the frequency of the highest-frequency component and let fmin be the frequency of the lowest-frequency component.
Then, the width of the signal ,w is :
w = fmax - fmin
3. Bandwidth of a communication channel in terms of frequency. The range of frequencies allocated to a band constitutes the bandwidth of a channel., also called the width of a channel, since it correlated with the width of a signal.
Modulation adds frequency components called sidebands to the original carrier signal, and these sidebands must lie within the designated channel. So, the bandwidth of a channel affects the amount of information that can be communicated.
但是，身為「 普選聯 」核心成員的蔡耀昌和 單仲偕( 民主黨副主席 )，不久前在一個網台的論壇中，竟然對 5月16日 會否去投票一事上支吾以對。
我們認為，這顯示「 普選聯 」正處於進退維谷之境地：「 五一六投票 」等於支持「 五區公投 」，妨礙溝通大業。
SRW LIVE 勇者王誕生
http://www.youtube.com/watch?v=7Hou0zeofVs&feature=related
《青台友香聞》訪問黃毓民 Part 6/8
http://www.youtube.com/watch?v=wlI1_ZMqK6U&feature=related
EE4209/EE5809 Digital Audio Technology baseband communication
EE4209/EE5809 Digital Audio Technology
The name bandpass communication arises from the fact that in this method
of data communication, the carrier signal lies in the center of frequency band, called a channelthat is allocated to them.
Digital data can be transmitted by means of a baseband signal or a bandpass (ie, modulated) signal.
The baseband signal uses discrete pulses representing 0s and 1s.
The modulated signal uses a carrier frequency and an encoding of data based on periodically altering the frequency,
amplitude, or phases of the signal.
Yugioh GX Final Episode SUBBED (part 1)
http://www.youtube.com/watch?v=GZKInvFOr-k&feature=related
沒有激烈的主張，連平和改革也不行──致「 終極普選大聯盟 」公開信
參與「 終極普選大聯盟 」的袞袞諸公，都是我們廿多年來一同為香港民主並肩作戰的盟友，因此我們深信「普選聯」諸君，是真誠地以為透過 與中央及建制派對話以求實現普選。
The name bandpass communication arises from the fact that in this method
of data communication, the carrier signal lies in the center of frequency band, called a channelthat is allocated to them.
Digital data can be transmitted by means of a baseband signal or a bandpass (ie, modulated) signal.
The baseband signal uses discrete pulses representing 0s and 1s.
The modulated signal uses a carrier frequency and an encoding of data based on periodically altering the frequency,
amplitude, or phases of the signal.
Yugioh GX Final Episode SUBBED (part 1)
http://www.youtube.com/watch?v=GZKInvFOr-k&feature=related
沒有激烈的主張，連平和改革也不行──致「 終極普選大聯盟 」公開信
參與「 終極普選大聯盟 」的袞袞諸公，都是我們廿多年來一同為香港民主並肩作戰的盟友，因此我們深信「普選聯」諸君，是真誠地以為透過 與中央及建制派對話以求實現普選。
Dienstag, 23. März 2010
EE4209/EE5809 Quantization
EE4209/EE5809 Quantization
1. samples must be taken at discrete points in time or space, but how each sample is represented in a computer.
2. Let n be the number of bits used to quantize a digital sample. Then, the maximum number of different values that can be represented, m, is m = 2**n
3. For digital audio,each sample represents the amplitude of sound wave at a discrete point in time. Common sample sizes are 8 or 16 bits.
Stereo CD-quality digital audio uses 16 bits per sample in each of the 2 stereo channels, for a total of 32 bits per sample.
4. Sample size affect how precisely the value of a sample can be represented.
5. In digital sound, sample size affects how much you have to round off the amplitude of the wave when it is sampled at various points in time.
6. A sample must be rounded to the closet discrete level. The difference between its actual value and its rounded value is the quantization error.
7. The amount of error implicit in a chosen bit depth can be measured in terms of the signal-to-noise ratio (SNR )
1. samples must be taken at discrete points in time or space, but how each sample is represented in a computer.
2. Let n be the number of bits used to quantize a digital sample. Then, the maximum number of different values that can be represented, m, is m = 2**n
3. For digital audio,each sample represents the amplitude of sound wave at a discrete point in time. Common sample sizes are 8 or 16 bits.
Stereo CD-quality digital audio uses 16 bits per sample in each of the 2 stereo channels, for a total of 32 bits per sample.
4. Sample size affect how precisely the value of a sample can be represented.
5. In digital sound, sample size affects how much you have to round off the amplitude of the wave when it is sampled at various points in time.
6. A sample must be rounded to the closet discrete level. The difference between its actual value and its rounded value is the quantization error.
7. The amount of error implicit in a chosen bit depth can be measured in terms of the signal-to-noise ratio (SNR )
EE4209/EE5809 Sampling and Aliasing
EE4209/EE5809 Sampling and Aliasing
1. The sample areas are designated by rectangles which we call sample blocks.
2. under-sampling : your sampling rate did not keep up with the rate of change of the pattern in the image.
3. With regard to sampling rate, Hz means samples per second, with regard to a sound wave, Hz means cycles per second.)
4. Nyquist theorem, which specifies the sampling rate needed for a given spatial or temporal frequency.
5. Nyquist theorem states that to guarantee that no aliasing will occur, you must use a sampling rate that is greater than TWICE the frequency of the signal being sampled.
6. Let f be the frequency of a sine wave. Let r be the minimum sampling rate that can be used in the digitization process such that the resulting digitized wave is not aliased.
Then r = 2f, r is called the Nyquist frequency.
1. The sample areas are designated by rectangles which we call sample blocks.
2. under-sampling : your sampling rate did not keep up with the rate of change of the pattern in the image.
3. With regard to sampling rate, Hz means samples per second, with regard to a sound wave, Hz means cycles per second.)
4. Nyquist theorem, which specifies the sampling rate needed for a given spatial or temporal frequency.
5. Nyquist theorem states that to guarantee that no aliasing will occur, you must use a sampling rate that is greater than TWICE the frequency of the signal being sampled.
6. Let f be the frequency of a sine wave. Let r be the minimum sampling rate that can be used in the digitization process such that the resulting digitized wave is not aliased.
Then r = 2f, r is called the Nyquist frequency.
EE4209/EE5809 Sampling and Aliasing
EE4209/EE5809 Sampling and Aliasing
http://www.youtube.com/watch?v=7TAOzPCYnw8&feature=player_embedded
陳志雲記者會上風采依然：真的假不了，假的真不了2010.03.18
1. The sample areas are designated by rectangles which we call sample blocks.
2. under-sampling : your sampling rate did not keep up with the rate of change of the pattern in the image.
3. With regard to sampling rate, Hz means samples per second, with regard to a sound wave, Hz means cycles per second.)
4. Nyquist theorem, which specifies the sampling rate needed for a given spatial or temporal frequency.
5. Nyquist theorem states that to guarantee that no aliasing will occur, you must use a sampling rate that is greater than TWICE the frequency of the signal being sampled.
6. Let f be the frequency of a sine wave. Let r be the minimum sampling rate that can be used in the digitization process such that the resulting digitized wave is not aliased.
Then r= 2f, r is called the Nyquist frequency.
Terrifying Girls' High School
http://www.youtube.com/watch?v=8m0ZNsvdGGE&feature=related
full movie ( a detourned version):
The Girls of Kamare (1974)
http://www.ubu.com/film/vienet_kamare.html
http://www.youtube.com/watch?v=7TAOzPCYnw8&feature=player_embedded
陳志雲記者會上風采依然：真的假不了，假的真不了2010.03.18
1. The sample areas are designated by rectangles which we call sample blocks.
2. under-sampling : your sampling rate did not keep up with the rate of change of the pattern in the image.
3. With regard to sampling rate, Hz means samples per second, with regard to a sound wave, Hz means cycles per second.)
4. Nyquist theorem, which specifies the sampling rate needed for a given spatial or temporal frequency.
5. Nyquist theorem states that to guarantee that no aliasing will occur, you must use a sampling rate that is greater than TWICE the frequency of the signal being sampled.
6. Let f be the frequency of a sine wave. Let r be the minimum sampling rate that can be used in the digitization process such that the resulting digitized wave is not aliased.
Then r= 2f, r is called the Nyquist frequency.
Terrifying Girls' High School
http://www.youtube.com/watch?v=8m0ZNsvdGGE&feature=related
full movie ( a detourned version):
The Girls of Kamare (1974)
http://www.ubu.com/film/vienet_kamare.html
EE4209/EE5809 Sampling and quantization
EE4209/EE5809
Sampling and quantization
1. sampling chooses discrete points at which to measure a continuous phenomenon
(which we will also call a signal).
In the case of sound, the sample points are evenly separated in time.
The number of samples taken per unit time or unit space (for image) is called the sampling rate or resolution.
2. quantization, requires that each sample be represented in a fixed number of bits, called sample size or bit depth.
Sampling and quantization
1. sampling chooses discrete points at which to measure a continuous phenomenon
(which we will also call a signal).
In the case of sound, the sample points are evenly separated in time.
The number of samples taken per unit time or unit space (for image) is called the sampling rate or resolution.
2. quantization, requires that each sample be represented in a fixed number of bits, called sample size or bit depth.
Montag, 22. März 2010
EE4209/EE5809 Digital Audio Technology
EE4209/EE5809 Digital Audio Technology
Notes : quoted from "The Science of Digital Media"
chapter 1
1. sound is a one-dimensional function -- that is, a function with one variable as input. if we think of sound as a continuous phenomenon, then we can model it as a continuous
function y= f (x) where x is time and y is the air pressure amplitude.
2. Let r be the size of an angle measured in radians, and let d be this size measured in degrees. then,
r/d = PI/180
we say " a simple sine wave " when we wish to emphasize that it is a single function rather than of two or more.
3.sound is " mechanical wave " , which means that it results from the motion of particles through a transmission wave,
it has to have something to move through, sound cannot be transmitted through a vacuum.
The movement associated with a sound wave is initiated by a vibration.
4. The motion of the air molecules is back and forth from left to right, the same direction in which the wave in which the motion of individual particles is parallel to the direction in which energy is being transported.
Sound is a longitudinal mechanical wave.
5. A wave is said to be periodic if it repeats a pattern over time. the pattern that is repeated constitutes one cycle of the wave.
A " wavelength " is the LENGTH ( in distance ) of ONE complete cycle.
The " frequency " of a wave is the NUMBER of times a cycle repeats per unit time, which in the case of sound corresponds to the rate at which the air molecules are vibrating.
The frequency of a sound wave is measured n cycles per sound or Hertz.
The PERIOD of a wave is the amount is the amount of time it takes for ONE cycle to complete. Period and frequency are reciprocals of each other.
Let T be the period and f be the frequency of a sinusoidal wave. Then, T = 1/f and f = 1/T.
The height of a wave is called its amplitude.
6. To create a sine function representing a sound wave frequency f HZ, you must convert f to " angular frequency " first.
Let f be the frequency of a sine wave measured in Hz. Let w be the equivalent angular frequency measured in radians/s.
then w = 2 PI *f
7. the amplitude of a wave corresponds to how loud the sound is. The frequency of a wave corresponds to the pitch of the sound.
陶君行反駁湯家驊對五區公投不斷進行言論破壞.
五區公投--陶君行惡鬥湯家驊-pt.1 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.2 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.3 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.4 www.youtube.com
吳靄儀﹕*立法會議員的辭職與補選* hk.news.yahoo.com
余若薇﹕*獻給反對公投的朋友* hk.news.yahoo.com
余若薇﹕*公投如何挑戰法律？* hk.news.yahoo.com
社會民主連線的《五區總辭，全民公決，爭取2012雙普選》政治說帖下載:...
Notes : quoted from "The Science of Digital Media"
chapter 1
1. sound is a one-dimensional function -- that is, a function with one variable as input. if we think of sound as a continuous phenomenon, then we can model it as a continuous
function y= f (x) where x is time and y is the air pressure amplitude.
2. Let r be the size of an angle measured in radians, and let d be this size measured in degrees. then,
r/d = PI/180
we say " a simple sine wave " when we wish to emphasize that it is a single function rather than of two or more.
3.sound is " mechanical wave " , which means that it results from the motion of particles through a transmission wave,
it has to have something to move through, sound cannot be transmitted through a vacuum.
The movement associated with a sound wave is initiated by a vibration.
4. The motion of the air molecules is back and forth from left to right, the same direction in which the wave in which the motion of individual particles is parallel to the direction in which energy is being transported.
Sound is a longitudinal mechanical wave.
5. A wave is said to be periodic if it repeats a pattern over time. the pattern that is repeated constitutes one cycle of the wave.
A " wavelength " is the LENGTH ( in distance ) of ONE complete cycle.
The " frequency " of a wave is the NUMBER of times a cycle repeats per unit time, which in the case of sound corresponds to the rate at which the air molecules are vibrating.
The frequency of a sound wave is measured n cycles per sound or Hertz.
The PERIOD of a wave is the amount is the amount of time it takes for ONE cycle to complete. Period and frequency are reciprocals of each other.
Let T be the period and f be the frequency of a sinusoidal wave. Then, T = 1/f and f = 1/T.
The height of a wave is called its amplitude.
6. To create a sine function representing a sound wave frequency f HZ, you must convert f to " angular frequency " first.
Let f be the frequency of a sine wave measured in Hz. Let w be the equivalent angular frequency measured in radians/s.
then w = 2 PI *f
7. the amplitude of a wave corresponds to how loud the sound is. The frequency of a wave corresponds to the pitch of the sound.
陶君行反駁湯家驊對五區公投不斷進行言論破壞.
五區公投--陶君行惡鬥湯家驊-pt.1 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.2 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.3 www.youtube.com
五區公投--陶君行惡鬥湯家驊-pt.4 www.youtube.com
吳靄儀﹕*立法會議員的辭職與補選* hk.news.yahoo.com
余若薇﹕*獻給反對公投的朋友* hk.news.yahoo.com
余若薇﹕*公投如何挑戰法律？* hk.news.yahoo.com
社會民主連線的《五區總辭，全民公決，爭取2012雙普選》政治說帖下載:...
Sonntag, 21. März 2010
EE5412 SRW LIVE 勇者王誕生
SRW LIVE 勇者王誕生
http://www.youtube.com/watch?v=7Hou0zeofVs&feature=related
勇者王最終回
http://www.youtube.com/watch?v=iLq1-AW5C7g&feature=related
勇者王ガオガイガー 第49話 「いつか星の海で」part3
http://www.youtube.com/watch?v=WDAVOF9XhLk&feature=related
Terrifying Girls' High School
http://www.youtube.com/watch?v=8m0ZNsvdGGE&feature=related
full movie ( a detourned version):
The Girls of Kamare (1974)
http://www.ubu.com/film/vienet_kamare.html
http://www.youtube.com/watch?v=7Hou0zeofVs&feature=related
勇者王最終回
http://www.youtube.com/watch?v=iLq1-AW5C7g&feature=related
勇者王ガオガイガー 第49話 「いつか星の海で」part3
http://www.youtube.com/watch?v=WDAVOF9XhLk&feature=related
Terrifying Girls' High School
http://www.youtube.com/watch?v=8m0ZNsvdGGE&feature=related
full movie ( a detourned version):
The Girls of Kamare (1974)
http://www.ubu.com/film/vienet_kamare.html
Donnerstag, 18. März 2010
EE5412 Descartes 笛卡兒
Descartes 笛卡兒
陳志雲被補後首次記者會
http://www.youtube.com/watch?v=33onDyC27vY
1. 除了清楚明白的觀念外，絕不接受其他任何東西；
2. 必須將每個問題, 分成若干個簡單的部分來處理；
3. 思想必須從簡單到複雜；
4. 我們應該時常進行徹底的檢查，確保沒有遺漏任何東西。
1. Studies in the Cartesian philosophy (1902) by Norman Kemp Smith
http://www.archive.org/details/studiesincartes00smitgoog
2. Descartes, his life and times (1905) by Haldane, Elizabeth Sanderson, 1862-1937
http://www.archive.org/details/cu31924029049950
3. The Philosophical Works Of Descartes Volume II (1934)
http://www.archive.org/details/philosophicalwor005524mbp
4. Descartes Philosophical Writings (1958) tr. by Norman Kemp Smith
http://www.archive.org/details/descartesphiloso010838mbp
5.The Method, Meditations and Philosophy of Descartes (1901)
Veitch, John, 1829-1894
http://www.archive.org/details/themethodmeditat00descuoft
6. 理性主義 導論
http://www.hfu.edu.tw/~huangkm/ration/rationalism.htm
陳志雲被補後首次記者會
http://www.youtube.com/watch?v=33onDyC27vY
1. 除了清楚明白的觀念外，絕不接受其他任何東西；
2. 必須將每個問題, 分成若干個簡單的部分來處理；
3. 思想必須從簡單到複雜；
4. 我們應該時常進行徹底的檢查，確保沒有遺漏任何東西。
1. Studies in the Cartesian philosophy (1902) by Norman Kemp Smith
http://www.archive.org/details/studiesincartes00smitgoog
2. Descartes, his life and times (1905) by Haldane, Elizabeth Sanderson, 1862-1937
http://www.archive.org/details/cu31924029049950
3. The Philosophical Works Of Descartes Volume II (1934)
http://www.archive.org/details/philosophicalwor005524mbp
4. Descartes Philosophical Writings (1958) tr. by Norman Kemp Smith
http://www.archive.org/details/descartesphiloso010838mbp
5.The Method, Meditations and Philosophy of Descartes (1901)
Veitch, John, 1829-1894
http://www.archive.org/details/themethodmeditat00descuoft
6. 理性主義 導論
http://www.hfu.edu.tw/~huangkm/ration/rationalism.htm
Sonntag, 7. März 2010
EE5412 TCPip QA1
EE5412 [TcpIpQA1.doc] [Garcia]
27. What is the difference between a physical address, a network address, and a domain name?
Solution:
The physical address is the unique hardware address that identifies an interface of a machine on a physical network such as a LAN. Physical addresses are used in the data link layer.
A network address is a machine's logical address on a network. The network address is used in the network layer. The network address used on the Internet is the IP address.
Domain names are used as an aid to identify hosts and networks in the Internet, since names are easier to remember than numbers. The DNS system is used to translate between domain names and IP addresses. The domain name for the network address 128.100.132.30 is toronto.edu.
------------------------------------
28. The Domain Name System has a hierarchical structure, for example, comm.toronto.edu. Explain how a DNS query might proceed if the local name server does not have the IP address for a given host.
Solution:
The domain name comm.toronto.edu has three levels of domains, comm.toronto.edu, toronto.edu, and edu. We can envision that name servers are arranged in a tree topology with a "root" server at the top; "edu" and other servers, such as "com", "org" "gov", "ca", at the second level; and below each second-level server, third level servers such as toronto.edu; and so on.
To find an IP address, in principle the host needs to contact the root server, that, if necessary, contacts an appropriate server below it, for example, edu. This second-level server can then, if necessary, contact a server in the level below it, for example, toronto.edu.
This process continues until the name is resolved.
This approach, however, can place large loads on the root server. In practice most queries involve local names, and so queries are first directed to a local name server. If the local name server cannot resolve a name, then the query is directed to another server in the domain system, for example, the parent server in the above tree hierarchy.
-------------------------------------------
31. Suppose a computer is moved from one department to another.
Does the physical address need to change?
Does the IP address need to change?
Does it make a difference if the computer is a laptop?
Solution:
The physical address does not change. It is globally unique to the computer's NIC card.
The IP address needs to be changed to reflect the new sub-network id and host id.
The situation is the same for laptops.
---------------------------------------
38. Explain why it is useful for application layer programs to have a "well-known" TCP port number?
Solution:
The TCP layer entity uses the port number to determine which application program the packets belong to. In the TCP connection setup process it is very convenient to have a unique well-known port number, otherwise some protocol or procedure would be required to find the desired number.
-----------------------------
41. Which of the TCP/IP transport protocol (UDP or TCP) would you select for the following applications: packet voice, file transfer, remote login, multicast communication (i.e., multiple destinations).
Solution:
Packet Voice - This example involves the transfer of a stream of information in real time across the network. At first, it may appear that TCP is suitable because of its connection orientation.
However the acknowledgment and retransmission mechanisms in TCP introduce too much delay in the transfer of packets, and so UDP is the preferred approach to transferring a real-time voice stream across the network.
File Transfer - In general, file transfer requires reliable transfer and so TCP is preferred.
Remote Login - TCP is preferable because it provides for the reliable transfer of the stream of keystrokes that forms the basis for a remote login application.
Multicast Communication - In multicast services, a source sends information to a subset of
destinations attached to the network. It is easy to imagine multicast applications that require reliable transfer of a stream of information to a set of destinations, and multicast applications that require only best effort transfer of individual messages.
Therefore neither TCP nor UDP is preferred. A more pertinent point is that providing reliable multicast stream transfer service is quite difficult to implement, and TCP is not designed for this.
--------------------------------------
46. Suppose regularly spaced PING packets are sent to a remote host. What can you conclude from the following results?
Solutions follow questions:
a. No replies arrive back.
Possibilities are: the remote host is down; the remote host or the network is extremely congested; the remote host is set up not to reply.
b. Some replies are lost.
Some packets are discarded due to congestion at the remote-host listening-buffer or congestion at the network routers.
c. All replies arrive but with variable delays.
The packets traverse network routes that have different path length or traffic load.
d. What kind of statistics would be useful to calculate for the round-trip delays?
Time(reply packet arrival) - Time( the echo packet is sent).
------------------------------------
27. What is the difference between a physical address, a network address, and a domain name?
Solution:
The physical address is the unique hardware address that identifies an interface of a machine on a physical network such as a LAN. Physical addresses are used in the data link layer.
A network address is a machine's logical address on a network. The network address is used in the network layer. The network address used on the Internet is the IP address.
Domain names are used as an aid to identify hosts and networks in the Internet, since names are easier to remember than numbers. The DNS system is used to translate between domain names and IP addresses. The domain name for the network address 128.100.132.30 is toronto.edu.
------------------------------------
28. The Domain Name System has a hierarchical structure, for example, comm.toronto.edu. Explain how a DNS query might proceed if the local name server does not have the IP address for a given host.
Solution:
The domain name comm.toronto.edu has three levels of domains, comm.toronto.edu, toronto.edu, and edu. We can envision that name servers are arranged in a tree topology with a "root" server at the top; "edu" and other servers, such as "com", "org" "gov", "ca", at the second level; and below each second-level server, third level servers such as toronto.edu; and so on.
To find an IP address, in principle the host needs to contact the root server, that, if necessary, contacts an appropriate server below it, for example, edu. This second-level server can then, if necessary, contact a server in the level below it, for example, toronto.edu.
This process continues until the name is resolved.
This approach, however, can place large loads on the root server. In practice most queries involve local names, and so queries are first directed to a local name server. If the local name server cannot resolve a name, then the query is directed to another server in the domain system, for example, the parent server in the above tree hierarchy.
-------------------------------------------
31. Suppose a computer is moved from one department to another.
Does the physical address need to change?
Does the IP address need to change?
Does it make a difference if the computer is a laptop?
Solution:
The physical address does not change. It is globally unique to the computer's NIC card.
The IP address needs to be changed to reflect the new sub-network id and host id.
The situation is the same for laptops.
---------------------------------------
38. Explain why it is useful for application layer programs to have a "well-known" TCP port number?
Solution:
The TCP layer entity uses the port number to determine which application program the packets belong to. In the TCP connection setup process it is very convenient to have a unique well-known port number, otherwise some protocol or procedure would be required to find the desired number.
-----------------------------
41. Which of the TCP/IP transport protocol (UDP or TCP) would you select for the following applications: packet voice, file transfer, remote login, multicast communication (i.e., multiple destinations).
Solution:
Packet Voice - This example involves the transfer of a stream of information in real time across the network. At first, it may appear that TCP is suitable because of its connection orientation.
However the acknowledgment and retransmission mechanisms in TCP introduce too much delay in the transfer of packets, and so UDP is the preferred approach to transferring a real-time voice stream across the network.
File Transfer - In general, file transfer requires reliable transfer and so TCP is preferred.
Remote Login - TCP is preferable because it provides for the reliable transfer of the stream of keystrokes that forms the basis for a remote login application.
Multicast Communication - In multicast services, a source sends information to a subset of
destinations attached to the network. It is easy to imagine multicast applications that require reliable transfer of a stream of information to a set of destinations, and multicast applications that require only best effort transfer of individual messages.
Therefore neither TCP nor UDP is preferred. A more pertinent point is that providing reliable multicast stream transfer service is quite difficult to implement, and TCP is not designed for this.
--------------------------------------
46. Suppose regularly spaced PING packets are sent to a remote host. What can you conclude from the following results?
Solutions follow questions:
a. No replies arrive back.
Possibilities are: the remote host is down; the remote host or the network is extremely congested; the remote host is set up not to reply.
b. Some replies are lost.
Some packets are discarded due to congestion at the remote-host listening-buffer or congestion at the network routers.
c. All replies arrive but with variable delays.
The packets traverse network routes that have different path length or traffic load.
d. What kind of statistics would be useful to calculate for the round-trip delays?
Time(reply packet arrival) - Time( the echo packet is sent).
------------------------------------
EE5412 Telecommunications Network NAT
EE5412 NAT, Network Address Translation
Network address translation (NAT) allows a site to use a set of private addresses for internal communication and a set of global Internet addresses for communication with external site.
The site must have only one single connection to the global Internet through a router that runs NAT software.
The private network uses private addresses. The router that connects the network to the global address uses one private address and one global address. The private network is transparent to the rest of the Internet. The rest of the internet sees only the NAT router with its own global IP.
Translation table - The NAT router keeps a translation table co-relating the private address with the external Internet destination address.
All out going packets go through the NAT router. The source address in the outgoing packets will be replaced with the global NAT address.
All incoming packets also pass through the NAT router. The destination address of the incoming packets will be replaced with the appropriate private address. The private host address is identified by the external host address on the translation table.
With this technique, communication must always be initiated by the private network so that the NAT table can be updated before communication with outside internet.
A private network can not run a server program for clients outside of its network if it is using NAT technology.
Pool of IP address
Allow multiple private network hosts to access the same external host at the same time. Private host address can be identified by the external host address and the NAT router IP address.
IP Address and Port Address
To allow many-to-many relationship between private-network host and external server programs, private port address can also be used.
Network address translation (NAT) allows a site to use a set of private addresses for internal communication and a set of global Internet addresses for communication with external site.
The site must have only one single connection to the global Internet through a router that runs NAT software.
The private network uses private addresses. The router that connects the network to the global address uses one private address and one global address. The private network is transparent to the rest of the Internet. The rest of the internet sees only the NAT router with its own global IP.
Translation table - The NAT router keeps a translation table co-relating the private address with the external Internet destination address.
All out going packets go through the NAT router. The source address in the outgoing packets will be replaced with the global NAT address.
All incoming packets also pass through the NAT router. The destination address of the incoming packets will be replaced with the appropriate private address. The private host address is identified by the external host address on the translation table.
With this technique, communication must always be initiated by the private network so that the NAT table can be updated before communication with outside internet.
A private network can not run a server program for clients outside of its network if it is using NAT technology.
Pool of IP address
Allow multiple private network hosts to access the same external host at the same time. Private host address can be identified by the external host address and the NAT router IP address.
IP Address and Port Address
To allow many-to-many relationship between private-network host and external server programs, private port address can also be used.
EE5412 subnet example
EE5412 Telecommunications Network
A company has three offices: Central, East, and West.
The Central office is connected to the East and West offices via private, point-to-point WAN lines. The company is granted a block of 64 addresses with the beginning address 70.12.100.128/26.
The management has decided to allocate 32 addresses for the Central office and divides the rest of addresses between the two offices.
Suggest a network configuration. Provide your answer with a network diagram.
On your diagram, indicate the Subnet address, subnet mask and the IP address on each router link.
Ans:
Address block 70.12.100.128/26 …[64 IP address]
sub-divided into 70.12.100.128/27 --- [32 IP address] [27 bits subnet mask]
70.12.100.160/28 --- [16 IP address]
70.12.100.176/28 --- [16 IP address]
A company has three offices: Central, East, and West.
The Central office is connected to the East and West offices via private, point-to-point WAN lines. The company is granted a block of 64 addresses with the beginning address 70.12.100.128/26.
The management has decided to allocate 32 addresses for the Central office and divides the rest of addresses between the two offices.
Suggest a network configuration. Provide your answer with a network diagram.
On your diagram, indicate the Subnet address, subnet mask and the IP address on each router link.
Ans:
Address block 70.12.100.128/26 …[64 IP address]
sub-divided into 70.12.100.128/27 --- [32 IP address] [27 bits subnet mask]
70.12.100.160/28 --- [16 IP address]
70.12.100.176/28 --- [16 IP address]
EE5412 IP_Subnet0.doc
EE5412 [IP_Subnet0.doc]
Subnetting
Assume
1. class B network of 128.6.0.0 has been assigned
2. two LANs or networks located in two different physical locations
3. main router has one external and two local interfaces, each local interface connects to a local network
‘a’ assign IP in random to host, routing table ‘b’ has to be updated.
‘b’ create two subnets with starting address 128.6.1 and 128.6.5
Motivation for Subnetting
Grouping address assignment by using geographic locations makes the routing table much simpler.
Effect of Simplified routing table –
Routers share routing table with others to let each other know what is connected.
Larger table places more demand [ie.Traffic] on the network as it is periodically transmitted.
Looking up entries is also time-consuming with larger table.
Subnet creates traffic isolation and security between work groups.
Example
Assume 5 bits host in the following IP
IP address 1101, 0110, 1001, 0010, 1110, 0111, 0100, 1101 214.146.231.77
Subnet Mask 1111, 1111, 1111, 1111, 1111, 1111, 1110, 0000 255.255.255.224
Subnet address 1101, 0110, 1001, 0010, 1110, 0111, 0100, 0000 214.146.231.64
Host number 0, 1101 13
Broadcast address 1101, 0110, 1001, 0010, 1110, 0111, 0101, 1111 214.146.231.95
IP address and its mask 214.146.231.77/27 27 is the mask in subnet
Loss of IP address
Each subnet occupy 1 IP address space for denoting subnet address [ie. All 0] and
1 IP address space for subnet broadcasting address [ie. All 1]
In the above example : IP address 214.146.231.64 and
214.146.231.95 is not available for host address allocation.
=> more subnet => more unavailable IP address for host
Example
An organization with class C network, 200.200.200.0 network assigned.
At home office , estimated max of 50 interface
Three branch office each with 20 interface
Lease line connects at each branch to the router at home office. Each line need IP address with its own subnet.
With class C, the last 8 bit in IP address is available for subnet. We can have 6 subnet and each subnet has 30 interface
000x,xxxx cannot use [200.200.200.0]
001x,xxxx branch 1 1 subnet address, 1 broadcast address, 2 link address , 20 host address
010x,xxxx branch 2
011x,xxxx branch 3
100x,xxxx home office
101x,xxxx home office
110x,xxxx not used
111x,xxxx cannot use [200.200.200.255]
Subnet mask 255.255.255.0
Routing table 200.200.200.32 branch 1 link
200.200.200.64 Branch 2 link
200.200.200.96 branch 3 link
200.200.200.128 home office link
200.200.200.160 home office link
200.200.200. 192 default link
Subnetting
Assume
1. class B network of 128.6.0.0 has been assigned
2. two LANs or networks located in two different physical locations
3. main router has one external and two local interfaces, each local interface connects to a local network
‘a’ assign IP in random to host, routing table ‘b’ has to be updated.
‘b’ create two subnets with starting address 128.6.1 and 128.6.5
Motivation for Subnetting
Grouping address assignment by using geographic locations makes the routing table much simpler.
Effect of Simplified routing table –
Routers share routing table with others to let each other know what is connected.
Larger table places more demand [ie.Traffic] on the network as it is periodically transmitted.
Looking up entries is also time-consuming with larger table.
Subnet creates traffic isolation and security between work groups.
Example
Assume 5 bits host in the following IP
IP address 1101, 0110, 1001, 0010, 1110, 0111, 0100, 1101 214.146.231.77
Subnet Mask 1111, 1111, 1111, 1111, 1111, 1111, 1110, 0000 255.255.255.224
Subnet address 1101, 0110, 1001, 0010, 1110, 0111, 0100, 0000 214.146.231.64
Host number 0, 1101 13
Broadcast address 1101, 0110, 1001, 0010, 1110, 0111, 0101, 1111 214.146.231.95
IP address and its mask 214.146.231.77/27 27 is the mask in subnet
Loss of IP address
Each subnet occupy 1 IP address space for denoting subnet address [ie. All 0] and
1 IP address space for subnet broadcasting address [ie. All 1]
In the above example : IP address 214.146.231.64 and
214.146.231.95 is not available for host address allocation.
=> more subnet => more unavailable IP address for host
Example
An organization with class C network, 200.200.200.0 network assigned.
At home office , estimated max of 50 interface
Three branch office each with 20 interface
Lease line connects at each branch to the router at home office. Each line need IP address with its own subnet.
With class C, the last 8 bit in IP address is available for subnet. We can have 6 subnet and each subnet has 30 interface
000x,xxxx cannot use [200.200.200.0]
001x,xxxx branch 1 1 subnet address, 1 broadcast address, 2 link address , 20 host address
010x,xxxx branch 2
011x,xxxx branch 3
100x,xxxx home office
101x,xxxx home office
110x,xxxx not used
111x,xxxx cannot use [200.200.200.255]
Subnet mask 255.255.255.0
Routing table 200.200.200.32 branch 1 link
200.200.200.64 Branch 2 link
200.200.200.96 branch 3 link
200.200.200.128 home office link
200.200.200.160 home office link
200.200.200. 192 default link
EE5412 Telecommunicatins Network
EE5412 TCP/IP [TcpIpQA0.doc]
---------
Domain Name Service and function of a “name server” in TCP/IP –
Domain name service (DNS) is the naming protocol used in the TCP/IP protocol suite, which enables IP routing to occur indirectly through the use of names instead of IP addresses. To accomplish this DNS provides a domain name to IP address translation service.
---------------------
The name server provides name-to-IP address translation service. It must also recognize that an address is outside its administrative zone of authority and must forward the address to another name server for translation into an appropriate IP address.
Eventually a name server will be reached that has administrative authority over the domain containing the host name to resolve and will return an IP address through a reversed hierarchy to provide the originating name server with a response to its query. Most name servers cache the results of previous name queries which can considerably reduce off-domain or internet network traffic.
DNS permits decentralized administration of resource names and specifies redundancy of Servers as a way of providing a reliable query service for users.
Decentralization of name administration is accomplished by user of multiple name fields, with each field further specifying a sub-domain.
The ‘top-level’ domain is centrally administered by the DDN Network Information Center which assigns administrative responsibility for immediately-subordinate sub-domains. Administrators for these sub-domains may in turn, create further partitioning through additional sub-domains.
------------------
ARP in TCP/IP -
ARP is Address Resolution protocol in TCP/IP. It is a mean of mapping IP address to hardware address before message can be send across a physical network. ARP maintains a table of MAC address and their corresponding IP address.
When ARP cannot find an IP address, it broadcast an “ARP REQUEST” to all o host on the network. If a host does have this IP address, it will return that information to the requester in an “ARP REPLY”. Thus the requester will be able to update its ARP table.
---------------------------------
Difference between TCP and UDP transport layer protocol
TCP is a connection-oriented protocol, meaning that TCP will set up, maintain and tear down a connection. TCP keeps track of the status and state of data passing through it. TCP ensures reliable end-to-end data transmission. TCP can also multiplex data from different applications and is full duplex.
UDP is connectionless transport level protocol for applications in layer above. UDP does not do any end-to-end error checking but uses a checksum in the UDP header.
UDP is used for small data transfers where an error is not a serious problem. It is faster and cheaper.
RIP, Routing Information Protocol and DNS, Domain Name Service use UDP.
-----------------------------------
Network congestion will increase the probability of “packet loss” which will in turn initiate packet retransmission and cause more congestion.
Technique used by TCP in Congestion control as follows -
Congestion Control
Congestion => packet-lost => retransmission. Retransmission => increase in input => more congestion => more loss.
To avoid the problem TCP use packet loss as a measure of congestion and responds by reducing the rate it transmit.
Slow Start
Whenever a message is lost, TCP begin congestion control. Instead of re-transmitting enough data to fill the window, TCP begins by sending a single packet. If “Ack” arrives without additional loss, TCP doubles the amount of data being sent and sends two additional packets.
If “Ack” arrives for these two, then TCP sends four more and so on. The increase continues until TCP is sending half of the receiver’s advertised window [ie window threshold], at which TCP slow down the rate of increase [ie. phase of congestion control].
By backing off quickly, TCP is able to alleviate congestion and help to avoid congestion collapse.
The congestion control double the congestion window every time the acknowledgements comes back which takes one round trip time (RTT) This is called the exponential growth of the congestion window in the slow start mechanism.
The exponential growth stops at the congestion threshold at which transmission rate is only increased linearly by adding one to the congestion window each time the ack comes back.
Linear increase continues until time out on missing ack or continuous ack on same packet occur. The congestion threshold is then set to half of the current congestion window and congestion window set to 1 packet.
Fast retransmit/Fast recovery
Lost of packet is indicated by the receiving of the same ack packet continuously or the timeout due to missing ack packet.
Timeout due to missing ack packet indicates packet loss due to network congestion. This will initiate congestion control and Slow Start procedure.
Receiving same ack packet continuously indicates packet loss due to transmission error. Since ack packets are received, the network is not congested. Sender can retransmit the packet before the timer expires and continue with the current congestion window. The sender performs packet recovery from packet loss. This will improve the efficiency of TCP. This is called fast retransmit and fast recovery.
Difference between “Slow Start” and “Fast retransmit/fast recovery” in TCP
• Fast Retransmit – When the sender receives the third duplicate acknowledgment, it realizes that some packets are lost and then retransmits them. This retransmission is faster than the regular timeout mechanism.
• Fast Recovery – When the Fast Retransmit mechanism signals packet loss, the sender halves the congestion window rather than drop the congestion window to 1.
Decide time out for varying delays encountered in Internet environment
Adaptive Retransmission
To avoid excessive retransmission delay
To support various networks with different delay requirements
TCP monitors current delay on each connection and estimate round-trip delay for each active connection by measuring the time needed to receive a response.
TCP generates a sequence of round-trip estimates and uses a statistical function to produce a weighted average.
In addition to a weighted average, TCP keeps an estimated of the variance, and use a linear combination of the estimated mean and variance as a value for retransmission.
TCP adaptive retransmission works well.
Variance helps TCP react quickly when delay increases following a burst of packets.
Weighted average helps TCP reset the retransmission timer if the delay returns to a lower value after a temporary burst.
When delay remains constant, TCP adjusts the retransmission timeout to a value that is slightly longer than the mean round-trip delay.
When delays start to vary, TCP adjusts the retransmission timeout to a value greater than the mean to accommodate peaks.
The goal is to wait long enough to determine that a packet was lost without waiting longer than necessary.
----------------------------
To close a TCP connection gracefully
Three Way Handshake
Problem: Delayed packets from previous connection arrive and appear to be valid packets on new connection.
To guarantee that connections are established or terminated reliably, TCP use Synchronization segment (SYN segment) to create a connection and Finish segment (FIN) to close a connection.
Ack sent in each direction are used to guarantee that all data has arrived before the connection is terminated.
TCP retransmits lost SYN or FIN segments. TCP will not open or close a connection until both ends have interacted
--------------------------
Consider the three-way handshake in TCP connection setup.
a. Suppose that an old SYN segment from station A arrives at station B requesting a TCP connection. Explain how the three-way handshake procedure ensures that the connection is rejected.
Ans:
In a three-way handshake procedure, one must ensure the selection of the initial sequence number is always unique. If station B receives an old SYN segment from A, B will acknowledge the request based on the old sequence number. When A receives the acknowledgement segment from B, A will find out that B received a wrong sequence number. A will discard the acknowledgment packet and reset the connection by sending a new SYN segment.
b. Now suppose that an old SYN segment from station A arrives at station B, followed a bit later by an old ACK segment from A to a SYN segment from B. Is this connection request also rejected?
Ans:
In an old SYN segment from A arrives at B, followed by an old ACK segment from A to a SYN segment from B, the connection will also be rejected. Initially, when B receives an old SYN segment, B will send a SYN segment with its own distinct sequence number set by itself. If B receives the old ACK from A, B will notify A that the connection is invalid since the old ACK sequence number does not match the sequence number previously defined by B. Therefore, the connection is rejected.
----------------------------
[Stalling 17.10]
In TCP/IP, is a dead lock possible using a two-way handshake instead of a three way handshake? Give an example.
Ans:
Deadlocks are possible. For example, an old packet initiate a connection arrives at A and A acknowledges it. The acknowledgement is lost, but A is now open. Now the same thing happens to B, and both are open, but expecting different sequence numbers.
Source: [TANE96]
-----------------------------
Usage of ICMP to test reachability and to trace a route
Using ICMP Messages to test Reachability
Ping use ICMP echo messages. Ping sends a datagram that contains an ICMP echo request message to the destination which sends an ICMP echo reply message. After sending the request, ping waits a shot time for the reply. If no reply arrives, ping retransmits the request twice. If no reply arrives for the retransmission, ping declares that the remote machine is not reachable.
Using ICMP to trace a route
TIME TO LIVE field in a datagram header is used to recover from routing error. If a counter reaches zero, the router discards the datagram and sends an ICMP time exceeded error back to the source.
A tool named TRACEROUTE use ICMP time exceeded messages to find a list of all routers along a path to a given destination. TRACEROUTE sends a series of datagrams and waits for a response to each.
TRACEROUTE send the TIME TO LIVE value in the first datagram to 1 before sending the datagram. The first router that receives the datagram decrements the time to live, discards the datagram, and sends back an ICMP time exceeded message. Because the ICMP message travels in an IP datagram, TRACEROUTE can extract the IP source address and announce the address of the first router along the path to the destination.
After it discovers the address of the first router, TRACEROUTE repeats the process with TIME TO LIVE sets to 2. The first router decrement the counter to 1 and forward the datagram. The second counter will decrement the counter to zero, discard the packet and sends back an error message.
-------------------------
IPV6 enchancements over IPV4
Expanded address space – 128 bit instead of 32 bit
Improved option mechanism – options are placed in separate optional header. This simplifies and speeds up router processing of IPV6 packets. It also makes it easier to add additional options. [options are not examined by intermediate routers]
Address auto-configuration – enable dynamic assignment of IPV6 address.
Increased addressing flexibility and capability – support conference call, multi-cast address
Support for resource allocation – label of packets belong to a particular traffic flow, support for audo and video traffic
--------------------------------------------
[Stalling 17.19]
b. A TCP entity opens a connection and uses slow start. Approximately how many round-trip times are required before TCP can send N segments? Briefly explain how you get the answer.
TCP initializes the congestion window to 1, sends an initial segment, and waits. When the ACK arrives, it increases the congestion window to 2, sends 2 segments, and waits. When the 2 ACKs arrive, they each increase the congestion window by one, so that it can send 4 segments. In general, it takes log2N round trips before TCP can send N segments.
c. Assume a round trip delay of a link across a continent is 60 ms. The link bandwidth is 1 Gbps. Assume the packet size of 10k bits is used. Determine the minimum window size needed to keep the pipe full.
Ans: packet transmission time = 100k/1G sec = 0.1 msec.
Minimum window size = [60msec] / [0.1msec] = 600
---------------------------
---------
Domain Name Service and function of a “name server” in TCP/IP –
Domain name service (DNS) is the naming protocol used in the TCP/IP protocol suite, which enables IP routing to occur indirectly through the use of names instead of IP addresses. To accomplish this DNS provides a domain name to IP address translation service.
---------------------
The name server provides name-to-IP address translation service. It must also recognize that an address is outside its administrative zone of authority and must forward the address to another name server for translation into an appropriate IP address.
Eventually a name server will be reached that has administrative authority over the domain containing the host name to resolve and will return an IP address through a reversed hierarchy to provide the originating name server with a response to its query. Most name servers cache the results of previous name queries which can considerably reduce off-domain or internet network traffic.
DNS permits decentralized administration of resource names and specifies redundancy of Servers as a way of providing a reliable query service for users.
Decentralization of name administration is accomplished by user of multiple name fields, with each field further specifying a sub-domain.
The ‘top-level’ domain is centrally administered by the DDN Network Information Center which assigns administrative responsibility for immediately-subordinate sub-domains. Administrators for these sub-domains may in turn, create further partitioning through additional sub-domains.
------------------
ARP in TCP/IP -
ARP is Address Resolution protocol in TCP/IP. It is a mean of mapping IP address to hardware address before message can be send across a physical network. ARP maintains a table of MAC address and their corresponding IP address.
When ARP cannot find an IP address, it broadcast an “ARP REQUEST” to all o host on the network. If a host does have this IP address, it will return that information to the requester in an “ARP REPLY”. Thus the requester will be able to update its ARP table.
---------------------------------
Difference between TCP and UDP transport layer protocol
TCP is a connection-oriented protocol, meaning that TCP will set up, maintain and tear down a connection. TCP keeps track of the status and state of data passing through it. TCP ensures reliable end-to-end data transmission. TCP can also multiplex data from different applications and is full duplex.
UDP is connectionless transport level protocol for applications in layer above. UDP does not do any end-to-end error checking but uses a checksum in the UDP header.
UDP is used for small data transfers where an error is not a serious problem. It is faster and cheaper.
RIP, Routing Information Protocol and DNS, Domain Name Service use UDP.
-----------------------------------
Network congestion will increase the probability of “packet loss” which will in turn initiate packet retransmission and cause more congestion.
Technique used by TCP in Congestion control as follows -
Congestion Control
Congestion => packet-lost => retransmission. Retransmission => increase in input => more congestion => more loss.
To avoid the problem TCP use packet loss as a measure of congestion and responds by reducing the rate it transmit.
Slow Start
Whenever a message is lost, TCP begin congestion control. Instead of re-transmitting enough data to fill the window, TCP begins by sending a single packet. If “Ack” arrives without additional loss, TCP doubles the amount of data being sent and sends two additional packets.
If “Ack” arrives for these two, then TCP sends four more and so on. The increase continues until TCP is sending half of the receiver’s advertised window [ie window threshold], at which TCP slow down the rate of increase [ie. phase of congestion control].
By backing off quickly, TCP is able to alleviate congestion and help to avoid congestion collapse.
The congestion control double the congestion window every time the acknowledgements comes back which takes one round trip time (RTT) This is called the exponential growth of the congestion window in the slow start mechanism.
The exponential growth stops at the congestion threshold at which transmission rate is only increased linearly by adding one to the congestion window each time the ack comes back.
Linear increase continues until time out on missing ack or continuous ack on same packet occur. The congestion threshold is then set to half of the current congestion window and congestion window set to 1 packet.
Fast retransmit/Fast recovery
Lost of packet is indicated by the receiving of the same ack packet continuously or the timeout due to missing ack packet.
Timeout due to missing ack packet indicates packet loss due to network congestion. This will initiate congestion control and Slow Start procedure.
Receiving same ack packet continuously indicates packet loss due to transmission error. Since ack packets are received, the network is not congested. Sender can retransmit the packet before the timer expires and continue with the current congestion window. The sender performs packet recovery from packet loss. This will improve the efficiency of TCP. This is called fast retransmit and fast recovery.
Difference between “Slow Start” and “Fast retransmit/fast recovery” in TCP
• Fast Retransmit – When the sender receives the third duplicate acknowledgment, it realizes that some packets are lost and then retransmits them. This retransmission is faster than the regular timeout mechanism.
• Fast Recovery – When the Fast Retransmit mechanism signals packet loss, the sender halves the congestion window rather than drop the congestion window to 1.
Decide time out for varying delays encountered in Internet environment
Adaptive Retransmission
To avoid excessive retransmission delay
To support various networks with different delay requirements
TCP monitors current delay on each connection and estimate round-trip delay for each active connection by measuring the time needed to receive a response.
TCP generates a sequence of round-trip estimates and uses a statistical function to produce a weighted average.
In addition to a weighted average, TCP keeps an estimated of the variance, and use a linear combination of the estimated mean and variance as a value for retransmission.
TCP adaptive retransmission works well.
Variance helps TCP react quickly when delay increases following a burst of packets.
Weighted average helps TCP reset the retransmission timer if the delay returns to a lower value after a temporary burst.
When delay remains constant, TCP adjusts the retransmission timeout to a value that is slightly longer than the mean round-trip delay.
When delays start to vary, TCP adjusts the retransmission timeout to a value greater than the mean to accommodate peaks.
The goal is to wait long enough to determine that a packet was lost without waiting longer than necessary.
----------------------------
To close a TCP connection gracefully
Three Way Handshake
Problem: Delayed packets from previous connection arrive and appear to be valid packets on new connection.
To guarantee that connections are established or terminated reliably, TCP use Synchronization segment (SYN segment) to create a connection and Finish segment (FIN) to close a connection.
Ack sent in each direction are used to guarantee that all data has arrived before the connection is terminated.
TCP retransmits lost SYN or FIN segments. TCP will not open or close a connection until both ends have interacted
--------------------------
Consider the three-way handshake in TCP connection setup.
a. Suppose that an old SYN segment from station A arrives at station B requesting a TCP connection. Explain how the three-way handshake procedure ensures that the connection is rejected.
Ans:
In a three-way handshake procedure, one must ensure the selection of the initial sequence number is always unique. If station B receives an old SYN segment from A, B will acknowledge the request based on the old sequence number. When A receives the acknowledgement segment from B, A will find out that B received a wrong sequence number. A will discard the acknowledgment packet and reset the connection by sending a new SYN segment.
b. Now suppose that an old SYN segment from station A arrives at station B, followed a bit later by an old ACK segment from A to a SYN segment from B. Is this connection request also rejected?
Ans:
In an old SYN segment from A arrives at B, followed by an old ACK segment from A to a SYN segment from B, the connection will also be rejected. Initially, when B receives an old SYN segment, B will send a SYN segment with its own distinct sequence number set by itself. If B receives the old ACK from A, B will notify A that the connection is invalid since the old ACK sequence number does not match the sequence number previously defined by B. Therefore, the connection is rejected.
----------------------------
[Stalling 17.10]
In TCP/IP, is a dead lock possible using a two-way handshake instead of a three way handshake? Give an example.
Ans:
Deadlocks are possible. For example, an old packet initiate a connection arrives at A and A acknowledges it. The acknowledgement is lost, but A is now open. Now the same thing happens to B, and both are open, but expecting different sequence numbers.
Source: [TANE96]
-----------------------------
Usage of ICMP to test reachability and to trace a route
Using ICMP Messages to test Reachability
Ping use ICMP echo messages. Ping sends a datagram that contains an ICMP echo request message to the destination which sends an ICMP echo reply message. After sending the request, ping waits a shot time for the reply. If no reply arrives, ping retransmits the request twice. If no reply arrives for the retransmission, ping declares that the remote machine is not reachable.
Using ICMP to trace a route
TIME TO LIVE field in a datagram header is used to recover from routing error. If a counter reaches zero, the router discards the datagram and sends an ICMP time exceeded error back to the source.
A tool named TRACEROUTE use ICMP time exceeded messages to find a list of all routers along a path to a given destination. TRACEROUTE sends a series of datagrams and waits for a response to each.
TRACEROUTE send the TIME TO LIVE value in the first datagram to 1 before sending the datagram. The first router that receives the datagram decrements the time to live, discards the datagram, and sends back an ICMP time exceeded message. Because the ICMP message travels in an IP datagram, TRACEROUTE can extract the IP source address and announce the address of the first router along the path to the destination.
After it discovers the address of the first router, TRACEROUTE repeats the process with TIME TO LIVE sets to 2. The first router decrement the counter to 1 and forward the datagram. The second counter will decrement the counter to zero, discard the packet and sends back an error message.
-------------------------
IPV6 enchancements over IPV4
Expanded address space – 128 bit instead of 32 bit
Improved option mechanism – options are placed in separate optional header. This simplifies and speeds up router processing of IPV6 packets. It also makes it easier to add additional options. [options are not examined by intermediate routers]
Address auto-configuration – enable dynamic assignment of IPV6 address.
Increased addressing flexibility and capability – support conference call, multi-cast address
Support for resource allocation – label of packets belong to a particular traffic flow, support for audo and video traffic
--------------------------------------------
[Stalling 17.19]
b. A TCP entity opens a connection and uses slow start. Approximately how many round-trip times are required before TCP can send N segments? Briefly explain how you get the answer.
TCP initializes the congestion window to 1, sends an initial segment, and waits. When the ACK arrives, it increases the congestion window to 2, sends 2 segments, and waits. When the 2 ACKs arrive, they each increase the congestion window by one, so that it can send 4 segments. In general, it takes log2N round trips before TCP can send N segments.
c. Assume a round trip delay of a link across a continent is 60 ms. The link bandwidth is 1 Gbps. Assume the packet size of 10k bits is used. Determine the minimum window size needed to keep the pipe full.
Ans: packet transmission time = 100k/1G sec = 0.1 msec.
Minimum window size = [60msec] / [0.1msec] = 600
---------------------------
EE5412 Telecommunication Networks
EE5412 [TCPIP/IPV6.doc]
[Computer Network and Internets; Dougles E Comer] [Ch14,15,18,19]
The future IP – IPV6
Motivation for change –
1. Address space limitation – larger addresses necessary to accommodate continued growth of Internet.
2. New applications –
Real time transmission for Audio & video
To keep such information flowing through the Internet without disruption, IP must avoid changing routes frequently.
Although the current IP datagram header includes a field that can be used to request a type of service, the protocol did not define a type of service that can be used for real time delivery of data.
More complex addressing and routing capabilities
Communication among a group of colleagues analogous to a telephone conference call .
To make collaboration effective, an internet needs a mechanism that allow groups to be created or changed, and provides a way to send a copy of a packet to each participant in a given group.
Groups to handle load sharing
That is, several identical copies of a service exist, and a packet sent to the group is routed to the copy of the service that is closest to the sender.
Characterization of Features in IPv6
1. Connectionless – each datagram contains a destination address and is routed independently.
2. The header contains a max number of hops before being discarded.
New features in IPV6 –
Address Size – 128 bits instead of 32 bits
Header Format – completely new format
Extension Header – A datagram consists of the base header followed by zero or more extension headers followed by data.
Support for audio and video – allows a sender and receiver to establish a high quality path through the network and to associate datagrams with that path. Mechanism is intended for use with audio and video applications that require high performance guarantees. The mechanism can also be used to associate datagrams with low-cost paths.
Extensible Protocol – does not specify all possible protocol features. The header extension scheme allow new features can be added to new design as needed.
IPV6 Datagram format
Base header plus data with optional extension header
Options in payload area of base header
IPV6 Base Header format - fewer field than IPV4
Version
Flow Label – divided into two parts – one used to specify a traffic class and the other used to define a specific path. Routers use the value to route the datagram along the prearranged path. A label is used and label is assigned by system on path setup.
Payload length – size of data carried
Next Header – specify the type of information that follows the current header.
Hop Limit – discard if hop limit counts down to zero
Source Address – 16 Octets
Destination Address – 16 Octets
Multiple headers – use Next Header field to determine the contents of multiple headers. Allow new or experimental header to add on without affecting the operation of the existing headers as long as the new header appears after the existing headers.
IPV6 Addressing - three basic types
Unicast – to a single computer ;
Multicast – one copy to each of the member;
Cluster – computers share a common address - datagram send to one of the computer [the nearest one]
Allow replication of services.
IPV6 Colon Hexadecimal Notation - written in hexadecimal with a colon separating groups.
[Computer Network and Internets; Dougles E Comer] [Ch14,15,18,19]
The future IP – IPV6
Motivation for change –
1. Address space limitation – larger addresses necessary to accommodate continued growth of Internet.
2. New applications –
Real time transmission for Audio & video
To keep such information flowing through the Internet without disruption, IP must avoid changing routes frequently.
Although the current IP datagram header includes a field that can be used to request a type of service, the protocol did not define a type of service that can be used for real time delivery of data.
More complex addressing and routing capabilities
Communication among a group of colleagues analogous to a telephone conference call .
To make collaboration effective, an internet needs a mechanism that allow groups to be created or changed, and provides a way to send a copy of a packet to each participant in a given group.
Groups to handle load sharing
That is, several identical copies of a service exist, and a packet sent to the group is routed to the copy of the service that is closest to the sender.
Characterization of Features in IPv6
1. Connectionless – each datagram contains a destination address and is routed independently.
2. The header contains a max number of hops before being discarded.
New features in IPV6 –
Address Size – 128 bits instead of 32 bits
Header Format – completely new format
Extension Header – A datagram consists of the base header followed by zero or more extension headers followed by data.
Support for audio and video – allows a sender and receiver to establish a high quality path through the network and to associate datagrams with that path. Mechanism is intended for use with audio and video applications that require high performance guarantees. The mechanism can also be used to associate datagrams with low-cost paths.
Extensible Protocol – does not specify all possible protocol features. The header extension scheme allow new features can be added to new design as needed.
IPV6 Datagram format
Base header plus data with optional extension header
Options in payload area of base header
IPV6 Base Header format - fewer field than IPV4
Version
Flow Label – divided into two parts – one used to specify a traffic class and the other used to define a specific path. Routers use the value to route the datagram along the prearranged path. A label is used and label is assigned by system on path setup.
Payload length – size of data carried
Next Header – specify the type of information that follows the current header.
Hop Limit – discard if hop limit counts down to zero
Source Address – 16 Octets
Destination Address – 16 Octets
Multiple headers – use Next Header field to determine the contents of multiple headers. Allow new or experimental header to add on without affecting the operation of the existing headers as long as the new header appears after the existing headers.
IPV6 Addressing - three basic types
Unicast – to a single computer ;
Multicast – one copy to each of the member;
Cluster – computers share a common address - datagram send to one of the computer [the nearest one]
Allow replication of services.
IPV6 Colon Hexadecimal Notation - written in hexadecimal with a colon separating groups.
EE5412 IP_Subnet1.doc
EE5412 Telecommunications Networks
IP_Subnet1.doc
[IP_Subnet1.doc]
Objective of address masking in router
Obtain network address and host address
To form subnets
Simplify routing table
Speed – improve router performance
------------------
From IP address , network mask, network class, network address and host address can be obtained.
eg. IP address 144.214.112.55
Ans: class B network
144.214.0.0 network address
112.55 host address
---------------------
Subnet example –
IP address 214.146.231.70 /28. [ ie. Host address suffix has 4 bits.]
Find
1. network class
2. network mask
3. network address
4. subnet mask
5. subnet address.
6. host ID with in the subnet
7. broadcast address to the subnet
214 = 1101, 0110
70 = 0100, 0110 Subnet number Host number
240 = 1111, 0000 mask
64 = 0100, 0000 Subnet number
79 = 0100, 1111 Net Broadcast
Ans: class C network
Network mask 255.255.255.0
Network address 214.146.231.0
subnet mask 255.255.255.240
Subnet address 214.146.231.64
Host ID 6
Broadcast address 214.146.231.79
---------------------------------
IP_Subnet1.doc
[IP_Subnet1.doc]
Objective of address masking in router
Obtain network address and host address
To form subnets
Simplify routing table
Speed – improve router performance
------------------
From IP address , network mask, network class, network address and host address can be obtained.
eg. IP address 144.214.112.55
Ans: class B network
144.214.0.0 network address
112.55 host address
---------------------
Subnet example –
IP address 214.146.231.70 /28. [ ie. Host address suffix has 4 bits.]
Find
1. network class
2. network mask
3. network address
4. subnet mask
5. subnet address.
6. host ID with in the subnet
7. broadcast address to the subnet
214 = 1101, 0110
70 = 0100, 0110 Subnet number Host number
240 = 1111, 0000 mask
64 = 0100, 0000 Subnet number
79 = 0100, 1111 Net Broadcast
Ans: class C network
Network mask 255.255.255.0
Network address 214.146.231.0
subnet mask 255.255.255.240
Subnet address 214.146.231.64
Host ID 6
Broadcast address 214.146.231.79
---------------------------------
EE5412 TCP/IP
[note/notew/TCPIP/Inpernet0.doc]
[Computer Network and Internets; Dougles E Comer] [Ch14,15,18,19]
The Internet Protocol ( IP )
The IP provides for the transmission of datagrams between systems over a collection of networks. It allows for fragmentation and reassembly of the data-grams at the gateways. Different networks may require different packet sizes.
IP Header - Format of internet datagram header
Header length - Header length depends on the length of option field. This field indicates where the data starts.
ID/flag/offset - These fields enable a gateway to split up the datagram into smaller segments. The ID field ensures that the receiver can piece together the fragments from the correct datagram. Fragments from datagrams may arrive in any order. The offset tells how far down the datagram this fragment is. The flags can be used to mark the datagram as non-fragment.
Time to Live - Counter limiting the lifetime of a data-gram. Each time it passes through a gateway, the count is decremented by one. If it reach zero, the gateway does not forward it. This prevents permanently circulating data-grams.
Protocol - indicates which protocol it carries
Checksum - for the header only
Address - Each IP address is structured into a Network Number and a local address.
Options - Last part of the header containing variable number of optional fields which is used for security and network management.
Padding - used to align the header.
There is no facility for error reporting in IP. An extra protocol ICMP ( Internet control message protocol) is used to report errors without trying to recover from error. It is used to help gateways.
eg. ICMP messages - Time exceeded - datagram lifetime expire
Destination Unreachable - gateway or network failure
IP Addressing
Each host assigns a unique address - a unique 32-bit binary number
IP address hierarchy-
A prefix to identify a physical network
A suffix to identify individual connection to the network
Authority for addresses
Internet Service Provider (ISP) coordinate with a central organization, the Internet Assigned Number Authority to ensure that each network prefix is unique throughout the entire Internet.
Classes of IP Address –
Five classes of IP addressing –
Class A – large network 0 + 7 bits network ID
Class B – medium network 10 + 13 bits network ID
Class C – small network 110 + 21 bits network ID
Address Space
Class A address can range from 0 to 127,
Class B address range is from 128 to 191,
Class C address range from 192 to 223.
Dotted Decimal Notation
32 bits ; four octets Each octet is converted to its decimal equivalent.
10000100.0110000.00000011.00000111 132.96.3.7
Special IP Address – reserved address
1. Network Address
IP reserves host address zero and uses it to denote a network.
Thus address 128.211.0.0 denotes the network that has been assigned the class B prefix 128.211.
2. Direct Broadcast Address – IP reserve the host address that contains all 1 as broadcast address.
3. This Computer Address – When a computer start up, it does not know its IP and cannot use the correct IP to communicate. The start up protocol use a reserved IP [all zero] to communicate.
4. Loopback Address – network testing applications
Data travels down the protocol stack to the IP software, which forwards it back up through the protocol stack. IP reserves the class A network 127 for use with loopback. The host address is irrelevant. Programmer use host number 1, making 127.0.0.1 the popular loop back address.
Router and the IP
Connection to multiple physical networks.
Each IP prefix a physical network.
One IP for each connection.
IP Datagram Forwarding
Performed by routers
Table driven; entry specified next hop
Next hop is router or destination
……………………………………..……………………… ……. …………………………………..
Routing table size
Number of entries in a routing table is proportional to the number of networks in an internet.
Default route corresponds to all destinations not explicitly listed => keeps routing table sizes small.
Note:
The destination address in a datagram header always refers to the ultimate destination. When a router forwards the datagram to another router, the address of the next hop does not appear in the datagram header.
Once the next hop address has been found, IP software transfers the packet across one physical network to the selected host or router.
This is done by encapsulating the datagram in a physical frame and sends the resulting frame directly to the destination.
IP address cannot be used when transmitting frames across physical network because the interface hardware does not understand IP address. Hardware only recognizes physical hardware address.
ARP – Address Resolution –
Mapping IP address to physical address [MAC address] before message can be send across a physical network.
ARP maintains a table of MAC addresses and their corresponding IP address.
Address Resolution Techniques
Table lookup;
Closed-form computation
Message exchange – network with server dedicated for address resolution function
ARP Look-up
Look for IP address in ARP table.
If not found, broadcast “ARP REQUEST” message.
Receive reply with hardware address.
Add entry to table
Address Resolution Protocol
ARP defines two basic message types – “request” and “response”
Request message contains an IP address and requests the corresponding hardware address.
Reply message contains an IP address and the hardware address.
ARP request message should be placed in hardware frame and broadcast out. The requested computer should response. Other computer discards the request. The response is placed in frame and sent directly back. ..
ARP Message Format
Although the ARP message is sufficiently general to allow arbitrary protocol and hardware addresses, ARP is almost always used to bind a 32-bit IP address to a 48-bit ethernet address.
Sending an ARP Message [fig 15.7]
The ARP message is encapsulated in a hardware frame
Identifying ARP Frames – type field in an Ethernet frame = 0x806
Caching ARP Responses –
Although message exchange can be used to bind addresses, sending a request for each binding is inefficient. When computer W has a packet to deliver to computer Y, W first broadcasts an ARP request to find out Y’s hardware address. After Y sends a reply, W can deliver the original packet to Y. W is likely to repeat the process many times.
To reduce the network traffic, ARP maintains a small table of bindings in memory. Whenever ARP performs address binding, it searches the cache before using the network.
Because ARP software is part of the network interface software, all higher layer protocols and applications can use IP addresses exclusively and completely unaware of hardware address.
Datagram Fragmentation
Different network with different packet size limitation
Large packet from one network may have to be segmented into smaller packets before sending to the next network.
Packets reassembled in destination.
ICMP – Internet Control Message Protocol
IP is assisted by ICPM and ARP. IP is connectionless and has no way to send error and status message back to the sender. It relies upon ICMP to do these tasks. ICMP sends error and status message back to the sending host and also handles routing and flow control.
Eg. A request through ICMP for information about another IP address is called a PING (Packet Internet Groper). The response with the requested information is called a PONG. UDP command FINGER asks the remote host what users are logged on
Five error messages and four informational messages
Error Message
1. Source Quench – When a router gets too busy, it sends a source quench message to the host that created the message. The host is required to reduce the rate of transmitting.
2. Time Exceeded – Whenever a router reduces the “time to live” to zero, it discard the datagram and send a time exceeded message. [eg. time to reassemble a message; time stay in network]
3. Destination Unreachable
4. Redirect – router receive a datagram that should be send to different router;
The router use the redirect message to cause the host to change its route.
5. Fragmentation Required – packet with bit set for fragmentation not allowed. However, the datagram size is larger than that allowed in the subsequent network.
Informational messages:
1. Echo Request/Reply
2. Address Mask Request/Reply – computer boot up and request address mask. Router response with the mask.
Using ICMP Messages to test Reachability
Ping use ICMP echo messages. Ping sends a datagram that contains an ICMP echo request message to the destination which sends an ICMP echo reply message. After sending the request, ping waits a shot time for the reply. If no reply arrives, ping retransmits the request twice. If no reply arrives for the retransmission, ping declares that the remote machine is not reachable.
Using ICMP to trace a route
TIME TO LIVE field in a datagram header is used to recover from routing error. If a counter reaches zero, the router discards the datagram and sends an ICMP time exceeded error back to the source.
A tool named TRACEROUTE use ICMP time exceeded messages to find a list of all routers along a path to a given destination. TRACEROUTE sends a series of datagrams and waits for a response to each.
TRACEROUTE send the TIME TO LIVE value in the first datagram to 1 before sending the datagram. The first router that receives the datagram decrements the time to live, discards the datagram, and sends back an ICMP time exceeded message.
Because the ICMP message travels in an IP datagram, TRACEROUTE can extract the IP source address and announce the address of the first router along the path to the destination.
After it discovers the address of the first router, TRACEROUTE repeats the process with TIME TO LIVE sets to 2. The first router decrement the counter to 1 and forward the datagram. The second counter will decrement the counter to zero, discard the packet and sends band an error message.
Transport Layer Protocols [TCP and UDP]
TCP
At the sending host TCP segments the data into smaller datagrams and adds consecutive sequence numbers. At the receiving host TCP reassembles the datagrams into their proper order. On receiving datagrams, IP passes the datagram to next layer TCP or UDP.
TCP is a connection oriented protocol, meaning that TCP will set up, maintain and tear down a connection. TCP keeps track of the status and state of data passing through it. TCP ensures reliable end to end data transmission. TCP can also multiplex data from different applications and is full duplex.
UDP
UDP is connectionless transport level protocol for applications in layer above. UDP does not do any end to end error checking but uses a checksum in the UDP header.
UDP is used for small data transfers where an error is not a serious problem. It is faster and cheaper.
Eg. RIP, Routing Information Protocol and DNS, Domain Name Service use UDP.
TCP – Transmission Control Protocol
TCP provides a completely reliable, connection-oriented, full-duplex stream transport service.
Services –
1. Connection Orientation
2. Point-TO-Point Communication
3. Complete reliability
4. Full duplex
5. Stream interface – does not guarantee that data will be delivered in the same size piece.
6. Reliable connection Startup – duplicated packet from previous connection will not appear.
7. Graceful Connection Shutdown – guarantees to deliver all data reliably before closing the connection.
End to End Service
TCP is called an end-to-end protocol providing connection directly from application on one computer to another application on a remote computer.
TCP provide virtual connections and rely on IP to carry messages. Each TCP message is encapsulated in an IP datagram and sent across the internet.
Packet loss and retransmission
TCP use timer, Ack and retransmission for reliable data transfer.
Adaptive Retransmission
To avoid excessive retransmission delay
To support various networks with different delay requirements
TCP monitors current delay on each connection and estimate round-trip delay for each active connection by measuring the time needed to receive a response.
TCP generates a sequence of round-trip estimates and uses a statistical function to produce a weighted average.
In addition to a weighted average, TCP keeps an estimated of the variance, and use a linear combination of the estimated mean and variance as a value for retransmission.
TCP adaptive retransmission works well.
Variance helps TCP react quickly when delay increases following a burst of packets.
Weighted average helps TCP reset the retransmission timer if the delay returns to a lower value after a temporary burst.
When delay remains constant, TCP adjusts the retransmission timeout to a value that is slightly longer than the mean round-trip delay.
When delays start to vary, TCP adjusts the retransmission timeout to a value greater than the mean to accommodate peaks.
The goal is to wait long enough to determine that a packet was lost without waiting longer than necessary.
////////
Three Way Handshake
Delayed packets from previous connection arrive and appear to be valid packets on new connection.
To guarantee that connections are established or terminated reliably,
TCP use Synchronization segment (SYN segment) to create a connection and Finish segment (FIN) to close a connection.
Ack sent in each direction are used to guarantee that all data has arrived before the connection is terminated.
TCP retransmits lost SYN or FIN segments. TCP will not open or close a connection until both ends have interacted.
//////
Congestion Control
Congestion => packet-lost => retransmission. Retransmission => increase in input => more congestion
=> more loss.
To avoid the problem TCP use packet loss as a measure of congestion and responds by reducing the rate it transmit.
Whenever a message is lost, TCP begin congestion control. Instead of re-transmitting enough data to fill the window, TCP begins by sending a single packet. If the Ack arrives without additional loss, TCP doubles the amount of data being sent and sends two additional packets.
If Ack arrives for these two, then TCP sends four more and so on. The increase continues until TCP is sending half of the receiver’s advertised window, at which TCP slow down the rate of increase.
By backing off quickly, TCP is able to alleviate congestion and help to avoid congestion collapse.
TCP Segment Format
TCP uses single format for all messages including data, Ack and message to create or terminate a connection.
Troubleshooting [relating Logical topology and the physical network]
Packet management and troubleshooting worked at the lower levels of the protocol stack, Physical, Data Link and Network levels.
An IP network may have many Physical networks using many different types of packet switches interconnected by IP gateways.
The IP gateways are what network managers must control. The IP network management must run at the Application level because of the many possible protocols and types of systems within an IP network.
The management and troubleshooting software must be written without regard to the hardware in the IP network. The same protocol must be able to be used for all gateways. However if the problems are at levels beneath the management and troubleshooting software’s level, the problem cannot be fixed by the IP administrator.
For instance the IP troubleshooter cannot fix a failing operating system or a corrupted routing tale or a system needing to be re-booted. The network people must fix these types of problems.
The most popular tool for TCP/IP management is Simple Network Management Protocol (SNMP).
Each gateway maintains statistics on its operation in a database called Management Information Base (MIB). Typical gateway data includes:
The gateway operating system
Network interface
ARP mappings [address resolution]
IP software
ICMP software [internet control message]
TCP software
UDP software
Some MIB statistic might include
Time since last re-boot
Number of datagrams received
Number of datagrams forwarded
Number of routing failures
Number of datagrams reassembled
Number of datagrams fragmented
The IP routing table
Number of messages received and type of message
Fetch, Store and Trap
SNMP uses only a variation of fetch and store commands. Eg. fetch value from a specific item in MIB or stores a value into MIB.
A trap is recording a particular event, such as too many routing failures and sent a message to network manager.
[Computer Network and Internets; Dougles E Comer] [Ch14,15,18,19]
The Internet Protocol ( IP )
The IP provides for the transmission of datagrams between systems over a collection of networks. It allows for fragmentation and reassembly of the data-grams at the gateways. Different networks may require different packet sizes.
IP Header - Format of internet datagram header
Header length - Header length depends on the length of option field. This field indicates where the data starts.
ID/flag/offset - These fields enable a gateway to split up the datagram into smaller segments. The ID field ensures that the receiver can piece together the fragments from the correct datagram. Fragments from datagrams may arrive in any order. The offset tells how far down the datagram this fragment is. The flags can be used to mark the datagram as non-fragment.
Time to Live - Counter limiting the lifetime of a data-gram. Each time it passes through a gateway, the count is decremented by one. If it reach zero, the gateway does not forward it. This prevents permanently circulating data-grams.
Protocol - indicates which protocol it carries
Checksum - for the header only
Address - Each IP address is structured into a Network Number and a local address.
Options - Last part of the header containing variable number of optional fields which is used for security and network management.
Padding - used to align the header.
There is no facility for error reporting in IP. An extra protocol ICMP ( Internet control message protocol) is used to report errors without trying to recover from error. It is used to help gateways.
eg. ICMP messages - Time exceeded - datagram lifetime expire
Destination Unreachable - gateway or network failure
IP Addressing
Each host assigns a unique address - a unique 32-bit binary number
IP address hierarchy-
A prefix to identify a physical network
A suffix to identify individual connection to the network
Authority for addresses
Internet Service Provider (ISP) coordinate with a central organization, the Internet Assigned Number Authority to ensure that each network prefix is unique throughout the entire Internet.
Classes of IP Address –
Five classes of IP addressing –
Class A – large network 0 + 7 bits network ID
Class B – medium network 10 + 13 bits network ID
Class C – small network 110 + 21 bits network ID
Address Space
Class A address can range from 0 to 127,
Class B address range is from 128 to 191,
Class C address range from 192 to 223.
Dotted Decimal Notation
32 bits ; four octets Each octet is converted to its decimal equivalent.
10000100.0110000.00000011.00000111 132.96.3.7
Special IP Address – reserved address
1. Network Address
IP reserves host address zero and uses it to denote a network.
Thus address 128.211.0.0 denotes the network that has been assigned the class B prefix 128.211.
2. Direct Broadcast Address – IP reserve the host address that contains all 1 as broadcast address.
3. This Computer Address – When a computer start up, it does not know its IP and cannot use the correct IP to communicate. The start up protocol use a reserved IP [all zero] to communicate.
4. Loopback Address – network testing applications
Data travels down the protocol stack to the IP software, which forwards it back up through the protocol stack. IP reserves the class A network 127 for use with loopback. The host address is irrelevant. Programmer use host number 1, making 127.0.0.1 the popular loop back address.
Router and the IP
Connection to multiple physical networks.
Each IP prefix a physical network.
One IP for each connection.
IP Datagram Forwarding
Performed by routers
Table driven; entry specified next hop
Next hop is router or destination
……………………………………..……………………… ……. …………………………………..
Routing table size
Number of entries in a routing table is proportional to the number of networks in an internet.
Default route corresponds to all destinations not explicitly listed => keeps routing table sizes small.
Note:
The destination address in a datagram header always refers to the ultimate destination. When a router forwards the datagram to another router, the address of the next hop does not appear in the datagram header.
Once the next hop address has been found, IP software transfers the packet across one physical network to the selected host or router.
This is done by encapsulating the datagram in a physical frame and sends the resulting frame directly to the destination.
IP address cannot be used when transmitting frames across physical network because the interface hardware does not understand IP address. Hardware only recognizes physical hardware address.
ARP – Address Resolution –
Mapping IP address to physical address [MAC address] before message can be send across a physical network.
ARP maintains a table of MAC addresses and their corresponding IP address.
Address Resolution Techniques
Table lookup;
Closed-form computation
Message exchange – network with server dedicated for address resolution function
ARP Look-up
Look for IP address in ARP table.
If not found, broadcast “ARP REQUEST” message.
Receive reply with hardware address.
Add entry to table
Address Resolution Protocol
ARP defines two basic message types – “request” and “response”
Request message contains an IP address and requests the corresponding hardware address.
Reply message contains an IP address and the hardware address.
ARP request message should be placed in hardware frame and broadcast out. The requested computer should response. Other computer discards the request. The response is placed in frame and sent directly back. ..
ARP Message Format
Although the ARP message is sufficiently general to allow arbitrary protocol and hardware addresses, ARP is almost always used to bind a 32-bit IP address to a 48-bit ethernet address.
Sending an ARP Message [fig 15.7]
The ARP message is encapsulated in a hardware frame
Identifying ARP Frames – type field in an Ethernet frame = 0x806
Caching ARP Responses –
Although message exchange can be used to bind addresses, sending a request for each binding is inefficient. When computer W has a packet to deliver to computer Y, W first broadcasts an ARP request to find out Y’s hardware address. After Y sends a reply, W can deliver the original packet to Y. W is likely to repeat the process many times.
To reduce the network traffic, ARP maintains a small table of bindings in memory. Whenever ARP performs address binding, it searches the cache before using the network.
Because ARP software is part of the network interface software, all higher layer protocols and applications can use IP addresses exclusively and completely unaware of hardware address.
Datagram Fragmentation
Different network with different packet size limitation
Large packet from one network may have to be segmented into smaller packets before sending to the next network.
Packets reassembled in destination.
ICMP – Internet Control Message Protocol
IP is assisted by ICPM and ARP. IP is connectionless and has no way to send error and status message back to the sender. It relies upon ICMP to do these tasks. ICMP sends error and status message back to the sending host and also handles routing and flow control.
Eg. A request through ICMP for information about another IP address is called a PING (Packet Internet Groper). The response with the requested information is called a PONG. UDP command FINGER asks the remote host what users are logged on
Five error messages and four informational messages
Error Message
1. Source Quench – When a router gets too busy, it sends a source quench message to the host that created the message. The host is required to reduce the rate of transmitting.
2. Time Exceeded – Whenever a router reduces the “time to live” to zero, it discard the datagram and send a time exceeded message. [eg. time to reassemble a message; time stay in network]
3. Destination Unreachable
4. Redirect – router receive a datagram that should be send to different router;
The router use the redirect message to cause the host to change its route.
5. Fragmentation Required – packet with bit set for fragmentation not allowed. However, the datagram size is larger than that allowed in the subsequent network.
Informational messages:
1. Echo Request/Reply
2. Address Mask Request/Reply – computer boot up and request address mask. Router response with the mask.
Using ICMP Messages to test Reachability
Ping use ICMP echo messages. Ping sends a datagram that contains an ICMP echo request message to the destination which sends an ICMP echo reply message. After sending the request, ping waits a shot time for the reply. If no reply arrives, ping retransmits the request twice. If no reply arrives for the retransmission, ping declares that the remote machine is not reachable.
Using ICMP to trace a route
TIME TO LIVE field in a datagram header is used to recover from routing error. If a counter reaches zero, the router discards the datagram and sends an ICMP time exceeded error back to the source.
A tool named TRACEROUTE use ICMP time exceeded messages to find a list of all routers along a path to a given destination. TRACEROUTE sends a series of datagrams and waits for a response to each.
TRACEROUTE send the TIME TO LIVE value in the first datagram to 1 before sending the datagram. The first router that receives the datagram decrements the time to live, discards the datagram, and sends back an ICMP time exceeded message.
Because the ICMP message travels in an IP datagram, TRACEROUTE can extract the IP source address and announce the address of the first router along the path to the destination.
After it discovers the address of the first router, TRACEROUTE repeats the process with TIME TO LIVE sets to 2. The first router decrement the counter to 1 and forward the datagram. The second counter will decrement the counter to zero, discard the packet and sends band an error message.
Transport Layer Protocols [TCP and UDP]
TCP
At the sending host TCP segments the data into smaller datagrams and adds consecutive sequence numbers. At the receiving host TCP reassembles the datagrams into their proper order. On receiving datagrams, IP passes the datagram to next layer TCP or UDP.
TCP is a connection oriented protocol, meaning that TCP will set up, maintain and tear down a connection. TCP keeps track of the status and state of data passing through it. TCP ensures reliable end to end data transmission. TCP can also multiplex data from different applications and is full duplex.
UDP
UDP is connectionless transport level protocol for applications in layer above. UDP does not do any end to end error checking but uses a checksum in the UDP header.
UDP is used for small data transfers where an error is not a serious problem. It is faster and cheaper.
Eg. RIP, Routing Information Protocol and DNS, Domain Name Service use UDP.
TCP – Transmission Control Protocol
TCP provides a completely reliable, connection-oriented, full-duplex stream transport service.
Services –
1. Connection Orientation
2. Point-TO-Point Communication
3. Complete reliability
4. Full duplex
5. Stream interface – does not guarantee that data will be delivered in the same size piece.
6. Reliable connection Startup – duplicated packet from previous connection will not appear.
7. Graceful Connection Shutdown – guarantees to deliver all data reliably before closing the connection.
End to End Service
TCP is called an end-to-end protocol providing connection directly from application on one computer to another application on a remote computer.
TCP provide virtual connections and rely on IP to carry messages. Each TCP message is encapsulated in an IP datagram and sent across the internet.
Packet loss and retransmission
TCP use timer, Ack and retransmission for reliable data transfer.
Adaptive Retransmission
To avoid excessive retransmission delay
To support various networks with different delay requirements
TCP monitors current delay on each connection and estimate round-trip delay for each active connection by measuring the time needed to receive a response.
TCP generates a sequence of round-trip estimates and uses a statistical function to produce a weighted average.
In addition to a weighted average, TCP keeps an estimated of the variance, and use a linear combination of the estimated mean and variance as a value for retransmission.
TCP adaptive retransmission works well.
Variance helps TCP react quickly when delay increases following a burst of packets.
Weighted average helps TCP reset the retransmission timer if the delay returns to a lower value after a temporary burst.
When delay remains constant, TCP adjusts the retransmission timeout to a value that is slightly longer than the mean round-trip delay.
When delays start to vary, TCP adjusts the retransmission timeout to a value greater than the mean to accommodate peaks.
The goal is to wait long enough to determine that a packet was lost without waiting longer than necessary.
////////
Three Way Handshake
Delayed packets from previous connection arrive and appear to be valid packets on new connection.
To guarantee that connections are established or terminated reliably,
TCP use Synchronization segment (SYN segment) to create a connection and Finish segment (FIN) to close a connection.
Ack sent in each direction are used to guarantee that all data has arrived before the connection is terminated.
TCP retransmits lost SYN or FIN segments. TCP will not open or close a connection until both ends have interacted.
//////
Congestion Control
Congestion => packet-lost => retransmission. Retransmission => increase in input => more congestion
=> more loss.
To avoid the problem TCP use packet loss as a measure of congestion and responds by reducing the rate it transmit.
Whenever a message is lost, TCP begin congestion control. Instead of re-transmitting enough data to fill the window, TCP begins by sending a single packet. If the Ack arrives without additional loss, TCP doubles the amount of data being sent and sends two additional packets.
If Ack arrives for these two, then TCP sends four more and so on. The increase continues until TCP is sending half of the receiver’s advertised window, at which TCP slow down the rate of increase.
By backing off quickly, TCP is able to alleviate congestion and help to avoid congestion collapse.
TCP Segment Format
TCP uses single format for all messages including data, Ack and message to create or terminate a connection.
Troubleshooting [relating Logical topology and the physical network]
Packet management and troubleshooting worked at the lower levels of the protocol stack, Physical, Data Link and Network levels.
An IP network may have many Physical networks using many different types of packet switches interconnected by IP gateways.
The IP gateways are what network managers must control. The IP network management must run at the Application level because of the many possible protocols and types of systems within an IP network.
The management and troubleshooting software must be written without regard to the hardware in the IP network. The same protocol must be able to be used for all gateways. However if the problems are at levels beneath the management and troubleshooting software’s level, the problem cannot be fixed by the IP administrator.
For instance the IP troubleshooter cannot fix a failing operating system or a corrupted routing tale or a system needing to be re-booted. The network people must fix these types of problems.
The most popular tool for TCP/IP management is Simple Network Management Protocol (SNMP).
Each gateway maintains statistics on its operation in a database called Management Information Base (MIB). Typical gateway data includes:
The gateway operating system
Network interface
ARP mappings [address resolution]
IP software
ICMP software [internet control message]
TCP software
UDP software
Some MIB statistic might include
Time since last re-boot
Number of datagrams received
Number of datagrams forwarded
Number of routing failures
Number of datagrams reassembled
Number of datagrams fragmented
The IP routing table
Number of messages received and type of message
Fetch, Store and Trap
SNMP uses only a variation of fetch and store commands. Eg. fetch value from a specific item in MIB or stores a value into MIB.
A trap is recording a particular event, such as too many routing failures and sent a message to network manager.
EE5412 Random_Access_0.doc
Random_Access_0.doc Local Area Network by Gerd E. Keiser
LAN ACCESS - user Share Tx link
simultaneous access – collision
control mechanism to resolve conflict – protocol
General technique - Syn/Asyn TDM
contention (ie random ) access
deterministic (ie. controlled ) access
Random Access scheme- ALOHA (ground based radio packet broadcast network)
CSMA, CSMA/CD, registered insertion
Controlled Access Scheme - centralized - eg. polling - master node determine the right
distributed - eg. token passing, slotted ring
Performance Measurment
1. Throughput characteristic
2. Transfer delay characteristic
Parameter
= mean packet arrival rate
= mean service rate
1/ = average length or service time\,
M/G/1 queue - Poisson distribution packet arrival, general service distribution and one server
S = throughput in bits/sec
R = channel transmission rate in bit/sec
K = packet length in bits
S = [ dimensionless ; normalized to channel transmission rate or bandwidth]
G = offered load
T = total offered traffic
= packets delivered on first attempt + repetition
G =(TK)/R
Random Access method - ALOHA
No control mechanism for contention - collide and retransmit
max. achievable channel utilization - = 18%
Slotted ALOHA - channel divided into time slots
Tx only at the beginning of a time slot eliminate partial overlapping of message
[ie. collide at the beginning ]
channel utilization = 37%
CSMA - carrier sense or listen before talk
further improve the utilization
Pure ALOHA
Transmit immediately whenever there is data to send.
Waits for an acknowledgement from the receiver for a time period equal to one propagation time.
If no acknowledgement - retransmit
tp = packet transmission time or propagation time
= time slot ( ~ service time 1/)
assume packet length fixed
transmission time = 1 time slot
Hence to transmit 1 packet the channel will be busy for 2 x tp sec. ( ie. propagation + transmission) If another user attempt to transmit during the 2 x tp sec, the packets will collide and both packets will be corrupted.
G = no. of packet transmission attempt in one time slot tp.
S = mean no. of successful transmission per time slot tp,
From 5.2 probability of k transmission per time slot
pk = [Gke-G]/[k!]
throughput = p1 (prob. of 1 transmission in one slot )
p0 (prob. of no transmission in the next slot)
S = p1 p0
= G e-G e-G = G e-2G
max. S 0.184 at G = 0.5
ie max channel utilization 18% for pure ALOHA
Slotted Aloha
The channel is divided into time slots which are exactly equal to a packet transmissin time. All users are synchronized to the time slot for packet transmission so that the vulnerable period for collision is limited to one time slot. ( all user attempt to transmit only at the start of the time slot )
The throughput of the channel becomes
S = p1 = G e-G
max. S 0.386 at G = 1
max. channel utilization is twice that of pure Aloha.
fig6.2 comparsion of throughput for pure and slotted ALOHA (infinite no. of users)
If you want to send a test packet, then the
probability of no collision = p0 = e-G
probability of collision = 1- p0 = 1- e-G
Probability of successful transmission requiring k attempts = Pk = e-G(1- e-G)k-1
The expected number of transmission required Pk
= e-G(1- e-G)k-1
= eG
exponential function implies small increase in G will drastically reduce its performance
Stability of Slotted ALOHA ** for detail, refer to text 6.3.3
assume N stations each can hold 1 packet only
assume each station generate new packets according to Poisson distribution with mean transfer probability p<<1 packet per slot when the station is not blocked
assume collided packet retransmitted with probability in every successive time slot until successful [normally wait for a random no. of slots]
Problem is to find the number of stations backlogged.
let state k = k out of N stations backlogged
each station retransmitt with probability
delay or skip the slot with prob. (1- )
ie. total of k retransmission per slot - blocked terminals
(N-k)p new packets per slot - unblocked terminals
let n = new packets from unblocked stations
r = retransmitted packets from blocked stations
[ 0 n N-k; 0 r k ]
Probability of a successful transmission at state k
Pk = P(k=1).P(n=0) + P(n=1).P(k=0)
[ie. (one retransmit)(no new) + (one new)(no retransmit) ]
( collide if more than one )
Pk = [k(1-)k-1][(1-p)N-k] + [(1-)k][(N-k)p(1-p)N-k-1]
= Sout,k
= rate packet leave the system with k backlogged stations
Rate packet enter the system = S = (N-k)p ....…..………………………. (6.15)
For large N and small p Sout,k = k(1-)k-1 e-S + (1-)kSe-S…………...(6.16)
For equilibrium, input = output [ 6.15 = 6.16]
Fig 6.4 shows the equilibrium throughput curve
Fig 6.5 shows the variation of ( ie. retransmit probability)
Decrease in achieve a finite throughput even with heavy backlog. This also results in long retransmission intervals.
----------------------------
Max Throughput for IEEE 802.3
Collisions occur if more than one station sensed idle and transmit simultaneously
Collisions => retransmission => increased delay and reduced throughput
Normal condition for LANs : propagation delay << message length or τ << m
a = τ/m << 1
max throughput : ρmax = λmax m = 1/[1 + ( 1 +2e)a] = 1/[1 + 6.436a]
example :
With bit rate =10mbps, length = 2500m, propagation speed = 2 x 108 m/s
Propagation delay in Bit length = [10 x 106 x 2500 ]/ [2x 108] = 125 bits
If frame length = 72 octets (min) = 72 x 8 bits = 576 bits
a = τ/m = 125 / 576 = 0.217
max throughput , ρmax = 1/[1 + 6.436a] = 0.417
if frame length is 1526 octets (max)
a = 0.010239
max throughput, ρmax = 1/[1 + 6.436a] = 0.938
-------------------------------
LAN ACCESS - user Share Tx link
simultaneous access – collision
control mechanism to resolve conflict – protocol
General technique - Syn/Asyn TDM
contention (ie random ) access
deterministic (ie. controlled ) access
Random Access scheme- ALOHA (ground based radio packet broadcast network)
CSMA, CSMA/CD, registered insertion
Controlled Access Scheme - centralized - eg. polling - master node determine the right
distributed - eg. token passing, slotted ring
Performance Measurment
1. Throughput characteristic
2. Transfer delay characteristic
Parameter
= mean packet arrival rate
= mean service rate
1/ = average length or service time\,
M/G/1 queue - Poisson distribution packet arrival, general service distribution and one server
S = throughput in bits/sec
R = channel transmission rate in bit/sec
K = packet length in bits
S = [ dimensionless ; normalized to channel transmission rate or bandwidth]
G = offered load
T = total offered traffic
= packets delivered on first attempt + repetition
G =(TK)/R
Random Access method - ALOHA
No control mechanism for contention - collide and retransmit
max. achievable channel utilization - = 18%
Slotted ALOHA - channel divided into time slots
Tx only at the beginning of a time slot eliminate partial overlapping of message
[ie. collide at the beginning ]
channel utilization = 37%
CSMA - carrier sense or listen before talk
further improve the utilization
Pure ALOHA
Transmit immediately whenever there is data to send.
Waits for an acknowledgement from the receiver for a time period equal to one propagation time.
If no acknowledgement - retransmit
tp = packet transmission time or propagation time
= time slot ( ~ service time 1/)
assume packet length fixed
transmission time = 1 time slot
Hence to transmit 1 packet the channel will be busy for 2 x tp sec. ( ie. propagation + transmission) If another user attempt to transmit during the 2 x tp sec, the packets will collide and both packets will be corrupted.
G = no. of packet transmission attempt in one time slot tp.
S = mean no. of successful transmission per time slot tp,
From 5.2 probability of k transmission per time slot
pk = [Gke-G]/[k!]
throughput = p1 (prob. of 1 transmission in one slot )
p0 (prob. of no transmission in the next slot)
S = p1 p0
= G e-G e-G = G e-2G
max. S 0.184 at G = 0.5
ie max channel utilization 18% for pure ALOHA
Slotted Aloha
The channel is divided into time slots which are exactly equal to a packet transmissin time. All users are synchronized to the time slot for packet transmission so that the vulnerable period for collision is limited to one time slot. ( all user attempt to transmit only at the start of the time slot )
The throughput of the channel becomes
S = p1 = G e-G
max. S 0.386 at G = 1
max. channel utilization is twice that of pure Aloha.
fig6.2 comparsion of throughput for pure and slotted ALOHA (infinite no. of users)
If you want to send a test packet, then the
probability of no collision = p0 = e-G
probability of collision = 1- p0 = 1- e-G
Probability of successful transmission requiring k attempts = Pk = e-G(1- e-G)k-1
The expected number of transmission required Pk
= e-G(1- e-G)k-1
= eG
exponential function implies small increase in G will drastically reduce its performance
Stability of Slotted ALOHA ** for detail, refer to text 6.3.3
assume N stations each can hold 1 packet only
assume each station generate new packets according to Poisson distribution with mean transfer probability p<<1 packet per slot when the station is not blocked
assume collided packet retransmitted with probability in every successive time slot until successful [normally wait for a random no. of slots]
Problem is to find the number of stations backlogged.
let state k = k out of N stations backlogged
each station retransmitt with probability
delay or skip the slot with prob. (1- )
ie. total of k retransmission per slot - blocked terminals
(N-k)p new packets per slot - unblocked terminals
let n = new packets from unblocked stations
r = retransmitted packets from blocked stations
[ 0 n N-k; 0 r k ]
Probability of a successful transmission at state k
Pk = P(k=1).P(n=0) + P(n=1).P(k=0)
[ie. (one retransmit)(no new) + (one new)(no retransmit) ]
( collide if more than one )
Pk = [k(1-)k-1][(1-p)N-k] + [(1-)k][(N-k)p(1-p)N-k-1]
= Sout,k
= rate packet leave the system with k backlogged stations
Rate packet enter the system = S = (N-k)p ....…..………………………. (6.15)
For large N and small p Sout,k = k(1-)k-1 e-S + (1-)kSe-S…………...(6.16)
For equilibrium, input = output [ 6.15 = 6.16]
Fig 6.4 shows the equilibrium throughput curve
Fig 6.5 shows the variation of ( ie. retransmit probability)
Decrease in achieve a finite throughput even with heavy backlog. This also results in long retransmission intervals.
----------------------------
Max Throughput for IEEE 802.3
Collisions occur if more than one station sensed idle and transmit simultaneously
Collisions => retransmission => increased delay and reduced throughput
Normal condition for LANs : propagation delay << message length or τ << m
a = τ/m << 1
max throughput : ρmax = λmax m = 1/[1 + ( 1 +2e)a] = 1/[1 + 6.436a]
example :
With bit rate =10mbps, length = 2500m, propagation speed = 2 x 108 m/s
Propagation delay in Bit length = [10 x 106 x 2500 ]/ [2x 108] = 125 bits
If frame length = 72 octets (min) = 72 x 8 bits = 576 bits
a = τ/m = 125 / 576 = 0.217
max throughput , ρmax = 1/[1 + 6.436a] = 0.417
if frame length is 1526 octets (max)
a = 0.010239
max throughput, ρmax = 1/[1 + 6.436a] = 0.938
-------------------------------
EE5412 Network Sharing Techniques
EE5412 Network Sharing Techniques
[Med_Access_0.doc]
Time division multiplexing
Statistical time division multiplexing
Frequency division multiplexing
Polling
Bus broadcast sharing - message sense signaling
Ring/loop sharing - extension of time division multiplexing usage is dictated by system protocols
. pre-allocated time slots ; empty time slots - slotted rings; token passing
Network Access Control
Data is send in packets. A packet consists of
Contention-based access methods
Multiple access
. Data packets are send to all terminal stations.
. Terminal station with matching address receive the packet while all other ignore it.
. Collision when more than one terminal send packets to the host simultaneously.
. If the station has not received an ACK from the host within a specific time, it knows that the packet has been destroyed. It then waits for a random period before re-transmitting.
Carrier Sense Multiple Access (CSMA)
. Carrier sense - node check the status of the network before transmission
. Collision - all transmitting nodes will detect a garbled signal on the network.
In CSMA all stations share the same physical medium or channel in a broadband system. All stations have equal priority and must listen to the media to detect if it is idle or not before starting its own transmission.
The problem is that two stations could detect an idle medium and transmit simultaneously. It also takes time for the signal to propagate from one station to another. One station may have transmitted for a time before all other station could detect the transmission. In the mean time, another station may also have started transmission. To solve the problem two schemes are normally used ie. CSMA/CA and CSMA/CD.
Carrier Sense Multiple Access with Collision Detect - CSMA/CD
Listen while transmitting
When the LAN is idle, a station can transmit but at the same time the transmitter also monitor the network for collision. On detecting collision, the transmitter sends out a jamming signal.
Collision consensus enforcement
If the collision only lasts a short time, it is possible that some nodes on the network would not detect it. To avoid this, the colliding nodes transmit a number of bytes of random data (called a jam). This last long enough to propagate to all nodes on the network so that there is no doubt that a collision has taken place.
Back off with out transmitting
The transmitting stations involved in the collision will each stop trying to transmit for random time intervals, before trying again. This is called “backing off”. Delay is computed in each individual node using an algorithm designed to minimize collision. After a fixed number of retries, no further attempts will be made to transmit.
Collisions are much more likely when there is a heavy demand on the network.
Binary exponential backoff
If a second collision is detected the station will double its mean random delay time and backoff again. This is known as binary exponential backoff and a station will attempt to transmit for up to 16 times before reporting an error condition.
n = no of retransmission attempt
k = min(n,10)
The delay is an integer of multiple of slot time. The number of slot times to delay before the n th retransmission attempt is chosen as a uniform distributed random integer r in the range
0 r 2k
Worst Case Collision
B detects collision first, stop sending message and sends a jamming signal.
Jamming signal must reach A before the end of A's frame to ensure A detects the collision. This imposes a minimum packet size with the maximum end to end transmission time.
ie. min. packet transmission time > 2 x max. propagation delay time.
In ethernet running at 10 Mbit/s, minimum packet size = 64 bits
max. end to end transmission time = 44.95 usec
overall distance of coaxial cable < 1.5 km
example: CSMA/CD
The network’s slot time is an important parameter when considering its overall efficiency. From a performance point of view, time spent in the handling of collisions represents channel bandwidth wasted and should be minimized. When a node begins transmission, it is exposed to the risk of a collision occurring for the duration of one slot interval (ie. one round trip time).
Thus the ratio of frame transmission time to slot length should be maximized. The slot time is fixed by physical and electrical considerations. The only way to improve network efficiency is to increase the packet length or to decrease the transmission speed. Reducing speed is not suitable as it would also reduce system throughput.
It has been shown in practice that the efficiency of a heavily loaded Ethernet can vary between 97% with a packet size of 512 bytes to 54% with a 4 byte packet. It is normal to engineer CSMA/CD networks so that they will run with a sustained load of no more than 50% of available capacity. This means that the access method provides reliable transmission with very low delay periods.
CSMA/CA ( Carrier Sense multiple access with collision avoidance )
CSMA/CA attempts to detect a collision before any actual data is transmitted. A station tries to claim the LAN by transmitting a short frame, called a carrier burst. Stations could detect a collision in this initial burst and backoff as normal. Any station seeing a carrier burst will not try to transmit until the end of the subsequent data packet has been seen.
The transmitting station then listens to the LAN to detect any carrier burst coming from remote stations. When it is sure that every station has seen the carrier burst it can transmit the data.
If the first station's carrier burst is swamped by a similar burst from a remote station, by the time it reaches the remote station, the carrier burst going in the opposite direction will have been seen by the first station, which will be in its listening gap. It will then backoff and let the second station transmit. This technique allows very short packets to be used.
example
transmitter listens before send
if cable free, tenasmitter sends initial carier burst
transmitter listen to detect carrier burst
if cable still free then send second carrier burst
short time delay
data packet
time reserved for a response frame from receiver
------------------------------------
CSMA - Carrier Sense Multiple Access
In this scheme, a station that wishes to transmit attempts to avoid collisions by first listening to the medium to determine if another transmission is in progress.
The scheme is further divided into the followings.
Non-persistent CSMA - if medium is idle, then transmit
if busy, then wait random amount of time and re-sense channel
p-persistent CSMA - if medium idle, transmit with probability p
if busy, continue to listen until channel is idle then transmit with probability p
1-persistent CSMA - if medium idle, then transmit
if busy, then continue to listen until channel idle and then transmit immediately
(special case of p-persistent)
When the transmission is unsuccessful, the packet will be retransmitted according to a randomly distributed retransmission delay.
IEEE802.3 [ use 1-persistent ]
refer to ethernet notes for detailed description.
Essentially similar to CSMA/CD. On detecting collision, the station ceases transmission and sends a brief jamming signal. Collisions are detected by monitoring the analog waveform. The waveform is distorted with larger-than-normal voltage amplitude on the cable.
The deference mechanism depends on the non/1/p-persistent being used when the channel is idle or busy.
After the last bit of a frame, the MAC sublayer wait for a period called inter-frame spacing before transmission.
A random delay is used after collision. Stations involved in the collision are not likely to collide on the next transmission. Truncated binary exponential backoff is used in Ethernet. In this method, a station will persist in trying to transmit when there are repeated collisions. After 16 failures, the packet is discarded and the event is reported as error.
Backoff strategy- after n failure, the next delay = r x base backoff time ( ie 2 x end to end propagation delay)
0 £ r £ 2k k = min(n,10)
-------------------------------------
NON CONTENTION ACCESS METHOD - nodes waiting for permission to transmit
Polling
The technique is widespread in traditional wide area networks. It relies a master-slave relationship between a central server and the other stations on the LAN.
The central server maintains a list of the stations and asks each one in turn if it has any transmission to make. If it has, that station is permitted to send one or more packet to the central station.
The station must then wait until it is polled again before it can send any more. Data can also be transmitted from the master to the slave during the same transaction.
Disadvantages - . station has to be polled even it has nothing to send.
. any station to station data transfer has to pass through the server.
. reliability depends on the central server.
Advantages –
. simple to implement requiring no complex hardware or software
. priority polling can easily be implemented
[Med_Access_0.doc]
Time division multiplexing
Statistical time division multiplexing
Frequency division multiplexing
Polling
Bus broadcast sharing - message sense signaling
Ring/loop sharing - extension of time division multiplexing usage is dictated by system protocols
. pre-allocated time slots ; empty time slots - slotted rings; token passing
Network Access Control
Data is send in packets. A packet consists of
Contention-based access methods
Multiple access
. Data packets are send to all terminal stations.
. Terminal station with matching address receive the packet while all other ignore it.
. Collision when more than one terminal send packets to the host simultaneously.
. If the station has not received an ACK from the host within a specific time, it knows that the packet has been destroyed. It then waits for a random period before re-transmitting.
Carrier Sense Multiple Access (CSMA)
. Carrier sense - node check the status of the network before transmission
. Collision - all transmitting nodes will detect a garbled signal on the network.
In CSMA all stations share the same physical medium or channel in a broadband system. All stations have equal priority and must listen to the media to detect if it is idle or not before starting its own transmission.
The problem is that two stations could detect an idle medium and transmit simultaneously. It also takes time for the signal to propagate from one station to another. One station may have transmitted for a time before all other station could detect the transmission. In the mean time, another station may also have started transmission. To solve the problem two schemes are normally used ie. CSMA/CA and CSMA/CD.
Carrier Sense Multiple Access with Collision Detect - CSMA/CD
Listen while transmitting
When the LAN is idle, a station can transmit but at the same time the transmitter also monitor the network for collision. On detecting collision, the transmitter sends out a jamming signal.
Collision consensus enforcement
If the collision only lasts a short time, it is possible that some nodes on the network would not detect it. To avoid this, the colliding nodes transmit a number of bytes of random data (called a jam). This last long enough to propagate to all nodes on the network so that there is no doubt that a collision has taken place.
Back off with out transmitting
The transmitting stations involved in the collision will each stop trying to transmit for random time intervals, before trying again. This is called “backing off”. Delay is computed in each individual node using an algorithm designed to minimize collision. After a fixed number of retries, no further attempts will be made to transmit.
Collisions are much more likely when there is a heavy demand on the network.
Binary exponential backoff
If a second collision is detected the station will double its mean random delay time and backoff again. This is known as binary exponential backoff and a station will attempt to transmit for up to 16 times before reporting an error condition.
n = no of retransmission attempt
k = min(n,10)
The delay is an integer of multiple of slot time. The number of slot times to delay before the n th retransmission attempt is chosen as a uniform distributed random integer r in the range
0 r 2k
Worst Case Collision
B detects collision first, stop sending message and sends a jamming signal.
Jamming signal must reach A before the end of A's frame to ensure A detects the collision. This imposes a minimum packet size with the maximum end to end transmission time.
ie. min. packet transmission time > 2 x max. propagation delay time.
In ethernet running at 10 Mbit/s, minimum packet size = 64 bits
max. end to end transmission time = 44.95 usec
overall distance of coaxial cable < 1.5 km
example: CSMA/CD
The network’s slot time is an important parameter when considering its overall efficiency. From a performance point of view, time spent in the handling of collisions represents channel bandwidth wasted and should be minimized. When a node begins transmission, it is exposed to the risk of a collision occurring for the duration of one slot interval (ie. one round trip time).
Thus the ratio of frame transmission time to slot length should be maximized. The slot time is fixed by physical and electrical considerations. The only way to improve network efficiency is to increase the packet length or to decrease the transmission speed. Reducing speed is not suitable as it would also reduce system throughput.
It has been shown in practice that the efficiency of a heavily loaded Ethernet can vary between 97% with a packet size of 512 bytes to 54% with a 4 byte packet. It is normal to engineer CSMA/CD networks so that they will run with a sustained load of no more than 50% of available capacity. This means that the access method provides reliable transmission with very low delay periods.
CSMA/CA ( Carrier Sense multiple access with collision avoidance )
CSMA/CA attempts to detect a collision before any actual data is transmitted. A station tries to claim the LAN by transmitting a short frame, called a carrier burst. Stations could detect a collision in this initial burst and backoff as normal. Any station seeing a carrier burst will not try to transmit until the end of the subsequent data packet has been seen.
The transmitting station then listens to the LAN to detect any carrier burst coming from remote stations. When it is sure that every station has seen the carrier burst it can transmit the data.
If the first station's carrier burst is swamped by a similar burst from a remote station, by the time it reaches the remote station, the carrier burst going in the opposite direction will have been seen by the first station, which will be in its listening gap. It will then backoff and let the second station transmit. This technique allows very short packets to be used.
example
transmitter listens before send
if cable free, tenasmitter sends initial carier burst
transmitter listen to detect carrier burst
if cable still free then send second carrier burst
short time delay
data packet
time reserved for a response frame from receiver
------------------------------------
CSMA - Carrier Sense Multiple Access
In this scheme, a station that wishes to transmit attempts to avoid collisions by first listening to the medium to determine if another transmission is in progress.
The scheme is further divided into the followings.
Non-persistent CSMA - if medium is idle, then transmit
if busy, then wait random amount of time and re-sense channel
p-persistent CSMA - if medium idle, transmit with probability p
if busy, continue to listen until channel is idle then transmit with probability p
1-persistent CSMA - if medium idle, then transmit
if busy, then continue to listen until channel idle and then transmit immediately
(special case of p-persistent)
When the transmission is unsuccessful, the packet will be retransmitted according to a randomly distributed retransmission delay.
IEEE802.3 [ use 1-persistent ]
refer to ethernet notes for detailed description.
Essentially similar to CSMA/CD. On detecting collision, the station ceases transmission and sends a brief jamming signal. Collisions are detected by monitoring the analog waveform. The waveform is distorted with larger-than-normal voltage amplitude on the cable.
The deference mechanism depends on the non/1/p-persistent being used when the channel is idle or busy.
After the last bit of a frame, the MAC sublayer wait for a period called inter-frame spacing before transmission.
A random delay is used after collision. Stations involved in the collision are not likely to collide on the next transmission. Truncated binary exponential backoff is used in Ethernet. In this method, a station will persist in trying to transmit when there are repeated collisions. After 16 failures, the packet is discarded and the event is reported as error.
Backoff strategy- after n failure, the next delay = r x base backoff time ( ie 2 x end to end propagation delay)
0 £ r £ 2k k = min(n,10)
-------------------------------------
NON CONTENTION ACCESS METHOD - nodes waiting for permission to transmit
Polling
The technique is widespread in traditional wide area networks. It relies a master-slave relationship between a central server and the other stations on the LAN.
The central server maintains a list of the stations and asks each one in turn if it has any transmission to make. If it has, that station is permitted to send one or more packet to the central station.
The station must then wait until it is polled again before it can send any more. Data can also be transmitted from the master to the slave during the same transaction.
Disadvantages - . station has to be polled even it has nothing to send.
. any station to station data transfer has to pass through the server.
. reliability depends on the central server.
Advantages –
. simple to implement requiring no complex hardware or software
. priority polling can easily be implemented
EE5412 Telecommunications Network
EE5412 LAN
LanQA0a.doc
-----------------
Difference in throughput performance between the pure ALOHA and the slotted ALOHA LAN access scheme.
Assume packet length equal to propagation delay equal to one slot time.
The best channel utilization that can be achieved is around 18% for pure ALOHA and 36% for slotted ALOHA. In pure ALOHA the vulnerable period for collision last for two times the slot time. It is the vulnerable period that is largely affect the throughput performance of the network. With slotted ALOHA, station only transmit at the beginning of a timeslot and the vulnerable is reduced. With assumption on packet length and propagation delay, the performance of slotted ALOHA is twice that of the pure ALOHA.
--------------------------
Back-off mechanism used in IEEE802.3 and its effect on performance and stability
Mechanism that maintains the LAN throughput at various loads [light load and heavy load] to the network.
Truncated Binary exponential back-off is used in IEEE802.3.
Packets are transmitted into the network in random. On detecting collision, the transmitting station will stop transmission for a random time interval before trying to transmit again. Delay is computed in each individual node using an algorithm designed to minimize collision. Packet is retransmitted after the delay. If a second collision is detected, the station will double its mean random delay time and back-off again. This is called binary exponential back-off. The station will attempt to transmit for up to 16 times before reporting an error and give up retransmission.
n= number of retransmission attempt
k= min(n,10)
The delay is an integer of multiple of slot time. The number of slot times to delay before the n th retransmission is chosen as a uniform distributed random integer r.
0 <= r <= 2k
Re-transmission has the effect of increasing the input load to the network. As the load increase, the probability of packet collision also increases. At heavy load the chance of successful transmission is small resulting in very small throughput and very high re-transmission. The system will lockup and become unstable.
Mechanism maintaining the LAN throughput at various load
The binary exponential back-off algorithm has the effect of keeping the system stable.
Under light load, delay time is small and re-transmission does not have any effect.
As load increase, probability of collision increase, number of retransmission will also increase. Backoff delay time will also increase exponentially.
Heavy load -
The increase in backoff time has the effect of reducing the input to the network. This will in turn reduce the probability of collision. The net effect is to maintain the network throughput and give a chance to the network to clear the backlog.
Since excessive input causing overload is only a temporary phenomenon, the network will recover and maintain its stability.
--------------------------------
Maximum throughput that can be achieved from a pure ALOHA channel
Ans: 0.184
---------------
Meaning of the following terms associated with a CSMA/CD bus network:
a. Slot time
b. Jam sequence
c. Truncated binary exponential backoff
Slot Time -
a. Due to signal propagation delay of the transmission medium, there is a small but finite time interval between a DTE connected to one end of the transmission medium starting to transmit a frame and another DTE connected to the other end receiving the signal. This is known as worst case propagation delay time of the cable and during this interval two DTEs may initiate a transmission on the assumption that the transmission medium is idle.
In the worst case, the corrupted signal will take the same time interval to propagate back to the first DTE before it detects the collision. This total time, twice the worst-case propagation delay, is known as the slot time and is represented in terms of bits at the particular bit rate being used. With thick-wire coaxial cable the maximum cable length is limited to 2.5km and at 10 Mbps, the slot time is 512 bits. This means that a DTE must transmit a minimum of 512 bits before it knows whether a collision has occurred or not.
Jam sequence-
The actual period of collision can be very short.
To ensure the two (or more) DTEs involved in a collision detect its occurrence, it is necessary for both stations to continue transmitting for a short time interval after first detecting the collision has occurred. On detecting a collision, therefore, each DTE sends a further random bit pattern known as the jam sequence.
Truncated Binary exponential backoff -
On detecting a collision, the two (or more) DTEs involved will try to retransmit the frames that have been corrupted. Hence to avoid both DTEs again starting at the same time, each DTE waits a random time internal before attempting to transmit its frame. This is known as the random backoff interval.
In the event of a second collision occurring, the previous (random) time interval is doubled before attempting again. This procedure then repeats for each subsequent collision up to a maximum number of tries before abandons trying to transmit the frame.
---------------------------
Operation of p-persistent CSMA protocol
----------------------------
Modification made to CSMA protocol in order to improve its performance
Collision detection – After sending a packet, the sending station checks if there is any collision. If yes, it can send a jamming signal to notify other stations.
Collision avoidance – mechanism to claim the channel before transmission.
------------------------------
Even though the Slotted_ALOHA protocol is more efficient than Pure-ALOHA, it also has some disadvantages. Following are the problems.
Slotted-Aloha requires that common clocks be established at each station. The clocks should be synchronized to send traffic at specific periods. Slotted-Aloha works with a time division multiplexing slot. The slot is fixed in length. If user does not use the slot, the slot becomes empty and channel capacity will be wasted.
----------------------
Two parameters that describe the performance of a LAN -
The key performance considerations for a LAN are the throughput or channel utilization and the delay characteristics. Throughput is a measure of the successful traffic or the total rate of data being transmitted between nodes.
This is expressed in terms of the offered load which is the actual message load or traffic demand presented to the network. Delay is a measure of the average interval of time between when a packet is ready for transmission from a source station until its successful reception at the destination.
------------------------
IEEE802.3 standard access scheme with the aid of a flow chart
-----------------
Reason for collision in random access scheme
Due to signal propagation delay through the network, carrier signal can not be detected by the host before packet transmission and hence collision.
-----------------
LanQA0a.doc
-----------------
Difference in throughput performance between the pure ALOHA and the slotted ALOHA LAN access scheme.
Assume packet length equal to propagation delay equal to one slot time.
The best channel utilization that can be achieved is around 18% for pure ALOHA and 36% for slotted ALOHA. In pure ALOHA the vulnerable period for collision last for two times the slot time. It is the vulnerable period that is largely affect the throughput performance of the network. With slotted ALOHA, station only transmit at the beginning of a timeslot and the vulnerable is reduced. With assumption on packet length and propagation delay, the performance of slotted ALOHA is twice that of the pure ALOHA.
--------------------------
Back-off mechanism used in IEEE802.3 and its effect on performance and stability
Mechanism that maintains the LAN throughput at various loads [light load and heavy load] to the network.
Truncated Binary exponential back-off is used in IEEE802.3.
Packets are transmitted into the network in random. On detecting collision, the transmitting station will stop transmission for a random time interval before trying to transmit again. Delay is computed in each individual node using an algorithm designed to minimize collision. Packet is retransmitted after the delay. If a second collision is detected, the station will double its mean random delay time and back-off again. This is called binary exponential back-off. The station will attempt to transmit for up to 16 times before reporting an error and give up retransmission.
n= number of retransmission attempt
k= min(n,10)
The delay is an integer of multiple of slot time. The number of slot times to delay before the n th retransmission is chosen as a uniform distributed random integer r.
0 <= r <= 2k
Re-transmission has the effect of increasing the input load to the network. As the load increase, the probability of packet collision also increases. At heavy load the chance of successful transmission is small resulting in very small throughput and very high re-transmission. The system will lockup and become unstable.
Mechanism maintaining the LAN throughput at various load
The binary exponential back-off algorithm has the effect of keeping the system stable.
Under light load, delay time is small and re-transmission does not have any effect.
As load increase, probability of collision increase, number of retransmission will also increase. Backoff delay time will also increase exponentially.
Heavy load -
The increase in backoff time has the effect of reducing the input to the network. This will in turn reduce the probability of collision. The net effect is to maintain the network throughput and give a chance to the network to clear the backlog.
Since excessive input causing overload is only a temporary phenomenon, the network will recover and maintain its stability.
--------------------------------
Maximum throughput that can be achieved from a pure ALOHA channel
Ans: 0.184
---------------
Meaning of the following terms associated with a CSMA/CD bus network:
a. Slot time
b. Jam sequence
c. Truncated binary exponential backoff
Slot Time -
a. Due to signal propagation delay of the transmission medium, there is a small but finite time interval between a DTE connected to one end of the transmission medium starting to transmit a frame and another DTE connected to the other end receiving the signal. This is known as worst case propagation delay time of the cable and during this interval two DTEs may initiate a transmission on the assumption that the transmission medium is idle.
In the worst case, the corrupted signal will take the same time interval to propagate back to the first DTE before it detects the collision. This total time, twice the worst-case propagation delay, is known as the slot time and is represented in terms of bits at the particular bit rate being used. With thick-wire coaxial cable the maximum cable length is limited to 2.5km and at 10 Mbps, the slot time is 512 bits. This means that a DTE must transmit a minimum of 512 bits before it knows whether a collision has occurred or not.
Jam sequence-
The actual period of collision can be very short.
To ensure the two (or more) DTEs involved in a collision detect its occurrence, it is necessary for both stations to continue transmitting for a short time interval after first detecting the collision has occurred. On detecting a collision, therefore, each DTE sends a further random bit pattern known as the jam sequence.
Truncated Binary exponential backoff -
On detecting a collision, the two (or more) DTEs involved will try to retransmit the frames that have been corrupted. Hence to avoid both DTEs again starting at the same time, each DTE waits a random time internal before attempting to transmit its frame. This is known as the random backoff interval.
In the event of a second collision occurring, the previous (random) time interval is doubled before attempting again. This procedure then repeats for each subsequent collision up to a maximum number of tries before abandons trying to transmit the frame.
---------------------------
Operation of p-persistent CSMA protocol
----------------------------
Modification made to CSMA protocol in order to improve its performance
Collision detection – After sending a packet, the sending station checks if there is any collision. If yes, it can send a jamming signal to notify other stations.
Collision avoidance – mechanism to claim the channel before transmission.
------------------------------
Even though the Slotted_ALOHA protocol is more efficient than Pure-ALOHA, it also has some disadvantages. Following are the problems.
Slotted-Aloha requires that common clocks be established at each station. The clocks should be synchronized to send traffic at specific periods. Slotted-Aloha works with a time division multiplexing slot. The slot is fixed in length. If user does not use the slot, the slot becomes empty and channel capacity will be wasted.
----------------------
Two parameters that describe the performance of a LAN -
The key performance considerations for a LAN are the throughput or channel utilization and the delay characteristics. Throughput is a measure of the successful traffic or the total rate of data being transmitted between nodes.
This is expressed in terms of the offered load which is the actual message load or traffic demand presented to the network. Delay is a measure of the average interval of time between when a packet is ready for transmission from a source station until its successful reception at the destination.
------------------------
IEEE802.3 standard access scheme with the aid of a flow chart
-----------------
Reason for collision in random access scheme
Due to signal propagation delay through the network, carrier signal can not be detected by the host before packet transmission and hence collision.
-----------------
Abonnieren
Posts (Atom)