Computer Network Unit IV - Lecture Notes - Network Layer

Title:
Lecture Notes - Unit IV - The Network Layer
Description:
Welcome to the comprehensive guide on Computer Network concepts, tailored for final year B.Sc. Computer Science students affiliated with Alagappa University. This document covers fundamental principles and advanced topics in Computer Network. PDF content is prepared from the text book Computer Network by Andrew S. Tenanbaum

Key Topics Covered:

Main Topic : The Network Layer
Sub-Topic : Network Layer Design Issues (Store and forward packet switching , service provided to the transport layer, implementation of connection less service, implementation of connection oriented service, Comparision of virtual circuit and datagram subnet), Routing algorithms (Shortest path routing, Flooding , Distance Vector routing algorithm, Link state routing algorithm , hierarchical routing algorithm, broadcast routing, multicast routing algorithm)
Other Link :
1.Introduction to computer network - https://www.slideshare.net/slideshow/lecture-notes-introduction-to-computer-network/274183454

2. Physical Layer - https://www.slideshare.net/slideshow/lecture-notes-unit-ii-the-physical-layer/274747125

3. Data Link Layer Part 1 : https://www.slideshare.net/slideshow/lecture-notes-unit-iii-the-datalink-layer/275288798

Target Audience:

Final year B.Sc. Computer Science students at Alagappa University seeking a solid foundation in Computer Network principles for academic.

About the Author:
Dr. S. Murugan is Associate Professor at Alagappa Government Arts College, Karaikudi. With 23 years of teaching experience in the field of Computer Science, Dr. S. Murugan has a passion for simplifying complex concepts in Computer Network

Disclaimer:
This document is intended for educational purposes only. The content presented here reflects the author’s understanding in the field of Computer Network

1. Unit IV -The Network Layer
Dr. S.Murugan
Associate Professor, Department of Computer Science.
AlagappaGovernment Arts College,
(Affiliated by AlagappaUniversity)
Karaikudi.
Email: [email protected]

2. This slides compiled from
Computer Network by
Andrew S. Tenenbaum4
th
Ed.

3. The Network Layer
➢Thenetworklayerisconcernedwithgettingpackets
fromthesourceallthewaytothedestination.
➢Toachieveitsgoals,thenetworklayermustknow
aboutthetopologyofthecommunicationsubnet(i.e.,
thesetofallrouters)andchooseappropriatepaths
throughit.

4. 5.1 Network Layer Design Issues
5.1.1Store-and-ForwardPacketSwitching
➢Theenvironmentofthenetworklayerprotocolis
representedinthefigure5.1.

5. 5.1.1 Store-and-Forward Packet Switching
➢Ahostwithapackettosendtransmitsittothenearest
router,eitheronitsownLANoroverapoint-to-point
linktothecarrier.
➢Thepacketisstoredthereuntilithasfullyarrivedso
thechecksumcanbeverified.
➢Thenitisforwardedtothenextrouteralongthepath
untilitreachesthedestinationhost,whereitis
delivered.
➢Thismechanismisstore-and-forwardpacket
switching.

6. 5.1.2 Services Provided to the Transport Layer
➢Thenetworklayerprovidesservicestothetransport
layeratthenetworklayer/transportlayerinterface.
Thenetworklayerserviceshavebeendesignedwith
thefollowinggoalsinmind.
1.Theservicesshouldbeindependentoftherouter
technology.
2.Thetransportlayershouldbeshieldedfromthe
number,type,andtopologyoftherouterspresent.
3.Thenetworkaddressesmadeavailabletothe
transportlayershoulduseauniformnumbering
plan,evenacrossLANsandWANs.

7. 5.1.3 Implementation of Connectionless Service
➢Ifconnectionlessserviceisoffered,packetsare
injectedintothesubnetindividuallyandrouted
independentlyofeachother.Noadvancesetupis
needed.
➢Inthiscontext,thepacketsarefrequentlycalled
datagrams(inanalogywithtelegrams)andthesubnet
iscalledadatagramsubnet.
➢Ifconnection-orientedserviceisused,apathfromthe
sourceroutertothedestinationroutermustbe
establishedbeforeanydatapacketscanbesent.

