10 Nov 2003

[ ARP ]

def: Address Resolution Protocol. The protocol a computer uses to map an IP address into a hardware address. A computer that invokes ARP broadcasts a request to which the target computer replies.

· Network hardware only recognizes MAC addresses and not IP addresses. Recall that Ethernet addresses are 6 bytes and IP addresses are 4 bytes.

· The IP layer only uses the IP addresses.

· ARP does the translation from the IP addresses to the Ethernet addresses.

Potentially ARP can be used for any network hardware addressing scheme, however, it is most often used for IP / Ethernet conversions.

[ ARP LOOKUP ]

· Host A wants to deliver an IP packet to B. B can be either another host or a router, but resides in the same network as A.

· Host A will lookup I_B in the ARP table to see if there is a translation to E_B . If the hardware address of B is not present, then :

1. Host A will broadcast an ARP request for the Ethernet address of B.

2. B will receive the request (along with all of the other hosts and routers on the network) and will respond with it’s Ethernet address. This response is sent as a unicast to host A.

3. B will add an entry for host A in it’s ARP table. It does this under the assumption that since A requested it’s Ethernet address then A plans on communicating with it again in the near future. By storing A’s information (it’s IP and Ethernet addresses; E_A I_A) then it will prevent B from generating ARP requests to send packets to A.

4. Host A will add B’s addresses (I_B , E_B) to it’s ARP table, under the assumption that it will communicate with B again soon. This will prevent A from having to generate additional ARP requests for the Ethernet address for B.

Notes:

- The entries for the ARP tables usually have a lifetime of about 20 minutes.

- The ARP table resides in the kernel memory as part of the network protocol stack.

- In some implementations a machine, at boot time, will send a gratuitous ARP reply to the network stating it’s Ethernet address.

- The ARP table only contains entries for entities that are directly connected (i.e. on the same network).

[ ARP LOOKUP EXAMPLE, LOCAL NETWORK ]

Host A wants to send a packet to B.

Step 1) A sends an ARP request via a broadcast.

Step 2) ARP reply. B sends a unicast reply to A.

Step 3) A sends packet(s) to B.

[ ARP LOOKUP EXAMPLE, DIFFERENT NETWORKS ]

- Host X wants to send an IP packet to host A which resides on a different network. While X cannot send an ARP request to X directly (since routers do not forward ARP requests), the ARP protocol can still be used to forward a packet.

- To print the ARP cache Unix one can use the command /usr/sbin/arp –a. It will generate a table such as:

dev IP address Ethernet address

elxl0 128.10.3.54 03:0F:E1:AA:12:FF

elxl0 128.10.3.58 FF:01:A2:DE:34:C9

[ IP AND ETHERNET ADDRESSES DURING TRANSIT ]

The IP destination and source addresses of an IP packet remain constant during the transition of the packet. The hardware src and dst addresses will change as the packet traverses different networks.

Example:

Host X is sending a packet to host A.

In N1 , the packet will have the fields set as such:

E_SRC = E_X

E_DST = E_R

I_SRC = I_X

I_DST = I_A

In N2, the packet will have the fields set as:

E_SRC = E_R // variable

E_DST = E_A // variable

I_SRC = I_X

I_DST = I_A

The IP addresses remain constant and the Ethernet fields will change as the packet crosses networks.

12 Nov 2003

Topics : Datagram transit, fragmentation, reassembly.

To send a packet the source host forms a datagram and then:

1) Sends the datagram directly if the destination is in the same network, or

2) Sends the datagram to the nearest router for forwarding.

[Datagram Fragmentation]

- Fragmentation may occur to a packet while it is in transit. The source host does not fragment a packet . It will form a packet based upon the MTU of the network that it resides in. It will form a packet size that is <= to the local network MTU.

- Intermediate routers will fragment a packet if it must pass the packet to another network that has a smaller MTU.

[ Datagram Fragmentation Example ]

Host A is sending a datagram of size 1500 to host B.

· A sends packet of size 1500 (based on MTU of N1) to B.

· R1 fragments the packet into two packets, sized 1000 and 500 to fit the MTU of N2.

· R2 fragments the packet of size 1000 into two packets sized 500 each.

· B receives three packets of size 500.

Notes :

· Fragmentation is only done by the routers. Since the host machine does not know the path that the packet(s) will take, it does not know how to size the packets to fit the MTUs of the intermediate networks.

· Each fragment will have it’s own IP header and is itself an IP packet.

· Fragments may potentially follow different routes to the destination.

