------------------------------------------------------------------------------ CSC358 Tutorial 3 Notes Below are some notes and sample solutions to the tutorial questions. These notes are only meant to provide the necessary amount of information for you to verify your own work and to help you recall the discussions in the tutorial. Simply reading these solutions does NOT convey the same learning experience as attending a tutorial (not even close). The tutorial materials are a mandatory and important component of this course, so don't miss any of them! ------------------------------------------------------------------------------ Question 1: Review lecture slides for answers. ------------------------------------------------------------------------------ Question 2 The point of this question is to discuss thoroughly about what's happening behind the scene. There is not an absolute correct answer. The following should be taken into consideration: - For the first object, all the DNS queries that are performed. - For all the objects, the HTTP requests ad responses - Need to specify whether we're using persistent or non-persistent HTTP connections. In total, the answer should be around 70T~90T. ------------------------------------------------------------------------------ Question 2 (a) Intuition: The server upload rate is relatively low, so assign the job of distributing the file primarily to the peers. Let each peer take a fair chunk of the file to distribute. Divide the file into N equal parts, each part of size F/N. The server uploads each part to a separate peer at rate r = us/N. Note that Nr = us,so that the aggregate server rate does not exceed the link rate of the server. Also have each peer forward the bits it receives to each of the N-1 peers at rate r. The aggregate forwarding rate by each peer is (N-1)r. We have (N-1)r = us(N-1)/N <= uc N/(N-1) x (N-1)/N = uc, where the second last inequality follows from the condition us <= uc N/(N-1). Thus the aggregate forwarding rate of each peer is less than its upload rate uc. In this distribution scheme, each peer receives bits at an aggregate rate of r + (N-1)r = Nr = us (r is from the server, (N-1)r from other peers) Thus each peer receives the file in F/us. (b) Intuition: In this case, the server is more powerful, or relatively the peers are less powerful, so the idea is to let the peers do the best they can, and let the server handle the rest. In this distribution scheme, the file is broken into N+1 parts. The server uploads bits from the first N parts to the N peers, one part for each peer, at rate r = uc/(N-1). Each peer i forwards the bits arriving at rate r to each of the other N-1 peers. Therefore, the upload rate of each peer is r(N-1) = uc, i.e., at full uploading capacity. The rest of upload (the N+1st chunk) is taken care of by the server, i.e., the server uploads bits from the (N+1)st part using its leftover upload rate: s = us - Nr = us - uc N/(N-1), which is >= 0 because of the assumption in this part. The server uploads to each of the N peers at rate s/N. The peers do not forward the bits from the (N+1)st chunk since they're already at fulling uploading capacity. rN = uc N/(N-1) is the server's total upload rate for chunks 1 to N, and s = us - uc N/(N-1) is the upload rate for the N+1st chunk, so the aggregate upload rate of the server is: rN + s = us so the server upload is just maxed. The peers are already maxed, so everyone is maxed. In this distribution scheme, each peer receives bits at an aggregate rate of d = r + (N-1)r + s/N = Nr + s/N = Nuc/(N-1) + us/N - uc/(N-1) = us/N + uc therefore the time taken to obtain the file is F / d = F / (us/N + uc) = NF / (us + Nuc) Note: the sizes of the N+1 chunks should be proportional to the rate they're being uploaded in, i.e., the first N chunks each has size Fr/(Nr + s) and the N+1st chunk has size Fs/(Nr + s).