8. 5.1.3 Implementation of Connectionless Service
➢ThisconnectioniscalledaVC(virtualcircuit),in
analogywiththephysicalcircuitssetupbythe
telephonesystem,andthesubnetiscalledavirtual-
circuitsubnet.
➢Figure5.2showstheroutingwiththedatagram
subnet.ThemessageMistransferfromHost1to
Host2.
➢Thenetworklayerhastobreakthemessagesintofour
packets,1,2,3,and4andsendseachoftheminturn
torouterAusingsomepoint-to-pointprotocol,for
example,PPP.

9. 5.1.3 Implementation of Connectionless Service
➢Atthispointthecarriertakesover.Everyrouterhasan
internaltabletellingitwheretosendpacketsforeach
possibledestination.
➢Eachtableentryisapairconsistingofadestination
andtheoutgoinglinetouseforthatdestination.
➢Onlydirectly-connectedlinescanbeused.

10. 5.1.3 Implementation of Connectionless Service

11. 5.1.3 Implementation of Connectionless Service
➢Forexample,inFig.5-2,Ahasonlytwooutgoing
linestoBandC.soeveryincomingpacketmustbe
senttooneoftheserouters,eveniftheultimate
destinationissomeotherrouter.A'sinitialrouting
tableisshowninthefigureunderthelabel''initially.''
➢
➢AstheyarrivedatA,packets1,2,and3werestored.
TheneachwasforwardedtoCaccordingtoA'stable.
➢Packet1wasthenforwardedtoEandthentoF.
WhenitgottoF,itwasencapsulatedinadatalink
layerframeandsenttoH2overtheLAN.Packets2
and3followthesameroute.

12. 5.1.3 Implementation of Connectionless Service
➢However,somethingdifferenthappenedtopacket4.
WhenitgottoAitwassenttorouterB,eventhoughit
isalsodestinedforF.
➢Forsomereason,Adecidedtosendpacket4viaa
differentroutethanthatofthefirstthree.
➢Perhapsitlearnedofatrafficjamsomewherealong
theACEpathandupdateditsroutingtable,asshown
underthelabel''later.''
➢Thealgorithmthatmanagesthetablesandmakesthe
routingdecisionsiscalledtheroutingalgorithm.

13. 5.1.4 Implementation of Connection-Oriented
Service
➢Forconnection-orientedservice,weneedavirtual-
circuitsubnet.virtualcircuitsistoavoidhavingto
chooseanewrouteforeverypacketsent,asinFig.5-2.
➢Withconnection-orientedservice,eachpacketcarries
anidentifiertellingwhichvirtualcircuititbelongsto.
➢Asanexample,considerthesituationofFig.5-3.

14. 5.1.4 Implementation of Connection-Oriented
Service

15. 5.1.4 Implementation of Connection-Oriented
Service
➢Here,hostH1hasestablishedconnection1withhost
H2.Itisrememberedasthefirstentryineachofthe
routingtables.ThefirstlineofA'stablesaysthatifa
packetbearingconnectionidentifier1comesinfrom
H1,itistobesenttorouterCandgivenconnection
identifier1.Similarly,thefirstentryatCroutesthe
packettoE,alsowithconnectionidentifier1.
➢NowletusconsiderwhathappensifH3alsowantsto
establishaconnectiontoH2.

16. 5.1.4 Implementation of Connection-Oriented
Service
➢Itchoosesconnectionidentifier1(becauseitisinitiating
theconnectionandthisisitsonlyconnection)andtells
thesubnettoestablishthevirtualcircuit.Thisleadstothe
secondrowinthetables.Notethatwehaveaconflict
herebecausealthoughAcaneasilydistinguish
connection1packetsfromH1fromconnection1packets
fromH3,Ccannotdothis.
➢Forthisreason,Aassignsadifferentconnection
identifiertotheoutgoingtrafficforthesecond
connection.Avoidingconflictsofthiskindiswhyrouters
needtheabilitytoreplaceconnectionidentifiersin
outgoingpackets.Insomecontexts,thisiscalledlabel
switching.

