Computer Networking

Yishay Mansour (mansour@cs.tau.ac.il)

Nir Andelman (http://www.cs.tau.ac.il/~andelmni)

Course Information
Lectures: Tuesday 9-12 Exercises: Wendsday 10-11 Web site: Books: An Engineering Approach to Computer Networking / Keshav
http://www.cs.tau.ac.il/~andelmni/courses/comnet05/

A Top-down Approach to Computer Networking / Kurouse-Ross

Computer Networks / Tanenbaum Data Networks / Bertsekas and Gallager

Practical Information
Homework assignment: Mandatory Both theoretical and programming Done in pairs

Grades: Final Exam: theory exercises: Programming exercises:

60% February 5 and October 18 20% 20%

Motivation

Todays economy

manufacturing, distributing, and retailing goods but also creating and disseminating information

publishing banking film making.

part of the information economy

Future economy is likely to be dominated by information!

Information?

A representation of knowledge Examples:

books bills CDs analog (atoms) digital (bits) convert information as atoms to information as bits use networks to move bits around instead of atoms

Can be represented in two ways

the Digital Revolution

The Challenges

represent all types of information as bits. move the bits

In large quantities,

everywhere, cheaply, Securely, with quality of service, .

Todays Networks are complex!

hosts routers links of various media applications protocols hardware, software

Tomorrows will be even more!

This courses Challenge

To discuss this complexity in an organized way, that will make todays computer networks (and their limitations) more comprehensive.
identification, and understanding relationship of complex systems pieces. Problems that are beyond a specific technology

Early communications systems

I.e. telephone point-to-point links directly connect together the users wishing to communicate use dedicated communication circuit if distance between users increases beyond the length of the cable, the connection is formed by a number of sections connected end-to-end in series.

Data Networks

set of interconnected nodes exchange information sharing of the transmission circuits= "switching". many links allow more than one path between every 2 nodes. network must select an appropriate path for each required connection.

Networking Issues - Telephone

Addressing - identify the end user

phone number 1-201-222-2673 = country code + city code + exchange + number

Routing - How to get from source to destination.

Telephone circuit switching: Based on the phone number.

Information Units - How is information sent

telephone Samples @ Fixed sampling rate. not self descriptive! have to know where and when a sample came

Networking Issues - Internet

Addressing - identify the end user

IP addresses 132.66.48.37, Refer to a host interface = network number + host number

Routing- How to get from source to destination

Packet switching: move packets (chunks) of data among routers from source to destination independently.

Information Units - How is information sent.

Self-descriptive data: packet = data + metadata (header).

Telephone networks support a single, end-toend quality of service but is expensive to boot Internet supports no quality of service but is flexible and cheap

A future network will have to support a range of service qualities at a reasonable cost

1961-1972: Early packet-switching principles

1961: Kleinrock - queuing theory shows effectiveness of packet-switching 1964: Baran - packet-switching in military networks 1967: ARPAnet conceived by Advanced Research Projects Agency 1969: first ARPAnet node operational 1972: ARPAnet demonstrated publicly NCP (Network Control Protocol) first host-host protocol first e-mail program ARPAnet has 15 nodes

History

1972-1980: Internetworking, new and proprietary nets

1970: ALOHAnet satellite network in Hawaii 1973: Metcalfes PhD thesis proposes Ethernet 1974: Cerf and Kahn - architecture for interconnecting networks late70s: proprietary architectures: DECnet, SNA, XNA late 70s: switching fixed length packets (ATM precursor) 1979: ARPAnet has 200 nodes

History

Cerf and Kahns internetworking principles:

minimalism, autonomy - no internal changes required to interconnect networks best effort service model stateless routers decentralized control

Defines todays Internet architecture

1980-1990: new protocols, proliferation of networks

1983: 1982: 1983: 1985: 1988: deployment of TCP/IP SMTP e-mail protocol defined DNS defined for name-to-IP-address translation FTP protocol defined TCP congestion control

History

new national networks: CSnet, BITnet, NSFnet, Minitel 100,000 hosts connected to confederation of networks

1990 - : commercialization and WWW

History

early 1990s: ARPAnet decomissioned 1991: NSF lifts restrictions on commercial use of NSFnet (decommissioned, 1995) early 1990s: WWW hypertext [Bush 1945, Nelson 1960s] HTML, http: Berners-Lee 1994: Mosaic, later Netscape late 1990s: commercialization of WWW

Demand and Supply

Huge growth in users

The introduction of the web Better user experience. Significant portion of telecommunication. Although, sometimes temporary setbacks

Faster home access

Infrastructure

New evolving industries

Internet: Users
1000 900 800 700 600 500 400 300 200 100 0 1995 1997 1999 2001 2003 2005

Million users

year

Users around the Globe (2005)

350 300 250 200 150 100 50 Africa 0
Africa Asia/Pacific Europe Middle East USA+Canada Latin America Australia

Asia Pacific

Europe

USA Canada Middle East Latin America Australia

Technology: Modem speed

70000 60000 50000 40000 30000 20000 10000 0 1979 1980 1984 1987 1991 1993 1995 1997 300 1200 2400 9600 56000

bps

33600 28800 14400

year

Todays options

Modem: 56 K ISDN: 64K 128K Frame Relay: 56K ++ Today High Speed Connections

All are available at 5Mb (2005) Cable, ADSL, Satellite.

Coming soon:

Today

Protocol Layers

A way for organizing structure of network

Or at least our discussion of networks

The idea: a series of steps

To: Yishay From: Vered

Shipment 792 Pack. 1 of 3 To: Yishay From: Vered

Shipment 792 Shipment 792 Pack. 2 of 3 Pack. 3 of 3 To: Yishay To: Yishay From: Vered From: Vered

Handling
To: Boston From: TLV

Shipment 792 Pack. 3 of 3 To: Yishay From: Vered

Routing

To: Boston To: Boston Shipment 792 From: TLV Pack. 3 of 3 To: Yishay From: Vered

Transport JFK

Haifa

TLV

BGN

To: Yishay From: Vered

Shipment 792 Pack. 1 of 3 To: Yishay From: Vered

Shipment 792 Pack. 2 of 3 To: Yishay From: Vered

Shipment 792 Pack. 3 of 3 To: Yishay From: Vered

To: Boston Shipment 792 From: TLV Pack. 3 of 3 To: Yishay From: Vered

To: Boston To: Boston Shipment 792 From: TLV Pack. 3 of 3 To: Yishay From: Vered

JFK

N.Y.

Boston

Layers:
Person delivery of parcel Post office counter handling Ground transfer: loading on trucks Airport transfer: loading on airplane Airplane routing from source to destination

Peer entities

each layer implements a service

via its own internal-layer actions relying on services provided by layer below

Advantages of Layering

explicit structure allows identification & relationship of complex systems pieces layered reference model for discussion modularization eases maintenance & updating of system change of implementation of layers service transparent to rest of system

Protocols

A protocol is a set of rules and formats that govern the communication between communicating peers

set of valid messages meaning of each message

Necessary for any function that requires cooperation between peers

Protocols

A protocol provides a service

For example: the post office protocol for reliable parcel transfer service

Peer entities use a protocol to provide a service to a higher-level peer entity

for example, truck drivers use a protocol to present post offices with the abstraction of an unreliable parcel transfer service

Protocol Layers

A network that provides many services needs many protocols Some services are independent, But others depend on each other A Protocol may use another protocol as a step in its execution

for example, ground transfer is one step in the execution of the example reliable parcel transfer protocol Post office handling is layered above parcel ground transfer protocol.

This form of dependency is called layering

Open protocols and systems

A set of protocols is open if

protocol details are publicly available changes are managed by an organization whose membership and transactions are open to the public

A system that implements open protocols is called an open system International Organization for Standards (ISO) prescribes a standard to connect open systems

open system interconnect (OSI)

Has greatly influenced thinking on protocol stacks

ISO OSI reference model

Reference model

formally defines what is meant by a layer, a service etc. describes the services provided by each layer and the service access point

Service architecture

Protocol architecture

set of protocols that implement the service architecture compliant service architectures may still use noncompliant protocol architectures

The seven Layers

Application Presentation Application Presentation Session Network Data Link Physical Transport Network Data Link Physical End system

Session Transport Network Data Link Physical End system

Intermediate system

The seven Layers - protocol stack

data

Application Presentation

AH PH SH TH

data data

Application Presentation

Session Transport Network Data Link Physical

Session

data data NH data

Network Data Link Physical

DH+data+DT bits

Session Transport Network Data Link Physical

and presentation layers are not so important, and are often ignored

Postal network

Application: people using the postal system Session and presentation: chief clerk sends some priority mail, and some by regular mail ; translator translates letters going abroad. mail clerk sends a message, retransmits if not acked postal system computes a route and forwards the letters datalink layer: letters carried by planes, trains, automobiles physical layer: the letter itself

Internet protocol stack

application: supporting network applications ftp, smtp, http transport: host-host data transfer tcp, udp network: routing of datagrams from source to destination ip, routing protocols link: data transfer between neighboring network elements ppp, ethernet physical: bits on the wire

application

transport
network link physical

Protocol layering and data

source
M Ht M Hn Ht M Hl Hn Ht M

destination

application transport network Link physical

application transport network Link physical

M Ht M Hn Ht M Hl Hn Ht M

message

segment datagram frame

Physical layer

Moves bits between physically connected end-systems Standard prescribes

coding scheme to represent a bit shapes and sizes of connectors bit-level synchronization
technology to move bits on a wire, wireless link, satellite channel etc.

Internet

Datalink layer

Reliable communication over a single link. Introduces the notion of a frame

set of bits that belong together

Idle markers tell us that a link is not carrying a

frame

Begin and end markers delimit a frame

Internet

a variety of datalink layer protocols most common is Ethernet others are FDDI, SONET, HDLC

Datalink layer (contd.)

Ethernet (broadcast link)

end-system must receive only bits meant for it need datalink-layer address also need to decide who gets to speak next these functions are provided by Medium ACcess sublayer (MAC)

Datalink layer protocols are the first layer of software Very dependent on underlying physical link properties Usually bundle both physical and datalink in hardware.

Network layer

Carries data from source to destination.

Logically concatenates a set of links to form the abstraction of an end-to-end link Allows an end-system to communicate with any other end-system by computing a route between them Hides idiosyncrasies of datalink layer Provides unique network-wide addresses Found both in end-systems and in intermediate systems

Network layer types

In datagram networks

provides both routing and data forwarding

In connection-oriented network

separate data plane and control plane data plane only forwards and schedules data (touches every byte) control plane responsible for routing, callestablishment, call-teardown (doesnt touch data bytes)

Network layer (contd.)

Internet

network layer is provided by Internet Protocol found in all end-systems and intermediate systems provides abstraction of end-to-end link segmentation and reassembly packet-forwarding, routing, scheduling unique IP addresses can be layered over anything, but only best-effort service

Network layer (contd.)

At end-systems

primarily hides details of datalink layer segments and reassemble

detects errors

At intermediate systems participates in routing protocol to create routing tables responsible for forwarding packets schedules the transmission order of packets chooses which packets to drop

Transport layer

Reliable end-to-end communication. creates the abstraction of an error-controlled, flow-controlled and multiplexed end-to-end link
(Network layer provides only a raw end-to-end service)

Some transport layers provide fewer services

e.g. simple error detection, no flow control, and no retransmission

Internet

TCP provides error control, flow control, multiplexing UDP provides only multiplexing

Transport layer (contd.)

Error control

GOAL: message will reach destination despite packet loss, corruption and duplication ACTIONS: retransmit lost packets; detect, discard, and retransmit corrupted packets; detect and discard duplicated packets match transmission rate to rate currently sustainable on the path to destination, and at the destination itself

Flow control

Multiplexes multiple applications to the same end-to-end connection

adds an application-specific identifier (port number) so that receiving end-system can hand in incoming packet to the correct application

Session layer

Not common Provides full-duplex service, expedited data delivery, and session synchronization Internet

doesnt have a standard session layer

Session layer (cont.)

Duplex

if transport layer is simplex, concatenates two transport endpoints together allows some messages to skip ahead in end-system queues, by using a separate low-delay transport layer endpoint

Expedited data delivery

Synchronization

allows users to place marks in data stream and to roll back to a prespecified mark

Presentation layer

Usually ad hoc Touches the application data Hides data representation differences between applications

(Unlike other layers which deal with headers)

characters (ASCII, unicode, EBCDIC.)

Can also encrypt data Internet

no standard presentation layer only defines network byte order for 2- and 4-byte integers

Application layer

The set of applications that use the network Doesnt provide services to any other layer

Discussion

Layers break a complex problem into smaller, simpler pieces. Why seven layers?

Need a top and a bottom 2 Need to hide physical link; so need datalink 3 Need both end-to-end and hop-by-hop actions; so need at least the network and transport layers 5

Course outline
1 2 Introduction and Layering Data Link: Multi Access

3 4 5 6 7 8 9 10 11 12

Hubs, Bridges and Routers Scheduling and Buffer Management Switching Fabrics Routing Reliable Data Transfer End to End Window Based Protocols Flow Control Multimedia and QoS Network Security Distributed Algorithms