Selected notes on Network Layer, Featuring IP

Service

Move transport layer PDU's from sender to receiver

PDU

Packet

Major Issues

· routing - determining path

· switching - within router, getting data from input line to proper output line

· call setup and termination (virtual circuit service only)

Major Levels of Service

· Datagram

· Virtual Circuit

Datagram Service

· best example is IP (Internet Protocol)

· IP packets normally called datagrams

· each packet separately routed

· router does not maintain state, so no setup/teardown

· "best effort" delivery, i.e. no guarantees

· ADV: simple, flexible for internetworking (interconnecting heterogeneous networks)

· DIS: places high demands on transport layer

· good fit to Internet, because it joins dissimilar networks plus transport layer is in computers

Virtual Circuit Service

· one example is ATM (also X.25, frame relay)

· provides circuit-like service using packet-switched network

· each packet follows same path

· complex protocol for establishing path

· router maintains state (VC information)

· several service quality (QoS) levels are available to customer

· ADV: simple for transport layer

· DIS : complex protocols must be followed by all routers

· good fit to telephony, because homogeneous networks plus "transport layer" is telephones

Routing Algorithms

Use graph theory to present algorithms

· nodes : routers (are assigned IDs)

· edges : links between routers (can be directed or undirected)

· weights on edges: any cost measure of using that link (distance, congestion, capacity)

· shortest path : minimum number of links (hops)

· least cost path : minimum total cost, regardless of # hops

Static vs. Dynamic routing algorithms

· static means routes change very slowly (e.g. manual changes to tables)

· dynamic means routes evolve as network loads and topologies change

Global vs. Local routing algorithms

· global means all nodes have complete knowledge of topology and costs (e.g. link state)

· local means nodes receive knowledge only from neighbors (e.g. distance vector)

· both are distributed in the sense that each node does its own calculations

· truly centralized algorithm is impractical -- why?

Link State Algorithms

Good example is Dijkstra's

· Before algorithm is run, all nodes must have complete cost and topology information.

· Knowledge achieved by each node broadcasting costs to get from itself to its neighbors.

· Algorithm works for either directed or undirected graphs.

· Undirected means assume link cost is same in both directions (not always true).

· Algorithm calculates shortest path from a given source to all destinations.

· Each node runs algorithm with itself as source.

· Results of this iterative algorithm go into routing table.

Distance Vector Algorithms

· Each node communicates only with its neighbors

· Each node calculates only its own table

· Distance vector table layout:

· Each row is a destination node X

· Each column is a neighbor Y

· Each entry represents cost to destination X via neighbor Y.

· Lowest value in each row is the “least cost path”.

· Least cost path for each destination is copied into routing table.( dest., neighbor, maybe cost)

· Table is dynamically updated. When? When node receives message from neighbor node.

· When does node send message? When its own update causes change(s) to least cost path.

· What does message contain? Destination ID and cost (note: neighbor ID is not in message).

· “good news travels fast” – when a link cost decreases, full reduction propagates rapidly (one hop per update)

· “bad news travels slow” – when a link cost increases (or link goes down) the increase may propagate at only one cost unit per update (the “count to infinity” problem). There are countermeasures.

Hierarchical routing

· How large would routing tables be if every router needed an entry for every other router and host?

· Define autonomous systems (AS) as logical grouping of routers.

· Inter-AS routing is routing from one AS to another.

· Intra-AS routing is routing within an AS.

· They can use different routing methods.

· ANALOGY: Post office as AS. use 5-digit ZIP code to deliver to destination post office (“inter-AS”), street address to deliver to host from there (“intra-AS”)

· Routers at the AS “edge” are called gateway.

· Gateways communicate with other gateways to implement inter-AS.

· Gateways must be able to run routing methods for both inter- and intra-AS.

IP: Internet Protocol

IP Addresses

· 32 bits for IPv4

· each “interface” must have unique IP address

· get ‘em from regional Internet registry (ARIN for U.S.), under ICANN management.

· Sys admin can configure address to host (static)

· DHCP is Dynamic Host Configuration Protocol, a client-server protocol for assigning available IP address dynamically

· dotted decimal notation: a.b.c.d

· partitioned into network part and host part.

· “network” means all hosts addressible without further routers

· IPv4 allows over 4 billion addresses, so why the shortage?

· Originally, length of host part had specific length -- “classful” addressing

· Class A address: 24 bit host, B: 16 bit host, C: 8 bit host.

