cs428 Internetworking

Internetworking : Internetworking


Internetworking : Internetworking Connecting multiple point-to-point networks Two problems must be addressed heterogeneity connected point-to-point networks may use different technologies still other network types may exist in between scale consider the growth of the Internet algorithms must work for much larger networks than they are designed for


Outline : Outline Bridging interconnects LAN’s to produce an extended LAN limited in how well it deals with heterogeneity and scale Internet Protocol (IP) the Internet service model hierarchical addressing and routing Next Generation IP (IPv6) designed to fix the problems of IP


Bridge : Bridge Problem: suppose we want to connect two Ethernets together to form a bigger one repeater forwards signals from one Ethernet segment to the next recall max of 4 per Ethernet: limited scalability Bridge connected to both Ethernets accepts all transmissions on either network and forwards them onto the other two or more networks connected by one or more bridges form an extended LAN


Why Bridges? : Why Bridges? Autonomy of ownership of the separate LANs one dept. might want FDDI, another Ethernet they still want to interact Geography it may be cheaper to build separate LANs and connect them Splitting load with two connected LANs, contention is halved Distance between nodes Ethernet allows max distance of 1500m Reliability: a bridge may isolate problems Security with bridges, not all nodes necessarily see all traffic


Learning Bridges : Learning Bridges Why should the bridge forward packets sent from A to B onto network 2? If the bridge knew where the hosts resided, it could forward only those packets that needed to be forwarded creating and maintaining a table manually is unnecessary use the source address of incoming packets if a packet comes in from host D on port 2, then the bridge can deduce that host D resides on network Y build the table dynamically, flush entries periodically to deal with hosts moving from one network to the other Y


Loops : Loops Bridges 1, 2, and 3 form a loop could be there on purpose (redundancy) or by accident (no single person considers the global topology) packets can be forwarded forever


Spanning Trees : A spanning tree S of a graph G is a subset of G that contains all the vertices but no cycles if S has cycles, throw out some edges Bridges select the ports onto which they will forward packets Spanning Trees


Spanning Tree Alg. Overview : Spanning Tree Alg. Overview identify the bridge with the smallest identifier, and elect that bridge to be the root of the spanning tree the root always forwards all packets over all ports each bridge computes the shortest path to the root remembers which port is on that path all bridges connected to a LAN elect a single designated bridge for that LAN the designated bridge is the one with the shortest path to the root a bridge forwards frames on only those ports connected to networks for which the bridge is the designated bridge


Spanning Tree Example : Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J


Spanning Tree Example : Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F


Spanning Tree Example : Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F Designated for A (closer to root than B3 is) Designated for B (5 < 7) (A, B, D) (C, E) (K, F) (H, I, J)


Spanning Tree Example : Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F Designated for A (closer to root than B3 is) Designated for B (5 < 7) (A, B, D) (C, E) (K, F) (H, I, J)


Spanning Tree Algorithm : Spanning Tree Algorithm Bridges can’t see the full topology to apply the rules must exchange information and run an algorithm The algorithm Send configuration messages that contain: sender’s id id of who the sender thinks the root is distance in hops from sender to the root Each bridge remembers the “best” message it has seen on each of its ports “best” means lower root id, shorter distance, lower sender id, in that order when a bridge gets a better message, it discards old information


Spanning Tree Algorithm : Spanning Tree Algorithm When a bridge learns it is not the root, it stops generating configuration messages it just forwards configuration messages from other bridges after adding 1 to the distance field When a bridge receives a “better” configuration on some port, it stops sending on that port Stabilized system only the root is generates configuration packets other bridges are forwarding them over networks for which they are the designated bridge If a bridge fails downstream bridges won’t hear config msgs from root will timeout and declare themselves the root, triggering the algorithm


Internetworking : Internetworking internetwork network of networks logical network (as opposed to physical network, e.g. FDDI)


Internet Protocol (IP) : Internet Protocol (IP) Internet Protocol (IP) the protocol that runs on all nodes of an internetwork, allowing them to become a single logical network The IP service model addressing scheme that uniquely identifies all hosts connectionless datagrams (best effort, no delivery guarantee) “runs over anything”


IP Packet Header Format : IP Packet Header Format


Packet Header Fields : Packet Header Fields Version (current version 4) indicates how the rest of the header is formatted Hlen indicates the length in words of the header usually 5 for IPv4 TOS: type of service, not really used Length total bytes in the datagram including the header (max 64K) Ident, flags, offset: for fragmentation and reassembly


Packet Header Fields (cont.) : Packet Header Fields (cont.) TTL: time to live counts hops (decremented by each router), current default 64 Protocol identifies the higher level protocol (e.g. TCP=6, UDP=17) Checksum sums 16-byte words, takes 1’s complement of result any failed packet is discarded Source / Destination Address defines a global address space; the IP address of any host is unique across the entire network Options: rarely used


