CIS307: Layers

Physical Layer

A significant physical layer protocol is SONET (Synchronous Optical NETwork), with a variation called SDH (Synchronous Digital Hierarchy). It uses a binary signal (baseband) multiplexed using Time-Division Multiplexing. It was originally designed for the transfer of voice data. SONET multiplexes a number of voice channels, in fact it sends a 810 byte frame each 125 microseconds. Of these 810 bytes only 783 bytes carry data, the rest is control information. Thus the total data rate is 810 * 8 * 8000 bits/s, or 52Mb/s. SONET also comes with data rates that are multiples of this value.
T1 is a carrier related to SONET. It again uses multiples of the voice channel. Now every 125 microseconds we send a frame of 24 voice channels plus one framing bit. Thus the data rate is 24*8 + 1 bits each 125 microseconds (remember from note on Nyquist Sampling Theorem), for a total of 1.544 Mb/s. Other carriers use multiples of T1: T2 is 4 times T1 plus control bits, for a total data rate of 6.312Mb/s; T3 is 6 times T2 plus extra control bits, for a total data rate of 44.736Mb/s; T4 is a combination of 7 T3s for a total with control bits of 274.176Mb/s. T1 can be multiplexed on T2, or T3, or T4. T1, T2, T3 can be multiplexed on SONET. You may have heard of people/companies leasing T1 lines, or T3 lines, or .. (rental is thousands of dollars per month).

Data Link Layer

A basic problem at the data link layer is what to do when errors are detected at the receiver end (we have already seen how detection is done). The transmitter has to retransmit the frame, and the question is how does the transmitter find out that it has to do so. There is need of an ARQ (Automatic Repeat Request) method. Three such methods are in common use:

• Stop-and-Wait: a transmitter after sending a frame waits for a message (ACK/NACK) back from receiver indicating if the previous frame was or not received correctly. If not, the frame is retransmitted.
• Go-Back_N: Now frames are numbered and the transmitter is allowed to send a number of frames (up to N) without waiting for acknowledgement (see Sliding Window Protocol below), but when the receiver sends a "NACK i" to indicate an error with frame i, then frame i and all its transmitted successors are retransmitted.
• Selective-Repeat: Similar to Go-Back-N, but now for the response "NACK i" only frame i is retransmitted.

Performance of ARQ Techniques

       Tt          1                 Tp   Propagation Time
    --------- = --------  where a = --- = -----------------
    Tt + 2*Tp    1 + 2*a             Tt   Transmission Time

      (1 - P)
     ---------
      1 + 2*a

If we consider instead the Go-Back-N ARQ or the Selective-Reject ARQ the transmission of ACKs is overlapped with the transmission of the frames. Thus the utilization, without worrying about errors, becomes

 
                            N
                      /  -------  if  N < 1 + 2*a
                      |  1 + 2*a
      utilization =   |
                      |
                      \  1        otherwise

• When N*Tt is less than (Tt + 2*Tp) the acknowledgement of the first frame is not yet received by the transmitter when the transmitter terminates sending all the N frames. Thus the transmitter has to wait before sending more frames and the utilization is less than 1.
• When instead N*Tt is greater or equal than (Tt + 2*Tp) the acknowledgement for the first frame has been received before all the frames are sent, thus the transmitter can keep on transmitting without idle time.

Sliding Window Protocol

1. One selects the number of bits m to be used for the frame identifier. Say m, for example 3.
2. Set N to 2**m - 1. So if m is 3 N is 7 and the frames will have ids 0,1,2,3,4,5,6,7, but only 7 of them may be outstanding (i.e. without acknowledgement) at a time.
3. The receiver will send ACK_i when it has received all the frames up to frame i-1 included. In addition if the receiver were to send a message to the sender (because they have a two way conversation) it will insert in the message the same ACK_i as a further confirmation (or as the only confirmation as suggested by some). [This second acknowledgement is said to be piggybacked on the message from receiver to sender and it is the reason why we cannot have 2**m outstanding frames: suppose sender sends 0 and gets ACK_1; then it sends 1,2,3,4,5,6,7,0, then it received ACK_1 again. Does it mean that 1,2,3,4,5,6,7,0 were all received correctly, or does it mean that they were all lost and receiver is repeating the previous ACK_1?]

We can determine the "ideal" size in bits W of the window used in the Sliding Window Protocol on the basis of the fact that we want to keep on transmitting until acknowledgement has been received for the initial packet. The round trip for the acknowledgement is Tt+2Tp. If r is the data rate at which the transmitter is transmitting, then the number of bits to be transmitted during the round trip is

    W = r(Tt+2Tp)

HDLC

        8 bits    8 bits    8 bits    >=0    16 bits     8 bits
    +----------+---------+---------+------+----------+----------+
    | 01111110 | address | control | data | checksum | 01111110 |
    +----------+---------+---------+------+----------+----------+