17. 5.1.5 Comparison of Virtual-Circuit and Datagram
Subnets

18. 5.2 Routing Algorithms
➢Themainfunctionofthenetworklayerisroutingpackets
fromthesourcemachinetothedestinationmachine.In
mostsubnets,packetswillrequiremultiplehopstomake
thejourney.
➢Theroutingalgorithmisthatpartofthenetworklayer
softwareresponsiblefordecidingwhichoutputlinean
incomingpacketshouldbetransmittedon.
➢Ifthesubnetusesdatagramsinternally,Forevery
arrivingpacketisroutedindependently.Whenvirtual
circuitisestablishedallpacketsarefollowsthesame
route.Thedatapacketsjustfollowthepreviously-
establishedrouteiscalledsessionrouting.

19. 5.2 Routing Algorithms
➢Thedesirablepropertiesofaroutingalgorithm:
correctness,simplicity,robustness,stability,fairness,and
optimality.
➢Therobustnessmaybeexpectedtoruncontinuouslyfor
yearswithoutsystemwidefailures.Duringthatperiod
therewillbehardwareandsoftwarefailuresofallkinds.
➢
➢Routingalgorithmscanbegroupedintotwomajor
classes:nonadaptiveandadaptive.
➢Innon-adaptiverouting,thechoiceoftherouteis
calculatedinadvance.Thistypeofroutingprocedureis
calledstaticrouting.

20. 5.2 Routing Algorithms
➢Inadaptiveroutingthechoiceoftherouteisnot
calculatedinadvance.Thistypeofroutingprocedureis
calleddynamicrouting.
➢
➢Thesetofoptimalroutesfromallsourcestoagiven
destinationformatreerootedatthedestination.Sucha
treeiscalledasinktreeandisillustratedinFig.5-6,
wherethedistancemetricisthenumberofhops.
➢Thegoalofallroutingalgorithmsistodiscoveranduse
thesinktreesforallrouters.
➢Asinktreeisindeedatree,itdoesnotcontainanyloops,
soeachpacketwillbedeliveredwithinafiniteand
boundednumberofhops.

21. 5.2 Routing Algorithms
Figure 5-6. (a) A subnet. (b) A sink tree for router B.

22. 5.2.2 Shortest Path Routing
➢Theideaistobuildagraphofthesubnet,witheachnode
ofthegraphrepresentingarouterandeacharcofthe
graphrepresentingacommunicationline(oftencalleda
link).
➢Tochoosearoutebetweenagivenpairofrouters,the
algorithmjustfindstheshortestpathbetweenthemon
thegraph.
➢Onewayofmeasuringpathlengthisthenumberofhops.
Usingthismetric,thepathsABCandABEinFig.5-7are
equallylong.Anothermetricisthegeographicdistance
inkilometers,inwhichcaseABCisclearlymuchlonger
thanABE(assumingthefigureisdrawntoscale).

23. 5.2.2 Shortest Path Routing
Figure 5-7. The first five steps used in computing the shortest path from A to D.
The arrows indicate the working node.

24. 5.2.2 Shortest Path Routing
Possible Path 1 : ABCD : 2+7+3=12
Possible path 2 : ABEFCD: 2+2+2+3+3=12
Possible path3 : ABEFHD : 2+2+2+2+2=10 -→
Shortest Path
Shortest Path : ABEGHD: 2+2+1+4+2=11

25. 5.2.2 Shortest Path Routing
➢Severalalgorithmsforcomputingtheshortestpath
betweentwonodesofagraphareknown.Thisoneis
duetoDijkstra(1959).Eachnodeislabeled(in
parentheses)withitsdistancefromthesourcenode
alongthebestknownpath.
➢Initially,nopathsareknown,soallnodesarelabeled
withinfinity.Asthealgorithmproceedsandpathsare
found,thelabelsmaychange,reflectingbetterpaths.
Alabelmaybeeithertentativeorpermanent.Initially,
alllabelsaretentative.Whenitisdiscoveredthata
labelrepresentstheshortestpossiblepathfromthe
sourcetothatnode,itismadepermanentandnever
changedthereafter.

