Review of Last Class 1. Ethernet media 2. CSMA/CD 3. Frame format 4. Collision domain 5. Bridging/Switching a. Transparent b. Source routing c. Switch improvements over bridging Administrative 1. Computer lab 2. Projects update 3. Homework 4. Readings/schedule update Weblinks (reading) http://www.itprc.com/tcpipfaq/default.htm http://www.3com.com/nsc/501302.html Diagrams, links: http://www.netbook.cs.purdue.edu III. Layer 3 Technology (Network) The network layer is made up of a number of packet switches, connected through various types of layer 2 technologies such as LANs or point-to-point links. Packet switch is also called: - intermediate system (IS), term used by ISO - gateway, term sometimes used by IP community - switch (layer 3 switch), newer use of the term - router, most common term in today's internetworks Packet switches are not end nodes, but they are nodes on a network. The primary functions performed at the network layer are: - Globally unique addressing - Routing (packet switching) - Packet fragmentation A. Network layer characteristics 1. Reliable versus best effort Reliable: All packets arrive correctly, in order. No packet loss nor packet duplication. Best effort: Send packets, let the transport layer deal with loss and duplicates. 2. connection oriented versus connectionless Connection oriented: Path constructed first, then packets carry path information, which they all follow. ex: ATM Connectionless: Each packet carries a source/destination address pair and is packet switched (routed) independently of all other packets. ex: IP We will be primarily talking about connectionless network layer protocols (IP) unless otherwise noted. 3. performance guarantees B. Network Addressing The major difference in connectionless based network layer protocols are the size of the address and whether the address refers to an interface or the entire node itself. 1. Address size - IPv4 = 32 bits (2^32 unique number of addresses - ~4billion) - IPX = 32 bits + 48 bits = 80 bits - IPv6 = 128 bits - AppleTalk = 24 bits 2. Address Configuration - Manual - Automatic 3. Hierarchical Addressing ex: picture of hierarchical network addressing (networks within networks 5.37.* 5.31.*, etc.) IEEE 802 addresses for not example, not hierarchical Hierarhical addressing provides route "summarization" so that routers need only know only about networks. Routers use routing tables to determine which interface can be used to reach each particular network. ex: Bad hierarchical design, DePaul's IP net 4. Owning versus renting 5. Types of Addresses a. Unicast DA and SA contain specific host/interface addresses. Only two end nodes involved in the conversation. b. Multicast DA contains a "group" or set of nodes, possibly at many locations. c. Broadcast DA pertains to "all" nodes on the network. d. Anycast The DA corresponds to a set of computers that share a common address prefix/location. Only one destination node needs to receive the message and process it. i.e. for load balancing B. Routing A process by which each packet is inspected in order to determine the next "hop" on a path to the destination. Routing algorithms and routing tables are used to compute the next hop on a path to the destination. Note: The forwarding of of packets does not typically depend on the source (sender). A concept known as source independence. Routing protocols: Internetwork services which create and maintain routing tables in every internetwork router. 1. Routing Protocol Requirements a. Efficient route table size b. Efficient routing control messages c. Robustness and reliablity i. prevent loops ii. avoid black holes iii. reconvergence 2. Routing characteristics a. centralized versus distributed i. a single node coordinates all routing information and distributes to all routers ii. in distributed, routers cooperate through a routing protocol to share information on network information b. source based versus hop-by-hop i. source places route info in each packet ii. router routes based on destination address iii. loose source routing, partial source route info c. stochastic versus deterministic i. deterministic routing has one route to destination ii. stochastic routing maintains multiple paths and can randomly pick any route it has d. single versus multiple path i. different from above, because multipath uses a primary and backup path which is only used if primary is down ii. Internet uses single path because it reduces routing table size and PSTN uses multipath to prevent blocking e. state-dependent (dynamic) versus state-independent (static) i. dynamic routing can route based on network condition or the current (measured) state of the network ii. static routing will ignore network state and route based on a single metric such as hop count or manually set f. route measurements i. hops ii. cost iii. delay iv. bandwidth v. error rate g. interior versus exterior 3. Routing Algorithms a. Distance Vector Routing Each router maintains the distance from itself to every other network. Routers learn distances by exchanging distance information. The basis is that you report your attached networks as a distance of zero. Everyone adds a distance of one to distance information they receive from their neighbors. There is a set interval of time in which routers exchange routing information in DVR protocols. This is nontrivial. Must balance sensitivity in link changes to the cost of exchanging and updating routes. ex: Signs at intersections pointing to towns and how many miles to each town i. Each router is configured with it's own ID ii. Each router has a cost associated with each of it's links iii. Each router has 0 for its links and infinity for others iv. Neighbors periodically exchange info or if things change v. Each router saves the most recently received info vi. Each router computes distances for all networks vii. Recalculation may occur if: - neighbor sends different info than before - a link to a neighbor goes down o Count to infinity problem ex: 3 routers a---b---c C goes down, what happens? Solutions: a. Hold down - Wait for a period of time before switching to another path, advertise the broken route as infinity. Based on timers. b. Report the entire path - Will guarantee no loops, but expensive. c. Split horizon - Do not advertise routes to neighbors if the route was received from that neighbor. Not foolproof. o Triggered updates Advertise distance changes as soon as you learn them. This is necessary because distance vector updates are usually sent at specific intervals. If you wait til the intervals for changes, _convergence_ time would be very high and the network unstable for a extended period of time. o Poison Reverse Used with split horizon. Report a value of infinity to your neighbors, rather than simply not mentioning the link. Explicitly telling your neighbors about your inability to reach a network. o Diffusing Update Algorithm (DUAL) Somewhat like hold down, but routers are alerted of the broken path. Timers are not used. Adds complexity to distance vector routing, may just want to use link state. b. Link State Routers distribute the cost of each link and the topology to all other routers. In this way, all routers have complete information about the network and each router computes its own, optimal path to a destination. This method ensures a loop-free environment. Procedure 1. Each router is responsible for meeting its neighbors and learning their names. 2. Each router constructs a packet known as a link state packet (LSP) which contains a list of the names and costs of its neighbors. 3. The LSP is transmitted to all other routers and each router stores the most recently generated LSP from each other router. 4. Each router, now with complete information, computes routes to each destination. ex: 4 notes in a square B A D C A creates LSP containing [A,B,1] which it forards to its neighbors. Its neighbors forward it as appopriate so that everyone has a copy of the LSP. This technique is known as "flooding". Duplicate LSPs are not forwarded. Flooding: each packet received is sent to all neighbors except the one in which the LSP was received from. Sequence numbers and aging are used to differeniate LSPs and the latest info. 1. Dijkstra algorithm for computing the shortest path. Four databases: a. The link state database contains the latest LSPs from all other routers. b. PATH (permanent) consists of ID, path cost and forwarding direction. c. TENT (tentative or temporary) consists of ID, path cost and forwarding direction. d. Forwarding database which only contains ID and forwarding direction. Procedure: a. Each router starts with itself as root of the tree by putting its ID and 0 cost and 0 forwarding direction in PATH. b. For each node placed in PATH, examine it's LSP and place those neighbors in TENT if not already exists in PATH or TENT. c. If TENT is empty, terminate, otherwise find the ID in TENT with the lowest cost and move it to PATH. D. Fragmentation A network layer packet cannot be larger than the MTU size of a data link network in which it is sent. If it is, the network layer (router or node) divides the packet into smaller, multiple pieces called fragments. Each fragment contains information necessary to identify and reconstruct the original packet. Datagram (connectionless) networks use data byte offsets to manage fragmentation. More about fragmenting when we talk about IP. E. The Internet Protocol (IP) A connectionless packet delivery service standardized in RFC 791. Provides for addressing, the basis for routing and defines packet format for other services and options including fragmentation. 1. Frame format Version (4) Header Length (4) ToS (8) Total Length (16) Identification (16) Flags (3) Reserved - always 0 (1) Don't fragment (1) More fragments (1) Fragment offset (13) TTL (8) Protocol (8) Header Checksum (16) Source Address (32) Destination Address (32) Options (variable) Padding (variable if necessary) 2. IP Addressing Each interface on a IP network is assigned a unique IP address which identifies the network and host ID. A few special types of addresses are reserved or used for special delivery needs of various applications. A. Original Class Hierarchy 1. Class A - first higher order bit is 0 - actual useable addresses: 0.1.0.0 to 126.0.0.0 2. Class B - 128.0.0.0 to 191.255.0.0 3. Class C - 192.0.1.0 to 223.255.255.0 4. Class D - 224.0.0.0 to 239.255.255.255 (multicast) 5. Class E - 240.0.0.0 247.255.255.255 (test) 6. Special addresses - Loopback 127.x.x.x - All 0's, this host - Alls 0's:host id, host on this net - All 1's, limited broadcast, local net - Net:all 1's, directed broadcast for net - Net:0, this network C. CIDR and VLSM The primary goal of CIDR and VLSM is to make more efficient usage of address space by setting network and host boundaries of an IP address anywhere within the 32 bit address space. *VERY IMPORTANT* Some examples: 140.192.91.0/25 11111111 11000000 00000000 00000000 CIDR - Instead of separating the network and host portion of an IP address on a octet boundary, you can separate the two on any bit boundary. VLSM - Variable length subnetwork masks can be used throughout a routed network. For example, one router interface might have a /25 bit mask, while another interface may have a /30. This may be useful for summarization. D. ARP Translation (binding) of a network layer address to a data link (hardware) address. 1. Table lookup - hardware to IP address pair, stored in a file or memory 2. Closed-form computation - network address computed based on hardware address 3. Message exchange - host exchanges messages with a resolver host to request appropriate address - most common Lookups can be stored in a ARP cache. ARP messages are special messages for the data link they are now. No IP packet format info per se. However, all data link networks use ARP exclusively to obtain an IP address. Example ARP lookup for a specific ethernet address E. BOOTP/DHCP Automated configuration of a IP address and parameters which need to be set. Requirements: 1. IP Address 2. Default router 3. Subnet mask 4. DNS address 5. other/misc. Reasons: 1. Mobility 2. Address re-use 3. Managability DHCP removes restriction of manually configuring BOOTP server with hardware addresses. DHCP uses "leases" for IP address allocation. F. Introduction to DNS Mapping of a name to a IP address. Hierarchical based like IP address hierarchy. Primarily used to provide an easier to use interface for humans.