---
# System prepended metadata

title: Computer network HW answer

---

---
title: Computer network HW answer
---

# 計網作業解答

## HW 1

### R11

$\frac{L}{R_1} + \frac{L}{R_2}$

### R13

* a
  * $\frac{2Mbps}{1Mpbs\ per\ user} = 2\ users$
* b
  * Because the total transmission rate does not exceed the limit rate of the link. 
  * Suppose there are three users can transmit simultaneously without queue delay under packet switching. The total transmission rate will be 3 Mbps which  exceeds the transmission rate of link. Hence, there must be queue delay.
* c
  * 0.2
* d
  * $0.2^3=0.008$

### R18

* wireless : $\frac{1500bytes*8bits/byte}{2*10^6bps} + \frac{1000m}{3*10^8m/s} = 6.003ms$
* twisted pair : $\frac{1500bytes*8bits/byte}{100*10^6bps} + \frac{1000m}{2*10^8m/s} = 0.125ms$

### R19

* a
  * $min\{R_1, R_2, R_3\} = 500kps$
* b
  * $\frac{4*10^6bytes*8bits/byte}{500kbps}=64s$
* c
  * $min\{R_1, R_2, R_3\} = 100kps$
  * $\frac{4*10^6bytes*8bits/byte}{100kbps}=320s$

### P2

* 在 $N\frac{L}{R}$ 時，第 1 個 packet 會在目的地，第 2 個 packet 會在最後一個 Router，依此類推總傳輸時間為 $(N + P - 1)\frac{L}{R}$

### P4

* a
  * 16
* b
  * 8
* c
  * 可以，兩條 A -> B -> C ， A -> D -> C ，依此類推

### P5

* a
  * $10*12s*3 + \frac{75km}{100km/h} = 96min$
* b
  * $8*12s*3 + \frac{75km}{100km/h} = 94min 48s$

### P6

* a
  * $m/s$
* b
  * $L/R$
* c
  * $m/s + L/R$
* d
  * just leve Host A
* e
  * in the link
* f
  * in Host B
* g
  * $5.35*10^5$ m

### P7

*  $\frac{56bytes*8bits/byte}{64kbps} + \frac{56bytes*8bits/byte}{2Mbps} + 10ms = 17.224ms$

### P8

* a
  * $\frac{3Mbps}{150kbps/user} = 20\ users$
* b
  * 0.1
* c
  * ${120 \choose n}(0.1)^n(0.9)^{120 - n}$
* d
  * $1 - \sum_{n = 0}^{20}{{120 \choose n}(0.1)^n(0.9)^{120-n}}$
  * approx by centeral limit theorem ~ 0.003
  * real(Chernoff bound) ~ 0.008

### P9

* a
  * 10000
* b
  * $\sum_{n=N+1}^{M}{M \choose n} p^{n} (1-p)^{M - n}$

### P10

* $\frac{1500 bytes}{4Mbps} + 2ms = 5ms < 6ms$, no queue delay

### P11

* Assume $d_1 > d_2$, $d_1 > d_2 + L/R_2$

### P12

* $\frac{h +L}{R}$
* $\frac{Nh + L}{R}$

### P13

* a
  * $\frac{(N-1)L}{2R}$
* b
  * $\frac{(N-1)L}{2R}$

### P14

* a
  * $\frac{L}{R} + \frac{IL}{R(1 - I)} = \frac{L/R}{1 - I}$

* b 
  * x = L/R
  * total delay : $\frac{x}{1 - ax}$

### P15

* $\frac{\frac{1}{\mu}}{1 - \frac{a}{\mu}} = \frac{1}{\mu - a}$

### P16

* N = 10 + 1
* N = a * (queue delay + transmission delay)
* N = a * (0.01 + 0.01)
* a = 550 packets/sec

### P20

* $min\{R_s, R_c, R/M\}$

### P21

* $min\{R_s, R_c\} > \frac{R_s + R_c}{N}$

### P22

