Let's look at other physical layer protocols. - almost every computer has a serial port - you can connect a serial cable to the port and connect a modem - you can use the modem to dial another modem, and you have a network! host -- modem -------------------------- modem -- host - by the way, a modem is short for "Modulator, De-modulator", and transforms digital output from your computer into analog transmission for a telephone line. A popular protocol for serial lines: SLIP (Serial Line Internet Protocol) - used to transmit TCP/IP data over serial lines. The protocol: 1. Each packet is terminated by a the C0 character (i.e., 11000000) - some implementations put a C0 at the beginning as well, to terminate any data generated by line noise. 2. If a byte in the IP packet is C0, it is replaced with two characters: DB and DC (11011011 11011100). 3. If a byte has a DB in it, it is replaced with DB and DD. Example: original packet: ---------------------------------------- | | c0 | |db | | ---------------------------------------- packet sent by slip: ------------------------------------------------------- | | db | dc | |db | dd | | c0 | ------------------------------------------------------- Disadvantages: 1. No "type" field, so it cannot be used for two protocols at the same time. 2. No checksum. Advantage: Quick and easy! --------------------- Another serial line protocol: CSLIP (Compressed SLIP) - Invented because serial lines are often slow side note: to carry one byte of TCP/IP data, TCP will put on a 20-byte header, and IP will put on a 20-byte header. That's 41 bytes to deliver 1 byte of data! - CSLIP reduces the 40-byte headers to 3 or 5 bytes - It does that by keeping state information about the headers. - we'll revisit this again when we see IP and TCP headers. --------------------- Another serial line protocol: PPP (the Point-to-point protocol) PPP has three components: 1. A component that transmits packets over a serial link 2. A "link control protocol" that allows each end to negotiate options; and 3. A family of "network control protocols" that are specific to different network layer protocols. PPP can be used with IP, OSI, DecNet, Appletalk, etc. PPP frame: bytes: 1 1 1 2 0-1500 2 1 ___________________________________________________________ | flag | addr | control | protocol | data | crc | flag | | 7E | FF | 03 | | | | 7E | ------------------------------------------------------------ - Each frame starts and ends with 7E. - Followed by FF and then 03 - The crc is a checksum of the entire packet - The protocol can be: 0021 - means the data is an IP datagram C021 - means the data is link control data, and is meant for the PPP software, not the higher layers 8021 - the data is network control data, specific to higher-layer protocols. Note: there is no length field. So, if 7E (i.e.,the end byte) appears in the data, it will be misinterpreted. So.... 1. if 7E is in data, it is replaced with 7D5E 2. if 7D is in data, it is replaced with 7D5D 3. All bytes less that hex 20 are also escaped: 0x01 is sent as 0x7D21 0x02 is sent as 0x7D22 0x03 is sent as 0x7D23 ... 0x10 is sent as 0x7D30 ... 0x1F is sent as 0x7D3F Reason: some modems interpret 00 to 20 specially. The link control protocol of PPP: 1. used to negotiate to omit the constant addr and control fields. - reduces the size of the frame 2. also used to negotiate to reduce protocol field to 1 byte. The network control protocol of PPP: 1. negotiates protocol-specific things 2. for IP, it is used to negotiate header compression like CSLIP uses. Let's look at Data-link layer functionality. The most common error-detecting method: The Polynomial Code or Cyclic Redundanvy Code (CRC) Here's how it works: 1. A packet comtains a bit string 2. We represent the bit string as a polynomial with coefficients of 0 and 1 only. - a k-bit packet is represented as a polynomial with k terms. it is said to be of degree (k - 1). Example: 1 1 0 1 0 1 1 0 1 1 Because there are 10 bits, represent it as a polynomial of degree 9. The rightmost bit is associated with x^0, the next as x^1, the next as x^2, and so on. So, represent that as a polynomial: 9 8 7 6 5 4 3 2 1 0 1 * x + 1 * x + 0 * x + 1 * x + 0 * x + 1 * x + 1 * x + 0 * x + 1 * x + 1 * x And that comes out to be: 9 8 6 4 3 1 x + x + x + x + x + x + 1 3. Polynomial arithmetic is done modulo-2; there are no carries for addition and no borrows for subtraction. So, both addition and subtraction are identiacal to "exclusive-or". Examples: 10011011 11110000 + 11001010 - 10100110 -------- --------- 01010001 01010110 4. Both sender and receiver agree on a "generator polynomial" (let's call it G(x)). Both high-order and low-order bits of G(x) must be 1. Example: 4 G(x) = x + x + 1 That has 5 terms: 1 0 0 1 1 4 3 2 1 0 ==> 1 * x + 0 * x + 0 * x + 1 * x + 1 * x The degree is 4. 5. Here's how the checksum works: a. Let's say the packet has m bits. b. Let r be the degree of G(X). c. Append r 0-bits to the low-order end of the packet, so the packet contains (m + r) bits. Note: if the polynomial associated with the frame was M(X), it is now (x^r * M(x)) d. divide the bit string corresponding to G(X) into the bit string corresponding to (x^r * M(X)), using modulo-2 division. e. Subtract the remainder from the bit string corresponding to (x^r * M(X)), using Modulo-2 subtraction. f. The result is the checksummed packet to send! Example: Packet: 1 1 0 1 0 1 1 0 1 1 4 G(X) = x + x + 1 Generator is: 1 0 0 1 1 Modified packet: 1 1 0 1 0 1 1 0 1 1 0 0 0 0 (the original packet plus 4 0's) Now do the division: 1 1 0 0 0 0 1 0 1 0 _____________________________ 1 0 0 1 1 ) 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 --------- 0 1 0 0 1 1 1 0 0 1 1 --------- 0 0 0 0 0 1 0 0 0 0 0 --------- 0 0 0 0 1 0 0 0 0 0 0 --------- 0 0 0 1 0 1 0 0 0 0 0 --------- 0 0 1 0 1 1 0 0 0 0 0 --------- 0 1 0 1 1 0 1 0 0 1 1 --------- 0 0 1 0 1 0 0 0 0 0 0 --------- 0 1 0 1 0 0 1 0 0 1 1 --------- 0 0 1 1 1 0 <- This is the remainder! So, subtract the remainder from the (x^ * M(X)): 1 1 0 1 0 1 1 0 1 1 0 0 0 0 - 1 1 1 0 --------------------------- 1 1 0 1 0 1 1 0 1 1 1 1 1 0 And that's what you transmit! So you send "1 1 0 1 0 1 1 0 1 1 1 1 1 0" to the pier. Note that we send the original packet with 4 extra bits. The 4 extra bits is the checksum! Now, let's call the thing we transmit "T(x)". T(x) is evenly divisible by G(x). - Because in any division, if you dimish the dividend by the remainder, the amount left is divisible by the divisor! So, when the receiver gets the bits, they divide it by G(x) (i.e., 10011), and the result should have no remainder! If the result has no remainder, the receiver says the packet passed the checksum! The receiver chops off the last 4 bits and send the packet up to the next layer.