Transcript CMPSCI 377 - Network Structures

Operating Systems
CMPSCI 377
Lecture 19: Network Structures
Emery Berger
University of Massachusetts Amherst
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
Next Few Classes


Networking basics
Distributed services



e-mail, www, telnet
Distributed operating systems
Distributed file systems
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
2
Distributed Systems

distributed system: set of physically separate processors
connected by one or more communication links
 no shared clock or memory
P2
P1
P4

P3
Many systems today distributed in some way
 e-mail, file servers, network printers, remote backup, web...
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
3
Parallel vs. Distributed Systems

Tightly-coupled systems: “parallel processing”



Processors share clock, memory, run one OS
Frequent communication
Loosely-coupled systems: “distributed computing”


Each processor has own memory, runs independent OS
Infrequent communication
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
4
Advantages of Distributed Systems




Resource sharing
Computational speedup
Reliability
Communication
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
5
Advantages of Distributed Systems

Resource sharing

Resources need not be replicated


Expensive (scarce) resources can be shared


Shared files
Color laser printers
Processors present same environment to user

Keeping files on file server
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
6
Advantages, continued

Computational speedup

n processors = n times computational power


Problems must be decomposable into
subproblems


SETI@home
Trivial = embarrassingly parallel
Coordination & communication required
between cooperating processes


Synchronization
Exchange of results
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
7
Advantages, continued

Reliability

Replication of resources provides fault tolerance



One node crashes, user works on another one
Performance degradation but system available
Must avoid single point of failure


Single, centralized component of system
Example: central file servers
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
8
Advantages, continued

Communication


Users/processes on different systems can
communicate
Mail, transaction processing systems like
airlines & banks, www
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
9
Distributed Systems Issues

Operating systems support for distribution






Communication & networks
Transparency
Security
Reliability
Performance & scalability
Programming models
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
10
Networks


Goal: provide efficient, correct, robust message
passing between two separate nodes
Local area network (LAN) – connects nodes in
single building, fast & reliable (Ethernet)



Media: twisted-pair, coax, fiber
Bandwidth: 10-100MB/s
Wide area network (WAN) – connects nodes
across large geographic area (Internet)


Media: fiber, microwave links, satellite channels
Bandwidth: 1.544MB/s (T1), 45 MB/s (T3)
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
11
Network Topologies

Connection of nodes impacts:




Maximum & average communication time
Fault tolerance
Expense
Two basic topologies:


Point-to-point
Bus
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
12
Point-to-Point Network Topologies

Fully-connected



Each message takes one “hop”
Node failure – no effect on communication with others
Expensive – impractical for WANs
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
13
Point-to-Point Network Topologies

Partially connected


Links between some, but not all nodes
Less expensive, less tolerant to failures


Single node failure can partition network
Sending message takes several hops

Needs routing algorithms
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
14
Point-to-Point Network Topologies

Tree structure: network hierarchy

Messages fast between direct descendants


Max message cost?
Not failure tolerant

Any interior node fails – network partitioned
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
15
Point-to-Point Network Topologies

Star network: all nodes connect to central node



Each message takes how many hops?
Not failure tolerant
Inexpensive – sometimes used for LANs
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
16
Point-to-Point Network Topologies

One-directional ring



Given n nodes, max hops?
Inexpensive
Fault-tolerant?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
17
Point-to-Point Network Topologies

Bi-directional ring



Given n nodes, max hops?
Inexpensive
Fault-tolerant? One node? Two?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
18
Point-to-Point Network Topologies

Doubly-connected ring: nodes connected to
neighbors & one more distant



Given n nodes, max hops?
Fault-tolerant?
More expensive
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
19
Bus Network Topologies

Bus nodes connect to common network

Linear bus – single shared link




Nodes connect directly to each other via bus
Inexpensive (linear in # of nodes)
Tolerant of node failures
Ethernet LAN
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
20
Bus Network Topologies

Ring bus – single shared circular link

Same technology & tradeoffs as linear bus
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
21
Principles of
Network Communication

Data broken into packets

Basic unit of transfer

Packets sent through network
Computers & routers at switching points control
packet flow

Road analogy:





Packets = cars
Network = roads
Computer = traffic lights (intersection)
Too many packets on shared link/node = traffic jam
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
22
Communication Protocols


Protocol: agreed-upon rules for
communication
Protocol stack: layers that comprise
networking software

Each layer N provides service to layer N+1
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
23
Traditional Layers







Application layer – applications that use the net
Presentation layer – data format conversion
(big/little endian)
Session layer – implements communication strategy
(e.g., RPC)
Transport layer – reliable end-to-end communication
Network layer – routing & congestion control
Data link control layer – reliable point-to-point
communication over unreliable channel
Physical layer – electrical/optical signaling across “wire”
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
24
TCP/IP Protocol Stack

Internet standard protocol stack


TCP: reliable protocol – packets received in order
UDP (user datagram protocol) – unreliable

No guarantee of delivery
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
25
Packet Format



Contains all info
needed to recreate
original message
Packets may arrive out
of order = need
sequence number
Data segment contains
headers for higher
protocol layers &
application data
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
26
Summary



Virtually all computer systems contain
distributed components
Networks connect them
Key tradeoffs:



Speed
Reliability
Expense
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
27