How can a 13 bit number represent 16 bit number?

[shivajikobardan]

Homework Statement

How can a 13 bit number represent 16 bit number?Or why is fragmentation offset multiple of 8?

Relevant Equations

none

This is more of a mathematics confusion rather than a computer science confusion, so please treat it like that. I understand the computer science behind it(I hope so) but my confusion lies in the basic math part that is there.

I am studying about ipv4 fragmentation.
This is ipv4 header. The fields of concern here are-:
-> identification(16 bit)

-> Flags(3 bit)

-> fragment offset(13 bit)

-> Total length(16 bit)

In order to understand these concepts of fragmentation, I have solved multiple problems. One of them is below.

Here initially we have 5000 byte datagram of which 20 byte is header.
The MTU is 1500 bytes.

The answer is this-:

But I am unable to realize this simple concept that I believe even a 5th grader can understand even though I am college level undergraduate student. It is being pretty shameful for me.I am leaving my shame aside and asking this instead of giving up. I have asked this everywhere and everyone says this is basic math but it is not clicking in my head. Imma memorize this lol. I can solve any numerical problem related to fragmentation but this curiosity isn’t letting me to learn further and go to ipv6.
It would be immensely helpful to me if anyone can help me via that above example to understand this simple concept. I am unable to relate with this concept.
I agree there are 2^13 offset values ie 0,1,2,3,4,5,6,7,8,9…..8191. So that is the total no. of fragments possible 8192 fragments. But datagram can be only as big as 2^16-1 bytes. But why are we dividing them? It doesn’t make any sense. Maybe it is trying to say that 8192 fragments need to span 65535 bytes which gives 7.99987793 as the answer. But I have calculated it later, and fragmentation doesn’t work like that.

Opinion 1-:

Max “true” fragment offset possible=sum of all previous DATA ONLY excluding header
=65535-n*20 bytes.

Where 65535 is the max total length possible.n is the number of fragments and 20 bytes is the header length
The max value of offset possible is 8191. 65535-n*20 bytes should be represented by 8191 (both max values). But this opinion takes nowhere.Opinion 2-:
Max. 13 bit number=8191
Max 16 bit number=65535
So 65535/8191=8.0000sthsth (not exactly 8).

So the problem is like how can max offset value represent the max data size. But as i said in opinion 1, max data size can never be 65535 as header also takes up some space.

Opinion 3–:
Say i want to understand this example by a dummy example. Say fragmentation offset field is of 1 bit. And total length field is of 4 bit. What would happen?

Here are some answers that I have read which gave me further confusions-:
https://networkengineering.stackexc...26/why-ip-fragmentation-is-on-8-byte-boundary

https://learningnetwork.cisco.com/s/question/0D53i00000Kt7dxCAB/fragment-offset-concept

 

[Baluncore]

65535 / 8191 =8.0008545965
You are forgetting the zeroth elements of the ranges.
2^16 / 2^13 = 2^3 ;
65536 / 8192 = 8 ; exactly.

 

[jack action]

Say I encode the word "fragment" in binary. Each character needs 8 bits of information (someone decided that because it was convenient). Each letter is a fragment of the whole word. The position of each letter is important. Otherwise, the word doesn't make sense anymore if all the letters are mixed up.

• So the letter "f" occupies the first 8 bits, positions 0 to 7;
• The letter "r" is the next 8 bits, positions 8 to 15;
• The letter "a" is the next 8 bits, positions 16 to 23;
• And so on.

In the end, you will need a sequence of 64 bits to represent the whole world because there are 8 letters needing 8 bits of information each.

Quickly, where is the letter "m" in the bit sequence? Well, there are 4 letters before it, each taking 8 bits of space, thus 32 bits total, positions 0 to 31.

We can say that the letter (or fragment) "m" is "offset" by 4 previous letters (or fragments). In the binary sequence we get (32-bit total fragments length) / (8-bit single fragment length) = (4 fragment offset)

