first_half (1).pdf

SpiNNaker Chip, composed of multiple ARM processors with a router in the middle. Deﬁnitions Router are used to connect at least 2 networks, (commonly 2 LANS or WANs or to connect a LAN and its ISP network. ROM is Read Only Memory Shared RAM is memory that is shared between multiple processors with the intent of providing inter-application communication and avoid redundant data copies. (Removes the need for I/O processors) Routing Table is a database that keeps tracks of paths and uses there to determine which was to forward tra ic. NoC I/Fs are …. Ethernet Interface is a device or card that allows a computer or mobile device to connect to a LAN using Ethernet as the transmission mechanism. Ethernet is a communication technology/medium that uses cables to transmit data. Ethernet interface can be internal which connects the routing engine to the packet forwarding components or aggregated which links multiple physical connections. System NoC is Network Operations centre responsible for network monitoring and control or network management. SDRAM Control is Synchronous Dynamic Random Access Memory is volatile memory where DRAM cells work in rhythm with the internal frequency of the CPU. The memory controller knows the time and no. of cycles after which data will be available on the bus. Identifying a packet transmission – A spike 5G: CM vs MM wave MM waves are sensitive to blockage by obstacles such as humans, furniture due to weak di raction ability. About 1-2% of the time one to 5 people, the channel was blocked. Therefore the mm wave links when taking into consideration of human mobility, they are intermittent – not steady. To tackle this problem, 1. Building blockage, high density of infrastructure required to cover areas around buildings 2. Body blockage, macro diversity users associate with multiple base stations Applications of mm wave communications: 1. Small cell Access, with huge bandwidth mm wave small cells are able to provide the multi gigabit rates. 2. Cellular access, mm wave for 5g cellular have the potential for high coverage and capacity as long as the infrastructure is densely deployed. mm Wave frequencies refer to frequency range from 20GHz to 300GHz. These frequency were designed as Extremely High Frequency, EHF band. Wavelength: 10mm to 1mm. Why is the transmission distance of 5g only 340 meters? Can 5g be used in the ﬁeld? Cm Wave: 340 meters Mm waves : 100 meters. A packet is piece of information carried around computer networks in form of packets. A packet is a sequence of bits, composed of header and body. LAN – Local Area Networks connect workstations, servers and other shared resources in a single room, building or campus. (Covering a small geographical area) WAN – Wide Area Network connects computers/multiple LANs at di erent geographic locations. We can trace route a connection from for example UK to Japan on command line using hops. Each hop represents a router*. WAN structure In wan, computers = hosts and WANs system of interconnections is called communication subnet. Protocol stacks & High level overview of network software Network software is structured as a series of layers known as protocol stack. Each layer builds on the one below and provides services to the one above. - Protocols stacks - OSI and TCP/IP reference models There are 2 standard models for network software: OSI and TCP/IP reference model 1. OSI, Open System Interconnect  Developed by ISO, International Standards Organization  Largely ignored by industry  Clean model provides good framework for discussing other systems OSI Model: OSI LAYERS: Physical Layer Provides the transmission of a stream of bits Deﬁnes physical transmission medium and signals used Provides an unreliable service (error may occur in transmission) Data Link Layer Gives a way to structure frames or blocks of data so that they can be sent and received over the physical layer bit stream. With a reliable service any errors are detected and corrected automatically. Network Layer Controls operation of subnet. May include the routing used to get packets from the source to the destination. Transport Layer True end-to-end layer from source through to destination. Supports connection-oriented service where user makes connection, communicates then ends connection (like telephone system). Session Layer Provides services useful for session-based applications such as ﬁle transfers and terminal connections. Presentation Layer Handles di erences in the binary representations of data. Supports compression and encryption. Application Layer Support for applications that operate via a network. Examples: virtual terminal, ﬁle transfer, email transfer. 2. TCP/IP, Transmission Control Protocol/ Internet Protocol    Developed with ARPANET, now used on Internet Widely used Poorly deﬁned model provides unsound basis for future development TCP/IP Reference Model TCP/IP Layers Host to Network Layer "A great void"! - No standard protocol deﬁned at this level Internet Layer Deﬁnes a standard format for packets and protocol called IP (Internet protocol). Connectionless delivery of arbitrary sized datagrams between hosts which may reside on di erent networks. No guarantees about delivery or routing. Packets may be lost, duplicated or arrive in wrong order Transport Layer Two end-to-end process-level protocols are deﬁned: TCP (Transmission Control Protocol) Reliable, connection-oriented protocol that delivers a byte stream with error correction. UDP (User Datagram Protocol) Unreliable, connectionless. Application Layer Numerous protocols are deﬁned. HTTP, FTP, TELNET, SMTP, DNS, etc. Data is transmitted via electronic signals which are carried by transmission medium which could be cable, wireless connection such as Bluetooth or WiFi. Data rate = number of bits transmitted /transmission time bps Bps – beats per second, indication of how fast ﬁle is downloaded or uploaded. Reminder: 1 Byte = 8 bits Mbps =Mega bits= 1,000,000 bps or 8,000,000 bits = 125,000 bytes MBps = Mega bytes, Example: Broadband link downloads 5,000,000 bytes in 10 seconds. Data rate is 5000000 * 8 / 10 = 4,000,000 bos = 4Mbps Side note: Max data rate of a medium aka capacity. Bandwidth is the amount of data that the transmission media can transfer per second. Latency is the delay between a device sending data and another receiving it across a network. Latency is a ected by: - No. of devices connected to network Bottlenecks that can occur when hardware operates at di erent speeds FUN FACT: Electronic signals travel at the speed of light, similar speed in copper and optical ﬁbre Example: Optical ﬁbre link which is 100km long 1. Convert to m: 100km = 100,000m 2. Transmission velocitiy is 200.000km/s = 200,000,000 m/s 3. 4. 5. Delay = 100,000/200,000,000 = 0.0005 seconds or 0.5ms To us its not very long but for a computer it can be very long to wait for a reply from the other end. Error Rate is the proportion if data that gets corrupted. An error is when a 0 changes to 1 and 1 changes to 0. Example: We transmit 1,000,000 bits of data and 10 bits get corrupted. The error rate is 1 in 100,000. Bit error probability = 10/1000000 = 0.00001 With random noise, we assume that each bit is independent therefore has equal chance of being in error. Data Transfer using Flash Drive Suppose a 2GB USB ﬂash drive is used to transfer data between two desktop PCs, one on campus and the other on the opposite side of Canterbury - capacity of ﬂash drive = 2 GB = 2 * 1024 * 1024 * 1024 bytes = 8 * 2 * 1024 * 1024 * 1024 bits - transfer time = 30 minutes (walking) = 30*60 = 1800 seconds - data rate = 8∗2∗1024∗1024∗1024 1800 = 9,544,371 bps ≈ 9.5 Mbps Note: 1 KB = 1024 bytes, 1 MB = 1024 Kbytes, 1 GB = 1024 MB Analogue Signalling An analogue signal is a continuous signal that changes over time. OR The amplitude (Strength) of an analogue signal can vary continuously. Uses: Telephone and radio communications How its transmitted: Audio data can be transmitted by varying the amplitude of an electric current or radio wave in proportion to the sound waves sensed by a microphone. Digital Signalling Digital signals are time separated signals that travel in discrete patterns. The amplitude of a digital signal is limited to a number of ﬁxed (discrete) levels. If two levels are used the lower and higher can represent 0 and 1 How is data transmitted: Data is transmitted as a stream of bits with the signal held high or low a ﬁxed interval of time for each bit. Digital Signalling – Multi Level Here we have 4 di erent voltage levels used. Each represents a di erent 2-bit chunk of data = Referred to as a symbol’. The more values we can have for a symbol, the more data we can send. Data Communications Theory This lecture describes the theory of data communications via physical transmission media, including some of the constraints.   Signal impairments - attenuation, distortion, noise Maximum data rate - Nyquist and Shannon limit Attenuation and Distortion Attenuation = to lose power Electronic signals are attenuated (lose power) as they travel through a physical medium. The shape of an electronic signal also becomes distorted. The distortion depends on the data rate and the bandwidth. Both attenuation and bandwidth depend on the quality of the physical connection and the distance travelled. Distortion vs Data Rate If we increase bps, we may get a signal that is no longer readable; able to say that there is data coming in where each curve represents a data or a 1 and a dip represents no data, 0. Nyquist Limit (for Distortion) The amount of distortion and its e ect depend on two main factors: 1. frequency bandwidth (H) in Hz = di erence between the highest and the lowest frequencies of an analogue signal that can be transmitted via the physical channel 2. number of discrete signal levels in use (V) aka quantization levels used for analogue-to-digital conversions. The more levels (higher V), the higher the precision The Nyquist limit (1924) gives the maximum safe rate beyond which distortion may cause data loss: Nyquist limit = 2 * H * log2(V) bps Note: 1 kHz = 1,000 Hz, 1 MHz = 1,000,000 Hz, 1 GHz = 1,000,000,000 Hz Example :We have a telephone channel with a bandwidth H = 3000 Hz and 4 signal levels (V=4) Nyquist limit = 2 * H * log2 (V) bps = 2 * 3000 * log2 (4) = 2*3000*2 = 12000 bps Noise Noise is unwanted power from other sources that interferes with the signal during transmission. The three most common types of noise are:    Thermal noise (a.k.a. white noise) present in all physical systems caused by random motions of individual electrons Thermal noise produces ﬂuctuations about some avg voltage that are Gaussian distributed. Cross-talk signal from one cable or channel leaking into another Cross-talk is where signals in 1 cable induce electromagnetic interference in an adjacent cable. Impulse noise intermittent bursts caused by power surges, lightning strikes Impulse noise increases/ decreases a circuits signal level, causing receiving equipment to misinterpret signal. May get errors undetectable by checksum. Noisy Signals Shannon Limit (for Noise) The amount of noise present on a physical connection is commonly expressed by the signal to noise ratio (SNR). SNR = signal power / noise power. The Shannon limit (1948) gives the maximum safe rate beyond which noise may cause data loss: Shannon limit = H * log2 (1 + SNR) bps. Shannon Limit gives accurate result for thermal noise and a reasonable approximation for cross-talk but unsuitable for impulse noise. Example: We have a telephone channel with a bandwidth H = 3000 Hz with a signal to noise ratio SNR = 255. Answer: Shannon limit = H * log2 (1 + SNR) bps = 3000 * log2 (1 + 255) = 3000 * 8 = 24000 bps Transmission Media Various physical media are used for the transmission of data. Each has its own niche in terms of capacity, delay, security, cost, etc. Communication media can broadly be divided into two categories:   Guided media: Wires, cables, ﬁbre, wave guides… Unguided media: Radio transmission, microwave, satellite … Guided Media Guided media provide a conduit between two or more nodes. A signal travelling through such a medium is directed and contained within its physical boundaries. Guided media generally take the form of cables or waveguides.    Twisted pair cable Coaxial cable Fibre optic cable Twisted Pair Cable Twisting reduces interference between adjacent cables. Widely used for telephone system and Ethernet. Bandwidth depends on thickness of wire, quality of insulation and distance involved. Several Mbps can be achieved over a few km, or higher rates over shorter lengths (e.g. 1 Gbps) Category 3 and 5 UTP Common standards for unshielded twisted pair (UTP) cable. Category 3 (Cat 3) was originally developed for the telephone system. Later used for 10 Mbps LANs. Category 5 (Cat 5) has tighter twisting, better insulation and the copper wires are of a superior quality too. Good for 100 Mbps LANs Coaxial Cable Superior shielding gives coax a higher bandwidth and greater immunity to noise than twisted pair cable. Data rates of 1 - 2 Gbps possible over 1 km of cable Fibre Optic These cables carry optical rather than electrical signals. Fibre Optic Data Rates Frequency bandwidth of optical cable is in the order of 100 THz (100,000 GHz), much higher than any form of electrical cable. Fibre optic data rates are limited by the interfaces that convert between electronic and optical signals, not by cable bandwidth. Rates of up to 100 Gbps are supported by the latest commercially-available LAN technologies. Even higher rates can be achieved over long distances using dense wavelength division multiplexing (DWDM), in which many data channels are carried simultaneously over the same ﬁbre by di erent wavelengths of light. Rates of 100 Tbps over a 50 km single-core optical ﬁbre and 1 Pbps via a 12-core ﬁbre have been demonstrated with recent R&D technology Fibre Optic Ring Network Fibre optic cables are used for LANs and WANs. Active repeater interfaces enable networks to be extended almost indeﬁnitely Fibre Optic vs Copper Cable (TP) Unguided Media Mobile users require an unguided (wireless) transmission medium. Unguided media are also useful for terrain where cables are hard to lay.     Electromagnetic spectrum Radio waves Microwaves Infrared and millimetre waves Electromagnetic Spectrum Radio Waves Radio waves are easy to generate and can travel long distances. The long range of radio waves means interference between di erent users can be a problem. Radio waves are also subject to interference from electrical equipment such as motors. Microwaves 1.Microwaves travel in straight lines and can be focused to a narrow beam using a parabolic antenna 2. Transmitting a narrow beam improves the signal/noise ratio but the transmitter and receiver must be aligned accurately. 3. Microwaves can't pass through obstacles and are adversely a ected by bad weather Satellite Transmission Uses microwave transmission via a satellite Uplink: signal transmitted from one earth station to the satellite Downlink: the satellite ampliﬁes the signal and sends it back to the other earth station (on a di erent frequency) Satellite power is from solar panels (with battery backup for night time). Example: Huawei Mate 60 Pro is the worlds ﬁrst satellite calling phone. Satellite Transmission Use: satellite television transmission      Direct To Home (DTH) or Broadcasting satellite service (BSS) Typically in the Ku band: 10.7 to 12.75 GHz downlink Mainly digital transmission these days Original DVB-S has typical data rate of around 38 Mbps Commonly run as ‘Multiple channels per carrier’ Each digital channel carries multiple TV stations Suitable for point to point transmission Video or news feeds from one TV company to another From a TV company to its terrestrial transmitters or to cable TV providers Internet access Satellite Transmission – delays and noise Challenges/Disadvantages that exist with satellite transmission:    Long delays Many of the satellites we use are ‘geostationary’ In an orbital position 35,786km directly above the equator, where they remain in the same position in the sky with respect to earth Delay from earth to satellite and back to earth is about ¼ second These delays can be problematic, as we will see later Noise A satellite dish will not only receive signals from the satellite they are pointing at but also pick up noise from space (a bit like a radio telescope) Other electrical and thermal noise can cause lots of transmission errors – which we need to address Infrared and Millimetre Waves Infrared and mm waves are widely used for short range communication such as: remote controls, wireless data ports (IRDA) and some indoor wireless LANs. Advantages: Infrared and mm have ability to pass through solid objects reduces the likelihood of interference and also makes them more secure. - Free Space Optics (FSO) - Line of sight laser links, typically between two buildings. - High data rates, e.g.: 622 Mbps to 1.2 Gbps Disadvantages: Can be problems with weather, building sway etc Summary              Radio transmissions that are on high frequencies often have large channel bandwidths. Channel bandwidth can be high Unlike guided media, radio transmission is subject to a lot more noise and interference Poor signal to noise ratio High error rates, particularly over satellite Satellite transmission can introduce long transmission delays High latency Need protocols that will cope with this Digital Communication via Telephone Telephone networks are economical means of connecting to the Internet for home, small business and mobile users. Public Switched Telephone Network Legacy technologies: dial-up Internet access Broadband (DSL, FTTX) Mobile Telephone and Broadband Networks :2G and 2.5G, 3G LTE Advanced (True 4G) , 5G (mmWave or cmWave)  Ethernet Originally had multiple machines connected to a coaxial cable. Multiple cables could be connected together using repeaters. Ethernet is the most popular cable-based LAN system. Ethernet uses CSMA/CD Later, individual machines connected to a hub or switch. The coax based ethernets are pretty much obsolete these days. Normally use UTP twisted pair cable to join individual machines to a hub or switch. 10 & 100 Mbps Ethernet Options: ethernet has many options these are just some Network delay The original 10 Mbps Ethernet allowed for 500m lengths of co-axial cable, joined together by repeaters. Up to 4 repeaters were allowed in any path, so the total network ‘diameter’ was 2500m Network delay (original 10 Mbps Ethernet) We can have:     A maximum of four repeaters involved in any path. We can cross ﬁve 500m segments, giving a maximum distance between any two computers of 2500 m. We also need to allow for the delay through the repeaters. Total maximum delay is deﬁned as being: 25.6 μs Allows for a bit of tolerance in cable lengths etc 2500m/200,000,000 m/s=12.5 us Ethernet MAC Frame Format Preamble = 10101010 repeated 7 times followed by 10101011 Length = number of bytes in data ﬁeld Data = up to 1500 bytes Pad = extra padding (added if necessary) CRC = cyclic redundancy check (CRC-32) 1) (Q) Why is a preamble needed? (A) Helps receiver detect start of frame (as opposed to no signal) 2 So receiver will know when data ends and padding/checksum begin Upper limit ensures no station can hog transmission time 2) (Q) Why is it necessary to have a minimum frame size? (A) Any shorter CSMA/CD won't work with maximum allowed cable lengths Alternative would be to reduce maximum cable lengths even further CRCs were covered earlier in data link layer segment Note that ﬁeld often referred to as "checksum" but always a CRC Ethernet frame size and padding Ethernet uses CSMA/CD We saw earlier that we need to have a minimum frame size with CSMA/CD networks, to ensure that the Collision Detection works correctly. The minimum frame size is determined by the network delay. If the network delay is t then the contention interval is 2t The transmission time for a frame must be >= 2t If we have a frame length L, a data rate D and network delay t, then: The max network delay for 10 Mbps Ethernet is deﬁned as being 25.6 μs … Padding The size of an ethernet frame with no data is only 18 bytes - Source address 6 - Destination address 6 - Length ﬁeld 2 - CRC ﬁeld 4 Smaller than the minimum required length of 64 bytes However, we have a padding ﬁeld which can be 0 to 46 bytes long For an ethernet frame with no data, we add 46 bytes in the padding ﬁeld  Padding is used for any frame less than 64 bytes long, to ensure we meet the minimum frame size needed for collision detection. Gigabit Ethernet Lecture 7: Error Detection and Correction Physical layer bit stream is likely to contain errors in transmission. An error is a change 0 1 or 1 0 and probability of an error occurring will depend on the type of network. Random bits may be corrupted in isolation or whole groups of adjacent bits a ected together May not be too important for transmission of speech. Error-Detecting Codes An error-detecting code (a.k.a. check bits) is added near the end of each frame. So, code generated by sender before transmission based on a calculation involving all of the data then Receiver performs same calculation after transmission and compares result with code in frame. If they di er then data bytes probably contain an error. Modulo 256 checksum/checksum – Error correction code summing the values of the data bytes as unsigned integers & Dividing by 256, and keeping the remainder as the checksum 1. Data bytes as unsigned 8-bit integers (in decimal) 2. Checksum (in decimal) (100+0+155+30+55+250) mod 256 = 590 mod 256 = 78 3. 590 divided by 256 = 2 remainder 78 590 mod 256 = 78 In java the mod operator is % 1. = (100+0+155+30+55+250) % 256 2. = 590 % 256 = 78 We can also implement this using a bitwise AND operator      590 % 256 = 590 & 0xFF ANDing the total with 0xFF keeps the bottom 8 bits of the result & throws any higher order bits away (59010 = 10010011102 ) (7810 = 010011102 ) keeping the remainder as the checksum Receiver performs same calculation after transmission and compares result with code in frame If they di er then data bytes probably contain an error And the pink is the remainder A hash code that's highly e ective for detecting errors Widely used in network and data storage technologies :LANs & Data stored on hard drives A hash function is any function that can be used to map digital data of arbitrary size to digital data of ﬁxed size, with slight di erences in input data producing very big di erences in output data. Examples: MD5, SHA1, SHA256 Backward Error Correction Each frame contains an error-detecting code.  Receiver: Recalculates value from data bytes received and compares with code stored in frame If equal then notiﬁes sender that frame received successfully. Else assumes data corrupt and discards frame  Sender: Retransmits any frames not received successfully  Most common approach for computer networks  Requires duplex (two-way) connection Forward Error Correction (FEC)  Each frame contains additional check bits that permit a limited number of error bits to be repaired by the receiver without retransmission  Can be more e icient than backward error correction:  If the error rate is high (e.g. noisy wireless networks)  If the propagation delay is large compared to length of a frame (e.g. satellite links)  FEC is only option for simplex (one-way) connections  FEC generally involves a larger overhead (more extra bits) than backward error correction  Example of the use of FEC for MPEG video transmission over cable TV networks This example allows the correction of up to 8 error bytes per packet. Backward error correction doesn’t work when you have a cable tv company with thousands of subscribers. Error-Correcting Codes A common FEC approach is to replace each character or block of data with a Hamming (a.k.a. block) code All valid Hamming codes must di er from each other in at least 3 of their bits (the number of bits that di er is known as the Hamming distance), e.g:    Error Correction Example Data to be sent ……………..... 01, 11, 00, 10, 11 Hamming codes sent ……….. 00111, 11110, 00000, 11001, 11110 Noisy link corrupts several bits at random during transmission Codes received ………………. 00101, 11110, 00100, 11000, 01010 Can the receiver repair these errors? Limits and E iciency a set of Hamming codes with a minimum distance of D can: - Repair errors a ecting up to (D-1)/2 bits per code (rounded down to an integer) Detect errors a ecting up to (D-1) bits per code If there are too many errors, then the repair mechanism may produce the wrong code - The number of extra bits needed to construct Hamming codes increases logarithmically with the number of data bits encoded (for a constant D) RAM with 64-bit data words needs an extra 7-bits for single bit error correction Some networks will use forward error correction ﬁrst to reduce the underlying error rate And then backward error correction to ﬁx up any errors that were missed Optimisation for Bursty Noise In situations where noise a ects multiple adjacent bits, robustness can be improved by multiplexing several Hamming codes during transmission, e.g: Receiver can correct these errors, as there’s only 1 error per codeword. STEP 1: Transmit the 1st bit of each frame in parallel STEP 2 : Transmit the 2nd bit of each frame in parallel Step 3: Transmit the 3rd bit of each frame in parallel Lecture 8: Data Link Layer, ARQ1 (Automated Repeat reQuest) Data Link Control Protocols Control protocols coordinate the exchange of data through a communications link and also the management of the link itself. Provides a reliable connection-oriented service over a duplex link. Use Backward Error Correction and bidirectional (full-duplex) data channel. Receiver can send control information back to sender. Need to ensure that all data packets received from the network layer at the sender are delivered to the network layer at the receiver in the same order with no packets lost or repeated. Stop and Wait, with positive only acknowledgement Sender, sends a frame of data and then stops and waits for a reply from the receiver. - Error Control Need a way to deal with lost or damaged frames. Positive acknowledgment Receiver responds with RR for error-free data frame(s) Any corrupt frames are discarded Retransmission after timeout Sender retransmits frame if RR not received within some time Known collectively as Automated Repeat reQuest (ARQ) mechanisms Stop-and-Wait ARQ with positive only acknowledgement Sender: transmits frame N, starts a timer and waits for RR Receiver: if frame N arrives without errors then respond with RR N+1 Receiver is saying that it expects frame N+1 next Referred to as implicit acknowledgement. Sender: If RR N+1 reaches sender before timer expires then it cancels timer and advances to next data frame. If timer expires before RR N+1 reaches sender then it retransmits frame N Example: Problems with positive only acknowledgement Two di erent errors could cause the sender not to get a RR reply :A lost data or a lost RR Problem: If the sender retransmits after a lost RR, then the receiver will get a repeated copy of the data frame. Fix : each data frame has a “sequence number”. The receiver keeps the ﬁrst copy of each data frame.Still sends an ack for repeats to keep the sender happy Performance of stop and wait Need to look at the various delays in the transmission system Round trip time 𝑡𝑟𝑡 depends on the network latency 𝑡𝑑 , the transmit time for the data frame 𝑡𝑓 and the transmit time for the RR 𝑡 lower sub r Performance of stop and wait D is the channel data rate The data frame contains H bits of header and L bits of data Tf = H + L/D - The RR contains H bits of header and no data Tr=H/D 𝑡𝑑 is the channel latency: 𝑡𝑑 = 𝑐𝑎𝑏𝑙𝑒 𝑙𝑒𝑛𝑔𝑡ℎ /𝑠𝑝𝑒𝑒𝑑 𝑜𝑓 𝑙𝑖𝑔ℎ𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑐𝑎𝑏𝑙e Round trip time 𝑡𝑟𝑡 is: 𝑡𝑟𝑡 = 𝑡𝑓 + 𝑡𝑑 + 𝑡𝑟 + 𝑡𝑑 = 𝑡𝑓 + 𝑡𝑟 + 2𝑡d E ective data rate: 𝐷𝐸 = 𝐿 / trt E iciency – LAN (scenario 1) Physical media = 100 m cable running at 1 Gbps, frame length 1000 bytes D = 1,000,000,000 bps, L = 8,000 bits, H = 48 bits 𝑡𝑑 = 100 2 × 108 = 0.5𝜇𝑠 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑐𝑜𝑛𝑑𝑠 𝑡𝑓 = 𝐻 + 𝐿 𝐷 = 8048 1000000000 = 8.048𝜇𝑠 𝑡𝑟 = 𝐻 𝐷 = 48 1000000000 = 0.048𝜇𝑠. Minimum round trip time including the RR reaching the sender 𝑡𝑟𝑡 = 𝑡𝑓 + 𝑡𝑟 + 2𝑡𝑑 = 8.048 + 0.048 + 2 ∗ 0.5 = 9.096 𝜇𝑠 Maximum e ective data throughput 𝐷𝐸 = 𝐿 𝑡𝑟𝑡 = 8000 9.096×10−6 = 0.879 𝐺𝑏𝑝𝑠 = 87.9% of physical link capacity which is right H= 48 bits is a total of 6 bytes for the header and checksum ﬁelds E iciency – WAN (scenario 2) Physical media = 100 km cable running at 1 Gbps, frame length 1000 bytes D = 1,000,000,000 bps, L = 8,000 bits, H = 48 bits 𝑡𝑑 = 100,000 2 × 108 = 500𝜇𝑠 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑐𝑜𝑛𝑑𝑠 𝑡𝑓 = 𝐻 + 𝐿 𝐷 = 8048 1000000000 = 8.048𝜇𝑠 𝑡𝑟 = 𝐻 𝐷 = 48 1000000000 = 0.048𝜇𝑠 Minimum round trip time including the RR reaching the sender 𝑡𝑟𝑡 = 𝑡𝑓 + 𝑡𝑟 + 2𝑡𝑑 ≈ 8.048 + 0.048 + 2 × 500 = 1008.096 𝜇𝑠 Maximum e ective data throughput 𝐷𝐸 = 𝐿 𝑡𝑟𝑡 = 8000 1008.096×10−6 = 7.936 𝑀𝑏𝑝𝑠 = 0.79% of physical link capacity which is incorrect Sliding Window protocols Multiple data frames are in transit simultaneously Sender can transmit up to W data frames before waiting for an acknowledgment (W = window size) Each data frame contains a sequence number in range 0.. 2k -1 where k is sequence number ﬁeld size in bits, e.g. if k = 3 then numbers = 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, etc  Receiver periodically responds with RR N where N is sequence number of next frame it expects, implicitly acknowledging all data up to (but excluding) frame N Example: Go-Back-N ARQ (Basic Version) Dealing with errorrs: 1. Sender can transmit up to W frames before waiting for RR 2. Sender starts a timer for each frame 3. While frames are arriving without errors and in correct order the receiver periodically responds with RR N (N = next frame) 4. Receiver discards bad, duplicate and out-of-sequence frames 5. If a frame is acknowledged before its timer expires then sender cancels that timer and advances to next unsent data frame 6. If a timer expires then sender goes back to frame that timed out and retransmits all frames from that point onwards Example: Lecture 9 – Sliding window protocols 2 and HDLC Go-Back-N ARQ with Negative Acknowledgment Di erence between basic Go-Back-N AND Reﬁnement of basic go-back-N ARQ The basic Go-Back-N system in the last lecture takes a while to recover from errors. Sender doesn’t realise that anything has gone wrong until the timeout expires.Although the receiver does ! Reﬁnement of basic go-back-N ARQ that speeds up error recovery when a data frame is lost or damaged ; If the receiver detects an out-of-sequence frame it responds immediately by transmitting a negative acknowledgment or reject (REJ, a.k.a. NAK) indicating which frame it expects next Example Go-Back-N ARQ (Full Version) Further improvement that speeds up error recovery when an acknowledgment or the last data frame in a sequence is lost/damaged Consider the following scenario: - Sender transmits frames 0 - 5 Receiver acknowledges all by transmitting RR 6 RR lost in transit Timer for frame 0 expires so sender retransmits all of them In full protocol the sender can transmit a special form of RR requesting the receiver to respond with another RR indicating which frame it expects next Example: Maximum Window Size for Go-Back-N ARQ Consider the following (invalid) scenario: 1. 2. 3. 4. 5. 6. Window size = 8 Sequence numbers = 0 – 7 Sender transmits frames 0 – 7 Sender receives RR 0 What should sender do next? Maximum window size for go-back-N ARQ = number of sequence numbers available - 1 = 2k -1 where k is size of sequence number ﬁeld in bits (Q) What should sender do next? (A) Problem - RR 0 ambiguous! Does it mean all frames got through and receiver ready for next batch (starting from 0 again) or none of the frames got through and sender must start from beginning (of the current batch)? 2) Hence window can't utilize all sequence numbers at the same time e.g. for this scenario k=3, 2k=8, 2k -1 = 7 so could return RR7 after receiving frames 0-6 rather than waiting for frame 7 and then returning RR0 Selective-Reject ARQ A more e icient error recovery mechanism when propagation delays are substantial (e.g. satellite links) or the error rate is high Similar to go-back-N except: 1. Only those individual frames that time out or for which a selective reject (SREJ) is returned are retransmitted 2. Receiver saves out-of-sequence frames and reassembles them in correct order when retransmitted frames arrive 3. Minimises number of retransmissions but requires extra bu er space at the receiver and more complex control logic Example: High-Level Data Link Control (HDLC) Several important network technologies employ data link protocols derived from HDLC, including:   PPP (Point-to-Point Protocol) used for broadband and dial-up connections LLC (Logical Link Control) used in IEEE 802 family of LAN standards including Ethernet (802.3) and WiFi (802.11) Supports:   Point-to-point and multidrop links (LLC handles multipoint too) Half-duplex and full-duplex links  Connection-oriented and connectionless services Frame Structure Flag…….. 011111102 - frames may be separated by 1 or more ﬂags Address.. destination - not needed for point-to-point links Control… type of frame - includes sequence number(s) Data…….. 0 or more bytes FCS…….. frame check sequence - calculated from all other ﬁelds except FLAGs Bit stu ing or byte stu ing may be used, depending on implementation Information Frames There are three categories of frame: information, supervisory and unnumbered Information frames (I-Frames) carry data In information frames the control ﬁeld contains two sequence numbers:   N(S) sequence number of this I-frame deﬁned by station that sent this frame N(R) sequence number of next I-frame expected from other station, acknowledging Iframe(s) received by station that sent this frame, i.e. acknowledgments piggybacked on data frames travelling in opposite direction Supervisory Frames carry various kinds of acknowledgment:    Receive Ready (RR) Reject (REJ) Selective Reject (SREJ) Receive Not Ready (RNR) RNR is similar to RR but tells sender not to transmit any more I-frames until further notice (receiver will transmit an RR when it is ready for more data) Control ﬁeld contains one sequence number - N(R) Unnumbered Frames Unnumbered frames (U-frames) are used for connection management and other situations where a sequence number isn't required, e.g: o o o o Set Asynchronous Balanced Mode (SABM) request to establish a data link connection Disconnect (DISC) terminate data link connection Unnumbered Information (UI) for simple connectionless data communication Unnumbered Acknowledgment (UA) acknowledges unnumbered control / information frames Example: N(S) sequence number of this I-frame deﬁned by station that sent this frame N(R) sequence number of next I-frame expected from other station, acknowledging Iframe(s) received by station that sent this frame, i.e. acknowledgments piggybacked on data frames travelling in opposite direction Lecture 10 – Media access control: Aloha & CSMA The Medium Access Control Sublayer The medium access control (MAC) sublayer is part of the data link layer. With broadcast networks we have multiple computers competing for access to a single communication channel. The channel allocation problem we need to decide who is allowed to transmit, and when Broadcast networks may connect many independent stations (computers or other devices). A single channel is available for all communication. If two or more stations transmit at the same time, their signals are garbled. This is known as collision. Collided frames will need to be retransmitted MAC Protocols for Guided LANs Many protocols exist for controlling access to a cable-based broadcast medium. We'll focus on protocols and issues associated with Ethernet. - Aloha - Carrier sense multiple access (CSMA) protocols CSMA with collision detection (CSMA/CD) Collision-free protocols Ethernet Gigabit Ethernet Pure Aloha Each sender transmits data frames at arbitrary times If two or more senders transmit at once, there will be a ‘collision’. The receiver sends an acknowledgement via a separate return channel if the data frame is received ok. If no acknowledgment is received, the sender waits a random time before transmitting it again Collisions in Continuous Timing A frame collides if any part of it overlaps another frame A frame will only collide if the other is sent within one frame time (t) before or after its start The vulnerable period for each frame is therefore twice the individual frame time (2t) BOTH WASTED! Loading and Throughput Loading (G) can be expressed as the number of frames o ered for transmission per frame time. This means all attempts to transmit a frame, including retransmissions. Throughput (S) can be expressed as the number of frames o ered for transmission per frame time that reach their destination successfully. Throughput is a ected by loading and varies between protocols. Slotted Aloha Time is divided into slots and stations may only begin transmission at the start of a slot This reduces the period of collision vulnerability to a single frame time and so improves throughput Aloha Throughput vs Loading Throughput versus loading for pure and slotted Aloha Graphs based on a simple statistical model of station activity CSMA Protocols With CSMA (Carrier Sense Multiple Access) protocols, stations wishing to transmit data must ﬁrst monitor the channel for other tra ic. Approaches: 1. 1-Persistent CSMA. Monitor channel continuously and transmit frame as soon as it is quiet. If collision occurs wait a random time before monitoring again. 2. Nonpersistent CSMA. Similar, but if channel busy then wait a random time before starting to monitor it again. 3. P-Persistent CSMA. As 1-persistent but transmit with probability p, otherwise defer until the next slot. (Probabilities applied using a random number generator.) CSMA Throughput vs Loading Comparison of throughput versus loading for various protocols Graphs based on a simple statistical model of individual station activity CSMA with Collision Detection (CSMA/CD) CSMA can be further improved by enabling stations to detect collisions between frames while they are still being transmitted. Aborting a corrupted frame quickly saves time and bandwidth. 1-Persistent CSMA/CD can be in one of three states: Binary Exponential Back-O Algorithm After collision occurs, time is divided into short slots of duration 2, where  is the maximum propagation delay. Each contending station initially waits either 0 or 1 slot times at random before trying again (but always listening ﬁrst). Another collision will occur if two stations choose the same delay, in which case the above process is repeated but doubling the range of random numbers after each successive collision, viz: 1. after collision #1: wait 0 or 1 slot times at random 2. after collision #2: wait 0, 1, 2 or 3 slot times at random 3. after collision #3: wait 0, 1, 2, 3, 4, 5, 6 or 7 slot times at random The upper limit is frozen after 10 collisions at 1023. Transmission will be aborted after 16 collisions. Example - - T=0) All attempt to transmit Frames collide; transmissions aborted Each station backs o for 0 or 1 slots (at random) T=1)Two stations backed o for 0 slots Frames collide; transmissions aborted Each station backs o for between 0 and 3 slots (at random) T=2)Stations that originally backed o for 1 slot now try again Collisions longer back o s T=3)Station D is only station trying to transmit at this time Transmission times of other stations dispersed Station D successfully transmits frame T=4)Station A back-o delay expires It senses channel now busy and reverts to normal CSMA behaviour (i.e. waiting for channel to become quiet) CSMA/CD: Propagation Delay vs Frame Duration Frame duration must be greater than twice the maximum propagation delay for CSMA/CD collision detection mechanism to work Left: CSMA/CD over a long distance 1. A transmits a frame to B… 2. B got the urge to send a frame just before the frame from A reached it At that moment the cable at B is silent - Hence B will transmit its frame… 3. B will detect the collision quickly because the frame from A reaches it almost immediately 4. However, A won't hear the collision until some time later due to the propagation delay 5. CSMA/CD collision detection requires sender to hear collision while it's still transmitting its frame otherwise it won't know the burst of noise was related to its own frame… 6. To prevent this failure we need to limit the cable length and/or increase the frame duration  Right: CSMA/CD is functioning correctly 7. As before, A transmits a frame to B and shortly before it arrives B starts to transmit it's frame… However, unlike before, the frame from B reaches A while A is still transmitting 8. Hence the collision detection mechanism will work in this case To prevent this failure we need to limit the cable length and/or increase the frame duration Right: CSMA/CD is functioning correctly 9. As before, A transmits a frame to B… 10. and shortly before it arrives B starts to transmit it's frame… 11. However, unlike before, the frame from B reaches A while A is still transmitting Hence the collision detection mechanism will work in this case Collision-Free Protocols adopt an entirely di erent approach that ensures collisions never occur. In the basic bit-map protocol, stations reserve slots for their frames in a contention period prior to transmission: - The contention period contains a ﬁxed number of 1-bit slots, one for each station in the network. Each station is identiﬁed by a unique number X. If station X has data to send, it transmits a 1 during contention slot number X. All stations monitor the contention period and can therefore work out when it is their turn to transmit a frame. Basic Bit-Map Protocol Example 1. There are 8 stations in this example (numbers 0-7) 2. Each contention period contains 8 x 1-bit slots 3. Initially stations 1, 3 and 7 have data to send 4. Next stations 1 and 5 have data to send 5. The above diagram isn't drawn to scale Each frame may be thousands of bits long Collision-Free vs CSMA Protocols Collision-free protocols Are: - relatively ine icient when the load is light Cope well under heavy loading conditions CSMA protocols: - Perform well under light loading conditions Su er from relatively long delays at high loads Lecture 11 – Ethernet Ethernet (IEEE 802.3) Ethernet originally had multiple machines connected to a coaxial cable Multiple cables could be connected together using repeaters. Ethernet is the most popular cablebased LAN system. Ethernet uses CSMA/CD Later, individual machines connected to a hub or switch The coax based ethernets are pretty much obsolete these days. Normally use UTP twisted pair cable to join individual machines to a hub or switch. 10 & 100 Mbps Ethernet Options: a few of them, there’s many more Network delay The original 10 Mbps Ethernet allowed for 500m lengths of co-axial cable, joined together by repeaters. Up to 4 repeaters were allowed in any path, so the total network ‘diameter’ was 2500 m Network delay (original 10 Mbps Ethernet) We can have: A maximum of four repeaters involved in any path. We can cross ﬁve 500m segments, giving a maximum distance between any two computers of 2500 m. We also need to allow for the delay through the repeaters. Total maximum delay is deﬁned as being: 25.6 μs Allows for a bit of tolerance in cable lengths etc 2500m/200,000,000 m/s=12.5 us Ethernet MAC Frame Format Preamble = 10101010 repeated 7 times followed by 10101011 Length = number of bytes in data ﬁeld Data = up to 1500 bytes Pad = extra padding (added if necessary) CRC = cyclic redundancy check (CRC-32) 1. 2. 1. 2. 3. 4. Why is a preamble needed? Helps receiver detect start of frame (as opposed to no signal) So receiver will know when data ends and padding/checksum begin Upper limit ensures no station can hog transmission time Why is it necessary to have a minimum frame size? Any shorter CSMA/CD won't work with maximum allowed cable lengths Alternative would be to reduce maximum cable lengths even further 5. CRCs were covered earlier in data link layer segment Note that ﬁeld often referred to as "checksum" but always a CRC Ethernet frame size and padding Ethernet uses CSMA/CD We need to have a minimum frame size with CSMA/CD networks, to ensure that the Collision Detection works correctly. The minimum frame size is determined by the network delay. If the network delay is t then the contention interval is 2t The transmission time for a frame must be >= 2t If we have a frame length L, a data rate D and network delay t, then: 𝐿 ≥ 2𝑡𝐷 or 𝑡 ≤ 𝐿 2𝐷 The max network delay for 10 Mbps Ethernet is deﬁned as being 25.6 μs … 𝐿 ≥ 2 × 25.6 × 10−6 × 10 × 106 𝐿 ≥ 512 bits or 64 bytes Padding The size of an ethernet frame with no data is only 18 bytes (Ignoring the preamble …) Source address 6 Destination address 6 Length ﬁeld 2 CRC ﬁeld 4 Smaller than the minimum required length of 64 bytes However, we have a padding ﬁeld which can be 0 to 46 bytes long For an ethernet frame with no data, we add 46 bytes in the padding ﬁeld Padding is used for any frame less than 64 bytes long, to ensure we meet the minimum frame size needed for collision detection. Twisted pair ethernet and hubs There was an early move away from the coaxial shared bus Ethernets The ﬁrst being 10baseT , Still 10 Mbps, but over point to point twisted pair cable.     Each computer plugged into a port on a multi port repeater, called a hub. The hub retransmits all data frames to all ports. As with repeaters, this is done at the physical layer (bit level). The data is just cleaned up and ampliﬁed. Ethernet Switches It builds up a table of which computers are on which ports, so it knows which port to send each outgoing frame to. Better security and better throughput. We now have separate segments, so not no longer competing to use a single bus. The switch watches incoming frames, and looks at the source address to see which computers are on which ports. A switch examines the destination address in each frame header. The frame is only retransmitted to the destination computer's port. Circuit Switching Circuit Switching is…. Network delays with higher data rates Can look at what happens if we move to 100 Mbps Ethernet If we keep the same minimum frame size of 512 bits (64 bytes), then what is the maximum allowable delay t over the network? 𝑡 ≤ 𝐿 2𝐷 𝑡 ≤ 512 2×100×106 hence: 𝑡 ≤ 2.56 𝜇𝑠 The smaller maximum network delay makes it hard to build large networks with multiple repeaters. Solution was to allow shorter cable lengths and only 1 or 2 repeaters or we just use Ethernet switches Gigabit Ethernet (IEEE 802.3z) : Operates at 1000 Mbps (1 Gbps) Two alternative conﬁgurations: Multidrop: computers connected to a hub Uses CSMA/CD but with a larger minimum frame size Switched: all links are now point-to-point and full-duplex CSMA/CD not needed Extending the frame size for Gigabit Ethernet … Two new features have been added to the Gigabit Ethernet MAC layer: Carrier extension: a set of special symbols are transmitted after the end of short MAC frames to increase the length to 4096 bit times. Frame bursting : several short MAC frames can be transmitted by a node once it has access to the network - this therefore reduces the overhead that would otherwise by imposed by carrier extension. Both are driven by the need to increase the length of transmission so that it’s as long as the contention interval. If Gigabit Ethernet kept to the existing minimum frame size of 512 bits, then the contention interval would be 512 ns, or a max network delay of 256 ns. Which would mean very tight limits for cable length Beyond Gigabit Ethernet For switched / point-to-point links only (no CSMA/CD) Applications include: High speed LAN backbones Backplanes for blade servers Alternative to WAN links (avoids packet conversion) Cabling options: Huge variety including several proprietary technologies Copper can be used for short distances but requires superior cabling Only optical ﬁbre is suitable for longer distances Multiple cost/performance options available for each rate Notes : 1. Channels refers to the number of parallel lanes or wavelengths used 2. Cat 6a and Cat 8 are forms of twisted pair copper cable with shielding 3. Twinaxial is a form of coaxial copper cable with two cores Lecture 12 – Wireless LANs MAC Protocols for Wireless LANs Wireless LANs such as IEEE 802.11 use di erent medium access protocols to Ethernet.  Why CSMA/CD is unsuitable for wireless LANs  CSMA with Collision Avoidance (CSMA/CA)  Multiple Access with Collision Avoidance for Wireless (MACAW)  IEEE 802.11 Wireless LAN standards (Wi-Fi) Wireless LAN Conﬁgurations [ Broadband routers often contain a WiFi access point ] Why not use CSMA/CD (Collision Detection )? The CSMA/CD protocol used by Ethernet is unsuitable for wireless LANs because: 1. Radio transceivers normally can't receive and transmit at the same time. Hence a collision can't be detected while the transmission is still in progress. 2. Radio signals aren't conﬁned to a private medium. Transmissions may be picked up from users in other wireless LANs. 3. The stations in a wireless LAN aren't necessarily all in range of each other. CSMA with Collision Avoidance (CSMA/CA) 1. A station with data to send monitors the channel continuously. 2. When it becomes quiet, the station enters a delay state for a random period of between 0 and 7 short slots. 3. The station transmits its frame if the channel is still quiet when the delay ends. 4. If, during a delay state, the channel becomes busy again, the station pauses its delay until the channel becomes quiet again. 5. A collision may occur if two stations choose the same random delay. In this event both stations initiate another random delay of between 0 and 15 short slots. 6. The maximum random delay doubles with each successive collision (binary exponential back-o algorithm). CSMA/CA Contention Example 1. B and C waiting for A to ﬁnish 2. A ﬁnishes; B starts 2 slot delay; C starts 3 slot delay 3. B starts sending; C detects transmission and suspends delay 4. A and C waiting for B to ﬁnish 5. C resumes delay (1 slot remaining); A starts 4 slot delay 6. C starts sending; A detects transmission and suspends delay IEEE 802.11 MAC Frame Format Control = type of frame (data, RTS, CTS, etc.) Duration = time needed for transmission (microseconds) Addresses = of source, destination and base-stations Seq = sequence number Data = up to 2312 bytes per frame Range Problems A transmitting to B. What would happen if C had data to send to B? Hidden station problem. B transmitting to A. What would happen if C had data to send to D? Exposed station problem. Multiple Access with Collision Avoidance for Wireless (MACAW) MACAW is a handshake protocol designed to operate with CSMA/CA on wireless networks where the hidden station problem may arise. The idea is that stations with data to send must ﬁrst stimulate the intended receiver to broadcast a short control frame which notiﬁes its neighbours that it's about to receive a (long) data frame, so they can avoid interfering with it. The MACAW Protocol Suppose station A wishes to transmit to station B: 1. A transmits a short request to send (RTS) frame to B, which indicates the size of the forthcoming data frame. 2. B responds with a short clear to send (CTS) frame, also contains copy of A’s forthcoming data frame size. 3. A then transmits its data frame. 4. B responds with an acknowledgment (ACK) frame. 5. Any other station overhearing A’s RTS or B's CTS will remain quiet until the above transaction is complete. MACAW Protocol Example RTS+CTS handshake notiﬁes all other stations in range of A or B that a data transmission is about to occur MACAW Timing Example IEEE 802.11 Wireless LAN Standards Most use CSMA/CA and MACAW protocols Main bands IEEE802.11b/g/n/ax   GHz ISM band ISM = Industrial, Scientiﬁc and Medical o to 2.45 GHz 11 to 14 channels, 22 MHz bandwidth each Shared with other uses, such as: Microwave Bluetooth IEEE802.11a/h/j/n/ac/ax : 5.03 to 5.99 GHz Permitted channel use is country dependent. Channels have 10 to 160 MHz bandwidth   Bands and Channels Most Wi-Fi mobile devices support both radio bands (2.4 and 5 GHz) Each band is divided into multiple channels Wireless networks in the same vicinity can be set to di erent channels so they don't interfere with each other The 2.4 GHz band has a better range but can be congested and is prone to interference from other kinds of radio-based device The 5 GHz band o ers greater capacity but is not currently supported by all network devices Some Wi-Fi access points/broadband routers operate both bands concurrently Cheaper access points are typically 2.4 GHz only Past exam question: Consider a very simple framing protocol with the following features: Frames are delimited by a ﬂag byte at both ends equal to the character F. Byte stu ing is used with an escape code equal to the character E. No checksum or other ﬁelds (just the ﬂags bytes, any escape bytes and the data payload). The maximum frame size is 8 bytes (characters) including the ﬂag bytes and any escape bytes. Encode the message DEEP-FRIED-WAFFLES as e iciently as possible with this protocol. Write each frame on a separate line. [6 marks] FDEEEEPF F-EFRIF FEED-WAF FEFEFLF FEESf Lecture 13 – Network Layer The Network Layer - Functions Routing packets of data from a source to a destination across a subnet. Applies to point-topoint networks. Not a problem with broadcast networks. Managing congestion in the subnet :    Packets can potentially arrive at di erent routers from di erent directions. Transferring packets across di erent types of interconnected networks Di erent networks may use di erent Data Link layer and Physical Layer technologies The Network Layer - Services Design goals for the Network Layer: Services o ered to the Transport Layer should be independent of the network technology.    Provide a uniform addressing scheme Use same address format across di erent networks. Shield the Transport Layer from the underlying network characteristics. Classes of service Connectionless service (Datagram).   Unreliable delivery of data from end-to-end. Higher layers do error correction and ﬂow control... Similar to the postal service. Connection-oriented service (Virtual Circuit).    Reliable delivery of data from end-to-end. Provides error correction and ﬂow control. Similar to the telephone service. Route calculation Dynamic or Adaptive Paths calculated periodically. Calculation based on current network measurements. Bandwidth, delay etc Distributed Every router calculates best forward paths. Paths can change as packets go from router to router. Distance Vector Routing  Uses distance vector tables  Distance and direction to all destinations.  Adjacent routers exchange these tables to discover where all the destinations are. Distances can be based on:  hops, link queue lengths or link delay. Link delay can be measured by timing echo packets between adjacent routers. Distributed Bellman-Ford and Ford-Fulkerson e.g. node C receives the vectors from its three neighbours (A, B & E). Add on the delay to the neighbour in each case and choose best route Propagation of routes 1. 2. 3. 4. Routes take time to be discovered and settle down (convergence). Here routes to router A from all other routers are discovered. Here we can see how routes propagate. This simple example has ﬁve routers connected in a line, each with a delay of 1 from each other A initially only knows about B, other routers are unknown so are given a delay of ∞ 5. After the ﬁrst cycle, B will tell A about C 6. After the second cycle, B will also tell A about D, which B previously found out about from C After the third cycle, B will also tell A about E, which B previously found out about from C, who previously found out about from D 7. Updates about new nodes happen quite quickly Count to inﬁnity problem a. Its rather slower when things fail b. B initially knows the distance to A is 1 via A c. Then the link between A and B fails In the ﬁrst cycle d. However, B is told (by C) that it can get to A in 2 via C e. B therefore decides it can get to A via C in 3 f. In the second cycle g. B still believes it can get to A via C in 3 h. i. j. k. l. m. n. C however is now being told by A that the route to A via B is 3 So C decides it can still get to A via B in 4 In the third cycle B is being told by C that it can get to A via C in 4 So B decides it can get to A via C in 5 One solution to this problem is referred to as ‘Split horizon’ Here we don’t relay paths back to a neighbour who we received them from What is a split horizon? 1. Never send routing information back in the direction from which it was received. 2. The R3 router broadcasts routing information about the 10.0.0.0/16 network to the R2 router. The R2 router receives this information, updates its routing table and broadcasts the information to the R1 router. When the R1 router receives this information, it updates its own routing table.  if the R2-to-R3 link fails and the R2 router receives a packet from R1 that's destined for the 10.0.0.0/16 network, the R2 router will send the packet back to R1 because the router advertised a viable network path. But the R1 router will simply return the packet to the R2 router based on its own routing information, resulting in a routing loop that continues until the packet expires. 3. With split horizon in place, the R1 router will not advertise the network route to the R2 router, preventing the routing loop from occurring. Lecture 14 – Link State Routing & Fragmentation Link State Routing     Based on Dijkstra’s shortest path (SPT) algorithm. Alternative to Distance Vector routing. Dynamic Distributed or centralised A little Graph Theory... We want to ﬁnd a path from, say, vertex A to vertex F. Ideally we would like to ﬁnd the shortest path. Starting from the source A: grow a tree of shortest paths to ALL destinations, to get a Shortest Path Tree rooted at A. Dijkstra’s shortest paths tree Initialise … 1. Add the root A to the tree: 2. T = ( A ) 3. Visited nodes are shown as a ﬁlledin circle in the diagram. 4. Other nodes are unvisited: 5. U = ( B, C, D, E, F ) 6. Record for each node: Current distance to root Unknown, so set to inﬁnity Node we came via to get there Unknown, so set as undeﬁned Current node is A Calculate distance to each of A’s neighbours. If new distance < current, then update distance and via. New distance to: B=2, C=1 Both currently inﬁnity, so update Find unvisited node with the smallest distance. In this case it is C (distance 1) So, add C to the tree T = (A,C), U = (B,D,E,F) Current node is C Distance to C’s unvisited neighbours. Distance to B = 1 + 2 = 3 Currently 2, so no change Distance to E = 1 + 2 = 3 Currently inﬁnity, so update Unvisited node with the smallest distance. Add B to the tree T = (A,C,B), U = (D,E,F) Current node is B Distance to B’s unvisited neighbours. Distance to D = 2 + 5 = 7 Currently inﬁnity, so update Distance to E = 2 + 3 = 5 Currently 3, so unchanged Find unvisited node with the smallest distance. Add E to the tree T = (A,C,B,E), U = (D,F) Current node is E Distance to E’s unvisited neighbours. Distance to D = 3 + 1 = 4 Currently 7, so update Distance to F = 3 + 2 = 5 Currently inﬁnity, so update Unvisited node with the smallest distance. Add D to the tree T = (A,C,B,E,D), U = (F) Current node is D Distance to D’s unvisited neighbours. Distance to F = 4 + 5 = 9 Currently 5, so unchanged Unvisited node with the smallest distance. Add F to the tree T = (A,C,B,E,D,F), U = () No unvisited nodes left so we’ve ﬁnished... Routes from A to all other nodes Path lengths:  B=2  C=1  D=4  E=3  F=5 Link State Routing Routers need to know entire network topology. Routers calculate delay or cost to neighbours. Link state data FLOODED throughout the network. All routers learn the network topology. Forwarding routes for data packets can then be calculated using Dijkstra’s SPT algorithm. Maximum packet size for each subnet Packet size may be limited because of … Constraints imposed by the hardware: e.g Ethernet max frame size (of 1500 bytes)  Probability of a frame error increases with its size : an issue when physical layer has a high error rate. If we need to carry real time tra ic:  Large packets cause long queuing delays in routers.  Large packets can hog a shared channel for a long time and cause other packets to have to wait.  Protocols may have constraints.  Any ‘payload size’ ﬁeld will have a set number of bits. Dealing with di erent maximum packets sizes Max packet size in subnets crossed may vary. A big packet may start life on subnet with a large max packet size. It later needs to be routed over another subnet whose max packet size is much smaller.... Possible for some virtual circuit subnets to allow the maximum packet size to be ‘negotiated’. Might be possible to negotiate-down to a maximum size that will work for all the subnets being crossed. Although this might cause ine icient transmission on the other subnets. Alternatively, we could ‘fragment’ large packets into a series of smaller ones Fragmentation Transparent fragmentation Non-transparent fragmentation Re-assembly Need to re-assemble the fragments back into the original packet.       Fragments may be of various lengths. They may arrive out of sequence. Some may be missing. Some fragments themselves get fragmented. Need to know how we ﬁt the fragments back together correctly. Need some way to label each fragment. Various methods possible … Fragment o set labelling Internetwork routing Here we are looking at how we route packets between the “Multiprotocol routers”. With data carried between them over the subnets. We now how two levels of routing: The routing within each individual subnet. The ‘interior gateway* protocol’ Internetwork routing between the multiprotocol routers The ‘exterior gateway protocol’. Gateway = router Above is an example of An internetwork and its graph, used for internetwork routing Here, each of the coloured areas is a subnet. The hexagons, labelled with letters are the multiprotocol routers that link the subnets together We build a graph with the multiprotocol routers as the nodes; the edges are the potential connections between these nodes over the subnets We can then perform routing on this graph, between the multiprotocol routers, using the subnets to carry tra ic between them. We will look brieﬂy later on at the protocols the Internet uses for the interior and exterior gateway protocols Lecture 15 – Internet Protocol Header ﬁelds VER (4-bits) IP Version – e.g. 4 for IPV4 HLEN (4-bits) Length of header in 32-bit words Service Type (8-bits) Di Serv Code Points (6 bits) Allows di erent IP datagram ‘precedence’ Explicit Congestion Notiﬁcation (2 bits) Used to indicate packet has experienced congestion Total Length (16-bits) Total size of IP datagram in bytes including both the header ﬁelds and any data Fragmentation header ﬁelds Identiﬁcation (16-bits) : which packet the fragment belongs to. Flags (3-bits) DF – do not fragment MF – more fragments to follow Fragment O set (13-bits) : Where in the datagram this fragment belongs (in multiples of 8 bytes) We multiply this value by 8 to get the byte o set of the fragment from the start of the packet Time to live (8-bits) : Decremented by each router - the datagram is deleted if the TTL ﬁeld ever hits 0. Used to kill packets that might otherwise wander around the Internet forever (e.g. caused by a routing error). Protocol (8-bits) : Speciﬁes the high level protocol type that the datagram contains. e.g. 6 = TCP, 17 = UDP Header checksum (16-bits) : Checksum created from all the header ﬁelds of the datagram. Options : Various option ﬁelds, such as specifying source routing, or recording routes across the network. Class based allocation: Classes of IP Addresses Networks have numbers, so do hosts. An IP address is the combination of network and host number. Five classes of addresses; A,B,C,D and E, each 32 bits long. Class based allocation: Routing 1. Routing in the Internet done on the basis of the network number. Only need to look at the host number when we get the destination network. With the original address ‘Classes’. 2. Look at the top 4 bits of the address to ﬁgure out what ‘class’ the address is. 3. Then extract out the appropriate group of bits for that class that give us the network number. Class based allocation: Addressing problems Routers know about local hosts and other networks Class A networks (126) can address 2^24=16 million hosts each Class B networks (16382) can address 2^16=64K hosts. Class C networks (2 million) can each address 2 ^ 8=256 hosts. Network class sizes are far from being ideal. Need half way house, between Class B and Class C. Classless Interdomain routing (CIDR) Moves away from Class based allocation. Instead, allocate blocks of 2n addresses, with each block starting on a 2n boundary. Say we’re allocated a block of 2048 addresses (for 2048 hosts). With the range 194.24.0.0 to 194.24.7.255 Block written as 194.24.0.0/21 Where 194.24.0.0 is the base address of the block Classless Inter Domain routing (CIDR) – subnet mask We have the block of addresses: 194.24.0.0/21 We now create the ‘subnet mask’ for this block. This is a 32 bit number with the top 21-bits set to 1 and the rest of the bits set to 0. Mask for the above written as 255.255.248.0 Arrow towards 21 is referring towards 194.24.0.0/21 CIDR address masking We have the block of addresses: 194.24.0.0/21 Take any address falling with the block E.g. 194.24.3.5 11000010 00011000 000000011 00000101 Bitwise AND the address with the subnet mask And we get the base address of the block. TICK Hence 194.24.3.5 is within the block 194.24.0.0/21 Now take an address falling outside the block E.g. 194.24.9.3 11000010 00011000 000001001 00000011 Bitwise AND the address with the subnet mask We don’t get the base address of the block. X So 194.24.9.3 is not within the block 194.24.0.0/21 CIDR Additional IP addresses used by CIDR Uses class C addresses in blocks of 32 million allocated to di erent parts of the world: 194.0.0.0 - 195.255.255.255 go to Europe 198.0.0.0 - 199.255.255.255 go to North America 200.0.0.0 - 201.255.255.255 for Central and South Asia 202.0.0.0 - 203.255.255.255 for the rest of Asia and Paciﬁc. All remaining addresses are saved for later. There are not enough IP addresses for everyone. These days computers expect to stay “on-line” all the time. People have more and more networks devices. “Private” IP addresses RFC1597 – deﬁnes how the following private IP addresses can be used within an organisation. 10.0.0.0 - 10.255.255.255 172.16.0.0 - 172.31.255.255 192.168.0.0 - 192.168.255.255 Private address range: Address space only unique within an organisation. They can’t be used on the Internet OK for packets that stay within the local network BUT need to translate address of packets going to/from the internet. #RFC: Request for Comments

first_half (1).pdf

Document Details

Tags

Related

Full Transcript

Upgrade to continue