Link%Layer%and%Wireless%CS144%Review%Session%7%May%16,%2008%Ben%Nham%Routers,%Switches,%and%Hubs%• Routers%are%network%layer%devices%– Modify%IP%datagram%(decrement%TTL)%– Hosts%and%other%routers%must%be%aware%of%them%• Switches%and%hubs%are%link%layer%devices%– Only%care%about%frames,%don’t%modif y%IP%datagram%– Transparent%to%network%Hubs%• Operate%as%a%repeater%– Broadcast%an%incoming%frame%to%all%ports,%except%for%the%ingress%port%– Like%having%a%longer%Ethernet%cable%that%all%the%hosts%tap%into%– All%ports%are%on%single%collision%domain!%• Advantages:%simple,%restores%signal,%potenUally%fast%since%we%don’t%have%to%buffer%or%examine%frame%• Disadvantages:%poor%bandwidth%due%to%collisions%Hub%QuesUon%1%• A%10‐port%hub%is%connected%to%10%hosts%using%gigabit%links.%What%is%the%maximum%aggregate%transfer%rate%of%data%flowing%through%this%network?%– All%ports%are%part%of%the%same%collision%domain‐‐only%one%device%can%send%at%a%Ume%– Therefore,%peak%bandwidth%is%one%gigabit%Hub%QuesUon%2%• Recall%that%100Mbps%Ethernet%restricts%cable%lengths%to%100m.%Suppose%we%want%to%connect%two%hosts%which%are%1000m%apart.%Can%we%use%10%100m%cables%with%9%hubs%in%series%to%accomplish%this?%– No.%Since%all%ports%are%on%same%collision%domain,%max%network%diameter%(1km)%is%too%large%to%meet%the%TRANSP%>%2%*%PROP%constraint%of%CSMA/CD%– In%reality,%the%IEEE%standard%limits%number%of%hubs%in%series%and%specifies%maximum%network%diameter%Switches%• Must%store%and%examine%frame%before%forwarding%• Simple%learning%protocol—no%configuraUon%– Given%incoming%frame%(MACsrc,%MACdst)%on%port%x:%– Add%(MACsrc,%x)%to%switch%table%– Look%up%port%for%MACdst%%for%in%switch%table%• If%entry%is%there,%forward%frame%to%that%port%• Else,%broadcast%frame%to%all%ports%(except%ingress%port)%– Runs%spanning%tree%protocol%to%prevent%loops%• Collision%domain%is%a%single%port—switch%will%make%sure%that%the%frame%it%sends%out%does%not%collide%with%another%frame%being%sent%on%the%same%link%Memory%Mapped%Registers%• Can%send%a%command%to%hardware%through%memory‐mapped%registers%• These%addresses%aren’t%mapped%to%physical%memory,%but%rather%to%the%HW%device%– Store%to%locaUon%writes%to%HW%device%over%bus%– Load%from%locaUon%reads%from%HW%device%over%bus%Direct%Memory%Access%• With%memory‐mapped%registers,%CPU%is%constantly%waiUng%on%I/O%operaUons%to%complete%– I/O%devices%are%usually%slower%than%processors%– Blocks%processor%• Instead,%beeer%to%have%device%write%directly%to%physical%memory%• This%can%be%done%through%DMA%– CPU%pokes%device,%goes%on%to%do%something%else%– Device%writes%directly%to%memory%– At%some%other%Ume%(like%an%interrupt),%CPU%goes%back%to%fetch%data%that%device%wrote%to%memory%Polling%vs.%Interrupts%• Polling:%CPU%periodically%checks%for%data%from%device%– Inefficient%if%there’s%no%data%for%CPU%to%process,%and%higher%latency%– Efficient%if%lots%of%data%to%process%(batches%context%switches)%• Interrupts:%Device%interrupts%CPU’s%current%execuUon,%making%it%jump%to%an%interrupt%handler%– Efficient%if%it%doesn’t%happen%much,%and%lower%latency%since%we%don’t%wait%for%a%polling%Umer%to%Umeout%– Can%lead%to%livelock%if%too%many%interrupts%(e.g.%in%network%cards%that%process%many%packets)%Lab%5:%Dynamic%RouUng%• Implement%RIP%(distance‐vector)%in%Java%• You%are%given%a%router%that%already%works,%except%it%doesn’t%process%RIP%packets%– Write%RIP%packet%handling%code%that%modifies%rouUng%table%– Simulates%the%network%topology%locally%(doesn’t%route%real%packets)%• References%– Assignment%webpage%– Textbook:%DV%(4.5.2)%and%RIP%(4.6.1)%– RIP%Version%2%RFC2453%(although%you%don’t%have%to%implement%all%the%features)%Distance%Vector%Refresher%• Distributed,%local%rouUng%algorithm%• Exchange%rouUng%tables%with%neighbors%• If%we%find%a%beeer%cost%path%to%any%desUnaUon%through%our%neighbors,%update%the%cost%Pseudocode%• Define:%– Dx(y)%=%cost%from%x%to%y%(x’s%rouUng%table)%– c(x,y)%=%link%cost%of%edge%(x,y)%while%True:%% wait%unUl%we%get%a%rouUng%table%from%neighbor%v%% for%each%new%rouUng%table%entry%received%from%v%that%goes%to%dest:%% %%%%entry%=%lookupRouUngTable(dest)%% %%%%if%c(x,v)%+%Dv(dest)%<=%entry.curCost%or%entry.nextHop%is%v:%% %%%%%%%%entry.nextHop%=%v%% %%%%%%%%entry.cost%=%c(x,v)%+%Dv(dest)%% send%rouUng%table%to%all%neighbors%if%Dx%changed%• Also%have%to%handle%updates%if%a%local%link%metric%is%updated%or%goes%up/down%Basic%Code%Overview%• acceptPacket%gets%called%with%a%new%RIP%update%packet%– RIPRouUngUpdate%contains%an%ArrayList%of%RIPRouUngUpdate.Entry%(get%the%ArrayList%through%getAllEntries()%method)%– Get%cost%to%neighbor%through%getLocalLinkInfoForNex tHop%• Send%a%packet%using%m_ports[PORT_UPDATE_OUT].pushOut(packet)%– Packet%is%of%type%IPPacket%– Build%by%creaUng%a%new%RouUngTableUpdate,%and%calling%addEntry%to%it%• noUfyAlarm()%gets%called%periodically,%use%it%to%do%periodic%tasks%– Decrement%TTL%of%routes%learned%from%others%– Send%updates%if%necessary%(if%Umeout%interval%has%passed,%or%a%route%Umed%out)%• Get%familiar%with%Java%funcUons%for%manipulaUng%IPs,%applying%netmasks%– NetuUls.applyNetMask%– InetAddress%class%• Use%Clack%JavaDoc%from%assignment%webpage%for%reference%AddiUonal%Cases%• New%network%adverUsed%– Add%to%rouUng%table%• Ignore%updates%to%one%of%your%own%prefixes%if%you%know%they’re%down%already%– Otherwise%you%could%end%up%thinking%you%have%a%route%to%yourself%that%you%know%is%already%down!%• Local%link%metric%has%updated%or%local%link%has%gone%down%•
View Full Document
Unlocking...