CS6551 COMPUTER NETWORKS

UNIT – II

Dr.P.Veeralakshmi, Associate Professor/IT,

Prince Shri Venkateshwara Padmavathy
Engineering College
 Unit - II
MEDIAACCESS & INTERNETWORKING

 Media access control – Ethernet (802.3) –

Wireless LANs – 802.11 – Bluetooth –
Switching and bridging – Basic
Internetworking (IP, CIDR, ARP,
DHCP,ICMP )

Computer Networks: A Systems Approach, 5e, Larry L. Peterson and Bruce S. Davie
 Ethernet
 Most successful local area networking technology of last 20 years.
 Developed in the mid-1970s by researchers at the Xerox Palo Alto
Research Centers (PARC).
 Uses CSMA/CD technology
 Carrier Sense Multiple Access with Collision Detection.
 A set of nodes send and receive frames over a shared link.
 Carrier sense means that all nodes can distinguish between an idle and a busy
link.
 Collision detection means that a node listens as it transmits and can therefore
detect when a frame it is transmitting has collided with a frame transmitted by
another node.
 Uses ALOHA (packet radio network) as the root protocol
 Developed at the University of Hawaii to support communication across the
Hawaiian Islands.
 For ALOHA the medium was atmosphere, for Ethernet the medium is a coax
cable.
3
 Ethernet
 DEC and Intel joined Xerox to define a 10-Mbps Ethernet
standard in 1978.
 This standard formed the basis for IEEE standard 802.3
 More recently 802.3 has been extended to include a 100-Mbps
version called Fast Ethernet and a 1000-Mbps version called
Gigabit Ethernet.
 An Ethernet segment is implemented on a coaxial cable of up to 500 m.
 This cable is similar to the type used for cable TV except that it typically
has an impedance of 50 ohms instead of cable TV’s 75 ohms.
 Hosts connect to an Ethernet segment by tapping into it.
 A transceiver (a small device directly attached to the tap) detects when
the line is idle and drives signal when the host is transmitting.
 The transceiver also receives incoming signal.
4
 Ethernet
 The transceiver is connected to an
Ethernet adaptor which is plugged
into the host.
 The protocol is implemented on the
adaptor.
 Multiple Ethernet segments can
be joined together by repeaters.
 A repeater is a device that
forwards digital signals.
 No more than four repeaters may
be positioned between any pair of
Ethernet transceiver and adaptor
hosts.
 An Ethernet has a total reach of only
2500 m.
5
 Ethernet
Any signal placed on the
Ethernet by a host is
broadcast over the entire
network
Signal is propagated in both
directions.
Repeaters forward the signal
on all outgoing segments.
Terminators attached to the
end of each segment absorb
the signal. Ethernet repeater

Ethernet uses Manchester

encoding scheme.
6
 Ethernet
New Technologies in Ethernet
 Instead of using coax cable, an Ethernet can be constructed from a thinner
cable known as 10Base2 (the original was 10Base5)
10 means the network operates at 10 Mbps
Base means the cable is used in a baseband system
2 means that a given segment can be no longer than 200 m
 Another cable technology is 10BaseT
T stands for twisted pair
Limited to 100 m in length
 With 10BaseT, the common configuration is to have several point to point
segments coming out of a multiway repeater, called Hub

Ethernet Hub

7
 Access Protocol for Ethernet
 The algorithm is commonly called Ethernet’s Media Access Control
(MAC).
 It is implemented in Hardware on the network adaptor.
 Frame format
 Preamble (64bit): allows the receiver to synchronize with the signal
(sequence of alternating 0s and 1s).
 Host and Destination Address (48bit each).
 Packet type (16bit): acts as demux key to identify the higher level protocol.
 Data (up to 1500 bytes)
 Minimally a frame must contain at least 46 bytes of data.
 Frame must be long enough to detect collision.
 CRC (32bit)

8
 Ethernet Addresses
 Each host on an Ethernet (in fact, every Ethernet host in the world)
has a unique Ethernet Address.
 The address belongs to the adaptor, not the host.
 It is usually burnt into ROM.
 Ethernet addresses are typically printed in a human readable format
 As a sequence of six numbers separated by colons.
 Each number corresponds to 1 byte of the 6 byte address and is given by a pair
of hexadecimal digits, one for each of the 4-bit nibbles in the byte
 Leading 0s are dropped.
 For example, 8:0:2b:e4:b1:2 is
 00001000 00000000 00101011 11100100 10110001 00000010
 To ensure that every adaptor gets a unique address, each
manufacturer of Ethernet devices is allocated a different prefix that
must be prepended to the address on every adaptor they build
AMD has been assigned the 24bit prefix 8:0:20
9
 Ethernet Addresses
 Each frame transmitted on an Ethernet is received by every adaptor
connected to that Ethernet.
 Each adaptor recognizes those frames addressed to its address and
passes only those frames on to the host.
 In addition, to unicast address, an Ethernet address consisting of all
1s is treated as a broadcast address.
 All adaptors pass frames addressed to the broadcast address up to the host.
 Similarly, an address that has the first bit set to 1 but is not the
broadcast address is called a multicast address.
 A given host can program its adaptor to accept some set of
