计算机网络-学校

本篇后半部分内容产生格式错乱和渲染错误, 是Ipad导出时所产生的格式混乱所致, 现已无法全部修改, 请转看另一篇计网内容.

Chapter 1 Computer Networks and the Internet (about 10%)

1.1 What’s the Internet?

• Internet: The Internet is a worldwide computer network, that is a network that inter connects millions of computing devices throughout the world.
• Host(end system): Computers and other devices connected to the Internet run application programs.
• Packet switching: The resources are not reserved; a session’s messages use the resources on demand, and as a consequence, may have to wait for access to a communication link.
• Path/route
• Protocols: controlling the sending and receiving of information within the Internet.
  A protocol defines the format and the order of messages exchanged between two or more communicating entities , as well as the actions taken on the transmission and/or receipt of a message or other event.

1.2 The Network Edge

• Client: client host requests, receives service from always-on server

• Server: Server host provides service

• Guide and unguided media

  • Guide media: signals propagate in solid media: twisted-pair copper, fiber, coaxial cable.
  • Unguided media: signals propagate in the atmosphere and in outer space: radio, satellite channel.

• Three types of access networks

  1. residential access: cable modems
  2. company access: local area networks
  3. wireless access network

• Differences of circuit switching and packed switching

  Difference	Circuit Switching	Packet switching
  Resource	Pre-allocate resource	Allocate resource on demand
  Bandwidth	Dedicated	Shared
  Forwarding	Cut-through	Stored and forward

• TDM and FDM

  • FDM: The frequency spectrum of a link is divided up among the connections established across the link.
  • TDM: time is divided into frames of fixed duration, and each frame is divided into a fixed number of time slots.

• Store and forward transmission: the switch must receive the entire packet before it can begin to transmit the first bit of the packet onto the outbound link.

1.3 Delay and Loss in Packed-Switched Networks

• Types of delay(definition and compute)

  • Nodal processing delay: examining the packet’s header and determine where to direct the packet check bit errors.
  • Queueing delay: time waiting to be transmitted onto the link depends on congestion level of router.
  • Transmission delay: time required to push all of the packet’s bits into the link.
    • $R = link\ bandwidth$
    • $L = packet\ length$
    • $d_{trans} = L\ /\ R$
  • Propagation delay: time required to propagate from the beginning of the link to next router (or host).
    • $d = lenght\ of\ physical\ link$
    • $s = propagation\ speed\ in\ medium$
    • $d_{prop} = d\ /\ s$
  • $d_{nodel} = d_{proc} + d_{queue} + d_{trans} + d_{prop}$
  • end 2 end delay(Ignore queuing delay):
    $d_{e2e} = N(d_{proc} + d_{trans} + d_{prop})$
    where N is number of links(N-1)routers

• Traffic intensity

  • $traffic_intensity = La / R$
  • $R = link\ bandwidth$
  • $L = packet\ length$
  • $a = average\ packet\ arrival\ rate$
  • Golden rules: design your system so that the traffic intensity is no greater than 1

1.4 Protocol Layers and their service models

• Layered architecture of computer network

  1. application
  2. transport
  3. network
  4. link
  5. physical

• Encapsulation: add head information that before forwarding

• Each layer packet name

  Layer	Packet name
  Application	message
  Transport	segment
  Network	datagram
  Link	frame
  Physical	bit

Addtion

• 重点：什么是因特网；什么是协议；客户端和服务器端程序；网络接入；物理媒体；电路交换和分组交换；时延分类；排队时延与分组丢失的关系；网络分层中各层次的关系与功能。
• 难点：协议的定义；网络接入方法；物理媒体种类；电路交换与分组交换技术及区别；时延的分类与计算；传输时延与传播时延的区别；网络分层的结构以及各层次的关系。

Chapter 2 Application Layers (about 20%)

2.1 Principles of Network Application