Hence, the letter "m" 8-bit sequence will start at position 32, all the way to position 39.

So the fragmentation of the word "fragment" would be:

Letter	Offset	Bit position	Bit sequence
f	0	0-7	01100110
r	1	8-15	01110010
a	2	16-23	01100001
g	3	24-31	01100111
m	4	32-39	01101101
e	5	40-47	01100101
n	6	48-55	01101110
t	7	56-63	01110100
Resulting word	Number of letters	Number of bits	Resulting bit sequence
fragment	8	64	01100110 01110010 01100001 01100111 01101101 01100101 01101110 01110100

 

[Mark44]

I agree there are 2^13 offset values ie 0,1,2,3,4,5,6,7,8,9…..8191. So that is the total no. of fragments possible 8192 fragments. But datagram can be only as big as 2^16-1 bytes. But why are we dividing them? It doesn’t make any sense. Maybe it is trying to say that 8192 fragments need to span 65535 bytes which gives 7.99987793 as the answer.

From the image you posted and highlighted:
"The field is measured in unit of 8 bytes."

Each fragment or chunk is 8 bytes. The total datagram size is 65536 bytes, with the bytes numbered 0, 1, 2, ..., 65,535. This means there are 65536/8 = 8192 (exactly) chunks of 8 bytes each. The chunks are numbered 0, 1, 2, ..., 8191.

The division above is $\frac{2^{16}}{2^3} = 2^{13}$. That's all there is to it.

Something you might be having trouble with is how many different integers can be represented with n bits.
n = 1 (bit) : 0 or 1 -- Note that $1 = 2^1 - 1$
n = 2 (bits): 0, 1, 2, 3 -- Note that $3 = 2^2 - 1$
n = 3 (bits): 0, 1, 2, 3, 4, 5, 6, 7 -- Note that $7 = 2^3 - 1$
...
n = 8 (bits): 0, 1, 2, 3, ..., 255 -- Note that $255 = 2^8 - 1$

 

[jbriggs444]

I am not entirely certain what the question here is.

At the level of IP (which is all that we are discussing here), what we are talking about is purely the IP frame (typically 1500 octets MTU). We do not care about Ethernet framing on the outside. We do not care about UDP or TCP or whatever encapsulation might be in use on the inside.

The IP frame has an IP header and an IP payload.

We are concerned here with fragments of a notional IP payload that may be between 0 and 65535 octets in length so that this original payload is carried in multiple IP frames on the wire.

The designers of IP decided that they could squeeze three bits out of the fragment offset field if they restricted all but the final fragment to always be a multiple of 8 octets. This would guarantee are only 8192 possible starting positions for a particular fragment within the payload as a whole.

So you have fields:

Total Length: Length of this fragment, including IP header and IP payload. Not including any padding added to meet the minimum Ethernet frame size or similar. This may be somewhere between the IP header length and 65535. In practice, MTU limitations usually limit it to something less than 65535, e.g. 1500.

Fragment Offset: Position within the original payload where this particular fragment lives. Since this position will always be a multiple of eight, the fragment offset is encoded as the position divided by eight. The available positions are 0, 8, 16, ... 65520, 65528. That is a total of 8192 possible positions. [There is no fencepost problem]

More Fragments: Flag that indicates whether this fragment is the final (in position order) fragment within a fragmented IP packet. If set, the payload length (determined based on the Total Length minus the IP header length) must be a multiple of 8 octets.

Payload: For non-final fragments, this will have a length of some multiple of 8 octets. It will be drawn from an 8-octet-aligned position within the original notional payload. The Fragment Offset will reflect this position. The Total Length will allow the payload length to be determined.

For the final fragment, the payload length is not restricted to be a multiple of 8 octets. For final fragments, the fragment offset field and the payload length taken together allow the original notional IP payload length to be calculated.If you are serious about IP then at some point you will want to look at the documentation. The RFCs. They can be heavy going, but they are the source of truth.