multicast addresses. To summarize, an Ethernet adaptor receives all
frames and accepts
 Frames addressed to its own address
 Frames addressed to the broadcast address
 Frames addressed to a multicast addressed if it has been instructed

10
 Ethernet Transmitter Algorithm
 When the adaptor has a frame to send and the line is idle, it transmits
the frame immediately.
 The upper bound of 1500 bytes in the message means that the adaptor can
occupy the line for a fixed length of time.
 When the adaptor has a frame to send and the line is busy, it waits
for the line to go idle and then transmits immediately.
 The Ethernet is said to be 1-persistent protocol because an adaptor
with a frame to send transmits with probability 1 whenever a busy
line goes idle.
 Since there is no centralized control it is possible for two (or more)
adaptors to begin transmitting at the same time,
 Either because both found the line to be idle,
 Or, both had been waiting for a busy line to become idle.
 When this happens, the two (or more) frames are said to be collide
on the network. 11
 Ethernet Transmitter Algorithm
 Since Ethernet supports collision detection, each sender is able
to determine that a collision is in progress.
 At the moment an adaptor detects that its frame is colliding
with another, it first makes sure to transmit a 32-bit jamming
sequence and then stops transmission.
 Thus, a transmitter will minimally send 96 bits in the case of collision
 64-bit preamble + 32-bit jamming sequence
 One way that an adaptor will send only 96 bit (called a runt
frame) is if the two hosts are close to each other.
 Had they been farther apart,
 They would have had to transmit longer, and thus send more bits,
before detecting the collision.

12
 Ethernet Transmitter Algorithm
The worst case scenario happens when the two hosts are at
opposite ends of the Ethernet.
To know for sure that the frame its just sent did not collide
with another frame, the transmitter may need to send as
many as 512 bits.
Every Ethernet frame must be at least 512 bits (64 bytes) long.
14 bytes of header + 46 bytes of data + 4 bytes of CRC
Why 512 bits?
Why is its length limited to 2500 m?
The farther apart two nodes are, the longer it takes for a
frame sent by one to reach the other, and the network is
vulnerable to collision during this time
13
 Ethernet Transmitter Algorithm
 A begins transmitting a frame at time t
 d denotes the one link latency
 The first bit of A’s frame arrives at B at
time t + d
 Suppose an instant before host A’s frame
arrives, host B begins to transmit its own
frame
 B’s frame will immediately collide with A’s
frame and this collision will be detected by
host B
 Host B will send the 32-bit jamming
sequence
 Host A will not know that the collision
occurred until B’s frame reaches it, which
will happen at t + 2 * d
 Host A must continue to transmit until this Worst-case scenario: (a) A sends a frame
time in order to detect the collision at time t; (b) A’s frame arrives at B at time
t + d; (c) B begins transmitting at time t + d
 Host A must transmit for 2 * d to be and collides with A’s frame; (d) B’s runt
sure that it detects all possible (32-bit) frame arrives at A at time t + 2d.
collisions 14
 Ethernet Transmitter Algorithm
Consider that a maximally configured Ethernet is 2500 m
long, and there may be up to four repeaters between any two
hosts, the round trip delay has been determined to be 51.2
s
Which on 10 Mbps Ethernet corresponds to 512 bits
The other way to look at this situation,
We need to limit the Ethernet’s maximum latency to a fairly small
value (51.2 s) for the access algorithm to work
Hence the maximum length for the Ethernet is on the order of 2500 m.
 Once an adaptor has detected a collision, and stopped its transmission,
it waits a certain amount of time and tries again.
 Each time the adaptor tries to transmit but fails, it doubles the amount
of time it waits before trying again.
15
 Ethernet Transmitter Algorithm
 This strategy of doubling the delay interval between each
retransmission attempt is known as Exponential Backoff.
 The adaptor first delays either 0 or 51.2 s, selected at random.
 If this effort fails, it then waits 0, 51.2, 102.4, 153.6 s (selected
randomly) before trying again;
 This is k * 51.2 for k = 0, 1, 2, 3
 After the third collision, it waits k * 51.2 for k = 0…23 – 1 (again
selected at random).
 In general, the algorithm randomly selects a k between 0 and 2n –
1 and waits for k * 51.2 s, where n is the number of collisions
experienced so far.

16
 Experience with Ethernet
 Ethernets work best under lightly loaded conditions.
 Under heavy loads, too much of the network’s capacity is wasted by
collisions.
 Most Ethernets are used in a conservative way.
 Have fewer than 200 hosts connected to them which is far fewer than the
maximum of 1024.
 Most Ethernets are far shorter than 2500m with a round-trip
delay of closer to 5 s than 51.2 s.
 Ethernets are easy to administer and maintain.
 There are no switches that can fail and no routing and configuration tables
that have to be kept up-to-date.
 It is easy to add a new host to the network.
 It is inexpensive.
 Cable is cheap, and only other cost is the network adaptor on each host.

17
 Wireless Links
 Wireless links transmit electromagnetic signals
 Radio, microwave, infrared
 Wireless links all share the same “wire” (so to speak)
 The challenge is to share it efficiently without unduly interfering with each other
 Most of this sharing is accomplished by dividing the “wire” along the
dimensions of frequency and space
 Exclusive use of a particular frequency in a particular geographic area
may be allocated to an individual entity such as a corporation
 Devices that use license-exempt frequencies are still subject to certain