• Difference of two types of network application architecture
  1. C/S
     • server: always-on host fixed,well-known IP address server farms for scaling.
     • client: communicate with server may be intermittently connected may have dynamic IP addresses do not communicate directly with each other.
     • In processes view, client is process that initiates communication, process that waits to be contacted.
  2. P2P: no always-on server arbitrary end systems, directly communicate peers are intermittently connected and change IP addresses
  • Socket and port number
  • Socket: A socket is the interface between the application layer and the transport layer within a host. Process sends/receives messages to/from its socket.
  • Port number: associated with process on host.
  • Services which application need
  1. reliable data transfer
  2. timing
  3. security
  4. bandwidth / throughput
  • Services provided by Internet transport protocol
  • TCP
    1. connetction-oriented
    2. reliable transport
    3. flow control
    4. congestion control
  • UDP
    1. connectionless
    2. unreliable data transfer
  • They both can’t provide timing, bandwidth.

2.2 The Web and HTTP

• Web page, object, base HTML file and URL and so on.
  Web page consist of objects. Objects can be in many types, and each object is addressable by a URL.

• Difference of non-persistent and persistent connection

  • non-persistent: at most one object is sent over a TCP connection.
  • persistent: multiple objects can be sent over single TCP connection.

• Compute how many RTT used:

  1. non-persistent without parallel: $2nRTT$
  2. non-persistent with n parallel: $n\to∞, (2+2)RTT$
  3. persistent without pipelining: $(n+1)RTT$
  4. persistent with pipelining: $2RTT / 3RTT$

• HTTP’s basic conception

  • port number: 80
  • stateless
  • work in C/S model

• Format of request and response message

  • request:
    1. request line
    2. header line
    3. blank line
    4. entity body
  • response:
    1. status line
    2. header lines
    3. blank line
    4. entity body
  • header line:
    1. Date: indicates the time and date when the HTTP response was created and sent by the client.
    2. Last-Modified: indicates the time and date when the object was created or last modified.
    3. Content-Length: indicates the number of bytes in the object being sent
    4. Content-Type: indicates type of the object in the entity body is

• Web caches(proxy server): Web accesses via cache browser sends all HTTP requests to cache.

• Conditional GET method

2.3 File Transfer:FTP

• Basic conception and common commands
  • Conception
    • port number: 21(control) / 20(data)
    • control in persistent, data in non-persistent
    • C/S
    • TCP
  • Command
    • USER: useranme
    • PASS: password
    • LIST: return list of file in current directory
    • RETR: get file
    • STOR: put files onto remote host
• Difference of FTP and HTTP
  1. FTP control connetion out of band, HTTP in band.
  2. FTP server maintains state, HTTP is stateless

2.4 Electronic Mail in the Internet

• Three major components of E-mail

  1. user agents
  2. mail servers
  3. SMTP protocol for mail transfer

• Basic conception of SMTP

  • C/S
  • TCP
  • port number 25
  • must be 7-bit ASCII

• Difference of SMTP and HTTP

  • HTTP
    1. pull protocol
    2. encapsulates each object with response message
    3. has no message restriction
  • SMTP
    1. push protocol
    2. place all message’s object into one message
    3. each message must be 7-bit ASCII format

• Mail message formats and MIME

  • format:

    TO:

    From:

    Subject:

    Body:

  • MIME: multimedia mail extension additional lines in msg header declare MIME content type.

• Types of mail access protocols

  • POP3:port 110
  • IMAP: port 143
  • HTTP

• Basic conception of POP3 and IMAP

  • POP3
    • session
      1. authorization phase
      2. transaction phase
      3. update phase
    • stateless
    • have download and delete or download and keep model(download to local host)
  • IMAP
    • keep all messages in server
    • allow user to orgnize message in folders
    • keep user state

• C/S sessions of SMTP and POP3

2.5 DNS-The Internet’s Direcotry of Service

• Services of provided by DNS

  1. hostname to IP address translation
  2. host aliasing
  3. mail server aliasing
  4. load distribution

• How DNS works before other applications protocols

  • port number 53

  • Work in UDP

  • ?????

• Hierarchical architecture and local DNS server

  • Hierarchical architecture:
    • Root servers: contacts authoritative name server if name mapping not known gets mapping
      returns mapping to local name server.
    • Top-level domain(TLD) servers: responsible for com, org, net, edu, etc, and all top-level country domains uk, fr, ca, jp.
    • Authoritative DNS servers: organization’s DNS servers, providing authoritative hostname to IP mappings for organization’s servers (e.g., Web, mail).
  • local Name servers: when host makes DNS query, query is sent to its local DNS server.

