Data Communication And Computer Networks

Front 1

Forwarding

Back 1

Move incoming packets into the appropriate outgoing link

Front 2

Routing

Back 2

Determines how and where to forward packets

Front 3

Network Service Model

Back 3

Unreliable - no guarantees in place, at least with IP

Connectionless - no connection establishment, just drops packets onto the network

Front 4

Is UDP more reliable?

Back 4

No, both are unreliable protocols with no guaranteed delivery

Front 5

Do TCP packets receive special treatment?

Back 5

No, TCP and UDP are treated the same, just as packets; dropped on the network and forgotten about.

Front 6

What is the major difference from TCP/transport layer in terms of endpoints?

Back 6

IP is host to host while TCP is process to process

Front 7

Why don't routers implement transport layer?

Back 7

Don't need to, don't need ports, just need to worry about hosts

Front 8

Virtual Circuits

Back 8

Establish a phone-esque connection

allows for QoS or guarantees for those expected packets

Front 9

Virtual Circuit signalling protocols

Back 9

set up, tear down, monitor

Front 10

Forwarding Table

Back 10

IP address destination to link interface table

Front 11

longest prefix match

Back 11

algorithm used by routers in IP networking to select an entry from a forwarding table

Front 12

Routers: Input Ports

Back 12

Receive electrical bits

Interpret, protocol de-capsulation

Queue if router is busy (i.e. arrival rate > forwarding rate into switch fabric)

Front 13

Routers: Switch Fabric

Back 13

Decides where to send packets

Front 14

Switch Fabric: Memory

Back 14

Cheap, basically a computer

Slow, based on RAM bus speed

Consumer routers

Front 15

Switch Fabric: Bus

Back 15

Dedicated bus = faster

Leads to bus contention: one on bus at a time

Front 16

Switch Fabric: Interconnection network

Back 16

Avoid bus competition: every input directly connected to every output

Banyan network is an example

May fragment datagram and switch cells through fabric if you want

Fastest, most expensive

Front 17

Router: Output

Back 17

Queuing and buffer management

needed when packets arrive from fabric faster than max transmission rate

head of line blocking

queueing delay and packet loss due to buffer overflow

Usually buffer typical RTT time * link capacity, sometimes divide by root N flows

Front 18

Head-of-line blocking:

Back 18

queued datagram at front of input queue blocks the ones behind it from proceeding

Front 19

Queuing policies:

Back 19

Scheduling or Drop Policy

Front 20

Queuing Policy: Scheduling

Back 20

First come first serve, weighted fair

Front 21

Queuing Policy: Drop Policy

Back 21

Drop tail: if at tail, probably going to timeout anyway

active queue management

Front 22

Fragmentation

Back 22

breaking datagrams into smaller pieces so that packets may be formed that can pass through a link with a smaller MTU than the original datagram size

Front 23

Fragmentation Fields

Back 23

Length field in bytes

ID = some unique ID among the packet

fragFlag set to 1 in all but the last packet

Offset to 1 in all but the last packet

Offset to the data offset divided by 8

Front 24

IP Address

Back 24

32 bits

every interface has one

dotted quad format

subnet part and host part

subnet

Front 25

Subnet

Back 25

can physically reach each other without intervening router (just switch or hub; MAC address broadcasted in same range)

Note: A single link between two routers is technically a subnet of its own

Front 26

Classful subnets

Back 26

Class A, B, C for one, two or three full quads specified (/8, /16, /24)

Either lots of wasted addresses (too many), or wasted space in routing table cause a bunch of smaller class C subnets

Front 27

CIDR

Back 27

classless interdomain routing

syntax for specifying IP addresses and their associated routing prefix. It appends a slash character to the address and the decimal number of leading bits of the routing prefix

eg. 192.168.2.0/24 for IPv4

Front 28

Dynamic Host Configuration Protocol (DHCP)

Back 28

Used to dynamically assign IP addresses, easier than static assignment

Notes: Everything back/forth is a single transaction ID

Everything past the discover includes a lifetime field, specifying how long the dynamic assignment is valid

