Category:
Customize My Settings Edit My Profile Register To Join Search Forums Main Page Forum Help Login To The Forums
Author
Message Text For:
Clock Driven Scheme to Initialize the Sequence Number
By Chong Kim
Navigation:

Discussion
Date Posted: Tuesday February 04, 2003 01:50:38 PM
Email Thread
Using TCP to deal with delayed duplicates of both old and new connections

Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Saturday February 08, 2003 07:01:16 AM
Email Thread
I am Chong Kim (email: kyongchongkim@yahoo.co.uk), the author of the article "Clock Driven Scheme to initialize the sequence number". I have discovered a couple of minor mistakes in my article. There are as follows:
In "The evaluation of m - case (1)",
the equation (1) should be
y = a.tx + m - MSSW + 2 (inclusive) --- (1)
the equation (3) should be
y = a(t1 + dt) + MSRW - 1 (inclusive) --- (3)
Then you will finally have
m >= a.MSL + MSSW + MSRW - 2
( or m>= a(MSL - B + C)+ MSSW + MSRW - 2 )
( I hate this -2 !!)

I apologize for this mistake. I am no good at adding and subtracting! The equations (1), (2) and (3) are vital for my theorem or theory. If any of them does not hold, the whole house collapes!

In addition, I would like to make the following additional statements in the Conclusion section. If you are familiar with Computer Networks, you already know them :

(1) Note that C is zero if the sending host is part of the subnet (i.e. the internet). For TCP/IP, the clock for the life time of the data octet begins to tick from the moment the data octet is passed by TCP of the sending host to its IP layer.

(2) It has crossed my mind that the communication developers for TCP have so far managed without knowing the lower boundary of the m value in my theorem. I assume that they have taken a few times larger MSL than ture MSL (i.e. the true maximum life time of a packet in the network) so that their m value is safely larger than the lower boundary of the m value in my theorem.

