Network

Time to put M-bit message "on the wire" \[T-delay = \frac{M(bits)}{Rate(bits/sec)} = \frac{M}{R}\ seconds\]

Time for bits to propagate across the wire \[P-delay = \frac{Length}{speed\ of\ signals} \approx \frac{Length}{\frac{2}{3}C} = D\ seconds\] C is the speed of light. In copper wire, the speed s generally ranges from .59c to .77c

\[L = \frac{M}{R} + D\] Often one delay component dominates.

BD is the maxmium amount of data in flight. Reperesents the data "in the network". \[BD = R\times D\] Small for LANs, big for "long fat" pipes(LFN "elephen").

• An important example of a system where the bandwidth-delay product is large is that of geostationary satellite connections
• TCP related option: TCP window scale option

• Twisted Pair

  Widely used in LANs and telephone lines. Twist reduce radiated signal.

• Coaxial Cable

Long, thin, pure strands of glass. Properties: Enormous bandwidth

Sender radiates signal over a region. Properties:

• In many directions, to potentially many receivers
• Receiver need to coordinate use(choose a sender)

A signal over time can be represented by its frequency components.(Fourier analysis) \[g(t)=\frac{1}{2}c+\sum_{n=1}^\infty a_n sin(2\pi nft) + \sum b_n cos(2\pi nft)\]

Let a high voltage(+V) represent a 1, and low voltage(-V)represent a 0.

Carriers is simply a signal oscillatiog at a desired frequency. To modulate these signal, we can change amplitude, frequency, or phase.

• more signal levels

eg: voltage splits into four levels. reperents 2bits per symbol.

• Clock Recovery

Clock recovery is designed for the case like 1000000000…0

\[Maximum\ data\ rate = 2Hlog_{2}V\ bits/sec\]

• V is the discrete levels the signal consists.
• H is the bandwidth

\[Maximum\ data\ rate = Hlog_{2}(1+S/N)\ bits/sec\]

• S/N is the signal-to-noise ratio, S is the signal power, N is the noise power.
• S/N in db unit \(=10log_{10}(S/N)\)

Use power of 10 for rates, 2 for storage. \[Mbps=1,000,000bps, 1KB = 2^{10}bytes\] "B" is for bytes, "b" is for bits

The range of frequencies transmitted without being strongly attenuated is called the bandwidth

• MRU(maximum receive unit): 1500 bytes(Payload part)
• ESC(escape character) is 0x7D

check bits of n-bit data is often referred to as an n-bit codeword.

The number of bit positions in which two codewords differ is called the Hamming distance. eg: The hamming distance between 1011101 and 1001001 is 2

• To detect d errors, we need d+1 distance.
• To correct d errors, we need 2d+1 distance.

Sum is defined in 1s complement.

1. Arrange data in 16-bit words
2. Add all
3. Add with the carryover back to get 16bits
4. Trans to 1s Complement

0001+f203+f4f5+f6f7=2ddf0
ddf0+2=ddf2
ddf2->220d

1. Arrange data in 16-bit words
2. Add all + checksum
3. Add any carryover back to get 16bits.
4. Negate the result and check if it is 0.

0001+f203+f4f5+f6f7+220d=2fffd
fffd+2 = ffff
ffff->0

• Distance: 2
• Detect 1 error

1. Extend the n data bits with k zeros
2. Divide by the generator value C
3. Keep remainder, ignore quotient
4. Adjust k check bits by remainder

Frame: 1101011011
Generator: 10011
K: 4 bits
11010110110000 devided by 10011
Reminder: 0010

Divide by the generator value C and check for zero remainder

Protection depends on generator.

Standard CRC-32 is: 1111 0000 0100 1100 0001 0001 1101 1011 0111

• Distance: 4
• Detect 3 errors

Should be

• Not too long (link goes idle)
• Not too short (spurious resend)

Two ways to solve this problem:

• Statically divide a resource

  Suited for continuous traffic, fixed
  number of users
  

• Widely used in telecommunications

  E.g:
  TV and radio stations: FDM
  GSM (2G cellular): TDM within FDM
  

Issue about CSMA under high load:

• High overhead(expect collisions)
• Access time varies(random)

Turn-Taking protocol defines an order in which nodes get a chance to send.
The way to define ordering:
E.g Token Ring, node addresses

• Token Ring

  Arrange nodes in a ring. Token rotates permission to send to each node in turn.

  

• Advantages:
  1. Fixed overhead with no collisions
  2. Regular chance to send with no unlucky nodes
• DisAdvantages(Complexity):
  1. More things could be wrong. E.g: token lost
  2. High overhead at low load

Uses a learning table, sends to the port in the table or broadcasts to all ports.

• How can we connect switches in any topology?

• Problem - forwarding loops

  

  Redundancy in case of failures. But loops occurs:

  1. \(A\to C\to B, D-left, D-right\)
  2. \(D-left\to C-right, E, F\)
  3. \(D-right\to C-left, E, F\)
  4. \(C-right\to D-left, A, B\)
  5. \(C-left\to D-right, A, B\)
  6. …

Both of two models use Store-and-Forward packet switching.
Switching element has internal buffering for contention.

• Buffer is typically a FIFO queue
• If full, packets will be discarded

Like postal letters

• Packets contain a dest. address

• Each router has a forwarding table(often changes) keyed by dest addr. Example table:

  Table 1: Router A's Table

  Dest.	Line
  A
  B	B
  C	C
  D	B
  E	C
  F	C

Like a telephone call. Three steps:

1. Connection establishment, circuit is set up (Path is chosen, circuit info stored in routers)
2. Data transfer, circuit is used
3. Connection teardown, circuit is deleted

• Virtual means there's no bandwidth need be reserved
• Packets only contain a short label to identify the circuit

• Each router has a forwarding table keyed by circuit

  

Connecting different networks together called internetworking. Differs:

• Service model(datagrams, VCs)
• Addressing
• QOS(priorities, no priorities)
• Packet sizes
• Security(whether encrypted)

IP is the "narrow waist" of the internet.

The idea is make IP as a lowest common denominator.
Ask little from lower-layer, gives little to a higher-layer.

IPv4 carries 32-bit addresses on each packet(often 1.5KB)

Uses datagrams, you can see Source and Destination addr inside.

The fields to handle the difference of networks:

• Identification, Fragment offset, Fragment control bits for different packet size.
• Differentiated Services for QOS
• Time to live(TTL) for ICMP

Nodes uses a table that lists the next hop for IP prefixes. Example:

• Longest Matching Prefix

  Prefixes can overlap!
  In example above,
  D: 192.24.0~63.0~255
  B: 192.24.12~15.0~255
  

  

The rule is to more specific area. This rule called Longest Matching Prefix.

• Flexibility

  provide default behavior, with less specific prefixes.
  E.g. send traffic going outside an organization to a border router.
  
  special case behavior, with more specific prefixes.
  E.g. For performance, economics, security
  

• Host Forwarding Table

  Prefix	Next Hop
  My network prefix	Send direct to that IP
  0.0.0.0/0	Send to my router

  • 0.0.0.0/0 is a default route that catches all IP addresses.

Different networks have different maximum packet sizes.
Also known MTU(Maximum Transmission Unit)
Two solutions:

On IP Header: IP Protocol = 1
Provides error report and testing

When router encounters an error while forwarding:

1. Sends an ICMP error report back to the IP source address
2. Discards the problematic packet(host needs to rectify)

• ICMP Message

  ICMP message has a type, code, and checksum
  Often carry the start of the offending packet as payload
  Each message is carried in an IP packet
  

  

  Some examples:

  Name	Type/Code	Usage
  Dest. Unreachable(Net or Host)	3/ 0or1	Lack of connectivity
  Dest. Unreachable(Fragment)	3/4	Path MTU Discovery
  Time Exceeded(Transit)	11/0	Traceroute
  Echo Request or Reply	8or0 /0	Ping

  The last two are used for testing.

• 128 bits address

  8 groups of 4 hex digits. Omit leading zeros and group of zeros.
  Ex: 2001:0db8:0000:0000:0000:ff00:0042:8329
  -> 2001:db8:ff:42:8329
  

• Message Format

  

  The changes:

  • Streamlined header processing
  • Flow lable to group of packets
  • Better fit with advanced features(mobility, multicasting, security)

• Deploy Issue

  The format incompatible with IPv4
  Solutions:
  

  • Dual stack (speak IPv4 and IPv6)
  • Translators (convert packets)

  • Tunnels (carry IPv6 on IPv4)

    

• Adding routes: one hop per exchange
• Removing routes: no more exchanges

• Partitions are a problem: "Count to infinity" scenario

  

  Some way to address: Split horizon, poison reverse.
  (Don't send route back to where you learned it from)
  
  There's no very effective way to solve this problem.
  And now link state favored in practice.
  

• DV protocal with hop count as metric
  • Infinity is 16 hops; limits network size.
  • Include split horizon, poison reverse.
• Routers send vectors every 30 secs
  • Runs on top of UDP.
  • Timeout in 180 secs to detect failures.

• Sends an incoming message on to all other neighbors

• Remember the message so that it is only flood once

  Using source and sequence number

• Datagram length up to 64K
• Checksum(16 bits) for reliability

• state machine

  

• state machine

  

Node sends broadcast messages.
broadcast address is all 1s.
255.255.255.255 for IP, ff:ff:ff:ff:ff:ff for Ethernet