8/18/2019 ECE544Lec215b.ppt

1/74

ECE544: Communication Networks-IISpring 2015

D. Raychaudhuri

Lecture II

Includes teaching materials from L. Peterson, J. Kurose

8/18/2019 ECE544Lec215b.ppt

2/74

Todays !ecture• Recap of network architecture &

top-down design– architecture paper discussion

• Shared media (!"# protoco$s– %thernet

– oken ring

– I%%% ').**

8/18/2019 ECE544Lec215b.ppt

3/74

!ink !ayer: Introduction• Some terminology:

– hu+,repeater ($ayer *# +ridge,L! switch ($ayer )#router ($ayer /# host ($ayers *-/ 0 app#

– Links are communication channe$s that connectad1acent nodes a$ong communication path (point-to-point shared wired wire$ess#

– Layer-) frame2 encapsu$ates pay$oad,datagram,I3packet,ser4ice unit

Router 

Switch

Link 

Host

Lin

k 

LAN

LAN !

Switch

Link 

Host

8/18/2019 ECE544Lec215b.ppt

4/74

!ink !ayer Ser"ices

• Data-link layer: transfer datagram fromone node to ad1acent node o4er a $ink– 5raming2 encapsu$ate datagram into frame

adding header trai$er.

• Identify what set of +its constitute a frame that isdetermining the +eginning and the end of a frame

– channe$ access if shared medium• !" addresses used in frame headers to identify

source destination• di6erent from I3 address7

– Re$ia+$e de$i4ery +etween ad1acent nodes• %rror detection• %rror reco4ery2 forward error correction code

retransmission (!R8#

8/18/2019 ECE544Lec215b.ppt

5/74

!ink !ayer Communication• Link $ayer imp$emented in adaptor (I"# and dri4er (%thernet

card 9L! card#• Sending side2 encapsu$ates higher $ayer pay$oad in a frame adds

error checking +its :ow contro$ etc.• Recei4ing side2 error detection :ow contro$ e;tracts pay$oad

passes to the recei4ing node

"P#

"ache

$emor%

"ontrol status

register 

&us

interface

Link 

interface

Host

 NI"

I'(

 )us

 Network 

*atagram

+rame

Adator 

Sending

node

*atagram

+rame

Adator 

Rec-

node

Link la%er rotocol

8/18/2019 ECE544Lec215b.ppt

6/74

!ayer 2 "s# !ayer $

• Layer ) switching–

8/18/2019 ECE544Lec215b.ppt

7/74

• Link Layer echni?ues

– %ncoding (more 3hysica$ Layer stu6#– 5raming & 333 3rotoco$

– %rror Detection & "orrection

– !R8

• Se$f study topics (see "h) & s$ides#

8/18/2019 ECE544Lec215b.ppt

8/74

%inary Encoding

•

8/18/2019 ECE544Lec215b.ppt

9/74

&anc'ester Encoding• anchester %ncoding2 R@Cencode data ER c$ock

– "$ock cyc$e (a $ow,high pair# A ) ; signa$ inter4a$–

8/18/2019 ECE544Lec215b.ppt

10/74

(oint-to-(oint )ata !ink (rotoco*• wo types of $inks

– point-to-point $ink (easier than +roadcast $ink#• one sender one recei4er on the $ink E edia

!ccess "ontro$

• no need for e;p$icit !" addressing

• e.g. dia$up $ink ISD $ine

– igh $e4e$ data $ink contro$#2 +it-oriented

PPP$odem

8/18/2019 ECE544Lec215b.ppt

11/74

((( +unctions• Framing: encapsu$ation of network-$ayer datagram in

data $ink frame– Identify what set of +its constitute a frame that is

determining the +eginning and the end of a frame• carry data of any network $ayer protoco$ (not 1ust I3# at

same time– a+i$ity to demu$tip$e; upwards

• bit transparency: must carry any +it pattern in thedata =e$d

• error detection (no correction#• connection liveness: detect signa$ $ink fai$ure to

network $ayer• network layer address negotiation: endpoint can

$earn,con=gure each otherGs network address• 333

– no error correction,reco4ery– no :ow contro$– out of order de$i4ery EH

– no need to support mu$tipoint $inks (e.g. po$$ing#

8/18/2019 ECE544Lec215b.ppt

12/74

((( )ata +rame

• 5$ag2 de$imiter (framing#• !ddress2• "ontro$2• 3rotoco$2 upper $ayer protoco$ to which frame carried (e.g. I3#

• Info2 upper $ayer data• "heck2 "R"

 rotocol info "R"

flag

(ctet0

controladdress

or ! -aria)le ! or 1

8/18/2019 ECE544Lec215b.ppt

13/74

%yte Stu,,

• data transparencyJre?uirement2 data =e$dmust +e a$$owed to inc$ude :ag patternK******B– 82 is recei4ed K******B data or :ag

• Sender2 adds (stu6sJ# e;tra K ******B+yte after each K ******B data +yte

• Recei4er2– two ****** +ytes in a row2 discard =rst +yte

continue data reception

– sing$e ******2 :ag +yte

8/18/2019 ECE544Lec215b.ppt

14/74

((( !ink Contro* (rotoco* !C(.

•

8/18/2019 ECE544Lec215b.ppt

15/74

/ig'-!e"e* )ata !ink Contro* /)!C. 

•

8/18/2019 ECE544Lec215b.ppt

16/74

Error )etection• %D"A %rror Detection and "orrection +its (redundancy#• D A Data protected +y error checking may inc$ude header =e$ds•  %rror detection not *P re$ia+$e7

–  protoco$ may miss some errors +ut rare$y–  $arger %D" =e$d yie$ds +etter detection and correction

8/18/2019 ECE544Lec215b.ppt

17/74

(arity C'ecking• Sing$e

8/18/2019 ECE544Lec215b.ppt

18/74

Internet C'ecksum

Sender2• treat segment

contents as se?uence

of *Q-+it integers• checksum2 addition(*Gs comp$ementsum# of segmentcontents and takethe ones comp$ementof the resu$t

• sender putschecksum 4a$ue intoD3 checksum =e$d

Recei4er2• compute checksum

of recei4ed segment

• check if computedchecksum e?ua$schecksum =e$d 4a$ue2– E -error detected–  %S -no error

detected.

8/18/2019 ECE544Lec215b.ppt

19/74

Cyc*ic edundancy C'eck CC.

• ! (n0*#-+it message can +e represented as apo$ynomia$ of degree n. 5or e;amp$e– A ****U– (# A V 0 W 0 / 0

• "hoose k0* +it pattern (di4isor# "(# a po$yn of degreek

• goa$2 get k "R" +its  such that– 3AKB e;act$y di4isi+$e +y " (modu$o )#– recei4er knows " di4ides KB +y ". If non-Mero

remainder2 error detected7– can detect a$$ +urst errors $ess than k0* +its

$0 data )its to )e sent 50 "R"

n )itsk )its

$ 6 !k  7(R R 

8/18/2019 ECE544Lec215b.ppt

20/74

CC Eamp*e

• Toa$2 design 3(# such that itis e;act$y di4isi+$e +y "(#

•  (# A (# k (add k MeroGs to

the end of the message#

89:9:;

 X C  X T remainder  R   =

• Su+tract the remainder from (# to get 3(#.

– 3(# is now e;act$y di4isi+$e +y "(#.

• "orresponding to the comp$etetransmitted message

(Remem+er – a$$ addition,su+tract use modu$o-)arithmetic#

8/18/2019 ECE544Lec215b.ppt

21/74

utomatic epeat re3uest3.• Stop-and-wait !R8

–  ransmit a frame and wait for acknow$edge

– If positi4e acknow$edge (!"H# from recei4er send ne;t frame– If !"H does not arri4e after a certain period of time (imeout# retransmits theframe

– Simp$e $ow eNciency

• To-+ack- !R8–  ransmit frames continuous$y no waiting–  he recei4er on$y acks the highest-num+ered frames recei4ed in se?uence

– !"H comes +ack after a round-trip de$ay– If timeout the sender retransmits the frames that are not acked and -*

succeeding frames that were transmitted during the round-trip de$ay (frames transmitted during a round-trip de$ay#

– eed +u6er at transmitter does not ha4e to +u6er the frames at the recei4er– moderate eNciency and comp$e;ity. Less eNcient when the round-trip de$ay

is $arge and data transmission rate is high

• Se$ecti4e-repeat–  ransmit continuous$y no waiting–  he recei4er acks a$$ successfu$$y recei4ed frames–  he sender on$y retransmits (repeats# the unacked frames when their timers

e;pire– ost eNcient +ut most comp$e; +u6er needed at +oth transmitter and

recei4er need per frame timer

8/18/2019 ECE544Lec215b.ppt

22/74

S*iding indow

• Re$ia+$e de$i4ery2 retransmission

• Erdered de$i4ery2 preser4e the order in

which the frames are transmitted– Recei4er does not pass a$ong (+u6er# out-of-order frames

• 5$ow contro$2 feed+ack mechanism +y which

the recei4er is a+$e to thrott$e the sender– Inform the sender of how much frames therecei4er has room to recei4e

8/18/2019 ECE544Lec215b.ppt

23/74

S*iding indow Cont.• Send window siMe (S9S#2 the upper +ound on the

num+er of unacked frames that the sender cantransmit– set according to the round-trip de$ay to keep the pipe fu$$

(reca$$2 +andwidth ; de$ay product represents the amountof data that cou$d +e in transit#

• L!R2 the se?uence X of the $ast ack recei4ed

• L5S2 the se?uence X of the $ast frame sent• Recei4er window siMe (R9S#2 the upper +ound on

the num+er of out-of-order frames that therecei4er is wi$$ing to accept

• L!52 the se?uence X of the $argest accepta+$e

frame• L5R2 the se?uence X of the $ast frame recei4ed• Se?umo!ck2 the $argest se?uence X not yet

acked such that all frames with se? X KASe?numo!ck ha4e +een recei4ed

8/18/2019 ECE544Lec215b.ppt

24/74

S*iding indow

• L5S-L!RKAS9S L!5-L5RKAR9S

• 5inite Se?. X wraps around2– S9S K (a;Se?um0*#,) when R9SAS9S to distinguish

+etween di6erent incarnations of the same se?. X

! < 1 = 4 > 3 ? < 1 = 4 > 3 ? !

! < 1 = 4 > 3 ? < 1 = 4 > 3 ? !

Sender 

Recei-er 

Ack Ack !

@rror 

Ack !Ack <

Ack ! Ack !Ack 1 Ack =

Ack 4

SS

LAR  L+S

RSL+R  LA+

Se2NumBoAck 

8/18/2019 ECE544Lec215b.ppt

25/74

S'ared &edia Networks

• !" (medium access contro$#– !LE>! S$otted !LE>!– "S!,"D "S!,"!– oken Ring– D! Dynamic D!– 5D! "D!

• L! echno$ogies– I%%% ')./ %thernet– I%%% ').O oken Ring– I%%% ').** 9ire$ess L!

8/18/2019 ECE544Lec215b.ppt

26/74

&edium ccess Su*ayer

• edium access contro$ (!"#su+$ayer is not re$e4ant onpoint-to-point $inks

•  he !" su+$ayer is on$yused in +roadcast or shared

medium,channe$ networks• !$$ communication entities

shareJ a common channe$– 9ired networks2 %thernet L!

– 9ire$ess & o+i$e etworks2

Sate$$ite "e$$u$ar 9ire$ess L!

Application

Presentation

Session

Transport

End host

Network

Data link

Physical

LL"$A"

Physical

Subnet

IP

TCP/UDP

Applications

8/18/2019 ECE544Lec215b.ppt

27/74

&edia ccess (rotoco*

• Shared +roadcast channe$– two or more simu$taneous transmissions +y nodes2

interference• "o$$ision if node recei4es two or more signa$s at the same

time

• !" protoco$– Determines how nodes share channe$ i.e. determine

when node can transmit

• Ideally, if +roadcast channe$ of rate R +ps– 9hen one node wants to transmit it can send at rate R.

– 9hen nodes want to transmit each can send ata4erage rate R, (fairness#

8/18/2019 ECE544Lec215b.ppt

28/74

&C C*assi,ication

• "hanne$ 3artitioning– di4ide channe$ into sma$$er piecesJ (time s$ots fre?uency

code#– a$$ocate piece to node for e;c$usi4e use

•  D! "D! 5D!

• Random !ccess– channe$ not di4ided

• 9hen node has frame to send transmit with the tota$ channe$

+andwidth– o coordination +etween nodes contro$ is comp$ete$ydistri+uted

– two or more nodes transmit simu$taneous$y Yco$$isionJ– random access !" protoco$ shou$d specify2

• how to detect co$$isions• how to reco4er from co$$isions (e.g. 4ia de$ayed retransmissions#

• %;amp$es2 !LE>! S$otted !LE>! "S!,"D "S!,"!• aking turnsJ

– odes take turns•  oken ring

• >y+rid– "om+ine two or more techni?ues together

8/18/2019 ECE544Lec215b.ppt

29/74

8/18/2019 ECE544Lec215b.ppt

30/74

*o'a *gorit'm• !$oha !$gorithm2

– odes transmit immediate$y whene4er they ha4e a frame tosend

– o synchroniMation among nodes

• If co$$ision retransmit after random de$ay

– random de$ay pre4ents the same frames fromco$$iding o4er and o4er again

• co$$ision window or 4u$nera+$e periodJ2

– frame sent at t co$$ides with other frames sent in [t-*t0*\

8/18/2019 ECE544Lec215b.ppt

31/74

(ure *o'a e,,iciency

• !ssume that the aggregate frame arri4a$ is 3oisson 3rocess

• 3 [k arri4a$s in a time-inter4a$\ A

• T2 the mean num+er of aggregate arri4a$s (a$$ nodes in network# in

the time inter4a$

• time-inter4a$ A one frame transmission time

• "onditiona$ successfu$ pro+a+i$ity for one frame transmission

attempt is

–  3 A 3 [ other attempts in ) time-inter4a$s\ Ae-2G

•  he pro+a+i$ity of successfu$ transmission

– S A T3 A Te-)T

• S is optimum at TA*,)

• SA*,)e A .*'W

Ck 

Gek G−

8/18/2019 ECE544Lec215b.ppt

32/74

S*otted *o'a

• !ssumptions– a$$ frames same siMe– time is di4ided into e?ua$ siMe

s$ots time to transmit * frame– nodes start to transmit frames

on$y at +eginning of s$ots– nodes are synchroniMed– if ) or more nodes transmit in

s$ot detect co$$ision

– 5eed+ack channe$ a+outwhether packet is recei4ed or

not (ha$f-dup$e;#

• Eperation– when node o+tains fresh

frame it transmits at the+eginning of ne;t s$ot

– no co$$ision node can sendnew frame in ne;t s$ot

– if co$$ision wait a randomnum+er of s$ots and try tosend again

8/18/2019 ECE544Lec215b.ppt

33/74

E,,iciency o, S*otted !7/• !ggregate frame arri4a$ is 3oisson 3rocess

• 3 [k arri4a$s in a time-inter4a$\ A

• T2 the mean num+er of aggregate arri4a$s (for a$$ nodes innetwork# in this inter4a$

• time-inter4a$ A s$ot (one frame transmission time#

• Successfu$ pro+a+i$ity for each s$ot is 2

SA 3 [* attempt in a s$ot\ AGe-G

• S is optimum at TA*• SA*,e A ./Q'

(s$otted a$oha reduce the potentia$ co$$ision period from 2t  to t  +y node synchroniMation#

Ck 

Ge k G−

8/18/2019 ECE544Lec215b.ppt

34/74

(er,ormance o, !7/

•  hroughput 4ersus o6ered traNc for !LE>! systems•  he main reason for poor channe$ uti$iMation of !LE>! (pure or

s$otted# is that a$$ stations can transmit at wi$$ without payingattention to what the other stations are doing.

8/18/2019 ECE544Lec215b.ppt

35/74

Carrier Sense &u*tip*e ccess CS&.

• "S!2 $isten +efore transmit2

– If channe$ sensed id$e2 transmit

– If channe$ sensed +usy defer transmission

• >uman ana$ogy2 donDt interrupt others7

• "an co$$isions occur in this scheme–  wo nodes might attempt to transmit a frame at the same

time

– 3ropagation de$ay means two nodes may not hear eachotherDs transmission immediate$y

• Se4era$ 4ariants of "S! protoco$s2– on-3ersistent "S!

– *-3ersistent "S!

– 3-3ersistent "S!

8/18/2019 ECE544Lec215b.ppt

36/74

Non-persistent CS&

•  o send data a node =rst $istens to thechanne$ to see if anyone e$se is transmitting.

• If so the node waits a random period of time(instead of keeping sensing unti$ the end ofthe transmission# and repeats the a$gorithm.Etherwise it transmits a frame.

• If a co$$ision occurs the node waits a random

amount of time and starts a$$ o4er again.

8/18/2019 ECE544Lec215b.ppt

37/74

1-persistent CS& 

Algorithm0. Bo send data, a node first listens to the channel to see if an%one else is

transmitting.

!. If so, the node waits :kees sensing it9 until the channel )ecomes idle.

(therwise, it transmits a frame.

8/18/2019 ECE544Lec215b.ppt

38/74

(-persistent CS&

• !ssume channe$s are s$otted• Ene s$ot A contention period (i.e. one round trip propagation

de$ay#

!$gorithm2

*. Sense the channe$

– If channe$ is id$e transmit a packet with pro+a+i$ity p• if a packet was transmitted go to step )

• if a packet was not transmitted wait one s$ot and go to step *

– If channe$ is +usy wait one s$ot and go to step *.

– In other words wait unti$ id$e and then transmit with pro+a+i$ityp

). Detect co$$isions

– If a co$$ision occurs wait a random amount of time and go tostep *

8/18/2019 ECE544Lec215b.ppt

39/74

(ropagation )e*ay

• D on$y sense !Ds transmission after apropagation de$ay τ

• If τ is $arger than packet transmission timetoo much time wasted.

• "S! in sate$$ite communication o.• Distance & propagation de$ay determine

co$$ision pro+a+i$ity

&A " *

The size (length) of the network must e limited!

8/18/2019 ECE544Lec215b.ppt

40/74

8/18/2019 ECE544Lec215b.ppt

41/74

na*ysis o, Non-persistent CS&

• 3ro+. of success transmission SA ; I,(

8/18/2019 ECE544Lec215b.ppt

42/74

Comparison o, t'e c'anne* uti*i8ation "ersus *oad ,or"arious random access protoco*s

8/18/2019 ECE544Lec215b.ppt

43/74

CS& wit' Co**ision )etection

CSMACD !Carrier Sense M"ltiple Access wit# CollisionDetection$ protoco$ further impro4es !LE>! +ya+orting transmissions as soon as a co$$ision isdetected.

Eperation2

•  o send data a node =rst $istens to the channe$ to see ifanyone e$se is transmitting.• If not it transmits a frame• If channe$ +usy deferra$ as in "S!

– the node wait a random period of time and repeats thea$gorithm (non-persistent# or waits unti$ the end of the

transmission (*-persistent#•  he node wi$$ detect the co$$ision if co$$ision detecteda+ort its transmission (reducing channe$ wastage#waits a random amount of time and starts a$$ o4eragain.

/ t ) t t C **i i

8/18/2019 ECE544Lec215b.ppt

44/74

/ow to )etect Co**ision

• 3rere?uisite2 ! node can $isten whi$eta$king

• %asy in wired L!s2 measure signa$strength compare ; and R; signa$s

• DiNcu$t in wire$ess L!s2 recei4er shut

o6 whi$e transmitting

B6 R6

8/18/2019 ECE544Lec215b.ppt

45/74

8/18/2019 ECE544Lec215b.ppt

46/74

(ro*ems wit' carrier sensing

Y

Z

W

Hidden terminal problem

W finds that medium is free

and it transmits a packet to Z

  no carrier ===> OK to transmit/

8/18/2019 ECE544Lec215b.ppt

47/74

8/18/2019 ECE544Lec215b.ppt

48/74

So*"ing /idden Node pro*em wit' TS9CTS

Y

ZX

W

#$%&$%

listen #$% ==> transmitter is close

listen &$% ==> recei!er is close

E listen #$%' wait long enough  for the re(uested

  station to respond

  with &$%

' if )timeout* then

  read+ to transmit

' listen &$%

' wait long enough

  for the transmitterto send its data

,ote- #$%.&$% does not sol!e exposed terminal problem/ 0n the example abo!e1

can send #$%1 but &$% from the responder will collide with Y2s data/

8/18/2019 ECE544Lec215b.ppt

49/74

TS9CTS ec'ange eamp*e

• RS 0 "S 0 5rame 0 !"H e;change in4oked when frame

siMe is $arge• !F (etwork !$$ocation Fector#

– !F maintains prediction of future traNc on the medium+ased on duration information that is announced inRS,"S frames prior to actua$ e;change of data

$ransmitter 

304%

 ACK 

"TS

#ecei!er 

Frame

#TS

567

8s 9:8s

%04%

;9

8/18/2019 ECE544Lec215b.ppt

50/74

Taking Turns; &C protoco*s

3o$$ing2 • master node

in4itesJ s$a4enodes to transmit

in turn• concerns2

– po$$ingo4erhead

– sing$e point offai$ure (master#

 oken passing2• contro$ token passed from one

node to ne;t se?uentia$$y.

• token message

• concerns2– token o4erhead

– comp$e;ity

– sing$e point of fai$ure (token#

 

8/18/2019 ECE544Lec215b.ppt

51/74

T)&•  ime Di4ision u$tip$e !ccess (D!#

8/18/2019 ECE544Lec215b.ppt

52/74

+ied T)&

• access to channe$ in ]rounds]• each station gets =;ed $ength s$ot ($ength A

packet transmission time# in each round

• unused s$ots go id$e  G  ot eNcient

• e;amp$e2 Q-station L! */W ha4e pkt s$ots)OQ id$e

8/18/2019 ECE544Lec215b.ppt

53/74

)ynamic T)&• In dynamic %DMA a schedu$ing a$gorithm dynamica$$y

reser4es a 4aria+$e num+er of times$ots in each frameto 4aria+$e user data streams +ased on the traNcdemand of each user data stream.

• egotiations (+eforehand# to determine how to a$$ocates$ots dynamica$$y.

Modem

preamble

TDM Downlink D-TDMA Uplink

S-ALOHA

control

User B User C

TDD-TDMA Frame

Burst from User A

To Access PointBurst from Access Point -> Mobiles

+rame header and schedule

8/18/2019 ECE544Lec215b.ppt

54/74

+)&• 5D!2 fre?uency di4ision mu$tip$e access

– channe$ spectrum di4ided into fre?uency +ands– each station assigned a fre?uency +and

• unused transmission time in fre?uency +ands goid$e if assignment =;ed

– IneNcient AB make it dynamica$$y assigned to

di6erent stations +ased on traNc demand– E5D!

   +  r  e  2  u  e  n  c  %

   )  a  n   d  s

8/18/2019 ECE544Lec215b.ppt

55/74

Spread Spectrum and C)&

• 9hat if we donDy not di4ide up the channe$ +y time (as in D!# or fre?uency (as in 5D!# Is co$$ision ine4ita+$e

• ot if co$$ision is no $onger damaging7

– Is there any way to decode +its gar+$ed +y other

o4er$apping frames

"ode Di4ision u$tip$e !ccess ("D!# +ased on Spread Spectrum

• !nother perspecti4e to so$4e mu$tip$e access pro+$ems

• Spread Spectrum is a 3> inno4ation not a !" techni?ue.

• "D! encodes data with a specia$ code associated with each

user and uses the constructi4e interference properties of the

specia$ codes to perform the mu$tip$e;ing.

8/18/2019 ECE544Lec215b.ppt

56/74

Spread Spectrum• Idea

– spread signa$ o4er wider fre?uency +and thanre?uired

– origina$$y deigned to thwart 1amming

• 5re?uency >opping– transmit o4er random se?uence of fre?uencies

– sender and recei4er share^

• pse$dorandom n$mber &enerator 

• seed

8/18/2019 ECE544Lec215b.ppt

57/74

Spread Spectrum cont.

• Direct Se?uence– for each +it send ER of that +it and n 

random +its

– random se?uence known to +oth senderand recei4er

– ca$$ed n-+it c'ippin& code

#andom se(uence- :9::9:99:9:99::9

3ata stream- 9:9:

O# of the two- 9:999:999:9:9::9

:

:

:

9

9

9

8/18/2019 ECE544Lec215b.ppt

58/74

Code )i"ision &u*tip*e ccess C)&.

• u$tip$e;ing echni?ue used with spread spectrum• Start with data signa$ rate

– "a$$ed +it data rate•

8/18/2019 ECE544Lec215b.ppt

59/74

!N tec'no*ogies

%thernet

 oken Ring

9ire$ess L!

8/18/2019 ECE544Lec215b.ppt

60/74

Et'ernet 7"er"iew• &istory

– de4e$oped +y ero; 3!R" in mid-*ZVs

– roots in !$oha packet-radio network

– standardiMed +y ero; D%" and Inte$ in *ZV'

– simi$ar to I%%% ')./ standard

• CSMACD

• 'vol"tion: ("s topology !)*+s$ Star topology !now$

• Most s"ccessf"l access network tec#nology

Hu) or switch

Ad-ance

Et' t +

8/18/2019 ECE544Lec215b.ppt

61/74

Et'ernet +rame• 3ream+$e2 ' +ytes

– V +ytes with pattern **** fo$$owed +y one +yte withpattern *****

– used to synchroniMe recei4er sender c$ock rates• !ddresses2Q +ytes

– if adapter recei4es frame with matching destination addressor with +roadcast address it passes data in frame to net-$ayerprotoco$ otherwise adapter discards frame

•  ype2 ) +ytes– indicates the higher $ayer protoco$ (most$y I3 +ut others a$so

supported#• "R"2 W +ytes

– checked at recei4er if error is detected the frame is simp$y dropped

•

8/18/2019 ECE544Lec215b.ppt

62/74

&C ddress•

!" !ddresses– uni?ue W'-+it unicast address assigned to each adapter

• e;amp$e2 /8:10:2b:e4:b1:02

– +roadcast2 a$$ 1s 62626262626 

– mu$ticast2 mu$ticast :ag (the $owest +it of the *st octet#A *

• *--O%--- to *--O%-V5-55-55 for I3 mu$ticast

– I3 mu$ticast group address mapped to the $owerorder )/ +its of !" address (not one-to-onemapping#

–ni?ue !" address a$$ocation administered +y I%%%• manufacturer +uys portion of !" address space

• the =rst three octets as 4endor-speci=c

8/18/2019 ECE544Lec215b.ppt

63/74

&C ddress "s# I( ddress

• W'-+it !" address

– Layer )

– sed to get packet fromone interface to

another within thesame L!,su+net(%thernet token ring^#

– 5$at

– ni?ue

– o change whenmo4ing

• /)-+it I3 address

– etwork $ayer

– sed to get packet to

destination I3 su+net– >ierarchica$

– "hange when mo4ing

• Depending on I3 su+netto which node is

attached

• I3 to !" address trans$ation2 !R3 (more $ater#

)i,,erent +*a"ors o, Et'ernet +ormat

8/18/2019 ECE544Lec215b.ppt

64/74

)i,,erent +*a"ors o, Et'ernet +ormat• %thernet 4ersion II

3estAB&

;

4&%"reamble %rcAB&

Type ?od+

7Octets '96::

3ata link header  3ata C & )4&%*

• I%%% ')./

3est

AB&

;

"reamble

%rc

AB& %ength

7Octets

3atalink Header 

*SAP SSAP "ontrol

4&%?od+

5'9

8/18/2019 ECE544Lec215b.ppt

65/74

6nre*ia*e< connection*ess ser"ice

• "onnection$ess2 o handshaking+etween sending and recei4ing adapter.

• nre$ia+$e2 recei4ing adapter doesnGtsend acks or nacks to sending adapter

– stream of datagrams passed to network$ayer can ha4e gaps

– gaps wi$$ +e =$$ed if app is using "3– otherwise app wi$$ see the gaps

8/18/2019 ECE544Lec215b.ppt

66/74

Et'ernet CS&9C)

*. If sender senses channe$ id$e it starts to transmitframe. If it senses channe$ +usy waits unti$channe$ id$e and then transmits (*-persistent"S!#• Inter-frame gap2 time to send ZQ +its (Z.Q µs for *+ps#

). If adapter transmits entire frame withoutdetecting another transmission the adapter isdone with frame 7

/. If adapter detects another transmission whi$etransmitting a+orts and sends /)-+it 1am signa$

(co$$ision detection#W. !fter a+orting sender enters e;ponentia$ +acko6 – after the mth co$$ision adapter chooses a H at random

from _*)^)m-*`. hen waits HO*) +it times (k ;O*.) us in * +ps %thernet# and returns to Step *

– gi4e up after se4era$ tries (usua$$y *Q#

8/18/2019 ECE544Lec215b.ppt

67/74

Et'ernet CS&9C) Cont.

 bam Signa$2

• make sure a$$ othertransmitters are aware ofco$$isionU

• /) +its

• 5rame2 QW (pream+$e# 0/) (1amming se?uence# AZQ +its – Runt 5rame

%;ponentia$

8/18/2019 ECE544Lec215b.ppt

68/74

Co**isions B ?

 B ?

 B ?

 B ?

9orst case2

• ! sends at t !Gs framearri4es < at t0d

• < +egins transmitting at t0dand co$$ides with !Gs frame

• < sends runt frame the runt

frame arri4es ! at t0)d•  o detect co$$ision ! must

continue transmit unti$ t0)d.! must transmit for )d.

• Round-trip de$ay a+out O*.)

us for )Om $ong %thernetwith W repeater

– "orresponds to O*) +its for* +ps %thernet

– So min frame siMe O*) +itsBhe longer the roagation dela%,

the higher ro)a)ilit% of collision.

8/18/2019 ECE544Lec215b.ppt

69/74

10%aseT and 100%aseT 

• *,* +ps rateU $atter ca$$ed fast ethernetJ•   stands for wisted 3air• Star top$ogy ma; *m +etween node and hu+• >u+s2 physica$-$ayer repeaters

– +its coming from one $ink go out a$$ other $inks at thesame rate

– no frame +u6ering– no "S!,"D at hu+2 adapters detect co$$isions– pro4ides net management functiona$ity

Hu)

!egacy Et'ernet

8/18/2019 ECE544Lec215b.ppt

70/74

!egacy Et'ernet• *

8/18/2019 ECE544Lec215b.ppt

71/74

=it Et'ernet

• uses standard %thernet frame format

• a$$ows for point-to-point $inks and shared+roadcast channe$s

• in shared mode "S!,"D is usedU shortdistances +etween nodes re?uired foreNciency

• uses hu+s

• 5u$$-Dup$e; at * T+ps for point-to-point $inks• * T+ps now

Et' t ( ,

8/18/2019 ECE544Lec215b.ppt

72/74

Et'ernet (er,ormance• a; throughput K* as a function of span

– !s propagation de$ay increases eNciency decreases– insta+i$ity can occur un$ess $oad is reduced under congestion

conditions– retransmission +acko6 po$icy for sta+i$ity

(-erload

region

 Normal oerating

 oint

"aacit% Limit.3

load lines

(ffered Braffic

BhruBraffic

margin

sta)le olic%:ret6 )ackoff9

sta)le olic%

:)ackoff too high9

unsta)le olic%

:no )ackoff9

8/18/2019 ECE544Lec215b.ppt

73/74

ire*ess !Ns

• ').** a,+,g di6erent 3hy techno$ogies– ').** +,g2 ) >M channe$ in ).W T>M up

to ** +ps (').**+# OW +ps (').**g#phy data rate

– ').**a2 ) >M channe$ in OT>M up to OW+ps phy data rate

• ').**n2–  */ +ps phy data rate on ) >M channe$

() ; ) IE#

– / +ps phy data rate on W >M channe$(channe$ +onding with ) ; ) IE#

See supplementary WLAN tutorial slides

8/18/2019 ECE544Lec215b.ppt

74/74

Todays /omework• 3eterson & Da4ie "hap ) Wth ed

).Q).*').)/

).//).WW).W)

Down$oad and re4iew %thernet and ').** !"specs and study I%%% ').** 9ire$ess L!

E4er4iew s$ides

Due ),Q