Chapter 3: Internetworking - Philadelphia University

Chapter 3: Internetworking - Philadelphia University

Computer Networks: A Systems Approach, 5e Larry L. Peterson and Bruce S. Davie Chapter 3 Internetworking Copyright 2010, Elsevier Inc. All rights Reserved 1 Chapter 3 Problems In Chapter 2 we saw how to connect one node to another, or to an existing network. How do we build networks of global scale? How do we interconnect different types of

networks to build a large global network? 2 Chapter 3 Chapter Outline Switching and Bridging Basic Internetworking (IP) Routing 3

Chapter 3 Chapter Goal Understanding the functions of switches, bridges and routers Discussing Internet Protocol (IP) for interconnecting networks Understanding the concept of routing 4 Chapter 3 Switching and Forwarding Store-and-Forward Switches Bridges and Extended LANs

Cell Switching Segmentation and Reassembly 5 Chapter 3 Switching and Forwarding Switch A mechanism that allows us to interconnect links to form a large network A multi-input, multi-output device which transfers packets from an input to one or more outputs 6

Chapter 3 Switching and Forwarding Adds the star topology to the point-to-point link, bus (Ethernet), and ring (802.5 and FDDI) topologies 7 Chapter 3 Switching and Forwarding Properties of this star topology Even though a switch has a fixed number of inputs and outputs, which limits the number of hosts that can be connected to a

single switch, large networks can be built by interconnecting a number of switches We can connect switches to each other and to hosts using pointto-point links, which typically means that we can build networks of large geographic scope Adding a new host to the network by connecting it to a switch does not necessarily mean that the hosts already connected will get worse performance from the network 8 Chapter 3 Switching and Forwarding The last claim cannot be made for the shared media network (discussed in Chapter 2) It is impossible for two hosts on the same Ethernet to transmit continuously at 10Mbps because they share the same transmission medium

Every host on a switched network has its own link to the switch So it may be entirely possible for many hosts to transmit at the full link speed (bandwidth) provided that the switch is designed with enough aggregate capacity 9 Chapter 3 Switching and Forwarding A switch is connected to a set of links and for each of these links, runs the appropriate data link protocol to communicate with that node A switchs primary job is to receive incoming packets on one of its links and to transmit them

on some other link This function is referred as switching and forwarding According to OSI architecture this is the main function of the network layer 10 Chapter 3 Switching and Forwarding How does the switch decide which output port to place each packet on? It looks at the header of the packet for an

identifier that it uses to make the decision Two common approaches Datagram or Connectionless approach Virtual circuit or Connection-oriented approach A third approach source routing is less common 11 Chapter 3 Switching and Forwarding Assumptions

Each host has a globally unique address There is some way to identify the input and output ports of each switch We can use numbers We can use names 12 Chapter 3 Switching and Forwarding Datagrams Key Idea

Every packet contains enough information to enable any switch to decide how to get it to destination Every packet contains the complete destination address 13 Chapter 3 Switching and Forwarding An example network To decide how to forward a packet, a switch consults a forwarding table (sometimes called a routing table) 14

Chapter 3 Switching and Forwarding Destination Port ------------------------------------A 3 B 0 C 3 D 3 E 2 F 1 G 0 H 0

Forwarding Table for Switch 2 Copyright 2010, Elsevier Inc. All 15 Chapter 3 Switching and Forwarding Characteristics of Connectionless (Datagram) Network A host can send a packet anywhere at any time, since any packet that turns up at the switch can be immediately forwarded (assuming a correctly populated forwarding table) When a host sends a packet, it has no way of knowing if the network is capable of delivering it or if the destination host is

even up and running Each packet is forwarded independently of previous packets that might have been sent to the same destination. Thus two successive packets from host A to host B may follow completely different paths A switch or link failure might not have any serious effect on communication if it is possible to find an alternate route around the failure and update the forwarding table accordingly 16 Chapter 3 Switching and Forwarding Virtual Circuit Switching

Widely used technique for packet switching Uses the concept of virtual circuit (VC) Also called a connection-oriented model First set up a virtual connection from the source host to the destination host and then send the data 17 Chapter 3 Switching and Forwarding Host A wants to send packets to host B 18 Chapter 3