From https://datatracker.ietf.org/doc/html/rfc791#page-11 [September 1981. The protocol has been around for a while]

Total Length:  16 bits

    Total Length is the length of the datagram, measured in octets,
    including internet header and data.  This field allows the length of
    a datagram to be up to 65,535 octets.  Such long datagrams are
    impractical for most hosts and networks.  All hosts must be prepared
    to accept datagrams of up to 576 octets (whether they arrive whole
    or in fragments).  It is recommended that hosts only send datagrams
    larger than 576 octets if they have assurance that the destination
    is prepared to accept the larger datagrams.

    The number 576 is selected to allow a reasonable sized data block to
    be transmitted in addition to the required header information.  For
    example, this size allows a data block of 512 octets plus 64 header
    octets to fit in a datagram.  The maximal internet header is 60
    octets, and a typical internet header is 20 octets, allowing a
    margin for headers of higher level protocols.

Flags:  3 bits

    Various Control Flags.

      Bit 0: reserved, must be zero
      Bit 1: (DF) 0 = May Fragment,  1 = Don't Fragment.
      Bit 2: (MF) 0 = Last Fragment, 1 = More Fragments.

          0   1   2
        +---+---+---+
        |   | D | M |
        | 0 | F | F |
        +---+---+---+

Fragment Offset:  13 bits

    The fragment offset is measured in units of 8 octets (64 bits).  The
    first fragment has offset zero.

Stepping out of the specification and into the discussion within RFC 791...

Fragmentation

    Fragmentation of an internet datagram is necessary when it
    originates in a local net that allows a large packet size and must
    traverse a local net that limits packets to a smaller size to reach
    its destination.

    An internet datagram can be marked "don't fragment."  Any internet
    datagram so marked is not to be internet fragmented under any
    circumstances.  If internet datagram marked don't fragment cannot be
    delivered to its destination without fragmenting it, it is to be
    discarded instead.

    Fragmentation, transmission and reassembly across a local network
    which is invisible to the internet protocol module is called
    intranet fragmentation and may be used [6].

    The internet fragmentation and reassembly procedure needs to be able
    to break a datagram into an almost arbitrary number of pieces that
    can be later reassembled.  The receiver of the fragments uses the
    identification field to ensure that fragments of different datagrams
    are not mixed.  The fragment offset field tells the receiver the
    position of a fragment in the original datagram.  The fragment
    offset and length determine the portion of the original datagram
    covered by this fragment.  The more-fragments flag indicates (by
    being reset) the last fragment.  These fields provide sufficient
    information to reassemble datagrams.

    The identification field is used to distinguish the fragments of one
    datagram from those of another.  The originating protocol module of
    an internet datagram sets the identification field to a value that
    must be unique for that source-destination pair and protocol for the
    time the datagram will be active in the internet system.  The
    originating protocol module of a complete datagram sets the
    more-fragments flag to zero and the fragment offset to zero.

    To fragment a long internet datagram, an internet protocol module
    (for example, in a gateway), creates two new internet datagrams and
    copies the contents of the internet header fields from the long
    datagram into both new internet headers.  The data of the long
    datagram is divided into two portions on a 8 octet (64 bit) boundary
    (the second portion might not be an integral multiple of 8 octets,
    but the first must be).  Call the number of 8 octet blocks in the
    first portion NFB (for Number of Fragment Blocks).  The first
    portion of the data is placed in the first new internet datagram,
    and the total length field is set to the length of the first[Page 8]
[HR][/HR]

September 1981
                                                       Internet Protocol
                                                                Overview
    datagram.  The more-fragments flag is set to one.  The second
    portion of the data is placed in the second new internet datagram,
    and the total length field is set to the length of the second
    datagram.  The more-fragments flag carries the same value as the
    long datagram.  The fragment offset field of the second new internet
    datagram is set to the value of that field in the long datagram plus
    NFB.

    This procedure can be generalized for an n-way split, rather than
    the two-way split described.

    To assemble the fragments of an internet datagram, an internet
    protocol module (for example at a destination host) combines
    internet datagrams that all have the same value for the four fields:
    identification, source, destination, and protocol.  The combination
    is done by placing the data portion of each fragment in the relative
    position indicated by the fragment offset in that fragment's
    internet header.  The first fragment will have the fragment offset
    zero, and the last fragment will have the more-fragments flag reset
    to zero.