bits  1      3         1     3
    +---+----------+-----+-------+
    | 0 | sequence | P/F |  next |     Format for Information Frames
    +---+----------+-----+-------+

bits  1   1    2      1      3
    +---+---+------+-----+-------+
    | 1 | 0 | type | P/F |  next |    Format for Supervisory Frames
    +---+---+------+-----+-------+

bits  1   1   1     1     1       3
    +---+---+---+------+-----+----------+
    | 1 | 1 | 0 | type | P/F | modifier |  Format for unnumbered frames
    +---+---+---+------+-----+----------+

PPP

Network Layer

IP Addresses

• Class A: The network identifier is 3 bytes and the host identifier is 1 byte. The network identifier will start with a 0 bit. For example 126.46.31.87 is a class A address.
• Class B: The network identifier is 2 bytes and the host identifier is 2 bytes. The network identifier will start with the bits 10. For example 155.247.170.2 is a class B address.
• Class C: The network identifier is 3 bytes and the host identifier is 1 byte. The network identifier will start with the bits 110. For example 200.77.88.91 is a class C address.
• Class D: It starts with the bits 1110 and it is used as a multicast address. For example 225.65.90.3 is a class D address.
• Class E: It starts with bits 1111 and it is currently not in use.

+------------+------------+----------+-------------------------------+
| Network    | Host       | Type of  | Purpose                       |
| Identifier | Identifier | Address  |                               |
+------------+------------+----------+-------------------------------+
| all 0s     |  all 0s    | this     | Using during bootstrap to     |
|            |            | computer | ask for own's IP address      |
+------------+------------+----------+-------------------------------+
| Network    |  all 0s    | specified| The specified network,        |
| Identifier |            | network  | independent of its hosts      |
+------------+------------+----------+-------------------------------+
| Network    |  all 1s    | specified| Broadcast address for the     |
| Identifier |            | network  | specified network.            |
+------------+------------+----------+-------------------------------+
| all 1s     |  all 1s    | local    | Broadcast on local network    |
|            |            | network  |                               |
+------------+------------+----------+-------------------------------+
| 127        | anything   | loopback | Testing of TCP/IP while not   |
|            |            |          | using the network             |
+------------+------------+----------+-------------------------------+

Subnetting

To account for subnetting a routing tables T takes the form:

   For each row i of routing table T
       Let D = T[i].subnet-mask BitwiseAnd IP;
       If (D == T[i].subnet-id) then
       {
          Forward packet to T[i].next-hop;
          break;
       }

IP Role

• Addressing: how to identify networks and hosts
• Fragmentation: it takes care of the fact that different networks may have different MTUs (Maximum Transfer Units), and thus they may need to fragment an existing packet when going through a network with smaller MTU.

• Computation of Routing Tables(done by other protocols)
• Congestion control
• Flow control
• Error control
• Resource management

IP Header

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |Type of Service|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version: Current IP  4 
         Next Generation:  6 ==> IPv6 or IPng
IHL: Header Length in words:  without options it is 5, with
         options it can be as high as 15.
Type of Service: the sender specifies the type of service desired,
         if one that maximizes reliability or one that minimizes delivery
         time or one that maximizes throughput.
Total Length: 16 bits ==> maximum packet size 65,535 Bytes (64 KB)
         including header length  
Identification: unique for each IP datagram
       (1) source increments a counter
       (2) gateway copies
       All the fragments of the same packet have the same identification.
Flag: three bits, two lower bits used for fragmentation
       (1) first bit if 1, means do not fragment (this is the DF flag)
       (2) second bit if 1, means more fragment are coming (not end of packet)
          (This is the MF flag.)
Fragment Offset: offset in the original datagram in units of 8 octets. All
       fragments, except the last, must me multiples of 8 bits.
TTL:   each gateway decrements TTL by some number and discard the packet if it
       reaches 0. If discarded, the sender is informed using the ICMP (Internet 
       Control Message Protocol) protocol.  
       In theory, it counts in second units and discards a packet that takes
       255 seconds to propagate.
Protocol: number of higher level protocol that is using the current packet
       ICMP: 1, TCP: 6, UDP: 17

• Fragments of a packet are not re-assembled together until the final destination is reached. There, if a fragment is missing, or a fragment is with bad data check, all the fragments are discarded.
• If necessary, a fragment may be further decomposed. All the fragments of a packet have the same header, except for minor differences like fragment offset, flags, checksum.

ICMP: Internet Control Message Protocol