restrictions
 The first is a limit on transmission power
 This limits the range of signal, making it less likely to interfere with another
signal
 For example, a cordless phone might have a range of about 100 feet.

18
 Wireless Links
These allocations are determined by government agencies
such as FCC (Federal Communications Commission) in
USA
Specific bands (frequency) ranges are allocated to certain
uses.
Some bands are reserved for government use
Other bands are reserved for uses such as AM radio, FM radio,
televisions, satellite communications, and cell phones
Specific frequencies within these bands are then allocated to
individual organizations for use within certain geographical areas.
Finally, there are several frequency bands set aside for “license
exempt” usage
 Bands in which a license is not needed
19
 Wireless Links
The second restriction requires the use of Spread
Spectrum technique
Idea is to spread the signal over a wider frequency band
 So as to minimize the impact of interference from other devices
 Originally designed for military use
Frequency hopping
Transmitting signal over a random sequence of frequencies
First transmitting at one frequency, then a second, then a third…
The sequence of frequencies is not truly random, instead computed
algorithmically by a pseudorandom number generator
The receiver uses the same algorithm as the sender, initializes it with
the same seed, and is
 Able to hop frequencies in sync with the transmitter to correctly receive
the frame

20
 Wireless Links
 A second spread spectrum technique called Direct sequence
 Represents each bit in the frame by multiple bits in the transmitted signal.
 For each bit the sender wants to transmit
 It actually sends the exclusive OR of that bit and n random bits
 The sequence of random bits is generated by a pseudorandom number
generator known to both the sender and the receiver.
 The transmitted values, known as an n-bit chipping code, spread the
signal across a frequency band that is n times wider

Example 4-bit chipping sequence

21
 Wireless Links
 Wireless technologies differ in a variety of dimensions
 How much bandwidth they provide
 How far apart the communication nodes can be
 Four prominent wireless technologies: Bluetooth, Wi-Fi (more formally
known as 802.11), WiMAX (802.16), 3G cellular wireless

Overview of leading wireless technologies

22
 Wireless Links
 Mostly widely used
wireless links today
are usually
asymmetric
 Two end-points are
usually different kinds
of nodes
 One end-point usually
has no mobility, but
has wired connection
to the Internet
(known as base
station)
 The node at the other
end of the link is often A wireless network using a base station
mobile

23
 Wireless Links
 Wireless communication supports point-to-multipoint communication
 Communication between non-base (client) nodes is routed via the base
station
 Three levels of mobility for clients
 No mobility: the receiver must be in a fix location to receive a directional
transmission from the base station (initial version of WiMAX)
 Mobility is within the range of a base (Bluetooth)
 Mobility between bases (Cell phones and Wi-Fi)
 Mesh or Ad-hoc network
 Messages may be forwarded via a chain of peer nodes
 Nodes are peers

24
 IEEE 802.11
 Also known as Wi-Fi
 Like its Ethernet and token ring siblings, 802.11 is designed for use
in a limited geographical area (homes, office buildings, campuses)
 Primary challenge is to mediate access to a shared communication medium –
in this case, signals propagating through space
 802.11 supports additional features
 power management and
 security mechanisms
 Original 802.11 standard defined two radio-based physical layer standard
 One using the frequency hopping
 Over 79 1-MHz-wide frequency bandwidths
 Second using direct sequence
 Using 11-bit chipping sequence
 Both standards run in the 2.4-GHz and provide up to 2 Mbps

25
 IEEE 802.11
Then physical layer standard 802.11b was added
Using a variant of direct sequence 802.11b provides up to
11 Mbps
Uses license-exempt 2.4-GHz band
Then came 802.11a which delivers up to 54 Mbps
using OFDM
802.11a runs on license-exempt 5-GHz band
Most recent standard is 802.11g which is backward
compatible with 802.11b
Uses 2.4 GHz band, OFDM and delivers up to 54 Mbps

26
 IEEE 802.11 – Collision Avoidance
 Consider the situation in the following figure where each of four
nodes is able to send and receive signals that reach just the nodes to
its immediate left and right
 For example, B can exchange frames with A and C, but it cannot reach D
 C can reach B and D but not A

Example of a wireless network

27
 IEEE 802.11 – Collision Avoidance
 Suppose both A and C want
to communicate with B and
so they each send it a frame.
 A and C are unaware of each
other since their signals do not
carry that far
 These two frames collide with
each other at B
 But unlike an Ethernet,
neither A nor C is aware of The “Hidden Node” Problem. Although
this collision A and C are hidden from each
other, their signals can collide at B. (B’s
 A and C are said to hidden
reach is not shown.)
nodes with respect to each
other

28
 IEEE 802.11 – Collision Avoidance
 Another problem called exposed
node problem occurs
 Suppose B is sending to A. Node
C is aware of this communication
because it hears B’s transmission.
 It would be a mistake for C to
conclude that it cannot transmit to
anyone just because it can hear B’s
transmission.
 Suppose C wants to transmit to
node D. Exposed Node Problem. Although B and
C are exposed to each other’s signals,
 This is not a problem since C’s
there is no interference if B transmits to A
transmission to D will not interfere while C transmits to D. (A and D’s reaches
with A’s ability to receive from B. are not shown.)

29
 IEEE 802.11 – Collision Avoidance
