Loading

Module 1: IP Routing

Notes
Study Reminders
Support
Text Version

Routing Protocols

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Routing Protocols
Hello. So, we will continue our discussion on IP Routing in our Computer Networks andInternet Protocol course. So, last day or in the last lecture I should say, we discussedabout this IP address and allocation and how the routing come into play. So, today wewill be little more going deep into the things. We will be having some basic introductionto this inter Intra Domain Routing and in the subsequent lecture we will be going to moredetail about the routing protocols right.(Refer Slide Time: 00:54)So, when we talk about routing just to have a quick recap of the things or somethingalready you know. So, one of the major feature or one of the major aspect ininternetworking or our communication between 2 network 2 device connected on thenetwork is to forwarding, right, moving packets between ports right. So, in this case weare looking at the network port. So, it can be from the host one end one host to other,intermediate host to router, router to router, router to host and anything. So, how thingscan move.So, it may be on a single hop distance. It may be on a multi hop distance. So, it can bedirectly connected, or it can be connected over a large network. So, look up destinationaddress in the forwarding table. So, as you remember in the last lecture we discussedabout the routers basically maintains a routing table. So, that means if it gets a packet fora particular destination it says that it forwards a packet to a particular path or particularso, to say port or next destination or like that, right.So, it has a routing table which has all ideally all the destination possible destinationsand what should be its next hop or what should be the path to be forwarded, right. Or if itis in the in, let us in the we will see that one in subsequent lectures when we talk aboutlayer 2 and type of things. Find out the find out port or output port and MAC addressright, what is the port and MAC address pair right. Finally, what we will what we knowthat it finds a logical path; that is, at the IP level. Finally, in order to packet in order toforward the packet, we need to get that hardware address or the MAC address of thedestinations.So, that is done by this some address resolution protocol, we will come to that. So,routing is a process of populating. If you look at that what is other way of looking, one isforwarding another is the routing protocol, right. So, one of that that it is a process ofpopulating the forwarding table or the routing table, right? So, again I repeat. So, routeris a layer (Refer Time: 03:21) 3 device which has a lookup table or routing table orforwarding table interchangeably we are using. And if a input packet comes to for somedestination it concerns the routing table that where it need to be forwarded, it forwards it.Now, overall inter network is a large network and that is dynamic and so and so forth.So, in other sense the router one of the objective is to maintain this routing table. Howthis routing table will be updated so that, any packet comes it gets that correct path to beforwarded, right.So, the router exchanges; so, in order to update the routing table, the router shouldexchange messages about the network they can reach, right. So, a if a router 1 isconnected to the router 2 and router 6, 7, 8, so, these routers exchange messages whothey are network they are connected, and the other things gets updated. So, find what ismy objective thing? Find the optimal route for every destination.So, given a destination or given a destination finding the optimal route in the for everydestination. Like, if we try to look at the analogy finding the if I am going visiting aplace, so, one of the objective is that find the optimal route to visit that, to reach thatparticular destination. So, optimal route maybe the shortest distance, I may look for lesscongested route. I may have some other criteria. Like, I want to travel through a routewhich is safer and type of things right. Nevertheless, based on my criteria I want to findout that what is the optimal route from this source to the destination or for that particularrouter to the destination, which way I should proceed.(Refer Slide Time: 05:17)Now, if we look at, so, routing algorithms; so, it is getting some local forwarding tablesare there. If these are the some for our discussions say, these are the different headervalues then these are the links which will be forwarded right. If it is 0100 to 3, 0101 to 2,0111 to 2 and so and so forth and I have that. So, given a header value if this one, itconcerns this table and forward it to 2.So, one is this objective of the forwarding the packet is one of the work of this particularrouter. Another, this table needs to be updated for this router, right and every router hadtheir corresponding table and is goes on forwarding the things. So, what we try to argueif somewhere or other, if these tables are maintains properly or they are able to updatethemselves in a proper in a regular fashion then, the packets can be routed fromanywhere in the internet to any destination, right, any source to any destination throughthis different router.One thing we should keep in mind in when we will talk about internetworking these aresome sort of a, so called distributed system. And most of the cases they are looselycoupled or quote unquote autonomous system, right or several autonomous systemthough they are at domain control, will come in this subsequently in this. So, in othersense I do not have a control that what that other router will do. It if it is the router is inmy domain then I have some control. But, most of the cases if it is in the other domain Ido not have any control. So, that is some sort of a message exchanging are going on andthen and this routing table is getting updated. If these routing tables are updated, then wego on hopping the things.(Refer Slide Time: 07:15)So, one of the issue which come into play is the stability, right. So, stable routers areoften preferred over rapidly changing ones. Or that in other sense, the routers where therouting table is stable right. So, that the exchanges are much faster etcetera. If the routingchange because, based on the routing table or this lookup table, these packets are routed.So, if it is very dynamic it is unstable then the whole thing is unstable. So, that is oneimportant aspect of the things, right. And there are several reasons. One may, is thismanageability will be better right, hard to debug a problem if it is a transient right. So, ifit is a if I if it is very dynamic and something at the when it is updating getting changedetcetera, there will be difficult to problem to manage this overall process. And if it is alarge network then it is a or scale of internet, it is a very difficult thing.Second reason is that higher layer optimizations like TCP RTT estimation like, as youhave if you remember when this in this particular course we discussed about this TCPand round trip delay and type of things. And there will be challenges there. So, imaginealters. Suppose it is alternating every 500 millisecond or 50 millisecond or 5 millisecondroutes and then how things will be there.So, I need to, so, more I look for the stability then, I am less on the optimality, right. So,if it is optimal things means, at that time I want to find out a solution which is theoptimal solution. And for that, I may need to be more dynamic or in other sense we arebasically fighting between stability and optimality, right. I, if suppose ideally if nothingis changing then, it is a most stable. Say, for hours together nothing is changing. But, youmay not get a optimal thing. But, if I allow it to change every now and then when there isa change then, it is more optimal. But, then the stability is hampered and that may causedifferent other issues.So, there should be some way of looking means need to be optimized and things. Andthat is why when we talk about performance analysis of the network and several othermatrices then, we talk we try to look at that what amount of the stability, optimality andetcetera we are looking for.(Refer Slide Time: 09:48).So, what we see? So, we have routing algorithms. So routing algorithms primarily whatit does? It basically allow me to maintain this routing tables right, individually at everyrouters and now the routers becomes independently once it gets a packet and goes outand so and so forth. So, there can be global or some sort of a centralized taking a call, ataking the global consideration or it can be decentralized right. In global, all routers havethe complete topology. So if I had the whole topology of the whole global scenario then Ican make a optimize scenario right, but it may be possible over a small network, but itmay not be possible on a large network. Whereas, in decentralized on the other hand,only know the neighbors and share information from them right.So, I only know the neighbor. So, if the router RI, know it is only neighbor JKLM and itshares information about the thing. Similarly, another router RJ takes the things andgoing on, so it is a decentralized person. So, I am not looking at the whole world or thewhole network and taking a call, but more taking a call taking at the at a only the localneighbors.So, that is one, so we have a option of intra, that is 2 way of routing will be intra domainand inter domain routing. So, inter domain all routers under the same administrativecontrol, when we say intra domain, it is under the same administrative control. It may belarge network; like in IIT Kharagpur, we have say around 50 odd networks under, butunder the control of IIT Kharagpur itself.Whereas, inter domain which is decentralized, scale to internet, so huge amount ofnetwork and etcetera which are to the scale scale of internet. So, these are inter-domain,so these are the broad category of the things. We will come back to those things shortly.So, we have 2 type of broadly routing, one is inter domain and one is intra domain. Intradomain is somewhat all routers under the single administrative control like, IITKharagpur network or any such networks or whereas inter domain is decentralized, solike scale of internet and type of things.Now, as we understand these 2 aspects has 2 routing and phenomena has different type ofconsideration so right. Once you have everything under control you have a way oflooking at the problem or the routing algorithms and if you have that it is a decentralizedand not under a single administration we have to do. So, today we will be looking atsome basics of inter domain, rather again, the in subsequent 1 or 2 lectures we will belooking at the intra domain and then we will talk about inter domain routing right.(Refer Slide Time: 12:51)So, before that we take up few couple of issues to show that we understand that what isthe challenges right, one is the issue of optimality right.So, I can look the whole network or the in the portion of the network under considerationas a graph. So, nodes are router and links are your edges and then the edges has can havevariable weight based on different considerations, it can be the conjestion level and orlength of the distance and a different type of consideration we can have right. So, assigncost to each edge based on latency, bandwidth, utilization, queue length etcetera etcetera,right, so this can be the cost to edges.Now, our problem is finding the lowest cost path between the two nodes. So, based on amy our, my metric or our metric under consideration I want to find out the least cost pathbetween node a and node b or node source node and the destination node. So, each nodeindividually computes the cost.Now, if each routers had the capability to compute the cost and in a distributed fashionand then I find out the overall cost of looking at the things right, this is now what Ilooking at is a optimal solution but, it may not be possible to always get a optimalsolution, so we can go for suboptimal solution. In some cases, we will see that a conceptof default route is there. If I do not found a right route, then I may have a default path toforward the packets.(Refer Slide Time: 14:41)Other issues which are definitely come into play is the scaling issue, like how it scale,how the algorithm scale. So, each router must be able to forward based on anydestination IP address. So our bottom line is that whatever is the destination IP addressthe router should be able to forward. So, given the address it needs to know the next hopconsulting the routing table or the forwarding table. So, it has to know that where itshould go next.So, one of the naive approach maybe have a entry for each addresses right, one that I canhave entry for each addresses but however, that will be a usually there can be hugenumber of entries there right the to the scale of 10 to the power 8, 10 to the power 9 typeof entries, if you consider the all systems etcetera across the across the domain right. So,it will be huge number of address, then that is that may not be practically feasible.So, one solution may be entry covers a range of addresses right. So, I have a thingswhich covers a range of addresses, like out IIT Kharagpur router takes care of the rest ofthe 20,000 odd systems within the campus right, systems in the sense systems, devicesetcetera network enabled devices within each domain right but, for the external world itlooks at only 1 router or maybe 1 or 2 routers which are looking at the things right.So, that may be so I do some sort of a address aggregation on the things. So, one is thatwe can’t do this sort of things if the address are assigned randomly right like, ethernetaddress or hardware address which comes from the manufacture we look at when in oursubsequent lectures. So, we cannot do something which is randomly assigned right.Address aggregation is a important aspect which we are looking at address allocationsshould be based on network structure. So, I can aggregate addresses provided that is thein the network structure.Now, if you look at some a type of analogy when we look at our normal postal addressesetcetera, we are able to club them together because, there is a sense of inherentaggregation, if it is a randomly things then making things very difficult like, if the housenumber 1, 2, 3, 4, 5, 6 etcetera are closely in a particular locality then sending theparticular forwarding that letters or sending letters with the postman is easy. But, after 1if it is 101, then 49, then 216, then it is very difficult to pack them together or things.
Routing Protocols- Part 2
So,that it is that, otherwise what we require is that some sort of a that addressing mechanismitself favor this aggregation. So, that may be one of the requirement of the means, one ofthe way of looking at it. So, aggregation is important.Now, let us come back to our basic problem. So, what we have seen these are some ofthe things which we try to address that scalability, optimality, stability and of the severalrouting protocols and if we look at the other way this, again come back.(Refer Slide Time: 17:57).So, what we have that we can have a way of direct delivery say, 2 systems are connectedby a cable and then I directly deliver one packet to another right, or I can have indirectand delivery system right or I can have multiple things.So, I have in this case a router which forwards the things etcetera and there can bemultiple where the routing come into play.(Refer Slide Time: 18:21)So, one route method that if I want to I can have a lookup table like, that if I want to goto a particular host, this is the series of things I need to do router 1, router 2, then host Bright. So, it is explicitly specified that where things are there so, this route method isexplicitly specified that, this is the route by which you. Other way I can only say that it ison the next hop, I only specify the next hop, the next hop takes care of that where itshould go right, that in the routing table of A, in order to go to host B in this for host A,the it says that in order to go to B, you need to go to router 1. Router 1 says in order to goto host B, that is the router 2 is the destination or the next hop, I should say next hop,routing R2 says that it is connected with this particular network, so we can directly thereis no next hop, you can go directly go to the things.Now, you see this is the next hop-based things so, individual routers R1 and R2 theymaintain that routing table, that given a destination where it should be pushed right so,that is next hop-based thing.(Refer Slide Time: 19:40).Then, we can have host-specific versus network-specific, last class if you remember, weare looking at that it is router is primarily between networks to network, not meant forhost to host right it is not like that, cannot be done but, it is mainly for network tonetwork.So, if it is in the particular router a host is on the host specific method, if it is destinationis A then, R1 is the next hop B is R1 C R1 and D, R1, so for all things are there and forrouting table for host A is based on the network specific thing that, in order to reachbecause, A B C are all connected to this network N2 so, it has a one thing if it is anetwork, that in order to reach N2, that R1 is the next router right.So, this network definition so, instead of taking individual host I take, we consider herethe network where the host are like and then I forward the packet on the based of thenetwork right.(Refer Slide Time: 20:57).So, there is a concept of default route. If I cannot find something where to be forwarded,then where should I forward? So, there is a default route like, in order to go to networkN2, push it to R1. In order for any other network, push it to R2 right, so, this is a defaultroute. So, there is a concept of default route if it is if it cannot find that where the routingtable things are there, it will put it to the default route.(Refer Slide Time: 21:25)Now, if we look at the basic modules or very fundamental structure of the a particularrouter - so once it is received a packet you need to extract the destination address fromthe IP address. So, these are routers are as I, as we discussed earlier that these are layer 3switch which has enabled up to network layer. So, it opens up to the network layer andextract the destination address and the next-hop destination address and the next-hopaddress and the interface. So, it extract the destination address, search the particularrouting table or the forwarding table and find out the next hop address and the interfacenumber, like it has to go to that particular address and to the interface number right andwhat happens when I want to push the packet to the things, I need to know the MACaddress or the hardware address of the of the next hop. For that I require a ARP protocol,so that we will discuss later on. So, ARP protocol, so that I know that what is the nextaddress and push it the things. So, in other sense I have some sort of a net mask, networkaddress, next hop address and the interface of the router where it need to be pushed.(Refer Slide Time: 22:46).Like here what we are having, there are several network like starting point, 180 70 65slash 25 here 201 4 dot 16 dot 0 and it is connected with different interfaces of thisparticular router right. So, it connected to the different phases of this router and there canbe a default route, may one of this interface right.So, these are this is a connection for 201 dot 4 dot 16 dot 2 slash 22, 180 70 slash 25 andso and so forth and there can be other router, sorry other router connected to this type ofinterface.(Refer Slide Time: 23:35).Now, if I see for router R1, if we look at if it is a slash 26 type of net mask with thisnetwork address then, the next hop is m2 right ok.So, if you look at so, slash if the net mask is slash 25 and the network address is 180 7065 128 then, the next hop is m0 right, similarly, so and so forth. So, slash 24 201 dot 4dot 22 dot 0, it is m3 right so, this is this is the address that it goes to this network right201 4 22 0, the next is slash 25 in the network, it should have been m3 out here there is atype here, not type that m3 came up into the this particular interface.So, in other sense the routing table of this what it says when it is this net mask so, whenit is gets a packet it checks with this net mask, if the address matches, it push it to thatparticular things right. So, I get a get a input packet from somewhere then, I extract thatparticular destination IP, do a masking, if the address matches with these networkaddresses, just put it push it to their interface. If it does not matches then, it push it to thisdefault interface right.(Refer Slide Time: 25:19).Like, some example forwarding process if the packet arrives at R1 in which thedestination address is 180 70 65 140, right.So, if it is there so, it does at slash 26 because, as you remember so, you on the longestprefix first right. So, 26, 25, 24, 22 so, first it does a it has 26 applied, the result is 180 7065 128, you can apply those this type of mask that that means, 26 1 followed by theirzeros and apply to this that the value will get that these values and this does not matchwith the corresponding address right, then it goes to the next slash 25 and it gives a valueof 180 70 65 128 and it matches with the this one, the second entry of the thing.So, it push it to the m0 right. It matches with the corresponding and the packet isinterface m0 passed to the ARP for further processing. Now, what m0 interface, in orderto go to this m0, what it has do, you need to find out the hardware address of thatparticular interface so, it does a ARP resolution, address resolution protocol right. So, atthe ARP typically changes a map say, IP address to a hardware address so, if it goes for aARP request, it returns that what is the hardware address of that particular device, so thatpacket the frame at the layer 2 level can be forwarded.So, your so, ARP things will be discussing later so, we need not immediately botherabout the ARP. But see, if a packet comes first it follows these things in the in this orderright, as we know that the we want the longest prefix match, so, 26, 25; first 26, then 25,24, 22, if does not match go to this default right.(Refer Slide Time: 27:16)So, say another example. So the forwarding process if the packet arrives at R1 with 201dot 4 dot 22 35, again do with a 26, is come up with a result 10 2 1 dot 4 dot 22, it doesnot match with the corresponding, there is no corresponding this, It then goes for the nextslash 25 and does not match with the row next entry, does a third one in the 22 whichmatches with the corresponding right and then it goes to the this one destination, that itgoes to the particular m3 and the at this particular resolution again will be done right.So, what we see here that given a packet and given this type of net masking and lookingat this I can basically forward the packet to the particular, to that particular destinationinterface and there is a address resolution; that means, I need to know the hardwareaddress to forward the packet of the frame at the layer 2. So for that as, resolution isrequired. But the primary routing reason is taken care by this thing right.(Refer Slide Time: 28:29)So, what we see there is there may be a need of address aggregation right, like in thiscase a organization 1, 2, 3, 4 may be taking service of a ISP and have different type ofnetwork addresses right. So, I instead of having all those entries I can have a particularnetwork address and then I can have a next hop type of things.So, I can so, in this particular thing I can have a entry like slash 26 if this networkaddress is this, next hop is m0, m1, m2, m3 and m4. Whereas, in the routing table 2, Iidentify that all those things as a single network as a slash 24 and it push it to the m0. Inother sense, for this rest of the word or these routers R2, this is aggregated as the as asingle network as with a mask of slash 24, 140 24 7 dot 0 slash 24 and any packetcoming with that it will be forwarded to this packet right.So, this is the way of looking at the things. So, these address aggregations helps us inclubbing these two, all this together for the rest of the so, you see for the entry of the R2becomes much simplified right. So, if instead of these 4 organization, in 400organizations such like this things that will be it will be heavy, a huge load on this typeof router and the processing time will be much higher because, it need to go to thisscanning these things.So, we will be going little bit on the that how these routing structures are there, there arebackbone routers and other type of things but, nevertheless these are the differentautonomous system, very loosely if you would like to see and these are differentnetworks, they have a bunch of routers and type of things and they can, they have theycan communicate between each other.So, more you we say this built in the ASes or what we look at is a some mostly as apolicy-based routing, whether within the autonomous system there is the local or intra,the autonomous system individual autonomous system has the authority or total controlover the network and decide on the routing.So, finally, we come to that intra domain routing with a, within an AS so, singleadministrative control: optimality is important, within the thing that optimality isimportant factor, contrast with inter-AS where policy dominates whereas, we will seethat in our next subsequent not in the next lecture, subsequent lecture that inter routingprotocol BGP where we will look at that policy-based routing or the inter-AS andpredominant intra domain routing algorithms.And just to have a view of this distance vector routing, so, every in a distance vector,each node shares its routing table with its immediate neighbor in a periodical periodicalin a periodical manner at every time interval say every 30 millisecond or so or based onthe things and when there is a change.So, if we initialize at the initialization at the initial step for A, where nothing is knownsay A starts up so, for A to A 0, A to 5 because, these are connected but, A to E, A doesn’tknow where E is so, it is infinity.So, when gets A, but, it C knows where E is with 4. So, next time it gets the beacon orthe miss update from the C, C is router update then, it updates it with the things. Howthese update process will go on, we will discuss in our subsequent lecture. So, this way itgoes on doing that. So, we will be discussing more detail on taking into these interdomain routing looking at different RIP, OSPF or distance vector and link state routing inour subsequent talk. So, let us stop here and with that basic understanding of what isrouting, what are inter domain and inter domain, intra, inter domain routing and in thesubsequent lecture we will we will discuss in detail those things.Thank you.