Difference between revisions of "The Wunet Protocol"
m |
m |
||
(9 intermediate revisions by the same user not shown) | |||
Line 13: | Line 13: | ||
* ''Network Virtualization'' | * ''Network Virtualization'' | ||
− | |||
* ''Unicast and Multicast Packets'' | * ''Unicast and Multicast Packets'' | ||
− | ** | + | * ''Virtual Link Rate Guarantee'' |
+ | * ''Virtual Link Weighted Fair Sharing'' | ||
* ''Route Learning'' | * ''Route Learning'' | ||
− | |||
* ''No-Route Flooding'' | * ''No-Route Flooding'' | ||
− | + | * ''Upstream Subscription Propagation'' | |
− | * ''Upstream | ||
− | |||
* ''Spoofing Protection'' | * ''Spoofing Protection'' | ||
− | |||
A version of Wunet that is targeted at conventional processors has been implemented in C++. | A version of Wunet that is targeted at conventional processors has been implemented in C++. | ||
Line 33: | Line 29: | ||
<pre> | <pre> | ||
+ | labels: hosts, routers, links | ||
+ | |||
H11 H12 H13 H21 H22 H23 ... | H11 H12 H13 H21 H22 H23 ... | ||
− | + | | ^ | ^ | ^ | ^ | ^ | ^ | |
− | ---- | + | v | v | v | v | v | v | |
− | + | 1 2 3 1 2 3 | |
− | + | ||
+ | R1 4-----------> R2 | ||
+ | <-----------4 | ||
+ | 6| 5\ 6/|5 | ||
+ | v \ / v | ||
... | ... | ||
− | R4 ------------ R3 | + | R4 ------------> R3 |
+ | <------------ | ||
− | + | | ^ | ^ | ^ | ^ | ^ | ^ | |
− | + | v | v | v | v | v | v | | |
− | |||
H11 H12 H13 H21 H22 H23 ... | H11 H12 H13 H21 H22 H23 ... | ||
</pre> | </pre> | ||
− | A Wunet network is | + | A Wunet network contains host nodes, router nodes and links that interconnect the nodes. |
− | + | The figure (right) shows four virtual routers directly connected to each other and each router is directly connected to three hosts. | |
− | + | ||
+ | Each host has one virtual link, and each router has six virtual links. | ||
+ | A link between two nodes is ''virtual'' in the sense that it is actually a path in the underlying actual network. | ||
+ | An example of the actual network might be an IP network where a virtual link is a communication path between two UDP endpoints (i.e., an IP address and UDP port number). | ||
+ | |||
+ | [[ Image:wunet-simple-overlay.png | thumb | right | 400px | The Overlay Network ]] | ||
+ | |||
+ | In the figure shown right, XXX | ||
+ | |||
+ | = Virtual Links = | ||
+ | |||
+ | LT: lnum --> (peerEP, type, padr, bitRate, pktRate) | ||
+ | |||
+ | R1 LT: | ||
+ | |||
+ | {| border=1 cellspacing=0 cellpadding=3 | ||
+ | ! lnum || peerEP || type || padr || bitRate || pktRate | ||
+ | |- align="center" | ||
+ | | 1 || 192.168.1.64:0 || host || 11 || 30000 || 15000 | ||
+ | |- align="center" | ||
+ | | 2 || 192.168.1.65:0 || host || 12 || 30000 || 15000 | ||
+ | |- align="center" | ||
+ | | 3 || 192.168.1.66:0 || host || 13 || 30000 || 15000 | ||
+ | |- align="center" | ||
+ | | 4 || 192.168.2.32:30123 || router || 200 || 30000 || 15000 | ||
+ | |- align="center" | ||
+ | | 5 || 192.168.2.80:30123 || router || 300 || 30000 || 15000 | ||
+ | |- align="center" | ||
+ | | 6 || 192.168.1.32:30123 || router || 400 || 30000 || 15000 | ||
+ | |} | ||
+ | |||
+ | = Wunet Packet Encapsulation = | ||
+ | |||
+ | [[ Image:wunet-encap.png | thumb | right | 400px | Wunet Packet Encapsulation ]] | ||
+ | |||
+ | Wunet is a virtual network overlayed over an IP network in which each Wunet packet is carried inside a UDP packet. | ||
+ | Although the underlying network need not be IP, we assume in all of our discussion that each Wunet packet is encapsulated in a UDP packet. | ||
+ | XXX | ||
+ | |||
+ | = A Wunet Packet = | ||
+ | |||
+ | [[ Image:wunet-pkt-hdr.png | thumb | right | 400px | Wunet Packet Header ]] | ||
+ | |||
+ | A Wunet packet header is four words (16 bytes) long. | ||
+ | Note that this version of Wunet has no field for detecting packet or packet header corruption. | ||
+ | Damaged packets are silently lost if the underlay network is unreliable | ||
+ | (e.g. UDP). | ||
+ | |||
+ | The first word of a Wunet header has XXX fields XXX | ||
+ | |||
+ | |||
+ | There are unicast and multicast DATA packets and multicast SUBSCRIBE and UNSUBSCRIBE multicast packets. | ||
= Basic Unicast DATA Packet Routing = | = Basic Unicast DATA Packet Routing = | ||
+ | |||
+ | |||
+ | RT: (vnet, dst) --> (qnum, quantum, links) | ||
+ | |||
+ | {| border=1 cellspacing=0 cellpadding=3 | ||
+ | ! colspan="4" | R1 || || colspan="4" | R2 || || colspan="4" | R3 || || colspan="4" | R4 | ||
+ | |- | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link | ||
+ | |- align="center" | ||
+ | | 1 || 11 || 0 || 1 || || 1 || 21 || 0 || 1 || || 1 || 31|| 0 || 1 || || 1 || 41|| 0 || 1 | ||
+ | |- align="center" | ||
+ | | 1 || 12 || 0 || 2 || || 1 || 22 || 0 || 2 || || 1 || 32|| 0 || 2 || || 1 || 42|| 0 || 2 | ||
+ | |- align="center" | ||
+ | | 1 || 13 || 0 || 3 || || 1 || 23 || 0 || 3 || || 1 || 33|| 0 || 3 || || 1 || 43|| 0 || 3 | ||
+ | |- align="center" | ||
+ | | 2 || 11 || 0 || 1 || || 2 || 21 || 0 || 1 || || 2 || 31|| 0 || 1 || || 2 || 41|| 0 || 1 | ||
+ | |- align="center" | ||
+ | | 2 || 12 || 0 || 2 || || 2 || 22 || 0 || 2 || || 2 || 32|| 0 || 2 || || 2 || 42|| 0 || 2 | ||
+ | |- align="center" | ||
+ | | 2 || 13 || 0 || 3 || || 2 || 23 || 0 || 3 || || 2 || 33|| 0 || 3 || || 2 || 43|| 0 || 3 | ||
+ | |} | ||
+ | |||
= Basic Multicast DATA Packet Routing = | = Basic Multicast DATA Packet Routing = | ||
+ | |||
+ | RT: (vnet, dst) --> (qnum, quantum, links) | ||
+ | |||
+ | {| border=1 cellspacing=0 cellpadding=3 | ||
+ | ! colspan="4" | R1 || || colspan="4" | R2 || || colspan="4" | R3 || || colspan="4" | R4 | ||
+ | |- | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link|| | ||
+ | ! vnet||dst||qnum||link | ||
+ | |- align="center" | ||
+ | | 1 || 11 || 0 || 1 || || 1 || 21 || 0 || 1 || || 1 || 31|| 0 || 1 || || 1 || 41|| 0 || 1 | ||
+ | |- align="center" | ||
+ | | 1 || 12 || 0 || 2 || || 1 || 22 || 0 || 2 || || 1 || 32|| 0 || 2 || || 1 || 42|| 0 || 2 | ||
+ | |- align="center" | ||
+ | | 1 || 13 || 0 || 3 || || 1 || 23 || 0 || 3 || || 1 || 33|| 0 || 3 || || 1 || 43|| 0 || 3 | ||
+ | |- align="center" | ||
+ | | 2 || 11 || 0 || 1 || || 2 || 21 || 0 || 1 || || 2 || 31|| 0 || 1 || || 2 || 41|| 0 || 1 | ||
+ | |- align="center" | ||
+ | | 2 || 12 || 0 || 2 || || 2 || 22 || 0 || 2 || || 2 || 32|| 0 || 2 || || 2 || 42|| 0 || 2 | ||
+ | |- align="center" | ||
+ | | 2 || 13 || 0 || 3 || || 2 || 23 || 0 || 3 || || 2 || 33|| 0 || 3 || || 2 || 43|| 0 || 3 | ||
+ | |} | ||
+ | |||
+ | |||
= Basic SUBSCRIBE/UNSUBSCRIBE Routing = | = Basic SUBSCRIBE/UNSUBSCRIBE Routing = | ||
+ | |||
+ | VT: vnet --> (plnk, qnum, quantum, links) | ||
+ | |||
+ | {| border=1 cellspacing=0 cellpadding=3 | ||
+ | ! colspan="4" | R1 || colspan="4" | R2 || colspan="4" | R3 || colspan="4" | R4 | ||
+ | |- | ||
+ | ! vnet||plnk||qnum||link | ||
+ | ! vnet||plnk||qnum||link | ||
+ | ! vnet||plnk||qnum||link | ||
+ | ! vnet||plnk||qnum||link | ||
+ | |- align="center" | ||
+ | | 1 || 0 || 1 || 1-6 || 1 || x21 || 1 || 1-6 || 1 || x31|| 1 || 1-6 || 1 || x41|| 1 || 1-6 | ||
+ | |- align="center" | ||
+ | | 2 || 4 || 2 || 1-4 || 2 || x22 || 2 || 1-4 || 2 || x32|| 2 || 1-4 || 2 || x42|| 2 || 1-4 | ||
+ | |} | ||
+ | |||
+ | |||
+ | = Virtual Link Rate Guarantees = | ||
+ | |||
+ | = Virtual Link Weighted Fair Sharing = | ||
= Route Learning = | = Route Learning = | ||
+ | |||
+ | A router will add a reverse route for any incoming packet with a source address not found in the routing table. | ||
= Flooding = | = Flooding = | ||
− | = Upstream | + | A unicast packet with no matching route table entry is forwarded by flooding. |
+ | |||
+ | = Upstream Subscription Propagation = | ||
+ | |||
+ | A multicast SUBSCRIBE packet with no matching route table entry is propagated toward the root of its multicast tree. | ||
= Spoofing Protection = | = Spoofing Protection = | ||
− | = | + | = XXX = |
A Wunet network consists of a set of nodes consisting of hosts and router nodes. | A Wunet network consists of a set of nodes consisting of hosts and router nodes. | ||
Line 72: | Line 201: | ||
A multicast address is any 32-bit address with its high-order bit set | A multicast address is any 32-bit address with its high-order bit set | ||
(i.e., any decimal number greater than 2^31-1 = 2,147,483,647). | (i.e., any decimal number greater than 2^31-1 = 2,147,483,647). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Latest revision as of 15:50, 5 February 2010
Contents
- 1 History of Wunet
- 2 A Wunet Virtual Network
- 3 Virtual Links
- 4 Wunet Packet Encapsulation
- 5 A Wunet Packet
- 6 Basic Unicast DATA Packet Routing
- 7 Basic Multicast DATA Packet Routing
- 8 Basic SUBSCRIBE/UNSUBSCRIBE Routing
- 9 Virtual Link Rate Guarantees
- 10 Virtual Link Weighted Fair Sharing
- 11 Route Learning
- 12 Flooding
- 13 Upstream Subscription Propagation
- 14 Spoofing Protection
- 15 XXX
History of Wunet
The Wunet Protocol is a simplified version of the Forest Protocol. Like Forest, Wunet is an overlay network that supports unicast and multicast traffic. But Wunet only supports only a rudimentary form of multicast and there is no provision for error control (e.g., dropped bits). It was developed primarily for educational purposes during the Fall 2009 semester for a course in the Computer Science and Engineering Department at Washington University in St. Louis.
This page describes the features of Wunet and gives several examples. These features include:
- Network Virtualization
- Unicast and Multicast Packets
- Virtual Link Rate Guarantee
- Virtual Link Weighted Fair Sharing
- Route Learning
- No-Route Flooding
- Upstream Subscription Propagation
- Spoofing Protection
A version of Wunet that is targeted at conventional processors has been implemented in C++. We plan to implement a GPE-only version of Wunet on the GENI deployment of the SPP as a precursor to implementing a fastpath verion involving the NPR.
A Wunet Virtual Network
labels: hosts, routers, links H11 H12 H13 H21 H22 H23 ... | ^ | ^ | ^ | ^ | ^ | ^ v | v | v | v | v | v | 1 2 3 1 2 3 R1 4-----------> R2 <-----------4 6| 5\ 6/|5 v \ / v ... R4 ------------> R3 <------------ | ^ | ^ | ^ | ^ | ^ | ^ v | v | v | v | v | v | H11 H12 H13 H21 H22 H23 ...
A Wunet network contains host nodes, router nodes and links that interconnect the nodes. The figure (right) shows four virtual routers directly connected to each other and each router is directly connected to three hosts.
Each host has one virtual link, and each router has six virtual links. A link between two nodes is virtual in the sense that it is actually a path in the underlying actual network. An example of the actual network might be an IP network where a virtual link is a communication path between two UDP endpoints (i.e., an IP address and UDP port number).
In the figure shown right, XXX
Virtual Links
LT: lnum --> (peerEP, type, padr, bitRate, pktRate)
R1 LT:
lnum | peerEP | type | padr | bitRate | pktRate |
---|---|---|---|---|---|
1 | 192.168.1.64:0 | host | 11 | 30000 | 15000 |
2 | 192.168.1.65:0 | host | 12 | 30000 | 15000 |
3 | 192.168.1.66:0 | host | 13 | 30000 | 15000 |
4 | 192.168.2.32:30123 | router | 200 | 30000 | 15000 |
5 | 192.168.2.80:30123 | router | 300 | 30000 | 15000 |
6 | 192.168.1.32:30123 | router | 400 | 30000 | 15000 |
Wunet Packet Encapsulation
Wunet is a virtual network overlayed over an IP network in which each Wunet packet is carried inside a UDP packet. Although the underlying network need not be IP, we assume in all of our discussion that each Wunet packet is encapsulated in a UDP packet. XXX
A Wunet Packet
A Wunet packet header is four words (16 bytes) long. Note that this version of Wunet has no field for detecting packet or packet header corruption. Damaged packets are silently lost if the underlay network is unreliable (e.g. UDP).
The first word of a Wunet header has XXX fields XXX
There are unicast and multicast DATA packets and multicast SUBSCRIBE and UNSUBSCRIBE multicast packets.
Basic Unicast DATA Packet Routing
RT: (vnet, dst) --> (qnum, quantum, links)
R1 | R2 | R3 | R4 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
vnet | dst | qnum | link | vnet | dst | qnum | link | vnet | dst | qnum | link | vnet | dst | qnum | link | |||
1 | 11 | 0 | 1 | 1 | 21 | 0 | 1 | 1 | 31 | 0 | 1 | 1 | 41 | 0 | 1 | |||
1 | 12 | 0 | 2 | 1 | 22 | 0 | 2 | 1 | 32 | 0 | 2 | 1 | 42 | 0 | 2 | |||
1 | 13 | 0 | 3 | 1 | 23 | 0 | 3 | 1 | 33 | 0 | 3 | 1 | 43 | 0 | 3 | |||
2 | 11 | 0 | 1 | 2 | 21 | 0 | 1 | 2 | 31 | 0 | 1 | 2 | 41 | 0 | 1 | |||
2 | 12 | 0 | 2 | 2 | 22 | 0 | 2 | 2 | 32 | 0 | 2 | 2 | 42 | 0 | 2 | |||
2 | 13 | 0 | 3 | 2 | 23 | 0 | 3 | 2 | 33 | 0 | 3 | 2 | 43 | 0 | 3 |
Basic Multicast DATA Packet Routing
RT: (vnet, dst) --> (qnum, quantum, links)
R1 | R2 | R3 | R4 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
vnet | dst | qnum | link | vnet | dst | qnum | link | vnet | dst | qnum | link | vnet | dst | qnum | link | |||
1 | 11 | 0 | 1 | 1 | 21 | 0 | 1 | 1 | 31 | 0 | 1 | 1 | 41 | 0 | 1 | |||
1 | 12 | 0 | 2 | 1 | 22 | 0 | 2 | 1 | 32 | 0 | 2 | 1 | 42 | 0 | 2 | |||
1 | 13 | 0 | 3 | 1 | 23 | 0 | 3 | 1 | 33 | 0 | 3 | 1 | 43 | 0 | 3 | |||
2 | 11 | 0 | 1 | 2 | 21 | 0 | 1 | 2 | 31 | 0 | 1 | 2 | 41 | 0 | 1 | |||
2 | 12 | 0 | 2 | 2 | 22 | 0 | 2 | 2 | 32 | 0 | 2 | 2 | 42 | 0 | 2 | |||
2 | 13 | 0 | 3 | 2 | 23 | 0 | 3 | 2 | 33 | 0 | 3 | 2 | 43 | 0 | 3 |
Basic SUBSCRIBE/UNSUBSCRIBE Routing
VT: vnet --> (plnk, qnum, quantum, links)
R1 | R2 | R3 | R4 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
vnet | plnk | qnum | link | vnet | plnk | qnum | link | vnet | plnk | qnum | link | vnet | plnk | qnum | link |
1 | 0 | 1 | 1-6 | 1 | x21 | 1 | 1-6 | 1 | x31 | 1 | 1-6 | 1 | x41 | 1 | 1-6 |
2 | 4 | 2 | 1-4 | 2 | x22 | 2 | 1-4 | 2 | x32 | 2 | 1-4 | 2 | x42 | 2 | 1-4 |
Virtual Link Rate Guarantees
Virtual Link Weighted Fair Sharing
Route Learning
A router will add a reverse route for any incoming packet with a source address not found in the routing table.
Flooding
A unicast packet with no matching route table entry is forwarded by flooding.
Upstream Subscription Propagation
A multicast SUBSCRIBE packet with no matching route table entry is propagated toward the root of its multicast tree.
Spoofing Protection
XXX
A Wunet network consists of a set of nodes consisting of hosts and router nodes. Each node has a 32-bit virtual node address (vaddr). By convention hosts have virtual node addresses between 1 and 99, and routers have addresses that are typically multiples of 100 (e.g., 300). A multicast address is any 32-bit address with its high-order bit set (i.e., any decimal number greater than 2^31-1 = 2,147,483,647).