Version 1.3. This note gives: (i) The exact formats of inputs and outputs for the CIS656 project, (ii) The description of ``strict source route'' as we will do it. It is possible the strict source route here is not quite right. It is correct in spirit, and almost correct in detail. In any case: this is the way you do it if you want full credit. I will be in my office Wed 11/21/2001 3:00 - 4:30. We will have class Nov 28, Dec 5, Dec 12. These three days I will teach 6:00 SHARP - 9:30, with a 15 to 20 minute break around 7:40. Final: Dec 19. For input, the format of a packet will be as follows (example): INPUT (this line is not part of the input!) A3 01000101000000000000000011110000 01010101010101010000000000000000 00011111000100010000000000000000 00010100000101000001010000010100 10101010101010100001010100001111 This means: the packet enters at Interface A3. The IP header is given in binary. Since the header length is 5 times 4 = 20 bytes, and the Total Length is 240 bytes, the number of data bytes must be 220 bytes. Unlike Professor Karvelas I do not give the number of data bytes separately: You must compute it. But I do give the input interface. Your output now will look as follows: OUTPUT (this line is not part of the output!): A4, direct delivery to a host on network I. 1 Fragment. Fragment 1: VERS = 4, HLEN = 5, Service = 0, TL = 240 Ident = 21845, FLAGS = 0, FragmOffset = 0 TTL = 30, PROT = 17, Checksum = 0 SourceAddress = 20.20.20.20 DestAddress = 170.170.21.15 DataField = 220 bytes. ------- (these ARE part of the output!). If you say ``PROT = UDP'' that is also OK (in this case). As long as your answer is correct. In case of fragmentation there are multiple output packets. Example: INPUT: A2 01000101000000000001010100000000 01010101010101010000000000000000 00011111000100010000000000000000 10101010101010101000000100010001 10101010101010100001000100010001 The packet has Total Length 5376 bytes (please check!). HLEN = 5, so there are 5376 - 4x5 = 5356 data bytes. 5376 is larger than the MTU of network I (4464 bytes), so fragmentation occurs. Fragment 1 will contain kx8 data bytes, where k is the largest integer for which kx8 + 20 is .LE. 4464. k = floor of (4464 - 20)/8 = 555. So fragment 1 will contain 555x8 = 4440 data bytes, and fragment 2 will contain 5356 - 4440 = 916 data bytes. Fragment 1 will have Total Length 4440 + 20 = 4460 bytes. Fragment 2 will have Total Length 916 + 20 = 936 bytes. OUTPUT: A4, Direct Delivery to Host on Network I. 2 Fragments Fragment 1: VERS = 4, HLEN = 5, Service = 0, TL = 4460 Ident = 21845, FLAGS = 1, FragOffset = 0 TTL = 30, PROT = UDP, Checksum = 0 SourceAddress = 170.170.129.17 DestAddress = 170.170.17.17 DataField = 4440 bytes Fragment 2: VERS = 4, HLEN = 5, Service = 0, TL = 936 Ident = 21845, FLAGS = 0, FragOffset = 555 TTL = 30, PROT = UDP, Checksum = 0 SourceAddress = 170.170.129.17 DestAddress = 170.170.17.17 DataField = 916 bytes ------- If you had said ``PROT = 17'' that would have been OK, too. As long as it is correct. Now a harder one: an Option (strict Source Route) with fragmentation. I am going to do the ``strict source route'' the way it is done in Forouzan's book. Ms Zhao said that is wrong. She may very well be right. But we are going to do it as described below. Explanation by example: INPUT: A2 01001001000000000000100000000000 10101010101010100000000000000000 00100000000001100000000000000000 10101010101010101000001010000010 10101010101010100000010100001000 00000001100010010000111100001000 10101010101010100010000000000010 10101010101010100010100000000000 10101010101010100000010000000010 Before giving the output, some explanation: For this packet, VERS = 4, HLEN = 9, Service = 0, TL = 2048 so there are 2048 - 9x4 = 2012 data bytes. Ident = 43690 (check that!), Flags = 0, FragOffset = 0 TTL = 32, PROT = 6 (TCP), Checksum = 0 SourceAdress = 170.170.130.130 (a host in network VIII) DestAddress = 170.170.5.8 (a host in network X) The first 8 bits in the next row are 00000001 : the No-Op code, used for allignment. I am not sure this is necessary, but this is the way we will do it. The next 8 bits are 10001001 i.e. 137: strict source route. The first bit (copy bit) is 1: the option is copied to all fragments. The next two bits are 00: Datagram Control. The last 5 bits are 01001: Strict Source Route. The next 8 bits are 00001111 = 15. Length = 15 (length of option). The next 8 bits are 00001000 = 8. The Pointer = 8. The next row is 10101010 10101010 00100000 00000010 = 170.170.32.2 This is the address of A11. The next row is 10101010 10101010 00101000 00000000 = 170.170.40.0 This is the address of A2 (the port on R1 where the packet comes in). The next row is 10101010 10101010 00000100 00000010 = 170.170.4.2 This is the address of A17. The pointer points at the 8-th byte in the options (start counting at 0). Hence, R1 compares the address in that row with its own incoming address, A2. They are the same, so the packet is not thrown on the floor. Next, R1 checks that the next address is immediately reachable, indeed, it is. The packet is still not thrown on the floor. R1 replaces its incoming address with its outgoing address A1, and increases P to 12. Now, if there were no issue with fragmentation, R1 would forward the packet to A17 on R9. The OUTPUT would look like: A1 Forward to A17 on R9 1 Fragment Fragment 1: VERS = 4, HLEN = 9, Service = 0, TL = 2048 Ident = 43690, Flags 0, FlagOffset = 0 TTL = 31, PROT = 6 (TCP), Checksum = 0 SourceAddress = 170.170.130.130 DestAddress = 170.170.5.8 Option = 1 (No-Op); Option = 137 (Str Source Route), L = 15, P = 12 170.170.32.2 170.170.4.1 170.170.4.2 DataField = 2012 bytes. In that case, R9 would replace the address of A17 with that of A18, (it might increase P to 16, that is unclear: there is no next router: see below) and do a direct delivery of the packet through A18 to the final destination, 170.170.5.8 . Ms Zhao felt this method is wrong. She may be right. However, it is consistent with the spirit of Internet Standards: to send the packet back along the same route, host 170.170.5.8 only needs to interchange source address and destination address, reverse the order of addresses in the option, and reset P to 4. So, in this method the routers on the way do NOT modify source address and destination address. They only modify addresses in the option. Since there IS an issue with fragmentation, actually two packets are forwarded. The first one contains kx8 data bytes, where k is the largest integer for which kx8 + 9x4 .LE. 1500, i.e. k = 183 . Fragment 1 contains 183x8 = 1464 data bytes plus a header of 36 bytes. Fragment 1 has TL = 1500 bytes. Fragment 2 contains 2012 - 1464 = 548 data bytes plus a header of 36 bytes. Fragment 2 has TL = 584 bytes. OUTPUT: A1, Forward to A17 on R9 2 Fragments Fragment 1: VERS = 4, HLEN = 9, Service = 0, TL = 1500 Ident = 43690, Flags 1, FlagOffset = 0 TTL = 31, PROT = 6 (TCP), Checksum = 0 SourceAddress = 170.170.130.130 DestAddress = 170.170.5.8 Option = 1 (No-Op); Option = 137 (Str Source Route), L = 15, P = 12 170.170.32.2 170.170.4.1 170.170.4.2 DataField = 1464 bytes. Fragment 2: VERS = 4, HLEN = 9, Service = 0, TL = 584 Ident = 43690, Flags 0, FlagOffset = 183 TTL = 31, PROT = 6 (TCP), Checksum = 0 SourceAddress = 170.170.130.130 DestAddress = 170.170.5.8 Option = 1 (No-Op); Option = 137 (Str Source Route), L = 15, P = 12 170.170.32.2 170.170.4.1 170.170.4.2 DataField = 548 bytes. ------- Input will be done in a single file called ``InputFile'', packets sequentially, separated by blank lines. The first line gives the number of input packets. Then a blank line. Then the first packet, and packets separated by blank lines. So the input file might look like: ---- Addition on 11/19/01: I have decided to allow standard input and standard output . I will use input redirection and output redirection. (e.g. a.out < InputFile > OutputFile ). So your program can either use standard input, standard output, or use InputFile , OutputFile . ---- INPUT (this line and the next are not in the input file!): 3 A3 01000101000000000000000011110000 01010101010101010000000000000000 00011111000100010000000000000000 00010100000101000001010000010100 10101010101010100001010100001111 A2 01000101000000000001010100000000 01010101010101010000000000000000 00011111000100010000000000000000 10101010101010101000000100010001 10101010101010100001000100010001 A2 01001001000000000000100000000000 10101010101010100000000000000000 00100000000001100000000000000000 10101010101010101000001010000010 10101010101010100000010100001000 00000001100010010000111100001000 10101010101010100010000000000010 10101010101010100010100000000000 10101010101010100000010000000010 Output is done to a file called ``OutputFile''. With the example above, your output file had better look like: OUTPUT (this is not part of the output file!): A4, direct delivery to a host on network I. 1 Fragment. Fragment 1: VERS = 4, HLEN = 5, Service = 0, TL = 240 Ident = 21845, FLAGS = 0, FragmOffset = 0 TTL = 30, PROT = 17, Checksum = 0 SourceAddress = 20.20.20.20 DestAddress = 170.170.21.15 DataField = 220 bytes. ------- A4, Direct Delivery to Host on Network I. 2 Fragments Fragment 1: VERS = 4, HLEN = 5, Service = 0, TL = 4460 Ident = 21845, Flags = 1, FragOffset = 0 TTL = 30, PROT = UDP, Checksum = 0 SourceAddress = 170.170.129.17 DestAddress = 170.170.17.17 DataField = 4440 bytes Fragment 2: VERS = 4, HLEN = 5, Service = 0, TL = 936 Ident = 21845, Flags = 0, FragOffset = 555 TTL = 30, PROT = UDP, Checksum = 0 SourceAddress = 170.170.129.17 DestAddress = 170.170.17.17 DataField = 940 bytes ------- A1, Forward to A17 on R9 2 Fragments Fragment 1: VERS = 4, HLEN = 9, Service = 0, TL = 1500 Ident = 43690, Flags = 1, FlagOffset = 0 TTL = 31, PROT = 6 (TCP), Checksum = 0 SourceAddress = 170.170.130.130 DestAddress = 170.170.5.8 Option = 1 (No-Op); Option = 137 (Str Source Route), L = 15, P = 12 170.170.32.2 170.170.4.1 170.170.4.2 DataField = 1464 bytes. Fragment 2: VERS = 4, HLEN = 9, Service = 0, TL = 584 Ident = 43690, Flags = 0, FlagOffset = 183 TTL = 31, PROT = 6 (TCP), Checksum = 0 SourceAddress = 170.170.130.130 DestAddress = 170.170.5.8 Option = 1 (No-Op); Option = 137 (Str Source Route), L = 15, P = 12 170.170.32.2 170.170.4.1 170.170.4.2 DataField = 548 bytes. ------- We have decided that for the purpose of this project Strict Source Route works as follows: A No-Op Option is used for allignment. If P > L-3, the router drops the packet and sends a further unspecified ICMP message. (I am not sure about sending an ICMP message). Else: The router finds the address the pointer points at. If that address is not identical to its input address, it drops the packet and sends a (unspecified) ICMP message (I am not sure it does). Otherwise, the router checks whether there is a next address in the options. If not, go to ``almost there''. If there is a next address, check whether it is one-hop reachable. If not, drop the packet. If one-hop reachable, determine the output port. Replace, in the list of addresses, input port address by output port address. Increase P. Forward the packet. ``almost there'': If the router finds no next address in the list of addresses (i.e. P = L-3), it checks whether the final address is directly reachable. If it is: determine output interface and output address. Replace input address by output address. Direct delivery of packet. In the ``almost there'' case: We will increase P by 4 (to L+1) before sending the packet out. This may be wrong, but this is the way we do it. If a computer receives an IP packet with its own address (one of its own addresses) in the destination address field, it always sends the packet to its higher level software. Even if the TTL is zero, even if it has an strict sourceroute option with P > L. In the ``almost there'' case: if the final destination is not directly reachable, drop the packet (I am not sure of this), send further unspecified ICMP message (I am not sure of this). This is the way you implement Strict Source Route in your program if you want full credit. So, the general format is For every packet in the input file, one of the following: ------- Drop, No ICMP message ------- Drop, Send ICMP message (short description of ICMP message) (A) ------ To higher level in router itself (e.g. destination address is one from A1, A2, A3, A4, or a directed broadcast e.g. to network I coming in through interface A4). (No need for packet description). ------ Interface, action Number of Fragments List of Fragments ------- Interface, action, plus ICMP message (short description of ICMP message) (B) Number of Fragments List of Fragments ------- here, ``action'' is one from: (1) Direct delivery to host on network N (2) Direct Broadcast to Network N (3) Forward to interface Ax on Router Ry (If I think of other possibilities I will send Email). In (A): E.g. TTL expired, Network Unreachable, DF set and packet too large, ... etc. In (B): The only ICMP message I can think of is ``Redirect''. Remember: you do this only if the packet goes back out the input port it came in on, AND the source is directly reachable. Outputs for different input packets must be separated by (blank line) ------- (blank line) Within the output for one input packet, fragments must be separated by a blank line. Further, the output must be as in the examples. You can test with the input packets I gave. If I have time I may generate a few more. Good Luck. Teun Ott.