26. 5.2.2 Shortest Path Routing
➢Toillustratehowthelabelingalgorithmworks,lookat
theweighted,undirectedgraphofFig.5-7(a),where
theweightsrepresent,forexample,distance.Wewant
tofindtheshortestpathfromAtoD.
➢WestartoutbymarkingnodeAaspermanent,
indicatedbyafilled-incircle.Thenweexamine,in
turn,eachofthenodesadjacenttoA(theworking
node),relabelingeachonewiththedistancetoA.
➢Wheneveranodeisrelabeled,wealsolabelitwith
thenodefromwhichtheprobewasmadesothatwe
canreconstructthefinalpathlater.

27. 5.2.2 Shortest Path Routing
➢HavingexaminedeachofthenodesadjacenttoA,we
examineallthetentativelylabelednodesinthewhole
graphandmaketheonewiththesmallestlabel
permanent,asshowninFig.5-7(b).
➢Thisonebecomesthenewworkingnode.Wenow
startatBandexamineallnodesadjacenttoit.
➢IfthesumofthelabelonBandthedistancefromBto
thenodebeingconsideredislessthanthelabelonthat
node,wehaveashorterpath,sothenodeisrelabeled.

28. 5.2.3 Flooding
1.Identifythenumberofhop(Jump)fromsourceto
destination.
2.Initialisethecountervalue
3.Decreasethecountervalueateachhopreaches
4.Stoptheprocesswhencounterreachestozero.

29. 5.2.4 Distance Vector Routing
➢Moderncomputernetworksgenerallyusedynamic
routingalgorithms.Twodynamicalgorithms,in
particular,distancevectorroutingandlinkstate
routing,arethemostpopular.
➢Indistancevectorrouting,eachroutermaintainsa
routingtableindexedby,andcontainingoneentryfor,
eachrouterinthesubnet.
➢Thisentrycontainstwoparts:thepreferredoutgoing
linetouseforthatdestinationandanestimateofthe
timeordistancetothatdestination.Themetricused
mightbenumberofhops,thetimedelayin
milliseconds,totalnumberofpacketsqueuedalong
thepath,orsomethingsimilar.

30. 5.2.4 Distance Vector Routing
➢Therouterisassumedtoknowthe''distance''toeach
ofitsneighbors.Ifthemetricishops,thedistanceis
justonehop.Ifthemetricisqueuelength,therouter
simplyexamineseachqueue.Ifthemetricisdelay,the
routercanmeasureitbytimedelay.
➢Byusingthebellmanfordcalculationforeach
neighbor,aroutercanfindoutwhichestimateseems
thebestandusethatestimateandthecorresponding
lineinitsnewroutingtable.
➢TheupdatingprocessisillustratedinFig.5-9.Part(a)
showsasubnet.TheFig5-9determinesthenext
estimateddelayfromJ.Thefirstfourcolumnsofpart
(b)showthedelayvectorsreceivedfromthe
neighborsofrouterJ.

31. 5.2.4 Distance Vector Routing

32. 5.2.4 Distance Vector Routing

33. 5.2.4 Distance Vector Routing
ConsiderhowJcomputesitsnewroutetorouterG.
Step1:DistancevectorfromAtoremainingrouterB.C,D,…LviaJ
(i.e,routerAtorouterBviaJ=12msec,routerAtorouterCviaJ=25,
etc.representedasBlackbold)
Step2:Forexample,Jhasmeasuredorestimateditsdelaytoits
neighbors,A,I,H,andKas8,10,12,and6msec,respectively.
Step3:DeterminetheshortestpathfromGtoA,I,HandKvia
routerJ.
DelayforGtoA=JADelaytime+GADelaytime➔8+18=26;
DelayforGtoA=JIDelaytime+GIDelaytime➔31+10=41;
DelayforGtoA=JHDelaytime+GHDelaytime➔6+12=18;
DelayforGtoA=JKDelaytime+GKDelaytime➔31+6=37;
Step4:Thebestofthesevaluesis18,soitmakesanentryinits
routingtablethatthedelaytoGis18msecandthattheroutetouse
isviaH.
Thesamecalculationisperformedforalltheotherdestinations,with
thenewroutingtableshowninthelastcolumnofthefigure.

