Chapter 7 Packet-Switching Networks - UCCS

1 1 Chapter 7 Packet-Switching NetworksNetworksNetwork Services and Internal network OperationPacket network TopologyDatagrams and Virtual CircuitsRouting in packet NetworksgShortest Path RoutingATM NetworksTraffic ManagementNetwork Layer network Layer: the most complex layer Requires the coordinated actions of multiple Requires the coordinated actions of multiple, geographically distributed network elements (switches & routers) Must be able to deal with very large scales Billions of users (people & communicating devices) Biggest Challengesggg Addressing: where should information be directed to?

2 Routing: what path should be used to get information there?2t0t1 packet SwitchingNetworkTransfer of information as payload in data packets Transfer of information as payload in data packets Packets undergo random delays & possible loss Different applications impose differing requirements on the transfer of informationTransportTransportMessagesMes sagesSegmentsNetwork ServiceEnd system PhysicalData linklayerPhysicalData linklayerEnd systemNetworklayerNetworklayerPhysicalDa ta linklayerNetworklayerPhysicalData linklayerNetworklayerplayerTransportlaye rNetworkserviceNetworkservice PhysicallayerPhysicallayer PhysicallayerPhysicallayer network layer can

3 Offer a variety of services to transport layer Connection-oriented service or connectionless service Best-effort or delay/loss guarantees3 network Service vs. OperationNetwork Service ConnectionlessInternal network Operation Datagram Transfer Connection-Oriented Reliable and possibly constant bit rate transfer Connectionless IP Connection-Oriented Telephone connection ATMV arious combinations are possible Connection-oriented service over Connectionless operation Connectionless service over Connection-Oriented operation Context & requirements determine what makes senseNetwork Layer FunctionsWhat are essentials?

4 Routing: mechanisms for determining the set of Routing: mechanisms for determining the set of best paths for routing packets requires the collaboration of network elements Forwarding: transfer of packets from NE inputs to outputs Priority & Scheduling: determining order of Priority & Scheduling: determining order of packet transmission in each NEOptional: congestion control, segmentation & reassembly, security4 End-to-End packet network packet Networks very different than telephone Networks Individual packet streams are highly bursty Statistical multiplexing is used to concentrate streams User demand can undergo dramatic change Peer-to-peer applications stimulated huge growth in traffic volumesItt t thihl dt li d Internet structure highly decentralized Paths traversed by packets can go through many Networks controlled by different organizations No single entity responsible for end-to-end serviceAccess MultiplexingAccessMUXT opacketnetwork packet traffic from users multiplexed at

5 Access to network into aggregated streams DSL traffic multiplexed at DSL Access Mux Cable modem traffic multiplexed at Cable Modem Termination System5 Oversubscription Access Multiplexer N subscribers connected @ c bps to mux Each subscriber active r/c of time (ave. rate r) Mux has C=nc bps to network rrnc Mux has C=nc bps to network Oversubscription rate: N/n Find nso that at most 1% overflow probabilityFeasible oversubscription rate increases with sizeNr/ extremely lightly loaded users1000533310 very lightly loaded userNrNcrnc very lightly loaded lightly loaded lightly loaded lightly loaded lightly loaded usersWhat is the probability that k users transmit at the peak rate?

6 Home LANsWiFiHomeRouterTopacketnetworkEtherne tHow about network addressing? Home Router LAN Access using Ethernet or WiFi (IEEE ) Private IP addresses in Home ( ) using network Address Translation (NAT) Single global IP address from ISP issued using Dynamic Host Configuration Protocol (DHCP)6 Internet service providerConnecting to ISPI nterdomain levelAutonomousBorder routersBorder routersCampusNetworkIntradomain levelAutonomoussystem ordomainsssLANnetwork administeredby single organizationrunning same routing protocolKey Role of RoutingHow to get packet from here to there? Decentralized nature of Internet makes Decentralized nature of Internet makes routing a major challenge Interior gateway protocols (IGPs) are used to determine routes within a domain Exterior gateway protocols (EGPs)

7 Are used to determine routes across domains Routes must be consistent & produce stable flows Scalability required to accommodate growth Hierarchical structure of IP addresses essential to keeping size of routing tables manageable7 Chapter 7 Packet-Switching NetworksNetworksDatagrams and Virtual CircuitsUserPacket switching NetworkPacket switching network Transfers packetsPacketswitchNetworkTransmissionli neUser Transfers packets between users Transmission lines + packet switches (routers) Origin in message switchingswitchingTwo modes of operation: Connectionless Virtual Circuit8 Message switching invented for telegraphyMessage switching Entire messages multiplexed onto shared lines, stored & forwarded Headers for source & destination addresses Routing at message switchesMessageSourceMessageMessageMessa ge ConnectionlessSwitchesDestination Transmission delay vs.

8 Propagation delay Transmit a 1000B from LA to DC via a 1 Gbps network , signal speed 200 switching DelayttttDestination Switch 1 Switch 2 DelayMinimum delay = 3 + 3 TAdditional queueing delays possible at each link9 Long Messages vs. Packets1 Mbit messagesourcedestBER=p=10-6 BER=10-6 Approach 1: send 1 Mbit message Probability message arrives correctlyHow many bits need to be transmitted to deliver message? Approach 2: send 10 100-kbit packets Probability packet arrives correctly/)(11010106666 101010106655 On average it takes about 3 transmissions/hop Total # bits transmitted 6 Mbits On average it takes about transmissions/hop Total # bits transmitted Mbits3/1)101(11010106 )101( eePcPacket switching - Datagram Messages broken into smaller units (packets) Source & destination Source & destination addresses in packet header Connectionless, packets routed independently (datagram)

9 packet may arrive out of order Pipelining of packets acrossPacket 2 packet 1 packet 1 packet 2 Pipelining of packets across network can reduce delay, increase throughput Lower delay that message switching , suitable for interactive trafficPacket 2 packet 210 packet switching DelayAssume three packets corresponding to one message traverse same pathtttt312312321 DelayMinimum Delay = 3 + 5(T/3) (single path assumed)Additional queueing delays possible at each linkPacket pipelining enables message to arrive soonertt321 SourceSwitch 1 Delay for k- packet Mess. over L Hopsttt3123123 + 2(T/3) first bit receivedL + (L-1)Pfirst bit received3 hopsL hopsDestinationSwitch 1 Switch 2 ()3 + 3(T/3) first bit released3 + 5 (T/3) last bit releasedL + LPfirst bit releasedL + LP + (k-1)

10 P last bit releasedwhere T = k P11 DestinationaddressOutputportRouting Tables in Datagram Networks Route determined by table lookup1345127078561566lookup Routing decision involves finding next hop in route to given destination Routing table has an entry for each destination specifying output port that 245812leads to next hop Size of table becomes impractical for very large number of destinationsExample: Internet Routing Internet protocol uses datagram packet switching across Networks Networks are treated as data links Hosts have two-part IP address: network address + Host address Routers do table lookup on network address This reduces size of routing tableg In addition, network addresses are assigned so that they can also be aggregated Discussed as CIDR in Chapter 812 packet switching Virtual CircuitPacketPacketPacket Call set-up phase sets ups pointers in fixed path along network All packets for a connection follow the same pathVirtual circuitPacket All packets for a connection follow the same path Abbreviated header identifies connection on each link Packets queue for transmission Variable bit rates possible.