HDU/HDOJ 2612 Find a way 双向BFS-socket编程步骤-SCTP协议源码分析--多归属特性multi-homed(二)

当前位置: 互联网>综合

本页文章导读:

▪HDU/HDOJ 2612 Find a way 双向BFS 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612 思路：从两个起点出发，有多个终点，求从两个起点同时能到达的终点具有的最小时间，开两个数组分别保存两个起点到达每一个终点的用.........

▪socket编程步骤参考文章：http://www.cnblogs.com/b2tang/archive/2009/05/28/1491471.html sockets（套接字）编程有三种，流式套接字（SOCK_STREAM），数据报套接字（SOCK_DGRAM），原始套接字（SOCK_RAW）；基于TCP的socket编程是.........

▪SCTP协议源码分析--多归属特性multi-homed(二) 继续看看path&assoc的断开和恢复管理。二. Manage transport andassociation 偶联的多归属管理主要针对transport，但多个transport/path的断开必然会倒致associatio.........

[1]HDU/HDOJ 2612 Find a way 双向BFS

来源: 互联网发布时间: 2013-10-25

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

思路：从两个起点出发，有多个终点，求从两个起点同时能到达的终点具有的最小时间，开两个数组分别保存两个起点到达每一个终点的用时，最后将两个

数组里的时间加起来求最小的一组，必须对应相加，因为终点必须同时到达。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
struct node{
	int x,y,step;
}a[1010];
node p,q;
int n,m,sx1,sy1,sx2,sy2,ans1[1010],ans2[1010],ans[1010];
int mmin,cnt;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};  
char maze[205][205];
bool visit[205][205];
int judge(int x,int y){
	for(int i=1;i<cnt;i++)
	{
		if(x==a[i].x&&y==a[i].y)return i;
	}
	return 0;
}
void bfs1(int x,int y){
	memset(ans,0,sizeof(ans));
	memset(ans1,-1,sizeof(ans1));
	memset(visit,0,sizeof(visit));
	queue<node> Q;
	p.x=x;
	p.y=y;
	p.step=0;
	Q.push(p);
	visit[p.x][p.y]=1;
	while(!Q.empty())
	{
		p=Q.front();
		Q.pop();
		int num=judge(p.x,p.y);
		if(num){
			ans[num]=p.step;
			visit[p.x][p.y]=1;
		}
		for(int i=0;i<4;i++)
		{
			q.x=p.x+dir[i][0];
			q.y=p.y+dir[i][1];
			q.step=p.step+1;
			if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;
			if(visit[q.x][q.y])continue;
			if(maze[q.x][q.y]=='#')continue;
			Q.push(q);
			visit[q.x][q.y]=1;
		}
	}
	for(int i=1;i<cnt;i++){
		if(ans[i])ans1[i]=ans[i];
	}
	
}
void bfs2(int x,int y){
	memset(ans,0,sizeof(ans));
	memset(ans2,-1,sizeof(ans2));
	memset(visit,0,sizeof(visit));
	queue<node> Q;
	p.x=x;
	p.y=y;
	p.step=0;
	Q.push(p);
	visit[p.x][p.y]=1;
	while(!Q.empty())
	{
		p=Q.front();
		Q.pop();
		int num=judge(p.x,p.y);
		if(num){
			ans[num]=p.step;
			visit[p.x][p.y]=1;
		}
		for(int i=0;i<4;i++)
		{
			q.x=p.x+dir[i][0];
			q.y=p.y+dir[i][1];
			q.step=p.step+1;
			if(q.x<0||q.x>=n||q.y<0||q.y>=m)continue;
			if(visit[q.x][q.y])continue;
			if(maze[q.x][q.y]=='#')continue;
			Q.push(q);
			visit[q.x][q.y]=1;
		}
	}
	for(int i=1;i<cnt;i++){
		if(ans[i])ans2[i]=ans[i];
	}
}
int main()
{
	//ifstream fin;
	//fin.open("data1.txt");
	
	while(cin>>n>>m)
	{
		cnt=1;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				cin>>maze[i][j];
				if(maze[i][j]=='Y'){
					sx1=i;
					sy1=j;
				}
				if(maze[i][j]=='M'){
					sx2=i;
					sy2=j;
				}
				if(maze[i][j]=='@'){
					a[cnt].x=i;
					a[cnt++].y=j;
				}
			}
			mmin=999999;
			bfs1(sx1,sy1);
			bfs2(sx2,sy2);
			for(int i=1;i<cnt;i++)
			{
				if(ans1[i]!=-1&&ans2[i]!=-1){
					int tsum=ans1[i]+ans2[i];
					if(mmin>tsum)mmin=tsum;
				}
			}
			cout<<mmin*11<<endl;
	}
	return 0;

}

作者：xiaozhuaixifu 发表于2013-6-19 13:42:18 原文链接

阅读：77 评论：0 查看评论

[2]socket编程步骤

来源: 互联网发布时间: 2013-10-25

参考文章：http://www.cnblogs.com/b2tang/archive/2009/05/28/1491471.html

sockets（套接字）编程有三种，流式套接字（SOCK_STREAM），数据报套接字（SOCK_DGRAM），原始套接字（SOCK_RAW）；基于TCP的socket编程是采用的流式套接字。

服务器端编程的步骤：

1：加载套接字库，创建套接字(WSAStartup()/socket())；

2：绑定套接字到一个IP地址和一个端口上(bind())；

3：将套接字设置为监听模式等待连接请求(listen())；

4：请求到来后，接受连接请求，返回一个新的对应于此次连接的套接字(accept())；

5：用返回的套接字和客户端进行通信(send()/recv())；

6：返回，等待另一连接请求；

7：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。