* Probability of successfully receiving a packet : $p_s = (1 - p)^N$
* The average retransmission times : $\frac{1}{p_s} - 1$

### P23

* a
  * $L/R_s$
* b
  * $L/R_c - L/R_s$

### P24

* $\frac{1.5GB}{100Mbps} < \frac{150km}{60km/h} + \frac{1.5GB}{1Gbps}$
* The fastest way is transfer data on the bus

### P25

* a
  * $2Mbps\ *\frac{20000km}{2.5*10^8m/s} = 160000 bits$
* b
  * 160000 bits 
* c 
  * The bandwidth-delay product of a link is the maximum number of bits that can be in the link.
* d
  * 125 m
* e
  * s / R

### P26

* a 
  * 160000 * 500 = 8*$10^7$ bits
* b
  * $8*10^7$ bits
* c
  * 125m / 500 = 0.25 m

### P27

*  Note that each message transmitted by the router to the client takes twice as much time as
the message transmitted by the server to the router (as Rs = 2 * Rc). Starting from when
the router receives the second message, its queue size increases by one message every
two more consecutive messages received. Thus, the router starts dropping messages after
the tenth message is received.

### P28

*  If we count the messages from zero, the size of the buffer is [n/2] after receiving the n-th
message. Thus, the router starts dropping messages when [n/2] > m. There are two cases:
if n is even then n > 2m; if n is odd then n > 2m+1

### P29

* Recall geostationary satellite is 36,000 kilometers away from earth surface
* a
  * 150 msec 
* b
  * 1,500,000 bits 
* c
  * 600,000,000 bits 

### P31

* a
  * Time to send message from source host to first packet switch : 4s
  * The total time to move message from source host
to destination host : 12s
* b
  * Time to send 1st packet from source host to first packet switch : 5 ms
  * Time at which 2nd packet is received at the first switch : 10ms
* c
  * 5ms * 3hop + (800 - 1)*5ms = 4.01s
* d
  * Without message segmentation, if bit errors are not tolerated, if there is a
single bit error, the whole message has to be retransmitted (rather than a single
packet). 
  * Without message segmentation, huge packets (containing HD videos, for
example) are sent into the network. Routers have to accommodate these huge
packets. Smaller packets have to queue behind enormous packets and suffer
unfair delays. 

* e
  * Packets have to be put in sequence at the destination
  * Message segmentation results in many smaller packets. Since header size is
usually the same for all packets regardless of their size, with message
segmentation the total amount of header bytes is more. 

### P32

* The duration of each file transfer increases by the propagation delay at each hop. It
becomes 12.75 s without segmentation and 4.76 with segmentation. As 4.76/12.75 >
4.01/12 segmentation becomes less and less beneficial as the propagation delay increases. 

### P33

* $delay=\frac{S + 80}{R}*(\frac{F}{S} + 2)$
* $\frac{d}{dS} delay = 0 \rightarrow S = \sqrt{40F}$

## HW 2

### R1

* HTTP, FTP, SMTP, POP, TELNET

### R2

* Network architecture refers to the organization of the communication process into
layers (e.g., the five-layer Internet architecture). Application architecture, on the other
hand, is designed by an application developer and dictates the broad structure of the
application (e.g., client-server or P2P). 

### R5

* The IP address of the destination host and the port number of the socket in the
destination process. 

### R8

* Reliable data transfer
  *  TCP provides a reliable byte-stream between client and server but UDP does not.
* A guarantee that a certain value for throughput will be maintained 
  * Neither
* A guarantee that data will be delivered within a specified amount of time
  * Neither
*  Confidentiality (via encryption) 
  * Neither

### R9

* SSL operates at the application layer. The SSL socket takes unencrypted data from
the application layer, encrypts it and then passes it to the TCP socket. If the
application developer wants TCP to be enhanced with SSL, she has to include the
SSL code in the application

### R11