For the TCP protocol, PMTUD (Path MTU discovery) is almost universally used. So the "Do Not Fragment" (DF) flag is normally set and TCP packets will normally not be fragmented. Instead, the TCP payload will be transmitted in smaller "segments".

Fragmentation is normally to be avoided. With VPN, one finds software that artificially reduces the MTU on VPN adapters. My organization does a lot of MSS clamping to avoid PMTUD black holes.

Wireshark is your friend.

 

[vela]

I agree there are 2^13 offset values ie 0,1,2,3,4,5,6,7,8,9…..8191. So that is the total no. of fragments possible 8192 fragments. But datagram can be only as big as 2^16-1 bytes. But why are we dividing them? It doesn’t make any sense. Maybe it is trying to say that 8192 fragments need to span 65535 bytes which gives 7.99987793 as the answer. But I have calculated it later, and fragmentation doesn’t work like that.

I think you're making two mistakes. First, the datagram can be 2^16 bytes in size. That's what the excerpt you quoted says, and for some reason, you decided to subtract 1.

Second, you seem to be assuming the offset 8191 has to correspond to the last possible eight-byte chunk of data. If you subtract out the 20 bytes used for the header, the data field can be 65516 bytes long. A data field of that length can be divided into 8190 eight-byte pieces, which corresponds to fragment offsets 0 through 8189. You should never see a fragment offset of 8190 or 8191.

Going the other way, you have thirteen bits for the fragment offset, so you have 8192 possible offsets. If you divide the largest possible datagram into 8192 pieces, you find that each piece needs to be eight bytes long. So if you use eight-byte chunks, you can accommodate any length data field since it's only a portion of the datagram. (Because of the overhead from the header, it doesn't follow that the largest possible data field would require all 8192 offsets.)

 

[jbriggs444]

I think you're making two mistakes. First, the datagram can be 2^16 bytes in size.

RFC 791 says 65,535.

"Total Length is the length of the datagram, measured in octets, including internet header and data. This field allows the length of a datagram to be up to 65,535 octets."

The packet format allows for the possibility of a last fragment in a 65,535 octet datagram at a fragment offset of 8191*8 = 65,528. In principle, this would allow for the possibility of creatively encoding a sequence of fragmented IP datagrams (I think you'd need at least three datagrams total) with a payload length totaling 65,528 + 65,535 - 20 = 131,043 octets. In practice, I do not think one would find many peers willing or able to accept such a monstrosity.

Edit: Googled it and found:

IP fragment overrun

The IP Fragment Overrun exploit is when a reassembled fragmented packet exceeds the declared IP data length or the maximum packet length. By definition, no IP packet should be larger than 65,535 bytes. Systems that try to process these large packets can crash, and can be indicative of a denial of service attempt.

Second, you seem to be assuming the offset 8191 has to correspond to the last possible eight-byte chunk of data. If you subtract out the 20 bytes used for the header, the data field can be 65516 bytes long. A data field of that length can be divided into 8190 eight-byte pieces, which corresponds to fragment offsets 0 through 8189. You should never see a fragment offset of 8190 or 8191.

Nicely observed.

However, it is 65,515 bytes total payload by my reckoning. Further, per RFC 791: "the minimum fragment is 8 octets" which puts the maximum fragment offset at floor((65535-20-8)/8) = 8188. Thus, you'll never see a fragment offset of 8189 either.

[A fragment offset value of 8188 is offset 65,504. With eleven payload octets in the fragment, that takes you to a payload of 65,515 octets total which, with the minimum IP header of 20 octets, takes you to the 65,535 limit]

 

[vela]

However, it is 65515 bytes total payload by my reckoning. Further, per RFC 791: "the minimum fragment is 8 octets" which puts the maximum fragment offset at floor((65535-20-8)/8) = 8188. Thus, you'll never see a fragment offset of 8189 either.

If the data doesn't have a length that's a multiple of eight, padding extends the last fragment to a length that's a multiple of eight. Couldn't that happen on chunk 8189 as well to meet the eight-octet minimum?

 

[jbriggs444]

If the data doesn't have a length that's a multiple of eight, padding extends the last fragment for a length that's a multiple of eight. Couldn't that happen on packet 8189 as well to meet the eight-octet minimum?

Padding is used on the IP header to ensure that it is a multiple of 4 octets in length. Padding is not required on the IP payload unless the higher level protocol that carries the IP datagrams requires padding.

The most common reason for padding an IP datagram is to make it long enough to meet the Ethernet minimum frame requirements. For IP datagrams that are already large enough to fulfil that requirement there is no need for padding when encapsulating them in an Ethernet frame.

There is no impediment to adding padding to an IP datagram when encapsulating it in a frame format such as Ethernet, Token Ring, Frame Relay, PPP, HDLC or whatever. The IP Total Length field allows the length of the IP payload to be recovered. The length of the higher level frame's payload can be ignored. (Or validated against the IP Total Length if one's TCP stack is being paranoid properly careful).

