Advanced Computer Network Review(5)——COPE

References for this article come from ：
1. Original paper 《XORs in The Air: Practical Wireless Network Coding》(SIGCOMM’06)
2. Course presentation

According to the review outline , about COPE We should understand the following questions ：
1. understand butterfly The Internet
2. understand COPE The coding algorithm of
3. understand COPE An example of

The core of this paper is the use of XOR (XOR) A feature of operation , namely $a\oplus b\oplus b=a$, namely The original value will become the original value after two exclusive or a phase value , This is a fundamental principle of the coding technology used in this paper .

---

1. understand Butterfly The Internet
Throw out in the text Butterfly The network is to illustrate Network coding (network encoding) Technology does have practical benefits for improving network throughput . What is network coding technology ？ The explanation given in the text is as follows ：

Network coding technology allows routers to mix the information content of each packet before forwarding it

Butterfly The schematic diagram of the network is as follows ：

The limitations and conditions are as follows ：
1.S1 Want to put ai To R1 and R2,S2 Also want to bi To R1 and R2
2. Only one message can be sent at a time on any link

If network coding technology is not used , that The intermediate link will become a bottleneck link . Because only one message can pass through the link at a time , that S1 towards R2 Sending action of and S2 towards R1 Sending action of It will be squeezed on the intermediate link , Wait a moment Two units of time Can all pass through the intermediate link ( One by one through the intermediate link ).

But if network coding technology is used ( here Refers specifically to the use of XOR operations Mixing multiple packets ), It can be transmitted on the intermediate bottleneck chain $a\oplus b$ Mixed packets ( One unit time ), This mixed packet arrives R1 and R2 after , And again Packets from two edge links Perform XOR operation to complete unpacking .

This Butterfly The small example of network is equivalent to an introduction to this article , Let people believe that network coding technology can effectively improve network throughput and performance .

---

2. understand COPE The coding algorithm of
COPE It is a kind of coding technology dedicated to Wireless Mesh Networks , It mainly combines three core technologies ：
2.1 Opportunistic Listening

I don't know what's going on here Opportunistic Listening How to translate appropriately ( Opportunistic monitoring ？ laugh ). In the traditional wireless network communication analysis, we often Broadcast characteristics in Wireless Networks Deliberately shield , It is abstracted into Simple point-to-point communication To simplify the analysis .

but COPE Go the opposite way , We should not only face the broadcast characteristics of wireless links , We should also make use of such broadcast characteristics to make various network devices As well as exchange of needed goods . It's also very simple , Since network coding technology is used to mix packets , It is necessary to ensure that the receiver can successfully decode the original packet , At this time, the sender must know the receiver ( Next jump ) Data packets already held .

This is through opportunistic listening To achieve ,COPE Set the listening mode of each node to Hybrid mode , In this mode, the node will receive any monitored packets , So as to know what node has what packet information . More Than This , There are also Send broadcast messages to inform neighbors Packets held locally .

So we see ,COPE Two methods are used in ：

• Set the device to hybrid mode
• Send broadcast messages to exchange what you need

Try to make Each node can timely grasp the packet information held by other neighbor nodes , So as to provide enough decision-making information for the later coding process .

But we should also see , The process is opportunistic Of , Try as hard as you can , But still There is no guarantee that the information obtained at this time must be complete , About why , So let's look down .

2.2 opportunistic coding
Mix Packets locally on a node , Its There are many possible combinations , So which one should we choose in the end , The article directly gives the goal of coding ：

maximize the number of native packets delivered in a single transmission, while ensuring that each intended nexthop has enough information to decode its native packet

Translate it , We pursue two points ：

• Ensure that the next hop router has enough information to unpack
• On the basis of meeting the above conditions , Mix as many bags as possible

A node needs to make the final decision of hybrid package , You have to know which packets the neighbor nodes hold , After knowing the ownership of neighbor nodes, you can Choose a strategy that can mix the most packets . Here is a natural question , That is, how to know exactly which bags the neighbors have ？

Actually in 2.1 The two methods proposed in part are to do this , But it is not complete . Because the network sometimes has Severe congestion occurs , At this time, the message broadcast by the neighbor node may be blocked in the network . If the local node The latest message that the neighbor node holds the packet is not received , Will cause it to make a Non optimal or even impossible to unpack The wrong decision-making .

2.3 Learning Neighbor State
How to alleviate the above situation , One word , guess ！

In fact, in Wireless Networks , Routers always dynamically Observe the quality of all links in the network , Link quality has different evaluation indexes , But the commonly used evaluation index is Probability of successful delivery ( To put it bluntly, there is no packet loss or error , Isn't that nonsense :), The easier it is to successfully deliver , The higher the link quality , The less it costs .

COPE When it is impossible to determine whether the neighbor node has a specific packet , It defaults that the probability of this neighbor owning a packet is The probability of successful delivery of the link between the last hop of this packet and its neighbors . It's a little twisted , But there is no need to study it in detail , Just take it as a certain probability value , This information will be considered by the node as the probability of a neighbor owning a packet , This will be used in the later Algorithm .

Now we can see the details of the coding algorithm ！

2.4 Dive into Packet Coding Algorithm

The design of coding algorithm follows three main points ：

• Never delay forwarding to wait for mixing opportunities

If the current packet to be forwarded has no chance of mixing , Then forward it directly , and Never wait passively until there is a mixing opportunity to forward .

• When mixing, give priority to packages with similar length

Mixing packets of similar length will save more network bandwidth , But if there is really no bag of similar length , Then put the Short packets are filled and then mixed with long packets No problem .

• COPE Never mix two packages with the same next hop

This is also obvious , Because if you do this, you can't unpack the next jump , therefore The opportunity of mixing packets must be distributed between different packets in the next hop .

In order to complete the decision of mixed packets more efficiently ,COPE In the implementation, we introduce A pair of virtual channels Used exclusively for the storage of The next hop is not the packet of the current neighbor . A pair is because the introduction of virtual channels also takes into account the length , Less than 100bytes Of packets are grouped in a queue , The remaining long packets are placed in another queue , In this way, you can find the right length of packages that can be mixed faster .

Other design considerations include the disorder of packages , This COPE Ensure the orderly arrival of data through a module , Press the table . Finally, try to Ensure that neighbors have the highest possible probability of completing unpacking , We have mentioned this above , For packets that can be determined to be owned by neighbors , The probability is 1, For packets that cannot be determined whether the neighbor owns , Just Guess through link quality , This probability is obviously <1. We Set a threshold G(e.g 0.8), Before executing the action of mixed package , Calculate if you mix this bag , Will it make the probability of solving the package P Less than this threshold , So as to decide whether to mix this bag .

Write here , The complete algorithm can be derived ：

Write here , Suddenly I feel that the above example is unnecessary ( It's so simple )… Just be lazy :)
Thank you for accompanying me 《 By Lake Baikal 》
Love & Peace, Good Night!