Transcript Computer Networks

Topical lectures
June 2007
01
11
010
001
1101
1110
11001
01011
110110
001101
1111111
0111000
11101010
01001110
110111001
000101101
1111010001
0101111100
111101001111
010110000101
Introduction to
computer networks
Sander Klous
Acknowledgements:
W
H
t

• Cees de Laat
• Jan Just Keijser
• Oscar Koeroo
Z
0
Reference:
• Cisco systems – CCNA
ISBN: 1-58720-095-3
Course overview
• Introduction
• Routing
- ARPA net
- IP networks
- How the web was born
- Address resolution
- Standard bodies
- Routing protocols
• Hardware
- VLANs
• Protocols
- Hubs and Switches
- Collision detection
- TCP and UDP
- OSI Layers
- Sockets and NAT
• Topology
• Network Security
- Ethernet (LAN)
- Firewalls (briefly)
- Error discovery
- (A)symmetric cryptography
- Wide Area Networks
- Public Key Infrastructure
2
ARPA net 1969
• Defense Advanced Research
Projects Agency (DARPA)
- Military part (MILNET)
- Research part (ARPANET)
• First two IMPs (Interface
Message Processors):
- UCLA (August 30, 1969)
- Stanford Research Institute
(October 1, 1969)
• Decommissioned in 1989
3
ARPA net 1977
4
Original proposal
of the WWW
• Gopher (University of Minnesota)
• Tim Berners-Lee
- Enquire (HyperText)
- TCP/IP
- DNS
- Uniform Resource Locator (URL)
• Mike Sendall
• Newsgroup announcement:
6 August 1991, 22:37
http://groups.google.com/group/alt.hypertext/msg/395f282a67a1916c
5
Google hits, August 14 2003
• 1.1 Billion internet users in 2007 (± 17% of the world, ± 50% in US and EU)
http://www.internetworldstats.com/stats.htm
• 11.5 Billion web pages (2005)
6
Standard bodies
• Institute of Electrical and Electronics Engineers (IEEE)
- Advancement of technology related to electricity
- IEEE 802.X Ethernet standards
• Internet Engineering Task Force (IETF)
- Rob Blokzijl ISOC member
- Develops and promotes internet standards
Requests for Comments (RFCs)
- In close cooperation with W3C
• World Wide Web Consortium (W3C)
- Founded by Tim Berners-Lee, director
- International standards organization for WWW
7
Internet overview
8
Simple network
9
Simple network internals
10
Collision detection
CSMA:
Carrier Sense Multiple Access
11
Switched networks
• Occupancy < 30%
• Switched Networks
- Half duplex
- 100%
• New network cards
- Full duplex
- 2 x 100%
12
OSI Layers
13
OSI Layer 2: Ethernet
• DIX: DEC, Intel and Xerox
• MAC: Media Access Control = number of your Ethernet card
• FCS: Frame Check Sequence – See CRC
• DSAP: Destination Service Access Point
• SNAP: Sub network Access Protocol
14
Ethernet Frame Specification
• Note: error discovery  error recovery
• Maximum Frame Length = 1500 (see MTU specs)
15
Check sum – bidirectional parity
• Works well for single bit errors
16
Cyclic Redundancy Check
• Polynomial division
• Based on Galois Field Theory, GF(2)
- Coefficients either 0 or 1
- Division results in Exclusive OR
Quotient
Divisor
Remainder
17
Partially from Tanenbaum
Computer Networks
ISBN 0-13-038488-7
Wide Area Networks
Router:
Connecting different OSI layer 2 protocols
PPP: Point to Point Protocol
18
WAN Internals
• Channel Service Unit (CSU)
• Customer Premises Equipment (CPE)
• High Level Data Link Control (HDLC)
• Asynchronous Transfer Mode (ATM)
19
Maximum Transmission Unit (MTU)
• Fragmentation, equal sized packages
• Jumbo frames  Configuration challenge
- Avoid fragmentation and reassembly
- Avoid too much overhead
20
Multiple links: Frame Relay
• Frame Relay Protocols
• Telecom Operator Agreements
• See also Border Gateway Protocol (BGP)
21
OSI Layer 3: Networking
• Internet Protocol (IP) numbers
• In Europe, policies are managed by RIPE
Originally (1997) from a NIKHEF office, now at Singel 258
• Three classes of networks
22
IP network
150.1.0.1
150.2.0.1
150.1.0.2
150.2.0.2
6 Class B networks
150.3.0.1
150.4.0.1
23
150.4.0.2
Subnets
• Split host identification in two parts:
- Subnet
- Host ID
• Splitting at bit level
Nr of bits available:
24
IP network with subnets
150.150.1.1
150.150.2.1
150.150.1.2
150.150.2.2
1 Class B network
150.150.3.1
150.150.4.1
150.150.4.2
25
Subnet calculation
Number of masked bits (network + subnet)
26
Boolean subnet calculations
Note, suppose your host definition is:
• 199.1.1.100/27
• Subnet addresses start at:
• Subnet mask: 255.255.255.224
• Number of subnets: 23 – 2 = 6
0, 32, 64, 96, 128, 160, 192, 224
• Your subnet range is:
• Number of hosts per subnet: 25 – 2 = 30
97 – 126
96 and 127 are reserved addresses
Private network ranges
27
Address Resolution Protocol (ARP)
• Ethernet does not use IP numbers
• Ethernet needs the MAC address
• Address Resolution Protocol ties them together
28
Ethernet route discovery
• Building Address Tables
29
Switch routing
30
Redundant links
• Avoid loops at all costs
- Additional hops 
• Spanning Tree Protocol (STP)
31
Rerouting
32
Spanning Tree Protocol rules
1. Decide which switch is the root switch
-
Based on priority (set manually)
-
Based on switch MAC address
2. All ports of root switch are open
3. All ports with shortest route to root switch are open
4. In case an existing route fails: rerun procedure
•
Convergence takes about 50 seconds
Improved version: (Rapid Spanning Tree Protocol)
33
WAN Routing: Border Gateway Protocol (BGP)
• Based on Telecom Operator policies
• Each operator has an autonomous system (AS)
• Avoid loops at all costs (based on AS number)
• Note that routers 34
work at OSI Layer 3 – IP numbers
Link state protocol (WAN spanning tree)
• Distance Vector Protocols
• Shortest Path First
Vertex
• AKA
Dijkstra’s Algorithm
- Weighted links (Euros)
• Build routing table
- Closest first
- Who is your neighbor?
• List of all routes
- In all routers
35
Dijkstra’s algorithm
Graph (V), where V is a set of vertices (vi)
1.
The length of a path from any vertex vk to a vertex v0 is l (vk)
-
So l (v0) = 0, initialize all other lengths l (vk) to 
2.
Start from a vertex vj (j=0) and consider all unlabeled neighbors (yi)
3.
Replace l (yi) with min{ l (yi), l (vj) + w( {vj, yi} ) }
1.
Where w( {vj, yi} ) is the weight of the link between vj and yi
4.
Choose the smallest value from all yi and label it vj+1
5.
Include the route from v to v1 as shortest path
6.
Add all unlabeled neighbors from vj+1 to the set (yi)
7.
Increase counter, j=j+1 and repeat procedure from step 4
8.
Algorithm is completed when all vertices are included
36
SPF Scalability – Topology Summarization
• Divide network in areas
• Router 3 is an intersection
• Topology
summarization
37
SPF Scalability – Route Summarization
• Classless inter domain routing (CIDR)
• Aggregate routes at ISP level
• Example below: all 198.* class C networks are ISP 1
Routing Information Protocol – RIP (hop counting)
Open Shortest Path First – OSPF
IGRP – Interior Gateway Routing Protocol (Cisco)
EIGRP –38Enhanced IGRP (Cisco)
Route poisoning
• In SPF, routers publish information about best route
• What happens if a route fails?
- Remove it from the table
- But…
Route poisoning
How to update other routers?
39
Route poisoning
Horizon splitting
• Counting to infinity
Horizon splitting
40
Virtual LAN introduction
• A VLAN is essentially a broadcast domain.
• Two machines on different VLANs require a layer 3
device for communication (i.e. a router).
• Two machines on the same VLAN require a layer 2
device for communication (i.e. a switch).
41
VLAN in real life
• NIKHEF: normal network and guest network (security)
- VLANs are often combined with subnet masks
• ATLAS trigger: redundancy, VLANs and MSTP  Jos
42
Fine grained security at layer 3
• Access control lists (ACLs)
43
OSI Layer 4: Transport Protocols
• Transmission Control Protocol (TCP)
• Routing based on Internet Protocol (IP)
44
}
TCP/IP
TCP/IP basics
• Mixing transfer and network layer
• Packages contain source and destination IP address
• Send request and provide reply address
• Most features are symmetric
45
Working with
acknowledgements
Source Port
Destination Port
Sequence Number
Acknowledgement Number
Length
Reserved
Code bits
Checksum
Window
Urgent
Options
Data
46
Working with sessions
• Initialize TCP session
- With arbitrary sequence number
- Sessions are synchronized in two directions
• Connection is established, sequence synchronized
- From that moment, sequence = total nr of bytes sent + offset
47
Acknowledgements in detail
• Agreement to confirm reception after X bytes.
- X bytes is called the window (size)
- In the example below: X = 3000
48
Error recovery
• Re-transmission on “No Data” Acknowledgement
• Timeout trigger re-transmission
• Package reordering
49
Window size
Sliding windows, congestion control
Slow start
Time
• Successful transfer
- Window size increases
- Reduce latency effects
• Failed transfer
- Window size reduces
• Window size updates are asynchronous
50
Socket concept
• Multiplexing on different ports
51
Network Address Translation (NAT)
• Provide internet access to private networks
• Changing IP number
and port number
52
User Datagram Protocol (UDP)
• UDP for real-time applications
UDP Header:
Source
Destination
Length
53
Checksum
Well known applications
• Running in parallel on different ports
• A socket consists of: (IP number, protocol, port)
54
Security at layer 4+
• Firewalls
- Expensive, inspection at layer 4+ requires a lot of resources
• Protection against internet worms
- Worms spread through vulnerabilities in applications
• Protection against Denial Of Service attacks
- Many requests to the same application make it unresponsive
• Distributed Denial Of Service attacks
- Attack the application from many different machines
- Avoids blocking the attack based on IP address
55
Firewall types
• First generation
- Packet inspection
- Check IP address and port number and filter
• Second generation
- State full firewall (i.e. state aware)
- Distinguishes between existing and new connections
• Third generation
- Proxy based firewalls
- Application aware
- Inspects traffic on application specific features
56
From Tanenbaum
Computer Networks
ISBN 0-13-038488-7
Cryptography
• Cryptography: Dk ( Ek (P) ) = P
- D = Decryption algorithm, E = Encryption algorithm and k = key
- P = Plain text
• Kerckhoff’s principle:
- All algorithms should be public, only keys are secret
• Symmetric (Asymmetric) key algorithms:
- Same (Different) key is used for encryption and decryption
• Examples of symmetric key algorithms
(based on substitutions and permutations):
- (Triple) DES = Data Encryption Standard
- AES = Advanced Encryption Standard
57
AES algorithm introduction
S box
(16 x 16) lookup
1
Shift rows with increased steps
2
Combine with secret key
Multiply with a polynomial
3
58
4
Asymmetric key algorithms
• Weak point in AES: distribution of the key
- If the key is known, Dk and Ek are known
• Solution: use different keys for Encryption/Decryption
- Still: Dk2 (Ek1 (P) ) = P
• Make Ek1 publicly available
- It should be very difficult to deduce Dk2 from Ek1
• Additional complication
- Part of the information is out in the open (k1)
• Examples of asymmetric key algorithms:
- DSA = Digital Signature Algorithm
- RSA = Rivest, Shamir and Adleman (MIT)
59
RSA overview
• Choose two large prime numbers (1024 bits or more)
• Compute n = p x q and z = (p - 1) x (q - 1)
• Find a number d smaller than z
- Where d and z should not have a common factor
• Find a number e
- Where e x d = 1 mod z
i.e. 1 + (k x z)
• You need (e, n) to encrypt and (p, n) to decrypt
- See example on next page
• It is extremely difficult to find p and q from n (factorization)
60
Toy example RSA encryption
• For p = 3, q = 11, n = 3 x 11 = 33, z = 2 x 10 = 20
• Choose d = 7 (20 and 7 do not have common factors)
• Solve 7 x e = 1 mod 20, so e = 3
• Note: asynchronous cryptography is slow, due to large key sizes
61
Public Key Infrastructure (PKI)
62
Public Key Infrastructure (Identification)
• Grid mechanisms
• X.509 Certificates
- Definitions
- Procedures
- Based on RSA
63
Transport Layer Security (TLS)
State of the art in secure connections
1. Client contacts server, server sends its certificate
2. Client checks digital signature of the CA
3. Client checks server certificate
•
Protection against man in the middle attacks
4. Client proposes encryption method
5. Switch to symmetric encryption (e.g. AES)
6. All kinds of additional measures
64
Advanced topics, not covered
• Network layer security
- PAP, CHAP
• IPv6 and IPSec
- Successor of IPv4, 128 bit = 5 x 10128 addresses
- Backward compatible
• Optical networks (lambdas)
- Dense Wave Length Division Multiplexing (DWDM)
- Optical Private Networks (OPNs)
- Switching optical networks (ONS boxes)
65
Advanced topics, not covered - continued
• Application layer
- DNS, P2P, VPN
- Email, HyperText
• Distributed File Systems
- AFS, NFS, etc.
• Unicast versus Multicast
- Time To Live (TTL)
• Grid
66
Cees de Laat
67