Switching and Forwarding Two-stage process Connection setup Data Transfer Connection setup Establish connection state in each of the switches between the source and destination hosts The connection state for a single connection consists of an entry in the VC table in each switch through which the connection passes 19

Chapter 3 Switching and Forwarding One entry in the VC table on a single switch contains A virtual circuit identifier (VCI) that uniquely identifies the connection at this switch and that will be carried inside the header of the packets that belong to this connection An incoming interface on which packets for this VC arrive at the switch An outgoing interface in which packets for this VC leave the switch A potentially different VCI that will be used for outgoing packets The semantics for one such entry is

If a packet arrives on the designated incoming interface and that packet contains the designated VCI value in its header, then the packet should be sent out the specified outgoing interface with the specified outgoing VCI value first having been placed in its header 20 Chapter 3 Switching and Forwarding Note: The combination of the VCI of the packets as they are received at the switch and the interface on which they are received uniquely identifies the virtual connection There may be many virtual connections established in the switch

at one time Incoming and outgoing VCI values are not generally the same VCI is not a globally significant identifier for the connection; rather it has significance only on a given link Whenever a new connection is created, we need to assign a new VCI for that connection on each link that the connection will traverse We also need to ensure that the chosen VCI on a given link is not currently in use on that link by some existing connection. 21 Chapter 3 Switching and Forwarding

Two broad classes of approach to establishing connection state Network Administrator will configure the state The virtual circuit is permanent (PVC) The network administrator can delete this Can be thought of as a long-lived or administratively configured VC A host can send messages into the network to cause the state to be established This is referred as signalling and the resulting virtual circuit is said to be switched (SVC)

A host may set up and delete such a VC dynamically without the involvement of a network administrator 22 Chapter 3 Switching and Forwarding Lets assume that a network administrator wants to manually create a new virtual connection from host A to host B First the administrator identifies a path through the network from A to B 23 Chapter 3 Switching and Forwarding Comparison with the Datagram Model

Datagram network has no connection establishment phase and each switch processes each packet independently Each arriving packet competes with all other packets for buffer space If there are no buffers, the incoming packet must be dropped In VC, we could imagine providing each circuit with a different quality of service (QoS) The network gives the user some kind of performance related guarantee Switches set aside the resources they need to meet this guarantee

For example, a percentage of each outgoing links bandwidth Delay tolerance on each switch Most popular examples of VC technologies are Frame Relay and ATM One of the applications of Frame Relay is the construction of VPN 24 Chapter 3 Internetworking What is internetwork

An arbitrary collection of networks interconnected to provide some sort of host-host to packet delivery service A simple internetwork where H represents hosts and R represents routers 25 Chapter 3 Internetworking What is IP IP stands for Internet Protocol Key tool used today to build scalable, heterogeneous internetworks It runs on all the nodes in a collection of networks and defines the infrastructure that allows these nodes and networks to function as

a single logical internetwork A simple internetwork showing the protocol layers 26 Packet Delivery Model Connectionless model for data delivery Best-effort delivery (unreliable service) Chapter 3

IP Service Model packets are lost packets are delivered out of order duplicate copies of a packet are delivered packets can be delayed for a long time Global Addressing Scheme Provides a way to identify all hosts in the network 27

Chapter 3 Packet Format Version (4): currently 4 Hlen (4): number of 32-bit words in header TOS (8): type of service (not widely used) Length (16): number of bytes in this datagram Ident (16): used by fragmentation Flags/Offset (16): used by

fragmentation TTL (8): number of hops this datagram has traveled Protocol (8): demux key (TCP=6, UDP=17) Checksum (16): of the header only DestAddr & SrcAddr (32) 28 Chapter 3 IP Fragmentation and Reassembly Each network has some MTU (Maximum Transmission Unit)

Ethernet (1500 bytes), FDDI (4500 bytes) Strategy Fragmentation occurs in a router when it receives a datagram that it wants to forward over a network which has (MTU < datagram) Reassembly is done at the receiving host All the fragments carry the same identifier in the Ident field Fragments are self-contained datagrams IP does not recover from missing fragments 29

Chapter 3 IP Fragmentation and Reassembly IP datagrams traversing the sequence of physical networks 30 Chapter 3 IP Fragmentation and Reassembly Header fields used in IP fragmentation. (a) Unfragmented packet; (b) fragmented packets. 31 Chapter 3 Global Addresses Properties