802.11 addresses these two problems with an algorithm
called Multiple Access with Collision Avoidance (MACA).
Key Idea
Sender and receiver exchange control frames with each other
before the sender actually transmits any data.
This exchange informs all nearby nodes that a transmission is
about to begin
Sender transmits a Request to Send (RTS) frame to the receiver.
The RTS frame includes a field that indicates how long the sender wants to
hold the medium
 - Length of the data frame to be transmitted
Receiver replies with a Clear to Send (CTS) frame
This frame echoes this length field back to the sender

30
 IEEE 802.11 – Collision Avoidance
Any node that sees the CTS frame knows that
it is close to the receiver, therefore
cannot transmit for the period of time it takes to
send a frame of the specified length
Any node that sees the RTS frame but not the
CTS frame
is not close enough to the receiver to interfere with
it, and
so is free to transmit

31
 IEEE 802.11 – Collision Avoidance
 Using ACK in MACA
 Proposed in MACAW: MACA for Wireless LANs
 Receiver sends an ACK to the sender after successfully receiving a
frame
 All nodes must wait for this ACK before trying to transmit
 If two or more nodes detect an idle link and try to transmit an RTS
frame at the same time
 Their RTS frame will collide with each other
 802.11 does not support collision detection
 So the senders realize the collision has happened when they do not receive the
CTS frame after a period of time
 In this case, they each wait a random amount of time before trying again.
 The amount of time a given node delays is defined by the same exponential
backoff algorithm used on the Ethernet.

32
 IEEE 802.11 – Distribution System
802.11 is suitable for an ad-hoc configuration of nodes that
may or may not be able to communicate with all other
nodes.
Nodes are free to move around
The set of directly reachable nodes may change over time
To deal with this mobility and partial connectivity,
802.11 defines additional structures on a set of nodes
Instead of all nodes being created equal,
some nodes are allowed to roam
 some are connected to a wired network infrastructure
 they are called Access Points (AP) and they are connected to each other by a
so-called distribution system

33
 IEEE 802.11 – Distribution System
 Following figure illustrates a distribution system that connects three access points,
each of which services the nodes in the same region
 Each of these regions is analogous to a cell in a cellular phone system with the
APIs playing the same role as a base station
 The distribution network runs at layer 2 of the ISO architecture
 Although two nodes can communicate directly with each other if they are within
reach of each other, the idea behind this configuration is
 Each nodes associates itself with one access point
 For node A to communicate with node E, A first sends a frame to its AP-1 which
forwards the frame across the distribution system to AP-3, which finally transmits the
frame to E

Access points connected

to a distribution network

34
 IEEE 802.11 – Distribution System
 How do the nodes select their access points
 How does it work when nodes move from one cell to another
 The technique for selecting an AP is called scanning
 The node sends a Probe frame
 All APs within reach reply with a Probe Response frame
 The node selects one of the access points and sends that AP an Association
Request frame
 The AP replies with an Association Response frame
 A node engages this protocol whenever
 it joins the network, as well as
 when it becomes unhappy with its current AP
 This might happen, for example, because the signal from its current AP has
weakened due to the node moving away from it
 Whenever a node acquires a new AP, the new AP notifies the old AP of the
change via the distribution system

35
 IEEE 802.11 – Distribution System
 Consider the situation shown in the following figure when node C moves from the
cell serviced by AP-1 to the cell serviced by AP-2.
 As it moves, it sends Probe frames, which eventually result in Probe Responses
fromAP-2.
 At some point, C prefers AP-2 over AP-1 , and so it associates itself with that
access point.
 This is called active scanning since the node is actively searching for an access point
 APs also periodically send a Beacon frame that advertises the capabilities of the
access point; these include the transmission rate supported by the AP
 This is called passive scanning
 A node can change to this AP based on the Beacon frame simply by sending it an
Association Request frame back to the access point.

Node Mobility

36
 IEEE 802.11 – Frame Format
Source and Destinations addresses: each 48 bits
Data: up to 2312 bytes
CRC: 32 bit
Control field: 16 bits
Contains three subfields (of interest)
6 bit Type field: indicates whether the frame is an RTS or CTS frame or
being used by the scanning algorithm
A pair of 1 bit fields : called ToDS and FromDS

Frame Format

37
 IEEE 802.11 – Frame Format
 Frame contains four addresses
 How these addresses are interpreted depends on the settings of
the ToDS and FromDS bits in the frame’s Control field
 This is to account for the possibility that the frame had to be
forwarded across the distribution system which would mean
that,
 the original sender is not necessarily the same as the most recent
transmitting node
 Same is true for the destination address
 Simplest case
 When one node is sending directly to another, both the DS bits are 0,
Addr1 identifies the target node, and Addr2 identifies the source node

38
 IEEE 802.11 – Frame Format
Most complex case
Both DS bits are set to 1
Indicates that the message went from a wireless node onto the
distribution system, and then from the distribution system to
another wireless node
With both bits set,
Addr1 identifies the ultimate destination,
Addr2 identifies the immediate sender (the one that forwarded the
frame from the distribution system to the ultimate destination)
Addr3 identifies the intermediate destination (the one that accepted
the frame from a wireless node and forwarded across the
distribution system)
Addr4 identifies the original source
Addr1: E, Addr2: AP-3, Addr3: AP-1, Addr4: A

