Chapter 1 Review Questions

Section 1.1

Q1. What is the difference between a host and an end system? List several different types of end systems. Is a Web server an end system?

Solution. Host and end system are used interchangeably. Hosts or end systems include Desktops, Laptops (PCs), workstations, Web servers, mail servers, Personal Digital Assistants, Internet-connected game consoles, etc.

Q2. The word protocol is often used to describe diplomatic relations. How does Wikipedia describe diplomatic protocol?

Solution. From Wikipedia: Diplomatic protocol is commonly described as a set of international courtesy rules. These well-established and time-honored rules have made it easier for nations and people to live and work together. Part of protocol has always been the acknowledgment of the hierarchical standing of all present. Protocol rules are based on the principles of civility— Dr. P.M. Forni on behalf of the International Association of Protocol Consultants and Officers.

Q3. Why are standards important for protocols?

Solution.In order to bring all the heterogeneous and homogeneous systems to a common platform, where all can intercommunicate successfully there is a need to establish some standards which all communicating required to follow.

Standards are important for protocols so that people can create networking systems and products that inter-operate.

Section 1.2

Q4. List six access technologies. Classify each one as home access, enterprise access, or wide-area wireless access.

Solution. Following are the technologies classified as home, small office, enterprise or wide area wireless access:

Technology Classification
Dial-up modem over telephone line home
DSL over telephone line home or small office
Cable to HFC home
100 Mbps switched Ethernet enterprise
Wifi (802.11) home and enterprise
3G and 4G wide-area wireless

Q5. Is HFC trSolutionmission rate dedicated or shared among users? Are collisions possible in a downstream HFC channel? Why or why not?

Solution.Bandwidth in Hybrid Fiber Coaxial (HFC) is shared among the multiple users. On the downstream channel, all packets originate from a single source, the head end, and every packet sent by a home travels on the upstream channel to the head end. Thus, there are no collisions in the downstream channel. (Section 1.2.1)

Q6. List the available residential access technologies in your city. For each type of access, provide the advertised downstream rate, upstream rate, and
monthly price.

Solution.In India the currently available facilities are: Broadband, DSL, Cable Modem; Fiber-to-the-home (Jio Fiber or BSNL), RF Link (Local Internet Service Providers like, Tikona, WiMax, Den Networks etc. (Section 1.2.1)

Q7. What is the transmission rate of Ethernet LANs?

Solution.Ethernet LANs (Local Area Networks) have transmission rates of 10 Mbps, 100 Mbps, 1 Gbps and 10 Gbps. (Section 1.2.1)

Q8. What are some of the physical media that Ethernet can run over?

Solution.Ethernet can run over twisted-pair copper wire (Commonly known as Ethernet or LAN Cable). Optical fiber links are also used for Ethernet.

Q9. Dial-up modems, HFC, DSL and FTTH are all used for residential access.
For each of these access technologies, provide a range of transmission rates
and comment on whether the transmission rate is shared or dedicated.

Solution.

Technology Bandwidth

Dedicated/ Shared (Bandwidth)

Dial-up modem over telephone line up to 56 Kbps Bandwidth is Dedicated
ADSL over telephone line up to 24 Mbps downstream and 2.5 Mbps upstream Bandwidth is Dedicated
HFC downstream rates up to 42.8 Mbps and upstream rates of up to 30.7 Mbps Bandwidth is Shared
FTTH 2-10Mbps upload; 10-20 Mbps download bandwidth is not shared

Q10. Describe the most popular wireless Internet access technologies today.

Solution. Following are the wireless Internet access technologies:

  1. Wifi (IEEE 802.11) In a wireless LAN, wireless users transmit/receive packets to/from an base station  (i.e., wireless access point) within a radius of few 10s of meters. The base station is typically connected to the wired Internet and thus serves to connect wireless users to the wired network.
  2. 3G and 4G wide-area wireless access networks. In these systems, packets are transmitted over the same wireless infrastructure used for cellular telephony, which is managed by a telecommunications provider. This provides wireless access to users within a radius of 10s of kilometers of the base station of telecommunication systems (also known as mobile base station).

Section 1.3

Q11. 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.)

Solution. Following is the diagram of the scenario:

               Sender  ——R1——- Switch ——-R2——- Receiver

After ignoring said delays, only transmission delay (Data size/Bandwidth) is effective here.

At time t0 the sending host begins to transmit.

At time t1 = L/R1 , the sending host completes transmission and the entire packet is received at the switch.

Because the switch is store and forwarding type, so further transmission will start after receiving the complete packet, which is completed at time t1 = L/R1 .

 The switch takes transmission time t2 = L/R2 to send complete packet on link R2 . As all other delays are zero.

Total Time taken by packet to travel from sender to receiver is:

 = Time between sender to Switch + Time between switch to receiver

 = t1  + t2 =  L/R1 + L/R2

Thus, the end-to-end delay is L/R1 + L/R2 .

Q12. What advantage does a circuit-switched network have over a packet-switched network? What advantages does TDM have over FDM in a circuit-switched network?

Solution.

  1. A circuit-switched network can guarantee a certain amount of end-to-end bandwidth for the duration of a call. Most packet-switched networks today (including the Internet) cannot make any end-to-end guarantees for bandwidth.
  2. FDM requires sophisticated analog hardware to shift signal into appropriate frequency bands.

