Chapter 15: Networks - SIUE Computer Science

Transcript Chapter 15: Networks - SIUE Computer Science

Chapter 15: Networks
Data communication networks are set up in
two basic configurations.
The mesh configuration uses direct, point-topoint connections between each pair of
communicating devices.
While this approach guarantees a direct connection between any
pair of devices, the amount of cabling and I/O hardware required
at each device makes it impractical in most situations.
The alternative is to establish a broadcast network in which
network lines are shared.
Simple configurations
associated with the broadcast
approach include the ring and
bus topologies, at left and
right, respectively.
Chapter 15
Networks
Page 162
Local Area Networks
LANs are privately owned networks containing perhaps dozens of
devices.
Example: Ethernet
Computer
Computer
Bus Cable
Computer
Computer
Computer
Computer
Ethernet uses a bus configuration and a protocol for accessing the bus called
CSMA/CD.
• CS - Carrier Sense: Each machine constantly listens to the traffic that’s
passing by on the bus.
• MA - Multiple Access: Every machine has equal access to the communication
medium (i.e., the bus).
• CD - Collision Detection: Each machine is capable of detecting
whether its transmitted message “collided” with that of another
Chapter 15
Networks
machine, thus corrupting the message and forcing a retransmission.
Page 163
Ethernet Carrier Sense: Incoming Traffic
As messages pass by, each machine examines the first few bits of
the message, the “address” of the message, and determines
whether or not the message is intended for itself.
Bus Cable
message
Computer
Computer
Computer
Computer
Computer
Computer
message
When the destination machine sees its
address in the message’s prefix, it copies
the passing message as the original
proceeds down the bus.
Chapter 15
Networks
Page 164
Ethernet Carrier Sense: Outgoing Traffic
When a machine wants to transmit a message, it waits a systemdependent amount of time, using its carrier sense to see if any
traffic appears on the bus. If not, it transmits its message and
“hopes” that no collision occurs.
Bus Cable
Computer
Computer
Computer
Computer
Computer
message
Computer
When the transmitting machine detects
no passing traffic for a certain time
interval, it places its message on the bus.
Chapter 15
Networks
Page 165
Ethernet Carrier Sense: Colliding Traffic
After a machine transmits a message, it continues to use its carrier
sense to see if there’s any difference between its transmitted
message and the message on the bus. If so, it interprets the
problem as a collision.
Bus Cable
Computer
Computer
Computer
Computer
When each transmitting machine
detects that its message has been
corrupted, it waits a random interval of
time, and then retransmits.
Computer
Computer
Chapter 15
Networks
Page 166
A LAN Alternative: Token Ring
Collisions tend to exacerbate traffic problems on congested
Ethernet LANs, so an alternative to the CSMA/CD approach is
desirable.
Ring
Computer
Computer
Computer
message
Computer
TOKEN
Computer
Computer
Computer
message
TOKEN
message
Computer
Computer
Computer
Computer
Computer
Computer
Token Ring uses a ring topology, with a specially formatted “token” message
perpetually traversing the ring.
When a machine wishes to transmit, it merely waits for the token to arrive,
removes it, and transmits its message.
When its message returns to the transmitting machine, it’s removed
from the ring, and the machine places the token back on the ring.
Chapter 15
Networks
Page 167
Wide Area Networks
WANs are large collections of smaller networks, with special
interconnection devices known as “routers” to make adjacent
sub-networks compatible.
Router
Router
Router
Router
Router
Router
Chapter 15
Networks
Page 168
Switching
Data communications is characterized by two switching
technologies.
Technology #1: Circuit Switching
Once the circuit is established, it is
maintained until one of the endstations
terminates the connection.
Chapter 15
Networks
Page 169
Problems with Circuit Switching
Circuit switching has one great advantage:
once established, the circuit is dedicated,
i.e., a communication line is completely
open until formally terminated.
However, this approach has a number
of serious problems:
• Many networked applications don’t require a dedicated circuit, so reserving a
communication line until an endstation formally terminates it can represent a
serious waste of resources.
• The route originally selected for the circuit may be optimal to begin with, but
may prove to be suboptimal as the communication continues.
• An entire, end-to-end path must be found and reserved before any
communication is allowed between the two endstations; this is definitely not
conducive to many modern applications (e.g., Web surfing, videoconferencing).
• Transmission errors are propagated all the way to the destination,
requiring retransmission across the entire network.
Chapter 15
Networks
Page 170
An Alternative to Circuit Switching
Technology #2: Packet Switching
The source’s message is broken into manageable “packets” that are transmitted
to the destination individually, not necessarily along the same path.
Chapter 15
Networks
Page 171
The Pros and Cons of Packet Switching
Packet switching remedies circuit
switching’s principal problems:
• Lines aren’t dedicated, so their
utilization is higher.
• Messages are “packetized”, so linesharing is reasonably fair.
• Routing may be dynamic, i.e., an
alternate route may be chosen when
traffic patterns change.
• The entire route does not have to be
chosen prior to sending any data.
• Errors aren’t propagated end-to-end.
However, packet switching does have its own set of problems:
• Switches must be programmed to make sophisticated routing decisions.
• Switches must manage memory for queued packets that await forwarding.
• Packets must be prefixed with control headers, increasing overhead.
Chapter 15
Networks
• Endstations must deal with missing packets and out-of-order packets.
Page 172
• Without a dedicated circuit, transmission times become unpredictable.
Multiplexing
To more efficiently utilize a physical medium, multiple higherlevel connections might “share” the medium simultaneously.
Frequency-Division Multiplexing
The spectrum of frequencies transmittable via the physical medium is divided into
several channels (e.g., cable TV).
Time-Division Multiplexing
Each transmitter is allocated a periodic time interval in which to transmit.
Chapter 15
Networks
Page 173
Code Division Multiplexing
Frequency Division
Multiplexing
Everyone gets to
talk at the same
time, but only
across their narrow
channels.
(Commonly used
with copper
cables)
Time Division
Multiplexing
Everyone gets to talk
using the entire
bandwidth, but they
have to take turns
talking.
(Commonly user with
fiber optics)
Code Division Multiplexing
Everyone gets to talk simultaneously, using the entire bandwidth!
They do this by coding their transmissions in a unique fashion (as if
every pair were speaking a different language, and each other
language merely sounds like background noise).
(Commonly used with wireless communications)
Chapter 15
Networks
Page 174
Modems
Digital data must be modulated into analog signals if it’s going
to be transmitted across an analog medium.
After transmission, it must be demodulated back into its original
digital form.
Cables between the workstation
and the modem and between the
modem and the telephone jack
Dial-in pool of 96 modems:
Six terminal servers, each
connecting 16 modems to a LAN
Chapter 15
Networks
Page 175
Modulation and Demodulation
Modulation of the digital signals
m1 and m2 is effected at left via
products with trig functions.
cos(ct)
m1(t)
X
cos(ct) m1(t) +
sin(ct) m2(t)

