HW2 Solution - Assignments PDF

Preview

Summary

Assignments...

Description

San Jose State University ELECTRICAL ENGINEERING DEPARTMENT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! EE""281,"Computer"Networks" Homework 2! Solution(

Problem 1

Show!the!NRZ,!Manchester,!and!NRZI!encoding!for!the!bit!pattern!shown!in!the!figure!below.! Assume!that!NRZI!signal!starts!out!low.!!

Solution" Answer waveforms are sketch below: Recall: 1.! NRZ: maps 5 V to 1 and 0V to 0 2.! Manchester: 1 is encoded by transition from High to low, while 0 is encoded by transition from low to high 3.! NRZI: Makes a transition from the current signal to encode 1 and stay at current position to encode 0 4.! Note: changes at midways of 1 is favorable technique as it maintains clock synchronizations between SN and RS

!

1

! ! Problem"2"" ! Show!the!4B/5B!encoding,!and!resulting!NRZI!signal!for!the!following!bit!sequence:! ! 1110!0101!0000!0011!! ! Solution!! Use!the!table!to!encode!4B/5B!! ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!4B!! !!! ! ! ! ! !!5B! ! !!!!!!!!!!!!1110!! ! ! ! ! !!!!!!!!!!!!11100! ! ! !!!!!!!!!!!!0101!!!!!!!!!!!!!!!!!!!!!!!! ! ! !!!!!!!!!!!!01011! ! ! !!!!!!!!!!!!0000!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!11110! ! ! !!!!!!!!!!!!0011!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!10101! ! ! The!4B/5B!encoding!for!the!sequence!is!! 11100!01011!11110!10101!! ! The!resulting!NRZI!signal!is:!! !

!

2

! Problem"3"" " Show!the!4B/5B!encoding,!and!resulting!NRZI!signal!for!the!following!bit!sequence:! 1101!1110!1010!1101!1011!1110!1110!1111! ! Solution:!! " Similar!to!previous!problem!,!for!message:! 1101!!1110!!1010!!1101!!1011!!1110!!1110!!1111! ! 4B/5B:! 11011!!11100!!10110!!11011!!10111!!11100!!11100!!11101! The!resulting!NRZI!signal!is!!

Problem 4

Assuming!the!framing!protocol!that!uses!bit!stuffing,!show!the!bit!sequence!!!transmitted!over! the!link!when!the!frame!contains!following!bit!sequence:! ! 110101111101011111101011111110!! Mark!the!stuffed!bit! ! !

!

3

Solution:! ! Bit!Stuffing!every!after!5!consecutive!one!! ! !!!!!!!!!!!!!!The!marked!stuff!bits!are!marked!in!RED!color!! !!!!!!!!!!!!!!!1!1!0!1!0!1!1!1!1!1!0!1!0!1!1!1!1!1!0!1!0!1!0!1!1!1!1!1!0!1!1!0! Problem"5"" " Suppose!the!following!sequence!of!bits!arrives!over!a!link:! 1101011111010111110010111110110! ! Show!the!resulting!frame!after!any!stuffed!bits!have!been!removed.!Indicate!any!errors!that! might!have!been!introduced!into!the!frame! ! Solution:!! ! Every!O!after!five!consecutive!1’s!are!the!stuffed!bits!! ! The!stuffed!bits!are!shown!below:! ! 1!1!0!1!0!1!1!1!1!1!0!1!0!1!1!1!1!1!0!0!1!0!1!1!1!1!1!0!1!1!0! ! The!resulting!bits!are!1101011111101111101011111110! Problem 6

Suppose!that!you!want!to!send!data!using!BISYNC!framing!protocol,!and!the!last!2!bytes!of!your! data!are!DLE!and!ETX.!What!sequence!of!bytes!would!be!transmitted!immediately!prior!to!CRC?! ! Solution:! Recall:!! with!BISYNC!if!ETX!appears!!in!data!portion,!then!sender!signals!!the!receiver!by!stuffing! an!extra!DLE!character!BEFORE!and!ETX!(some!sort!of!waning),!also!if!DLE!itself!appears!in!the! data!portion,!then!!it!is!stuffed!by!another!DLE!as!well:! !!! Since!the!last!2!bytes!of!the!data!are!DLE!and!ETX,!the!sequence!of!bytes!that!!!!would!be!send! immediately!prior!to!CRC!is!! ! !…….,!DLE,!DLE,!DLE,!ETX,!ETX!! !! ETX!(End!of!text!Character)!DLE!(Data!link!escape)!! " !