34. 5.2.5 Link State Routing
➢The idea behind link state routing is simple and can be
stated as five parts. Each router must do the following:
1.Discoveritsneighborsandlearntheirnetworkaddresses.
2.Measurethedelayorcosttoeachofitsneighbors.
3.Constructapacket,tellingallithasjustlearned.
4.Sendthispackettoallotherrouters.
5.Computetheshortestpathtoeveryotherrouter.

35. 5.2.5 Link State Routing
LearningabouttheNeighbors
➢Whenarouterisbooted,itsfirsttaskistolearnwhoits
neighborsare.Itaccomplishesthisgoalbysendinga
specialHELLOpacketoneachpoint-to-pointline.The
routerontheotherendisexpectedtosendbackareply
tellingwhoitis.
➢WhentwoormoreroutersareconnectedbyaLAN,the
situationisslightlymorecomplicated.Fig.5-11(a)
illustratesaLANtowhichthreerouters,A,C,andF,
aredirectlyconnected.Eachoftheseroutersis
connectedtooneormoreadditionalrouters,asshown.

36. 5.2.5 Link State Routing
➢OnewaytomodeltheLANistoconsideritasanode
itself,asshowninFig.5-11(b).
➢Hereintroducedanew,artificialnode,N,towhichA,
C,andFareconnected.Thefactthatitispossibleto
gofromAtoContheLANisrepresentedbythepath
ANChere.

37. 5.2.5 Link State Routing
MeasuringLineCost
➢Thelinkstateroutingalgorithmrequireseachrouterto
know,oratleasthaveareasonableestimateof,the
delaytoeachofitsneighbors.
➢Themostdirectwaytodeterminethisdelayistosend
overthelineaspecialECHOpacketthattheotherside
isrequiredtosendbackimmediately.
➢Unfortunately,thereisanargumentagainstincluding
theloadinthedelaycalculation.Considerthesubnetof
Fig.5-12,whichisdividedintotwoparts,Eastand
West,connectedbytwolines,CFandEI.

38. 5.2.5 Link State Routing
➢SupposethatmostofthetrafficbetweenEastandWest
isusinglineCF,andasaresult,thislineisheavily
loadedwithlongdelays.Includingqueueingdelayin
theshortestpathcalculationwillmakeEImore
attractive.
➢Afterthenewroutingtableshavebeeninstalled,most
oftheEast-WesttrafficwillnowgooverEI,
overloadingthisline.Consequently,inthenextupdate,
CFwillappeartobetheshortestpath.Asaresult,the
routingtablesmayoscillatewildly,leadingtoerratic
routingandmanypotentialproblems.

39. 5.2.5 Link State Routing

40. 5.2.5 Link State Routing
Building Link State Packets
➢Oncetheinformationneededfortheexchangehasbeen
collected,thenextstepisforeachroutertobuilda
packetcontainingallthedata.Thepacketstartswiththe
identityofthesender,followedbyasequencenumber
andage(tobedescribedlater),andalistofneighbors.
➢Foreachneighbor,thedelaytothatneighborisgiven.
AnexamplesubnetisgiveninFig.5-13(a)withdelays
shownaslabelsonthelines.Thecorrespondinglink
statepacketsforallsixroutersareshowninFig.5-
13(b).

