Introduction
Ethernet 是过去30年以来最为成功的局域网（local area networking）技术。
1. First widely used LAN technology （第一次被广泛使用的局域网技术）
2. kept up with speed race: 10 Mbps � 100 Gbps
3. Connectionless: No handshaking between sending and receiving NICs（Network Interface Card，网卡）
不建立连线。
4. Unreliable: receiving NIC doesn't send ACKs or NACKs to sending NIC
不可靠。
ACK：Acknowledgement，即确认字符，在数据通信中，接收站发给发送站的一种传输类控制字符。表示发来的数据已确认接收无误。
NACK：Nacknowledge，说明数据传输不正确，需要进行重传。
5. Ethernet's MAC protocol: Carrier Sense Multiple Access with Collision Detection (CSMA/CD，即带冲突检测的载波监听多路访问技术)
Ethernet Topologies
1. Bus Topology
Bus topology popular through mid 90s.
The bus is the data link in a bus network. The bus can only transmit data in one direction, and if any network segment is severed, all network transmission ceases.
A host on a bus network is called a station or workstation. In a bus network, every station receives all network traffic（流量）, and the traffic generated by each station has equal transmission priority. Each network segment is, therefore, a collision domain. In order for nodes to transmit on the same cable simultaneously（同时）, they use a media access control technology such as carrier sense multiple access (CSMA) or a bus master. （引用自 wikipedia ）
collision domain：在以太网中，如果某个CSMA/CD网络上的两台计算机在同时通信时会发生冲突，那么这个CSMA/CD网络就是一个冲突域。
all nodes in same collision domain (can collide with each other)
2. Ethernet (10Base5)
An Ethernet segment is implemented on a coaxial cable of up to 500 m.
Hosts connect to an Ethernet segment by tapping into it.
A transceiver (a small device directly attached to the tap) detects when the line is idle and drives signal when the host is transmitting. （transceiver 既可以接受信号，也可以发送信号）
The transceiver also receives incoming signal.
The transceiver is connected to an Ethernet adaptor（网卡） which is plugged into the host. But now most are built in into the computers.（现在大部分网卡已经做成内置，如笔电）
The protocol is implemented on the adaptor.（指 CSMA/CD 这个协议被实作在网卡内部的芯片中）
Each bit has a transition
Allows clocks in sending and receiving nodes to synchronize to each other
之所以要采用 Manchester Encoding，是为了同步时钟。接收方利用包含有同步信号的特殊编码从信号自身提取同步信号来锁定自己的时钟脉冲频率，达到同步目的。
Manchester Encoding 将时钟和数据包含在数据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，每位编码中有一跳变，不存在直流分量，因此具有自同步能力和良好的抗干扰性能。但每一个 bit 的 transition 都被调成两个电平。
2. repeaters
Multiple Ethernet segments can be joined together by repeaters. 多个网段可以通过 repeaters 连接在一起。
A repeater is a device that forwards digital signals. 10Base5 Ethernet 一个网段500米， 数字信号传送500米后会减弱不少，repeater 可以起到放大信号的作用。
No more than four repeaters may be positioned between any pair of hosts.(An Ethernet has a total reach of only 2500 m.
下图示例了两个网段通过 repeater 来连接：
下图示例了5个网段的连接：
3. Ethernet (10Base2)
Ethernet 的第二代技术
Instead of using coax cable, an Ethernet can be constructed from a thinner cable known as 10Base2 (the original was 10Base5)
10 means the network operates at 10 Mbps
Base means the cable is used in a baseband system
2 means that a given segment can be no longer than 200 m
10Base2 使用更细的电缆。
4. Ethernet (10BaseT)
New Technologies in Ethernet
-> Another cable technology is 10BaseT
T stands for twisted pair （使用双绞线）
Limited to 100 m in length
-> With 10BaseT, the common configuration is to have several point to point segments coming out of a multiway repeater, called Hub
之前使用 10Base5 或者 10Base2 技术时，我们通常直接把 cable 是放地上的，这样只要有一个网段不小心断开了，那么所有的网络就瘫痪了。为了管理线路，我们在 10BaseT 技术中可以使用一个 Hub 来管理双绞线。
注意使用 Hub ，采用的仍然是广播的方式。只要有一台电脑发送讯号了，那么所有电脑都会收到。
5. Star Topology
相对于 Bus Topology，今天我们盛行的是 Star Topology。
active switch in center
each "spoke" runs a (separate) Ethernet protocol (nodes do not collide with each other)
注意：Switch 的每一个端口相当于一个网卡，每一台电脑与交换机连接，都是 point to point ，也就是网卡与网卡相连接，因此每个网段相当于只有两台电脑。Switch的每个端口是可以处理内容，它可以选择将其滤掉或者选择性的转送到某一台机器，而 Hub 同 Repeater 一样，只可以将讯号进行转送，而没有处理内容的能力。
Description
有1至 N编号的N 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）做游戏。游戏开始时，以正整数m作为报数上限值，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将其密码作为新的报数上限值，从其下一个人开始重新报数，如此下去，直至所有的人全部出列为止。如N=7，m=20，每个人的密码依次是：3，1，7，2，4，8，4，则出列顺序为6，1，4，7，2，3，5。要求最后一个出列的人的编号。
Input
有多组测试数据。每组有两行，第1行有2个正整数n，m，（n，m<100），n表示人数，m表示开始时报数上限值，第2行有n个整数，一次表示第1，2，…，个人的密码。
Output
对每组测试数据，输出最后一个人的编号。
Sample Input
Sample Output
using namespace std;
void DeleteNum(int num,int *a,int *b);
void Display (int *a);
int main ()
{
int a[100],b[100];
int m,n,i;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
{
a=i+1;
cin>>b;
}
b='\0';
a='\0';
int length=n;
int index=m%n;
while(length!=1)
{
if(index==0)
{
index=length-1;
}
else
{
index--;
}
m=b;
DeleteNum(index,a,b);
length--;
index=m%length;
}
cout<<a<<endl;
}
}
void DeleteNum(int num,int *a,int *b)//删除目标，并将删除元素的下一个作为第一个数组元素
{
int ALength=0;
for(int i=0;a!='\0';i++)
{
ALength++;
}
int temp[100];
int temp2[100];
int i;
for (i=0;a!='\0';i++)
{
num++;
if(num>=ALength)
{
num-=ALength;
}
temp=a[num];
temp2=b[num];
}
temp='\0';
temp2='\0';
int j;
for(j=0;j<ALength-1;j++)
{
a[j]=temp[j];
b[j]=temp2[j];
}
b[j]='\0';
a[j]='\0';
}
void Display (int *a)
{
for(int i=0;a!='\0';i++)
cout<<a<<" ";
cout<<endl;
}
大致思路：将每一种情况转化为第一次的情况（即第一个报数的人是数组的第一个元素），这样大大简化了过程。
本文链接：Josephus问题，转载请注明。
没有评论:
发表评论