An arriving fragment can fill any of the existing holes in a number
of ways. Most simply, it can completely fill a hole. Alternatively, it
may leave some remaining space at either the beginning or the end of an
existing hole. Or finally, it can lie in the middle of an existing
hole, breaking the hole in half and leaving a smaller hole at each end.
Because of these possibilities, it might seem that a number of tests
must be made when a new fragment arrives, leading to a rather
complicated algorithm. In fact, if properly expressed, the algorithm
can compare each hole to the arriving fragment in only four tests.
4
We start the algorithm when the earliest fragment of the datagram
arrives. We begin by creating an empty data buffer area and putting one
entry in its hole descriptor list, the entry which describes the
datagram as being completely missing. In this case, hole.first equals
zero, and hole.last equals infinity. (Infinity is presumably implemented
by a very large integer, greater than 576, of the implementor's choice.)
The following eight steps are then used to insert each of the arriving
fragments into the buffer area where the complete datagram is being
built up. The arriving fragment is described by fragment.first, the
first octet of the fragment, and fragment.last, the last octet of the
fragment.
1. Select the next hole descriptor from the hole descriptor
list. If there are no more entries, go to step eight.
2. If fragment.first is greater than hole.last, go to step one.
3. If fragment.last is less than hole.first, go to step one.
- (If either step two or step three is true, then the
newly arrived fragment does not overlap with the hole in
any way, so we need pay no further attention to this
hole. We return to the beginning of the algorithm where
we select the next hole for examination.)
4. Delete the current entry from the hole descriptor list.
- (Since neither step two nor step three was true, the
newly arrived fragment does interact with this hole in
some way. Therefore, the current descriptor will no
longer be valid. We will destroy it, and in the next
two steps we will determine whether or not it is
necessary to create any new hole descriptors.)
5. If fragment.first is greater than hole.first, then create a
new hole descriptor "new_hole" with new_hole.first equal to
hole.first, and new_hole.last equal to fragment.first minus
one.
5
- (If the test in step five is true, then the first part
of the original hole is not filled by this fragment. We
create a new descriptor for this smaller hole.)
6. If fragment.last is less than hole.last and fragment.more
fragments is true, then create a new hole descriptor
"new_hole", with new_hole.first equal to fragment.last plus
one and new_hole.last equal to hole.last.
- (This test is the mirror of step five with one
additional feature. Initially, we did not know how long
the reassembled datagram would be, and therefore we
created a hole reaching from zero to infinity.
Eventually, we will receive the last fragment of the
datagram. At this point, that hole descriptor which
reaches from the last octet of the buffer to infinity
can be discarded. The fragment which contains the last
fragment indicates this fact by a flag in the internet
header called "more fragments". The test of this bit in
this statement prevents us from creating a descriptor
for the unneeded hole which describes the space from the
end of the datagram to infinity.)
7. Go to step one.
8. If the hole descriptor list is now empty, the datagram is now
complete. Pass it on to the higher level protocol processor
for further handling. Otherwise, return.
4. Part Two: Managing the Hole Descriptor List
The main complexity in the eight step algorithm above is not
performing the arithmetical tests, but in adding and deleting entries
from the hole descriptor list. One could imagine an implementation in
which the storage management package was many times more complicated
than the rest of the algorithm, since there is no specified upper limit
on the number of hole descriptors which will exist for a datagram during
reassembly. There is a very simple way to deal with the hole
descriptors, however. Just put each hole descriptor in the first octets
6
of the hole itself. Note that by the definition of the reassembly
algorithm, the minimum size of a hole is eight octets. To store
hole.first and hole.last will presumably require two octets each. An
additional two octets will be required to thread together the entries on
the hole descriptor list. This leaves at least two more octets to deal
with implementation idiosyncrasies.
There is only one obvious pitfall to this storage strategy. One
must execute the eight step algorithm above before copying the data from
the fragment into the reassembly buffer. If one were to copy the data
first, it might smash one or more hole descriptors. Once the algorithm
above has been run, any hole descriptors which are about to be smashed
have already been rendered obsolete.
在网上看到淘宝的一个面试题，实现会议室预订系统。类似会议室预订的，还有汽车出租系统，本质上都是都某个资源的时间占用问题。
我们排除一些细节问题，把问题缩小为某一天去预订一个会议室，在没有发生任何预订的情况下，这个会议室的时间片是一段连续的时间【00:00:00】到【23:59:59】，我们称之为时间片ST。
新产生的预订可能从中间切分ST，生成两段新的时间片。例如，预订时间是【08:00:00】到【09:000:00】，那么会切分出【00:00:00】到【07:59:59】，【09:00:01】到【23:59:59】。也可能刚好从时间片的开头占用，或者占用到时间片的结尾，或者是占用完整的时间片。
随着越来越多的预订，剩下的可以被占用的时间片将是被占用时间分割开的一个个小的时间片，当新的会议室请求到来时，我们要从这一个个时间片中寻找可以满足预订要求的时间片（即时间片的开始时间<=会议预订的开始时间&时间片的结束时间>=会议预订的结束时间），找到满足要求的时间片后，把这个旧的时间片基于当前的占用时间进行切分。
最近看IP相关的资料时，发现在rfc815中提供的重组机制竟然和自己之前为实现会议室预订系统的算法惊人地相似，下面是具体的逻辑：