Internet Protocols CSC 343
Popular in Course
BIOL 221 - 001
verified elite notetaker
Popular in ComputerScienence
This 124 page Class Notes was uploaded by Melyssa Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CSC 343 at Wake Forest University taught by Errin Fulp in Fall. Since its upload, it has received 21 views. For similar materials see /class/230722/csc-343-wake-forest-university in ComputerScienence at Wake Forest University.
Reviews for Internet Protocols
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/28/15
lnternet Protocols Multiplexing csc 343643 WAKE FOREST Department of Computer Science Fall 2008 Multiplexing E w Fulp Multiplexing o Often two machines can not utilize the full capacity of a link 0 Need to share the channel among multiple users multiplexing 0 Three types of multiplexing Frequency division multiplexing Time division multiplexing Statistical time division multiplexing Fall 2008 1 m lnternet Protocol Multlplexlng Frequency Division M ultiplexing 0 Given a medium with bandwidth larger than a single signal 0 Divide bandwidth to allow multiple carrier signals Carrier frequencies may not overlap analog signaling Signal raised in frequency to particular carrier Channell Frequency kH Mulllplex channel Frequency Hz Frequency kH uvlglnalbandwldlhs Eandwldlhsvalsedlnlvequency Multiple signals can be sent simultaneously E w Fulp lnternet Protocol Fall 2008 Multlplexlng W Fulp 0 Telephone system Consider backbone links carrying multiple connections Twelve 4 kHz channels multiplexed together Multiplexed into the 60 to 108 kHz band called a group What are other ezmmples 0f FDM Fall 2008 3 2 lnternet Protocols CSC 39 36 I Multiplexing 4 Digital Subscriber Line Using the existing telephony network for high speed data and voice 0 Local loop twisted pair has a 11 MHZ bandwidth potential However only a fraction is actually used Voice requires 300 HZ to 3400 HZ Remove filter anything below 300 HZ and above 3400 Hz 0 Asymmetric Digital Subscriber Line ASDL has larger bandwidth Asymmetric since higher bit rates downstream than upstream Line is not filtered 11 MHZ is available E w Fulp Fall 2008 lnternet Protocols CSC 39 36 I Multiplexing 5 o Divides 11 MHZ bandwidth into 256 channels three bands 1 0 to 4 kHZ telephone service POTS 1 channel 2 25 kHZ to 200 kHZ upstream 5 channels 3 250 kHZ to 1000 kHZ for downstream remaining channels 256 4rkHZ Channels 1W HOOkHZ Power EEe Upslream Downslream Each channel modulation is similar to V34 QAM used 15 bitsbaud 4000 baud Actual rate also depends on line length and quality What is the bit rate if 224 channels are available E w Fulp Fall 2008 lnternet Protocol Multlplexlng 6 nun m nun w ADSLrLlle STE 0 PC Hg p llE 39 llltewmodem old telephone Samoa Elwolklelmlnallon synchronous dlgllal subscllbel llne n2 lnmrnet E W Fulp Fall 2008 lnternet Protocol Multlplexlng 7 Cable TV Networks 0 Uses FDM to transmit multiple channels concurrently Each channel is allocated 6 Mhz 8 MHZ in Europe Coaxlal cable bandWldln Downsueamnovwavd channels Analog TV channels ea MHZ pel channel Unused l l Unused 5 MHZ same 7 300450550 900 MHZ 7 Note Nolmally the band Ol llequenclesllom SE 7 110MHz ale used lol ladle bloadcasls o Upstream is 5 42 MHZ and downstream is above 550 Hz Use QAM 64 per channel What is the maximum data rate per channel E W Fulp Fall 2008 lnternet Protocols Multiplexing s m Time Division M ultiplexing o FDM requires analog circuits not amenable to computers 0 Time Division Multiplexing TDM is used by digital electronics However local loops are analog 0 TDM works by interleaving multiple signals over time m w Fulp FallQOOS lnternet Protocols Multiplexing 9 Generic TDM Description 0 A n signals miti1n are to be multiplexed 0 Input data may be briefly buffered o Buffers scanned to produce a composite digital stream buffer m1t m2t server mnt 0 Data rate of the composite stream 77 c Z 72 21 Fall 2008 w Fulp lnternet Protocol Multiplexing 10 Digital Carrier Systems o TDM is used in telephone networks voice is 4 kHz 0 8000 PCM samples are taken per second at 8 bitssample therefore a voice channel is 64 kbps What is the time per sample 0 24 voice channels are multiplexed together T1 193 Enrrame 4 a Channel 1 Channel Channel Channel Channel 1 39139 2 391 a 4 24 per sample m w Fulp lnternet Protocol F211 2008 Multiplexing 1 I Illm IIIII 0 T1 frame consists of 24 gtlt 8 192 bits plus 1 extra bit for framing total of 193 bits every 125 Msec What is the bit rate of a T o If a T1 is used for data non voice then only 23 channels are used 24th is for synchronization 0 T1 can be multiplexed into higher carriers 4 T1 streams in 7 T2 streams in 6 T3 streams in 1 T2 streams out 4 IIIE 39 k amglam I 7 1544 Mbps 6312 Mbps 44736 Mbps 274176 Mbps T1 T2 T3 T4 E w Fulp F211 2008 m lnternet Protocols C Multiplexing 12 TDM Link Control The T1 description does not have headers trailers CRCs etc 0 Control mechanisms data link are not needed 0 Flow control Multiplexed data rate is fixed Multiplexer and demultiplexer operate at same rate Therefore flow control is not needed What if a user transmits more or less than subscribed 0 Error control Why retransmit an entire T1 frame 0 Flow and error control are handled on a per channel basis m w Fulp Fall 2008 lnternet Protocols C Multiplexing 13 Multiplexing Analogy 3 lane highway used by employees of 3 companies IBM Cisco Nortel o FDM Assign a lane to each company Employees must use lane assigned to their company Can use assigned lane at any time o TDM Assign specific times for highway use 1 IBM employees 500am 600am 2 Cisco employees 601am 700am 3 Nortel employees 701am 800am Employees use entire highway but only during assigned time Any problems with FDM 0r TDM w Fulp Fall 2008 m lnternet Protocols C Multiplexing 14 o STDM Any employee can use any lane at any time Works only if there is no peak time based on averages If all employees use highway at 800am Assume every day trash builds up along the highway and you acting a governor have the right to ne the company instead of the individual employee Is it easy to identify the o ending employee group using the di erent multiplezring techniques E W Fulp Fall 2008 lnternet Protocols C Multiplexing 15 Statistical Time Division Multiplexing 0 Computer traffic data is often bursty not a constant bit stream Onoff oriented consider telephone conversations ampmud Using TDM ifa station is idle transmit What 0 Statistical TDM eXploits the fact that digital data is often bursty Dynamically allocate time slots channels on demand What is the disadvantage w Fulp Fall 2008 lnternet Protocols Multlplexlng 1o Generic STDM Description 0 Slots are not assigned to a particular source a4 a3 a2 a1 STDM 0 Assume arriving frames join a queue Frames will be buffered until transmitted Addresses are required i more overhead Why are addresses required E W Fulp Fall 2008 lnternet Protocols Multlplexlng 17 STD M Performance 0 Sum of the average input rates is less than the multiplexed line However the sum of the input peaks is greater If all inputs transmit at the peak 0 Typically buffering is done on the input side This temporarily stores the data until it is served Smoothes the data stream by removing burstiness Buffering does add possible transmission delays 0 Analysis is based on queueing theory Interested in the average packet delay Delay is based on the arrivals and the server E W Fulp Fall 2008 Multlplexmg 1s lnternet Protocols A Simple Model buffer arrivals depatu res server Packets arrive at the system according to arrival pattern Packets can be from one or multiple sources multiplexer If the buffer is finite and full the packet is dropped 0 Packets are serviced in a FIFO order 0 We are interested in a relationship between the following Nt the number of packets in the system at time t 0405 the number of arrivals in interval 0 tot Ti the time spent in the system by packet i E W Fulp Fall 2008 lo Multlplexmg 1 lnternet Protocols Little39s Theorem 0 An intuitive notion of the typical number of packets in the system the time average of NW up to time t o Nt will change over time but it will approach a steady state N 11m Nt f wvw l ma Ema gm Ens Ens Em n3 U2 El sun mun lEDEI 2am 25mm 1 e E W Fulp Fall 2008 E w Fulp lnternet Protocols m lnternet Protocols o Multiplexing 2 0 Similarly we can make the same claim about the arrivals alttgt t the average arrival rate up to time t o The steady state arrival rate is A tlim At average arrival rate MN U15 sun nun sun llmE 2000 2 an Fall 2008 Multiplexing 21 o The time average of the packet delay up to time t is a t EAT Tt CW the average time spent in the system per packet up to time t o The steady state time average packet delay is T hm Tt taco 0 These quantities N A and T are related by a simple formula also known as Little39s Theorem lt expresses the natural idea that crowded systems large N are associated with long delays large T Valid for different types of queueing systems W Fulp Fall 2008 lnternet Protocols Multiplexing 22 Graphical Proof o Little39s Theorem is really an accounting identity 4 E 2 a 3 51 x E 852 En lt T2 5 packeIZ C1 F packel1 Ilme 0 Suppose the system is initially empty N0 0 0 Let 0405 be the number of arrivals and Mt be the number of departures at time t The number in the system at time t is NOE 0405 7 Mt Fall 2008 Fall 2008 E w Fulp m Multiplexing 23 o The area between the graphs of 0405 and t is t MT 1 0 0 Let t be any time at which the system is empty Nt 0 then the same area is equal to 0405 22 2 21 0 Setting equation 1 equal to equation 2 and dividing byt at at 1 t 1 041571 Ti N 7 T2 7277 t 0 T t t 0405 o This equals N15 AtTt E w Fulp lnternet Protocols Multlplexlng 24 Applications 0 The significance of Little39s Theorem is its generality Holds for almost any queueing system that reaches steady state However it may require information we don39t know 0 Given the statistics about the arrivals and departures we can derive the wait time as well as the queue length Given a certain arrival and departure process we want the average delay E w Fulp Fall 2008 lnternet Protocols Multlplexlng 25 MMl Queue buffer arrivals depatu res server 0 Consider a single buffer and server assume lnterarrival times are exponential with rate A gt 0 Processing times are exponential with rate M gt 0 Buffer space is infinite 0 Average delay is i 1 7 M i A 0 Can determine the delay given the average arrival and processing E W Fulp Fall 2008 Multiplexing 26 lnternet Protocols MMl Performance 0 As the utilization approaches 1 performance decreases unstable 0 System is stable when p lt 1 underload MMl oueue MMl oueue average delay Why does queueing increase dramatically when A u Why does queueing exist when A lt u underload condition E W Fulp Fall 2008 u Multiplexing 2 lnternet Protocols Average Rate o The arrival pattern of packets customers is important We need to also describe the variation So what Want more Fulp coolness Request 050 790 High Speed Networks m w Fulp Fall 2008 lnternet Protocols C Multiplexing 28 Back to TDM and STDM Performance Results for the MMl queue can be applied multiplexing systems 0 TDM consists of dividing the capacity into 11 channels Each channel has rate Each stream can be modeled as an MMl queue with gtk Arrival rate A gtk Transmission rate M Using Little39s Theorem delay per packet is 1 T 7 TDM MiA E W Fulp Fall 2008 lnternet Protocols C Multiplexing 29 STDM buffers packets from n streams Assume multiplexed in one FIFO buffer Total arrival rate is n A System is an MMl queue with transmission rate 11 M Average delay is 1 i TTDM TSTDM npinA n therefore the STDM system delay is a fraction of TDM E w Fulp Fall 2008 lnternet Protocols Multlplexlng 30 0 Example channel with 128kbps data rate 10 users that transmit packets with independent exponentially distributed lengths of 1000 bits Each packet is transmitted according to a Poisson process with average rate 10 packets per second TDM each user gets a 128kbps channel 1 T 360 TDM 128 i 10 msec STDM all users share the link T TSTDM g 36msec m w Fulp lnternet Protocols Fall 2008 Multlplexlng 31 TDM and STDM Comparison u 1 average delay 08 04 06 arrival rate 7 E w Fulp Fall 2008 Multiplexing 32 lnternet Protocols Multiplexing Results 0 Preceding example indicates TDM separate channel multiplexing results in poor delay Performance is even worse if channels are not assigned proportionally to arrival rate Arrival rates tend to change over time 0 However models presented here rely on assumptions that may not be applicable to actual traffic 0 TDMFDM is still used in telephony since voice traffic tends to be regular rather than Poisson Fall 2008 m w Fulp Routing csc 343643 WAKE FOREST Department of Computer Science Fall 2008 lnternet Protocols Routing 1 Routing Algorithms o A primary function of the network layer is routing packets 0 Routing algorithm is responsible for deciding which output line incoming packets should be transmitted o If a datagram network Routing decision is new for every packet o If a VC network Routing decision made for a VC request Thereafter packets follow established path 0 Routing algorithm goals include correctness simplicity robustness stability fairness and optimality E W Fulp Fall 2008 lnternet Protocols Routng 2 What is Optimal General statement about optimal routes 0 Optimality principle If routerj is on the optimal path from router i to router k then the optimal path from j to k falls on this route 0 As a result the set of optimal routes from all destinations to a source is in the form of a sink tree network Slnktree o The sink tree in not necessarily unique but a tree never has m w Fulp Fall 2008 lnternet Protocols Routng 3 Routing Algorithm Classifications 0 Performance criterion Number of hops cost delay 0 Decision time Packet or session 0 Decision place Each node or central node 0 Strategy Nonadaptive static routing Routes calculated off line in advance Adaptive dynamic routing Routes calculated based on measurements or topology that change E W Fulp Fall 2008 lnternet Protocols C Routing 4 Routing Methods 0 Four different algorithms Dijkstra39s Bellman Ford Flooding Random For each method consider Centralized or distributed Ability to handle network dynamics Amount of overhead required E W Fulp Fall 2008 lnternet Protocols C Routing 5 Dijkstra39s Algorithm Summary Find the shortest paths from a given source node to all other nodes by developing the paths in order of increasing path length Algorithm proceeds in stages by the k stage shortest paths to the k nodes closest least cost to the source node have been determined 0 For the algorithm let N set of nodes in the network 5 source node M set of nodes incorporated by the algorithm did link cost from iaj D71 cost of least cost path 3 a n direct paths have a value otherwise 00 1 M s 0 D71 15771 Vn 31 5 directly connected nodes E W Fulp Fall 2008 lnternet Protocols C Poutng 6 2 Get next cheapest node and incorporate into set M Find neighboring node not in M that has least cost path from s and add to M also incorporate edge such that Dw Find w Z M Vrjtg DJ AddwtoMMMUw 3 Update least cost paths using w D71 minDnDw dwm Vn Z M 4 Go to step 2 and repeat until all nodes incorporated in M E w Fulp lnternet Protocols C Fall 2008 Poutng 7 Dijkstra Example ow x 7 3 4 Iter D2 Path D3 Path D4 Path WMH Fall 2008 E w Fulp lnternet Protocols Routing 8 Bellman Ford Algorithm Summary Find the shortest paths from a given source node subject to the constraint that the paths contain at most one link then find the shortest paths with a constraint of paths that contain at most two links and so on o For the algorithm let 5 source node d link cost from 1 j di 0 d 00 if not directly connected d gt 0 otherwise h maximum number of hops allowed in any path D5 cost of least cost path 3 a n using h hops E W Pulp Fall 2008 lnternet Protocols Routing 9 1 Initialization 0 D2 oo Vn 31 5 D 0 Vh 2 Update for each successive h 2 0 for each n 7E 3 DZ minvg39 Di dam E W Pulp Fall 2008 lnternet Protocols Routmg 10 BellmanFord Example h D3 Path Dg Path of Path E W Fulp Fall 2008 lnternet Protocols Routmg 11 Flooding 0 Simple technique requires no network information Source node sends to each neighbor Neighbor transmits on every link accept arriving link 0 Avoiding an infinite number of copies 1 Nodes remember identity of packets don39t transmit duplicates 2 Place hop counter inside each packet Node passes packet decrements counter by 1 If count is zero discard packet What should the hop count equal 0 Flooding properties Robust since all paths tried at least one copies will arrive One copy will arrive using the minimum hope route All nodes are visited E W Fulp Fall 2008 m lrlterrlet Protocols Routng lei broadcast 2nd broadcast 3rd broadcast lell value reached E W Fulp FallQOOS lrlterrlet Protocols ROMng 13 Random Routing 0 Random routing has the simplicity and robustness of flooding but requires far less resources 0 Algorithm details Node randomly selects outgoing link for an arriving packet exclude the link packet arrived on lf links equally probable then utilization of links is round robin 0 Performance modification for links with different rates Assign a probability to each link based on its data rate Ti Pi Zj Ti Yields better utilization of links What are the advantages and disadvantages w Fulp Fall 2008 12 E w Fulp lnternet Protocols m lnternet Protocols Routng 1 Adaptive Routing Adaptive routing is used in packet switched networks Routes will change based on network conditions Network state information needed by all nodes as a result Routing decisions are more complex Must trade off overhead and freshness Classic control probem Control problem Changing too quickly will cause oscillations Changing too slowly never converging Two adaptive routing methods Distance vector and link state Fall 2008 m Routng 1 Distance Vector Each node router maintains a table vector indicates Best known distance to a destination Next link hop to take to get there Tables updated by exchanging info with neighbors A form of distributed Bellman Ford Each node i maintains two vectors di1 di2 delay vector Di next node vector Si dim did current minimum delay from i Hj Sij next node in the current route from i Hj W Fulp Fall 2008 m m lnternet Protocols lnternet Protocols Routing 16 o Periodically nodes exchanges DZ with neighbors Each node updates the vectors using the new information 0 At node k vectors are updated using the equations dim Igng dig ska i using i from preceding equation A set of neighbors of k lk current delay from k a i sent by node W Fulp Fall 2008 Routing 17 Distance Vector Example 0 Given the following network consider the vector for node 1 a Kkltg 111 0 8117 161 A237 D1 1121 31 3122 1134 8133 0 Suppose the 2 a 3 link changes to 2 W Fulp Fall 2008 lnternet Protocols Routng 18 dg l 1 dg l 4 D2 d2 20 D3 d3 22 123 2 133 0 0 Above two vectors are sent to node 1 which calculates routes dllj iglli dig j all other nodes i 2 112 minll2 122113 132 812 2 j 3 113 minll2 123113 133 i 813 2 E W Fulp Fall 2008 lnternet Protocols Routng 19 Count to Infinity Problem 0 Distance vector routing Given n is the longest path in the network with n exchanges all nodes will know about any good news Bad news will take infinite exchanges 0 Consider the following full duplex network 619 19 Initially 1 a 2 is 1 unit and 3 a 1 is 2 units 0 Assume node 1 goes down what happens on the exchanges 1 Node 2 gets nothing from node 1 therefore cost is 00 However cost to node 1 via node 3 is 2 so node 2 uses path via node 3 to get to 1 cost is 3 E W Fulp Fall 2008 lnternet Protocols Routng 20 2 Node 3 gets update cost from node 1 path to node 1 is 3 must update its cost to 4 3 Node 2 get updated cost from node 3 path to node 1 is 4 must update its cost to 5 This repeats until cost is 00 Several changes to the DV routing have been proposed Split horizon and reverse poison are two examples where minimum distance information is not sent to a neighbor if the neighbor is on the minimum path Unfortunately these fixes do not always work E W Fulp Fall 2008 lnternet Protocols Routng 21 Link State Has the following steps Discover neighbors and learn addresses Measure cost delay to neighbors Create packet containing cost information Send packet to all nodes not just neighbors 9quot 90 Compute shortest path to all other nodes Dijkstra39s Algorithm Any problems with link state E W Fulp Fall 2008 internet Protocois Routing 22 Routing Comparison Algorithm Characteristic Distance Vector Link State Complexity Messages sent to neighbors Messages sent to all other nodes Convergence Time varies count to infinity May oscillate Robustness Routing tables depend on Calculations made on a per neighbor calculations error node basis propagates So which is used in IP7 both Routing Information Protocol RIP is DV Open Shortest Path First OSPF is LS However neither method is scalable E W Filip Faii 2008 internet Protocois Routing 23 Hierarchical Routing 0 As the network size increases so do the routing tables Infeasible for every router have an entry for every other router called source based routing The previous methods are not scalable Hierarchical routing is used instead 0 Hierarchical routing divides the network into regions called Autonomous Systems AS Router can route to other routers inside its region Router does not know how to route inside other regions Traffic destined for another region forwarded by gateway router E W Filip Faii 2008 lnternet Protocols Full table for 1A Regionl Routing Dest Region 2 Dest 2A 2B 15 1C RegionS Regi0n4 Re bns Example network nonrhierarchical routing table 0 Example network is a two level hierarchy Source based routing table has 17 entries 2 level hierarchy has 7 entries E w Fulp Hierarchical table for 1A hierarchicaltable lnternet Protocols o Hierarchical tables Fall 2008 Routing 25 One entry for each router in same region AS One entry for all routers in another region gtr All traffic from region 1 to region 2 traverse lB 2A link Given a destination address in another region how does a router know which region to route Addresses are hierarchical gtr In the example network router addresses have the form region number followed by router letter o Hierarchical routing disadvantages May result in increased path lengths E w Fulp For example best route from 1A to 5C is via region 2 but hierarchical routing uses region 3 Fall 2008 24 lnternet Protocols Routing 26 How Many Hierarchies Consider a network with 720 routers o No hierarchy each router has 720 entries 0 Partition into 24 regions each with 30 routers This is a two level hierarchy Each routing table has entries 0 Using a three level hierarchy with 8 domains each containing 9 regions of 10 routers Each routing table gtk 10 entries for local routers gtk 8 entries for routing to other regions inside of own domain gtk 7 entries for other domains Total of 25 entries E w Fulp lnternet Protocols Fall 2008 Routing 27 Static versus Dynamic IP Routing 0 Already know how IP packets are routed using routing tables How were the entries generated statically or dynamicaly7 o In static routing entries are manually adjusted Acceptable for small networks 0 For larger networks dynamically change table entries Routes should change based on network conditions Allow routers to pass route information to one another Use variations of Bellman Ford and Dijkstra39s 0 NB This will not change the way IP datagrams are routed just howwhen the routing table contents change E w Fulp Fall 2008 lnternet Protocols Routing 28 Internet and Autonomous Systems 0 Internet is a collection of connected networks Local regional national and international lSPs o Autonomous Systems AS Collection of routershosts under an administration control May consist of multiple networks Why is it important to divide into autonomous systems 0 Within this hierarchy classify routing algorithm as Intra AS route within one autonomous system Inter AS route among autonomous systems E w Fulp Fall2008 lnternetprotocols Routing 29 mummy memrgatamv suhmimm Omwamlneml Q mmtwm Saumemst Dasunatnnhust AP AP Cara e n m LAW J lep gtl Ligepgtl LlGP Fl LAW J Aezmcma w Assammusmm mmmemmwmm K3 magma lGP z mmgmv WW Eemrnrgataav szwmrgaEWDmcal E w Fulp Fall 2008 Internet Protocols C Routing 3o IntraAS Routing 0 Used to configure and maintain routing tables within an AS 0 Also called Interior Gateway Protocols IGP o Historically three routing protocols have been used Routing Information Protocol RIP Open Shortest Path First OSPF Enhanced Interior Gateway Routing Protcol EIGRP Cisco propriety E W Fulp Fall 2008 Internet Protocols C Routing 31 Routing Information Protocol 0 RIP was one of the earliest intra AS protocols Still in use popular since it was included BSD UniX Two versions original RFC1058 and version 2 RFC1723 0 Distance vector protocol Neighboring routers exchange messages every 30 seconds Message called RIP response message or RIP advertisement In original version cost metric a hop count Which shortest path algorithm is it based oh What problem is associated with this algorithm E W Fulp Fall 2008 Internet Protocols Routing RIP Messages 0 Messages are carried in UDP datagrams transport layer 394 IPdatagram gt RIP Message IP U P Header Header 0 RIP messages have the format command I version must be zero I address family I 32 bit IP address must be zero must be zero 20 bytes must be zero metric 1 16 up to 24 more routes with same format as previous 20 bytes E w Fulp Internet Protocols Routing 32 Fall 2008 0 RIP message fields Command field 1 request or 2 reply Version field 1 or 2 Next 20 bytes specify address family an IP address and an associated metric o 25 routes can be advertised in a RIP message Total size of RIP message is 20 gtlt 25 I 4 504 bytes less than 512 bytes Why so much wasted space per entry quotThe packet format is intended to allow RIP to carry routing informa tion for several different protocols None of the RIP implementations available to the author implement any other type of address How ever to allow for future development implementations are required to skip entries that specify address families that are not supported by the implementationquot RFC1058 E w Fulp Fall 2008 w Routing 34 internet Protocols RIP Problems 0 No knowledge of subnet addressing 0 May take a long time to converge Count to infinity problem 0 Only uses hop count as metric Other variables should be taken into account Maximum of 15 limits size of network E W Fulp Fall 2008 Routing 35 internet Protocols RIP Version 2 0 Protocol remains the same but uses entire RIP message a m command version I must be zero address iamin I route tag 3241i iP address subnet mask 20 bytes next nop metric 1716 up to 24 more routes witn same iormat as previous 20 bytes 0 New message format Routing domain identifies the routing daemon Route tag eXists to support exterior gateway protcols Mask applies to the corresponding IP address entry 0 RIP 2 also provides a simple authentication scheme to verify the sender of the routing table Fall 2008 m w Fulp lnternet Protocols Routng 3o Open Shortest Path First 0 OSPF is another intra AS routing protocol RFC1247 2328 0 Primary characteristics Open protocol specification is public domain Link state protocol Dijkstra39s algorithm used for SPF What is the disadvantage to using a link state algorithm 0 OSPF can operate within a hierarchy Largest entity is the AS AS is divided into area Routing algorithm will operate in each area What problem does this attempt to avoid m w Fulp Fall 2008 lnternet Protocols Routng 37 OSPF Routing Hierarchy o OSPF allows an AS to broken into areas Areas do not overlap but are not exhaustive Therefore we are reducing Outside an area topology and details are not known Area is generalization of a subnet 0 Within an area each router must Have the same link state database and run the same SPA Know the shortest path to any other router in its area 0 Router classification Internal routers within an area Area border routers connect outside of area within AS AS boundary routers connect to other autonomous systems E W Fulp Fall 2008 lnternet Protocols Routing 3 o The diagram show all the different types of routers Routers R2 R3 R5 R6 and R7 are internal routers Routers are area border routers Router R0 is the AS boundary router R amnmmnussy em o A backbone area also eXists consists of all area border routers boundary routers and any networksrouters not inside an area m w Fulp lnternet Protocols Fall 2008 Routing 39 OS P F Operation 0 Determine neighbors by sending hello messages Hello messages are multicast every 10 seconds Failure to receive hello from neighbor for 40 seconds assume linkneighbor failed 0 Each router in an area distributes information about its local environment in datagrams called link state advertisements Information about neighboring routers links and costs LSA are distributed via reliable flooding explicitly ACKed sequenced and time stamped gtr Sent if new neighbor found link failure cost change refresh every 30 minutes Using this information shortest tree path can be determined E w Fulp Fall 2008 m lnternet Protocols Routng 40 OSP F Operation Review 0 Using reliable flooding routers inform other routers in area Each router can then construct a graph of the area and find the shortest paths 0 Backbone area performs same procedure Backbone also accepts information from area border routers Can determine the best route from each backbone router to every other router o Backbone information sent to area border routers which advertise information within their area E w Fulp Fall 2008 lnternet Protocols Routng 41 OSP F Advanced Features 0 Different routes based on traffic type of service Allow different types of traffic to take different routes How can this be done 0 Load balancing Using multiple routes may be better than just one best route 0 Security Router exchanges are authenticated prevents router spoofing E w Fulp Fall 2008 m m lnternet Protocols lnternet Protocols Routing 42 Exterior Gateway Routing Protocol 0 Within a single AS OSPF is generally used 0 Routing between AS requires another routing protocol Called an exterior gateway protocol Border Gateway Protocol BGP RFC1772 Backbone lmemalromer as prereeer conneclsmeamonomussysmms Area border rower AS boundary miner w Fulp Fall 2008 Routing 43 Otherwise is it transit refuse to transit traffic backbone networks o BGP routers classify traffic as Routing decisions are policy based BGP routers classify networks as o A different protocol is needed since goals are different Routing based on who controls AS rather than cost or delay gtk A telco accepts customer traffic but not other telco traffic Loca traffic originates or terminates in the AS Stub networks have only one connection to the BGP graph can not be used to transit traffic Multiconnected networks have multiple connections but Transit networks are willing to transmit third party traffic W Fulp Fall 2008 lnternet Protocols Routng 44 BGP Routing 0 Path vector routing algorithm BGP routers propagate path information instead of cost Keeps track of the exact path used not just the next hop The count to in nity probem is avoided since complete paths are exchanged o BGP is the de facto standard for inter AS routing Internet routing Used to connect Network Access Points NAPS Current BGP routing tables available at httpbgppotaroonet and httpwwwapnic netstatsbgp E w Fulp lnternet Protocols Fall 2008 Routng Unix Routing Damons 0 Routing daemon adds a routing policy to the system Determines which routes to place in the routing table For example if multiple routes to a destination exists the daemon selects the best route 0 Unix systems run one of two routing daemons routed or gated Interior Gateway Protocol Exterior Gateway Protocol Daemon RIP OSPF EGP BGP routed V1 gated version 1 V1 V1 gated version 2 V1V2 V2 V2 V3 E w Fulp 0 Which one is being used on a Unix machine enter the command ps ef I grep quotedquot Fall 2008 45 Introduction to Network Programming csc 343643 WAKE FOREST Department of Computer Science Fall 2008 lnternet Protocols C introduction to Network Programming 1 Socket Application Programming Interface API Introduced in 1981 Berkeley Software Distribution BSD 41 Originally only Unix a WinSock almost the same 0 Connects sockets on two hosts Data transfer similar to UniX file operations 0 Two services provided Datagram Stream Socket interface is generic it can be used with a variety of protocols not just UDPTCPIP E w Fulp Fall 2008 nternet Protocois introduction to Network Programmmg 2 Review of Unix File Operations 0 Unix file operations readwrite to a file descriptor An integer associated with an open file A file can be data file device network connection 1 int fileDescriptor file descriptor char buffer 256 buffer for readwrite 2 3 4 fileDescriptor openquotfiledatquot ORDWR OCREAT 5 code storing info in buffer o writefileDescriptor buffer 256 7 closefileDescriptor o Sockets are very similar except for setup E W Fuip FaH 2008 internet Protocois introduction to Network Programming 3 Generic Data Types Data types are needed to represent a socket and an address 0 A socket is an int like a file descriptor o sockaddr is a generic struct containing socket address information 1 struct sockaddr 2 C 3 unsigned short safamily address family 4 char sadata 14 protocol address 5 safamily identifies the address famin AFINET sadata contains a network address 0 Prefer something more IP specific which is sockaddrin E W Fuip FaH 2008 Internet Protocols Introduction to Network Programming 4 Internet Data Types o sockaddrin is a parallel struct containing Internet socket address information 1 struct sockaddrin 2 C 3 short int sinfamily address family 4 unsigned short int sinport port number 5 struct inaddr sinaddr Internet address 6 char sinzero8 filler no data 7 0 inaddr is an Internet address 1 struct inaddr 3 unsigned long int saddr 4 bytes IPv4 address What is parallel Why is it important E W Fulp Fall 2008 Internet Protocols Introduction to Network Programming 5 safanu391y sadata sockaddr family 2 bytes 2 bytes 4 bytes 8 bytes SDCkaddlLin famin port Internet address unused sin amily sinpot sinadd sinzeo 0 Socket calls are generic sockaddr but we will use Internet addresses sockaddrin Since the structs are the same size parallel a cast m w Fulp Fall 2008 lnternet Protocols lntroductlon to Network Programmlng o Byte Order As you may recall 0 There are two types of byte orderings Most significant byte first also called network byte order Least significant byte first 0 Computers based on architecture will use one or the other Therefore we need to be consistent remember to convert o How do we convert Use the following functions htons is host to network short htonl is host to network long ntohs is network to host short ntohl is network to host long E W Fulp Fall 2008 lntroductlon to Network Programmlng 7 lnternet Protocols Address Example Create an address for www cs wfu edu web server 1 includeltarpainethgt for sockaddrin and inetaddr 2 includeltstringhgt for memset 3 4 struct sockaddrin wquddr wwwcswfuedu 5 o wquddrsinfamily AFINET Internet address 7 wquddrsinport htons 80 port network byte order 8 copy IP address asc1i to network byte order 10 inetatonquot1521714092quot ampwquddrsinaddr to 12 zero the rest of the struct 13 memset ampwquddrsinzero 0 8 15 prlnt the address to the screen 16 cout ltlt inetntoawquddrsinaddr ltlt n E W Fulp Fall 2008 lnternet Protocols lntroductlon to Network Programmlng 8 Creating a Socket Before sendingreceiving must create a socket 0 Must specify protocol family PFINET type SUCKDGRAM or SDCKSTREAM and protocol 0 for default include ltsyssockethgt for socket 0 int sock ifsock 1 stores the socket descriptor socketPFINET SUCKSTREAM IPPRUTUTCP cerr ltlt exit 1 1 2 3 4 5 6 7 quotCouldunotucreateusocketUnquot 8 9 0 Returns the socket number 1 if error 0 Once done with the socket your program must close it like a file close sock Is the above socket UDP 07 TOP E w Fulp lnternet Protocols C m lnLroducLlon to Network Programmmg Fall 2008 9 TCP or UDP 0 There are two types of services available in the Internet User Datagram Procotol UDP is an unreliable transmission Transport Control Protocol TCP is a reliable stream 0 Service must be specified once the socket is created Creating the socket with SDCKDGRAM uses UDP socket PFINET 1 sock SUCKDGRAM 0 Creating the socket with SUCKSTREAM used TCP 1 sock socketPFINET SUCKSTREAM IPPRUTELTCP 0 Functions used to transmit data differ based on the service W Fulp Fall 2008 MAM W m TCP Chem Server Model Fm TCP ante the serveth 2 mnnectmn request handshzte emvmme wequot numbersznd hu evswce 7 Once mnnectmn 2mm can send and mamach 5m Wet 9mm ghsxm a men gt pawm gt513 Tm mat mm Sammachse 1 2 1 T What I m dwmm m UDF Wm N Mam TCP Chem TC chant must perm the Tanmgmmeps 1 3mm 2 TC We 5mg sacket 2 Beams mnnectmn m sen21 5mg camect mu m xecv 3 i E a a C mthemnne mn thh class a Q smdxecv a close 4 T Aheadydxscussed mmmm mgkat 7 Ben m thesmket Ts socmzm Tm TC lnternet Protocols tntroductron to Network Programmrng TCP Client connect To connect the client program must specify 0 Socket server address and address length 1 int connectint sock struct sockaddr serverAddr 2 unsigned int aderength 0 Assume we want to connect to a server 1 ifconnectsock struct sockaddr ampserverAddr 2 sizeofstruct sockaddr lt O cerr ltlt quotCouldunotuconnectUtouserverunquot 5 exit 1 o 0 Connect will perform three way handshake 0 Once connected client and server can send and recv data Would UDP use the connect function m w Fulp Fall 2008 lnternet Protocols ntroductron to Network Programrmng 13 TCP send To send data TCP only the program must supply 0 Socket pointer to data data length and flags 1 int sendint sock const void msg 2 unsigned int msgLength int flags 0 Assume we want to send a C string char str quotPlufustillurulesquot int strLength strlenstr 1 m 3 ifsendsock str strLengh 0 strLength 4 f 5 cerr ltlt quotCouldunotUsenduallutheudataunquot 6 exit 1 0 send will return the number of bytes sent How does send know which address and port to send to E W Fulp Fall 2008 m internet Protocois introduction to Network Programming TCP recv To recv data TCP only the program must supply 0 Socket pointer to buffer maximum buffer length and flags 1 int recvint sock void buffer 2 unsigned int bufferLength int flags 0 Assume we want to receive data from a TCP socket 1 char buffer 256 2 int numBytes 3 ifnumBytes recvsock buffer 256 0 lt 0 4 5 cerr ltlt quotCouldunotUrecvufromusocketUnquot 6 exit 1 7 o recv returns the number of bytes read Blocks until data received or timeout Data is placed in the buffer E w Fuip internet Protocois Faii 2008 introduction to Network Programming 15 Closing a Socket Once communication over a socket is complete you must close 0 Specify the socket and use the Close function 1 include unistd hgt 2 3 closesock 0 Cannot readwrite to the socket after Close Why is close necessary W Fuip Faii 2008 lntroducuon to Network Programmmg 1o lnternet Protocols TCP Time Service TCPIP defines a service port 13 that allows one machine to obtain the current data and time from another The following client program will obtain the time from the server 152171403 includeltiostreamgt includeltsyssockethgt socket 0 send recv NH 3 includeltarpainethgt struct socket sockaddr 4 includeltunistdhgt close 5 includeltstringhgt memsetO 6 using namespace std 7 8 int main 9 10 int sock socket for datagram communication 11 ifltltSOCk socketPFINET SUCKSTREAM IPPRUTUTCP 12 1 13 C 14 cerr ltlt quotCouldunotucreateusocketUnquot 15 exit 1 16 E w Fulp FallQOOS lnternet Protocols lntroducuon to Network Programming 17 1 struct sockaddrin srvAddr time server 2 srvAddrsinfamily AFINET Internet addr 3 srvAddrsinport htons 13 port 13 4 srvAddrsinaddrsaddr inetaddrquot152171403quot 5 memset ampsrvAddrsinzero 0 8 set to zero 6 7 ifconnectsock struct sockaddr ampsrvAddr 8 sizeofltstruct sockaddr 1 9 1o cerr ltlt quotCouldunotuconnectUtouserverunquot 11 exit 2 12 13 14 to receive the time just ask the question 15 char msg quotWhatutimeuisuit7quot 1o ifsendsock msg strlenmsg 1 0 1 17 18 cerr ltlt quotCouldunotusendutousocketUnquot 19 exit 3 20 E W Fulp Fall 2008 cm mm 2581 7 cores am mam mm mm um um mu dzhlgam Wm xm mm xfxecvsock mm 255 o gt cm ltlt Couldumtuxecew ufxumusucketum mm w u mm ltlt vxnn cosesock return 0 Tarmma gt mum mmuusnm TCP Server ch senEv must mmv ete the DHmmgsxxsmvs 1 5 m usmgsacket pm numhev sucket My 3 Te mm msz mnnectmns on man mg mm Me n Values usmgac apt s Cnmmummte mg xecvznd mu m naw mckzt a Omelhe mnnemun usmgclase mm mum lxstenaacceyi I msud ans 4 A mdy knmzhuut sunken xecV send and class lnternet Protocols introduction to Network Programming 20 Tob 1 2 TCP bind ind a port to an address the program must supply Socket address and address length int bindint sock struct sockaddr localAddr unsigned int aderength Assume we wanted to bind to port 1122 struct sockaddrin localAddr memsetamplocalAddr O sizeofltlocalAddrgtgt localAddrsinfamily AFINET Internet localAddrsinaddrsaddr htonlINADDRANY any localAddrsinport htons1122 local port 6 7ifbindsock struct sockaddr amplocalAddr sizeofltstruct sockaddr lt O local addr 1 zero addr 2 3 4 5 g 10 cerr ltlt quotCouldunotubindutousocketUnquot n exit1 12 Fall 2008 EW mm lnternet Protocols introduction to Network Programming TCP listen To listen for a connection request the program must supply 0 Socket and queue limit int listenint sock queueLimit is the maXimum outstanding requests 1 int queueLimit 0 Assume we wanted to listen for incoming connections define MAXPENDING 5 max1mum outstanding req iflistensock MAXPENDING lt 0 3 cerr ltlt quotCouldunotUlistenuonusocketUnquot exit1 o listen returns 0 on success 1 otherwise The queue is used by accept 21 Fall 2008 EW mm lnternet Protocols introduction to Network Program mg m TCP accept 1 To accept an incomming connection the program must supply 0 Socket client address and address length 1 int acceptint sock 2 struct sockaddr clientAddress unsigned int aderength 0 Assume we wanted to accept an incoming connection int clientSock socket for connection struct sockaddrin clientAddr unsigned int aderength ifclientSock incoming address sizeofltstruct sockaddrin acceptsock struct sockaddr ampclientAddr ampaderength lt O cerr ltlt quotCouldunotuacceptuconnectionunquot exit1 EW mm lnternet Protocols introduction to Network Programm Fall 2008 l m o accept returns a descriptor for a new socket Dequeues the next connection on the socket queue Creates a new socket for arriving connection Sets the address and address length variables lfthe queue is empty then block If error then accept returns 1 0 After accept program can recv and send As described there are two sockets one for receiving a connection request and another created for the connection Which sachet is used for sending and which for receiving The socket that has been bound to a port and marked listening is never used for sending and receiving in TCP EW mm Fall 2008 lnternet Protocols lntroduction to Network Programming 24 Example TCP Client Server Program Write a TCP client and a server that will sendreceive C strings Listen for a connection on port 1848 Must be started before client program Why must the server be running before the client starts 0 Client will send the message quotHello from Clientquot to the server Assume the destination port is 1848 0 Server will reply to the client quotHello wxyzquot E w Fulp lnternet Protocols Fall 2008 lntroducuon to Network Programming 25 TCP CString Client Program include ltiostreamgt includeltsyssockethgt socket send rech includeltarpainethgt struct sockaddr includeltunistdhgt closeO memsetO using namespace std 1 2 3 4 5 includeltstringhgt 6 7 8 int main 9 10 int sock socket for stream communicatlon 11 ifsock socketPFINET SUCKSTREAM 12 IPPRUTOTCP 1 13 cerr ltlt quotCouldunotucreateusocketUnquot exit1 14 15 struct sockaddrin srvAddr address of server 16 srvAddrsinfamily AFINET Internet address 17 srvAddrsinport htons 1848 port 1848 18 srvAddrsinaddrsaddr inetaddrquot1521714017quot 19 memset ampsrvAddrsinzero 0 8 set to zero E w Fulp Fall 2008 nternet Protoco s ntroducmon to Network Programmmg 26 21 establish connection with server 22 ifconnectsock struct sockaddr ampsrvAddr 23 sizeofstruct sockaddr lt O 24 cerr ltlt quotCouldunotuconnectunquot exit 2 25 26 char msg quotHelloufromuclientquot cstring to send 27 ifsendsock msg strlenmsg 1 0 1 2s cerr ltlt quotCouldunotusendutousocketUn39 exit3 29 30 char buffer 256 stores data received from socket 31 unsigned int aderength sizeofsockaddr 32 int numBytes O 33 ifnumBytes recvsock buffer 256 0 lt 0 34 cerr ltlt quotCouldunotureceiveUfromusocketUnquot exit 4 35 cout ltlt buffer ltlt n 36 37 closesock 38 return 0 39 E w Mp FaHQOOS nternet Protoco s ntroducuon to Network Programmmg 27 TCP CString Server Program 1 include ltiostreamgt 2 includeltsyssockethgt socket send recv 3 includeltarpainethgt struct sockaddr 4 includeltunistdhgt close 5 includeltstringhgt memset 6 using namespace std 7 8 int main 10 int sock socket for datagram communication 11 ifSOCk socketltPFINET SUCKSTREAM 12 IPPRUTUTCP 1 13 cerr ltlt quotCouldunotucreateusocketUnquot exit1 14 15 struct sockaddrin myAddr my server addr 16 myAddrsinfamily AFINET Internet addr 17 myAddrsinport htons1848 port 1848 18 myAddrsinaddrsaddr INADDRANY my address 19 memsetampmyAddrsinzero 0 8 Set to zero EWFM Rm 2008 nternet Protoco s ntroducuon to Network Programmmg 2s 1 ifbindsock struct sockaddr ampmyAddr 2 sizeofstruct sockaddr 1 3 cerr ltlt quotCouldunotUbindutouportunquot exit2 4 5 iflistensock 0 lt O 6 cerr ltlt quotCouldunotUlistenutousocketUnquot exit 3 7 8 int clientSock client socket 9 struct sockaddrin clientAddr client addr 10 unsigned int clientAderength 11 sizeofstruct sockaddrin 12 13 ifclientSock acceptsock struct sockaddr 14 ampclientAddr ampclientAderength lt O 15 cerr ltlt quotCouldunotuacceptUconnectionun exit 4 16 17 char buffer 256 data received from socket 18 ifrecvclientSock buffer 256 0 1 19 cerr ltlt quotCouldunotureceiveUfromusocketUnquot exit 3 20 cout ltlt buffer ltlt n E w Pulp FaHQOOS nternet Protoco s ntroducuon to Network Programmmg 29 1 char reply new charEstrlenU39I Iellouquot 2 strleninetntoadestAddrsinaddr 1 3 strcpyreply quotHellouquot 4 strcatreply inetntoaclientAddrsinaddr 5 ifsendclientSock reply strlenreply 1 0 1 6 cerr ltlt quotCouldunotusendutousocketUnquot exit4 7 8 closesock 9 return 0 10 Terminal Terminal gt tcpStrSrv gt tcpStrCli Hello from client Hello 1521714012 gt gt E W Fu p F2 2008 Sockets Dim WE 7mm and do m7 mmquot W 7 777 quot7 7a m 7 mm m m 57 7 m m 7quot m7 7 7 m 7 m m 7 m W7M7W W7Eh7 77 WWWWE 7 Oxentdu notesm 179 12 mm mm m m datagmmw InTGFac Immune hhsh 2 mnnectmn seam emsnm 1 m Wbmzwn om mth Wm In msz a new mm to m mm 4m mzm 2m pmn m mm lnternet Protocols lntroductlon to Network Programmlng Datagram sendto To sendto the program must specify 0 Socket data data length flags to address to address length 1int sendtoint sock const void msg int len 2 unsigned int flags 3 const struct sockaddr toAddr 4 int toLength 0 Assume we want to send a C string char msg quotWhatutimeuisuit7quot sendtosock msg strlenmsg 1 O 1 2 3 struct sockaddr ampsrvAddr 4 sizeofstruct sockaddr o sendto will return the number of data bytes sent 1 if error 32 EW mm lnternet Protocols Fall 2008 lntroductlon to Network Programmlng 33 Datagram recvfromo Similarly to recvfromO the program must specify 0 Socket buffer to store data buffer length flags from address and from address length int recvfromltint sock void buffer unsigned int flags struct sockaddr fromAddr int fromLength 1 int bufferLength 2 3 4 0 Assume we want to receive data from a datagram 1 char bufferE256 2 sockaddrin fromAddr 3 unsigned int aderength sizeofstruct sockaddr 4 5 recvfromltsock buffer 256 O struct sockaddr ampfromAddr ampaderength o recvfromO returns the number of data bytes 1 if error fromAddr stores the datagram address aderength stores the address length must be initialized EW mm Fall 2008 lntroducmon to Network Programmmg 34 lnternet Protocols UDP Time Service TCPIP defines a service port 13 that allows one machine to obtain the current data and time from another The following program will obtain the time from 152171403 1 includeltiostreamgt 2 includeltsyssockethgt socket sendto recvfrom 3 includeltarpainethgt struct sockaddr 4 includeltunistdhgt close 5 includeltstringhgt memset 6 using namespace std 7 8 int main 9 10 int sock socket for datagram communication 11 ifsock socketPFINET SUCKDGRAM 0 1gt 12 13 cerr ltlt quotCouldunotucreateusocketUnquot 14 exit 1 15 E w Fulp FallQOOS lnternet Protocols lntroducuon to Network Programming 35 1 struct sockaddrin srvAddr address of server 2 srvAddrsinfamily AFINET Internet address 3 srvAddrsinport htons 13 port 13 4 srvAddrsinaddrsaddr inetaddrquot1521714013quot 5 memset ampsrvAddrsinzero 0 8 set to zero 6 7 to receive the time just ask the question 8 char msg quotWhatutimeuisutime7quot 9 ifsendtosock msg strlenmsg 1 0 10 struct sockaddr ampsrvAddr 11 sizeofltstruct sockaddr 1 12 13 cerr ltlt quotCouldunotusendutousocketUnquot 14 exit 2 15 E W Fulp Fall 2008 lnternet Protocols E w Fulp lnternet Protocols m lntroduction to Network Programming 1 char buffer 256 Stores data received from socket 2 unsigned int aderength sizeofltsockaddrgt 3 4 will block until datagram received from socket 5 ifrecvfromsock buffer 256 O struct sockaddrgtrgt 6 ampsrvAddr ampaderength 1 7 8 cerr ltlt quotCouldunotureceiveUfromusocketUnquot 9 exit 3 10 close sock cout ltlt buffer ltlt return 0 n Terminal gt udeime Mon Nov 24 121547 2003 Fall 2008 lntroductlon to Network Programming Example UDP Client Server Program Write a UDP client and a server that will sendreceive C strings Client will send the message quotHello from clientquot to the server Assume the destination port is 1848 Server will reply to the client quotHello wyzquot Listen for datagrams on port 1848 Must be started before client program W Fulp Fall 2008 nternet Protoco s ntroducuon to Network Programmmg 38 UDP CString Client Program 90 me includeltiostreamgt includeltsyssockethgt includeltarpainethgt includeltunistdhgt includeltstringhgt using namespace std int main int sock ifsock cerr ltlt exit1 struct sockaddrin srvAddrsinfamily srvAddrsinport srvAddrsinaddrs memsetampsrvAddr srvAddr AFINET htons1848 addr sinzero sendto sockaddr socket struct close memset SUCKDGRAM 0 quotCouldunotucreateusocketUnquot O 8 recvfrom socket for datagram communication socketPFINET 1 address of server Internet address port 1848 inetaddrquot1521714017quot set to zero EW mm nternet Protoco s Rm 2008 ntroducuon to Network Programmmg 39 char msg ifsendtosock msg quotHelloufromuclientquot strlenmsg 1 0 struct sockaddr ampsrvAddr sizeofstruct sockaddr cerr ltlt exit2 char buffer256 stores data received from socket unsigned int aderength ifrecvfromsock buffer 1 quotCouldunotusendutousocketUnquot sizeofsockaddr 256 O struct sockadddr ampsrvAddr ampaderength cerr ltlt exit3 cout ltlt buffer ltlt closesock return 0 n y 1 quotCouldunotureceiveUfromusocketUnquot c string to send EW mm Rm 2008 nternet Protoco s ntroducmon to Network Programmmg 40 UDP CString Server Program 1 includeltiostreamgt 2 includeltsyssockethgt socket sendto recvfrom 3 includeltarpainethgt struct sockaddr 4 includeltunistdhgt close 5 includeltstringhgt memset 6 using namespace std 7 int main 8 9 int sock socket for datagram communication 10 ifsock socketPFINET SUCKDGRAM 0 1gt 11 12 cerr ltlt quotCouldunotucreateusocketUnquot 13 exit 1 14 15 struct sockaddrin myAddr my server addr 16 myAddrsinfamily AFINET Internet address 17 myAddrsinport htons 1848 port 1848 18 myAddrsinaddrsaddr INADDRANY my address 19 memset ampmyAddrsinzero 0 8 set to zero 20 E w Mp FaHQOOS nternet Protoco s ntroducuon to Network Programmmg 41 21 ifbindsock struct sockaddr ampmyAddr sizeofstruct 22 sockaddr 23 24 cerr ltlt quotCouldunotUbindutouportunquot 25 exit 1 26 27 28 struct sockaddrin destAddr dest client address 29 unsigned int destAderength sizeofstruct sockaddr 30 31 char buffer 256 data from socket 32 ifrecvfromsock buffer 256 O struct sockadddr 33 ampdestAddr ampdestAderength 1 34 35 cerr ltlt quotCouldunotureceiveUfromusocketUnquot 36 exit 3 37 38 39 cout ltlt buffer ltlt n 40 41 char reply new charstrlenquotIIellouquot 42 strleninetntoadestAddrsinaddr 1 43 strcpyreply quotHellouquot E W F111 F211 2008 ntemet Protocols ntroducmon to Network Programmmg 42 gt udpStrSrv Hello from client gt strcatltreply inetntoadestAddrsinaddr ifsendtosock reply strlenltreplygt 1 O struct sockaddr ampdestAddr sizeofltstruct sockaddr 1 cerr ltlt quotCouldunotusendutousocketUnquot exit 4 closesock return 0 Terminal Terminal gt udpStrCli Hello 1521714012 gt E w Mp Rm 2008 Medium Access Control csc 343643 WAKE FOREST Department of Computer Science Fall 2008 lnternet Protocols Medium Access Control 1 Local Area Networks 0 Previously we have primarily discussed point to point connections Connecting two stations together Now consider connecting mutipe stations together 0 Local Area Networks LAN have a broadcast characteristic Each station connected to a medium shared by others Transmission of one station is received by all others Routing is not required What does this mean 0 Given multiple local stations how are they connected E w Fulp Fall 2008 lnternet Protocol Medlum Access Control 2 LAN Topologies Slaan O S II staan shared medlum ring lAN bus lAN 0 Ring Unidirectional receive on one link and transmit on the other Is this routing 0 Bus Stations tap into shared medium How are stations typically connected Topology will impact the Medium Access Control MAC m W Ful lnternet Protocol 9 Fall 2008 Medlum Access Control 3 Medium Access Control A LAN consists of multiple stations sharing a medium 0 Method to control access a Medium Access Control MAC Network layer LLC sublayer v Link layer MAC sublayer Convergence sublayer v 39 Physical layer Mediumrdependenl sublayer o Technically MAC is a sublayer bottom of the data link layer E w Fulp Fall 2008 m lnternet Protocols Medlum Access Control LLC Physical layer N etwork 0 Logical Link Control LLC At the top of the data link layer Provides error and flow control 0 We will focus on the MAC sublayer Question to resolve Who may send next7 An allocation problem What about multiplexing m W lnternet Protocols Fulp 4 Fall 2008 Medlum Access Control Channel Allocation Problem How do we allocate a shared channel among competing stations 0 Static channel allocation TDM approach each user has a specific time slot Already determine static allocation is inefficient It is e icient for telephone networks why not in a LAN 0 Dynamic channel allocation is better for bursty traffic Is there any reason for static allocation in computer networks W Fulp Fall 2008 5 m lnternel Protocols Medlum Access Control MAC Types Three general types contention round robin and reservation o Contention No permission to send pure ALOHA slotted ALOHA CSMA CSMACD Bus topology and wireless 0 Round robin Send when you have permission Token passing or polling Ring or bus topology 0 Reservation Request before sending Similar to TDM Dynamic must request sot before sending Ring or bus topology Is control centralized or distributed in the above E w Pulp lnternet Protocols Fall 2008 Medlum Access Control Pure ALOHA Protocol developed at the University of Hawaii 197039s 0 Simple protocol Send when you have data to send 0 Collisions may occur Two frames transmitted at or during the same time Signal garbled data is lost Even just a single bit overap Since broadcast sender can always tell if collision occurred Listen during transmissiona If collision wait a random time and try again Why random aActually wireless networks may not do this W Pulp Fall 2008 7 6 lnternet Protocols Medium Access Control 8 Performance of Pure ALOHA 0 Assume a fixed frame size constant transmission time 0 Users generate new frames according to a Poisson distribution with mean n frames per frame time If n gt 1 more frames generated than channel can handle For reasonable performance assume 0 lt n lt 1 0 Assume the probability of h transmission attempts during a frame time is also Poisson with mean 9 per frame time We will consider the case where g 2 n why 0 Under any load the throughput is where 190 is the probability that a frame does not suffer a collision 8P039 9 E w Filip lnternet Protocols m Fall 2008 Medium Access Control 9 0 Assume you are sending the gray frame let t be the time to send i Collides wi h the start of the shaded 39ame Rt u tn lt7 Vulnerable Collides with the end of the shaded 39ame t tD 2t i tu 3t Time 4 0 When would another frame collide with the gray frame7 The vulnerable period is between to and to 2t Why is the collision at the beginning a possibility W Filip Fall 2008 liiteriiei Protocols Medium Access Control 1 o o The probability that k frames are transmitted during the vulnerable period is given from the Poisson distribution 29 6 29 pk transmissions in 29 seconds k k012 0 Remember throughput is equal to the total arrival rate times the probability of a successful transmission 5 g pno transmissions in 29 seconds 2906 29 7 9T g 7 72g m w Fulp liiteriiet Protocols Medium Access Control Fail 2008 11 Pure ALOHA 0 Highest possible throughput is 18 What is an ezmmple ALOHA network E w Fulp Fail 2008 lnternet Protocols m lnternet Protocols m Medium Access Control 12 Slotted ALOHA An improvement of ALOHA where time is divided into slots 0 Time divided into discrete slots equal to one frame Requires users to agree on slot boundaries not trivial Continuous protocol is now discrete 0 Simple protocol Send when you have data must wait until beginning of next sot Vulnerable period is halved Why is the vulnerable period halved 0 As a result throughput is W Fulp Medium Access Control 1 Fall 2008 w ALOHA Systems Pure ALOHA Slo ed ALOHA throughput 0 Highest possible throughput 368 occurs when 9 1 0 Therefore the best performance is when 37 slots are empty 37 are successes and 26 are collisions W Fulp Fall 2008 lnternet Protocols Medlum Access Control Carrier Sense Multiple Access Protocols 0 ALOHA systems were precursors to CSMA All are contention based access protocols Slotted ALOHA improved pure ALOHA by CSMA increases performance by Listening to the carrier before sending as the name implies Does assume tpmp ltlt ttmm Three different CSMA types 1 persistent non persistent p persistent CSMA types differ on when they access an idle channel E w Fulp lnternet Protocols 14 Fall 2008 Medlum Access Control CSMA Variations l persistent listen to medium before sending 1 If idle transmit otherwise go to step 2 2 If busy continue to listen until channel idle then transmit immediately non persistent listen to medium before sending 1 If idle then transmit immediately otherwise go to step 2 2 If busy then wait random amount of time then go to step 1 p persistent listen to medium before sending 1 If idle transmit with probability 1 otherwise go to step 2 2 If busy then wait until channel idle then go to step 1 E w Fulp Fall 2008 15 Medium Access Control 16 lnternet Protocol 0 0 l perslslel ll CSMA Nonperslslel ll CSMA 0 lypel slslel lt CSMA o 5rper5l5lenl CSMA throughput leperslslenl CSMA 3 4 5 attempts per trametlme 0 Listening before sending increases throughput Persistent increases performance why The optimal value ofp 0 One problem remains if a collision occurs the medium remains unusable for the duration of the damaged frames E W Fulp Fall 2008 Medium Access Control 17 lnternet Protocol CSMA with Collision Detection CSMACD improves performance by aborting transmission immediatey once a collision occurs 0 Transmission rules 1 Medium idle transmit otherwise go to step 2 2 Medium busy listen until idle then transmit immediately 3 If collision detected transmit brief jamming signal 4 After jamming wait random amount of time then go to step 1 o Wasted capacity is reduced to the time to detect a collision How long does it take to detect a collision Just the propagation delay between the two farthest stations E W Fulp Fall 2008 lnternet Protocol Medlum Access Control 0 Consider the worst case Let the propagation time between the two farthest stations A and B be 75pm At time to station A transmits At time to tpmp 7 6 station B transmits Station B detect the collision immediately Station A detects at time to tpmp 7 E tpmp E to 215p p Packet starts Packet almost attime0 E atBatrE E ll gt ll gt a b Noise burst gets E backtoA at 21 E 4 4i l l c Collision at lt7 d E W Fulp Fall 2008 lnternet Protocol Medlum Access Control 1 o 0 Therefore a station cannot be certain it has seized the medium until 215p p has passed 0 As a result CSMACD systems require frames to be long enough to allow collision detection prior to end of transmission Collision detection can only occur during transmission E W Fulp Fall 2008 m m o lnternet Protocols Medium Access Centre pPersistent and CSMACD Performance 0 Consider 20 stations using p persistent or CSMACD Assume the p value is set to the optimal value 0 The average utilization per station for different MAC39s Ethernet PrPevssem a 5 a 5 me me What is the di erence between CSMACD and p persistent Disadvantage of optimal p persistent E W Fulp Fall 2008 m lnternet Protocols Medium Access Centre Dynamic p Persistent 0 Set the value of based on the number of stations A collision is a good indicator Kester amp Fulp 04 0 Let nw be the number of collisions during time w then 1 71w pp ersistem Dwamic P39PEVsistem a 5 a 5 me me What are the advantages of dynamic p persistent E W Fulp Fall 2008 lnternet Protocols Medium Access Centre m m Service Differentiation 0 Consider 20 stations and 2 classes of traffic Assume class 1 has higher priority than class 2 0 Set p to increase the utilization of the higher class PJ evssem m 2 mm Classes Dmevermated PJ evssem m 2 Ymmc Classes a 5 me a 5 me What is the di iculty of setting p dynamically o This strategy can be used for any shared medium wireless E w Fulp lnternet Protocols Medium Access Centre Fall 2008 m w Token Passing o Contention based MACs have poor performance with heavy traffic Due to the high number of collisions o Token passing requires stations to take turns no collisions o A small frame called a token is circulated when stations are idle o A station wishing to transmit must wait for the token 1 The station seizes the token and transmits its data frame 2 Data frame will circulate the ring the transmitting station will release the token if a Data transmission complete b Leading edge of data frame has returned circulated Token passing and polling are similar since both require permission What is the di erence E w Fulp Fall 2008 lnternet Protocols Medlum Access Control 2 5 CSMACD and Token Passing Performance 0 Want to compare utilization contention and token passing 7 throughput data rate 0 Define the following variables data rate of channel 7quot d maximum distance between any two stations 1 velocity of signal propagation 1 frame length fixed 0 Throughput is number of bits transmitted per unit time Fall 2008 throughput d l a t E w Fulp lnternet Protocols Medlum Access Control 25 0 Using the definition of a tpmp dv 7 d a 7 7 tfmme lr l v m rewrite the utilization equation using the throughput equation as U 0 Therefore utilization will depend on a propagation delay and frame transmission time 1 1a W Fulp Fall 2008 m lnternet Protocols lnternet Protocols Medlum Access Control Token Passing 0 Assume a LAN with 11 stations with maximum normalized propagation delay of a 0 Furthermore assume each station is always prepared to send 0 Time on the ring will alternate between data transmission and token passing Refer to a single instance of a data frame followed by a token as a cycle Define the following variables 0 average time for cycle tdata average time to transmit data frame ttoken average time to transmit token 26 W Fall 2008 Fulp Medlum Access Control 2 u therefore 0 he average cycle rate Is i f t 13 tdata u tdata ttoken 9999 we mwa 0 Must consider two cases agt1 alt1 mm QQQ ma mm moloa E w Fulp Fall 2008 m lnternet Protocol m lnternet Protocol Medlum Access Control o For a lt 1 Station starts at time to Receives leading edge of frame at time to a Completes transmission at time to 1 therefore cycle time is 1 9 n x 999 m n3 utilization is tEIl tula Station releases token takes time to reach next station w Fulp Medlum Access Control Fall 2008 o For a gt 1 Station starts at time to Completes transmission at time to 1 Receives leading edge of frame at time to a Station releases token takes time to reach next station therefore cycle time is a and utilization is 1 u 7 a a g 999 tEIl Q Ma tEIla W Fulp Fall 2008 KO m lnternet Protocol Medium Access Control 30 Token Passing E w Filip lnternet Protocol Medium Access Control Fall 2008 31 CSMACD Performance 0 Assume time is divided into slots where a slot is twice the propagation delay max time to detect a collision 0 Assume 11 stations where each station transmits with probability p for every slot Contention slots D E Transmission Contention Idle inte a interval interval Time 4 There are two types of intervals to consider i slots Transmission duration is 2a Contention E w Filip Fall 2008 lnternet Protocols Medium Access Control 32 0 To compute contention interval must determine the probability 1 that one station seizes the medium 71 q 1 p1p 1np1ip 1 where p is the probability a station transmits during a slot Maximum occurs when p i 1 7171 1 e n o The mean length of the contention interval w is 0 Elm E i pi slots in a row with collision followed by one success i1 00 i liq qlt1iqgti i1 q m w Fulp Fall 2008 lnternet Protocols Medium Access Control 3 w o CSMACD utilization is determined using the length of the transmission interval and the cycle 1 Z 1 ui 12alj l 2a q q CSMACD E W Fulp Fall 2008 lnternet Protocols Medium Access Control 34 CSMACD and Token Passing Comparison CSMACD and Token Passing CSMAICD a01 CSMAICD a1 Token Passing a01 Token Passinga1 number ofstations If token passing performs better than CSMACD m most cases why is CSMACD more popular m w Fulp Fall 2008 lnternet Protocols Medium Access Control 35 Wireless MAC 0 A Wireless LAN is considered a type of broadcast network If a station transmits everyone with range can hear A set of stations use the same channel As a result it is very similar to a bus topology Stations share a medium a similar MAC problems right 0 You cannot use a CSMA type of MAC CSMA considers interference only at the sender With wireless conditions at sender 31 conditions at receiver E W Fulp Fall 2008 lnternet Protocols Medlum Access Control 36 Wireless Station Problems Assume in the following two diagrams a station39s range is one hop Radio range station A transmitting 0 Hidden station problem using CSMA Assume station A is transmitting to B If C senses the medium it will not hear A If C then transmits it will interfere with B Frame transmitted by A is lost but A would never sense it E W Fulp Fall 2008 lnternet Protocols Medlum Access Control 37 Radio range station B transmitting 0 Exposed station problem using CSMA Assume station B is transmitting to A If C senses the medium and concludes it cannot send to D However it could send to D without interfering with A How is this possible 0 Therefore before transmitting a station needs to know the activity around the receiver E w Fulp Fall 2008 lnternet Protocols Medium Access Control 38 MACA Multiple Access with Collision Avoidance MACA is a wireless MAC 0 Assume station A wishes to send to station B A starts with a Request To Send RTS message B replies with a Clear To Send CTS message If A receives a CTS from B then it transmits the data Neighboring stations react as follows Stations hearing the RTS wait long enough for the CTS Stations hearing the CTS wait long enough for the data What is long enough Does this solve the hidden and ezrposed station problems E W Fulp Fall 2008 lnternet Protocols Medium Access Control 39 Ran eolA sUansmmev 9 e Range ol B s U nsmmev Asending an RTSloB B iespondingwilh mm 0 Consider station C within range of A but not B C hears the RTS from A but not the CTS from B C can transmit while the data is transmitted 0 Consider station D within range of B but not A D does not hear the RTS from A but hears the CTS from B D waits to transmit after the data is sent Can collisions still occur m w Fulp Fall 2008 lnternet Protocols m Data Link Layer Part 2 csc 343643 WAKE FOREST Department of Computer Science Fall 2008 Data Link Layer Part 2 1 Flow Control Another important issue for the data link layer is when the sender transmits faster than the receiver can process 0 Flow control Throttle the sender into transmitting no faster than the receiver can handle Requires a feedback mechanism 0 Rules typically are of the form Prohibit sending frames unti permission given 0 There are two basic strategies for flow control 1 Stop and wait 2 Sliding window W Fulp Fall 2008 lnternet Protocols C Data Llnk Layer Part 2 2 Stop and Wait 0 Rules NB message broken into multiple frames Sender waits for an ACK after every frame sent EOT sent to indicate end of message 0 Acceptable for a few large frames 51m 5W What happens if an ACK is lost lme May send next frame after the ACK has been received The data ACK repeats until the end of the message m w Fulp lnternet Protocols C Fall 2008 Data Llnk Layer Part 2 3 Effect of Propagation Delay and Transmission Rate Consider the maximum potential efficiency of a half duplex point to point link using stop and wait f17f27quot afn Using a polling procedure the following events occur Station 51 polls station 52 52 responds with f1 51 sends an acknowledgement 52 sends f2 51 sends ACK SQ sends fn 51 sends ACK 0 Suppose a long message is broken into a long sequence of frames E w Fulp Fall 2008 lnternet Protocols Data Link Layer Part 2 4 o The total time to send the message is TD T1 71 TF Where TI is the time to initiate sequence TI tp rop tpou tpmc and TF time to send one frame TF tp l op 75 frame tp roc tp r op tack tp roc To simplify assume TI is relatively small com pared to the frame transmissions Furthermore assume the processing and ACK time is negligible The formula is TD 2tprop tframe E W Fulp Fall 2008 lnternet Protocols Data Link Layer Part 2 5 0 Of the time spent only n tfmme is used for transmitting data Therefore the link utilization is u n 39 tframe tframe 2tprop tframe 2tprop tframe Defining a tpmptfmme the formula is 1 u 7 1 2a This is the utilization of the link howeuer why is the actual what the user sees utilization even lower E W Fulp Fall 2008 lnternet Protocols C Data Link Layer Part 2 6 Stop and Wait Utilization Examples 0 WAN example Two computers 1 km apart using ATM over a fiber optic link ATM frames cells are 424 bits with a bit rate of 15552 Mbps 424 27 gtlt 10 6seconds 15552 gtlt 106 tf39rame 103 75 tprop W 05 gtlt 10 seconds u 0027 12185 E w Fulp Fall 2008 lnternet Protocols C Data Link Layer Part 2 7 0 LAN example Two computers 01 km apart using 10 Mbps Ethernet Frame size is 1000 bits and v 2 gtlt 108 1000 7 1 X 10 4seconds 10 gtlt 106 tf39rame 100 tpmp W 5 X 10 7seconds u 099 120005 What can we conclude from the previous ezmmples E w Fulp Fall 2008 lnternet Protocol Data Link Layer Part 2 s Link Utilitization for StopandWait Flow Control m w Fulp lnternet Protocol Fall 2008 Data Link Layer Part 2 9 Sliding Window Flow Control Overview 0 Send 0 Rece Receiver allocates buffer space for 11 frames What is the bu er space for stop and wait er may transmit 11 frames without an ACK To keep track of which frames have be ACKed each has a sequence number iver ACK39s a frame by sending an ACK that includes the sequence number of the next expected frame 0 Sender can send the next 11 frames staring with the last received sequence num ber E w Fulp Fall 2008 m lnternet Protocols Data Link Layer Part 2 10 o A single ACK can acknowledge multiple frames Receiver gets frames 2 and 3 but waits for frame 4 to ACK Once frame 4 arrives ACK5 is sent to the receiver Therefore frames 2 3 and 4 are ACKed Station A frame 2 frame 3 39ame 4 frame 5 Station B time 0 Therefore the sender can send multiple back to back frames making better use of the channel w Fulp FallQOOS lnternet Protocols Data Link Layer Part 11 0 Sequence number is a field in the frame finite size o If k bits are reserved for the sequence number then the values range from O to 2k 7 1 modulo counter o This can be depicted as a sliding window frames alreadytransmitted I frames U181 may be transmitted I f l lll2l3l4l5l6l7lUl l2l3l4l5l6l7l I l SEQUENCE Wumnks as WinduMands as sender number rrames transmitted rrames ACKEd framesalreadyreceived I framestnatmaybereceived I l Ulil2345l67l lil 345l67 I l Wl d m l as wmueManus as frames rEEElVEd TENESACKEd o In the figures above the window is represented using bits w Fulp Fall zoos m internet Protocois Data Link Layer Pan 2 12 Siatioi iA Station B 0 NB can only sendreceive n window size beyond last ACKH o In this example 11 and k E W Fuip Faii 2008 Data Link Layer Pan 13 internet Protocois Siaiioi iA Station B frame 3 frame 5 frame 6 o In this example 11 and k rm w Fuip Faii 2008 m lnternet Protocols lnternet Protocols Data Link Layer Part 2 14 Sliding Window Performance 0 Assume a full duplex point to point link using sliding window tprop o Efficiency depends on n window size and a twang 0 To simplify the analysis normalize the frame transmission time therefore the propagation time is 1 There are two cases to consider 1 ACK for the first frame reaches station A before the window is exhausted station A transmits Without pausing n gt 2a 1 1 m m a 3 m 5 ACK 1 m 2 1I frame 23 frame a3 game a2 a 3 ACK 1 W m Fulp Fa Data Link Layer Pan 112008 215 2 Station A exhausts window before an ACK is received station A must pause n lt 2a 1 w 0 I a 3 1 l0a1 A ACK1 frame n ACKl 0 Using the two cases the link utilization is 1 ngt2a1 nlt2a1 1 L 2a1 w Fulp Fall 2008 lnternet Protocol Data Link Layer Part 2 16 Link Utilitization for Sliding Window Flow Control 1 5 m lnternet Protocol w Fulp Fall 2008 Data Link Layer Pan 17 Error Control Mechanisms that detect covered in previous slides and correct via retransmission errors that may occur 0 Two types of errors possible 1 Lost frame Frame data or control fails to arrive 2 Damages frame Frame recognized but some bits have been changed What is the dt erehce with error detection using parity 0 Error control mechanisms are referred to as ARQ Automatic Repeat reQuest there are three common versions 1 Stop and wait ARQ 2 Go back N ARQ 3 Selective reject ARQ E w Fulp Fall 2008 lnternet Protocols E w Fulp lnternet Protocols m Data Link Layer Part 2 1s StopandWait ARQ As previously described sender transmits a frame then waits for ACK 0 Two types of errors may occur Frame received in error detected gtr Receiver sends NACK to sender gtr Sender then retransmits frame Frame data lost during transmission gtr Receiver neither ACKs nor NACKs gtr Sender times out and retransmits What additional resources are required by the sender lfthe ACK is lost gtr Frame received correctly but ACK is lost gtr Sender times out and retransmits gtr Receiver gets frame it needs to identify that it is a copy Fall 2008 Data Link Layer Part 19 Avoiding the lost ACK problem gtr Label frames as O or 1 alternating gtr ACKO acknowledges frame1 while ACK1 acknowledges frameO timeout timeout Station A Station B 0 10V LIMOV OJMOV L IOV HH W Fulp Fall 2008 lnternet Protocols Data Link Layer Part 2 20 StopandWait ARQ Performance 0 We have previously shown that error free stop and wait achieves a maximum link utility of However now we wish to account for the possibility of errors 0 Utilization can be defined as u tf39rame ttotal where tfmme is the time to transmit a frame and ttotal is the total time the line is used to transmit the frame E w Fulp lnternet Protocols Fall 2008 Data Link Layer Pan 21 o For error free operation using stop and wait ARQ u tf39rame 25mm 2tpmp tPTOP We will divide by tfmme and use a thame o If errors occur then tf39rame u n39r 39 ttotal where in is the number of transmissions required therefore stop and wait ARQ utilization is tf39rame n39r 39 tf39rame 2tp39rop E w Fulp Fall 2008 lnternet Protocols Data Link Layer Part 2 22 Which can be rewritten as 1 anr12a 0 Must determine a value for nr based on the probability that a frame is in error 1 Assume ACKs and NACKs are never in error The probability that it will take k attempts to transmit a frame successfully is pk l 7p which is one success after k 7 1 failures m w Fulp Fall 2008 lnternet Protocols Data Link Layer Pan 23 The expected number of transmissions is 0 HT Eltransmissions E i pli transmissions i1 E w Fulp Fall 2008 Data Link Layer Part 2 24 lnternet Protocols Link Utilitization for StopandWait ARQ utilization 0 0 E W Filip Fall 2008 Data Link Layer ParLQ 25 lnternet Protocols GoBackN ARQ A type of continuous ARQ 0 Similar sliding window flow control sender may transmit multiple frames based on window size 0 ACKi sti indicates expected frame Every frame need not be explicitly ACKed Does sliding window flow control require each frame be ezrplicitly ACKed Fall 2008 m w Filip internet Protocois C Data Link Layer Part 2 26 0 Modifications Sender sets an acknowledgement timer for each frame NACKM indicates gtr Frame i not received resend along with any subsequent frames gtr Previous frames accepted Receiver discards any frame out of order Every lostdamaged frame must be NACKed Maximum window size is 2 7 1 0 There are two error cases 1 Errorlost frame 2 Errorlost ACKNACK E W Fuip Faii 2008 internet Protocois C Data Link Layer Pan 27 GoBackN Error Cases Frame Error 0 Sender transmits FRAMEM o Receiver gets FRAMEM then detects error 0 Receiver transmits NACKM indicating FRAMEM rejected 0 Sender receives NACKM and must retransmit FRAMEM and any subsequent transmitted frames StationA 1m3m5m 0 39 3 StationB m m IEI m m m Iii I 393 discard 4 4o VaII time E W Fuip Faii 2008 internet Protocois CSC In 36 I Data Link Layer Part 2 Lost frame 0 FRAMEM lost in transit sender does not know 0 Sender sends FRAMEH 1 o Receiver gets FRAMEH 1 which is out of ora39er o Receiver sends NACKM first missing frame 0 Sender receives NACKM and must retransmit FRAMEH and any subsequent transmitted frames StationA W m El El W HRH 7 El ITI xx ngt ngt m m m m m m m m m w time discard internet Protocois CE Data Link Layer Pan Sender Time Out o Sender transmits FRAMEM o FRAMEM lost in transit o Sender times out for ACKM o Sender retransmits FRAMEM and any subsequent frames ITI FRAME0 timeout StationA 0 ITI El 0 T El x 2lt StationB M I IA IE time E w Fuip 28 RM 2008 Rm 2008 lnternet Protocols m lnternet Protocols m Data Link Layer Part 2 Damaged or Lost ACK 0 Receiver get FRAMEM and sends ACKH 1 o ACKH 1 lost in transit o Sender will eventually time out or get subsequent ACK Damaged or Lost NACK o Receiver sends NACKM due to error 0 NACKM lost in transit o Sender will eventually time out and retransmit W Fulp Data Link Layer Part2 GoBackN Window Size Although similar to sliding window flow control go back n window sizes must be S 2 7 1 where k is the sequence field length Station A E p O Y Station B time E 114 k 2 Sender does not know if the second ACK1 is for the first or last FRAMEO StationA E lTl El El e e v v StationB m l1l Ill lil time n3k2 W Fulp 30 Fall 2008 Fall 2008 Data Llnk Layer Part 2 32 lnternet Protocol GoBackN ARQ Performance 0 Same assumptions as stop and wait ARQ analysis 0 Approximating n is different since each error may cause multiple frame retransmissions n Elnumber of frames required to successfully transmit one frame fwd pHlt1 7p i1 where is the total number of frames transmitted if the original frame must be transmitted i times E W Fulp Fall 2008 Data Llnk Layer Pan 33 lnternet Protocol 0 Therefore the link utilization for go back n ARQ is g 11 gt 2a 1 n 17 lt2a1gtlt1inpgt lt 2 1 Link Utilitization for GoBack N ARQ n 50 E W Fulp Fall 2008 m E w Fulp lnternet Protocols lnternet Protocols Data Link Layer Part 2 Selective Reject ARQ Only the specific damaged or lost frame is retransmitted o If FRAMEM is lost or damaged then a NACKM is returned Only FRAMEM is then retransmitted 0 Receiving device must place frames in correct order Since frames may arrive out of order 0 Modifications Receiver continues to accept frames after damaged frame Smaller windows sizes are required n S Qk l Fall 2008 Data Link Layer Pan o ACKM and NACKM still imply the successful receipt of all previous frames Frames after the error frame can not be ACKed until the damaged frame is received StanonAlTllTlm Station B W Fulp Fall 2008 35 34 Data Link Layer Part 2 36 internet Protocois FRAME0 timeout StationA 0 W 7i 0 m m g StationB M i IE I m IE time n 3 k 2 Receiver believes the second FRAME0 is a new frame not a repeat FRAMEO timeout StationA 0 m 0 m Station B iil ill L n 2 k 2 Receiver knows second FRAME0 is a repeat since it expects either FRAME2 or FRAME3 time Rm 2008 E w Fuip Data Link Layer Pan 37 internet Protocois Selective Reject ARQ Performance 0 Approximating n is the same as stop and wait 1 ngt2a1 u 725 n lt 2a1 Link Utiimzation for SeiectwerReJect ARQ n 50 Rm 2008 w Fuip m lnternet Protocols Data Link Layer Part 2 38 ARQ Utilization Comparison SelectiveReject and GoBackN ARQ n 50 1 l SR p0001 SR p01 08 X u SR p025 GBN p0001 GBN p01 06 GBN p025 9 16 g 04 0 C E W Fulp Fall2008 lnternet Protocols Data Link Layer ParLQ 39 GoBackN and Selective Reject 0 As seen in the previous figure selective reject yields a higher link utilization 0 However selective reject is expensive to implement Sender needs extra state information to retransmitt Receiver needs complex storage and sorting 0 Therefore go back n is typically used for implementation m w Fulp Fall 2008 IEEE 802 csc 343643 WAKE FOREST Department of Computer Science Fall 2008 lnternet Protocols C E lEEE 802 1 IEEE 802 Standards 0 Previously we discussed abstract channel allocation protocols 0 IEEE has produced several LAN standards known as IEEE 802 0 IEEE 802 standards cover Logical Link Control LLC IEEE 8022 CSMACD IEEE 8023 Token bus IEEE 8024 Token ring IEEE 8025 Wireless IEEE 80211 and 80216 IEEE 8021 serves as an introduction to IEEE 802 E w Fulp Fall 2008 lnternet Protocols lEEE 802 2 IEEE 8023 0 Standard describes a 1 persistent CSMACD LAN What are the transmission rules 0 8023 History Pure ALOHA for communication between Hawaiian Islands CSMACD developed at Xerox PARC connected 100 stations first demo November 11 1973 by Robert Metcalfe System called Ethernet Why the name Ethernet DEC and Intel later created standard for 10 Mbps Ethernet the basis for IEEE 8023 0 Remember 802345 will describe the physical and MAC layers E W Fulp Fall 2008 lnternet Protocols lEEE 802 3 IEEE 8023 Physical Layer 0 Four types of cabling Name Cable Max segment Nodesseg Advantages loBaseS thick coax 500m 100 good for backbone 108ase2 thin coax 200m 30 cheap loBaseT twisted pair 100m 1024 easy setup loBaseF fiber optics 2000m 1024 long distance 0 Names have the form acBasey o IOBase5 thick Ethernet Requires thick size of a garden hose yellow coaX Connections via vampire taps o IOBase2 thin Ethernet Smaller diameter coaX cable TV size Connection via T junctions E W Fulp Fall 2008 lnternet Protocols lEEE 802 4 0 Thick and thin Ethernet suffer from cable breaks bad taps and loose connectors real bus topology no hub o lOBase T Twisted pair telephone all connect via hub Limited distance 100m 0 lOBase F Fiber optics long distances possible low sn ratio Twisted pair Transceiver controller Transceiver Connector lOBase5 lOBaseZ lOBaserT E W Fulp Fall2008 lnternet Protocols lEEE 802 5 0 Manchester encoding used by 8023 baseband systems Manchester and Differential Manchester Advantages and disadvantages High is 085 volts and low is O85 volts Bit stream Binary encoding Manchester encoding Differential Manchester encoding Transition here Lack oftransition here indicates a 0 indicates a1 E W Fulp Fall 2008 lnternet Protocols C m lnternet Protocols C m lEEE 802 6 8023 MAC Frame Structure 0 Frame structure is Bytes 7 1 20r6 20r6 2 071500 046 4 ll Destination Source Data ddress address 4 ll Pad Preamble Checksum Length of framedellmlter datafleld 0 Frame starts with preamble 7 bytes of 10101010 Results in a 10 MHZ square wave for 56 psec Allows clock synchronization 0 Start delimiter is next 10101011 indicates data is next Source and destination addresses follow MAC address 6 byte standard for 10 Mbps First bit is 0 for ordinary address 1 for group address W Fulp Fall 2008 lEEE 802 7 Group address All stations in the group receive If all bits are 139s then broadcast frame 0 Bit 46 adjacent to high order bit distinguishes between local and global addresses Local Assigned by administrator no meaning outside LAN Global Assigned by IEEE stations have the same address 0 Length field identifies number of bytes in data field 64 to 1500 bytes possible Why 64 Why 1500 As transmission speed increases frame size must increase or cable length decrease o Checksum CRC of the data is added to the end W Fulp Fall 2008 lnternet Protocol lEEE 802 8 IEEE 8023 MAC Medium Access o CSMACD requires a random wait after collision o Binary exponential backofF algorithm After collision time divided into discrete slots equal to 2tpmp After first collision each station waits O or 1 slots random After second consecutive collision each station waits either 0 1 2 or 3 slots randomly selected Therefore after i collisions wait 0 to 2i 7 1 slots Exponential growth reduces multiple collisions Fairness is a growing concern is the back o procedure fair to everyone How could we provide di erentiated service m w Fulp Fall 2008 lnternet Protocol lEEE 802 9 enoe lmur Incremer anemm 39 1 Alarm llmll reached Campule and waif bade lime Transmil iam sequ d 5 39 quot22 2 g g g1 35 g g is 35 e 5 53 E3 Egg 5 E E cg 38 3 g 339 2 22 jg 25 g 3 3 3 50 9E g Egg g u 23 52 as 5 2 E n 53 E 2 3 E EEE quot3 0 23 z 1 a is 5 3 1 3 D g E a 5 85 o If 35 5 E 0 9 25 E 5 O transmit receive E W Fulp Fall 2008 lEEE 802 10 lnternet Protocols Switched 8023 0 8023 performance decreases as the number of stations increases Primarily because collisions are very expensive What does this mean Any reasonable solutions 0 One solution is switched 8023 Swltcn Cunnectur Tu nusts am a LAN 6 El l2th 39Tv cunnecnun n ma nust umputers Tu nusts o Consists of a switch containing a high speed backplane m w Fulp Fall 2008 lEEE 802 11 lnternet Protocols 0 When station wishes to transmit it sends the standard frame 0 Switch determines which card the frame is destined for lf destined for another card sent leps to that card What are the implications to network security 0 What is two stations on the same card send at the same time Two possibilities depends on manufacturer 1 Collision occurs on the card collision domain CSMACD 2 Buffer every port switch sends frames when medium idle each port a collision domain Most places have moved to switched Ethernet including our department so do collisions still exist E W Fulp Fall 2008 lnternet Protocols lEEE 802 Fast Ethernet 8023u o The previous slides described classic Ethernet Bus and star topologies and maximum data rate of 10 Mbps 0 8023u describes fast Ethernet Maximum data rate is 100Mbps 10 times faster Places limitations on the CSMACD protocol What are the limitations How can it be resolved 0 Medium alternatives Name Cable Max segment Topology IOOBaseT4 twisted pair cat3 100m star looBaseT twisted pair cat5 100m star 1008aseFX multimode fiber two strands 2km star E w Fulp lnternet Protocols Fall 2008 lEEE 802 80232 is the Gigabit Ethernet 802395 gigabit Ethernet standard completed in 1998 Maximum rate is 1 Gbps 10 times faster than fast Ethernet Again increasing speed places limitations on CSMACD What are the limitations Slot time extended to 512 bytes frames must be 2 64 bytes How can this work Frame must be greater than slot 80232 medium alternatives Name Cable Max segment Topology 10008aseSX multimode fiber two strands 550m star 10008aseLX single mode fiber two strands 5m star IOOOBaseT twisted pair cat5 100m star E w Fulp Fall 2008 13 12 lnternet Protocols C lEEE 802 14 o 8023ae is the 10Gbps Ethernet standard ratified in 2002 Only operates in full duplex mode point to point connections CSMACD protocol is disabled How can Ethernet operate without CSMACD 8023ae medium alternatives Name Cable Max segment IOGBaseSR multimode fiber two strands 300m IOGBaseLR single mode fiber two strands 10km loGBaseEW single mode fiber two strands 40km When would 8023ae be useful m lnternet Protocols C w Fulp Fall 2008 lEEE 802 15 o The IEEE 8024 standard describes a token bus 0 While 8023 was widely accepted GM had reservations 8023 is probabilistic no guarantees of delivery Not appropriate for real time data assembly line IEEE 8024 0 GM liked the idea of a token ring but An actual ring topology is not robust Ring topology does not fit an assembly line 0 8024 was developed to combine Robustness of linear medium 8023 Predictability of token passing E w Fulp Fall 2008 lnternet Protocols lEEE 802 16 0 Solution is to logically organize stations as ring Stations must know left and right neighbors 0 Use token passing for MAC After sending station passes token to neighbor addressed 17 777777777 2 Broadband quot c2o r 14 coaxial cable Logical ring l i l 1 77 This station not currently in 13 11 4 7 19 the logical ring Direction of token motion 0 In general MAC is very complex over 200 pages describing 10 different timers E w Fulp Fall 2008 lnternet Protocols lEEE 802 17 lEEE 8024 MAC 0 Stations ordered based on MAC addresses 0 Token is passed from highest to lowest Each time a station receives the token it may send for a duration of time token hold time Any need for minmag frame size If no data to send pass token to neighbor 0 Supports 6 priorities each with token timer Highest priority can provide guaranteed bandwidth E w Fulp Fall 2008 lnternet Protocols C lEEE 802 18 0 Logical ring maintenance Enable stations to enterleave ring Once ring established each station must maintain address of predecessor and successor in the ring Periodically token holder asks Anyone Wish to join7 Is contention problem with tohen bus What is necessary to leave the ring Other problems and issues How to recover if the token lost How can multiple tokens be managed E w Fulp lnternet Protocols C Fall 2008 lEEE 802 19 o The IEEE 8025 standard describes token ring 0 8025 Attributes 0 Major design issue is physical length ofa bit IEEE 8025 Rings are fair and have bounded channel access IBM developed the ring as its LAN technology Each station can only store a single bit at a time Therefore stations do not store and forward an entire frame lfthe propagation speed is 200 X 106 msec the ring is 1000 m and bit rate is 1 Mbps then only ring at once bits are on the The token will not even t on the ring E w Fulp Fall 2008 lEEE 802 20 lnternet Protocols o A token is circulated while the stations are idle o If a station wishes to transmit then it seizes the token This is done by inverting a bit in the 3 byte token This converts it into a normal data frame What 0 Station is free to transmit Data frames transmitted around ring and returned to sender An ezrtremely e cz39ent ACK from receiver is possible 0 Due to the limitations of the ring topology IBM implemented token ring as a star E W Fulp Fall 2008 lEEE 802 21 lnternet Protocols 1 i 2 o 5 g 25 goes 3 Ea Egg Egg 533 2 a 0 3L g Egg ggd lt5 358 gm 23 582 1555 T gt eo g E gm 25 2 SE2 g9u egg egu 22 g lt2 333 deg swig 6 38 5E 523 is in as use a E25 its 922 I x Token I kg mek I r39x kg aw E W Fulp Fall 2008 lnternet Protocols lEEE 802 22 IEEE 8025 MAC 0 Token is a 3 byte frame To seize the token a single bit is set to 1 which converts it to a start of frame sequence token 20r6 20r6 4 1 1 lEDl FSl A A Ending delimiter 4 Frame status No limit iv address i l Frame control Access control Starting delimiter token ring lrame Fc Destination source Checksum 0 Station may hold the token 10 msec and transmit E w Fulp lnternet Protocols lEEE 802 Faii 2008 23 0 Data frame Starting delimiter and ending delimiter mark frame boundaries Access Control AC contains token bit Frame Control FC distinguishes data from control frames 0 Generally ring can not hold entire data frame once bits return to sender they are removed 0 8025 also supports priorities To send frame of priority n must seize token with same or lower priority 0 Separate station is the monitor Monitors the ring and ensures correct operation Checks for lost token multiple tokens E w Fulp Faii 2008 lnternet Protocols lEEE 802 24 8023 8024 8025 Comparison Issue 8023 8024 8025 simple engineering yes no yes analog components yes yes no deterministic no yes yes priorities no yes yes high load performance poor good good reliability good good good current deployment everywhere small large E w Fulp lnternet Protocols m Fall 2008 lEEE 802 25 Resilient Packet Ring 80217 0 80217 is Resilient Packet Ring RPR completed June 2004 Dual ring technology opposite directions Can handle mutliple gigabit transmission speeds For MAN and WAN 0 Designed to transport packets layer 3 Can provide different forms of fairness different types of traffic can be transported What is important about dz erent types of tm c W Fulp Fall 2008 Intern PW IEEE m 80211 The standard describes the physical layer and MAC unpev isms Lngical link cumml MAC Data link ian suman Physical layer mm mm HRLDSSS OFDM M m mm was 0333 OFDM 0 Only one MAC but 5 different physical layers Infrared FHSS DSSS OFDM HR DSSS and OFDM o The IEEE 80211 standards are for wireless networks LAN Therefore 80211a b and g only differ in the physical layer E w Fulv new Emma Fall 2m IEEE m 27 Spread Spectrum 0 Most 80211 wireless physical layers rely on spread spectrum o The idea of spread frequency was developed before WWII Lamarr and her husband an arms merchant lived in Europe Radio controlled torpedoes was sought by governments But narrowband one frequency wireless is easilyjammed E w Fulv Invented and patented in part by Austrianborn Hedy Lamarr Fall 2m m lnternet Protocols C m lnternet Protocols C lEEE 802 28 Lamarr developed the idea of hopping from frequency to frequency during transmission sending short bursts Even if a frequency was jammed the entire signal was not Of course there is a secret predetermined hopping pattern Hedy Lamarr fled to the US before the war started She married George Antheil and patented spread frequency US patent number 2292387 dated 1942 Unfortunately the US government did not believe in the system It was never used and the patent eXpired in 1959 This work was rediscovered in the 199039s for wireless networks So what else was Hedy Lamarr famous for W Fulp Fall 2008 lEEE 802 29 80211 Phy calLayer 80211 Infrared 80211 FHSS 80211 DSSS 80211a OFDM 80211b HRDSSS soz1m OFDM Physical layer Frequency Hopping Spread Spectrum FHSS used by 80211 Uses 79 channels each 1 MHZ wide Randomy hops from channel to channel Transmits a short burst per hop maXimum rate is 2 Mbps All stations must be synchronized How is this accomplished Direct Sequence Spread Spectrum DSSS used by 80211 Spreads the power over a larger spectrum See CDMA for details maXimum rate is 2 Mbps W Fulp Fall 2008 m Internet Protocols C IEEE 802 3 o Orthoganal Frequency Division Multiplexing ODFM 80211a Divides channel into smaller sub channels Transmits on different sub channels in parallel Very similar to DSL modems maximum rate is 54 Mbps 80211g uses a variation of OFDM maXimum rate is 54 MBps 0 High Rate Direct Sequence Spread Spectrum HR DSSS 80211b Improved encoding with a maXimum rate of 11 Mbps 80211b is slower than 80211a its range is 7 times greater 0 All methods use Industrial Scientific and Medical ISM bands Unlicensed frequencies used by microwaves cordless phones So consider what the error rate is Now let us move from EE back to the comfort of C5 E W Fulp Fall 2008 Internet Protocols C iEEE 802 31 80211 Network Types There are two basic types of 80211 wireless networks Ease Tu Wired netwurk Siatiuri inirasimdure Basic Service Set Independent Basic Service Set adrhu wireless netwurk 0 Infrastructure Basic Service Set Infrastructure BSS Have a wireless Access Point AP present AP are used for all communications If one station needs to communicate with another station how many hops are required w Fulp Fall 2008 o lnternet Protocols lEEE 802 32 0 Independent Basic Service Set ad hoc network MANET Stations communicate directly with one another Must all the stations be within range of each other Designed to be dynamic and self organizing hence ad hoc It appears that an ad hoc wireless network can do as much as a infrastructure BSS and more what are two advantages of using an infrastructure B55 0 Each network type will have a different MAC Distributed Coordination Function DSF Point Coordination Function PCF E W Fulp Fall 2008 lnternet Protocols lEEE 802 33 Distributed Coordination Function Distributed Coordination Function DCF is for ad hoc networks 0 Uses CSMACA Collision Avoidance and no central control Physical and virtual channel sensing 0 Physical sensing Station listens if idle physically and virtually then transmit Does not sense channel while transmitting lfthe channel is busy it waits until idle If a collision occurs then binary back off is used Do stations send whenever the channel is idle What about the hidden and exposed station problems E W Fulp Fall 2008 lnternet Protocols lEEE 802 34 DCF and MACAW The preceding physical sensing but virtual sensing is also used 0 Virtual sensing is done using MACAW enhancement of MACA Sender and receiver are required to send RTS and CTS 0 Assume station A sends to B a complete transaction would be 1 Station A sends RTS message to station B 2 Station B replies with a CTS message 3 Station A sends frame and sets an ACK timer 4 Station B receives the frame and sends ACK 0 RTS and CTS include a Network Allocation Vector NAV field NAV indicates the time for the complete transaction Allows for virtual sensing E w Fulp lnternet Protocols Fall 2008 lEEE 802 35 CTS NAV 0 Assume stations C and D are present C within A D within B Station C hears the RTS and is idle for NAV Station D hears the CTS and is idle for the NAV 0 After transaction is complete other stations may send Channel is idle physically and virtually Therefore what occurs after a successful transaction E w Fulp Fall 2008 lnternet Protocols lEEE 802 36 Point Coordination Function Point Coordination Function PCF is used for infrastructure 35 0 PCF provides contention free access using the access point Access is coordinated by the access point AP As a result PCF can provide fair and predictable service Is DCF fair or predictable Why is predictability important 0 PCF operation is based on polling The AP transmits a beacon frame asking for new stations Once a station is added it is systematically polled A station can send one frame per poll IfI use a AP with my wireless network I am using PCF right E w Fulp Fall 2008 lnternet Protocols lEEE 802 37 What is Actually Used 0 You won39t find a PCF option on your average AP Most vendors Cisco Proxim and Symbol don39t include PCF Even when the chipsets have PCF functionality AP vendors don39t activate it o PCF has been part of the 80211 standard since 1997 The problem is 80211 is fairly vague when defining PCF As a result you would need to use the same vendor for the access points and radio cards to make it work properly The Wi Fi Alliance does not include PCF functionality in their interoperability standard 0 Therefore if you have an AP the wireless network will use DCF and the AP behaves like any other station E w Fulp Fall 2008 lnternet Protocols lEEE 802 38 80211 Frame Structure Bytes 2 2 6 6 6 2 6 072312 4 Durr Address Address Address Address Cheeky control alien 1 2 3 seq 4 Data Sum l Bits 2 2 4 1 1 1 1 Tquot1 Lquot1 T0 me Ree Version Type Subtype D8 D8 MP W PWrMure W o Frame control o The first field is the frame control that has 11 sub fields Protocol version indicates the protocol used DCF or PCF both can be used simultaneously The type field indicates control data or management To D5 and FromDS indicates if the frame is going to or coming from and intercell distribution system What is an intercell distribution system m w Fulp lnternet Protocols Fall 2008 lEEE 802 39 MF indicates more fragments will follow Retry indicates the frame is a retransmission Power management is used to put the receiver to sleep or to wake the receiver The More bit tells the receiver more frames follow W bit indicates the frame is encrypted using the Wired Equivalent Privacy WEP The 0 bit indicates the frames must be processed in order The second field of the data frame is the Duration Tells how long the transaction will take NAV Four addresses follow interpretation depends To DS and From DS E w Fulp Fall 2008 lnternet Protocols C lEEE 802 40 80211 Frame Address Fields Emema Ease statlun quot I PM E g gig o If sender and receiver in the same cell Addrl is the destination station address receiver Addr2 is the source station address sender o If sender and receiver are in different cells Addrl is the final destination station address receiver Addr2 is the immediate sender relay from distribution Addr3 is the intermediate destination Addr4 is the original source original sender Why is this necessary Is this muting E W Fulp Fall 2008 lnternet Protocols C lEEE 802 41 80211 Frame Structure Continued 0 The sequence field is between the third and fourth addresses Allows fragments to be numbered 12 bits for the frame and 4 bits identify the fragment 0 The Data field stores the frame data Payload may contain up to 2313 bytes 0 The Checksum field follows E W Fulp Fall 2008
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'