Computer Networking

Homework 3, 9 October 2012

This homework assignment has five questions; answer all of them. This assignment is due no later than 9:00 p.m. on Thursday, 18 October.

If you mail in your assignment, please submit a printable document — a PostScript .ps or PDF .pdf document, for example — and not a source document — a Word .docx or Latex .tex document, for example.

  1. For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16.

    Given 163 < 16217 < 4,800 < 173, assume each node has 17 routers. Because 173 - 4,800 = 113 < 172, the nodes with fewer routers are at the bottom level.

    The answers, approximately verbatim, and in no particular order:

    1. Let us assume that x refers to clusters, y refers to regions, and z refers to routers.

      Min (x - 1) + (y - 1) + z While (x.y.z) >= 4800 | X | Y | Z | (x - 1) + (y - 1) + z | X.Y.Z. | 16 | 15 | 20 | 49 | 4800 | 15 | 16 | 20 | 49 | 4800 | 17 | 18 | 16 | 49 | 4896 | 18 | 16 | 17 | 49 | 4896 | 17 | 16 | 18 | 49 | 4896 | 16 | 17 | 18 | 49 | 4896 | 16 | 18 | 17 | 49 | 4896

      X = 16, Y = 15, Z = 20 and X = 15, Y = 16, Z = 20 are the minimum values that occur. For that, the table size is going to be 16 + 15 + 20 and that is 51. (Tanenbaum A., Computer Networks, Chapter 5).

    2. A) Assume that there are 'a' clusters, 'b' regions in each region and 'c' routers per region.

      The formula to minimize is (a - 1) + (b - 1) + c.

      While abc >= 4800.\ The possible solutions by trial and error1 are 1 a = 17, b = 18, c = 16 \ By the formula (a - 1) + (b - 1) + c = 17 + 18 + 16 = 51 1 a = 17, b = 17, c = 17 \ By the formula (a - 1) + (b - 1) + c = 17 + 17 + 17 = 51 1 a = 18, b = 16, c = 17 \ By the formula (a - 1) + (b - 1) + c = 18 + 16 + 17 = 51 1 a = 16, b = 18, c = 17 \ By the formula (a - 1) + (b - 1) + c = 16 + 18 + 17 = 51 1 a = 17, b = 17, c = 17 \ By the formula (a - 1) + (b - 1) + c = 17 + 17 + 17 = 51 1 a = 16, b = 17, c = 18 \ By the formula (a - 1) + (b - 1) + c = 16 + 17 + 18 = 51

      1: But which one is the best solution?

    3. The minimum occurs at 15 clusters, each with 16 regions, each region having 20 routers, or one of the equivalent forms, e.g., 20 clusters of 16 regions of 15 routers. In all cases the table size is 15 + 16 + 20 = 51.

      Reference: Computer Networks by Tanenbaum & Wetherall
    4. (cluster)(regions)(routers) = 4800 \ K is about the cube root of 4800 \ So each k is around 16

      16 times 16 times 16 = 4096 -> a little too small \ 16 times 18 times 18 = 5184 -> too big \ 16 times 17 times 15 = 4080 -> too small \ 17 times 17 times 18 = 4896 -> almost \ 16 times 16 times 19 = 4864 -> almost \ 16 times 15 times 20 = 4800

    5. Using trial and error, 15 clusters of 20 regions of 16 routers a piece will yield 4800 routers in the three-tier hierarchical routing system. These numbers are all in the general vicinity of 16, which means that this solution is close to optimal according to the hypothesis mentioned in the question.
    6. Let's suppose that there are unknown (x) clusters, (y) regions per cluster, and (z) routers per region.

      The minimum size of the routing table for a three-layer is (x - 1) +, and multiply xyz ≥ 4800 in each other is close enough to the total routers.

      The answer would be:

      | x | y | z | (x - 1) + (y - 1) + z | 17 | 17 | 17 | 49 | 18 | 17 | 16 | 49 | 17 | 18 | 16 | 49 | 18 | 16 | 17 | 49 | 17 | 16 | 18 | 49 | 16 | 17 | 18 | 49 | 16 | 18 | 17 | 49

    7. Let us assume there are:

      'a' clusters, \ 'b' regions per cluster, and \ 'c' routers per region.

      Now, \ Given that, \ Since abc ≥ 4800 \ The min size of the routing table is (1 - 1) + (b - 1) + c \ and the nearest cube root of 4800 is 16 \ Hence according to trial and error method we get,

      | A | B | C | (a - 1) + (b - 1) + c | 17 | 17 | 17 | 49 | 18 | 17 | 16 | 49 | 17 | 16 | 18 | 49 | 16 | 17 | 18 | 49 | 16 | 18 | 17 | 49 | 17 | 18 | 16 | 49 | 18 | 16 | 17 | 49

      Hence the three parameters in the general vicinity of 16 are 16, 17, and 18.
  2. A token bucket scheme is used for trafic shaping. A new token is put into the bucket every 5 μsec. Each token is good for one 48-byte packet. What is the maximum transmission rate?

    Adding a tokens to the bucket every 5 usec puts (1/5 tkn/usec)(106 usec/sec) = 2×105 tkn/sec. If each token represents 48 bytes, the transmission rate is (2×105 tkn/sec)(48 bytes/tkn) = 9.6 Mbytes/sec.

    The answers, approximately verbatim, and in no particular order:

    1. Maximum Transmission rate = Time(max) times max rate in bytes/second \ = 5 sec times 48 bytes \ = 240 bytes/second
    2. Given \ A token is put into a bucket every 5 usec, \ So for 1 sec = 200000 tokens/sec can be sent \ Now each token has 48 data bytes or 48*8 = 384 bits Hence now the maximum transmission rate is = no of tokens/sec*484 bits = 200000*384 = 76800000 bits/sec = 76.8 Mbits
    3. Given = A new token for every 5 usec = 2*10 sup 5 tokens/sec = 200,000 tokens/sec can be sent = Each token holds 48 bytes packet = 48*8 bits = 384 bits = Maximum transmission rate is = 200,000 tokens/sec * 384 bits = 76,800,000 bps = 76.8 Mbps
    4. Given that each token is put into the bucket for 5 usec \ Each token is good for 48-byte packet.

      For 1 sec there are 200,000 tokens.\ As each byte has 8 bits, 48 bytes have = 384 bits

      Transmission rate = number of tokens/sec times number of bits per token. 200,000 times 384 = 76.8 mbps.
    5. With a token ever 5 usec 200,000 cells/sec can be sent. \ Each cell holds 48 data bytes = 384 bits. The maximum transmission is = 384 * 2 * 10 sup 5 = 76.8 Mb/s.
    6. 48 bytes per token essentially equates 48 bytes per 5 usec. There are 1,000,000 microseconds in a second, which means that there are 200,000 groups of 5 microseconds in one second (the amount of time that it takes a new token to be introduced). 200,000 groups of usec multiplied by 48 bytes per group = 9,600,000 bytes per second.
    7. The maximum transmission rate limits how fast packets may be sent back to back from the host. Consider that if the token bucket is full, it is possible for the flow to send a series of back-to-back packets equal to the size of the token bucket. If the token bucket size is large, this is back-to-back run may be long enough to significantly inhibit multiplexing.1

      The maximum transmission rate is the rate at which the bucket is emptied. The field2 is in the general field format and indicates the size of the bucket in bytes. The value must be a number and must be greater than or equal to the token bucket rate.

      To determine the maximum transmission rate we should:

      Convert from byte to bit (multiply by 8)3 \ Convert from microsecond to second (multiply by 10 sup -6)

      5 usec = 48 times 8 times 10 sup 3 bits.

      1 sec = (48 times 8 times 10 sup 3) / 10 times 10 sup -6

      1 sec = 38.4 times 10 sup 9 -> 38.4 Gbps

      The maximum transmission rate is 38.4 Gbps

      (source: rfc 1363)

      1: First, the question asks about the undifferentiated maximum transmission rate. Because it doesn't matter which senders contribute to the maximum, multiplexing doesn't seem to be relevant to this question. Second, a back-to-back run of any size has at best an indirect effect on multiplexing: all the packets in the run could come from one sender, but it could also be that each packet in the run comes from a different sender. The choice of senders getting tokens from the bucket has nothing to do with the bucket, but has to do with a scheduler elsewhere in the network subsystem.

      2: Field? What is the field?

      3: Multiply what by 8?

  3. Convert the IP address whose hexadecimal representation is C22F1582 to dotted decimal notation.

    C22F1582 base 16 is 194 047 021 130 base 256, represented as 194.47.21.130 in dotted-quad notation. 194 base 10 is 11000010 base 2, indicating a class C IP address. See also.

    The answers, approximately verbatim, and in no particular order:

    1. C22F1582 in hexadecimal is broken up to be C2.2F.15.82. C in hex equals 12 in decimal. 12 in decimal equals 1100 in binary. 2 in hex equals 2 in decimal, which equals 0010 in binary. The first portion of the hexadecimal IP address in dotted decimal is 11000010 (binary) converted to decimal, which is 194. Following a similar sequence of conversions, F2 in hex becomes 00101111 in binary, which translates to 47 in decimal. 15 in hex becomes 00010101 in binary, which is 21 in decimal. 82 in hex becomes 10000010 in binary, which is 130. The final answer is 194.47.21.130 (in dotted decimal).
    2. C22F1582 = C2.2F.14.82 = 194.47.21.130 \ This address is in a class C network. (Class C networks are those between 192.0.0 and 223.255.255.255). The network is 194.47.21.0 and the host number is 130.
    3. Hexadecimal representation is broken down into 4 sets of 2.

      C2-2F-15-82 = 11000010.00101111.00010101.10000010 = 194.47.21.130

      SOURCE: http://technet.microsoft.com/en-us/library/bb726995.aspx \ http://technet.microsoft.com/en-us/library/cc786995(v=ws.10).aspx
    4. Given Hexadecimal representation if IP address is C22F1582 \ Hexadecimal value: C2 2F 15 82 \ Binary value: 1100 0010 0010 1111 0001 0101 1000 0010 \ Decimal Value: 194 47 21 130 Dotted decimal notation is 194.47.21.130

    5. To convert a hexadecimal IP address to dotted decimal notation we need to do two conversion steps:

      1 Convert from hex to binary 1 Convert from binary to decimal notation.

      Conversion Hex to Binary:1

      | Hex | Binary | | 0 | 0000 | | 1 | 0001 | | 2 | 0010 | | 3 | 0011 | | 4 | 0100 | | 5 | 0101 | | 6 | 0110 | | 7 | 0111 | | 8 | 1000 | | 9 | 1001 | | 10 | 1010 | | 11 | 1011 | | 12 | 1100 | | 13 | 1101 | | 14 | 1110 | | 15 | 1111 | |2 Conversion Table

      C22F1582 in hex equals \ 11000010001011110001010110000010 in binary

      Convert from Binary to Decimal:

      With dotted decimal notation, each 32-bit address numbers is viewed as four distinct groupings of 8 bits Each of the four groupings of 8 consecutive bits is referred to as an octet. (source: HTTP://technet.microsoft.com/enus/library/cc786995%28v=2s.10%29.aspx)

      | 11000010 | 00101111 | 0010101 | 10000010 | | 128 + 64 + 2 | 32 + 8 + 4 + 2 + 1 | 16 + 4 + 1 | 128 + 2 |

      As a result, C22F1582 in hexadecimal equals \ 194.47.21.130 in decimal notation.

      1: Not necesary

    6. Given, \ The IP address hexadecimal representation is C22F1582 \ Since the dotted decimal notation consists of 4 parts which means 4 bytes i.e. 32 bits \ hence the hexadecimal representation can be divided into 4 parts i.e. C2-2F-15-82 \ Now

      C2=11000010 2F=00101111 15=00010101 82=10000010

      Now the combined notation is,

      11000010.0010101.00010101.10000010 = 194.47.21.130

      Hence the dotted decimal notation is 194.47.21.130
    7. A) As IP address has 4 parts. The hexadecimal address is divided into 4 sections as follows

      C2-2F-15-82 \ Now expanding the hexadecimal to binary form, we get. 11000010-00101111-00010101-10000010 \ The decimal equivalent of the above binary form is 194.47.21.130.

  4. Describe a way to reassemble IP fragments at the destination.

    Assuming an IP packet, a receiver assembling fragments has to 1) recognize fragments, 2) buffer fragments for reassembly into a packet, and 3) determine how received fragments effect the sequence number acknowledged. Recognizing fragments can be done with the identifier and more-fragments bit in the header. Fragment buffering can be handled easily and flexibly with a queue array indexed by fragment identifier and each queue ordered by fragment offset. Acknowledgments can ignore partially assembled packets, but it may be helpful to acknowledge fragments extending the received-byte sequence number.

    The answers, approximately verbatim, and in no particular order:

    1. Place fragments in buffer at destination in the right place for reassembly, even if the fragments arrive out of order.

      SOURCE: Tenenbaum page 434
    2. Fragments that travel can arrive out of order and get missing. At this time retransmission takes place and the datagram may get fragmented into different-sized fragments.

      So at this stage till the last fragment arrives the total size is not known, since the total size information is not known in any fragment hence the only indication is the last fragment will not contain the more fragment (mf) bit set.

      Hence the only way to handle the reasembling of the IP fragments is to buffer the pieces till the last one arrives.1 Once they arrive build a buffer based on the size information that can be extracted and then put the fragments into the buffer.

      For tracking the bytes that are present or absent a bit map is used. But in a general phenomenon this process is difficult.2

      1: Or treat the fragments as if they were packets and use existing buffering, if any.

      2: It may be inefficient in terms of space used, but why would it be difficult?

    3. When a destination host receives a series of datagrams from the same source, it needs to determine if any of these datagrams are fragments of some “original” bigger datagram. If it does determie that some datagrams are fragments, it must further determine when it has received the last fragment and how the fragments it has received should be pieced back together to form the original datagram. To allow the destination host to perform these reassembly tasks, the designers of IP (version 4) put identification number, flag and fragmentation fields in the IP datagram. When a datagram is created, the sending host stamps the datagram with an identification number as well as a source and destination address. The sending host increments the identification number for each datagram it sends. When a router needs to fragment a datagram, each resulting datagram (i.e., “fragmennt”) is stamped with the source address, destination address and identification number of the original datagram. When the destination receives a series of datagrams to determine which of the datagrams are actually fragments of the same bigger datagram. Because IP is an unreliable service, one or more of the fragments may never arrive at the destination. For this reason, in order for the destination host to be absolutely sure it has received the last fragment of the original datagram, the last fragment has a flag bit set to 0 whereas all the other fragments have this flag bit set to 1. Also, in order for the destination proper order, the offset field is used to specify where the fragment. Furthermore, the total size is not known until the last fragment arrives and the size is known. Then build a buffer of the right size, and put the fragment in to the buffer. \ Reference: Computer Networking Kurose and Ross
    4. In many cases, fragments might arrive out of order or might not arrive. On a retransmission, the datagram may be fragmented into different-sized fragments. The total size is also not known until the last fragment arrives. Since this “total size” information is not included in any fragment (the only indication is that the last fragment will not have the mf bit set).

      To get rid of that issue, we need to build a buffer which is based on the size of the information that can be derived. Then we can use a bit map to track bytes. (Tanenbaum A., Computer Networks, Chapter 5)

    5. IP fragments each contain the same packet id3 so that they can be grouped in the same buffer upon receipt at the destination.4 These fragments can then be reassembled after all of the packets are received (or if a timer expires, which would tell the recipient that it should not expect any more packets5).

      3: Fragment identifier.

      4: But is the fragment-identifier field always valid?

      5: Does such a timer exist on the receiver side? Sounds difficult to set up. Also, how does the receiver respond when the timer goes off?

    6. The only way6 to reassemble IP fragments at the destination is to bufer all pieces until the last one arrives by building a buffer based on the size of information that can be extracted and putting the fragments into the buffer beccause during the retransmission the total size is unknown until the last fragment arrives, also, the datagram may be fragmented into different size of fragments.7

      6: Really? The only way? Why is that?

      7: Yes? And why is that important?

    7. At the destination the IP fragments arrive at different order or some can be missing. As the total size is also not included in any fragment,8 the bit which doesn't has mf bit set is the last fragment.

      By building a buffer from which the size of information is extracted, we can put all the fragments and a bit map can be used to track the presence and absence of bytes. This is complete when all the bits in the bitmap are 1.

      8: The total size of what? The original unfragmented packet? If so, how is that any different from not including the size of the entire data transfer in each packet?

  5. Write a function to do forwarding in an IP router. The procedure has one parameter, an IP address. It also has access to a global table consisting of an array of triples. Each triple contains three integers: an IP address, a subnet mask, and the output line to use. The function looks up the IP address in the table using CIDR and returns the line to use as its value.

    Assume the subnet mask specifies the CIDR prefix for the entry. 

    int look-up(int ipa)

  out-line = default-out-line
  prefix-size = 0

  for each entry in look-up-table
    if ipa & entry.mask == entry.prefix and prefix-size < entry.mask.size
      prefix-size = entry.mask.size
      out-line = entry.out-line

  return out-line

