Notes

Outline

What is a network? A network is a distributed application which delivers information between processes in a distributed system Typically provides two classes of service: reliable stream (connection-oriented): in-order delivery of information is guaranteed (telephone system model) unreliable datagram (connectionless): information is delivered on a best-effort basis (post office model)

Issues in Providing Reliable Service Receiver: While ((ch = getchar()) != EOF) putc (ch, tty); Sender: While ((ch = getc(tty)) != EOF) putchar(ch); Issues: Error control Framing Sequencing Flow control

Issues in Providing Reliable Service (cont.) Additional issues: addressing multiplexing routing congestion control in-order delivery

OSI Reference Model

OSI Reference Model Physical Layer gets the bits across wire Data Link Layer provides interface to physical layer Network Layer lets non-adjacent machines communicate Transport Layer provides interface to network layer Session Layer structures communication Presentation Layer abstracts communication Application Layer provides end-user services

Physical Layer Physical layer standards specify: Mechanical characteristics: for example, the physical medium used for communication (copper wire, coaxial cable, optical fibre, ....), types of connectors, .... Electrical characteristics: for example, voltage levels and timing of voltages (for fibre: optical characteristics) Functional characteristics: for example, pin assignments Procedural characteristics: sequence of events for transmitting data based on functional  characteristics Example: RS-232 standard for connecting modems to computers and terminals (latest version is EIA-232-D).

Data Link Layer Often split into two sublayers: MAC sublayer: deals with sharing a common channel, as in Ethernet or Token Ring networks, is empty for networks build with dedicated point-point connections Logical link control sublayer: sits on top of MAC sublayer, assumes that adjacent machines communicate over a dedicated physical or logical link, deals with: flow control error control framing Example standards: IEEE 802 standards 802.2: Logical link control 802.3: Ethernet 802.5: Token ring 802.8: FDDI and fiber optics advisory group 802.11: Wireless Ethernet

Sharing a Broadcast Channel Two general approaches: scheduling: ready station transmit in orderly fashion fixed assignment FMDA (frequency-division multiple access): divide bandwidth into N independent subchannels, one for each station TDM (time-division multiple access): divide time into discrete intervals, each station is exclusively allocated entire bandwidth every N-th interval variations possible to account for different traffic volume originating from different stations fixed assignment is efficient for constant and predictable traffic, mean delay is N times worse than optimal when traffic is bursty on-demand assignment: stations that want to transmit have to wait until they are given permission to access common channel Token ring, FDDI: token circulates on ring DQDB: FCFS queue of send requests, maintained in a distributed fashion

Sharing a Broadcast Channel (cont.) random access approach: ready stations broadcast at will, leads to collisions that have to be resolved somehow Aloha: explicit acknowledgments of received packets Ethernet: similar to Aloha, but tries to minimize chance of collisions by limiting “broadcast at will” appropriately, also stops broadcast as soon as collision is detected Scheduling approaches perform better under a heavy load Random access approaches perform better under a light load

Example: Aloha ALOHANET packet radio network (developed by the University of Hawaii in 1971 to provide terminal access to a central computer) popularized random access protocols. Two 9600 bps channels: inbound and outbound. The inbound channel uses a MAC protocol known as (pure) ALOHA: stations transmit packets whenever they have data to sent inbound packets are ACKed. If no ACK is received during a random timeout interval, the packet is retransmitted Pure ALOHA is basis for many other MAC protocols, including Ethernet Works well under light load, under heavy load, channel utilization is only 18%

Example: Aloha (cont.) Problem: the vulnerable period (length of time in which a frame can be destroyed) for pure ALOHA is 2t, where t is the time required to broadcast a frame Slotted ALOHA: devised by Roberts in 1972 as a means for doubling channel utilization: divide time into discrete intervals or slots, each slot corresponds to a frame. Stations must wait for the beginning of a slot before broadcasting Under light load, average waiting time is increased from zero to one-half the slot length Under heavy load, the utilization is doubled, to about 37% (because vulnerability period dropped from 2t to t)

CSMA: Carrier Sense Multiple Access Improvements in ALOHA: 1-persistent CSMA: listen for idle channel before broadcasting. Collisions can still occur: due to propagation delay two stations may wait for a third to finish and then start broadcasting simultaneously nonpersistent CSMA: listen to the channel, if not busy, start broadcasting. Otherwise, wait for a random interval and try again. Utilization approaches 1 under heavy load p-persistent CSMA: listen for an idle channel. Then with probability <p broadcast frame (otherwise, delay and try again) Yet another improvement: abort broadcast as soon as collision is detected (called CSMA/CD) frames must be long enough so that all transmitting stations can detect a collision: the farther stations can be apart, the larger the minimum packet length Ethernet: maximum network length is 2.5 km, minimum frame length is 512 bytes

