返回 N Vs.选择性重复 [英] Go Back N Vs. Selective Repeat
问题描述
对于流水线错误恢复，是否有任何理由为什么 Go Back N 比选择性重复更受欢迎?
Are there any reasons why Go Back N would be preferred over selective repeat for pipelined error recovery ?
显然，SR 在接收端需要一个缓冲区(大小合适)，这是它唯一的弱点吗?
Clearly, SR needs a buffer (appropriately sized) at the receiver's end, is that its only weakness ?
GBN 是唯一首选的任何情况吗?
Any situation where GBN would be exclusively preffered?
推荐答案
我的回答可能和你的问题不太相关，但重点是Selective Repeat的接收缓冲区问题.
选择性重复是处理 UDP 不可靠性的更智能和有效的方法.
My answer might not be too relevant to your question, but it focuses on receive buffer problem of Selective Repeat.
Selective Repeat is much more smart and efficient way of dealing with unreliability of UDP.
但前提是它实施得很好.如果我们很好地实现它，那么我们就不需要担心接收缓冲区.
But only if it's implemented well. And If we implement it nicely then we don't need to worry about receive buffer.
例如，如果您选择线程方式，那么将数据保存在缓冲区中是很容易的.现在，您无需为整个早期到达的数据制作一个缓冲区.
For example If you choose threading way, then it's quite easy to keep data in buffer. Now you don't need to make one single buffer for whole early arrived data.
所以线程的方式实际上是这样的:
So threading way actually goes like this:
- 接收器程序将接收数据包.
- 检查校验和
- 如果没有损坏，请使用数据包编号检查重复
- 发送ACK
- 如果是第一次打包，我们将进行下一步，否则什么都不做
- 为此数据包创建一个线程.我们将平等地处理每个数据包，而不管它们的顺序如何.
- 该线程的功能将使用简单的信号量等待和信号机制，我们将在后面讨论.
- 将此数据包保存到缓冲区*，因此我们不需要为所有早期到达的数据包设置一个缓冲区，但我们可以为每个数据包制作不同的指针.我们稍后会讨论这个问题.
- 创建线程后，我们将检查此数据包编号是否位于上次保存的数据包旁边.因此，我们可以为此使用
packetCounter. - 如果是下一个，我们将signal(semaphore[thisPacketNumber]).这将告诉该数据包的线程轮到您继续执行您的任务，只需将此数据包保存到文件.
- 如果它不是上次保存的数据包的倒数第二个，我们会将其放入等待队列，即
waitingQueue[thisPacketNumber] = true;
- Receiver Program going to receive packet.
- Check for checksum
- If not corrupted, check for duplication using packet Number
- Send ACK
- If it's first time packet, We going to do next steps, else DO Nothing
- Create a Thread for this packet. We are going to process each packet equally irrespective of their sequence.
- The function of this thread will use simple semaphore wait and signal mechanism, which we will discuss later.
- Save this packet to buffer*, So we don't need a single buffer for all the early arrived packets, but we can make different pointers for each one of them. We will discuss about this later.
- After creating thread we going to check if this packet number is just next to our last saved packet. So we can use a
packetCounterfor that purpose. - If it's just next, we going to signal(semaphore[thisPacketNumber]). This will tell the thread of this packet that it's your turn to go ahead and perform your task, which is simply saving this packet to file.
- And if it's not the next to last saved packet, we going to put it in a waiting queue i.e.
waitingQueue[thisPacketNumber] = true;
这就是 while 循环部分.我们不需要一个单独的缓冲区来存储所有这些数据包或在它们之前的兄弟数据包(数据包)之前到达的数据包.
So that's it for the while loop part. We don't need one single buffer to store all these packets or packets that arrived before their previous siblings(packet).
所以现在我们有两个挑战，一个是找到正确的数据结构来分别存储每个数据包，另一个是保持我们的<强>线程队列流畅.
So now we have two challenges, one is to find right data structure for storing each packets separately and another is to keep our thread queue flowing well.
让我们先看看第二个挑战的解决方案.
Let's see the solution of our second challenge first.
这是我们要为每个原始数据包传递给线程的函数.
this is our function that we going to pass to our thread for each original packet.
//this is our packetQueue
//Each packet will be alloted one instance of this functionality using threads
//So here, we have packetNumber of each respective packet
//Each packet will call wait(on Its Respective Semaphore) , shown below.
//Since we are going to initiate there respective semaphores from 0;
//They will enter in a waiting state and will only awake after getting signal from somewhere else or another packet.
//So As we saw in the while loop section, we are signaling the current packet if it's next to last saved packet.
//Once this packet got signaled, it will perform it's task, i.e. saving this packet into file.
//*****Increment the packetCounter++
//And then check if next packet in the sequence is waiting in the queue.....
//here we are using waitingThread[] boolean array for that purpose, you can use waitingQueue[] as it's name.
//if yes then signal next packet.
//And **TADA** it's done
unsigned long CALLBACK packetQueue(void *pn){
int packetNumber = (int) pn;
wait(packet[packetNumber]);
char *dt = dataBucket[packetNumber]->data;
save_line_into_file(dt);
waitingThread[packetNumber] = false;
packetCounter++;
if(waitingThread[packetNumber+1]){
signal(packet[packetNumber+1]);
}
}
类型声明在 Windows 和Linux.这是用于 Windows 的.
Types declaration can vary in Windows & Linux. This one is for Windows.
因为您可以在随代码提供的注释中阅读它的功能，所以我们可以讨论下一个挑战，即第一次挑战.
As you could read the functionality of it in comments provided with code, we can talk about next challenge, i.e. First challenge.
用于分别保存每个数据包的数据结构.
Data-Structure for saving each packet separately.
我们简单地定义一个结构体并为其指针分配一些内存.
We simply define a struct and allocate some memory to it's pointer.
所以我们有:
typedef struct{
char data[200];
} DataBuffer;
DataBuffer* dataBucket[ESTIMATED_NO_OF_PACKETS];
ESTIMATED_NO_OF_PACKETS 可以是任何数字，具体取决于您估计的接收数据大小(无需正确)，例如500
ESTIMATED_NO_OF_PACKETS can be any number depending on your estimated size of receiving data (No need to be correct), e.g. 500
或者我们使用 Recycler Buffer 之类的东西，通过在将指针保存到文件后释放指针的内存.我们可以使用 base 和 window 方法，就像:
Or we use something like Recycler Buffer, By freeing the memory of pointer after saving it to file. We can use base and window method, which is like:
Set window = 100
AND base = 0
AND ESTIMATED_NO_OF_PACKETS = 100;
并成功保存 100 个数据包后使 base = 100所以我们可以像这样从缓冲区访问数据 *dataBucket[base+thisPacketNumber];
And after successfully saving 100 packets make base = 100
so we can access the data from buffer like this *dataBucket[base+thisPacketNumber];
并且不要忘记在每次保存操作后释放每个指针的内存.
And don't forgot to free the memory of each pointer after each save action.
最后这就是我们原来的包处理部分的样子:
So finally this is how our while original packet processing section going to look like:
//After sending ACK of this packet
//We can check if this is duplicate packet or not
//if(original){...
//Create Semaphore for this packetThread
packet[packetNumber] = create(0);
//Create Thread for this packet
//We gonna treat each request equally
//that's why we are putting each thread in queue.
//And a dataBucket Structure to pass parameters to thread
dataBucket[packetNumber] = (DataBuffer*)malloc(sizeof(DataBuffer));
strcpy(dataBucket[packetNumber]->data, data);
CreateThread(NULL,0,packetQueue,(void *)packetNumber,0,&tid);
//Now check if this the next packet in queue of not.
//If yes then signal this packet
//else put it in queue
if((packetCounter+1) == packetNumber){
signal(packet[packetNumber]);
}else{
waitingThread[packetNumber] = true;
}
此代码仅与 Windows 兼容，但您可以为 Linux 或 Mac 轻松更改它们
This code is compatible with Windows only, but you can easily change them for Linux or Mac
其他一些有用的功能:
void wait(semaphore h) { // wait for a semaphore
WaitForSingleObject( h, MAXLONG);
}
void signal(semaphore h) { // signal a semaphore
ReleaseSemaphore(h,1,NULL);
}
semaphore create(int v) { // create a semaphore with value v
return CreateSemaphore(NULL,(long)v, MAXLONG, NULL);
}
如果我忘记添加任何内容，请提供一些反馈.
Do give some feedback if I forgotten anything to add.
这篇关于返回 N Vs.选择性重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
