# How can a 13 bit number represent 16 bit number?

• Comp Sci
• shivajikobardan
In summary, the conversation discusses the concept of IPv4 fragmentation and the confusion surrounding it. The discussion delves into the different fields of an IPv4 header and how they relate to fragmentation, as well as solving numerical problems to understand the concept better. The conversation also touches on the importance of understanding the position or offset of fragments, using a dummy example to explain it. There is also a mention of the number of fragments possible and how they are divided into chunks of 8 bytes. The conversation concludes with a summary of the confusion and the need for further clarification on the concept.
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.

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

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

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

shivajikobardan said:
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##

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.

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]

Code:
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
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.
Code:
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 |
+---+---+---+
Code:
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...

Code:
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

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.

Last edited:
shivajikobardan said:
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.)

vela said:
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.

https://en.wikipedia.org/wiki/IP_fragmentation_attack said:
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.

vela said:
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]

Last edited:
vela
jbriggs444 said:
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?

vela said:
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
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;
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;
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.

Last edited:
berkeman

## 1. How does a 13 bit number represent a 16 bit number?

A 13 bit number can represent a 16 bit number by using a technique called zero-padding. This means that the missing 3 bits in the 13 bit number are filled with zeros to make it a 16 bit number.

## 2. Can a 13 bit number accurately represent all 16 bit numbers?

No, a 13 bit number cannot accurately represent all 16 bit numbers. It can only accurately represent numbers within its own range, which is from 0 to 8191 (2^13 - 1).

## 3. Why would a 13 bit number be used to represent a 16 bit number?

A 13 bit number may be used to represent a 16 bit number in situations where memory space is limited. By using only 13 bits instead of 16, less memory is required to store the number.

## 4. How is the conversion from a 13 bit number to a 16 bit number done?

The conversion from a 13 bit number to a 16 bit number is done by adding 3 zeros to the left side of the 13 bit number. This effectively shifts the number to the left and fills in the missing bits with zeros.

## 5. Is there any loss of information when converting from a 13 bit number to a 16 bit number?

Yes, there is a loss of information when converting from a 13 bit number to a 16 bit number. This is because the 3 extra bits in the 16 bit number cannot be accurately represented by the 13 bit number, so they are filled with zeros instead.

• Engineering and Comp Sci Homework Help
Replies
5
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
7
Views
915
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Programming and Computer Science
Replies
1
Views
627
• Engineering and Comp Sci Homework Help
Replies
8
Views
1K
• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Programming and Computer Science
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
6K