1EE 122: Switching and ForwardingKevin LaiSeptember 23, [email protected] 2Direct Link Network ReviewData link layer presents a single media (e.g., single wire) network modelProblem and solutions-Framing• character stuffing, byte counting, bit stuffing, clocked framing- Error detection• parity, checksum, CRC- Reliability• stop and go, sliding window- solutions also apply to similar problems in higher layers• problems can not be completely solved at data link layer• only implemented in data link layer as [email protected] 3Limitations of Direct Link Networksdistance- distance increases propagation delay- large propagation delay causes large coordination delay- e.g., Ethernet collision detection requires 2*prop_delaynumber of hosts- More hosts increases the probability of collisions- collisions decrease efficiency of linkbandwidth- bandwidth of link is shared among all connected nodessingle media type- different media (e.g., fiber, Ethernet, wireless) have different tradeoffs for performance, cost, [email protected] 4Direct Link Networks v.s. SwitchingDirect Link Network Switched NetworkSingle linkn linksSwitch [email protected] 5Definitionsswitch (aka bridge)- does switching- operates at data link layer- router also does switching, but at network layerswitching consists of- forwarding• read data from input links,• decide which output link to forward on, and❢examine packet header or incoming circuit, and❢look up in forwarding table• transmit it on one of the output links (unicast)- routing• how the switch/router builds up its forwarding [email protected] 6Propertiesspans larger physical area than direct link network (DLN)- can connect multiple switches togethersupports more hosts than DLN- hosts on separate links can transmit at same timehigher aggregate bandwidth than DLN- approaches (n/2)*b instead of b, n = number of switched links, b = bandwidth of one linksupports more than one media type- more expensive for bridge than [email protected] 7Bridge/Router ComparisonRouter interconnects different link layer protocols more easilyEthernet802.11bATMSONETEthernet802.11bATMSONETE-to-8E-to-AE-to-SO(n2) convertersn = different link typesEthernet802.11bATMSONETEthernet802.11bATMSONETSwitchRouterO(n) convertersE-to-IP IP-to-E8-to-IPS-to-IPA-to-IPIP-to-8IP-to-SIP-to-AE-to-Elaik@cs.berkeley.edu 8Forwarding Techniquespacket switching- aka [packet|datagram|connectionless] [switching|forwarding]source routingvirtual circuit switching- aka virtual circuit forwardingcircuit switchingdespite names, all ways for switch to decide which output port to forward [email protected] 9Packet SwitchingData is separated into packetsEach packet is forwarded independently of previous packets- packets between two hosts can follow different pathsOn link failure, adjoining switches select new route and continue forwarding packetsStatistical multiplexing- any one host may use 100% of a link’s [email protected] 10Statistical Multiplexing v.s. Resource ReservationsReserve explicit amount of resources (e.g., bandwidth)- get exactly that amountStatistical multiplexing: get whatever is available...SH9H010Mb/s / 10Mb/s......StatisticalMultiplexingResourceReservationsAdvantage Problem10Mb/s...SH9H0congestion,packet loss......10Mb/s10Mb/s10Mb/s 10Mb/s10Mb/s...SH9H0......1Mb/s1Mb/s10Mb/s1Mb/s...SH9H0......1Mb/s1Mb/s10Mb/s0Mb/s10Mb/s / 10Mb/s10Mb/s / 10Mb/s1Mb/s / 10Mb/slow [email protected] 11Packet Switching OperationEach switch maintains a forwarding table- forwarding entry: (address, output port)Upon packet arrival - input port forwards the packet to the output port whose address matches packet’s destination address• exact matchlongest prefix match- forwarding entry: (address prefix, output port)- forward packet to the output port whose address matches packet’s destination address in the longest number of bits212.xxx.xxx.xxx112.82.xxx.xxx1128.16.120.11112128.16.120.11112.82.100.101laik@cs.berkeley.edu 12Packet Switching PropertiesExpensive forwarding- forwarding table size depends on number of different destinations- must lookup in forwarding table for every packetRobust- link and router failure may be transparent for end-hostsHigh bandwidth utilization- statistical multiplexingNo service guarantees- Network allows hosts to send more packets than available bandwidth → congestion → dropped [email protected] 13Source RoutingEach packet specifies the sequence of routers, or alternatively the sequence of output ports, from source to destination 1234123412341234123412344source3 44 3 44 3 [email protected] 14Source Routing (cont’d)Gives the source control of the pathNot scalable- Packet overhead proportional to the number of routers- Typically, require variable header length which is harder to implementHard for source to have complete informationLoose source routing Æ sender specifies only a subset of routers along the [email protected] 15Virtual Circuit (VC) SwitchingPackets not switched independently- establish virtual circuit before sending dataForwarding table entry- (input port, input VCI, output port, output VCI)- VCI – Virtual Circuit IdentifierEach packet carries a VCI in its headerUpon a packet arrival at interface i - Input port uses i and the packet’s VCI v to find the routing entry (i, v, i’, v’)- Replaces v with v’ in the packet header- Forwards packet to output port i’[email protected] 16VC Forwarding: Example1234123412341234123412345……114………3…inoutin-VCI11out-VCI……5……73………2…inoutin-VCIout-VCI……117……14………1…inoutin-VCI out-VCI……[email protected] 17VC Forwarding (cont’d)A signaling protocol is required to set up the state for each VC in the routing table - A source needs to wait for one RTT (round trip time) before sending the first data packetCan provide per-VC QoS- When we set the VC, we can also reserve bandwidth and buffer resources along the [email protected] 18Virtual Circuit Switching PropertiesLess expensive forwarding- forwarding table size depends on number of different circuits- must lookup in forwarding table for every packetMuch higher delay for short flows- 1 RTT delay for connection setupLess Robust- end host must spend
View Full Document
Unlocking...