------------------------- Week 03 Notes for CST8165 ------------------------- -Ian! D. Allen - idallen@idallen.ca - www.idallen.com Remember - knowing how to find out an answer is more important than memorizing the answer. Learn to fish! RTFM! (Read The Fine Manual) Review ------ - you know the four Unix networking system calls for servers - you know the difference between read/write and recv/send - you know that network sockets may not write all the data - you can write pseudocode for a forking, looping "echo" server (server2.c) - you know what assert() does - you can rewrite code to remove excessive indentation - you can write code for binary data that doesn't have NUL on the end - you can use GDB without fear - you know how EOF works from the keyboard - your error messages have four qualities (from programming_style.txt) - you write good comments (from programming_style.txt) - you know what goes in a header .h file - you know the list of functions that are prohibited in this course (and why) - you know what FLOSS means - you know the Internet is dumb - you know what Net Neutrality is about - you know which organization coordinate the Internet names and numbers - you know the names of the three big categories of TCP/UDP ports - you remember the RFC1918 port ranges and masks References to Notes files (required reading): ------------------------- programming_style.txt deep_indentation.txt buffer_overflows.txt header_files.txt makefiles.txt screendumps.txt TCP/IP References ----------------- http://www.tcpipguide.com/ Encapsulation - Protocol Layering --------------------------------- http://www.tcpipguide.com/free/t_IPDatagramEncapsulation.htm - encapsulation as data moves down the stack, de-encapsulation moving up - large packets may be "fragmented" by lower layers - seearch for "fragmentation considered harmful" Review the OSI network stack and Internet network stack: http://en.wikipedia.org/wiki/Internet_protocol_suite http://en.wikipedia.org/wiki/TCP/IP_model OSI Seven Layers - OSI divides into seven layers with standard names TCP/IP Model has Four or Five Layers (but strict layering is discouraged) - the Internet grew up with four layers: 1. Process / Application Layer e.g. DHCP, DNS, FTP, HTTP, IMAP, IRC, NNTP, POP, SIP, SMTP, etc. 2. Host-to-Host (Transport) Layer e.g. TCP, UCP, ICMP, IGMP, etc. 3. Internet / Internetworking / IP Layer e.g. IPV4, IPV6, IPsec, ARP, RAPR, OSPF, BGP, etc. 4. Network Access Layer e.g. 802.11, Wi-Fi, Ethernet, Token Ring, PPP, PPTP, ISDN, etc. - the bottom layer is now often split in two: 4A) Network Access Layer / Data Link Layer 4B) Physical Layer (optical fiber, coax, twisted-pair, etc.) "The original TCP/IP reference model consists of 4 layers, but is now viewed by some as a 5-layer model, even though no IETF standards-track document has accepted a five-layer model, and IETF documents indeed deprecate strict layering of all sorts. Given the lack of acceptance of the five-layer model by the body with technical responsibility for the protocol suite, it is not unreasonable to regard five-layer presentations as teaching aids, possibly to make the IP suite architecture more familiar to those students who were first exposed to OSI layering." -- http://en.wikipedia.org/wiki/TCP/IP_model "No document officially specifies the model; different names are given to the layers by different documents, and different numbers of layers are shown by different documents. There are versions of this model with four layers and with five layers." "In modern text books, the model has evolved into a five-layer version that splits Layer 1 into a Physical layer and a Network Access layer, corresponding to the physical layer and data link layer of the OSI model. The Internet or Internetworking layer is named Network layer." "An updated IETF architectural document [1] even contains a section entitled: "Layering Considered Harmful". Emphasizing layering as the key driver of architecture is not a feature of the TCP/IP model, but rather of OSI. Much confusion comes from attempts to force OSI-like layering onto an architecture that minimizes their use." -- http://en.wikipedia.org/wiki/TCP/IP_model Comparison of OSI and TCP/IP: http://www.tcpipguide.com/free/t_TCPIPArchitectureandtheTCPIPModel-2.htm - be aware of the confusion between what TCP/IP names the layers and what the OSI model names the layers! Encapsulation: Your application data (perhaps containing its own header information) is passed to the computer's TCP/IP stack, which wraps a TCP header around it (containing port information), then an IP header around that (containing information such as source/destination address). That wrapped packet is passed down to the network hardware, which wraps your packet with hardware framing bits that will get it out your network card, onto the network, and into the next network card. Your Ethernet card has a unique MAC address that is used at the Ethernet level to pass packets around between Ethernet cards. Also: "2.2. Low level Nonsense and Network Theory" in http://beej.us/guide/bgnet/output/html/singlepage/bgnet.html#lowlevel This "packetization" of your data across the Internet may be visible to your application. Low-level IP packets may be dropped, fragmented, arrive late, or arrive out-of-sequence (and no amount of money can change that on the public Internet, at least until the big telcos get their way). Applications writing to network sockets must be prepared to loop until all bytes are sent. Applications reading from network sockets must be prepared to receive data in arbitrary chunks. ----------------------------------------------------------------------------- Q: Give examples of programs/protocols/methods at each layer: see Figure 1 in http://tools.ietf.org/html/rfc791 see sidebar in http://en.wikipedia.org/wiki/TCP/IP_model Q: With respect to the original four-layer Internet protocol stack, what is the difference between an IP router and an Ethernet switch or hub? Q: Show how data from an application (e.g. TFTP) is encapsulated/de-encapsulated as it moves down the four-layer TCP/IP stack, gets shipped over an Ethernet, passes through a switch, passes through an IP router, and is finally delivered to another application. - See Figure 2 in http://tools.ietf.org/html/rfc791 - See http://en.wikipedia.org/wiki/Image:UDP_encapsulation.svg - See http://en.wikipedia.org/wiki/Image:IP_stack_connections.png - See http://www.tcpipguide.com/free/t_IPDatagramEncapsulation.htm Q: T/F IP packets arrive in the order in which they are sent. Q: T/F IP packets are reliable. Q: Discuss how network packetization affects data transfer (both writing and reading) in an application. ----------------------------------------------------------------------------- Dotted Quad (Dotted Decimal) structure (Review) ----------------------------------------------- IP addresses are part network number and part host number depending on how you divide up the 32 bits, e.g. address 1.2.3.4 might be host number 4 on network 1.2.3 (a /24 network), or it might be host 3.4 on network 1.2 (a /16 network), or host 2.3.4 on network 1 (a /8 network). The division of bits doesn't have to be on an 8-bit (one-byte) boundary, so you will find nets given as 1.2.3.0/25 (25 bit network, 7-bit host). Some nice properties apply to a "network" of hosts, including limiting of traffic and being able to direct traffic to a large number of hosts by using just the network number: http://www.ralphb.net/IPSubnet/ipaddr.html http://www.networkcomputing.com/netdesign/1122ipr-full.html In old-style traditional routing, sub-networks and hosts are not allowed to use numbers that are either all-zeroes or all-ones. All-ones addresses are interpreted as broadcast addresses for their networks - packets sent to these addresses are processed by every node on the network. (All-zeroes used to be broadcast addresses some decades ago.) Q: Why not just put all the machines on the same network? Q: What happens if you send an ICMP echo "ping" to a network broadcast address? (Most hosts are hardened against this these days.) Q: Suppose you forge your IP source address and then send a ping to a network broadcast address with a large number of hosts on it? http://www.webopedia.com/TERM/S/smurf.html ----------------------------------------------------------------------------- CIDR, Subnetting, Supernetting (Review) --------------------------------------- http://www.zegelin.com/computers_files/ref/IP_Addressing.html - diagrams of bits for traditional Class A,B,C networking - Figure 14: "Notice how sequential subnet numbers do not appear to be sequential when expressed in dotted-decimal notation. This can cause a great deal of misunderstanding and confusion since everyone believes that dotted-decimal notation makes it much easier for human users to understand IP addressing. In this example, the dotted-decimal notation obscures rather than clarifies the subnet numbering scheme!" http://tools.ietf.org/html/rfc1518 - the CIDR proposal Originally, IP addresses were classified strictly as Class A, B, C depending on the size of the network part. Class A addresses used the top 8 bits for the network number (starting with 0); Class B used 16 bits (starting with 10); Class C used 24 bits (starting with 110). The top few bits of an IP address decided whether an address was A, B, or C. Pre-classless (the old Class A,B,C way) - Classful addressing Figure 5 is a nice diagram of how the top bits of the IP address determined the old Class A,B,C addressing: - http://www.garykessler.net/library/tcpip.html#IPadd "Although the original intent of having Classes was to allow for flexible addressing, experience showed that the hard boundary of the three Classes actually made the addressing less flexible. For example, if a site connecting to the Internet needed to address 300 hosts, then a Class C network wouldn't be adequate and a Class B would need to be assigned. This resulted in poor utilization of the assigned address space and caused a faster-than-necessary rate of consumption of the available IP address space." http://www3.ietf.org/proceedings/99jul/I-D/draft-ietf-idr-aggregation-tutorial-01.txt When the number of IP numbers started to run scarce, the Internet changed to using an arbitrary number of bits: "CIDR removed the idea of Classes from IP. Instead of having networks with an implied number of bits referring to network/host, there are "prefixes" with an associated mask explicitly identifying which bits refer to network/host. For example, the prefix "38.245.76.0" with a mask of "255.255.255.0" has 24 bits of network and 8 bits of host (i.e., it can address the same number of hosts as a Class C network even though the prefix is in the Class A range). The CIDR paradigm prefers the term "prefix" over "network" because it's more clear that no Class is being implied. Another way to write this example prefix is "38.245.76.0/24", meaning that the mask contains 24 1s in the high-order portion of the mask." http://www3.ietf.org/proceedings/99jul/I-D/draft-ietf-idr-aggregation-tutorial-01.txt July 1997 CIDR throws out all the traditional classes and subnetting. You are allowed to have subnets that are all-zeroes or all-ones. "The solution is simple: someone just issued an edict saying "forget everything you learned, we won't bother with those rules any more". There's even a command to tell the routers themselves that they should ignore the rules - "ip classless" When you break the rules like this, and allow netmasks that end in all 0's or all 1's, it's called "CIDR" - Classless InterDomain Routing." http://www.gtoal.com/subnet.html Subnetting is the process of being handed a network address and being able to subdivide it into subnets, correctly deciding how many bits to use for the subnet and how many bits to leave for the host addresses. - RFC: http://tools.ietf.org/html/rfc950 Modern standards let you use subnets that are all zeroes and all ones; but, you might want to avoid them so that legacy devices still handle your packets correctly. ( http://www.ralphb.net/IPSubnet/restr.html ) Subnet calculator tool (with explanations!): http://www.subnetmask.info/ CIDR vs. traditional - see http://www.ipprimer.com/addressing.cfm "Although RFC 1812 came out in June of 1995(!), most certification tests still test you on the RFC 950 rules, for (in my opinion) one of the following reasons: * Their software still follows RFC 950 rules (this is rare.) * Since RFC 1812 simplifies things significantly, there's not enough material to test on. Test items from RFC 950 are added as "filler". * They are ignorant of the fact that the material on their tests has been out of date for more than five years. * They are mean-spirited, perniciously forcing you to learn material that will never be relevant to your job." Closer to the Internet backbone, sets of contiguous networks are grouped together under "super-net" network masks. Instead of having identical routes for the contiguous networks, the network mask is "backed up" (shortened) so that the contiguous networks are included in the one mask. Super-netting greatly reduces the size of the routing tables by replacing multiple identical routes with one super-net route. "a supernet is a block of contiguous subnetworks addressed as a single subnet." - http://en.wikipedia.org/wiki/Supernet "You can also aggregate formerly class "C" networks together using network prefixes fewer than 24 bits long. For example, you could combine the formerly class "C" networks 192.168.2.0 and 192.168.3.0 into a single subnet with 510 usable addresses, by using a network mask of 255.255.254.0. What you're really saying here is that the last bit of the third byte now belongs to the "host number" portion of the address, and the "network prefix" is 23 bits (two bytes and seven bits) long. Therefore, the two networks being combined must be contiguous, and the third byte must be even on the lower numbered network. You could not combine, for example, 192.168.2.0 and 192.168.5.0; [nor] could you combine 192.168.11.0 and 192.168.12.0. You could follow similar rules to combine four contiguous class "C" style networks, but the third byte of the lowest numbered network would have to be a multiple of four. This sort of thing is routinely done (on an increasingly larger scale) as you get closer to the Internet backbones." - http://www.ipprimer.com/addressing.cfm In other words, if you have a set of 2**N contiguous networks, you can super-net them all into one single super-network by shortening the network mask by N bits, provided that (a) all 2**N networks are in the same network after the shortening (they all start with the same network prefix), and (b) those N bits cover all 2**N numbers, starting at zero and ending at (2**N)-1. For (a) and (b) to be true, the lowest-numbered network prefix in the set to be aggregated must be evenly divisible by N, e.g. the last N bits of the lowest-numbered network must be zeroes, so that the network mask can be shortened by N bits. e.g. The four contiguous class "C" networks 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24, and 192.168.3.0/24 can be super-netted under the one route 192.168.0.0/22 that has a network mask two bits shorter. This only works because (a) all four networks are in the same network 192.168.0.0/22 after the shortening (they all start with the same 22-bit prefix), and (b) the two bits in question have the four values 00, 01, 10, and 11 (all possible two-bit patterns). Note that the last two bits of the lowest-numbered network 192.168.0.0/24 are zeroes. e.g. The four contiguous class "C" networks 192.168.4.0/24, 192.168.5.0/24, 192.168.6.0/24, and 192.168.7.0/24 can be super-netted under the one route 192.168.4.0/22 that has a network mask two bits shorter. This only works because (a) all four networks are in the same network 192.168.4.0/22 after the shortening (they all start with the same 22-bit prefix), and (b) the two bits in question have the four values 00, 01, 10, and 11 (all possible two-bit patterns). Note that the last two bits of the lowest-numbered network 192.168.4.0/24 are zeroes. e.g. The four contiguous class "C" networks 192.168.8.0/24, 192.168.9.0/24, 192.168.10.0/24, and 192.168.11.0/24 can be super-netted under the one route 192.168.8.0/22 that has a network mask two bits shorter. This only works because (a) all four networks are in the same network 192.168.8.0/22 after the shortening (they all start with the same 22-bit prefix), and (b) the two bits in question have the four values 00, 01, 10, and 11 (all possible two-bit patterns). Note that the last two bits of the lowest-numbered network 192.168.8.0/24 are zeroes. For the next example, note that the network part of 192.168.10.0/22 and 192.168.11.0/22 are both the same as the network part of 192.168.8.0/22, and the network part of 192.168.12.0/22 and 192.168.13.0/22 are both the same as the network part of 192.168.12.0/22. That is, the first two and the second two are on different /22 networks. Also note that the network 192.168.10.0/22 should really be written as 192.168.8.0/22, since the notation shows that only the first 22 bits are relevant for a network. (In other words, the network 192.168.10.0/22 is the same as the network 192.168.8.0/22 since we ignore everything except the first 22 bits.) e.g. The four contiguous class "C" networks 192.168.10.0/24, 192.168.11.0/24, 192.168.12.0/24, and 192.168.13.0/24 can *not* be super-netted under the one route 192.168.10.0/22 that has a network mask two bits shorter. This fails because (a) 192.168.11.0/24 and 192.168.12.0/24 differ in the first 22 bits - they aren't both under the same 192.168.10.0/22 network prefix (which is really 192.168.8.0/22). (192.168.11.0/24 is under 192.168.8.0/22 but 192.168.12.0/24 is under 192.168.12.0/22 - they can't both be expressed under the same /22 network prefix and thus can't be super-netted together.) Note that the last two bits of the lowest-numbered network 192.168.10.0/24 are *not* zeroes. (They are "10", indicating that the network isn't divisible by four.) e.g. The eight contiguous class "C" networks 192.168.0.0/24 through 192.168.7.0/24 can be super-netted under the one route 192.168.0.0/21 that has a network mask three bits shorter. This only works because (a) all eight networks are in the same network 192.168.0.0/21 after the shortening (they all start with the same 21-bit prefix), and (b) the three bits in question have the eight values 000...111 (all possible three-bit patterns). Note that the last three bits of the lowest-numbered network 192.168.0.0/24 are zeroes. e.g. The eight contiguous class "C" networks 192.168.8.0/24 through 192.168.15.0/24 can be super-netted under the one route 192.168.8.0/21 that has a network mask three bits shorter. This only works because (a) all eight networks are in the same network 192.168.0.0/21 after the shortening (they all start with the same 21-bit prefix), and (b) the three bits in question have the eight values 000...111 (all possible three-bit patterns). Note that the last three bits of the lowest-numbered network 192.168.8.0/24 are zeroes. e.g. The eight contiguous class "C" networks 192.168.9.0/24 through 192.168.16.0/24 can *not* be super-netted under the one route 192.168.9.0/21 that has a network mask three bits shorter. The quickest way to know this is to note that the last three bits of the lowest-numbered network 192.168.9.0/24 are *not* zeroes. (They are "001", indicating that the network isn't divisible by eight.) This fails because (a) 192.168.15.0/24 and 192.168.16.0/24 differ in the first 21 bits - they aren't both under the same 192.168.9.0/21 network prefix (which is really 192.168.8.0/21 since we ignore all but the first 21 bits). (192.168.15.0/24 is under 192.168.8.0/21 but 192.168.16.0/24 is under 192.168.16.0/21 - they can't both be expressed under the same /21 network prefix and thus can't be super-netted together.) ----------------------------------------------------------------------------- Q: Know how to divide a network into subnets. Q: Given an IP address and network mask, determine the network prefix (the /nn number), the network number, and the broadcast address. Q: Given an IP network address, apply subnetting to the address to supply a certain number of subnets, or a certain number of hosts. Q: What is the maximum number of hosts you can have (avoiding the all-zero and all-one networks and hosts) for a Class C address and a 4-bit subnet mask? (How many usable subnets are available with with four bits? How many usable hosts can reside on each of those sub-networks? Multiply.) Answer: 14 networks of 14 hosts = 196 - http://www.ralphb.net/IPSubnet/example.html - http://www.ralphb.net/IPSubnet/restr.html Q: What if you didn't have to avoid the all-zero or all-ones subnets? x.x.x.x/24+4 -> 16 usable subnets, each with 32-(24+4)=4 bits for hosts -> 16 subnets times (2**4 minus two hosts) = 224 hosts Q: What is the next available subnet address above this one 192.168.1.0/24 ? Answer: 192.168.2.0 (/24) - add one to the network part of the 32-bit number Q: What is the next available subnet address above this one 192.168.1.0/25 ? Answer: 192.168.1.128 (/25) - add one to the network part of the 32-bit number Q: What is the lowest usable host address in the 192.168.1.128/25 network? Answer: 192.168.1.129 (/25) - avoid the all-zero host address 192.168.1.128 (/25) Q: Discuss the use of subnets that are all-zeroes or all-ones. Q: Give an example (network and mask) of a Class A,B,C address. Q: What advantage does super-netting have in backbone routers? Q: You can super-net 192.168.2.0 and 192.168.3.0 into a single /23 subnet with 510 usable addresses, by using a network mask of 255.255.254.0. Why can't you super-net 192.168.5.0 and 192.168.6.0 the same way? ( http://www.ipprimer.com/addressing.cfm ) Q: Can you super-net the eight networks 192.168.20.0/24 through 192.168.27.0/24 into one /21 network? Why or why not? (Hint: Look at the last N bits of the lowest-numbered network.) ----------------------------------------------------------------------------- IP Routing (Review) ------------------- Reference: http://www.dcs.gla.ac.uk/~lewis/networkpages/m05s05IPForwarding.htm When an application's machine wants to send a packet on the network, the low-level network hardware (which knows nothing about IP addresses) needs to know "the next stop" hardware network interface for the packet. Either the packet is destined directly for a host on one of the attached networks (often a machine is on only one single network); or, the packet has to be sent off to the network card of a "gateway" machine on the local network, and the gateway machine will know where to forward it (to another hardware network card on another network, and so on...). http://tools.ietf.org/html/rfc950 - Internet Standard Subnetting Procedure (August 1985) - introduced subnetting to the Internet - setion 2.2 shows code fragment used in IP routing and subnet routing - note that the IP address and IP mask are unique to each network interface Either way, local or gateway, your system has to send the IP packet, encapsulated for the local network hardware (e.g. for Ethernet). At or near the bottom of the network stack, below IP, is the Network layer (e.g. Ethernet). That encapsulation - the finding out of the network card MAC (Media Access Control) address - is often assisted by a low-level networking protcol such as ARP (Address Resolution Protocol). - http://en.wikipedia.org/wiki/MAC_address - ARP converts between Ethernet hardware (MAC) and IP addresses - ARP is part of both "layers" (IETF doesn't like the "layers" concept) http://www.garykessler.net/library/tcpip.html#ARP Routing Tables Explained - http://www.freesoft.org/CIE/Topics/116.htm - http://www.dcs.gla.ac.uk/~lewis/networkpages/m05s05IPForwarding.htm Routing vs. Switching http://www.networkcomputing.com/netdesign/1122ippart2.html - routers forward based on IP address (OSI Layer 3) - must open up the Ethernet packet and look at the IP header - switches and hubs forward packets based on MAC address (OSI Layer 2) - don't look inside the Ethernet packets - no IP info used Indirect (gateway) routing is used when the network numbers of the source and destination do not match: - the packet must leave the local network (is not in this ARP domain) - must be forwarded elsewhere by a known "gateway" (a router) - a gateway is a node that knows how to reach the destination, or at least knows where to send a packet if it doesn't know - backbone routers may have different gateways for different networks Path Determination - which way to send a packet? - http://www.freesoft.org/CIE/Topics/117.htm - http://www.freesoft.org/CIE/Topics/118.htm Algorithms use 'metrics' to determine path. Metrics - cost, length, etc Algorithms populate routing tables, tables are used for determination * If two routing prefix paths match, the *longest* prefix match is preferred. - the route 1.2.3.0/25 is preferred over 1.2.3.0/24 Default route: 0.0.0.0/0 or 0.0.0.0/0.0.0.0 - every /nn match has more 1-bits in the mask than /0 - thus /0 is always a last choice if nothing else matches Routing is a way of getting packets from one place to another Routing software determines the next hop for a datagram Specifically does 2 things: 1. Determines the (optimal) path 2. Delivers the datagram The network can adjust routing tables according to network changes: Router receives change notifications and recalculates its routing table Updates to a routing table triggers notifications sent out to other routers Minimalized human config required (setup) Be careful that the updates don't cause a "storm" or route instability Routing Protocols needed to decide on global Internet routing tables: Ref: http://www.freesoft.org/CIE/Topics/87.htm - interior protocols: http://www.freesoft.org/CIE/Topics/119.htm - RIP - Router Information Protocol (old - not CIDR) - used internally http://www.freesoft.org/CIE/Topics/90.htm - very widely used - but 1970s design, no CIDR - OSPF - Open Shortest Path First - replaces RIP, used internally http://www.geocities.com/Heartland/4394/work/ospf.html http://www.freesoft.org/CIE/Topics/89.htm - exterior protocols: http://www.freesoft.org/CIE/Topics/120.htm - BGP4 - Border Gateway Protocol (v4) - used between large nets http://www.freesoft.org/CIE/Topics/88.htm - Cisco protocols (IGRP, EIGRP) - etc. Tracing routing in Unix/Linux: mtr and traceroute, "traceroute -n" (RTFM) - lost or blocked return ICMP packets print "*" Display the local routing tables in Unix/Linux kernel: Linux Commands: "ip route list" or just "ip route" Old way (Unix): "route" and "netstat -r" - shows the known network interface routes, including default route (gateway) ----------------------------------------------------------------------------- Q: How does my computer know if an IP address is on the local network? Q: How does my machine know what to do with an IP packet if the packet IP address isn't on the local network? Q: Does my computer have routing tables for the Internet? Does my machine know how a packet will travel to Google.ca ? Q: T/F Ethernet switches and hubs forward based on IP addresses. Q: What is the purpose of network routing? Q: T/F To send packets to machines on your local network, you first send the packet to the gateway. Q: If two routing prefixes match a packet, which one is chosen? Q: Why is the default address always chosen last? http://www.freesoft.org/CIE/Topics/116.htm Q: What do BGP and OSPF stand for? What is each used for? Q: What interior/internal routing protocol is replacing the old RIP protocol? Q: T/F - Both BGP and OSPF are designed to work on a local network. Q: What do all the fields in the output of a traceroute mean? Q: T/F "ip route" will show the IP address of your gateway