Scribd
Upload
8 views50 pages

Unit - Iii

The document discusses routing concepts, including the differences between forwarding and routing tables, and the mechanisms of distance vector and link-state routing protocols. It explains how routing tables are built and updated, the challenges of link failures, and the use of algorithms like RIP and OSPF for efficient routing. Additionally, it covers the process of reliable flooding for disseminating link-state information and the application of Dijkstra's algorithm for calculating the shortest paths in a network.

Uploaded by

220801032
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
8 views50 pages

Unit - Iii

The document discusses routing concepts, including the differences between forwarding and routing tables, and the mechanisms of distance vector and link-state routing protocols. It explains how routing tables are built and updated, the challenges of link failures, and the use of algorithms like RIP and OSPF for efficient routing. Additionally, it covers the process of reliable flooding for disseminating link-state information and the application of Dijkstra's algorithm for calculating the shortest paths in a network.

Uploaded by

220801032
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
UNIT I ROUTING @ Routing (RIP, OSPF, metrics) — Switch basics — Global Internet (Areas, BGP, IPv6), Multicast ~ addresses — multicast routing (DVMRP, PIM) In a network there are multiple routes available from a source to destination & one of them is to be chosen is called routing. The network layer decides the route. The forwarding table is used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function. This means that a row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC. information, such as the Ethernet address of the next hop. The routing table, on the other hand, is the table that is built up by the routing algorithms as a precursor to building the forwarding table. It generally contains mappings from network numbers to next hops. It may also contain information about how this information was learned, so that the router will be able to decide when it should discard some information Forwarding versus Routing Forwarding: > to select an output port based on destination address and routing table Routing: > process by which routing table is built Forwarding table VS Routing table Forwarding table > Used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function > A row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet Address of the next hop Routing table > Built by the routing algorithm as a precursor to build the forwarding table > Generally contains mapping from network numbers to next hop Prefix/Length 13/8 Prefix/Length 18/8 fa) Next Hop [Link] {b) Interface | MAC Address ifo 8:0:2b:e4:b:1:2 Example rows from (a) routing (Defines IP addr) (b) forwarding tables (Defines MAC addr) Autonomous system A group of networks and routers under authority of a single administrator Autonomous system Autonomous system Interior Network as a Graph « The basic problem of routing is to find the lowest-cost path between any two nodes « Where the cost of a path equals the sum of the costs of all the edges that make up the path « For a simple network, we can calculate all shortest paths and load them into some nonvolatile storage on each node. Such a static approach has several shortcomings It does not deal with node or link failures It does not consider the addition of new nodes or links It implies that edge costs cannot change What is the solution? Need a distributed and dynamic protocol Two main classes of protocols 1. Di e Vector routing (RIP) 2. Link State routing (OSPF) Routing algorithms 1. Intra domain protocols - RIP, OSPF 2, Inter domain protocols - BGP Intra domain protocols * Also called as Interior Gateway Protocol (IGP) ¢ Use din midsized networks (less than 100 nodes) tance Vector routi * Each node constructs a one dimensional array (a vector) containing the “distances” (costs) to all other nodes and distributes that vector to its immediate neighbors * Starting assumption is that each node knows the cost of the link to each of its directly connected neighbors. > Ifa node learns a shortest path to the destination, it updates its own distance information for that destination. > Each node knows the cost’ of the links to its directly connected neighbors. Links that are down are assigned as infinite cost. * The distance vector routing algorithm is sometimes called as Bellman-Ford algorithm « “In distance vector routing Every T seconds each router sends its table to its neighbor each each router then updates its table based on the new information” + Problems include fast response to good new and slow response to bad news. Also too many messages to update The following figure shows an example of distance vector routing. 8 o— Sa Initially each node only knows the information about the distance to all other nodes as the table below. Information Stored at Node am one > Distance to Reach Hode aTe|<];e°l[elFi[s er = | eof ee rfo fats fw la |x ifr fe fate la] x wfw]r]ofwf« fs 1 [wo fw» | wo fo fw | r}awfx2fxefofofs wo | ~of{~{rfo]s fo Initial distances stored at each node (global view) Initially, each node sets a cost of 1 to its directly connected neighbors and to all the other nodes. For eg A believe that it can reach B in one hop and D is unreachable. Initial routing table at node A is as follows Destination oummao Cost 1 1 0 NextHop B c E E The next step in distance-vector routing is that every node sends a 5 message to its directly connected neighbors containing its personal list of distances. For example node F tells node A that it can reach node G at a cost of 1; A also knows it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. After receiving the distance vector of its neighbors the routing table at node A is as follows, Destination | Cost | NextHop 8 rd B c 1 c D 2 c e 1 E FE 1 F a 2 F Final routing table at node A After a few exchanges of information between neighbors, all nodes have consistent routing table with correct distance information. The process of getting consistent routing information to all the nodes is called nver gence. The following figure shows the final distances stored at each node. Information Distance to Reach Node Stored atNode [A | 8 | ©] 9 | & [FIs x eTela | aber... 2 r>fofafafadada © 1 PPP ao aep a pe ° 212] o » fata E 1 aba a fewef ee pa F 1 2}2]{2fa]fo fa 6 af |e ow feel ph Final distances stored at each node (global view) The advantage of each distributed algorithm is that each node can achieve a consistent view of network in the absence of a centralized authority. ™ There are two different conditions under which a node decides to send a routing table to neighbors 1. Periodic update - each node automatically sends an update message every seconds or minutes even though there is no change 2° Triggered update whenever a node’s routing table changes, it sends its updated Failure example Consider, in this F detects its link to G is failed. When a node detects a link failure (G) 1. F detects that link to G has failed 2. F sets distance to G to infinity and sends update to A . A sets distance to G to infinity since it uses F to reach G . A receives periodic update from C with 2-hop path to G . A sets distance to G to 3 and sends update to F . F decides it can reach G in 4 hops via A ouR Count-to-infinity problem In this example, consider the link A-E fails. * Slightly different circumstances can prevent the network from stabilizing v Suppose the link from A to E goes down v In the next round of updates, A advertises a distance of infinity to E, but B and C advertise a distance of 2 to E Y Depending on the exact timing of events, the following might happen > Node B, upon hearing that E can be reached in 2 hops from C, concludes that it can reach E in 3 hops and advertises this to A > Node A concludes that it can reach E in 4 hops and advertises this to C > Node C concludes that it can reach E in 5 hops; and so on. > This cycle stops only when the distances reach some number that is large enough to be considered infinite Partial solutions to this problems. 1) Use some relatively small number as an approximation of infinity ¢ For example, the maximum number of hops to get across a certain network is never going to be more than 16 2) One technique to improve the time to stabilize routing is called split horizon ( means Never sent same information back to the interface it came from) « When a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor For example, if B has the route (E, 2, A) in its table, then it knows it must have learned this route from A, and so whenever B sends a routing update to A, it does not include the route (E, 2) in that update « In a stronger version of split horizon, called split horizon with poison reverse Y B actually sends that back route to A, but it puts negative information in the route to ensure that A will not eventually use B to get to E Y For example, B sends the route (B, «) to A ‘Routing Information Protocol (RIP) « Widely used routing protocol in IP networks ¢ Itis a routing protocol built on distance vector algorithm « Routers running RIP actually advertise distances to networks. They send periodic updates every 30 seconds and triggered updates when the routing table changes. ¢ RIP uses link costs equal to 1 and uses 16 to represent infinity. So a network running RIP must have a maximum hops of 16. The following figure shows an example network running on RIP. 4 In this example each network, Router C advertises to router A that it can reach, 5 Nw 2and 3 at cost 0 Nw 5 and 6 at cost 1 Nw 4 at cost 2 RIP Packet Format RIP version 2 supports CIDR. RIP messages are encapsulated in a UDP datagram RIP uses the services of UDP on well-known port 520 0 8 16 31 Command| Version | Must be zero Command > request = or | _ response Family of net 4 Route Tags version +2 ‘Address prefix of net 4 must be zero - unused Address - IP address Mask of net 4 Family _- network address designed to carry information to different Protocols Distance _- metric value that determines how many hops to reach its Distance to net 1 Route Tags destination Mask of net 2 (1 to 15 are valid routes, 16 is unreachable) L —_— mask - subnet masking | Distance to net 2 next hop ~ indicates the IP address of the next hop Route tag - Distinguishes between internal & external routes (internal routes are learned by diff protocols like RIP, OSPF etc) (external routes are learn using only one protocol. Eg: BGP) ink State Routi: Link-state routing is the second major class of intradomain routing protocol. The starting assumptions for link-state routing are rather similar to those for distance vector routing. Each node is assumed to be capable of finding out the state of the link to its neighbors (up or down) and the cost of each link. Again, we want to provide each node with enough information to enable it to find the least- cost path to any destination. The basic idea behind link-state protocols is very simple: Every node knows how to reach its directly connected neighbors, and if we make sure that the totality of this knowledge is disseminated to every node, then every node will have enough knowledge of the network to build a complete map of the network. Thus, link-state routing protocols rely on two mechanisms: 1. reliable dissemination of link-state information, 2. calculation of routes from the sum of all the accumulated link- state knowledge. Strategy: Send to all nodes (not just neighbors) information about directly connected links (not entire routing table). e Link State Packet (LSP) contains the following informations id of the node that created the LSP cost of link to each directly connected neighbor sequence number (SEQNO) time-to-live (TTL) for this packet KAKK Reliable Flooding > Reliable flooding is the process of making sure that all the nodes participating in the routing protocol get a copy of the link-state information from all the other nodes. o As the term —flooding suggests, the basic idea is for a node to send its link-state information out on all of its directly connected links, with each node that receives this information forwarding it out on all of its links. > Initially each node knows only the state of the link to each of its neighbor. > The information of each node is put into update packet called as Link State Packet (LSP) and its flooded to all other packets. Ie This process continues until the information has reached all the nodes in the network. In short the process is can be summarized as, Y store most recent LSP from each node ¥ forward LSP to all nodes but one that sent it Y generate new LSP periodically; increment SEQNO v start SEQNO at 0 when reboot v decrement TTL of each stored LSP; discard when TTL=0 In flooding, each node forwards the LSP to all neighbors except the one from which the LSP was received. In the figure shows an LSP being flooded in a small network @D—A) © @O=@ | oy () ®) @—@ j ©—-®= Flooding of link-state packets. (a) LSP arrives at node X; (b) X floods LSP to A and C; () A and C flood LSP to B (but not X); (a) flooding is complete © Each node becomes shaded as it stores the new LSP. In Figure (a) the LSP arrives at node X, which sends it to neighbors A and in Figure (b) A and C do not send it back to X, but send it on to B. Since B receives two identical copies of the LSP, it will accept whichever arrived first and ignore the second as a duplicate. It then passes the LSP on to D, who has no neighbors to flood it to, and the process is complete. Just as in RIP, each node generates LSPs under two circumstances. Either the expiry of a periodic timer or a change in topology can cause a node to generate a new LSP. LSP contains sequence numbers that make it possible to distinguish new LSP from old one. Route Calculation Once a node has a copy of LSP from every other node, it can compute a complete map of network topology. From the complete network map, a node can then compute the shortest paths to all other nodes and build its routing table. Using dijktra shortest path algorithm, a node can calculate its shortest path. In practice, each switch computes its routing table directly from the LSPs it has collected using a realization of Dijkstra’s algorithm called the forward search algorithm. Shortest Path Routing ¢ Dijkstra’s Algorithm - Assume non-negative link weights v _N: set of nodes in the graph v \(i, j): the non-negative cost associated with the edge between nodes i. j eN and Iii. j) = « if no edge connects i andj v Let s €N be the starting node which executes the algorithm to find shortest paths to all other nodes in N ¥ Two variables used by the algorithm > M: set of nodes incorporated so far by the algorithm > C(n) : the cost of the path from s to each node n > The algorithm M= {3} For each n in N ~{s} Ca) = Ks, n) while (N #M) M=M w {w} such that C(w) is the minimum for all w in (N-M) for each n in (N-M) C(n) = MIN (C(n), CGw) + Iew, n)) « In practice, each switch computes its routing table directly from the LSP'’s it has collected using a realization of Dijkstra’s algorithm called the forward search algorithm * Specifically each switch maintains two lists, known as 1. Tentative 2. Confirmed « Each of these lists contains a set of entries of the form ‘Destination, Cost, NextHop) The algorithm 1. Initialize the Confirmed list with an entry for myself; this entry has a cost of 0 2. For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP 3. For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum 0’ the cost from myself to Next and from Next to Neighbor a) If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, Nexthop) to the Tentative list, where Nexthop is the direction I go to reach Next b) If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for the Neighbor, then replace the current entry with (Neighbor, Cost, Nexthop) where Nexthop is the direction I go to reach Next 4. If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to Step 2. Consider an example network for link-state routing The following table list the steps for building routing table for node D. Step Confirmed Tentative ‘Comments 1 | (09-) Since Dis the only new member of the confirmed Uist, look at ts LSP. 2 | @0-) (8,11,8) (2,0) | D's LSP says we can reach 8 through B at cost 11, ‘whichis better than anything else on either lis, so putit on Tentative list; same for C 3 | DeAC20 (811.8) Put lowest-cost member of Tentative (C) onto Confirmed lst. Next, examine LSP of newly con- firmed member (0). 4 | (09-)(62,0) (85,0(A12.0) | Cost to reach B through C Is, so replace (B,11,8). C's LSP tells us that we can reach Aat cost 12. s | Wo71C2.0185.0 A120) Move lowest-cost member of Tentative (8) to Confirmed, then look at its LSP. 6 | DOAC20 185.0 (A10,0) ‘Since we can reach A at cost 5 through 8, replace the Tentative entry. 7 | DO-)1C2,0) 85.0) (A100) Move lowest-cost member of Tentative, (A) to Confirmed, and we are all done. The difference between distance vector and link state routing algorithm is — in distance vector, each node talks only to its directly connected neighbors about the distance to all nodes. In link state, each node talks to all other nodes only about the state of its directly connected links. (Open Shortest Path First Protocol (OSPF) 1s One of the most widely used link-state routing protocols is OSPF. The first word,—Open, refers to the fact that it is an open, nonproprietary standard, created under the auspices of the IETF. The —SPF part comes from an alternative name for link state routing OSPF adds quite a number of features to the basic link-state algorithm described above, including the following: « Authentication of routing messages + Additional hierarchy « Load balancing Authentication of routing messages Protection against misconfigured routers by providing 8 byte password for authentication Additional hierarchy > Introduces additional hierarchy by allowing arouting domain to be portioned into areas. » Reduces the amount of information that must be transmitted to and stored in each node. > Router doesn’t need to know how to reach each network in its domain; it may know how to get to right area. Load balancing OSPF allows distributing traffic among multiple routes of same cost. OSPF Header Format oO 8 16 uM Message length Checksum Authentication type a « Version - set to2 ¢ Type—may take the values 1 through 5 * SourceAddr - identifies the sender of the message « Authentication type - 0 if authentication is used - Lif password is used - 2 if cryptographic authentication checksum is used ¢ Area id — 32 bit identifier of the area in which node is located e Authentication - password or cryptographic checksum Checksum —- the entire packet, except the authentication data, is protected by a 16-bit checksum using the same algorithm as the IP header. ‘Type - OSPF Message Types Type 1 -> “hello” msg (notfication msg to nofity that it is alive) Type 2 -> request Type 3 -> response Type 4— send Type 5 -> acknowledge the receipt of link state msg The basic building blocks of link state messages is known as link state advertisement (LSA). One message may contain one or many LSAs. The packet format for typel link-state advertisement is as follows:- Options Link-state ID _____ Advertising router LS sequence number LS checksum Length Number of links | Link 1D — CT Link data | Num_T0S | Optional TOS information — More links Link type OSPF Link State Advertisement e LSAge — Equivalent to time to live(TTL), LSA expires when the age reaches the maximum value ( difference is TTL counts down, LSAge counts Up) * Type = 1 LSAs advertise the cost of a link between routers. « [ Type= 2 are used to advertise the networks to which the advertising routers are connected * Other Types are used to support additional hierarchy] ¢ Link state ID & Advertising router -identical in Type 1 LSA, it should be unique in routing domain - 32 bit identifier for a router that created this LSA « LS sequence number — to detect old or duplicate LSAs e LS Checksum - similar to the other checksum , - used to verify data - covers all the fields except LSAge - no need to compute checksum everytime LSAge is incremented e Length — length in bytes of complete LSA * TOS - Type of Service 1s ¢ Link Type - Type 1—point to point - Type 2 - Transient (in between nodes ) ype 3. - Stub - Type 4- Virtual ‘Type is based on Link ID and Link data ¢ Metric - cost of link ‘trices Link costs Some ways to calculate link costs, 1. To assign a cost_1 to all links least cost route will be the one with few hops Limitations « does not distinguish between links on a latency basis * does not distinguish between routes on capacity basis « oncurrent load, making it impossible to route around overloaded links. 2. Metric measured no of packets that are queued waiting to be transmitted on each link ie more packets were waiting, then large cost weight. Limitations ¢ did not work well * it moves packets toward the shortest queue rather than towards the destination ¢ used originally in ARPANET routing 3. Second version of ARPANET routing algorithm called new routing mechanism. ¢ took both link bandwidth & latency into consideration. * used delay rather queue length Working * each incoming packet was timestamped with its arrival t‘me at the router (Arrival time) * its departure time from the router (Departure time) was recorded. « when link-level ACK was received from other side, Node computes the delay for that packet Delay = (DepartTime — ArrivalTime)+ TransmissionTime + Latency where TransmissionTime and Latency were statically defined. DepartTime — ArrivalTime represents the amount of time the packet was delayed (queued) in the node due to load Ifthe ACK did not arrive, but instead the packet timed out, then DepartTime was reset to the time the packet was retransmitted. imitations * more frequent retransmission « less reliable a link — the more we want to avoid it 4, Weight assigned to each link was derived from the average delay experienced by the paths recently sent over that link Limitations Under heavy load, congested link would start to advertise a very high cost- this causes all traffic to move off that link, leaving it idle. so again it will advertise a low cost, thereby attacking back all traffic and so on. therefore instability. 5. 3" approach called “Revised ARPANET routing metric” Major changes * to compress the dynamic range of metric considerably * to account for link type © to smooth the variation of metric with time Switches and routers use similar implementation techniques, EFIGURE “A general-purpose processor used as apace switch Figure shows a processor with three network interfaces used as a switch. The figure shows a path that a packet might take from the time it arrives on interface 1 until it is output on interface 2. We have assumed here that the processor has a mechanism to move data directly from an interface to its main memory without having to be directly copied by the CPU, a technique called direct memory access (DMA). Once the packet is in memory, the CPU examines its header to determine which interface the packet should be sent out on. It then uses DMA to move the packet out to the appropriate interface. Note that Figure does not show the packet going to the CPU because the CPU inspects only the header of the packet; It does not have to read every byte of data in the packet. The main problem with using a general-purpose processor as a switch is that its performance is limited by the fact that all packets must pass through a single point of contention. In the example shown, each packet crosses the I/O bus twice and is written to and read from main memory once. The upper bound on aggregate throughput of such a device (the total sustainable data rate summed over all inputs) is, thus, either half the main memory bandwidth or half the I/O bus bandwidth, whichever is less. (Usually, it’s the I/O bus bandwidth.) For example, a machine with a 133-MHz, 64-bit-wide I/O bus can transmit data at a peak rate of a little over 8 Gbps. Since forwarding a packet involves crossing the bus twice, the actual limit is 4 Gbps—enough to build a switch with a fair number of 100-Mbps Ethernet ports, for example, but hardly enough for a high-end router in the core of the Internet. Moreover, this upper bound also assumes that moving data is the only problem—a fair approximation for long packets but a bad one when packets are short. In the latter case, the cost of processing each packet— parsing its header and deciding which output link to transmit it on—is likely to dominate. Suppose, for example, that a processor can perform all the necessary processing to switch 2 million packets each second. This is sometimes called the packet per second (pps) rate. (This number is representative of what is achievable on an inexpensive PC.) If the average packet is short, say, 64 bytes, this would imply Throughput = pps x (BitsPerPacket) 2x 106 x 64x8 1024 x 106 that is, a throughput of about 1 Gbps—substantially below the range that users are demanding from their networks today. Bear in mind that this 1 Gbps would be shared by all users connected to the switch, just as the bandwidth of a single (unswitched) Ethernet segment is shared among all users connected to the shared medium. Thus, for example, a 20-port. switch with this aggregate tl roughput would only be able to cope with an average data rate of about 50 Mbps on_ each _ port. To address this problem, hardware designers have come up with a large array of switch designs that reduce the amount of contention and provide high aggregate throughput. Note that some contention is unavoidable: If every input has data to send to a single output, then they cannot all send it at once. However, if data destined for different outputs is arriving at different inputs, then a well-designed switch will be able to move data from inputs to outputs in parallel, thus increasing the aggregate throughput. n [The Global Interne: > Internetworking is a heterogeneous of networks with tens of thousands of networks connected to it. > The Global Internet NSFNET backbone MidNet regional BARRNET regional Berkeley The tree structure of the Internet in 1990 > As the internet grows it poses, - large no of network numbers are used, routers have to maintain a large routing table Global internet is not just a random interconnection of Ethernets, but instead it takes on a shape that reflects the fact that it interconnects many different organizations. NSFNET backbone BARRNET regional Figure : The tree structure of the Internet in 1990 Salient features of this topology is, > It has end user sites that connect to service provider etwork > Eg: user site — Stanford university Service provider network - e.g., BARRNET was a provider network that served sites in that area Many providers served a limited geographic region and known as Regional Networks. a These Regional networks were in turn connected by NationWIdeBackbone 19 =was funded by NSF ( National Science Foundatin). Therefore its called as NSFNET backbone. This has some significant consequence in routing: Eg: AS decide the best routing protocol used in their network. As the internet grows it poses - large no of network numbers are used - routers have to maintain a large routing table - large amount of IP address space are wasted To tackle the 2 issues of scalability we use, - Supernetting or classless routing - Subnetting [Routing Area As a first example of using hierarchy to scale up the routing system, we'll examine how link-state routing protocols (such as OSPF and IS-IS) can be used to partition a routing domain into subdomains called_areas. By adding this extra level of hierarchy, we enable single domains to grow larger without overburdening the routing protocols or resorting to the more complex interdomain routing protocols Area is a set of routers that are administratively configured to exchange link-state information with each other. There is one special area—the backbone area, also known as area 0. An example of a routing domain divided into areas is shown in Figure Y Routers R1, R2, and R3 are members of the backbone area, They are also members of at least one nonbackbone area. R1 is actually a member of both area 1 and area 2. A youter that is a member of both the backbone area and a nonbackbone area is an area_border router (ABR). The routers that are at the edge of an AS, which are referred to as AS border routers KAN Routing within a single area v Allthe routers in the area send link-state advertisements to each other and thus develop a complete, consistent map of the area Y The link-state advertisements of routers that are not area border routers do not leave the area in which they originated. v This has the effect of making the flooding and route calculation processes considerably more scalable. ¥Y For example, router R4 in area 3 will never see a link-state advertisement from router R8 in area 1. As a consequence, it will know nothing about the detailed topology of areas other than its own. How does a router in one area determine the right next hop for a packet destined to a network in another area? The answer to this becomes clear if we imagine the path of a packet that has to travel from one nonbackbone area to another as being split into three parts. 1. First, it travels from its source network to the backbone area 2. then it crosses the backbone, 3. then it travels from the backbone to the destination network To make this work, the area border routers summarize routing information that they have learned from one area and make it available in their advertisements to other areas. For example, R1 receives link-state advertisements from all the routers in area 1 and can thus determine the cost of reaching any network in area 1. When R1 sends link-state advertisements into area 0, it advertises the costs of reaching the networks in area 1 much as if all those networks were directly connected to R1 This enables all the area 0 routers to learn the cost to reach all networks in area 1. The area border routers (ABR) then summarize this information and advertise it into the nonbackbone areas. Thus, all routers learn how to reach all networks in the domain. In the case of area 2, there are two ABRs and that -9) routers in area 2 will thus have to make a choice as to which one they use to reach the backbone. Sealability & optimality When dividing a domair into areas, the network administrator makes a tradeoff between scalability and optimality of routing. The use of areas forces all packets traveling from one area to another to go via the back- bone area, even if a shorter path might have been available. For exam- ple, even if R4 and R5 were directly connected, packets would not flow bettveen them because they are in different nonbackbone areas. It turns out that the need for scalability is often more important than the need to use the absolute shortest path. Finally, we note that there is a trick by which network administrators can more flexibly decide which routers go in area 0. This trick uses the idea of a virtual link between [Link] a virtual link is obtained by configuring a router that is not directly connected to area 0 to exchange backbone routing information with a router that is. For example, a virtual link could be configured from R8 to Rl, thus making R8 part of the backbone. R8 would now participate in link-state advertisement flooding with the other routers in area 0. The cost of the virtual link from R8 to R1 is determined by the exchange of routing information that takes place in area 1. This technique can help to improve the optimality of routing. [Interdomain Routing (BGP) > Inter domain routing is used for complex netwi > Internet is organized as autonomous systems (AS) each of which is under the control of a single administrative entity > Autonomous System (AS) - corresponds to an administrative domain - examples: University, company, backbone network > A corporation's internal network might be a single AS, as may the network of a single Internet service provider Route Propagation » Idea: Provide an additional way to hierarchically aggregate routing information is a large internet. - Improves scalability - Divide the routing problem in two parts: - Routing within a single autonomous system - Routing between autonomous systems Another name for autonomous systems in the Internet is routing domains * Two-level route propagation hierarchy ¥ Inter-domain routing protocol (Internet-wide standard) Y Intra-domain routing protocol (each AS selects its own) Challenges in Interdomain Routing Perhaps the most important challenge of interdomain routing today is the need for each AS to determine its own routing policies. Akey design goal of interdomain routing is that policies and much more complex ones, should be supported by the interdomain routing system There are two Inter-domain Routing Protocols 1. Exterior Gateway Protocol (EGP) 2. Border Gateway Protocol (BGP) « Exterior Gateway Protocol (EGP) v Forced a tree-like topology onto the Internet v Did not allow for the topology to become general bo Tree like structure: there is a single backbone and autonomous systems are connected only as parents and children and not as peers * Border Gateway Protocol (BGP) v BGP version 4 is often regarded as one of the more complex parts of the internet. v BGP makes virtually no assumptions about how autonomous systems are interconnected—they form an arbitrary graph. IBGP- Border Gateway Protocol] > BGP (Border Gateway Protocol) is a type of Inter Domain protocol > BGP is used for routing interconnected set of Autonomous Systems(ASs) > It Assumes that the Internet is an arbitrarily interconnected set of ASs. > Today’s Internet consists of an interconnection of multiple backbone networks. > Sites are connected to each other in arbitrary ways > This model is clearly general enough to accommodate non- tree- structured internetworks, like the simplified picture of a multi-provider Internet shown in Figure. vy Assumes that the Internet is an arbitrarily interconnected set of ASs. ¥ Today’s Internet consists of an interconnection of multiple backbone networks (they are usually called service provider networks, and they are operated by private companies rather than the government) v — Sites are connected to each other in arbitrary ways BGP is used for routing interconnected set of Autonomous Systems(ASs° Figure shows today’s multibackbone Internet. today’s Internet consists of a richly interconnected set of networks, mostly operated by private companies (ISPs) rather than governments. Many Internet Service Providers (ISPs) exist mainly to provide service to “consumers” (i.e., individuals with com- puters in their homes), while others offer something more like the old backbone service, interconnecting other providers and sometimes larger corporations. Often, many providers arrange to interconnect with each other at a single peering point. « Assumes the Internet is an arbitrarily interconnected set of AS's. Large corporation’ “Consumer” ISP Peering point Backbone service provider point “Consumer” ISP fe C Large corporation >) Consumer” I6P. Small corporation Figure : Today’s multibackbone Internet a | It defines two types of traffic 1) local traffic - as traffic that originates at or terminates on nodes within an AS 2) transit traffic - as traffic that passes through an AS. Three types of AS are, Stub AS: an AS that has only a single connection to one other AS; such an AS will only carry local traffic (small corporation in the figure of the previous page). ¥ Multihomed AS: an AS that has connections to more than one other AS, but refuses to carry transit traffic (large corporation at the top in the figure of the previous page). ¥ Transit AS: an AS that has connections to more than one other AS, and is designed to carry both transit and local traffic (backbone providers in the figure of the previous page). The goal of Inter-domain routing is > To find any path to the intended destination that is loop free > Paths must be compliant with policies of various ASs along the paths. Challenges in interdomain routing * We are concerned with reachability than optimality +Finding path anywhere close to optimal is considered to be a great achievement ¢ Scalability: An Internet backbone router must be able to forward any packet destined anywhere in the Internet v Having a routing table that will provide a match for any valid IP address « Autonomous nature of the domains Y It is impossible to calculate meaningful path costs for a path that crosses multiple ASs ¥ A cost of 1000 across one provider might imply a great path but it might mean an unacceptable bad one from another provid « Issues of trust v Provider A might be unwilling to believe certain advertisements from provider B Basics of BGP Each AS has one or more border routers through which packets enter and leave the AS. A Border Router is simple an IP router that is charged with the task of forwarding packet bet-veen autonomous systems. Each AS has: 25 > One BGP'speaker that advertises: Y local networks Y other reachable networks {transit AS only) Y gives path information > In addition to the BGP speakers, the AS has one or more border “gateways” which need not be the same as the speakers > The border gateways are the routers through which packets enter and leave the AS > BGP does not belong to either of the two main classes of routing protocols (distance vectors and link-state protocols). > BGP advertises complete paths as an enumerated lists of ASs to reach a particular network. It is sometimes called a path-vector protocol for this reason. consider the very simple example network in Figure. Assume that the providers are transit networks, while the customer networks are stubs. An Example of a network running BGP Customer P) 128.96 — . = a (AS 4) 192.4.153 Regional provider A Pe (AS 2) —— ee ape Customer >) 192.4.32 ass) _) 1924.3 Backbone network ees) (AS 1) Customer R. (AS 6) 1192.12.69 ‘Regional provider B as3) Customer S 192.454 (as7) _) 192.4.23 e ABGP speaker for the AS of provider A (AS 2) advertises reachability to P and Q Y Network 128.96, 192.4.153, 192.4.32, and 192.4.3, can be reached directly from AS 2. « Speaker for backbone network then advertises Y Networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached along the path . « Speaker can also cancel previously advertised paths « An important job of BGP is to prevent the establishment of looping paths. 128.96 Backbone network (AS 1) | FIGURE 4.6 Example of oop among axtonomaus ystems. In figure only in the addition of an extra link between AS 2 and AS 3, but the effect now is that the graph of autonomous systems has a loop in it. Suppose AS 1 learns that it can reach network 128.96 through AS 2, so it advertises this fact to AS 3, who in turn advertises it back to AS 2. In the absence of any loop prevention mechanism, AS 2 could now decide that AS 3 was the preferred route for packets destined for 128.96. If AS 2 starts sending packets addressed to 128.96 to AS 3, AS 3 would send them to AS 1; AS 1 would send them back to AS 2; and they would loop forever. This is prevented by carrying the complete AS path in the routing messages. In this case, the advertisement for a path to 128.96 received by AS 2 from AS 3 would contain an AS path of . AS 2 sees itself in this path, and thus concludes that this is not a useful path for it to use. In order for this loop prevention technique to work, the AS numbers carried in BGP clearly need to be unique. For example, AS 2 can only recognize itself in the AS path in the above example if no other AS iden- tifies itself in the same way. AS numbers have until recently been 16-bit numbers, and they are assigned by a central authority to assure uniqueness. PGP-4 Update Packet Format: 0 5 Given that links fail and policies change, BGP speakers need to be able to cancel previously advertised paths. This is done with a form of negative advertisement known as a withdrawn route. Both positive and negative reachability information are carried in a BGP update message, the format of which is shown in Figure. HE FIGURE 4.8 Common AS relationships Three common relationships and the policies are, 1. Provider-Customer Providers are in business of connecting their customers to rest of internet. A customer might be s smaller ISP. so the common policy is to advertise all the routes I know to my customer, and advertise routes I learn from my customer to everyone. 2. Customer-Provider Advertise my own prefixes and routes learned from my provider to my customers to my provider, advertises routes learned from my providers to my customers , but don’t advertise routes learned from one provider to another provider. 3. Peer Third option is a symmetrical peering between autonomous systems. policy here is to advertise routes learned from my customers to my peer, advertise routes learned from my peer to my customers, but don’t advertise routes from my peer to any provider or vice versa. 27 Integrating Interdomain and Intradomain Routing Consider, for example, the border router of a provider AS that connects te a customer AS. That router could learn that the network prefix 192.4.54/24 is located inside the customer AS, either through BGP or because the information is con- figured into the border router. It could inject a route to that prefix into the routing protocol running inside the provider AS. This would be an adver- tisement of the sort, “I have a link to 192.4.54/24 of cost X.” This would cause other routers in the provider AS to learn that this border router is the place to send packets destined for that prefix. The routers in a backbone network use a variant of BGP called interior BGP (iBGP) to effectively redistribute the information that is learned by the BGP speakers at the edges of the AS to all the other routers in the AS. (The other variant of BGP, discussed above, runs between autonomous systems and is called exterior BGP, or eBGP). iBGP enables any router in the AS to learn the best border router to use when sending a packet to any address. At the same time, each router in the AS keeps track of how to get to each border router using a conventional intradomain protocol with no injected information. By combining these two sets of information, each router in the AS is able to determine the appropriate next hop for all prefixes. TTavtrom other autonemous systems } / Tota ctor manors ‘yatema / Ve «OR FO \ Tatrom other autonomous systems FIGURE 4.9 Example of interdomain and intradomain routing. All youters run iBGP and an intradomain routing protocol. Border routers A, D, and E also run eBGP to other autonomous systems. Consider the simple example network, rep- resenting a single AS, in Figure 4.9. The three border routers, A, D, and E, speak eBGP to other autonomous systems and learn how to reach various _| prefixes. These three border routers communicate with other 29 and with the interior routers B and C by building a mesh of iBGP sessions among all the routers in the AS. Let’s now focus in on how router B builds up its complete view of how to forward packets to any prefix. Look at the table at the top left of Figure 4.10 which shows the information that router B learns from its iBGP sessions. It learns that some prefixes are best reached via router A, some via D, and some via E. At the same time, all the routers in the AS are also running some intradomain routing protocol such as Routing Information Protocol (RIP) or Open Shortest Path First (OSPF). (A generic term for intradomain protocols is an interior gateway protocol, or IGP.) From this completely separate protocol, B learns how to reach other nodes inside the domain, as shown in the top right table. For example, to reach router E, B needs to send packets toward router C. Finally, in the bottom table, B puts the whole picture together, combining the information about external prefixes learned from iBGP with the infor- mation about interior routes to the border routers learned from the IGP. Thus, ifa prefix like 18.0/16 is reachable via border router E, and the best interior path to E is via C, then it follows that any packet destined for 18.0/16 should be forwarded toward C. In this way, any router in the AS can build up a complete routing table for any prefix that is reachable via some border router of the AS. All routers run iBGP and an intradomain routing protocol. Border routers (A, D, E) also run eBGP to other ASs BGP routing) table, IGP routing table, and combined table at router B is, IGP Path 18.016 12.5.5/24 128.3416 4128.69.16 Le c | Prone | 18.0n6 | 12.8.8/24 t | 128.3416 | 120.69.46 ‘Combined table for router 8 FIGURE 4.10 BGP routing table, IGP routing table, and combined table at router B. [Pv6 (IP Version 6) The motivation for new version of IP is - To deal with scaling problem - Toachieve 100 % address utilization efficiency Historical perspective « IEFT (Internet Engg Task Force), which is responsible for specification of standards and protocols looked into the problem in 1991 * Since the IP address is carried in the header of every IP packet, increasing the size of the address dictates a change in the packet header. « The effort to define a new version of IP was known as IP Next Generation, or IPng. « an official IP version number was assigned, so IPng is now known as IPv6 In addition to deal with scalable routing and addressing, IPv6 should also - support for real-time services - supports multicast = security support - auto configuration (i.e., the ability of hosts to automatically configure themselves with such information as their own IP address and domain name) - End-to-end fragmentation - Enhanced routing functionality, including support for mobile hosts. Addresses and Routing IPV6 provides a 128-bit address space. IPv6 can address 3.4*10% nodes, IPv6 address space is predicted to provide over 1500 addresses per square foot of the earth’s surface vvVVv Address Space Allocation « IPvé6 also follows CIDR like IPv4, so IPv6 addresses are classless ° The address prefix assignments for IPV6 is as follows, At the time of writing, IPv6 unicast addresses are being allocated from the block that begins 001, with the remaining address space—about 87%—being reserved for future use. Prefix Use 3} 00...0 (128 bits) | Unspecified 00...1 (128 bits) | Loopback oan 4111 1110 10 11111101 Everything else Multicast addresses Site local unicast Link local unicast Global unicast Fig : Address Prefix Assignments for IPv6 Multicast address - Similar to class D address in IPV4 - The multicast address space is for multicast, - Start with a byte of all 1s. local unicast - Enable a host to construct an address that will work on the network to which it is connected, without being concerned about the global uniqueness of the address. - This may be useful for autoconfiguration Site local unicast - Intended to allow valid address to be constructed on site. - (eg., a private corporate network) that is not connected to the larger Internet; global unicast address - Some important special types of addresses. - Two special address types have uses in the IPv4-to-IPv6 transition. 1. IPv4 compatible IPv6 address 2. IPv4 mapped IPv6 address IPv4 compatible IPv6 address - One type, the [Pv4-compatible IPu6 address, is used for devices that are compatible with both IPv4 and IPv6; - Begins with 96 bits zeros then followed by 32 bits IPv4 address IPv4 mapped IPv6 address - Anode that is only capable of understanding IPv4 can be assigned an IPv4-mapped IPv6 address by prefixing the 32-bit IPv4 address with 2 bytes of all 1s and then zero-extending the result to 128 bits. - Begins with 80 bits zeros, followed by 16 bits of ones and 32 bits IPv4 address | Address Notation The standard representation is : IXIKIX where each —x is a hexadecimal representation of a 16-bit piece of the address. Example IPV6 Address 47CD:1234:4422:ACO2:0022:1234:A456:0124 If we have a address with a large number of contiguous 0s can be written more compactly by omitting all the 0 fields. Examplel A7CD:0000:0000:0000:0000:0000:A456:0124 could be written as 47CD::A456:0124 Example 2 3FFE:085B:1F1F:0000:0000:0000:00A9:1234 could be written as 3FFE:85B:1F 1F::A9:1234 8 groups of 16-bit hexadecimal numbers separated by “:” & Leading zeros can be removed. :: = all zeros in one or more group of 16-bit hexadecimal numbers Clearly, this formof shorthand can only be used for one set of contiguous Os in an address to avoid ambiguity. The two types of IPv6 addresses that contain an embedded IPv4 address have their own special notation that makes extraction of the [Pv4 address easier. For example, the IPv4-mapped IPv6 address of a host whose IPv4 address was [Link] could be written as nFFFF:[Link] That is, the last 32 bits are written in IPv4 notation, rather than as a pair of hexadecimal numbers separated by a [Link] that the double colon at the front indicates the leading Os. Global unicast addresses o IPV6 provide unicast addressing that supports a rapid rate of increasing hosts to internet and also allows routing in a scalable way. o IPV6 has address allocation plan which determines how unicast addresses are assigned to service providers, AS, N/Ws,host and routers. o The address allocation plan in IPV6 unicast addresses is similar to CIDR in IPV4. IPV6 address allocation plan is to provide aggregation of routing information to reduce the burden on intradomain routers. o This is done by assigning an address prefix to a direct providers and then for that direct provider to assign longer prefixes that begin with that prefix to its subscribers. An IPv6 provider-based unicast address is as follows: BS 3 m n © Pp 125-men-o-p SubnetiD |. InterfacelD RegistryID | ProviderlD | SubscriberlD The RegistryID might be an identifier assigned to a European address registry, with different IDs assigned to other continents or countries. Packet Format The IPV6 packet header format is as follows 9 4 1216 24 31 TrafficClass FlowLabel T ia en PayloadLen HopLimit v Version - set to 6 for IPv6. v TrafficClass and FlowLabel- deals with quality of service issues. v PayloadLen -Length of the packet excluding the [Pv6 header,measured in bytes. v NextHeader — if special headers follow IP header, it indicate option. ¥ If there are no special headers, it indicates the highlevel protocols running over IP. Eg: TCP and UDP ¥ HopLimit - field is simply the TTL of [Pv4. Each Option has its own type of extension header. The IPv6 fragmentation extension header is as follows, ° 8 16 29 31 NextHeader | Reserved Offset RES M Ident « Assuming it is the only extension header present, then the NextHeader field of the [Pv6 header would contain the value 44, which is the value assigned to indicate the fragmentation header. « The NextHeader field of the fragmentation header itself contains a value describing the header that follows it. Again, assuming no other extension headers are present, then the next header might be the TCP header, which results in NextHeader containingthe value 6, just as the Protocol field would in IPv4. « Ifthe fragmentation header were followed by, say, an authentication header, then the fragmentation head NextHeaderfield would contain the value 51. [Internet Multicast, @ IP multicast is a method of sending Internet Protocol (IP) datagrams to a group of interested receivers in a single transmission, ™ It is often employed for streaming media applications on the Internet and private networks. The method is the IP-specific version of the general concept of multicast networking. Overview ™ One-to-many v Radio station broadcast v Transmitting news, stock-price v Software updates to multiple hosts @ Many-to-many v Multimedia teleconferencing ¥ Online multi-player games Y Distributed simulations Without support for multicast ¥ A source needs to send a separate packet with the identical data to each member of the group > This redundancy consumes more bandwidth > Redundant traffic is not evenly distributed, concentrated near the sending host VY Source needs to keep track of the IP address of each member in the group > Group may be dynamic + To support many-to-many and one-to-many IP provides an IP-level multicast ¢ Basic IP multicast model is many-to-many based on multicast groups v Each group has its own IP multicast address ¥ Hosts that are members of a group receive copies of any packets sent to that group’s multicast address Y A host can be in multiple groups v A hos” can join and leave groups « Using IP multicast to send the identical packet to each member of - 39 the group y A host sends a single copy of the packet addressed to the group’s multicast address v The sending host does not need to know the individual unicast IP address of each member Y Sending host does not send multiple copies of the packet e IP's original many-to-many multicast has been supplemented with support for a form of one-to-many multicast One-to-many multicast Source specific multicast (SSM) Y Single sender, multiple receivers v A receiving host specifies both a multicast group and a specific sending host E.g. radio stations, TV stations Many-to-many model Any source multicast (ASM) v Some or all nodes can become sender E.g. teleconferencing, online video games « A host signals its desire to join or leave a multicast group by communicating with its local router using a special protocol v In IPv4, the protocol is Internet Group Management Protocol (IGMP) v In IPv6, the protocol is Multicast Listener Discovery (MLD) © The router has the responsibility for making multicast behave correctly with regard to the host Multicast address > A multicast address is a logical identifier for a group of hosts in a computer network, that are available to process datagrams or frames intende | to be multicast for a designatednetwork service. > IPv6 has a portion of address space 11111111 reserved for multicast group addresses. >» When a host on the Ethernet joins an IP multicast group, it configures its Ethernet interface to receive packets with corresponding Ethernet multicast address. > This causes the receiving host to receive not only the multicast traffic but also traffic sent to any of the other multicast groups. Thus, IP header of any receiving host examine IP header of any multicast packet to determine whether the packet belongs to desire group.

You might also like