4

Problem"7"" ! For!each!of!the!following!framing!protocols,!give!an!example!of!byte/!bit!sequence!that!should! never!appear!in!transmission?!! (A)!!BISYNC! (B)!HDLC! ! Solution:!! ! A)!BISYNC! ! P!DLE!Y;!where!P!can!take!any!value!in!addition!to!DLE!and!Y!can!be!anything!except!DLE!or!ETX! ! B)!HDLC!! ! Bit!sequence!that!can!never!appear!on!the!transmission!is!0111!1111! Problem"8" "

Suppose!that!one!byte!in!buffer!covered!by!the!internet!checksum!algorithm!needs!to!be! decremented!(eg:!header!hop!count!field).!Give!an!algortihm!to!compute!revised!checksum! without!rescanning!the!entire!buffer.!The!algorithm!should!be!considered!whether!the!byte!in! question!is!low!order!or!high!order.! ! Solution:!! ! Switches!or!routers!when!processing!an!!arriving!!packet,!they!commonly!!modify!some!of!its! hearder!fields!before!retransmitting!it.!For!instance,!routers!!decrement!!TTL!field!of!IP`packet! (as!we!will!discuss!it!in!the!next!chapters)!!by!1!before!frowrading!it!to!the!next!hop.!For!this! problem!!and,!for!simplicity,!let!us!!assume!that!!1’s!complement!sum!is!performed!over!4`bit! words!(m=4!in!classnotes).!As!requested!by!the!problem,!let!us!distinguish!2!cases!(a)!when! least!significant!bit!!of!a!byte!is!decremented!,!and!(b)!the!most!significant!bit!is!decremented.! ! Case"(a)""" To!help!deduce!the!modification!on!the!checksum,!consider!the!example!! !!!!!!!!!!M1"="1001"0110"1110"0111!!!(2!bytes,!with!m=4)! then!the!check!sum!of!M1,!!S1=6!!!!!!(1’s!complement!of!9+6+14+7)! When!!decrementing!M1!by!one!we!got!the!message!M2!with!its!check!sum!S2,!as!below:!!! !!!!!!!!!!!!M2"="1001"0110"1110"0110""","S2=5" " Comparing!S2!to!S1,!it!can!easily!!generalized:!If!we!decrement!a!low`order!byte!by!1!in!the!data,! we!decrement!the!sum!by!1"as!well.! " "

!

5

Case(b)" ! Let!M3!!is!the!message!M1!!with!its!most!significant!bit!of!its!byte!!was!decremented!by:!! !!!!!!!!!!!!!!!!!!!M3"="1001"0110"0110"0111""","S3=13""(which"is"E2"in""1’s"complement,"that"S1E8=E2")" Hence!for!this!case,!(we!can!try!it!for!other!values!as!well!)!!!If!we!decrement!a!high!order!byte! by!1!we!must!decrement!the!old!checksum!by!8"(23).! Problem 9

Suppose!we!want!to!transmit!the!message!1011!0010!0100!1011!and!protect!it!from!errors! using!the!CRC`8!polynomial!X8+X2+X+1.! (a)!Use!polynomial!long!division!to!determine!the!message!that!should!be!transmitted.!! (b)!Suppose!that!left!most!bit!of!the!message!is!inverted!due!to!noise!on!the!transmission!link.! What!is!the!result!of!the!receiver’s!CRC!calculation?!How!does!the!receiver!know!that!an!error! has!occurred?!

Solution: (a)! ! M(x)=!1011!0010!0100!1011!! C(x)=!x8+x2+x1+1=!100000111! M’(x)=!1011!0010!0100!1011!00000000!

!

6

! !

Remainder!gives!information!about!CRC.! The!transmitted!bits!are:!1011001001001011010010011! ! (b)! ! ! After!the!left!most!bit!is!inverted!! M(X)=!0011001001001011! C(X)=!x8+x2+x1+1=!100000111! M’(x)=!1011!0010!0100!1011!00000000! ! !

!

7

! ! The!remainder!is!not!zero.!So!the!CRC!at!the!receiver!side!knows!that!there!is!an!error.! ! !

!

8...