Operating Systems Lecture Notes
Martin C. Rinard
- Networking deals with interconnected groups of machines talking
with each other. Is a very different field than operating systems.
Have a lot of standards stuff because everyone must agree on what
to do when connect machines together.
- What is a network? A collection of machines, links and switches
set up so that machines can communicate with each other. Some examples:
Message may have to traverse multiple links and multiple switches
to go from source to destination.
- Telephone system. Machines are telephones, links are the telephone
lines and switches are the phone switches.
- Ethernet. Machines are computers, there is one link (the ethernet)
and no switches.
- Internet. Machines are computers, there are multiple links,
both long-haul and local-area links. The switches are gateways.
- Circuit-switched versus Packet-switched networks. Basic
disadvantage of circuit-switched networks - cannot use resources
flexibly. Basic advantage of circuit-switched networks - deliver
a guaranteed resource.
- Basic Networking Concepts:
- Flow control.
- Unreliable Delivery.
- Local Area Networks. Connect machines in a fairly close geographic
area. Standard for many years: Ethernet. Standardized by Xerox, Intel
and DEC in 1978. Still in wide use.
- Physical hardware technology: coax cable about 1/2 inch thick.
Maximum length: 500 meters. Can extend with repeaters. Can only
have two repeaters between any two machines, so maximum length is
- Vampire taps to connect machines to Ethernet. Attach an
ethernet transceiver to tap; the transceiver does the connection
between the Ethernet and the host interface. The host interface
then connects to the host machine.
- Ethernet is 10 Mbps bus with distributed access control.
It is a broadcast medium - all transceivers see all packets and
pass all packets to host interface. The host interface chooses
packets the host should receive and discards others.
- Access scheme: Carrier sense multiple access with collision
detection. Each access point senses carrier wave to figure out
if machine is idle. To transmit, waits until carrier is idle,
then starts transmitting. Each transmission consists of a
packet; there is a maximum packet size.
- Collision detection and recovery. Transceivers monitor carrier
during transimission to detect interference. Interference can happen
if two transceivers start sending at same time. If interference
happens, transceiver detects a collision.
- When collision detected, uses a binary exponential backoff policy
to retry the send. Adds on a random delay to avoid synchronized retries.
- Is there a fixed bound on how long it will take a packet to
get successfully transmitted? Is any packet guaranteed to be
transmitted at all?
- Addressing. Each host interface has a hardware address
built into it. Addresses are 48 bits long. When change host
interface hardware, address changes.
- Are three kinds of addresses:
- Physical address of one network interface.
- Broadcast address for the network. (All 1's).
- Multicast addresses for a subset of machines on network.
- Host interface looks at all packets on the ethernet. It
passes a packet on to the host if the address in the packet
matches its physical address or the broadcast address. Some
host interfaces can also recognize several multicast addresses,
and pass packets with those addresses on to the host.
- How do vendors avoid ethernet physical address clashes?
Buy blocks of addresses from a central authority.
- Packet (frame) format.
Ethernet frames are self-identifying. Can just look at frame and
know what to do with it. Can multiplex multiple protocols on
same machine and network without problems.
CRC lets machine identify corrupted packets.
- Preamble. 64 bits of alternating 1 and 0, to synchronize receivers.
- Destination address. 48 bits.
- Source address. 48 bits.
- Packet type. 16 bits. Helps OS route packets.
- Data. 368-120000 bits.
- CRC. 32 bits.
- Token-ring networks. Alternative to ethernet style networks.
Arrange network in a ring, and pass a token around that lets
machine transmit. Message flows around network until reaches
destination. Some problems: long latency, token regeneration.
- ARPANET. Ancestor of current Internet. Long-haul packet-switched
network. Consisted of about 50 C30 and C300 BBN computers in US and
Europe connected by long-haul leased data lines. All computers
are dedicated packet-switching machines (PSNs).
- Interesting fact: ARPANET, like highway system, was initially
a DOD project set up officially for defense purposes.
- In original ARPANET, each computer connected to ARPANET
connected directly to a PSN. Each packet contained address of
destination machine and PSN network routed the packet to that machine.
Now this is totally impractical and have
a much more complex local structure before get onto Internet.
- Design of Internet driven by several factors.
Will have multiple networks around the world. An internetwork,
or internet, connects the different networks. So, job of
internet is to route packets between networks.
- Will have multiple networks. Different vendors compete,
plus have different technical tradeoffs for local area, wide
area and long haul networks.
- People want universal interconnection.
- One goal of internet: Network transparency. Want to have
a universal space of machine identifiers and refer to all machines
on the internet using this universal space of machine identifiers.
Do not want to impose a specific interconnection topology or
- Internet architecture. Connect two networks using a gateway
machine. The job of the gateway is to route packets from one
network to another.
- As network topologies become more complicated, gateways
must understand how to route data through intermediate networks
to reach final destination on a remote network.
- In Internet, gateways provide all interconnections between
physical networks. All gateways route packets based on the
network that the destination is on.
- Internet addressing. Each host on the Internet has a unique
32-bit address that is used for all Internet traffic to that host.
Each internet address is a (netid, hostid) pair. The network identifies
the network that the host is on, the hostid identifies the host
within the network.
- Three classes of Internet addresses:
See RFC 990 for spec.
- Class A. First Bit: 0. Bits 1-7: Netid. Bits 8-31: Hostid.
Can have 128 Class A networks.
- Class B. Bits 0-1: 10. Bits 2-15: Netid. Bits 16-31: Hostid.
Can have 16,384 Class B networks.
- Class C. Bits 0-2: 110. Bits 3-23: Netid. Bits 24-31: Hostid.
Can have 2 Gig Class C networks.
- Class D. (multicast addresses). Bits 0-3: 1110. Used
for Internet multicast.
- Class E. Bits 0-3 1111. Reserved.
- Interesting point. Whole structure of internet is available
in RFC's (request for comments). Available over the Internet - use
the net search functionality for RFC and you'll find pointers. Can
read them to figure out what is going on.
- Gateways can extract network portion of address quickly.
Gateways have two responsibilies:
- Route packets based on network id to a gateway connected to
- If they are connected to destination network, make sure
the packet gets delivered to correct machine on that network.
- Conceptually, an Internet address identifies a host. Exceptions:
gateways have multiple internet addresses, at least one per network
that they are connected to.
- Because network id is encoded in Internet address, a machine's
internet address must change if it switches networks.
- Dotted Decimal notation: Reading Internet addresses. Four
decimal integers, with each integer representing one byte.
- cs.stanford.edu - 22.214.171.124 (what kind of network is it on).
- cs.ucsb.edu - 126.96.36.199
- ecrc.de - 188.8.131.52
- lcs.mit.edu - 184.108.40.206
- sri.org - 220.127.116.11
- Who assigns internet addresses? The Network Information Center!
A centralized authority. It just allocates network ids, leaving
requesting authority to allocate host ids.
- Do example on page 45.
- Mapping Internet addresses to Physical Network addresses.
Will discuss case when physical network is an Ethernet. Given
a 32 bit Internet address, gateway must map to a 48 bit Ethernet
address. Uses Address Resolution Protocol (ARP).
- Gateway broadcasts a packet containing the Internet address
of the machine that it wants to send the packet to. When machine
receives packet, it sends back a response containing its physical
address. Gateway uses physical address to send packet directly to
- Also works for machines on same network even when they
are not gateways.
- Use a address resolution cache to eliminate ARP traffic.
- ARP request and response frames have specific type fields.
An ARP request has a type field of 0806, responses have 8035.
Standard set up by the Ethernet standard authority.
- How does a machine find out its Internet address? Store it on
disk, and looks there to find out when it boots up. What if it
is diskless? Contacts server and finds it out there using Reverse
ARP (RARP). RFC 903 - Ross Finlayson, etc.
- RARP request is broadcasted to all machines on network.
RARP server looks at physical address of requestor and sends
it a RARP response containing the internet address. Usually
have a primary RARP server to avoid excessive traffic.
- Now switch to talking about IP - the Internet Protocol.
The internet conceptually has three kinds of services layered
on top of each other: Connectionless, unreliable packet delivery
service, reliable transport service, and application services.
IP is the lowest level - the packet delivery.
- The basic unit of transfer in the Internet is the IP datagram.
IP datagram has header and data. Header contains internet addresses
and the Internet routes IP datagrams based on Internet addresses
- Internet makes a best effort attempt to deliver each datagram,
but does not deal with error cases. In particular, can have:
Higher level software layered on top of IP deals with these conditions.
- Lost Packets
- Duplicated Packets
- Out of order Packets
- IP packets always travel from gateway to gateway across
physical networks. If the IP packet is larger than the physical
network frame size, the IP packet will be fragmented: chopped
up into multiple physical packets. IP is designed to deal with
this situation and provides for fragmentation.
- Once a packet has been fragmented, must be reassembled back into
a complete packet. Usually reassembled only when fragments
reach final destination. But, could build a system that reassembled
fragments when got to a physical network with a larger frame size.
- Why is there a need for possibility of fragmentation?
No good way to impose a uniform packet size on all networks.
Some networks may support large packets for performance, while
others can only route small packets. Should not prevent some
networks from using large packets just because there exists
a network somewhere in the world that can not handle large packets.
But must be able to route large packets through a network that
only handles small packets - network transparency.
- Important fields in IP header:
- VERS: protocol version.
- LEN: length of header, in 32-bit words.
- TOTAL LEN: total length of IP packet.
- SOURCE IP ADDRESS: IP address of source machine.
- DEST IP ADDRESS: IP address of destination machine.
- TTL: time to live. How many hops the packet may take
without getting removed from Internet. Every time a gateway
forwards the packet, it decrements this field. Required to
deal with things like cycles in routing, etc.
- IDENT: packet indentifier. Unique for each source.
Typically, source maintains a global counter it increments
for every IP datagram sent.
- FLAGS: A do not fragment flag (dangerous) and a
more fragments flag - 0 marks end of datagram.
- FRAGMENT OFFSET - gives offset of this fragment
in original datagram.
- How to reassemble a fragmented packet? Allocate a buffer
for each packet. Use IDENT and SOURCE IP ADDRESS to identify
the original datagram to which the fragment belongs. Use the
FRAGMENT OFFSET field to write each fragment into correct spot
in the buffer. Use more fragments flag to find end of original
datagram. Use some mechanism to make sure all fragments arrived
before consider datagram complete.
- Routing IP datagrams. There are multiple possible paths
between hosts in an internet. How to decide which path for which
- Routing for hosts on same network. Realize that are on
same network by looking a netid field of Internet address, and
just use underlying physical network.
- Routing for hosts on different networks. Gateways pass
datagrams from network to network until reach a gateway
connected to destination network.
- Each gateway must decide next gateway to send datagram to.
Most routers use a combination of table driven routing and
default routing. They know how to route some packets, and
pass others along to a default router. Eventually, all defaults
point to a router that knows how to route ALL packets.
- Source routing. The source specifies the route in the
datagram. Useful for debugging and other cases in which Internet
should be forced to use a certain route.
- Host-specific routes. Can specify a specific route for each
host. Used mostly for debugging.
- Table driven routing. Each gateway has a table indexed
by destination network id. Each table entry tells where
to send datagrams destined for that network. Do example
on page 82.
- Default routes. Specify a default next gateway to be
used if other routing algorithms don't give a route.
- How are routing tables acquired and maintained?
There are a lot of different protocols, but the basic idea
is that the gateways send messages back and forth advertising
routes. Each advertisement says that a specific network is
reachable via N hops. Some protocols also include information
about the different hops. The gateways use the route
advertisements to build routing tables.
- Internet was originally designed to survive military attacks.
It has lots of physical redundancy and
its routing algorithm is very dynamic and resilient to change.
If a link goes away, the network should be able to route around
the failure and still deliver packets. So, routing tables change
in response to changes in the network.
- In practice doesn't always work as well as designed. Chief
threat to Internet links these days is backhoes, not bombs.
Common error is routing all of the links that are supposed to
give physical redundancy in the same fiber run, so are vulnerable
to one backhoe.
- In original internet, partition gateways into two groups.
Core and noncore gateways. Core gateways have complete information about
routes. Original core gateways used a protocol called
GGP (Gateway to Gateway Protocol) to update routing tables.
- GGP messages allow gateways to exchange pairs of messages.
Each message advertise that the sender can reach a given
network N in D hops. Receiver compares its current route to the
new route through the sender, and updates its tables to use
the new route if it is better.
- Famous case: Harvard gateway bug. Memory fault caused it
to advertise a 0 hop route to everybody!
- Problem with GGP - distributed shortest path algorithm
may take a long time to converge.
- Later algorithm (SPF) replicated a complete database
of network topology in every gateway. Gateway runs a local shortest
path computation to build its tables.
- In current Internet, there is no longer any central backbone
or authority. Instead, have internet providers. The whole system
has switched over to private enterprise.
- A top-down view of system. There are 4 Network Access Providers.
Each NAP is a very fast router connected via high-capacity lines
to other gateways and NAPs. Lines may be T3 (644 Mb/s) lines.
Typically big communications companies (MCI, Sprint, ATT) own
the lines. Lines are typically fiber.
- Organizations go to internet providers to get access to the
internet. An internet provider buys a bunch of routers (usually
from Cisco) and leases a bunch of lines. The internet provider
must also buy access to a NAP or to a gateway that leads to a
NAP. The routers talk
a route advertisement protocol and implement some routing algorithm.
- The internet provider can then turn around and sell internet
access to whoever wants to buy it. UCSB buys its internet access
from CERFNET, and it pays $23,000 per year for its internet access.
All of the UC schools will band together and buy internet access
from MCI, getting more bandwidth but at a higher price.
- Check out
http://www.cerf.net to see an Internet topology.
- Organizations tend to chop their communications
up into multiple networks, so there are too many networks in the
world to give every network an Internet address. For example,
the UCSB CS department has more than 10 networks.
- The solution is subnetting. Internet views whole organization
as having one network. The organization itself chops the host
part of IP address up into a pair of local network and local host.
For example, UCSB has one class B Internet network. The third byte
of every IP address identifies a local network, and the fourth
byte is the host on that network.
- All IP packets from outside come to one UCSB gateway (by default).
As far as the Internet is concerned, all of UCSB has only one
- Inside UCSB, there is a set of networks connected by routers.
These routers interpret the IP address as containing a local
network identifier and a host on that network, and route the
packet within the UCSB domain. The routers
periodically advertise routes using a protocol called RIP.
- This is an example of hierarchical routing. Internet routes to
UCSB gateway based on Internet network id, then routers within
UCSB route based on the subnet id.
- traceroute command tells you the gateways packets go through
to get to a given location. Here are a few:
cheetah > traceroute minnie (CSIL Lab, UCSB)
traceroute to minnie (18.104.22.168), 30 hops max, 40 byte packets
1 toons (22.214.171.124) 17 ms * 3 ms
2 minnie (126.96.36.199) 3
cheetah > traceroute ecrc.de (Munich, Germany)
traceroute to ecrc.de (188.8.131.52), 30 hops max, 40 byte packets
1 lo-galaxy (184.108.40.206) 6 ms 3 ms 3 ms
2 ecigw1-41 (220.127.116.11) 4 ms 12 ms 4 ms
3 cerfgw (18.104.22.168) 6 ms 12 ms 7 ms
4 uclagw.cerf.net (22.214.171.124) 24 ms 22 ms 22 ms
5 sdsc-ucla.cerf.net (126.96.36.199) 44 ms 263 ms 116 ms
6 nynap-sdsc-atm-ds3.cerf.net (188.8.131.52) 141 ms 111 ms 126 ms
7 sprintl.sprint.ep.net (184.108.40.206) 124 ms 147 ms *
8 sl-pen-1-F0/0.sprintlink.net (220.127.116.11) 170 ms 114 ms 122 ms
9 sl-dc-6-H2/0-T3.sprintlink.net (18.104.22.168) 123 ms 122 ms 132 ms
10 icm-dc-2b-F1/0.icp.net (22.214.171.124) 126 ms 212 ms 119 ms
11 icm-dc-1-F0/0.icp.net (126.96.36.199) 122 ms 214 ms 156 ms
12 icm-ecrc-1-S0-1984k.icp.net (188.8.131.52) 218 ms 209 ms 223 ms
13 ECRC-RBS.ECRC.DE (184.108.40.206) 280 ms 536 ms 315 ms
14 ECRC-GW.ECRC.DE (220.127.116.11) 297 ms 215 ms 236 ms
15 ecrc.de (18.104.22.168) 219 ms * 343 ms
cheetah > traceroute rain.org (Santa Barbara, CA)
traceroute to rain.org (22.214.171.124), 30 hops max, 40 byte packets
1 lo-galaxy (126.96.36.199) 7 ms 3 ms 3 ms
2 ecigw1-41 (188.8.131.52) 5 ms 5 ms 5 ms
3 cerfgw (184.108.40.206) 7 ms 6 ms 6 ms
4 uclagw.cerf.net (220.127.116.11) 57 ms 40 ms 22 ms
5 sdsc-ucla.cerf.net (18.104.22.168) 44 ms 54 ms 57 ms
6 ucop-sdsc.cerf.net (22.214.171.124) 84 ms 62 ms 61 ms
7 sl-ana-3-S2/6-T1.sprintlink.net (126.96.36.199) 85 ms 81 ms 75 ms
8 sl-ana-1-F0/0.sprintlink.net (188.8.131.52) 162 ms 139 ms *
9 sl-fw-6-H2/0-T3.sprintlink.net (184.108.40.206) 125 ms 138 ms 158 ms
10 sl-fw-3-F0/0.sprintlink.net (220.127.116.11) 141 ms 184 ms 121 ms
11 sl-rain-network-1-S0-T1.sprintlink.net (18.104.22.168) 175 ms 165 ms 153 ms
12 coyote.rain.org (22.214.171.124) 149 ms 192 ms 184 ms
cheetah > traceroute cs.orst.edu (Corvallis, Oregon)
traceroute to cs.orst.edu (126.96.36.199), 30 hops max, 40 byte packets
1 lo-galaxy (188.8.131.52) 7 ms 3 ms 3 ms
2 ecigw1-41 (184.108.40.206) 5 ms 10 ms 10 ms
3 cerfgw (220.127.116.11) 8 ms 9 ms 8 ms
4 * uclagw.cerf.net (18.104.22.168) 37 ms *
5 uci-la-smds.cerf.net (22.214.171.124) 38 ms 33 ms 30 ms
6 * * ucop-sf-ds3-smds.cerf.net (126.96.36.199) 64 ms
7 border3-hssi1-0.SanFrancisco.mci.net (188.8.131.52) 70 ms 71 ms 51 ms
8 core-fddi-0.SanFrancisco.mci.net (184.108.40.206) 75 ms * 103 ms
9 core-hssi-2.Seattle.mci.net (220.127.116.11) 74 ms 79 ms 81 ms
10 border1-fddi0-0.Seattle.mci.net (18.104.22.168) 87 ms 72 ms 142 ms
11 nwnet.Seattle.mci.net (22.214.171.124) 68 ms 272 ms 238 ms
12 seabr1-gw.nwnet.net (126.96.36.199) 225 ms 103 ms 75 ms
13 seattle1-gw.nwnet.net (188.8.131.52) 84 ms * 162 ms
14 portland1-gw.nwnet.net (184.108.40.206) 102 ms 137 ms 161 ms
15 osu-gw.nwnet.net (220.127.116.11) 186 ms 151 ms 202 ms
16 orst3-gw.ORST.EDU (18.104.22.168) 127 ms * 91 ms
17 ece-gw-out.ece.ORST.EDU (22.214.171.124) 86 ms * 95 ms
18 CS.ORST.EDU (126.96.36.199) 100 ms 89 ms *
Permission is granted to copy and distribute this
material for educational purposes only, provided that the
following credit line is included: "Operating Systems
Lecture Notes, Copyright 1997 Martin C. Rinard."
Permission is granted to alter and distribute this material provided
that the following credit line is included:
"Adapted from Operating Systems
Lecture Notes, Copyright 1997 Martin C. Rinard."
Martin Rinard, firstname.lastname@example.org, www.cag.lcs.mit.edu/~rinard