This is a simple algorithm, but impractically inefficient.

    The answers, approximately verbatim, and in no particular order:

    1. The function receives as an input parameter the buffer skb associated with the packet; the necessary information is inside that structure. skp->dst, the routine information, was initialized by the call to ip_route_input in ip_rcv_finish earlier in the code path.

      int ip_forward(struct sk_buff * skb)

      If there is no Router_Alert option in the header, or if it is present but no interested processes are running (in which case ip_call_ra_chain) return FALSE), ip_forward continues:1 

        if (IPCB(skb)->opt.router_alert && ip_call_ra_chain(skb))
    return NET_RX_SUCCESS

  if (skb->pkt_type != PACKET_HOST)
    goto drop

  skb->ip_summed = CHECKSUM_NONE

  if (iph->ttl <= 1)
    goto too_many_hops

  rt = (struct rtable *) skb->dst;
  if (opt->is_strictroute && rt->rt_dst != rt->rt_gateway)
    goto sr_failed

  if (skb_cow(skb, LL_RESERVED_SPACE(rt->u.dst.dev) + rt->u.dst.header_len))
    goto drop

  ip_decrease_ttl(iph)

  if (rt->rt_flags & RTCF_DOREDIRECT && !opt->srr)
    ip_rt_send_redirect(skb)

  skb->priority = rt_tos2priority(iph->tos)

  return NF_HOOK(
    PF_INET, NF_IP_FORWARD, skb, skb->dev, rt->u.dst.dev, ip_forward_finish)

      The packet is finally transmitted with dst_output given below: 

        static inline int ip_forward_finish(struct sk_buff * skb)
  {
    struct ip_options * opt = &(IPCB(skb)->opt)

    IP_INC_STATUS_BH(IPSTATS_MIB_OUTFORWARDDATAGRAMS)

    if (unlikely(ipt->optlen) {
      ip_forward_options(skb)

    return dst_output(skb)
  }

      Reference:\ http://www.civilnet.cn/book/kernel/Understanding%20Linux%20Network%20Internals/understandIni-CHP-20-SECT-1.html

      1: Does this handle CIDR?

    2. [ not answered ]
    3. [ not answered ]
    4. IP Packet Validation: The router must check that the received packet is properly formed for the protocol before it proceeds with protocol processing. This involves checking the version number, checking the header length field (also needed to determine whether any options are present in the packet), and calculating the header checksum.2

      Destination IP Address Parsing and Table Lookup:

      The router performs a table lookup to determine the output port onto which to direct the packet, and the next hop to which to send the packet along this route. This is based on the destination IP address in the received packet and the subnet mask(s) of the associated table entires. The result of this lookup could imply: - A local delivery: that is, the destination addresses is one of the router's local addresses and the packet is locally delivered. - A unicast delivery: to a single output port, either to a next-hop router or to the ultimate destination station. - A multicast delivery: to a set of output ports that depends on the router's knowledge of multicast group membership. The router must also determine the maping of the destination network address to the daa link address for the output port (address resolution or ARP). This can be done either as a separate step or integrated as part of the routing lookup. - Packet Lifetime Control: The router adjusts the time-to-live (TTL) field in the packet used to prevent packets from circulating endlessly throughout the internetwork. A packet being delivered to a local address within the router is acceptable if it has any positive value of TTL. A packet being routed to output ports has its TTL value decremented as appropriate and then is rechecked to determine if it has any life before it is actually forwarded. A packet whose lifetime is exceeded is discarded by the router (and may cause an error message to be generated to the original sender). - Checksum Calculation: The IP header checksum must be recalculated due to the change in the TTL field. Fortunately, the checksum algorithm employed (a 16-bit one's complement addition of the header fields) is both commutative and associative, thereby allowing simple, differential recomputation. (source: rfc 1071) 

          If (N matches a directly connected network address)
      Deliver datagram to D over that network link;
    Else if (the routing table contains a route for N)
      Send datagram to the next-hop address listed in the routing table;
    Else if (there exists a default route)
      Send a datagram to the default route;
    Else
      Send a forwarding error message to the originator;3

      2: You may assume packet validity is established by a lower layer in the protocol stack.

      3: Does this handle CIDR?

    5.   if (IPCB(skb)->opt.router_alert && ip_call_ra_chain(skb))
    return NET_RX_SUCCESS

  if (skb->pkt_type != PACKET_HOST)
    goto drop

  skb->ip_summed = CHECKSUM_NONE

  if (iph->ttl <= 1)
    goto too_many_hops

  rt = (struct rtable *) skb->dst;
  if (opt->is_strictroute && rt->rt_dst != rt->rt_gateway)
    goto sr_failed

  if (skb_cow(skb, LL_RESERVED_SPACE(rt->u.dst.dev) + rt->u.dst.header_len))
    goto drop

  ip_decrease_ttl(iph)

  if (rt->rt_flags & RTCF_DOREDIRECT && !opt->srr)
    ip_rt_send_redirect(skb)

  skb->priority = rt_tos2priority(iph->tos)

  return NF_HOOK(
    PF_INET, NF_IP_FORWARD, skb, skb->dev, rt->u.dst.dev, ip_forward_finish)4

      Reference--\ http://www.civilnet.cn/book/kernel/Understanding%20Linux%20Network%20Internals/understandIni-CHP-20-SECT-1.html

      4: Does this handle CIDR?

    6.   #define MAX_ROUTES 128 /* maximum size of routing table */

  typedef struct {
    int IPaddress;
    int subnetmask;
    int outline;
    }

  int   numRoutes = 0;
  Route routingTable[MAX_ROUTES];

  /* This function takes ipaddress as its parameter
  and returns outline value of type int */
  public int forward(int ipaddress) {
    int i;
    for (i = 0; i < numRoutes; ++i)
    {
      // looking for ipaddress in routing table
      if (ipaddress == routingTable[i].IPaddress)
      {
        // returning line value
        return routingTable[i].outline5
      }
    }
  }

      5: Does this handle CIDR?

    7.   int Forward(IP_address)
  {
    for (triple in table)
    {
      if triple.address = IP_address6
        return triple.outline_line
    }
    return -1 // or some integer that is irrelevant to the outline lines.
  }

      6: Does this handle CIDR?

This page last modified on 2012 November 24.