2.6 Peer-to-Peer Application

• The basic conception of P2P file sharing
  • based on HTTP
  • centralized directory - Napster
  • Query flooding - Gnutella
    • fully distributed
    • public domain protocol
  • hierarchical overlay - KaZaA
    • based on TCP

Addtion

• 重点：两种类型的网络应用结构（C/S和P2P结构）；持久连接与非持久连接的原理；HTTP请求报文与响应报文格式；HTTP请求报文的方法；HTTP响应报文的状态码；Web缓存的优点；FTP的连接方法与命令；FTP与HTTP的不同点；E-mail的三个组成部分；SMTP的基本概念；SMTP和HTTP的区别；邮件报文格式与MIME；POP3和IMAP协议的基本概念；邮件访问协议种类；DNS的功能；DNS服务器的层次结构；P2P协议基本概念。
• 难点：socket和port number的概念；HTTP的基本概念；持久连接与非持久连接的方法；条件GET方法；FTP工作时的两种并行连接；SMTP和HTTP的区别；POP3与IMAP的区别；DNS协议的分层与访问方式。

Chapter 3 Transport Layer (about 30%)

3.1 Introduction and Transport-Layer Service

• Relationship between transport and network layers
  • Transport layer
    1. provide logical communication between processes
    2. encapsulate message to segment
  • Network layer
    1. provide logical communication between host
    2. encapsulate segment to datagram
• Services provided by TCP and UDP.
  • TCP
    1. congestion control
    2. flow control
    3. connection setup
    4. reliable, in-ordered
  • UDP
    1. best effort
    2. unreliable, unordered delivery

3.2 Multiplexing and De-multiplexing

• Multiplexing and de-multiplexing
  • De-multiplexing: Delivering the data in a segment to the correct socket.
  • Multiplexing: gathering data from multiple sockets, encapsulating data with header (later used for demultiplexing) to create segments, and passing to the network layer.
• The difference of UDP and TCP Multiplexing/ de-multiplexing
  • demux UDP identified by 2 tuple(dest IP addr, dest port number)
  • demux TCP identified by 4 tuple(source IP addr, source port number, dest IP addr, dest port number)
• MSS and MTU
  • MSS: maximum segment size, maximum amount of data that can be grabbed and placed in a segment (application-layer data in the segment).
  • MTU: maximum transmission unit, maximum amount of data that a link-layer frame can carry.

3.3 Connectionless Transport: UDP

• Basic conception and format of UDP

  • Conception
    • connectionless
    • no retransmit
    • no congestion control
    • small segment header: 8 bytes header
    • Format(8 bytes)
  1. source port(16)
  2. dest port(16)
  3. length(bytes) (16)
  4. checksum(16)
     • applications: DNS, SNMP, RIP

• Checksum methods

  • carryout
  • wraparound
  • bits inversion

3.5 Connection-Oriented Transport: TCP

• Format of TCP segment structure(20 bytes at least)

  • port number[16 * 2(dest, source)]
  • sequence number(32)
  • ACK(32)
  • checksum(16)
  • rcv window(16)
  • header length(4)
  • flag(6)
  • urg data pnter(16)

• Sequence numbers and ACK numbers

  • sequence number: the byte stream “number” of first bytes in segment’s data
  • ACK number: The sequence number of next byte expected from other side.

• Analyze the reliable data transfer of TCP (Simplified TCP, doubling the timeout interval and fast retransmit)

  • dobubling timeout interval: Timeout is a kind of congestion event, so next timeout interval = 2× previous timeout interval
  • fast retransmit: If sender receives 3 duplicate ACKs for the same data, it supposes that segment after ACKed data was lost.

• Function of flow control and receive window

  • flow control: sender won’t overflow receiver’s buffer by transmitting too much, too fast.
  • receive window: app process may be slow at reading from buffer.

  $$
  RcvWindow = RcvBuffer - [ LastByteRcvd - LastByteRead ]
  $$

  $$
  LastByteSent - LastByteAck \le RcvWindow
  $$

