Paper on Routing

CSC-3080
Data Communication and Network
Title Routing
Group Member:
Mohsin Shoukat 12-NTU-1065
Shahmeer Ali 12-NTU-1083
Submitted to: Sir Asif Habib.
Submission Date: 24/03/2015
..………………… /………………….. .................................
Members Sign Teacher Sign

Acknowledgement
We agree all the content written in this documentation is our selves’ .We are
responsible to this. We are thankful to our teacher Mr. Asif Habib to help write this
document.

Table of Contents
What is Router .................................................................................................................................1
What is Routing................................................................................................................................1
Desirable Property of Routing Algorithms......................................................................................2
Design Parameter of Routing Algorithms ........................................................................................2
Routing Strategies ...........................................................................................................................3
Fixed Routing ...................................................................................................................................3
Least Cost Path ................................................................................................................................4
Dijkstra Algorithm............................................................................................................................5
Flooding Routing ..............................................................................................................................6
Selective Flooding ............................................................................................................................7
Utilities of Flooding ..........................................................................................................................7
Random Routing ..............................................................................................................................8
Adaptive Routing............................................................................................................................10
Distance Vector Routing ................................................................................................................11
Link State Routing ..........................................................................................................................12
Multicast Routing............................................................................................................................. 13

1
Router
A router is networking hardware device which send and receive data packets to other
networks.
Routing Defined
From particularstationtoparticular station, i.e. fromsource todestinationthere are manypath, sothe
routingisto choose the bestcost effectivepath,whichisselectedbyroutingalgorithm.
Detail:
Thisis packetswitchnetwork,numberof stationA,B,ETC , numberof nodesswitching,which
connected toothernodesandstation, suppose stationA -> D , you can see there isnotpath , other
words, bothare not directly connect,so itcan go several path, i.e. 1-2-6 ,itcan alsogo 1-3-5-6 or it can
go 1-4-6
so there are several routes,sowhichone isthe best, so the keypointisfromS TO D the bestcost
effectivepathisselection,andthisselectionbyroutingalgorithm
Routingisone of mostcomplex andcrucial aspectof packetswitched network, itplay animportantrole
innetworking.

2
Desirable Properties of Routing
1: Correctness andsimplicity:self-explanatory
to delivertocorrectlocation station, androutingalgorithmshouldbe simple, otherwiseitputoverhead
on nodes.
2: Robustness:Networkisqof packetsdynamically change with time, alsopossible nodefailure, so
underthe failure congestion sothatroutingalgorithmcansendpacketto its locationinthiscase.
3:Stability:Qof packetschangingin networksuppose thereistrafficinthispart, so routing algorithm
diverttootherpart maycongestion,so quick changingconditionitalsocan handle ,so itshouldcan
bearstability.
4: Fairness andoptimality: obviousrequirementbut confliction.
What isdesired eachnode ,stationhave each particularrouting,but some packetsgive priority ,but
thisisnot fairness,solike we give priority tosome adjacentnode ,butlongnodesdon’tgetfairness,so
there istrade off , givingsome kindof weightage.
5: Efficiency:Minimumcomplex,routing algorithmshouldbe simple not complexsothatitcan’t make
overheads, itshouldsimple thatItcan deliverpackettoitsdestination.
Design Parameter of Routing Algorithm
Performance criteria:numberofhopswhenpacketgo to one to node to othernode to itsD, it passesto
numberof hops, cost, if bandwidthishighcostis lessitinversely proportion,Delaydepends onsize of Q
, if in particulate packetif thisis large miserable delaywill there , throughput numberof packets
deliverperunittime …….These are variousparameterforperformance parameter
Decision time:whenitdesignitshould routing, perpacket(datagram),persession(virtual circuit) in
virtual circuitforparticularstation,all packetssendtothispath.
Decisionplane:whodecidetorouting,each node decide toselectionparticularpath
EACHNODE(Distributed), central Node(centralized) centernode whichdecidethe routing, originated
node(source) orsource node decide the routing
Network information source:there are algorithmwhichdon’ttake cost, topology none ,QLENGTH take
no othergatherinformation local ,particularnode gatheradjacentnode information adjacentnode , it
may be alongpath route nodesalong route ,or itcan be global a node gatherinfoof all nodesafter
several time tomake algorithmtablesall nodes.

3
Network information updatingtime:itcanbe continuous local whatcan info,all node periodic, major
loadchange congestionsmajorload change, topologychange.
So these are the designparameter which shouldtake inmindduring developingof routingalgorithm.
Routing Strategies
A large numberof strategiesare develop till now here are some popular
 Fixedrouting
 Floodingrouting
 Randomrouting
 Flowbasedrouting
 Adaptive/dynamicrouting