· Organization could buy only a class A network, class B network or class C network (exclusive rights to all host addresses within).

· Led to serious “three bears problem”

· Several solutions: CIDR, subnetting, IPv6 (covered after IPv4).

CIDR

· Classless InterDomain Routing

· Allows network part of address to be arbitrary length, denoted by “/ x”.

· For routing table, IP address supplemented with length in bits of network part: a.b.c.d / x

· E.g. “/ 20”Gives organization 12 bit host address (between class B and C) and 4096 hosts.

· ISP can buy a large block of IP address space, and allocate in smaller blocks to clients

· “/ x” forms mask that router applies to datagram destination address before matching

· E.g. / 20 defines mask 11111111 11111111 11110000 00000000

· Problem: after mask applied, destination address may match more than one router table entry.

o E.g. router table has separate entries for 64.48.16.0 / 20 and 64.48.24.0 / 21

o destination address 64.48.24.3 will match both!

o Ambiguity resolved using longest prefix matching rule. Select 64.28.24.0 / 21; it has a longer mask (e.g. longer matching prefix) and is thus addresses a smaller block.

Subnetting

· Conceptually similar to CIDR, except is within organization (invisible to external routers)

· Some of the IP address host bits can be used to identify internal subnet

· Each internal subnet has a 32 bit mask

· Gateway (or internal) router has subnet routing table

· Destination gateway router applies mask to incoming datagram

· Routes to matching subnet

· Adds another level to routing hierarchy

· Allows organization to better organize its internal networks

IPv4 Datagram Format

· See http://www.cs.smsu.edu/~pete/csc465/notes/spring00/ip.html#format

· Note that destination and source IP addresses are hosts, and are not changed by routers

· Note that TTL field is decremented by each router.

· Note that checksum is based on datagram header, and thus must be recalculated by each router because TTL field decremented!

Fragmentation

· Datagrams are payload of link layer frame (e.g. ethernet)

· Each link layer technology has maximum payload size (called MTU)

· What to do if datagram is bigger than MTU? Fragment.

· Even if sender knows MTU for its own link layer, datagram may encounter smaller MTU as it is routed to destination.

· Who does the fragmenting? Any router.

· Datagram must be reassembled at destination before being given to transport layer.

· Who does the reassembly? Destination host!

· Why the host? Because reassembly is more complex than fragmentation (any tinkerer can tell you that)!

· Fragments are IP datagrams themselves and thus may be dropped or arrive out-of-order or with errors.

· Thus network layer at destination has to run a reassembly protocol to account for at least out-of-order and delay.

· Reassembly protocol relatively simple since dropped or erroneous fragment results in entire datagram being dropped (even if only one fragment doesn’t arrive).

· IP has header bits to support this: “don’t fragment” bit, “more fragments” bit, fragment offset.

· Fragmentation can be avoided by keeping datagram to no more than 576 total bytes (standard minimum MTU). Subtracting 20 bytes for IP header and 20 bytes for TCP header, yields 536 byte TCP payload.

· Using ICMP, it is possible to determine minimum MTU for a given path. How? Answer below.

Internet Control Message Protocol (ICMP)

· Used to communicate IP-level error and control information.

· Interesting twist: the control message itself is payload in IP datagram. IP header’s Protocol field set to 1.

· Some error messages are:

o Source Quench: router buffers are full so it tells sender to back off

o Time Exceeded: datagram's TTL or fragment reassembly timer has expired -- notify sender.

o Destination Unreachable: when router learns this, transmits message to sender

o Redirect: tell sender to use a different route

o Fragmentation Required: datagram too big but can't be fragmented -- drop it and notify sender.

· Useful for more than error messages.

· ping is implemented using this. ICMP “echo request” from sender and “echo reply” from receiver

· traceroute is implemented using this. How?

· Answer to question at end of previous section: Minimum MTU for a path can be found using ICMP protocol. Send very large datagram (max size?) with “don’t fragment” bit set, and see if response is ICMP message with type=3 and code=4 (see RFC 792) “fragmentation needed and DF bit set”. If so, try smaller datagram and repeat until it gets through.

IPv6

· Hotter topic 5 years ago than now. Why? CIDR has relieved most issues of inefficient allocation of IP addresses.

· Address expanded to 128 bits.

· Ipv6 allows 7 * 10²³ IP addresses per square meter of the earth surface (water plus land). -- Andrew Tanenbaum, Computer Networks 3^rd Edition.

