CS155a E Commerce Lecture 4 Sept 18 2001 How Does the Internet Work continued Acknowledgements J Rexford and V Ramachandran Layering in the IP Protocols HTTP Web Domain Name Service Telnet Transmission Control Protocol User Datagram Protocol Internet Protocol SONET Ethernet Real Time Protocol ATM Internet Architecture interdomain protocols dial in access ISP 2 private peering intradomain protocols destination NAP ISP 1 gateway router access router ISP 3 commercial customer destination IP Connectionless Paradigm No error detection or correction for packet data Higher level protocol can provide error checking Successive packets may not follow the same path Not a problem as long as packets reach the destination Packets can be delivered out of order Receiver can put packets back in order if necessary Packets may be lost or arbitrarily delayed Sender can send the packets again if desired No network congestion control beyond drop Send can slow down in response to loss or delay IP Packet Structure 4 bit 8 bit 4 bit Version Header Type of Service Length TOS 16 bit Identification 8 bit Time to Live TTL 8 bit Protocol 16 bit Total Length Bytes 3 bit Flags 13 bit Fragment Offset 16 bit Header Checksum 32 bit Source IP Address 32 bit Destination IP Address Options if any Payload 20 byte Header Main IP Header Fields Version number e g version 4 version 6 Header length number of 4 byte words Header checksum error check on header Source and destination IP addresses Upper level protocol e g TCP UDP Length in bytes up to 65 535 bytes IP options security routing timestamping etc Time to Live Field Potential robustness problem What happens if a packet gets stuck in a routing loop What happens if the packet arrives much later Time to live field in packet header TTL field decremented by each router on the path Packet is discarded when TTL field reaches 0 Discard generates timer expired message to source Expiry message exploited in traceroute tool Generate packets with TTL of i 1 2 3 4 Extract router id from the timer expired message Provides a way to gauge the path to destination Type of Service Bits Initially envisioned for type of service routing Low delay high throughput high reliability etc However current IP routing protocols are static And most routers have first in first out queuing So the ToS bits are ignored in most routers today Now heated debate for differentiated services ToS bits used to define a small number of classes Affect router packet scheduling and buffering polices Arguments about consistent meaning across networks Transmission Control Protocol TCP Byte stream socket abstraction for applications Retransmission of lost or corrupted packets Flow control to respond to network congestion Simultaneous transmission in both directions Multiplexing of multiple logical connections TCP connection source network destination TCP Header 16 bit source port number 16 bit destination port number 32 bit sequence number 32 bit acknowledgement number 4 bit header length U A P R S F R C S S Y I G K H T N N 16 bit TCP checksum 16 bit window size 16 bit urgent pointer Options if any Payload 20 byte Header Establishing a TCP Connection FIN Data ACK CK FIN A ACK A CK SYN A SYN B time Three way handshake to establish connection Host A sends a SYN open to the host B Host B returns a SYN acknowledgement ACK Host A sends an ACK to acknowledge the SYN ACK Closing the connection Finish FIN to close and receive remaining bytes and other host sends a FIN ACK to acknowledge Reset RST to close and not receive remaining bytes Lost and Corrupted Packets Detecting corrupted and lost packets Error detection via checksum on header and data Sender sends packet sets timeout and waits for ACK Receiver sends ACKs for received packets Retransmission from sender Sender retransmits lost corrupted packets Receiver reassembles and reorders packets Receiver discards corrupted and duplicated packets Packet loss rates are high e g 10 causing significant delay especially for short Web transfers TCP Flow Control Packet loss used to indicate network congestion Router drop packets when buffers are nearly full Affected TCP connection reacts by backing off Window based flow control Sender limits number of outstanding bytes Sender reduces window size when packets are lost Initial slow start phase to learn a good window size TCP flow control header fields Window size maximum of outstanding bytes Sequence number byte offset from starting Acknowledgement number cumulative bytes User Datagram Protocol UDP Some applications do not want or need TCP Don t need recovery from lost or corrupted packets Don t want flow control to respond to loss congestion Amount of UDP packets is rapidly increasing Commonly used for multimedia applications UDP traffic interferes with TCP performance But many firewalls do not accept UDP packets Dealing with the growth in UDP traffic Pressure for applications to apply flow control Future routers may enforce TCP like behavior Need better mathematical models of TCP behavior Getting an IP Packet From A to B Host must know at least three IP addresses Host IP address to use as its own source address Domain Name Service to map names to addresses Default router to reach other hosts e g gateway Simple customer company Connected to a single service provider Has just one router connecting to the provider Has a set of IP addresses allocated in advance Does not run an Internet routing protocol Connecting Networks Autonomous System AS Autonomous System AS EarthLink AOL Autonomous System WorldNet A collection of IP subnets and routers under the same administrative authority Interior Routing Protocol e g Open Shortest Path First Exterior Routing Protocol e g Border Gateway Protocol Open Shortest Path First OSPF Routing Network is a graph with routers and links Each unidirectional link has a weight 1 63 535 Shortest path routes from sum of link weights Weights are assigned statically configuration file Weights based on capacity distance and traffic Flooding of info about weights and IP addresses Large networks can be divided into multiple domains Example Network and Shortest Path 6 8 9 0 24 7 0 0 0 8 5 5 5 0 24 2 3 2 1 1 1 3 link router 5 12 34 0 0 16 OSPF domain 4 3 1 2 3 0 24 4 5 0 0 16 IP Routing in OSPF Each router has a complete view of the topology Each router transmits information about its links Reliable flooding to all routers in the domain Updates periodically or on link failure installation Each router computes