Fixed Routing
A route isselectedforeach source-destinationpairof nodesinnetwork.
The routesare fixedtheyonlymaychange if there ischange intopologyinnetwork.
That meanfor givingnetworkthe routingisfixed,
So howit is fixed?There are
FixedRouting:Example
A central routingmatrix iscreatedbased onleast-costpath, whichisstoredinnetworkcontrol center.
The matrix showfor each source-destinationpartof node, the identity of nextnode toroute.
From
Node
To Node
1 2 3 4 5 6
1 - 2 3 2 2 2
2 1 - 1 6 6 6
3 1 1 - 4 5 1
4 6 6 3 - 5 6
5 4 4 3 4 - 4
6 2 2 2 4 4 -
SUCH a bigroutingdirectory iscreatedinnetworkcontrol center.
Thishas a big drawbacks.If this NC centerfail everythingfail, soitisnot very reliable.

4
Otherapproach to thisisthat create directoryof each node, eachmeannode have copyof directory
From the mainrouting matrix, routingtablestobe usedby eachindividualnode canbe developed.
So thisis disturbed routingalgorithms
As directoryispacketreceive and sendittoits nextnode.
Questionishowthese directory created?
Least-Cost Path
That can be createdonleast-costpath.
A cost isassociated witheachlink.
The simplestcriteriaischoose minimum-hoproute throughnetwork
-easily measured criterion.
A generalizationisleast –costrouting, I.e. bandwidth,q length, distance
For any pairof attach station, the leastcostroute through the networkislookedfor.
Several waystochoose optimal path.

5
- Dijkstraalgorithm
-Bellman-fordalgorithm.
What theyalgorithmsdo, forgivingtopology fromsourstoall destination theyfindthylestcostroute
Dijkstra Algorithm
It findthe leastcostpaths fromgivennode toall othernodesinorderto increasingpathlength.
The algorithmworkinstatic conditiononthe topology andlinkcost.
These are basic steps:
-initialization;M={s} , Dn =DSN for n!=s
-findneighboringnodesnotinMhas least-costpathfroms include inM.
-update the leastcostpath.
Iteration M C(2) path C(3) path C(4) path C(5) path C(6) path
1 (1) 2, 1-2 2, 1-3 ------- ------- -------
2 (1,2) 2, 1-2 2, 1-3 6,1-2-4 ------- 3, 1-2-6
3 (1,2,3) 2, 1-2 2, 1-3 5,1-2-6-4 7, 1-2-6-4-5 3, 1-2-6
4 (1,2,3,6) 2, 1-2 2, 1-3 5, 1-2-6-4 7, 1-2-6-4-5 3, 1-2-6
5 (1,2,3,4,6) 2,1-2 2, 1-3 5, 1-2-6-4 7, 1-2-6-4-5 3, 1-2-6
6 (1,2,3,4,5,6) 2, 1-2 2, 1-3 5, 1-2-6-4 7,1-2-6-4-5 3,1-2-6
So fromthisyou can create routingtable for centerroutingor distributedsystem follow byleastcost
path Dijkstraalgorithm.

6
Fixed routing
 Advantages:
Simple, costgiven, leastcostpathgivenyoucan use it simple
Works well forstable loadnetwork
Same for virtual-circuitordatagram.
 Problems:
Lack of flexibility, if networkconditionchange itfail
Doesnot react to failure network, orcongestion condition
Flooding Routing
Require nonetworkanyinformationwhatsoever
Everyincomingpacketissendto all node exceptfromwhichitcome.
Do deliverapacketlarge numberof packetscopy generate these are alarmcondition

7
Advantages
All possible routinesfromSto D are tried.Soif there’sispath italwaysreachto its D. itsRobotsmeanif
any route failure packetbutwill reachfromotherpath.so its’ reliable.
All routesare tried,soat leastone packetgoestoshortestroute.
All nodes directorindirectly visited.
Problem
Generate large numbercopiesare generate whichmake congestion.
Suitable if use damping mechanismsothatlarges numberof packetsare not make.
Technique To Use
Hop-Count: a hopcounteris containinheaderof packetand it decrease eachone time whenpass
throughthe node and discardwhenitreach to zero.
The senderinitialize the hopcounterif notknownitissetto full diameterof subnet. Worstcase value.
Keeptrack of packetswhichare responsible forfloodingusingasequence number.Avoidsendingthem
out secondtime.
Selective Flooding
A variationwhichis slightly more practical isselective flooding.
The router don’tsendpacketstoin all directionbutinthe directiontothe destination. Give weightage
to check whetheritisgoingto D or movingawayto D.
Utilities Of Flooding
Floodingis robustness:incase of war or loador topology change undersuchcase thisis veryuseful
May be usedinvirtual circuitlike whenpacketreachtoD from least costpath it sendacknowledgment
and itsave.
Floodingalwaysusesshortestpathsince itexplore everypossible pathtoD.
Some time to messagesall nodessoit’s good.To upgrade infothishelpful
Ratherits disadvantagesit’salsohave imp utilities.

8
Random Routing
Thishas the simplicityandrobustnessof floodingwithfarlesstrafficload.
A node onlyselective one outgoingpathforretransmissionof incomingpacket.
The outgoinglinkischosenat random,excludingthe linkonwhichthe packetcome.

