d

{
 "metadata": {
  "name": "",
  "signature": "sha256:dac4c1e908e671b2f9222884d3ed013270055d3ad43e784cf7526efb5a2fd0a4"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Saul Shanabrook\n",
      "COSC 465: Computer Networking<br>\n",
      "Spring 2015<br>\n",
      "Homework 6: Transport Layer<br>\n",
      "Due: 1 April 2015, 11:55:59pm (this is not an april fool's joke \ud83d\ude1e)<br>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To run use [my iPython docker image](https://github.com/saulshanabrook/ipython)\n",
      "    "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> #1)\n",
      ">  Suppose a congestion-control scheme results in a collection of competing flows that achieve the following throughput rates: 200 KB/s, 160 KB/s, 110 KB/s, 95 KB/s, and 150 KB/s."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "flows = [200, 160, 110, 95, 150]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## a)\n",
      "> Compute the Jain fairness index for these flows (see slides for formula)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from fn import _ as X\n",
      "from __future__ import division\n",
      "\n",
      "def fairness(flows):\n",
      "    n = len(flows)\n",
      "    return sum(x)**2/(n*sum(map(X**2, x)))\n",
      "\n",
      "print 'Answer is {}'.format(fairness(flows))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Answer is 0.936095216297\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ##b)\n",
      "> Assume a flow with throughput 1000 KB/s is added.  What is the new fairness index?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "flows.append(1000)\n",
      "print 'Answer is {}'.format(fairness(flows))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Answer is 0.780079346914\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> #2)\n",
      "> Two users, one using ssh (virtual terminal application which uses TCP) and one sending files with FTP (which uses TCP for delivering large files), both send their traffic out via router R.  The outbound link from R is slow enough that both users keep packets in R's output queue at all times.  Discuss the relative performance seen by the ssh user if R's queuing policy for these two flows is:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## a)\n",
      "> Round-robin service"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Since round-robin is irrespective of packet size, the ssh user would see less overall throughput than the FTP user, because it's packets would usually be not as large, since it is only sending small text commands"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## b)\n",
      "> fair queueing "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Fair queueing would give each around the same bandwith, so would give better treatment to the ssh user, by allowing them to send more small packets"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> # 3)\n",
      ">(P40 in the text, page 296).  Consider the figure below.  Assuming TCP Reno is the protocol experiencing the behavior shown, answer the following questions, briefly justifying each answer.\n",
      "![](https://www.dropbox.com/s/96ppusujlvte5om/image00.png?dl=1)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## A.\n",
      "> Identify intervals of time when TCP slow start is operating."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* 1-6\n",
      "* 23-26\n",
      "\n",
      "This is when expenonetial window size growth occurs"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ##B.\n",
      "> Identify intervals of time when TCP congestion avoidance is operating."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* 6-16\n",
      "* 16.5-22\n",
      "\n",
      "This is when linear window size growth occurs"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## C.\n",
      "> After the 16th transmission round, is segment loss detected by a triple-duplicate ACK or by a timeout?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It only reduced the windows size by half, so it was still in the congestion avoidance phase, which means it detected a **triple duplicate ACK**."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## D.\n",
      "> After the 22nd transmission round, is segment loss detected by a triple-duplicate ACK or by a timeout?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It  reduced the windows size to 0, so it reverted to the slow start phase, which means it detected a **timeout**."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## E. \n",
      "> What is the initial value of ssthresh at the first transmission round?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "32.5\n",
      "\n",
      "When window size exceeds this threshold, it goes to congestion avoidance"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ##F.\n",
      "> What is the value of ssthresh at the 18th transmission round?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "21.25\n",
      "\n",
      "When the triple duplicate ACK was recieved the threshold was changed to half the current window size of 42.5"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## G.\n",
      "> What is the value of ssthresh at the 24th transmission round?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "14.5\n",
      "\n",
      "When the timeout happened the threshold was changed to half the current window size of 29"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## H.\n",
      "> During what transmission round is the 70th segment sent?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# transmission round 6 goes up to...\n",
      "1+2+4+8+16+32"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "63"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# transmission round 7 goes up to...\n",
      "1+2+4+8+16+32+33"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "96"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Round **7**"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## I.\n",
      "> Assuming a packet loss is detected after the 26th round by the receipt of a triple-duplicate ACK, what will be the values of the congestion window size and of ssthresh?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "previous_window_size = 8\n",
      "window_size = ssthresh = previous_window_size / 2\n",
      "print \"Window size = ssthresh = {}\".format(window_size)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Window size = ssthresh = 4.0\n"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> # 4)\n",
      "> Assume that TCP implements an extension that allows window sizes much larger than 64 KB.  Suppose that you are using this extended TCP over a 1 Gb/s link with a latency of 50 milliseconds to transfer a 10 MB file, and the TCP receiver window is 1 MB.  If TCP sends 1 KB packets (assuming no congestion and no lost packets):"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pint import UnitRegistry\n",
      "\n",
      "u = UnitRegistry()\n",
      "file_size = 10 * u.megabyte\n",
      "packet_size = u.kilobyte\n",
      "number_packets = int(file_size / packet_size)\n",
      "reciever_window = u.megabyte\n",
      "packets_in_reciever_window = int(reciever_window / packet_size)\n",
      "latency = 50 * u.milliseconds\n",
      "link_throughput = u.gigabit/u.second"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ##a)\n",
      "> How many RTTs does it take until slow start opens the send window to 1 MB?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rtts = 1 # for two way handshake\n",
      "send_window = 1 \n",
      "while send_window * packet_size < u.megabyte:\n",
      "    rtts += 1\n",
      "    send_window *= 2\n",
      "print 'It would take {} rtts'.format(rtts)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "It would take 11 rtts\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ##b)\n",
      "> How many RTTs does it take to send the file?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "window_size = 1\n",
      "rtts = 1 # for two way handshake\n",
      "while number_packets > 0:\n",
      "    number_packets -= min([window_size, packets_in_reciever_window])\n",
      "    window_size *= 2\n",
      "    rtts += 1\n",
      "rtts += 1 # for teardown\n",
      "print 'It would take {} rtts'.format(rtts)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "It would take 21 rtts\n"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> #c)\n",
      "> If the time to send the file is given by the number of required RTTs multiplied by the link latency, what is the effective throughput for the transfer?  What percentage of the link bandwidth is utilized?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "time_to_send = rtts * latency\n",
      "throughput = file_size / time_to_send\n",
      "print 'throughput is {}'.format(throughput.to(u.gigabit/u.second))\n",
      "print '{} percent of the link bandwith is utilized'.format(100 * float(throughput/link_throughput))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "throughput is 0.0761904761905 gigabit / second\n",
        "7.61904761905 percent of the link bandwith is utilized\n"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> # 5)\n",
      "> You are hired to design a reliable byte-stream protocol that uses a sliding window (like TCP).  This protocol will run over a 1 Gb/s network.  The RTT of the network is 100 milliseconds, and the maximum segment lifetime is 30 seconds. \n",
      "\n",
      "> How many bits would you include for the AdvertisedWindow and SequenceNumber fields of your protocol header?  Briefly justify your answer."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So the advertised window is for the maximum number of packets each side will allow in the window at once. It is for flow control. If this (times packet size)  is less than the bandwith delay product, then the network can never be fully utilized. So Let's set it equal, so that it can be. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "\n",
      "bandwidth = u.gigabit/u.second\n",
      "delay = 100 * u.millisecond\n",
      "max_window = (bandwidth * delay).to(u.bit)\n",
      "print 'The maximum window size should be {}'.format(max_window)\n",
      "print 'the number of bits to represent this is {}'.format(math.log(max_window.magnitude, 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The maximum window size should be 100000000.0 bit\n",
        "the number of bits to represent this is 26.5754247591\n"
       ]
      }
     ],
     "prompt_number": 42
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There have to be enough sequence numbers so that when they wrap, you won't be worried about getting a sequance number from the old packet from the first time around."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "maximum_segment_lifetime = 30 * u.second\n",
      "min_number_sequences = float(maximum_segment_lifetime / delay)\n",
      "print 'We shoud have at least {} sequence numbers'.format(min_number_sequences)\n",
      "print 'so there needs to be at least {} bits to represent sequence numbers'.format(math.log(min_number_sequences, 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "We shoud have at least 300.0 seequence numbers\n",
        "so there needs to be at least 8.2288186905 bits to represent sequence numbers\n"
       ]
      }
     ],
     "prompt_number": 43
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> # 6\n",
      "> Is it possible for TCP Reno to reach a state in which the congestion window size much larger than RTT x bandwidth (e.g., twice as large)?  Is it likely?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Yes it is possible, for a short period of time. The RTT * bandwdth is the maximum amount of data in the network at once. If it worked out just right, TCP could get back all that data, that was previously fully saturating the network, and double their window size (if the ssthresh is set to a large value), and wouldn't know it had oversaturated the network until it got dropped packets or a timeout, shortly after"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> # 7\n",
      "> Suppose a TCP connection, with window size of 1, loses every other packet.  Those that do arrive have RTT = 1 second.  What happens?  What happens to the retransmission timeout (RTO) value?  Consider these questions for two separate cases:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> ## a.\n",
      "> After a packet is eventually received, we pick up where we left off, resuming with EstimatedRTT initialized to its pre-timeout value, and a Timeout value of double that.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So the first packet is sent and recieved back, with a RTT of 2 seconds. So the EstimatedRTT gets set to 2 seconds and the timouet is 4 seconds. Then the second packet is sent and lost. The server waits 4 seconds and sends the first packet, and both value stay the same. Then it gets that packet back in two seconds and again everything stays the same. Then the server sends again and times out. It all keeps repeating."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      ">## b.\n",
      ">After a packet is eventually received, we resume with the Timeout value initialized to the last exponentially backed-off value used for the timeout interval.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So the first packet is sent and recieved back, with a RTT of 2 seconds. So the EstimatedRTT gets set to 2 seconds and the timeout is 4 seconds. Then the second packet is sent and lost. The server waits 4 seconds and sends the first packet. The timeout is now 8 seconds and the EstimatedRTT is 4 seconds. Then it gets that packet back in two seconds and everything stays the same. Then the server sends again and times out. This increase the timeout to 16 seconds."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}