04 Chapter4 Network Layer.pptx

第1页：第5章：数据链路

第5章：数据链路

• understand principles behind data link layer services:
  • error detection, correction
  • sharing a broadcast channel: multiple access
  • link layer addressing
  • reliable data transfer, flow control:done!
• instantiation and implementation of various linklayer technologies

第2页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link virtualization:ATM, MPLS

第3页：链路层概述 Some 术语

链路层概述 Some 术语

• hosts and routers arenodes
• communication channels thatconnect adjacent nodes along communication path arelinks
  • wired links
  • wireless links
  • LANs
• layer-2 packet is aframe,encapsulates datagramdata-link layerhas responsibility oftransferring datagram from one nodeto adjacent node over a link

第4页：Link layer: context

Link layer: context

• datagram transferred bydifferent link protocolsover different links:
  • e.g., Ethernet on first link,frame relay onintermediate links, 802.11 on last link
• each link protocol provides different services
  • e.g., may or may notprovide rdt over link transportation analogy
• trip from Princeton to Lausanne
  • limo: Princeton to JFK
  • plane: JFK to Geneva
  • train: Geneva to Lausanne
• tourist =datagram
• transport segment =communication link
• transportation mode =link layer protocol
• travel agent =routing algorithm

第5页：链路层服务

链路层服务

• framing, link access:
  • encapsulate datagram into frame, adding header, trailer
  • channel access if shared medium
  • “MAC” addresses used in frame headers to identify source, dest
• different from IP address!
• reliable delivery between adjacent nodes
  • we learned how to do this already (chapter 3)!
  • seldom used on low bit-error link (fiber, some twistedpair)
  • wireless links: high error rates
• Q: why both link-level and end-end reliability?

第6页：链路层服务补充

链路层服务补充

• flow control:
  • pacing between adjacent sending and receiving nodes
• error detection:
  • errors caused by signal attenuation, noise.
  • receiver detects presence of errors:
• signals sender for retransmission or drops frame
• error correction:
  • receiver identifiesand correctsbit error(s) withoutresorting to retransmission
• half-duplex and full-duplex
  • with half duplex, nodes at both ends of link can transmit,but not at same time

第7页：Where link layer implemented?

Where link layer implemented?

• in each and every host
• link layer implemented in“adaptor” (akanetwork interface card NIC)
  • Ethernet card, PCMCIcard, 802.11 card
  • implements link, physical layer
• attaches into host’ssystem buses
• combination ofhardware, software,firmware controller physical transmissioncpu memoryhostbus(e.g., PCI)network adaptercardhost schematic application transport networklinklink physical

第8页：适配器通信

适配器通信

• sending side:
  • encapsulates datagram inframe
  • adds error checking bits,rdt, flow control, etc.
• receiving side
  • looks for errors, rdt, flowcontrol, etc
  • extracts datagram, passesto upper layer at receivingsidecontrollercontrollersending hostreceiving host datagram datagram datagram frame

第9页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM. MPLS

第10页：差错检测 EDC= 差错检测

差错检测 EDC= 差错检测

• Error detection not 100% reliable!
• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction otherwise

第11页：Parity Check

Parity Check

Parity Checking Single Bit Parity:Detect single bit errors Two Dimensional Bit Parity:Detectand correct single bit errors 00

