CS-NETWORK HW1

# CS-NETWORK HW1 ## R11 **Suppose there is exactly one packet switch between a sending host and a receiving host. The transmission rates between the sending host and the switch and between the switch and the receiving host are R1 and R2, respectively. Assuming that the switch uses store-and-forward packet switching, what is the total end-to-end delay to send a packet of length L? (Ignore queuing, propagation delay, and processing delay.)** :::info (L/R1)+(L/R2) ::: ## R13 **Suppose users share a 2 Mbps link. Also suppose each user transmits continuously at 1 Mbps when transmitting, but each user transmits only 20 percent of the time. (See the discussion of statistical multiplexing in Section 1.3.)** ### a **When circuit switching is used, how many users can be supported?** :::info $\dfrac{2Mbps}{1Mbps} = 2$ 兩位 ::: ### b **For the remainder of this problem, suppose packet switching is used. Why will there be essentially no queuing delay before the link if two or fewer users transmit at the same time? Why will there be a queuing delay if three users transmit at the same time?** :::info 2個最大也是用2Mbps，剛剛好三個含以上同時都傳送就會需要3Mbps就需要Queuing delay ::: ### c **Find the probability that a given user is transmitting.** :::info Probability that a given user is transmitting = 0.2 ::: ### d **Suppose now there are three users. Find the probability that at any given time, all three users are transmitting simultaneously. Find the fraction of time during which the queue grows.** :::info $(0.2)^3 = 0.008$ ::: ## R18 **A user can directly connect to a server through either long-range wireless or a twisted-pair cable for transmitting a 1500-bytes file. The transmission rates of the wireless and wired media are 2 and 100 Mbps, respectively. Assume that the propagation speed in air is 3 x 10$^8$ m/s, while the speed in the twisted pair is 2 x 10$^8$ m/s. If the user is located 1 km away from the server, what is the nodal delay when using each of the two technologies.** :::info **Wireless** - Transmission Delay = 12000 / (2 * $10^6$) = 0.006s = 6ms - Propagation delay = 1000 / (3 * $10^8$) = 0.00000333333s = 0.003 ms - 6ms +0.003ms = **6.003ms** **Wired** - Transmission Delay = 12000 / (1 * $10^8$) = 0.00012s = 0.12ms - Propagation delay = 1000 / (2 * $10^8$) = 0.000005s = 0.005 ms Transmission Delay + Propagation delay = 0.12ms + 0.005ms = **0.125ms** ::: ## R19 **Suppose Host A wants to send a large file to Host B. The path from Host A to Host B has three links, of rate R1 = 500 kbps, R2 = 2 Mbps, and R3 = 1 Mbps.** ### a **Assuming no other traffic in the network, what is the throughput for the file transfer?** :::info 500kbps ::: ### b **Suppose the file is 4 million bytes. Dividing the file size by the throughput, roughly how long will it take to transfer the file to Host B?** :::info 4 million bytes = 32 * $10^6$ bits throughput -> 500kbps = 500 * $10^3$ = 5 * $10^5$ bps packet of length / transmission rates = $\dfrac{32 * 10^6}{5 * 10^5}$ = 64s ::: ### c **Repeat (a) and (b), but now with R2 reduced to 100 kbps.** :::info $\dfrac{32 * 10^6}{1 * 10^5}$ = 320s ::: ## P2 **Equation 1.1 gives a formula for the end-to-end delay of sending one packet of length L over N links of transmission rate R. Generalize this formula for sending P such packets back-to-back over the N links.** ![](https://i.imgur.com/g8cjk7H.png) :::info Back-to-back first packet -> $N*\dfrac{L}{R}$ till last packet -> $(P - 1)*\dfrac{L}{R}$ $N*\dfrac{L}{R} + (P - 1)*\dfrac{L}{R} = (N+P-1)*\dfrac{L}{R}$ ::: ## P4 **Consider the circuit-switched network in Figure 1.13. Recall that there are 4 circuits on each link. Label the four switches A, B, C, and D, going in the clockwise direction.** ![](https://i.imgur.com/HmCTlC9.png) ### a **What is the maximum number of simultaneous connections that can be in progress at any one time in this network?** :::info all connect to next host => 4 * 4 = 16 ::: ### b **Suppose that all connections are between switches A and C. What is the maximum number of simultaneous connections that can be in progress?** :::info A -> B -> C => 4 a -> D -> C => 4 4 + 4 = 8 ::: ### c **Suppose we want to make four connections between switches A and C, and another four connections between switches B and D. Can we route these calls through the four links to accommodate all eight connections?** :::info Yes 兩兩交錯 A > B > C 兩個, A > D > C 兩個 B > C > D 兩個, B > A > D 兩個 ::: ## P5 **Review the car-caravan analogy in Section 1.4. Assume a propagation speed of 100 km/hour. Tollbooths are 75 km apart, and the cars propagate at 100km/hr. A tollbooth services a car at a rate of one car every 12 seconds. There are 10 cars.** ### a **Suppose the caravan travels 150 km, beginning in front of one tollbooth, passing through a second tollbooth, and finishing just after a third tollbooth. What is the end-to-end delay?** :::info 75 / 100 * 60 = 45 min 10 * 12 = 120s = 2 min 2+45+2+45+2 = **96min** ::: ### b **Repeat (a), now assuming that there are eight cars in the caravan instead of ten.** ![](https://i.imgur.com/x3HuQts.png) :::info 75 / 100 * 60 = 45 min 12 * 8 = 96s 96s + 45min + 96s + 45min + 96s = **94min48s** ::: ## P6 **This elementary problem begins to explore propagation delay and transmission delay, two central concepts in data networking. Consider two hosts, A and B, connected by a single link of rate R bps. Suppose that the two hosts are separated by m meters, and suppose the propagation speed along the link is s meters/sec. Host A is to send a packet of size L bits to Host B.** ### a Express the propagation delay, $d{prop}$, in terms of m and s. :::info $d_{prop}$ = m/s seconds ::: ### b Determine the transmission time of the packet, $d{trans}$, in terms of L and R. :::info $d_{trans}$ = L / R seconds ::: ### c Ignoring processing and queuing delays, obtain an expression for the end-to-end delay. :::info $d_{end-to-end}$ = $d_{prop}$ + $d_{trans}$ **(m / s) + (L / R) Seconds** ::: ### d Suppose Host A begins to transmit the packet at time t = 0. At time t = $d_{trans}$, where is the last bit of the packet? :::info The bit is just leaving Host A ::: ### e Suppose $d_{prop}$ is greater than $d_{trans}$. At time t = $d_{trans}$, where is the first bit of the packet? :::info The first bit has not reached Host B. Because of the $d_{prop}$ not finish. ::: ### f Suppose $d_{prop}$ is less than $d_{trans}$. At time t = $d_{trans}$, where is the first bit of the packet? :::info The first bit has reached Host B. Because $d_{prop}$ has fininshed. ::: ### g Suppose s = 2.5 * $10^8$ , L = 120bits, and R = 56kbps. Find the distance m so that $d_{prop}$ equals $d_{trans}$. :::info $\dfrac{L}{R}$ = $\dfrac{m}{s}$ m = $\dfrac{L}{R}$ * s m = $\dfrac{120}{56 * 10^3}$ * (2.5 * $10^8$) = 535714.285m $\approx$ **536km** ::: ## P7 **In this problem, we consider sending real-time voice from Host A to Host B over a packet-switched network (VoIP). Host A converts analog voice to a digital 64 kbps bit stream on the fly. Host A then groups the bits into 56-byte packets. There is on link between Hosts A and B; its transmission rate is 2 Mbps and its propagation delay is 10 msec. As soon as Host A gathers a packet, it sends it to Host B. As soon as Host B receives an entire packet, it converts the packet’s bits to an analog signal. How much time elapses from the time a bit is created (from the original analog signal at Host A) until the bit is decoded (as part of the analog signal at Host B)?** :::info - packet generate time : $\dfrac{56*8}{64*10^3}$ = 7 ms - transmission delay : $\dfrac{56*8}{2*10^6}$ = = 224 µs - propagation delay : 10 ms **7ms + 10ms + 224µs = 17.224 ms** ::: ## P8 **Suppose users share a 3 Mbps link. Also suppose each user requires 150 kbps when transmitting, but each user transmits only 10 percent of the time. (See the discussion of packet switching versus circuit switching in Section 1.3.)** ### a When circuit switching is used, how many users can be supported? :::info $\dfrac{3000}{150}$ = 20 ::: ### b For the remainder of this problem, suppose packet switching is used. Find the probability that a given user is transmitting. :::info p = 0.1 ::: ### c Suppose there are 120 users. Find the probability that at any given time, exactly n users are transmitting simultaneously. (Hint: Use the binomial distribution.) :::info $\left( \begin{array}{c} 120 \\ n \\ \end{array} \right) p^n(1-p)^{120-n}$ ::: ### d Find the probability that there are 21 or more users transmitting simultaneously. :::info $1 -\sum_{n=0}^{20} \left( \begin{array}{c} 120 \\ n \\ \end{array} \right) p^n(1-p)^{120-n}$ ::: :::warning $1 - P(\leq 20 people)$ ::: ## P9 **Consider the discussion in Section 1.3 of packet switching versus circuit switching in which an example is provided with a 1 Mbps link. Users are generating data at a rate of 100 kbps when busy, but are busy generating data only with probability p = 0.1. Suppose that the 1 Mbps link is replaced by a 1 Gbps link.** ### a What is N, the maximum number of users that can be supported simultaneously under circuit switching? :::info $\dfrac{10^6}{10^2}$ = 10000 ::: ### b Now consider packet switching and a user population of M users. Give a formula(in terms of p, M, N) for the probability that more than N users are sending data. :::info 1. $1 -\sum_{n=0}^{M} \left( \begin{array}{c} M \\ n \\ \end{array} \right) p^n(1-p)^{120-n}$ 2. $\sum_{n=N+1}^{M} \left( \begin{array}{c} M \\ n \\ \end{array} \right) p^n(1-p)^{m-n}$ ::: ## P10 **Consider the network illustrated in Figure 1.16. Assume the two hosts on the left of the figure start transmitting packets of 1500 bytes at the same time towards Router B. Suppose the link rates between the hosts and Router A is 4-Mbps. One link has a 6-ms propagation delay and the other has a 2-ms propagation delay. Will queuing delay occur at Router A?** ![](https://i.imgur.com/oJRCnhc.png) :::info 1500 * 8 = 12000 12000 / (4 * 10^6) = 0.003s = 3ms 3ms + 2ms = 5ms 6 > 5 #### no delay ::: ## P11 **Consider the scenario in Problem P10 again, but now assume the links between the hosts and Router A have different rates R1 and R2 byte/s in addition to different propagation delays d1 and d2. Assume the packet lengths for the two hosts are of L bytes. For what values of the propagation delay will no queuing delay occur at Router A?** :::info assume d2 > d1 than (L/R1) + d1 < d2 meet the requirement ::: ## P12 **Consider a client and server connected through one router. Assume the router can start transmitting an incoming packet after receiving its first h bytes instead of the whole packet. Suppose that the link rates are R byte/s and that the client transmits one packet with a size of L bytes to the server. What is the end-to-end delay? Assume the propagation, processing, and queuing delays are negligible. Generalize the previous result to a scenario where the client and the server are interconnected by N routers.** :::info one router => $\dfrac{h}{R} + \dfrac{L}{R}$ N router => $N*\dfrac{h}{R} + \dfrac{L}{R}$ ::: ## P13 ### a Suppose N packets arrive simultaneously to a link at which no packets are currently being transmitted or queued. Each packet is of length $L$ and the link has transmission rate $R$. What is the average queuing delay for the $N$ packets? :::info $(\dfrac{\dfrac{L}{R} + 2\dfrac{L}{R} + 3\dfrac{L}{R} + .... + (N-1)\dfrac{L}{R}}{N}) = \dfrac{L}{RN}(1+2+...+(N-1))\\ = \dfrac{L}{RN} * \dfrac{N(N-1)}{2} \\= \dfrac{(N-1)L}{2R}$ ::: ### b Now suppose that N such packets arrive to the link every $N*\dfrac{L}{R}$ seconds. What is the average queuing delay of a packet? :::info $\dfrac{(N-1)L}{2R}$ ::: ## P14 **Consider the queuing delay in a router buffer. Let I denote traffic intensity; that is $I = La/R$. Suppose that the queuing delay takes the form $IL/R (1 - I) for I < 1$.** ### a. Provide a formula for the total delay, that is , the queuing delay plus the transmission delay. :::info The transmission delay is $\dfrac{L}{R}$ Queuing delay is $\dfrac{IL}{R(1-I)}$ Total Delay = $\dfrac{L}{R} + \dfrac{IL}{R(1-I)} = \dfrac{L/R}{(1-I)}$ ::: ### b. Plot the total delay as a function of L/R :::info Total Delay = $\dfrac{L}{R} + \dfrac{IL}{R(1-I)} = \dfrac{L/R}{(1-I)}$ $f(x) = \dfrac{L}{R}$ $I = \dfrac{La}{R}$ Total Delay => $\dfrac{f(x)}{(1-af(x))}$ if $f(x) = 0$, 則 Total delay 為 0 隨 $f(x)$增加則 Total Delay 變大當 $f(x)$趨近於 $\dfrac{1}{a}$ 則接近無窮大 ::: ## P15 **Let $a$ denote the rate of packets arriving at a link in packets/sec, and let $μ$ denote the link’s transmission rate in packets/sec. Based on the formula for the total delay (i.e., the queuing delay plus the transmission delay) derived in the previous problem, derive a formula for the total delay in terms of $a$ and $μ$.** :::info $\dfrac{L}{R} = \dfrac{1}{u}$ Total Delay = $\dfrac{L/R}{(1-I)} = \dfrac{L/R}{(1-aL/R)} = \dfrac{1/u}{(1-a/u)} = \dfrac{1}{(u-a)}$ ::: ## P16 **Consider a router buffer preceding an outbound link. In this problem, you will use Little’s formula a famous formula from queuing theory. Let $N$ transmitted. Let $a$ denote the rate of packets arriving at the link. Let $d$ denote the average total delay (i.e., the queuing delay plus the transmission delay) experienced by a packet. Little’s formula is $N = a * d$ . Suppose that on average, the buffer contains 10 packets, and the average packet queuing delay is 10 msec. The link’s transmission rate is 100 packets/sec. Using Little’s formula, what is the average packet arrival rate, assuming there is no packet loss?** :::info The total number of packets in the system includes those in the buffer and the packet that is being transmitted. So, N=10+1. $d_{queue}$ = 10ms = 0.01s $d_{tran}$ = 1/100 s $N = a * d_{total} \\ (10+1)=a*(d_{queue} + d_{tran}) \\ 11 = a *(0.01 + \dfrac{1}{100}) \\ a = 550 packets/sec$ ::: ## P20 **Consider the throughput example corresponding to Figure 1.20(b). Now suppose that there are M client-server pairs rather than 10. Denote $Rs, Rc$, and $R$ for the rates of the server links, client links, and network link. Assume all other links have abundant capacity and that there is no other traffic in the network besides the traffic generated by the $M$ client-server pairs. Derive a general expression for throughput in terms of $Rs, Rc, R, and M$.** ![](https://i.imgur.com/3nLBAbm.png) :::info $Throughput = min(Rs, Rc, \dfrac{R}{M})$ ::: ## P21 **Assume a client and a server can connect through either network (a) or (b) in Figure 1.19. Assume that $R_i = (R_c + R_s) / i, i = 1, 2, …, N$. In what case will network (a) have a higher throughput than network (b)?** ![](https://i.imgur.com/pjOTGk1.png) :::info * throught of a is $Rc$, $R_s > (R_s + R_c)/N$ -> $Rc > Rs/(N − 1)$ * throught of a is $Rs$, > $R_c > (R_s + R_c)/N$ -> $Rs > Rc/(N − 1)$ ::: :::warning 原先Network b 的 throughput是$min(R_1 , R_2,...,R_n)$ 但題目又假設$R_i = (R_c + R_s) / i$，$R_c, R_s固定下最小的是R_n$ 在計算Network a 的 throughput要大於Network b 的 throughput的情況 ::: ## P22 **Consider Figure 1.19(b). Suppose that each link between the server and the client has a packet loss probability $p$, and the packet loss probabilities for these links are independent. What is the probability that a packet (sent by the server) is successfully received by the receiver? If a packet is lost in the path from the server to the client, then the server will re-transmit the packet. On average, how many times will the server re-transmit the packet in order for the client to successfully receive the packet?** :::info Probability of successfully receiving a packet is : $P_s = (1 - p)^N$ 代表說平均要傳$\dfrac{1}{(1 - p)^N} = \dfrac{1}{P_s}次$才成功因此需要重傳$\dfrac{1}{P_s} - 1次$ ::: ## P23 Consider Figure 1.19(a). Assume that we know the bottleneck link along the path from the server to the client is the first link with rate $R_s$ bits/sec. Suppose we send a pair of packets back to back from the server to the client, and there is no other traffic on this path. Assume each packet of size $L$ bits, and both links have the same propagation delay $d_{prop}$. ### a What is the packet inter-arrival time at the destination? That is, how much time elapses from when the last bit of the first packet arrives until the last bit of the second packet arrives? :::info 假設有A和B封包,A是第一個傳出的,B是第二個傳出的因為是Back-to-Back，且$d_{prop}$相同所以要等的時間就是$d_{trans} = \dfrac{L}{R_s}$ ::: :::warning 因為是Back-to-Back且$d_{prop}$相同因此就是$d_{trans}$ ::: ### b Now assume that the second link is the bottleneck link (i.e., $R_c < R_s$). Is it possible that the second packet queues at the input queue of the second link? Explain. Now suppose that the server sends the second packet $T$ seconds after sending the first packet. How large must $T$ be to ensure no queuing before the second link? Explain. :::info $\dfrac{L}{R_s} + \dfrac{L}{R_s} + d_{prop} + T \geq \dfrac{L}{R_s} + d_{prop} + \dfrac{L}{R_c}$ Thus, the minimum value of T is $\dfrac{L}{R_c} - \dfrac{L}{R_s}$ ::: :::warning 會有Queuing Delay 第二個Packet到second link了但second link還沒傳完第一個packet 第二個Packet到second link < second link傳完第一個packet --- second link傳完第一個packet : 第一個packet的first link 的 delay + second link的$d_{tran}$ $\dfrac{L}{R_s} + d_{prop} + \dfrac{L}{R_c}$ 第二個Packet到second link : 第一個packet的first link 的$d_{tran}$ + 第二個packet的first link 的$d_{tran}$ + back-to-back所以只有一個$d_{prop}$ $\dfrac{L}{R_s} + \dfrac{L}{R_s} + d_{prop}$ ::: --- ## P24 Consider a user who needs to transmit 1.5 gigabytes of data to a server. The user lives in a small town where only dial-up access is available. A bus visits the small town once a day from the closest city, located 150 km away, and stops in front of the user’s house. The bus has a 100-Mbps WiFi connection. It can collect data from users in rural areas and transfer them to the Internet through a 1 Gbps link once it gets back to the city. Suppose the average speed of the bus is 60km/h. What is the fastest way the user can transfer the data to the server? :::info $1.5 GB = 12 * 10^9 bits$ - dial up $\dfrac{12 * 10^9}{56 * 10^3} = 214286s = 59.5 hr$ - Bus - 傳到公車上$\dfrac{12 * 10^9}{100 * 10^6} = 120s$ - 開車到城市 150 / 60 = 2.5 h - 城市再接網路 $\dfrac{12 * 10^9}{1 * 10^9} = 12s$ 用公車這個方案比較快 ::: :::warning - dial up : $56 * 10^3bps$ - Bus - 1. 傳到公車上 - 2. 開車到市區裡 - 3. 市區再接到Internet ::: ## P25 **Suppose two hosts, A and B, are separated by 20,000 kilometers and are connected by a direct link of R = 2Mbps. Suppose the propagation speed over the link is $2.5*10^8$ meters/sec.** ### a Calculate the bandwidth-delay product, R．$d_{prop}$. :::info $20000km = 2 * 10^7 m$ $d_{prop} = \dfrac{2 * 10^7}{2.5*10^8} = 0.08s$ $R = 2Mbps = 2 * 10^6 bps$ bandwidth-delay product$= 0.08(2 * 10^6) = 160000 bits$ ::: ### b Consider sending a file of 800,000 bits from Host A to Host B. Suppose the file is sent continuously as one large message. What is the maximum number of bits that will be in the link at any given time? :::info 160000bits ::: ### c Provide an interpretation of the bandwidth-delay product. :::info The bandwidth-delay product of a link is the maximum number of bits that can be in the link. ::: ### d What is the width (in meters) of a bit in the link? Is it longer than a football field? :::info the width of a bit = length of link / bandwidth-delay product, so 1 bit is 125 meters long, which is longer than a football field $\dfrac{2*10^7}{160000} = 125meters/s$ ::: :::warning width of a bit = length of link / bandwidth-delay 足球場長度90~120公尺...... ::: ### e Derive a general expression for the width of a bit in terms of the propagation speed s, the transmission rate R, and the length of the link m. :::info width of a bit = length of link / bandwidth-delay length of link = m bandwidth-delay = R * (m/s) = $\dfrac{m}{R(m/s)} = \dfrac{m}{R}\dfrac{1}{(m/s)} = \dfrac{m}{R}\dfrac{s}{m} = \dfrac{s}{R}$ ::: ## P26 Consider problem P25 but now with a link of R = 1 Gbps. ### a Calculate the bandwidth-delay product, $R * d_{prop}$. :::info $20000km = 2 * 10^7 m$ $d_{prop} = \dfrac{2 * 10^7}{2.5*10^8} = 0.08s$ $R = 1Gbps = 1 * 10^9 bps$ bandwidth-delay product$= 0.08(1 * 10^9) = 80,000,000 bits$ ::: :::warning P26 $R = 1Gbps = 1 * 10^9 bps$ ::: ### b Consider sending a file of 800,000 bits from Host A to Host B. Suppose the file is sent continuously as one big message. What is the maximum number of bits that will be in the link at any given time? :::info min(bandwidth delay product, packet size) = 800,000 bits. ::: ### c What is the width (in meters) of a bit in the link? :::info $\dfrac{s}{R} = \dfrac{2.5*10^8}{10^9} = 0.25m$ ::: ## P27 **Consider the scenario illustrated in Figure 1.19(a). Assume Rs is 20 Mbps, Rc is 10 Mbps, and the server is continuously sending traffic to the client. Also assume the router between the server and the client can buffer at most four messages. After how many messages sent by the server will packet loss starts occurring at the router?** ![](https://i.imgur.com/2qVTJJ4.png) :::info $R_s : R_c = 2 : 1$ 意思是Router收到連續兩個Message時會有一個在Queue Buffer最多有4個傳到第10個就會packet loss 2 0 0 -> 2 2 1 1 -> 4 2 2 1 2 3 1 2 4 1 -> 10 ::: :::warning $R_s = 2 * R_c$ 意思是Router傳送給Client的時間會是Server傳給Router時間的兩倍 Router連續收到兩個Message時會有一個在Queue ::: ## P28 **Generalize the result obtained in Problem P27 for the case where the router can buffer m messages** :::info 設n為第n個收到的message Buffer裡有$[\dfrac{n}{2}]$ 當$[\dfrac{n}{2}] > m$則Router會drop message ::: :::warning 設n為第n個收到的message Buffer裡有$[\dfrac{n}{2}]$ ::: ## P29 Suppose there is a 10-Mbps microwave link between a geostationary satellite and its base station on Earth. Every minute the satellite takes a digital photo and sends it to the base station. Assume a propagation speed of $2.4*10^8$ meters/sec. ### a What is the propagation delay of the link? :::info Recall geostationary satellite is 36,000 kilometers away from earth surface. $\dfrac{3.6 * 10 ^ 7}{2.4*10^8} = 0.15s$ ::: :::warning $d_{prop} = \dfrac{Distance}{Speed}$ ::: ### b What is the bandwidth-delay product, $R*d{prop}$? :::info $36000km = 3.6 * 10^7 m$ $d_{prop} = \dfrac{3.6 * 10^7}{2.4*10^8} = 0.15s$ $R = 10Mbps = 10 * 10^6 bps$ bandwidth-delay product$= 0.15(10 * 10^6) = 1500000 bits$ ::: :::warning $d_{prop} = \dfrac{Distance}{Speed}$ $R = 10Mbps$ bandwidth-delay product = $R * d_{prop}$ ::: ### c Let x denote the size of the photo. What is the minimum value of x for the microwave link to be continuously transmitting? :::info 10Mbps = $10 * 10^6$ = $1 * 10^7$ 每一分鐘拍一張並傳給基地台因此x最小可為 $60 * 10^7$ = 600000000 = $6 * 10^8$ bits ::: :::warning 10Mbps 那一分鐘可以傳的資料量是 ::: ## P31 In modern packet-switched networks, including the Internet, the source host segments long, application-layer messages (for example, an image or a music file) into smaller packets and sends the packets into the network. The receiver then reassembles the packets back into the original message. We refer to this process as message segmentation. Figure 1.27 illustrates the end-to-end transport of a message with and without segmentation. Consider a message that is $8*10^6$ bits long that is to be sent from source to destination in Figure 1.27. Suppose each link in the figure is **2 Mbps**. Ignore propagation, queuing, and processing delays. ![](https://i.imgur.com/tTjeYLD.png) ### a Consider sending the message from source to destination without message segmentation. How long does it take to move the message from the source host to the first packet switch? Keeping in mind that each switch uses store-andforward packet switching, what is the total time to move the message from source host to destination host? :::info $\dfrac{8*10^6}{2*10^6} = 4s$ 經過三個hop所以為12s ::: :::warning $\dfrac{L}{R}*hop數$ ::: ### b Now suppose that the message is segmented into 800 packets, with each packet being **10,000 bits** long. How long does it take to move the first packet from source host to the first switch? When the first packet is being sent from the first switch to the second switch, the second packet is being sent from the source host to the first switch. At what time will the **second packet be fully received at the first switch**? :::info $\dfrac{1*10^4}{2*10^6} = 5ms$ 2*5 = 10ms 0 -> 5ms -> 10ms ::: :::warning Time at which 2nd packet is received at the first switch = time at which 1st packet is received at the second switch ::: ### c How long does it take to move the file from source host to destination host when message segmentation is used? Compare this result with your answer in part (a) and comment. :::info 15ms + (800-1)*5ms = 4.01s ::: :::warning 第一個packet到目的地的時間 + 剩下每$\dfrac{L}{R}$會來一個packet ::: ### d In addition to reducing delay, what are reasons to use message segmentation? :::info 1. retransmission 只要傳那個packet就好 2. unfair delays (若前面有比較大的則要等更久比較小的) ::: ### e Discuss the drawbacks of message segmentation. :::info 1. 順序可能打亂，要加 seq num. 2. 如果切很小，header又占一部分，利用率就沒有很高 ::: ## P32 Consider Problem P31 and assume that the propagation delay is 250 ms. Recalculate the total time needed to transfer the source data with and without segmentation. Is segmentation more beneficial or less if there is propagation delay? :::info 12s + 250ms*3 = 12.75s (without message segmentation) 4.01 + 250ms*3 = 4.76s (message segmentation) 12.75/4.76 = 2.67 剛剛沒有Propagation delay時到4倍，所以好處降低 ::: :::warning P31的加上3*Propagation delay 再去比較有無propagation delay情況下好或壞 ::: ## P33 Consider sending a large file of $F$ bits from Host A to Host B. There are three links (and two switches) between A and B, and the links are uncongested (that is, no queuing delays). Host A segments the file into segments of S bits each and adds 80 bits of header to each segment, forming packets of $L = 80 + S$ bits. Each link has a transmission rate of $R$ bps. Find the value of S that minimizes the delay of moving the file from Host A to Host B. Disregard propagation delay :::info A-----$S_1$-----$S_2$-----B 全部有 $\dfrac{F}{S}$個Segments A----$S_1$ : 最後一個Packet到是 $\dfrac{S+80}{R} * \dfrac{F}{S}$ The whole file delay is $\dfrac{S+80}{R} * (\dfrac{F}{S}+2)$ +2 是 $S_1$-----$S_2$-----B S = $\sqrt{40F}$ ::: :::warning 全部有 $\dfrac{F}{S}$個Segments 最後一個Packet到是 A----$S_1$ : $\dfrac{S+80}{R} * \dfrac{F}{S}$ $S_1$-----$S_2$ : $\dfrac{F}{S}$ $S_2$-----B : $\dfrac{F}{S}$ 算出來的值對S微分等於0求小值 :::