39
 Bluetooth
 Used for very short range
communication between mobile
phones, PDAs, notebook
computers and other personal or
peripheral devices
 Operates in the license-exempt
band at 2.45 GHz
 Has a range of only 10 m
 Communication devices
typically belong to one
individual or group
 Sometimes categorized as Personal
Area Network (PAN) A Bluetooth Piconet

40
 Bluetooth
 Version 2.0 provides speeds up to 2.1 Mbps
 Power consumption is low
 Bluetooth is specified by an industry consortium called the
Bluetooth Special Interest Group
 It specifies an entire suite of protocols, going beyond the link layer
to define application protocols, which it calls profiles, for a range of
applications
 There is a profile for synchronizing a PDA with personal computer
 Another profile gives a mobile computer access to a wired LAN
 The basic Bluetooth network configuration is called a piconet
 Consists of a master device and up to seven slave devices
 Any communication is between the master and a slave
 The slaves do not communicate directly with each other
 A slave can be parked: set to an inactive, low-power state
41
 ZigBee
ZigBee is a new technology that competes with
Bluetooth
Devised by the ZigBee alliance and standardized as IEEE
802.15.4
It is designed for situations where the bandwidth
requirements are low and power consumption must be
very low to give very long battery life
It is also intended to be simpler and cheaper than
Bluetooth, making it financially feasible to incorporate in
cheaper devices such as a wall switch that wirelessly
communicates with a ceiling-mounted fan

42
 Switching and Forwarding
Switch
A mechanism that allows us to
interconnect links to form a
large network
A multi-input, multi-output
device which transfers packets
from an input to one or more
outputs
A switch is connected to a set of
links and for each of these links,
Adds the star topology
runs the appropriate data link
protocol to communicate with to the links
that node

43
 Switching and Forwarding
 A switch’s primary job is to receive incoming packets on one of its
links and to transmit them on some other link
This function is referred as switching or forwarding
According to OSI architecture this is the main function of the
network layer
 How does the switch decide which output port to place each packet
on?
It looks at the header of the packet for an identifier that it uses to
make the decision
Two common approaches
Datagram or Connectionless approach
Virtual circuit or Connection-oriented approach
A third approach source routing is less common
44
 Switching and Forwarding
 Datagrams
Key Idea
Every packet contains
enough information to
Dest Port
-------------------
enable any switch to decide
A 3 how to get it to destination
B 0 Every packet contains
C 3
D 3
the complete
E 2 destination address
F 1  To decide how to forward a
G 0
H 0
packet, a switch consults a
Forwarding Table forwarding table (sometimes
for Switch 2 An example network called a routing table)

45
 Switching and Forwarding
 Characteristics of Connectionless (Datagram) Network
 A host can send a packet anywhere at any time, since any packet that turns
up at the switch can be immediately forwarded using the forwarding table
 When a host sends a packet, it does NOT know if the network is capable
of delivering it or if the destination host is even up and running
 Each packet is forwarded independently of previous packets that might
have been sent to the same destination.
Thus two successive packets from host A to host B may follow
completely different paths
 A switch or link failure might not have any serious effect on
communication if it is possible to find an alternate route around the failure
and update the forwarding table accordingly
 Virtual Circuit Switching (connection-oriented)
 Uses the concept of virtual circuit (VC)
 First set up a virtual connection from the source host to the destination host
and then send the data
46
 Switching and Forwarding
Two-stage process
Connection setup
Data Transfer
Host A wants to send
packets to host B
Connection setup
Establish “connection state” in each of the switches
between the source and destination hosts
The connection state for a single connection consists of an
entry in the “VC table” in each switch through which the
connection passes
47
 Switching and Forwarding
 Characteristics of VC
 Since host A has to wait for the connection request to reach the far side of the network
and return before it can send its first data packet, there is at least one RTT of delay
before data is sent
 While the connection request contains the full address for host B (which might be quite
large, being a global identifier on the network), each data packet contains only a small
identifier, which is only unique on one link.
 Thus the per-packet overhead caused by the header is reduced relative to the datagram model
 If a switch or a link in a connection fails, the connection is broken and a new one will
need to be established.
 Also the old one needs to be torn down to free up table storage space in the switches
 The issue of how a switch decides which link to forward the connection request on has
similarities with the function of a routing algorithm
 Comparison with the Datagram Model
 Datagram network has no connection establishment phase and each switch processes
each packet independently
 Each arriving packet competes with all other packets for buffer space
 If there are no buffers, the incoming packet must be dropped

48
 Switching and Forwarding
 Good Properties of VC
 By the time the host gets the go-ahead to send data, it knows quite a lot about the
network-
 For example, that there is really a route to the receiver and that the receiver is
willing to receive data
 It is also possible to allocate resources to the virtual circuit at the time it is established
 X.25 network ( an early virtual-circuit-based networking technology but now
largely obsolete) allocates buffers per VC
 In VC, we could imagine providing each circuit with a different quality of service (QoS)
 The network gives the user some kind of performance related guarantee
 Switches set aside the resources they need to meet this guarantee
 For example, a percentage of each outgoing link’s bandwidth
 Delay tolerance on each switch
 Most popular examples of VC technologies are X.25, Frame Relay and ATM
 However, with the success of the Internet’s connection-less model, none of them enjoys