Fragmentation and Reassembly : Fragmentation and Reassembly Different networking technologies allow different sized frames Ethernet: 1500 bytes FDDI 4500 bytes ATM: 53 bytes maximum transmission units (MTU) an MTU is the size of the largest datagram that the physical network can contain in a frame IP packets can be up to 64K requires that they be broken up into smaller units on physical networks


Fragmentation and Reassembly : Fragmentation and Reassembly Fragmentation can occur in hosts or routers hosts generally break packets up to fit the local network routers fragment when a packet arrives that is too big for a network that it must be forwarded onto Transmission fragments of the same packet may take different paths Reassembly done at the destination, never at intermediate routers


Fragmentation and Reassembly : Fragmentation and Reassembly Details ident field is chosen to be unique for the original packet the flags contain a bit that indicates whether it is the last packet the offset field indicates the first byte in this packet (X, 0, 0) can become (X, 1, 0), (X, 1, 512), (X, 0, 1024) and then (X, 1, 0), (X, 1, 512), (X 1, 768), (X, 1, 1024), (X, 0, 1280)


IP Addressing : IP Addressing Hierarchical addresses parts of the address indicate a hierarchy in the system IP addresses network part, and a host part all hosts on the same network have the same network part variable sized parts, depending on the class of the address Hosts connected to multiple networks have multiple IP addresses dotted decimal notation 128.146.88.9


IP Address Classes : IP Address Classes Class A starts with 0 7 bits network, 24 bits for the host Class B starts with 10 14 bits network, 16 bits host Class C starts with 110 21 bits for network, 8 bits for host Class D starts with 1110 for multicast IP addr 0 = “this host” IP addr -1 = “broadcast” 127.x.y.z = loopback host


IP Datagram Forwarding : IP Datagram Forwarding Source host compares destination address with the local network if there is a match, deliver directly to the destination ARP, more later if no match, send to a router select a router by consulting the forwarding table forwarding table entry: if no entry, use a designated default router Hierarchical aggregation forwarding tables contain network numbers, not host numbers much smaller


Address Resolution : Address Resolution Problem we have the IP address of a host or router we know the host or router is on our local network but the local network has its own type of address, not IP addr Each host maintains a table of mappings hosts populate the table dynamically Address Resolution Protocol (ARP) the table is called an ARP cache or ARP table


ARP : ARP If a source host does not contain an ARP cache entry corresponding to some target IP address source broadcasts an ARP query includes the target host responds with adds to its ARP cache other hosts “refresh” entries, if they exist reset the timeout value do not add brand new entries: they may never need them!


DHCP : DHCP Problem what if we have a physical address, but need the IP address? booting a diskless workstation needs its own IP address! Dynamic Host Configuration Protocol (DHCP) new host broadcasts a packet announcing its physical address and asking for its IP address a DHCP server runs on each network responds with the IP address for the new machine the DHCP server must be configured first to expect the question


ICMP : ICMP Internet Control Message Protocol (ICMP) Defines error messages for the source of a packet destination unreachable reassembly failed bad info in header TTL expired (hop count reached zero) checksum failed control messages ICMP-Redirect tells the source there is a better way to a destination echo and timestamp request / reply


Next… : Next… Subnetting impose another level of hierarchy within IP addresses Intradomain routing RIP, OSPF Interdomain routing EGP, BGP


IP Addresses : IP Addresses IP addresses contain a network part and a host part different classes of addresses give different numbers of bits to each part. Class B: 14 bits network, 16 bits host Problem 1: wasted addresses small networks need at least a class C address designates a minimum of 255 addresses (8 bit host part) networks with just over 255 hosts would need a class B designates 64K addresses Problem 2: routing scalability lots of networks means lots of forwarding table entries


Subnetting : Subnetting The idea introduce another level of hierarchy into IP addresses use one network number for multiple physical networks assign each “subnet” a different prefix within the host part of the address


Subnetting (cont.) : Subnetting (cont.) The network number identifies the network may contain multiple physical subnets hosts on different physical networks may have the same network number the subnet ID identifies the subnet (physical network) each host is given an IP address and a subnet mask the bitwise AND of the IP address with the subnet mask identifies the subnet IP addr. = 128.104.42.12, mask = 255.255.255.0 then subnet = 128.104.42.0


Sending : Sending Problem recall the algorithm for deciding whether to deliver locally if network id’s match, deliver locally, otherwise deliver to router this no longer works with subnetting Solution must check to see if subnets match, not just network ids sender bitwise ANDs its own subnet mask with the destination IP address if the result matches the subnet of the sender, then deliver locally otherwise send to a router


Routing : Routing Problem routers need know how to send to all other networks and “local” hosts with subnetting, “local” means something different a destination host may have the same network part as the router, and the router may still not be able to deliver directly to the host Solution maintain maintain an entry for each subnet within a network check the subnet of the destination bitwise AND an entry’s subnet mask with the destination address if the result matches the subnet number, use this entry’s next hop