Q13.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.)

  1. When circuit switching is used, how many users can be supported?
  2. 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?
  3. Find the probability that a given user is transmitting.
  4. 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.

Solution.

  1. 2 users can be supported because each user requires half of the link bandwidth.
  2. Since each user requires 1Mbps when transmitting, if two or fewer users transmit    simultaneously, a maximum of 2Mbps will be required. Since the available      bandwidth of the shared link is 2Mbps, there will be no queuing delay before the link. Whereas, if three users transmit simultaneously, the bandwidth required will be 3Mbps which is more than the available bandwidth of the shared link. In this case, there will be queuing delay before the link.
  3. Probability that a given user is transmitting = 0.2
  4. Probability that all three users are transmitting simultaneously = (0.2)3 = 0.008 . Since the queue grows when all the users are transmitting, the fraction of time during which the queue grows (which is equal to the probability that all three users are transmitting simultaneously) is 0.008.

Q14.Why will two ISPs at the same level of the hierarchy often peer with each other? How does an IXP earn money?

Solution.

  • If the two Internet Service Providers (ISPs) do not peer with each other, then when they send traffic to each other they have to take services of some intermediary provider ISP, to which they have to pay for carrying the traffic. By peering with each other directly, the two ISPs can reduce their payments to their provider ISPs.
  • An Internet Exchange Points (IXP)  (typically in a standalone building with its own switches) is a  meeting point where multiple ISPs can connect and/or peer together.
  • An IXP earns its money by charging each of the the ISPs that connect to the IXP a relatively small fee, depending on the amount of traffic sent to or received from the IXP.

Q15.Some content providers have created their own networks. Describe Google's network. What motivates content providers to create these networks?

