|
Welcome To
|
||||||||||||||||
|
Helping You |
||||||||||||||||
The Cisco Career
Certification Program.
|
||||||||||||||||
|
|
||||||||||||||||
|
|
||||||||||||||||
                             
|
||||||||||||||||
|
|
||||||||||||||||
|
Google XMLSiteMap |
Navigation
|
TCP/IP Checksum Ones-Complement Addition Ones-complement addition is a calculation performed on binary integers. Before defining the addition algorithm, we first look at the way in which integers may be represented in binary form. There are several alternative conventions used to represent negative as well as positive integers, all of which involve treating the most significant (leftmost) bit in the word as a sign bit. If the sign bit is 0, the number is positive; if the sign bit is 1, the number is negative. The simplest form of representation that employs a sign bit is the sign-magnitude representation. In an n-bit word, the rightmost n – 1 bits hold the magnitude of the integer.+18 = 00010010 –18 = 10010010 (sign magnitude) So, an 8-bit word can represent values in the range –127 to +127. With sign-magnitude representation, there are two representations for zero: +010 = 00000000 –010 = 10000000 (sign magnitude) This is inconvenient, because it is slightly more difficult to test for 0 (an operation performed frequently on computers) than if there were a single representation. Another drawback to sign-magnitude representation is that addition and subtraction require a consideration of both the signs of the numbers and their relative magnitudes to carry out the required operation. Like sign magnitude, ones complement representation uses the most significant bit as a sign bit, making it easy to test whether an integer is positive or negative. It differs from the sign magnitude representation in the way that the other bits are interpreted, which leads to simpler algorithms for addition and subtraction. We need to distinguish between an operation and a representation. To perform the ones complement operation on a set of binary digits, replace 0 digits with 1 digits and 1 digits with 0 digits.X = 01010001 ones-complement of X = 10101110 Y = 10101110 ones-complement of Y = 01010001 Note that the ones-complement of the ones-complement of a number is the original number. The ones-complement representation of binary integers is defined as followed. Positive integers are represented in the same way as in sign-magnitude representation. A negative integer is represented by the ones-complement of the positive integer with the same magnitude. +18 = 00010010 –18 = ones-complement of +18 = 11101101 Note that because all positive integers in this representation have the left-most bit equal to 0, all negative integers necessarily have the leftmost bit equal to 1. Thus the leftmost bit continues to function as a sign bit. In ordinary arithmetic, the negative of the negative of a number gives you back that number. This is also true in ones-complement arithmetic. –18 = 11101101 +18 = ones-complement of –18 = 00010010 As with sign-magnitude, ones-complement has two representations of zero: +010 = 00000000 –010 = 11111111 (ones-complement) We can now turn to a consideration of ones-complement addition. It should be intuitively obvious that the simplest implementation of addition for signed binary integers is one in which the numbers can be treated as unsigned integers for purposes of addition. This approach does not work for the sign-magnitude representation. For example, these are clearly incorrect: 0011 = +3 + 101 1 = –3 1110 = –6 (sign-magnitude) 0001 = +1 + 111 0 = –6 1111 = –7 (sign-magnitude) For sign-magnitude numbers, correct addition and subtraction involve the comparison of signs and relative magnitudes of the two numbers. With ones-complement addition, however, the straightforward approach, with a minor refinement, works: 0011 = +3 + 110 0 = –3 1111 = 0 (ones-complement) 0001 = +1 + 100 1 = –6 1010 = –5 (ones-complement) This scheme will not always work unless an additional rule is added. If there is a carry out of the leftmost bit, add 1 to the sum. This is called an end-around carry. 1101 = –2 + 101 1 = –4 11000 1 1001 = –6 (ones-complement) 0111 = +7 + 110 0 = –3 10011 1 0100 = +4
(ones-complement) Application to IP and TCP For the IP error detection operation, the entire header of an IP datagram is treated as a block of 16-bit binary integers in ones-complement representation. To compute the checksum, the checksum field in the header is first set to all zeros. The checksum is then calculated by performing ones-complement addition of all the words in the header, and then taking the ones complement operation of the result. The identical computation is performed for TCP. In this case, the computation is performed on the words comprising the segment header, the segment data, plus a pseudoheader that includes the following fields from the IP header: source address, destination address, TCP's protocol identifier, and the length of the TCP segment. If the segment contains an odd number of octets, the last octet is padded out on the right with zeros to form a 16-bit word. As with the IP algorithm, the checksum field is set to zero for the calculation. TCP is a transport-layer protocol. It needs to sit on top of a network-layer protocol, and was designed to ride atop IP. (Just as IP was designed to carry, among other things, TCP packets.) Because TCP and IP were designed together and wherever you have one, you typically have the other, the entire suite of Internet protocols are known collectively as ``TCP/IP.'' TCP itself has a number of important features that we'll cover briefly. Guaranteed Packet DeliveryProbably the most important is guaranteed packet delivery. Host A sending packets to host B expects to get acknowledgments back for each packet. If B does not send an acknowledgment within a specified amount of time, A will resend the packet. Applications on host B will expect a data stream from a TCP session to be complete, and in order. As noted, if a packet is missing, it will be resent by A, and if packets arrive out of order, B will arrange them in proper order before passing the data to the requesting application. This is suited well toward a number of applications, such as a telnet session. A user wants to be sure every keystroke is received by the remote host, and that it gets every packet sent back, even if this means occasional slight delays in responsiveness while a lost packet is resent, or while out-of-order packets are rearranged. It is not suited well toward other applications, such as streaming audio or video, however. In these, it doesn't really matter if a packet is lost (a lost packet in a stream of 100 won't be distinguishable) but it does matter if they arrive late (i.e., because of a host resending a packet presumed lost), since the data stream will be paused while the lost packet is being resent. Once the lost packet is received, it will be put in the proper slot in the data stream, and then passed up to the application.
|
