Transcript Document

Networking in Linux
Aditya Dev Nayar
Avanish Kushal
Mayank Kukreja
Ravi Gupta
Definitions
TCP/IP : The set of all the protocols used
to transfer data from one computer to the
other.
TCP/IP stack: The function layers
(stacked on top of each other) used to
categorize the functions performed by the
communication protocols.
DOD reference model
TCP/IP Stack
➢
➢
➢
Process of data transfer
Every protocol communicates with its
peer
Headers and trailers
Structure of packet
Note: Data structure for the layers are
compatible for the sake of efficiency and
avoid copying.
Network Access Layer
➢
➢
➢
Transmission of a frame(packet)
Details of underlying physical network
Adds the suitable header and trailer
Internetwork layer
➢
➢
➢
Send the data across different networks
Adds the suitable header and the trailer
No or minimal checks for errors and
retransmits
Host to host transport layer
➢
➢
➢
Formation of a connection is possible
Checks for errors can be done
The delivery of the data packet can be
ensured
Application Layer
➢
➢
Interacts with the users
Implements the encryption and
decryption techniques for data
OSI model
IP protocol
➢
➢
➢
➢
➢
➢
Protocol at internetwork layer
Define the datagram, which is the basic
of transmission in the Internet.
Define the Internet addressing scheme
Move data between the Network Access
Layer and the Host-to-Host Transport
Layer.
Route datagrams to remote hosts
Fragment and reassemble datagrams
TCP and UDP protocols
TCP:
 Reliable and full-duplex connections
 Reliable service
UDP:
 Stateless transmission
 Minimum protocol overhead
 High speed
SOCKETS



Definition: A socket is a software
construction representing a single
connection between two networking
applications.
IP information at connection time :
ip_route_connect()
Adv : No need to do continuous routing
table look-ups
Socket Structures
There are two main socket structures in Linux: general BSD
sockets and IP specific INET sockets
BSD SOCKETS
•struct sock *sk
•struct proto_ops *ops
INET SOCKETS
•struct sk_buff_head (receive/write)_queue
•__u32 saddr
•struct proto *prot
Establishing Connections



Server = gethostbyname(SERVER_NAME)
sockfd = socket(AF_INET,SOCK_STREAM,
0);
connect(sockfd, &address,sizeof(address));
Socket Call Walk-Through







Check for errors in call
Create (allocate memory for) socket object
Put socket into INODE list
Establish pointers to protocol functions
(INET)
Store values for socket type and protocol
family
Set socket state to closed
Initialize packet queues
Connect Call Walk-Through





Check for errors
Determine route to destination:
Store pointer to routing entry in socket
Call protocol specific connection
function (e.g., send a TCP connection
packet)
Set socket state to established
Close Walk-Through





Check for errors
Change the socket state to
disconnecting
Do any protocol closing actions
Free memory for socket data
structures (TCP/UDP and INET)
Remove socket from INODE list
Sending Messages
Receiving Message
Address Resolution
Protocol


Problem: Given an IP address find the
MAC address
Solution 1. Table Lookup:
Searching or indexing to get MAC
address.
ARP (contd.)
2. Closed-Form Computation: Using local IEEE 802
– addresses, e.g., Hardware Address = (IP_address & 0xFF)
!40:00:00:00:00:00
3. Message Exchange: ARP
– The host broadcasts a request: “What is the MAC address
of 127.123.115.08?”
– The host whose IP address is 127.123.115.08
replies back: “The MAC address for
“127.123.115.08 is 8A-5F-3C-23-45-5616”
All three methods are allowed in TCP/IP networks.
Message format
Caching


ARP responses are cached.
Entry replaced when



Cache table fills up (oldest removed)
After some time, e.g., 20 minutes
Sender’s address binding is stored in
the cache of the target
Proxy & Reverse ARP

Proxy ARP: A router may act as a
proxy for many IP addresses

Reverse ARP : What is the IP address
of a given hardware address?
Used by diskless systems for their IP
Need RARP server to respond.
Routing
 Routing :The process of choosing a
path over which to send packets.
 Routing occurs at a TCP/IP host when it sends IP
packets, and occurs again at an IP router.
 Router : A device that forwards the
packets from one physical network to
another.
 Routers are commonly referred to as gateways.
A Walk Through




When a host attempts communication with another host,
IP first determines whether the destination host is local or
on a remote network
If the destination host is remote, IP then checks the
routing table for a route to the remote host or remote
network.
If no explicit route is found, IP uses its default gateway
address to deliver the packet to a router
At the router, the routing table is again consulted for a
path to the remote host or network. If a path is not found,
the packet is sent to the router's default gateway address
The Details
Linux maintains 3 sets of Routing Data
1.
Neighbour Table – Directly connected
computers.
2.
3.
FIB Table – All other networks/computers.
Routing Cache – Cache for FIB.
Neighbour Table
• struct neigh_table : Contains common neighbour
information.All computers connected by same type of
connection are in same table.
• struct neighbour : specific info about a
neighbour like device which is connected to the
neighbour, various flags regarding connection .
• struct neigh_parms : contains message travel
time, queue length and other statistical information.
Forwarding Information Base (FIB)
FIB is a structure containing
routing information for any valid
IP address.
An exhaustive list of known IP
destinations and their best routes.



