 | The identity of the application sending the data |
| The identity of the application that should receive the data |
| A checksum |
Name
|
Bit Size
|
Purpose
|
Source Port
|
16
|
The source port number. |
Destination Port
|
16
|
The destination port number. |
Sequence Number
|
32
|
The sequence number of the first data octet in this segment unless the SYN control bit is set. If the SYN control bit is set, then the sequence number is the initial sequence number (ISN) and the first data octet is ISN+1. |
Acknowledgment Number
|
32
|
This portion of the header contains the value of the next sequence number that the sender of the segment is expecting to receive if the ACK control bit is set. Once a connection is established, this is always sent. |
Data Length
|
4
|
The number of 32-bit words in the TCP header. This indicates where the data begins. |
Reserved
|
6
|
Reserved for future use. It has to be zero. |
Flags
|
6
|
The bits from left to right.URG: Urgent Pointer field
significant ACK: Acknowledgment field significant PSH: Push function RST: Reset the connection SYN: Synchronize sequence numbers FIN: No more data from sender |
Window
|
16
|
The number of data octets beginning with the one indicated in the acknowledgment field, which the sender of this segment is willing to accept. |
Checksum
|
16
|
The checksum field is the 16-bit 1’s complement of the 1’s complement sum of all 16-bit words in the header and data. |
Urgent Pointer
|
16
|
This field communicates the current value of the urgent pointer as a positive offset from the sequence number in this segment. The urgent pointer points to the sequence number of the octet following the urgent data. This field is interpreted only in segments that have the URG control bit set. |
Options
|
variable
|
Options may occupy space at the end of the TCP header and are a multiple of 8 bits in length. All options are included in the checksum. |
Padding
|
variable
|
The TCP header padding is used to ensure that the TCP header ends and data begins on a 32-bit boundary. The padding is composed of zeros. |
Name
|
Bit Size
|
Purpose
|
Source Port
|
16
|
The source port number. |
Destination Port
|
16
|
The destination port number. |
Length
|
16
|
The length in octets of this user datagram including the header and data. |
Checksum
|
16
|
The checksum field is the 16-bit 1's complement of the 1's complement sum of all 16-bit words in the header and data. The checksum is an option in the UDP header and not always used. |
Name
|
Bit Size
|
Purpose
|
Version
|
4
|
The format of the Internet header. |
IHL
|
4
|
Internet header length is the length of the Internet header in 32-bit words. The minimum value for a correct header is 5. |
Type of Service
|
8
|
An indication of the abstract parameters of the quality of service desired. |
Total Length
|
16
|
The length of the datagram, measured in octets, including Internet header and data. |
Identification
|
16
|
An identifying value assigned by the sender to aid in assembling the fragments of a datagram. |
Flags
|
3
|
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. |
Fragment Offset
|
13
|
Indicates where in the datagram this fragment belongs. The fragment offset is measured in units of 8 octets (64 bits). The first fragment has offset zero. |
Time to Live
|
8
|
Indicates the maximum time the datagram is allowed to remain in the Internet system. If this field contains the value zero, then the datagram has to be destroyed. |
Protocol
|
8
|
Indicates the next level protocol used in the data portion of the Internet datagram. |
Header Checksum
|
16
|
A checksum on the header only. Since some header fields change, such as the time-to-live field, this is recomputed and verified at each point that the Internet header is processed. |
Source Address
|
32
|
The source address. |
Destination Address
|
32
|
The destination address. |
Options
|
variable
|
The options may or may not appear in datagrams. A couple of
the available options are:Security: used to carry security, compartmentation, and
handling restriction codes compatible with DOD requirements. Record Route: used to trace the route an Internet datagram takes. |
Padding
|
variable
|
The Internet header padding is used to ensure that the Internet header ends on a 32-bit boundary. The padding is zero. |
| "Marissa says that it take her "forever" to reach a host in another city…" | Use TRACERT to see the path her machine may be using to contact the other machine. You may be able to isolate a routing problem. |
| "Martha is having a problem with inconsistent data she is receiving from a network application…" | It is possible that the network application uses UDP instead of TCP. Since UDP provides unreliable "best effort" delivery, some data may be lost. You need to see if you can get her an equivalent network application that uses TCP to ensure that all data she needs arrives safely. |
| "James from the sales department tells you that he cannot communicate with a machine in the accounting department…" | You need to run the PING utility to see if the computer is operating correctly on the network. |
100010
XOR 011010
111000 Distance = 3
|
A B | A xor B 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0 |
| 000000 is a distance of 1 from 000001, a single error changes 000000 to 000001 |
What is the Hamming distance between 000000 and 111100?
| No parity | Even parity | ||||||
| 00 | m=2, r=0, d=1 | 000 | valid | m=2, r=1, d=2 | |||
| 01 | The change of any one | 001 | invalid | Adding parity doubles | |||
| 10 | bit results in a valid | 010 | invalid | the number of codewords, but | |||
| 11 | codeword. No error | 011 | valid | only half are valid. Any single bit | |||
| can be detected. | 100 | invalid | error produces an invalid code. | ||||
| 101 | valid | ||||||
| 110 | valid | ||||||
| 111 | invalid |
- What is the odd parity for the ASCII data: 11111111 and 11111110?
- Is data and parity bit 111100001 valid for even parity?
- Suppose that one million bits were sent with a single parity bit for error detection. Would a 1-bit error be detected? Would all errors in two bits be detected?
| 000000 |
| 000111 |
| 111000 |
| 111111 |
- What was sent if 000011 is received and we assume a 1-bit error occurred?
- How many errors occurred at a minimum if 011001 is received? Can it be corrected reliably? Then what to do on receiving 000011?
The following is an example of a method by Hamming for constructing a minimal single bit error correcting code. The code has m=4 data bits, thus can encode 16 data values (00002-11112), and r=3 check bits. There are seven bits numbered from 1 to 7 with four data bits (m3, m2, m1, m0) and three check bits (p2, p1, p0). Note that check bits are placed at positions numbered as a power of 2 (e.g. check bit p2 is at position 4 = 22) between data bits. Data bits can be in any order but below are arranged in standard high bit at left order. The m data (m3m2m1m0) and r check bits (p2p1p0) are then organized into a vector as follows:
- m data bits
- r check bits
- m+r+1 <= 2r
- r=3 can correct one error in m=4 data bits, since m+3+1<=23 = 8, or m=4.
- r=4 can correct one error in m=11 data bits, since m+4+1<=24 = 16, or m=11.
- r=5 can correct one error in m=26 data bits, since m+5+1<=25 = 32, or m=26.
| POSITION | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| BIT | p0 | p1 | m3 | p2 | m2 | m1 | m0 |
Data bits are checked by check bits whose position sum is equal to the position of the data bit. In this example:
m3 = p0 + p1 Position of m3 = Position of p0 + Position of p1 = 3
m2 = p0 + p2 Position of m2 = Position of p0 + Position of p2 = 5
m1 = p1 + p2 Position of m1 = Position of p1 + Position of p2 = 6
m0 = p2 + p1 + p0 Position of m0 = Position of p2 + Position of p1 + Position of p0 =7
| p2 = m2 xor m1 xor
m0 p1 = m3 xor m1 xor m0 p0 = m3 xor m2 xor m0 |
Note that the sender computes
p0, p1, p2. For example: p2 = m2 xor m1 xor m0 = 1 xor 0 xor 0 = 1 |
| C0 = p0 xor m3
xor m2 xor m0 C1 = p1 xor m3 xor m1 xor m0 C2 = p2 xor m2 xor m1xor m0 |
Note that the receiver computes
C0, C1, C2. From the above computation of p2 = 1 and no errors in p2, m2, m1, m0 C2 = p2 xor m2 xor m1xor m0 = 1 xor 1 xor 0 xor 0 = 0 |
| POSITION | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| BIT | p0 | p1 | m3 | p2 | m2 | m1 | m0 |
| TRANSMIT | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| RECEIVED | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
Computing the error vector yields (1, 0, 0) indicating that POSITION 4 (410 = 1002 of the received frame is in error and should be inverted to correct the error.3.2.2 Error Detecting Codes - To detect d errors requires a distance of d+1, no d number of errors can change a valid code into another valid code.
C0 = 0 xor 1 xor 1xor 0 = 0
C1 = 1 xor 1 xor 0 xor 0 = 0
C2 = 0 xor 1 xor 0 xor 0 = 1
ASCII code with parity, 8 data bits and 1 bit parity for error checking has a distance of two, meaning each valid code + parity is at least 2 bits different from any other valid code. All valid codes are transformed by a 1 bit error into an invalid code. The invalid code is detected as an error.
The ASCII code uses 8 data bits, so that all possible valid 8-bit codes are used. The distance is one, since each valid code is 1 bit from another valid code. Hence one error transforms any valid code to another valid code.
It is generally cheaper to detect an error and retransmit data than to send error correcting codes.A two bit error burst, such as in the underlined bits, would be detected by the parity bits when the message was reconstructed by the receiver. In general, n frames with a parity bit can detect a single n bit error burst.
Sending 1,000,000 data bits in frames of 1000 bits using error correcting Hamming codes requires 10 check bits per 1000 data bit frames or 10,000 extra bit to correct single bit errors, a total of 1,010,000 bits transmitted (i.e. m+r+1 <= 2r or 1000+10+1=1011<= 210=1024).
- Alternatively, 20 check bits could correct a 1 bit error for 1,000,000 data bits for a total of 1,000,020 bits (i.e. m+r+1 <= 2r or 1,000,000+20+1<= 220=1,048,576). Why is this a bad idea?
- A single parity bit can detect one error in a 1,000,000 bit message but the message would be retransmitted when an error was detected. Under what conditions is this a bad idea or a good idea?
Using error detection and retransmit on a detected error requires 1 parity bit per 1000 data bits or 1000 check bits for the data plus 1 additional check bit for the 1000 parity bits, a total of 1,001,001 bits transmitted error free. For 1 error per million bits, error detection and retransmit requires 1,002,002 bits to be transmitted (i.e. an additional 1001 bits retransmitted).
One key problem is the lack of robustness to error detection using parity as it can detect 100% of single bit errors but only 1/2 of more than 1 bit errors. This can be improved by observing that most errors occur in bursts and reorganizing how blocks of data are sent.
Suppose that we send two 3 bit numbers 101 and 001 with even parity, 1010 and 0011. Sending as 1010 0011, a two bit error burst might transform the underlined bits to 1100 0011 which is not detected as an error by a parity check bit. Instead of sending all of one message data bits and parity bit at once which can only detect a one bit error, a more robust approach sends the first bit of each message, then the second, etc. This provides error detection of a 2 bit burst since only one bit in each column would be changed but not any 2 bit error, better than before but not good enough. The data and parity of both is sent as:
Sending 1010 0011 would be transmitted as: 10001101. A two bit error burst in the underlined bits would be received as 10111101.
10 First bit 00 Second bit 11 Third bit 01 parity
G(x)=x4+x+1 = 10011
xrM(x) = 01100001 0000 M(x) xr
Q(x)
G(x)/ T(x)
R(x)= 1110
|
1101010
10011/011000010000
xor 10011
10110
xor 10011
10110
xor 10011
10100
xor 10011
1110 R(x)
|
|
xrM(x)
011000010000 xor R(x) xor 000000001110 T(x) 011000011110 |
1101010
10011/011000011110
xor 10011
10110
xor 10011
10111
xor 10011
10011
xor 10011
00
00
0 remainder implies no error
|
It is important to note that the data link layer of the sender adds the framing information, which is used and removed by the receiver's data link layer. From the network layer view, framing is transparent as the message appears to travel directly from the sender's network layer to the receiver's, since the framing information was added and removed by the corresponding data link layers. The following are common framing methods.
_ _____ Volts _______| |___| | | | | |_____________ 1 1 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 No data |B| Data 'S' ASCII code |P | E| No data time--> B = Start bit (opposite of no data representation). P = Parity bit (0 as even number of 1's in ASCII 'S' code). E = Stop bit (same as no data representation).
How would the following data be sent using character stuffing?
- ABC
- <DEL><STX>A<DEL><ETX>
How would the following data be sent using bit stuffing as described above using a framing flag of 111111?
- 0000
- 1111111111
