DATA LINKLAYER
1. INTERNETWORKING
An
arbitrary collection of networks interconnected to provide some sort of
host-host to packet delivery service
2. 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
IP
Service Model
·
Packet Delivery Model
o
Connectionless model for data delivery
o
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
·
Global Addressing Scheme
o
Provides a way to identify all hosts in the network
Packet Format
o
Version (4): currently 4
o
Hlen (4): number of 32-bit words in header
o
TOS (8): type of service (not widely used)
o
Length (16): number of bytes in this datagram
o
Ident (16): used by fragmentation
o
Flags/Offset (16): used by fragmentation
o
TTL (8): number of hops this datagram has traveled
o
Protocol (8): demux key (TCP=6, UDP=17)
o
Checksum (16): of the header only
DestAddr
& SrcAddr (3
IP Fragmentation and Reassembly
·
Each network has some MTU (Maximum Transmission
Unit)
o
Ethernet (1500 bytes), FDDI (4500 bytes)
·
Strategy
o
Fragmentation occurs in a router when it receives a
datagram that it wants to forward over a network which has (MTU < datagram)
o
Reassembly is done at the receiving host
o
All the fragments carry the same identifier in the
Ident field
o
Fragments are self-contained datagrams
o
IP does not recover from missing fragments
3. ARP
Address
Translation Protocol (ARP)
·
Map IP addresses into physical addresses
o
destination host
o
next hop router
·
Techniques
o
encode physical address in host part of IP address
o
table-based
·
ARP (Address Resolution Protocol)
o
table of IP to physical address bindings
o
broadcast request if IP address not in table
o
target machine responds with its physical address
table entries are discarded if not refreshed
o
HardwareType: type of physical network (e.g.,
Ethernet)
o
ProtocolType: type of higher layer protocol (e.g.,
IP)
o
HLEN & PLEN: length of physical and protocol
addresses
o
Operation: request or response
o
Source/Target Physical/Protocol addresses
o
Ethernet addresses are configured into network by
manufacturer and they are unique
o
IP addresses must be unique on a given internetwork
but also must reflect the structure of the internetwork
o
Most host Operating Systems provide a way to
manually configure the IP information for the host
o
Drawbacks of manual configuration
§ A lot of
work to configure all the hosts in a large network
§ Configuration
process is error-prune
o
Automated Configuration Process is required
4. REVERSE ADDRESS RESOLUTION PROTOCOL
·
(RARP) is a Link layer networking protocol
·
RARP is described in internet EngineeringTask
ForceETF) publication RFC 903
·
It has been rendered obsolete by the Bootstrap Protocol
(BOOTP) and the modern Dynamic Host Configuration Protocol(DHCP)
·
BOOTP configuration server assigns an IP address to
each client from a pool of addresses.
·
BOOTP uses the User Datagram Protocol (UDP)
5. DYNAMIC HOST CONFIGURATION PROTOCOL (DHCP)
n DHCP server is responsible for
providing configuration information to hosts
n There is
at least one DHCP server for an administrative domain
n DHCP server maintains a pool of
available addresses
n Newly
booted or attached host sends DHCPDISCOVER message to a special IP address
(255.255.255.255)
n DHCP relay agent unicasts the
message to DHCP server and waits for the response
6. INTERNET CONTROL MESSAGE PROTOCOL
o
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
o
ICMP-Redirect
§ From
router to a source host
§ With a
better route information
o
Forwarding versus Routing
– Forwarding:
– to select an output port based on destination
address and routing table
– Routing:
– process by which routing table is built
7. ROUTING
Forwarding versus Routing
– Forwarding:
– to select an output port based on destination
address and routing table
– Routing:
– process by which routing table is built
– Forwarding
table VS Routing table
– Forwarding table
– Used when a packet is being forwarded and so must
contain enough information to accomplish the forwarding function
– A row in the forwarding table contains the
mapping from a network number to an outgoing interface and some MAC
information, such as Ethernet Address of the next hop
– Routing table
– Built by the routing algorithm as a precursor to
build the forwarding table
– Generally contains mapping from network
numbers to next hops
– 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
– Need a distributed and dynamic protocol
– Two main classes of protocols
– Distance Vector
– Link State
8. ROUTING ALGORITHMS
Distance
Vector
o
Each
node constructs a
one dimensional array (a
vector) containing the “distances”
o
(costs) to all other nodes and distributes that
vector to its immediate neighbors
o
Starting assumption is that each node knows the
cost of the link to each of its directly connected neighbors
o
The distance vector routing algorithm is sometimes
called as Bellman-Ford algorithm
o
Every T seconds each router sends its table to its
neighbor each each router then updates its table based on the new information
o
Problems include fast response to good new and slow
response to bad news. Also too many messages to update
§ When a
node detects a link failure
·
F detects that link to G has failed
·
F sets distance to G to infinity and sends update
to A
·
A sets distance to G to infinity since it uses F to
reach G
·
A receives periodic update from C with 2-hop path
to G
·
A sets distance to G to 3 and sends update to F
·
F decides it can reach G in 4 hops via A
·
Slightly different circumstances can prevent the
network from stabilizing
§ Suppose
the link from A to E goes down
§ In the
next round of updates, A advertises a distance of infinity to E, but B and C
advertise a distance of 2 to E
§ Depending
on the exact timing of events, the following might happen
·
Node B, upon hearing that E can be reached in 2
hops from C, concludes that it can reach E in 3 hops and advertises this to A
·
Node A concludes that it can reach E in 4 hops and
advertises this to C
·
Node C concludes that it can reach E in 5 hops; and
so on.
·
This cycle stops only when the distances reach some
number that is large enough to be considered infinite
Count-to-infinity
problem
·
Use some relatively small number as an
approximation of infinity
·
For example, the maximum number of hops to get
across a certain network is never going to be more than 16
·
One technique to improve the time to stabilize
routing is called split horizon
o
When a node sends a routing update to its
neighbors, it does not send those routes it learned from each neighbor back to
that neighbor
o
For example, if B has the route (E, 2, A) in its
table, then it knows it must have learned this route from A, and so whenever B
sends a routing update to A, it does not include the route (E, 2) in that
update
·
In a stronger version of split horizon, called
split horizon with poison reverse
o
B actually sends that back route to A, but it puts
negative information in the route to ensure that A will not eventually use B to
get to E
o
For example, B sends the route (E, ∞) to A
Link
State Routing
Strategy: Send to all nodes (not just
neighbors) information about directly connected links (not entire routing table).
·
Link State Packet (LSP)
o
id of the node that created the LSP
o
cost of link to each directly connected neighbor
o
sequence number (SEQNO)
o
time-to-live (TTL) for this packet
·
Reliable Flooding
o
store most recent LSP from each node
o
forward LSP to all nodes but one that sent it
o
generate new LSP periodically; increment SEQNO
o
start SEQNO at 0 when reboot
o
decrement TTL of each stored LSP; discard when
TTL=0
9. ADDRESSING
Global
Addresses
o
Properties
§ globally
unique
§ hierarchical:
network + host
§ 4 Billion
IP address, half are A type, ¼ is B type, and 1/8 is C type
o
Format
o
Dot notation
§ 10.3.2.4
§ 128.96.33.81
·
192.12.69.77
IP
Datagram Forwarding
·
Strategy
o
every datagram contains destination's address
o
if directly connected to destination network, then
forward to host
o
if not directly connected to destination network,
then forward to some router
o
forwarding table maps network number into next hop
o
each host has a default router
o
each router maintains a forwarding table
Example (router R2)
n 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
10. CIDR
Classless Addressing
Classless Inter-Domain Routing
A technique that addresses two scaling concerns in
the Internet
The growth of backbone routing table as more and
more network numbers need to be stored in them
Potential exhaustion of the 32-bit address space
Address assignment efficiency
Arises because of the IP address structure with
class A, B, and C addresses
Forces us to hand out network address space in
fixed-size chunks of three very different sizes
A network with two hosts needs a class C address
Address assignment efficiency = 2/255 = 0.78
A network with 256 hosts needs a class B address
ADDRESS ASSIGNMENT EFFICIENCY = 256/65535 = 0.39
Problem with this solution
Excessive storage requirement at the routers.
If a single AS has, say 16 class C network numbers
assigned to it,
Every Internet backbone router needs 16 entries in
its routing tables for that AS
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 = 16 × 255 / 65, 536 = 6.2%
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
Consider an AS 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
11. SUBNETTING
Add
another level to address/routing hierarchy: subnet
Subnet
masks define variable partition of host part of class A and B addresses
Subnets
visible only within site 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)
Subnet
Addressing
Suppose
that the first two bytes are the subnet indicator with addresses of the form
131.156.x.x
Then,
131.156.29.156 and 131.156.34.215 would be on the same subnet.
The
subnet mask would be 255.255.0.0, which corresponds to
11111111.11111111.00000000.00000000, where 1 indicates that the position is
part of the subnet address and a 0 indicates that it is not.
Partial
bytes can also be used as subnets.
For
example, consider the subnet mask 255.255.255.128, which is
11111111.11111111.11111111.10000000.
Here, all
computers with the same first three bytes and last byte from 128 to 254 would
be on the same subnet.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.