9
How You Do It Then?
If youit randomthenyou don’tneedthe infoof the networklike how manypacketsare inQueue
bandwidth etc.
Or you can do inanothermethodlike roundrobinfashioninwhichyouchose randomandchose a link
and nexttime youchoose otherlink etc.andreadto you destination.Soyou distribute the load.Butthis
some have limitationlike insteadof packetgoing towards destinationitmaygo towardssource side
So thiscan approx. overcome by.
A refinementistoassigna probabilityto eachoutgoinglinkandtoselectthe linkbasedonthat
probability.
The actual route will typicallynot be the least-costpath.
So here the Data rate isusedas networkinformation.Higherthe Date rate of particularlinkis
probabilityisselectedinthe network.
It has robustness because ituse higherdatarate pathso packetshall be delivertothe destinationbutit
alsohas a limitationlikeitdon’tselectcosteffectivepath.

10
Flow-Base Routing
So here we previouslyuse networking info, topologybutnotconsiderload.
An approachthat usesbothtopologyloadinformationforrouting.
Flowbetweenapairof nodesisrelativelystable andpredictable.That’smeanif you know the traffic
loadof a nodesanddata rate thenyoucan calculate the flow betweenapairof nodes.
For a givenline if the capacityandaverage flow is known,itispossible tocalculate tomeanpacketdelay
by queuingtheory.
From the mean delay of all the lines,itiseasyto calculate the flow-weightaverage togetmeandelayfor
the whole subnet.bythiswe use Dijkstraalgorithmandmake aroutingtable .soitalso fix,statictype
routing.
Thenthe routingalgorithmfindthe minimumaveragedelay.
Adaptive Routing
Routingdecisionchange asconditionon the networkchange.
Two principal thataffectingroutingdecision.
Failure:whenanode, linkfail itcan’tlongeruse asa route.
Congestion:whenaparticularareaof the network congested itisdesirable tomove the route packets
aroundthe congestion area.
So adaptive routingchangesdynamicallywiththe networkingcondition.
Classification onthe basicof informationsource:local,adjacentnodes,all nodes.
For adaptive routingto be, there mustbe exchange networkinformationamongthe nodes.
Typically metrics:
Numberof hops (simplestone butthe notuse i.e. forparticularS TO D how many hopspackets use)
Time delayinmsec(fora particularS to D, queue lengthisknow we can call the time delay)
Total numberof packets queued innetwork.
How muchof information:

11
More informationexchange betterroutingmore overhead
More frequentbetterroutingmore overhead
So there istrade off.
Draw Backs Of Adaptive Routing
Routingisdone dynamically changingconditionsoitput Burdon on switchingnodes.
So if networkconditionchangesveryquicklylike congestionthenwhatwill happenitproduce
congestion-oscillation. I.e.if there istrafficloadatone area we move the traffictoaround area then
whatwill happentrafficonotherareabecome congestive.
So thisproblemis solve by thushing.
Advantages Of Adaptive Routing
- Improve performance
- Can aidin congestion control
- Widelyused
Distance Vector Routing
Key characteristic:
1: Knowledgeaboutentire network.
2: Routingonlyto neighbor.
3: Informationsharingatregularinterval.
Each node maintainthe routingtable havingone entryforeachnode withtwootherfields;preferred
nextnode andcost estimate of distance ,basedonone of the matrices.
Network ID Cost Next Router

12
Link State Routing
Basic steps:
Identifythe neighboringnodes.
Measure the delayor cost to eachof itsneighbor.
Form a packetcontainall the information.
Sendthe packetsto all othernodes(flooding)
Compute the shortestpathto everyothernode (Dijkstraalgorithm).
Here in linkstate informationgatherisonlyfromitsneighboringnodesratherentire networklike
distance routing.
So the basicideais itgatherinformationto itsneighboringnode androute toall like flooding.
Andinformationsharinggatherisdone afterregularinterval.
Advertise ID NetworkID
(destination)
Cost NextRouter
So a linkstate packetformsand spreaditin flooding strategies.
So as informationisgatheratregularinterval everynode make some kindof itsdatabase andwiththe
passage of time thisdatabase become large. Anditas usesinformationgatheringatregularinterval it
needmore computational powerandmemory.solink state routingissome kindof expensivethen
distance routing.Howeverismore scalable thandistance Routing.

13
Multicast Routing
As we studyroutingisthe sendinginformationfromSto D. butin some case we have to sendsome
message toa group of peoples.Sendingapacketstoa groupof people isknownasMulticastingRouting.
i.e. Service providerlikemovies, TV channelswantto sendingparticularmessagestoparticulargroupof
peoplesthenthistype of routingisdone by Multicaststrategies.
To do multicastroutingeachnode computesaspanningtree coveringall nodesinsubnet.Firstwhena
packetsissendfirstnode findthe spanningtree towardsselectivegrouporDestination.Andafterthatit
sendpacketto fromthat spanningtree route. Anothertechnique isalsowe canuse like floodingwhich
we discuss recently.
Reference:
Data.And.Computer.Communications.8e.WilliamStallings
------------------------------------------------------------------------------------------------------------------------------------------

Paper on Routing

Recommended

Recommended

More Related Content

What's hot

What's hot (18)

Similar to Paper on Routing

Similar to Paper on Routing (20)

More from Mohsin Ali

More from Mohsin Ali (12)

Recently uploaded

Recently uploaded (20)

Paper on Routing