Solution.

  • Google's private network connects its all data centers.
  • Traffic among the Google data centers passes over its private network rather than over the public Internet.
  • In order to reduce the response time Google located its many of data centers close to, lower tier ISPs. By doing so it often can bypass higher tier ISPs while serving user requests.
  • What motivates content providers to create these networks?
    • First, quick response to users, since it has to use few intermediary ISPs.
    • Second, it can save money by sending less traffic into provider networks.
    • Third, if ISPs decide to charge more money to highly profitable content providers  (in countries where net neutrality (Network neutrality, or simplynet neutrality, is the principle that Internet service providers (ISPs) must treat all Internet communications equally, and not discriminate or charge differently based on user, content, website, platform, application, type of equipment, source address, destination address, or method of communication) doesn't apply), the content providers can avoid these extra payments.

Section 1.4


Q16. Consider sending a packet from a source host to a destination host over a fixed route. List the delay components in the end-to-end delay. Which of these delays are constant and which are variable?

Solution.The delay components in the end-to-end delay are:

  • processing delays, time taken by router in processing the packet header. It is a fixed delay.
  • transmission delays = Data size transmitted/ Bandwidth. It is a fixed delay.
  • propagation delays, = Length of path/ Speed of signal in media. It is a fixed delay.
  • queuing delays = time spent in the queue due to congestion or non availability of channel or media. It is a variable delay.

Q17.Visit the Transmission Versus Propagation Delay applet at the companion Web site. Among the rates, propagation delay, and packet sizes available, find a combination for which the sender finishes transmitting before the first bit of the packet reaches the receiver. Find another combination for which the first bit of the packet reaches the receiver before the sender finishes transmitting.

Solution. Do it by yourself.

Q18. How long does it take a packet of length 1,000 bytes to propagate over a link of distance 2,500 km, propagation speed 2.5 · 10^8 m/s, and transmission rate 2 Mbps? More generally, how long does it take a packet of length L to propagate over a link of distance d, propagation speed s, and transmission rate R bps? Does this delay depend on packet length? Does this delay depend on transmission rate?

Solution.

  • Propagation time = distance/speed of signal in media or channel

              = 2500KM/2.5 · 10^8 m/s = 2500*1000 m/(2.5 · 10^8 m/s) = 10 msecond

  • Generally, the Propagation delay = d/s
  • Propagation delay does not depend on packet length and transmission rate.

Q19.Suppose Host A wants to send a large file to Host B. The path from Host A to Host B has three links, of rates R1 = 500 kbps, R2= 2 Mbps, and R3
= 1 Mbps.

  1. Assuming no other traffic in the network, what is the throughput for the file transfer?
  2. 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
  3. Repeat (a) and (b), but now with R2 reduced to 100 kbps.

Solution.       A —-R1(500kbps)—–X——–R2(2Mbps)—–X——-R3(1Mbps)—— B

  1. This is the concept of bottleneck link. Overall throughput will be the least bandwidth in the path between sender and receiver. So, throughput = 500 kbps

  2. File size = 4*10^6 bytes, throughput = 500 kbps=> [4*(10^6)*8]/[500*10^3] = 64 seconds

  3. A —-R1(500kbps)—–X——–R2(100kbps)—–X——-R3(1Mbps)—— B

        Now the bottleneck link is R2 (100kbps). Repeat above calculation with R2 = 100kbps instead of R1 = 500kbps.

Q20. Suppose end system A wants to send a large file to end system B. At a very high level, describe how end system A creates packets from the file. When one of these packets arrives to a packet switch, what information in the packet does the switch use to determine the link onto which the packet is forwarded? Why is packet switching in the Internet analogous to driving from one city to another and asking directions along the way?

Solution.

  • End system A breaks the large file into chunks. It adds header (which contains control information like: IP address of source, destination etc) to each chunk. By doing so sender has created multiple packets from the file.
  • The packet switch uses the destination IP address in the packet's header to determine the outgoing link.
  • Asking which road to take is analogous to a packet asking which outgoing link it should be forwarded on, given the packet's destination address.

Q21. Visit the Queuing and Loss applet at the companion Web site. What is the maximum emission rate and the minimum transmission rate? With those rates, what is the traffic intensity? Run the applet with these rates and determine how long it takes for packet loss to occur. Then repeat the experiment a second time and determine again how long it takes for packet loss to occur. Are the values different? Why or why not?

Solution.Do it by yourself.

Section 1.5

Q22. List five tasks that a layer can perform. Is it possible that one (or more) of these tasks could be performed by two (or more) layers?

Solution.

  • Five tasks performed are:
    1. error control,
    2. flow control,
    3. segmentation and reassembly,
    4. multiplexing, and
    5. connection setup.
  • Yes, one or more of these tasks can be duplicated at different layers. For example, error control is often provided at more than one layer (Transmission Layer and Data Link Layer of OSI Model).

Q23.What are the five layers in the Internet protocol stack? What are the principal responsibilities of each of these layers?

Solution. Below are the five layers in the Internet protocol stack (from top to bottom) –

  1. Application layer: It deals with the application in one end system using the protocol to exchange packets of information with the application in another end system
  2. Transport layer: It transports application-layer messages between
    application endpoints. It deals with application on sender side to application on receiver side. Also called as point-to-point delivery.
  3. Network layer: It is responsible for moving network-layer packets
    known as datagrams from one host to another using IP addresses. It also contains routing protocols information.
  4. Link layer: It is responsible for Hop-to-Hop data delivery. The network layer routes a datagram through a series of routers between
    the source and destination. To move a packet from one node (host or router) to the next node in the route, the network layer relies on the services of the link layer. In particular, at each node, the network layer passes the datagram down to the link layer, which delivers the datagram to the next node along the route. At this next node, the link layer passes the datagram up to the network layer
  5. Physical layer: While the job of the link layer is to move entire frames from one network element to an adjacent network element, the job of the physical layer is to move the individual bits within the frame from one node to the next. Physical layer deals with the physical media.

Q24.What is an application-layer message? A transport-layer segment? A network layer datagram? A link-layer frame?

Solution.

  • Application-layer message: data which an application wants to send and passed onto the transport layer; It is the user message, also called as raw data.

  • Transport-layer segment: generated by the transport layer and encapsulates application-layer message with transport layer header;

  • Network-layer datagram: encapsulates transport-layer segment with a network-layer header; also known as a packet

  • link-layer frame: encapsulates network-layer datagram with a link-layer header.

Q25. Which layers in the Internet protocol stack does a router process? Which layers does a link-layer switch process? Which layers does a host process?

Solution.

  • Routers process: Router is network layer device, which is capable of processing header information of network, link and physical layers.

  • Link layer switches: can process link and physical layers header information.

  • Hosts can process all five layers.

Section 1.6
Q26. What is the difference between a virus and a worm?

Solution.

  • Virus: they requires some form of human interaction to replicate or spread. Classic example: Spam or E-mail viruses.

  • Worms: No user interaction needed. Worm in infected host scans IP addresses and port numbers, looking for vulnerable processes to infect.

Q27.Describe how a botnet can be created, and how it can be used for a DDoS attack.

Solution.

  • In order to create a botnet, the attacker first has to find out the vulnerability in some software or application or system (e.g. exploiting the buffer overflow vulnerability that might exist in an application).
  • After finding the vulnerability, the attacker needs to scan for hosts that are vulnerable.
  • The target is to attack or compromise a series of systems by exploiting or attacking that particular vulnerability.
  • Any system that is part of the botnet can automatically scan its environment and propagate by exploiting the vulnerability.
  • An important property of such botnets is that the originator of the botnet can remotely control and issue commands to all the nodes in the botnet.
  • Hence, it becomes possible for the attacker to issue a command to all the nodes, that target a single node (for example, all nodes in the botnet might be commanded by the attacker to send a TCP SYN message to the target, which might result in a TCP SYN flood attack at the target).

Q28. Suppose Alice and Bob are sending packets to each other over a computer network. Suppose Trudy positions herself in the network so that she can capture all the packets sent by Alice and send whatever she wants to Bob; she can also capture all the packets sent by Bob and send whatever she wants to Alice. List some of the malicious things Trudy can do from this
position.

Solution. Trudy can pretend to be Bob to Alice (and vice-versa) and partially or completely modify the message(s) being sent from Bob to Alice. Furthermore, Trudy can even drop the packets that are being sent by Bob to Alice (and vise-versa), even if the packets from Bob to Alice are encrypted.

Problems

Q1.Design and describe an application-level protocol to be used between an automatic teller machine and a bank's centralized computer. Your protocol should allow a user's card and password to be verified, the account balance (which is maintained at the centralized computer) to be queried, and an account withdrawal to be made (that is, money disbursed to the user). Your protocol entities should be able to handle the all-too-common case in which there is not enough money in the account to cover the withdrawal. Specify your protocol by listing the messages exchanged and the action taken by the automatic teller machine or the bank's centralized computer on transmission and receipt of messages. Sketch the operation of your protocol for the case of a simple withdrawal with no errors, using a diagram similar to that in Figure 1.2 of book. Explicitly state the assumptions made by your protocol about the underlying end-to-end transport service

Solution.

Pb1 Ch1 kurose CN

Q2.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.

Equation-1.1-kurose-cn

Equation-1.1

Solution. Transmission time is the time taken by a node to load the data on the channel or link and that is L/R for one node.

For given N links:-

1st packet will reach to destination at time N*(L/R)

The 2nd packet has to wait at sender, until the 1st packet will be transmitted completely (L/R).

So, after reaching the 1st packet at receiver (N*(L/R)), after L/R time 2nd packet will reach to the receiver.

At time N*(L/R) + L/R, the second packet has reached the receiver.

Continuing with this logic, after reaching 1st packet at receiver, after each L/R time next packet will be reaching at receiver.

So, the time required by all the packets to reach the destination is:  =

= 1st packet time + 2nd packet time + 3rd packet time + 4th packet time + …………. + (P-1)th packet time

N*(L/R) + (L/R) + (L/R) + (L/R) …………………..+ (P-1)th time (L/R)

=N*(L/R) + (P-1)*(L/R) = (N+P-1)*(L/R)

Q3. Consider an application that transmits data at a steady rate (for example, the sender generates an N-bit unit of data every k time units, where k is small and fixed). Also, when such an application starts, it will continue running for a relatively long period of time. Answer the following questions, briefly justifying your answer:

  1. Would a packet-switched network or a circuit-switched network be more appropriate for this application? Why?
  2. Suppose that a packet-switched network is used and the only traffic in
    this network comes from such applications as described above. Furthermore, assume that the sum of the application data rates is less than the capacities of each and every link. Is some form of congestion control needed? Why?

Solution.

  1. A circuit-switched network would be well suited to the application, because the application involves long sessions with predictable smooth bandwidth requirements. Since the transmission rate is known and not bursty, bandwidth can be reserved for each application session without significant waste. In addition, the overhead costs of setting up and tearing down connections are amortized over the lengthy duration of a typical application session.
  2. In the worst case, all the applications simultaneously transmit over one or more network links. However, since each link has sufficient bandwidth to handle the sum of all of the applications' data rates, no congestion (very little queuing) will occur. Given such generous link capacities, the network does not need congestion control mechanisms.

Q4. 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.

  1. What is the maximum number of simultaneous connections that can be in progress at any one time in this network?
  2. Suppose that all connections are between switches A and C. What is the maximum number of simultaneous connections that can be in progress?
  3. 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?

Figure-1.13-kurose-CN

Figure-1.13

Solution.

  1. Between the switch in the upper left and the switch in the upper right we can have 4 connections. Similarly we can have four connections between each of the 3 other pairs of adjacent switches. Thus, this network can support up to 16 connections.
  2. We can 4 connections passing through the switch in the upper-right-hand corner and another 4 connections passing through the switch in the lower-left-hand corner, giving a total of 8
  3. Yes. For the connections between A and C, we route two connections through B and two connections through D. For the connections between B and D, we route two connections through A and two connections through C. In this manner, there are at most 4 connections passing through any link.

Q5. Review the car-caravan analogy in Section 1.4. Assume a propagation speed of 100 km/hour.

  1. 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?
  2. Repeat (a), now assuming that there are eight cars in the caravan instead of ten.

Solution.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.

  1. There are ten cars. It takes 120 seconds, or 2 minutes, for the first tollbooth to service the 10 cars. Each of these cars has a propagation delay of 45 minutes (travel 75 km) before arriving at the second tollbooth. Thus, all the cars are lined up before the second tollbooth after 47 minutes. The whole process repeats itself for traveling between the second and third tollbooths. It also takes 2 minutes for the third tollbooth to service the 10 cars. Thus the total delay is 96 minutes.
  2. Delay between tollbooths = 8*12 sec + 45 min =  46 min and 36 sec.

          Total delay =2*(46 min and 36 secs) + 8*12 sec = 94 min and 48 sec.

 Q6. 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.

  1. Express the propagation delay, d_prop, in terms of m and s.
  2. Determine the transmission time of the packet, d_trans, in terms of L
    and R.
  3. Ignoring processing and queuing delays, obtain an expression for the end-to-end delay.
  4. 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?
  5. Suppose d_prop is greater than d_trans. At time t=d_trans, where is the first bit of the packet?
  6. Suppose d_prop is less than d_trans. At time t=d_trans, where is the first bit of the packet?
  7. Suppose s= 2.5 * 10^8, L= 120 bits, and R= 56 kbps. Find the distance m
    so that d_prop equals d_trans.

Solution.

  1. d_prop = m/s seconds.
  2. d_trans = L/R seconds
  3. d_end-to-end = (m/s + L/R) seconds
  4. The bit is just leaving Host A.
  5. The first bit is in the link and has not reached Host B
  6. The first bit has reached Host B
  7. d_prop = d_trans => m/s = L/R => m = L*s/R = 120*(2.5 * 10^8)/(56*10^3) = 536 KM

Q7.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 one 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)?

