计算机代写 BB-76-09-AD

Link layer: introduction
terminology:
• hosts and routers: nodes
• communication channels that connect adjacent nodes along communication path: links

– wired links
– wireless links – LANs
• layer-2 packet: frame, encapsulates datagram
data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link
global ISP

Link layer: context
• datagram transferred by different link protocols over different links:
– e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link
• each link protocol provides different services
– e.g., may or may not provide 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
Link Layer 5-2

Link layer services
• 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!

Where is the link layer implemented?
• in each and every host
• link layer implemented in “adaptor” (aka network interface card NIC) or on a chip
– Ethernet card, 802.11 card; Ethernet chips
(e.g., PCI)
controller
transmission
network adapter card

Adaptors communicating
controller
controller
sending host
• sending side:
– encapsulates datagram in frame
– adds error checking bits, rdt, flow control, etc.
receiving host
receiving side
– looks for errors, rdt, flow control, etc
– extracts datagram, passes to upper layer at
receiving side

MAC addresses and ARP
• 32-bitIPaddress:
– network-layer address for interface
– used for layer 3 (network layer) forwarding
• MAC(orLANorphysicalorEthernet)address:
– function: used ‘locally” to get frame from one interface to another physically-connected interface (same network, in IP- addressing sense)
– 48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
– e.g.: 1A-2F-BB-76-09-AD
hexadecimal (base 16) notation (each “number” represents 4 bits)

What is a LAN?
• Local area network
• We will use the term “Local Area Network” (LAN or LAN segment; both are used interchangeably) to refer to each Ethernet shared link
– The term LAN can also be used to refer to an access point and all hosts associated with it

LAN addresses and ARP
each adapter on LAN has unique LAN address 1A-2F-BB-76-09-AD
LAN (wired or wireless)
71-65-F7-2B-08-53
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Link Layer

LAN addresses (more)
• MAC address allocation administered by IEEE
• manufacturer buys portion of MAC address space (to assure uniqueness)
• analogy:
– MAC address: like Social Security Number – 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

ARP: address resolution protocol
Question: how to determine interface’s MAC address, knowing its IP address?
ARP table: each IP node (host, router) on LAN has table
– IP/MAC address mappings for some LAN nodes:
< IP address; MAC address; TTL>
– TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)
137.196.7.23
71-65-F7-2B-08-53
137.196.7.88
137.196.7.78 1A-2F-BB-76-09-AD
137.196.7.14
58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98

ARP protocol: same LAN
• A wants to send datagram to B
– B’sMACaddressnotin A’s ARP table.
• A broadcasts ARP query packet, containing B’s IP address
– destMACaddress=FF-FF- FF-FF-FF-FF
– all nodes on L AN receive ARP query
• B receives ARP packet, replies to A with its (B’s) MAC address
– frame sent to A’s MAC address (unicast)
• A caches (saves) IP-to- MAC address pair in its ARP table until information becomes old (times out)
– soft state: information that times out (goes away) unless refreshed
• ARP is “plug-and-play”:
– nodes create their ARP tables without intervention from net administrator

Addressing: routing to another LAN
walkthrough: send datagram from A to B via R
– focus on addressing – at IP (datagram) and MAC layer (frame) – assume A knows B’s IP address
– assume A knows IP address of first hop router, R (how?)
– assume A knows R’s MAC address (how?)
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F

Addressing: routing to another LAN
v A creates IP datagram with IP source A, destination B
v A creates link-layer frame with R’s MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55 MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
Link Layer 5-14

Addressing: routing to another LAN
v framesentfromAtoR
v frame received at R, datagram removed, passed up to IP
MAC src: 74-29-9C-E8-FF-55 MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222 IP src: 111.111.111.111
IP dest: 222.222.222.222
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
Link Layer 5-15

111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
Link Layer

Addressing: routing to another LAN
v R forwards datagram with IP source A, destination B
v R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
Link Layer

Switches and bridges
• Switches: Link layer devices that have multiple input/output ports (interfaces) where LAN segments/hosts/other switches can plug in
• Switches are also called “bridges”. We will mostly use “switches” to avoid confusion, but realize that it means the same as “bridges”.
• Often connected using a star topology
• This forms the basis for scalable connectivity as nodes
can be added without impacting efficiency
• Key Functionality:
• Forwarding, Learning, Spanning Tree construction CS 640 19

Ethernet switch
• link-layer device: takes an active role
– store, forward Ethernet frames
– examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses contention resolution to access segment
• transparent
– hosts are unaware of presence of switches
• plug-and-play, self-learning
– switches do not need to be configured

Switch: multiple simultaneous transmissions
• hosts have dedicated, direct connection to switch
• switches buffer packets
• Ethernet protocol used on each incoming link, but no collisions; full duplex
– each link is its own collision domain
• switching: A-to-A’ and B-to-B’ can transmit simultaneously, without collisions
switch with six interfaces (1,2,3,4,5,6)

Switch forwarding table
Q: how does switch know A’ reachable via interface 4, B’ reachable via interface 5?
v A: each switch has a switch table, each entry:
§ (MAC address of host, interface to reach host, time stamp)
§ looks like a routing table! Q: how are entries created,
maintained in switch table?
§ something like a routing protocol?
switch with six interfaces (1,2,3,4,5,6)
Link Layer

Switch: self-learning
• switch learns which hosts can be reached through which interfaces
– when frame received, switch “learns” location of sender: incoming LAN segment
– records sender/location pair in switch table
Source: A Dest: A’
Switch table (initially empty)
Link Layer