* A protocol is called stateless when it does not keep any information about the clients
during one or more communication sessions; otherwise, it is known as stateful. In
other words, each request sent by a client using a stateless protocol can be interpreted
independently of others. IMAP is not stateless (i.e., it is stateful), as it “remembers”
user information (for instance, what messages have been read) across different
sessions (see also Section 3 of RFC 3501). SMTP is stateful too (see Section 2.3.6 of
RFC 5321). 

### R14

* skip

### R17

* skip

### R21

* BitTorrent is much faster than the centralized client-server approach when the total
upload capacity of the system (i.e., the denominator of the last term in Equation 2.2)
is high. This happens when the sum of the upload rates of individual peers is much
higher than us.

### P1

* F, 4 request message
* T
* F, A TCP segment at most carry one HTTP request
* F. The `Date:` header in HTTP response message indicates when the object was created.
* F, It is possible to response empty message body. ie. 304 status code

### P2

* SMS (Short Message Service) is a technology that allows the sending and receiving of
text messages between mobile phones over cellular networks. One SMS message can
contain data of 140 bytes and it supports languages internationally. The maximum size of
a message can be 160 7-bit characters, 140 8-bit characters, or 70 16-bit characters. SMS
is realized through the Mobile Application Part (MAP) of the SS#7 protocol, and the
Short Message protocol is defined by 3GPP TS 23.040 and 3GPP TS 23.041. In addition,
MMS (Multimedia Messaging Service) extends the capability of original text messages,
and support sending photos, longer text messages, and other content.

* iMessage is an instant messenger service developed by Apple. iMessage supports texts,
photos, audios or videos that we send to iOS devices and Macs over cellular data network
or WiFi. Apple’s iMessage is based on a proprietary, binary protocol APNs (Apple Push
Notification Service).

* WhatsApp Messenger is an instant messenger service that supports many mobile
platforms such as iOS, Android, Mobile Phone, and Blackberry. WhatsApp users can
send each other unlimited images, texts, audios, or videos over cellular data network or
WiFi. WhatsApp uses the XMPP protocol (Extensible Messaging and Presence Protocol). 

* iMessage and WhatsApp are different than SMS because they use data plan to send
messages and they work on TCP/IP networks, but SMS use the text messaging plan we
purchase from our wireless carrier. Moreover, iMessage and WhatsApp support sending
photos, videos, files, etc., while the original SMS can only send text message. Finally,
iMessage and WhatsApp can work via WiFi, but SMS cannot. 

### P4

* a
  * The document request was http://gaia.cs.umass.edu/cs453/index.html. The Host :
field indicates the server's name and /cs453/index.html indicates the file name. 
* b
  * The browser is running HTTP version 1.1, as indicated just before the first <cr><lf>
pair. 
* c
  * The browser is requesting a persistent connection, as indicated by the Connection:
keep-alive. 
* d
  * This is a trick question. This information is not contained in an HTTP message
anywhere. So there is no way to tell this from looking at the exchange of HTTP
messages alone. One would need information from the IP datagrams (that carried the
TCP segment that carried the HTTP GET request) to answer this question. 
* e
  * Mozilla/5.0. The browser type information is needed by the server to send different
versions of the same object to different types of browsers. 

### P5

* a
  * The status code of 200 and the phrase OK indicate that the server was able to locate
the document successfully. The reply was provided on Tuesday, 07 Mar 2008
12:39:45 Greenwich Mean Time. 
* b
  * The document index.html was last modified on Saturday 10 Dec 2005 18:27:46
GMT. 
* c
  * There are 3874 bytes in the document being returned. 
* d
  * The first five bytes of the returned document are : <!doc. The server agreed to a
persistent connection, as indicated by the Connection: Keep-Alive field 

### P7

* a
  * $TT_l + 3*RTT_r$
* b
  * $TT_l + 3*RTT_r$
* c
  * $TT_l$ in both case

### P8

* Assume request the server ip through N DNS
* The DNS delay = $TT_l +\sum_{i = 1}^N RTT_i$
* The $RTT_o$ is the RTT between server and client
* a
  * $18 RTT_o + DNS delay$