Front 29

DHCP 4 step handshake

Back 29

1. Host looking for address broadcasts (from 0.0.0.0 to 255.255.255.255) a DHCP discover message

2. Server responds with DHCP offer message, identifying IP that is available

3. Host requests the IP address with a DHCP request message

4. DHCP server responds with an ACK

Front 30

Network Address Translation (NAT)

Back 30

Allows for multiple machines behind a single actual IP address

Translates outgoing private IP/port pairings to an actual public facing IP/random port pair

Front 31

Internet Control Message Protocol (ICMP)

Back 31

Used by hosts and routers to communicate network level informational stuff

pings, unreachability information

Front 32

ICMP message format:

Back 32

Type (a number)

Code (associated with particular type, usually except for errors)

First eight bytes of IP datagram causing error

Front 33

ICMP traceroute

Back 33

Sends a series of UDP packets to dest with increasing TTLs (# hops = 1, 2, 3, ...)

When last router receives packet, responds back with ICMP message saying packet died

Traceroute uses result to identify this router, calculate RTT to/from it (average of 3)

STops when we get to end host, ICMP host unreachable returned

Front 34

In routing all routers know...

Back 34

cost to neighbors

Front 35

In routing all routers don't know...

Back 35

costs of anything other than neighbors

Front 36

In routing we must decide:

Back 36

who to send to next

Front 37

In routing we repeatedly...

Back 37

calculate cost to each possible neighbor + cost from that neighbor to the final destination, choose the lowest

Front 38

Types of routing?

Back 38

Global and decentralized

Front 39

Link-state is global or decentralized?

Back 39

global

Front 40

Link-State details

Back 40

All nodes know the full topology of the network

Any changes to a local connection gets flooded to all other connections

Basically, when we are notified of a change, we use Dijkstra's to calculate a routing table

Front 41

Link State Algorithm

Back 41

Initialize Graph for all neighbors with a total cost to neighbor, mark start as visited

while we haven't visited all nodes:

1. Of all nodes that we know of a route to but haven't visited pick the one with smallest cost; that's its final cost/route

2. Add all neighbors/routes attached to the new node, recalculate any new minimum routes if needed

Front 42

Poisoned Reverse

Back 42

If we route around a node to get to a new one, we tell the node we're routing through that our cost to the destination is infinity, so they will never route back through us.

Front 43

Local: distance vector

Back 43

Only knows neighbors

Maintains a distance vector of minimum cost to all known nodes, as well as known node's distance vectors

periodically, nodes send out their distance vector to neighbors, as well as on any changes to DV

more efficient than Dijkstra's: avoids complex algorithm, and fewer messages sent overall

see notes for more detail

Front 44

Distance vector count to infinity problem

Back 44

Avoided with Poisoned reverse

results in a routing loop

counts up to the new cost until it routes correctly

Front 45

Border Gateway Protocol (BGP)

Back 45

Routers with semi permanent connections via TCP

We've been assuming flat routing structures; we have hierarchies, and different subnets managed for different purposes. May want different routing strategies and algorithms depending on the particular subnet.

Front 46

Autonomous Systems (AS's)

Back 46

Collection of connected IP routing prefixes under the control of one or more network operators on behalf of a single administrative entity

Front 47

How does Border Gateway Protocol (BGP) work?

Back 47

We'll aggregate clusters of routers into Autonomous Systems

Routers in the same AS run the same routing protocol (distance vector vs linkstate) this is intra-AS routing protocol

Routers in different AS's can have different protocols

Single protocol, BGP, to communicate general route info between AS's

A router in one AS with a direct link to another is called a gateway router to that AS

each gets an AS ID, unique 16 bit number

Front 48

A router in one AS with a direct link to another is called a

Back 48

gateway router

basically the gateway router will learn that a particular subnet/prefix is reachable via AS3 through a given gateway. This propagates globally in the AS, so any given machine knows that to get to a prefix in another AS we just forward it to the right router

Front 49

BGP route prefix:

Back 49

the aggregate set of addresses that we can route to

Front 50

BGP message types

Back 50

OPEN - start connection + auth

UPDATE - new route, updated route

KEEPALIVE - no new updates + ACK for open

NOTIFICATION - error + closing

Front 51

Link Layer Services

Back 51

Framing/encapsulation

reliable delivery for some channels

flow control

error detection

error correction

half/full duplex

Front 52

Framing/Encapsulation

Back 52

Frame

Channels if shared

MAC addressing

Front 53

Why is reliable delivery for some channels in link layer services?

Back 53

TCP is general reliability, end to end. Works well for relatively low errors

Things like WiFi: much higher errors or dropped packets, so don't just transmit junk data the whole way if its bad initially

Front 54

Error detection: single bit parity

Back 54

sum of 1's odd or even. include sum bit at the end

Front 55

Two-dim parity:

Back 55

row and column. correctable, isolate incorrect bit

Front 56

Internet checksum:

Back 56

1's complement sum, sum with overflow carry, invert

Front 57

Cyclic Redundancy Check

Back 57

D input bits, r+1 bit pattern, G, a generator

R bit CRC R is chosen such that D followed by R is exactly divisible by G

Front 58

Why is error detection provided at the link layer and at TCP?

Back 58

TCP can run on any lower protocol; error correction cannot be assumed

Front 59

Multiple Access

Back 59

dealing with shared channels

ideal: perfect sharing with multiple nodes, but full bandwidth with few

Front 60

Time division multiple access (TDMA)

Back 60

Divides up time slots, assign

Fair

efficient when saturated

wasted time when few connections

no collisions

Front 61

Frequency division multiple access

Back 61

Divide up frequencies, assign

Fair, efficient when saturated, wasted bandwidth when connected, no collisions

Front 62

Random access

Back 62

Transmit full channel data rate

two or more at the same time = collision, must deal with them

Front 63

Slotted ALOHA

Back 63

Timed frames, start transmitting at beginning

if two transmit at the same time, then collision

Retransmit with probability p

full transmission rate when needed, decentralized

wasted slots, idle slots, collisions, synchronization

37% efficient = 1/e

Front 64

ALOHA

Back 64

like slotted ALOHA, but transmit any time

half as efficient, 1/2e

Front 65

Carrier Sense Multiple Access (CSMA)

Back 65

Don't transmit if someone else is transmitting

Front 66

CSMA/CD

Back 66

if collision detected, stop and jam signal

exponential backoff

hard to detect in wireless networks due to attenuation/hidden terminal problem

Front 67

CSMA/CA

Back 67

Collision avoidance - used in WiFi

Get permission to send first

Small message to request transmission permission, broadcast all-clear from router, full transmission, broadcast ack from router

Front 68

multiple access: Taking turns

Back 68

partitioning good at high loads

random access good with low loads

we want compromise

polling: master invites slaves (single POF, polling overhead)

Token ring: token POF

Front 69

Ethernet

Back 69

uses MAC address, as does wifi: 48 bits, six bytes written as hex quads separated by colons, permanent and burned in

Front 70

Why do we use both IP and MAC?

Back 70

Can't use MAC to entire internet

we have aggregate prefixes and stuff with IP. That's cause IP is dynamic and changes; it's geographical, and MAC is permanent burned in

Front 71

Why don't we only use IP for routing?

Back 71

Most IP addresses are assigned via DHCP - need to communicate at lower level without an IP address

Could statically assign all, but thats a ridiculous level of configuration

MAC address gives deterministic way to communicate without having to be configured for the device you're connecting to

Front 72

Address Resolution Protocol (ARP)

Back 72

Determine MAC address from IP address

ARP table at each IP node: mapping of IP address to MAC address with TTL

Broadcast an ARP query packet with a particular IP address

The right one responds directly with it's MAC address

Front 73

Hub:

Back 73

Dumb repeater. collisions

Front 74

Switch

Back 74

smarter. minimized collision domains by learning routes over time

Front 75

Multimedia?

Back 75

Different challenges

Likely use UDP to avoid TCP delays overhead

Front 76

Quality of Service (QoS)

Back 76

Provide level of performance necessary for a particular application

Front 77

General Characteristics of QoS

Back 77

Delay sensitive ( don't want lag or too much buffer time)

Loss tolerant ( a few dropped frames not a big deal)

Opposite of normal data transmission

Front 78

Jitter

Back 78

variability of packet delays within the stream

Front 79

Stored Stream

Back 79

Just need to stream it

playout begins before all data arrives

timing constraint: can't have too many pauses for buffering

Buffer to handle jitter

Front 80

Live Stream

Back 80

Streaming as in Stored stream, but can't have as much of a delay

Limits interactivity, like fast forwarding

Front 81

Real-time Streaming

Back 81

Much harder, because we interact and expect reasonable response (like skype)

audio: <150 msec good, <400 msec ok

Front 82

delay loss

Back 82

packet arrived, but too late, so we discard it anyway wasted work

fixed playout delay/buffering time for interactive stuff

high buffer = less loss

low buffer = more interactive

Front 83

Content distribution networks (CDNs)

Back 83

Helps with multimedia a bit by bringing static resources like videos geographically closer

origin server replaces image references or other stuff dynamically with cdn.com/original url

DNS server will dynamically send you to the machine closest to you

Front 84

Zero Conf

Back 84

Fully PnP

no centralized servers for configuration

getting address

-pick random one in ZeroConf range

-Probe to see if taken via ARP

-Assign or regenerate

Front 85

Multicast

Back 85

Send packet to a prefix or multicast address/ group, people who want it can selectively listen to it

Front 86

Multicast DNS

Back 86

specific dns for whoever wants it

dedicated TLD and multicast address (.local)

Machine may drop a multicast dns packet on network looking for a particular name with ".local", you'd respond if on that multicast group

Front 87

Service Discovery: DNS-SD

Back 87

Special domain name hierarchy

instance.type*.domain

can multicast dns query for a whole group of services, if they're configured and properly listening on the multicast group they'll jump in and work

Front 88

Access point/base station

Back 88

connected directly to a wired network

different data rates and rages

usually infrastructure mode: APS bridge gap between wireless devices and wireless networks

ad-hoc mode: wireless devices communicate directly, like mesh net

Front 89

Wireless characteristics

Back 89

Decreased signal propagation

Interference

Reflection/multipath propagation

Much harder to deal with

Front 90

Signal to noise ratio

Back 90

how much data we can extract from random noise larger is better

Front 91

Bit error rate (BER)

Back 91

how much of a signal is error. Smaller is better

Front 92

Given a particular SNR we need, choose

Back 92

physical layer medium that meets BER requirements

Front 93

Common problems with Wireless networks

Back 93

Hidden terminal: don't know about terminals due to obstruction (mountain in the way example)

Signal attenuation: Dont know about terminals due to fading signal strength

Front 94

Code division multiple access (CDMA)

Back 94

Lets some interference be fine

Multiplies signal by chipping pattern

Reconstructed with dot product divided by parts

Signal, chip is 1's and -1s

allows signals to interfere and still be extracted

Front 95

WiFi Characteristics

Back 95

All use CSMA/CA (permission)

All use same chipping code

All have both infrastructure and ad-hoc mode

Front 96

Basic service station (BSS)

Back 96

radius covered by a particular AP

Channels - 11 spectrum channels

Host must associate with an AP (connect)

Two types:

passive scanning

-aps send beacon frames advertising their SSID and MAC

-Association request frame sent to selected AP

-Association response frame send back

active scanning

-probe request sent, probe response sent back

-otherwise same

Front 97

WiFi CSMA/CA

Back 97

hard to detect collisions due to attenuation/hidden terminal

Front 98

Why 3 MAC addresses in WiFi packet?

Back 98

Need a source. If only had AP MAC, then we'd need next hop; if we must determine next hop, we're just a router. Can't do that. If only had next hop, AP doesn't know to pick up packet because multiple wireless networks or AP's in one range (BSS)