m2(t)
X
sin(ct)
Upon arrival, the message is
demodulated below via trig
multiplications, trig identities,
and high-frequency filtering.
2cos(ct)
m1(t)+cos(2ct) m1(t)
+sin(2ct) m2(t)
X
cos(ct) m1(t) +
sin(ct) m2(t)
X
m2(t)+cos(2ct) m2(t)
+sin(2ct) m1(t)
FILTER OUT
THE HIGH
FREQUENCIES
m1(t)
m2(t)
2sin(ct)
Chapter 15
Networks
Page 176
Modem Interfaces
The EIA-232D connector connects
a modem to a computer.
• It uses a 25-pin connector, with
each pin having a different
meaning.
• The meaning of each pin is
activated by applying a voltage
across it.
For example...
Pin 20: Data Terminal Ready
(i.e., “Hey! The computer’s ready to
send something to the modem!”)
Chapter 15
Networks
Page 177
Network Protocol Layers
In an effort to simplify networks, they are often organized as
layered hierarchies of protocols, with hardware-intensive
protocols on the bottom and user applications at the top.
Layer 5
Layer 5
Layer 4
Layer 4
Layer 4
Layer 4
Layer 3
Layer 3
Layer 3
Layer 3
Layer 2
Layer 2
Layer 2
Layer 2
Layer 2
Layer 1
Layer 1
Layer 1
Layer 1
Layer 1
Source
Host
Intermediate
Router
Low-Level
Bridge
Intermediate
Router
Destination
Host
Physical Medium
Chapter 15
Networks
Page 178
Communicating Via Layered Protocols
Consecutive network nodes only communicate directly at the
lowest (hardware) layer; to communicate at higher layers,
networking software inserts certain relevant data as headers
and trailers to the message coming from the source.
Layer 5
message
Layer 4
Layer 4
hdr4 message
hdr4 message
Layer 3
Layer 3
hdr3 hdr4 msgB
hdr3 hdr4 msgA
hdr3 hdr4 msgA
hdr3 hdr4 msgB
Layer 2
Layer 2
hdr2 hdr3 hdr4 msgA trl2
hdr2 hdr3 hdr4 msgB trl2
hdr2 hdr3 hdr4 msgA trl2
hdr2 hdr3 hdr4 msgB trl2
Layer 1
Layer 1
Chapter 15
Networks
Page 179
hdr1 hdr2 hdr3 hdr4 msgB trl2
hdr1 hdr2 hdr3 hdr4 msgA trl2
Layered Protocol Models
Several models have been developed to implement protocol
hierarchies for networks.
Reference Model #1: Open Systems Interconnection (OSI)
Application
• End-user protocols, e.g., e-mail, file transfer, Web browsing,
network management, videoconferencing.
Presentation
• Format data according to negotiations between source and
destination; encrypt and decrypt messages.
Session
Transport
• Establish, maintain, and discontinue dialogues between a
source and a destination; synchronize data transfer.
• Detect and handle end-to-end transmission errors; alter
transmission rate when too much congestion is encountered.
Network
• Route messages from their source to their destination; reroute
traffic when heavy congestion is encountered.
Data Link
• Detect and handle transmission errors between consecutive
network devices; control access to the shared medium.
Physical
• Transmit bits across physical medium; determine frequencies
to use when transmitting; specify role of connector pins.
Chapter 15
Networks
Page 180
Reference Model #2: Transmission Control Protocol/Internet Protocol (TCP/IP)
Application
• Analogous to OSI’s Application Layer
TCP
• Analogous to OSI’s Transport Layer
IP
• Analogous to OSI’s Network Layer
Lower Levels • Analogous to OSI’s Physical and Data Link Layers
Chapter 15
Networks
Page 181
The IP Protocol
The Internet Protocol was designed for three primary purposes:
1. Define the data format to be used by messages
travelling through TCP/IP networks.
2. Route the data through the Internet by
selecting appropriate paths.
3. Process packets, generate error messages,
and discard packets in such a way to ensure
“unreliable” packet delivery.
Chapter 15
Networks
Page 182
The IP Header
Version HdrLen
Service Type
Identification
Time To Live
Total Length
Flags
Protocol
Fragment Offset
Header Checksum
Source IP Address
Destination IP Address
Options & Padding (if any)
Version: The version of IP used to create the packet, used by nodes to process it correctly.
HdrLen: The length of the header in 32-bit words (because the Options field has no fixed size).
Service Type: Six bits to represent the relative priority and delay sensitivity of the packet.
Total Length: The length of the entire packet in bytes (16-bit field means a 65,535-byte max).
Identification: All fragments of the same packet have the same ID number.
Flags: Don’t-Fragment flag and More-Fragments flag.
Fragment Offset: Offset from start of packet (in bytes) of current fragment.
Time To Live: Length of time (in seconds) the packet may stay in the Internet.
Protocol: Global ID # of the protocol used to create the packet (e.g., TCP).
Header Checksum: Error-checking sum of all of the 16-bit values in the header.
Source IP Address: 32-bit IP address of the packet’s original source.
Destination IP Address: 32-bit IP address of the packet’s final destination.
Options & Padding: Options include: No-operation-just-align; Military-security-application;
Loose-source-routing; Record-route; Strict-source-routing; Record-internet-timestamps.
Chapter 15
Networks
Page 183
IP Addresses
There are three principal classes of IP addresses, with all
endstations on the same network given a common prefix:
CLASS A - for networks with at least 216 (65536+) endstations:
Host ID
0 Network ID
CLASS B -for networks with between 28 and 216 (256-65535) endstations:
10
Network ID
Host ID
CLASS C - for networks with less than 28 (0-255) endstations:
110
Network ID
Host ID
Chapter 15
Networks
Page 184
The Domain Name System (DNS)
A hierarchical system of domains and
subdomains has been established to
permit stations to communicate with
other stations by “name”.
A station contacts its server, who knows
the location of the required domain
server, who knows the location of the
required subdomain server, etc., until
the required endstation is located,
whereupon its IP address is returned.
Chapter 15
Networks
Page 185
Electronic Mail
User Sends Mail
User
Interface
User Reads Mail
Outgoing
Mail Spool
Area
Mailboxes
for Incoming
Mail
Client
TCP Connection
(Background
Transfer) for Outgoing Mail
Server
(To Accept
Mail)
TCP Connection
for Incoming Mail
E-mail is considered low priority traffic, so it’s only transmitted directly if the network is
deemed to be relatively uncongested. The background transfer process sweeps through
the spool area periodically (typically, 2-4 times an hour). Whenever it finds an undelivered
message, the background process increases the message’s priority and attempts delivery.
Alias
Database
User Sends Mail
User
Interface
User Reads Mail
Alias Expansion
& Forwarding
Mailboxes for
Incoming Mail
Outgoing
Mail Spool
Area
Client
TCP Connection
(Background
Transfer) for Outgoing Mail
Server
(To Accept
Mail)
TCP Connection
for Incoming Mail
Rather than resorting to the Domain Name System for each outgoing message, and
to accommodate locally used aliases for incoming messages, most systems provide
mail forwarding software with a mail alias expansion mechanism.
Chapter 15
Networks
Page 186
File Transfer Protocol (FTP)
Client System
control
process
Server System
One active TCP connection
before and after data
transfer, just for control.
Operating System
control
process
Operating System
TCP/IP Internet
Client System
data
transfer
control
process
Server System
Two active TCP
connections during data
transfer, one for control
and one for data.
Operating System
control
process
data
transfer
Operating System
TCP/IP Internet
Chapter 15
Networks
Page 187
Firewalls
To ensure the security of a private network,
“firewall” programs have been developed.
A common approach is to filter incoming and
outgoing packets based upon header
information, and to use an application gateway
to inhibit application-specific traffic.
packet
Incoming packets for bad
address/port combinations are
rejected (e.g., no outsider can
“finger” an internal site).
packet
Incoming or outgoing
packets are rejected on
the basis of size or
payload info.
packet
My Secure
Network
packet
Outgoing packets for bad
address/port combinations are
rejected (e.g., no insider can “http”
an external site).
Chapter 15
Networks
Page 188
Chapter 16: The World Wide Web
The World Wide Web applies point-andclick hypermedia application software
to facilitate accessing documents on the
Internet via TCP-based protocols.
Click on this piece of
Type in and
a keyword
hypertext,
you’re
and
clickto...
the “Go!”
taken
pushbutton, and
Click on thisyou’re taken to...
pushbutton, and you’re
taken to...
And with additional downloaded
software, elaborate Web sites that
include more than text and simple
images can be accessed.
Chapter 16
The World Wide
Web
Page 189
HyperText Transport Protocol (HTTP)
HTTP is the software defining the format of requests relayed from a Web browser to a
Web server, as well as the replies relayed from the server to the browser.
HTML (HyperText Markup Language) is the standard used to
write Web pages; it doesn’t require specific formatting
instructions, so two browsers may display a page differently.
<html><head><title>Welcome to IEEExpl</title></head> <body>
<table width="550" border="0" cellspacing="0" cellpadding="0" align="center"> <tr><td valign="top">