· Still contains prefix and suffix, but not address classes.

· Addresses written in colon hexadecimal notation. This is 8 groups of 16-bit hex numbers, each group separated by colon. A sequence of multiple groups of 0's can be compressed to a double colon (::).

· Features streamlined 40 byte fixed length header

o Version (value is 6),

o traffic class,

o flow ( kinda like a VC #),

o payload length,

o next header (same as IPv4 Protocol field),

o hop limit,

o source addr,

o dest addr.

o No fragmentation fields needed (if datagram too big, router drops it and sends ICMP message to sender, sender responds with smaller datagram).

o No checksum, redundant because TCP can handle it plus it is seldom needed.

· ICMPv6 defined with additional message types/codes.

· IPv4 – IPv6 transition tricky!

o One transition approach is “dual stack” e.g. has both IPv4 and 6 network layer functions

o Has to determine whether neighbor is IPv6-capable or not, and use IPv4 if not.

o This affects DNS; returns IPv6 address only if both it and requester are IPv6-capable.

o Another transition approach is “tunneling”

o If neighbor determined to be IPv4-only, then put IPv6 datagram in payload of IPv4 datagram.

o Receiver has to recognize this and pull it apart appropriately.

· Transition will be difficult at any rate.

Routing IP datagrams

RIP – an intra-AS protocol

· Routing Information Protocol

· A distance vector protocol

· Distributed with early TCP/IP as part of BSD unix

· Cost is hop count (e.g. each link has cost 1).

· 15 hop limit.

· Distance vectors exchanged every 30 seconds

· Exchange protocol uses UDP and port 520. Yes, transport layer protocol used to implement network layer function!

OSPF – an intra-AS protocol

· Open Shortest Path First

· A link state protocol

· Uses Dijkstra’s algorithm

· Has security features (exchanges authenticated)

· Allows use of multiple same-cost paths

· Can use different cost metric for different TOS, e.g. different graph for each TOS

· Supports hierarchical structure w/i the AS.

· AS partitioned into areas, each area has border router, one area has backbone.

· Backbone routes among area border routers

· Area border routers route within area

BGP – an inter-AS protocol

· Border Gateway Protocol, RFC 1772

· De facto standard for Internet

· For routing between AS’s. E.g. between organizations.

· Policy and political considerations now come into play (e.g. routers on AT&T networks will not route through routers on MCI networks).

· Path may not be “optimal cost”

· “Path vector” algorithm, a variation of distance vector

· Routers maintain path to each destination AS. In BGP, these paths are periodically communicated to neighbor (called “peer”).

· Note that exchanged paths do not contain cost information.

· Example:

o network with routers A through H.

o A is a peer of B

o B has this route for datagrams destined for H: BCEH.

o B sends this path info to A.

o A then may set its path to H as: ABCEH, but doesn’t have to.

o Decision not to, may be technical (already has shorter path) or political (A will not route anything through E because E is owned by competitor).

· Routers exchange BGP messages via TCP, port 179.

· There are 4 types of BGP messages:

o open – to establish contact with peer

o update – to send (“advertise”) path vector to peer

o keepalive – let peer know your connection is still OK

o notification – let peer know that error has occurred

· BGP can also be used for intra-AS routing (IBGP, Internal BGP)

Switching at the Network Layer

· 3-layer architecture:

o bits received at physical layer and delivers frame to link layer.

o Link layer extracts datagram and passes datagram to network layer.

o Routing and switching happens to datagram at network layer.

o Upon departure, datagram is passed to link layer,

o which encapsulates into frame and passes to physical layer for transmission.

· Major components are: input lines, switching fabric, routing processor, output lines.

· Queueing can occur at input lines, if desired path through switching fabric is occupied with another datagram.

· Queueing can occur at output lines, if link is busy transmitting another datagram.

· Desired path is determined by reading datagram’s destination and performing routing table lookup. This can be centralized, or done at each input line by shadowing copies of routing table for each.

· Switching itself can be handled by

o software (e.g. using system bus to read into memory, process in memory, output to system bus)

o switch bus (all input and output lines attached to bus, only one datagram can use at a time)

o switching configuration, such as crossbar or omega switch.

· Speed of operation is of utmost import

[notes | CSC 465 | Peter Sanderson | Computer Science | SMSU ]

Updated 21 March 2001

PeteSanderson@smsu.edu