Solution. A ————————2Mbps ———————B

Consider the first bit in a packet. Before this bit can be transmitted, all of the bits in the packet must be generated. This requires

= 56.8/(64*10^3) = 7msec.

The time required to transmit the packet is

56.8/(2*10^6) = 224 *10^-6 sec.

Propagation delay = 10 msec.

The delay until decoding is

7msec + 224*10^-6 sec + 10msec = 17.224msec

A similar analysis shows that all bits experience a delay of 17.224 msec.

Q8.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.)

  1. When circuit switching is used, how many users can be supported?
  2. For the remainder of this problem, suppose packet switching is used. Find the probability that a given user is transmitting.
  3. Suppose there are 120 users. Find the probability that at any given time, exactly n users are transmitting simultaneously. (Hint: Use the binomial distribution.)
  4. Find the probability that there are 21 or more users transmitting
    simultaneously .

Solution.

  1. Supported users = 3*1000/150 = 20 users
  2. p=0.1 (a user transmits 10% (10 out of 100) of the time =>p= 10/100)

Q9.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.

  1. What is N,the maximum number of users that can be supported simultaneously under circuit switching?
  2. 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.

Solution.

  1. N = 1000000/100 = 10000 users

Q10. Consider a packet of length L which begins at end system A and travels over three links to a destination end system. These three links are connected by two packet switches. Let d_i, s_i, and R_i denote the length, propagation speed, and the transmission rate of link i, for i= 1, 2, 3. The packet switch delays each packet by d_proc. Assuming no queuing delays, in terms of d_i, s_i, R_i, (i= 1,2,3), and L, what is the total end-to-end delay for the packet? Suppose now the packet is 1,500 bytes, the propagation speed on all three links is 2.5 * 10^8 m/s, the transmission rates of all three links are 2 Mbps, the packet switch processing delay is 3 msec, the length of the first link is 5,000 km, the length of the second link is 4,000 km, and the length of the last link is 1,000 km. For these values, what is the end-to-end delay?