客户端编程的步骤：

1：加载套接字库，创建套接字(WSAStartup()/socket())；

2：向服务器发出连接请求(connect())；

3：和服务器端进行通信(send()/recv())；

4：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。

第一式: 加载/释放Winsock库:

1.加载方法:

WSADATA wsa;
/*初始化socket资源*/
if (WSAStartup(MAKEWORD(1,1),&wsa) != 0)
{
return; //代表失败
}

2.释放方法:

WSACleanup();

第二式: 构造SOCKET:

1.服务端:构造监听SOCKET,流式SOCKET.
SOCKET Listen_Sock = socket(AF_INET, SOCK_STREAM, 0)

2.客户端:构造通讯SOCKET,流式SOCKET.
SOCKET Client_Sock = socket(AF_INET, SOCK_STREAM, 0)

第三式:配置监听地址和端口:

1.服务端: SOCKADDR_IN serverAddr
ZeroMemory((char *)&serverAddr,sizeof(serverAddr));
   serverAddr.sin_family = AF_INET;
   serverAddr.sin_port = htons(1234);           /*本地监听端口:1234*/
   serverAddr.sin_addr.s_addr = htonl(INADDR_ANY); /*有IP*/

第四式: 绑定SOCKET:

1.服务端:绑定监听SOCKET.
bind(Listen_Sock,(struct sockaddr *)&serverAddr,sizeof(serverAddr))

第五式: 服务端/客户端连接:

1.服务端:等待客户端接入.
SOCKET Command_Sock = accept(Listen_Sock, ...)

2.客户端:请求与服务端连接.
int ret = connect(Client_Sock, ...)

第六式: 收/发数据:

1.服务端:等待客户端接入.char buf[1024].
接收数据:recv(Command_Sock,buf, ...)
或
发送数据:send(Command_Sock,buf, ...)

2.客户端:请求与服务端连接.char buf[1024].
发送数据:send(Client_Sock,buf, ...)
或
接收数据:recv(Client_Sock,buf, ...)

第七式: 关闭SOCKET:

1.服务端:关闭SOCKET.
closesocket(Listen_Sock)
closesocket(Command_Sock)

2.客户端:关闭SOCKET.
closesocket(Client_Sock)

作者：jeakon 发表于2013-6-19 21:40:30 原文链接

阅读：3 评论：0 查看评论

[3]SCTP协议源码分析--多归属特性multi-homed(二)

来源: 互联网发布时间: 2013-10-25

继续看看path&assoc的断开和恢复管理。

二. Manage transport andassociation

偶联的多归属管理主要针对transport，但多个transport/path的断开必然会倒致association也断开。所以追踪path的更新、断开和恢复，也离不开assoc的断开和恢复管理。

每个path的传送失败（即收不到SACK），除了本path出错计数外，assoc的出错计数器也要递增。除了primary transport(主通路)在传送DATA期间外，在primarytransport闲时和alternatetransport（备用通路）上，一般是通过发送HeartBeat来检测链路状态。

path和assoc的出错计数器分别如下：

transport->error_count和asoc->overall_error_count

path和assoc的几种状态分别如下：

pathstate： 0-Unactive，1-Active，2-Unconfirm。

assocstate：0~max，4是已建立。/proc/net/sctp/assoc中“ST”项表示偶联状态。

1、何时更新path

操作函数：sctp_assoc_control_transport #net/sctp/associola.c

操作对象：asoc->primary_path

asoc->active_path

asoc->retran_path

操作类型：up / down

(1). SCTP_TRANSPORT_UP点：sctp_check_transmitted,sct_cmd_transport_on

(2). SCTP_TRANSPORT_DOWN点：sctp_do_8_2_transport_strike #可能会更新active_path！

2、DOWN：何时断开path

path重传次数超过最大值（可通过/proc/sys/net/sctp/path_max_retrans设置），path通路断开。

操作函数：sctp_do_8_2_transport_strike，实现源码如下所示：

	/* The check for association's overall error counter exceeding the
	 * threshold is done in the state function.
	 */
	/* We are here due to a timer expiration.  If the timer was
	 * not a HEARTBEAT, then normal error tracking is done.
	 * If the timer was a heartbeat, we only increment error counts
	 * when we already have an outstanding HEARTBEAT that has not
	 * been acknowledged.
	 * Additionally, some tranport states inhibit error increments.
	 */
	if (!is_hb) {               
		asoc->overall_error_count++;
		if (transport->state != SCTP_INACTIVE)
			transport->error_count++;                //传送失败次数统计，下同
	 } else if (transport->hb_sent) {
		if (transport->state != SCTP_UNCONFIRMED)
			asoc->overall_error_count++;
		if (transport->state != SCTP_INACTIVE)
			transport->error_count++;
	}
//。。。（略），SCTP_PF状态处理
	if (transport->state != SCTP_INACTIVE &&
	    (transport->error_count > transport->pathmaxrxt)) {        //通路失败次数比较
		SCTP_DEBUG_PRINTK_IPADDR("transport_strike:association %p",
					 " transport IP: port:%d failed.\n",
					 asoc,
					 (&transport->ipaddr),
					 ntohs(transport->ipaddr.v4.sin_port));
		sctp_assoc_control_transport(asoc, transport,
					     SCTP_TRANSPORT_DOWN,         //通路断开
					     SCTP_FAILED_THRESHOLD);
	}

sctp_do_8_2_transport_strike这个函数何时被调用：(都在sctp_cmd_interpreter中)

(1). SCTP_CMD_STRIKE -> sctp_do_8_2_transport_strike

触发点：sctp_sf_do_6_3_3_rtx,sctp_sf_t2_timer_expire, sctp_sf_t4_timer_expire