Complex Data structure.
Slow access.
Forwarding Information Base
(FIB)



Each IP subnet is represented by a
fib_zone data structure
All of these are pointed at from the
fib_zones hash table. The hash index
is derived from the IP subnet mask.
Routes to the same subnet described
by pairs of fib_node and fib_info data
Route Cache




Keeps every route that is currently in use or has
been used recently in a hash table.
The index into the route table is a hash function
based on the least significant two bytes of the IP
address.
If route not in cache, FIB looked up and a new
entry made in route cache.
Routes chained in order of most frequently used
first. Removed when old.
Routing Cache…conceptual
organization
Routing Information Protocol
(RIP)
RIP : Protocol for
routers to
track distance to
different
networks and to
share this
information
among
themselves.
RIP contd..




At startup, information from all
neighbouring routers is requested.
A received packet can be a 'response'
or a 'request'.
A response is sent to all neighbours
every 30 sec.
Listens on UDP socket 520 for
incoming packets.
CSMA/CD Technology
Requirement




Ethernet network provides shared
access to a group of attached nodes
Each node has a NIC (Network
Interface Card)
The shared cable allows any NIC to
send whenever it wishes
But if two NICs happen to transmit at
the same time, a collision will occur,
resulting in the data being corrupted
1.
Source NIC
dispatches frame
2.
Frame transmits in
both directions
3.
Every NIC receives
the frame; do MAC
address matching
4.
Intended NIC picks
up the frame; rest
drop it
CSMA/CD Algorithm


Sense for carrier.
If carrier present, wait until carrier ends.
– Sending would force a collision and waste time


Send packet and sense for collision.
If no collision detected, consider packet
delivered.
CSMA/CD Algorithm




Otherwise if collision detected
Send Jam Signal
Abort immediately
Perform “exponential back off” and send
packet again.
– Start to send at a random time picked from an
interval
– Length of the interval increases with every
retransmission
Collision Detection
Time
A
B
C
Collision Detection:
Implications A
B

All nodes must be able to
detect the collision.
– Any node can be sender

The implication is that either
we must have a short wires, or
long packets.
– Or a combination of both

Can calculate length/distance
based on transmission rate and
propagation speed.
– Minimum packet size is 64 bytes

Cable length ~256 bit times
– Example: maximum coax cable
length is 2.5 km
C
CSMA/CD: Some Details

When a sender detects a collision, it sends a
“jam signal”.
– Make sure that all nodes are aware of the
collision
– Length of the jam signal is 32 bit times

Exponential backoff operates in multiples of
512 bit times.
– Longer than a roundtrip time
– Guarantees that nodes that back off longer will
notice the earlier retransmission before starting
to send
Ethernet Frame Format
8
6
6
2
Preamble
Dest
Source
Type

4
Data
Pad
Preamble marks the beginning of the frame.
– Also provides clock synchronization

Source and destination are 48 bit IEEE MAC addresses.
– Flat address space
– Hardwired into the network interface

Type field is a demultiplexing field.
– What network layer (layer 3) should receive this packet?
– Is actually a length field in the 802.3 standard

CRC for error checking.
CRC
Minimum Packet Size




Why put a minimum packet size?
Give a host enough time to detect
collisions
In Ethernet, minimum packet size = 64
bytes (two 6-byte addresses, 2-byte
type, 4-byte CRC, and 46 bytes of data)
If host has less than 46 bytes to send,
the adaptor pads (adds) bytes to make
it 46 bytes
Limited cable length

Limitation: Before the transmitted
packet is completely dispatched from
the sender, all other nodes on the local
network must at least start receiving
it. This assumption is required for the
“jam signal” protocol to work.
Drawbacks of CSMA/CD






Ethernet Capture
A has to send bigger file than B
A transmits first.
A and B then both simultaneously try to
transmit. B picks a larger retransmission
interval than A and defers.
A sends, then sends again.
Both A and B attempt to resume
transmission
Drawbacks of CSMA/CD


A and B both back-off, however, since B was
already in back-off (it failed to retransmit), it
chooses from a larger range of back-off
times (using the exponential back-off
algorithm).
A is therefore more likely to succeed, which
it does in the example. The next pause in
transmission, A and B both attempt to send,
however, since this fails in this case, B
further increases its back-off and is now
unable to fairly compete with A.
Performance of CSMA/CD

Only one transmitter
– Near 100% utilisation of network
– Possible to completely use 10Mbps

Many transmitting NICs
– Some bandwidth wasted in collision
detection
– Typical busy network gives 2-4 Mbps
References





http://en.wikipedia.org
http://www.erg.abdn.ac.uk
http://www.cisco.com
The linux kernel: David A Rusling
Linux IP Networking: Glenn Herrin