Benefits of Subnetting : Benefits of Subnetting Addresses are not used up as quickly subnets can be used to make better use of addresses, rather than requiring one network ID per physical network Routing tables shrink fewer network numbers all packets to subnets of the same network get routed (from outside the network) to a common place from that common place, they get routed within the local network add relatively few entries for subnets of the same network


Autonomous Systems : Autonomous Systems An Autonomous System (AS) is a network under the administrative control of a single entity Binghamton University is an AS IBM, Endicott is an AS An AS is also known as a routing domain intradomain routing getting packets to destinations within an AS accomplished by an interior gateway protocol interdomain routing getting packets to destinations outside of an AS accomplished by an exterior gateway protocol


Intradomain Routing : Intradomain Routing Routing Information Protocol (RIP) Bellman-Ford: distance vector routing advertises routes every 30 seconds measures link cost in terms of number of hops (1-16) Open Shortest Path First (OSPF) link state routing protocol “open” in that the algorithm is published by IETF even though an IGP need not be known outside its network


OSPF Characteristics : OSPF Characteristics Route authentication what if a host advertises a low cost to all networks? nearby routers will use this host for all packets represents a point of attack on a network OSPF supports an 8 byte password used when routing information is exchanged Domain areas OSPF allows a domain to be partitioned into areas routers need not know how to get to all subnets, just all areas each domain has a backbone area all other areas are connected to it


OSPF : OSPF Domain areas (continued) intra-area routing just send along shortest path to destination inter-area routing send to backbone, across the backbone, then out to the appropriate area Multiple routing metrics delay, throughput, reliability compute and maintain three different routes one per metric enables multiple types of service low latency, high reliability, etc.


OSPF : OSPF Load balancing allows more than one route to a destination multiple copies of routes with the same cost are maintained 2nd-best route may be chosen Packet format 0 32 16


Interdomain Routing : Interdomain Routing Exterior Gateway Protocol (EGP) assumed (imposed) a tree-like structure in the Internet required routing over a designated backbone limited scalability Border Gateway Protocol (BGP) assumes an arbitrary topology of interconnected AS’s scales better used in the current Internet goal: reachability, not optimality


Interdomain Routing : Interdomain Routing The Problem different autonomous systems have different policies and goals may be willing to route any traffic, regardless of source and destination may not be willing to route traffic to/from foreign countries may not want traffic routed through a competitor’s AS etc.


BGP : BGP Two types of traffic, with respect to some AS local traffic: originates within or terminates at the AS transit traffic: passes through the AS Three types of autonomous systems stub one connection to one other AS multiconnected more than one connection to other AS’s refuse to carry transit traffic transit (backbones) more than one connection designed (and willing) to carry transit traffic


BGP : BGP Each BGP network elects a BGP speaker The speaker advertises reachability information stub and multiconnected networks advertise the networks contained within that AS transit networks also advertise networks they can reach Speakers advertise complete paths an enumeration of all AS’s used to get to each destination allows a flexible set of policies to be implemented at each AS e.g. if an untrusted AS is in a route, don’t select this route


Problems with Internet Routing : Problems with Internet Routing Scaling problems growth of forwarding tables with more and more networks exhausting the IP address space particularly class B networks Potential solutions work against each other e.g. assign multiple class C addresses instead of a class B better address utilization, but increases forwarding table size aggregate within a class B address forwarding tables shrink, addresses used up faster Subnetting helps


Classless Interdomain Routing : Classless Interdomain Routing Classless Interdomain Routing (CIDR) also called supernetting Goal: balance the competing concerns aggregate routes behind a single forwarding table entry hand out class C addresses in blocks e.g. hand out 192.54.16 through 192.54.31 all together they all share the first 20 bits of their address build routers and protocols that allow this to be useful let network numbers be pairs essentially allows variably sized network parts: classless addresses incorporated into BGP version 4


IPv6 : IPv6 Next Generation IP (IPng) the massive growth of the Internet requires different solutions we’ll run out of addresses before 4 billion have been assigned 4 billion isn’t that large a number depending on what gets an IP address in the future Changing address size requires a new header format a new header requires a new version number if we’re changing the header, we might as well fix a lot of other stuff at the same time


IPv6 Goals : IPv6 Goals Support more (billions of) hosts Reduce routing table sizes Allow for efficient implementations Provide better security Implement type-of-service, especially real-time Enable multicasting Enable mobility of hosts Allow the protocol to change in the future Smooth transition period


IPv6 addresses : IPv6 addresses 128-bit address space allows 3.4 X 1038 different addresses 1500 per square foot of the earth’s surface should be enough Address notation colon-separated hexadecimal representation 49AB:4851:ABCD:9981:7439:AB12:0014:1111 IPv4 embedded in an IPv6 header ::00FF:128.99.42.11


IPv6 Addresses (cont.) : IPv6 Addresses (cont.) Address allocation classless, but prefix identifies the type of network address many prefixes set, but undefined e.g. 010 prefix contains provider-based unicast addresses, which encompasses the functionality of class A, B, and C addresses 100 prefix contains geography based unicast 11111111 is for multicast addresses (like IPv4 class D)