· The final destination reassembles the packets. This is done for a couple of reasons. First, the fragments may follow different routes, so intermediate routers may not have all the fragments for reassembly. Secondly, it would not make sense for an intermediate router to reassemble a packet that may have to be fragmented again further along the route.

· As the above example shows, it is possible to fragment an already fragmented packet.

· All fragments will have the same IP id (assuming they came from the same packet) and the same IP source and destination addresses.

· The IP offset field will tell where in the original packet the fragment will be placed.

· The “more fragments” flag will be set (to 1) in all of the fragments except for the last fragment.

· The receiver collects all incoming fragments and reassembles them in a buffer using the offset field.

· The last packet will tell the total length of the packet (the original).

· Once all of the fragments are received and the whole packet is reassembled it is passed to the TCP or UDP stack.

· The receiver will not know the identity of the router that did the fragmentation. There is no state associated to the packets within the routers.

· After the first fragment is received, the receiver starts a timer. If, after 255 seconds, the packet is not fully reassembled, all the fragments are discarded and the reassembly buffer released. This timer is called the reassembly timer.

· The receiver cannot request missing pieces.

· In summary, the fields used for reassembly are:

- IP src address

- IP id number

- the offset

- the “more fragment” bit

* The source IP address and id number gives identity to the packet fragments so that different source addresses and identical id numbers will not be confused.

[ ICMP ]

- Internet Control Message Protocol

- Used for error reporting and information.

- ICMP sends error messages to the source.

ICMP

UDP

TCP

	Each layer in the stack is implemented as a module or loadable library.

[ Example, ICMP Message ]

· Type number : 4.

· Type message : Source Quench.

· This message is sent by routers when it drops packets due to buffer overrun (congestion).

· Requests that the source slow down transmission rate.

14 Nov 2003

[ Lab5 Update ]

· New deadline : Sunday Dec 7^th.

· Since we have extra time, the Professor stated that we are expected to implement additional features, such as the ones that are listed in the project handout.

· The presentations will be during deadweek, Dec 8-12. There will be a signup sheet available as deadweek approaches.

· An additional feature, mentioned by name, was to implement compression. The Professor mentioned that a free implementation (i.e. open source) called zlib could be used for compression.

[ Lab 5 : Capture-Play Overview ]

· Three threads total: one in the voice client, two in the player server. In the following overview the threads will be labeled 1 through 3.

· The references to read and write pointers are best thought of in context to the buffer that they are associated. At times a write pointer will also read from another buffer so it can be confusing. In the following I try to use them in the manner that they operate on the buffer in question.

Thread 1 (Voice Client)

Each box represents a ‘tick mark’ in the buffer, which is a point where we would have Direct Sound trigger an event, such as to retrieve more data from the read pointer, etc.

		The write pointer. This pointer is the one used to write data to the buffer. It will write into the send buffer data contained in the capture buffer. It will be controlled by an event ( a timer, for instance). It, like the read pointer, will ‘wrap around’ the buffer so as to provide continuous (infinite) capability with a finite resource.

[ Voice Client Pseudo Code ]

while( 1 ) {

· Wait for event from the capture buffer (say, every 1/10^th of a second).

· When event occurs, write the captured data to the send buffer

· Form packets (the header and the sound samples).

· Send packets to peer play server.

}

[ Player Server Pseudo Code and Illustrations ]

Thread 2 (Jitter Buffer)

while(1) {

· Receive a UDP packet.

· Place the sound data samples in the jitter buffer.

o Ensure that the samples are in order.

o Consider lost packets (samples) and how to deal with them.

}

	Jitter Buffer

Thread 3 (Play Buffer)

while(1){

· Wait for event from the play (secondary) buffer. This will be a logical event .

· When event triggered, copy data from jitter buffer into the play buffer.

}

Notes:

· Hint for a final’s test question ; Q : Why do we need two buffers? Answer : Need to block for two events.

· Thread2 and thread3 run independently of each other.

· Thread1 and thread3 must run at the same frequency (i.e. the sampling speed must be the same for capturing and playing).

[ ICMP Types (continued) ]

Type 4 : Source Quench

- sent by routers when packet(s) dropped.

Type 11 : Time Exceeded

- sent by router when a packet’s TTL reaches 0.

- also sent by hosts when the reassembly of a fragmented packet times out, such as when a fragment is lost.

Type 3 : Destination Unreachable

- sent by a router when it determines that the destination network is unreachable, such as when it is non-existent.

- also used for a destination host that is unreachable.

- also used when a protocol port does not exist.

Type 0 : Echo Reply

- not an error message.

- used by the Ping program.

- the sender sends an ICMP Echo Request and the receiver answers with an ICMP Echo Reply.

- this ICMP message is used to test connectivity.