• How to estimate the RRT and timeout

  • RTT

  $$
  EstimatedRTT_{(n)} = (1 - \alpha) EstimatedRTT_{(n - 1)} + \alpha SampleRTT_{(n - 1)}
  $$
  ​ Typically, $\alpha=0.125$

  • Timeout

  $$
  DevRTT_{(n)} = (1 - \beta) DevRTT_{(n - 1)} + \beta |SampleRTT_{(n - 1)} - EsimatedRtt_{(n - 1)}|
  $$

  $$
  TimeoutInterval = EstimatedRTT + 4 * DevRTT
  $$

  ​ Typically, $\beta = 0.25$

• Three-way handshaking

  1. client host sends TCP SYN segment to server The SYN bit, is set to 1 specifies initial sequence number (client_isn), no data
  2. server host receives SYN, replies with SYNACK segment server allocates buffers
     specifies server initial sequence number (server_isn), The SYN bit, is set to 1, ACK=client_isn+1
  3. client receives SYNACK, replies with ACK segment, which may contain data.The client does so by putting the value server_isn+1 in the acknowledgment field of the TCP segment header). The SYN bit is set to 0, since the connection is establishe

  If you feel puzzled, see this table:

  Source host	Dest host	SYN	Sequence	ACK	ACKFLAG
  A	B	1	client_isn	none	0
  B	A	1	server_isn	client_isn + 1	1
  A	B	0	client_isn + 1	server_isn + 1	1

• TCP congestion control algorithm

  • AIMD:

    • Approach: increase transmission rate (window size), probing for usable bandwidth, until loss occurs.
    • additive increase: increase CongWin by 1 MSS every RTT until loss detected (congestion avoidance).
    • multiplicative decrease: cut CongWin in half after loss (CongWin$\geq$1MSS).
    • Congwin + 1 / n RTT when ACK.

  • Slow start: When connection begins, increase rate exponentially fast until first loss event

    • set CongWin = 0.5 * CongWin

  • Reaction to Timeout Event:

    • 3 duplicated ACKs:
      CongWin cut in half and grows linearly.
    • timeout event:
      CongWin = 1 and grows exponetially. To a threshold grows linearly.

• The compute of CongWin and Threshold

  • When CongWin is below Threshold, sender in slow- start phase, window grows exponentially.
    • When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly.
    • When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold.
    • When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS.

Addtion

• 重点：传输层的功能；TCP与UDP协议所提供的服务；多路复用与多路分解的概念；UDP协议的基本概念与格式；checksum方法；TCP报文段格式；序列号与确认序号；简单TCP传输模型；快速重传方法；流量控制；TCP连接建立的过程与关闭的过程；拥塞窗口计算；TCP拥塞控制算法。
• 难点：传输层与网络层的关系与区别；多路复用与多路分解的区别；滑动窗口协议；检查和校验方法；序列号与确认序号的计算方法；flag字段的填写；怎样实现TCP可靠数据传输；简单TCP传输模型实现；加倍超时间隔；快速重传机制；接收窗口的计算；三次握手；拥塞窗口与流量控制窗口的区别；拥塞控制中慢启动、对超时事件的反应处理；CongWin与Threshold的计算方法。

Chapter 4 Network Layer (about 30%)

4.1 Introduction

• Definition and difference of forwarding and routing
  • Forwarding: move packets from router’s input to appropriate router output. Like process of getting through single interchange.
  • Routing: determine route taken by packets from source to dest. Like process of planning trip from source to dest.
• possible services provided by network layer
  • transport segment from sending to receiving host
  • on sending side encapsulates segments into datagrams
  • on rcving side, delivers segments to transport layer
• forwarding table and routing table in the router.
  Conception is like themselves, forwarding table just care which interface should datagram go next, but routing table care which router should datagram go.

4.2 Virtual Circuit and Datagram Networks

• Difference of virtual circuit and datagram networks
  • Datagram: connectionless
  • VC network: connection
• Three components of virtual circuit network
  1. Path from source to destination
  2. VC numbers, one number for each link along path
  3. Entires in forwarding tables in routers along path
• VC signaling protocols: ATM, frame-relay, X.25

4.3 What’s inside a Router?