great popularity today

49
 Switching and Forwarding
 ATM (Asynchronous Transfer Mode)
 Most well-known VC-based networking technology
 Somewhat pasts its peak in terms of deployment
 Was important in the 1980s and early 1990s
 High-speed switching technology
 Was thought of to take over the world
 Connection-oriented packet-switched network
 Packets are called cells
 5 byte header + 48 byte payload
 Fixed length packets are easier to switch in hardware
 Simpler to design
 ATM
 GFC: Generic Flow Control (not used) VPI: Virtual Path Identifier
 VCI: Virtual Circuit Identifier CLP: Cell Loss Priority
 (VPI + VCI together makes the VC number we talked about)
 Type: management, congestion control HEC: Header Error Check (CRC-8)

50
 Switching and Forwarding
 Source Routing
 All the information about network topology that is
required to switch a packet across the network is
provided by the source host
 Notes on Source Routing
Assumes that the source host knows
enough about the topology of the network
 Analogous the problem of building the
forwarding tables in datagram networks or
figuring out where to send a setup packet in a virtual
circuit network
 We can not predict how the header needs to be (# of
switches in the path)
 Can be used in both datagram and virtual circuit
networks
 For example, IP, which is a datagram protocol includes a
source route option that allows selected packets to be
source routed.

51
 Bridges and LAN Switches
 Bridges and LAN Switches
 Class of switches that is used to forward packets between shared-media LANs such as
Ethernets
 Known as LAN switches
 Referred to as Bridges
 Suppose you have a pair of Ethernets that you want to interconnect
 One approach is put a repeater in between them
 It might exceed the physical limitation of the Ethernet
 No more than four repeaters between any pair of hosts
 No more than a total of 2500 m in length is allowed
 An alternative would be to put a node between the two Ethernets and have the node forward
frames from one Ethernet to the other
 This node is called a Bridge
 A collection of LANs connected by one or more bridges is usually said to form an Extended LAN
 Simplest Strategy for Bridges
 Accept LAN frames on their inputs and forward them out to all other outputs
 Used by early bridges
 Learning Bridges
 Observe that there is no need to forward all the frames that a bridge receives
52
 Bridges and LAN Switches
 Consider the following figure
 When a frame from host A that is addressed to host B arrives on port 1, there
is no need for the bridge to forward the frame out over port 2. Host Port
--------------------
A 1
B 1
C 1
X 2
Y 2
Z 2
 How does a bridge come to learn on which port the various hosts reside?
 Solution
 Download a table into the bridge
 Who does the download?
 Human
 Too much work for maintenance

53
 Bridges and LAN Switches
 Can the bridge learn this information by itself?
 Yes
 How
 Each bridge inspects the source address in all the frames it receives
 Record the information at the bridge and build the table
 When a bridge first boots, this table is empty
 Entries are added over time
 A timeout is associated with each entry
 The bridge discards the entry after a specified period of time
To protect against the situation in which a host is moved from one network to
another
 If the bridge receives a frame that is addressed to host not
currently in the table
 Forward the frame out on all other ports

54
 Bridges and LAN Switches
 Strategy works fine if the extended LAN does not have a loop
in it
 Why?
Frames potentially loop through the extended LAN forever

Bridges B1, B4, and B6 form a loop

55
 Bridges and LAN Switches
How does an extended LAN come to have a loop in it?
Network is managed by more than one administrator
For example, it spans multiple departments in an
organization
It is possible that no single person knows the entire
configuration of the network
A bridge that closes a loop might be added without anyone knowing
Loops are built into the network to provide
redundancy in case of failures
Solution
Distributed Spanning Tree Algorithm
56
 Spanning Tree Algorithm
 Think of the extended LAN as being represented by a graph that
possibly has loops (cycles)
 A spanning tree is a sub-graph of this graph that covers all the
vertices but contains no cycles
Spanning tree keeps all the vertices of the original graph but
throws out some of the edges

Example of (a) a cyclic graph; (b) a corresponding spanning tree.

57
 Spanning Tree Algorithm
 Developed by Radia Perlman at Digital
A protocol used by a set of bridges to agree upon a spanning
tree for a particular extended LAN
IEEE 802.1 specification for LAN bridges is based on this
algorithm
Each bridge decides the ports over which it is and is not willing
to forward frames
In a sense the extended LAN is reduced to an acyclic tree
Details are NOT required for the exam purposes
Take point: Spanning Tree Algorithm removes the cycles/loops
from the extended (bridged) LANs

58
 Limitation of Bridges
Do not scale
 Spanning tree algorithm does not scale
 Broadcast does not scale
Nodes get bothered with too many broadcasts that the
bridges forward to ALL nodes
Do not accommodate heterogeneity
Ethernet with Ethernet, Wi-Fi with Wi-Fi, etc.
A solution
Virtual LAN (VLAN)

59
 Virtual LANs (VLANs)
Allow a single extended LAN to be partitioned into
several logical LANs
Each VLAN is assigned an ID (or color)
Frames can only be travel between LANs segments
within the same VLAN
Partially solves the broadcast problem in the extended
LAN
One Attractive feature of VLANs is
We can change the logical topology of the extended
LAN without moving/changing any wire or addresses
Just change the Bridge configuration