So I do not see padding as a way out of the 8 byte minimum fragment size.

However, the RFC is fairly quiet about the situation for the minimum fragment size on the final packet. Let me read it again.

"Every internet module must be able to forward a datagram of 68 octets without further fragmentation. This is because an internet header may be up to 60 octets, and the minimum fragment is 8 octets."

Without context, this says that the minimum fragment size is 8 octets. With context, this says that a layer 3 device with a small output MTU can expect to be generating fragments of at least 8 octets. But not more.

So let's look at the sample code in the RFC to disambiguate.

Say that we have a 60 octet internet header and a 68 octet MTU. We have 15 octets of payload to send.

" Notation:

FO - Fragment Offset
IHL - Internet Header Length
DF - Don't Fragment flag
MF - More Fragments flag
TL - Total Length
OFO - Old Fragment Offset
OIHL - Old Internet Header Length
OMF - Old More Fragments flag
OTL - Old Total Length
NFB - Number of Fragment Blocks
MTU - Maximum Transmission Unit

Procedure:

IF TL =< MTU THEN Submit this datagram to the next step
in datagram processing ELSE IF DF = 1 THEN discard the
datagram ELSE
To produce the first fragment:
(1) Copy the original internet header;
(2) OIHL <- IHL; OTL <- TL; OFO <- FO; OMF <- MF;
(3) NFB <- (MTU-IHL*4)/8;
(4) Attach the first NFB*8 data octets;
(5) Correct the header:
MF <- 1; TL <- (IHL*4)+(NFB*8);
Recompute Checksum;
(6) Submit this fragment to the next step in
datagram processing;

[So we've spit out the first 8 bytes in a fragment. Frag offset = 0, More Fragments = 1, TL = 68. 8 payload octets go out on the wire in a 68 octet IP frame]

To produce the second fragment:
(7) Selectively copy the internet header (some options
are not copied, see option definitions);
(8) Append the remaining data;
(9) Correct the header:
IHL <- (((OIHL*4)-(length of options not copied))+3)/4;
TL <- OTL - NFB*8 - (OIHL-IHL)*4);
FO <- OFO + NFB; MF <- OMF; Recompute Checksum;
(10) Submit this fragment to the fragmentation test; DONE.

[So we've dropped Total Length by 8 and we're going back to the top of the loop]

This time, TL is small enough that the final fragment can be emitted with its 7 octet payload in a 67 octet IP frame.

By this logic, the final fragment (only) can indeed have less than 8 octets. You were correct about 8189 being a potentially valid fragment offset and my overly literal reading of the RFC was not correct.