• Functions of four components of the router
  1. Input port
     • line termination
     • protocol, decapsulation
     • lookup forwarding queueing
  2. Switch fabric: conjunction input port and output port
  3. Router processor: execute routing algorithm
  4. Output port
     • buffer management
     • processing encapsulation
     • line termination
• Three techniques of switching fabrics
  • Memory
  • Bus
  • Crossbar
• Where does queuing occur: Packet queues can form at both the input ports and the output ports.

4.4 The Internet Protocol

• Format of IPV4 and IPV6 datagram and the difference

  • IPV4:

    1. Version: 0100
    2. Headlen: length of header
    3. Type of service(TOS): don’t care message detail
    4. Datagram Len: header + data]
    5. Indentifier, flags, fragmentation offset: for fragmentation and reassembly
    6. TTL: time to live
    7. Upper layer protocol
    8. Header checksum: variable(cause of TTL changed)
    9. Source and dest IP addr 32 bits each
    • IPV6:
  1. Version: 0110
  2. Priority: identify priority among datagrams in flow
  3. Flow label: identify datagrams in same “flow”
  4. Next header: identify upper layer protocol for data
  5. Hop limit: Like TTL
  6. Source and dest IP addr 128 bits each
     • Difference:
  7. 32bit ip addr -> 128bit ip addr
  8. fixed 40 bytes
  9. no fragmentation allowed
  10. no checksum
  11. no option
  12. ver from 0100 -> 0110

• Transition from IPV4 to IPV6

  • Dual stack: IPv6 nodes also have a complete IPv4 implementation as sell.
  • Tunneling: IPv6 carried as payload in IPv4 data-gram among IPv4 routers.

• IP fragmentation and reassembly

  • $fragment_num = \lceil {\frac{datagram - 20} {MTU - 20}} \rceil $

  • $ID = x$ for x in all fragments

  • $fragflag = 0$ if it is the last fragment, else 1

  • $offset = \frac{MTU - 20} {8}$

  • $lastLength = datagram - (fragment_num - 1) * ( MTU - 20 ) $

• IPV4 addressing (compute subnet address, broadcast address, subnet mask and so on, CIDR especially)

• DHCP: Dynamic Host Configuration Protocol. Allow host to dynamically obtain its IP address from network server when it joins network.

• Function of ICMP(Internet Control Message Protocol)

  1. error reporting
  2. echo request / reply
  3. ICMP msgs carried in IP datagrams.

4.5 Routing Algorithms

• default router, first-hop router, source router, destination router, shortest path and least-cost path
  • default router / first-hop router: the router attached directly to the host.
  • source router: source host’s default router.
  • destination router: destination host’s default router.
• LS algorithm and DV algorithm (compute)
  • Link State(Static):
    • $c(x,y)$: link cost from node x to y; = ∞ if not direct neighbors
    • $D(v)$: current value of cost of path from source to dest. v
    • $p(v)$: predecessor node along path from source to v
    • $N’$: set of nodes whose least cost path definitively known
  • Distance Vector(Dynamic):
    • Bellman-Ford Equation:
      $d_x(y) = \min\limits_{v}^{} \left\{c(x, y) + d_v(y) \right\}$
    • $d_x(y)$: estimate of least cost from x to y
    • $c(x,v)$: Node x knows cost to each neighbor v
    • $D_x = [d_x(y): y є N ]$: Node x maintains distance vector
    • $D_v = [D_v(y): y є N ]$: Node x also maintains its neighbors’ distance vectors, For each neighbor v, x maintains
    • $S_x = [s_x(y): y є N ]$: Node x maintains successive vector $s_x(y)$ is the successive node from x to y
• AS(autonomous systems): aggregate routers into regions, run same routing protocol
• Gateway can interplay between two AS

4.6 Routing in the Internet

• types of intra-AS and inter-AS routing protocol
  • intra-AS routing also known as IGP(Interior Gateway Protocols)
    • RIP
    • OSPF
  • inter-AS
    • BGP
• the definition of RIP, OSPF and BGP
  • RIP: routing information protocol, based on DV, uses hop count as cost metric
  • OSPF: open shortest path first, based on LS， broadcast routing info to all other routers in AS
  • BGP: border gateway protocol, based on DV

Addtion

