Autonomous System & Path Vector Routing
Hello, welcome to this course. We will continue our discussion on Computer Networksand Internet Protocols. So, we are discussing on routing protocols right as we discussedover this lectures. So, one of the primary objective of this overall network is route apacket from one source one node to another node in the internet right. So, and it may goon over several routers right. So, there are two things which is important: one is thatwhat is being routed right, the packet which is being routed.Another is that how this routing is possible right, how this routing happens. So, in othersense if we see, if you recollect that what we have seen that every router or inintermediate or in the internet routers every routers maintain a routing table. So, what itsays, that if the packet is for this particular destination then follow this particularinterface of the router right.So, in other sense what we see that our routing protocols primarily aims at updating thisrouting table or sometimes called forwarding table. So, if I get a get a packet with so,such destination, then I need to forward to this particular network; that is my objective.As we are referring to the analogy, like if I have a road network with different crossings,which acts as a forwarder or routers. Then, the person or the traffic person in the crossingmay help you that you say that, if I want to go to that particular destination which path Ineed to follow or what should be my next hop to follow right.So, this is this is the thing will do. So, what it needs to do that every this router or thetraffic man needs to be updated or maintain a table or lookup table a forwarding table bywhich, if say if we looks that this is my destination, this should be the network right. So,the protocol across this overall inter networking with helps in doing this forwarding orrouting of packets are routing protocols.Now, we will see subsequently there is a concept of autonomous systems. So that means,it is a good group of network or a portion of the whole network along with hosts and thenecessary things like their connectivity protocols and so on and so forth. It constitute aautonomous systems autonomous system. We will we will look into those things andthese autonomous systems usually under one organizational or administrative control.Like IIT Kharagpur along with several networks, routers, hosts, protocols running,connectivity defined etcetera for can form a autonomous system.That means, it is inside the things it maintains as a autonomous system. So, overall internetworking or a overall internet is of this type of autonomous systems or popularlyknown as AS. So, every AS has a unique number right so that it is identified. Now, yousee so, some of the packets need to be routed within the AS, some of the packets need tobe routed outside the AS right. Suppose, you are said sending some source to destination.So, destination can be within that AS only or the source and source and the destinationcan be different AS.So, for that we require something what we say intra domain routing sort of thing or interdomain route of things right, which is localized and which is more globalized right. So,conceptually you may say that the same algorithm may work across the thing absolutelyno problem, but there are issues of scalability, there are issues of time complexityetcetera. So, based on managing a small network is much easier than managing thewhole internet and type of things.Secondly, that internet works most of the things works on a cooperating basis. You maynot have control over whole internet working as such. So, you cannot you may not runthe whole thing at a surfaces right. So, what will, what we have started from the lastclass, we will be continuing that we look at the intra domain routing right. Primarily, wetoday we would like to look at the intra domain routing which has two specific primarycategory of distance vector and link state type of protocol right.(Refer Slide Time: 05:11)So, as we discussed if we look at the dynamic routing protocol. So, that is anotherconcept of static routing; that means static routes as specified, but if we look at thedynamic routing protocols. So, we have intra domain or inter domain and inter domainhas two things, that two group of protocols. One is distance vector, another is link stateprotocol.One a very popular protocol in distance vector is the RIP Routing Information Protocolor the in the Link state is the OSPF protocol for the in the link state whereas, in the interdomain we have a concept of Path vector routing. And, one of the very that majorprotocol will which predominates is the BGP or Border Gateway Protocol right. So, thisway we segregate, we today’s talk or today’s discussion will be primarily hoveringaround distance vector and the link state protocol right.(Refer Slide Time: 06:19)So, just to quick recap. So, if we have a routing protocol one can be a static route that thestatic route uses programmed definitions representing paths through the network. Thatmeans, already programmed or already defined routes or it can be a dynamic routes.Dynamic route algorithms allowed router to automatically discover and maintain theawareness of the paths through the network right. The difference between these protocolsis the way they discover and calculate the routes to the destination. So, everybody’sobjective is to update the routing table to a individual router, such that the packets areforwarded optimally.The different routing protocols which they differ is primarily that in what sort of howthey discover these routes. How they calculate the new routes etcetera. Why this isrequired? The, what we see that the internet is a dynamic phenomenon. The packet thatthere are means routes being added or deleted in dynamically right. And secondly, this isnot under a single administrative control overall right. So, you need to have update youneed to update individual or a router needs to update its routing table dynamically basedon that how what frequency and other objectives are there.So, to in order to maintain a appropriate routing things. Again, though there arepredominantly distance vector and link state at the predominant protocol. There are sorrythere are three distance vector link state as the inter domain. And, path vector protocol isthe inter domain whereas, there is another protocol called hybrid. It is not a newprotocol, but mix of this sort of things that also people use. But, that is mostly used insome sort of a proprietary or more regulated scenario.(Refer Slide Time: 08:23).So, we will see that distance vector each router in the internode maintains a distance orcost from itself to its neighbor. So, it is more localized like a router only look at the lookor maintains and share the information about the, its neighbors along with the cost. Thisor sometimes we call that distance of the things. The path represented by the smallestcost become the preferred path to reach the destination right.So, if there are more than one path for the destination the minimum cost path will betaken these information is maintained in a distance vector table right. The table isperiodically advertised to each neighbor and each router processes this advertisement todetermine the best paths. So, what happens that every router has a localized informationabout his neighbor and the cost and it goes on advertising right. And, the neighborslistens and go on updating the things.So, there is a period of advertisement that is how periodically it is done, one maybe oneis every 30 seconds and so. And, along with that there can be thing that, if there is anychange the it will be advertised. Based on this input and that already packet available toit already the table available to it the a particular router updates the routing table. And, inway it is some sort of a this sort of whispering goes on into the whole internet or whole Ito say autonomous system or and then it goes on updating right.Whereas, in link state each router advertises a list of all directly connected network andassociated cost of the link. Or, it tries to look at the whole network or the portion of thenetwork in the autonomous systems. And, it advertises the what is the link state it saysright. This is performed through exchange of link state advertisements or popularlyknown as LSAs - LSA with other routers in the network. Using these advertisement eachrouter creates a database detailing the current network topology, the topology database ineach router is same.So, in other sense the every router advertises the what way the networking overallnetwork state or the picture is there to the rest and it goes on updating and, at any pointof time ideally the routers have the same picture of the network under its under itsdomain or under its where in the region it is there. Like in the AS or the area in the AS,where it is there it has the whole picture. Based on the thing it calculates the how to go tothe destinations. So, one is more localized only with the neighbor, here it has a globalpicture of the things.(Refer Slide Time: 11:25)And, in case of a path vector it somewhat somewhere in some of the literature say it issomewhat similar to distance vector, but not exactly. But, there is a thing instead in casein path vector we have destination, distance to the destination, and the that what is thepath to reach the destinations right. So, it is not the which is the next networks, but whatis the path in the rest of the to reach the destination.Or later we will see that we need to talk about BGP, BGP and all those things then youwill see that the it says that this that the ordered set of autonomous systems which therouter need to pass to reach to that particular destination, if it is a inter domain routing.And finally, the hybrid protocol this protocol attempt to combine the positive attributesof both distance vector and link state. So, networks using hybrid protocol tend to covermore converge more quickly and so and so forth. But, most of the cases it has be it hasbeen seen that in order to maintain these both this type of things you require some more Ishould say hardware or resource support.And, in most of the cases if you have a more controlled environment or what we sayproprietary environment that is this may be much useful. But, but in number of cases wedo have those type of things. So, this can be followed. So, these protocols potentiallyreduce the cost of link state updates and distance vector advertisement and try to have aoptimized path along the things.(Refer Slide Time: 13:11).Now, so if we have a is typically a scenario like this where there are different networksconnected by different routers A B C D like that.(Refer Slide Time: 13:23).And then so, if we look at the distance vector what we have discussed so, A says thatperiodically says the knowledge about the about the whole network to B E F. So,whatever it has in having the knowledge its send is to B E F to its neighbor. Similarly, incase of B periodically send my knowledge about the whole network to A and C.So, whatever it is having the knowledge about the whole network it share with itsneighbor. So, some sort of a whispering with its neighbor right. It goes on doing that andin order to do that it attempts to converge right.(Refer Slide Time: 14:05).Look at another example like in a distance vector each node share its routing table; thatmeans, the knowledge about the network with its in immediate neighbors periodicallyand when there is a change. So, it is either it will be a periodically; that means, every saytime period t and when there is a change. So, if there is a change, then it also exchangethe thing, like A B C D etcetera.So, A have the knowledge that from A to A the cost is 0, A to B is 5, A to C is 2, A this isthe first table is the A’s table right, A to D is 3 and A to E is 6. Now, A to E is 6 via C. So,the next stop is C. This blank means the next stop is the immediate either itself or itsimmediate neighbor. Similarly, if you see the cost of D you can deduce that A directly toA as 3, but to B it has to go via A.But, to so, it next stop is A then B, but it could have been A C B also based on thecosting. Like from for C it has to go via A and then C, similarly for E it has to go A thenC then A. So, A to D to A is 3, but for going to A to E is via C is 6. So, overall costing is9.(Refer Slide Time: 15:51)So, initially so, if we look at initially, what is happening? Initially, if you look at A for Ait what is see that to itself is 0 A’s table, to B is 5 because, that is directly connected. To Cis 2, to B is 3 and to E is infinity, because it know does not have any information about Ethat is not directly connected.So, this when the router say time t equal to 0, it has these are the instances. Similarly, forB is like this, for B is something like this, C for C is something like this, D is only it isconnected to A. So, D knows that to reach itself is 0, reaching to A is 3, it is directlyconnected. But however, going to any other network or any other routers it is the infinity.
Autonomous System & Path Vector Routing-Part 2
Now, when it advertise say we look at the A’s table right. So, A receives A instance alsoC from C what it is receive, it to for C to go to A is 2 B 4 C 0 D infinity E 4 because, itdoes not have any knowledge about the D initially right. So, A receives say informationfrom C, similarly it receives information from B also right at periodic information right.Now, on receiving say we consider only one that C, subsequently it will come same typeof activity will go for what it this is from B. Now, on receiving it compares that so, in forif it goes via C reaching A will be 4. That means, it says that A to C is 2, C to A is 2 right4, but wherever it has a better hosting thing like A to A is 0 it is having. So, it updates isA 0 with no hop. See in order to reach B C says that it has a thing called 4.So, what it what it say is that in order to reach A to C is 2 and C to B is 4. So, in order viaC if it goes, reaching B is 6. It has a better advantage out here reaching B is 6, itmaintains at 5 right. Similarly, going to C via C it has 2 and now here also 2 so, it keepsthat. For D, C do not does not have any information because C is not having anyinformation. So, but A already having that reaching C is the it maintains that. For E, Csays that via C that it is a there is it can go by 6 whereas, A’s initial table says it was theinfinity. So, it updates as the thing.So, the C is so, the A’s table, A’s routing table after receiving the information from C itbecomes like this right. Now, similarly it will receive the information from B also. So,that updated table can be compared with the B, it can be before or after. Nevertheless,what you what we see it finally converges to the things. But, if it is very dynamic or insome typical cases there may be situations where you may end up in, what we say nondesirable states right which you do not want to be there right.So, what I encourage those who are learning this thing in for the first time or not verymuch accustomed with this try to find out these tables yourself right. What will be theupdated table for B from the initially or E and how it goes on right. It is easy if you do itwe I also tried that all references along with the things you can consult those books andtype of things.(Refer Slide Time: 20:15)Now, there may be some problems right. Like let us see that there is one is two nodeinstability problem right. Why, what is happening? Now, see if this is the network orportion of the network right, let us consider this is the our networking consideration. So,A for A table reaching X was 2 and it is directly connected alright. Reaching B for B instable reaching X was 6 and it is via A and nevertheless it is other things are there. So,dot dot dot that means, it has other information we have only, we are only consideringthese three nodes.Now, after failure that means, there is a link failure between A and X. So, what A updatesthat reaching X via A is infinity right. So, there is no connection. However, still there is aB is still get yet to get the update from the thing right. So, if it A receives a update fromB during that time. So, what it does? It sees that though there is no path for 2 X directly,but there is a it seems a there is a path from A to via B. So, it updates so, A to B is 4 andB by virtue of these says that in order to reach X it is still having that 6 entry right.So, what it does? It goes on X to it says that it you can reach X via B by 4 plus 6 10right. And, though only looking at the three nodes may be little, you may be littleconfused that why what is the big problem. But, if you look at the whole internetworkingsituation or a large network so, this can very much happen based on than when you arereceiving this beaconing or the messages etcetera.Now, subsequently A B updates through A and find that it is 10 plus 4, 14 and goes on.So, long they do not end up in a infinity; that means, non reachability finally, it goes onthe things. So, these goes on a two node level instability. So, this is a typical situationwhich may arise in this sort of scenarios.(Refer Slide Time: 22:45).There can be a option of a problem of what we say three node instability right. So, thereare three node A B C, A is same thing A is connected to X via with a link of 2. Then whatwe see after A sends the route to B and C, but the packet to C is lost right. So, what isthat there is a failure out here, A gets to infinity and A updates the thing. So, B also getsthe infinity, but somehow the packet to C is lost you know.So, C its still keep that X 5 A right. So, and based on that in the next round getting theadvertisement from C, the other tries to update. B updates as 8 right, getting a updatefrom the B, A finds that there is a path to X via B right with a 8 plus 4 12 and it goes onincreasing like this right.So, this is another problem of three node level instability right. So, there are issues whichneed to be addressed when we look at the this sort of link state type of scenarios. Sorry,this distance vector type of scenario. So, these are what we are discussing about distancevector routing, where it whispers to the neighbors.(Refer Slide Time: 24:25)Now, a another routing protocol where which take which keep the inter first of all intradomain routing protocol, which keeps the track of the which keeps the track or whichkeep the state of the whole network is link state routing right. So, the basic philosophy isa link state is a description of a interface of a router; that means, IP address may besubnet mask, network type and so on and so forth and is connectivity to the neighboringrouters. Or in other sense I so, we can look at that it keeps a network graph in a senseright.The collection of these links link states form a link state database. The routing algorithmsuse this principle of link state to determine the network topology. So, in other sense theevery router keep track of the topology of the whole network right. So, link stateapproach to determine network topology, if we look at; each router identifies all routingdevices on the directly connected network right that is easy.So, whatever the it is directly connected. Easy router advertises a list of directlyconnected network links and is associated cost links; through a exchange of link stateadvertisements or LSAs right with other network right. So, it has a each router advisedthe LSAs. Why in this advertisement each router creates a database detailing the currentnetwork topology. So, by looking at this advertisement or receiving this or using thisadvertisement, it makes the network topology.The network topology in each router is typically or ideally should be same right, eachrouter should be same. Each router uses the information in the topology database tocompute the most desirable routes to the each destination. So, in other sense it goes onadvertising these link states that whatever the connectivity information is there. So, eachrouter gives the information and make the network topology of its own.And, they using this database, link state database or the topology it constitute or it findsout that what is the optimal path or optimal route to the destination network right. And,this information is used to update the routing table finally, it updates the routing tableand it goes on that, if this is the destination this is the route and this is the interface to beused of the router. So, that is the routing table update because, when the packet comes itgets stored and forwarded based on the routing table.(Refer Slide Time: 27:33)So, in the same way if we look at that same type of network. So, what it says that I sendinformation about my neighbors to every router. I send information about my neighborsservice so, everybody sends information and other things and every individual nodes thatthe router constitute this. Or update its link state database and realize the networktopology and find the best path based on this topology.(Refer Slide Time: 28:07)So, similarly like what you are seeing the link state things. So, individual router has thissort of instances of the network right, at a particular time. And, then a they take a callbased on this topology. Find out the best possible path and update this routing tablewhich is used by the packet forwarding.(Refer Slide Time: 28:35)So, same thing link state knowledge as states of the links that how that connectivity andtype of things are there. These are the different link state knowledge of the individualrouters.(Refer Slide Time: 28:51)And, then it can use some sort of spot algorithm, the popular algorithm like extraalgorithm can be used. So, like the this already we know that how this algorithm was.Now, once for this algorithm to work and find out the that optimal path or the shortestpath, we need to have the whole instance of the network. So, said route to the local nodeand move it to the tentative things.And, this is the, and if we have the tentative list is empty then stop. So, long then as isnot empty, it goes on iterate like this; like among the node in the tentative list move theone which is the shortest path to the permanent list. Add each unprocessed node in thelast move node to tentative list, if not already present. If the neighbor is in the tentativelist with in the tentative list means larger cumulative cost, replace with new one right.(Refer Slide Time: 29:55)So, this is the standard way of looking at it and if we construct that shortest path tree persay. So, the tree will look like this one right. Initially, the topology is like that initially thesay the route to A and move to tentative list; move A to permanently list and add C these.Then, if move C to the permanent list because, it is the least path from the A and so andso forth.And, finally, we end up in the position 6, where our tentative your list is empty and as thealgo says it stops. So, it finds out the overall 3 and this can be used for updating therouting table or the service forwarding the packets to the next destination or rather nexthop to reach the destination.(Refer Slide Time: 30:51)So, in doing so, if we see the routing table of A’s routing table. So, no reaching node A iscalled 0, B is 5, C is 2, D is 3 and E is 6 via C right. So, this is the table which is beingconstructed from the, from using those information. And this the updated table can beused for forwarding the packets.(Refer Slide Time: 31:23)So, if we try to summarize this link states. So, share knowledge about the neighborneighborhood, share with every other router, share sharing when there is a change right.So, one of the popular link step of routing protocol is the OSPF: Open Shortest PathFirst, which uses is in state protocol to update table. And, OSPF if you see that it is a in awe will see later on. It is the popular protocol or inter domain routing protocol, which isused in as for intra domain routing in the in within the AS or a with in the areas in the ASright.So, this follows the link state routing. So, what we I have seen that the broad way of howthis distance vector and link state works. And, the popular protocol for your distancevector is RIP and whereas, this in case of a link state it is OSPF. So, with this let usconclude our lecture. We will be continuing our discussion with this intra domain andsubsequently inter domain in (Refer Time: 32:45) subsequent lectures of this particularcourse.Thank you.
Log in to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Networks and Internet Protocol online course
Sign up to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Networks and Internet Protocol online course
Please enter you email address and we will mail you a link to reset your password.