Solution. S——-R_1 —-  X ——–R_2 ———X———-R_3 ———-D

 The first end system requires L/R_1  to transmit the packet onto the first link;

The packet propagates over the first link in d_1/s_1 ;

The packet switch adds a processing delay of d_proc;

After receiving the entire packet, the packet switch connecting the first and the second link requires L/R_2  to transmit the packet onto the second link;

The packet propagates over the second link in d_2/s_2 .

Similarly, we can find the delay caused by the second switch and the third link: L/R_3 , d_proc, and d_3/s_3 .

Adding these five delays gives

d_end-to-end = L/R_1 +L/R_2 + L/R_3 + d_1/s_1 + d_2/s_2 + d_3/s_3+ d_proc+ d_proc

 Now, by putting the values into the above equation:

=6 + 6 + 6 + 20+16 + 4 + 3 + 3 = 64 msec.

Q11.In the above problem, suppose R_1 =R_2 =R_3 =R and d_proc= 0. Further suppose the packet switch does not store-and-forward packets but instead immediately transmits each bit it receives before waiting for the entire packet to arrive. What is the end-to-end delay?

Solution. As bits are immediately transmitted, the intermediate nodes (switch or router) does not introduce any transmission delay; Thus,

d_end-to-end = L/R + d_1/s_1 + d_2/s_2+ d_3/s_3

By putting values in question 10, we get

d_end-to-end = 6 + 20 + 16 + 4 = 46 msec.

Q12. A packet switch receives a packet and determines the outbound link to which the packet should be forwarded. When the packet arrives, one other packet is halfway done being transmitted on this outbound link and four other packets are waiting to be transmitted. Packets are transmitted in order of arrival. Suppose all packets are 1,500 bytes and the link rate is 2 Mbps. What is the queuing delay for the packet? More generally, what is the queuing delay when all packets have length L, the transmission rate is R, x bits of the currently-being-transmitted packet have been transmitted, and n packets are already in the queue?

Solution.Given that, at time t_0 a packet is received on switch and at that time, switch is transmitting a packet (half of that is remaining i.e. 750 bytes are remaining). At the same time 4 other packets were also queued  on switch and waiting to be transmitted => The newly arrived packet has 4 and half packet ahead of it. Total data  to be transmitted before newly arrived packet gets its chance to be transmitted = 4.5 *1,500 bytes = 6,750 bytes or 54,000 bits. The rate or bandwidth of transmission = 2 Mbps.

Time taken by these 4 and half packets to be transmitted = 54,000/(2*10^6) = 27msec.

Generally, the queuing delay is = [size of packets ahead of the newly arrived packet/ Bandwidth]  = (nL + (L – x))/R

Q13.

  1. 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?
  2. Now suppose that N such packets arrive to the link every LN/R seconds. What is the average queuing delay of a packet?

