New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CS 621 Network Programming Notes/Quiz/Midterm

by: Jose

CS 621 Network Programming Notes/Quiz/Midterm 621

Marketplace > University of San Francisco > ComputerScienence > 621 > CS 621 Network Programming Notes Quiz Midterm

Network Programming
Eunjin (EJ) Jung

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes, 2 Quizzes, and 1 midterm
Network Programming
Eunjin (EJ) Jung
75 ?




Popular in Network Programming

Popular in ComputerScienence

This 40 page Bundle was uploaded by Jose on Thursday October 2, 2014. The Bundle belongs to 621 at University of San Francisco taught by Eunjin (EJ) Jung in Spring2014. Since its upload, it has received 269 views. For similar materials see Network Programming in ComputerScienence at University of San Francisco.

Similar to 621 at USF

Popular in ComputerScienence


Reviews for CS 621 Network Programming Notes/Quiz/Midterm


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/02/14
Include TOR o confidentiality and anonymity Know how to read an IP address 52 Error detection correction o bitlevel error detection and correction EDC o detecting and correcting the corruption of bits in a linklayer frame sent from one node to another physically connected neighboring node o two services often provided by the link layer o Even with the use of error detection bits there still may be undetected bit errors so receiver might deliver a corrupted datagram to the network layer o Three techniques for detecting errors in the transmitted data o Parity Checks to illustrate the basic ideas behind error detection and correction Use of a single parity bit to detect errors In an even parity scheme the sender simply includes one additional bit and chooses its value such that the total number of 1s in the d1 bits the original information plus a parity bit is even For odd parity changes the parity bit value is chosen such that there is an odd number of 1s Receiver operation is simple with a single parity bit 0 Receiver need only count the number of 1s in the received d1 bits If an odd number of 1valued bits are found with an even scheme the receiver knows that at least one bit error has occured More precisely it knows that some odd numbers of bit errors have occurred If an even number of bit error occured the receiver will not be able to detect the error Two dimensional parity o Parity of both the column and the row containing the flipped bit will be in error The receiver can thus not only detect the fact that a single bit error occured but can use the column and row indices of the column and row with parity errors to actually identify the bit that was corrupted and correct the error The ability of the receiver to both detect and correct errors is known as forward error correction FEC o Checksumming Methods which are typically used in the transport layer I One simple checksumming method is to simply sum the kbit integers and use the resulting sum as the errordetection bits o The Internet checksum is based on this approach Bytes of data are treated as 16bit integers and summed The 1s compliment of this sum then forms the Internet checksum that is carried in the segment header o The receiver checks the checksum by taking the 1s complement of the sum of the received data including the checksum and checking whether the result is all 1 bits If any of the bits are 0 an error is indicated o Cyclic Redundancy Checks which are typically used in the link layer CRC codecs I Consider the dbit piece of data D The sender and receiver must first agree on an r1 bit pattern known as a generator which we will denote as G We require that the most significant leftmost bit of G be 1 I For a given piece of data D the sender will choose r additional bits R and append them to D such that the resulting dr bit pattern is exactly divisible by G ie has no remainder using modulo2 arithmetic I The receiver divides the dr received bits by G If the remainder is nonzero the receiver knows that an error has occurred othenvise the data is accepted as correct 54 LAN addressing ARP Address Resolution Protocol PowerPoint Link Layer 542 to o ARP provides a mechanism to translate IP address to ink ayer address An ARP module in the sending host takes any IP address on the same LAN or subnet as input and returns the corresponding MAC address ARP straddles the boundary between the link and network layers 0 Each host and router has an ARP table which contains mappings of IP to MAC ARP table also contains a timeto ive TTL value which indicates when each mapping will be deleted from the table A typical expiration time for an entry is 20 minutes which sometimes causes IP errors 0 If a frame s destination address does not match the MAC address of the receiving adapter the the packet is loss unless it s addressed as a MAC broadcast o A link ayer address is variously called a LAN address a physical address or a MAC address 0 MAC address is 6 bytes long giving 2quot48 possible MAC addresses No two adapters have the same address o MAC addresses have a flat structure and a host with an Ethernet interface always has the same MAC address IP addresses have a hierarchical structure network part and host part and a host s IP address needs to be changed when the host moves ie changes the network to which it is a ached 54 Switches 0 Ethernet Frame Structure Preamble Destination Address Source Address Type Data CRC 0 Filtering is the switch function that determines whether a frame should be fonvarded to some interface or should just be dropped 0 Forwarding is the switch function that determines the interfaces to which a frame should be directed and then moves the frames to those interfaces 0 Switch filtering and fonvarding are done with a switch table The switch table contains entries for hosts and routers on a LAN An entry contains 1 a MAC address 2 the switch interface that leads toward that MAC address and 3 the time at which the entry was placed in the table 0 They re pug andplay devices because they require no intervention from a network administrator They re self learning devices 0 Advantages of switches elimination of collisions heterogeneous links better management 55 Multiprotocol Label Switching MPLS o MPLS is a packetswitched virtua circuit network in its own right It has its own packet formats and fonvarding behaviors MPLS seners interconnect to IP devices 0 The goal was not to abandon the destinationbased IP datagramfonvarding infrastructure for one based on fixedlength labels and virtual circuits but to augment it by selectively labeling datagrams and allowing routers to fonvard datagrams based on fixedlength labels rather than IP addresses when possible MPLS performs switching based on labels without needing to consider the IP address of a packet o The true advantages of MPLS lie not in the potential increases in switching speeds but rather in the new traffic management capabilities that MPLS enables MPLS provides the ability to fonvard packets along routes that would not be possible using standard IP routing protocols It s been used to implement virtual private networks VPNs It can also be used to perform fast restoration of MPLS fonvarding paths eg to route traffic over a precomputed failover path in response to link failure 0 An MPLS header is added between the layer2 Ethernet header and ayer 3 IP packet It contains fields for the label which serves the role of the virtua circuit identifier bits reserved for experimental use a single S bit which is used to indicate the end of a series of stacked MPLS headers and a time tolive field 0 Can only be send between routers that are both MPLS capable An MPLS router need not extract the destination IP address and perform a lookup of the longest prefix match in the fonvarding table 57 A day in the web 71 Multimedia networking applications o A multimedia network application is any network application that employs audio or video Videos have a high bit rate requirement It can be compressed trading off video quality with bit rate c There are 2 types of redundancy in video o Spatial redundancy is the redundancy within a given image lntuitively an image that consists of mostly white space has a high degree of redundancy and can be efficiently compressed without significantly sacrificing image quality o Temporal redundancy reflects repetition from image to subsequent image If for example an image and the subsequent image are exactly the same there is no reason to reencode the subsequent image it is more efficient simply to indicate during encoding that the subsequent image is exactly the same 72 Streaming stored video 0 Streaming stored video has 3 key distinguishing features o Streaming The technique where the client will be playing from one location in the video while at the same time receiving later parts of the video from the server It avoids having to download the entire video file and incurring a potentially long delay before playout begins o Interactivity Because the media is recorded the user may pause reposition fonvard reposition backward fast forward and so on through the video content o Continuous playout Data must be received from the server in time for its playout at the client othenvise users experience video frame freezing when the client waits for the delayed frames or frame skipping when the client skips over delayed frames 0 Most important performance feature for streaming video is average throughput o Streaming video systems can be classified into 3 categories UDP streaming HTTP streaming and adaptive HTTP streaming o A common characteristic of all 3 forms of video streaming is the extensive use of clientside application buffering to mitigate the effects of varying endtoend delays and varying amounts of available bandwidth between server and client There are two important advantages provided by client buffering Client side buffering can absorb variations in server to client delay If a particular piece of video data is delayed as long as it arrives before the reserve of receivedbutnot yet payed video is exhausted this long delay will not be noticed The server toclient bandwidth briefly drops below the video consumption rate a user can continue to enjoy continuous playback again as as long as the client application buffer does not become completely drained UDP Streaming O CDN O The server transmits video at a rate that matches the client s video consumption rate by clocking out the video chunks over UDP at a steady rate In addition to the senertoclient video stream the client and server also maintain in parallel a separate control connection over which the client sends commands regarding session state changes such as pause resume reposition and so on Suffers from 3 drawbacks I Due to the unpredictable and varying amount of available bandwidth between server and client constantrate UDP streaming can fail to provide continuous playout I Requires a media control server such as an RTSP server to process cient toserver interactivity requests and to track client state eg the client s playout point in the video whether the video is being paused or played and so no for each ongoing client sessions This increases the overall cost and complexity of deploying a largescale videoondemand system I Many firewalls are configured to block UDP traffic preventing the users behind these firewalls from receiving UDP video For Internet video companies the most straightfonvard approach to providing streaming video service is to build a single massive data center store all of its videos in the data center and stream the videos directly from the data center to clients worldwide I 3 Major problems with this o If the client center is far from the data center senerto cient packets will cross many communication links and if one of these links provides a throughput that is less than the video consumption rate the endto end throughput will also be below the consumption rate resulting in annoying freezing delays for the user o The popular videos will likely be sent many times over the communication links wasting bandwidth and increasing the cost o A single data center represents a single point of failure o In order to meet the challenges of distributing massive amounts of video data to users distributed around the world almost all major videostreaming companies make use of Content Distribution Networks CDNs A CDN manages servers in multiple geographically distributed locations stores copies of the videos and other content in its servers and attempts to direct each user request to a CDN location that will provide the best user experience The CDN can be owned by the content provider or a third party CDN that distributes content on behalf of multiple content providers I Goal is to set up a CDN close to end users thereby improving userperceived delay and throughput by decreasing the number of links and routers between the end user and the CDN cluster from which it receives content I Maintaining and managing these clusters becomes challenging I One in place CDNs replicate content across its clusters They don t copy every video If a client requests a video from a cluster that is not storing the video then the cluster retrieves the video and stores a copy locally while streaming the video to the client at the same time When a custer s storage becomes full it removes the videos that are not frequently requested I o Qos Quality of Service o SDN is better than the existing system because it can understand QoS o Go through Scenarios in PowerPoint o TCP Header o Port Number from srce dst o Guess the service from the port number o IP Header o src dst o could be a well known IP address 73 Voiceover IP o Voiceover IP is rea time conversational voice over the Internet 0 Timing considerations are important because audio and video conversational applications are highly delaysensitive On the other hand conversational multimedia applications are losstolerant occasional loss only causes occasional glitches in audiovideo playback and these losses can often be partially or fully concealed o Endtoend delay is the accumulation of transmission processing and queuing delays in routers propagation delays in links and end system processing delays 0 Packetjitter is the phenomenon where the time from when a packet is generated at the source until it is received at the receiver can fluctuate from packet to packet 0 To remove networkjitter the sender should prepend each chunk with a timestamp and the receiver should delay playing chunks because the received audio chunks must be long enough so that most of the packets are received before their scheduled playout times With a fixeddelay strategy the receiver attempts to play out each chunk exactly q msecs after the chunk is generated So if a chunk is timestamped at the sender at time t the receiver plays out the chunk at time tq assuming the chunk has arrived by that time Packets that arrive after their scheduled playout times are discarded and considered lost Making the playout delay large will cause most packets to make their deadlines and therefore be negligible loss however long delays can become bothersome if not not interoperable The natural way to deal with this tradeoff is to estimate the network delay and the variance of the network delay and to adjust the playout delay accordingly at the beginning of each talkspurt There s two types of loss anticipation scheme 0 Forward Error Correction FEC Idea is to add redundant information to the original packet stream For the cost of marginally increasing the transmission rate the redundant information can be used to reconstruct approximations or exact versions of some lost packets First mechanism sends a redundant encoded chunk after every n chunks The redundant chunk is obtained by exclusive ORing the n original chunks In this manner if any one packet of the group of n1 packets is lost the receiver can fully reconstruct the lost packet But if two or more packets in a group are lost the receiver cannot reconstruct the lost packets Second mechanism is to send a lowerresolution audio stream as the redundant information For example the sender might create a normal audio stream and a corresponding lowresolution lowbit rate audio stream The sender then reconstructs the nth packet by taking the nth chunk from the nominal stream and appending it to the n1st chunk from the redundant stream Therefore whenever there is non consecutive packet loss the receiver can conceal the loss by playing out the lowbit rate encoded chunk that arrives with the subsequent packet interleaving The sender resequences units of audio data before transmission so that originally adjacent units are separated by a certain distance in the transmitted stream For example units are 5msecs in length and chunks are 20msecs then the first chunk could contain 15813 the second chunk could contain units 261014 This can significantly improve the perceived quality of an audio stream It s also low overhead but it obviously increases latency A major advantage is that it does not increase the bandwidth requirements of a stream 0 Error concealment schemes attempt to produce a replacement for a lost packet that is similar to the original understand error detection and correction focus on delivery 75 Quality of Service QoS guest talk on CDN SDN a Go through Scenarios in PowerPoint o SDN is better than the existing system because it can understand QoS o Three broad approaches toward providing networklevel support for multimedia applications o Making the best of besteffort service can be applied successfully in a welldimensioned network where packet loss and excessive endtoend delay rarely occur When demand increases are forecasted the SPs deploy additional bandwidth and switching capacity to continue to ensure satisfactory delay and packetloss performance 0 Differentiated Service Perconnection QualityofService QoS Guarantees Each instance of an application explicitly reserves endtoend bandwidth and thus has a guaranteed endtoend performance A hard guarantee means the application will receive its requested quality of service with certainty A soft guarantee means the application will receive its requested QoS with high probability I The network can t guarantee that an ongoing flow in a highpriority traffic class will continue to receive the highest class of service throughout the fow s duration For example consider 2 1Pbps audio applications transmitting over a 15 Mbps link The combined rate exceeds the link capacity 0 Solution Block one of the application flows while the other is allowed to proceed using the full 1Mbps needed by the application o The only way to guarantee that a call will have the resources needed to meet its desired QoS is to explicitly allocate those resources to the call process known as resource reservation If the resources are to be reserved then the network must have a mechanism for calls to request and reserve resources a TCP Header 0 Port Number from src dst o Guess the service from the port number o IP Header o src dst o could be a well known IP address 0 81 What is network security a The following are desirable properties of secure communication 0 Confidentiality only the sender and intended receiver should be able to understand the contents of the transmitted message Message Integrity the content of the communication is not altered either maliciously or by accident Endpoint Authentication both the sender and receiver should be able to confirm the identity of the other party involved in the communication Operational Security used to counter attacks against an organization s network An intrusion detection system performs deep packet inspection alerting the network administrators about suspicious activity 82 Principles of cryptography Cryptographic techniques allow a sender to disguise data so that an intruder can gain no information from the intercepted data Plaintext or cleartext is a message in it s original form Ciphertext is an encrypted message A key is a string of numbers or characters An encryption algorithm takes the key and the plaintext message m as input and produces ciphertext as output Km The decryption algorithm takes the ciphertext and the receivers key as input and produces the original plaintext as output Symmetric Key Cryptography Client and Server keys are identical and are secret O Ciphertextonly attack the intruder may have access only to the intercepted ciphertext with no certain information about the contents of the plaintext message Knownplaintext attack when an intruder knows some of the plaintext ciphertext pairings For example if Trudy had recorded all of the ciphertext transmission and then found Bob s own decrypted version of one of the transmissions scribbled on a piece of paper Chosenplaintext attack the intruder is able to choose the plaintext message and obtain its corresponding ciphertext form There are two broad classes of symmetric encryption techniques Stream ciphers and Block ciphers but we only focus on block ciphers In a block cipher the message to be encrypted is processed in blocks of k bits For example if k64 then the message is broken into 64bit blocks and each block is encrypted independently To encode a block the cipher uses a onetoone mapping to map the kbit block of cleartext to a kbit block of ciphertext This requires a table mapping each block which becomes infeasible with large number kbit value Instead block ciphers typically use functions that simulate randomly permuted tables The function breaks 64bit block into each 8bit chunks where each chunk is processed by an 8bit to 8bit table Public Key Encryption a pair of keys is used One of the keys is known to both client and server indeed the whole world The other key is known only by client or server not both 0 Bob has two keys a public key KBthat is available to everyone and a private key KB that is known only to Bob In order to communicate with Bob Alice first fetches Bobs public key Alice then encrypts her message m to Bob using Bos public key KBm Bob receives Alices encrypted message and uses his private key to decrypt Alices encrypted message KBKBm m In this manner Alice can use Bobs public key to send a secret message to Bob without either of them having to distribute any secret keys I Concern Since Bobs encryption key is public anyone can send an encrypted message to Bob including Alice or someone claiming to be Alice In the case of a single shared secret key the fact that the sender knows the secret key implicitly identifies the sender to the receiver In the case of public key cryptography this is no longer the case since anyone can send an encrypted message to Bob using Bobs publicly available key 83 Message integrity and Authentication c To authenticate a message Bob needs to verify O O The message indeed originated from Alice the message was not tampered with on its way to Bob 0 A hash function takes as an input m and computes a fixedsize string Hm known as a hash A cryptographic hash function is required to have the additional property It is computationally infeasible to find any two different messages x and y such that Hx Hy This property means that an intruder cannot forge the contents of another message that has the same has value as the original message 0 The shared secret is called the authentication key Using this shared secret message integrity can be performed as follows 0 Alice creates message m concatenates s with m to create ms and calculates the Hash Hms Hms is called the message authentication code MAC Alice then appends the MAC to the message m creating an extended message m Hms and sends the extended message to Bob Bob receives an extended message mh and knowing s calculates the MAC Hms If Hmsh Bob concludes that everything is fine Problem How do we distribute the shared authentication key to the communicating en es o A digital signature is cryptographic technique for achieving these goals in a digital world Should be done in a way that is verifiable and non forgeable 0 Steps to sending a digitally signed message I Bob puts his original message through a hash function He then digitally signs the resulting hash with his private key The original message in cleartext along with the digitally signed message digest digital signature is then sent to Alice o Steps to verify a signed message I Alice applies the sender s public key to the message to obtain a hash result Aice also applies the hash function to the cleartext message to obtain a second hash result If the two hashes match then Alice can be sure about the integrity and author of the message 0 An important application of digital signatures is public key certification that is certifying that a public key belongs to a specific entity Binding a public key to a particular entity is typically done by a Certification Authority CA whose job is to validate identities and issues certificates A CA has the following roles o Verify that an entity a person a router and so on is who it says it is o After step 1 create a certificate that binds the public key of the entity to the identity 0 the certificate contains the public key and globally unique identifying information about the owner of the public key 85 Securing TCP connections SSL LOOK AT POWERPOINT This section did not have a nounce Client and Sewer gt Client Hellow Nc lt Sener Hello NS centPubS gt PubSSecret nc ns secret gt K 3 way handshake verified Every communication from Client and Sewer will use K o Alice used a symmetric session key Ks to send a secret email to Bob o Alice select a random symmetric session key Ks I She encrypts her message m with the symmetric key I Encrypts the symmetric key with Bob s public key Kb I Concatenates the encrypted message and the encrypted symmetric key to form a package o Bob receives the package and uses his private key Kb to obtain the symmetric key Ks I He uses the symmetric key Ks to decrypt the message m 0 Using hash functions and digital signatures to provide sender authentication and message integrity o Alice applies a hash function H to her message m to obtain a message digest I signs the result of the hash function with her private key KA to create a digital signature I concatenates the original unencrypted message with the signatures to create a package I sends the package to bobs email address 0 Bob receives the package and applies Aice s public key Ka to the signed message digest I Compare the result of this operation with his own hash H of the message o If the results are the same Bob can be pretty confident that the message came from Alice and is unaltered 86 7 VPN guest talk on May 5 Slides are in canvas Guest talk was about creating the illusion that the school campus downtown is connected to the main campus network Creates confidentiality and authentication between the branches network Not required if access is requested from within Your computer would be using a special software that authenticates you and PSecs you into the network 0 SSL is used to provide security to transactions that take place over HTTP It consists of a type field version field length field data field and MAC field First 3 are not encrypted The type field indicates whether the record is handshake message or a message that contains application data o Actual SSL protocol o SSL Handshake I The client sends a list of cryptographic algorithms it supports along with a client nonce I From the list the server chooses a symmetric algorithm for example AES a public key algorithm and a MAC algorithm It sends back to the client its choices as well as a certificate and a server nonce I The client verifies the certificate extracts the servers public key generates a PreMaster Secret PMS encrypts the PMS with the servers public key and sends the encrypted PMS to the server I Using the same key derivation function as specified b y the SSL standard the client and server independently compute the Master Secret MS from the PMS and nonces The MS is then sliced up to generate the two encryption and two MAC keys Furthermore when the chosen symmetric cipher employs CBC than two Initialization Vectors IVs one for each side of the connection are also obtained from the MS Henceforth all messages sent between client and server are encrypted and authenticated with the MAC I The client sends a MAC of all the handshake messages I The server sends a MAC of all handshake messages 0 lPsec provides security at the network layer It secures IP datagrams between any two network ayer entities including hosts and routers Before sending Psec datagrams from source entity to destination entity the source and destination entities create a network ayer logical connection This logical connection is called a security association SA An SA is a simplex logical connection that is it is unidirectional from source to destination If both entities want to send secure datagrams to each other then two SAs need to be established one in each direction 88 9 Firewall and IDS PowerPoint Network Security 8118 Stateless makes the decision from one packet Stateful makes the decisions from previous packets can be used to know if you received an ACK from a computer that you didn t expect an ACK from Application gateway built specifically for each application works like a proxy cache that goes through all the files that come in and out can be used to check if an employee is sending company secrets through google doc Do Exercises 2223 from chapter 4 o ACL notjust for firewalls Anything that requires authorization uses ACL o Firewalls can be classified in 3 categories traditional packet filters stateful filters and application gateways o Traditional Packet Filters All traffic leaving and entering the internal network passes through the gateway router connecting its internal network to its ISP and it is at this router where packet filtering occurs A packet filter examines each datagram in isolation IDS determining whether the datagram should be allowed to parr or should be dropped based on administratorspecific rules Filtering decisions are made on each packet in isolation Stateful Packet Filters track TCP connections and use this knowledge to make filtering decisions Application Gateway look beyond the IPTCPUDP headers and make policy decisions based on application data An application gateway is an applicationspecific server through which all application data inbound and outbound must pass Multiple application gateways can run on the same host but each gateway is a separate server with its own process I They don t come without their disadvantages o a different application gateway is needed for each application o there is a performance penalty to be paid since all data will be relayed via the gateway o the client software must know how to contact the gateway when the user makes a request and must know how to tell the application gateway what external server to connect to Deep Packet Inspection look beyond the header fields and into the actual application data that the packets carry Application gateways often do deep packet inspection A device that generates alerts when it observes a potentially malicious traffic is called an intrusion detection system IDS A device that filters out suspicious traffic is called an intrusion prevention system IPS An IDS can be used to detect a wide range of attacks including network mapping port scans TCP stack scan DoS bandwidth fooding attacks etc When multiple sensors are deployed they typically work in concert sending information about suspicious traffic activity V xquot7mur Problem VPIBME 2 H Pmblem Pmblvem 4 Pmmem o Proble l IL I lFe4 n f jg 3 1 3 r Nn lapmpq um 5 P J 0 7 W Fl Iv r fl rl um I1quot i M ji amt rfw InfI d P ii E ii 55 F A 1 L Prtjlem 1 HTTP A10 pluinte Explain how G eri1quothe EDIIEI SiStE39 t eenneetiene 3 G 6 mth pere tent CUEI1E1CtIDI1S are di eAren39te and here this di erenee a eete the reepeeneee e r I I awe 39 i E 6 39 39 J 39 r g 1 I V 0 P In 211 ID hmj H H e 395quot39 quotw39 E If g W1 J3939I lvi K eni fi r J an J if 39 I 2 3 V 39 i V 3 2 RE II39 ft quot d E IFlr1quotL 0 39 r 1 if 1 1 0 P quot 4 397 e P 39 he ifieweeE39 H ff 3 J j 5 n eL e 5 U 39 1rn Cr E r39I39quot u 3 a ffquot E4 ii 139 5 0 If fig32 4 r quot5 iquotquot quot39E H 3 39g39aquot mJf iT11rvquot Q nquotu a393 F 39e e M39 T ff 0 gejrge I a r E b1i 1 e394L 39caj39f39i ara Jquot P bk F E 4 e I 1 ampquot3e 4 aquot 11r E J p ar 5 U P I fj egte17f l YT 393 j fr g E751 P 5 I I t39 ampun 5 er gr f 13 55quot n1M393 Problem 2 s addreeslee 15 pnint5 E Eb p iiLi lg j m u E 7 391quot F Lav pc V i 5 peiete One eubne1 is identi ed 25 2 23 1Q 2e3 Is 22 31e1e33 part ef this eubnei F I lE 111eiJ39squotIa11r e 39 Lmww quotM an 351 L153 95 0 ll39 7 FquotLv 23 3915 P 39gquot Ie g 5 s r e s394q rm pb 39H5 P H H I 9 pr L J EH 39J Sa5 J7337 5 W quotquot quotquot I ag J Efelih n 0 0 C P T p l39 N E 1 U 0 39 Z a P p p p P 2 5 d 0 A F A ii peime A quotrenter is e geteeag 10 three subnetwerke 2 231QU 23 223I1390f23 V and 22e3e12B j23 In ether weeds this ereuteer ie the eel wegr tn et tn H1338 three W eu uewrerk5 5ggegee etheeee At eubnetweee for this renter inate ene eddriees Shaw Pp V51g39 fe iif39 T i 5 yy stepe 12 quot 1 p jig 2 at 5 see 12 iquotfS f Ha P 1g I requot 39quot39e39 H na 3 Jr In p is39 2 ii gt 391 e p6 r w1 3 as I T T V r if 0 p I L gt 7 H nmg q pill F r 34quot P quot1 quothiquot 3 I m quotl l 5 C3 1H 397J55391i39l1 l11E nuintH Wlmt IEITEE lhr 1rcsrs nmi m39ms nf mri lnr tni mn E 0 1 J 1 MIA t W11I39 1 nlri Ilf39t E1I fELSE ijilvf3l C39JllE I H1iHI urIu1raH Iimlxain whnn r1 iIx mi MquotrI3EIas 139h is lrI lm39 um WIm mgatjwrknHHi tici approach is lmtinr f 9 53 A i e um r4 N mVIxl39 F V 3 4 quotquot1 TH E V I 7 E quotI 39 7 n a Hi 39j quot V J 1 Pt rt ILlJ tiI EA L1 Pi E V7 I 1 1 1 IE iE J in 39 Z p I 1 w u 0L I 1 1 7 t K p I E J 1 e 2 P J k Pg Ii 3 r iv an 9 J 1 F X 11quot F N 539 quot3 1 4 1 P 39 hi 39nL1Iare 554 39r 3939I39i3943939r aquot39439 P 1J 5 w IVEquotV quot39g 1 r I39 I H I 1 F 1 AA G f hfn quot39 quot a39E 1391quot J i u39lquot E AA 5 dfr L rrarr EJ39V39IIquotJ quot 0 NJ lI l V 3 rf1 l ydlti K 39g39 r irzilgi xivd Iu 39 quotquotquot39quotquotquotnn P 8 jv 6 1 ff E V 39 gtI V Ti I gt p f 8 1quot F gr I J IL 5quotquot39 4 g 139 g 5 Ex H S Li Nquot E7 I I it 4 Ir C K quotquot quotF F 39 Z V W x1s39391 ltI 7 H I 394Z i I 1 A W V D in Ftquot V H W1 1 JquotL139 3939T 39J J T i 1 W 0 as p Ex 0V 54 J39quot W 5 lt I1quot quot39 pI pP 39J urwquotrquot iv 5 5 quotquot w gr lt4 4 t Ina quot 39 E rmquot ff T T i 39 I HF quotI1 39 Vquot a39 I n s A K was PE 91 M 0L g3939ampquot il397 iiquot 39 3 39 7 M N 5 Ce 5 5 E 1 f quot quot Hquot p P p 1 p J P K p F o 21 Socket 0 Process sends receives messages to from o Analogous to door 0 TCP vs UDP 0 TCP o UDP o BOTH I I sending process shove message out door sending process relies on transport infrastructure on other side of door to deliver message to socket at receiving process reliable transport between sending and receiving flow control sender won39t ovenvhelm receiver congestion control throttle sender when network overloaded does not provide timing minimum throughput guarantee security connectionoriented setup required between client and server processes SSL provides encrypted TCP connection data integrity endpoint authentication unreliable data transfer between sending and receiving process does not provide reliability flow control congestion control timing throughput guarantee security or connection setup no encryption cleartext passwords sent into socket traverse internet in cleartext o 22 HTTP stateless what does it mean how it is implemented o HTTP HyperText Transfer Protocol port 80 o HTTP is said to be a stateless protocol because an HTTP server maintains no information about the clients The server sends requested files to clients without storing any state information about that client If a particular client asks for the same object twice in a period of a few seconds the server resends the object as it has completely forgotten what it did earlier o 22 HTTP Nonpersistent vs persistent in response time o Nonpersistent connections When the clientserver interaction is taking place over TCP each requestresponse made is sent over a separate TCP connection Each TCP connection is closed after the server sends the object the connection does not persist for other objects A brand new connection must be established and minted for each requests object For each of these connections TCP buffers must be allocated and TCP variables must be kept in both the client and server This can place a significant burden on the Web server which may be serving requests from hundreds of different clients simultaneously With HTTP at most one object sent over TCP connection connection closed downloading multiple objects required multiple connection 0 Persistent connections When the clientserver interaction is taking place over TCP all requests and their corresponding responses are sent over the same TCP connection The server leaves the TCP connection open after sending a response Subsequent requests and responses between the same client and server can be sent over the same connection I These requests for objects can be made backtoback without waiting for replies to pending requests I With HTTP multiple objects can be sent over single TCP connection between client server o 22 Web caching pros and cons how it is implemented 0 A web cache also called a proxy server is a network entity that satisfies HTTP requests on the behalf of an origin web server The web cache has it s own disk storage and keeps copies of recently requested objects in this storage 0 A cache is both a server and a client at the same time When it receives requests from a client and sends responses to sender it is a server When it sends requests to server and receives responses from an origin server it is a client 0 Pros I It can substantially reduce the response time for a client requests particularly if the bottleneck bandwidth the client and the origin server o SKIPPING 24 o 25 DNS how to resolve name recursively and nonrecursively 0 DNS Domain Name System I A distributed database implemented in a hierarchy of DNS servers I An applicationlayer protocol that allows hosts to query the distributed database I Once any name server learns mapping it caches the mapping Cache entries timeout disappear after some time TTL 0 DNS Process The same user machine runs the client side of the DNS application The browser extracts the hostname wwwsomeschooedu from the URL and parses the hostname to the client side of the DNS application The DNS client sends a query containing the hostname to a DNS server The DNS client eventually receives a reply which includes the IP address for the hostname I Once the browser receives the IP address from DNS it can initiate a TCP connection to the HTTP server process located at port 80 at that IP address 0 Recursively and NonRecursively I The example shown in Figure 221 makes use of both recursive queries and iterative queries The query sent from cispoyedu to dnspoyedu is a recursive query since the query asks dnspoyedu to obtain the mapping on its behalf I The subsequent 3 queries are iterative since all of the replies are directly returned to dnspoyedu I The query from the requesting host to the local DNS server is recursive and the remaining queries are iterative I Recursive query puts burden of name resolution on contacted server Heavy load at upper levels of hierarchy o Iterated Query I Contacted server replies with the name of server to contact I don t know this name but ask this server 0 OTHER I All DNS query and reply messages are sent within UDP datagrams to port 53 o 24 DNS authoritative vs nonauthoritive servers 0 Authoritative DNS servers I Every organization with publicly accessible hosts on the Internet must provide publicly accessible DNS records that map the names of those hosts to IP addresses An organization s authoritative DNS server houses these DNS records An organization can choose to implement its own authoritative DNS server to hold these records alternatively the organization can pay to have these records stored in an authoritative DNS server of some service provider Most universities and large companies implement and maintain their own primary and secondary backup authoritative DNS server Organization own DNS servers providing authoritative hostname to IP mappings for organization s named hosts Can be maintained by organization or service provider o 24 NAT IP address netmask network ID host ID o IP address Consist of four bytes o SKIPPING 253 31 o 27 Socket programming using UDP and TCP 0 Socket is the door between application process and endtoendtransport protocol 0 Application example Client reads a line of characters data from its keyboard and sends the data to the server The server receives the data and converts characters to uppercase The server sends the modified data to the client The client receives the modified data and displays the line on its screen o 32 connectionless vs connectionoriented o Connectionless use UDP The client side of the application lets the transport layer automatically and transparently assign the port number whereas the server side of the application assigns a specific port number UDP socket is identified by a twotuple consisting of a destination IP address and a destination port Two arriving UDP segments have different source IP addresses andor source port numbers but have the same destination IP address and destination port number then the two segments will be directed to the same destination process via the same destination socket o ConnectionOriented use TCP TCP socket is identified by a fourtuple source IP address source port number destination IP address destination port number Use all 4 values to direct demultiplex the segment to the appropriate socket Two arriving TCP segments with different source IP addresses or source port numbers will be directed to two different sockets o 32 MultiplexingDemultiplexing o Demultiplexing The job of delivering the data in a transportlayer segment to the correct socket Host receives IP datagrams o each datagram has source IP address destination IP address o each datagram carries one transportlayer segment a each segment has source destination port Host uses IP address amp port numbers to direct segment to appropriate socket o Multiplexing O I The job of gathering data chunks at the source host from different sockets encapsulating each data chunk with transport header information that will later be used in demultiplexing to create segments and passing the segments to the network layer Analogy I When Bill receives a batch of mail from the mail carrier he performs a demultiplexing operation by observing to whom the letters are addressed and then hand delivering the mail to his brothers and sisters Ann performs a multiplexing operation when she collects letter from her brothers and sisters and gives the collected mail to the mail person o 33 why is there UDP 0 It does just about as little as a transport protocol can do Aside from the multiplexingdemultiplexing function and some light error checking it adds nothing to IP The application using UDP is almost directly talking with IP There is no handshaking between sending and receiving transportlayer entities before sending a segment For this reason UDP is said to be connectionless Many application are better suited for UDP for the following reasons I Finer applicationlevel control over what data is sent and when I No connection establishment I No connection state I Small packet header overhead No connection establishment which can add delay simple no connection state at sender receiver small header size no congestion control UPD can blast away as fast as desued o 33 checksum how to compute what kinds of errors can be detected 0 O The checksum is used to determine whether bits within the UDP segment have been altered as it moved from source to destination UDP at the sender side performs the 1s complement of the sum of all the 16bit words in the segment with any overflow encountered during the sum being wrapped around This result is put in the checksum field of the UDP segment The 1s complement is obtained by converting all the Os to 1s and converting all the 1s to Os Thus the complement of the sum 0100101011000010 is 1011010100111101 which becomes the checksum If no errors are introduced into the packet then clearly the sum at the receiver will be 1111111111111111 If one of the bits is 0 then we know that errors have been introduced into the packet Although UDP provides error checking it does not do anything to recover from an error Some implementations of UPD simply discard the damaged segment others pass the damaged segment to the application with a warning o 34 how to tolerate data corruption 0 Use a messagedictation protocol that uses both positive acknowledgements OK and negative acknowledgements Please repeat that These control messages allow the receiver to let the sender know what has been received correctly and what has been received in error and thus requires repeating In a computer networking setting reliable data transfer protocols based on such retransmission are known as ARQ Automatic Repeat reQuest protocols I Three additional protocol capabilities are required in ARQ protocols to handle the presence of bit errors o Error detection o Receiver feedback o Retransmission 34 how to tolerate ACK corruption 0 The difficulty here is that if an ACK or NAK is corrupted the sender has no way of knowing whether or not the receiver has correctly received the last piece of transmitted data Consider the 3 possibilities for handling corrupted ACKs or NAKs I If the speaker didn t understand the OK or Please repeat that response from the receiver the speaker would probably ask what did you say but what if the What did you say is corruptedThe receiver would probably respond with What did you say and then of course that response might be garbled Clearly heading down a difficult path I Add enough checksum bits to allow the sender not only to detect but also to recover from bit errors I The sender simply resends the current data packet when it receives a garbled ACK or NAK packet This approaches however introduces duplicate packets into the sendertoreceiver channel 34 how to tolerate outoforder packets O A sequence number field is added to the data packet to determine whether or not the received packet is a retransmission When an outoforder packet is received the receiver sends a positive acknowledgment for the packet it has received When a corrupted packet is received the receiver sends a negative acknowledgement 34 GoBackN O O The sender is allowed to transmit multiple packets when available without waiting for an acknowledgment but is constrained to have no more than some maximum allowed number N the window size of unacknowledged packets in the pipeline The name is derive from the sender s behavior in the presence of lost or overly delayed packets Sender can have up to N unacked packets in pipeline receiver only sends comulative ack doesn t ack packet if there s a gap Sender has timer for oldest unacked packet when timer expires retransmit all unacked packets Stopandwait operation I Sender transmits multiple packets receiver acknowledges the last one Pipeline operation I Sender transmits multiple packets receiver acknowledges every packet received 34 Selective Repeat 0 Protocol that avoids unnecessary retransmission by having the sender retransmit only those packets that it suspects were received in error that is were lost or corrupted at the receiver This individual as needed retransmission will require that the receiver individually acknowledge correctly received packets Example every time a word was garbled the surrounding 1 000 words had to be repeated The dictation would be slowed by all of the reiterated words Sender can have up to N unacked packets in pipeline Receiver sends individual ack for each packet Buffers each packet as needed for eventual inorder delivery to upper layer Sender maintains timer for each unacked packet when timer expires retransmit only that unacked packet O Sender window N consecutive seq s limit seq s of sent unacked packets o 34 Nat IP address net mask network ID a 35 sequence numbers and acknowledgments in the real world 0 The 32bit sequence number field and the 32bit acknowledgement number field are used by the TCP sender and receiver in implementing a reliable data transfer service TCP views data as unstructured but ordered stream of bytes TCP s use of sequence numbers reflects this view in that sequence numbers are over the stream of transmitted bytes and not over the series of transmitted segments The sequence number for a segment is therefore the bytestream number of the first byte in the segment Suppose that a process in Host A wants to send a stream of data to a process in Host B over a TCP connection The TCP in Host A will implicitly number each byte in the data stream Suppose that the data stream consists of 500000 bytes that the MSS Maximum Segment Size is 1 000 bytes and that the first byte of the data stream is numbered 0 TCP constructs 500 segments out of the data stream The first segment gets assigned sequence number 0 the second segment gets assigned sequence number 1000 the third segments gets assigned sequence number 2000 and so on Each sequence number is inserted in the sequence number field in the header of the appropriate TCP segment Each of the segments that arrive from Host B has a sequence number for the data flowing B to A The acknowledgment number that Host A puts in its segment is the sequence huber of the next byte Host A is expecting from Host B Suppose that Host A has received all bytes numbered 0 through 535 from B and suppose that is is about to send a segment to Host B Host A is waiting for bytes 536 and all the subsequent bytes in Host B s data stream So Host A puts 536 in the acknowledgment number field of the segment it sends to B o 35 how to decide timeout value interval 0 Clearly it should be larger than the connection s roundtrip time RTT that is the time from when a segment is sent until it is acknowledged In other words time for a small packet to travel from client to server and back Too short premature timeout unnecessary retransmission Too long slow reaction to segment loss Read How to Estimate RTT first Clearly it should be greater than or equal to EstimatedRTT or unnecessary retransmission would be sent but the timeout interval should not be too much larger than EstimatedRTT othenvise when segment is lost TCP would not quickly retransmit the segment leading to large data transfer delays Timeoutlnterval EstimatedRTT 4 DevRTT An initial Timeoutlnterval value of 1 is recommended Also when a timeout occurs the value of Timeoutlnterval is doubled to avoid a premature timeout occurring for a subsequent segment that will soon be acknowledged As soon as a segment is received and EstimatedRTT is updated the Timeoutlnterval is again computed using the formula above o 35 how to estimate RTT O The sample RTT denoted SampeRTT for a segment is the amount of time between when the segment is sent that is passed to IP and when an acknowledgment for the segment is received Instead of measuring a SampeRTT for every transmitted segment most TCP implementations take only one SampeRTT measurement at a time That is at any point in time the SampeRTT is being estimated for only one of the transmitted but currently unacknowledged segments leading to a new value of SampeRTT approximately once every RTT The SampeRTT values will fluctuate from segment to segment due to congestion in the routes and to the varying load on the end system and because of this fluctuation any given SimpeRTT value may be atypical In order to estimate RTT it is therefore natural to take some sort of average of the SampeRTT values TCP maintains an average calle EstimatedRTT of the SampeRTT values Upon obtaining a new SampeRTT TCP updated EstimatedRTT according to the following formula EstimatedRTT 1 alpha EstimatedRTT alpha SampeRTT The recommended value for alpha is 0125 that is 18 In statistics such an average is called an exponential weighted moving average EWMA In addition to having an estimate of the RTT it is also valuable to have a measure of the variability of the RTT RFC 6298 defines the RTT variation DevRTT as an estimate of how much SampeRTT typically deviates from EstimatedRTT DevRTT 1 beta DevRTT beta SampeRTT EstimatedRTT If the SampeRTT values have little fluctuations then DevRTT will be small on the other hand if here is a lot of fluctuation DevRTT will be large The recommended value of Beta is 025 o 35 TCP handshake O O TCP is said to be connectionoriented because before one application process can begin to send data to another the two processes must first handshake with each other that is they must send some preliminary segments to each other to establish the parameters of the ensuing data transfer Threeway Handshake I Client first sends a special TCP segment I Server responds with a special TCP segment I Client responds again with a third special TCP segment I The first two segments carry no payload that is no application layer data I The third may carry a payload o Skipped 354 o 35 flow control 0 A TCP connection provides a fullduplex service If there is a TCP connection between Process A on one host and Process B on another host then application layer data can flow from Process A to Process B at the same time as application layer data flows from Process B to Process A A TCP connection is also always pointtopoint that is between a single sender and a single receiver Multicasting the transfer of data from one sender to many receivers in a single send operation is not possible with TCP The 16bit receiver window field is use for flow control It is used to indicate the number of bytes that a receiver is willing to accept Receiver control sender so sender won39t overflow receivers buffer by transmitting too much too fast Receiver advertises free buffer space by including rwnd value in TCP header of receivertosender segments Sender limits amount of unacked infight data to receivers nivnd value Guarantees receive buffer will not overflow When the TCP connection receives bytes that are correct and in sequence it places the data in the receive buffer The associated application process will read data from this buffer but not necessarily at the instant the data arrives TCP provides a flowcontrol service to its applications to eliminate the possibility of the sender overflowing the receiver s buffer Flow control is thus a speedmatching service matching the rate at which the sender is sending against the rate at which the receiving application is reading TCP provides flow control by having the sender maintain a variable called receive window Informally the receive window is used to give the sender an idea of how much free buffer space is available at the receiver Because TCP is fullduplex the sender at each side of the connection maintains a distinct receive window Skipped 356 36 37 congestion control signs of congestion o Congestion informally too many sources sending too much data too fast for network to handle They have different flow control 0 Signs of congestion I When the sending rate exceeds R outgoing link capacity 2 the average number of queued packets in the router is unbounded and the average delay between source and destination becomes infinite While operating at an aggregate throughput of near R may be ideal from a throughout standpoint it is far from ideal from a delay standpoint Large queuing delays are experienced as the packet arrival rate nears the link capacity I The sender must perform retransmission in order to compensate for dropped lost packets due to buffer overflow I Unneeded retransmission by the sender in the face of large delays may cause a router to use its link bandwidth to forward unneeded copies of a packet This happens when the sender times out prematurely and retransmits a packet that has been delayed in the queue but not yet lost In this case both the original packet and the retransmission may reach the receiver I When a packet is dropped along a path the transmission capacity that was used at each of the upstream links to forward that packet to the point at which it is dropped ends up having been wasted o Congestion Control I Endtoend congestion control 0 The network layer provides not explicit support to the transport layer for congestion control purposes The presence of congestion must be inferred by the end systems based only on observed network behavior o TCP segment loss as indicated by a timeout or triple duplicate acknowledgment is taken as an indication of network congestion and TCP decreases its window size accordingly o No explicit feedback from network Congestion inferred from endsystem observed loss delay Approach taken by TCP I Networkassisted congestion control o Routers provide explicit feedback to the sender regarding the congestion state in the network This feedback may be as simple as a single bit indicating congestion at a link Direct feedback may be sent from a network router to the sender This form of notification typically takes the form of a choke packet essentially saying I m congested o The second form of notification occurs when a router marksupdates a field in a packet flowing from sender to receiver to indicate congestion o Routers provide feedback to end systems Single bit indicating congestion Explicit rate for sender to send at o ABR Available Bit Rate I Elastic service If senders path underloaded sender should use available bandwidth If senders path congested sender throttled to minimum guaranteed rate o TCP must use endtoend congestion control rather than networkassisted congestion control since the IP layer provides no explicit feedback to the end systems regarding network congestion TCP congestioncontrol mechanism operating at the sender keeps track of an additional variable the congestion window The congestion window imposes a constraint on the rate at which a TCP sender can send traffic into the network TCP will take the arrival of previously unacknowledged segments as an indication that all is well that segments being transmitted into the network are being successfully delivered to the destination and will use acknowledgments to increase its congestion window and hence its transmission rate Note that if the acknowledgements arrive at a relatively slow rate eg if the endend path has high delay or contains a lowbandwidth link then congestion window will be increased at a relatively slow rate On the other hand if acknowledgments arrive at a high rate then the congestion window will be increased more quickly TCP is said to be selfclocking because it uses acknowledgements to trigger or clock its increase in congestion window size o Skipped 363 o 36 37 AIMD additiveincrease multiplicativedecreases O TCPs congestion control consists of linear additive increase in cwnd of 1 MSS per RTT and then halving multiplicative decreases of cwnd on a triple duplicateACK event For this reason TCP congestion control is referred to as an AIMD form of congestion control AIMD congestion control gives rise to the saw tooth behavior shown in figure 354 which also nicely illustrates our earlier intuition of TCP probing for bandwidth TCP linearly increases its congestion window size and hence its transmission rate until a triple duplicateACK event occurs It then decreases its congestion window size by a factor of 2 but then again begins increasing it linearly probing to see if there is additional available bandwidth Approach sender increases transmission rate window size probing for usable bandwidth until loss occurs Additive increase increase cwnd by 1 MSS every RTT until loss detected Multiplicative decrease cut cwnd in half after loss o 36 37 slow start 0 0 When a TCP connection begin the value of the congestion window cwnd is typically initialized to a small value of 1 MSS resulting in an initial sending rate of roughly MSSRTT The value of cwnd begins at 1 MSS and increases by 1 MSS every time a transmitted segment is first acknowledged TCP sends the first segment into the network and waits for an acknowledgment When this acknowledgment arrives the TCP sender increase the congestion window by one MSS and sends out 2 maximumsized segments This process results in a doubling of the sending rate every RTT When connection begins increase rate exponentially until first loss event initially cwnd 1 MSS double cwnd every RTT done by incrementing cwnd for every ACK received Summary Initial rate is slow but ramps up exponentially fast o Skipped371 o 41 local forwarding table 0 A router forward a packet by examining the destination IP address and then using this value to index into the router s fonvarding table The value stored in the fonvarding table entry for that IP address indicates the router s outgoing link interface to which that packet is to be fonvarded The routing algorithm determines the values that are inserted into the router s fonvarding tables o Forwarding move packets from routers input to appropriate router output 0 Routing determine route taken by packets from source to destination 0 Routing algorithm determines endtoend path through network 0 Forwarding table determines local forwarding at this router Skipped 42 Skipped 43 44 CIDR O The Internet39s address assignment strategy is known as Classless lnterdomain Routing CIDR CIDR generalize the notion of subnet addressing As with subnet addressing the 32bit IP address is divided into two parts and again has the dotteddecimal from abcdx where x indicates the number of bits in the first part of the address Before CIDR was adopted the network portions of an IP address were constrained to be 8 16 or 24bits in length an addressing scheme known as classful addressing 44 hierarchical addressing route aggregation 45 link state algorithm 0 Algorithms with global state information are often referred to as linkstate LS algorithms A global routing algorithm computes the leastcost path between a source and destination using complete global knowledge about the network That is the algorithm takes the connectivity between all nodes and all link costs as inputs In practice this is accomplished by having each node broadcast linkstate packets to all other nodes in the network with each linkstate packet containing the identities and costs of its attached links The result of the nodes broadcast is that all nodes have an identical and complete view of the network Each node can then run the LS algorithm and compute the same set of leastcost paths as every other node o 45 distance vector DV algorithm 0 0 DV is an iterative asynchronous distributed and decentralized routing algorithm because each node maintains a vector of estimates of the costs distances to all other nodes in the network No one has complete information about the costs of all network links Instead each node begins with only the knowledge of the costs of its own directly attached links It is distributed in that each node receives some information from one or more of its directly attached neighbors performs a calculation and then distributes the results of its calculation back to its neighbors It is iterative in that this process continues on until no more information is exchanged between neighbors The algorithm is asynchronous in that it does not require all of the nodes to operate in lockstep with each other Link cost change can lead to failure Add poisoned reversed to fix the problem o 45 comparison of LS and DV 0 LS I Each node talks with all other nodes via broadcast but it tells them only the costs of its directly connected links Speed Convergence ONquot2 algorithm requiring ONE messages Robustness A router could broadcast an incorrect cost for one of its attached links but an LS node is computing only its own forwarding tables other nodes are performing similar calculations for themselves This means route calculations are somewhat separated under LS providing a degree of robustness DV I Each node talks to only its directly connected neighbors but it provides its neighbors with leastcost estimates from itself to all the nodes in the network I Speed convergence Converges slowly and can have routing loops while the o 46OSPF RIP o RIP I o OSPF o Skipped 463 algorithm is converging It also suffers from the counttoinfinity problem Robustness A node can advertise incorrect leastcost paths to say or all destinations More generally we note that at each iteration a node s calculation in DV is passed on to its neighbor and then indirectly to its neighbor s neighbor on the next iteration In this sense an incorrect node calculation can be diffused through the entire network under DV A distance vector protocol that uses hop count as a cost metric That is each link has a cost of 1 RIP uses the term hop which is the number of subnets traversed along the shortest path from source to destination subnet including the destination subnet The maximum cost of a path is limited to 15 thus limiting the use of RIP to autonomous system that are fewer than 15 hops in diameter Routing updates are exchanged between neighbors approximately every 30 seconds using RIP response message The response sent by a router or host contains a list of up to 25 destination subnets within the AS as well as the sender s distance to each of those subnets Response messages are also known as RIP advertisements Running over UDP A linkstate protocol that uses flooding of linkstate information and a Dijkstra leastcost path algorithm With OSPF a router constructs a complete topological map of the entire autonomous system The router then locally runs Dijkstra s shortestpath algorithm to determine a shortestpath tree to all subnets with itself as the root node A router broadcasts routing information to all other routers in the autonomous system notjust to its neighboring routers OSPF advertisements are contained in OSPF messages that are carried directly by IP with an upperlayer protocol of 89 for OSPF Security Exchanges between OSPF routers can be authenticated Multiple samecost paths When multiple paths to a destination have the same cost OSPF allows multiple paths to be used Integrated support for unicast and multicast routing Support for hierarchy within a single routing domain o 52 parity checking 2D bit parity o Parity bit In an even parity scheme the sender simply includes one additional bit and chooses its value such that the total number of 1s is the d1 bits is even For odd parity schemes the parity bit value is chosen such that there is an odd number of 1s Receiver operation is also simple with a single parity bit The receiver need only count the number of 1s in the received d1 bits If an odd number of 1valued bits are found with an even parity scheme the receiver knows that at least one bit error has occured More precisely it knows that some odd number of bit errors have occurred Under burst error conditions the probability of undetected errors in a frame protected by singlebit parity can approach 50 percent 0 2D bit parity I The d bits in D are divided into i rows andj columns A parity value is computed for each row and for each column The resulting ij1 parity bits comprise the linklayer frame s errordetection bits I With this 2D parity scheme the parity of both the column and the row containing the flipped bit will be in error The receiver can thus not only detect the fact that a single bit error has occured but can use the column and row indices of the column and row with parity errors to actually identify the bit that was corrupted and correct the error I 2D parity can also detect but not correct any combination of two errors in a packet The ability of the receiver to both detect and correct errors is known as forward error correction FEC Problem 1 HTTP ID p0imts 39IEixp h1m huw Hh39TquotI iEquot39 with mmpereietent mn1h1eeLiltme and HTTP witll pereietem em1m39etin11e are diH nquot391 t lIl mull lhmw lluis 1Ii i f fquotl M I I ehfi39eeIe the response time Anshwer39 NonAper539mLem oz39e neiemiMaetinrtnquot l39l tlIiI t mm vnmfwtequotl1iu1hn wr nl1jM1 whihz ptemi31hent fj I1I1BChtiZI1I1S reuse the same mnnevtsinn Fm nllnllgiple ll1mjtquotquot iH 39l hia 221M twl the NHpunet Lime due to the TCP l1a11dshhakeh I11 nnn pel39sieimL ml111v equottiume 39lquotilquot l lllihquotl mk Llmp39pena per object thus 1 exthre RTT per 0bjeet is mitieti tn the wlmjevt ti39atmaifeir tiII391tf9 In p 2r eietent connecti0r1s TCP llezldslmefke lmphpenrs vemh tZII39lI t 39 l m39 hnhnn11r njet39Ie quotthus 1 e2Lire H39lquot T is amortized over Inumple objecet tmllsfer time I11 uIl1er w39u139t39ls jpersisl e11t m11e1ectihu11e show average response tahne per 0lJj E39L h wlltm 1 pm ltis39tet1t l l1lll1t Li0l1 is elmeeJ by muitiple object transfeer Problem 2 IP addresses 15 points i 5 points One eulmet is idee11ti eedi es lEJ139 3 is h3923933h I ll33 part of Lhis subueet Explain yutlr answer Answer Noi IP addresses in 22v3el Jl1 733 enhnet111115tstn1I with 11011M1 UIUUUD1UDU U100 22311033 is 11011111IUU UlUUUl UUUIUllJUUlU39DUl so it does u039139L1 hlil llg In other words 223iL92 3 subllet hiI1E V1l l S 22 Ble8h K nlemm aJny nugmher hetween l 254 22819x addressee but met 22339LleUx ii ID points A router is e geteway to Lltree sul3I1etwe1quotke 223h1 JU23 223l1U023 am1 2 23e120h23 In other ewerzise this router is the only way to gel to these three su39bnetworks Aggregate these three subhm1elwm ks for this rmumeer into one 39 ddI39EESquoti Show your steps Answer 223i1903923 subneth 11011111UUU 0UlLUileUD 2quot2311e h2 3 subnet 110111110UUU0Jl DJUhl l 223l20 23 subnet 1101111lhODl00DDlhUO39Dl01D So the hznngest common pre is 110111110000DDDh1DOU ie 2 231019 Problem 3 UDP 15 phoints What are the bene ts of UDP ever TCP Answer UDP does not add the extra RTT for l1anClShampke UDP does not require Senderreceiver to I118iI1lai11 the state of the connection so less overhead UDP does not re39trarmsmit packets even when they are corrupted or haste so is beetter for thime een3itive a pphlhati0nsh Problem 4 Reliable Data Treansfere 15 points RDT 20 above has a fatal aw Demonshthramte the aw with an exemple Answer If there is a AACKNAK eorrtlprtionh then the receiver will accept duplicate quotpackets If there is a ACKNAK 1053 then the sender will wait fcrreveer if there is e pache 1055 then both sender andh quotreceiver will wait l turever rdt20 FSM is 39 eci cation rdlgendtriataj sndpkt make pIci data ehecksiurm aLEiWLm ud tsenad snpkt T V i rdIrcv rcvpIin 88 WEN sNAKrCfpkU rd hrm i39FW0kl 311 a39Lf39quot quot i uid1siend snid4ipkt eerrxemA a eve T udlm eend 39N M in rdtirciwfrcvpk1 ampamp isACKrcvpIltl A sender rrdIFcvre pk ea insetceimi e39rn pexi remeenezsmrame delrveri date39da1e 1 iud1sendACK emeea Es Problem 5 RDT 30 20 points Fix RDT 20 abeve so tthet it heaimirries 1hr ame Problem 4 Answer If the answer to Problem 4 was ACK quot CDE1 11r3 ii 1i arid 3 sa qizwnwe number U and 1 so that the receiver ea11 teli the dupilieetiers If the a3SI391S IDIquot E T In iquot m fwTir H ammi ACKI er packet less then add timeout to the rsenuder Problem 6 Congestions 15 poir1ts Vi i1at the pres ancl mars ref emi39roerni ears2i gestien control and networkessiieted eongestioin control Ezcplain when ende1e mi agmmwm39i is better and when lE1EtWD k 5SiStEd appreeeh is better Answ er Enci teend Congestion Control is cheaper beceuee it does mart aiii my i sf392 Em to the netwoark for congestioncer1lrol iPeckie39t lose and delequot nmiiimring is d39WTf39 1 47W 3 existing date and ACK packets However the COI1gtiDI39l detseetiam it amt1 72mrm on iindireeti inforInetio n so it may not be accurate Nietworkei td mngrzri Jan weruZ more expieinsive b eceuse it requires network entities sucuh as routers to aiioea139e 2reww mt n1onite139ing and reporting on the neitiwork status Hewever the eemgesLin1i iiemr Irm pi imr at the routers whielh experience congestion see it is mr39urete Netm ezquotk raesi imi cnrim1 ime control provides more negirained control on congestion ceiirm11 ami niay exam n39 3nsiywei before it happens by eieriding warning signs to the eendere Emi 1oend ezmvigrextixma a riuI139aiE does not provide as detailed and eccuratei iI1fGITI39l39llampti0l1 on the rmner em h u nus e39a ii5e 1 from unnecessary beekeo or only beckeff after congeeticm lmppene in zwi mi 39 39 fquot39lquot quot3ZLi 23 me 39T39I jquotl39P tu1eVI Hw T A El i X Ezxm alt P U T i RL U EH6 dtutas p mkcL ffumlx L1 It rmtii3r mg hM sqL p H yV H O U L 39T a 39FAIa V iE tMl1 3111152 as J1 ni C K H pi A5 When theV data E3 tik tl ggaissj P S L hm T1 FjE l Eii wi O P 3 0 M bR 0 M T P P O p 0 S Aquot uL Q N P R LQ 0FJ N pM N lR f39l1E l139C iE 1mmber Eu hm time puK imuvwj 1 mm f mg D a B dB O Q 0 Q M pP p K T O MP M N N 2L M wEhen N eiDit dam K at1 EaL VL km 1ewivear qr ijiammu u ms P P P P A a 39 quotaz Socket Programming Assignment 4 HTTP Web Proxy Server In this lab you will learn how web proxy servers work and one of their basic functionalities caching Your task is to develop a small web proxy server which is able to cache web pages It is a very simple proxy server which only understands simple GETrequests but is able to handle all kinds of objects not just HTML pages but also images Generally when the client makes a request the request is sent to the web server The web server then processes the request and sends back a response message to the requesting client In order to improve the performance we create a proxy server between the client and the web server Now both the request message sent by the client and the response message delivered by the web server pass through the proxy server In other words the client requests the objects via the proxy server The proxy server will forward the client s request to the web server The web server will then generate a response message and deliver it to the proxy server which in turn sends it to the client Request Request Client 39 Proxy A 39 Web Server J Server Response Response Code Below you will find the skeleton code for the client You are to complete the skeleton code The places where you need to fill in code are marked with Fill in start and Fill in end Each place may require one or more lines of code Running the Proxy Server Run the proxy server program using your command prompt and then request a web page from your browser Direct the requests to the proxy server using your IP address and port number For e g httplocalhost8888wwwgooglecom To use the proxy server with browser and proxy on separate computers you will need the IP address on which your proxy server is running In this case while running the proxy you will have to replace the localhost with the IP address of the computer where the proxy server is running Also note the port number used You will replace the port number used here 8888 with the port number you have used in your server code at which your proxy server is listening Configuring your Browser You can also directly configure your web browser to use your proxy This depends on your browser In Internet Explorer you can set the proxy in Tools gt Internet Options gt Connections tab gt LAN Settings In Netscape and derived browsers such as Mozilla you can set the proxy in Tools gt Options gt Advanced tab gt Network tab gt Connection Settings In both cases you need to give the address of the proxy and the port number that you gave when you ran the proxy server You should be able to run the proxy and the browser on the same computer without any problem With this approach to get a web page using the proxy server you simply provide the URL of the page you want For e g httpwWwgooglecom What to Hand in You will hand in the complete proxy server code and screenshots at the client side verifying that you indeed get the web page via the proxy server Skeleton Python Code for the Proxy Server from socket import import sys if lensysargv lt 1 print Usage quotpython ProxyServerpy serveripquotnserverip It is the IP Address Of Proxy Server sysexit2 Create a server socket bind it to a port and start listening tcpSerSock socketAFINET SOCKSTREAM Fill in start Fill in end while 1 Strat receiving data from the client print Ready to serve tcpCliSock addr tcpSerSockaccept print Received a connection from addr message Fill in start Fill in end print message Extract the filename from the given message print messagesplitl filename messagesplitlpartitionquotquot2 print filename fileExist quotfalsequot filetouse quotquot filename print filetouse try Check wether the file exist in the cache f openfiletousel quotrquot outputdata freadlines fileExist quottruequot Proxyserver finds a cache hit and generates a response message tcpCliSocksendquotHTTP10 200 OKrnquot tcpCliSocksendquotContent Typetexthtmlrnquot Fill in start Fill in end print Read from cache Error handling for file not found in cache except IOError if fileExist quotfalsequot Create a socket on the proxyserver c Fill in start Fill in end hostn filenamereplacequotwwwquotquotquotl print hostn try Connect to the socket to port 80 Fill in start Fill in end Create a temporary file on this socket and ask port 80 for the file requested by the client fileobj cmakefile39r39 O fileobjwritequotGET quotquothttpquot filename quot HTTPlOnnquot Read the response into buffer Fill in start Fill in end Create a new file in the cache for the requested file Also send the response in the buffer to client socket and the corresponding file in the cache tmpFile openquotquot filenamequotwbquot Fill in start Fill in end except print quotIllegal requestquot else HTTP response message for file not found Fill in start Fill in end Close the client and the server sockets tcpCliSockclose Fill in start Fill in end Optional Exercises 1 Currently the proxy server does no error handling This can be a problem especially when the client requests an object which is not available since the quot404 Not foundquot response usually has no response body and the proxy assumes there is a body and tries to read it The simple proxy server supports only HTTP GET method Add support for POST by including the request body sent in the POSTrequest Caching A typical proxy server will cache the web pages each time the client makes a particular request for the first time The basic functionality of caching works as follows When the proxy gets a request it checks if the requested object is cached and if yes it returns the object from the cache without contacting the server If the object is not cached the proxy retrieves the object from the server returns it to the client and caches a copy for future requests In practice the proxy server must verify that the cached responses are still valid and that they are the correct responses to the client39s requests You can read more about caching and how it is handled in HTTP in RFC 2068 Add the simple caching functionality described above You do not need to implement any replacement or validation policies Your implementation however will need to be able to write responses to the disk ie the cache and fetch them from the disk when you get a cache hit For this you need to implement some internal data structure in the proxy to keep track of which objects are cached and where they are on the disk You can keep this data structure in main memory there is no need to make it persist across shutdowns


Buy Material

Are you sure you want to buy this material for

75 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.