Ethernet Standardized in IEEE 802.3 Based on DIX (Dec/Intel/Xerox) 10 Mbps Ethernet standard, which is based in turn on the Xerox Ethernet developed by Metcalf and Boggs Sending station listens while sending. If data sent differs from data received, assume collision and execute following protocol: after i successive collisions, pick a random number between 0 and 2**i - 1 and skip that number of slots (one slot is 512 bits times long) interval frozen after 10 collisions (at 1023) abort sending if 16 attempts failed

Logical Link Control Framing: used for multiplexing and synchronization can be done by coding violations at physical layer or bit/char stuffing bit stuffing: special bit pattern is used to separate frames: e.g., 01111110. Whenever the transmitter encounters 5 consecutive 1’s in the user’s data, it stuffs (inserts) a 0 bit into the transmission. When the receiver sees five consecutive 1’s followed by a 0, it deletes the 0 bit byte/char stuffing: two special characters are used. One, say `”`, is used to separate frames, and the other, say ‘/’, is used as an escape character if `”` or ‘/’ appear in the user’s data, the sender transmits, say, ‘/a’ or ‘/b’, respectively when receiver sees ‘/a’ or ‘/b’, it delivers `”` or ‘/’ respectively byte count can be added to protect against insertions and deletions

Logical Link Control (cont.) Error Control Schemes: used to increase reliability. Complete reliability is not possible, even internal circuits are not completely reliable must deal with (at the data link layer) duplication, distortion, deletion, and insertion of messages work by increasing redundancy of message in some well-defined way; consistency of received message is used to assess the reliability of its information types of error control schemes: forward error control: uses error-correcting codes (such as Reed-Solomon or Hamming codes) to send enough information to allow receiver to detect and correct errors feedback error control: uses error-detecting codes (such as parity bits, CRC) to allow receiver to detect but not to correct errors. Requires retransmission for correction feedback error control typically superior to forward error control (but there are exceptions....)

Logical Link Control: Flow Control assure that transmitting station does not overwhelm a receiving station with data assumptions: data transmitted in frames, sequential, variable and arbitrary delays simplest form: stop-and-wait (or stop-and-go) simple, low overhead poor utilization of channel, particular for channels with long propagation delays (such as satellite channels)

Flow Control (cont.) To achieve better channel utilization, employ sliding window protocol: basic idea: allow multiple frames to be in transit at one time each frame is assigned a sequence number, using k bits in frame header (numbering is done module 2k) sender sends up to N frames without waiting for ACK receiver ACKs a frame by sending sequence number of next frame expected, does not have to ACK every single frame sender maintains a list of sequence numbers that is is allowed to send, receiver maintains a list of sequence numbers it is prepared to accept => sliding window different protocols differ in how they handle errors

Go-Back-N Protocol

Selective-Reject Protocol

Network Layer Primary concern: routing determines path of packets from source to destination (so that non-adjacent machines can communicate) implementations differ as to when path is selected (static, dynamic, per packet, per circuit), where selection is done (centralized, distributed), and what information is used (none, local, adjacent, global) selection usually based on some least-cost criterion: each link is assigned a cost, cost of path is sum of costs of path traversed Routing algorithms: Djikstra’s shortest path algorithm source routing flooding random walk backward learning

Network Layer (cont.) As networks grow in size, routing tables (tell next destinations on way to receiver) grow Partial solution: use default entries Hierarchical routing: networks organized (recursively) into subnetworks. Routing problem reduces to two smaller subproblems routing between subnetworks (with relatively stable topology) routing with subnetwork (with dynamically changing topology) requires identifiable structure of network addresses (IP addresses: class A, B, C) Another problem addressed at network layer: mobility (mobile-IP) Congestion control: ensure efficient network usage, do not overload internal routers or links: pre-allocate buffers, discard packets, choke packets, etc....

Transport Layer First layer in which end-to-end functionality can be implemented. Issues that need to be addressed: addressing multiplexing flow control error control connection management Addresses are typically of the form (station, port), initiating process obtains address of a target process from: configuration database “well-known” address name server from a server that starts the target process

Connection Management Connection-oriented services have three phases connection establishment data transfer connection termination Connection establishment: allows each end to ensure other exists allows negotiation of optional parameters triggers allocation of resources In unreliable network, connection establishment non-trivial (2-army problem):

2-Way Handshake

3-Way Handshake