Solution.

  1. The Average queuing delay = [delay of 1st pkt +  delay of 2nd pkt ….+ delay of Nth pkt ]/N
    delay of 1st pkt  = 0,
    delay of 2nd pkt = transmission time of 1st pkt =L/R,
    delay of 3rd pkt = transmission time of 1st and 2nd pkts
                                =L/R + L/R = 2L/R,
    delay of nth pkt = transmission time of 1st, 2nd  upto (N-1) pkts
                         =L/R + L/R + . . upto (N-1) times = (N-1)L/R,
    Thus, the average delay for the N packets is: = (N-1)L/(2R)
  2. It takes  L/R seconds to transmit a packet. In a batch there are N packets, so it takes NL/R time to transmit a batch and given that each batch arrives at an interval of NL/R. That is when a new batch arrives it immediately gets link free to transmit (as the previous batch has been transmitted completed in NL/R time).Thus, the average delay of a packet across all batches is the average delay within one batch, i.e., (N-1)L/2R.

Q14.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.

  1. Provide a formula for the total delay, that is, the queuing delay plus the transmission delay.
  2. Plot the total delay as a function of L/R.

Solution.

  1. Transmission delay = L/R, Queuing delay = IL/R(1 – I).
    Total delay = L/R + IL/R(1 – I) = L/(R(1-I))
  2. Let x = L/R, Total delay = L/(R(1-I)) = (L/R)/(1-La/R) = x/(1-ax)
         For x=0, the total delay =0; as we increase x, total delay increases, approaching infinity as x approaches 1/a.

Q15.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 μ.

Solution. Total delay = (L/R)/(1-I)) = (L/R)/(1-La/R) ,
Considering L = a packet = pkt.
Total delay = [pkt/( μ pkt/sec)] / [1-(pkt * a)/ (μ pkt/sec)]
                     = [1/μ] / [1-(a/μ)] = 1/(μ-a) sec.

Q16. 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 denote the average number of packets in the buffer plus the packet being 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?

Solution. N=10+1, (buffer =10, transmitting = 1), Remember that a packet moves to the buffer only when it does not gets the link free, i.e. another packet is being transmitting.
Little's formula is N=a*d,
=> (10+1)=a*(queuing delay + transmission delay).
queuing delay = 10 msec =0.01 sec
Transmission delay  =data/rate = 1 packet / 100 (packets/sec) = 0.01 sec
=> 11=a*(0.01+0.01) = a*(0.02)
=> a=550 packets/sec.  [as N is the number of packets so, unit of N is packets]

Q17.

  1. Generalize Equation 1.2 in Section 1.4.3 for heterogeneous processing rates, transmission rates, and propagation delays.
  2. Repeat (a), but now also suppose that there is an average queuing delay of dqueue at each node.

Solution.

dend-to-end = N(d_proc+d_trans+ d_prop ) …………………. (1.2)

Q18. Perform a Traceroute between source and destination on the same continent at three different hours of the day.

  1. Find the average and standard deviation of the round-trip delays at each of the three hours.
  2. Find the number of routers in the path at each of the three hours. Did the paths change during any of the hours?
  3. Try to identify the number of ISP networks that the Traceroute packets pass through from source to destination. Routers with similar names and/or similar IP addresses should be considered as part of the same ISP. In your experiments, do the largest delays occur at the peering interfaces between adjacent ISPs?
  4. Repeat the above for a source and destination on different continents. Compare the intra-continent and inter-continent results.

Solution. Do it your self.Use "tracert www.studykorner.org" on command prompt in windows or terminal in Linux OS.

Q19.

  1. Visit the site www.traceroute.org and perform traceroutes from two different cities in France to the same destination host in the United States. How many links are the same in the two traceroutes? Is the transatlantic link the same?
  2. Repeat (a) but this time choose one city in France and another city in Germany.
  3. Pick a city in the United States, and perform traceroutes to two hosts, each in a different city in China. How many links are common in the two traceroutes? Do the two traceroutes diverge before reaching China?

Solution. Do it your self.Use "tracert www.studykorner.org" on command prompt in windows or terminal in Linux OS. Use websites hosted in countries said in question.

Q20.Consider the throughput example corresponding to Figure 1.20(b). Now suppose that there are M client-server pairs rather than 10. Denote R_s, R_c, 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 R_s, R_c, R, and M.

Figure 1.2 (b)

Figure 1.2 (b)

Solution. Bottleneck link is of capacity = R, which is shared by M client server pairs,
=> share of each pair  = R/M.
Throughput = min{R s , R c , R/M}

Q21. Consider Figure 1.19(b). Now suppose that there are M paths between the server and the client. No two paths share any link. Path k(k= 1, . . ., M) consists of N links with transmission rates Rk1, Rk2,……….,RkN (where, k is path number and 1,2,…N are the links number between server and client). If the server can only use one path to send data to the client, what is the maximum throughput that the server can achieve? If the server can use all M paths to send data, what is the maximum throughput that the server can achieve?

Figure 1.19 (b)

Figure 1.19 (b)

Solution. Given that there are M paths between server and client. Also No two paths share any link.
Path 1 (for, k=1) = R11, R12,……….,R1N
Path 2 (for, k=2) = R21, R22,……….,R2N

.

.

Path M (for, k=M) = RM1, RM2,……….,RMN
Throughput of each path will be the minimum bandwidth of the link among all the links of that path.
To achieve Maximum throughput, one has to choose the Maximum throughput out of all the available paths.
 = Max{Min{R11, R12,……….,R1N}, Min{R21, R22,……….,R2N}, …….. Min{RM1, RM2,……….,RMN}}