60
 Virtual LANs (VLANs)
 When a frame from X arrives at bridge B2, the bridge observes that
it came in a port that was configured as being in VLAN 100, so it
inserts a VLAN header (has the VLAN ID) between the Ethernet
header and its payload
 When the frame arrives at B1, it will only forward it to the port of
VLAN 100 and not to VLAN 200
 The link between B1 and B2 is considered to be in both VLANs

61
 Internetworking
 What is internetwork
 An arbitrary collection of networks interconnected to provide some sort of
host-to-host packet delivery service

 A simple internetwork where H represents hosts and R represents routers

62
 Internetworking
 What is IP
 IP stands for Internet Protocol
 Key tool used today to build scalable, heterogeneous internetworks
 It runs on all the nodes in a collection of networks and defines the
infrastructure that allows these nodes and networks to function as a single
logical internetwork

 A simple internetwork showing the protocol layers

63
 IP Service Model
Two parts
Global Addressing Scheme
Provides a way to identify all hosts in the network
Datagram (Connectionless) model for data delivery
Best-effort delivery (unreliable service)
packets are lost
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time

64
 Packet Format
 Version (4 bits):
 currently 4 or 6.
 Also called IPv4 and IPv6
 Hlen (4 bits):
 number of 32-bit words in header
 usually 5 32-bit words with no options
 TOS (8 bits):
 type of service (not widely used)
 Length (16 bits):
 number of bytes in this datagram including the
header
 Ident (16 bits) and Flags/Offset (16 bits):
 used by fragmentation
 Protocol (8 bits):
 demux key (TCP=6, UDP=17)
 Checksum (16 bits):
 of the header only
65
 Packet Format
 TTL (8 bits):
 number of hops/routers this packet can travel
 discard the looping packets
 Originally based on time, but changed to a hop-count based
 Each router decrements it by 1
 Discard the packet when it becomes 0
 Default is 64
 Problems
 Setting it too high the packet will loop a lot
 Setting it too low the packet will not reach the destination
 DestAddr & SrcAddr (32 bits)
 The key for datagram delivery
 Every packet contains a full destination address
 Forwarding/routing decisions are made at each router
 The source address is for the destination to know the sender and if it wants
to reply to it

66
 IP Fragmentation and Reassembly
Each network has some MTU (Maximum Transmission
Unit)
Ethernet (1500 bytes), FDDI (4500 bytes)
IP packets need to fit in the payload of link-layer frame
Solutions
Make all packet size small enough to fit all
Or fragment the large packets into smaller ones and reassembles them
later
Strategy
Fragmentation occurs in a router when it receives a datagram that
it wants to forward over a network which has (MTU < datagram)
Reassembly is done at the receiving host
All the fragments carry the same identifier in the Ident field
Fragments are self-contained datagrams

67
 IP Fragmentation and Reassembly
Suppose PPP has MTU of 532-byte packet (20 header +
512 payload)

IP datagrams traversing the sequence of physical networks

Header fields used in IP fragmentation.

(a) Unfragmented packet; (b) fragmented packets.

 MTU path discovery is a good strategy to avoid fragmentation

Send some packets first just discover the MTUs on the path to D
68
 Global Addresses
 IP addresses Properties
 globally unique
 hierarchical: network + host
 Network part: identifies the network the host is attached to
 Host: identifies a unique host on that network
 Ethernet addresses, even globally unique, are flat (no structure and thus no meaning) and can
not be use for routing
 Note that a router is attached to at least two networks, so it must have an IP
address on each port/interface
 Thus it is more precise to think of IP addresses as belonging to interfaces rather than to hosts

 Approximately, 4 Billion IP address,

half are A type, ¼ is B type, and 1/8 is C type

(a) Class A (b) Class B (c) Class C

69
 Global Addresses
 Class A was intended for Wide Area Networks
 Thus there should a very few of them
 Class B was intended for a modest size networks (like a campus)
 Class C is for the large number of LANs
 However, these classifications are not flexible and today’s IP
addresses are normally “classless” as we will see
 Format
 4 bytes, each byte is represented by a decimal number
 Dot notation
 10.3.2.4
 128.96.33.81
 192.12.69.77

70
 IP Datagram Forwarding
 Strategy
 every datagram contains destination's address
 if directly connected to destination network, then forward to host
 if not directly connected to destination network, then forward to some router
 forwarding table maps network number into next hop
 each host has a default router
 each router maintains a forwarding table
 Example (router R2)
Algorithm
if (NetworkNum of destination = NetworkNum of one of my interfaces) then
deliver packet to destination over that interface
else
if (NetworkNum of destination is in my forwarding table) then
deliver packet to NextHop router
else
deliver packet to default router
For a host with only one interface and only a default router in its forwarding table, this simplifies to
if (NetworkNum of destination = my NetworkNum)then
deliver packet to destination directly
else
deliver packet to default router