• Source Quench: A router that has to discard a packet because it has run out of buffer space sends a Source Quench message to the source of the packet. That source will have to slow down the rate at which it sends packets.
• Time Exceeded: It is sent to the source of a packet when a router has to discard that packet since its TTL has reached zero, or when the destination of the packet is unable to collect all the fragments of the packet before the time out expires.
• Destination Unreacheable: sent to source of packet when a router cannot find its destination, either network or host.
• Fragmentation Required: when there is need of fragmentation, but fragmentation is not allowed because the non fragmentation flag is set in the packet.
• Echo Request/Reply: When a node receives an Echo Request it is supposed to send a Echo Reply message.
• Address Mask Request/Reply: When a host first starts, it sends an Address Mask Request on the local network and a local router replies with an Address Mask Reply indicating the subnet mask of the network.

Transport Layer

TCP Header

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          source port          |        destination port       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        sequence number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 acknowledgement number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | TCP |             |U|A|P|R|S|F|                               |
   |Headr|             |R|C|S|S|Y|I|       window size             |
   |lengt|             |G|K|H|T|N|N|                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       checksum                |   urgent pointer              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options (0 or more words)                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Source and Destination Ports:

They are 16 bit numbers. A port number is local to a specific host, i.e. different hosts have 65,535 different ports. In unix /etc/services keeps a list of specific uses for some of these ports. For example, HTTP uses 80, Telnet uses 23, FTP uses 21. The first 1024 ports are said to be "well known" and are reserved. Notice that ports allow us to communicate with specific programs on a computer, not just with a computer as in IP.

Sequence and Acknowledgement Numbers:

These numbers are local to a connection between two nodes, they are unique during the life of message. The initial sequence number is agreed between the sender and the receiver when the connection is set up with a Three-Way-Handshake [SYN->, SYN+ACK<-, ACK->]. For example, if two nodes A, B are communicating, then A as sender may choose initially the number 200 and B as sender may choose initially the number 500. Then B will acknowledge messages relative to 200 and A will acknowledge messages relative to 500.

Length of the TCP header:

It is counted in 32-bit words.

Flags:

There are a variety. Among them:

• URG: It is 1 if the Urgent Pointer is used.
• ACK: Confirms that the acknowledgement field is valid
• SYN: Request to setup a connection. It must be acknowledged.
• FIN: Request to shutdown. It must be acknowledged.

Window Size:

It specifies the size of the receiver's available buffer (called window).

Urgent pointer:

Byte offset from the current sequence number at which urgent data will be found.

• Message identification: Managing identifiers for messages to make sure that stale message do not create confusion. It uses lower k bits from the local timer. One must make sure that no two messages are sent for the same tick of the clock (that is usually the case) and that no message remains alive across the intervening time (2^k ticks). The transmitter and receiver both identify their messages and these identifiers are usually different.
• Connection management, both starting and terminating a connection, and multiplexing multiple connections.
  A connection is started using a three-way handshake. The transmitter sends ConnectionRequest(seq=x) to start a connection with transmitter id x. The receiver replies ConnectionAccepted(seq=y, ACK=x), to acknowledge x and establish for its messages the identity y. Finally the transmitter confirms the connection with ConnectionAccepted(seq=x,ACK=y) to confirm its own identifier x and accept the receiver's identifier y. If the receiver wanted to reject x, it would send Reject(ACK=x), and if the transmitter wanted to reject y it would send Reject(ACK=y). As part of the handshake the transmitter and receiver specify their MSS (Maximum Segment Size), that is the maximum size of a segment they can accept. A typical value for MSS is 1460.
  A connection is terminated with a similar FOUR-way handshake [FIN->, ACK<-, FIN<-, ACK->].
• Error management, including error detection, error control, choosing timeouts. For timeouts, for each distinct destination one keeps track of round trip times, RTT, and chooses a timeout that is computed from the recent RTTs. One may compute an estimated RTT that is the exponential average of the RTTs and then choose the timeout as 2 times that estimate. [Exponential averaging assumes a number a, 0<=a<=1, and computes a sequence of estimated RTTs according to the formula
  ERTT(i+1) = a*ERTT(i) + (1-a)*RTT(i).]
• Managing message fragmentation.
• Flow Control. Here we use the Sliding Window Protocol. Remember that flow control deals with the ability of the end receiver of a transmission to deal with incoming messages.
• Congestion Control. Remember that congestion control deals with the ability of the network to deal with current traffic, i.e. it refers to the intermediate routers and links, not to the endpoints of the transmission. The transmitter knows the receiver's window from the Sliding Window Protocol. It maintains in addition a Congestion Window and a Threshold, initially 64KB. The amount of data that can be transmitted is the minimum of the sliding window and the congestion window. The congestion window starts at the maximum size of a segment. If the message is acknowledged, the congestion window is doubled, and so on until the threshold is reached or a message is lost due to congestion. When the threshold is reached, the congestion window can still grow, but now it is incremented by a single maximal segment per successful transmission. When a message is lost, the threshold is set to 1/2 of the congestion window and the congestion window is restarted at the size of the maximum segment.