Network-CS144 の 3 Packet Switching
分组交换
特点：
- Packets被独立地路由，通过查找当前路由的局部路由表
- 所有的Packets共享一个完整的Link
- 路由不需要维护通信状态
- 路由是有缓存的
- 缓存在以下情况下会存在Packets：
- When two or more packets arrive at the same time
- During periods of congestion
- 缓存在以下情况下会存在Packets：
Curcuit switching
建议了解下通信历史
建议了解下网络历史
特点：
- Each call has its own private, guaranteed, isolated data rate from end-to-end
- A call has three phases:
- Establish circuit form end-to-end
- Communicate
- Close circuit
- Originally, a circuit was end-to0end physical wire
- Nowdays, a circuit is like a virtual private wire
能否在计算机通信使用Curcuit switching
- Inefficient: 计算机通信是爆炸式的，通信需要比较高的速度，不然影响体验
- Diverse Rates: 计算机通信在不同情况下速度是不同的，比如 a web server streaming video at 6Mb/s, typing at a. Character per second. A fixed rate circuit will not be much use.
- State management. Curcuit switch maintain per-communication state, which must be managed.
Efficient use of expensive links
- Links were assumed to be expensive and scarce
- Packet switching allows many, bursty flows to shae the same link efficiently
- Circuit switching is rarely used for data networks, ... because of very inefficient use of the links
(PS: 其实就是说分组交换允许共享链接，而电报交换每次链接都是一个新的链路，重新构建一个Link代价是比较大的)
Resilience to failure of links & routerss
- For high reliability, [the internet] was to be a datagram subnet, so if some lines and [routers] were destroyed, messages could be ... rerouted
(PS: 分组交换即使中间路由损坏了，也可以通过其他路由重新路由)
排队机制是ATM交换中一个极为重要的内容，队列的溢出会引起信元丢失，信元排队是交换时延和时延抖动的主要原因，因此排队机制对ATM交换机性能有着决定性的影响。基本排队机制有三种：输入排队、输出排队和中央排队。这三种方式各有缺点，如输入排队有信头阻塞，交换机的负荷达不到60%；输出排队存储器利用率低，平均队长要求长，而中央排队存储器速率要求高、存储器管理复杂。同时，三种方式有各有优点，输入队列对存储器速率要求低，中央排队效率高，输出队列则处于两者之间，所以在实际应用中并没有直接利用这三种方式，而是加以综合，采取了一些改进的措施。
分包交换
what does a packet switch look like ?
what does a packet switch do ?
- 以太网交换机(Ethernet switch)
- 因特网路由器(Internet router)
How address lookup works
- 以太网交换机(Ethernet switch)
- 因特网路由器(Internet router)
以太网交换机：
Ethernet switch
- Examine the header of each arrving frame
- If the Ethernet DA(Destniation addrdress) is in the forwarding table, forward the frame to correct output port(s)
- If the Ethernet DA is not in the table, boradcast the frame to all posts
- Entries in the table are learned by examining the Ethernet of arriving packets.
Internet Router
If the Ethernet DA of the arriving frame belongs to the router, accept the frame. Else drop it
Examine the IP version number and length of the datagram
Decrement the TTL, update the IP header checksum.
Check to see if TTL == 0
if the IP DA is in the forwarding table, forward to the correct egress port(s) for the next hop
Find the Ethernet DA for the next hop router
Create a new Ethernet frame an d send it
Lookup address: How is the address looked up into forwarding table ?
Switching: How is the packet sent to the correct output port ?
Lookup address: Ethernet
Methods:
- Store address in hash table (maybe 2-way hash)
- Look for exact match in hash table
Lookup address: IP
Lookup is a longest prefix match, not an exact match
Method 1:
Method 2:
switching packeted to the egress port(向导出端口转发):
- Output queuing and shared memory（输出队列和共享内存，输出存在缓存，如下图的Buffer memory）
- Input queuing and head-of-line blocking (输入队列，输出存在缓存)
- Virtual output queues（虚拟输出队列）
但是存在线头阻塞（Head of line blocking），由于其影响，速率下降了，因为同一时刻，input queue内最前面的挡住了后面排队的：
解决方法：Virtual Output Queue
The simplest and slowest switches uses output queuing, which minimizes packet delay.
High performance switches often use iput queuing, with virtual output queues to maximize throughput.
lab 0:
使用操作系统的TCP和流式socket抽象，基于Internet写一个fetch web page的程序：
- 使用IDE打开../apps/webget.cc
- 在ge tURl函数里实现你的代码
- 就像该文件里描述的那样，实现一个简单的web客户端（使用http协议）（注：使用
TCPSocketandaddress这两个类）
提示：
- Please note that in HTTP, each line must be ended with “” (it’s not sufficient to use just “” or endl).
- Don’t forget to include the “Connection: close” line in your client’s request. This tells the server that it shouldn’t wait around for your client to send any more requests after this one. Instead, the server will send one reply and then will immediately end its outgoing bytestream (the one from the server’s socket to your socket). You’ll discover that your incoming byte stream has ended because your socket will reach “EOF” (end of file) when you have read the entire byte stream coming from the server. That’s how your client will know that the server has finished its reply.
- Make sure to read and print all the output from the server until the socket reaches “EOF” (end of file)—a single call to read is not enough. 确保读取和打印所有来自服务器的输出，知道socket达到了EOF（文件末尾）
- 希望你只用9行代码
正如上面的TCPSocket类在网络通信中是非常重要的，even
though the Internet itself only provides the service of “best-effort”
(unreliable) datagrams.
下面将实现一个字节流，已经提供了相关的抽象。
字节s从input侧写入，并以相同顺序从output侧读取，字节流是有限的writer可以end the input, 表示没有更多字节写入了。reader一直读，直到遇到了EOF。