Thanks.


Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Monday February 10, 2003 10:32:22 AM
Email Thread
I am Chong Kim (the author of the article "Clock Driven Scheme to initialise the sequence number). I have something to add to the conclusion part of the article. It is as follows:

We know that with TCP/IP the sending TCP aborts its connection if a data octet has been retransmitted a number of times and its acknowledgement still does not come. For example, in case (1) the sequence number of the possible lower boundary of the sender's window at t=tx is
y = a.tx + m - MSSW + 2 --- (1)
Clearly the data octet emitted at t = tx with this sequence number is a duplicate and might have already been retransmitted a number of times. With large(?!) MSSW, the sequence number of the possible lower boundary of the sender's window should be higher than y in (1). Otherwise, the data octet with the sequence number y in (1) has been retransmitted too many times and the sender has already aborted the connection. Simple calculations using the diagram in case (1) show that, for MSSW > a.WT (i.e. the sender emits a new data octet at time t = t1 and at t = t1 + WT its acknowledgement is not coming and the sender retransmits the data octet last time), the sequence number of the lower boundary of the sender's window should be higher than y in (1) and consequently our lower boundary of m is unnecessarily a bit too large ( i.e. for the correct lower boundary of m with MSSW > a.WT, let the equation (1) be y = a.tx + m - a.WT + 2 and so we will have m >= a.MSL + a.WT + MSRW - 2 or m >= a(MSL - B + c) + a.WT + MSRW - 2). In my theory or theorem, for the generality sake, the number of retransmissions allowed before the sender aborts the connection has not been limited. So it ensures that, regardless of the size of MSSW, the lower bounday of m in my theory or theorem still guarantees that a delayed data octet of an old connection is rejected by the receiver if it arrives at the receiver.

If you diagree with me on this, let me know your view. Please email to kyongchongkim@yahoo.co.uk. Thanks!

Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Tuesday February 11, 2003 09:00:19 AM
Email Thread
I am Chong Kim (the author of the article "Clock Driven Scheme to initialize the sequence number"). This is the third time that I reported my mistakes in the article. I must confess that I am no good at adding and subtracting. The mistakes are with the equations (1) and (3) in "The evaluation of m - case (1)". I believe that
the equation (1) should be
y = a.tx + m - MSSW + 2 --- (1)
and the equation (3) should be
y = a(t1 + dt) + MSRW --- (3)
Then we will have m >= a.MSL + MSSW + MSRW -1
or m = a(MSL - B + C) + MSSW + MSRW -1

If the sender's ASC(1)is allowed to touch FZB, the equation (1) will be
y = a.tx + m - MSSW + 1
This will give us
m >= a(MSL - B + C) + MSSW + MSRW
( much better because I can get rid of -1 !!).


I sincerely apologize for this third update. As I said, Iam no good at adding and subtracting!! You could expermiment with the equations (1), (2), (3) and (4) to see if there still are mistakes. If you do find some, would you please let me know (kyongchongkim@yahoo.co.uk)? Odd numbers to add or subtract would make little difference, I believe.

Thanks.

Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Tuesday February 18, 2003 05:43:17 AM
Email Thread
It is me again, Chong Kim (the author of Clock Driven Scheme).
I had a look at my own article again. It puzzled me that the receiver makes no contribution to increase the lwer boundary of m value in my formula. So I tried "The evaluation of m - case (1)" with a different approach. The result is that the formula for m should be altered. First we define A= the largest time taken by a data octet to travel from the last gateway/router of the subnet (i.e. Internet) to the receiver, B=the shortest time taken by a data octet between its birth at the sender and its arrival at the receiver, and C=the largest time taken by a data octet between its birth at the sender and its arrival at the subnet. Then euqations (1), (2), (3) & (4) change as follows:
(c.f. replace t1+dt with ty in the diagram by the way!)

y = a.tx + m - MSSW + 2 (inclusive) --- (1)
ty - tx <= MSL + C + A --- (2)
y = a(ty - B) + MSRW (inclusive) --- (3)
( Imagine that the data octet of the new connection emitted at t=ty-B has just arrived at the receiver of the new connection at t = ty)
m >= a(ty-tx-B) + MSSW + MSRW -1 --- (4)

So we have finally m>= a(MSL + C + A - B) + MSSW + MSRW -1
(or m >= a(MSL + C + A -B) +MSSW + MSRW if ASC is allowed to touch FZB).
We may take B = zero since it will safely raise the lower boundary of m. For TCP/IP, the sender and receiver are TCPs of hosts while the subnet includes IPs of the sending and receiving hosts. So for TCP/IP, (A+C) may be relatively small.

I do not like this new formula because the sender using the Clock Driven Scheme now has to know a factor concenring the receiver, i.e. A. However, it seems unavoidable.

Finally it was difficult to determine the upper boundary of the receiver's sliding window at t = ty exactly. The lower boundary of m using the equation (3) is quite safe. But we can still lower it. The factors such time taken by the receiver to process the incoming data octet and to move the sliding window up can lower the upper boundary of the receiver's window at t = ty. It will lower the lower boundary of m in my formula. However, they are non-deterministic. For generality sake, I have ignored these factors. I have even assumed that the receiver can receive two data octets at the same time and move the window up before the sencond one is put on the window. One probably has to be a hardware and operating system engineer to argue about this kind of thing.

Many thanks. If you have been confused, email to me (kyongchongkim@yahoo.co.uk) and I will send you a copy of my updated file. My update dfile is much easier to read and understand.



Reply
Top
Bottom
Next
Previous

Discussion
Date Posted: Tuesday March 25, 2003 12:25:10 PM
Email Thread
Hi I am Chong Kim (the author of the Clock Driven Scheme to initialize the sequence number).
Hopefully this is the last time I made an ammendment to my article.
In the "Evaluation of m - Case (1)", I would like to add -1 to y value in the equation (3). So we have
y = a(ty - B) + MSRW -1 --- (3)
The reason for this should be self-explanatory. Then the equation (4) becomes
m >= a(MSL + C + A - B) + MSSW + MSRW -2
( or m >= a(MSL + C + A - B) + MSSW + MSRW - 1 if ASC is allowed to touch FZB)
I have tried very hard to eliminate this -2 from the formula so that the formula would look neat. I have failed.

Thanks!!

Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Thursday June 26, 2003 08:54:55 AM
Email Thread
I am Chong Kim (the author of this article).

I have a proposal to make regarding what to do when ASC approaches FZB. We know that TCP aborts the connection when the data octet(s) has been retransmitted a number of times, i.e. duplicates, but its acknowledgement does not arrive. Let's say that the sending TCP may wait for the maximum time T since it emitted the data octet(s) for the first time before the abortion of the connection. During this time T, a number of retransmissions take place if an acknowledgement does not arrive. What we could do is that, when ASC is at least T units in t away horizontally from FZB, the sending TCP initiates the resynchronization of the sequence number with the receiving TCP. This ensures that ASC never enters FZ. That is, either the sender aborts the connection because none of the resynchronization packet of the sender and its possible retransmissions has been acknowledged before time T elapses or the resynchronization is successful before ASC meets FZB. With this scheme, we can do some arithmetic to raise the possible minimum sequence number of the data octet in (1) in "The evaluation of m - case (1)", which will lead to a smaller lower boundary of our m (i.e. Let S = the maximum waiting time after the last retransmission of a packet. (i) If we allow the sender to initiate the resynchronization before all the data octets emitted earlier are acknowledged, the sender emits the resynchronization packet at least T away horizontally from FZB. For this, if MSSW >= a(T - S) + 1, add (a×T - 1) to (1) in "The evaluation of m - case (1)", which will make the lower boundary of our m smaller by (a×T - 1 ) . In this case, do not forget to replace MSSW with (a×WT+1) or a(T - S )+1. If MSSW < a(T - S) + 1, add (MSSW + a×S - 2) to (1) in "The evaluation of m - case (1)", which will make the lower boundary of our m smaller by (MSSW + a×S - 2). Of course, with the same scheme, there are other ways to make the lower boundary of our m smaller. For example, the sender may emit the resynchronization packet at least (T - S) away horizontally from FZB. In this case, ASC may enter FZ but, while ASC is progressing horizontally in FZ, no data octet whether duplicate or not is emitted. For this, if MSSW >= a(T-S) + 1, add a(T-S) -1 to (1) in "The evaluation of m - case(1)", which will make the lower boundary of our m smaller by a(T-S) -1. If MSSW < a(T-S) + 1, add (MSSW-2) to (1) in "The evaluation of m - case(1)", which will make the lower boundary of our m smaller by (MSSW-2). (ii) Suppose that all data octets should be acknowledged before the sender initiates the resynchronization. Then when ASC is at least 2×T away horizontally from FZB, the sender sends no more new data octets and waits until all the data octets are acknowledged, after which the sender emits the resynchronization packet while ASC is at least T away horizontally from FZB. ) I have assumed that the horizontal width of FZ is relatively large (with T relatively very small to the t range ) so that the sender can not afford to remain idle while ASC progresses horizontally in FZ until it exits from FZ (i.e. I have heard that, in one implementation of TCP, the horizontal width of FZ is set to a value larger than 3 minutes! Suppose that the horizontal width of FZ is 4 minutes and the clock cycles every 10 hours. Suppose that ASC can enter FZ horizontally. Then, with a security system using TCPs that run day and night, the system may stop working for 4 minutes every some hours which is smaller than a small multiple of 9 hours and 27 minutes. What about a bank service till machine that occasionally stops working for 4 minutes every few days or once a day? ). Or if the maximum waiting time S after the last retransmission of a packet is larger than the horizontal width of FZ, we do not need FZB at all. In this case, the sender initiates the resynchronization when ASC is horizontally T away from ISC (after the clock cycles). FZ is implicit in this case. I do not suppose that such S is implemented. If such S is implemented, we can also make the lower boundary of our m smaller using the previous arguments above.

Also in "The evaluation of m - case (1)", we do not consider any data octet, whether duplicate or not, emitted before t = t1 - MSL - C - A + B exclusive because such a data octet will not exist in the network after t = t1+B inclusive ( i.e. after the new connection opened at the receiver ).


Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Monday September 22, 2003 10:06:56 AM
Email Thread
I am Chong Kim (the author of this article).

There may be ways to put arbitrary upper boundaries to A and C for practical purposes (c.f. the lower boundary of m increases as A and C increase ). For example, in TCP/IP, we may introduce a scheme that the host monitors time taken to move a data octet between its TCP and its IP and, if the time taken exceeds the given upper boundary, the host abandons the data octet. We assume that the time taken is almost always small in practice but the worst case scenario possible in theory leads to too high upper boundaries for A and C. We use this scheme to determine an acceptable lower boundary of m by choosing practical upper boundaries for A and B arbitrarily. For example, suppose that x is our upper boundary for A (i.e. the max time taken to move a data octet from the receiving host's IP to its TCP) where x is a small constant very likely to be much smaller than the theoretical upper boundary for A. If the receiving host has taken longer than x in time to move a data octet from its IP to its TCP, the receiving host abandons the data octet. In a similar scheme, we may arrange that, when an IP packet forms in the sending IP, its birth time is not zero but the time taken to move the data octet from the sending TCP to the sending IP. We also arrange that, when the IP packet arrives at the receiving TCP, the receiving host lets (the life-time of the data octet) = (the IP packet's life-time when it gets to the receiver's IP) + (time taken to move the data octet from the receiver's IP to the receiver's TCP). In this alternative scheme, if the receiving host finds that the life-time of the data octet, when it arrives at the receiver's TCP, is larger than MSL + x1( i.e. an upper boundary for A ) + x2( i.e. an upper boundary for C) or than T (i.e. the smaller of the two), the host throws out the data octet. If T is the smaller of the two, (2) in "The evaluation of m - case (1)" simply becomes ( ty - tx <= T). Note that, in these two schemes, upper boundaries for A and C greater than T are pointless where the sending TCP aborts the connection if there is no acknowledgement of a data octet ( not its duplicates ) from the receiving TCP for time T. For example, in the second scheme, if the life-time of a data octet when it arrives at the receiving TCP is greater than T, it is pointless that the receiving TCP processes the data octet and sends its acknowledgement. Note that, if the host usually takes longer than T to move a data octet between its IP and its TCP, upper boundary values for A and C larger than T makes no difference to the situation where the connection is very likely to be aborted because too many acknowledgements come too late.


Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Monday September 22, 2003 10:06:57 AM
Email Thread
I am Chong Kim (the author of this article).

There may be ways to put arbitrary upper boundaries to A and C for practical purposes (c.f. the lower boundary of m increases as A and C increase ). For example, in TCP/IP, we may introduce a scheme that the host monitors time taken to move a data octet between its TCP and its IP and, if the time taken exceeds the given upper boundary, the host abandons the data octet. We assume that the time taken is almost always small in practice but the worst case scenario possible in theory leads to too high upper boundaries for A and C. We use this scheme to determine an acceptable lower boundary of m by choosing practical upper boundaries for A and B arbitrarily. For example, suppose that x is our upper boundary for A (i.e. the max time taken to move a data octet from the receiving host's IP to its TCP) where x is a small constant very likely to be much smaller than the theoretical upper boundary for A. If the receiving host has taken longer than x in time to move a data octet from its IP to its TCP, the receiving host abandons the data octet. In a similar scheme, we may arrange that, when an IP packet forms in the sending IP, its birth time is not zero but the time taken to move the data octet from the sending TCP to the sending IP. We also arrange that, when the IP packet arrives at the receiving TCP, the receiving host lets (the life-time of the data octet) = (the IP packet's life-time when it gets to the receiver's IP) + (time taken to move the data octet from the receiver's IP to the receiver's TCP). In this alternative scheme, if the receiving host finds that the life-time of the data octet, when it arrives at the receiver's TCP, is larger than MSL + x1( i.e. an upper boundary for A ) + x2( i.e. an upper boundary for C) or than T (i.e. the smaller of the two), the host throws out the data octet. If T is the smaller of the two, (2) in "The evaluation of m - case (1)" simply becomes ( ty - tx <= T). Note that, in these two schemes, upper boundaries for A and C greater than T are pointless where the sending TCP aborts the connection if there is no acknowledgement of a data octet ( not its duplicates ) from the receiving TCP for time T. For example, in the second scheme, if the life-time of a data octet when it arrives at the receiving TCP is greater than T, it is pointless that the receiving TCP processes the data octet and sends its acknowledgement. Note that, if the host usually takes longer than T to move a data octet between its IP and its TCP, upper boundary values for A and C larger than T makes no difference to the situation where the connection is very likely to be aborted because too many acknowledgements come too late.


Reply
Top
Bottom
Next
Previous

kyongchongkim
Date Posted: Monday November 24, 2003 06:11:39 AM
Email Thread
Hello I am the author of this article, Chong Kim. I wish to revise my Clock Driven Scheme to initialize the sequence number or Clock Driven ISN as follows:

The equation (1) in "The evaluation of m - case (1)" should be y = a×tx + m - MSSW (Maximum Size of the Sender's Window) + 1 + a×z (inclusive) --- (1) where 0 <= z and the emission of a data octet takes place until ASC(1) is z away horizontally from FZB, after which ASC(1) may progress horizontally without data emission until the resynchronization is complete and ASC(1) is below ISC again. Choose such z that y can be an integer for some tx. If z is any arbitrary number, our lower boundary of m can be slightly higher than the true lower boundary of m. The we have m >= a(MSL + C + A - B - z) + MSSW + MSRW - 1

If a is a real number but not an integer, then we may have a problem with choosing the initial sequence number (ISN) from ISC. There may be several ways to deal with this. One way can be that, if ISN from ISC is not an integer, the sender (i.e. the sending TCP) waits for a few clock ticks or units until the sequence number from ISC becomes an integer. For example, suppose that a = ½ and the sender wishes to chooses ISN from ISC at t = 1 but ISN = ½ at t = 1. In this case, the sender waits until t = 2 and so ISN becomes 1. Another way can be that, if ISN from ISC is not an integer, then we truncate ISN into the nearest integer. In the above example, the sender chooses 0 at t = 1. This ensures that ASC remains below ISC until the clock cycles. In this case, the equation (3) in "The evaluation of m - case (1)" may become y = a(ty - B) + MSRW - 1 - d where 0 <= d < 1 and, since a is known, d can be determined easily at the time the sender (i.e. the sending TCP) opens the new connection.


If you would like to have my article in a Microsoft Word file, email to me (kyongchongkim@yahoo.co.uk). I will email one to you. I welcome any feedback from a reader.


Reply
Top
Bottom
Next
Previous
Navigation:

[ACM]   [Ubiquity]   [ACM Privacy Policy]