• 重点：转发与路由的概念与区别；虚电路网络与数据报网络的原理；路由器的基本组成；哪里会产生排队；IPV4和IPV6的报文格式及两者之间的区别；IP分段与重组；IPV4寻址；ICMP协议；网络传输中各种不同路由器的概念与区别；LS路由算法；DV路由算法；路由表；ICMP协议的功能；AS的概念；自治系统内部选路算法；RIP和OSPF协议的概念与功能。
• 难点：转发与路由的区别；虚电路网络与数据报网络的区别；IP分段与重组；ICMP的功能；IPV4和IPV6的报文格式的区别；LS路由算法；DV路由算法；自治系统内和自治系统间的协议；RIP和OSPF协议的功能与区别。

Chapter 5 Link Layer and Local Area Network (about 10%)

5.1 Link Layer: Introduction and Services

• Services provided by the link layer
  1. Framing: encapsulate datagram into frame, adding header, trailer.
  2. Link access: Point-to-point link, Broadcast link, MAC protocol specifies the rules by which a frame is transmitted onto the link.
  3. Reliable delivery between adjacent nodes: move each datagram across the link without error
     seldom used on low bit-error link (fiber, some twisted pair) wireless links: high error rates.
  4. Flow control: pacing between adjacent sending and receiving nodes.
  5. Error detection: errors caused by signal attenuation, noise. receiver detects presence of errors: signals sender for retransmission or drops frame.
  6. Error correction: receiver identifies and corrects bit error(s) without resorting to retransmission.
  7. Half-duplex and full-duplex: with half duplex, a node cannot both transmit and receive at the same time, With full-duplex, the node can both transmit and receive at the same time.
• Difference of the link layer and transport, network layer: network layer is host to host, link layer is node to node.
• Conception of adapter (NIC), two types of interfaces.
  • NIC(network interface card): implements link, physical layer, attaches into host’s system buses.
    • interfaces: Ethernet card, PCMCI card, 802.11 card.

5.2 Error-Detection and Correction Techniques

• Cyclic redundancy checks - CRC (compute)

5.3 Multiple Access Protocol

• Two types of link layer channel
  • point to point: a single sender and a single receiver.
  • broadcast: multiple sender and multiple receivers.
• Conception and difference of three types of multiple access protocols, random access protocol especially
  • Channel Partitioning: divide channel into smaller “pieces” (time slots, frequency, code) allocate piece to node for exclusive use
    1. TDMA(time division multiple access)
    2. FDMA(frequency division multiple access)
    3. CDMA(code division multiple access)
  • Random Access: channel not divided, allow collisions “recover” from collisions
    1. Slotted ALOHA
    2. Pure ALOHA
    3. CSMA(Carrier Sense Multiple Access)
       • 先听后发
       • 边听边发
       • 冲突停止
       • 随机延迟后重发
  • “Taking turns”: nodes take turns, but nodes with more to send can take longer turns
    1. Polling
    2. Token passing
• LAN: local area network, a computer network concentrated in a geographical area, such as in a building or on a university campus.

5.4 Link-Layer Addressing

• MAC address: function: get frame from one interface to another physically-connected interface (same network), has 48bits long, permanet and unique.

• Difference of MAC address and IP address, hostname

  • MAC flat address: portability, can move LAN card from one LAN to another
  • IP hierarchical address not portable, depends on IP subnet to which node is attached

• Conception and principle of ARP: Translates IP addresses to MAC addresses , only resolves IP addresses only for nodes on the same subnet.

  • ARP query:

    1. Same LAN, Query packet, A want to find B’s MAC address, it’s a kind of broadcast.

    2. Same LAN, Response packet, B sends to A specifically.

    3. Different LAN, suppose R is router between two subnets. Frame A to R.

    4. Different LAN , Frame R to B.

       Condition	Source IP	Dest IP	Source MAC	Dest MAC
       1. Query packet	A’s IP	B’s IP	A’s MAC	FF-FF-FF-FF-FF-FF
       2. Response packet	B’s IP	A’s IP	B’s MAC	A’s MAC
       3. Frame A to R	A’s IP	B’s IP	A’s MAC	R’s interface MAC
       4. Frame R to B	A’s IP	B’s IP	R’s interface MAC	B’s MAC

