Transcript Connectionless, Wireless, Multicast & ProxiNet

Systems Programming
Meeting 9:
Connectionless
Communication
GWU CS 259 Brad Taylor Spring 2004
1
Objectives
•
•
•
•
•
•
•
Connectionless Communication
User Data Protocol (UCP)
Team Formation (Peer-to-Peer) Model
Wireless Communication
Project Status Briefs (100% code review)
Assignment 4: due next week
Project Presentations next week!
GWU CS 259 Brad Taylor Spring 2004
2
From TCP to UDP
GWU CS 259 Brad Taylor Spring 2004
3
Success story #1: UDP
User Datagram Protocol: best-effort, process-to-process
– Lives on top of IP: adds corruption detection and “ports” so
packets can be addressed to a process on host
– Many header fields are hidden
UDP data cksum
src port
dst port
IP Hdr cksum
src IP addr
dst IP addr
GWU CS 259 Brad Taylor Spring 2004
Host: IP addr = 18.26.0.1
Port 1028
Port
Port 18
92
4
Two Connection Models
• Connectionless (or “datagram”):
– Packets contain enough information so routers can
decide how to get it to its final destination
b
b
B
A
C
• Connection-oriented (or “virtual circuit”)
– Connection between two nodes first set up
– Label it (called virtual circuit identifier: VCI)
– All packets carry label
1
1
1
B
A
GWU CS 259 Brad Taylor Spring 2004
C
5
Datagrams
• Simple idea:
– Don’t set up a connection, just make sure each packet contains
enough information to get to destination
– What is this? Complete destination address
– “In a connectionless network, you are always connected.”
D. Cheriton
• Forwarding:
– Switch creates “forwarding table”, mapping destinations to
output port (ignores input ports)
– When packet with destination address in table arrives, pushes
it out appropriate output port
– When packet with destination address not in table arrives,
must find out more routing information (next problem)
GWU CS 259 Brad Taylor Spring 2004
6
Datagram Tradeoffs
• Good:
– No round-trip delay to setup connection
– Each packet forwarded independently of last: if
switch or link fails, will be routed around it
– Resources allocated dynamically (adaptively) rather
than statically bound at connection time: lets each
“flow” achieve peak bandwidth of idle link
• Bad:
– Busy link = unpredictable, wild service fluctuations
– Each packet carries full destination address, which
makes per packet overhead higher
• Internet supports datagram (IP protocol)
GWU CS 259 Brad Taylor Spring 2004
7
Mobile Ad-Hoc Networks
• ProxiNet:
– Supports ad-hoc networks comprised of hand held
devices that facilitate exchange of information
between nodes
– Forms teams to accomplish given tasks
– Allows dynamic introduction and extraction of nodes
• Extends and demonstrates MANET issues :
– Node and link establishment and maintenance
– Communication scheme alternatives and
enhancements
– Network instantiation applications
GWU CS 259 Brad Taylor Spring 2004
8
On-Demand Multicast
Routing Protocol (ODMRP)
•
•
•
•
Developed by Internet Engineering Task Force (IETF) MANET working group
ODMRP forwards multicast packets to subset of nodes, minimizing
communication loading
Source establishes and maintains membership & routing information on demand
Soft state group membership maintenance approach: explicit control message not
required to leave
Join Query
Join Reply
Multicast Receiver
Multicast Source
Mobile Node
GWU CS 259 Brad Taylor Spring 2004
9
ODMRP Creation &
Maintenance
•
•
•
•
•
•
•
•
•
Multicast source with messages to send, but not a multicast group
route, periodically broadcasts a Join-Query until receiving
membership & routing information
Node receiving ODMRP message stores message source & sequence
number for duplicate detection
Reverse path to source node updated if routing table changed
Join-Query rebroadcast if not duplicate & time to live (TTL) > 0
Multicast group member receiving Join-Query, creates & broadcasts
Join-Reply to neighbors
Node receiving Join-Reply as “next hop” on source return path is
forwarding group member; sets a flag for that source node & sends its
Join Table
Process recursively executed by next routing table node, until reaching
multicast source, constructing (updating) route mesh from sources to
receivers
Join-Query periodically sent to refresh forwarding group & routes
Multicast source simply stops sending Join-Query messages to leave
group
GWU CS 259 Brad Taylor Spring 2004
10
Unicast Routing:
Dynamic Source Routing
•
•
•
•
•
DSR provides reactive, on-demand message routing
Each node maintains cache of routes to other known nodes, dynamically updated
as new routes determined
Route negotiation process entails first checking cache for non-expired hop-by-hop
route to destination
Expiration occurs if route error received, indicating broken link
Route discovery initiated if destination not in cache
N1-N2
N1-N2-N5
N2
N1
N5
N2
N5
N1-N3-N4
N1
N1-N2
N1
N1-N2-N5
N1-N3
N3
N4
N1-N3
Route Discovery
GWU CS 259 Brad Taylor Spring 2004
N1
N4
N3
Route Reply
11
DSR Creation & Maintenance
• Route discovery broadcast to all neighbors, with
source and destination addresses and a unique
identifier
• Recipients respond if
– (1) the destination or
– (2) holding a non-expired route in cache
• Otherwise, node appends its address to the
discovery request & forwards to all other neighbors
• Nodes only forward requests not yet seen by
examining the header field, limiting message
complexity
GWU CS 259 Brad Taylor Spring 2004
12
Unicast Routing:
Cluster-based Routing Protocol
• CBRP: a clustered, hierarchical, reactive (table driven) distant
vector routing method
• Ad hoc network partitioned into clusters; each ‘elects’ cluster head
• Mobile node belonging to two or more clusters is a gateway, known
to cluster heads, connecting the clusters
• Inter-cluster messages are routed via these gateways
Destination
Source
Cluster-head
GWU CS 259 Brad Taylor Spring 2004
Gateway
Normal node
13
CBRP Creation &
Maintenance
• Each node maintains two tables for originating messages:
– (1) Cluster member table, broadcast periodically, with cluster
membership information and
– (2) Routing table, with paths to cluster members, including the
head
• Intra-cluster messages are routed as previously discussed
• Remote message routed:
– 1: Local cluster head,
– 2: Via gateways and cluster heads until reaching destination
cluster head, and
– 3: Onto destination node
• A lowest-ID algorithm applied to form clusters:
– Each node, assigned a distinct ID, periodically broadcasts a cluster
nodes list, including its ID
– Lowest ID node in cluster, hearing only IDs higher than own, is
(becomes) cluster head
– Others are cluster members
– Node hearing two or more cluster heads is a gateway
GWU CS 259 Brad Taylor Spring 2004
14
Group Formation and
Management
• Group formation allows decomposition of
responsibilities too complex for individual
accomplishment into sub-tasks given deadline
assigned or resources available
• ProxiNet DSR protocol demonstrates robust team
management method suite suitable for variety of
mobile, ad hoc, distributed environments
• Clique (or Team) Formation allows teams, and nodes
belonging to multiple teams
• Team challenges stem from two aspects:
– Mobile environment teams form dynamically: nodes join and
leave at will, requiring proper maintenance procedures
– Same requirements and problems of any node in the regular
wireless infrastructure continue to apply to team nodes
GWU CS 259 Brad Taylor Spring 2004
15
Team Methods
•
Team methods
– Provide basic application-level (i.e., above network
layer) functionality
– Organize, maintain and disband MANET team
(group of nodes organized in peer-to-peer manner)
from previously unassociated entities
•
Individual nodes
– Unique, static name and IP address
– Dynamic set of skills (gainSkill)
– Negotiate to join team created for a set goal
(joinTeamReq)
•
Team leader (administration proxy)
–
–
–
–
•
Advertises for team members
Accepts bids meeting specified criteria (joinTeam)
Records member and collective information
Assigns each member a unique team ID
Goal partitioned into task set (assignTask)
– Tasks assigned & communicated to members for
accomplishment
– Handshaking used for robust operation
GWU CS 259 Brad Taylor Spring 2004
16
Team Methods (con’t)
•
Team member (node) may leave team (leaveTeamReq)
– Internal reasons or
– Lost due to communications link failure
– mobile, ad hoc, nature of the network highlights this
concern
•
Team leader loss requires New leader (electLeader)
– Elected from among peers (using the Bully Algorithm)
– Learn additional distributed team attributes from
members, minimizing information loss and overhead
while remaining robust
•
Changes
– Team membership & leadership changes sent to all
members use lightweight roster
– Negotiations with or requests from single members (i.e.,
acquiring new skills or assigned new tasks)
communicated between leader & involved member with
detailed heavyweight team information
– Special case: new leader election, as Bully Algorithm
entails sending successive messages to rapidly shrinking
group subset (those with lower team IDs) until complete
GWU CS 259 Brad Taylor Spring 2004
17
Extended Team Methods
•Extended methods provide
– Attribute-based negotiations for ‘active’ &
‘reserve’ members
– Modify task assignment process for
classification consistency
– Automate member negotiation and
reclassification between categories upon
departure
– Allow dynamic active team resource
expansion or reduction, as might be
necessary for varying network resource
demand
•Initial constraints include specified team size
– As target reached, subsequent bidders held
in reserve
– As size requirements change or a member
leaving team requires replacement, active
and reserve members’ skills serve as
negotiation basis
GWU CS 259 Brad Taylor Spring 2004
18
UDP/Socket Example:
Bare Minimum Client/Server
• Server:
– Creates a server socket bound to a fixed
port (12345)
– Receives a message from a client and
displays it
• Client:
– Creates a client socket
– Repeatedly sends the message "Hi" out of
this socket to the server
GWU CS 259 Brad Taylor Spring 2004
19
UDP Minimum:
udpServer.c
#include "def"
main()
{
int sd;
struct sockaddr_in server;
char buf[512];
int rc;
server.sin_family = AF_INET;
server.sin_addr.s_addr = htonl(INADDR_ANY);
server.sin_port = htons(12345);
sd = socket (AF_INET,SOCK_DGRAM,0);
bind ( sd, (SA *) &server, sizeof(server));
}
for(;;){
rc = recv (sd, buf, sizeof(buf), 0);
buf[rc]= (char) NULL;
printf("Received: %s\n", buf);
}
GWU CS 259 Brad Taylor Spring 2004
20
UDP Minimum:
udpClient.c
#include "def"
main(..)
{
int sd;
struct sockaddr_in server;
struct hostent *hp, *gethostbyname();
sd = socket (AF_INET,SOCK_DGRAM,0);
server.sin_family = AF_INET;
hp = gethostbyname(argv[1]);
bcopy ( hp->h_addr, &(server.sin_addr.s_addr), hp>h_length);
server.sin_port = htons(12345);
}
for (;;) {
sendto(sd, "HI",2, 0, (SA *) &server,
sizeof(server));
sleep(2);
}
GWU CS 259 Brad Taylor Spring 2004
21
Mapping UICI to Teams
• UICI functions and UDP Socket Team
Formation functions:
– u_join => {create UDP socket, bind & listen
for multicast messages}
– u_leave => {leave multicast group}
GWU CS 259 Brad Taylor Spring 2004
22
Final Project Report
•
•
•
•
•
•
Teams report next week (4/19)
Following week (4/26) “Final Prep”
15-20 minute Powerpoint presentation
All group members participate
Humor, A/V within capabilities encouraged
Discussion items include
–
–
–
–
–
–
–
•
Framework
Tasks Undertaken
Unique Solutions
Challenges
GWire Integration
Lessons Learned
Code Highlights
Written Report
–
–
–
–
5 – 8 pages, project synopsis
Code and Test cases, as appendices
Due: 4/26 (in class) or NLT 4/28 (CS mailbox)
“Formal Name” for Web Attribution
GWU CS 259 Brad Taylor Spring 2004
23
100% Project Status Report
Group I: Dan, Ricardo & Kamal: “Wire Socket”
Group II: Clayton, Jason: “Named Pipes”
Group III: Brooke, Nush, Ram: “Shared Memory,
Semaphores & Futexs”
Integration: Nate & Brad
Issues to discuss:
Code Review for Each Group
Error checking
Rough draft code submission for integration review
Further Guidance, Questions
GWU CS 259 Brad Taylor Spring 2004
24