* b
  * $6 RTT_o + DNS delay$
* c
  * pipeline
    * $3 RTT_o + DNS delay$
  * non pipeline
    * $10 RTT_o + DNS delay$

### P9

* a
  * The time to transmit an object of size L over a link or rate R : L/R
  * The average time
is the average size of the object divided by R: $\frac{850,000 bits}{15,000,000 bits/sec} = 0.0567s$
  * The traffic intensity on the link : $\frac{16 requests/sec}{.0567 sec/request} =
0.907$
  * The average access delay : $\frac{0.0567 s}{1 - 0.907} \approx 0.6s$
  * The total average response time : 0.6 + 3 = 3.6 s
* b
  * The average access delay : $\frac{0.0567 s}{1 – (0.4)(0.907)} = 0.089 s$
  * The response time is approximately zero if the request is satisfied by the cache (which happens with probability 0.6)
  * The average response time : 0.089 s + 3 s = 3.089 s for cache misses (which
happens with  probability 0.4).
  * The average response time is (0.6)(0 s) + (0.4)(3.089 s) = 1.24 s.
  * Thus the average response time is reduced from 3.6 s to 1.24 s. 

### P10

* a
  * $2 \cdot 100ms + \frac{8 \cdot 10^3bits}{10^6bits/s} + 5 \cdot (2 \cdot 100ms+ \frac{4\cdot10^5bits}{10^6bits/s}) = 3.208s$
* b 
  * $2 \cdot 100ms + \frac{8 \cdot 10^3bits}{10^6bits/s} + 3\cdot(2 \cdot 100ms+ \frac{4\cdot10^5bits}{10^6bits/s}) = 2.008s$
* c
  * $2 \cdot 100ms + \frac{8 \cdot 10^3bits}{10^6bits/s} + 1\cdot(2\cdot 100ms +\frac{4 \cdot 10^5bits}{10^6bits/s}) = 0.808s$
* d
  * $2 \cdot 100ms + \frac{8 \cdot 10^3bits}{10^6bits/s} + 5 \cdot ( \frac{4 \cdot 10^5bits}{10^6bits/s}) = 2.208s$

### P11

* non-persistent
  * $2\cdot RTT_{avg} + \frac{L_d}{R} + 2\cdot N\cdot RTT_{avg} + \sum_{i = 0}^{N-1}\frac{L_i}{R}$
* persistent
  * $2\cdot RTT_{avg} + \frac{L_d}{R} + \sum_{i = 0}^{N-1}\frac{L_i}{R}$

### P15

*  MTA stands for Mail Transfer Agent. A host sends the message to an MTA. The message
then follows a sequence of MTAs to reach the receiver’s mail reader. We see that this
spam message follows a chain of MTAs. An honest MTA should report where it receives
the message. Notice that in this message, “asusus-4b96 ([58.88.21.177])” does not
report from where it received the email. Since we assume only the originator is
dishonest, so “asusus-4b96 ([58.88.21.177])” must be the originator. 

### P16

* The SRV record allows us to request the address of a server based on its domain and a
specific service/protocol combination. It can be seen as a generalization of the MX record
(which only refers to email addresses) to diverse types of services. 

### P17

* a
```
 C: dele 1
 C: retr 2
 S: (blah blah …
 S: ………..blah)
 S: .
 C: dele 2
 C: quit
 S: +OK POP3 server signing off
```

* b
```
 C: retr 2
 S: blah blah …
 S: ………..blah
 S: .
 C: quit
 S: +OK POP3 server signing off
```

* c
```
 C: list
 S: 1 498
 S: 2 912
 S: .
 C: retr 1
 S: blah …..
 S: ….blah
 S: .
 C: retr 2
 S: blah blah …
 S: ………..blah
 S: .
 C: quit
 S: +OK POP3 server signing off
```

### P20