globally unique hierarchical: network + host 4 Billion IP address, half are A type, is B type, and 1/8 is C type Format Dot notation 10.3.2.4 128.96.33.81 192.12.69.77

32 Strategy Chapter 3 IP Datagram Forwarding every datagram contains destination's address if directly connected to destination network, then forward to host if not directly connected to destination network, then forward to some router

forwarding table maps network number into next hop each host has a default router each router maintains a forwarding table Example (router R2) 33 Chapter 3 Subnetting Add another level to address/routing hierarchy: subnet Subnet masks define variable partition of host part of class A and B addresses Subnets visible only within site 34

Chapter 3 Subnetting Forwarding Table at Router R1 35 Chapter 3 Subnetting Notes Would use a default router if nothing matches Not necessary for all ones in subnet mask to be contiguous Can put multiple subnets on one physical network Subnets not visible from the rest of the Internet 36

Chapter 3 Classless Addressing Classless Inter-Domain Routing A technique that addresses two scaling concerns in the Internet The growth of backbone routing table as more and more network numbers need to be stored in them Potential exhaustion of the 32-bit address space Address assignment efficiency

Arises because of the IP address structure with class A, B, and C addresses Forces us to hand out network address space in fixed-size chunks of three very different sizes A network with two hosts needs a class C address Address assignment efficiency = 2/255 = 0.78 A network with 256 hosts needs a class B address Address assignment efficiency = 256/65535 = 0.39

37 Chapter 3 Classless Addressing Exhaustion of IP address space centers on exhaustion of the class B network numbers Solution Say NO to any Autonomous System (AS) that requests a class B address unless they can show a need for something close to 64K addresses

Instead give them an appropriate number of class C addresses For any AS with at least 256 hosts, we can guarantee an address space utilization of at least 50% What is the problem with this solution? 38 Chapter 3 Classless Addressing Problem with this solution If a single AS has, say 16 class C network numbers assigned to it,

Excessive storage requirement at the routers. Every Internet backbone router needs 16 entries in its routing tables for that AS This is true, even if the path to every one of these networks is the same If we had assigned a class B address to the AS The same routing information can be stored in one entry Efficiency = 16 255 / 65, 536 = 6.2% 39 Chapter 3

Classless Addressing CIDR tries to balance the desire to minimize the number of routes that a router needs to know against the need to hand out addresses efficiently. CIDR uses aggregate routes Uses a single entry in the forwarding table to tell the router how to reach a lot of different networks Breaks the rigid boundaries between address classes 40

Consider an AS with 16 class C network numbers. Instead of handing out 16 addresses at random, hand out a block of contiguous class C addresses Suppose we assign the class C network numbers from 192.4.16 through 192.4.31 Observe that top 20 bits of all the addresses in this range are the same (11000000 00000100 0001) Chapter 3 Classless Addressing

We have created a 20-bit network number (which is in between class B network number and class C number) Requires to hand out blocks of class C addresses that share a common prefix 41 Chapter 3 Classless Addressing Requires to hand out blocks of class C addresses that share a common prefix The convention is to place a /X after the prefix where X is

the prefix length in bits For example, the 20-bit prefix for all the networks 192.4.16 through 192.4.31 is represented as 192.4.16/20 By contrast, if we wanted to represent a single class C network number, which is 24 bits long, we would write it 192.4.16/24 42 How do the routing protocols handle this classless addresses Chapter 3 Classless Addressing It must understand that the network number may be of

any length Represent network number with a single pair All routers must understand CIDR addressing 43 Chapter 3 Classless Addressing Route aggregation with CIDR 44 IP forwarding mechanism assumes that it can find the network number in a packet and then

look up that number in the forwarding table We need to change this assumption in case of CIDR CIDR means that prefixes may be of any length, from 2 to 32 bits Chapter 3 IP Forwarding Revisited 45 Chapter 3

IP Forwarding Revisited It is also possible to have prefixes in the forwarding tables that overlap Some addresses may match more than one prefix For example, we might find both 171.69 (a 16 bit prefix) and 171.69.10 (a 24 bit prefix) in the forwarding table of a single router A packet destined to 171.69.10.5 clearly matches both prefixes. The rule is based on the principle of longest match