<img src="/images/subidinfmast_01.gif" width="550" height="39“
vspace="3"
hspace="0" border="0" alt="IEEE
xpl Subscription Access Information“
usemap="#Map">
<map name="Map"> <area shape="rect" coords="6,5,182,31" href="http://ieeexpl.ieee.org"> </map>
 
<table width=510 border=1 cellspacing=0 cellpadding=5 bordercolor=#CCCCCC align=center><tr><td>

Your institution subscribes to:</td></tr><tr><td bgcolor=#E8E8E8>
   
Search Xplore Database</td></tr></table> 
<table width=510 border=1 cellspacing=0 cellpadding=5 bordercolor=#CCCCCC align=center><tr><td>
Your
institution subscribes to:
</td>
</tr>
<tr>
<td bgcolor=#E8E8E8>   


IEEE All Society Periodicals Package (ASPP)
</td>
</tr>
<tr>
<td bgcolor=#FFFFFF>
<blockquote>
<blockquote>
Your
online subscription includes access to the
abstracts and full-text
of IEEE journals, transactions, and magazines published since 1998:

   

<a href=/xpl/ieeejrns.jsp?hr=1>IEEE journals, transactions, and magazines</a>

</blockquote>
</blockquote>
</td>
</tr>
</table> 
<table width="500" border="0" cellspacing="0" cellpadding="0" align="center"><tr> <td> 
In addtion to the above, you may purchase individual IEEE journal/magazine articles and
conference papers that
are not included in your institution's online subscription. If you want a copy of an article or paper, first check with
your librarian for a copy available locally.
Any questions? <a href="/xpl/techform.jsp">
Contact IEEE Customer Service</a>.</td></tr></table> 
<table width="500" border="0" cellspacing="0" cellpadding="0" align="center"> <tr> <td valign="top"> <div align="right">
 <A href='javascript:window.close();'>