71
 Subnetting
 The network number part was designed to uniquely identify exactly one physical network
 However, this approach has some problems
 A network with only 2 hosts has to have at least a class C network!!
 A network with only 256 hosts has to have at least a class B network!!
 Thus, we will waste our valuable IP address space
 Solution: Subnetting
 Key Idea
 Allocate a single network number and use it for several physical networks - subnets
 Several things need to be done
 Subnets need to be physically close to each other
 From the Internet point of view, they all look ONE network
 A perfect situation to use subnetting is for large campus or corporation
 Configure all nodes on each subnet with a subnet mask
 It masks the network part
 Introduces the subnet number
 All nodes on the same subnet have the same subnet number and the same mask
 The IP address of a nodes ANDed with the subnet mask give the subnet number
 IP AND subnet mask  subnet number

72
 Subnetting
 When a host wants to send a packet to a certain IP address
 First, it does the bitwise AND between its own subnet mast and destination IP address
 If the result equals the subnet number of the sender, then the destination host is on the same
subnet so the packet can be delivered directly (without a router)
 Else, the packet will be forwarded to another subnet (through a router)

Increases the number of

networks and reduces the
number of hosts

73
 Subnetting

Forwarding Table at Router R1

Forwarding Algorithm
D = destination IP address
for each entry < SubnetNum, SubnetMask, NextHop>
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to destination
else
deliver datagram to NextHop (a router)
74
 Classless Addressing
 Subnetting has a counterpart, sometimes called supernetting, but
often called Classless Interdomain Routing, CIDR (pronounced
cider)
 Address assignment efficiency
 A network with 256 hosts needs a class B address
 Address assignment efficiency = 256/65535 = 0.39
 Solutions
 Use subnetting
 Only give class C networks
 Give class B only with a proof of that the network has more than 64K hosts

Problem with this solution

Excessive storage requirement at the routers.

75
 Classless Addressing
 If a single site has, say 16 class C network numbers assigned to it,
 Every Internet backbone router needs 16 entries in its routing tables
for that site (too much for one site)
 This is true, even if the path to every one of these networks is the same
 If we had assigned a class B address to the AS
 The same routing information can be stored in one entry
Efficiency = number of hosts / number of available addresses =16
255 / 65, 536 = 6.2% (not efficient)
 CIDR tries to balance the desire to minimize the number of routes that a
router needs to know against the need to hand out addresses efficiently.
 CIDR uses aggregate routes
 Uses a single entry in the forwarding table to tell the router how to
reach a lot of different networks
 Breaks the rigid boundaries between address classes

76
 Classless Addressing
 Consider a site with 16 class C network numbers.
 Instead of handing out 16 addresses at random, hand out a block of
contiguous class C addresses
 Suppose we assign the class C network numbers from 192.4.16
through 192.4.31
 Observe that top 20 bits of all the addresses in this range are the
same (11000000 00000100 0001)
 We have created a 20-bit network number (which is in between class B
network number and class C number)
 Requires to hand out blocks of class C addresses that share a
common prefix
 The convention is to place a /X after the prefix where X is the prefix
length in bits

77
 Classless Addressing
 For example, the 20-bit prefix for all the networks 192.4.16
through 192.4.31 is represented as 192.4.16/20
 By contrast, if we wanted to represent a single class C network
number, which is 24 bits long, we would write it 192.4.16/24

Route aggregation with CIDR

78
 Different Protocols

ARP (Address Resolution Protocol)

DHCP (Dynamic Host Configuration
Protocol)
ICMP (Internet Control Message
Protocol)

79
 Address Translation Protocol (ARP)
Map IP addresses into physical addresses
ARP (Address Resolution Protocol)
table of IP to physical address bindings
The router broadcasts a request (who-has / tell)
if the required IP address not in the ARP table
Ex., who-has 192.168.0.29 tell 192.168.0.1
target machine (with IP 192.168.0.29 in the
example) responds with its physical address (its
MAC)
80
 Host IP Configurations
Most host Operating Systems provide a way to
manually configure the IP information for the
host
Drawbacks of manual configuration
A lot of work to configure all the hosts in a large
network
Configuration process is error-prune
Automated Configuration Process is required
Using the DHCP protocol

81
Dynamic Host Configuration Protocol
 DHCP server is responsible for providing configuration
information to hosts
 There is at least one DHCP server for an administrative domain
 DHCP server maintains a pool/set of available addresses
 Newly booted or attached host sends DHCPDISCOVER message
to a special IP address (255.255.255.255)
 DHCP relay agent unicasts the message to DHCP server and waits
for the response

82
 Internet Control Message Protocol
Defines a collection of error messages that are
sent back to the source host whenever a router or
host is unable to process an IP datagram
successfully
Destination host unreachable due to link /node failure
Reassembly process failed
TTL had reached 0 (so datagrams don't cycle forever)
IP header checksum failed
ICMP-Redirect
From router to a source host
With a better route information

83
 Routing
Forwarding versus Routing
 Forwarding:
 to select an output port based on destination address and routing
table
 Routing:
 routing table is built
 Network as a Graph

 The basic problem of routing is to find the lowest-cost path between any two
nodes
Where the cost of a path equals the sum of the costs of all the edges that
make up the path

84
 Routing
• For a simple network, we can calculate all shortest paths and
load them into some nonvolatile storage on each node.
• Such a static approach has several shortcomings
• It does not deal with node or link failures
• It does not consider the addition of new nodes or links
• It implies that edge costs cannot change
• What is the solution?
• Need a distributed and dynamic protocol
• Two main classes of protocols
• Distance Vector
Details are not required for
• Link State the exam purposes

85
Questions?