171.69.10 in this case A packet destined to 171.69.20.5 would match 171.69 and not 171.69.10 46 Map IP addresses into physical addresses destination host next hop router Techniques

Chapter 3 Address Translation Protocol (ARP) encode physical address in host part of IP address table-based ARP (Address Resolution Protocol) table of IP to physical address bindings broadcast request if IP address not in table target machine responds with its physical address table entries are discarded if not refreshed 47

Chapter 3 ARP Packet Format HardwareType: type of physical network (e.g., Ethernet) ProtocolType: type of higher layer protocol (e.g., IP) HLEN & PLEN: length of physical and protocol addresses Operation: request or response Source/Target Physical/Protocol addresses 48 Chapter 3

Host Configurations Notes Ethernet addresses are configured into network by manufacturer and they are unique IP addresses must be unique on a given internetwork but also must reflect the structure of the internetwork Most host Operating Systems provide a way to manually configure the IP information for the host Drawbacks of manual configuration

A lot of work to configure all the hosts in a large network Configuration process is error-prune Automated Configuration Process is required 49 Chapter 3 Dynamic Host Configuration Protocol (DHCP) DHCP server is responsible for providing configuration information to hosts There is at least one DHCP server for an administrative domain DHCP server maintains a pool of available addresses

50 Chapter 3 DHCP Newly booted or attached host sends DHCPDISCOVER message to a special IP address (255.255.255.255) DHCP relay agent unicasts the message to DHCP server and waits for the response 51