If use all paths, the max throughput is given by:
= Sum(for k=1 to M)[min{R k1 , R k2 ,……….,R kN }

Q22. 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?

Figure 1.19 (b)

Figure 1.19 (b)

Solution. Probability of loss over a link = p
=> probability of successfully receiving a packet over a link is: (1-p)
Suppose, there are two links in the path:- the communication will be successful, when successful transmission over 1st link and successful transmission over 2nd link.
=> (1-p)*(1-p)
Similarly, for N links, for successful transmission of a packet over N links:
= ps= (1-p)N.
Thus, the average number of transmissions needed is given by: 1/ps .
Then, the average number of re-transmissions (for unsuccessful delivery) needed is given by: [1/ps]-1.

Q23.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 Rs 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 dprop .

  1. 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?
  2. Now assume that the second link is the bottleneck link (i.e., Rc <Rs ). 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.

Figure 1_19a

Figure 1.19 (a)

Solution.Assuming the first packet = A and the second packet =B, both are of same size.

  1. Given that the bottleneck link is Rs , the first link. the packet B has to wait in buffer at server till the transmission of packet A completed that is L/Rs . So the packet B will arrive at client after L/Rs time.
  2. Yes, it is possible.
    If the Rc (second) link is the bottleneck link and both packets are sent back to back.
    That is, transmission time for second link is more than that of first link.
    That is, the packet B will arrive at intermediate node before the second link finishes the transmission of the packet A.
    That is, (time taken by B to arrive at intermediate node) < (time taken by A to finish  transmission onto the second link)
            =>         L/Rs + L/Rs + dprop  <  L/Rs + dprop + L/Rc
         T is such that:
             =>       L/Rs + L/Rs + dprop + T >= L/Rs + dprop + L/Rc
                 =>       T >=  [L/Rc ] –  [ L/Rs ]
    Thus, the minimum value of T = L/Rc – L/Rs .

Q24.Suppose you would like to urgently deliver 40 terabytes data from Boston to Los Angeles. You have available a 100 Mbps dedicated link for data transfer. Would you prefer to transmit the data via this link or instead use FedEx overnight delivery? Explain.
Solution. 40 terabytes = 40 * 1012 * 8 bits.
So, if transferring via this link, time =  40 * 1012 * 8 / (100 *106 ) =3200000 seconds = 37 days.
But with FedEx overnight delivery, the delivery can be expected within 5 days.

Q25.Suppose two hosts, A and B, are separated by 20,000 kilometers and are connected by a direct link of R= 2 Mbps. Suppose the propagation speed
over the link is 2.5 *108 meters/sec.

  1. Calculate the bandwidth-delay product, R*dprop .
  2. 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?
  3. Provide an interpretation of the bandwidth-delay product.
  4. What is the width (in meters) of a bit in the link? Is it longer than a football field?
  5. 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

Solution.A ————–2Mbps ——  20,000 KM ———– B
dprop  = 20000 * 1000/(2.5 * 108) = 2/25

  1.  R * dprop = (2*106 )* (2 /25)  = 160,000 bits
  2. Say, time to reach 1st bit from A to B  is T. Within this time interval  bits transmitted, will be the number of bits on the link (between A and B) and given that rate of putting data on the link = R.
    So, in 1 second 2Mb of data is placed on the link, and in this time (dprop ) interval, bits placed on the link =R * dprop
    = (2*10 6 ) * (2 /25)  = 160,000 bits
  3. The bandwidth-delay product of a link is the maximum number of         bits that can be in the link.
  4. The width of a bit can be calculated as:  = length of link /maximum number of bits that can be in the link, so 1 bit is 125 meters long, which is longer than a football field
  5. Propagation delay = m/s, within this time number of bits transmitted    = R * (m/s), so, these many are the bits on the link.
    Bit width = m/ (R * (m/s)) = s/R

Q26. Referring to problem Q25, suppose we can modify R. For what value of R is the width of a bit as long as the length of the link?

Solution. Bit width = s/R
=> 20000 * 1000 = s/R
=>R = 2.5*108/(2*107)
R=12.5 bps

Q27. Consider problem Q25 but now with a link of R= 1 Gbps.

  1. Calculate the bandwidth-delay product, R * dprop .
  2. 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?
  3. What is the width (in meters) of a bit in the link?

Solution.

  1. R * dprop = [1 * 10^9 ] * [20000 * 1000/(2.5 * 108)]
    =  10^9 * 2 / 25 = 8,00,00,000 bits.
  2. 8,00,00,000 bits.
  3. Bit width = 20000 * 1000 / 80000000 = 2/8 = 1/4= 0.25 meter

Q28. Refer again to problem Q25.

  1. How long does it take to send the file, assuming it is sent continuously
  2. Suppose now the file is broken up into 20 packets with each packet containing 40,000 bits. Suppose that each packet is acknowledged by the receiver and the transmission time of an acknowledgment packet is negligible. Finally, assume that the sender cannot send a packet until the preceding one is acknowledged. How long does it take to send the file?
  3. Compare the results from (a) and (b).

Solution.

  1. Total delay = [d trans ]+[ dprop ]                     = [800000 / (2*106)] + [2/25]                     =400 msec + 80 msec = 480 msec.
  2. Total delay for 1 packet =
    transmission time of packet at sender (40000 / (2*106) sec) +
    propagation time of packet from sender to receiver (2/25 sec) +
    transmission time of Acknowledgement at receiver (0 sec) +
    propagation time of Acknowledgement from receiver to sender (2/25 sec)
    =  (d trans + 2 dprop ) = (20 msec + 80 msec).
    For 20 packets total delay = 20 *[Total delay for 1 packet]= 20 * [(d trans + 2 dprop )]
    = 20*[(20 msec + 80 msec)] = 2 sec.
  3. Breaking up a file takes longer to transmit because each data packet and its corresponding acknowledgement packet add their own propagation delays.

Q29. 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 * 108 meters/sec.

  1. What is the propagation delay of the link?
  2. What is the bandwidth-delay product, R*dprop ?
  3. Let x denote the size of the photo. What is the minimum value of x for the microwave link to be continuously transmitting?

Solution.Assuming the distance between geostationary satellite and base station is 36000 KM.

  1. dprop = 36000 *1000 / 2.4 * 108 =36/240 = 3/20 =0.15 sec = 150 msec
  2. R*dprop = 10*106*0.15 = 1500000 bits
  3. It generates a photo every 60 sec.
    That is before generating new photo, the previous photo should be transmitted completely.
    That is the photo should be transmitted within 60 sec.
     => dtrans = 60 = x/10*106 => x = 600000000 bits

Q30. Consider the airline travel analogy in our discussion of layering in Section 1.5, and the addition of headers to protocol data units as they flow down the protocol stack. Is there an equivalent notion of header information that is added to passengers and baggage as they move down the airline protocol stack?

Solution.Let's suppose the passenger and his/her bags correspond to the data unit arriving to the top of the protocol stack (application layer).

  • When the passenger checks in, his/her bags are checked, and a tag containing personal and travel information of its owner is attached to the bags and ticket.
  • This is additional information added in the Baggage layer to implement the service or separating the passengers and baggage on the sending side, and then reuniting them on the destination side.
  • When a passenger then passes through security check, additional stamp is often added to his/her ticket, indicating that the passenger has passed through a security check.
  • This information is used to ensure (e.g., by later checks for the security information) secure transfer of people.

Q31.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 message segmentation. Consider a message that is 8 * 106 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.

  1. 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-and-forward packet switching, what is the total time to move the message from source host to destination host?
  2. 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?
  3. 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.
  4. In addition to reducing delay, what are reasons to use message segmentation?
  5. Discuss the drawbacks of message segmentation.

Figure 1.27

Solution.

  1. Time to send message from source to first switch =8*106 / 2*106=4 sec Total time to move message from source to destination = transmission time at source + at 1st switch + at 2nd switch = 3[8*106 / 2*106]=12 sec
  2. Time to send 1st packet from source host to first packet switch =10000/2*106=5 msec.  Time at which 2nd packet is received at the first switch = 2*5msec =10 msec (as it is transmitted when 1st packet starts transmitting at first switch, so delay = [transmission time of 1st at source + that of 2nd packet at source time at which 1st packet is received at the second switch])
  3. Time at which 1st packet is received at the destination host = 5 msec * 3 hops = 15 msec.. After this, every 5 msec (transmission time of a packet) one packet will be received at destination, thus time at which last (800th) packet is received = 15 msec + 799 * 5 msec = 4.01 sec. It can be seen that delay in using message segmentation is significantly less (almost 1/3rd).
    1. Without message segmentation, if bit errors are not tolerated, if there is a single bit error, the whole message has to be re-transmitted (rather than a single packet).
    2. 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.
    1. Packets have to be put in sequence at the destination.
    2. 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.

Q32. Experiment with the Message Segmentation applet at the book's Web site. Do the delays in the applet correspond to the delays in the previous problem? How do link propagation delays affect the overall end-to-end delay for packet switching (with message segmentation) and for message switching?

Solution. Do it by yourself.

Q33. 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.

Solution. A ———Switch1 ——— Switch2 ———– B
Number of packets = F/S. Packet size (S) =80 bits.
Time at which the last packet is received at the Switch1=[(S+80)/R]*[F/S] sec.
At this time, the first F/S-2 packets are at the destination, and the F/S-1 packet is at the Switch2.
The last packet must then be transmitted by the Switch1 and the Switch2, with each transmission taking (S+80)/R sec.
Thus delay in sending the whole file is [(S+80)/R]*[(F/S) + 2] sec
To calculate the value of S which leads to the minimum delay, = differentiate and equate to zero.
=> d/dS  (delay) = 0 => S = sqrt(40F)

Q34.Skype offers a service that allows you to make a phone call from a PC to an ordinary phone. This means that the voice call must pass through both the Internet and through a telephone network. Discuss how this might be done.

Solution. In this system Gateways are responsible for conversion message of message between voice signal and voice packets.

  • The circuit-switched telephone networks and the Internet are connected together at "gateways".
  • When a Skype user (connected to the Internet) calls an ordinary telephone, a circuit is established between a gateway and the telephone user over the circuit switched network.
  • The skype user's voice is sent in packets over the Internet to the gateway.
  • At the gateway, the voice signal is reconstructed and then sent over the circuit.
  • In the other direction, the voice signal is sent over the circuit switched network to the gateway.
  • The gateway packetizes the voice signal and sends the voice packets to the Skype user.