当前位置:网站首页>Advanced Computer Network Review(5)——COPE
Advanced Computer Network Review(5)——COPE
2022-07-06 09:02:00 【Zheyuan Zou】
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 ⊕ b ⊕ b = a a \oplus b \oplus b = a a⊕b⊕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 ⊕ b a \oplus b a⊕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!
边栏推荐
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- LeetCode:39. 组合总和
- [sword finger offer] serialized binary tree
- 力扣每日一题(二)
- LeetCode:214. 最短回文串
- LeetCode:34. Find the first and last positions of elements in a sorted array
- Detailed explanation of dynamic planning
- CUDA realizes focal_ loss
- LeetCode:836. Rectangle overlap
- requests的深入刨析及封装调用
猜你喜欢
BMINF的後訓練量化實現
自定义卷积注意力算子的CUDA实现
Navicat Premium 创建MySql 创建存储过程
Problems encountered in connecting the database of the project and their solutions
Computer graduation design PHP Zhiduo online learning platform
如何正确截取字符串(例:应用报错信息截取入库操作)
What is MySQL? What is the learning path of MySQL
Simple use of promise in uniapp
LeetCode:236. The nearest common ancestor of binary tree
BN折叠及其量化
随机推荐
[today in history] February 13: the father of transistors was born The 20th anniversary of net; Agile software development manifesto was born
To effectively improve the quality of software products, find a third-party software evaluation organization
How to effectively conduct automated testing?
[text generation] recommended in the collection of papers - Stanford researchers introduce time control methods to make long text generation more smooth
In depth analysis and encapsulation call of requests
vb. Net changes with the window, scales the size of the control and maintains its relative position
Implement window blocking on QWidget
CUDA implementation of self defined convolution attention operator
Unsupported operation exception
[OC foundation framework] - string and date and time >
Booking of tourism products in Gansu quadrupled: "green horse" became popular, and one room of B & B around Gansu museum was hard to find
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Advanced Computer Network Review(5)——COPE
Intel Distiller工具包-量化实现1
[OC]-<UI入门>--常用控件-提示对话框 And 等待提示器(圈)
Cesium draw points, lines, and faces
Variable length parameter
LeetCode:剑指 Offer 42. 连续子数组的最大和
LeetCode:387. 字符串中的第一个唯一字符
Navicat premium create MySQL create stored procedure