Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Amira Cormier on Monday November 2, 2015. The Class Notes belongs to CS4590 at California State University - East Bay taught by Staff in Fall. Since its upload, it has received 190 views. For similar materials see /class/234375/cs4590-california-state-university-east-bay in ComputerScienence at California State University - East Bay.
Reviews for ComputerNetworks
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Routing Continued Outline Routing to Hosts ARP amp DHCP Tunnels Mobile Host Routing Maklng Routing Scale Datagram Forwardlng Strategy 7 eyey datagram contains destinations address 7 lf dlrectly connected to destrnatlon network then forward to host 7 lfnot directly connected to desunatlon network then forward to some router e forwarding table maps network number into nert hop 7 each host has a default route 7 each router maintains a forwarding table Example 2 Netwurk Number Next llup R3 R interface 1 interface it Address Translatlon Map IP addresses into physical addresses destlnatlo 05L 7 naithop rou Techniques 7 encode physical address in hostpart ofIP address won t work for Ethernet addresses 7 tablerbased RP 7 At host keep a table OH to physical address bindings eARP cache 7 broadcastrequest lfIP addressnot in table 7 target machine responds with its physical address 7 table entries are discarded ifnot refreshed 7 Update everylSmlnules ARP Details Request Format 7 HardwareType type ofphysical network e g Ethanet e ProtocolType type ofhigher layer protocol e g 1P 7 HLEN amp PLEN length ofphysical and protocol addresses 7 Operation request orresponse e SourceTargetrPhyslcalProtocol addresses Notes 7 table entries timeout in about 15 minutes 7 update table with source when you are the target 7 update table ifalready have an entry 7 do not refresh table entries ifhost Isn t the target and a table entry doesn t exlst ARP Packet Format u u 16 at HaYdMYEWPE l Pvutururrvpe EIXEIBEIEI HLen or New 32 opevatlun SuuvreHainwaieAnm hvtEsEI 73 SuuireHavnwwwhms t eel SuuvcerutuculAddYbvtes el SuuvcerutuculAddV WES 2 73 Tavaetrtavnwamnwhvles u 71 TametHavwaveAddV bytes 75 TavgeleluculAddVbvtes 4 ATM LANE I ATM does not support broadcasting use LAN emulation LANE I 3 different servers are required to emulate regular LAN service 7 LECS LAN emulation con guration server 7 LES LAN emulation server 7 BUS Broadcast or Unknown server Note this does not work for ATM WAN 6 ATM LANE ATM ARP I Client connecw to LEC at startup I Part of the classical IP over ATM model 7 Send ATM address 7 Receive info on type ofLAN being emulated I A server resolves addresses I Physical ATM network is divided into smaller I Client registers is ATM address and MAC logical 1P subnets LIS address with LES r Receives BUS address 7 All nodes on same subnet have same network number 7 Hosts that share a subnet can communicate I BUS maintains a single point to multipoint VC to 7 Hosts on different subnets communicate through the all clienw so it can broadcast messages to them Iver ATM ARP I Advantage is many hosts and routers can be connected to the same ATM WAN without giving them the same IP network number 7 Helps ifall hosts not controlled by asingle administrative enti ATM WW 7 Helps with scalability by limiting the number ofnodes that rely on one ATM ARP se er I Broadcast is not used 7 each host registers with the server WAN ATM ARP 9 in DHCP DHCP Used for autocon guration I DHCP discover message sent out by host 7 Match IP address to MAC address 7 Host address is 255 255 255 255 7 Get IP address of default router r This is abroadcast message 7 Get IP address ofDomain Name Server I DHCP server should respond Server maintains a pool of IP addresses and leases r DHCP messages are sent using UDP them to hOStS 0 dam I Relay agents can be used ifa DHCP server is to be shared among subnets u l2 Unlcasttu server ehavvy ha bytes I l shame 54 bytes me 128 bytes I l uplmns DHCP packet Internet Control Message Protocol Echo ping Redirect from router to source host Destination unreachable protocol port or host TTL exceeded so datagrams don t cycle forever Checksum failed Reassernbly failed Cannot fragment Virtual Tunnels I A Way to keep IP network lines private 7 Leased lines are shared with other customers I Create an IP tunnel 7 Virtual point to point connection between two hosts across many networks 7 Encapsulate packets Eavvavahah mm MW e mth v mm WW 6 mm m mnsmms Tunneling 17 lP heaven lP heaven lP heaven Deshhaunh 2x Deshhahnh m n at Deshhaunh 2x lP heaven l W payload l Dewaan 2 X l w payload l w paytnav V inual Tunn els Tunneling I Used for increased security and for multicasting I Disadvantages increased packet length decreases routerperformance speed increases management issues I Sending nost Foreign agent 12 0 0 0 Home agent 10 0 0 3 Home network Mobile nost networw0 10009 Mobile Host Routing Mobile Host Routing I Mobile hosts needs a new IP when it attaches to a new network I Home agent will act as intermediary between sender and mobile host 7 Senders use mobile hosts permanent IP address which re ects the network that the home agent is attached to I Foreign agent will contact home agent when it detects a new mobile node on its netwo 7 Home agent forwards packets to foreign agent for delivery to mobile host Mobile Host Routing I Using proxy ARP home agent impersonates the mobile no e 7 Home agent inserts IP address ofthe mobile host and uses its own physical address 7 Gratuitous ARP message is sent when it is known that the mobile host is at anewnet r Use tunneling to deliver messages 7 Wrap packet to mobile host in 11 packet addressed to foreign agent Mobile host uses its permanenth address to reply 22 Mobile Host Routing I Issues optimization 7 Triangular routing problem sender and receiver may be on the same networ sender may get a binding update message from the home agent sender can then create its own tunnel to mobile agent 7 Security 7 Ad Hoc networks all nodes are mobile How to Make Routing Scale I Flat versus Hierarchical Addresses I Inef cient use oinerarchical Address Space 255 0 78 efficient 7 class B With 256 hosts 25665535 0 39 efficient Still Too Many Networks 7 routing tables do not scale 7 route propagation protocols do not scale I Need to reduce the number oftable entries and routes stored l 8 5 Internet Structure Recent Past Internet Structure Today A mm m pm Backbone SENlEE pvwldev P2211719 Small cumuvatlun Subnetting Add another level to addressrouting hierarchy mbrtet Subnet masrs de ne variable partition ofhost part Subnets visible only within site Class E address 111111111111111111111111 uuuuuuuu Subnet mask 255 255 255 El Subnetted address Subnetting I All 1 s in the network and subnet part ofthe IP address I All 0 s in the host part I Subnet masks do not need to align on a byte boundary nor do ones need to be contiguous Subnetting Routing outside the subnet e routers Just need to know how to forward packets to the correct network overall 7 From theredo Subnet delivery 7 A oitwise AND ofthe mask and the IP address will reveal the Subnet host who wants to send a message will rst perform a bitwise AND between its subnet mask and the destination address I Ifthe result is the subnet ofthe sender it knows the s e can be delivered directly otherwise it will forward it to the default router Subnet Example suhnsl mask 255 255 255128 suhnsl quotmost 128 an at 8 Subnetmask 255255255128 Suhnetnumhev 128 an 3t128 5 Next Hup Subnet mask 255 255 255 8 Subnmmg imam 128 95 34 8 255 255 255128 interface 8 128 95 34128 interface l 128 95 33 8 Forwarding Algorithm Supernettmg n destination I address for each try subnetnum SubnetMask ext op I Asslgnblock ofcontlguous network numbers to D1 SubnetMask s n nearby networks 1f D1 sub 5 quotserene I Called CIDR Classless InterDomain Routing deliver dstsgrsm directly to n Represent blocks with Mingle Pair else deliver datagzam to ext op firstnetworkaddress count Use adefault router irnothing matches I Restrict block sizes to powers of 2 Not necessary for all is in subnet mask to be contiguous Use a bit mask CIDR mask to identify block Size Can put mu1tip1e subnets on one physical network Subnets not visible from the rest ofthe Internet 39 A11 routers must undersmd CIDR addfessmg Use 1ongest match ru1e CIDR Route Propagation I Know a smarter router r h st 1m 1 l t CIDP a11ows grouping ofroutes under asing1e entry in a 7 10 Crou izsiiaovfgtfmm routing table 7 site rou ers now co router Blocks ofcontiguous class c addresses can be handed out 7 comoutaslmow everything Ex 192 416 192 4 31 39 Autonomous System AS s correspon sto an administratiyedomain The top 20 brtswi11be the same so itbasically is anetwork examples Unwemtyy company backbmnetwoxk number of20 bits Note blocks must share a common agggneam As a igbgnumber pre x and be assigned in powers of 2 Twolevel route propagation hierarchy Use ltnumberorbitsinprerix valueaddressgt pairs for manor gatewayprotocol each AS selects ms ovmgt classless addressin s exterior gateway protocol Intemetswide standard g Used by Internet Service providers Popular Interior Gateway Protocols EGP Exterior Gateway Protocol I Overview 39 RIP39 Route Infommon Fromm e designed for treestructured lntemet d V 1 P d f rXNS e concerned with reachabzlzty not optima1 routes e distributed with Unix I Protocol messages e distancevector algorithm b d h e neighbor acquisition one router requeststhat another 1 quot P39 quot39 be its peer peers exchangereachabi1ity information 39 OSPFI Open Sho est Path FIISt e neighborreachabi1ity one router periodically tests if e recent Intemet standard the another is sti11reachab1e exchange HELLOACK 7 uses link state algorithm messages uses akoutof n rule suppons loadbaiming e routing updates peers periodically exchange their routing tabies distanceVector 7 supports authentication BGP4 Border Gateway Protocol I AS Types 7 stub AS has a single connection to one other AS carries local traf c only 39 med AS has connections to more than one AS refuses to carry transittralric 7 transit AS has connections to more than one AS carries both transit and local traf c I Each AS has 7 one or more border routers 7 one BGP speaker that advertises local networks other reachable networks transltAS only gives path information BGP Example Speaker for ASZ advertises reachability to P and Q 7 network 128 96192 41531924 32 and 192 4 3 can be reached directly from ASZ izsco 1924153 iionri PlavldelA A57 costmiu iozm A55 19243 ammunition A51 iozizao Revlanal vimmu a A53 192454 iozezi I Speaker for backbone adverti s r ne se orks 128 9o19241531924 32 and 19243 canbereached along the path As1As2 Speaker can cancel previously advertised paths 1P Ver51on 6 I 1991 IETF began looking for solutions to alleviate the shortage of IP addresses I Also added other functions 7 Support for real tirne services 7 Securi suppo r Autocon guration support 7 En ance routing and support formobilehosts I Many of these have since been integrated into PV4 1P Version 6 Classless addresses but space is subdivided into uses I 128 bits for address 7 001 fortradltlonal classABC addresses ernes XXXXXXXX Each X stands for a 16 bit piece ofthe address 1P Version 6 atu 2 Fe res e 1 87b addresses classless e ulti e realrtlmesa39vlce r authentication and secunty 7 en 7 read fragmentation 7 protocol extensions Header e 407byte basequot header 7 extension headers flxed order mostly flxed length authentication and security er opaons Chapter 6 Congestion Control Outline Congestion control ac Resource allocation Congestion control Network Layer 7 Queuing Tran ort La er Resource Reservation ac QoS Resources I Bandwidth ofthe links I Buffer space Queues on the switches and routers e If Queues are full packets are dropped 7 pracket drops occur frequently the network is congested I Congestion Control effort ofthe network nodes to prevent or respond to overloaded conditions Resources I Resource allocation is complex why I Because resource issues involve multiple levels of the protocol stack and are therefore implemented in multiple places 7 e g transport andnetwork layers Resource Allocation I Three problems assuming a packet switched network 7 A source may have plenty ofbandwidth to send a ket on an imme iate outgoing link but somewhere in the process of delivery the packet may encounter a link that is used by many traf c sources 7 Input packets on all incoming lines may be destined for the same output line causing delay or loss 7 Losses and delays cause retransmissions which further increases congestion Increasing buffer sizes may make the problem worsel Congestion The behavior ofone router can affect the performance ofanother Congestion I Bottleneck the congested node I Upgrading the routers in one area of the network may just move the bottleneck somewhere else Congestion ofthis type isn t a problem on shared accessbroadcast networks such as Etherne Why 7 The nodes can sense the traf c directly and choose when to send or not Issues Two approaches 7 prerallocate resources so as to avoid congestion 7 control congestion irand when is occu Two points of implementat39on ts at the edges ofthe network transport protocol etw ork queuing discipline Underlying service model estreffort assume for now 7 multiple qnoltres afservice later Framework Flows can be implicitly deiined and explicitly estab lished e Implicit implies that the router watches soureddestination pairs and discovers ows 7 Explicit means a ow setrup messa r This does not mean end to aad reliable ordered delivery like we have in Connectionronented systems s sent The service model we will concentrate on first is best effort Taxo omy r routasrcentric y ersus hostrcen tric r reservationrbased vasus feedbackrbased r windowrbased versus raterbased Framework I Connectionless flows 7 Connectionoriented transport la er 7 sequence ofpackets sent between sourcedestination pair 7 maintain Su state at the routers Resource allocation decisions So state does n t eed to be created or removed by signaling 39 It is a m iddle ground betweaa COnneCLlOnrOnenLed and COnneCLiOnrleSS Taxonomy I Routercentric versus host centric who will address the problem 7 the end hosts or the intermediate routers r Router centric means the routers will choose which packets to drop 7 hostcentric means the hosts will observe network conditions and adjust transmittal acc rdingly Taxonomy I Reservationbased versus feedback based 7 re ervation based ahost might request so resources for a ow The router will either accept or reject the request This implies a routarrcentric resource allocation mechanism 7 Feedback means the host starts sending an 39 implicitly adjusts it rate du t al behavior it can observe or adjusts by an explicit command from the router A feedbackrbased system can be either a router orhost cmtnc mechanism Taxonomy Window based Versus rawrb ased Window based is similar to that used in TCP ow control 7 An adv rtised window can be used to reserve buffer space This is what was done in X 25 work Ratebased e We can also control a senders behavior by using various send rates e several experimental applications which will adjust rate ofvideo and audiobased on currentnetw rk conditions its should mean less congestion This is done with compression routines Problem 1 pg 516 I It is possible to define flows on either a hostto host basis or on a process to process basis I Discuss the implications of each approach to application programs Problem 1 pg 516 From the application s perspective it is better to de ne ows as processtoprocess Ifa ow is hosttohost then an application running e may be penalized by having its packets dropped if another application is heavily using w However it is much easier to keep track ofhosttohost flows routers need only look at the 11 addresses to identify he ow on amultiuser mac in If ows are processtoprocess i e endtoend routers must also extract the TCP or UDP ports that ident39 y the endpoints In effect routers have to do the sarne demultiplexing that is one on the receiver to match messages with their ows 4 Problem 1 pg 516 I Ipv6 includes a owlabel eld If the host put a pseudorandom hash number into this eld to identify the ow what would it be based on for each of the two above approaches Problem 1 pg 516 Hosttohost then FlowLabel would be a hash of the hostspeci c information that is the 2 addresses If ows are processtoprocess then the port numbers should be included in the hash input Congestion Control Evaluation I Is the technique good or bad 7 We want ourmethod to be effective and fair 7 We want 1ots ofthroughput with 1itt1e delay 7 sirnp1e approach send as many packets as possible onto the network so that link utilization reaches 100 15 this good7 hint remember router queues Power of the Network Power throughput delay Limitations This assumes that queues are in nite in length they aren t in reality It is an equation for only one ow so it is dif th to apply it when multiple competing connections are present The objective is to maximize the mtio which is a function of the network load Load is set by the resource allocation method Evaluation Fairness I The power curve I Power of the network ratio of throughput to delay Whalisl air 7 Equal 7 This means irseveral ows share a particular link they should receive equal portions othe avallablebandwldth Raj Jain proposes afaimess metric Fxlx2x3 xn znglxiy nzngpri2 Throughputdelay Where xlx2 is a set of ow throughputs measured in OiE a Ea Luau bitssecond The metric will be a number between 0 Cungesuun Cullapse and 1 9 2D Queuing Disciplines Example FirstInFirstOutFFO discriminate between traffic sources rWh bff39full kt dr dFIFO t39l Competing ows that have rates of 100KB 60KB dmen er 5 p e s are Oppe W m 110KB 95KB and lSOKBs 7 Scheduling Discipline and adrop polic e simplest and used the most on Internet routers 100 6011095150251002 60211029521502 e Congestion control is left to source and destination 265225 286125 gain E 926 g I Is this good or bad a Free butters oueuea packets J 63 semi 21 22 h amp Fair Queuing Fair Queuing FQ e explicitly segregates traffic based on ows e a s are processe in a round robin manner from each ow Priority queuing A router may have multiple FIFO 7 Again this needs to be used along With some en queues d sysmm cungesti n control method or else packets Will be dropped when the ueues ge full 7 Use the 12 T08 field to mark each packetwlth a pnonty L The router will transmit packets out ofthe highest priority queue rst 7 Problem starvation Flam1 Priority queuing is used in the Internet to protect routing up date p ckets that are necessary to stabilize routing tables after a ram topology change Priority Queuing e ensures o a w captures more than its share ofcapaclty 7 Variation weighted fair queuing W39FQ mm mmquot Falr Queulng Fair Queuing F Issue packets may not all be the same size one ow may still grab up most ofthe bandwidth 7 is needed is bltsbysblt round robin servicing ofthe queue or ow 7 FQ simulates this by discovering when a packetwould finish transmitting ifit were Smtbltsbyrblt round robin It then uses this finishing time to order the packets for transmission Raund outquot FQ Algorithm Suppose clock ticks each time abit is transmitted Let P denote the length ofpacketz I Let S denote the time when start to transmit packetz Let F denote the time when finish transmitting packetz F s P When does router start transmitting packet 17 e Depends on whetherpacket i arrived before or after the router finished transmitting packet il Ifbefore thm the first bit ofpacket l should be transmitted immediately afterthe lastbit ofpacket lrl It mightbe howeverthat i r l was done transmitting a long time before i arrived the queue was empty for awhlle Ai is the time that packet i arrives at the mute si maxFi1Ai so Fi maxFi1Ai Pi 26 FQ Algorithm Now what ifthere is more than one flow we need to time things so that the clock advances after 1 bit has been sent from all ows so we can t just check time when apacket arrives The clock must advance by one u39ck when n bits are transmi ed if there are n ows Calculate Fi s using the formula Fi maxFi1Ai Pi for each ofthe ows Treat all the FPS as timestamps The one with the lowest value will transmit first FQ Algorithm cont I A shorter packet that arrives later than a longer packet on some other ow may get scheduled rst however a ner 39 acket cannot reem t tt cketthatis currentl bein transml ed I Example r law t r law 2 Fluwt Flow 2 Output ammg tvansmmnu output r g r tu r tu F 5 r 2 a n 22 FQ Benefits 1 the link is never idle as long as there is at least on packet in the queue 2 Ifthe link is fully loaded and there are n ows sending data no link can use more than lnth ofthe 39dt 3 Any bandwidth not used by a ow is automatically available for other ows FQ I A variation is Weighted fair queuing W FQ e a weight is assigned to each ow 7 the weight specifies how many bits to transmit each time the router services that queue e Ifwe were going to do this it wouldmake sense to assign weights based on some reservation scheme Weigats could also be assigned differently to various T08 of classes oftraffic FQ Example I Assume Ai is 0 Fi Fi1 Pi I Find Fi s and send in increasing order of Fi Multimedia Requirements Session Control Audio and Video I audio and video data use variable rate coding to represent data I sample mte dictates the playback mte I buffer received data RTP multimedia applications I Originated from MB ONE applications I A genemlpuipose protocol designed to support RTP I Provides common endtoend functions to a number of applications I RTP carries application speci c data 7 VIC video I runs on top of a transport protocol typically UDP V31 39 audm I more general that the previous application layer protocols 3 4 Elh d 7 en Apphcatlons u JTengPrince I m I W D Desklnp nnen Lab 390 Aquot ry Cnlem I Categories 7 Streaming RealAudio e Conferencing 7 user interaction AK nrnnuvunnz Menn mun Qu Chem 9 Figure 2 RTP UDP IP Subnet Chaf zr 9 Figure 9 RTP Requirements Protocol must allow similar applications to interoperate I Need to establish a coding scheme 7 Bandwidth 7 Computational cost RTP Requirements I Timing mechanism 7 Relationship among received data 7 Synchronization e Playback point RTP Requirements I Packet Loss 7 what to do 7 Playback last packet e Reconstruct the packet with interpolation 7 Reduce encoding rate RTP Requirements Congestion 7 what to do 7 UDP doesn t have ow control 7 Use loss rate adapt Framing Which packets correspond to a frame 7 Frames help identify talkspurts 7 Use silence periods for playback adjustment Sender identi cation RTP Requirements I Ef cient bandwidth utilization I Audio packets are small I Header ofthe RTP packet can t be too large RTP I Developed by IETF With control protocol RTCP I RTP used to send data I RTCP used to monitor transmission I Use consecutive transport layer ports for RTP and RTCP 7 Example port 6000 and 6001 RTP I A general protocol I Profiles provides a range of information for a particular application class I Formats explains hoW the data is to be interpreted for that class RTP I A general protocol I Design called Application Level Framing ALF Which Was de ned in 1990 by Clark and Tennenhouse I Idea leave most protocol details to the pro le and format so that they can be tailored to the particular application Contnoutlng source CSRC ldentlflers Extenslon header RTP payload RTP Header chipera Figure in Header I 1st 12 bytes mandatory I Optional header extensions I RTP data 7 format determined by application I Note header only contains data that all types of applications Will need speci cs are in the data portion Header Version identi er value is 2 Padding bit indicates ifthe payload has been padded to t aparticular size requiremen 7 contains the number ofbytes in the payload to ipiore 7 note theheader data and padding length Will be carried in the length field ofthe UDP heads Extension bit X used to indicate the presence ofan extension header which would be necessary for a particular application 7 rarely used rt is more common to put this type ofdata in the payload portion ofthe packet Header I CC is a 4 bit eld that lists the number of contributing sources I M denotes the marker bit which can be used to indicate particular frames of interest talksmeS I 7 bit payload type indicates the type of multimedia data in the packet r This field can be used in an altemative way it can be used to indicate a change in encoding type 7 How this field and the M bit are used will be specified by the application profile Length as earned in UDP header UDP headerl RTP header l RTP payload l Padding Fan mom Fan eeuht hyies chapter 9 Figure ii Demultiplexing Header I The payload field is not used as a demultiplexing key to direct data to different applications I Sequence Number 7 detect missing and missordered packets e ifapacket is lost the application must handle it or not I This service is provided by the transport layer I Time stamp protocol 7 detect missing and missordered packets I Note two different types ofmedia streams using 7 timestamp represents when the first sample in the d RTP will use two different UDP ports Pack 7 The differences between timestamps are important Header Header I synchronization source SSRC is a 32 bit number that uniquely identi es a single source of the stream I contributing source CSRC is used only when a number of RTP streams go through a mixer r Mixers help reduce bandwidth 7 it can receive multiple streams say audio andmix them together and encode them as a single stream A random number is generated for each sender and this number becomes the SSRC I By not using the IP address RTP is independent 7 The me mequot beconies the synd mmzmoquot sourfe39 but also lists the contributing sources that were mixed from the lower layer protocol for that particular puket 7 Can also distinguish multiple sources from the same ode RTCP RTCP provides a control stream that does the following ee thi 39 1 Gives feedback on the performance ofthe application and the network 2 Provides a my to synchronize media streams from the same sender 3 Conveys the identity ofthe sender for display on auser interface RTCP RTCP Packet Types Sender reports enable active senders to report transmission and reception statistics Receiver reports used by receivers to indicate reception statistics Source descriptions carry the CNAMEs and fo other sender description ln Application specific control packew RTCP RTCP packets are sent via UDP Several can be sent together in one UDP packet Don t want too much control data Limit RTCP traf c to 5 of the RTP traf c Periodic reports are sent RTCP Sender and receiver report contain 7 timestamp with the actual time of day the report was generated 7 The RTP timestamp corresponding to the time the report was generated 7 Cumulative counts ofthe packets and bytes sent by this sender since the start ofthe transmission RTCP Also contain ablock of data per source with 39 Its SSRC The fraction ofdata packets thatwere lost since the lastreportwas sen Total number ofpackets lost from this source smcethe start of transmission Highest sequence numberreceiyed from the source Estimated interral39rlval Jitta for the source Last actual timestamp recelved yia RT C for this source Delay since last sender report recelved yia RTCP forthls source RTCP I Use all this to evaluate the condition of the network and estimate the receiver s quality of service Ifa large ofpackets are lost decrease encoding rate Loss rates of530 are common over the Internet 7 30 loss is intolerable by listeners Source Description source description packet SSRC ofthe sender and the sender s canonicalname O o o 3 O z a E m 3 E a E 392 a g o E E a rm 0 erate media streams that might need to be synchronized Will choose the same CNAME even though they may choose different SSRC values format is userhost identify media streams that come from the same sender Other items may include real name or email address of the user Used by the user interface ofthe application Session Control I Still need something to control the session and to allow users to nd out abouti 7 Advertise event 7 Advertise Port number 7 Advertise IP address Session Control I Standard format and protocol I IETF group Multiparty Multimedia Session Control Group I They have de ned four areas of session control Session Control I Session Description Protocol SDP I Session Announcement Protocol SAP I Session Initiation Protocol SIP I Simple Conference Control Protocol SCCP Session Control Use I To advertise a conference on the Mbone you could use SDP and SAP 7 need to infonn everyone as to what is going on and which multicast address to use I To make an Internet phone call to a certain user at a particular time you Would use SIP and SDP 7 Here you need to locate a receiver announce your desire to speak to them and negotiate an encoding H323 I H323 is a protocol for multimedia communication over packet networ s I Groups together several other protocols such as H245 for call control I This is the protocol used for Internet Telephony Conventional telephone network H 323 tevmmal chapter 9 Figure l2 H323 I H323 terminal a originates the call phone or PC I Gatekeepers a translate among address formats phone to IP address a control how many calls can be placed based on bandwidth available Gateways 7 Connect H 323 networks to other types ofnetworks like the PSTN 32 H245 I The control protocol allows negotiation ofthe properties ofthe call a encoding types a signal the UDP port number that will be used by RTP and RTCP for the media streams 7 Once this is established the call proceeds with only RTP an R CP carrying the relevant information Compression Overview I Encoding and Compression r Huffman codes I Lossless 7 data received data sent 7 used for executables text files numeric data I Lossy 7 data received does not data sent 7 used for images video audio Lossless Algorithms I Run Length Encoding RLE 7 example AAABBCDDDD encoding as 3A2B1C4D a good for scanned text 8to1 compression ratio a can increase size for data with variation e g some images Differential Pulse Code Modulation DPCM 7 example AAABBCDDDD encoding as A0001123333 a change reference symbol ifdelta becomes too large 7 works better than RLE for many digital images 1 5to1 DictionaryBased Methods I Build dictionary of common terms a variable length strings I Transmit index into dictionary for each term I LempelZiv L2 is the bestknown example Commonly achieve 2tol ration on text Variation of LZ used to compress GIF images 7 first reduce 24bit color to 8bit color a treat common sequence ofpixels as terms in dictionary 7 not uncommon to achieve 10to1 compression x3 Image Compresswn J39PEG Joint Photogaphlc Expert Group ISOITU Lossy Stillrlmage compression Threephase process JPEG cummesslun DOT e praeess in m bluck ehunks maerahlaek greyscale eaeh pixel is three values YU 7 DOT txansfurms si nal frum spaaal damanintr and equivalent 513131 in the sequeney domain ussrless 7 apply a quanuzanun tr the results lussy e RLErllke eneading lussrless Quantization and Encoding Quantization Table Encoding Battem MPEG I Motion Picture Expert Group I Lossy compression ofvideo I First approximation JPEG on each frame Also remove interframe redundancy MPEG cont cture cted picture 7 B frames bidirectionalpredictedpicture l El El Farmam Pvedmmn e Wrasse sham Bldlvedmna Pvedlchan Example sequence transmitted as I P B B I B B MPEG cont B and P frames 7 coordinate forthe macroblock in the frame 7 motion vector relative to previous reference frame B P e motion vector relative to subsequentreference frame B e delta for each pixel in the macro block Effectiveness e P and B frames get another 3 to 5x Problem 33 Suppose We Want returning RTCP reports from receivers to amount to no more than 5 ofthe outgoing primary RTP stream If each report is 84 bytes and the RTP traf c is 20KBps and there are 1000 recipienw how o en do individual receivers get to report What if there are 10000 recipienw Answer RTP frame 20KB 05 20000bytessec 1000bytessec 1000 recipients so each get 1 bytesecond The report is 84bytes so each receiver can send one report every 84 seconds Ifthere are 10000 recipients then each can send one packet per 840 seconds 84060 14 minutes Chapter 6b Congestion Control Outline Congestion control ac Resource allocation Congestion control Network Layer 7 Queuing Tran ort La er Resource Reservation ac QoS TCP Congestion Control Idea 7 assumes besteffort network FIFO or FQ routers 7 Send packets on to the network without reserving resources 7 React to events 7 ACKs pace transmission Selfcluckmg Challenge 7 detennining the available capacity in the rst place 7 adjusting to changes in the available capacity TCP Congestion Control I How can TCP detect congestion in the network 7 Use acknowledgements r If it does not receive an ACK for apacket in some amount oftime it can consider this aloss I But does that necessarily mean that there was congestion e No Why TCP Congestion Control There are three mechanisms used by TCP to handle congestion control additive increasemultiplicative decrease slow start fast retransmitfast recovery Additive Increase Multiplicative Decrease Use ACKs to nd clues regarding the state ofthe network Where can bottlenecks be 1 They can be at the receiver due to lack ofbuffer space the Advertised window eld should restrict the sender based on that value 2 The bottleneck can also be the network imell in which case the advertised window doesn t help at What we need is another window based on the network s capabilities CongestionWindow Additive Increase Multiplicative Decrease AIMD Objective adjust to changes in the available capacity New state variable per connection Congestionwindow r lirnits how much data source has in transit namin MI CongestionWindow Advertisedwindw Eff win Maxmn Las tByteSent Las tsytehcked Idea 7 increase Congestionwindow when congestion goes down 7 decrease Congestionwindow when congestion goes up AIMD cont Question how does the source determine whether or not the network is congested I Answer atimeout occurs 7 lostpacket implies congestion AIMD cont Dulce irtation I Algorithm 7 increment Congestionwindow b one packet per RTT lmear Increase e divide Congestionwi ndow by two whenever imeout occurs mulnplzcatzvz decrease I In practice increment a little for each ACK Increment MSS MSS Congestionwindow Congestionwindow Increment AIMD cont Dulce irtation I TCP follows an additive increase procedure for increasing the number of packets sent This is a conservative approach I Whenever the source successfully sends a CongestionWindoW s Worth of packets or bytes meaning each has been ACKed it adds an equivalent of 1 packet to the CongestionWindoW the number of bytes to equal a packet AIMD cont Dulce stinaiion I Example increase Window if the CongestionWindoW stmts is 65K bytes and a timeout occurs indicating a dropped packet I the source Will set the congestionWindoW to onehalf is original size or 32K bytes I If another timeout occurs the size 39 r reduced Eventually Will fall to a minimum size or MSS AIMD cont I Trace sawtooth behavior AIMD Why do you suppose the window decreases so much more quickly than it grows 7 It was found that additive increasemultiplicative decrease was necessary to pro uce st e conditions 7 oscillations can occur ifwe adjust to quickly to transitory events AIMD Slow Start I TCP tries to match is speed to the network Why do you supp ose the window decreases so much capacity using 510W Stan more quickly than it grows I At connection setup the two TCP endpoinw may negotiate a 64K maximum window size T e a The trigger that iscansing the window to adjust then is somce couldjust Stm sending at 64KBPS but it 1ack ofACKs or timeouts doesn t Instead it sendsust 1 segment based on a chapter 5 timeouts are set based on afunction of th MTU average RTT and standard deviation in that average 3 39 RTl s are calculated once per RTT using a coarse I Only when that segment is acknowledged does it grained 500 ms clock send more 13 14 Slow Start Slow Start I Congestion window begins with a size of 1 Objective determine the available segment capacity in the rst I Each time a batch ofpackets is ACKed it doubles 39 Idea the size ofthe congestion win ow begin With CongestionWindw 1 packet I TCP continues to double the size of the window until it encounters loss at which time it moves to multiplicative decrease 7 double Congestionwindow each RTT increment by 1 packet for each ACK Slow Start cont I A sender will reach a point where it has sent as much as the advertised window allows Coarse grained timeout Blocks waiting for an ACK I Coarse grained timeout 7 connection goes dead ACK dues not 311ng because sender is blocked A cumulative ACK will open the window but the sender times out I Timeout occurs but there are no packets in transit before this happens I Source gets a single cumulative ACK that reopens the entire windo I Slow start is used to start sending again Slow Start I A er connection goes dead while waiting for a timeout you know more about connection then you did at connection setup 7 Current value ofCongestionWindow prior to last packet loss 7 target CongestionWindow 7 Store in congestionThreshhold variable 7 Congestionwindow starts at 1 again Slow Start cont Exponential growth but slowerthan all at once se 7 when rst starting connection 7 when connection goes dead waiting for timeout em 21 a 1 eout 7 so d bullet hash mark time packet transmitted vertical bar time when packet that ms retransmitted was originally sent Improvements to TCP I It was found that TCP timeouts o en allowed the connection to go dead waiting for the timer to expire too long of a timeout I Fast retransmit was added to solve this The idea is that some event will tn ger a retmnsmit ofa lost packet before the regular timeout mechanism not in place of Fast Retransmit I When a receiver receives a packet it always responds with an ACK even if it is the ACK for a previous packet some arrived out of order Duplicate ACKs such as these indicate to the sender that packew have arrived outof order I The sender will take note of this but will realize that the packet may just be late I It will wait until it sees three duplicate ACKs A er this it will retransmit the missing packet Fast Retransmit and Fast Recovery Problemcoarsegrai39nTCP 5 timeouts lead to idle periods Fast retransmit use duplicate ACK to trigger retransmission Original plus3 duplicates W am AEKZ Acw min AEKZ mine ABM Mimi Packetl AEKE Results Results Congestlon AVOldance TCP s strate 7 control congestion once it happens 7 repeatedly increase load in an effort to find the point at which congestion occurs and then back off Alternative strategy 7 predict when congestion is about to 7 reduce rate before p ckets start bein 7 call this happ en g discarded congestion avatdance instead of congestion control Two possibilities routerscentrlc DECb see Compare trace 6 11 to 613 In trace 6 131quot i ast asused Here we i h Ste tr TCPV the long periods in which the window stays at in 6quot ega I ast t and RED Gateways retran sm it w 5 6 11 andno packets are sent is eliminated F retransmit eliminates about half ofthe normal timeouts and allows for a 20 improvement in throughput 25 DECbit DECbit DECbit was designed to be used on Digital Network Add binary congestion bit to each packet header Architecmre DNA Router 7 when to adjust each router monitors its load and explicitly notifies the end 7 monitors average queue length over lastbusy dle cycle nodes when congestion is about to occ Noti cation takes the form ofa special bit called abinary congestion bit which is added to the header ofthe packet The destination host then copies this bit into the ACK that it sends back to the source The source then adjusts its sending rate to avoid congestion 7 set congestion bit lfavemge queue length gt1 7 attempts to balance throughout against delay End HOStS Random Early Detection RED Destination echoes bit back to source I Develo ed in earl 90 57 aln monitor ueue len th Source records how many packew resulted 111 set b1t p y ag q S Notification is implicit Ifless than 50 oflast W1ndow s Worth had b1t set 7 JuSl ran omly drop a packet TCP will timeout 7 increase Congestionwindow by 1 packet could make 6x10110th mammg 5 PackeL 0 7 Sender will adjust its congestion window If50 K or more oflast W1ndoW s Worth had b1t set Which packet will be dropped 7 decrease conges tionwindow by 0 875 times 7 E andom drop 7 ratherthan wait for the queue to become full drop each amvlng packet with s rap prababtllry whenever the queue length exceeds some drop level RED Details I Compute average queue length llngen 1 Weight II llvgnen Weight I SampleLen o ltWeight lt1 usually 0 002 SampleLen is queue length each time apacket amves MaXThreShold MlnThreShold Avgten RED Details cont Two queue length thresholds if llngen lt Min39rhreshold then nqu if Min39l hzeshold lt hvgnen lt Max39l hzeshold then calculate probability P drop arriving packet with probability P if ManThzeshold lt hvgnen then dr p arriving packet RED Details cont I Computing probability P Temp Maxi I hvgnen Min39l heshold Max39l hzeshold Min l hzeshold P TempEl count II Temp Count is the it of packets arrived when Qlength live is between the 2 threshholds I Drop Prob Tlity Curve Minnie Maxlmesh How did they know to use these values I Performance tests analysis and simulation I The type or characteristics of the network traffic affects all these values I Current work is being done to characterize Internet traf c and to evaluate optimal queue length so that RED can be deployed on the Internet Issues I Is it good to drop packets before you are forced to 7 ATM networks present an interesting case 7 Ifyou send AALS packets through a congested ATM switch and the switch is forced to drop one ofthe cells from the packet p aru39al packet discard then the ther cells should be dropped as well since they are useless to the host 7 These cells should be dropped even ifthere is enough buffer space This is called early packet discard Tuning RED Probability ofdropping aparticular ow s packets is roughly proportional to the share ofthe bandwidth that ow is currently getting MaxP is typically set to 0 02 meaning that when the average queue size is halfway between the two thresholds the suf ciently large to allow link utilization to be maintained at an acceptably high level Ditrerence between two thresholds should be larger than the typical increase in the calculate average queue length in one RTI39 setting MaxThre sho 1d to twice Mi nThres hol dis reasonable for traf c on today s Internet penalty Box for Offenders TCP Vegas I Source based congestion avoidance 7 now we look at another strategy ofcongestion avoidance In order for the source to get an ideathat congestion is eminent it will need some clues 7 What can it use RTT as this value increases the sender can assume queues are increasing TCP Vegas I Algorithm 1 7 Check the RTI every two round trips and see ifthe delay is greater than an average orthe minRTT and maxRTT seen so far 7 Ifit is the congestion window can be decreased by 13 TCP Vegas I Algorithm 2 7 Adjust the cunent window size based on changes in RTl and the window Again it can be adjusted every two roundtrips based on I CmrentWindoW 7 OldWindoW CurrentRTT 7 OldRTT I If the result is positive the source decreases the 39ndoW size again y 1 8 ifresult is negative or 0 increase by one packet size The Window Will oscillate around an optimal point TCP Vegas I Algorithm 3 each RTl increase window by one packet and compare throughput achieved to that when the window was smaller 7 1fthe difference is smaller than vs the throughput ofthat when only one packet was in transit at connection start up decrease the window by one pac e e Throughput is calculated by dividing the number of bytes outstanding on the network by the RTI TCP Vegas Algorithm 4 TCP Vegus e 1 p 3 e e m E 8 Earlier implementations ofTCP were distributed with BSD Unix T ad Jacobson s implementation ofslow start additive increasemultiplicative decrease 539 Reno added fast recovery another optimization method called header prediction was used when se ments arrive in order and all is running well and delayed ACKs ACK every other segment Newer versions ofTCP distributed with 4 4 BSD Unix added big win ows What this all means is that two implementations ofTCP may interoperate but may not perform well due to the difference in implemenuiu39on 4 TCP Vegas I So what is TCP Vegas 7 Algorithm looks at throughput rate changes in send rate 7 It compares measured throughput rate with expected throughput rate 7 tries to measure the amount of extra datathat the source hinks it should be able to send but that really should not have been transmitted due to available bandwidth constraints TCP Vegas Idea source watches for some sign that router s queue is bui1dmg up and congestion will happen too e g e RTT grows e sending rate attens g Congestion Wman sue Average sending rate at source Average queue sue atmuter 43 Algorithm Let BaseRTT be the minimum ofall measured RTTs common1y the RTT ofthe rst packet Ifnot over owing the connection then Expectkate CongestionwindowBasek39l Source calcu1ates sending rate ActualRate once per RTT Source compares ActualRate with ExpectRate Diff Expectedkate hctualxate if Diff lt a increase Congestionwindow linearly else if Diff gt d crease Congestionwindow linearly else leave Congestionwindow unchanged Algorithm we thresholds at and are defined as representing too little extra data and too much extra data in the network Therefore Diff lt a increase window linearly during next R39l39 Diff gt 5 decrease the window linearly during next R39l39 a lt diff lt a do nothing The bigger the difference between expected and actual throughput the more congestion reduce sending If values are close may be under utilizing the network Algorithm cont Parameters gg mm c 1 packet jg r 53packets g3 m sewa Congesoon Wmdww Expected teal shaded S ceheMeentwathreshaids actual blackthrmlghput Even faster retransmit 7 keep rmeegrained timestamps for each packet Check for timeout on first duplicate ACK Internetworking Outline Best Effort Service Model Global Addressing Scheme Routing IP Internet Concatenation of Networks Network 4 pointtopoint Protocol Stack Example Assume lOMbps Ethernet that is 20 meters long Packet size is 1500 bytes How long will it take to send one packet Latency propagation transmit queue Propagation distancec Transmit sizebandwidth Example Latency 20m23X108ms 1500bytes 8bitsbyte 10Mbps Answer 12ms Example Given a channel with a two way latency of IOOms and a bandwidth of 45Mbps how much data can be in ight Latency bandwidth volume Example Latency bandwidth volume IOOms 45Mbps 560Kbytes Service Model Connectionless datagrambased Besteffort delivery unreliable service packets are lost packets are delivered out of order duplicate copies of a packet are delivered packets can be delayed for a long time 1P Packet format 0 4 s 16 19 31 Versionl HLenl TOS Length Ident Flags Offset TTL l Protocol Checksum SourceAddr DestinationAddr Options variable I V ble Data W Service Model Version 4 Hlen length of header in 32 bit words 20bytes Wo options TOS used when differentiated services are provided Length size of data header in bytes Max size 65535 TTL time to live Protocol of upper layer UDP6 TCP17 Checksum adds up header in 16bit words using 1 s complement then take 1 s complement of result Source address Destination address Options not used Pad for even byte boundary 0 4 8 16 19 31 Versionl HLenl TOS Length ldent Flags Offset TTL I Protocol Checksum SourceAddr DestinationAddr Options variable Data WNW l Pad variable Fragmentation and Reassembly Each network has some MTU Strategy fragment when necessary MTU lt Datagram try to avoid fragmentation at source host refragmentation is possible fragments are selfcontained datagrams use CSPDU not cells for ATM delay reassembly until destination host do not recover from lost fragments H1 Example R1 R2 R3 1420 bytes total Start of header dent x I I IoI Of fset0 Rest of header 1400 data bytes R2 1 Start of header dent x I I I1IOtfset0 Rest of header 512 data bytes IETH IIPI 1400 MTU ETH 1500bytes IFDDIIIPI1400I MTU FDDI4500 Start of header dent x I I I1 I Offset512 Rest of header 512 data bytes Start of header dent x I I0 IOf fset 1024 Rest of header 376 data bytes MTU PPP532bytes 10 Global Addresses Properties globally unique hierarchical network host Dot Notation 10324 128963381 192126977 24 A 0 Networkl 14 Host 16 1o Network Host c 11o Network I Host Datagram Forwarding Strategy every datagram contains destination s address if directly connected to destination network then forward to host if not directly connected to destination network then forward to some router forwarding table maps network number into next hop each host has a default router each router maintains a forwarding table Example Network Number Next Hop 1 R3 2 R1 3 interface 1 4 interface 0 Address Translation Map IP addresses into physical addresses destination host next hop router Techniques encode physical address in host part of IP address won t work for Ethernet addresses tablebased Overview Routing Forwarding vs Routing forwarding to select an output port based on destination address and routing table routing process by which routing table is built Table 44 Routing Table Network Number Next Hop 10 1716924510 Forwarding Table Network Number Interface Next Hop 10 ifO 802BC4B12 Forwarding Algorithm D destination IP address for each entry SubnetNum SubnetMask NextHop D1 SubnetMask amp D if D1 SubnetNum if NextHop is an interface deliver datagram directly to D else deliver datagram to NextHop Use a default router if nothing matches Not necessary for all ls in subnet mask to be contiguous Can put multiple subnets on one physical network Subnets not Visible from the rest of the Internet Overview Routing Network as a Graph Problem Find lowest cost path between two nodes Factors static topology dynamic load Adaptive amp Static algorithms for routing Distance Vector Each node maintains a set of triples Destination Cost NextHop Exchange updates to directly connected neighbors periodically on the order of several seconds Whenever table changes called triggered update Each update is a list of pairs Destination Cost Update local table if receive a better route smaller cost came from nexthop Refresh existing routes delete if they time out Original algorithm used on ARPANET called RIP Example Initial Routing table for Node A Destination Cost NextHop A 0 A B 1 B C 1 C D X E 1 E F 1 F G X Example Finding 3 Routing table for Node A Destination Cost NextHop A 0 mmm00wgt CD TJD39JUOW Nt t Nww 20 Example Final Routing table for Node A Destination Cost NextHop A CD TJD39JUOW 0 Ni HNHi mmmoowgt 21 39EX 39EX Routing Loops ample 1 F detects that link to G has failed F sets distance to G to in nity and sends update t o A A sets distance to G to in nity since it uses F to reach G A receives periodic update from C with 2hop path to G A sets distance to G to 3 and sends update to F F decides it can reach G in 4 hops via A ample 2 link from A to E fails A advertises distance of in nity to E B and C advertise a distance of 2 to E B decides it can reach E in 3 hops advertises this to A A decides it can read E in 4 hops advertises this to C C decides that it can reach E in 5 hops 22 LoopBreaking Heuristics Set in nity to a number that represents the maX number of hops across the network EX 16 Split horizon don t send routes for a node learned from a neighbor back to that particular neighbor Split horizon with poison reverse do send route back to neighbor but also send info stating the neighbor should not go through you to get to that particular node 23 Example network running RIP 24 16 31 Command Version Must be zero Family of net 1 Address of net 1 Address of net 1 Distance to net 1 Family of net 2 Address of net 2 Address of net 2 Distance to net 2 RIP packet format 25 Link State Strategy send to all nodes not just neighbors information about directly connected links not entire routing table Link State Packet LSP id of the node that created the LSP cost of link to each directly connected neighbor sequence number SEQNO timetolive TTL for this packet 26 Link State cont Reliable ooding store most recent LSP from each node forward LSP to all nodes but one that sent it generate new LSP periodically increment SEQNO start SEQNO at 0 when reboot decrement TTL of each stored LSP discard when TTLO 27 mm Algorithm Discover neighbors and learn their addresses Measure the delay or cost to each neighbor Construct a packet that summarizes this information id of node List of neighbors Sequence TTL Send packet to 3 other routers Compute shortest path to each router 29 Route Calculation Dijkstra s shortest path algorithm Let N denotes set of nodes in the graph I 1 j denotes nonnegative cost weight for edge 1 j s denotes this node M denotes the set of nodes incorporated so far Cn denotes cost of the path from s to node n M s for each n in N s Cn ls 11 while N M M M union W such that CW is the minimum for all W in N M for each n in N M Cn MINCn C W 1W n 30 Fig 418 Link state routing example 31 LINK STATE ROUTING shortest path 1 Initialize con rmed list with source entry DO 2 This node is then called Next choose its LSP 3 For each neighbor of Next calculate the cost to reach this neighbor as the sum of the source node s cost next and from next to the neighbor DB 01 1 nextHop B If the neighbor is not con rmed nor on the tentative list then add neighbor cost nextHop to the tentative list where next hop is the direction the source must go to get to next If neighbor is currenth on the tentative list and the cost is less than the currently listed cost replace the current entry with the lower cost entry 4 If the tentative list is empty stop otherwise pick the entry on tentative with the lowest cost and move to the con rmed list and return to step 2 32 Analysis Bene ts Link State routing stabilizes quickly doesn t generate too much traf c and responds to topology changes Disadvantages Amount of info stored at each node can be large 33 OSPF Open Shortest Path First Link State Algorithm Authenticates routing messages Adds additional hierarchy can partition domains into areas A router will just need to know how to get to a particular area Essentially provides info on how to reach other networks Multiple routes to the same place can be assigned the same cost Load balancing 34 8 16 31 Version Type I Message length SourceAddr Areald Checksum I Authentication type Authentication Fig 419 OSPF header format 35 LS Age Options Type1 Link state ID Advertising router LS sequence number LS checksum Length 0 Flags 0 Number of links Link ID Link data Link type NumTOS Metric Optional TOS information More links Fig 420 OSPF linkstate advertisement LSA s Sent on a timed basis or when an event occurs Nodes periodically send out hello packets so link failures can be detected Nodes will know when they have an LSA from all other active nodes because each LSA will have info about other nodes As each is added to the table nodes without full paths will be obvious therefore the node knows to wait for more LSA s to complete the table 37 Metrics Original ARPANET metric measures number of packets queued on each link took neither latency or bandwidth into consideration New ARPANET metric stamp each incoming packet with its arrival time AT record departure time DT when linklevel ACK arrives compute Delay DT AT Transmit Latency if timeout reset DT to departure time for retransmission link cost average delay over some time period Fine Tuning to eliminate oscillations compressed dynamic range replaced Delay with link utilization 38 225 E 96Kbps satellite link C 140 g 96Kbps terrestrial link g 56Kbps satellite link g 56Kbps terrestrial link g 90 E 75 E 60 Z 30 l 25 50 75 100 Utilization 39 Input utilization link speed link type Results D o A highly loaded link never shows a cost of more than 3 times its idle link cost D o The most expensive link is only 7 times the cost of the least expensive D o A highspeed satellite link is better than a low speed terrestrial link D 0 Cost is a function of link utilization only at moderate to high loads 40 Text Ch 4 6 What is the maximum bandwidth at which an IP host can send 57 6 byte packets without having the Ident eld wrap around within 60 seconds Suppose IPs maX segment lifetime is 60 seconds delayed packets can arrive up to 60 seconds later but no later than that What might happen if this bandwidth were exceeded 41 Answer The Ident eld is 16 bits so we can send 576 216 bytes per 60 seconds or about SMbps If we send more than this then fragments of one packet could conceivably have the same Ident value as fragments of another packet 42 Introduction Outline Network Architecture Networks Statistical Multiplexing Performance Metrics ISO Architecture End host End host Application One or more nodes within the network Internet Architecture De ned by Internet Engineering Task Force IETF Hourglass Design Application vs Application Protocol FTP HTTP lFTPllHTTPll NV TFTPI Layering Use abstractions to hide complexity Abstraction naturally lead to layering Alternative abstractions at each layer Application programs Requestreply Message stream channel channel Hosttohost connectivity Hardware Protocols Building blocks of a network architecture Each protocol object has two different interfaces service interface operations on this protocol peeriopeer interface messages exchanged with peer Term protocol is overloaded specification of peertopeer interface module that implements this interface Interfaces Host 1 Host 2 Highlevel Sequotquot e Highlevel object 39quotterface object M V V Protocol 7 Protocol Peertopeer interface Protocol Machinery Protocol Graph most peertopeer communication is indirect peertopeer is direct only at hardware level Host 1 Video appllcatlo Digital library appllcatlo File appllcatlo Machinery cont 0 Multiplexing and Demultiplexing demux key Encapsulation headerbody Building Blocks Nodes PC specialpurpose hardware hosts switches Links coax cable Optical ber B D Wee pointtOpoint multiple access Switched Networks A network can be de ned recursively as two or more nodes two or more networks connected by a link or connected by two or more nodes Strategies for Network Design Circuit switching carry bit streams original telephone network Packet switching storeandforward messages Internet Network Services offered Connectionoriented connectionless reliable unreliable Addressing and Routing Address bytestring that identi es a node usually unique Routing process of forwarding messages to the destination node based on its address Types of addresses unicast nodespecific broadcast all nodes on the network multicast some subset of nodes on the network Multiplexing TimeDivision Multiplexing TDM FrequencyDivision Multiplexing FDM L1 gt I I 4 L2 gt gt i l Switch 1 Switch 2 2 iii 0 Ell L Statistical Multiplexing Ondemand timedivision Schedule link on a perpacket basis Packets from different sources interleaved on link Buffer packets that are contending for the link Buffer queue over ow is called congestion 81 ampamp InterProcess Communication Turn hosttohost connectivity into processtoproccss communication Host Host Host Chan Host Host What Goes Wrong in the Network Bitlevel errors electrical interference Packetlevel errors congestion Link and node failures Messages are delayed Messages are deliver outof order Third parties eavesdrop Performance Metrics Bandwidth throughput data transmitted per time unit link versus endtoend notation KB 210 bytes 0 Mbps 106 bits per second Latency delay time to send message from point A to point B oneway versus roundtrip time RTT components Latency Propagation Transmit Queue Propagation Distance c Transmit Size Bandwidth Bandwidth versus Latency Relative importance lbyte latency is more important 25MB bandwidth is more important In nite bandwidth RTT dominates Throughput TransferSize TransferTime TransferTime RTT 1Bandwidth x TransferSize Delay X Bandwidth Product Amount of data in ight or in the pipe Example IOOms x 45Mbps 560KB Delay Vquot Bandwidth J QOS I Packet switched networks advertise that they su ort m 39 39 39 Chapter 6 Quality of Service I Bandwidth has been increasing new coding Outline techniques allow for data to be compressed and Realtime Applications links are getting faster Integr 316d SerViceS I This is not always enough to provide good Quality Di emmmed services ofService at the receiver Realtime Applications I Require deliver on time assurances 7 must come from mssz the network The timeliness of delivery is important S m Mlcluphune aw ll Phone a delay gt 250ms is annoying to listeners M convene w D39A M speak 7 reduces the conversation to halfduplex timely data delivery also an issue in robotics QOS I Example application audio r 1 39 125 manufacturing and database updates that must be 5mm 6 vmce once every 5 d 7 each sample has a playback nme 53 mule 7 packets experience variable delay in network Hosts and routers play a part 7 add constant factor to playback time playbackpumt Playback Buffer Example Distribution of Delays BUDa 97 98 99 Packets Sequence number l TlmE Delay mlllseennns One Way delayuvel a speeme path on the lntemet m one day lam 2mm Taxonomy QOS I There are several approaches to quality of service support 7 Fine grained approaches which provide QoS for individual applications or ows 7 Coarse grained approaches which provide QoS to large classes or data or aggregated traf c QOS Fine grained approaches include integrated services a QoS architecture de ned byt e an associated with RSVP th r source reservation protocol Coarse grained approaches are o en called diiierentiated services which are undergoing standardization by the IETF at this moment ATM networks provide a full set of QoS services that are often categorized as fine grain however it is also possible to aggregate traf c between asingle vc so it is also use for coarse grained QoS as well Integrated Services I Service Classes 7 Guaranteed for delay intolerant data 7 controlledload for tolerant adaptive applications I Mechanisms 7 signaling protocol 7 admission control 7 policing 7 packet scheduling Flowspec I Rspec describes service requested from network 7 controlledloadnone 7 guaranteed delay target I Tspzc describes ow s traf c characteristics 7 Flows bandwidth needs 7 Dif cult to specif 7 Use a token bucket lter Flowspec I Tspzc describes ow s traf c characteristics 7 average bandwidth burstiness taken barretrilter r token rate 7 7 bucket depth 8 7 must have a token to send a byte 7 musthave 71 tokens to sendn bytes 7 start With no tokens 7 accumulate tokens at rate ofr per second 7 can accumulate no more than B tokens Token Bucket I An application starts With 0 tokens I To send a byte an application must have a token To send a packet of length n n tokens are needed I Tokens are accumulated at a rate of r per second but an application cannot accumulate more than B tokens I A burst ofbytes tokens can be sent as fast as an application Wanw over an interval but it can t send more than r bytes per second Fluvv E Flutva l Bandwidth M Eps FluWA HDWE AveRate leps Vela s Time seconds leps Dl byte DZ 1W Stores chapter o Figure 24 tokens Problem 43 The transmission schedule table 6 3 for a given ow lists for eac secon he number orpackets sent between that time and the following second The ow must stay within bounds ofatoken bucket lter What bucket depth does the ow need for a token rate of2 packets per second Tirnesec 0 l 2 3 4 5 Packetssent 5 5 l 0 6 l Problem 44 Suppose arouterhas accepted ows with the TSpecs shown in Table 6 4 where r is token rate and B is bucket depth All ows are int e same direction and the router can forward 1 packet every 1 second a What is the max delay apacket might face b What is the min number orpackets from the third ow that the router would send over 2 0 seconds assuming the 1 ow sent packets at its max rate uniform y Table 64 B104 1 PerRouter Mechanisms I Admission Control 7 decide ifanew ow can be supported 7 answer depends on service class 7 not the same as pullcmg I Packet Processing 7 classi cation associate each packet with the appropriate reservation scheduling manage queues so each packet receives the requested service RSVP I RSVP is a protocol designed for connectionless networks like the Internet I One ofits designer s goals Was to maintain the robustness of a connectionless network by using so state in the routers I This state does not need to be explicitly deleted When it is no longer needed I RSVP supports both unicast and multicast ows RSVP Instead ofthe senderoriented approach o en found in connectionoriented networ s RSVP requires that the receiver s keep track oftheir own needs ere may be only one receiver unicast or thousands of receivers multicast each receiver is required to periodically send refresh messages regarding its reservation requirements in order to keep soft state in place Requests can easily be changedusing this approach decrease or increase or remove Reservation Protocol Called signaling in ATM proposed Internet standard RSVP Consistent with robustness oftoday s connectionless model Uses so state refresh periodically Designed to support mu icas Receiveroriented Two messages PATH and RESV Source transmits PATH messages every 30 seconds Destination responds with RESV message Merge requirements in case ofmulticast Can specify number of speakers RSVP 1 First the receiver needs to know how much traf c the sender will probably send Tspec 2 Second it needs to know the path that the traf c will probably follow RSVP A PATH message is sent from the sender to the receiver With the Tspec As the message goes past each router on the Way to the receiver the routers gure out the reverse path that Will be used to send reservations from the receiver back to the sender Once the PATH message reaches the receiver the receiver can then send a reservation back up the tree in a RESV message RSVP I What happens if a link fails a The path will have to change a The routing protocol will find a new path 7 PATH messages ent every 30 seconds and possibly earlier ifarouter detects a change in its forwarding table RSVP How are things differentwhen we are multicasting 7 Now we have multiple receivers RESV messages will travel up the tree as before but they will probably eventually reach apoint in the multicast tree where some other receiver s reservation already been established a Ifthe previous reservation is adequate nothing needs to be done RSVP Example RSVP mulicast I RESV messages Will travel up the tree as before but they Will probably eventually reach a point in the multicast tree Where some other receiver s reservation has already been established I If the previous reservation is adequate nothing needs to be done merge resul s I If there are multiple senders the receiver s need to collect all the Tspecs from all senders and try to make a reservation that Will accommodate all of their traf c RSVP Multicast Packets must then be classi ed as belonging to apaiticular reservation 7 Examine the 5 key fields ofthe packet source amp destination address pmmcul number suurce amp destination part i Wth Ipv6 the flaw label eld can be used which is a shorler demultipleror Finally queues must be managed properly packet scheduling e Welghted fair queuing is the best forproviding a guaranteed endr torend delay bound 7 For controlled load traffic simpler schemes can be used could aggregate these into one flow and use W39FQ again Problem 45 I Suppose an RSVP router suddenly loses is reservation state but otherwise remains running a What Will happen to existing reserved ows if the router handles reserved and nonreserved ows via a single FIF queue b What Would happen to the ows if Weighted fair queuing Was used to segregate traf c RSVP versus ATM Q2931 I RSVP er generates reservation e QoS can change dynamically 7 receiver heterogeneiy e problemwith scalability ATM sen er generates connection request 7 hard state explicit delete 7 concurrent with route establishment e QoS is static for life ofconnection e uniform QoS to all receivers Differentiated Services Using differentiated services resources are allocated to a small number ofclasses oftraffic The easiest model uses two classes premium and secondary premium get special service and secondary get best effort service packets will then be required to identify their service class to the intermediary routers so they can be handled correctly Typically this requires abit to be set in the packet header Issues who sets the premium bitandwhen What does the router do with premium packets Differentiated Services Set bit at an administrative boundary This is o en an edge router ofapar cular ISP s network who can mark packew coming from a particular corporate interface based on the service the corporation has requested and paid fo Contracts are negotiated based on percentage of traf c that will be marked as premium I The usual model is to pay for some max I assume anything over that rate will be best effort Differentiated Services I How do the routers treat this traffic The IETF is busy standardizing router behaviors for marked packets 7 called p er7hop behaviors PHB 7 The TOS byte from the IP header is rede ned for this 7 6 bits are allocated to differentiated servi points DSCP whe per hop behavior ces code re each DSCP indicates aparticular Differentiated Services PHBs orinterest 7 Expedited forwarding EF these packets should be forwarded with minimal delay or loss The router can on y implanentthis ifthe airiyal rate ofthe packets is less than the rate at which the router can forward 7 This rate is achieved by configuring the edge routers to allow only a ataln max rate ofEF packets into the network e surn ofthe rates ofall EF packets rnustbe less than the bandwidth ofthe slowest llnk in the domain 7 To implement this we can give EF packets strict pnonty oruse wei ted queuing surprise Differentiated Services I Assured forwarding AF 7 This is an extension ofRED and is known as RED with in and out RIO 0r weighted RED 7 The idea is that we categorize packets as either in higher priority or out lower priority 7 We use two separate drop probability curves Differentiated Services Assuredforwarding RIO Idea support two classes ofpackets 7 premium 7 best7effort Mechanisrns m 7 packets marked ln and out 7 edge routers tag packets tn 7 core route RIO RED with 1n and Out Avvlgn Minaquot Mints13quot Mix RIO I Under low levels of congestion only out packets will be dropped I As congestion increases more out packets are dropped until nally we have to drop in packe I This method provides a high assurance but not a guarantee that a majority of the packets within the requested pro le will be delivered accordingly ts QOS in ATM I Five service level classes I Class A constant bit rate CBR this requires exact timing and xed guarantee bandwidth 7 t was designed for voice tra ic and is used in telephony 7 It came out before QoS services were available in P routers so it is commonly av 39 7 Implementation is with atoken bucket and delay specified value QOS in ATM Five service level classes I Class C variable bit rate nonrealtime VBR nrt e not widely implemented 7 Rnrt is similar to IP s controlled load service again token buckets are used but a hard delay value is not guaranteed QOS in ATM Five service level classes I Available bit rate ABR 7 designed to provide low cell loss rates inot widely supported due to its cornple ity e ABR requires that resource anagement RM cells are sent between the source and destination with the e can set its send rate to an appropriate level explicit feedback congestion smle oft QOS in ATM I Five service level classes I Class B variable bit ratereal time VBR RT Used for for video conferencing 7 not Widely implemented I VBRrt is like IP s guaranteed service agai token bucket is implemented and max delay is speci ed QOS in ATM Five service level classes Class D This class is or IP and LANrLAN trarnc unspeci ed bit rate UBR r simpler no protections for U39BR tratric a h e Usu lly s ut down lfcorlgestlon occurs rwldely implemented UBR ls ATMs best effort servlce Wth a blt o a dlfference ATM 1 Ce to speclfy a max rate at which it mlght send during initial signaling I e fthls is less than the link capacity this info can be used to decide whether a new vc will affect previously establishedVCs ABR ATM ABR requires that resource management RM cells are s ce and destination with the oal o E U 392 o o E o e source sends the cell which includes the rate at which it Wishes to sen Intermediary switches will decide ifenough resources are available 7 If so the RM cell ls passed wlthout modlflcatlon r Ifnot the requested rate is decreased before being passed along ABR ATM The destination will send the cell back to the source so it can learn what its send value should be RM cells are sent periodically so that the rate can adjust as eded based on network conditions Interestingly the rate at which the source can send is ecreased with tirne if it does not use its resources Use it or lose it ABR extends the notion ofsource and destination by allowing the definition ofvirmal sources and Virmal destinations This allows service to differ between various sections of ork the n etW 43 RM EHS RM EHS H1 51 52 53 1 H2 Suume vmual vmual Destinatlun uesunatmn suurce chapter 5 Figure 27 Chapter 5 End to End Protocols Outline Sliding windows Sockets pg 31 oftext Sliding Window Protocols I Form of pipelining e Continuously sendframes for atirne equal to the round trip transit time 7 Must choose the appropriate receive and send window izes 7 Need large windows when the bandwidth x delay product is large a lls the pipe At lssMbps 64KB rep max window size canbe sent in 3 3ms Use option fleld for a multiplierto makethe window bigger Sliding Window Protocols I How big should the window be 7 Sequence number is used to distinguish between segments a Only aMaxSeqNu Xofsegments may be outstanding at a time in order to distinguish between successive segments 7 Sequence numbers are 11123 X 7 Send window should be 12 x MaxSeqNu Go Back N I The receiver acknowledges each segment as it arrives I Ifa frame is lost all subsequent segment will be dro ed until the missing frame arrives successfully I Dropped segment are not acknowledged I Goal To pass segmenw to the application layer in order Selective Repeat I More ef cient use ofbandwidth than go back N I Buffer segmenw received out of order I Oldest unacknowledged segment will be retransmitted when the sender times out I Send a NAK if a damaged segment arrives e Speeds up time for retransrnission I Again pass segments up in order to application layer I Tradeoff bandwidth and buffer space Sockets I Two programs communicate through an application programming interface API I The socket interface distributed with Berkeley B SD Unix is so popular it has been ported to other operating systems I The API de nes ways for creating a socket sending and receiving and closing the socket Creating a Socket int socketint domain int type int protocol domain is either PLUer UNIX system internal protocols or PFilNET ARPA lntemet protocols or A r typ e SOCKisTREAM byte stream SOCKiDGRAM message oriented service UDP protocol type UNSPEC FilN39ET and SOCKisTREAM implies TCP 7 PFJNET and SOCKiDGRAM lmpllesUDP Creating a Socket sd socketAFINET SOCKSTREAM 0 r Creates aTCP socket I sd will be an integer identi er for referring to the socket sd socketAFINET SOCKDGRAM 0 r Creates aUDP socket Open The server will accept connections but doesn39t actually establish one 7 passive open Client makes an explicit connection Both use int bindint socket struct sockaddr address int ad r en BIND I Bind binds the newly created socket to the local participant the server or client I The address structure will contain the IP address ofthe server and the TCP port number for the service 7 when you call bind you can specify an address INADDRiANY which means you ll take any port 7 or you can specify the port you want 7 oh UNIX machines you can tuse any port below 1024 They are reserved for the operating system Server Passive open int listenint 5 int backlog The listen call tells the transport layer how many clienw can be gueued waiting for you to respond Additional client connections are refused s is the socket descriptor number backlog is the number of connections which can be queue Server Passive open I ns int acceptint socket struct sockaddr addr int addrlen I The accept call carries out the passive open I It is a blocking operation that does not return until a client has established a connection I When this happens it returns a new socket that corresponds to this newly established connection The address argument will contain the remote participant39s address Server Passive open ns int accepl nl socket struct sockaddr addr int addr en Socket is the socket descriptor The address ofthe client is returned when a connection is accepted the server creates a new socket to handle the request and returns the socket descriptor as ns Then the server can fork offanew process to handle this connection and go back and accept another connection on the original socket or do thern sequentially Client TCP Connect int connectint socket struct sockaddr address int addrlen socket is the socket descn39ptor Sockaddr is the service address sockaddr address ofthe server This causes TPDUs to be sent over the network to set up the connection This op rat m until aconnection is successfully established a er which data can be sent In practice the client only specifies the remote dr s 39 doesn39t care what address it uses for itself it lets the systern fill in that information the os chooses an unused address Send amp Receive Write socket buffer size Read socket buffer size Socket is socket descriptor Burrer is an array holding the data you want to send Other choices 7 int sendint socket char msg int msglen int flags 7 int recvint socket char buffer int burlen int flag 7 You won thave towony aboutthe flags UDP Sockets UDP messages do not require a connect I With UDP sockew you may use sendtoO and recvfromO instead of send and receive a sendto andrecvfrorn specify the address ofthe destination Closing the connection I int closeint fields End to End Protocols Outline c1gt connection establishment Sliding window Flow control Adaptive timeout EndtoEnd Protocols I Underlying besteffort network layer 7 drop messages 7 reorders messages 7 delivers duplicate copies ofa given message 7 1imits messages to some finite size 7 delivers messages a er an arbitrari1y1ong delay EndtoEnd Protocols I Common endtoend services 7 guaranteemessage delivery 7 deliver messages in the same order they are sent 7 deliver at most one copy ofeach message 7 support arbitranIy 1arge messages 7 support synchronization 7 allow the receiver to ow control the sender 7 support multiple app1ication processes on each host Transport Versus Data Link Potentially connects many different hosts 7 need explicit connection establishment and termination Potentially different RTT 7 need adaptive timeout mechanism Potentially long delay in network 7 need to be prepared for arrival ofvery o1d packets Potentially different capacity at destination 7 need to accommodate different node capacity Potentially different network capaci 7 need to be prepared for network congestion Simple Demultiplexor UDP I Unreliable and unordered datagram service I Adds multiplexing I No ow control Appiicaiinn Appiicaiinn Appiicaiinn pincsss pincsss pincsss Packets aYWE Simple Demultiplexor UDP Endpoints identi ed by ports 7 vewellrlmawn orts 7 see etcsevices on Unix unique to hosts Header format Length Hdr data Optional checksum e psuedo header UDP heada data Applications that use UDP Request Reply applications SNMIP Well Known Ports I Web server pelt 80 I DNS pelt 53 I Time pelt 37 39 See 1112HWWWidm n39nnlESianZstEmEHlSE l l39nllmhE for a complete list Psuedo Header o The protocol number I Source IP address I Destinatien IP address I Plus the UDP length eld I Using the pseudeheader allews veli catien that the message has been delivered between e correct twe endpeints The checksum is eptienal in ipv4 but will be mandatory in ipv6 Reliable TCP Overview Full duplex Connewonronmted Flowcontrolkeep sender BY e39Skeam from overrunning receiver 7 app wntestsytes Congestion control keep 7 TCP sends segments by sender from overrunmng network 7 son reads m Yvansmitsevments TCP I Cengestien centrel versus ew control 7 Congestion control limits how fast TCP sends data so that it doesn t overload the network 7 Flow control is so it doesn t overrun the receiver TCP I TCP is a sliding window protocol and gobackn or selective repeat depending on the situation 7 acknowledgements I TCP has an explicit connection phase where the two sides agree to send data to each other During this time the two sides will establish the sliding window size I TCP also has a connection teardown phase TCP Issues How long to wait for an ACK How far out of order can packets arrive What is the max segment lifetime What is the correct window size How do you know if the network is congested TCP Segment Format sicPuit n Flags AdveltlsedVWlduw Checksum Segment Format cont Each connection identi ed with 4tuple e Szchzt SchERddz Dszrozt Dstrnddz Sliding window ow control a acknowledgment Sequence um Advertisedwinow Data8equerlceNum Acknowledgment AdvenlsederldOW Flags 7 syn rm RESET PUSH use BCK Checksum e pseudo headerTCP headerdata TCP segment Sequence number is used to specify the rst byte ofthe packet e assigned by clock time Ack next byte expected Hdr length 4 byte words Flags control info between sender and receiver Window indicates the space the receiver has for new arriving packets Options indicated by header length field 7 Expandedwln ows r Selective repeat Connection Establishment and Termination Active participant client Passlve participant server State Transition Diagram Ylmeauta eltwa 5 sevment quotsome V ACK v cmsED Transition Diagram This diagram displays the semantics ofthe peertopeer interface and its service inte ace The syntax ofthese interfaces is given by the segment format and by some application programming interface 39 All connections start in Closed state The labels on the arcs are ofthe form eventaction There are 2 events which trigger state transition 7 a segment amves from the peer or a the local application process invokes an operation on TCP Sliding Window Revisited naaaaaa leanerquot uaaaaaa Sendin side g Receiving side T 135 LastByteSent T LastByteRead lt Lastsytesm extByteExpected astgytewznten a extByteExpected lt 1 23 t R d 1 7 bufferbytesbetween as Y e Cquot LastByteRckedand T ufferby sbetwee LastBytewzitten quotextByteReadand LastByteRcvd Flow Control Send buffer size MaxSendBuffer Receive buffer size MachvBuffer Receiving side a LastByteRcvd e LastByteRead lt Maxkchuffe extByteRead The window size will grow and shrink depending on how fast the application is consuming data Advenized window may shrink to 0 Flow Control Sending side 7 Las tByteSent e LastByteRcked lt hdvertisedwindow s Effectivewindow hdvertis edwindow e LastByteSent e LastByteRcked Effective window limits the amount the sender can send Also make sure the local bu er doesn t over ow the send buffer 7 Las tBytewzitten rLastByteRcked lt Maxsendsuffe y gt Maxsendezsuffe Always send ACK in response to arriving data segment Persist when Adverti sedwindow 0 Flow Control Always send ACK in response to an arriving data segment 7 Response will have the latest values for the ACK and Advertised Window Persist when Advertisedwindow 0 e Sender will send aprobe segment with 1 byte of datato trigger the update ofthe window size 7 Smart sender dumb receiver approach 7 keep receiver simple Protection Against Wrap Around 32bit SequenceNum dwidth T115Mbps 64hours Ethanet 10 Mbps 57 minutes T3 45 Mbps 1 minutes D1 100 Mbps 6 minutes STS73 155 Mbps 4 minutes STS7IZ 622 Mbps 55 seconds STS7Z4 1 2 Gbps 28 seconds Keeping the Pipe Full l6bitAdvertisedWindow for RTT of 100m Lh Delay x Bandwidth Product T1 1 5 Mbp 18KB Ethanet 1o Mops 122KB T3 45 Mbps 549KB mm 100 Mops STS7Z4 1 2 Gbps Keeping the Pipe Full Delay X Bandwidth of data should be sent I EXAMPLE 7 Satellite link has an RTT of540ms 7 Link has abandwidth ofl 5Mbps 7 Need to send 810000bitssec Keeping the Pipe Full I Delay X Bandwidth of data should be sent I EXAMPLE 7 RTl39 is 100 ms andthe link is 1 5Mbps r 15 x 105x 100 x103938l8 75KB I How many bits are needed for the sequence numbers 7 2 x18750bytes 37500bytes 7 2X 7 37 500 7 21416384 21532768 Triggering Transmission I Assuming no ow control send a segment when 7 When MSS is reached MTU 7 rep hdr n hdr 7 Push r initiated by sender to ush bu er r Timer elapses send even ifbuffer isn t full Silly Window Syndrome I Occurs when the receive window has been closed for awhile I An Ack arrives which opens the window a small amount 7 Should sender take advantage ofthis or wait for more s so it can send afull segment Silly Window Syndrome If sender takes advantage and sends immediately silly Window syndrome may occur Receive window never gets a chance to open completely 7 Only very small segrnents are sent 7 This is inefficient Silly Window Syndrome Syndrome Was discovered When early implementations of TCP Were studied I A er advertising a receive Window of zero receiver must Wait for space equal to an MSS before advertising that the Window is open again I Delayed ACKs cumulative may also help 7 Since it is inevitable that occasionally small segments will need to be sent Sender I So When should the sender send a segment I If there is data to send but the Window is less than the MSS how long should it Wait I Nagle s algorithm 7 Selfclocking use atimer at the sender r If data is inflight must wait for an ACK before sending e Ifno data in ight send whatever you have if window is open enou Nagle s Algorithm When the app1ication produces data to send Ifboth the available data and the window x MSS Send afull segrnent Else Ifthere is unACKed data in ight outrer the new data until an ACK arrives else send all the new data now Adaptive Retransmission Original Algorithm How do we know how 1ong to wait for an ACK I Measure Samplek39l39 for each segment ACK pair I Take difference between the two values Compute weighted average ofRTl39 7 Es ax EstR39l39I x Samplek39l39 r where a d 1 7 abetweenO 8 and 0 9 a betweaa o 1 and 02 I Set timeout based on Estk39l39 Timeout 2 X EstR Adaptive Retransmission Original Algorithm I Alpha helps smooth the estimated RTT e Iftoo big small changes won t be recorded 7 Iftoo small minor differences in RTT will cause to much change I Original algorithm problem 7 Doesn t take into account retransmission KarnPartridge Algorithm Sennev Receive Sennev SampleR W Sample TT Do not sample RTl when retransinitting Double timeout a er each retransmission e Exponential backoff e Congestion is causing retransrnissions Receive Jacobson Karels Algorithm previously didn t take variance ofsample tirnes into account ots ofvanance don t tle timeout so Closely to estimated RTT New Calculations for average RTT m Sample stRTT ES 11 Est a X 1H v u mun 7 Dev ne e where 5 is a factorbetween o andl Consider variance when setting timeout value Timeout tix EstRTT ox nev e wheren l and 4 0 es e algontnrn only as good as granularity of clock 500m on Unix e accurate timeout rnecnanisrn irnp ortant to congestion control later 2 RTT Latencies Message size UDP TCP Throughput M A a Message size KB chapter 5 Figure 24