Switch: frame filtering/forwarding
when frame received at switch:
1. record incoming link, MAC address of sending host
2. index switch table using MAC destination address
3. if entry found for destination then {
if destination on segment from which frame arrived then drop frame
else forward frame on interface indicated by entry }
else flood /* forward on all interfaces except arriving interface */

Self-learning, forwarding: example
Source: A Dest: A’
• frame destination, A’, locatonunknown: flood
v destination A location known: selectively send
on just one link
switch table (initially empty)

Interconnecting switches
switches can be connected together
Q: sending from A to G – how does S1 know to forward frame destined to F via S4 and S3?
v A: self learning! (works exactly the same as in single-switch case!)

Self-learning multi-switch example
Suppose C sends frame to I, I responds to C
v Q: show switch tables and packet forwarding in S1, S2, S3, S4

Institutional network
to external network
mail server
web server
Link Layer

Switches vs. routers
both are store-and-forward:
§ routers: network-layer devices (examine network- layer headers)
§ switches: link-layer devices (examine link-layer headers)
both have forwarding tables:
§ routers: compute tables using routing algorithms, IP addresses
§ switches: learn forwarding table using flooding, learning, MAC addresses
application
transport network link physical
application
link physical
transport network link physical
Link Layer

• Packet switching:
• Frame comes in on interfaces
• Switch looks at destination LL address
• Looks address up in a table and forwards it along
• Runs contention resolution method if needed
• Size of table in worst case == number of nodes
• If there is no entry in the table, then broadcast to all

• Learning
• Problem: How to build this table
• Constraint: Hosts can move or go offline
• Option: Manual configuration is painful and has no mobility support
• So switches use learning
• Keep track of source addresses of packets (S) arriving on interface (I)
• If packets arrive with destination address S then we know which interface to use
• Time out – accounts for mobility

Spanning Tree
How to handle forwarding in complex Layer 2 topologies?

Each LAN segment can have many bridges
• Morecomplextopologiescanprovideredundancy.
– But can also create loops.
• E.g. What happens when there is no table entry?
– Multiple copies of data
àCould crash the networkàhas happened often!
host host host
Bridge host host host
host host host
host host host

What is a Spanning Tree?
• Reduce our topology graph to a tree:
– Make sure there are no loops in the topology
– All LAN segments are still connected to the LAN and can receive messages
• Main idea: Bridges choose the ports over which they have to forward frames.

Spanning Tree Protocol Overview
Embed a tree that provides a single unique default path to each destination:
Bridges designate ports over which they will or will not forward frames
By removing ports, extended LAN is reduced to a tree
Addresses the crashing problem; but tree is not resilient
When switch/link fails, rerun protocol to converge to new tree

Spanning Tree Algorithm
• Root of the spanning tree is elected firstàthe bridge with the lowest identifier.
– All ports are part of tree
• Bridges designate ports on which they will/not forward
• Each bridge finds shortest path to the root.
– Remembers port that is on the shortest path
– Used to forward packets
• Select for each LAN a designated bridge that will forward frames to root
– Has the shortest path to the root.
– Identifier as tie-breaker

Spanning Tree Algorithm
• Each node sends configuration message to all neighbors.
– Identifier of the sender
– Id of the presumed root
– Distance to the presumed root
• Initially each bridge thinks it is the root.
– S5 sends (S5, S5, 0)
• When B receive a message, it decide whether the solution is better than their local solution.
– A root with a lower identifier?
– Same root but lower distance?
– Same root, distance but sender has lower identifier?
• Message from bridge with smaller root ID
– Not root; stop generating config messages, but can forward
• Message from bridge closer to root
– Not designated bridge; stop sending any config messages on the port
– Block port

Spanning Tree Algorithm
• Each bridge B can now select which of its ports make up the spanning tree:
– B’s root port
– All ports for which B is the designated bridge on the LAN
• States for ports on bridges
– Forward state or blocked state, depending on whether the port is part of the spanning tree
• Root periodically sends configuration messages and bridges forward them over LANs they are responsible for
• Any bridge failure => Start over

Spanning Tree Algorithm Example
–S3 receives (S2,S2,0)
–Since 2<3 S3 accepts S2 as a root –S3 adds one to the distance advertised by S2(0) and thus sends (S3,S2,1) toward S5 –Meanwhile S2 accepts S1 as the root and sends (S2,S1,1) –S5 accepts S1 as the root and sends (S5,S1,1) –S3 accepts S1as the root and figures that S5 and S2 are closer to the root. So stops forwarding on both interfaces. Bridge Protocol Data Units • STP requires network devices to exchange messages to form a loop-free logical topology • Messages called Bridge Protocol Data Units (BPDUs) – Ports that will cause a loop are put in a blocking state – BPDUs continue to be received on blocked ports Bridge Protocol Data Units • BPDUs help in – Select a single switch that will act as the root – Calculate the short path from itself to the root – Designate one of the switches as the closest one to the root for each LAN segment--- called the designated switch • Designated switch handles all communication from that LAN towards root bridge – Choose one of its ports as a root port (if non-root switch) • The interface that is the best path to the root bridge – Select ports that are part of the spanning tree, designated ports – Non-designated ports are blocked Info in BPDUs • Root BID (root bridge) • Root Path Cost (how far is the root bridge) • Sender BIF (who sent this BPDU) • Port ID (what port on the sending bridge does this BPDU come from) • Root ports and designated ports forward data • Non-designated ports discard data The numbered boxes represent bridges, that is switches in a LAN. The number is the bridge ID. The lettered clouds represent network segments. The smallest bridge ID is 3. Therefore, bridge 3 is the root bridge. Path tie: The least-cost path to the root from network segment e goes through bridge 92. Therefore, the designated port for network segment e is the port that connects bridge 92 to network segment e. Example with failure 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts