计算机网络

Posted on | In |

1.2 The Network Edge
host = end system
1.2.1 Access Networks
Home Access: DSL (digital subscriber line) cable FTTH Dial-Up Satellite
hybrid fiber coax

Chapter4: The Network Layer:Data Plane

network layer can be decomposed into two interactiing parts,the data plane and the control plane
what will be coverd?

  • per_router functions
  • traditional IP forwarding
  • generalized forwarding
  • IPv4 IPv6 addressing

4.1 Overview of Network Layer

4.1.1 Forwarding and Routing: The Data and Control Planes

  • two important network-layer functions:
    • Forwarding in data plane of the network layer
    • Routing in control plane of the network layer

4.2 What’s Inside a Router?

4.2.1 Input Port Processiing and Destination-Based Forwarding

  • longest prefix matching

    4.2.2 Switching

  • Switching via memory
    • only one memeory read/write can be done at a time.
  • Switching via a bus
    • only one packet can cross the bus at a time.
  • Switching via an interconnection network
    • crossbar switch non-blocking
    • a packet being forwarding will not be blocked as long as no other packet is currently being forwarded to that output port.

      4.2.3 Output Port Processing

      4.2.4 Where Does Queueing Occur?

  • queueing-at both input ports and output ports
  • factor: line speed, traffic load, relative speed
  • Input Queueing
    • head-of-line(HOL) blocking
      a queued packet in an input queue must wait for transfer through the fabric even though its output port is free
  • Output Queueing
    • drop-tail drop the arriving packet
    • active queue management(AQM)
      Random Early Detection(RED)

      4.2.5 Packet Scheduling

  • FIFO
  • Priority Queueing
    • non-preemptive priority queuing
      the transmission of a packet is not interrupted once it has begun
  • Round Robin and Weighted Fair Queueing(WFQ)
    alternates service among different classes in priority
    queueing
    • work_conserving queueing
      move on to the next class in the service sequence when it finds an empty calss queue.(轮到服务你但是你为空我就跳过)
  • WFQ each class may receive a different amout of service in any interval of time.

4.3 The Internet Protocol(IP): IPv4,IPv6,Addressing

4.3.1 IPv4 Datagram Format

20 bytes of header(no optons)

  • Version number 4bits
  • Header length
  • Type of service
  • Datagram length 16bits long
  • Identifier, flags, fragmentation offset
  • Time-to-live
  • Protocol
    指定IP datagram的data portion应该传给transport-layer的哪种协议
  • Checksum
    • 路由器检查到错误就丢弃datagram，因为每经过一个路由器TTL和option（可能）都会改变，所以要重新计算checksum
    • 为什么TCP/IP 在transport layer和networklayer 都要error checking？
    • IP能携带不会传给TCP/UDP的数据
  • Source and destination IP address
  • Option IPv6没有
  • Data(Playload)
    包含transport-layer segment(TCP/UDP)还可以包含其他数据(ICMP)

4.3.2 IPv4 Datagram Fragmentaion

  • maximum transmission unit(MTU)
  • 为什么要fragmentation?
    因为不同的link-layer protocol有不同的MTU
  • fragments need to be reassembled befroe reach transport layer

    4.3.3 IPv4 Addressing

  • interface
    • 什么是interface?
    • an IP address is technically associated with an interface, rather than with the host or router containing that interface*
  • subnet
    • 如何划分子网
    • 255.255.255.255 广播地址
  • subnet mask
    • 注意，路由器之间也算可以构成子网
  • DHCP
    dynamic host configuration protocol 自动分配IP地址
    • first-hop router = default gateway
    • DHCP protocol的four-step process
      • DHCP server discovery DHCP discover message
      • DHCP server offer DHCP offer message 同个子网可能有多个DHCP server
      • DHCP request DHCP request message
      • DHCP message DHCP ACK

        4.3.4 Network Address Translation(NAT)

  • private network
    • 10.0.0.0/8 是三种保留的IP地址之一
    • NAT translation table 让router知道该把外网的datagram传给哪个host

Chapter5 Network Layer-Control Plane

link state中的oscillation是什么？
distance vecotr中最坏的情况是？

##goals

  • understanding principles behind network control plane
  • SDN controllers
  • Internet Control Message Protocol
  • network management
  • OSPF BGP OpenFlow ODL ONOS
  • ICMP SNMP

5.1 introductino

  • two network-layer function
    • forwarding-data plane
    • routing-control plane
  • two approches of control plane
    • per-router control
    • logically centralized control
      software defined networking

5.2 routing protocols

  • link state
    dijkstra oscillations???
  • distance vector
    bellman-ford $D_x(y)=min{c(x,v)+d_v(y)}$
    when link cost change what will happen?
    convergence timn varies, count-to-infinity

5.3 intra-AS routing in the internet:OSPF

  • autonomous system(AS)
  • intra-AS routing
    routing in same AS
    all routers in AS must run same intra-domain protocol
    • intra-AS routing algorithm
  • inter-AS routing
    routing among AS
    • inter-AS routing algorithm
      router in AS1 destined outside of AS1
      propagate rechability info to all routers in AS1
  • interior gateway protocols(IGP)
    ##intra-AS routing protocols:
  • RIP routing information protocol
  • OSPF open shortest path
    use link-state algorithm
    carried in OSPF messages directly over IP
    like IS-IS routing protocol
    • hierarchical OSPF
      two-level hierarchy: local area, backbone
      link-state advertisement only in area
      • area border routers
      • backbone routers
      • boundary routers
  • IGRP interior gateway routing protocol

5.4 inter-AS routing

BGP(border gateway protocol)
eBGP
iBGP

  • BGP session: over TCP connection
    advertise: prefix(destination)+attributesd = route
    two attributes
    AS-PATH
    NEXT-HOP
    policy-based routing
    how BGP path advertisement works?
    BGP route slection
    • local preference-policy
    • shortest AS-PATH
    • closest NEXT-HOP-hot potato routing
    • additional criteria

      different between inter/intra routing

  • policy
    inter-AS: admin wants to control how traffic is routed
    intra-AS: no need
  • scale
    hierarchical routing saves table size, reduced update traffic
  • performance
    intra-AS: can focus on performance
    inter-AS: policy may dominate over performance

5.5 software defined networking(SDN)

  • network control applications
  • SDN controller
  • network switches
  • openflow protocol
    controller to switch message
    switch to controller message

5.6 ICMP(internet control message protocol)

  • ICMP
    used by hosts & routers to communicate
    ICMP msgs carried in IP datagrams
    format type+code+first 8 bytes of IP datagram
    source send UDP to routers and routers back ICMP(name of routers and ip address)

5.7 network management

managed devices contain managed objects whose data is gathered into a management information base(MIB)

  • SNMP protocol
    • request/response mode
    • trap mode

Chapter6

##goals

  • understand principles behind link layer services
    • error detection, correction
    • sharing a broadcast channel: multiple access
    • link layer addressing
    • local area networks: Ethernet, VLAN
  • instantiation, implementation of various link layer technologies

##6.1 introduction, services
link layer transfer datagram from one node to physically adjacent noe over link
datagram transferred by different link protocols over different links

ethernet, ppp, 802.ii

  • framing, link access
    encapsulate datagram into frame
    mac addresses used in frame header to identify source, destination
  • reliable delivery between adjacent nodes
    seldom used on low bit-error link(fiber, twisted pair)
    why both link-level and end-end reliability
  • flow control
  • error detection
    error caused by signal attenuation, noise
  • error correction
    receiver identifies and corrects bit errors(s)
  • full-duplex / half-duplex
  • in each and every host
  • implemented in adaptor(network interface card NIC)

    adaptor communicating

sending side

  • encapsulates datagram in frame
  • adds error checking bits, rdt, flow control
    recieving side
  • looks for errors, rdt, control
  • extracts datagram, passes to upper layer

6.2 error detection/correction

error detection

EDC

parity checking

single bit parity
two-dimensional bit parity

internet checksum

used at transport layer only

cyclic redundancy check

D:data G: r+1 bit pattern
D: data to be sent R:CRC bits
D*2^r XOR R
example

6.3 multiple access protocols

two types of links

  • point-to-point
    ppp for dial-up access
  • broadcast(shared wire or medium)
    upstream HFC
802.II wireless LAN
    collision if node reveives two or more signals at the same time
    multiple access protocol
    desired properties

    MAC protocols: taxonomy

    channel partitioning
    divide channel into pieces
    random access
    channel not divided, allow collisions
    taking turns
    nodes with more to sent can take longer turns

    channel partitioning MAC protocols

    TDMA time division multiple access
    access to channel in rounds, each station get fixed slot
    FDMA frequency division multiple access

    random access MAC protocol

    slotted ALOHA
    efficiency
    max efficiency = 1/e = 3.7
    ALOHA
    max efficiency = 1/2e = 2.8
    CSMA
    CSMA/CD
    binary(exponential)backoff
    CSMA + CD(collision detection)
    easy in wire LANs: measure signal strength, compare transmitted, received signals
    difficult in wireless LANs: received signal strenth overwhelmed by local transmission strength
    , CSMA/CA**
    carrier sense multiple access
    CSMA listen before transmit
    if channel sesed idle,transmit entire frame
    if channel sensed busy, defer transmission
    transmit at full channel data rate R
    two or more transmitting nodes->collision
  • how to detect collisions
  • how to recover from collisions

    taking turns protocols

    FDDI, bluetooth, token ring
    polling
    token passing

6.4 LANs

MAC addresses and ARP

ip address MAC(LAN or physical or Ethernet) address
MAC flat address -> protability
can move LAN card from one LAN to another
IP hierarchical address - > unprotable
address depends on IP subnet to which node is attached
ARP:address resolution protocol
ARP table

Ethernet

wired LAN technology

physical topology

  • bus coaxial cable
  • star switch

    frame structure

    sending adapter encapsulates IP datagram in Ethernet frame
  • preamble
  • addresses
  • type

    Ethernet is unreliable, connectionless

  • connectionless: no handshaking between sending and receiving NICs
  • unreliable: receiving NIC doesn’t send acks or nacks
  • ethernet’s mac protocol
  • unslotted CSMA/CD with binary backoffcommon MAC protocol and frame format
    different speeds: 2 Mbps, 10Mbps, 100Mbps
    different physical layer media: fiber, cable

    Ethernet switch

    switch

  • link-layer device: takes an active role
  • transparent
    hosts are unaware of presence of switches
  • plug-and-play self-learning
    switches do not need to be configured
  • switching can transmit simultaneously

    switch forwarding table

    each switch has a switch table
    switch learns which hosts can be reached through which interfaces
  • elimination of collisions
  • heterogeneous links
  • management

    different between switches and routers

  • routers
    network-layer devices
    compute tables using routing algorithms, IP addresses
  • switches(no network layer)
    link-layer devices
    learn forwarding table using flooding, learning, MAC addresses

    VLANs

    virtual local area network
    define multiple virtual LANs over single physical LAN infrastructure

    port-based VLAN

  • traffic isolation
  • dynamic membership
    ports can be dynamically assigned among VLANs
  • forwarding between VLANS
    done via routing(just as with separate switches)

    VLANs spanning multiple switches

    trunk port
    carries frames between VLANS defined over multiple physical switches
    802.I q protocol adds/removed additional header fields for frames forwarded between trunk ports

    wireless LANs

    802.II LAN architecture

    AP(base station=access point)
    BSS(basic service set)

    802.II channels, association

6.7 a day in the life of a web request

  • DHCP
    dhcp request encapsulated
    -UDP
    -IP
    -802.3 Ethernet
    -broadcast(dest:全F)
    -ethernet demuxed to ip demuxed to udp demuxed to dhcp
    client now has ip address, name & address of DNS server, ip address of its first-hop router
  • DNS
    DNS encapsulated
    -UDP
    -IP
    -ARP
    client now knows MAC address of first hop router
  • TCP
  • HTTP