41. 5.2.5 Link State Routing
Building Link State Packets
➢Oncetheinformationneededfortheexchangehasbeen
collected,thenextstepisforeachroutertobuilda
packetcontainingallthedata.Thepacketstartswiththe
identityofthesender,followedbyasequencenumber
andage(tobedescribedlater),andalistofneighbors.
➢Foreachneighbor,thedelaytothatneighborisgiven.
AnexamplesubnetisgiveninFig.5-13(a)withdelays
shownaslabelsonthelines.Thecorrespondinglink
statepacketsforallsixroutersareshowninFig.5-
13(b).

42. 5.2.5 Link State Routing

43. 5.2.5 Link State Routing
➢Thefundamentalideaistousefloodingtodistributethe
linkstatepackets.Tokeepthefloodincheck,each
packetcontainsasequencenumberthatisincremented
foreachnewpacketsent.Whenanewlinkstatepacket
comesin,itischeckedagainstthelistofpacketsalready
seen.Ifitisnew,itisforwardedonalllinesexceptthe
oneitarrivedon.Ifitisaduplicate,itisdiscarded.
➢Thesolutiontoroutercrashorsequencenumberlossis
toincludetheageofeachpacketafterthesequence
numberanddecrementitoncepersecond.Whentheage
hitszero,theinformationfromthatrouterisdiscarded.

44. 5.2.5 Link State Routing
➢ThedatastructureusedbyrouterBforthesubnet
showninFig.5-13(a)isdepictedinFig.5-14.Eachrow
herecorrespondstoarecently-arrived,butasyetnot
fully-processed,linkstatepacket.
➢Thetablerecordswherethepacketoriginated,its
sequencenumberandage,andthedata.Inaddition,
therearesendandacknowledgementflagsforeachof
B'sthreelines(toA,C,andF,respectively).
➢Thesendflagsmeanthatthepacketmustbesentonthe
indicatedline.Theacknowledgementflagsmeanthatit
mustbeacknowledgedthere.

45. 5.2.5 Link State Routing

46. 5.2.5 Link State Routing
ComputingtheNewRoutes
Oncearouterhasaccumulatedafullsetoflinkstate
packets,itcanconstructtheentiresubnetgraphbecause
everylinkisrepresented.Everylinkis,infact,represented
twice,onceforeachdirection.Thetwovaluescanbe
averagedorusedseparately.

47. 5.2.6 Hierarchical Routing
➢Whenhierarchicalroutingisused,theroutersare
dividedintowhatwewillcallregions,witheachrouter
knowingallthedetailsabouthowtoroutepacketsto
destinationswithinitsownregion.
➢Figure5-15givesaquantitativeexampleofroutingina
two-levelhierarchywithfiveregions.
➢Thefullroutingtableforrouter1Ahas17entries,as
showninFig.5-15(b).

48. 5.2.6 Hierarchical Routing
➢Whenroutingisdonehierarchically,asinFig.5-15(c),
thereareentriesforallthelocalroutersasbefore,but
allotherregionshavebeencondensedintoasingle
router,soalltrafficforregion2goesviathe1B-2A
line,buttherestoftheremotetrafficgoesviathe1C-
3Bline.
➢Hierarchicalroutinghasreducedthetablefrom17to7
entries.Astheratioofthenumberofregionstothe
numberofroutersperregiongrows,thesavingsintable
spaceincrease.

49. 5.2.6 Hierarchical Routing
➢Fulltablefor1AisderivedfromFig.5.15a.InFig5.15a,
Region1has2lines1Band1C.Byusingthesetwolines,
thepacketcantranvelfromoneregiontoanotherregion.

50. 5.2.7 Broadcast Routing
➢Insomeapplications,hostsneedtosendmessages
tomanyorallotherhosts.
➢Sendingapackettoalldestinationssimultaneously
iscalledbroadcasting.
➢Forexample,aservicedistributingweather
reports,stockmarketupdates,orliveradio
programsmightworkbestbybroadcastingtoall
machines.

51. 5.2.8 Multicast Routing
➢Someapplicationsrequirethatwidely-separated
processesworktogetheringroups,forexample,a
groupofprocessesimplementingadistributed
databasesystem.
➢Sendingamessagetosuchagroupiscalled
multicasting,anditsroutingalgorithmiscalled
multicastrouting.