Direct Link Network Review EE 122 Switching and Forwarding Data link layer presents a single media e g single wire network model Problem 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 optimization Kevin Lai September 23 2002 laik cs berkeley edu Limitations of Direct Link Networks Direct Link Networks v s Switching distance n links distance increases propagation delay large propagation delay causes large coordination delay e g Ethernet collision detection requires 2 prop delay number of hosts bandwidth single media type 2 Single link More hosts increases the probability of collisions collisions decrease efficiency of link Switch Direct Link Network bandwidth of link is shared among all connected nodes Emulates clique Switched Network different media e g fiber Ethernet wireless have different tradeoffs for performance cost etc laik cs berkeley edu 3 laik cs berkeley edu Definitions Properties switch aka bridge does switching operates at data link layer router also does switching but at network layer forwarding read data from input links decide which output link to forward on and spans larger physical area than direct link network DLN supports more hosts than DLN higher aggregate bandwidth than DLN supports more than one media type can connect multiple switches together switching consists of hosts on separate links can transmit at same time approaches n 2 b instead of b n number of switched links b bandwidth of one link 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 table laik cs berkeley edu 4 more expensive for bridge than router 5 laik cs berkeley edu 6 1 Bridge Router Comparison Forwarding Techniques Router interconnects different link layer protocols more easily packet switching source routing virtual circuit switching aka packet datagram connectionless switching forwarding Router Switch Ethernet E to E Ethernet Ethernet E to IP IP to E Ethernet 802 11b E to 8 802 11b 802 11b 8 to IP IP to 8 802 11b ATM A to IP IP to A ATM IP to S SONET E to A EtoS ATM SONET ATM SONET SONET O n2 converters n different link types S to IP aka virtual circuit forwarding circuit switching despite names all ways for switch to decide which output port to forward data O n converters laik cs berkeley edu 7 laik cs berkeley edu Statistical Multiplexing v s Resource Reservations Packet Switching Advantage Data is separated into packets Each packet is forwarded independently of previous packets packets between two hosts can follow different paths On link failure adjoining switches select new route and continue forwarding packets Statistical multiplexing H0 H9 Resource Reservations any one host may use 100 of a link s bandwidth Problem 10Mb s 10Mb s Statistical Multiplexing 8 S 10Mb s 10Mb s 10Mb s 1Mb s H0 1Mb s 1Mb s H9 10Mb s 10Mb s H0 10Mb s 10Mb s H9 S 10Mb s 10Mb s congestion packet loss 10Mb s S 10Mb s 10Mb s 1Mb s H0 0Mb s 1Mb s H9 low utilization S 1Mb s 10Mb s Reserve explicit amount of resources e g bandwidth Statistical multiplexing get whatever is available get exactly that amount laik cs berkeley edu 9 laik cs berkeley edu Packet Switching Operation Each switch maintains a forwarding table Upon packet arrival Packet Switching Properties forwarding entry address output port input port forwards the packet to the output port whose address matches packet s destination address 12 82 100 101 exact match longest prefix match 128 16 120 111 12 xxx xxx xxx 12 82 xxx xxx 2 Expensive forwarding forwarding table size depends on number of different destinations must lookup in forwarding table for every packet 1 1 2 Robust High bandwidth utilization No service guarantees link and router failure may be transparent for end hosts 1 128 16 120 111 statistical multiplexing forwarding entry address prefix output port forward packet to the output port whose address matches packet s destination address in the longest number of bits laik cs berkeley edu 10 Network allows hosts to send more packets than available bandwidth congestion dropped packets 11 laik cs berkeley edu 12 2 Source Routing Source Routing cont d Each packet specifies the sequence of routers or alternatively the sequence of output ports from source to destination Packet overhead proportional to the number of routers Typically require variable header length which is harder to implement source 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 4 3 4 1 2 3 4 1 2 3 4 Gives the source control of the path Not scalable 1 2 3 4 Hard for source to have complete information Loose source routing sender specifies only a subset of routers along the path 4 3 4 laik cs berkeley edu 13 laik cs berkeley edu Virtual Circuit VC Switching Packets not switched independently Forwarding table entry VC Forwarding Example source input port input VCI output port output VCI VCI Virtual Circuit Identifier Each packet carries a VCI in its header Upon a packet arrival at interface i 5 1 2 3 4 1 2 3 4 4 1 7 4 1 destination 11 1 2 3 4 1 2 3 4 11 1 2 3 4 1 7 in in VCI out out VCI 2 11 3 7 laik cs berkeley edu 16 Virtual Circuit Switching Properties A signaling protocol is required to set up the state for each VC in the routing table Less expensive forwarding forwarding table size depends on number of different circuits must lookup in forwarding table for every packet A source needs to wait for one RTT round trip time before sending the first data packet 5 15 VC Forwarding cont d 3 1 2 3 4 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 laik cs berkeley edu in in VCI out out VCI in in VCI out out VCI establish virtual circuit before sending data 14 Can provide per VC QoS When we set the VC we can also reserve bandwidth and buffer resources along the path Much higher delay for short flows Less Robust 1 RTT delay for connection setup end host must spend 1 RTT to establish new connection after link and router failure Flexible service guarantees either statistical multiplexing or resource reservations laik cs berkeley edu 17 laik cs berkeley edu 18 3 Circuit Switching Circuit Switching Properties Packets not switched
View Full Document
Unlocking...