<img src="/images/backbutton.gif" width="165" height="34" vspace="0" hspace="0" border="0" alt="Close this Window"></A>
</div></td></tr></table></td></tr></table></body></html>
Chapter 16
The World Wide
Web
Page 190
Extensible Markup Language (XML)
Unlike HTML, XML allows users to include content-specific
information in their files, facilitating its being formatted to suit
various display devices.
A job vacancy at the department of
Tourism is added to the job database.
XML technology stores the
data separately from the
presentation, allowing for a
variety of platforms.
The vacancy is displayed on
the job center kiosk...
...can be accessed by
mobile devices...
...and is displayed on
the Department of
Tourism website.
Chapter 16
The World Wide
Web
Page 191
Uniform Resource Locators (URLs)
A URL specifies three pieces of information:
1. Type of file transfer
Different types of file transfer:
2. Name of computer
http://
- hypertext transfer protocol
3. Name of file
ftp://
- file transfer protocol
telnet:// - opens a telnet session
gopher:// - transfer file from a gopher server
mailto: - open a mail session
For example:
http://www.cs.siue.edu/undergrad/BS/files/prerequisites.pdf
1. http:// - type of file transfer
2. cs.siue.edu - name of the computer
3. /undergrad/BS/files/prerequisites.pdf - location of the file on the computer
Chapter 16
The World Wide
Web
Page 192
Web Browsing
Client software running
on the workstation
HTML
Interpreter
Java
Interpreter
HTTP
Client
Display Driver
Input from
mouse &
keyboard
Interpreting
downloaded
Web pages
and files
Browser
Controller
Output to
user’s
display
FTP
Client
Issuing requests
for external files
Network Interface
Communications
with remote
Web server
Chapter 16
The World Wide
Web
Page 193
Internet Search Engines
Search engines use “spider”
programs to “crawl” through
the Web, building a list of
words.
Some follow every link on
every home page.
Some ignore links that lead to
graphics, sound, or animation
files, or to newsgroups.
Some concentrate primarily on
the most popular Web pages.
Chapter 16
The World Wide
Web
Page 194
Comparing Search Engines
Share of Searches
Searches Per Day (in millions)
16
6
13
Google
Yahoo
MSN
AOL
Ask
Other
91
28
60
Percentage of Search Results
1.8
Security Issues
Red = distribute adware, send a high
volume of spam, or make unauthorized
changes to a user's computer
Yellow = send a high volume of "nonspammy" email, display many popup
ads, or prompt a user to change
browser settings
1.4
1.7
1.5
2.3
1.9
3.6
1.9
0
1
1.8
1.5
2
3
4
5
6
Chapter 16
The World Wide
Web
Page 195
Chapter 17: Limitations of Computing
What problems cannot be solved on a computer?
What problems cannot be solved on a computer in a
“reasonable” amount of time?
These aren’t just philosophical questions; their answers will
determine how practical it is to pursue computer-based
solutions to real-world problems like hurricane prediction,
disease control, and economic forecasting.
Chapter 17
Limitations of
Computing
Page 196
Computability
To examine the limits of what it is possible to do with a
computer, Alan Turing (1912-1954) developed a simplified
mathematical model, called a Turing machine.
A Turing machine consists of three parts:
1)
A tape of cells from which symbols can be read and into
which symbols can be written,
2)
A read/write head that moves back and forth across the
tape, reading the symbol inside the current cell and/or
writing a new symbol into the current cell, and
3)
A control unit that keeps track of what “state” the
machine is in, and uses that state and the current
symbol under the read/write head to:
a)
Determine which symbol to place in the current cell,
b)
Determine whether to move the read/write head one
cell to the left or right, and
Determine the next state of the machine.
c)
Control
Unit
Read/Write
Head
Tape
Chapter 17
Limitations of
Computing
Page 197
State Transition Diagram
A state transition diagram may be used to
define a Turing machine.
State:
START
*
1
0
1
*
Each // transition signifies reading  on
the tape, replacing it with , and then
moving the read/write head in the 
direction.
State:
ADD
*
1
0
1
*
State:
CARRY
*
1
0
0
*
State:
NO CARRY
*
1
1
0
*
State:
NO CARRY
*
1
1
0
*
State:
RETURN
*
1
1
0
*
State:
RETURN
*
1
1
0
*
State:
RETURN
*
1
1
0
*
State:
RETURN
*
1
1
0
*
*/*/L
START
1/0/L
ADD
CARRY
0/1/L
*/*/R
0/1/L
NO CARRY
*/1/L
0/0/L,
1/1/L
*/*/R
HALT
*/*/-
1/0/L
OVERFLOW
*/*/R
RETURN
0/0/R,
1/1/R
The state transition diagram above defines
a Turing machine that increments a binary
number on the tape by one.
State:
HALT
*
1
1
0
*
Chapter 17
Limitations of
Computing
Page 198
The Church-Turing Thesis
Computer scientists commonly accept the Church-Turing Thesis,
which states that the set of functions that can be calculated on a
computer is exactly the same as the set of functions for which a
Turing machine can be devised.
There are problems that have been proven to be non-computable (i.e., no
Turing machine can be devised to calculate their solutions).
One classical example:
The Halting Problem
Given a program with a set of
input values, does the program
halt on that input, or does it get
stuck in an infinite loop?
Chapter 17
Limitations of
Computing
Page 199
Complexity
The time complexity of an algorithm is a measure of how many steps are executed
when the associated program is run.
void printA()
{
cout << 0 <<
cout << 0 <<
cout << 0 <<
cout << 0 <<
}
endl;
endl;
endl;
endl;
Number of Output
Statements Executed: 4
Time Complexity: O(1)
void printB()
{
int i;
for (i = 1; i <= 100; i++)
cout << 0 << endl;
}
void printC(int n)
{
int i;
for (i = 1; i <= n; i++)
cout << 0 << endl;
}
void printD(int n)
{
int i,j;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
cout << 0 << endl;
}
Number of Output
Statements Executed: 100
Time Complexity: O(1)
Number of Output
Statements Executed: n
Time Complexity: O(n)
Number of Output
Statements Executed: n2
Time Complexity: O(n2)
The “big-O” notation
provides information
regarding the program’s
“order of complexity”.
O(1) indicates that the
execution time doesn’t relate
to the size of the number n.
O(n) indicates that the
execution time increases
linearly as n increases.
O(n2) indicates that the
execution time increases
quadratically as n increases.
Chapter 17
Limitations of
Computing
Page 200
Logarithmic/Polynomial/Exponential
An algorithm is said to have logarithmic time complexity if the number of steps in
its execution is bounded by some logarithmic function:
k log2(n)
Essentially, this means that doubling the size of the problem (n) would only
increase the execution time by a constant amount (k).
An algorithm is said to have polynomial time complexity if the number of steps in
its execution is bounded by some polynomial function:
aknk+ak-1nk-1+…+a2n2+a1n+a0
An algorithm is said to have exponential time complexity if the number of steps in
its execution is bounded by some exponential function:
k(2n)
Essentially, this means that increasing the size of the problem (n) by one would
double the execution time.
log2(n)
n
n2
n3
2n
2
5
25
125
31
3
10
100
1000
1024
4
20
400
8000
1048576
Chapter 17
Limitations of
Computing
Page 201
Big-O
An algorithm’s time complexity is dominated by its
most significant term.
For example, an algorithm that executes in time n2+10n is
considered to be O(n2) because, as n increases, the n2 term
ultimately dominates the n term.
Additional examples:
5n + n2 + 0.125n3 is O(n3)
log2(n) + n2 + 2n is O(2n)
100n + max(n2, 1000 - n3) is O(n2)
n3 - ⅞(n3 - 80n2 - 800n) is O(n3)
1000000 + 0.000001log2(n) is O(log2(n))
Chapter 17
Limitations of
Computing
Page 202
P and NP Problems
A problem is said to be a P problem if it can be solved with
a deterministic, polynomial-time algorithm. (Deterministic
algorithms have each step clearly specified.)
A problem is said to be an NP problem if it can be solved with a
nondeterministic, polynomial-time algorithm.
In essence, at a critical point in the NP problem’s algorithm, a
decision must be made, and it is assumed that some magical
“choice” function (also called an oracle) always chooses correctly.
For example, take the Satisfiability Problem:
Given a set of n boolean variables b1, b2, … bn, and a boolean
function f (b1, b2, …, bn), are there any values that can be assigned
to the variables so the function value will evaluate to TRUE?
To try every combination of
boolean values would take
exponential time, but the
nondeterministic solution at
right has polynomial time
complexity.
for (i = 1; i <= n; i++)
bi = choice(true, false);
if (f(b1, b2,…, bn) == true)
satisfiable = true;
else satisfiable = false;
Chapter 17
Limitations of
Computing
Page 203
The Knapsack Problem
The Knapsack Problem involves
taking n valuable jewels J1, J2,…,Jn,
with respective weights w1, w2,…,
wn, and prices p1, p2,…, pn, and
placing some of them in a knapsack
that is capable of supporting a
combined weight of M.
The problem is to pack the
maximum worth of gems without
exceeding the capacity of the
knapsack.
(It’s not as easy as it sounds; three
lightweight $1000 gems might be
preferable to one heavy $2500 gem,
and one 20-pound gem worth a lot
of money might be preferable to
twelve 1-pound gems that are
practically worthless.)
A Nondeterministic Polynomial
Solution:
TotalWorth = 0;
TotalWeight = 0;
for (i = 1; i <= n; i++)
{
bi = choice(true, false);
if (b1 == true)
{
TotalWorth+= pi;
TotalWeight += wi;
}
}
if (TotalWeight <= M)
cout << “Woo-hoo!” << endl;
else
cout << “Doh!” << endl;
Chapter 17
Limitations of
Computing
Page 204
Supplement: Computer Ethics
How dependable is computer technology?
In 1994, Intel’s new Pentium processor was determined
to have a flaw…
4195835–(4195835*3145727)/3145727 = 256
The Problem: Five values were left out of a table of 1,066 on the
chip. Those five values were looked up when
certain divisions were performed and, since they
weren’t there, the values were interpreted as zeros.
The Response: Initially denying that there was any error at all, Intel
ultimately offered to replace customers’ chips with
corrected versions.
The Reaction: Intel’s competitors condemned Intel, but all
of the press Intel received, while negative,
turned it into a household name.
Supplement
Computer Ethics
Page 205
Therac-25
In the mid 1980’s, the Therac-25, a computerized radiation therapy
machine from Canada’s AECL, was determined to have a software
bug that resulted in several patients receiving hundreds of times
the proper amount of radiation, causing three deaths.
Supplement
Computer Ethics
Page 206
Cell Phones
The U.S. Food & Drug Administration
and the American Cancer Society
have determined that the evidence is
inconclusive regarding the link
between cell phone use and brain
cancer.
Somewhat less doubtful is the link
between male cell phone use and
reduced sperm count (primarily due to
the phone being kept in pants pockets).
Supplement
Computer Ethics
Page 207
Unsolicited Commercial E-Mail
Various techniques have been developed
for dealing with the “spam” that plagues
people’s e-mail accounts.
Blacklists
One very effective technique for blocking spam is to
maintain a blacklist of spam sources, and to refuse all
e-mail from those sources.
The problem: Aggressive blacklist policies might list
sources that send legitimate e-mail as well as spam.
Whitelists
Instead of trying to block spam while allowing everything else, whitelist
software blocks everything except messages from already known, accepted
senders, thus changing e-mail from an open system to a closed one.
Whitelists typically allow e-mail from everyone in a user's existing address
book. Other, unknown senders receive an automated reply, asking them to
take further action, such as explain who they are. Or senders may be asked to
identify a partially obscured image of a word. A person can make out the word,
but automated spammer software can't.
Supplement
Computer Ethics
Page 208
Identity Theft
Rank
Victim State
Victims per
100,000
Population
Number
of
Victims
9,113
1
Arizona
147.8
2
Nevada
120.0
2,994
3
California
113.5
41,396
4
Texas
110.6
26,006
5
Florida
98.3
17,780
6
Colorado
92.5
4,395
7
Georgia
86.3
8,084
8
New York
85.2
16,452
9
Washington
83.4
5,336
10
New Mexico
82.9
1,621
Technological advances in
recent years have facilitated
the ability of criminals to
obtain personal information
about people and to
unlawfully gain access to their
financial accounts.
Rank
Victim State
Victims per
100,000
Population
Number
of
Victims
3,700
26
Tennessee
61.3
27
Alabama
60.3
2.774
28
Ohio
59.9
6,878
29
Kansas
58.8
1,626
30
Rhode Island
57.6
615
31
Alaska
57.3
384
32
South Carolina
55.7
2,408
33
Minnesota
55.6
2,872
34
Arkansas
54.7
1,537
35
Louisiana
52.6
2,256
11
Maryland
82.9
4,656
36
Mississippi
51.3
1,494
12
Illinois
78.6
10.080
37
Nebraska
49.1
868
13
Oregon
76.1
2,815
38
Idaho
49.0
718
14
New Jersey
73.3
6,394
39
Hawaii
47.8
615
15
Virginia
67.2
5,137
40
New Hampshire
46.1
606
16
Michigan
67.2
6,784
41
Montana
45.9
434
17
Delaware
66.7
569
42
Wisconsin
45.6
2,536
18
Connecticut
65.8
2,305
43
Wyoming
42.3
218
19
Pennsylvania
64.9
8,080
44
Kentucky
42.0
1,766
20
North Carolina
64.9
5,748
45
Maine
39.7
525
21
Missouri
64.2
3,753
46
West Virginia
39.3
715
22
Massachusetts
63.7
4,102
47
Iowa
34.9
1,041
23
Oklahoma
63.0
2,254
48
South Dakota
30.2
236
24
Indiana
62.2
3,928
49
North Dakota
29.7
189
25
Utah
61.8
1,577
50
Vermont
28.5
178
* 2006 FTC Statistics
Supplement
Computer Ethics
Page 209
Electronic Monitoring
To combat employee “cyberslacking”, employers
are increasing making use of monitoring software
that records how employees are using their office
communication capabilities.
Legally, the courts have consistently defended the right of
employers to monitor telephone conversations, voice-mail
messages, e-mail, and Web browsing of employees using
employer-provided equipment.
Supplement
Computer Ethics
Page 210
The Blue Screen of Death
A bug in a software package may cause the program
to access or alter memory inappropriately, causing
this program (or an entirely separate program) to
crash later.
“A broad range of conditions can cause a Fatal Exception
error. As a result, troubleshooting a Fatal Exception error
can be difficult.”
- Microsoft’s “helpful” documentation
A recent study showed that 70% of these errors are
caused by device drivers, the software that handles the
communication between a computer’s core operating
system and its hardware.
Because device drivers tie the computer’s software and
hardware together, they have special access privileges
within the machine that most software doesn’t.
The likelihood that others are experiencing the same problem with the
same hardware is usually high, so hardware manufacturers frequently
post updated versions of the device drivers, which address the problem.
Supplement
Computer Ethics
Page 211

Chapter 15: Networks - SIUE Computer Science

Transcript Chapter 15: Networks - SIUE Computer Science

Directory