Loading

Module 1: IP Routing

Notes
Study Reminders
Support
Text Version

IP Routing: Introduction

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

    +

IP Routing: Introduction
Hello, so today we will continue our discussion on Computer Networks and InternetProtocols. Today we will be starting or starting our couple of lectures on IP Routing. So,already you have seen that how a application layer in our OSI or TCP/IP model works.You have already looked into several transport layer protocols and also the basics of IPlayer protocols.So, IP as such is IP layer or it is also known as the network layer is primarily responsiblefor forwarding packet from one network to another right. So, it is a if we look at theinternet which is a network of networks. So, the IP layer is primarily responsible forconnecting the two, two or two or more different network and so and so things.Now, one major aspects of this particular forwarding thing that, how the packet will beforwarded across the global internet, right. So, internet as such we have seen a havingtruly speaking that a millions of systems, thousands of routers and so and so forth right.So, how a packet from one to another it will be getting forward, like if you from yoursystem if you are typing www dot iitkgp ac dot in, then the IITKGP page gets displayedon your screen. So, how your request comes up to this IITKGP web server and thenIITKGP web server replies back to your systems right. So, if you are requesting from afar network so how it will go on hopping to through this router.So, if we imagine a overall internet or not imagine if we look at the overall inter internet.So, if there are several networks and there are a router switch connects these networksright. So, routers are responsible for for forwarding packets from one network to anothernetwork and type of things. So, if there are multiple hops are required the router shouldbe responsible for doing that right.So, today or from coming couple of lectures, we’ll be discussing or different forwardingmechanisms. How the packets are getting forwarded from one network to anothernetwork to another networks till then the destination host is reached right. So, if we lookat we will be primarily looking at following things IP addresses and address allocationalready you have gone through that we will quickly brush up on the things.(Refer Slide Time: 03:16)And we will start looking at packet forwarding or routing or there are will sayforwarding table or routing table will be a little bit interchangeably using. The tableswhich are looked at the in the router and there is another concept whenever we come intoplay that is the longest prefix match sometime LPM forwarding right. So, longest prefixmatch and we’ll be primarily referring this in the in whole of these lectures or series oflectures will be primarily referring some of the books and reference note and differencereference materials and of as mentioned there and as we have mentioned in our earlierslides also right.(Refer Slide Time: 04:05)So, IP address is a already all of us or you know that it is typically when we as of nowwe are talking about IPv4 all our dealing of this routing will be primarily based on IPv4.So, it is a 32 bit address with every 8 bit dot, 8 bit dot, 8 bit dot, 8 bit right. And ituniquely identifies a particular machine, logically provide a logical address to aparticular systems which is connected in the internet.In other sense we can say that a two systems on the same on this network cannot havetwo same IP address then it will not be able to identify those uniquely right, but there areway out still we are having those type of things that will come slowly. But neverthelesswe think that this is the logical address which goes to the things. Later on in thisparticular course we look at another type of addressing what we say physical or MACaddress, which comes with your network interface card right.So, that is the address by which by the system is identified so, but this is logically able toidentify the systems. So, these IP address is typically provided by the system systemadmin or in some cases are provided through some other mechanism like DHCP and typeof things right.So, uniquely it identifies in interface on a host on a router there is a interface right. So,where the thing where the network is connected represented by dotted quad notationright, this is known fact. And in everything in the thing everything in the system or the isrepresented by binary. So, if it is 14, 35, 158, 15 it is represented by like this right.(Refer Slide Time: 06:08)Now, if we look at internetworking so used to connect networks together not primarilynetwork. So, there are several networks which are connected together. So, we need sayway to address a network or group of host right. Like I say that I require IIT Kharagpuras a network, in inside the IIT Kharagpur I may have different sub network like say,center of educational technology, may have a network computer science and engineeringcan be a network, administration of IIT Kharagpur can be network and like that right.And so there are several networks and in other way we need a way to address thisnetwork also right; that means, if I am going from one network to another I should beable to know that address of the network.As we have discussed at the previous lectures initial lectures like so, this network layer isthe is responsible for routing; that means, for forwarding packet from one network toanother right or we say that in other words these routers are having that layer 3 capabilityor it can see packet up to layer 3 or network layer in TCP/IP model right. So, we havephysical layer, MAC layer and then ordered link layer and then the layer 3 and router canlook at the layer 3 capability.So, it can look into the network to network communication right. So, here also we cansay this is a typical one LAN having some host, this is another LAN having another hostand there can be bunch of routers and we can say this is a something in the internetworking or sometimes we say there is a wide area network. But nevertheless what werequire that different routers which allows me to connect there. There can be 3, 1 nnumber of routers which allows to the connect to the network right and there can bedifferent other networks which are connected to the network.So, the every router has a some interfaces right. Sometimes we represent by the serialport of this router 1, 2, 3, 4, 1 slash like this type of representation we will see some ofthose. But nevertheless that router has interfaces, every interfaces connects connectallows it to connect to another router or another network in the things right.(Refer Slide Time: 08:46)So, the one major challenges in any system is the scalability right, like one way oflooking at this router is that the router knows router somewhere or other knows that if Iget a packet from say host a to host b to be forwarded a to b or c say a to b or c to d to beforwarded. So, the router knows that if from here it is generated then where it should beforwarded which router to be forwarded, then somewhere is to be forwarded and so andso forth. That means, there should be somewhere a what we say a some sort of a lookuptable router looks at a table and see that this is the packet so forward these to the thingsright.The problem becomes that any system added or other since deleted from any of thenetwork needs to be again the now routing table needs to be updated across the allnetwork all, all routers across the world. Otherwise it will not be able to forward packetsright. So, there should be some mechanisms that we will see slowly that how to forwardthese packets from one to other.Now, if we holistically try to look at a router is primarily a it gets something from oneinterface looks at the destination where it should go consult its some table or someinformation. And say now you go to that to this particular through this channel right, orin other sense if I try to make an analogy like I want to go from here to say Nasik andthen try to go a major corner I ask that traffic fellow. Now, I want to go to these Nasikthis, then which way you go, he has some information that in order to go that it has tofollow this path. Then go and meet the at the next traffic person and who will redirectetcetera. So, it has some informations which allows it to route it.So, what we what in other sense what we say these are the router maintains a table whichis called Routing or sometimes Forwarding Table which allows to forward these things tothe destination right. And this how this table will be constructed how this table will bemaintained there is another challenge, but nevertheless having this table will be prettylarge considering even considering the number of networks and routers and in the ourinternetworking.And as we understand this is very dynamic because we do not have any control or thatthere cannot be a overall centralized control that how man how many networks etceterathere. And not only that there can be more systems coming in going out more networkbeing generated. So, it becomes a major challenge in the in routing the packets right. So,every router needs to needs lot of information and to know how to direct packets towardsthe host.(Refer Slide Time: 11:54)So, divide the network into host portion is the first thing what we have seen right. So, if Iif I have so have some hierarchal sort of things or I divide that it is a host portion and asorry network portion and by a host portion right. And that already you already youknow that there is a the net mask which allows that if I mask it and then so net mask is amask which followed by a it is also a 32 bit number or 32 bit address where it follows bya series of 1 and then a series of 0. So, there cannot be in between 0 1 type of thingsright. So, it is series of one followed by things it mask it and whatever it mask it out it isthe network address right.So, like here what we say 24 bit address slash 24 representation. So, the first three octetthey represent that network or the 24 bit network and rest is the host of the thing right.And if you try to look at something analogy with our postal mail system also we havedifferent category of the things right. We have say country, state, district, city, thenmaybe a area, location and then the house address and type of things right.So, if I want to mask that whatever is for West Bengal say West Bengal, India I can maskit an segregate I can say Kharagpur, West Bengal, India segregate then IIT campusKharagpur and type of things and so and so forth. So, it depends on that how, so it isthere is some rough so I what we can say I can approach the problem in a hierarchicalway right.(Refer Slide Time: 13:51)So, I can make a hierarchy that given address so this is the network address and type ofthings right. And this is typically a mask of 25 bit and if I mask it out and we get that IPaddress that already you have seen right.(Refer Slide Time: 14:06)So, in other sense we have improved some sort of scalability like I can say that this isidentify that particular with respect to a network address. And now with the LAN 2 if thiswas the way it was the table was maintained in this router. That this way incoming with24 bit whoever is matching you will be coming here or going out.(Refer Slide Time: 14:31)So, in the LAN 2 if I add a new host so you does not require adding a new forwardingentry into the table. So, it now does not address host by host, but address a network. So,this network what we see is 5, 6, 7, 0 slash 24. So, it is a net network address is with 24bit mask and if I add something like this I do not require that all these routing thingsindividual routers across the world need to be changed, still it is in the same network.In other sense this way of representation allows me to identify a particular networkthrough a identifier right. So, I mask it and this network has this network address andforward that. And then rest is the host address will be inside the thing right. Now, so thisis this way we can look at some way of addressing the scalability issues.(Refer Slide Time: 15:40)And then if you look at the IP address allocation again you have gone through that youknow those things, but just to again to brush up (Refer Time: 15:47). So, one is that wehave some fixed address allocation or we say classful addressing right like class Aaddress which starts with a 0 and star class B address 10 rest anything after that, class Caddress 110. There are two other one is for multicast group another is a reserved forfuture use right. These two other addressing schemes are there these are classfuladdressing mechanisms or in this case we have a very large block of slash 8. Thenetwork number of network is less whereas, the number of host are much larger whereas,in class B it is slash 16.So, it is somewhere it is something large number of networks are with first 16 bitrepresentation and rest are with the number of hosts. And 24 is where number of host inthese organizations are much less that 8 bit is there and there are two multicast things.So, as we know that this type of addressing or which addressing you will choose basedon that what sort of requirement you are having at the at your organization level correct.(Refer Slide Time: 17:10)And then we have also seen that classless inter domain routing where instead of thisclassful we represent by an IP mask right of any variable length again followed by 1s andthen 0s. Like here we say that one 12 dot 4 dot 0 dot 0 with a mask of slash 15 and canbe like this. So, that first 15 bit represent the address and the rest represent the host likehere what we see right. So, may not be the figure fitting properly, but first 15 bit and therest is on the host side.(Refer Slide Time: 17:50)And in other sense if we can see that if I get a this sort of things then I can go on dividingthem into different subnets right or sub networking. In other way we can have a bettermanageability of the things in a hierarchical fashion right. So, prefixes are key to theinternet scalability challenge, address allocated in contiguous chunks prefixes, routing,protocols and packet forwarding based on these prefixes. So, the while we route we routebetween these addresses. So, I can have different hierarchy of this sort of mechanismsright and this is the and I can manage IP in a the whole IP things in a better way.Not only that our I can manage the routing information or the routing table or theforwarding table in the router in a much efficient way right. Otherwise I need to have allthe things into the things like think of again not may not be very strong analogy with thepostal, but think of that I have to keep every post office need to keep individual addressof rest of the world or even rest of India right. So, if I want to send a message to x y z atsomewhere Nasik then I need to know that where to send. Instead I divided that I if I amsending something to IIT Kharagpur, so, it is a state of West Bengal, then district aparticular district, then particular city, then particular area of that city and then the thing.So, I divide into different stuff. So, similarly here also we have that type of we can dividethem into this sort of things. These are already you have you have studied in your IPaddress allocation etcetera, but we can utilize this phenomena for our routing.
IP Routing: Introduction - Part 2
So, we can have aggregation of the things like if there are these different networks. ThenI can have a aggregated network so I have 2 201 dot 00, 22, 24, 24, 23, type of things.Then I can have a aggregated network of 201 dot 10 dot 00 slash 21 right. So, routers inthe rest of the internet needs to know to reach only 2 naught 1 dot 10 dot 00 slash 21 restare handled at the lower level at the at the inside the inside that particular domain.So, the provider can now direct the IP packets to the appropriate customer ok. So, if theprovider has these are the customers right routers only need to know this higher level IPonly right. This can have different so this if this is a some sort of a IP ISP provider. So,its customer’s things are handled like this right.(Refer Slide Time: 21:07)So, but there are challenges in aggregations if there is scenario of dual homing or multihoming right like say IIT Kharagpur takes a internet connection from provider 1, anotherconnection from provider 2, another connection from provider 3. Then that particularnetwork has different multi homing things. Then it then I cannot identify this overallaggregation by a simplified thing so I need to work on some other things. So, there arechallenges, but nevertheless there is a there is a way to aggregate this sort of IPaddresses. And then my load on this routing information or routing table can be reduced.(Refer Slide Time: 21:55)So, as we are discussing the scalability through hierarchy is one of the way we handle.So, the hierarchical addressing critical for scalable systems don’t require everyone toknow everyone else for that matter because it is only the hierarchical and the in routerneeds to know or the intermediate router rest of the things reduces amount of updatingwhen something changes right. So, if something changes it reduces the amount ofupdating in the things right. Like as again try to put on the analogy if the number ofquarters in IIT Kharagpur increases the address need not to be to be published to wholerest of the world right.It is only the IIT KGP post office needs to know and update it and all the packets comesto its and it gets displayed or type of things. And if there is a and there are non uniformhierarchy useful for heterogeneous network of different sizes. So, either it can beuniform non uniform initially class based addressing was far too coarse because theaddressing what we have a classful type of addressing. So, CIDR helps it in that, but itbrings its own challenges in handling those that we will see.(Refer Slide Time: 23:13)So, we can have a block of addresses the separation of control prefix assigned to aparticular institution, address assigned addresses assigned by the institution to a host likeIIT Kharagpur it may have this is the network address and this is your host portion. Howyou address the host portion; is basically determined by the institute networkadministration right or the institute network policy there how the things will be there. Forthe rest of the world the network IP IIT Kharagpur network is like this right. So, it helpsand who assigned prefixes in a at the top level.There is a consortium or association call or internet corporation for assigned names andnumber ICANN allocates large address blocks to regional internet registries. So, registrywhich maintains the IP blocks regional internet registry like ARIN. We have theAmerican registry for internet numbers, allocates address blocks to their regions,allocated internet service providers. And there are ISP’s allocated address blocks to theircustomers who may be in turn allocate their to the custom customers and so and so forth.(Refer Slide Time: 24:40)So, there are several address registries and there are several address registries whichmaintains like who is in registry dot UNIX in the Indian context. There are domain widepages we will show you some of the things where if you give the address who is theowner etcetera it displays the things.(Refer Slide Time: 25:02)Now, definitely whether it is 32 bit addresses is enough or not that is a serious questionwith huge number of devices or network connected devices in place. This is a majorchallenge and we have IPv6 and so and so forth, already you know a overview of thethings. So, there is a there are several long term solution of IPv6 and short term we canhave private addressing scheme right this IP addresses private addresses we are not routenon routable addresses like 10 dot star dot star dot star this type of addresses are nonroutable. So, within the thing so I can have some mechanisms called network addresstranslator which translate to a public IP and goes and type of things. There are there areway to dynamically allocate addresses that you know that DHCP type of things. So,those are solutions which are available on the IPv4.(Refer Slide Time: 26:59)So, there are several other challenges in the IP related that how much address space forgeographic region. Address space portability whether you carry over the address spacekeeping the address registries up to dates there are several challenges there are what wesay so called quote unquote hard problems which are people are looking a work it.(Refer Slide Time: 26:25)Now, if we with this context if we try to look at that packet forwarding. So, what we tryto say that each router or layer 3 enabled devices which connect networks has someinformations or forwarding or routing table which maps destination address. So, routerwhat it is getting a address for the destination, like if I say www dot iiitkgp dot ac dot infrom this particular machine or IIT www nptel dot in, nptel dot ac dot in from thismachine it goes to the nearest router and it looks the router gets a destination as nptel dotac dot in.And it tries to find out that where this IP is there either the information should be victimor it should know that what should be my next hop right. Nevertheless it takes up it looksas a lookup table or what we say forwarding table or routing table and sees that what isthe next hop. So, the router in other sense has to maintain this table, like anything it getsin one interface check the table and send that appropriate interface right. If it is not inthat table so there is a concept of default route if it is not finding on the table by default itwill deduct to that particular interface right.So, upon receiving inspects the destination IP address in the header, index into the table,determine the outgoing interface forward the packet to the interface right. And they are insome situation it can change the some update the header that will come later right. Thenext router in the path repeats the thing so it goes on hopping, hopping, hopping,hopping like that right. So, it checks and go to the hop.(Refer Slide Time: 28:13)Like here it get say get say if the router forwards a as per IP match destination incomingpackets forward the table entry determine the outgoing interface. So, it goes onforwarding the table one after another right.(Refer Slide Time: 28:28)Here slash 24 is the IP yeah is the mask so; that means, it case that first 24 base is thenetwork. So, if gets if it gets a packet like this 1 dot 3 dot 24 it forwards out here this orit gives that 5 dot 6 dot 7 dot 0 slash 24 that if the this is the network address is forwardhere right.(Refer Slide Time: 28:58)Now, I can have separate entry for class full type of address, each router had an entry perclass full prefixes, a mixture of A, B, C addresses; depends on the first couple of bits onthe destination as we have seen in the class full addresses. So, identify the maskautomatically from the address like if it is bit is 0 the mask slash 8, 10 mask is slash 16and 110 the mask is slash 24 right. Look at the forwarding table of the match and then itgoes to on the onto the things right.(Refer Slide Time: 29:36)Now, CIDR complicates this right because now it has any type of mask right. So, CIDRallows efficient use of the limited address space that is absolutely fine the address spaceis not wasted or I should say efficiently used, but makes the packet forwarding muchcomplicated right. Forwarding the forwarding table can have many matches like 201 dot10 dot 00 slash 21, 2010 dot 6 dot 0 dot 23 can have more than one matches. So, where itwill forward so that is a challenge. So, the policy it is followed is the your longest prefixmatch. So, where the longest prefix is matched there it is forwarded right.So, like here in this case it needs to be forwarded 201 dot 6 dot 0 because that is thelongest prefix which match whereas, others can have a much less prefix that is this is thelongest prefix which matches right. So, that that way it takes care of the thing right.(Refer Slide Time: 30:47)So, forwarding table in IP router so map each IP prefix to the next hop or links,destination based forwarding, packets has a destination address right. So, when I am I amsending a packet the packet has a destination address. So, when I am saying www dotiitknptel dot ac dot in so a www dot ac dot in has a after DNS resolution IP which is thedestination IP for my packet. The router identifies the longest matching prefix and somealgorithms should have to be look up on the things right.So, routing and forwarding table so I have that destination addresses and it goes on to thelookup tables. Now, it is what it does it does say maximum prefix match. So, though thisup to 1201 dot 10 and these are both are matching, but the maximum prefix match saysthat the other destination this needs to be forwarded out to the 10 dot 201 dot 10 dot 6dot 0 right and which is connected to serial 0 or some particular interface of the routeroutgoing interface of the router.(Refer Slide Time: 32:05)So, now that is the longest prefix match algorithm is maybe as or a simple orcomplicated there is a major challenge because that it is have major time. So, the routermay have a huge number of entries like the scan and forwarding table one entry at a timemay take a huge time into the thing. So, that that it requires some better algorithm tohandle this like there can be huge entries like 200000, 200000, 300000 entries into theoverall entries.And looking at in a linear time will take a huge time whereas, the packets are beingpumped into the router maybe every nanosecond right. So, it is huge number of thingsneed to be processed. So, we need to have a better algorithm to find out this how thislongest prefix match can be done so that is a major challenge. So, these days it ishardware it is handled to the hardware.(Refer Slide Time: 33:00)So, one very traditional way of or looking at it is this Patricia Tree; where it is in thiscase it is a binary, where you have 0 and 1 and type of thing. So, one bit for each level oftree some nodes correspond to be varied prefixes which I have next hop interfaced on thein a table. And packet forwarded by the forwarding packets, forwarded by there is a type offorwarded by the end devices or the host like. So, at what we are having at our end is theEthernet link. This machine has some RJ 45 connection to the cable to the next things.So, PC with Ethernet links, laptops with wireless links, does not need to run a routingprotocols. So, right it forward to that particular local or the next hop whatever thegateway is defined into the things right.So, finally, what we look at that IP addresses and different allocation quickly already youhave known and seen that packet forwarding based on the IP prefixes right. So, lookingat that routing routers how it forwards and what we look at this long longest prefix matchwhen there are more than one matching coming up that where the longest prefix match isthere. So, with this we conclude our today’s discussion. We will continue these routing IProuting mechanisms in our subsequent lectures.Thank you.