Review Network Protocols Protocol Agreement between two parties as to how information is to be transmitted CS162 Operating Systems and Systems Programming Lecture 23 Example system calls are the protocol between the operating system and application Networking examples many levels Physical level mechanical and electrical network e g how are 0 and 1 represented Link level packet formats error control for instance the CSMA CD protocol Network level network routing addressing Transport Level reliable message delivery Networking III Protocols on today s Internet NFS November 19 2008 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Transport 11 17 08 Review IP Packet Format IP Packet Format IP Ver4 Time to Live hops Type of transport protocol 0 Size of datagram header data 15 16 31 4 IHL ToS Total length 16 bits 16 bit identification flags 13 bit frag off TTL protocol 16 bit header checksum 32 bit source IP address 32 bit destination IP address options if any UDP Network Physical Link IP Header Length RPC WWW e mail ssh TCP IP Ethernet ATM Packet radio Kubiatowicz CS162 UCB Fall 2008 Lec 22 2 Goals for Today Flags Fragmentation to split large messages IP header 20 bytes Networking Continue discussion of reliable messaging Sequence numbers for ordering Acknowledgments for reliability TCP windowing Sockets Messages Send receive One vs two way communication Data Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Gagne Many slides generated from my lecture notes by Kubiatowicz 11 17 08 Kubiatowicz CS162 UCB Fall 2008 Lec 22 3 11 17 08 Kubiatowicz CS162 UCB Fall 2008 Lec 22 4 Performance Considerations Sample Computations E g Ethernet within Soda Before we continue need some performance metrics Overhead CPU time to put packet on wire Throughput Maximum number of bytes per second Depends on wire speed but limited by slowest router or by congestion Latency time until first bit of packet arrives at receiver So 4KB 100Mb s 0 3 milliseconds same order as disk Raw transfer time overhead at each routing hop Router LW1 LR1 E g ATM within Soda Latency same as above assuming no routing Throughput 155Mb s Throughput delay 4KB 155Mb s 200 Router LW2 LR2 E g ATM cross country Lw3 Latency assuming no routing 3000miles 5000ft mile 15 milliseconds Contributions to Latency Wire latency depends on speed of light on wire How many bits could be in transit at same time 15ms 155Mb s 290KB about 1 1 5 ns foot In fact Berkeley MIT Latency 45ms Router latency depends on internals of router 872KB in flight if routers have wire speed throughput Could be 1 ms for a good router Question can router handle full wire throughput Requirements for good performance Local area minimize overhead improve bandwidth Wide area keep pipeline full What is the End to end MTU Minimum across path What is the End to end Throughput Minimum across path 11 17 08 Latency speed of light in wire is 1 5ns foot which implies latency in building 1 s if no routers in path Throughput 10 1000Mb s Throughput delay packet doesn t arrive until all bits Kubiatowicz CS162 UCB Fall 2008 Lec 22 5 Sequence Numbers Ordered Messages 11 17 08 Physical media packet not transmitted received If transmit close to maximum rate get more throughput even if some packets get lost If transmit at lowest voltage such that error correction just starts correcting errors get best power bit Ask remote machine to first do x then do y etc Unfortunately underlying network is packet based Packets are routed one at a time through the network Can take different paths or be delayed individually IP can reorder packets P0 P1 might arrive as P1 P0 Congestion no place to put incoming packet Solution requires queuing at destination Need to hold onto packets to undo misordering Total degree of reordering impacts queue size Ordered messages on top of unordered ones Assign sequence numbers to packets 0 1 2 3 4 If packets arrive out of order reorder before delivering to user application For instance hold onto 3 until 2 arrives etc Reordering among connections normally doesn t matter If restart connection need to make sure use different range of sequence numbers than previously Lec 22 7 Point to point network insufficient queue at switch router Broadcast link two host try to use same link In any network insufficient buffer space at destination Rate mismatch what if sender send faster than receiver can process Reliable Message Delivery on top of Unreliable Packets Need some way to make sure that packets actually make it to receiver Every packet received at least once Every packet received at most once Sequence numbers are specific to particular connection Kubiatowicz CS162 UCB Fall 2008 Lec 22 6 Reliable Message Delivery the Problem All physical networks can garble and or drop packets Several network services are best constructed by ordered messaging 11 17 08 Kubiatowicz CS162 UCB Fall 2008 Can combine with ordering every packet received by process at destination exactly once and in order 11 17 08 Kubiatowicz CS162 UCB Fall 2008 Lec 22 8 A Using Acknowledgements B A Packe t Timeout a ck Packe t How to deal with message duplication Solution put sequence number in message to identify re transmitted packets B Receiver checks for duplicate s Discard if detected Requirements Packe t Sender keeps copy of unack ed messages Easy only need to buffer messages a ck Receiver tracks possible duplicate messages Hard when ok to forget about received message How to ensure transmission of packets Alternating bit protocol Detect garbling at receiver via checksum discard if bad Receiver acknowledges by sending ack when packet received properly at destination Timeout at sender if no ack retransmit Some questions If the sender doesn t get an ack does that mean the receiver didn t get the original message No What if ack gets dropped Or if message gets delayed Sender doesn t get ack retransmits Receiver gets message twice acks each 11 17 08 Kubiatowicz CS162 UCB Fall 2008 Lec 22 9 Better messaging Window based acknowledgements Window based protocol A Send up to N packets without ack Each packet has sequence number Receiver acknowledges each packet Ack says received all packets up to sequence number X send more Acks serve dual purpose Reliability Confirming packet received Flow Control Receiver ready for packet B 0 4 k ac Remaining space in queue at receiver can be returned with ACK Sender will timeout waiting for ack packet Resend missing packets
View Full Document
Unlocking...