第12页：Internet checksum(re

Internet checksum(re

• treat segment contentsas sequence of 16-bitintegers
• checksum: addition (1’scomplement sum) ofsegment contents
• sender puts checksum value into UDP checksum field Receiver:
• compute checksum ofreceived segment
• check if computed checksum equals checksum field value:
  • NO-error detected
  • YES-no error detected. But maybe errors nonetheless?Goal:detect “errors” (e.g., flipped bits) in transmitted packet (note: used at transport layeronly)

第13页：Check summing: Cyclic Redundancy Check

Check summing: Cyclic Redundancy Check

• view data bits, D, as a binary number
• choose r+1 bit pattern (generator), G
• goal: choose r CRC bits, R, such that
  • <D, R> exactly divisible by G (modulo 2)
  • receiver knows G, divides <D, R> by G. If non-zero remainder:error detected!
  • can detect all burst errors less than r+1 bits
• widely used in practice (802.11 Wi Fi, ATM)

第14页：CRC Example Want:D.2 r XOR R

CRC Example Want:D.2 r XOR R

CRC Example Want:D.2 r XOR R = n Gequivalently:D.2 r= n G XOR Requivalently:if we divide D.2 rby G, want remainder RR= remainder[ ]D.2 r G

第15页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM, MPLS

第16页：多路访问链路和协议 Two

多路访问链路和协议 Two

• point-to-point
  • PPP for dial-up access
  • point-to-point link between Ethernet switch and host
• broadcast(shared wire or medium)
  • old-fashioned Ethernet
  • upstream HFC
  • 802.11 wireless LANshared wire (e.g.,cabled Ethernet)shared RF(e.g., 802.11 Wi Fi)shared RF(satellite)humans at acocktail party(shared air, acoustical)

第17页：多路访问协议

多路访问协议

• single shared broadcast channel
• two or more simultaneous transmissions by nodes:interference
  • collisionif node receives two or more signals at the same timemultiple access protocol
• distributed algorithm that determines how nodesshare channel, i.e., determine when node can transmit
• communication about channel sharing must use channel itself!
  • no out-of-band channel for coordination

第18页：Ideal 多路访问协议广播信道

Ideal 多路访问协议广播信道

• no special node to coordinate transmissions
• no synchronization of clocks, slots 4. simple

第19页：MAC Protocols: taxonomy Three broad

MAC Protocols: taxonomy Three broad

• Channel Partitioning
  • divide channel into smaller “pieces” (time slots,frequency, code)
  • allocate piece to node for exclusive use
• Random Access
  • channel not divided, allow collisions
  • “recover” from collisions
• “Taking turns”
  • nodes take turns, but nodes with more to send can takelonger turns

第20页：信道划分 MAC 协议 TDM

信道划分 MAC 协议 TDM

• access to channel in "rounds"
• each station gets fixed length slot (length = pkttrans time) in each round
• unused slots go idle
• example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle 1341346-slotframe

第21页：信道划分 MAC 协议 FDM

信道划分 MAC 协议 FDM

• channel spectrum divided into frequency bands
• each station assigned fixed frequency band
• unused transmission time in frequency bands go idle
• example: 6-station LAN, 1,3,4 have pkt, frequencybands 2,5,6 idlefrequency bandstime FDM cable

第22页：随机接入协议

随机接入协议

• When node has packet to send
  • transmit at full channel data rate R.
  • noa priori coordination among nodes
• two or more transmitting nodes➜“collision”,
• random access MAC protocol specifies:
  • how to detect collisions
  • how to recover from collisions (e.g., via delayed retransmissions)
• Examples of random access MAC protocols:
  • slotted ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

第23页：Slotted ALOHA Assumptions

Slotted ALOHA Assumptions

• all frames same size
• time divided into equalsize slots (time totransmit 1 frame)
• nodes start to transmitonly slot beginning
• nodes are synchronized
• if 2 or more nodestransmit in slot, allnodes detect collision Operation:
• when node obtains fresh frame, transmits in nextslot
  • if no collision:node cansend new frame in nextslot
  • if collision:noderetransmits frame ineach subsequent slotwith prob. p until success

第24页：Slotted ALOHA

Slotted ALOHA

• single active node cancontinuously transmitat full rate of channel
• highly decentralized:only slots in nodesneed to be in sync
• simple Cons
• collisions, wasting slots
• idle slots
• nodes may be able todetect collision in lessthan time to transmit packet
• clock synchronization

第25页：Slotted Aloha efficiency

Slotted Aloha efficiency

• suppose:N nodes withmany frames to send,each transmits in slotwith probabilityp
• prob that given nodehas success in a slot=p(1-p)N-1
• prob thatanynode hasa success= Np(1-p)N-1
• max efficiency: findp* that maximizes Np(1-p)N-1
• for many nodes, takelimit of Np*(1-p*)N-1 as N goes to infinity,gives:Max efficiency = 1/e = .37 Efficiency: long-runfraction of successful slots(many nodes, all with manyframes to send)At best:channelused for useful transmissions 37%of time!!

第26页：Pure (unslotted) ALOHA

Pure (unslotted) ALOHA

• unslotted Aloha: simpler, no synchronization
• when frame first arrives
  • transmit immediately
• collision probability increases:
  • frame sent at t 0 collides with other frames sent in [t 0-1,t 0+1]

第27页：Pure Aloha efficiency P(success given

Pure Aloha efficiency P(success given

Pure Aloha efficiency P(success by given node) = P(node transmits). P(no other node transmits in [p 0-1,p 0]. P(no other node transmits in [p 0-1,p 0]= p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)… choosing optimum p and then letting n-> infty ...= 1/(2 e) = .18 evenworsethan slotted Aloha!

第28页：CSMA (Carrier Sense Multiple

CSMA (Carrier Sense Multiple

• If channel sensed busy, defer transmission
• human analogy: don’t interrupt others!

第29页：CSMA collisions collisions canst

CSMA collisions collisions canst

CSMA collisions collisions canstill occur:propagation delay meanstwo nodes may not heareach other’s transmission collision:entire packet transmissiontime wasted spatial layout of nodesnote:role of distance & propagation delay in deter mining collision probability

第30页：CSMA/CD (Collision Detection)CSMA/CD

CSMA/CD (Collision Detection)CSMA/CD

• collisions detected within short time
• colliding transmissions aborted, reducing channel wastage
• collision detection:
  • easy in wired LANs: measure signal strengths,compare transmitted, received signals
  • difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
• human analogy: the polite conversationalist

第31页：CSMA/CD collision detection

CSMA/CD collision detection

CSMA/CD collision detection

第32页：轮流 MAC 协议信道

轮流 MAC 协议信道

• share channelefficientlyandfairlyat high load
• inefficient at low load: delay in channel access,1/N bandwidth allocated even if only 1 activenode!Random access MAC protocols
• efficient at low load: single node can fully utilize channel
• high load: collision overhead“taking turns” protocolslook for best of both worlds!

第33页：轮流 MAC 协议轮询

轮流 MAC 协议轮询

• master node“invites” slave nodesto transmit in turn
• typically used with“dumb” slave devices
• concerns:
  • polling overhead
  • latency
  • single point offailure (master)masterslavespolldatadata

第34页：轮流 MAC 协议令牌传递

轮流 MAC 协议令牌传递

• control token passedfrom one node to nextsequentially.
• token message
• concerns:
  • token overhead
  • latency
  • single point of failure(token)Tdata(nothingto send)T

第35页：本章小结

本章小结

• channel partitioning,by time, frequency or code
  • Time Division, Frequency Division
• random access(dynamic),
  • ALOHA, S-ALOHA, CSMA, CSMA/CD
  • carrier sensing: easy in some technologies (wire), hard inothers (wireless)
  • CSMA/CD used in Ethernet
  • CSMA/CA used in 802.11
• taking turns
  • polling from central site, token passing
  • Bluetooth, FDDI, IBM Token Ring

第36页：LAN技术与链路层寻址

LAN技术与链路层寻址

• services, error detection/correction, multiple access Next: LAN technologies
• addressing
• Ethernet
• switches
• PPP

第37页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-Layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM, MPLS

第38页：MAC Addresses and ARP

MAC Addresses and ARP

• 32-bit IP address:
  • network-layer address
  • used to get datagram to destination IP subnet
• MAC (or LAN or physical or Ethernet)address:
  • function:get frame from one interface to another physically-connected interface (same network)
  • 48 bit MAC address (for most LANs)
• burned in NIC ROM, also sometimes software settable

第39页：LAN Addresses and ARPEach adapter

LAN Addresses and ARPEach adapter

LAN Addresses and ARPEach adapter on LAN has unique LAN address Broadcast address =FF-FF-FF-FF-FF-FF= adapter 1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53LAN(wired orwireless)

第40页：LAN 地址补充

LAN 地址补充

• MAC address allocation administered by IEEE
• manufacturer buys portion of MAC address space(to assure uniqueness)
• analogy:(a) MAC address: like Social Security Number(b) IP address: like postal address
• MAC flat address➜portability
  • can move LAN card from one LAN to another
• IP hierarchical address NOT portable
  • address depends on IP subnet to which node is attached

第41页：ARP: Address

ARP: Address

• Each IP node (host,router) on LAN has ARPtable
• ARP table: IP/MACaddress mappings forsome LAN nodes< IP address; MAC address; TTL>
  • TTL (Time To Live): timeafter which address mapping will be forgotten(typically 20 min)Question:how to determine MAC address of Bknowing B’s IP address?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53LAN137.196.7.23137.196.7.78137.196.7.14137.196.7.88

第42页：ARP 协议相同 LAN 网络

ARP 协议相同 LAN 网络

• A wants to send datagramto B, and B’s MAC addressnot in A’s ARP table.
• Abroadcasts ARP query packet, containing B's IPaddress
  • dest MAC address = FF-FF-FF-FF-FF-FF
  • all machines on LANreceive ARP query
• B receives ARP packet,replies to A with its (B's)MAC address
  • frame sent to A’s MACaddress (unicast)
• A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)
  • soft state: informationthat times out (goesaway) unless refreshed
• ARP is “plug-and-play”:
  • nodes create their ARPtables without intervention from netadministrator

第43页：DHCP: Dynamic Host Configuration

DHCP: Dynamic Host Configuration

• support for mobile users joining network
• host holds address only while connected and “on”(allowing address reuse)
• renew address already in use
• DHCP overview:
  • 1. host broadcasts “DHCP discover” msg
  • 2. DHCP server responds with “DHCP offer” msg
  • 3. host requests IP address: “DHCP request” msg
  • 4. DHCP server sends address: “DHCP ack” msg

第44页：DHCP client-server scenario

DHCP client-server scenario

DHCP client-server scenario 223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEDHCPserverarriving DHCPclientneedsaddress in this(223.1.2/24) network

第45页：DHCP client-server scenario DHCP

DHCP client-server scenario DHCP

DHCP client-server scenario DHCP server: 223.1.2.5 arrivingclienttime DHCP discoversrc : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654DHCP offersrc: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 Lifetime: 3600 secs DHCP requestsrc: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs DHCP ACKsrc: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs

第46页：编址路由 另一种 LAN

编址路由 另一种 LAN

• two ARP tables in router R, one for each IPnetwork (LAN)

第47页：creates IP datagram with source

creates IP datagram with source

• A creates IP datagram with source A, destination B
• A uses ARP to get R’s MAC address for 111.111.111.110
• A creates link-layer frame with R's MAC address as dest,frame contains A-to-B IP datagram
• A’s NIC sends frame
• R’s NIC receives frame
• R removes IP datagram from Ethernet frame, sees itsdestined to B
• R uses ARP to get B’s MAC address
• R creates frame containing A-to-B IP datagram sends to BR1A-23-F9-CD-06-9B222.222.222.220111.111.111.110E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D111.111.111.112111.111.111.111A74-29-9C-E8-FF-55222.222.222.22188-B2-2F-54-1A-0FB222.222.222.22249-BD-D2-C7-56-2AThis is areally important example
  • make sure youunderstand!

第48页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-Layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM and MPLS

第49页：Ethernet“dominant” wired LAN technology

Ethernet“dominant” wired LAN technology

• cheap $20 for NIC
• first widely used LAN technology
• simpler, cheaper than token LANs and ATM
• kept up with speed race: 10 Mbps
  • 10 Gbps Metcalfe’s Ethernet sketch

第50页：星形拓扑

星形拓扑

• bus topology popular through mid 90 s
  • all nodes in same collision domain (can collide with eachother)
• today: star topology prevails
  • active switchin center
  • each “spoke” runs a (separate) Ethernet protocol (nodesdo not collide with each other)switchbus: coaxial cablestar

第51页：以太网帧结构发送 adapter

以太网帧结构发送 adapter

• 7 bytes with pattern 10101010 followed by onebyte with pattern 10101011
• used to synchronize receiver, sender clock rates

第52页：以太网帧结构补充

以太网帧结构补充

• Addresses:6 bytes
  • if adapter receives frame with matching destination address, or with broadcast address (eg ARP packet), itpasses data in frame to network layer protocol
  • otherwise, adapter discards frame
• Type:indicates higher layer protocol (mostly IPbut others possible, e.g., Novell IPX, Apple Talk)
• CRC:checked at receiver, if error is detected,frame is dropped

第53页：以太网不可靠无连接

以太网不可靠无连接

• connectionless:No handshaking between sending andreceiving NICs
• unreliable:receiving NIC doesn’t send acks or nacksto sending NIC
  • stream of datagrams passed to network layer can have gaps(missing datagrams)
  • gaps will be filled if app is using TCP
  • otherwise, app will see gaps
• Ethernet’s MAC protocol: unslotted CSMA/CD

第54页：Ethernet CSMA/CD algorithm 1. NIC

Ethernet CSMA/CD algorithm 1. NIC

Ethernet CSMA/CD algorithm 1. NIC receives datagramfrom network layer,creates frame 2. If NIC senses channel idle,starts frame transmission If NIC senses channelbusy, waits until channelidle, then transmits 3. If NIC transmits entire frame without detecting another transmission, NICis done with frame !4. If NIC detects another transmission while transmitting, aborts andsends jam signal 5. After aborting, NICentersexponentialbackoff: aftermthcollision, NIC chooses Katrandom from{0,1,2,…,2 m-1}. NIC waits K·512 bit times, returns to Step 2

第55页：Ethernet’s CSMA/CD (more)Jam Signal

Ethernet’s CSMA/CD (more)Jam Signal

• Goal: adapt retransmission attempts to estimated current load
  • heavy load: random waitwill be longer
• first collision: choose K from{0,1}; delay is K·512 bittransmission times
• after second collision: choose K from {0,1,2,3}…
• after ten collisions, choose Kfrom {0,1,2,3,4,…,1023}See/interact with Javaapplet on AWL Web site:highly recommended !

第56页：CSMA/CD efficiency

CSMA/CD efficiency

• Tprop= max prop delay between 2 nodes in LAN
• ttrans= time to transmit max-size frame
• efficiency goes to 1
  • as tpropgoes to 0
  • as ttransgoes to infinity
• better performance than ALOHA: and simple,cheap, decentralized!

第57页：3 Ethernet Standards: Link & Physical

3 Ethernet Standards: Link & Physical

• manydifferent Ethernet standards
  • common MAC protocol and frame format
  • different speeds: 2 Mbps, 10 Mbps, 100 Mbps,1 Gbps, 10G bps
  • different physical layer media: fiber, cable application transport networklink physical MAC protocoland frame format 100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BXfiber physical layer copper (twisterpair) physical layer

第58页：曼彻斯特编码

曼彻斯特编码

• used in 10 Base T
• each bit has a transition
• allows clocks in sending and receiving nodes tosynchronize to each other
  • no need for a centralized, global clock among nodes!
• Hey, this is physical-layer stuff!

第59页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-layer Addressing
• 5.5 Ethernet
• 5.6 Link-layer switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM, MPLS

第60页：Hubs… physical-layer (“dumb”) repeaters

Hubs… physical-layer (“dumb”) repeaters

• bits coming in one link go outallother links atsame rate
• all nodes connected to hub can collide with oneanother
• no frame buffering
• no CSMA/CD at hub: host NICs detect collisions twisted pairhub

第61页：交换机

交换机

• link-layer device: smarter than hubs, takeactiverole
  • store, forward Ethernet frames
  • examine incoming frame’s MAC address,selectively forward frame to one-or-moreoutgoing links when frame is to be forwarded onsegment, uses CSMA/CD to access segment
• transparent
  • hosts are unaware of presence of switches
• plug-and-play, self-learning
  • switches do not need to be configured

第62页：Switch: allows multiple simultaneous

Switch: allows multiple simultaneous

• hosts have dedicated,direct connection to switch
• switches buffer packets
• Ethernet protocol used oneachincoming link, but nocollisions; full duplex
  • each link is its own collision domain
• switching:A-to-A’ and B-to-B’ simultaneously,without collisions
  • not possible with dumb hub AA’BB’CC’switch with six interfaces(1,2,3,4,5,6)123456

第63页：交换表

交换表

• Q:how does switch know that A’ reachable via interface 4, B’ reachable via interface 5?
• A:each switch has aswitch table,each entry:
  • (MAC address of host, inter faceto reach host, time stamp)
• looks like a routing table!
• Q:how are entries created,maintained in switch table?
  • something like a routing protocol?AA’BB’CC’switch with six interfaces(1,2,3,4,5,6)123456

第64页：Switch: self-learning

Switch: self-learning

• switch learns which hostscan be reached through which interfaces
  • when frame received,switch “learns” location ofsender: incoming LANsegment
  • records sender/locationpair in switch table AA’BB’CC’123456A A’Source: ADest: A’MAC addr interface TTLSwitch table(initially empty)A160

第65页：Switch: frame filtering/forwarding

Switch: frame filtering/forwarding

Switch: frame filtering/forwarding When frame received:1. record link associated with sending host 2. index switch table using MAC dest address 3. ifentry found for destinationthen {ifdest on segment from which frame arrivedthendrop the frameelse forward the frame on interface indicated}else flood forward on all but the interfaceon which the frame arrived

第66页：Self-learning,forwarding:example

Self-learning,forwarding:example

• frame destination unknown:flood A’ A
• destination Alocation known:A’460 selective send

第67页：Interconnecting switches

Interconnecting switches

• switches can be connected together AB
• Q:sending from A to F-how does S1 know toforward frame destined to F via S4 and S3?
• A:self learning! (works exactly the same as insingle-switch case!)S1CDEFS2S4S3HIG

第68页：Self-learning

Self-learning

• Q:show switch tables and packet forwarding in S1, S2, S3, S4ABS1CDEFS2S4S3HIG12

第69页：Institutional networkto external

Institutional networkto external

Institutional networkto external network router IP subnetmail serverweb server

第70页：交换机 vs. 路由器

交换机 vs. 路由器

• both store-and-forward devices
  • routers: network layer devices (examine network layer headers)
  • switches are link layer devices
• routers maintain routing tables, implement routing algorithms
• switches maintain switch tables, implement filtering, learning algorithms

第71页：本章小结

本章小结

Summary comparison

第72页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-Layer Addressing
• 5.5 Ethernet
• 5.6 Hubs and switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM

第73页：点对点数据链路控制

点对点数据链路控制

• one sender, one receiver, one link: easier thanbroadcast link:
  • no Media Access Control
  • no need for explicit MAC addressing
  • e.g., dialup link, ISDN line
• popular point-to-point DLC protocols:
  • PPP (point-to-point protocol)
  • HDLC: High level data link control (Data linkused to be considered “high layer” in protocol stack!

第74页：PPP Design Requirements [RFC 1557]

PPP Design Requirements [RFC 1557]

• packet framing:encapsulation of network-layer datagram in data link frame
  • carry network layer data of any network layer protocol (not just IP)at same time
  • ability to demultiplex upwards
• bit transparency:must carry any bit pattern in thedata field
• error detection(no correction)
• connection liveness:detect, signal link failure tonetwork layer
• network layer address negotiation:endpoint canlearn/configure each other’s network address

第75页：PPP non-requirements

PPP non-requirements

• no error correction/recovery
• no flow control
• out of order delivery OK
• no need to support multi point links (e.g., polling)Error recovery, flow control, data re-orderingall relegated to higher layers!

第76页：PPP数据帧格式

PPP数据帧格式

• Flag:delimiter (framing)
• Address:does nothing (only one option)
• Control:does nothing; in the future possible multiple control fields
• Protocol:upper layer protocol to which frame delivered (eg, PPP-LCP, IP, IPCP, etc)

第77页：PPP数据帧示例

PPP数据帧示例

• info:upper layer data being carried
• check:cyclic redundancy check for error detection

第78页：字节填充

字节填充

• “data transparency” requirement: data field mustbe allowed to include flag pattern <01111110>
  • Q:is received <01111110> data or flag?
• Sender:adds (“stuffs”) extra < 01111110> byteafter each < 01111110>databyte
• Receiver:
  • two 01111110 bytes in a row: discard first byte,continue data reception
  • single 01111110: flag byte

第79页：字节填充

字节填充

Byte Stuffingflag bytepatternin datato sendflag byte pattern plusstuffed byte intransmitted data

第80页：PPP Data Control Protocol Before

PPP Data Control Protocol Before

• configure PPP link(max.frame length,authentication)
• learn/configure network layer information
  • for IP: carry IP Control Protocol (IPCP) msgs(protocol field: 8021) toconfigure/learn IPaddress

第81页：链路层

链路层

• 5.1 Introduction andservices
• 5.2 Error detectionand correction
• 5.3 Multiple access protocols
• 5.4 Link-Layer Addressing
• 5.5 Ethernet
• 5.6 Hubs and switches
• 5.7 PPP
• 5.8 Link Virtualization:ATM and MPLS

第82页：虚拟化的网络虚拟化

虚拟化的网络虚拟化

• computing examples: virtual memory, virtualdevices
  • Virtual machines: e.g., java
  • IBM VM os from 1960’s/70’s
• layering of abstractions: don’t sweat the details ofthe lower layer, only deal with lower layers abstractly

第83页：Internet: virtual

Internet: virtual

• ARPAnet
• data-over-cable networks
• packet satellite network (Aloha)
• packet radio network… differing in:
• addressing conventions
• packet formats
• error recovery
• routing ARPAnet satellite net"A Protocol for Packet Network Intercommunication", V. Cerf, R. Kahn, IEEE Transactions on Communications, May, 1974, pp. 637-648.

第84页：Internet: virtual

Internet: virtual

• addressing: inter network appears as single, uniform entity, despite underlying local network heterogeneity
• network of networks Gateway:
• “embed inter network packets inlocal packet format or extractthem”
• route (at inter network level) tonext gateway

第85页：Cerf & Kahn’s Inter network Architecture

Cerf & Kahn’s Inter network Architecture

• two layers of addressing: inter network and local network
• new layer (IP) makes everything homogeneous atinter network layer
• underlying local network technology
  • cable
  • satellite
  • 56K telephone modem
  • today: ATM, MPLS… “invisible” at inter network layer. Looks like a linklayer technology to IP!

第86页：ATM and MPLS

ATM and MPLS

• ATM, MPLS separate networks in their ownright
  • different service models, addressing, routingfrom Internet
• viewed by Internet as logical link connecting IP routers
  • just like dialup link is really part of separate network (telephone network)
• ATM, MPLS: of technical interest in theirown right

第87页：Asynchronous Transfer Mode: ATM

Asynchronous Transfer Mode: ATM

• 1990’s/00 standard for high-speed(155 Mbps to 622 Mbps and higher)Broadband Integrated Service Digital Network architecture
• Goal:integrated, end-end transport of carry voice,video, data
  • meeting timing/Qo S requirements of voice, video(versus Internet best-effort model)
  • “next generation” telephony: technical roots intele phone world
  • packet-switching (fixed length packets, called“cells”) using virtual circuits

第88页：ATM 体系结构

ATM 体系结构

• adaptation layer:only at edge of ATM network
  • data segmentation/reassembly
  • roughly analagous to Internet transport layer
• ATM layer:“network” layer
  • cell switching, routing
• physical layer physical ATMAALphysical ATMAALphysical ATMphysical ATMend systemend system switch switch

第89页：ATM: network or link layer?Vision

ATM: network or link layer?Vision

• ATMisa network technology Reality:used to connect IP backbone routers
• “IP over ATM”
• ATM as switchedlink layer,connecting IProuters ATMnetwork IPnetwork

第90页：ATM Adaptation Layer (AAL)

ATM Adaptation Layer (AAL)

• ATMAdaptation Layer(AAL): “adapts” upper layers (IP or native ATM applications) to ATMlayer below
• AAL presentonly in end systems, not in switches
• AAL layer segment (header/trailer fields, data)fragmented across multiple ATM cells
  • analogy: TCP segment in many IP packets physical ATMAALphysical ATMAALphysical ATMphysical ATMend systemend system switch switch

第91页：ATM Adaptation Layer (AAL) [more]

ATM Adaptation Layer (AAL) [more]

• AAL1:for CBR (Constant Bit Rate) services, e.g. circuit emulation
• AAL2:for VBR (Variable Bit Rate) services, e.g., MPEG video
• AAL5:for data (eg, IP datagrams)AAL PDUATM cell User data

第92页：ATM Layer Service:transport cells

ATM Layer Service:transport cells

• analogous to IP network layer
• very different services than IP network layer Network Architecture Internet ATMATMATMATMService Modelbest effort CBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteedminimumnone Lossnoyesyesnono Ordernoyesyesyesyes Timingnoyesyesnono Congestion feedbackno (inferredvia loss)nocongestionnocongestionyesno Guarantees ?

第93页：ATM Layer: Virtual Circuits

ATM Layer: Virtual Circuits

• VC transport:cells carried on VC from source to dest
  • call setup, teardown for each callbeforedata can flow
  • each packet carries VC identifier (not destination ID)
  • every switch on source-dest path maintain “state” for eachpassing connection
  • link,switch resources (bandwidth, buffers) may beallocatedto VC: to get circuit-like perf.
• Permanent VCs (PVCs)
  • long lasting connections
  • typically: “permanent” route between to IP routers
• Switched VCs (SVC):
  • dynamically set up on per-call basis

第94页：ATM虚电路

ATM虚电路

• Advantages of ATM VC approach:
  • Qo S performance guarantee for connection mapped to VC (bandwidth, delay, delay jitter)
• Drawbacks of ATM VC approach:
  • Inefficient support of datagram traffic
  • one PVC between each source/dest pair) doesnot scale (N*2 connections needed)
  • SVC introduces call setup latency, processing overhead for short lived connections

第95页：ATM Layer: ATM cell

ATM Layer: ATM cell

• 5-byte ATM cell header
• 48-byte payload
  • Why?: small payload-> short cell-creation delayfor digitized voice
  • halfway between 32 and 64 (compromise!)Cell header Cell format

第96页：ATM 信元首部

ATM 信元首部

• VCI:virtual channel ID
  • willchangefrom link to link thru net
• PT:Payload type (e.g. RM cell versus data cell)
• CLP:Cell Loss Priority bit
  • CLP = 1 implies low priority cell, can bediscarded if congestion
• HEC:Header Error Checksum
  • cyclic redundancy check

第97页：ATM 物理层补充

ATM 物理层补充

• Transmission Convergence Sublayer (TCS):adapts ATM layer above to PMD sublayer below
• Physical Medium Dependent:depends on physical medium being used TCS Functions:
  • Header checksum generation: 8 bits CRC
  • Cell delineation
  • With “unstructured” PMD sublayer, transmissionofidle cellswhen no data cells to send

第98页：ATM Physical Layer Physical Medium

ATM Physical Layer Physical Medium

• SONET/SDH:transmission frame structure (like acontainer carrying bits);
  • bit synchronization;
  • bandwidth partitions (TDM);
  • several speeds:OC3 = 155.52 Mbps; OC12 = 622.08 Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps
• TI/T3:transmission frame structure (oldtelephone hierarchy): 1.5 Mbps/ 45 Mbps
• unstructured: just cells (busy/idle)

第99页：网络虚拟化：ATM与MPLS（示意图）

网络虚拟化：ATM与MPLS（示意图）

• 3 “networks” (e.g., LAN segments)
• MAC (802.3) and IPaddresses IP over ATM
• replace “network”(e.g., LAN segment)with ATM network
• ATM addresses, IPaddresses ATMnetwork Ethernet LANs Ethernet LANs

第100页：网络虚拟化：ATM与MPLS（示意图）

网络虚拟化：ATM与MPLS（示意图）

IP-Over-ATMAALATMphyphy Eth IPATMphy ATMphyapptransport IPAALATMphyapptransport IPEthphy

第101页：Datagram Journey IP

Datagram Journey IP

• at Source Host:
  • IP layer maps between IP, ATM dest address (using ARP)
  • passes datagram to AAL5
  • AAL5 encapsulates data, segments cells, passes to ATM layer
• ATM network:moves cell along VC to destination
• at Destination Host:
  • AAL5 reassembles cells into original datagram
  • if CRC OK, datagram is passed to IP

第102页：网络虚拟化：ATM与MPLS（示意图）

网络虚拟化：ATM与MPLS（示意图）

• IP datagrams into ATM AAL5 PDUs
• from IP addressesto ATM addresses
  • just like IPaddresses to 802.3 MACaddresses!ATMnetwork Ethernet LANs

第103页：Multi protocol label switching (MPLS)

Multi protocol label switching (MPLS)

• initial goal: speed up IP forwarding by using fixed length label (instead of IP address) to doforwarding
  • borrowing ideas from Virtual Circuit (VC) approach
  • but IP datagram still keeps IP address!PPP or Ethernet header IP header remainder of link-layer frame MPLS header label Exp STTL20315

第104页：MPLS capable routers

MPLS capable routers

• a.k.a. label-switched router
• forwards packets to outgoing interface basedonly on label value (don’t inspect IP address)
  • MPLS forwarding table distinct from IP forwarding tables
• signaling protocol needed to set up forwarding
  • RSVP-TE
  • forwarding possible along paths that IP alone wouldnot allow (e.g., source-specific routing) !!
  • use MPLS for traffic engineering
• must co-exist with IP-only routers

第105页：网络虚拟化：ATM与MPLS（示意图）

网络虚拟化：ATM与MPLS（示意图）

R1R2DR3R4R50100AR6 in out outlabel label dest interface 6-A 0 in out outlabel label dest interface 10 6 A 112 9 D 0 in out outlabel label dest interface 10 A 012 D 01 in out outlabel label dest interface 8 6 A 008 A 1MPLS forwarding tables

第106页：第5章小结

第5章小结

• principles behind data link layer services:
  • error detection, correction
  • sharing a broadcast channel: multiple access
  • link layer addressing
• instantiation and implementation of various linklayer technologies
  • Ethernet
  • switched LANS
  • PPP
  • virtualized networks as a link layer: ATM, MPLS

第107页：Chapter 5: let’s take

Chapter 5: let’s take

• journey down protocol stack complete(except PHY)
• solid understanding of networking principles,practice
• ….. could stop here …. butlotsof interesting topics!
  • wireless
  • multimedia
  • security
  • network management