* Without a proxy, all clients need to reach the origin server on the Internet and share the
bandwidth of the bottleneck link. As a consequence, the total transfer time is $2 * RTT + N * L / R_b$. If a proxy is installed, the clients share the bandwidth on the local link with the
proxy. Thus, the total transfer time is $2 * RTT + L / R_b + N * L / R_l$. The file transfer is
faster with the proxy when $R_l > R_l * N / (N – 1)$.

### P22

* client server

| rate | N = 10 | N = 100 | N = 1000 |
| --- | --- | --- | --- |
| 300kbps | 7680 | 51200 | 512000 |
| 700kbps | 7680 | 51200 | 512000 |
| 2Mbps | 7680 | 51200 | 512000 |

* p2p

| rate | N = 10 | N = 100 | N = 1000 |
| --- | --- | --- | --- |
| 300kbps | 7680 | 25904 | 47559 |
| 700kbps | 7680 | 15616 | 21525 |
| 2Mbps | 7680 | 7680 | 7680 |

### P23

* a
  * Consider a distribution scheme in which the server sends the file to each client, in parallel, at a rate of a rate of $u_s/N$. Note that this rate is less than each of the client’s download rate, since by assumption $u_s/N \le d_{min}$. Thus each client can also receive at rate $u_s/N$. Since each client receives at rate $u_s/N$, the time for each client to receive the entire file is $F/(u_s/N) = NF/u_s$. Since all the clients receive the file in $NF/u_s$, the overall distribution time is also $NF/u_s$.
* b
  * Consider a distribution scheme in which the server sends the file to each client, in parallel, at a rate of $d_{min}$. Note that the aggregate rate, $Nd_{min} \le u_s$.
 Since each client receives at rate $d_{min}$, the time for each client to receive the entire file is $F/d_{min}$. Since all the clients receive
the file in this time, the overall distribution time is also $F/d_{min}$.

* c
  * If $u_s/N \le d_{min}$, then $D_{CS} = NF/u_s$
  * If $u_s/N \ge d_{min}$, then $D_{CS} = F/d_{min}$
  * Hence, $D_{CS} \ge max\{NF/u_s, F/d_{min}\}$

### P24

* a
  * $u = \sum_{i = 1}^{N}u_i$
  * Divided file into N part with the size of $(u_i/u)F$
  * The server transmits each peer i with the $i$ part at rate $r_i = (u_i/u)u_s$
  * The aggregate forwarding rate by peer i is $(N-1)r_i \le u_i$
  * In this distribution scheme, peer i receives bits at an aggregate rate of $r_i + \sum_{i\neq j}r_j = u_s$
  * Thus each peer receives the file in $F/u_s$
* b
  * $u = \sum_{i = 1}^{N}u_i$
  * $r_i = u_i / (N - 1)$
  * $r_{N + 1} = (u_s - u / (N - 1))/ N$
  * Divided file $F$ in N + 1 part with the size of $F/(N + 1)$
  * The server transmits each peer i with the $i$ part at rate $r_i$
  * The server transmits each peer i with the last part of file at rate $r_{N + 1}$
  * The aggregate send rate of peer i is $u_i$
  * In this distribution scheme, peer i receives bits at an aggregate rate of $r_i + \sum_{i<>j}r_j = (u_s + u) / N$
  * Thus each peer receives the file in $NF/(u_s+u)$
* c
  * Combine a and b to get the result

### P26

* $N^2$ files
* 2N files

### P27

* a
  * If you run TCPClient first, then the client will attempt to make a TCP connection with
a non-existent server process. A TCP connection will not be made.
* b
  * UDPClient doesn't establish a TCP connection with the server. Thus, everything
should work fine if you first run UDPClient, then run UDPServer, and then type some
input into the keyboard. 
* c
  * If you use different port numbers, then the client will attempt to establish a TCP
connection with the wrong process or a non-existent process. Errors will occur. 

### P28

* It is not neccessary to change UDPServer.py
* After modification, the client port is 5432.
* Before making this change, the client port is assigned by OS randomly.

