Internet Protocol (IP) & Routing
Textbook: Ch.19, 20
SEHH2238 Computer Networking
SEHH2238 Lecture 8 1
Copyright By PowCoder代写 加微信 powcoder
Network Layer Functions
SEHH2238 Computer Networking
Internet Protocol (IP)
IP Datagram Format
IP Fragmentation
C. Routing
Routing Algorithms
Next-hop Routing Table
D. LAN Addressing
Main Topics
Address Resolution Protocol (ARP)
SEHH2238 Lecture 8 2
SEHH2238 Computer Networking
A. Network Layer Functions
SEHH2238 Lecture 8 3
SEHH2238 Computer Networking
Network Layer Functions
Creating a packet from the data coming from another protocol (usually the upper layer, TCP or UDP).
The header of packet contains the logical address (e.g. IP address) of the source and destination.
Identify the first routing information. (E.g. the address of next hop, such as default gateway.)
If the packet is too large, the packet is fragmented. (Similar to data size in the Ethernet)
SEHH2238 Lecture 8 4
SEHH2238 Computer Networking
Network Layer Functions
Router (or L3 Switch)
Routing the packet.
It looks up the routing table find the interface that the packet should be sent.
The packet is sent to data link layer with the appropriate port.
SEHH2238 Lecture 8 5
SEHH2238 Computer Networking
Network Layer Functions
Destination
Send the packet to the upper
It performs address verification to ensure that the destination address on the packet is the same as the address of the host.
If the packet is a fragment, it waits until all fragments have arrived and reassembles them.
SEHH2238 Lecture 8 6
SEHH2238 Computer Networking
A set of protocols, or protocol suite, that defines how all transmissions are exchanged across the Internet
TCP/IP is a five-layer protocol: physical, data link, network, transport and application
Transport layer: (2 protocols/services) Transmission Control Protocol (TCP) – data unit
is called TCP segment (VC service)
User Datagram Protocol (UDP) – data unit is
called user datagram (Datagram service)
Network layer: Internet Protocol (IP)
At least 6 protocols in the application layer
SEHH2238 Lecture 8 7
SEHH2238 Computer Networking
TCP/IP Protocol Suite
SEHH2238 Lecture 8 8
SEHH2238 Computer Networking
Internet Protocol (IP)
The Internet Protocol version 4 (IPv4) is the network layer protocol used by TCP/IP
Provides an unreliable, connectionless datagram best-effort delivery service
Unreliable
packet may be lost, duplicated, delayed, out of
Connectionless datagram
sequence of packets (belong to the same data file)
may travel along different paths
Best-effort delivery
– Internet does not discard packets
– unreliability arise only when resources are fully
loaded or underlying networks fail
SEHH2238 Lecture 8 9
SEHH2238 Computer Networking
Internet Protocol (IP)
Defines the format of the basic unit of data transfer
The IP packet, called IP datagram, consists of variable-length header and data (payload) fields
Setting IP address and routing tables
Handle the routing decision and operation
SEHH2238 Lecture 8 10
SEHH2238 Computer Networking
Figure 19.2: IP datagram
SEHH2238 Computer Networking
IP Datagram Format
Version Number (VER) for IPv4, it is 4
Header Length (HLEN)
min. 20 bytes to max. 60 bytes
(in 4-byte words) the header length in bytes is divided by 4 to get the value of this field
Total Length
the total length (header plus data) in bytes min. 20 bytes to max. 65535 bytes
Identification, Flags, and Fragment Offset
for fragmentation (when the datagram is too long)
and reassembly (discuss later)
SEHH2238 Lecture 8 12
SEHH2238 Computer Networking
IP Datagram Format
Time-to-live
max. no. of remaining hops (or routers)
allowed to visit
initially set to two times the path length
being decremented at each router
if it is zero, the datagram will be discarded
Protocol
a number to indicate which upper layer
protocol will get the data
Header Checksum
just for detecting errors in the header
SEHH2238 Lecture 8 13
Example 19.1
An IPv4 packet has arrived with the first 8 bits as (01000010)2 The receiver discards the packet. Why?
There is an error in this packet. The 4 leftmost bits (0100)2 show the version, which is correct. The next 4 bits (0010)2 show an invalid header length (2 × 4 = 8). The minimum number of bytes in the header must be 20. The packet has been corrupted in transmission.
SEHH2238 Lecture 8
Example 19.2
In an IPv4 packet, the value of HLEN is (1000)2. How many bytes of options are being carried by this packet?
The HLEN value is 8, which means the total number of bytes in the header is 8 × 4, or 32 bytes. The first 20 bytes are the base header, the next 12 bytes are the options.
SEHH2238 Lecture 8 15
Example 19.3 (modified)
In an IPv4 packet, the value of HLEN is 5, and the value of the total length field is (0038)16. How many bytes of data are being carried by this packet?
The HLEN value is 5, which means the total number of bytes in the header is 5 × 4, or 20 bytes (no options). The total length is (0038)16 or 56 bytes, which means the packet is carrying 36 bytes of data (56 − 20).
SEHH2238 Lecture 8 16
SEHH2238 Computer Networking
IP Fragmentation & Reassembly
Network links have MTU (maximum transfer unit) : largest possible link-level frame payload size
fragmentation:
Different link types, different sizes of MTUs
in: one large datagram out: 3 smaller datagrams
The size of MTU includes both data and header of the IP datagram
reassembly
SEHH2238 Lecture 8 17
SEHH2238 Computer Networking
IP Fragmentation & Reassembly (cont.)
A datagram can travel through different networks. Each router decapsulates the IP datagram from the frame it receives, processes it, and then encapsulates it in another frame.
The format and size of the sent frame depend on the protocol used by the physical network through which the frame is going to travel.
For example, if a router connects a LAN to a WAN, it receives a frame in the LAN format and sends a frame in the WAN format.
SEHH2238 Lecture 8 18
SEHH2238 Computer Networking
Figure 19.5: Maximum transfer unit (MTU)
TCP/UDP Header
Transport Layer
SEHH2238 Lecture 8
Data-link Layer
SEHH2238 Computer Networking
IP Fragmentation & Reassembly (cont.)
Large IP datagram is divided (“fragmented”) within a network
fragmentation:
One datagram becomes several datagrams (fragments)
in: one large datagram out: 3 smaller datagrams
“Reassembled” only at final destination
reassembly
IP header bits used to identify related fragments and put them in order
SEHH2238 Lecture 8 20
SEHH2238 Computer Networking
1st bit – not used
IP Fragmentation Fields
The16-bitIdentificationfieldidentifiesadatagram originating from the source
When a datagram is fragmented, the ID is copied into all fragments
The3-bitFlagsfielddefinesthreeflags:
2nd bit (D-bit), “do not fragment” bit – if 1, means must not fragment; if 0, means can be fragmented if needed
3rd bit (M-bit), “more fragment” bit – if 1, means more fragments after this one; if 0, means this is the last or only fragment
The13-bitFragmentationOffsetfieldshowstheoffset (position) of this fragment in the original datagram in units
of 8 bytes
SEHH2238 Lecture 8 21
SEHH2238 Computer Networking
The fragflag is the M-bit
• Assume no optional fields in header
length ID fragflag offset
• 4000 byte datagram
• MTU = 1500 bytes
One large datagram becomes several smaller datagrams
• Data size =4000 – 20 =3980
• =1480+1480+1020 1480 bytes in
length ID fragflag offset
data field
offset = 1480/8
=1 =185 =0 =370
IP Fragmentation
length ID fragflag offset
length ID fragflag offset
The offset value is specified in units of 8 bytes
SEHH2238 Lecture 8 22
SEHH2238 Computer Networking
(M-bit,offset) (0,0) =>
The fragflag is the M-bit
no fragmentation (1,0)=>
the first fragment (1,>0)=>
length ID fragflag offset =1500 =x =1 =0
a middle fragment and more to be followed
length ID fragflag offset =1500 =x =1 =185
(0,>0)=>
the last fragment
length ID fragflag offset
IP Fragmentation
length ID fragflag offset =4000 =x =0 =0
SEHH2238 Lecture 8
Figure 19.7: Detailed fragmentation example
Further fragmentation may be needed when the MTU of the next link is smaller than the current fragment size
Example 19.6
A packet has arrived with an M bit value of 0. Is this the first fragment, the last fragment, or a middle fragment? Do we know if the packet was fragmented?
If the M bit is 0, it means that there are no more fragments; the fragment is the last one.
However, we cannot say if the original packet was fragmented or not. A nonfragmented packet is considered the last fragment.
SEHH2238 Lecture 8 25
Example 19.7
A packet has arrived with an M bit value of 1. Is this the first fragment, the last fragment, or a middle fragment? Do we know if the packet was fragmented?
If the M bit is 1, it means that there is at least one more fragment.
This fragment can be the first one or a middle one, but not the last one. We don’t know if it is the first one or a middle one; we need more information (the value of the fragmentation offset).
SEHH2238 Lecture 8 26
Example 19.9
A packet has arrived in which the offset value is 100. What is the number of the first byte? Do we know the number of the last byte?
To find the number of the first byte, we multiply the offset value by 8.
This means that the first byte number is 800. We cannot determine the number of the last byte unless we know the length of the data.
SEHH2238 Lecture 8 27
Example 19.10
A packet has arrived in which the offset value is 100, the value of HLEN is 5, and the value of the total length field is 100. What are the numbers of the first byte and the last byte?
The first byte number is 100 × 8 = 800.
The total length is 100 bytes, and the header length is 20 bytes (5 × 4),
which means that there are 80 bytes in this datagram.
If the first byte number is 800, the last byte number must be 879.
SEHH2238 Lecture 8 28
SEHH2238 Computer Networking
They connect networks and decide the path a packet should take
The routing table are normally dynamic and are updated using routing protocols
SEHH2238 Lecture 8 29
SEHH2238 Computer Networking
C. Routing Algorithms
Decide which output link (path) a packet should be transmitted in order to reach the destination
There are many different routing algorithms:
It is used to exchange information among routers to
build and maintain their routing tables
Decision may base on some criteria: e.g. shortest path, least cost (Compare it with how you reach the campus from home)
In routing the term shortest can mean the combination of many factors including shortest, cheapest, fastest, most reliable and so on.
SEHH2238 Lecture 8 30
SEHH2238 Computer Networking
Routing Algorithm Classification
Global or decentralized?
Static or dynamic?
Allroutershavecomplete
topology, link cost information e.g.“linkstate”algorithms Decentralized:
Routes (the routing tables) change slowly over time
Router knows neighbors’ information, link costs to neighbors only
Routes change more
Iterative process of computation, exchange of information with neighbors
in response to link cost changes
e.g.“distance vector” algorithms CC3209Lect07
periodic update
SEHH2238 Computer Networking
Next-Hop Routing
Each host (source/destination) and router have their own (local) routing tables.
Look at this table to find the route to the final destination (i.e. the next router to be visited)
The table holds only the information that leads to the next hop (neighbor)
The entries of the routing tables are generated by a selected algorithm and must be consistent with each other
SEHH2238 Lecture 8 32
SEHH2238 Computer Networking
Next-Hop Routing
Also see the example: SEHH2238_T8_IP_RoutingTableExample.pd f
SEHH2238 Lecture 8 33
SEHH2238 Computer Networking
Figure 18.22: Network address
The network address is the identifier of the network and it is used by the forwarding (or routing) table in the Internet
SEHH2238 Lecture 87 34
SEHH2238 Computer Networking
Routing Example
Assume that a station wants to send data with destination IP address of 131.108.2.2
The data is sent out over the Internet until it reaches the router that is attached to the network
The router in the destination network will determine which one of the subnets the data should be routed to
The router knows that the subnet mask is 255.255.255.0
SEHH2238 Lecture 8 35
SEHH2238 Computer Networking
SEHH2238 Lecture 8 36
SEHH2238 Computer Networking
SEHH2238 Lecture 8
Forwarding table at the router
SEHH2238 Computer Networking
D. LAN Addresses and Address Resolution
32-bit IP address:
Network-layer address
Used to send datagram to destination IP network A logical address
LAN (or MAC or Ethernet) address:
A physical address
Used to send datagram from one node to another
physically-connected node (in the same network)
48 bit MAC address (for most LANs) which is burned (hard-coded) in the adapter ROM
Physical Address. . . . . . . . . : 00-25-26-56-8D-30
SEHH2238 Lecture 8 38
SEHH2238 Computer Networking
LAN Addresses and ARP
Each adapter on LAN has unique LAN address
SEHH2238 Lecture 8 39
SEHH2238 Computer Networking
LAN Address (more)
MAC address allocation administered by IEEE
Manufacturer buys MAC address space (to
assure uniqueness)
MAC address => portable
can move LAN card from one LAN to another LAN (the station (LAN card) still uses the same MAC address)
IP address (structured) => NOT portable
depends on the IP of the attached network
when moving to another network, the station needs to change its IP address (without changing the MAC address if the same LAN card is used)
SEHH2238 Lecture 8 40
SEHH2238 Computer Networking
Recall earlier routing discussion
Starting at A, given IP datagram addressed to B:
• look up net. address of B, find B on same net. as A
223.1.2.1 223.1.1.4 223.1.2.9
• link layer send datagram
223.1.2.2 E 223.1.3.2
to B inside link-layer
223.1.1.3 223.1.3.1
223.1.3.27
B’s MAC addr
A’s MAC addr
A’s IP addr
B’s IP addr
Frame dest, source address
datagram source, dest address
IP data datagram
SEHH2238 Lecture 8
SEHH2238 Computer Networking
ARP: Address Resolution Protocol
How to determine
MAC address of B knowing B’s IP address? – Done by ARP
Each IP node (Host, Router) on LAN has an ARP table
ARPTable:IP/MACaddress 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)
SEHH2238 Lecture 8 42
SEHH2238 Computer Networking
ARP Protocol
“A” wants to send datagram to “B”, and A knows B’s IP address.
Suppose B’s MAC address is not in A’s ARP table.
An ARP packet contains the sending and receiving IP and MAC addresses
“A” broadcasts ARP query packet, containing B’s IP address (as well as A’s IP & MAC addresses)
all nodes on LAN receive ARP query
SEHH2238 Lecture 8 43
SEHH2238 Computer Networking
ARP Protocol (cont.)
“B” receives ARP query packet, then replies to “A” with its (B’s) MAC address
ARP reply packet sent to A’s MAC address only
After receiving the ARP reply packet, “A” caches (saves) IP-to-MAC address pair of “B” in its ARP table until information becomes old (times out- TTL expires)
SEHH2238 Lecture 8 44
SEHH2238 Computer Networking
Network Layer Functions Internet Protocol (IP)
Connectionless, unreliable, best-effort Routing
Routing Algorithms, Next-hop Routing Table LAN Addressing
Address Resolution Protocol (ARP) Revision Quiz
http://highered.mheducation.com/sites/0073376221/student_view0/chapter 19/quizzes.html
SEHH2238 Lecture 8 45
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com