5.5 Ethernet

• Format of Ethernet frame

  1. Preamble: used to synchronize receiver, sender clock rates
  2. Dest addr(MAC) (6 bytes)
  3. Source addr(MAC) (6 bytes)
  4. Types(2 bytes): indicates higher layer protocol
  5. Data
  6. CRC(4 bytes)

• Mechanism and principles of CSMA/CD

  • Jam Signal: make sure all other transmitters are aware of collision; 48 bits
  • Expnential Backoff: adapt retransmission attempts to estimated current load

• Service provided by Ethernet

  • connectionless: No handshaking between sending and receiving NICs
  • unreliable: receiving NIC doesn’t send acks or nacks to sending NIC. Stream of datagrams passed to network layer can have gaps (missing datagrams). Gaps will be filled if app is using TCP otherwise, app will see gaps.
  • baseband transmission: The adapter sends a digital signal directly into the broadcast channel.
  • Ethernet’s MAC protocol: CSMA/CD
  • Encoding: Manchester encoding(up edge is 1, down edge 0)

5.6 Link-Layer Switches

• Difference of forwarding and filtering

  • Filtering: is the ability of a switch to determine whether a frame should be forwarded to some interface of should just be dropped
  • Forwarding: is the ability to determine the interfaces to which a frame should be directed and then directing the frame to those interfaces(use a switch table)

• Functions of hubs and switches

  • hub: physical-layer (“dumb”) repeaters: acts on individual bit rather than on frames, bits coming in one link go out all other links at same rate, all nodes connected to hub can collide with one another
  • switch: smarter than hubs, take active role
    store, forward Ethernet frames examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment

• Compare hubs and switches to routers

  Attribute	Hubs	Routers	Switches
  traffic isolation	no	yes	yes
  plug & play	yes	no	yes
  optimal routing	no	yes	no
  cut through	yes	no	yes
  layers	physical	network	link

Addtion

• 重点：链路层提供的服务；链路层与网络层和传输层的不同；CRC校验法；多址访问协议；随机访问协议；TDM、FDM、CDMA协议；局域网；MAC寻址及其与IP寻址的区别；ARP、DHCP协议的功能；以太网帧的结构；CSMA/CD协议原理；交换机与集线器的功能；交换机、集线器和路由器的区别。
• 难点：CRC校验法；多址访问协议；随机访问协议；MAC寻址和IP寻址的区别；ARP、DHCP协议的功能；CSMA/CD协议的原理；交换机、集线器和路由器的区别。

Summary

1. Port number and protocols

   Protocol	Port number	Transport layer protocol
   HTTP	80	TCP
   FTP	21	TCP
   SMTP	25	TCP
   POP3	110	TCP
   IMAP	143	TCP
   DNS	53	UDP

   • p2p based on HTTP, it have no self protocol.

2. TCP, UDP server and action

   Protocol	Server	Action
   UDP	error detection	check sum
   TCP	connection-orient	three way handshake
   TCP	in-order and reliable	sequence, ACK
   TCP	flow control	receive window
   TCP	congestion control	AIMD, slow start, reaction to timeout
   TCP	error detection	check sum

3. Layers duty

   Layer	Between	Implement method
   transport	process	socket - port number
   network	host	router - IP address
   link	node	hubs or switches - MAC address

4. CDMA (code division multiple access) is different from CSMA(Carrier Sense Multiple Access), they are confusable.

5. In fragmentation and reassembly, length means bytes length include headers, but ask you to write bytes, it means payload in the fragment, do not include headers.

• Type
  • 1.3 Types of delay compute
  • 2.2 HTTP protocol html
  • 3.3 Check sum compute
  • 3.5 TCP congestion control algorithm with timeout and duplicated ACK
  • 3.5 Receive window
  • 3.5 TCP connection management(simple condition)
  • 4.1 Forwarding Table: select link interface – Longest prefix matching
  • 4.4 IPV4 addressing (compute subnet address, broadcast address, subnet mask and so on, CIDR especially)
  • 4.4 IP fragmentation and reassembly
  • 4.5 Routing Algorithm: LS and DV
  • 5.2 Cyclic redundancy checks - CRC