Chapter 3 Internet Control Message Protocol (ICMP) Defines a collection of error messages that are sent back to the source host whenever a router or host is unable to process an IP datagram successfully Destination host unreachable due to link /node failure Reassembly process failed TTL had reached 0 (so datagrams don't cycle forever) IP header checksum failed ICMP-Redirect

From router to a source host With a better route information 52 Chapter 3 Internet Control Message Protocol (ICMP) Defines a collection of error messages that are sent back to the source host whenever a router or host is unable to process an IP datagram successfully

Destination host unreachable due to link /node failure Reassembly process failed TTL had reached 0 (so datagrams don't cycle forever) IP header checksum failed ICMP-Redirect From router to a source host With a better route information 53 Chapter 3 Routing Forwarding versus Routing Forwarding: to select an output port based on destination address and routing table

Routing: process by which routing table is built 54 Chapter 3 Routing 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 hops 55 Chapter 3 Routing Example rows from (a) routing and (b) forwarding tables 56 Chapter 3 Routing 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

57 Chapter 3 Routing 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 Distance Vector Link State 58 Chapter 3 Distance Vector

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 59 Chapter 3 Distance Vector Initial distances stored at each node (global view) 60 Chapter 3

Distance Vector Initial routing table at node A 61 Chapter 3 Distance Vector Final routing table at node A 62 Chapter 3 Distance Vector Final distances stored at each node (global view) 63

The distance vector routing algorithm is sometimes called as Bellman-Ford algorithm 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 Chapter 3 Distance Vector 64

Chapter 3 Distance Vector When a node detects a link failure F detects that link to G has failed 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 65

Chapter 3 Distance Vector Slightly different circumstances can prevent the network from stabilizing Suppose the link from A to E goes down 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 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 Count-to-infinity problem 66 Chapter 3 Count-to-infinity Problem 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 One technique to improve the time to stabilize routing is called split horizon

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 67 Chapter 3 Count-to-infinity Problem In a stronger version of split horizon, called split horizon with poison reverse

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 For example, B sends the route (E, ) to A 68 Example Network running RIP Chapter 3 Routing Information Protocol (RIP) RIPv2 Packet Format 69 Chapter 3 Link State Routing Strategy: Send to all nodes (not just neighbors) information

about directly connected links (not entire routing table). Link State Packet (LSP) 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 Reliable Flooding store most recent LSP from each node

forward LSP to all nodes but one that sent it generate new LSP periodically; increment SEQNO start SEQNO at 0 when reboot decrement TTL of each stored LSP; discard when TTL=0 70 Chapter 3 Link State Reliable Flooding Flooding of link-state packets. (a) LSP arrives at node X; (b) X floods LSP to A and C; (c) A and C flood LSP to B (but not X); (d) flooding is complete 71 Chapter 3 Shortest Path Routing

Dijkstras Algorithm - Assume non-negative link weights N: set of nodes in the graph l((i, j): the non-negative cost associated with the edge between nodes i, j N and l(i, j) = if no edge connects i and j 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 = {s}

For each n in N {s} C(n) = l(s, n) while ( N M) M = M {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), C(w) + l(w, n)) 72 3 Subtitle Chapter # Chapter Shortest Path Routing

In practice, each switch computes its routing table directly from the LSPs it has collected using a realization of Dijkstras algorithm called the forward search algorithm Specifically each switch maintains two lists, known as Tentative and Confirmed Each of these lists contains a set of entries of the form (Destination, Cost, NextHop) 73 Chapter 3 Shortest Path Routing The algorithm

Initialize the Confirmed list with an entry for myself; this entry has a cost of 0 For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from Next to Neighbor 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 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 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. 74 Chapter 3 Shortest Path Routing 75 OSPF Header Format Chapter 3 Open Shortest Path First (OSPF) OSPF Link State Advertisement 76 Chapter 3

Summary We have looked at some of the issues involved in building scalable and heterogeneous networks by using switches and routers to interconnect links and networks. To deal with heterogeneous networks, we have discussed in details the service model of Internetworking Protocol (IP) which forms the basis of todays routers. We have discussed in details two major classes of routing algorithms Distance Vector Link State 77

Recently Viewed Presentations

  • The Philosophy of Education Chapter 5 What is

    The Philosophy of Education Chapter 5 What is

    The Philosophy of Education Chapter 5 What is Philosophy of Education All teachers have a personal philosophy that colors the way they teach Engaging in philosophy helps clarify what they do or intend to do, justify or explain why they...
  • The Difficult Airway Management in Adult Critical Care

    The Difficult Airway Management in Adult Critical Care

    Dose 0.8 - 1.2mg/kg iv SUXAMETHONIUM ROCURONIUM LARYNGOSCOPY TECHNIQUE BIMANUAL LARYNGOSCOPY CRICOID PRESSURE Avoid regurgitation of gastric contents by occluding upper end of oesophagus May worsen glottic view BURP: Improve glottic view by manipulating thyroid cartilage LARYNGOSCOPY INSERTING ET TUBE...
  • Special Thanks To: Glenn Hurricane Schwartz, Dave Tolleris

    Special Thanks To: Glenn Hurricane Schwartz, Dave Tolleris

    Henry Margusity, Elliot Abrams, Joel Myers, OSU2, famartin, Joe and Bastardi for the sharing of your ideas, your sense of humor, your innate passion for the science, your objective views (sometimes), your debates driven by either the pure desire for...
  • Interest Groups - Southeast Missouri State University

    Interest Groups - Southeast Missouri State University

    Interest Groups Background Groups have a significant impact on policy Single-issue politics Interest groups Organized membership Pursuit of policy goals from shared interest of members Economic groups Make profits, provide jobs, improve pay, or protect occupation Property is "most common...
  • Sampling Rate Conversion There will be math!

    Sampling Rate Conversion There will be math!

    As to IIR filters, apodizing filters, and the like: Unless this is for a stringently power-limited low-fi application, forget IIR filters. For quality, you will need frightening word lengths. You will have to be very careful in filter design. And....
  • Diapositive 1 - NCKU

    Diapositive 1 - NCKU

    Ultracold Quantum Gases Claude Cohen-Tannoudji NCKU, 23 March 2009 Collège de France
  • GE 1216 Speech Communication - E-class

    GE 1216 Speech Communication - E-class

    Give them ThinkWave access code sheets for each student. Listening and Reporting Exercise 1. On your note card write . answers to the following: where are you from. Favorite hobby. One short term goal youhave for the future. Something unique...
  • Evolutiona ry explanatio n of group disp lays

    Evolutiona ry explanatio n of group disp lays

    The universal nature of war dances cross-culturally in sport (Haka,) suggests that the behaviour may have an evolutionary component related to ritualised aggression. Dunning . et al (1988) argued that far from being ritualised and harmless, a lot of aggression...